Algorithms Flashcards

1
Q

Big 0 - Sequential

A

O (n)
Loops n times

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

What is a Sequential Search?

A

Searches each element one by one until the search term is found, or the list is exhausted

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

What is a Selection Sort?

A

Starting from the first element, find the smallest number and swap it with the first item in the list.
Starting from the second element, find the smallest number and swap it with the second item in the list.
Repeat until you reach the final element.

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

Big O - Selection Sort

A

O (n2)
Loop inside a loop

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

What is a Binary Search?

A
  1. Compare k with the middle element of the list .
  2. If k is smaller than the middle element, disregard the second half of list. If k is greater than the middle element, disregard the second half of list.
    (Reduces the size of the list at each step by half)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Big O - Binary Search

A

O (log n)

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

What is a Merge Sort

A

Divide the list (or array) of numbers into two halves. Recursively solve the two halves. Merge the two halves into a single sorted list

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

Big O - Merge Sort

A

O (n log n)

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

What is Kruskals Algorithm?

A

A greedy algorithm designed to find a minimal spanning tree from a graph.

Continue picking the minimal cost “fringe” edges so long as no cycles are formed.

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

What is Prim’s algorithm?

A

A greedy algorithm designed to find a minimal spanning tree from a graph.

Start from a random vertex, pick the lowest cost fringe vertex.

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

What is the difference between algorithms and programs?

A

▶ An algorithm is free from grammatical rules and content.

▶ A computer program must obey very stringent syntax rules

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

What is Euclid’s algorithm?

A

Finds the greatest common divisor where
GCD (m, n) = GCD (n, m mod n).

Repeat this sum until the answer is 0.

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