Lectures
You can download the lectures here. We will try to upload lectures prior to their corresponding classes.
-
Lecture 1
tl;dr: Course Overview and introduction to ADT.
[slides]
Assigned Readings:
Lecture recording is on Blackboard.
-
Lecture 2
tl;dr: Mathematical review.
[slides]
Assigned Readings:
- Wikipedia on mathematical proof
- Wikipedia on proof by contradiction
- Wikipedia on mathematical induction
- Mathematical review on exponentials and logarithms, factorials, etc.
Lecture recording is on Blackboard.
In CLRS (optional textbook):
Chapter 3.3 Standard notations and common functions
-
Lecture 3
tl;dr: RAM Model and Algorithm Analysis.
[slides]
Assigned Readings:
Lecture recording is on Blackboard.
In CLRS (optional textbook):
Chapter 2.1 Insertion sort Introduce algorithm by the example of insertion sort
Chapter 2.2 analyzing algorithms introduces RAM model and gives an example of analysis of insertion sort
-
Lecture 4
tl;dr: Asymptotic Analysis.
[slides]
Assigned Readings:
Lecture recording is on Blackboard.
In CLRS (optional textbook):
Chapter 1.3 Characterizing Running Times Asymptotic analysis and Landau notations
-
Lecture 5
tl;dr: Linked List.
[slides]
Assigned Readings:
Lecture recording is on Blackboard.
In CLRS (optional textbook):
Chapter 1.2 Linked Lists
-
Lecture 6
tl;dr: Dynamic array and amortized analysis.
[slides]
Assigned Readings:
Lecture recording is on Blackboard.
In CLRS (optional textbook):
Chapter 16 Amortized analysis
-
Lecture 7
tl;dr: Tree Data Structure.
[slides]
Assigned Readings:
Lecture recording is on Blackboard.
-
Lecture 8
tl;dr: Binary Search Tree.
[slides]
Assigned Readings:
Lecture recording is on Blackboard.
Extended Readings
AVL tree is a typical data structure for self-balancing binary search tree. In the next lecture we will disucuess red-black tree which is usually more frequently used because of overall lower balancing cost.
-
Lecture 9
tl;dr: Red Black Tree.
[slides]
Assigned Readings:
Lecture recording is on Blackboard.
Extended Contents There are huge numbers of tree structures for searching. Due to the limited time in class, we cannot go over them.
Trie, or prefix tree, is usually used to store string.
-
Lecture 10
tl;dr: Priority array and binary heap.
[slides] [Summary for midterm]
Assigned Readings:
Lecture recording is on Blackboard.
Extended Contents There are many heap data structures. We won’t cover the following, but it is useful somtimes to using a more advanced heap.
-
Quiz 1 and Midterm exam
tl;dr: Exam preparation.
[Quiz 1] [Quiz 1 solutions]
Suggestions for the exam preparation:
We do not have past exams for preparation. But there are many useful online resources you can take a look on.
Rutgers U Washington Our midterm has many overalpping with this class. Notice that we do have different topics coverred. For example, we cover red-black tree instead of AVL tree which is taught in the University of Washington class.
DSA Quiz Here are many simple multiple choice problems you might want to take a look. A lot of them can be helpful in general (typical entry level interview questions) even they are not coverred in class so far.
-
Lecture 11-13
tl;dr: Sorting.
[Lecture 11 slides] [Lecture 12 slides] [Lecture 13 slides]
Assigned Readings:
-
Sorting and order statistics CLRS: You can read Chapter 6, 7, 8 for your reference. We will cover more topics in the lectures than CLRS.
-
Animation of sorting algorithms: You might find it provide an intuitive illustration of different sorting algorithms.
Lecture recording is on Blackboard.
-
-
Lecture 14
tl;dr: Hash table.
[slides]
Assigned Readings:
-
Unordered Sets in C++ Standard Template Library: in addition to unordered_set, unordered_map is also usually implemented with hash table.
In Python, dictionary is implemented with hash table data structures.
Lecture recording is on Blackboard.
Extended Readings:
- A lecture on universal and perfect hashing
-
A lecture note on universal and perfect hashing The Youtube video is a good MOOC lecture on universal hashing expected runtime and perfect hashing. Perfect hashing is to get expected O(1) search time. There used be a section about perfect hashing in CLRS edition 3. But it was removed in edition 4.
- Benchmarking on C++ hash maps std::unordered_map is a fine implementation covers daily usuage. But if you really need a huge hash table/map, using some other implementaitons is a good idea.
-
Lecture 15
tl;dr: Dynamic Programming.
[slides]
Assigned Readings:
Lecture recording is on Blackboard.
Extended Readings:
-
Lecture 16
tl;dr: Graph basics.
[slides]
Assigned Readings:
Recording is on Blackboard.
Extended Readings:
-
Lecture 17
tl;dr: Graph traversal and topological sort.
[slides]
Assigned Readings:
- Breadth First Search or BFS for a Graph
- Depth First Search or DFS for a Graph
- Wikipedia on topological sort
Recording is on Blackboard.
-
Lecture 18
tl;dr: Minimum spanning tree.
[slides]
This lecture is coverred in the exam.
Assigned Readings:
-