Response: Thanks for pointing this out. You are correct. I have two fixes: I could change the scheme as I gave it to the one in the Rivest article. But by experimenting with the xor formula, I was able to find a formula which worked with the scheme as I gave it:

This new formula seems to work (if I haven't made another mistake). I've changed the WOM page with this correction. Alternatively you can use the data in the Rivest article. I took the scheme as I posted it from an online source and only later discovered the original article, without noticing that the scheme was different. Then I didn't carefully check the formula, which I took from the article. [Questions are supposed to be anonymous, but in case someone makes a contribution to the class, I want to give credit. Mr. Brad Munsterteiger submitted this "question", which is a correction. Thanks again.]

Suppose you have the following information as bits: 01 11 10 11 00 10. Show the result of burning this to storage in the manner of the topic. Then burn the following information as a second generation and show the result: 10 01 00 11 10 10.

Info 1st burn     2nd burn
 01    001          110
 11    100          011
 10    010          101
 11    100          011
 00    000          111
 10    010          101

Is this all you need? I got confused when you ask for: show the result: 10 01 00 11 10 10? What do you mean? I read the WOM article but got no explanation....

Answer: The numbers at the end, under "show the result: 10 01 00 11 10 10 ..." are not the result of the second burn. These are supposed to be the information that you use for the second burn.

The problem asks you to burn a new set of information for the second burn. After burning "001" to represent the information "01", you are asked to burn information "10" for a second burn. Then continue using 10 01 00 11 10 10 for your second burn.

Don't forget to show that you can use the xor formula to get the original information back, whether first or second burn. (And be careful that my notation differs slightly from that of the article.)

Answer: I never adequately addressed this issue. So if you are in a CS lab and on a Windows machine, you can access anything you have on the Linux side through the "Z" drive (Z drive! Z??). If you're on a Linux machine, then it (apparently) has the Desktop in common with the Windows side, so any file on the Windows Desktop is also accessible through the Linux Desktop. So to get a file from Windows to Linux, put the file on the Windows Desktop, do the secures shell to Linux and find it on the Linux Desktop.

However, if you are running Linux at a remote location and want to submit a file for your recitation, you can use sftp, the secure file transfer program, which exists on Linux and on Macs. I have prepared a tutorial that shows sessions using ssh and sftp on a remote Linux system (mine) to get to one of the elk machines: ssh and sftp tutorial. Let me know if any of this stuff doesn't work. (Worked for me!) The tutorial is also referenced under Item 2 on the submissions page.

One final comment: You should not make a special trip to UTSA just so you can do the proper submission (for example if ssh and sftp can't hook up to an elk). Instead of wasting gas and time, just send the recitation by email to my gmail account, as the person asking this question did.

Answer: This sort of thing is why I wrote "depending on your system, you may encounter a problem here" at the end of question 5. Different students may have results that are highly variable. Your code should work for n = 1000, but otherwise you should just report what happens. (We'll discuss this more in class or at a recitation session sometime.)

Answer: You can always combine code to produce answers, and make other reasonable modifications to how you answer questions. I would prefer that you include an "answer" for each numbered item, even if the answer says something like: "5. The answer is contained in the answer to 4 above."

Response: Yeah, you're right. I'm removing the sentence "You have to do this [insert value for depth] after you have finished constructing the tree.'

Answer:No! The median is the middle element of the array, middle in size. If the array happens to be in sorted order with 13 elements, indexed from 0 to 12, then the element with index 6 is the median. The algorithm given here lets us find the median without completely sorting the array.

Answer: Look at the tail end of the page: Recursion Trees, or look at the same material on page 176 of your text. This is using the recursion tree approach to analyze a special "unbalanced quicksort", in which the recursion tree is unbalanced 1/10-9/10 all the way down. The analysis starts with a recurrence and proceeds to an analysis of the recursion tree.

The situation in Question 6 is somewhat similar. (There are also differences.) Earlier parts have described the algorithm. In Question 6, you are asked to start with a recurrence and examine the recursion tree. All this is similar to the quicksort example, except that you are to conclude that this is a Θ(n) algorithm, rather than O(n log(n)). The correct argument needs to be a bit more precise and mathematical.

Answer: You already have the algorithm. The question asks you to argue that this really is the median, the correct result. (Why should this algorithm be working?) There is a fairly simple and straightforward answer.

Answer: OK, I added an extra line in my set of examples in the page on the master theorem (extra example clear at the end): Master Method. I also added an extra sentence before the list of examples. This refers to your text's example at the bottom of page 95 and on to the top of page 96.

2) Start with: {15,13,9,5,12,8,7,4,0,6,2,1}
Remove the max element: {13,9,5,12,8,7,4,0,6,2,1}
Reorganize the array to fit the heap property: {13,12,7,9,8,5,4,0,6,2}

Answer: This is going to take time to answer. It would be OK to just give the arrays that result, but your work is not even close to correct (sorry, don't mean to be too negative). Everything is in your text, and I'm following it exactly. In my online materials, the pseudocode for HeapExtractMax is the third box from the end on the page: heaps.

Then a later page gives an illustration of the process: extract max.

Now with the data you are given: A = {15,13,9,5,12,8,7,4,0,6,2,1}, what you did is just throw out the first element, moving all the remaining elements over one. With heaps you can NEVER do something like this. Instead, you are to exchange the max element (15) with the last one (1). Then decrease the heapsize by 1, so that the 15 effectively disappears. (But it will be returned as the return value.) Now from the top element (1), you have to restore the heap property down the line. (See the illustration.)

With what you did, after throwing out the top item, you had {13,9,5,12,8,7,4,0,6,2,1}. This is not at all a heap. The heap property fails all over the place. Doing it correctly, the heap property only fails at the top. Then it can be restored in a sequence of steps down to the bottom. You need to work through my example above.

(Wheh!) I hope this helps.

After taking off the two conditions and running the function say on A = {1,9,5,3,8}, with a work array of 27 and trying to find sums that add up to 13, the function doesn't seem to work well and gives me this as a result: W = {0,1,1,3,3,3,3,3,8,8,8, (all 8s) }. I don't know what I'm supposed to do with that information and how to tie in the C array to work parallel with W. I see that I'm supposed to find the least count of coins to add up to a certain number, but how do I do that with a modification of the calcWork function?

Answer: I'm pleased that you are working on Recitation 7. Originally it was going to be due on Monday, March 19. but I put off the due date until Wednesday, March 21, so that we would have one period when you could ask questions.

Here is a web page giving hints as a partial answer to this question 5: Hints for Rec 7, Question 5.

Response: Yeah, thanks for the heads up. I straightened it out. Now the Java program uses a file "capsdisth.txt" ("h" for "header") with the extra "48" at the start. The C program is still supposed to use the old file "capsdist.txt" without the "48".

The problem was that I was schizophrenic about wanting to allocate the graph dynamically, and also wanting to keep the C code as simple as possible. Of course you can use malloc or such to allocate the array in C dynamically.

[Um, ..., this is not an April fools' joke.]

Answer: You must use a queue for the breadth-first search, but you also should use the recursive version of depth-first search in your book (and scanned on the Rec 10 page), so there is no need for a stack. You can use whatever queue you want, including the one given in class or a library queue.

• edge < 1, 5 > should be < 1, 4 >
  
• edge < 2, 5 > is missing
  
• edge < 13, 10 > should be < 10, 13 >
  

Response: You're right, %?$#*-it. Believe it or not, those were original errors that I corrected when I ran the program, but somehow I posted the original files. The online files are now correct. If you ran your program with the old data, or even submitted it that way, you don't have to resubmit, since the incorrect data also represents a directed acyclic graph. I will easily be able to tell which data (old or new) you are using.

Answer: Sorry, but I forgot. You're the first to ask. Anyway, the answers are posted now.

Answer: Yes, quiz, and it will cover material from Recitations 9, 10, and 11, which is mostly graphs, plus Problem 1 on Rec 11 (the Newton's method-square root-reciprocal-log₂ material).