CS2004_Algorithmic_Concepts_Flashcards
(15 cards)
What is an algorithm?
An algorithm is a finite, well-defined sequence of instructions used to solve a specific problem or perform a computation.
✅ Example: The steps to perform Bubble Sort are an algorithm that arranges a list in ascending order.
What is a program?
A program is the implementation of an algorithm in a specific programming language so that it can be executed by a computer.
✅ Example: Writing the Bubble Sort algorithm in Python makes it a program.
What is the difference between an algorithm and a program?
An algorithm is the abstract plan or logic, while a program is the concrete implementation of that logic in code.
✅ Example: The logic of finding a minimum in a list is the algorithm; writing it in Java makes it a program.
What is a decision problem?
A decision problem is a problem that has a yes/no (true/false) output for a given input.
✅ Example: Is a number prime? (Input: 17 → Output: Yes)
What is a computable problem?
A computable problem is one for which an algorithm exists that will solve the problem in a finite number of steps.
✅ Example: Sorting a list of numbers using Merge Sort is a computable problem.
What is an incomputable problem?
An incomputable (undecidable) problem is one for which no algorithm can solve all instances of the problem.
✅ Example: The Halting Problem — determining if a program halts on a given input — is incomputable.
What is the Halting Problem?
The Halting Problem is the problem of deciding whether a given program will finish running or continue forever for a specific input.
✅ Example: There is no general-purpose algorithm that can answer this for all programs.
What is P in computational complexity?
P is the class of decision problems that can be solved in polynomial time by a deterministic Turing machine.
✅ Example: Binary Search runs in O(log n), which is polynomial → in class P.
What is NP?
NP (nondeterministic polynomial time) is the class of decision problems where a solution can be verified in polynomial time.
✅ Example: Verifying a completed Sudoku board can be done quickly, so it’s in NP.
What is an NP-Complete problem?
An NP-Complete problem is both in NP and as hard as any problem in NP. If any NP-Complete problem is solved in polynomial time, then all NP problems can be.
✅ Example: Boolean Satisfiability (SAT) is NP-Complete.
What is an NP-Hard problem?
An NP-Hard problem is at least as hard as the hardest problems in NP but does not have to be in NP (it may not be verifiable in polynomial time).
✅ Example: The optimisation version of the Travelling Salesperson Problem is NP-Hard.
What is an example of a problem in P?
Problems that can be solved in polynomial time by a deterministic machine.
✅ Example: Matrix multiplication or Binary Search.
What is an example of a problem in NP?
Problems whose solutions can be verified in polynomial time.
✅ Example: Verifying a solution to the Knapsack Problem.
What is an example of an NP-Complete problem?
An NP-Complete problem is both in NP and NP-Hard.
✅ Example: The Travelling Salesperson Problem (decision version) and 3-SAT.
What is the purpose of problem classification in complexity theory?
It helps to determine whether a problem can be solved efficiently and guides which algorithms are applicable.
✅ Example: Classifying a problem as NP-Hard tells us that we likely need a heuristic or approximation algorithm.
