当前位置:天才代写 > 其他代写 > 计算机代写理论题笔试刷题算法代写601.433/633 Introduction to Algorithms Fall 2018

计算机代写理论题笔试刷题算法代写601.433/633 Introduction to Algorithms Fall 2018

2018-09-18 08:00 星期二 所属: 其他代写 浏览:1194

601.433/633 Introduction to Algorithms Fall 2018


Homework  #1 Due:  September 13, 2018, 1:30pm

 

Remember: you may work in groups of up to three people, but must write up your solution entirely on your own. Collaboration is limited to discussing the problems – you may not look at, compare, reuse, etc. any text from anyone else in the class. Please include your list of collaborators on the first page of your submission. You may use the internet to look up formulas, definitions, etc., but may not simply look up the answers online.


Please include proofs with all of your answers, unless stated otherwise.

Asymptotic Notation (40 points)

 

For each of the following statements explain if it true or false and prove your answer. The base of log is 2 unless otherwise specified, and ln is loge.

(a) log(n70) = O(log(n1/2))

(b) 2n = Θ(en)

(c) 1000(n log2 n + 1 n2) = Θ(n2)

(d) 3n = Θ(3(n4))

(e) n cos n = Θ(n)

(f) Let f, g be positive functions. Then f (n) + g(n) = Ω(min(f (n), g(n)))

(g) Let f, g be positive functions, and let g(n) = o(f (n)). Then f (n) + g(n) = Θ(f (n))

(h) 25 log n = O(n2)

 

Recurrences (35 pts)

 

Solve the following recurrences, giving your answer in Θ notation. For each of them you may assume T (x) = 1 for x 5 (or if it makes the base case easier you may assume T (x) is any other constant for x 5). Justify your answer (formal proof not necessary, but recommended).

(a) T (n) = 3T (n 5)

(b) T (n) = n2/3T (n1/3) + n (c) T (n) = 4T (n/3) + n

(d) T (n) = 4T (n/4) + n log4 n (e) T (n) = T (n  3) + 5


Basic Proofs (25 pts)

 

(a) Let A, B, C, D be sets. Prove that

 

(A B) (C D) = (A C) (B C) (A D) (B D)

(b) There are 130 students registered for this class. Prove that there are at least 11 students who were all born in the same month.


(c) Prove by induction that Σn

(2i 1) = n2 for all positive integers n.

R代写 C语言代写 java代写 经济代写 金融代写 数据库代写
理论题代写 数学代写 助攻考试 python代写 网页代写 网课代修

 

    关键字:

天才代写-代写联系方式