BYTE BATTLE FINALS

[Complexity Classes]

Q: Which of the following problems is NP-Hard but not NP-Complete?

• 3-SAT

• Halting Problem

• Traveling Salesman Problem (decision version)

• Subset Sum Problem

[Turing Machines]

Q: A Turing Machine with k tapes is equivalent in computational power to a standard single-tape Turing Machine. This is an example of:

• Church-Turing Thesis

• Rice’s Theorem

• Time Hierarchy Theorem

• None of the above

[Algorithm Analysis]

Q: What is the time complexity of the optimal solution for the Matrix Chain Multiplication problem with n matrices?

• O(n log n)

• O(n)

• O(n³)

• O(2ⁿ)

[Automata Theory]

Q: Which language is not context-free?

• {aⁿbⁿ | n ≥ 0}

• {aⁿbⁿcⁿ | n ≥ 0}

• {aⁱbʲcᵏ | i = j or j = k}

• {wwᴿ | w ∈ {0,1}*}

[Graph Theory]

Q: Which problem can be solved in linear time?

• Finding the shortest path in an unweighted graph

• Finding a maximum matching in a bipartite graph

• Finding all Hamiltonian cycles in a graph

• Finding the longest path in a directed acyclic graph

[Computability]

Q: Which problem is decidable?

• None of the above

• Determining if two context-free grammars generate the same language

• Determining if a first-order logic formula is valid

• Determining if a Turing Machine halts on an empty input

[Logic]

Q: Which formula is not a tautology in propositional logic?

• (P → Q) → (¬Q → ¬P)

• (P ∧ ¬P) → Q

• ¬(P ∧ Q) → (¬P ∨ ¬Q)

• P ∨ ¬P

[Recursion]

Q: The Ackermann function is not primitive recursive because:

• It has no base case

• It grows faster than any primitive recursive function

• It uses mutual recursion

• It requires memoization

[Dynamic Programming]

Q: The recurrence for the Fibonacci sequence using memoization has a time complexity of:

• O(n²)

• O(n)

• O(2ⁿ)

• O(1)

[P vs NP]

Q: If P = NP, which statement is false?

• Factorization can be done in polynomial time

• All NP problems can be solved in polynomial time

• One-way functions cannot exist

• The Halting Problem becomes decidable