The aim of this homework assignment is to practice writing hierarchy of classes.Design a hierarchy of Files. You have two different kinds of Files, Text File and an Image File. The files are identified by their name and type, which is identified by either txt or gif extension. An Image file has dimensions of pixel rows and pixel columns. Each pixel has a color depth that can be represented by number of bits. (8 bits is one byte). A Text file is a plain ASCII file that contains characters. Each character is represented by 8 bits. You should provide a function getSize that returns size of a file. Size of a file is measured in bytes. The size of an Image file is calculated by finding how many pixels are needed to store a file multiplied by number of bits to color a single bit divided by 8. The size of the Text file is calculated by counting number of ASCII characters stored in a file.Provide a function to display properties of a File. Properties include: type, name, size, dimensions and color depth for an Image File, characters for a Text File. Provide functions to return type and names of files. Provide function to retrieve character count for a Text file. Provide functions to retrieve dimensions and color depth of an Image File.Write .h and .cpp files for File, Image, and Text classes.Please submit this assignment to your lab instructor.
The aim of this homework assignment is to practice writing template classes. You must use SafeArray template class and implement a SafeMatrix template class that will allow you to work with two dimensional arrays of any type. The boundaries are checked. You must be able to create instances of SafeMatrix template class like,SafeMatrix m(2,3);The above statement will create a 2 by 3 dimensional array of integers. You must be able to access and set values using bracket operators. For example m[0][1] = 5; will set element at row 0 column 1 to an integer value 5. You must be able to return dimensions of the array as follows: m.length() will return the number of rows in your 2D array. m[0].length() will return number of columns in row number 0. Provide all necessary functions to your template class. Write a Driver program that tests your template class with at least two different types.
Modify your Roster class so that it will now store a dynamic array of pointers to Student objects. The Roster is identified by the course name, course code, number of credits, instructor name, and contains a list of students stored in an array of pointers to Students.The array must have the ability to grow if it reaches the capacity (for that provide a private function grow ()). Modify your functions to add a student to a Roster, delete student from a Roster, and search for a student to reflect the changes. Overload [] operator to return immutable Student object at a particular location. Include the “big-three” that are needed when there is a dynamic allocation within a class.Submit your homework to your recitation instructor.
Modify your Student class to overload the following operators: ==, !=, , = as member operators. The comparison operators will compare students by last name first name and id number. Also, overload > as friend operators in the Student class. Overload > operators in Roster class as well to output Rosters in a nice format as well as input Roster.Provide a function sort in a Roster class as a private function to sort out all the students in a Roster according to their Last Name, First Name, and Student id using the comparison operators that you overloaded in the Student class (We will go over a simple selection sort on integers either in the lab or the lecture). Overload > operators in Date class that I provided for you.Change the date of birth and date of matriculation in the Student class from string to an instance of Date object. Change the functions and constructors in the Student class to set and get the Dates as Date objects rather than strings.Write a driver program to test your functions.Submit your homework to your lab instructor.
The aim of this homework assignment is to practice using a class written by someone else and use dynamic allocation. This homework assignment will also help build towards project 1, which will be to write a program implementing the Roster Management Program. For this assignment, write a program that uses the class Date. As an added challenge, I will not provide you with the .cpp file for this class, rather, only the .o file, to which you can link your program for testing purposes. Write a program that does the following:Note that you do not need to know the implementation of the Date class.In order to compile your program and link it to my Date class you will need to do the following: 1. Before you begin writing any program, make a copy of the Date.h file into your directory. Do this by typing the following (note the . at the end): cp ~alayev/cs211/fall2022/hw4/Date.h . 2. Write your program. 3. Compile your program using the following (to link to my .o file) g++ main.cpp ~alayev/cs211/fall2022/hw4/Date.oNote that you may copy the Date.o file to your local directory; however, this is not necessary, and will use up valuable space on your venus/mars account. Note further that this .o file will only work on venus/mars, it will not work on other UNIX systems or on Windows. Submit this program to your lab instructor following his instructions. If you find any bugs with the code, please do not hesitate to e-mail me. /* Date.h * * Declaration of the class that holds a date, * which is a month-day-year combination. * * Author: Yosef Alayev */ #ifndef DATE_H #define DATE_H #include using namespace std; class Date { public: // Initializes a date to the default value of January 1, 1970. Date();// Initializes a date to the values in the parameters. If the //date is not legal, sets the date to one of the legal values. Date(int m, int d, int y);// Returns the month stored by the class string getMonth() const;// Returns the month stored by the class as a number int getMonthNum() const;// Returns the day stored by the class int getDay() const;// Returns the year stored by the class int getYear() const;// solicit the date from the user void input();// output the date in a nice format void output() const;private: int month, day, year; void adjust(); }; #endif
Write a class Roster that is identified by the course name, course code, number of credits, instructor name, and contains a list of students stored in an array. For now you can use stack allocated array of MAX_CAPACITY=10 (define MAX_CAPACITY as a macro in the .h file). Later we will make this array dynamic to allow it to grow. Provide necessary constructors, accessor functions for each member, and mutator functions for each member. Provide a function to add a student to a Roster, delete student from a Roster, and search for a student. Provide a function to output all Students from a roster to console in a nice format.For now you should not worry about the order of Students in your Roster. They do not need to be sorted.Write a driver program to test your Roster class. Use declare/define/use approach Submit the assignment to your lab instructor.
The aim of this homework assignment is to practice writing classes. This homework assignment will help build towards project 1, which will be to write a program implementing Management of Rosters System.For this assignment, write a class called Student. This class should contain information of a single student. This information includes:last name, first name, standing, credits, gpa, date of birth, matriculation date.For now you can store date of birth and date of matriculation as strings. Your class should support the following functions:Make sure that the standing is set based on credits and not passed in as a parameter. When you call mutator function on credits, or initialize an object in a constructor, or through input function, that is where the standing is set. Standing is:Lower Freshman 0
The aim of this homework assignment is to write simple programs that will be a review of the old material from previous course. It consists of writing 4 simple programs.Please submit this homework to your lab instructor following lab instructor’s instructions.
In lib280-asn6 you are provided with a fully functional 2-3 tree class called TwoThreeTree280. Recall that 2-3 trees are keyed dictionaries. As such, the TwoThreeTree280 class implements the KeyedBasicDict280 interface. This interface adds the methods obtain(k), delete(k) and has(k), and set(x) (replace the item whose key matches they key of x with the item x). Presently, TwoThreeTree280 does not implement KeyedDict280 which adds additional operations including all of the methods in KeyedLinearIterator280 which, in turn, includes all of the public operations on a cursor. Note that KeyedDict280 is the same interface that is implemented by KeyedChainedHashTable280 so you should be somewhat familiar with it from the previous assignment. The task for this question is to extend the TwoThreeTree280 to a class called IterableTwoThreeTree280 which allows linear iteration over the keyed data items stored in the two-three tree in ascending keyorder. We will achieve this by adding additional references to leaf nodes so that the leaf nodes form a bi-linked list. Note that adding this feature to a 2-3 tree results in exactly a B+ tree of order 3 (see textbook Section 17.1). We aren’t going to call it a B+ tree class though, because we are implementing specifically a B+ tree of order 3, and higher-order B+ trees will not be supported. Our IterableTwoThreeTree280 class will be exactly a B+ tree of order 3. Figure 1 in the Appendix shows the differences between a 2-3 tree (without iteration) and a B+ tree of order 3 containing the same elements, with the linking of the leaf nodes to support iteration. The algorithms for insertion and deletion are the same in both kinds of tree, except that in the case of the B+ tree, references to/from the predecessor and successor leaf nodes in key-order have to be adjusted to maintain the bi-linked list of leaf nodes. The full class hierarchy of IterableTwoThreeTree280 is shown in Figure 2 of the Appendix. The hierarchy of tree node classes is shown in Figure ?? of the Appendix. To implement the IterableTwoThreeTree280, the following tasks must be carried out: 1. Make an extension of LeafTwoThreeNode280 that adds references to its predecessor and successor leaf nodes. This has already been done for you in the class LinkedLeafTwoThreeNode280. 2. Override the TwoThreeTree280::createNewLeafNode() method by adding a new protected method in IterableTwoThreeTree280 that it returns a new LinkedLeafTwoThreeNode280 object instead of a TwoThreeNode280 object. This has already been done for you. 3. In IterableTwoThreeTree280, override the insert and delete methods of TwoThreeTree280 with modified versions that correctly maintain the additional predecessor and successor references in the LinkedLeafTwoThreeNode280. Each leaf node should always point to the the leaf node immediately to the left of it (the predecessor) and to the right of it (the successor) even if they are not siblings in the tree. Of course, the leaf node with the smallest key has no predecessor and the leaf node with the largest key has no successor. In IterableTwoThreeTree280, the insert and delete methods from TwoThreeTree280 already have been copied, and TODO comments have been inserted indicating where you need to add additional code to maintain the additional leaf node references. The comments also provide a few hints. You should not have to modify any of the existing code for insert or delete, just add new code to deal with the linking and unlinking of leaf nodes from their successors and predecessors. Maintaining these links is very similar to inserting and removing nodes from the middle of a doubly-linked list. 4. Implement the additional methods required by KeyedDict280 (and, by extension, KeyedLinearIterator280). Some of these have been done for you, others have not. TODO comments in IterableTwoThreeTree280 indicate which methods you need to implement and maybe even a hint or two. In this class, the Page 2 linear iterator interface allows positioning of the cursor along the leaf-level of the tree. The cursor can never be positioned at an internal node. 5. In the main() function, write a regression test to test the methods required by KeyedDict280 (and, by extension, KeyedLinearIterator280). You to not need to explicitly test the insertion and deletion methods since testing of the methods from KeyedLinearIterator280 will reveal any problems with the new leaf node linkages. This is because you will need to insert and delete items to create test cases for those methods in KeyedLinearIterator280 You must test all of the methods listed in the interfaces that are coloured blue in Figure 2 of the Appendix. Use instances of the local class called Loot (which has been defined in the main() method) as the data items to insert into the tree for testing. This class implements the type of item depicted in Figure 1 in the Appendix consisting of the name of a magic item from a fantasy game, and its value in gold pieces. The item keys are the item names (strings). Hint: The toStringByLevel() method you’ve been given prints not only the 2-3 tree’s structure, but also displays current linear ordering of the nodes that results from following the successor links in the leaf nodes, beginning with the leftmost leaf node. This may be helpful for the debugging of step 2.For this question you will be implementing a k-D tree. We begin with introducing some algorithms that you will need. Then we will present what you must do.As we saw in class, in order to build a k-D tree we need to be able to find the median of a set of elements efficiently. The “j-th smallest element” algorithm will do this for us. If we have an array of n elements, then finding the n/2-smallest element is the same as finding the median. Below is a version of the j-th smallest element algorithm that operates on a subarray of an array specified by offsets left and right (inclusive). It places at offset j (where left ≤ j ≤ right) the element that belongs at offset j if the subarray were sorted. Moreover, all of the elements in the subarray smaller than that belonging at offset j are placed between offsets left and j − 1 and all of the elements in the subarray larger than that element are placed between offsets j + 1 and right, but there is no guarantee on the ordering of any of these elements! The only element guaranteed to be in its sorted position is the one that belongs at offset j. Thus, if we want to find the median element of a subarray of the array list bounded by offsets left and right, we can call jSmallest(list, left, right, (left+right)/2) The offset (left + right)/2 (integer division!) is always the element in the middle of the subarray between offsets left and right because the average of two numbers is always equal to the number halfway in between them. The j-smallest algorithm is presented in its entirety on the next page. Page 3 ✞ ☎ Algorithm jSmallest ( list , left , right , j ) list – array of comparable elements left – offset of start of subarray for which we want the median element right – offset of end of subarray for which we want the median element j – we want to find the element that belongs at array index j To find the median of the subarray between array indices ’left ’ and ’right ’, pass in j = ( right + left )/2. Precondition : left pivotIndex jSmallest ( list , pivotIndex +1 , right , j ) // Otherwise , the pivot ended up at list [j] , and the pivot *is* the // j-th smallest element and we ’re done . ✝ ✆ Notice that there is nothing returned by jSmallest, rather, it is the postcondition that is important. The postcondition is simply that the element of the subarray specified by left and right that belongs at index j if the subarray were sorted is placed at index j and that elements between le f t and j − 1 are smaller than the j-th smallest element and the elements between j + 1 and right are larger than the j-th smallest element. There are no guarantees on ordering of the elements within these parts of the subarray except that they are smaller and larger than the the element at index j, respectively. This means that if you invoke this algorithm with j = (right + left)/2 then you will end up with the median element in the median position of the subarray, all smaller elements to its left (though unordered) and all larger elements to its right (though unordered), which is just what you need to implement the tree-building algorithm! NOTE: for this algorithm to work on arrays of NDPoint280 objects you will need an additional parameter d that specifies which dimension (coordinate) of the points is to be used to compare points. An advantage of making this algorithm operate on subarrays is that you can use it to build the k-d tree without using any additional storage — your input is just one array of NDPoint280 objects and you can do all the work without any additional arrays — just work with the correct subarrays. Page 4 You may have noticed that jSmallest uses the partition algorithm partition the elements of the subarray using a pivot. The pseudocode for the partition algorithm used by the jSmallest algorithm is given below. Note that in your implementation, you will, again, need to add a parameter d to denote which dimension of the n-dimensional points should be used for comparison of NDPoint280 objects. ✞ ☎ // Partition a subarray using its last element as a pivot . Algorithm partition ( list , left , right ) list – array of comparable elements left – lower limit on subarray to be partitioned right – upper limit on subarray to be partitioned Precondition : all elements in ’list ’ are unique ( things get messy otherwise !) Postcondition : all elements smaller than the pivot appear in the leftmost part of the subarray , then the pivot element , followed by the elements larger than the pivot . There is no guarantee about the ordering of the elements before and after the pivot . returns the offset at which the pivot element ended up pivot = list [ right ] swapOffset = left for i = left to right -1 if ( list [ i ] 0). • Perform a range search: given a pair of points (a1, a2, . . . ak ) and (b1, b2, . . . , bk ), ai
We have seen how we can extend the functionality of a data structure that we already have implemented by creating a subclass using the extends keyword in Java. This allows us to take an existing data structure class and add new functionality or modify existing ADT functionality (e.g. extension of ArrayedTree280 to ArrayedHeap280), or to create a specialization of a more generic ADT (e.g. extension of LinkedSimpleTree280 to ExpressionTree). Another ADT programming paradigm is restriction. Restriction is used to make an existing ADT appear to be another ADT that has less functionality. Consider the following example. Suppose we need a Stack ADT, but our data structure library, whatever it is, doesn’t have one.Further suppose that our data structure library does have a list ADT which allows insertions and deletions from either end of the list. Such a list has more than the necessary functionality of a stack. A stack is really just a list where we can only add (push) and remove (pop) items at one end. We could just use the list itself as a stack, trusting ourselves to only add and remove at one end. But this does not eliminate the possibility that the “stack” could be used in ways that a stack should not be used when all we really need is a stack. Perhaps another programmer comes along and doesn’t realize that you were using a list to get the behaviour of a stack and does something very un-stack-like to the list without realizing it! What is really needed in this situation is an ADT that has less functionality than the one we already have.We can’t get that by extending the existing list ADT, but we can use the idea of restriction to make the list appear to the outside world as nothing more than a stack! The solution is to restrict the list class by writing a stack class which includes a list as an instance variable, and methods that consist of only the interface for a stack. In other words, the list is the internal data structure for the stack ADT, but the public operations for the ADT consist of only those for a stack.These methods then “translate” the stack operations into the corresponding list operations, thus resulting in a new class that looks exactly like a stack to the outside world, but implements the stack using a list.1 If you take a look at the Stack280 class in lib280, you’ll see that this is precisely what Stack280 does. Its methods translate stack operations into operations on an internal list. Implementing this restriction is far less work than writing a new linked or array-based stack class from scratch. You will practice the concept of restriction in Question 1, below.In this assignment you will work with an implementation of a chained hash table. lib280-asn5 contains the class KeyedChainedHashTable280. You will use this class to solve a problem. KeyedChainedHashTable280 is an example of a keyed dictionary where each item is associated with a unique key. A keyed hash table computes the hash of an item from only the item’s key, even though the item itself might contain other data. Additional background and details about chained hash tables are covered in Session 11 and Tutorial 5. 1Some might call this a “wrapper” class because all it does is “wrap” one ADT in a more restrictive interface, and passes all the work on to the inner ADT.Recall from assignment 2 that a priority queue is a queue in which there is a numeric priority associated with every item in the queue. The item at the head of a priority queue is always the item with highest priority. If we think about it, a heap actually has some of the functionality of the priority queue ADT we specified in assignment 2. We can insert items into a heap which are kept organized by their size (equivalent to enqueue!), and a heap always “dispenses” the largest item (equivalent to getting the item at the front of the priority queue), and it allows us to delete the largest item (equivalent to a dequeue!). The problem we would like to solve is to implement the priority queue ADT specification from assignment 2 by re-using as much of our existing code as we can.You can find the priority queue specification in the appendix of this document. In Assignment 3 we wrote a class ArrayedHeap280 (the instructor’s ArrayedHeap280 is included in lib280-asn5), which has some of the functionality we need for a priority queue. But we cannot just extend it because: 1. it has methods that a priority queue ADT doesn’t have, like itemExists; 2. it has methods that have the right functionality, but the wrong name, like deleteItem, which, for our priority queue, is called deleteMax; and 3. it doesn’t have an iterator, which we need in order to determine the item with the smallest priority (we need to be able to inspect all of the items in the heap to find the smallest one without moving the internal cursor away from the root of the heap).The solution will be as follows: (a) Write a class ArrayedBinaryTreeIterator280 which extends ArrayedBinaryTreePostion280 and implements the LinearIterator280 interface. This will be an iterator for the ArrayedBinaryTree280 class. ArrayedBinaryTreeIterator280 should be fairly easy to implement since you can pretty much copy all of the methods required by the LinearIterator280 interface from ArrayedBinaryTreeWithCursors280, with perhaps some small modification. A mostly incomplete ArrayedBinaryTreeIterator280.java file has been provided in the tree package of lib280-asn5 to start you off. (b) Extend ArrayedHeap280 to a class IterableArrayedHeap280 and write the following methods in IterableArrayedHeap280: • Add a deleteAtPosition method to delete a specific item in the heap (which need not be the root). The item to be deleted should be specified by passing a reference to an ArrayedBinaryTreeIterator280 object. The algorithm for this is just a slight modification of the normal heap deletion algorithm where you swap the item at the end of the array with the item to be deleted, and then swap it with its larger child until it is larger than both its children. This method should be very similar to deleteItem from ArrayedHeap280. • Add a method to IterableArrayedHeap280 called iterator which returns a new ArrayedBinaryTreeIterator280 object for the tree. A mostly incomplete IterableArrayedHeap280.java file has been provided in the tree package lib280-asn5 to start you off. (c) Write a class PriorityQueue280 which is a restriction (as defined in Section 1.1) of IterableArrayedHeap280 which implements the priority queue ADT specification given in the Appendix of this document. This means that PriorityQueue280 should have an IterableArrayedHeap280 as an instance variable, and it is in this heap that the queue items are stored. In this way we can hide the functionality of IterableArrayedHeap280 that we don’t want exposed, as well as add the functionality that it lacks. Page 3 Some of the priority queue methods, like isFull and deleteMax, require identical behavior to existing methods in the IterableArrayedHeap280 and can be written as a single call to a method in the IterableArrayedHeap280 instance variable. Other methods, like minItem and deleteAllMax, require functionality that doesn’t exist in IterableArrayedHeap280 which will be up to you to implement – this will still be done by calling methods of the internal heap, but a single call won’t be enough, for example, you may need to iterate over the heap using an iterator. I have provided you with a mostly incomplete PriorityQueue280.java file in the dispenser package lib280-asn4 which contains a regression test for your convenience (you do not have to write your own). (d) Comment all of the methods in all classes that you wrote by adding a javadoc comment header, and inline comments where appropriate.Since items in the IterableArrayedHeap280 must implement Comparable, your priority queue may assume that the compareTo method of the items compares items based on their priority.Almost every modern video game in the roleplaying genre provides the player with a quest log which is essentially a list of tasks that the player’s character has to perform to advance the story or to obtain rewards.2 In this question we are going to create a data structure for a quest log based on a chained hash table. For our purposes, a quest log entry will consist of the following pieces of information: • Name of the quest. • Name of the area of the world in which the quest takes place. • Recommended minimum character level that should attempt the quest. • Recommended maximum character level that should attempt the quest. For the purposes identifying quests, quest log entries are keyed on the name of the quest. A class called QuestLogEntry that can hold these pieces of information is provided. Notice how the key() method of the QuestLogEntry class returns the name of the quest. For this question, you are provided with a complete IntelliJ module called QuestLog-Template in which you will modify one of the classes. It includes the QuestLogEntry class and some .csv (commaseparated value) files which will be used as input data. The QuestLog-Template module requires access to the lib280-asn5 project, set this up as a module dependency as per the self-guided tutorial on the class website for setting up an IntelliJ module to use lib280. You’ve already done this sort of thing previously with other assignments. The entirety of your work will be to finish implementing methods in the QuestLog class provided in the QuestLog-Template project, and to write a couple of interesting tests. Note that the QuestLog class is a specialized extension of KeyedChainedHashTable280, so it is a chained hash table. Here is a list of what you have to do: (a) Complete the implementation of the QuestLog.keys() method. This method must return an array of the keys (i.e. the quest names) of each QuestLogEntry instance in the hash table. The keys may appear in the returned array in any order. (b) Complete the implementation of the QuestLog.toString() method. This method should return a printable string consisting of the complete contents of all of the QuestLogEntry objects in the hash table in alphabetical order by the quest names, one per line. Here is an example string returned by toString() from a quest log containing four entries: ✞ ☎ Defeat Goliad : Candy Kingdom , Level Range : 20 -25 Locate the Lich ‘s Lair : Costal Wasteland , Level Range : 35 -40 Make an Amazing Sandwich : Finn ‘s Treehouse , Level Range : 1 -5 Win Wizard Battle : Wizard Battle Arena , Level Range : 2 -4 ✝ ✆ Remember that the hash table makes no promises whatsoever about the ordering of the quest log entries in the chains of the hash table. Hint: the keys() method from part (a) will be handy for this method, as will knowing that Arrays.sort() can sort the elements of an array. (c) Complete the implementation of the QuestLog.obtainWithCount() method. This method takes a quest name as input and returns a Pair280 object (found in lib280.base) which must contain the QuestLogEntry object from the quest log which matches the given quest name (if it exists) and the number of QuestLogEntry objects that were examined while searching for the desired one. The latter number must be present whether the quest name was found in the quest log or not. 2Back in ’80s and early ’90s, games didn’t have quest logs. If you wanted to remember what you were supposed to do, or something that a character in the game said, you wrote it down with an ancient mystical device called a pencil. And there was no Internet with detailed wikis for every game to get hints from if you got stuck! Page 5 Hints: A Pair280 object has two generic type parameters, the first of which specifies the type of the first element of the pair, and the second of which specifies the type of the second element in the pair. For example, if I wanted a pair consisting of an Integer and a Float I might write: ✞ ☎ Pair280 < Integer , Float > p = new Pair280 < Integer , Float >( 5 , 42.0 ); ✝ ✆ The components of the pair can be accessed using the firstItem() and secondItem() methods: ✞ ☎ System . out . println ( p . firstItem ()); // prints the integer 5 System . out . println ( p . secondItem ()); // the floating point number 42.0 ✝ ✆ (d) Now take a look at the main() program in QuestLog.java. As given, it already does the following things: 1. Creates a new, empty QuestLog instance called hashQuestLog. 2. Creates a new, empty OrderedSimpleTree280 instance (a binary search tree) called treeQuestLog that can hold items of type QuestLogEntry. 3. A .csv file containing the data for a number of QuestLogEntry objects is opened, and read in, creating a QuestLogEntry instance for each quest, and adding each such instance to both both the hashQuestLog and treeQuestLog data structures. 4. The complete contents of hashQuestLog and treeQuestLog are printed out using their respective toString() methods. You’ll know when your Questlog.toString() method from part (b) is working when its output matches that of treeQuestLog.toStringInorder(). At the end of main() are two TODO markers. For the first one, you need to write code that calls hashQuestLog.obtainWithCount() for each quest in the hashed quest log and determines the average number of QuestLogEntry objects that were examined over all such calls. Finally, for the second TODO marker, you have to do the same thing for treeQuestLog. You can do this by calling the searchCount() method of treeQuestLog for each quest stored in the log. Note that searchCount() requires that you pass in the actual QuestLogEntry object that you are looking for rather than just the quest name (you can obtain these from the hashed quest log). searchCount() returns the number of items that were examined while trying to position the tree’s cursor at the given QuestLogEntry object. Once you have computed the average number of QuestLogEntry objects examined for each of the two data structures, print out the results. Something like this will do: ✞ ☎ Avg . # of items examined per query in the hashed quest log with 4 entries : 1.25 Avg . # of items examined per query in the tree quest log with 4 entries : 2.0 ✝ ✆ (e) Run your completed main() program for each of the .csv files provided in the project (just change the filename in quotes that is passed to FileReader). Each .csv file contains in its filename the number of quest entries in the file. For each .csv file, record the reported average number of items examined per query in each data structure. In a text file called a4q2.txt (or other acceptable file format) answer the following questions: 1. List the reported averages that you recorded for each .csv input file in a table that looks something like this (filling in the rest of the table of course): Filename Avg. Queries for hashQuestLog Avg. Queries for treeQuestLog quests4.csv 1.25 2.0 quests16.csv quests250.csv quests1000.csv quests100000.csv Page 6 2. If you had to choose a simple function (i.e. from the list of functions used in big-O notation) to characterize the behaviour of the the average number of items examined per query for the hashed quest log as the number of quests (n) in the log increases, what would it be? 3. If you had to choose a simple function (i.e. from the list of functions used in big-O notation) to characterize the behaviour of the the average number of items examined per query for the tree quest log as the number of quests (n) in the log increases, what would it be? 4. If your primary use of the quest log was to display all of the quests in the log in alphabetical order, would you prefer the hashed quest log or the tree quest log? Why? 5. If your primary use of the quest log was to periodically look up the details of specific quests in no particular order, would you prefer the hashed quest log or the tree quest log? Why?lib280-asn5: A copy of lib280 which includes: solutions to assignment 3; ArrayedBinaryTreeIterator280.java A mostly incomplete implementation of a linear iterator for arrayed binary trees; IterableArrayedHeap280.java A mostly incomplete implementation of a heap which provides an iterator and allows any item to be deleted; and PriorityQueue280.java: A mostly incomplete implementation of our priority queue ADT (in the lib280 dispenser package). QuestLog-Template.zip: A complete IntelliJ module containing everything you need for Question 2.You must submit a .ZIP file containing following files: ArrayedBinaryTreeIterator280.java Your completed implementation of a linear iterator for arrayed binary trees. IterableArrayedHeap280.java Your completed implementation of a heap which provides an iterator and allows any item to be deleted. PriorityQueue280.java: Your completed implementation of the priority queue ADT. QuestLog.java: Your completed quest log based on a hash table (parts (a), (b), and (c) of Q2), and completed additions to main() (part (d) of Q2). a4q2.txt: Your answers to the questions posed in part (e) of Q2. If you prefer, this file may be a MS Word file or a PDF file. 5 Grading Rubric The grading rubric can be found on Canvas.Appendix – Priority Queue ADT Specification This is the Priority Queue ADT specification from Assignment 2, but with the frequency operation omitted.You need to implement only the operations shown here. Name: PriorityQueue Sets: Q : set of priority queues containing elements from G. G : set of items that can be in a priority queue. B : {true, f alse} N : set of positive integers. N0 : set of non-negative integers. Signatures: newPriorityQueue: N → Q Q.insert(g): G ̸→ Q Q.isFull: → B Q.isEmpty: → B Q.count: → N0 Q.maxItem: ̸→ G Q.minItem: ̸→ G Q.deleteMax: ̸→ Q Q.deleteMin: ̸→ Q Q.deleteAllMax: ̸→ Q Preconditions: For all q ∈ Q, g ∈ G, q.insert(g): queue is not full q.maxItem: queue is not empty q.minItem: queue is not empty q.deleteMax: queue is not empty q.deleteMin: queue is not empty q.deleteAllMax: q must not be empty. (Operations without preconditions are omitted)Semantics: For all n ∈ N, g ∈ G, n ∈ N newPriorityQueue(n): create a new queue with capacity n. q.insert(g): insert item g into t in priority order with the highest number being the highest priority. q.isFull: return true if t is full, f alse otherwise q.isEmpty: return true if t is empty, f alse otherwise q.count: obtain number of items in q q.maxItem: return the largest (highest priority) item in q. q.minItem: return the smallest (lowest priority) item in q. q.deleteMax: remove the largest (highest priority) item in q from q. q.deleteMin: remove the smallest (lowest priority) item in q from q. q.deleteAllMax: all occurrences of the highest priority item are deleted from q.
A heap is a binary tree which has the following heap property: the item stored at a node must be at least as large as any of its descendents (if it has any). In a heap, when an item is removed, it is always the largest item (the one stored at the root) that gets removed. Also, the only item that is allowed to be inspected is the top of the heap, in much the same way that the only item of a stack that may be inspected is the top element. Stacks, queues, and heaps are all examples of collections of data items that we call dispensers. You can put stuff into a dispenser, but the user doesn’t get to specify where – the collection decides according to some rule(s). Likewise, you can take something out of a dispenser, but the dispenser decides what item you get. Dispensers maintain a current item using an internal cursor, but the dispenser always decides what is the current item, and thus the item that will next be dispensed when a user asks to remove or inspect the current item. Dispensers do not have public methods to control the cursor position because the user is not supposed to control this; it’s up to the dispenser. In a stack, the “current” item is always the item at the top of the stack. In a queue it is the item at the front of the queue. In a heap it is the item at the root of the heap. In question 1 you will implement a heap by writing a class called ArrayedHeap280 that extends the abstract class ArrayedBinaryTree280 and implements the Dispenser280 interface. Here are brief pseudocode sketches of the insert and deleteItem algorithms: ✞ ☎ Algoirthm insert (H , e ) Inserts the element e into the heap H . Insert e into H normally , as in ArrayedBinaryTreeWithCursors280 // ( put it in the left – most open position at the bottom level of the tree ) while e is larger than its parent and is not at the root : swap e with its parent ✝ ✆ ✞ ☎ Algorithm deleteItem ( H ) Removes the largest element from the heap H . // Since the largest element in a heap is always at the root … Remove the root from H normally , as in ArrayedBinaryTreeWithCursors280 // ( copy the right – most element in the bottom level , e, into the root , // remove the original copy of e.) while e is smaller than its largest child swap e with its largest child ✝ ✆ For AVL trees, we need to be able to identify critical nodes to determine if a rotation is required. After each recursive call to insert(), we need to check whether the current node is critical (the restoreAVLProperty algorithm). This means we need to know the node’s imbalance, which means we need to know the heights of its subtrees. If we compute the subtree heights with the recursive post-order traversal we saw in class, we are in trouble, because this algorithm costs O(n) time, where n is the number of nodes in the tree. Since insertion requires O(log n) checks for critical nodes, computing imbalance in this way makes insertion O(n log n) in the worst case. To avoid this cost, in each node of the AVL tree we have to store the heights of both of its subtrees, and update these heights locally with each insertion and rotation. The insertion algorithm from the AVL tree slides becomes: ✞ ☎ // Recursively insert data into the tree rooted at R Algorithm insert ( data , R) data is the element to be inserted R is the root of the tree in which to insert ‘data ‘ // This algorithm would only be called after making sure the tree // was non – empty . Insertion into an empty tree is a special case . if data
Question 2 is about a bounded binary tree implementation. You should remember binary trees from CMPT 145 (or similar course) – they are trees in which each node has at most two children. What you probably didn’t know is that binary trees can be stored using an array, rather than a linked structure. In such an array, the contents of the root node are stored in offset 1 of the array (offset 0 is unused). The contents of the children of the node whose contents are stored at offset i are stored at offset 2i and 2i + 1, respectively. Thus, the left child of the root is at offset 2 × 1 = 2, the right child of the root is at offset 2 × 1 + 1 = 3, the left child of the left child of the root is at offset 2 × 2 = 4, and so on. The parent of the node whose contents are at offset i, is at offset i/2 (integer division). Thus, the parent of node at offset 7 is at offset 3. Example 1 Here is the array representation of a tree storing the elements 1 through 10, in no particular order. The array – 7 1 4 3 9 10 2 8 5 6 is a representation of the tree: 7 1 3 8 5 9 6 4 10 2 Note that we do not allow any unused entries in the array between used ones. All the data items in the array are stored contiguously. This means that we can represent only a particular subset of binary trees with this representation. Namely, it is the set of trees where all levels except possibly the last level are complete (full) and the nodes in the bottom level are all as far to the left as possible. You might be thinking that this is too restrictive and not very useful because we can’t represent all binary trees with this data structure. However, as we will see on future assignments, this array-based tree data structure is highly useful and efficient as a basis for implementing certain other important data structures. Also note that if we read off the items from left to right in each level of the tree, starting from the top level, we get the items in the same order as they appear in the array.An m-ary tree is one in which a node may have up to m children. Your lib280-asn3 library has a class called BasicMAryTree280 which implements an m-ary tree. It has some similarities with LinkedSimpleTree280 in that, like LinkedSimpleTree280, you have to build up larger trees from smaller trees, rather than inserting individual elements, because since m-ary trees have no defined structure in general and thus there is no obvious algorithm for automatically deciding where a new element should go. You will use this class in Question 3. More details and some examples on how to use this class are/were provided in Tutorial 3. A priority queue is a queue where a numeric priority is associated with each element. Access to elements that have been inserted into the queue is limited to inspection and removal of the elements with smallest and largest priority only. A priority queue may have multiple items that are of equal priority. Give the ADT specification for a bounded priority queue using the specification method described in Topic 7 of the lecture notes. By “bounded”, it is meant that the priority queue has a maximum capacity specified when it is created, and it can never contain more than that number of items. Your specification must specify the following operations: newPriorityQueue: make a new queue insert: inserts an element with a certain priority isEmpty: test if the queue is empty isFull: test if the queue is full maxItem: obtain the item in the queue with the highest priority minItem: obtain the item in the queue with the lowest priority deleteMax: remove from the queue the item with the highest priority deleteAllMax: remove from the queue all items that are tied for the highest priority deleteMin: remove from the queue the item with the lowest priority frequency: obtain the number of times a certain item occurs in the queue (with any priority) Your task is to write a Java class called ArrayedBinaryTreeWithCursors280 which extends and implements the abstract class ArrayedBinaryTree280 (provided in the lib280-asn3.tree package as part of lib280-asn3). Tutorial 3 also has more about array-based trees. Your Tasks Some of the work of implementing ArrayedBinaryTreeWithCursors280 has already been done, but there is more to do. Firstly, there are several methods in ArrayedBinaryTreeWithCursors280 which are defined but not implemented. You must implement these methods. These methods can be easily identified by their “TODO” comments. Secondly, since ArrayedBinaryTreeWithCursors280 implements some other interfaces, there are several methods required by these interfaces that also need to be implemented but have not yet been finished. The method headers for these methods have already been generated but the method bodies are empty. The definitions of these methods in their respective interfaces document what these methods are supposed to do. These methods can be identified by their “TODO” commands as well as the @Override directive above the method headers. Many of these methods are defined by LinearIterator280, which is inherited through Dict280. These are the same linear iterator methods that you wrote for LinkedList280 on assignment 1. The rest of these methods are defined by Cursor280. There is already a regression test included in ArrayedBinaryTreeWithCursors280. Your completed implementation of the arrayed binary tree must pass the given regression test. If all the regression tests are successful, the only output should be: Regression test complete. You may not modify any of the existing code in the provided ArrayedBinaryTreeWithCursors280.java file (including the regression test) but you can add to it. You may also not modify any other files within lib280-asn3. • You don’t need to declare an array instance variable in ArrayedBinaryTreeWithCursors280 to hold the data items. There is already one inherited from ArrayedBinaryTree280. You should look at the other inherited instance variables too! • One of your first tasks will be to start implementing the insert method and decide where the new element should be inserted. If you think about it, there’s really only one place it can go… • The algorithm for deleting an element is to replace the element to be deleted by the right-most element in the bottom level of the tree, then delete the right-most element in the bottom level of the tree. • Not sure how a linear iterator works on a tree? If you think about it, there is only one reasonable way to define a linear ordering on the elements of an array-based binary tree. • Reminder: the items array (defined in the abstract class ArrayedBinaryTree280 ) represents the nodes of the tree. You are storing the contents of nodes in the array. There is no node class. It is very important that the contents of the root are stored in offset 1 and we don’t use offset 0 of the array, otherwise the given formulae for finding the child or parent of a node at offset i will not work correctly. In video games, especially those in the roleplaying genre, it is common that characters in the game are advanced in power through the use of a skill tree. Generally, a skill tree defines the prerequisite for the various skills that your character in the game might acquire. For example, in a hypothetical game, if the Shield Bash, Defensive Stance, and Shield Ally skills all require that your character first have the skill Shield Proficiency, then this might be represented by the following skill tree: Shield Proficiency, Cost: 1 Shield Bash, Cost: 2 Defensive Stance, Cost: 1 Shield Ally, Cost : 3 More formally, a skill in the skill tree can only be gained if the character first gains all of the skills which are ancestors of that skill in the tree.1 Your task in this question is to write a class called SkillTree which extends BasicMAryTree280 (an m-ary tree of Skill objects; a complete Skill.java is provided). A template for the SkillTree class is provided. It contains a constructor and a couple of useful methods. You will add additional methods to this class in the following steps, which you should complete in order: (a) Write a main() method in the SkillTree class in which you construct your own skill tree for your own hypothetical video game. Your tree must contain at least 10 skills. However, for the sanity of everyone involved, try to keep it under 15 skills. Be creative! There is no reason why any two students should hand in exactly the same (or even very similar) skill trees, nor should you just duplicate the skill tree shown in the sample output. Print your tree to the console using the toStringByLevel() method inherited from BasicMAryTree280. (b) Write a method in the SkillTree class called skillDependencies which takes a skill name as input and returns an instance of LinkedList280 which contains all the of the skills which are prerequisites for obtaining the input skill (including the input skill itself!). A RuntimeException exception should be thrown if the tree does not contain the given skill. A good implementation approach for this method is to use a recursive traversal of the tree to find the named skill, and then add skills to the output list as the recursion unwinds. Tutorial 3 includes some discussion of recursive traversal of m-ary trees. Add to your main() program a few tests of this method, and print out the lists that is returned (you can use the list’s toString() method for this). Be sure to test the case where the named skill does not exist in the tree. (c) Write a method in the SkillTree class called skillTotalCost which takes a skill name as input and returns the total number of skill points that a player must invest to obtain the given skill. If the named skill is not in the skill tree, then the skillTotalCost method should throw a RuntimeException exception. Hint: this method is quite easy to implement if you make use of the previously implemented skillDependencies method. For example, in the above skill tree, if a character wants the Shield Ally skill they would need to spend 1 skill point to get Shield Proficiency, and then spend 3 skill points to get Shield Ally for an 1 In the video game world, the term “skill tree” sometimes refers to things that actually aren’t trees; a noteworthy example is the skill tree in the ARPG Path Of Exile, which, if you click the link, can see is clearly not a tree, even though they call it that. Here in question 3, we used the term “skill trees” to mean skill trees that are, in fact, actual trees. Page 5 overall investment of 1 + 3 = 4 points, so for the above tree, skillTotalCost(“Shield Ally”) should return 4. Note that the Skill object contains the cost of the skill. Add to your main() program a few tests of skillTotalCost, and print out the total costs returned. Be sure to test the case where the named skill does not exist in the tree. (d) Run your main() program. Cut and paste the console output to a text file and submit it with your assignment. See the sample output below. Sample Output Here is an example of what the output of your program might look like. Remember, you are expected to be creative in designing your skill tree, and your submission should not attempt to duplicate what you see here aside from the general formatting (the formatting can be the same, but the data should be different!). Note that the formatting of output of the skill tree contents is done by the toStringByLevel() method of BasicMAryTree280. ✞ ☎ My Skill Tree : 1: Slash , Cost : 1 2: Mighty Blow , Cost : 2 2: Shield Bash , Cost : 1 3: Shield Charge , Cost : 2 3: Parry , Cost : 2 4: Shield Wall , Cost : 4 4: – 4: – 4: – 3: – 3: – 2: Cleave , Cost : 2 3: Whirlwind , Cost : 3 4: Berzerk , Cost : 5 4: – 4: – 4: – 3: – 3: – 3: – 2: Mobility , Cost : 1 Dependencies for Shield Wall : Slash , Cost : 1 , Shield Bash , Cost : 1 , Parry , Cost : 2 , Shield Wall , Cost : 4 , Dependencies for Mobility : Slash , Cost : 1 , Mobility , Cost : 1 , Dependencies for Slash : Slash , Cost : 1 , Dependencies for FakeSkill : FakeSkill not found . To get Whirlwind you must invest 6 points . To get Mighty Blow you must invest 3 points . To get Slash you must invest 1 points . FakeSkill not found . ✝ ✆ Page 6 3 Files Provided lib280-asn3: A copy of lib280 which includes the ArrayedBinaryTree280 class needed for Question 1, a partially complete ArrayedBinaryTreeWithCursors280 for Question 1, and the BasicMAryTree280 class which is needed for Question 2. Skill.java : A complete implementation of the Skill class needed for Question 2. SkillTree.java : A template for your implementation of the SkillTree class in Question 2. In You must submit a .ZIP file containing following files: Assignment2.doc/docx/rtf/pdf/txt – your answer to Question 1. Acceptable file formats are Word (.doc or .docx), PDF (.pdf), rich text (.rtf), or plain text (.txt). Digital images of handwritten pages are also acceptable, provided that they are clearly legible and that they are in JPEG (.jpg or .jpeg) or PNG (.png) format. Other image formats are not accepted and will receive a grade of zero. ArrayedBinaryTreeWithCursors280.java – Your completed class for Question 2. SkillTree.java – Your completed implementation of the skill tree and associated tests. q3-output.txt – The console output from your SkillTree::main() test program to Question 3.
For this assignment you’ll be working with linked list classes from the data structure library lib280. lib280 is a library of data structures that we will build up over the duration of the course. We will start with a version of lib280 that has very few data structures in it and add more with each assignment. Each assignment will come with a new version of lib280 which contains the correct implementations of ADTs that were the subject of the previous assignment.For this assignment the first thing you’ll need to do is to obtain a copy of lib280-asn1. It is provided along with this assignment description on the class webpage. Download the lib280-asn1.zip file and expand its contents somewhere in your filesystem. The class website provides a self-guided tutorial that explains how to import lib280 into an IntelliJ project once you have downloaded it; it is located in the “Modules” page under “Week 2” and is called and “Self-Guided Tutorial: Setting up lib280 in IntelliJ”. First complete part 1 of the tutorial to create an empty IntelliJ project. Then complete part 2 of the tutorial to import lib280-asn1 into your project. For question 1 of this assignment, complete part 3 of the tutorial to create a module for your question 1 solution that can access the classes from lib280-asn1. For questions 2 and 3 you don’t need to complete part 3 again because you’ll just be working within the lib280-asn1 module.The lib280-asn1 module contains several packages. The classes of interest to use for this assignment are in the lib280.list package. Find the lib280-asn1 module in your “project” tab, normally located on the left side of the IntelliJ window. Expand it by clicking the little triangle beside it. This should reveal a folder called “src”. Expand that as well. Now you will see a list of java packages that contain the various classes in the lib280-asn1 library. For this assignment, the classes we are interested in are in the lib280.list package, so click the triangle to expand it. You should now see classes like LinkedList280 and BilinkedList280.The UML diagram below shows the class hierarchy you’ll be working with in this assignment. It may look a bit daunting at first, but you’ll soon see it’s not that complicated. There are four pairs of classes/interfaces (surrounded by light blue boxes1 ). In each pair, there is one class for a singly-linked list and one for a doubly-linked list. The class/interface of each pair that pertains to doubly linked lists extends the class/interface related to singly linked lists. 1The light blue boxes in the UML diagram are only to show the pairs of classes that serve the same roles for singly-/doubly-linked lists and do not represent any actual grouping within lib280. All of the pictured classes are in the same package within lib280. Page 2 List classes Iterator/cursor interfaces Iterator classes List node classes * * BilinkedList280 LinkedList280 ≪interface≫ BilinearIterator280 ≪interface≫ LinearIterator280 LinkedIterator280 BilinkedIterator280 LinkedNode280 BilinkedNode280 LinkedNode280: The node class used for a singly-linked list. BilinkedNode280: An extension of LinkedNode280 that adds the “previous node” reference required for nodes in a doubly linked list. LinearIterator280: An interface that defines the methods that must be supported by cursors and iterators that can step forwards over a linear structure, such as goFirst(), goForth(), after(), etc. BilinearIterator280: An interface that extends LinearIterator280 by adding methods that allow stepping backwards, such as goBack() and goLast(). LinkedIterator: An implementation of LinearIterator280 which is an iterator object for a singlylinked list. It is used by the LinkedList280 class to provide iterators. BiinkedIterator: An implementation of BilinearIterator280, and an extension of LinkedIterator280, which is an iterator object for a doubly-linked list. It is used by the BilinkedList280 class to provide iterators. LinkedList280: A singly-linked list class. It provides a cursor by implementing the LinearIterator280 interface. The Nodes of the list are LinkedNode280 objects, and it can provide iterators of of type LinkedIterator. BiLinkedList280: A doubly-linked list class. It provides a cursor that can move both forwards and backwards by implementing the BilinearIterator280 interface. The nodes of the list are BilinkedNode280 objects, and it can provide iterators of of type BilinkedIterator. Take a moment to familiarize yourself with these classes and their methods, particularly the LinkedList280 and LinkedIterator280 classes as you will be working on coding extensions of these classes. This section describes a bit more about how iterators work. Iterators provide the same functionality as a container ADT that has a cursor, but they are separate objects from the container. This allows us to record a cursor position that is different and independent from the position recorded by the container’s internal cursor. The list objects, LinkedList280 and BilinkedList280 both have methods called iterator. The iterator method in the LinkedList280 class returns a new cursor position encapsulated in an instance of the LinkedIterator280 class. This instance will have references directly to the nodes of the LinkedList280 instance that created it. In essence, the LinkedIterator280 contains its own copies of the position and prevPosition fields that appear in LinkedList280 – i.e. another cursor that is external to the list! This cursor can be manipulated in exactly the same was as the internal cursor of the list. If you compare the methods in LinkedIterator280 to the methods of the same name in LinkedList280, you’ll see that they are almost identical. Thus, each time we want a new cursor that is independent of the list’s internal cursor, we can call the iterator method and get a new one. This adds additional flexibility. If we can get away with just using the lists internal cursor for our purposes, then we can do so, but we have the option to create more cursors in the form of iterators should we so desire. Tractor Jack is a notorious pirate captain who sails the Saskatchewan River plundering farms for wheat, barley, and all the other grains. You may remember him from his exploits in CMPT 141 or CMPT 214. Jack wants to simulate the loading of cargo onto his ships so he can track how much of one type of grain is on a given ship, and to make sure that his ships are not overloaded.2 In this problem you will be given a list-of-lists data structure. It will be a list of Ship objects, each of which contains a list of Sack objects. Each Sack object represents one sack of a particular type of grain. The type of grain in a sack is represented by a value of type Grain, where Grain is an enumeration. In this question use a data type in Java called an enumeration to represent the type of grain in a sack. Enumerations define a fixed set of named constant values. The grains Jack most commonly plunders are wheat, barley, oats and rye so he wants to count the amount of those four grains separately. Any other types of grain he wants to count together. We can us an enumeration to define five constants to denote what type of grain is in a sack: ✞ ☎ enum Grain { WHEAT , BARLEY , OATS , RYE , OTHER } ✝ ✆ This declaration defines a data type called Grain and five values which we can assign to variables of type Grain. You can find it at the top of Sack.java. Now we can then write in Java: ✞ ☎ Grain g = Grain . WHEAT ; // Assign value WHEAT to the variable g ✝ ✆ You’ll need to use one of the values from the Grain enumeration in task 3, below. Provided You are provided with three Java files: Sack.java: Contains the class Sack which is an object that represents a sack of grain. A sack of grain has a grain type, and a weight (in pounds). This object is complete and you will not need to edit this file, but you should familiarize yourself with its data and methods. This file also contains the definition of the enumerated type Grain. Ship.java: Contains the class Ship which represents a ship in Jack’s fleet. Each ship has a name, a capacity (weight in pounds), and contains a list of Sack objects which represent the ship’s cargo. This class contains two unfinished methods that you will write (see below). Familiarize yourself with the other methods and instance variables of this class. CargoSimulator.java This file contains the CargoSimulator class. This class generates the data you’ll be working with for this question. Its constructor generates a list of ships and fills them with sacks of grain. You’ll be writing some code in the main() method of this class (see below). 2This question was inspired by this song (click to link). Arrrr! 1. In Ship.java, complete the isOverloaded method. This method must return a boolean value true if the ship is overloaded, and false otherwise. The ship is overloaded if the total weight of all sacks of grain in its cargo exceeds the ship’s capacity. 2. In Ship.java, complete the sacksOfGrainType method. This method must return the number of sacks of grain of the grain type indicated by its parameter that are in the ship’s cargo. That is, if the parameter type is Grain.WHEAT and the ship’s cargo contains 42 sacks of wheat, the method should return 42. 3. In the main() method of CargoSimulator.java, there is an instance of a CargoSimulator object called sim. As described above, this object contains a list of ships, and each ship contains its list of cargo. At the location indicated, print out how many sacks of wheat each ship in sim is carrying. 4. In the main() method of CargoSimulator.java, print out a message for each ship in the CargoSimulator instance sim that is overloaded. If a ship is not overloaded, print nothing.Upon inspection of the constructor for CargoSimulator, it may appear that the data is being randomly generated. The data is “randomly” generated, but a fixed random seed is used to ensure that the same random instance of the data is generated every time the program is run. Thus, you should expect that the data will always be the same, and that you will get the same answer every time. That said, it is possible that different computers and/or operating systems will generate different data. However, on the same machine within the same operating system, the same data will be generated every time. Sample Output Here is what the output might look like. This demonstrates the form of the output only, and not the expected numbers. The exact numbers may depend on the random number generator for your operating system. ✞ ☎ The Icebreaker is carrying 37 sacks of wheat . The Salty Farmer is carrying 46 sacks of wheat . The Bunnyhug is carrying 40 sacks of wheat . The Blackstrap is carrying 37 sacks of wheat . The Prairie Onion is carrying 40 sacks of wheat . The Icebreaker is overloaded ! The Salty Farmer is overloaded ! The Blackstrap is overloaded ! ✝ ✆ For each of the following functions, give the tightest upper bound chosen from among the usual simple functions listed in Section 3.5 of the course readings. Answers should be expressed in big-O notation. (a) f1(n) = n log2 n + n 4 log280 n + 2 n 42 (b) f3(n) = 0.4n 4 + n 2 log n 2 + log2 (2 n ) (c) f2(n) = 4n 0.7 + 29n log2 n + 280 Suppose the exact time required for an algorithm A in both the best and worst cases is given by the function TA(n) = 1 280n 2 + 42 log n + 12n 3 + 280√ n (a) (2 points) For each of the following statements, indicate whether the statement is true or false. 1. Algorithm A is O(log n) 2. Algoirthm A is O(n 2 ) 3. Algoirthm A is O(n 3 ) 4. Algoirthm A is O(2 n ) (b) (1 point) What is the time complexity of algorithm A in big-Θ notation. If possible, simplify the following expressions. Hint: See slide 11 of topic 4 of the lecture slides! (a) O(n 2 ) + O(log n) + O(n log n) (b) O(2 n ) · O(n 2 ) (c) 42O(n log n) + 18O(n 3 ) (d) O(n 2 log2 n 2 ) + O(m) (yes, that’s an ‘m’, not a typo; note that m is independent of n) Consider the following pseudocode: ✞ ☎ Algorithm roundRobinTournament ( a) This algorithm generates the list of matches that must be played in a round – robin pirate – dueling tournament ( a tournament where each pirate duels each other pirate exactly once ). a is an array of strings containing names of pirates in the tournament n = a . length for i = 0 to n -1 for j = i +1 to n -1 print a [ i ] + ” duels ” + a [ j ] + “, Yarrr !” ✝ ✆ (a) (6 points) Use the statement counting approach to determine the exact number of statements that are executed by this pseudocode as a function of n. Show all of your calculations.. (b) (1 point) Express the answer you obtained in part a) in big-Θ notation. Using the active operation approach, determine the time complexity of the pseudocode in question 5. Show all your work and express your final answer in Big-Θ notation. Your Tasks The BilinkedList280 and BilinkedIterator280 classes in lib280-asn1 are incomplete. There are missing method bodies in each class. Each missing method body is tagged with a // TODO comment. Write code to implement each of these unfinished method. Implementation Notes The javadoc headers for each method explain what each method is supposed to do3 . Many of the methods you must implement override methods of the LinkedList280 superclass. Add your code right into the existing files within the lib280-asn1 module. When implementing the methods, consider carefully any special cases that might cause need to update the cursor position, or ensure that it remains in a valid state. You are not permitted to modify any existing code in the .java files given. You may only fill in the missing method bodies. Your Tasks Write a regression test for the BilinkedList280 class. You only need to test the methods that you had to write in question 7. You may generate test cases using white-box, black-box, or a combination of both methods. Comment your regression test code. Each test case should be clearly identifiable from the comments, and the comments should indicate which method(s) you are testing, the purpose of the test, and the condition(s) under which you are testing it/them. Implementation Notes Again, write the code for this question within the existing BiLinkedList280.java within the lib280-asn1 project. A function header for the regression test (main() function) has already been provided. Marks for this question are earned for generating and coding good tests, not whether or not the methods being tested actually work. This means that you can still get full marks on this question even if the methods you were supposed to code in Question 7 don’t work. 3The javadoc comments in these files are also good examples of how we will expect you to document methods that you write yourself in future assignments. Page 8 Files Provided lib280-asn1: A copy of lib280. Sack.java Object representing a sack of grain for question 1. Ship.java Object representing one of Tractor Jack’s pirate ships for question 1. CargoSimulator.java Object for simulating the loading of cargo onto Tractor Jack’s ships for question 1. Ship.java Your completed Ship object for question 1. CargoSimulator.java Your completed CargoSimulator object for question 1. assignment1.doc/docx/rtf/pdf/txt – your answers to questions 2 to 6. Acceptable file formats are Word (.doc or .docx), PDF (.pdf), rich text (.rtf), or plain text (.txt). Digital images of handwritten pages are also acceptable, provided that they are clearly legible and that they are in JPEG (.jpg or .jpeg) or PNG (.png) format. Other image formats are not accepted and will receive a grade of zero. BilinkedList280.java: Your completed doubly linked list class from question 7 and its regression test that you wrote for question 8. BilinkedIterator280.java: Your completed iterator class from question 7. Grading Rubric The grading rubric can be found on Canvas.
In this assignment, you will investigate memory access patterns, simulate the operation of page tables and implement several page replacement algorithms. This will give you some practice working with the algorithms we have been talking about in class. This assignment is based on a virtual memory simulator that uses the simvaddr-*.ref memory reference traces located at /u/csc369h/fall/pub/a4/traces . The first task is to implement virtual-to-physical address translation and demand paging using a page table design of your choice. Then you will implement two different page replacement algorithms: exact LRU (Least Recently Used) and Clock. Before you start work, you should complete the set of readings about memory, if you haven’t done so already: Paging: Introduction (http://pages.cs.wisc.edu/~remzi/OSTEP/vm-paging.pdf)The Tutorial 7 Exercise (%24CANVAS_OBJECT_REFERENCE%24/assignments/g99295e10ed471a400741e73aef899c8e) provides an introduction to the memory address traces used in the simulator.Intro video (https://web.microsoftstream.com/video/697981d9-04de-406f-9aeed38107682433)Log into MarkUs to create or update your repo and get the starter code. Remember that you cannot manually create a new a3 directory in your repo or MarkUs won’t see it. The traces from our sample programs at /u/csc369h/fall/pub/a4/traces will be interesting to run once you have some confidence that your program is working, but you will definitely want to create small traces by hand for testing. The format of the traces is reftype vaddr value as shown in the sample below.Note that the page offset part of the addresses are all between 0 and 15 (0xf) to fit in the reduced simulated physical page frames.For a write reference type (S or M), the value will be written to the virtual address. For a read reference type (L or I) the value is the expected value that should be read from the virtual address. It should always be the same as the value in the most recent preceding write reference to the same virtual address. We use this to check that the address translations and pagein/pageout operations are working correctly.A sample trace snippet is shown below: S 309001 182 S 1fff000000 55 I 108005 0 S 308008 122 L 1fff000000 55 L 308008 122 I 4cc5000 0 L 5018008 0 Note that in our traces, the Instruction reference type is likely to always have a value of 0 because these addresses are not written to after the program starts executing. You will also see Load references with a value of 0 when the trimmed trace includes a Load from an address that has not yet been written to.Implement virtual-to-physical address translation and demand paging using a pagetable design of your choice. The main driver for the memory simulator, sim.c , reads memory reference traces in the format produced by the simify-trace.py tool from trimmed, reduced valgrind memory traces (refer to the Tutorial 7 exercise (%24CANVAS_OBJECT_REFERENCE%24/assignments/g99295e10ed471a400741e73aef899c8e) for more information on how the traces are generated).For each line in the trace, the program asks for the simulated physical page frame that corresponds to the given virtual address by calling find_physpage, and then reads from the simulated physical memory at the location given by the physical frame number and the page offset. If the access type is a write (‘M’ for modify or ‘S’ for store), it will also write the value from the trace to the location. You should read sim.c so that you understand how it works but you should not modify it.The simulator is executed as ./sim -f -m -s -a where memory size and swapfile size are the number of frames of simulated physical memory and the number of pages that can be stored in the swapfile, respectively. The swapfile size should be as large as the number of unique virtual pages in the trace, which you should be able to determine easily based on your analysis from Tutorial 7.There are four main data structures that are used: 1. unsigned char *physmem : This is the space for our simulated physical memory. We define a simulated page frame size of SIMPAGESIZE and allocate SIMPAGESIZE * “memory size” bytes for physmem. 2. struct frame *coremap : The coremap array represents the state of (simulated) physical memory. Each element of the array represents a physical page frame. It records if the physical frame is in use and, if so, a pointer to the page table entry for the virtual page that is using it. 3. struct pt_entry – a page table entry.The format of a page table entry is up to you, but at a minimum it must record the frame number if the virtual page is in (simulated) physical memory and an offset into the swap file if the page has been written out to swap. It must also contain flags to represent whether the entry is Valid, Dirty, and Referenced. 4. swap.c : The swapfile functions are all implemented in this file, along with bitmap functions to track free and used space in the swap file, and to move virtual pages between the swapfile and (simulated) physical memory. The swap_pagein and swap_pageout functions take a frame number and a swap offset as arguments.The simulator code creates a temporary file in the current directory where it is executed to use as the swapfile, and removes this file as part of the cleanup when it completes. It does not, however, remove the temporary file if the simulator crashes or exits early due to a detected error. You must manually remove the swapfile.XXXXXX files in this case. To complete this task, you will have to write code in pagetable.c and pagetable.h . Read the code and comments in this file — it should be clear where implementation work is needed and what it needs to do.Basic round-robin and random replacement algorithms are already implemented for you, so you can test your translation and paging functionality independently of implementing the replacement algorithms. Efficiency: In a real operating system implementation, the memory space taken up for your page tables reduces the memory space available to store the pages of processes’ virtual address spaces. Hence, keeping page tables small is desirable.Reducing the time complexity of page table lookups is also important. Your solution will be evaluated on correctness as well as space and time efficiency.Using the starter code, implement exact LRU and CLOCK (with one ref-bit) replacement algorithms. You may find that you want to add fields to the struct frame for the different page replacement algorithms. You can add them in pagetable_generic.h , but please label them clearly.Note: to test your page replacement algorithms, we will replace your pagetable.c with a solution version, so your page replacement algorithm must be contained to the provided functions. Once you are done implementing the algorithms you can use the provided simvaddr-*.ref traces and the autotester to check the results. For each algorithm, the tester will run the programs on memory sizes 50 and 100 and check the output against the expected results.Efficiency: Page replacement algorithms must be fast, since page replacement operations can be critical to performance. Consequently, you must implement these policies with efficiency in mind. For example, we will give you the expected complexities for some of the policies: RR: init, evict, ref: O(1) in time and space CLOCK: init, ref: O(1) in time and space; evict: O(M) in time, O(1) in space, where M = size of memory LRU and MRU: evict, ref: O(1) in time and space; init: O(M) in time and space, where M = size of memory Important notes When we run the autotests on your code, your page replacement algorithms will be compiled with a different pagetable.c file (the one from the solution).All the code of the page replacement algorithms must be in their separate .c files, not in pagetable.c (except for additions to struct frame in pagetable.h ). When a page is being evicted, there should be only 2 possibilities: (i) the page is dirty and needs to be written to the swap; and (ii) the page is clean and already has a copy in the swap. A newly initialized page (zero-filled) should be marked dirty on the very first access. CLOCK must use the “Referenced” flag stored in the page table entry. All the algorithms must utilize their ref() functions (if necessary) instead of adding any algorithm-specific code to pagetable.c .There are functions in pagetable.c to get the values of the Valid, Dirty, and Referenced flags given a page table entry, which you should implement. Use these functions in your replacement algorithm implementations if you need to check any of these flags — do not assume a particular format for page table entries, or your replacement algorithms are unlikely to work with our solution version of pagetable.c .The simulator and the page replacement algorithms must not produce any additional or different (from starter code) output (except for errors that should be printed to stderr ), otherwise the tests will fail. The simulator writes a value into the simulated physical memory pages for Store or Modify references, and checks that simulated physical memory contains the last written value on Load or Instruction references. If there is a mismatch, the simulator prints an error message.These errors indicate that there is something wrong with the address translation implementation. For debugging, you will find it useful to implement the print_pagetable() function in pagetable.c. The function should print (at least) one line for each in-use page in the pagetable (valid in memory, or currently evicted to swap).Other than that, what information it displays is up to you — we will only be testing that it produces at least the expected number of outputs lines. You can use the debug flag in sim.c to control extra output during development. (NOTE: remember to set it to false in your final submission).
You will be implementing a version of the Very Simple File System (https://q.utoronto.ca/courses/315157/file_contents/course%20files/tutorials/A5-vsfs-dumptool.pdf? canvas_=1&canvas_qs_wrap=1) (VSFS) from the OSTEP text and lectures.We will be using FUSE to interact with your file system. FUSE allows you to implement a file system in user space by implementing the callback functions that the libfuse library will call. The Tutorial 7 Exercise (https://q.utoronto.ca/courses/315157/assignments/1146491) should give you some practice with using FUSE.Your tasks include: Implement the code to format an empty disk into a VSFS file system by completing mkfs.c (this will be compiled into the mkfs.vsfs executable). This part of the assignment does not need FUSE at all. Implement the FUSE functions to list the root directory, and to create, remove, read, write, and resize files, as well as get status information about files, directories, or the overall file system, by completing vsfs.c .We are providing a set of formatted VSFS disk images so that you can work on these two parts of the assignment independently.Refer to the Tutorial 7 Exercise (https://q.utoronto.ca/courses/315157/assignments/1146491) handout for instructions on getting started with FUSE. If you would like to learn more about FUSE: libfuse GitHub repository: https://github.com/libfuse/libfuse (https://github.com/libfuse/libfuse) FUSE wiki: https://github.com/libfuse/libfuse/wiki (https://github.com/libfuse/libfuse/wiki) (https://github.com/libfuse/libfuse) FUSE API header file for the version we’re using: https://github.com/libfuse/libfuse/blob/fuse_2_9_bugfix/include/fuse.h (https://github.com/libfuse/libfuse/blob/fuse_2_9_bugfix/include/fuse.h)Unlike the passthrough file system of the tutorial exercise, your VSFS file system will operate on a disk image file. A disk image (https://en.wikipedia.org/wiki/Disk_image) is simply an ordinary file that holds the content of a disk partition or storage device.To allow you to test your file system operations independently of your file system format code ( mkfs.vsfs ), we have provided some simple VSFS-formatted disk images in the course pub directory on teach.cs at /u/csc369h/fall/pub/a4/images: vsfs-empty.disk – Small, empty file system (64 inodes, 1 MB size). Contains just root directory with ‘.’ and ‘..’ entries. vsfs-empty2.disk – Another small, empty file system (256 inodes, 1MB size).Contains just root directory with ‘.’ and ‘..’ entries. vsfs-maxfs.disk – Maximum size VSFS file system (512 inodes, 128 MB size). Contains just root directory with ‘.’ and ‘..’ entries. vsfs-1file.disk – Small file system (64 inodes, 1 MB size) containing a single small file (only 1 data block) in the root directory. vsfs-3file.disk – Medium file system (128 inodes, 16 MB size) containing 3 files (small – only direct blocks, medium – some indirect blocks, and maximum VSFS file size). vsfs-42file.disk – Medium file system (128 inodes, 16 MB size) containing 42 small files (root directory inode uses multiple direct blocks). vsfs-many.disk – Small file system (256 inodes, 2 MB size) containing lots of small files (root directory inode uses indirect block pointer).You will need to make your own copies of these disk images to use them, since you will need to be able to write to them. You will also need to create your own empty disk images that you can format using your mkfs program. To do so, you will run the following commands: truncate -s ./mkfs.vsfs -i The truncate command will create the image file if it doesn’t exist and will set its size; mkfs.vsfs will format it into your vsfs file system (after you have completed the implementation).Once you have a formatted vsfs disk image (one of ours, or your own) the next step is to mount your file system. We assume that you will be using /tmp/userid as in the Tutorial 7 exercise as the mountpoint, and that you will want to keep it running in the foreground so that you can see your output as it runs: ./vsfs -f The image file is the disk image formatted by mkfs.vsfs . Not only does vsfs mount the disk image into the local file system, it also sets up callbacks and then calls fuse_main() so that FUSE can do its work. Both vsfs and mkfs.vsfs have additional options – run them with -h to see their descriptions.After the file system is mounted, you can access it using standard tools (ls, cp, rm, etc.). To unmount the file system, run: fusermount -u Note that you should be able to unmount the file system after any sequence of operations, such that when it is mounted again, it has the same contents.The name fsck comes from the common tool (https://en.wikipedia.org/wiki/Fsck) for checking the consistency of file systems in Unix-like operating systems. We provide two executables on teach.cs servers for checking the consistency of images, in the /u/csc369h/fall/pub/a4/tools/ directory: fsck.mkfs checks that your mkfs.vsfs implementation correctly formats the disk. fsck.vsfs checks that your code that performs various file system operations (written in vsfs.c ) has not corrupted the file system.For this assignment, we make a number of simplifying assumptions: VSFS file systems are always small enough that they can be entirely mmap’d into the vsfs process’s virtual address space. The underlying operating system will handle all write-back of dirty pages to the vsfs disk image. If the file system crashes, the disk image may be inconsistent. Your code should not crash, but it does not need to make any special effort to maintain crash consistency.There is a flat namespace. All files are located in the root directory and there are no subdirectories. You do not need to implement mkdir or rmdir. All paths are absolute (they all start with ‘/’). If you see a path that is not absolute, or that has more than one component, you can return an error.First read through all of the starter code to understand how it fits together, and which files contain helper functions that will be useful in your implementation. mkfs.c – contains the program to format your disk image.You need to write part of this program. You will also find it helpful to read the code to see how we access parts of the file system after using mmap() to map the entire disk image into the process virtual address space.vsfs.h – contains the data structure definitions and constants needed for the file system. You may add other definitions or constants that you find useful, but you should not change the file system metadata. That is, do not add or modify fields in the superblock, inode, or direntry structures and do not change the existing definitions. vsfs.c – contains the program used to mount your file system. This includes the callback functions that will implement the underlying file system operations.Each function that you will implement is preceded by detailed comments and has a “TODO” in it. Please read this file carefully. NOTE: It is very important to return the correct error codes (or 0 on success) from all the FUSE callback functions, according to the “Errors” section in the comment above the function. The FUSE library, the kernel, and the user-space tools used to access the file system all rely on these return codes for correctness of operation.Note: You will see many lines like (void)fs; . Their purpose is to prevent the compiler from warning about unused variables. You should delete these lines as you make use of the variables. fs_ctx.h and fs_ctx.c – The fs_ctx struct contains runtime state of your mounted file system. Any time you think you need a global variable, it should go in this struct instead. We have cached some useful global state in this structure already (e.g. pointers to superblock, bitmaps, and inode table), but you may find there is additional state that you want to add, instead of recomputing it on every operation. map.h and map.c – contain the map_file() function used by vsfs and mkfs.vsfs to map the image file into memory and determine its size. You should not need to change anything here, or make any additional calls to the map_file() function beyond what is in the starter code. options.h and options.c – contain the code to parse command line arguments for the vsfs program. You should not need to change anything here. util.h – contains some handy functions: is_powerof2(x) – returns true if x is a power of two. is_aligned(x, alignment) – returns true if x is a multiple of alignment (which must be a power of 2). align_up(x, alignment) – returns the next multiple of alignment that is greater than or equal to x. div_round_up(x, y) – returns the integer ceiling of x divided by y. bitmap.h and bitmap.c – contain code to initialize bitmaps, and to allocate or free items tracked by the bitmaps. You will use these to allocate and free inodes and data blocks, so make sure you read the functions and understand how to use them. You may notice that the bitmap_alloc function can be slow, since it always starts the search for a 0 bit from the start of the bitmap. You are free to improve on this if you wish, but you do not need to do so. You are welcome to put some of the helper functions in separate files instead of keeping everything in vsfs.c . Make sure to update the Makefile to compile those files and add/commit/push them to your git repository.You should tackle this project in stages so that you can be confident that each piece works before moving on to the next step. The creation of a new file system (mkfs.c) and operations on a formatted file system (vsfs.c) can be handled independently however, so you can do Steps A and B in either order.Step A1: Write enough of mkfs.vsfs so that you can mount the file system and check the superblock.We have implemented vsfs_statfs() in vsfs.c so that you can mount the file system in your disk image and then run stat -f on the root directory to check that the superblock is initialized correctly by your mkfs . Step A2: Complete the implementation of mkfs.vsfs . Use the provided fsck.mkfs tool to check the correctness of the file system as you proceed.Step B1: Write vsfs_getattr() . You have probably seen from the tutorial exercise that FUSE calls getattr() a lot. Implementing this function is the key to the rest of the operations. You will want to write a helper function that takes a path and returns a pointer to the inode (or the inode number) for the last component in the path. Remember that you only need to handle paths that are of the form “/” or “/somefile” – all paths are absolute and there are no subdirectories in our vsfs file systems.Step B2: Write vsfs_readdir() so that you can run ls -la on the root directory when the root directory entries fit within a single data block. You should be able to mount vsfs-empty.disk, vsfs-maxfs.disk, vsfs1file.disk and vsfs-3file.disk and list their root directories on completion of this step. Step B3: Add the ability to create and remove empty files by implementing vsfs_create() and vsfs_unlink() . On completion of this step, you should be able to mount vsfs-empty.disk and use ‘ touch /tmp/userid/anewfile’ to create a new empty file.The new file should be visible and the mode and timestamps should be appropriate when you ‘ls -l’ on the root directory. You should also be able to delete the new file you created (e.g. ‘ rm /tmp/userid/anewfile ‘). Step B4: Add the ability to grow a file up to the limit of the inode’s direct block pointers, or shrink a file to empty, using truncate. Implement vsfs_truncate() . This operation shares functionality with writing to a file (increasing the file size) or removing a file (freeing all the blocks allocated to the file), so think about how you can avoid duplicating code.Step B5: Add the ability to write to, and read from, small files, first where the data is stored in a single data block, and then when the data can be stored using only the direct block pointers in the inode. Implement vsfs_write() and vsfs_read() . Step B6: Add the ability to remove small files (where the file data uses only the direct block pointers in the inode).Step B7: Enhance your implementation of vsfs_readdir() to list larger directories, first using just the direct blocks in the directory inode, and then using the directory inode’s indirect block to read all of the directory data blocks. You should be able to mount vsfs-42file.disk (direct blocks only) and vsfsmany.disk (direct and indirect blocks) and list the root directory on completion of this step.Step B8: Enhance your implementations of vsfs_truncate() , vsfs_write() , vsfs_read() , and vsfs_unlink() to support large files, where the indirect block in the file’s inode is used to locate some of the file’s data blocks. Tip: Comment your code well. It will help you keep track of what is implemented and your understanding of how things work. Refactor your code during development (not after) and keep your functions short and well-structured.Tip: Check that there is enough space before making any changes to the file system. This will save you from having to roll back changes if you discover that an operation cannot be completed due to lack of space. Tip: Remember to update fields in the superblock (e.g. free_inodes, free_blocks) as you operate on the file system.You can use standard Unix tools to manipulate directories and files in a mounted vsfs image in order to test your implementation.System call tracing with strace can help understand what syscalls they invoke to access the file system. You can, in general, use the behaviour of the host file system (ext4) as a reference – your vsfs should have the same observable behaviour for operations that vsfs needs to support. You can also write your own C programs that invoke relevant syscalls directly.You will find it useful to run vsfs under gdb : gdb –args ./vsfs -d You can then run file system operations in a separate terminal window. You can set breakpoints at the start of your FUSE callback functions (e.g. break vsfs_getattr ) to help you understand what callbacks are invoked when you execute a file system operation (e.g. ls), in what order, and with what arguments. The debugger is also helpful in investigating crashes (e.g., segfaults) and stepping through the execution of the callback functions so that you can check your the state of the filesystem as the operations execute.Off-by-one errors are common but can be catastrophic when they lead to accessing the wrong block of file system metadata. You might also find it useful to view the binary contents of your vsfs image files using xxd . See man 1 xxd for documentation. To avoid errors when mounting the file system, make sure that the mount point is not in use (e.g. by a previous vsfs mount that didn’t finish cleanly). If fusermount fails to unmount because the mount point directory is “busy”, you can use the lsof command (see man lsof ) to identify the process that keeps it open.One common error message you might see when running operations on the mounted file system is “transport endpoint is not connected”. This error usually means that the file system is still mounted, but the vsfs program has terminated (e.g. crashed). In this case you need to manually unmount it with fusermount -u . One of the most common errors you might see at the early stages of the implementation is ls -la reporting an “I/O error” and displaying “???” entries.This error usually means that your getattr() callback returns invalid data in the stat structure and/or an invalid return value. To test reads at a given file offset, you can use the tail -c command (see man 1 tail ). To test either reads or writes at a given file offset, you can write your own C programs that use pread() and pwrite() .The maximum number of inodes in the system is a parameter to mkfs.vsfs , the image size is also known to it, and the block size is VSFS_BLOCK_SIZE (4096 bytes – declared in vsfs.h). Many parameters of your file system can be computed from these three values. We will not test your code on an image smaller than 64 KiB (16 blocks) with 4 inodes.You should be able to fit the root directory and a non-empty file in an image of this size and configuration. You shouldn’t pre-allocate additional space for metadata (beyond the fixed metadata defined for VSFS, the space needed to store the inode table and the root directory) in your mkfs.vsfs implementation. Indirect blocks should only be allocated on demand, when a file or directory grows large enough to need it. The maximum path component length is VSFS_NAME_MAX (252 bytes including the null terminator). This value is chosen to fit the directory entry structure into 256 bytes (see vsfs.h ).Names stored in directory entries are null-terminated strings so that you can use standard C string functions on them. The maximum full path length is _POSIX_PATH_MAX (4096 bytes including the null terminator). This allows you to use fixed-size buffers for operations like splitting a path into a directory name and a file name. The maximum file size is dictated by the number of direct block pointers in a vsfs inode (VSFS_NUM_DIRECT) and the number of block pointers in an indirect block (VSFS_BLOCK_SIZE / sizeof(vsfs_blk_t)).The number of directory entries is limited by the maximum number of directory entry data blocks (same as the limit on file blocks). The number of blocks in your file system is limited by the number of bits in a single VSFS block, since we use only 1 block for the data bitmap. You can assume that read and write operations are performed one block at a time. Each read() and write() call your file system receives will only cover a range within a single block.NOTE: this does not apply to truncate() – a single call needs to be able to extend or shrink a file by an arbitrary number of blocks. Sample disk configurations that must work include: 64KiB size and 4 inodes 64KiB size and 16 inodes1MiB size and 64 inodes 128MiB size and 512 inodes We will not be testing your code under extreme circumstances so don’t get carried away by thinking about corner cases. However, we do expect you to properly handle “out of space” conditions in your code. Any operation that cannot be completed because there are not enough free blocks or inodes must be cleanly aborted – no blocks or inodes can “leak” in the process. The simplest way to ensure this is to check that there is enough space to complete the operation before modifying any file system metadata.The formatting program ( mkfs ) must also check that the image file is large enough to accommodate the requested number of inodes. Other implementation notes: Although the “.” and “..” directory entries can be manually listed by the vsfs_readdir() callback (as in the starter code), you should create actual entries for these when you initialize the root directory in mkfs(). The only timestamp you need to store for each file and directory is mtime (modification time) – you don’t need to store atime and ctime .You can use the touch command to set the modification timestamp of a file or directory to the current time. Any data and metadata blocks (other than the fixed metadata) should only be allocated on demand. Read and write I/O should be performed by reading/writing the virtual memory where the disk image is mmap’d. It should NOT be performed byte-by-byte (which is very inefficient); use memcpy() . Your implementation shouldn’t use any floating point arithmetic.See the helper functions in util.h – if you need other, similar, functions (like floor), they can also be easily implemented using integer arithmetic.It is recommended that you include a README.txt file that describes any aspects of your code that do not work well. Code that works well and implements a subset of the functionality will get a higher mark than code that attempts to implement more functionality but doesn’t work.Add all the starter files from MarkUs to your a4 repository.Also add to your repository all additional source code files that you create as part of your implementation. Your a4 repository must contain all the files necessary to compile and run mkfs.vsfs and vsfs . It may include a README file as described above.Do NOT add and commit virtual machine images, executables, .o or .d files, disk image files, or any other unnecessary files – you will lose code style marks if you do submit those. You are welcome to commit test code and other text files. You should use a .gitignore file to help ensure you only commit and push files you should.
This assignment will provide you with experience in dealing with concurrency by using correct synchronization. Nearly all modern systems are faced with managing concurrency in order to better utilize their hardware. We’ll be working on this project in the context of an HTTP server, something that you are already well acquainted with after Assignment 1.We are going to split the assignment up into three checkpoints to help you best manage your time. The checkpoints will ramp up in difficulty, so keep up with the work! You will also probably find it helpful to think about the design of your server before you start building the code. A well-considered design is extra important when dealing with multiple threads.You will be adding multi-threading and an audit log to your HTTP server from Assignment 1. Multi-threading will enable your server to serve multiple clients simultaneously, thus improving the throughput of your server. Audit logging will provide a record of the actions that your server performs.Audit logging is very common in practice; you also might find it a very useful tool to help you debug and test your software, especially since your multi-threaded server will likely be non-deterministic. To help you budget your time throughout this project, you will turn in your project at three checkpoints. Each checkpoint will require partial functionality: first, you will implement the audit logging, then the work-queue, and finally the atomicity of file system operations.See the checkpoint section below for more details. Checkpoint Folder Task Points Due 1 asgn2 Audit Logging 50 May 11 @ 12:01 AM 2 asgn3 Work Queue 50 May 24 @ 12:01 AM 3 asgn4 Atomic Requests 100 Jun 01 @ 12:01 AM The code that you submit must be in your repository on git.ucsc.edu. In particular, your assignment must build your HTTP server, called httpserver, when we execute the command make from the directory specified in the checkpoint folder above (i.e., asgn2 for the first checkpoint, asgn3 for the second checkpoint, and asgn4 for the third checkpoint).In each checkpoint, you should include a README.md file that tracks the interesting design decisions and outlines the high-level functions, data-structures, and modules that you used in your code. For the second and third checkpoints, the README.md should also include a description of why your system is thread-safe (i.e., why does it work even when multiple threads are operating concurrently?). This description should talk about which variables are shared across threads, how they are modified, what critical sections you have, etc.You must submit a 40 character commit ID hash on Canvas in order for us to identify which commit you want us to grade. We will grade the last hash that you submit to each of the checkpoints on Canvas and will use the timestamp of your last upload to determine grace days. For example, if you post a commit hash 36 hours after the deadline, we will subtract 2 grace days from your total. We will use the final checkpoint to assign bonus points—i.e., you will earn bonus points by submitting to the third checkpoint early. Your server must implement the functionality explained below subject to the limitations below.Your code will necessarily build on Assignment 1, so there is a benefit to starting with an Assignment 1 that uses abstraction and modularity well. However, we’ve minimized the dependency between the assignments by limiting the Assignment 1 functionality that we will test. 1 Functionality In this assignment, you’ll build on your program from Assignment 1.We expect you to use your code from Assignment 1, and also to reuse code across each checkpoint. But be sure to copy the code that you want tested to the the folder for each checkpoint (asgn2, asgn3, and asgn4). Your new httpserver should take three command line arguments, port—the port to listen on (this is the same as assignment 1)—threads—the number of worker threads to use, and logfile—the file in which to store your audit log.The port argument is required, the threads argument is optional (defaulting to 4), and the logfile is optional (defaulting to writing to stderr). We have provided starter code that uses getopt to parse the command line alongside this assignment document. The usage of the server is the following: ./httpserver [-t threads] [-l logfile] Like in Assignment 1, your server will create, listen, and accept connections on a socket that is listening on a port. However, it will also use threads worker threads in order to support multiple clients at the same time, and will output an audit log to the location specified by logfile.Below, we provide details about the audit log, worker queue, and the atomicity and coherency guarantees that your server must provide. Each checkpoint in this assignment will test for these features one-by-one. We then provide some high-level guidance on what synchronization libraries you should use, and describe the assignment 1 functionality that your server must implement (this will help you ensure that you have a decent place from which to start building your server).Audit Log Your server must log the requests that were made to it in the order in which the server processes them. When your server processes each request, it should add an entry to the log. Each entry must have the following format: ,,, The comma separated, single line of text, starts with the type of operation that was performed, i.e., PUT, GET, or APPEND. Then, the line includes the URI (With the same limitations as in Assignment 1, i.e., the format /%19[A-Z,a-z .]s). The line should then include the status code produced in the response to the request.Finally, the line should include the value of an HTTP header, called RequestID, or the keyword 0 if the RequestID header was not found in the request associated with the line. There should not be any partial, overwritten, or otherwise corrupted lines in your log. The log must be consistent with the responses that your server produces: If request, R1, is before a request, R2, in the log, then your server must have processed R1 and R2 such that R1 happens before R2. This is especially important for operations that conflict (e.g., requests that modify the same URI). The audit log entry should reflect the status code that your server intended to send to the client in its response.This is relevant if your server has an issue sending the right data to a client (e.g., if a server is unable to send an entire message body because the client closes a message). Your log must be durable; the server must ensure that the log entries for each request processed by your server are resident in the log. We will send a SIGTERM signal to kill your server and wait for the server to terminate on shutdown, so the requirement is that the log entries are resident in the log after your serve handles the SIGTERM. The starter code includes a signal handler that you can modify as needed to help you with this task. Please note, if your server does not gracefully terminate after the “polite” SIGTERM within 5 seconds, then we will kill your process with a SIGKILL.If signal handlers freak you out, you can also ensure that each log entry is flushed immediately after being written. 2 Example. If we send the following requests one-after-the-other, assuming that hello.txt exists initially, but goodbye.txt does not: GET /hello.txt HTTP/1.1r Request-Id: 1r r GET /goodbye.txt HTTP/1.1r Request-Id: 2r r PUT /goodbye.txt HTTP/1.1r Request-Id: 3r Content-Length: 3 r r bye GET /goodbye.txt HTTP/1.1r r then your server should produce the log: GET,/hello.txt,200,1 GET,/goodbye.txt,404,2 PUT,/goodbye.txt,201,3 GET,/goodbye.txt,200,0Your server must use a thread-pool design, a popular concurrent programming construct for implementing servers. A thread pool has two types of threads, worker thread, which actually process requests, and a dispatcher thread, which listens for connections and dispatches them to the workers. Worker Threads Your server must create exactly threads worker threads (Note: this means that the server must have a total of threads + 1 threads).A worker thread should be idle (i.e., sleeping by waiting on a lock, conditional variable, or semaphore) if there are no requests to be processed. Each worker thread should perform the HTTP processing from Assignment 1 when a request arrives. You will have to implement correct synchronization to ensure that your server properly maintains state that is shared across worker threads.You must ensure that the output of your server is indistinguishable from the output that a single-threaded version would produce. Potential pitfalls include ensuring that the each request gets its intended response, and ensuring that all requests eventually receive a response, among others. On a related note—your server must concurrently process requests when it is safe to do so. You cannot simply fork threads, but only perform work in a single thread. Dispatcher Thread Your server should create a single dispatcher thread. Note: Your server must call pthread create exactly threads times, so the dispatcher thread should probably be the main thread.The dispatcher should wait for connections from a client. Once a connection is initiated, the dispatcher should alert one of the worker threads and listen for a new client. If there are no idle worker threads, then the dispatcher should wait until a worker thread finishes its current task. Your server will have to implement correct synchronization to ensure that the dispatcher thread and worker threads correctly “hand-off” client requests without dropping any client requests, corrupting any data, or crashing the server. Example. Suppose that we start your server with two threads.Your server should create two worker threads and one dispatcher thread (Note: one of these should be the main thread, the thread that called main()). The worker threads should wait for requests to arrive, while the dispatcher thread should wait for a connection on its listen socket (i.e., calling accept() on the listen socket, as is done in the starter code for Assignment 1). Then, suppose that we send the following three requests concurrently (i.e., at the same time): GET /hello.txt HTTP/1.1r Request-Id: 1r r GET /goodbye.txt HTTP/1.1r Request-Id: 2r r GET /hellogoodbye.txt HTTP/1.1r Request-Id: 3r r The dispatcher thread should wake up one of the worker threads to handle one of the requests and wake up another worker thread to handle a second of the requests. The dispatcher should account for the third, unprocessed, request. You have a number of potential designs for this, such as (1) waiting until a worker thread is idle or (2) storing the unprocessed request somewhere and returning to listening for a connection. As soon as either worker finishes processing its request, that worker should begin processing the third and final request. The other thread should go back to a waiting state after it finishes processing its request, as should the thread that processed two requests.After all of this processing, the server should be back in the steady state of having (1) the workers waiting for requests to arrive and (2) the dispatcher thread waiting for a connection (i.e., calling accept() on the listen socket). Atomicity and Coherency While your server is multithreaded, it must process requests atomically and coherently. The server’s request processing must follow a total ordering—i.e., for all pairs of requests, R1 and R2, the response to R1 and R2 must be equivalent to output that would be produced if R1 happens-before R2 or R2 happens-before R1, where we say that R1 happens-before R2 if and only if the response of R1 is produces before the server begins processing R2. For example, suppose that R1 and R2 are APPEND requests that append the content, hello 1 , and hello 2 , respectively, to a URI that points to an empty file.The end content of the file pointed to by the URI must be either: hello 1 hello 2 or hello 2 hello 1 This essentially stipulates that the operations must be atomic. Additionally, suppose that R1 and R2 are PUT requests that update the content of a URI that points to an empty file to be hello 1 , and hello 2 , respectively. Further, suppose that R3 is a request that occurs after R1 and R2. Then, if R1 happens before R2, then R3 must return a content body of hello 2 ; if R2 happens before R1, then R3 must return a content body of hello 1 (note: there is no other case since each request must have a total ordering with respect to all other requests).This requirement enforces coherency. The audit log produced by your server must encode the total order of your servers processing. That is, if your server processes R1 before R2, then your log must indicate that R1 happened-before R2. Think carefully about how the atomicity and coherency constraints interact with the audit log and thread-pool design! Getting this correct is a tough challenge :). Example. Suppose that we start your server with two threads.Your server should create two worker threads and one dispatcher thread (n.b., one of these should be the main thread, the thread that called main). The worker threads should wait for requests to arrive, while the dispatcher thread should wait for a connection on its listen socket (i.e., calling accept() on the listen socket, as is done in the starter code for assignment 1).Then, suppose that we send the following three requests concurrently (i.e., at the same time), assuming that goodbye.txt does not exist initially: GET /goodbye.txt HTTP/1.1r Request-Id: 1r r PUT /goodbye.txt HTTP/1.1r Request-Id: 2r Content-Length: 3 r r bye Your server can produce either of the following combinations or responses and audit log. It’s very important, however, that the server produces a combination listed below (i.e., it cannot produce an audit log from one option but the responses from another): 4 Option 1. Audit Log GET,/goodbye.txt,404,1 PUT,/goodbye.txt,201,2 Request-Id Response 1 HTTP/1.1 404 Not Foundr Content-Length: 10 r r Not Found 2 HTTP/1.1 201 Createdr Content-Length: 8 r r Created Option 2. Audit Log PUT,/goodbye.txt,201,2 GET,/goodbye.txt,200,1 Request-Id Response 2 HTTP/1.1 201 Createdr Content-Length: 8 r r Created 1 HTTP/1.1 200 OKr Content-Length: 3 r r OK The dispatcher thread should wake up one of the worker threads to handle one of the requests and wake up another worker thread to handle a second of the requests. The dispatcher should account for the third, unprocessed, request. You have a number of potential designs for this, such as (1) waiting until a worker thread is idle or (2) storing the unprocessed request somewhere and returning to listening for a connection. As soon as either worker finishes processing its request, that worker should begin processing the third and final request.The other thread should go back to a waiting state after it finishes processing its request, as should the thread that processed two requests. After all of this processing, the server should be back in the steady state of having (1) the workers waiting for requests to arrive and (2) the dispatcher thread waiting for a connection (i.e., calling accept() on the listen socket).Additional Functionality In addition to supporting the methods listed above, your project must do the following: • httpserver should not have any memory leaks. Your server must cleanup any memory that it uses in its SIG TERM handler; the starter code has a signal handler to help you get started on this task! • httpserver must be reasonably efficient. • Your code should be formatted according to the clang-format provided in your repository and it should compile using clang with the -Wall -Werror -Wextra -pedantic -lpthread compiler flags.The -lpthread flag is what allows your program to use the pthread library (see Hints). Limitations You must write httpserver using the C programming language. Your program cannot use functions, like system or execve, that allow you to execute external programs. If your submission does not meet these minimum requirements, then the maximum score that you can get is 5%. Carry-over from Assignment 1 There is a necessary dependency between this assignment and your Assignment 1. However, we want to minimize the number of “double-jeopardy” issues that arise.Consequently, we have drastically limited the 5 scope of requests that you will need to handle. In particular, you may assume that each request will be correctly formatted. I.e., there are no invalid requests—if your server reads some bytes, those bytes belong to some valid HTTP request. You will only need to produce the following status codes: Status-Code Status-Phrase Message-Body Usage 200 OK OK When a method is Successful 201 Created Created When a URI’s file is created 404 Not Found Not Found When the URI’s file does not 500 Internal Server Error Internal Server Error When an unexpected issue prevents processing Checkpoints There are three checkpoints for this assignment.In the first, you need to implement the audit log, but will not need to worry about multiple threads. In the second, you will need to implement the Work Queue, but do not need to worry about HTTP method atomicity. Finally, in the third, you will implement the final atomic requests and ensure that the audit log, work queue, and atomic requests all operate correctly in tandem. Checkpoint 1. You will implement the audit log. Our tests will start your server with the default thread options, but you don’t need to actually create the worker threads.This should be a fairly straightforward application of things that we’ve discussed in this course and is a good opportunity for you to ensure that you have all of the necessary Assignment 1 behavior ironed out. This checkpoint will be worth 50 points and should be turned in through the asgn2 folder in your repository. Checkpoint 2. You will implement the Work Queue. Our tests will start your server with a variety of different numbers of threads, you will need to ensure that you create the correct number. Your server will need to return valid responses when serving a large number of concurrent clients. You will need to ensure that your server does not busy wait, but also processes requests as soon as possible.However, we will ensure that the client requests are all non-conflicting (i.e., you will not need to worry about atomicity and coherency concerns for these tests). This will allow you to focus entirely on the Work Queue part of this assignment independently from the rest. Note–your audit log does not need to be managed atomically for Checkpoint 2 (i.e., you can have log entries that overwrite and intermix with each other). This checkpoint will be worth 50 points and should be turned in through the asgn3 folder in your repository. Checkpoint 3.You will implement the atomicity and coherence in the third checkpoint. This checkpoint is a superset of the past two checkpoints, i.e., you will need to perform all of the functionality from Checkpoints 1 and 2. Your server will need to start the correct number of threads, manage the work queue using synchronizaiton to ensure that all client requests are processed correctly. Your server should perform all operations atomically and coherently, ensuring that it processes each HTTP method in a total order that matches the total order in the audit log.Your audit log will need to be managed atomically for Checkpoint 3. Finally, your server should not busy loop (i.e., Worker threads should sleep when there is not work to be performed), and should also process requests as fast as possible (i.e., it should aim for the highest possible throughput). This checkpoint will be worth 100 points and should be turned in through the asgn4 folder in your repository. 6 Testing your Code We will be implementing a new testing approach.Our aim is to encourage you to perform your own testing in order to debug your code, rather than using the pipeline to debug your code. As such, you will be able to, on a daily basis, see how your program performs on every test, and, on a per-push basis, see how your program performs on a subset of tests: • Each day at 9AM, I will execute the full suite of tests on the default branch of your git@ucsc repository. You will receive an email that indicates the aggregate score (e.g., xx/85 functionality points) that your current commit achieves. • Each time you push your code to git@ucsc, the pipeline will check formatting, make, and execute a few of the functionality tests.We will show a small English description of these tests on the pipeline. Hints Synchronization Your server must use the POSIX threads library (pthreads) to implement multithreading. The pthread library is MASSIVE, but you’ll only need a few things for this assignment. In particular, you might find the following groups of functions to be useful (you probably won’t use them all, though): • pthread create: create a thread • pthread mutex init, pthread mutex lock, and pthread mutex unlock: the pthread mutex implementation • sem init, sem wait, and sem post: the pthread semaphore implementation • pthread cond init, pthread cond signal, and pthread cond wait: the pthread condition variable implementationYou will also probably find the function, flock, to be useful for helping atomically update files. Other Tips • There are many functions that are not “re-entrant”, which means that you cannot safely use them with multiple threads at the same time (e.g., strtok). These functions generally have a “re-entrant” version (e.g., strtok r). • You will likely need to lookup how some system calls (e.g., read) and library functions (e.g., warn) work. You can always Google them, but you might also find the man pages useful (e.g., try typing man 2 read on a terminal).• There are a few ways to test httpserver. Below, we assume that you started httpserver on port 1234 by executing the command ./httpserver 1234. We also assume that you are using your client on the same machine upon which the server is currently executing: • You can use an HTTP Client, such as a web browser. We recommend testing with curl, a command-line HTTP client. curl can produce both GET and PUT commands. For example, to execute a GET of the file foo.txt on httpserver and place the output into the file download.txt, you execute: curl http://localhost:1234/foo.txt -o download.txt curl can execute PUT and GET commands; use help curl or man curl on a terminal to learn more.• You can also use nc (“netcat”). To connect to your server, execute nc localhost 1234. Then, you can type in the text that you wish to send to your server. You can also automate this approach by piping data to nc. For example, to send the PUT command listed above to your server, execute: printf “PUT /foo.txt HTTP/1.1r Content-Length: 12r r Hello World!” |nc localhost 1234 7 • If you try to start your server immediately after killing a previous instance of it, you will likely see the following error: httpserver: bind error: Address already in use In this case, just restart the server with a different port number.The issue is that the operating system must ensure unique ports are used across the entire system; it often waits to gracefully close ports even after the process that was using them terminates. Grading Each Checkpoint will be graded with the following breakdown: • Functionality tests: 70% • README design doc: 15% • Coding style: 15% Starter Code Your starter code does four basic things for you: • Your starter code parses and validates command-line arguments passed to your HTTP server.• Your starter code creates a socket, binds that socket to the local interface, and then listens for requests on the socket. The starter code calls handle connection() for each request, which simply echoes bytes passed to the established connection file descriptor connfd. • Your starter code includes a signal handler that ignores the SIGPIPE signal. This handler makes it so that socket failures will result in setting errno to EPIPE rather than throwing a signal. • Your starter code also includes a signal handler that calls sigterm handler() whenever SIGTERM is signaled.
This assignment will provide you with experience building a system that uses strong modularity. Additionally, this will provide you with an opportunity to apply the things we will learn about client/server systems in class to the real world. This assignment is a fair bit more complex than Assignment 0; you would do well to get a head start on the task.You will be building an HTTP server for this assignment. Your server should execute “forever” without crashing (i.e., it should run until a user types CTRL-C on the terminal). Your server should process incoming HTTP commands from clients; we provide starter code to help you accept incoming commands. The code that you submit must be in your repository on git.ucsc.edu. In particular, your assignment must build your HTTP server, called httpserver, when we execute the command make from the directory asgn1 in your repository.Your repository must include a README.md file that includes information about the interesting design decisions and outlines the high-level functions, data-structures, and modules that you used in your code. The README.md should also include how your design implements any “vague” requirements listed in this document. You must submit a 40 character commit ID hash on Canvas in order for us to identify which commit you want us to grade.We will grade the last hash that you submit to the assignment on Canvas and will use the timestamp of your last upload to determine grace days and bonus points. For example, if you post a commit hash 36 hours after the deadline, we will subtract 2 grace days from your total.Your server must implement the functionality explained below subject to the limitations below. You’ll need to handle bad or poorly formatted requests in accordance with the way they are handled by the reference implementation.Functionality Your server will create, listen, and accept connections on a socket that is listening on an port. A socket is an abstraction provided by the operating system and libc that represents a connection with an external entity. For the purposes of this project, you should think of a socket as equivalent to a file descriptor: It is an integer that represents a sequence of characters.You can receive bytes in the order that they were written by the other side (i.e., the client) by calling read and using the socket as the file descriptor. You can write bytes to the other side by calling write using the socket as the file descriptor; the bytes that you write will be received by the other side (i.e., the client) in the order in which you write them.Your server should take a single command-line argument, an int, to specify the port that your server will listen on. Namely, you should start your server using the following command: ./httpserver We have provided starter code alongside this assignment that simplifies working with the socket and managing the command-line arguments1 . The starter code creates a socket that listens on the localhost interface with the port provided on the command line. When you test your httpserver, you will specify localhost and the port that you provided to httpserver to establish a connection; the Hints section below gives some tips for this process. The starter code manages the socket such that you can treat network programming as simply as interacting with file descriptor.Your task is to implement the handle connection function in the starter code, 1We describe some details of the starter code at the end of this document 1 which takes a socket as input and should process client HTTP requests. In particular, the httpserver should support three types of HTTP operations: GET, PUT, and APPEND. Below, we first describe the HTTP Protocol, and then describe what each of these operations should do for a valid HTTP request. HTTP Protocol The HTTP 1.1 protocol is described in detail in Request For Comments: 2616 (abbreviated RFC 2616)2 , which is a standards document produced by the Network Working Group. RFC 2616 describes all of the functionality that an server and client needs to support for the HTTP 1.1 protocol.We have simplified the features that you must support for this project and have created a new operation, APPEND, for you to implement. Requests Regardless of the type of operation, valid HTTP requests will follow the grammar below. To make your processing easier, you may assume that the total length of the request-line and all header-fields is less than or equal to 2048 for any valid request: Request = Request-Liner ; [Required] (Header-Fieldr )* ; [Optional, repeated] r Message-Body ;[Optional] • Request-Line. Every valid request must include exactly one request-line. The request-line specifies the method to be performed, the object upon which to perform it, and the HTTP version. A client denotes the end of a request-line using the sequence r . The format of request-line is as follows: Method URI Version In detail, Method, URI, and Version are as follows: • Method Valid requests will include a Method, a case-sensitive sequence of characters within the range [a-z, A-Z] (i.e., ”HeLlO” and ”HELLO” are both valid, but different, methods).All valid requests in this assignment will use a method that uses eight (8) characters or fewer. Your httpserver will need to implement the semantics of GET, PUT, and APPEND, as explained below. • URI Valid requests will include a URI, a case-sensitive sequence of characters starting with the character ‘/’ and including additional characters within the range [a-z], [A-z], [0-9] and including the characters ‘.’ and ‘ ’, for a total of 64 characters in the alphabet of valid URIs. Each URI, /path, matches to the file path within the directory in which the httpserver is running.For example, the URI /foo.txt matches the file foo.txt from the folder in which the httpserver is running. All valid URIs in this assignment will contain a path with 19 characters or fewer. • Version Valid requests will include an HTTP version, of the form HTTP/#.# (where each # is a single digit number). Your httpserver only needs to support version 1.1, so HTTP/1.1 is the only version string upon which your server needs to perform GET, PUT, and APPEND operations. • Header-Field. Every valid request will include zero (0) or more header-fields after request-line. A header-field is key-value pair expressed in the form: key: valueThe key and value fields are delimited by the first instance of a ‘:’ character. Valid requests’ keys will be in ascii and not contain whitespace. Valid requests will separate each header-field using the sequence r , and will terminate the list of header-fields with a blank header terminating in r . (Essentially, the list of header-fields end with r r ). 2 I believe that there are more current RFCs for HTTP1.1, but we’ll be using 2616 for this assignment. 2 • Message-Body. Valid PUT and APPEND requests must include a message-body; valid GET requests will not include a message-body.Valid requests that include a Message-Body will also include a header, Content-Length, whose value will indicate the number of bytes in the Message-Body. As a summary, here is an example of a valid PUT request to the URI, foo.txt: PUT /foo.txt HTTP/1.1r Content-Length: 12r r Hello world! Responses Your httpserver must produce a response for each request. Your response must follow the grammar: Request = Status-Liner ; [Required] (Header-Fieldr )* ; [Optional, repeated] r Message-Body ;[Optional] • Status-Line The status line indicates the type of response to the request. It consists of three fields: HTTP-Version Status-Code Status-Phrase httpserver must always produce the HTTP-Version string, HTTP/1.1, regardless of the HTTP-Version provided in the request. A response with a Status-Code in the 200s indicates a successful response, in the 400s indicates an erroneous response, and in the 500s indicates an internal server error.The list of status-codes that httpserver needs to produce, and their associated status-phrase, are listed below. When returning a status-code listed below, the status-phrase field should have the corresponding value. We provide guidance on when to return each code in the sections on methods and errors. Status-Code Status-Phrase Message-Body Usage 200 OK OK When a method is Successful 201 Created Created When a URI’s file is created 400 Bad Request Bad Request When a request is ill-formatted 403 Forbidden Forbidden When the server cannot access the URI’s file 404 Not Found Not Found When the URI’s file does not 500 Internal Server Error Internal Server Error When an unexpected issue prevents processing 501 Not Implemented Not Implemented When a request includes an unimplemented Method • Header-Field.The status-line should be followed by zero (0) or more header-fields. A response’s header-fields have the same format as the request header fields, namely: key: value Responses that include a message-body must include a Content-Length header field. httpserver must separate each header-field using the sequence r and terminate the list of header-fields with a blank header terminating in r . (Essentially, the list of header-fields ends with r r ). • Message-Body. httpserver must produce a response with a message-body for each GET request.A message-body in a response must always be accompanied by a Content-Length header that indicates the number of bytes in the Message-Body. 3 Methods You must implement three HTTP methods, GET, PUT, and APPEND: • GET A GET request indicates that the client would like to receive the content of the file identified by the URI. For each valid GET request, httpserver must produce a response with a status-code of 200, a message-body that includes the current state of the file pointed to by URI, and a Content-Length that indicates the number of bytes in the file.• PUT A PUT request indicates that the client would like to update/replace the content of the file identified by the URI. If a valid PUT request’s URI points to a file that does not yet exist, httpserver must create the file, set the file’s contents equal to the message-body in the request, and produce a response with a status-code of 201. If a valid PUT request’s URI points to a file that does already exist, httpserver must replace the file’s contents with the message-body in the request and produce a response with a status-code of 200.• APPEND An APPEND request indicates that the client would like to append content to the end of the file identified by the URI. For each valid APPEND request, httpserver must add the content of the message-body to the end of the file pointed to by the URI and produce a response with a status-code of 200. Additional Functionality In addition to supporting the methods listed above, your project must do the following: • httpserver must work on binary message-bodys. • httpserver must produce error messages and return codes that are identical to those of the reference implementation; see the section below on errors. • httpserver should not have any memory leaks.• httpserver must be reasonably efficient. • Your code should be formatted according to the clang-format provided in your repository and it should compile using clang with the -Wall -Werror -Wextra -pedantic compiler flags. Limitations You must write httpserver using the C programming language. Your program cannot call the following functions from the C stdio.h library: fwrite, fread, fopen, fclose, variants of put (e.g., fptuc, putc, putc unlocked, putchar, putchar unlocked, and putw), and get (e.g., fgetc, fget, getc,getc unlocked, getchar, getchar unlocked, and getw).You cannot use functions, like system(3), that allow you to execute external programs. If your submission does not meet these minimum requirements, then the maximum score that you can get is 5%. Errors httpserver must never crash and should not produce output to standard out or standard error (the starter code validates and produces errors for the only input to httpserver). Your httpserver will only need to produce responses that contain a status-code listed in the table above. You can consult the reference implementation to identify the precise scenarios in which you should produce each status-code. The reference is located (in binary format, of course!) on Git@UCSC. Part of the assignment is enumerating as many errors as you can think of and figuring out when to produce the error messages! Hints Here are some hints to help you get going: 4• You will likely need to lookup how some system calls (e.g., read) and library functions (e.g., warn) work. You can always Google them, but you might also find the man pages useful (e.g., try typing man 2 read on a terminal). • There are a few ways to test httpserver. Below, we assume that you started httpserver on port 1234 by executing the command ./httpserver 1234. We also assume that you are using your client on the same machine upon which the server is currently executing: • You can use an HTTP Client, such as a web browser. We recommend testing with curl, a command-line HTTP client. curl can produce both GET and PUT commands. For example, to execute a GET of the file foo.txt on httpserver and place the output into the file download.txt, you execute: curl http://localhost:1234/foo.txt -o download.txt curl can execute PUT and GET commands; use help curl or man curl on a terminal to learn more. • You can also use nc (often called “netcat”).To connect to your server, execute nc localhost 1234. Then, you can type in the text that you wish to send to your server. You can also automate this approach by piping data to nc. For example, to send the PUT command listed above to your server, execute: printf “PUT /foo.txt HTTP/1.1r Content-Length: 12r r Hello World!” |nc localhost 1234 • If you try to start your server immediately after killing a previous instance of it, you will likely see the following error: httpserver: bind error: Address already in use In this case, just restart the server with a different port number.The issue is that the operating system must ensure unique ports are used across the entire system; it often waits to gracefully close ports even after the process that was using them terminates. Dazzle Points In addition to the functionality listed above, our reference implementation implements a number of extensions. These extensions fall into two categories (1) additional functionality and (2) supporting the robustness principle. You can earn Dazzle Points by implementing the optional features implemented in the reference implementation.To make this more fun (or, competitive), we will include a Dazzle Points Scoreboard on Dr. Q’s website at this link. To be included in the scoreboard, include a file scoreboard.txt in the asgn1 folder of your repository. The scoreboard.txt should include a single word, name, which we will use to display your Dazzle Points3 Grading Your submission will be graded using the following high-level rubric: • Functionality tests: 70% • README design doc: 15% • Coding style: 15% Starter Code Your starter code does three basic things for you:• Your starter code parses the command line argument provided by the client and ensures that it is in the correct format. 3Keep in mind, while this is anonymous to your peers, the name you choose to display is not anonymous to us. Trying to get Dr. Q to display profane or inappropriate things on his website is not a good strategy for success in this class. 5 • Your starter code creates a socket, binds that socket to the local interface, and then listens for requests on the socket. For each request, the starter code calls handle connection. • Your starter code includes a signal handler that ignores the SIGPIPE signal. This handler makes it so that socket failures will result linux setting errno to EPIPE rather than throwing a signal.
For this assignment, you will write a program, split, that takes a delimiter character and a list of files as input. The program “splits” each file into a set of lines by replacing each instance of a delimiter character into a new line character and prints the lines to stdout.To execute split, you specify: ./split … For example, to split a file foo into lines at each instance of the character, a, you would specify: ./split a foo If foo contains the character sequence, baabab, then the above command prints the following to stdout: b b b (your program should print the new line character, ‘ ’, rather than the sequence of characters followed by n).Submission details Your repository should create a binary, called split, when we run make in the asgn0 directory. split should implement the functionality listed below, subject to the limitations listed below. Additionally, your repository should also include a README.md file, which we will use in place of a design doc. You should include the interesting design decisions that you make and outline the high-level functions, data-structures, and modules that you used.You must submit a 40 character commit ID hash on Canvas in order for us to identify which commit you want us to grade. We will grade the last hash that you submit to the assignment on Canvas and will use the timestamp of your last upload to determine grace days and bonus points. For example, if you post a commit hash 36 hours after the deadline, we will subtract 2 grace days from your total.Your repository should include the following files: • split.c • Makefile • README.md Functionality You must implement the following behavior: • If – is given as a filename, then split should use standard input as the next input. That is, split a foo – specifies that split first splits foo and then splits standard input. You can assume that – will only be used once in the list of input files. • split should work for an arbitrary number of files • split must work on binary input files. 1 • split should produce the error messages and return codes that are identical to those of the reference implementation; see the section below on errors. • split should not have any memory leaks.• split must support any single-character delimiter. • split must be reasonably efficient. • Your code should be formatted according to the clang-format provided in your repository and it should compile using clang with the -Wall -Werror -Wextra -pedantic compiler flags. Limitations You must write split using the C programming language.Your program cannot call the following functions from the C stdio.h library: fwrite, fread, variants of put (i.e., fptuc, putc, putc unlocked, putchar, putchar unlocked, and putw), and get (i.e, fgetc, getc,getc unlocked, getchar, getchar unlocked, and getw). You cannot use functions, like system(3), that allow you to execute external programs. If your split does not meet these minimum requirements, then the maximum score that you can get is 5%. Errors Your version of split must produce the same error messages and return codes as the reference implementation.You can find the reference implementation (in binary format, of course!) on Git@UCSC. Part of the assignment is enumerating as many errors as you can think of and running them through the reference implementation to see what output you should produce! Hints Here are some hints to help you get going: • You will likely need to lookup how some system calls (e.g., read) and library functions (e.g., warn) work.You can always Google them, but you might also find the man pages useful (e.g., try typing man 2 read on a terminal). • You might find the warn function useful for producing error messages. • Think about how to make your program more efficient. Inefficient programs will lose points. • You can check the return code of a program by printing the value of $? on a terminal after you execute a program. For example, to see the code returned by split, you would run split a foo; echo $?. • To format a file, named foo, using the included clang-format, execute the command clang-format -i -style=file foo. Grading Your submission will be graded using the following high-level rubric: • Functionality tests: 70% • README design doc: 10% • Coding style: 20%
