SPPU Computer Engineering Second Year (SE) Data Structures & Algorithms (DSA) Lab Assignments (2019 Pattern)
Aledutron Youtube PPS Lab Playlist Link: https://www.youtube.com/playlist?list=PLlShVH4JA0ov8DstIyTidJhSmW4WIGa7V
| Question No. | Problem Statement | Code Link | Youtube Link |
|---|---|---|---|
| Group A | |||
| 1 | Consider telephone book database of N clients. Make use of a hash table implementation to quickly look up client‘s telephone number. Make use of two collision handling techniques and compare them using number of comparisons required to find a set of telephone numbers | ||
| 2 | Implement all the functions of a dictionary (ADT) using hashing and handle collisions using chaining with / without replacement. 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) | ||
| 3 | For given set of elements create skip list. Find the element in the set that is closest to some given value. (note: Decide the level of element in the list Randomly with some upper limit) | ||
| 4 | To create ADT that implement the "set" concept. a. Add (newElement) -Place a value into the set b. Remove (element) Remove the value c. Contains (element) Return true if element is in collection d. Size () Return number of values in collection Iterator () Return an iterator used to loop over collection e. Intersection of two sets f. Union of two sets g. Difference between two sets h.Subset |
||
| Group B | |||
| 5 | 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. | ||
| 6 | 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 from root 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 |
Group-B/Q6.cpp | https://www.youtube.com/watch?v=y7Ckft2iHls&list=PLlShVH4JA0ov8DstIyTidJhSmW4WIGa7V&index=1&pp=iAQB |
| 7 | Construct an expression tree from the given prefix expression eg. +--a*bc/def and traverse it using postordertraversal(non recursive) and then delete the entire tree. | ||
| 8 | Read for the formulas in propositional calculus. Write a function that reads such a formula and creates its binary tree representation. What is the complexity of your function? | ||
| 9 | Convert given binary tree into threaded binary tree. Analyze time and space complexity of the algorithm. | ||
| 10 | Consider threading a binary tree using preorder threads rather than inorder threads. Design an algorithm for traversal without using stack and analyze its complexity. | ||
| 11 | 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. | ||
| 12 | Implement a file compression algorithm that uses binary tree. Your program should allow the user to compress and decompress messages containing alphabets using the standard Huffman algorithm for encoding and decoding. | ||
| Group C | |||
| 13 | Represent a given graph using adjacency matrix/list to perform DFS and using adjacency list to perform BFS. Use the map of the area around the college as the graph. Identify the prominent land marks as nodes and perform DFS and BFS on that. | Group-C/Q13.cpp | https://www.youtube.com/watch?v=9HBNPDp4U6E&list=PLlShVH4JA0ov8DstIyTidJhSmW4WIGa7V&index=2&pp=iAQB |
| 14 | 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. Check whether the graph is connected or not. Justify the storage representation used. | ||
| 15 | You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. Solve the problem by suggesting appropriate data structures. | ||
| 16 | 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. | ||
| 17 | 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 D | |||
| 18 | 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? | ||
| 19 | 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 | ||
| Gourp E | |||
| 20 | Consider a scenario for Hospital to cater services to different kinds of patients as a) Serious (top priority), b) non-serious (medium priority), c) General Checkup (Least priority). Implement the priority queue to cater services to the patients. |
||
| 21 | Implement the Heap/Shell sort algorithm implemented in Java demonstrating heap/shell data structure with modularity of programming language | ||
| 22 | Read the marks obtained by students of second year in an online examination of particular subject. Find out maximum and minimum marks obtained in that subject. Use heap data structure. Analyze the algorithm. | Group-E/Q22.cpp | https://www.youtube.com/watch?v=OI0cUNtHLLU&list=PLlShVH4JA0ov8DstIyTidJhSmW4WIGa7V&index=3&pp=iAQB |
| Group F | |||
| 23 | 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-F/Q23.cpp | https://www.youtube.com/watch?v=4oUKl3bAI4w&list=PLlShVH4JA0ov8DstIyTidJhSmW4WIGa7V&index=4&pp=iAQB |
| 24 | 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. | ||
| 25 | Implementation of a direct access file -Insertion and deletion of a record from a direct access file | ||
| 26 | Assume we have two input and two output tapes to perform the sorting. The internal memory can hold and sort m records at a time. Write a program in java for external sorting. Find out time complexity. | ||
| Mini Project | |||
| 27 | 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. | ||
| 28 | Design a mini project to implement Snake and Ladders Game using python. | ||
| 29 | Design a mini project to implement a Smart text editor. | ||
| 30 | Design a mini project for automated Term work assessment of student based on parameters like daily attendance, Unit Test / Prelim performance, Students achievements if any, Mock Practical |