This is the home page for the course CS 32: Puzzles, Games and Algorithms:
Introductory computer science through exploration and analysis of
mathematical puzzles and games, and the algorithms that handle them;
offered by the
Department of Computer Science
at the
University of Vermont,
Fall 2007.
(N.B., the content of this page changes frequently.)
General Information:
- Instructor:
Robert R. Snapp
(e-mail).
-
Office Hours:
Tues. 1:30 – 3:00 p.m., Wed. 3:30-4:30 p.m., Fri. 9:30 - 11:00 a.m.,
and by appointment.
- Lectures on Monday, Wednesday and Friday, in Room 367 Votey,
11:15 a.m. – 12:05 p.m.
- Lab Instructor: Paul Haake (e-mail)
- Lab Sections meet in room 206 Votey:
- Wednesdays, 4:40 – 6:30 p.m.
- Thursdays, 6:30 – 8:20 p.m.
- Fridays, 2:30 – 4:20 p.m.
- Pop quizzes can occur on any day!
- Field trip: Saturday, Sept. 29, 9:30 a.m. – 4:30 p.m.. (Rain Date: Sat., Oct. 13).
The bus will leave at 9:30 a.m. If you are driving to the Great Vermont Corn Maze,
please download and print these directions.
Please return a completed field-trip form by
12 noon, Friday, Sept. 28, 2007
(photos).
- Midterm Exams (in class): Friday, Oct. 12, 2007 and Friday, Nov. 16, 2007.
Click here to download the extra credit study questions, due 11/16/07.
- Final Exam: 3:30 – 6:30 p.m., Friday., December 7, 2007.
Required Materials:
- Access to a computer with drscheme, which can be downloaded for free from
www.drscheme.org.
(Each student will be given a computer
account that will enable use of drscheme on most of the public computers in the Votey building. However, ready access to your own computer is recommended.)
- Two (or more) six-sided dice.
- Fifty to one-hundred counters (e.g., pennies, buttons, poker chips,
M&Ms).
- Rubik's cube (usually available at
Vermont Toy and Hobby (Essex and South Burlington), Barnes and Noble (102 Dorset St., South Burlington), Hessport's Rubik's Shop, or amazon.com
Recommended Materials:
One or more of the following will enrich your course experience.
Many of the following puzzles and games can be constructed from inexpensive materiels (paper, cardboard, pencils, and counters).
- chess game.
- go game.
- mancala game.
- peg solitaire.
- 15 (sliding piece) puzzle.
- Tower of Hanoi puzzle.
- Chinese Rings.
- A standard deck of 52 playing cards.
Assigned Reading:
Texts will be assigned during the semester and either distributed in class or placed on reserve in the Bailey-Howe Library.
- By 08/29/07, please read Chapter 1 of Johan Huizinga's Homo Ludens.
- By 08/31/07, please read Chapters 1 and 2 of Roger Caillois's,
Man, Play and Games.
- By 09/05/07, please read E. B. Tylor's "The history of games,"
and study Pieter Bruegel's Kinderspiele, (1560)
[small-jpeg (315KB),
large-jpeg (10MB)].
The book, Edward Snow, Inside Bruegel, North Point Press, New York,
1997, discusses Kinderspiele in great detail. It is on reserve at
the Bailey-Howe Library.
- By 09/21/07 please read the short story "The Garden of Forking Paths"
by Jorge Luis Borges.
Homework Assignments:
Each homework assignment usually consists of written assignments and
programming projects.
- Homework 1: From which puzzle or game do you derive the most fun?
Please write a short essay (between 400 and 600 words, excluding the bibliography,
quotations, and footnotes) that briefly describes this puzzle or game, and
explains why you personally enjoy it. Due, Wednesday, September 5, 2007.
Additional guidelines were distributed on a handout in class on August 31.
- Homework 2:
A lipogram is a manuscript that omits words that contain a particular symbol or a particular group of symbols. Your task is to draft and mail a lipogram to your family, or to a pal, which omits our fifth and most common symbol,
that which follows d. Your communication should contain 300 words, and should discuss an unusual action or thing that you saw this month in
class or on campus. Your writing should scan naturally. Avoid
faulty grammar, bad punctuation, obfuscations, and word malformations. By 9/12/2007 you should mail
your original lipogram to your family or compatriot, and submit a copy to your instructor.
Thus, you should not discuss any information that you would not want to broadcast in public. (If you wish, you may transmit your lipogram using a mail program
on your Macintosh or PC, as long as you mail a carbon copy to your instructor.
You may put symbols that follow d in your "To:," "From:,"
and "CC:" locations.)
- Homework 3: Please identify every reference to mazes and labyrinths
in Borges's "The Garden of Forking Paths," and study in particular Dr. Stephen Albert's description of the lost labyrinth of Ts'ui Pen. Then please write a 1000 to 1500 word essay (not including quotations) that describes the various roles that mazes and labyrinths (and the humans that walk through them) play in this story. Is the story itself a maze or labyrinth? Alternatively, you may explore another topic that relates this story to the subject of our course.
- Create an appropriate title. (It is usually easier to do this after having
finished the bulk of the paper.)
- Your paper should begin with an introductory paragraph that contains an original, thoughtful, and well-defined thesis statement. The introductory paragraph should at least hint how the body of the paper supports the thesis, and how the paper is organized.
- The main body of your paper should consist of several paragraphs that present evidence in support of your thesis statement. Each paragraph should contain a topic sentence, which somehow relates to your thesis, as well as at least one reference, or quotation, from the short story, or other sources.
- Your paper should conclude with a paragraph that restates and develops your thesis just a bit further, using the evidence you provide in the body of your essay. You may wish to use this last paragraph to speculate beyond your thesis.
- If your paper refers to secondary sources, you should list these in
a bibliography, as in Homework 1.
- After completing the above, please polish your work. Check spelling, grammar, and punctuation. Omit needless words. Adopt lively verbs.
Avoid repetitive language, and vary your sentence structure.
This assignment is due by Friday, September 28, 2007.
- Homework 4: Design a maze on a standard sheet of paper that contains at least 16 junctions.
Assign a unique label to the entrance, goal, and each junction and dead end. Construct the equivalent
graph (using labeled dots and lines), and finally describe the topology of your maze using a nested
list, as we did in class on Monday, Oct. 15. Bring all of the above to your lab session this week.
Handouts:
Most handouts are availabe in pdf format, a page description language
supported by Adobe Acrobat. If you do not have Acrobat Reader for your
personal computer, you can
download it for free from Adobe.
- syllabus [pdf] (4 pages).
- UVM's New Code of Academic Integrity [pdf] (10 pages).
- A word jumble program: jumble.scm
and a modest dictionary file with 25,143 common words
- jumble2005.scm is an improved version
of jumble that looks for a word file in several places. You must set
the Language of drscheme to MzScheme (or better) to use it.
And web2 is a larger dictionary that contains
234,937 words, and
words_big_lower.txt
converts the former using only lower-case characters.
- Scheme programs that count: factorial.scm
and binomial.scm
- A scheme program that generates random sentences:
madlibs.scm
- The maze at Hampton Court: pdf
- Solving a maze by a random walk:
randomsearch.scm (see also the scheme
program that we wrote together in class on Monday,
October 15, 2007);
and by Trémaux's algorithm tremaux2.scm.
- Coxeter's garden maze [pdf],
from Ball and Coxeter, Mathetmatical Recreations and Essays, 13th Edition,
Dover, Mineola, New York, 1987, p.259.
- Expected winnings at video stud poker:
poker.scm
- A scheme implementation of random dice:
dice.scm
- Some homemade random number generators:
rand.scm
- Functions that use cons to clone lists, etc.
clone.scm
- The scheme function search threads a maze:
graphsearch.scm. Refer to the
maze in
Ball and Coxeter, and its equivalent
graph.
- A scheme implementation of the Tower of Hanoi:
hanoi.scm
- Scheme functions that create and manipulate a deck of
playing cards: cards.scm
- Scheme functions for drawing lottery numbers or random cards from
a deck of playing cards: draw.scm
- Scheme functions that play the game Nim: nim.scm
- Scheme implementation of mancala: mancala.scm
-
Click here to download the extra credit study questions, due 11/16/07.
Field Trip:
On Saturday, September 29, 2007 we will take an educational and scenic field trip
to meander through the
Great Vermont Corn Maze. (Click
here for
photos from a former field trip.)
Also save the rain date of October 13, 2007, in the event of heavy rain on September 29.
Lecture Notes:
We will go over most of these notes during class. They are posted on this page
so that students can review them. Please note the dates. Most of these files
will be modified during the course of the semester.
- Introduction to Puzzles and Games (8/30/07 to 9/05/07)
[pdf] .
- Conway's Doomsday Algorithm (8/30/07)
[pdf] .
- Word Jumbles, Permutations, and Factorial Trees (9/05/07 to 9/07/07)
[pdf].
- Anagrams and Factorials (9/07/07)
[pdf].
- Scheme Arithmetic
[pdf] .
- Games of Chance (9/11/06 to 9/25/06)
[pdf] .
- Poker probabilities (9/22/06)
[pdf] .
- The Birthday Paradox
[pdf] .
- Random Numbers
[pdf] .
- Labyrinths and Mazes
[pdf] .
- How to thread a maze (9/27/06 to 9/30/06)
[pdf]
- Teaching Graph Algorithms in a Corn Maze (presented at ITiCSE 2006)
[pdf]
- Elements of scheme
[pdf]
- The Game of Nim
[pdf]
- Mancala Games
[pdf]
- Analysis of Algorithms (Part 1)
[pdf].
- Tower of Hanoi
[pdf]
- Peg Solitiare: A Four Peg Puzzle
[pdf].
- Rubik's Cube
[pdf].
Resources on Scheme:
- www.drscheme.org has free
versions of the Dr. Scheme programming environment, for Mac OS X, Unix, and
Microsoft Windows, that you can download.
- How to Design Programs is
an introduction to computer programming, written by Matthias Felleisen,
Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi, the developers
of Dr. Scheme. The full text is available on line. Highly recommended!
- The syntax of the scheme programming language is concisely described in
R. Kent Dybvig's
The Scheme Programming Language, second edition, Prentice-Hall,
Upper Saddle River, NJ, 1996. (The link should direct you to an on-line
copy of the textbook.)
- The textbook
Structure and Interpretation of Computer Programs, by Harold Abelson
and Jay and Julie Sussman, is available on line. It is used as an "introductory" textbook at MIT, and is based on scheme.
Resources on Puzzles and Games:
Copyright (C) 2003, 2004, 2005, 2006, 2007 to Robert R. Snapp
Last modified at 4:08 PM on 9/24/07.