Following usual Internet conventions, administrative requests concerning the mailing list itself, such as add/delete/address change requests, should be addressed to cse326-request@cs.
To: cse326@geoduck Subject: test of mail log Date: Mon, 25 Mar 1996 14:56:58 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu>
To: cse326@geoduck Subject: cse326 mailing list Date: Mon, 25 Mar 1996 17:31:43 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> I have established a mailing list, cse326@cs, for class announcements and discussion. Mail sent to the list is also automatically logged to the course web, http://www.cs.washington.edu/education/courses/326 so you can read it in either place. You should feel free to use it to ask questions, post information, or initiate discussions of general interest to the class. Questions or comments that are not of general interest should instead be directed to the TA (juanito@cs) or instructor (tompa@cs). Send mail to cse326-request@cs to be added to or removed from the list.
To: cse326@geoduck Subject: no need to subscribe to cse326 Date: Tue, 26 Mar 1996 13:24:03 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> If you receive this message, there is no need for you to send a "subscribe" request to cse326-request. You are already on the mailing list. The course web is now initialized and ready to roll.
To: cse326@geoduck Subject: expanded office hours Date: Wed, 27 Mar 1996 15:58:06 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> As announced in lecture today, our office hours for the quarter are expanded, as follows: Martin Tompa: Sieg 426B, Mon 3:00 -- 4:00 and Wed 2:00 -- 3:00 tompa@cs.washington.edu, 543-9263 Juan Alemany: Sieg 326D, Thu 10:30 -- 11:30 juanito@cs.washington.edu I have updated this on the course web.
To: cse326@geoduck Subject: web tech notes on unix Date: Wed, 27 Mar 1996 16:12:34 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> A few students have asked about introductory (or refresher) unix notes. There are some tech notes on the department web at URL http://www.cs.washington.edu/htbin/info2www?(DIR)TN In particular, TN159, called Notes for New UNIX Users, looks like a pretty good summary of the basics.
To: cse326@geoduck Subject: for nonmajors Date: Thu, 28 Mar 1996 12:08:50 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> If you are not a CSE major and you need an account on the 329 lab machines, please see me after class on Friday for an application.
To: cse326@geoduck Subject: reading Date: Fri, 29 Mar 1996 08:43:42 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> You should read the following sections in the textbook: 3.1 - 3.3 4.1 - 4.4 I will start talking about chapter 3 today.
To: cse326@geoduck Subject: questions 4-6 Date: Sun, 31 Mar 1996 19:42:00 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> A 326 student asks: For questions 4, 5, and 6, in the statement of a for loop is the "to" intended to mean "less than" or "less than or equal to". I assumed the latter case, but thought I should ask while there is still ample time to make the necessary changes. Yes, it's the latter. The book's construct for i from 1 to n do ... means the loop is executed n times, with i running from 1 to n, inclusive.
To: cse326@geoduck Subject: singly linked list implementation of queues Date: Mon, 01 Apr 1996 12:58:29 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> I looked in the book (Figure 3.3) and see now what was wrong with my hasty diagram at the end of today's lecture. I had implemented queues with the list pointers pointing toward the front of the queue. If you do this, then when you dequeue you can't get your hands (or rather, your front pointer) on the new front of the queue (without using linear time to traverse the whole list). But if the pointers all point toward the back of the queue, then both enqueue and dequeue can be done in constant time. It's worth drawing a few pictures to try it each of these ways, and see why one works and the other doesn't. Live and learn.
To: cse326 Subject: example code Date: Tue, 02 Apr 1996 16:15:54 PST From: Juan Alemany <juanito@june.cs.washington.edu> Hi, I just put a sample project in /cse/courses/cse326/examples/sample_project This project includes a README, a makefile, a few source files, and a couple of input files. To copy it over to your directory do the following steps: grizzly% cd (this brings you back to your home directory) grizzly% mkdir my_project (this creates the directory with the name my_project) grizzly% cp /cse/courses/cse326/examples/sample_project/* my_project (this copies all files in /cse/courses/cse326/examples/sample_project to your directory) Once you have done this look at the files, in particular the README and the makefile and try compiling and running the project. Hope this helps.. --juan
To: cse326@geoduck Subject: error recovery in InfixToTree Date: Wed, 03 Apr 1996 13:36:48 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> I gave some thought to the question of error recovery in HW2. The problem is that you may encounter an error when you are deeply nested in recursive calls to InfixToTree. Here's what I suggest as the cleanest way to handle this: If you discover an error in the formula during InfixToTree, it simply returns some sort of error indicator (say, a null tree) to its caller. If that caller is again InfixToTree, it should also return the error indicator. If the caller is InfixToPrefix or InfixToPostfix, then that function should print an error message, flush the rest of the input line, and return.
To: cse326@geoduck Subject: I/O for HW2 Date: Wed, 03 Apr 1996 14:52:40 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> Your functions InfixToPrefix and InfixToPostfix should take no parameters and return no result. They will instead be reading an infix formula from the standard input stream and writing the converted formula to the standard output stream. This is important, because we will soon be providing a small driver that calls these two functions and assumes this interface.
To: cse326 Subject: Turning in homework 2 Date: Wed, 03 Apr 1996 15:53:12 PST From: Juan Alemany <juanito@june.cs.washington.edu> CSE 326 Spring 1996 Turning in Homework 2: ------------------------ What to Turn in: ---------------- For each programming assignment you will need to turn in a hard copy in class, and also turn in electronically your files. Hard Copy: ---------- You should turn in a hard copy of all your source files, and a hard copy of your README file (see below for more details). Electronic Copy: ---------------- You should turn in the following: 1) a short file called README. In this file you should tell me: -if your program is complete (if it isn't complete tell me how far you got) -if your program works (if it has bugs tell me what they are) (Motivation: For almost all homeworks I will run all programs. If your program doesn't work I'll spend some time trying to figure out how well it works. Unfortuanetly, if I don't quickly see what's wrong and you don't have a README file telling me what you were doing and what isn't working I'll have to guess or estimate how far you got. The more you tell me, the better I'll estimate what you did). 2) all the necessary source files (.h and .cc) 3) a makefile. -I should be able to compile your program just by typing make at the command line. -in the makefile, you should change the name of the executable to hw2.exe (for hw2). In other words change the PROGRAM line to PROGRAM = hw2.exe 4) Please don't turn in your executable, and don't turn in your .o files. They take a lot of room on the disk and I will want to compile your stuff anyway. How to Turn in the Electronic Copy: ----------------------------------- Suppose you have all your files in a directory called my_hw2 and you are ready to turn in, i.e. if you type ls at the command line you get grizzly%ls cse321/ my_hw2/ t2/ Suppose your section is AB. Then you would type turnin -c cse326=AB -p hw2 my_hw2 For example: grizzly% turnin -c cse326=AB -p hw2 my_hw2 Compressing submitted files... please wait Your files have been submitted to cse326, hw2 for grading. grizzly% Other Details: -------------- 1. Please put your name in all your source files. 2. Please use comments. You should have at least a comment per function telling what it does. If you have any piece of code for which it is not completely obvious how it works, put a comment explaining what's going on.
To: cse326@geoduck Subject: HW2 info field Date: Thu, 04 Apr 1996 11:32:30 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> A student asks, "For the data part of the tree node is it necessary to differentiate between integers and characters or can we just store them as strings?" You should store them as either integers (operands) or characters (operators). Even though all you're doing with this program is printing out the tree, in a real application you would be applying the operators to the operands, and so you wouldn't want them to be strings.
To: cse326 Subject: driver for hw 2 available. Date: Thu, 04 Apr 1996 12:49:01 PST From: Juan Alemany <juanito@june.cs.washington.edu> The driver for hw2 is available in /cse/courses/cse326/examples/hw2_driver.cc To copy it to your directory, cd to your hw2 directory and then type cp /cse/courses/cse326/examples/hw2_driver.cc . The driver calls the functions InfixToPrefix and InfixToPostfix with no arguments.
To: cse326@geoduck Subject: chapter 6 reading Date: Fri, 05 Apr 1996 08:24:54 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> Read sections 6.1 6.2 6.3 through the end of page 183 6.4
To: cse326@geoduck Subject: HW2: BinaryTree interface Date: Fri, 05 Apr 1996 09:32:17 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> A few students have asked Juan if the BinaryTree operations must have exactly the syntax specified in HW2, e.g., Info(T). The answer is no, in the following sense: in C++, it's most natural to make these member functions, so that the invocation would look like T.Info() -- that's just fine. Some students also asked if it's o.k. to use a parameterized constructor instead of a member function NewTree. Again, that's fine. What's worrying a number of you is the sentence "if I substituted some other correct implementation of BinaryTree in part (1), your procedures in part (2) should still work." All I mean by this is that the representation of the tree should be private to the class, and your procedures in part (2) shouldn't be relying on explicitly following pointers, knowing the names of the fields in tree nodes, etc. They should be accessing the tree only through the types of operations listed in part (1).
To: cse326@geoduck Subject: lab tech notes Date: Fri, 05 Apr 1996 12:42:42 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> I added a link on the 326 home page that points to the lab tech notes mentioned below, in case you have had trouble finding it. --------- To: cse326@geoduck Subject: web tech notes on unix Date: Wed, 27 Mar 1996 16:12:34 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> A few students have asked about introductory (or refresher) unix notes. There are some tech notes on the department web at URL http://www.cs.washington.edu/htbin/info2www?(DIR)TN In particular, TN159, called Notes for New UNIX Users, looks like a pretty good summary of the basics.
To: cse326@geoduck Subject: questions on HW2 Date: Sat, 06 Apr 1996 18:00:19 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> A student asks two questions (indented below): 1. for LeftSubTree and RightSubTree do you want them to actually return the subtrees by VALUE -- that is make copies of subtrees. Such as BinaryTree leftsub = someOtherBTinstance.LeftSubTree(); or are they to return references to subtrees: BinaryTree *pLSub = someOtherBTinst.LeftSubTree(); These operations should return a BinaryTree, not a pointer to a BinaryTree, as specified in the instructions. 2. What's going on with isEmpty(T)? What is an empty tree? Does this mean it is a tree with info "empty" ? -- this seems unlikely as trees are constructed in your specs with info and there is no apparent way to strip a tree of its info, if this is something that you would even want... Or perhaps this means that the trees descendents are both NIL trees, but then I guess the method/message/member would be named isLeaf, as per page 103 of text. Look back at the definition of binary tree, either in the textbook or from my lecture. You will find that the empty tree is the basis of that recursive definition. It is a tree with NO nodes, so neither guess above is correct.
To: cse326@geoduck Subject: HW2 error messages Date: Sat, 06 Apr 1996 18:25:02 PST From: Martin Tompa <tompa@geoduck.cs.washington.edu> I don't much care how detailed your error messages are, in the case that the input expression isn't a fully parenthesized infix expression. It's o.k. with me if you simply print "Error" with no explanation of what is wrong with the input. This is not a central point of this assignment.
Date: Mon, 8 Apr 1996 20:53:13 -0700 (PDT) From: Eric Farris <esfarris@grizzly.cs.washington.edu> To: Juan Alemany <juanito@grizzly.cs.washington.edu> cc: cse326@grizzly.cs.washington.edu I'm having trouble figuring out how to do the infixToTree recursion. I`ve come up with some ideas on how to do the other functions but even after a long time I can't seem to get anywhere on the recursion. I'm stuck and need serious help. If you could mail me or even call me at home at 789-6893 (up til 10) I'd really like to set up a time to meet and discuss my problems. Thank you very much. Eric Farris esfarris
To: cse326@geoduck Subject: HW3 due date Date: Mon, 15 Apr 1996 12:34:53 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> As announced in class today, HW3 will be due this Friday (4/19) instead of Wednesday.
To: cse326@geoduck Subject: reading assignment Date: Tue, 16 Apr 1996 17:42:48 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Your next reading assignment is to read Section 7.1.
To: cse326@geoduck Subject: lecture room change Friday, 4/19 Date: Wed, 17 Apr 1996 12:34:29 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> For this Friday only, CSE 326 will meet in Loew 201.
To: cse326@geoduck Subject: Algorithm 6.9 (recap) Date: Wed, 17 Apr 1996 12:37:40 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> As mentioned today in lecture, I've now seen 3 versions of the textbook with 3 different Algorithm 6.9's in it. Two of them are fine (and interchangeable for our purposes), but if you have one with the line else if LC(RC(P)) = Lambda then LC(Q) <- LC(P); P <= Q; then simply cross out that line. It makes no sense, since Q is uninitialized. Yes, you do still have to do exercise 4 of HW3, since none of these 3 versions of Algorithm 6.9 is correct on the case mentioned in that exercise.
Date: Wed, 17 Apr 1996 18:48:51 -0700 (PDT) From: "A. Berglund" <aberglun@u.washington.edu> To: cse326@cs.washington.edu Cc: juanito@cs.washington.edu, tompa@cs.washington.edu Subject: Re: Locatives: C++ Translations. ( On Wed, 17 Apr 1996, Martin Tompa wrote: ) Thanks for thinking about this. This seems like a good exercise to have done. It looks like you've got all the right ideas, but there are 2 possible places where I see problems. 1. P <- 2 C = 2; P = &C; It's not clear that P <- constant is meaningful, and probably best to avoid it. See the discussion on page 496, where they say it should either produce an error, or else be interpreted the way you have. In general, I found Appendix A good for clarifying the semantics of locatives. 2. P <= Q *P = *Q; P = Q; This doesn't look right to me. I think the translation should simply be *P = *Q; did you see anything in the book that suggests otherwise? You would be doing the class a service if you're willing to make these notes below and broadcast to cse326. I'd like to see more class use of this list. ____________________________________________________________________________ compiler temporary variable C; // assigned by compiler during compile, // and is not accessable to programer. locative P, Q; // locative variables, the equivilant of // pointers in C++. variable N; // like int in C++. // The digit "2" used below represents a non-single variable right side! locative C++ translation comments -------- --------------- ------------------------------------------- P <- 2 C = 2; P = &C; See Tompa's comment #1 above. P <- N P = &N; P <- Q P = Q; P <= 2 *P = 2; P <= N *P = N; P <= Q *P = *Q; P = Q; See Tompa's comment #2 above, and mine below. N <- 2 N = 2; N <- N N = N; N <- Q N = *Q; This situation always results in the locative being dereferenced: *P or *Q . N <= 2 N = 2; N <= N N = N; N <= Q N = *Q; // The use of a locative in an equation on the right side, or as an // address calculation on the left side, or as in the last line of groups // #3 and #4 above, the locative is always dereferenced: *P or *Q . ________________________________________________________________________ With reference to Tompa's #2: The book is not clear on this one, or more precisely, is contridictory. Juan and I seem to hold to the translation above, but . . . Appendix A of the new edition, page 494, last paragraph, next three lines: This is the only portion that seems to refer to this particular situation, as does the fourth line of Figure A.1, but the discussion is not clear. This would seem to support Tompa's view. On page 14, last paragraph: This seems to support the translation above, but . . . There is a "First," and a "Second,". The first statement seems clear enough, but the second seems purposelessly redundant. This leads to the question of "Are we interpreting the author's intent or are we missing something?". So, it would seem that the second part of the translation, P = Q; , is still uncertain. Comments or errors? Send to cse326@cs .
Date: Wed, 17 Apr 1996 18:56:08 -0700 (PDT) From: "A. Berglund" <aberglun@u.washington.edu> To: cse326@cs.washington.edu Subject: Locatives: C++ translations. Oops . . . Two slight omissions: 1 - The comment on the third line of Group #3 should have been erased. It became incorporated in the comment right after Group #4. 2 - A point of posible confusion: I am using <- for the equal operator, and <= as the locative equal operator.
To: cse326@geoduck Subject: Re: Locatives: C++ Translations. Date: Wed, 17 Apr 1996 23:30:15 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Alan's done a very nice job of translating the various assignments involving locatives into C++, which I think helps understand locatives better. Let me particularly direct your attention to his table below, which I find helpful: compiler temporary variable C; // assigned by compiler during compile, // and is not accessable to programer. locative P, Q; // locative variables, the equivilant of // pointers in C++. variable N; // like int in C++. locative C++ translation -------- --------------- P <- 2 C = 2; P = &C; P <- N P = &N; P <- Q P = Q; P <= 2 *P = 2; P <= N *P = N; P <= Q *P = *Q; P = Q; N <- 2 N = 2; N <- N N = N; N <- Q N = *Q; N <= 2 N = 2; N <= N N = N; N <= Q N = *Q; Notice that groups 3 and 4 are identical: if the left side of an assignment isn't a locative, then <- and <= have the same meaning. There's also a sort of duality between groups 1 and 2: in group 2, there is an extra level of dereferencing on the left and right sides of the assignment (well, sort of). Alan then goes on to say that the book is self-contradictory about the exact meaning of P <= Q when both are locatives: Chapter 1 seems to say that Alan's translation above is correct, whereas Appendix A seems to say the translation should simply be *P = *Q. This uncertainty would only make a difference if there was some use made of P after the locative assignment P <= Q. So far we haven't encountered such a situation, and it may well not arise in the rest of the course either.
Date: Thu, 18 Apr 1996 09:02:17 -0700 (PDT) From: "A. Berglund" <aberglun@u.washington.edu> To: cse326@cs.washington.edu Subject: Re: Locatives: C++ Translations. locative C++ translation -------- --------------- P <- 2 C = 2; P = &C; P <- N P = &N; P <- Q P = Q; P <= 2 *P = 2; P <= N *P = N; P <= Q *P = *Q; P = Q; N <- 2 N = 2; N <- N N = N; N <- Q N = *Q; N <= 2 N = 2; N <= N N = N; N <= Q N = *Q; An additional thought: Irrespective to anything that might be in the book, I woke up this morning with an interesting thought. Suppose that after using P <= Q, the programer still wanted access to what P had been pointing to. Since P <- Q does the same thing as the second part of P <= Q, perhaps we should dispose of the second part all together and simply invoke P <- Q directly if that is the functionality that we want. That would leave P <= Q to mean only *P = *Q .
Sender: amir Date: Fri, 19 Apr 1996 14:19:54 -0700 From: Amir Michail <amir@cs.washington.edu> Organization: University of Washington To: cse326@cs CC: amir@cs Subject: Using visual programming to teach data structure algorithms. Hi. I am a graduate student working on my quals project with Prof. Tanimoto. The project is about an approach for teaching data structure algorithms through visual programming. The idea is to have the student visually manipulate abstract pieces of the data structure (i.e., not just nodes) in order to implement an algorithm. Moreover, in the process, certain properties of the algorithm are also proved (visually). Once the programming is completed, the algorithm can be animated on examples. I have been building a prototype system which teaches balanced tree (dictionary) algorithms in this manner. Moreover, I have had a paper on this work accepted at the Visual Languages '96 conference. However, I need some user testing to complete the work. If you are interested in trying out this system and giving me some feedback, please send me email. I would appreciate your help. Amir Michail P.S. If you are curious, the system is implemented in Java and accessible from my home page: http://www.cs.washington.edu/homes/amir/Main.html However, as this is an early prototype and doesn't come with instructions, it is best if you contact me first.
To: cse326@geoduck Subject: HW4, 2a Date: Tue, 23 Apr 1996 16:30:29 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Problem 2a should refer to AVLTreeDeleteMin rather than AVLDeleteMin. This is the algorithm that I handed out on Monday.
To: cse326@geoduck Subject: 7.3 Date: Wed, 24 Apr 1996 09:49:35 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Your next reading assignment is section 7.3.
To: cse326@geoduck Subject: (abuse of) asymptotic notation Date: Mon, 29 Apr 1996 09:05:12 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> A student asked: "In the homework problem 2b, you mention that executing AVLDeleteMin on the worst case trees on page 221 (figure 7.2) causes theta(log n) rotations to be done. Is this the same thing as saying that the number of rotations necessary to balance the tree after deletion is some function g(n), where g(n) is a member of theta(log n) ?" Yes, this is exactly right, and in fact a more accurate (but less common) way of saying it.
Date: Wed, 1 May 1996 15:42:50 -0700 (PDT) From: Frederic Mokren <frederic@wolf.cs.washington.edu> To: Martin Tompa <tompa@geoduck.cs.washington.edu> cc: cse326@geoduck Subject: Really cool Binary Tree web site Here is the URL of animated demonstrations of various binary tree implementations: http://langevin.usc.edu/BST/ Warning: requires Java aware browser. Check it out. Frederic
To: cse326@geoduck Subject: HW5 Date: Wed, 01 May 1996 17:39:31 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> HW5 is on the web. It's an implementation assignment, so don't put off getting started on it. I'll hand out hard copy Friday.
To: cse326@geoduck Subject: HW#5 Questions Date: Fri, 03 May 1996 08:38:05 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> A student asked the following good questions about HW5: 1. What is the data type for Key K (int, char, ...) ? Make it int, in keeping with most of our examples. 2. I suppose we need to have Info field for each node. What do you want us to put in the Info field ? No need to have an Info field for this HW. Just keep in mind that in a real application there would be one. 3. Is there a restriction that we have to implement the Binary Tree as a class, or can we implement it as a struct ? What should be implemented as a class is the Dictionary, with member functions for (at least) lookup, insert, concat, and delete. I'll leave it to you to decide whether splay trees and/or binary trees should also be implemented as classes.
To: cse326@geoduck Subject: HW5: parent pointer Date: Fri, 03 May 1996 10:29:38 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> A student asked: "Is it ok for us to use a parent field in our splay tree?" It shouldn't be necessary, and I would rather that you didn't, since it wastes space.
To: cse326 Subject: scores so far. Date: Fri, 03 May 1996 16:12:27 PDT From: Juan Alemany <juanito@june.cs.washington.edu> Here is a list of averages for the first 3 homeworks. homework average maximum --------------------------------------- hw1 60.7 65.0 hw2 73.8 85.0 hw3 62.6 65.0
To: cse326@geoduck Subject: Chapter 8 Date: Mon, 06 May 1996 10:09:26 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Read sections 8.1, 8.3, and 8.5.
To: cse326 Subject: hw5 driver. Date: Mon, 06 May 1996 13:44:13 PDT From: Juan Alemany <juanito@june.cs.washington.edu> The driver for hw 5 is available in /cse/courses/cse326/examples/hw5_driver.cc To copy the driver to your directory type cp /cse/courses/cse326/examples/hw5_driver.cc . Currently, the driver only prompts the user for input; unlike the driver for hw2 it does not call any functions. You should put calls to your code and object declarations in the driver so it works with your code. Let me know if you have problems with it. Thanks,--juan
To: cse326@geoduck Subject: HW5 questions and answers Date: Mon, 06 May 1996 13:59:45 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> 1) How will the driver call the specified function? Do you want them to invoke members of the class, so that they are called SplayTree.LookUp(K,T) or do you want it like the last assignment where the functions return pointers or actual splay trees? Also, do you want a NewTree and IsEmpty functions like the Binary Tree implementation? Juan has written a driver for HW5, and has sent out mail telling you where to find it. In the driver, there are places for you to insert function calls that (1) initialize an empty dictionary, and (2) do lookup, insert, delete, and print on the current dictionary. IsEmpty is not necessary. Since you are implementing a dictionary class, probably the best way to do this would be to have public member functions for the operations. But we don't have to be consistent about naming, since you will supply the invocations in the driver yourself. Please keep changes to the driver to a minimum by simply inserting function calls in the marked places. You do not have to make concat public. 2) In displaying the splay tree, do you want it to be displayed vertically like: 5 / \ 3 7 \ 4 or horizontally like: 5 |--3 | |--4 | |--7 The display is up to you: make it as fancy or as plain as you like. (There will be a couple of extra credit points available for especially nice trees, but not enough that it's worth spending time on unless you're interested.) But be sure that the tree is unambiguously recoverable from your display. For instance, in the outline form above I can't tell whether 4 is a left or right child. 3) Since we don't need an Info Field for the BinaryTree in this assignment, what should be the return value of LookUp ? Will Boolean be appropiate ? (True if key K exist in the Tree, and False otherwise). Yes, that's what you should do. 4) Is it o.k. if our functions make copies of the splay tree? Be sure that none of your functions make a copy of the tree. Such a Theta(n) time operation would destroy the efficiency of splay trees. Finally, don't forget the instructions for electronic turn-in posted earlier by Juan: CSE 326 Spring 1996 Turning in Homework 2: ------------------------ What to Turn in: ---------------- For each programming assignment you will need to turn in a hard copy in class, and also turn in electronically your files. Hard Copy: ---------- You should turn in a hard copy of all your source files, and a hard copy of your README file (see below for more details). Electronic Copy: ---------------- You should turn in the following: 1) a short file called README. In this file you should tell me: -if your program is complete (if it isn't complete tell me how far you got) -if your program works (if it has bugs tell me what they are) (Motivation: For almost all homeworks I will run all programs. If your program doesn't work I'll spend some time trying to figure out how well it works. Unfortuanetly, if I don't quickly see what's wrong and you don't have a README file telling me what you were doing and what isn't working I'll have to guess or estimate how far you got. The more you tell me, the better I'll estimate what you did). 2) all the necessary source files (.h and .cc) 3) a makefile. -I should be able to compile your program just by typing make at the command line. -in the makefile, you should change the name of the executable to hw2.exe (for hw2). In other words change the PROGRAM line to PROGRAM = hw2.exe 4) Please don't turn in your executable, and don't turn in your .o files. They take a lot of room on the disk and I will want to compile your stuff anyway. How to Turn in the Electronic Copy: ----------------------------------- Suppose you have all your files in a directory called my_hw2 and you are ready to turn in, i.e. if you type ls at the command line you get grizzly%ls cse321/ my_hw2/ t2/ Suppose your section is AB. Then you would type turnin -c cse326=AB -p hw2 my_hw2 For example: grizzly% turnin -c cse326=AB -p hw2 my_hw2 Compressing submitted files... please wait Your files have been submitted to cse326, hw2 for grading. grizzly% Other Details: -------------- 1. Please put your name in all your source files. 2. Please use comments. You should have at least a comment per function telling what it does. If you have any piece of code for which it is not completely obvious how it works, put a comment explaining what's going on.
To: cse326@geoduck Subject: prompting for the key on HW5 Date: Mon, 06 May 1996 16:08:09 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> From the driver, it appears that you wont be prompting for the Key. Do you want us to prompt for the Key inside of Insert or to add the code in the driver to prompt for the Key and pass the Key to Insert... It's fine to add the prompts for the key to the driver. This will make your call on the dictionary operations look more like they do in the book, since you would be able to pass the key as a parameter.
To: cse326@geoduck Subject: concat on null trees Date: Tue, 07 May 1996 09:08:53 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> "I have a question about the function Concat(T1, T2). If T1 is NULL, the function will just return T2. Now, if T1 is not NULL but T2 is NULL, is Concat supposed to perform Splay on T1 and and attach a null tree to the right child of the root? If so, what's the best way to pick a key to splay on T1?" It is not necessary to splay T1 if T2 is null. You can simply return T1 as the concatenation of the two trees.
To: cse326@geoduck Subject: inheritance in dictionaries Date: Tue, 07 May 1996 12:56:55 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> With Owen's permission, I'm forwarding a message about inheritance and dictionaries. The answer I gave him is that I think it's fine to have the class be SplayTree, as long as it provides the public functions Lookup, Insert, Delete, and Print. The alternative of having a more generic Dictionary class (implemented as splay trees) with these public functions is also o.k. for HW5. ------- Forwarded Message Date: Tue, 07 May 1996 10:48:30 -0700 From: Owen Benneter-Flatley <flato@lynx.cs.washington.edu> To: Martin Tompa <tompa@geoduck.cs.washington.edu> Subject: Re: HW#5 Questions On Fri, 3 May 1996, Martin Tompa wrote: > 3. Is there a restriction that we have to implement the Binary Tree as a > class, or can we implement it as a struct ? > > What should be implemented as a class is the Dictionary, with member function s > for (at least) lookup, insert, concat, and delete. I'll leave it to you to > decide whether splay trees and/or binary trees should also be implemented as > classes. > Further, is there a restriction to how we devise our inheritence, assuming we choose to represent splay tree as a class. To me, we have something like: (base class at top) Container_____________________________ | | _____________________Dictionary________________ ... | | | | BinaryTrees Lists deque ... | | | | RotatableTree ... ... ... | | Splay_Tree AVL_Tree Of course, this means that clients must know if they want to use a splayTree or an AVL or a List or whatever. Like: main() { SplayTree adfoh; DoubleList goik; AVLTree gijh; Stack myStack; } To me, this makes sense. There are times that I definitely want to choose which form of dictionary I use. Certainly, I can implement Dictionary as an abstract base class with methods as specified. However, another student gave me the impression that our driver should look more like: main() { dictionary fred, ethel; for( long ndx=0 ; ; ndx++ ) fred.insert(ndx!) } The implication being that the client should not care what dictionary is being used, just that they have the 3 basic operations available. If this is correct, then how would a client use a List and a Splay Tree in the same program ? owen ------- End of Forwarded Message
To: cse326@geoduck Subject: office hour cancelled Date: Wed, 08 May 1996 13:06:59 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> An emergency has come up, and I'm going to have to cancel this afternoon's office hour. Sorry.
To: cse326 Subject: tomorrow's 326 section cancelled Date: Wed, 08 May 1996 13:15:23 PDT From: Juan Alemany <juanito@june.cs.washington.edu> Tomorrow there will be no quiz section. Instead, I will be around the Sieg 329 lab at those times (9:30-10:30 and 2:30-3:30) to answer any hw 5 questions. Please, keep in mind that answering a question may take some time (especially if it involves looking at code) so I may not be able to help everyone. I guess the best thing to do would be to be there working and if you have a question, tell me and when I am free I'll get over to your machine. thanks, --juan
To: cse326@geoduck Subject: class and office hour cancelled today Date: Mon, 13 May 1996 07:26:29 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> I have to cancel today's lecture and office hour, because I'm sick. I'll be back on Wednesday. Enjoy the day off, and my apologies if this last minute notice caused you problems.
To: cse326@geoduck Subject: Read sections 9.1 and 11.3 Date: Wed, 15 May 1996 10:47:26 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> I will probably start on priority queues and heaps in Friday's lecture.
To: cse326@geoduck Subject: the meaning of distinct Date: Mon, 20 May 1996 08:56:45 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> "On problem 3, does "distinct" mean different? That is, for the ordered pair (q,r) q cannot equal r?" Yes, this is exactly right. "Distinct" means "unequal".
To: cse326@geoduck Subject: hw6, prob 1(d) Date: Mon, 20 May 1996 10:20:11 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Does "all the nodes...on the path to 90 had rank k" include the node with key 90 itself? Also, does "no increase in ranks" include the node with key 90? "Yes" to both questions.
To: cse326@geoduck Subject: universal classes of hash functions Date: Mon, 20 May 1996 10:42:04 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> What's indented below is a thoughtful question from a student about randomness. My answer is at the end. With regard to UC of Hash fuct, I understand that its claim is that choosing any two different number x1 and x2, doesn't necessarily to be the same, using UC of Hash fuct will give us h(x1) and h(x2) as if x1 and x2 are random. And in class (in the beginning of discussion about UC of Hash fuct), we talked how the statement : "choosing a random h from a good set of H after some key of K has been inserted" , doesn't make sense, cause we can't wait till all key has been inserted then choose a random h. (Practically, we choose a random h, right after the first key has been inserted). If what I said inside the parantheses is true, then this bothers me : it is true that by choosing a random h from a good set of H, will give us h(x1) and h(x2) as if x1 and x2 are random, but after the first key has been inserted, h(x) is fixed, thus the above statement is true only for the first two keys we insert. For the rest of the keys, h(x) is not random anymore, and thus the above statement doesn't hold anymore. Does it (what bothers me) make sense ? Can you give some explanation ? The only property you need is that the keys do not depend on knowledge of the hash function h. (If the client could pick keys knowing the randomly chosen h, it would be easy to make them all collide.) So as long as h is chosen randomly and the client doesn't know the choice, you can THINK of the whole process as though h were chosen after all the keys. Either way, h is random with respect to the keys. Someone asked in class whether this view wasn't somewhat paranoid, namely who would pick keys in such a malicious manner as to cause lots of collisions? The answer is one of guarantees: if you could choose from two different hashing schemes, with scheme A promising to perform well provided your keys were nicely behaved, and scheme B promising to perform well (with probability 9999/10000) no matter what keys you used, which would you prefer? One final question that's food for thought: in practice, how could you choose a random anything with a computer program? Where in the computer is there a source of true randomness? You could use a pseudorandom number generator such as rand, but is there anything truly random about its outputs?
To: cse326@geoduck Subject: HW6, #1 Date: Tue, 21 May 1996 13:55:37 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Indented questions from a student, with my answers not indented: For questions 1A and 1B, it says, 'label the subtrees that hang off this path T1, T2, ..., T10 in the order encountered during an inorder traversal' I am not sure what you want for this question. When I redrew the trees for each of the rotations, I just labeled the nodes with their appropriate key values. Do you want something more than this? All the problem statement supplies are the keys along one particular path of the splay tree. The shape and keys in the rest of the tree are left unspecified. Because there are 9 nodes on this path, there are 10 places where subtrees might be hanging off the path (two children of 90, and one additional child of each other node). These subtrees should be labeled T1, T2, ..., T10 in your diagrams. If this still isn't clear, please ask in or after class Wednesday. In question 1B, it says "Show the splay tree after each of the four double rotations" Unless I am mistaken, the tree specified by this problem, unlike the tree specified by problem 1A (which does contain the key 90) does not contain the key 90, and therefore we are going to be splaying the inorder successor of the key. I just didnt see how four double rotations would be needed if we were going to be splaying the inorder succesor of key 90. (It looks like three double rotations, and a single rotation) In both problems there IS a node with key 90. In problem 1b it is a child of 100.
To: cse326@geoduck Subject: hw#6 - 3 Date: Tue, 21 May 1996 17:03:28 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> "I am a little confused with question #3. It says that the pairs <q, r> are ordered pairs of distinct numbers. Is this mean: 0 <= q,r < N, where q < r instead q != r that you covered in the class?" No, "ordered" means the order of the pair is important. The only constraints on q and r are that 0 <= q,r < N and q != r, exactly as in the proof I gave in class.
To: cse326@geoduck Subject: Read pages 447-450 Date: Wed, 22 May 1996 11:12:15 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> ... on finding shortest paths in graphs.
To: cse326@geoduck Subject: HW6, #1 Date: Wed, 22 May 1996 11:26:22 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Problem 1, 27c: It says that all the node on the path to node 90 have the same rank K. How is this possible? Aren't they all going to have lesser ranks as one decends the splay tree? The rank can't go up as you descend down a path, but it can stay equal for a long time. For instance, consider a splay tree with n nodes in which every internal node has only one nonempty child (i.e., it's a chain). If you were to read off the ranks as you go from the leaf up to the root, they would be 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, ... In problem 1, it's quite possible to fix the unknown subtrees T1, T2, ..., T10, so that the 9 nodes in question all have the same rank.
To: cse326@geoduck Subject: HW6, #1 Date: Wed, 22 May 1996 18:09:16 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Problem 1c: Page 255 - 27c: From the text version of part-c, is it sufficient to show a specific example of ranks before and after, or are you looking for a formal variablized Proof? Again, same question for the Assignment Sheet part-c. Do you want a formal Proof that there are two node that decrease? I've come up with a simple specific case with specific decendant counts and ranks that "fits the bill", but is this sufficient for what is wanted in the text and assignment sheet? Note first that you don't have to solve the textbook version of part c for this homework. You just need to read it in order to do part d. In both c and d, I'd like your answer to hold for rank that's a variable (k in part d) rather than a particular constant. That is, in part c you should prove that there are 2 nodes whose rank decreases, and your proof should rely on the fact that the rank of 90 doesn't increase twice, not on a particular instance in which the rank of 90 is (say) 3. In part d, your proof should work for any value of k.
To: cse326@geoduck Subject: read section 9.2 through the theorem on page 314 Date: Fri, 24 May 1996 10:40:42 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu>
To: cse326@geoduck Subject: #2s Date: Wed, 29 May 1996 12:48:52 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Please bring your #2 pencils to class on Friday. We'll take the last 10 minutes to do student evaluations of the class.
To: cse326@geoduck Subject: final exam Date: Wed, 29 May 1996 14:06:40 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> The final exam is this Wednesday, 2:30-4:20, in the usual lecture room. It is closed book and comprehensive (i.e., covering the whole quarter, but with emphasis on the material since the midterm). You won't need to bring anything other than pencils or pens. The material covered includes everything in lectures and the assigned reading (see class messages on the web), right up to the last lecture this Friday.
To: cse326@geoduck Subject: last reading assignment Date: Wed, 29 May 1996 14:48:21 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Section 12.3 through the end of page 446. This is the algorithm I described in today's lecture.
To: cse326@geoduck Subject: practice problems Date: Wed, 29 May 1996 14:56:26 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Here are some practice problems on material covered since HW6, if you want them for studying for the final exam. 1. For the graph of Figure 12.9(a), ignore the edge directions and run Kruskal's algorithm on it to find a minimum spanning tree. 2. Page 467, #31. Express your answer in terms of n and e, where e is the number of edges. What property must the graph have in order for Kruskal's algorithm to consider the minimum number of edges? The maximum? 3. Page 467, #33. Also show how Dijkstra's algorithm would find the minimum cost paths themselves, and not just their costs. 4. Page 334, #12. 5. Page 334, #15.
Date: Thu, 30 May 1996 15:43:03 -0700 (PDT) From: Sean McDirmid <mcdirmid@wolf.cs.washington.edu> To: cse326@wolf.cs.washington.edu Subject: Sample exam In the following directory there is a final that was given in the winter of 1992. I thought their might be more exams, but they only have one quarter in the directory and no answers are provided. On an up note the material looks sort of familiar to what we covered in class. Standard disclaimers apply. (at the shell prompt on wolf, lynx or grizzly type this) cd /uns/acm/exams/326 Sean
To: cse326 Subject: office hours + average scores. Date: Fri, 31 May 1996 15:45:45 PDT From: Juan Alemany <juanito@june.cs.washington.edu> Office Hours: I'll have office hours on tuesday afternoon from 2-4. Averages: 93 for homework 5 72 for homework 6
To: cse326@geoduck Subject: office hours during finals week Date: Fri, 31 May 1996 15:53:52 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> I will be out of the office on Monday, June 3, and tied up most of the day on Tuesday. I'll be in my office Wednesday morning and afternoon up to the time of the exam, so if you have last minute questions that day stop by.
To: cse326@geoduck Subject: HW7, #5 Date: Tue, 04 Jun 1996 16:28:56 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> What the text neglected to mention is that the m operations should start with each element in its own singleton set. ------- Forwarded Message Date: Tue, 04 Jun 1996 16:24:00 -0700 To: Martin Tompa <tompa@geoduck.cs.washington.edu> cc: Juan Alemany <juanito@grizzly.cs.washington.edu> Subject: Re: practice problems For number 5 on the practice problems (pg 334 #15), is there anything interesting about finding m operations that take omega(log n) time? Wouldn't it just be m Find(x) operations where x is a leaf (possibly being the same leaf all m times)? ------- End of Forwarded Message
To: cse326@geoduck Subject: Re: HW7, #5 Date: Wed, 05 Jun 1996 09:32:28 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Here's a hint. You don't need more than log n time for any Find to get this result. It would suffice, say, to do m/2 Unions each taking constant time, followed by m/2 Finds each taking log n time. The question is, then, what should those Unions look like in order to create nodes that require log n Find time? It would be o.k. for this problem to choose (say) m=2(n-1), so that the Unions merge all n nodes into one Uptree. ------- Forwarded Message Date: Tue, 04 Jun 1996 18:30:12 -0700 To: Martin Tompa <tompa@geoduck.cs.washington.edu> cc: Juan Alemany <juanito@grizzly.cs.washington.edu> Subject: Re: HW7, #5 I don't see what kind of operations will do this. I can't figure out what kind of a Find operation will get me the greater-than-log n time to make up for the constant time that a Union of these subsets takes. On Tue, 4 Jun 1996, Martin Tompa wrote: > > What the text neglected to mention is that the m operations should start with > each element in its own singleton set. > > ------- Forwarded Message > > Date: Tue, 04 Jun 1996 16:24:00 -0700 > To: Martin Tompa <tompa@geoduck.cs.washington.edu> > cc: Juan Alemany <juanito@grizzly.cs.washington.edu> > Subject: Re: practice problems > > For number 5 on the practice problems (pg 334 #15), is there anything > interesting about finding m operations that take omega(log n) time? > Wouldn't it just be m Find(x) operations where x is a leaf (possibly > being the same leaf all m times)? > > > ------- End of Forwarded Message > > ------- End of Forwarded Message
To: cse326@geoduck Subject: final exams Date: Mon, 10 Jun 1996 17:02:42 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> Final exams can be picked up from my office (Sieg 426B) this week until Thursday only. The safest thing is to call me first (543-9263) to make sure I'm in.
To: cse326@geoduck Subject: final exam stats Date: Mon, 10 Jun 1996 17:08:03 PDT From: Martin Tompa <tompa@geoduck.cs.washington.edu> The mean grade on the final exam was 72.5 out of a possible 100. There were a few scores in the 90s.