Data Structures Sample Midterm

NOTE: Unless otherwise indicated, all logarithms are in base 2.

Select the tightest big-Oh notation for the following expressions:

i) 4 + 8 + 12 + 16 + ..... + 4n
ii) 1 + 2 + 4 + 8 + 16 + ..... + n
iii) n*(1 + 2 + 3 + ..... + n)
iv) log (n^2) + (log n)^2
v) n + 2^(2*log(n))

Show the following:

i) n! = O(n^n)
ii) 1^2 + 2^2 + 3^2 + ..... + n^2 = Theta (n^3)
iii) n / (sqrt(n) + 1) = O(n)
iv) sqrt(n) + log(n) = Omega(sqrt(n))

Using mathematical induction, show that:

1^2 + 2^2 + 3^2 + ..... + n^2 = n(n+1)(2n+1)/6

Analyze the complexity (in big-Oh terms) of the following selection-sort routine. The routine picks out the largest element in the current list and exchanges it with the last element. It continues until the list has only one element:
```
 
	for (i = n-1; i > 0; i--) {
		MaxPosition = i;
		for (j = 0; j < i; j++) {
			if (a[j] > a[MaxPosition])
				MaxPosition = j;
		}
		exchange(i, MaxPosition);
	}
```
a) Give a Theta(n) algorithm for computing a^n, given a and n.

b) Give a Theta(log n) algorithm for computing a^n, given that n is a power of 2.
You are given a data structure stack with the following ADT:
```
push(element)
pop()
size()
```
Each of these operations runs in O(1) time. Use pseudocode to implement the following Queue ADT using the stack ADT only. What is the complexity of each of your methods?
```
enqueue(element)
dequeue()
size()
```
Note: you do not have to implement a linked list or an array. Instead, you must use only the three methods in the stack ADT.

Hint: Use multiple stacks.
Insertion into Ranked Sequences implemented as arrays take O(n) time and location in positional sequences using linked lists taks O(n) time. Describe an implementation using a linked list of fixed size arrays that reduces this time. Assume that each node in the linked list contains a count of the number of elements in array of the node. If an element must be inserted between two nodes whose arrays are filled, a new node is created in between and the element is inserted into the node. Note that there may be partially filled arrays in the list. If the array in each linked list node is capable of carrying 10 elements, what is the runtime of this data structure for location and insertion (do not ignore any constants). Write pseudocode for location and insertion. (While computing complexities, assume that all nodes in the linked list are full.)