Computability: Guide for the Final

  1. Define and describe ways to evaluate sorting: time bound, space bound, stability, adaptability, etc.
  2. Describe the merge sort algorithm. Give an informal proof of its complexity.
  3. Describe the heap sort algorithm. Give an informal proof of its complexity.
  4. Describe the bubble sort algorithm. Give an informal proof of its complexity.
  5. Describe the insertion or selection sort algorithms. Give an informal proof of the complexity.
  6. Describe the quicksort algorithms (the two variants: sorting into 2 groups or into 3 groups). Give an informal proof of the complexity.
  7. Describe what is meant by a binary search. Give an informal proof of the complexity. Why is it called 'binary'?
  8. Describe the geography game of the Meyer family. Use the terms ‘dimension’ and search space.
  9. Describe a method for shuffling. Give an informal proof of its complexity.
  10. Give formal and informal definitions of big Oh notation.
  11. Explain why the base of the logarithm is not given in discussions of bounds.
  12. Prove or disprove the following:
  13. log(n) = O(n)
  14. n2 +n = O(n)
  15. log(n) = O(n 2)
  16. 10n = O(2n)
  17. Define and give an example of a verifier for a problem (e.g., Hamiltonian path, factoring).
  18. Define P and NP (note: two definitions for NP).
  19. Describe the P = NP problem and give the current status.
  20. Define what is meant by polynomial time reduction of one problem to another. Give examples.
  21. Define and give examples of problems that are NP-Complete.
  22. Define and give examples of problems that are NP-Hard.
  23. Describe the hierarchy involving: P, NP, PSPACE ,NPSPACE, Exponential Time and indicate what is known and what is not known.
  24. Describe Savitch’s Theorem. Use this to compare and contrast time complexity with space complexity.
  25. Describe the following problems and where they are in the hierarchy: SAT, 3SAT, Exam scheduling, knapsack.
  26. Describe any other NP-complete or PSPACE problem.
  27. Describe and contrast the Traveling Salesman problem and the TSP decision problem.
  28. Recalling the hierarchy (bull’s eye) from the compatibility part of the course (starting with finite state automata and ending with Turing recognizable): show and describe how the two hierarchies relate.
  29. Give the Shannon definition of information. Relate to binary search and the geography game.
  30. Define descriptive complexity. Give informal description.
  31. Describe the Berry paradox.
  32. Summarize someone else’s presentation. Indicate what you found most interesting or surprising.
  33. Who invented the computer? Give arguments for Turing, Atanasoff, Babbage, Ada Lovelace, Mauchly-Eckhart, Von Neumann.
  34. Is history and biography important in the study of computer science or mathematics? Give reasons for and against including history and biography in technical courses.