http://www.cs.caltech.edu/~ps/questions.html
and included below for the curious.
-- Adam
GRAPHICS
--------
1. Explain the causes of aliasing and ways to mitigate
it through anti-aliasing techniques. (see CS174
Fourier Handout)
2. Digital filtering. Why are negative lobes essential?
Lanczos filter, Hamming filter.
3. What is the Sampling theorem?
4. What is the surface rendering equation? Discuss
raytracing and radiosity as instances of
approximately solving it. (Jim Kajiya, "The Rendering
Equation," Computer Graphics, Siggraph 1986
Proceedings, pp. 143-150)
5. What is the equation for volume rendering? Is it
covered by the rendering equation?
6. Piecewise polynomial curves can be analyzed with the
help of their blossom or polar form. Discuss it and
show how it can be used to explain the de Casteljau
algorithm. (Hans-Peter Seidel, "An Introduction to
Polar Forms.")
7. What is inverse kinematics?
8. What is volume rendering? How can Bresenham's
algorithm be used for volume rendering? How can
texture mapping hardware and alpha compositing be
used for it?
9. Describe a spatial search data structure such as one
might use to accelerate ray tracing.
10. How are homogenous coordinates useful in computer
graphics? Describe the entire transformation pipeline
from object local space to screen space.
11. Local shading models describe how light interacts
with a surface. Discuss the shading models of
Lambert, Phong, and Cook-Torrance.
12. What is a quaternion? Discuss applications of
quaternion algebra in computer graphics.
13. What are the equations of motion for rigid bodies,
and descriptions of each of the terms?
14. What is the generalized material balance law
equation?
15. Vision: What is the "aperture" problem? What is the
"correspondence" problem?
Answers to the above questions can be found in Foley, van Dam, Feiner,
Hughes, "Comptuter Graphics: Principles and Practice," Addison-Wesley,
and Watt, "3D Computer Graphics,", Addison-Wesley.
NUMERICAL ANALYSIS
------------------
1. What is Neville's Algorithm?
2. Explain Gaussian integration rules and how they are
constructed.
3. What is the LU decomposition? Why is pivoting
important?
4. Discuss the SVD and its applications.
5. Describe the conjugate gradient method for the
solution of linear systems.
6. Explain the concepts of ill-posed and
ill-conditioned.
7. What is a least squares approximation and how can one
compute it?
8. Root finding: Explain Newton's method and discuss
numerical issues associated with root finding.
9. What is the Jordan form of a matrix.
10. Discuss methods to solve ODEs.
11. Discuss the Laplace equation and how one might solve
it in 2 dimensions.
12. What is preconditioning? Give an example.
13. What is the pseudo-inverse of a matrix? How is it
computed? How is it used?
14. Consider the linear system Ax = b. If A and b are
perturbed, how does the solution x vary?
15. Discuss the relative merits of the following methods
for computing eigenvalues: power method, inverse
power method, QR method.
16. Are direct methods ever used for solving general
eigenvalue problems? Why or why not?
17. How does the finite element method work?
18. Elementary probability. What is conditional
probability? Independence? A Markov process?
19. Describe methods for soft constraint, Lagrange
multiplier methods for hard constraints, constrained
optimization solution methods.
20. What is a functional? What is the Euler-lagrange
equation?
21. What is Arrow's method for constrained optimization?
22. What are regularization principles for optimization?
23. What is the Convolution theorem? How can it be used
to solve linear PDE's?
Answers to the above questions can be found in Bulirsch and Stoer,
"Introduction to Numerical Analysis," Springer.
CONTINUOUS MATH
---------------
1. Describe manifolds, atlas, coordinate charts ...
2. What is a tensor and how does it differ from other
coordinate-independent mathematical objects?
3. What is the jacobian matrix, hessian matrix of a
transformation?
4. What is the geometric interpretation of the jacobian
determinant of an n-d transformation? What is the
change-of-variables rule for N-dimensional
integration?
5. What are the differences between unsigned and signed
curvature? What is gaussian curvature? Under what
circumstances are the principal components of
curvature orthogonal? What is the curvature tensor?
6. What is the difference between cartesian tensors and
general tensors? What is the difference between a
covariant transformation and contravariant
transformation?
7. What is a Christoffel symbol?
8. What is a geodesic and how do you compute it?
9. What is the N-dimensional chain-rule of
differentiation?
10. What is the N-dimensional generalized Stokes theorem?
11. What is the N-dimensional Integral mean-value
theorem?
12. What is the exponential form of N-dimensional
rotation matrices?
13. What is the equation for angular velocity in N
dimensions? What is its geometric interpretation in N
dimensions? What is the equation for angular
velocity, for quaternions?
THEORY
------
1. Boolean functions:
o prove associativity, commutativity,
distributivity, DeMorgan's rules, absorption
rules and substitution of constants;
o prove that AND, OR and XOR are symmetric
functions; prove that a boolean function is
symmetric if and only if it can be expressed as
a function of the number of 1's in the input;
prove that there are exactly 2^{n+1} symmetric
functions in n variables;
o Prove that there are n! permutations of the
integers from 1 to n; construct a k by k
symmetric matrix for k arbitrary so that every
row and every column is a permuation of the
integers from 1 to k; prove that for an
arbitrary such matrixh the diagonal of it is
also a permuation if k is odd;
o Given computing elemenst SQUARE, ADD, and SUB
opeating on integers; prove that Z=X^2 for
arbitrary X implies the zoro order bits of X and
Z in binary to be equal and the first order bit
of Z to be 1; show how to compute the product of
two integers using a circut that consists of the
compute elements ADD, SUB, and SQUARE.
2. Computability:
o What is a Turing machine?
o What is the difference between a finite
automaton and a Turing machine.?
o Describe a Turing machine that will print 1 and
halt if the input string is a palindrome.
3. Information theory: A person rolls two fair dice and
records the total number of points. We are to ask a
sequence of yes/no questions to find out this number.
The answer to a question may affect our choice of the
following questions. Devise, in detail, a strategy
that achieves the minimum possible average number of
questions.
4. Learning systems: Given a feed-forward neural
network, and set of training input and outputs,
o describe how gradient descent is used to to
teach the training inputs to the neural network.
o Describe what backpropagation and momentum are.
How does momentum help in optimization?
5. Learning systems:
o What is overfitting?
o What is early stopping?
o What is regularization?
o Describe why and how weight decay works as a
regularization method.
6. Learning Systems:
o What is the VC (Vapnik-Chervonenkis) bound and
the VC dimension for a learning model?
o Let the input space be the real numbers. Find
the VC dimension of a learning model with that
outputs 1 if its input lies in either one of two
arbitrary intervals, and 0 otherwise.
7. Learning Theory: Consider the training input-output
set {([1,0], -1), ([0,1], -1), ([0,-1], -1),
([-1,0],1),([0,2],1), ([0,-2],-1)}, where for each
element the first two numbers are inputs, and the 3rd
number is the output.
o Plot the decision boundary of the
nearest-neighbor rule.
o What is the difference between a
nearest-neighbor classifier and a radial basis
function network?
8. Show that 3SAT is in NP-complete, but 2SAT is in P.
9. What is the Church-Turing thesis? What is the
supporting evidence?
10. Give a polynomial-time algorithm for determining
satisfiability of Horn expressions. Can it be done in
linear time?
11. What is the "word problem"? In what sense is it
unsolvable?
12. Show that the "Post correspondence problem" is
undecidable.
13. What does it mean for the predicate calculus to be
complete? How is this proven?
14. Show that the satisfiability problem in the predicate
calculus is semi-decidable.
15. What are the following classes of languages? How are
they related? Regular, context free, decidable,
undecidable, recursively enumerable.
16. What is a finite-state machine, a Turing machine, a
push-down automata, a context-free grammar?
17. What is the Church-Rosser theorem? What are its
implications?
18. Describe the following methods for solving problems
in SAT: truth table, Davis-Putnam procedure,
resolution. What are their relative merits?
19. What is the "most general unifier" of two predicate
formulas? How is it used?
20. What is the minimum number of states required to
build a univeral Turing machine?
21. How does non-determinism affect the set of languages
accepted by the following classes of abstract
machines: finite automata, push-down automata, Turing
machines.
22. What is Cantor's diagonalization argument?
23. What does computability mean? Give an example of a
function that is not computable and show how you
would prove that it is uncomputable.
24. What is meant by the halting problem and why is it
important?
ALGORITHMS
----------
1. Show that the geometric separation problem is in
NP-Hard by reduction from PARTITION or KNAPSACK. Is
it also in NP-Complete?
2. Give a Theta(n log(n)) algorithm for computing 2D
convex hulls. How does the asymptotic complexity of
the problem increase with dimension?
3. Show that the convex hull of a simple polygon can be
computed in linear time. How can this be used to
efficiently compute the diameter of a collection of
polygons?
4. Describe the branch and bound strategy and give a few
examples of its use. Use the strategy for a problem
that's given to you.
5. What is the dynamic programming strategy? Use the
strategy for a problem that is given to you.
6. What are greedy algorithms. Give examples, and use it
to solve a problem given to you.
7. Explain alpha-beta search and its use.
8. Basic algorithms: graph algorithms such as
breadth-first and depth-first search, topological
sort, connected components, shortest paths, and basic
network flow. String-matching, FFT, and convex hull.
9. What does it mean to say that a problem is in P or in
NP? What does it mean to say that a problem is
NP-complete? What are the central ideas in Cook's
theorem? Show how you would prove that a problem
given to you is NP-complete.
10. What are properties of different types of sorting
algorithms?
PREDICATE CALCULUS, PROGRAM SEMANTICS, COMPLEXITY
-------------------------------------------------
1. What is the state of a sequential program, a parallel
program? iean? a predicate? a Hoare triple? weakest
precondition?
2. What is the weakest precondition for an assignment
statement? For example, what is wp(x := x + 1, x > 1)?
3. How do you prove the correctness of a conditional
statement? an iteration statement? What does an
assertion in the program text mean?
4. What is a deterministic program? A non-deterministic
program?
5. How is induction used in proofs?
6. Prove the correctness of simple programs.
7. What is meant by program complexity? What do O(n),
o(n) mean? What do worst case and average case mean?
Determine the complexity of trivial programs such as
mergesort.
8. Elementary data structures: How would you implement
and use linked lists, stacks, queues, trees, binary
search trees, red-black trees, B-trees, graphs.
CONCURRENT SYSTEMS
------------------
1. What are some classic solutions to the deadlock
problem of concurrent computation?
2. How is this solution relevant to digital hardware?
3. What is an action system? What is meant by fairness?
What does interleaving semantics mean? What is meant
by "safety" and "progress"?
4. What does "p next q is a property of system S" mean?
What does "p leads-to q" mean? What is an invariant
of the system? How would you prove the correctness of
a simple algorithm?
5. What are the issues that determine the performance of
a multithreaded system? a message-passing system?
Develop concurrent programs for simple problems.
6. What is a semaphore, a monitor? Design simple
concurrent algorithms such as for readers-writers or
mutual exclusion. Here we do not require you to know
specific algorithms, but we are interested in your
ability to use basic concepts to develop algorithms.
7. Communication protocols: What is meant by a protocol
stack? How does it help in reasoning about the
correctness of the protocol? What are standard
protocol stack layers?
8. What is the alternating bit protocol? How would you
prove its correctness? What is meant by sliding
window protocols? What are the issues that determine
the performance of such protocols?
9. What are the TCP and UDP protocols for the internet?
How are they different?
10. Security and Authentication: What is the RSA
algorithm? What does public key encryption mean? How
are public key and private keys different? How are
they used in authenticating an object?
HARDWARE
--------
1. What is a CMOS transistor?
2. Why is voltage sometimes more useful for
communication, and current more useful for
computation, in analog chips?
3. Describe a basic inverter in CMOS.
4. Construct basic combinatorial gates in CMOS.
5. What are state-holding operations and how do you
build them?
6. What is threshold voltage and how does it affect CMOS
behavior?
7. What is the "subthreshold" level and how is it
relevant for analog VLSI computation? (mead analog
book).
8. What is gain? Why is it important?
9. What is the tau model? How is it used?
10. Describe basic clocking schemes.
11. What is a PLA?
12. Where does the energy go in a CMOS circuit?
13. What is an arbiter? What is the problem with using
arbiters?
14. What is clock skew? Why is it a problem?
15. Describe an asynchronous handshake protocol?
16. Describe an asynchronous and delay-insensitive
handshake protocol with data communication.
DATABASES AND DIRECTORIES
-------------------------
1. What are the basic kinds of database structures
(relational,hierarchical,..)?
2. How is the relational algebra used in designing
languages for querying/updating databases?
3. What are the issues that need to be considered in
replicating data at different sites?
4. How does the domain name server work for the
internet?
PROGRAMMING LANGUAGES
---------------------
1. What is an abstract data type? What is the
relationship between abstract data types and objects?
What is meant by inheritance? polymorhism?
Overloading? Over-riding?
2. What is meant by a "functional programming language."
What are its advantages? Design programs for simple
problems in a functional language. What is meant by a
"logic programming" language? What are its
advantages?
3. What are continuations? What does lazy evaluation
refer to?
4. Give an example of a program or data structure which
is easy to do with continuations or in a language
which supports lazy evaluation, but would be very
hard to do in languages not having these features.
Last modified: Wed Feb 11 14:31:14 PST 1998
----
adam@cs.caltech.edu
The candidate should be able to leap tall buildings, outrun speeding
bullets and be able not only to forsee the future, but control it.