Theoretical Foundations of Computer Science II

3 credits · Undergraduate Programs

Discrete probability spaces and distributions. Random variables, expectation, tail bounds. Independence and conditional probability. Repeated trials and algorithmic applications of probability theory. Languages, regular languages and regular expressions. Deterministic and nondeterministic finite automata. Turing machines. Reductions and methods for classifying computational problems as regular, decidable or undecidable. Prerequisite(s): 3 units from Computer Science 219, 233 or 235; and 3 units from Mathematics 249, 265 or 275; and 3 units from Philosophy 279 or 377; and 3 units from Computer Science 251 or 6 units from Statistics 213 and Mathematics 271 or 273. Antirequisite(s): Credit for Computer Science 351 and Computer Science 313 will not be allowed. Notes: As prerequisites for this course, Computer Science 251 may be replaced by a combination of Statistics 213 and one of Mathematics 271 or 273.