CPE 103 Homework Questions

Homework #1
Chapter 1
#1 Consider the following statements:
int a = 4;
int b = 7;
int c = ++a + b--;
What is the resulting value of c?
a. 10
b. 11
c. 12
d. 13
e. none of the above

#2 Which of the following loop constructs guarantee that the body is executed at least once?
a. do loop
b. for loop
c. while loop
d. two of the constructs
e. all three of the constructs

#3 In the method below, which statement about the possible outputs is most correct?
       public static void what( )
       {
          int x = 5;
          f( x );
          System.out.println( x );
       }
a. 0 is a possible output
b. 5 is the only possible output
c. any positive integer can be output
d. any integer can be output
e. none of the above are true

Chapter 2
#2.3

#2.9

#2.15

View Solutions

Homework #2
Chapter 3
3.1, 3.10, 3.13, 3.18, 3.25, 3.28
Chapter 4
4.6, 4.7, 4.9, 4.36 (Clarification: Person is figure 4.1 and findMax is figure 4.40.)
View Solutions


Homework #3
Chapter 5
5.4,  5.5,  5.7,  5.8,  5.10,  5.14,  5.15a,c,d,  5.19,  5.20a,  5.23,  5.28b, 5.28a (Clarification: What is a formula for the running time of contains in terms of N when val is not in m. It isn't asking for Big O estimate.) 
View Solutions


Homework #4

1. Given the table of running times from an empirical study of some algorithm,
a. derive the Big Oh for the running time and
b. predict the time to run for one million items.
N
 Time (secs)
10
 0.00034
100
 0.00063
1000
 0.00333
10000
 0.03042
100000
 0.29832

2. 5.31a

View Solutions



Homework #4.5
Write the Java code to create an enum for a baseball player position.  Player can be Pitcher, Catcher, Firstbase, Secondbase, Shortstop, Thirdbase, Leftfield, Centerfield, Rightfield.

Write a client program that loops to show all the players, in order.
Read a string from the user that represents a player, and creates an enum value.  If the enum value is a Pitcher, print "Strike", otherwise print "Ball".


Homework #5

Problem 1.  Consider these programs (view pdf or view txt) to test visibility.

  1. In package fruit, the class Tester has a print statement.  Which accesses in the print statement are illegal?
  2. Copy the main() method to Apple. Which accesses are illegal?
  3. Copy the main() method to Gala. Which accesses are illegal?
  4. The grow() method in the class Gala is passed an Apple object. Which of the Apple object members can the grow() method access?
  5. The package birds also has a class named Tester.  Which accesses in Tester are illegal?
  6. Which access in the grow() method of Fuju are illegal?
  7. Write a four-parameter constructor for Apple. Then write a six-parameter constructor for Gala.
  8. The class Gala consists of six integers, four that it inherits and two that it declares. Which are accessible to the class Gala?
    9. View solution
problem 2.
problem 3.
problem 4.


Homework #6
Decribe the shortcoming with how the data is represented in each scenario below.  Propose a better solution.
  1. Representing a position on a baseball team by an integer 1 to 9.
  2. Representing a checkerboard using a one-dimensional array.
  3. Representing a bank account balance as a double.
  4. Representing cars in line at a car wash as an ArrayList.
  5. Representing the duration of a song in MP3 format as an integer.
  6. Representing a year as a four-digit String.
View solution

Homework #7
Chapter 6
6.2
6.10
6.16 a,b,c

View solution

Homework #8

17.6
17.7

View solution
Homework #9

1) 6.1 a,b

2) 6.6

3) 6.19

4)  Draw a conceptual diagram of a queue to show it's state after the following sequence
of method calls:

enqueue("dog")
enqueue("cat")
enqueue("bird")
enqueue("mouse")
dequeue()
enqueue("fox")
dequeue()


5) Draw a conceptual diagram of a stack to show it's state after the following sequence
of method calls:

push("dog")
push("cat")
push("bird")
push("mouse")
pop()
push("fox")
pop()


6) Suppose the elements 1,2,3,4,5 are pushed onto an initially empty stack, in that order.
The stack is then popped four times and each element popped is enqueued into an initially empty
Queue.  If one element is then dequeued from the Queue, what is the element at the head of the queue?


7) Evaluate the following postfix expression using a stack.  Draw a diagram of the stack at each
step of the evaluation as on page 457.

                    8 5 4 + * 7 -


8) 11.1
 
9) Translate the following infix expressions to postfix notation using a stack as described in section 11.2.2:

  1. x + y * z
  2. (x + y) * z
  3. x - y - z * (a + b)
View solution


Homework #10

The solutions to these six homework questions can be determined by compiling and executing the code snippets provided.

