CSE 143: Computer Programming II, Autumn 2015

Week11 Wed 12:01 AM

Section 20: Final review (Thu Dec 10)

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?

Week11 Mon 12:01 AM

Section 19: Linked List Review (Tue Dec 8)

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.

Week10 Wed 12:01 AM

Section 18: Inheritance (Thur Dec 3)

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".

Week10 Mon 12:01 AM

Section 17: TA's Choice Review and Sudoku Solver (Tue Dec 1)

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.

Week9 Mon 12:01 AM

Section 16: Inheritance and Polymorphism (Tue Nov 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 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();
   

Week8 Wed 12:01 AM

Section 15: Binary Trees 2 (Thur Nov 19)

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

Week8 Mon 12:01 AM

Section 14: Binary Trees (Tue Nov 17)

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.
   

Week7 Wed 12:01 AM

Section 13: More Recursive Backtracking (Thu Nov 12)

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.

Week7 Mon 12:01 AM

Section 12: Recursive Backtracking (Tue Nov 10)

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?

Week6 Wed 12:01 AM

Section 11: testing and debugging (Thu Nov 5)

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

1. What is the difference between black box testing and white box testing? Why do we do both?
2. 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.

Week6 Mon 12:01 AM

Section 10: Midterm Review (Tue Nov 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 12.7 (12.6 2nd E.) p804 (p766 2nd E.): Convert the following iterative method into a recursive method:

   
       // Prints each character of the string reversed twice.
       // doubleReverse("hello") prints oolllleehh
       public static void doubleReverse(String s) {
           for (int i = s.length() - 1; i >= 0; i--) {
               System.out.print(s.charAt(i));
               System.out.print(s.charAt(i));
           }
       }
   

2. Complete the following Practice-It problem. Write the code necessary to convert the following sequences of ListNode objects:

       front  -> [1] -> [2] /
       temp -> [3] -> [4] -> [5] /
   
   Into this sequence of ListNode objects:
   
       front  -> [3] -> [2] -> [4] -> [1] -> [5] /
   

   There may be more than one way to write the code, but you are NOT allowed to change any existing node's data field value. You also should not create new ListNode objects unless necessary to add new values to the chain, but you may create a single ListNode variable to refer to any existing node if you like. If a variable does not appear in the "after" picture, it doesn't matter what value it has after the changes are made.

Week5 Wed 12:01 AM

Section 9: Comparable (Thur Oct 29)

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)

Week5 Mon 12:01 AM

Section 8: Sets and Maps (Tue Oct 27)

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);
   

Week4 Wed 12:01 AM

Section 7: Recursive programming (Thu Oct 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 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);
   

Week4 Mon 12:01 AM

Section 6: Recursion (Tue Oct 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 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);
   

Week3 Wed 12:01 AM

Section 5: Linked lists (Thur Oct 15)

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.)

Week3 Mon 12:01 AM

Section 4: Linked nodes (Tue Oct 13)

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);

Week2 Wed 12:01 AM

Section 3: Stacks and queues (Thur Oct 8)

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]?

Week2 Mon 12:01 AM

Section 2: Implementing ArrayIntList (Tue Oct 6)

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.

Jan 5 2015 12:01 AM

Section 1: ArrayList (Thur Oct 1)

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.