CSCI C243 Midterm Review

Version 8.3¹

Overview

See Oncourse Modules for exam locations and dates.

There will be a mixture of question types, possibly including multiple choice, true/false, short answer, essay, and coding. Each student will be allowed one letter-size (8.5x11 inch) sheet of notes for reference, which may be filled on both sides. Calculators may be used during the exam, but probably will not be needed.

Notation conventions: [a, b, c] represents an array; a is the element at index 0; the size (length) of the array is 3. (a, b, c) represents a list with a at the front; the size of the list is 3; the list might be either linked or array-based, and if array-based, the array storing its elements may have 3 or more elements.

Main themes: object-oriented design, Java language, linear data structures, algorithms.

* = question recommended for in-class review.

A Java Language

See Appendix A.

Basics of using the Java programming language: Unix shell commands to compile and run programs; Java code to define classes, declare interfaces, declare variables, define and call methods, use arithmetic expressions and control structures (if, while, for), and use exceptions (try/catch, throw, throws).

What is garbage collection? How does it make a programmer’s life easier?

1 Encapsulation

Encapsulation is “division of a program into distinct components which have limited interaction.” Information hiding = enforcement of encapsulation. Why are encapsulation and information hiding considered to be good things? How do classes, methods, and access levels in the Java language support encapsulation and information hiding?

2 Polymorphism

Polymorphism = “the ability of a word or symbol to mean different things in different contexts.” Explain how these features of the Java language support polymorphism: the Object type, array types, interfaces, and overloading.

Distinguish between primitive and reference types. What is the null reference? What are wrapper classes, autoboxing, and (auto)unboxing?

Distinguish between interfaces and classes.

3 Inheritance

Inheritance is the passing down of traits (fields and methods) from parent (super, base) classes to child (sub, derived) classes. Name the top class in the Java inheritance hierarchy. Distinguish between “is a” and “has a”.

Distinguish between “overriding” and “overloading”. Why do we commonly override the Object class methods equals and toString?

Know how to use the reserved words extends, super, public, protected, private. Distinguish between the four levels of access in Java, including the default “package” access level.

4 Stacks and Queues

Name and describe the operations of the Stack interface. Trace the state of a stack through a series of push and pop operations. Describe the role of stacks in executing method calls, including recursive methods.

Name and describe the operations of the Queue interface. Trace the state of a queue through a series of enqueue (add) and dequeue (remove) operations. Know the terms “enqueue” and “dequeue”.

Using Exceptions and “generic” (parameterized) types in Java.

1. Starting with an empty stack, execute the operations: push(A); push(B); push(C); x = pop(); y = pop(). What are the values of x and y?
2. Starting with an empty queue, execute the operations: enqueue(12); enqueue(16); enqueue(84); x = dequeue(); y = dequeue(). What are the values of x and y?
3. Demonstrate how a stack is used to evaluate the postfix expression 70 10 * 3 4 + /. (List the stack operations and show the result.)

5 Array-Based Structures

Describe the array-based implementations of Stack and Queue, the interface List, and the array-based list. Shrinking and stretching of array-based structures. Iterators: motivation; their methods hasNext, next, and remove. The “enhanced” for statement.

1. Sketch the array-based representation of a stack with elements (from top to bottom) A, B, C.
2. Sketch the array-based representation of a queue with elements (from front to back) 10, 30, 60, 45.

3. Here is an array-based queue:

   front	size	data
   6	4	0 7 42 77 89 62 23 17 19 44

   1. List the queue’s elements, from front to back.
   2. Show how the representation changes with these operations: enqueue 18; dequeue.

4. Here is an array-based representation of the list (10, 15, 44, 90, 72):

   size	data
   5	0 7 10 15 44 90 72 ? ? ?

   For each operation, describe the steps to perform it, and sketch the resulting data structure:
   1. Insert 95 at position 3 (between 44 and 90).
   2. Remove the element (15) at position 1.

6 Linked Structures

Varieties of linked list: single or double link, circular. Advantages/disadvantages of linked lists compared to array-based lists; of doubly linked lists, compared to singly linked. List nodes, the LinkedStack, LinkedQueue, and LinkedList classes. “Two-finger” algorithms for inserting and removing items in a singly linked list.

The functional (recursive, immutable) approach to lists (actually, to the chains of nodes inside lists).

1. Sketch the linked representation of a stack with elements (from top to bottom) A, B, C.
2. Sketch the linked representation of a queue with elements (from front to back) 10, 30, 60, 45.
3. State the recursive definition of list.
4. Critically evaluate Java as a language for functional-style list processing.

