Problem 1:
Given N courses, along with their course strength, and M examination halls, along with their capacity; assign the courses to examination halls such that least number of invigilators are used. The additional constraints to the problem are:
i. For every S students, one invigilator has to be assigned. Every course assigned to a hall must have one invigilator assigned to it.
ii. Ensure that all the students for a given course are assigned to the same class room.
iii. If all students of the same course cannot be placed in the same classroom, flag the course for assignment at a later point of time.
The upper bound time complexity must be O(MN log M), and space complexity of O(1).
File formats
course.txt
cc_code strength
ex:
779 45
928 101
332 13
410 32
halls.txt
hallno capacity
ex:
1223 76
1234 45
2201 103
1217 95
Data structures: (Use dynamic arrays wherever possible)
Courses: list of courses with tuples containing at least (cc-code, strength, assigned)
Halls: list of examination halls with tuples containing at least (hallno, capacity, remaining, invigilator_count, assigned_courses)
Minimum list of methods to be implemented: (All methods in separate files)
a) readCourses(): creates the Course list from the input file
b) readHalls(): creates the Halls list from the input file
c) getNextCourse(): retrieves the next course to be assigned.
d) getNextHall(): retrieves the next hall in which a course has to assigned
e) assign(): this function uses a greedy choice to assign courses to halls.
f) count(): returns the number of invigilators required for assigning the courses to the exam halls.
Outputs:
Hall no followed by the list of courses assigned to it in each line.
Problem 2:
Data entry operators are paid on the basis of the correctness of the entries they make. For every correct entry they make, they are paid Rs. 100/-. If they miss an entry, they are penalized with Rs. 50. If they enter the wrong value, they are penalized with Rs. 200/-. Given the list of numbers entered by an operator and the actual list of values, compute the payment due to an operator. The algorithm must have time complexity of O(max(m,n)), where m and n are the lengths of the actual and entered lists respectively.
Input files:
actual.txt
entered.txt
One integer per line
Minimum list of methods to be implemented: (All methods in separate files) a) computePay(): computes the payment due for the entries considered so far.
Driver file for this problem must be named as prob2.c, and header file as prob2.h
Files to be mandatorily submitted: the driver files, header files, file (a)-(e) of problem 1, computePay.c for problem 2, the two readme files.