Flashcards: Problem Solving and Algorithm Analysis — 54 cards

Why is a computer called a dumb machine?

It operates strictly according to instructions and cannot perform tasks without software.

What is the first step in the program-development process?

Requirements specification.

Which step follows problem analysis in program development?

Algorithm design.

What is the final step in the program-development process?

Documentation.

What does requirements specification state about the problem?

It states the problem, required inputs and resources, expected outputs, and constraints.

What are the inputs in the apple-cost problem example?

Apple quantity in kilograms and cost per kilogram.

What is the output in the apple-cost problem example?

Total cost in rupees.

What is the formula for total cost in the apple-cost problem?

Total cost equals cost per kilogram multiplied by quantity.

What defines an algorithm in problem solving?

A complete, unambiguous, finite sequence of logical steps.

What must an algorithm's instructions be?

Clear and unambiguous.

What inputs and outputs must an algorithm have?

Zero or more well-defined inputs and one or more well-defined outputs.

What are two essential properties of an algorithm's execution?

Finite termination and feasible operations.

What independence does an algorithm have?

It is independent from programming code.

Which variables does the average-of-three-numbers algorithm read?

Variables a, b, and c.

What operations does the average-of-three-numbers algorithm perform?

It sums a, b, and c, divides by 3, stores in d, prints d, and ends.

What are the major steps in top-down algorithm design?

Get the data, perform computations, and display the result.

What three requirements must a top-down algorithm meet?

Correctness, finiteness, and efficiency.

What initial values does the factorial algorithm set?

Factorial to 1 and i to 1.

What condition controls the factorial algorithm's loop?

i is less than or equal to n.

What operation is repeated inside the factorial algorithm's loop?

Multiplying factorial by i.

What does the factorial algorithm do after completing the loop?

Prints factorial.

What is program testing?

The process of executing a program to demonstrate its correctness.

What is program verification?

The process of ensuring that a program meets user requirements.

What does program documentation include?

In-line comments and separate external files.

How does program documentation help others and the original programmer?

It helps others modify the program and helps the original programmer understand it later.

What is a flowchart?

A graphical representation of an algorithm’s logic paths and operation sequence.

Which symbol represents start and end in flowcharts?

The oval terminator symbol.

What is pseudocode?

An informal, English-like description of an algorithm without programming syntax.

What does A = 10 mean in programming?

It assigns the value 10 to A.

What does A == 10 test in programming?

Whether A equals 10.

What distinguishes low-level from high-level programming languages?

Low-level languages are hardware-close and machine-dependent, high-level are readable and portable.

What does machine-level language consist of?

Binary instructions made of 1s and 0s.

How does machine-level language execute on hardware?

It executes directly without a compiler or interpreter.

What must assembly language be translated into?

Machine code by an assembler.

Name some mnemonics used in assembly language.

ADD, SUB, INR, DCR, and CMP.

What stages does the C compilation process include?

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

How does a compiler translate source code?

It translates the entire program before execution.

How does an interpreter process source code?

It translates and executes instructions line by line.

What does time complexity measure in an algorithm?

The time or number of constant-time steps as a function of input size n.

What is the time requirement formula for adding two n-bit integers?

$t(N) = c \cdot n$

How is space complexity expressed mathematically?

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

What does A represent in the space complexity formula?

Fixed space independent of the problem instance.

What does $S_p(I)$ represent in space complexity?

Variable space dependent on the problem instance.

What does best-case analysis measure in algorithm complexity?

The minimum number of operations performed.

What does worst-case analysis measure in algorithm complexity?

The maximum number of operations performed.

What is the best-case time complexity of linear search?

Θ(1) when the item is first.

What is the exact time cost formula for single-loop summation?

$T(n) = 2n + 3$

What is the asymptotic time bound for single-loop summation?

$O(n)$

What is the space bound for single-loop summation and why?

$O(n)$ because of the array.

What is the exact time cost formula for matrix addition?

$T(n) = 2n^2 + 2n + 2$

What are the time and space bounds for matrix addition?

Both are $O(n^2)$.

What is the exact time cost formula for matrix multiplication?

$T(n) = 2n^3 + 3n^2 + 2n + 2$

What is the time bound for matrix multiplication?

$O(n^3)$

What is the space bound for matrix multiplication?

$O(n^2)$