- Please Solve In C 1 (59.79 KiB) Viewed 52 times
Assignment 1 The Exam Scheduler I. Introduction Despite the speed of modern processors, computationally intensive problems remain a challenge. In many cases, interpreted languages (such as Java) are too slow to handle such problems. C Language and assembler, which execute 'close-to-the-silicon', are often the only practical means for solving such problems in a useful amount of time. Consider, for example, the following. Imagine there are n = 1000 students taking first year computer science courses. These students are drawn from many sub-disciplines within computer studies and they will each have their own very different exam schedules. Now assume that they all have to take their C Language exam in the same 2 hour block, any day of the week, between 9 a.m. and 5 p.m.. How does a scheduler find that 2-hour block of time amid all the conflicting schedules (assuming such a block exists), and perform that calculation in a reasonable time, given that the number of possible scheduling conflicts increases as O(n²)? II. Methodology We can represent each 8-hour exam day with one byte of information, where each bit represents one hour. If an hour is booked for an exam, we'll place a '1' at that location. If the hour is free, this will be represented by a '0'. So a day having a two-hour exam from 10:00 - 12:00 and a second, three-hour exam from 14:00 - 17:00 would be represented by the byte 0 1 1 0 0 1 1 1 i.e. 0 1 1 0 0 1 1 1 9:00 10:00 11:00 12:00 13:00 14:00 15:00 16:00 So to book a one hour block starting at time hr in a byte initially set to 0, you would OR that byte with block = 10000000 >> (hr - 9) (The actual bitmask will vary for longer exam durations. For example, to book a three hour exam, you'd start with 11100000.) Now consider how we would represent exam bookings for the entire week. The unsigned long long int data type contains 64-bits of information enough for the entire week, plus a byte left over. To store two weeks of exam bookings, you'll need two unsigned long long ints. Now consider how we would find an unbooked block of time. If we OR'd all the students' exam schedules together, then the available blocks of time would be where the O's are in other words, the hours when no one has any exams booked. The alternative, in most other languages, would be to create a large array to hold the booked/unbooked status of each hour of the day. Compared with this method, using the binary operations as outlined above ensures that program execution in C will be at least 64X faster than the conventional program just outlined. And given that C produces executable code that runs off the silicon, the true speed increase is probably closer to 100X. III. Implementation a. Since we'll be using 64-bit unsigned long long ints throughout this application, start by typedefing this data type as an uLLInt. (This notation will be used throughout the document.)
b. Create a menu similar to the one used in Lab3, with the following options: 1. display a student's exam schedule load a new exam booking 2. 3. find unbooked times 4. exit c. In a practical application, we'd store each student's scheduled exams in a file, and load these values into RAM memory in the binary form just indicated when required. Here, exam bookings are stored in a 2D array in the file "Assignment I - Exam Bookings files.zip", available on Brightspace with this document. Unzip this file and examine the .h files inside. All student booking data is contained in an examBookings [][] array (see next section for details). For testing purposes, use #include _test.h in your code, which contains the default examBooking [][] array. But when submitting your finished code, include the .h file corresponding to your student number. In short, the .h files in the zip file allow us to pre-load exam bookings without the trouble of having to enter the information at the command prompt, while avoiding the use of File I/O, to be discussed later in the semester. d. Each row in the examBookings [] [] array contains the following five pieces of information, in the order presented: the student's student number-typically a value between 0-20, for simplicity the week of the exam, i.e. '0' for the first week, '1' for the second. the day of the week, where 0 = Monday, 1 Tuesday, 2 = Wednesday,...6 = Sunday. i. ii. iii. iv. V. the start time, using the 24-hour clock. (Hence '14' indicates 2 p.m.) the duration of the exam, in hours e. Note that each student will generally have more than one exam, with each exam day/ time/ duration represented by one row of the array. For example, in _test. h. the student having student number 20 has the following information listed as: (20, 0, 3, 9, 3}, (20, 1, 3, 9, 3}, {20, 1, 4, 16, 1}, {20, 1, 5, 15, 2} This tells us the student has four exams booked, at the following times Week 1: Week 2: Week 2: Week 2: Thursday 9:00 12:00 Thursday 9:00 - 12:00 Friday 16:00 17:00 Saturday 15:00 - 17:00 f. For the first menu option, your program should provide a function displayStudentExamSchedule(), that prompts the user to enter the student number and then, using the appropriate information in examBookings [][] array for that student, displays the student's exam bookings for both weeks of the exam period, complete with day of the week and exam times, exactly as indicated above. g. In the second menu option, you'll want to prompt the user to enter the all exam scheduling information into examBookings, starting with the student number. (Note that you'll need to reset the default size of the 2D array to include a few extra rows for testing this functionality.) Call this function setExamBooking Time().
Assume the student will have a student number already used in the examBookings array, i.e. a value between 0 -20. Note: your code should first check to ensure that the student does not attempt to book an appointment in a time that is already booked. See the note on the display Unbooked Times() function at right, which uses the 'OR trick' mentioned above to simplify the detection of duplicate bookings. In short, setExam Booking Time() and displayStudentExamSchedule() perform complimentary functions. The latter converts each row of the array to printable output; the former takes user entered information and converts it to new rows in the examBookings array. h. For the third menu item, we'll need to convert the current examBookings array information into binary form. Stored as two uLLInt values, the information for the student whose exam information is given above would be: [0] = 00000000000000000000000011100000 00000000000000000000000000000000 [1] = 00000000000000000000000011100000 00000001000000110000000000000000 So your code will need to read through the examBookings array and translate this into an array in the form uLL Int binaryReservations[][2] containing the binary values whose 'recipe' is roughly sketch out in section II above. (Here, each row will store each student's booking information, and the two columns represent the first and second weeks of the IV. exam period respectively.) Call this function display Unbooked Times(). [Note that, to generate a bitmask for a test of X hours duration, simply start with 0xFFFFFFFFFFFFFFFF, shift this X values to the right, and bitwise invert the result.] Once the binaryReservations array is loaded, you should loop through each row (20 in the test.h file, one row for each student) of the array for either week (0 and 1 separately). Create a function-call it convertuLLintToArray() that converts the two cumulative uLLInt values back to a 2D array of the form {0, 0, 0, 13, 2}, {0 0, 1, 9, 1}, {0 0, 1, 12, 1}, {0, 1, 0, 9, 1}, {0, 1, 0, 16, 1}, {0, 1, 1, 16, 1}, etc. 3 > where the values shown indicate all the unbooked times in the exam schedule. Then use your displayStudentExam Schedule() function to display these unbooked times to the screen. Additional Information, Suggestions, Cautions, etc. a. You are not limited to just the four functions indicated-although you should provide at least these four as a minimum. In the interests of good coding practice, feel free to add additional functions you feel are necessary to help clarify program execution. b. Documentation is an essential feature of any program, and it is particularly essential here.
Document each function, as well as the file itself-being certain to include your complete name, as it appears in Brightspace, along with your student number, the date the code was written, and a brief description of its execution. Additionally, add inline comments where they clarify a line of block of code which would otherwise be unclear (e.g. bitwise operations will not be clear to the average user: obviously, this is the sort of code that must be clearly documented.) c. In your finished submission, replace_test.h with the .h file corresponding to your student number. This is the code that your program will be tested on. d. Your uLLInt arrays should be declared globally, before main () but after the #includes, so that they can be accessed inside any function; e. You may use pointers in your code, but they are not necessary to complete this lab. f. See Modules 2b and 3 for notes on the use of AND, OR, XOR and binary NOT operations. Marks/Evaluation IV. Submission Guidelines Your code should be uploaded to Brightspace (via the link posted) in a single zip file prior to the submission deadline. You can include the two relevant .h files, but please don't bother returning the original "Assignment I - Exam Bookings files.zip" file Make certain to name your zip file according to the following format: Assignment! Yourfirstname_Yourlastname.zip Corrections and Addenda Will be added as required. Check Brightspace to see if new versions of this document have been added. And corrections, comments, or clarifications to this document will be noted here. Requirement Documentation Followed the instructions in this document (including any late additions/changes), and in particular used the functions correctly, i.e. for the purpose described Code appears to execute correctly, i.e. no obvious defects Clarity of Code (terse is good, but not to the point of incomprehensibility) MINUS: late penalty; failure to cite sources; diagnostic strings output to the console, abnormal termination, seg faults thrown under certain circumstances; unusual, abnormal and erratic features displayed during execution, which may indicate the scanf() bug; documentation which is not part of the program itself (e.g. TODOS and commented-out code: these are for your purposes only: if it's not part of the program, I don't need to see it)...etc. Total: Mark 6 9 4 6 25