CS COMP-273: Sample MidTerm Examination Student Name: Signature:
Note: This is a closed book, closed notes examination. Be sure to read through
the entire question sheet and to pace yourself accordingly. There are 3 questions
CS COMP-273: Sample MidTerm Examination
in all, with the third question being worth the most. No calculators are allowed. Make sure to show your working and to comment any code you write. Sign your
Student Name: Signature:
question sheet and turn it in along with your exam booklets. When in doubt,
state any assumptions you make.
Note: This is a closed book, closed notes examination. Be sure to read through
the entire question sheet and to pace yourself accordingly. There are 3 questions
Question 1 (Digital Circuits). [30%]
in all, with the third question being worth the most. No calculators are allowed.
Your task is to design a digital circuit which implements a version of a shift logical left or Make sure to show your working and to comment any code you write. Sign your
a shift logical right. Let A2,A1,A0 represent the 3 bits of a 3-bit register, where A2 is the question sheet and turn it in along with your exam booklets. When in doubt,
most significant bit. Let S1,S0 represent the higher and lower bits, respectively, of a 2-bit state any assumptions you make.
signed binary number, which will be interpreted as a shift amount. Positive values will denote logical shifts to the left and negative values logical shifts to the right. This circuit
Question 1 (Digital Circuits). [30%]
should generate three outputs F , F , F which are the three bits left in the 3-bit register Your task is to design a digital circ2uit1wh0ich implements a version of a shift logical left or
after its contents are shifted by the shift amount.
a shift logical right. Let A2,A1,A0 represent the 3 bits of a 3-bit register, where A2 is the
most significant bit. Let S , S represent the higher and lower bits, respectively, of a 2-bit
a) Generate the truth table for the outputs F , F , F as functions of the inputs.[10 marks] 210
10
signed binary number, which will be interpreted as a shift amount. Positive values will denote logical shifts to the left and negative values logical shifts to the right. This circuit
b) Derive a minimized sum-of-products expression for each of the three outputs F , F , F ,
should generate three outputs F , F , F which are the three bits left in the 3-bit register 210
as functions of the inputs, using K-maps, but do not worry about the case of logical after its contents are shifted by the shift amount.
shifts to the right.[20 marks]
a) Generate the truth table for the outputs F , F , F as functions of the inputs.[10 marks] 210
Hint: Use the sign of the shift amount to identify the cases you need to represent.
b) Derive a minimized sum-of-products expression for each of the three outputs F2,F1,F0,
(InpQarutebs,tdion¡¯t2u(sNeKu-mbaeprssRinecperewsendtidanti¡¯tonco).ve[r2t0h%em] thisyear,buttrytosimplifythe
as functions of the inputs, using K-maps, but do not worry about the case of logical
expressions using the laws of Boolean algebra.)
shifts to the right.[20 marks]
Hint: Use the sign of the shift amount to identify the cases you need to represent.
a) Suppose you have a m-digit unsigned number in base 8. What is the largest value that
such a number can take on? If such a number is to be represented in base 2 using n digits,
what is the precise relationship between n and m? [10 marks]
Question 2 (Number Representation). [20%]
b) Represent -102.25 as an IEEE single precision floating point number. [10 marks]
a) Suppose you have a m-digit unsigned number in base 8. What is the largest value that
such a number can take on? If such a number is to be represented in base 2 using n digits, what is the precise relationship between n and m? [10 marks]
Question 3 (MIPS). [50%]
In this question you are asked to complete the MIPS code below to implement a subrou- b) Represent -102.25 as an IEEE single precision floating point number. [10 marks]
tine which tests whether or not an input string is a palindrome. A palindrome is a string
which reads the same way when read backwards and forwards. For example, the string ¡°12fo- Qruoef2st1i¡±onis 3a (pMaliInPdSro)m. [e5. 0T%h]e string you are asked to test has an associated label ¡°string¡±. The NULL termination character should not be considered for the palindrome test, but your
In this question you are asked to complete the MIPS code below to implement a subrou- tine which tests whether or not an input string1 is a palindrome. A palindrome is a string which reads the same way when read backwards and forwards. For example, the string ¡°12fo- rof21¡± is a palindrome. The string you are asked to test has an associated label ¡°string¡±. The NULL termination character should not be considered for the palindrome test, but your
1
210
what is the precise relationship between n and m? [10 marks]
b) Represent -102.25 as an IEEE single precision floating point number. [10 marks]
Question 3 (MIPS). [50%]
In this question you are asked to complete the MIPS code below to implement a subrou-
tine which tests whether or not an input string is a palindrome. A palindrome is a string
which reads the same way when read backwards and forwards. For example, the string ¡°12fo-
code should work for any such test string. For all your working your use of registers should
rcoofn21fo¡±rmis taoptahleincdornovmeen.tioTnhseinstroindgucyeoduinarcelassk.edBetosutersetthoacsoamnmaesnstocyioauterdcoladbeecla¡°rsetfruilnlyg.¡±.
TNhoeteNtUhLatLttherm¡°minaitni¡±onrocuhtainraecitseralsrheoaudlydwnroittbene.coPnrsoicdeerdedasfofroltlhowe sp:alindrome test, but your code should work for any such test string. For all your working your use of registers should
conform to the conventions introduced in class. Be sure to comment your code carefully.
code should work for any such test string. For all your working your use of registers should Note that the ¡°main¡± routine is already written. Proceed as follows:
a) Complete the subroutine ¡°length¡± which takes as input a single argument which is a conform to the conventions introduced in class. Be sure to comment your code carefully.
pointer to the first element in the NULL terminated string. This routine should return the Note that the ¡°main¡± routine is already written. Proceed as follows:
a) Complete the subroutine ¡°length¡± which takes as input a single argument which is a
length of the string (the number of characters in it not including the NULL termination
pointer to the first element in the NULL terminated string. This routine should return the
a) Assume a subroutine called ¡°length¡± has already been written for you.
character).[10 marks]
length of the string (the number of characters in it not including the NULL termination
a) Complete the subroutine ¡°length¡± which takes as input a single argument which is a character).[10 marks]
pointer to the first element in the NULL terminated string. This routine should return the
1
b) Complete the subroutine ¡°palind¡± which takes as input two arguments, the first being a
length of the string (the number of characters in it not including the NULL termination b) Complete the subroutine ¡°palind¡± which takes as input two arguments, the first being a
pointer to the first element in a string and the second being the length of the string. This cphoainrtaecrtteor)th.[e10firsmt aelrekmse]nt in a string and the second being the length of the string. This
routine should return a value of 1 if the test string is a palindrome and 0 otherwise. Do not routine should return a value of 1 if the test string is a palindrome and 0 otherwise. Do not
use recursion for this part.[20 marks] use recursion for this part.[20 marks]
b) Complete the subroutine ¡°palind¡± which takes as input two arguments, the first being a
pointer to the first element in a string and the second being the length of the string. This
c) Come up with an entirely new version of the subroutine ¡°palind¡± which is recursive. To
c) Come up with an entirely new version of the subroutine ¡°palind¡± which is recursive. To
routine should return a value of 1 if the test string is a palindrome and 0 otherwise. Do not do so you need to first come up with the proper recursive step. Hint: A string having one
do so you need to first come up with the proper recursive step. Hint: A string having one
uelseemreenctuisrsaiopnalifnodrotmhei.sApasrtrti.n[2g0hamvinagrktws]o elements is a palindrome if … A string having
element is a palindrome. A string having two elements is a palindrome if … A string having
3 elements is a palindrome if…, and so on.[20 marks]
3 elements is a palindrome if…, and so on.[20 marks]
c) Come up with an entirely new version of the subroutine ¡°palind¡± which is recursive. To
# Your program begins here.
do so you need to first come up with the proper recursive step. Hint: A string having one .data
# Your program begins here.
element is a palindrome. A string having two elements is a palindrome if … A string having
string: .asciiz ¡®¡®CabbUlafadodafalUbbaC¡¯¡¯ # this is the test string .data
3 elements is a palindrome if…, and so on.[20 marks]
string: .asciiz ¡®¡®CabbUlafadodafalUbbaC¡¯¡¯ # this is the test string
#
length: string:
length: palind:
palind: lmeainng:th:
main: palind:
main:
.text .globl main
.text
.align 2
Your program begins here. .align 2
.data # first line of ¡®¡®length¡¯¡¯ subroutine .globl main
.asciiz ¡®¡®CabbUlafadodafalUbbaC¡¯¡¯ # this is the test string
jr $ra .text
# last line of ¡®¡®length¡¯¡¯
# first line of ¡®¡®length¡¯¡¯ subroutine
# first line of ¡®¡®palind¡¯¡¯ subroutine # last line of ¡®¡®length¡¯¡¯
# last line of ¡®¡®length¡¯¡¯
# first line of ¡®¡®palind¡¯¡¯ subroutine # ¡®¡®main¡¯#¡¯ pfriorgsrtam lbiengeinsofby¡®g¡®eltetninggthp¡¯o¡¯intseurbroutine
.align 2 jr $ra
.globl main jr $ra
la $a0,string
jal length
# to the string and calling ¡®¡®length¡¯¡¯
jr $ra
add $a1,$v0,$zero
# last line of ¡®¡®length¡¯¡¯
# now set up the arguments for ¡®¡®palind¡¯¡¯ and
jr $ra
la $a0,string
# last line of ¡®¡®length¡¯¡¯ # call it
jallapal$ian0d,string
nop
jal length
add $a1,$v0,$zero
jr $ra
la $a0,string
jal palind
la $a0,string nop
jal length
add $a1,$v0,$zero
la $a0,string
jal palind
nop
# ¡®¡®main¡¯¡¯ program begins by getting pointer
2
# to the string and calling ¡®¡®length¡¯¡¯
# now set up the arguments for ¡®¡®palind¡¯¡¯ and
# last line of ¡®¡®length¡¯¡¯ # call it
# ¡®¡®main¡¯¡¯ program begins by getting pointer # last line of ¡®¡®main¡¯¡¯
# to the string and calling ¡®¡®length¡¯¡¯
# now set up the arguments for ¡®¡®palind¡¯¡¯ and
# call it
# last line of ¡®¡®main¡¯¡¯
# first line of ¡®¡®palind¡¯¡¯ subroutine # last line of ¡®¡®main¡¯¡¯
2