# Java Data Structure

we will perform some experiments with Hash Table, Disjoint Set, and

Graph algorithms. You may use the source codes that we have created in the lab exercises folder of the

Q1. [5 marks] We have discussed Disjoint Set ADT in the lab. It performs “union” and “find” operations.

In a simple implementation of union operation, it changes the parent of one set to another set without

considering any weight factor of the parent. This can create a skewed tree and search may become

inefficient. Create a DisjointSetADT class with “Union” and “Find” operations. In the union operation

consider the weight of the parents and make the heavier set as the parent set of the lighter set.

Q2. [5 Marks] Given an array of characters, give an O(n) algorithm (that is you can visit each character

only once) for removing the duplicates. [Hint: use hash table].

Q3. [10 Marks] Given a list of pairs; Give an efficient method (O(n)) to print all “Symmetric Pairs”. A pair

is symmetric if both pair (i, j) and pair (j, i) exist in the list. For example, in { {3, 1}, {2, 6}, {3, 5}, {7, 4}, {5,

3}, {8, 7} } , note that {3, 5} is already present in the list when you encounter {5, 3}, that means they are

symmetric pair, so print this pair when you encounter {5, 3}. [Hint: use hash table]

Algorithm:

1) Read the pairs of elements one by one and insert them into a hash

table. For each pair, consider the first element as a key and

second element as value.

2) While inserting the key elements check if the hashing of the

second element of the current pair is the same as the first

number of the current pair.

3) If they are the same, this means that the pairs are symmetric and

output that pair.

4) Otherwise, insert that element into that. That means, use the

first number of the pair as key and the second number as value

and insert them into the hash table.

5) By the time we complete the scanning of all pairs, we have output

all the symmetric pairs.

Q4. [5 Marks] Given an unweighted directed graph G, write a program that counts and prints all simple

paths from a given ‘s’ to a given ‘d’. Assume the graph G is represented using adjacent matrix.

Q5 [5 Marks] Write a program to determine whether a given unweighted undirected graph G contains a

cycle or not.

Q6. [5 Marks] Implement the GraphADT using Adjacency List and test it with BFS search.

Q7. [15 Marks] There is a maze of size N x N. You are designing a robot that can traverse through the

maze and find the exit point. You can select a starting point in the maze ‘S’ and there is only one exist

point marked as ‘E’. Your robot needs to find the shortest path (with minimum energy cost) from 'S' to

'E' in the maze.

➔ The robot can only move left (L), right (R), up (U) and down (D) from a cell.

➔ An empty cell in a maze is represented as ‘.’

➔ Once the robot moves from one cell, it loses one unit of energy.

➔ There are some obstacles in some cells (marked as ‘R’), the robot cannot pass through them.

➔ You cannot cross the boundary of the maze.

➔ If there is no path then print -1, otherwise print the shortest path (in terms of move) from

‘S’ to ‘E’.

Sample 1

Input:

4 (this is the value of the N, which means the maze is a 4x4 maze)

. . . S

. R R .

. . R R

R . . E

Output: 9 moves.

L L L D D R D R R

Sample 2

5

. . S . R

. R R . .

. . R R E

R . . . R

R . . . R

Output: 4 moves.

R D R D

Sample 3

5

. . S . R

. R R . .

. R . R R

R . . E .

R . . . R

Output: -1

Beceriler: Java

İşveren Hakkında:
( 6 değerlendirme ) kamloops, Canada

Proje NO: #22524083

## Bu iş için 8 freelancer ortalamada \$70 teklif veriyor

koustav2006

Hi..i am proficient in core Java object oriented programming along with data structures, algorithms and can help you answer all the questions and write the programs.

\$100 CAD in 3 gün içinde
(185 Değerlendirme)
6.3
iridescent2x15

Hi I am computer software engineer and have done many java and technical projects. You can share more details in chat. Thank you

\$150 CAD in 7 gün içinde
(65 Değerlendirme)
6.0

Hello. I am the Java expert and lover. In Java, I've no problem. I've 9+ years of experience in developing large Java app/libs. I've major in Java and Java binary codes, so I'll guarantee best quality. I'm interested i Daha Fazla

\$80 CAD in 7 gün içinde
(2 Değerlendirme)
1.3
shindeps4545

Hello, I'm interested in your project. I am a Java Developer (Specialist in Java ,Python). I am working in this field from last 4+ years, perfection always top priority. Please send me a message so that we can discuss Daha Fazla

\$30 CAD in 4 gün içinde
(3 Değerlendirme)
2.5
kashifaws

Hey Brother,I Will Do Your Assignment If You Need Me Let Me Know And Assign To Me, I Have Decent Experience In Development You Can Check My Portfolio From My Profile I Can Do Your Work Timely. Thanks

\$60 CAD in 5 gün içinde
(0 Değerlendirme)
0.0
kodersin

Koders is a service-based organization of developers that has 4+ years of experience in software development. Koders is an All-in-one place for software development that's minimalistic, confidential and develops produc Daha Fazla

\$20 CAD in 7 gün içinde
(0 Değerlendirme)
0.0
ateeq1

Experience Designer UI/UX I am expert in advertisement design,logo design, banner design, ads design. I have read your project description very carefully. I’m eager to talk with you and discuss details. Thank you for Daha Fazla

\$20 CAD in 7 gün içinde
(1 Yorum)
0.6
Webguru71

Hello, I am a java Developer.I also have strong knowledge of the skills listed below: 1- java, JavaScript, javafx, Html, CSS. 2- Native Application. 3- Mobile Application. 4- Web Application. 5- SQLite, MySQL. Daha Fazla

\$100 CAD in 7 gün içinde
(0 Değerlendirme)
0.0