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:30pm-1: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/math8650-fall2015/
- 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://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.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, tic-tac-toe, connect5, 4 in a row in 3d, endgame chess)
- Solvers/generators for Mathematical puzzles (conway, sudoku, Str8ts, Kakuro, …)
- Path finding: A* vs Dijkstra
- Red-black trees, self-balancing trees
- Efficient delaunay mesh triangulation
- Weighted Quick-union with path compression (performance comparisons)
- Graph partioning/coloring (minimum k-cut, 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: 2016-08-18 08:09:04 EDT
HTML generated by org-mode 6.33x in emacs 23