| 1 |
INTRODUCTION |
Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem Types –
Fundamentals of the Analysis of Algorithmic Efficiency –Asymptotic Notations and their properties.
Analysis Framework – Empirical analysis - Mathematical analysis for Recursive and Non-recursive
algorithms - Visualization |
| 2 |
BRUTE FORCE AND DIVIDE-AND-CONQUER |
Brute Force – Computing an
– String Matching - Closest-Pair and Convex-Hull Problems - Exhaustive
Search - Travelling Salesman Problem - Knapsack Problem - Assignment problem.
Divide and Conquer Methodology – Binary Search – Merge sort – Quick sort – Heap Sort -
Multiplication of Large Integers – Closest-Pair and Convex - Hull Problems. |
| 3 |
DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE |
Dynamic programming – Principle of optimality - Coin changing problem, Computing a Binomial
Coefficient – Floyd‘s algorithm – Multi stage graph - Optimal Binary Search Trees – Knapsack
Problem and Memory functions.
Greedy Technique – Container loading problem - Prim‘s algorithm and Kruskal's Algorithm – 0/1
Knapsack problem, Optimal Merge pattern - Huffman Trees. |
| 4 |
ITERATIVE IMPROVEMENT |
The Simplex Method - The Maximum-Flow Problem – Maximum Matching in Bipartite Graphs, Stable
marriage Problem. |
| 5 |
COPING WITH THE LIMITATIONS OF ALGORITHM POWER |
Lower - Bound Arguments - P, NP NP- Complete and NP Hard Problems. Backtracking – n-Queen
problem - Hamiltonian Circuit Problem – Subset Sum Problem. Branch and Bound – LIFO Search and
FIFO search - Assignment problem – Knapsack Problem – Travelling Salesman Problem -
Approximation Algorithms for NP-Hard Problems – Travelling Salesman problem – Knapsack
problem. |