Held: Friday, 28 August 2015

On to Outline 02 - Asymptotic Analysis.

Summary

We begin to consider the core ideas of the course.

Related Pages

Overview

• Course Goals.
• Course Format.
• Approaching Algorithms.
• Problem: Getting From Here to There.
• Problem: Optimal Soldering Plans.
• Problem: Scheduling Overlapping Tasks.

Administrivia

• Attendance!
• The department has a new academic honesty policy, available at http://www.cs.grinnell.edu/academic-honesty-policy.
  
  • I expect all of you to read it.
  • I will probably ask you to sign something attesting to it.
  • Chat with me if you have questions about it.
• At some point in the near future signup for my office hours will be available at https://rebelsky.youcanbook.me.
• The class is in a bit rough shape. Expect it to evolve over the next few weeks.
• Do you want to assign daily note-takers?
• Friday PSA.

Upcoming Work

• For Monday: Read chapter 1 of Skienna.

Extra Credit

Academic

• CS Table, Tuesday, topic tbd.

Peer

• ???

Course Goals

• See the front door

Course Format

• Some lecture
• Lots of small-group/large-group problem solving
• I would prefer that you not read the book in advance. You learn the techniques better by trying to apply them than by just reading them. You learn key algorithms and data structures better if you've had to design them.

Approaching Algorithms

You are now experienced computer science students. When some gives you a problem that admits algorithms solution, what do you do?

• Here's one approach
  • Try some examples by hand
  • Attempt to generalize your solution
  • Try the generalized solution on other problems
  • Write some unit tests
  • Turn the generalized solution into code
  • Analyze the algorithm
  • Try to improve
• Here's another approach
  • Find a related problem and related solution
  • Adapt the solution
  • Try the adapted solution on other problems
  • Write some unit tests
  • Turn the generalized solution into code
  • Analyze the algorithm
  • Try to improve
• We are going to add a few important steps
  • Try to break the algorithm. Think carefully about situations in which it will fail (or fail to work quickly)
  • Prove the algorithm correct

Problem: Getting From Here to There

• Let's pretend that net neturality fails.
• We now have a problem: We need to get information from place to place, and we may want the least expensive path, or the quickest, or ...
• We model the problem

Problem: Optimal Soldering Plans

Stolen/modified from Skienna

• We have a bunch of points that we need to have a robot solder a circuit board.
• We want the least wear and tear on the robot

Problem: Scheduling Overlapping Tasks

Stolen/modified from Skienna