Chapter 5: Algoithms

Question 1

Formal definition of algorithm

Answer 1

An algorithm is an ordered set of unambiguous, executable steps that define a terminating process.

Question 2

Algorithm representation

Primitives:

Programming language:

Answer 2

• Primitives: a well-defined set of building blocks from which algorithm representation can be constructed.
• Programming language: a collection of primitives along with a collection of rules stating how the primitives can be combined.

Question 3

What is a flow chart?

Answer 3

A flow chart is a picture of the separate steps of a process in a sequential order

Question 4

What’s pseudo code?

Answer 4

It’s a notational system in which algorithms can be expressed (less formal than real programming language code)

Question 5

Loop control

Answer 5

• Initialize : establish an initial state
• Test: continue only if the current state fulfills the loop condition
• Modify: change the state towards a termination state

Question 6

Iterative structures

Answer 6

• Pre test loop: 0 try if condition false

- Post test loop: 1 try if condition false

Question 7

Insertion sort

Answer 7

• Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

Question 8

Recursion

Answer 8

• The execution of a procedures leads to another execution of the procedure
• Multiple activations of the procedure are formed, all but one of which are waiting for other activations to complete.
• Recursion is a function or method that has the ability of calling itself to solve the problem

Question 9

Algorithm efficiency

Answer 9

• Measured as number of instructions executed
• Big theta O with a - in it (and Big O) notation is used to represent efficiency classes:
  
  • insertion sort is Big theta(n^2)
  • sequential search is Big theta(n)
  • binary search is Big theta(log n)

Question 10

Software verification

Answer 10

• Static verification (code analysis) and testing