Table of contents
Fundamentals of Computer Science
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.
Professor(s)
- Dr. Golnaz Badkobeh
Topics covered
- 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
Assessment
One two hour unseen written examination and coursework (Type I)
Module specification
Past exams
Syllabus
Resources
Complementary learning
- 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
Essential reading
“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
Textbooks solutions
Discrete Mathematics and its Applications
- 7th Edition (2012) - written explanations on Slader.com
- 8th Edition (2018) - step-by-step solutions in videos on Numerade.com
Introduction to Automata Theory, Languages, and Computation
Notes
Sample Paper with solutions
March 2020
Study guide
Weekly reading list
Supplementary Videos
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)