Problem Solving Flashcards Preview

Computing > Problem Solving > Flashcards

Flashcards in Problem Solving Deck (38):

what is an algorithm

- a step by step procedure needed to solve a problem


define sequence

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


define iteration

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


define selection

- decisions are made and a course of action is selected


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

- enter password
- increase number of attempts by 1


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

- return to step 1
- return to step 4


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

- 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


why is sequencing important when coding

- the algorithm will not work correctly


state 2 other ways of displaying algorithms

- pseudo-code
- flowcharts


what is meant by the term pseudo-code

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


desbribe how a linear search algorithm works

- 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)


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

- yh7


ahmed ann claire david mary matt peter stephen zoe

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



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

- 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


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



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



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



explain the advantage of using the merge sort algorithm



state what is mean by abstraction



what is a brute force algorithm

- 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


how do you find the efficiency of a linear search

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


desbribe an algorithm for carrying out a linear search

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


describe an algorithm for carrying out bubble sort

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


what is a traversal method of sorting numbers

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


what is a recursion method of sorting numbers

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


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

- 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


what does a searching algorithm do

finds a specific item in a list


describe an algorithm for carrying out binary search

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


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

- 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


name one disadvantage for binary search

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


describe the differences between the bubble sort and merge sort algorithms



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



discuss the advantages of using arrays in algorithms



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

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


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

+ 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


give an example of a logic error

if variable == 20:
variable + 2


give an example of a syntax error

- pint ("hello")


give an example of a runtime error

- 0/2