Welcome to MATH 8650: Advanced Data Structures (Fall 2015)
Instructor: Dr. Timo Heister, heister@clemson.edu, http://www.math.clemson.edu/~heister/
Meeting time: Tue/Thu 12:30pm1:45pm, Martin M204
Please contact me via email for questions, appointments, etc..
Course Description
This course is designed to introduce students to advanced data structures and algorithms from computer science. The goal is to provide a solid foundation for sophisticated software development, research in computational mathematics, and other computational problems.
We will be using the Python programming language for weekly exercises and larger group projects.
Handouts and Resources
 This site: http://www.math.clemson.edu/~heister/math8650fall2015/
 Blackboard: http://bb.clemson.edu (grades, materials, etc.)
 No required textbox. Reading material will be supplied.
 Syllabus
Files:
Notes

About CPUs, memory speeds, caches, and optimization:
 CPUs over time:
 latency numbers: https://gist.github.com/hellerbarde/2843375
 complexity spreadsheet: https://goo.gl/CA9gIi
 caches: https://en.wikipedia.org/wiki/CPU_cache
 memory hierarchy: https://en.wikipedia.org/wiki/Memory_hierarchy
 std vector vs std list (and caches): http://baptistewicht.com/posts/2012/12/cppbenchmarkvectorlistdeque.html
 Premature optimization: http://c2.com/cgi/wiki?PrematureOptimization
Projects
 deadline: Dec 1, before class
 groups of two to three
 deliverables: code, ~2 page written report, 15 minute presentation

Grading:
 Code: documented, object oriented, well structured, automated tests
 Presentation: adequate introduction to topic, show results
 Report: problem summary, solution, difficulties encountered, literature

Projects: can pick your own, should deal with:
 complexity, performance
 data structures

Suggested projects:
 Board game with AI, minimax strategy, game trees (quarto, checkers, nim, tictactoe, connect5, 4 in a row in 3d, endgame chess)
 Solvers/generators for Mathematical puzzles (conway, sudoku, Str8ts, Kakuro, …)
 Path finding: A* vs Dijkstra
 Redblack trees, selfbalancing trees
 Efficient delaunay mesh triangulation
 Weighted Quickunion with path compression (performance comparisons)
 Graph partioning/coloring (minimum kcut, Kernighanâ€“Lin algorithm?)
Class Schedule
See http://www.registrar.clemson.edu/pdf/academicCalendar2015.pdf and http://www.registrar.clemson.edu/html/examSched.htm for important dates.
Date: 20160818 08:09:04 EDT
HTML generated by orgmode 6.33x in emacs 23