Part 6, Algorithms

Question 1

finish the sentence

a well written algorithm can be

Answer 1

implemented into many different programming languages

Question 2

give a definition that would describe an algorithm for a program

Answer 2

a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.

Question 3

what is this sentence a definition of

a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.

Answer 3

this is the definition of an algorithm for a program

Question 4

what is meant by unambiguous in the definition for a programs algorithm

a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.

Answer 4

the term unambiguous means that no part of the algorithm is open to interpretation

the algorithm is therefore written clearly and precise for the benefit of the computer and anyone wanting to reuse the algorithm

Question 5

what is meant by self contained in the definition for a programs algorithm

a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.

Answer 5

the term self contained means that the algorithm contains all information it needs

therefore when using the algorithm it will require no external sources of information or extra work put into it

Question 6

what is meant by step-by-step instructions in the definition for a programs algorithm

a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.

Answer 6

step-by-step instructions means that the algorithm is written in steps which eventually lead to the desired outcome

this is much like the steps written in a recipe

Question 7

an algorithm needs refinement/decomposition

what does this mean

Answer 7

this means the algorithm is open to more than one interpretation

it should be refined or decomposed until all ambiguities have been resolved

Question 8

an algorithm is open to more than one interpretation what two terms describe the process it must go through to rid it of the open interpretation

Answer 8

refinement

decomposition

Question 9

what method might you use to refine an algorithm that is open to more than one interpretation

Answer 9

break the step down into several smaller clearer steps

Question 10

how can you tell when an algorithm is refined fully

Answer 10

the algorithm will be clear and precise to the author and any audience that uses it

Question 11

what four fundamental features do all algorithms share

Answer 11

1. inputs and outputs
2. sequence of instructions
3. repetition of instructions
4. selection of instructions

Question 12

what shares these four features

1. inputs and outputs
2. sequence of instructions
3. repetition of instructions
4. selection of instructions

Answer 12

algorithms

Question 13

an algorithm will follow a sequence of instructions unless
1.
2.

Answer 13

1. there is repetition in which case the algorithm repeats a set of instructions until the loop is broken
2. there is selection. in which case the sequence of instructions will branch to different sequence of instructions and outcomes

Question 14

name four input sources an algorithm might get its data from

Answer 14

1. the user
2. a constant unchangeable value written in the algorithm
3. data from the current environment (current time, current mouse position)
4. lists

Question 15

what is a case instruction or a switch statement

Answer 15

this can be used in contrast to selection.

instead an input variable is assessed then if the variable exists as a case or switch then it has its block of code ran

switch (variable or an integer expression)
{
     case constant:
     //C Statements
     ;
     case constant:
     //C Statements
     ;
     default:
     //C Statements
     ;
}

Question 16

this can be used in contrast to selection.

instead an input variable is assessed then if the variable exists as a case or switch then it has its block of code ran

switch (variable or an integer expression)
{
     case constant:
     //C Statements
     ;
     case constant:
     //C Statements
     ;
     default:
     //C Statements
     ;
}

Answer 16

case instruction/switch statement

Question 17

what two ways can you judge if an algorithm is good or not

Answer 17

1. readability - are its steps clearly laid out and self explanatory
2. efficiency - is it written in its most efficient form. that is can it be re written to perform the same outcome quicker and with less effort

Question 18

how can you tell if an algorithm has good readability

Answer 18

the steps will be clear and precise to all. this includes the author and any audience that uses it

Question 19

name two ways you can increase the efficiency of an algorithm

Answer 19

1. reduce the number of steps while still maintaining the desired outcome
2. reduce the number of calculations while still maintaining the desired outcome

Question 20

describe the three steps of the swapping algorithm

Answer 20

1. set temp to item 2
2. set item 2 to item 1
3. set item 1 to temp

Question 21

what does this algorithm do

1. set temp to item 2
2. set item 2 to item 1
3. set item 1 to temp

Answer 21

swaps two items

Question 22

describe a sorting algorithm

Answer 22

a sorting algorithm takes a list of unsorted items and then sorts the items by a given rule

Question 23

takes a list of unsorted items and then sorts the items by a given rule

Answer 23

sorting algorithm

Question 24

what rules might be applied to sort items in a list

1 - 4

Answer 24

1. sort numbers in ascending/descending order
2. sort words alphabetically in ascending/descending order
3. sort by length of item in ascending/descending order
4. sort by price in ascending/descending order

