Preparing for week 7

Please do the following in preparation for week 7:

• Read chapter 6 (6.2 only Gaussian Elimination, 6.3 only 2-3 Trees, skip 6.5);
• Attempt these problems before the tute: 6.1: 3, 11 (3, 10 in first edition); 6.3: 7 (for a different input); 6.4: 1, 6; 6.6: 5;
• Complete the week 5 lab exercise on directed graphs.

Answers to tutorial exercises from chapters 3 and 4

3.2: 5a: 4,980; 5b: 996; 5c: 1,992; 3.3: Θ(kn^2); 3.4: 1a: Θ(n!); 1b: 15,16,18,20; 4.1: 5a: Θ(n^2); 5b: Θ(n^2 log n); 5c: Θ(n^3); 4.6: 1a: Θ(n log n); 7: Ω(n).

Preparing for week 6

Please do the following in preparation for week 6:

• Read chapter 5;
• Review chapters 1-4 (except 4.5) before Monday's review exercises;
• Attempt these problems before the tute: 4.6: 1, 7, 8 (or first edition: 1, 8, 9); 5.1: 6, 9; 5.3: 1, 5; 5.4: 1, 4; 5.5: 1, 3; 5.6: 7;
• NB there's no special lab exercises in week 6, please use this time to work on your projects or finish previous lab exercises.

Graphs are everywhere

As we saw in today's lecture, graphs show up in some surprising places. Here's pictures for just four of the examples we discussed (click the image to enlarge). Can you find others?

Power Distribution Network	Sexual Network
Supply Chain	Web Graph

Feedback on data structure design

The first part of project 1 was generally well done, with a median mark of 2.5/3. Common problems were: insufficient information about game state; missing size for an array; missing functions (e.g. for detecting a win); not discussing a function's input or return values; missing explanations; wrapped comment lines. Please collect your marked work from the helpdesk on level 1.

A brute-force opponent for project 1

The files for a brute-force opponent for project 1 are now posted on the handouts page. To incorporate this code you'll need to add brute.h and brute.c to your Makefile, and modify your version of game.c.

Who do you know, after all?

What on earth is this? Some simple computer science made it into the world's most famous journal (5,5). [Yes, its a small world after all. Rae Min's post correctly identified this as the small world phenomenon. David Coles followed up with a reference to the original 3-page article in Nature (read it here) and a more authoritative (?) source (ABC's Dr Karl). We'll look at such structures more closely in lectures this week.]

Google scholarship for female students

A message from Google: As part of Google's ongoing commitment to encourage women to excel in computing and technology, we are pleased to announce the 2006 Google Australia Anita Borg Scholarship. This is a $A5k scholarship for 2007 (deadline 15/9).

Answers to tutorial exercises from chapter 2

2.1: 3: yes; 7a: 8; 7b: 10; 9a: same; 9c: same; 9e: same. 2.2: 1a: Θ(n); 1b: Θ(1); 1c: Θ(n); 3a: Θ(n^20); 3b: Θ(n); 3c: Θ(n^2 log n); 3d: Θ(3^n); 3e: Θ(log n); 7a: true; 7b: true; 7c: true; 7d: false; 9a: Θ(n log n); 9b: Θ(n). 2.3: 1b: 2046; 1d: (n^2+3n-4)/2; 1f: (3^(n+2)-9)/2; 2a: Θ(n^5); 2c: Θ(n2^n); 4a: Σ(i=1..n)i^2; 4b: multiplication; 4c: n; 4d: Θ(2^b); 4e: Θ(1). 2.4: 1b: 4.3^(n-1); 1d: 2n-1; 4a: Q(n) = n^2; 4b: M(n)=n-1; 4c: C(n)=3(n-1) [NB 2(n-1) also ok)].

Mystery data

This is part of an infinite quarter-plane of ones and zeros, visualised as a raster image. How was it created? What is the special significance of the middle vertical column of ones and zeros? [Sam Owen pointed out that this data is generated by a cellular automaton, and that the middle column can be used as a pseudorandom number generator.]

Preparing for week 5

Please do the following in preparation for week 5:

• Read chapter 4
• Attempt these problems before the tute: 3.2: 5; 3.3: 3; 3.4: 1; 4.1: 1,5,7; 4.2: 1,3,10.
• Read the week 5 lab notes before the lab (download from the handouts page).

