Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computing > Problem Solving > Flashcards

Problem Solving Flashcards

1
Q

what is an algorithm

A
  • a step by step procedure needed to solve a problem
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

define sequence

A
  • the specific order which instructions are performed in an algorithm.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

define iteration

A
  • repeating code for a certain amount of times or until a condition is met
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

define selection

A
  • decisions are made and a course of action is selected
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A
  • enter password

- increase number of attempts by 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A
  • return to step 1

- return to step 4

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

why is sequencing important when coding

A
  • the algorithm will not work correctly
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

state 2 other ways of displaying algorithms

A
  • pseudo-code

- flowcharts

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

what is meant by the term pseudo-code

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

desbribe how a linear search algorithm works

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A
  • yh7
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

list:
ahmed ann claire david mary matt peter stephen zoe

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

A

-

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

-

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

-

17
Q

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

A

-

18
Q

explain the advantage of using the merge sort algorithm

A

-

19
Q

state what is mean by abstraction

A

-

20
Q

what is a brute force algorithm

A
  • 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
Q

how do you find the efficiency of a linear search

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

desbribe an algorithm for carrying out a linear search

A
  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
Q

describe an algorithm for carrying out bubble sort

A
  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
Q

what is a traversal method of sorting numbers

A

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

25
Q

what is a recursion method of sorting numbers

A

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

26
Q

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

A
  • 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
Q

what does a searching algorithm do

A

finds a specific item in a list

28
Q

describe an algorithm for carrying out binary search

A
  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
Q

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

A
  • 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
Q

name one disadvantage for binary search

A

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

31
Q

describe the differences between the bubble sort and merge sort algorithms

A

-

32
Q

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

A

-

33
Q

discuss the advantages of using arrays in algorithms

A

-

34
Q

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

A
  • helps to understand any errors in the algorithm

- helps to understand the processes and the possible outcomes of the future program

35
Q

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

A

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
Q

give an example of a logic error

A

if variable == 20:

variable + 2

37
Q

give an example of a syntax error

A
  • pint (“hello”)
38
Q

give an example of a runtime error

A
  • 0/2

Computing (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions