Quiz: Problem Solving and Algorithm Analysis — 23 questions

1. Why can a computer not produce useful results without software?

A. It creates operating rules from the hardware configuration

B. It interprets human intentions and selects suitable tasks

C. It improves its reasoning by observing previous outputs

D. It follows instructions supplied by software to perform tasks

Answer: (D)

Explanation

A computer is a machine that executes instructions, and software provides those instructions. The idea that it can independently interpret intentions confuses programmed operation with human-like decision-making.

2. Which sequence best represents the program-development process?

A. Implementation, documentation, requirements specification, testing, analysis, and design

B. Problem analysis, implementation, documentation, requirements specification, and testing

C. Algorithm design, testing, implementation, requirements specification, and documentation

D. Requirements specification, analysis, design, implementation, testing, and documentation

Answer: (D)

Explanation

Program development begins by specifying requirements and analyzing the problem, then proceeds through algorithm design, implementation, testing and verification, and documentation. Treating coding as the starting or complete activity omits essential planning and checking stages.

3. What does a requirements specification primarily describe?

A. The test results obtained after the completed program is executed

B. The programming language, data structures, and code used for implementation

C. The detailed sequence of computational steps for processing each input

D. The needed inputs, outputs, resources, constraints, and expected solution

Answer: (D)

Explanation

Requirements specification defines what the solution must receive, produce, use, and satisfy. A detailed sequence of computational steps belongs to problem analysis or algorithm design rather than requirements specification.

4. In a program that calculates the cost of apples, which item is an output rather than an input?

A. The cost per kilogram expressed in rupees

B. The total cost expressed in rupees

C. The quantity of apples measured in kilograms

D. The weighing information supplied for the purchase

Answer: (B)

Explanation

The apple quantity and price per kilogram are supplied values, while their product gives the total cost in rupees. Calling the quantity an output reverses the roles of supplied data and calculated results.

5. Which description best defines an algorithm?

A. A collection of programming statements written in a selected language

B. A hardware procedure that executes instructions without software support

C. A finite, unambiguous sequence of logical steps for a specific problem

D. A general explanation of a problem that omits operational details

Answer: (C)

Explanation

An algorithm gives complete, clear, finite steps for solving a particular problem and does not depend on a programming language. Programming statements are an implementation of an algorithm, not the language-independent algorithm itself.

6. Which statement correctly describes the input and output requirements of an algorithm?

A. It may omit inputs and outputs when its instructions are unambiguous

B. It must accept exactly one input and produce exactly one output

C. It may accept zero or more inputs and must produce at least one output

D. It must accept at least one input and may produce zero or more outputs

Answer: (C)

Explanation

An algorithm can operate without input, but it must provide at least one defined output as part of its required properties. Requiring an input would incorrectly exclude valid algorithms that use fixed or internally available data.

7. Which property of an algorithm concerns whether it solves the intended problem rather than how many resources it uses?

A. Efficiency concerns solving the intended problem

B. Finiteness concerns minimizing resource use

C. Correctness concerns solving the intended problem

D. Correctness concerns minimizing resource use

Answer: (C)

Explanation

Correctness evaluates whether the algorithm produces a solution to the intended problem. Efficiency instead concerns the resources the algorithm uses, such as time or memory.

8. What happens after the factorial algorithm finishes multiplying by the current value of $i$?

A. It prints the factorial before changing the value of $i$

B. It resets the factorial value and reads a new $n$

C. It increments $i$ and checks whether $i \leq n$

D. It stops whenever $i$ is equal to or less than $n$

Answer: (C)

Explanation

The algorithm increments $i$ after each multiplication and continues while $i \leq n$. Termination occurs when the increment makes $i$ greater than $n$, not while the condition remains true.

9. What is the primary purpose of program testing?

A. Checking whether a program meets user requirements

B. Writing comments that explain the program's structure

C. Planning the algorithm before any code is written

D. Executing a program to demonstrate its correctness

Answer: (D)

Explanation

Program testing involves executing the program to provide evidence that it behaves correctly. Checking compliance with user requirements is the role of verification rather than testing.

10. A developer compares a completed program with the features and constraints requested by users without focusing on running test inputs. What activity is being performed?

A. Algorithm design through computational decomposition

B. Program documentation through explanatory comments

C. Program verification against user requirements

D. Program testing through executed input cases

Answer: (C)

Explanation

Verification determines whether the program meets user requirements. Testing differs because it executes the program with inputs to demonstrate correctness.

11. Which description best characterizes a flowchart?

A. A programming-language representation containing executable syntax

B. A graphical representation of an algorithm's logic and operation sequence

C. An informal description written with English-like algorithm statements

D. A collection of comments explaining how program code can be modified

Answer: (B)

Explanation

A flowchart uses graphical elements to represent logic paths and the sequence of operations in an algorithm. Pseudocode conveys the same kind of planning information through informal English-like statements rather than pictures.

12. In a flowchart, which symbol represents a decision that can create different branches of execution?

A. The rectangular process symbol

B. The parallelogram input-output symbol

C. The oval start-and-end symbol

D. The diamond-like decision symbol

Answer: (D)

Explanation

The diamond-like symbol represents a decision and therefore supports branching in the flow of control. The oval identifies the start or end, while the parallelogram represents input or output.

13. Which statement correctly describes pseudocode?

A. It tests whether a program satisfies user requirements during execution

B. It describes algorithm operations in execution order using informal English-like language

C. It assigns values and compares conditions using programming syntax

D. It depicts algorithm paths with standardized graphical symbols and arrows

