2023年11月25日

编程代写｜Secure Programming Coursework

本次美国作业是一个算法分析的算法代写限时测试

Section A: Algorithms Math [4 points each]

1. Compute exactly the sum 4 + 8 + 12 + 16 + … + 2008.

2. How many vertices are in a “complete” binary tree of height 24? How many of those vertices are leaves?

3. Prove using the c-n0 definition that if f(n) = 2008n2 + 24n + 9 and g(n) = 9n2 + 24n + 2008, then f(n) = O(g(n)).

4. Express (9n + 24) / n(n+1) as the sum of two “partial fractions”.

5. Rank the following five functions in increasing order of asymptotic growth: (n-9)!, 9log(n+2008)10 , 33n, 0.24n4 + 1, √n.

Section B: Recurrence Equations

Consider the base–cases and recurrence equation

T(1) = 1
T(n) = 8T(n/4) + n, n > 1

1. Construct an algorithm whose time complexity is described by this recurrence equation. [4 points]

2. Use the Master Theorem to determine the order of growth of T(n). [4 points]

3. Use the techniques studied in class to derive a closed-form solution for T(n). [10 points]

4. Verify that your solution is correct for the case n = 4. [2 points]

Section C: Numerical Algorithms

1. Describe a brute-force approach to finding the product of two “long” (multi-digit) integers. What is the time complexity?

2. Describe a brute-force approach to evaluating p(x), where p is a polynomial of degree n. What is the time complexity?

3. Describe a brute-force approach to multiplying a pair of n x n matrices. What is the time complexity?

4. Describe a brute-force approach to solving a system of n linear equations and n unknowns. What is the time complexity?

5. For one of the four aforementioned numerical problems, describe an alternative approach that is better than the brute-force.
What is its time complexity?

Section D: Closest-Point Problems and Algorithms

1. Describe how to find the furthest pair of values in a sorted array of numbers (where “furthest” means maximizing the
difference in their values). What is the time complexity?

2. Describe how to find the closest pair of values in a sorted array of numbers (where “closest” means minimizing the difference
in their values). What is the time complexity?

3. Describe a brute-force approach to find the closest pair of values in an unsorted array of numbers? What is the time
complexity?

4. Describe a brute-force approach to find the closest pair of values in a set of points in two dimensions (where “closest” means
minimizing the Euclidean distance). What is the time complexity?

5. Describe a divide-and-conquer approach to find the closest pair of values in a set of points in two dimensions. What is the
time complexity?

6. Suppose that in a Geometry exam, each of the m students in the class is given the same list of n cities around the United
States and is asked to specify the coordinates (longitude and latitude) of each city. A grade of A+ is given to the student
whose has the smallest total deviation of his specified coordinates from the actual coordinates. Describe how to determine
which student gets the A+. What is time complexity as a function of m and/or n?