Brainscape's Knowledge GenomeTM

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


See full index

TM111: Block 2, Creating solutions > Part 6, Algorithms > Flashcards

Part 6, Algorithms Flashcards

1
Q

finish the sentence

a well written algorithm can be

A

implemented into many different programming languages

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

give a definition that would describe an algorithm for a program

A

a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.

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

what is this sentence a definition of

a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.

A

this is the definition of an algorithm for a program

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

what is meant by unambiguous in the definition for a programs algorithm

a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.

A

the term unambiguous means that no part of the algorithm is open to interpretation

the algorithm is therefore written clearly and precise for the benefit of the computer and anyone wanting to reuse the algorithm

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

what is meant by self contained in the definition for a programs algorithm

a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.

A

the term self contained means that the algorithm contains all information it needs

therefore when using the algorithm it will require no external sources of information or extra work put into it

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

what is meant by step-by-step instructions in the definition for a programs algorithm

a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.

A

step-by-step instructions means that the algorithm is written in steps which eventually lead to the desired outcome

this is much like the steps written in a recipe

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

an algorithm needs refinement/decomposition

what does this mean

A

this means the algorithm is open to more than one interpretation

it should be refined or decomposed until all ambiguities have been resolved

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

an algorithm is open to more than one interpretation what two terms describe the process it must go through to rid it of the open interpretation

A

refinement

decomposition

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

what method might you use to refine an algorithm that is open to more than one interpretation

A

break the step down into several smaller clearer steps

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

how can you tell when an algorithm is refined fully

A

the algorithm will be clear and precise to the author and any audience that uses it

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

what four fundamental features do all algorithms share

A
  1. inputs and outputs
  2. sequence of instructions
  3. repetition of instructions
  4. selection of instructions
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

what shares these four features

  1. inputs and outputs
  2. sequence of instructions
  3. repetition of instructions
  4. selection of instructions
A

algorithms

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

an algorithm will follow a sequence of instructions unless
1.
2.

A
  1. there is repetition in which case the algorithm repeats a set of instructions until the loop is broken
  2. there is selection. in which case the sequence of instructions will branch to different sequence of instructions and outcomes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

name four input sources an algorithm might get its data from

A
  1. the user
  2. a constant unchangeable value written in the algorithm
  3. data from the current environment (current time, current mouse position)
  4. lists
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

what is a case instruction or a switch statement

A

this can be used in contrast to selection.

instead an input variable is assessed then if the variable exists as a case or switch then it has its block of code ran

