Continue lab partners.

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Linked lists.
• Implementation details.
• Lab.

Preliminaries

Admin

• Dr. Davis may be visiting our class today. (She was interested in hearing how we resolved the exam issues.)
• Extended office hours this week (and probably next).
• Here's the plan for the next few days.
  • Today: Lab on Linked Lists.
  • Friday: Collaboratively Design a Doubly-Linked-List Class.
  • Monday: A chance to debrief on the issues raised in lists.

Responding to Issues in Exam 1

• Primary goals for makeup:
  • Make sure that you learn/understand the material.
  • Give you the opportunity to demonstrate that you understand the material.
  • Give you the opportunity to improve your grade.
• Secondary goals:
  • A reasonable student time commitment.
  • A reasonable faculty time commitment.
• Past semesters:
  • "Redo the problems you missed" was a failure in meeting almost all of the goals.
• Suggestion:
  • Three-hour exam. One problem. Requires OO/Java Understanding (e.g., Functional Interfaces), Algorithmic Skill, and some tests.
    
    • An extended version of Pseudosort is one model.
      
      • Functional interface: Comparators
      • Algorithm: pseudo-sorting
      • Tests: You would develop these
    • You might also have to design the functional interface.
    • I'll probably build a library of potential problems and choose your problem randomly from among that library.
  • First thirty minutes: Read the problem. Gather useful online resources.
  • Second thirty minutes: Discuss the problem with me. Part of your grade will depend on the discussion. But I will also try to help you identify key ideas to move forward.
  • Next two hours: Code. I probably won't be available, because I'll be meeting with other students.
  • I average the grade on this with your grade on the exam, with a maximum average of B+.

Projects

Intended model for this semester: I pair groups of students with a client. You set up an Ushahidi installation for the client. You build a simple Java application that does some custom analysis of the data. You present an overview to the class.

• 14
• 2

Model from last semester: You write a parser for JSON. You extend the parser in an "interesting" way. (You get to choose what "interesting" means.) You give a three-minute, three-slide presentation to an audience of potential "clients".

• 5
• 9

Requested model from Heather Benning: You write a program that takes requirements for setting up sporting seasons. We'll probably still do the three-minute, three-slide presentations.

• 19
• 1
• The choice.

I prefer that you all do the same type of project so that things are comparable (and because projects require a lot of support).

Homework 8

• Sam provides the start of a timing suite.
• You complete the timing suite.
• You compare three versions of Insertion sort
  • The one I gave you
  • One in which you inline the call to swap
  • One in which you shift and then insert, rather than swapping
• You compare three versions of Merge sort
  • The one I gave you
  • One in which you use only one other array (rather than building lots)
  • Bottom-up (two arrays)
• You compare four versions of Quicksort
  • Using the first element as the pivot
  • Using the middle element as the pivot
  • Using a random element
  • Using the median of 3 random elements as the pivot
• You compare a generalized sorting algorithm (T[] vals, Comparator order) for integers to one that you hand-code for int[].

Groups:

• HZ, CM, RJHB
• EE, PS, WR
• LBA, CMV, E?F
• ZW, AOA, ZC
• AK, AS
• NS, YK, MSZ
• CG, NK
• AHD, TP, LG

Upcoming Work

• Homework 8: Sorting Out Sorting
  • NOT YET AVAILABLE
• Reading for Friday:
  • Review your notes on linked lists from 161.
  • Reflect on how you might make those linked lists meet our new SimpleList interface (see today's lab for details).

Extra Credit

Academic

• CS Extras Thursday: Randomness
• Pre-CS Extras: Graduate School Meeting at 3:45.
• Wednesday two weeks: 7:30 p.m. Internship panel with Lea and Mira and some random Grinnellian who interned at Google.

Peer Support

• Ajuna MC's talk on Sustainability of Grinnell today at noon in ARH 102.
• Men's Soccer, today at 4pm vs. Cornell.
• Basketball Scrimmage, today at 7pm in Darby.
• 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.
• Saturday fall festival to support MICA. 4-8 pm in Main Quad.
• Cook for ISO Food Bazaar. (You need to submit recipes in order to do this.)
• Eat at ISO Food Bazaar.
• Wear a costume on Friday.

Questions

Linked lists

• What's a linked list?
• A lot of nodes. Each node has a value and a pointer to the next node.
  • Amazingly like pairs in Scheme
• But the nodes get scattered all over memory.

Implementation details

• How do we represent iterators?
  • A node?
  • Don't forget to keep track of what we just saw in the list (and what comes next?)
  • Conclusion: The node we just saw.
• Where should the pointer be before we've called next?