Skip to main content
e-učilnica UP FAMNIT
You are currently using guest access (
Log in
)
Comprehensive Course in Computer Science - Theoretical Computer Science
Home
Courses
Študijsko leto 2020/2021
Računalništvo in informatika (1. stopnja, 2. stopnja, 3. stopnja)
3.stopnja
1.letnik
Comprehensive Course in Computer Science - Theoretical Computer Science
Tractability, P, NP & Satisfiability
[12/05/2020] Lecture recording
[12/05/2020] Lecture recording
Click on
[12/05/2020] Lecture recording
to open the resource.
◄ Did you understand what you've learned?
Jump to...
Jump to...
Announcements
Student's Forum
General information about the course
Detailed course syllabus
Homework No. 1 - DFA
Homework No. 2 - NFA
Homework No. 3 - NFA --> DFA + minimisation
Homework No. 4 - RE
Homework No. 5 - CNF
Homework No. 6 - PDA
Homework No. 7 - CYK
Homework No. 8 - TM
Homework No. 9 - Satisfiability
Motivation and course outline
Introduction to finite automata
Deterministic finite automata
Did you understand what you've learned?
Nondeterministic finite automata
Finite automata with output
Regular expressions
Did you understand what you've learned?
Regular expressions in the real world
Decision algorithms for regular languages
Closure properties of regular languages
Did you understand what you've learned?
Regular languages (wrap-up)
JFLAP - A graphical tool for learning Formal Languages and Automata Theory
Quiz 01 - Regular Languages
Lecture recording - part 1
Lecture recording - part 2
Whiteboard screenshot #1
Whiteboard screenshot #2
Whiteboard screenshot #3
Whiteboard screenshot #4
Whiteboard screenshot #5
Whiteboard screenshot #6
Introduction to context-free grammars
Parse trees
Normal forms
Did you understand what you've learned?
[17/03/2020] - Lecture recording
Pushdown automata (PDA)
Equivalence of PDAs and CFGs
More on CFGs
Did you understand what you've learned?
[24/03/2020] - Lecture recording
Context-free languages (wrap-up)
Last year's 1st midterm (example)
Quiz 02 - Context-free Languages
[31/03/2020] - Lecture recording (part #1)
Whiteboard screenshot #1
Whiteboard screenshot #2
Whiteboard screenshot #3
Whiteboard screenshot #4
[31/03/2020] - Lecture recording (part #2)
Whiteboard screenshot #5
Whiteboard screenshot #6
Whiteboard screenshot #7
Whiteboard screenshot #8
Whiteboard screenshot #9
The pumping lemma for CFLs
Decision and closure properties for CFLs
Did you understand what you've learned?
Quiz 03 - CNF and the CYK algorithm
[07/04/2020] Lecture recording
Turing machines
Extensions and properties of TMs
Did you understand what you've learned?
[14/04/2020] Lecture recording
Decidability
More undecidable problems
Did you understand what you've learned?
Quiz 04 - PDAs, TMs and Reductions
[21/04/2020] Lecture recording
Turing machines & decidability (wrap-up)
[05/05/2020] Lecture recording
Whiteboard screenshot #1
Whiteboard screenshot #2
Whiteboard screenshot #3
Whiteboard screenshot #4
Whiteboard screenshot #5
P and NP
Satisfiability
Did you understand what you've learned?
Specific NP-complete problems
Did you understand what you've learned?
Tractability, P, NP & Satisfiability (wrap-up)
Quiz 05 - Tractability, Satisfiability, P and NP
[19/05/2020] Lecture recording
Explanation on a figure (P, NP, NP-complete, NP-hard)
Figure (P, NP, Co-NP, NP-complete, Co-NP-complete, NP-hard, Co-NP-hard)
Last year's 2nd midterm (example)
Last year's exam (example)
[26/05/2020] Lecture recording
Whiteboard screenshot #1
Whiteboard screenshot #2
Whiteboard screenshot #3
Whiteboard screenshot #4
Whiteboard screenshot #5
Whiteboard screenshot #6
Whiteboard screenshot #7
15.05.2020
08.05.2020
24.04.2020
20.04.2020
10.04.2020
03.04.2020
27.03.2020
20.03.2020
Online tutorial feedback
Specific NP-complete problems ►