Overview

• Preliminaries.
  • Admin.
  • Thinking about next semester.
  • Thinking about summer.
  • HW 8.
• Linear structures.
• Stacks.
• Reverse Polish Notation.
• Lab.

Preliminaries

Admin

• Welcome to any Discover Grinnell visitors who have chosen to visit our class.
  • Meet our prospectives
  • Why should they come to Grinnell rather than big schools?
    • We're small
    • People don't blindly obey
    • People here are surprisingly worthwhile
• 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.
• We will visit the roundtable on the digital commons at 10 a.m. on Tuesday, 19 November.
• Upcoming extra credit opportunities:
  • Kate Kearney talk noon today in Math
  • 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

Thinking About Next Semester

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.

Thinking About Summer

As long as you're thinking about next semester, you might want to start thinking beyond next semester. What will you do 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 CLS
• Talk to your colleagues

HW 8

Any comments on iterative merge sort?

Professor Walker has been talking a lot about memory efficiency. You may find it useful to build one helper array (of size N) where you copy values before merging back into the main array. (The typical strategy is to copy the first half of the section to be merged into the helper array, and then you can merge back in place.)

_There's a bug in Sam's Quicksort

Thanks AK. I'll fix.

_Can you cut problems 5-8?

Done.

Linear structures

Stacks

Reverse Polish Notation

• A stack-based calculation model
• Unambiguous!
• See a number: PUsh it
• See an operation: Pop operands, evaluate, push result
• 3 4 5 + 6 - *
• dc in Mathlan

Lab