COS 111, Fall 1997 - Problem Sets

Problem sets should be submitted by putting them in the collection box near the mailboxes in the lobby of the second floor of the Computer Science building.

Graded problem set 10 and solutions to problem set 10 are now available in the homework pick-up bin, next to the collection bin.

Problem Set 10

Problem 1:
Part a. In her article "Copyright's Fair Use Doctrine and Digital Data", Pamela Samuelson talks about "digital plasticity". What is "digital plasticity" and how does it exacerbate the problem of applying copyright protections to digital media?
Part b. One attempt to protect the ownership of digital images is through digital "watermarks". A digital watermark is created by changing a selected set of bits in the representation of an image so that

1. The image can be viewed with no perceptable change in image quality.
2. Anyone copying the image cannot detect the watermark and so cannot remove or alter it.
3. A copy of a watermarked image can be proven to be a copy by reveiling the watermark. (The argument is basically: "These bits were set in this way to make the watermark for my digital image. Your image that looks just like mine but you claim not to have copied has those bits set in the same way. It is extremely unlikely that those special bits were accidently set that way in your version. Therfore, your image must be a copy of of my digital image.")

Problem 2: The version of insertion sort presented by Brookshear (algorithm presented pgs 151-155 and analyzed pg. 417) uses sequential search to find where the pivot item belongs in the portion of the list that is already sorted. (The sorted portion ranges from the beginning of the list to just preceeding the location of the pivot item before it is inserted in the sorted portion.) Suppose the list is stored as an array so that binary search can be used in the sorted portion to find the correct position of the pivot item. Will this improve the speed of insertion sort significantly? Justify your answer. Be careful to consider all the basic steps the new version of insertion sort would have to do -- in particular, each time an array item is examined or changed must be counted as a step. (Note: the term "pivot item" is used here in the same way as in Figure 4.12, pg. 154 of Brookshear; this is different from the pivot item in quick sort).

Problem 3: Apply the recursive tree-printing algorithm of Fig. 7.25, pg.286 of Brookshear to the tree represented in Chapter 7 Review Problem 24, pg 299. (Don't do Problem 24, just use the tree shown there.)

Problem 4:
Part a. Give the values of the nodes examined, in the order examined, in the binary serach tree shown below if the value 131 is being sought.

                         100
                        /   \
                       /     \
                      /       \
                    25         130
                   /  \       /   \
                  /    \     /     \
                18     60  111    135
               /  \      \       /   \
              3   20     87    131   200

Problems 5 and 6: Brookshear, Chapter 10 Review Problems 14;19 (pgs 391-392).

Problem Set 9

Due by 5pm, Tuesday December 2 Due date extended to Thursday December 4 at 5pm.

Problem: In class, we looked at one way to implement a linked list in Java. Each of the items in a linked list was an object of type (i.e. Java class) node and a list was an object of type LinkedList. In class we wrote some, but not all, methods that manipulated objects of type LinkedList: we did insertFront and removeFront. For this problem, write insertBack to insert an item at the back of the list. You can use pseudocode. Your pseudocode should be close to Java -- you should try to use Java commands and Java syntax -- but need not be perfect Java. Click here to get the Java code we looked at in class.

Brookshear, Chapter Seven Review Problems 16; 22 (pg 298).
For Problem 16: use only the operations for a stack: push to add an item to the top of the stack and pop to delete an item from the top of the stack. You may define a second stack to use in your algorithm. Express the algorithm in pseudocode.

Extra Credit (20 points): Brookshear, Chapter Seven Review Problem 11 (pg 297).

Problem Set 8

Due by 5pm, Tuesday November 25

Brookshear, Chapter Five Review Problems 4, 5, 9 (pgs 227-228).

Problem: Java has a for loop control structure as well as a while loop control structure -- see Brookshear page 201 and Lab 8, Page 3. Below is a program fragment using a for loop. Rewrite the fragment using a while loop instead of the for loop. Variables n and k are integer variables declared elsewhere.

n = 0;
for (k = 1;  k < 1000; k = 2*k)
  { n = n + k;}

Problem: Write a program fragment that sets all the even-numbered elements of an array A to value 0 and all the odd-numbered elements of an array to value 1. (By the number of an element I mean its position in the array.) Assume A is an array variable referring to an existing array of 20 integer elements (i.e. A has been declared and space has been allocated for 20 integer elements). Your program fragment should express the algorithm for doing this assignment of values to the elements of A in pseudocode that is very close to Java. That is, your program fragment need not be perfect Java, but you should try to use Java commands and Java syntax.

Extra Credit (10 points):Brookshear, Chapter Five Review Problem 25 (pg 228).

Problem Set 7

Execute Quicksort on the list of 8 items given below. Indicate the pivot element and show the revised list each time an exchange is made. Do the same for each recursive execution of Quicksort made during the sorting process. Be sure to explicitly give the list with which each recursive execution starts. A recursive execution of a procedure is an execution that is started during a different execution of the same procedure because the procedure requests another execution of itself (with different values for the parameters).

List:

1. Dean
2. Bob
3. Helen
4. Garth
5. Frank
6. Carol
7. Edith
8. Abby

Brookshear, Chapter Four Review Problem 26 (pg 179).

Brookshear, Chapter Five Review Problem 7 (pg 228).

Problem Set 6

Brookshear, Chapter Four Review Problems 4; 13; 14; 15; 36 (pgs 177 - 180)