Foundation Exam - CS I Section

pdf

School

Rumson Fair Haven Reg H *

*We aren’t endorsed by this school

Course

C101

Subject

Computer Science

Date

Nov 24, 2024

Type

pdf

Pages

Uploaded by CoachRiverTiger30

October 16 th Foundation Exam CS I Questions (1, 15%) The following (INCORRECT) algorithm is intended to be the iterative bubble sort algorithm. Assume that swap is a global procedure that exchanges the contents of its two parameters. algorithm Bsort(n) procedure B(k) 1) set j <- 1 2) while j < k do 3) if a[j] > a[j+1] then 4) swap(a[j], a[j+1]) 5) set j ß j + 1 endprocedure begin 6) for i = 1 to n-1 do 7) B(n-i); endalgorithm It SHOULD take this first list… 8 3 10 7 5 4 …and produce this list. 3 4 5 7 8 10 1a) But, it doesn't. What does it produce? 1b) There is one error in the algorithm. In which line does it occur? __________ 1c ) Write the correct pseudo-code for the line identified in 1b).

(2, 20%) The following are Postfix strings. All values are single decimal digits and the operations are binary add "+", binary subtract "-",and binary multiplication "*". Indicate which are invalid, if any. For those that are valid, compute the result. a) 9 4 + 2 3 * - 6 3 - 5 * + 7 - ___________________________ b) 8 3 2 4 * + - 7 8 2 3 * - + ________________________ c) 3 2 + 4 2 * 7 5 - 2 3 * + - + ________________________ d) Given the following Postfix expression, show in the boxes below what the stack would contain immediately before the - operation is processed. Do not find the final result. Assume that the stack is initially empty. 2 6 + 5 3 2 * - 5 * + (top of stack)

(3, 15%) The following insertion algorithm, Insert , must be invoked from the algorithm you are to write below. Assume that the variables j and x are local to the procedure and that k is an integer parameter. Procedure Insert(k) set j <- k set x <- a[j] while (j > 1) and (x < a[j-1]) do set a[j] <- a[j-1] set j <- j-1 set a[j] <- x end Write a recursive "InsertionSort" algorithm using Insert . You may assume a globally defined array a[1..n] of integer values that is already initialized. (4, 20%) Find the closed form or exact value for each of the following: ( n is an arbitrary positive integer): 4a) å (3i+2) = ( i ranges from 0 to n .) _______________________ 4b) å (2i-3) = ( i ranges from 50 to 200 .) ____________________

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

4c) S = 5 + 6 + 7 + 8 + … + (n-2) + (n-1) = _____________________ 4d) t(n) = t(n-1) + 2, where t(0) = 1 ________________________ (5, 15%) Answer each of the following "timing" questions concerning an algorithm of a particular order and an instance of a particular size. a) For an O(n) algorithm, an instance with n = 50 takes 4 seconds. How long will it take with n = 250? ____________________ b) For an O(n 3 ) algorithm, an instance with n = 30 takes 20 seconds. How long will it take when n = 60? ____________________ c) For an O(2 n ) algorithm, an instance with n = 2 takes 12 seconds.

How long will it take when n = 3? ____________________ (6, 5%) Given the following procedure, fill in the blanks below to show the order in which the values of x will be output if the procedure is called with Print_it(5) . procedure Print_it(x) if (x = 1) then print(x) else Print_it(x-1) print(x) endif endprocedure Show, in order, the output from executing the procedure: ___________ ___________ ___________ ___________ ___________ (7, 10%) P is the class of problems known to be solvable in polynomial time, NP is the class that is verifiable in polynomial time (i.e., given the correct solution to an instance, we can verify its validity in polynomial time), and EXP are problems we know require exponential time to solve and to verify. Which is the most appropriate set for each of the following? Evaluate a postfix expression _________________ Finding the most distant pair in a list of n items _________________ Reverse a character string of n characters _________________ Find a cycle containing every node in a graph _________________ Finding the closest pair in a list of n items _________________ Search a list of n items for a given value _________________

Fitting a set of final exams into the shortest number of days_________________ Sort a list of n values _________________ Towers of Hanoi _________________ Find a subset of numbers which sum exactly to X _________________ Solutions to the CSI questions.

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

Related Documents

Project_Part2_Assignment.docx6572a62c9e3c224541.docx

201.jpg

Silicon Valley Leaders Symposium Paper.docx

task08.pdf

DEA-3TT2 Exam – Free Actual Q&As, Page 3 _ ExamTopics.pdf

ha.docx

IMG_5040.png

3.1nn_wshop.pdf

Assessment 5_Unique numbe r 302211 (page 4 of 10).pdf

Cs_certification_ansewes[1].docx

februarycyberdays_blogspot_com_2023_09_dataframes_in_r_html.pdf

2312 Slides 9.pdf

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

EBK JAVA PROGRAMMING

Computer Science

ISBN:9781337671385

Author:FARRELL

Publisher:CENGAGE LEARNING - CONSIGNMENT

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE

Computer Science

ISBN:9780357392676

Author:FREUND, Steven

Publisher:CENGAGE L

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++ 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
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT
COMPREHENSIVE MICROSOFT OFFICE 365 EXCE
Computer Science
ISBN:9780357392676
Author:FREUND, Steven
Publisher:CENGAGE L
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