On This Page

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 (still under construction)

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

• Week 1 (Sep. 5): Abstraction and Information Structures
  • Lists as fundamental information structures
  • Sets and graphs as lists
  
  
• Assignment 1
  • Data representation
  
  
• Week 2 (Sep. 10): Using Functions
  • Representing trees as lists
  • Higher-order functions: some common examples
  • Function composition
  • First-class objects
  • Anonymous functions
  • Additional examples
  • Predicates as special functions
  • More general entities: relations
  • Functional decomposition of problems
  
  
• Assignment 2
  • Several small programs
  
  
• Week 3 (Sep. 17): Implementing Rex functions
  • Rewrite rules
  • accumulators
  • recursion; tail recursion
  • tree search: BFS, DFS
  • guards: equational, conditional
  • laziness
  • infinite lists
  • currying
  • types


• Assignment 3
  • Project using Rex
  
  
  
• Sep. 24 - Implementing data structures in Java
  • Java syntax
  • List implementation
  • References and pointers
  
  
  
• • 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
  
  
  
• Oct. 1 - 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"
  
  
  
• 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. 8 - Event-driven programming
  • graphics syntax and AWT
  • event handling
  • double buffering
  • interfaces
  
  
  
• Additional Java programming
  • 2d arrays; matrices
  • Breadth-first search, depth-first search
  
  
  
• 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. 15 - 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. 22 - Fall break
• Oct. 24 - 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. 29 - Modeling and implementing low-level computation
  • Propositional Logic
  • Boolean algebra
  • combinational functions
  • encoding sets in binary
  • two-term operators
  • completeness of nor
  • tautologies
  
  
  
• Manipulating and analyzing logical functions
  • Minterm reduction
  • Shannon expansions
  • SOP == DNF representation
  • Karnaugh maps
  • computing circuits
  • "don't care" bits; LED example
  
  
  
• Assignment 8
  • TBD
  
  
  
• Nov. 5 - 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
  
  
  
• 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. 12 - 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. 19 - 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. 26 - More algorithms
  • Sorting
  • Empirical and code-analysis techniques
  • asymptotic growth rates
  • proving one function is O(another)
  • profiling
  • Heaps
  
  
  
• Assignment 11
  • 1/2 written: running time analyses
  • 1/2 coding: empirical running time experiments
  
  
  
• Dec. 3 - Models for computers
  • finite-state machines
  • DFA NFA and regular expressions
  • more generally, what languages are accepted by what machines
  
  
  
• More models for computers
  • clocks, flip-flops
  • buses
  • multiplexors, etc.
  • latches
  • adders, registers
  • RAM, one-hot selection
  
  
  
• Assignment 12
  • use the JFLAP graphical interface to develop and test some DFAs etc.
  
  
  
• Dec. 10 - Stored-program computers
  • conceptual model
  • ISC assembly language
  • implementing recursion in ISC and C
  • memory-mapped I/O : other services of the OS
  
  
  
• Stored-program computers II
  • other hardware-related issues
  • interrupts, traps, signals
  • pipelining
  • strobes
  • types of addressing
  
  
  
• Assignment 13
  • Write ISC programs
  
  
  
• Limitations of practical computing
  • practical limitations: exponential running time
  • examples of difficult important problems
  • P ?= NP
  
  
  
• 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