Announcements

Fundamentals of Data Structures
ICS-23: Lecture A/Labs 1-3
Winter 2012


#19: 3/27/12
Final Exam Grades/Penultimate Grading Spreadsheet
I have now recorded all the grades for the final exam in the spreadsheet, and thus all the grades for this quarter. You should examine it one more time to ensure that I have recorded all your pre-final exam grades correctly.

The average score on the first part of the final exam was 62%; on the second part it was 54% (much lower: maybe harder questions, maybe you just had less time, or maybe you were just more fatigued). The average for the entire final exam was 58% (and the median was also 58%). In the two previous quarters I taught this class, the averages were 55% and 54% (and the medians 58% and 56%). The high grade was 92% and the low grade was 25%.

Recall that if your percentage on the first part of the final exam was higher than your percentage on the midterm, your percentage on the first part of the final exam will count for your midterm percentage): 54 of 94 students scored higher: although the average was just 3% higher, 6 students scored 20% or more higher (most had low midterm scores), and 23 scored 10%-19% higher.

After normalization, there were 22% As, 20% Bs, 21% Cs, and 36 Ds and Fs. The last time I taught this class there were 20% As, 20% Bs, 26% Cs, and 35% Ds and Fs; the time before that there were 14% As, 19% Bs, 30% Cs, and 37% Ds and Fs.

I'm taking off this evening (Tuesday) from grading and then I will re-examine the spreadsheet for each student on Wednesday, before assigning final grades. No one will get a lower grade than the spreadsheet shows, and few (very few, often no one) will get a higher grade: but I do look at all the grades for each student individually before assigning final grades. After I do enter the final grades, I will send you a final email with some observations on how to interpret your grades and advice on what to do if you scored a C or lower, and some final comments on this course.

Let me now briefly discuss the current grades distribution. At present there are 33% As, 24% Bs, 26% Cs, and 17% Ds and Fs. The last time I taught this class there were 34% As, 27% Bs, 16% Cs, and 23% Ds and Fs; the time before that there were 39% As, 25% Bs, 16% Cs, and 20% Ds and Fs. I have provided this information to show you that although my grade distributions vary from quarter to quarter, there is general consistency between them. While there are a bit fewer As and Bs this quarter, there are also fewer Ds and Fs.

You will be able to examine you final exam in my office but not keep them; you can also see my solution to the final exam, when you examine yours. I will have these exams in my office for the first few weeks of the Spring quarter; you can find my office hours for Spring soon, on my updated home page. You can visit me then (and I hope you do stop by, even if it just to say hi and update me on what you are doing).


#18: 3/22/20121
Program #5
The reader has graded (and I have recorded the grades for) Program #5. The class average was about 55 (or about 92%) and the median was about 60 (or about 100%). There were 66 submissions (from groups and some individuals): 36/8 submissions received 3/2 points extra credit for an early submission. The scores on this assignment were very good on the graph part: only 3 submissions lost many points on HashGraph, and a bit worse on the algorithm part, where 20 submissions lost many points on Dijkstra / TSP.

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/TSP 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. Since some of the final exam will be in our labs, he/we can stay clear up any disputed points right after the final exam.


#17: 3/14/12
Quiz #8
I have graded (and recorded the grades for) Quiz #8. The class average was about 20 (or about 78%); the median was about 22 (or about 88%). The last time I taught this course, the class average was about 20 (or about 80%); the median was about 22 (or about 88%). About eight students did not turn in all parts of this quiz.

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, your explanation should say that none of the unprocessed nodes had an in-degree of 0, not say just that nodes formed a cycle.

  • Problem #2: Most students got this part correct. Some student left-out the values on the edges (1 point deduction). A few students had incorrect edges in the minimum spanning tree (-2 for each).

  • 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 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.

    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).


#16: 3/7/12
Quiz #7
I have graded (and recorded the grades for) Quiz #7. The class average was about 20 (or about 78%); the median was about 22 (or about 88%). The last time I taught this class the average was about 20 (or about 79%); the median was about 23 (or about 92%).

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. 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/into a recursive method, as this creates more/slower code: the for loops are optimal for either. 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. I took off points because I wasn't sure where this code came from

  • 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. 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 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 an 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.

#15: 3/5/12
Program #4
The TA has graded (and I have recorded the grades for) Program #4. The class average was about 51 (or about 85%) and the median was about 55 (or about 92%). Last time I taught this class, the average was about 53 (or about 89%) and the median was about 58 (or about 97%). There were 60 submissions (from groups and some individuals): 23/0 submissions received 3/2 points extra credit for an early submission. The scores on this assignment were good. Only about 12 submissions lost many points on HashMap and 3 submissions lost many points on SetFromMap; but,many submissions lost many points on SkipListSet (most by not being submitted).

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.


#14: 3/2/12
In-Lab Programming Exam #2
I have graded (and recorded the grades for) In-Lab Programming Exam #2. The class average was about 38 (or about 76%); the median was about 42 (or about 83%). The last time I taught this class, the class average was about 39 (or about 77%); the median was about 43 (or about 86%). About 37% of the students scored an A; another 18% scored a B (so about 55% 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 Friday. 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 94 students in the class there were lots of different kinds of problems in incorrect solutions.

  • findNode
    • Most students wrote this method correctly (using .equals, not ==) although some students wrote code that changed highest instead of a locally-declared cursor variable, losing the reference to the start of the list.
    • Some students stopped scanning when cursor.next == null so didn't examine the last node.
    • A for loop is the simplest, most natural way to write this method.

  • 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, to know whether to immediately return false.
    • There should be one check for putting the value at the front (changing highest: combining the case where the list is empty with the case in which a non-empty list has a first priority that is less than the priority of new value being added).
    • There were all sorts of errors in finding the spot to put the new value (based on the rules for putting it inside -after all equal priorities- or at the end of the list) and actually inserting it there; many students lost 4 or more points for these mistakes.
    • After grading this method, I replaced it with a working one to grade the rest of the methods.

  • priorityOf
    • Most students wrote this method correctly, using one call to findNode, whose value should be cached, checked, and if not null used to access the priority of the returned LNobject.
    • Some students called findNode twice; others wrote a new loop in this code (sometimes skipping the last value).

  • howManyHavePriority
    • Most students wrote this method correctly or close to correctly. The full credit solution uses one loop, stopping when a lower priority is reached, incrementing a variable for all values earlier have the selected priority.
    • I deducted points for multiple loops, or loops that didn't have one simple continuation condition (in the for/while header): cursor != null && cursor.priority >= priority.

  • highestPriority
    • Most students wrote this method correctly, writing a special case for empty and non-empty lists.
    • I deducted points for using any kind of loop (which is unecessary because the list is ordred largest to smallest priority, so in a non-empty list, the priority of the first node should be returned).

  • lowestPriority
    • This appears on the gradesheet as lowestHighestPriority.
    • Most students wrote this method correctly, writing a special case for empty and non-empty lists.
    • The loop here should find the last value in the linked list and return its priority: it shouldn't check priorities in this process; if it did I deducted points.

  • removeHighestPriority
    • Many students had correct solutions here, but there were a few possibilities for incorrect or poor solutions.
    • Some students forgot to check for the exception, or threw an exception with no message about an empty list.
    • Some students did a removal similar to what one would do in a trailer list, which would fail if there was only one LN in the linked list. The right code for removing the first LN is just highest = highest.next.
    • Some students forgot to decrement objectCount or return the correct value.

  • removeLowestPriority
    • Many students had correct solutions here, but there were a few possibilities for incorrect or poor solutions.
    • Some students forgot to check for the exception, or threw an exception with no message about an empty list.
    • Some student forgot the special case of a list with one node, in which case highest must be set to null (not the .next of the second-to-last node in the list).
    • Some students did not correctly locate the second-to-last node in the list, return the value in the node after it (the node storing the last value), and then set its next to be null so it becomes the new last node.
    • Some students forgot to decrement objectCount or return the correct value.

    Some methods in this class would have benefitted from having a header node, others from having a trailer node. I originally explored this problem with both, but some code seemed very obscure/complicated; I then looked at just a header node or just a trailer node, but decided to just require a simple list. Because of the paired lowest/highest methods, I did all the initialization and wrote the method headers, something I didn't do the last quarter I gave an exam like this one.


