Design and Analysis of Algorithm Lab

Instructions:

1. The course objectives and course outcomes are identical to that of (Design and Analysis of Algorithm) as this is the practical component of the corresponding theory paper.
2. The practical list shall be notified by the teacher in the first week of the class commencement under intimation to the office of the Head of Department / Institution in which the paper is being offered from the list of practicals below. At least 10 experiments must be performed by the students, they may be asked to do more. At least 5 experiments must be from the given list.

List of Programs

1. To implement following algorithm using array as a data structure and analyse its time complexity. a) Merge sort      b) Quick sort     c) Bubble sort     d) Selection sort    e) Heap sort
2. To implement Linear search and Binary search and analyse its time complexity.
3. To implement Huffman Coding and analyse its time complexity.
4. To implement Minimum Spanning Tree and analyse its time complexity.
5. To implement Dijkstra‘s algorithm and analyse its time complexity.
6. To implement Bellman Ford algorithm and analyse its time complexity.
7. Implement N Queen's problem using Back Tracking.
8. To implement Matrix Multiplication and analyse its time complexity.
9. To implement Longest Common Subsequence problem and analyse its time complexity.
10. To implement naïve String Matching algorithm, Rabin Karp algorithm and Knuth Morris Pratt algorithm and analyse its time complexity.
11. To implement Sorting Network.