Programing exercises in this course are developed using DrRacket (formerly known as DrScheme). DrRacket supports a language called racket, a descendant of a language called scheme, which in turn was derived from the classic language for artificial intelligence called LISP. Think of LISP as the grandmother, scheme as the mother, and racket as the daughter. DrRacket can also be used to develop languages in a variety of dialects of scheme (e.g., R5RS).
To get started, download and install Racket from www.racket-lang.org. Automatic installers exist for Linux, Microsoft Windows, and Mac OS X. (If you have trouble installing the software, please consult with the professor or teaching assistant.) When you first run DrRacket it is advisable to select a language dialect from the Language menu that appears along the top of your display. For our applications to run optimally, select Choose Language …, and then select “PrettyBig” under “Legacy Languages” from the drop-down menu. Since the distinction between racket and scheme is minimal,
Almost all of the information that you need to use DrRacket will be given in your lecture and laboratory sessions. We actually will need only to understand a small fraction of racket and scheme in this course. More information for the curious student is available at the bottom of this page.
factorial.scm The factorial function, defined recursively by , if and , otherwise. So, for example, enumerates the number of ways that distinct objects can be permuted, e.g., the number of anagrams that can be created using distinct letters of the alphabet. We will use this formula and function pattern often.
binomial.scm computes binomial coefficients, which are the numerical values that appear in Pascal’s triangle.
jumble2005.scm solves simple jumble, or word scramble, puzzles: e.g., find a word in the dictionary that is an anagram of naanba. This program requires a dictionary (web2) of English words.
clone.scm creates an exact copy of a list. This task is not particularly useful. However it is helpful to learn the pattern of taking something completely apart, and then putting it back together again, as variations of this pattern can lead to impressive and useful applications.
anteater.scm is a simple variation of clone that swallows every ant that is visible in the argument list, leaving everything else alone.
alchemy.scm is a simple variation of clone that turns every piece of lead in the input list into gold, leaving everything else intact.
randomsearch.scm simulates the behavior of a drunken mouse in a maze.
tremaux.rkt simulates the behavior of a CS 32 student in the Great Vermont Corn Maze.
hanoi.scm sovles the Tower of Hanoi puzzle.
graphsearch.scm demonstrates how a single function graph-search can be used to solve four different problems: threading a maze, solving a one-dimensional peg solitaire puzzle, solving the Tower of Hanoi puzzle (although not so efficiently), and solving the missionaries and cannibals puzzle. A common algorithm is facilitated by reducing each puzzle to its state-transition graph.