Syllabus (COMPUTER SCIENCE)

Course Type: MAJ-6

Semester: 5

Course Code: BCOSMAJ06C

Course Title: Design and Analysis of Algorithm

(L-P-Tu): 4-2-0

Credit: 6

Practical/Theory: Combined

Course Objective: 1. To understand the role, characteristics and need of algorithms. 2. To understand the classification strategies of algorithms and recursive algorithms.

Learning Outcome: 1. Ability to analyze asymptotic runtime complexity of algorithms including formulating recurrence relations. 2. Ability to understand and design algorithms using greedy strategy, divide and conquer approach, dynamic programming, Demonstrate a familiarity with major algorithms and data structures.

Theory

Introduction:

Analysis of Algorithms: Insertion Sort, Merge Sort, Time and Space Complexity, Growth of Functions: Asymptotic Notation, Recurrences: Substitution, Iteration, Master Method. (10 Lectures)

Divide and Conquer Algorithms:

General method, Quicksort, Randomized Algorithms, Applications-Analysis of Binary Search, Heap Sort, Matrix Multiplication. (10 Lectures)

Greedy Algorithms:

Introduction to Greedy Strategies, Minimum Spanning Tree: Kruskal’s Algorithm, Prim’s Algorithm, Huffman Coding. (8 Lectures)

Dynamic programming:

Principles Of Dynamic Programming, Memorization and Tabulation Techniques, Knapsack Problem, Matrix Chain Multiplication, Longest Common Subsequence. ( 10 Lectures)

Graph Algorithms:

Graph Traversal: BFS And DFS, Topological Sort, Strongly Connected Components, Single-Source Shortest Paths: The Bellman-Ford Algorithm, Dijkstra’s Algorithm, All-Pairs Shortest Paths: The Floyd-Warshall Algorithm. (12 Lectures)

Introduction to Complexity Theory:

Basic Concepts, Non-Deterministic Algorithms, NP-Hard And NP-Complete Classes, Cook‘s Theorem. (10 Lectures)

DESIGN AND ANALYSIS OF ALGORITHMS LAB

1. Write a program to perform Insertion Sort, Merge Sort, Quicksort, Heap Sort for the given list of integer values.

2. Write a program to find Maximum and Minimum of the given set of integer values.

3. Write a Program to perform Binary Search for a given set of integer values recursively and non-recursively.

8. Write a program to find solution for knapsack problem using greedy method.

9. Write a program to find minimum cost spanning tree using Prim’s Algorithm.

10. Write a program to find minimum cost spanning tree using Kruskal’s Algorithm.

11. Write a program to perform Single source shortest path problem for a given graph.

12. Write a program to find solution for job sequencing with deadlines problem.

13. Write a program for all pairs shortest path problem.

14. Write a program to solve N-QUEENS problem.

15. Write a program to solve Sum of subsets problem for a given set of distinct numbers.

Reading References:

1. T.H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms, PHI

2. Sarabasse & A.V. Gelder Computer Algorithm - Introduction to Design and Analysis, Pearson.

3. A. Aho, V. Alfred, J. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley.