Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

CS P2 > Algorithms > Flashcards

Algorithms Flashcards

1
Q

What two pieces of information allow you to analyse
an algorithm?

A

● Time Complexity
● Space Complexity

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

What is meant by the time complexity of an
algorithm?

A

The amount of time required to solve a particular problem

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

How do you measure of the time complexity?

A

Big-O notation

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

What does the Big-O notation show?

A

The effectiveness of an algorithm

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

What is the Big-O notation good for?

A

It allows you to predict the amount of time taken to solve an algorithm given the number of items stored

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

What does a linear time complexity mean?

A

The amount of time taken to complete an algorithm is independent from the number of elements inputted.

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

What does a constant time complexity mean?

A

The amount of time taken to complete an algorithm is independent to the number of inputted elements

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

What does a polynomial time complexity mean?

A

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

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

What does an exponential time complexity mean?

A

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

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

What does a logarithmic time complexity mean?

A

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

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

What is a logarithm?

A

How many times a certain number (base) is multiplied together to reach another number.

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

What is space complexity?

A

The space complexity is the amount of storage space an algorithm takes up

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

What is an algorithm?

A

An algorithm is a series of steps that complete a task

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

How do you reduce the space
complexity?

A

Try to complete all of the operations on the same data set

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

How do you reduce the time complexity of an
algorithm?

A

You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer

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

best case time complexity of Quicksort

A

O(n log(n))
log-linear complexity

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

worst case time complexity of Quicksort

A

O(n^2)
Quadratic complexity

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

best case time complexity of Mergesort

A

O(n log(n))
log-linear complexity

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

worst case time complexity of Mergesort

A

O(n log(n))
log-linear complexity

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

best case time complexity of Bubble Sort

A

O(n)
Linear Complexity

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

worst case time complexity of Bubble Sort

A

O(n^2)
Quadratic complexity

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

best case time complexity of Insertion Sort

A

O(n)
Linear Complexity

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

worst case time complexity of Insertion Sort

A

O(n^2)
Quadratic complexity

24
Q

best case time complexity of Linear Search

A

0(1)
Constant Time Complexity

25
Worst case time complexity of Linear Search
O(n) Linear Complexity
26
Best case time complexity of Binary Search
0(1) Constant Time Complexity
27
Worst case time complexity of Binary Search
O(log n) logmarithmic complexity
28
Are stacks FIFO or FILO?
FILO
29
Which function adds an item to a stack?
Push
30
Which function removes an element from a stack?
Pop
31
What is the significance of the back pointer in the array representation of a queue?
Holds the location of the next available space in the queue
32
Which function returns the item at the front of a queue without removing it?
Peek
33
What is the purpose of the front pointer in the array representation of a queue?
Points to the space containing the first item in the queue
34
What value is the top pointer initialised to in the array representation of a stack?
-1
35
Give pseudocode for the two functions which add new elements to stacks and queues
Stacks push(element): top += 1 A[top] = element Queues enqueue(element): A[back] = element back += 1
36
Which function returns the item at the top of a stack without removing it?
Peek
37
Which of our sorting algorithms is the most efficient?
Merge sort
38
What is Dijkstra's algorithm?
A shortest path algorithm used to find the shortest distance between two nodes in a network.
39
How is Dijkstra's algorithm implemented?
You use a priority queue which has the shortest lengths at the front of the queue.
40
What is the A* algorithm?
The A* algorithm is a general path-finding algorithm which has two cost functions: actual cost and an approximate cost.
41
How does the A* algorithm differ from Dijkstra’s algorithm?
A* algorithm has two cost functions: the actual cost and the approximate cost
42
Why are heuristics used in the A* algorithm?
To calculate an approximate cost from node x to the final node. This aims to make the shortest path finding process more efficient.
43
What data structure can be used to implement Dijkstra’s algorithm?
Priority queue
44
State a disadvantage of using the A* algorithm
The speed of the algorithm is constrained by the accuracy of the heuristic
45
How does the Breath-first algorithm work?
Works by visiting all the nodes on a row, before moving to the next row.
46
In what data structure is a breadth-first search algorithm used?
A queue (FIFO)
47
In this tree diagram: https://gyazo.com/349ec19d07959bf5ae8d1b2bc42fd5ed. Describe how this tree would be searched using a breath-first search algorithm.
1. A 2. B,C 3. D,E,F,G 4. H,I
48
How does the Depth-first algorithm work?
works by visiting all the nodes on the same verticle, before horitizontal.
49
In what data structure is a Depth-first algorithm used?
Stacks (LIFO)
50
In this tree diagram: https://gyazo.com/01975111eff5d629c81b74fec90f7c58. Describe how this tree would be searched using a depth-first search algorithm.
1. A 2.B 3. C,D,E 4. F 5.G,H,I
51
How does bubble sort work?
Compares pairs of data and then goes through list again and compares pairs again.
52
Use bubble sort on: 2, 8, 5, 3, 9, 4, 1
2, 8, 5,3 ,9, 4, 1 2>8 8>5 = swap 2,5,8,3,9,4,1 8>3 = swap 2,5,3,8,9,4,1 8<9 9>4 = swap 2,5,3,8,4,9,1 9>1 2,5,3,8,4,1,9 KEEPS GOING
53
how is Merge Sort done?
Recursively, using divide and conquer which is when you break a problem into a smaller problem in order to solve it.
54
How does merge sort work?
Breaks down elements into individuals then doubles them up while comparing and changing until list is sorted
55
Use Merge Sort on: 2, 8, 5, 3, 9, 4, 1, 7
Divide the array until elements are individual elements. 2 8 3 5 4 9 1 7 2,8 3,5 4,9 1,7 2,3,5,8 1,4,7,9 1,2,3,4,5,7,8,9
56
How to remove a node from a linked list
1. Traverse through list to find data. 2. Find the previous and next node of the data. 3. Switch the previous nodes next pointer to datas next pointer 4. And switch datas next pointers, previous pointer to datas previous pointer 5. Set data to null

CS P2 (10 decks)

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