Notion of Algorithm, Review of Asymptotic Notations, Mathematical Analysis of Non-Recursive and Recursive Algorithms Brute Force Approaches: Introduction, Selection Sort and Bubble Sort, Sequential Search and Brute Force String Matching.
Divide and Conquer: General Method, Defective Chess Board, Binary Search, Merge Sort, Quick Sort and its performance.
The General Method, Knapsack Problem, Job Sequencing with Deadlines, Minimum-Cost Spanning Trees: Prim’s Algorithm, Kruskal’s Algorithm; Single Source Shortest Paths.
The General Method, Warshall’s Algorithm, Floyd’s Algorithm for the All-Pairs Shortest Paths Problem, Single-Source Shortest Paths: General Weights, 0/1 Knapsack, The Traveling Salesperson problem.
Decrease-and-Conquer Approaches: Introduction, Insertion Sort, Depth First Search and Breadth First Search, Topological Sorting Space-Time Tradeoffs: Introduction, Sorting by Counting, Input Enhancement in String Matching.
Lower-Bound Arguments, Decision Trees, P, NP, and NP-Complete Problems, Challenges of Numerical Algorithms.
Backtracking: n - Queens problem, Hamiltonian Circuit Problem, Subset – Sum Problem. Branch-and-Bound: Assignment Problem, Knapsack Problem, Traveling Salesperson Problem. Approximation Algorithms for NP-Hard Problems – Traveling Salesperson Problem, Knapsack Problem
Introduction, Computational Model, Parallel Algorithms for Prefix Computation, List Ranking, and Graph Problems,