| Instructor | Dr. Andreas Klappenecker |
| Where | HRBB 104 |
| When | Monday, Wednesday 1:40pm-2:50pm, occasionally Fridays |
| Office | HRBB, Room 509B |
| Office Hours | M 3:00pm-4:00pm, T 2:00pm-3:00pm |
| klappi @ cs.tamu.edu | |
| Course Information | Syllabus |
| This course discusses fundamental data structures and algorithms. The goals of this course include correctness proofs of algorithms and the analysis of algorithms. Basic design techniques for algorithms, such as divide and conquer, dynamic programming, and greedy algorithms, will be explored. This course will conclude with an introduction to complexity theory. Teams of 2-3 students will explore current algorithmic research topics, and perhaps even produce a publication. |
| - Analysis of algorithms is challenging, but also a lot of fun! |
| - Learn more about the professor at www.pickaprof.com. |
| - Each time I teach a class, I prepare the material anew; this is what I had covered last year. |
| M | Aug 28 | Introduction, Euclidean Algorithm, Proofs |
| W | Aug 30 | Extended Euclidean Algorithm, Correctness Proofs |
| F | Sep 01 | Big Oh Notation, Estimating the Running Time of Programs, Asymptotics |
| M | Sep 04 | Asymptotics |
| W | Sep 06 | Sums, Lower bounds for Comparison Sorting, Quiz |
| M | Sep 11 | Quicksort, Divide and Conquer Algorithms |
| W | Sep 13 | Quicksort, worst case and best case running time, expected running time |
| M | Sep 18 | Max-Heaps, Heapsort |
| W | Sep 20 | Order Statistics |
| M | Sep 25 | Order Statistics |
| W | Sep 27 | The Master Theorem |
| M | Oct 02 | Hashing with Chaining |
| W | Oct 04 | Open-address Hashing |
| M | Oct 09 | Open-address Hashing, Red-Black Trees |
| W | Oct 11 | Red-Black Trees, Quiz |
| M | Oct 16 | Review |
| W | Oct 18 | Exam |
| M | Oct 23 | Dynamic Programming, Matrix Chain Multiplication |
| W | Oct 25 | Longest Common Subsequence |
| M | Oct 30 | Greedy algorithms, Huffman codes |
| W | Nov 01 | Matroids |
- Proofs
- The Extended Euclidean Algorithm