This course introduces the theoretical foundations of computer science. These form the basis for a more complete understanding of, and proficiency in computer science. Topics include computational models, formal languages, and an introduction to computability and complexity theory, including NP-completeness. Students will be expected to complete a variety of exercises and proofs. Undergraduate credit may not be earned for both this course and for CS 5003. Students who have credit for CS 4123 may not receive credit for CS 3133.