Algorithms and Problem Solving

Sample questions

Showing 20 of 70 questions from this chapter. The full bank is in the chapter test below.

1. 1

   In the input-process-output view of a computational problem, the algorithm itself corresponds to which element?

   • A.Input
   • B.Output
   • C.✓ Process (correct answer)
   • D.Storage

   Why: The process is the algorithm: the step-by-step rules applied to the input to produce the output. Input is the data handed to the algorithm at the start, and the output is the result it returns.
2. 2

   Which of the following best describes a well-defined computational problem?

   • A.Ambiguous goals that allow several interpretations
   • B.✓ Clear goals, inputs, process and outputs (correct answer)
   • C.A problem whose outputs are unrelated to its inputs
   • D.A problem that no algorithm can solve

   Why: A well-defined problem states its goal, its input, the steps to be followed and the expected output precisely, as with deciding whether a number is even. Vague or ambiguous goals are the mark of an ill-defined problem.
3. 3

   Which of these is an example of an ill-defined problem?

   • A.Testing whether an integer is divisible by 2
   • B.Finding the greatest common divisor of two numbers
   • C.Sorting a list of numbers into ascending order
   • D.✓ Deciding how to reduce poverty in a country (correct answer)

   Why: A goal such as reducing poverty has no precise input, no agreed measure of success and no clear stopping point. The other three have exact inputs, a fixed process and a checkable output.
4. 4

   A small program asks the user for an integer, checks whether the number is divisible by 2, and prints either 'Even' or 'Odd'. Why is this a well-defined problem?

   • A.Because the same problem can be solved by more than one algorithm
   • B.Because the answer depends on the computer that runs it
   • C.✓ Because its goal, input, process and output are all clearly specified (correct answer)
   • D.Because it needs no input from the user

   Why: The goal (decide whether the number is even), the input (one integer), the process (test divisibility by 2) and the output (even or odd) are all fixed in advance. Having several possible algorithms does not make a problem ill-defined.
5. 5

   A computational problem whose answer is only 'yes' or 'no' is classified as a:

   • A.✓ Decision problem (correct answer)
   • B.Search problem
   • C.Optimization problem
   • D.Counting problem

   Why: Decision problems ask whether some condition holds, so the output is a single yes or no. A search problem instead returns an item or solution that meets the stated criteria.
6. 6

   In which category of computational problem is the task to find a solution or item that satisfies certain criteria?

   • A.Decision problem
   • B.✓ Search problem (correct answer)
   • C.Counting problem
   • D.Optimization problem

   Why: Search problems ask for an item meeting the stated conditions, such as finding a name in a list. Counting problems ask how many such items exist, and optimization problems ask which of them is best.
7. 7

   A route planner is asked which of several valid routes uses the least fuel. This problem is classified as a:

   • A.Decision problem
   • B.Counting problem
   • C.✓ Optimization problem (correct answer)
   • D.Sorting problem

   Why: Optimization problems seek the best solution measured by some criterion, here the fuel used. A decision version of the same task would ask only whether a route within a given fuel limit exists.
8. 8

   Counting how many different ways a committee of three can be chosen from ten students is an example of a:

   • A.Decision problem
   • B.Search problem
   • C.Optimization problem
   • D.✓ Counting problem (correct answer)

   Why: Counting problems ask how many configurations satisfy a condition, so the answer is a number rather than an item or a yes/no verdict.
9. 9

   Why are algorithms central to problem solving?

   • A.They remove the need to test a program
   • B.✓ They give the exact logic that turns inputs into the required outputs, so the solution is correct and repeatable (correct answer)
   • C.They guarantee that every problem is solvable
   • D.They let a program run without any input

   Why: An algorithm is the reasoning behind the code: the same steps applied to the same input always produce the required output. An algorithm cannot rescue an unsolvable problem, since the halting problem has no algorithm at all.
10. 10

    The PageRank algorithm used by the Google search engine ranks web pages mainly by:

    • A.✓ The number of links to a page and the quality of those links (correct answer)
    • B.The number of words on each page
    • C.The alphabetical order of the page titles
    • D.How recently each page was last edited

    Why: PageRank treats a link as a vote, so pages with many high-quality incoming links are ranked higher. Word counts and title order play no part in the ranking it computes.
