CS136 Midterm Study Guide

Midterm Exam Format

The midterm exam will be administered as an assignment on GLOW. You will be given a 5-day window (Wednesday 4/8 to Sunday 4/12), and you may choose any time within that window to begin taking the exam.

Once you begin taking the exam, you will have 3 uninterrupted hours to work the exam. Here is what that means:

The time that you actively work on the exam should not exceed 3 hours; this time limit does not include any time spent resolving technical difficulties. We understand that technical difficulties are not only possible, but in a class as large as ours, it is likely that someone will experience a technological issue that is outside of their control. That is OK. If you are disconnected or if you have some other issue, please do the following:
- Roughly document the issue in a few short sentences (e.g., approximately when did the issue occur, what did you observe, what led to the issue, how did it affect your exam-taking, etc.). We would like to know these details so that we can fix the issue in the future (if possible), and also ensure that we take appropriate steps to prevent you from being negatively affected by it. When you submit the exam (or decide you are unable to resolve the issue on your own), email us your description.
- Once you/we are able to resolve the issue, continue taking the exam and resume your 3 hour “timer”. Do not stress out; we trust you to do the right thing, and that means you can use your judgment.

The exam is closed-book, closed-notes. We will provide relevant interfaces and implementation details as part of the exam when appropriate. Our goal is to test your understanding, not your memorization.

You may perform calculations and/or draft answers on scratch paper, but we cannot grade this work. Please make sure that the answers you submit represent the work that you would like us to consider.

For all questions you are allowed to write Java code from scratch, compile, and run your code to determine your answer. However, you must not access any other code (even if you are the author of the code) while taking the exam.

Midterm Exam Material

The exam may include anything we covered in class or in lab up to and including Sorting, and everything in the assigned reading from Java Structures. That is, Chapters 1-7 and Chapter 9, as well as the handouts posted on the course webpage.

Key Course Topics

The following non-exhaustive list may be helpful to recall some of the key topics we have covered:

Java syntax, compilation, and debugging, as covered in our programming assignments.
Classes (both concrete and abstract) and interfaces, and the roles that concrete classes, abstract classes, and interfaces play in program design.
Information hiding (abstraction as a concept) and why it is good.
Extending classes with inheritance.
Generic classes (e.g., Vector<E>, Association<K,V>, SinglyLinkedList<E>, etc.) and their use
Pre-conditions, post-conditions, and assertions.
The meaning of static (and non-static) as applied to variables and methods
Vector, its implementation in the structure5 package, and its methods.
Complexity: Big O definition.
- Determining the asymptotic behavior of mathematical functions
- Determining the time and space complexity for a given algorithm/piece of code.
- Worst and best case analysis (and why they might differ).
Recursion and induction.
Sorting.
- A working understanding of the Bubble sort, selection sort, insertion sort, merge sort, and quicksort algorithms
- Using Comparator classes and the Comparable interface for sorting.
Linked lists: Singly, Doubly, and Circularly linked lists.
- Note In the Linked List lab, we modified the standard doubly linked list implementation by adding ``dummy nodes’’. You should be familiar with the standard implementation as described in class and in the textbook (i.e., lists without dummy nodes).