Brainscape's Knowledge GenomeTM

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


See full index

Exam prep Josh > ADDS exam prep > Flashcards

ADDS exam prep Flashcards

1
Q

What is a directed graph

A

Every point has a line segment that connects to every other point. n(n-1) line-segments

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

What is an undirected graph

A

Only one line segment connection between two points.

(n(n-1))*1/2

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

Define Adjacency list

A

List that represents a graph as an array of linked lists

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

How many edges can a tree have?

A

can have (n-1) edges

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

What is a tree?

A
  • > Must have all nodes connected
  • >Cannot contain cycles
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the height of a tree?

A

Longest path from node to leaf

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

What is the depth of a tree?

A

Longest path from root to the leaf

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

What is a binary tree?

A

A tree with at most two child nodes

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

What is an ordered, balanced tree?

A

The tree is organised such that a nodes left child will be less than the parent.

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

What is the complexity for searching a ordered balanced tree?

A

O(log n)

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

What is the worst case complexity of a binary tree search?

A

complexity n - If they are in one line.

o
\
o
\
o
\
ect

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

Tree traversal - What is Pre-order?

Give output to image

A

(node, left, right)

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

Tree traversal - What is post-order

A

(left, right, node)

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

Tree traversal - What is in-order

A

(left, node, right)

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

Write post fix for the following seqence

5231+*-4/

Give the output for pre-order, post-order and in-order

A

pre-order (node, left, right)

/ - 5 * 2 + 3 1 4

Post order - (left right node)

5 2 3 1 + * - 4 /

in-order (left node right)

5 - 2 * 3 + 1 / 4

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

What are the properties of Binary Search Tree

A
  • Nodes are comparable
  • The left subtree of a node contains only values that are less than the node’s own value
  • The right subtree of a node contains nly values that are greater thanhe node’s own value.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Binary search tree - Searching

Example, how would you search for the following

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

Binary search tree - Min and max value

How would you find the max value of a binary tree?

What is the worst case running time?

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

Binary search tree - How do you insert a number?

For example add the following numbers

A

If the value is less than the node it is put on the left and if the value is greater than the node it is put on the right.

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

Binary search tree - Deletion

case 1: Deleated node has no child nodes

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

BST - Deletion

case 2: The node to be deleted has one child

What do you do?

A

You

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

BST - Deletion

Case three - The node to be deleted has two child nodes

Delete 7 node

A

So you look at the node that you need to delete

1) Replace the node that you are going to delete with the max value from it’s left subtree. In this case it’s 5. So the 7 node has now become a 5.
2) You delete the 5 leaf. Thus the BST still holds. The larger values are on the right and the smaller values are on the left.

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

What is the performance of a BST?

What is the worst case of a BST search?

A

o(n) if the are all within a line

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

AVL - What is the balance factor?

give equation

A

height(left subtree) - height(right subtree) |

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

What are the three properties of an AVL tree?

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

Calculating the balance factor examples

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

AVL - Single rotation

What type of rotation is needed here?

Complete the rotation

A

It’s left left heavy so we need to rotate to the right.

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

AVL - Single rotation

What type of rotation is needed here?

Complete the rotation

A

Right right heavy which means that you need to do a left rotation.

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

AVL - double rotation

What type of rotation is needed here?

Complete the rotation

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

AVL - Single rotation

What type of rotation is needed here?

Complete the rotation

A
31
Q

AVL trees

How would you search for a node?

How would you add a node?

How would you delete a node?

A
32
Q

AVL tree - insert numbers from 1 to 7 and restructor

A
33
Q

Performance of AVL tree

How much space?

What is the complexity of restructing?

What is the complexity of searching?

What is the complexity of insertion?

What is the complexity of deletion?

A
34
Q

AVL example:

insert the following numbers in an AVL tree

A
35
Q

AVL example

Restructure the following BST into an AVL tree

A
36
Q

What are the properties of a Binary heap?

What is a min heap?

What is a max heap?

What must happen on every level?

In which way are nodes added to a binary heap?

A
37
Q

What is the complexity of insert and delete min?

A

O(log(n))

38
Q

Build a min heap with the following inputs

Also what is the complexity this heap?

A

It will be O( n log(n))

This is because inserting into the heap is log(n) and we will need to do this n times where n is the number of elements that needed to be added to the heap.

39
Q

Is this a min heap? If not, fix it.

A

Start at the right of the second to last row and start swapping. Compare elements 2i+1 then 2i

40
Q

What is the complexity of build heap backwards

A

Establishes a heap in O(n) time

41
Q

Fix the following min heap

After fixing the min heap perform a heap sort.

A

To sort the array, push the root into the first element of the array then delete.

Then, you move the last leaf into the root. Restructure if necessary.

Repeat.

42
Q

