# 程序代做 CS 70 Discrete Mathematics and Probability Theory Fall 2021 – cscodehelp代写

CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Truth Tables
Determine whether the following equivalences hold, by writing out truth tables. Clearly state whether or not each pair is equivalent.
(a) P∧(Q∨P) ≡ P∧Q

(b) (P∨Q)∧R ≡ (P∧R)∨(Q∧R) (c) (P∧Q)∨R ≡ (P∨R)∧(Q∨R)
(a) Not equivalent.
P Q P∧(Q∨P) P∧Q TTTT TFTF FTFF FFFF
(b) Equivalent.
P Q R (P∨Q)∧R (P∧R)∨(Q∧R) TTTTT TTFFF TFTTT TFFFF FTTTT FTFFF FFTFF FFFFF
(c) Equivalent.
CS 70, Fall 2021, DIS 1A 1

P Q R (P∧Q)∨R (P∨R)∧(Q∨R) TTTTT TTFTT TFTTT TFFFF FTTTT FTFFF FFTTT FFFFF
2 Converse and Contrapositive
Consider the statement “if a natural number is divisible by 4, it is divisible by 2”.
(a) Write the statement in propositional logic. Prove that it is true or give a counterexample.
(b) Write the inverse of the implication in English and in propositional logic. Prove that it is true
or give a counterexample. (The inverse of an implication P =⇒ Q is ¬P =⇒ ¬Q.)
(c) Write the converse of the implication in English and in propositional logic. Prove that it is true
or give a counterexample.
(d) Write the contrapositive of the implication in English and in propositional logic. Prove that it is true or give a counterexample.
(a) (∀x∈N)(4|x =⇒ 2|x). Thisstatementistrue. Weknowthatifxisdivisibleby4,wecan write x as 4k for some integer k. But 4k = (2 · 2)k = 2(2k), where 2k is also an integer. Thus, x must also be divisible by 2, since it can be written as 2 times an integer.
(b) The inverse is that if a natural number is not divisible by 4, it is not divisible by 2: (∀x ∈ N) (4 􏰀 x =⇒ 2 􏰀 x). This is false, since 2 is not divisible by 4, but is divisible by 2.
(c) The converse is that any natural number that is divisible by 2 is also divisible by 4: (∀x ∈ N)(2|x =⇒ 4|x). Again,thisisfalse,since2isdivisibleby2butnotby4.
(d) The contrapositive is that any natural number that is not divisible by 2 is not divisible by 4: (∀x∈N)(2􏰀x =⇒ 4􏰀x). Toshowthatthisistrue,firstconsiderthatsayingthatxisnot divisible by 2 is equivalent to saying that x/2 is not an integer. And if we divide a non-integer by an integer, we get back another non-integer–so (x/2)/2 = x/4 must also not be an integer. But that is exactly the same as saying that x is not divisible by 4.
Note that the inverse and the converse will always be contrapositives of each other, and so will always be logically equivalent.
CS 70, Fall 2021, DIS 1A 2

3 Preserving Set Operations
Forafunction f,definetheimageofasetX tobetheset f(X)={y|y= f(x)forsomex∈X}. DefinetheinverseimageorpreimageofasetY tobetheset f−1(Y)={x| f(x)∈Y}. Provethe following statements, in which A and B are sets.
Recall: ForsetsX andY,X =Y ifandonlyifX ⊆Y andY ⊆X. ToprovethatX ⊆Y,itissufficient toshowthat(∀x)((x∈X) =⇒ (x∈Y)).
(a) f−1(A∪B) = f−1(A)∪ f−1(B). (b) f(A∪B)=f(A)∪f(B).
In order to prove equality A = B, we need to prove that A is a subset of B, A ⊆ B and that B is a subset of A, B ⊆ A. To prove that LHS is a subset of RHS we need to prove that if an element is a member of LHS then it is also an element of the RHS.
(a) Supposex∈ f−1(A∪B)whichmeansthat f(x)∈A∪B. Theneither f(x)∈A,inwhichcasex∈ f−1(A),or f(x)∈B,inwhichcasex∈ f−1(B),soineithercasewehavex∈ f−1(A)∪f−1(B).
This proves that f −1(A ∪ B) ⊆ f −1(A) ∪ f −1(B).
Now, suppose that x ∈ f −1(A) ∪ f −1(B). Suppose, without loss of generality, that x ∈ f −1(A). Then f(x) ∈ A, so f(x) ∈ A∪B, so x ∈ f−1(A∪B). The argument for x ∈ f−1(B) is the same. Hence, f−1(A)∪ f−1(B) ⊆ f−1(A∪B).
(b) Suppose that x ∈ A∪B. Then either x ∈ A, in which case f(x) ∈ f(A), or x ∈ B, in which case f(x) ∈ f(B). In either case, f(x) ∈ f(A)∪ f(B), so f(A∪B) ⊆ f(A)∪ f(B).
Now, suppose that y ∈ f(A)∪ f(B). Then either y ∈ f(A) or y ∈ f(B). In the first case, there isanelementx∈Awith f(x)=y;inthesecondcase,thereisanelementx∈Bwith f(x)=y. In either case, there is an element x ∈ A∪B with f(x) = y, which means that y ∈ f(A∪B). So
f(A)∪ f(B) ⊆ f(A∪B).
The purpose of this problem is to gain familiarity to naming things precisely. In particular, we named an element in the LHS (or the pre-image of the LHS) and then argued about whether that element or its image was in the right hand side. By explicitly naming an element generically where it could be any element in the set, we could argue about its membership in a set and or its image or preimage. With these different concepts floating around it is helpful to be clear in the argument.
4 Numbers of Friends
Prove that if there are n ≥ 2 people at a party, then at least 2 of them have the same number of friends at the party. Assume that friendships are always reciprocated: that is, if Alice is friends with Bob, then Bob is also friends with Alice.
CS 70, Fall 2021, DIS 1A 3

(Hint: The Pigeonhole Principle states that if n items are placed in m containers, where n > m, at least one container must contain more than one item. You may use this without proof.)
We will prove this by contradiction. Suppose the contrary that everyone has a different number of friends at the party. Since the number of friends that each person can have ranges from 0 to n − 1, we conclude that for every i ∈ {0, 1, . . . , n − 1}, there is exactly one person who has exactly i friends at the party. In particular, there is one person who has n − 1 friends (i.e., friends with everyone), and there is one person who has 0 friends (i.e., friends with no one), which is a contradiction.
Here, we used the pigeonhole principle because assuming for contradiction that everyone has a different number of friends gives rise to n possible containers. Each container denotes the number of friends that a person has, so the containers can be labelled 0,1,…,n−1. The objects assigned to these containers are the people at the party. However, containers 0, n − 1 or both must be empty since these two containers cannot be occupied at the same time. This means that we are assigning n people to at most n − 1 containers, and by the pigeonhole principle, at least one of the n − 1 containers has to have two or more objects i.e. at least two people have to have the same number of friends.
CS 70, Fall 2021, DIS 1A 4

# CS代写 Part A: Short Answer (49 marks) – cscodehelp代写

Part A: Short Answer (49 marks)
For the following short answer questions, a text file called q1.txt has been provided for you to fill in your answers (in addition to this question sheet). Each question below is represented by a line in this text file, with an underscore character (“_”) that must be replaced with your answer.
For example, the examples below show what the contents of q1.txt might look like before and after you fill in your answers:
Before After

Here are a few things to keep in mind when filling out the answers to this question:
1. All letters should be lowercase, unless specified otherwise.
2. Once you have filled in all the answers, submit the text file through Markus (not Quercus).
3. Do not submit your answers as a Word file or PDF file. Make sure to view your text file with a
plain text editor before submitting your solution, to make sure the content is what you expect.
1. The output of a gate is 1 when connected to high voltage and 0 when connected to low
voltage. What letter is used to represent an output that isn’t connected to anything? (1 mark)
2. True or False? Voltage is the measure of electrical potential between two points. (1 mark)
3. After the pn-junction from Question 2 has reached equilibrium, what can be said about the drift current and the diffusion current? Circle all that apply. (1 mark)
a) The drift current is higher b) The diffusion current is higher c) The two currents are the same d) Both currents are zero.
4. True or False? At the moment you combine a p-type material with an n-type material to
form a pn-junction, the drift current is high and the diffusion current is low. 5. True or False? A circuit with N inputs will have 2N rows in its truth table.
(1 mark) (1 mark)
Student Number: __________________ 2
(continued)
3. counter

