Design and Analysis of Algorithms
Deep Understanding: 90 hours
This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms. Representative problems and their algorithms are discussed for each topic.
Analyze the asymptotic performance of algorithms,Demonstrate familiarity with major algorithm design techniques,Apply important algorithmic design paradigms and methods of analysis,Solve simple to moderately difficult algorithmic problems arising in applications,Demonstrate the hardness of simple NP-complete problems
Course Contents
Algorithm and its properties, RAM model, Time and Space Complexity, detailed analysis of algorithms (e.g., factorial algorithm), Concept of Aggregate Analysis, Asymptotic Notations: Big-O, Big-Ω and Big-Ө Notations, Geometrical Interpretation and Examples, Recurrences: Recursive Algorithms and Recurrence Relations, Solving Recurrences (Recursion Tree Method, Substitution Method, Application of Masters Theorem)
Basic Algorithms: GCD, Fibonacci Number and analysis of their time and space complexity, Searching Algorithms: Sequential Search and its analysis, Sorting Algorithms: Bubble, Selection, and Insertion Sort and their analysis
Searching Algorithms: Binary Search, Min-Max Finding and their Analysis, Sorting Algorithms: Merge Sort and Analysis, Quick Sort and Analysis (Best, Worst and Average Case), Heap Sort (Heapify, Build Heap, Heap Sort Algorithms and Analysis), Randomized Quick Sort and Analysis, Order Statistics: Selection in Expected Linear Time, Selection in Worst Case Linear Time and their Analysis
Optimization Problems and Optimal Solution, Introduction to Greedy Algorithms, Elements of Greedy Strategy, Greedy Algorithms: Fractional Knapsack, Job Sequencing with Deadlines, Kruskal’s Algorithm, Prim’s Algorithm, Dijkstra’s Algorithm and their Analysis, Huffman Coding: Purpose, Prefix Codes, Huffman Coding Algorithm and Analysis
Greedy Algorithms vs Dynamic Programming, Recursion vs Dynamic Programming, Elements of DP Strategy, DP Algorithms: Matrix Chain Multiplication, String Editing, Zero-One Knapsack Problem, Floyd Warshall Algorithm, Travelling Salesman Problem and their Analysis, Memoization Strategy, Dynamic Programming vs Memoization
Concept of Backtracking, Recursion vs Backtracking, Backtracking Algorithms: Subset-sum Problem, Zero-One Knapsack Problem, N-Queen Problem and their Analysis
Number Theoretic Notations, Euclid’s and Extended Euclid’s Algorithms and their Analysis, Solving Modular Linear Equations, Chinese Remainder Theorem, Primality Testing: Miller-Rabin Randomized Primality Test and their Analysis
Tractable and Intractable Problems, Concept of Polynomial Time and Super Polynomial Time Complexity, Complexity Classes: P, NP, NP-Hard and NP-Complete, NP Complete Problems, NP Completeness and Reducibility, Cook’s Theorem, Proofs of NP Completeness (CNF-SAT, Vertex Cover and Subset Sum), Approximation Algorithms: Concept, Vertex Cover Problem, Subset Sum Problem
Laboratory Works
Implement comparison sorting algorithms and perform empirical analysis,Implement divide-and-conquer sorting algorithms and perform empirical analysis,Implement algorithms for order statistics and perform empirical analysis,Implement algorithms using Greedy, DP and Backtracking paradigms,Implement NP-complete problems and realize their computational hardness