Efficient Algorithms and Intractable Problems

  

CS170
Efficient Algorithms and Intractable Problems
a.k.a. Introduction to CS Theory 

 

 


Prof. Christos Papadimitriou & Prasad Raghavendra
Spring 2015

Lectures: Tue-Thu 5:00-6:30pm, 155 Dwinelle.

Sections: 

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

Textbook: The required textbook is Algorithms (Dasgupta, Papadimitriou, and Vazirani) as our textbook. All chapter numbers and exercise numbers in this course refer to the official paper textbook, not the online version.

Announcements: All announcements will be posted to Piazza. You are responsible for staying up-to-date with announcements made on Piazza.

Contact information: If you have a question, the best way to contact us is via the class Piazza site. The staff (instructors and TAs) will check the site regularly, and if you use it, other students will be able to help you too. Avoid posting answers or hints on homework questions before the homework is due. If in doubt, mark your question as private.

If your question is personal or not of interest to other students, you are encouraged to mark the question as private on Piazza. If you wish to talk with one of us individually in person, you are welcome to come to any of our office hours. We prefer that use these methods instead of sending us email; email regrettably does not scale well to a class of this size.

 

Tentative Schedule

We will meet Tuesdays and Thursdays from 5 to 6:30. Everyone should sign up for a discussion section as well.

  • First Midterm: March 12, 6:30pm to 8pm.
  • Second Midterm: April 16, 6:30pm to 8pm.
  • Final Exam: check schedule.berkeley.edu

Lesson #

Date

Topic

Readings

1

Jan 20

Introduction and overview

Chapter 0

2

Jan 22

Modular arithmetic, divide and conquer

Section 1.2, section 2.1, 2.2

3

Jan 27

Hashing, divide and conquer (continued)

Section 1.5, 2.5

4

Jan 29

Divide and conquer

Chapter 2.1-2.5

5

Feb 3

Roots of unity, Fourier transform

Pages 63-66

6

Feb 5

Fast Fourier transform

Section 2.6

7

Feb 10

Graph search

Chapter 3

8

Feb 12

Graph search

Chapter 3

9

Feb 17

Shortest paths

Chapter 4

10

Feb 19

Shortest paths

Chapter 4

11

Feb 24

Spanning trees and greedy algorithms

Chapter 5

12

Feb 26

Spanning trees and greedy algorithms

Chapter 5

13

Mar 3

Parallel algorithms

 

14

Mar 5

Dynamic programming

Chapter 6

15

Mar 10

Dynamic programming

Chapter 6

16

Mar 12

Midterm I

 

 

 

 

 

17

Mar 17

Dynamic programming

Chapter 6

18

Mar 19

Linear programming

Chapter 7

 

Mar 24

NO class (spring recess)

 

 

Mar 26

NO class (spring recess)

 

19

Mar 31

Linear programming

Chapter 7

20

Apr 2

Linear programming

Chapter 7

21

Apr 7

Linear programming

Chapter 7

22

Apr 9

Linear programming

Chapter 7

23

Apr 14

NP-completeness

Chapter 8

24

Apr 16

Midterm II

 

25

Apr 21

NP-completeness

Chapter 8

26

Apr 23

Coping with NP-completeness

Chapter 9

27

Apr 28

Coping with NP-completeness

Chapter 9

28

Apr 30

Coping with NP-completeness

Chapter 9 

 

(Rough) weights for final grade:

          30% homework

          20% first midterm

          20% second midterm

          30% final exam

There will be a fun programming problem during the last two weeks of the course and quizzes during discussion sections. The programming problem will count as a homework that cannot be dropped. If you score less than 40% out of a possible 70% on the homework and midterms, your quizzes will count for up to 5%. Note, these quiz results can NOT reduce your score in the class, it can only increase it.

Getting Help / Office Hours : Piazza is a great place to get help. Instructor office hours and e-mail addresses are also listed on Piazza.

Homework:

We will assign weekly problem sets. Homework is due every Friday at 5pm and self-grading is due every Monday at 5pm electronically via Gradescope (previously Pandagrader).     

