Practice Final Exam from Fall 2019

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

This practice final exam has 6 questions, and is representative of questions on a former final exam from Fall 2019 (the last in-person semester pre-pandemic). This is a closed book exam. No calculators or any other electronic devices allowed. Question 1 / 10 Question 2 / 10 Question 3 / 10 Question 4 / 10 Question 5 / 10 Question 6 / 10 Total / 60 1

Question 1 : (10 marks) 1) Convert the following binary number to decimal: (1 mark) 10101 = 2) Convert the following decimal number to binary: (1 mark) 18 = 3) Complete the following binary multiplication: (3 marks) 1 1 1 1 x 1 0 1 4) Using the sum of products, derive the expression E from the following truth table: (5 marks) P R E 0 0 0 0 1 1 1 0 1 1 1 0 E = 2

Question 2 : (10 marks) Complete the following Python program so that it finds and prints the smallest value in the list. The output should be: The smallest value = 2 def findMin (alist): min = alist[0] for __________________________ : if _____________________: ___________________ return _____________ mylist = [8,5,2,3,6,4] print("The smallest value =", findMin(mylist)) Complete the following Python program so that it finds and prints the index of the smallest value in the list. The output should be: Min index = 6 def findMinIndex (alist): min = alist[0] minIndex = ___________ for ___________________________ : if _____________________ : _____________________ ____________________ return ___________________ mylist = [8,5,2,3,6,4,1] print("Min index =", findMinIndex(mylist)) 3

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 3 : (10 marks) Complete the following Python program so that it appends to a new list newlist all the items with even indexes in the original list numlist . The output of this program is: [1, 3, 5, 7] def createlist(numlist): newlist = __________ for _________________________ : if ________________ : ___________.append(______________) return _______________ print(createlist([1,2,3,4,5,6,7,8])) 4

Question 4 : (10 marks) Trace through the following search program, as per the instructions below, fill out the trace tables, and finally, answer the questions below. def binarySearch(target, mylist): startIndex = 0 endIndex = len(mylist) -1 found = False targetIndex = -1 while not found and startIndex <= endIndex: midpoint = (startIndex + endIndex)//2 if mylist[midpoint] == target: found = True targetIndex = midpoint else: if target > mylist[midpoint]: endIndex = midpoint -1 else: startIndex = midpoint +1 return targetIndex def getInterval(firstIndex, secIndex, alist): newlist = [] i = firstIndex while i <= secIndex: newlist.append(alist[i]) i = i + 1 return newlist mylist=[9,8,7,6,5,3,2,1] firstIndex = binarySearch(7, mylist) secIndex = binarySearch(3,mylist) print(getInterval(firstIndex, secIndex,mylist)) First, trace thru the binarySearch( ) function, and fill in the table below: 1) When target = 7 midpoint targetIndex 2) When target = 3 midpoint targetIndex 5

Question 4 continued: Now, trace through the getInterval( ) function. Before you start tracing, first indicate the values for firstIndex and secIndex . Then, fill out the table below. firstIndex = ___________ secIndex = ___________ Fill out the following trace table for the getInterval( ) function: i newlist 6

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 5 : (10 marks) Trace through selection sort, fill out the trace table, and answer the questions below: (6 marks) def findSmallestIndex(alist,start): smallestIndex = start for i in range(start,len(alist)): if alist[smallestIndex] > alist[i]: smallestIndex = i return smallestIndex def selectionSort(alist): start = 0 while start < len(alist)-1: smallestIndex = findSmallestIndex(alist, start) alist[start], alist[smallestIndex] = alist[smallestIndex], alist[start] start = start + 1 return alist mylist = [2,8,5,9,6,3] print(selectionSort(mylist)) start alist Answer the questions below: (4 marks) 1) How many passes would the above algorithm have over a list size of n items? What are the stopping conditions for this selection sort algorithm? 2) How many comparisons did the above algorithm perform in the first pass over the list? How many swaps does it perform per pass? 7

Question 6 : (10 marks) 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? 8

Related Documents

ITEC 1000 midterm.docx

CMPUT 101 Practice MT2 Solutions.docx

Additional Practice Questions.docx

Practice Final Spring 2020.docx

Assignment 2 - Module 3.docx

Assignment 3- Module 4.docx

Chapter11 Part1.pdf

Chapter7Part3.pdf

CS 410 Binary to Assembly Activity .docx

CS 410 Project One Proficiency Test .docx

CS 410 6-1 Journal.docx

CS 410 8-1 Journal.docx

Recommended textbooks for you

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

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

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE

Computer Science

ISBN:9780357392676

Author:FREUND, Steven

Publisher:CENGAGE L

Np Ms Office 365/Excel 2016 I Ntermed

Computer Science

ISBN:9781337508841

Author:Carey

Publisher:Cengage

EBK JAVA PROGRAMMING

Computer Science

ISBN:9781337671385

Author:FARRELL

Publisher:CENGAGE LEARNING - CONSIGNMENT

Enhanced Discovering Computers 2017 (Shelly Cashm...

Computer Science

ISBN:9781305657458

Author:Misty E. Vermaat, Susan L. Sebok, Steven M. Freund, Mark Frydenberg, Jennifer T. Campbell

Publisher:Cengage Learning

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
COMPREHENSIVE MICROSOFT OFFICE 365 EXCE
Computer Science
ISBN:9780357392676
Author:FREUND, Steven
Publisher:CENGAGE L
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:9781337508841
Author:Carey
Publisher:Cengage
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT
Enhanced Discovering Computers 2017 (Shelly Cashm...
Computer Science
ISBN:9781305657458
Author:Misty E. Vermaat, Susan L. Sebok, Steven M. Freund, Mark Frydenberg, Jennifer T. Campbell
Publisher:Cengage Learning