Algorithms, computational complexity, asymptotic notations, pseudocode, greedy algorithms, easy vs. hard problems.
Introduction to Big-O notation and code analysis.
Recurrence, generating functions, inclusion-exclusion principle, divide-and-conquer, application to algorithm design.
Probability theory, computing discrete probabilities, random variables, discrete distribution functions, Bayes’ Theorem, expected values, Central Limit Theorem.
Introduction to the Hash Table and Map abstract data types.
Introduction to the Tree abstract data type.
Trees, tree traversal, spanning trees, minimum spanning trees, Huffman encoding, Prim’s and Kruskal’s algorithms.
Heapsort, Quicksort, Mergesort.
Directed and undirected graphs, representations, classification, isomorphism, connectivity, Euler and Hamilton paths, shortest paths, planarity, coloring.