Answer: (B)

Explanation

Pseudocode is an informal, abstract description of an algorithm that lists operations in execution order without actual programming syntax. Graphical symbols and arrows characterize flowcharts, not pseudocode.

14. Which statement correctly distinguishes low-level languages from high-level languages?

A. Low-level languages require interpretation, while high-level languages execute directly on hardware.

B. Low-level languages are hardware-dependent, while high-level languages are easier to read and more portable.

C. Low-level languages are written in portable syntax, while high-level languages use binary instructions.fi

D. Low-level languages are easier to read, while high-level languages depend closely on specific hardware.

Answer: (B)

Explanation

Low-level languages are closely tied to hardware, whereas high-level languages are designed for readability and portability across platforms. The distractor claiming that high-level languages depend closely on hardware reverses the central distinction.

15. Which sequence correctly describes the main stages that transform C source code into an executing program?

A. Loader, compiler, assembler, preprocessor, linker, and execution

B. Preprocessor, compiler, assembler, linker, loader, and execution

C. Compiler, linker, preprocessor, loader, assembler, and execution

D. Assembler, preprocessor, compiler, execution, linker, and loader

Answer: (B)

Explanation

C processing proceeds through preprocessing, compilation, assembly, linking, loading, and execution. The other sequences place these translation and program-loading stages in an incorrect order.

16. How does a compiler differ from an interpreter when translating a program?

A. A compiler loads programs into memory, while an interpreter connects separately compiled object files.

B. A compiler translates the whole program before execution, while an interpreter handles instructions line by line.

C. A compiler executes each instruction as it is read, while an interpreter translates the whole program first.

D. A compiler converts machine code into source code, while an interpreter converts binary into assembly.

Answer: (B)

Explanation

A compiler translates the entire source program before it runs, whereas an interpreter translates and executes instructions incrementally. The claim that a compiler processes each instruction during execution describes interpreter behavior instead.

17. What does time complexity measure for an algorithm with input size $n$?

A. The amount of memory reserved for storing input and intermediate results

B. The physical time needed by a processor regardless of the input size

C. The number of constant-time execution steps as a function of input size

D. The number of programming languages required to implement the algorithm

Answer: (C)

Explanation

Time complexity describes execution time through the number of constant-time steps as input size changes. Memory requirements belong to space complexity, so the memory-focused distractor confuses the two measures.

18. Which expression represents the space complexity when fixed and instance-dependent storage are both considered?

A. $S(p) = \frac{A}{S_p(I)}$

B. $S(p) = A + S_p(I)$

C. $S(p) = A - S_p(I)$

D. $S(p) = A \cdot S_p(I)$

Answer: (B)

Explanation

Total space consists of fixed space $A$ plus variable space $S_p(I)$ determined by the problem instance. Multiplication, subtraction, and division do not represent this additive decomposition.

19. Which analysis evaluates the maximum number of operations an algorithm may perform over its possible inputs?

A. Best-case analysis

B. Worst-case analysis

C. Average-case analysis

D. Amortized storage analysis

Answer: (B)

Explanation

Worst-case analysis measures the maximum operations required among possible inputs. Best-case analysis measures the minimum, while average-case analysis estimates expected behavior across inputs.

20. A linear search checks an array and finds the target in its first position. What is the search time complexity in this situation?

A. $\Theta(n^2)$

B. $\Theta(n)$

C. $\Theta(1)$

D. $\Theta(\log n)$

Answer: (C)

Explanation

When the target is first, linear search performs a constant number of comparisons, giving $\Theta(1)$ best-case complexity. The bound $\Theta(n)$ applies when the target is absent or appears at the final position.

21. What are the exact time cost and asymptotic time bound of a single-loop summation with cost modeled by $T(n) = 2n + 3$?

A. Exact cost $2n^2 + 2n + 2$ and asymptotic bound $O(n^2)$

B. Exact cost $n + 3$ and asymptotic bound $O(1)$

C. Exact cost $2n^3 + 3n^2 + 2n + 2$ and asymptotic bound $O(n^3)$

D. Exact cost $2n + 3$ and asymptotic bound $O(n)$

Answer: (D)

Explanation

The single-loop summation has the stated exact cost $2n + 3$, whose dominant growth is linear, so its asymptotic time is $O(n)$. The quadratic and cubic expressions belong to matrix addition and matrix multiplication examples, respectively.

22. If matrix addition is performed on two $n \times n$ matrices, which time and space bounds apply?

A. Time $O(n^3)$ and space $O(n^2)$

B. Time $O(n)$ and space $O(n)$

C. Time $O(n^2)$ and space $O(n^3)$

D. Time $O(n^2)$ and space $O(n^2)$

Answer: (D)

Explanation

Matrix addition processes the entries of an $n \times n$ matrix, producing both time and space bounds of $O(n^2)$. Cubic time is associated with the matrix multiplication example, not matrix addition.

23. For matrix multiplication with exact cost $T(n) = 2n^3 + 3n^2 + 2n + 2$, what are its asymptotic time and space bounds?

A. Time $O(n^3)$ and space $O(n^2)$

B. Time $O(n)$ and space $O(n^2)$

C. Time $O(n^2)$ and space $O(n^2)$

D. Time $O(n^3)$ and space $O(n^3)$

Answer: (A)

Explanation

The cubic term dominates the exact time expression, giving time complexity $O(n^3)$, while the stored matrices require space $O(n^2)$. A cubic space bound incorrectly treats the multiplication time growth as memory growth.