3. Carefully read the notes below before you start the exam.
By submitting the exam answers via WebCMS or give, you declare that all of the work submitted for this exam is your own work, completed without assistance from anyone else.
Please refer to the Student Conduct web site for details.
Notes
During the 3-hr Exam, you must not:
communicate with other students in any way
Your answers must be submitted using give or via WebCMS
If you believe that insufficient information has been provided to answer a given question, then you should write any assumptions (as comments in your code, or in the PDF) that you think are necessary to complete the question and continue work from there.
2. Submission:
You can submit your exam solution either using:
i) WebCMS: Login to Course Web Site > Exam > Final Exam > Final Exam Paper
> Make Submission > upload required files > [Submit]
Or: : ii) The give command: give cs9319 exam makefile q1.cc q2.cc
q3.cc q4.pdf q5.pdfAssignment Project Exam Help
3. Downloads
Downloads: exam.tgz or exam.zip Both .tgz and .zip files contain the same material.
Each archive contains a sample makefile; an answer template file for each programming question and a sample test file for each programming question.
4. How to Start:
read these notes carefully and completely
download one of the archive files above unpack the downloaded file
for programming questions, modify and put your code in the corresponding
.cc file
modify the supplied makefile accordingly so that the make command will generate a correct executable program from your .cc file
for written questions, type and/or draw your answers using an appropriate
software that can save them as PDF
login to wagner or a CSE linux machine, and test your makefile and programs the sample test files provided are provided for requirement clarifications, you
are expected to make more tests yourself to check for your program correctness submit all the Required Files via WebCMS3 (or give) as described above End of Notes
Exam Questions
%wagner> cat test1.txt
BILL GATES%wagner>
%wagner> ./q1 test1.txt 0.2572167752 0.2572167756
%wagner>
Instructions:
Put all your code in the provided q1.cc. Modify the makefile accordingly.
Suppose T is a text file that contains at least 1 and at most 5120 characters with
ASCII value between 0 and 126 inclusively, and it is always ended with a newline
(the only newline in the file). Write a BWT decoder (called q2) that reverses the BWT encoded T back to the original T. q2 accepts two commandline arguments: the name of a BWT encoded file; the output filename. The following is a simple test of q2 using the provided sample test:
wagner % ./q2 test2.bwt myoutput.txt wagner % diff myoutput.txt test2.txt wagner %
Instructions:
Put all your code in the provided q2.cc. Modify the makefile accordingly.
Suppose T is a text file that contains at least 1 and at most 5120 characters with
ASCII value between 0 and 126 inclusively, and it is always ended with a newline
(the only newline in the file). Write a BWT backward search program (called q3)
wagner % ./q3 test3.bwt ATATA
68 wagner %
Instructions:
Put all your code in the provided q2.cc. Modify the makefile accordingly.
Given the text string below:
jejunojejunostomy
a. What is its entropy?
b. Draw a Huffman tree based on the letters and their
corresponding
distributions for the above text string (Do not need to draw trees for the intermediate steps).
c. Provide the resulting Huffman code for each letter.
d. What is the average number of bits needed for each letter, using your Huffman code? How does it compare to the entropy ? (i.e., equal/larger/small and why) Instructions:
Save your answer and/or drawing as a file called q4.pdf in PDF format.
Using the linear-time SA construction algorithm discussed in the class, derive the Burrows Wheeler transform BWT(S) of character sequence S:
database$
Show all the steps involved. After that, derive the Move-to-Front transform of the BWT(S), assuming we use the 255 ASCII symbols as the symbol table. Note: If you need an ASCII table, use the “ascii” command available on CSE linux machines.
Instructions:
Save your answer and/or drawing as a file called q5.pdf in PDF format.
End of Exam
