Computer Science 789 Randomized Online Algorithms
Fall 2003
Final Examination Page
Most recent update: December 9, 2003.
-
Handouts:
-
Thursday, December 11, 2003.
Final Examination, 6:00 PM to 8:00 PM.
-
You may discuss the problems with anyone before the exam. You may bring
books or notes of any kind to the exam. During the exam, you may not
discuss the problems with anyone, and you must write
the solutions in your own handwriting during the time alloted.
-
The exam itself will consist of the following problems:
-
Excercise 4 from the server problem handout.
-
Professor Bifid's problem.
-
Work Exercises 14, 17 and 20 in the work function
handout, but only one fourth of each, namely the part that deals
with Action 21, the action when the request is to page
a from the
knowledge state Gb,c,d,e,f.
-
A problem involving HARMONIC in a specific space,
namely the triangle whose sides are 1,2,2.
-
The first two problems are easy, but in different ways.
The third problem is harder, but we've done a similar one in class.
The last problem is even harder, and you should devote a substantial amount
of effort to working it out in advance. I will be available by email,
if not in my office, up until the morning of the final exam. (Do not count
on finding me on the afternoon of the final exam.)
-
I will meet Dr. Bein and he will help me decide what clues I should post
on the test problems.
Current version of the hints.
Part of what you learn doing research is that the hardness of problems
that arise naturally (as opposed to problems made up by a professor for
students) is not balanced, and that figuring out which ones are easy, which
are very hard, and which are in between, is part of the job.
So, here's a clue: the hardness levels of the various parts of the
fourth problem are very different.
But none are in the realm of
really hard.
-
Read the metrical task system page.
-
After discussion with Dr. Bein, I have provided you with a partial
answer to Problem 6, namely the
graph showing the knowledge states.
For discussion of the graph, read the hints page.
The final version of this file is now available, dated
Tue Dec 9 03:12:49 PST 2003.
The error in the graph has been fixed.
But there was still an error up until
Mon Dec 8 07:47:13 PST 2003 becuase I failed to update the eps file.
(You will excuse my mistake, as this is the very first
time I have done anything with xfig.)
-
A major error in the work function handout
was discovered by Qin Zhang.
The corrected version is only very slightly
different. The error was revealed trying to work the third problem
on the final exam.

Back to
Course Page