CS 6515 Exam
CS 6515 Exam 1 QUESTIONS WITH
SOLUTION
Binary Search Runtime - O(log n)
Merge Sort Runtime - O(n log n)
Naive Multiplication of n-bit Integers Runtime - O(n²)
Fast Multiplication of n-bit Integers (Using Divide and Conquer) Runtime - O(n^log₂3) ≈
O(n¹.⁵⁹)
Median Finding Algorithm Runtime - O(n)
FFT (Fast Fourier Transform) Runtime - O(n log n)
Gauss's Method for Multiplying Complex Numbers (Number of Multiplications) - 3
multiplications
Euclid's GCD Algorithm Runtime - O(log(min(a, b)))
Strassen's Algorithm for Matrix Multiplication Runtime - O(n^log₂7) ≈ O(n².⁸ⁱ)
Recurrence for Naive Multiplication of n-bit Integers - T(n) = 4T(n/2) + O(n)
Recurrence for Fast Multiplication (Divide and Conquer) - T(n) = 3T(n/2) + O(n)
CS 6515 Exam
, CS 6515 Exam
Gauss's Formula for Multiplying Two Complex Numbers -
(a+bi)×(c+di)=(ac−bd)+(ad+bc)i
Recurrence for Merge Sort - 2T(n/2) + O(n)
Master Theorem Formula - T(n) = aT(n/b) + O(n^d)
a = number of recursive calls
b = size of partitions in recursive calls
d = degree of work done at each recursive step
Matrix Multiplication via Strassen's Algorithm (Formula for Recursive Steps) - T(n)=
7T(n/2) + O(n^2)
QuickSelect Algorithm Description - Choose a pivot p.
Partition A into elements less than p, equal to p, and greater than p.
Recursively search one of the partitions based on the value of k and the size of the
partitions.
Definition of a Good Pivot - A pivot p is good if it lies between the n/4-th smallest and
the 3n/4-th smallest element, meaning the partition sizes are at most 3n/4.
Recurrence for Algorithm with an Approximate Median - T(n)=T(0.75n)+O(n), which
solves to O(n).
Recursive Algorithm to Find a Good Pivot (Main Idea) - Break A into n/5 groups of 5
elements.
CS 6515 Exam
CS 6515 Exam 1 QUESTIONS WITH
SOLUTION
Binary Search Runtime - O(log n)
Merge Sort Runtime - O(n log n)
Naive Multiplication of n-bit Integers Runtime - O(n²)
Fast Multiplication of n-bit Integers (Using Divide and Conquer) Runtime - O(n^log₂3) ≈
O(n¹.⁵⁹)
Median Finding Algorithm Runtime - O(n)
FFT (Fast Fourier Transform) Runtime - O(n log n)
Gauss's Method for Multiplying Complex Numbers (Number of Multiplications) - 3
multiplications
Euclid's GCD Algorithm Runtime - O(log(min(a, b)))
Strassen's Algorithm for Matrix Multiplication Runtime - O(n^log₂7) ≈ O(n².⁸ⁱ)
Recurrence for Naive Multiplication of n-bit Integers - T(n) = 4T(n/2) + O(n)
Recurrence for Fast Multiplication (Divide and Conquer) - T(n) = 3T(n/2) + O(n)
CS 6515 Exam
, CS 6515 Exam
Gauss's Formula for Multiplying Two Complex Numbers -
(a+bi)×(c+di)=(ac−bd)+(ad+bc)i
Recurrence for Merge Sort - 2T(n/2) + O(n)
Master Theorem Formula - T(n) = aT(n/b) + O(n^d)
a = number of recursive calls
b = size of partitions in recursive calls
d = degree of work done at each recursive step
Matrix Multiplication via Strassen's Algorithm (Formula for Recursive Steps) - T(n)=
7T(n/2) + O(n^2)
QuickSelect Algorithm Description - Choose a pivot p.
Partition A into elements less than p, equal to p, and greater than p.
Recursively search one of the partitions based on the value of k and the size of the
partitions.
Definition of a Good Pivot - A pivot p is good if it lies between the n/4-th smallest and
the 3n/4-th smallest element, meaning the partition sizes are at most 3n/4.
Recurrence for Algorithm with an Approximate Median - T(n)=T(0.75n)+O(n), which
solves to O(n).
Recursive Algorithm to Find a Good Pivot (Main Idea) - Break A into n/5 groups of 5
elements.
CS 6515 Exam
