Problem Solving Flashcards
(38 cards)
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
list:
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
- if length is zero, stop
- start at the beginning of the list
- compare list item with search item (critereon)
- if theyre the same, stop
- if theyre not the same, move to next item of the list
- repeat steps 3-5 until end of list
describe an algorithm for carrying out bubble sort
- start at the beginning of the list
- compare values of position 1 & 2 in the list. if theyre not in ascending order, swap
- compare values of position 2 & 3 & swap if necessary
- continue to the end of the list
- 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