Practice Final Spring 2020

docx

School

University of Alberta *

*We aren’t endorsed by this school

Course

101

Subject

Computer Science

Date

Jan 9, 2024

Type

docx

Pages

Uploaded by DrCloverPorcupine11

Practice Final Spring 2020 Question 1: Trace through the following Python program, then fill in the following table, and answer the questions below: def printLists(alist): firstList = [] secList = [] thirdList = [] for i in range(len(alist)): current = alist[i] if current % 2 == 0: firstList.append(current) elif current % 3 == 0: secList.append(current) else: thirdList.append(current) print(firstList) print(secList) print(thirdList) myList = [1,2,3,4,5,7,9,12,13,15] printLists(myList) i current firstList secList thirdList 0 1 2 3 4 5 6 7 8 9 What are the final outputs of this program? What does each list contain by the end of the loop iterations?

Question 2: Consider this Binary Search algorithm that we have studied in class: def binarySearch(target, mylist): startIndex = 0 endIndex = len(mylist) -1 found = False while not found and startIndex <= endIndex: midpoint = (startIndex + endIndex)//2 if mylist[midpoint] == target: found = True else: if target < mylist[midpoint]: endIndex = midpoint -1 else: startIndex = midpoint +1 return found numList = [1,2,4,7,9,12,15,18,20] print(binarySearch(3,numList)) Now, let’s specifically look at the while loop conditions that run this algorithm. 1) Does the loop run when either or both conditions are True? 2) If target = 2, how many loop iterations will it take to find it? What’s the midpoint for this target? What makes the while loop stop running once the target has been located? 3) If the target value is not found in the list, what makes the algorithm stop instead of further attempting to search for a value that is not in the list? Specifically, which loop condition and how does it work? 4) If target = 21, what will be each of startIndex and endIndex when the algorithm completes running? Write the details of your computation and tracing.

Question 3: We have the following sorted list in ascending order: [1, 2, 4, 6, 7, 8, 10, 12, 15, 16, 17, 20] Now, consider the three sorting algorithms we have studied in this course, and answer the questions below: Bubble sort, Short Bubble sort, and Selection sort. 1) How many passes does each of these three algorithms perform over this list? Explain how you compute the number of passes for each algorithm. Bubble sort: Short Bubble sort: Selection sort: 2) Is any of these three algorithms able to detect that the list is sorted? If yes, which one and how does it detect that the list is sorted? 3) Finally, if you have the choice to run either one of these three algorithms, which one would you use to sort a semi-sorted list? Why?

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

Question 4: 1) Show on the following time complexity graph where each of the following algorithms falls: sequential search, binary search, bubble sort, short bubble sort, and selection sort. Note on the below graph that n is the data size (i.e., the list size), and Work describes the number of steps (i.e., the amount of work) each algorithm is performing. 2) Explain the difference between the time complexities (i.e., the efficiency) of binary search vs. sequential search. Which algorithm is more efficient and why? 3) Explain the difference between the time complexities (i.e., the efficiency) of selection sort vs. short bubble sort when the list is fully sorted. Which algorithm is more efficient and why?

Related Documents

ECSE_415_Project_Winter_2023 - Copy.pdf

ECSE_415_Assignment_3.pdf

Assignment_2_updated.pdf

ITEC 1000 midterm.docx

CMPUT 101 Practice MT2 Solutions.docx

Additional Practice Questions.docx

Assignment 2 - Module 3.docx

Assignment 3- Module 4.docx

Practice Final Exam from Fall 2019.docx

Chapter11 Part1.pdf

Chapter7Part3.pdf

CS 410 Binary to Assembly Activity .docx

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

EBK JAVA PROGRAMMING

Computer Science

ISBN:9781337671385

Author:FARRELL

Publisher:CENGAGE LEARNING - CONSIGNMENT

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

Microsoft Visual C#

Computer Science

ISBN:9781337102100

Author:Joyce, Farrell.

Publisher:Cengage Learning,

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Microsoft Visual C#
Computer Science
ISBN:9781337102100
Author:Joyce, Farrell.
Publisher:Cengage Learning,
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning