Announcements

Remember that an important part of every assignment is examining my solution and compare it to yours; it gives you another chance to learn something.

You can find a detailed spreadsheet of how we graded your programs in Program 5 Grading. Incorrect Junit tests are marked as either RX (a red-flag: exception thrown) or RX (blue-flag: assertion failed). HashGraph was worth 40 points (about 66%) of this assignment, and Dijkstra was worth 20 points (about 33%).

Generally each of the Junit tests was worth the same amount.

IMPORTANT If you believe that we recorded one or more JUnit tests in error, please email the TA (see the fact sheet; also cc a copy to me) and tell him what you think the differences are. Email Naveen if the UCInetID of the submitter was between aamendez - kan1; email Yan if the UCInetID of the submitter was betwen kelvil1 - zsimjee.

Look at your returned work carefully. Generally scoring 20 or over is good for quiz. Scoring under 16 might indicate a lack of understanding of something important (which you might learn from looking at my solution, or in other ways). If your score was below 16, you might want to review this quiz with me or your TA during office/consulting hours; certainly you should compare your solution to mine. Material similar to this quiz will be on the written exams.

After I return your graded work in class on Wednesday, 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 a thousand 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 (which is sometimes minimal, because I do publish solutions and expect you to read them)..

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. Overall, I expected students to do very well on the hand problems, and get the HashEquivalence class working (but I expected lots of small improvements were possible with this code).

• Problem #1: Most students did well on this problem. Only a few showed an order that did not follow the algorithm; some repeated some same letter in the same position for their two orders. I expected students to state, re-draw or circle the nodes that formed a cycle (and node C, which was reachable from the cycle). Finally, to get full credit (one point) your explanation should say that none of the unprocessed nodes had an in-degree of 0, or say that these nodes formed a cycle.

• Problem #2: Most students got this part correct. Some student left-out the values on the edges (1 point deduction). Some students had incorrect edges in the minimum spanning tree (-2 for each) wrong edge. A few students seemed to be following a strange algorithm for computing minimum spanning trees, getting most edges wrong.

• Problem #3: Some students did very well on this problem; other students struggled: either their code didn't compile, didn't run the test case correctly, or threw exceptions or produced wrong results when running the EmpiricalComplexityClass, which acted like a large scale test. For those student who had code that did not work, I took off up to the full 15 points, depending on whether any of the code was relevant. For example a few students didn't check whether the roots of the values to merge were the same (in this special case, nothing is to be done); instead, they updated the parentMap (not a problem, the root already refers to itself) but then updated the rootSizeMap of one to the combined size and then removed the other: but the roots are the same so it updated the size of that root and then removed that root. Subsequent calls to .get on that root would return null rather than a size.

  For code that was incorrect, see the grading key for more details: the code could still work, but not do all the things that it was supposed to; for example, not remove the root from the smaller tree from the rootSizeMap: that doesn't affect correctness but it doesn't implement the algorithm the way that it was specified.

  Another commong problem was compressToRoot not compressing the node e that it was called on to refer to the root: it depends on the code before/inside the loop to reach the root.

  For the last question, most students said the complexity class was linear, but most measurements showed a ratio that was always > 2 by an extra 10%-20%. I would describe this as a complexity that is a bit bigger than linear, something like O(N Log2 N) or as we discussed in class O(N Log2* N): some slowly growing function times O(N). Depending on your actual number, I took off .5 if I thought the ratio was always greater than 2: I think only a handful of students had their grade lowered, because I rounded half-points up and there were few other places I took off half points.

Look at your returned work carefully. Generally scoring 20 or over is good for quiz. Scoring under 16 might indicate a lack of understanding of something important (which you might learn from looking at my solution, or in other ways). If your score was below 16, you might want to review this quiz with me or your TA during office/consulting hours; certainly you should compare your solution to mine. Material similar to this quiz will be on the written exams.

