CS60 Final Exam Review Sheet

Fall 2002

First part of the course:

• Information structures:
• Lists,
• Trees, trees as lists, lists as trees,
• graphs
• Difference between [A, B] and [A | B] (list, cons) and append(A, B)
• Use of higher-order functions and predicates, anonymous functions
• Recursion
• Number representations and encodings, conversion from one to another
• Open lists vs. Closed lists, Java implementation
• Iterators, Enumerations
• Stacks, queues
• Object-oriented programming
• Interfaces
• Inheritance
• Abstract classes
• Exceptions
• Copying and equality
• Searching trees and graphs
• McCarthy's Transformation

Second part of the course:

• Languages and Grammars
• Parsing
• Derivation Trees
• Recursive Descent
  
  
• Proposition logic
• Truth table, hypercube, and map representations of functions
• Expressing one function in terms of others
• Sum-of-products form
• Simplifying combinational logic expressions
• Determining whether an expression is a tautology
• Boole/Shannon expansion
• Tautologies vs. Satisfiability vs. Unsatisfiability
• Minterm expansion
• Karnaugh maps
• Don't care conditions
• Circuit implementations of logical functions
• Hardware components
  
  
• Predicate Logic
• Meaning of quantifiers
• Logic programming with Prolog
• Databases
• Recursion
• Backtracking
• Proving programs correct
• Pre- and Post- Conditions
• Partial vs. Total Correctness
• Loop Invariants
• Termination
  
  
• Complexity
• "O" notation for run-time bounds
• Simple algorithm analysis (deriving the run-time, whitebox)
• Running time of loops and nested loops
• Running time through unwinding recurrences
• Sorting programs
• Bucket sort
• Radix sort
• Quicksort
• Mergesort
• Minsort
• Insertion sort
• Heap sort
• Empirical (black-box) analysis
  
  
• Models of Computation
• States and transitions
• Turing Machines
• Finite-State Machines
• Transducers
• Classifiers, Acceptors
• Regular expressions
  
  
• Computer architecture
• Registers
• Combinational logic
• Controllers
• Assembly language