CSE 143: Computer Programming II, Winter 2015

Section 20: Final review (Thu Mar 12)

Problems: Solve the following three (3) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 10.20 (10.15 2nd E.) p696 (p675 2nd E.): What is natural ordering? How do you define a natural ordering for a class you've written? (write 2-3 sentences)
2. Self-Check 17.20 p1050 (p1028 2nd E.): Draw the binary search tree that would result if the given elements were added to an empty binary search tree in the given order: Lisa, Bart, Marge, Homer, Maggie, Flanders, Smithers, Milhouse
3. Self-Chech 17.22 p1050 (p1028 2nd E.): What is the x = change(x) pattern, and how is it used with binary trees?

Section 18: Inheritance and Polymorphism (Tue Mar 10)

Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 9.4 (9.3 2nd E.) p635 (p616 2nd E.): Consider the following classes:

       public class Vehicle {...}
       public class Car extends Vehicle {...}
       public class SUV extends Car {...}
   

   Which of the following are legal statements?
   
   1. Vehicle v = new Car();
   2. Vehicle v = new SUV();
   3. Car c = new SUV();
   4. SUV s = new SUV();
   5. SUV s = new Car();
   6. Car c = new Vehicle();


2. Self-Check 9.17 (9.14 2nd E.) p641 (p622 2nd E.): Suppose that the following classes have been declared:

       public class Bay extends Lake {
           public void method1() {
               System.out.print("Bay 1 ");
               super.method2();
           }
           
           public void method2() {
               System.out.print("Bay 2 ");
           }
       }
       
       public class Pond {
           public void method1() {
               System.out.print("Pond 1 ");
           }
       
           public void method2() {
               System.out.print("Pond 2 ");
           }
   
           public void method3() {
               System.out.print("Pond 3 ");
           }
       }
   
       public class Ocean extends Bay {
           public void method2() {
               System.out.print("Ocean 2 ");
           }
       }
   
       public class Lake extends Pond {
           public void method3() {
               System.out.print("Lake 3 ");
               method2();
           }
       }
   

   
   Suppose that the following variables referring to those classes have been declared:

       Pond var1 = new Bay();
       Object var2 = new Ocean();
   

   
   Which of the following statements produce compiler errors? For the statements that do not produce errors, what is the output of each statement? (Answer for all five lines of code shown)

       ((Lake) var1).method1();
       ((Bay) var1).method1();
       ((Pond) var2).method2();
       ((Lake) var2).method2();
       ((Ocean) var2).method3();
   

Section 18: TA's Choice Review and Sudoku Solver (Thur Mar 5)

Problems: Solve the following one (1) problem on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Write a method makePerfect, which is also a Practice-it problem, that could be added to the IntTree class. The method should add nodes until the binary tree is a "perfect" tree. A perfect binary tree is one where all leaves are at the same level. Another way of thinking of it is that you are adding dummy nodes to the tree until every path from the root to a leaf is the same length. A perfect tree's shape is exactly triangular and every branch node has exactly two children. Each node you add to the tree should store the value 0. The following is an example with a variable treeIntTree.

   
   IntTree tree = new IntTree();
   
   tree.makePerfect();
   
   

   	before call:
                    +----+
                    | 67 |
                    +----+
                 /          \
              /                \
         +----+                +----+
         | 80 |                | 52 |
         +----+                +----+
        /      \              /
       /        \            /
   +----+     +----+      +----+
   | 16 |     | 21 |      | 99 |
   +----+     +----+      +----+
               /  \           \
              /    \           \
          +----+  +----+      +----+
          | 45 |  | 33 |      | 67 |
          +----+  +----+      +----+
   
   	after call:
                           +----+
                           | 67 |
                           +----+
                       /             \
                   /                     \
              +----+                     +----+
              | 80 |                     | 52 |
              +----+                     +----+
            /        \                 /        \
          /            \             /            \
      +----+         +----+       +----+        +----+
      | 16 |         | 21 |       | 99 |        |  0 |
      +----+         +----+       +----+        +----+
      /    \         /    \       /    \        /     \
     /      \       /      \     /      \      /       \
   +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
   |  0 | |  0 | | 45 | | 33 | |  0 | | 67 | |  0 | |  0 |
   +----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
   

   For this problem, you may assume the existence of the following helper method, which you are allowed to call at most once during an entire call to your method:
   
   public int height() { ... } // returns height of tree from root to lowest leaf For example, calling height on the tree above would return 4 because it is 4 levels tall.
   
   You may define private helper methods, but aside from height you may not call any other methods of the class nor create any data structures. Your solution should be recursive and utilize the x = change(x) pattern discussed in the Building Java Programs textbook.

Section 17: Linked List Review (Tue Mar 3)

Problems: Solve the following two (2) problem on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 16.18 (p998): What are two ways to change the contents of a linked list?
2. Self-Check 16.13 (p1000): Write a method transferFrom, also on PracticeIt, that accepts a second LinkedIntList as a parameter and that moves values from the second list to this list. You are to attach the second list's elements to the end of this list. You are also to empty the second list. For example, suppose two lists store these sequeces of values:

       list1: [8, 17, 2, 4]
       list2: [1, 2, 3]
   

   The call of list1.transferFrom(list2); should leave the lists as follows:

       list1: [8, 17, 2, 4, 1, 2, 3]
       list2: []
   

   The order of the arguments matters; list2.transferFrom(lis1); would have left the lists as follows:

       list1: []
       list2: [1, 2, 3, 8, 17, 2, 4]
   

   Either of the two lists could be empty, but you can assume that neither list is null. You are not to create any new nodes. Your method should simply change the links of the lists to join them together. Assume that you are adding this method to the LinkedIntList class from lecture.

Section 16: Binary Trees 2 (Thur Feb 26)

Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 17.15 p1049 (p1027 2nd E.): Which of the following trees are valid binary search trees?
   1. 
   
   
   2. 
   
   
   3. 
   
   
   4. 
   
   
   5. 
2. Self-Check 17.17 p1050 (p1028 2ns E.): Draw the binary search tree that would result if the given elements were added to an empty binary search tree in the given order: Leia, Boba, Darth, R2D2, Han, Luke, Chewy, Jabba

Section 15: Binary Trees (Tue Feb 24)

Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 17.3 p1047 (p1025 2nd E.):
   
   1. How many levels does the given tree have?
   2. How many branches does it have, and which nodes are they?
   3. How many leaves does it have, and which nodes are they?
   4. Which node is the root of the tree?
   5. Which node(s) are the sibling(s) of the node storing the value 2? Which nodes are its children
2. Self-Check 17.5 p1048 (p1026 2nd E.): Write the elements of the given tree in the order in which they would be seen by a pre-order, in-order, and post-order traversal.
   

Section 14: More Recursive Backtracking (Thu Feb 19)

Problems: Solve the following one (1) problem on paper (hand-written or printed) and bring your sheet of paper to either one of the sections this week:

1. Modify the Permute.java so that it outputs the permutations in the opposite order. That is, instead of permute("JANE") outputting JANE, JAEN, JNAE, ..., it should output ENAJ, ENJA, EANJ, ... Reverse the order by modifying the algorithm and the order in which it chooses various paths to explore, not by literally reversing strings as they are about to be printed. Use Permute.java's as a starting point.

Section 13: Recursive Backtracking (Tue Feb 17)

Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. In the recursive backtracking example Dice.java, why is it necessary to use a private helper method? Explain in a sentence or two.
2. What is pruning in the context of recursive backtracking? Why is it worth doing?

Section 12: Comparable (Thur Feb 12)

Problems: Solve the following problem on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Complete the following Practice-It problem.

   Define a class called Office that keeps track of information about an office's features. The class should have the following public methods:

   Method	Description
   public Office(double width, double length, boolean couch, int windows)	constructs an Office object with the given width and length, couch (true or false) and number of windows
   public boolean isCorner()	returns true if the office is a corner office. A corner office is square (has the same width and length) and has exactly two windows.
   public String toString()	returns a string representing the office in the format: width: , length: , windows: . If the office has a couch ", has a couch" should be appended to the end of the string.

   Examples:

   Office o1 = new Office (10.3, 10.3, true, 3);
   Office o2 = new Office (14.0, 6.7, false, 3);
   

   A call on o1.toString() and o2.toString() would return, respectively:

   width: 10.3, length: 10.3, windows: 3, has a couch
   width: 14.0, length: 6.7, windows: 2
   

   Also make Office objects comparable to each other using the Comparable interface. Offices that have that have a greater area (width * length) should be considered "less" than other Offices so that they appear at the beginning of a sorted list. Offices that have the same area should be ordered by the number of windows they have, with Offices that have a greater amount of windows considered "less" than Offices that have less. If Offices still appear equal they should be compared by whether or not they have a couch. Offices with couches should be considered "less".