Complete the following breadth first search tree

A
43
Q

Assuming that the graph has n nodes and m edges. What is the big-oh runtime?

A

o(n+m)

44
Q

Complete the following depth first search tree

A
45
Q

Complete the tree for BFS

A
46
Q

Complete the DFS for the following graph

A
47
Q

Complete the BFS for the following graph

A
48
Q

Complete DFS for the following graph

A
49
Q

How does selection sort work?

sort 1,8,6,5,9,2

How many comparisons? How many swaps

A

The first element of the array is initially set as the minimum.

Then, the array is itterated through to check what the minimum of the array is.

If there is a value that is less than the current minimum, they are swaped

After the swap (or no swap in the case that the first element was the smallest in the array) the next element is set as the minimum and the process is repeated until the array is sorted.

50
Q

What is the best, avarage and worst case complexity for selection sort?

A
51
Q

Write pseudocode for selection sort

A
52
Q

How does insertion sort work?

sort 1,8,6,5,9,2

How many comparisons? How many swaps

A

The array is itterated through.

First element is marked as sorted

then each element is checked to see if it’s smaller or larger than the sorted list. If it is smaller then it’s inserted in the correct place.

The number keeps checking the previous element to check if it’s in the correct place until it is. Every check is a comparison

53
Q

What is the pseudocode for insertion sort?

A
54
Q

What is the time complexity of insertion sort?

A
55
Q

How does Bubble Sort work?

sort 1,8,6,5,9,2

How many comparisons? How many swaps

A

The first two elements are checked. If the larger element of the two is not on the right then the elements are swaped. This is completed untill the end of the array. After each itteration, the largest number will filter down to the end of the array.

This is repeated until the array is sorted

56
Q

Write pseudocode for bubble sort

A
57
Q

What is the average, best and worst complexity of bubble sort?

A
58
Q

How does quicksort work?

Sort 5,6,3,4,7,2

How many comparisons? How many swaps?

is it stable?

A

Quicksort is a recursive divide and conquer sorting algorithm.

A pivot is chosen and the array is recursivly sorted into two arrays. On the left the values are less than the pivot and on the right the values are larger than the pivot.

The recursive call is then called again until there is only one element in the array. Everything is then appended and you will have a sorted array

no not stable

59
Q

Write the psudo code for quicksort

A
60
Q

What is the complexity of quicksort?

What happens if we don’t choose the pivot correctly?

A
61
Q

What is merge sort?

sort 3,7,8,2,9,1,6,5 how many comparisons and swaps?

A

Merge sort is a recursive sort that keeps splitting an arary in half until we have just one element.

Then the recursion tree is climbed and each element is sorted

62
Q

Write the code for merge sort?

A
63
Q

What is the complexity of merge sort?

Is merge sort stable?

A

O(nlog(n)) for all cases

yes stable

64
Q

What is distribution sort/bucket sort?

sort 2,5,6,6,2,3,410,3,6,7,8

A

Distribution sort is a little weird.

We first set up buckets with the values of 1 to 10. The unsorted array is read through and each number is put into its respective bucket. Each time a number enters a bucket the counter goes up

Then a running total is added and using this information, the list is sorted

65
Q

What is the complexity of bucket sort?

A

You need to make sure that your data is uniformally distributed. If it isn’t, you will have a complexity of o(n^2)

This is faster than comparison sorting but the data can’t be complex.

66
Q

Stack - is it FIFO or LIFO?

A

LIFO

Think of it like a stack of books. You need to remove the books on top to get access to the book on the bottom.

67
Q
A

a) 67
b) 9

68
Q
A

b) 1

69
Q

What are the two major operations that you can do with a queue?

A

1) en-queue - add a node at the end of a queue
2) de-queue - remove the queue at the front of the list

70
Q

Complete for stack and queue

A
71
Q

What is the definition of Big-oh?

A

1) for f(n) = O( g(n) )

If f(n) <= c*g(n) for all n>= k Where C and K are positive.

2) f(n)/g(n) <= c for all n >= k.

72
Q

What is the difference between Overloading, Overriding, Redefining.

A

Overloading:

int func(int a); -superclass

int func(int a, int b) (same name but different signature)

Overriding: -virtual is found in run-time

virtual int func(int a); -super class

virtual int func(int a) override; -child class

Redefining: -This is bad coding practice

int func(); - superclass

int func(); - childClass

73
Q

What is masters theorem and what are the three cases?

A

T(n) = aT(n/b)+f(n)

Where a>=1 b>1 f(n) = Theta(n^d)

T(n) is calculated from the following cases:

1) Theta(n^d) if a < b^d
2) Theta(n^d log n) if a = b^d
3) Theta(n^(log(a/b)) if a > b^d

Exam prep Josh (3 decks)

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