Skip to main content
Engineering LibreTexts


  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Course Assessment

    Miscellaneous Problems

    1. Which sorting algorithm is always slow and time complexity O(n2)?
    1. Which sorting algorithm is sometimes O(n)?
    1. What sorting algorithm runs in O(log n)?
    1. What other sorting algorithms have O(n log n) expected time?
    1. Which sorting algorithm needs extra memory space?
    1. Consider the N-Queens Problem discussed in Unit 1, which was used to demonstrate the recursive backtracking strategy. Assemble the code snapshot provided for N-Queens problem and write a complete program.
    1. Suppose you are given a sorted array with possible duplicate elements, write a program to find the number of occurrences of a given input item (assuming the element is present in the array).
    1. Consider two sets of integers, S={s1, s2, ..., sm} and T = {t1, t2, ..., tn}, m ≤ n.
      1. Design an algorithm that uses a hash table of size m to test whether S is a subset of T.
      2. What is the average running time of your algorithm?


    Grading Scheme

    As per the offering Institution grading policy.

    Course References

    • Introduction to the Design and Analysis of Algorithms, Anany Levitin, 2nd Edition, Pearson Education, Inc. 2007
    • Algorithm Design, John Kleinberge and Eva Tardos, 1st Edition, Perason Education Inc., 2006
    • Design and Analysis of Algorithms: Course Notes, Samir Khuller, University of Maryland, 1996
    • Was this article helpful?