Theory of Computation

Theory of Computation

@VTU COE

0.0
(0) 0 Students
Download Brochure

What you will learn

  • none

This course is an introduction to the theory of computation. We start with computability --- different models of computations and see what are the capabilities of each of these models. Each of these models try to model a computer. We see the classes of languages each of these models are capable of computing. After computability, we will see an introduction to complexity, where we classify computable languages on the basis of easiness/difficulty of computation. The student should be comfortable with basic proof techniques.

play
An Introduction to The Theory of Computation
Preview 20:29
play
Notations and Terminology in Theory of Computation
Preview 32:43
play
An Introduction to Finite Automata and Regular Languages - Part 01
Preview 31:44
play
An Introduction to Finite Automata and Regular Languages - Part 02
Preview 27:30
play
Significance of Regular Languages and Regular Operations
Preview 16:11
play
Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation-Part 01
Preview 32:27
play
Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation-Part 02
Preview 12:25

play
An Introduction to Non-Deterministic Finite Automata (NFA)
Preview 34:06
play
Formal Definitions and Examples of Non-Deterministic Finite Automata(NFA)
Preview 16:22
play
Equivalence of NFA and DFA
Preview 42:02
play
Closure of Regular Languages Under Regular Operations(Using NFA)
Preview 38:31
play

Regular Expressions - Part 01

28:29
play
Regular Expressions - Part 02
Preview 17:25
play
Proving Equivalence of Regular Expression and DFA Through a GNFA
Preview 45:39

play
Pumping Lemma for Regular Languages - Part 01
Preview 32:09
play
Pumping Lemma for Regular Languages - Part 02
Preview 41:54
play
Distinguishability of Strings and Myhill-Nerode Theorem
Preview 30:04
play
Proving the Myhill-Nerode Theorem
Preview 39:54
play
An Introduction to Context-Free Languages - Part 01
Preview 27:16
play
An Introduction to Context-Free Languages - Part 02
Preview 38:44

play
Chomsky Normal Form
Preview 37:12
play
CYK Algorithm - Part 1
Preview 28:02
play
CYK Algorithm - Part 2 (Example)
Preview 19:00
play
Closure Properties of Context Free Languages
Preview 17:24
play
An Introduction to Push Down Automata
Preview 43:47
play
Normalizations in PDA and Intersection of Regular Language & CFL
Preview 21:54

play
Equivalence of Context Free Grammars and Push Down Automata - Part 01
Preview 25:12
play
Equivalence of Context Free Grammars and Push Down Automata - Part 02
Preview 33:45
play
Equivalence of Context Free Grammars and Push Down Automata - Part 03
Preview 33:45
play
Pumping Lemma for Context Free Languages
Preview 37:55
play
Examples of Pumping Lemma Usage for Context Free Languages
Preview 21:09
play
Formal Definition of a Turing Machine
Preview 37:17

play
Turing Recognizable & Decidable Languages and TM Examples
Preview 41:08
play
Multitape Turing Machine
Preview 26:47
play
Non-Deterministic Turing Machines
Preview 36:40
play
Equivalence of Deterministic and Nondeterministic TM
Preview 26:56
play
Church-Turing Thesis
Preview 29:52

play
Decidable Problems Concerning Regular Languages
Preview 26:36
play
Decidable Problems Concerning Context Free Languages
Preview 22:26
play
Countability of Sets
Preview 33:57
play
Proof of Existence of Undecidable Languages
Preview 26:42
play
Halting Problem
Preview 33:58
play
Co-Turing Recognizability
Preview 20:01

play
An Introduction to Mapping Reducibility
Preview 33:56
play
Examples of Proving Undecidability Using Reductions
Preview 37:56
play
Rice Theorem
Preview 34:32
play
Computation Histories
Preview 36:20

play
The Post Correspondence Problem
Preview 46:26
play
Checking Ambiguity in CFG is Undecidable
Preview 20:01
play
Time Complexity - Part 1
Preview 33:19
play
Time Complexity - Part 2
Preview 30:29
play
Non-Deterministic Polynomial Time - Part 1
Preview 32:03
play
Non-Deterministic Polynomial Time - Part 2
Preview 18:01

play
Verifiability and NP
Preview 38:29
play
Polynomial Time Reductions - Part 1
Preview 23:11
play
Polynomial Time Reductions - Part 2
Preview 27:18
play
NP-Completeness
Preview 14:41
play
Cook-Levin Theorem
Preview 35:21
play
Cook-Levin Theorem - Proof and Implications
Preview 43:41

play
CLIQUE and VERTEX-COVER is NP-Complete
Preview 44:37
play
HAM-PATH is NP-Complete
Preview 39:01
play
SUBSET-SUM is NP-Complete
Preview 39:15
play
Knapsack Problem
Preview 18:09
play
Integer Linear Program is NP-Complete
Preview 22:05

play
Space Complexity and its Complexity Classes
Preview 50:51
play
Logspace Reductions and NL-Completeness
Preview 50:51
play
Savitch's theorem
Preview 26:28
play
Results in Space Complexity
Preview 30:57
play
Summary and Concluding Remarks
Preview 17:05
img
No Discussion Found

0.0

0 Reviews

5
0
4
0
3
0
2
0
1
0
Meet Your Instructor
@VTU COE
img

Instructor
3.2 Rating
2542 Students
759 Courses
About Instructor

VTU is one of the largest Technological Universities in India with 24 years of Tradition of excellence in Engineering & Technical Education, Research and Innovations. It came into existence in the year 1998 to cater the needs of Indian industries for trained technical manpower with practical experience and sound theoretical knowledge.

video

Free

  • Course Duration
    35 h 37 m 56 s
  • Course Level
    Intermediate
  • Student Enrolled
    0
  • Language
    English
This Course Includes
  • 35 h 37 m 56 s Video Lectures
  • 0 Quizzes
  • 0 Assignments
  • 0 Downloadable Resources
  • Full Lifetime Access
  • Certificate of Completion