Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Computer Science > Algorithms > Flashcards

Algorithms Flashcards

(67 cards)

Start Studying
1
Q

Abstraction

A

Ignore unnecessary information and focus on important facts to reduce complexity

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

Decomposition

A

Break a problem down into smaller tasks to make it easier to solve

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

Reason to use abstraction

A

Simplifies problems
Less complex
Straightforward to understand problem and create solutions
Focus on fundamental

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

Reasons to use decomposition

A

Each individual problem can be separately tested+solved
Enables different people to work on different part of the bigger problem, which can be recombined to produce a full solution
Easier for error detection and debugging

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

Algorithmic thinking

A

Final stage, in which logical steps are done to solve the problem
Identify problem components
Logical way to get the solution of a problem

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

Order of algorithmic thinking

A

Problem is broken down using decomposition into smaller problems
Then the required data and relevant data is considered using abstraction

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

What is an algorithm?

A

A precise set of instructions presented in a logical sequence and when executed will solve a problem

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

What is automation?

A

Taking a model and implementing a solution

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

What is debugging?

A

Detecting and resolving problems in a program

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

What is logical reasoning?

A

Applying rules to solve an issue/problem

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

Flowchart- start/stop shape

A

Rounded cornered rectangle

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

Flowchart- input/output shape

A

Parallelogram

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

Flowchart- process/instructions/calculations shape

A

Rectangle

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

Flowchart- decisions (if/else) shape

A

Diamond

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

Flowchart- subprogram/function shape

A

Rectangle with two lines going down at each end

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

What should be in every flowchart?

A

Arrow connecting boxes and showing direction of program

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

What is a structure diagram?

A

Display organisation of a problem in visual format after decomposing the problem
They show subsections to a problem and their link to other subsections

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

What do structured diagrams show?

A

Smaller tasks of a larger problem

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

Advantages of structured diagrams

A

Easier to code (code solutions for simpler problems)
Each programmer can work on each module individually/independently
Easier to test and debug (done individually)
Individual modules can be updated and fixed without affecting the rest of the program
Reuse sub programs in other programs (in future)

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

Why keep program easy to maintain?

A

Easy for others to understand what the code does.
Able to change parts of source code without risk of causing problems elsewhere

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

How to improve maintainability of code?

A

Comments can explain what key features do
Indentation to separate different statements in your program
Variables, subprograms(functions), parameters named to what they do (standard naming conventions)
Using subprograms (functions)

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

What do comments do?

A

Clear comments enable programmer to understand purpose of each line of code
Important to use when working in a team

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

What are indentations used for in maintainability?

A

Improves readability and clearly shows each block of code
Separates different statements in a program

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

What is the importance of standard naming conventions?

A