After I return your graded work in class on Wednesday, 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 a thousand 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 (which is sometimes minimal, because I do publish solutions and expect you to read them)..

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. Overall, I expected students to get all these methods working, given that I provided the pseudocode; yes, there are all sorts of bugs that can arise when getting all the details to work, but I expected you to be able to debug your code. The result was that I awarded few points for methods that failed the tests, even if they could be easily fixed (because students couldn't figure out the easy fixes).

• Problem #1: Some students did not accurately follow the algorithm. There is a distinctive pattern that shows what values/nodes were tested: after previously stopping at a level (or at the very beginning) it goes down one level and compares against the node(s) afterwards (not the one it just came down to). Many students incorrectly showed access to -inf (it is never checked) and 35 and 40 (under the top accesses to 35 and 40); almost all +inf were tested. Some students showed accesses as if the bottom level was exclusively searched. Also, some students had the wrong number of 52s, or didn't link up these values vertically. So, it is not totally intuitive; look at my solution, and the pseudocode to try to understand the exact pattern. When it finds the right location on the bottom level, it puts in a new node with the required value, and puts three new values/nodes at levels going upwards (each coin flip of heads means to put it at the next upper level).

• Problem #2: Many students got this part correct. Each line in the array code needs to be replaced with the equivalent line for linked lists (switching from and array and its index cursor to a linked list and its reference cursor. I took off points for translating the for loops into while loops (and there was no reason to rewrite this method recursively): the for loops simple and elegant. Some students wrote code that looked like some kind of insertionSort code (it sorted) but it didn't look like the Java code I supplied: for example, swapping values whenever a new smallest value was found, instead of waiting until the end to swap it.

• Problem #3: This was probably the hardest of the methods to get right. I wanted just a single for loop; each iteration through the loop would put one more value (the remaining smallest one) into the temp array, based on one of four simple tests. When there were no more values to put in, the loop would exit and you would copy back from the temp array to the original one in all the appropriate indexes.

  A few students did not follow the algorithm at all; others tried to follow the algorithm but failed to do so correctly. Common problems were declaring an array of an incorrect size (or accessing its indices incorrectly regardless of the size), not testing the boundary conditions correctly (some tested leftIndex == leftHigh instead of leftIndex > leftHigh), or not copying back the information into the a array correctly. I took off points for overly complicated tests/code and sometimes for not using the prefix/postfix ++ operator as Java/C/C++ programmers would (saving some lines of code too).

• Problem #4: Fewer students got this part correct than Problem #2, but more got it correct than Problem #3. Some students forget that after allocating the array of queues, you needed to put a newly constructed (and empty) queue into each array index. Also, some students didn't understand how to use selectDigit: it needed to be called with a second parameter of 1, 10, 100, etc. (not 1, 2, 3, etc.): here is a case where the index of a loop is updated by i = i * 10. I took off points for not declaring Queue<Integer> and instead casting to Integer later, and for repeatedly computing 10^1, 10^2, etc.: the places should be computing in a simple for loop as for (int place=1; place<= 100000; place*=10) ...

Remember that an important part of every assignment is examining my solution and compare it to yours; it gives you another chance to learn something.

You can find a detailed spreadsheet of how we graded your programs in Program 4 Grading. Incorrect Junit tests are marked as either RX (a red-flag: exception thrown) or RX (blue-flag: assertion failed). I counted HashMap as worth 42 of 50 points, SetFromMap as worth 12 points, and SkipList as worth 6 points.

Generally each of the Junit tests was worth the same amount, along with writing in the correct complexity classes for the operations in the comments at the front of the .java class files. Note a special column for whether the HashMap worked with SetFromMap and used a trailer-list. I abbreviated the SkipListSet test to one number.

IMPORTANT If you believe that we recorded one or more JUnit tests in error, please email the TA (Sam) (see the fact sheet; also cc a copy to me) and tell him what you think the differences are. He will then rerun the test, possibly asking you for more information if there is still confusion, or running it with you at lab meeting. 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.

About 42% of the students scored an A; another 18% scored a B (so about 60% passed at the B or above level). I have posted in our EEE dropbox a download with everyone's submitted programs, so you can download your work and better interpret my gradesheets, which I will return in class on Monday. Of course, you should also look at my solution, which is also in the EEE dropbox.

There were many different mistakes made by students writing this class. Here are some comments on the solutions: with 175 students taking this exam there were lots of different kinds of problems in incorrect solutions. Recall that at most I could take off at most 5 points (10%) for suboptimal "Java use"; so if your solution was correct, you would at worst score >= 90%.

• Instance Variable and Constructor
  • Most student allocated the trailer node in the constructor, when it is best to allocated it in the instance variable declaration for bag, but I did not take off points for its placement.
  • Some, but few, students did not allocate the trailer at all and just set bag to null; fewer still made bag refer to two linked node (header and trailer?).
  • Some students declared extra instance variable (e.g., objectCount), which were prohibited in the writeup and comments.

• findNode
  • Most students wrote this method correctly (using .equals, not ==) although some students wrote code that changed bag instead of a locally-declared cursor variable, losing the reference to the start of the list.
  • Some students scanned too far (checking the values stored in the trailer node); and, a few students returned a reference to the trailer instead of null if the value was not stored in the linked list (which contradicts the specifications, and makes checking this value more complicated in later code).
  • Some students wrote extra unneeded checks before the looping code; others returned a value of type E instead of LN<E>.
  • A for loop is the simplest, most natural way to write this method; there is no reason to check for an empty bag: just let the for loop do its job.

• add
  • There were many opportunities for errors and just overly complicated code in this method: some students did not call findNode to get things started, at which point the code should decide to increment some count or put a new LN<E> at the front.
  • Some students scanned the list twice, calling combinations of contains and findNode.
  • Some students wrote code that changed bag instead of a locally-declared cursor variable, losing the reference to the start of the list.

• getSize
  • Most students wrote this method correctly or close to correctly; some students incorrectly analyzed the trailer node, although most students initialized its count as 0, so the right answer was calculated even if the loop scanned too far.
  • Some students wrote code that changed bag instead of a locally-declared cursor variable, losing the reference to the start of the list.
  • A for loop is the simplest, most natural way to write this method; += is the right operator increment here; there is no reason to check for an empty bag: just let the for loop do its job.

• getUniqueSize
  • Most students wrote this method correctly or close to correctly; some students incorrectly analyzed the trailer node, which computed a count that was 1 too high, at which point they initialized the count to -1 to correct for this, which made the code very confusing.
  • Some students wrote code that changed bag instead of a locally-declared cursor variable, losing the reference to the start of the list.
  • Some students misunderstood what I wanted here and counted the number of list nodes whose count was 1.
  • A for loop is the simplest, most natural way to write this method; ++ is the right increment operator here; there is no reason to check for an empty bag: just let the for loop do its job.

• clear
  • Most students wrote this method correctly, either by storing a new trailer node into bag (simplest) or setting the node bag referred to (it is guaranteed to refer to some node, maybe already the trailer) so that it stored null for value and next, and stored 0 for count (fastest: no allocation).

• contains
  • Most students wrote this method correctly or close to correctly. The best solution is just one line (no if/else) that calls findNode and returns whether or not the result is not null; using a conditional expression here is overkill.

• times
  • Most students wrote this method correctly or close to correctly. The best solution is to call and store the value returned by findNode; then, if it is null return 0 and if it is non-null return the count in the node it refers to.
  • Some students scanned the list twice, calling combinations of contains and findNode.

• remove
  • Many students had correct solutions here, but there were many possibilities for incorrect or poor solutions.
  • In a trailer-node list, you can easily find the node to remove with findNode (if none is found, the method immediately returns false), decrement its count, and if it reaches 0 remove the entire node by copying ALL 3 of its instance variables from the node that follows it (guaranteed to exist because we are processing trailer-node lists)
  • A few wrote complicated code to rescan the list for removal, using a ghost reference or looking ahead, which overly complicated this method and often failed to work in some cases; other students had a subtle bug by copying the value and next fields, but not count.
  • Some students scanned the list twice, calling combinations of contains and findNode.

• random
  • Some students didn't check for an empty list correctly (not bag==null since it is a trailer-node list); others did not throw a IllegalStateException (the bag is in an illegal state - no values - to call this argumentless method; also see the results printed by Autotest); and others did not include a message showing the class, method, and cause of the failure.
  • Some students didn't use the random number generator in a way that would generate each possibility with equal probability. Note that casting has a higer precedence than multiplication, so (int)Math.random()*getUnqiqueSize() first converts the number returned by Math.random() to an int (which will ALWAYS be 0) and only then multiplies, so the result is always 0, which will always return the first value instead of a random one.
  • Some students didn't write a loop that skipped the correct number of values.

Remember that the Final written exam will be about 1/2 on the material covered on the midterm and 1/2 on the material that we cover during the remaining part of the quarter (mostly hashing, sorting, string processing, graphs, and details on computer memory and how it affects some data structures and their algorithnms). As I have discussed in class, if you do better on the final exam than you did on the midterm, I will use your grade from the final exam for your midterm grade. The point here is for you not to feel anchored by your midterm grades; if your grasp of this material improves, so will your grade.

The class average for the midterm was about 59% (last time 59%) and the median grade was 58% (last time 58%), so that is an exact match. Because the class average was below 75%, the grade sheet will automatically add in about 25 "normalization" points (about 16%) to everyone's score when tallying your final grade. Note that I entered your "real" score (from you midterm paper) in the spreadsheet; the spreadsheet will automatically bump it by the normalization points when computing your 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 168 points out of 160, so you could have lost partial credit on any problem and still scored near 100% on the exam. The highest score (un-normalized) on the exam was 96% (last year it was 93%). About 20% of the students scored 75% or above (which when normalized means those student scored the equivalent of an A on the exam); about 19% of the students scored 65% or above (the equivalent of a B). Last time I taught this course 22% scored an A on the exam and 19% scored a B after normalization: so, this quarter there were 2% fewer As and the same percentage of Bs. Thus, the scores represented by these curves were very close. See the Exams tab in the spreadsheet for a histogram of all the scores.

• Problem 1: Students attempting this problem scored an average of 62%; 2% of the students (4) scored perfectly: Pablo Kang, Jonathan Mak, Joel Ruckle, and Joseph Than. This problem was designed to test whether you had a good grasp of thinking about and using collection classes: it used Maps and Sets. The code was fairly straightforward from the problem description and my algorithmic hints: the Set in the first part was used as the main data structure in the second part (building the Map; once it loaded the keys from the Map). Then the Map was used simply (a get+add) to complete the graph, inside two nested loops for finding each edge: a source node and destination node.

• Problem 2: Students attempting this problem scored an average of 51%. 2% of students scored perfectly: Craig Steinke, Maymunah Khafateh, and Kuan Tseng. Most students did very well on the first part and poorly on the second part. We did talk in class about building a list in order by doing caching of the last node and extending it (I implemented my shallowCopy methods this way in Programming Assignment #3). The recursive copy had a wide variety of scores: some wrote it simply and correctly with the l==null test; other used l.next==null which was legal for a header list but made things more complicated: you must return new LN(l.value,null) not just null or l.

• Problem 3: Students attempting this problem (with many parts) scored an average of 51%. No students scored perfectly (although four students scored above 34 pt): Alex Dixon, Brandon Park, Craig Steinke, and Zachary Kloock. In part a, most students did a reasonable job: there were lots of parts so it was easy to make afew small mistakes. In part b there were some but not many correct answers: you needed to point out Log₁₀ 2 as a constant. Part c was just like a question on Quiz #4: in the first column when N doubled, time went up by a factor of 8, which is O(N^3) (more than O(N^2), which quadruples); in the second column the time went up by more than a factor of 2 consistently, matching O(N Log₂ N), but I have 50% credit for writing just linear; the last one was just O(1); some students choose incorrectly. In part d, many students got full credit, but there were many possible places to make small mistakes: some students did not solve for the constants in the formulas, some are still not approximating logarithms correct, some didn't deal with the powers of 10 correctly, and some just didn't simplify their answers. In part e, few students got full credit for writing each complexity class and the complexity class for the entire task (many forgot/omitted the last part): note that addition to both the linked list priority queue and linked list set is O(N) (because of searching for the place to put the value in priority queues, and searching for duplicates in sets), and fast sorting is O(N log₂ N). Finally, few students got any credit for part f: you needed to say the solution was in the optimal complexity class (none could be in a lower complexity class by the lower-bound proof) but that another algorithm in that same complexity class might have a smaller constant.

• Problem 4: Students attempting this problem scored an average of 58%. 6% (13) scored perfectly. The first part of the problem (filling in the bounds for nodes in the tree) was supposed to prime you for writing the algorithm: how the min and max bounds (parameters to the method) changed as the method recurred. Some students always used the same minimum and maximum in each call; others did not check the value of the node against the required minimum and maximum; a few did not recur at all.

• Problem 5: Students attempting this problem scored an average of 84% (the highest by far on the midterm). 46% of the students (83) scored perfectly. If you did not show a perfect answer, you lost many points. While most students did very well on this problem, there are still some who did not correctly indicate which two nodes were removed from the heap (or even removed the wrong ones, or removed them in the wrong order): I could tell from the percolations; or student did not percolate up/down the correct way (often swapping with a smaller child, but not the smallest child), sometimes even swapping with a larger child.

• Problem 6: Students attempting this problem scored an average of 61%. 13% of the students (24) scored perfectly. This problem was like the AVL tree problem on Quiz #6 (in terms of what different tasks it asked you to do) If you did not draw the trees perfectly , doing exactly the right rotation required by the algorithm, you lost many points. Some students just rearranged the nodes in the unbalanced subtree so that it had the AVL property, but did not actually do the rotation that the AVL algorithm would do. Finally, in part f I wanted you to demonstrate that you knew that you delete a node for an AVL tree like a BST: replacing it by the closest value and removing the node containing the closest value: which has at most one child, and then rebalancing if necessary.

• Problem 7: Students attempting this problem scored an average of 37% (the lowest on the exam, although maybe students had to rush through these questions at the end). One student scored perfectly: Brankdon Park. This was a "stand back and take in the big picture" question. Some student have the concept of data types and data structures backwards; more seem confused by these terms. Parts a and b should have been easy; likewise part c. Part d's answer was based on being able to remember that we select the data types needed to write programs, choosing any implementation we have, but different implementations can have better performance (also related to part c). I over-/re-viewed this material a few times in lecture, and have spoken these terms hundreds of times. Part e's answer was difficulty; almost everyone answering this question circled data type, because they thought of int as a type; but I was looking for a deeper understanding here: both int and BigInteger are two different implementations of some abstraction of mathematical integers; int with its size limitations and BigInteger with is peformance limitations; I agree this was a tough question that required an excellent grasp of data types vs. data structures.

The scores on these programs were lower than I expected: in fact, about 23 submissions did not correctly implement the majority of the HeapPriorityQueue class; students who went two weeks without making substantial progress on this class should have been asking more questions in lab of me and the TAs. The code required was intricate, but writing it should have been within the grasp of all students over a two week period. For the BSTMap 27 submissions did not correctly implement the majority of the methods. I would ask you to reassess how you plan to work on the upcoming assignments to ensure that you learn the material and can demonstrate that learning by turning in more working code on time.

Remember that an important part of every assignment is examining my solution and comparing it to yours; it gives you another chance to learn something. Of special interesting is the percolateDown method in the HeapPriorityQueue class: many student solutions were very complicated compared to my code.

You can find a detailed spreadsheet of how we graded your programs in Program 3 Grading. Incorrect Junit tests are marked as either RX (a red-flag: exception thrown) or RX (blue-flag: assertion failed). I counted HeapPriorityQueue as worth 30 of 60 points and BSTMap as worth 30 of 60 points, so each half.

Generally each of the Junit tests was worth the same amount, along with writing in the correct complexity classes for the operations in the comments at the front of the .java class files. Note a special column for whether the HeapPriorityQueue used the offline linear algorithm in it constructor with the array parameter, as specified in the writeup.

IMPORTANT If you believe that we recorded one or more JUnit tests in error, please email the TA (see the fact sheet; also cc a copy to me) and tell him what you think the differences are. He will then rerun the test, possibly asking you for more information if there is still confusion , or running it with you at lab meeting. 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.

Look at your returned work carefully. Generally scoring 20 or over is good for a quiz. Scoring under 16 might indicate a lack of understanding of something important (which you might learn from looking at my solution, or in other ways). If your score was below 16, you might want to review this quiz with me or your TA during office/consulting hours; certainly you should compare your solution to mine. Material similar to this quiz will be on the written exams.

After I return your graded work in class on Wednesday, 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 a thousand 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 (which is sometimes minimal, because I do publish solutions and expect you to read them).

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 but some seem to not understand the rotations well. Almost everyone included the heights correctly (although some students forgot to label the rotated trees correctly with heights, and others showed depths instead of heights). Most students determined which leaves could be easily removed, but some students also listed 8 (and others, even non-leaf nodes), which causes a violation of the AVL property at the root in the tree. Finally, many students applied the rotations correctly, although some rotated at the wrong node: often the resulting tree was an AVL tree, but not the one that results from the algorithm doing the rotation.

• Problem #2: Students scored from 0 to 4 (full credit) on this problem. I was looking for initializing the count at t.value, followed by a simple combination of looping and recursion that accumulated the sum (including the t.value) and returned it. Note there is no reason to check for empty or size == 0; in such cases the loop will execute 0 times.

• Problem #3: Most students did well here. Solutions needed a loop (over all the children's values) that made a recursive call (for each child); some students wrote incorrect code that returned before finishing the looping, meaning some paths were ignored (not recurred on). The code should have also checked d.isWord to determine whether the root of the DTN to process represented a word. I took off .5 points for many students who iterated over keys and did gets on each key: instead you should iterator over values - the third iterator for Maps. Note that the only thing you need to do with each child is call the recursive method; you shouldn't look at anything else in it.

• Problem #4: Most students scored around 4 on this problem. You needed to initialize a longest word and again loop over the values in the map, computing a recursive call on each child and storing the value it returns; then updating the running longest word using the stored value in some conditional statement/expression. I took off .5 points if you called the recursive method on the same value twice instead of caching it.

Look at your returned work carefully. Generally scoring 20 or over is good for a quiz. Scoring under 16 might indicate a lack of understanding of something important (which you might learn from looking at my solution, or in other ways). If your score was below 16, you might want to review this quiz with me or your TA during office/consulting hours; certainly you should compare your solution to mine. Material similar to this quiz will be on the written exams.

After I return your graded work in class on Wednesday, 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 a thousand 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 (which is sometimes minimal, because I do publish solutions and expect you to read them)..

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 here. A few students built a binary search tree with the wrong structure: not the one that added each of the numbers provided in order. Some students boxed the node containing 10 but that node stays in the tree (with a new value of 9 or 12); only the node containing 9 or 12 is removed from the tree; the node containing 10 just has its value changed. Some student did not understand the definition of height.

• Problems #2-#3: Students made lots of small and large mistakes here. Many students are still missing the base case of an empty tree, and instead checking, often multiple times, whether t.left and/or t.right was null (or even worse, not checking). Note that allLess returns false if it finds a value in the tree that is not less than the parameter; if there are no values in a tree (an empty tree) then no such value can be found, so allLess returns true when defined on an empty tree. The same conclusion could be gotten from seeing how a recursive call on a 1 node tree would force the base case to return true. The allLess method needed to check t.value against v and recursively call itself on both its left and right subtrees (with both a subtree and v passed as arguments). The isBST method needed to call allLess and allGreater to check that the subtrees were good and also recursively call itself on both its left and right subtrees, which also must be BSTs. Many students wrote code with lots of if statements or conditional expressions when logical operators would solve the problems.

• Problem #4: Most students got most parts correctly. A few students made small mistakes; some did not seem to understand the idea of a post-order traversal.

• Problem #5: There were many small errors here. Some students built the original tree incorrectly (mostly concerning problems with the structural property, just a few with the order property); more students did one or both removals incorrectly (not removing 85 first, then 90, and precolating down the right way: 85 percolates to the left of the root (where 20 was originally stored, which moves to the root on the first removal); 90 percolates to the right of the root (where 25 was originally stored, which moves to the root on the second removal).

You can find a detailed spreadsheet of how we graded your programs in Program 2 Grading. Incorrect Junit tests are marked as either RX (a red-flag: exception thrown) or RX (blue-flag: assertion failed). I counted LinkedQueue as worth 20 (of the assignment total of 60 points), HeaderLinkedPriorityQueue as worth 20, and TrailerLinkedSet as worth 20.

Generally each of the Junit tests was worth the same amount, along with writing in the correct complexity classes for the operations in the comments at the front of the .java class files.

Some students did not reach the C level (17%; 20% last quarter); these students should come by to office hours to talk to me (especially if the Quiz and In-Lab Programming Exam grades are also low).

IMPORTANT If you believe that we recorded one or more JUnit tests in error, please email one of the TAs: Yan if the submitting person has a UCInetID of abhinavj to kghodsti; Naveen if the submitting person has a UCInetID of kkpham1 to zsimjee (see the fact sheet; also cc a copy to me) and tell him what you think the differences are. He will then rerun the test, possibly asking you for more information if there is still confusion, or running it with you at lab meeting. 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.

About 37% of the students scored an A; another 22% scored a B (so about 59% passed at the B or above level); the last time I taught this class this number was 55%. I have posted in our EEE dropbox a download with everyone's submitted programs, so you can download your work and better interpret my gradesheets, which I will return in class on Monday. Of course, you should also look at my solution, which is included inside the download.

There were many different mistakes made by students writing this class. Here are some comments on the solutions: with 175 students in the class there were lots of different kinds of problems in incorrect solutions. Recall that at most I could take off at most 5 points (10%) for suboptimal "Java use"; so if your solution was correct, you would at worst score >= 90%.

I placed short, but more detailed comments on the sheets I will return; view these sheets, along with your program and mysolution, to learn the most from this In-Lab Programming Exam (in preparation for the midterm).

• readGraph (worth 20 points)
  • Some students either did not include an "infinite" loop to read each line in the file, terminated by catching the EOFException and breaking out of the loop. It is possible to do this part using readAllTokens, and a few students did this successfully, but most who tried failed.
  • Some students did not tokenize the line correctly, or extract the first/second values: the source and destination nodes; some used an inner while, but there were just two nodes per line.
  • Some students did not write the "map updating" code correctly, or as simply as it could be written: doing a minimal amount of object creation and map operations.

• nodesByEdgeCount (worth 30 points)
  • There were many ways to solve this problem: my algorithmic hint was a particularly simple and symmetric way to solve the problem, but other algorithms -if implemented simply- received full credit.
  • Building the temporary map required two loops (although there were many variants of how to use these loops): edges from both source and destination nodes must be accounted for, for each edge represented in the graph.
  • Students who tried to keep counters for these edges were not successful: the counters were kept in the map itself.
  • It is possible to process a source node in the outer loop and only destination nodes in the inner loop, but it must be done carefully, and each source node typically updated the map based on the size of its associated set (see my alternative solution).
  • Reversing the Map<String,Integer> to a Map<Integer,Set<String>> required just one loop (I used entries) using the entry value as the key and updating the associated set with the entry key.
  • All this code, along with the code in readGraph was similar, in that special cases were needed for the first time a key was placed in a Map, and general code for every other time, updating the associated value.

Look at your returned work carefully. Generally scoring 20 or over is good for a quiz. Scoring under 16 might indicate a lack of understanding of something important (which you might learn from looking at my solution, or in other ways). If your score was below 16, you might want to review this quiz with me or your TA during office/consulting hours; certainly you should compare your solution to mine. Material similar to this quiz will be on the written exams.

After I return your graded work in class on Wednesday, 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 a thousand 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 (which is sometimes minimal, because I do publish solutions and expect you to read them).

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 this problem, which involved determining the complexity class based on statement counts. For full credit, I wanted you to compute the exact number of times statement was executed (for parts 1, 3, and 4) and say something relevant about part 2: "like binary searching" is a bit obtuse, "divides i in half for each iteration" is better, "doubling N causes one more loop iteration" is best: all of which relate to its O(Log₂N) complexity class. Note that if i is 1, i/2 is 0. For part 4, many students treated the nested loops as if they were separate (they are in part 3), but the upper-bound of the inner loop depends on the index of the outer loop: as a result the exact statement count is half what many students wrote.

• Problem #2: Most students did well on this problem, although some multiplied O(N) for the test in the 2nd part instead of adding it: do the test, and in the worst case then do the nested statement. Also, a few students dropped the log₂ N term in the last part N²log₂ N because it was a lower-order term: but we drop only lower-order terms that are added, not multiplied. Finally some students think that O(N log₂ N) is a lower complexity class than O(N), but log₂ N is bigger than 1 if N>=2

• Problem #3: Many students did well on this problem. For full credit you needed to solve exactly for the size where the two methods take the same amount of time, not just approximate it. You also needed to specify correctly which method to use for sizes greater than the "equal-size", which many students did in reverse, saying that m2 was better for large N. It is m1 that has a lower complexity class (see my comments from Problem #2), so eventually m1 is faster than m2. Given that the curves cross, you don't have to evaluate the time function for any values to figure out which algorithm is faster for the larger N: it must be the function in the smaller complexity class (independent of coefficients); if you showed such a calculation, I took off half a point (and in other places if you didn't show some calcuation, I took off points: students can't win:).

• Problem #4: Students did well here, but some did not get full credit. I wanted you to state the complexity classes of binary searching (O(Log₂ N)), determining whether an array is sorted ( O(N), which some students got wrong, saying that was the complexity class for sorting it), doing both is (O(N)), and then mention that linear searching could be used to solve such a problem in the same complexity class (O(N)). If you got 1.5 points here, you did well.

• Problem #5: Most students got this correct: some had minor calculation mistakes, for which I took off points based on how "crazy" your result was: e.g., if you calculated solving the 1,000 times bigger problem to take less time than the smaller problem, or much more than 1,000 times longer, you lost more points. Also, you needed to show your work in solving for the constant, not just put it in the formula for T(N) pulled out of thin air. Also, I wanted you to approximate logarithms, not use your calculator. Some students had no idea how to proceed on this problem, but something very similar was in the notes from the first AA lecture (and I did a few examples in class). I expect you to read the notes: they cover more material (including important material) than I can cover in class, and act as a good refresher.

• Problem #6: Many students missed parts of this problem. In Algorithm 1, doubling the size of the problem approximately doubled the running time (and doubling 3 times -increasing the input size by a factor of 8- led to an increasing in running time by a factor of 8): the signature of an O(N) algorithm. In Algorithm 2, doubling the size of the problem approximately quadrupled the running time (and doubling 3 times -increasing the input size by a factor of 8- led to an increasing in running time by a factor of about 64 -actually closer to 60 for my measurement): the signature of an O(N^2) algorithm. Some students I think saw the relative amounts of time and deduced that Algorithm 1 had to be a higher complexity class because the times were bigger; but, that was based on a bigger constant: notice that if you double the input size again, and go out to N = 1,600, the first algorithm would take about 4,800 ms while the second would take about the same: after that the second would always take longer than the first. Finally, Algorithm 3 was the strangest. The first thing to note is that while doubling N from 100 to 200 doubled the time, each other doubling did NOT double the time. In fact, doubling the input always lead to a time increase of about 20 ms (a constant increase): the signaure of an O(Log N) algorithm. Some students thought a constant increase means an O(1) complexity class, but that class would show no increase for doublings. Also, this algorithm showed time increases that were less than linear, so another cue that you should be looking for a complexity class between O(1) and O(N).

There were 108 submissions (from groups and some individuals): 42/14 groups received 3/2 points extra credit for an early submission (so a total of 56 of 108 submissions, or abouit 51%; last quarter it was 56%); about 46 groups submitted correct solutions to part #5 (43% of the class). 77% of the students worked in groups and 23% worked by themselves. Overall, there were 77% As, 10% Bs, 6% Cs, and 7% below Cs; last quarter the numbers were 71% As, 10% Bs, 12% Cs, and 6% below Cs. Remember that an important part of every assignment is examining my solution and comparing it to yours; it gives you another chance to learn something about Java programming. Of course, the first In-Lab exam depends on your knowledge of this material.

You can find a detailed spreadsheet of how we graded your programs in Program 1 Grading. There are comments wherever X's are placed, briefly explaining why a part was not counted correct (for a sequence of Xs, sometimes the comment is just on the leftmost X). Recall that the number of points for each part was Reverse 15, Reachable 15, FA 15, NDFA 10, and WordGenerator 5. Generally students scored best to worst: Reverse, FA, Reachable, NDFA, and WordGenerator.

Generally 1/2 credit was given for reading/printing the information correctly, 1/2 for "solving" the problem related to the data (on those problesm with 3 data files, on each part I gave 50% for correctly solving the first part, and 25% for each of the 2nd and 3rd parts). 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, building the required map, and then simulating that machine on an arbitrary input read from another file (see the InputDivisibiityBy3 FA).

Only a few students did not reach the C level (~7%); these students should come by to office hours to talk to me (especially if their Quiz grades are also low).

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; also cc a copy to me) and tell him what you think the differences are. Please read the comments in the spreadsheet carefully before contacting your TA. He will then rerun the test, possibly asking you for more information if there is still confusion, or running it with you at lab meeting. 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. If you feel there is still a problem after talking to the TA, please contact me (but always contact the TA first).

Look at your returned work carefully and carefully examine my solution Generally scoring 20 or over is good for a quiz. Scoring under 16 might indicate a lack of understanding of something important (which you might learn from looking at my solution, or in other ways). If your score was below 16, you might want to review this quiz with me or your TA during office/consulting hours; certainly you should compare your solutions to mine. Material similar to this quiz will be on the written exams.

After I return your graded work in lab 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 a thousand 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).

A few students are submitting their quizzes with the wrong Lab #; others are stapling togther multiple sheets of paper. Both actions result in point deductions.

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 (which is sometimes minimal, because I do publish solutions and expect you to read them).

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: Some students had no idea how I wanted this picture updated; others knew the right form of the answer, although some did not correctly update the references in the loca/instance variables, or they wrote new LN nodes instead of updating the ones shown. Many students missed some of the changed references; especially worrisome to me were assignments of the form a = b; where students made the variable "a" refer to the variable "b" instead of making the box for variable "a" refer to the same object that variable "b" was referring to (the correct semantics). Finally, if a variable stores null (written as a slash) it doesn't contain an arrow that refers to null written somewhere, or worse refer to part of an object (that's impossible). If you don't understand how to do problems like these, it will be very difficult for you to debug linked list code. Also, there will be a problem like this on the midterm.

• Problem #2: Some students knew the right form of the answer, but many students missed some (or many) of the components: most commonly omitted was the ArraySet<String> object (instead many students wrote "s" refering directly to an array); other students missed the labels or values for some of the objects and/or instance variables (I didn't care about the inherited modCount variable). I did expect you here to look up the definition of the ArraySet class and find its instance variables (I drew a few diagrams like these on the white board during class, and they should have been in your notes); you needed to show what these variable needed to store "reasonable" values. The instance variables in the array are numbered starting at 0. You need to show the String values as labelled objects. Quite a few student drew a linked list implementation instead of a array implemention.

