Data Structure and Algorithms Midterm

Insertion Sort

Scans entries from LEFT to RIGHT, exchange key with a LARGER entry to its left. Sorts in Ascending

Insertion Sort Average case

N2

Insertion Sort Best Case

N (already sorted- Scan & Done)

Selection Sort

Scans from LEFT to RIGHT, finds minimum, swaps with key

Selection sort Average case

N2 (best, worst is the same)

Insertion > Mergesort

Insertion Sort is preferable when the array is small or nearly sorted because it requires fewer operations, while Mergesort always takes O(N log N) time.

Quicksort

Shuffles array, partitions. recursively sorts left and right arrays until sorted.

Selects pivot, Scans from LEFT for a LARGER item, scan from RIGHT for a SMALLER item, swap.

Repeats until LEFT>RIGHT

Quicksort average case

NlogN

Quick sort worst case

N2/N (Already sorted)

shuffle avoids worst case

What algorithm sorts in place? (no additional memory)

Quick, Insertion, selection

Merge sort

Mergesort is a sorting algorithm that repeatedly divides an array into two halves until each subarray contains one element. It then merges the subarrays back together in sorted order until the entire array is sorted

NlogN

What does a stable algorithm mean?

It preserves the relative order of equal values, meaning that equal values of first sorting will be secured even if there are multiple fields are considered to sort.

e.g. insertion & merge

why is quick sort not stable?

the partitioning and swapping could move identical elements past each other

Binary Tree

Data structure where the parent node have 2 kids on the left and right

Heap-order

Parent > Children

Binary Heap

data structure where:

1. Complete: balanced & filled

2. Heap-ordered: Parent > Children (max) or Children > Parent (min)

How to achieve heap order (heap sort)

add a node to the end, work up, delete maximum

Heap sort time/height

logN

Binary Search Tree

Symmetric binary tree where each node’s keys are:

1. Larger than all keys in LEFT

2. smaller than all keys in RIGHT

BST ordering (IN ORDER TRAVERSAL)

1. Traverse LEFT until you can’t

2. Print node

3. Traverse RIGHT until you can’t

Shuffle → Insert → In order traversal

Perfectly balanced BST

Every node has the same number of nodes. left smaller, right more

Average time: N/2

height: log2N + 1

BST weakness

Depends on order of insertion (right→ right→ right…)

height: N

BST vs Binary Heap

BST have differing children, binary heap’s children MUST be SMALLER OR LARGER

2-3 search tree

either empty or must have the SAME DEPTH

can contain 2-node or a 3-node

1. ALWAYS BALANCED

2. Sorted

3. Self-balancing: Splitting

2-3 tree search times

logN constantly

2-3 tree vs BST

BST could be skewed, 2-3 resolves that issue

Red-Black tree

Self-balancing binary search tree where each node is colored red or black to keep the tree approximately balanced

Black must be root

red cannot have children

Perfectly (sorta) balanced RB tree

same number of black nodes along every path

All paths to empty node leaves must have equal black height.

Red black time

Average: lg N

Gurantee: 2 lg N

Red black vs 2-3

implementing 2-3 requires nodes that can store multiple keys and have different numbers of children (multiple keys per node e.g. 32|16)

Red-Black Trees aim to provide similar balancing benefit, where every node stores only one key and has at most two children. 2-3 simplified (one key per node)

RB sacrifice performance with simple implemtation

what supports ordered operation (min/max, rank, select)

Search tree operations

Hashing

Saves items in a indexed table

hashcode()

assigns index to an item (k key m array size)

1. key k k.hashcode() - produces a 32 bit integer

2. compresses integer in to a array between o & M-1
   (MODULAR HASHING: computes the remainder when dividing by M)

3. stores key

Collision

two keys hashing in the same index

Separate chaining

M (slot #) < N (key #)

Each index holds a linked list

Separate chaining average time

is constant (3-5) because of UFA

Uniform Hashing Assumption

1. Each key is equally likely to hash to an int between 0 & M-1

2. Each key’s hash is independent

proves hash table efficiency of constant time

Why is search proportional to N/M

based on UHA, keys are equally likley to be hashed between 0 and M-1,

probability of # of keys in the index is N/M, average share of N/M

if N is almost = M

proves efficiency of hash tables as collisions are randomly spread out rather than clustered, so search is constant when load is bounded

n/m = almost one (constant), time is constant

Open addressing (linear probing)

when new keys collide, it finds the next empty slot to insert (keep checking until it is)

M MUST BE > N or else it will go on forever

load factor

how much of the table is occupied

average: ~1/2

higher= longer search time.

UHA search and insert

Under the Uniform Hashing Assumption, keys are evenly distributed across the hash table on average. N/M represents the average number of keys in each bucket (linked list). A higher N/M means longer lists and slower searches, while a constant N/M keeps average search time at O(1).

problem & solution for linear probing

Running out of room, clustering in middle (more likley)

if N/M > 1/2, double array size

if M/N < 1/8, half the array size

need to rehash (start over)

modular hashing

taking modulus (remainder) 32 bit hash code number by dividing by M (table size)

Why is guranteed time N or average time 3-5 for hashing

N: the values could all be hashed to the same index, meaning it will be in one large linked list. In the worst case, the key could be the very last element of that linkedlist and would have to go through all

3-5: UHA states that keys are all equally likley to be hashed in the M slots. every linked list should be about the same size, on average N/M which is a constant. constant good