- Friday October 25: Diane's lecture today
-
I decided not to cover the proof of correctness for binary search.
Instead, we discussed stacks and queues (see lecture slides 266 and 276)
and ADTs and abstraction in general.
- Friday October 25: Assnt 2 -- Suggestion
-
Don't let Part A of the assignment hold you up.
Ideally, you'd have
a well-thought-out ADT definition before proceeding.
As you went on to develop the program,
you'd probably discover some shortcomings in the ADT definition,
and go back to modify it.
But if you are really stuck on the ADT, move on to the program.
(And come to office hours next week to get some help with the ADT!)
- Friday October 25: Assnt 2 -- building the board
-
In the hints for the assignment, we gave some suggestions for how to
write the code for creating a random board.
This is one of the trickiest bits of code in the assignment.
If you're finding it hard, here's a way to tackle it in small,
incremental steps:
- Forget your data structure for this assignment for a moment.
Write code to create a linked list of 100 strings, each containing
the value "hi".
This should not take 100 (or 200, or 300) lines!
- Modify this so that it creates a circular, doubly-linked list
of tiles.
- Make that a subprogram.
- Call it five times and store five pointers to the fronts of the five lists.
- Now write a subprogram to link any two given rows together vertically.
- Put the whole thing together to build your board.
- Friday October 25: ADT help
-
The information I said I'd post to help you with your ADT definition
(see Wednesday's announcements below)
is now available.
Click here.
- Thursday October 24: Assnt 2 -- var tPtr in displayBoard
-
In the code that we provided for the assignment, procedure displayBoard
includes a declaration:
var tPtr := board
This line shouldn't be here -- just delete it.
(It is a leftover from an old version of the procedure.)
- Wednesday October 23: Concerned about your marks?
-
If you disagree with or are confused about your midterm or A1 mark,
click here to find out what you should do.
You must address any concerns regarding these marks by
Friday 01 November.
If you want to discuss how you're doing in the course -- perhaps to get
some advice about how to do better, or to help decide whether or not
to drop the course -- please see Diane, or your own instructor in office hours.
- Wednesday October 23: Assignment 2 -- Abstraction and ADTs
-
Many students are confused about part A of the assignment, in which
you are to define an ADT.
Click here for some help with this.
- Wednesday October 23: Office hour changes
-
Diane's office hour on Thursday at 3:00 will be held one hour earlier,
from 2:00-3:00.
Her evening hour will go ahead as usual, at 5:30.
- Wednesday October 23: Lectures friday?
-
Both the Borodin/Cook and the Horton sections of 148 will have
lectures this friday.
Some students may not be able to attend due to the Days of Action.
This is what will be covered:
- Borodin/Cook: a review of the concept of an ADT, and more
examples regarding proof of correctness
- Horton: the proof of correctness for binary search
(slides 152-170). I probably will not complete all of this on Friday.
My class is behind schedule. To help catch up, I may use next
week's tutorial slot for a lecture, held in the lecture hall.
Check here beforehand for an announcement about this.
- Wednesday October 23: Problems viewing the diagram?
-
The diagram posted on Monday is in a format called "postscript".
If you view it using netscape on the cdf PCs, netscape will
automatically pop up a postscript viewer window, which displays the
diagram.
To view it from your own computer, you need to have a postscript
viewer installed.
Here are some instructions (from our system administrator)
on how to install one:
Obtain and install GhostScript and GhostView for your platform
from:
http://www.cs.wisc.edu/~ghost/index.html
Then configure your browser to use the viewer that you just installed.
(In our version of Netscape, you do this using
Options | Preferences | HelperApps.)
- Wednesday October 23: Assignment 2 -- Testing and randomness
-
Question:
I've run into a bit of problem with capturing the output of the game
for my annotated test runs.
Re-directing the output to a file poses a problem because
you have to see what tiles you're
dealing with before you can decide on the right input.
Answer:
I think the easiest way to get around this problem is
to make your program capable of reading in a configuration
for the initial board from some input file.
That way, when producing test runs
you could pick the exact board you want to start with.
- Wednesday October 23: Assignment 2 -- Uniform distribution
-
Question:
The handout says that there should be "a uniform distribution
among the 3 (this should say 4) tile types and their
various rotations".
This is a little ambiguous; is the distribution uniform among
the 16 combinations of tile type and rotation,
or among the 11 distinguishable combinations?
Answer:
I will accept either approach as correct.
Fyi,
the procedure we provided for generating a random tile
uses a uniform distribution among the 11.
- Wednesday October 23: Assignment 2 -- Using more than 1 module
-
Question:
I would like to use one module for tiles, and another
to deal with tile positions, prizes, and
player pieces. This requires me to export a tile type
from the tile module; I have chosen to
export it opaque, so that finding out the details about a tile
requires one to call procedures exported by the Tile
module. Is any of this Bad Programming Style?
Answer:
Your instinct for breaking things down into smaller modules is very good.
It is perfectly fine to do so, and yes, you should export the tile type
opaque.
This is analogous to the Car and Stud modules in assignment 1;
we had to export carType and studentType so that the simulate module
could create multiple cars and students.
Exporting a type isn't ideal;
it would be better to hide everything about it inside the module.
But with modules, there is no solution other than export opaque.
(This is precisely why we said it was fine to use only one module
in your program.)
Later, when we learn classes, we'll see a way to allow multiple instances
of a type while still hiding the type.
Question:
If I do use more than one module to handle the game data, do I
need to provide the module signature for this module, as well as the
signature of the main module?
Answer:
Yes.
- Monday 21 October: Assignment 2 -- what the data structure looks like
-
Click here for a (simplified) diagram of the
board data structure.
It is simplified in that it does not show the wrap-around pointers that
make the rows and columns into circular linked lists.
Also, the diagram shows a single pointer into the data structure.
As the hints indicate, this is just one of many choices for how you
to get at the data structure.
- Monday 21 October: Tutorial this week
-
Your tutor will be referring to the slides on bubblesort (slides 193 onwards).
You will get more out of this week's tutorial if you make sure you're
familiar with how bubblesort works -- just the algorithm and/or code.