Harvey Mudd College Computer Science 60 Principles of Computer Science Spring 2010

New!    CS 60 practice problems for the final exam...
New!    CS 60 solutions to the above practice problems .
New!    CS 60 final exam study guide for the final exam
You may take the final on your choice of Monday 5/10 at 2pm or Friday 5/14 at 2pm.
There will be a review session (using the practice problems, above, as a starting point) on Sunday 5/9 at 7pm.
Old    CS 60 midterm study guide for the midterm in-class on Wed. and Thu. 3/24 and 3/25.

Brief Overview:     In CS 60, Principles of Computer Science, students will complete a broad, hands-on overview of the science of computer science. In several conceptual areas CS 60's depth prepares students to apply key CS principles to any endeavor or project, with any computational interface or language. After CS 60, both CS majors and non-majors will be able to design, program, test, and evaluate novel computational solutions to problems across CS, mathematics, science, engineering, and other fields.
Here is a link to the complete course syllabus.

Assignments will be posted here; note that assignments are customarily due at 11:59 p.m. on the day indicated. Please submit your files through our web-based submission system.

Your submission password has been reset to the default, but please set it to something memorable!
If you forget the default password, email me at dodds@cs.hmc.edu... .

Assignment 14    Optional, extra-credit assignment: Seam Carving!    Due Sunday, May 9, 2010, by 11:59 pm.

• Filenames: Submit an updated version of SeamCarving.zip under week 14.
• The starter files, SeamCarving.zip

Assignment 13    Fast algorithms via dynamic programming!    Due Sunday, May 2, 2010, by 11:59 pm.

• Euro reminder:     if you use a Euro, then Hw13 is due by 11:59pm on Monday, May 3.
• Filenames: You'll submit three files this week. They are named
  • change.scm, change.java, and FloydWarshall.java
• HW links, slides, etc.:
  • Efficiency and dynamic programming
    
  • Sorting out CS: finale
    
    
  • Support files:
  • Link to source code for the in-class knapsack example
  • Link to the US.txt currency file   Link to the Shmorbodia.txt currency file
  • Link to compiled Floyd-Warshall algorithm and support files, fw.zip

Assignment 12    Uncomputability proofs, run-time analysis, and a bit of review...    Due Sunday, April 25, 2010, by 11:59 pm.

• Euro reminder:     if you use a Euro, then Hw12 is due by 11:59pm on Monday, April 26.
• Filenames: You'll submit a few files this week. They are named
  • hw12.txt, hw12.scm, hw12.pl, and hw12.java
• HW links, slides, etc.:
  • Uncomputability
    
  • Complexity: big-O analysis
    
  • The assignment has a link to an example proof of uncomputability on which to base your own.

Assignment 11    Computational Models: FSMs and Turing Machines    Due Sunday, April 18, 2010, by 11:59 pm.

• Euro reminder:     if you use a Euro, then Hw11 is due by 11:59pm on Monday, April 19.
• Filenames: You'll submit many small files this week. They are named
  • part1.jff, part2.jff, part3.txt, part4.jff, part5.jff, part6.jff, part7.txt, part8.txt, part9.jff, part10.jff, and optionally excr1.jff, excr2.jff, excr2.txt, and excr3.txt.
• HW links, slides, etc.:
  • Finite state machines and the distinguishability theorem
    
  • Nondeterministic FSMs and Turing Machines
    
  • Note, too, that the assignment has links to a couple of example proofs on which to base your own.

Assignment 10    Compiler for a Simple Language    Due Sunday, April 11, 2010, by 11:59 pm.
Improved Version.
              extra-credit grammars for hw#10

• Euro reminder:     if you use a Euro, then Hw10 is due by 11:59pm on Monday, April 12.
• Filenames: You'll submit a10.pl for this week.
• HW links:
  • CS 60 grammars (W/Th) lecture
    

Assignment 9    Constraint Solving and Backtracking    Due Sunday, April 4, 2010, by 11:59 pm.

Assignment 8    Prolog: yes!    Due Sunday, March 28, 2010, by 11:59 pm.

