Department Events
Algorithms and Complexity
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.
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.
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.
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.
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.
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.
