Course pages 2011–12

# Algorithms II

2011–2012

**Principal
lecturer:** Dr Frank
Stajano

Email to the address frank.stajano--algs2 at cl cam
ac uk (a special address containing two consecutive hyphens) will be
given priority over that sent to other addresses.

**Taken by:** Part IB

## Syllabus

The official syllabus has its own page. More accurately, here is what we actually did in lectures and is considered examinable, with reference to CLRS3 and mentioning any book sections you may skip from the relevant chapters.

### 2011-11-04 Fri

17.1, 17.3

You may skip 17.2, 17.4

From last year: revise 6.5 and binomial heaps (problem 19-2) if you forgot them.

### 2011-11-07 Mon

19.1, 19.2

### 2011-11-09 Wed

19.3, 19.4

### 2011-11-11 Fri

20.1, 20.2

### 2011-11-14 Mon

20.3

### 2011-11-16 Wed

21.1, 21.2, 21.3, 22.1, 22.2, 22.3

You may skip 21.4, 22.5

### 2011-11-18 Fri

22.4, 23.1, 23.2

### 2011-11-21 Mon

24.1, 24.3, 24.5

You may skip 24.2, 24.4

### 2011-11-23 Wed

25.1, 25.3

You may skip 25.2

### 2011-11-25 Fri

26.1, 26.2, 26.3

You may skip 26.4, 26.5

### 2011-11-28 Mon

27.1

You may skip 27.2, 27.3

### 2011-11-30 Wed

33.1, 33.2, 33.3

You may skip 33.4

## Past exam questions

Questions can be found under Algorithms II but also, for historical reasons, under Data Structures and Algorithms (the parent course for both Algorithms I and Algorithms II); if you pick from the latter set, be sure to select questions dealing with topics covered in this year's syllabus.

## Information for supervisors

This year the course has two new lectures. You want the new guide. Contact lecturer for access, stating your name, your CRSID and, if you are a student, your PhD supervisor.

## Lecture handouts

Distributed during the first lecture. It will be to your advantage to bring your handout to every lecture, together with a notebook with non-detachable pages and a few coloured pens. Further printed copies of the handout are available from the student administration office. An electronic copy is also available: please do not print it again yourself and please do not circulate it outside cam.ac.uk.

## Microchallenges

### 2011-11-04 Fri

CDLL (expired)

### 2011-11-09 Wed

lg lg nanochallenge (expired)

### 2011-11-25 Fri

MST microchallenge (expired)

## My heroes!

### 2011-11-04 microchallenge (circular doubly-linked list)

Timothy Goh |

James King |

David Brazdil |

Eduardo Munoz |

Lewis Brown |

Rory McCann |

Thomas Chetwin |

Dylan Ede (8 mins past the deadline :-)) |

### 2011-11-09 nanochallenge (lg lg x)

Tom Smith (7 mins after the lecture!!!) |

Thomas Chetwin |

Timothy Goh |

Rolandas Glotnis |

David Brazdil |

James Morley |

### 2011-11-16 (spontaneous initiative, not a microchallenge)

