CPSC 500-101 Page, Fall 2013

This course gives a self-contained introduction to algorithms. Our course often follow the text Algorithms, by Dasgupta, Papadimitriou, and Vazirani. There is a currently free online PDF version of the text, although you may prefer to purchase a hard copy from the UBC Bookstore.

The course is self-contained, i.e., all formal concepts will be developed "from scratch." We will assume some familiarity with algorithms at the undergraduate level.

News September 9, 2013: We have not formally defined Turing Machines or RAMs. Wikipedia has good introductory articles, but there are many variants in the definition of TMs and RAMs. We may glance at a formal definition of a RAM, but this will probably be of little use; the idea is to look at enough algorithms until we have a good idea of which TIME and SPACE resources a RAM will take.
Class Meetings We will meet 9:30-10:50am in Dempster 101, Mondays and Wednesdays; the first class is Wednesday, September 4, 2013; class will not be held on September 18, during the West Coast National Event of the Truth and Reconciliation Committee (during which you are encouraged to participate), which is free and will take place at the PNE (where the 50-year-olds go to hear Heart and REO Speedwagon for a $12 entry fee) , see TRC FAQ for more info; the university is closed on October 14, Thanksgiving, and November 11, Remembrance Day; the last day of UBC classes is November 29, hence our last meeting will be November 27.
Other Materials We may supplement the main text with additional material given here.
Midterm The midterm will take place during class time on Monday, October 28.
Office Hours Office hours will be given by appointment, as long as this is feasible. When things get too busy, I will give office hours by fixed hours which I will post (this will always happen just before an exam).
Sample Exam Problems The course will be organized around sample exam problems.
Homework Homework will be assigned roughly weekly, less often around holidays and exams. I expect roughly six or seven assignments.
Homework #1, due September ???: ???
Slides At times I will make skeletal slides of an upcoming lecture, mostly as notes to myself (i.e., I might write a lot about something not so important, and merely refer to the text for very important stuff). I am happy to share these slides with you, although posted scribe assignment will give you a more even representation of the content of the lecture and time spent on various topics.

My slides exist for: September 9; September 11.

Migrating to Beamer/LaTeX PDF files: September 16. September 23 (note to self: these slides still in progress, and may vary for the next few days...).
Scribe Assignment You will sign up to write notes on what was covered in two classes; your notes will be posted on this webpage. You will be required to add some of your own material, including an introductory paragraph and a concluding paragraph, and some material or example not covered in class. Each of your two scribe assignments will be worth roughly 10% of the grade. Monday scribed classes should be emailed by Friday at noon; Wednesday scribed classes by Monday noon. The quality of your scribe assignment should be comparable to that of an above-average extended-abstract submitted to a CS theory conference.
Scribed Classes You may write in any laguage you like, but you should email me (jf at cs dot ubc etc.) a PDF attachment. Your submission will be posted here; you may make revisions that I suggest, within a week of receiving such suggested revisions, for a higher grade. Grades will be given in the real interval [0,1] (e.g. 0.75, 1.00, 0.33). A grade of 1 out of 1 requires no further revision and is the maximum score.

Sept 4, SM (this is a terrific model/example, and is far above the 1 out of 1 threshold).

Additional scribes: Sept 4, KW Sept 9, VG Sept 11, KL
Scribe Schedule You should do one scribe assignment from September 1 to October 15, and another one October 16 to November 30. We have passed around a list of dates, and you have put your initials on one date. This is not set in stone, for if you are ill then you cannot be expected to come to class and be a scribe. Hence, at the start of each class, I will ask for scribes; if your initials are on today's date, you have priority over the others. If someone is very eager to be a scribe on your date, then you can elect to be a scribe on a later date, and let them have your turn. If you have placed your initials next to October 9, and you are ill from, say, October 9 - November 5, we will let you take two scribe assignments from November 6 to November 31.
Suggestions Regarding Scribe Assignments
  1. Scribe assignments are not required to list matters discussed in chronological order; in fact, at times they can be dramatically improved by rearranging the order. Consider the reader and the flow of the exposition. For example, you might gather all the administrative matters at the beginning.
  2. Make sure you have a great opening sentence and opening paragraph. After you have finished the assignment, wait an hour (or so) and reread your opening paragraph, perhaps aloud if circumstances permit; make sure that you can understand what you have written, and that you cannot substantially improve your opening paragraph. If you have any doubt, read your opening paragraph to a friend who can offer gentle constructive criticism. For some competitive conferences, the opening paragraph is your main--if not only--opportunity to impress the reader.
Overview A course overview, including grading policies, will be given here. The course grade will be
.10 max(h,m,f) + .20 s + .25 max(m,f) + .45 f,
where h,s,m,f are, respectively, the grade on the homework, scribe assignment, midterm, and final exam (respectively).
Grade Accomodation If your grade as computed above falls below the grade required for Theory Breadth, you may raise it to the minimum grade needed to obtain Theory Breadth provided that you (1) meet me at least three times, each for at least three minutes, to discuss a detail of this course that you find difficult; (2) prepare a supplementary article on some aspect of algorithms related to your interests (whose topic is subject to my approval); and (3) you give the class a three minute presentation on your article.

UBC Math Home| Joel Friedman Home| Course Materials