Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CISC 203 - Assignment 1
Due: Thursday September 26 by 2:30 PM
(in the locked CISC 203 drop-off box on Goodwin 2nd floor)
One bonus mark for neatly written student information: Papers that have your name, student number and other information written exactly as requested in the regulations (found at the end), will receive one bonus mark.
1. (3 marks) Let A and B be sets. Prove
A ∩ B = A ∪ B.
Recall that A stands for the complement of the set A.
Note: In order to prove equality of sets, you need to prove inclusion in both directions. If you wish, you can illustrate the argument using a Venn diagram but a diagram by itself is not sufficient. You are expected to give a logical argument that proves both inclusions.
2. Consider relations R ⊆ A × B and S1, S2 ⊆ B × C (where A, B, C are sets).
(a) (2 marks) Prove that R (S1 ∩ S2) ⊆ (R S1) ∩ (R O S2).
(b) (2 marks) Give a concrete example of relations R ⊆ A × B and S1, S2 ⊆ B × C such that
R O (S1 ∩ S2) 6= (R S1) ∩ (R O S2)
(thus proving that the inclusion in part (a) cannot be replaced by equality).
Above R O S denotes the composition of relations R and S (as defined in Definition 3.2 of the first part of the notes). Hint for (b): It may be useful to select S1, S2 6= ∅ such that S1 ∩ S2 = ∅.
3. (3 marks) For each case answer “true” or “false”. (In this question it is not required to explain the answers.)
(a) 5n 2 + n + 7 = O(n 2 )
(b) n 2 = o(5n 2 + n + 7)
(c) n 2 = o(n 2 · √ n)
(d) n 2 = O(n 2 · √ n)
(e) log n = o( √ n) (f) √ n = O(log n)
4. (4 marks) A decimal digit is one of the characters 0, 1, 2, . . . , 9. A string is an ordered sequence of characters. Examples of strings of four decimal digits include 1234, 0001, 5567.
How many strings of four decimal digits
(a) do not contain the same digit four times?
(b) do not contain the same digit twice?
(c) end with an even digit?
(d) have exactly 3 digits that are 8’s?
Justify your answers: in each case you need to explain why the number is as claimed.
5. (2 marks) Show that if f is a function from A to B, where A and B are finite sets and ` = d |A| |B| e, then there are at least ` elements of A mapped to the same element of B. That is, show that there are ` distinct elements a1, . . . , a` ∈ A such that f(a1) = . . . = f(a`). Hint. Here some result from class (the notes on combinatorics) may be useful.
6. (4 marks) Consider a function f : A → B. Prove: f has a right inverse if and only if f is onto. Recall that “right inverse of a function” is defined in Definition 3.4 of the first set of notes.
Regulations on assignments
• The assignment must be based on individual work. Copying solutions from other students is a violation of academic integrity. See the course web site for more information http://research.cs.queensu.ca/home/cisc203/index.html
• At the top of the first page of the assignment, type or write in clear capital letters the following information on four different lines and in the order listed below:
– CISC-203 ASSIGNMENT X (where X ∈ {1, 2, 3, 4} is the number of the current assignment)
– LAST-NAME, FIRST-NAME (your name as it appears on solus, e.g., “SMITH, NANCY”)
– your student number (e.g., “1234 4321”)
– your signature (the signature need not be easily readable)
• Bonus mark: Papers that have the above information written exactly correctly and perfectly clearly and legibly will receive one bonus mark. An additional requirement is that it is not permitted to submit more than one copy of the same assignment. The assignment is worth 20 marks. Papers that receive the bonus mark, may get more than 20 marks. For the bonus mark there is no partial credit for incomplete information or unclear handwriting.
• The assignment should be put into the locked CISC 203 drop-off box on the 2nd floor of Goodwin hall by the due date. The assignments must be submitted in hardcopy. Assignments sent by email are not accepted.
• If the submission consists of more than one page, the pages must be stapled together.
• Note: You are asked to write your solutions using non-erasable pen (or to type the solutions). Solutions written in pencil or erasable ink will be marked, but they will not be considered for remarking after the assignments are returned.