www.cs.amherst/~ccm/cs40/syllabus.html

CS40 Course Syllabus

What matters most to performance?

• Discussion, Readings, In-class practice
  • What are the sources of program efficiency: algorithmic, runtime constants, faster compilers, operating systems? How much does each factor contribute, in proportion. Have these factors changed over time? Will they change in the future?
  • How much impact does the memory heirarchy have on performance (cacheing, pageing, big data sets).
  • How does Internet computation differ from in-machine computation (communication costs, big data problems, etc)?
  • Application Case Studies (selected by students): Internet, Data Mining, Communication algorithms, the Human Genome Project, etc.

  • 1.Appel's 1981 paper on algorithms for many-body simulation.
  • 1. Bentley's chapter commenting on Appel's work.
  • 1. Anderson et al's recent work on many-body simulation problems.
  • 2. Bentley, ``Faster and faster and faster.''
  • 2. Bentley, ``Writing Efficient Code.''
  • 3. LaMarca and Ladner's work on memory-sensitive data structures.
  • 4. Anderson's paper on Big Data and a map-generation problem.
  • 4. Other papers selected by students.

  • Practice: Library skills, how to find research papers.
  • Practice: How to do runtime experiments in Unix
  • Practice: Apply Bentley's program speedups.
  • Practice: Selecting and building instance generators.
  • Practice: Designing fair runtime tests.

• Project (First Assignment)
  • Implement an algorithm for all pairs shortest paths (or similar problem on graphs). Time it. Apply all the speedup tricks you have learned, or at least the ones most likely to succeed. Time it again. Present your results.