![Your task is to design algorithms to solve the following problems. For full credit, your algorithm must run in logarithmic time. 1.1 Root-finding Given a number n 1 and a (user-specified) error tolerance e, you want to approximate the square root of n to within error tolerance e. Specifically, you want to return an z s Vn that satisfies nl s e. For example, to compute the square root of n with e 0.01, an acceptable answer would be z 1.414 because 1.414 1.999396 Note that 1.415 is also acceptable, as 1.415 2.002225, but you only need to return a single answer Assume that you cant perform a arithmetic functions other than addition, subtraction, multiplication and division. 1. Write pseudocode for an efficient algorithm to solve this problem 2. Briefly justify a good asymptotic bound on the runtime of your algorithm in terms of n (i.e., give a runtime in terms of n assuming a fixed value of e) 3. BONUS: Provide an asymptotic bound on the runtime of your algorithm in terms of e, for a fixed value of n. Prove your result 1.2 Array-chopping An arithmetic array is one whose elements form an arithmetic sequence, in order i.e., theyre arrays of the form where A has length n (for n 2). Youre given an arithmetic array with one element missing from somewhere in the middle (i.e its not the first or last element thats been removed For example, the missing number in 3, 6, 12, 15, 18 is 9. The missing number in L1, 15, 22, 29, 36] is 8 1. Describe a way to calculate c in constant time 2. Design an algorithm to efficiently find the missing number in the array 3. Briefly justify a good asymptotic runtime of your algorithm.](http://img.homeworklib.com/questions/272e0530-8f83-11eb-a134-5b301a36323f.png?x-oss-process=image/resize,w_560)
Homework Answers
Add Answer to:
Your task is to design algorithms to solve the following problems. For full credit, your algorithm...
For each problems segment given below, do the following: Create an algorithm to solve the problem...
For each problems segment given below, do the following: Create an algorithm to solve the problem Identify the factors that would influence the running time, and which can be known before the algorithm or code is executed. Assign names (such as n) to each factor. Identify the operations that must be counted. You need not count every statement separately. If a group of statements always executes together, treat the group as a single unit. If a method is called, and...
Write a recurrence relation describing the worst case running time of each of the following algorithms,...
Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution by using substitution or a recursion tree. You may NOT use the Master Theorem. Simplify your answers, expressing them in a form such as O(nk) or (nklog n) whenever possible. If the algorithm takes exponential time, then just give an exponential lower bound using the 2 notation. function...
6. Consider the following algorithm, where P is an array containing random numbers. The function swap(v1,v2)...
6. Consider the following algorithm, where P is an array containing random numbers. The function swap(v1,v2) will swap the values stored in the variables v1 and v2. Note that % is the modulus operation, and will return the integer remainder r of a/b, i.e., r-a%b Require: Array P with n > 0 values 1: i-1, j-n-l 2: while i<=j do for a=i to j by i do 4: 5: 6: 7: if Pla>Pat 11 and Pla]%2--0 then swap(Plal, Pla+1l) end...
Exercise 1 Use Top-Down Design to “design” a set of instructions to write an algorithm for...
Exercise 1 Use Top-Down Design to “design” a set of instructions to write an algorithm for “travel arrangement”. For example, at a high level of abstraction, the algorithm for “travel arrangement” is: book a hotel buy a plane ticket rent a car Using the principle of stepwise refinement, write more detailed pseudocode for each of these three steps at a lower level of abstraction. Exercise 2 Asymptotic Complexity (3 pts) Determine the Big-O notation for the following growth functions: 1....
1. (10 pts total) For parts (1a) and (1b), justify your answers in terms of deterministic...
1. (10 pts total) For parts (1a) and (1b), justify your answers in terms of deterministic QuickSort, and for part (1c), refer to Randomized QuickSort. In both cases, refer to the versions of the algorithms given in the lecture notes for Week 3. (a) (3 points) What is the asymptotic running time of QuickSort when every element of the input A is identical, i.e., for 1 ≤ i,j ≤ n, A[i] = A[j]? Prove your answer is correct. (b) (3...
Python. Just work in the def sierpinski. No output needed. Will give thumbs up for any attempt beginning this code. Your task is to implement this algorithm in Python, returning a random collection of...
Python. Just work in the def sierpinski. No output needed. Will
give thumbs up for any attempt beginning this code.
Your task is to implement this algorithm in Python, returning a random collection of inum-100, 000 points. You should then plot the points to see the structure. Please complete the following function: def sierpinski (po, v, f, inum) The four arguments are ·po the initial point. You may assume this is the origin, i.e., po = [0, 0] . v:...
Psuedocode works! DP is dynamic programming for this algorithm Problem 4.2. (Difficulty 3) Seam carving is...
Psuedocode works! DP is dynamic programming for this
algorithm
Problem 4.2. (Difficulty 3) Seam carving is a real-world application of DP for content- aware image resizing. The simplest way to reduce the size of an image is cropping and scaling, i.e. cutting out parts of the image and scaling down the size. However, cropping leaves visible crop lines of incontinuity while scaling reduces the details of the image. We would like to intelligently reducing the size while accounting for the...
This C++ Program consists of: operator overloading, as well as experience with managing dynamic memory allocation...
This C++ Program consists of: operator overloading, as well as experience with managing dynamic memory allocation inside a class. Task One common limitation of programming languages is that the built-in types are limited to smaller finite ranges of storage. For instance, the built-in int type in C++ is 4 bytes in most systems today, allowing for about 4 billion different numbers. The regular int splits this range between positive and negative numbers, but even an unsigned int (assuming 4 bytes)...
Use the C programming language to complete #include <stdio.h> #include <stdlib.h> #include <float.h> // Declare Global...
Use the C programming language to complete
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
// Declare Global variables here.
void array_stats() {
// Insert your solution here.
}
#include <stdlib.h>
#include <time.h>
int main() {
// Simulate the test setup process.
srand( time( NULL ) );
for ( int i = 0; i < 32; i++ ) {
val[i] = rand();
}
val_count = rand();
val_mean = rand();
val_min = rand();
val_max = rand();
// Call submitted code.
array_stats();
// Display...
For each problems segment given below, do the following: Create an algorithm to solve the problem Identify the factors that would influence the running time, and which can be known before the algorithm or code is executed. Assign names (such as n) to each factor. Identify the operations that must be counted. You need not count every statement separately. If a group of statements always executes together, treat the group as a single unit. If a method is called, and...
Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution by using substitution or a recursion tree. You may NOT use the Master Theorem. Simplify your answers, expressing them in a form such as O(nk) or (nklog n) whenever possible. If the algorithm takes exponential time, then just give an exponential lower bound using the 2 notation. function...
6. Consider the following algorithm, where P is an array containing random numbers. The function swap(v1,v2) will swap the values stored in the variables v1 and v2. Note that % is the modulus operation, and will return the integer remainder r of a/b, i.e., r-a%b Require: Array P with n > 0 values 1: i-1, j-n-l 2: while i<=j do for a=i to j by i do 4: 5: 6: 7: if Pla>Pat 11 and Pla]%2--0 then swap(Plal, Pla+1l) end...
Python. Just work in the def sierpinski. No output needed. Will
give thumbs up for any attempt beginning this code.
Your task is to implement this algorithm in Python, returning a random collection of inum-100, 000 points. You should then plot the points to see the structure. Please complete the following function: def sierpinski (po, v, f, inum) The four arguments are ·po the initial point. You may assume this is the origin, i.e., po = [0, 0] . v:...
Psuedocode works! DP is dynamic programming for this
algorithm
Problem 4.2. (Difficulty 3) Seam carving is a real-world application of DP for content- aware image resizing. The simplest way to reduce the size of an image is cropping and scaling, i.e. cutting out parts of the image and scaling down the size. However, cropping leaves visible crop lines of incontinuity while scaling reduces the details of the image. We would like to intelligently reducing the size while accounting for the...
Use the C programming language to complete
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
// Declare Global variables here.
void array_stats() {
// Insert your solution here.
}
#include <stdlib.h>
#include <time.h>
int main() {
// Simulate the test setup process.
srand( time( NULL ) );
for ( int i = 0; i < 32; i++ ) {
val[i] = rand();
}
val_count = rand();
val_mean = rand();
val_min = rand();
val_max = rand();
// Call submitted code.
array_stats();
// Display...
Most questions answered within 3 hours.
-
4. Without doing any calculations, predict whether the observed
∆T would increase, decrease or remain the...
asked 1 hour ago -
Based on the range, which of the following sets of scores has
the greatest variability? 3,...
asked 2 hours ago -
Ripples in a pond travel at a velocity of 3 m/s with one peak
passing a...
asked 2 hours ago -
A man stands on the roof of a building of height 13.0 mm and
throws a...
asked 2 hours ago -
The extent to which assets are financed by borrowed funds and
other liabilities is indicated by:...
asked 3 hours ago -
Explain in detail
Germany is the fifth largest economy
explain what goods and services Germany specializes...
asked 3 hours ago -
The density of platinum is 21.45 g/mL. If a cube of platinum
with a mass of...
asked 3 hours ago -
Accounts Receivable
Sales
A/R Posting
Extended Sales Invoice
Packing Slip
Compare invoice to packing slip 2...
asked 3 hours ago -
Michaella, age 23, is a full-time law student and is claimed by
her parents as a...
asked 3 hours ago -
Why are polymers not typically casted into products?
asked 3 hours ago -
When rolling a die 129 times, what is the probability of rolling
a 6 no more...
asked 4 hours ago -
4. A call option currently sells for $7.75. It has a strike
price of $85 and...
asked 4 hours ago