| 1 | Introduction
o What is an algorithm?
o Notation for programs
o Proof techniques
o Basics review: Sets - Functions - Limits - Simple series |
| 2 | Fundamentals
o Instances and problems - Elementary operations.
o Efficiency
o Average and worst-case analysis
o Examples |
| 3 | Asymptotic notation
o Introduction
o A notation for "the order of"
o The omega notation
o The theta notation
o The conditional asymptotic notation |
| 4 | Analysis of algorithms
o Analyzing control structures
o Using a barometer
o Amortized analysis
o Solving recurrences |
| 5 | Data structures
o Arrays, stacks and queues
o Records and pointers
o Lists, graphs, trees and associative tables
o Heaps
o Disjoint set structures |
| 6 | Greedy algorithms
o Making change
o General characteristics of Greedy algorithms
o Graphs MST - Kruskal's and Prims's algorithms
o Graphs: shortest paths
o Knapsack problem
o Scheduling |
| 7 | Divide - and - Conquer
o Multiplying large integers
o Binary search
o Sorting by: merging and quicksort
o Finding the median
o Matrix multiplication
o Exponentiation
o Quick look at cryptography |
| 8 | Midterm Exam |
| 9 | Dynamic programming
o Making change |
| 10 | o Principles of optimality
o The knapsack problem |
| 11 | o Shortest paths - Floyd's algorithm
o Chained matrix multiplication |
| 12 | Introduction to probabilistic algorithms - Parallel algorithms |
| 13 | Introduction to computational complexity |
| 14 | Introduction to computational complexity |
