CIT 594 Final Exam Spring 2006, Dave Matuszek Name _______________________________________

1. (8 points) Tell the running time of each of the following algorithms:

1. __________ Bubble sort

2. __________ Selection sort

3. __________ Insertion sort

4. __________ Binary search (when unsuccessful)

5. __________ Heapsort

6. __________ Quicksort (worst case)

7. __________ Creation of a Huffman tree

8. __________ Dijkstra's shortest-path algorithm

2. (3 points) Tell whether each of these specifies a lower bound, upper bound, or exact bound:

1. Big-O specifies a(n) ____________________ bound.

2. Big-Θ specifies a(n) ____________________ bound.

3. Big-Ω specifies a(n) ____________________ bound.

3. (4 points) We will define a "word" to consist of one or more syllables. Each syllable consists of one or two consonants followed by a vowel, except that the first syllable may be a single vowel and the last syllable may end with a single consonant. Assume that the terms <vowel> and <consonant> have already been defined (i.e. don't write them yourself), use BNF (or EBNF) to define a <word>. Example words: a, at, kokomo, tokamak, ashanti. (Hint: Use scratch paper, and copy your answer to the exam.)

4. (2 points)
1. What advantage does Java's TreeMap have over HashMap?

2. What advantage does Java's HashMap have over TreeMap?

5. (4 points) What are your instructor's four rules for writing a recursive method?

6. (2 points) Suppose in a (correct) Java program you find the line
for (Pet pet : pets) {
tell everything you can deduce about the pets variable.

7. (3 points) In which Java package would you expect to find:

1. a method for sorting an array?

2. a method for appending two Lists?

3. a method for testing whether a file exists?

8. (1 point) When should you use Comparator rather than Comparable?

9. (8 points) Consider the following binary tree:
 Is this a sorted binary tree? Why do you think it's sorted (or not sorted)?
In what order will the nodes of this binary tree be visited:

1. In preorder?

2. In inorder?

3. In postorder?

In what order will the nodes be examined by each of the following:

2. A depth-first search?

3. A depth-first iterative deepening search?

10. (1 point) If you override hashCode(), you must also override _____________________.

11. (2 points) Jack has the job of assigning n tasks to n people (one task per person). Each person has told Jack how happy he/she would be (on a scale of -1.0 to +1.0) to do each task. Jack wants to maximize the total happiness, so he writes a program that tries every possible assignment of tasks to persons, and chooses the best.

1. What is the name for the kind of algorithm Jack is using?

2. How long will his program take?

12. (2 points) Jill has the same problem as Jack (above), but her program finds the best (happiest) matching of some one person to a task and assigns it, then repeats the same process with the remaining persons and tasks, until none are left.

1. What is the name for the kind of algorithm Jill is using?

2. How long will her program take?

13. (14 points) Briefly define each of the following. Do not give examples.

1. mutative transformer

2. weakly connected (digraph)

3. factory method

4. heap property

5. blind search

6. collision

7. checked exception

14. (2 points) The A* search method is a kind of ____________-first search. It uses the formula f(n) = g(n) + h(n); in this formula, what is the meaning of n?

15. (2 points) What are the two most important differences between a Set and a List in Java?

16. (3 points) Messages are composed of the letters A, B, and C. On average there are ten times as many As as Bs, and ten times as many Bs as Cs. (For example, a message might start out as AAAAAAABAAA...). What is a suitable Huffman code for these messages?

A =                    B =                    C =

17. (1 point) Suppose a class definition begins as follows:
public class Person {
String name;
GregorianCalendar dateOfBirth;
int age;
...

What style rule does this violate?

18. (1 point) A heap (as in heapsort) is useful in implementing what ADT?

19. (3 points) Using Java's generics,
1. Declare a HashMap named map whose keys are Strings and whose values are Doubles.

2. Write an "enhanced for loop" to find the total of the values in this HashMap.

double total = 0.0;
for (                                                   ) {
total = total +
}

20. (1 point) A maze can be created by finding a(n) _________________________ of a graph.

21. (1 point) An algorithm is considered intractable if it requires __________________ time.

22. (1 point) What is the relationship between an alpha cutoff and a beta cutoff?

23. (1 point) If an adjacency matrix is symmetric about the main diagonal, what does this imply about the digraph that it represents?

24. (1 point) Which digraph representation is more generally useful, an adjacency set representation, or an edge set representation? (Don't explain why.)

25. (1 point) In class I described how to build a maze. For an NxN maze, what is the running time of this algorithm?

26. (3 points) sin = ------------ , cos = ----------- , tan = ------------ .

27. (1 point) What can you do with a "pointer" that you can't do with a "reference"?

28. (4 points) Each of the following Collection methods corresponds to a mathematical operation on sets. Give the names of the corresponding mathematical operations.

1. containsAll(Collection c) corresponds to ______________________________ .

2. addAll(Collection c) corresponds to ______________________________ .

3. removeAll(Collection c) corresponds to ______________________________ .

4. retainAll(Collection c) corresponds to ______________________________ .

29. (3 points) An Abstract Data Type specifies these two things:

but does not specify:

30. (1 point) If you get a "Concurrent modification exception," what have you probably done wrong?

31. (12 points) True or false:
1. _____ A hashCode( ) method must return different values for different objects.

2. _____ The split(String) method in String takes a regular expression as its parameter.

3. _____ The trig functions (sin, cos, tan) expect their arguments to be in radians.

4. _____ The Stack class extends Vector.

5. _____ A method may have at most one vararg parameter.

6. _____ The java.util package defines Stack and Queue classes.

7. _____ Genetic algorithms work better with sexual, rather than asexual, reproduction.

8. _____ Genetic algorithms work best with a moderate to large probability of mutation.

9. _____ Mutation in genetic algorithms helps combat lack of genetic diversity.

10. _____ State-space searches should be designed with as few operators as possible.

11. _____ Backtracking is basically depth-first tree searching.

12. _____ Breadth-first searches usually require more memory than depth-first searches.

32. (1 point) How can you easily turn a nonrecursive depth-first search into a breadth-first search?

33. (3 points) When you need to time a method, tell three things you can do to improve the accuracy of the timing.