Advanced Algorithms Honors

Syllabus:

Books:

1. Main course book: “Grokking Algorithms”, Aditya Y. Bhargava, 2016. ISBN 978-1617292231
2. “Numerical recipes in C”, W. Press et. Al, 1992. We will mostly use Chapter 2 (Solution of linear algebraic equations) and Chapter 9 (Root finding). ISBN 978-0521431088
3. “Pearls of functional algorithm design”, Richard Bird, 2010. We will mostly use chapters 18 and 19 dealing with Games-AI. ISBN 978-0521513388.

• All classroom material is distributed through Github Classroom.
You need a github account for this.
• We program together in class, and then links are given to students for the classroom assignment.

What we actually did 2018-2019:

1. Numerical algorithms:
   1. Gauss Jordan elimination - Inverse matrix, solving set of equations.
   2. Numerical integration - Mid-point, Trapezoid, Simpson's rule (adaptive splitting), Adaptive quadrature
   3. Step-wise solution of PDE (trajectory)
2. O(n) : Euler 461
3. AI games
   1. 8Queens (--> 10, 12) - Enumeration, greedy.
   2. MineSweeper (!!)
4. Various algorithms:
   1. Dijkstra
   2. Depth first, Breadth first.
   3. Maze
   4. shortest path on a grid, shortest path on a grid with obstacles.
5. Dynamic programming: Recursion and table:
   1. Coins change
   2. Edit distance
   3. Game of 10
6. Markov chains: Random words / text generator
   1. Simple histogram table for words (letters probability)
   2. Hash map for words probability

Course outline:

1. Intro and setup. In class activity: Syllabus. Installation.
2. Taxicab numbers: Exercise. Ramanujan and Hardy. [ github]



3. Numerical alorithms : Introduction to algorithms
   1. Gauss-Jordan : Solution of system of equations.
      1. Gauss elimination: 2x2 ; General case.
      2. Gauss-Jordan: General case.
   2. Newton-Raphson : Finding the zero of a function.
   3. Time/memory : Closest sum exercise.



4. Dynamic programming : String matching
   1. Levenshtein distance.
   2. Smith-Waterman algorithm.
   3. Exercises with dynamic programming:
      1. Exact change
      2. Partitioning a set of integers into two groups of equal sum



5. Graph algorithms
   1. Graphs, and graph representation.
   2. Dijkstra : shortest distance.
   3. Minimu spanning trees
   4. Depth first/ breadth first traversal
   5. 8 queens problem