COSC2430: Programming and Data Structures
HW3: Database System
1 Introduction
You will write a C++ program to simulate database operation (add, get and delete).
2 Input and Output Specification
The records input file is very clean (but may contain duplicated records) and have uniform attributes(columns). Each
record stream begins with operation add, delete or get, then follows by a space and a record. For add operation, you
will need to add a record with full attributes. However, when you do delete or get operation, you may only have partial
attributes. For get operation, you need to output the result in the origin record order and an empty line.
Example of input files (between the lines)
input1.txt
add {id:1234567,first:Mary,last:Green,DOB:1996-10-03,GPA:4.0}
add {id:1234568,first:Peter,last:White,DOB:1997-05-22,GPA:3.8}
add {id:1654238,first:Nick,last:Park,DOB:1995-08-18,GPA:4.0}
add {id:1234587,first:Katy,last:Green,DOB:1995-08-18,GPA:4.0}
get {GPA:4.0}
delete {first:Mary}
add {id:1234567,first:Mary,last:Green,DOB:1996-10-03,GPA:4.0}
get {last:Green,GPA:4.0}
output1.txt
{id:1234567,first:Mary,last:Green,DOB:1996-10-03,GPA:4.0}
{id:1654238,first:Nick,last:Park,DOB:1995-08-18,GPA:4.0}
{id:1234587,first:Katy,last:Green,DOB:1995-08-18,GPA:4.0}
{id:1234587,first:Katy,last:Green,DOB:1995-08-18,GPA:4.0}
{id:1234567,first:Mary,last:Green,DOB:1996-10-03,GPA:4.0}
3 Program specification
The main program should be called ”database”. Call syntax is as follows (from the OS prompt):
./database input=input1.txt output=output1.txt
Notice that the file name will not necessarily be the same every time. Therefore, your program will have to take that
into account.
4 Requirements
• Homework is individual. Your homework will be automatically screened for code plagiarism against code from
the other students and code from external sources. If you copy/download source code from the Internet or a
book it is better you acknowledge it in your comments, instead of the TAs detecting it. Code that is detected
to be copied from another student (for instance, renaming variables, changing for and while loops, changing
indentation, etc) will result in ”Fail” in the course and being reported to UH upper administration.
• The maximum number of records is 100,000. Timeout is set to 2s. That said, your program must get the result
file in 2 seconds.
• For each operation add, get and delete, you need to do it in O(max(k, n)) time complexity at maximum,
where n is current number of records in the database, k is the number of attributes in one record. Failing
to do this is likely to get a timeout error. That said, hash table and binary search tree are preferred. Any
data structures and algorithms in stl library are allowed.