In this module, you'll gain a broad understanding of key topic areas in computer science and the fundamental concepts underpinning them. In the area of fundamental concepts, you'll learn about binary representations and logic, complexity theory and theories of computation, finite state machines and Turing machines. Building on this, you'll then study key areas of interest in computer science including databases, artificial intelligence and machine learning. These will be presented as practical examples to illustrate how they are implemented in modern computer systems.
- Dr. Golnaz Badkobeh
- Boolean logic
- Algorithms
- Searching and sorting algorithms
- Theory of Computation and complexity
- Turing machines and universal machines
- Basic combinatorial principles
- Proof techniques
- Finite automata
- Regular languages
- Context-free grammar
One two hour unseen written examination and coursework (Type I)
- Highly recommended for week 7 onwards: lectures and videos from Prof. Michael Harrison.
- Context-free grammar tool
- Context-Free Grammar with Daniel Shiffman - A fun way to understand CFG with real-world examples and programming.
- Easy Theory - "This is a channel about making Computer Science theory as easy as possible." Relevant for this course as well as Algorithms and Data Structures I.
- Great Ideas in Theoretical Computer Science - Complementary topics, including proofs, deductive systems, logic, finite automata, Turing, time complexity, graph algorithms, etc.
- Guide to Negating Formulas (propositional logic) - stanford.edu
- Introduction to Theoretical Computer Science
- Truth Table Generator
"Specific essential readings for each week from the following list are included in the Readings page for each week:"
- 🥇 Kenneth H. Rosen (2011). Discrete Mathematics and its Applications, 7th. McGraw-Hill
- 🥇 Thomas Koshy (2004). Discrete Mathematics with Applications, 1st, Elsevier Inc.
- 🥇 Michael Sipser (2012). Introduction to the theory of computation, 3rd. Cengage Learning
- 🥇 John Hopcroft et al. (2013). Introduction to Automata Theory, Languages and Computation, Pearson
- 🥈 Merlin Forbes (2012). A Theoretical Introduction to Turing Machine, 1st. Learning Press
- Dexter Kozen (2007). Automata and Computability, 1st. Springer
- Shi-Kui Chang (2003). Data Structures and Algorithms, 1st. World Scientific Publishing Co
- 7th Edition (2012) - written explanations on Slader.com
- 8th Edition (2018) - step-by-step solutions in videos on Numerade.com
Following are supplementary videos for Theory of computation part of the module (week 7-14) for week 1-6 refer NM/DM material and for week 15-20 refer ADS1 material.
- Basics: Proofs (YouTube playlist)
- Mathematical Thinking - Keith Devlin (YouTube playlist)
- Portland State university - YouTube - Harry Porter - "Theory of Computation" (Uses Sipser book and paper+sharpie for teaching) (YouTube playlist)
- Pumping lemma (for regular languages) - Neso Academy (YouTube video)
- Pumping lemma for Regular - Didem Yalcin (YouTube video)
- Stanford - Lagunita - Jeff Ullman - "Automata theory" (uses Hopcroft - Ullman book and slideshow based lectures)
- UC Davis - YouTube - Dan Gusfield - "Theory of Computation" (Uses Sipser book and blackboard style lectures) (YouTube playlist)