Brainscape's Knowledge GenomeTM

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


See full index

Computer Science > 2.3 Algorithms > Flashcards

2.3 Algorithms Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What are the maximum number of passes in a bubble sort?

A

n^2

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

What are the maximum number of passes in an insertion sort?

A

n^2

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

What are the maximum number of passes in a linear search?

A

n

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

What are the maximum number of passes in a binary search?

A

log(n)

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

What is the method of merge sorts?

A

List is split in half every time until there is only 1 item in a sub list

Individual sub lists are then merged together into order until list is complete again

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

What is a partition in a quick sort algorithm?

A

An unsorted section of the list

To sort items, list is repeatedly partitioned

Divide and conquer approach means when each partition only contains one items, list is sorted

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

What is a pivot value?

A

Value chosen to partition the list which is being sorted

New value chosen each time list is partitioned

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

What are the markers of a quick sort?

A

To keep track of items as they are in order, uses two marks

Lowmark and highmark

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

What is the method of a quick sort?

A
  1. choose value as pivot (usually 1st item in list)
  2. take two variables to point left and right of list excluding pivot
  3. left points to low index and right points to high
  4. while value at left is less than pivot, move right
  5. while value at right is greater than pivot, move left
  6. if both step 4 and 5 don’t match, swap left and right values
  7. if left greater or equal to right, point where they met is new pivot
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is Dijkstra’s algorithm?

A

Finds the shortest path between a start node and every other node in a weighted graph

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

What are the uses of Dijkstra’s algorithm?

A

Scheduling aeroplanes and staff so air crews always have suitable rest time

Finding best move in chess fame

Timetabling classes in a school

Finding shortest path between two points (circuit boards, route planning GPS, communication networks)

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

What could the weights of a graph represent?

A

Distances

Time

Cost of travel

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

How is Dijkstra’s algorithm implemented?

A

Similar to breadth-first search

Could use different data structures (queue, array)

Starts by assigning temporary distance value to each node

Temporary distance is 0 at start node and ∞ at every other node

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

How is the distance to a node calculated?

A

Distanced from connected node + distance from start to connected node

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

How is the next current node selected?

A

Unvisited node with shortest distance from the start

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

What are the column names for the table in Dijkstra’s algorithm?

A

Node

Visited

Shortest distance from start

Previous node

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

What is a heuristic approach?

A

One which tries to find a solution which may not be perfect but which is adequate for its purpose

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

What is A* algorithm?

A

Makes use of heuristics as each node has a heuristic value associated to it

Makes an ESTIMATE of the distance from each node to the goal node, which may not be perfect but can be used to determine most probable route and therefore don’t need to check all nodes

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

What can a GPS app use as a heuristic value?

A

Expected distance from end

Level of congestion

Speed restrictions

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

What are the functions of an A* algorithm?

A

g(x) = distance from start (weight of node + distance to node)

h(x) = the approximate cost from node(x) to goal node

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

How does the A* algorithm calculate the cost of each node?

A

f(x) = g(x) + h(x)

h(x) should NEVER be greater than g(x)

22
Q

What are the column names for the table in an A* algorithm?

A

Node

Visited

Shortest distance from start

Heuristic (h)

f = g + h

Previous node visited

23
Q

How are algorithms compared?

A

Using time or space complexity

To produce an algorithm that can run in the shortest amount of time and take up a minimal amount of memory resources

24
Q

What is time complexity?

A

The amount of time they take to solve a problem in relation to the size of the input

How many lines need to be executed when running the algorithm

Need to be able to select the MOST SIGNIFICANT PART OF THE ALGORITHM

25
Q

What is memory complexity?

A

The amount of memory resources an algorithm requires, in relation to the size of the input

26
Q

What is Big O notation?

A

Way of expressing time and space complexity of an algorithm and therefore being able to compare algorithms

27
Q

How should time and space complexity be considered?

A

Default consider WORST-CASE SCENARIO

If worst-case is same, pick either AVERAGE-CASE or BEST-CASE

28
Q

What are the different types of complexity?

A

Constant

Logarithmic

Linear

Linearithmetic

Polynomial

Exponential

29
Q

What is constant complexity?

A

An algorithm that always executes in the same time regardless of the size of the data set

An algorithm that uses the same amount of memory regardless of the size of the data set

30
Q

What is the efficiency of constant complexity?

A

Efficient for any data set

31
Q

What is the Big O notation for constant complexity?

A

O(1)

32
Q

What algorithms have a constant complexity?

A

Extracting data from any element from an array

Hash tables

33
Q

What is logarithmic complexity?

A

An algorithm that halves the data set in each pass

Because the algorithm halves each time from the large data set, it starts off with a really large search time then flattens out over time

Opposite to exponential

34
Q

What is the efficiency of logarithmic complexity?

A

Efficient for large data sets

35
Q

What is the Big O notation of a logarithmic complexity?

A

O(logn)

36
Q

What algorithms have a logarithmic complexity?

A

Binary search

37
Q

What is linear complexity?

A

An algorithm whose performance will grow in proportion to the size of the data set

An algorithm whose performances declines as the data set grows

38
Q

What is the efficiency of linear complexity?

A

Reduces efficiency with increasingly large data sets

39
Q

What is the Big O notation for linear complexity?

A

O(n)

40
Q

What algorithms have linear complexity?

A

A loop iterating through a single dimension array

Linear search

41
Q

What is linearithmetic complexity?

A

Algorithms that divide a data set but can be solved using concurrency on independent divided lists

42
Q

What is the efficiency of linearithmetic complexity?

A

Not as efficient as logarithmic algorithms

43
Q

What is the Big O notation of linearithmetic complexity?

A

O(nlogn)

44
Q

What algorithms have linearithmetic complexity?

A

Merge sort

Quick sort

45
Q

What is polynomial complexity?

A

An algorithm whose performance is proportional to the square of the size of the data set

Deeper nested iteration result in O(N^3), O(N^4) etc depending on the number of dimensions

Used for algorithms that have nested loops (number of nested loops is x)

46
Q

What is the efficiency of polynomial complexity?

A

Significantly reduces efficiency with increasingly large data sets

47
Q

What is the Big O notation of polynomial complexity?

A

O(n^x)

48
Q

What algorithms have polynomial complexity?

A

A nested loop iterating through a two dimension array

Bubble sort

49
Q

What is exponential complexity?

A

An algorithm that doubles with each addition to the data set in each pass

Execution time can quickly become very large

Opposite to logarithmic

50
Q

What is the efficiency of exponential complexity?

A

Inefficient

51
Q

What is the Big O notation for exponential complexity?

A

O(2^n) - for a problem that doubles as the size of the data set increases

52
Q

What algorithms have exponential complexity?

A

Recursive functions with two calls

Fibonacci number calculation with recursion

Brute force of a password

Computer Science (8 decks)

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