Algorithms and Complexity

Paper Code: 
CSC-144(D)
Credits: 
04
Max. Marks: 
100.00
Objective: 

This course will enable the students
1. To analyze the complexities of various problems in different domains.
2. To apply the algorithms and design techniques to solve problems.
3. To prove the correctness and analyze the running time of the basic algorithms for those classic problems in various domains.

12.00
Unit I: 

Introduction: Algorithm definition and specification, Design of Algorithms, and Complexity of Algorithms, Growth of function, Recurrences, Performance analysis.

Asymptotic Notations: Asymptotic analysis (best, worst, average cases) of time and space, upper and lower bounds.

Basic concepts of complexity classes: P, NP, NP-hard, NP-complete.

 

12.00
Unit II: 

Divide and Conquer approach: General Method, Quick Sort, Merge Sort, Strassen’s matrix multiplication, Convex hull algorithms.

Greedy Method: General Method, Knapsack Problem, Tree Vertex Splitting, Job Sequencing with deadlines, Minimum Cost Spanning Trees (Prim’s Algorithm and Kruskal’s Algorithm), Single Source Shortest Path(Dijkstra’s Algorithm).

Branch and bound: The Method, LIFO, FIFO, 0/1 Knapsack problem, traveling salesperson.

12.00
Unit III: 

Dynamic Programming: General method, Warshall’s and Floyd’s Algorithms, multistage graphs, all pair shortest path, Single Source shortest path, optimal binary search trees, 0/1 Knapsack, traveling salesman problem, flow shop scheduling, Single Source Shortest Path(Bellman and Ford Algorithm), Reliability Design.

Backtracking:  General Methods, 8 queens problem, n queens problem, sum of subsets, graph coloring, Hamiltonian cycles, knapsack problem.

12.00
Unit IV: 

NP Hard and NP Complete Problems: Approximation Algorithms, Pram Algorithms, Mesh Algorithms and Hypercube Algorithms.

Parallel models: Basic concepts, performance Measures, Parallel Algorithms: Parallel computation and complexity, Analysis of Parallel Addition, Parallel Multiplication and division.

 

12.00
Unit V: 

Computational Complexity: Models of Computation, Computability, reductions, hardness, completeness, hierarchy, relationships between complexity classes, Randomized computation and complexity; Logical characterizations, incompleteness, Approximability, Circuit complexity, lower bounds, Parallel computation and complexity, Counting Problems, Probabilistically checkable proofs, Communication complexity, Quantum computation.

 

ESSENTIAL READINGS: 
  1. Anany Levitin, “Introduction to the Design and Analysis of Algorithm”, Pearson Education Asia, 2003.
  1. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, “Introduction to Algorithms”, PHI Pvt. Ltd., 2001
  1. Sara Baase and Allen Van Gelder, “Computer Algorithms, Introduction to Design and    Analysis”, Pearson Education Asia, 2003.
  1. A.V.Aho, J.E. Hopcroft and J.D.Ullman, “The Design and Analysis of Computer Algorithms”, Pearson Education Asia, 2003.
  1. Ellis Horowitz, Sarataj Sahni, S. Rajsekaran, ”Fundamentals of Computer Algorithms”, University press.
  1. Mark Allen Weiss, “Data Structure & Algorithm Analysis in C++”, Third Edition,     Pearson Education.
  1. Y. Langsam, M.J. Angestein and A.M. Tanenbaum, “Data Structures Using C and C++”, Prentice Hall of India.

 

Academic Year: 
2021-22
  • Printer-friendly version