CS 2ME3: Software Design I
Winter 2007
- Instructor: Michael Soltys, email:
my last name at mcmaster.ca
- Course Information
- Lectures: M,W 11:30-12:20, and F 13:30-14:20,
in BSB/340.
- Course outline:
Algorithm design and correctness techniques, and implementation using
Java.
- Textbook:
There is one required textbook:
- Algorithm Design
by Jon Kleinberg and Eva Tardos
Addison Wesley, ISBN: 0321295358.
- Please Read:
McMaster Academic Integrity Statement.
- Previous versions of this course:
2004,
2005,
2006.
- WebCT
Announcements:
- Mar 27: For question 3 of part B, Assignment 3, you must assume
that the cache is of size k.
- Mar 21: A detailed description of the CLOCK paging
algorithm: imagine the cache as a circle, that is, the cells are in
order 1,2,3,...,k, and after k comes 1 again. There is
a pointer to cell i, and each cell has a flag associated with
it, which is 0 or 1. When a request for a page comes, and the page is
in the cache, its flag is turned to 1 (and if it was 1 already, it is
not changed). If there is a page fault, we move the pointer clockwise
until we find a 0-flag. On the way there, we turn all the 1-flags
into 0-flags. When we find a 0-flag, we evict the corresponding page,
and put the new page in its place, and set its flag to 1.
How is CLOCK related to LRU? In LRU we
replace the page whose most recent request was the earliest. The flag
in CLOCK works as an approximation to the time of last access
of LRU.
- Mar 21: For the last assignment, your Java program has to output
Java charts of the performance of the different online algorithms. If
you are having trouble displaying the charts directly, you can
also do it as follows: make your program output a text file
charts.java
(Click here for an example from problem
set 2 from the year 2004; this is a file Coordinates.java that was
supposed to draw a tree representation of an algebraic formula.)
Then, do the command
javac charts.java
to convert this file to
charts.class
Finally, you can display charts.class with an appletviewer. (To
continue with our example, click here,
to see the result of "drawing" the file Coordinates.java.)
- Mar 9: Today in class we did an example of the CYK algorithm on
the palindrome 01011010, but we failed to get an S in the upper-right
corner. The reason is that the grammar that we were working with,
while in Chmosky Normal Form, is actually not the correct
grammar for the language of palindromes. The original palindromes
grammar was
S-->e|0|1|0S0|1S1
and we claimed that the corresponding Chomsky Normal Form grammar was:
S-->e|0|1
X-->1
Y-->0
S-->XU|YV
U-->SX
V-->SY
and this isn't the correct translation! (The problem is the S-->e
rule; since we did not present the Chomsky Normal Form translation in
this course, it is not in the scope of the course to explain what the
problem is; and you are of course not responsible for this material.)
So we did a correct run of the algorithm for the above grammar,
and we did not get an S in the upper-left corner because the string
01011010 is not in the language of this grammar. On the other
hand, the string 010 is in the language of this grammar and you can
see that its table is:
S,Y U S
S,X V
S,Y
- Mar 5: Assignment 3 (the last assignment) has been posted below.
- Mar 4: The midterm with solutions has been posted below.
- Feb 27: The solutions to problem set 2 have been posted below.
- Feb 14: The university is closed until noon today (due to the
weather), so today's class is canceled.
- Feb 12: The solutions to assignment 1 have been posted below.
- Feb 5: TA office hours: Wednesdays, BSB/B139, 1:30-2:20.
(The TA is Bill (Rongshu) Yi.)
- Feb 3: Assignment 2 (due on Feb 26) has been posted below.
- Feb 3: Midterm: Friday March 2nd, 1:30-2:30 (usual lecture
time, and usual lecture room). The midterm will cover the
preliminary material (handed out as Chapter 1), Greedy Programs
(handed out as Chapter 2), and Dynamic Programming (which will be
handed out as Chapter 3--we are going to start Dynamic Programming on
Monday Feb 5th).
- Feb 3: My new office hours will be Fridays 2:30-3:30 (right after
the lecture; my office is ITB-214). Please feel free to make
appointments for other times and to ask questions by email.
- Feb 1: For part 1 of the assignment, if you are having trouble
setting euclid up to take input in the form of "euclid m n", it is
acceptable to instead ask for inputs in the form "enter m:" and "enter
n:".
- Jan 13: Problem Set 1 has been posted below.
- Jan 12: WebCT is now set
up (but there is nothing there yet; we'll use WebCT for program
submission).
- Jan 10: Here is the corrected versiono of one of the programs
given in class today:
x <-- m
y <-- n
z <-- 0
while (x != 0)
if (rem(x,2) = 1)
z <-- z+y
end if
x <-- div(x,2)
y <-- 2y
end while
return z
Notes, Assignments, and Tests: