Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Linear structures.
• Stacks.
• An application of stacks: Matching parens.

Preliminaries

Admin

• Continue lab partners.
• Extended office hours continue next week.
• Sorry that I could not be here today. Be nice to Mira.

Upcoming Work

• Homework 9: Skip Lists due Wednesday.
• Reading for Monday.
  • Queues

Cool Upcoming Events on Campus

• Peace studies talk Monday at 4:15 p.m. in JRC 101 "With All the World’s Violence, Where is Peace?"

Extra Credit

Academic

• CS Table Friday: Open Data.
• Convocation Wednesday at noon: Dean Latham.
  • Convo returns to the awesome time of 11:00 a.m. on Thursdays starting in Fall 2015!
• Wednesday one week: 7:30 p.m. Internship panel with Nelson, Mira, and Lea.

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music.
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• Charlie's Friday Night "War in Animated Film" ExCo. tonight!
• Womens soccer game today, 2:00 p.m., at Lake Forest.

Questions on the homework

Do our iterators have to work at anything other than level 0? For example, should we allow the creation of an iterator at level 1, 2, or 3?

Iterators provide information about the data to the client. The client should not have access to the underlying implementation of the structure, or even know about that implementation. Hence, you should only have one kind of iterator: the one that matchees the SortedList interface.

Should we cap the number of levels in the skip list?

I'd suggest that your constructor take the number of levels as a parameter. However, you may also limit the number of levels to 20 (which supports about 1 million items, at least if the probability is 1/2).

Can we use a fixed probability?

I'd suggest that your constructor take the probability as a parameter. However, you may also use a fixed or default probability of 1/2. (You might learn some interesting things when you use different probabilities.)

Can I make doubly-linked skip lists?

Skip lists are traditionaly singly-linked. But if you want to try to maintain both directions, you are welcome to try.

Linear structures

• Add things in sequence, remove things in sequence.
• A policy determines the sequence.

Stacks

• LIFO.

An application of stacks: Matching parens

• See the lab.

Lab