CRA-W Grad Cohort

This weekend, I took a break from the last-week-of-school panic to attend a conference in Seattle for women in computer science. It's actually not so much a conference as let's all get together, eat free food, and talk about how to get through graduate school. And for the most part, I learned quite a bit and enjoyed myself quite thoroughly and actually made some new friends.

There were certain parts that concerned me. The two sessions that one wouldn't have seen at a similar event for any gendered cs grad student were...pretty gender biased. In a bad way. The suggested reactions to possible situations made me uncomfortable. They were all very passive reactions, which only leads to the persistence of the attitude that it's okay to say that someone only got their position because of their gender, or to interrupt a female speaker just because they're female. I do not believe in simply sitting back if I'm having a conversation with someone and someone else butts in and tries to end my conversation preemptively. I am far more likely to inject myself into the "new" conversation, politely. Restraint is something I should learn.

But there were constant references to "having a cry" when a rejection letter was received. There were the 'jokes' about shopping. If we're talking about activities that are relaxing, why are they all so stereotypically gendered activities? It...perturbed me. For all of the information I received, the attitudes I encountered at CRA-W were not really...about being equal. They were about establishing our femininity within being a computer scientist and somehow trying to be normal.

I have no desire to be normal. Not a normal woman, whatever that means, not a normal computer scientist, not a normal anything. Will I return to CRA-W next year if they fund me? Yes, I likely will. The opportunity to network with women in computing research is much too large to ignore. Will I perhaps be skipping the sessions on "Building Self Confidence" and "Being a Woman in Computing Technology" ...no, because I think it's critical that someone stands up and says that we should not let even "unintentional" sexism stand.

On a somewhat related note, if ever you have to be stranded in an airport for two hours, SeaTac is a great one for it. Comfortable seats, true free wi-fi, and outlets galore.

Qualifier Results & Summer Plans

Qualifiers Scores:

Foundations: No Go. Retry in September. We received the exams back, and I really need to study algorithms in depth, as well as some dynamic programming techniques. Whoops.

Human Centered Computing : Conditional Pass. I have to take Artificial Intelligence this Fall, which is cool. My AI course was not a practical course, instead being largely a theoretical approach. UIC emphasizes practice so much that I'm actually mildly excited. I did rock the HCI portion of the HCC exam, and that delighted me.

Systems: Pass. I find it peculiar that the only test I passed absolutely on the first try is the only one I didn't explicitly study for, but I'll take what I can get. Primarily my success here was due to taking Networking the prior semester.

While I attempted to apply for internships, I was largely unsuccessful. For some reason, places that are looking for research interns actually desire research experience. Fancy that. Luckily for me, I've been talking at length with Dr.Leilah Lyons about a project that only recently was given a small budget so that my summer will be partially funded, which is a delightful development that makes my summer much less stressful. The project?

The project involves two subjects that I'm aware of and one that I've studied with just a bit of depth. Essentially, it's an augmented reality project that will take AR input for a system, and then run a simulation for that system, based on the input. I actually question the extent to which this is Augmented Reality to some extent, since it's being used as input only, and not active input. Once the images are captured, they are not then acknowledged again unless another capture is requested.

The semester is coming to a close and Kenchi Games is taking up quite a bit of my time. Reach has been an interesting project with many, many problems that we're working on, a day at a time. Hopefully, we'll be making another video capture this week to post on youTube. The original intent had been to do that far more often than we have, but the amount of progress between weeks has been less than desired.

Additionally, for User Interface Design, we're now working on small projects in Android. This slow build up will hopefully lead to a good understanding of the API so that I can build small applications over the summer and increase my portfolio of work. (Speaking of portfolio, another high priority item on the list is definitely completing a portfolio website by the end of summer, since the school year seems to not include much real time.)

Qualifier Exams

Last Thursday and Friday were the qualifier exams. After reading some ten texts on computer science in the short time of a month, I still feel that I was under prepared for the exams and should've started studying about the same time I was accepted into UIC if I had wanted to actually excel, instead of merely feeling that it was possible I passed certain portions of the exams.

From here, things start to get interesting. When the results from quals come back, quite a bit changes. But for now? For now I am content to know that I have two possible research projects lined up, one possibly starting this summer. Now that I am not aggressively reading textbooks, it's time to turn back to the original plan for this blog, which implies doing quite a bit more reading of various journals and actually writing summaries on the interesting articles. I'll be posting a few of the summaries I've done for CS 594 here in the next few days, as well as the cleaned up version of our report for User Interface Design.

