Second Year of Computer Engineering (2019 Course)
210257: Data Structures & Algorithms Laboratory

INDEX

 

1. Given sequence k = k1 <k2 < ... < kn of n sorted keys, with a search probability pi for each key ki . Build the Binary search tree that has the least search cost given the access probability for each key.

2. Implement the Heap/Shell sort algorithm implemented in Java demonstrating heap/shell data structure.

3. 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).

4. Represent given graph using adjacency matrix/list to perform DFS and adjacency list to perform BFS. Use map of area around the college as a graph. Identify prominent landmark as nodes and perform DFS and BFS on that.

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 takes 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.

6. Consider Telephone book database of N clients. Make use of hash table implementation to quickly look up clients telephone number.

7. 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 Binary Search Tree for implementation.

8. 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 .

9. A book consists of chapters, chapters consist of sections and sections consist of subsections. Construct a tree and print the nodes. Find the time and space requirements of your method.

10. Company maintains employee information as employee ID, name, designation and salary. Allow user to add, delete information of employee. Display information of particular employee. If employee does not exist an appropriate message is displayed. If it is, then the system displays the employee details. Use index sequential file to maintain the data.

11. 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 students. If record of student does not exist an appropriate message is displayed. If it is, then the system displays the student details.

12. 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 fins complexity for finding keyword.