Syllabus for Experimental Combinatorics CS7083

Syllabus for CS7083 – Experimental Combinatorics

CS7083 – Spring 2016
Professor Fred Annexstein
OLDCHEM 811B (6-1807)
fred.annexstein@uc.edu

Meeting Times: TuThurs 11:00a – 12:20pm in BALDWIN 661?

Course Summary

Goals: This course is designed as a graduate research level course covering topics in combinatorial computational science, functional programming and computer-math experimentation.

This course will cover methods and algorithms for generating a variety of combinatorial objects and answering combinatorial questions using computer-programming experiments. Topics will include modeling and generating experiments in a variety of areas of computational science, including classical simulations and mathematical games: conway’s game-of-life, generating music and chordal progressions, using permutations, combinations, partitions, selections and necklaces; and generating important network structures using graphs and codes, e.g., small-world and expander graphs. Students are also encouraged to suggest research topics.

Grading: There are no exams. Grades will be based on class participation (10%), class presentations (20%), two midterm projects (20%) and one final project (30%).

This course will have both lectures and student presentations and discussion. Students will be expected to (a) present and lead discussions on classical and recently published papers in the area of combinatorial scientific computing; (b) design and carry out research on at least two topics related to combinatorial computing and generating combinatorial objects. The instructor will provide reference material, appropriate papers, potential projects and experimental tools. Mid-term and final projects are open-ended but should be carried out in consultation with the instructor.

Prerequisites: Advanced Algorithms I (20-EECS-7081) or permission of instructor.

Topics:

1. Introduction to Computational Science and Experimental Combinatorics
2. The Clojure Programming Language and Ecosphere
3. Computational Natural Science
   1. Darwin’s Metaphors for Biology
   2. Conway’s Game-of-Life
   3. Formal writing systems L-systems and fractals
4. Computational Social Science
   1. Ranking and Relevance: Voting , Comparisons, and Hotness, Critic Synthesis
   2. Communication in Music: chords and scales, representations and enumerations, necklaces, Polya’s Theorem, Wave transformations
5. Computational Games and Codes
   1. Combinatorial Games, Rubik’s Cube, Nim
   2. Gray codes, DeBruijn Sequences, Hamming spheres.
6. Computational Geometry and Symmetry,
   1. N-Queens and Isomorph Rejection
   2. Self-Similarity and Tiles
   3. Cayley Graphs, Latin Squares, Penrose Tiles
   4. Graphs and Networks: Planer graphs, Expander graphs, Small-World and Power-law graphs, Centrality and Balance