Harvey Mudd College

Computer Science 42
DON'T PANIC

Principles and Practice of Computer Science
Fall 2009

Instructor: Prof. Keller, Olin 1253, x-18483, keller at cslhmcledu, AIM: MuddProf, Hours: MTW 4-5 and as otherwise available.

Meets: MW 1:15-2:30, Parsons 1285

Selected first-year students only, grading P/HP/NC, Homework 50%, Midterm 15%, Final 30%, Participation 5%

Languages we use: Scheme, Java, Prolog, ISCAL

 

The purpose of CS 42 is to provide an accelerated introduction for first-year students who are advanced and who possess more than average motivation for study of computer science. If youÕve completed this course, you will have learned the topics in both the general introductory course CS 5, as well as the second course CS 60, and possibly more. You are then eligible to take any course having CS 60 as the prerequisite.

 

CS 42 is oriented toward concepts. We currently use four different languages to illustrate those concepts. However, the purpose is not to teach those languages as much as it is to use them as vehicles for the concepts. The expectation is that, once those concepts are learned, they can be applied in the context of other languages, although the difficulty may vary with the language chose.

 

Catalog Description

 

Accelerated breadth-first introduction to computer science as a discipline for students (usually first-year) who have some programming background. Computational models of functional, object-oriented, and logic programming. Data structures and algorithm analysis. Computer logic and architecture. Grammars and parsing. Regular expressions. Computability. Extensive practice constructing applications from principles, using a variety of languages. Prerequisite: Permission of Instructor.  3 credit hours.  (Fall.)

 

Assignments and Useful Links

Assignments will be posted here as they are issued. Note: Assignments are always due at 11:59 p.m. on the day indicated. They are submitted using a web-based system at http://www.cs.hmc.edu/~cs0grad/submissions/submit.py.

á          Assignment 1 (Functional Programming Warmup) Due Tue. 8 September 2009 at 11:59 p.m.

á          Assignment 1 solutions

á          sampler.scm (Scheme sample definitions)

á          Recursion Examples from Lecture 2

á          Tail-Recursion and Mutual Recursion Examples from Lecture 3

á          Assignment 2 (Unicalc API) Due Tue. 15 September 2009 at 11:59 p.m. 

á          Assignment 2 solutions

á          unicalc-db.scm (Unicalc database)

á          unicalc-tests.scm (Unicalc API tests)

á          Unicalc database cycle check (example from Lecture 4)

á          read-eval-print loop for Unicalc in Scheme (Lecture 4)

á          First approximation evaluator for Unicalc in Scheme (only normalizes input, Lecture 4)

á          Second approximation evaluator for Unicalc in Scheme (does some evaluation, Lecture 5)

á          Sample input for the above (does some evaluation, Lecture 5)

á          Assignment 3 (Unicalc API) Due Tue. 22 September 2009 at 11:59 p.m. 

á          Assignment 3 solutions

á          Tests for assignment 3

á          Output from tests for assignment 3

á          Assignment 4 (User-Friendly Unicalc) Due Tue. 6 October 2009 at 11:59 p.m.

á          Assignment 4 Solution

á          Parsing hint for assignment 4

á          Tests for assignment 4

á          Output from tests for assignment 4

á          Unicalc Applet

á          Expression Parser Applet

á          Logic Synthesis (slides)

á          Logic Simulator (from TETZL.de)

á          Logic Simplification (slides)

á          Logic parser and simplifier example

á          Assignment 5 (Logic Simplifier) Due Wed. 14 October 2009 at 11:59 p.m.

á          Assignment 5 Solution (Scheme part)

á          7-segment test cases for assignment 5

á          Possible output for tests for assignment 5

á          Tautology Checker Applet

á          Hypercube Applet

á          Finite-State Machines as Hardware

á          MOS Transistors and Gates

á          Transistor Gates

á          NMOS Transistor Diagram

á          FPGA's, etc.

á          Digital Logic with VHDL Design (book)

á          Computer Architecture and the ISC

á          Stored Program Computers

á          Java Tutorial

á          Primitive Types in Java

á          Generics in Java

á          Assignment 6 (due Wed. 4 November, 11:59 p.m.)

á          Assignment 6 Solution (zipped source files)

á          Some test input for Assignment 6

á          Test output for the above

á          Bigger test input for Assignment 6

á          Test output for the above

á          Random graph generator (in Scheme)

á          Assignment 7 (due Wed. 11 November, 11:59 p.m.)

á          Assignment 7 Solution (zipped source files)

á          jUnit tests for Assignment 7

á          Assignment 8

á          Starter Kit for Assignment 8

á          Various Java Topics, including Graphics, Threads, Memory Management

á          Exceptions in Java

á          Visibility and Access Control in Java

á          Logic Programming and Prolog

á          Assignment 9 (Due Thurs. Dec. 10, 11:59 p.m.)

á          Assignment 9 Solution

á          Prolog Code Examples

á          Prolog References

á          Turing Machines

á          Busy Beaver problem

á          Keller's openlist2009 JavaDoc

á          Keller's openlist2009 Doxygen

á          Keller's openlist2009 files (.zip)

á          trace.scm (Example of how to use Scheme trace facility)

á          On-Line Version of a Book covering much of the course material,
written by the instructor (uses rex rather than Scheme, however)

á          Download Dr. Scheme

á          On-line Documentation for Dr. Scheme

á          tester.scm (Scheme unit tester)

á          Scheme Quick Reference Card (4 page pdf)

á          Scheme Manual (html version)

á          PLT Scheme Reference (html version)

 

Approximate Syllabus

Day

Date

Topics

Wed.

9/2

Data modeling by lists, S-Expressions, Scheme language, Functions, Association Lists

Mon.

9/7

Low-Level Functional Programming, Recursion, Number representation

Wed.

9/9

Propositional Logic Functions, Functional Completeness, Logic simplification

Mon.

9/14

High-Level Functional Programming, Problem Decomposition, Anonymous Functions

Wed.

9/16

Lists vs. Arrays, Complexity considerations

Mon.

9/21

Directed Graphs and Relations, Graph Searching

Wed.

9/23

Trees and DAGs

Mon.

9/28

Language Interpreter

Wed.

9/30

Open lists in Java

Mon.

10/5

Exceptions, Copying and Equality

Wed.

10/6

Abstractions and Interfaces, Higher-Order Functions in Java

Mon.

10/12

Enumerations, Closed Lists, Inner Classes,

Wed.

10/14

Inheritance, Abstract Classes, Event-Handling, Graphics

Mon.

10/19

Fall Break

Wed.

10/21

Take-home Mid-term exam

Mon.

10/26

Threads, Garbage Collection

Wed.

10/28

Grammars and Parsing

Mon.

11/2

Finite-State Machines, Regular Expressions

Wed.

11/4

Logic synthesis, Hardware components

Mon.

11/9

Turing Machines

Wed.

11/11

Predicate logic, Prolog and databases

Mon.

11/16

Non-determinism and Backtracking

Wed.

11/18

Computer architecture, Assembly language

Mon.

11/23

Constructing a compiler

Wed.

11/25

No class the day before Thanksgiving

Mon.

11/30

Program correctness

Wed.

12/2

Complexity, Algorithm design

Mon.

12/7

Undecidability, the Halting Problem

Wed.

12/9

Incomputability Reductions

Wed.

12/16

Final Exam, 2-5 pm