Preparing for week 9

Please do the following in preparation for week 9:

• Read chapter 8 (skip 8.3); Review previous chapters
• Attempt these problems before the tute: 8.1: 1, 2; 8.2: 1, 7; 8.4: 1a, 3;
• Complete indexer and pageranker, and start on the query system.

Attributes of the Melbourne Graduate

This University "expects its graduates to be educated and well-informed, able to contribute effectively to their communities wherever in the world they choose to live and work." Melbourne graduates are expected to have a rich set of qualities and skills.

Project 2: Web Search Engine

Search engines provide efficient keyword lookup over large collections of web pages. For the second project you will implement a simple search engine, analyze the efficiency of its algorithms, and write up your work in the form of a product sheet. The project specification was handed out in today's lecture, and is also available from the CSSE Helpdesk and from the online handouts page (linked from the sidebar).

Probability of collision

In yesterday's discussion of hash tables I asked how many cells do we need to randomly occupy in an array of size 1,000,000 before there is a 95% chance of collision. It turns out to be about 2440; i.e. the array only has to be 0.244% full! (See p18 of this week's slides, available online or via the CSSE Helpdesk, and the program circulated on the discussion list).

Preparing for week 8

Please do the following in preparation for week 8:

• Read chapter 7 (skip Boyer-Moore and B-Trees);
• Attempt these problems before the tute: 7.1: 3, 4; 7.2: 2, 3, 6; 7.3: 1, 2, 3, 8;
• Complete the week 7 lab exercise on PageRank;
• Prepare for the week 8 lab exercise on Dictionaries.

Week 7 Lab: Google PageRank

In next week's lab you will extend your directed graph code to implement Google PageRank [1, 2, 3]. It will help if you read up on PageRank before the lab, and also take a look at the lab notes, available from our handouts page. We'll use your work in the second project.