#13: 1/22/12
Midterm Written Exam
I have graded (and recorded the grades for) the Midterm in-class written exam. I expect you to go over my solutions and understand them (and if you don't understand them, to seek help understanding them). We will review the grade distibutions in class on Wednesday. At present there are 26% As, 30% Bs, 23% Cs, and 21 % Ds and Fs -which is about the percentages that I originally projected at the start of the quarter: about 25% in each category. If I had to predict final grades, I would use your current grade, although there is still a lot more work to do: I am going to record 2 more quizzes, 2 more programs (the grade sheet inlcudes Programming Assignment #3, see below), and the final exam. For comparison, the last time I taught this course, at midterm the distribution was 34% As, 20% Bs, 18% Cs, and 28 % Ds and Fs, so this quarter there are more As and Bs (grouped) and fewer Ds and Fs (grouped).

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 midterm-part of the final exam than you did on the midterm itself, I will use your grade from the midterm-part of 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 60%) and the median grade was 58% (last time 62%). Because the class average was below 75%, the grade sheet will automatically add in about 26 "normalization" points (about 15%) 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 skipped any small question (or lost partial credit on any large one) and still scored near 100% on the exam. The highest score (un-normalized) on the exam was 93% (last year it was also 93%). About 22% 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 24% scored an A on the exam and 18% scored a B after normalization: so, this quarter there were 2% fewer As and 1% more Bs. Thus, the scores represented by these curves 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 50%; 4% of the students (4) scored perfectly: Richmond Chang, Jonathan Stroud, Raymond Chan and Chi-Hsun Chang; 8% didn't write an answer for this problem. 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 complicated, but straightforward from the problem description and my algorithmic hints: the Set in the first part was used as the main data structure in the other parts (once it loaded the keys from the Map). Nested loops processed each component, and all the nodes in the component: removing a node from the set (for each seen node) and getting to the next node (or end) in the component via the Map's get method. As we discussed in class, one can use .iterator().next() to get one random value from a collection.

  • Problem 2: Students attempting this problem scored an average of 74%. 22% of the students (21) scored perfectly; 8% didn't write an answer for this problem. A few students still have no idea of what it means to show such a hand simulation, shown on Quiz #3 (this one was easier, doing fewer and simpler iterations). Many students missed how null is shown when it is assigned to a variable/field (some drew an arrow to the null reference inside an instance variable. A few students still drew arrows referring to named variables (only LN objects can have arrows referring to them). Finally, a few just got a bit confused about the meaning some assignment operators, or got lost.

  • Problem 3: Students attempting this problem scored an average of 53%. 5% of the students (5) scored perfectly: Jeffrey He, Samantha Hohmann, Jonathan Stroud, Linda Kwok, and Kelly Yin; 11% didn't write an answer for this problem. This was the priority queue version (from Programming Assignment #2) similar to the array stack implementation shown on Quiz #3. Many students still do not understand these oval/box diagrams: they don't seem to grasp what ovals enclose (all the instance variables in the object represented by the oval). Some students showed array object or linked list objects, and not the HeaderLinkedPriorityQueueu object; some students left out the ovals and labels/instance variables names for each LN node (or forgot the header). I believe that you should understand what objects are needed to specify collection classes: in this case a HeaderLinkedPriorityQueue object, each LN object, and the String objects stored in the priority queue.

  • Problem 4: Students attempting this problem scored an average of 67%. 19% of students scored perfectly; 5% didn't write an answer for this problem. Student solutions to the first part should handle an empty list as a special case; otherwise they should scan until a cursor referred to the final node in the lsit (c.next == null) and stored into the next instance of that a reference to a newly constructed LN storing the parameter's value. For the second part, I wanted you to realize that the special case is not needed, and the other code remains unchanged.

  • Problem 5: Students attempting this problem scored an average of 65%. 2% of the students (2) scored perfectly: John Ader and Christopher Berizko; 19% didn't write an answer for this problem. If you understand recursion, this code often writes itself. First the base cases: two empty lists are equal; one empty and one non-empty list throw an exception. If neither list is empty, check the first values for oppositses and check for the opposites of all following values with a recursive call. To get full credit you needed a close to elegant solution, mirror most of the recursive methods we've seen. This problem was skipped by the most number of students, but for anyone who has a reasonable grasp of recursion it was pretty simple; if your solution immediately looked at .next you are still not thinking about recursion correctly.

  • Problem 6: Students attempting this problem scored an average of 79% (the second highest on the midterm). 6% of the students (6) student scored perfectly; everyone wrote an answer for this question. In e, note that you can delete a value in any position (in an unordered array) by replacing it with the value at the end -not shifting- which is O(1) (when changing the order is allowed). As briefly discussed online, in part r the most "pathological" an AVL tree can get is about 1.44 times the optimal height, so searching such an AVL tree is still O(Log2 N); some students wrote something like "there are no pathological AVL trees" on the exam and I gave them full credit (.5 points) for this part of the problem. Finally, the complexity of a tree traversal, if each node is visited once, depends ony on the size of a tree, not on its height: each node is reachable in O(1) from the node above it, so the total complexity is O(N).

  • Problem 7: Students attempting this problem (with many parts) scored an average of 54%. No students scored perfectly (although four students scored 18): John Ader, Richmond Chang, Matthew Kelly, and Jonathan Stroud; everyone wrote an answer for this question. In part a some students put O(N!) in the wrong place, while fewer put others in the wrong place. In part b I repeated a task from Quiz #5, with an exponential instead of a logarithm (you should know 2^10, 2^20, and 2^30 as 10^3, 10^6, 10^9). Some students were able to compute the formula and new time correctly, some had arithmetical errors (or didn't know how to compute simple powers of 2), others did not really solve for (or know how to solve for) the cofficients. Part c was just like another question on Quiz #4 but a bit more complicated: in the first column when N doubled, time went up by a factor of 4 (so more again O(N^2)); in the second column the time went up by more than a factor of 2 consistently, matching O(N Log2 N), but I have 50% credit for writing just linear; the last one was just O(1); some students forgot to write the predicted value; others choose incorrectly. In part d, very few students got full credit: I wanted a very specific answer about how the O() algorithm could not be reduced to a lower complexity class because of the Omega() bound, but how smaller constants could still lead to a better algorithm.

  • Problem 8: Students attempting this problem scored an average of 59%. 3% (3) scored perfectly: Kenneth Baldauf, Spencer Stephens, Shannon Lewis; 5% didn't write an answer for this problem. In part a, the recursive call pattern was just like for size, which must traverse both sides of the tree, calling check.isOK on each value; again, I felt that this method almost wrote itself if you understood basic binary tree recursion. Students did a bit better in part b: most were able to fill in the preorder and postorder traversal (although a few write breadth-first for preorder), but many fewer were able to recognize (some just wrote the postorder traversal reversed and some left this part blank) that the reversal of a postorder traversal was just a preorder traversal going to the right subtree before the left. Students did well on part c, often writing the full tree or nothing; a few students wrote a tree that either wasn't a BST or the numbers/structure wouldn't produce the required travesal.

  • Problem 9: Students attempting this problem scored an average of 80% (the highest on the midterm). 42% of the students (40) scored perfectly; 5% did not write an answer to this problem. 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 10: Students attempting this problem scored an average of 51%. 6% of the students (6) scored perfectly: Hye Chi, Brandon Gaw, Kier Groulx, Jeffrey He, Ashish Patel, Suhayum Chowdhury; 5% didn't write an answer for this problem. This problem was like the AVL tree problem on Quiz #6 (in terms of what different tasks it asked you to do), but I also asked you to show two standard rotations (which should have included general node names A, B, and C -in the correct order- and subtrees T1-T4): note that when drawing the trees, you needed to account for the fact that A<B<C. I gave little partial credit for the final tree: it was worth 6 points to redraw the tree after the correct AVL rotation. 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, restoring the order property by moving either 45 or 80 where 54 was and then rebalancing if necessary.

  • Problem 11: Students attempting this problem scored an average of 45% (the lowest on the exam, although maybe students had to rush through these questions at the end: each allowed only a minute of thought/writing). No students scored perfectly (although one student scored 11.5): Valree Weythman; 21% didn't write an answer for this problem (second only to the recursive linked list problem). This was a "stand back and take in the big picture" question, and each part was worth 2 points. Some student have the concept of data types and data structures backwards; more seem confused by these terms. Others did OK, but had trouble writing answer for parts e and f which did require a bit of thinking. Note the interface handout, if you thought to look at it, listed all the data types and by being called the interface handout signalled this was an important aspect of data types. I over-/re-viewed this material a few times in lecture, and have spoken these terms hundreds of times.

