Flashcards in Problem Solving Deck (38):
1
what is an algorithm
- a step by step procedure needed to solve a problem
2
define sequence
- the specific order which instructions are performed in an algorithm.
3
define iteration
- repeating code for a certain amount of times or until a condition is met
4
define selection
- decisions are made and a course of action is selected
5
give some examples of sequence (programming construct) in an algorithm for authenticating a users logon details
- enter password
- increase number of attempts by 1
6
give some examples of iteration (programming construct) in an algorithm for authenticating a users logon details
- return to step 1
- return to step 4
7
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
8
why is sequencing important when coding
- the algorithm will not work correctly
9
state 2 other ways of displaying algorithms
- pseudo-code
- flowcharts
10
what is meant by the term pseudo-code
a way of expressing an instruction in structured english that resembles computer language
11
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)
12
describe the stages of a binary search on a list of items sorted in ascending order
- yh7
13
list:
ahmed ann claire david mary matt peter stephen zoe
show the stages of a binary search to find the name stephen
-
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
- 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
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
-
16
explain why using a linear search may be quicker than using a binary search in certain circumstances
-
17
show the stages of a bubble sort when sorting this list into ascending order
20 15 3 13 9 2 6
-
18
explain the advantage of using the merge sort algorithm
-
19
state what is mean by abstraction
-
20
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
21
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
22
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
23
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
24
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
25
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
26
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
27
what does a searching algorithm do
finds a specific item in a list
28
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
29
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
30
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
31
describe the differences between the bubble sort and merge sort algorithms
-
32
explain when a linear search might be preferable to a binary search even though the binary search algorithm is more efficient
-
33
discuss the advantages of using arrays in algorithms
-
34
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
35
descbribe one benefit and one drawback of using binary rather than linear search
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
36
give an example of a logic error
if variable == 20:
variable + 2
37
give an example of a syntax error
- pint ("hello")
38