CS60 Topic
Review Sheet
First half of the course (less emphasis):
- Information structures: lists, trees,
trees as lists, lists as trees, graphs
- Use of higher-order functions and predicates, anonymous
functions
- Use of recursion
- Number representations and encodings,
conversion from one to another
- List manipulation in rex and Java
- Difference between [A, B] and [A | B]
(list, cons) and append(A, B)
- Stacks, queues
- Object-oriented programming
Second half of the course (more emphasis):
- Grammars, parsing
- Derivation Trees
- Recursive Descent
- Tautologies vs. Satisfiability vs. Unsatisfiability
- 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
- Minterm expansion
- Karnaugh maps
- Don't cares
- Predicate Logic
- Meaning
of quantifiers
- Logic programming in Prolog
- Ascertaining program correctness
- Loop Invariants
- Energy Function
Complexity
- "O"
notation for run-time bounds
- Simple algorithm analysis (deriving the
run-time for a program)
- Running time of loops
- Running time through unwinding recurrences
- Sorting programs
- Bucket sort
- Radix sort
- Quicksort
- Heap sort
- Mergesort
- Empirical analysis
Finite-State Machines
- Deterministic Finite Automata
- Nondeterministic Finite Automata
- Regular expressions
- Languages which aren't regular.
- Implementing a sequential finite-state machine
with combinational logic and flip-flops or registers