• Euro reminder:     if you use a Euro, then Hw8 is due by 11:59pm on Monday, March 29.
• Filenames: You'll submit at least one file for Hw #8:
  • [Pair or Indiv.]     movies.pl    Starter file: movies.txt - rename to .pl or .pro
  • helper file     movies_db.pl    Starter file: movies_db.txt - rename to .pl or .pro
  • [Pair or indiv. extra!]     lists.pl    Starter file: lists.txt - rename to .pl or .pro
• HW links:
  • SWI Prolog download page
    Prolog is available for Windows (with a graphical IDE) and Mac OS X and Linux (command-line) from the site linked above.
    Note   For Max OS X, you don't need to worry about xquartz or the developer tools - as far as I can tell, you'll need to run Prolog from the command-line anyway. Do get the version that matches your operating system, however!
• Lectures 15-16 slides 3/10-3/11 and 3/22-3/23    (6-up version)
• Prolog Examples:
  • exam.pro (How to pass an exam)
  • ancestor.pro (Ancestry)
  • tutors.pro (Tutoring Database)
  • enumerate.pro (Enumeration Utility)
  • sexp.pro (S-expression parser)
• Lectures 17 slides 4/5    (6-up version)

Assignment 7    The double-ended spamcruncher: Spampede!    Due Friday, March 12, 2010, by 4:59 pm.

• Filenames: You'll submit at least these files for Hw #7:
  • [Pair or Indiv.]     Maze.java    (The updated Maze class)
  • [Pair or Indiv.]     SpamMaze.java    (The SpamMaze class, derived from Maze!)
  • [Pair or Indiv.]     Spampede.java    (The applet code)
  • Be sure to submit any additional files needed to run your code, too. You can submit them by clicking the "support file" checkbox on the submission site.
  Support files and starter versions of some of these files are available from these links:
• HW links:
  • hw7files.zip starter files for Hw#7, all parts.
• Lecture 13 (W/Th slides) 3/3-3/4
• Lecture 14 (M/T slides) 3/8-3/9

Assignment 6: Spam-sweeping and -seeking!    Due Wednesday, March 3, 2010, by 11:59 pm.

• Euro reminder:     if you use a Euro, then Hw6 is due by 9:59pm on Thursday, March 4.
• Filenames: You'll submit (at least) one file for each problem:
  • [Indiv. or pair programming]     Spamsweeper.java    (The Spamsweeper game)
  • [Individual Only!]    Queue.java    (Your closed-list Queue class)
  • [Individual Only!]    Maze.java    (Your maze-solver)
  • (Extra credit): SpamsweeperApplet.zip    (the web version)
  Note that problems 2 and 3 (Queue and Maze) are to be done individually this week.
  Support files and starter versions of some of these files are available from these links:
• HW links:
  • [pair or indiv.] SpamsweeperStarterFiles.zip starter files for Hw#6, part 1
  • [pair or indiv.] SpamsweeperClassfiles.zip class files for running Spamsweeper
  • [indiv. only] Parts2And3Files.zip starter files for Hw#6
  • [pair or indiv.] SpamsweeperAppletFiles.zip class files for running Spamsweeper
  • Stack.java, the linked-list Stack implementation from class
  • StackInterface.java, Stack's interface "contract"
• Lecture 11 (W/Th slides) 2/24-2/25
• Lecture 12 (M/T slides) 3/1-3/2

Assignment 5: Tokenize - Parse - Evaluate!    Due Wednesday, February 24, 2010, by 11:59 pm.

