Description
Goals This assignment is a programming assignment that is designed to get you ready for the project. The assignment is composed of three programming problems that you will need to submit separately, each with its own main program. Problem 1 Consider you have an embedded application to be deployed on a set of card readers for a classroom seats management and attendance system. An institute deploys this application on a set of 8 classrooms, with each classroom having 256 available seats. Seats are pre-assigned to students, where by the same seat will be occupied by the same student in all classrooms; i.e. no two students can have the same seat number ever. The seat number of the student will be hardwired on his card. Each student will stamp upon entering and upon leaving a specific class. A student cannot exist in two classes at any point in time. The whole idea is to be able to know how many students are there in any particular class, inquire about a specific student location in any class at any point of time, and to be able also to inquire on the availability of a specific student at any point in time. The maximum number of students that can go to any class is 256, and students are numbered from 0 to 255. Implement the needed C++ classes that model this problem. The classes will be used in an embedded application (card reader) where storage constraints applies, and thus they should be optimum from the storage point of view, while being as efficient as possible during execution. Also you cannot assume the existence of the STL in the target embedded deployment environment. Your classes should provide all the needed constructors and destructor, in addition to implementing the following methods: 1. Allow class users to reserve and avail classroom seats. 2. Implement a method that checks if a specific seat is occupied in any particular class. 3. Implement a method that returns the number of available seats in a specific class at any point in time. 4. Inquire about the location of the student. Apply all validations that you viable, and again, your classes should be self contained and should not use the C++ STL library, but should be based on built-in C++ types. Note: you can consider that all the eight card readers are synchronized Problem 2 Consider an embedded application to be deployed on a scanning device that checks in/out products into a manufacture inventory. The manufacture manufactures 256 different products each product can have up to 8 colors. Each product has a unique ID from 0-255. Each time an instance of a product is checked in the corresponding product stock is incremented, and each time checked out the stock gets decremented. Product stock should be categorized by product color. A product with empty stock cannot be checked out, and the inventory can have a maximum capacity of 256 items of each product per color. Implement the needed C++ classes to model this problem. This class will be used in an embedded application (scanning device) where it will run in an environment that you cannot assume the existence of the STL. The class should optimize both storage usage and execution efficiency. Your class should provide all the needed constructors and destructor, in addition to implementing methods that allow class users to add and remove product items to and from the inventory. Moreover, you need to implement methods that performs the following functionalities: Checks if a specific product and/or color exists in the inventory. How many items exist for a specific product ID. How many items exist for a specific product ID of a specific color. How many items exist for a specific product color; cross products. Number of product types having stock in the inventory. Again, your inventory classes should be self contained and should not use the C++ STL library but should be based on built-in C++ types. Problem 3 The MAX heap is a data structure that can be used by a priority scheduling. A priority scheduler will always need the highest priority processes to be stored such that when retrieving a process from its queue, the highest priority process is at the front end of the heap data structure and its retrieval requires the least amount of processing. You should assume that your class may be used as a utility class that can be used and deployed on hybrid systems and deployment environments. Using the below partial implementation, implement a C++ class for a MAX heap of integers that should represent the priorities of different processes. Your class should have the appropriate constructors (including a copy constructor) and destructor. In addition, your class should provide the following operators and functions: operator+ to allow for adding of two heaps (e.g., heap3 = heap1 + heap2 results in heap3 contacting the element of heap1 and heap2). operator+ to allow for adding a single integer to a heap (e.g., heap2 = heap1 + 5 results in heap2 containing the elements of heap1 and the value 5) operator[] to allow for accessing the individual elements of the heap as they were stored in a sorted array (e.g., heap[5] accesses the 5th largest element in the heap). operator= to allow heap assignments (e.g. heap1 = heap2 = heap3) operator+= to allow heap assignments (e.g. heap1 += heap2 and heap3 += 5) operator<< to allow for printing heaps on cout (e.g. cout << heap1 prints heap1 on cout). You have to use the below pseudo code and make it workable and extend it to achieve all the above requirements. class Heap { private: int * array; int MaxSize, Nel; void adjust (int a[], int i, int n); public: Heap(int MSize); bool insert (int item); bool delMax(int & item); ~Heap(); }; void Heap::adjust (int a[], int i, int n) { int j = 2*i, item = a[i]; while ( j <= n ) { if (j= a[j] ) break; a[j/2] = a[j]; j*=2; } a[j/2] = item; } Heap::Heap(int MSize):MaxSize(MSize) { array = (int *) calloc(MSize+1,sizeof(int)); Nel = 0; } bool Heap::insert (int item) { int i = ++Nel; if ( i == MaxSize) { cout << “heap size exceeded” << endl; return false; } while ( (i > 1 ) && ( array[i/2] < item )) { array[i] = array[i/2]; i/=2; } array[i] = item; } bool Heap::delMax(int & item) { if ( !Nel) { cout << “heap is empty” << endl ; return false; } item = array[1]; array [1] = array[Nel–]; adjust (array,1,Nel); return true; } What to submit 1. All your code. 2. You code should be split among header files (.h) and source files (.cpp), and all you implementation need to be in the source files. You need to have a very good reason for including implementation in header files, and an explanation of the motive needs to be included in your report. 3. Very detailed in-code documentation. 4. For each problem of the above mentioned 3 problems you need to provide a main program to show and illustrate all the functionalities that your program can perform. 5. A single make file that can compile the three programs by default or a specific program based on the command line arguments. 6. A report describing how to build the programs using g++, including all design decisions for the three problems, and explains anything unusual to the teaching assistant. The report should be in PDF format, and each assignment code should be in separate director named as problem. 7. Do not submit any object, or executable files. Any file uploaded and can be reproduced will result in mark deductions. Important Assump#ons: As stated in all problems, the deployment environment is either limited (problem 1 and 2), or undefined (problem 3). Some specifications that are built by default in the compiler’s builds should not be assumed for granted. Please read the documentation of QNX as an example of a real-time operating system that withdraws some of the features granted by some builds of the compiler for better performance. http://www.qnx.com/developers/docs/660/index.jsp?topic= %2Fcom.qnx.doc.ide.userguide%2Ftopic%2Fmemory_Illegal_dealloc_.html. This is just an example, and my point is to urge you to try to be as conservative as possible with practices you usually do and are guarded when the compiler default build options are being enabled. You are developing code that you do not know who is going to be using it, and where is it going to be deployed. How to submit: The git repo is now ready for you to checkout. Use this tutorial at https://git.soe.ucsc.edu/ git/index.html to setup you repo local version. Include ̃ everything under the folder hw2. Keep on updating your repository as many times as you need. When you are confident of your submission, submit the commit Id of the desired version to the ecommons. Grade This assignment is worth 10% of the overall course grade. The assignment will be graded on a 100% grade scale, and then will be scaled down to the 10% its worth. The grading of the assignment will be broken down to the following: 1. 10% for submitting the assignment. A submission that contains code and reports i.e. if you just submitted an empty assignment you will get nothing. This 10% does not account for the correctness of your assignment. 2. 30% for problem 1. 3. 30% for problem 2. 4. 30% for problem 3. Delays You have up to 2 working days of delay, after which the assignment will not be accepted and your grade in that case will be ZERO. For every day (of the 2 allowed day), a penalty of 15% will be deducted from the grade. And of course you will lose the 10% mentioned in point 1 above under the “Grade” section.