## CME369 Syllabus - Theory On Computation And Visualization - 2021 Regulation Anna University

CME369

THEORY ON COMPUTATION AND VISUALIZATION

L T P C

3003

COURSE OBJECTIVES:
1 To study the concepts and techniques of discrete mathematics for theoretical computer science.
2 To learn different formal languages and their relationship.
3 To classify and construct grammars for different languages and vice-versa.
4 To study Visualization, Graphical and Quantitative Information.
5 To learn Visualization design and data Ink.

UNIT I

REVIEW OF MATHEMATICAL THEORY

9

Sets, Functions, Logical statements, Proofs, Relations, Languages, Principal of Mathematical Induction, Strong Principle, Recursive Definitions, Structural Induction.

UNIT II

REGULAR LANGUAGES AND FINITE AUTOMATA

9

Regular Expressions, Regular Languages, Application of Finite Automata, Automata with output – Moore machine & Mealy machine, Finite Automata, Memory requirement in a recognizer, Definitions, union- intersection and complement of regular languages, Non Deterministic Finite Automata, Conversion from NFA to FA, ??- Non Deterministic Finite Automata, Conversion of NFA- ? to NFA, Kleene’s Theorem, Minimization of Finite automata, Regular And Non Regular Languages – pumping lemma.

UNIT III

CONTEXT FREE GRAMMAR (CFG) AND PUSHDOWN AUTOMATA

9

Definitions and Examples, Unions Concatenations And Kleene’s of Context free language, Regular Grammar for Regular Language, Derivations and Ambiguity , Unambiguous CFG and Algebraic Expressions, BacosNaur Form (BNF), Normal Form – CNF. Definitions, Deterministic PDA, Equivalence of CFG and PDA & Conversion, Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL.

UNIT IV

VALUE OF VISUALIZATION

9

Information Visualization, In Readings in Information Visualization, Graphical Excellence, Graphical Integrity, Sources of Graphical Integrity In The Visual Display of Quantitative Information

UNIT V

VISUALIZATION DESIGN

9

The Power of Representation, Data-Ink and Graphical Redesign, Data-Ink Maximization and Graphical Design, Data Density and Small Multiples

TOTAL: 45 PERIODS

OUTCOMES: At the end of the course the students would be able to
1. Discussing the concepts and techniques of discrete mathematics for theoretical computer science.
2. Explain the different formal languages and their relationship.
3. Discussing to classify and construct grammars for different languages and vice-versa.
4. Explaining the Visualization, Graphical and Quantitative Information.
5. Appling the Visualization design and data Ink.

TEXT BOOKS:
1. Introduction to the Theory of Computation by Michael Sipser
2. Automata Theory, Languages, and Computation By John Hopcroft, Rajeev Motowani, and Jeffrey Ullman

REFERENCES:
1. Introduction to Languages and the Theory of Computation, 4th by John Martin, Tata Mc Graw Hill
2. An introduction to automata theory and formal languages By Adesh K. Pandey, Publisher: S.K. Kataria& Sons
3. Introduction to computer theory By Deniel I. Cohen , Joh Wiley & Sons, Inc
4. Computation: Finite and Infinite By Marvin L. Minsky Prentice-Hall.