Beyond Linked Lists: The Skip List

Illustration of a skip list.  Note that the number of forward pointers per node is itself dynamically allocated.

Students who want exposure to data structures more advanced than a simple linked list might enjoy the skip list.  A skip list is a probabilistic data structure that looks a bit like a linked list, but behaves like a self-balancing binary tree that makes insertion and deletion relatively simple and fast.  If you want to know about a self-balancing tree that is challenging to implement, go try a red-black tree.  This spirit of the data structure turns up every now and then, such as in distributed hash tables used in peer-to-peer file sharing among other things.

"Skip Lists: A Probabilistic Alternative to Balanced Trees" by William Pugh, Communications of the ACM, June 1990.

Verdict on Student Feedback About EECS 280

A couple weeks ago, we surveyed the students in EECS 280 to get feedback on how to improve the operation of the course after we received complaints about long wait times (i.e., hours) for meeting with instructors.  About 620 students registered for the course with two faculty, 13 TAs (of which 6 are quarter time), and 4 graders to cover three lecture sections, 16 discussion sections, approximately 25 office hours, nearly 24x7 coverage of the piazza forum, and grading each week. Taking into account part-time staff (1 faculty + 1 double-time faculty + 7 full TAs + 6 1/2 TAs approx= 13), there is effectively a 620:13 ratio of students to instructors or 47:1.

Here's the original survey, and the results.  Short story: we agree the wait times are too long, and we'd like to see improvements in the student-to-instructor ratio.  In the meantime, we are load balancing office hours to increase availability at certain peak times (at the expense of decreasing availability for hands-on exercises in the classroom and other things).  Unfortunately, we were denied requests for additional graders.  Human resources requested that we instead divert TA hours from in-person student interaction to grading homework.  Human resources further admonished the staff when one TA accidentally exceeded the allowable hours.  We're trying to figure out ways to do more with less.

The data, please:

The data indicate that a small number of students experienced excruciatingly long wait times.
At busy times, the more typical wait is about an hour.

Data indicate that very few students are willing to accept "group" office hours to cut down on wait times.
It seems that students strongly prefer 1-1 debugging sessions because of the personal nature of individual programming assignments.

The data are clear: Students feel overwhelmingly that they could perform better if staff office hours were more accessible.  We have rebalanced office hours to address this short term problem, but the long-term solution seems to require more instructional staff.

Surprising to the staff, the data indicate that students overwhelmingly prefer the whiteboard over the chalkboard.  Boo!!

The data seem to indicate a toss up.  Before the survey, a number of students wrote rather strongly that the slides put them to sleep.  We were asked to cut down on the use of slides (to which we agree) during lecture, but it seems a majority of students prefer slides over the blackboard.  We surmise that students who watch recorded lectures prefer the slides because the boards are illegible via the camera, but we have no data to support this hypothesis.

Euchre Code Base

We were curious how much euchre code was collectively written by students in EECS 280. Thanks to UNIX pipes and this handy command-line (you might find this type of command useful in the future): 

find . -name '*.cpp' | xargs wc -l

We found that students submitted 555,285 lines of code (including comments and newlines).  The staff solution to the euchre project is 747 lines of code, of which about 200 are comments and newlines.  So the class collectively wrote more code than is found in a typical pacemaker or the Quake 3 video game engine, but significantly less code than reportedly behind the healthcare.gov website.  However, there is skepticism whether the website truly has 500 million lines of code (and by what measure).  Summary: the less code you have, generally the easier to test.

"According to one specialist, the Web site contains about 500 million lines of software code." - NY Times.

Binary Trees and Football

Binary trees turn up in the most interesting places.

From the Daily Californian:

Kore Chan/Senior Staff, Daily Californian

On his dream: “I’d like to play football for the Pittsburgh Steelers.”

On playing offensive line: “Most people get lucky if they make five big decisions a day. We run 99 plays in a given game. It’s my job over the course of those 99 plays to call out a protection, call out a front and organize traffic. If I get that wrong, someone’s ribs gets broken, and someone goes to the hospital. For protections and calling out schemes, my track record is second to none. People call it pressure; I think it’s fun. You can think of your system algorithmically: If it’s a two by two with three down lineman, it’s this or this; if it’s three by one, you do this. Special case A, special case B. That’s what I think of when there’s eight men in the box. In my younger and more formidable years, I would say that (I suffered from paralysis by analysis.) Now, I actually think that thinking about it algorithmically like that makes it simpler. Most of time, it’s like a binary search tree: It’s either option A or option B. You go down a level: option A, option B. Whichever one it is, you make it and go.”

Container ADTs and Sorting

Testing Code

Students of EECS 280 often ask about the importance of testing code and catching problems early in the software engineering process (ideally at the time of creating requirements rather than at run-time).  A second popular question: is there partial credit for code that does not compile or pass certain test cases?  Here's an example of not getting partial credit for inadequate integration testing.

Graphic from the NYTimes article on a U.S. House Hearing on health insurance marketplaces.  Note the code in the lower left.

Pointers

Lecture on C++ Classes

Credit: Hilferty Memorial

And now all EECS 280 students should understand the graphic on the course web page.

Tail Recursion

xkcd.  that is all.

Recursion

Now I wonder what tail recursion looks like.  (image found by an anonymous EECS 280 student)

NUL-terminated strings: the most expensive one-byte error ever?

ACM Queue on NUL-terminated character arrays.

"This change was made partially to avoid the limitation on the length of a string caused by holding the count in an 8- or 9-bit slot, and partly because maintaining the count seemed, in our experience, less convenient than using a terminator." - Dennis M. Ritchie

Musings on Testing Software

Random musings about software testing for EECS 280 students.

• Testing boundary conditions in Apple Mail
• Leap day errors
• Y2K
• Stages of software engineering for medical devices
• If it compiles, .... (No!!!!!!!)
• Negative security testing for SSL client authentication (news, engineers, swag from RSA)

TARDIS: #1 in the Dematerialization Business

I decided to have some fun with my construction site/home. I wanted to know what the house might look like in the future or whether the emergency re-construction now in its 8 month might ever finish. So I tried to build a time machine. The TARDIS. Unfortunately, I installed a 3rd party chameleon circuit (that's all I could afford) and dropped the dimensional stabilizer down the toilet. (Why have we never seen bathrooms in the TARDIS?  How disgusting. Is the Doctor like one of these people who regularly use the facilities at fast food restaurants?) Enter the TURDIS. Time under relative distress in ....

Tail Recursion Helper Function

Source

See the Hacker's Dictionary on tail recursion.

Recursion

Ah the 1980s.  Big hair.  Puffer vests.  Recursion at MIT.




http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1