Qualifer Practice Exam: Foundations

Question 5 (9 Points): Below are three recursive java methods. In each case, the

“problem size” n is given by r − l + 1 – the number of elements in the subarray being

processed. For each method do the following:

(1) Derive and explain a recurrence relation for the runtime T(n) of the recursive method.

(2) Give and explain a tight Big- bound on the T(N).

Ugh. Coming back to this problem some other time. (Ugly code.)

Question 6 (5 Points): Suppose the following values are inserted into a “generic” (i.e.,

not self-balancing) binary search tree:

10, 2, 8, 11, 14, 3, 42

(They will not necessarily be inserted in the given order).

Devise an insertion order which will result in the tree having minimum height.

10, 3, 14, 2, 8, 11, 42 (Creates a balanced tree, w/ h=2)

Question 7 (6 Points): Draw a minimum sized AVL tree of height 4 (an AVL tree

with 1 node has height 0). (In other words, among all AVL trees of height 4, draw one with

a minimum number of nodes). How many nodes does your tree have?

Recall that a Binary Search Tree T is an AVL tree if and only if the following holds: for

all nodes v in T, the height of v’s subtrees differ by at most 1. Sometimes this is called

“height-balanced-1”.

x

/ \

x x

/ \ / \

x x x x

/ \ / \ / \ / \

x x x x x x x x

/

x

