Computer Science 60
Study Guide for the Final Exam
Fall 2010
- Java and Object-Oriented Programming
- What is a constructor and when is it invoked?
- What does this refer to in a
java class?
- What do private, protected,
and public mean and where is it appropriate to
use each of them?
- What are accessor ("getter") methods and why are they
important?
- What is static and where and why
would it be used?
- What is inheritance, why is it useful, and how does it
work?
- Within an inheritance hierarchy, how does Java decide
which out of several overridden methods to actually invoke for an
Object?
- What is polymorphism and why is it useful?
- How are the terms extends, super,
and implements used in Java?
- You should be comfortable with box-and-arrow diagrams
to illustrate how Java organizes references and data in computer
memory.
- When would you choose Java (vs Racket, Prolog or
Python) as an implementation language?
- What is the merge technique and
under what conditions can it be used?
- How do reference counting and mark-and-sweep
garbage-collection algorithms
work? What are the advantages/disadvantages of each?
- How many points per minute is one furlong per
fortnight?
- Data Structures
- What is the difference between an abstract data type
and a data structure?
- How do Java interfaces facilitate the relationship
between ADTs and data structures?
- What operations do the information structures named
Open Lists, Queues, Stacks, and Deques support?
- You should be comfortable with the data-structure
implementation of the above structures using linked lists of cells.
- What are the differences between open lists and closed
lists?
- How do breadth-first search and depth-first search
work? How are queues and stacks used in each of these algorithms? How
can recursion be used to implement depth-first search without
explicitly using a stack?
- What are the advantages of BFS and DFS over each other?
- How do linked lists, binary trees work? In particular, make sure that
you could write
code for each of these data structures and for similar data structures including the more challenging ones
such as
inserting, deleting, and finding data in a binary search tree.
- On the structure of (computer) languages
- What do tokenizing, parsing, and evaluation each
contribute to the execution of a computer program.
- How do grammars and production rules work? How does a
grammar of production rules specify the meaning of a legal expression?
- You should be familiar with how to use recursive
descent in order to parse a list of tokens and how to use recursion to
evaluate the resulting parse tree.
- How does an environment contribute
to the evaluation of an expression? What are free and bound variables
within an expression?
- Logic Programming
- Prolog "programs" are a collection of facts and rules.
Make sure that you understand all of the examples that we saw in class
and on homework.
- Why does prolog sometimes produce multiple identical
answers to a query?
- What is the fundamental algorithm that prolog uses in
seeking bindings that satisfy predicates?
- What is "unification" ? What are the differences among
prolog's =, =:=, ==, and is operators? Similarly,
what are the differences between \+, \==,
and =\=?
- Why does the order in which prolog clauses are placed
sometimes matter to the inference of variable/value bindings?
- What types of problems is Prolog well-suited for?
- You should feel comfortable composing a Prolog solution to a (moderately-sized) problem
similar to the ones we did in class and on the HW.
- What does it mean for a logical statement (that may include variables) to be
satisfiable or unsatisfiable or a tautology?
- You should understand an algorithm that can determine which of the three
categories above a particular logical statement falls under.
- Functional Programming in Racket
- Make sure that you understand and feel comfortable
with Racket's syntax and basic functions like first,
rest, etc.
- You should be comfortable about the differences in the
assumptions that append, list,
and cons make about their inputs.
- Make sure that you can write basic Racket functions
like those developed in lecture and in the assignments. In particular, recursion is the secret to all happiness in
functional programming -- you may want to review decomposing problems
recursively.
- What are anonymous functions and where are they
useful? How is lambda used in Racket?
- What is tail recursion and how can it improve
performance?
- You should be familiar with the Racket higher-order
functions such as map, foldl, and foldr. You certainly don't need to
memorize them, but you should feel like you could implement them and
other higher-order functions from a definition using recursion.
- What are trees, graphs, cyclic graphs, directed
graphs, and DAGS?
- How can objects such as trees and graphs be encoded as
lists? Make sure that you feel comfortable writing Racket functions to
manipulate such objects.
- What is mutual recursion and when is it useful?
- What is the fundamental data structure in Racket?
Be comfortable using it to construct ADTs?
- What types of problems is Racket well-suited for?
- Finite Automata
- What is a deterministic finite automaton (DFA)? What
does the name mean? What is the definition of a regular language?
- Feel comfortable building a DFA for a given regular
language. Remember that the states can encode meaningful information
about what the machine has seen so far.
- What does "distinguishable" mean? What does "pairwise
distinguishable" mean?
- What does the Distinguishability Theorem state? How
can it be used to prove that a specific DFA has the minimum possible
number of states for the language that it accepts?
- What does the Nonregular Language Theorem state? How
can it be used to prove that a given language is not regular? How did
we prove this theorem?
- What is an NFA? What does it mean for an NFA to accept
a string?
- What is a regular expression? Why are regular
expressions useful? How can a regular expression be converted into an
NFA and an NFA into a DFA? How can a DFA be converted to a Regular
expression?
- What are some practical applications of DFAs?