# Readings and slides

You can find links to the PDF version of the course slide sets here. I strongly recommend that you not print the slides (save paper!).

11

 Week Readings Slides 0 Peter Alfeld’s Guide to Understanding Mathematics Course policies on academic integrity Sets, Functions and Relations (pages 1-12) Basic Proof Techniques (pages 13-15) Propositional Logic and Inference (pages 95-100) Proofs by Induction (Sections 1-6; 12 pages) Some notes on propositional logic and inference techniques A refresher on basic set theory Relations and functions Propositional logic (self study: propositions, rules of inference) Predicate logic & proof techniques (self study: predicates and quantifiers, methods of proof) Mathematical induction (self study: principle of mathematical induction, elementary inductive proofs) 1 Prologue for Algorithms (Chapter 0; 10 pages) Simple Arithmetic Algorithms (Sections 1.1-1.5; 33 pages) Fibonacci Numbers (Section 0.2; 4 pages) What is an algorithm? The Big-Oh notation Notes on Fibonacci Numbers Course Introduction (logistics and course overview) Stable Marriages (The Stable Marriage Problem, the traditional marriage algorithm — Gale & Shapley — and its properties) Algorithms for elementary arithmetic 2 Refresher: Basic Data Structures (lists, stacks, queues, binary trees and binary search trees) Analysis of Insertion Sort (4 pages) Big-O notation(Section 0.3; 2 pages) Examples, courtesy Charles A. Cusack Asymptotic growth of functions (Asymptotic complexity measures such as big-O, Theta, little o; insertion sort as an example; useful mathematical identities) More on algorithmic analysis (Illustrating the growth of functions; common running times) 3 Pre-reading: BinarySearch and QuickSort Divide and Conquer (Chapter 2; 28 pages) This chapter contains a discussion of problems different from lectures. Focus on mastering the principle. FFTs are useful but you could skip that material initially. Solving recurrences Divide & Conquer (Counting inversions, closest pair of points, integer multiplication, matrix multiplication) 4 Greedy Algorithms (Chapter 5; 28 pages) Some examples may differ from those in lecture. Greedy Algorithms (Section 7.4: Huffman Codes) Jeff Erickson’s notes provide better coverage of Huffman compression. An efficient implementation requires good data structures, an issue that we will attend to later. Greedy Algorithms (Scheduling to minimize lateness, interval scheduling, interval partitioning, optimal caching, …) 5-6 Dynamic Programming (Chapter 6; 22 pages) Some examples may differ from those in lecture. More examples Dynamic Programming (Weighted interval scheduling, knapsack, shortest paths and more) 7 Graphs (Chapter 3; 16 pages) Definitions Simple Proofs with Graphs Inductive Proofs on Trees (Section 11; 3 pages) More Proofs with Graphs (6 pages) Graphs – I (Definitions, trees, planar graphs, dual graphs, graph colouring, representations of graphs) Graphs – II (breadth first search, directed acyclic graphs and topological sorting) 8-9 Paths in Graphs (Chapter 4; 17 pages) Minimal Spanning Trees (Sections 20.1-20.3, 20.6; 6 pages) Graphs – III (greedy algorithms on graphs) Graphs – IV (matchings in graphs, Hall’s Theorem) 10 Red-Black Trees (or how to keep a tree height-balanced) Data Structures for Disjoint Sets (Sections 16.1-16.3; 5 pages) 11 Universal Hashing (Section 1.5; 4 pages) Hashing (9 pages) Applications of Hashing (3 pages) (background) Introduction to Probability (background) Random Variables and Linearity of Expectation 12 Modular Arithmetic Algorithms (Sections 1.2-1.4; 19 pages) Primality Testing (5 pages) 13 An Introduction to Linear Programming (Section 7.1; 11 pages) Linear Programming (8 pages) 14 NP-completeness (Wikipedia entry) NP-complete Problems (Sections 8.1-8.2; 15 pages) Approximation Algorithms