Describe in pseudocode an algorithm that takes as input a sequence of distinct numbers a0, a1, .....
Describe in pseudocode an algorithm that takes as input a sequence of distinct numbers a0, a1, ..., an and returns 1 if the sequence is ordered increasingly, -1 if the sequence is in decreasing order, and 0 otherwise.
What are the worse-case, best-case, and avergae-case of the algorithm? Analyze the running time in each of the three cases using asymptotic notation.
Homework Answers
Function isOrderedIncreasingly(arr)
BEGIN
// traverse the array
for i = 1 to arr.length
BEGIN
// if the i th element is greater than (i + 1) th element
If arr[i[ > arr[i + 1]
BEGIN
return -1
END
END
return 0
END
The tie complexity in all the 3 cases, worse-case, best-case, and avergae-case is
O(n)
It is because in all the 3 cases, the entire array is traversed which takes O(n) time.
Add Answer to:
Describe in pseudocode an algorithm that takes as input a sequence of distinct numbers a0, a1, .....
a. Use pseudocode to specify a brute-force algorithm that takes as input a list of n...
a. Use pseudocode to specify a brute-force algorithm that takes as input a list of n positive integers and determines whether there are two distinct elements of the list that have as their sum a third element of the list. That is, whether there exists i, j.k such that iヂj, i关k,j关k and ai + aj = ak. The algorithm should loop through all triples of elements of the list checking whether the sum of the first two is the third...
Given the following algorithm: Algorithnm Input: a1, a2,...,an, a sequence of numbers n, the length of the sequence x, a number Output: ?? i:- 1 While (x2 # a, and i < n) i+1 End-while If (x- - a)...
Given the following algorithm:
Algorithnm Input: a1, a2,...,an, a sequence of numbers n, the length of the sequence x, a number Output: ?? i:- 1 While (x2 # a, and i < n) i+1 End-while If (x- - a) Return(i) Return(-1) 3, -1, 2,9, 36,-7, 6,4 a) What is the correct output of the Algorithm with the following input: a1, a2,..an b) What is the asymptotic worst-case time complexity of the Algorithm?
Algorithnm Input: a1, a2,...,an, a sequence of numbers...
1) Design a greedy algorithm that solves the problem; describe your algorithm with clear pseudocode; and...
1) Design a greedy algorithm that solves the problem; describe your algorithm with clear pseudocode; and prove the time efficiency class of your algorithm: If x, y are two adjacent elements in a sequence, with x before y, we say that the pair x, y is in order when x <= y and the pair is out of order when x > y. For example, in the string “BEGGAR” the pair G, A are out of order, but all the...
ALGORITHM PROBLEM: A) Significant Inversions: We are given a sequence of n arbitrary but distinct real...
ALGORITHM PROBLEM: A) Significant Inversions: We are given a sequence of n arbitrary but distinct real numbers <a1 , a2 ,..., an>. We define a significant inversion to be a pair i < j such that ai > 2 aj . Design and analyze an O(n log n) time algorithm to count the number of significant inversions in the given sequence. [Hint: Use divide-&-conquer. Do the “combine” step carefully] B) The Maximum-Sum Monotone Sub-Array Problem: Input: An array A[1..n] of...
Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an...
Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an input sequence of numbers. MysteryAlgorithm Input: a1, a2....,an n, the length of the sequence. p, a number Output: ?? i != 1 j:=n While (i < j) While (i <j and a < p) i:= i + 1 End-while While (i <j and a 2 p) j:=j-1 End-while If (i < j), swap a, and a End-while Return( aj, a2,...,an) (a) Describe in English...
Question 1: Complexity Take a look at the following algorithm written in pseudocode: procedure mystery(a1, a2,...
Question 1: Complexity Take a look at the following algorithm written in pseudocode: procedure mystery(a1, a2, …, an: integer) i := 1 while (i < n and ai ≤ ai+1) i := i + 1 if i == n then print “Yes!” else print “No!” What property of the input sequence {an} does this algorithm test? What is the computational complexity of this algorithm, i.e., the number of comparisons being computed as a function of the input size n? Provide...
Coding for Python - The pattern detection problem – part 2: def calculate_similarity_list(data_series, pattern) Please do not use 'print' or 'input' statements. Context of the assignme...
Coding for Python - The pattern detection problem – part 2:
def calculate_similarity_list(data_series,
pattern)
Please do not use 'print' or 'input'
statements.
Context of the assignment is:
In this assignment, your goal is to write a Python program to
determine whether a given pattern appears in a data series, and if
so, where it is located in the data series. Please see attachments
below:
We need to consider the following cases:
Case 1 - It is possible that the given...
Hi i will give you a thumbs up if you do this problem correctly. Sorting Analysis Code and Essay ...
Hi i will give you a thumbs up if you do this problem correctly. Sorting Analysis Code and Essay Due: 4/22/2019(Monday) Introduction And now for something completely different. Different sorting algorithms are better for different size data sets. Other sorting algorithms are better for data sets of a specific type – for instance, data that is already ordered. In this assignment you will implement four different sorting algorithms and collect statistics for each of those algorithms while sorting multiple different...
10. Write a one-page summary of the attached paper? INTRODUCTION Many problems can develop in activated...
10. Write a one-page summary of the attached paper? INTRODUCTION Many problems can develop in activated sludge operation that adversely affect effluent quality with origins in the engineering, hydraulic and microbiological components of the process. The real "heart" of the activated sludge system is the development and maintenance of a mixed microbial culture (activated sludge) that treats wastewater and which can be managed. One definition of a wastewater treatment plant operator is a "bug farmer", one who controls the aeration...
a. Use pseudocode to specify a brute-force algorithm that takes as input a list of n positive integers and determines whether there are two distinct elements of the list that have as their sum a third element of the list. That is, whether there exists i, j.k such that iヂj, i关k,j关k and ai + aj = ak. The algorithm should loop through all triples of elements of the list checking whether the sum of the first two is the third...
Given the following algorithm:
Algorithnm Input: a1, a2,...,an, a sequence of numbers n, the length of the sequence x, a number Output: ?? i:- 1 While (x2 # a, and i < n) i+1 End-while If (x- - a) Return(i) Return(-1) 3, -1, 2,9, 36,-7, 6,4 a) What is the correct output of the Algorithm with the following input: a1, a2,..an b) What is the asymptotic worst-case time complexity of the Algorithm?
Algorithnm Input: a1, a2,...,an, a sequence of numbers...
Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an input sequence of numbers. MysteryAlgorithm Input: a1, a2....,an n, the length of the sequence. p, a number Output: ?? i != 1 j:=n While (i < j) While (i <j and a < p) i:= i + 1 End-while While (i <j and a 2 p) j:=j-1 End-while If (i < j), swap a, and a End-while Return( aj, a2,...,an) (a) Describe in English...
Coding for Python - The pattern detection problem – part 2:
def calculate_similarity_list(data_series,
pattern)
Please do not use 'print' or 'input'
statements.
Context of the assignment is:
In this assignment, your goal is to write a Python program to
determine whether a given pattern appears in a data series, and if
so, where it is located in the data series. Please see attachments
below:
We need to consider the following cases:
Case 1 - It is possible that the given...
Most questions answered within 3 hours.
-
Minitab Problem: Take the Lake Hume June rainfall data and find
use the processes outlined in...
asked 17 minutes ago -
X Company is trying to decide whether to continue using old
equipment to make Product A...
asked 18 minutes ago -
IN PYTHON ONLY !! Program 2: Re-work
program #5 (WeeklyHours) from the previous assignment such that...
asked 55 minutes ago -
The average length of time between arrivals at a turnpike
toll-booth is 26 seconds. What is...
asked 2 hours ago -
(a) A piston at 6.1 atm contains a gas that occupies a volume of
3.5 L....
asked 3 hours ago -
Please answer true or false. Words
cannot be changed or added in to make it true...
asked 3 hours ago -
An empty test tube weighs 15.923 grams. Then,
MgCl2•6H2O is added into the test tube. After...
asked 3 hours ago -
Assume memory access is 10 units of time and disk access is
10000 units of time....
asked 4 hours ago -
1. Are all good samples random?
2. Magazines often report surveys giving statistics such as “63%...
asked 4 hours ago -
Under all the various types of market structures, firms
must eventually earn some economic profits for...
asked 4 hours ago -
Consider the following fitness regime for a single locus trait
with two co-dominant alleles: w11 =...
asked 4 hours ago -
A large cable company reports the following.
80% of its customers subscribe to its cable TV...
asked 4 hours ago