## CS218 Design And Analysis Of Algorithms

Monday， Wednesday & Friday    4:00 – 4:50 PM    Online (via Zoom)

Instructor: Yan Gu   -    Email : ygu@cs.ucr.edu    Office Hour: TBA

### Course Information

The course covers efficient algorithms and data structures for problems from a variety of areas such as sorting, searching, selection, linear algebra, graph theory, and combinatorial optimization. It will also cover techniques for algorithm design (greedy, divide-and-conquer, dynamic programming) and rigorous proofs of correctness and time- and space-complexity (amortized analysis, Master Theorem).

Lecture: 3 hours.
Prerequisite(s): CS 141 or equivalent courses; proficiency in programming.

#### Other Useful Tools

You could post your questions or problems you want to discuss on Piazza.
All written homework solutions should be submitted via Gradescope.
All programming assignments should be submitted via CodeForces.

#### Calendar:

Introduction to algorithms (CLRS). Third Edition Cormen, Leiserson, Rivest, and Stein MIT Press UCR library
Prerequisite knowledge in the book includes: Sections 1-4, 6, 7, 10-13, 15, 16, 22.1-22.3, and 23-25 in the book. Plaese make sure you understand these sections.

### Course Schedule

(This is a tentative scheduler, the final version may be different)

1 Introduction (*) Intro, Growth of function § 1, 2, 3
Divide-and-Conquer (*) Merge sort, quicksort, Master theorem § 4
2 Greedy algorithms (*) Activiti selection, elements of greedy algorithm, Huffman code § 16
Data Structure 1 Winning tree, augmented tree § 14
3 Dynamic programming (*) Overview, knapsack, LCS § 15
Dynamic programming Memorization § 15
4 Dynamic programming Game, DP on trees § 15
Dynamic programming DP + optimization § 15
5 Randomized algorithms Average analysis, quick selection, Rabin-Karp § 5, 9.2, 17
Review for Midterm
5/3 Midterm exam
6 Randomized algorithms and amortize analysis Hash table, amortized analysis § 5, 9.2, 17
7 Graph algorithms (*) Overview, BFS, DFS, Prim's § 22.1-22.3, 23
Data Structure 2 Union-find, Kruskal's § 21, 23
Graph algorithms Connectivity and SCC § 22.4, 22.5
8 Graph algorithms Dijkstra and other SSSP § 24
Graph algorithms Matching § 26.3
Graph Algorithms Network flow § 26
9 Graph Algorithms Network flow § 26
10 Review for Final
6/6 Final exam

Some of the lecutues are marked with (*). This means that they are reviews for undergraduate algorithm courses (in particular, CS141 at UCR). Note that this does not mean that we'll learn these topics again in CS218. They are just to remind you the contents that you should already be familiar with. You need to make sure you have already learned them in previous courses. If not, you should take CS 141, which is a prerequisite of CS 218.

### Assignments

#### Written and Programming Assignments

Here you can find sample code for writng solutions using LaTeX.

3/29 4/9 11:59pm Divide-and-Conquer, and other prerequisites
4/9 4/19 11:59pm Greedy
4/19 4/30 11:59pm Dynamic Programming
5/3 5/17 11:59pm Randomized algorithms, graph
5/17 6/2 11:59pm Graph

### Policy

Class Participation: 5% bonus
Assignments: 50%
Midterm: 20%
Final exam: 30%

#### Late Policy

You have 4 grace days throughout the quarter. More details will be talked about in the lecture.

#### Cheating or plagiarism will NOT be tolerated!!!

For homework assignments:

You CAN get help from the instructors, TAs, textbooks (or relevant books), or the Internet, but must cite them. You can discuss homework problems with your classmates, but must acknowledge them. You CANNOT look at others' solution or share your solution with others. You CANNOT copy anything from the book or the Internet. When you write down your solution, it MUST be close-book.

### Other Suggestions

• You need basic knowledge about algorithms, data structures, probabilistic, and discrete math. Courses such as CS141 is helpful. If you don't have some basic background in algorithms, you should take these courses first. If you don't have such basic knowledge and you still want to take the course, you have to be aware that you need to spend more time on the course.
• Reading slides and the textbook before each lecture could be very helpful. All course material will be available online before class.
• You could participate in the discussions in Piazza. Paying attention to other students' questions can also be helpful for yourself.
• Start working on homework assignments as early as possible. You have about 2 weeks for each of the homework assignment. However, don't start working on it on the last day. The homework problems can be hard and take a lot of time to finish.
• Please don't underestimate the time you will need to spend on this course. Especially if you don't have enough background in algorithm design, you need to spend much more time in this course.
>>>>>>>>>>>>