Introduction: What is an Algorithm? (T2:1.1), Algorithm Specification (T2:1.2),Analysis Framework (T1:2.1), Performance Analysis: Space complexity, Timecomplexity (T2:1.3). Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω),Theta notation (Θ), and Little-oh notation (o), Mathematical analysis of Non-Recursiveand recursive Algorithms with Examples (T1:2.2, 2.3, 2.4). Important Problem Types:Sorting, Searching, String processing, Graph Problems, Combinatorial Problems.Fundamental Data Structures: Stacks, Queues, Graphs, Trees, Sets and Dictionaries.(T1:1.3,1.4)
Divide and Conquer: General method, Binary search, Recurrence equation for divide and conquer, Finding the maximum and minimum (T2:3.1, 3.3, 3.4), Merge sort, Quick sort (T1:4.1, 4.2), Strassen’s matrix multiplication (T2:3.8), Advantages and Disadvantages of divide and conquer. Decrease and Conquer Approach: TopologicalSort. (T1:5.3)
Greedy Method: General method, Coin Change Problem, Knapsack Problem, Job sequencing with deadlines (T2:4.1, 4.3, 4.5). Minimum cost spanning trees: Prim’s Algorithm, Kruskal’s Algorithm (T1:9.1, 9.2). Single source shortest paths: Dijkstra\'s Algorithm (T1:9.3). Optimal Tree problem: Huffman Trees and Codes (T1:9.4).Transform and Conquer Approach: Heaps and Heap Sort (T1:6.4).
Dynamic Programming: General method with Examples, Multistage Graphs (T2:5.1, 5.2). Transitive Closure: Warshall’s Algorithm, All Pairs Shortest Paths: Floyd\'s Algorithm, Optimal Binary Search Trees, Knapsack problem ((T1:8.2, 8.3, 8.4), Bellman-Ford Algorithm (T2:5.4), Travelling Sales Person problem (T2:5.9), Reliabilitydesign (T2:5.8).
Backtracking: General method (T2:7.1), N-Queens problem (T1:12.1), Sum of subsetsproblem (T1:12.1), Graph coloring (T2:7.4), Hamiltonian cycles (T2:7.5). Branch andBound: Assignment Problem, Travelling Sales Person problem (T1:12.2), 0/1Knapsack problem (T2:8.2, T1:12.2): LC Branch and Bound solution (T2:8.2), FIFO Branch and Bound solution (T2:8.2). NP-Complete and NP-Hard problems: Basic concepts, on-deterministic algorithms, P, NP, NP-Complete, and NP-Hard classes(T2:11.1).