Information about the content/format can be found here .
Note that you won't be able to submit your project yet.
Corrections/Clarifications :
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.
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.
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.
Corrections : selection sort (p 163) is instable, consider 0 1 7 7 2, the first 7 gets swapped with 2.
Exam procedure
Corrections:
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.
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.
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)).
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.
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.
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'.
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