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.