It has 16 nodes. (Not sure if this needed to have values, but it would not be difficult to come up with values.

Question 8 (7 Points): Below is (part of) a simple java class for a Binary Tree node.

The method isBST is supposed to determine if the given tree is a valid Binary Search Tree.

(E.g., the developer might use it as a sanity checker).

Is the algorithm correct?

If your answer is YES give a concise argument of correctness.

If your answer is NO give and explain a counterexample.

public class BTNode {

private int key;

private BTNode left;

private BTNode right;

// Returns true iff binary tree rooted at

// t is a valid Binary Search Tree with

// respect to the stored keys.

public static boolean isBST(BTNode t) {

if(t == null) return true;

if(t.left != null && t.key <>

else if(t.right != null && t.key > t.right.key) return false;

else return isBST(t.left) && isBST(t.right);

}

}

This is a correct method for determining if a BST is correct. If each sub-tree is correct, than the entire BST is correct. This could be proven via induction. It may not be as pretty as an AVL tree, but it will be correct.

Qualifier Practice Exam: Foundations

Question 7 (5 Points): A complete ternary tree is defined as a tree in which every non-leaf

node has exactly 3 children and every leaf is the same distance from the root. The height of

a complete ternary tree is defined as the distance (number of links) from the root to a leaf.

A ternary tree with just one node has height 0.

Prove the following by mathematical induction: “a complete ternary tree of height h has

a total of (3^(h+1)−1)/2 nodes.”

i. Base Case: Let h=0. (3 ^ (0+1) - 1)/2 = 1. Just one node, h=0.

ii. Let h be an arbitrary value such that h > 1. Assume P(h) holds.

iii. Profit?

I know this section should somehow involve (3 ^ ((h+1)+1)-1)/2, but there really isn't a "left side" to this equation to work with.

Using our induction hypothesis, P(h) = (3^(h+1)-1)/2

Spending too long on this problem, moving on. This is not boding well. ._.

Part II: Data Structures and Algorithms (52 pts)

Question 1 (8 Points): Which of the following problems is known to be solvable in

running time O (n3)? (Give a list of the problem numbers.)

1. Finding the longest simple path from a given start vertex to a given end vertex in a

directed acyclic graph on n vertices with nonnegative integer weights.

2. Finding the shortest path from a given start vertex to a given end vertex in a directed

graph on n vertices with arbitrary integer weights.

3. Finding the longest simple path from a given start vertex to a given end vertex in a

directed graph on n vertices with nonnegative integer weights.

This is referring to Floyd-Warshall algorithm. Definitely 1, 3. It mentions an ability to identify (2), but since the cycles produce arbitrary weights when negative, I'm going to stick with 1, 3.

Question 2 (5 Points): True or False: Circle your final answers.

T [F] If an algorithm runs in O(n) time on the worst case input then it runs in O(n) time on every input.

[T] F Running BFS on a directed unweighted graph with cycles will produce shortest paths from the source vertex to all other reachable vertices (where path length is simply the number of edges).

T [F] log(n!) = o(n2)

[T] F Running DFS on an undirected graph may produce cross edges.

[T] F The lowest weight edge in a graph with all unique edge-weights is always included in any minimum spanning tree

Question 3 (6 Points): Code for the Floyd-Warshall all-pairs shortest paths algorithm (the dynamic programming based O(V 3) algorithm) appears below. Write a loop invariant for the end of the outer loop (on variable k) – i.e., at the point in the code indicated, what can be claimed about adj[i][j] with respect to k. Hint: this loop invariant essentially why the algorithm works!

// adj[][] is initially the weight matrix.

// If there is no edge (i,j) then adj[i][j] = Infinity

// where Infinity is a sufficiently large number (e.g.,

// n*MAX_EDGE_WEIGHT).

for (k = 1 to n){

for (i = 1 to n){

for (j = 1 to n){

adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

}

}

// adj[i][j] is the minimum path as far nodes 1...k are concerned.

}

Question 4 (6 Points):

Part (A) Give example functions f(n) and g(n) where f(n) = o(g(n)).

f(n) = n

g(n) = n^2

o(g(n)) = n

(Because lim(n->inf) (n/(n^2))=0)

Part (B) Is the following statement TRUE or FALSE (if it is true, give a clear argument;

if it is false, give a counter-example):

“If f(n) = o(g(n)) then log(f(n)) = o(log(g(n))).”

False.

Let's use the previous f(n)-(g(n) pair here. log(f(n))= log(n), while log(g(n))= log(n^2) = 2log(n)

lim(n->inf) logn/2logn = .5 =/= 0.

Qualifier Practice Exam: Foundations

Question 3 (4 Points): Suppose you have an alphabet with k characters. How many
strings of length n from this alphabet are palindromes?

Return later.

Question 4 (5 Points): should get a math-writing piece of software. Ugh. Will return later.

Question 5 (3 Points): Write a truth table for the following logical expression.
A V B' -> (A V B)'

A B B' AVB' AVB (AVB)' A V B' -> (A V B)'
T T F T T F F
T F T T T F F
F T F F T F T
F F T T F T T

Question 6 (2 Points): Draw a Venn Diagram (shaded circle diagram) for the following
set.
{x|((x in A) or (x in B)) and x not in A ^ B}

I don't have a drawing utility right now, but that would be two circles that overlap with the circles shaded but not the section of overlap not shaded.

Depth Cues for Augmented Reality Stakeout

Paper by Volkert Jurgens, Andy Cockburn, Mark Billinghurst

I read this paper because it isolates stereo cues and tests them against other augmented reality assistance for placing a stake in the correct position. The study finds no significant difference between the several types of augmentation used. The conclusion is that the task is more reliant on kinesthetic memory than it is on visual cues. There was some discussion of the subjective preferences, but it seems the critical lesson to learn from this experiment is to assess whether a task is as visual cue driven as it seems before committing time and energy to an experiment.

Qualifer Practice Exam: Foundations

Question 1 (3 Points): Conte di Savoia on Taylor Street (between Racine and Ashland) sells 6 different kinds of pastries. How many different pastry trays can they make that have 20 pastries, with at least 3 of those 20 being cannoli? Note that the order of the pastries on the tray does not make a tray different, but having different numbers of pastries does. (I.e., “10 apple strudels and 10 cannoli” is the same tray as “10 cannoli and 10 apple strudels”, but “11 apple strudels and 9 cannoli” is different. You may use exponents and factorial symbols in your answer; you do not need to simplify to a single integer.

Order doesn't matter, so this is a combinations problem. Now 3 of the twenty positions are already handled since 3 have to be cannoli. The formula for combinations with repetition is (n+k-1)!/k!(n-1)! Since ALL of the combinations will have 3 cannoli, we are only choosing 17 items of the 6 types. n=17, k=6. (22)!/6!16! (The problem says simplifying is unnecessary, but let's finish for the sake of cleanliness.

(22)!/6!16! = (17*18*19*20*21*22)/2*3*4*5*6 = 17*3*19*7*11 = 74613 different plates.

Question 2 (5 Points): Suppose there are 10 students in a class and that each will receive one of the following grades: A, B, C, D, F. For each of the following you need not give a final numerical answer; an equivalent expression is sufficient.

Part I: How many distinct ways are there for the instructor to assign the grades?

Now order matters, because student 1 is not student 2. So there are 5 grades being chosen (n), ten times (r). Therefore, there are 5^10 distinct ways to assign the grades.

Part II: Now suppose the Dean has stated that at least two of the students must receive F’s. With this added constraint on the instructor, how many distinct grade assignments are there?

So the tricky thing I'm not sure about here is that the core part is definitely 5^8, in that the eight students without F's can have any grade. Come back.

Introduction

My name is Tia Shelley and I am a graduate student in computer science, pursuing human-centered design and specifically the human computer interaction tree. You have likely found this blog through a link I delivered, and thus, that's the depth of introduction to me that I feel I should present.

Over the years, I've written many different types of blogs. On-going stories, the livejournal that documents most of my high school career and all of my college years. This blog is not for that. This is for documenting the path to becoming a PhD. That means, in general, this blog is going to be utterly filled with summaries, abstracts, and various links to projects I'm working on. I'm keeping this to keep track of my sources because it's easier to search a web page than it is to search a binder full of papers. I'm using this to make sure I process every paper I read at least to the depth that I can post a summary and brief review of each article. My frustrations and successes with courses and the graduate school life style will, for the most part, be something for my personal journal and not for this particular blog, unless it has some greater impact than just my mood.

Last semester, I took Virtual Reality and Networking. Networking will probably come up again while I'm studying for my qualifier exams over the next month, but VR has a very high potential of becoming a common topic despite the fact that the class is over. This semester, I'm taking User Interface Design, Research Methods in Computer Science and Video Game Design. Any projects for these classes will probably be roughly outlined here under tags for each class. General research will be tagged with authors, subject, and either review or summary.