Brainscape's Knowledge GenomeTM

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


See full index

[OBSELETE] AQA - A Level CS > Algorithms > Flashcards

Algorithms Flashcards

1
Q

What are the different ways to traverse a binary tree?

A
  1. Preorder
  2. In order
  3. Postorder
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How do all of the tree traversal algorithms work?

A
  • Algorithm given a input
  • Algorithm outputs a data in a different order
  • Depending on algorithm used
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How does preorder traversal work?

A
  • The top down traversal method
  • Encounters all roots before encountering the leaves
  • Left over right
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the pseudo code for preorder traversal?

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

How does in order traversal work?

A
  1. Traverse left sub tree
  2. Visit the root first
  3. Traverse the right sub tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the pseudo code for in order traversal?

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

How does post order traversal work?

A
  • Bottom up traversal
  • Encounter all the leaves before the roots
    1. Traverse the left sub-tree
    2, Traverse the right sub-tree
    3. Visit the root
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the pseudo code for post order traversal?

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

What is the infix notation?

A
  • A + B
  • The + notation is fixed in between the two operands (numbers)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the problem with infix notation?

A
  • When not using brackets with longer expressions
  • Order of calculations can be ambiguous
  • 2 * A + B
  • Computers don’t know what to do first without brackets
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is Polish notation?

A
  • Alternative to infix notation
  • A + B -> +A B
  • Add number A to number B
  • Prefix notation due to operator before opperand
  • No ambiguity meaning its easier for computers to understand
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is reverse Polish notation?

A
  • Postfix notation
  • Operator after operand
  • A + B -> A B +
  • No ambiguity
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Why is reverse Polish notation important in comp Sci?

A
  • Unambiguous and doesn’t require brackets
  • Can be worked out using stacks
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What can you do with infix notation (3*(1+2)) and a binary tree

A
  • You can use reverse Polish notation to store tree traversal routes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How do use a stack with reverse Polish notation

A
  • You use the reverse Polish notation and go from left to right
  • To push items onto stacks if they are numbers
  • To pop items out of stacks and carry out calculations if there is an operator
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the steps in converting from infix to reverse polish notation?

A
  1. Use infix notation to contruct binary tree
  2. Use binary tree to write reverse polish notation
  3. Using post order tree traveersal
17
Q

What are the steps in converting 3*(1+2) to a binary tree

A
18
Q

How do you convert a binary tree to reverse polish notation?

A

From the root node:
- Go left and call traverse
- Go right and call traverse
- Out node
- Go up if you can

19
Q

Explain this psudocode

A
  • Linear seach
  • Linear time complexity O(n)
  • Keep going along the data set until you have found the datayou want
20
Q

Explain this psudocode

A
  • Binary Search
  • Time complexity O(log n)
  • Uses a Lower Bound, Mid Point and Upperbound which are assigned to indexes
  • Uses a 2 ranges lower to mid and mid to upper to estimate which range the wanted data is in
  • Repeats until the mid is the same as upper or lower
21
Q

What are the two different ways to traverse a graph?

A
  • Depth first (using a stack)
  • Breath first (using a queue)
22
Q

What is the depth-first approach?

A
  • Graph Traversall algorithm
  • Uses a stack
  • Start at the root and follow one branch as fasr as it will go
  • Then backtrack
23
Q

What is the breath-first approach?

A
  • Graph Traversal allgorithm
  • Uses a queue
  • Starts at the root, scan every node connected
  • Continue scaning from left to right
24
Q

What is the psudocode for a depth first approach?

A
25
Q

Use the diagram to traverse the graph using the depth first approach

A
26
Q

What is the psudocode for a breadth first approach?

A
27
Q

Use the diagram to traverse the graph using the breadth first approach

A
28
Q

What is merge sort?

A
  • Sorting algorithm
  • O (n log n)
  • Fast
  • Divide and concquer approach
  • Uses Recusion
29
Q

How does merge sort work?

A
30
Q

How can you layout dijkstras shortest path?

A
  • Represented as an array
  • Can use a series of lists and a cube structure
31
Q

Perform Dijkstras algorithm on this graph

A

[OBSELETE] AQA - A Level CS (13 decks)

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