Overview

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.

Prerequisites

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).

Course Format

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.

Lecture

Lectures will be held in Li Ka Shing 245 every Tuesday and Thursday from 3:30 PM to 4:59 PM. They will be asynchronously recorded, but (as of now) not zoom livestreamed.

Discussion sections

There is no discussion in the first week. Details for the specific times will be decided and announced on Ed. 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.

Textbook

The textbook for this course is Algorithms by Dasgupta, Papadimitriou, and Vazirani, also known as DPV. The relevant textbook sections will be linked for each lecture.

Office Hours

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.

Course Communication

Edstem

Ed will be our primary communication method, and all announcements will be posted to Ed. You are responsible for staying up-to-date with announcements and course updates made on Ed.

Ed is also a fantastic resource for course staff to answer your questions. Please read our Forum 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!

Contacting Staff

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).

Assignments and Exams

Homework

Every Tuesday evening, homework is posted on Ed, and it is due the following Monday by 10:00 PM, followed by a 119 minute grace period until 11:59 PM.

• Homework submission is through Gradescope.
• You will lose no points if you submit by the late deadline of 11:59 PM. We accept absolutely no submissions after 11:59 PM, even after technical issues or emergencies. No exceptions. We strongly recommend you use the late deadline to protect against technical issues and have your homework finished by 10:00 PM.
• At the end of the semester, we will automatically drop your two lowest homeworks (including any you may have received a 0 on).
• We want you to focus on understanding the material for homeworks, not necessarily on maximizing your score. For this reason, we will give you full credit on a homework if you score above 90%. If you score below 90%, we will divide your score by 0.9, e.g. a score of 50% becomes 55.5%.

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.

Exams

We will have two midterms and one final—all conducted in person. We are not planning on offering alternate exams or remote exams. If you are unable to attend any exam, please email [email protected]

Exam schedule:

• Midterm 1: Monday, 2/26/2024, 7:00 PM - 9:00 PM
• Midterm 2: Tuesday, 4/2/2024, 7:00 PM - 9:00 PM
• Final: Friday, 5/10/2024, 7:00 PM - 10:00 PM (Group 20)

Exam-specific policy will be released closer to the exam dates.

Grading

We will compute grades from a weighted average, as follows:

• Homeworks: 15%
• Exams: 85%
  • Midterm 1: 25%
  • Midterm 2: 25%
  • Final: 35%

The class will be curved at the end of the semester. There is no clobbering policy, but we may take into account participation on Ed, discussion, office hours, HW Party and student performance when considering students on grade borderlines.

Regrades

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. Note that we reserve the right to take points off for frivolous or repetitive regrade requests.

Extra Credit

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 grade.

Waitlist/Late Adds

If you are on the waitlist, you have full access to all course materials and you are expected to keep up with the course content and submit assignments just as you would if you were officially enrolled in the class. If you enroll in the course late and miss assignments, missing homework scores can be automatically dropped using your two homework drops, but we cannot offer you any additional extensions or homework drops.

Disability Accommodations

UC Berkeley is committed to creating a learning environment that meets the needs of its diverse student body including students with disabilities. If you anticipate or experience any barriers to learning in this course, please feel welcome to send your concerns to cs170@.

If you have a disability, or think you may have a disability, you can work with the Disabled Students’ Program (DSP) to request an official accommodation. The Disabled Students’ Program (DSP) is the campus office responsible for authorizing disability-related academic accommodations, in cooperation with the students themselves and their instructors. You can find more information about DSP, including contact information and the application process here: dsp.berkeley.edu.

Students who need academic accommodations or have questions about their accommodations should contact DSP, located at 260 César Chávez Student Center. Students may call 642-0518 (voice), 642-6376 (TTY), or e-mail [email protected].

Collaboration

The guiding principle for homework collaboration is that your writeup of the solutions should be yours only.

With the exception of solo problems (see Homework Guidelines), you are encouraged to work on homework problems in study groups; however, you must always write up the solutions on your own, listing all collaborators at the top. 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.

Usage of LLMs

In general, you should treat the outputs of LLMs (including, but not limited to, ChatGPT, Copilot, and other LLM-based code completion tools) the same way you would treat any resource you find online: just like you shouldn’t search the internet for direct answers to homework questions, you shouldn’t ask LLMs to directly solve homework questions for you. Likewise, if you use LLMs to help you solve a homework question, you should cite it just like you would any other resource.

If you’re ever in doubt about what constitutes academic dishonesty, always ask a TA or on Ed.

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.

Parting Thoughts

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!