Additionally, if anyone is interested in what we are currently doing for Video Game Design, you can track our progress at Kenchi Games. That website should continue to be updated over the semester.

Human Centered Computing Exam: HCI

HCI Question 1 – 100 points:

The interface for a typical elevator is still based on physical buttons that allow the user to select a specific floor, hold the door open, close the door, or ring the alarm bell. With the price of flat panel displays dropping, it is possible that in the coming years we will see touch screen LCD panels replacing the existing designs.

A – What are the advantages of completely replacing a typical elevator button panel like the one

shown below with a touch-screen LCD panel?

Completely replacing the panel would allow for more information to be presented. There would be fewer individual mechanical pieces that could go faulty. Particularly in the case of some mechanical error, the LCD screen could provide information about what had happened to the caller to be relayed to the technician.

B – What are the disadvantages of that complete replacement?

With all changes there is a learning curve, and the newness may cause some confusion. Going beyond that, an LCD screen is unlikely to provide the same immediate feedback when a 'button' is pushed.

C – Suggest a hybrid design combining the current interface and an LCD touch screen that

maximizes the advantages and minimizes the disadvantages. Note which principles you

are using and how they affect your design.

HCI Question 2 – 33 points:

On some computer systems, using a mouse to move the cursor to the corner of the screen causes the system to sleep or go into alternative display modes. Is this a Fitts’ task? Explain your answer.

Yes, this task is a Fitts task. Since Fitts' Law deals with the placement and utilization of space for the distribution of objects for a task, placing the most frequently used objects near the center of the task, the act of placing a common task that shouldn't interfere with normal use at the edges of the screen falls under that umbrella of tasks.

HCI Question 3 – 34 points:

Touch-screen interactions often face the problem that the user’s finger occludes the object being

manipulated (e.g., selected, moved).

A - Describe two techniques that might potentially mitigate this problem, and discuss the

advantages and disadvantages of each technique.

One technique would be to have an offset of the touch, displaying the selection as slightly above(to avoid occlusion by the rest of the finger) of the contact. The advantage of this technique

B - Describe a procedure (including subjects, tasks, and analysis methods) for characterizing the

performance of the two proposed methods.

More later. Need to go back to foundations and really hard core study so...backing away from this for now. I feel this is easier and more comfortable than hard comp sci, and that's not cool.

Qualifier Practice Exam : Foundations

Part III: Theory of Computation (40 pts)
Question 1 (3 Points): Consider the following language over the alphabet of the 10
decimal digits (i.e., {0, 1, , 2, 3, 4, 5, 6, 7, 8, 9}):
L = {n : n = closing price of oil rounded to nearest U.S. dollar on Dec. 29, 2017}
What is the smallest class of languages of which L is a member?

(a) Languages decidable in linear deterministic time.
(b) NP
(c) NP-complete languages (?)
(d) P
(e) The undecidable languages

Question 2 (3 Points): The FUBAR problem is a new decision problem that you have
just begun to study. So far you have been able to show the following two things about the
FUBAR problem:
• There is a polynomial-time reduction from the Satisfiability problem (“Is a given
Boolean formula satisfiable?”) to the FUBAR problem.
• You have a nondeterministic method that solves the FUBAR problem and that never
consumes more than a polynomial amount of space.
What do you know for sure about the FUBAR problem given current knowledge?
(a) It is NP complete
(b) It is in the complexity class NP
(c) It is in the complexity class P
(d) It is not in the complexity class P
(e) It is NP hard.

Question 3 (4 Points): The minimum number of states of a Deterministic Finite State
Automaton (DFSA) over the alphabet {0, 1} recognizing the language containing the single
string of n 0s (n is fixed) is:
(a) 2n (b) n + 2 (c) n^2 (d) 10. (no)
Not sure if this is saying 0*1*(0^n)1*0* or just 0^n

Question 4 (4 Points): Let L be the language over {0, 1} consisting of all strings that
have a 1 in the third symbol from the end (e.g., the string 0100 is in L). The minimum
number of states of a DFSA recognizing L is:
(a) 50 (b) 5 (c) 8 (d) 100.

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.