Basics of graphs: traversals; cycles; connectivity; trees and dags
Hashing and sketching
Intractability and ways to cope with it
Required text (available at bookstore): Dasgupta-Papadimitriou-Vazirani
Lectures will be recorded and available at http://podcast.ucsd.edu.
You must choose a particular discussion section to attend weekly. Homeworks and quizzes will be returned at this section.
Wed 4-5, Peterson 102
Wed 6-7, Peterson 102
Wed 7-8, Mandeville B-150
Midterm 1: TBA, in class
Midterm 2: TBA, in class
Final: December 9, 3-6pm, in class
There will be a homework due every Friday at noon (via GradeScope, see below), and a quiz that Friday covering the same material. Solutions to the homework will be posted shortly after it is due.
A good way to understand the course material is to discuss homeworks with your peers.
We will be handling homeworks through Gradescope. To initialize your account, go to gradescope.com, enter your campus email address, and select "Forgot password" to trigger a password reset. If the system does not recognize your email, please contact the instructor or TAs.
Homeworks can be handwritten or typeset, but each problem should begin on a fresh page; this is not necessary for subproblems. Upload a PDF of your homework to gradescope.com by noon on Friday at the latest; no late submissions will be accepted. When uploading, you will be asked to indicate which page(s) correspond to which problems.
Homeworks: 10% (lowest score will be dropped)
Quizzes: 20% (lowest score will be dropped)
Midterms: 15% each