On This Page

Exam Dates

The midterm exam will be held in-class on Mon. October 25.
The final exam will be held on a date designated by the college.

The two exams are closed-book except that you are allowed one sheet of paper (double sided) containing your own notes. The exams emphasize conceptual understanding, rather than memorization of fine details. Both are taken by all students according to the HMC honor code.

Past courses' exams are available for review here.

Last term's list of final exam topics is also available.

Tentative Lecture Schedule

This list constitutes the basic topics of CS60; they will be the focus of the lectures, assignments, and exams for the course.

• Sep. 1 - Computation in the abstract
  • Functional Programming (Rex)
  • Lists as fundamental information structures
  • Operations on lists
  • Pattern Matching
  
  
  
• Sep. 6 - Information Structures
  • Recursive data structures
  • Using recursion effectively
  • Trees and graphs as lists and their operations
  • Emphasize the no-side-effects paradigm
  
  
  
• Assignment 1
  • Practice using Rex
  
  
  
• Sep. 8 - Putting the function in functional programming
  • first-class objects
  • function composition
  • environment as execution context
  • static vs. dynamic binding
  • higher-order functions: some common examples
  • anonymous functions
  
  
  
• Sep. 13 - Higher-order functions
  • additional examples
  • predicates as special functions
  • more general entities: relations
  • functional decomposition of problems
  
  
  
• Assignment 2
  • Project using Rex, e.g., unit calculator
  • several small programs
  
  
  
• Sep. 15 - Implementing Rex functions
  • Rewrite rules
  • accumulators
  • recursion; tail recursion
  • tree search: BFS, DFS
  
  
  
• Sep. 20 - Wrap-up of functional programming
  • guards: equational, conditional
  • laziness
  • infinite lists
  • currying
  • types
  
  
  
• Assignment 3
  • continue project using Rex
  • several small programs
  
  
  
• Sep. 22 - Implementing data structures in Java
  • Java syntax
  • List implementation
  • References and pointers
  
  
  
• Sep. 27 - More Java Data Structures
  • Stacks/Queues and variants
  • deep vs. shallow equality
  • open vs. closed lists
  • virtual memory
  
  
  
• Assignment 4
  • Implement some data structure in Java: Queues based on lists
  
  
  
• Sep. 29 - The object oriented paradigm
  • Classes and objects
  • Interfaces
  • Object state and methods for making transitions
  • mutability
  • appropriate uses of class derivation: "is a" not "part of"
  
  
  
• Oct. 4 - Inheritance
  • message metaphor; casting
  • polymorphism and container classes
  • the java built-in hierarchy
  • virtual functions
  • applets
  
  
  
• Assignment 5
  • Extend assignment 4 to take advantage of the properties of inheritance hierarchies, e.g. double-ended queues
  
  
  
• Oct. 6 - Event-driven programming
  • graphics syntax and AWT
  • event handling
  • double buffering
  • interfaces
  
  
  
• Oct. 11 - Additional Java programming
  • 2d arrays; matrices
  • Breadth-first search, depth-first search
  • other stuff I've forgotten
  
  
  
• Assignment 6
  • Use queues in an applet, e.g., the maze-solving applet or the minesweeper applet.
  • include programming based on an interface and not the source code
  
  
  
• Oct. 13 - Implementation of programming languages
  • grammars aas a specification tool for languages
  • inductive definitions
  • more general notion of "language"
  • general proof by induction
  • expression trees
  • precedence and associativity: tighter-binding functions are closer further from the root
  
  
  
• Oct. 20 - Parsing of expressions
  • grammar generates; parser tests for membership
  • compilation steps: tokenize, parse, translate
  • parsing and recursive descent
  
  
  
• Assignment 7
  • Parsing programming in Rex and/or Java
  
  
  
• Midterm
  
  
• Oct. 25 - Modeling and implementing low-level computation
  • Propositional Logic
  • Boolean algebra
  • combinational functions
  • encoding sets in binary
  • two-term operators
  • completeness of nor
  • tautologies
  
  
  
• Oct. 27 - Manipulating and analyzing logical functions
  • Minterm reduction
  • Shannon expansions
  • SOP == DNF representation
  • Karnaugh maps
  • computing circuits
  • "don't care" bits; LED example
  
  
  
• Assignment 8
  • No idea.
  
  
  
• Nov. 1 - Predicate logic
  • variables representing individuals
  • quantifiers
  • graphs as binary relations -- equivalent to predicates
  • valid, satisfiable, unsatisfiable expressions (SAT)
  • DeMorgan's laws for quantifiers and simplifying expressions
  
  
  
• Nov. 3 - Programming in Logic
  • prolog and its syntax
  • computes variables within predicates
  • closed-world assumption and assumed quantifiers
  • examples: geneology, puzzle-like problems
  
  
  
• Assignment 9
  • Programs in prolog, e.g., restaurant-query example and puzzle-solving examples
  
  
  
• Nov. 8 - Using logic in procedural programming
  • program correctness: proving vs. debugging
  • program specification: states and transitions
  • assertions
  • loop invariants
  • proofs of correctness; assertion proofs
  • examples
  
  
  
• Nov. 10 - Analyzing algorithms
  • program vs. computational complexity
  • other possibilities: memory complexity
  • dependence on input size
  • counting steps
  • writing and unrolling recurrences
  • growth rate and big-O definition
  
  
  
• Assignment 10
  • Another prolog example
  • Assignment on proving programs correct and big-O notation.
  
  
  
• Nov. 15 - More algorithms
  • Sorting
  • Empirical and code-analysis techniques
  • asymptotic growth rates
  • proving one function is O(another)
  • profiling
  
  
  
• Nov. 17 - Even more algorithms
  • Worst/Average/Best case
  • Adversary proofs of lower-bound running times
  • Min-extraction
  • Heaps
  • Dynamic programming vs. divide and conquer vs. greedy strategies
  
  
  
• Assignment 11
  • 1/2 written: running time analyses
  • 1/2 coding: empirical running time experiments
  
  
  
• Nov. 22 - Models for computers
  • finite-state machines
  • DFA NFA and regular expressions
  • more generally, what languages are accepted by what machines
  
  
  
• Nov. 24 - More models for computers
  • clocks, flip-flops
  • buses
  • multiplexors, etc.
  • latches
  • adders, registers
  • RAM, one-hot selection
  
  
  
• Assignment 12
  • use the JFLAP graphical interface (a la Ran) to develop and test some DFAs etc.
  
  
  
• Nov. 29 - Stored-program computers
  • conceptual model
  • ISC assembly language
  • implementing recursion in ISC and C
  • memory-mapped I/O : other services of the OS
  
  
  
• Dec. 1 - Stored-program computers II
  • other hardware-related issues
  • interrupts, traps, signals
  • pipelining
  • strobes
  • types of addressing
  
  
  
• Assignment 13
  • Write ISC programs
  
  
  
• Dec. 6 - Limitations of practical computing
  • practical limitations: exponential running time
  • examples of difficult important problems
  • P ?= NP
  
  
  
• Dec. 8 - Limitations of Turing computing
  • TM limitations: undecidability
  • Turing's thesis
  • other computational models: do they change things?
  • molecular computation, quantum, reversible, nerual nets, genetic programming (not reallya model of computation, but...)
  
  
  
• Final Exam