ECE264 Programming Assignment 2

Friend Activity Database

The test sets for grading can be downloaded here.  WARNING: some test set is huge in file size.  They may use up your disk quota if not cleaned up properly.  Before extracting the files, please make sure that your storage quota is sufficient (for ECN accounts).

(Thursday 2/26) Some details are updated.  They are marked blue (newer updates are highlighted).

Notice: The programming assignments are graded by machines.  Your program will only be graded based on input and output.  No one will look into your code and give you partial credit.  If your output is incorrect for every test input, you will receive zero, no matter how minor the errors are.  Therefore, it is crucial that you read this specification very carefully and follow every rule.

You are very popular and have many friends. They like to tell you what they are doing. Please write a program to keep track of these friends' activities.

Purpose: In this programming assignment, you learn how to handle data using a structure (or structures) and handle unknown sizes using a linked list (or linked lists). You also learn how to distinguish different strings and extract information from the strings.  The input data comes from a file. Since this file can be very large, your program can read the file only once.

Input and Output

Your friends may tell you three types of activities: whom they meet and where they go. Each activity is marked with the date. From time to time, You want to know the friends' past activities by asking "What has this friend done?" or "What happened on this date?" Since we have not explained how to build GUI, all inputs and outputs will use text through files. 

The input file may be arbitrarily long. Each line can have one of the five following formats:

1. A year/month/date friend1 meets friend2
2. A year/month/date friend visits location
3. Q year/month/date
4. Q Friend
5. R friend leaves town

The first two add activities to your friend database. The third searches the database and reports everything that happened on that day. The fourth reports everything known so far related to this friend.  When your program reads the activities, the program produces no output. If an input line is a question, your program has to answer the question and print the results. If a question has multiple answers, the results must appear in the same order as the input file. The last removes everything related to the friend. It is possible that the friend moves back later.  In that case, treat it as a new friend.

Sample Input and Output

• Sample #1:  input100 and output100
• Sample #2:  input999 and output999

The sample solution program is also available (click here).  After downloading, you may need to run "chmod u+x pa2" to grant executable permission to this file.  This sample solution works on Linux system with CPU based on Intel-x86 architecture.  You should be able to run this program on MSEE190PCx machines.

Always use "diff" to detect difference.  You may use switches '-bB' to ignore difference in blank lines and white spaces since they will not be taken into consideration when your program is graded.  Notice that the sample input and output are only for self-checking.  Your program will not be graded with these inputs.  Passing these inputs does not necessarily guarantee full score.  If you want to test your program more intensively, please make use of the input generator and sample solution program.

The source code for input generator can be downloaded here.  The original version has a limit on the ending date of events, therefore won't create an input more than about 2000 lines. If you are not satisfied with the generated input, you may modify the source code and create your own version.

Assumptions and Requirements

• Time can move only forward. Any activities occurring later in the input file must not be earlier (in the date) than  an activity earlier in the file.
• The activities do not duplicate. It is unnecessary to check duplicates. If there are indeed duplicates in the input file, treat them as two activities.
• If a friend leaves town, delete all information related to this friend and release memory immediately.
• Your program has to release memory before it terminates.
• The questions ask what is currently stored in the database. If there is no information, the program reports "I do not know anything about [friend | date].\n" If the same question is asked later, the answer may be different as more information is obtained.
• The date format is year/month/date. The year has four digits (such as 2009). The month is one or two digits (such as 3 or 11). The date has one or two digits (such as 9 or 27). There is no space between them.
• Each friend has first name and last name but there is no space, for example, MarkTaylor and SharonThompson.
• The location is also a single word, such as HarborAvenue and FirstStreet.
• The main function takes one additional argument as the name of the input file. If this argument is not provided, print "Need file name.\n" and terminate the program with -1 as the return value.
• If the input file cannot be open, print "Cannot open file.\n" and terminate the program.
• The program must be able to distinguish the five types of inputs described above. If a line is not in one of the five types, ignore this line (this should not occur in the input file).
• If a line is an activity, store the activity.
• If a line is a question, answer this question. If it is a question about a friend, remember to check both friend1 and friend2. If there is no answer from the current information stored in the database, print "I do not know anything about [friend | date].\n"
• Your program can read the input file only once. It cannot read the whole file to determine the length of the file and then process the file. The program cannot call fopen twice nor use fseek. Neither can you use anything like ungetc. 
• Your program must allocate and release memory while processing the file. The program cannot allocate a fixed-size memory at the beginning of execution.
• Each friend name and location name will have no more than 20 characters.  Each line in the input file will be no longer than 200 characters.
• You must use dynamic memory allocation.  Do not forget to free memory instantly when "R"(remove) input is encountered.  The grading test will run under limited amount of memory.  If you do not use memory efficiently, you may encounter "out of memory" failure and you might receive very low grade.

What to submit?

