Instructors: Shusen Wang and Xuting Tang
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 31, Lecture 1
Array, vector, and list.
Binary search.
Skip List.
Insertion sort.
Sep 7, Labor Day, No Classes
Sep 14, Lecture 2
Merge sort.
Quick sort.
Quick select.
Divide and conquer.
Sep 21, Lecture 3
Matrix data structures.
Fast matrix multiplication.
Binary search trees.
Sep 27, 3:00 - 7:59 PM
Bonus Quiz (on Canvas, auto-graded.)
Voluntary; not required. Up to 2 bonus points.
Sep 28, Lecture 4
Binary search trees (cont).
Priority queues.
Oct 5, Lecture 5
Quiz 1, from 3 to 4 PM.
Disjoint sets.
Graph basics.
Oct 12, 20 Fall Recess; No Classes.
Oct 13, Lecture 6
Shortest path.
Spanning trees.
Oct 19, Lecture 7
Spanning trees (cont.)
Network flow.
Oct 26, Lecture 8
Network flow (cont.)
Bipartite graphs.
Nov 2, Lecture 9
Bipartite graphs (cont.)
Dynamic programming.
Nov 9, Lecture 10
Quiz 2, from 3:00 to 4:00 PM.
Dynamic programming (cont.)
Nov 16, Lecture 11
Nov 23, Lecture 12
Randomized algorithms.
Hashing.
Nov 30, Lecture 13
Quiz 3, from 3:00 to 4:00 PM.
Hashing (cont.)
Cryptographic algorithms.
Dec 7, Lecture 14
Homework 1: Programming
Available on Canvas.
Submit to Canvas before Sep 23.
Homework 2: Matrix Data Structure and Algorithms
Available on Canvas (auto-graded.)
Submit to Canvas before Sep 30.
Homework 3: Trees
Available on Canvas (auto-graded.)
Submit to Canvas before Oct 4.
Make sure you finish HM3 on time in order to get prepared for Quiz 1.
Homework 4: Heaps and Disjoint Sets
Available on Canvas (auto-graded.)
Submit to Canvas before Oct 13.
Homework 5: Graphs algorithms (Graph Basics, Shortest Paths, Spanning Trees, and Network Flow)
Available on Canvas (auto-graded.)
Submit to Canvas before Oct 25.
Homework 6: Bipartite Graphs
Available on Canvas (auto-graded.)
Submit to Canvas before Nov 8.
Homework 7: Programming
Available on Canvas.
Submit to Canvas before Nov 22.
Homework 8: DP and Strings
Available on Canvas.
Submit to Canvas before Nov 23.
Homework 9: Randomized Algorithms & Hashing
Available on Canvas.
Submit to Canvas before Dec 2.
Sep 27, 3:00 - 7:59 PM, Bonus Quiz
Online 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.
Oct 5, 3:00 - 4:00 PM Quiz 1
Online quiz (on Canvas, auto-graded.)
Time limit: 60 minutes.
Coverage: from the beginning to binary search trees.
Nov 9, 3:00 - 4:00 PM Quiz 2
Online quiz (on Canvas, auto-graded.)
Time limit: 60 minutes.
Coverage: from heaps to network flows.
Nov 30, 3:00 - 4:00 PM Quiz 3
Online quiz (on Canvas, auto-graded.)
Time limit: 45 minutes.
Coverage: from bipartite graphs to hashing basics.
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 4%
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.