Monday, January 16, 2012

Teaching algorithms: the concepts

The other day I saw a student studying a handout with a vocabulary list of figures of speech in English, with definitions and examples. For example, there was "Juvenalian irony" , "Metaphor", "Meter", etc. What struck me was that the list was in alphabetical order! What a way to teach! I started imagining what would happen if I organized my Algorithms class or my lecture notes using that principle. The reader would find topics in the following order:

Asymptotics
Average case
Big oh
Bipartite matching
Divide and conquer
Dynamic programming
Fast Fourier transforms
Greedy algorithms
Heaps
Huffman coding
Induction
Knapsack
Little oh
Matching
Max cut
Max flow
Median finding
Min cut
Minimum spanning tree
Randomized algorithms
Recurrences
Run time
Scheduling
Shortest paths
Sorting
Strassen's algorithm
Union find
Worst case

4 comments:

  1. Then I can search for particular topics in O(log n) time...

    ReplyDelete
  2. Sure, and if you're interested in shortest paths, you know to show up in class towards the end of the semester.

    ReplyDelete
  3. Oh my...... Actually, your list made me ponder (yet again) how worst case analysis is ingrained so deep in us.

    ReplyDelete
  4. i cant get max flow algos ,what do you recommend??

    ReplyDelete