Exam1-Justin-Exam

pdf

School

University of Maryland, College Park *

*We aren’t endorsed by this school

Course

351

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by SargentClover11186

CMSC351 Fall 2022 Exam 1 Justin’s Section NAME (Neatly): UID (Neatly): Instructions: Please do all problems on the pages and in the spaces provided. This exam will be scanned into Gradescope and if your answers are not in the correct locations they will not be found or graded!

. THIS PAGE INTENTIONALLY LEFT BLANK! DO NOT USE!

1. Fill in the following as True or False . Any answers that are unclear will be marked as [10 pts] incorrect. Statement True/False Bubble Sort is best-case Θ(1). If f ( n ) ̸ = Ω( n 2 ) then f ( n ) = O ( n 2 ). Selection Sort is stable. Kadane’s Algorithm is Ω( n ). A Θ( n ) algorithm is always faster than a Θ( n 2 ) algorithm. 2. Suppose Kadane’s algorithm is run on a list of length 7. The values of maxendingati are given [5 pts] in the table below. Fill in the values of maxoverall . i maxendingati maxoverall 0 4 1 1 2 3 3 -1 4 8 5 13 6 12

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

3. Prove the following by the definition: [15 pts] n 2 lg n + lg n − n + 100 lg 2 n = O ( n 2 lg n ) Solution:

4. Prove the following by the definition: [15 pts] If f ( n ) = Ω(2 n + 1) then f ( n ) = Ω(100 n + 42). Solution:

5. Here is the pseudocode for Bubble Sort: for i = 0 to n-2 for j = 0 to n-i-2 if A[j] > A[j+1] swap A[j] and A[j+1] end end end Consider the following list: [1,2,7,4,5,6,3,8,9,10] (a) How many > comparisons will be made? Show work and simplify your answer. [15 pts] Solution: (b) How many swaps will be made? [5 pts] Solution:

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

6. Here is the pseudocode for Insertion Sort: for i = 1 to n-1 key = A[i] j = i-1 while j >= 0 and key < A[j] A[j+1] = A[j] j = j - 1 end A[j+1] = key end (a) Suppose Insertion Sort is run on a list of length 10 but crashes right after the i = 4 [10 pts] iteration ends. Only one of the following could be A at this point. Explain which one and why the other two could not. (i) [6,8,9,10,1,2,3,4,5,7] (ii) [3,7,8,2,1,10,6,5,4,9] (iii) [1,2,3,5,4,6,7,8,9,10] Solution: (b) Suppose the line A[j+1] = A[j] takes time C and nothing else takes any time at all. If [15 pts] a random permutation of the list [1,2,3] is chosen and sorted, with each equally likely, how long do we expect the code to take? Solution:

7. Here is the pseudocode for Selection Sort: [10 pts] for i = 0 to n-2 minindex = i for j = i+1 to n-1 if A[j] < A[minindex] minindex = j end end swap A[i] with A[minindex] end Give an example of a list with three elements which demonstrates that Selection Sort is unstable and explain. Solution:

Related Documents

140_PMC_Lab80.docx

Assignment-2.docx

Defining Computer Science and Information Technology-1.docx

Exam 5- Modules 14-16.docx

CCNA 2 EXAM MODULE 5-6.docx

RTI+Case+Study+-+Jamie+Holly.pdf

GRA 470 - Site Selection and Website Evaluation - Pizzeck.docx

Exam3-PlanD-Solutions.pdf

Exam2-Herve-Solutions.pdf

doc 6.docx

ITN 260 Lab 1 fa22 (turn in).docx

ITN260 Lab 3 FA22.doc

Recommended textbooks for you

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE

Computer Science

ISBN:9780357392676

Author:FREUND, Steven

Publisher:CENGAGE L

Programming with Microsoft Visual Basic 2017

Computer Science

ISBN:9781337102124

Author:Diane Zak

Publisher:Cengage Learning

Np Ms Office 365/Excel 2016 I Ntermed

Computer Science

ISBN:9781337508841

Author:Carey

Publisher:Cengage

Oracle 12c: SQL

Computer Science

ISBN:9781305251038

Author:Joan Casteel

Publisher:Cengage Learning

CMPTR

Computer Science

ISBN:9781337681872

Author:PINARD

Publisher:Cengage

SEE MORE TEXTBOOKS

Recommended textbooks for you

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE
Computer Science
ISBN:9780357392676
Author:FREUND, Steven
Publisher:CENGAGE L
Programming with Microsoft Visual Basic 2017
Computer Science
ISBN:9781337102124
Author:Diane Zak
Publisher:Cengage Learning
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:9781337508841
Author:Carey
Publisher:Cengage
Oracle 12c: SQL
Computer Science
ISBN:9781305251038
Author:Joan Casteel
Publisher:Cengage Learning
CMPTR
Computer Science
ISBN:9781337681872
Author:PINARD
Publisher:Cengage