Question 25

what are the three steps for the selection sort algorithm

Answer 25

repeat until (only 1 item of unsorted data remains) - ------- find the lowest item in the unsorted data - ------- swap the lowest item with the first item in the ------------ unsorted data

Question 26

what algorithm is this repeat until (only 1 item of unsorted data remains) - ------- find the lowest item in the unsorted data - ------- swap the lowest item with the first item in the ------------ unsorted data

Answer 26

selection sort algorithm

Question 27

name two features of the selection sort algorithm

Answer 27

1. always makes the same number of comparisons regardless of lists initial state sorted or unsorted 2. has a non linear line on a graph. as the number of items to sort increases the number of comparisons grows faster

Question 28

1. always makes the same number of comparisons regardless of lists initial state sorted or unsorted 2. has a non linear line on a graph. as the number of items to sort increases the number of comparisons grows faster

Answer 28

features of the selection sort algorithm

Question 29

describe a not in place sort

Answer 29

this uses two lists two sort data unsorted list - holds the initial unsorted data. is either emptied while being sorted or its state is left unchanged sorted list - is initially empty but is filled with items from the unsorted list as the items are sorted

Question 30

this uses two lists two sort data unsorted list - holds the initial unsorted data. is either emptied while being sorted or its state is left unchanged sorted list - is initially empty but is filled with items from the unsorted list as the items are sorted

Answer 30

not in place sort

Question 31

describe an in place sort

Answer 31

uses only one list and upon sorting is abstracted into two lists. the unsorted items and the sorted items pass 1 - the entire list is unsorted (1 list) pass 2 - the list has 1 sorted item (2 lists) pass 3 - the list has 2 sorted items (2 lists) repeat until there is only one unsorted item (essentially 1 sorted list)

Question 32

uses only one list and upon sorting is abstracted into two lists. the unsorted items and the sorted items pass 1 - the entire list is unsorted (1 list) pass 2 - the list has 1 sorted item (2 lists) pass 3 - the list has 2 sorted items (2 lists) repeat until there is only one unsorted item (essentially 1 sorted list)

Answer 32

in place sort

Question 33

which of these two methods is more likely to be used 1. in place sort 2. not in place sort

Answer 33

an in place sort is more likely to be used as it is more elegant and efficient as items are contained within one list no extra memory is required

Question 34

describe the bubble sort algorithm/sinking sort algorithm

Answer 34

this sorts items in a way that the sorted items will bubble or sink to either end of the list

Question 35

the bubble sort algorithm contains a swapping pass describe what it does

Answer 35

looks at the first item in the list and compares it to the adjacent item if they are in the wrong order they are swapped. it then moves to the next item and repeats until there are no more adjacent items the swapping pass sorts 1 item

Question 36

what are the four steps in the swapping pass

Answer 36

starting at the beginning of the list repeat for (each pair of adjacent items) -------- if items are in the wrong order then ---------------- swap them

Question 37

what is this starting at the beginning of the list repeat for (each pair of adjacent items) -------- if items are in the wrong order then ---------------- swap them

Answer 37

bubble sort algorithms swapping pass

Question 38

what are the 8 steps of the bubble sort algorithm written in its most efficient form

Answer 38

set flag to true repeat until (flag is false) ---- set flag to false ---- starting at the beginning of the list ---- repeat for (each pair of adjacent items in the -------------- unsorted portion) -------- if items are in wrong order then ------------ swap them ------------ set flag to true

Question 39

what algorithm is this set flag to true repeat until (flag is false) ---- set flag to false ---- starting at the beginning of the list ---- repeat for (each pair of adjacent items in the -------------- unsorted portion) -------- if items are in wrong order then ------------ swap them ------------ set flag to true

Answer 39

bubble sort algorithm

Question 40

name two features of the bubble sort algorithm

Answer 40

1. can stop sorting a sorted list after 1 iteration because of its use of a flag 2. shares the same non linear line on a graph of selection sort when reverse sorting

Question 41

1. can stop sorting a sorted list after 1 iteration because of its use of a flag 2. shares the same non linear line on a graph of selection sort when reverse sorting

Answer 41

features of the bubble sort algorithm

Question 42

name 3 sorting algorithms

Answer 42

1. selection sort 2. bubble sort 3. merge sort