12 Dec: The celebrated Doomsday for December, and the final exam for CS 32.
7 Dec: Last day of class before the final exam. Review of Sprague Grundy numbers, and mancala games. Extra credit study questions for the final exam are posted here. (You can earn up to 12 extra credit points on the final exam by turning in your solutions before you begin the final exam.)
5 Dec: Midterm 2 is returned. Whytoff’s game and its Sprague Grundy numbers. NO LABS THIS WEEK.
2 Dec: Northcott’s game, its relation to nim, and the Sprague Grundy numbers (the minimum excluded number) for nim,
30 Nov: Strategies for nim and nim misère.
28 Nov: Introduced games of perfect information and the game of nim.
18 Nov: Extra credit study problems due. Midterm 2.
16 Nov: Posted the state-transition graph and solution to the missionaries and cannibals puzzle. Today we will finish discussing Rubik’s Cube..
14 Nov: Rubik’s Cube: the third layer. Extra credit study problems were posted today. Turn them in before you begin the midterm this Friday to earn up to 15 extra credit points on your exam.
11 Nov: Rubik’s Cube: the second layer.
9 Nov: Added a new section on the main page called Programing in Racket, that consolidates information about racket and scheme programs and resources for CS 32. Today we will introduce Rubik’s Cube and learn how to unscramble the first layer.
7 Nov: The Towers of Hanoi: the recursive solution, the computation of the solution length, , and the state-transition graph of the puzzle. We had Quiz #4 today.
4 Nov: The Towers of Hanoi: introduction to the puzzle.
2 Nov: One dimensional peg solitaire.
31 Oct: Happy Hallowe’en and Happy Doomsday! We will start an new topic today: river crossing puzzles. (See Hadley and Singmaster’s annotated translation of Alcuin’s Problems to sharpen the young.)
28 Oct: Trémaux’s algorithm in racket. The TEDxUVM talks may be viewed from here.
26 Oct: More racket, including functions for walking through a maze: neighbors and random-search.
24 Oct: A little more racket: creating functions that count things in lists, including function count and antcount. Finding members in a set.
21 Oct: We will discuss the Garden of Forking Paths. Every student should be prepared to answer the question, “What is the most interesting feature about this story?”
19 Oct: Midterm exams [solutions]and study problems [solutions] were returned today. The Wednesday afternoon lab session will be cancelled today. Instead, students should attend the presentation given by Eric Brown of IBM, entitled, “Building Watson: A Brief Overview of DeepQA and the Jeopardy! Challenge,” at 4 pm today in room 427 Waterman Building. In class we will continue to discuss recursive functions in scheme and racket that manipulate lists.
17 Oct: We continued our discussion of scheme and Dr. Racket, and described functions
for manipulating lists: cons, car, cdr, and list. We also introduced random which
is available in the PrettyBig language. We studied similarities between the factorial
function and the dice function in the notes.
14 Oct: Midterm Exam.
12 Oct: Review for the midterm exam.
10 Oct: More on functions of racket, and then composite objects. We will also begin reviewing for the first midterm. (Happy Doomsday!) Quiz #3 was returned today. The alternate field trip assignment and extra credit problems were posted on the assignment page.
8 Oct; Perfect weather for a field trip to the Great Corn Maze in North Danville, Vermont. The bus is scheduled to leave at 8:30 am from the Royal Tyler Theatre Bus Stop. Here are some photos of the trip 1 2 3 4 5 6
7 Oct: We discussed more feature of Racket, including constants, symbols, and functions. We also had Quiz #3.
5 Oct: We discussed the Elements of Racket further. Also announced a reading assignment for Week 6
3 Oct: Quiz #2 was returned. Following a discussion of astronomical numbers, we showed that a random shuffle of a deck of 52 cards is almost certainly unique. A new assignment on Eulerian paths was announced, and a few examples of Eulerian paths were discussed on the blackboard. We finished class discussing some features of racket.
1 Oct: Because of a rainy forecast, the field trip scheduled for today has been postponed to Saturday, October 8.
30 Sep: Field trip permission forms are due today. We will reviewed mazes and labyrinths, completed Quiz #2 in class, and discussed how to compute factorials with Dr. Racket. We also introduced some “astronomical numbers”.
28 Sep: We practiced Trémaux’s algorithm on the blockhouse maze for both right and left bearing mice. Then we introduced Tarry’s algorithm.
26 Sep: We practiced Trémaux’s algorithm on the plan of the Hampton Court maze. Homework #3 is due today.
23 Sep: We finished our history of mazes and labyrinths, and introduced three algorithms for threading mazes: (1) random walks, (2) wall following, and (3) Trémaux’s algorithm.
21 Sep: We introduced labyrinths and mazes, and described the history of unicursal labyrinths up to the middle ages. Students learned how to draw from memory 7, and 11 circuit Cretan-style labyrinths.
19 Sep: We reviewed the multiplication principle and used it to enumerate anagrams with repeated letters. In particular, the number of distinct anagrams, , that can be constructed from a multiset containing letters, with repetitions of the first letter, repetitions of the second letter, , repetitions of the -th letter, with , is
Also, see the assignments page for a new homework assignment that is due on Monday, September 26, 2011.
16 Sep: We reviewed how to enumerate anagrams with unique letters, and introduced the multiplication principle. We also had our first surprise quiz.
14 Sep: After applying the doomsday algorithm to the date April 14, 1865, we introduced a variety of word puzzles, including anagrams. (Can you create a clever anagram using each of the letters in BARACK HUSSEIN OBAMA?) We introduced graphs and trees as abstract structures, and constructed “factorial trees” to enumerate the number of ways of permuting sets of distinct letters. Homework 1 was returned, and HW 2 was assigned.
12 Sep: We discussed some approaches to Homework 1. (Solutions are posted here.) Then we introduced DrRacket with some simple arithmetical expressions and the factorial function. Finally, we completed our introduction to puzzles and games.
Note: during the lecture today Professor Snapp mentioned that he would award an A grade to any student who was able to reverse engineer and fabricate one of Gary Foshee’s impossible objects. Of course, this remark was made in jest. However, if you have sufficient skill to manufacture such creations, you have a career opportunity that few can match.
9 Sep: We continued our introduction to puzzles and games. Note: the first homework assignment will be due today. There is also a new reading assignment.
7 Sep: We finished our discussion of the Doomsday algorithm, and began introducing some of the puzzles & games that we will study this semester.
5 Sep: Labor Day Holiday. No class today!
2 Sep: Today we introduced John Horton Conway’s Doomsday Algorithm for computing the day of the week of any date in the Gregorian calendar. Please check the assignment page for the reading and homework assignments.
31 Aug: Welcome to CS 32, Puzzles, Games & Algorithms. Today we discussed the course goals, organization, and policies. We reviewed the syllabus, and changed the time of the first Wednesday lab to Tuesdays, 10:00–10:50 am, in Room 229 Votey. Lab sessions will not meet this week.
