Held: Monday, 4 November 2013

Back to Outline 33 - Quicksort. On to Outline 35 - Implementing Queues with Arrays.

Summary

We consider a general class of collections called "linear structures". We explore one kind of linear structure, the stack, in a bit more depth.

Related Pages

• Reading: Linear Structures
• Reading: Stacks
• Lab: Stacks
• Code: https://github.com/Grinnell-CSC207/linear
• EBoard (HTML) (PDF)

Overview

• Linear structures.
• Stacks.
• Lab.

Administrivia

• Welcome to any Discover Grinnell visitors who have chosen to visit our class.
• Current students: It's almost time for prereg. Have you thought about what you're going to do next in CS?
  • If you haven't taken Combo (MAT 218) or Discrete (MAT/CSC 208), you should take one of the two.
  • Software Design (CSC 323) delves deeper into the programming and program design side of CS, and meets a requirement for the major. I have no idea what Mr. Stone plans for next semester. It is also likely to be our last semester offering CSC 323 in this format.
  • Theory (CSC 341) delves deeper into the question of what is computable and how you model computation. If you've enjoyed our more formal work (and have the math prerequisites), you should consider that course. It is required for the major, so you'll need to plan to take it at some point.
  • Networks (CSC 364) is also a relatively hands-on course. It may be the last time we offer the course in this format. The course does not meet a requirement of the major.
  • If you want to claim that you're a competent C programmer, and you can deal with another semester with me, you should take CSC 295 (1 credit).
  • If you might want to do research with me, you should consider taking CSC 195. (Note, however, that I may prioritize first-year students.)
  • Beyond CS, you might consider Electronics. I also understand that Bridges, Towers, & Skyscrapers will be particularly cool next semester (although it doesn't have a lot of relevance to what we do)..
  • I'm amazed by the number of people who tell me that Monessa Cummins signficantly transformed their ability to write. Consider taking a course from her some time in your career.
• And as long as you're thinking about next semester, you should think about this coming summer.
  • CS Extra this week on Internships (I think)
  • CS Extra week 14 on "Things CS Students Might Do In The Summer"
  • Visit the CDO
  • Talk to your colleagues
• I'll leave time for questions on HW8.
• I've made some changes to the order of topics in the schedule.
• I've rethought our discussions on the project, and I really think all of you should attempt the project. (See more notes in the EBoard).
• We will visit the roundtable on the digital commons at 10 a.m. on Tuesday, 19 November.
• Upcoming extra credit opportunities:
  • One Grinnell Prize Event this week
  • Learning from Alumni, Thursday: Shitanshu Aggarwal '11
  • CS Extra, Thursday: Internships (I think)
  • Town Hall, Wednesday, November 13, noon or 7:30 p.m.
  • Digital Commons talk Monday, November 19, 7:00 p.m. or so

Linear Structures

• Simple collections.
• Two basic operations: put and get.
• Sam thinks of linear structures as a magic box. You give the box a policy for returning values and it folows that policy when you get something.

Stacks

• Linear structures with a "last in, first out" policy.
• Terminology: put is called push; get is called pop.
• Can be implemented with arrays or linked structures.

Lab

• Read, fix, use.