11. 11

    The generate-and-test method solves a problem by:

    • A.Sorting all the candidate solutions before checking any of them
    • B.Dividing the problem into two equal halves
    • C.✓ Generating possible solutions and testing each one until a satisfactory solution is found (correct answer)
    • D.Always choosing the option that looks best at the moment

    Why: Candidates are produced one after another and each is checked against the requirements. The process stops when a candidate passes the test or when all possible candidates have been exhausted.
12. 12

    For which situation is the generate-and-test method most suitable?

    • A.When the problem is known to be unsolvable
    • B.When the size of the input is unknown
    • C.When no candidate solution can be described
    • D.✓ When the problem space is small enough to generate and test all candidates (correct answer)

    Why: Exhaustive generation is practical only when the space of candidates is small or can be pruned by heuristics. If the solution space is huge, testing every candidate is hopeless and a smarter technique is needed.
13. 13

    What is the role of heuristics in the generate-and-test method?

    • A.They prove that the problem has no solution
    • B.✓ They reduce the number of candidate solutions that have to be tested (correct answer)
    • C.They guarantee that the first candidate generated is correct
    • D.They replace the testing stage altogether

    Why: Heuristics are rules of thumb that discard unlikely candidates early, so fewer possibilities reach the tester. The tester is still needed, because a heuristic can miss the correct candidate.
14. 14

    In the generate-and-test cycle, what happens when the tester decides that a candidate is incorrect?

    • A.The whole algorithm stops and reports failure
    • B.✓ The generator produces another candidate and testing continues (correct answer)
    • C.The tester repairs the candidate itself
    • D.The input is rejected and the process ends

    Why: The generator and the tester form a loop: a rejected candidate sends control back to the generator for another attempt. The loop ends only when a candidate is accepted or no candidates remain.
15. 15

    The generate-and-test approach is widely used in artificial intelligence applications such as:

    • A.Compiling source code
    • B.Formatting a storage device
    • C.Converting binary numbers to decimal
    • D.✓ Game playing and puzzle solving, where different possibilities are tried until one works (correct answer)

    Why: In such applications the program repeatedly proposes a move or a configuration and checks whether it is acceptable, which is exactly the generate-and-test cycle. Compiling and number-base conversion follow fixed procedures instead.
16. 16

    A problem is solvable when:

    • A.✓ An algorithm exists that gives the correct answer in a finite number of steps for every allowed input (correct answer)
    • B.It can be solved only by a human expert
    • C.It requires exponential time to solve
    • D.Its input may be of any size

    Why: Solvability means that an algorithm exists which always terminates with the right answer. A problem for which no algorithm handles every input is unsolvable, however much time is allowed.
17. 17

    Finding the greatest common divisor of two integers by the Euclidean algorithm is a classic example of:

    • A.An unsolvable problem
    • B.An NP-complete problem
    • C.An ill-defined problem
    • D.✓ A solvable problem (correct answer)

    Why: The Euclidean algorithm always finishes in a finite number of steps with the correct GCD, so an algorithm for the problem exists. Solvable does not mean easy: it means only that a step-by-step procedure is possible.
18. 18

    What does the halting problem ask?

    • A.✓ Whether a given program and input will eventually finish running or continue forever (correct answer)
    • B.Whether two different programs produce the same output
    • C.Whether a program uses more memory than it is allowed
    • D.Whether a program can be compiled without errors

    Why: The halting problem asks for a general method that decides, for any program and input, whether the program eventually stops. No such method exists, which is why the problem is the standard example of an unsolvable problem.
19. 19

    Who proved that no general algorithm can decide the halting problem for every program and input?

    • A.✓ Alan Turing (correct answer)
    • B.Charles Babbage
    • C.John McCarthy
    • D.Ada Lovelace

    Why: Turing's proof showed that no single algorithm answers the halting question correctly for all program-input pairs. Babbage and Lovelace worked on early computing machines long before the result was proved.
20. 20

    Which statement is true of unsolvable problems?

    • A.They can always be solved if enough time is allowed
    • B.✓ No algorithm exists that solves them for all possible inputs (correct answer)
    • C.They are exactly the same as intractable problems
    • D.They all belong to class P

    Why: An unsolvable problem has no algorithm that answers correctly for every input. Intractable problems are different: algorithms for them do exist, but those algorithms take far too long on large inputs.