• The source code (including all .c and .h needed to generate the final executable). You must use at least three files (one .h header file and two .c source files.)  You will receive zero if everything is in a single file. Of course, you cannot submit three files and two of them are empty.
• Makefile to create the executable. Name the executable as pa2 (not PA2, not Pa2, not pa2.exe, or anything else). You will receive zero if your submission has no Makefile. The file name must be Makefile (This is a widely accepted convention.); any other name will be rejected.
• README to explain what you have done and how you do it. You need to explain how you store the activities, how to remove activities and how to find the answer for each question. The file name must be README, not readme, not Readme, not README.txt, not README.pdf, nor README.doc.
• Do not include object files, executable files, sample input, or sample output.
• You may upload the files as several attachments but it is recommended that you create a zip package containing the necessary files (source files, header files and Makefile).  You can name the source files, header files and the zip package arbitrarily, but make sure that the target executable of the Makefile is named "pa2" (all lower-case).  You will receive zero if there is no executable named "pa2" after running "make".

Grading (total 8 points)

This programming assignment will be graded by another program. Make sure your program's output is exactly the same as specified. Any deviation from the specification will likely lose points. You can use "diff" to compare the output of your program with the output of the sample program.

If you do not finish the complete program, explain clearly in README what your program can do. You may receive some points. If your program does not meet the specification and there is no README, you will receive zero.

• 1: report errors for missing one argument or the file cannot be open.
• 1: can read the input file line by line. If your program cannot store the activities nor answer the questions, print the input file. If your program can store the activities and answer questions, do not print the file.
• 2: can answer questions but provide only one line when multiple lines are expected.
• 2.4: can answer questions and all expected answers.
• 0.4: can handle extra long lines.
• 0.6: README explaining how to store the activities, how to remove activities and how to answer the questions.
• 1: programming style and clarity
  • 0.2 meaningful variable names (not just i, j, k, x, y...).
  • 0.2 proper indentation.
  • 0.2 proper names (noun for variables, verb for functions).
  • 0.2 one statement per line, no overly complex statements, no line exceeds 80 characters (at least one newline every 80 characters).
  • 0.2 sufficient comments in the code.
• -0.5: for each warning message reported by -Wall -Wshadow.
• -3: memory leak reported by valgrind. The program has to release allocated memory before the program terminates.
  • For self-checking:  You must receive "no leaks are possible" at the end of the valgrind report to pass the memory test.
• You will receive zero if your program contains one or multiple syntax errors or crashes during tests.
• You will receive zero if your program cannot run on msee190pcxx.ecn.purdue.edu.
• You will receive zero if the program does not dynamically allocate or release memory. If you allocate a large array, regardless of its size, you will receive zero. You must use a dynamic structure (such as a linked list).
• The lowest score is zero. You will not receive a negative score.

Notice: The programming assignments are graded by machines.  Therefore it will only be graded based on input and output.  No one will look into your code and give you partial credit.  If your output is incorrect for every test input, you will receive zero, no matter how minor the errors are.  Therefore, it is crucial that you read this specification very carefully and follow every rule.

No re-grade request will be accepted for programming assignments since the grade given by machine is deterministic.

Presubmission

You can submit before the deadline and receive a score of your program. The submissions will be graded 72, 48, and 24 hours before the deadline. You may correct mistakes and submit again before the deadline. Your final score for this assignment will be no lower than the score received in this "pre submission."  You are strongly encouraged to take advantage of this opportunity.

Late Policy

Everyone has a 7-day no-penalty extension to accommodate any expected situation. You do not need the instructor's approval to use this extension. This extension is not a new deadline. Do not use the extension unless you have truly exceptional situations that prevent you from submitting before the deadline. Do not procrastinate. Procrastination is a common reason of failures.

Performance

The score of your program is not determined by its performance. However, your program has to be "reasonably fast" so that it can be graded. If your program takes longer than 100 times of the sample solution, your program will not be graded and you will receive zero. The sample solution takes 50 milliseconds for an input file of 1500 lines. Your program cannot take more than 5 seconds for a similar input.

Do not use scanf or anything that requires inputs from keyboard.  This will cause timeout while your program is being graded and you will likely receive zero.

Hint

C provides a function sscanf to check whether a string has a particular format. Suppose oneLine is a string (char array) "A 2009/1/20 RobertMorgon meets CharlesJackson". The following statement is true

int year;
int month;
int date;
char friend1[strlen(oneLine) + 1];
char friend2[strlen(oneLine) + 1];

if (sscanf(oneLine, "A %d/%d/%d %s meets %s\n", & year, & month, & date, friend1, friend2) == 5)

{

    ...

}

The function sscanf checks whether oneLine starts with A and followed by three integers, separated by '/'. After the integers, there is another word, followed by "meets". Before the end of the line, there is another word.  There are five variables to match (year, month, date, friend1, and friend2). If all five are matched successfully, the function returns 5.  You can use sscanf to check other types of inputs.

If you do not know where to start, download this zip file, unzip it, and use it as a reference.