6. Consider the semiconductor circuit on the right. In which direction will the current travel? Remember that current is measured as the flow of positive charges, not
electrons.
a) b) c) d)
Current flows from left to right Current flows from right to left
All of the above None of the above
7. True or False? Once all the Karnaugh map groupings are made, any “don’t care” values that aren’t in a group are assigned a value of 0 in the final circuit. (1 mark)
8. True or False? When used properly, the Karnaugh map will produce the most reduced version of a circuit. (1 mark)
9. True or False? When used properly, the Karnaugh map will produce a unique solution. (1 mark)
10. Consider the circuit on the right. What is the gate cost of this circuit? (1 mark)
11. Considering this same circuit on the right, what is the gate cost plus NOTs for this circuit? (1 mark)
12. TrueorFalse?Fora3-inputdevice,F=m1+m2+m3+m5
and G = M0 ∙ M4 ∙ M6 ∙ M7 express the same function. (1 mark)
13. What is the 8-bit signed binary representation of the decimal number -64?
(1 mark) 14. What is the decimal representation of the signed binary number 11011011? (1 mark)
15. How many flip-flops are needed for a finite state machine with 200 states? (1 mark)
16. True or False? A finite state machine with 2 inputs and 3 flip-flops will have 32 states. (1
Student Number: __________________ 3 (continued)

17. Fill in the blank. A finite state macine whose the output can be determined by the current state is called a ________ machine. (1 mark)
18. How many flip-flops are needed to implement an FSM with 100 states? (1 mark)
19. Fill in the blank. A clock frequency of 0.5 Hz means that the clock goes high ___ times per
second. (1 mark)
20. Which of the following best describes a “race condition”? (1 mark)
a) Something that might cause increase a clock’s frequency
b) Unpredictable behaviour when multiple signals change simultaneously c) Two signals writing values to a shared data bus at the same time
d) What happens when a movie character insults Vin Diesel’s car
21. True or False? Writing to memory is faster than reading from the registers. (1 mark) 22. How many integers can be stored in a memory unit that uses 16 address bits, byte-
addressable memory, and a 32-bit architecture? (2 marks)
23. How many address bits are needed to specify a location in byte-addressable memory,
given a 1024 bit memory unit and a 64-bit architecture? (2 marks)
24. Which of the following best describes the running time of multiplication with Booth’s
Algorithm versus multiplication with an accumulator circuit? (1 mark)
a) The accumulator circuit performs multiplication in O(N) time
b) Booth’s Algorithm performs multiplication in O(N) time
c) Both of the above
d) None of the above
25. If the binary number 01101101 is the input to a barrel shifter with a shift value of 4, what is the shifter’s output? (1 mark)
26. True or False? The assembly instruction sll can turn a negative number into a positive number. (1 mark)
27. True or False? The assembly instruction sra can turn a negative number into a positive number. (1 mark)
28. True or False? The assembly instruction srl can turn a negative number into a positive number. (1 mark)
Student Number: __________________ 4 (continued)

29. Which of the following is true about jump instructions? (1 mark)
a) The new PC value and the old PC value will have the same first four bits
b) The new PC value and the old PC value will have the same first six bits
c) The new PC value and the old PC value will have the same first fourteen bits
d) The new PC value and the old PC value will have the same first sixteen bits
d) None of the above.
30. Which of the following assembly instructions sets ALUSrcB to 11? Provide your answer asoneofa,b,cordhere. (2marks)
a) addi b) bne c) lw d) xori
31. Which of the following assembly instructions sets ALUSrcB to 10? Again, provide your
answer as one of a, b, c or d here. (2 marks)
a) add b) beq c) sw d) jal
32. True or False? If your assembly language function modifies the value in \$s0, it must save that value onto the stack first. (1 mark)
33. True or False? If your assembly language function modifies the value in \$t0, it must save that value onto the stack first. (1 mark)
34. If we store 0x01234567 at address 0x400000 in little endian, what hexadecimal value will end up in 0x400003? You might find the diagram below to be useful. (2 marks)
0x400000 0x400001 0x400002 0x400003
35. For this final question, perform Booth’s Algorithm on operands A = 10101 and B = 01010. In the spaces provided as parts a) to f), provide the contents of P after each right shift of A and P in the algorithm. The initial value of P has been provided for you in part a). (10 marks)
Student Number: __________________ 5 (continued)

# 代写代考 Part J: Assembly Language, part 1 (12 marks) – cscodehelp代写

Part J: Assembly Language, part 1 (12 marks)
In the spaces provided below, write the assembly language instruction(s) that perform the following tasks. Full marks will only be given for one-instruction answers. Do not use pseudo- instructions in your solutions.
a) Set register \$t0 to 0 if register \$s0 is even, and 1 if \$s0 is odd. (3 marks)
b) Invert all the bits of \$a0. (3 marks)

