﻿ 算法考试代考 CSC 445代写 algorithm代写 – 天才代写

# 算法考试代考 CSC 445代写 algorithm代写

2022-10-19 11:38 星期三 所属： 算法代写 浏览：443

## CSC 445 Final Exam

### Instructions

For this final exam, you have a choice of two formats: either

(1) do one of Problems (1) or (2) on divide-and-conquer and dynamic programming, and one of Problems (3) or (4) on greedy algorithms and amortized algorithms, for a total of two problems each worth 50 points; or

(2) do one of Problems (3) or (4) on greedy algorithms and amortized algorithms, for a total of one problem worth 100 points.

(If you do both Problems (1) and (2), or both Problems (3) and (4), only one problem from these pairs will be graded.)

Please be sure to indicate in your submission which problem numbers you are doing.

#### In general, when asked to design an algorithm, you should   算法考试代考

(i) describe your algorithm using prose and pictures,

(ii) argue that your algorithm is correct, and

(iii) analyze its running time.

Pseudocode is not required, but may aid the time analysis. When analyzing the time taken by a recursive algorithm, write down a recurrence and solve it.

When asked to design a dynamic programming algorithm, be sure to follow the four-part framework. You will be graded on each part of the framework.

When asked to design a greedy algorithm, be sure to argue that your algorithm is correct by proving a greedy augmentation lemma, that is used within a full correctness proof.

This midterm exam is take-home, open notes, open book, and closed friend. You may not use any resources other than your course notes and textbook.

Good luck!

### (1).(Divide and conquer) (50 points)   算法考试代考

Suppose we are given three sorted arrays A[1 : n], B[1 : n], and C[1 : n], where all 3n elements from the arrays are distinct, and an integer k where 1 k 3n. We would like to identify which element in these three arrays would be the kth smallest element in the merge of arrays A, B, and C into one sorted array.

Using divide and conquer, design an algorithm that, given the three separate sorted arrays A, B, and C as input, finds the kth smallest element in their merge in O(log k) time.

Be sure to argue that your algorithm is correct.

(Note: You cannot actually merge arrays A, B, and C, as that would take Θ(n) time, which exceeds the allowed time bound.)

### (2).(Dynamic programming) (50 points)   算法考试代考

Suppose you have an xy plot of points that you wish to approximate by a series of straight lines. Formally, given a collection of n points in the plane,

(x1, y1), (x2, y2), · · · (xn, yn),

where

x1 x2 ≤ · · · ≤ xn,

and an integer k 1, you wish to find a partition of the points into k consecutive runs, and fit a line to the points in each run, such that the sum of the errors of the least-squares lines through each of the runs is minimum.

You may assume that you have access to a function e(i, j) that finds a single line for points i, i+ 1, . . . , j that has the minimum least-squares error on these points, and that returns its corresponding error. This function e(i, j) runs in Θ(ji+1) time.

Using dynamic programming, design an algorithm that finds the best approximation of the n points by k lines in O(kn2 ) time.

Be sure to follow the four-step framework for designing dynamic programming algorithms. You will be graded on each part of the framework.

### (4).(Amortized algorithms) (50 or 100 points)   算法考试代考

Suppose we want to support a balanced search tree data structure that does automatic backup of the tree during search tree operations, according to the following scheme. After executing each search tree operation of Find, Insert, and Delete, we check whether at least n such operations on the tree have occurred since the last backup was performed, where n is the current size of the tree. If this many operations have occurred, a backup is performed when executing this tree operation by writing a copy of the entire tree after the operation to a file.

Show how to implement automatic backup of balanced search trees so that all tree operations, including those that cause backups to occur, run in O(log n) amortized time.

Use the accounting method for your analysis.