Mid-Term Exam Study Guide

Plan

The mid-term exam is scheduled in the Testing Center (see the course schedule). You will have a 3 hour time limit. The exam is closed book, and you may have one page of notes handwritten or typed by you – both sides of the page can be used. Your notes may not include any material pasted in from other resources. No calculators or digital assistants (you won't need one). I think a well-prepared student will be able to complete the exam in two hours. You’re going to do well!

The format is short answers, worked mathematical solutions, and possibly some T/F or multiple choice.

You will be expected to show your work. You will be graded not only on the correctness of your answer, but also on the clarity with which you express your rationale for your answer; plan to be neat. It is your job to make your understanding clear to us; non-neat work is likely to earn a lower grade. If using a pencil (rather than a pen) helps you be neat, please plan accordingly.

Study

I recommend the following activities to study the topics covered by the exam:

  • Review the lecture notes and identify the topics we emphasized in class. Focus on those listed below. Prepare your one page of notes, handwritten or typed by you. This process will probably be your best preparation.
  • Compare the homework solution keys to your homework assignments, and make sure that you understand the major principles covered in the homework problems. The difficulty of homework problems is generally a good gauge for exam problems.

Topics

The exam will cover a subset of the following topics:

  1. Main ideas: Problems, problem instances, solutions, algorithms
  2. Orders of growth
  3. Distinctions among best case, average case, and worst case
  4. The roles of empirical analysis and theoretical analysis
  5. Asymptotic notation: formal, mathematical definitions of big-O, big-Theta and big-Omega
    • A “formal, mathematical” definition is a precise definition employing mathematical notation (not English or some other natural language).
  6. Applications of the definitions of asymptotic notation
  7. The Limit and Max rules. L'Hopital's rule will also be useful sometimes when using the Limit rule.
  8. Modular exponentiation, esp. the key ideas that make modular exponentiation efficient
  9. Euclid’s Algorithm for Greatest Common Divisor and its efficiency
  10. Fermat primality tester and its efficiency
  11. RSA Public-key Cryptography
    • how algorithm analysis informs its security
    • NO manual computation using the Extended Euclid Algorithm, including NO computation of multiplicative inverses modulo N
  12. Analyzing divide and conquer algorithms using the “Master Theorem”
  13. Analysis of Mergesort
  14. Quicksort, the pivot selection problem and the worst-case behavior of quicksort
  15. Deriving the big-O (upper) bounds for certain kinds of divide-and-conquer algorithms using the methods for solving recurrence relations covered in class. This will involve knowing some logarithm and exponent identities.
    • Homogeneous Recurrence Relations
    • Non-homogeneous Recurrence Relations (only with geometric forcing functions)
      • The characteristic equation theorem
      • Roots with multiplicity
    • Divide and Conquer-style Recurrence Relations requiring Change of Variable.
  16. Formulating problems as graphs
  17. Depth-first search and connected components; the broader usefulness of DFS; its efficiency
  18. Linearization of a DAG (i.e., topological sorting)
  19. Finding strongly connected components
  20. Shortest path(s) problem
  21. Breadth-first search
  22. Dijkstra’s algorithm and shortest paths on undirected graphs (with positive weights)
  23. NOT the Bellman-Ford algorithm
  24. Importance of data structure choice in efficiency of algorithms
  25. NOT the details of a Fibonacci heap
  26. Six steps to formulating a dynamic programming algorithm
    • Extracting solutions from Dynamic Programming tables
    • Optimality property and Dynamic Programming
  27. Dynamic programming: making change (coins with infinite supply)
  28. (Gene) Sequence alignment using Dynamic Programming
  29. Choosing suitable problem solving strategies for new problems
cs-312/mid-term-study-guide.txt · Last modified: 2015/04/17 13:35 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0