Computer Science > QUESTIONS & ANSWERS > a1solutions - University of Manitoba COMP 3170 (All)

a1solutions - University of Manitoba COMP 3170

Document Content and Description Below

University of Manitoba COMP 3170, Winter 2018 Assignment 1 Due Date: Wednesday, January 24, at 8:00pm All problems are written problems; submit your solutions electronically as a PDF files via UMlearn. Most question ...

University of Manitoba COMP 3170, Winter 2018 Assignment 1 Due Date: Wednesday, January 24, at 8:00pm All problems are written problems; submit your solutions electronically as a PDF files via UMlearn. Most questions include an example accompanied with an answer which is aimed to provide some guideline on how the solutions should look like. Think of them as a tool for reviewing the material. Your solutions do not necessarily need to look like provided answers. There are 63 marks available. The assignment will be marked out of 60. Please read http://www.cs.umanitoba.ca/~kamalis/comp3170/info.pdf for guidelines on academic integrity. Throughout the assignment, all logarithms are based 2 logarithms, i.e., log x = log2 (x). Problem 1 [4+4+4+4+4=20 marks] Provide a complete proof of the following statements from first principles (i.e., using the original definitions of order notation). Ex.) 15n 3 + 10n 2 + 20 ∈ O(n 3 ) Consider M := 15 + 10 + 20 = 45 and n0 := 1. Then 0 ≤ 15n 3 + 10n 2 + 20 ≤ Mn3 for all n ≥ n0. a) n 2 + 3n 2 2+cos(n) ∈ O(n 2 ) For any value of n, we have cos(n) ≥ −1 and hence 3n 2 2+cos(n) ≤ 3n 2 . So f(n) ≤ n 2+3n 2 = 4n 2 . So, it suffices to have n0 ≥ 1 and M ≥ 4. b) 2n 2 (log n) ∈ Ω(n(log n) 2 ). We need to provide n0 and M s.t. for n > n0 we have 2n 2 log n ≥ Mn(log n) 2 , i.e., 2n ≥ M log n. Since n > log n for all positive integers, it suffices to have n0 ≥ 1 and M ≤ 2. c) 10n 2/(n − 10) ∈ Θ(n). Assume n0 ≥ 19. For n > n0, we have n/2 ≤ n − 10 < n, which implies 10n < 10n 2 n−10 ≤ 20n. So is suffices to define M1 ≤ 10 and M2 ≥ 20. d) 1396n ∈ o(n log n) Given any value of M, we should provide n0 so that 1396n < Mn log n, i.e,. 1396/M < log n. For this to hold, it suffices to have n > 2 1396/M. So it suffices to define n0 as max{1, 2 1396/M}. e) n n ∈ ω(n 20) Set n0 := 21 + M. Then, for n ≥ n0, we have n n = n n−20n 20 ≥ (21 + M) 1+Mn 20. Since (21 + M) 1+M > M, this shows

[Show More]

Last updated: 3 years ago

Preview 1 out of 4 pages

Buy Now

Instant download

Preview of a1solutions - University of Manitoba COMP 3170

Buy this Document to get the Full Access Instantly

Provided by Students Who Aced it

We Verify Document Content to Gurantee Accuracy

Buy Now

Report Copyright Violation

Reviews( 0 )

QUESTIONS & ANSWERS

$5.00

Instant download

79

0

Document information

Connected school, study & course

About the document

Uploaded On

Dec 14, 2022

Number of pages

4

Written in

All

QUESTIONS & ANSWERS

Seller

jimmydarts

Member since 5 years

80 Documents Sold

Reviews Received

4

2

1

1

5

Additional information

This document has been written for:

Computer Science

QUESTIONS & ANSWERS

Uploaded

Dec 14, 2022

Downloads

0

Views

79

Topic Tags

Related Subjects & Courses

Explore similar study resources and related concepts.

Recommended For You

Get more on QUESTIONS & ANSWERS »

Preview of Comp 3170 - Analysis of Algorithms & Data Structures Quiz 2 (WITH CORRECT ANSWERS)

Same Course Code Popular Match

$6

6 Pages

