CMPT307 Midterm Test Summary Qianping
Midterm Test Summary Qianping
CMPT307 Midterm Test Summary Qianping Gu
Summary for midterm test 1
• Asymptotic order of growth of functions for the running time of algorithms.
Big-Oh, Big-Omega, Big-Theta, little-oh and little-omega notations. For example,
answer which of functions f(n) and g(n) has a larger order of growth rate.
• Divide and conquer algorithm basics, recursion analysis, master theorem. For
example, design a divide and conquer algorithm for a given problem, prove the
correctness of the algorithm and analyze the running time of the algorithm.
• Randomized algorithm basics, expectation of discrete random variables,
average running time of algorithms. For example, design a randomized
algorithm for a given problem, prove the correctness of the algorithm and
analyze the average running time of the algorithm.
1
CMPT307 Midterm Test Summary Qianping Gu
• Sorting and statistics, insertion sort, merge sort, max-heap, min-heap, heapsort,
quicksort, lower bound on comparison based sorting, counting sort, radix sort,
bucket sort, selection problem (find the ith smallest element). For example,
apply/modify the sorting algorithms to sort input instances satisfying some
conditions, prove the correctness of the modified algorithm and analyze the
running time of the modified algorithm.
Summary for midterm test 1
• Asymptotic order of growth of functions for the running time of algorithms.
Big-Oh, Big-Omega, Big-Theta, little-oh and little-omega notations. For example,
answer which of functions f(n) and g(n) has a larger order of growth rate.
• Divide and conquer algorithm basics, recursion analysis, master theorem. For
example, design a divide and conquer algorithm for a given problem, prove the
correctness of the algorithm and analyze the running time of the algorithm.
• Randomized algorithm basics, expectation of discrete random variables,
average running time of algorithms. For example, design a randomized
algorithm for a given problem, prove the correctness of the algorithm and
analyze the average running time of the algorithm.
1
CMPT307 Midterm Test Summary Qianping Gu
• Sorting and statistics, insertion sort, merge sort, max-heap, min-heap, heapsort,
quicksort, lower bound on comparison based sorting, counting sort, radix sort,
bucket sort, selection problem (find the ith smallest element). For example,
apply/modify the sorting algorithms to sort input instances satisfying some
conditions, prove the correctness of the modified algorithm and analyze the
running time of the modified algorithm.