Project 3

Last modified: November 11 2008 08:58:33 AM

For this project, you are allowed to work with a partner. You can choose to work with at most one person for the entirety of the project. If you work with another person, both names should appear in the solution, however, EACH OF YOU NEED TO SUBMIT the assignment. Also note that if you choose to work with a partner, you will be required to implement extra functionality as described below.

Description

This assignment has two distinct parts. The first is an interactive part designed to allow you to explore and critique the code of other students in the class. The second is designed to bring together the previous two assignments into one fully-functional assignment.

More Details - Part One

For part one, you will be critiquing the project one submission of up to three other people in the class. To complete this part of the assignment, you are required to complete the following tasks:

(1) Attend recitation the week of 11/10 and form a group of at minimum three and at most four students to work on this part of the assignment with. You will hand in a sheet with the names of the students into Jeff by the end of recitation. Attendance will be taken this week and will be part of your grade on this project. During this time you should also exchange emails and contact information. If possible, you should also email all the members of the group a copy of your project one code (even if not completely implemented or working).

(2) Either in recitation or shortly thereafter, you should decide which two member's code submissions will be critiqued first. The work of the group is to read over the code of the member who is to be critiqued and to write notes on a hard copy of the code about the following:

1. Good points about the code
2. Bad points about the code
3. Places where the code could be improved

These notes on the hard copies of the code will be handed in as part of the submission for this assignment. You will bring these notes with you to the next recitation.

(3) During the week of 11/17 in recitation, your group will meet to critique the code of the first two members. Attendance will be taken at this recitation as well. Each critique will last 21 minutes. It will follow the format discussion in lecture on 11/10, summarized here:

1. 7 minutes - good points about the code (Each member should articulate at least two good points.)
2. 6 minutes - bad points about the code (Each member should articulate at least two criticisms.)
3. 6 minutes - improvement points (Each member should articulate at least two improvements.)
4. 2 minutes - wrap up where one person talks reiterates the good of the code without emphasis or mention of the bad parts.

During this process, the code author should not participate in the conversation, but should rather be taking notes on what the group members have said to be used in the writeup. After the process is complete, the written notes and hard copies of the code should be given to the author. It is most important to remember that this process is not a process of criticism, but of critique and improvement. Make sure that the tone of the group stays positive even through the critical parts.

(4) The authors whose code is critiqued should go back and write up their response to the critique as described below. Preparation needs to begin for the next two code reviews by repeating steps 2 & 3 for the week of 12/1 (after Thanksgiving).

(5) The writeup. This is what you will hand in on the due date (or earlier) for this part of the assignment. You will create a hard copy document that contains the following information:

The hard copies with annotations from each of the group members of your code. Make sure that the group members indicate whose comments are whose.

A response paper about this experience, which answers the following questions: What were 2 good points that were mentioned about your code that made you feel good about the work you had done? What was 1 bad point about your code that you actually knew before you started the critique? What was 1 bad point about your code that you didn't know before the critique? What were 2 things you felt were the best suggestions for improvements of your code? Overall what did you learn during this process (in regards to your own code or someone else's or the process in general)? I would expect that this part of the paper would take no less than three to four pages double spaced. Although that is not an official graded requirement, it gives you an idea of how in depth I would like the analysis.

On a separate page, include any information about your fellow group participants that will help me in the grading of this assignment. Points that should be especially noted are group members that did not participate, group members who did not engage in the process, group members who were not open to criticism, or group members who you felt helped you and others in the group the most. These comments do not have to be long, just enough to give me an idea about the level of participation of each member.

More Details - Part Two

For this part, you are still allowed to work with a partner, but only one other person. If you choose to work with a partner, pay special attention to the parts of the assignment that need to be implemented by those working with a partner.

For this assignment, you will be combining the previous two assignments to make a system that reads in a file and creates a Huffman tree for the elements in a file, and then produces the encoded Huffman file. You do not need to create the intermediate word/frequency file any longer if you don't want to.

If you are working alone or in a pair, you are expected to be able to read in a file of significant size. We will be testing your files on books from the Guttenberg project. Make sure your program can handle it. Your parsing routine is not expected to be any smarter than it was before, but feel free to make improvements upon it if you wish.

If you are working alone or in a pair, your program is expected to create the Huffman tree for encoding by words and to create the associated encoded file. If you are working alone, your program does not have to handle punctutation and white spaces, those can be ignored. However, if you are working in a pair, you will need to handle those elements and encode them in the file for full credit.

If you are working with a partner, your program is also expected to create the Huffman tree for encoding by characters and to create the associated encoded file, once again including spaces and punctuation.

If you are working with a partner, you must also implement a way for an encoded file to be decoded. That is, you should devise a way to send the information about the Huffman encoding along with the file, so someone at the other end can decompress the file. The information about the Huffman codes can be sent in a different file and can be in whatever format you'd like. However, your program should then be able to decompress the files as well.

All projects should be able to tell the word with highest frequency from the file (or multiple if there is a tie), the word with lowest frequency (or multiple if there is a tie), as well as their frequency. The project should also report the average frequency of all the words in the file, and a way to query to find out if a particular word was in the original file.

Lastly, your project should use a hash table to compute the frequencies of words from the original file. You should be able to report the total number of collisions detected when inputting information into your hash table.

User Interface

The user interface to your program must provide the following functionality:

• Load a file to be Huffman encoded, encode by word and produce an output file.
• Load a file to be Huffman encoded, encode by character and produce an output file (partners only).
• Load a decompressor file for a Huffman encoding (partners only).
• Load a compressed file and recreate the original file (partners only).
• A way to find out which word from the original file had the highest frequency, which one had the lowest frequency and what the average frequency of the words were in the file.
• A way to find out if a word was in the file processed (yes or no).
• A print out of how many collisions occurred in your hash table while you were processing the input file. That is, how many times was probing necessary in order to find or put something into your hash table. This can be reported as a total number. Bonus if you point out how many resizings the table did and can report collisions based on the particular table sizes.

Testing

You should test your program with various inputs. You can create the test files yourself, but you should also test on one of the files of a book from the Guttenberg project if you are working with a partner.

You should create a test plan for this program. It is perhaps highly advisable to create a base test plan before you begin coding so that you can use it to form a strategy for implementation.

You should write up your test plan and your test cases in a file named testing.txt that you will submit with your project. You should make note in this file if there are any bugs found in your testing that you were not able to fix for the final submission.

What to submit

You should put all of your coding files in a directory named project3 and zip them creating a project3.zip file. You should submit this file using the electronic submission command.

Your zip should contain all of your .cpp and .h files, a description of the testing of your program in a file named testing.txt, as well as a makefile. You should also include a file named README that gives the name of the executable that is created when make is run as well as any pertinent user interface issues that the grader should be aware of when grading your submission. Failure for the grader to be able to use and grade your program will result in an automatic grade of 0 on this assignment.

Note also that your program MUST compile and run on our systems using your makefile or your grade on the project will be an automatic 0.

You must also submit a hard copy of the part one critique and response.

Due Date

All electronic files for this assignment need to be submitted by 11:59:59pm on Friday, December 5, 2008. Hard copies of the critique are due at the start of the final exam. Hard copy submissions of part one will be accepted early in class as well.