You need to write a valid C program that solves each of these problems it must read the input, as specified in the problem description then print the solution to the given problem for that input.
- Input is read from the standard input, in the same way that you read input from the keyboard as shown in lectures (e.g., using scanf). Output is also printed to the standard output, as you have seen (e.g., using printf).
- You must also include a brief report describing your solutions to the problems. This should be maximum two side of A4 paper and should give a description of how each of your solutions works. This should include describing the algorithm used to reach the solution, describing your use of any C language features (that were not discussed in lectures) and identifying any resources that you have used to help you solve the problems.
- Name each of your c files according to the problem number; i.e., problem 10xx should be in a file 10xx.c (where 'xx' is replaced by the actual number).
1. Problem 1077
Title: Birthday Lookup
Description
In this assignment, you will need to create a 'database' of birthdays that will be queried repeatedly.
First, a (non-specified) number of birthdays + names is specified. You will need to store this data in a binary search tree (BST). The nodes of the BST will contain the (birthday, name) pairs.
Once the birthdays are stored, a number of queries follows. These take the shape of numeric (D-M-YY) dates. For each queried date you need to return the person that has a birthday on that date, or, if the queried date is nobodies birthday, the name of the person whose birthday is the first after the query date.
- Each line corresponds to a valid date, and a name. (You do not have to worry about date validation; all dates in the input are valid dates.)
- Each date consisting of one string ("January", "February", ..., or "December"), one integer between 1 and 31, and one two digit integer representing the year (from 90 to 99, and then from 00 to 16).
- Each name consists of a first name and a last name. (i.e., you do not need to worry about compound names comprised of more than 2 'words')
- Please use structures to store the dates and names.
- Use malloc to dynamically allocate just enough space for all the data and data structures.
- The access time of binary trees depends on how "balanced" they are. So a perfect solution would deal with this issue.
Input
- the string "BIRTHDAYS_START"
- followed by the (date, birthday)-pairs
- followed by the string "QUERIES_START"
- followed by a number of user query in format day month year (e.g. "1 1 00" or 31 3 68).
Output
- the names of persons who have their birthday on the queried dates, or those of the first subsequent birthdays.
- In the latter case, this should be indicated by pre-pending "first subsequent birthday: " before the name.
- In the unlikely case that there is no next birthday, you should print "no subsequent birthday"
Sample Input
BIRTHDAYS_START
January 1 01 Molly Mcauliffe
January 1 00 Dennise Nigh
February 28 99 Erma Merrick
July 17 12 Linn Alvin
September 10 12 Delphia Bynum
July 1 00 Vania Jones
June 30 90 Brittney Gemmill
August 25 06 Aubrey Sherard
May 27 08 Marica Rising
October 1 03 Eugena Steele
QUERIES_START
1 1 00
3 7 12
30 6 90
6 7 16
1 1 90
Sample Output
Dennise Nigh
first subsequent birthday: Linn Alvin
Brittney Gemmill
no subsequent birthday
first subsequent birthday: Brittney Gemmill
2. Problem 1079
Title: Football Statistics II
Description
In this assignment, you are asked to process a list of outcomes of football games and process the results. You can assume that there are only 30 teams, but not much else:
- not every teams need to play against every other team
- some teams might not play a single match
- the number of matches between two teams need not be the same as that between other teams
- the number of home games might be different from the number of away games
- the total number of match results that you may need to process can be small, or very large.
The last point means that you cannot store the entire list of match results in memory, only aggregate statistics.
Since the statistics are fractional, make sure that you process the data using double precision.
Input
The input consists of:
- The number of matches played
- List of results for each match
Each row in the list has the form
home_team_id away_team_id goals_home_team goals_away_team
where the IDs are integers in the range [0, 29]. That is, you can assume that there are maximally 30 teams.
For instance:
3 8 1 0
encodes a 1-nil win for home team 3 against away team 8, and
16 1 0 0
For each team that played at least one match, output a row containing:
- team id
- win ratio (= #wins / #plays )
- win ratio on home games. This should be -1 in case of no home games.
- average point difference. E.g., "-0.25" would indicate that on average the team lost by 0.25 point per game.
All fractional output data should be truncated to 3 digits behind the decimal point.
The list needs to be ordered, based on team ID. (How else could it be black box tested?)
Sample Input
6
0 1 5 0
1 0 3 1
0 2 2 2
2 0 4 2
1 2 2 3
2 1 8 0
Sample Output
0 0.250 0.500 0.250
1 0.250 0.500 -3.000
2 0.750 1.000 2.750
