Welcome to CSL318

Theory of Computation
Vision and Mission of the University

To be known globally for learning innovations, academic excellence

and socially relevant research outcomes; strive to become the
preferred destination for students, faculty, employers and
collaborators & pride of alumni and the community.

• Focus on quality of learning and innovation in all programmes with

rigour and relevance.
• Develop competent professionals-innovative, analytical and
independent; committed to excel in all their endeavours.
• Develop linkages globally with government, industry, academia and
alumni for knowledge generation, dissemination and application.
• Encourage multi-disciplinarity in programmes and projects to
explore new frontiers of knowledge.
• Continuously improve physical, academic and information
infrastructure in pursuit of academic excellence.
• Create a nurturing environment for lifelong learning.
• Focus on entrepreneurship and socially relevant projects.
Vision and Mission of the Department

Department of Computer Science Engineering (CSE) encourages all

modern endeavors in academia, learning innovations, socially
relevant research and problem solving. The department aims at
being recognized universally as a promoter of computing
technologies and their applications.

• Develop competent professionals with analytical skills and independent thinking,

through excellent undergraduate and graduate education for productive career in
industry, academia and administration.
•To enhance theoretical, experimental and applied skills of faculty and students in
Computer Science Engineering & Information Technology through nationally and
internationally recognized research.
•Continuously improve physical, academic information and computing infrastructure.
•Support society by focusing on entrepreneurship and socially relevant projects.
•Create a nurturing environment for lifelong learning skills
Programme Outcomes
1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering fundamentals, and an engineering specialization to the solution of complex engineering problems.

2. Problem analysis: Identify, formulate, review research literature and analyze complex engineering problems reaching substantiated conclusions using first principles of mathematics, natural
and engineering sciences.

3. Design/development of solutions: Design solutions for complex engineering problems and design system components or processes that meet a specific requirement with appropriate
consideration for the public health and safety and the cultural, societal and environmental considerations.

4. Conduct investigations for the complex problems: Use research-based knowledge and research methods including design of experiments, analysis and interpretation of data and synthesis of
the information to provide valid conclusions.

5. Modern tool usage: Create, select and apply appropriate techniques, resources and modern engineering and IT tools including prediction and modeling to complex engineering activities
with an understanding of the limitations.

6. The engineer and society: Apply reasoning informed by the contextual knowledge to assess societal, health, safety, legal and cultural issues and the consequent responsibilities relevant to
the professional engineering practice.

7. Environment and sustainability: Understand the impact of the professional engineering solutions in societal and environmental contexts, and demonstrate the knowledge of and need for
sustainable development.

8. Professional Ethics: Apply ethical principles and commit to professional ethics and responsibilities and norms of the engineering practice.

9. Individual and team work: Function effectively as an individual and as a member or leader in diverse teams and in multidisciplinary settings.

10. Communication: Communicate effectively on complex engineering activities with the engineering community and with the society at large. Will be able to comprehend and write effective
reports and design documentation, making effective presentations and guide with themselves and others with clear instructions.

11. Project management and finance: Demonstrate knowledge and understanding of the engineering and management principles and apply these to one’s own work being a member and
leader in a team, to manage projects and in multidisciplinary environments.

12. Life-long learning: Recognize the need for and have the preparation and ability to engage in independent and life-long learning in the broad context of technological change.
Programme Specific Outcomes & Programme Educational
Objectives

Programme Specific Outcomes

PSO 1 Understand the fundamental concepts of Computer Science & Engineering with specialized engineering
knowledge in the areas of data science, artificial intelligence, full stack, web development, gaming,
augmented reality and virtual reality.

PSO 2 Design and Integrate hardware and software systems in the areas of IOT, cloud computing, cyber security with
strong emphasis on lifelong learning to create feasible engineering solutions for the advancement of society.

PSO 3 Enable the students for premium National/International jobs, higher education, entrepreneurship and to
become responsible global citizens.

Programme Educational Objectives

PEO1 To provide an in-depth understanding of the fundamentals of Computer Science and create a foundation of
lifelong learning to facilitate progressive careers in industry and in pursuit of higher studies.
PEO2 To equip our students with technical and analytical skills to develop innovative solutions to complex real-life
problems suing existing and novel technologies.
PEO3 To equip our students with sufficient communication & interpersonal skills, multi-disciplinary teamwork and
leadership skills to enable them to fulfill professional responsibilities.
PEO4 To expose them to various contemporary issues which will enable them become ethical and responsible
towards themselves, co-workers, the Society and the Nation.
Course Outcomes

Course Outcomes (COs)

On successful completion of this course students will be able to:

Articulate the mathematical foundations of computation including automata theory CO1

Describe the notion related to formal languages and grammar CO2

Identify and Assess the concepts , design of pushdown automata CO3

Explain the concept of turing machine and its working, design and applicability among students. CO4

Understand the notions of algorithm, decidability, complexity, and computability CO5

CO-PO/PSO Attainment
• Aligning program level outcomes with course-level outcomes.
• This level of outcomes mapping focuses on student learning.
• It helps faculty to assess how students are meeting program-level outcomes at the course level.

CO-PO/PSO
Attainment

Direct Indirect
Method Method
(80%) (20%)

Mapping CO-
Surveys
PO&PSO for
each course

Continuous Student
Semester End Alumni
Internal Survey
Exam (45%) Survey
Exam (55%)
Syllabus

L-T-P: 3-2-0, Credits: 4

• Refer to Course Template

Reference Material/Resources

Brief Description of Self-learning 1. Pumping Lema for Regular Sets, Problems based on Pumping Lemma
components by students (through 2. Greiback Normal Form, Chomsky Normal Form, Problems related to CNF
books/resource material etc.) and GNF
3. Pumping Lema for CFL, Problems based on Pumping Lemma
4. Turing Machine Constructions, Modification of Turing Machines
5. NP hard graph and NP scheduling problems some simplified NP hard
problems
Text Books:
Books recommended 1. “Introduction to Automata Theory, Languages and Computations”,
Hopcroft J.E., Motwani R. and Ullman J.D, Third Edition, Pearson Education,
2008.
Reference Books:
1. “An Introduction to Formal Languages and Automata”, Peter Linz,
Sixth Edition, Jones and Bartlett, 2016
2. “Introduction to The Theory of Computation”, Michael Sipser, Third
Edition, Cengage Learning, 2014

NPTEL Swayam Course:

Advance Learning Components
https://nptel.ac.in/courses/106104148/
Evaluation Scheme

ALLOTTED
TYPE OF COURSE PARTICULAR RANGE OF PASS CRITERIA
MARKS
Minor Test 25
Major Test 45
Continuous Evaluation Must Secure 30% Marks Out of Combined
Blended MOOC Through Class
20 Marks of Major Test Plus Minor Test with
(L-T-P/L-T-0) Tests/Practice/Assignm
ents/Presentation/Quiz Overall 40% Marks in Total.
Online Quiz 10
Evaluation Scheme