After the sublist implementation, I began working on a new means of speeding up the order maintenance algorithm with the use of skip lists.

A skip list builds multiple layers on top of a regular linked list. The original linked list contains all the elements, and the first level of the skip list contains nodes from the original list chosen with a certain probability. In our case, this probability was 50%. The next level of the skip list is 50% of the nodes from the previous level and so on.

Over the course of the week, I read up on skip lists and created a skip list independent of the order maintenance algorithm.

On Thursday, a few of my roommate's graduate student friends invited me along to see Cats at the local outdoor theatre. Free seats are available to theatregoers who get there early, and we waited for about 90 minutes in line to get in. Luckily, the other students had packed a picnic dinner and waiting didn't feel long at all. Cats was, well, Cats, but we agreed to meet up again in two weeks for their production of the Sound of Music.

We went to Fitz's again this week. It is quickly becoming a lab favorite. We also went to see Inception at the Tivoli. The movie really divided the lab. Some people loved it, some people hated it. The Tivoli is advertising a film festival for the next week, and a few of us are talking about going. Unfortunately, the Loop can be a little unsafe at night, so some of the students don't want to be in the area after dark. My apartment is quite literally right around the corner, so it's very easy for me to go without worrying about making a long journey at night. Zach, a student from the lab, and his friend Mark, a chemistry student, have agreed to meet me to see the "Comedy" shorts at the festival.