On cheese and !eggs

In our last lecture we enjoyed some demonstrations of your search engines, including James' fancy boolean queries and David's cute web interface. As we discovered, web search engines are quite complex! They are also a great source of practical problems for a subject on algorithms and data structures, because they involve amortised searching, sorting, string matching, directed graphs, and more. Come back and do more computer science to learn how to make these algorithms run faster and make better use of computer hardware, distributed computation, and automatic language analysis...

Answers to tutorial exercises from chapters 9 and 11

9.1: 2: Θ(m); 7b: {ab,be,ed,dc,ef,ei,ij,cg,gh,il,gk}; 9.2: 1b: T, F, T, F; 11.2: 2a: 2; 2c: no; 11.3: 1: Yes; 2: c; 6: size metric is number of bits b, so problem is O(2^b); 10: b, e.

Preparing for week 11

Please do the following in preparation for week 11:

• Read chapter 11 on Limitations of Algorithm Power (skip 11.4); NB this is chapter 10 in the first edition
• Attempt these problems before the tute: 11.1: 2, 5 (10.1: 1, 4); 11.2: 2, 6; 11.3: 1, 2, 6, 7a, 10;
• Read the week 11 lab exercise on dynamic programming
• Submit project 2

Answers to tutorial exercises from chapters 7 and 8

7.1: 4: yes; 7.2: 3a: 996, 3b: 4980, 3c: 996, 6: by the entry t[c] in the shift table for the text's character c aligned against the last character of the pattern; 7.3: 1b: 3, 1c: 10/6, 2b: 6 (for K=19), 2c: 14/6; 8.1: 2b: yes.

Preparing for week 10

Please do the following in preparation for week 10:

• Read chapter 9 (skip 9.4)
• Attempt these problems before the tute: 9.1: 2, 7b, 8 (2, 6b, 7 in first edition); 9.2: 1b, 7; 9.3: 2b;
• Finish the query system and start writing the product sheets

Answers to tutorial exercises from chapters 5 and 6

5.1: 6: yes, 9: Θ(n log n); 5.4: 4b: C(n)=n!, 4c: S(n)=Θ(n!); 5.5: 3b: W(n)=log3(n), 3c: log2(3) = ~1.6; 5.6: 7b: linear (worst case), logarithmic (average case); 6.1: 3a: O(nm); 6.3: 7b: 25/9; 6.6: 5: is convex hull a triangle?

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).