Absolutely no late homeworks or homework excuses,  but we will drop the TWO lowest homework grades (this is a valuable piece of peace of mind, please don't waste it by skipping the first two . In fact, it is a terrible idea to skip working on a homework, even if you may skip writing it up and submitting.)

Submission instructions: Submit your homework, in PDF (not images), electronically via Gradescope. Details on the homework and self-grading submission process will be provided later. 

You have three options for creating your PDF files:

  • Use LaTeX . This is the recommended method since it is powerful and convenient to use for typesetting mathematics, and it produces nice-looking documents. Nice documents predispose graders.  And LaTeX looks ok in your resume. We will post a LaTeX template for you to use for each homework for those who wish to use LaTeX. Useful LaTeX platforms include texmakerand texworks; or, you can compile latex documents to PDF using pdflatex on a Unix machine. Alternatively, you could also use LyX
  • Use a word processor and export the document to PDF.
  • Handwrite your homework on paper and scan it to PDF. You can scan at the libraries or using a scanner on the 2nd floor of Soda Hall.

We really strongly advise you to go with the first option.  

Formatting your homework: Put your name, student ID number, class account userid, and the homework number prominently at the top of the first page of your PDF file. Also, list the people you collaborated with on the first page. Each problem should begin on a new page. You risk receiving no credit for any homework that does not adhere to these guidelines.

Special information: Please follow these instructions on how to write up algorithms on homeworks. We insist that you provide a clear explanation of your algorithms and the intuition of how it works. It is not acceptable to provide a long pseudocode listing with no explanation. In our experience, in such cases the algorithm usually turns out to be incorrect. Even if your algorithm turns out to be correct, we reserve the right to deduct points if it is not clearly explained. Homework solutions must be legible. We will not grade messy or unreadable submissions.

Homework parties: We will hold a weekly homework party Wednesdays 8-11pm at the Woz! (except March 11th). Homework parties are completely optional. 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. TAs will be present to help you. If the room is crowded, please, be kind and make room for others by leaving if you can find an alternative source of assistance. When the room is not crowded, people from the class are welcome to just hang out as long as they aren't bothering other people. For us to be able to continue to offer this service, you all have to be very responsible in taking care of the room, not make a mess, and put things back the way they were before you leave.

Self-grading and redemption: After solutions are posted Friday around 5pm, you must self-grade your homework by Tuesday 5pm and resubmit it (your homework will not be graded if you don't submit this). For certain problems, you will be given the chance to demonstrate that you have understood thoroughly the correct solution (not by cutting and pasting the solution, but by explaining it in your own clear and novel way), and that you have also understood the reasons why your own solution was wrong. If you do these things correctly and thoroughly, you will get (actually, take) half of the credit back. Self-graded homeworks will then be checked by readers.

What if I find the answer in a book or online? Good work! Read what you found, then log off and answer the question in your own words. Cite the sources you used.

Late homework will not be accepted. Instead, we will drop your lowest two homework grades, except that the last homework (a programming problem) can't be dropped.

Collaboration: For each homework, you may collaborate with at most 3 other students. We encourage you to collaborate with your fellow students (in small groups) on the homeworks.  Be sure to write the names of your group members on the first page of your homework submission.

If you don't have a group to work with, come to the homework parties and form one! Clarifying concepts and discussing possible approaches to problems are good forms of collaboration. However, you must write up all solutions on your own, without ever looking at or copying any other student's solutions. If you are tempted to look at someone else's solutions (this includes over the Internet), keep in mind that the exams carry much more weight than the homeworks, and there is a strong correlation between students' exam scores and the effort they put into the homework.

Academic dishonesty: Cheating on homeworks or exams will be taken seriously. We refer you to the department's policy on academic dishonesty and the the campus honor code. In particular, keep the following in mind:

  • Give credit. You must list any students you worked with, as well as other sources of information you used, on the first page of your homework.
  • Don't share solutions. Working together means clarifying concepts and discussing possible approaches. Never look at any part of someone else's solution (including online) and never share any part of your own work with another student.
  • When in doubt, ask. If you're not sure whether a particular situation constitutes cheating, ask a TA or the instructor.
  • Also in self-grading: Dishonesty in self-grading will be punished by double loss of credit.  Recurring dishonesty in self grading will be treated as academic dishonesty.

We expect that most people can distinguish legitimate collaboration from cheating, but here are some more details. Telling someone who is not in your homework group how to solve a homework problem is not allowed. Splitting up the problems -- "you solve the first three problems, I'll solve the last three problems, and we'll tell each other how to solve them" -- is not collaboration and not allowed. No matter what, you must write up your solutions entirely on your own. For homeworks, you must never read, see, or copy the solutions of other students, and you must not allow other students to see your solutions. You must never share your solutions, or partial solutions, with another student -- not even with the explicit understanding that they won't be copied; not even with students in your homework group. You must not receive help on homeworks from students who have taken the course in previous years. You must not review homework solutions from previous years. You must not search the Internet for a solution to the exact problem we gave you on a homework. The only way to learn algorithms to practice, practice, practice, so we want you to solve the problems on your own, not rely on other sources as a crutch.

You must 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. If you use Github, Github offers free student accounts that allow you to keep your solutions private; please use one.

Extra credit problems: Do the extra credit problems only if you really enjoy working on these problems and want an extra challenge. It is likely not the most efficient manner in which to maximize your score.

Discussion sections: Attendance at discussion sections is expected, and sections may cover important material not covered in lecture. 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.  Each discussion section will begin with a short quiz. 

Computer accounts: We expect to use 'class' accounts for the programming problem. You will need to obtain an account form with a username and password from your discussion section TA. When you first log into your account, you will be prompted to enter information about yourself; that will register you with our grading software. If you want to check that you are registered correctly with our grading software, you can run check-register at any time. 

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.

Don't be afraid to ask for help: Are you struggling? We'd much rather you approached us for help than gradually fall behind over the semester until things become untenable. Sometimes this happens when students are afraid of an unpleasant conversation with a professor if they admit to not understanding something. We would much rather deal with your misunderstanding early than deal with its consequences later. Even if you are convinced that you are the only person in the class that doesn't understand the material, and that it is entirely your fault for having fallen behind, please overcome your feeling of guilt and ask for help as soon as you need it. Remember that the other students in the class are working under similar constraints -- they are taking multiple classes and are often holding down outside employment. Don't hesitate to ask us for help -- helping you learn the material is what we're paid to do, after all!

Advice: The following tips are offered based on our experience with CS 170:

  1. Come to the lectures!  The lectures present a complementary view of the material, which you will not find in the book, and are much easier to follow live.  Skipping lectures will deprive you of much of the fun and mystique of the class.
  2. 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 have any major projects, you should plan to spend as much time on it as your other technical classes.
  3. Do the homeworks! The homeworks are explicitly designed to help you to learn the material as you go along. Although the numerical weight of the homeworks is small, there is usually a strong correlation between homework scores and final grades in the class. (The most common denominator among people who do poorly in the class is that they skipped several homework assignments or multiple homework problems.)
    Also, regardless of how well you did on the homework, read the sample solutions, even for the problems you got right. You may well learn a different way of looking at the problem, and you may also benefit from emulating the style of the solutions. (In science people learn a lot from emulating the approach of more experienced scientists.)
  4. Don't wait until the last minute to start homeworks! My best advice is to read through the homework problems as soon as they are available, and let them percolate in your brain. Think through possible approaches while you are waiting in line, or stuck in an elevator, or whatever. Sleeping on a problem has often helped people to come up with a creative approach to it. Definitely do not wait until the night before it is due to start working on the homework.
  5. Make use of office hours! 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). You will also likely get more out of an office hour if you have spent a little time in advance thinking about the questions you have, and formulating them precisely. (In fact, this process can often lead you to a solution yourself!)
  6. Take part in discussion sections! Discussion sections are not auxiliary lectures. They 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.
  7. Form study groups! As stated above, you are encouraged to form small groups (two to four students) to work together on homeworks and on understanding the class material on a regular basis. 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. I strongly advise you to 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. 

 

Course Summary:

Date Details Due