• Course Number: 16:198:508
  • Course Type: Graduate
  • Semester 1: Fall
  • Credits: 3
  • Description:

    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

    This course counts as category A for M.Sc. degree requirement. This course does NOT count as category A for Ph.D. students

  • M.S. Course Category: Algorithms & Complexity
  • Category: A (M.S.)
  • Topics:

    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).