Schedule

Assigned Readings:

• Wikipedia on ADTs
• (Extended Reading) An introduction to generic programming in Boost

Lecture recording is on Blackboard.

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

Assigned Readings:

• Wikipedia on analysis of algorithms
• Insertion sorting
• Linear search vs binary search

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

Assigned Readings:

• Wikipedia on big O notation
• Complexity notations

Lecture recording is on Blackboard.

In CLRS (optional textbook):

Chapter 1.3 Characterizing Running Times Asymptotic analysis and Landau notations

Assigned Readings:

• Wikipedia on linked list
• List in C++ STL

Lecture recording is on Blackboard.

In CLRS (optional textbook):

Chapter 1.2 Linked Lists

Assigned Readings:

• Amortized analysis
• Introduction to amortized analysis

Lecture recording is on Blackboard.

In CLRS (optional textbook):

Chapter 16 Amortized analysis

Assigned Readings:

• Introduction to Tree
• Wikipedia on Tree
• Wikipedia on Recursion

Lecture recording is on Blackboard.

Assigned Readings:

• Wikipedia on Binary Search Tree
• Binary Search Tree Tutorial

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.

• AVL tree

Assigned Readings:

• Chapter 13 Red-Black Tree of CLRS

• RB-tree Introduction

• RB-tree Inseetion

• RB-tree Inseetion

• An interactive visualization to RB-tree

• Red Black Tree vs AVL Tree

• A good explanation of the proof of O(log n) for red-black tree

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.

• Splay tree
• B Tree
• Van Emde Boas Tree

Trie, or prefix tree, is usually used to store string.

• Trie

Assigned Readings:

• Chapter 6 heapsort of CLRS

• Heap introduction

• Binary heap wikipedia

• Priority queue wikipedia

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.

• Leftist heap
• Binomial heap
• Fibonacci heap

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.

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.

• Lower bound for comparison based sorting algorithms

• Animation of sorting algorithms: You might find it provide an intuitive illustration of different sorting algorithms.

Lecture recording is on Blackboard.

Assigned Readings:

• CLRS chapter 11

• 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.

• Wikipedia on hash table
• Wikipedia on hash function

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.

Assigned Readings:

• CLRS chapter 14

• Wikipedia on dynamic programming

• Nth Fibonacci Number

• Wikipedia on Knapsack problemg

Lecture recording is on Blackboard.

Extended Readings:

• Wikipedia on Bellman equation

Assigned Readings:

• Wikipedia on Graph

• Wikiepdia on Graph Theory

• Comparison between adjacency matrix and adjacency list

• CLRS chapter 20.1

Recording is on Blackboard.

Extended Readings:

• Wolfram Mathworld on graph theory

Assigned Readings:

• CLRS chapter 20.2-20.4

• Breadth First Search or BFS for a Graph
• Depth First Search or DFS for a Graph

• Topological sorting

• Wikipedia on topological sort

Recording is on Blackboard.

This lecture is coverred in the exam.

Assigned Readings:

• Minimum spanning tree
• Kruskal’s algorithm
• Prim’s algorithm

Good luck.