Szymon Sidor, for suggesting and implementing a non-recursive alternative (Kahn's algorithm) for topological sort. There is pseudocode on Wikipedia.

### 2011-11-25 microchallenge (MST)

Timothy Goh |

Lewis Brown |

Max Spencer (Prim only) |

"I know my submission is totally late and you might not even have read these emails, but I am so glad I figured it out I just wanted to send it anyway! This is the best feeling, this is why I love programming."

## Additional resources

### Fibonacci heaps

The original paper on Fibonacci heaps is available from the ACM digital library (or cached).

Here is the animation that I used in lectures (click for multi-page pdf).

### Visualization of graphs and other linked data structures

Worth becoming familiar with DOT and Graphviz; then, when you write programs to practice what you study in this course, with modest additional effort you can neatly display what goes on inside.

## Errata corrige

Negative line numbers are counted from the bottom of the page. Top line (excluding headers) is 1. Bottom line (excluding footers) is -1.

Page | Line | Errata | Corrige | Found on | by |
---|---|---|---|---|---|

8 | pseudocode line 29 | Payload p; | Data payload; | 2011-12-03 | Heidi Howard |

15 | -4 | cost of Dijkstra is |V| times | cost of Dijkstra is dominated by |V| times | 2011-11-03 | author |

19 | -3 | void decreaseKey(FibNode n, int delta) | void decreaseKey(FibNode n, int newKey) | 2011-12-03 | Heidi Howard |

20 | 1 | Decrease the key of node n by delta | Decrease the key of node n to newKey | 2011-12-03 | Heidi Howard |

20 | 2 | and delta is non-negative | and newKey < n.key | 2011-12-03 | Heidi Howard |

20 | 5 | Decrease that key by the stated amount | Decrease n.key to the new value | 2011-12-03 | Heidi Howard |

20 | 21 | with the largest possible delta (conceptually decreasing the key to -infinity) | with a newKey of -infinity | 2011-12-03 | Heidi Howard |

21 | -16 | given heap in a given state | heap with n nodes | 2011-11-03 | author |

21 | -16, -14, -13, -13, -13 | d | d(n) | 2011-11-03 | author |

21 | -10 | O(d) = O(lg n) | d(n) = O(lg n) | 2011-11-03 | author |

21 | -3 | void decreaseKey(FibNode n, int delta) | void decreaseKey(FibNode n, int newKey) | 2011-12-03 | Heidi Howard |

22 | 13 | This is still a constant, | This is still a constant with respect to n, | 2011-11-03 | author |

22 | -14 | in a Fibonacci heap | in an n-node Fibonacci heap | 2011-11-03 | author |

24 | 8 | were the fastest | were the asymptotically fastest | 2011-11-01 | author |

24 | 20 | set: insert() | set (except that we disregard satellite data): member(), insert() | 2011-11-01 | author |

25 | -6 | the total cost is O(1) | the total cost is O(√ u) | 2011-11-11 | author |

30 | -26 to -24 | If it's not the base case, we set the appropriate summary bit (direct access, therefore constant time) and we recursively insert the key into the correct cluster. | If the node is empty, insert directly at constant cost. Otherwise, insert into both cluster and summary. However only one of these two calls is recursive: if the cluster was empty, insertion into cluster has constant cost and insertion into summary is recursive; otherwise, insertion into cluster is recursive and insertion into summary is not needed because it's already marked as non-empty. | 2011-11-14 | author |

32 | lines 10 and 11 of first pseudocode block | PRECONDITION: there exists a set containing x and a different one containing y. | PRECONDITION: x != y. | 2011-12-27 | Simon Blessenohl |

42 | lines 11 to 14 of Kruskal listing |
for edge in E: if D.findSet(edge.start) != D.findSet(edge.end): A.append(edge) D.union(edge.start, edge.end) | for edge in E: startSet = D.findSet(edge.start) endSet = D.findSet(edge.end) if startSet != endSet: A.append(edge) D.union(startSet, endSet) | 2011-12-27 | Simon Blessenohl |

45 | -15 to -14 | equal to the number of vertices in the graph | eqal to the maximum possible length of a shortest path, |V|-1 | 2011-12-16 | Tom Sparrow |

47 | -8 | cost of decreaseKey. | cost of decreaseKey(). | 2011-11-01 | author |

59 | 5 | computation on on | computation on | 2011-11-19 | author |

59 | 15 | >= | ≥ | 2011-11-19 | author |

61 | 13 | (and the next vertex may or may not be a source at that point) | (and the next vertex will be a source at that point) | 2011-11-28 | Ben Thorner |

63 | -4 | Extrapolating to 256 processors | Extrapolating to 512 processors | 2011-11-19 | author |

If you find any more errors, please mail them to me and I'll credit you here and in the next version of the handout. Recursive thanks also to Simon Iremonger for finding a further error, now corrected, in the Errata Corrige itself.