News Uni Dev Res Blag

/u/ - Preparing for the Java exam

2010/05/06 - 17:35

Update 2010/05/06 @2240 ~ Second task full of issues, resolved it

The exam will primarily contain theoretical questions; the amount of actual coding is abysmal. Known topics are:
Searching, Sorting, B-Tree insertion, Nabo-multilister, and some more. Djikstra's Algorithm, also Threaded Binary Trees.

Nabo Multilister

A relational graph represented in a more space-efficient way for sparsely populated graphs. This implmentation is for simple graphs; some modifications are necessary for weighted graphs. I do not know the origin of this algorithm.

I am NOT good at describing stuff. You're probably better off just looking at the pretty images.

Example #1 The first example

Sorry for the poor quality mspaint mashup, I didn't exactly have time to prettify this during the lesson. Anyways. A question on the exam will present you with - the graph itself, and tell you to present its neighbour multilist. Let's see how you go about doing this.

②. First off, list all nodes {A..E} and edges v{1..5} vertically. Remember to label the nodes "Head nodes" (fuck knows why). Then we will be drawing some arrows.

③. For each edge, from the first (v1) to the last (v5), draw an arrow from each node on this edge to the edge itself, given that this node has not been "used" yet. In other words, we will draw ONE arrow from each node to the first graph it appears on. While I don't see any point in doing this, I'm sure there's some ingenious reason.

Next; draw a column for each edge. The columns should be four cells wide. We shall fill the two first cells in each column first, then fill the remaining two in each column afterwards.

④. For each edge, fill in the names of the nodes appearing on this edge. Note the alphabetical order.

⑤. The third cell in each row is to contain the next occurence of the node mentioned in this row's first cell. Same for the fourth/second cell. Find the next column containing the same node, and fill it in here. X specifies last occurence.

The only required arrows during an exam are the ones in step ③. The other arrows are for illustrational purposes.

Example #2

The solution for the practice task handed out in class.

Copyright © 2010 Ed Edland