Weekly Schedule, Semester 2, 2001

Information about the content/format can be found here .

- Tuesday: Graph algorithms (breadth-first search, shortest path, topological sorting), skipped p394-397
- Thursday: P vs NP, NP completeness

- Q.64
- Q.81
- Q.83 (if time permits)

- Implement Breadth-first search algorithm

- Tuesday: Hashing, String searching (matching), skipped lecture notes p314-347, this material won't be part of the final exam
- Thursday: Knuth-Morris-Pratt algorithm, Graph algorithms (depth-first, breadth-first), skipped p358-361

- Q.60
- Q.61
- Q.63

- Work on the project
- Implement a C code to do BST insertion & deletion (if you feel like it).

- Tuesday: (a,b) Trees, Red-Black Trees, ..
- Thursday: Hashing

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

- Tuesday: External sorting, searching, binary trees, ..
- Thursday: Balanced trees, Tree rotations, ...

** Corrections/Clarifications : **

- Q.51
- Q.52
- Q.54
- Q.55

- Implement Merge sort algorithm
- Demo on Heap sort algorithm using the AIA tool.

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.

- Tuesday: continue with Radixsort, Priority Queues, start with Heapsort
- Thursday: finish up Heapsort, Mergesort
Note that the condition, each child is less or equal than its parent, does not imply the tree is complete. However, our algorithm operating on heaps, downheap and upheap, ensure the invariant that the heap (seen as a tree) is complete.

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

- Q.49
- Q.50

- Q.48

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

- Tuesday: Quicksort review plus complexity analysis, iterative version, application (selecting k elements)
- Thursday: Radixsort (L->R), distribution counting
**Corrections :**selection sort (p 163) is instable, consider 0 1 7 7 2, the first 7 gets swapped with 2.

- Discussion on the midterm test question paper

- Implement Insertion sort, selection sort & shell sort in C
- Demo on Quick sort using AIA.

** Exam procedure **

- Tuesday: Mid-semester test. 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.
- Thursday: Tutorial lecture

- Q.46
- Q.47

- Q.42
- Anything outstanding from the previous weeks

- Tuesday: recurrences, selection/insertion sort, complexity
- Thursday: recurrences, complexity, shell-sort, quick-sort
**Corrections:** - There's a typo on p156. It should be c_1=1.
- Note that a sorting algorithm is stable iff it preserves the relative order of duplicate keys.
- Complexity analysis insertion sort:
Argh, there's again a slight mistake (
**in the material presented in the lecture, this material is not explictly covered in the lecture notes**). For key exchanges we have, k_n = k_{n-1} + n + 2 (worst case), k_n = k_{n-1} + 1 + 2 (best case) and k_n = k_{n-1} + n/2 + 2 (average case).

- Q.43
- Q.44
- Q.45

- Anything outstanding from previous weeks
- Q.42

- To submit your project use the command
**submit 253 1 proj1.c** - To verify your project use the command
**verify 253 1 proj1.c | more**