#12: 1/22/12
Program #3
The TA has graded (and I have recorded the grades for) Program #3. The class average was about 45 (or about 75%) and the median was about 57 (or about 95%): the two prior averages were 95%. The class average last quarater was about 44 (or about 74%) and the median was about 56 (or about 93%). There were 59 submissions (from groups and some individuals): 14/13 submissions received 3/2 points extra credit for an early submission.

The scores on these programs were lower than I expected: in fact, about 13 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 TA. The code required was intricate, but writing it should have been within the grasp of all students over a two week period. 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 compare 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.


#11: 2/15/12
Quiz #6
I have graded (and recorded the grades for) Quiz #6. The class average was about 20 (or about 79%); the median was about 21 (or about 84%). Last quarter, the class average was about 18 (or about 73%); the median was about 20 (or about 80%).

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 that leaves 5, 9, 13 and 16 could be easily removed, but some students also listed 2, 24, and 38 (and others, even non-leaf nodes), which both cause a violation of the AVL property somewhere 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 an empty base case, followed by a simple combination of looping and recursion that accumulated the sum (including t.value) and returned it. There is no right answer for the "Traveral Order" question: it depended where you added t.value to the sum; if first, it would be a preorder traversal; if last (in the return statement) it would be a postorder traversal. And, I wanted one of those two words.

  • 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.

  • Problem #4: Most students scored either >=6 or <=4; the reason was that many forgot to include a second loop that traversed the linked list in each bin/bucket; best to not check whether the bin/bucket is empty, but just loop through all its values (none if it is empty) adding them into the new (twice as big array). Some students who actually called the add method to get the value added forgot to reset objectCount, which each call to add increases (resulting in an object count twice what it should be.


#10: 2/8/12
Quiz #5
I have graded (and recorded the grades for) Quiz #5. The class average was about 21 (or about 84%); the median was about 21 (or about 84%). Last quarter, the class average was about 21 (or about 85%); the median was about 22 (or about 88%).

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.

  • 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, fewer 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).


#9: 2/6/12
Program #2
The TA has graded (and I have recorded the grades for) Program #2. The class average was about 55 (or about 92%) and the median was about 60 (or about 100%). Last quarter, the class average was about 54 (or about 90%) and the median was about 60 (or about 100%). There were 63 submissions (from groups and some individuals): 19/10 submissions received 3/2 points extra credit for an early submission. About 8 LinkedQueuesubmissions failed most of the JUnit tests; about 12 HeaderLinkedPriorityQueuesubmissions failed most of the JUnit tests; about 8 TrailerLinkedSetsubmissions failed most of the JUnit tests. 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. Of special interesting is the add method in the HeaderLinkedPriorityQueue class: some student solutions were very complicated compared to my code. Using a header-list allows for this code to be expressed in a very simple and compact form.

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 (20%, 17% 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 Sam Hallman, the Lab 1-2 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.


#8: 2/2/12
In-Lab Programming Exam #1
I have graded (and recorded the grades for) In-Lab Programming Exam #1. The class average was about 37 (or about 75%); the median was about 42 (or about 83%). Last quarter, the class average was about 36 (or about 73%); the median was about 41 (or about 82%).

About 44% of the students scored an A; another 11% scored a B (so about 55% 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 included inside the download.

There were many different mistakes made by students writing this class. Here are some comments on the solutions: with 98 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 15 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.
    • Some students did not tokenize the line correctly, or extract the first/second values: the source and destination nodes.
    • 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.

  • printMap (worth 5 points)
    • Some students didn't follow the obviouis steps: create a List of keys (using the ArrayList constructor), sort it, and iterate over this List of keys, retrieving the value associated with each (and printing both key and value).
    • Some students constructed and empty List and added to it, forgot to sort, or used a complicated loop (not just a for-each loop.
    • Some students used extra variables or explicitly called .toString which was not necessary.

  • 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.
    • Using the temporary map required two loops (although there were many variants of how to use these loops: both source and destination nodes must be accounted for, for each edge represented in the graph. Reversing the Map<String,Integer> to a Map<Integer,Set<String>> required just one loop. All this code, along with the code in readGraph was similar, in that special cases were needed for the first time a key was place in a Map, and general code for every other time.


#7: 2/1/12
Quiz #4
I have graded (and recorded the grades for) Quiz #4. The class average was about 21 (or about 83%); the median was about 12 (or about 84%). The class average was about 21 (or about 84%); the median was about 22 (or about 88%).

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", "divides in half for each iteration", "doubling N causes one more loop iteration" all of which relate to its O(Log2N) complexity class. 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 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. Also, a few students dropped the log2 N term in the last part N2log2 N because it was a lower-order term: but we drop only lower-order terms that are added, not multiplied.

  • 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. 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, 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).

  • 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(Log2 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)).

  • 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. I expect you to read the notes: they cover more material (including important material) than I can cover in class.

  • 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.

  • Problem #7: Most students did well, but many methods mixed base cases with non-base cases which made them harder to understand: try to write all the base cases first (three in this problem) before the recursive case. Some students were testing l1.next for null; the only use of .next was in the recursive call; everything else should test l1 and l2. Finally, a few students wrote iterative solutions (the requirement was recursive ones), or used local variables (none are needed) or forgot to include some return statements.

#6: 1/25/12
Quiz #3
I have graded (and recorded the grades for) Quiz #3. The class average was about 18 (or about 73%); the median was about 19 (or about 76%). Last quarter the class average was about 18 (or about 72%); the median was about 20 (or about 78%). Because the average was < 75%, everyone will receive about .4 "normalization" points to bring the average for this instrumnent up to 75%. It shows as rounded to 0, but it is added to your final score The total of all points recorded for each student and the normalization points for all the instruments in the course (totaled in column T), are automatically added in the % column to compute the current percentage for each student.

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 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).

A few students are submitting their quizzes in the wrong piles on Monday; 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 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 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). 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 of the components: most commonly omitted was the StackArray<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 ArrayStack class and find its instance variables (although I drew a few of 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; a question about this was asked and answered on the message board.

  • Problem #3: This turned out to be too complicated to grade on a fine scale, so I gave "rough" points. You should check to see whether your code produces reasonable results for an empty list, and that it works correctly whether the final values in the list are duplicates or different (I wrote end fix if I thought your code didn't work in one of these cases: see me if I was wrong.
  • Problems #4-5: These problems were easier to solve and grade. Many students lost .5 points on each problem, because their code would throw a NullPointerException when called with an empty list.

#5: 1/23/12
Program #1
The TA has graded (and I have recorded the grades for) Program #1. The class average was about 56 (or about 93%) and the median was about 57 (or about 95%). Last quarter the class average was about 57 (or about 95%) and the median was about 60 (or about 100%).

There were 64 submissions (from groups and some individuals): 20/14 groups received 3/2 points extra credit for an early submission (so a total of 34 of 64 submissions, or abouit 53%; last quarter it was 73%); about 16 groups submitted correct solutions to part #5. 70% of the students worked in groups and 30% worked by themselves. Overall, there were 71% As, 10% Bs, 12% Cs, and 16% 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.

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 (~6%); 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 Sam Hallman (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 the 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).


#4: 1/18/12
Quiz #2
I have graded (and recorded the grades for) Quiz #2. The class average was about 21 (or about 86%); the median was 23 (or about 92%). The class average the last time I taught this course was about 20 (or about 81%); the median was 22 (or about 88%). 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 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 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).

  • 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 List to the constructor for ArraySet, which just iterates over its values, attempting to put each in the set, an 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 get each value and add it to the set, checking whether, it was new to the set; you never need to call contains.

  • 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 next Monday) 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.

#3: 1/17/12
Quiz #1
I have graded (and recorded the grades for) Quiz #1. The class average was about 22 (or about 88%); the median was 23 (or about 92%). The 4 point gap here is because while many students did very well, a few did very poorly - bringing down the average but not bringing down the median grade. The class average the last time I taught this course was about 20 (or about 79%); the median was 22 (or about 88%), so I'm happy to report that as a class, you seem to be doing well.

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/consulting hours; certainly you should compare your solutions to mine. Material similar to this quiz will be on the written exams.

Besides 7 registered students who did not turn in quizzes, there were 5 students who scored less than 50%, some one digit scores; they should see me immediately, so that we can discuss whether or not they should be in this course: why they did so poorly on the quiz (there certainly might be legitimate reasons). In schools on the quarter system, I advocate students who did not perform well in a previous course (possibly indicated by a low score on Quiz #1), 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 when considering how well you will be able to do in all the other courses that you'll take that build on this material.

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

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.

Please remember to turn in your quizzes on 1 sheet of paper (no staples, paper clips, etc.) I pass out quizzes on 1 sheet of paper on Friday, or you need to 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 1/2 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 to tryIt to a String (or calling toString on it): you must use an Object when calling the .isOK method; not putting spaces only between String; 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. Working solutions that did not effectively use Catenate were not awarded many points.

#2: 9/23/11
Install Course Software
All students with computers should download and install Java (latest version is JDK 6 Update 26) and Eclipse (latest version is Eclipse 3.6.2 - named Helios); it is also a good idea to install VNC (Virtual Network Computing). All these products are available for free. Students can download and install this software (and other useful material) from the web by exploring the Online Resources link (see Course Software, near the top of that page).

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.


#2: 1/9/12
Install Course Software
All students with computers should download and install Java (latest version is JDK 6 Update 30) and Eclipse (latest version is Eclipse 3.7.1 - named Indigo); it is also a good idea to install VNC (Virtual Network Computing). All these products are available for free. Students can download and install this software (and other useful material) from the web by exploring the Online Resources link (see Course Software, near the top of that page).

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.


#1:1/9/12
First Message
Welcome to ICS-23 I am going to post and archive important messages about the class in this announcements web page: each entry will be numbered, dated, and labeled. The entries will appear in reverse chronological order. Whenever you follow the link to this page (and you should do so daily), scan its top for new announcements; scan downward for older announcements. This message will always appear at the bottom of this file.

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.