Difference between revisions of "CSC231 Final Exam 2017"

From dftwiki3
Jump to: navigation, search
 
(22 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 16:23, 29 April 2017 (EDT)
 
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 16:23, 29 April 2017 (EDT)
 
----
 
----
 +
<onlydft>
  
−
<onlydft>
 
 
<bluebox>
 
<bluebox>
 
<font color="purple">This exam is due on May 12, at '''4:00 p.m.'''.</font>
 
<font color="purple">This exam is due on May 12, at '''4:00 p.m.'''.</font>
 
<br />
 
<br />
−
This exam is given under the rules of the ''honor code''. You have access to all your notes, to books, and to the Web. You cannot, however, discuss the details of the exam with anybody other than your instructor. Questions regarding the exam can only be asked in class, or using Piazza.  Do not post code on Piazza.  Do not suggest or imply possible solutions in your posts on Piazza.  
+
This exam is given under the rules of the ''honor code''. '''It has to be done individually'''. You have access to all your notes, to books, and to the Web. You cannot, however, discuss the details of the exam with anybody other than your instructor. <font color="magenta">'''Questions regarding the exam can only be asked in class, or using Piazza'''</font>.  Do '''not post code''' on Piazza.  Do not suggest or imply possible solutions in your posts on Piazza.  
−
All three problems are worth the same number of points.
+
<br />
 +
All five problems are worth the same number of points (20/100).
 +
<br />
 +
<font color="magenta">'''If you use material not in the class Web page or the on-line textbook we used for class, you need to list references to them in the header of your program.'''</font>
 
</bluebox>
 
</bluebox>
 
<br /><br />
 
<br /><br />
 
=Problem 1: C Programming=
 
=Problem 1: C Programming=
 
<br />
 
<br />
−
Write a C program called '''231grep.c''' that works similarly to the Linux grep command.  Your program should get its input from the command line, just like grep, and support the "-i" switch.  When the user uses this switch, the search is not case sensitive.  When the user omits the switch the search is case-sensitive.
+
Write a C program called '''231grep.c''' that works similarly to the Linux grep command.  Your program should get its input from the command line, just like grep, and support the "-i" switch.  The user will '''never''' use another switch, if she uses one.  When the user uses this switch, the search is not case sensitive.  When the user omits the switch the search is case-sensitive.
 
<br />
 
<br />
 
Here is an example illustrating how your program should work.
 
Here is an example illustrating how your program should work.
Line 43: Line 46:
 
==Implementation Details==
 
==Implementation Details==
 
<br />
 
<br />
−
* Your program needs to support only the "-i" switch
+
* Your program needs to support only the "-i" switch.
 
* The order of the command-line parameters will always be  
 
* The order of the command-line parameters will always be  
 
::# switch (if present)
 
::# switch (if present)
 
::# word  
 
::# word  
 
::# file name
 
::# file name
 +
* You may assume that lines will never be more than 1000 characters long.
 
<br />
 
<br />
 +
 
==Testing==
 
==Testing==
 
<br />
 
<br />
Line 58: Line 63:
 
* Submit your code on Moodle, in the '''grep''' section of the final exam.
 
* Submit your code on Moodle, in the '''grep''' section of the final exam.
 
<br />
 
<br />
−
=Problem 2: Fixed and Floating Point Numbers=
+
=Problem 2: Fixed Point Numbers=
 +
<br />
 +
Take the quiz on Moodle regarding the '''Fixed-Point'''  number system.
 
<br />
 
<br />
−
Take the quiz on Moodle regarding '''Fixed''' and '''Floating-Point''' numbers.
 
 
<br />
 
<br />
 
=Problem 3: Assembly Programming=
 
=Problem 3: Assembly Programming=
 
<br />
 
<br />
−
Write a program that contains a recursive function called '''binSearch''', that searches a sorted array of integers (4 bytes) for an integery ''key''.  
+
Write a program that contains a '''recursive''' function called '''binSearch''', that searches a '''sorted array''' of integers for an integer ''key''.  
 
<br />
 
<br />
−
Your program will be linked with a separate main program that will call your function and will provide it with
+
Your program will be linked with a separate main program that will call your function and will pass it the following parameters:
−
:# the address of the array, i.e. the address of the first byte of the first integer in the array,
+
:# the address of the array,
−
:# an integer ''key'', which is the integer we are searching in the array,
+
:# an integer ''key'', which is the integer we are searching for in the array,
 
:# a low index, identifying the lowest bound of the interval being searched, and
 
:# a low index, identifying the lowest bound of the interval being searched, and
−
:# a high index, idnetifying the upper bound of the interval being searched.
+
:# a high index, identifying the upper bound of the interval being searched.
−
Your function will return the index of the key, if it is found, or it will return -1 if the key is not found.
+
<br />
 +
Your function will return the index of the key (not its address), if it is found, or it will return -1 if the key is not found.  The example program below will make that clear.
 
<br />
 
<br />
 
The Python function '''search()''' given [[CSC231_binarySearch.py| on this page]] is exactly what you need to translate to assembly.
 
The Python function '''search()''' given [[CSC231_binarySearch.py| on this page]] is exactly what you need to translate to assembly.
 
<br />
 
<br />
 
==Example Main Program==
 
==Example Main Program==
 +
<br />
 +
You can use the following main program to test your binSearch function.  <font color="magenta">Note, you should get a brand new copy of the '''231Lib.asm''' file, as it has been updated with a new function, '''_printInt''' that can print 2's complement numbers</font>.  In particular, if eax contains -1, then _printInt will print it correctly (_printDec would print 4294967295 instead).
 
<br />
 
<br />
 
::<source lang="asm">
 
::<source lang="asm">
Line 128: Line 137:
 
_start:
 
_start:
 
;; binSearch( table1, 3000, 0, TABLE1LEN-1 )
 
;; binSearch( table1, 3000, 0, TABLE1LEN-1 )
−
;; returned value should be -8
+
;; returned value should be 28
 
 
 
mov eax, table1 ; pass table1
 
mov eax, table1 ; pass table1
Line 173: Line 182:
  
 
;; binSearch( table2, 2, 0, TABLE2LEN-1 )
 
;; binSearch( table2, 2, 0, TABLE2LEN-1 )
−
;; returned value should be 2
+
;; returned value should be -1
 
 
 
mov eax, table2
 
mov eax, table2
Line 195: Line 204:
 
</source>
 
</source>
 
<br />
 
<br />
 +
==Additional Information==
 +
<br />
 +
Your binSearch.asm program may contain several functions.  You can make binSearch( table, key, low, high) a function that is not itself recursive, but that call another function, this one a recursive function, that will do the recursive searching.  The Python program below illustrates how the main program calls a function that is not itself recursive, but uses recursion to solve the problem.
 +
<br />
 +
::<source lang="python">
 +
def sumUp( A ):
 +
   
 +
    retVal = recursiveSum( A, len( A ) )
 +
    return retVal
 +
 +
def recursiveSum( A, n ):
 +
    if n==1:
 +
        return A[0]
 +
 +
    return A[0] + recursiveSum( A[1: ], n-1 )
 +
 +
def main():
 +
    Array = [ 5, 10, 20, 50, 5, 10 ]
 +
    print( "Array = ", Array )
 +
    print( "sum( Array ) = ", sumUp( Array ) )
  
 +
main()
 +
</source>
 +
<br />
 +
==Restrictions==
 +
<br />
 +
* Your search implementation must use recursion to find the item searched.  Submitted programs that do not use recursion will be given a failing grade.
 +
* If you use material not in the class Web page or the on-line textbook we used for class, you need to list references to them in the header of your program.
 +
* Your program should be well documented and readable.  Points will be removed for poor documentation.
  
−
<onlydft>
+
<br />
 +
=Problem 4=
 +
<br />
 +
This problem is a quiz on Moodle that pertains to Problem 3, and will ask you questions about the recursive properties of the '''binSearch()''' function.  Even if you do not write a correct solution for Problem 3, this will not prevent you from being able to answer these questions. 
 +
<br />
 +
Please answer the quiz on Moodle, in the '''Quiz on BinSearch section'''.
 +
<br />
 +
<br />
 +
<br />
 +
=Problem 5=
 +
<br />
 +
Assume that we want to create a 16-bit floating point format similar to the IEEE floating point format we have seen in class.
 +
This format uses all the rules we have studied as being intrinsic to the 32-bit format, including the ''exceptions'', and the ''biased exponent''.
 +
<br />
 +
In this 16-bit format, the sign, exponent, and mantissa are as follows:
 +
<br />
 +
* The most significant bit is the sign bit: 0 for positive, 1 for negative
 +
* The next 4 bits are the exponent.  The stored exponent is offset by a bias relative to the true exponent.
 +
* The lower 11 bits are the mantissa, which assumes a hidden 1.  All numbers, as with the 32-bit format, are normalized as 1.bbb...bbb x 2^(true exponent).
 +
<br />
 +
==Questions==
 +
<br />
 +
Section 5 of the Final Exam section on Moodle contains several questions relating to this format.
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
</onlydft>

Latest revision as of 17:48, 10 December 2017

--D. Thiebaut (talk) 16:23, 29 April 2017 (EDT)


...

Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC231_Final_Exam_2017&oldid=32379"