Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Wrappers, Adapters, Delegation, and such.
• Design patterns and terminology.
• Lab.

Preliminaries

Admin

• Old lab partners.
• Extended office hours continue this week.
• Sorry that I could not be here on Friday. I hope you were nice to Mira.
• I'm surprised that no one showed up to the review session last night.
• I probably won't return makeup exams until next week.
• We'll discuss general issues with the makeup exams after I return them.

Upcoming Work

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

Cool Upcoming Events on Campus

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

Extra Credit

Academic

• Convocation Wednesday at noon: Dean Latham.
• Wednesday at 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.
• Men's soccer team "cold" scrimmage on Thursday at 5
• Charlie's Friday Night "War in Animated Film" ExCo.
• Ajuna's week of events. 4:30 p.m. TODAY Prof Powell on effects of disease on economy in Africa.
• Women's BBall, Saturday at 2pm vs. Central.

Questions

• Will we get extra credit if we implement indexing in skip lists?
  • I trust the grader.
  • If you write "Sam said we'd get extra credit for implementing efficient array indexing", your grader is more likely to give you that extra credit.
• What's the role of the Iterator?
  • It's the same as the Iterator for any collection: It gives you all of the values one by one. Easiest to achieve by just following the level-0 links.
  • Also makes you implement a different kind of remove

• How do we use probability?

  • You can have your client code set it. public class SkipList implements SortedList { /** Nice, clear explanation. */ double probability;

          public SkipList(double probability)
          {
            this.probability = probability;
          } // SkipList(double)
    
    
      public SkipList()
      {
        this(0.5);
      } // SkipList
    
    
    

What's a linear structure?

• "It's in an order."
  • Differentiate from a list?
• Linear Structure ADT
  • Philosophy - Collection. There's a policy by which we remove elements from the collection, and we add and remove them one at a time. You can intermix. (Holds for both stack and queue.)
  • Use cases
    • Task list
  • Methods: add(T val), get/remove(T val)
  • Implementation
• Stack: Linear Structure with the LIFO policy
• Queue: Linear Structure with the FIFO policy
• Implementation strategies for collections ...
  • Array
  • Some funky variant of array
  • Linked nodes
  • Some funky variant of linked nodes
• Implementation question: Randomized linear structure, using arrays
  • Need to implement both add and get.
  • Keep track of the array into which we put things and the number of elements
  • Decision (EE) we put elements in in order, but get is random
  • add shove at the end of the array
  • get: generate a random number between 0 and the number of elements
    • Grab the element at that index
    • Fill in the space
      • Option 1: Shove everything over
      • Option 2: Put the last thing in the now freed space
    • Decrement position

Implementing Queues with Arrays

• Keep track of
  • array - values
  • the index of the next place at which we insert a value - addIndex
  • the index of the next place from which we remove a value - removeIndex
• Implement add
  • make sure that the array is not full; if it's full, exception
  • put something add addIndex
  • move addIndex forward, wrapping around if necessary (mod by length)
• Implement get
  • make sure that the arry is not empty
  • remember the element at index removeIndex
  • put null there
  • increment removeIndex, wrapping around if necessary
• We put null in the array so that
  • anything referenced can be cleaned up by the gc
  • we get a signal of an error if we try to reuse
  • can be used to determine full/empty, provided null is not normally allowed
• isEmpty: return values[removeIndex] == null
• isFull: return values[addIndex] != null

Wrappers, Adapters, Delegation, and such

Design patterns and terminology

Lab