Instructors: Shusen Wang and Xuting Tang

**Meeting Time:**

- Monday, 3:00-5:30 PM, Online until notified otherwise

**Office Hours:**

- Monday, 5:30-6:30 PM, Online

**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

- Strings.

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

- Cryptographic algorithms (Cont.).

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.