Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSc 245 — Introduction to Discrete Structures

Spring 2022

Homework #6

 Directions 

1. This is an INDIVIDUAL assignment; do your own work!  Submitting answers created by computers or by other people is NOT doing your own work.

2. Start early! Getting help is much easier n days before the due date/time than it will be n hours before.

3. The questions that have section numbers are found in the Rosen text, available via D2L. Note that “(w,z)”is asking you to complete parts w and z only, not parts x and y.

4. Write complete answers to each of the following questions, in accordance with the given directions. Create

your solutions as a PDFdocumentsuchthateachanswer isclearlyseparatedfromneighboringanswers,

to help the TAs easilyreadthem. Show your work, when appropriate, for possible partial credit.

5. If you have questions about any aspect of this assignment, help is available from the class sta via piazza.com and our oce hours.

6. When your written answers are ready to be turned in, do so on gradescope.com.  Be sure to assign pages to problems after you upload your PDF. Need help? Visit https://help.gradescope.com/ and search for“Submitting an Assignment.”Note that the programming question has separate submission instructions.

7.  Solutions submitted after the    rst   ve minutes of class on the due date will not be accepted.

 


Functions:

1.  (4 points) Section 2.3, 12(c,d)

2.  (2 points) Section 2.3, 20(a). (N = Z  .)

3.  (2 points) Section 2.3, 22(b)

4.  (2 points) Section 2.3, 38

5.  (2 points) Section 2.3, 68

Sequences:

6.  (2 points) Section 2.4, 4(b,d)

7.  (2 points) Section 2.4, 26(a)

Set Cardinality:

8.  (2 points) Section 2.5, 2(a)


Division:

9.  (4 points) Section 4.1, 8

10.  (2 points) Section 4.1, 14(e)

11.  (2 points) Section 4.1, 30(b)

Primes, GCD, and LCM:

12.  (2 points) Section 4.3, 16(a,c)

13.  (2 points) Section 4.3, 24(a,f)

14.  (2 points) Section 4.3, 26(a,f)

15.  (2 points) Section 4.3, 30

Programming:

16.  (16 points) See Back!


Demonstrating the Fundamental Theorem of Arithmetic. In class we recently introduced the Funda- mental Theorem of Arithmetic (FToA). We haven’t reached inductive proofs yet, but the concepts of inductive proofs are exhibited in a form that you are already familiar with: Recursion. For this part of the homework, you are to write a recursive program that generates a“proof”(OK, a demonstration) of the FToA for a given integer value.  That is, the program will show, step by step, how the integer is decomposed into factors, and factors of factors, etc., until everything is shown to be prime or products of primes.

Write a complete, well–documented recursive Java (named Hmwk6.java) or Python (named hmwk6.py) program that shows the user that a given integer (provided on the command line) is either prime or can be shown to be expressible as the product of two or more primes. Here are two executions that show how your program’s output is to look:

$ java Hmwk6 1173  [ or: $ python3 hmwk6.py 1173 ]

This program will demonstrate that 1173 is either prime

or is the product of two or more prime numbers.

1173 = 391 * 3; are these factors either prime or products of primes?

391 = 23 * 17; are these factors either prime or products of primes?

23 is prime.

17 is prime.

391 is the product of primes (23 and 17 are prime or prime products).

3 is prime.

1173 is the product of primes (391 and 3 are prime or prime products).

As this output shows, the Fundamental Theorem of Arithmetic holds for 1173.

$ java Hmwk6 36  [ or: $ python3 hmwk6.py 36 ]

This program will demonstrate that 36 is either prime

or is the product of two or more prime numbers.

36 = 18 * 2; are these factors either prime or products of primes?

18 = 9 * 2; are these factors either prime or the products of primes?

9 = 3 squared; is this factor either prime or the product of primes?

3 is prime.

9 is the square of 3, which is prime or the product of primes.

2 is prime.

18 is the product of primes (9 and 2 are prime or prime products).

2 is prime.

36 is the product of primes (18 and 2 are prime or prime products).

As this output shows, the Fundamental Theorem of Arithmetic holds for 36.

Note three features in particular:  (a) Indentation is used to make it easier to see what’s happening, (b) the larger factor is listed/used before the smaller, and (c) when a factor is shown to be the square of a prime the output re  ects this. We expect your program to have all of these features, too.

Program  Submission:  After you have created your program, submit your completed program   le(s) using the turnin command on lectura.  The submission directory is cs245h6. Instructions are available from the brief turnin tutorial linked to the class web page.  (The same tutorial explains one way to get   les from your home PC to lectura, should you need to.) Remember to name your source code   le Hmwk6.java or hmwk6.py

so that we don’t have to guess which   le to test.

Programming Info:

 


ˆ

 

ˆ


Don’t know how to get information from the command line? See CmdLine.java and cmdline.py, which are linked to class web page.

What will we be looking for in the way of program documentation?

See http://u.arizona.edu/~mccann/style.html; in particular,

http://u.arizona.edu/~mccann/develop_java.html and .../develop_python.html

show the basic content of the internal and external block comments you are to include with your code (along with a lot of stu that isn’t really relevant to this class).

Yes, I want‘a lot’of documentation. Why? Because every programmer should include detailed, useful documentation in any program. The documentation is worth around a quarter of your possible program score.