• Euro reminder:     if you use a Euro, then Hw5 is due by 9:59pm on Thursday, February 25.
• Filenames: You'll submit a zip file named hw5.zip with at least these five files:
  • Quantity.java    (quantity lists and Unicalc)
  • Tokenizer.java    (the tokenizer)
  • Parser.java    (the parser)
  • Evaluator.java    (the evaluator)
  • OpenList.java    (an OpenList class from Hw#4)
  Starter versions of these files (and a tester named QuantityTester.java) are already in hw5.zip, below:
• HW links:
  • [pair or indiv.] hw5.zip starter files for Hw#5
  • a set of class files implementing hw #5 for testing or confirming how it should work...
  • Unicalc.scm , Scheme solutions to unicalc (to help port to Quantity)
  • MiniMath.zip , a full implementation of a small math-evaluation language
• Lecture 9 (W/Th slides)
• Lecture 10 (M/T slides)

Assignment 4: Conversational Java!    Due Wednesday, February 17, 2010, by 11:59 pm.

• Filenames: You'll submit three files: JavaInteration.java, Complex.java, and OpenList.java.
• Euro reminder:     if you use a Euro, then Hw4 is due by 9:59pm on Thursday, February 18.     HW links:
• for problem #1: [pair or indiv.] JavaInteraction.java    A text version to browse     A starting file for problem #1
• for problem #1: JavaIntro.java    JavaIntro.java.txt    the full intro file, for reference
• for problem #2: [pair or indiv.] Complex.java    A text version to browse    A starting point for Complex
• for problem #2: Point.java    A text version to browse    Our in-class Point example
• for problem #3: [pair or indiv.] OpenList.java    A text version to browse    A starting point for your lists.
• MainFromCompletedOpenList.java    A text version to browse The main function we used to test our solutions - (most useful a bit at a time...)
• the Java language: obtaining it, getting an editor, and lots of references:
  • My favorite java syntax reference
  • Wikipedia's Java syntax reference
  • Java 6 API   All of Java's library functions!
  • JDK 6 Update 18 download (You'll want the JDK for your OS)
  • Java language basics (you're only 1 hour away from putting Java on your resume/CV!)
  • Sun's introduction-to-java tutorial
  • all of the Java tutorials (a lifetime's worth!)
• Link to Lec7_cs60_spr_2010_wed.ppt, W/Th's slides
• Link to Lec8_cs60_spr_2010.ppt, M/T's slides

Assignment 3: Unicalc CLI    Due Wednesday, February 10, 2010, by 11:59 pm.

• The filename: Please name your submission a03.scm this week... .
• Euro reminder:     if you use a Euro, then Hw3 is due by 9:59pm on Thursday, February 11.     HW links:
• Unicalc database
• top-level-Tests for Assignment 3 (unicalc-top-level-tests.scm)
• repl-tests for Assignment 3 (unicalc-repl-tests.txt)
• repl-test output for Assignment 3 (unicalc-repl-tests-out.txt)

Assignment 2: Unicalc API    Due Wednesday, February 3, 2010, by 11:59 pm.

• The filename: Please name your submission a02.scm this week... .
• Euro reminder:     if you use a Euro, then Hw2 is due by 9:59pm on Thursday, February 4.     HW links:
• Unicalc database
• Tests for Assignment 2 (unicalc-tests.scm)
• Example Unicalc applet on the web
Assignment 2 solution

Assignment 1: Fun with functional programming!    Due Wednesday, January 27, 2010, by 11:59 pm.

• Remember:     if you use a Euro, then Hw1 is due by 9:59pm on Thursday, January 28.
• Useful links     - remember to remove the .txt from text files to run them in Dr. Scheme:
• Download Dr. Scheme!    Online Dr. Scheme Docs    PLT Scheme Reference
• Scheme quick reference card    Online Scheme Manual
• tester.scm (Scheme unit tester)    trace.scm (Example of Scheme tracing)
• sampler.scm (Scheme samples)   
• show.scm, test-show.scm: Additional debugging aid: When (show ...) is wrapped around an expression, prints the expression and its value, in addition to returning the value as the value of show.
• On-Line book covering much of the course material, by Prof. Keller, but using Rex, not Scheme.
• Lec1_cs60_Spring_2010_Tuesday.ppt (ZD's slides 1/19/10)
• Lecture 2: Scheme List (and String) Functions
• Hw1 hints on map and foldr: hw1_scheme_hints_map_and_foldr.scm.txt
• Lecture 3: High-Level Functional Programming
• Lecture 4: Low-Level Functional Programming
• Lecture 5: Designing A Language
• Language for Logic Implemented in Scheme (with function values, etc.)
• Lecture 6: Functional Programming Wrap-Up