18.4x

Theoretical Computer Science

There are two basic subjects on the theory of computational complexity:

  • 18.400J/6.045J (Automata, Computability, and Complexity) is slower paced than 6.840J/18.404J.
  • 18.404J/6.840J (Theory of Computation) is a more extensive and theoretical treatment of the material of 6.045J/18.400J.

Both 18.400J and 18.404J have 18.062J/6.042 as a prerequisite, though 18.404J allows a substitution of 18.310. 18.404J is listed as a graduate subject and carries graduate credit for students outside Course 18, but it has the structure of a standard undergraduate subject.

The study of algorithms is taken up by 18.410J/6.046J. It requires 6.006, or, from the older Course 6 sequence, 6.001 and either 18.062/6.042 or 18.310.

There are two Undergraduate Seminars in this area:

  • 18.424 (Seminar in Information Theory) requiring a subject in probability and a subject in linear algebra.
  • 18.434 (Seminar in Theoretical Computer Science) requiring 18.404J and 18.410J.

Probability and Statistics

Many subjects at MIT require acquaintance with probability or statistics, and there are several options for gaining this expertise. The principal ones are 18.05, 6.041, and 18.440. Here is a brief comparison of these three subjects.

  • 18.05 (Introduction to Probability and Statistics) has only 18.01 as a prereqisite: it is an "elementary introduction with applications" to both probability and statistics.
  • 6.041 (Probabilistic Systems Analysis) has 18.02 as a prerequisite. It is "an introduction to probability theory, and modeling and analysis of probabilistic systems," which also includes a treatment of the "elements of statistical inference."
  • 18.440 (Probability and Random Variables) also has 18.02 as prerequisite. It covers a broader range of topics in probability, at greater depth than either 18.05 or 6.041, and it is the probability subject of choice for most Mathematics majors. 18.443 is a companion subject on statistics, accepting either 18.440 or 6.041 as prerequisite.