CS-2008

Lab Programs

Lab 1 : Time complexity analysis Insertion Sort
Lab 2 : Time complexity analysis Selection Sort
Lab 3 : Random Problems
Lab 4
- Time complexity analysis Merge Sort
- Comparison b/w linear and dnc strategy for Max-Min Problem
Lab 5
- Time complexity analysis Quick Sort
- Time complexity analysis Heap Sort
Lab 6 : Implementation of Priority Queue using Binary Heap
Lab 7 Dynamic Programming Approach
- Longest Common Subsequence Problem
- Optimal Parenthesization : Matrix Chain Multiplication Problem
Lab 8 Greedy Algorithms
- Activity Selection
- Job Sequencing
- Magnetic Tape Storage
- Knapsack Problem (Also solved using dynamic approach)
- Huffman Code
Lab 9 : Implementing a 2D map/maze

Group Assignment: Minimum Spanning Tree

We have some network nodes on a 2D cartesian plane.

Objective

Connect all the network nodes to a network with the minimum possible packet exchange cost.
For this purpose we construct a minimum spanning tree with the vertices being the network nodes and the edges being the network lines.