d) Set \$t0 to half the value of \$t1. (3 marks)
Student Number: __________________ 14 (continued)

# CS代写 Part B: Transistors (16 marks) – cscodehelp代写

Part B: Transistors (16 marks)
For each of the gates and devices below, draw a transistor circuit that implements its behaviour in the spaces provided. In each case, full marks will only be given to circuits that a) use the fewest transistors possible and b) are drawn clearly and neatly (i.e. similar to the lecture slide diagrams).
a) Three-input NAND gate
b) Tri-state buffer A

(separate this into two circuits, one for each output)
Student Number: __________________
(continued)

# 程序代写 Part L: Assembly Language, part 3 (24 marks) – cscodehelp代写

Part L: Assembly Language, part 3 (24 marks)
For this question, three text files called q12a.asm, q12b.asm and q12c.asm have been provided for you to fill in your answers. You must provide code that completes each of the functions below:
N! is short for “N factorial”.
a) Inq12a.asm,assumethat\$a0containsanunsignedintegerN.CalculateN!andstore the result in \$v0. (assume that the length of N! will be less than 32 bits). (8 marks)

b) Inq12b.asm,assumethat\$a0and\$a1containtwopositiveintegers.Calculatethe largest integer that can divide both \$a0 and \$a1 evenly (the greatest common divisor) and store that value in \$v0. (8 marks)
c) In q12c.asm, assume that \$a0 and \$a1 contain two pixel values from the bitmap display of your final project. Set \$v0 to store the pixel value that is the average of \$a0 and \$a1 (meaning that each colour component of \$v0 is the average of the corresponding colour components in \$a0 and \$a1). (8 marks)
When completing this question, make sure that you do the following:
 Comment your code to help us understand each of your steps.
 Make sure your code assembles and runs before you submit it!
We will be using testing scripts to check the functionality of your code. Keep the following guidelines in mind before you submit your solution:
 Only add your code to the end of the files provided, after the comment that says, “ONLY ALTER THE CODE BELOW THIS LINE”. Anything above this comment will be replaced with our own testing code.
 Save and submit your .asm files as plain text (do not save it in Word or a PDF or any other file format that could interfere with our testing scripts).
 Do not implement your solutions recursively.
 Once your code is complete, do not use jr \$ra or syscall commands to terminate
your program. This will cause our testing scripts to fail.
Student Number: __________________ 16 (continued)

# 代写代考 CSC258 course in the space below. – cscodehelp代写

Part M: Bonus Question (1 mark)
Draw a picture of the CSC258 course in the space below.
Student Number: __________________ 17 (continued)

# 留学生作业代写 Part E: Sequential Circuits (18 marks) – cscodehelp代写

Part E: Sequential Circuits (18 marks)
1. The waveform diagram below illustrates the output behaviour of five devices in response to inputs X, Y and the clock. Based on the output behaviour of A, B, C, D and E (marked in green), Indicateinthespacesprovidedthegateordevicecausedtheseoutputwaveforms. (10marks)
A: _____________ B: _____________ C: _____________ D: _____________ E: _____________
Clock Q0 Q1

2. In the waveform diagram below, show what the waveform looks like for the signals in the flip-
flop circuit on the right. Assume that Q0
1 1TQ1 Clock
Student Number: __________________ 9
(continued)

# CS代写 Part F: Sequential Devices (10 marks) – cscodehelp代写

Part F: Sequential Devices (10 marks)
1. For each of the sequential devices below, identify the operation that they perform by filling in the space below each device. Note: Be as specific as possible. For instance, ¡°flip-flop¡± won¡¯t get you full marks, whereas ¡°positive edge-triggered RS flip-flop¡± would. (8 marks)
2. In the last diagram, what function does the input X perform? (2 marks)
Student Number: __________________ 10 (continued)

# 计算机代写 Part J: Assembly Language, part 1 (12 marks) – cscodehelp代写

Part J: Assembly Language, part 1 (12 marks)
In the spaces provided below, write the assembly language instruction(s) that perform the following tasks. Full marks will only be given for one-instruction answers. Do not use pseudo- instructions in your solutions.
a) Set register \$t0 to 0 if register \$s0 is even, and 1 if \$s0 is odd. (3 marks)
b) Invert all the bits of \$a0. (3 marks)