Sections
Each week you will complete problem(s) to turn in at your 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 for that week. You must earn a total of 20 points for the quarter to receive 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 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.
Mar 3 2012 12:01 AM
Section 19: Polymorphism (Thu Mar 8)
Problems: Solve the following one (1) problem on paper (hand-written or printed) and bring your sheet of paper to your section:
- 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.)
Mar 3 2012 12:01 AM
Section 18: Advanced Lists (Tue Mar 6)
Problems: Solve the following one (1) problem on paper (hand-written or printed) and bring your sheet of paper to your section:
- 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.)
Feb 25 2012 12:01 AM
Section 17: Inheritance (Thu Mar 1)
Problems: Solve the following one (1) problem on paper (hand-written or printed) and bring your sheet of paper to your section:
- Self-Check 9.3 (p616): Consider the following classes: ... Which of the following are legal statements? (Consider all of (a) - (f).)
Feb 25 2012 12:01 AM
Section 16: Binary Trees 2 (Tue Feb 28)
Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- Self-Check 17.15 (p1027): Which of the following trees are valid binary search trees? (consider all of (a) - (e).)
- 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, ...
Feb 18 2012 12:01 AM
Section 15: Binary Trees (Thu Feb 23)
Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- Self-Check 17.3 (p1025): How many levels... (solve all of (a) - (e).)
- 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.
Feb 18 2012 12:01 AM
Section 14: Comparable / 2D Arrays (Tue Feb 21)
Problems: Solve the following three (3) problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- 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.)
- Exercise 10.18 (p677): Modify the TimeSpan class from Chapter 8 ... (You can use the following file as a template: TimeSpan.java)
- Self-Check 7.28 (p495): Write a piece of code that constructs a two-dimensional array of ...
Feb 11 2012 12:01 AM
Section 13: Recursive Backtracking (Thu Feb 16)
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:
- (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.
Feb 11 2012 12:01 AM
Section 12: Recursive Backtracking (Tue Feb 14)
There are no pre-section problems for Section 12. To get credit for the section points for this week, you will need to do the problems for Section 13. Sorry for the inconvenience.
Feb 4 2012 12:01 AM
Section 11: Midterm Review (Thu Feb 9)
Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- Self-Check 12.6 (p766): Convert the following iterative method into a recursive method: ...
- 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.
Feb 4 2012 12:01 AM
Section 10: Sets and Maps (Tue Feb 7)
Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- Self-Check 11.10 (p711): A List has every ... (A few sentences will suffice.)
- 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, ...}
Jan 28 2012 12:01 AM
Section 9: Recursive programming (Thu Feb 2)
Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- 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?)
- 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.
Jan 28 2012 12:01 AM
Section 8: Recursion (Tue Jan 31)
Problems: Solve the following one (1) problem on paper (hand-written or printed) and bring your sheet of paper to your section:
- 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.
Jan 21 2012 12:01 AM
Section 7: Linked lists (Thu Jan 26)
Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- Self-Check 16.19 (p976): An element can be inserted at or removed from the beginning, middle, or ...
- 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.)
Jan 21 2012 12:01 AM
Section 6: Linked nodes (Tue Jan 24)
Problems: Solve the following one (1) problem on paper (hand-written or printed) and bring your sheet of paper to your section:
- 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);
Jan 14 2012 12:01 AM
Section 5: Stacks and queues (Thu Jan 19)
SECTION CANCELLED: You will need to study stacks and queues on your own. We strongly recommend attempting these section problems in preparation for HW3: splitStack, stutter, rearrange, isPalindrome and isConsecutive. Additional section problems include copyStack, collapse, equals, reverseHalf, switchPairs and reorder.
SNOW NOTE: Since class was canceled on Wed 1/18 due to snow, you haven't been taught about stacks and queues yet in order to solve the problems below. So if you didn't do Tuesday's problems for your points for this week, you can skim the Appendix Q and/or the lecture slides on stacks and queues before answering these problems.
Problems: Solve the following two (2) problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- (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?
- 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?
- 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]?
Jan 14 2012 12:01 AM
Section 4: Binary search (Tue Jan 17)
Problems: Solve the following three (3) problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- Self-Check 13.7 (p817): Why does the binary search ... (One sentence is fine.)
- 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.)
- Self-Check 9.4 (p617): Explain the difference ... (One or two sentences is fine.)
Jan 7 2012 12:01 AM
Section 3: Testing and debugging (Thu Jan 12)
Problems: Solve the following three (3) problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- Self-Check 15.10 (p924): What is the purpose of ... (A few sentences will be fine. Give at least one specific example.)
- Self-Check 15.13 (p924): Why do we bother to ... (One or two sentences will be fine.)
- 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.
Jan 7 2012 12:01 AM
Section 2: implementing ArrayIntList
(Tue Jan 10)
Problems: Solve the following two (2) Self-Check problems on paper (hand-written or printed) and bring your sheet of paper to your section:
- Self-Check 15.7 (p924): An element can be inserted at ...
- 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.