Chapter 1 Algorithms

Question 1

Definition of an Algorithm

Answer 1

An algorithm is a FINITE sequence of operations
To carry out a procedure or solve a problem

Question 2

What are the three things an algorithm MUST BE

Answer 2

1) UNAMBIGOUS
- the program should never have to make a choice at any point, based on conditions it must be sble to know what to do

2) DETERMINISITIC
- can’t have probabilities of going down paths (no chance involved)

3) FINITE
- CAN NOT LOOP FOREVER , must have some end and stop

Question 3

What is the most typical problem with an algorithm if they say there is one

Answer 3

It’s not finite, it loops forever most likely

Question 4

Algorithm flowchart shaped and meaning

Kite rectangle circle parallelogram

Answer 4

Circle = start stop

Parallelogram = input or output (variable or text)

Rectangle = common (add x+y)

Kite = IF STATEMENT ! Decision

Question 5

How to make and fill out a TRACE TABLE

Answer 5

make a table with all variables as column headings, along with a PRINT column

• then for each time you go down a line in the code, go down a row

Keep doing this and fill it out

Question 6

How to try work out what an algorithm is trying to do once yiu traced it out

Answer 6

Look at print column and try find a pattern, like fibonacci or mean etc

Question 7

What does algorithmic complexity describe

Answer 7

Describes the EFFICIENCY OF THE ALGORITHM
- some algorithms can achieve same thing with less steps, you rather take this as it tskes less power

Question 8

Big O notation what does it show

What case scenario does it show

Answer 8

It represents complexity, and shows the steps needed when an algorithm SCALES UP

• for any algorithm it represents the WORSE case scenario

Question 9

Explain how Big O works and what mean by worse case scenario

Answer 9

Example complexity of algorithm is O(N2)
For 10 commands, it takes a time of 5 seconds
And yiu make it 20 commands, the time will increase to 20 seconds, increases by a factor of 4!

2) now this is the worse case scenario , so like if the algorithm had to do the most steps each time , not necessarily gonna take this much time

Question 10

Worse case scenario again

Answer 10

Bubble sort best case could be order n but worse case order n 2

So big O Notation takes the WORSE one

Question 11

What complexity is the algorithm typically if there is a COUNTER VARIABLE

Answer 11

This will be O(N)

This because the time is proportional to the counter, increase counter increase time linearly