Administrative requests concerning the mailing list itself, such as add/delete/address change requests, should be addressed to cse521-request@cs. There is no need for you to send an initial "subscribe" request to cse521-request. Everyone registered in the course is automatically on the initial mailing list.
To: cse521@geoduck Subject: testing the mail log Date: Wed, 26 Mar 1997 00:31:45 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu>
To: cse521@geoduck Subject: mailing list, office hour, and course outline Date: Mon, 31 Mar 1997 22:07:19 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> Please disregard this second mailing. I'm trying to see if the logging of mail on the course web is now fixed. ------- Forwarded Message Date: Mon, 31 Mar 1997 12:15:47 -0800 From: Martin Tompa <tompa@geoduck.cs.washington.edu> To: cse521@geoduck Subject: mailing list, office hour, and course outline 1. The mailing list cse521@cs is now set up, based on today's signup sheet. 2. I neglected to mention my office hour policy for this quarter. Because this is a grad course, and not a very large one, my preference would be to make every hour my office hour. My door's open, and you're welcome to either drop in, or make an appointment if you want to be sure to catch me. But I want to do this to encourage interaction rather than discourage it, and if you find it's not working, let me know. 3. Please send me mail before Wednesday's lecture answering the following questions about the handout titled "Course and Text Outline": a. Of the algorithms in Section 1 ("Chapters to read on your own"), which ones have you not seen previously? b. Of your answers to question (a), which ones are you disappointed not to be seeing in 521? c. Of the algorithms in Section 2("Chapters to be covered in lecture"), which ones have you already seen previously? ------- End of Forwarded Message
To: cse521@geoduck Subject: course outline Date: Sun, 06 Apr 1997 18:07:01 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> I received only 11 responses to the following survey. For the rest of you, unless I hear right away, I'll assume that the outline I've proposed is just peachy. 10 of the 11 respondents said they don't know much about chapter 22, so I may well add that to this quarter, and delete some of the material that many of them said they've seen. In order to do the latter, it would help me if I'd get some more responses. ------- Forwarded Message Date: Mon, 31 Mar 1997 12:15:47 -0800 From: Martin Tompa <tompa@geoduck.cs.washington.edu> To: cse521@geoduck Subject: mailing list, office hour, and course outline ... 3. Please send me mail before Wednesday's lecture answering the following questions about the handout titled "Course and Text Outline": a. Of the algorithms in Section 1 ("Chapters to read on your own"), which ones have you not seen previously? b. Of your answers to question (a), which ones are you disappointed not to be seeing in 521? c. Of the algorithms in Section 2("Chapters to be covered in lecture"), which ones have you already seen previously? ------- End of Forwarded Message
To: cse521@geoduck Subject: collaboration policy Date: Wed, 09 Apr 1997 11:48:26 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Stefan pointed out that I never said what my policy is on homework collaboration. It's the usual Gilligan's Island rule: I encourage you to brainstorm together and discuss approaches to the problems, but I want to make sure that you fully understand the solutions you're handing in. So take away nothing written from the discussion, vegetate in front of the TV for an hour, and then write down your solution on your own. If you can do that, then you've understood what you're writing.
To: cse521@geoduck Subject: HW1, #1a Date: Wed, 09 Apr 1997 11:54:17 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> A few students have noticed that the recurrence you get has different solutions, depending on whether m_c > c^2 or not. You can assume for this problem that this inequality is true. (It would be astonishing if it wasn't true.)
To: cse521@geoduck Subject: miniproject language Date: Wed, 16 Apr 1997 13:17:51 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> A few people asked questions today about the choice of programming language for the miniproject. Firstly, the only other time I've assigned this project was a bit over 3 years ago, and there was a suggestion that C++ (and templates in particular) have stabilized enough in the past 3 years that it may no longer be a problem. So my information may be out of date. It was also asked what other languages teams chose that time. There was a team using each of Scheme, Ada, Modula-3, and Miranda. Each of these teams expressed pleasure with their choices. The other 7 teams chose C++, and none of them expressed anything like pleasure. As with other assignments, it's fine for you to brainstorm in groups larger than 2, as long as distinct teams aren't sharing details (such as code). Feel free to use this mailing list to look for partners, look for brainstorming groups, or anything else.
Date: Wed, 16 Apr 1997 14:16:30 -0700 From: Jared Saia <saia@cs.washington.edu> To: cse521@cs Subject: miniproject hi. have any C++ hackers been able to get STL working with g++(or any other compiler) here? it seems like it would be helpful for this project - there is an extension to it NTL which defines matrices among other nice numeric types. -j
Sender: gjb@methow.cs.washington.edu To: Jared Saia <saia@cs.washington.edu> Cc: cse521@cs Subject: Re: miniproject References: <199704162116.OAA24646@june.cs.washington.edu> From: Greg Badros <gjb@cs.washington.edu> Date: 16 Apr 1997 14:55:45 -0700 Lines: 24 Jared Saia <saia@cs.washington.edu> writes: > hi. have any C++ hackers been able to get STL working with g++(or any > other compiler) here? it seems like it would be helpful for this > project - there is an extension to it NTL which defines matrices among > other nice numeric types. Hmmm.. it works by default for me (i.e. no guru-dom needed). g++ (since at least 2.7.2, maybe earlier), has this stuff included as the norm.... see the headers in /usr/include/g++ (on linux 2.0.2x sushi boxes). Incidentally, I highly recommend Musser & Saini's book-- see http://www.aw.com/cp/musser-saini.html There's source code for the examples from the book off there. Just beware not all work (due to limitations/differences in g++ templates), and their examples generally use the older scoping rules for variables declared in "for" loops, so you'll get warnings unless you tell g++ to use old scoping rules or update the code. Greg
X-Authentication-Warning: tako.cs.washington.edu: jbuhler owned process doing -bs Date: Wed, 16 Apr 1997 16:47:39 -0700 (PDT) From: Jeremy Buhler <jbuhler@cs.washington.edu> To: cse521@cs.washington.edu Subject: Mini-project - calling all ML hackers X-NSA: tritium Oklahoma City nerve agent militia encryption I'd like to use Standard ML for the mini-project. Are there any ML hackers out there who are of like mind and need a partner? Jeremy
To: cse521@geoduck Subject: miniproject groups Date: Sun, 20 Apr 1997 15:38:38 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Please let me know if you don't yet have a miniproject team. I'll act as a clearinghouse to help make remaining matches.
To: cse521@geoduck Subject: next 521 topics Date: Sun, 20 Apr 1997 16:02:55 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> I've struggled a bit to figure out where we should go next in 521, based on your responses to what material you've seen previously. All but one of the respondents hadn't seen the union-find material in Chapter 22. About 1/3 of the respondents said they have seen the material on dynamic programming and greedy algorithms in Chapters 16, 26, and 17, which were next on my syllabus. So at the moment I've decided to give an abbreviated version of these two topics. Here are the sections of the book I'm planning to cover in the next lectures, in this order: 16.3 17.2 17.4 17.5 22 (I haven't decided how much yet.) 16.3 will give you a look at a typical dynamic programming algorithm, and 17.2 at a typical greedy algorithm. I don't know the material in 17.4-17.5 myself, and look forward to learning it; I would guess few of the respondents have seen this either. Sometime around the time we do 17.4 you should review Chapter 24, because Kruskal's algorithm for minimum spanning trees is intimately tied to both the algorithm in Section 17.4 and the data structures in Chapter 22.
To: cse521@geoduck Subject: miniproject specs Date: Tue, 22 Apr 1997 18:21:08 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Questions from a student indented, my answers outdented. 1) You refer to implementing the 0 and 1 operators in the rings. Mathematically, these are only special elements of the rings. Is there some reason you want them treated specially, as "operators"? I have not found a need to single them out any differently than any other ring elements. 2) It seemed more natural to define a division (/) operator rather than an inverse (^-1) operator. Is this acceptable? 3) It seems more natural for the primitive function to return both omega and its inverse at the same time. Is this acceptable? For 1-3, my answers are all the same. I get to provide the specification, and you get to implement it. My specification says that the user interface has to be a certain way. 1) You have to provide procedures that return 0 and 1 (because these are 2 of the ring or field operators I've asked your interface to provide). The user should be able to treat your package as a black box and say "apply + to these operands" or "give me the multiplicative identity". 2) Ditto. You must supply ^-1. If you want to also add a function that computes a/b via the mandatory operators (a*b^-1), that's fine. 3) Ditto. If you want the inverse, then call ^-1 after you get the primitive. 4) I'm not sure about the end goal for the total package. Is this supposed to work as an interactive program, or does it just have to be functions called by programmed test data? If it were interactive, requesting an omega for every element would get tedious. I suppose this revolves around the definition of "user". Is it a programmer or a Mathematica user? It's just a package (abstract data type) that a later user can use. You'll be the first user, by doing some testing and playing with roundoff. 5) How large of values for p and N are you expecting? It sounds like you only require small numbers, but you discuss very large ones as well. (I realize this has significance for the roundoff issue, so you may hedge your answer to this one if you think it appropriate.) You've guessed the answer: p and N should be large enough that you can discover interesting things about roundoff in the complex numbers, and verify the correct answer mod p. I don't know how large that will be, but using Lipson's table of primes and primitives is hopefully plenty big.
To: cse521@geoduck Subject: linear space optimal alignment Date: Wed, 23 Apr 1997 17:44:15 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Here are some hints for the O(n+m) space and O(nm) time algorithm for computing optimal global alignments mentioned in class. Assume for simplicity that n is a power of 2. The key to reconstructing the alignment itself is to find a column index k' such that some optimal alignment path in the dynamic programming matrix passes through entry (n/2, k'). For any string S, let S^R denote string S written in reverse. Given two strings S and T, let V^R(i,j) denote the value of an optimal global alignment of the first i characters of S^R and the first j characters of T^R. How much time and space does it take to compute V(n/2,k) for all 0 <= k <= m and to compute V^R(n/2, m-k) for all 0 <= k <= m? How could you compute k' efficiently from these values? You have now reduced the problem to two similar but smaller subproblems, namely finding the path from (0,0) to (n/2, k') and finding the path from (n/2, k') to (n,m). Show that solving these two subproblems ``recursively'' (i.e., by using the same method on each of them) results in an algorithm with the time and space bounds required.
To: cse521@geoduck Subject: modular inverses Date: Fri, 25 Apr 1997 17:37:49 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Jeremy pointed out to me that, from the book's description of the extended Euclidean algorithm, it's not clear how to eliminate the recursion. Here's a simple iterative version: Procedure Extended_Euclid (a,b: integer) Returns g,s,t: integer Comment: The inputs and outputs satisfy g = gcd(a,b) = sa+tb; Begin (a_0,a_1) <- (a,b); (s_0,s_1) <- (1,0); (t_0,t_1) <- (0,1); While a_1 != 0 Do Begin q <- floor(a_0/a_1); (a_0,a_1) <- (a_1, a_0 - q * a_1); (s_0,s_1) <- (s_1, s_0 - q * s_1); (t_0,t_1) <- (t_1, t_0 - q * t_1); End; g <- a_0; s <- s_0; t <- t_0; End. It is straightforward to prove by induction on the number of iterations that a_0 = s_0 a + t_0 b and a_1 = s_1 a + t_1 b at the beginning and end of each iteration, from which g = sa + tb follows. Jeremy also pointed out that there's an alternative method for computing inverses modulo a prime p, namely a^{-1} = a^{p-2} mod p, which you can compute by "repeated squaring" (alternately square and divide by p). The reason this is the correct inverse is Fermat's Little Theorem: a^{p-1} mod p = 1, when p is prime and a is not a multiple of p. Both of these methods use a number of iterations proportional to log p (see page 811 in the text), and it's not clear which is faster in practice. One benefit of the extended Euclidean algorithm is that it is more general: even if p is not prime, it will find the inverse of a mod p whenever it exists (which is exactly when gcd(a,p)=1).
To: cse521@geoduck Subject: typo in HW3 Date: Mon, 28 Apr 1997 14:26:01 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> There's a typo in the hint for problem 2 on HW3: T[i..j] should instead read T[1..j]. Sorry about that. I've corrected the version on the web.
To: cse521@geoduck Subject: what to insert in the proof of Theorem 17.10 from today's lecture Date: Wed, 30 Apr 1997 11:32:47 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> At the beginning of Case 2.2, add the sentence "Note that A is a proper subset of B, since B is optimal and w(x) > 0." It was nagging me that the proof didn't use the fact that the weights were positive.
To: cse521@geoduck Subject: insertion in red-black trees Date: Fri, 09 May 1997 14:01:13 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Corey pointed out that I neglected a case in the insertion algorithm. Namely, if a red node has a red parent but NO grandparent, because the red parent is the root. This case is easy to handle: just flip the color of the root. (This is how the black-height increases, if you do a bunch of insertions.)
To: cse521@geoduck Subject: 2-3 trees Date: Mon, 12 May 1997 12:36:13 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Sure enough, it's exactly as Emily said, and Brian's citation to Lewis and Denenberg's "Data Structures & Their Algorithms" was exactly right. They show that 2-3 trees correspond to red-black trees: take every red node and make a 3-node out of it and its parent. (One of the invariants of red-black trees is that the root is always left black.)
To: cse521@geoduck Subject: HW4, #3 Date: Tue, 13 May 1997 09:40:06 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Yes. No actual implementation is necessary. ------- Forwarded Message Date: Mon, 12 May 1997 19:11:14 -0700 To: Martin TOMPA <tompa@cs.washington.edu> Subject: cse 521 hw 4 On problem 17-3(b) (#3 on the homework), what do you want us to do for "implement"? give pseudocode? ------- End of Forwarded Message
To: cse521@geoduck Subject: morals from today's lecture Date: Wed, 14 May 1997 12:47:03 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Today's proof wasn't as smooth as a prepared one would have been, but I think it may still have been useful. First of all, it does my humility and your entertainment some good to watch me flounder. More important, though, is that it points out the importance of writing down careful proofs. It has happened to me several times that I believed some fact was obvious, and when I tried to write down the proof it turned out to be not only unobvious, but in fact untrue! I find that the act of writing out the details forces you to examine every case carefully and mechanically, which is either reassuring or else turns up unexpected surprises. Today's proof was a case in point. Before writing it down, it seemed to have two extremely simple cases. But careful examination turned those two cases into several. It would be instructive for you to take a look at the book's proof of Theorem 15.2 while today's alternate is still fresh in your mind. The book's is organized somewhat orthogonally, and I think it is a bit simpler in retrospect.
From: nitin@june (Nitin Sharma) Subject: hw3 To: cse521@june Date: Wed, 14 May 1997 14:26:50 -0700 (PDT) Hi!, Homework 3 has been graded, and i've put your papers in your mailboxes. Those of you who dont have mailboxes can collect your paper from Martin. Some general comments about the homework: 1. a) For the first problem, when you write the algorithm, you dont need to write a detailed, almost C-like code. Pseudo-code at a fairly high level is ok too, in fact preferable. For example, saying "do a binary search in a sorted array..", or "find the max in a 2D array.." is fine, rather than writing detailed code actually implementing binary search. It makes it easier for you to write the solution, and easier and quicker for me to understand it! b) On the other extreme, showing how your algorithm would work on one particular input is not enough; you do need to write out the algorithm pseudo-code explicitly . c) Feel free to add an informal description of what your algorithm is trying to do, eg what a particular data structure in your alg represents (" Last[i] contains the last element of a candidate sub-sequence of length exactly i..", as opposed to having a number of different arrays with cryptic names like A,S, P, I etc with little clue about what they mean. 2. optimal sub-sequence alignment: - need to define the base cases. - in the recurrence V(i,j) = max (V(i-1,..),.... ) you need to include the case where you choose to match nothing (val 0). - construct the optimal alignment; start from max V_ij, rather than Vnm. 3. Most of you got it right. 4. Some of you omitted to consider the case when sum w_i > 2W. In this case, you add an elt with wt sum w_i - 2W and value infinity. From your solution to this modified problem, drop this elt and you have the sol. to the original problem. 5. Almost everyone got this right. ---------- If you have any questions regarding grading or anything else, feel free to come to my office (sieg 233)anytime. i'm usually in by 10 and stay in office during the day, but it might be better to drop a mail before coming down to 233 . -nitin ps: i havent computed the class avg. just by eye-balling the scores, my guess would be abt 65/80.
To: cse521@geoduck Subject: more on HW3 Date: Wed, 14 May 1997 15:01:06 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> 2. optimal sub-sequence alignment: - need to define the base cases. - in the recurrence V(i,j) = max (V(i-1,..),.... ) you need to include the case where you choose to match nothing (val 0). - construct the optimal alignment; start from max V_ij, rather than Vnm. Just to make this a tediously explicit, the big differences between the local alignment and global alignment algorithms are: (a) both the basis and recurrence are computed as max(0, ...the rest as in global alignment). (b) to recover the alignment from the matrix, start at the maximum matrix entry (rather than the lower right) and stop at the first 0 entry encountered (rather than the upper left). 4. Some of you omitted to consider the case when sum w_i > 2W. In this case, you add an elt with wt sum w_i - 2W and value infinity. In this case you also have to change W to sum w_i - W. If there's demand for it, I can go over any of these problems in class in more detail.
To: cse521@geoduck Subject: HW4, #4(c) Date: Wed, 14 May 1997 15:56:48 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> A pride of students came to my office at 1:20 today asking about #4(c). I apologize for the fact that I had to run off to class; I would've enjoyed talking more about it. In answer to your question, I've thought about it and yes, I do have a polynomial time algorithm. Feel free to come and talk any time about the class or HW.
To: cse521@geoduck Subject: HW3, #4 Date: Thu, 15 May 1997 10:15:27 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Nitin pointed out an interesting alternative solution to the fractional knapsack problem that some of you came up with. It uses the ordinary median algorithm rather than weighted median. I like this solution: it seems a bit simpler than going through the weighted median. Here's the outline from Nitin: An interesting apporach was to use the ordinary O(n) time median to decide if the top half elements' weights sum to W or more. If they do, recursively solve the problem with top n/2 elements. If they don't, the top half are in the knapsack, and solve recursively for the lower half elements with the knapsack size adjusted. In either case, the recurrence works out to T(n) = cn + T(n/2), which is O(n).
From: nitin@june (Nitin Sharma) Subject: more on hw2 To: cse521@june Date: Thu, 15 May 1997 12:03:23 -0700 (PDT) Hi, i omitted to mention how much worth each problem in hw3 was. so here it is: 1. 25 points for n logn solution. 2. 15 points 3. 10 points. 4. 20 points 5. 10 points ----- Total 80 points. -nitin
To: cse521@geoduck Subject: HW4, #4 Date: Thu, 15 May 1997 16:37:53 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Well, er, ahem, I'm a bit embarassed about this. My proof of the exchange property for #4 has fallen apart, and there are lots of folks in the hallway struggling with it as I write. Given that I now don't have a clean proof, here's what I propose: 1. The deadline for HW4 is extended to Monday. 2. If you're sick of having it hanging over your head, turn in as much of it tomorrow as you'd like. 3. I will work on #4 tonight. If I succeed in coming up with a clean proof, I'll broadcast some helpful hints. If I fail, well, I'll jump off that bridge when I come to it (to quote one of my favorite movies). Sorry for the pain and suffering. Martin.
To: cse521@geoduck Subject: HW4, #4b (BIG HINTS) Date: Thu, 15 May 1997 22:55:00 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> It took me the whole bike ride home, but I now believe I have a correct and clean proof. Once again, HW4 isn't due till Monday (if you want to delay that long), and I won't be handing out HW5 tomorrow. Because I had so much trouble myself with this problem, and many of you have put so much time into it already, here's what I'm going to do. In this message I'll lay out the outline of my proof of the exchange property. Your job will be to fill in the parts where I've left ellipses (...) below. (And, of course, you also have to do 4a and 4c.) First of all, forget about the hint I gave on the HW4 handout about "mates". Apologies for having misled you: that was the right hint for my wrong proof. OK, here we go. The matroid is (S,I), where S = V and A is in I iff G has some matching F incident on every vertex in A. (It is possible that A contains BOTH endpoints of some of the edges in the matching F.) (I know some of you were working on this same matroid, but some of you had other candidate matroids in mind, and I don't want to leave confusion about which matroid I'm talking about below.) I is hereditary because ... Now for the exchange property. Suppose A and B are in I, with |A| < |B|. There is some matching incident on every vertex in A; let's call the edges in this matching "A-edges". There is some matching incident on every vertex in B; let's call the edges in this matching "B-edges". Case 1: Some A-edge goes from y in A to x in B-A. ... Case 2: No A-edge goes from A to B-A. Choose a vertex x in B-A, which must exist because ... Beginning with the B-edge incident on x, create as long a path P as possible that alternates between B-edges and A-edges. Case 2.1: P ends with a B-edge at vertex y. ... Case 2.2: P ends with an A-edge at vertex y, where y isn't in A union B. ... Case 2.3: P ends with an A-edge at vertex y in A-B. x is the only vertex on P in B-A, since ... Thus, P has one vertex in B-A, and at least one vertex in A-B. ... Cases 2.2 and 2.3 exhaust the possibilities of P ending with an A-edge, because ...
X-Authentication-Warning: awabi.cs.washington.edu: molly owned process doing -bs Date: Fri, 16 May 1997 10:20:33 -0700 (PDT) From: Molly Brown <molly@cs.washington.edu> To: cse521@cs.washington.edu Subject: Classroom change Class will be underneath the tree outside the Sieg doors closest to the lawn. -- Molly
To: cse521@geoduck Subject: BRING YOUR TEXTBOOKS! Date: Fri, 16 May 1997 10:23:22 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> ------- Forwarded Message Date: Fri, 16 May 1997 10:20:33 -0700 From: Molly Brown <molly@cs.washington.edu> To: cse521@cs.washington.edu Subject: Classroom change Class will be underneath the tree outside the Sieg doors closest to the lawn. - -- Molly ------- End of Forwarded Message
To: cse521@geoduck Subject: small correction to HW4, #4b outline Date: Fri, 16 May 1997 15:43:56 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Steven just pointed out an omission in the proof outline I broadcast last night, having to do with the (technically possible) case that an A-edge has NEITHER endpoint in A. Here's the change to the two main cases to take care of this eventuality: Case 1: Some A-edge is incident on x in B-A. ... Case 2: No A-edge is incident on any vertex in B-A.
To: cse521@geoduck Subject: theory out of the box Date: Fri, 16 May 1997 18:45:12 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Thanks again for making all the arrangements to hold 521 outdoors. It was incredibly pleasant. I'm happy to continue this tradition if the weather holds up and you do the arranging (board, textbooks, and pointer in 227). (On the other hand, if anyone finds meeting outdoors somehow inconvenient or difficult, please let me know.)
X-Authentication-Warning: awabi.cs.washington.edu: molly owned process doing -bs Date: Mon, 19 May 1997 10:19:45 -0700 (PDT) From: Molly Brown <molly@cs.washington.edu> To: cse521@cs.washington.edu Subject: Class today ... will be outside again, where it was on Friday. -- Molly
To: cse521@geoduck Subject: BRING YOUR TEXTBOOK Date: Mon, 19 May 1997 10:20:49 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> ------- Forwarded Message Date: Mon, 19 May 1997 10:19:45 -0700 From: Molly Brown <molly@cs.washington.edu> To: cse521@cs.washington.edu Subject: Class today ... will be outside again, where it was on Friday. -- Molly ------- End of Forwarded Message
From: nitin@june (Nitin Sharma) Subject: averages for hw1 and hw3 To: cse521@june Date: Tue, 20 May 1997 12:03:25 -0700 (PDT) The averages are: HW1 : 44/45 hw3 : 70/80 -nitin
To: cse521@geoduck Subject: average for hw2 Date: Tue, 20 May 1997 13:06:45 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> The average for HW2 (including possible 10 points extra credit) was 104. The total was 110, with another 10 possible for extra credit.
To: cse521@geoduck Subject: HW5, #3 Date: Thu, 22 May 1997 10:03:53 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> If it helps, it's a property of red-black trees that the root is always black. (See exercises 14.3-2 and 14.4-1.)
To: cse521@geoduck Subject: best max flow algorithms Date: Mon, 26 May 1997 17:06:25 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Richard A. knows much more than I do about max flow, so I thought I'd ask him the current status. ------- Forwarded Message Date: Mon, 26 May 1997 16:45:30 -0700 From: Richard Anderson <anderson@whistler.cs.washington.edu> To: Martin Tompa <tompa@geoduck.cs.washington.edu> cc: anderson@cs.washington.edu Subject: Re: max flow > 1. Do you know of an animation of this algorithm? No, I don't know of anything. > 2. What's the best max flow time these days? CLR says VE log (V^2/E) > by Goldberg and Tarjan, but that's 10 years old now. Is the best > algorithm still a preflow-push variant? The best algorithms are still the preflow-push algorithms. There are slightly better results - but they are not interesting (minor asymptotic improvements with a tremendous amount of effort). One important point - the "in practice" behavior is much, much better than VE. ------- End of Forwarded Message
To: cse521@geoduck Subject: last lectures Date: Fri, 30 May 1997 16:17:23 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> On Monday I'm going to start on Chapter 37, appoximation algorithms for NP-complete problems. I'll assume that you've had basic exposure to NP-completeness. If not, be sure to read Chapter 36 now.
To: cse521@geoduck Subject: HW6 Date: Mon, 02 Jun 1997 10:20:52 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> You can assume that |E| >= |V| - 1, since otherwise the network isn't even connected.
To: cse521@geoduck Subject: final exam Date: Mon, 02 Jun 1997 15:57:31 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Our final exam is scheduled for 8:30-10:20 next Monday. For humane reasons, I'm going to propose that we make it 9:00-10:20 instead, and I'll attempt to make the exam commensurately shorter. Objections?
To: cse521@geoduck Subject: #2s Date: Tue, 03 Jun 1997 09:51:22 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Bring your #2 pencils to class Wednesday and Friday this week. We'll do the course evaluations whenever they fit in.
To: cse521@geoduck Subject: final exam FAQ Date: Wed, 04 Jun 1997 15:04:29 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Here are some actual questions I've gotten. Q: Should we study the sections in the book that you did not cover but told us to read? A: If you've already read the material in the sections I asked you to read, then that should be sufficient. (I assigned it for 2 reasons: so that you'd know this basic stuff, and so that you'd be able to follow my lectures that depend on it.) Q: Should we mostly concentrate on lecture material? A: Yes. Q: Will the problems focus on knowledge of algorithms presented in class or use of proof techniques for new algorithms or problems? A: Yes. (OK, if I had to guess, I'd guess more on the knowledge of algorithms, but I haven't made up the exam yet.) Q: I've spent at least 80 minutes on each of the homework problems throughout the quarter, so I don't expect that the final will look much like the homework assignments we have had. A: Right. It's likely to look more like the easier exercises in The Big White Book of Knowledge (as one of you calls it) that I thought would be insulting to put on homework, but wouldn't be insulting to put on an exam. There are plenty of them to use for practice. Q: I'm interested in the standard questions concerning the use of notes and the text during the test. A: My inclination now is that it will be closed book, closed notes, closed calculator. I'll let you know very soon if I've changed my mind.
To: cse521@geoduck Subject: swan song Date: Fri, 06 Jun 1997 10:10:14 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> It's too nice out to resist one last outdoor lecture. I checked, and the grass seems pretty dry. So if I can get a couple of you burly grads to help me with the whiteboard, we'll do it. I'll bring the markers. We'll meet in the usual outdoor place. Please bring your textbooks, as I've got a few transparencies and a purple shirt. Please send me mail immediately if: (a) you're volunteering to write a note on the classroom whiteboard saying where we are, or (b) you're volunteering to help move the whiteboard. M
To: cse521@geoduck Subject: repeat today's messages about the final Date: Fri, 06 Jun 1997 14:49:18 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> For those of you who missed class today, here's what I said about the exam: (1) It's 9:00-10:20. (2) Closed book, closed notes, no calculator, no blue book. All you is a pencil and eraser. (3) You don't have to memorize the details of Strassen's algorithm or red-black deletion. For any other algorithm, it's fair game for me to ask you to demonstrate that you know how it works. (4) Here's an old message from a previous incarnation of 521. ------- Forwarded Message From: Martin Tompa <tompa@geoduck.cs.washington.edu> To: cse521@geoduck Subject: some apologies I finished grading the midterms, and will return them on Tuesday. It was clear on Thursday that the exam took longer to write than I had expected when I made it up. I'm sorry about that. It was unintentional. The place where most of you had trouble was the FFT question. One of the causes of trouble I hadn't anticipated at all, namely that many of you didn't know shortcuts for doing modular arithmetic. For instance, in trying to show that 9 is a primitive 4th root of unity mod 41, some of you computed the powers 9, 81, 729, 6561, and then were faced with finding the remainders of these large numbers on division by 41. You had similar computations in the FFT simulation. No wonder you were cursing me. There are 2 tricks to make computations like this easy. I illustrated them when I did the FFT example mod 13 in class, but maybe it went by too quickly. The first trick is to reduce mod 41 whenever an intermediate computation goes over 40. For instance, in computing 9^3, if you reduce 9^2 = 81 before multiplying by 9, you'll only have to deal with 40x9 instead of 81x9. The second trick is to consider any numbers x > 20 as x-41 instead, so that you never have a remainder whose absolute value exceeds 20. With these two tricks, here's how you could compute the first 4 powers of 9 easily: 9^1 = 9 9^2 = 81 = 40 9^3 = 40x9 = (-1)x9 = -9 = 32 9^4 = 32x9 = (-9)x9 = -81 = 1 (Alternatively, 9^4 = (9^2)^2 = 40^2 = (-1)^2 = 1.) If you used these tricks, you could do the whole FFT simulation without ever doing a computation harder than 14 - 9x3 or (-10)x24. When I made up the exam, I didn't anticipate the trouble you would have if you hadn't picked up these tricks in class or from practice on your own. Because of this, I was lenient in grading the accuracy of your answers, and tried to see instead whether you understood how the algorithm works (which was the intention of the problem in the first place). Martin. ------- End of Forwarded Message
From: nitin@june (Nitin Sharma) Subject: hw6 and other misc stuff To: cse521@june Date: Fri, 13 Jun 1997 13:39:30 -0700 (PDT) HW 6 has been graded and so you'll be able to collect it from Martin soon. I'll be gone tomorrow, so if you have any questions regarding hw6 grading (or any prev hw's), see me soon. I'll be in my office (233 sieg) until 5. -nitin
To: cse521@geoduck Subject: exams and HW6 Date: Fri, 13 Jun 1997 16:19:51 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> are in my office, ready to be picked up.
To: cse521@geoduck Subject: final exam solutions Date: Mon, 16 Jun 1997 10:33:36 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Here are some hints, if you want to figure out places where you went wrong. 1(a): p=37 is actually the SMALLEST prime guaranteed to be large enough. Some of you bounded the output incorrectly, making it look as though a smaller prime would also have worked. The answer to this part is intimately tied to the correct answer to part (e). 2: A number of you must have studied this problem together from the book, and came up with an interesting but not quite correct solution. Here are 3 possible correct solutions: (a) Insert A[1], ..., A[n] in that order into an OS tree that is initially empty. Whenever the insertion path goes left from some node x, add 1 + size(right(x)) to an accumulator. (b) Insert them all into an OS tree. For i from 1 to n, add rank(A[i]) - 1 into an accumulator and remove A[i] from the tree. (c) Find the rank of A[i] in A[1..i], and later the rank of A[i] in A[1..n]. Add the difference into an accumulator. 4: Many of you extended the binary heap algorithm for increasing a key to binomial heaps, and some of you recognized that that would run in log^2 n time. There is a simple O(log n) time algorithm: delete x, change its key, and reinsert it. The beauty of binomial heaps is the rich set of operations you have at your disposal. 5(a): Repeat after me: depth-first search, breadth-first search, depth-first search, breadth-first search, depth-first search, breadth-first search. All you need to do is find all the vertices reachable from s in the residual network. Nic had a lovely solution that runs in O(|V|) rather than O(|V|+|E|) time: find an h' between 0 and |V| such that no vertex ends up at height h', and output all the vertices that end up higher than h'.
To: cse521@geoduck Subject: exam mean Date: Mon, 16 Jun 1997 10:56:42 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> I forgot to mention that the mean final exam grade was 72. It was a pretty challenging exam, and the grades were spread all over.