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 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 RAM model, Algorithm Analysis: worst, best and average cases, space and time complexities. Mathematical background: asymptotic behavior: big-O, big- , big- , solving recurrences: Iterative, recursion-tree, substitution technique, Masters Theorem (without proof)
1.2 Data Structures Brief overview: linear data structures, hierarchical data structures, data structures for representing graphs and their properties. Search structures: heaps, BST, hash tables.
Unit 2. 17 Hrs.
2.1 Divide and Conquer: Concepts, applications, sorting problems (quick, merge, heap), binary search , randomized quick sort, median finding problem and general order statistics (Finding minimum and maximum, selection in nonlinear time, selection in expected linear time and worst case linear time), strassens matrix multiplications.
2.2 Greedy Paradigm: Concepts, applications, fractional Knapsack problem, job sequencing, Huffman codes.
2.3 Dynamic Programming: Concepts, applications, 0/1 Knapsack problem, longest common subsequence, matrix chain multiplications.
Unit 3 18 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(point, line, line segment, vertex, ear, mouth, left and right turn, diagonal) Determining intersection of line segments, polygon triangulation (Diagnolisation), Convex hull computation (Gram's Scan Algorithm).
3.3 NP Completeness: Introduction, class P and NP, cooks theorem (brief overview), NP complete problems: vertex cover problem, solving vertex cover problem using approximation algorithms
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.
Horowitz Ellis Sahani S., Rajasekaran S. Computer Algorithms/C++
Second Edition. University Press
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.
Thank you very much for the post. After finding your blog on googling, I was extremely happy. Though the information presented here might appear just a presentation formal document, nobody knows when something is utterly needed. I was looking for the text book applied in TU and your post did the work for me. Many many thanks for the good work.
ReplyDelete