Tue March 26

Welcome back ...

I'd like to go over your midterm projects.

• Kat - Floyd-Warshall
• Nate - Prim's
• Cyrus - Floyd-Warshall
• Jimmy - A*
• ...

We'll see how far we get with the rest of this.

review - big ideas

• analysis of algorithms
  • big O()
  • log < linear or poly < exponential (time)
  • tradeoffs : space (memory) vs time
• data structures
  • API vs implementation
  • stack and queue
  • links vs indeces
  • min heap
  • hash table
  • binary tree
• approaches
  • brute force (all possibilities, includes combinatorics & backtracking)
  • greedy (head towards goal)
  • divide and conquer (reduce problem, usually by 1/2)
• typical problems
  • numbers
  • strings
  • trees and graphs

where we're going next

• dynamic programming : an important but tricky approach
• compression : some information theory topics (huffman, LZW, jpeg & DCT)
• some crypto ... depending on time
• final projects ... research, implement, test, discuss an algorithm ... a>