Announcements

You can find a detailed spreadsheet of how we graded your programs in Program 5 Grading. There are comments wherever X's are placed. The number of points for the first part, HashGraph was 60, and for the second part Dijkstra was 20. Each JUnit test (there were 23 for graphs) was worth 60/23 points. For Dijkstra, reading the flightcost graph was worth 5 points, computing the correct minimum distances and predecessors was worth 10 points, and displaying the nodes on the shortest path to any node was worth 5 points.

About 15 students did not reach the C level (70%) on this assignment.

IMPORTANT If you believe that we recorded one or more tests in error (we used the same tests you downloaded for the project), please email your TA (see the fact sheet for the assignment of Labs to TAs) and tell him what the differences are. He will then rerun the test, possibly asking you for more information, or running it with you at lab. If there is a difference, he will email me a revised summary about your program, and cc a copy to you. I will update the grades spreadsheet as appropriate. Every assignment so far has had a few such corrections.

After I return your graded work in class on Thursday, please download the Grades(zipped .xls file) from the course web and ensure that I have computed and entered your grade correctly (I'll be entering thousands of grades for students in my course this quarter, so even if I'm 99% accurate, I'll incorrectly compute/record some grades). Note that all grades are recorded as integral values: I always round up (e.g., an exam score of 22.5 is recorded as 23).

If you do not pick up your returned work in class, you should pick it up during my office hours ASAP; I don't like keeping student exams: it makes my office messier, and you don't get the benefit of the feedback I wrote on the quiz.

If you believe that there is a problem with grading the quiz, please bring it to my office hours. It is a win-win situation. If I did grade it incorrectly, I want to correct my mistake and give you the points you deserve. If I did not grade it incorrectly, then you are still confused about why your answer is wrong, and by coming by we can clear up the problem quickly.

Here is a quick analysis of the quiz.

• Problem #1: Students did very well on this problem. Only a few had a wrong order (those often inverted A and F), and a few more processed too many nodes: EGB was a cycle, with C having an in-edge from the cycle.

• Problem #2: Again, students did very well on this problem. Some students missed an edge here or there; more (and still not many) did not seem to follow the algorithm at all.

• Problem #3: See the solution for the file Quiz8Tester.java to see how I tested the HashEquivalence class. Typically I took off 5-8 points for solutions that did not work, and fewer points for working solutions that did not correctly implement the algorithms: typically by either (1) not truly compressing to the root (many solutions returned the root from this method, but did not make the nodes along the path all directly refer to the root), or not using/updating correctly the size information when merging.

You can find a detailed spreadsheet of how we graded your programs in Program 4 Grading. There are comments wherever X's are placed. The number of points for each class, BSTMap and HashMap was 40. Each JUnit test (there were 17 for maps) was worth 38/17 points, with an additional 2 points for having the Map implementation work correctly in the WordGenerator program.

A surprising number of students failed the WordGenerator program test because they did not take the absolute value of the hash code before doing the remainder operator (part of the compress part of hashCompress); remainder is well behaved only for positive values. I'm not surprised that you could forget to write that code initially (all the JUnit test keys hash to positive values -they are one letter); but if you ran the WordGenerator program, it would quickly fail with a negative indexs inside the bucket array. The problem statement says, "We will use the WordGenerator program, with the large text file (huck.txt) for both a large scale correctness and speed test."

Once again many students did not reach the C level (70%) on this assignment, mostly by failing to get the iterator to work correctly in BSTMap and by not solving many parts of the HashMap class.

IMPORTANT If you believe that we recorded one or more tests in error (we used the same tests you downloaded for the project), please email your TA (see the fact sheet for the assignment of Labs to TAs) and tell him what the differences are. He will then rerun the test, possibly asking you for more information, or running it with you at lab. If there is a difference, he will email me a revised summary about your program, and cc a copy to you. I will update the grades spreadsheet as appropriate. Every assignment so far has had a few such corrections.

After I return your graded work in class on Tuesday, please download the Grades(zipped .xls file) from the course web and ensure that I have computed and entered your grade correctly (I'll be entering thousands of grades for students in my course this quarter, so even if I'm 99% accurate, I'll incorrectly compute/record some grades). Note that all grades are recorded as integral values: I always round up (e.g., an exam score of 22.5 is recorded as 23).

If you do not pick up your returned work in class, you should pick it up during my office hours ASAP; I don't like keeping student exams: it makes my office messier, and you don't get the benefit of the feedback I wrote on the quiz.

If you believe that there is a problem with grading the quiz, please bring it to my office hours. It is a win-win situation. If I did grade it incorrectly, I want to correct my mistake and give you the points you deserve. If I did not grade it incorrectly, then you are still confused about why your answer is wrong, and by coming by we can clear up the problem quickly.

Here is a quick analysis of the quiz.

• Problem #1: Only a few students got this fully correct, but most students got most parts correct (say 3 of 4 points). The exact pattern of accesses is a bit complicated, and most students incorrectly showed access to -inf (never checked) and 35 and 40 (under the top accesses); actually both 50s are accessed (the bottom one for an equality check after the search). Also, some students had the wrong number of 52s, or didn't link up these values vertically.

• Problem #2: Most students did a good job here, although many implemented a version of bubble sort, not selection sort (where values are swapped only in the outer loop, not the inner one). Many students used while loops when for loops were simpler. I took off 3 points for a non-(but close to) working answer.

• Problem #3: Many students did a nice job here, and got the first test to work, but many others were not able to get the calls from mergeSort to work (which did not fill the arrary). I took off 3 points for a non-(but close to) working answer (and took off only 2 points if the first test worked).

• Problem #4: I think more students did well on this problem than any other. I took off minor points for rechecking queue allocation and for using an ArrayList.

You can find a detailed spreadsheet of how we graded your programs in Program 3 Grading. There are comments wherever X's are placed. The number of points for the Tree Statistics program was 46, the number of points for the HeapPriorityQueue was 34.

In the Tree Statistics program 1/2 credit went to computing a reasonable average height (we tested on 10,000 trees, each containing 1,000 nodes) and 1/2 credit went to printing a reasonable looking histogram

In the HeapPriorityQueue class, there were 11 tests, each worth the same amount (out of 30 points; the remove in the iterator was worth 4 points).

Many students did not reach the C level (70%) on this assignment: some did not correctly solve either part of the Tree Statistics program; others solved few parts of the HeapPriorityQueue.

IMPORTANT If you believe that we recorded one or more tests in error (we used the same tests you downloaded for the project), please email your TA (see the fact sheet for the assignment of Labs to TAs) and tell him what the differences are. He will then rerun the test, possibly asking you for more information, or running it with you at lab. If there is a difference, he will email me a revised summary about your program, and cc a copy to you. I will update the grades spreadsheet as appropriate. Every assignment so far has had a few such corrections.

The class average was about 60% and the median grade was 58% Note that by the median being higher than the average, it means that there were many scores at the tail of the distribution. Because the class average was below 75%, the grade sheet will automatically add in about 23 "normalization" points (15%) to everyone's score. Note that I entered you "real" score in the spreadsheet; the spreadsheet effectively will bump it by about 23 normalization points when computing a grade. More information about this writen exam appears below.

After I return your graded work in class on Tuesday, please download the Grades(zipped .xls file) from the course web and ensure that I have computed and entered your grade correctly (I'll be entering thousands of grades for students in my course this quarter, so even if I'm 99% accurate, I'll incorrectly compute/record some grades). Note that all grades are recorded as integral values: I always round up (e.g., an exam score of 122.5 is recorded as 123). It would be a great idea to check that I correctly listed on the first page the points you earned for each problem and computed their total correctly.

If you do not pick up your returned work in class, you should pick it up during my office hours ASAP; I don't like keeping student exams: it makes my office messier, and you don't get the benefit of the feedback I wrote on the quiz.

Recall that the exam was 165 points out of 160, so you could have skipped any small question (or lost partial credit on any large one) and still scored 100% on the exam. The highest score was 100% (although the student actualy missed 5.5 points). A bit over 23% of the students scored 75% or above (which when normalized means 23% of the student scored the equivalent of an A on the exam). See the Exams tab in the spreadsheet for a histogram of all the scores.

• Problem 1: Students attempting this problem scored an average of 86% the highest on the exam; this problem was designed to allow you to get off to a good start on the material that we reviewed. 34% of the students scored perfectly. They most common mistake was on the first part (not making next in the new node refer to the node containing 5. On the last part, some students drew an arrow to the variable labeled X, but that is not an object. Typically changing the correct instance variables was 1 point, and making it refer to the correct node was 1 point.

• Problem 2: Students attempting this problem scored an average of 71%. 20% of the students scored perfectly. To get full points you needed to write correctly the header, base cases of either reference null, compare .value instances, do one recursive call via .next, and have no minor mistakes (e.g., didn't forget return, etc.

• Problem 3: Students attempting this problem scored an average of 72%. 8% of the students scored perfectly. Almost everyone forgot to check for a case of a one-node list, in which case front and not the last .next reference is set to null. To get full points you needed to write correctly the header, test both special case (empty and 1 node list), loop to stop one before the end of the list, and store null in its .next instance variable.

• Problem 4: Students attempting this problem scored an average of 79% the second highest on the exam. Only 3% of the students scored perfectly: Michael Sevilla, Aamir Shah, and Jesse Joseph. Many more students got the code correct, but not the big-O analysis (many gave the complexity for a HashMap not an ArrayMap; others forget that many operations are O(N) for Array versions of Map and Set). An elegant solution, shorter than mine but a bit more inefficient was listed by a few students:

  if (!m.contains(key)
    m.put(key, new ArraySet());
  m.get(key).add(value);

• Problem 5: Students attempting this problem scored an average of 55% tied for the second worst on the exam. 8% of the students scored perfectly (same as for problem 3, which had a 72% average), but 1/3 of the students didn't attempt to answer this problem. The key was using some kind of Stack, which is loaded during construction and unloaded (one value at a time) via remove. This is similar to how the iterator for the HeapPriorityQueue worked. Declaring the right instance variable and writing the constructor, and two methods were each worth 4 points.

• Problem 6: Students attempting this problem scored an average of 65%. No one scored perfectly: there were so many parts, it was easy to mess-up on something small. Nicholas Olsen was the top scorer at 28.5 of 30. In part (a), some students had difficulty thinking about i=i+2 and i=i*2. In part (b), some students didn't say hasing was O(1) and others said computing .size was O(N) but we've seen how such a value is cached and returned in O(1). Parts (1-2) were worth 5 points and (3-4) worth 3 points; if you got the main idea but didn't use Omega/Theta notation you could get 2 of these three points. In part (c), I was kind of surprised at the mistakes made since this problem (or one very much like it) was on one of the quizzes). In part (d), there were all sorts of small mistakes: note that you can delete a random position in an unordered array by replacing it with the value at the end, which is O(1); also the most "pathological" and AVL tree can get is 2 times the optimal height, so searching such an AVL tree is still O(Log₂ N)

• Problem 7: Students attempting this problem scored an average of 65%. 24% of the students scored perfectly. To get full points you needed to write correctly the header, single base case (an empty tree), and the recursive case which used new, .value, and two recursive calls to the subtree.

• Problem 8: Students attempting this problem scored an average of 63%. 13% of the students scored perfectly. This is the English version of a problem you did on one of the quizzes, but few students could state the three cases (leaf, internal with one child, internal with two children) and how they were solved.

• Problem 9: Students attempting this problem scored an average of 75% third highest on the exam. 43% of the students scored perfectly. While these scores were good, I expected even better give that these problems were on a quiz and a major part of Programming Assignment #3.

• Problem 10: Students attempting this problem scored an average of 57%. 6% of the students scored perfectly. The split between Problem #9 and this problem was interesting. Students got 5 points for writing a loop with a test and return, and more points for having the right bounds on the loop, not accessing any values outside of the heap, and using the right mapping. Notice that if you follow the English, and look at every node but the root and compare it to its parent, it was easier than looking at every node (including the root) and comparing it to its children -if they existed: every node by the root has a parent, so the code was much simpler.

• Problem 11: Students attempting this problem scored an average of 70%. Only two students, Andrew Beier and Collins Chang scored perfectly. This problem was like the AVL tree problem on the quiz, but I also asked you to show a rotation (the one needed in the next part) and you had to know that while removal can require O(Log₂ N) rotations, adding requires at most one.

• Problem 12: Students attempting this problem scored an average of 55% tied for the second worst on the exam. Five students, Daniel Tozaki, Jonathan Fuentes, Suraj Mehta, Allen Luo, and Shawn Merrill scored perfectly. For part (a) most students drew something like a hash table (you got 4 points for drawing an array labeled 0-4 with buckets leading to some values in a linked list. Getting the right values in the right buckets (being able to do hashing and compression) was worth 2 points. Computing the load factor correctly (many students wrote 4/5, since 4/5 of the buckets stored values) and knowing that Java keeps the load factor < 1 were each worth 1 point. For part (b) you needed to say that M grows (with N) to get full credit. If you had a reasonable mathematical argument about M vs. N you could get 3 of 4 points max. Just writing O(N / N/2) was not enough; also some students wrote M = N/M which made little sense (M^2 = N?).

• Problem 13: Students attempting this problem scored an average of 37% the lowest on the exam. Only one student, Austin Liou, scored perfectly. These were "stand back and take in the big picture" questions, and I graded them toughly: there were specific points I was looking for. The first concerned the limits of complexity analysis, the second the reasons behind breaking the world into data types and data structures.

After I return your graded work in class on Tuesday, please download the Grades(zipped .xls file) from the course web and ensure that I have computed and entered your grade correctly (I'll be entering thousands of grades for students in my course this quarter, so even if I'm 99% accurate, I'll incorrectly compute/record some grades). Note that all grades are recorded as integral values: I always round up (e.g., an exam score of 22.5 is recorded as 23).

If you do not pick up your returned work in class, you should pick it up during my office hours ASAP; I don't like keeping student exams: it makes my office messier, and you don't get the benefit of the feedback I wrote on the quiz.

If you believe that there is a problem with grading the quiz, please bring it to my office hours. It is a win-win situation. If I did grade it incorrectly, I want to correct my mistake and give you the points you deserve. If I did not grade it incorrectly, then you are still confused about why your answer is wrong, and by coming by we can clear up the problem quickly.

Here is a quick analysis of the quiz.

• Problem #1: Many students got full credit for this problem; those who didn't often lost a substantial number of points for multiple mistakes.

• Problem #2: For those students who got the idea of "separate cases for the separate operators" most got full or close to full credit. Students who left out the base case of "value" lost 1 point; I also deducted .5 points for specifying the wrong complexity class. Some students wrote this method non-static, as if it were written in the ExpTN class: so long as their answer was correct and consistent with this approach (and no other errors), they should have received full credit.

• Problem #3: This problem was difficult to grade, because there are many logically correct ways to do this problem. The most common mistake was not changing the .parent reference for the node labelled "A" (worth 1 point). Also, some students lost many points for not changing either the left or right reference in "C" to its correct grandhild (or null), or changing too many: students wrote that if "B" had no children, to change both "C"'s left and right to null (only one should be changed, the one referring to "B").

• Problem #4: A very mixed bag here: many students got near 10 points, but then many students got near 6-7 points. Understanding that the values had to be rehashed in the larger table was worth 4 points: many students just copied the references from the old table to the new table (this was something I discussed in class and is the essence of doubling a hash table). Generally, the solution required two nested loops: one for going to each bucket, one for processing each chain in that bucket (rehashing each value found there). Student scoring around 8 probably had the idea of rehashing but not quite working code. Finally, a few students used "add" but forget to reset countObjects (which "add" increments), which was a .5 point deduction.

You can find a detailed spreadsheet of how we graded your programs in Program 2 Grading. There are comments wherever X's are placed (e.g., some students used lists where the specification was sets and had duplicate values). The number of points for each part was Sentence 20, Reverse 16, Reachable 10, FA 16, NDFA 10, WordGenerator 8. Generally students scored best to worst: Sentence, Reverse, FA, NDFA, Reachable, and WordGenerator (and I set the points for each part following this same distribution).

Generally 1/2 credit was given for reading/printing the information correctly, half for "solving" the problem related to the data (on those problesm with 3 data files, on each part I gave 50% for the first, and 25% each for the 2nd and 3d). Some solutions to FA or NDFA hard-wired in the automaton in the problem; they did not write code that read in the description of the machine from a file and simulate it on an arbitrary input read from another file.

Only about 8 students did not reach the C level (70%) and of these, two were very close to that level.

IMPORTANT If you believe that we recorded one or more tests in error (we used the same tests you downloaded for the project), please email your TA (see the fact sheet for the assignment of Labs to TAs) and tell him what the differences are. He will then rerun the test, possibly asking you for more information, or running it with you at lab. If there is a difference, he will email me a revised summary about your program, and cc a copy to you. I will update the grades spreadsheet as appropriate.

After I return your graded work in class on Tuesday, please download the Grades(zipped .xls file) from the course web and ensure that I have computed and entered your grade correctly (I'll be entering thousands of grades for students in my course this quarter, so even if I'm 99% accurate, I'll incorrectly compute/record some grades). Note that all grades are recorded as integral values: I always round up (e.g., an exam score of 22.5 is recorded as 23).

If you do not pick up your returned work in class, you should pick it up during my office hours ASAP; I don't like keeping student exams: it makes my office messier, and you don't get the benefit of the feedback I wrote on the quiz.

If you believe that there is a problem with grading the quiz, please bring it to my office hours. It is a win-win situation. If I did grade it incorrectly, I want to correct my mistake and give you the points you deserve. If I did not grade it incorrectly, then you are still confused about why your answer is wrong, and by coming by we can clear up the problem quickly.

Here is a quick analysis of the quiz.

• Problem #1: Most students did well on these problems. Mistakes tended to be minor ones, as opposed to big conceptual ones, although some students had problems applying the algorithms to some subtrees.

• Problem #2: Solutions here were generally good, but many students did not know (or know how to follow) the add/remove algorithms. It is NOT CORRECT for the first part to build some tree that is a heap (one could put the values, low to high, into the tree using a breadth-first traversal). Instead, one has to follow the algorithm for adding. The same holds true for removal: the tree must be restructured according to the algorithm. Please not that when I said "draw a box around nodes that are removed" I DIDN'T MEAN "...values that are removed"; of course the values at the root of the tree are removed, but I wanted and indication of which NODES got removed from the trees: the ones on the right of the deepest depth.

• Problem #3: Solutions here were generally good, but many students lost points on one thing or another. A surprising number of students filled in depths instead of heights for the first part (with the root as 0, its children as 1, its grandchildren as 2 etc.). For part (b) lots if students said that node 38 could be removed, but that makes the root not satisfy the AVL property; others said 2 (but that makes 4" not satisfy the property) and still other specified "non leaf" nodes. Most students got part (c) corrrect: there were many correct answers.

  A bit fewer than 1/2 of the students didn't do a correct rotation after adding 6. Again, you cannot just write a tree that has the new node and satisfies the AVL property: you need to do the correct rotation. The node that is unbalanced is 4, so the three nodes appearing in the rotation are 4, 7, and 5 (some students rotated 7, 5, and 6). Generally I took off -2 for an incorrect rotation that still produced an AVL tree (so it looked "right"), and -3 if the rotation was incorrect, and it also produced a non-AVL tree (which should have been a tipoff you did something wrong).

• Problem #4: A very mixed bag here. I should have specified whether this method could be called with and empty NTN (so I didn't count off for either assumption). Also, I should ahave specified whether a node with no children has children refer to null or just an empty set (so I didn't count off for either assumption). My solution allows t to be null but assumes a leaf has a Set for children but it is empty.

  There were many solutions that had a for loop with a return on the inside: such a loop iterates once, executes the return, and doesn't iterate any more. Other solutions called addUp recursively, but did nothing with the int value it returned (it needs to be accumulated in a sum). Some solutions included adding t.value in the loop, which added this value multiple (too many) times into the sum.

  Finally, I did not grade the traversal spot (answers were all over the board). The answer as supposed to depend on where you used t.value, the information stored at the parent: if you put t.value into the sum before adding-in the children's values, that would be preorder. if you returned the sum of the children plus t.value at the end, that would be postorder.

After I return your graded work in class on Tuesday, please download the Grades(zipped .xls file) from the course web and ensure that I have computed and entered your grade correctly (I'll be entering thousands of grades for students in my course this quarter, so even if I'm 99% accurate, I'll incorrectly compute/record some grades). Note that all grades are recorded as integral values: I always round up (e.g., an exam score of 22.5 is recorded as 23).

If you do not pick up your returned work in class, you should pick it up during my office hours ASAP; I don't like keeping student exams: it makes my office messier, and you don't get the benefit of the feedback I wrote on the quiz.

If you believe that there is a problem with grading the quiz, please bring it to my office hours. It is a win-win situation. If I did grade it incorrectly, I want to correct my mistake and give you the points you deserve. If I did not grade it incorrectly, then you are still confused about why your answer is wrong, and by coming by we can clear up the problem quickly.

Here is a quick analysis of the quiz.

• Problem #1: Most students did well on these problems. To get full credit you needed to state some reason, in English or big-O notation, leading to your answer. For the last part, I wanted explicit mention of the sum: 0+1+2+...+n-1 (as I required in Quiz #2, question 3 part a): too many students still don't know the exact form of this sum.

• Problem #2: Again, most students did well on these problems. Some are still multiplying complexities (first part); on the second part, in the worst case, the test is true so method m2 will execute (a good question might be what is the complexity class of "test"); on the first part, multiplication is important. Some students rewrote O(N^2 Log N) as O(N^2) which is not correct: multiplicative non-costants (Log N) remain in big-O notation.

• Problem #3: Most students at least lost 1 point here: the whole reason to use a header node is to avoid the special if, and reduce the code just to the loop. The initialization, body, and post processing of the loop were the same as in the code I told you too look at. To get full credit on part b, you needed to discuss "remove". I was liberal, giving full credit to any discussion of remove, but in fact it is only the remove in the iterator that is improved.

• Problem #4: Most students got the original tree correct; those who drew it incorrectly mostly messed up with nodes 45 (added first) and then 42. Most, but not everyone, got the delete correct as well, but some students restructed the tree (some with correct order properties, some without) in some way not connected to any delete/remove method we discussed.

• Problem #5: Some students got full credit here, but the majority didn't: there were lots of 3 point solutions. Some didn't use null as a base case (when in doubt, try null); some didn't compare the value to t.value; some didn't do a recursive call on the left AND right subtrees (with the same second argument); some did a recursive call but didn't pay attention to the boolean results returned from such recursive calls. Each of these possibilies was about a 1 point deduction.

• Problem #6: Students scored similarly to problem #5; again there were there were lots of 3 point solutions.. Some didn't use null as a base case (when in doubt, try null); some didn't call allLess AND all greater on the appropriate subtrees with the appropriate value; some didn't do a recursive call on isBST with the left AND right subtrees; some did a recursive call but didn't pay attention to the boolean results returned from such recursive calls. Each of these possibilies was about a 1 point deduction.

You can find a detailed spreadsheet of how we graded your programs in Program 1 Grading. The number of points for each class (not counting remove in the iterator) was 26 for the stack, 25 for the queue, and 25 for the priority queue. Each X means a failure; there were 11 tests in each category, each worth the same amount. The remove in the iterators were worth 2 points for the stack, 1 point for the queue, and 1 point for the priority queue.

Scoring under ~50 might indicate a lack of understanding of something important (which you might learn from looking at my solution, or in other ways); I conjecture most of these students were not able to transfer knowledge effectively from the stack implementation to the other classes. Scoring under ~25 might indicate that you did not seek adequate help on this assignment; I conjecture most of these students were not able to debug even the stack implementation.

Based on the numbers for speeds and sizes, I decided to base the entire grade on correctness (the points above add up to 80), although we did record numbers for sizes and approximate numbers for speeds in the spreadsheet.

IMPORTANT If you believe that we recorded one or more tests in error (we used the same tests you downloaded for the project), please email your TA (see the fact sheet for the assignment of Labs to TAs) and tell him what the differences are. He will then rerun the test. If there is a difference, he will email me a revised summary about your program, and cc a copy to you. I will update the grades spreadsheet as appropriate.

After I return your graded work in class on Tuesday, please download the Grades(zipped .xls file) from the course web and ensure that I have computed and entered your grade correctly (I'll be entering thousands of grades for students in my course this quarter, so even if I'm 99% accurate, I'll incorrectly compute/record some grades). Note that all grades are recorded as integral values: I always round up (e.g., an exam score of 22.5 is recorded as 23).

If you do not pick up your returned work in class, you should pick it up during my office hours ASAP; I don't like keeping student exams: it makes my office messier, and you don't get the benefit of the feedback I wrote on the quiz.

If you believe that there is a problem with grading the quiz, please bring it to my office hours. It is a win-win situation. If I did grade it incorrectly, I want to correct my mistake and give you the points you deserve. If I did not grade it incorrectly, then you are still confused about why your answer is wrong, and by coming by we can clear up the problem quickly.

Here is a quick analysis of the quiz.

• Problem #1: Many students got the main idea for this code: iterating through the map using the .get method (the output of one get became the input for the next call), and adding each result to an array; there were all sorts of opportunities for small errors in such solutions. Some students tried to solved the problem by iterating through the entries in the map, but most of the times these solutions assumed a certain order for the iterator, which cannot be guaranteed.

• Problem #2: Again, many students did well writing this code. The biggest common mistake was using retainAll on one of the parameter sets (either directly or via sharing): you need to use a copy of one set, using either shallowCopy or explicitly constructing and initializing a copy of one of the sets. Students solving this problem using a correct and simple version of iterators received a 1/2 point deduction (more if the iterators were complicated or wrong).

• Problem #3: Answers were all across the board here. Each part was 1 point. In part a2 you needed to show a sum (N-1)+(N-2)+...; in part b2 you needed to say sorting was O(N Log₂ N), searching for equals adjacent pairs was O(N) and their sum was O(N Log₂ N)

• Problem #4: Answers were all across the board here. I wanted a formula for T(N) with c as a calculated number (and some indication of how it was to be computed). Then, I wanted you to plug in a different number an recalculate. Since O(N Log₂ N) is a bit faster growing than linear, increasing the input by a factor of 1,000 should have increased the fime by a bit more than a factor of 1,000 (actually, double this amount).

• Problem #5: Wanted two parts to answer this problem: first, some indication that for large N, m1 was faster (some students got this backwards); second, solve or indicate how to solve for finding where the two curves cross (m2 is faster for smaller sizes, but m1 is faster for larger).

• Problem #6: I was strict on this problem. Just saying it would "slow down" the method was not enough. I wanted an indication it would change the complexity class from O(Log₂ N) to O(N).

• Problem #7: The first part was worth 1 pt; the last two worth 1.5 pts each. Note that each doubling in column 1 approximately doubled the time; each doubling in column 2 approximately quadrupled the the time (the signature of quadratic complexity); finally, each doubling in column 3 approxinmately added 20 milliseconds to the time (the signature of logarithmic complexity.

There were six students with one-digit scores; they should see me immediately, so that we can discuss whether or not they should be in this course. In schools on the quarter system, I advocate students who did not perform well in a previous course, to repeat that course. This is often tough advice to swallow, but you really need a mastery of ICS-22 to learn what you need to learn (and perform well) in ICS-23, and spending an extra quarter to obtain this mastery is well worth it. Material similar to this quiz will be on the written exams.

After I return your graded work in class on Tuesday, please download the Grades(zipped .xls file) from the course web and ensure that I have computed and entered your grade correctly (I'll be entering thousands of grades for students in my course this quarter, so even if I'm 99% accurate, I'll incorrectly compute/record some grades). Note that all grades are recorded as integral values: I always round up (e.g., an exam score of 22.5 is recorded as 23).

If you do not pick up your returned work in class, you should pick it up during my office hours ASAP; I don't like keeping student exams: it makes my office messier, and you don't get the benefit of the feedback I wrote on the quiz.

If you believe that there is a problem with grading the quiz, please bring it to my office hours. It is a win-win situation. If I did grade it incorrectly, I want to correct my mistake and give you the points you deserve. If I did not grade it incorrectly, then you are still confused about why your answer is wrong, and by coming by we can clear up the problem quickly.

Here is a quick analysis of the quiz.

• Problem #1: Most students did well writing this class. Common problems included not writing a constructor with one parameter and/or not declaring the right instance variables (including copying the parameter to one instance variable); not using the type Decision for the constructor's parameter and its matching instance variable (instead using Object or Prefix); not declaring all the instance variables private; not writing reset and/or not calling it in the constructor: note that the String should be reinitialzed to "" not null, and the Decision> should not be reset. not calling the .isOK method correctly in tryCat; incrementing the count conditionally: it should be incremented unconditionally, whenever tryCat is called; a minor issue, but I took off .5 for it, your if statements should NOT include ==true as in if (prefix.isOK(x) == true) because writing if (prefix.isOK(x)) means the same thing.

• Problem #2: Again, most students did well writing this class. Common problems included not specifying that the class implements Decisionwriting a constructor; making the parameter to isOK a String (it must be an Object to match the interface); not casting the parameter from Object to String (calling toString is not quite the right thing to do here); calling .contains instead of .startsWith; a minor issue, but I took off .5 for it, you should not have an if statement that returns either true or false, but instead just return the boolean condition of the if: dont' write if (test.startsWith(prefix)) return true; else return false; instead write just return test.startsWith(prefix);

• Problem #3: This problem had the widest range of answers and points. Some students knew exacty what I wanted in terms of the diagrams, but some seemed to have little idea of what I wanted. Many also either added extra references or didn't show new ones (or cross out old ones). Some students showed references the wrong way, references to variables (not objects) and other mistakes that showed a fundamentally misunderstanding related to hand simulation of linked list code. So there was a wide range of scores here. Again, students leaving ICS-23 should be able to debug their linked list code correctly, by doing such hand simulations to find errors.

Specifically, read the handout on Java and Eclipse (Download/Installation Instructions) for details. Please contact me if you are having trouble, as I will assume every has successfully downloaded and installed this software by the end of the first week of classes.

IMPORTANT: Students should also download and install the Barr-Courier Font on their computers. Again, explore the Online Resources link (see Miscellaneous, near the bottom of the page).

I will never remove a message from this page, although a subsequent message may "cancel" a previous one; in such a case, I'll refer to the number of a canceled message in the message that cancels it.

Expect a few new messages to be posted here each week.

Read this page, along with the the course email discussions, daily.