CSE 143

Course Info

Tutorials

Getting Help

Check Scores

Other

Sections

Each week, you will complete problem(s) to submit at the start of section. Most weeks there will be problems posted for both Tuesday's and Thursday's section. You must complete at least one problem set per week to earn 3 points credit for that week. Section this quarter will be worth a total of 20 points which means you need credit for 7 weeks for full credit. Additional points beyond these 20 do not affect your grade, but you are welcome to complete every set of problems if you like. (These points become part of your homework grade; each weekly homework assignment is worth 40 points, so all of the section points for the quarter combine to equal roughly half the weight of one homework assignment.) You may only receive credit for your section homework if you attend section.

You will not be graded on whether you have a perfect solution, but on whether you have demonstrated effort. Therefore please show some work that demonstrates how you got the answer rather than just writing the answer by itself. We will be somewhat lenient about exactly how the work is shown. If you find that you have been working on these problems for more than 30 minutes, please stop and indicate this on your paper. Incomplete solutions can still receive credit.

Section homework will be made available the day before it is due. Since it is meant as a warm-up for section, we encourage you to do it not too long before section.

Section 20: Final review (Thu Jun 2)

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 (p696): 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.17 (p1050): Draw the binary search tree that would result if the given elements were added to an empty binary search tree in the given order. Then write the elements of the tree in the order that they would be visited by each kind of traversal (preorder, inorder, and postorder): Leia, Boba, Darth, R2D2, Han, Luke, Chewy, Jabba
  3. Self-Chech 17.22 (p1050): What is the x = change(x) pattern, and how is it used with binary trees?

Section 16: Binary Trees 2 (Thu May 19)

Since these weren't visible on Wednesday, just coming to this section will give you credit for the week (i.e. these problems are optional)

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): Which of the following trees are valid binary search trees? (consider all of (a) - (e).) 
    a) 
   -5
  /  \
-1    -7

b) 
        8
      /   \
     5     11
   /  \   /  \
  2   7  10   18
   \           \
    4          20
              /
            18

c) 
    42

d) 
        m
      /   \
     g     q
    /     /  \
   b     k    x
    \  
     e

e) 
       7.2
      /   \
    1.9    9.6
           /  \ 
         8.1   21.3
  2. Self-Check 17.20 (p1050): 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

Section 15: Binary Trees (Tue May 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): Consider the following tree: 
                  3
             / \
            5   2
           /   /  \
          1   4    6

    a) How many levels does the given tree have?
    b) How many branches does it have, and which nodes are they?
    c) How many leaves does it have, and which nodes are they?
    d) Which node is the root of the tree?
    e) Which node(s) are the sibling(s) of the node storing the value 2? Which nodes are its children?

  2. Self-Check 18.5 (p1048): 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. 
               19
         /    \
       47      63
      /  \       \ 
    23   -2       94
        /           \
       55            28

Section 14: Recursive Backtracking (Thu May 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. (not from textbook): Modify the permute code from 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.

Section 13: Recursive backtracking (Tue May 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 last Wednesday's lecture examples (see Dice.java), why did we need 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: Midterm Review (Thu May 5)

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

  1. Describe your midterm review strategy in a few sentences.
  2. Self-Check 12.7 (p804): 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));
   }
}
  3. Self-Check 11.9 (p733): Write the countDuplicates method described in Self-Check 11.4 (reproduced below), and make it so that it can accept either type of list (LinkedList or ArrayList) as a parameter. Write a piece of code that counts the number of duplicate elements in a linked list, that is, the number of elements whose values are repeated at an earlier index in the list. Assume that all duplicates in the list occur consecutively. For example,the list 
    [1, 1, 3, 5, 5, 5, 5, 7, 7, 11]
    contains five duplicates: one duplicate of element value 1, three duplicates of element value 5, and one duplicate of element value 7.

Section 11: 2D Arrays and TA's choice (section problems on searching/sorting) (Tue May 3)

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.20 (p863): What indexes will be examined as the middle element by a binary search for the target value 8 when the search is run on the following input array? Notice that the input array isn't in sorted order. What can you say about the binary search algorithm's result? 
    int[] numbers = {6, 5, 8, 19, 7, 35, 22, 11, 9};
  2. Self-Check 13.26 (p864): How many calls on the mergeSort method are generated by a call to sort a list of length 32?
  3. Self-Check 13.27 (p864): Consider the following array of int elements: 
    int[] numbers = {7, 2, 8, 4, 1, 11, 9, 5, 3, 10};
    a. Show the state of the elements after five passes of the outermost loop of selection sort have occurred. b. Show a trace that is two levels deep of the merge sort algorithm. Show the splitting of the overall array, plus one level of the recursive calls.

Section 10: Comparable (Thu Apr 28)

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 (p696): Consider the following variable declarations, and 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.) 
    Integer n1 = 15;
Integer n2 = 7;
Integer n3 = 15;
String s1 = "computer";
String s2 = "soda";
String s3 = "pencil";

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 (p699): 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 Apr 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 11.10 (p733): 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 (p735): 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 Apr 21)

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 12.10 (p804): What would be the effect
  2. Self-Check 12.12 (p805): What are the differences...
  3. Self-Check 12.17 (p806): 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?)

Section 7: Recursion (Tue Apr 19)

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 12.4 (p803): 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.)
  2. Self-Check 12.11 (p805): The following method is an attempt...

Section 6: Linked lists (Thu Apr 14)

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.20 (p998): When you add or remove ...
  2. Exercise 16.1 (p999): Write a method called set that ... (You can base your solution on the get method we wrote in lecture. If you're having trouble, do the best that you can in < 30 minutes and turn in your best effort.)

Section 2: implementing ArrayIntList (Thurs Mar 31)

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): An element can be inserted at ...
  2. Self-Check 15.8 (p946): 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.