Theory of Computation - Syllabus

Review of fundamental concepts in set theory, logic, functions, and proofs, including set operations, propositional and predicate logic, function definitions, and proof techniques.

Introduction to automata theory, computability theory, and complexity theory, including the study of automata, Turing machines, and complexity classes.

Foundational concepts in automata theory, including alphabets, power of alphabet, Kleene closure, positive closure, strings, empty strings, substrings, concatenation, languages, and empty languages.

Overview of E-commerce and its significance in the digital age.

Understanding the differences between E-business and E-commerce.

Key characteristics and benefits of E-commerce.

Types of E-commerce models and their applications.

Evolution and development of E-commerce over time.

Understanding the components of E-commerce framework including People, Public Policy, Marketing and Advertisement, Support Services, and Business Partnerships.

Learn how to design relational databases using ER-to-relational mapping, including mapping of regular entities, weak entities, relationship types, multivalued attributes, and N-ary relationships.

Understand informal design guidelines for relational schemas, including semantics of attributes in relations, redundant information in tuples and update anomalies, NULL values in tuples, and generation of spurious tuples.

Study functional dependencies, including definition, inference rules, Armstrong's axioms, attribute closure, equivalence of functional dependencies, and minimal sets of functional dependencies.

Explore normal forms based on primary keys, including First Normal Form, Second Normal Form, Third Normal Form, and their general definitions.

Learn about Boyce-Codd Normal Form, a higher normal form that ensures a relational schema is in a good structure.

The internship work should be relevant to the field of computer science and information technology, with a minimum duration of 180 hours or ten weeks.

The internship evaluation consists of three phases: Proposal Submission, Mid-Term Submission, and Final Submission.

A regular faculty member of the college is assigned as a supervisor to supervise the students throughout the internship period.

A regular employee of the intern providing organization is assigned as a mentor to guide the students throughout the internship period.

The evaluation scheme consists of Proposal Defense, Midterm, and Final Defense, with a total of 200 marks.

The internship report should contain prescribed content flow, including introduction, problem statement, objectives, and references.

This topic introduces Push Down Automata (PDA), its representation, operations, and instantaneous description.

This topic covers deterministic and non-deterministic PDA, acceptance of strings, and language of PDA.

This topic explains the construction of PDA by final state and by empty stack.

This topic covers the conversion of PDA by final state to PDA accepting by empty stack and vice-versa.

This topic explains the conversion of Context-Free Grammar (CFG) to PDA and vice-versa.

This topic introduces the basic concepts of Turing Machines, including notations, language, instantaneous description, and acceptance of strings.

This topic explores the role of Turing Machines as language recognizers, computing functions, and enumerators of strings of a language.

This topic covers variations of Turing Machines, including those with multiple tracks, multiple tapes, non-deterministic, and restricted Turing Machines.

This topic discusses the Church-Turing Thesis, which states that any effectively calculable function can be computed by a Turing Machine.

This topic introduces the concept of a Universal Turing Machine, which can simulate the behavior of any other Turing Machine.

This topic covers the encoding of Turing Machines, enumerating binary strings, and the use of Universal Turing Machines for encoding.

E-readiness refers to the state of preparedness of a country or organization to participate in the digital economy. It involves assessing the availability and quality of digital system infrastructure, legal frameworks, institutional arrangements, human resources, and technological capabilities.

The evolutionary stages in e-governance refer to the different phases of development and implementation of e-governance initiatives, from basic online presence to integrated and transformative e-governance systems.

Bridges and routers in distributed networking, enabling communication between different networks.

History and development of the internet, including its design principles and evolution over time.