UNIT - 1

 

INTRODUCTION:

Some Representative Problems, A First Problem: Stable Matching: The Problem, Designing the Algorithm, Analyzing the Algorithm, Extensions, Five Representative Problems: Interval Scheduling, Weighted Interval Scheduling, Bipartite Matching, Independent Set, Competitive Facility Location, Computational Tractability: Some Initial Attempts at Defining Efficiency, Worst-Case Running Times and Brute-Force Search, Polynomial Time as a Definition of Efficiency, Asymptotic Order of Growth: Properties of Asymptotic Growth Rates, Asymptotic Bounds for Some Common Functions, Implementing the Stable Matching Algorithm, Using Lists and Arrays: Arrays and Lists, Implementing the Stable Matching Algorithm, A Survey of Common Running Times: Linear Time, O(n log n) Time, Quadratic Time, Cubic Time, O(nk) Time, Beyond Polynomial Time, Sub linear Time.

 

 

                                                                                               UNIT - 2

 

GRAPHS & DIVIDE AND CONQUER:

Graph Connectivity and Graph Traversal, Breadth-First Search: Exploring a Connected Component, Depth-First Search, Implementing Graph Traversal Using Queues and Stacks: Implementing Breadth-First Search, Implementing Depth-First Search, An Application of Breadth-First Search: The Problem, Designing the Algorithm, Directed Acyclic Graphs and Topological Ordering: The Problem, Designing and Analyzing the Algorithm, A First Recurrence: The Merge sort Algorithm: Unrolling the Merge sort Recurrence, Counting Inversions: The Problem, Designing and Analyzing the Algorithm.

 

 

                                                                                             UNIT - 3

 

GREEDY ALGORITHMS:

Interval Scheduling: The Greedy Algorithm Stays Ahead: Designing a Greedy Algorithm, Analyzing the Algorithm, Scheduling to Minimize Lateness: An Exchange Argument: The Problem, Designing the Algorithm, Optimal Caching: A More Complex Exchange Argument: The Problem, Designing and Analyzing the Algorithm, Extensions: Caching under Real Operating Conditions, Shortest Paths in a Graph: The Problem, Designing the Algorithm, Analyzing the Algorithm, The Minimum Spanning Tree Problem: The Problem, Designing Algorithms, Analyzing the Algorithms, Huffman Codes and Data Compression: The Problem, Designing the Algorithm.

 

 

                                                                                            UNIT - 4

 

DYNAMIC PROGRAMMING:

Weighted Interval Scheduling: A Recursive Procedure: Designing a Recursive Algorithm, Subset Sums and Knapsacks: Adding a Variable: The Problem, Designing the Algorithm, Shortest Paths in a Graph: The Problem, Designing the Algorithm, The Maximum-Flow Problem and the Ford-Fulkerson Algorithm: The problem, Designing the Algorithm, Survey Design: The problem, Designing the Algorithm, Analyzing the Algorithm, Airline Scheduling: The problem, Designing the Algorithm,Analyzing the Algorithm.

 

                                                                                           UNIT - 5

 

NP AND COMPUTATIONAL INTRACTABILITY

Polynomial-Time Reductions A First Reduction: Independent Set and Vertex Cover, Reducing to a More General Case: Vertex Cover to Set Cover, NP-Complete Problems: Circuit Satisfiability: A First NP-Complete Problem, General Strategy for Proving New Problems NP-Complete, Sequencing Problems: The Traveling Salesman Problem, The Hamiltonian Cycle Problem.

 

Text Book:

1. Algorithm Design - Jon Kleinberg and Eva Tardos, Tsinghua University Press (2005)

Reference Books:

1. Anany Levitin: Introduction to The Design & Analysis of Algorithms, 2nd Edition, Pearson Education, 2007.