|Analysis and Design of Algorithms||Learning Schedule|
|Pre-requisites: Fundamental of C||3||0||0||3|
This course provides elementary introduction to algorithm design and analysis. It includes the topic: mathematics foundation, divided-and-conquer, dynamic programming, greedy method, NP-completeness complexity, approximation algorithm, random-ized algorithm, etc. At the end of this course student should be able to understand the concepts and skills of algorithm design, Implemental some well-known algorithms and analyze the performance of algorithms.
The objective of this course is to learn:
- Existing algorithm and develop efficient algorithms for simple computational tasks.
- Reasoning about the correctness of the algorithm
- Behaviours of algorithms and the notion of tractable and intractable problems.
At the end of the course student will be able to:
- Analyze algorithms and determine efficiency of algorithm.
- Understand advanced abstract data type (ADT), data structures and their implementations
- Design algorithms using the brute force, greedy, divide and conquer, branch and bound etc. methodologies.
- Prove problems of P, NP, or NP-Complete.
- Develop and implement learned/new algorithm using appropriate techniques to solve problems.
Unit I: Introduction
Introduction : Algorithms, Analyzing algorithms, Complexity of algorithms, Growth of functions, Performance measurements, Sorting and order Statistics – Shell sort, Quick sort, Merge sort, Heap sort, Comparison of sorting algorithms, Sorting in linear time.
Unit II: Advanced Data Structures
Advanced Data Structures: Red-Black trees, B – trees, Binomial Heaps, Fibonacci Heaps.
Unit III : Divide & Conquer and Greedy Methods
Divide and Conquer with examples such as Sorting, Matrix Multiplication, Convex hull and Searching. Greedy methods with examples Huffman Coding, Knapsack, Minimum Spanning trees – Prim’s and Kruskal’s algorithms, Single source shortest paths – Dijkstra’s and Bellman Ford algorithms.
Unit IV: Dynamic Programming
Dynamic programming with examples such as Knapsack, All pair shortest paths –Warshal’s and Floyd’s algorithms, Resource allocation problem. Backtracking, Branch and Bound with examples such as Travelling Salesman Problem, Graph Coloring, n-Queen Problem, Hamiltonian Cycles and Sum of subsets.
Algebraic computation, String Matching, Theory of NP-completeness, Approximation algorithms and Randomized algorithms.
- Thomas H. Coreman, Charles E. Leiserson and Ronald L. Rivest, “Introduction to Algorithms”, Printice Hall of India.
- RCT Lee, SS Tseng, RC Chang and YT Tsai, “Introduction to the Design and Analysis of Algorithms”, Mc Graw Hill, 2005.
- Horowitz & S Sahni, “Fundamentals of Computer Algorithms”,
- Berman, Paul,” Algorithms”, Cengage Learning.
- Aho, Hopcraft, Ullman, “The Design and Analysis of Computer Algorithms” Pearson Education, 2008.