Due: 5pm Friday 27, April , 2012

What to hand in:

• This is an individual assignment.
• You must now include a Make file with your projects. Separate your program into multiple files, at the minimum, data structure implementation should be in a separate file.
• Organize the subparts into separate directories, i.e. hw7a/, hw7b/ and hw7c/
• READMEs for all parts if there is programming
• Write-up for 7c
• Paper print out and electronic tar file copied to /home/dxu/submissions/cs246 as usual.

7a: Histogram of names - Linked List [100pts]

Based on your previous homeworks on the names data files, add the flag -h name, so that your program will print a histogram for the usage of that name over the years. The -h flag runs on a list of data files, which you can assume are given at command line. Like the last assignment, not providing the -h flag will result in the program entering the interactive mode. You do not have to retain functionality of your previous homeworks, i.e. -h can be the only flag you support in this program.

For example: hw7a -h Dianna names*

will print out the the following horizontal histogram which shows that 1950 was the year where my name was most popular (714 babies were given that name and it was ranked 221), and it's popularity has been declining, first holding steady around 200s and then dropping to 0 starting in 2005.

1900 0

1910 0

1920 0

1930    30(981)

1940                                                   496(226)

1950                                                                         714(221)

1960                                                                  653(243)

1970                                    351(347)

1980                      216(493)

1990             122(771)

2000                           259(854)

2001                           265(860)

2002                       226(976)

2003 0

2004                         241(976)

2005 0

2006 0

2007 0

2008 0

2009 0

2010 0

Construct a linked list for all names read from all files. Store the usage numbers and ranks for each year again as a linked list, within each struct for the individual names. One might argue that since we currently only have 21 data files, an array of 21 structs should suffice. But remember that new data files are available every year.

If a name is used for both genders, print a histogram for both.

The scale you use to plot the histogram is entirely upto you, the only requirement is that it fits the screen. Typical unix terminal window is 80x24, you may use larger sizes as most windows are resizable, but make sure you do not exceed reasonable screen sizes. 80 characters is usually about half the screen size on most monitors these days, so 160 characters really should be about as large as the width should get.

You may also plot the histogram vertically if you prefer, however it will probably be more headache to code. Java and its applet abilities would have been preferred for this application, interfacing with graphical APIs is much more work in C.

7b: Histogram of names - Bineary Search Tree [100pts]

Modify the previous part so that now the top-level linked list of names becomes a binary search tree instead. All other functionalities remain the same.

7c: Total Rank [25-100pts]

Discuss how to add back support for total rank - i.e. to be able to simply print the total rank of a name after the histogram. There are many ramifications in terms of data structure design, and trade-offs between run-time efficiency and memory requirements. Discuss your data structure design given the following senarios:

• Suppose that the priority is to search for a name quickly to print out basic stats, i.e. number and rank of a particular year, histogram, etc
• Suppose that the priority is to rank a name quickly
• Suppose that the priority is to use as little memory as possible

This part of the project will be worth an additional 75 points if you implement the total rank support. Use your best judgement to choose between the trade-offs.