In this project, you are asked to simulate Distance Vector routing for a given network. The main goal of this project is to study the impact of different factors on the convergence times to optimal routes. You will be provided with multiple files that represent different network topologies.Your simulator would need build routing tables and then forward data packets until they reach their destinations based on the routing tables built.Each network topology file consists of a number of rows, each row represents a single edge in the network.There are three entries per row. The first entry is the node ID at one end, the second is the node ID at the other end, and the third entry is the cost of the link between the nodes which will be used in computing optimal routes. For example, a row with these values: 2 12 23 means that there is a link between node 2 and node 12 and that link has a cost 23.Here are three topologies to use: • Toplogy1.txt (5 nodes, 7 edges) • Toplogy2.txt (10 nodes, 20 edges) • Toplogy3.txt (30 nodes, 60 edges)Initially, every node is only aware of its immediate neighbors (and thus would not have a complete picture of the topology). To build routing tables, nodes will proceed in “Rounds”. At the beginning of every round, each node will prepare a DV packet that it would send to its immediate neighbors. DV packets include the source node and the list of nodes-costs pairs for what this node knows about the network. In every round, a pair of nodes that are connected will exchange their DV packets and update their tables.The above topologies were generated using BRITE. The grader may test/grade your code on different topologies than the ones provided above, so make sure nothing is hard-coded (even the number of nodes!).Your simulator should take as a line argument, which topology file to use along with the duration to run your simulation (e.g., how many rounds needs to be simulated).Recall that in a distance vector-based routing algorithm, each node would tell its neighbors, what it knows about the whole network. As nodes exchange information with their neighbors in every round, they update their routing tables if better routes are discovered.Each node would maintain a routing table that consists of < destination, cost, nexthop >. The DV packet each node sends is simply the destination and cost pairs (no need to send the next hop). When a node receives a data packet, it consults its routing table and forwards the packet to the next hop, which would do the same until the packet reaches the destination.What to Turn in • A short design document stating the overall design decisions made and data structures used. • The source code. • The“results document that includes the full routing table for each node (for the above 3 topology files) after convergence.• Please provide a single command line to compile your program and another single command line to test your code and make sure to provide a working example of the command line. You can assume that the topology file will be in the same directory as your simulator.• The TA must be able to compile and run the simulator on the CS Linux Servers. • You need to upload a single zipped file to Canvas. • In the Results document, answer the following questions (for each topology): 1. How many rounds did it take each network to converge? 2. What is the ID of the last node to converge in each network? 3. How many DV messages were sent in total until each network converged? • After convergence, have your simulator route the following data packets using the routing tables created, showing the path used from source to destination.1. For the first topology: node 0 receives a data packet destined to node 3. 2. For the second topology:node 0 receives a data packet destined to node 7. 3. For the third topology: node 0 receives a data packet destined to node 23.
In this project, you will further enhance your simulator to model pipeline stalls due to memory latency, and you will simulate a data cache to study the performance impact of caching.You should begin with a copy of your Project 3 submission. Additionally, I have provided a class skeleton for a CacheStats class intended to be instantiated inside your existing CPU class. You may add any functions, function parameters, etc. to it that you want.The simulated data cache should store 1 KiB (1024 Bytes) of data in block sizes of 8 words (32 bytes). It should be 4-way set associative, with a round-robin replacement policy and a write policy of write-back write-allocate. All blocks in the cache are initially invalid. For simplicity, assume the cache has no write buffer: a store must be completely finished before the processor can proceed. Since this is a data cache, only loads and stores access it; instruction fetches should still be assumed to hit in a perfect I-cache with immediate access (i.e., there is never a stall for an instruction fetch).Note that since you only have to model the hit/miss/timing behavior of the cache, you do not have to actually store any data in your cache model. It is sufficient to simulate the valid, tag, and dirty bits as well as the round-robin replacement policy.Your cache model will calculate and report the following statistics: • The total number of accesses, plus the number that were loads vs. stores • The total number of misses, plus the number caused by loads vs. stores • The number of writebacks • The hit ratioEvery time an access is made to the cache model, the cache model should return the number of cycles that the processor must stall in order for that access to complete. It takes 0 cycles to do a lookup or to hit in the cache (i.e., data that is hit will be returned or written immediately).A read access to the next level of the memory hierarchy (e.g., main memory) has a latency of 30 cycles, and a write access has a latency of 10 cycles. Note that an access resulting in the replacement of a dirty line requires both a main memory write (to write back the dirty block) and a read (to fetch the new block) consecutively. Because the cache has no write buffer, all stores must stall until the write is complete.Before computing the cache statistics, be sure to drain all the dirty data from the cache, i.e. write it back. Count these as writebacks, but do not count any stalls/latency resulting from them. Inside your Stats class, add a new function similar to the bubble() and flush() functions. This stall() function should stall the entire pipeline for a specified number of cycles. The Stats class should track the total number of stall cycles that occur during program execution.Your simulator will report the following statistics at the end of the program: • The exact number of clock cycles it would take to execute the program on this CPU • The CPI (cycle count / instruction count) • The number of bubble cycles injected due to data dependencies (unchanged from Project 3) • The number of flush cycles in the shadows of jumps and taken branches (also unchanged from Project 3 – not the values from Project 4)• The number of stall cycles due to cache/memory latency, new for Project 5 • The data cache statistics reported by the cache model I have provided the following new files: • A CacheStats.h class specification file, to which you’ll need to add member variables • A CacheStats.cpp class implementation file, which you should enhance with code to model the described cache and count accesses, misses, and writebacks• A new Makefile In addition to enhancing the CacheStats.h/.cpp skeleton, you will need to modify your existing Stats.h/Stats.cpp in order to implement memory stalls. You will also need to modify CPU.h to instantiate a CacheStats object, and CPU.cpp to call both CacheStats and Stats class functions appropriately to model cache behavior and resulting pipeline stalls. You’ll also need to change CPU::printFinalStats() to match my expected output format (see below).Here are the steps you should follow for this project: 1) Begin by copying all of your Project 3 files into a new Project 5 directory 2) Untar and add the additional files from TRACS to your project5 directory 3) Write your name in the header of CacheStats.cpp and CacheStats.h 4) Add the #include for CacheStats.h into your CPU.h file5) Instantiate a CacheStats object named cache in your CPU.h similar to your stats object 6) Complete the functions for stats.stall, cache.access, and others as needed. 7) Modify CPU.cpp to call cache.access HINT: you probably want to do this in CPU::mem() 8) Also modify CPU.cpp to call cache.printFinalStats() and remove any unnecessary output 9) Check your results using submit_test script 10)Upload to TRACS before the deadline – verify by getting the email confirmationYou can compile and run the simulator program identically to previous projects, and test it using the same *.mips inputs. Only sssp.mips yields interesting cache behavior; I’ll only grade your code using this one.If you examine CacheStats.h, you’ll notice that I’ve already defined constants for you for all of the cache configuration options you’ll need (e.g., number of sets, number of ways, block size, read miss latency, etc.).You should not need to change any of these defines. They are defined to be modifiable from the compilation command line, but for this project, I will not change any of them. You can even get away with not using these defined constants if you prefer.The following is the expected result for sssp.mips. Your output must match this format verbatim. Compare your output to the provided sssp.out file in the tarball using the diff command as in prior projects: CS 3339 MIPS Simulator Cache Config: 1024 B (32 bytes/block, 8 sets, 4 ways) Latencies: Lookup = 0 cycles, Read = 30 cycles, Write = 10 cycles Running: sssp.mips 7 1 Program finished at pc = 0x400440 (449513 instructions executed) Cycles: 2040814 CPI: 4.54 Bubbles: 1125724 Flushes: 51990 Stalls: 413580 Accesses: 197484 Loads: 146709 Stores: 50775 Misses: 12044 Load misses: 8559 Store misses: 3485 Writebacks: 5229 Hit Ratio: 93.9%The CacheStats skeleton already includes code to disable the cache (i.e., all loads result in a read access to the next level of the memory hierarchy, and all stores result in a write access). To explore the performance impact of adding a cache, you can compile your simulator with the cache disabled: $ make clean; make CACHE_EN=0 Re-run the simulator on sssp.mips. What happens to the CPI? How big is the difference?Additional Requirements: • Your code must compile with the given Makefile and run on zeus.cs.txstate.edu • Your code must be well-commented, sufficient to prove you understand its operation • Make sure your code doesn’t produce unwanted output such as debugging messages. (You can accomplish this by using the D(x) macro defined in Debug.h)• Make sure your code’s runtime is not excessive • Make sure your code is correctly indented and uses a consistent coding style • Clean up your code before submitting: i.e., make sure there are no unused variables, unreachable code, etc.SUBMISSION INSTRUCTIONS Submit all of the code necessary to compile your simulator (all of the .cpp and .h files as well as the Makefile) as a compressed tarball. You can do this using the following Linux command: $ tar czvf yourNetID_project5.tgz *.cpp *.h MakefileDo not submit the executables (*.mips files). Any special instructions or comments to the grader, including notes about features you know do not work, should be included in a separate text file (not inside the tarball) named yourNetID_README.txt.Use the script file submit_test provided for you on TRACS to confirm the contents of your tar file, ability to compile and execute on zeus, and check your output format using sssp.mips. The instructions are in the script itself. Submissions that do not untar correctly and compile on zeus with this script will receive zero points so you are highly encouraged to check your submission.All project files are to be submitted using TRACS. You may submit your file(s) as many times as you’d like before the deadline. Only the last submission will be graded. TRACS will not allow submission after the deadline, so I strongly recommend that you don’t come down to the final seconds of the assignment window. Late assignments will not be accepted.ACADEMIC HONESTY (excerpt from course syllabus) You are expected to adhere to the Texas State University Honor Code which is described here http://www.txstate.edu/honorcodecouncil/Academic-Integrity.html All assignments and exams must be done individually, unless otherwise noted in the assignment handout. Turning in an exam or assignment that is not entirely your own work is cheating and will not be tolerated.Group discussion about course content is NOT cheating and is in fact strongly encouraged! You are welcome to study together and to discuss information and concepts covered in class, as well as to offer (or receive) help with debugging or understanding course concepts to (or from) other students. However, this cooperation should never involve students possessing a copy of work done by another student, including solutions from previous semesters, other course sections, the Internet, or any other sources.Turning in an assignment any part of which is copied from the Internet, another student’s work, or any other non-approved source will result in a 0 grade on the assignment and will be reported to the Texas State Honor Code Council. Should one student copy from another, both the student who copied work and the student who gave material to be copied will receive 0s and be reported to the Honor Code Council.You should never grant anyone access to your files or email your programs to anyone (other than the instructor)!ACKNOWLEDGEMENT: This assignment, handout, and provided code are based on prior work by Molly O’Neil and Martin Burtscher. I am grateful for their support.
Cycle-accurate simulators are often used to study the impact of microarchitectural enhancements before they are designed in hardware. In this project, you will turn your emulator from Project 2 into a cycleaccurate simulator of a pipelined MIPS CPU.Most cycle-accurate simulators are composed of two parts: a functional model, which emulates the functional behavior of each instruction (e.g., your Project 2 emulator), and a timing model, which simulates enough of the cycle-level behavior of the hardware to allow it to determine the runtime of an instruction sequence. The simulator may also track and report other events of interest, such as the number of branches taken vs. not-taken.These counts are called performance counters. I have provided a class skeleton for a Stats class intended to be instantiated inside your existing CPU class. The Stats class has functions (some of which are defined already, some of which are blank and need to be filled in) that allow it to collect statistics from the CPU during the simulation of a program, and to model the timing behavior of an 8-stage MIPS pipeline similar to the one we have studied in class.The pipeline has the following stages: IF1, IF2, ID, EXE1, EXE2, MEM1, MEM2, WB. Branches are resolved in the ID stage. There is no branch delay (in other words, the instruction words immediately following a taken branch in memory should not be executed). There is also no load delay slot (an instruction that reads a register written by an immediately-preceding load should receive the loaded value). Just like the 5-stage MIPS pipeline, there are no structural hazards, and data is written to the register file in WB in the first half of the clock cycle and can be read in ID in the second half of that same clock cycle.For now, assume there are no forwarding paths: all sources must be read in ID, and a value must always be written back to the register file before it can be used as a source. The pipeline must inject the appropriate number of bubbles to ensure this for all read-after-write (RAW) data hazards. Note that trap 0x01 reads register Rs and trap 0x05 writes register Rt. Note that mfhi and mflo read the hi/lo registers, and mult and div write them. Note that the $zero register cannot be written and is therefore always immediately available.2 Your simulator will report the following statistics at the end of the program: • The exact number of clock cycles it would take to execute the program on a CPU with the hardware parameters described above. (Remember that there’s a 7-cycle startup penalty before the first instruction is complete) • The CPI (cycle count / instruction count) • The number of bubble cycles injected due to data dependencies • The number of flush cycles in the shadows of jumps and taken branches • The percentage of instructions that are memory accesses ( memory-op count / instr count) • The percentage of instructions that are branches (branch count / instruction count) • The percentage of branch instructions that are taken (taken branches / total branches)Note that the last two bullet points above refer to conditional branch instructions only (i.e., beq and bne instructions), not jump instructions. You are provided the following new files: • A Stats.h class specification file, which you should read carefully to understand the functions which should be implemented • A Stats.cpp class implementation file, which you should enhance with code to track the pipeline state in order to identify data dependencies and to model bubbles and flushes • A new Makefile In addition to enhancing the Stats.cpp/.h skeleton, you will need to modify your existing CPU.cpp in order to call the necessary Stats class functions.Don’t forget to #include “Stats.h” in the CPU class header file and instantiate a Stats class object in CPU. When modifying your existing CPU.cpp please follow this format example (you will have to change it as appropriate for each instruction). If you keep the calls to Stats on the same line as the register use it will be much easier to find mistakes.Additionally, by keeping the order rd, rs, rt it will help me debug your code if needed. writeDest = true; destReg = rd; stats.registerDest(rd); aluOp = ADD; aluSrc1 = regFile[rs]; stats.registerSrc(rs); aluSrc2 = regFile[rt]; stats.registerSrc(rt); You’ll also need to change CPU::printFinalStats() to match the expected output format (see below).This project is to be submitted individually, and you should be able to explain all code that you submit. You are encouraged to discuss, plan, design, and debug with fellow students. Unlike the prior assignments you do not have a complete set of outputs to compare, however you can check your results with the information provide in the project3_expected.txt file which is included in the tarball. You are encouraged to check your results with other students as well, but never share your source code.You must have a working copy of Project 2 to start this project. Begin by copying all of your Project 2 files into a new Project 3 directory, e.g.: $ cp -r cs3339_project2/ cs3339_project3/ Download and extract the additional files in provided cs3339_project3.tgz and add them to your project3 directory. You can compile and run the simulator program identically to Project 2, and test it using the same *.mips inputs.The following approach is recommended for your Stats class. Notify the Stats object whenever an instruction in the ID stage uses a register as a destination, and whenever an instruction in ID uses a register as a source. I’ve provided function definitions for this (registerSrc/Dest). When a register is used as a source, the Stats class should look for instructions in later pipeline stages (older instructions) that will write that register. This will allow Stats to identify data dependencies (RAW hazards). A bubble injects a NOP into the pipeline (an operation that doesn’t write any register).You’ll also need to keep track of flushes due to jumps and taken branches. A flush overwrites an existing pipeline entry with a NOP. You can check your timing results using the equation instrs = cycles – 7 – bubbles – flushes. The following is the expected result for sssp.mips which is included as sssp.out in the tarball.Your output must match this format verbatim: CS 3339 MIPS Simulator Running: sssp.mips 7 1 Program finished at pc = 0x400440 (449513 instructions executed) Cycles: 1627234 CPI: 3.62 Bubbles: 1125724 Flushes: 51990 Mem ops: 43.9% of instructions Branches: 9.6% of instructions % Taken: 60.5 4 Note that you can print the ratio a/b with 1 place after the decimal and a percentage sign using the following C++ code: cout
In this project, you will write a disassembler that reads MIPS machine instructions from a (simplified) binary executable file and prints each assembly language instruction to the screen.Write your disassembler code in the provided C++ code skeleton, disassembler.cpp. All of your code will go in the disassembleInstr function. You should read and understand the rest of the code, as it will form the basis for the remaining projects. Your disassembler only needs to support the MIPS instructions listed in comments in the code skeleton.Your disassembler must precisely match the output in the sample output files, including all whitespace and formatting. Note that all constants are in decimal representation except PC values and jump and branch targets, which are in hexadecimal.Please use the updated “green card” provided in class and posted on TRACS. Note that the green card says the sll instruction means ‘rd = rt
[pdf-embedder url="https://assignmentchef.com/wp-content/uploads/2024/12/Unordered-Containers-Homework-1.pdf" title="Unordered Containers Homework"] • Familiarization and practice with key/value association data structure usage and hash table concepts • Familiarization and practice using the STL’s unordered_map container interface• Reinforce the similarities and differences between sequence and associative containers • Reinforce reading persistent data from disk files and storing in memory resident data structures• Reinforce modern C++ object-oriented programming techniquesThis project analyzes words in English text using a hash table to store words. The main task is to count the occurrences of each word in a novel – called its word frequency. Text analysis using word frequencies is used in linguistics.You are given the public interface of class WordFrequency. Your task is to complete the class implementation.You are provided with starter code that forms your point of departure to complete this assignment: 1. main.cpp – This file is provided, requires no modifications, and will be overwritten during the grading process. Function main() orchestrates the flow of execution and tests your intermediate results along the way.2. WordFrequency.hpp/WordFrequency.cpp – The class has a single member attribute of type std::unordered_map, which is the C++ Standard Library’s implementation of a hash table, to store the association of words (key) to the number of times that word occurs (value).a. WordFrequency – This (default) constructor takes a reference to an input stream as a parameter defaulted to console input (e.g., std::cin). This function is to i. Read a single word at a time from the input stream until end of file. Words are delimited by whitespace as defined in standard C++.ii. For each word read, accumulate the number of times that sanitized word has appeared in the text as the word’s frequency.Constraint: Only “sanitized” words shall be added to the hashtable. For example, leading and trailing punctuation, parentheses, brackets, etc. should be removed, but intra-word punctuation should remain. A working sanitize function has been provided.b. numberOfWords – This function takes no arguments and returns the number of unique words. c. wordCount – This function takes a constant reference to a standard string as a parameter and returns the frequency of occurrence of that sanitized word, or zero if the word is not found in the hashtable.d. mostFrequentWord – This function takes no arguments and returns the most frequent word, or the empty string if the hashtable is empty.e. maxBucketSize – This function takes no arguments and returns the size of the largest bucket in the hashtable. See the unordered_map’s bucket interface at https://en.cppreference.com/w/cpp/container/unordered_mapRules and Constraints: 1. You are to modify only designated TO-DO sections. The grading process will detect and discard any changes made outside the designated TO-DO sections, including spacing and formatting. Designated TO-DO sections are identified with the following comments: ///////////////////////// TO-DO (X) ////////////////////////////// … /////////////////////// END-TO-DO (X) ////////////////////////////Keep and do not alter these comments. Insert your code between them. In this assignment, there are 8 such sections of code you are being asked to complete. 2 of them are in WordFrequency.hpp and 6 are in WordFrequency.cpp.2. This assignment requires you redirect standard input from “The Legend of Sleepy Hollow by Washington Irving.txt” and redirect standard output to “output.txt”.Reminders: • The C++ using directive using namespace std; is never allowed in any header or source file in any deliverable product. Being new to C++, you may have used this in the past. If you haven’t done so already, it’s now time to shed this crutch and fully decorate your identifiers.• A clean compile is an entrance criterion. Deliveries that do meet the entrance criteria cannot be graded. • Always initialize your class’s attributes, either with member initialization, within the constructor’s initialization list, or both. Avoid assigning initial values within the body of constructors.• Use Build.sh on Tuffix to compile and link your program. The grading tools use it, so if you want to know if you compile error and warning free (a prerequisite to earn credit) than you too should use it. • Filenames are case sensitive on Linux operating systems, like Tuffix.• You may redirect standard input from a text file, and you must redirect standard output to a text file named output.txt. Failure to include output.txt in your delivery indicates you were not able to execute your program and will be scored accordingly. A screenshot of your terminal window is not acceptable. See How to build and run your programs. Also see How to use command redirection under Linux if you are unfamiliar with command line redirection.Deliverable Artifacts: Provided files Files to deliver Comments main.cpp CheckResults.hpp 1. main.cpp 2. CheckResults.hppYou shall not modify these files. The grading process will overwrite whatever you deliver with the one provided with this assignment. It is important that you deliver complete solutions, so don’t omit these files. WordFrequency.hpp WordFrequency.cpp 3. WordFrequency.hpp 4. WordFrequency.cppStart with the files provided. Make your changes in the designated TO-DO sections (only). The grading process will detect and discard all other changes.5. output.txt Capture your program’s output to this text file using command line redirection. See command redirection. Failure to deliver this file indicates you could not get your program to execute. Screenshots or terminal window log files are not permitted.Readme.* Optional. Use it to communicate your thoughts to the grader • Frankenstein or The Modern Prometheus by Mary Shelley.txt • The Legend of Sleepy Hollow by Washington Irving.txtText files to be used as program input. Do not modify these files. They’re big and unchanged, so don’t include it in your delivery.Redirect standard input to The Legend of Sleepy Hollow by Washington Irving.txt sample_output.txtSample output of a working program. Use for reference, your output format may be different. But the contents should match. Do not include this file with your delivery.
• Familiarization and practice with key/value association data structure usage and binary search tree concepts • Familiarization and practice using the same key across associative containers to join the contents into a single view• Familiarization and practice using the STL’s map container interface • Reinforce the similarities and differences between sequence and associative containers • Reinforce reading persistent data from disk files and storing in memory resident data structures • Reinforce modern C++ object-oriented programming techniquesThis GroceryStore Inventory project builds on the GroceryItem, Shopping Cart, and GroceryItemDatabase from previous assignments by adding the maintenance of a grocery store’s inventory at the checkout counter. Here you are given a collection of customers (e.g., Woodstock, Lucy, Carlie) pushing their shopping cart, each already filled with the groceries from their shopping list.Each customer goes through the checkout line where the groceries are scanned and a receipt is given. As groceries are scanned, the store’s inventory is updated by reducing the number of groceries on hand for that grocery item. At the end of the day after all customers have been processed, you take inventory and reorder groceries that are getting low.You are provided with starter code that together with your work from previous assignments form your point of departure to complete this assignment. 1. main.cpp – Function main() orchestrates the flow of execution. A partial implementation has been provided. You are to complete the implementation.2. GroceryItem.hpp/GroceryItem.cpp – Reuse the GroceryItem class from your previous assignments. Unless you find an error or omission in your code, these files should require no modification.3. GroceryItemDatabase.hpp/GroceryItemDatabase.cpp – A partial implementation of the GroceryItemDatabase class has been provided. The previous assignment used the sequence container std::vector for the memory resident database.This assignment uses the associative container std::map, a binary search tree, associating a UPC with a grocery item. An updated GroceryItemDatabase.hpp incorporating this change is provided and requires no modifications. You are to modify GroceryItemDatabase.cpp by completing the implementation.Leverage the code you wrote in the last assignment adjusting for std::map vice std::vector. Function find(), for example, will no longer be implemented as a recursive linear search function. Instead, it should delegate to the map’s binary search function find(). If duplicate keys are discovered during construction, use the first occurrence.4. GroceryStore.hpp/GroceryStore.cpp – A partial implementation of the GroceryStore class has been provided. You are to complete the implementation. GroceryStore.hpp requires no modifications. You are to modify GroceryStore.cpp by completing the implementation.a. GroceryStore constructor – This function takes as a parameter the name of the store’s inventory database file containing pairs of UPC and quantity, each pair on a separate line. Populate the store’s inventory database with the contents of the file. For example, the contents of “GroceryStoreInventory.dat” may look like: 0051600080015 36 0019600923015 34 0688267141676 36 0657622604842 25In this assignment, there are two text files used to persist data. Don’t confuse this file (GroceryStoreInventory.dat) that persists a store’s inventory with the file (Grocery_UPC_Database-Large.dat) used by class GroceryItemDatabase above that persists the full description and price of a grocery item. Both use the UPC as the key but contain quite different information.b. inventory – This function takes no arguments and returns a reference to the store’s inventory database. The inventory, designed as a binary search tree and implemented using the STL’s map class, is an association between UPC (the key) and the quantity on hand (the value). As a convenience, an alias called Inventory_DB has been created as part of the GroceryStore interface in GroceryStore.hpp. Use this alias in your work everywhere as appropriate.c. ringUpCustomers – This function takes a collection of shopping carts (i.e., a collection of customers with their shopping cart) and an optional receipt output stream as parameters and returns a collection of unique UPCs for groceriesthat have been sold. Pretend you have a lot of customers waiting in line to purchase the groceries in their cart. Ring up each customer individually while accumulating the groceries sold. As a convenience, aliases called GroceryItemsSold, ShoppingCart and ShoppingCarts have been created as part of the GroceryStore interface in GroceryStore.hpp. Use these aliases in your work everywhere as appropriate.d. ringUpCustomer – This function takes a shopping cart and a receipt output stream as parameters and returns a collection of UPCs purchased by this customer. Scan all the groceries in the shopping cart, print a receipt with an amount due, and deduct the groceries purchased from the store’s inventory. The logic to scan groceries and print a receipt should be carried forward from your last assignment. Look at last assignment’s posted solution if you need help. Add the grocery item to the collection of groceries purchased.e. reorderGroceryItems – This function takes a collection of UPCs for groceries sold and an optional reorder report output stream as a parameter and returns nothing. For each grocery item sold, check the store’s inventory for the quantity on hand. If the number of grocery items on hand has fallen below the REORDER_THRESHOLD, print a message indicating the current number on hand then order LOT_COUNT more by adding LOT_COUNT to the current number on hand. A sample report might look like: Re-ordering grocery items the store is running low on.1: {“00025317533003”, “Applegate Farms”, “Hotdog Uncrd Big Apple”, 12.57} only 8 in stock after selling 1 unit(s) below threshold (15), re-ordering 20 more 2: {“00041331092609”, “Goya”, “Frz Spnsh Omelet”, 16.84} *** no longer sold in this store and will not be re-ordered 3: {“00070596000647”, “Ultra Glow”, “Ultra Glow Black Soap”, 21.19} only 12 in stock after selling 1 unit(s) below threshold (15), re-ordering 20 moreProgram Overview: Sometimes it helps to see pictures of what you’re building. The following is just for information. Class Structure: To help you visualize the interface your three classes provide, and to summarize instance attributes for the developer, the class diagram on the right is provided.File Dependencies: To help you visualize the dependencies between included files, the diagram on the left is provided. Notice that each class has a header and source file pair, and that the class’s source file always includes the class’s header file. In this assignment, main.cpp requires only GroceryStore’s interface (header file). GroceryStore’s interface requires only GroceryItem’s interface, but GroceryStore’s implementation (source file) requires GroceryItem’s, GroceryItemDatabase’s, and of course GroceryStore’s interfaces.Data Types: To help you visualize the data structures, types and aliases, the following is provided: • GroceryItemsSold: a set of unique UPCs organized as a binary search tree. • Inventory_DB: an association from UPC to quantity on hand organized as a binary search tree. • ShoppingCart: a collection of groceries indexed by UPC organized as a binary search tree.• ShoppingCarts: a collection of shopping carts indexed by customer’s name organized as a binary search tree. Analogous to a matrix being an array of arrays, ShoppingCarts is a tree of trees. 79200299101 46689125962 83078113155 38100533036 62338822921 82815012003 91404518208 79200299101 12 46689125962 32 83078113155 27 38100533036 6 62338822921 18 82815012003 21 91404518208 13 79200299101 46689125962 83078113155 38100533036 62338822921 82815012003 91404518208 Peppermint Patty Charlie Brown Red BaronRules and Constraints: 1. You are to modify only designated TO-DO sections. The grading process will detect and discard any changes made outside the designated TO-DO sections, including spacing and formatting. Designated TO-DO sections are identified with the following comments: ///////////////////////// TO-DO (X) ////////////////////////////// … /////////////////////// END-TO-DO (X) ////////////////////////////Keep and do not alter these comments. Insert your code between them. In this assignment, there are 13 such sections of code you are being asked to complete. 5 of them are in main.cpp, 3 in GroceryItemDatabase.cpp, and 5 in GroceryStore.cpp.Reminders: • The C++ using directive using namespace std; is never allowed in any header or source file in any deliverable product. Being new to C++, you may have used this in the past. If you haven’t done so already, it’s now time to shed this crutch and fully decorate your identifiers.• A clean compile is an entrance criterion. Deliveries that do meet the entrance criteria cannot be graded. • Always initialize your class’s attributes, either with member initialization, within the constructor’s initialization list, or both. Avoid assigning initial values within the body of constructors.• Use Build.sh on Tuffix to compile and link your program. The grading tools use it, so if you want to know if you compile error and warning free (a prerequisite to earn credit) than you too should use it. • Filenames are case sensitive on Linux operating systems, like Tuffix.• You may redirect standard input from a text file, and you must redirect standard output to a text file named output.txt. Failure to include output.txt in your delivery indicates you were not able to execute your program and will be scored accordingly. A screenshot of your terminal window is not acceptable. See How to build and run your programs. Also see How to use command redirection under Linux if you are unfamiliar with command line redirection.Deliverable Artifacts: Provided files Files to deliver Comments GroceryItem.hpp GroceryItemDatabase.hpp GroceryStore.hpp 1. GroceryItem.hpp 2. GroceryItemDatabase.hpp 3. GroceryStore.hppYou shall not modify these files. The grading process will overwrite whatever you deliver with the ones provided with this assignment. It is important your delivery is complete, so don’t omit these files.GroceryItem.cpp 4. GroceryItem.cpp Replace with your (potentially updated) file from the previous assignment. GroceryItemDatabase.cpp main.cpp GroceryStore.cpp 5. GroceryItemDatabase.cpp 6. main.cpp 7. GroceryStore.cpp Start with the files provided. Make your changes in the designated TO-DO sections (only). The grading process will detect and discard all other changes.GroceryItemDatabase.cpp is similar to the previous assignment but needs updating to move from std::vector to std::map. sample_output.txt 8. output.txt Capture your program’s output to this text file and include it in your delivery. Failure to deliver this file indicates you could not get your program to execute.readme.* Optional. Use it to communicate your thoughts to the grader Grocery_UPC_Database-Large.dat GroceryStoreInventory.dat Text files with a grocery item’s full description and a grocery store’s inventory databases. Do not modify these files. They’re big and unchanged, so don’t include it in your delivery. RegressionTests/ GroceryItemDatabaseTests.cpp GroceryStoreTests.cpp GroceryItemTests.cpp CheckResults.hppWhen you’re far enough along and ready to have your class tested, then place this folder in your working directory. These tests will be added to your delivery and executed during the grading process. The grading process expects all tests to pass.
• Familiarization with stack and queue concepts • Reinforce the concept of adapting the stack and queue abstract data type to an underlying implementation data structure• Familiarization and practice using the STL’s adapter container interface • Increase recursion proficiency • Reinforce modern C++ object-oriented programming techniquesContinuing with our grocery item and grocery list themes, you are now at a grocery store shopping for the grocery items on your list. As you walk up and down the aisles you place grocery items into your shopping cart, one grocery item on top of the other. The last grocery item you place into your shopping cart will be on top and will be the first grocery item you remove.In fact, if you want to get to something at the bottom of your cart you’ll have to remove everything on top of it first. You’re a very smart shopper so you know to start with canned goods first so they won’t break, and finish with the eggs last.As luck would have it, you’ve almost completed your shopping and have a pretty full cart when the wheel falls off rendering your cart unmovable. Determined to complete your grocery shopping you grab another cart and begin moving items from the broken cart to the new cart when you realize that your breakable grocery items, like eggs, will now be on the bottom. But that’s an easy problem to solve, all you have to do is get a third cart and carefully move grocery items between the two new carts so that the breakable items are always on the top.A recursive algorithm to carefully move grocery items from the broken cart to a working cart is: START Procedure carefully_move_grocery_items (number_of_items_to_be_moved, broken_cart, working_cart, spare_cart) IF number_of_items_to_be_moved == 1, THEN move top item from broken_cart to working_cart ELSE carefully_move_grocery_items (number_of_items_to_be_moved-1, broken_cart, spare_cart, working_cart) move top item from broken_cart to working_cart carefully_move_grocery_items (number_of_items_to_be_moved-1, spare_cart, working_cart, broken_cart) END IFEND Procedure STOP See Towers of Hanoi in WikiBooks, or Data Structure & Algorithms – Tower of Hanoi, Tower of Hanoi video or Tower of Hanoi recursion game algorithm explained for more about the recursive algorithm. A sample trace might look like: After 0 moves: Broken Cart Spare Cart Working Cart ————————————————————————— eggs bread apple pie hotdogs rice krispies milk =========================================================================== After 1 moves: Broken Cart Spare Cart Working Cart ————————————————————————— bread apple pie hotdogs rice krispies milk eggs =========================================================================== After 2 moves: Broken Cart Spare Cart Working Cart ————————————————————————— apple pie hotdogs rice krispies milk eggs bread =========================================================================== After 3 moves: Broken Cart Spare Cart Working Cart ————————————————————————— apple pie hotdogs rice krispies eggs milk bread =========================================================================== and so on . . . After 63 moves: Broken Cart Spare Cart Working Cart ————————————————————————— eggs bread apple pie hotdogs rice krispies milk ===========================================================================Once you fill your shopping cart you’ll proceed to the checkout line. When it’s your turn, you’ll take all your grocery items from your shopping cart and place them flat on the counter one after the other where they will be scanned in order and a total calculated. As a grocery item is scanned, the UPC is used to query the store’s persistent database for the grocery item’s full name, description, and price. Note that the grocery item scanned may not be in the database. You take your receipt and your bags of groceries and leave the store.The output of your program is an itemized receipt with the total amount due, perhaps something like this: How to Proceed: The following sequence of steps are recommended to get started and eventually complete this assignment.1. Review the solution to the last homework assignment. Use the posted solution to fix your solution and verify it now works. Your GroceryItem class needs to be working well before continuing with this assignment. When you’re ready, replace the GroceryItem.cpp file packaged with this assignment with your (potentially updated) GroceryItem.cpp file from last assignment.2. Implement the database functions first. This worldwide database of grocery items has hundreds of thousands of entries most grocery stores access when looking up a particular UPC’s for a matching brand name, product description and recommended retail price. Details are in GroceryItemDatabase.hpp and GroceryItemDatabase.cpp.a. The constructor opens a text file containing Grocery Items and populates a memory resident data store with the contents of the text file. Implement the memory resident data store with a standard vector. You are given a sample database text file to test your work. The actual database file used to grade your work may be different.b. The find() function takes a UPC, searches the memory resident data store, and returns a pointer to the grocery item if found and a null pointer otherwise. Solutions with non-recursive solutions earn no credit. Separate interface from implementation by declaring an overloaded helper function in the header file and implementing both find functions in the source file. c. The size() function takes no arguments and returns the number of grocery items in the database.3. Next, implement the segments in main.cpp from top to bottom. Details are embedded in main.cpp. a. Implement the carefully_move_grocery_items items recursive algorithm first, then i. Hint: You may want to stub this out for now so you can make progress elsewhere, but do remember to come back later and actually implement it. In TO-DO (2), simply set to = from; b. Snag an empty cartc. Shop for a while placing grocery items into a shopping cart d. A wheel on your cart falls off so carefully move grocery items from the broken cart to a new cart that works e. Checkout and pay for all this stuff by choosing a checkout line and placing grocery items on the counter’s conveyor belt. Once all the grocery items have been moved from the cart to the “00688267039317”, “Nature’s Promise”, “Nature’s Promise Naturals Fresh Brown Eggs Omega 3 Large”, 24.66 “00835841005255”, “Fiber One”, “Fiber One Bread Country White”, 2.78 “09073649000493” (apple pie) not found, your grocery item is free! Bon appetit! “00038000291210”, “Rice Krispies”, “Kellogg’s Rice Krispies Cereal”, 12.85 “00075457129000”, “Garelick Farms”, “Garelick Farms Dairy Pure Milk 1% Lowfat”, 9.64 ————————- Total $49.93counter the cashier will begin scanning the grocery items in the order you placed them on the counter.f. Scan the grocery items in the order you placed them on the counter accumulating the amount due and creating a receipt with full product descriptions and prices obtained from the database. i. Don’t assume the grocery item’s UPC will be in the worldwide database of grocery items. ii. Do assume the database text file will have formatting errors and that your Grocery Item’s extraction operator will handle the errors. Of course, verify your Grocery Item’s extraction operator really does handle errors.Rules and Constraints: 1. You are to modify only designated TO-DO sections. The grading process will detect and discard any changes made outside the designated TO-DO sections, including spacing and formatting. Designated TO-DO sections are identified with the following comments: ///////////////////////// TO-DO (X) ////////////////////////////// … /////////////////////// END-TO-DO (X) ////////////////////////////Keep and do not alter these comments. Insert your code between them. In this assignment, there are 12 such sections of code you are being asked to complete. 7 of them are in main.cpp, 2 are in GroceryItemDatabase.hpp, and 3 are in GroceryItemDatabase.cpp.Reminders: • The C++ using directive using namespace std; is never allowed in any header or source file in any deliverable product. Being new to C++, you may have used this in the past. If you haven’t done so already, it’s now time to shed this crutch and fully decorate your identifiers.• A clean compile is an entrance criterion. Deliveries that do meet the entrance criteria cannot be graded. • Use Build.sh on Tuffix to compile and link your program. The grading tools use it, so if you want to know if you compile error and warning free (a prerequisite to earn credit) than you too should use it.• Filenames are case sensitive on Linux operating systems, like Tuffix. • You may redirect standard input from a text file, and you must redirect standard output to a text file named output.txt. Failure to include output.txt in your delivery indicates you were not able to execute your program and will be scored accordingly.A screenshot of your terminal window is not acceptable. See How to build and run your programs. Also see How to use command redirection under Linux if you are unfamiliar with command line redirection.Deliverable Artifacts: Provided files Files to deliver Comments GroceryItem.hpp 1. GroceryItem.hpp You shall not modify this file. The grading process will overwrite whatever you deliver with the one provided with this assignment. It is important your delivery is complete, so don’t omit this file.GroceryItem.cpp 2. GroceryItem.cpp Replace with your (potentially updated) file from the previous assignment. main.cpp GroceryItemDatabase.hpp GroceryItemDatabase.cpp 3. main.cpp 4. GroceryItemDatabase.hpp 5. GroceryItemDatabase.cppStart with the files provided. Make your changes in the designated TO-DO sections (only). The grading process will detect and discard all other changes. sample_output.txt 6. output.txt Capture your program’s output to this text file using command line redirection. See command redirection. Failure to deliver this file indicates you could not get your program to execute. Screenshots or terminal window log files are not permitted.readme.* Optional. Use it to communicate your thoughts to the grader. Canvas comments are not sent to the grader and are not seen. Grocery_UPC_Database-Small.dat Text file with a worldwide grocery item database. Do not modify this file. It’s big and unchanged, so don’t include it in your delivery RegressionTests/ GroceryItemDatabaseTests.cpp GroceryItemTests.cpp CheckResults.hppWhen you’re far enough along and ready to have your classes tested, then place these files in your working directory. These tests will be added to your delivery and executed during the grading process. The grading process expects all tests to pass.
• Familiarization with arrays, extendable vectors, and doubly and singly linked lists • Understanding the sequence container’s insertion, deletion, traversal, and search concepts.• Reinforce the similarities and differences between the sequence data structures and their interfaces. • Analyze and understand the differences in the sequence container’s complexity for some of the more common operations• Familiarization and practice using the STL’s sequence container interface • Reinforce modern C++ object-oriented programming techniques • Reinforce the software development cycle and practice building error free solutions on LinuxThis Grocery List assignment builds on the GroceryItem class from the previous assignment. Here you create and maintain a collection of grocery items to form a grocery list. Grocery items are placed on the list, removed from the list, and reordered within the list. A complete GroceryList class interface and partial implementation have been provided. You are to complete the implementation.To reinforce the four data structure concepts (arrays, extendable vectors, doubly linked lists, and singly linked lists) discussed in class, your grocery list implementation mirrors grocery item insertion, removal, and reordering requests to each of four STL containers (std::array, std::vector, std::list, and std::forward_list respectively). At the end of each operation the four STL containers must be consistent.For example, when your GroceryList object receives a request to insert a grocery item, your implementation of GroceryList::insert() will insert that grocery item into all four STL containers such that each container holds the same grocery items in the same order.The following UML class diagrams should help you visualize the GroceryList interface, and to remind you what the GroceryItem interface looks like. class GroceryItem summary class GroceryList summaryGroceryList function summaries: 1. find() takes a grocery item as a parameter and returns the zero-based offset of that grocery item, or the total number of grocery items in the grocery list if the grocery item was not found. For example, if your grocery list contains the grocery items in the picture above, a request to find “Marshmallows” returns 0, “Ice” returns 5, and “Peanut Butter” returns 15.2. insert() takes a grocery item and either a position (TOP or BOTTOM) or a zero-based offset into the list as parameters and inserts the provided grocery item before the insertion point. For example, again if your grocery list contains the grocery items in the picture above, inserting “Peanut Butter” with an offset of 5 places “Peanut Butter” between “Mango Juice” and “Ice”. Duplicate grocery items are silently discarded (not added to the grocery list).3. moveToTop() takes a grocery item as a parameter, locates and removes that grocery item, and then places it at the top of the list. For example, a request to move “Beer” to the top removes “Beer” from its current location and places it before “Marshmallows”. Of course, “Ginger” would then immediately follow “Pita”. The grocery list remains unchanged if the provided grocery item is not in the grocery list.4. operator+=() appends the provided grocery list to the bottom of this grocery list while silently discarding duplicate grocery items. This behavior is similar to std::string’s append (a.k.a. concatenation) operator. See std::string::operator+=().5. operator() returns a negative number if this grocery list is less than the other grocery list, zero if this grocery list is equal to the other grocery list, and a positive number if this grocery list is greater than the other grocery list. This behavior is similar to std::vector’s three-way-comparison (a.k.a. spaceship) operator. See std::vector::operator() #76. operator==() returns true if this grocery list is equal to the other grocery list, false otherwise.7. remove() takes either a grocery item or a zero-based offset from the top as a parameter and removes that grocery item from the grocery list. No change occurs if the given grocery item is not in the grocery list, or the offset is past the size of the grocery list. For example, a request to remove “Frozen Peas” from your above pictured grocery list reduces the size of the grocery list by one and causes “Pita” to immediately follow “Ice”.8. size() takes no parameters and returns the number of grocery items in the grocery list. For example, the size of your above pictured grocery list is 15. The size of an empty grocery list is zero.How to Proceed: The following sequence of steps are recommended to get started and eventually complete this assignment. 1. Review the solution to the last homework assignment. Use the posted solution to fix your solution and verify it now works. Your GroceryItem class needs to be working well before continuing with this assignment. When you’re ready, replace the GroceryItem.cpp file packaged with this assignment with your (potentially updated) GroceryItem.cpp file from last assignment.2. Compile your program using Build.sh. There will likely be warnings, after all it’s only a partial solution at this point. If there are errors, solve those first. For example, implement gList_sll_size() first to remove the “must return a value” error. Your program should now execute.3. Once you have an executable program, start implementing functions with the fewest dependencies and work up. Consider this order: gList_sll_size(), size(), find(), insert(), remove(), moveToTop(), and finally opertor+=().4. Implementing insert() and remove() is really implementing insert and remove on each of the four STL containers. For example, upon receipt of an “insert” request, GroceryList::insert() inserts the provided grocery item into the _gList_array, then into the _gList_vector, then the _gList_dll, and finally into the _gList_sll. The following UML sequence diagram summarizes the flow of execution through GroceryList::insert(). GroceryList::remove()is similar.You may want to: a. Work the insert() and remove() functions together for arrays, then for vectors, lists, and finally forward_lists. Insertion and removal (or as the STL calls it, erasure) are very close complements of each other.b. While working insert and remove for each container, you may want to temporary turn off container consistency checking by commenting out those functions. But don’t forget to uncomment them before you’re finished. sd [GroceryList Insert] myGroceryList : GroceryList _gList_array : std::array _glist_vector : std::vector std::list : std::list std::forw ard_list : std::forw ard_list void GroceryItem* insert_after(position, groceryItem) GroceryItem* insert(position, groceryItem) GroceryItem* insert(position, groceryItem) insert(groceryItem, offsetFromTop)Rules and Constraints: 1. You are to modify only designated TO-DO sections. The grading process will detect and discard any changes made outside the designated TO-DO sections, including spacing and formatting. Designated TO-DO sections are identified with the following comments: ///////////////////////// TO-DO (X) ////////////////////////////// … /////////////////////// END-TO-DO (X) ////////////////////////////Keep and do not alter these comments. Insert your code between them. In this assignment, there are 19 such sections of code you are being asked to complete. 18 of them are in GroceryList.cpp, and 1 in main.cpp.Hint: In most cases, the requested implementation requires only a single line or two of code. Of course, finding those lines is non-trivial. Most all can be implemented with less than 5 or 6 lines of code. If you are writing significantly more than that, you may have gone astray.Reminders: • The C++ using directive using namespace std; is never allowed in any header or source file in any deliverable product. Being new to C++, you may have used this in the past. If you haven’t done so already, it’s now time to shed this crutch and fully decorate your identifiers.• A clean compile is an entrance criterion. Deliveries that do meet the entrance criteria cannot be graded. • Always initialize your class’s attributes, either with member initialization, within the constructor’s initialization list, or both. Avoid assigning initial values within the body of constructors.• Use Build.sh on Tuffix to compile and link your program. There is nothing magic about Build.sh, all it does is save you (and me) from repeatedly typing the very long compile command and all the source files to compile. • Filenames are case sensitive on Linux operating systems, like Tuffix.• You may redirect standard input from a text file, and you must redirect standard output to a text file named output.txt. Failure to include output.txt in your delivery indicates you were not able to execute your program and will be scored accordingly. A screenshot of your terminal window is not acceptable. See How to build and run your programs. Also see How to use command redirection under Linux if you are unfamiliar with command line redirection.Deliverable Artifacts: Provided files Files to deliver Comments GroceryItem.hpp GroceryList.hpp 1. GroceryItem.hpp 2. GroceryList.hppYou shall not modify these files. The grading process will overwrite whatever you deliver with the ones provided with this assignment. It is important your delivery is complete, so don’t omit these files.GroceryItem.cpp 3. GroceryItem.cpp Replace with your (potentially updated) file from the previous assignment. main.cpp GroceryList.cpp 4. main.cpp 5. GroceryList.cpp Start with the files provided. Make your changes in the designated TO-DO sections (only). The grading process will detect and discard all other changes.6. output.txt Capture your program’s output to this text file using command line redirection. See command redirection. Failure to deliver this file indicates you could not get your program to execute. Screenshots or terminal window log files are not permitted.readme.* Optional. Use it to communicate your thoughts to the grader. RegressionTests/ GroceryListTests.cpp GroceryItemTests.cpp CheckResults.hppThese files contain code to regression test your GroceryItem and GroceryList classes. When you’re far enough along and ready to have your class regression tested, then place these files somewhere in your working directory and Build.sh will find them. Simply having these files in your working directory (or sub directory) will add it to your program and run the tests – you do not need to #include anything or call any functions.These tests will be added to your delivery and executed during the grading process. The grading process expects all tests to pass. sample_output.txt A sample of a working program’s output. Your output may vary.
• Become familiar with creating, compiling, running, and submitting programming assignments • Demonstrate mastery of basic C++ skills, including o allocating and releasing dynamic memory using smart pointers o reading from standard input and writing to standard output o working with standard vectors o overloading insertion and extraction operators • Demonstrate the ability to translate requirements into solutions • Refresh your memory and normalize our point of departure. Depending on your background and how long ago you actively practiced programming in C++, some of this may be review and some may seem new to youIn this assignment, you will play both the role of class developer and the role of class consumer. As class developer you will implement the provided class interface, and then as class consumer you will create and use objects of this class to solve a simple problem. The class itself has a few private attributes, and a multiparameter constructor. Objects of the class have the fundamental capability to insert, extract, and compare themselves. The problem being solved is to simply read and dynamically store several objects, and then after you’ve read them all print them in reverse order. You will reuse class GroceryItem in all future homework programming assignments, so effort you apply now getting it right will greatly benefit you throughout the entire semester.Implement class GroceryItem’s interface, which is provided to you. a. A member-function interface summary is shown in Figure 1 b. In addition, the interface also consists of the non-member insertion and extraction operators. Part 2 – class consumer: Implement function main() to use the GroceryItem class above: a. Read a grocery item1 from standard input (std::cin) until end of file2 . For each grocery item read: i. Store the grocery item in a dynamically created object (e.g., new, make_unique, …) ii. Store the grocery item’s pointer in a standard vector b. After you have reached the end of file, write the grocery items3 to standard output (std::cout) in reverse order using constant reverse iterators c. Be sure to release the dynamically allocated objects before exiting the program 1 Do not read a grocery item’s attributes (three strings and a number), use GroceryItem’s extraction operator to read a grocery item. You know you have an incorrect solution if you have defined variables to hold product name, brand name, UPC, or price.2 This program requires you to not explicitly open files. Simply write your program extracting data from std::cin. Enter Cntl-D (Linux) or Cntl-Z (windows) to indicate end-of-file. Better yet, create a text file with your input and then simply redirect input from that text file (see below). You know you have an incorrect solution if you have included or call the ifstream::open function.) 3 Again, don’t write grocery item attributes; write grocery item objects. Figure 1: Class GroceryItem SummaryRules and Constraints: 1. You are to modify only designated TO-DO sections. The grading process will detect and discard any changes made outside the designated TO-DO sections, including spacing and formatting. Designated TO-DO sections are identified with the following comments: ///////////////////////// TO-DO (X) ////////////////////////////// … /////////////////////// END-TO-DO (X) //////////////////////////// Keep and do not alter these comments. Insert your code between them. In this assignment, there are 22 such sections of code you are being asked to complete. All of them are in GroceryItem.cpp.In addition, you need to create and populate main.cpp from scratch. Hint: In most cases, the requested implementation requires only a single line or two of code. Of course, finding those lines is non-trivial. All can be implemented with less than 9 or 10 lines of code. If you are writing significantly more than that, you may have gone astray.Reminders: • The C++ using directive using namespace std; is never allowed in any header or source file in any deliverable product. Being new to C++, you may have used this in the past. If you haven’t done so already, it’s now time to shed this crutch and fully decorate your identifiers. • A clean compile is an entrance criterion. Deliveries that do meet the entrance criteria cannot be graded. • Object Oriented programming suggests that objects know how to read and write themselves. Classes you write shall overload the insertion and extraction operators.• Object Oriented programming suggests that objects know how to compare themselves. Classes you write shall overload the spaceship () and equality (==) relational operators. • Always initialize your class’s attributes, either with member initialization, within the constructor’s initialization list, or both. Avoid assigning initial values within the body of constructors. • Use Build.sh on Tuffix to compile and link your program.There is nothing magic about Build.sh, all it does is save you (and me) from repeatedly typing the very long compile command and all the source files to compile. • Using std::system(“pause”) is not permitted. If you don’t know what this is, good! • Filenames are case sensitive, both in source code and in your OS file system. Windows doesn’t care about filename case, but Linux does. • You may redirect standard input from a text file, and you must redirect standard output to a text file named output.txt. Failure to include output.txt in your delivery indicates you were not able to execute your program and will be scored accordingly. A screenshot of your terminal window is not acceptable. See How to build and run your programs. Also see How to use command redirection under Linux if you are unfamiliar with command line redirection.Deliverable Artifacts: Provided files Files to deliver Comments GroceryItem.hpp 1. GroceryItem.hpp You shall not modify this file. The grading process will overwrite whatever you deliver with the one provided with this assignment. It is important your delivery is complete, so don’t omit this file. GroceryItem.cpp 2. GroceryItem.cpp Start with the file provided. Make your changes in the designated TO-DO sections (only). The grading process will detect and discard all other changes. 3. main.cpp Create this file as describe above.4. output.txt Capture your program’s output to this text file using command line redirection. See command redirection. Failure to deliver this file indicates you could not get your program to execute. Screenshots or terminal window log files are not permitted. Readme.txt Optional. Use it to communicate your thoughts to the grader. RegressionTests/ GroceryItemTests.cpp CheckResults.hpp These files contain code to regression test your GroceryItem class.When you’re far enough along and ready to have your class regression tested, then place these files somewhere in your working directory and Build.sh will find them. Simply having these files in your working directory (or sub directory) will add it to your program and run the tests – you do not need to #include anything or call any functions.These tests will be added to your delivery and executed during the grading process. The grading process expects all tests to pass. sample_input.txt A sample set of data to get you started. sample_output.txt A sample of a working program’s output. Your output may vary.
In this assignment we will write functions that operate on a filesystem. We provide starter code for this assignment which contains our solution for Assignment 2 as well as our filesystem implementation. We begin by describing the properties of our filesystem, the new shell commands, the list of new files included in the starter code, an example of how to use the filesystem and a note about using your own A2 solution code. We then discuss your tasks for the assignment.Our filesystem has a similar structure to the simple filesystem discussed in class. So if you attended the lectures and did the practice filesystem problems, you are already in a good position to understand some part of our implementation. If not, you are strongly suggested to catch up on those lectures before beginning this assignment.First, we will store our filesystem inside a single file on our computer. We will call this file the hard drive file or disk image. A regular hard drive has sectors that are read from and written to; our hard drive file will also have ‘sectors’ (of size 512 bytes) which are really just bytes in the file. Sector 0 will be the first 512 bytes of the file; sector 1 will be from bytes 512 to 1024, and so on. In this way, we can approximate a real hard drive by using this one file.Our shell will be able to use only one disk image at a time. The file will be specified as the first argument to the myshell executable. For instance, to run the shell with blank.dsk, which is a disk image of size 1MB provided with the starter code, you can run ./myshell blank.dskA disk image by itself is just an empty file with some metadata at the beginning (sector 0) relating to partitions. In order for our shell to use it, we must first format it for our filesystem. To do this, we must pass the -f flag to myshell, as follows: ./myshell blank.dsk -fNote that formatting will destroy any metadata already existing in the disk image. So if your disk image already has some files on it and you then format it by passing the -f flag, your files will no longer be accessible.Now for the basics of the filesystem. The filesystem stores a file by creating an inode for it in a free sector, and then stores the data of the file in other sectors (called the data blocks); the inode for a file will store the sector numbers for the file’s data blocks.In particular, the inode will directly store 123 sector numbers for data blocks (recall that each sector is 512 bytes, so that means that 123 ∗ 512 = 62, 976 bytes can be addressed by these direct block pointers). If a file needs more than that, the filesystem will create (in a new sector) an indirect block which has space for another 128 sector numbers (pointing to data blocks). If a file still needs more, it will create (in a new sector) a double indirect block, which will hold 128 sector numbers that each point to indirect blocks (each allocated as needed). Note that this scheme is very similar to the one discussed in class. See Figure 1 (next page) for an illustration.When making a new file, space on disk must be found for the inode and for the data blocks (and possibly the indirect block(s)). Finding free space is accomplished by checking the free space bitmap, which itself is written to disk in a reserved sector near the start of the disk. The data blocks for a file do not have to be all stored in one contiguous chunk, so a file’s data blocks may be spread across the disk.The filesystem has both on-disk and in-memory data structures. For example, the on-disk inode stores the block sectors. There is also an in-memory inode, into which the on-disk inode is loaded when a file is accessed; the in-memory inode also contains some additional information. Page 4 Figure 1: On-disk inode struct (defined in inode.h)Also as discussed in class, the filesystem has a write-behind cache for both inodes and data blocks. When a request is made to read a block, the cache is checked first before we go to the hard disk. If the block is not in the cache, then we read it from the hard disk (disk image) and put it in the cache. Similarly, if we write a block, we put it in the cache. The cache has a limited size, so when it is full, we evict another block (writing to disk if needed), and on the close of the shell we flush all blocks to disk. Finally, although our filesystem supports directories, we will assume that all files are stored in the root directory.To make our shell work with this new filesystem, we have added shell commands which we describe below. Note that some of these commands had already existed, but they operated on your real filesystem and not a disk image and its filesystem as described above; we have replaced those implementations with versions that do operate on the disk image. (Note that we’ve also renamed commands to remove their my_ prefix.)• ls: Lists all files (in the root directory). • cat fname: Displays the contents of the specified file. • rm fname: Removes the specified file. • create fname size: Creates a (blank) file with the given filename and initial size. • write fname data1 … …: Writes data into the specified file. (Spaces are supported; any reasonable number of tokens can be given.) Note that any write will move forward the current offset of the file, so subsequent reads/writes will take place after the written data.• read fname bytes: Displays the given number of bytes of the specified file. Note that any read will move forward the current offset of the file, so subsequent reads/writes will take place after the written data. • size fname: Displays the number of bytes taken up in data blocks by the given file. • seek fname offset: Updates the given file’s offset to the given amount, to be used for subsequent reads/writes. • freespace: Prints out the number of free sectors on the disk. (You will implement some further commands.)The following files (inside the fs folder) make up our filesystem implementation. As part of your tasks for this assignment, you will need to understand the various structs and call on the various functions exposed in these files. Please take a moment to look through these files as you read through this list so that you get a bit of an idea of what is available to you. We point out some useful functions below, but when to use them and what other functions to use are left for you to understand and find.Note that we do not expect you to modify these files. You can if you like (and you may need to for some of the optional parts), but if you do so, please be careful, because if your filesystem implementation starts to diverge from ours, it may no longer pass the tests used for grading your work. (Of course, it is ok to add new functions that only your code calls.)• cache.c/cache.h: Implementation of the write-behind cache. To read or write blocks, you should use the cache functions buffer_cache_read and buffer_cache_write. • directory.c/directory.h: directory operations; dir_readdir_inode can be called successively to return each filename/inode in the directory. Note that we will assume that all files are in the root directory. • file.c/file.h: Operations on the file struct. This struct contains an (in-memory) inode and the current file position (for reading/writing). Also contains the open file table.• filesys.c/filesys.h: Operations at the filesystem level: creating a new file, removing a file, opening a file, and others, given the filename. • free-map.c/free-map.h: Operations on the free space bitmap. • fsutil.c/fsutil.h: Operations at the shell level: code for the shell commands ls, cat, rm, create, read, write, size, seek, freespace. Understanding how these functions work may be useful to you as you may want to replicate some of their behaviours.• inode.c/inode.h: Operations on the inode struct, including creating, opening, closing, removing, and reading/writing into the data blocks of the inode. Important stuff! These files are also present, however, they are slightly less important. • bitmap.c/bitmap.h: A general purpose implementation of a bitmap. Used for the free map. • block.c/block.h: Block level operations: reading and writing to blocks (sectors). (You will want to use the cache functions instead.)• debug.c/debug.h: some miscellaneous debugging functions; some may be useful to you. • ide.c/ide.h: ‘controller’ code to handle the ATA drive at the physical level (in reality just handling the disk image). • list.c/list.h: a general-purpose linked-list implementation. Some functions could be useful if you need to modify lists. • off_t.h/round.h: misc definitions.• partition.c/partition.h: code to deal with partitions on a disk image. (We will assume there is only one partition.)Example of filesystem use Here is sample output from running myshell with the provided blank disk image blank.dsk (after passing the flag -f to format it). $ ls Files in the root directory: End of listing. $ create ysub.txt 128 $ ls Files in the root directory: ysub.txt End of listing.$ write ysub.txt In the town where I was born Lived a man who sailed to sea $ cat ysub.txt Printing ysub.txt to the console… 00000000 49 6e 20 74 68 65 20 74-6f 77 6e 20 77 68 65 72 |In the town wher| 00000010 65 20 49 20 77 61 73 20-62 6f 72 6e 20 4c 69 76 |e I was born Liv| 00000020 65 64 20 61 20 6d 61 6e-20 77 68 6f 20 73 61 69 |ed a man who sai| 00000030 6c 65 64 20 74 6f 20 73-65 61 00 00 00 00 00 00 |led to sea……| 00000040 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00 |…………….| 00000050 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00 |…………….| 00000060 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00 |…………….| 00000070 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00 |…………….|We encourage you to compile the starter code now and play around a bit with the filesystem shell commands so that you can get some experience with them before continuing to read this PDF. Part of this assignment involves understanding the existing code given to you so that you can use it or parts of it as needed.As before, to compile your code, you will run make clean; make myshell framesize=X varmemsize=Y in the Docker container as detailed earlier in this PDF. Also like the last assignment, to run your shell, you can either run in interactive mode (by typing ./myshell diskname.dsk at the prompt), or in batch mode, by making a file of commands and then typing ./myshell diskname.dsk < commands.txt. We will be using the latter mode to test your code.Using your own Assignment 2 solution code You are free to use your current Assignment 2 solution, in which case you will have to make the following modifications: • copy the provided fs folder into your code folder. • merge the provided Makefile with your own (if you made any changes to your Makefile); otherwise, simply replace your current one with the new version.• merge the provided shell.c file with your own; it is likely you did not make any changes to that file, so you can simply replace your current one with the new version. • merge the provided interpreter.c file with your own. This file contains substantial changes, including: new headers, error messages, and a bunch of new else if’s in interpreter() for the new shell commands.(To see the changes in these files in detail, you can use a file diff program like FileMerge on the Mac, which comes with Xcode. Or you could put them in your Git repo and use Github Desktop to view the change in the files before committing.)Your tasks for this assignment are as follows: 1. Implement some basic file utilities. 2. Implement a simple defragmentation algorithm and fragmentation statistic. 3. Implement data recovery and forensics routines.Details on the required behaviour of your functions follow. Note that we will make some recommendations as to how to proceed, but you have full freedom for your implementation, as long as it complies with all instructions and edge cases.For each sub-part below, we also note how (relatively) lengthly it may take you to accomplish, based somewhat on the length of the required solution code (or, new code needed in excess of code written for prior parts) by indicating (Short), (Medium) or (Long). If you find that you are taking a very long time on a short part, then it may be helpful to rethink your implementation and possibly seek advice in office hours/Ed as there could be a much easier way to solve it. Note however that these notes are only our best approximations.Note that the assignment is designed to be done in the order below. The reason is that parts of the code that you write in earlier parts may be reusable in later parts and, likewise, the understanding that you build up in earlier parts will help you in later parts. That’s why we recommend, if working with a partner, to actually work together on the assignment (e.g., pair programming) instead of splitting up the work.A reminder that we will be having a lab on this assignment in the days following its release (date to be announced). You are strongly encouraged to attend the lab or watch the recording afterwards as it will go through some helpful tips for getting started with the assignment.Finally, note that we provide two sample disk images (each of size 1MB) with this starter code. One is blank (and thus needs to be formatted) and the other has a few files in it already (so do not format that one).You will probably want to make backups of these files so that you can recover from a clean copy in case they get corrupted. There may also be a way to obtain other disk images, but I don’t know anything about that. Write all your code for this assignment in the file fsutil2.c. As described above, you may also modify other files if you like.• (Short) Part 1-1: Implement the shell commands copy_in and copy_out. copy_in should be followed by a filename of a file on your real hard drive. It should read in the file, and then store it as a new file into the shell’s hard drive with the same name in the root directory. copy_out should be followed by a filename of a file in the shell’s hard drive. It should create a file on your real hard drive in the current working directory (normally the same directory as the myshell executable), with the same name as the given file and with the same contents.For copy_in, if you are able to only partially copy the file in (because of lack of free space), print out the message “Warning: could only write %d out of %ld bytes (reached end of file” where %d is the number of bytes you could write and %ld is the total file size of the file to be copied in. Both functions should return the appropriate error flags (defined in interpreter.h) if there is an issue with the file. E.g., if the file does not exist, file could not be read, created, written, etc./code# echo abcdef > test.txt /code# ./myshell < blank.dsk -f Shell v2.0 Frame Store Size = 120; Variable Store Size = 120 hda: 2049 sectors (1 MB) hda1: 2048 sectors (1 MB) Formatting file system…done. Num free sectors: 1974 $ copy_in test.txt $ ls Files in the root directory: test.txt End of listing. $ cat test.txt Printing to the console… 00000000 61 62 63 64 65 66 0a |abcdef. | Done printing /code# ./myshell blank.dsk -f Shell v2.0 Frame Store Size = 120; Variable Store Size = 120 hda: 2049 sectors (1 MB) hda1: 2048 sectors (1 MB) Formatting file system…done. Num free sectors: 1974 $ create myfile.txt 10 $ write myfile.txt testdata $ copy_out myfile.txt $ exit Bye! /code# cat myfile.txt testdata• (Short) Part 1-2: Implement a file finding function find_file. The function should take one argument – a pattern to search for. It should go through all files in the root directory and print out the name of each file whose contents contain the given pattern. /code# ./myshell tswift.dsk Shell v2.0 Frame Store Size = 120; Variable Store Size = 120 hda: 2049 sectors (1 MB) hda1: 2048 sectors (1 MB) Num free sectors: 1771 $ ff cat vigilante-sh*t.txt karma.txt welcome-to-new-york.txt style.txt bad-blood.txt all-you-had-to-do-was-stay.txt 22.txt miss-americana.txt i-wish-you-would.txt• (Medium) Part 2-1: Write the function fragmentation_degree to implement a simple filesystem fragmentation metric. The function should print out the degree of fragmentation of the filesystem. The degree is calculated by dividing the number of fragmented files by the number of fragmentable files. A fragmented file is a file which contains at least two consecutive data blocks which are in sectors that are more than three away from each other. For example, a file with three data blocks in sectors 3, 4, 5, or 3, 4, 7, is not fragmented. But a file that has two data blocks in sectors 4 and 10 (and not in 5,6,7,8,9) is fragmented.A fragmentable file is any file that has more than one data block. • (Long) Part 2-2: Write the function defragment. This function should reduce the number of fragmented files to zero without any data loss. This function can be partly implemented by reading all files into memory (not necessarily the shell memory, just a buffer); we will assume that the memory is large enough to store the contents of all files on the disk. Note that real defragmentation algorithms cannot make this assumption and must try to defragment in-place.Write your code for this part in the function recover. You may (as always) use helper functions. When the shell command recover %d is executed, the function recover will be executed. The integer %d will be passed as argument and serve as a flag. Depending on the flag, you will execute a different routine, listed below. Each routine involves recovering files on the hard drive.• (Short) Part 3-1 (flag 0): Recovering deleted files. Your code should scan all free sectors on the drive and check if any contain inodes which were previously deleted from the root directory (i.e., through the rm command) but still exist on disk. If it finds any, it should restore the inodes so that the files can be accessed normally via the shell. The filename for each recovered file should be ‘recovered0-%d’ where %d is the sector number containing the deleted inode. All recovered files of this type should be stored in the root directory of the disk image. (We will assume that the data blocks pointed to by the inode will not have been overwritten.)• (Short) Part 3-2 (flag 1): Recovering individual, non-zeroed out data blocks (since it may be that a deleted file’s inode has been overwritten, but some or all of its data blocks may remain intact). If you find any non-zero data blocks (starting at sector 4), save the contents of the sector outside of the shell (on your real filesystem) in a file called ‘recovered1-%d.txt’ where %s is the sector in which you found the data.• (Long) Part 3-3 (flag 2): Finding data hidden past the end of a current file. A file can be split over multiple data blocks, but it may not fully fill its final data block. For example, a file might be created with size 768, which will fit into two data blocks (since blocks/sectors are 512 bytes each). However, the last 256 bytes of the second data block will go unused, and the contents of this part of the data block will not be shown using cat. It is possible that data is hidden in this area. Your function should go through all files and check for this hidden data, if any. If any such (non-zeroed) data is found, save it outside of the shell (on your real filesystem) in a file called ‘recovered2-%s.txt’ where %s is the name of the file in which you found the data.Note: your recovered filed must contain only the requested data recovered. If it contains less or more than that, it will not be judged as correct.The following sub-parts are not worth any marks and will not be graded. However, if you pass the tests for this part, you will be awarded the specified number of COMP310COIN. Coins will be awarded upon submission if the relevant test(s) are passed.Note: For those working with a partner, you will split the coins with your partner. However, your leaderboard score will appear as if you had each obtained the full amount.500 coins Recover more hidden data from the hard drive file beyond the points mentioned in part 3 above. You will need to implement a routine for flag 3. Store the recovered data in a file recovered3.txt. We do not say where the data may be hidden. 500 coins Recover more hidden data from the hard drive file beyond the points mentioned in part 3 above. You will need to implement a routine for flag 4. Store the recovered data in a file recovered4.txt. We do not say where the data may be hidden.500 coins Recover more hidden data from the hard drive file beyond the points mentioned in part 3 above. You will need to implement a routine for flag 5. Store the recovered data in a file recovered5.txt. We do not say where the data may be hidden.500+ coins Extend the capacity of the disk image without making the disk image file larger. We provide a 1MB blank disk image with this assignment. Here we ask you to update the filesystem code so that it can store more files than in the initial implementation. Some possibilities here are compression or sharing sectors that multiple files have in common; or looking for unused parts of the disk image in the current implementation and finding out why they are unused (you can check where empty space may be by using a hex-editor, e.g., http://hexfiend.com for Mac, on a disk image filled to capacity). The more amount of data that can be stored, the more coins you will receive (in fixed increments).1000 coins Implement the shell commands cd and mkdir which should operate on the shell’s hard drive (not your real hard drive). The other file commands (create, read, write, etc.) should all be modified to look for the file in the current working directory instead of the root directory.Finally, add a README.md file into the same folder as your code files. In this file, state your name(s) and McGill ID(s), any comments you would like the TA to see, and whether you have implemented any optional parts, and if so, which parts, so that the TA will know to check for this.
Welcome to Operating Systems Assignment 2. We have implemented a shell. Now we are in our paging era.We provide starter code for this assignment which contains our solution for Assignment 1 as well as additional changes listed below. Note: If you have made improvements to the shell you made for Assignment 1, e.g., by adding additional commands (for the optional components), then you may wish to port those changes to our new starter code.You don’t have to, of course. But it would be a bit sad to have done that extra work and then just discard it! Changes in new template code A round-robin scheduler has been added to the shell which allows several scripts to be executed in a round-robin fashion. To execute several scripts in this manner, a new command exec has been added. exec takes up to three files as arguments (e.g., exec prog1 prog2 prog3, where progN are text files containing script commands).Then the scheduler will execute one command from each progN file at a time, until all commands in those files have been executed. Here are some notes on our implementation: • When exec is executed, the contents of each specified script file will be read and fully loaded into the shell memory. • A Process Control Block (PCB) for each script file will be created to represent the script’s process. Each PCB will store the process PID (unique to each process), the location in shell memory where the file contents of the script was stored, and the current instruction of the script to execute (i.e., the program counter). • A ready queue is used to store the PCBs of the running processes.It is implemented as a linked list. Each element in the queue has a next pointer which points to the next PCB in the ready queue. The queue also has a head pointer to point to the first PCB in the queue. • The scheduler runs the process at the head of the ready queue by sending its current instruction to the interpreter. • After the instruction is done, the scheduler switches to a different process according to the scheduling policy. It updates the ready queue according to said policy and then executes the current instruction of the next head process. • When a process is done executing, its source code is removed from the shell memory.Here is an example. Given the following three files: prog1_pdf echo helloP1 set x 10 echo $x echo byeP1 prog2_pdf echo helloP2 set y 20 echo $y print y echo byeP2 prog3_pdf echo helloP3 set z 30 echo byeP3 we can run them concurrently using the following commands, and get the following output, assuming that the round-robin scheduler runs with a time slice/quantum of 2 (i.e., two instructions per process before switching): $ exec prog1_pdf prog2_pdf prog3_pdf helloP1 helloP2 helloP3 10 byeP1 20 20 byeP3 byeP2 $ Specifically, the following files were added to the template code: • pcb.c and pcb.h to implement the Process Control Blocks• ready_queue.c and ready_queue.h to implement the ready queue • kernel.c and kernel.h to implement scheduling and process creation And the following files were modified: • interpreter.c and interpreter.h: to add the exec command and update the run command implementation, and miscellaneous error handling improvements • shellmemory.c and shellmemory.h: to implement loading the script files into shell memory • shell.c and shell.h: small miscellaneous changes • Makefile: to add the new files. As before, to compile your code, you will run make clean; make myshell in the Docker container as detailed earlier in this PDF. Also like the last assignment, to run your shell, you can either run in interactive mode(by typing ./myshell at the prompt), or in batch mode, by making a file of commands and then typing ./myshell < commands.txt. We will be using the latter mode to test your code. We encourage you to compile the starter code now and play around a bit with the exec command so that you understand how it works before continuing to read this PDF. You are going to need to have to modify our implementation, so part of this assignment is to understand the existing code given to you. As always, if you have troubles with this part after spending some time on it, feel free to come to see us in office hours or post on Ed to obtain clarifications.Your tasks for this assignment are as follows: 1. Implement a paging system. 2. Implement a demand paging system. 3. Implement the LRU page replacement policy in demand paging. On a high level, in this assignment we will allow programs larger than the shell memory size to be run by our OS. We will split the program into pages; only the necessary pages will be loaded into memory and old pages will be switched out when the shell memory gets full. Programs executed through both the run and exec commands will need to use paging.Details on the behavior of your memory manager follow in the rest of this section. We will make recommendations, but you have full freedom for your implementation, as long as it complies with all instructions and edge cases that we specify below. For each sub-part below, we also note how (relatively) lengthly it may take you to accomplish it, by indicating (Short), (Medium) or (Long). If you find that you are taking a very long time on a short part, then it may be helpful to rethink your implementation and possibly seek advice in office hours/Ed as there could be a much easier way to solve it.Note however that these notes are only our best approximations and we do not attach fixed amounts, but only specify them for a relative comparison. Also, a reminder that we will be having a lab on this assignment on Wednesday, February 14 (see our Ed post for details). You are strongly encouraged to attend the lab or watch the recording afterwards as it will go through some helpful tips for getting started with the assignment.We will start by building the basic paging infrastructure. For this intermediate step, you will modify the run and exec commands to use paging. Note that, even if this step is completed successfully, you will see no difference in output compared to the run/exec commands in the provided template code. However, this step is crucial, as it sets up the scaffolding for demand paging in the following section. As a reminder, the run command is specified as follows: run SCRIPT.txt: Executes the commands in the file SCRIPT.txt in the current directory run assumes that a file with the given name exists in the current directory. It opens that file and sends each line one at a time to the interpreter.The interpreter treats each line of text as a command. At the end of the script, the file is closed, and the command line prompt is displayed. And the exec command specification is as follows: exec prog1 prog2 prog3 (where prog3 or prog2 prog3 may be omitted). Note that the same script may be passed twice (e.g., exec prog1 prog1 is valid). Also, note that we will not test recursive exec calls.You will need to do the following to implement the paging infrastructure.1. (Short) Set up the (empty) backing store for paging. A backing store is the part of the hard drive that is used by a paging system to store information not currently in main memory. In this assignment, we will represent the backing store as a directory. • An empty backing store directory should be created when the shell is initialized. It should be created inside the current directory. In case the backing store directory is already present (e.g., because of an abnormal shell termination), then the initialization should remove all contents in the backing store. • The backing store should be deleted upon exiting the shell with the quit command. (Note: If the shell terminates abnormally without using quit then the backing store may still be present.)2. (Medium) Partition the shell memory. The shell memory should be split into two parts: • Frame store. A part that is reserved to load pages into the shell memory. The total lines in the frame store will be a multiple of the size of a single frame. In this assignment, each page (and thus frame) will have three lines, so the total lines in the frame store will be a multiple of three. • Variable store. A part that is reserved to store variables.To accomplish this you will need to modify the current shell memory implementation. Note that you are free to implement these two memory parts as you wish. For instance, you can opt to maintain two different data structures, one for loading pages and one for keeping track of variables. Alternatively, you can keep track of everything (pages + variables) in one data structure and keep track of the separation via the OS memory indices (e.g., you can have a convention that the last X lines of the memory are used for tracking variables). For now, the sizes of the frame store and variable store can be static. We will dynamically set their sizes at compile time in the next section.3. (Short) Add a shell command resetmem. This command will take no arguments. It will clear the entirety of the variable store, setting all values to default (the string “none”). Note that it will not modify the frame store. 4. (Medium) Load scripts into the backing store and frame store when run or exec is called. The shell will load script(s) as follows. • The script(s) are copied as files into the backing store.The original script files (in the current directory) are closed, and the files in the backing store are opened. (Thus, if exec has identical arguments, then the same program will be copied into the backing store multiple times, and each copy will be its own process with its own PCB.) • Then, all the pages for each program should be loaded from the backing store into the frame store. (This will change in the next section.) Unlike in the starter code, where scripts were loaded contiguously into the shell memory, in your implementation the pages do not need to be contiguously loaded. (See example on next page.) • When a page is loaded into the frame store, it must be placed in the first free spot (i.e., the first available hole).For example, assume you have two programs that each have six lines. Since each frame will store three lines, you will thus have two pages per program, which do not have to be contiguous in the frame store: 0 prog2-page0 1 prog2-page0 2 prog2-page0 3 prog1-page0 4 prog1-page0 5 prog1-page0 6 prog2-page1 7 prog2-page1 8 prog2-page1 9 prog1-page1 10 prog1-page1 11 prog1-page1 12 5. (Long) Create the page table. You must extend the PCB data structure to include a page table. Each process will have its own page table. The page table will keep track of the loaded pages for that process, and their corresponding frames in memory.You are free to implement the page table however you wish. One possible implementation is creating an array for the page table, where the values stored in each cell of the array represent the frame number in the frame store. For instance, in the example above with the two programs of six lines each, the page tables would be: Prog 1: pagetable[0] = 1 // frame 1 starts at line 3 in the frame store pagetable[1] = 3 // frame 3 starts at line 9 in the frame store Prog 2: pagetable[0] = 0 // frame 0 starts at line 0 in the frame store pagetable[1] = 2 // frame 2 starts at line 6 in the frame store Note that you will also need to modify the program counter to be able to navigate through the frames correctly. For instance, to execute prog 1, the PC needs to make the transitions between the 2 frames correctly, accessing lines: 3,4,5,9,10,11. Assumptions: • The frame store is large enough to hold all the pages for all the programs. (We will modify this assumption in part 2 below.)• The variable store has at least 10 entries. • An exec/run command will not allocate more variables than the size of the variable store. • Each command (line) in the scripts will not be larger than a shell memory line (i.e., 100 characters in the reference implementation). • A one-liner is considered as multiple commands. If everything is correct so far, your run/exec commands should have the same behavior as in the template code. We include some examples with the template code that you can use to make sure your code works properly.We are now ready to add demand paging to our shell. In the section above, we assumed that all pages of all programs fit in the shell memory’s frame store. Now, we will remove this assumption, as follows: 1. (Short) Set the sizes for the frame store and variable store as macros. As you may know, when compiling with GCC, we can pass the -D flag followed by name=value. This flag will have the effect of replacing all occurrences of name in your compiled executable with the value value. We will use this flag to set the size of our frame store and variable store as follows.• Update your Makefile to add -D name=value flags to the gcc command for the two sizes. Use “framesize” and “varmemsize” for the two names. • Do not specify the values inside the Makefile. Instead, we will specify the values as an argument to make. By running make xval=42, the variable xval can be accessed inside the Makefile by writing $(xval). Use this approach to specify the values for the two sizes. For example, you might call make like this: make xval=42 And in your Makefile you might have: gcc -D XVAL=$(xval) -c test.c Then, in your C code, the term XVAL will be replaced by 42. E.g.: for the line int x = XVAL;, x will be set to 42. • Using the technique described above, your shell will be compiled by running make myshell framesize=X varmemsize=Y where X and Y represent the number of lines in the frame store and in the variable store.You can assume that X will always be a multiple of 3 in our tests and that X will be large enough to hold at least 2 frames for each script in the test. The name of the executable remains myshell. • Include an extra printout in your shell welcome message as follows (on the line right after “Shell v2”: “Frame Store Size = X; Variable Store Size = Y” where X and Y are the values passed to make from the command line. Please make sure your program compiles this way and that the memory sizes are adjusted. 2. (Medium) Load only part of each script into memory when run or exec is called. In the previous section, we loaded the entirety of each script into the frame store.Here, we will modify our approach to load pages into the frame store dynamically, as they become necessary. We will begin by modifying the shell behaviour when a run or exec is called. • In the beginning of the run/exec commands, only the first two pages of each program should be loaded into the frame store. A page consists of 3 lines of code. In case the program is smaller than 3 lines of code, only one page is loaded into the frame store. Each page is loaded into the first available hole. The programs should then start executing normally, according to the round-robin scheduling policy with time slice of two lines of code.3. (Long) Handle page faults. Since not all pages of a program may be in memory, there may come a point where a program needs to execute the next line of code that resides in a page which is not yet in memory. This situation is known as a page fault, and you will deal with it as follows: • The current process P is interrupted and placed at the back of the ready queue, even if it may still have code lines left in its “time slice.” The scheduler selects the next process to run from the ready queue.• The missing page for process P is brought into the frame store from the file in the backing store. P’s page table needs to be updated accordingly. The new page is loaded into the first free slot in the frame store if a free slot exists in the frame store. • If the frame store is full, we need to pick a victim frame to evict from the frame store. For now, pick a random frame in the frame store and evict it. (We will improve on this policy in part 3 of the assignment.)Do not forget to update P’s page table. Upon eviction, print the following to the terminal: “Page fault! Victim page contents:” “End of victim page contents.” • P will resume running whenever it comes next in the ready queue, according to the scheduling policy. • When a process terminates, you should not clean up its corresponding pages in the frame store.Note that because the scripting language is very simple, the pages can be loaded into the shell memory in order (i.e., for a program, you can assume that you will first load page 1, then pages 2, 3, 4 etc.). This greatly simplifies the implementation, but be aware that real paging systems also account for loops, jumps in the code, etc. Also, note that if the next page is already loaded in memory, there is no page fault. The execution simply continues with the instruction from the next page, if the current process still has remaining lines in its “time slice”.The final piece is adjusting the page replacement policy to Least Recently Used (LRU). As seen in class, you will need to keep track of the least recently used frame in the entire frame store and evict it. Note that, with this policy, a page fault generated by process P1 may cause the eviction of a page belonging to process P2.(Optional) Part 4 The following sub-parts are not worth any marks and will not be graded. However, if you pass the tests for this part, you will be awarded the specified number of COMP310COIN. Note: For those working with a partner, you will split the coins with your partner. However, your leaderboard score will appear as if you had each obtained the full amount. 500 coins In the given template code, there is a bug that occurs for certain inputs. If you fix the bug and pass the corresponding (optional) test on submission of your code, you will be automatically awarded 500 coins.1000 coins Compare the number of page faults of selected programs under the Random and LRU page replacement policies. Analyze how the page fault rate varies based on program characteristics. Include your analysis in the README.md file (see below). 1000 coins Add another page replacement policy. Do not use random (since that what we implemented in Part 3). Instead, you could try FIFO (First In First Out) or another of your choice. Also, add a new shell command pagepolicy policyname. It will switch the current page replacement policy to the given policy.2500 coins For the additional policy mentioned in the above bullet point, choose the EELRU page replacement policy, which is a paper that students are presenting the week of February 12. You can find the paper link in the presentations spreadsheet on myCourses and/or come to one of our presentation sessions that week to learn more about it.README Finally, add a README.md file into the same folder as your code files. In this file, state your name(s) and McGill ID(s), any comments you would like the TA to see, and whether you have implemented any optional parts, and if so, which parts, so that the TA will know to check for this.
1. State True/False. (a) Assume P 6∈ NP. Let A and B be decision problems. If A ∈ NP C and A ≤p B, then B ∈ P. (b) If someone proves P=NP, then it would imply that every decision problem can be solved in polynomial time. (c) If A ≤p B and B ∈ NP, then A ∈ NP.2. Given an n bit positive integer, the problem is to decide if it is composite. Here the problem size is n. Is this decision problem in NP?3. State True/False. Assume you have an algorithm that given a 3-SAT instance, decides in polynomial time if it has a satisfying assignment. Then you can build a polynomial time algorithm that finds a satisfying assignment(if it exists) to a given 3-SAT instance.4. Show that vertex cover remains NP-Complete even if the instances are restricted to graphs with only even degree vertices.Practice Problems 5. Given an integer m × n matrix A and an integer m − vectorb, the 0- 1integer programming problem asks whether there exists an integer n − vectorx with elements in the set {0; 1} such that Ax = b. Prove that 0-1integer programming is NP Complete. (Hint: Reduce from 3-CNFSAT.)6. Assume that you are given a polynomial time algorithm that decides if a directed graph contains a Hamiltonian cycle. Describe a polynomial time algorithm that given a directed graph that contains a Hamiltonian cycle, lists a sequence of vertices (in order) that forms a Hamiltonian cycle.
1. Given a graph G = (V, E). We want to color each node with one of three colors so that no two adjacent nodes have the same color. We say that an edge (u, v) is satisfied if the colors assigned to u and v are different. Consider the algorithm that picks a color for each vertex uniformly and independently at random. Compute the expected number of satisfied edges.2. An IPod holds a collection of 1000 songs. The collection consists of 100 artists each of whom sang 10 songs. The 1000 songs played in a random order. What is the expected number of times that that three songs sung by the same artist are played in a row?3. Five hundred seventy airline passengers are boarding a plane with 570 seats. Each passenger has a ticket with an assigned seat. Unfortunately, the first person lost his boarding pass, so he picks a seat at random. After that, each person entering the plane either sits in their assigned seat, if it is available, or, if not, chooses an unoccupied seat randomly. What is the probability that the last person to board the plane will sit in the originally assigned seat?4. Consider a random binary array of an infinite size in which exactly half elements are 0s and half are 1s. Your task is to find an index of any 1. Design a randomized algorithm to find such an index. What is the expected number of trials before success?Practice Problems 1. You are in a Cartesian coordinate system. Every step you will go up, down, left, or right, with the equal probabilities (1/4), and the length of every step is 1. What is the expected distance R from the origin to your location, after n steps? Hint: compute R
1. At a dinner party, there are n families a1, a2, …, an and m tables b1, b2, …, bm. The i th family ai has gi members and the j th table bj has hj seats. Everyone is interested in making new friends and the dinner party planner wants to seat people such that no two members of the same family are seated in the same table.Design an algorithm that decides if there exists a seating assignment such that everyone is seated and no two members of the same family are seated at the same table.2. There is a precious diamond that is on display in a museum at m disjoint time intervals. There are n security guards who can be deployed to protect the precious diamond. Each guard has a list of intervals for which he/she is available to be deployed. Each guard can be deployed to at most A time slots and has to be deployed to at least B time slots. Design an algorithm that decides if there is a deployment of guards to intervals such that each interval has either exactly one or exactly two guards deployed.3. Solve Kleinberg and Tardos, Chapter 7, Exercise 28.4. The computer science department course structure is represented as a directed acyclic graph G = (V, E) where the vertices correspond to courses and a directed edge (u, v)E exists if and only if the course u is a prerequisite of the course v. By taking a course w ∈ V , you gain a benefit of bw which could be a positive or negative number. Design an algorithm that picks a subset P A ⊂ V of courses to take such that the total benefit w∈A bw is maximized. Remember that if v ∈ A and (u, v) ∈ E, then u has to be in A. That is, to take a course, you have to take all its prerequisites. The running time should be polynomial in |V |.
1. The edge connectivity of an undirected graph is the minimum number of edges whose removal disconnects the graph. Describe an algorithm to compute the edge connectivity of an undirected graph with n vertices and m edges in O(m2n) time.2. Solve Kleinberg and Tardos, Chapter 7, Exercise 7. 3. Solve Kleinberg and Tardos, Chapter 7, Exercise 9.2 Practice Problems 1. An edge of a flow network G is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Is it true that with respect to a maximum flow of G, any edge whose flow is equal to its capacity is a critical edge? Give an efficient algorithm that finds a critical edge in a flow network.
Question 1 Suppose you have a DAG with costs ce > 0 on each edge and a distinguished vertex s. Give a dynamic programming algorithm to find the most expensive path in the graph that begins at s. Prove your algorithm’s runtime and correctness. For full credit, your algorithm’s runtime should be linear.Question 2 A palindrome is a string that reads the same forwards and backwards. Suppose we are given a string S = s1s2s3…sn, and we want to find the longest palindrome that can be formed by deleting some characters from the string. Give an efficient dynamic programming algorithm to solve this problem. Prove its running time and correctness. For full credit, your algorithm should output which character(s) to delete to form the longest palindrome.Question 3 Suppose you are in Casino with your friend, and you are interested in playing a game against your friend by alternating turns. The game contains a row of n coins of values v(i), where n is even. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money you can definitely win if you move first.Question 4 Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.
Note This homework assignment covers dynamic programming. It is recommended that you read chapter 6.1 to 6.4 from Klienberg and Tardos.1. From the lecture, you know how to use dynamic programming to solve the 0-1 knapsack problem where each item is unique and only one of each kind is available. Now let us consider knapsack problem where you have infinitely many items of each kind. Namely, there are n different types of items. All the items of the same type i have equal size wi and value vi .You are offered with infinitely many items of each type. Design a dynamic programming algorithm to compute the optimal value you can get from a knapsack with capacity W.2. Given a non-empty string s and a dictionary containing a list of unique words, design a dynamic programming algorithm to determine if s can be segmented into a space-separated sequence of one or more dictionary words. If s=“algorithmdesign” and your dictionary contains “algorithm” and “design”. Your algorithm should answer Yes as s can be segmented as “algorithmdesign”.3. Given n balloons, indexed from 0 to n − 1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[lef t] ∗ nums[i] ∗ nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.You may assume nums[−1] = nums[n] = 1 and they are not real therefore you can not burst them. Design an dynamic programming algorithm to find the maximum coins you can collect by bursting the balloons wisely. Analyze the running time of your algorithm.Here is an example. If you have the nums arrays equals [3, 1, 5, 8]. The optimal solution would be 167, where you burst balloons in the order of 1, 5 3 and 8. The left balloons after each step is: [3, 1, 5, 8] → [3, 5, 8] → [3, 8] → [8] → []And the coins you get equals: 167 = 3 ∗ 1 ∗ 5 + 3 ∗ 5 ∗ 8 + 1 ∗ 3 ∗ 8 + 1 ∗ 8 ∗ 1. 4. Solve Kleinberg and Tardos, Chapter 6, Exercise 5.2 Practice Problems 5. Solve Kleinberg and Tardos, Chapter 6, Exercise 6. 6. Solve Kleinberg and Tardos, Chapter 6, Exercise 10. 7. Solve Kleinberg and Tardos, Chapter 6, Exercise 24.
CSCI570 HW5This homework assignment covers divide and conquer algorithms and recurrence relations. It is recommended that you read all of chapter 5 from Klienberg and Tardos, the Master Theorem from the lecture notes, and be familiar with the asymptotic notation from chapter 2 in Klienberg and Tardos.1. The recurrence T(n) = 7T(n/2) + n 2 describes the running time of an algorithm ALG. A competing algorithm ALG0 has a running time of T 0 (n) = aT0 (n/4) + n 2 log n. What is the largest value of a such that ALG0 is asymptotically faster than ALG?2. Solve the following recurrences by giving tight Θ-notation bounds in terms of n for sufficiently large n. Assume that T(·) represents the running time of an algorithm, i.e. T(n) is positive and non-decreasing function of n and for small constants c independent of n, T(c) is also a constant independent of n. Note that some of these recurrences might be a little challenging to think about at first.(a) T(n) = 4T(n/2) + n 2 log n (b) T(n) = 8T(n/6) + n log n (c) T(n) = √ 6006T(n/2) + n √ 6006(d) T(n) = 10T(n/2) + 2n (e) T(n) = 2T( √ n) + log2n (f) T 2 (n) = T(n/2)T(2n) − T(n)T(n/2) (g) T(n) = 2T(n/2) − √ n3. Consider the following algorithm StrangeSort which sorts n distinct items in a list A. (a) If n ≤ 1, return A unchanged. (b) For each item x ∈ A, scan A and count how many other items in A are less than x. (c) Put the items with count less than n/2 in a list B.(d) Put the other items in a list C. (e) Recursively sort lists B and C using StrangeSort. (f) Append the sorted list C to the sorted list B and return the result.Formulate a recurrence relation for the running time T(n) of StrangeSort on a input list of size n. Solve this recurrence to get the best possible O(·) bound on T(n).4. Solve Kleinberg and Tardos, Chapter 5, Exercise 1.2 Practice Problems 1. Solve Kleinberg and Tardos, Chapter 5, Exercise 3. 2. Solve Kleinberg and Tardos, Chapter 5, Exercise 6. 3. Consider an array A of n numbers with the assurance that n > 2, A[1] ≥ A[2] and A[n] ≥ A[n − 1]. An index i is said to be a local minimum of the array A if it satisfies 1 < i < n, A[i − 1] ≥ A[i] and A[i + 1] ≥ A[i]. (a) Prove that there always exists a local minimum for A. (b) Design an algorithm to compute a local minimum of A. Your algorithm is allowed to make at most O(log n) pairwise comparisons between elements of A.4. A polygon is called convex if all of its internal angles are less than 180◦ and none of the edges cross each other. We represent a convex polygon as an array V with n elements, where each element represents a vertex of the polygon in the form of a coordinate pair (x, y). We are told that V [1] is the vertex with the least x coordinate and that the vertices V [1], V [2], · · · , V [n] are ordered counter-clockwise. Assuming that the x coordinates (and the y coordinates) of the vertices are all distinct, do the following.(a) Give a divide and conquer algorithm to find the vertex with the largest x coordinate in O(log n) time. (b) Give a divide and conquer algorithm to find the vertex with the largest y coordinate in O(log n) time.5. Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array. An example of array rotation is as follows: original sorted array A = [1, 3, 5, 7, 11], after first rotation A 0 = [3, 5, 7, 11, 1], after second rotation A 00 = [5, 7, 11, 1, 3].
