A capstone course in which students design and implement a compiler as an application of the principles of software engineering, formal language theory, algorithms and data structures. Topics include lexical analysis, parsing, symbol table management, code generation and optimization and use of compiler tools.
Prerequisite(s): Grades of "C" or better in CMPSC 2410 Data Structures and CMPSC 3000 Formal Languages and Automata.
A natural continuation of CMPSC 1500 Program Design concentrating on the motivation, design, implementation, and utilization of abstract data types. Topics include linked lists, stacks, queues, trees, and recursion. A lab component is incorporated.
Prerequisite(s): Grade of "C" or better in CMPSC 1500 Program Design.
(Normally offered each spring semester.)
An overview of formal models of computation and complexity classes. Topics include formal languages (finite automata, regular expressions, push-down automata, context-free grammars, and Turing machines), Church's thesis, computability, non-determinism, and NP-completeness. Same as MATH 3000 Formal Languages and Automata.
Prerequisite(s): Grade of "C" or better in either CMPSC 1500 Program Design or MATH 2200 Introduction to Higher Mathematics and junior standing.