CIS 1210 - Midterm 1 (GS - Heaps)

Euclid’s Algorithm

Prove correctness of Euclid’s

Runtime of Euclid’s

O(logb) where b is the the second inputed element gcd(a, b)

Runtime Analysis of Euclid’s

Is sorting in decreasing or increasing order?

increasing

Runtime of Insertion Sort

O(n²)

Insertion Sort Algorithm

Correctness of Insertion Sort

Proof of Runtime of Insertion Sort

Big O def

Big Omega def

Theta def

little o

little omega

just read

what’s wrong?

equals

give runtime recurrence for each

solve recurrences

Linear Search Algorithm

Find & solve out runtime recurrence of linear search

binary search algo

Find & solve out runtime recurrence of binary search

Merge & MergeSort Algorithm

Find & solve out runtime recurrence of merge sort

Prove using induction that Merge Sort is upperbounded by O(nlgn)

Write out Simplified Master’s Theorem

Runtime of Deterministic QuickSort Algo

O(n²)

Deterministic QuickSort Algorithm

Prove Running Time & Recurrence of Deterministic QuickSort

Design an Algo

Prove runtime analysis for Counting Inversions

Running time of Closest Pair Algorithm

O(nlgn)

Summarize the Closest pair algorithm

https://www.seas.upenn.edu/~cis1210/current/lectures/notes.pdf#page=66

runtime of quicksort using select as pivot

worst case O(nlgn)

partition runtime

O(n)

Select runtime

O(n)

select algorithm

Proof of runtime of select

Integer Multiplication Algorithm

Integer Multiplication Runtime

O(n^1.59)

Integer Mutlipication Runtime Proof

amortized analysis & class example

amortized analysis, which means that we will be finding the time-averaged cost for a sequence of operations. In other words, the amortized runtime of an operation is the time required to perform a sequence of operations averaged over all the operations performed. Let T(n) be the total time needed to perform a series of n push operations. Then the amortized time of a single push operation is T(n)/n. e.g. stacks *2

amortized runtime analysis of push

O(1)

worst case analysis of push

O(nlgn)

Do the runtime analysis

Do the runtime analysis

Stacks are

LIFO

Queues are

FIFO

How does the binary heap data structure work?

• its an array where each node corresponds to an element in the array

• we can view it as an almost complete binary tree (completely filled on all levels except the lowest which is filled from the left up to a point)

Max heap properties

every node i other than the root, A[Parent] >= A[i], that is, the value of a node is at most the value of its parent. Thus, the largest element in a max-heap is stored at the root, and the subtree rooted at a node contains values no larger than that contained at the node itself.

what is height and what is the height of a complete binary tree?

we define the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf, and we define the height of the heap to be the height of its root. Since a heap of n elements is based on a complete binary tree, its height is floor(lgn)

What is the index of the parent, left child, and right child of a binary tree?

What’s the difference between A.length and A.heapsize?

for the heap array A, we store two properties: A.length, which is the number of elements in the array, and A.heapsize, which is the number of array elements that are actually part of the heap. Even though A is potentially filled with numbers, only the elements in A[1..A.heapsize] are actually part of the heap.

What are the indices of the leaves in a binary heap? How many leaves?

The leaves of the heap are the nodes indexed by bn/2c + 1, bn/2c + 2, ..., n, so there are ∼ n/2 = O(n) elements which are at the leaves.

What is Max-Heapify and its running time?

It maintains the Max-Heap Property, O(lgn)

What is Build-Max-Heap and its running time?

Build-Max-Heap produces a max-heap from an unordered input array, O(n)

What is Heapsort and its running time?

A sorting algorithm, O(nlgn)

What is the running time of Max-Heap Insert, Heap-Extract-Max, Heap-Increase-Key, Heap_Maximum?

O(lgn)

What is the Max-Heapify Algo?

What is the running time of max-heapify?

Build Heap Algorithm

Correctness of Build Max Heap

Runtime of Build-Max-Heap

How does HeapSort work?

What is Heap-Maximum in Priority Queues and its running time?

What is Heap-Extract-Max and its running time?

What is Heap-Increase-Key and its running time?