CSC231 Final Exam 2017

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

---

This exam is due on May 12, at 4:00 p.m..
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.
All five problems are worth the same number of points (20/100).
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.

Problem 1: C Programming

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.
Here is an example illustrating how your program should work.

• Create a text file called quote.txt containing the following 3 lines:

Believe in yourself! Have faith in your abilities! 
Without a humble but reasonable confidence in your own powers 
you cannot be successful or happy. --Norman Vincent Peale

• Run grep and search for various words in the file:

231b@aurora ~/handout $ ./231grep in quote.txt
Believe in yourself! Have faith in your abilities! 
Without a humble but reasonable confidence in your own powers 
you cannot be successful or happy. --Norman Vincent Peale
231b@aurora ~/handout $ ./231grep faith quote.txt
Believe in yourself! Have faith in your abilities! 
231b@aurora ~/handout $ ./231grep Faith quote.txt
231b@aurora ~/handout $ ./231grep but quote.txt 
Without a humble but reasonable confidence in your own powers 
231b@aurora ~/handout $ ./231grep -i believe quote.txt 
Believe in yourself! Have faith in your abilities! 
231b@aurora ~/handout $ ./231grep confidence doesnotexist.txt
grep: doesnotexist.txt: No such file or directory

• Your program should behave exactly the same way.

Implementation Details

• Your program needs to support only the "-i" switch.
• The order of the command-line parameters will always be

1. switch (if present)
2. word
3. file name

Testing

• Your program will be tested by comparing its output to the output of grep, using diff.
• You know enough to be able to create your own test script that should be able to inform you of whether your program's output is correct or not.

Submission

• Submit your code on Moodle, in the grep section of the final exam.

Problem 2: Fixed Point Numbers

Take the quiz on Moodle regarding the Fixed-Point number system.

Problem 3: Assembly Programming

Write a program that contains a recursive function called binSearch, that searches a sorted array of integers for an integer key.
Your program will be linked with a separate main program that will call your function and will pass it the following parameters:

1. the address of the array,
2. an integer key, which is the integer we are searching for in the array,
3. a low index, identifying the lowest bound of the interval being searched, and
4. a high index, identifying the upper bound of the interval being searched.

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.
The Python function search() given on this page is exactly what you need to translate to assembly.

Example Main Program

You can use the following main program to test your binSearch function. 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. In particular, if eax contains -1, then _printInt will print it correctly (_printDec would print 4294967295 instead).

;;; test program for binSearch()
;;; D. Thiebaut
;;; main program that will call the recursive binSearch
;;; function 4 times, on 2 different arrays, with 2 different
;;; keys.
;;; To assembly, link and run:
;;; nasm -f elf main.asm
;;; nasm -f elf binSearch.asm
;;; nasm -f elf 231Lib.asm
;;; ld -melf_i386 -o main main.o binSearch.o 231Lib.o
;;; ./main
;;; 28
;;; -1
;;; 2
;;; -1
;;;	
	section .data
table1	dd	1,3,5,10,11,20,21,22,23,34
	dd	40,41,42,43,45,48,50,51,100
	dd	102,103,200,255,256,1000,1001
	dd	1020,2000,3000,4000,4001,5000
TABLE1LEN equ	($-table1)/4

table2	dd	10,20,30,40,41,50,60,80,90,100
TABLE2LEN equ	($-table2)/4


	section	.text
	
	extern	_printInt
	extern	_println
	extern	binSearch
	


;;; -------------------------------------------------------------
;;;                        MAIN PROGRAM
;;; calls binSearch on two different arrays, each time for 2
;;; different keys.  The values printed should be:
;;; 
;;; 	28
;;; 	-1
;;; 	2
;;; 	-1
;;; 
;;; -------------------------------------------------------------
	global 	_start
	
_start:	
	;; binSearch( table1, 3000, 0, TABLE1LEN-1 )
	;; returned value should be 28
	
	mov	eax, table1 ; pass table1
	push	eax
	mov	eax, 3000	; search for 3000 in table1
	push	eax		
	mov	eax, 0
	push	eax
	mov	eax, TABLE1LEN-1
	push	eax
	call	binSearch
	call	_printInt
	call	_println

	;; binSearch( table1, 2, 0, TABLE1LEN-1 )
	;; returned value should be -1
	
	mov	eax, table1
	push	eax
	mov	eax, 2		; search for 2 in table1.
	push	eax		; 
	mov	eax, 0
	push	eax
	mov	eax, TABLE1LEN-1
	push	eax
	call	binSearch
	call	_printInt
	call	_println	

	;; binSearch( table2, 30, 0, TABLE2LEN-1 )
	;; returned value should be 2
	
	mov	eax, table2
	push	eax
	mov	eax, 30		; search for 30 in table2
	push	eax
	mov	eax, 0
	push	eax
	mov	eax, TABLE2LEN-1
	push	eax
	call	binSearch
	call	_printInt
	call	_println

	;; binSearch( table2, 2, 0, TABLE2LEN-1 )
	;; returned value should be -1
	
	mov	eax, table2
	push	eax
	mov	eax, 2	; search for 2 in table2
	push	eax
	mov	eax, 0
	push	eax
	mov	eax, TABLE2LEN-1
	push	eax
	call	binSearch
	call	_printInt
	call	_println
	
;;; exit
        mov     ebx, 0
	mov     eax, 1
	int     0x80

Additional Information

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.

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()

Restrictions

• 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.

Problem 4

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.
Please answer the quiz on Moodle, in the Quiz on BinSearch section.

Problem 5

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.
In this 16-bit format, the sign, exponent, and mantissa are as follows:

• 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).

Questions

Section 5 of the Final Exam section on Moodle contains several questions relating to this format.