Some tips for Midterm 1

The exam will potentially cover everything we have covered so far, as well as Homeworks 1 and 2 and their answers. (I'll expect you to understand the homework answers, even if the original homework problem was so difficult I wouldn't expect you to solve it; please read and understand the answers we've posted.) There could also be some questions related to Lab A and, to the extent we've discussed it, Lab B. The new material, presented on the last class before the midterm, about designing a good division hash function will not be required for the test, but the material about properties of modular arithmetic covered earlier could be on the test.

The old exams may be useful to you as you prepare. I may reuse some questions or modifications of them. Note, however, that the material I cover varies from quarter to quarter, so there are some questions on old first midterms that would not be appropriate given the material we've covered so far this quarter. Note that for some quarters many years ago we were using C++ instead of Java, so some of the notation may look different; for example where we would say x.next an old exam might say x->next.

In general, it is more important to understand the concepts than memorize a lot of details; of course I do expect you to remember some things. For example, I do expect you to know to know the definitions of the four types of trees we discussed, and how to tell whether, for a given type, two pictures represent the same tree.

I generally try to have a mix of different levels of difficulty in the questions on my tests; there will be some I would expect people to be able to do, but there may be some that I expect most people not to get. Of course, if the test turns out to be hard enough that the average is low, I plan to set the curve appropriately rather than still say 90% is an A, 80% is a B, etc.

Below is a list of some topics we've discussed.

• Introduction and review
  • Mathematical background, such as sums, sets, etc.
  • Notations for growth rates, such as O-, Omega-, and Theta-notation
  • Analysis of algorithms
  • Lists and variations on linked lists, such as list headers, double links, circular links, and pointers to the end instead of the beginning of the list
  • Binary trees
  • Definitions
  • Traversals
  • Expression trees
• Graphs
• Terminology: paths, cycles, connected components, etc.
• Types of trees
• Free trees
• Rooted (or oriented) trees
• Ordered trees
• Binary trees
• Depth First Search and Breadth First Search
• Topological order and task networks
• Graph coloring
• Properties of modular arithmetic (in preparation for hashing)

Below are some examples types of questions I could ask. (I'm not saying, however, that this list covers all types of questions that will be on the test.)

• A question could ask whether given constants would work in the definition to show that some statement involving O-, Omega-, or Theta-notation is true. A more difficult question might be to give a modified definition of one of these types of notation and ask you what the implications are.
• Given examples of code involving some variable n, a question could ask you to indicate the amount of time they use as a function of n.
• A question might ask you to write code using ideas similar to those used in class or on the homework. For example, a question might specify some combination of the variations we saw on lists (header nodes, double links, circular links, pointers to the beginning or end of lists) and ask you to write code to perform some operation on this type of lists.
• A question might ask you to perform some analysis using concepts similar to those used in class or on the homework. I do want you to understand the proofs and analyses we gave. For example, I want you to understand the analysis that showed that DFS ran in O(n+m) time (with an adjacency list representation) and that if all vertices were initially unvisited, DFS(v) would mark all vertices reachable from v.