• Problems #3-5: Most students showed a good understanding of iteration and recursion on loops. Many students lost .5 points on each problem, because their code would throw a NullPointerException when called with an empty list. Always ensure you code works for empty lists. Note that if your loops do at least 2 of the 3 function of a for loop (initialize a variable, perform a continuation test, advance the variable to be closer to termination) write it as a for, which combines these three aspects in one locality: the parenthesized information after the keyword for; doing so makes it easier to understand the loop before you go into the body.

After I return your graded work in class on Wednesday, 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 a thousand 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 (which is sometimes minimal, because I do publish solutions and expect you to read them).

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. Most students did well on all problems; the quiz was designed for you really to explore the methods in these collection classes, to write concise and efficient code.

• Problem #1: Lots of scores in the 4-5 range (of 5). Many students lost points for not using the for-each iterator (you don't need to declare/use an explicit iterator here), or for using a second iterator instead of using the .addAll method. Note that the returned result has to be declared and allocated (both using the generic type parameter <T>).

• Problem #2: Lots of scores 2 or above (of 3). Some students wrote 3-4 line versions (as one might exchange the values in two variables); but we can use the fact that .put returns the value previously associated with the key (so the methods can be composed: written with one statement that uses nested .put calls). Some students called .remove (which is not needed because just calling .put keeps the key in the map but associates it with a new value). Maybe this isn't the clearest way to write this code, but it shows you understand the semantics/meaning of these methods.

