Course Objectives:
To provide an introduction to formalisms to understand, analyze and denote time complexities of algorithms
To introduce the different algorithmic approaches for problem solving through numerous example problems
To provide some theoretical grounding in terms of finding the lower bounds of algorithms and the NP-completeness
Course Outcomes:
Describe asymptotic notation used for denoting performance of algorithms
Analyze the performance of a given algorithm and denote its time complexity using the asymptotic notation for recursive and non-recursive algorithms
List and describe various algorithmic approaches
Solve problems using divide and conquer, greedy, dynamic programming, backtracking and branch and bound algorithmic approaches
Apply graph search algorithms to real world problems
Demonstrate an understanding of NP- Completeness theory and lower bound theory
UNIT I Introduction:
Algorithm Definition, Algorithm Specification, performance Analysis, Performance measurement, Asymptotic notation, Randomized Algorithms. Sets & Disjoint set union: introduction, union and find operations. Basic Traversal & Search Techniques: Techniques for Graphs, connected components and Spanning Trees, Bi-connected components and DFS.
UNIT II Divide and Conquer:
General Method, Defective chessboard, Binary Search, finding the maximum and minimum, Merge sort, Quick sort. The Greedy Method: The general Method, container loading, knapsack problem, Job sequencing with deadlines, minimum-cost spanning Trees.
UNIT III Dynamic Programming:
The general method, multistage graphs, All pairs-shortest paths, singlesource shortest paths: general weights, optimal Binary search trees, 0/1 knapsack, reliability Design, The traveling salesperson problem, matrix chain multiplication. UNIT IV Backtracking: The General Method, The 8-Queens problem, sum of subsets, Graph coloring, Hamiltonian cycles, knapsack problem. Branch and Bound: FIFO Branch-and-Bound, LC Branch-and-Bound, 0/1 Knapsack problem, Traveling salesperson problem. UNIT V NP-Hard and NP-Complete problems: Basic concepts, Cook’s Theorem. String Matching: Introduction, String Matching-Meaning and Application, NaÏve String Matching Algorithm, Rabin-Karp Algorithm, Knuth-Morris-Pratt Automata, Tries, Suffix Tree
UNIT IV Backtracking:
The General Method, The 8-Queens problem, sum of subsets, Graph coloring, Hamiltonian cycles, knapsack problem. Branch and Bound: FIFO Branch-and-Bound, LC Branch-and-Bound, 0/1 Knapsack problem, Traveling salesperson problem.
UNIT V NP-Hard and NP-Complete problems:
Basic concepts, Cook’s Theorem. String Matching: Introduction, String Matching-Meaning and Application, NaÏve String Matching Algorithm, Rabin-Karp Algorithm, Knuth-Morris-Pratt Automata, Tries, Suffix Tree.