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

Cryptographic Algorithms: RSA (6 pages)

applications of number theory to cryptography

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 Pencast on bit complexity Pencast on integer multiplication
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)	Red-Black Trees The Union-Find Data Structure
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	Universal Hashing and Randomized Algorithms
12	Modular Arithmetic Algorithms (Sections 1.2-1.4; 19 pages) Primality Testing (5 pages)	brief introduction into modular arithmetic
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

Spam prevention powered by Akismet

This work by Sathish Gopalakrishnan is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Canada.