Algorithms and homework to aid my study of algorithms class.

• Fibonacci
• Big(O)
• Numbers of digits from base to base

• Addition/Subtraction (running times)
• Multiplication/Division (running times)
• Modular Arithmetic
  • Standard : Addition, Subtraction, Multiplication
  • Fast : Exponentiation
  • Slow : Division
  • Finding modular inverse
• RSA algorithm
• Hashing <- Not covered

• Fast multipilcation
• Master's Theorem
• Binary Search
• Mergesort (Recursive and iterative) (show it is optimal)
• Median Finding (Using probablity to give number of steps on average)
• Fast matrix multiplication (Strassen Algorithm)

• Depth First Search
  • Pre and Post ordering
• Directed Acyclic Graphs, DAGs
• Strongly Connected components

• Breadth first search
  • Alarm clock algorithm (Preparation for Djikstra)
• Dijkstra's algorithm
• Proofs of correctness

• Kurskal's algorithm
• The cut property
  • Proof of the cut property
• Prim's algorithm

• Shortest path in a dag
• All dp questions are implicit dags
• Longest increasing subsequence
• Manhattan tourist problem
• Longest common subsequence
• Edit text

Class Textbook: Algorithms Sanjoy Dasgupta