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.

Reference no: EM131989

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.

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

  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.

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Recursive tree algorithms

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

  Determine the mean salary as well as the number of salaries

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

  Currency conversion development

Currency Conversion Development

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

  Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

  Data structures for a single algorithm

Data structures for a single algorithm

  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.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd