CME369 Theory on Computation and Visualization Syllabus:
CME369 Theory on Computation and Visualization Syllabus – Anna University Regulation 2021
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
Sets, Functions, Logical statements, Proofs, Relations, Languages, Principal of Mathematical Induction, Strong Principle, Recursive Definitions, Structural Induction.
UNIT – II REGULAR LANGUAGES AND FINITE AUTOMATA
Regular Expressions, Regular Languages, Application of Finite Automata, Automata with output – Moore machine & Mealy machine, Finite Automata, Memory requirement in a recognizer, Definitions, unionintersection 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
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
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
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.