|
Class: we covered the slides (lec1, and lec1-4), giving a basic introduction to the course.
At the end I did the analysis of POWER-REM3 on the board. First did a count of the algorithm to set up the recurrence as
T(1) = 1
T(n) = 2 + T(n/2), if n>1, n even
T(n) = 4 + T((n-1)/2), if n>1, n odd.
In trying to analyse T(n), I initially made the mistake of trying to show it was monotone increasing with n, before abandoning that idea (it is NOT monotone, as Stanislav pointed out afterwards - try 7 and 8).
However it *is* easy to show that T(n) <= T'(n), when we
define T'(n) to have +4 as its constant for both even and
odd cases of n>1. Also T'(n) is monotone. So for any n,
we can use the fact that T'(n) <= T'(N) where N is the closest
power of 2 satisfying n <= N; then a direct substitution shows
T'(n) <= T'(N) = 4*lg(N)+1 < 4*lg(2n)+1,
then via T(n) <= T'(n) we get T(n) <= 4*lg(2n)+1, and done.
We can similarly show a Omega(lg(n)) lower bound.
Class: Main issue is that I was late to class; we didn't complete the slides.
We covered the early slides in the set (lec2, and lec2-4), revising Asymptotic notation, Insertion sort and Mergesort.
We also tried to prove the upper bound T(n) <= 5nlg(n) + n for MergeSort BY FIRST PRINCIPLES (induction; no Master theorem).
However I made a couple of mistakes:
The above was all we considered in class.
The set of slides ends with a group of 6 slides on the example recurrence. The proof of the upper and lower bound for this recurrence was assigned as personal reading. However there is an easier way "first principles" way to prove Θ(n*n lg(n)) for this particular recurrence and we did this approach as Q3 of the week 3 tutorial sheet.
Assigned reading: finish lecture (read slide 13 onwards), also
[CLRS, Chapter 2.3 and pp.28-54 of Chapter 3].
Assigned questions [CLRS, Problems 3-1, 3-2 on pages 57, 58].
Class: We revised the Master Theorem. Then we demonstrated its effectiveness by covering Strassen's algorithm for fast matrix multiplication. We spent about 3 minutes in interactive mode - the class broke into 3 groups, and each group checked one of the C11, C21, C22 terms in Strassen's algorithm.
I had one mistake on the slides I handed out - somehow I wrote the wrong URL for the course webpage (copied from a lecture for a different course, and forgot to change the extension). This has been corrected on the slides online.
Assigned Reading [CLRS, Section 4.3 and Section 28.2].Class: We covered the definition of the DFT, and the Fast Fourier Transform (FFT) algorithm for computing the DFT. We used the "wheel" representation for n-th roots of unity, and in particular showed how the FFT recurrence means that our recursive calls are for n/2-th roots.
We did not cover all of the slides originally destined for today (did not get to the formal presentation of the Algorithm, or the analysis of runtime). We will continue through slides4&5 on Friday Friday's lecture.
Assigned reading: "Notes on FFT" FFT.pdf (handed-out), also lecture slides 4-5.Class: We started by continuing with the leftover slides for lecture 4, proving that the FFT algorithm computes the DFT in Θ(n lg(n)) time.
Then we covered the material on lecture slides 5 - the Inverse DFT, and how it can be set up as a slight modification of the standard DFT. The main thing to take away for this lecture is that the slides presenting (and verifying) the van-der-Monte Matrix which computes the Inverse are background, proof-related but not an efficient Algorithm for Inverse DFT. The efficient (Θ(nlg(n))) algorithm for Inverse DFT is the algorithm appearing near the end - where we just apply straight DFT and at the very end divide-by-n and do some flipping of the vector.
We did the proof of correctness of the "cute" (and efficient) Algorithm for Inverse DFT on the board.
We also showed how to use FFT to come up with a Θ(nlg(n)) time algorithm for multiplying polynomials (students are asked to read the "notes on FFT" to get a better understanding).
Assigned reading: the lecture notes on FFT FFT.pdf, also [CLRS (edition 2 or 3), Section 30.2].
Class:
We went through all of the slides for this topic.
The version of QuickSort in the lecture is different to the one
used in Inf2B. For that reason, I was asked to prove correctness.
I did this on the board, but abandoned it towards the end,
because I was not sure I had the indices correct in my LI
(loop invariant) ... and did not want to delay things (can be
hard to get correctness wrt i, i-1 etc right on the fly).
Writing after the lecture ... the correct loop invariant is:
(LI) Before entering the loop for a particular j (j = p, ..., r)
(a) i < j
(b) A[p ... i] contains items strictly <= pivot,
(c) A[i+1... j-1] contains items strictly > pivot
It is not too hard to show this LI - just show Base Case, when i=p-1
and j is p. Then show that when the LI holds, still holds after an
extra loop.
In setting this up, we imagine that we consider entering the loop
with r - so then the termination of the loop is characterized by
(a), (b), (c) and j= r. Then we can see that by (b) and (c) the
location of the first >pivot value (if one exists) is in i+1 (which
is <= r by (a)), so the Exchange on line 7 puts "pivot" in the right
place.
The later part of the lecture was the average-case analysis of QuickSort on slides 11-13, this is the most interesting bit. We did this on the BOARD, but the slide have all the details there.
Class: We analysed the problem of Comparison-Based sorting via the use of the Decision Tree model for an algorithm. We proved the Ω(nlg(n)) information-theory lower bound for Comparison-based sorting - we did this "worst-case" proof quite quickly.
The remainder of the lecture was devoted to the lower bound for Average-Case number of comparisons for any Comparison-based Algorithm. This is also Ω(nlg(n)) - but to show this, it is necessary to show that the average-leaf-depth in any binary tree with L leaves, is at least Ω(lg(L)). So the second half of the lecture was on the BOARD, getting the proofs of Theorems 11 and 12. I have much later (9th Dec) re-written and scanned-in the proofs (with pictures) of these theorems. These "Board Notes" are here.
Assigned reading: the lecture slides, (12 dec) the BOARD NOTESClass: We went through these slides in class. First discussed in detail the algorithm for counting sort - there was a question about whether it could be changed to make the loop on lines 9.-12 proceed in increasing order of i ... it can, but the changes necessary for this make the C[j] values less consistent-as-a-whole (across all j = 1,... ,m).
Rest of class was showing the proof of Theorem 2 about Radix Sort.
Assigned reading: [CLRS, sections 8.2, 8.3]Class: Started off discussing Fibonacci and how the recursion table for F(n) grows so fast. If I remember correctly (not sure now), I did the sketch on the BOARD to show that F(n) >= (3/2)^n for Fibonacci. With the help of someone's iPhone/calculator, we verified that the base cases are n=8 (then F(8)=21), n=9 (F(9) = 34). We need n this big before F(n) >= (3/2)^n becomes true.
After that we proceeded to the real work - the problem of matrix-chain multiplication. We saw 4 approaches (slides 9 and 10) which either give an INCORRECT answer or are TOO SLOW. For APPROACH 1 (correct but exponential time), the number of parenthesizations would be Ω(3^n) ... this is not shown in the notes but was done as a tutorial question for week 7. We did show on the BOARD that the recursive algorithm, using the correct recurrence for m[i,j] (APPROACH 4) is Ω(2^n).
Finally we started off on the remaining slides about the O(n^3) dynamic programming algorithm for Matrix-chain multiplication - this uses the recurrence for APPROACH 4, but by computing bottom-up, it manages to efficiently (as well as correctly) solve the problem. We did not finish all of this.
Here (added 13th Dec) are some notes on DP (from a previous session).
Assigned reading: [CLRS, sections 8.2, 8.3]class: I was quite late to class - I went to the wrong lecture theatre first of all, probably as a consequence of omitting the usual Tuesday lecture this week. The very first thing I did was return to Dynamic Programming and the Matrix-Chain Multiplication problem, re-introduce the problem, and finish those slides.
After that I started MSTs, going through slides lec10.11.12 (or lec10.11.12-4). I started to go through the slides on Prim's algorithm and its implementation. I proved Prim's algorithm in detail on the BOARD, but did not get a lot further than this. Actually I am not sure I even got as far as proving it (writing this in Dec). Main point is that for Prim's algorithm (being a greedy algorithm), it is the proof of correctness which is important - the algorithm itself is very simple.
Assigned reading: [CLRS, Chapter 23]class: 2nd lecture on Minimum Spanning Trees (slides here, and here-4). Started on the implementation of Prim's Algorithm via priority Queue implementations. Discussed the subtleties of the analysis - making the Key Point that the analysis of the running time for the loop on lines 7.-11. (on slide 14) must not be structured according to the nested loop at lines 9.-10., otherwise our Upper Bound will be overly conservative. The Key Observation, which involves splitting the work done according to each edge of the graph is on slide 15.(NB) Everything is added up on slide 16.
As I'm editing this log on 9th December, I don't remember perfectly, but I think this is about as far as I got. I also released Coursework 2 today.
Assigned reading: [CLRS, Chapter 23]class: 3rd lecture on Minimum Spanning Trees. Kruskal's algorithm. We were looking at slides 22-26 of the MST set (here, and here-4) and also writing quite a bit on the BOARD.
Lecture mainly was devoted to the proof of correctness of Kruskal's algorithm. I first discussed the easier parts of the proof, steps 1 and 2. I spent too long on step 2 and really what is written in the slides is fine for that. After that I did the proof of Step 3 (the main part of the proof) on the BOARD. This proof does not appear in the slides. I have re-drawn proof and pictures and scanned them in now (9th Dec) - here is the BOARD NOTE.
Did not really get onto implementations of the Disjoint Sets for Kruskal. Running late with MSTs.
Assigned reading: [CLRS, Chapter 23]class: I had ran over on the topic of Kruskal's Algorithm, so most of today's lecture was dedicated to finishing it off. Basically we were going through slides 27 onwards from the set lecture10.11.12 (here or here-4) - data structures for Disjoint Sets (Kruskal).
This topic is quite different to the earlier stuff on MSTs because it focuses on various data structures for implementing Kruskal. They are quite simple data structures - also we approach the analysis in terms of an amortized analysis where we are interested in overall cost of a bunch of operations.
We did some details of the Amortized cost of LinkedLists
with WeightedUnion. We also showed on in BOARD that for the Forest
implementation of Disjoint Sets with UnionByRank, the height of
any tree in the Forest is bounded above by
lg(|number of nodes of tree|). This *gives* the amortized
bound of O(m lg(n)) for a collection of operations.
NB:For the Forest Implementation of Disjoint Sets,
remember the trees in the forest Data Structure are convenient
representations of the Disjoint Sets - they won't necessarily
match the shape of the trees in the Kruskal forest.
We introduced the problem of Network Flow, partly in relation to the example Network. After defining Network Flow, we discussed the example flow on slide 6 together, and found a way to send an extra 7 along the path (s, c, b, t). This allowed me to chat a bit about the concept of residual network in advance of meeting it.
Next I introduced the Ford-Fulkerson algorithm, and discussed the fact that (as with most "greedy" algorithms) the Algorithm itself is quite simple, but the work really lies in getting the proof of correctness right. With this motivation :-), we ploughed through slides 9 to 15, where there are lots of small lemmas and observations ... which will later be used in the proof of MaxFlow-MinCut Theorem.
Assigned reading: [CLRS, Chapter 23]class: I did a quick skate through the early slides on this topic, then started on slide 16, where finally, after all our intuitive discussions of Residual Flow, we define the Residual Network (which is so important for the Ford-Fulkerson algorithm, and its proof). We went through Lemma 6, verifying that a flow in the residual network N(f) when added to f, is overall a flow in the original network N. Then we defined an augmenting path, which can be found using Breadth-first search.
After these basic details of Ford-Fulkerson, we moved onto the concept of a cut, and proved some basic Lemmas. Finally we come to the "piece de resistance", the MaxFlow MinCut theorem. This is very important, both as an interesting graph-theoretic fact, and in its application to prove correctness of Ford-Fulkerson. I did the proof on the board - though most details are in the slides. note: students are usually able to re-construct the easier half of the MaxFlow MinCut proof (that the max flow is bounded *above* by the min cut). However, they are often unable to re-create the proof that the value of the Max Flow is AS BIG AS the MinCut - ie, the details the proof of Theorem 13. This is important (though I'm not writing that as an 'exam hint'), and you should make sure you can understand it.
Assigned reading: [CLRS, Chapter 23]Working on the first half of lecture15.16 (here, here-4).
Went through the definitions of the simple "point level" questions of "clockwise or anti-clockwise?" "turn left, right or go straight on?" and "do the segments intersect?".
Main things to take away from the lecture are the idea of shifting the base point to origin (0,0) and that it is tricky to remember the correspondence of left or right with negative or positive cross product. If you ever need to work out this in an exam, try it for (0, 0), (4,0) and the new point (2,2). The computation is simple with these numbers, and it is easy to check on a page that (2,2) is left of the directed segment (0,0)->(4,0).
In a previous year, one student wanted justification of the "cross-product role" in determining clockwise versus counter-clockwise for a pair of vectors - here are the notes(in txt) and a picture(in .pdf) if anyone is interested.
Assigned reading: Basic Computational Geometry in [CLRS]class: Working on the second half of lecture15.16 (here, here-4) for convex hull.
We first did a quick revision of the early slides (reminding what was done on Friday), then covered Graham's Scan algorithm for Convex Hull, plus the proof of its running time and correctness.
I have revised the slides a small amount since I gave lectures 15 and 16.
We are finished lectures now. See you for the revision lecture in April.
|
Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh |
