PAGE UNDERGOING MODIFICATIONS
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
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.
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.
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
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.
We may supplement the main text with additional material given
The midterm will take place during class time
on Monday, October 28.
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
|Sample Exam Problems
The course will be organized around
sample exam problems.
Homework will be assigned roughly weekly, less often around holidays
I expect roughly six or seven assignments.
Homework #1, due September ???: ???
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:
Migrating to Beamer/LaTeX PDF files:
September 23 (note to
self: these slides
still in progress, and may vary for the next few days...).
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.
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
Sept 4, SM
(this is a terrific model/example, and is far above the 1 out of 1 threshold).
Sept 4, KW
Sept 9, VG
Sept 11, KL
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,
October 9 - November 5, we will let you take two scribe assignments
from November 6 to November 31.
Suggestions Regarding Scribe Assignments
- 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.
- 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.
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).
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.