University of Nevada, Las Vegas Computer Science 456/656 Fall 2019

Assignment 1: Due Wednesday August 14, 2019

Name:

You are permitted to work in groups, get help from others, read books, and use the internet. But the handwriting on this document must be your own. Print out the document, staple, and fill in the answers. You may attach extra sheets. Turn in the pages to the graduate assistant at the beginning of class, August 28.

1. Proof by contradiction will be used this semester. A number is called rational if it is the quotient of two integers; otherwise it is called irrational. Prove that \sqrt{3} is irrational. (Read the proof in the book that \sqrt{2} is irrational.)

2. We will be using many of the equations given in Exercises 1–12 on pages 23–24. of the fifth edition, problems 9,10,11,12,6,13,14,15,16,17,18,7 on pages 14–15 of the sixth edition. Review those equations, but do not hand anything in.

3. Look at the figure on page 37 of the fifth edition, page 27 of the sixth edition, which represents an abstract automaton. Make sure you understand it.

4. We will make use of the equations given in Exercises 1–4, and 8–9 on pages 37–38 of the fifth edition, problems 2–5, 8,9 on page 28 of the sixth edition. . Make sure you understand them, but do not turn anything in.

5. Work exercises 12–13 on page 38 of the fifth edition, exercises 15–16 on page 29 of the sixth edition.