CSE 143: Computer Programming II, Winter 2011

Section 20: Polymorphism (Thu Mar 10)

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 9.14 (p622): Suppose that the following variables referring to the classes from the previous problem are declared: ... 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. You'll need to look at the Bay / Pond / Ocean / Lake classes declared on the previous page.)

Section 19: Advanced Lists (Tue Mar 8)

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 9.21 (p622): What’s wrong with the code for the following interface? (Explain what is wrong in 1-2 sentences, then show the code for a corrected version of the interface.)

Section 18: Inheritance (Thu Mar 3)

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 9.3 (p616): Consider the following classes: ... Which of the following are legal statements? (Consider all of (a) - (f).)

Section 17: Comparable (Tue Mar 1)

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 10.16 (p675): Indicate whether the result of each of the following comparisons ... (solve all of (a) - (f). You do not need to show your work.)
2. Exercise 10.18 (p677): Modify the TimeSpan class from Chapter 8 ... (You can use the following file as a template: TimeSpan.java)

Section 16: Binary Trees 2 (Thu 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.15 (p1027): Which of the following trees are valid binary search trees? (consider all of (a) - (e).)
2. Self-Check 17.17 (p1028): 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, ...

Section 15: Binary Trees 1 (Tue Feb 22)

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 17.5 (p1026): 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.

Sections 13 and 14: Recursive Backtracking (Tue Feb 15, Thu Feb 17)

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. (not from textbook): Modify the permute code from Mon/Wed's lecture 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 the Permutations.java file from the Lectures page as a starting point.
2. (not from textbook): The combinations problem from lecture prints the combinations in a particular order. How would you print them in the opposite order? Keep in mind that the combinations are currently stored in a Set the way our code is written. (Just describe in a few sentences what you would do; you don't need to turn in any code.)

Section 12: Midterm Review (Thu Feb 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 12.6 (p766): Convert the following iterative method into a recursive method: ...
2. Self-Check 11.9 (p711): Write the countDuplicates method described in Self-Check 11.4, and make it so that it can accept either type of list as a parameter as explained in Self-Check 11.9.

Section 11: Sets and Maps (Tue Feb 8)

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 (p711): A List has every ... (A few sentences will suffice.)
2. Self-Check 11.20 (p713): What keys and values are contained ... (write the final contents of the map in the following format; the relative order of the keys doesn't matter. {key1=value1, key2=value2, ...}

Section 10: Recursive programming (Thu 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 12.14 (p767): The following method has a bug ... (Indicate the bug and explain why it causes the method to fail. Why does your change solve the problem?)
2. Exercise 12.12 (p767): 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.

Section 9: Recursion (Tue Feb 1)

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 (p764): mystery1 method. For each of the following calls, indicate the output that is produced by the method: (Solve only parts (a), (b), 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.

Section 8: Linked lists (Thu Jan 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 16.19 (p976): An element can be inserted at or removed from the beginning, middle, or ...
2. Exercise 16.1 (p977): Write a method called set that ... (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 7: Linked nodes (Tue Jan 25)

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 (p975): 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 6: Stacks and queues (Thu Jan 20)

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

1. (not from textbook): What is the point of using stacks and queues, when an ArrayList can already do all the things they do and more?
2. (not from textbook): Suppose we have a Stack named s that contains various integer values:

   Stack<Integer> s = new Stack<Integer>();
   s.add(...);
   ...
   

   Write a piece of code that looks through the entire stack to find all occurrences of the value 42 and prints out this count to the console. If you like, you can put your code in a method named count that accepts the stack and the value to search for as parameters, but this is not required.

Section 5: Binary search, inheritance (Tue Jan 18)

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 13.7 (p817): Why does the binary search ... (One sentence is fine.)
2. Self-Check 13.8 (p817): How many elements (at most) does a binary search examine ... (Give a number as your answer and briefly explain why you chose that answer in one or two sentences.)
3. Self-Check 9.4 (p617): Explain the difference ... (One or two sentences is fine.)

Section 4: Testing and debugging (Thu 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 (p924): What is the purpose of ... (A few sentences will be fine. Give at least one specific example.)
2. Self-Check 15.13 (p924): Why do we bother to ... (One or two sentences will be fine.)
3. JUnit (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 JUnit test method that would expose this bug. (In other words, the test would fail if we have this bug, but pass if we do not.)

   You do not have to write a complete test class, or any import statements, etc.; and you don't actually need to set up JUnit on your computer yet or run your test method 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 make an assertion fail.

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

Section 3: implementing ArrayIntList (Tue Jan 11)

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 (p924): An element can be inserted at ...
2. Self-Check 15.8 (p924): Write methods called min and max that ... (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 2: ArrayList (Thu Jan 6)

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

1. Self-Check 10.2 (p674): Write the code to declare an ArrayList containing these elements. ...
2. Self-Check 10.3 (p674): Write code to insert two additional elements, ...
3. Self-Check 10.6 (p674): Write code to declare an ArrayList holding ...

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

Section 1: arrays (Tue Jan 4)

No problems are due for the first section.