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.
2





















学霸联盟