EXAM QUESTION TYPES

This is a list of some of the questions you may have to answer at test/exam time. Questions further down the list are probably more difficult.

  • Define the following terms: X, Y, Z. [The terms may be concepts specific to particular problem areas.]
  • Define what a XXX is and give an example.
  • What is the output of algorithm XYZ on input UVW? [Here and in all other questions algorithm XYZ may be just mentioned or given explicitly in pseudo-code]
  • Simulate algorithm XYZ on the following input sequence. [You need to describe how the algorithm works mentioning intermediate results, etc]
  • Compute the asymptotic complexity of the following piece of pseudo-code.
  • Give an example input for which algorithm XYZ takes Omega(n log n) time.
  • Give an example input for which algorithm XYZ uses Omega(n log n) space.
  • Give a (convincing) argument proving that the asymptotic complexity of the following piece of pseudo-code is O(nm).
  • Prove the correctness of algorithm XYZ (this can only be one of the proofs we have done together). [For this type of exercise a clear understanding of the argument is much much more important than remembering all the details]
  • Write an algorithm to solve the following problem ... [This should be based on either one of the paradigms we looked at during the lecture, or on a straightforward adaptation of the various algorithms we looked at]