Brainscape's Knowledge GenomeTM

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


See full index

A level Comp Sci > Algorithms > Flashcards

Algorithms Flashcards

1
Q

ideal algorithm

A

will run quickly and take up as little space(memory) as possible.

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

Time complexity

A

How much time they need to solve a given problem

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

Space complexity

A

The amount of resources e.g. memory they require

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

Permutation

A

number of ways we can arrange a set of data - factorial e.g. 4! = 4x3x2x1

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

Constant

A

y = 3

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

Linear

A

y = 3x

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

Logarithmic (Big O + graph)

A

y = log(x)

O(logn)

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

Polynomial

A

y = x^2

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

Exponential graph

A

y = x^3

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

How to write Big O

A

Notation always assumes the worst case scenario,
1. remove all terms except the one with the largest factor
2. Remove any constants
e.g. 3n is expressed as O(n), this is a linear complexity that grows by ‘n’ number of times

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

Constant complexity

A

O(1)

Always executes in the same time regardless of the size of the data set - most efficient. Time is independent of input

e.g. Determining if a number is odd or even

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

Logarithmic complexity

A

O(log n)

Halves the data in each pass. Opposite to exponential and efficient with large data sets - efficient

e.g. Binary search

Linear Logarithmic -
Merge sort = O(n log n)

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

Linear complexity

A

O(n)

Performance is proportional to the size of the data set and declines as the data set grows. - medium efficiency

In the worst case scenario it must go through each item once

e.g. Linear search

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

Polynomial complexity

A

O(n^2)

Performance is proportional to the square of the size of the data set. - inefficient

A loop inside a loop

e.g. Bubble sort

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

Exponential complexity

A

O(2^n)

Doubles with each addition to the data set in each pass, opposite to logarithmic - very inefficient

Intractable

e.g. recursively calculating Fibonacci numbers

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

Constant Time

A

Time remains constant even when the number of output increases

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

Logarithmic Time

A

Time will grow as the size of the input increases

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

Linear Time

A

Time will be linear to the size of the input

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

Polynomial Time

A

Time will grow proportionally to the square of the size of the data set

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

Exponential Time

A

Time will be as the power of the number of inputs, grows very quick

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

Factorial Time O(n!)

A

Time will grow even quicker as data is input, very inefficient

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

Tractable problems

A

efficient, have a polynomial or less time solution e.g. O(1). O(n), O(log n), O(n^2)

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

Intractable problems

A

inefficient, any problems that can be theoretically solved but take longer than polynomial time e.g. O(n!), O(2^n)

24
Q

Heuristic algorithms

A

used to provide approximate but not exact solutions.

25
Q

Unsolvable problems

A

can never be solved algorithmically, an example is demonstrated by the Halting problem

26
Q

Graph Traversal

A

Is the process of visiting each vertex in a graph. You can use both depth-first and breadth first

27
Q

Depth First Graph Traversal

A

a branch is fully explored before backtracking. Uses a stack

28
Q

Breadth First Graph Traversal

A

a layer is fully explored before venturing on to the next node. Uses a queue

29
Q

Pre-Order Tree Traversal

A

Drawing a dot on the left of the nodes, used for prefix notation and copying a tree

30
Q

Post-Order Tree Traversal

A

Drawing a dot on the right of the nodes, used for reverse polish notation

31
Q

In Order Tree Traversal

A

Drawing a dot underneath the nodes and follow around the nodes – Used for binary tree search and outputting values in ascending order

32
Q

How to represent a tree data structure?

A
  1. An array that contains values at the nodes
  2. An array that points to the location of the left child of the node in the values array
  3. An array that points to the location of the right child of the node in the values array
33
Q

Reverse Polish Notation

A

Humans prefer in-fix order notation, this is where operand is either side of the opcode. However RPN creates a postfix equivalent

e.g. infix 3 + 5
Postfix/RPN 35+

Both give the answer 8

34
Q

Evaluate the postfix equation 963/+ (Use a stack)

