5th sem syllabus:Design and Analysis of Algorithms

Course Title: Design and Analysis of Algorithms

Course no: CSC-303                                                                                    Full Marks: 90+10

Credit hours: 3                                                                                  Pass Marks: 36+4

Nature of course: Theory (3 Hrs.)

Course Synopsis:     Methods and tools for analyzing different algorithms. Different approaches of designing efficient algorithms like divide and conquer paradigm, greedy paradigm, dynamic programming. Algorithms pertainig various problems like sorting, searching, shortest path, spanning trees, geometric problems etc. NP-complete problems.

Goal:   Competency in analyzing different algorithms encountered. Ability to conquer the problem with efficient algorithm using the algorithm development paradigms.

Course Contents:

Unit 1.                                                                                                             10 Hrs.

1.1    Algorithm Analysis: worst, best and average cases, space and time complexities. Mathematical background: asymptotic behavior, solving recurrences.

1.2    Data Structures Review: linear data structures, hierarchical data structures, data structures for representing graphs and their properties. Search structures: heaps, balanced trees, hash tables.

Unit 2.                                                                                                             14 Hrs.

2.1    Divide and Conquer: Concepts, applications, sorting problems(quick, merge), searching (binary), median finding problem and general order statistics, matrix multiplications.

2.2    Greedy Paradigm: Concepts, applications, Knapsack problem, job sequencing, Huffman codes.

2.3    Dynamic Programming: Concepts, applications, Knapsack problem, longest common subsequence, matrix chain multiplications.

Unit 3                                                                                                              21 Hrs.

3.1    Graph Algorithms: breadth-first and depth-first search and their applications, minimum spanning trees (Prim's and Kruskal's algorithms), shortest path problems (Dijkstra's and flyod's algorithms), algorithm for directed acyclic graphs (DAGs).

3.2    Geometric Algorithms: Concepts, polygon triangulation, Convex hull computation.

3.3    NP Completeness: Introduction, class P and NP, cooks theorem, NP complete problems: vertex cover problem.

3.4    Introductions: Randomized algorithms concepts, randomized quick sort, approximation algorithms concepts, vertex cover problem.

Textbook:       T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to                                 Algorithms, 2^nd Edition, MIT Press, 2001 ISBN: 0-262-530-910.

Reference:     G. Brassard and P. Bratley, Fundamentals of Algorithmics, Prentice-                                    Hall, 1996 ISBN: 0-13-335068-1.

Prerequisites: Good programming concepts (any language), Data structures and their                           properties, mathematical concepts like methods of proof, algorithmic                                   complexity, recurrences, probability.

Assignments: This course deals with wide range of problem domain so sufficient                                             number of assignments from each unit and subunit should be given to the                            students to familiarize the concepts in depth.

Lab:     The motive of this course is to provide good theoretical and mathematical          background of algorithms and their analysis, however it is advisable to provide        programming assignments that aid the students learn the behavior of the             algorithms.