PA1

pdf

School

San Jose State University *

*We aren’t endorsed by this school

Course

146

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by SargentMandrillMaster963

CS 146 Programming Assignment 1 (100 Points) Introduc:on: The purpose of this assignment is to familiarize yourself with submi6ng the assignments in a prescribed format and analyze running 9mes of the algorithms. Each ques9on has a programming part and some wri=en ques9ons. Ques:on 1 (Implemen:ng sorts): (50 points) a. (Program – 10 points): Write a Java program PA1Sort that takes two command line arguments. The first command line argument can be one of [‘inser9on’, ‘bubble’] and the second argument will be a number. The second number specifies the number of input numbers. Read the input numbers from the standard input. This allows us to do an input redirec9on using < and send a text file (see example below). b. (Program – 30 points): Implement the two sort methods inser9onSort and bubbleSort that takes a list/array of integers and performs the sor9ng using inser9onSort and bubbleSort algorithms. Call the appropriate method based on the first command line argument and print the sorted list on standard output. c. (Wri7en – 10 points): Run your program for inputs of sizes (5, 100, 1000) and 9me them. Report your run 9mes for each sort method. (see below). In your wri=en report include a table as follows. Sort Method N User System CPU Total Inser9on 100 2.51 0.52 135 2.240 Here are some examples: $ java PA1Sort inser9on 5 3 13 8 6 5 3 5 6 8 13 $ $ java PA1Sort bubble 6 10 9 11 8 12

7 7 8 9 10 11 12 $ $ java PA1Sort inser9on 5 < 5.txt 3 5 6 8 13 $ 9me java PA1Sort inser9on 100 < 100.txt … java PA1Sort inser9on 5 < 100.txt 2.51s user 0.52s system 135% cpu 2.240 total $ Ques:on 2 (Inversions): (50 points) Let A be an array of n dis9nct integers. If i < j and A[i] > A[j], then the pair (I,j) is called an “inversion” of A (Note: that the inversions are reported as indices and not actual values) a. (Wri7en – 5 points): List the inversions of the array [3, 13, 8, 6, 5] b. (Wri7en – 5 points): Let the array A be a permuta9on of the numbers {1,2,3,….,n}. Which is the array that will have the most inversions. How many inversions will there be? c. (Program – 30 points): Write a Java program PA1Inversion that takes one commandline argument which is the number of input values. Read the input values from the standard input (as in Ques9on1) and prints the number of inversions in the given array d. (Wri7en – 10 points): What is the running 9me analysis of your algorithm (Specifically what is Q of the algorithm). How do you prove it? Is there a way to make it be=er? $ java PA1Inversion 5 < 5.txt 6 $ Teamwork This Is an INDIVIDUAL assignment. What to turn in Create a zip file containing: • Your Java source files. • A txt/doc/pdf file with answers to the wri=en ques9ons above. Name the zip file a-er yourself (lastname_sjsuid.zip) Examples: smith_012345678.zip

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

7.5.11 Practice Questions.pdf

hw02.pdf

Unix HW 4.docx

assign1.pdf

Hardware_Shopping.rtf

sample midterm_solutions.docx

Lab Cryptography Forging Digital Signatures Assignment Instructions.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

EBK JAVA PROGRAMMING

Computer Science

ISBN:9781337671385

Author:FARRELL

Publisher:CENGAGE LEARNING - CONSIGNMENT

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

New Perspectives on HTML5, CSS3, and JavaScript

Computer Science

ISBN:9781305503922

Author:Patrick M. Carey

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
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
New Perspectives on HTML5, CSS3, and JavaScript
Computer Science
ISBN:9781305503922
Author:Patrick M. Carey
Publisher:Cengage Learning