Slides, links, material:
Note everything is developed on the board in class; these are supporting written slides (and extra links
to animations or optional papers) that cover the same scope of material.
- Jan 16: Introduction to algorithms: Algorithms1aSlides_spring18.pdf
- Jan 18: Introduction to algorithms: Algorithms1bSlides_spring18.pdf
- Jan 23: Loop invariants in Jan 18 slides; Started intro to complexity classes and growth of functions, including big Oh, Omega, Theta: Algorithms2aSlides_spring18.pdf;
Website on complexity classes beyond scope of class: ComplexityZoo
- Jan 25: Continued intro to complexity classes and
growth of functions, including big Oh, Omega, Theta. Slides above and
also: Algorithms2bSlides_spring18.pdf Started Divide and Conquer part 1 up to and including Max Subarray problem: Algorithms3aSlidesClass_spring18.pdf
- Jan 30: Continued Divide and Conquer part 1 and 2.
Divide and Conquer part 2: Algorithms3bSlides_class_spring18.pdf
- Feb 1: Continued Divide and Conquer part 2 (slides above), and part 3:
Algorithms3c_2018.pdf
- Feb 6: Continued divide and Conquer part 3 (slides 3c above).
- Feb 8: Randomized algorithms 1, Probability review: Algorithms4aSlides_spring18.pdf
- Feb 13: Randomized algorithms 2, and Start of Quicksort:
Algorithms4b_spring18.pdf
Partition algorithm for quicksort animation by Burt Rosenberg: Partition
- Feb 15: Randomized algorithms part 3, proof of Quicksort: Algorithms4c_spring18.pdf
We also talked about optimal stopping algorithms for hiring and other applications in the book:
Algorithms to Live By: The Computer Science of Human Decisions (Brian Christian, Tom Griffiths).
- Feb 20: Finished Randomized algorithms with brief mention of Order Statistics (slides above). Review/Intro of data structures; and hash functions part 1:
Algorithms5aSlides_spring18.pdf
- Feb 22: Hash functions part 1:
Algorithms5b_spring18.pdf
- Feb 27: Hash functions part 2:
Algorithms5c_spring18.pdf
- March 1: Review for midterm.
- March 6: Midterm in class.
- March 8: Binary Search trees:
Algorithms6aClass_spring18.pdf
(material not on midterm)
- March 20: Midterm in class.
- March 22: Red Black Trees part 1:
Algorithms6b_RedBlackTree_spring18.pdf
(material not on midterm)
- March 30: Dynamic programming part 1: Fibonacci and (only starting) Longest Common Subsequence:
DP1_2018.pdf
(notes up to the intuition of Longest Common Subsequence).
Fibonacci animation website by David Galles.
Fibonacci compute time by Burt Rosenberg.
LCS animation website by David Galles.
Cipher Thomas Jefferson.
- April 5: Completed slides above; and Dynamic Programming part 2:
Rod cutting problem:
Algorithms7b_DynamicP_spring18.pdf
- April 10: Completed Dynamic Programming part 2.
- April 12:
Greedy algorithms part 1: Activity Selection problem:
Algorithms8a_greedy_spring18.pdf
- April 17: Greedy algorithms part 2 and Huffman coding:
Algorithms8b_greedy_spring18.pdf
Compression intro slides
- April 19: Graph algorithms: BFS (briefly), DFS (in more detail).
friendsArticle2018.pdf
Networks, Crowds, and Markets book. By David Easley and Jon Kleinberg
BFS_animation website by David Galles.
DFS_animation website by David Galles.
AlgorithmsGraphsClass1_spring18.pdf
AlgorithmsGraphsClass2_spring18.pdf
- April 24: Graph algorithms part 2: Topological sorting,
Strongly Connected Components:
AlgorithmsGraphsClass3_spring18.pdf
Broder paper on web connectivity
Topics covered:
- Introduction to algorithms
- Sorting as example
- Correctness
- Growth of functions and Big-Oh notation
- Divide and conquer and recursion equations
- Randomized algorithms
- Hashing
- Trees and Red Black Trees
- Algorithmic paradigms: Dynamic programming, Greedy algorithms
- Graph Algorithms
|