Design and Analysis of Algorithms Assignment

Assignment Task

1. Lower Bound Practice. Please do problem 42(b) (chapter 3).

2. Sorting Fractions. Please do problem 48 (chapter 3).

3. Median Distance. Please do problem 65 (chapter 3), part (b). For extra credit, feel welcome to try part (c).

Problem 42 (Reduction Practice). Please use reductions from sorting or other problems above (element uniqueness, set disjointness, set equality) to show (nlogn) worst-case bounds for the following problems.

(a) Consider the following problems in the comparison model:

(i) counting the number of occurrences of a most-frequently-occurring element in an n-element array, and

(ii) given two sets A and B with A+B=n, compute AnB, AUB, or A-B. 

(b) Why is it not possible to build a comparison-based data structure supporting both the operations insert and find-median in O(1) time? 

(c) Many problems in computational geometry inherit lower bounds from sorting, element uniqueness, or their relatives. Consider the following problems in the real RAM model, since they involve points with numeric coordinates:

(i) the closest pair problem asks us to find the closest pair of points within a set of n points in the plane, and

(ii) the congruence testing problem gives us two n-point sets A and B in the 2D plane, and asks whether B can be obtained from A by applying a rigid transformation a translation plus a rotation plus (possibly) a reflection.

Problem 48 (Sorting Fractions). Radix sort can sort n integers of magnitude n for e= O(1) in linear time. Please show how to sort n fractions also in linear time, where the a,'s and be's are integers in the range 1...n for e- O(1). As a hint, can you convert this problem back to one involving sorting small integers?

Problem 65 (Average and Median Distance on a Line). we investigate the computation of statistical information about the set of () distances between n points on a number line. As input, you are given the locations 1... of these points (not necessarily sorted).
(a) Give an O(nlogn) algorithm for computing the average distance among all pairs of points.

(b) Give a randomized algorithm running in O(nlogn) time with high probability that computes the median of all (5) pairwise distances.

(c) For a challenge, can you find a deterministic O(nlogn) algorithm for the problem from part (b)?

This Mathematics has been solved by our PhD Experts at My Uni Paper.