Section 10: Comparable (Thur Feb 5)

Problems: Solve the following three (3) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 9.22 p641: What is the difference between implementing an interface and extending a class?
2. Self-Check 10.21 (10.16 2nd E.) p696 (p675 2nd E.): Consider the following variable declarations:

       Integer n1 = 15;
       Integer n2 = 7;
       Integer n3 = 15;
       String s1 = "computer";
       String s2 = "soda";
       String s3 = "pencil";
   

   Indicate whether the result of each of the following comparisons is positive, negative, or 0: (solve all of (a) - (f). You do not need to show your work.)

       a. n1.compareTo(n2)
       b. n3.compareTo(n1)
       c. n2.compareTo(n1)
       d. s1.compareTo(s2)
       e. s3.compareTo(s1)
       f. s2.compareTo(s2)
   

3. Exercise 10.19 (10.18 2nd E.) p699 (p677 2nd E.): Modify the TimeSpan class from Chapter 8 to include a compareTo method that compares time spans by their length. A time span that represents a shorter amount of time is considered to be "less than" one that represents a longer amount of time. For example, a span of 3 hours and 15 minutes is greater than a span of 1 hour and 40 minutes. (You can use the following file as a template: TimeSpan.java)

Section 9: Sets and Maps (Tue Feb 3)

Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 11.10 p733 (p711 2nd E.): A List has every method that a Set has, and more. So why would you use a Set rather than a List? (A few sentences will suffice.)
2. Self-Check 11.18 (11.20 2nd E.) p734 (p713 2nd E.): What keys and values are contained in the following map after this code executes? (write the final contents of the map in the following format; the relative order of the keys doesn't matter. {key1=value1, key2=value2, ...}

       Map<Integer, String> map = new HashMap<Integer, String>();
       map.put(8, "Eight");
       map.put(41, "Forty-one");
       map.put(8, "Ocho");
       map.put(18, "Eighteen");
       map.put(50, "Fifty");
       map.put(132, "OneThreeTwo");
       map.put(28, "Twenty-eight");
       map.put(79, "Seventy-nine");
       map.remove(41);
       map.remove(28);
       map.remove("Eight");
       map.put(50, "Forty-one");
       map.put(28, "18");
       map.remove(18);
   

Section 8: Recursive programming (Thu Jan 29)

Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 12.17 (12.14 2nd E.) p806 (p767 2nd E.): The following method has a bug that leads to infinite recursion. What correction fixes the code?

       // Adds the digits of the given number.
       // Example: digitSum(3456) returns 3+4+5+6 = 18
       public static int digitSum(int n) {
           if (n > 10) {
               // base case (small number)
               return n;
           } else {
               // recursive case (large number)
               return n % 10 + digitSum(n / 10);
           }
       }
   

   (Indicate the bug and explain why it causes the method to fail. Why does your change solve the problem?)
2. Exercise 12.14 (12.12 2nd E.) p805 (p767 2nd E.): Consider the following method:

       public static int mystery5(int x, int y) {
           if (x < 0) {
   	    return -mystery5(-x, y);
   	} else if (y < 0) {
   	    return -mystery5(x, -y);
   	} else if (x == 0 && y == 0) {
   	    return 0;
   	} else {
   	    return 100 * mystery5(x / 10, y / 10) + 10 * (x % 10) + y % 10;
   	}
       }
   

   For each of the following calls, indicate the value that is returned: (Solve only parts (a), (c), and (e). Show your work by writing out the series of calls that are made before writing the final output. For example, if mystery1(5) calls mystery1(4), write the sequence of such calls before your answer.

       a. mystery5(5, 7);
       c. mystery5(-7, 4);
       e. mystery5(128, 343);
   

Section 7: Recursion (Tue Jan 27)

Problems: Solve the following one (1) problem on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 12.3 p802 (p764 2nd E.):

       public static void mystery1(int n) {
           if (n <= 1) {
   	    System.out.print(n);
   	} else {
   	    mystery1(n / 2);
   	    System.out.print(", " + n);
   	}
       }
   

   For each of the following calls, indicate the output that is produced by the mystery1 method: (Solve only parts (a), (b), (e) and (f)). Show your work by writing out the series of calls that are made before writing the final output. For example, if mystery1(5) calls mystery1(4), write the sequence of such calls before your answer.

       a. mystery1(1);
       b. mystery1(2);
       e. mystery1(16);
       f. mystery1(30);
   

Section 6: Linked lists (Thur Jan 22)

Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 16.19 p998 (p976 2nd E.): An element can be inserted at or removed from the beginning, middle, or end of a linked list. Which of the three locations is the most computationally expensive, and why? How does this compare against the result for an array list?
2. Exercise 16.1 p999 (p977 2nd E.): Add this method to the LinkedIntList class from this chapter. Write a method called set that accepts an index and a value and sets the list's element at that index to have the given value. You may assume that the index is between 0 (inclusive) and the size of the list (exclusive). (You can base your solution on the get method we wrote in lecture on Wednesday. If you're having trouble, do the best that you can in < 30 minutes and turn in your best effort.)

Section 5: Linked nodes (Tue Jan 20)

Problems: Solve the following one (1) problem on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 16.6 p997: Draw a picture of what the given linked nodes would look like after the given code executes.

   

   list.next = new LinkNode(3, list.next);

Section 4: Stacks and queues (Thur Jan 15)

Problems: Solve the following three (3) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. What is the point of using stacks and queues, when an ArrayList can already do all the things they do and more?
2. What is the difference between a stack and a queue? Why might we want to use one versus the other? Can you name a situation (real-world or programming) where you want one of these kinds of structures?
3. Describe, in English or in pseudo-code, the general idea of an algorithm to reverse the contents of a stack of integers, using only one stack or queue as auxiliary storage. For example, if the stack stores the values [10, 20, 30, 40] from top to bottom, how would you modify it to store [40, 30, 20, 10]?

Section 3: implementing ArrayIntList, testing and debugging (Tue Jan 13)

Problems: Solve the following three (3) problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 15.10 p946 (p924 2nd E.): What is the purpose of the checkIndex method? Where is it called in the list class? Describe a way that the client can utilize an ArrayIntList that will be caught by checkIndex. (A few sentences will be fine. Give at least one specific example.)
2. Self-Check 15.13 p946 (p924 2nd E.): Why do we bother to add the contains.isEmpty, and remove methods to the list class, when the client can already perform this same functionality with the indexOf, size, and remove methods, respectively? (One or two sentences will be fine.)
3. Writing tests (not from the textbook): Suppose we have a bug in our ArrayIntList where the size is never incremented when add is called. Write a minimal method that would expose this bug. In other words, your code should include some printlns that would indicate that something bad happened given that bug.

   You don't necessarily have to type up and run the code if you don't want to. Just write out the code for this one method manually. It can be very short; write the minimal amount of code you need so that this bug will be visible.

You don't need to write a complete program; just the relevant lines of code to answer the question.

Section 2: Implementing ArrayIntList (Thur Jan 8)

Problems: Solve the following two (2) Self-Check problems on paper (hand-written or printed) and bring your sheet of paper to your section:

1. Self-Check 15.7 p946 (p924 2nd E.): An element can be inserted at the beginning, middle, or end of an array list. Which of the three insertion points is the most computationally expensive, and why? Which is the most expensive location to remove an element from the list?
2. Self-Check 15.8 p946 (p924 2nd E.): Write methods called min and max that return the smallest and largest values in the list respectively. For example, if a variable called list stores [11, -7, 3, 42, 0, 14], the call of list.min() should return -7 and the call of list.max() should return 42. If the list is empty, the methods should throw an IllegalStateException. (Write just one of the two methods. Either one is fine. You don't need to write both.)

You don't need to write a complete program; just the relevant lines of code to answer the question.

Section 1: ArrayList (Tues Jan 6)

No problems are due for the first section.

Here are some optional Practice-It problems that would be useful review: arrayMystery, indexOf, findMin, numUnique, stretch, rotateRight, add.