### Data structures and algorithm design

Assignment Help Data Structure & Algorithms
##### Reference no: EM131989

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.

#### Questions Cloud

 Write a program using binary search approach : Write a program using binary search approach Write a java class : Write a Java class called PQueue that extends the provided abstract QueueADT class. Data structures and algorithm design : Data Structures and Algorithm Design Who will be the main actors responsible for innovation : Who will be the main actors responsible for innovation? Plan for the optimal use of the promotional mix elements : Promotional strategy is a plan for the optimal use of the promotional mix elements. Impact on the strategies of foreign firms : How are they likely to impact on the strategies of foreign firms Research essay- arguing for change : Briefly identifies a problem and then uses research to support your proposal for change.

### Write a Review

#### Write the selection sort algorithm

Write the selection sort algorithm

#### Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

#### Describe sorting algorithms and how they work

Describe sorting algorithms and how they work

#### Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

#### Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

#### Addition and subtraction of numbers in binary

Addition and Subtraction of numbers in binary and round to the nearest decimal number with three significant decimal digits

#### C++ program to evaluate expressions combining set union

Create a C++ program to evaluate expressions combining set union, set intersection and parentheses

#### Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

#### How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

#### Data structures and algorithm design

Data Structures and Algorithm Design

#### Data structures for a single algorithm

Data structures for a single algorithm

#### Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.