Description

1 attachmentsSlide 1 of 1attachment_1attachment_1

Unformatted Attachment Preview

Krzysztof Brzȩczyszczykiewicz SID 834322002

Venkataratnam Narasimha Rattaiah SID 854377890

CS 111 ASSIGNMENT 127

due Friday, February 13

Problem 1: Consider a sequence defined recursively as a0 = 4, a1 = 9, and an = an−1 + 3an−2 for

n ≥ 2. Prove that an = O(2.5n ).

Solution 1: We first prove by induction that an ≤ 4(2.5)n is true.

Base step: In the base step we verify the inequality for n = 0, 1. For n = 0 we have a0 = 4 and

4(2.5)0 = 4, so a0 ≤ 4(2.5)0 . For n = 1 we have a1 = 9 and 4(2.5)1 = 10, so a1 ≤ 4(2.5)1 .

Inductive step: The inductive hypothesis is that an ≤ 4(2.5)n is true for n = 0, 1, …, k, where k ≥ 1.

To complete the inductive step, we need to show that ak+1 ≤ 4(2.5)k+1 .

Since ak ≤ 4(2.5)k and ak−1 ≤ 4(2.5)k−1 holds, we have

ak+1 = ak + 3ak−1

≤ 4(2.5)k + 3 · 4(2.5)k−1

≤ 4(2.5)k−1 (2.5 + 3)

≤ 4(2.5)k−1 (2.5)2

≤ 4(2.5)k+1 .

That is, we have shown that if the inductive hypothesis is true, then ak+1 ≤ 4(2.5)k+1 is also true.

This complete the inductive step.

We thus have an ≤ 4(2.5)n | for all n ≥ 0. Therefore an = O(2.5n ), completing the proof.

Problem 2: Suppose we have three sets, A1 , A2 , A3 with the following properties:

(a) |A2 | = 2|A1 |, |A3 | = 4|A1 |,

(b) |A1 ∩ A2 | = 2, |A1 ∩ A3 | = 2, |A2 ∩ A3 | = 5,

(c) |A1 ∩ A2 ∩ A3 | = 1

(d) |A1 ∪ A2 ∪ A3 | = 27.

Use the inclusion-exclusion formula to determine the number of elements in A1 ∪ A1 ∪ A3 . Show

your work.

Solution 2: We have

|A1 ∪ A2 ∪ A3 | = |A1 | + |A2 | + |A3 | − |A1 ∩ A2 | − |A1 ∩ A3 | − |A2 ∩ A3 | + |A1 ∩ A2 ∩ A3 |

27 = |A1 | + |A2 | + |A3 | − 2 − 2 − 5 + 1

|A1 | + |A2 | + |A3 | = 35

|A2 | = 2|A1 |

|A3 | = 4|A1 |

1

By solving the above equations, we get the cardinalities of A1 , A2 and A3 :

|A1 | = 5

|A2 | = 10

|A3 | = 20

Problem 3: We are given an array A[0, …, n−1] that contains distinct numbers sorted in increasing

order, that is A[i] < A[i + 1] for all i = 0, ..., n − 2. Consider the algorithm below, described in
pseudo-code
1 i
Purchase answer to see full
attachment
Tags:
IT
CSS
discrete mathematics
User generated content is uploaded by users for the purposes of learning and should be used following Studypool's honor code & terms of service.

## Reviews, comments, and love from our customers and community:

This page is having a slideshow that uses Javascript. Your browser either doesn't support Javascript or you have it turned off. To see this page as it is meant to appear please use a Javascript enabled browser.