Chapter 2

Question 1

What is involved in the process of program development?

Answer 1

Problem description

• Input
• Result (output)

Algorithm

• Pseudocode is fine

Program

• Java, C, Python

Machine instructions (executable)

Question 2

How is pseudocode created?

Answer 2

It’s created from using components of natural language to express algorithms

• Pseudocode = “Not real” Code

Question 3

What are some issues with using natural language to represent algorithms?

Answer 3

• Natural language can be extremely verbose
• Lack of structure makes it difficult to locate specific sections of the algorithm
• Natural language is too “rich” in interpretation and meaning
• Not sufficiently precise to represnt algorithms

Question 4

Why is using pseudocode beneficial?

Answer 4

• Used to design and represent algorithms
• A compromise between the two extremes of natural and formal languages
• Will not be unique

Question 5

Define:

Sequential Algorithm

Answer 5

Sometimes called a straight-line algorithm; the order is followed in a linear fashion.

Question 6

Define:

Control Operations

Answer 6

• Conditional and iterative
• Allow us to alter the normal sequential flow of control in an algorithm

Question 7

Define:

Conditional Statements

Answer 7

• The “question-asking” operations of an algorithm
• If/then/else

Question 8

Define:

Loop

Answer 8

• The repetition of a block of instructions
• While or For loop statement

Question 9

Define:

Continuation Condition

Answer 9

Determines if statement is true or false

• if/elif statements

Question 10

Give an example of a loop.

Answer 10

Question 11

Define:

Pretest Loop

Answer 11

Continuation condition is tested at the beginning of each pass through the loop

Question 12

Define:

Posttest Loop

Answer 12

Continuation condition is tested at the end of the loop body, not the beginning.

Question 13

Define:

Primitives

Answer 13

Instructions that computing agent understands and is capable of executing without further explanation.

Question 14

Define:

Pattern Matching

Answer 14

• Process of searching for a special pattern of symbols within a larger collection of information.
• Is assisting microbiologist and geneticists studying and mapping the human genome.

Question 15

Give examples of higher-level constructs.

Answer 15

• Sort the entire list into ascending order.
• Attempt to match the entire pattern against the text.
• Find a root of the equation.

Question 16

Define:

Abstraction

Answer 16

Use of high-level instructions during the design process

Question 17

Define:

Top-down Design

Answer 17

Viewing an operation at a high level of abstraction

Question 18

How to test efficiency of algorithms?

Answer 18

Run Time Analysis

• Worst Case
• Average Case

Big Oh

• Constant run time O(1)
• Logarithmic run time O(logn)
• Linear run time O(n)
• Linearithmic run time O(nlogn)
• Quadratic run time O(n²)

Question 19

How to test efficiency of direct sequecing algorithms?

Answer 19

For a sequence of instructions, the cost of executing the sequence of instructions is, asymptotically speaking, the same as the maximum cost of the individual instructions.

For three instructions a, b and c:

• O({a, b, c}) = max (O(a), O(b), O(c))

where {a, b, c} represents direct sequencing of the three individual instructions.

Question 20

How to test effeciency for conditional execution algorithms?

Answer 20

For a conditional statement, the cost of execution is the maximum of the cost of evaluating the condition and the cost(s) of the alternate instruction sequences

• O(if {condition} then {sequence1} else {sequence2}) = max (O(condition), O(sequence1), O(sequence2))

Question 21

How to test the effeciency of iterative construct algorithms?

Answer 21

Applies to an iterative construct ( e.g., loop, for, while) that will cause the execution of a subset of instructions to be repeated a specified number of times.

The trick is to understand how many times the instructions will be repeated.

For k iterations, the general rule is:

• O(loop (k) {sequence}) = O(k*sequence)