Instructors: Shusen Wang
Meeting Time:
Office Hours:
Contact the Instructor:
For questions regarding grading, send emails to the instructor.
For technical questions, ask the instructor during office hours, or start a discussion in the “Discussions” module of Canvas.
Prerequisite:
Familiar with either C++ or Python.
Know the basics of C++.
Familiar with basic data structures and algorithms, including
asymptotic notations (big-O, small-o, Ω, Θ),
basic data structures (arrays, linked lists, stacks, queues).
If you do not meet the prerequisites, consider taking CS385 or CS590 first.
Slides: All the slides are available here: [link]
Aug 30, Lecture 1
Array, vector, and list.
Binary search.
Skip List.
Insertion sort.
Sep 6, Labor Day, No Class
Sep 13, Lecture 2
Merge sort.
Quick sort.
Quick select.
Divide and conquer.
Sep 19, 7:00 - 10:59 PM
Online Bonus Quiz (on Canvas, auto-graded.)
Voluntary; not required. Up to 2 bonus points.
Time limit: 20 minutes.
Coverage: array, vector, list, skip list, divide-and-conquer.
Sep 20, Lecture 3
Matrix data structures.
Fast matrix multiplication.
Binary search trees.
Sep 27, Lecture 4
Binary search trees (cont).
Priority queues.
Oct 4, Online Quiz 1, from 3 to 4 PM.
On Canvas, auto-graded.
Time limit: 60 minutes.
Coverage: from the beginning to binary search trees.
Oct 4, Lecture 5
Disjoint sets.
Graph basics.
Oct 11, No Class; Class Moved to Tuesday
Oct 12, Lecture 6
Shortest path.
Spanning trees.
Oct 18, Lecture 7
Oct 25, Lecture 8
Nov 1, Online Quiz 2, from 3:00 to 4:00 PM.
On Canvas, auto-graded.
Time limit: 60 minutes.
Coverage: from heaps to network flows.
Nov 1, Lecture 9
Nov 8, Lecture 10
Nov 15, Lecture 11
Nov 22, Lecture 12
Nov 29, Lecture 13
Hashing
Cryptographic algorithms.
Dec 6, Online Quiz 3, from 3:00 to 4:00 PM.
On Canvas, auto-graded.
Time limit: 45 minutes.
Coverage: from bipartite graphs to hashing.
Dec 6, Lecture 14
Dec 13, Final Exam, from 3:00 to 5:00 PM.
Homework 1: Programming
Available on Canvas.
Submit to Canvas before Sep 12.
Homework 2: Matrix Data Structure and Algorithms
Available on Canvas (auto-graded.)
Submit to Canvas before Sep 26.
Homework 3: Trees
Available on Canvas (auto-graded.)
Submit to Canvas before Oct 3.
Make sure you finish HM3 on time in order to get prepared for Quiz 1.
Homework 4: Programming
Available on Canvas.
Submit to Canvas before Oct 10.
Homework 5: Heaps and Disjoint Sets
Available on Canvas (auto-graded.)
Submit to Canvas before Oct 13.
Homework 6: Programming
Available on Canvas.
Submit to Canvas before Oct 17.
Homework 7: Graphs algorithms (Graph Basics, Shortest Paths, Spanning Trees, and Network Flow)
Available on Canvas (auto-graded.)
Submit to Canvas before Oct 31.
Homework 8: Bipartite Graphs
Available on Canvas (auto-graded.)
Submit to Canvas before Nov 7.
Homework 9: Programming
Available on Canvas.
Submit to Canvas before Nov 14.
Homework 10: DP and Strings
Available on Canvas.
Submit to Canvas before Nov 21.
Homework 11: Programming
Available on Canvas.
Submit to Canvas before Nov 25.
Homework 12: Randomized Algorithms & Hashing
Available on Canvas.
Submit to Canvas before Dec 5.
Grades:
A: 93 and above.
A-: [90, 93)
B+: [87, 90)
B: [83, 87)
B-: [80, 83)
C+: [77, 80)
C: [73, 77)
Fail: below 73
Weights:
Homework 50%
Quizzes 30%
Final 20%
Bonus 2%
Late penalty:
Late submissions for whatever reason will be punished. 2% of the score of an assignment/project will be deducted per day. For example, if an assignment is submitted 15 days and 1 minute later than the deadline (counted as 16 days) and it gets a grade of 95%, then the score after the deduction will be: 95% - 2*16% = 63%.
Dec 10 is the firm deadline for all the assignments. Submissions later than the firm deadline will not be graded.