Course Description:
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. For each topic, beside in-depth coverage, one or more representative problems and their algorithms shall be discussed.
Course Objectives:
- Analyze the asymptotic performance of algorithms.
- Demonstrate a 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.
- Able to demonstrate the hardness of simple NP-complete problems
Course Contents:
Unit 1: Foundations of Algorithm Analysis (4 Hrs.)
Algorithms and its properties
Definition of algorithms and brief explanation about the basic properties of algorithms
RAM model
Explanation of the RAM model and its use for algorithm analysis.
Time and Space Complexity
Concepts of Time and Space Complexity with best case, worst case , average case
Detailed Analysis of algorithms
Detailed Analysis with examples like factorial of an integer using RAM model.
Concept of Aggregate Analysis
Definition, brief explanation of Aggregate Analysis with example.
Asymptotic Notations:
Concept, definition of Asymptotic notation: Big-O, Big-Ω and Big-Ө Notations and their Geometrical Interpretation and Examples.
Recursive Algorithms
Brief overview of recursion and , Recursive Algorithms
Recurrence Relations
Definitions of Recurrence Relations with example. Uses of Recurrence Relations in Algorithm Analysis.
Solving Recurrences
Recursion Tree Method, Substitution Method, Application of Masters Theorem for solving recurrence relations. Examples
Unit 2: Iterative Algorithms (4 Hrs.)
Basic Algorithms
Algorithm for GCD, Fibonacci Numbers and analysis of their time and space complexity.
Searching Algorithms:
Sequential Search and its analysis
Sorting Algorithms:
Description of Bubble Sort, Selection Sort and Insertion Sort with their complexity analysis.
Unit 3: Divide and Conquer Algorithms (8 Hrs.)
Concepts
Concept and applications of divide and conquer approach in algorithm design.
Searching Algorithms:
Concept and detail description of Binary Search algorithms and its analysis, Finding Minimum and maximum element in a list of items(Min-Max algorithm) and their analysis.
Sorting Algorithms:
Merge Sort algorithm, examples and its time and space complexity
Concepts of partitioning, Quick Sort algorithm and its analysis ( Best Case, Worst Case and Average Case ). Examples, Randomized Quick Sort and its analysis.
Concept of Heap Data Structures(max , min). Heap Sort Algorithm ( with Build Heap and Heapify ) and its complexity analysis.
Order Statistics
Concepts of Order statistics, Median order. Brute-force approach for selection
Selection in Expected Linear Time and its analysis.
Selection in Worst Case Linear Time algorithm and its complexity analysis.
Unit 4: Greedy Algorithms (6 Hrs.)
Introduction to Greedy Approach
Concept of Optimization Problems and Optimal solution. Introduction of Greedy Strategy for algorithm design. Elements of Greedy Strategy(Greedy Choice Property, Optimal Substructure Property)
Greed Algorithms:
Concept of Knapsak problem, Algorithm for Fractional Knapsack Problem examples and analysis of its complexity.
Concept of Job Sequencing Problem with deadline. Algorithm for Job Sequencing with deadline and its time complexity.
Kruskal’s and Prim’s algorithms for Minimum Spanning Tree, their examples and complexity analysis. Correctness .Dijkastra Shortest Path Algorithms , example and its time complexity.
Huffman Coding:
Purpose of Huffman Coding, Prefix Codes, Huffman Tree, Huffman Coding Algorithm, example and its Analysis.
Unit 5: Dynamic Programming (8 Hrs.)
Introduction
Concepts of Dynamic Programming approach for algorithm design, Greedy Algorithm vs Dynamic Programming, Recursion vs Dynamic Programming. Elements of Dynamic Programming Approach
D P Algorithms:
Concept of Matrix Chain Multiplication, its Algorithm ,examples and complexity analysis
String Editing Algorithm(edit distance problem with insertion, deletion, replace operation) and its complexity analysis
0-1 Knapsack problem and its complexity analysis.
Floyd Warshall Algorithms for all pair shortest path problem, example and its complexity analysis.
Travelling Salesman Problem and its analysis
Memoization Strategy
Concept of Memoization. Dynamic Programming vs Memoization.
Unit 6: Backtracking (5 Hrs.)
Introduction
Concept of Backtracking Approach. Recursion vs Backtracking
Backtracking Algorithms
Concept of Subset Sum, Algorithm for Subset-Sum, its example and Complexity Analysis.
Zero-One Knapsack Problem, algorithm with backtracking approach and its analysis.
N-Queen Problem and their Analysis
Unit 7: Number Theoretic Algorithms (5 Hrs.)
Introduction
Concept of Number Theoretic Notation.
Concept of Modular Linear Equations. Chinese Remainder Theorem.
Solving Modular Linear Equations
Euclid’s and Extended Euclid’s Algorithms for solving Modular Linear Equations.
Primility Testing
Miller-Rabin Randomized Primility Test and Analysis
Unit 8: NP Completeness (5 Hrs.)
Tractable and Intractable Problems, Complexity Classes
Concept of tractable and intractable problems, Polynomial Time and Super Polynomial Time complexity.
P , NP , NP Complete, NP Hard with Examples
NP Complete Problems
NP Completeness and Problem Reducibility, Concept of Cooks Theorem(Without Proof). Proof of NP Completeness( CNF-SAT, Vertex Cover and Subset-Sum Problem)
Approximation Algorithms
Concept and Application, Vertex Cover Problem, Subset Sum Problem
Laboratory Works:
This course can be learnt in effective way only if we give focus is given in practical aspects of algorithms and techniques discussed in class. Therefore student should be able to implement the algorithms and analyze their behavior.
For the laboratory work, students should implement the following algorithms in C/ C++ and perform their analysis for time and space complexity.
- Basic iterative algorithms GCD algorithm, Fibonacci Sequences, Sequential and Binary Search.
- Basic iterative sorting algorithms: Bubble Sort, selection Sort, Insertion Sort.
- Binary Search with Divide and conquer approach.
- Merge Sort, Heap sort, Quick Sort, Randomized Quick Sort.
- Selection Problem with divide and Conquer approach
- Fractional Knapsack Problem, Job sequencing with deadline, Kruskal’s algorithm, Prims algorithm, Dijkstra’s Algorithm
- Implement the dynamic programming algorithms.
- Algorithms using Backtracking approach.
- Implement approximation Algorithm.
Recommended Books:
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to algorithms”, Third Edition.. The MIT Press, 2009.
- Ellis Horowitz, SartajSahni, SanguthevarRajasekiaran, “Computer Algorithms”, Second Edition, Silicon Press, 2007.
- Kleinberg, Jon, and Eva Tardos, “ Algorithm Design” , Addison-Wesley, First Edition, 2005