Algorithms and Complexity Analysis

At the end of the course, students should be able to: 1. explain the use of big-O, omega, and theta notation to describe the amount of work done by an algorithm, 2. use big-O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms, 3. determine the time and space complexity of simple algorithms, 4. deduce recurrence relations that describe the time complexity of recursively defined algorithms, 5. solve elementary recurrence relations, 6. for each of the strategies (brute-force, greedy, divide-and-conquer, recursive backtracking, and dynamic programming), identify a practical example to which it would apply, 7. use pattern matching to analyse substrings, and 8. use numerical approximation to solve mathematical problems, such as finding the roots of a polynomial.

Basic algorithmic analysis. Asymptotic analysis of Upper and average complexity bounds. Standard Complexity Classes. Time and space trade-offs in analysis recursive algorithms. Algorithmic Strategies. Fundamental computing algorithms. Numerical algorithms. Sequential and Binary search algorithms. Sorting algorithms, Binary Search trees. Hash tables. Graphs and their representation.