Summary
- Page ID
- 50075
\( \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}}\)
Miscellaneous Problems
- Which sorting algorithm is always slow and time complexity O(n2)?
- Which sorting algorithm is sometimes O(n)?
- What sorting algorithm runs in O(log n)?
- What other sorting algorithms have O(n log n) expected time?
- Which sorting algorithm needs extra memory space?
- 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.
- 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).
- Consider two sets of integers, S={s1, s2, ..., sm} and T = {t1, t2, ..., tn}, m ≤ n.
- Design an algorithm that uses a hash table of size m to test whether S is a subset of T.
- What is the average running time of your algorithm?
Answers
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