CS 201: Topics for exam 1

This is intended to give you a sense of what I think is important from the course so far, and what I will be thinking of when creating the exam.

I hate disclaimers, but here are some anyway. This is not a contract. I may have inadvertently left something off this list that ends up in an exam question. I make no guarantees that the exam will be 100% limited to items listed below. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.

You are permitted one 8.5 x 11 sheet of paper with notes (both sides) for use as a reference during the exam.

Here are the specifics: Students should be able to...

Write Java code to solve specified problems. Specific examples may be:

• Take input from a user and do something with it
• Appropriately use loops and conditionals ("if")
• Write object-oriented Java code. Appropriately use classes, objects, methods, parameters, instance variables, and constructors.
• Use inheritance. Appropriately use interfaces, abstract classes, and subclasses. Be able to correctly predict what results that sample code using the above produces.

Look at Java code or pseudo code and accurately count the number of times that something executes. Use the fact that successive divisions in half is logarithmic. Use big-O to represent answers appropriately. Use definition of big-O in order to show that one expression is O(another). Compare different big-O quantities (n², log n, 2ⁿ, etc) and be able to rank them relative to each other. Determine the big-O description of an algorithm described.

Implementation tradeoffs: Be able to justify when arrays (or ArrayLists) are appropriate vs. linked lists. Be able to do this quantitatively with big-O descriptions.

Be able to construct Java code or pseudo-code to implement linked lists or other similar structures (doubly linked lists, or something else I come up with) according to specification. Be able to use generics appropriately.