1. Consider the following code snippet:
import java.util.*;
public class TestCol3
{
    public static void main(String[] args)
    {
        List l = new ArrayList();
        l.add("One");
        l.add("Two");
        l.add("Three");
        l.add("Four");
        l.add("One");
        l.add("Four");
        Set h = new HashSet();
        h.addAll(l);
        System.out.println("Size:" + l.size() + h.size());
    }
}
What will be the output?

2.      Consider the following code snippet:
import java.util.*;
public class TestCol4
{
public static void main(String[] args)
    {
        Set h = new HashSet();
        h.add("One");
        h.add("Two");
        h.add("Three");
        h.add("Four");
        h.add("One");
        h.add("Four");
        List l = new ArrayList();
        l.add("One");
        l.add("Two");
        l.add("Three");
        h.retainAll(l);
        System.out.println("Size:" + l.size() + h.size());
    }
}
What will be the output of the above code snippet?

3.      Given:
TreeSet ma=new TreeSet();
ma.add("one");
ma.add("two");
ma.add("three");
ma.add("four");
ma.add("one");
Iterator it=ma.iterator();
while(it.hasNext())
{
    System.out.println(it.next()+" ");
}
What is the result ?


4.     
import java.util.*;
public class Example
{
public static void main(String[] args)
{
// insert code here
    set.add(new Integer(2));
    set.add(new Integer(1));
    System.out.println(set);
}
}
Which code, inserted at line 4, guarantees that this program will output [1, 2]?
{
    A.     Set set = new TreeSet();
    B.     Set set = new HashSet();
    C.     Set set = new SortedSet();
    D.     Set set = new LinkedHashSet();
    E.     Set set = new SortedList();

5.      Given
    public static void before()
    {
        Set set=new TreeSet();
        set.add("2");
        set.add("3");
        set.add("1");
        Iterator it=set.iterator();
        while(it.hasNext()) System.out.print(it.next()+" ");
        System.out.println();
    }
    Which of the following statements are true??
    A.     before() method will print 1 2
    B.     before() method will print 1 2 3
    C.     before() method wil print three numbers, but order cannot be determined.
    D.     before() method will not compile
    E.     before() method will throw an exception at runtime

6.
     import java.util.*;
    public class WrappedString
    {
        private String s;
        public WrappedString(String s)
        {
            this.s = s;
        }
        public static void main(String[] args)
        {
            HashSeths = new HashSet();
            WrappedString ws1 = new WrappedString("aardvark");
            WrappedString ws2 = new WrappedString("aardvark");
            String s1 = new String("aardvark");
            String s2 = new String("aardvark");
            hs.add(ws1);
            hs.add(ws2);
            hs.add(s1);
            hs.add(s2);
            System.out.println(hs.size());
        }
    }  
What will be the output?


Homework #11

A utility class RomanNumerals is being created to do arithmetic with Roman Numerals.  You are to write a private helper function in this class

private static int getDigitValue(char digit)

that given a single Roman Numeral character will return the equivalent integer value (assuming the input character is a valid roman numeral). 

Here are the roman numerals and their corresponding values.
    C         D       I       L       M        V      X
    100     500    1      50     1000   5      10

Use a lookup table in your solution.

View solution
Homework #12

Solve homework 11 using a Map instead of an array.

View solution
Homework #13

1. Annie was asked to create a minimal perfect hashing function for the names of the planets of the Solar System, including Pluto.
She came up with this function:    Math.abs(1st letter's position in alphabet - word length)/2
So for Mercury,  (13 - 7) / 2 = 3.
Verify whether or not Annie's function is minimally perfect. Show all your calculations.
Irrelevant trivia: Jingle for remembering the ordering of planets "My Very Excellent Mother Just Sent Us Nine Pies".
View solution.

2. Chapter 20.5   View solution

Homework #14

a. Given the input:
375 254 639 718 101 105 692 538 799 277 512 822
a fixed table size of 13, and a hash function of H(x) = x mod 13, show the resulting linear probing hash table

b. Given the input:
255 375 254 639 718 101 100 692 538 800 277
a fixed table size of 13, and a hash function of H(x) = x mod 13, show the resulting quadratic probing hash table
Indicate if any inputs can't fit in the table.

View solution

Homework #15

1. Consider a definition of the function mystery(): 

mystery(0,n) = n
mystery(p,q) = mystery(p-1, q+1)

According to this definition, what is mystery(2,4)?


2. Which of the following Java methods correctly implements the  mystery() function?

A.    
int mystery( int P, int Q )
{
  if ( Q==0 )
  {
    return Q;
  }
  else
  {
    return mystery(P-1, Q-1);  
  }
}
 B.    
int mystery( int P, int Q )
{
  if ( P==Q )
  {
    return Q;
  }
  else
  {
    return mystery(P-1, Q);  
  }
}
C.    
int mystery( int P, int Q )
{
  if ( P==0 && Q==0)
  {
    return 1;
  }
  else
  {
    return mystery(P-1, Q+1);  
  }
}
 D.    
int mystery( int P, int Q )
{
  if ( P==0 )
  {
    return Q;
  }
  else
  {
    return mystery(P-1, Q+1);  
  }
}

3. Say that you have a recursive Java method, funct(). Is it always possible to write an iterative version of funct()?


4. Say that you have an iterative Java method, foo(). Is it always possible to write a recursive version of foo()?


5. Write a recursive function in Java that returns the sum of the digits of a positive integer. 
public static int sumOfDigits(int x)

If x is 234, the function should return 2 + 3 + 4, which is 9.
If x is 12, the function should return 1 + 2, which is 3.
If x is 39, the function should return 3 + 9, which is 12.

Hints:


View solution
Homework #16

Part 1
18.1, 18.2, 18.3

Part 2
Give the prefix, infix, and postfix expressions corresponding to this tree.

View solution
Homework #17


1. For each diagram below, indicate if it's a binary search tree.
If not, explain why not.




2. Given an empty binary search tree, draw a diagram of how it will appear after the following
sequence of operations:
insert('M');
insert('O');
insert('R');
insert('T');
insert('D');
insert('A');
insert('N');





3. Draw a picture of the binary search tree in diagram (g) after each statement below

insert('S');
insert('E');
insert('G');



4. Draw a picture of the binary search tree in diagram (j) after the operation below:
  remove('K');



5. Draw a picture of the binary search tree in diagram (i) after the operation below:
remove('P');



6. Draw a picture of the binary search tree in diagram (h) after the operation below:
remove('N');



7. Given the names of seven people: Sandra, Alfred, Larry, Wilma, David, Nancy, and Tom. Construct an arrangement of these names to be inserted into a binary search tree that will produce a tree where searching for a name will be as efficient as possible. List the ordering you create, and draw a diagram of the resulting tree.

8. Construct an arrangement of the names in problem 1 to be inserted into a binary search tree that will produce a tree where searching for a name will be as INEFFICIENT as possible. List the ordering you create, and draw a diagram of the resulting tree.

View Solution (PDF)
Homework #18
1. The numbers 9, 7, 10, 11, 15, 19, 5, 26, 3 are to be inserted into an initially empty AVL tree. Draw a diagram of the tree after each insert.

View Solution (PDF)
Homework #19
1. Suppose that Bubble Sort is applied to the following list of numbers (ascending order).
Show what the list will look like after each phase in the sort:

73 21 15 83 66 7 19 18

2. Suppose that Selection Sort is applied to the list of numbers given in Exercise 1.
Show what the list will look like after each phase in the sort.


3. Suppose that Insertion Sort is applied to the list of numbers given in Exercise 1.
Show what the list will look like after each phase in the sort.

Notes:
Assume sorting in ascending order.
Bubble sort can quit "early" if a pass results in no swaps.
Selection sort finds "highest" and swaps with end spot.
Insertion sort: show all passes, even in a pass has no moves.
First pass starts with second item.

View solutions

1. Suppose that Mergesort is applied to the following list of numbers.
Show what the list will look like after each phase in the sort:

73 21 15 83 66 7 19 18

2. Suppose that Quicksort is applied to the following list of numbers.
Show what the list will look like after each phase in the sort:

38 25 57 34 37 65 73 21

Use the algorithm illustrated in this animation.
When "picking the pivot", use the first element, as described on page 265. In reality this is a poor idea, but it works well for us on homework problems.
Here are directions for how to diagram Quicksort.

View solutions
Homework #20

1. Show the adjacency list representation of this graph. Use this Adjacency List Notation.

For the following problems, we will draw our solutions using this Adjacency Matrix Notation.
2. Show the adjacency matrix representation of this graph.
3. Show the adjacency matrix representation of this directed graph.

View solution
Homework #21

The next two exercises are about traversal algorithms. If you would like more explanation than provided in the textbook, you can watch this video. (Breadth-first starts at 4:30).

1. List the nodes of the graph below in the order visited by breadth-first traverse. If there is a choice of nodes to visit, select them in alphabetical order.
  1. starting at node A.
  2. starting at node B.
  3. starting at node E.
  4. starting at node F.

2. List the nodes of the graph below in the order visited by depth-first traverse
  1. starting at node A.
  2. starting at node H.
  3. starting at node G.




View solution
Homework #22

Use Dijkstra's algorithm to find the shortest path from node a to node i in this graph. Use the notation for marking the graph as shown in this video. Show the order in which the nodes are visited.
View solution

Another practice graph