Corina

Question 1

What is Big-Theta Notation

Answer 1

f(n) is Θ(g(n)) if there exist constants c > 0, d > 0 and N ∈ N
such that
cg(n) ≤ f(n) ≤ dg(n) for n ≥ N

Question 2

What is time complexity?

Answer 2

The computational complexity that describes the amount of computer time it takes to run an algorithm

Question 3

What is asymptotic behaviour of a running time?

Answer 3

What happens when n becomes very large

Question 4

What are the advantages of Big-Theta Notation?

Answer 4

• We can compare algorithms by comparing the rates of growth of their running times
• We can estimate algorithm running times on large inputs by measuring running time on a small input

Question 5

What are the disadvantages of Big-Theta Notation?

Answer 5

• Can not compare algorithms whose running times have the same rate of growth
• Small inputs Big-Theta can be misleading

Question 6

What is Big-O notation?

Answer 6

• Gives the upper bound for the rate of growth
• it is true for either worst/average/best case

Question 7

What is Big-Omega Notation?

Answer 7

• Gives the lower bound for the rate of growth
• It is true for either worst/average/best case

Question 8

What is the Big-O notation equation?

Answer 8

f(n) is O(g(n)) if there exist constants d > 0 and N ∈ N s.t.
f(n) ≤ dg(n) for n ≥ N

Question 9

What is the Big-Omega notation equation?

Answer 9

f(n) is Ω(g(n)) if there exist constants c > 0 and N ∈ N s.t.
f(n) ≥ cg(n) for n ≥ N

Question 10

What is the access time of arrays?

Answer 10

Θ(1)

Question 11

How are arrays stored?

Answer 11

They use a contiguous chunk of memory

Question 12

What is the time complexity of a stack?

Answer 12

Θ(1)

Question 13

What is the memory requirement of a stack?

Answer 13

Θ(n)

Question 14

What is a doubly linked list?

Answer 14

Allows for Θ(1) add and remove at both ends

Question 15

What is a dummy node used for?

Answer 15

To make implementation slicker

Question 16

How are skip lists more beneficial than linked lists?

Answer 16

Skip lists are hierarchies of linked lists which support binary search

Question 17

What is the search time complexity of skip lists?

Answer 17

Θ(log(n))

Question 18

What advantage do skip lists have over binary trees?

Answer 18

They allow efficient concurrent access

Question 19

What is a tree?

Answer 19

An acyclic undirected graph

Question 20

What is a binary tree?

Answer 20

A tree where each node can have zero, one or two children

Question 21

What is the total number of possible nodes?

Answer 21

2^l

Question 22

How do you search a binary tree?

Answer 22

• Start at the root
• Compare the element
• If less than element go left
• If greater than element go right
• If equal to element found

Question 23

How do we iterate through trees?

Answer 23

• We start at the left-most branch
• If right child exists then move right once and then move as far left as possible
• Else go up to the left as far as possible and then move up right

Question 24

How do we remove an element with two children from a tree?

Answer 24

• Replace that element by its successor
• And then remove the successor using the above procedure

Question 25

How can we change the shape of trees to avoid unbalanced trees?

Answer 25

Rotations

Question 26

What are the 4 types of rotation?

Answer 26

- Left Rotation - Right rotation - Left-right double rotation - Right-left double rotation

Question 27

What is an AVL tree?

Answer 27

A binary search tree in which 1. the heights of the left and right subtree differ by at most 1 2. the left and right subtrees are AVL trees

Question 28

What is the worst case of rotations for an AVL tree?

Answer 28

Θ(log(n))

Question 29

What is the height of an AVL tree?

Answer 29

Θ(log(n))

Question 30

What is the worst case for insertion, deletion and search in an AVL tree?

Answer 30

Θ(log(n))