Problem Set 5: Karma Problems

Due April 12, 2012


These Karma problems extend PS 5. We recommend that you attempt them only after you have completely finished the problem set itself. Each problem suggests an extension to one of the parts of PS 5. We have intentionally left the design, implementation, and evaluation is left open-ended. You should provide documentation in your code (e.g., in the form of a long comment) explaining your goals, and provide evidence (e.g., in the form of unit tests) that will let us check that you have achieved your goals in your code.

Karma 1: Concurrency Abstractions

On many platforms, the OCaml Threads module has a limit to how many threads can be spawned. In addition, the cost of starting a thread is non-trivial, so some programs will actually be made slower when written using threads. Design and implement a different concurrency abstraction that does not suffer from one or both of these limitations (e.g., a thread pool) and modify your sequence implementation to use it. For the purposes of analyzing work and span, you may define analogues of multi_create and multi_join and assume that they have O(1) work and span.

Karma 2: Floating Point

In general, performing floating-point operations in different order can lead to surprising results. For example:

# 10e30 +. (-10e30 +. 1.0);;
- : float = 0.
# (10e30 +. -10e30) +. 1.0;;
- : float = 1.
Design and implement a better version of the Plane module that does not suffer from these problems.

Karma 3: Collision and Verlet Integration

The mechanics used in the n-body problem ignore collisions, and also use a naive method to update the velocity and position in response to the gravitational forces on each body. Design and implement a version of your n-body simulation that correctly handles collisions and uses Verlet integration instead.

Karma 4: Cool N-Body Simulation

Design a cool n-body simulation!