- Course Number: 01:198:452
- Course Type: Undergraduate
- Semester 1: Spring
- Credits: 3
To provide a rigorous mathematical framework for two general areas: that of language description and that of computation; to examine the relation between the two and to consider practical applications from Computer Science and Linguistics. Computability theory and complexity theory are also introduced. Students who plan to pursue a graduate degree incomputer science are strongly encouraged to take 01:198:452.
- Prerequisite Information:
- A grade below a "C" in a prerequisite course will not satisfy that prerequisite requirement.
- Course Links: 01:198:344 - Design and Analysis of Computer Algorithms
Regular languages and automata
Context-free languages and Pushdown Automata
Turing Machines and Decidability
Hierarchies and properties of language families
Computational Complexity Theory
- Expected Work: weekly homework
- Exams: 1 midterm and a final exam
- Learning Goals:
Computer Science majors ...
- will be prepared to contribute to a rapidly changing field by acquiring a thorough grounding in the core principles and foundations of computer science (e.g., techniques of program design, creation, and testing; key aspects of computer hardware; algorithmic principles).
- will acquire a deeper understanding on (elective) topics of more specialized interest, and be able to critically review, assess, and communicate current developments in the field.
- will be prepared for the next step in their careers, for example, by having done a research project (for those headed to graduate school), a programming project (for those going into the software industry), or some sort of business plan (for those going into startups).