Held: Monday, 1 September 2014

Back to Outline 01 - An Introduction to the Course. On to Outline 03 - An Introduction to Java Development.

Summary

We ground our understanding of abstract data types and their implementation by exploring the design of two ADTs.

Related Pages

• Reading: Designing ADTs
• Reading: Designing Data Structures
• Wiki: https://github.com/Grinnell-CSC207/adt-exploration/wiki/An-Expandable-Array-ADT
• EBoard 2 (Source 2) (HTML 2)

Overview

• Thinking about problem solving
• ADT Design Exercise 1: Stacks
• Implementation Example: Stacks
• ADT Design Exercise 2: Dynamic Arrays

Administrivia

• The department has a mailing list of events and opportunities in CS.
  Please let me know if you'd like to be on it.
• Don't forget that we have class on Tuesday.
• I have about 60 introductory surveys between my two classes. It takes about fifteen minutes per survey. It will take a little while for me to reply to them all, and I'll probably do the 151 ones first. I will skim the 207 surveys for questions tonight, but probably won't give detailed responses until Friday.
• Not all of you turned in HW 2. I'd like to hear why.

Attendance

• Please write your name on one of the blank playing cards. You may also decorate the same side of the card as your name. Leave the other side blank.

Upcoming Work

• HW3 to be distributed on Wednesday.
• Readings for Tuesday:
  • Getting Started with Git and Github
  • The Eclipse IDE

Extra Credit Opportunities

Academic

• CS extra Thursday: Adam Arsenault on his work at FSF.

Peer Support

Miscellaneous

• Second-year students get extra credit for doing the second-year science retreat. You should have gotten a notice about it.

Thinking About Problem Solving

Here are three things that I expect you to focus on this semester.

• Separate interface and implementation. (You can also think of this as separating the what and the how, the six P's vs. the corresponding Scheme code.)
• Start simple. We're tempted to add lots of features. But more features limit your choice of implementation. So we'll start simple and build.
• Refactor. Good programmers find common code and write instructions that factor out the commonalities. So, whenever you are tempted to copy, paste, and change, instead write a more general function and just call that function.

ADT Design Exercise 1: Stacks

• What are the three key steps in ADT design?
• If you were introducing a stack to someone, what would you say?
• What are situations in which you would use stacks as a programmer?
• What are the essential stack operations? (Small group, then large group.)
  • Name ("Procedure")
  • Meaning ("Purpose")
  • Inputs ("Parameters")
  • Outputs ("Produces")
  • Preconditions ("Preconditions")
  • Postconditions ("Postconditions")

Implementing Stacks

• I'll give a quick and dirty guide to two approaches to implementing stacks.
• Array-based stacks
  • Store the array
  • Store the index of the top of the stack
• Linked stacks
  • Store a link to the node at the top of the stack
• Suppose we choose to implement array-based stacks. How should the code for a stack of doubles or strings differ from the code for a stack of integers?
  • How do you handle the code repetition in C?
  • Java will provide a much more elegant approach.

ADT Design Exercise 2: Dynamic Arrays

• Large group: What is the philosophy?
• Large group: What are some use cases?
• Small group: Review the Wiki page. Decide on operations.
  • Name ("Procedure")
  • Meaning ("Purpose")
  • Inputs ("Parameters")
  • Outputs ("Produces")
  • Preconditions ("Preconditions")
  • Postconditions ("Postconditions")