Comp 3170 - Analysis of Algorithms & Data Structures Quiz 2 (W...

Sep 12, 2026

Related document

Preview of Comp 3170 - Analysis of Algorithms & Data Structures Quiz 2 (WITH CORRECT ANSWERS)

Same Course Code Popular Match

$5

4 Pages

Comp 3170 - Analysis of Algorithms & Data Structures Quiz 2 (W...

Sep 28, 2026

Related document

Preview of a02-solutions - University of Manitoba COMP 3170

Same Course Code Popular Match

$5

6 Pages

a02-solutions - University of Manitoba COMP 3170

May 12, 2023

Related document

Preview of A6Solution - University of Manitoba COMP 3170

Same Course Code Popular Match

$4

3 Pages

A6Solution - University of Manitoba COMP 3170

May 12, 2023

Related document

Preview of quiz1-solutions - University of Manitoba COMP 3170

Same Course Code Popular Match

$5

3 Pages

quiz1-solutions - University of Manitoba COMP 3170

May 12, 2023

Related document

Preview of final-exam-version-3 - University of Manitoba COMP 3170

Same Course Code Popular Match

$5

6 Pages

final-exam-version-3 - University of Manitoba COMP 3170

Sep 28, 2026

Related document

Preview of midterm. Exam - Université de Saint-Boniface COMP 3170

Same Course Code Popular Match

$5

6 Pages

midterm. Exam - Université de Saint-Boniface COMP 3170

Sep 28, 2026

Related document

Preview of University of Manitoba COMP 3170, Winter 2018 Assignment 4 Solutions

Same Course Code Popular Match

$5

5 Pages

University of Manitoba COMP 3170, Winter 2018 Assignment 4 Sol...

Sep 20, 2026

Related document

Preview of WGU D075 OA EXAM NEWEST 2026 / WGU D075 WEB DEVEOPMENT FOUNDATIONS NEWEST 2026 ACTUAL E

Same Course

$13

14 Pages

WGU D075 OA EXAM NEWEST 2026 / WGU D075 WEB DEVEOPMENT FOUND...

Apr 01, 2026

Related document

Preview of CMU 10-601 Machine Learning Midterm Exam Solutions | Carnegie Mellon University

Same Course Popular Match

$11

17 Pages

CMU 10-601 Machine Learning Midterm Exam Solutions | Carnegie...

Apr 04, 2026

Related document

Preview of HIM 1103 FINAL EXAM with 100% verified solution

Same Course Popular Match

$10

16 Pages

HIM 1103 FINAL EXAM with 100% verified solution

Apr 03, 2026

Related document

Preview of AWS Certified Solutions Architect Associate SAA-C03 – 2026 Latest Practice Exams | 360 Q

Same Course

$17.5

43 Pages

AWS Certified Solutions Architect Associate SAA-C03 – 2026 La...

Apr 08, 2026

Related document

Preview of AWS Certified Solutions Architect Associate SAA-C03 2026 – Full Version Exam with 360 Qu

Same Course

$16

43 Pages

AWS Certified Solutions Architect Associate SAA-C03 2026 – Fu...

Apr 08, 2026

Related document

Preview of AWS Certified Solutions Architect Associate SAA-C03 2026 – Complete 360-Question Practic

Same Course

$16.5

38 Pages

AWS Certified Solutions Architect Associate SAA-C03 2026 – Co...

Apr 08, 2026

Related document

Preview of AWS Certified Solutions Architect – Associate (SAA-C03) 160 Exam Questions with Detailed

Same Course

$17

62 Pages

AWS Certified Solutions Architect – Associate (SAA-C03) 160 E...

Apr 08, 2026

Related document

Preview of INTEGRATED HUMAN SCIENCES EXAM 3 2026 COMPLETE QUESTIONS AND ANSWERS GRADED A+

Same Course

$10

20 Pages

INTEGRATED HUMAN SCIENCES EXAM 3 2026 COMPLETE QUESTIONS AND A...

Apr 03, 2026

Related document

Preview of INSY 1 UTA PRACTICE EXAMINATION 2026 QUESTIONS WITH ANSWERS GRADED A+

Same Course

$10

19 Pages

INSY 1 UTA PRACTICE EXAMINATION 2026 QUESTIONS WITH ANSWERS GR...

Apr 03, 2026

Related document

Preview of INSY 1 UTA FINAL TEST 2026 QUESTIONS WITH CORRECT ANSWERS GRADED A+

Same Course

$10

11 Pages

INSY 1 UTA FINAL TEST 2026 QUESTIONS WITH CORRECT ANSWERS GRAD...

Apr 03, 2026

Related document

Preview of INSY 1 UTA CERTIFICATION SCRIPT 2026 QUESTIONS WITH SOLUTIONS GRADED A+

Same Course

$10

16 Pages

INSY 1 UTA CERTIFICATION SCRIPT 2026 QUESTIONS WITH SOLUTIONS...

Apr 03, 2026

Related document

Preview of INSY 1 UTA ACTUAL EXAM PAPER 2026 QUESTIONS WITH ANSWERS GRADED A+

Same Course

$10

13 Pages

INSY 1 UTA ACTUAL EXAM PAPER 2026 QUESTIONS WITH ANSWERS GRADE...

Apr 03, 2026

Related document

More related documents below

Browse more QUESTIONS & ANSWERS

More From jimmydarts

View all jimmydarts's documents »

$5.00

Instant download

What is Scholarfriends

Scholarfriends.com Online Platform by Browsegrades Inc. 651N South Broad St, Middletown DE. United States.

Get to know us

About Us
Privacy Statement
Refund Policy
Terms and Conditions
Contact Us
Blog
HTML Sitemap
Sellers Directory (A–Z)

We are here to help

We're available through e-mail, Twitter, and live chat.
FAQ
Questions? Leave a message!

Follow us on

Instagram
Linktree
X (Twitter)

Useful links

Join our Subreddit

Solutions Manuals for Accounting, Business, Economics and Management Text Books. The Popular and the Latest.

Popular NURSING Test Banks

Sellers Directory (A–Z)

We accept

payment cards

Copyright © Scholarfriends · High quality services·