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 problem sets and programming assignments.
Students enrolled should also have access to the course Canvas page, which will be used sparingly, and an EdDiscussion board, which will be used frequently.
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.
- Lecture 7-8 handout covers more about complexity.
- Lecture 9 covers minimum spanning trees. This lecture is Friday, October 21, to make room for the exam review on Monday the 24th.
- Lectures 10-12 handout covers greedy algorithms and their proofs, both for exact algorithms and for approximations.
- Lectures 13-15 handout covers Divide and Conquer algorithms. Lecture 15 is now included.
- Lectures 16-17 covers linear programming. Also included are lab questions towards the lab on 11/28.
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 covers dynamic programming.
- Discussion 2 covers dynamic programming and some NP-complete problems.
- Discussion 3 also covers dynamic programming and complexity.
- Discussion 4 covers that too, and is held in conjunction with the review session on Monday the 24th.
- Discussion 5 was used for Lecture 9, with a review session replacing the regularly scheduled lecture nine.
- Discussion 6 covers correct greedy algorithms.
- Discussion 7 would have been on November 11.
- Discussion 7? covers greedy approximation algorithms.
Problem Sets:
- Problem Set 1 covers dynamic programming and is due October 12.
- Problem Set 2 covers complexity and is due October 24.
- Problem Set 3 covers greedy algorithms (exact and approximate) and is due November 14. Note that this due date is five days later than originally planned.
- Problem Set 4 is in the lecture handouts for linear programming and will not be collected this quarter.
Programming Projects:
First, please read the CompSci 260P Lab Manual.
- Project 0 is about getting to know the VM. It is due Monday October 3.
- Project 1 is about dynamic programming and is due Monday October 17.
- Project 2 is about the dynamic programming TSP and is due Wednesday October 26.
- Project 3 is about an approximation algorithm for TSP and is due November 16. Note that you must push code AND submit your report to GradeScope.
- Project 4 is about an experimental evaluation of trade-offs within Divide and Conquer algorithms. It is due on Friday of week 10 at the last minute of the day. Note that you must push code AND submit your report to GradeScope.
Exams:
- Diagnostic Exam 1. I encourage you to take this in as close to exam-like circumstances as you can, and do so prior to lecture time on Monday October 24. This will allow you to evaluate how well prepared you are for the real first exam on Wednesday October 26, and to get the most out of the review session on Monday.
- Diagnostic Exam 2A. I encourage you to take this in as close to exam-like circumstances as you can.
- Diagnostic Exam 2B. I encourage you to take this in as close to exam-like circumstances as you can.