DCS: MCS 702 – Advanced Theoretical Computer Science
Categories: Doctorate of Computer Science
About Course
- This core course delves into advanced topics in theoretical computer science, including formal languages, automata theory, and computational complexity.
- It provides a deep understanding of the theoretical limits of computation and prepares students to tackle complex algorithmic challenges.
- The course is designed for students who are pursuing advanced research in computer science and wish to gain a rigorous understanding of the foundational theories that underpin modern computing.
Course Objectives
- Develop an in-depth understanding of formal languages, automata theory, and computational complexity.
- Analyze the theoretical limits of computation and their implications for practical computing problems.
- Explore advanced algorithmic techniques and their applications in solving complex problems.
- Engage with current research topics in theoretical computer science.
- Prepare for advanced research in algorithm design and analysis.
Course Content
Week 1: Introduction to Formal Languages
-
Introduction to Formal Languages
00:00 -
LO1: Define the concepts of Formal languages and Regular Expressions
00:00 -
LO2: Explain the role of Finite Automata in Language Recognition
00:00 -
LO3: Illustrate examples of simple Regular Expressions and Equivalent Automata
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 2: Automata Theory
-
Automata Theory
00:00 -
LO1: Differentiate between Deterministic and Non- deterministic Finite Automata
00:00 -
LO2: Prove the equivalence of Deterministic and Non- deterministic models
00:00 -
LO3: Construct Automata for given Regular languages
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 3: Context-free Grammars and Pushdown Automata
-
Context-free Grammars and Pushdown Automata
00:00 -
LO1: Define Context-free languages and their grammar rules
00:00 -
LO2: Explain the design of pushdown Automata and their role in parsing
00:00 -
LO3: Apply parsing techniques to analyse Context-free languages
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 4: Turing Machines
-
Turing Machines
00:00 -
LO1: Describe the structure and operation of a Turing machine
00:00 -
LO2: Explain the Church-Turing thesis and its implications for Computation
00:00 -
LO3: Design simple Turing machines for language recognition
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 5: Undecidability and the Halting Problem
-
Undecidability and the Halting Problem
00:00 -
LO1: Define undecidable problems and explain their significance
00:00 -
LO2: Demonstrate reductions to show undecidability
00:00 -
LO3: Analyze the halting problem and its implications for Computation
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 6: Computational Complexity
-
Computational Complexity
00:00 -
LO1: Explain Time and Space Complexity measures
00:00 -
LO2: Classify problems based on Big-O and other Complexity Notations
00:00 -
LO3: Apply Complexity analysis to evaluate Algorithms
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 7: The P vs NP Problem
-
The P vs NP Problem
00:00 -
LO1: Distinguish between P, NP, NP-complete, and NP-hard classes
00:00 -
LO2: Explain reductions used to prove NP-completeness
00:00 -
LO3: Evaluate the implications of the P vs NP question for algorithm design
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 8: Midterm Test
-
Midterm Test
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 9: Advanced Topics in Complexity Theory
-
Advanced Topics in Complexity Theory
00:00 -
LO1: Explain Space Complexity and its Classification
00:00 -
LO2: Compare Probabilistic complexity classes and their relationships
00:00 -
LO3: Analyse case studies of problems requiring advanced complexity models
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 10: Approximation Algorithms
-
Approximation Algorithms
00:00 -
LO1: Define Approximation algorithms and their necessity for NP-hard problems
00:00 -
LO2: Explain approximation ratios and performance guarantees
00:00 -
LO3: Design approximation algorithms for selected NP-hard problems
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 11: Randomized Algorithms
-
Randomized Algorithms
00:00 -
LO1: Explain the role of randomness in algorithm design
00:00 -
LO2: Differentiate between Monte Carlo and Las Vegas algorithms
00:00 -
LO3: Apply randomized techniques to solve Computational problems
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 12: Advanced Automata Theory
-
Advanced Automata Theory
00:00 -
LO1: Define omega-Automata and their role in infinite word recognition
00:00 -
LO2: Explain applications of Automata on infinite inputs in system verification
00:00 -
LO3: Construct examples of Automata for infinite word languages
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 13: Cryptographic Complexity
-
Cryptographic Complexity
00:00 -
LO1: Explain the relationship between Computational hardness and cryptography
00:00 -
LO2: Analyze the role of one-way functions in cryptographic security
00:00 -
LO3: Evaluate cryptographic assumptions using complexity theory frameworks
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 14: Future Directions in Theoretical Computer Science
-
Future Directions in Theoretical Computer Science
00:00 -
LO1: Identify emerging research areas in Computational complexity and Automata theory
00:00 -
LO2: Discuss the current status of open problems, such as P vs NP
00:00 -
LO3: Predict future applications of theoretical computer science in practice
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Written Assignment
-
Short Answer Questions
-
Presentation Task
-
Exercises and Activities Adaptation
-
Peer Review Task
-
Role-Playing Activity
Week 15: Course Review
-
Course Review
00:00 -
LO1: Discuss the key theories of Automata, Languages, and Complexity
00:00 -
LO2: Integrate theoretical concepts to analyse complex Computational problems
00:00 -
LO3: Prepare for the final assessment through review of core models and problem-solving approaches
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 16: Final Test
-
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
