Course overview

• The one-sentence summary of this class is that this is about done efficient procedures for solving problems on large inputs.
• Efficient procedures for solving large scale problems.
• scalability is important.
• Classic data structures.
• Classical algorithms.
• Real implementations in Python.

Content

• 8 modules:
  1. Algorithmic thinking.
  • Sorting & trees: Event Simulation.
  • Hashing: Genome Compparison
  • Numerics: RSA encryptioon
  • Graphs: Rubik's Cube
  • Shortest paths:
  • Dynamic programming:
  • Advanced topics:

Peak finding

• One-dimensional version.

a-i are numbers
Position 2 is a peak if and only if b >= a and b >= c
Position 9 is a peak if and only if i >= h
Problem: Find the peak if it exists

Peak Finding