Introduction, Fundamentals of the Analysis of Algorithm Efficiency
Notion of Algorithm, Fundamentals of Algorithmic Problem Solving, Important Problem Types, Fundamental data Structures. Analysis Framework, Asymptotic Notations and Basic efficiency classes, Mathematical analysis of Recursive and Nonrecursive algorithms.
Brute Force: Selection Sort and Bubble Sort, Sequential Search, Exhaustive search and String Matching.
Divide-and-Conquer
Mergesort, Quicksort, Binary Search, Binary tree Traversals and related properties, Multiplication of large integers.
Decrease-and-Conquer
Insertion Sort, Depth First and Breadth First Search, Topological sorting, Algorithms for Generating Combinatorial Objects: generating permutations.
Greedy Technique
Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffmann Trees.
Space and Time Tradeoffs
Sorting by Counting, Input Enhancement in String Matching, Hashing.
Dynamic Programming
Computing a binomial coefficient, Warshall’s and Floyd’s Algorithms, The Knapsack Problem and Memory Functions
Limitations of Algorithm Power
Lower-Bound Arguments, Decision Trees, P, NP and NP-Complete Problems.
Coping with Limitations of Algorithm Power
Backtracking: n-Queens problem, Hamiltonian Circuit Problem, Subset – Sum Problem. Branch-and-Bound: Assignment Problem, Knapsack Problem, Traveling Salesperson Problem.