CS218 Design And Analysis Of Algorithms
Monday & Wednesday 2:00 – 3:20 PM Online (via Zoom)
Instructor: Yihan Sun -
Email : yihans@cs.ucr.edu Office Hour: TBA
TA: 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)
| Dates | Topic | Reading | Content | Attachment |
|---|---|---|---|---|
| Mon 1/4 | Introduction (*) | § 1, 2, 3 | Intro, Growth of function | |
| Wed 1/6 | Divide-and-Conquer (*) | § 4 | Merge sort, quicksort, Master theorem | |
| Mon 1/11 | Greedy algorithms (*) | § 16 | Activity selection, elements of greedy algorithm, Huffman code | |
| Wed 1/13 | Data Structure 1 | § 14 | Winning tree, augmented tree | |
| Mon 1/18 | Martin Luther King Day | |||
| Wed 1/20 | Dynamic programming 1 (*) | § 15 | Overview, knapsack, LCS | |
| Mon 1/25 | Dynamic programming 2 | § 15 | Memorization | |
| Wed 1/27 | Dynamic programming 3 | § 15 | Game, DP on trees | |
| Mon 2/1 | Dynamic programming 4 | § 15 | DP + optimization | |
| Wed 2/3 | Review for Midterm | |||
| Mon 2/8 | Midterm | |||
| Wed 2/10 | Randomized algorithms 1 | § 5, 9.2, 17 | Average analysis, quick selection, Rabin-Karp | |
| Mon 2/15 | Presidents Day | |||
| Wed 2/17 | Randomized algorithms 2 and amortize analysis | § 5, 9.2, 17 | Hash table, amortized analysis | |
| Mon 2/22 | Graph algorithms 1 (*) | § 22.1-22.3, 23 | Overview, BFS, DFS, Prim's | |
| Wed 2/24 | Data Structure 2 | § 21, 23 | Union-find, Kruskal's | |
| Mon 3/1 | Graph algorithms 2 | § 22.4, 22.5, 24 | Topological sort, connectivity, Dijkstra | |
| Wed 3/3 | Graph Algorithms 3 | § 26.3 | Matching | |
| Mon 3/8 | Data structure 3 | § 33.2 | Range tree, sweepline algorithm | |
| Wed 3/10 | Review for Final |
Some of the lecutues are marked with (*). This means that they are reviews for undergraduate algorithm courses. 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.
Assignments
Written Assignments
Here you can find sample code for writng solutions using LaTeX. Here is the instruction document about programming assignments.
| Release Date | Due Date | Assignment |
|---|---|---|
| Mon 01/04 | Mon 01/18 11:59pm | Assignment 1 |
| Wed 01/13 | Wed 01/27 11:59pm | Assignment 2 |
| Wed 01/27 | Wed 02/10 11:59pm | Assignment 3 |
| Wed 02/10 | Wed 02/24 11:59pm | Assignment 4 |
| Wed 02/24 | Wed 03/08 11:59pm | Assignment 5 |
Policy
Grading
Class Participation: 5% bonus
Assignments: 50% + 5% bonus
Midterm: 20%
Final exam: 30%
Late Policy
You have 4 late days and 2 grace days to use across the quarter. However, for each homework assignment, you can use no more than two (late_days+grace_days). This means that for each assignment, you have at most 48 hours after the deadline.
You will lose 20% of your score for each late day you use for one homework
assignment. If you use grace days, you don't lose points. If you use any of the grace days, please indicate it at the beginning of your solution.
For example, if you don't use any grace day:
* If you submit it within 24 hours after deadline, you get 80% of the points you earn.
* If you submit it within 48 hours after deadline, you get 60% of the points you earn.
* If you submit it later than 48 hours after the deadline, you don’t get any points for this homework.
If you use one grace day:
* If you submit it within 24 hours after deadline, you get 100% of the points you earn.
* If you submit it within 48 hours after deadline, you get 80% of the points you earn.
* If you submit it later than 48 hours after the deadline, you don’t get any points for this homework.
If you use two grace days:
* If you submit it within 24 hours after deadline, you get 100% of the points you earn.
* If you submit it within 48 hours after deadline, you get 100% of the points you earn.
* If you submit it later than 48 hours after the deadline, you don’t get any points for this homework.
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.