1. Recursive Tracing Method Call Value Returned ----------------------------------------------- mystery(18, 0) 0 mystery(8, 18) 1 mystery(25, 21) 1 mystery(305, 315) 2 mystery(20734, 1724) 2 2. Recursive Programming One possible solution public void writeNumbers(int n) { if (n < 1) { throw new IllegalArgumentException(); } if (n == 1) { System.out.print(1); } else if (n % 2 == 1) { System.out.print(n + ", "); writeNumbers(n - 1); } else { writeNumbers(n - 1); System.out.print(", " + n); } } 3. List Nodes before after code -----------------------+-----------------------+------------------------------- p->[1]->[2] | p->[2] | q.next = p; | | p = p.next; | | q.next.next = null; q->[3] | q->[3]->[1] | -----------------------+-----------------------+------------------------------- p->[1] | p->[3] | p.next = q; | | q = p; | | p = p.next.next; q->[2]->[3] | q->[1]->[2] | q.next.next = null; -----------------------+-----------------------+------------------------------- p->[1]->[2] | p->[3]->[2]->[1] | p.next.next = p; | | ListNode temp = q.next; | | q.next = p.next; q->[3]->[4] | q->[4] | p.next = null; | | p = q; | | q = temp; -----------------------+-----------------------+------------------------------- p->[1]->[2] | p->[1]->[3]->[5] | ListNode temp = p.next; | | p.next = q; | | temp.next = q.next; q->[3]->[4]->[5] | q->[2]->[4] | q.next = q.next.next; | | q = temp; | | q.next.next = null; -----------------------+-----------------------+------------------------------- 4. Collections One possible solution public Set takingAlongside(String course, Map> enrollments) { Set courses = new TreeSet(); for (String name : enrollments.keySet()) { Set namesCourses = enrollments.get(name); if (namesCourses.contains(course)) { // most people wrote addAll using a foreach loop courses.addAll(namesCourses); } } return courses; } 5. Stacks and Queues One possible solution public static void compressDuplicates(Stack s) { Queue q = new LinkedList(); s2q(s, q); q2s(q, s); s2q(s, q) if (!q.isEmpty()) { int last = q.remove(); int count = 1; while (!q.isEmpty()) { int next = q.remove(); if (next == last) { count++; } else { s.push(count); s.push(last); count = 1; last = next; } } s.push(count); s.push(last); } } 6. ArrayIntList One possible solution public void removeFront(int n) { if (n < 0 || n > size) { throw new IllegalArgumentException(); } for (int i = n; i < size; i++) { elementData[i - n] = elementData[i]; } size -= n; }