Introduction: What is an Algorithm?, Fundamentals of Algorithmic Problem Solving, Important Problem Types, Fundamental Data Structures
Fundamentals of the Analysis of Algorithm Efficiency: Analysis Framework, Asymptotic Notations and Basic Efficiency Classes, Mathematical Analysis of Nonrecursive and Recursive Algorithms, Example – Fibonacci Numbers
Brute Force: Selection Sort and Bubble Sort, Sequential Search and Brute-Force String Matching, Exhaustive Search Divide and Conquer: Mergesort, Quicksort, Binary Search
Divide and Conquer contd.: Binary tree traversals and related properties, Multiplication of large integers and Stressen’s Matrix Multiplication. Decrease and Conquer: Insertion Sort, Depth First Search, Breadth First Search, Topological Sorting, Algorithms for Generating Combinatorial Objects
Transform and Conquer: Presorting, Balanced Search Trees, Heaps and Heapsort, Problem Reduction Space and Time Tradeoffs: Sorting by Counting, Input Enhancement in String Matching
Space and Time Tradeoff contd.: Hashing Dynamic Programming: Computing a Binomial Coefficient, Warshall’s and Floyd’s Algorithms, The Knapsack Problem and Memory Functions
Greedy Technique: Prim’s Algorithm,Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffman Trees Limitations of Algorithm Power: Lower-Bound Arguments, Decision Trees
Limitations of Algorithm Power contd.: P, NP and NP-Complete Problems Coping with the Limitations of Algorithm Power: Backtracking, Branch-and-Bound, Approximation Algorithms for NP-Hard Problems