Syllabus_for_4th_Semester_Algorithms.md

Practical / Lab work to be performed for Design and Analysis of Algorithms

1. Implement Insertion Sort (The program should report the number of comparisons)

• Click me to Navigate to the C file
• Click me to Navigate to the Java file

2. Implement Merge Sort(The program should report the number of comparisons)

• Click me to Navigate to the C file
• Click me to Navigate to the Java file

3. Implement Heap Sort(The program should report the number of comparisons)

• Click me to Navigate to the C file
• Click me to Navigate to the Java file

4. Implement Randomized Quick sort (The program should report the number of comparisons)

• Click me to Navigate to the C file

1. Implement Radix Sort

• Click me to Navigate to the C file

2. Create a Red-Black Tree and perform following operations on it: i. Insert a node ii. Delete a node iii. Search for a number & also report the color of the node containing this number.

3. Write a program to determine the LCS of two given sequences

4. Implement Breadth-First Search in a graph

5. Implement Depth-First Search in a graph

6. Write a program to determine the minimum spanning tree of a graph

   For the algorithms at S.No 1 to 3 test run the algorithm on 100 different inputs of sizes varying from 30 to 1000. Count the number of comparisons and draw the graph. Compare it with a graph of nlogn.