Exam Problems

Math

You will need to know basic summation formulas listed in section 1.2 of your book.

Big O Notation

Problem 2.11 and 2.12

Which complexity classes do the following functions belong to. List all right answers.

A1. O(1) A2. Ω(1) A3. Θ(1) A4. o(1)
B1. O(N) B2. Ω(N) B3. Θ(N) B4. o(N)
C1. O(N) C2. Ω(N) C3. Θ(N) C4. o(N)
D1. O(2^N) D2. Ω(2^N) D3. Θ(2^N) D4. o(2^N)

f(N) = (N + 5)(N - 6)
g(N) = round(sin(N))
h(N) = 1 + 2 + 3 + ... + N
k(N) = 3^N

Algorithms

Write a function that finds the second largest element of an array (of length at least 2) and runs in O(log N) time.

Problem 2.26

Write an algorithm that computes 2^N in O(log N) time.

Here's a sample problem from TopCoder.com: An instructor wants to create a test consisting of an easy problem, a medium problem, and a hard problem. The test should take between 60 and 75 minutes to complete. Implement a function which, given three integers representing completion time for a variety of hard, medium, and easy problems:

hard[i] = # of minutes to complete ith hard problem
medium[i] = # of minutes to complete ith medium problem
easy[i] = # of minutes to complete ith easy problem

Write a function that given three arrays computes the number of exams that can be made from them:

int numTests(int[] hard, int[] medium, int[] easy) { ??? }

What's the runtime of your problem.

Register at topcoder.com and visit the practice problem area for lost more problems like this one.

Analyzing Algorithms

Be able to compute T_A(N) for algorithms involving nested loops:

for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
count++;
}
}

for(int i = 0; i < N; i++) {
for(int j = 0; j < N * N; j++) {
count++;
}
}

for(int i = 0; i < N; i++) {
for(int j = 0; j < i; j++) {
count++;
}
}

Java Collections Framework

Write a function that finds the maximum element in a list of comparable objects.

Implement a binary search algorithm for a SortedSet.

Write a declaration for the Java Set interface.

True or false: An implementation of the Collection interface must disallow repeated elements.

Musical notes implement the Note interface:

interface Note {
void play();
}

Implement a class called Score that represents musical scores. Implement a play() method that plays each note in the score. (Don't use arrays).

Implement the following methods:

abstract class AbstractCollection implements Collection {
boolean addAll(Collection c) { ??? }
boolean containsAll(Collection c) { ??? }
boolean retainAll(Collection c) { ??? }
boolean removeAll(Collection c) { ??? }
// etc.
}

Trees

Implement the following methods added to the Binary Search Tree presented in class:

class BinarySearchTree {
BinarySearchTree between(Comparable low, Comparable hi) {
// = tree of nodes between hi and low, inclusive
}
Comparable nth(int n) {
// = nth largest element
}
}

Implement an algorithm that displays a binary tree in breadth-first order.

class BinarySearchTree {
BinaryNode root;
void display() {
display level n elements before level n + 1 elements
}
// etc.
}

Hint: Repeatedly remove a node from the front of a queue, place the children of the node at the rear of the queue, then display the node. Do this until the queue is empty.

Implement the binary heap operations

class BinaryHeap {
   void increaseKey(int pos, int pri) {
// increases the priority of element at position i
}
}

Show the result of inserting 1, 2, 3, 10, 8, 5, 9, 4 one at a time into an initially empty AVL tree. Into an initially empty binary heap.

Show the result of inserting 1, 2, 3, 10, 8, 5, 9, 4 one at a time into an initially empty splay tree, then show how the tree readjusts itself after the operation contains(10).