New consultation hours

I'm offering more times when you can drop by my office to talk about 253. Please see the "253 Consultation" times in the sidebar calendar. You're also welcome to make an appointment to see Duane or me, or visit the Second Year Centre.

Out of their Minds

In today's lecture I handed out an interesting chapter about Robert Tarjan, from this book about the lives and discoveries of great computer scientists. The chapter talks about Tarjan's research on designing data structures, a process we have been going through with our first project. Our approach to the formal analysis of algorithms also owes a lot to Tarjan. If you missed out on a copy of this handout you can collect it (and others) from the CSSE Helpdesk on Level 1.

Preparing for week 4

Please do the following in preparation for week 4:

• Finish chapter 2, and read all of chapter 3 (that's right; find a nice quiet spot to curl up with your textbook!)
• Attempt these problems before the tute: 2.3: 1 (b,d,f); 2 (a,c); 4; 2.4: 1 (b,d); 4;
• Read the week 4 lab notes before the lab (download from the handouts page).

By the way, have you noticed that this textbook, tute, and lab material will be really easy to examine?

Mystery data structure

What data structure is depicted here? Who invented it? Can you find the full picture? Please respond on the discussion list. [Wallace Stark correctly identified this as a splay tree, invented by Daniel Sleator and Robert Tarjan; he found this full picture and demo.]

Q/A Session today

The first of our question/answer sessions will happen at noon today in ICT Theatre 1. Please come along with any questions you have about the subject.

Second mystery algorithm solved

The second mystery algorithm was solved by David Coles. Another solution was presented by James Laird. The application of the algorithm is tone generation in mobile devices. David found a nice summary of methods for generating sine waves. Another method for solving this can be found in Appendix B of the textbook, in the section on linear second-order recurrences. Thanks to Michael Covington for this interesting puzzle.

New student representatives

Welcome to our student reps, Bhawika <bbawa> and Wallace <wjstark>. Please contact them if you have any feedback or concerns about this subject. Special thanks to David and Steve for being great sports with our brute force selection algorithm!

Would you like to be a student representative?

This week we need to find two student representatives for this subject. Student reps get feedback from fellow-students, attend occasional meetings with the 253 staff, and attend two Student-Staff Liaison Committee meetings (1pm, 15/8; 5:30pm one day later in semester). Student reps get: nice food at the meetings, knowledge about how the department works, experience in representing others, and a letter to certify that they have done this work (on request). Please think about whether you would like to serve as a student representative.

Mystery algorithm

Congratulations to James Laird for solving our mystery algorithm. His solution was in two parts [1,2]. (Here is a full discussion of the Jordan Curve Theorem for Polygons, on which this algorithm is based.) Please check the discussion list for the next mystery algorithm.

Please volunteer to help with Open Day

Volunteers are needed to assist the CSSE department with various activities at Open Day, Sunday the 20th of August. There are a wide variety of jobs available, and all volunteers receive a free T-shirt, lunch, a certificate of appreciation from the Department, and an extra-curricular activity to put on their CV. For more information, and to sign up for jobs, attend the Information Session, hosted by CSSE, MUCSA & CSSEPG: 1:30-2:15pm, Thursday 10th August, ICT Theatre 3 (level 2 near lifts).

Preparing for week 3

The work is coming thick and fast now, don't fall behind! Here's what you need to do to prepare for week 3:

• Read sections 2.1 and 2.2 in the textbook;
• Attempt the following tutorial exercises: 2.1: 1(a-c), 3, 7, 9(a,c,e); 2.2: 1, 3, 7, 9, and decide which ones you would like help with;
• Read the project specification and think about how you are going to represent game state; post any questions to the discussion list or ask them in your tutorial;
• Read the week 3 lab notes before the lab.

Animated sorting

Thanks to all the volunteers in yesterday's class who helped animate our sorting algorithms! Here is a collection of online sort animations, including selection sort and insertion sort. If you find other good algorithm animation sites please post them to the discussion list.

Project 1 released today

The first project will be to implement some data structures and algorithms for a game.  The specification will be distributed in today's lecture. It can be downloaded from the handouts page.