Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Course Goals.
• Course Format.
• Approaching Algorithms.
• Problem: Getting From Here to There.
• Problem: Optimal Soldering Plans.
• Problem: Scheduling Overlapping Tasks.

Preliminaries

Admin

• 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.
• I may be using the white board more than in other classes, particularly since I will be drawing data structures. Do you want to share daily note-taking responsibilities?
• Friday PSA.

Upcoming Work

• For Monday: Read chapter 1 of Skienna.

Extra Credit

Academic

• CS Table, Tuesday, topic tbd.

Peer

• Look ahead to Jazz Concert on family weekend
• Critique YK's app
• Soccer vs. Simpson Saturday the 5th

Non-Extra Credit

• Candidate Sunday

Questions

Course Goals

• Build skills in designing
  • Algorithms
  • Abstract Data Types - Generalizations that we give to organizations of data - What you can do with the data, not how you do it. (Interface)
  • Data Structures (Class)
• Review "the literature"
  • Often with an active-learning approach
• More formally! Proof.
  • Correctness.
  • Running time
  • Minimum possible running time for a solution
• New techniques for designing algorithms
  • Randomness
  • Approximation (maybe)

Course Format

• Attempted active learning
  • Sam poses problems
  • Work in small groups to solve
  • Present solutions
  • Attempt to destroy solutions
  • Eventually ... read what others have done
• Regular homework. Don't worry, I have a grader.
• No mentor. Sniff.
• Three take-home exams.

Approaching Algorithms

• Decompose into simpler problems
• "Doodle code"
• Try on examples
• Try on more examples
• Write unit tests, while considering edge cases
• Implement in a programming language
• Analyze

• Attempt to improve

• Solve one instance of the problem

• Solve another instance of the problem
• Generalize the solution
• Try on examples
• Write unit tests
• Implement in a programming language

• ...

• Look for a similar problem you've already solved and adapt the solution

• Try on examples

• ...

• Attempt each of the algorithm design strategies you know

This semester, we add

• Try really hard to find examples that break the algorithm
• Prove the algorithm correct

Problem: Getting From Here to There

Given a collection of nodes (dots) and weighted edges (connections between the nodes), a designated source node, and a designated sink node, find the shortest path from the source to the sink.

Add a piece of information to each node: Length of the shortest known path from the source to that node. l(n)

Initially, l(source) = 0; l(n != source) = infinity

Maintain a collection, DONE, of nodes for which we've already determined the shortest path. These are ones we no longer have to visit. Initially, we should look at every node.

while nodes left in that collection choose the one with the smallest value, s look at each neighbor, n, not in DONE l(n) = min( l(s) + distance(s,n), l(n) )

Problem: Optimal Soldering Plans

Problem: Scheduling Overlapping Tasks