CS 5800

 
 

Syllabus

 

[ home ] [ syllabus ] [ class list ] [ references ] [ projects ] [ assignments ]

 


Topics

Topics/modules with Bloom classifications are listed below:

  • K = Know the terminology
  • C = Comprehend so as to paraphrase/illustrate
  • A = Apply it in some way, in homework assignments or projects
  • N = Elective

Review of discrete mathematics and proof methods (A), cardinality/countability (C)
Formal languages, the Chomsky hierarchy: languages, their grammars, and automata (regular (A), CFL (A), CSL (K), recursive enumerable (C)), their grammars, and automata (D/NFA (A), PDA (A), LBA (K), TM (A)), stochastic automata (Markov models (N))
Undecidability: Church-Turing thesis (C); some undecidable problems (C), reductions (K), relation to recursive enumerable (r.e.) languages (C), recursive languages (C), Turing machines (C)
Intractable problems, complexity: Non-deterministic time and space complexity (C), Polynomial time and space, classes P and NP (C), some NP-Complete problems (K)
Applications to compiling: lexical analysis (C), parsing (C), (LL(k), LR(k) (N)), ambiguity (C)
Models of computation: lambda-calculus (N) (in relation to functional languages), (partial-) recursive functions (C), Markov algorithms (N) (in relation to logic programming languages), cellular automata (N)

Learning outcomes

  • A. General learning outcomes:

    • Reinforce analytic development and problem solving abilities, and develop a foundation in computer science.
    • Show progress with regard to understanding the theory of computation (for use, e.g., in further graduate level courses), including knowledge and use of terminology and how the theory connects with real-world applications, possibly in different and new areas.
    • Apply the concepts covered in the course to written and practical problems, e.g., by combining problem solving with computer programming and the use of software tools as part of assignments and a semester project. The latter may be done in teams or individually.

  • B. Content specific outcomes:
    (for students who earn a grade of B or better):

    • The students will demonstrate an introductory to intermediate-level knowledge of definitions and theorems for problem solving relating to automata, grammars and formal languages.
    • Students will demonstrate the ability to apply proof techniques and other mathematical concepts, as well as algorithms to questions concerning automata, grammars and languages.
    • The students will demonstrate knowledge of the theory of computability/ decidability.
    • Students will demonstrate the ability to synthesize knowledge and use tools of automata, grammars and computational models to solve problems relating to language specification and machine computation.

 

[ home ] [ syllabus ] [ class list ] [ references ] [ projects ] [ assignments ]