Skip to main content
You are not a member of this wiki.
Join now
Dismiss
guest
Help

Sign In
Analysis of Algorithms I, Section 1 and H1, Spring 2017
Home
guest

Help

Sign In
Analysis of Algorithms I, Section 1 and H1, Spring 2017
Wiki Home
Recent Changes
Pages and Files
Members
Favorites
20
All Pages
20
Home
Homework
Lectures
Add
Add "All Pages"
Done
Lectures
Edit
0
86
…
0
Tags
No tags
Notify
RSS
Backlinks
Source
Print
Export (PDF)
Date
Topic
Readings
Notes
Jan 18
Introduction, Class overview,
RAM model, Worstcase complexity，
Insertion sort, and Asymptotics
Chapter 1, Section 2.1, 2.2 and 3.1
Note 1
Jan 23
Asymptotics, Induction,
Divide and conquer, Merge sort，
Recurrence, Recursion tree
Section 2.3 and 3.2
Sort with dance
Sorting algorithms in six minutes
Note 2
Jan 25
Binary search, Powering, Matrix
multiplication, Strassen's algorithm
Master theorem
Section 4.2, 4.3 and 4.5
Note 3
Jan 30
Randomized algorithms
Quicksort and its analysis
Chapter 5, Section 7.1 and 7.2
Appendix C for basics of probability
Note 4
Feb 1
Randomized Quicksort
Sectioin 7.3 and 7.4
Note 5
Feb 6
Selection in linear time, and
Lower bound on comparison sorts
Section 9.2, 9.3 and 8.1
Note 6
Feb 8
Counting sort and Radix sort
Hash tables and hash functions
Section 8.2 and 8.3
Section 11.1 and 11.2
Note 7.1
Note 7.2
Feb 13
Universal hashing
Section 11.3.3
Note 8
Feb 15
Perfect hashing and
Binary search trees
Section 11.5 and Chapter 12
Note 9.1
Note 9.2
Feb 20
RedBlack trees
Chapter 13
Note 10
Feb 22
Augmenting data structures
Order statistics, Interval trees
Chapter 14
Note 11
Feb 27
Greedy algorithms
Activity selection
Section 16.1 and 16.2
Note 12
Mar 1
Greedy: Huffman trees,
Dynamic programming: Rod cutting
Section 16.3 and 15.1
Note 13
Mar 6
Dynamic programming: Longest
common subsequence
Section 15.3 and 15.4
See Note 13
Mar 8
Midterm in class
FAY 313 and MUDD 1127
Spring Recess, Mar 13  Mar 17
Mar 20
Dynamic programming: Optimal
binary search tree; midterm problems
Section 15.5
Note 14
Mar 22
Amortized analysis
Chapter 17
Note 15
Mar 27
Graphs and Breadthfirst search
Section 22.1 and 22.2
Note 16
Mar 29
Breadthfirst search and its correctness
Section 22.2
See Note 16
Apr 3
Depthfirst search and Topological sort
Section 22.3 and 22.4
Note 17
Apr 5
Strongly connected components
Minimum spanning tree: the generic method
Section 22.5 and Section 23.1
Note 18
Apr 10
Minimum spanning trees:
Kruskal and Prim
Chapter 23 and Section 21.12
Note 19
Apr 12
Singlesource shortest path:
BellmanFord and Dijkstra
Chapter 24
Note 20
Apr 17
Allpairs shortest paths
Chapter 25
Note 21
Apr 19
Maximum Flow: FordFulkerson
Section 26.1 and 26.2
Note 22
Apr 24
EdmondsKarp, and
Maximum bipartite matching
Section 26.2 and 26.3
Note 23
Apr 26
NPcompleteness
Chapter 34
Note 24
May 1
NPcompleteness
Chapter 34
Note 25
Final exam
7:1010pm on Monday May 8
Javascript Required
You need to enable Javascript in your browser to edit pages.
help on how to format text
Turn off "Getting Started"
Home
...
Loading...
Date
Topic
Readings
Notes
RAM model, Worstcase complexity，
Insertion sort, and Asymptotics
Divide and conquer, Merge sort，
Recurrence, Recursion tree
Sort with dance
Sorting algorithms in six minutes
multiplication, Strassen's algorithm
Master theorem
Quicksort and its analysis
Appendix C for basics of probability
Lower bound on comparison sorts
Hash tables and hash functions
Section 11.1 and 11.2
Note 7.2
Binary search trees
Note 9.2
Order statistics, Interval trees
Activity selection
Dynamic programming: Rod cutting
common subsequence
binary search tree; midterm problems
Kruskal and Prim
BellmanFord and Dijkstra
Maximum bipartite matching