Unit 3 - Algorithms and data structures

Question 1

What is an algorithm?

Answer 1

A set of rules of instructions for completing a task.

Question 2

Why don’t algorithms give perfect results?

Answer 2

The perfect result is not efficient and takes a lot more time than ‘good enough’.

Question 3

What type of problems are algorithms very useful for?

Answer 3

Recurrent problems where you can perform the same task over and over again.

Question 4

What is a flowchart?

Answer 4

It is used to translate human instruction into computer instruction.

Question 5

What is a terminator in a flowchart?

Answer 5

It is used at the beginning and end, representing the external node of a flow. You use an oval.

Question 6

What is a Process in a flowchart?

Answer 6

A rectangle representing a process such as data calculation or filtering.

Question 7

What is a decision in a flowchart?

Answer 7

Diamond shaped indicating a choice and multiple possible paths.

Question 8

What is input/output in a flowchart?

Answer 8

A parallelogram, data is sent into or out of the process.

Question 9

What does an arrow do in a flowchart?

Answer 9

It represents the direction of the flow.

Question 10

What is a stack?

Answer 10

It is a data structure with the philosophy Last in, First Out (LIFO)

Question 11

What operations does a stack have?

Answer 11

Push: Add a new item to the top. Used to populate the stack with data.
Pop: Removes the top piece of data from the stack. Used to read the value and then remove it.

Question 12

What are characteristics of a stack?

Answer 12

Takes up a low amount of space, but cannot be searched randomly. Random Access Memory is not possible with Stack.

Question 13

What is a linked list?

Answer 13

It is a sequential storage structure where each element is linked to the next. The last element has no pointer and so points to null.

You can insert elements in the middle of the sequence, but it is still allowing quick access. More flexibility than a stack.

There is no restriction on number of elements. It is unbounded.

Question 14

What is an array?

Answer 14

A sequential data structure. Takes more memory but allows for random access for reading and writing. They are usually bounded meaning they have a predetermined size.

Each element has an index that identifies it, starting at 0.

Question 15

What is a multi-dimensional array?

Answer 15

Imagine a checkerboard, you give coordinates to the array. You can have more than two dimensions but this makes it a lot more complex.

Checkerboard[3,5] “Red

Question 16

What is binary search?

Answer 16

Slicing the data size in two by jumping in the middle and then based on the information there, move left or right.

Question 17

What is linear search?

Answer 17

You start at the beginning and look at each element until you find what you want.

Question 18

What is jump search?

Answer 18

You jump forward in pre-determined steps. For a 2500-page book, jump 50 pages each time until you’re past your objective. Then, go back one jump and continue with linear search.

Question 19

What is bubble sort?

Answer 19

You compare two values at a time and sort those, putting the largest on top. After doing this for all elements, you start at the top again and repeat. The large values will ‘bubble’ to the top.

Amount of passes is n-1 ( one less than the total amount of elements).

Question 20

What is a modified bubble sort?

Answer 20

An enhanced version of bubble sort, you stop when a whole pass did not produce any swaps. That way you don’t have to do the full n-1 passes.

Question 21

What is binary insertion sort?

Answer 21

Take a list of elements (input list) and put them in a new list one by one (output list). If it has 5 values, divide it in two. Look at the middle value and keep dividing in two until you find the place where you need to insert the next value. It is slightly faster than bubble sort.

Question 22

What is quicksort?

Answer 22

An efficient sorting algorithm, but also more complex. Divide your data in two piles, one with higher values and one with lower. Divide them again until you have 4 piles. Sort each pile in the normal fashion. After that you can place the four piles on top of each other.

Question 23

What is an exhaustive search?

Answer 23

Calculating every single possibility of a route / problem. Not an optimal algorithm.

Question 24

What is algorithm termination?

Answer 24

A place where the algorithm stops calculating. it needs to know when to do this beforehand.

Question 25

What is algorithm complexity?

Answer 25

How many operations an algorithm requires to complete a task. The more operations, the more complex and thus more time and energy.

Question 26

What does the big O stand of?

Answer 26

The mathematical complexity of an algorithm.

Question 27

What is a constant algorithm complexity?

Answer 27

The exact number of steps is needed, no matter the data size.

O(n)

Question 28

What is a linear algorithm complexity?

Answer 28

It takes (close to) as many steps as the size of the data set.

O(n)

Question 29

What is a N*Log algorithm? Name an example.

Answer 29

Algorithm where O is n times the logarithm of n. Close to as efficient as linear for a lot of data sets.

Example: quick sort.

Question 30

What is a quadratic algorithm? Name an example.

Answer 30

The number of steps is the square of the data set size.

O(n2)

Example: Bubble sort and binary insertion.

Question 31

What is a cubic algorithm?

Answer 31

The number of steps are the data size cubed.

O(n^3)

Question 32

What is an exponential algorithm?

Answer 32

A complexity with an exponent above 3 raised to the power of n.

O(n^k)