Assign 1 2015 PDF

Preview

Summary

Assignment 1...

Description

2

Swansea University Computer Science

Questions

1. Give Θ-expressions which are as simple as possible, and state the rules you applied:

CS-270 Algorithms 2015/16 Coursework I Oliver Kullmann, 22/10/2015 Deadline: 4/11/2015

4n8

=

Θ(?)

2n6 + 8n3 + n7

=

Θ(?)

n

4·2 +n = Θ(?) √ 5 n + log4 (n) = Θ(?)

• See https://science.swansea.ac.uk/ intranet/help/students/coursework • The possible marks for individual exercises sum up to 115; results over 100 are capped. • Please enter the answers into this coursework sheet, and add any drafts you have used. The complete coursework must be written in its entirety by you. If you use any sources other than the course-book, then you must clearly cite it, and you need to explain how you used it. Since we cannot return your coursework to you, please keep a copy for yourself.

1

A framework simplifications

for

Θ-

As a kind of reminder and reference, here are the basic rules for Θ-simplifications, where a, b stand for arbitrary terms, and n ≥ 1: (EQ) If a = b, then a = Θ(b). For example (n + 5)2 = θ (n2 + 10n + 25). (IQ) If a ≤ b, then a = O(b). E.g., 2 n = O(3n ). (F) For a (constant!) factor α > 0, we have α · a = Θ(a). E.g., 5n2 = Θ(n2 ). (LO) Lower-order terms: if a = O(b), then a + b = Θ(b). E.g., n2 + n3 = Θ(n3 ). (L1) logb (n) = Θ(lg(n)) for any (constant) b > 1. E.g., log10 (n) = Θ(lg(n)). α

(L2) lg(n) = O(n ) for any (constant) α > 0. E.g., lg(n) = O(n2 ). (P) For (constant) α ≥ β > 0, we have nβ ≤ nα . E.g., n2 = O(n3 ). (E) nα = O(β n ) for any (constant) α > 0, β > 1. E.g., n3 = O(2n ).

1000

(n + 2)4

=

Θ(?)

lg(n) + 3n + n3

=

Θ(?) [30 marks]

2. After Θ-simplifications one sees, that each of the following expression is either (asymptotically) a logarithm (L), a power (P), or an exponential (E) — say which applies: (a) log10 n + 5 lg n (b) 1.6n (c) 10n + n2 √ (d) 4 n + log n (e)

2n 101000

+ n5 + lg n [20 marks]

3. Mark each of the following assertions “true” or “false”: (a) All logarithms are asymptotically equal. (b) Some exponentials are asymptotically smaller than some powers. (c) Every power is asymptotically smaller than every exponential. (d) Some powers are asymptotically smaller than some logarithms. (e) Every logarithm is asymptotically smaller than any power. (f) All powers are asymptotically equal. (g) All exponentials are asymptotically equal. For each correct answer you get 5 marks. [35 marks] 4. Solve the following recurrences, using the simplified Master Theorem, where you need to show the (small) computation, and state the case applied:

3

(a) T (n) = 16T (n/2) + n4 . 4

(b) T (n) = 4T (n/2) + n . (c) T (n) = T (n/2) + T (n/2) + 2. (d) T (n) = 5T (n/3) + n. (e) T (n) = 7T (n/3) + n2 . (f) T (n) = 7T (n/7) + n2 . [30 marks]

Additional questions, for you to practice

1. Write down the recurrence for a variant of MergeSort, where the array is subdivided into three equal parts, solve it, and compare it with the standard procedure — is it faster? 2. Consider the algorithmic problem to decide whether for an array of integers all numbers are equal (input array A, output true if all elements of A are equal, false otherwise). (a) Design a divide-and-conquer algorithm to solve this problem. (b) Analyse your algorithm by the (simplified) Master Theorem, and state its run-time in terms of big-Oh. (c) Is your algorithm best-possible? (d) Can you come up with a direct (simple) algorithm?...