Problem Solving

Question 1

what is an algorithm

Answer 1

• a step by step procedure needed to solve a problem

Question 2

define sequence

Answer 2

• the specific order which instructions are performed in an algorithm.

Question 3

define iteration

Answer 3

• repeating code for a certain amount of times or until a condition is met

Question 4

define selection

Answer 4

• decisions are made and a course of action is selected

Question 5

give some examples of sequence (programming construct) in an algorithm for authenticating a users logon details

Answer 5

• enter password

- increase number of attempts by 1

Question 6

give some examples of iteration (programming construct) in an algorithm for authenticating a users logon details

Answer 6

• return to step 1

- return to step 4

Question 7

give some examples of selection (programming construct) in an algorithm for authenticating a users logon details

Answer 7

• if username is recognised, set number of attempts to 1

- if p/word doesnt match stored p/word and attempt number is 3 tell user p/word is incorrect

Question 8

why is sequencing important when coding

Answer 8

• the algorithm will not work correctly

Question 9

state 2 other ways of displaying algorithms

Answer 9

• pseudo-code

- flowcharts

Question 10

what is meant by the term pseudo-code

Answer 10

a way of expressing an instruction in structured english that resembles computer language

Question 11

desbribe how a linear search algorithm works

Answer 11

• starts at the begginning of the list & moves through item by item until it finds the matching item or reaches end of the list
• it is sequential and an example of a brute force algorithm
• not efficient (smaller the list more efficient the search)

Question 12

describe the stages of a binary search on a list of items sorted in ascending order

Answer 12

• yh7

Question 13

list:
ahmed ann claire david mary matt peter stephen zoe

show the stages of a binary search to find the name stephen

Answer 13

-

Question 14

1 6 9 13 15 21 22 33 36 42 69 76 85

show the stages of a binary search to find the number 9

Answer 14

• the median item is 22. this is higher than the search item therefore the all numbers ahead of 22 are discarded
• the sublist to the left is used 1, 6, 9, 13, 15, 21
• the median of the sublist is 9 which is the search item

Question 15

when searching a list of 100 items, the largest number of comparisons a linear search would have ti make would be 100
show the max number of comparisons using a binary search of the same list wouldbe 7

Answer 15

-

Question 16

explain why using a linear search may be quicker than using a binary search in certain circumstances

Answer 16

-

Question 17

show the stages of a bubble sort when sorting this list into ascending order
20 15 3 13 9 2 6

Answer 17

-

Question 18

explain the advantage of using the merge sort algorithm

Answer 18

-

Question 19

state what is mean by abstraction

Answer 19

-

Question 20

what is a brute force algorithm

Answer 20

• doesnt use any specialist techniques only raw computing power
• not efficient as it starts at beginning of the list & continues until item is found/ end of list is reached

Question 21

how do you find the efficiency of a linear search

Answer 21

• in best case its first item in list
• in worst case its last item in list
• average case: (total items + 1)/ 2

Question 22

desbribe an algorithm for carrying out a linear search

Answer 22

1. if length is zero, stop
2. start at the beginning of the list
3. compare list item with search item (critereon)
4. if theyre the same, stop
5. if theyre not the same, move to next item of the list
6. repeat steps 3-5 until end of list

Question 23

describe an algorithm for carrying out bubble sort

Answer 23

1. start at the beginning of the list
2. compare values of position 1 & 2 in the list. if theyre not in ascending order, swap
3. compare values of position 2 & 3 & swap if necessary
4. continue to the end of the list
5. if there has been any swaps, repeat steps 1-4

Question 24

what is a traversal method of sorting numbers

Answer 24

moving through each item of a list first to last in ordeer and sorting them one by one ie bubble sort

Question 25

what is a recursion method of sorting numbers

Answer 25

splitting up the list into smaller chunks and solving it this way then putting it back together ie merge sort

Question 26

compare the efficiency of merge sort and bubble sort when sorting a list of numbers in order

Answer 26

- merge sort and bubble sort have similar efficiencies for lists of less than 100 items - for lists over 1000 merge sort is much less efficient than bubble sort as it uses a brute force method

Question 27

what does a searching algorithm do

Answer 27

finds a specific item in a list

Question 28

describe an algorithm for carrying out binary search

Answer 28

1. select the median item of a list 2. if median is equal to search item, stop 3. if median is too high, repeat steps 1-2 with the sublist to the left 4. if median is too low, repeat steps 1-2 with the sublist to the right 5. repeat steps 3-4 until item has been found or all items have been checked

Question 29

compare the efficiency of linear and binary search when searching a list of 1000 items to find a number

Answer 29

- linear. best case is item is first item in the list; worst casr is item is last item in the list. - the average is 500 comparisons for linear search - binary. best case is item is at the median position in list so only needs 1 comparison; worst case is 10 attempts of choosing the medians (500, 250, 125, 63...) binary is far more efficient

Question 30

name one disadvantage for binary search

Answer 30

a sorting algorithm must be applied to the list as it must already be sorted into ascending/descending order before searching

Question 31

describe the differences between the bubble sort and merge sort algorithms

Answer 31

-

Question 32

explain when a linear search might be preferable to a binary search even though the binary search algorithm is more efficient

Answer 32

-

Question 33

discuss the advantages of using arrays in algorithms

Answer 33

-

Question 34

give the advantages of doing a dry run and using trace tables to test out algorithms

Answer 34

- helps to understand any errors in the algorithm | - helps to understand the processes and the possible outcomes of the future program

Question 35

descbribe one benefit and one drawback of using binary rather than linear search

Answer 35

LINEAR + uses a strategy to minimise the number of comparisons that are made and is therefore more efficient than linear search when there are a lot of items in the list - the data must first be sorted into ascending order. sorting the data will take and reduce the overall efficiency

Question 36

give an example of a logic error

Answer 36

if variable == 20: | variable + 2

Question 37

give an example of a syntax error

Answer 37

- pint ("hello")

Question 38

give an example of a runtime error

Answer 38

- 0/2