Midterm Examination

Com 1201 – Winter 2003 – Jeff Raab

 

 

Name  _______________________________________      ID#  _________________________

 

Introduction

 

This is a closed book, closed notes examination.  Please read all of the instructions for each problem before you provide your solution.  If you have any questions regarding a particular problem, please ask the test proctor for help understanding the problem.  The number of points for each problem in a section is listed in the left margin.  You have one class period to complete the problems on this examination.

 

Grading

 

Section

Points

Score

1

25

 

2

30

 

3

25

 

4

20

 

Total

100

 

Letter grade

 

 

Section 1 – Java Programming

 

            (10)     The flag of the United States of America contains 13 stripes of alternating colors and 50 stars in rows of alternating lengths.  The layout of these stars and stripes is shown in the picture of the flag at the right.  You must write two methods that deal with this kind of layout.

 

Write a method below named stripes that takes one parameter named count of type int and has a return type of boolean.  This method must return true if it is possible to create a flag whose layout of stripes is similar to that of the United States of America, in that it has an odd number of red stripes and an even number of white stripes whose sum is equal to the given count.  This method must return false otherwise.

 

For the purposes of this problem, zero is an even number.  It is not possible to create a flag with a negative number of stripes.  Your method must be correct and completely documented to the specification of the model code for a function as posted on the course website.  Write your function and its documentation in the space below:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The running time for this method, as you have written it, is _______________________ .

            (15)      Write a method below named stars that takes one parameter named count of type int and has a return type of boolean.  This method must return true if it is possible to create a flag whose layout of stars is similar to that of the United States of America, in the following ways:

 

1.         The stars are in rows of alternating lengths.

2.         The lengths of the rows differ by exactly one.

3.         There are at least 3 rows of stars.

4.         There is one more row of the longer length than of the shorter length.

5.         The number of stars is equal to the given count.

 

This method must return false if it is not possible to create a flag that meets these criteria.

 

It is not possible to create a flag with a negative number of stars.  Your method must be correct and completely documented to the specification of the model code for a function as posted on the course website.  Write your function and its documentation in the space below:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The running time for this method, as you have written it, is _______________________ .

Section 2 – Implementing a Java interface

 

            (30)      The Deck interface describes a data structure used to store and retrieve Objects in the same manner as a deck of cards.  Assume the following code:

 

/** Interface describing the operations for a deck. */

public interface Deck {

 

     /**

      * Adds the given element to the bottom of this deck.

      * @param element object to be added

      */

public void add(Object element);

 

     /**

      * Inserts the given element at a random position

      * in this deck.

      * @param element object to be inserted

      */

public void insert(Object element);

 

/**

 * Removes the object on the top of this deck,

 * and returns that object.

 */

     public Object removeTop() throws RuntimeException;

 

     /** Returns the number of objects in this deck. */

     public int size();

 

     /** Returns whether or not this deck is empty. */

     public boolean isEmpty();

}

 

On the following page, write a complete Java class named VectorDeck that implements this ADT using a Java Vector object to do the work of the methods required by the interface.  The last pages of this exam summarize the documentation for the Vector class, for your reference.

 

The following code stores a random integer in the range [0, n) in the variable k:

 

int k = (int)(Math.random() * n);

 

Your method must be correct and completely documented to the specification of the model code for a class as posted on the course website.  Write your class and its documentation on the next page.

Section 2 answer

 

Section 3 – Analysis

 

Analyze each function.  Write the number of * characters it actually prints, in terms of the values of any inputs to the function.  Provide an asymptotic analysis of the number of * characters printed, in terms of the values of any inputs to the function.  In case you are unsure, the following code prints a single * character:

 

            System.out.println(“*”);

 

The following code prints three * characters:

 

            System.out.println(“***”);

 

Be sure to completely read the code of each function before performing your analysis of it. 

 

 

 

            (5)        public void printStars1(int n) {

System.out.println(“***”);

 

               

for (int i = 0; i < n; i++) {

     for (int j = 0; j < 50; j++) {

           System.out.println(“*”);

     }

}

 

System.out.println(“**”);

}

The number of * characters actually printed is  __________________________ .

Asymptotically, the number of * characters printed is __________________________ .

           

 

 

 

            (5)        public void printStars2(int n) {

     System.out.println(“**********”);

}

The number of * characters actually printed is  __________________________ .

Asymptotically, the number of * characters printed is __________________________ .

Section 3 – Analysis

 

Analyze each function.  Write the number of * characters it actually prints, in terms of the values of any inputs to the function.  Provide an asymptotic analysis of the number of * characters printed, in terms of the values of any inputs to the function.  In case you are unsure, the following code prints a single * character:

 

            System.out.println(“*”);

 

The following code prints three * characters:

 

            System.out.println(“***”);

 