• Problem #3: Lots of scores in the 4-5 range (of 5). Many students lost points for not using the for-each iterator (you don't need to declare/use an explicit iterator here), or for using a second iterator instead of passing each Set to the constructor for ArrayList, which just iterates over its values, attempting to put each in the list, and succeeding if it is not already there.

• Problem #4: This was the hardest problem: getting 6 (of 7) was good. I wanted students to transcribe my algorithm into collection code, but some students implemented different solutions, some that worked and some that didn't. Only one loop is needed: use it to add each value to the set, while checking whether, it was new to the set; you never need to call contains. And, if you set-up right, you need to call get only once in the loop.

• Problem #5: Lots of scores 4 or above (of 5). The exception code should appear at the top, immediately throwing an IllegalArgumentException which includes an error message that includes any of the illegal values. Some students solved the rest recursively (not needed; we will cover recursion in class soon) and some iteratively (both solutions are short). Some students solved it right, but some recurred/iterated too few or too many times or didn't calculate a new value for each recursion/iteration.

Look at your returned work carefully and carefully examine my solution Generally scoring 20 or over is good for a quiz. Scoring under 16 might indicate a lack of understanding of something important. If your score was below 16, you might want to review this quiz with me during office/lab hours; certainly you should compare your solutions to mine. Material similar to this quiz will be on the written exams.

