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:
Reading Materials
| Name | Author | Publisher | Link |
|---|---|---|---|
| Introduction to algorithms (CLRS). Third Edition | Cormen, Leiserson, Rivest, and Stein | MIT Press | UCR library |
Course Schedule
(This is a tentative scheduler, the final version may be different)
| Week | Topic | Content | Reading | |
|---|---|---|---|---|
| 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.
| Release Date | Due Date | About |
|---|---|---|
| 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
Grading
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.
Plagiarism Warning
Cheating or plagiarism will NOT be tolerated!!!
Check UCR academic integrity for additional information.
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.