A

963/+
63/= 6/3 = 2
92+

= 11

Operand is pushed onto the stack, whilst opcode causes two items to be popped off the stack with the result of the operation pushed back onto the stack.

35
Q

RPN uses/benefits

A

RPN can be executed on a stack, as a result, RPN is ideal for interpreters which are based on a stack e.g. Bytecode and PostScript
RPN is non ambiguous and therefore easier for computers to read

36
Q

Linear Search Operations?

A
  1. Compare every search item against every item in the list one-by-one.
  2. Starts at the beginning and keeps going until the search item is found
  3. Returns the position of where it is found
  4. If the item is not in the list, it will return a suitable message indicating it is not in the list, should not error
37
Q

Big O for time complexity for Linear Search?

A

Big O = O(N)
Linear search is slow when compared with other search algorithms

38
Q

What can Linear Search be conducted on?

A

any unordered list

39
Q

How can you determine the maxiumum number of searches a binary list performs?

A

Divide by 2 until you reach 1 or lower, the number of times divded is the max number of searches#
(or can use log)

40
Q

What can Binary Search be conducted on?

A

any ordered list

41
Q

Binary Search Operations?

A
  1. works by looking at the midpoint of the list and determining if the target is higher or lower than the midpoint
  2. If when calculating the midpoint it is decimal, the decimal is removed e.g. 2.6 → 2
  3. The list is then halved
42
Q

Big O time complexity for Binary Search?

A

O(logN)

43
Q

Linear Search Advantages and Disadvantages

A

Advantages;
-Simple and easy to implement
-No sorting required
-Good for short lists

Disadvantages;
-Slow because it searches through the whole list
-Inefficient for long lists

44
Q

Binary Search Advantages and Disadvantages?

A

Advantages;
-Much quicker, halving the search zone

Disadvantages;
-Items of the list need to be placed in order

45
Q

What kind of algorithm is bubble sort?

A

Sorting

46
Q

What is the purpose of a Bubble Sort?

A

The purpose of bubble sort is to order an unordered list, this can be alphabetically or by number.

47
Q

Bubble Sort: Order of Operations

A
  1. Bubble sort steps through a list and compares pairs of adjacent numbers
  2. The numbers are swapped if they are in the wrong order. e.g. ascending or descending.
  3. The algorithm repeatedly passes through the list until no more swaps are needed
  4. Going through the list once is considered 1 pass
48
Q

Bubble sort advantages and disadvantages

A

Advantages : Very simple to code and robust
Disadvantages : Slow, inefficient, especially for long lists

49
Q

What is the maximum number of comparisons a bubble sort can make?

A

for n items n(n−1)/2

50
Q

What is a merge sort?

A

Merge sort is a recursive function that calls itself. It is a divide and conquer algorithm

51
Q

Merge Sort: Order of Operations

A
  1. Divides unsorted lists into sublists, until there is one item in each list
  2. it then combines pairs of sublists into ordered lists,
  3. Continues until only one ordered list remains
52
Q

Merge Sort vs Bubble Sort

A

Merge sort;
- Much faster than bubble sort especially when the number of elements is large O(n log n)
- More Complex to code and understand

Bubble sort;
- Much slower than merge sort especially when the number of elements is large O(n^2)
- Easy to code and understand

53
Q

what is Dijkstra

A

Dijkstra’s shortest path optimisation algorithm finds the shortest path between nodes/vertices in a graph

54
Q

Dijkstra: Order of operations

A
  1. Selects the unvisited node with the shortest path
  2. Calculates the distance to each unvisited neighbour
  3. Updates the distance of each unvisited neighbour if smaller
  4. Once all neighbours have been visited mark node as visited
55
Q

Uses for Dijkstra’s algorithm?

A

Applications of DA is heavily used in computer systems that need to calculate shortest paths:
- satellite navigation systems to display shortest or fastest route
- Routers in networks to find shortest path when routing packets within networks

A level Comp Sci (13 decks)

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