Appropriate variable/parameter/sub programs names, ensure the purpose of said thing is understood and is easier to keep track of

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Why should you use sub programs?
Allows reuse of code and is easier to test( and see how different parts of code work separately) Called modularisation.
26
What are trace tables?
Keep track of values which certain variable have as the program is run Manually track values
27
Why would a trace table be used?
Manually track for logic errors and to see why a program isn’t working as intended To see what a piece of code is doing
28
How to do binary search?
Find middle value [ (first value+last value)DIV 2] If mid point in even range, its middle right value Compare to value being searched for If it is the same, you’ve found it. If not, if value being searched for comes before this value then remove the 2nd half of the list (and vice versa) Repeat with the smaller list until value is found
29
Defensive design
Ensure programs function properly and don’t produce errors
30
What is pattern recognition?
Ability to recognise common themes/patterns within problems Sometimes referred to as generalisation
31
What to do when using pattern recognition?
Investigate any similarities or characteristics within the problem that are similar to each other Spot patterns within problem
32
Why is pattern recognition important?
Identifies similarities and patterns allows to create solutions which can be applied multiple times. Problems can be solved efficiently (same solution used multiple times)
33
What is an exception?
Exceptional or unexpected event that occurs when program is running.
34
What is exceptional handling?
Ways that a program handles/deals with unexpected circumstances. Ensures it doesn’t crash Can code an exception handler (it’ll deal with it in the best way possible and not crash)
35
What are the characteristics of a binary search?
(Standard version) iterates Works with lists that are in ascending order Efficient with long lists (and short ones)
36
What value would be searched for in the worst case scenario? Binary search
Very first/very last value
37
What are the maximum comparisons (in the worst case scenario) when searching through 1000 values? Binary search
10
38
What are the maximum comparisons (in the worst case scenario) when searching through 2000 values? Binary search
11
39
What are the maximum comparisons (in the worst case scenario) when searching through 10 values? Binary search
4
40
What are the maximum comparisons (in the worst case scenario) when searching through 100 values? Binary search
7
41
What are the maximum comparisons (in the worst case scenario) when searching through 10,000 values? Binary search
14
42
What are the maximum comparisons (in the worst case scenario) when searching through 100,000 values? Binary search
17
43
What are the maximum comparisons (in the worst case scenario) when searching through 1,000,000 values? Binary search
20
44
How to do linear search?
Look at first item If it is it, stop Else, continue to next item Repeat (2 and 3) until item founded
45
What are the conditions for binary search?
Ordered list
46
What are the conditions for linear search?
Unordered list
47
On what lists would a linear search be used for?
Short, simple lists
48
What are the characteristics of a linear search?
Iterates Inefficient (item could possibly not be in list) Simple compared to binary search
49
How to do bubble sort?
Look at first two items (1,2) (comparison) If in correct order, move on Else, swap them Move onto next pair (2,3) Repeat (step 2 and step 3) until the end (one pass has occurred) Last item in correct place(don’t involve it in next pass)
50
In programming, why would ‘temp’ be used?
To temporarily store data within a variable as the data in the variable may be written over.
51
What are the benefits of bubble sort?
Simple algorithm (easily implemented) Efficient way to check if list is already sorted (n items, do n-1 comparisons) Doesn’t use much memory
52
Why doesn’t bubble sort use much memory?
All sorting is done using original list
53
What are the disadvantages of bubble sort?
Inefficient, doesn’t cope with long lists One of the slowest sorting algorithms
54
How many comparisons will occur in the worst case scenario? Bubble sort
[ n ( n - 1 ) ] DIV 2
55
What would be the worst case scenario for bubble sort?
All items are in descending order
56
How to do merge sort?
Repeatedly split the original list into sub-lists (until all lists contain one item) Merge pairs of sub-lists (while comparing the items, so the lowest value of both lists become first) Repeat until all lists have merged
57
What would occur if the merge sort had an odd value?
When first splitting, one sub-list would have more than another
58
What must you remember during merge sort?
Put squares around each list and sub-lists
59
What are the advantages of merge sort?
More efficient and less time consuming that insertion and bubble sort (especially on long lists) Consistent running time (no matter how unordered the list is)
60
What are the disadvantages of merge sort?
Slower with small (mainly sorted) lists Even if list is mainly sorted, it’ll still split and merge them Uses more memory
61
Why does merge sort use more memory?
To create separate lists.
62
How to do insertion sort?
Sorted sub-list (containing one value) Unsorted sub-list (containing all other values) Look at next value (in unsorted sub-list) Compare to all values in sorted sub-list (comparison) and insert in the right position/place (a pass) Repeat until all values in unsorted sub-list are sorted
63
What are the advantages to insertion sort?
Intuitive way of sorting (easy to code) Efficient with small lists (use a merge/insertion hybrid) Doesn’t require much memory Quick when adding items to already ordered list and checking if a list is sorted
64
Why doesn’t insertion sort require additional memory?
All sorting happens on the original list
65
How many comparisons are done in the worst case scenario? Insertion sort
(In descending order) [ n ( n - 1 ) ] DIV 2 comparisons
66
How many comparisons are done in the best case scenario? Insertion sort
(List is already ordered) n - 1 comparisons
67
How is insertion quicker than bubble sort?
Few comparisons per pass

Computer Science (4 decks)

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