Yours

Summary

Algorithm Design and Analysis · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    From LibreTexts, under CC BY-SA 3.0, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    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?

    Answers

    mailto:njulumi@gmail.com

    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