Weekly Schedule, Semester 2, 2001


Week 12, 29 - 2 November

Final Exam

Exam date : Wed 28 Nov

Information about the content/format can be found here .

Project 2

Information about your marks and sample solutions will be made available by the middle of next week.

Lectures:

Tutorials:

Laboratories:

Week 11, 22 - 26 October

Lectures:

Tutorials:

Laboratories:

Week 10, 15 - 19 October

Project 2 :

Submit is open. Try submitting your proj2.c using the command submit 253 2 proj2.c. Do not forget to verify your submission. Use the command verify 253 2 | more . Submit your file as often as you wish. There were some typos in the proj2.c file. Make sure that you've downloaded the latest version.

Lectures:

Week 9, 8 - 12 October

Project 2:

The first project is out, a description can be found here . FAQ can be found here . You'll also need to download the following file proj2.c . Please make sure that you follow the instructions in the project description.

Note that you won't be able to submit your project yet.

Lectures:

Corrections/Clarifications :

  • p259: Both successful and unsuccessful search needs O(log(n+1)) comparisons. Best case for successful is O(1).
  • p264: There must be two pointers from each leaf node to the z node.
  • p267: line 6 from the top, replace `x < val' by `x < key'

    Tutorials:

    Laboratories:


    Non - teaching period Monday 24 September - Sunday 7 October

    If you feel like doing some readings/preparations in light of the upcoming project and exam, I suggest to go through the lecture notes, text book and lab and tute questions again.

    If you have already done all this and you're interested in some fun stuff, I highly recommend to take a look at `Introduction to Algorithms: A Creative Approach' by Udi Manber. The focus is not so much on some particular C-hacks. He introduces a more general approach how to develop algorithms. Recommended to students you want to know more than the average.


    Week 8, 17 - 21 September

    Student-staff meeting

    There will be a student-staff meeting on Thursday. Now it's the time to contact your 253 reps (see front-page) to give them some feed-back.

    Lectures :

    Questions:

    (refering to some previous lectures)

    Q: p176, Summary What is the complexity of shell sort based on the Knuth's sequence (1,4,13,40...)? Is it O(n^1.25)? Is the complexity of a shell sort implementation dependent on the sequence adopted?
    A: As it says in the lecture notes, it's a conjecture. There's not much known about the complexity behaviour of shell-sort. I have to refer you to the text book.

    Q: p175, Shell sort C code The code here fails to address the element in a[0]. Does this mean that this element is a sentinel?? If it is, it is not even used anywhere in the program. The while loop uses the condition j > h to eliminate the use of this sentinel. Hence, why has the code skipped the element, a[0]?
    A: I can't give you a definite answer here. I guess it's a bug. Note that if you don't use a[0] the algorithm presented should still work. I must say I don't like this version of shell-sort. Have a look at the text book, there the presentation/code is much clearer.

    Q: Just looking over some of the notes that you wrote in lecture 9 or 10...I am very confused about how you obtained the recurrence relationships for each case.

    1) Comparison, Worst case You wrote: c_1 = 1 c_n = c_(n-1) + n I agree with c_n, but look at c_1. If you have a look at the code on p166 of the lecture notes, you will notice that the for loop to initiate the program requires that the number of elements in the array a must be at least 2 (not including the sentinel). Hence, your initial condition should be c_2 = 1. I found that it doesn't affect the complexity in that it is still O(n^2), but I just want to check for correctness!!!

    This also applies to the key exchanges. You wrote: k_1 = 1 k_n = k_(n-1) + n + 2 Again I agree with k_n, but k_1 = 1 is incorrect by the reasons discussed above. The for loop fails since there is only 1 element in the array, as denoted by n. Just checking n is the number of elements in the array a, not including the sentinel??? So, in this case, it should k_2 = 1.
    A: Your observations are correct (guess I started counting with 0!), as you've noticed, both recurrences yield the same complexity result (meaning complexity class).

    Q: Best case, Key exchanges You made an alteration on the web page that: k_n = k_(n-1) + 1 + 2 Looking at the code on p166, 'k_(n-1)' and '+ 2' is correct, but the additional '+ 1' should not be there. In the best case, the array is already sorted, so the while loop should fail on each iteration, which also means that the key exchange in the while loop is not processed. That means k_n = k_(n-1) + 2.
    A: +1 is correct if we also count assignment among loop variables (I've mentioned this in the lecture but this is not mentioned in the lecture notes). If we only count for `key' exchanges, then k_n = k_(n-1) + 2 is correct. Again, both recurrences yield to the same complexity result.

    Tutorials:

    Laboratories:

    Week 7, 10 - 14 September

    Project 1 marks available here

    Please collect the hardcopy of your project 1 from the Student Services between 12noon-1.00pm anyday (SEE CS Building). If you have any queries with regard to project 1 , contact the Staff Tutor Antonette Mendoza on Monday (17.09.01) between 4.30pm - 5.30pm.

    Lectures :

    Tutorials:

    Laboratories:

    Week 6, 3 - 7 September

    Project 1

    Samples solutions for Project 1 are made available . Sample solution1 here and Sample solution2 here

    Mid-semester test

    The mid-semester test takes place on Tuesday 4th September 12.05pm in the usual lecture theatre . Please be punctual, bring along your student ID. If there's a good reason why you can't attend the mid-semester test (you'll need to provide evidence such as medical certificates etc) contact the Lecturer.


    Exam procedure

    - Around 12.05pm you can enter the lecture theatre.
    - Take any seat you like.
    - Leave personal belongings such as coats, back-packs at the front of the lecture theatre.
    - Reading time is 5 minutes, exam duration is 30 minutes.
    - Note that no materials are authorized.
    - Note that any cheating attempt immediately results to zero marks.

    Lectures:

    Tutorials:

    Laboratories:

    Week 5, 27 - 31 August

    Lectures:

    Tutorials:

    Laboratories:

    Week 4, 20 - 24 August

    Project 1:

    The first project is out, a description can be found here .

    Lectures:

    Tutorials:

    Laboratories:

    Week 3, 13 - 17 August

    Lectures:

    Tutorials:

    Laboratories:

    Week 2, 6 - 10 August

    Lectures:

    Lecture notes:

    Tutorials:

    Laboratories: