CSC-303: Design and Analysis of Algorithms

 Course Title: Design and Analysis of Algorithms

Course no: CSC-303                                                              Full Marks: 80+20
Credit hours: 3                                                                 Pass Marks: 32+8
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 pertaining 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, 2nd 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.