Brainscape's Knowledge GenomeTM

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


See full index

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
Q

Worst case time complexity of Linear Search

A

O(n)
Linear Complexity

26
Q

Best case time complexity of Binary Search

A

0(1)
Constant Time Complexity

27
Q

Worst case time complexity of Binary Search

A

O(log n)
logmarithmic complexity

28
Q

Are stacks FIFO or FILO?

A

FILO

29
Q

Which function adds an item to a stack?

A

Push

30
Q

Which function removes an element from a stack?

A

Pop

31
Q

What is the significance of the back pointer in the
array representation of a queue?

A

Holds the location of the next available space in the queue

32
Q

Which function returns the item at the front of a
queue without removing it?

A

Peek

33
Q

What is the purpose of the front pointer in the array
representation of a queue?

A

Points to the space containing the first item in the queue

34
Q

What value is the top pointer initialised to in the array
representation of a stack?

A

-1

35
Q

Give pseudocode for the two functions which add new elements to stacks and queues

A

Stacks
push(element):
top += 1
A[top] = element

Queues
enqueue(element):
A[back] = element
back += 1

36
Q

Which function returns the item at the top of a stack
without removing it?

A

Peek

37
Q

Which of our sorting algorithms is the most efficient?

A

Merge sort

38
Q

What is Dijkstra’s algorithm?

A

A shortest path algorithm used to find the shortest distance between two nodes in a network.

39
Q

How is Dijkstra’s algorithm implemented?

A

You use a priority queue which has the shortest lengths at the front of the queue.

40
Q

What is the A* algorithm?

A

The A* algorithm is a general path-finding algorithm which has two cost functions: actual cost and an approximate cost.

41
Q

How does the A* algorithm differ from
Dijkstra’s algorithm?

A

A* algorithm has two cost functions: the actual cost and the approximate cost

42
Q

Why are heuristics used in the A* algorithm?

A

To calculate an approximate cost from node x to the final node. This aims to make the shortest path finding process more efficient.

43
Q

What data structure can be used to implement
Dijkstra’s algorithm?

A

Priority queue

44
Q

State a disadvantage of using the A* algorithm

A

The speed of the algorithm is constrained by the accuracy of the heuristic

45
Q

How does the Breath-first algorithm work?

A

Works by visiting all the nodes on a row, before moving to the next row.

46
Q

In what data structure is a breadth-first search algorithm used?

A

A queue (FIFO)

47
Q

In this tree diagram: https://gyazo.com/349ec19d07959bf5ae8d1b2bc42fd5ed. Describe how this tree would be searched using a breath-first search algorithm.

A
  1. A
  2. B,C
  3. D,E,F,G
  4. H,I
48
Q

How does the Depth-first algorithm work?

A

works by visiting all the nodes on the same verticle, before horitizontal.

49
Q

In what data structure is a Depth-first algorithm used?

A

Stacks (LIFO)

50
Q

In this tree diagram: https://gyazo.com/01975111eff5d629c81b74fec90f7c58. Describe how this tree would be searched using a depth-first search algorithm.

A
  1. A
    2.B
  2. C,D,E
  3. F
    5.G,H,I
51
Q

How does bubble sort work?

A

Compares pairs of data and then goes through list again and compares pairs again.

52
Q

Use bubble sort on:
2, 8, 5, 3, 9, 4, 1

A

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
Q

how is Merge Sort done?

A

Recursively, using divide and conquer which is when you break a problem into a smaller problem in order to solve it.

54
Q

How does merge sort work?

A

Breaks down elements into individuals then doubles them up while comparing and changing until list is sorted

55
Q

Use Merge Sort on:
2, 8, 5, 3, 9, 4, 1, 7

A

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
Q

How to remove a node from a linked list

A
  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.
© 2024 Bold Learning Solutions. Terms and Conditions