CSE 104 – Data Structures & Algorithms
Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University
CSE104 RESIT Coursework
Learning Outcomes
On successful completion of this assignment, students are expected to:
– understand and be able to apply a variety of data structures, together with their internal representation and algorithms;
– be able to make informed choices between alternative ways of implementation, justifying choices on grounds such as time and space complexity;
– be able to select, with justification, appropriate data structures to ensure efficient implementation of an algorithm.
To Do: Design and code a Java program that:
1. Requests from the user for a text filename to read the text inside, then it counts the frequency of each letter that file contains. There is no need to differentiate between upper and lower cases while punctuation marks are ignored. For this assignment purpose, the text file should be named as “Huff_in” with only letters inside. The program’s frequency table output should be like this:
a 12 c7
e 17 f4 k5 ……… u3
2. Based on the frequency table derived, a ternary Huffman codebook manager is implemented in your program that produces as output a codebook (in tabular format) that encodes letters based upon an input frequency table while the code generated should consume minimum bandwidth using these for codes: {0, 1, 2}, e.g. symbol ‘e’ is encoded as ‘0’, ‘a’ as ‘12’, ‘c’ as ‘112’, etc.
3. Corresponding ternary Huffman encoder & decoder are also implemented that carry out the encoding or decoding task based upon ternary codes received and a codebook as part of input. The encoder encodes input letters based on the specified codebook. The decoder will decode letters from ternary codes received using the codebook.
Coursework Submission
You should submit your Java program code files together with your report to the entry I provided on ICE. The submitted program solution should be well commented together with another 4-page report with a file name “Report.pdf” or “Report.doc” (or docx).
The report should not exceed 4 pages, without counting your .java files submitted separately from this report) with the module title and your name/student number & signed
CSE 104 – Data Structures & Algorithms
Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University
. Your report should
, and how they are tested in your programs. You should also analyse the and the
developed (i.e. cost of running time asymptotically).
Marking
The mark distribution (100% total) is arranged as follows:
This assignment: 100% of the RESIT marks.
declaration for non-plagiarism shown on the title page
you have designed & why they are used
motivate &
explain your data structure(s), what data structures/algorithms (rendered in pseudo code)
space complexity
(i.e. memory costs) of your data structures
time complexity of your algorithms
1. Correctness, efficiency, conciseness, & readability of your codes worth up to 75%:
codebook manager 25%, encoder 25%, decoder 25%
2. Your report worth up to 25%.