Old announcements for COSC4101

For A3, Q4: You are allowed to reuse parts of the analysis done in class (don't copy them down, just refer to them). But naturally there are some parts that will be different. Among other things, you will have to define what your potential function is and show how much it changes when trees are cut into two pieces or joined together.
For A3, Q5: Remember that the graph you construct must satisfy the triangle inequality. If you can't solve the problem, you can earn partial credit if you prove that the approximation ratio is at least c, for some c > 4/3 (eg. prove the approximation ratio is bigger than 1.3982719), and the closer your c is to 2, the better your mark will be.
Test 2 will be on November 18. It will cover material up to the end of the November 11 lecture. You may bring one handwritten 8.5x11 inch sheet of notes (written on both sides) into the test.
Course evaluations will be done on November 20.
For A2, Q5, assume you have a random number generator so that picking a random number can be done in one step.
Extension: A2 is now due on Friday, Nov 8. Hand it in at my office between 2 and 3 pm.
In A2, Q5(c), remember that m=n for this part. For the last part of the question, you can change th 6 to a 7. (You can do it with 6 but it's a tiny bit easier with 7).
Every few years, the computer science undergraduate programme is reviewed by external consultants, who then suggest ways we can improve the programme. As part of this process, the reviewers will be meeting with students on November 11 at noon and at 6p.m. Both meetings will have free pizza and pop and will be held in the foyer outside the PRISM lab. As senior undergrads, I'm sure you could give lots of helpful information to the reviewers. I encourage you to attend one of the meetings and help us make the programme better.
For assignment 2, Q3, you should give some indication of why your algorithm is correct. Include pre- and post-conditions. If you use a loop, write a loop invariant. You don't have to prove the loop invariant holds if the proof is really easy. (However, if you do something unusual in your algorithm and it's not obvious why it works, then you should explain it in more detail to make the TA's life easier.)
There will be an information day for students interested in going to grad school in the mathematical sciences (math, stats, theoretical CS) on November 2 at the Fields Institute (located at 222 College Street downtown). See this link for more info.
York's ACM programming contest is on Oct 25. See this link if you want to participate. There are lots of reasons you should participate: you'll learn lots, it's fun, it will look good on your resume, you can win stuff, and you can indulge your competitive spirit.
For question 4(c) on assignment 1, note that a tree containing no nodes is a legal 2-3-4 tree. Perhaps the clearest way to answer question (c) is to describe how to construct the trees T_0', ..., T_m' and the keys k_1', ..., k_m' and the corresponding trees and keys for S''.
For clarity, change the n in Question 3(b) of Assignment 1 to an m.
There's a tiny typo in 17.3-7 (Q2 on Assignment 1): ceiling(S/2) should be ceiling(|S|/2). As mentioned in class, you can assume elements inserted are all distinct.
For assignment 1, 18-2: 2-3-4 trees are just B-trees with t=2 (see page 439). So you are still using a 2-3-4 data structure as presented in class, just writing new algorithms (join, split) and (in part (a)) making small modifications to the algorithms presented in class.
For assignment 1, 17.2-3: You should measure the complexity of your algorithm in terms of the basic bit operations: every time you look at a bit or change a bit, that is a step.
I changed my office hours because some students could not attend the old ones. The new hours (posted above) start the week of Sep 30 (so there will not be one on Sep 27).
Test 1 will be on October 16.
Participate in the ACM programming contest! See this link for details.
The lectures have been moved to room 230 of Bethune College.