Computer Science > SOLUTIONS MANUAL > A6Solution - University of Manitoba COMP 3170 (All)

A6Solution - University of Manitoba COMP 3170

Document Content and Description Below

COMP 3170 Assignment 6 Helen Cameron Due: Friday 29 June 2018 at 4:30 p.m. Questions and Solutions 1. Consider the decision tree corresponding to insertion sort working on inputs of size 3 that we looked at in class ...

COMP 3170 Assignment 6 Helen Cameron Due: Friday 29 June 2018 at 4:30 p.m. Questions and Solutions 1. Consider the decision tree corresponding to insertion sort working on inputs of size 3 that we looked at in class. The basic operation vi < vj represents the comparison siftVal < nums[j]. (a) Which result (true or false) for that comparison represents the case when insertion sort is going to move one position to the right (in the array) a value that is larger than siftValue? Solution: True. Explanation: (See Slide 20 in 04.2LowerBounds-SortingProof.pdf.) If the comparison shows that siftVal < nums[j], then nums[j] has to be moved one position to the right in the array to make room for a smaller siftVal. Thus, “true” is the result for that comparison that represents the case when insertion sort is going to move one position to the right (in the array) a value that is larger than siftValue. (b) Consider all decision trees that correspond to the insertion sort code used in class working on inputs of size 3, size 4, size 5, . . . . Using your answer to the previous question, which path in all those decision trees corresponds to insertion sort doing the most moves to the right? Solution: The path from the root to the leftmost leaf represents every basic operation (siftVal < nums[j]) performed by insertion sort having the result true, making insertion sort move another value to the right. 2. Consider the following comparison-based sorting algorithm called upDownSort: 1. void upDownSort( int[] nums ) { 2. int lo = 0, hi = nums.length-1; 3. while ( hi - lo > 0 ) { // at least 2 values remain to sort 4. swap( nums, hi, goingUp( nums, lo, hi ) ); 5. hi--; 6. swap( nums, lo, goingDown( nums, lo, hi ) ); 7. lo++; 8. } // end while 9. } // end sort It uses the following method three methods: First, method goingUp, which returns an index: 1. int goingUp( int[] nums, int lo, int hi ) { 2. int resultIndex = lo; 3. for ( int i = lo+1; i <= hi; i++ ) 4. if ( nums[ resultIndex ] <

[Show More]

Last updated: 3 years ago

Preview 1 out of 3 pages

Buy Now

Instant download

Preview of A6Solution - 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 )

SOLUTIONS MANUAL

$4.00

Instant download

172

0

Document information

Connected school, study & course

About the document

Uploaded On

Dec 14, 2022

Number of pages

3

Written in

All

SOLUTIONS MANUAL

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

SOLUTIONS MANUAL

Uploaded

Dec 14, 2022

Downloads

0

Views

172

Document Keyword Tags

Recommended For You

Get more on SOLUTIONS MANUAL »

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 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 a1solutions - University of Manitoba COMP 3170

Same Course Code Popular Match

$5

4 Pages

a1solutions - University of Manitoba COMP 3170

Aug 06, 2026

Related document

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...

Aug 06, 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...

Aug 06, 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...

Aug 06, 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 Carnegie Mellon University final_solutions

Same Course Popular Match

$11

16 Pages

CMU 10-601 Machine Learning Carnegie Mellon University final_...

Apr 04, 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 Solutions Manual for Business Statistics Communicating with Numbers, 4th Edition by Sanjiv

Same Category Popular Match

$24

512 Pages

Solutions Manual for Business Statistics Communicating with Nu...

Apr 26, 2026

Related document

Preview of Essentials of Econometrics, 5th Edition by Damodar Gujarati, Dawn Porter | Solutions Manua

Same Category Popular Match

$25

228 Pages

Essentials of Econometrics, 5th Edition by Damodar Gujarati, D...

Apr 26, 2026

Related document

Preview of Analyzing Politics Rationality, Behavior, and Institutions, 2e Kenneth, Shepsle (Solutions

Same Category Popular Match

$26

47 Pages

Analyzing Politics Rationality, Behavior, and Institutions, 2e...

Apr 26, 2026

Related document

Preview of INSY 1 UTA COMPREHENSIVE STUDY GUIDE 2026 FULL QUESTIONS AND SOLUTIONS GRADED A+

Same Course

$10

39 Pages

INSY 1 UTA COMPREHENSIVE STUDY GUIDE 2026 FULL QUESTIONS AND S...

Apr 03, 2026

Related document

Preview of ITE 152 EXAM 1, PRACTICE EXAM AND STUDY GUIDE NEWEST 2026 ACTUAL EXAM 140 QUESTIONS AND

Same Course

$13

28 Pages

ITE 152 EXAM 1, PRACTICE EXAM AND STUDY GUIDE NEWEST 2026 AC...

Apr 01, 2026

Related document

Preview of ITE 152 EXAM 2, PRACTICE EXAM AND STUDY GUIDE NEWEST 2026 ACTUAL EXAM 100 QUESTIONS AND

Same Course

$13

22 Pages

ITE 152 EXAM 2, PRACTICE EXAM AND STUDY GUIDE NEWEST 2026 AC...

Apr 01, 2026

Related document

Preview of WGU C777 FINAL PAPER 2026 FULL Q&A STUDY GUIDE GRADED A+

Same Course

$10

8 Pages

WGU C777 FINAL PAPER 2026 FULL Q&A STUDY GUIDE GRADED A+

Apr 01, 2026

Related document

Preview of AQA A-LEVEL COMPUTER SCIENCE STUDY GUIDE EXAM 2026 COMPLETE QUESTIONS WITH SOLUTIONS GRADE

Same Course

$10

23 Pages

AQA A-LEVEL COMPUTER SCIENCE STUDY GUIDE EXAM 2026 COMPLETE QU...

Mar 29, 2026

Related document

More related documents below

Browse more SOLUTIONS MANUAL

More From jimmydarts

View all jimmydarts's documents »

$4.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·