Link Search Menu Expand Document
Uni Notes

Exam Notes

CSE 143

Table of contents
  1. Midterm
  2. Ye Recursive Diagramming Form

Midterm

  • On ArrayIntList problems, always make sure to deal with the size field.
  • On recursive tracing problems, use Ye Recursive Diagramming form (see below).
  • Remember to write exception-throwing code early on.
  • Always terminate linked lists for node manipulation problems, just in case.
  • If you’re modifying a stack or queue in a list based on the size, be careful of using .size() in the loop - instead, save it to a variable.
  • Read closely and don’t forget about returns.

Tips from Khushi Chaudhauri, TA of CSE-EG:

  1. ArrayIntList
    • Don’t forget to change the size field!
    • Walk through general and edge cases
  2. Collection Programming
    • Remember you can’t modify contents of the object while you’re are loop through with a for each loop
    • Difference between hash vs. tree (speed vs. order)
    • Look over the cheat sheet to know which methods are associated with which object
  3. Stacks and Queues
    • Draw pictures!
    • Know the common patterns: reversing stacks and queues, merging things together or splitting.
    • If you’re stuck, try moving things from one data structure to another and see what happens
  4. LinkedList Node Manipulation
    • Draw pictures!
    • Remember to do a quick walk through with your code after writing the code.
  5. Recursion Tracing
    • Do the first couple and you might be able to spot a pattern which may save some time
  6. Recursion Programming
    • Think about the base case and recursive case
    • How can you break the problem into a smaller problem for the recursive case?
    • Understand how recursion works with both string and integer problems
    • Draw out different outputs for different parameters to see what the pattern could be

Ye Recursive Diagramming Form

I have very humbly branded my own recursive diagramming organization scheme. Using this organization format, I have consistently obtained correct results.

Consider the following recursive function (indicative of many recursive tracing problems on the CSE 143 midterm exam):

public void mystery(int x, int y) {
  if (y <= 0) {
    System.out.println("0 ");
  } else if (x > y) {
    System.out.print(x + " ");
    mystery(x - y, y);
  } else {
    mystery(x, y - x);
    System.out.print(y + " ");
  }
}

Let’s say we are asked to trace mystery(6, 3). We begin with a ‘starting note’:

(6, 3)

In this case, 6 > 3. We enter the second condition in which we first print an output, then recurse. We can diagram this by drawing a horizontal arrow with the printed output, then a vertical line down from that output to indicate the recursion occurs after the output is printed.

(6, 3) → 6
         ↓
         (3, 3)

The recursed case is (3, 3), so we connect it vertically. This call falls under the third condition, in which we recurse first, and print second. We draw a horizontal arrow with the printed output, but draw the vertical line to the next recursed case directly under the call (rather than the output) to indicate it is performed first.

(6, 3) → 6
         ↓
         (3, 3) → 3
         ↓
         (3, 0)

The last output is a base case; the only output is 0.

(6, 3) → 6
         ↓
         (3, 3) → 3
         ↓
         (3, 0) → 0

To trace the output, we begin by traversing from the very first call ((6, 3)) to the terminal output (0). If we encounter any outputs along the path (e.g. 6), we print it out in order. If it is a ‘dead end’ (e.g. 3 in (3, 3) → 3), we print it in opposite order ‘going back’ after we reach the terminal output 0. Going forward, we have (6, 3) → 6 → (3, 3) → (3, 0) → 0. Going backward, we have 0 → 3. Thus, the output in order is 6 0 3.

The diagram for mystery(2, 3) is as such:

(2, 3) → 3
↓
(2, 1) → 2
         ↓
         (1, 1) → 1
         ↓
         (1, 0) → 0

Following the tracing logic, we get the output 2 0 1 3.

As a final example, consider mystery(21, 12):

(21, 12) → 21
           ↓
           (9, 12) → 12
           ↓
           (9,  3) → 9
                     ↓
                     (6, 3) → 6
                              ↓
                              (3, 3) → 3
                              ↓
                              (3, 0) → 0

The output generated by tracing this structure is 21 9 6 0 3 12.