- Tuesday: Project 1, Complexity of Algorithms, Slide 146 - 156, Algorithm Analysis
- Thursday: More Examples, Recurrences, Sorting (Selection/Insertion Sort), Complexity Analysis, Slide 156 - 166
**Q:**when will our mid-semester test be? could we have it in week 7 instead of week 6 ... because a lot of us already have 2 mid semester tests in week 6... what will the mid semester be like and how can we have a look at previous mid semester tests?**A:**The 253 mid-semester test will be in week 6, see above.**Q:**Where can I find more about (solving) recurrences?**A:**The basic stuff is covered in the lecture notes and lecture. A good reference is `Introduction to Algorithms: A Creative Approach' by Udi Manber. I highly recommend this book if you'd like to more about algorithms. There's a general technique behind solving recurrences which is very similar to solving differential equations. This is clearyly beyond the scope of the lecture, and I have to refer you to some math books or simply search the web!**Q:**On the 253 web page you wrote: "Note how the '*' operation (e.g. *pointer) can be simulated by the array index operation (memory[pointer])." Does this mean that the pointer notation and the array notation are interchangeable?**A:**Yes, you can always mimic pointers via array indices. Assuming you treat the heap (ie memory space) as an array.**Q:**Do all of the lecture slides come from the prescribed textbook "Algorithms in C"? Some people have said that they find the lecture notes hard to understand and they'd rather read the textbook alone. Would this be ok?**A:**Yes, I strongly encourage you to read the text book. As I already mentioned the lecture notes give a brief summary of the key concepts. In addition to the lecture notes, I'm giving you additional material during the lecture. Often, I make this material available on the web-page. However, I also do expect that you're taking notes of during the lecture.

- Q.34
- Q.37
- Q.38
- Q.39 (if time permits)

- Q.31
- Q.40
- Q.41

- Tuesday: Trees, Slide 112 - 128
- Thursday: Trees, Slide 129 - 146
**Corrections:**The transformation of multi-way trees to binary trees as shown in class has some problems. Will correct this next Tuesday.Here's some additional material about asymptotic behaviour and complexity measures of functions.

- Versions are available in html , ps and pdf format
- Note that the presentation slighly differs from the lecture notes.

- Q.14
- Q.29
- Q.30

- Q.09
- Q.11
- Q.12
- Q.17
- Q.27 (if time permits)

- Tuesday: Data structures: Arrays and lists, Slide 84 - 95
Insertion in simple linked lists (slightly differs from the presentation in the lecture notes), implementations given in C and Haskell

Using arrays to implement lists. Note how the '*' operation (e.g. *pointer) can be simulated by the array index operation (memory[pointer]). An (sketch) implementation can be found here .

Destructive vs non-desctructive update. Observe that in the first implementation of insert (void insert(NodePtr *head, char value) we pass in the head-pointer of the list as a var-argument (i.e. we pass in not its value but its address). We could have circumenvent this by returning the 'updated' head pointer as a result value (i.e. we have that NodePtr insert(NodePtr head, char value)).

- Thursday: Data structures: Queues, stacks, ..., Slide 96 - 111
**Q:**p 109 (referring to the implementation on p 110,111). When is the queue full?**A:**(answered by widjaja) We know that the stack will grow upwards and it will continue to grow, with tail keeping record of where the most recent element is and head keeping record of the first element, until they hit MAX, in this case 100, in which it will go back to 0. The problem we are faced with is that we want to restrict the case of filling up the queue when it is full, which only happen when tail == head - 1, or the special case when head == 0 and tail == MAX the assumptions that i am making is that the stack is empty iff head == tail, as you stated in the lecture. so in order to prevent the filling up of more elements, we can just check the case that we have when the queue is full before we actually start running through the function put by putting conditional sentence checking if tail == head - 1 and the special case when ( head == 0 && tail == MAX ) I am not really sure about the implementation in C, it might look something like this after the addition of the checking part: put (int v) { if (( tail == (head - 1) ) || ( head == 0 && tail == MAX ) ) /* checking if the queue is full */ { fprintf (stderr, " QUEUE IS FULL!"); return; } /* or any other way to stop the function to fill up the queue */ else { queue[tail++] = v; /* else keep adding elements in queue */ if (tail > MAX) tail =0; } }

**Q:** p90, Lists
The C code appears to be incorrect. It attaches a new
node to list1 by eliminating the first node currently
in the list.
plist is a pointer to a pointer to the head of list1.
On the line,
p1->next=(*plist)->next;
The next node that p1 (the new node) points to is the
second node in list1 since (*plist)->next points to
the next node after the head of the list.
At the end, list1 points to p1 via *plist = p1.
What has happened to the first node? Is this code
correct?
Would this code work?
p1 = NEW(NODE);
p1->key = 'X';
p1->next = list1;
list1 = p1;
**A:** You're observations are correct.

- Q.13 (from the subject notes)
- Q.23 (from the subject notes)

- Q.05
- Q.08
- Q.10
- Q.15 (if time permits)
- Q.16 (if time permits)
### Week 1, 30 July-3 August

#### Lectures:

Note that assessment is different this semester.- Tuesday: Introduction, Problem solving, Recursive functions, Slides 1-16.
The coins program shown in class is incorrect (although the mathematical reasoning is correct). See here for the corrected version including some explanations. Note that I make use of some techniques not covered yet in lecture. Consider this simple as an example of the issues behind developing algorithms, proving the correct and implementing them in an actual language.

- Thursday: C, Programming style, Invariants,
Material covered in the lecture: Slides 17-19, 38-53, 71-75

Homework: up to Slide 83

Pre/Post-conditions, Invariants: This material won't be examinable. In case you're interested in this material(I consider this material as essential for each computer scientist) I recommend David Gries book `The Science of Programming'.

#### Tutorials:

enrol here#### Laboratories:

enrol here**There are specific Tutorials and Labs that have been opened. When you run labenrol and tuteenrol, you will be informed the list of tutes and labs that are scheduled to run. The list that you will see when labenrol and tuteenrol are run , are the only tutes and labs available this semester.****Martin Sulzmann Last modified: Thu Nov 1 11:46:30 EST 2001** - Tuesday: Introduction, Problem solving, Recursive functions, Slides 1-16.