Algorithms

Question 1

What is an algorithm?

Answer 1

A series of steps to solve a given problem

Question 2

What is algorithmic thinking?

Answer 2

A way of solving problems by producing algorithms

Question 3

Writing down an algorithm

Answer 3

Can be written as a set of numbered steps to follow

Question 4

What is often used to represent algorithms?

Answer 4

Pseudocode or flow diagrams

Question 5

How do you interpret an algorithm?

Answer 5

Identify what the algorithm does

Question 6

What is a search algorithm?

Answer 6

A set of instructions for finding a specific item of data within a data set

Question 7

What is an effective search?

Answer 7

A search that will either find the solution or determine that the target data is not present

Question 8

What is an efficient search?

Answer 8

Will find the solution quickly regardless of its location within the data set

Question 9

What are examples of search algorithms?

Answer 9

1) linear search 2) Binary search

Question 10

What is linear search?

Answer 10

A simple searching algorithm

Question 11

What is the concept of linear search?

Answer 11

If you were looking for a specific piece of paper in a stack of papers, then one way to find it would be to work from the top of the stack to the bottom, checking each paper on the way.

Question 12

Linear search -

Answer 12

1) Check the first item in the dataset:
- if it is what we are looking for, return it
2) Check the second item in the dataset:
- if it is what we are looking for, return it
3) Continue for the rest of the items

Question 13

What does it mean when you reach the end of the dataset in linear search?

Answer 13

The item was not in the data set

Question 14

Linear search pseudocode example =

Answer 14

for item in dataset
 if item = target then
     return True
   endif
endfor
return False

Question 15

What are the pros of linear search?

Answer 15

Very easy to implement

Question 16

What are the cons of linear search?

Answer 16

Slow on a longer list

Question 17

What is binary search?

Answer 17

A divide and conquer algorithm

Question 18

What is the concept of binary search?

Answer 18

If you try to find a certain page in a book, it’s unlikely that you check every page on the way
- you are more likely to split the book in 2 then see if the page you need is before or after the split & repeat

Question 19

Binary search -

Answer 19

1) Find the middle of the dataset
- if the middle value is greater than the target then:
- - repeat on first half of dataset
2) If the middle value is lesser than the target then:
- repeat on second half of dataset
3) If the middle value is the target:
- We found it
4) Stop repeating once the size of our dataset is zero

Question 20

Binary search pseudocode example =

Answer 20

dataset = [...] 
min = 0; max = len(dataset)

while (min target then
max = midpt - 1
else if dataset+ [midpt] < target then
min = midpt + 1
endif
endwhile
return False

Question 21

What are the pros of binary search?

Answer 21

Faster than linear search on a large dataset

Question 22

What are the cons of binary search?

Answer 22

Dataset must be sorted before starting

Question 23

What are the 3 basic constructs when needed to design an algorithm?

Answer 23

Iteration, Selection & Sequence