5. Given a functional List class with operations cons(Object head, List tail), head(List chain), tail(List chain), and with the empty list represented by null, complete the following recursive method definitions. Note that the methods are static and take a List argument; so we would write, for example, cons(x, xs) instead of xs.cons(x).

   public static int length (List list) {
     // returns the number of elements in this list
     if (list == null)
       ...
     else
       ...
     }
   
   public static List replace (Object old_item, Object new_item, List list) {
     // returns a new list in which the first occurrence of old_item in the
     // original list, if any, is replaced by new_item; otherwise, a copy
     // of the original list.
     if (list == null)
       ...
     else if ...
       ...
     else
       ...
     }
   
   public static List remove (Object item, List list) {
     // returns a new list which is the given list with the first occurrence
     // of item, if any, removed; otherwise a copy of the list
     if (list == null)
       ...
     else if ...
       ...
     else
       ...
     }

6. Sketch the list (Alfy, Barb, Carla, Dave) — (a) as a singly linked list; (b) as a doubly linked list, (c) as a singly linked circular list.
7. Show and describe the steps of inserting Edwin in the list (Alfred, Barb, Carl, Dave, Fred, Giulia) — (a) in position 2; (b) just before Fred.
8. Explain how to modify the ListNode class, page 159, for use in defining a doubly linked list class.

9. Define an iterative method for the LinkedList class, p. 168 ff., to compute the sum of a list of Integers.

7 Analysis of Algorithms

Be able to analyze the running time of a structured algorithm, stated in pseudocode, or a Java method. The algorithm may use any of the following control structures: sequence, selection, and iteration. Structures may be nested (e.g., nested loops or conditionals).

Know the names of common orders of functions (such as linear and quadratic, page 187) and be able to compare them. For example, is Θ(N²) higher or lower order than Θ(log N)?

Simplify running time functions using asymptotic notation Θ.

Distinguish between best, worst, and average case running time. Distinguish amortized from worst and average case.

Why do we need both theoretical analysis and empirical measurement of running time?

1. Analyze the worst case running time of the pseudocode fragment below:

   read N
   sum = 0;
   if N > 10:
     loop for i from 1 to N:
       loop for j from 1 to N:
         loop for k from 1 to N:
           sum = sum + (i * j * k)
         end loop
       end loop
     end loop
   else:
     loop for i from 1 to N:
       sum = sum + i
     end loop
     sum = 2 * sum
   end if
   write sum

2. What is the order of the function 20 N⁵ + 100 N³ + 55 N? Use Θ notation in the simplest form.

8 Searching and Sorting

How do linear search, binary search, and insertion sort work? What are their running times?

The Comparable interface: motivation and use; the compareTo method.

1. Show the steps of linear search for 24 in the array [10, 12, 17, 21, 24, 27, 31, 39]. Show the steps for binary search.
2. Trace the algorithm insertion sort on the array [55, 49, 27, 300, 185, 211]. (Show the array after each pass through the main loop.)

9 Recursion

Be able to: name and describe the two required parts of a recursive algorithm; trace the execution of a recursive algorithm; describe sources of inefficiency in recursion; discuss tail recursion and its elimination.

Be able to set up the recurrence relation (not necessarily to solve it!) for the running time of a recursive function (or method). Be able to give an intuitive analysis of running time for simple cases.

How do merge sort and quicksort work? What are their running times?

Avoiding recursion: why, when (and when not), and (for tail recursion), how?

1. Show the steps of evaluating the method call barber(21); given the recursive method definition:

   int barber (int n) {
     if (n < 1)
       return 0;
     else
       return 2 + barber(n - 4);

2. Using the definition below and the array A = [5, -4, 7, 6, 12, 19, 7, 8, 9], trace the call maxArray(A, 0, 8).

   public static int maxArray(int [] A, int lo, int hi) {
     if (hi == lo) 
       // Array has one item; return it
       return A[lo];
     else {
       // Find max of each half, and return the larger
       int mid = (lo + hi) / 2;
       int maxLeft = maxArray(A, lo, mid);
       int maxRight = maxArray(A, mid + 1, hi);
       if (maxLeft > maxRight)
         return MaxLeft;
       else
         return maxRight;
     }
   }

3. *Set up the recurrence relations for barber and maxArray (from the previous two questions). Analyze the running time for barber, either by solving the recurrence relation or through informal reasoning.

4. *For the array [55, 49, 27, 300, 185, 211, 99, 85, 42, 150], trace the execution of (a) merge sort; (b) quicksort, pivoting on the last element. “Trace” here means show the array segments on entering and returning from each recursive call.