Brainscape's Knowledge GenomeTM

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


See full index

A2 CS > 3 - Fundamentals of Algorithms > Flashcards

3 - Fundamentals of Algorithms Flashcards

1
Q

What is infix notation?

What is postfix notation (also known as Reverse Polish Notation)?

A

Infix notation is where the operator is between the operands eg. 5 + 3

Postfix notation is where the operators follow the operands eg. 5 3 +

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

How do you evaluate a postfix expression?

eg.4 2 3 5 1 - + * +

A

Work from left to right, applying each operator to the previous two operands.

eg.4 2 3 5 1 - + * + → 4 2 3 4 + * +
→ 4 2 7 * + → 4 14 + → 18

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

How do you convert from postfix to infix?

eg.3 4 + 2 *

A

Work from left to right, moving the operator between the previous two operands and encasing the operands in brackets. Make sure the operands remain in the same order.

eg.3 4 + 2 * → ( 3 + 4 ) 2 *
→ (( 3 + 4 ) * 2 ) → ( 3 + 4 ) * 2

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

How do you convert from infix to postfix?

eg.3 * ( 7 - 2 )

A

Add brackets to indicate which order to perform the operations. Move the operator to the end of each bracket, then remove the brackets. Make sure the operands are in the same order.

eg.3 * ( 7 - 2 ) → ( 3 * ( 7 2 ) - )
→ ( 3 ( 7 2 ) - ) * → 3 7 2 - *

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

Why is Reverse Polish Notation used?

A

• Because the order of evaluation of an expression is unambiguous, RPN expressions don’t need brackets.
• Expressions in RPN can be evaluated easily using a stack.
• There is no need for backtracking in evaluation as the operators appear in the order required for computation and can be evaluated from left to right.

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

Where is Reverse Polish Notation used?

A

RPN is used in interpreters based on a stack for example Postscript and bytecode.

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

What is meant by a recursive subroutine?

A

A subroutine that calls itself.

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

What are the advantages of Reverse Polish Notation over infix notation?

A

• Simpler for a computer to evaluate.
• Do not need brackets to show correct order of evaluation.
• Operators appear in the order required for computation.
• No need for order of precedence of operators.
• No need to backtrack when evaluating.

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

What is the complexity of merge sort?

A

O(nlogn)

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

What is the complexity of bubble sort?

Explain why this is.

A

O(n²)

In each pass through the list n items will be examine. There will be at most n passes through the list.

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

What is the complexity of binary search?

Explain why this is.

A

O(logn)

Each comparison halves the size of the list that has to be searched through.

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

What is the complexity of linear search?

Explain why this is.

A

O(n)

As the size of the list increases the time taken increases at the same rate.

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

What are the steps for Breadth-First Search?

A

• Mark all vertices as unvisited
• Choose a starting vertex
• Visit the starting vertex and mark it as visited
• Enqueue starting vertex in the queue
• Dequeue a vertex from the queue
• For each neighbouring vertex of this vertex, if it is univisited visit it, mark it as visited and enqueue it in the queue
• Repeat the processor of dequeuing vertices and visiting its neighbours until the queue is empty

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

What is a common use of Breadth-First Search?

A

To find the path containing the least number of nodes between two points in an unweighted graph.

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

What are the steps for Depth-First Search using a stack?

A

• Mark the starting vertex as discovered
• Push the starting node onto the stack
• Pop the top vertex off the stack and mark and visit it
• Push each of this vertex’s neighbours to the stack and mark them as discovered
• Repeat the processes of popping vertices and pushing their neighbours to the stack until the stack is empty

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

What is a common use of Depth-First Search?

A

It is commonly used to navigate a maze.

17
Q

What are the steps for linear search?

A

• Start with the beginning of the list
• Compare each item with the item you’re searching for
• Stop either when the item is found or the end of the list is reached

18
Q

What are the steps for binary search?

A

• For a sorted list
• Set the front pointer to 0 and the rear pointer to the index of the last item in the list
• Compare the item in the middle of the two pointers with the item you’re looking for
• If the items are the same, the item is in the list
• If the middle item is less than the item to search for, change the rear pointer to the middle - 1
• If the middle item is greater than the item to search for, change the front pointer to the middle + 1
• Repeat the processes of comparing the middle item until either the item is found or the front pointer is greater than the rear pointer

19
Q

What are the steps for binary tree search?

A

• Start at the root
• Compare the item at the root to the value you’re searching for
• If it is the same, the item has been found
• If the root is higher, check the left child
• If the root is lower, check the right child
• Keep comparing the value to different nodes until either the item is found or the item has been compared with a leaf node

20
Q

What are the steps for bubble sort?

A

• Compare the first item to the second item and swap them if they are in the wrong order
• Compare the second item with the third item and swap them if they are in the wrong order
• Keep comparing each pair of adjacent items and swapping them if they are in the wrong order
• After each pair of cards have been compared the first pass is complete
• For the next pass the item at the rear of the list doesn’t need to be compared with (as it is already in the correct position)
• For each pass, the number of items at the rear of the list that don’t need to be compared with increases by 1
• Stop when there is only 1 item that hasn’t been discounted from the comparisons

21
Q

What are the steps for merge sort?

A

• Repeatedly split the list in half until each sublist contains only 1 item
• Merge each sublist with the sublist that it was most recently split from so that the new list they form is ordered
• Continue merging the sublists until they form a single list

22
Q

What approach to problem solving is merge sort an example of?

A

‘Divide and conquer’

23
Q

What problem is Dijkstra’s Algorithm designed to solve?

A

Finding the shortest path between two nodes in a graph (it actually find the shortest path between one node and every other node)

24
Q

What is an application of Dijkstra’s Algorithm?

A

Routing packets on the Internet

25
Q

What type of tree traversal is RPN using

A

Post order tree traversal

26
Q

Convert the following from infix to RPN: 3-2

A

32-

27
Q

Convert the following from infix to RPN: (6-4) *3

A

64-3*

28
Q

Convert the following from infix to RPN: (2+(3*4))-3

A

234*+3-

29
Q

Convert the following from RPN to infix: 7 5 +

A

7+5

30
Q

Convert the following from RPN to infix: 95-2/

A

(9-5)/2

31
Q

Convert the following from RPN to infix: 42/91+x

A

(4/2)*(9+1)

32
Q

Convert the following from RPN to infix: ab+c/d^

A

((a+b)/c)^d

33
Q

Name three types of tree traversal (orders)

A

Pre-order Post-Order In-order

34
Q

What is used to implement a Depth First Search

A

Stack

35
Q

What is used to implement a breadth first search

A

Queue

36
Q

Outline Dijkstra’s algorithm

A

All nodes apart from the initial node will be set to infinity and the starter will be set to 0. All vertices and their weights are added to a priority queue sorted by current distance. While the queue is not empty the first vertex will be removed from the queue and will check all unvisited neighbors (w) of the current vertex (u) Then it will iterate the neighbors and change newDistance to distance to w + distance between W and U Checks if the distance at w (7) is greater then new distance 7 If it is distance to W = new distance At any change of a value in the priority queue there will be a reshuffle to have them in ascending order

A2 CS (12 decks)

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