After I return your graded work in lecture on Monday, 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 a thousand 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).

We will also briefly look at the grades worksheet in class on Monday.

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 work: it makes my office messier, and you don't get the benefit of the feedback I wrote on the quiz (which is sometimes minimal, because I do publish solutions and expect you to read them).

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.

Please remember to turn in your quizzes on 1 sheet of paper (no staples, paper clips, etc.), with both sides oriented correctly. I pass out quizzes on 1 sheet of paper on Friday; get them or find a 2-sided printer. Also, please write your lab number in the provided space and put your quiz in the correct pile. I took off points for a dozen students who did not follow these instructions.

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 not copying the parameter to one instance variable in the constructor); also, declaring too many instance variables (instead of declaring some as local variables in the methods that use them); the int and String instance variables should be initialized in their declarations: they are always initialized to the same values; not using the type Decision for the constructor's parameter and its matching instance variable (e.g., instead using Object or LengthLess or Prefix or both): you must have written only one constructor to work with all possible Decisions. not declaring all the instance variables private; not putting the instance variables, constructor, accessors, and mutators on the correct side of the dividing line; not writing reset: note that the String should typically be reinitialzed to "", not null (although that depends on other parts of your solution), and the Decision should not be reset (it is never changed); not specifying a Object parameter to tryIt and not calling the .isOK method correctly in tryIt; incrementing the count conditionally: it should be incremented unconditionally, whenever tryIt is called; casting the Object parameter in tryIt to a String (or calling toString on it) when calling the .isOK method: you must use an Object; not putting spaces only between Strings; checking the counting variable to be 0 to decide whether or not to append a space to the String you are catenating: this fails if isOK is false for the first value, because then the String will be empty but the count will be 1 so an extra leading space will be added to the String; a minor issue, but I took off .5 for it; your if statements should NOT include ==true as in if (decide.isOK(x) == true) because writing if (decide.isOK(x)) means the same thing; also, you should generally not declare a local variable in a method unless it is used at least twice in the method.

• Problem #2: Again, most students did well writing this class. Common problems included not specifying that the class implements Decision or not writing a the required constructor for the class (copying the parameter to an instance variable). 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 or writing some complicated checking code instead of just calling .startsWith; a minor issue, but I took off .5 for it, you should NOT have an if statement that returns either the literal true or false, but instead should just return the boolean condition of the if: dont' write if (test.startsWith(prefix)) return true; else return false; but instead write just return test.startsWith(prefix);

• Problem #3: The whole point of this problem was to construct and use an object from the Catenate class (passing its constructor an object constructed from the Prefix class which was constructed with one parameter from the method). Then, the other code just loops through every array value, calling the tryIt method from the constructed Catenate class, finally returning the getCatenation computed by the Catenate class. Even working solutions that did not effectively use Catenate were not awarded many points.

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.

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.

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