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
- Predicate Logic
- Meaning
of quantifiers
- Logic programming with Prolog
- Proving programs correct
Complexity
- "O"
notation for run-time bounds
- Simple algorithm analysis (deriving the
run-time for a program)
- Running time of loops and nested loops
- Running time through unwinding recurrences
- Sorting programs
- Bucket sort (Counting sort)
- Radix sort
- Quicksort
- Mergesort
- Minsort
- Insertion sort
- Empirical analysis
Finite-State Machines
- Deterministic Finite Automata
- Nondeterministic Finite Automata
- Regular expressions
- Turing Machines
- Limitations of DFAs and TMs
- Minterm expansion
- Karnaugh maps
- Don't cares
- Implementing logical functions with circuits
- Implementing DFAs with circuits and flip-flops
Assembly Language (Extra Credit)