联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Web作业Web作业

日期:2024-08-12 06:29

compX123

Tutorial 1: Analysis

s2 2024

Warm-up

Problem 1. Sort the following functions in increasing order of asymptotic growth

Problem 2. Sort the following functions in increasing order of asymptotic growth

Problem 3. Consider the following pseudocode fragment.

1: function printFive(n)

2: for i 1; i 5; i++ do

3: Print a single character ’n’

Using the O-notation, upperbound the running time of printFive.

Problem 4. Consider the following pseudocode fragment.

1: function stars(n)

2: for i 1; i n; i++ do

3: Print ’*’ i times

a) Using the O-notation, upperbound the running time of stars.

b) Using the Ω-notation, lowerbound the running time of stars to show that your up- perbound is in fact asymptotically tight.

Problem 5. Recall the problem we covered in lecture: Given an array A with n entries, find 0 ≤ i ≤ j < n maximizing A[i] + · · · + A[j].

Prove that the following algorithm is incorrect: Compute the array B as described in the lectures. Find i minimizing B[i], find j maximizing B[j + 1], return (i, j).

Come up with the smallest example possible where the proposed algorithm fails.

Problem solving

Problem 6. Given an array A consisting of n integers, we want to compute the upper triangle matrix C where

for 0 ≤ i ≤ j < n. Consider the following algorithm for computing C:

1: function summing up(A)

2: C new matrix of size(A) by size(A)

3: for i 0; i < n; i++ do

4: for j i; j < n; j++ do

5: Compute average of entries A[i : j]

6: Store result in C[i, j]

7: return C

a) Using the O-notation, upperbound the running time of summing-up.

b) Using the Ω-notation, lowerbound the running time of summing-up.

Problem 7. Come up with a more efficient algorithm for computing the above matrix for 0 i j < n. Your algorithm should run in O(n2 ) time.

Problem 8. Give a formal proof of the transitivity of the O-notation.  That is, for function f , g, and h show that iff (n) = O(g(n)) and g(n) = O(h(n)) thenf (n) = O(h(n)).

Problem 9. Using O-notation, show that the follow snippet of code runs in O(n2 ) time. As an extra challenge, it can be shown that it actually runs in O(n) time.

1: function algorithm(n)

2: j 0

3: for i 0; i < n; i++ do

4: while j 1 and [condition that can be checked in O(1) time] do

5: j j 1

6: j j + 1

7: return j


Problem 10. Given a string (which you can see as an array of characters) of length n, determine whether the string contains k identical consecutive characters. You can assume that 2 ≤ k ≤ n. For example, when we take k = 3, the string ”abaaab” contains three consecutive a’s and thus we should return true, while the string ”abaaba” doesn’t contain three consecutive characters that are the same.

Your task is to design an algorithm that always correctly returns whether the input string contains k identical consecutive characters. Your solution should run in O(n) time. In particular, k isn’t a constant and your running time shouldn’t depend on it.


Problem 11. Given an array with n integer values, we would like to know if there are any duplicates in the array. Design an algorithm for this task and analyze its time complexity.




版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp