CIT594 Midterm Exam Spring 2008 Name_________________________________________

Please keep all your answers short and to the point. Do not provide extra information that was not asked for.

1. (4 points) Write a Java snippet to create an `int[][]` array named `ragged`, having 25 rows, where each row i has i % 4 elements.
int[ ][ ] ragged = new int[25][ ];
for (int i = 0; i < ragged.length; i++) {
ragged[i] = new int[i % 4];
}

2. (2 points) If `log2N = x`, then `N = `2x.

3. (8 points) Here are two versions of a method to compute Fibonacci numbers. Beneath each one, indicate its expected running time (Big-O notation).
 `private long fibonacci_1(int n) { if (n == 0 || n == 1) return 1; return fibonacci_1(n-1) + fibonacci_1(n-2);}` `private long fibonacci_2(int n) { int first = 1, second = 1, next = 1; for (int i = 1; i < n; i++) { next = first + second; first = second; second = next; } return next;}` O(n!), or approximately O(2n) O(n)

4. (4 points) What can you say about the order of elements in the array when you are halfway through a selection sort?

All elements in the left half of the array are in their correct, final position.

5. (2 points) If a program needs to be optimized because it is running too slowly, what should your first step be?

Use a Profiler to find where the bottlenecks are.

6. (2 points) When does the Collection method remove(E o) return false?

When the collection is unchanged (because o wasn't in it).

7. (10 points) Write the complete signature, including the return type and generics, for each of the following methods in the Collection interface:

2. contains
boolean contains(Object o)
3. containsAll
boolean containsAll(Collection<?> c)
4. iterator
Iterator<E> iterator()
5. singleton
public static <T> Set<T> singleton(T o)
Sorry, this is actually in the Collections class

8. (4 points) Assertions and Exceptions are similar. When should you use each?

1. Use an assertion when:
You know that some condition can "never" happen.

2. Throw an Exception when:
A problem has occurred that is outside the control of your code.

9. (4 points) List Dr. Dave's four rules for doing recursion.

1. Do the base cases first.
2. Recur only with a simpler case.
3. Don't both use and modify global variables.
4. Don't look down.

10. (2 points) Under what circumstances will an Iterator method throw a ConcurrentModificationException?

When the collection being iterated over has been changed by some external agency.

11. (2 points) Declare and define a Java variable named `stuff` as an `ArrayList` containing a `List` of `String`s.

List<String> stuff = new ArrayList<String>();

12. (5 points) Write a recursive boolean method to determine whether an int array contains any negative numbers. (Your method should take two parameters: the array itself, and an int index into the array.)

private boolean containsNegativeNumbers(int[ ] array, int index) {
index--;
if (index < 0) return false;
if (array[index] < 0) return true;
return containsNegativeNumbers(array, index);
}

13. (4 points) Given the following binary tree, in what order are the nodes visited by each technique?
 ` C \ O / \ M P / \ E U / T` (a) preorder   C O M E P U T (b) inorder   C E M O P T U (c) postorder   E M T U P O C (c) depth-first iterative deepening   C  C O  C O M P  C O M E P U  C O M E P U T

14. (2 points) What is a "factory method"?

A static method used to take the place of a constructor.

15. (3 points) What is wrong with the following, and how would you fix it?
SortedSet<Object> set = new SortedSet<Object>();

SortedSet is an interface, not a class.
Replace with SortedSet<Object> set = new TreeSet<Object>();

16. (3 points) Write one BNF rule to define a Java if statement. You can assume that <boolean condition> and <statement> have already been defined.

<if statement> ::= "if" "(" <boolean condition> ")" <statement> [ "else" <statement> ] ";"

17. (5 points) Suppose you have a singly-linked, nonempty list named list, declared as class MyList { public int value; public MyList next; }. Without using any methods of this class, write a recursive method int last(list) to return the last value in the list.

private int last(MyList node) {
if (node.next == null) return node.value;
else return last(node.next);
}

18. (2 points) Assuming the class declaration in the previous question, how much storage is allocated by the declaration MyList list; and what are its initial contents?

Enough storage to hold a reference (4 bytes), initially null.

19. (4 points) Suppose you have a method boolean symbol(String s) as defined in the Recognizer assignment. Write a method boolean dashes() that will recognize one or more consecutive "-" symbols.

private boolean dashes(String string) {
if (!isSymbol("-")) return false;
while (isSymbol("-")) { }
return true;
}

20. ( 2 points) To program a state machine in Java, put a switch statement inside a loop statement.

21. (2 points) Draw a state machine to recognize a Java comparator (the comparators are  <, <=, ==, !=, >=, and >).

22. (2 points) What is the difference between the Stack methods peek and pop? (Be sure to tell which is which.)

peek returns the top element of the stack, pop removes the top element from the stack and returns it.

23. (2 points) An ADT should not include too many "convenience" methods. Why not?

The more methods a class has, the harder it is to learn, and the harder it is to recognize which methods are useful.

24. (4 points) Circle the legal statements, cross out the illegal statements:

1. List<String> list = new List<String>();

2.  List<String> list = new ArrayList<String>(); OK

3. ArrayList<String> list = new List<String>();

4. ArrayList<String> list = new ArrayList<String>(); OK

25. (3 points) Briefly define "tracer code."

Initial code that is written to see whether a project is proceeding in the right direction.

26. (4 points) Give two advantages of storing information as plain text.

* "Insurance against obsolescence." Doesn't depend on the application that wrote the data to have survived.
* "Leverage." Virtually every software tool can work with plain text.
* "Easier testing." No special tools needed to add, updata, or modify the test data.

27. (3 points) How does the "Broken Window Theory" apply to programming?

"Don't leave 'broken windows' (bad designs, wrong decisions, or poor code) unrepaired."
If you can't fix it right away, at least mark it as needing work.

28. (6 points) List three advantages of using TDD (Test Driven Design).

* TDD encourages program development to proceed in small, easily implemented steps.
* TDD helps focus on how the functionality will be used.
* TDD helps clarify what methods should do.
* TDD encourages writing methods that are more testable.
* TDD encourages writing methods that are simpler and single-purpose
* TDD encourages writing methods that are more independent of the environment
* TDD leads to more modularized, flexible, and extensible code.
* TDD reduces development costs by catching problems early.
* TDD leads to better code quality, with fewer bugs.
* With TDD, tests actually get written