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 2009.
(N.B., the content of this page changes frequently.)
General Information:
- Instructor:
Robert R. Snapp
(e-mail).
-
Office Hours:
Tues. 1:30 – 2:30 p.m., Wed. 1:30 – 3:00 p.m., Fri. 10:00 – 11:00 a.m.,
and by appointment.
- Lectures on Monday, Wednesday and Friday, in Room 367 Votey,
11:45 am. – 12:35 pm.
- Lab Instructor: TBA
- Lab Sections meet in room 206 Votey:
- Wednesdays, 4:25 – 5:40 p.m.
- Thursdays, 4:00 – 5:15 p.m.
- Thursdays, 5:30 – 6:45 p.m.
- Pop quizzes can occur on any day!
- Field trip: Saturday, September 26, 8:30 a.m. – 4:30 p.m.. (Rain Date: Sat., Oct. 17).
The bus will leave at 8:30 a.m. from the bus stop south of Old Main, and west of the Royall-Tyler Theater. 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. 25, 2009
(photos from 2007).
- Midterm Exams (in class): Friday, Oct. 16, 2009 and Friday, Nov. 20, 2009.
- Final Exam: Tuesday, Dec. 15, 2009, 3:30 – 6:30 pm.
Required Materials:
- Access to a computer with PLT-Scheme, which can be downloaded for free from
www.plt-scheme.org.
(Each student will be given a computer
account that will enable use of PLT-Scheme 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).
- One standard, 3 x 3 x 3 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 Wednesday, 09/09/09, please read Chapter 1 of Johan Huizinga's Homo Ludens.
and Chapters 1 and 2 of Roger Caillois's, Man, Play and Games, the course
syllabus, and UVM's
Code of Academic Integrity.
- By 10/02/09 please read the short story
“The Garden of Forking Paths”
by Jorge Luis Borges.
- By 11/30/09 please read the short story
“The Lottery in Babylon”
by Jorge Luis Borges.
Homework Assignments:
Each homework assignment usually consists of written assignments and
programming projects.
- HW 1:
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. Your lipogram
can contain acronyms such as “USA” and “UVM”, but you should avoid faulty grammar, bad punctuation, obfuscations, and word malformations. By 9/16/2009 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 2:
In this maze of an assignment you must first decide one of the following
alternatives before writing a 5 to 6 page (double spaced) composition. You may write
either an analytic essay, or a creative composition (e.g., a short story excerpt).
For example, for the analytic essay you might consider:
- The word “time” is prohbited from Ts' ui Pen's Garden of Forking Paths. Use your imagination to discover which single significant word is “prohibited” from Jorge Borges's “The Garden of Forking
Paths”.
- What is the relation between Borges's story and Ts'ui Pen's fictional
labyrinth? Are they recursive like our factorial function? Are they both
literary labyrinths? Do they both portray conflicting portraits
of reality?
- References are made in the story to real people, novels, and
events, for example, Captain Liddell Hart, the
Thousand and One Nights,
the Annals of Tacitus, the
Hung Lu Meng, and the First World War.
Describe how one or more of these elements enhance
the story.
Your analytic essay should follow the the revised Essay Style Guidelines for CS 32.
However, if you decide to follow a fictional path,
you might consider one of these options:
- Write “the first two pages” that are “missing” from the statement of Dr. Yu Tsuan.
- Write several short conflicting tales that might be part of Ts'ui Pen's
Garden of Forking Paths.
- Write the police report filed by Captain Richard Madden, that narrates
his observations, suppositions, and most importantly how he was able to track Dr. Yu Tsun during his elusive flight.
Please ensure that your final draft is grammatically correct, and correctly
spelled and punctuated. Omit needless words. Proof read your work before you
turn it in on Monday, October 12, 2009.
- Extra Credit Assignment: In addition to Homework 3, you may for extra credit
modify the scheme function madlibs.scm so that it prints out a random
fortune instead of a silly phrase. You may modify it as much as you please, however, your program should have the potential of generating hundreds of millions of different fortunes. Please turn
in your assignment by e-mail by Monday, October 12, 2009.
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] (2 pages).
- Essay Style Guidelines for CS32 [html].
- UVM's 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 javascript program that computes factorials
- 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 tremaux.scm (revised 10/2/08).
- Coxeter's garden maze [pdf],
from Ball and Coxeter, Mathetmatical Recreations and Essays, 13th Edition,
Dover, Mineola, New York, 1987, p.259.
- Scheme function definitions created in class on October 7, 2009, including functions Reverse, Append2, count-down and count-up are defined in file oct7.ss
- 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
Field Trip:
On Saturday, September 26, 2009 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.)
Lecture Notes:
We will go over most of these notes during class. They are posted on this page
so that students can review them. Titles that appear in black have either been
covered in class, or will be covered soon. Titles that appear in
green will be covered in the future.
Some of these files
will be modified during the course of the semester.
- Conway's Doomsday Algorithm
[pdf] .
- Introduction to Puzzles and Games
[pdf] .
- Word Jumbles, Permutations, and Factorial Trees
[pdf].
- Anagrams and Factorials
[pdf].
- Scheme Arithmetic
[pdf] .
- Labyrinths and Mazes
[pdf] .
- How to thread a maze
[pdf]
- Elements of scheme (09/28/09 to 10/02/09)
[pdf]
- Peg Solitiare: A Four Peg Puzzle (10/20/08 to 10/22/08)
[pdf].
- River crossing puzzles
[pdf]
- Tower of Hanoi (10/22/08 to 10/24/08)
[pdf]
- Rubik's Cube (10/24/08 to 10/29/08)
[pdf].
- The Game of Nim (10/31/08 to 11/17/08)
[pdf]
- Mancala Games (11/17/08 to 11/19/08)
[pdf]
- Games of Chance (12/01/08 to 12/010/08)
[pdf] .
- Poker probabilities (12/08/08)
[pdf] .
- The Birthday Paradox
[pdf] .
- Random Numbers
[pdf] .
- Analysis of Algorithms (Part 1)
[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) 2009 to Robert R. Snapp
Last modified at 1:33 AM on 4/18/09.
