CS515, Fall 2011
From Theoretical Computer Science Courses at Oregon State University
This course will cover the most powerful, broadly useful design techniques for algorithms and prepare you for the advanced algorithms classes (523 and 529) and life in general (as a computer scientist). There is no formal textbook for this course; we will be using Jeff Erickson's comprehensive lecture notes and other freely available materials. If you find any errors in Prof. Erickson's materials, please let me know (I will keep track of these over the quarter and award bonus points accordingly).
A major goal of this course is to teach you to solve algorithmic problems with a particular emphasis on communicating solutions (oral and written).
|Lecturer||Professor Borradaile||Wednesday 1-2PM||KEC 3071|
|Teaching Assistants|| Anna Harutyunyan||Monday and Wednesday 2-3.30 PM||Atrium|
This schedule is tentative and subject to change.
| Stable matching.|
Intro notes, including stable matching (in more depth)
| Divide and conquer.|
|Problem solving session 1: divide and conquer.||Greedy algorithms.|
|Problem solving session 2: greedy algorithms.|| Matroids.|
|Problem solving session 3: matroids.||Dynamic programming (I).|
| Test 1 (divide & conquer, greedy, matroids). |
(Prof. B out of town Monday and Tuesday.)
|Dynamic programming (II).|
Oct 31-Nov 4
|Problem solving session 4: dynamic programming.|| Randomized algorithms.|
| 7 |
| Problem solving session 5: randomized algorithms.|
If your group number is odd, solve the odd questions, if your group number is even, solve the even questions.
| Network flow (I).|
|Test 2 (dynamic programming and randomized algorithms).||Network flow (II).|
|Problem solving session 6: network flow.||Thanksgiving - no class|
Nov 28-Dec 2
| Linear programming.|
The simplex algorithm.
| Problem solving session 7: linear programming.|
(Note: there will be no written solutions submitted for this session, but questions of this type are "fair game" for the final test.
| 11 |
|Friday December 9 @ 9.30 AM: Test 3 (network flow and linear programming).|
Your grade will be determined as follows:
|Problem solving sessions||36% (6% each)|
|Tests||60% (20% each)|
Your grades indexed by code are available here. Your code is generated by multiplying the middle three digits of your OSU ID number by the last three digits of your OSU ID number.
Problem solving sessions
There will be no assignments in the traditional sense. Rather, you will be working much harder. Roughly every week, there will be a problem solving session, organized as follows:
- Students are broken up in to groups of 2-4 (assigned randomly for each problem solving session).
- Each group will prepare solutions to 2 assigned questions before the problem solving session.
- At the problem solving session I will flag one problem for each group and groups will be paired up to teach and challenge:
- Suppose groups A and B are paired. Group A will teach the solution to their flagged problem to Group B. Group B will challenge A to make sure that the answer is correct, going over the details and make sure they understand the solution completely. Group B will not take any written material from Group A, but may make their own notes. Groups A and B swap roles and repeat the process with B's flagged problem. It is the challenger's responsibility to make sure that the solution is correct. The challenger, in discussing the problem, may see a simpler solution. The best solution is what should be taken to the next phase.
- Each group presents the solution that they were taught to the me, the TA and/or the class (depending on time). They will be graded on this presented solution. Group A's grade is determined by both their presentation and the presentation of their flagged problem by Group B.
- Each group, using any feedback from the challenge or the presentation, must hand in a typeset solution to the problem they were taught before the start of the next class. See the guidelines for written assignments. These solutions will be posted online to act as a study repository for the midterm and final - perhaps with a round of editing by the TA(s). Print this solution and turn in at the beginning of the next class.
Frequently asked questions
What if Group A couldn't get a solution to our problem before class?
- Try to work out the solution with Group B. Partial solutions will garner partial marks. Group B may be able to help turn your partial solution into a full solution.
What if Group A didn't even get a partial solution to the problem selected for the teaching round?
- Too bad! Group A will not participate as a teacher. Group A can still participate as a challenger but can earn at most 50% for this round. Group B's grade will be determined solely by Group A's presentation and can still earn full points. Your lowest problem solving session grade will be dropped. You should still attend the session. Seeing the solutions to all the problems will (hopefully) be very useful for the midterm and exam.
What if member X of Group A cannot (or does not) help prepare solutions?
- Member X may still participate as a challenger to Group B and earn up to 50% for the session. The rest of Group A can still earn full points.
What if member X cannot attend the problem solving session?
- Member X will get 0 for this session. Your lowest problem solving session grade will be dropped.