Key documents about the course:
- Everything begins with the syllabus. Among other things, this document tells you what you can expect from me for the class.
- The following Common Policy Documents are referenced in the syllabus and are incorporated into it by reference:
- We also have a Projected Schedule, complete with exam dates as well as due dates for programming assignments.
Announcements:
Students enrolled should also have access to EdDiscussion board, which will be used frequently. Announcements may be made on this page or on the EdDiscussion board, and you should check both regularly.
Contacting the Professor
- To contact the professor, please fill out this form. You will need to be logged into your UCI Google account to do so. He will view responses a few times a week. Please use this form only for matters that require the professor's specific attention.
Before filling this out, if this is something that could be answered by your classmates or a TA, such as asking for a clarification on a lecture topic, please make a public post on EdDiscussion. If it could be answered by any member of course staff, such as asking for help debugging your programming assignment, please make a private post on EdDiscussion
Lecture Handouts:
The following are digital copies of handouts that I plan to provide in lecture. I recommend you have a printed copy (which will likely be provided in the first lecture on each topic) and take notes in pen or pencil (not digitally).
- Lectures 2 and 3 handout covers the introduction to dynamic programming.
- Lectures 4-6 handout covers the introduction to complexity, including introduction to coping with complexity and recognizing easy vs hard problems for a computer (a major theme of this class!).
- Lectures 7-8 cover tying together concepts from the first three weeks.
- Lecture 9 covered the two diagnostic exams as preparation for the midterm on May 3.
- Lectures 10-11 cover exact (correct) greedy algorithms.
- Lectures 12-13 cover greedy approximation algorithms
- Lectures 14-16 cover Divide and Conquer algorithms. This file was updated May 30; the major change is the addition of the last digital page.
Lab Worksheets:
I recommend you read these before lab and attempt the problems, first alone and then with one or more study partners. I will not check that you have done that, but I have found that students who do this tend to perform better in the class.
- Discussion 1 : Dynamic Programming. Don't worry (yet) about how to present a solution to these; focus on solving them. We will discuss presentation later.
- Discussion 2 covers more dynamic programming and some complexity proofs.
- Discussion 3 covers more dynamic programming and some complexity proofs.
- Discussion 4 covers more dynamic programming and some complexity proofs.
- Discussion 5 covers exam solutions.
- Discussion 6 covers exact (correct) greedy algorithms.
- Discussion 7 covers approximation greedy algorithms.
- Discussion 8 covers divide and conquer algorithms.
- Discussion 9 also covers divide and conquer algorithms.
Annotated Slides
These are the annotated slides from my lectures. Note that I do not provide the blanks in advance; this is for a very good reason. In the past, I discovered that when I post un-annotated slides in advance, students write down only what I write on the board. My writing on these is not the lecture, but rather goes along with the lectures. Accordingly, I suggest using the handouts (above) while following lecture, and the annotated slides to double-check or refer back. If you miss a lecture, I suggest getting notes from a classmate and discuss those notes with them, rather than relying on these posted slides.
Units 3 and 4
This section is slides that start in week six.
- Lecture 10: Introduction to Greedy. In this lecture, we saw two problems which admit a greedy optimal solution and demonstrated the correctness of them. The first was a packing problem. You will see a covering problem in lab on Friday.
- Lecture 11 : Greedy, part 2. We saw two problems with a greedy optimal solution, the fractional knapsack problem and scheduling with deadlines.
- Lecture 12 : Greedy, Part 3. We begin approximation algorithms with TSP.
- Lecture 13 : Greedy, Part 4. We finish approximation algorithms with Vertex Cover and load balancing.
- Lecture 14 : Divide and Conquer, Part 1. We introduce the paradigm and the Master Theorem.
- Lecture 15 : Divide and Conquer, Part 2. We cover selection algorithms and introduce multiplication algorithms.
- Lecture 16 : Divide and Conquer, Part 3. We cover multiplication algorithms and the minima set problem.
- Midterm Review : slides from Monday June 5's midterm review session.
Units 1 and 2
This section is slides that predated the first exam:
- Lecture 1 : covering the famous problem. We also discussed the syllabus, although I did not annotate those slides.
- Lecture 2 : Longest Common Subsequence and Subset Sum. I recommend as reinforcement you walk through the algorithms by filling in the tables on the handouts until you can visualize what the algorithm is doing. Then, try to write code to retrieve the actual LCS or the subset that adds to T at the end of each. Discuss this with your study group.
- Lecture 3 : covering Edit Distance and Bellman-Ford (single-destination shortest path, with negative edge costs). Coming soon: a writeup of the former, as if it were a homework question response.
- Lecture 4 : introducing complexity. As preparation for next lecture, determine how large the graphs used in the reductions are, in terms of n, the number of variables in 3-SAT instance, and k, the number of clauses in the 3-SAT instance.
- Lecture 5 : complexity 2. This continues the coverage of computational complexity and begins introducing how we cope with complexity. Next lecture, we'll discuss what sorts of problems are easy or hard for a computer.
- Lecture 6 begins to tie together what we saw the first several lectures, discussing problems that are easy (for a computer -- this doesn't mean you should be able to write code for all of these off the top of your head) and hard (for a computer -- you probably can write code for several of these, some in maybe a dozen lines of code, but don't expect the running time to be any good).
- Lecture 7 proves Subset Sum is NP-complete and uses this as a lead-in to our first conversation about coping with complexity.
- Lecture 8 ties the two core topics of the first half of the class together; we see an algorithm for Knapsack that can be customized for a time/accuracy trade-off.
- Midterm Review : slides from Monday May 1's midterm review session. This covers the two diagnostic exams, below. More complete solutions are posted on EdDiscussion, under "resources."
Problem Sets:
While we will not be collecting these this quarter, we strongly encourage you to do these problems as practice for the exams.
- Problem Set 0 covers prerequisite material and is good practice to get you prepared for CompSci 260P.
- Problem Set 1 covers dynamic programming. The problems on this set cover a variety of levels of understanding of the topic. Projects 2 and 3 will involve the implementation side of this, while this problem set covers the concept.
- Problem Set 2 covers computational complexity.
- Supplemental to PSets 1 and 2 : this document is the Edit Distance problem from lecture and the proof that Independent Set is NP-complete, also from lecture, written as if they were homework submissions (or exam answers). A document with just the submission and a document with one with commentary also is available.
- Problem Set 3 covers greedy algorithms.
- Supplemental to PSet 3: this document covers greedy algorithms from lectures on May 8 and 10, written as if they were homework submissions (or exam answers).
- Problem Set 4 covers Divide and Conquer algorithms.
Programming Projects:
First, please read the CompSci 260P Lab Manual.
If you are submitting late (within the period allowed), or otherwise do not want your last commit pushed prior to the deadline to be graded, please use this form. You will need to be signed in to your UCI account to access this. Projects other than project 0 are eligible to be submitted up to 48 hours late, as described in the lab manual.
- Project 0 is primarily about getting to know the VM and will also help assess your readiness for the course. It is due on April 10.
- Project 1 is a review of graph fundamentals. It is due on April 17, although your first 24 late hours are free (there is still a limit of 48 total, including the 24 free ones).
- Project 2 is the first dynamic programming project. It is due April 24, and can be submitted up to 48 hours late. Submitting at any time after April 24 at 6pm requires filling out the form, above.
- Project 3 is the second dynamic programming project. It is due May 1, and can be submitted up to 48 hours late. Note that the first exam is 48.5 hours after the due time. Submitting at any time after May 1 at 6pm requires filling out the form, above.
- Project 4 relates to approximation algorithms and experimental analysis of the same. This is due on May 24, and can be submitted up to 48 hours late. This is later than the due time listed in the syllabus.
- Project 5 relates to divide and conquer algorithms and experimental analysis of the same. This is due very late, June 9 -- that's the latest I can make it due.
Exams:
As the exams get closer, I will post diagnostic exams here, which will enable you to practice some key skills you will need for the tests. In the meantime, I encourage you to work on the practice set questions.
To get the most out of a diagnostic exam, take it in exam-like circumstances, such as in a quiet area in the library. Set a timer so you know if you can accomplish the exam in the allowed time.
- Exam 1; there are two diagnostic exams. To print these in exam format, print double-sided and staple. I will provide printed copies in lecture on April 26 and I will discuss the solutions and strategies for the test in class on May 1; around then, I will also post solutions on Ed Discussion.
- Exam 2; there are two diagnostic exams. To print these in exam format, print double-sided and staple. I will provide printed copies in lecture on May 31 and I will discuss the solutions and strategies for the test in class on June 5; around then, I will also post solutions on Ed Discussion.