switch (variable or an integer expression)
{
     case constant:
     //C Statements
     ;
     case constant:
     //C Statements
     ;
     default:
     //C Statements
     ;
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

this can be used in contrast to selection.

instead an input variable is assessed then if the variable exists as a case or switch then it has its block of code ran

switch (variable or an integer expression)
{
     case constant:
     //C Statements
     ;
     case constant:
     //C Statements
     ;
     default:
     //C Statements
     ;
}
A

case instruction/switch statement

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

what two ways can you judge if an algorithm is good or not

A
  1. readability - are its steps clearly laid out and self explanatory
  2. efficiency - is it written in its most efficient form. that is can it be re written to perform the same outcome quicker and with less effort
18
Q

how can you tell if an algorithm has good readability

A

the steps will be clear and precise to all. this includes the author and any audience that uses it

19
Q

name two ways you can increase the efficiency of an algorithm

A
  1. reduce the number of steps while still maintaining the desired outcome
  2. reduce the number of calculations while still maintaining the desired outcome
20
Q

describe the three steps of the swapping algorithm

A
  1. set temp to item 2
  2. set item 2 to item 1
  3. set item 1 to temp
21
Q

what does this algorithm do

  1. set temp to item 2
  2. set item 2 to item 1
  3. set item 1 to temp
A

swaps two items

22
Q

describe a sorting algorithm

A

a sorting algorithm takes a list of unsorted items and then sorts the items by a given rule

23
Q

takes a list of unsorted items and then sorts the items by a given rule

A

sorting algorithm

24
Q

what rules might be applied to sort items in a list

1 - 4

A
  1. sort numbers in ascending/descending order
  2. sort words alphabetically in ascending/descending order
  3. sort by length of item in ascending/descending order
  4. sort by price in ascending/descending order
25
Q

what are the three steps for the selection sort algorithm

A

repeat until (only 1 item of unsorted data remains)

  • ——- find the lowest item in the unsorted data
  • ——- swap the lowest item with the first item in the ———— unsorted data
26
Q

what algorithm is this

repeat until (only 1 item of unsorted data remains)

  • ——- find the lowest item in the unsorted data
  • ——- swap the lowest item with the first item in the ———— unsorted data
A

selection sort algorithm

27
Q

name two features of the selection sort algorithm

A
  1. always makes the same number of comparisons regardless of lists initial state sorted or unsorted
  2. has a non linear line on a graph. as the number of items to sort increases the number of comparisons grows faster
28
Q
  1. always makes the same number of comparisons regardless of lists initial state sorted or unsorted
  2. has a non linear line on a graph. as the number of items to sort increases the number of comparisons grows faster
A

features of the

selection sort algorithm

29
Q

describe a

not in place sort

A

this uses two lists two sort data

unsorted list - holds the initial unsorted data. is either emptied while being sorted or its state is left unchanged

sorted list - is initially empty but is filled with items from the unsorted list as the items are sorted

30
Q

this uses two lists two sort data

unsorted list - holds the initial unsorted data. is either emptied while being sorted or its state is left unchanged

sorted list - is initially empty but is filled with items from the unsorted list as the items are sorted

A

not in place sort

31
Q

describe an in place sort

A

uses only one list and upon sorting is abstracted into two lists. the unsorted items and the sorted items

pass 1 - the entire list is unsorted (1 list)
pass 2 - the list has 1 sorted item (2 lists)
pass 3 - the list has 2 sorted items (2 lists)
repeat until there is only one unsorted item (essentially 1 sorted list)

32
Q

uses only one list and upon sorting is abstracted into two lists. the unsorted items and the sorted items

pass 1 - the entire list is unsorted (1 list)
pass 2 - the list has 1 sorted item (2 lists)
pass 3 - the list has 2 sorted items (2 lists)
repeat until there is only one unsorted item (essentially 1 sorted list)

A

in place sort

33
Q

which of these two methods is more likely to be used

  1. in place sort
  2. not in place sort
A

an in place sort is more likely to be used as it is more elegant and efficient as items are contained within one list no extra memory is required

34
Q

describe the bubble sort algorithm/sinking sort algorithm

A

this sorts items in a way that the sorted items will bubble or sink to either end of the list

35
Q

the bubble sort algorithm contains a swapping pass describe what it does

A

looks at the first item in the list and compares it to the adjacent item if they are in the wrong order they are swapped. it then moves to the next item and repeats until there are no more adjacent items

the swapping pass sorts 1 item

36
Q

what are the four steps in the swapping pass

A

starting at the beginning of the list
repeat for (each pair of adjacent items)
——– if items are in the wrong order then
—————- swap them

37
Q

what is this

starting at the beginning of the list
repeat for (each pair of adjacent items)
——– if items are in the wrong order then
—————- swap them

A

bubble sort algorithms swapping pass

38
Q

what are the 8 steps of the bubble sort algorithm written in its most efficient form

A

set flag to true
repeat until (flag is false)
—- set flag to false
—- starting at the beginning of the list
—- repeat for (each pair of adjacent items in the ————– unsorted portion)
——– if items are in wrong order then
———— swap them
———— set flag to true

39
Q

what algorithm is this

set flag to true
repeat until (flag is false)
—- set flag to false
—- starting at the beginning of the list
—- repeat for (each pair of adjacent items in the ————– unsorted portion)
——– if items are in wrong order then
———— swap them
———— set flag to true

A

bubble sort algorithm

40
Q

name two features of the bubble sort algorithm

A
  1. can stop sorting a sorted list after 1 iteration because of its use of a flag
  2. shares the same non linear line on a graph of selection sort when reverse sorting
41
Q
  1. can stop sorting a sorted list after 1 iteration because of its use of a flag
  2. shares the same non linear line on a graph of selection sort when reverse sorting
A

features of the bubble sort algorithm

42
Q

name 3 sorting algorithms

A
  1. selection sort
  2. bubble sort
  3. merge sort

TM111: Block 2, Creating solutions (5 decks)

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