In this workshop, you will work with classes that make up the hierarchical structure. The base or parent class will be a `MotorVehicle` that holds common attributes of a vehicle with an engine then the child class `Truck` will be derived from the parent class. In addition to this hierarchy, we will define custom input/output operators for these classes.## Learning OutcomesUpon successful completion of this workshop, you will have demonstrated the abilities to:– inherit a derived class from a base class – shadow a base class member function with a derived class member function – access a shadowed member function that is defined in a base class – utilize custom input/output operators with these classes – describe to your instructor what you have learned in completing this workshop## Submission PolicyThe workshop is divided into one coding part and one non-coding part:– Part 1 (**LAB**): A step-by-step guided workshop, worth 100% of the workshop’s total mark > Please note that the part 1 section is **not to be started in your first session of the week**. You should start it on your own before the day of your class and join the first session of the week to ask for help and correct your mistakes (if there are any). – Part 2 (reflection): non-coding part. The reflection doesn’t have marks associated with it but can incur a **penalty of max 40% of the whole workshop’s mark** if your professor deems it insufficient (you make your marks from the code, but you can lose some on the reflection).## Due Dates Part 1 (lab) is due 2 days after your lab day and Part 2 (Reflection) is due 2 days after your lab day.The Due dates depend on your section. Please choose the “-due” option of the submitter program to see the exact due date of your section:> Note that the submission usually opens by the end of Monday. “`bash ~profname.proflastname/submit 2??/wX/pY_sss -due “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]## Late penalties You are allowed to submit your work up to 2 days after the due date with a 50% penalty for each day. After that, the submission will be closed and the mark will be zero.## CitationEvery file that you submit must contain (as a comment) at the top: **your name**, **your Seneca email**, **Seneca Student ID** and the **date** when you completed the work.### For work that is done entirely by you (ONLY YOU)If the file contains only your work or the work provided to you by your professor, add the following message as a comment at the top of the file:> I have done all the coding by myself and only copied the code that my professor provided to complete my workshops and assignments.### For work that is done partially by you.If the file contains work that is not yours (you found it online or somebody provided it to you), **write exactly which part of the assignment is given to you as help, who gave it to you, or which source you received it from.** By doing this you will only lose the mark for the parts you got help for, and the person helping you will be clear of any wrongdoing.> – Add the citation to the file in which you have the borrowed code > – In the ‘reflect.txt` submission of part 2 (Reflection), add exactly what is added to which file and from where (or whom).> :warning: This [Submission Policy](#submission-policy) only applies to the workshops. All other assessments in this subject have their own submission policies.### If you have helped someone with your codeIf you have helped someone with your code. Let them know of these regulations and in your ‘reflect.txt’ of part 2 (Reflection), write exactly which part of your code was copied and who was the recipient of this code.By doing this you will be clear of any wrongdoing if the recipient of the code does not honour these regulations.## Compiling and Testing Your ProgramAll your code should be compiled using this command on `matrix`:“`bash g++ -Wall -std=c++11 -g -o ws file1.cpp file2.cpp … “`– `-Wall`: the compiler will report all warnings – `-std=c++11`: the code will be compiled using the C++11 standard – `-g`: the executable file will contain debugging symbols, allowing *valgrind* to create better reports – `-o ws`: the compiled application will be named `ws`After compiling and testing your code, run your program as follows to check for possible memory leaks (assuming your executable name is `ws`):“`bash valgrind –show-error-list=yes –leak-check=full –show-leak-kinds=all –track-origins=yes ws “`– `–show-error-list=yes`: show the list of detected errors – `–leak-check=full`: check for all types of memory problems – `–show-leak-kinds=all`: show all types of memory leaks identified (enabled by the previous flag) – `–track-origins=yes`: tracks the origin of uninitialized values (`g++` must use `-g` flag for compilation, so the information displayed here is meaningful).To check the output, use a program that can compare text files. Search online for such a program for your platform, or use *diff* available on `matrix`.> Note: All the code written in workshops and the project must be implemented in the **seneca** namespace, unless instructed otherwise.### Custom code submissionIf you have any additional custom code, (i.e. functions, classes etc) that you want to reuse in the workshop save them under a module called Utils (`Utils.cpp and Utils.h`) and submit them with your workshop using the instructions in the “[Submitting Utils Module](#submitting-utils-module)” section.# Part 1 – LAB (100%)## `MotorVehicle` ModuleDesign and code a class named `MotorVehicle` that holds information about a vehicle with an engine. Place your class definition in a header file named `MotorVehicle.h` and your function definitions in an implementation file named `MotorVehicle.cpp`.Include in your solution all of the statements necessary for your code to compile under a standard C++ compiler and within the `seneca` namespace.### `MotorVehicle` ClassDesign and code a class named `MotorVehicle` that holds information about a vehicle with an engine.#### `MotorVehicle` Private MembersThe class should be able to store the following data:– a license plate number as a statically allocated array of characters of size 9. – the address where the vehicle is at a given moment as a statically allocated array of characters of size 64. – the year when the vehicle was built.You can add any other private members in the class, as required by your design. #### `MotorVehicle` Public Members– a custom constructor that receives as parameters the license plate number and the year when the vehicle was built. Set the location of the vehicle at `Factory`. Assume all data is valid. – `void moveTo(const char* address)`: moves the vehicle to the new address if the new address is different from the current address. Prints to the screen the message “`txt |[LICENSE_PLATE]| |[CURRENT_ADDRESS] —> [NEW_ADDRESS]| “` where – the license plate is a field of 8 characters aligned to the right – current address is a field of 20 characters aligned to the right – new address is a field of 20 characters aligned to left– `ostream& write(ostream& os)`: a query that inserts into `os` the content of the object in the format “`txt | [YEAR] | [PLATE] | [ADDRESS] “` – `istream& read(istream& in)`: a mutator that reads from the stream `in` the data for the current object “`txt Built year: [USER TYPES HERE] License plate: [USER TYPES HERE] Current location: [USER TYPES HERE] “`#### Helper Functions– overload the insertion and extraction operators to insert a `MotorVehicle` into a stream and extract a `MotorVehicle` from a stream. These operators should call the `write`/`read` member functions in the class `MotorVehicle`.## `Truck` ModuleDesign and code a class named `Truck` that holds information about a motor vehicle that can carry cargo. Place your class definition in a header file named `Truck.h` and your function definitions in an implementation file named `Truck.cpp`.Include in your solution all of the statements necessary for your code to compile under a standard C++ compiler and within the `seneca` namespace.### `Truck` ClassDesign and code a class named `Truck` that holds information about a motor vehicle that can carry cargo. **This class should inherit from `MotorVehicle` class.**#### `Truck` Private MembersThe class should be able to store the following data (on top of data coming from the parent class):– a capacity in kilograms as a floating-point number in double precision; this is the maximum weight of the cargo the truck can carry. – the current cargo load (in kilograms) is a floating-point number in double precision; the load cannot exceed the capacity.You can add any other private members in the class, as required by your design. **Do not duplicate members from the base class!** #### `Truck` Public Members– a custom constructor that receives as parameters the license plate number, the year when the truck was built, the capacity of the truck and the current address. Call the constructor from the base class and pass the license number and year to it. Set the current cargo to 0 and move the truck to the address specified in the last parameter. – `bool addCargo(double cargo)`: a mutator that adds to the attribute that stores the current cargo load the weight specified as a parameter. **Do not exceed the capacity!** If the current load has been changed, return `true`, otherwise return `false`. – `bool unloadCargo()`: a mutator that unloads current cargo (sets the attribute to 0). If the current load has been changed, return `true`, otherwise, return `false`. – `ostream& write(ostream& os)`: a query that inserts into `os` the content of the object in the format “`txt | [YEAR] | [PLATE] | [ADDRESS] | [CURRENT_CARGO]/[CAPACITY] “` – `istream& read(istream& in)`: a mutator that reads from the stream `in` the data for the current object “`txt Built year: [USER TYPES HERE] License plate: [USER TYPES HERE] Current location: [USER TYPES HERE] Capacity: [USER TYPES HERE] Cargo: [USER TYPES HERE] “`#### Helper Functions– overload the insertion and extraction operators to insert a `Truck` into a stream and extract a `Truck` from a stream. These operators should call the `write`/`read` member functions in the class `Truck`.## `main` Module (supplied)**Do not modify this module!** Look at the code and make sure you understand it.[main.cpp](lab/main.cpp)### Correct output[correct_output.txt](lab/correct_output.txt)### Files to Submit “`text MotorVehicle.cpp MotorVehicle.h Truck.cpp Truck.h main.cpp “`### Submission Data Entry“`text 2020 abc-111 Toronto 2019 def-222 Montreal 2345 1234 “` ### Submission Process:Upload the files listed above to your `matrix` account. Compile and run your code using the `g++` compiler as shown in [Compiling and Testing Your Program](#compiling-and-testing-your-program) and make sure that everything works properly.Then, run the following command from your matrix account“`bash ~profname.proflastname/submit 2??/wX/pY_sss “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]and follow the instructions.#### Submitting Utils Module To have your custom Utils module compiled with your workshop and submitted, add a **u** to the part number of your workshop (i.e **u**p1 for part one and **u**p2 for part two) and issue the following submission command instead of the above: “`text ~profname.proflastname/submit 2??/wX/upY_sss “` See [Custom Code Submission](#custom-code-submission) section for more detail> :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty# Part 2: ReflectionStudy your final solutions for each deliverable of the workshop **and the most recent milestones of the project if applicable**, reread the related parts of the course notes, and make sure that you have understood the concepts covered by this workshop. **This should take no less than 30 minutes of your time and the result is suggested to be between 150 to 300 words in length.**Create a file named `reflect.txt` that contains your detailed description of the topics that you have learned in completing this workshop and **the project milestones if applicable** and mention any issues that caused you difficulty.### Reflection Submission Process:Upload `reflect.txt` to matrix containing the reflectionThen, run the following command from your matrix account“`bash ~profname.proflastname/submit 2??/wX/pY_sss “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]and follow the instructions.> :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty. act a penalty
In this workshop, you will implement classes with resources that follow [the rule of 3](https://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming)) to be safely copied and assigned.## Learning OutcomesUpon successful completion of this workshop, you will have demonstrated the abilities to:– define and create copy constructors – define and create copy assignment – Prevent copying and assignment in a class – Overload insertion operator so the class can be printed using ostream – Overload extraction operator so the class can be read using istream – Do simple file IO using ifstream and ofstream – use the C++ string class to extract an unknown number of characters from the input.## Submission PolicyThe workshop is divided into one coding part and one non-coding part:– Part 1 (**LAB**): A step-by-step guided workshop, worth 100% of the workshop’s total mark > Please note that the part 1 section is **not to be started in your first session of the week**. You should start it on your own before the day of your class and join the first session of the week to ask for help and correct your mistakes (if there are any). – Part 2 (reflection): non-coding part. The reflection doesn’t have marks associated with it but can incur a **penalty of max 40% of the whole workshop’s mark** if your professor deems it insufficient (you make your marks from the code, but you can lose some on the reflection).## Due Dates Part 1 (lab) is due 2 days after your lab day and Part 2 (Reflection) is due 2 days after your lab day.The Due dates depend on your section. Please choose the “-due” option of the submitter program to see the exact due date of your section:> Note that the submission usually opens by the end of Monday. “`bash ~profname.proflastname/submit 2??/wX/pY_sss -due “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]## Late penalties You are allowed to submit your work up to 2 days after the due date with a 50% penalty for each day. After that, the submission will be closed and the mark will be zero.## CitationEvery file that you submit must contain (as a comment) at the top: **your name**, **your Seneca email**, **Seneca Student ID** and the **date** when you completed the work.### For work that is done entirely by you (ONLY YOU)If the file contains only your work or the work provided to you by your professor, add the following message as a comment at the top of the file:> I have done all the coding by myself and only copied the code that my professor provided to complete my workshops and assignments.### For work that is done partially by you.If the file contains work that is not yours (you found it online or somebody provided it to you), **write exactly which part of the assignment is given to you as help, who gave it to you, or which source you received it from.** By doing this you will only lose the mark for the parts you got help for, and the person helping you will be clear of any wrongdoing.> – Add the citation to the file in which you have the borrowed code > – In the ‘reflect.txt` submission of part 2 (Reflection), add exactly what is added to which file and from where (or whom).> :warning: This [Submission Policy](#submission-policy) only applies to the workshops. All other assessments in this subject have their own submission policies.### If you have helped someone with your codeIf you have helped someone with your code. Let them know of these regulations and in your ‘reflect.txt’ of part 2 (Reflection), write exactly which part of your code was copied and who was the recipient of this code.By doing this you will be clear of any wrongdoing if the recipient of the code does not honour these regulations.## Compiling and Testing Your ProgramAll your code should be compiled using this command on `matrix`:“`bash g++ -Wall -std=c++11 -g -o ws file1.cpp file2.cpp … “`– `-Wall`: the compiler will report all warnings – `-std=c++11`: the code will be compiled using the C++11 standard – `-g`: the executable file will contain debugging symbols, allowing *valgrind* to create better reports – `-o ws`: the compiled application will be named `ws`After compiling and testing your code, run your program as follows to check for possible memory leaks (assuming your executable name is `ws`):“`bash valgrind –show-error-list=yes –leak-check=full –show-leak-kinds=all –track-origins=yes ws “`– `–show-error-list=yes`: show the list of detected errors – `–leak-check=full`: check for all types of memory problems – `–show-leak-kinds=all`: show all types of memory leaks identified (enabled by the previous flag) – `–track-origins=yes`: tracks the origin of uninitialized values (`g++` must use `-g` flag for compilation, so the information displayed here is meaningful).To check the output, use a program that can compare text files. Search online for such a program for your platform, or use *diff* available on `matrix`.> Note: All the code written in workshops and the project must be implemented in the **seneca** namespace, unless instructed otherwise.### Custom code submissionIf you have any additional custom code, (i.e. functions, classes etc) that you want to reuse in the workshop save them under a module called Utils (`Utils.cpp and Utils.h`) and submit them with your workshop using the instructions in the “[Submitting Utils Module](#submitting-utils-module)” section.# Part 1 – LAB (100%) TextFile moduleYour task for this part of the workshop is to complete the implementation of the **TextFile** module. This module attaches itself to a text file on the hard drive and loads the content of the text file into an array of **Line**s.This module is then capable of displaying the text file page by page on the screen or give the user program read-only access to the lines of the text file as an array of C-strings.A **Textfile** can be safely copied, and the copying will also result in the creation of a copy of the attached file on the hard drive.A **TextFile** can be safely assigned to another **TextFile**, and the assignment will also overwrite the contents of the target file on the hard drive with the content of the source file.Unlike all the other modules that you have created till now (containing the implementation of only one class), the **TextFile** module contains two classes; **Line** and **TextFile**.The **Line** class encapsulates a single line of a text file. The **TextFile** encapsulates a text file on the hard drive and it is a dynamic array of **Lines**. This means an instance of **Line** class should not be able to exist outside of a **TextFile** class.To enforce this, make the **Line** class fully private and make the **TextFile** class a friend of the **Line** class. Doing so, only within the scope of the **TextFile** class, a **Line** can be instantiated and accessed:“`C++ class TextFile; // forward declaration class Line{ // fully private, no public member …….. friend class TextFile; }; class TextFile{ public: ……. }; “`## The Line Class The **Line** class is fully private and should only be accessible by the **TextFile** class. “`C++ class Line { char* m_value; Line(); ~Line(); operator const char* ()const; Line& operator=(const char* lineContent); // incomplete…}; “` ### Attributes (Member variables) #### char* m_value holds the address of the dynamically allocated Cstring (to hold a line of the text file) ### Methods (Member functions) #### operator const char* ()const; Returns the address held in the **m_value** attribute. #### Operator=(const char*) overload Dynamically allocates memory in **m_value** and copies the Cstring pointed by **lineContent** into it. ### default constructor Initializes the **m_value** attribute to **nullptr**. ### destructor Makes sure all the allocated memory is freed.> Make sure **Line** can not be copied or assigned to another **Line**.## The TextFile Class “`C++ class TextFile { Line* m_textLines; char* m_filename; unsigned m_noOfLines; unsigned m_pageSize; void setFilename(const char* fname, bool isCopy = false); void setNoOfLines(); void loadText(); void saveAs(const char *fileName)const; void setEmpty(); public: TextFile(unsigned pageSize = 15); TextFile(const char* filename, unsigned pageSize = 15); TextFile(const TextFile&); TextFile& operator=(const TextFile&); ~TextFile(); std::ostream& view(std::ostream& ostr)const; std::istream& getFile(std::istream& istr); operator bool()const; unsigned lines()const; const char* name()const; const char* operator[](unsigned index)const; }; “` ### Attributes (Member variables) **TextFile** has four private member variables: “`C++ Line* m_textLines; “` A pointer to hold the dynamic array of **Lines**. This attribute should be initialized to **nullptr** “`C++ char* m_filename; “` A pointer to hold the dynamic Cstring holding the name of the file. This attribute should be initialized to **nullptr** “`C++ unsigned m_noOfLines; “` An unsigned integer to be set to the number of lines in the file. “`C++ unsigned m_pageSize; “` The page size is the number of lines that should be displayed on the screen before the display is paused. After these lines are displayed, the user must hit enter for the next page to appear. ### Private Methods (Member functions) #### setEmpty “`C++ void setEmpty(); “` deletes the **m_textLines** dynamic array and sets is to **nullptr** deletes the **m_filename** dynamic Cstring and sets is to **nullptr** sets **m_noOfLines** attribute to **zero**. #### setFilename “`C++ void setFilename(const char* fname, bool isCopy = false); “` If the isCopy argument is false, dynamically allocates a Cstring in **m_filename** and copies the content of the **fname** argument into it. If the isCopy argument is true, dynamically allocates a Cstring in **m_filename** and copies the content of the **fname** argument with a prefix of **”C_”** attached to it. “`C++ Example: setFilename(“abc.txt”); // sets the m_filename to “abc.txt” setFilename(“abc.txt”, true); // sets the m_filename to “C_abc.txt” “` #### setNoOfLines “`C++ void setNoOfLines(); “` Counts the number of lines in the file:Creates a local **ifstream** object to open the file with the name held in **m_filename**. Then it will read the file, character by character, and accumulates the number of newlines in the **m_noOfLines** attribute.In the end, it will increase **m_noOfLines** by one, just in case, the last line does not have a new line at the end.If the number of lines is zero, it will delete the m_filename and set it to nullptr. (Setting the TextFile to a safe empty state)#### loadText “`C++ void loadText(); “` Loads the text file **m_filename** into the dynamic array of Lines pointed by **m_textLines** : If the **m_filename** is null, this function does nothing.If the **m_filename** is not null (**TextFile** is not in a safe empty state ), **loadText()** will dynamically allocate an array of Lines pointed by **m_textLines** with the size kept in m_noOfLines. > *Make sure **m_textLine** is deleted before this to prevent memory leak*.Create a local instance of **ifstream** using the file name **m_filename** to read the lines of the text file.Since the length of each line is unknown, read the line using a local C++ string object and the **getline** **helper** function. (note: this is the **HELPER** **getline** function and not a method of istream).In a loop reads each line into the string object and then sets the **m_textLines** array elements to the values returned by the **c_str()** method of the string object until the reading fails (end of file reached).After all the lines are read, make sure to update the value of m_noOfline to the actual number of lines read (This covers the possibility of one extra empty line at the end of the file)#### saveAs “`C++ void saveAs(const char *fileName)const; “` Saves the content of the TextFile under a new name.Use a local ofstream object to open a new file using the name kept in the argument filename. Then loop through the elements of the m_textLines array and write them in the opened file adding a new line to the end of each line.### Constructors “`C++ TextFile(unsigned pageSize = 15); “` Creates an empty TextFile and initializes the m_pageSize attribute using the pageSize argument. “`C++ TextFile(const char* filename, unsigned pageSize = 15); “` Initializes the m_pageSize attribute using the pageSize argument and all the other attributes to nullptr and zero. Then if the filename is not null, it will set the filename, set the number of Lines and load the Text (using the corresponding private methods.) ### Rule of three implementations for classes with resource Implement The Copy Constructor, Copy assignment and destructor. #### Copy ConstructorInitializes the m_pageSize attribute using the m_pageSize of the incoming TextFile object and all the other attributes to nullptr and zero. If the incoming Text object is in a valid State, performs the following tasks to copy the textfile and the content safely:– Sets the file-name to the name of the incoming TextFile object (isCopy set to true) [See setFilename()](#setfilename) – Saves the content of the incoming TextFile under the file name of the current TextFile – set the number of lines – loads the Text#### Copy Assignment If the current and the incoming TextFiles are valid it will first delete the current text and then overwrites the current file and data by the content of the incoming TextFile.– deallocate the dynamic array of Text and sets the pointer to null – Saves the content of the incoming TextFile under the current filename – Sets the number of lines – loads the Text#### destructor Deletes all the dynamic data. ### public Methods #### lines() “`C++ unsigned lines()const; “` returns m_noOfLines; #### view() “`C++ std::ostream& view(std::ostream& ostr)const; “` Prints the filename and then the content of the file “m_pageSize” lines at a time.– print the file name – underline the file name with ‘=’ character – loops through the lines and print them one by line – pauses after printing “m_pageSize” lines and prompts the user “`Hit ENTER to continue…“` and waits for the user to press enter and repeats until all lines are printed.The function performs no action if the **TextFile** is in an empty state.This function receives and returns an instance of istream and uses the instance for printouts.#### getFile() “`C++ std::istream& getFile(std::istream& istr); “` Receives a filename from istr to set the file name of the TextFile. Then sets the number of lines and loads the Text. When done it will return the istr;#### index Operator Overload “`C++ const char* operator[](unsigned index)const; “` Returns the element in the m_textLine array corresponding to the index argument. If the TextFile is in an empty state, it will return null. If the index exceeds the size of the array it should loop back to the beginning.For example, if the number of lines is 10, the last index should be 9 and index 10 should return the first element and index 11 should return the second element.### Type conversion overloads: #### boolean cast “`C++ operator bool()const; “` Returns true if the TextFile is not in an empty state and returns false if it is. #### constant character pointer cast “`C++ const char* name()const; “` Returns the filename.### Insertion and extraction helper operator overloads To print and read on and from istream and ostream overload operator>: #### operator(istream& istr, TextFile& text); “` uses the getFile() method to get the file name from console and load the content from the file ### Tester program “`C++ /*********************************************************************** // Intro. to Object Oriented Programming // Workshop 6 // Version 1.0 // Description // professor’s tester program // // Revision History // ———————————————————– // Name Date Reason // ///////////////////////////////////////////////////////////////// ***********************************************************************/ #include #include #include #include “TextFile.h” using namespace seneca; using namespace std;void FirstTen(TextFile T); void Copy(const string& dest, const string& source); void Dump(const string& filename); int main() { TextFile Empty; TextFile BadFilename(“badFilename”); Copy(“echoes.txt”, “echoesOriginal.txt”); Copy(“seamus.txt”, “seamusOriginal.txt”); TextFile E; TextFile S(“seamus.txt”); cout > E; cout
In this workshop, you will implement different types of operator overload in a partially developed class.## Learning OutcomesUpon successful completion of this workshop, you will have demonstrated the abilities to:– define and create binary member operator – define and create a type conversion operator – define and create unary member operator – define and create helper binary operator between classes – define and create a helper operator between a primitive type and a class.## Submission PolicyThe workshop is divided into one coding part and one non-coding part:– Part 1 (**LAB**): A step-by-step guided workshop, worth 100% of the workshop’s total mark > Please note that the part 1 section is **not to be started in your first session of the week**. You should start it on your own before the day of your class and join the first session of the week to ask for help and correct your mistakes (if there are any). – Part 2 (reflection): non-coding part. The reflection doesn’t have marks associated with it but can incur a **penalty of max 40% of the whole workshop’s mark** if your professor deems it insufficient (you make your marks from the code, but you can lose some on the reflection).## Due Dates Part 1 (lab) is due 2 days after your lab day and Part 2 (Reflection) is due 2 days after your lab day.The Due dates depend on your section. Please choose the “-due” option of the submitter program to see the exact due date of your section:> Note that the submission usually opens by the end of Monday. “`bash ~profname.proflastname/submit 2??/wX/pY_sss -due “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]## Late penalties You are allowed to submit your work up to 2 days after the due date with a 50% penalty for each day. After that, the submission will be closed and the mark will be zero.## CitationEvery file that you submit must contain (as a comment) at the top: **your name**, **your Seneca email**, **Seneca Student ID** and the **date** when you completed the work.### For work that is done entirely by you (ONLY YOU)If the file contains only your work or the work provided to you by your professor, add the following message as a comment at the top of the file:> I have done all the coding by myself and only copied the code that my professor provided to complete my workshops and assignments.### For work that is done partially by you.If the file contains work that is not yours (you found it online or somebody provided it to you), **write exactly which part of the assignment is given to you as help, who gave it to you, or which source you received it from.** By doing this you will only lose the mark for the parts you got help for, and the person helping you will be clear of any wrongdoing.> – Add the citation to the file in which you have the borrowed code > – In the ‘reflect.txt` submission of part 2 (Reflection), add exactly what is added to which file and from where (or whom).> :warning: This [Submission Policy](#submission-policy) only applies to the workshops. All other assessments in this subject have their own submission policies.### If you have helped someone with your codeIf you have helped someone with your code. Let them know of these regulations and in your ‘reflect.txt’ of part 2 (Reflection), write exactly which part of your code was copied and who was the recipient of this code.By doing this you will be clear of any wrongdoing if the recipient of the code does not honour these regulations.## Compiling and Testing Your ProgramAll your code should be compiled using this command on `matrix`:“`bash g++ -Wall -std=c++11 -g -o ws file1.cpp file2.cpp … “`– `-Wall`: the compiler will report all warnings – `-std=c++11`: the code will be compiled using the C++11 standard – `-g`: the executable file will contain debugging symbols, allowing *valgrind* to create better reports – `-o ws`: the compiled application will be named `ws`After compiling and testing your code, run your program as follows to check for possible memory leaks (assuming your executable name is `ws`):“`bash valgrind –show-error-list=yes –leak-check=full –show-leak-kinds=all –track-origins=yes ws “`– `–show-error-list=yes`: show the list of detected errors – `–leak-check=full`: check for all types of memory problems – `–show-leak-kinds=all`: show all types of memory leaks identified (enabled by the previous flag) – `–track-origins=yes`: tracks the origin of uninitialized values (`g++` must use `-g` flag for compilation, so the information displayed here is meaningful).To check the output, use a program that can compare text files. Search online for such a program for your platform, or use *diff* available on `matrix`.> Note: All the code written in workshops and the project must be implemented in the **seneca** namespace, unless instructed otherwise.### Custom code submissionIf you have any additional custom code, (i.e. functions, classes etc) that you want to reuse in the workshop save them under a module called Utils (`Utils.cpp and Utils.h`) and submit them with your workshop using the instructions in the “[Submitting Utils Module](#submitting-utils-module)” section.# Part 1 – LAB (100%) The Account module.Your task for this part of the workshop is to complete the implementation of the **Account** module for holding a bank account number (an integer) and the balance of the account (a double value).# The Account class The Account class has two attributes; one integer for an account number (**m_number**) and a double for the balance of the account (**m_balance**)The **Account** class can be in three different states:* Invalid Empty State An account is in an **invalid** state if invalid information is fed into the account. In these types of situations the account number is set to **-1** and the balance is set to **0**. The Account object in this case is rendered inactive and can not be used anymore. * New An account is considered **New** or **not set** when it is just created and the account number is not assigned yet. This state of the **Account** class is flagged by setting the account number (**m_number**) to **0**. * Valid An **Account** is considered **valid** if the account number is a 5 digit integer with a zero or positive balance.## Already implemented parts: ## Constructors The **Account** can be created in two different ways: – default constructor *(implemented)* “`C++ Account(); “` The default constructor sets the account as **new** with a balance of **0**. – Two argument constructor (and integer and a double) *(implemented)* “`C++ Account(int number, double balance); “` The two-argument constructor sets the account number and balance to incoming arguments only if both values are valid. If an invalid account number or a negative balance is passed to the constructor, the object will be set into an invalid empty state.## display function. *(implemented)* “`C++ ostream& display() const “` Displays the account on the screen. If the account is invalid, it is going to print: **Bad Account**. If the account is a new account, instead of the account number it will print **New**. At the end **display** will return the **cout** object.## To be implemented: ### type conversion operators – **operator bool** returns **true** if the account is **valid** and otherwise **false**. This operator can not modify the **account** object. – **operator int** returns the **account number**. This operator can not modify the **account** object. – **operator double** returns the **balance value**. This operator can not modify the **account** object.### Unary member operator – **bool operator ~()** This operator returns **true** is the account is **new** or **not set** (i.e. if the **account number** is **zero**), otherwise it will return **false**. This operator can not modify the **account** object.### Binary member operators > Note: All the binary member operators **will not take any action** if the **account** is in an **invalid** state.#### assignment operators – overload the **assignment operator** so a **NEW account** can be set to an **integer**. Doing so should set the **account number** of the **account** to the **integer value**. If the **integer value** is an invalid account number, the object should be set to an **invalid empty state** instead. If the account is not new, then this operator should not perform any action. In any case, a reference of the **current object** (**account**) should be returned. “`C++ Account A,B; A = 55555; // the account number of A will be set to 55555 B = 555; // the account B will be set to invalid state B = 66666; // no action will be taken since the B is in not new A = 66666; // no action will be taken since the A is in not new “` – overload the **assignment operator** so a **NEW account** can be set to another **Account** object. This action should **move** the balance and the account number from one account to another; therefore unlike the usual assignment operator that affects the left operand only, this operator will affect both operands; the balance of the left account will be set to the balance of the right account and then the balance of the right account will be set to zero. The same will happen to the account number If the left Account operand is not new or the right account operand is not valid, no action should be taken. In any case, a reference of the **current object** (**account**) should be returned. “`C++ Account A, B(66666, 400), Bad(555, -10); A = B; // A will have the properties of B and B will become a NEW account B = Bad; // Nothing will happen since Bad is not new Bad = B; // Nothing will hapen since Bad is invalid “` – overload the **+= operator** to add a double value to an account. This should act like depositing money into an account. (i.e. the value of the double should be added to the balance) if the account is in an invalid state or the double value is negative, no action should be taken. In any case, a reference of the **current object** (**account**) should be returned. “`C++ Account A(55555, 400.0), Bad(555, -10); A += 200.0; // A will have a balance of 600 Bad += 300.0; // Nothing will happen since Bad is invalid A += -20.0; // Nothing will happen since double value is negative “` – overload the **-= operator** to reduce an account balance by a double value . This should act like withdrawing money from an account. (i.e. the value of the balance should be reduced by the double value) if the account is in an invalid state, the double value is negative or there is not enough money in the account no action should be taken. In any case, a reference of the **current object** (**account**) should be returned. “`C++ Account A(55555, 400.0), Bad(555, -10); A -= 150.0; // A will have a balance of 250 A -= 300.0; // Nothing will happen since there not enough money in A A -= -20.0; // Nothing will happen since double value is negative Bad -= 20.0 // Nothing will happen since Bad is invalid “`– overload the **> B; // Nothing will happen B >> Bad; // Nothing will happen Bad >> B; // Nothing will happen “`### Binary helper operators— create a binary stand alone helper **+ operator** that accepts a **constant account reference** at left and another **constant account reference** at right and returns a **double** value. The **double** value should be the **sum** of the **balances** of the two accounts. If any of the two accounts is **invalid**, then **zero** is returned. “`C++ Account A(55555, 400.0), B(66666, 600.0), Bad(555, -10); double sum; sum = A + B; // sum should be 1000.0 sum = A + Bad; // sum should be 0 since Bad is invalid sum = Bad + B; // sum should be 0 since Bad is invalid “` — create a binary stand alone helper **+= operator** that accepts a **double reference** at left and a **constant account reference** at right and returns a **double** value. The value of the balance of the right operand (account reference) should be added to the left operand (double reference) Then the value of the double reference is returned.“`C++ Account A(55555, 400.0), B(66666, 600.0), Bad(555, -10); double sum = 100, ret; ret = sum += A; // sum and ret should be 500.0 “`## The tester program.[main.cpp](lab/main.cpp)The tester program tests all the operator overloads and the output should be as follows:## Correct output[correct_output.txt](lab/correct_output.txt)## PART 1 Submission (part 1) ### Files to submit: “`Text Account.cpp Account.h main.cpp “`### Submission Process:Upload the files listed above to your `matrix` account. Compile and run your code using the `g++` compiler as shown in [Compiling and Testing Your Program](#compiling-and-testing-your-program) and make sure that everything works properly.Then, run the following command from your matrix account“`bash ~profname.proflastname/submit 2??/wX/pY_sss “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]and follow the instructions.#### Submitting Utils Module To have your custom Utils module compiled with your workshop and submitted, add a **u** to the part number of your workshop (i.e **u**p1 for part one and **u**p2 for part two) and issue the following submission command instead of the above: “`text ~profname.proflastname/submit 2??/wX/upY_sss “` See [Custom Code Submission](#custom-code-submission) section for more detail> :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty# Part 2: ReflectionStudy your final solutions for each deliverable of the workshop **and the most recent milestones of the project if applicable**, reread the related parts of the course notes, and make sure that you have understood the concepts covered by this workshop. **This should take no less than 30 minutes of your time and the result is suggested to be between 150 to 300 words in length.**Create a file named `reflect.txt` that contains your detailed description of the topics that you have learned in completing this workshop and **the project milestones if applicable** and mention any issues that caused you difficulty.### Reflection Submission Process:Upload `reflect.txt` to matrix containing the reflectionThen, run the following command from your matrix account“`bash ~profname.proflastname/submit 2??/wX/pY_sss “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]and follow the instructions.> :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty. act a penalty
In this workshop, you will use Constructors, a Destructor and a reference of the current object to simulate a Canister to hold liquid food products.## Learning OutcomesUpon successful completion of this workshop, you will have demonstrated the abilities to:– define a default constructor – define custom constructors with different number of arguments – define a Destructor to prevent memory leaks. – Use the reference of the current object – describe to your instructor what you have learned in completing this workshop## Submission PolicyThe workshop is divided into one coding part and one non-coding part:– Part 1 (**LAB**): A step-by-step guided workshop, worth 100% of the workshop’s total mark > Please note that the part 1 section is **not to be started in your first session of the week**. You should start it on your own before the day of your class and join the first session of the week to ask for help and correct your mistakes (if there are any). – Part 2 (reflection): non-coding part. The reflection doesn’t have marks associated with it but can incur a **penalty of max 40% of the whole workshop’s mark** if your professor deems it insufficient (you make your marks from the code, but you can lose some on the reflection).## Due Dates Part 1 (lab) is due 2 days after your lab day and Part 2 (Reflection) is due 6 days after your lab day.The Due dates depend on your section. Please choose the “-due” option of the submitter program to see the exact due date of your section:> Note that the submission usually opens by the end of Monday. “`bash ~profname.proflastname/submit 2??/wX/pY_sss -due “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]## Late penalties You are allowed to submit your work up to 2 days after the due date with a 30% penalty for each day. After that, the submission will be closed and the mark will be zero.## CitationEvery file that you submit must contain (as a comment) at the top: **your name**, **your Seneca email**, **Seneca Student ID** and the **date** when you completed the work.### For work that is done entirely by you (ONLY YOU)If the file contains only your work or the work provided to you by your professor, add the following message as a comment at the top of the file:> I have done all the coding by myself and only copied the code that my professor provided to complete my workshops and assignments.### For work that is done partially by you.If the file contains work that is not yours (you found it online or somebody provided it to you), **write exactly which part of the assignment is given to you as help, who gave it to you, or which source you received it from.** By doing this you will only lose the mark for the parts you got help for, and the person helping you will be clear of any wrongdoing.> – Add the citation to the file in which you have the borrowed code > – In the ‘reflect.txt` submission of part 2 (Reflection), add exactly what is added to which file and from where (or whom).> :warning: This [Submission Policy](#submission-policy) only applies to the workshops. All other assessments in this subject have their own submission policies.### If you have helped someone with your codeIf you have helped someone with your code. Let them know of these regulations and in your ‘reflect.txt’ of part 2 (Reflection), write exactly which part of your code was copied and who was the recipient of this code.By doing this you will be clear of any wrongdoing if the recipient of the code does not honour these regulations.## Compiling and Testing Your ProgramAll your code should be compiled using this command on `matrix`:“`bash g++ -Wall -std=c++11 -g -o ws file1.cpp file2.cpp … “`– `-Wall`: the compiler will report all warnings – `-std=c++11`: the code will be compiled using the C++11 standard – `-g`: the executable file will contain debugging symbols, allowing *valgrind* to create better reports – `-o ws`: the compiled application will be named `ws`After compiling and testing your code, run your program as follows to check for possible memory leaks (assuming your executable name is `ws`):“`bash valgrind –show-error-list=yes –leak-check=full –show-leak-kinds=all –track-origins=yes ws “`– `–show-error-list=yes`: show the list of detected errors – `–leak-check=full`: check for all types of memory problems – `–show-leak-kinds=all`: show all types of memory leaks identified (enabled by the previous flag) – `–track-origins=yes`: tracks the origin of uninitialized values (`g++` must use `-g` flag for compilation, so the information displayed here is meaningful).To check the output, use a program that can compare text files. Search online for such a program for your platform, or use *diff* available on `matrix`.> Note: All the code written in workshops and the project must be implemented in the **seneca** namespace, unless instructed otherwise.### Custom code submissionIf you have any additional custom code, (i.e. functions, classes etc) that you want to reuse in the workshop save them under a module called Utils (`Utils.cpp and Utils.h`) and submit them with your workshop using the instructions in the “[Submitting Utils Module](#submitting-utils-module)” section.# Part 1 – LAB (100%) The Canister ModuleYour task for this part of the workshop is to create a **Canister** module for holding liquid edible products.A **Canister** is a cylindrical container that is created using its height and its diameter and is labeled by the name of its content with an unknown length(i.e. Milk, Orange juice, etc…) that is dynamically held by a Canister. A Canister also holds the volume of the content it is holding making sure the liquid does not exceed its capacity. Any container that is filled higher than 0.267 centimetres from the top of the canister is considered unusable.The smallest Canister can have a height and diameter of 10.0 by 10.0 centimetres and the largest one can be 40 by 30 respectively.#### Calculating the capacity A Canister’s capacity (i.e. maximum amount of content it can hold) is calculated as follows: “`Text PI: 3.14159265 (a global constant double value created in Canister.cpp) H: Height D: Diameter Capacity = PI x (H – 0.267) x (D/2) x (D/2) “`The **Canister** can be created in three different ways; – By default a **Canister** is created with the following **height** and **diameter**: 13.0 x 10.0 with no name and content amount of 0 (empty) – Also a Canister can be created with its **content name**. In this case, the dimensions will be set to default values like the previous case and it will be empty. – Finally, a Canister can be created using its height, diameter and content name.> In any case, when a Canister is created using initial values and any of the values provided is invalid, the Canister is rendered unusable.#### Pouring contents of one canister into another You can fill the Canisters with the content they are labelled for. If too much is poured into the Canister, it will overflow and be rendered unusable.You can pour all or some of the content of one Canister into another. If this results in mixed content, the target will be rendered unusable.For example, if you can fill an empty orange juice Canister with the contents of a Canister holding Olive oil. Since the Orange juice Canister was empty everything will be OK and the Canister will be re-labelled as Olive oil. But if the orange juice canister has some orange juice in it, then it would have been rendered unusable.To reuse an unusable Canister it must be reset and cleared.You must design your code in a way that re-labelling and destruction of Canisters do not result in a memory leak. ## ImplementationCreate a class in a Module called Canister.### Private attributes (member variables)“`C++ char* m_contentName; // points to a dynamically allocated Cstring. double m_diameter; // in centimeters double m_height; // in centimeters double m_contentVolume; // in CCs bool m_usable; // a flag to identify if the Canister is usable or unusable “`### Private methods (member functions)“`C++ void setToDefault(); “` This function sets the attributes to their default values. It sets the content name pointer to null, height to 13.0, diameter to 10.0, content volume to 0.0 and usable flag to true.“`C++ bool isEmpty()const; “` Returns true if the content volume is less than 0.00001 CCs. “`C++ bool hasSameContent(const Canister& C)const; “` Compares the content name of this Canister with the one received from the argument **C**. Compare the two content names using strcmp from **** so that it returns true if both names are not null and are identical. Otherwise, it returns false; “`C++ void setName(const char* Cstr); “` Sets the content name of the current Canister. If the incoming **Cstr** is not null and the Canister is usable, it will delete the current content name, allocate memory to the length of Cstr (+1 for null) and copies the Cstr into the newly allocated memory. Otherwise, it will silently do nothing.### Constructors #### No argument Constructor (defualt) Sets the attributes to their default values #### One argument Constructor: “`C++ Canister(const char* contentName); “` – Sets the attributes to their default values (note: reuse code) – Sets the name to the incoming **contentName** argument. “`C++ Canister(double height, double diameter, const char* contentName); “` – Sets the attributes to their default values.If the dimensions are within acceptable values: – it will set the m_height and m_diameter to the corresponding argument values – it will set the content volume to 0. – it will set the content name to the corresponding argument value.If any of the dimensions have invalid values, it will set the Canister as **unusable**### The Destructor Deallocates the dynamic memory pointed by the content name attribute.### Public Methods (member variables) “`C++ void clear(); “` Clears an unusable Canister back to an empty Canister by: – deallocating the memory pointed by the content name attribute – sets the content name attribute to **nullptr** – sets the content volume attribute to 0.0 – set the usable flag attribute to true “`C++ double capacity()const; “` returns the capacity as stated in [Calculating the capacity](#calculating-the-capacity) “`C++ double volume()const; “` returns the content volume attribute “`C++ Canister& setContent(const char* contentName); “` It will set the Content name of the canister using the following rule and then returns the reference of the current object (i.e. *this):If the **contentName** argument is null it will render the Canister unusable else if the Canister is empty it will set the name to the value pointed by the argument else if the name of the Canister is not the same as the contentName argument it will render the Canister unusable. “`C++ Canister& pour(double quantity); “` Adds the **quantity** argument to the content volume of the Canister if the **quantity** fits in the Canister. Otherwise, it will render the Canister unusable and then returns the reference of the current object. Use this rule to accomplish the above: If the Canister is **usable** and the **quantity** is more than zero and if the sum of the quantity and the **volume()** is less than or equal to the **capacity()**, add the **quantity** to the content volume, otherwise set usable flag attribute to false. “`C++ Canister& pour(Canister& C); “` Pours the content of the Canister argument into the current Canister following the [Specs stated at the top](#pouring-contents-of-one-canister-into-another)Set the content name to the Canister argument using **setContent()**. if the **volume()** of the argument is greater than the **capacity()** minus the **volume()** Reduce the **content volume** of the argument by **capacity()** minus **volume()** and then set the content volume to **capacity()** else pour the **content volume** of the argument using **pour()** method and set the **content volume** of the argument to 0.0. return the reference of the current object at the end.“`C++ std::ostream& display()const; “` > Prints all the number values with one digit after the decimal point.Prints the Canister in the following format: “`Text In 7 spaces prints the capacity “cc (” height “x” diameter “) Canister” “` if unusable: “`Text ” of Unusable content, discard!” “` otherwise, if the content name is not null “`Text ” of ” in 7 spaces prints the volume “cc ” content name “` returns the cout object at the end.## Tester program:[main.cpp](lab/main.cpp)## Execution sample:[correct_output.txt](lab/correct_output.txt)## PART 1 Submission (part 1) ### Files to submit: “`Text Canister.cpp Canister.h main.cpp “`### Submission Process:Upload the files listed above to your `matrix` account. Compile and run your code using the `g++` compiler as shown in [Compiling and Testing Your Program](#compiling-and-testing-your-program) and make sure that everything works properly.Then, run the following command from your matrix account“`bash ~profname.proflastname/submit 2??/wX/pY_sss “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]and follow the instructions.#### Submitting Utils Module To have your custom Utils module compiled with your workshop and submitted, add a **u** to the part number of your workshop (i.e **u**p1 for part one and **u**p2 for part two) and issue the following submission command instead of the above: “`text ~profname.proflastname/submit 2??/wX/upY_sss “` See [Custom Code Submission](#custom-code-submission) section for more detail> :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty# Part 2: ReflectionStudy your final solutions for each deliverable of the workshop **and the most recent milestones of the project if applicable**, reread the related parts of the course notes, and make sure that you have understood the concepts covered by this workshop. **This should take no less than 30 minutes of your time and the result is suggested to be between 150 to 300 words in length.**Create a file named `reflect.txt` that contains your detailed description of the topics that you have learned in completing this workshop and **the project milestones if applicable** and mention any issues that caused you difficulty.### Reflection Submission Process:Upload `reflect.txt` to matrix containing the reflectionThen, run the following command from your matrix account“`bash ~profname.proflastname/submit 2??/wX/pY_sss “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]and follow the instructions.> :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty.
In this workshop, you will use member functions, privacy, safe empty state and formatting the output to complete your work.## Learning OutcomesUpon successful completion of this workshop, you will have demonstrated the abilities to:– to define a class type – to privatize data within the class type – to instantiate an object of class type – to access data within an object of class type through public member functions – to use standard library facilities to format data inserted into the output stream – to describe to your instructor what you have learned in completing this workshop## Submission PolicyThe workshop is divided into one coding part and one non-coding part:– Part 1 (**LAB**): A step-by-step guided workshop, worth 100% of the workshop’s total mark > Please note that the part 1 section is **not to be started in your first session of the week**. You should start it on your own before the day of your class and join the first session of the week to ask for help and correct your mistakes (if there are any). – Part 2 (reflection): non-coding part. The reflection doesn’t have marks associated with it but can incur a **penalty of max 40% of the whole workshop’s mark** if your professor deems it insufficient (you make your marks from the code, but you can lose some on the reflection).## Due Dates Part 1 (lab) is due 2 days after your lab day and Part 2 (Reflection) is due 4 days after your lab day.The Due dates depend on your section. Please choose the “-due” option of the submitter program to see the exact due date of your section:> Note that the submission usually opens by the end of Monday. “`bash ~profname.proflastname/submit 2??/wX/pY_sss -due “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]## Late penalties You are allowed to submit your work up to 2 days after the due date with a 30% penalty for each day. After that, the submission will be closed and the mark will be zero.## CitationEvery file that you submit must contain (as a comment) at the top: **your name**, **your Seneca email**, **Seneca Student ID** and the **date** when you completed the work.### For work that is done entirely by you (ONLY YOU)If the file contains only your work or the work provided to you by your professor, add the following message as a comment at the top of the file:> I have done all the coding by myself and only copied the code that my professor provided to complete my workshops and assignments.### For work that is done partially by you.If the file contains work that is not yours (you found it online or somebody provided it to you), **write exactly which part of the assignment is given to you as help, who gave it to you, or which source you received it from.** By doing this you will only lose the mark for the parts you got help for, and the person helping you will be clear of any wrongdoing.> – Add the citation to the file in which you have the borrowed code > – In the ‘reflect.txt` submission of part 2 (Reflection), add exactly what is added to which file and from where (or whom).> :warning: This [Submission Policy](#submission-policy) only applies to the workshops. All other assessments in this subject have their own submission policies.### If you have helped someone with your codeIf you have helped someone with your code. Let them know of these regulations and in your ‘reflect.txt’ of part 2 (Reflection), write exactly which part of your code was copied and who was the recipient of this code.By doing this you will be clear of any wrongdoing if the recipient of the code does not honour these regulations.## Compiling and Testing Your ProgramAll your code should be compiled using this command on `matrix`:“`bash g++ -Wall -std=c++11 -g -o ws file1.cpp file2.cpp … “`– `-Wall`: the compiler will report all warnings – `-std=c++11`: the code will be compiled using the C++11 standard – `-g`: the executable file will contain debugging symbols, allowing *valgrind* to create better reports – `-o ws`: the compiled application will be named `ws`After compiling and testing your code, run your program as follows to check for possible memory leaks (assuming your executable name is `ws`):“`bash valgrind –show-error-list=yes –leak-check=full –show-leak-kinds=all –track-origins=yes ws “`– `–show-error-list=yes`: show the list of detected errors – `–leak-check=full`: check for all types of memory problems – `–show-leak-kinds=all`: show all types of memory leaks identified (enabled by the previous flag) – `–track-origins=yes`: tracks the origin of uninitialized values (`g++` must use `-g` flag for compilation, so the information displayed here is meaningful).To check the output, use a program that can compare text files. Search online for such a program for your platform, or use *diff* available on `matrix`.> Note: All the code written in workshops and the project must be implemented in the **seneca** namespace, unless instructed otherwise.### Custom code submissionIf you have any additional custom code, (i.e. functions, classes etc) that you want to reuse in the workshop save them under a module called Utils (`Utils.cpp and Utils.h`) and submit them with your workshop using the instructions in the “[Submitting Utils Module](#submitting-utils-module)” section.# Part 1 – LAB (100%) Shopping Bill> Note: In this and future documents a **member function** may be referred to as a **method** and a **member variable** may be referred to as an **attribute**.Your task for this part of the workshop is to create a program that provides a class called **Bill**. This class can be initiated using a Title name and number of shopping **Item**s.Then the **Item**s will be added one at a time to the Bill by their name and the price and whether they are taxable or not.The **Bill** then can be displayed, listing all the items, their prices and whether each item is taxed or not. At the end of the list the total price, tax and total price after tax should be listed as follows:## Sample main program and execution sample[main.cpp](lab/main.cpp)## An example for a valid list: “`Text +————————————–+ | Quick Shopping | +———————-+———+—–+ | Item Name | Price + Tax | +———————-+———+—–+ | Milk 2%…………. | 4.99 | No | | Spatula…………. | 15.50 | Yes | | Frying Pan………. | 24.99 | Yes | | Eggs……………. | 5.99 | No | | Bug Spray……….. | 9.99 | Yes | +———————-+———+—–+ | Total Tax: 6.56 | | Total Price: 61.46 | | Total After Tax: 68.02 | +————————————–+ “` ## Examples of incomplete or lists with invalid items:“`Text +————————————–+ | Invalid Bill | +———————-+———+—–+ | Item Name | Price + Tax | +———————-+———+—–+ | Milk 2%…………. | 4.99 | No | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | +———————-+———+—–+ | Invalid Bill | +————————————–+ +————————————–+ | Invalid Bill | +———————-+———+—–+ | Item Name | Price + Tax | +———————-+———+—–+ | Milk 2%…………. | 4.99 | No | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | | Frying Pan………. | 24.99 | Yes | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | +———————-+———+—–+ | Invalid Bill | +————————————–+ “`## ImplementationImplement this program in two modules (ie. classes): **Item** and **Bill**### The Item Class Develop this class in files **Item.h** and **Item.cpp**#### Private Member Variables (attributes) The class subject should have the following member variables:“`C++ char m_itemName[21]; // holds the item name up to 20 chars double m_price; bool m_taxed; “` #### Private Member functions (Methods) “`C++ void setName(const char* name); “` This function sets the **itemName** member Cstring variable to a the Cstring in the **name** argument up to 20 characters.#### Public Member functions (Methods) “`C++ void setEmpty(); “` Sets the **Item** to a recognizable safe Empty State. Do this by setting the price to an impossible value like **0.0** and setting the **m_itemName** to a blank string (first character set to null).“`C++ void set(const char* name, double price, bool taxed); “` Sets the **m_itemName** attribute to the Cstring pointed by the **name** argument using the **setName** method and sets the **m_price** and **m_taxed** attributes to the corresponding arguments.If price is less than **0** or name is **null**, then the Item is set to a recognizable invalid **empty state** (safe empty state).“`C++ double price()const; “` Returns the **m_price** attribute;“`C++ double tax()const; “` Returns the product of m_price and 0.13(define a constant double value for this tax rate). Or it returns **0.0** if the m_taxed is false.“`C++ bool isValid()const; “` Returns true if the **Item** is not set to the empty state (As done in setEmpty function) . This function can not modify its owner.“`C++ void display()const; “` Prints an item in the following format. **If the Item is valid:** “`Text “| ” m_itemName; left-justified in 20 spaces, padded with ‘.’ (dots) ” | ” m_price; right-justified in 7 spaces with two digits after the decimal point ” | ” if m_taxed is true prints “Yes” otherwise prints “No ” ” |” Newline “` **If the Item is invalid** “`Text | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | Newline “`### The Bill Class#### Private Member Variables (attributes) The class **Bill** should have the following private member variables and functions:“`C++ char m_title[37]; // title of the shopping list Item* m_items; // pointer to the dynamically allocated array of Items int m_noOfItems; // size of the dynamically allocated array of Items int m_itemsAdded; // number of the Items added by the add method double totalTax()const; // returns the total tax applied to the Items double totalPrice()const; // returns the sum of prices of Items void Title()const; // Prints the title of the shopping list // prints the footer contaning total tax, price and total price after tax void footer()const; void setEmpty(); // sets the Bill to an emtpy state bool isValid()const; // returns true is the Bill and all of its Items are valid “`#### Private Member functions (Methods) “`C++ void setEmpty(); “` Sets the **Bill** object to an empty state by setting **m_title** to an Empty Cstring and **m_items** to **nullptr**“`C++ bool isValid()const; “` Returns true if **m_title** is not empty and **m_items** is not null and all the **Items** in the **m_items** array are valid.> hint: First check and make sure m_title and m_items are valid. Then loop through all the Items in the m_items array and make sure they are all valid.“`C++ double totalTax()const; “`Adds all the taxes of the items using a loop and returns the sum.“`C++ double totalPrice()const; “`Adds all the prices of the items using a loop and returns the sum;“`C++ void Title()const; “` Prints the title in the following format:Prints: “`”+————————————–+”“`**If the Bill is valid** “`Text “| ” m_title; left-justified in 36 spaces ” |” Newline “` **If the Bill is invalid** “` “| Invalid Bill |” “` Then in both cases (valid or invalid), it will print:“` “+———————-+———+—–+” “| Item Name | Price + Tax |” “+———————-+———+—–+” “`“`C++ void footer()const; “` Prints the footer in the following format:Prints: “`”+———————-+———+—–+”“`**If the Bill is valid** “`Text “| Total Tax: ” totalTax(); right justified in 10 spaces with two digits after the decimal point ” |” Newline “| Total Price: ” totalPrice(); right justified in 10 spaces with two digits after the decimal point ” |” Newline “| Total After Tax: ” totalTax()+totalPrice(); right justified in 10 spaces with two digits after the decimal point ” |” Newline “` **If the Bill is invalid** “` “| Invalid Bill |” “` Then in both cases (valid or invalid), it will print:“` “+————————————–+” “`#### Public Member functions (Methods)“`C++ void init(const char* title, int noOfItems); “`If any of the arguments are invalid, it will set the Bill to an empty state (ie. **title** is null or **noOfItems** is zero or less)Otherwise, if the incoming arguments are valid:– **init()** function will first set the **m_noOfItems** member variable to the incoming corresponding argument and sets **m_itemsAdded** to zero. – Next, it will copy the Cstring pointed by the **title** argument into **m_title** attribute up to 36 characters – Then it will dynamically allocate an array of **Item**s pointed by **m_items** member variable. The length of this array will be **m_noOfItems**. > Make sure all the dynamically allocated **Item**s are set to empty“`C++ bool add(const char* item_name, double price, bool taxed); “`If the number of added **Item**s (**m_itemsAdded**) is less than the length of the **m_items** array, this function will set the next available subject to the incoming argument values. Then it will add one to the **m_itemsAdded** and return true;Otherwise, this function will do nothing, returning false;“`C++ void display()const; “`This function will first print the **title()**, then it will loop through the **m_items** elements, printing every one of them, and finally prints the **footer()**. This function can not modify the Bill.“`C++ void deallocate(); “` Deallocates the **m_items** arrays and sets the pointers to null.## The tester program[main.cpp](lab/main.cpp) is the tester program that provides the following output[main_prof.cpp](lab/main_prof.cpp) is a comprehensive tester program that tests your program during submissiont.### The tester program output: “`Text +————————————–+ | Invalid Bill | +———————-+———+—–+ | Item Name | Price + Tax | +———————-+———+—–+ | Milk 2%…………. | 4.99 | No | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | +———————-+———+—–+ | Invalid Bill | +————————————–+ +————————————–+ | Invalid Bill | +———————-+———+—–+ | Item Name | Price + Tax | +———————-+———+—–+ | Milk 2%…………. | 4.99 | No | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | | Frying Pan………. | 24.99 | Yes | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | | xxxxxxxxxxxxxxxxxxxx | xxxxxxx | xxx | +———————-+———+—–+ | Invalid Bill | +————————————–+ +————————————–+ | Quick Shopping | +———————-+———+—–+ | Item Name | Price + Tax | +———————-+———+—–+ | Milk 2%…………. | 4.99 | No | | Spatula…………. | 15.50 | Yes | | Frying Pan………. | 24.99 | Yes | | Eggs……………. | 5.99 | No | | Bug Spray……….. | 9.99 | Yes | +———————-+———+—–+ | Total Tax: 6.56 | | Total Price: 61.46 | | Total After Tax: 68.02 | +————————————–+ “`### main_prof.cpp execution output[correct_output.txt](lab/correct_output.txt)## PART 1 Submission ### Files to submit “`Text main.cpp Item.cpp Item.h Bill.cpp Bill.h “` ### Submission Process:Upload the files listed above to your `matrix` account. Compile and run your code using the `g++` compiler as shown in [Compiling and Testing Your Program](#compiling-and-testing-your-program) and make sure that everything works properly.Then, run the following command from your matrix account“`bash ~profname.proflastname/submit 2??/wX/pY_sss “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]and follow the instructions.#### Submitting Utils Module To have your custom Utils module compiled with your workshop and submitted, add a **u** to the part number of your workshop (i.e **u**p1 for part one and **u**p2 for part two) and issue the following submission command instead of the above: “`text ~profname.proflastname/submit 2??/wX/upY_sss “` See [Custom Code Submission](#custom-code-submission) section for more detail> :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty# Part 2: ReflectionStudy your final solutions for each deliverable of the workshop **and the most recent milestones of the project if applicable**, reread the related parts of the course notes, and make sure that you have understood the concepts covered by this workshop. **This should take no less than 30 minutes of your time and the result is suggested to be between 150 to 300 words in length.**Create a file named `reflect.txt` that contains your detailed description of the topics that you have learned in completing this workshop and **the project milestones if applicable** and mention any issues that caused you difficulty.### Reflection Submission Process:Upload `reflect.txt` to matrix containing the reflectionThen, run the following command from your matrix account“`bash ~profname.proflastname/submit 2??/wX/pY_sss “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]and follow the instructions.> :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty.
In this workshop, you will use *references* to modify content of variables in other scopes, overload functions and allocate memory at run-time and deallocate that memory when it is no longer required.## Learning OutcomesUpon successful completion of this workshop, you will have demonstrated the abilities to:– allocate and deallocate dynamic memory for an array; – overload functions; – create and use references;## Submission PolicyThe workshop is divided into one coding part and one non-coding part:– Part 1 (**LAB**): A step-by-step guided workshop, worth 100% of the workshop’s total mark > Please note that the part 1 section is **not to be started in your first session of the week**. You should start it on your own before the day of your class and join the first session of the week to ask for help and correct your mistakes (if there are any). – Part 2 (reflection): non-coding part. The reflection doesn’t have marks associated with it but can incur a **penalty of max 40% of the whole workshop’s mark** if your professor deems it insufficient (you make your marks from the code, but you can lose some on the reflection).## Due Dates Part 1 (lab) is due 2 days after your lab day and Part 2 (Reflection) is due 4 days after your lab day.The Due dates depend on your section. Please choose the “-due” option of the submitter program to see the exact due date of your section:> Note that the submission usually opens by the end of Monday. “`bash ~profname.proflastname/submit 2??/wX/pY_sss -due “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]## Late penalties You are allowed to submit your work up to 2 days after the due date with a 50% penalty for each day. After that, the submission will be closed and the mark will be zero.## CitationEvery file that you submit must contain (as a comment) at the top: **your name**, **your Seneca email**, **Seneca Student ID** and the **date** when you completed the work.### For work that is done entirely by you (ONLY YOU)If the file contains only your work or the work provided to you by your professor, add the following message as a comment at the top of the file:> I have done all the coding by myself and only copied the code that my professor provided to complete my workshops and assignments.### For work that is done partially by you.If the file contains work that is not yours (you found it online or somebody provided it to you), **write exactly which part of the assignment is given to you as help, who gave it to you, or which source you received it from.** By doing this you will only lose the mark for the parts you got help for, and the person helping you will be clear of any wrongdoing.> – Add the citation to the file in which you have the borrowed code > – In the ‘reflect.txt` submission of part 2 (Reflection), add exactly what is added to which file and from where (or whom).> :warning: This [Submission Policy](#submission-policy) only applies to the workshops. All other assessments in this subject have their own submission policies.### If you have helped someone with your codeIf you have helped someone with your code. Let them know of these regulations and in your ‘reflect.txt’ of part 2 (Reflection), write exactly which part of your code was copied and who was the recipient of this code.By doing this you will be clear of any wrongdoing if the recipient of the code does not honour these regulations.## Compiling and Testing Your ProgramAll your code should be compiled using this command on `matrix`:“`bash g++ -Wall -std=c++11 -g -o ws file1.cpp file2.cpp … “`– `-Wall`: the compiler will report all warnings – `-std=c++11`: the code will be compiled using the C++11 standard – `-g`: the executable file will contain debugging symbols, allowing *valgrind* to create better reports – `-o ws`: the compiled application will be named `ws`After compiling and testing your code, run your program as follows to check for possible memory leaks (assuming your executable name is `ws`):“`bash valgrind –show-error-list=yes –leak-check=full –show-leak-kinds=all –track-origins=yes ws “`– `–show-error-list=yes`: show the list of detected errors – `–leak-check=full`: check for all types of memory problems – `–show-leak-kinds=all`: show all types of memory leaks identified (enabled by the previous flag) – `–track-origins=yes`: tracks the origin of uninitialized values (`g++` must use `-g` flag for compilation, so the information displayed here is meaningful).To check the output, use a program that can compare text files. Search online for such a program for your platform, or use *diff* available on `matrix`.> Note: All the code written in workshops and the project must be implemented in the **seneca** namespace, unless instructed otherwise.### Custom code submissionIf you have any additional custom code, (i.e. functions, classes etc) that you want to reuse in the workshop save them under a module called Utils (`Utils.cpp and Utils.h`) and submit them with your workshop using the instructions in the “[Submitting Utils Module](#submitting-utils-module)” section.# Part 1 – LAB (100%) Employees Salary Report***Employees Salary Report*** is a program that reads an unknown number of Employee records from a file and holds these records of Employees in a dynamically allocated array of **Employee**s. (Each record holds the Employee’s name, Employee number and Salary of the Employees in a comma separated value format.)After loading all the information into a dynamic array of **Employee**s, the program will sort the records based on the Employee number of the Employee in an ascending order and prints them on the screen.## Execution example[correct_output.txt](lab/correct_output.txt)This program is partially developed; you can find all the files in the lab directory. Your responsibility is to complete the code as stated in the comments in the source code.## The CodeThe structure holding the Employee record is designed as follows:“`C++ struct Employee { char* m_name; int m_empNo; double m_salary; }; “`In addition to holding the employee records in an dynamically allocated array of `Employee`s, each employee’s name is also held in a dynamically allocated C-style string in the **Employee** structure. Consider the following visual and note that every circle with an arrow in this diagram shows dynamic memory in use.## Data fileThe data in the file has the following format:“`Text EMPLOYEE NUMBER,SALARY,NAME “`and this is a sample file:“`Text 529967,80084.40,Abraham Simpson 737371,32943.14,Agnes Skinner 760089,55772.04,Akira Kurosawa 238023,15310.58,Alice Glick 463877,93971.86,Allison Taylor 836915,63415.69,Apu Nahasapeemapetilon 261382,44801.13,Artie Ziff 811518,90670.05,Baby Gerald 543817,54858.69,Barney Gumble 881837,47608.23,Bart Simpson 268411,27776.91,Bernice Hibbert 954291,51499.66,Brandine Spuckler 117493,43554.12,Bumblebee Man 928072,23678.38,Carl Carlson “`### The ModulesThere are three modules in the program: `File`, `Employee` and `salReport`.#### `File` ModuleThis modules contains functions that facilitate working with files to read data. The module has one global variable called `fptr`. This File pointer is used to point to the datafile for the application.The following functions are already implemented in the `File` module:– `openFile`: Opens the data file for reading – `closeFile`: Closes the data file – `noOfRecords`: Returns an integer that is the number of records in the file; use this function in the `Employee` module to determine the size of the dynamic array of employees. ***Your coding responsibility in the `File` module:***Implement 3 **overloads** of a function called `read`:1. `read`: accepts as a parameter the **address** of an array of characters. Reads from the file the name of the employee and stores it in the parameter.Returns `true` if the read was successful, `false` otherwise.Use the following `fscanf` function to read the name of the employee from the file and return true if `fscanf` returns 1. See more information [here](https://en.cppreference.com/w/cpp/io/c/fscanf).“`C fscanf(fptr, “%[^ ] ”…… “`2. `read`: accepts as a parameter a **reference** to an integer representing the employee number. Reads from the file the employee number and stores it in the parameter.Returns `true` if the read was successful, `false` otherwise.Use the following `fscanf` function to read the number from the file and return true if `fscanf` returns 1. See more information [here](https://en.cppreference.com/w/cpp/io/c/fscanf).“`C fscanf(fptr, “%d,”……. “`3. `read`: accepts as a parameter a **reference** to an floating point number in double precision representing the employee’s salary. Reads from the file the employee salary and stores it in the parameter.Returns `true` if the read was successful, `false` otherwise.Use the following `fscanf` function to read the salary from the file and return true if `fscanf` returns 1. See more information [here](https://en.cppreference.com/w/cpp/io/c/fscanf).“`C fscanf(fptr, “%lf,”,…… “`#### `Employee` ModuleThe `Employee` module has two global variables: “`cpp // Holds the number of records (employees) in the file. // Should be used (after setting) to allocate the dynamic array of Employees. int noOfEmployees;// Stores the address of a dynamically-allocated array of employees. // The size of the array is “noOfEmployees”. Employee* employees; “`The function `sort` has been already implemented. This function sorts the array of employees based on the employee number.***Your coding responsibility in the `Employee` module.***Implement following functions:– `load`: receives as parameter a reference to an object of type `Employee`, loads from the file the information about the employee and returns `true` if it was successful (`false` otherwise).– First it will read the employee number, then salary and finally in a **local** array of 128 characters, it will read the employee name from the file.– If all reads are successful: – find the actual length of the employee name using the `strlen` function in `` and then add one to the length (for null termination) – allocate the same amount of characters in the name of the `Employee` parameter – copy the read name (from the local character array) into the newly allocated name of the `Employee` parameter using `strcpy` function implemented ``. – store the employee number and salary read into the attributes of the parameter. – return `true`. – If at least one read failed, do not change the parameter and return `false`.– `load`: an overload of the `load` function that receives no parameters. This function should: – open the file (use function(s) from `File` module) – get the number of records (employees) from the file (use function(s) from `File` module) and store it into the global variable – create a dynamically allocated array of `Employee`; store its address into the global variable. – load each record from the file and store it into the array. – if everything is loaded correctly, return `true`. – if something goes wrong during data loading, display the following error message and return `false`. “`text Error: incorrect number of records read; the data is possibly corrupted. “`– `display`: receives as a parameter a constant reference to an Employee object and prints it in the following format: “`text NUMBER: NAME, SALARY “`– `display`: an overload of the `display` function that receives no parameters and returns nothing. This function should: – print to screen “`txt Employee Salary report, sorted by employee number no- Empno, Name, Salary ———————————————— “` – sort the array – iterate over the sorted array an print each employee in th format: “`txt IDX- NUMBER: NAME, SALARY “` – see [sample output](#part-1-execution-example) for more details.– `deallocateMemory`: deallocate **all** the memory used by the the dynamic array of employees (make sure to also deallocate the names). ### `main` Module.This module is already provided. Look at it, make sure you understand it, but do not change it.[main.cpp](lab/main.cpp)### Files to submit:“`Text main.cpp :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty # Part 2: ReflectionStudy your final solutions for each deliverable of the workshop **and the most recent milestones of the project if applicable**, reread the related parts of the course notes, and make sure that you have understood the concepts covered by this workshop. **This should take no less than 30 minutes of your time and the result is suggested to be between 150 to 300 words in length.**Create a file named `reflect.txt` that contains your detailed description of the topics that you have learned in completing this workshop and **the project milestones if applicable** and mention any issues that caused you difficulty.### Reflection Submission Process:Upload `reflect.txt` to matrix containing the reflectionThen, run the following command from your matrix account“`bash ~profname.proflastname/submit 2??/wX/pY_sss “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]and follow the instructions.> :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty.
In process of doing your first workshop, in part 1 section you are to sub-divide a program into modules, compile each module separately and construct an executable from the results of each compilation.## Learning OutcomesUpon successful completion of this workshop, you will have demonstrated the abilities to: – organize source code into modules, using header and implementation files; – compile and link modular programs; – distinguish the contents of a header and an implementation file; – describe to your instructor what you have learned in completing this workshop.## Submission PolicyThe workshop is divided into one coding part and one non-coding part:– Part 1 (**LAB**): A step-by-step guided workshop, worth 100% of the workshop’s total mark > Please note that the part 1 section is **not to be started in your first session of the week**. You should start it on your own before the day of your class and join the first session of the week to ask for help and correct your mistakes (if there are any). – Part 2 (reflection): non-coding part. The reflection doesn’t have marks associated with it but can incur a **penalty of max 40% of the whole workshop’s mark** if your professor deems it insufficient (you make your marks from the code, but you can lose some on the reflection).## Due Dates Part 1 (lab) is due 2 days after your lab day and Part 2 (Reflection) is due 6 days after your lab day.The Due dates depend on your section. Please choose the “-due” option of the submitter program to see the exact due date of your section:> Note that the submission usually opens by the end of Monday. “`bash ~profname.proflastname/submit 2??/wX/pY_sss -due “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]## Late penalties You are allowed to submit your work up to 2 days after the due date with a 30% penalty for each day. After that, the submission will be closed and the mark will be zero.## CitationEvery file that you submit must contain (as a comment) at the top: **your name**, **your Seneca email**, **Seneca Student ID** and the **date** when you completed the work.### For work that is done entirely by you (ONLY YOU)If the file contains only your work or the work provided to you by your professor, add the following message as a comment at the top of the file:> I have done all the coding by myself and only copied the code that my professor provided to complete my workshops and assignments.### For work that is done partially by you.If the file contains work that is not yours (you found it online or somebody provided it to you), **write exactly which part of the assignment is given to you as help, who gave it to you, or which source you received it from.** By doing this you will only lose the mark for the parts you got help for, and the person helping you will be clear of any wrongdoing.> – Add the citation to the file in which you have the borrowed code > – In the ‘reflect.txt` submission of part 2 (Reflection), add exactly what is added to which file and from where (or whom).> :warning: This [Submission Policy](#submission-policy) only applies to the workshops. All other assessments in this subject have their own submission policies.### If you have helped someone with your codeIf you have helped someone with your code. Let them know of these regulations and in your ‘reflect.txt’ of part 2 (Reflection), write exactly which part of your code was copied and who was the recipient of this code.By doing this you will be clear of any wrongdoing if the recipient of the code does not honour these regulations.## Compiling and Testing Your ProgramAll your code should be compiled using this command on `matrix`:“`bash g++ -Wall -std=c++11 -g -o ws file1.cpp file2.cpp … “`– `-Wall`: the compiler will report all warnings – `-std=c++11`: the code will be compiled using the C++11 standard – `-g`: the executable file will contain debugging symbols, allowing *valgrind* to create better reports – `-o ws`: the compiled application will be named `ws`After compiling and testing your code, run your program as follows to check for possible memory leaks (assuming your executable name is `ws`):“`bash valgrind –show-error-list=yes –leak-check=full –show-leak-kinds=all –track-origins=yes ws “`– `–show-error-list=yes`: show the list of detected errors – `–leak-check=full`: check for all types of memory problems – `–show-leak-kinds=all`: show all types of memory leaks identified (enabled by the previous flag) – `–track-origins=yes`: tracks the origin of uninitialized values (`g++` must use `-g` flag for compilation, so the information displayed here is meaningful).To check the output, use a program that can compare text files. Search online for such a program for your platform, or use *diff* available on `matrix`.> Note: All the code written in workshops and the project must be implemented in the **seneca** namespace, unless instructed otherwise.# Part 1 – LAB (100%)***Shopping List*** is a program that keeps track of your shopping list up to 15 items. You can add items to the list, remove and check the items you bought. Also, you can remove all the checked items and clear the list.Here is a sample execution of the program## LAB Execution example“`text –>>> My Shopping List > My Shopping List > My Shopping List > My Shopping List :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty# Part 2: ReflectionStudy your final solutions for each deliverable of the workshop **and the most recent milestones of the project if applicable**, reread the related parts of the course notes, and make sure that you have understood the concepts covered by this workshop. **This should take no less than 30 minutes of your time and the result is suggested to be between 150 to 300 words in length.**Create a file named `reflect.txt` that contains your detailed description of the topics that you have learned in completing this workshop and **the project milestones if applicable** and mention any issues that caused you difficulty.### Reflection Submission Process:Upload `reflect.txt` to matrix containing the reflectionThen, run the following command from your matrix account“`bash ~profname.proflastname/submit 2??/wX/pY_sss “` – Replace **??** with your subject code (`00 or 44`) – Replace **X** with Workshop number: [`1 to 10`] – Replace **Y** with the part number: [`1 or 2`] – Replace **sss** with the section: [`naa, nbb, nra, zaa, etc…`]and follow the instructions.> :warning:**Important:** Please note that a successful submission does not guarantee full credit for this workshop. If the professor is not satisfied with your implementation, your professor may ask you to resubmit. Re-submissions will attract a penalty.
1. Consider a distributed system of four processes as shown in Figure 1. The system is synchronous, and the minimum and maximum network delays (in seconds) between each pair of processes are shown in the figure as [min, max] against each channel. Assume no messages are lost on the channel, and the processing time at each process is negligible compared to network delays. a b c d [3,11] [4,15] [6,8] [3,13] [2,4] [12,18] Figure 1: Figure for question 1.(a) (3 points) Consider an all-to-all heartbeat protocol, where each process sends a heartbeat to each other process periodically every T=50s, and each process sets a timeout (computed appropriately from the known bounds on network delay) to detect failure of other processes. Suppose that process a crashes. For every other process, calculate how long it will take to detect a’s failure, in the worst case.(b) (3 points) Now consider a small extension of the protocol in in Q1(a) – as soon as a process detects that another process p has crashed via a timeout, it sends a notification to all other processes about p’s failure. Suppose that process a is the only process that crashes. For every other process, calculate how long it will take to detect a’s failure, in the worst case.(c) (2 points) If it is known that at most two processes may crash within a few hours of each other, how would you redesign the heartbeat protocol described in Q1(a) to minimize bandwidth usage, without increasing the worst case time taken to detect the failure of a process by at least one alive process. [Hint: do we really need all-to-all heartbeats?](d) (2 points) Assuming the modification in Q1(c), list the minimal set of processes a must send heartbeats to, so as to minimize the worst case time taken to detect failure of a by at least one alive process. client s3 s2 s1 RTT = 36ms RTT = 60ms RTT = 24ms Figure 2: Figure for question 2(a).2. (a) (4 points) Consider Figure 2. The client has an option of using any of the three authoritative sources of real time (s1, s2, or s3) for external synchronization via Cristian algorithm. The roundtrip times (RTT) between the client and the three servers are shown in the figure. Assume that the observed RTT to each server remains constant across all synchronization attempts.(i) Which server should the client choose to achieve the lowest accuracy bound right after synchronization? What is the value of this bound, as estimated by the client right after synchronization? [1 point](ii) If the client’s local clock drifts at the rate of 3µs every second, what is the smallest frequency (or the longest time-period) at which the client must initiate synchronization with the server it chose in part (i), so as to maintain an accuracy bound within 90ms at all times. [3 points] 12 39 46 30 32 65 71 52 60 90 93 75 A B Figure 3: Figure for question 2(b).(b) (6 points) Consider the series of message exchanged between two servers A and B as shown in Figure 3. The local timestamps at the servers when sending and receiving each message are shown in the figure.(i) Assume symmetric mode synchronization, where the send and receive timestamps for each message are recorded by both servers. Given A’s knowledge of the send and receive timestamps for all six messages, what is the lowest synchronization bound (as estimated by A) with which A can compute its offset relative to B? What is the corresponding estimated offset value? [Hint: A may use any pair of messages exchanged between the two servers, and not just two consecutive messages to compute offsets.] (4 points)(ii) Now assume that A uses the same series of messages for synchronization via Cristian algorithm: messages sent from A to B are requests, and messages from B to A are responses carrying the timestamp when B received the last request. What is the tightest synchronization bound (as estimated by A) with which A can compute its offset relative to B? (2 points)0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 P1 P2 P3 P4 A B C D E F G H I J K L M N O P Figure 4: Timeline for questions 3 and 4.3. The timeline in Figure 4 shows 16 events (A to P) across four processes. The numbers below indicate real time. (a) (2 points) Write down the Lamport timestamp of each event. (b) (4 points) Write down the vector timestamp of each event. (c) (4 points) List all events considered concurrent with: (i) A, (ii) F, (iii) K, and (iv) N.4. (a) (4 points) Consider the timeline and events in Figure 4 again. Suppose that P2 initiates the Chandy-Lamport snapshot algorithm at (real) time 8. Assuming FIFO channels, write down all possible consistent cuts that the resulting snapshot could capture. You can describe each cut by its frontier events.(b) (6 points) Write all possible states of the incoming channels at P1 and at P3 that the above snapshot could record. You can denote each message by its send and receive event ids.P1 P2 A B C D E F H I J Figure 1: for question 1 1. (a) (4 points) Consider the timeline of events {A,B,…J} across two processes as shown in Figure 1. List all possible linearizations for this system that includes each event.(b) (5 points) What is the total number of consistent global states that can be possibly captured for the above system? Identify each of them by the frontier events of the corresponding cuts. (c) (1 point) Provide an example of an unstable global safety property (which results in unstable nonsafety). How can it be made stable? (This is unrelated to 1(a) and 1(b).) P2 P1 P3 P4 Figure 2: for question 2(a)2. (a) (6 points) In the execution in Figure 2, processes send messages to each other to implement FIFO ordered multicast. To simplify the picture, messages sent by each process to itself are not shown, but assume that such messages are received and delivered instantaneously. For the questions below, you may use printed or hand-drawn figure with hand-drawn responses, or digitally edit the figure from the homework PDF.(i) Identify the messages that are buffered at the processes to ensure FIFO multicast delivery. (Circle the receive event for the buffered messages to identify those messages.) (3 points)(ii) For each message buffered as above, determine the earliest instant of time at which the message may be delivered, while ensuring FIFO multicast. (To identify the instant of time draw an arrow that begins at the time when the message is received to the time at which the message may be delivered.) (3 points) P2 P1 P3 P4 Figure 3: for question 2(b)(b) (6 points) In the execution in Figure 3, processes send messages to each other to implement causal multicast. To simplify the picture, messages sent by each process to itself are not shown, but assume that such messages are received and delivered instantaneously. For the questions below, you may use printed or hand-drawn figure with hand-drawn responses, or digitally edit the figure from the homework PDF.(i) Identify the messages that are buffered at the processes to ensure causally-ordered multicast delivery (Circle the receive event for the buffered messages to identify those messages.) (3 points)(ii) For each message buffered as above, determine the earliest instant of time at which the message may be delivered, while ensuring causally-ordered multicast. (To identify the instant of time draw an arrow that begins at the time when the message is received to the time at which the message may be delivered.) (3 points)3. For each of the statements below, identify whether it is true or false. If it is false, present a counterexample. If it is true, prove why. (a) (2 points) A total ordered multicast is also causal.(b) (3 points) If the processes in a system use R-multicast, and each channel follows FIFO order, then causal ordering is satisfied. (c) (3 points) We can implement the ISIS algorithm for total ordering on top of (or using) causalordered multicast, to achieve a total causal multicast.Process ID Time when “enter” is called (since start of system) Time spent in critical section after “enter” returns, before calling “exit”. P1 250ms 50ms P2 30ms 50ms P3 100ms 30ms P4 20ms 60ms P5 15ms 20ms Table 1: Timings for Q44. Consider a distributed system of five processes {P1, P2, P3, P4, P5}. Each process needs mutually exclusive access to a critical section. Table 1 lists the time when each process first makes a blocking call to “enter” the critical section (since the start of the system). It also lists the time each process spends in the critical section after “enter” succeeds, before calling “exit”.(a) (5 points) Suppose the system uses the central server algorithm for mutual exclusion, electing P4 as the leader. Assume that message latency at P4 for communicating with the leader (itself) is zero, i.e. it takes negligible time for P4’s token request to reach the leader upon calling enter, to receive the token after its request has been granted, and for the token to be released back to the leader upon calling exit. For all other processes, assume the one-way network latency for communicating with the leader (P4) is fixed at 10ms, i.e. it takes 10ms each for the token request to reach P4 after calling “enter”, 10ms for the token to reach the process after the leader has granted the request, and 10ms for the token to reach the leader after the process has called “exit”. The leader grants requests in the order in which it receives them. When will each process start executing its critical section?(b) (5 points) Now suppose that the system uses ring-based algorithm for mutual exclusion, with the ring structured as shown below (P1 to P2 to P3 to P4 to P5 to P1). Figure 4 At time 0ms (when the system starts up), the token is at P1. The network latency for passing the token from a given process to its ring successor is fixed at 10ms. When will each process start executing its critical section?Figure 1 shows three process P1, P2, and P3 (with ids 1, 2, and 3 respectively) implementing the RicartAgrawala (RA) algorithm for mutual exclusion. The lines indicate requests for accessing the critical section (CS) made by each process – blue, green, and red requests are from P1, P2, and P3 respectively. Other than the replies to CS requests (not shown in the figure), no other messages are exchanged between the processes. The timeline indicates real time. Assume that any reply sent for a CS request reaches the requesting process after exactly one (real) time unit. Further assume that any process that enters the CS, spends 3 (real) time units in it.(a) (2 points) What is P1’s state as per the RA algorithm when it receives CS request from P2 – Held, Wanted, or neither (Free)? How will P1 handle P2’s request upon receiving it – will it immediately send back a reply or will it queue the request? Why? (b) (2 points) What is P3’s state as per the RA algorithm when it receives CS request from P2 – Held, Wanted, or neither (Free)? How will P3 handle P2’s request upon receiving it – will it immediately send back a reply or will it queue the request? Why?(c) (2 points) What is P2’s state as per the RA algorithm when it receives CS request from P1 – Held, Wanted, or neither (Free)? How will P2 handle P1’s request upon receiving it – will it immediately send back a reply or will it queue the request? Why?(d) (2 points) What is P3’s state as per the RA algorithm when it receives CS request from P1 – Held, Wanted, or neither (Free)? How will P3 handle P1’s request upon receiving it – will it immediately send back a reply or will it queue the request? Why?(e) (2 points) What is P2’s state as per the RA algorithm when it receives CS request from P3 – Held, Wanted, or neither (Free)? How will P2 handle P3’s request upon receiving it – will it immediately send back a reply or will it queue the request? Why?Consider the following modification of the Bully algorithm: The initiating node (which we assume does not fail) sends an Election message only to the process with the highest id. If it does not get a response after a timeout, it then sends an Election message to the process with the second highest id. If after another timeout it gets no response, it tries the third highest id, and so on. If no higher numbered processes respond, it sends a Coordinator message to all lower-numbered processes.(a) (1 point) What should a process do when it receives an Election message in order to minimize turnaround time? For the following parts, consider a distributed system of 8 processes {P1, P2, . . . P8}. P8 has the highest id, followed by P7, then P6, and so on. The system uses the modified Bully algorithm for leader election (including the solution for 2a). Initially, all 8 processes are alive and P8 is the leader. Then P8 fails, P3 detects this, and initiates the election. P3 knows that P8 has failed and P7 has the highest id among the remaining processes. Assume one-way message transmission time is T, and timeout is set using the knowledge of T.(b) (1 point) If no other node fails during the election run, how many total messages will be sent by all processes in this election run? (c) (1 point) If no other node fails during the election run, how long will it take for the election to finish?(d) (1 point) Now assume that right after P3 detects P8’s failure and initiates the election, P7 fails. How many total messages will be sent by all processes in this election run? (e) (1 point) For the above scenario (where P7 fails right after P3 initiates election upon detecting P8’s failure), how long will it take for the election to finish?(5 points) Consider a system of N process that are arranged in a ring, with each process having a ring successor and a predecessor, and a communication channel only to its ring successor. Each process Pi has a unique id i. Further, each process Pi maintains a value xi (which may not be unique across processes). A process may not know the total number of other processes in the ring. Each process Pi is required to set the value of an output variable yi (initialized to undecided) to minN j=1(xj ). The safety condition for the problem requires that, at any point in time, the variable yi at process Pi ∀i ∈ [1, N] is either undecided or minN j=1(xj ).A distributed algorithm designed for the above problem works as follows: • A process Pi initiates the algorithm by sending (propose, xi) to its ring successor. • When a process Pj receives (propose, x) from its ring predecessor: – if x < xj , it forwards (propose, x) to its successor. – if x > xj , it sends (propose, xj ) to its successor. – if x = xj , it concludes that x = xj is the minimum value, and sends (decided, x) to its successor.• When a process Pj receives (decided, x), it sets yj = x and forwards (decided, x) to its successor (if it had not already done so in the past). Once Pj sets yj , it ignores any subsequently received decided messages. Multiple processes may initiate the above algorithm simultaneously. Assume no process fails and the communication channel delivers all messages correctly and exactly once. Does the algorithm described above guarantee safety condition for the problem? If yes, prove how. If not, (i) describe a scenario where safety is violated, and (ii) suggest modifications to the algorithm that would guarantee the safety condition.Consider a system of five processes [P1, P2, P3, P4, P5]. Each process Pi proposes a value xi . Let x1 = 6, x2 = 5, x3 = 8, x4 = 2, and x5 = 10. Each process Pk must decide on an output variable yk (initialized to undecided), setting it to one of the proposed values xi for i ∈ [1, 5]. The safety condition requires that at any point in time, for any two processes Pj and Pk, either yj or yk is undecided, or yj = yk (in other words, the decided value must be same across all processes that have decided).A consensus algorithm is designed for the above problem that works as follows: • Each process R-multicasts its proposed value at the same time t = 0ms since start of the system (as per their local clocks). • As soon as proposed values from all 5 processes are delivered at a process Pj , Pj sets yj to the minimum of the proposed values it received from the five processes.• If yj is still undecided at time (t + timeout), Pj computes the minimum of the proposed values it has received so far and sets yj to that value. • Once a process Pj decides on yj , it does not update yj ’s value, and ignores future proposals (if any are received). Assume that all clocks are perfectly synchronized with zero skew with respect to one-another. The proposed value xi of a process Pi gets self-delivered immediately at time t = 0ms when Pi begins the multicast of xi . A message sent from a process to any other process takes exactly T = 10ms (and this value is known to all processes). All communication channels are reliable. Processes may fail, but a failed process never restarts.Suppose the timeout value for the above algorithm is set to 25ms. Answer the following questions with respect to local time at the processes’ clock since the start of the system. (a) (2 points) Assume no process fails in the system. When will each process decide on a value and what will each of their decided values be? (b) (2 points) Assume P4 fails right after unicasting x4 to P3 and P5 but just before it could initiate the unicast of x4 to any of the other processes. When will each of the alive processes decide on a value and what will each of their decided values be?(c) (2 points) Assume P4 fails at right after unicasting x4 to P3 but just before it could initiate the unicast of x4 to any of the other processes. P3 fails right after it has relayed x4 to P5 but just before it unicasts it to any other process. When will each of the alive processes decide on a value and what will each of their decided values be?(d) (2 points) Assume P4 fails right after unicasting x4 to P3 but just before it could initiate the unicast of x4 to any of the other processes. P3 fails right after it has relayed x4 to P5 but just before it unicasts it to any other process. P2 fails right before it could unicast x2 to any process. When will each of the remaining alive processes decide on a value and what will each of their decided values be?(e) (2 points) What is the smallest value that the timeout should be set to for ensuring safety in this system? (f) (1 point) Answer Q4c assuming that the timeout is updated to the value in Q4e. (g) (1 point) Answer Q4d assuming that the timeout is updated to the value in Q4e.Consider a system of five processes that implement the Paxos algorithm for consensus. As shown in Figure 2, P1 and P2 are proposers. P3, P4, P5 are acceptors. P1 sends a prepare message with proposal number 2 to processes P4 and P5, receives their replies, and sends an accept message with proposed value of 10 for proposal #2. P2 concurrently sends a prepare message with proposal #5, with an initial intention to propose a value of 15 if it receives sufficient replies. Only a subset of responses from processes P4, and P5 are shown in the figure. Assume no other proposals are initiated.Answer the following sub-questions. 0 1 2 3 4 5 6 7 8 9 10 11 12 P1 P2 P3 P4 P5 Prepare #2 13 14 15 16 17 18 Accept #2 Proposed value = 10 Prepare #5 Acceptors Proposers Figure 2: Figure for question 5(f) (a) (1 point) Which processes will accept P1’s proposal? (b) (1 point) Which processes will reply back to P2’s prepare message? (c) (2 points) Will P2 send out an accept message for its proposal #5? If yes, what will be the corresponding proposed value?(d) (2 points) Consider the state of the system at time 10 units. Has the proposed value 10 been implicitly decided upon at this point? If yes, explain why? If not, construct a possible scenario that may occur after time 10 units where the system ends up deciding on a different proposed value. The scenario would involve a temporal sequence of events that may differ from the one shown in the figure beyond time t=10units but must comply with what is shown until t=10units. An event in such a sequence may include a prepare/accept request sent by a proposer or received by an acceptor, or a prepare reply received by the proposer at some time unit.(e) (1 point) Suppose that P1’s accept request reaches P5 at time 8 units (instead of 14 units). If we now consider the state of the system at time 10 units, has the proposed value 10 been implicitly decided upon?(f) (1 point) Suppose that P1’s accept request reaches P4 at time 15 units (instead of 9 unit) and reaches P5 at the original time 14 units. Will P2 send out an accept message for its proposal #5? If yes, what will be the corresponding proposed value?1. Consider a system of 5 processes {P1, P2, P3, P4, P5} using Raft’s algorithm for leader election. Suppose P1, the leader for term 1, fails and its four followers receive its last heartbeat at exactly the same time. Answer the following questions assuming that the election timeout is chosen uniformly at random from the range [100,500] ms (unless otherwise specified), no processing delay exists, and the one-way delay for all messages between two processes are as shown in Figure 1. The processes communicate with oneanother only through their direct channels (not via other processes). Each question below is independent of others. P2 P3 P5 P4 25ms 10ms 30ms 15ms 5ms 20ms Figure 1: Figure for question 1(a) (2 points) Suppose P2 and P3 both set their election timeout to 150 ms and call an election for term 2. Assume P4 and P5 have their timeout values set to more than 400 ms. Which candidate (P2 or P3) will each of the four alive processes vote for? Will a leader be elected for term 2? If yes, which process?(b) (2 points) Suppose P2 sets its election timeout to 150 ms and calls an election for term 2, and P3 sets its timeout to 170 ms and also calls an election for term 2. Assume P4 and P5 have their timeout values set to more than 400 ms. Which candidate (P2 or P3) will each of the four alive processes vote for? Will a leader be elected for term 2? If yes, which process?(c) (6 points) Suppose P2 sets its election timeout to 150 ms and calls for an election for term 2. Assume P4 and P5 have their timeout values set to more than 400 ms. What range of timeout values for P3 (within [100,500] ms) will certainly result in: (i) P2 winning the election? (ii) P3 winning the election? (iii) split vote?(d) (5 points) Suppose P2 sets its election timeout to 105 ms and calls for an election for term 2. What is the probability that another process (among P3, P4 and P5) also calls an election for term 2? Round your response upto 4 decimal places. [Hint: this probability can be computed as (1 – (probability that neither P3 nor P4 nor P5 call for an election for term 2))]2. Consider a system of three servers {S1, S2, S3} wanting to achieve log consensus using the Raft algorithm. For each sub-part below, state whether the shown snapshot of log entries at each server could arise from a valid run of the Raft algorithm. If yes, construct a scenario that would lead to these log entries in Raft’s execution. If not, explain what makes the entries invalid.Each number in the shown log entries represents the Raft term that the corresponding event is associated with. For the valid log entries, the scenario you construct should include, for each term: which server gets elected as the leader, which servers vote for it, and which log entries does it append / replicate at each server. (a) (3 points) S1: 1, 1, 1 S2: 1, 2, 2 S3: 1, 1 (b) (3 points) S1: 1, 1, 1 S2: 1, 1, 2 S3: 1, 1 (c) (3 points) S1: 1, 1, 1 S2: 1, 1, 2 S3: 1, 1, 3 (d) (3 points) S1: 1, 1, 1 S2: 1, 2, 2 S3: 1, 2, 3 (e) (3 points) S1: 1, 1, 3, 3 S2: 1, 2, 2 S3: 1, 1, 33. In a system using a blockchain for distributed consensus, in order to add a block to a chain, a participating node must solve the following puzzle: it must find a value x such that its hash, H(x||seed), is less than T. The hash function is such that a given value of x can uniformly map to any integer in [0, 2 256 − 1]. Assume T is set to 2226 .(a) (2 points) What is the probability that a given value of x, randomly chosen by the participating node, is a winning solution to the puzzle (i.e. H(x||seed) < T)? (b) (4 points) Assume a participating node adopts the standard strategy for solving the puzzle: it randomly picks a value x and checks if it is the winning solution. It keeps repeating this step, until a winning solution is found. Further assume that, for simplicity, the strategy is memoryless (unoptimized), in the sense that a value of x that has already been checked can get re-checked if it is randomly selected again. If the node can hash and check 25 values per second, what is the probability of finding a winning solution within 10 hours? (You may round your answer to five decimal places.)(c) (4 points) Assume there are 5000 participating nodes in the system, and that each node starts solving the puzzle at exactly the same time. Assuming the same rate of computing hashes at each node (i.e. 25 values per second), what is the probability that at least one node in the system finds a winning solution in 5 hours? (You may round your answer to four decimal places.)A bank uses a transaction processing system that complies with ACID properties. Within each transaction, a user can issue one or more of the following operations: (i) DEPOSIT which deposits the specified amount into the specified account, (ii) WITHDRAW which withdraws the specified amount from the specified account, and (iii) BALANCE which immediately displays the current balance in the specified account (also including the effects of operations previously executed within the same transaction).As a consistency check, if at the end of a transaction, any account has a negative balance, the system aborts that transaction. Consider the five transactions shown below that are executed serially (one after another) in order T1, T2, T3, T4, T5. Answer the following questions, assuming all accounts referred in the transactions have a balance of zero before T1 is executed. T1: DEPOSIT A 50; DEPOSIT B 80; DEPOSIT C 10 T2: WITHDRAW A 70; WITHDRAW B 50; DEPOSIT C 50; BALANCE B T3: WITHDRAW A 40; DEPOSIT B 20; WITHDRAW C 30; BALANCE A T4: WITHDRAW A 20; WITHDRAW B 60; DEPOSIT C 30 T5: BALANCE A; BALANCE B; BALANCE C (a) (5 points) For each transaction, state whether it gets committed or aborted and why. (b) (5 points) What will be the result displayed by each of the BALANCE operations invoked in the transactions?Consider the following two transactions, each with five operations: T1 T2 1 read A read D 2 read B write C 3 write A read A 4 read D write B 5 write B write E (a) (2 points) Write down all the conflicting pairs of operations across the two transactions. (You can refer to each operation as T n.m; e.g., T2.1 is “read D”, T2.2 is “write C”, and so on). (b) (3 points) Is the following interleaving of operations across T1 and T2 serially equivalent? Explain why or why not. T1 T2 read A read B write A read D write C read A read D write B write B write E (c) (3 points) Write down a non-serial interleaving of operations across T1 and T2, that could result from using strict two-phase locking (with read-write locks), and is equivalent in effect to a serial execution of T1 followed by T2. (d) (3 points) Write down a non-serial interleaving of operations across T1 and T2, that could result from using strict two-phase locking (with read-write locks), and is equivalent in effect to a serial execution of T2 followed by T1.(e) (4 points) Write down a partial interleaving of the operations across T1 and T2 that is compliant with strict two-phase locking (with read-write locks) and leads to a deadlock. List which lock (and in which mode – read or write) will be waited upon by each transaction in your deadlock. (f) (4 points) Write down an interleaving of the operations across T1 and T2 that is serially equivalent, but impossible with strict two-phase locking. Explain what makes the interleaving impossible with strict two-phase locking. (g) (3 points) Write down a non-serial interleaving of operations across T1 and T2, that could result from using timestamped ordering, and is equivalent in effect to a serial execution of T1 followed by T2. It should not result in any transaction getting aborted. You can use the example format like “write X (X.committedTS = 1, X.RTS = [1,2], X.TW=[2])” to indicate the state maintained by an object (i.e. timestamps for reads and tentative writes) after an operation has been executed. (h) (3 points) Write down a partial non-serial interleaving of the operations across T1 and T2, that could result from using timestamped ordering, and leads to T1 getting aborted (assume timestamp of T2 > timestamp of T1). You can use the example format mentioned in (g).3. Two-Phase Commit Figure 1 shows a system of three servers processing a distributed transaction. Server 1 is the coordinator and interacts with the client. The network delay between the client and the coordinator, and among the three servers is indicated in the figure. Client Server 1 (coordinator) Server 2 Server 3 50ms 20ms 10ms 5ms Figure 1: Figure for question 3 Any local processing at a server or self-messages take negligible time.The client issues a COMMIT request for its transaction at time t=0s. Assuming no messages are lost, no server crashes, and no server wishes to abort the transaction. Answer the following questions: (a) (3 points) When will each of the three servers locally commit the transaction? (b) (2 points) What is the earliest time at which the coordinator can safely send a message to the client stating that the transaction will be successfully committed?In Spanner and similar systems, a combination of two-phase commit (2PC) and Paxos protocols are used. Both the coordinator and participants in 2PC are implemented as replica groups, using Paxos to achieve consensus in the group. Each replica group has a leader, so during 2PC, the leader of the coordinator group communicates with the leaders of the participant groups.During the execution of 2PC in such a system, there are three points at which a consensus must be achieved within the nodes in a replica group for a transaction to be committed: (i) at each participant group to prepare for a commit, (ii) at the coordinator to decide on a commit after receiving a vote from each participant, and (iii) at each participant again to log the final commit.Suppose that there is one coordinator and three participants. Each of these has a Paxos replica group with 5 nodes. The leader of each replica group also acts as the proposer and the distinguished learner for the Paxos protocol, while the remaining four nodes are acceptors. The leaders of the participant and the coordinator replica groups send appropriate messages for 2PC to one another once consensus has been achieved (a decision has been reached) in their respective replica groups. Assume for simplicity that the coordinator replica group only coordinates the transaction and does not participate in processing the transaction (so the coordinator leader need not send prepare and commit messages to itself during 2PC).The communication latency between each pair of nodes within each group is exactly 10ms and the communication latency between any pair of nodes in two different groups is exactly 25ms. The processing latency at each node is negligible.Answer the following questions assuming that there are no failures or lost messages. Further assume that the leader of each replica group has already been elected / pre-configured. All participant groups are willing to commit the transaction, and all nodes within each replica group are completely in sync with one-another.(a) (6 points) With this combined 2PC / Paxos protocol, (ai) what is the minimum amount of time it would take for each node in the participant group to commit a transaction after the leader of the coordinator group receives the “commit” command from the client? (3 points)(aii) how many messages are exchanged in the system before all nodes in the participant groups commit the transaction? (Ignore any message that a process may send to itself). (3 points) [Hint: Think about the message exchanges required by each protocol (2PC and Paxos). Are there messages that can be safely sent in parallel to reduce the commit latency?](b) (2 points) What is the earliest point at which the coordinator group’s leader can safely tell the client that the transaction will be successfully committed? Calculate the latency until this point (from the time since the leader of the coordinator group receives the “commit” command from the client).(c) (4 points) Suppose we re-configure the system such that the leader of the coordinator group also acts as the leader (proposer and distinguished learner) for the participant Paxos groups. Four nodes in each participant group continue to be acceptors. With this modification, what is the minimum time it takes for each node in the participant group to commit a transaction after the leader of the coordinator group receives the “commit” command from the client?Consider a Chord DHT with a 16-bit address space and the following 100 nodes (hexadecimal values in parentheses). 1127 (467), 2456 (998), 3786 (eca), 4562 (11d2), 5579 (15cb), 6016 (1780), 6134 (17f6), 6351 (18cf), 7576 (1d98), 8608 (21a0), 9379 (24a3), 9916 (26bc), 10111 (277f), 10335 (285f), 11967 (2ebf), 12158 (2f7e), 12721 (31b1), 14471 (3887), 15900 (3e1c), 16315 (3fbb), 16419 (4023), 17102 (42ce), 17193 (4329), 17460 (4434), 19257 (4b39), 19857 (4d91), 19963 (4dfb), 20012 (4e2c), 20485 (5005), 20721 (50f1), 21422 (53ae), 22029 (560d), 24052 (5df4), 24335 (5f0f), 25642 (642a), 25963 (656b), 26446 (674e), 26842 (68da), 27477 (6b55), 28481 (6f41), 28926 (70fe), 29112 (71b8), 29408 (72e0), 29548 (736c), 30729 (7809), 31428 (7ac4), 32403 (7e93), 33125 (8165), 33875 (8453), 34871 (8837), 35312 (89f0), 35526 (8ac6), 35600 (8b10), 37641 (9309), 37773 (938d), 41351 (a187), 41463 (a1f7), 42016 (a420), 42200 (a4d8), 42513 (a611), 43590 (aa46), 43934 (ab9e), 43967 (abbf), 45357 (b12d), 46305 (b4e1), 46625 (b621), 46684 (b65c), 47477 (b975), 48441 (bd39), 48679 (be27), 49659 (c1fb), 49844 (c2b4), 50069 (c395), 50135 (c3d7), 50197 (c415), 52086 (cb76), 52325 (cc65), 52368 (cc90), 53171 (cfb3), 53684 (d1b4), 54501 (d4e5), 55037 (d6fd), 55263 (d7df), 56343 (dc17), 56739 (dda3), 57289 (dfc9), 58569 (e4c9), 58640 (e510), 59317 (e7b5), 59453 (e83d), 60596 (ecb4), 60598 (ecb6), 62457 (f3f9), 62794 (f54a), 63816 (f948), 64743 (fce7), 64831 (fd3f), 65010 (fdf2), 65363 (ff53), 65423 (ff8f), For programmatic computations, these numbers have also been made available at: https://courses.grainger.illinois.edu/ece428/sp2022/assets/hw/hw6-ids.txt(a) (6 points) List the fingers of node 49844. (b) (6 points) List the nodes that would be encountered on the lookup of the following keys by node 49844: (i) 12100 (ii) 29200(c) (4 points) A power outage takes out a few specific nodes: the ones whose numbers are odd. Assume that each node maintains only one successor, and no stabilization algorithm has had a chance to run, so the finger tables have not been updated. When a node in the normal lookup protocol tries to contact a finger entry that is no longer alive (i.e. its attempt to connect with that node fails), it switches to the next best option in its finger table that is alive. List the nodes that would be encountered on the lookup of the key 29200 by node 49844 (include the failed ones).(a) (6 points) Given four vectors V1, V2, V3 and V4, each having a dimension of N. Use a map-reduce chain to compute the dot product of (V1 + V2) and (V3 + V4). The input to the map-reduce chain is in the following key-value format: (k, v), with k = (i, n), where i ∈ [1, N] is the index of the vector Vn, and v is the corresponding value (Vn[i]). The output of your map-reduce chain must of the form (-, final result). Assume there are 50 nodes (servers) in your cluster. Your map-reduce chain must support proper partitioning and load-balancing across these nodes. In particular, assuming a vector dimension of 10000 ensure that a single node is not required to handle more than ≈800 values at any stage. You can assume that, if allowed by your map-reduce semantics, the underlying framework perfectly load-balances how different keys are sent to different nodes.(b) (6 points) Given a directed graph G = (V, E), use a map-reduce chain to compute the set of vertices that are reachable in exactly 3 hops from each vertex. For example, in a graph with vertices {a, b, c, d} and the following directed edges, a → b → c → d, the vertex d is reachable in exactly three hops from vertex a.The input to the map-reduce chain is in the following key-value format: (k, v) where k is a graph vertex and v is a list of its out-neighbors; i.e., for each x ∈ v,(k, x) is a directed edge in E. The output must be key-value pairs (k, v), where k is a graph vertex and v is a list of vertices that are reachable in exactly three hops from k. The list must be empty if there are no vertices reachable in exactly three hops from k. Vertices maybe repeated in the three-hop path and need not be distinct. It is also possible for a vertex to be exactly three hops away from itself, in which case it should be included in the list.For your assistance, the first map function for an exemplar map-reduce chain has been provided below. You may choose to use the same function, or design your own. function map1((k, v)): for node in v do emit ( ( node , ( “in” , k ) ) ) emit ( ( k , ( “out” , node ) ) ) end for if v is empty then emit ( (k, (“out”, ))) end if end function
In Spanner and similar systems, a combination of two-phase commit (2PC) and Paxos protocols are used. Both the coordinator and participants in 2PC are implemented as replica groups, using Paxos to achieve consensus in the group. Each replica group has a leader, so during 2PC, the leader of the coordinator group communicates with the leaders of the participant groups.During the execution of 2PC in such a system, there are three points at which a consensus must be achieved within the nodes in a replica group for a transaction to be committed: (i) at each participant group to prepare for a commit, (ii) at the coordinator to decide on a commit after receiving a vote from each participant, and (iii) at each participant again to log the final commit.Suppose that there is one coordinator and three participants. Each of these has a Paxos replica group with 5 nodes. The leader of each replica group also acts as the proposer and the distinguished learner for the Paxos protocol, while the remaining four nodes are acceptors. The leaders of the participant and the coordinator replica groups send appropriate messages for 2PC to one another once consensus has been achieved (a decision has been reached) in their respective replica groups. Assume for simplicity that the coordinator replica group only coordinates the transaction and does not participate in processing the transaction (so the coordinator leader need not send prepare and commit messages to itself during 2PC).The communication latency between each pair of nodes within each group is exactly 10ms and the communication latency between any pair of nodes in two different groups is exactly 25ms. The processing latency at each node is negligible.Answer the following questions assuming that there are no failures or lost messages. Further assume that the leader of each replica group has already been elected / pre-configured. All participant groups are willing to commit the transaction, and all nodes within each replica group are completely in sync with one-another.(a) (6 points) With this combined 2PC / Paxos protocol, (ai) what is the minimum amount of time it would take for each node in the participant group to commit a transaction after the leader of the coordinator group receives the “commit” command from the client? (3 points)(aii) how many messages are exchanged in the system before all nodes in the participant groups commit the transaction? (Ignore any message that a process may send to itself). (3 points) [Hint: Think about the message exchanges required by each protocol (2PC and Paxos). Are there messages that can be safely sent in parallel to reduce the commit latency?](b) (2 points) What is the earliest point at which the coordinator group’s leader can safely tell the client that the transaction will be successfully committed? Calculate the latency until this point (from the time since the leader of the coordinator group receives the “commit” command from the client).(c) (4 points) Suppose we re-configure the system such that the leader of the coordinator group also acts as the leader (proposer and distinguished learner) for the participant Paxos groups. Four nodes in each participant group continue to be acceptors. With this modification, what is the minimum time it takes for each node in the participant group to commit a transaction after the leader of the coordinator group receives the “commit” command from the client?Consider a Chord DHT with a 16-bit address space and the following 100 nodes (hexadecimal values in parentheses). 1127 (467), 2456 (998), 3786 (eca), 4562 (11d2), 5579 (15cb), 6016 (1780), 6134 (17f6), 6351 (18cf), 7576 (1d98), 8608 (21a0), 9379 (24a3), 9916 (26bc), 10111 (277f), 10335 (285f), 11967 (2ebf), 12158 (2f7e), 12721 (31b1), 14471 (3887), 15900 (3e1c), 16315 (3fbb), 16419 (4023), 17102 (42ce), 17193 (4329), 17460 (4434), 19257 (4b39), 19857 (4d91), 19963 (4dfb), 20012 (4e2c), 20485 (5005), 20721 (50f1), 21422 (53ae), 22029 (560d), 24052 (5df4), 24335 (5f0f), 25642 (642a), 25963 (656b), 26446 (674e), 26842 (68da), 27477 (6b55), 28481 (6f41), 28926 (70fe), 29112 (71b8), 29408 (72e0), 29548 (736c), 30729 (7809), 31428 (7ac4), 32403 (7e93), 33125 (8165), 33875 (8453), 34871 (8837), 35312 (89f0), 35526 (8ac6), 35600 (8b10), 37641 (9309), 37773 (938d), 41351 (a187), 41463 (a1f7), 42016 (a420), 42200 (a4d8), 42513 (a611), 43590 (aa46), 43934 (ab9e), 43967 (abbf), 45357 (b12d), 46305 (b4e1), 46625 (b621), 46684 (b65c), 47477 (b975), 48441 (bd39), 48679 (be27), 49659 (c1fb), 49844 (c2b4), 50069 (c395), 50135 (c3d7), 50197 (c415), 52086 (cb76), 52325 (cc65), 52368 (cc90), 53171 (cfb3), 53684 (d1b4), 54501 (d4e5), 55037 (d6fd), 55263 (d7df), 56343 (dc17), 56739 (dda3), 57289 (dfc9), 58569 (e4c9), 58640 (e510), 59317 (e7b5), 59453 (e83d), 60596 (ecb4), 60598 (ecb6), 62457 (f3f9), 62794 (f54a), 63816 (f948), 64743 (fce7), 64831 (fd3f), 65010 (fdf2), 65363 (ff53), 65423 (ff8f), For programmatic computations, these numbers have also been made available at: https://courses.grainger.illinois.edu/ece428/sp2022/assets/hw/hw6-ids.txt(a) (6 points) List the fingers of node 49844. (b) (6 points) List the nodes that would be encountered on the lookup of the following keys by node 49844: (i) 12100 (ii) 29200(c) (4 points) A power outage takes out a few specific nodes: the ones whose numbers are odd. Assume that each node maintains only one successor, and no stabilization algorithm has had a chance to run, so the finger tables have not been updated. When a node in the normal lookup protocol tries to contact a finger entry that is no longer alive (i.e. its attempt to connect with that node fails), it switches to the next best option in its finger table that is alive. List the nodes that would be encountered on the lookup of the key 29200 by node 49844 (include the failed ones).(a) (6 points) Given four vectors V1, V2, V3 and V4, each having a dimension of N. Use a map-reduce chain to compute the dot product of (V1 + V2) and (V3 + V4). The input to the map-reduce chain is in the following key-value format: (k, v), with k = (i, n), where i ∈ [1, N] is the index of the vector Vn, and v is the corresponding value (Vn[i]). The output of your map-reduce chain must of the form (-, final result). Assume there are 50 nodes (servers) in your cluster. Your map-reduce chain must support proper partitioning and load-balancing across these nodes. In particular, assuming a vector dimension of 10000 ensure that a single node is not required to handle more than ≈800 values at any stage. You can assume that, if allowed by your map-reduce semantics, the underlying framework perfectly load-balances how different keys are sent to different nodes.(b) (6 points) Given a directed graph G = (V, E), use a map-reduce chain to compute the set of vertices that are reachable in exactly 3 hops from each vertex. For example, in a graph with vertices {a, b, c, d} and the following directed edges, a → b → c → d, the vertex d is reachable in exactly three hops from vertex a.The input to the map-reduce chain is in the following key-value format: (k, v) where k is a graph vertex and v is a list of its out-neighbors; i.e., for each x ∈ v,(k, x) is a directed edge in E. The output must be key-value pairs (k, v), where k is a graph vertex and v is a list of vertices that are reachable in exactly three hops from k. The list must be empty if there are no vertices reachable in exactly three hops from k. Vertices maybe repeated in the three-hop path and need not be distinct. It is also possible for a vertex to be exactly three hops away from itself, in which case it should be included in the list.For your assistance, the first map function for an exemplar map-reduce chain has been provided below. You may choose to use the same function, or design your own. function map1((k, v)): for node in v do emit ( ( node , ( “in” , k ) ) ) emit ( ( k , ( “out” , node ) ) ) end for if v is empty then emit ( (k, (“out”, ))) end if end function
A bank uses a transaction processing system that complies with ACID properties. Within each transaction, a user can issue one or more of the following operations: (i) DEPOSIT which deposits the specified amount into the specified account, (ii) WITHDRAW which withdraws the specified amount from the specified account, and (iii) BALANCE which immediately displays the current balance in the specified account (also including the effects of operations previously executed within the same transaction).As a consistency check, if at the end of a transaction, any account has a negative balance, the system aborts that transaction. Consider the five transactions shown below that are executed serially (one after another) in order T1, T2, T3, T4, T5. Answer the following questions, assuming all accounts referred in the transactions have a balance of zero before T1 is executed. T1: DEPOSIT A 50; DEPOSIT B 80; DEPOSIT C 10 T2: WITHDRAW A 70; WITHDRAW B 50; DEPOSIT C 50; BALANCE B T3: WITHDRAW A 40; DEPOSIT B 20; WITHDRAW C 30; BALANCE A T4: WITHDRAW A 20; WITHDRAW B 60; DEPOSIT C 30 T5: BALANCE A; BALANCE B; BALANCE C (a) (5 points) For each transaction, state whether it gets committed or aborted and why. (b) (5 points) What will be the result displayed by each of the BALANCE operations invoked in the transactions?Consider the following two transactions, each with five operations: T1 T2 1 read A read D 2 read B write C 3 write A read A 4 read D write B 5 write B write E (a) (2 points) Write down all the conflicting pairs of operations across the two transactions. (You can refer to each operation as T n.m; e.g., T2.1 is “read D”, T2.2 is “write C”, and so on). (b) (3 points) Is the following interleaving of operations across T1 and T2 serially equivalent? Explain why or why not. T1 T2 read A read B write A read D write C read A read D write B write B write E (c) (3 points) Write down a non-serial interleaving of operations across T1 and T2, that could result from using strict two-phase locking (with read-write locks), and is equivalent in effect to a serial execution of T1 followed by T2. (d) (3 points) Write down a non-serial interleaving of operations across T1 and T2, that could result from using strict two-phase locking (with read-write locks), and is equivalent in effect to a serial execution of T2 followed by T1.(e) (4 points) Write down a partial interleaving of the operations across T1 and T2 that is compliant with strict two-phase locking (with read-write locks) and leads to a deadlock. List which lock (and in which mode – read or write) will be waited upon by each transaction in your deadlock. (f) (4 points) Write down an interleaving of the operations across T1 and T2 that is serially equivalent, but impossible with strict two-phase locking. Explain what makes the interleaving impossible with strict two-phase locking. (g) (3 points) Write down a non-serial interleaving of operations across T1 and T2, that could result from using timestamped ordering, and is equivalent in effect to a serial execution of T1 followed by T2. It should not result in any transaction getting aborted. You can use the example format like “write X (X.committedTS = 1, X.RTS = [1,2], X.TW=[2])” to indicate the state maintained by an object (i.e. timestamps for reads and tentative writes) after an operation has been executed. (h) (3 points) Write down a partial non-serial interleaving of the operations across T1 and T2, that could result from using timestamped ordering, and leads to T1 getting aborted (assume timestamp of T2 > timestamp of T1). You can use the example format mentioned in (g).3. Two-Phase Commit Figure 1 shows a system of three servers processing a distributed transaction. Server 1 is the coordinator and interacts with the client. The network delay between the client and the coordinator, and among the three servers is indicated in the figure. Client Server 1 (coordinator) Server 2 Server 3 50ms 20ms 10ms 5ms Figure 1: Figure for question 3 Any local processing at a server or self-messages take negligible time.The client issues a COMMIT request for its transaction at time t=0s. Assuming no messages are lost, no server crashes, and no server wishes to abort the transaction. Answer the following questions: (a) (3 points) When will each of the three servers locally commit the transaction? (b) (2 points) What is the earliest time at which the coordinator can safely send a message to the client stating that the transaction will be successfully committed?
1. Consider a system of 5 processes {P1, P2, P3, P4, P5} using Raft’s algorithm for leader election. Suppose P1, the leader for term 1, fails and its four followers receive its last heartbeat at exactly the same time. Answer the following questions assuming that the election timeout is chosen uniformly at random from the range [100,500] ms (unless otherwise specified), no processing delay exists, and the one-way delay for all messages between two processes are as shown in Figure 1. The processes communicate with oneanother only through their direct channels (not via other processes). Each question below is independent of others. P2 P3 P5 P4 25ms 10ms 30ms 15ms 5ms 20ms Figure 1: Figure for question 1(a) (2 points) Suppose P2 and P3 both set their election timeout to 150 ms and call an election for term 2. Assume P4 and P5 have their timeout values set to more than 400 ms. Which candidate (P2 or P3) will each of the four alive processes vote for? Will a leader be elected for term 2? If yes, which process?(b) (2 points) Suppose P2 sets its election timeout to 150 ms and calls an election for term 2, and P3 sets its timeout to 170 ms and also calls an election for term 2. Assume P4 and P5 have their timeout values set to more than 400 ms. Which candidate (P2 or P3) will each of the four alive processes vote for? Will a leader be elected for term 2? If yes, which process?(c) (6 points) Suppose P2 sets its election timeout to 150 ms and calls for an election for term 2. Assume P4 and P5 have their timeout values set to more than 400 ms. What range of timeout values for P3 (within [100,500] ms) will certainly result in: (i) P2 winning the election? (ii) P3 winning the election? (iii) split vote?(d) (5 points) Suppose P2 sets its election timeout to 105 ms and calls for an election for term 2. What is the probability that another process (among P3, P4 and P5) also calls an election for term 2? Round your response upto 4 decimal places. [Hint: this probability can be computed as (1 – (probability that neither P3 nor P4 nor P5 call for an election for term 2))]2. Consider a system of three servers {S1, S2, S3} wanting to achieve log consensus using the Raft algorithm. For each sub-part below, state whether the shown snapshot of log entries at each server could arise from a valid run of the Raft algorithm. If yes, construct a scenario that would lead to these log entries in Raft’s execution. If not, explain what makes the entries invalid.Each number in the shown log entries represents the Raft term that the corresponding event is associated with. For the valid log entries, the scenario you construct should include, for each term: which server gets elected as the leader, which servers vote for it, and which log entries does it append / replicate at each server. (a) (3 points) S1: 1, 1, 1 S2: 1, 2, 2 S3: 1, 1 (b) (3 points) S1: 1, 1, 1 S2: 1, 1, 2 S3: 1, 1 (c) (3 points) S1: 1, 1, 1 S2: 1, 1, 2 S3: 1, 1, 3 (d) (3 points) S1: 1, 1, 1 S2: 1, 2, 2 S3: 1, 2, 3 (e) (3 points) S1: 1, 1, 3, 3 S2: 1, 2, 2 S3: 1, 1, 33. In a system using a blockchain for distributed consensus, in order to add a block to a chain, a participating node must solve the following puzzle: it must find a value x such that its hash, H(x||seed), is less than T. The hash function is such that a given value of x can uniformly map to any integer in [0, 2 256 − 1]. Assume T is set to 2226 .(a) (2 points) What is the probability that a given value of x, randomly chosen by the participating node, is a winning solution to the puzzle (i.e. H(x||seed) < T)? (b) (4 points) Assume a participating node adopts the standard strategy for solving the puzzle: it randomly picks a value x and checks if it is the winning solution. It keeps repeating this step, until a winning solution is found. Further assume that, for simplicity, the strategy is memoryless (unoptimized), in the sense that a value of x that has already been checked can get re-checked if it is randomly selected again. If the node can hash and check 25 values per second, what is the probability of finding a winning solution within 10 hours? (You may round your answer to five decimal places.)(c) (4 points) Assume there are 5000 participating nodes in the system, and that each node starts solving the puzzle at exactly the same time. Assuming the same rate of computing hashes at each node (i.e. 25 values per second), what is the probability that at least one node in the system finds a winning solution in 5 hours? (You may round your answer to four decimal places.)
Figure 1 shows three process P1, P2, and P3 (with ids 1, 2, and 3 respectively) implementing the RicartAgrawala (RA) algorithm for mutual exclusion. The lines indicate requests for accessing the critical section (CS) made by each process – blue, green, and red requests are from P1, P2, and P3 respectively. Other than the replies to CS requests (not shown in the figure), no other messages are exchanged between the processes. The timeline indicates real time. Assume that any reply sent for a CS request reaches the requesting process after exactly one (real) time unit. Further assume that any process that enters the CS, spends 3 (real) time units in it.(a) (2 points) What is P1’s state as per the RA algorithm when it receives CS request from P2 – Held, Wanted, or neither (Free)? How will P1 handle P2’s request upon receiving it – will it immediately send back a reply or will it queue the request? Why? (b) (2 points) What is P3’s state as per the RA algorithm when it receives CS request from P2 – Held, Wanted, or neither (Free)? How will P3 handle P2’s request upon receiving it – will it immediately send back a reply or will it queue the request? Why?(c) (2 points) What is P2’s state as per the RA algorithm when it receives CS request from P1 – Held, Wanted, or neither (Free)? How will P2 handle P1’s request upon receiving it – will it immediately send back a reply or will it queue the request? Why?(d) (2 points) What is P3’s state as per the RA algorithm when it receives CS request from P1 – Held, Wanted, or neither (Free)? How will P3 handle P1’s request upon receiving it – will it immediately send back a reply or will it queue the request? Why?(e) (2 points) What is P2’s state as per the RA algorithm when it receives CS request from P3 – Held, Wanted, or neither (Free)? How will P2 handle P3’s request upon receiving it – will it immediately send back a reply or will it queue the request? Why?Consider the following modification of the Bully algorithm: The initiating node (which we assume does not fail) sends an Election message only to the process with the highest id. If it does not get a response after a timeout, it then sends an Election message to the process with the second highest id. If after another timeout it gets no response, it tries the third highest id, and so on. If no higher numbered processes respond, it sends a Coordinator message to all lower-numbered processes.(a) (1 point) What should a process do when it receives an Election message in order to minimize turnaround time? For the following parts, consider a distributed system of 8 processes {P1, P2, . . . P8}. P8 has the highest id, followed by P7, then P6, and so on. The system uses the modified Bully algorithm for leader election (including the solution for 2a). Initially, all 8 processes are alive and P8 is the leader. Then P8 fails, P3 detects this, and initiates the election. P3 knows that P8 has failed and P7 has the highest id among the remaining processes. Assume one-way message transmission time is T, and timeout is set using the knowledge of T.(b) (1 point) If no other node fails during the election run, how many total messages will be sent by all processes in this election run? (c) (1 point) If no other node fails during the election run, how long will it take for the election to finish?(d) (1 point) Now assume that right after P3 detects P8’s failure and initiates the election, P7 fails. How many total messages will be sent by all processes in this election run? (e) (1 point) For the above scenario (where P7 fails right after P3 initiates election upon detecting P8’s failure), how long will it take for the election to finish?(5 points) Consider a system of N process that are arranged in a ring, with each process having a ring successor and a predecessor, and a communication channel only to its ring successor. Each process Pi has a unique id i. Further, each process Pi maintains a value xi (which may not be unique across processes). A process may not know the total number of other processes in the ring. Each process Pi is required to set the value of an output variable yi (initialized to undecided) to minN j=1(xj ). The safety condition for the problem requires that, at any point in time, the variable yi at process Pi ∀i ∈ [1, N] is either undecided or minN j=1(xj ).A distributed algorithm designed for the above problem works as follows: • A process Pi initiates the algorithm by sending (propose, xi) to its ring successor. • When a process Pj receives (propose, x) from its ring predecessor: – if x < xj , it forwards (propose, x) to its successor. – if x > xj , it sends (propose, xj ) to its successor. – if x = xj , it concludes that x = xj is the minimum value, and sends (decided, x) to its successor.• When a process Pj receives (decided, x), it sets yj = x and forwards (decided, x) to its successor (if it had not already done so in the past). Once Pj sets yj , it ignores any subsequently received decided messages. Multiple processes may initiate the above algorithm simultaneously. Assume no process fails and the communication channel delivers all messages correctly and exactly once. Does the algorithm described above guarantee safety condition for the problem? If yes, prove how. If not, (i) describe a scenario where safety is violated, and (ii) suggest modifications to the algorithm that would guarantee the safety condition.Consider a system of five processes [P1, P2, P3, P4, P5]. Each process Pi proposes a value xi . Let x1 = 6, x2 = 5, x3 = 8, x4 = 2, and x5 = 10. Each process Pk must decide on an output variable yk (initialized to undecided), setting it to one of the proposed values xi for i ∈ [1, 5]. The safety condition requires that at any point in time, for any two processes Pj and Pk, either yj or yk is undecided, or yj = yk (in other words, the decided value must be same across all processes that have decided).A consensus algorithm is designed for the above problem that works as follows: • Each process R-multicasts its proposed value at the same time t = 0ms since start of the system (as per their local clocks). • As soon as proposed values from all 5 processes are delivered at a process Pj , Pj sets yj to the minimum of the proposed values it received from the five processes.• If yj is still undecided at time (t + timeout), Pj computes the minimum of the proposed values it has received so far and sets yj to that value. • Once a process Pj decides on yj , it does not update yj ’s value, and ignores future proposals (if any are received). Assume that all clocks are perfectly synchronized with zero skew with respect to one-another. The proposed value xi of a process Pi gets self-delivered immediately at time t = 0ms when Pi begins the multicast of xi . A message sent from a process to any other process takes exactly T = 10ms (and this value is known to all processes). All communication channels are reliable. Processes may fail, but a failed process never restarts.Suppose the timeout value for the above algorithm is set to 25ms. Answer the following questions with respect to local time at the processes’ clock since the start of the system. (a) (2 points) Assume no process fails in the system. When will each process decide on a value and what will each of their decided values be? (b) (2 points) Assume P4 fails right after unicasting x4 to P3 and P5 but just before it could initiate the unicast of x4 to any of the other processes. When will each of the alive processes decide on a value and what will each of their decided values be?(c) (2 points) Assume P4 fails at right after unicasting x4 to P3 but just before it could initiate the unicast of x4 to any of the other processes. P3 fails right after it has relayed x4 to P5 but just before it unicasts it to any other process. When will each of the alive processes decide on a value and what will each of their decided values be?(d) (2 points) Assume P4 fails right after unicasting x4 to P3 but just before it could initiate the unicast of x4 to any of the other processes. P3 fails right after it has relayed x4 to P5 but just before it unicasts it to any other process. P2 fails right before it could unicast x2 to any process. When will each of the remaining alive processes decide on a value and what will each of their decided values be?(e) (2 points) What is the smallest value that the timeout should be set to for ensuring safety in this system? (f) (1 point) Answer Q4c assuming that the timeout is updated to the value in Q4e. (g) (1 point) Answer Q4d assuming that the timeout is updated to the value in Q4e.Consider a system of five processes that implement the Paxos algorithm for consensus. As shown in Figure 2, P1 and P2 are proposers. P3, P4, P5 are acceptors. P1 sends a prepare message with proposal number 2 to processes P4 and P5, receives their replies, and sends an accept message with proposed value of 10 for proposal #2. P2 concurrently sends a prepare message with proposal #5, with an initial intention to propose a value of 15 if it receives sufficient replies. Only a subset of responses from processes P4, and P5 are shown in the figure. Assume no other proposals are initiated.Answer the following sub-questions. 0 1 2 3 4 5 6 7 8 9 10 11 12 P1 P2 P3 P4 P5 Prepare #2 13 14 15 16 17 18 Accept #2 Proposed value = 10 Prepare #5 Acceptors Proposers Figure 2: Figure for question 5(f) (a) (1 point) Which processes will accept P1’s proposal? (b) (1 point) Which processes will reply back to P2’s prepare message? (c) (2 points) Will P2 send out an accept message for its proposal #5? If yes, what will be the corresponding proposed value?(d) (2 points) Consider the state of the system at time 10 units. Has the proposed value 10 been implicitly decided upon at this point? If yes, explain why? If not, construct a possible scenario that may occur after time 10 units where the system ends up deciding on a different proposed value. The scenario would involve a temporal sequence of events that may differ from the one shown in the figure beyond time t=10units but must comply with what is shown until t=10units. An event in such a sequence may include a prepare/accept request sent by a proposer or received by an acceptor, or a prepare reply received by the proposer at some time unit.(e) (1 point) Suppose that P1’s accept request reaches P5 at time 8 units (instead of 14 units). If we now consider the state of the system at time 10 units, has the proposed value 10 been implicitly decided upon?(f) (1 point) Suppose that P1’s accept request reaches P4 at time 15 units (instead of 9 unit) and reaches P5 at the original time 14 units. Will P2 send out an accept message for its proposal #5? If yes, what will be the corresponding proposed value?
P1 P2 A B C D E F H I J Figure 1: for question 1 1. (a) (4 points) Consider the timeline of events {A,B,…J} across two processes as shown in Figure 1. List all possible linearizations for this system that includes each event.(b) (5 points) What is the total number of consistent global states that can be possibly captured for the above system? Identify each of them by the frontier events of the corresponding cuts. (c) (1 point) Provide an example of an unstable global safety property (which results in unstable nonsafety). How can it be made stable? (This is unrelated to 1(a) and 1(b).) P2 P1 P3 P4 Figure 2: for question 2(a)2. (a) (6 points) In the execution in Figure 2, processes send messages to each other to implement FIFO ordered multicast. To simplify the picture, messages sent by each process to itself are not shown, but assume that such messages are received and delivered instantaneously. For the questions below, you may use printed or hand-drawn figure with hand-drawn responses, or digitally edit the figure from the homework PDF.(i) Identify the messages that are buffered at the processes to ensure FIFO multicast delivery. (Circle the receive event for the buffered messages to identify those messages.) (3 points)(ii) For each message buffered as above, determine the earliest instant of time at which the message may be delivered, while ensuring FIFO multicast. (To identify the instant of time draw an arrow that begins at the time when the message is received to the time at which the message may be delivered.) (3 points) P2 P1 P3 P4 Figure 3: for question 2(b)(b) (6 points) In the execution in Figure 3, processes send messages to each other to implement causal multicast. To simplify the picture, messages sent by each process to itself are not shown, but assume that such messages are received and delivered instantaneously. For the questions below, you may use printed or hand-drawn figure with hand-drawn responses, or digitally edit the figure from the homework PDF.(i) Identify the messages that are buffered at the processes to ensure causally-ordered multicast delivery (Circle the receive event for the buffered messages to identify those messages.) (3 points)(ii) For each message buffered as above, determine the earliest instant of time at which the message may be delivered, while ensuring causally-ordered multicast. (To identify the instant of time draw an arrow that begins at the time when the message is received to the time at which the message may be delivered.) (3 points)3. For each of the statements below, identify whether it is true or false. If it is false, present a counterexample. If it is true, prove why. (a) (2 points) A total ordered multicast is also causal.(b) (3 points) If the processes in a system use R-multicast, and each channel follows FIFO order, then causal ordering is satisfied. (c) (3 points) We can implement the ISIS algorithm for total ordering on top of (or using) causalordered multicast, to achieve a total causal multicast.Process ID Time when “enter” is called (since start of system) Time spent in critical section after “enter” returns, before calling “exit”. P1 250ms 50ms P2 30ms 50ms P3 100ms 30ms P4 20ms 60ms P5 15ms 20ms Table 1: Timings for Q44. Consider a distributed system of five processes {P1, P2, P3, P4, P5}. Each process needs mutually exclusive access to a critical section. Table 1 lists the time when each process first makes a blocking call to “enter” the critical section (since the start of the system). It also lists the time each process spends in the critical section after “enter” succeeds, before calling “exit”.(a) (5 points) Suppose the system uses the central server algorithm for mutual exclusion, electing P4 as the leader. Assume that message latency at P4 for communicating with the leader (itself) is zero, i.e. it takes negligible time for P4’s token request to reach the leader upon calling enter, to receive the token after its request has been granted, and for the token to be released back to the leader upon calling exit. For all other processes, assume the one-way network latency for communicating with the leader (P4) is fixed at 10ms, i.e. it takes 10ms each for the token request to reach P4 after calling “enter”, 10ms for the token to reach the process after the leader has granted the request, and 10ms for the token to reach the leader after the process has called “exit”. The leader grants requests in the order in which it receives them. When will each process start executing its critical section?(b) (5 points) Now suppose that the system uses ring-based algorithm for mutual exclusion, with the ring structured as shown below (P1 to P2 to P3 to P4 to P5 to P1). Figure 4 At time 0ms (when the system starts up), the token is at P1. The network latency for passing the token from a given process to its ring successor is fixed at 10ms. When will each process start executing its critical section?
[pdf-embedder url="https://assignmentchef.com/wp-content/uploads/2025/02/ece428_sp25_hw1.pdf"] 1. Consider a distributed system of four processes as shown in Figure 1. The system is synchronous, and the minimum and maximum network delays (in seconds) between each pair of processes are shown in the figure as [min, max] against each channel. Assume no messages are lost on the channel, and the processing time at each process is negligible compared to network delays. a b c d [3,11] [4,15] [6,8] [3,13] [2,4] [12,18] Figure 1: Figure for question 1. (a) (3 points) Consider an all-to-all heartbeat protocol, where each process sends a heartbeat to each other process periodically every T=50s, and each process sets a timeout (computed appropriately from the known bounds on network delay) to detect failure of other processes. Suppose that process a crashes. For every other process, calculate how long it will take to detect a’s failure, in the worst case. (b) (3 points) Now consider a small extension of the protocol in in Q1(a) – as soon as a process detects that another process p has crashed via a timeout, it sends a notification to all other processes about p’s failure. Suppose that process a is the only process that crashes. For every other process, calculate how long it will take to detect a’s failure, in the worst case. (c) (2 points) If it is known that at most two processes may crash within a few hours of each other, how would you redesign the heartbeat protocol described in Q1(a) to minimize bandwidth usage, without increasing the worst case time taken to detect the failure of a process by at least one alive process. [Hint: do we really need all-to-all heartbeats?] (d) (2 points) Assuming the modification in Q1(c), list the minimal set of processes a must send heartbeats to, so as to minimize the worst case time taken to detect failure of a by at least one alive process. client s3 s2 s1 RTT = 36ms RTT = 60ms RTT = 24ms Figure 2: Figure for question 2(a). 2. (a) (4 points) Consider Figure 2. The client has an option of using any of the three authoritative sources of real time (s1, s2, or s3) for external synchronization via Cristian algorithm. The roundtrip times (RTT) between the client and the three servers are shown in the figure. Assume that the observed RTT to each server remains constant across all synchronization attempts. (i) Which server should the client choose to achieve the lowest accuracy bound right after synchronization? What is the value of this bound, as estimated by the client right after synchronization? [1 point] (ii) If the client’s local clock drifts at the rate of 3µs every second, what is the smallest frequency (or the longest time-period) at which the client must initiate synchronization with the server it chose in part (i), so as to maintain an accuracy bound within 90ms at all times. [3 points] 12 39 46 30 32 65 71 52 60 90 93 75 A B Figure 3: Figure for question 2(b). (b) (6 points) Consider the series of message exchanged between two servers A and B as shown in Figure 3. The local timestamps at the servers when sending and receiving each message are shown in the figure. (i) Assume symmetric mode synchronization, where the send and receive timestamps for each message are recorded by both servers. Given A’s knowledge of the send and receive timestamps for all six messages, what is the lowest synchronization bound (as estimated by A) with which A can compute its offset relative to B? What is the corresponding estimated offset value? [Hint: A may use any pair of messages exchanged between the two servers, and not just two consecutive messages to compute offsets.] (4 points) (ii) Now assume that A uses the same series of messages for synchronization via Cristian algorithm: messages sent from A to B are requests, and messages from B to A are responses carrying the timestamp when B received the last request. What is the tightest synchronization bound (as estimated by A) with which A can compute its offset relative to B? (2 points) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 P1 P2 P3 P4 A B C D E F G H I J K L M N O P Figure 4: Timeline for questions 3 and 4. 3. The timeline in Figure 4 shows 16 events (A to P) across four processes. The numbers below indicate real time. (a) (2 points) Write down the Lamport timestamp of each event. (b) (4 points) Write down the vector timestamp of each event. (c) (4 points) List all events considered concurrent with: (i) A, (ii) F, (iii) K, and (iv) N. 4. (a) (4 points) Consider the timeline and events in Figure 4 again. Suppose that P2 initiates the Chandy-Lamport snapshot algorithm at (real) time 8. Assuming FIFO channels, write down all possible consistent cuts that the resulting snapshot could capture. You can describe each cut by its frontier events. (b) (6 points) Write all possible states of the incoming channels at P1 and at P3 that the above snapshot could record. You can denote each message by its send and receive event ids.
553.421 Honors Intro. to Probability Assignment #3 Due Friday, Sep. 23 11:59PM as a PDF upload to Gradescope. 3.1. You pick two cards from a standard deck of 52 cards. Compute the probability they are both red given they are the same color. 3.2. Consider the sample space of the 10! (equally likely) orderings of the digits 0 thru 9. Let’s say you’ll win if you pick an ordering that starts with three even digits or if you pick an ordering that ends with three odd digits. Compute the probability you’ll win. Please simplify completely! 3.3. (a) Suppose A and B are events. We denote set subtraction A - B to mean take away all the members of B that happen to belong to A. Since we can’t take away members of B that don’t belong to A, we can write A-B = A-(A∩B),i.e., A-B = A∩Bc. Show that P (A-B) = P (A)-P (A∩B). (b) We deal a 5-card hand from a standard deck of 52 cards. Let B be the event that all cards are black, let S be the event that all cards are the same suit. (1) Is S ≤ B? Briefiy explain why or why not. (2) Briefly, using words, describe the event B - S in the context of this problem. Then compute its probability. 3.4. A manufacturer is trying to promote a brand of cereal. They create a set of m = 4 action figures and, for each box of cereal, they choose one of these action figures equally likely at random to put in the cereal box (exactly one action figure per box). If a parent buys n = 8 boxes of this cereal, compute the probability they have collected all 4 action figures. Hint: If we let Fi represent the event that you’ve collected action figure i (i = 1, 2, 3, 4), then F1 ∩ F2 ∩ F3 ∩ F4 is the event that you’ve collected all four. Use the fact that (F1 ∩ F2 ∩ F3 ∩ F4 )c = F1(c) U F2(c) U F3(c) ∩ F4(c) . 3.5. (a) A and B are mutually exclusive and P (A) = .2 and P (B) = .3. Compute P (AjA U B). (b) Re-do part (a) except now, A and B are not mutually exclusive but are independent, i.e., they have the property P (A ∩ B) = P (A)P (B). 3.6. Suppose we are told that 20% of college freshmen get homesick and 30% of college freshmen attend school more than 500 miles from home, and of the college freshmen that attend school more than 500 miles from home, 40% get homesick. (a) What percentage of freshmen are both homesick and attend school more than 500 miles from home? (b) Of the freshmen that get homesick, what percentage attend school more than 500 miles from home? (c) If a freshman is not homesick, what is the chance they attend school more than 500 miles from home? 3.7. I deal you 2 cards from a standard deck of 52. (a) Given they are both red, compute the probability they are different ranks. (b) Given they are different ranks, what’s the probability they are the same color? 3.8. 12 postal workers (9 females, 3 males) have applied for a promotion. Only two people get pro- moted and all 12 are equally qualified. Management decides to equally likely at random select two people from the 12 to be promoted. (a) If a female is promoted, compute the probability that a male is promoted. (b) If a male is promoted, compute the probability that a female is promoted. 3.9. A parent has 2 children. If we know (at least) one of them is a girl, what’s the probability the other is a girl? 3.10. A fair coin is tossed repeatedly. If the first head happened on an odd-numbered toss (i.e., toss #1,3,5,7,. . . etc.), what’s the chance the 2nd head also occurs on an odd-numbered toss? Hint: From a reduced sample space point of view, once we’re told that the first head happened on an odd-numbered trial, the coin flipping can be though of starting anew except now the first trail after this first head will be an even-numbered trial. 3.11. A computer generates a 5-digit code where each entry of the code is equally likely to be one of the 10 digits 0 thru 9 repetition allowed. If the code generated is nondecreasing order, what’s the probability it is missing the digit 5? 3.12. The multiplicative rule for conditional probability generalizes to many events, for example, P (A1 ∩ A2 ∩ A3 ) = P (A1 )P (A2 jA1 )P (A3 jA1 ∩ A2 ) and P (A1 ∩ A2 ∩ A3 ∩ A4 ) = P (A1 )P (A2 jA1 )P (A3 jA1 ∩ A2 )P (A4 jA1 ∩ A2 ∩ A3 ), etc. (a) Please verify these two rules that are written. (b) There are three boxes of marbles - call them box 1, 2 and 3. Box 1 initially has 2 blue and 1 green; Box 2 has 1 blue and 1 green; Box 3 has 0 blue and 1 green. The experiment is as follows: draw a marble at random from box 1, then put that marble into box 2; then draw a marble at random from box 2, and put that marble into box 3. Finally, draw a marble at random from box 3. Use one of the rules above to compute the probability that you select a blue marble at every stage of the experiment. h.13. Let A1 , A2, . . . , An be any events. Provide a proof by mathematical induction (on n) to show that h.14. Recall that in the matching problem we considered all n! orderings of the integers 1 thru n to be equally likely, and we let Mi be the event that there is a match at i. We showed the proba-bility that there no matches (i.e., a derangement) is Compute the probability that there is exactly one match. For example, the probability the one match is in position 1 is P (M1 only) = P (M1 M2(c)M3(c) · · · Mn(c)). h.15. 12 balls (5 red, 4 green, 3 yellow) are lined-up left to right. If no two green balls are adjacent, what’s the probability the no two yellows are adjacent?
Understanding Data and their Environment Assessment 1: provenance report Note: these assessment tasks are group tasks and will be marked based on asingle submission. Upload via blackboard: 1. PROV-N text file (as a .txt or .provn file) 2. Report with diagrams (as pdf) a. Remember to indicate your teamname (e.g. “Blue”) in the report and PROV! Your task is to formalise the provenance of your week 1-3 group work as PROV-N, from the point the group designed the survey questions, through to including the generation of the metadata schema. For added complexity you should also include the indicator task (even if your indicator did not use your own survey). Do not include the generation of the initial provenance graph in group exercise or this week 4 work. Note: For this task, you should focus on your group’s actual process as students, rather than the process that you were simulating. Part 1: PROV-N text file You will write a single PROV-N text file that include the statements you deem sufficient to describe the provenance of the data. As this is done after-the-fact, it does not have to be fully accurate, but it should aim to be representative. Consider modelling the provenance in this order: a. Responsibility view – which agents were attributed for which engagements? Were any external actors involved? (but: use Alice/Bob/Charlie-style placeholders instead of actual personal names within your group) b. Data flow view – how did the information move from one entity to another? Which pre- existing entities were sourced? Did any entities evolve overtime? c. Process view – which activities were performed that directly or indirectly led to the above entities? Include digital activities as well as essential non-digital activities. d. Add attributes for types, attributes, roles, plans. Name your own custom types and attributes, or explore schema.org (for instance http://schema.org/Dataset) and Dublin Core Terms ( http://purl.org/dc/terms/) Add the right prefix statements to provn! See References below. Think about the granularity you want to detail provenance in (e.g. scope of entities and activities, which relations to include). Try to make sure the provenance trace is internally consistent. You can justify your modelling decisions in the report; but in PROV-N try to showcase your knowledge and explore detail levels beyond the week 4 lab exercises. Avoid using personal information (it is not important to this assessment who did what in the group work, but it’s important to show that everyone contributed). You can use approximate date/time stamps, but make sure they are chronologically consistent. Try to make sure the prov-n is syntactically valid, however it is better to submit a more complete (but syntactically invalid) PROV-N file than an incomplete (but valid) file. Then try to programmatically generate a diagram from PROV-N, saved as SVG vector image or PNG bitmap image. You can use either the PROV ToolBox command line tool, the PROVStore web service, or both. Note that if you want to show the interactive diagrams, you may have to take a screenshot. Tip: The order of statements in prov-n does not matter, so if you get an error message without line message, use copy-paste and delete 50% of the lines (except the document... endDocument statements) until you hit the bug. (This is Newton’s method or binary search applied to debugging! https://en.wikipedia.org/wiki/Newton's_method). Note: The provconvert command line tool in PROV Toolbox gives more detailed error messages on validation but can be harder to install and use. The ProvStore service is hosted by KCL and may be shutdown by November 2024. Assessment: One member of team to upload a provn text file in Blackboard (see Submission Instructions below) NB: Include any diagrams in the report (see below) Part 2: Textual report Write a brief report (word limit: 500 excluding headings/captions), considering: 1. How did you decide which entities, activities and agents you needed? How did you decide on their identifiers and types? You can justify here any activities/entities/agents you did not include. 2. How would your provenance look different if you had modelled it instead for: a. lower granularity (simplified for wider audience) b. higher granularity (detailed for researchers interviewing same subjects) Indicate what you would add/remove/change, and what design decisions this would imply. 3. Did you find any part of writing provenance easy? What was most challenging? Reflect on any team disagreements on how to model the provenance. Tip: To include a high resolution diagram in the report you may need to convert it to SVG rather than PNG. Assessment: Upload report to Backboard, preferably as PDF (see below). How to collaborate on the assessed work? This assessed work is marked on a group-wide basis. You can use your Group room in Microsoft Teams to organise the work between you, try to split the tasks so all can contribute (e.g. split PROV-N tasks by view, split report writing by sections). You can share a Word document using OneDrive with the team to allow collaborative editing, rather then passing the baton. For Blackboard, remember to save the PROV-N file as a plaintext file, not Word document. Set internal deadlines for team-wide reviews and discussions, don’t let one person dominate even if they claim to understand the topic better. Make sure you have enough time for final editing so the PROV-N is consistent (e.g. identifiers are the same across views), the report is coherent and below word limit, and the updated diagrams are included.
TTTK2323 MOBILE DEVELOPMENT LEMMING REPORT SEMESTER 1 2024/2025 0.1 PROJECT DESCRIPTION Lemmings is an application designed for visitors to Malaysia from all over the world, which may include normal tourists, international students, travel bloggers and even religious people. Users can view the states or federal territories in Peninsular Malaysia, led by Kuala Lumpur, that contain tourist attractions, learn about tourist attractions and their DOS and don 'ts in advance, and users can even plan their routes in advance. We have included a link to grab for easy route planning. 1.0 INTRODUCTION Malaysia is a multi-racial country located in Southeast Asia. The former Union of Malaya, North Kalimantan (now Sabah), Sarawak and Singapore formed a federal, parliamentary democracy, elected monarchy and constitutional monarchy on 16 September 1963, after the state of Singapore was delisted from the Federation on 9 August 1965 and became an independent state. Malaysia has a total area of 330,803 square kilometers, which is divided into two parts by the South China Sea: the western half of the Malay Peninsula is divided into eleven states and two federal territories, Kuala Lumpur and Putrajaya, known as the "Malaysian Peninsula Area", which is connected with Singapore by the new Roh Causeway and the second channel; The eastern half is located in the north of the world's third largest island, Kalimantan Island, is divided into Sabah and Sarawak two states and the Federal territory of Labuan, known as "Kalimantan Island", the capital is located in Kuala Lumpur, Malaysia's most densely populated and most prosperous area, the federal government is located in Putrajaya. Malaysia's geographical location is close to the equator, its climate belongs to the Asian tropical rainforest climate, as of 2023, the population of the country is about 33.4 million. Thanks to the combination of natural attractions, cultural diversity, cosmopolitan Spaces and gastronomy. With an excellent natural environment and a large number of wildlife, Malaysia has become the first choice for many people to travel in Southeast Asia, so many people choose to travel to Malaysia and leave unforgettable memories here. For international students, Malaysia has become the first choice for many families to study abroad due to the excellent teaching quality, teacher resources and not very expensive tuition fees. But no matter what kind of people, after coming to Malaysia, they will be troubled by the way of travel and the arrangement of tourist attractions. As most of the local people drive for daily travel, the public transportation in Malaysia is not very developed, and the traffic restrictions cause many people to be unable to perfectly arrange their schedule and time during travel. It causes a lot of unnecessary extra expenses and wasted time. Therefore, we plan to make the Lemming software, which clearly lists the scenic spots in Western Malaysia, and filters the scenic spots according to whether users prefer natural scenery or human history. Users can click the scenic spot details page to learn about the scenic spots, get the ticket price range of each scenic spot and the weather conditions in recent days. At the same time, after understanding the relevant information, we will recommend the corresponding APP according to the travel mode chosen by the user. In this interface, the user can also get the relevant information about the surrounding facilities of the scenic spot (parking lot, restaurant, public toilet, etc.) and the precautions when visiting the scenic spot (for example, the dress of men and women entering the mosque). At the bottom end of the introduction, we have added a footprint function (marking places) to facilitate the user's next scenic spot search and travel track generation.
MSc Engineering and Education Module Guide 2024-25 for EDPS0249 Engineering and Education Report Overview and Aim of the Module All master’s-level students are required to submit a dissertation or a report at the end of their final year. Typically, dissertations and reports are long and in-depth pieces of work that offer a critical exploration of a subject matter relevant to a specific educational programme. To successfully complete these assignments students are required to conduct extensive and largely independent research involving the collection of primary data and/or comprehensive literature reviews. They should demonstrate abilities in research topic design, execution and presentation and a capacity for in-depth critical thinking in their chosen area of study. For the MSc Engineering and Education students , in particular, dissertations and reports represent an opportunity to develop their research skills and investigate a topic of interested in the field of engineering education. These pieces of academic writing are the culmination of the MSc Engineering and Education Programme, the students' chance to synthesise and use the knowledge gained during the year and demonstrate their expertise in this field with the view to launching the next stage of their career. Although dissertations and reports involve largely student-driven activities, a full package of support is offered to the MSc Engineering and Education students, including lectures and tutorials. In this regard, the EDPS0224 (Dissertation) and EDPS0249 (Report) modules aim to guide the students through all the steps needed to successfully complete a large-scale individual research project at master's level and help them develop all the necessary skills and capabilities required to prepare this substantial piece of work. EDPS0224 and EDPS0249 are coupled together in a single 'module' that runs across Terms 1, 2 and 3 with the view to assisting students during the different stages of the dissertation (EDPS0224) or report (EDPS0249) process. Furthermore, individual tailored support to each student is also provided through an allocated dissertation or report supervisor. This present guide provides an outline of the EDPS0249 (Report) module in terms of intended learning outcomes, content and structure, nature of assessments and indicative reading. It also offers guidance regarding the expected report timeline and details the support available to students. Further information can be found on the module's Moodle page. 2 What is a Report? Dissertations and reports are an opportunity for a critical examination of a topic of direct interest to Engineering and Education students. The number of credits assigned to the module, the word length of the assignment and the scope of the study are the major differences between dissertations and reports. As illustrated in Table 1, the Report module is worth 30 credits of the 180 credit MSc degree. The main output of this module is a written report with a word limit of 10,000 words, plus 10% (i.e., 11,000 words maximum), excluding references and appendices. Compared with a dissertation, a report represents a more focused and narrowly-defined study of a topic relevant to engineering education. It is anticipated that this investigation can be based either on: A. A comprehensive analysis of the existing literature on a specific topic relevant to engineering education; or B. A comprehensive literature review supplemented with a limited amount of primary data collection. The choice between type A and type B reports will be dictated by the specific students’ inclinations and needs, and the research topic under investigation, and will be taken by the students after discussion with their supervisors. Table 1 - Main differences between dissertations and reports. Dissertation Report An in-depth investigation of a research topic (relevant to engineering education) aimed at addressing a specific research question through the gathering and analysis of both primary data and literature sources An exploration of a narrowly defined research topic based on: a) A review of the literature; or b) A review of the literature supplemented with a limited amount of primary data collection. 60 credits 30 credits 20,000 words, plus 10% (i.e., 22,000 words maximum). 10,000 words, plus 10% (i.e., 11,000 words maximum). Starting Point: Identification of a research gap (i.e., an area of study that has not been fully addressed or answered by previous studies), and/or an area of conflict or controversy. Starting point: a) A clear rationale for conducting a literature review on a specific topic; or b) Identification of a research gap, and/or an area of conflict or controversy. Aim: to generate new knowledge on a topic (relevant to engineering education). Aim: a) To examine and present the state of the art of the literature on a topic (relevant to engineering education); or b) To generate some new knowledge on a topic (relevant to engineering education). Data needed: primary data and literature sources. Data needed: a) Literature review only; or b) Literature review and a small amount of primary data. Ethics application: an ethics application, which includes participant information sheets and/or consent forms, is required. Ethics application: a) A short ethics application is required; or b) An ethics application supplemented with participant information sheets and/or consent forms is required. Students need to be aware that type A and type B reports have different features and expectations. In particular, type A reports (i.e., reports based on comprehensive literature reviews) are expected to offer: ● An identification of a research topic of particular interest (which must be relevant to engineering education) based on the student's reflections on the wide range of themes covered in the other taught modules, and discussions with their supervisor and other members of the MSc Engineering and Education team. ● A thorough examination of what is already known about a problem or issue through a comprehensive literature review, which must make use of teaching materials and literature sources provided as part of the MSc Engineering and Education Programme. ● A critical discussion of the literature review findings where strengths and weaknesses of previous studies are exposed, different authors' views are compared and perhaps combined with the view to developing new theoretical frames and generating new ways for understanding a particular problem, and research gaps and under- researched areas are highlighted so as to pave the way for further primary research studies. By comparison, key features and expectations of type B reports (i.e., reports based on the analysis of primary data and literature sources) include: ● An identification of a research topic of particular interest (which must be relevant to engineering education) based on the student's reflections on the wide range of themes covered in the other taught modules , and discussions with the supervisor and other members of the MSc Engineering and Education team. ● An examination of what is already known about a problem or issue through a rather synthetic and focused literature review, which must make use of teaching materials and literature sources provided as part of the MSc Engineering and Education Programme. ● The recognition of a very specific and a narrowly-defined research gap that warrants further investigation through primary research studies. ● The collection of (a limited amount of) primary data about that problem or issue through fieldwork and data collection methods such as interviews and surveys with the view to generating new knowledge about the chosen topic. ● Appropriate consideration of research ethics and data protection issues arising from research and primary data collection activities. ● The analysis and discussion of the research findings as well as the exploration of some new (or partially new) ideas about a problem or issue that can potentially have some important implications for policy, practice and/or future research. 3 Learning Outcomes Reports are student-driven exercises that should draw from and allow students to reflect on the range of subject-matters covered in the taught modules. The purpose of undertaking a report is to enable the students to apply the knowledge and skills acquired from their broader programme to an investigation of a narrowly defined topic, thereby demonstrating a capability to apply theory to the analysis of a topic and demonstrating the capacity to design and execute an appropriate programme of research. More specifically, with the report students should convey the ability to: 1. Identify a topic for original research. 2. Establish and address clearly focused and fundamental research questions. 3. Critically analyse relevant theory and literature. 4. Supplement the literature review by gathering and analysing relevant primary research data and information, thus making an original contribution to the field (only for type B reports). 5. Conduct research independently and in a reflective manner, with suitable consideration of ethical issues and data protection requirements (especially for type B reports). 6. Write clearly and concisely in a manner that logically presents research findings and evidence, and draws clear research conclusions and insight. 4 Teaching and Learning Methods The overall package of support provided for dissertations and reports include a series of lectures and practical workshops, as well as some tutorials with the supervisors. EDPS0224 and EDPS0249 run together across the three terms of the academic year to guide students progressively through the different stages of the dissertation and report process. EDPS0224 and EDPS0249 comprise 11 sessions, which examine the key elements of a research project (i.e., research topic and aim, literature review, research methodology and ethics, data collection and analysis methods, presentation of research findings). The sessions will be delivered in class and all lecture notes and teaching material will be uploaded to the module's Moodle page. In addition to these compulsory and optional sessions throughout Terms 1, 2 and 3, students will be also allocated a supervisor in Term 2. Ideally, this allocation will be based on the preliminary research topic chosen by the students and the research interests of the supervisors. Supervisors can offer up to four hours of supervision for reports, usually over the second and third term of the year. This may combine group and individual tutorials, which can take place in person or online, and email support. Individual reading and independent research are an essential and substantial component of the Report module. The total workload to complete the report (including lectures, workshops and tutorials, student-driven reading and research; data collection and analysis, and report writing and editing) is about 300 hours (1 Credit = 10 notional learning hours).
