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.
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, PrenticeHall,
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.
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.
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, PrenticeHall,
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.
Comments
Post a Comment