CS 170 is Berkeley’s introduction to the theory of computer science. In CS 170, we will study the design and analysis of graph algorithms, greedy algorithms, dynamic programming, linear programming, fast matrix multiplication, Fourier transforms, number theory, complexity, and NP-completeness.
The prerequisites for CS 170 are CS 61B and CS70. You will need to be comfortable with mathematical induction, big-O notation, basic data structures, and programming in a standard imperative language (e.g., Java/C/Python). Another “prerequisite” for doing well in the course is mathematical maturity, or the ability to think about and work with proof-based math (which CS70 can help build).
The primary methods for engaging with the course material are through lectures, discussion sections, homework, and the readings. All are important, and exams will test a mix of the material from these sources.
Webcasts will be posted on the website and on CalCentral as soon as possible after every lecture.
Attendance at discussion sections is not required, although sections cover important material not covered in lecture that will appear on exams. You may attend any discussion section! Outside of your discussion section, you should feel free to attend any of the staff office hours (not just your section TA’s office hours) and ask any of us for help.
The required textbook is Algorithms by Dasgupta, Papadimitriou, and Vazirani, also known as DPV. Most readings will be from the textbook, and the relevant textbook chapters will be linked for each lecture. Any readings not from the textbook will be freely available as notes.
TA office hours are a fantastic resource for questions about concepts, course material including homework, and study tips. The instructors’ office hours are best for major concerns or high-level questions about the course material. We prioritize conceptual questions over homework questions in office hours.
We will hold two weekly homework parties! Homework parties are completely optional, but you are encouraged to come! This is a fantastic opportunity to meet people and form a group to study for the class and work on homework.
Every Monday evening, homework is posted on Piazza, and it is due the following Monday by 10:00 PM.
Please see the homework guidelines to see how to answer homework questions and format your homework submissions. You may lose points for not properly following the homework guidelines.
There will be one challenging, yet (hopefully) fun programming project, where you can apply the ideas from the course to solve an interesting problem algorithmically. Details on the project will be announced after the second midterm.
There will be two midterms and one final exam.
DSP exams will be 6pm-10pm the day of the midterm, and 4pm-10pm the day of the final.
We will compute grades from a weighted average, as follows:
The class will be curved at the end of the semester. There is no clobbering policy, but we may take into account participation on Piazza, discussion, office hours, HW Party and student performance.
Regrading of homeworks or exams will only be undertaken in cases where you believe there has been a genuine error or misunderstanding. Any requests for grade changes or re-grading must be made by the deadline. Submit regrade requests via Gradescope. Before making a request please make sure that you read Regrade Etiquette.
We may offer optional activities that provide a small amount of extra credit, for those eager for a tougher challenge. However, please note that you should do the extra credit problems only if you want an extra challenge. It is likely not the most efficient manner in which to maximize your score.
The guiding principle for homework collaboration is that your writeup of the solutions should be yours only.
You are encouraged to work on homework problems in study groups of up to five people; however, you must always write up the solutions on your own. Similarly, you may use books or online resources to help solve homework problems, but you must always credit all such sources in your write-up and you must never copy material verbatim. However, as a general rule of thumb, you should never possess solutions to exact homework questions other than those solutions you have written yourself. We realize that it is sometimes possible to stumble upon solutions on accident. If this happens, please cite the source and write up solutions in your own words.
We believe that most students can distinguish between helping other students and cheating. Explaining the meaning of a question, discussing a way of approaching a solution, or collaboratively exploring how to solve a problem within your group are types of interaction that we strongly encourage. But you should write your homework solution strictly by yourself so that your hands and eyes can help you internalize this material. At no time should you be in possession of another student’s solution. You may discuss approaches but your solution must be written by you and you only. You should explicitly acknowledge everyone whom you have worked with or who has given you any significant ideas about the homework.
Further, it is your responsibility to ensure that your solutions will not be visible to other students. If you use Github or another source control system to store your solutions electronically, you must ensure your account is configured so your solutions are not publicly visible. Many popular version control systems provide free repositories to students; staff members or fellow students can help you obtain one.
As a final note, we’d like to point out that collaboration on homework, while encouraged, can be detrimental to your learning if misused. In particular, avoid collaborations where you do not contribute enough to your own satisfaction. Such a collaboration not only cheats you out of an opportunity to learn through homework, but can also affect your confidence. If you feel that you are not contributing enough to your group, then try to spend time thinking about the problems alone before working with your group. If you end up solving the problem all by yourself that’s great! And if not, you’ll still be prepared to better contribute to your group.
If you’re ever in doubt about what constitutes academic dishonesty, always ask a TA or on Piazza.
Warning: Your attention is drawn to the Department’s Policy on Academic Dishonesty. In particular, you should be aware that copying or sharing solutions, in whole or in part, from other students in the class (or any other source without acknowledgment) constitutes cheating. Any student found to be cheating risks automatically failing the class and being referred to the Office of Student Conduct.
Piazza will be our primary communication method, and all announcements will be posted to Piazza. You are responsible for staying up-to-date with announcements and course updates made on Piazza.
Piazza is also a fantastic resource for course staff to answer your questions. Please read our Piazza Etiquette so we can help you most effectively. We also encourage you to help your fellow students by answering their questions - it is a great learning opportunity for them, and for you!
For logistics and administrative questions, please email cs170@, a private email that is only seen by the head TAs and professors. (add berkeley.edu after the @ symbol)
The staff is excited to teach for you this semester! If you would like some tips on how to do well in this course, please see our advice page.
Always feel free to contact us via email or visit us during office hours if you feel unsure about your progress in the course, or would just like to reach out. We are here to support you and help you succeed!