Below are non-exhaustive lists of key questions you should be able to answer on the referenced test.
You should be able to apply the key functional concepts inherent in these questions.
It is thus important to study these with the aim of understanding the key concepts, as opposed to simply being able to regurgitate a memorized response.
If you have a good understanding of the core concepts inherent in the questions on this page, you should do fine.
Explain what a tractable problem is
Be able to identify some hard problems which are in fact tractable
Explain what an intractable problem is
Be able to give some examples of practical problems which are intractable
Explain what an uncomputable problem is
Be able to give some examples of uncomputable problems
How we formally define a computer program
Explain what universal computability is
Explain what ASCII is
What a SISO program is, and why it is useful for this course
Be able to write a simple SISO program for a problem which has integer inputs and outputs
How we formally define a Python program, for the purpose of this course
Explain why a formal definition matters
What it means for a program to "accept" or "reject" on certain inputs
What it means for the output of a program to be "undefined"
What a computable function is
What a total function is
What a decision program is
What it means for two programs to be "equivalent"
What proof by contradiction is, and be able to prepare this proof for simple problems
Explain what a self-referential program is, and how it is useful in our course
What polynomial time is
What exponential time is
Explain the Traveling Salesman Problem and what features drive its uncomputability
Explain the Halting Problem and why it is uncomputable
What an "instance" of a problem is
What graphs are and how to encode them as strings
What a graph cycle is
What a graph path is
What trees and rooted trees are and how to encode them as strings
What an alphabet is (in the context of this course)
How to articulate and express an alphabet for a particular use case
What the symbols for an alphabet are
What a string is
What a string on an alphabet is
What a language or formal language is
Be able to articulate a formal language for a particular use case (see the various examples in the book)
What membership in a language means
What the Kleene star is, and what it represents when applied to a language
Understand, and be able to use, the various available operations on languages
What the terms function, domain, co-domain mean in the context of our definition of a computational problem
What a computational problem is in the context of our SISO approach
Be able to give simple examples of a computational problem
What positive and negative instances of a computational problem are, and be able to give examples
Explain what a search problem is, and be able to give an example (for example, given a graph and its string representation, be able to articulate the string representation for a path between two points, if it exists)
Explain what an optimization problem is, and be able to give an example
Explain what a threshold problem is, and be able to give an example
Explain what a function problem is, and be able to give an example
Explain why decision problems are particularly important in computability
How to convert a problem to, and from, a decision problem
What the concepts of solve, compute, decide, computable, and decidable mean, in the context of computability
Given some code, be able to identify whether a program is computable and/or decidable
What it means for a particular problem program to be "recognizable"
Who Alan Turing is
Why the Turing machine model is important
Be able to identify the key components of a Turing machine, what the utility of each of the components is, and how their combination is powerful
Be able to summarize and explain the Turing machine computation process
Identify and explain the three possible Halting states of a Turing machine
Explain the idea of ''state" and its value in computation
Explain what a "state transition" is, and how it may occur in a Turing machine
What a transition table is, and the role it plays in computing on a Turing machine
Identify and describe the three types of actions a Turing machine can take during a "turn"
Be able to trace through a simple transition table, given a particular tape state, and determine what the applicable Turing machine does
Explain how state diagrams work, and how they can represent a Turing machine transition table
Be able to convert a transition table to a state diagram
Be able to trace through a state diagram, given a provided input tape
Be able to describe when a Turing machine is an acceptor or a transducer, and be able to give examples of simple problems from these two classes
Explain what it means for a Turing machine to loop
How a Turing machine can be used to simulate any computer
What the key feature of a Turing machine is which enables this simulation power, and explain why that feature is critical
Explain what Turing-Equivalence means, and give some examples of machines that meet that test
Explain what a universal computer is, and why it is conceptually important
Explain the difference between recognizable and decidable decision problems
Be able to write a short Python which is either recognizing or deciding, given some input parameters
Be able to use the correct notation conventions used in the book
What a computable/uncomputable problem is
What a decidable/undecidable problem is
What a recognizable/ unrecognizable problem is
What a transducer is
What an accepter is
What a Turing reduction is, what the notation means
How to do a reduction generally
What an oracle function is and explain the role it plays in reduction
How to use a reduction to prove a program is computable/uncomputable
Explain what it means for reductions to be transitive
How reduction transitivity reflects "hardness"
Explain the halting problem, and why it is undecidable
How to do reductions for various problems like the examples used in the book
Be able to identify programs which are decidable/undecidable
Explain what the class of Computes(F) problems are and why they are undecidable/uncomputable
What Rice's Theorem is, and be able to use it to prove non computability for a particular problem
What a diophantine equation is, and why Hilbert's 10th Problem is undecidable.
What the Post Correspondence Problem is, and offer an explanation of why it is, in general, uncomputable.
How to identify a program which is "obviously" computable
Be able to summarize the approach for the three reduction strategies outlined in the book
What parallelism is
Be able to clearly articulate definitions for determinism and non-determinism, and be able to give examples of each
Be able to differentiate between deterministic and non-deterministic processes/events/programs
Explain what threading is
Explain what a computation tree is, and be able to construct one
How to convert a non-deterministic program into a deterministic program
What a non-deterministic Turing machine and how it implements the non-deterministic functionality
How to create a state diagram for a non-deterministic Turing machine
How to create a computation tree for a non-deterministic Turing machine
How to formally articulate a non-deterministic Turing machine
Describe the three models of non-determinism described in the book, and be able to identify example instances of each
Articulate the benefits of studying the non-deterministic paradigm
Define what a deterministic finite automaton (dfa) is
Define what a non-deterministic finite automaton (nfa) is
Given a state transition table, be able to construct a dfa/nfa and vice versa
What an epsilon transition is, and how it is used in nfa/dfa state diagrams
What the computational limitations of a dfa/nfa are
How a dfa/nfa accepts or rejects
Explain the process of converting an nfa to a dfa, and be able to do this for a simple state diagram
Explain what a regular expression is
Explain the utility of concatenation, alternatives and the Kleene star in creating regular expressions
Explain the utility of the . , + , and [ ] operations for regular expressions
Given a description be able to create an equivalent regular expression, and vice versa
Be able to convert a regular expression into an nfa
Describe what it means for a language to be regular or irregular, and be able to give examples of each.
Explain the relationship of irregular languages with the computational limitations of a dfa/nfa
What equivalence of dfas/nfas means
Explain what pumping a substring is
Explain the Pumping Lemma and how it is useful in distinguishing between regular and irregular languages
Be able to demonstrate using the pumping lemma on relatively simple languages
Explain what a context free grammar (CFG) is, and be able to list its constituent components
Be able to derive a string, given a definition of a CFG
What it means for a computation to be efficient
What asymptotic running time is
How input size relates to computational efficiency
What a running time curve is
How the log function works
Explain and be able to give examples of logarithmic, polynomial, and exponential functions
Be able to identify whether a code snippet is reflective of any of the above functions
Where n! fits in the above three classes
What "Big-O of a function class" means
What a dominant term is in the context of Big-O notation
How to identify a dominant term in a stated complexity formula
How multiplication and logarithms affect dominant terms
Be able to articulate a practical and formal definition of Big-O notation
Be able to identify and correct common Big-O notation mistakes
What superpolynomial and subexponential functions are, and be able to give examples
What combinatorics is
Know the complexity of the 6 combinatorial problems referenced in the book
How to calculate the running time for a Turing machine, given a state diagram
What running time is in the context of a programming language such as Python or Java
Know the complexity of basic list operators
Be able to analyze a Python function with various control flows, and determine its complexity
How the length of input relates to the numerical value of the input
Know (and explain) the complexity of multiplication, division, addition, and subtraction in a programming language such as Python
Know and explain the time complexity of factoring
Be able to define the Poly complexity class and be able to give some examples
Be able to define the Expo complexity class and be able to give some examples
Be able to define the PolyCheck complexity class and be able to give some examples
Explain what a "verifier" is and how it works in the context of PolyCheck
Explain why the difference between Poly and Expo is important in computer science
Explain how Poly, Expo, computable problems, and all computational problems relate to each other
Be able to give examples of problems which appear very similar but have markedly different complexity
Explain what it is about such problems that makes some "easy" and others "hard"
Explain why some polynomial time algorithms are not useful in practice, and be able to give examples
Be familiar with the Packing, SubSetSum, and Partition problems
Explain what the NPoly complexity class is
Be able to explain why PolyCheck and NPoly are the same
Explain why PolyCheck is "sandwiched" between Poly and Expo
Explain what a polynomial time reduction is
Explain the difference between a Turing reduction and a Poly reduction
Explain the "C algorithm" components of a successful (mapping) Poly reduction
Give examples of basic mapping reduction strategies
Explain what a satisfiability problem is
Explain the CircuitSAT, SAT, and 3-SAT variants
Know what a Tseytin transformation is
Know what "splitting a clause" is
Explain what Polyequivalence is
Explain the difference between P and NP using different approaches
Explain what NP-Completeness is
Explain the Cook-Levin Theorem and how it relates to NP-Completeness
How NP-Completeness relates to P versus NP
Explain what NP-Hard problems are
Explain what it means if someone can prove that P = NP
How the proof of CircuitSAT or SAT being in NP-Complete generally works (assuming and accepting that we have a poly Turing Machine to Boolean formula/logic converter)
Explain the general strategy for proving NP-Completeness
Have a good sense of which real-world problems fit in the NP-Complete / NP Hard universe