COP 3530 Final Exam Review

Computational complexity of accessing an item at a specified index in an array based list

O(1)

Computational complexity of accessing an item at a specified index in a reference based (linked) list

O(n)

Computational complexity of adding an item to an array based list

O(1)

Computational complexity of adding an item to a reference based list

O(n)

Computational complexity of inserting and deleting for BST

O(log n)

I make it easy to access the item most recently added or accessed

Splay Tree

I guarantee balance after every insertion

AVL Tree

Every access is at a leaf

B+ Tree

I use color changes and rotations to maintain similar path lengths to each leaf

Red-Black Tree

Computational complexity for access, insertion, deletion in a hash table

O(1)

Array implémentation of a heap has a root at

1

An item at index i has a left child at

2i

An item at index I has a right child at

2i + 1

An item at index I has a parent at

floor (I/2)

Computational complexity of selection sort

O(n^2)

Computational complexity of insertion sort (average)

O(n^2)

Computational complexity of Insertion sort (best)

O(n)

Computational complexity of bubble sort (average)

O(n^2)

Computational complexity of bubble sort (best)

O(n)

Computational complexity of quick sort (average)

O(n log n) (divide and conquer)

Computational complexity of quick sort (worst)

O(n^2) (divide and conquer)

Computational complexity of merge sort

O(n log n) (divide an conquer)

Computational complexity of heap sort

O(n log n)

Greedy algorithm

Solves problems in steps and takes an optimum at each step

Dynamic programming

Solves the problem in steps starting at the lowest step and building up (overlapping subproblems)

Divide and conquer

Splits the problem into smaller parts and recursively solves the smaller versions

Brute force

Checks every possible solution

The following recurrence relation used to solve a problem is indicative of what type of algorithm?

S(i, W) = max( S(i-1, W) , S(i-1, W-wi + vi)

Dynamic programming

Uses a table

Dynamic programming

The only way to get the optimal solution for np problems

Brute force

Solved using recursion

Divide and conquer

Recursive factorial complexity

O(n)

Complexity (avg) of insertion/deletion of heaps

O(log n)