- \> Must have all nodes connected - \>Cannot contain cycles

ADDS exam prep Flashcards by Tom Henderson

What is a directed graph

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

How well did you know this?

Not at all

Perfectly

What is an undirected graph

Only one line segment connection between two points.

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

How well did you know this?

Not at all

Perfectly

Define Adjacency list

List that represents a graph as an array of linked lists

How well did you know this?

Not at all

Perfectly

How many edges can a tree have?

can have (n-1) edges

How well did you know this?

Not at all

Perfectly

What is a tree?

> Must have all nodes connected
>Cannot contain cycles

How well did you know this?

Not at all

Perfectly

What is the height of a tree?

Longest path from node to leaf

How well did you know this?

Not at all

Perfectly

What is the depth of a tree?

Longest path from root to the leaf

How well did you know this?

Not at all

Perfectly

What is a binary tree?

A tree with at most two child nodes

How well did you know this?

Not at all

Perfectly

What is an ordered, balanced tree?

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

How well did you know this?

Not at all

Perfectly

What is the complexity for searching a ordered balanced tree?

O(log n)

How well did you know this?

Not at all

Perfectly

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

complexity n - If they are in one line.

o
\
o
\
o
\
ect

How well did you know this?

Not at all

Perfectly

Tree traversal - What is Pre-order?

Give output to image

(node, left, right)

How well did you know this?

Not at all

Perfectly

Tree traversal - What is post-order

(left, right, node)

How well did you know this?

Not at all

Perfectly

Tree traversal - What is in-order

(left, node, right)

How well did you know this?

Not at all

Perfectly

Write post fix for the following seqence

5231+*-4/

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

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?

Not at all

Perfectly

What are the properties of Binary Search Tree

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?

Not at all

Perfectly

Binary search tree - Searching

Example, how would you search for the following

How well did you know this?

Not at all

Perfectly

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?

How well did you know this?

Not at all

Perfectly

Binary search tree - How do you insert a number?

For example add the following numbers

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?

Not at all

Perfectly

Binary search tree - Deletion

case 1: Deleated node has no child nodes

How well did you know this?

Not at all

Perfectly

BST - Deletion

case 2: The node to be deleted has one child

What do you do?

You

How well did you know this?

Not at all

Perfectly

BST - Deletion

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

Delete 7 node

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?

Not at all

Perfectly

What is the performance of a BST?

What is the worst case of a BST search?

o(n) if the are all within a line

How well did you know this?

Not at all

Perfectly

AVL - What is the balance factor?

give equation

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

How well did you know this?

Not at all

Perfectly

What are the three properties of an AVL tree?

Calculating the balance factor examples

AVL - Single rotation What type of rotation is needed here? Complete the rotation

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

AVL - Single rotation What type of rotation is needed here? Complete the rotation

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

AVL - double rotation What type of rotation is needed here? Complete the rotation

AVL - Single rotation What type of rotation is needed here? Complete the rotation

AVL trees How would you search for a node? How would you add a node? How would you delete a node?

AVL tree - insert numbers from 1 to 7 and restructor

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?

AVL example: insert the following numbers in an AVL tree

AVL example Restructure the following BST into an AVL tree

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?

What is the complexity of insert and delete min?

O(log(n))

Build a min heap with the following inputs Also what is the complexity this heap?

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.

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

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

What is the complexity of build heap backwards

Establishes a heap in O(n) time

Fix the following min heap After fixing the min heap perform a heap sort.

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.

Complete the following breadth first search tree

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

o(n+m)

Complete the following depth first search tree

Complete the tree for BFS

Complete the DFS for the following graph

Complete the BFS for the following graph

Complete DFS for the following graph

How does selection sort work? sort 1,8,6,5,9,2 How many comparisons? How many swaps

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.

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

Write pseudocode for selection sort

How does insertion sort work? sort 1,8,6,5,9,2 How many comparisons? How many swaps

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

What is the pseudocode for insertion sort?

What is the time complexity of insertion sort?

How does Bubble Sort work? sort 1,8,6,5,9,2 How many comparisons? How many swaps

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

Write pseudocode for bubble sort

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

How does quicksort work? ## Footnote Sort 5,6,3,4,7,2 How many comparisons? How many swaps? is it stable?

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

Write the psudo code for quicksort

What is the complexity of quicksort? What happens if we don't choose the pivot correctly?

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

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

Write the code for merge sort?

What is the complexity of merge sort? Is merge sort stable?

O(nlog(n)) for all cases yes stable

What is distribution sort/bucket sort? sort 2,5,6,6,2,3,410,3,6,7,8

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

What is the complexity of bucket sort?

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.

Stack - is it FIFO or LIFO?

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.

a) 67 b) 9

b) 1

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

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

Complete for stack and queue

What is the definition of Big-oh?

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.

What is the difference between Overloading, Overriding, Redefining.

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

What is masters theorem and what are the three cases?

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