Every Sunday evening, homework is posted on Piazza, and is due the following Sunday by 10:00 PM. No late homeworks will be accepted for any reason, since we release solutions immediately soon after the deadline. Scoring 90% or above on homeworks is considered full credit. We will drop your two lowest homework scores.
Although most of the homeworks are theoretical, there will be one challenging but fun programming project. The programming project cannot be dropped. Details will be decided and announced when that time approaches.
There will be two midterms and one final exam.
- MT1 - 9/18 7-9PM
- MT2 - 10/23 7-9PM
- Final - 12/10 3-6PM
DSP midterms will take place on the corresponding days between 6 and 10PM, and the DSP final will take place on the corresponding day between 12 and 6PM. The exact times will be emailed closer to the exams.
All exams are mandatory. We will not provide any alternate exams.
There is no clobbering policy, but we may take into account participation on Piazza, discussion, office hours, HW Party and student performance if the grade is on a boundary.
We will compute grades from a weighted average, as follows:
- Homeworks: 15%
- Programming Project: 5%
- Midterm 1: 20%
- Midterm 2: 25%
- Final exam: 35%
The class will be curved at the end of the semester.
You are encouraged to work on homework problems in study groups of three 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.
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 note that 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.
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.
Other Policies and Information
All announcements will be posted to Piazza. You are responsible for staying up-to-date with announcements made on Piazza.
Please contact course staff through Piazza. Be careful about posting homework questions (do not give away the answers or parts of the answers). If you want only the instructors to see your post, mark it as private.
If you want to contact the Professors and Head TAs for special requests, email email@example.com.
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).
The required textbook is Algorithms (Dasgupta, Papadimitriou, and Vazirani). All chapter numbers and exercise numbers in this course refer to the official paper textbook, not the online version.
Attendance at discussion sections is expected, and sections may cover important material not covered in lecture. You may attend any discussion section, regardless of your registration. 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.
TA office hours are for homework- and midterm-related questions, or minor concerns. Prof. Chiesa’s and Prof. Rao's office hours are for major concerns or high-level questions about the course material. Please note that on Mondays and Tuesdays, Office Hours will prioritize conceptual questions over homework questions.
We will hold two weekly homework parties: Wednesdays 5-8PM in Cory 540AB (on most weeks; see calendar for most up-to-date information) and Fridays 2-5PM in the Wozniak Lounge in Soda Hall. Homework parties are completely optional, but are strongly encouraged. This is an opportunity to find a group of other students to work together on the homework. Students are expected to form ad-hoc "pickup" homework groups, in the style of a pickup basketball game, and help others in their group.
You can write your homework in one of the following ways:
- Typeset your answers using LaTeX. (Strongly recommended, see [piazza link])
- Type your answers using a mainstream word processor.
- Neatly handwrite, then use a flatbed scanner or smartphone app (such as CamScanner) to produce a PDF. Do not simply take a photo and dump it into a PDF.
The readers work hard to grade your homeworks in a timely manner, and with useful feedback. Given the size of the course, we require a certain format of all homeworks: each problem must start on a new page, and clearly display the problem number; if a problem has multiple parts, make sure that each part fits on a page.
List your collaborators on the first page of your submission. If you have no collaborators, you must explicitly write "none".
Responding to Algorithm Problems
Oftentimes, a problem will ask you to "give/design/devise/formulate/create/etc. an algorithm" or to "show how" to solve some computational task. In this case, write your solution in the 4-part algorithm format detailed here.
Homework must be submitted via Gradescope. If you encounter an issue at 10:00PM and Gradescope doesn't let you submit the homework, it will not be accepted.
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.
Students may use laptops and other electronics in the class. But if you do so, please sit only in the rows at the back of the class, so as to not disturb anyone else.
Extra credit opportunities:
The instructor reserves the right to offer optional activities that provide a small number of extra credit, for those eager for a tougher challenge. We recommend you do them only if you enjoy these problems, as spending effort on them is likely not the most efficient way to maximize your final course grade.
The following tips are offered based on our experience with CS 170:
Don't fall behind!
In a conceptual class such as this, it is particularly important to maintain a steady effort throughout the semester, rather than hope to cram just before homework deadlines or exams. This is because it takes time and practice for the ideas to sink in. Make sure you allocate a sufficient number of hours every week to the class, including enough time for reading and understanding the material as well as for doing assignments. (As a rough guide, you should expect to do at least one hour of reading and two hours of problem solving for each hour of lecture.) Even though this class does not focus on projects, you should plan to spend as much time on it as your other technical classes.
Do the homeworks, and go over homework solutions:
The effort you spend on the homework assignments is the largest factor in your mastery of the material, and thus performance in the class as a whole. The staff posts detailed solutions of the homework problems each week, often with multiple solution approaches and commentary. Regardless of how well you did on the homework, make it a priority to carefully read the solutions and compare them with your own work, even for the problems you got right. The main reason to do so is that sample solutions will often be simpler and cleaner. You will have a higher chance of solving similar problems under exam pressure if you have a simple picture. You may well learn a different way of looking at the problem, and you may also benefit from emulating the style of the solutions. It might seem attractive in the short term to just ignore homework solutions, or delay reading them until the day before the final. Some students will even try to finish the homework faster by looking up solutions to problems online. But these practices are detrimental to understanding in the long term, and thoroughly understanding solutions is a critical step to mastering the material. These homeworks are provided to you not as a chore, but as an opportunity for you to challenge yourself and explore the wonderful world of algorithms. Don’t short-change yourself by skimping on them. As an added incentive, we will draw from the homework problems when writing exams.
Don't wait until the last minute to start homeworks!
Read through the homework problems as soon as they are available, and let them percolate in your brain. Schedule multiple times throughout the week to attempt the problems. Often, the solution will only come to you the second or third time you try a problem. Definitely do not wait until the night before it is due to start working on the homework. If you do this (alas, procrastination is all too common), (a) the stress will make it harder to be creative and solve the problems; (b) you will be tempted to ask your homework group for too many hints (or outright solutions) to the problems, which borders on cheating and impedes your learning, and (c) the stress will sap the joy of finding algorithms!
Make use of office hours and discussion sections:
The instructor and TAs hold office hours expressly to help you. You are free to attend as many office hours as you wish (you are not constrained just to use the office hours of your section TA). Discussion sections are an opportunity for interactive learning. The success of a discussion section depends largely on the willingness of students to participate actively in it. As with office hours, the better prepared you are for the discussion, the more you are likely to get out of it.
Form study groups!
As stated above, you are encouraged to form small groups (e.g. of four students) to work together on homeworks and on understanding the class material on a regular basis. If you’re unsure about how to find a study group, attending homework parties is a great way to getting started. In addition to being fun, this can save you a lot of time by generating ideas quickly and preventing you from getting hung up on some point or other. Of course, it is your responsibility to ensure that you contribute actively to the group; passive listening will likely not help you much. And recall the caveat above that you must write up your solutions on your own. Spend some time on your own thinking about each problem before you meet with your study partners; this way you will be in a position to compare ideas with your partners, and it will get you in practice for the exams.