Exam Topics
This is a list of some topics we have covered that you should think
about for the first exam. The exam will be designed to take 90
minutes. You may use one page of handwritten notes. The use of other
reference materials or electronic devices is a violation of the honor
code. To be fair to everyone, papers will be collected promptly when
time expires. Plan accordingly. This exam counts as 15% of the
course grade.
Generally, you are responsible for anything we covered in class or in
lab, and everything in the assigned reading from Java
Structures, up to and including class on October 15 and Lab 5. Be
sure you know how to do the assigned homework problems and programs.
- Java syntax, as we have used it in our programming assignments.
Classes, abstract classes, interfaces.
- Java memory management. What is allocated and how when regular
variables, arrays, and instances of classes are created?
- Information hiding and why it's good.
- Extending classes: Inheritance.
- Pre- and post-conditions. Assertions.
- class Vector, its implementation in the structure package,
and its methods.
- Complexity: Big "O" definition, determining for a mathematical
function, determining for a given algorithm, worst, average, and best
case analysis, both time and space complexity.
- Searching. Linear and binary.
- Recursion and induction. Proving correctness and complexity of
a given function or algorithm.
- Sorting. Bubble sort, selection sort, insertion sort, merge
sort, quicksort, radix sort. Using Comparators and/or Comparables for sorting.
- Iterators.
- Linked lists.