Be sure to completely read the code of each function before performing your analysis of it. 

 

 

 

            (5)        public void printStars3(int n) {

     System.out.println(“***”);

 

int pow = 1 * 2 * 3 * 4;

for (int i = 0; i < pow; i++)

     System.out.println(“**”);

 

System.out.println(“***”);

}

The number of * characters actually printed is  __________________________ .

Asymptotically, the number of * characters printed is __________________________ .

 

 

 

            (10)      public void printStars4(int n) {

     System.out.println(“**”);

 

for (int i = 0; i < n; i++) {

     System.out.println(“**”);

     System.out.println(“*”);

}

 

System.out.println(“*”);

}

The number of * characters actually printed is  __________________________ .

Asymptotically, the number of * characters printed is __________________________ .

Section 4 – Linked Lists

 

            (20)      Assume a linked list class constructed from nodes that each contain three references: one for the element Object the node contains, one that refers to the next node in the list, and one that refers to the previous node in the list.  You must draw diagrams that show the state of the nodes in the list during the process of inserting a new node immediately after the head sentinel node.

 

The diagram below shows the state of the list before inserting.  Draw one diagram per step, in the boxes below, that shows the state of the list after that step is performed.  Use the given diagram as a guide for the correct way to draw a linked list.  References to null can be left blank.  Feel free to ask if your diagrams are understandable, to ensure that you get proper credit.

 

Before insert of object o at the front of the list

 

Create a new node n that refers to o

Set the previous for n to the head

Set the next for n to the first node after the head

Set the next for the head to n

Set the previous for the first node after head to n

java.util
Class Vector

 

Constructor Summary

Vector()
          Constructs an empty vector so that its internal data array has size 10 and its standard capacity increment is zero.

 

Vector(Collection c)
          Constructs a vector containing the elements of the specified collection, in the order they are returned by the collection's iterator.

 

Vector(int initialCapacity)
          Constructs an empty vector with the specified initial capacity and with its capacity increment equal to zero.

 

Vector(int initialCapacity, int capacityIncrement)
          Constructs an empty vector with the specified initial capacity and capacity increment.

 

Method Summary

 void

add(int index, Object element)
          Inserts the specified element at the specified position in this Vector.

 boolean

add(Object o)
          Appends the specified element to the end of this Vector.

 void

addElement(Object obj)
          Adds the specified component to the end of this vector, increasing its size by one.

 int

capacity()
          Returns the current capacity of this vector.

 void

clear()
          Removes all of the elements from this Vector.

 boolean

contains(Object elem)
          Tests if the specified object is a component in this vector.

 void

copyInto(Object[] anArray)
          Copies the components of this vector into the specified array.

 Object

elementAt(int index)
          Returns the component at the specified index.

 void

ensureCapacity(int minCapacity)
          Increases the capacity of this vector, if necessary, to ensure that it can hold at least the number of components specified by the minimum capacity argument.

 boolean

equals(Object o)
          Compares the specified Object with this Vector for equality.

 Object

firstElement()
          Returns the first component (the item at index 0) of this vector.

 Object

get(int index)
          Returns the element at the specified position in this Vector.

 int

indexOf(Object elem)
          Searches for the first occurence of the given argument, testing for equality using the equals method.

 int

indexOf(Object elem, int index)
          Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method.

 void

insertElementAt(Object obj, int index)
          Inserts the specified object as a component in this vector at the specified index.

 boolean

isEmpty()
          Tests if this vector has no components.

 Object

lastElement()
          Returns the last component of the vector.

 int

lastIndexOf(Object elem)
          Returns the index of the last occurrence of the specified object in this vector.

 int

lastIndexOf(Object elem, int index)
          Searches backwards for the specified object, starting from the specified index, and returns an index to it.

 Object

remove(int index)
          Removes the element at the specified position in this Vector.

 boolean

remove(Object o)
          Removes the first occurrence of the specified element in this Vector If the Vector does not contain the element, it is unchanged.

 void

removeAllElements()
          Removes all components from this vector and sets its size to zero.

 boolean

removeElement(Object obj)
          Removes the first (lowest-indexed) occurrence of the argument from this vector.

 void

removeElementAt(int index)
          Deletes the component at the specified index.

protected  void

removeRange(int fromIndex, int toIndex)
          Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive.

 Object

set(int index, Object element)
          Replaces the element at the specified position in this Vector with the specified element.

 void

setElementAt(Object obj, int index)
          Sets the component at the specified index of this vector to be the specified object.

 void

setSize(int newSize)
          Sets the size of this vector.

 int

size()
          Returns the number of components in this vector.

 Object[]

toArray()
          Returns an array containing all of the elements in this Vector in the correct order.

 Object[]

toArray(Object[] a)
          Returns an array containing all of the elements in this Vector in the correct order; the runtime type of the returned array is that of the specified array.

 void

trimToSize()
          Trims the capacity of this vector to be the vector's current size.