Advanced Data Structures

NOTE: These Programs are just for example. 

They may not fulfil the actual requirement of Question!

Group A

1. Beginning with an empty binary search tree, Construct binary search tree by inserting the

values in the order given. After constructing a binary tree -

i. Insert new node

ii. Find number of nodes in longest path

iii. Minimum data value found in the tree

iv. Change a tree so that the roles of the left and right pointers are swapped at every node

v. Search a value
DOWNLOAD THIS PROGRAM

2. Convert given binary tree into threaded binary tree. Analyze time and space complexity of the algorithm.
DOWNLOAD THIS PROGRAM

3. For given expression eg. a-b*c-d/e+f construct inorder sequence and traverse it using postorder traversal(non recursive).

DOWNLOAD THIS PROGRAM

Group B

5. There are flight paths between cities. If there is a flight between city A and city B then there is an edge between the cities. The cost of the edge can be the time that flight take to reach city B from A, or the amount of fuel used for the journey. Represent this as a graph. The node can be represented by airport name or name of the city. Use adjacency list representation of the graph or use adjacency matrix representation of the graph. Justify the

storage representation used.

DOWNLOAD THIS PROGRAM (Dijsktra & BFT DFT)

6. Tour operator organizes guided bus trips across the Maharashtra. Tourists may have different preferences. Tour operator offers a choice from many different routes. Every day the bus moves from starting city S to another city F as chosen by client. On this way, the tourists can

see the sights alongside the route travelled from S to F. Client may have preference to choose route. There is a restriction on the routes that the tourists may choose from, the bus has to take a short route from S to F or a route having one distance unit longer than the minimal distance. Two routes from S to F are considered different if there is at least one road from a

city A to a city B which is part of one route, but not of the other route.

DOWNLOAD THIS PROGRAM (Dijsktra & BFT DFT)

(STUDY ASSIGNMENT)

7. Consider the scheduling problem. n tasks to be scheduled on single processor. Let t1, ..., tn be durations required to execute on single processor is known. The tasks can be executed in any order but one task at a time. Design a greedy algorithm for this problem and find a schedule that minimizes the total time spent by all the tasks in the system. (The time spent by one is the sum of the waiting time of task and the time spent on its execution.)

Group C

8. Implement all the functions of a dictionary (ADT) using hashing.

Data: Set of (key, value) pairs, Keys are mapped to values, Keys must be comparable, Keys must be unique Standard Operations: Insert(key, value), Find(key), Delete(key)

9. Consider telephone book database of N clients. Make use of a hash table implementation to quickly look up client‘s telephone number.

Group D

10. A Dictionary stores keywords & its meanings. Provide facility for adding new keywords, deleting keywords, updating values of any entry. Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Height balance tree and find the complexity for finding a keyword

DOWNLOAD THIS PROGRAM (AVL)

Group E

11. Read the marks obtained by students of second year in an online examination of particular subject. Find out maximum and minimum marks obtained in a that subject. Use heap data structure. Analyze the algorithm.

Group F

12. Department maintains a student information. The file contains roll number, name, division and address. Allow user to add, delete information of student. Display information of particular employee. If record of student does not exist an appropriate message is displayed.

If it is, then the system displays the student details. Use sequential file to main the data.

Group G

13. Write a Java program which will demonstrate a concept of Interfaces and packages: In this assignment design and use of customized interfaces and packages for a specific application are expected
DOWNLOAD NETBEANS PROJECT FILE

14. Any application defining scope of Formal parameter, Global parameter, Local parameter accessing mechanism and also relevance to private, public and protected access. Write a Java program which demonstrates the scope rules of the programming mechanism.

15. Write a Java program for the implementation of different data structures using JAVA

collection libraries (Standard toolkit library): at least 5 data structures are used to design a suitable application.

Mini Project

Design a mini project using JAVA which will use the different data structure
with or without Java collection library and show the use of specific data
structure on the efficiency (performance) of the code.