This introductory assignment is designed to familiarize you with the mechanics of creating, compiling, and running Java applications. You may use the IDE of your choice to build and run these programs. Make sure you add the required documentation box to the top of each as described in the Java Documentation and Coding Guidelines in Blackboard’s Course Documents. Once you are finished, submit two .java files named Add1.java and Add2.java on Blackboard by the due date and time. Be sure you do not submit files of the same names but with extensions .class. Also be sure you do not submit files ending with a tilde (~). This indicates that it is a temporary version of the file, i.e., it is open for editing. If you choose to use Intellij IDEA as your development environment, here is a link to a simple tutorial to get you started with this assignment:https://www.jetbrains.com/help/idea/creating-and-running-your-first-java-application.html Part 1: Compile and Run a Java Console Program Type in (or copy and paste) the program listed below and save it as Add1.java. The file name is case-sensitive and must match the class name in the program below. import java.util.Scanner; /** Add1.java** Console program to add two numbers.*/ public class Add1 { public static void main(String[] args) { String amountStr;double num1, num2; Scanner sc = new Scanner(System.in); // Read the first number as a String.System.out.println(“Enter the first number: “);amountStr = sc.next(); // Try to convert String to double for calculation.try { num1 = Double.parseDouble(amountStr);}catch (NumberFormatException nfe) { System.out.println(“1st number invalid.”);return;} // Read the second number as a String.System.out.println(“Enter the second number: “);amountStr = sc.next(); // Try to convert String to double for calculation.try { num2 = Double.parseDouble(amountStr);}catch (NumberFormatException nfe) { System.out.println(“2nd number invalid.”);return;} // Compute and print the sum.System.out.printf(“Sum is: %.2f ”, num1 + num2);}} Part 2: Build and Run a Java Swing GUI Program Type in (or copy and paste) the following program, and then build and run it. import javax.swing.*;import java.awt.*;import java.awt.event.ActionEvent;import java.awt.event.ActionListener; /** Add2** Swing program to find the sum of two numbers.*/ public class Add2 extends JFrame implements ActionListener { private static final long serialVersionUID = 1L; private JButton addButton = new JButton(“Add Numbers”);private JButton clearButton = new JButton(“Clear Numbers”);private JTextField num1Field = new JTextField(10);private JTextField num2Field = new JTextField(10);private JLabel sumLabel = new JLabel(); public static void main(String[] args) { EventQueue.invokeLater(() -> { Add2 frame = new Add2(“Sum of Two Numbers”);frame.createAndShowGUI();});} private Add2(String title) { super(title);} /** Create the GUI and show it. For thread safety, this method should* be invoked from the event-dispatch thread.*/ private void createAndShowGUI() { initComponents(); // Add listeners for the buttons.addButton.addActionListener(this);clearButton.addActionListener(this); // Display the window.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);pack();setVisible(true);} /** Set the frame’s layout, create the UI components, and add them to the* layout.*/ private void initComponents() { JPanel panel = new JPanel(new GridLayout(4, 2, 5, 5));panel.setBorder(BorderFactory.createEmptyBorder(10, 10, 10, 10)); panel.add(new JLabel(“First number:”));panel.add(num1Field);panel.add(new JLabel(“Second number:”));panel.add(num2Field);panel.add(new JLabel(“Sum:”));panel.add(sumLabel);panel.add(addButton);panel.add(clearButton); add(panel, BorderLayout.CENTER);} /** Handle ActionEvents from the buttons.*/ @Overridepublic void actionPerformed(ActionEvent e) { double num1, num2; if (e.getSource() == clearButton) { num1Field.setText(“”);num2Field.setText(“”);sumLabel.setText(“”);}else { // Try to convert String to double for calculationtry { num1 = Double.parseDouble(num1Field.getText());}catch (NumberFormatException nfe) { sumLabel.setText(“1st number invalid.”);return;} // Try to convert String to double for calculationtry { num2 = Double.parseDouble(num2Field.getText());}catch (NumberFormatException nfe) { sumLabel.setText(“2nd number invalid.”);return;} // Compute and display the sum.sumLabel.setText(String.format(“%.2f”, num1 + num2));}}}
The purpose of this assignment is to work with directed graphs. You’ll implement a class that allows a user to query various info about a graph, which also implements several of the graph algorithms discussed in class.You are responsible for implementing all of the following functions:– In `graph.h`, you will implement all of the methods of the `Graph` class: – `nvertices()` – `nedges()` – `v_label(vertex)` – `v_index(label)` – `assign(vertices, edges)` – `edge_exists(origin, destination)` – `edge_weight(origin, destination)` – `undirected_adjacency_list(vertex)` – `in_adjacency_list(vertex)` – `out_adjacency_list(vertex)` – `weighted_adjacency_matrix()` – `unweighted_adjacency_matrix()` – `depth_first(start, visitfn, connected_only)` – `breadth_first(start, visitfn, connected_only)` – `toposort()` – `dijkstra(start)`### Some Provided Types#### In `graph.decl.h`The `GraphEdge` data structure is used to store the info needed for the edges that are used to construct your `Graph`.~~~~~ {.cpp} struct GraphEdge { size_t origin; // index of vertex the edge starts from size_t destination; // index of vertex the edge goes to double weight; // the weight/cost associated with this edge }; ~~~~~The `AdjListEdge` is used to store data on edges in your adjacency lists.~~~~~ {.cpp} struct AdjListEdge { size_t vertex; // the index of the vertex on the other side of the edge double weight; // the weight/cost associated with this edge }; ~~~~~Your implementation of Dijkstra’s shortest path algorithm will return a `std::vector` of `dijkstra_row`, which will contain the info on shortest paths to every vertex from the source vertex you passed to the algorithm.~~~~~ {.cpp} struct dijkstra_row { size_t vertex; // the index of the vertex for this row bool visited; // whether the vertex has been visited double shortest_known; // distance of shortest known path to this vertex ssize_t came_from; // the index of the vertex we came from for shortest known path, or -1 if N/A }; ~~~~~#### In `config.h`If you want to store the graph data in a more convenient/efficient format than the edge list that is used to construct it, you are free to do so. Any additional data members that you’d like your `Graph` to contain can be added to the `StudentExtra` struct in `config.h`. It is currently empty, and its use is not required, but it is available if you want it. Any members you add to the `StudentExtra` can be accessed through the `student` member of the `Graph`.### The Methods of `Graph` #### `nvertices()` Returns the number of vertices in the graph stored.#### `nedges()` Returns the number of edges in the graph stored.#### `v_label(vertex)` – `vertex` – a `size_t` representing the index of the vertex to look up.Retuns the string label for the vertex index passed in.#### `v_index(label)`– `label` – the `string` label of the vertex whose index you would like.Returns the `size_t` index of the vertex whose label matches `label`.#### `assign(vertices, edges)`– `vertices` – a `std::vector` of strings containing labels for the vertices in the graph. – `edges` – a `std::vector` containing a `GraphEdge` for each edge in the graph.Removes any data currently stored in the `Graph`, and replaces it with the graph described by the vertex vector, `vertices`, and edge list vector, `edges`, passed in.If you are using the `StudentExtra` structure to store the graph in another format, this is where you would handle that conversion.Returns nothing.#### `edge_exists(origin, destination)`– `origin` – the index of the vertex the edge starts from – `destination` – the index of the vertex the edge goes toReturns `true` if an edge exists going from `origin` to `destination`. Returns `false` if not.#### `edge_weight(origin, destination)` – `origin` – the index of the vertex the edge starts from – `destination` – the index of the vertex the edge goes toIf an edge exists going from `origin` to `destination`, return its weight/cost. Otherwise return `INFINITY`.#### `undirected_adjacency_list(vertex)`– `vertex` – the index of the vertex whose adjacency list we want.Returns a `std::vector` containing an `AdjListEdge` for each edge that starts or ends at the vertex with the index passed in.#### `in_adjacency_list(vertex)`– `vertex` – the index of the vertex whose adjacency list we want.Returns a `std::vector` containing an `AdjListEdge` for each edge that ends at the vertex with the index passed in.#### `out_adjacency_list(vertex)`– `vertex` – the index of the vertex whose adjacency list we want.Returns a `std::vector` containing an `AdjListEdge` for each edge that starts at the vertex with the index passed in.#### `weighted_adjacency_matrix()`Returns a `std::vector` that contains the weighted adjacency list in row major order. Each row represents the corresponding starting vertex, and each column represents the corresponding ending vertex.If there is an edge going from the starting vertex to the ending vertex, the value of that entry will be the weight/cost of that edge. If not, the value should be `INFINITY` (**NOT** zero).#### `unweighted_adjacency_matrix()`Returns a `std::vector` that contains the unweighted adjacency list in row major order. Each row represents the corresponding starting vertex, and each column represents the corresponding ending vertex.If there is an edge going from the starting vertex to the ending vertex, the value of that entry will be `true`. If not, the value should be `false`.#### `depth_first(start, visitfn, connected_only)`– `start` – index of the vertex to start the traversal from – `visitfn` – the function (or function-like object) to call when visiting – `connected_only` – controls whether vertices to which not path from the `start` vertex exists are traversed separately.Performs a depth first traversal of the graph starting from the vertex whose index is passed in as `start`. When visiting, the `visitfn` will be called on the index of the vertex visited.When choosing which of the unvisited adjacency vertices to do next, choose them in ascending order of the vertex index numbers.If `connected_only` is `true`, only start the traversal from the starting vertex.If `connected_only` is `false`, also traverse the graph from any remaining non-visited vertices, that may have been missed because there was no path to them from the original starting vertex.#### `breadth_first(start, visitfn, connected_only)`– `start` – index of the vertex to start the traversal from – `visitfn` – the function (or function-like object) to call when visiting – `connected_only` – controls whether vertices to which not path from the `start` vertex exists are traversed separately.Performs a breadth first traversal of the graph starting from the vertex whose index is passed in as `start`. When visiting, the `visitfn` will be called on the index of the vertex visited.When choosing which of the unvisited adjacency vertices to do next, choose them in ascending order of the vertex index numbers.If `connected_only` is `true`, only start the traversal from the starting vertex.If `connected_only` is `false`, also traverse the graph from any remaining non-visited vertices, that may have been missed because there was no path to them from the original starting vertex.#### `toposort()`Performs the Topological Sort algorithm on the graph. Returns a `std::vector` containing the index of each vertex in the order determined by the algorithm.If a cycle is found. Stop early and return only the vertices whose order was determined before the cycle. The caller can determine whether a cycle stopped the algorithm early by comparing the length of the vector returned to the number of vertices in the graph.When ther are multiple choices for the next vertex, choose the one with the lowest vertex index first.#### `dijkstra(start)`– `start` – the index of the source vertex, from which all of the shortest paths will be found.Use Dijkstra’s Shortest Path algorithm to find the shortest path to every vertex from the source vertex whose index is passed in as `start`.When there are multiple unvisited vertices to choose as the next one (same minimal shortest known path distance), choose the one with the lowest index first.This will return the table used by the algorithm in its final state, as a `std::vector` containing a `dijkstra_row` for every vertex in the graph.Remember that Dijkstra’s algorithm is not guaranteed to (and likely will not) work if any of the edges have a negative weight. If any of the edges in your graph have a negative weight, print…`”Error: Dijkstra’s algorithm does not support graphs with negative edge weights. ”`… and return an empty vector.### NotesRemember to continue with our routine of creating a `development` branch and making all changes to that branch, leaving `main` entirely alone. This will be necessary to submit the pull request at the end, signaling completion of your program to the graders.Your work should be done in `graph.h` and `config.h`. Do not alter the other files that were provided with the assignment.You should feel free to create whatever files you want to test things locally, including writing your own simple programs to test small parts on their own, but none of them should end up becoming a part of your remote repo. I actually *encourage* you to write unit test programs for yourself, but they should not be a part of your submission.**DO NOT ADD OR COMMIT THE EXECUTABLE FILES CREATED WHILE COMPILING.** They are big and we will be compiling anyway.### TestingThere are only two testing programs included. These will be used to evaluate the functionality of your implementations of the required functions. Typing `make` will attempt to compile them all, and will succeed to the degree it can with whatever you have implemented at that point.The table below has a list of the tests available, and they are shown in order from least complex to most complex.|Order|Test |Purpose | |:-: |:—-|:——————–| 1|`simple` |Tests the most basic graph functions with known data. 2|`loadgraph` |Allows you to test the rest of your functions with data loaded in from a file. Loads from a default file if no filename is passed as a command line argument.The expected output is contained in the `*.refout` files in the `output/` directory.### How To SubmitLike the other assignments for this semester, we will be doing submissions through GitHub. Make sure you do all of your development in the `development` branch. You can commit as many times as you need to, but keep in mind that this will grow the size of your repo and you may run up against the quota on turing/hopper if it gets too big.When you are finished implementing everything required and the test program is working properly, make sure you add, commit, and push the working version to the repo. Once that is done, **SUBMIT** a pull request but **DO NOT ACCEPT IT**.### Grading Considerations– Does it compile? Does it run? All of the tests should compile and run on turing/hopper with the `Makefile` provided, and points will be deducted for each test that will not compile. – Does the output match for all of the tests? I have provided reference output for each of the test programs, so you can compare your program’s output to what is expected. This output can be found in the files ending in `.refout`. – Did you change files you’re not allowed to? There are warning messages at the top of several of the files telling you not to make changes. If you make changes to these, you will receive a grade penalty. You can write your own test programs if you’d like, but do not commit them or push them to the server, and make sure the only modifications that make it to GitHub are the required ones. – Did you commit/push all of the source code needed to compile your program? – Did you indent your code? – Indentation aids in the readability of source code, and if you’re not indenting your code blocks, the grader will legitimately dislike you for it. I’m authorizing them to mark you off if you subject them to reading that. – Did you document your code? – You need a docbox at the top of every one of the files you’re required to change including: – Your name – Your zid – Your GitHub ID – Your course section – A description of what the program does – You should add a docbox for every function that you implement, explaining what it does and what each parameter is for. – Add other comments inside your code blocks describing what you’re doing and why. – The use of `doxygen` style comments is encouraged, but not required.
The purpose of this assignment is to have you implement the heap data structure. You will also implement a priority queue class using that heap implementation, which will work like the STL priority queueYou are responsible for implementing all of the following functions:– For heap functionality (in `heap.h`): – `heap_left(node)` – `heap_right(node)` – `heap_parent(node)` – `heap_preorder` – `heap_inorder` – `heap_postorder` – `heap_levelorder` – `is_heap` – `heap_bubble_up` – `heap_bubble_down` – `heap_insert` – `heap_extract` – `heapify_in_place_up` – `heapify_in_place_down` – `heap_sort`– For the `heap_priority_queue` class (in `heap_priority_queue.h`): – Constructor `heap_priority_queue(ITERATOR, ITERATOR)` – `top()` – `empty()` – `size()` – `push()` – `pop()`### HeapsAs a quick review, a heap is a type of tree that is useful for quickly finding the “best” thing according to some criterion, called the heap criterion.The heap we are using is a complete binary tree, filled from the left. Instead of using the pointer-based nodes that we had used for other trees, we will be storing the heap into an array by mapping the nodes in the tree to an element in the array based on level order.Placing items in the heap involves the “King of the Hill” method discussed in class. For minheaps, smaller values must be above lower values. For maxheaps, the greater values must be on top.When comparison functions are used in the functions below, they are used to compare two values (parent value is the left hand side, child value is the right hand side) and return `true` if the parent value and the child value conform to the heap criterion for the heap we are using.Thus, less than, `parent < child` would be used for minheaps, and greater than, `parent > child` would be used for maxheaps.### The Heap Functionality (in `heap.h`):#### `heap_left(node)`– `node` – index of the node whose left child’s index we’d likeThis function returns the index in the heap that would contain the left child of node `node`.#### `heap_right(node)`– `node` – index of the node whose right child’s index we’d likeThis function returns the index in the heap that would contain the right child of node `node`.#### `heap_parent(node)`– `node` – index of the node whose right child’s index we’d likeThis function returns the index in the heap that would contain the parent of node `node`, unless `node` is already the root, in which case it returns `0`.#### `heap_preorder(heapdata, heapnodes, nodes, fn)` – `heapdata` – The array-like object containing the heap data – `heapnodes` – The number of nodes in the heap – `node` – Index of the node in the heap that is the root of the subtree to traverse. – `fn` – The function to call when visiting.Traverses, preorder, the subtree of the binary tree represented by the heap array that has `node` as its root, calling `fn` on each element. Returns nothing.#### `heap_inorder(heapdata, heapnodes, nodes, fn)` – `heapdata` – The array-like object containing the heap data – `heapnodes` – The number of nodes in the heap – `node` – Index of the node in the heap that is the root of the subtree to traverse. – `fn` – The function to call when visiting.Traverses, inorder, the subtree of the binary tree represented by the heap array that has `node` as its root, calling `fn` on each element. Returns nothing.#### `heap_postorder(heapdata, heapnodes, nodes, fn)` – `heapdata` – The array-like object containing the heap data – `heapnodes` – The number of nodes in the heap – `node` – Index of the node in the heap that is the root of the subtree to traverse. – `fn` – The function to call when visiting.Traverses, postorder, the subtree of the binary tree represented by the heap array that has `node` as its root, calling `fn` on each element. Returns nothing.#### `heap_levelorder(heapdata, heapnodes, fn)` – `heapdata` – The array-like object containing the heap data – `heapnodes` – The number of nodes in the heap – `fn` – The function to call when visiting.Visits each of the nodes in the heap in level order, calling `fn` to visit. Returns nothing.#### `is_heap(heapdata, nodes, compare)` – `heapdata` – The array-like object containing the heap data – `nodes` – The number of nodes in the heapReturns `true` if, and only if, the heap condition remains true for every node in the given heap. Depending on your implementation, you might get a different answer when there are nodes in a heap with the same key, but duplicates will not be tested for grading, so you don’t need to worry about that.#### `heap_bubble_up(begin, nodes, start, compare)` – `begin` – Beginning of random access iterator range containing the tree data. – `end` – Random access iterator one past the last element in the iterator range. – `start` – Index of the node to start bubbling up from. – `compare` – The comparison function to be used when deciding whether to swap.This performs the heap bubble up procedure on the given heap starting from the element. `start`, as would be needed, for example, when inserting a new node into the heap. Returns the number of swaps that had to be performed.#### `heap_bubble_down(begin, nodes, start, compare)` – `begin` – Beginning of random access iterator range containing the tree data. – `end` – Random access iterator one past the last element in the iterator range. – `start` – Index of the node to start bubbling down from. – `compare` – The comparison function to be used when deciding whether to swap.This performs the heap bubble down procedure on the given heap starting from the element. `start`, as would be needed, for example, when moving the number that was swapped with the root during the root extraction procedure.#### `heap_insert(heapdata, nodes, key, compare)` – `heapdata` – The STL container, supporting random access, that contains the data for the heap. – `nodes` – A **reference** to the `size_t` passed in containing the number of nodes in the heap. You will need to report the changes back to the caller by changing the value stored in this. – `key` – The key to insert into the heap. – `compare` – The comparison function to use.Performs the heap insertion procedure, inserting `key` into the heap of `nodes` nodes stored in `heapdata`. You can assume that the data is a heap before you start, and must ensure that the data is a heap again by the time you finish. Returns nothing. Make sure to change the `size_t` value referenced by nodes in order to report that the additional node was added.If there is not enough room in the container to add another key, you are responsible for resizing the container to make that room.#### `heap_extract(heapdata, nodes, compare)` – `heapdata` – The STL container, supporting random access, that contains the data for the heap. – `nodes` – A **reference** to the `size_t` passed in containing the number of nodes in the heap. You will need to report the changes back to the caller by changing the value stored in this. – `compare` – The comparison function to use.Removes the key stored at the root of the heap and returns its value. You can assume that the data contains a heap when you start, and you are responsible for ensuring that the data is still a heap once you’ve removed the node.#### `heapify_in_place_up(begin, end, compare)` – `begin` – Random access iterator representing the beginning of the data to heapify. – `end` – Random access iterator one past the end of the data that will be heapified. – `compare` – The comparison function to be used when deciding whether swaps must occur.This function takes the data in the given, random access iterator range, which may not yet be a heap, and heapifies it *in place*, by bubbling up nodes as new values are inserted. You are not allowed to use another array/`vector`/etc. to store things as you do this. Returns the number of swaps that had to be performed.#### `heapify_in_place_down(begin, end, compare)` – `begin` – Random access iterator representing the beginning of the data to heapify. – `end` – Random access iterator one past the end of the data that will be heapified. – `compare` – The comparison function to be used when deciding whether swaps must occur.This function takes the data in the given, random access iterator range, which may not yet be a heap, and heapifies it *in place*, by bubbling *down* for all of the nodes that have children. You are not allowed to use another array/`vector`/etc. to store things as you do this. Returns the number of swaps that had to be performed.#### `heap_sort(begin, end, compare)` – `begin` – Random access iterator representing the beginning of the data to sort. – `end` – Random access iterator one past the end of the data that will be sorted. – `compare` – The comparison function to be used when deciding whether swaps must occur.This function sorts the data in the given, random access iterator range using the heapsort algorithm. You should heapify in place using the `compare` function as your heap condition, and then extract the root. What remains in the array after all the nodes have been extracted will be sorted.You should choose the heapification algorithm that tends to require fewer swaps when you implement this.Returns nothing.**NOTE** Your tree is built using `compare` as the heap condition, and when it is unrolled, it will be in the opposite order of the order you would expect using the `compare` function directly in the `std::sort` algorithm. This means that heapsorting with a minheap gives you the items in descending order, and using a maxheap would give you the items in ascending order in the end.### The `heap_priority_queue` class (in `heap_priority_queue.h`: #### Constructor `heap_priority_queue(ITERATOR, ITERATOR)`This constucts your new `heap_priority_queue` with the the elements contained in the range specified with the two iterators already present, in a proper heap.You should choose the heapification algorithm that tends to require fewer swaps when you implement this.#### `top()`This returns a reference to the element at the top of the heap. As was also the case in `std::priority_queue`, this should never be called on an empty heap. Thus, you can assume that it never will be, and don’t need to worry about what would happen if it were, as that would be *undefined behavior*.#### `empty()`Returns `true` if, and only if, the heap is currently empty.#### `size()`Returns the number of nodes currently in the heap.#### `push(x)`Inserts the given key, `x`, into the heap.#### `pop()`Removes the value currently at the top of the heap from the heap. Returns nothing. This should never be called on an empty heap, so you don’t need to plan around that happening. Just like `std::priority_queue`, popping when empty is *undefined behavior*.### NotesRemember to continue with our routine of creating a `development` branch and making all changes to that branch, leaving `main` entirely alone. This will be necessary to submit the pull request at the end, signaling completion of your program to the graders.Your work should be done in `heap.h` and `heap_priority_queue.h`. Do not alter the other files that were provided with the assignment.You should feel free to create whatever files you want to test things locally, including writing your own simple programs to test small parts on their own, but none of them should end up becoming a part of your remote repo. I actually *encourage* you to write unit test programs for yourself, but they should not be a part of your submission.**DO NOT ADD OR COMMIT THE EXECUTABLE FILES CREATED WHILE COMPILING.** They are big and we will be compiling anyway.### TestingThere are a number of testing programs included. These will be used to evaluate the functionality of your implementations of the required functions. Typing `make` will attempt to compile them all, and will succeed to the degree it can with whatever you have implemented at that point.The table below has a list of the tests available, and they are shown in order from least complex to most complex.|Order|Test |Purpose | |:-: |:—-|:——————–| 1|`1-basic` |Tests the most basic heap functions with known data. 2|`2-bubble` |Allows you to test your `heap_bubble_up` and `heap_bubble_down` implementations. 3|`3-insdel` |Tests `heap_insert` and `heap_exract` 4|`4-heapify` |Tests `heapify_in_place_up` and `heapify_in_place` down. 5|`5-heapsort` |Tests your `heap_sort` implementation. 6|`6-pq` |Tests your `heap_priority_queue` implementation.The expected output is contained in the `*.refout` files in the `output/` directory.### How To SubmitLike the other assignments for this semester, we will be doing submissions through GitHub. Make sure you do all of your development in the `development` branch. You can commit as many times as you need to, but keep in mind that this will grow the size of your repo and you may run up against the quota on turing/hopper if it gets too big.When you are finished implementing everything required and the test program is working properly, make sure you add, commit, and push the working version to the repo. Once that is done, **SUBMIT** a pull request but **DO NOT ACCEPT IT**.### Grading Considerations– Does it compile? Does it run? All of the tests should compile and run on turing/hopper with the `Makefile` provided, and points will be deducted for each test that will not compile. – Does the output match for all of the tests? I have provided reference output for each of the test programs, so you can compare your program’s output to what is expected. This output can be found in the files ending in `.refout`. – Did you change files you’re not allowed to? There are warning messages at the top of several of the files telling you not to make changes. If you make changes to these, you will receive a grade penalty. You can write your own test programs if you’d like, but do not commit them or push them to the server, and make sure the only modifications that make it to GitHub are the required ones. – Did you commit/push all of the source code needed to compile your program? – Did you indent your code? – Indentation aids in the readability of source code, and if you’re not indenting your code blocks, the grader will legitimately dislike you for it. I’m authorizing them to mark you off if you subject them to reading that. – Did you document your code? – You need a docbox at the top of every one of the files you’re required to change including: – Your name – Your zid – Your GitHub ID – Your course section – A description of what the program does – You should add a docbox for every function that you implement, explaining what it does and what each parameter is for. – Add other comments inside your code blocks describing what you’re doing and why. – The use of `doxygen` style comments is encouraged, but not required.
The purpose of this assignment is for you to add AVL support to the binary search tree from the previous assignment, and create an STL-style container, `avl_set`, that uses your AVL tree to act like `std::set`.– You will need to add to your `bst.h`): – `predecessor(node)`– In `avltree.h`, you will implement: – `is_avl(root)` – `rotate_left(pivot)` – `rotate_right(pivot)` – `fix_avl_tree(root, node)`– In `avl_set.h`, you will need to implement all of the methods in `avl_iterator` and `avl_set` classes for which implementations were not already provided.### Reused FunctionalityYou were to implement all of the below functions in the previous assignment. If you finished, great. You should use your solution from the previous assignment. If you did not finish them, you’re responsible for finishing them now.– For general binary tree functionality (in `bintree.h`). – `preorder(root, fn)` – `inorder(root, fn)` – `postorder(root, fn)` – `levelorder(root, fn)` – `delete_tree(root)` – `height(node)` – `count(root)`– For dealing with binary search trees (in `bst.h`): – `bst_find(root, value)` – `bst_insert(root, value)` – `bst_remove_value(root, value)` – `is_bst(root)` – `bst_minimum(root)` – `bst_maximum(root)` – `successor(node)`### AVL Binary Search TreesAVL Trees are a type of dynamically self-balancing binary search tree. They have to follow all of the rules that normal binary search trees, *and* they have an additional rule that the height of the left subtree and the height of the right subtree may differ by at most one in every node of the tree. Forcing this rule to be followed will keep the tree balanced, which has performance benefits.Insertions and deletions are performed in the same way they would be done in a BST, but whenever you add or remove a node, there’s a potential of breaking the height constraint. Your `fix_avl_tree` function is responsible for fixing those problems and ensuring that the tree remains AVL.### Functions you ImplementRemember, you will be including the files you had from your previous assignment. If you still need to implement one of those functions, check out *that* assignment’s `README`.#### `predecessor(node)` – `node` – a pointer to the node in the binary search tree whose successor we would like to find.**NOTE:** This will work like the `successor` function that you wrote in the previous assignment, but in the opposite direction.This function must return a pointer to the node in the binary search tree that would be the *inorder predecessor* to the supplied node, `node`. If the node has no predecessor, then return `nullptr`. Remember that the inorder predecessor is the node that would have been visited *previous* to the current node in an inorder traversal. In a binary search tree, this will be found in the node with the greatest value that is less than the current node’s value. If called on binary tree that is *not* a BST, do not expect the values to come out sorted, but iterating over the predecessors is like doing an inorder traversal in reverse.#### `is_avl(root)` – `root` – A pointer to the root of the tree that’s being checked.This function will return true if and only if the AVL tree’s balance condition is true for every node in the tree whose root is pointed to by `root`.This is independent from the check for whether it’s a BST or not. Only do the AVL check based on heights, and don’t worry about the values of the nodes themselves in this function.#### `rotate_left(pivot)` – `pivot` – a *reference* to the pointer to the pivot node that the rotation goes through.This function is responsible for performing the left rotation as discussed during the lecture. No new nodes are created, and the values stay the same, but you will be changing the pointers of the nodes involved to reshape the tree. Make sure you remember to change the `parent` pointers as well.**NOTE:** `pivot` is a **reference** to a pointer, and you need to make sure that it is actually referencing either the pointer holding the root of the tree, or the `left` or `right` pointer of the pivot node’s parent, and not just a copy of the address. If you ignore this, you will have a lot of issues with your tree ending up wrong.Returns nothing.#### `rotate_right(pivot)` – `pivot` – a *reference* to the pointer to the pivot node that the rotation goes through.This function is responsible for performing the right rotation as discussed during the lecture. No new nodes are created, and the values stay the same, but you will be changing the pointers of the nodes involved to reshape the tree. Make sure you remember to change the `parent` pointers as well.**NOTE:** `pivot` is a **reference** to a pointer, and you need to make sure that it is actually referencing either the pointer holding the root of the tree, or the `left` or `right` pointer of the pivot node’s parent, and not just a copy of the address. If you ignore this, you will have a lot of issues with your tree ending up wrong.Returns nothing.#### `fix_avl_tree(root, node)` – `root` – **REFERENCE** to pointer to the root of the BST – `node` – pointer to the node where fixing should begin.Start out at `node` and make sure that the AVL balance condition is not being broken. If it is, perform the rotations necessary to reshape the tree to fix the problem as discussed in this lecture. Whether you fix anything at the current node or not, proceed to each of its parents and do the same thing, all the way to the root.This algorithm is not difficult, but you will need to remember that `root` is a reference, and needs to be a reference to the actual pointer for the root of the tree, in case a rotation moves another node up to replace the root.Returns the number of nodes in which a violation of the AVL balance criterion was detected and fixed.### `class avl_set`This class will be used to implement a version of the STL `set` container that works based on your AVL trees.– The template parameter `T` will be the type of data contained by the nodes. – `root` is a pointer to the root of the AVL tree you’re using to contain your data. – `node_count` is used to track the number of elements currently in your AVL tree set. Thus, you can implement `size()` as an $O(1)$ operation instead of needing to count another way.Important methods and their meanings:– `avl_set(InputIterator start, InputIterator end)` – constructs an AVL tree by inserting the values found in the iterator range provided and rebalancing as needed. – `~avl_set()` – destructor needs to free up the memory allocated for nodes when the `avl_set` is destroyed. – `begin()`, `end()` – return an `avl_iterator` that points to the corresponding position – `rbegin()`, `rend()` – use the `std::reverse_iterator` adapter on the `avl_iterator` for the appropriate position these can be used to iterate in reverse. – `insert(key)` – inserts a new key into your `avl_set`. Duplicate keys are not allowed. – `erase(key)` – removes any node in your AVL tree that has the given key. – `count(key)` – counts the number of nodes in your tree that have the given key. – `size` – returns the number of nodes in the tree. Try to do this in $O(1)$ time. – `height` – returns the height of the tree. – `empty` – returns true if and only if there are no nodes in the tree. – The `is_bst` method checks whether the values of the keys in the tree match the BST condition. – The `is_avl` method checks whether the tree is balanced according to the AVL balance condition. – Traversal methods will just be wrappers to call the traversals you already wrote. These will be useful for checking that your tree is the right shape.When in doubt, the aim is for your methods to behave like the corresponding methods from `std::set`, implemented using the functions you’ve made to work with AVL trees. You can find that specification here: [https://en.cppreference.com/w/cpp/container/set](https://en.cppreference.com/w/cpp/container/set)#### `insert(key)` – `key` – the key to search for in the AVL treeTries to insert `key` into the AVL tree in the appropriate location. Duplicate keys are not allowed, so the insertion of a key that was already present in the tree should fail.Returns a `std::pair`. The first item of the pair will be an `avl_iterator` referencing the node where the key was placed. The second item of the pair will be a `bool` representing whether the insertion succeeded.If the insertion fails, the first element must still be an iterator, but it should be an iterator for which `==` comparison with the `end()` iterator would be true.#### `erase(key)` – `key` – the key to search for and whose node we wish to remove from the treeThis method should locate the key on your AVL tree and remove it, making sure to fix any imbalances caused by that removal.Returns the number of elements removed. If duplicate keys were allowed, this would have had the potential of removing multiple, but we are requiring our keys to be unique, so this will end up being `1` on successful erasure of the node, and `0` if it fails.#### `count(key)` – `key` – the key to search forThis function searches your AVL tree for the key given, and returns the number of times it is found. We are not allowing duplicate keys to be inserted, so this will be `1` if it’s found or `0` if it’s not found on your tree.### `class avl_iterator`– `pos` – pointer to the node being pointed to by this iterator – `prev` – if `pos` is becoming `nullptr` because we went off the end of the tree, make sure to set this to the position of the last thing so we can get back onto the tree again. Otherwise keep it `nullptr`. – `next` – if `pos` is becoming `nullptr` because we went backward past the beginning, make sure to set this to the position of the first thing so we can get back onto the tree again by incrementing from here. Otherwise keep it `nullptr`.This class is where you implement the bidirectional iterator that will be used by the `avl_set` class. They will be implemented in such a way that iterating over the BST will visit the nodes in the same order as an inorder traversal. The implementation of `rbegin()` in the `avl_set` will require that `–` works on `end()` to get you back on the tree. In other bidirection iterators, using `–` to go past `begin()` and then `++` to get back is undefined behavior, but your implementation should allow it to get back onto the tree on the correct side.– There are various constructors, but you only need to implement the copy constructor. – `++` – You need to implement both prefix `++x` and postfix `x++`, which move the iterator to point to the next element. – `–` – You need to implement both prefix `–x` and postfix `–x`, which move the iterator backward by one. – `*x` – Dereferencing the iterator should provide a reference to the value at the current position. – `==` – Comparing two iterators compares their position, not their value.### NotesRemember to continue with our routine of creating a `development` branch and making all changes to that branch, leaving `main` entirely alone. This will be necessary to submit the pull request at the end, signaling completion of your program to the graders.Your work should be done in `bintree.h` and `bst.h`. Do not alter the other files that were provided with the assignment. If you use work from a previous assignment, make sure that you do push the necessary files to the GitHub repo so that they will be there when the grader tries to compile.You should feel free to create whatever files you want to test things locally, including writing your own simple programs to test small parts on their own, but none of them should end up becoming a part of your remote repo. I actually *encourage* you to write unit test programs for yourself, but they should not be a part of your submission.**DO NOT ADD OR COMMIT THE EXECUTABLE FILES CREATED WHILE COMPILING.** They are big and we will be compiling anyway.### TestingThere are a number of testing programs included. These will be used to evaluate the functionality of your implementations of the required functions. Typing `make` will attempt to compile them all, and will succeed to the degree it can with whatever you have implemented at that point.The table below has a list of the tests available, and they are shown in order from least complex to most complex.|Order|Test |Purpose | |:-: |:—-|:——————–| 1|`01-rotate` |Builds some known trees with `bst_insert` and tests your rotation functions. 2|`02-avlfix` |Test your `fix_avl_tree` function with some known trees. 3|`03-loop` |Interactive program like `test4` from previous assignment, but using `fix_avl_tree` and `is_avl`. 4|`04-iter` |Shows how bidirectional iterators from other containers work, then tests the ones from your `avl_set`. 5|`05-avl-set` |Inserts, searches for, and removes various values from `set`, `unordered_set` and `avl_set` for comparison. 6|`06-loop-set` |Interactive program like the other, but using the `avl_set` methods to insert/remove/search.The expected output is contained in the `*.refout` files in the `output/` directory.### How To SubmitLike the other assignments for this semester, we will be doing submissions through GitHub. Make sure you do all of your development in the `development` branch. You can commit as many times as you need to, but keep in mind that this will grow the size of your repo and you may run up against the quota on turing/hopper if it gets too big.When you are finished implementing everything required and the test program is working properly, make sure you add, commit, and push the working version to the repo. Once that is done, **SUBMIT** a pull request but **DO NOT ACCEPT IT**.### Grading Considerations– Does it compile? Does it run? All of the tests should compile and run on turing/hopper with the `Makefile` provided, and points will be deducted for each test that will not compile. – Does the output match for all of the tests? I have provided reference output for each of the test programs where such a thing is valid, so you can compare your program’s output to what is expected. This output can be found in the files ending in `.refout`. – Did you change files you’re not allowed to? There are warning messages at the top of several of the files telling you not to make changes. If you make changes to these, you will receive a grade penalty. You can write your own test programs if you’d like, but do not commit them or push them to the server, and make sure the only modifications that make it to GitHub are the required ones. – Did you commit/push all of the source code needed to compile your program? – Did you indent your code? – Indentation aids in the readability of source code, and if you’re not indenting your code blocks, the grader will legitimately dislike you for it. I’m authorizing them to mark you off if you subject them to reading that. – Did you document your code? – You need a docbox at the top of every one of the files you’re required to change including: – Your name – Your zid – Your GitHub ID – Your course section – A description of what the program does – You should add a docbox for every function that you implement, explaining what it does and what each parameter is for. – Add other comments inside your code blocks describing what you’re doing and why. – The use of `doxygen` style comments is encouraged, but not required.
The purpose of this assignment is for you to implement a fully functional binary search tree. No auto-balancing is done, but the insertion and removal functions will return information that will be useful when adding it at a later time.You are responsible for implementing, all of the following functions:– For general binary tree functionality (in `bintree.h`). – `preorder(root, fn)` – `inorder(root, fn)` – `postorder(root, fn)` – `levelorder(root, fn)` – `delete_tree(root)` – `height(node)` – `count(root)`– For dealing with binary search trees (in `bst.h`): – `bst_find(root, value)` – `bst_insert(root, value)` – `bst_remove_value(root, value)` – `is_bst(root)` – `bst_minimum(root)` – `bst_maximum(root)` – `successor(node)`Some of these were in a previous assignment. If you got them working, feel free to use them again. If not, write them now.### Binary Search TreesYou should have already covered binary search trees in your course’s lecture, but I’m including a brief summary.A binary search tree is a binary tree where nodes are organized based on a comparison in a specific way. The comparison function we will use for this assignment is `
The purpose of this assignment is to have you perform a practical task using binary trees. This time, that task will be to implement a simplified XML parser.You are responsible for implementing, all of the following functions:– For general binary tree functionality (in `bintree.h` – `inorder(root, fn)` – `preorder(root, fn)` – `postorder(root, fn)` – `levelorder(root, fn)` – `delete_tree(root)`– For dealing with “tilted” trees (in `bintree.h`): – `tilted_find_parent` – `tilted_get_children` – `tilted_levelorder`– For the XML parser (in `xml.cc`:– `to_string(const xml_element &element, bool opening)` – `xml_handle_tag` – `xml_handle_plaintext` – `xml_handle_attributes` – `xml_add_node` – `xml_close_tag` – `xml_print_subtree` – `xml_find_by_name` – `xml_find_with_attr`### What is XML?XML, short for eXtensible Markup Language, is a tool for encoding heirarchically organized data into a text file. You’ll be writing parts of a program that reads a file in a simplified version of XML and builds a tree representing the data inside.#### ElementsXML is composed of “elements” and plain text. Elements are allowed contain other elements, and plain text. Plain text doesn’t contain anything. The contents of an element should be represented as children of that element on a tree.plain text : Just normal, ASCII text, but you will need to avoid the characters `'’`, as they will be used to identify “tags”.tags : Tags are used to denote the beginning and end of an element. Everything between the opening tag and the closing tag for an element is said to be “contained” by that element.opening tag : This denotes the beginning of an element, i.e. `` indicates that an element named “tag” has begun. Any attributes associated with the element must be specified in this opening tag.closing tag : This denotes the end of an element, i.e. `` indicates that the most recent element named `tag` is now complete.attributes of an element : These are key/value pairs associated with an element. If there are any, they will be written in the opening tag. As an example `` is an open tag with two attributes. The first one has a key of `height` with a value of `100`, and the second has a key of `width` and a value of `200`. Attributes are separated from the tag name and from other attributes by *whitespace*, and the values should always be in double quotes.whitespace : In the XML standard, whitespace is defined as spaces `’ ‘`, tab characters `’t’`, newlines `’ ’`, and carriage returns `’r’`. Leading and trailing whitespace will be trimmed. Attributes are separated by one or more characters of whitespace.#### Well-formed XMLFor our purposes, well-formed XML is XML data that follows these rules:#. All XML elements must have a closing tag. #. XML tags are case-sensitive. #. Attribute values must always be quoted. #. All XML elements must be properly nested. This is a constraint on the ordering of closing tags where inner elements contained by an outer element must all be closed before the outer element can be closed. – `` is properly nested because the inner tag is closed before the outer tag – `` is *not* properly nested, because the outer `a` tag is told to close before the `b` tag.Your assignment must work for well-formed XML. XML that is not well-formed will cause problems, and your program should generate error messages when these problems are encountered.#### XML Features not SupportedThere are several XML features that we will be avoiding for simplicity’s sake, these include, but are not limited to:– Open tags that are self closing, like `` will not be supported. – Entities such as `<`, `>`, `&`, etc., will not be interpreted. – Only attributes in the `key=”value”` form will be handled, no turning on boolean attributes by naming them. – `CDATA` will not be used. – XML namespaces and DTD will not be used.### “Tilted” TreesXML documents don’t lend themselves immediately to binary trees. An element is able to contain other elements, and this is not constrained to just two. However, there is a way of representing any non-binary tree in a form that fits into a binary tree.To do this, we change the meaning of the left and right pointers in our binary tree node. We redefine the left child of a node to point to the node’s first child on the non-binary tree, and we redefine the right child of the node to point to the node’s next sibling. We’ll call these “tilted” trees, because the binary tree resembles the other, but tilted by 45 degrees. Here is an example.{width=50%}You could tilt the tree in either direction, but we’re using the left for children and right for siblings because it will work better with the traversals you’ve already learned.### Provided for YouI have provided parts of this assignment for you, and you will not need to reimplement those portions:#### `enum xmltype { plain, tag };`This is an enumeration type with two possibilities. It will be used in the `xml_element` class to indicate the type of the element:– `plain` – plain text – `tag` – tag-based element#### `class xml_element`This is the class you will use to store information on elements as you insert them into your tree. The nodes in your tree will use this as the `T` template parameter, so the `data` element for each node will be one.– `type` – an `xml_type` that will be either `plaintext` for plain text, or `tag` for a tag element – `name` – If the element is a tag, the name of the tag. If not, unused. – `fulltext` – The full text of the element. This will be the text of a plain text element, or the tag specifier for a tag. – `attrs` – a `map` containing any attributes detected for a tag – `closed` – a `bool`. Defaults to `false`. Will be set to `true` when the tag is closed.#### `class xml_tree_state`This is a class used to represent the current state of the tree as it is parsed.– `root` – a pointer to the `root` of the tree. Will be `nullptr` for an empty tree. – `cur` – a pointer to the current node, used in the parsing algorithm when adding elements and closing tags.#### `parse_xml( ist, state, verbose )`I provided this function for you. It handles reading the data from the XML file, and it will call your functions to handle tags and plain text encountered.#### `trim`This is another function that is provided. It takes a string and returns a new string that contains the input string with its leading and trailing whitespace removed.### Functions You Implement – Binary Tree#### `inorder(root,fn)`, `preorder(root,fn)`, `postorder(root,fn)`, `levelorder(root,fn)`– `root` – The root of the tree to traverse – `fn` – A function or function-like object that is called to visit each node during the traversal.Each of these functions performs the traversal it is named after on the tree with `root` as its root, calling `fn` as it visits each node.#### `delete_tree(root)`– `root` – The root of the tree for which all nodes will be deleted.Deletes all of the nodes in the tree with `root` as its root, freeing up any dynamically-allocated memory used.### Functions You Implement – Tilted Trees: #### `tilted_find_parent( node )`– `node` – The node whose parent we would like to know.This function returns a pointer to the node that is the *real* parent of the current node, on the non-binary tree represented by this tilted binary tree. If it has no parent, return `nullptr`.#### `tilted_get_children( node )`– `node` – The node whos children we would like to gather.This function returns a `vector` containing pointers to all of the nodes that are *direct* children of `node` in the non-binary tree represented by this tilted binary tree. If `node` is `nullptr` or a leaf node, then return an empty `vector`.#### `tilted_levelorder( root, fn )`– `root` – the root of the tree to traverse – `fn` – The function or function-like object to be called with the current node when visiting.This function performs a level order traversal of the non-binary tree that was tilted to create the binary tree with root `root`. It will call `fn` to visit each node. This traversal is best done non-recursively. I recommend using a `queue`. Remember that each of your nodes can *actually* have multiple children instead of just the two that it would have if we were treating the binary tree normally.### Functions You Implement – XML Parsing:#### `xml_handle_tag( tagstring, state, verbose )`– `tagstring` – This string will contain the entirety of the text that detected as a tag. This will include the `'’` at the end. – `state` – an `xml_tree_state` containing the current state of the tree, this will be needed to add/close the node in the appropriate location. – `verbose` – boolean value. If `true`, you may print out debug information in the function. If `false`, only print error messages.This function is called by `parse_xml` whenever a tag has been found in the input.In this function, you will need to find out the name of the tag, and whether it is an opening tag or closing tag.If the string is empty, too short to be a valid tag, or does not begin with `'’`, then the tag is invalid. Print an error message and return `1` immediately.If it is an opening tag, it may have attributes. You must pass the portion of the `tagstring` after the name to the `xml_handle_attributes` function to break down those attributes and store them into the attribute map for the node.Once you’ve broken down the tag into its parts, construct an `xml_element` and call `xml_add_node` to add it to the tree in the appropriate location.If it’s a closing tag (it has a `’/’` right after the `'
This assignment gives you an opportunity to work with both of the main STL associative container types.– `std::map` will be used to contain configuration info loaded from a file in the INI file format. – `std::set` will be used to store the remaining possibilities for each cell in a Sudoku grid solverYou *are* allowed to use code from previous assignments if it makes solving the problem easier. In fact, you are *encouraged* to use `grid_row_major` from the previous assignment, though this is not a requirement. If you *do* use code from your previous assignment, make sure that the appropriate files are added and committed, as well as pushed to the GitHub repo for submission.You are responsible for implementing, all of the following functions:– For the INI file functionality. The declarations for these are found in `iniparse.h` (which you should not alter), and you will be implementing the functions in `iniparse.cc`. – `add_ini_section(config, section)` – `remove_ini_section(config, section)` – `get_ini_key(config, section, key);` – `set_ini_key(config, section, key, value)` – `remove_ini_key(config, section, key)` – `read_ini(input, verbosity)` – `write_ini(ost, config);` – `print_ini(ost, config);`– For the Sudoku solver. These are declared in `sudoku.h` (which you should not alter), and you are expected to provde the implementations in the file `sudoku.cc`.– `initialize_grid(grid)` – `set_sudoku_cell_known(grid, row, col, solution)` – `set_sudoku_cell_unknown(grid, row, col)` – `remove_sudoku_option(grid, row, col, value)` – `handle_row_for_cell(grid, row, col)` – `handle_col_for_cell(grid, row, col)` – `handle_subgrid_for_cell(grid, row, col)` – `load_sudoku_grid(filename, grid)` – `print_sudoku_grid(ost, grid, unknown, impossible)`### What is an INI file?INI files are files whose data was written in the INI file format. This format (INI is short for initialization) was commonly used to store configuration information for DOS and Windows applications, but it’s been used for many things over the years, and it’s a good application for our associative containers.The idea is that there are several sections, each of which can contain several keys, with associated values. Here’s an example of one:“` ; This is an INI file — if the first non-whitespace character is a ;, it’s a comment [section1] key1=value1 key2=value2[section2] laugh=haha smile=:-) “`The lines `[section1]` and `[section2]` are section headers. They indicate that the keys that follow will belong to the section named.The `key=value` lines are declaring that a key (whose name is on the left hand side of `=`) exists in the most recently named section, and its value should be set to whatever’s on the right hand side of the `=`.So, in the above file, the section `section1` has two keys, `key1` and `key2`. The section `section2` has two keys, `laugh` and `smile`.Comments start with `;`, and are ignored. Leading and trailing whitespace are ignored.### What is Sudoku?Sudoku is a common puzzle game where the player is presented a $9times 9$ grid, divided into $9$, $3times3$ subgrids. In this grid, cells can be filled with numbers $1-9$ or left blank to begin.The goal of the puzzle is to fill any remaining blanks with the numbers $1-9$ such that:– No number appears twice on the same row. – No number appears twice on the same column. – No number appears twice in the same subgrid.We’ll be writing a program that will use these constraints to automatically solve most Sudoku puzzles that are solveable.### What is `INI_CONFIG`?The type `INI_CONFIG` is used to store the configuration data. The default type to be used is `map`.The inner map links string keynames to their string values, and each will hold all of the keys for a particular section.The outer map allows you to look up the appropriate inner map (based on the string section name) for a given section’s keys.### What is `SUDOKUGRID`?The type you see above, `SUDOKUGRID`, is a `typedef` for whatever type you are using to handle your Sudoku grid, whose data will consist of a $9times 9$ grid containing `std::set` in each cell. These sets will be filled the with the numbers $1-9$ that are still possible for that cell in the puzzle.I set up the default type for `SUDOKUGRID` as `grid_row_major`, which would use your code from the grids assignment. If you want to use that, make sure that the relevant files are pushed to GitHub for this assignment’s repo. This is likely the easiest way to handle the grid, but it is not required.If you do not wish to or are not able to use the grid you made for the last assignment, you can change the typedef for `SUDOKUGRID` in `settings.h` to something else that can handle the grid, and write your code to target that.### Functions Required for INI Parsing #### `add_ini_section(config, section)`– `config` – The `INI_CONFIG` to add the section to. – `section` – A string containing the name of the section to add.If the section named already exists, do nothing. If not, create a new empty map to hold the keys the section may contain later and add it into the `INI_CONFIG` outer map using the section name as the key.#### `remove_ini_section(config, section)`– `config` – The `INI_CONFIG` to remove the section from. – `section` – A string containing the name of the section to remove.If the section named already exists, remove it and all of its keys. Return the number of sections actually removed.#### `get_ini_key(config, section, key);`– `config` – The `INI_CONFIG` to retrieve the key from. – `section` – A string containing the name of the section containing the key desired. – `key` – A string containing the name of the key whose value is desired.If the given key exists in the given section, return its value, otherwise return an empty string.#### `set_ini_key(config, section, key, value)` – `config` – The `INI_CONFIG` to set the key in. – `section` – A string containing the name of the section containing the key desired. – `key` – A string containing the name of the key whose value should be set. – `value` – A string for the new value of the key.If the given key exists in the given section, set its value to `value`. If it did not previously exist, add it.#### `remove_ini_key(config, section, key)`– `config` – The `INI_CONFIG` to remove the key from. – `section` – A string containing the name of the section containing the key. – `key` – A string containing the name of the key to remove.If the given key exists in the given section, remove it. Return the number of keys actually removed.#### `read_ini(input, verbosity)`– `input` – an input stream to read from. The data read will be interpreted as a file in the INI format. – `verbosity` – The verbosity level — controls how much debug information will be shown – `0` – no debug information, be quiet and load – `1` – print when sections begin and when keys are detected – `2` – all of the debug information from `1` **and** print the line number and contents for each non-empty, non-comment line foundThis function will start with an empty `INI_CONFIG`, then read all available data from the `input` stream a line at a time. Each line is interpreted in the INI file format:– Lines with only whitespace (spaces or tabs) are empty and should be ignored – Lines where the first non-whitespace character is `’;’` are to be interpreted as comments, and ignored. – Lines where the first non-whitespace character is `'[`’ are to be interpreted as heading naming the section that future keys are to be added into. The section name continues either until a `’]’` (correct) or the end of the line (invalid but we’ll deal with it). – Non-comment lines of the form `key=value` are interpreted to mean that there is a key named `key` in the current section with value `value`. All of the values are to be kept as strings, and any conversion will happen later. The key will be the part before the `’=’` and the value will be everything from the character after the `’=’` until the end of the line, but with no leading or trailing whitespace kept. – Lines that are not empty, are not comments, do not name a section, and do not set a key’s value are invalid, and should be ignored.Key names, section names, and values may exist in the file with whitespace around them, but they should have any leading or trailing whitespace removed from them before storage in your configuration.This function returns the `INI_CONFIG` built up from the input file. All of the detected keys should have values in the maps for their corresponding sections. No empty sections should be kept.#### `write_ini(ost, config);`– `ost` – output stream to write the INI data to – `config` the `INI_CONFIG` we are writing to the output streamThis function will output all of the keys found in `config` in such a way that the output could be used with `read_ini` to restore the same config (except for any sections that contain no keys).#### `print_ini(ost, config);`– `ost` – output stream to print to – `config` the `INI_CONFIG` whose info we would like to printThis function prints the configuration data from `config` with one key per line, in the format `section_name.key_name = “value”`. Use a tab character and not a space between the key name and the equal sign so things will tend to line up more neatly.If `config` is empty, print `”Configuration is empty. Nothing to print ”` to `cout`. If any of the sections are empty, print a message in the format `Section “section_name” is empty `.Print out an additional newline at the end of printing all of the keys.### Functions Required for Sudoku Solving #### `initialize_grid(grid)`I’ve provided an implementation of this if you are using your `row_major_grid` from the previous assignment. If you’re using something else, then this function is an opportunity to do any initialization that is necessary to prepare an object of the the type you chose for `SUDOKUGRID`.#### `set_sudoku_cell_known(grid, row, col, solution)`– `grid` – the `SUDOKUGRID` to use – `row` – the row of the cell we’re marking – `col` – the column of the cell we’re marking – `solution` – the value we’re marking for the cellMarks the Sudoku cell in row `row` and column `col` as known by clearing the set of everything but the known answer, `solution`.#### `set_sudoku_cell_unknown(grid, row, col)`– `grid` – the `SUDOKUGRID` to use – `row` – the row of the cell we’re marking – `col` – the column of the cell we’re markingMarks the Sudoku cell in row `row` and column `col` as unknown by filling the set with all possibilies (1-9).#### `remove_sudoku_option(grid, row, col, value)`– `grid` – the `SUDOKUGRID` to use – `row` – the row of the cell we’re removing an option from – `col` – the column of the cell we’re removing an option fromThis removes the given value from the set of remaining possibilities for the cell at in the given row and column.#### `handle_row_for_cell(grid, row, col)`– `grid` – the `SUDOKUGRID` to use – `row` – the row of the cell we’re handling – `col` – the column of the cell we’re handlingIf the cell at (row,col) is known (only one possibility remaining), remove its value from the possibilities of all of the *other* cells in the same row. If unknown, do nothing for now.#### `handle_col_for_cell(grid, row, col)`– `grid` – the `SUDOKUGRID` to use – `row` – the row of the cell we’re handling – `col` – the column of the cell we’re handlingIf the cell at (row,col) is known (only one possibility remaining), remove its value from the possibilities of all of the *other* cells in the same column. If unknown, do nothing for now.#### `handle_subgrid_for_cell(grid, row, col)`– `grid` – the `SUDOKUGRID` to use – `row` – the row of the cell we’re handling – `col` – the column of the cell we’re handlingIf the cell at (row,col) is known (only one possibility remaining), remove its value from the possibilities of all of the *other* cells in the same $3times 3$ subgrid. If unknown, do nothing for now.#### `load_sudoku_grid(filename, grid)`– `filename` – filename of the grid file that’s storing our Sudoku grid – `grid` – the `SUDOKUGRID` that will be populated based on the input dataThis function reads in the Sudoku data from a file. The data is stored in the same format as was used to store files for the `grid_row_major`. The values will be integers from $0-9$. $0$ will indicate that the cell was blank, and needs to be solved for. The numbers $1-9$ indicate the known value for the cell.Remember that the numbers in the file are integers, but your `SUDOKUGRID` contains sets of remaining possible values for each field.If the file cannot be opened, print an error message and return `false`.If the dimensions of the grid in the input file are not $9times 9$, print an error message and return `false`.If the file is successfully loaded, the function should return `true`.#### `print_sudoku_grid(ost, grid, unknown, impossible)`– `ost` – output stream to print to – `grid` – `SUDOKUGRID` containing the grid information – `unknown` – The character used for a cell with an unknown value. The default is `’ ‘` (space). – `impossible` – The character used when a cell has no remaining possibilities. The default is `’x’`This function prints the grid to the `ost` output stream in a neat format.– each cell has one space before its value and one space after – each $3times 3$ subgrid will be divided by vertical lines drawn with `|` and horizontal lines drawn with `-`.If a cell is known, its known value should be displayed. If it’s unknown, the `unknown` character should be printed, and if there are no remaining possibilities, display the `impossible` character.“` with unknown = ‘ ‘ with unknown = ‘?’ 5 3 | 7 | 5 3 ? | ? 7 ? | ? ? ? 6 | 1 9 5 | 6 ? ? | 1 9 5 | ? ? ? 9 8 | | 6 ? 9 8 | ? ? ? | ? 6 ? ———|———|——— ———|———|——— 8 | 6 | 3 8 ? ? | ? 6 ? | ? ? 3 4 | 8 3 | 1 4 ? ? | 8 ? 3 | ? ? 1 7 | 2 | 6 7 ? ? | ? 2 ? | ? ? 6 ———|———|——— ———|———|——— 6 | | 2 8 ? 6 ? | ? ? ? | 2 8 ? | 4 1 9 | 5 ? ? ? | 4 1 9 | ? ? 5 | 8 | 7 9 ? ? ? | ? 8 ? | ? 7 9“` ### NotesRemember to continue with our routine of creating a `development` branch and making all changes to that branch, leaving `main` entirely alone. This will be necessary to submit the pull request at the end, signaling completion of your program to the graders.Your work should be done in `settings.h`, `sudoku.cc`, and `iniparse.cc`. Do not alter the other files that were provided with the assignment. If you use work from a previous class, make sure that you do push the necessary files to the GitHub repo so that they will be there when the grader tries to compile.You should feel free to create whatever files you want to test things locally, including writing your own simple programs to test small parts on their own, but none of them should end up becoming a part of your remote repo. I actually *encourage* you to write unit test programs for yourself, but they should not be a part of your submission.**DO NOT ADD OR COMMIT THE EXECUTABLE FILES CREATED WHILE COMPILING.** They are big and we will be compiling anyway.### TestingThere are a number of testing programs included. These will be used to evaluate the functionality of your implementations of the required functions. Typing `make` will attempt to compile them all, and will succeed to the degree it can with whatever you have implemented at that point.The table below has a list of the tests available, and they are shown in order from least complex to most complex.|Order|Test |Purpose | |:-: |:—-|:——————–| 1|`test1` |Interactive test for the functions that add/remove/change things in an `INI_CONFIG`. 2|`test2` |Loads an INI file into an `INI_CONFIG`. Prints out all of the keys in the `INI_CONFIG`. 3|`test3` |Loads a Sudoku grid from a file. Prints it out immediately. 4|`test4` |Tests portions of the Sudoku solver without loading in a Sudoku file. 5|`test5` |Loads a Sudoku grid from a file. Prints it before and after solving. 6|`test6` |Loads a Sudoku grid from a file. Reads some parameters from an INI file that control its behavior.The expected output is contained in the `*.refout` files in the `output/` directory.### How To SubmitLike the other assignments for this semester, we will be doing submissions through GitHub. Make sure you do all of your development in the `development` branch. You can commit as many times as you need to, but keep in mind that this will grow the size of your repo and you may run up against the quota on turing/hopper if it gets too big.When you are finished implementing everything required and the test program is working properly, make sure you add, commit, and push the working version to the repo. Once that is done, **SUBMIT** a pull request but **DO NOT ACCEPT IT**.### Grading Considerations– Does it compile? Does it run? All of the tests should compile and run on turing/hopper with the `Makefile` provided, and points will be deducted for each test that will not compile. – Does the output match for all of the tests? I have provided reference output for each of the test programs, so you can compare your program’s output to what is expected. This output can be found in the files ending in `.refout`. – Did you change files you’re not allowed to? There are warning messages at the top of several of the files telling you not to make changes. If you make changes to these, you will receive a grade penalty. You can write your own test programs if you’d like, but do not commit them or push them to the server, and make sure the only modifications that make it to GitHub are the required ones. – Did you commit/push all of the source code needed to compile your program? – Did you indent your code? – Indentation aids in the readability of source code, and if you’re not indenting your code blocks, the grader will legitimately dislike you for it. I’m authorizing them to mark you off if you subject them to reading that. – Did you document your code? – You need a docbox at the top of every one of the files you’re required to change including: – Your name – Your zid – Your GitHub ID – Your course section – A description of what the program does – You should add a docbox for every function that you implement, explaining what it does and what each parameter is for. – Add other comments inside your code blocks describing what you’re doing and why. – The use of `doxygen` style comments is encouraged, but not required.
This assignment was designed to give students an opportunity to use some of the STL generic algorithms, and to write and use some higher order functions, composing them to make a more useful whole.You are responsible for implementing, in `gen-algo.h`, all of the following functions:– To load and process input data: – `size_t read_lines(std::istream &instream, FN linecb);` – `size_t split_string_strict(const std::string &instring, FN tokencb, char delim);` – `size_t split_string_greedy(const std::string &instring, FN tokencb, char delim);`– To work with tables, which we will be using a vector containing other vectors as the rows to represent. – `void print_table(…);` – `int table_min_cols(const STR_TABLE &table);` – `std::vector calc_widths(const STR_TABLE & table);` – `STR_TABLE load_tsv(const std::string & filename);` – `void table_sort_alpha(STR_TABLE & table, unsigned int col);` – `void table_sort_numer(STR_TABLE & table, unsigned int col);`### What is `STR_TABLE`?The type you see above, `STR_TABLE`, is a `typedef` for `vector< vector >`, which is being used as a table stored as a vector containing vectors representing its rows, which contain string elements. Here are some examples of what to expect when working with it.“` Given STR_TABLE x; : x[0] => vector containing all elements in 0th row x[i] => vector containing all elements in ith row (x[i])[j] => jth column in ith row. x.size() => number of rows in the table x[i].size() => number of cells in the ith row x.begin() => on the outer vector gives an iterator that points to the ***vector*** for the 0th row x[i].begin() => (begin for inner vector) gives an iterator that points to the 0th element of the vector for row i “`### Functions for Loading / Parsing DataThese functions are higher order functions, which means that one or more of their parameters will be something that is callable as a function.#### `read_lines( instream, linecb )`– `instream` – a `std::istream` that you will read the lines from. This could be `cin` or an open file. – `linecb` – a *callable* — a function or a function-like object that you can call with the `()` operator. For `read_lines` to work, the person calling it must give you a `linecb` that accepts a `std::string` as its only parameter.This function will use `getline` on the `istream` passed in as `instream`. Every line in the file should be read, until the EOF. For each line read, call the “callback” function, linecb, and pass the string read to that function.Your function must return the number of lines read.#### `split_string_strict (instring, tokencb, delim )`– `instring` – The string to be split. – `tokencb` – something that can be invoked as a function, which takes a single string as a parameter. This function will be called once for each token detected. – `delim` – The character used as the delimiter for splitting.This function goes through the whole string passed in, splitting it into tokens based on the delimiter character. This is the **strict** version, which means that a delimiter always indicates the end of one token and the start of another, even if that means the token is empty.When a token is detected, `tokencb` function must be called with a string containing that token.The function will return the total number of tokens detected.You may adapt your code from 02a for this purpose, or you can use this as an opportunity to do it in terms of the STL `find` and `find_if` algorithms.#### `split_string_greedy (instring, tokencb, delim )`– `instring` – The string to be split. – `tokencb` – something that can be invoked as a function, which takes a single string as a parameter. This function will be called once for each token detected. – `delim` – The character used as the delimiter for splitting.This function goes through the whole string passed in, splitting it into tokens based on the delimiter character. This is the **greedy** version, which means:– There is no such thing as an empty token unless the whole string was empty. – Any delimiters that occur before the first token should be ignored, not included in the token. – When there are several delimiters in a row, the first one splits the token, and the rest are ignored until a non-delimiter character begins the next token.When a token is detected, `tokencb` function must be called with a string containing that token.The function will return the total number of tokens detected.You may adapt your code from 02a for this purpose, or you can use this as an opportunity to do it in terms of the STL `find` and `find_if` algorithms.### Table Functions#### `print_table ( ost, table, widths, maxcol, pre, sep, post, leftalign)`This function is responsible for printing out your table in a tidy format.– `ost` – The `std::ostream` to print the output to. This will usually be `cout`, but could be any `ostream` – `table` – The `STR_TABLE` containing the data you need to print – `widths` – `widths[i]` will contain the column width for column `i` – `maxcol` – maximum number of columns to print – `pre` – prefix – string to print before each row – `sep` – separator – string to print between columns – `post` – string to print at the end of each row – `leftalign` – `bool` – `true` makes columns left-aligned, `false` aligns them to the right.The column widths must be set using `std::setw`, and their alignment can be handled with `std::left` and `std::right`, which are declared in ``.Do not print more than `maxcol` columns. This is for a couple of reasons:– It can be used as an upper bound on `widths` if you only have a few column widths (to prevent segfault) – There may have been rows that had uneven widths; this was detected, and the minimum width was passed here.You can make the assumption that either the rows are all of the same length, or that `maxcol` that is passed in will be the width of the shortest row or less. If you use this outside of the test programs, that would be a thing to keep in mind.#### `table_min_cols ( table )`This function looks at each of the rows in the table provided, and returns the width of the shortest row present.If the input data was in the proper format, this should be the same as the maximum number as well, but this function is used to find out how many columns exist in all of the rows.When implementing this, avoid writing a loop yourself. You should use the STL `for_each` algorithm, or `transform` together with `min_element`.#### `calc_widths ( table )`This function returns a vector of integers. Each integer in the vector will contain the width (in characters) of the longest string in the corresponding column of the `STR_TABLE` passed in, `table`.When implementing this, avoid writing a loop yourself. You should use the STL `for_each` algorithm, or `transform` together with `min_element`.#### `load_tsv ( filename )`This function is responsible for loading a table from the file given, which must be a tab-separated values file. This data will be returned as a `STR_TABLE`.Tab separated values files are a way of storing a table in a text format. Rows are delimited by the newline character, so if you read the whole line you get the whole row. The fields in each column are strictly delimited by a tab character (hence the name).You are expected to do this using the `read_lines` function together with the `split_string_strict` function.**Hint:** This is easy to do with lambda expressions using capture by reference, but if you didn’t learn them in class, you’ll need to figure out another way to have your functions communicate with the table in the scope of the function running `read_lines`. You could do this with global variables, or make a class that overloads the calling operator () that tracks this information itself, but lambda expressions with captures will make your life much easier.#### `table_sort_alpha( table, col )`Using the version of the `std::sort` algorithm that allows you to pass a custom comparator, order the rows in the table so that column number `col` is sorted in ascending order, alphabetically. The reference output used a case sensitive comparator.#### `table_sort_numer( table, col )`Using the version of the `std::sort` algorithm that allows you to pass a custom comparator, order the rows in the table so that column number `col` is sorted in ascending order, numerically. This order will be different than the alphabetical sort for numbers of differing lengths. To convert a string value to a `double`, you can use the function `strtod`.### NotesRemember to continue with our routine of creating a `development` branch and making all changes to that branch, leaving `main` entirely alone. This will be necessary to submit the pull request at the end, signaling completion of your program to the graders.There is one file that you should do your work in, `gen-algo.h`. Do not commit/push any changes to the other files.You should feel free to create whatever files you want to test things locally, including writing your own simple programs to test small parts on their own, but none of them should end up becoming a part of your remote repo. I actually *encourage* you to write unit test programs for yourself, but they should not be a part of your submission.**DO NOT ADD OR COMMIT THE EXECUTABLE FILES CREATED WHILE COMPILING.** They are big and we will be compiling anyway.### TestingThere are a number of testing programs included. These will be used to evaluate the functionality of your implementations of the required functions. Typing `make` will attempt to compile them all, and will succeed to the degree it can with whatever you have implemented at that point.The table below has a list of the tests available, and they are shown in order from least complex to most complex.|Order|Test |Purpose | |:-: |:—-|:——————–| 1|`test-read-line` |Tests your `read-line` function in isolation. 2|`test-simple-strict` |Tests your `split_string_strict` function in isolation. 3|`test-simple-greedy` |Tests your `split_string_greedy` function in isolation. 4|`test-print-table` |Tests your `print-table` function in isolation. 5|`test-calc-widths`|Tests `calc_widths`, requires `print_table`. 6|`test-sorting` |Tests your sort functions, requires `calc_widths` and `print_table`. 7|`test-load-tsv` |Tests your `load_tsv` function. Requires almost everything to work. 8|`test-load-sort` |Tests your `load_tsv` function together with sorting. This uses almost everything.The expected output is contained in the `*.refout` files in the `output/` directory.### How To SubmitLike the other assignments for this semester, we will be doing submissions through GitHub. Make sure you do all of your development in the `development` branch. You can commit as many times as you need to, but keep in mind that this will grow the size of your repo and you may run up against the quota on turing/hopper if it gets too big.When you are finished implementing everything required and the test program is working properly, make sure you add, commit, and push the working version to the repo. Once that is done, **SUBMIT** a pull request but **DO NOT ACCEPT IT**.### Grading Considerations– Does it compile? Does it run? All of the tests should compile and run on turing/hopper with the `Makefile` provided, and points will be deducted for each test that will not compile. – Does the output match for all of the tests? I have provided reference output for each of the test programs, so you can compare your program’s output to what is expected. This output can be found in the files ending in `.refout`. – Did you change files you’re not allowed to? There are warning messages at the top of several of the files telling you not to make changes. If you make changes to these, you will receive a grade penalty. You can write your own test programs if you’d like, but do not commit them or push them to the server, and make sure the only modifications that make it to GitHub are the required ones. – Did you indent your code? – Indentation aids in the readability of source code, and if you’re not indenting your code blocks, the grader will legitimately dislike you for it. I’m authorizing them to mark you off if you subject them to reading that. – Did you document your code? – You need a docbox at the top of every one of the files you’re required to change including: – Your name – Your zid – Your GitHub ID – Your course section – A description of what the program does – You should add a docbox for every function that you implement, explaining what it does and what each parameter is for. – Add other comments inside your code blocks describing what you’re doing and why. – The use of `doxygen` style comments is encouraged, but not required.
For this assignment, you’ll be implementing a class that provides resizeable 2D grid functionality. It allows you to access its contents via coordinates, whether they’re (x,y) or (row, column). It’ll also provide access to the individual rows and columns via iterators.– I’ve given you the declaration of a class called `grid_row_major` in the file `grids.decl.h`. You need to implement all of the methods that have not already been provided, putting that code into `grids.h`. **DO NOT CHANGE `grids.decl.h`**.– Develop a class to implement the column iterators properly. I’ve given you the declaration of something that can be made to work, but you are not required to use it, if you’d rather solve it in a different way. The methods that provide these iterators have `auto`-deduced return types so you can return anything that would work as an appropriate iterator in them.– Implement the `matrix_multiply(lhs,rhs,result)` function.### NotesRemember to continue with our routine of creating a `development` branch and making all changes to that branch, leaving `main` entirely alone. This will be necessary to submit the pull request at the end, signaling completion of your program to the graders.There is one file that you should do your work in, `grids.h`. Do not commit/push any changes to the other files.You should feel free to create whatever files you want to test things locally, including writing your own simple programs to test small parts on their own, but none of them should end up becoming a part of your remote repo. I actually *encourage* you to write unit test programs for yourself, but they should not be a part of your submission.**DO NOT ADD OR COMMIT THE EXECUTABLE FILES CREATED WHILE COMPILING.** They are big and we will be compiling anyway.### Our Grid Class: `grid_row_major`You can find the declaration for `grid_row_major` in `grids.decl.h`. Before we get into a discussion of the methods and what you need to do to implement them, let’s talk about how the data will actually be stored.Each instance of our class will have some random access container actually holding the data for the grid. To provide access to that data as a 2D grid, we’ll need to map our coordinates to the cells in that array-like object. One really common way to do this is called “row major order”, where all of the elements of one row are listed next to each other, and one row starts after all the elements of the last one have been listed. If we were using a 25-element `vector` as a $5 times 5$ grid, it would be organized like this:| | | | | | | -:| -:| -:| -:| -:| | 0 | 1 | 2 | 3 | 4| | 5 | 6 | 7 | 8 | 9| | 10 | 11 | 12 | 13 | 14| | 15 | 16 | 17 | 18 | 19| | 20 | 21 | 22 | 23 | 24|Taking a look at the numbers, the number goes up by one as we move from left to right across rows, and it goes up by the width of the table whenever we move down the columns. It can also be noted that the total number of cells is always the product of the width times the height.### Members (Data/Methods) of `grid_row_major`#### Data Member `data` – This will be an instance of whatever container you chose to use for your `RA_CONTAINER` template parameter. This will default to a `std::vector` containing the type of element contained. Any container that supports random access iterators should work, in general, but we will mainly use `std::vector` and `std::deque` in practice.– If you try to instantiate a grid with an `RA_CONTAINER` with a type that isn’t a container or with a container type that doesn’t support random access, then compilation is not expected to succeed.#### Data Members `_height` and `_width` – These keep track of the dimensions of the grid, and you’ll need them in order to calculate the index where the data for a particular set of coordinates resides in.#### Constructor `( width, height )` – Make the grid width $times$ height, without taking the trouble to change the data values. They’ll remain at their default until you change them with something else.#### Constructor `( width, height, begin, end )` – This is the STL-style cross-container-type iterator-based copy constructor. The grid is resized to width $times height and values are copied from the iterator range into the grid directly, interpreted, once again, as being in row major format.#### Copy Constructor – Construct a new grid by copying the contents of another grid. The new grid gets its width, height, and data from the existing grid.#### Assignment Instructor `operator =` – Overwrite this grid by copying in the contents of the other grid. Replace this grid’s width, height, and data, copying them from the other grid.#### Dimensions Checking `width()` and `height()`– These methods return the width, or the height, respectively, of the grid.#### `empty()` – This method should return `true` if, and only if, there are no elements present in the grid.#### Bounds Checking: `boundscheckxy` and `boundscheckrc` – These methods take coordinates as parameters — the `xy` version takes (x,y) coordinates and the `rc` version takes (row, column) coordinates. If the coordinates fit within the boundaries of the grid, they will return true, otherwise false. Notice that both sets of coordinates start with 0 as the lowest available.#### Grid Element Access `atxy, atrc`These functions are used to access (by reference) the location in the grid corresponding to the coordinates provided. These are analogous to the `at` method of the STL sequence containers, but adapted to take two-dimensional grid coordinates instead of a one-dimensional index. Just like `at`, you should perform a bounds check in these and throw a `std::out_of_range` exception if the user tries to go out of bounds.– `atrc(row, col)`: takes row, column coordinates — row 0 is the first row, and row (height-1) is the last row. Column 0 is the first, leftmost column. These coordinates are typically used by mathematicians (they may decide to start the numbering at 1 instead of 0) and you’ll see them used a lot when a program involves linear algebra (like matrix multiplication). – `atxy(x,y)`: takes screen x,y coordinates — (x=0,y=0) is the top left element, and (x=width-1, y=height-1) is the bottom right. These coordinates are commonly used when doing raster graphics on a computer screen.#### Row Iterator Access `rowbegin`, `rowend` – `rowbegin(i)` provides an iterator that points to the first element in row `i` (numbering from 0). `rowend(i)` returns an iterator that points just past the last element on row `i`. These are simple to provide in a row major grid.#### Column Iterator Access `colbegin`, `colend` – `colbegin(i)` will return a *column* iterator that points to the first element in column `i` (numbering from 0) – `colend(i)` returns a *column* iterator that points to the position that you’d get to after iterating one time past the last valid element in the column. – You will need to do some extra work to implement the iterators used here compared to the ones for the rows, as a simple iterator’s `++` operation would be moving within a row, and these require you to move through a column. I’ve provided the declaration for a class that could be used to implement this, but if there’s another way that you prefer to handle the problem, feel free to use your own solution, as long as it was you who wrote it and it works.#### `resize()` – Destructively resize the grid. Do not worry about keeping the data that was previously present intact. Make the `data` container big enough to fit a width $times$ height grid, and change the `_height` and `_width` parameters to the new size.#### `clear()` – Get rid of all of the data that was being stored, and change the stored height and width accordingly.#### `load_from_file( filename )` – This method will try to replace the contents of this grid with the data from the specified file. To do this, it will open the file with a `std::fstream` and ask for data with the abstraction operator. – Before you try to interpret any of the data, read two integers in from the file. The first one will be the width, and the second will be the height. – From that point on, you read values in, extracting the data into whatever type our container holds, and putting them into our backing container *in row order*. – If there’s too much data in the file, stop reading when you’ve filled the grid. If there’s too little data in the file, print an error message to standard error when you’ve run out early.### Column Iterators `col_iterator`– I’ve provided an outline of a possible class that you could use to implement the column iterators. You are not forced to use the `col_iterator` class if you do not want to, but the code *will* need to work with whatever solution you choose. – Remember that the point of the column iterators is that, when you increment the iterator, it points to the next element in the *column*. Our grid is row major, so just incrementing the position by one would leave the current column. You’ll need to overload the ++ operator to handle the *correct* movement. – Unlike the iterators you implemented for your linked list, the iterators provided by your grid’s backing container provide random access. It would be useful to implement things like operators `+`, `-`, and `[]`.### Matrix MultiplicationMatrix multiplication is a very useful operation that can be performed on grids that you will likely see used in a lot of application (3D graphics use them extensively). Your function will treat the input grids as matrices and perform that calculation, overwriting the data in the result grid with the result.In matrix multiplication, each cell (row `i`, col `j`) will contain the “dot product” of row `i` in the left hand side matrix with column `j` in the right hand side matrix. A dot product is the sum of the multiples of corresponding elements.– $[a_1, a_2, a_3, a_4] cdot [b_1, b_2, b_3, b_4] = (a_1 times b_1) + (a_2 times b_2) + (a_3 times b_3) + (a_4 times b_4)$Details on how to perform matrix multiplication can be found here:– [`https://en.wikipedia.org/wiki/Matrix_multiplication`](https://en.wikipedia.org/wiki/Matrix_multiplication)If you don’t like the Wikipedia article, there are many results on the web that you can search for.As a reminder, you need to write the code based on an explanation of the process, **not** find and use someone else’s.#### `matrix_multiply( lhs, rhs, result )`##### Template Parameters The `GRID1`, `GRID2`, and `GRID3` template parameters are each (potentially different) classes that implement our grid functionality. What is important is that the `lhs` and `rhs` grids contain elements of types that can be multipled with each other and added to a `double` in a way that makes sense. The `result` grid needs to be able to have `double`s assigned to it. You won’t need to specify these types explicitly to call this function; the compiler will be able to deduce them automatically.##### Parameters– `GRID1 lhs` – The grid to be used as the left hand side of the matrix multiplication – `GRID2 lhs` – The grid to be used as the right hand side of the matrix multiplication – `GRID3 result` – The grid that will be used to store the result.##### Return CodeThis function returns `true` if the grids supplied for `lhs` and `rhs` can be matrix multiplied. If they can’t, it should return `false`, and `result` should not be touched.### How To SubmitLike the other assignments for this semester, we will be doing submissions through GitHub. Make sure you do all of your development in the `development` branch. You can commit as many times as you need to, but keep in mind that this will grow the size of your repo and you may run up against the quota on turing/hopper if it gets too big.When you are finished implementing everything required and the test program is working properly, make sure you add, commit, and push the working version to the repo. Once that is done, **SUBMIT** a pull request but **DO NOT ACCEPT IT**.### Grading Considerations– Does it compile? Does it run? All of the tests should compile and run on turing/hopper with the `Makefile` provided, and points will be deducted for each test that will not compile. – Does the output match for all of the tests? I have provided reference output for each of the test programs, so you can compare your program’s output to what is expected. This output can be found in the files ending in `.refout`. – Did you change files you’re not allowed to? There are warning messages at the top of several of the files telling you not to make changes. If you make changes to these, you will receive a grade penalty. You can write your own test programs if you’d like, but do not commit them or push them to the server, and make sure the only modifications that make it to GitHub are the required ones. – Did you indent your code? – Indentation aids in the readability of source code, and if you’re not indenting your code blocks, the grader will legitimately dislike you for it. I’m authorizing them to mark you off if you subject them to reading that. – Did you document your code? – You need a docbox at the top of every one of the files you’re required to change including: – Your name – Your zid – Your GitHub ID – Your course section – A description of what the program does – You should add a docbox for every function that you implement, explaining what it does and what each parameter is for. – Add other comments inside your code blocks describing what you’re doing and why. – The use of `doxygen` style comments is encouraged, but not required.
This assignment is an opportunity for students to learn more about how iterators work in STL by implementing a container and its iterators such that various STL algorithms will *just work* with it.Your task is to provide implementations for all of the methods of the `simple_linked_list` class, which is declared in `simple_linked_list.decl.h`. Your code to implement them will go into the file `simple_linked_list.h`.**NOTE:** This assignment will use some of the algorithms from your previous assignment, so don’t forget to add/commit/push your last assignment’s `assign2-algos.h` to this assignment’s repo.### NotesRemember to continue with our routine of creating a `development` branch and making all changes to that branch, leaving `main` entirely alone. This will be necessary to submit the pull request at the end, signaling completion of your program to the graders.There is one file that you should do your work in, `simple_linked_list.h`. Do not commit/push any changes to the other files, but do add/commit/push a copy of your working `assign2-algos.h` from the previous assignment.You should feel free to create whatever files you want to test things locally, including writing your own simple programs to test small parts on their own, but none of them should end up becoming a part of your remote repo. I actually *encourage* you to write unit test programs for yourself, but they should not be a part of your submission.**DO NOT ADD OR COMMIT THE EXECUTABLE FILES CREATED WHILE COMPILING.** They are big and we will be compiling anyway.### Implementing an STL-style Linked ListAlthough a doubly-linked list is already implemented in the STL in the form of `std::list`, and you should use it in the future when you need a linked list, there is a lot to be learned by writing your own STL-style container and watching iterator-based generic algorithms “just work” on it.Toward that end, you will be implementing the member functions for several classes, which are declared in `simple_linked_list.decl.h`, but that you should define/implement in `simple_linked_list.h`:#### `linked_node`This is the class that handles your individual linked list nodes. It is already complete, and you don’t need to implement anything for it, but a brief explanation of the members follows:– `data` will store the value for the current node – `next` will point to the next node in the list, or be `nullptr` if there is no such node. – The constructor is provided for convenience, and it allows you to construct a node with the value and/or the next node pointer already set.#### `simple_linked_list`This the class that provides the STL-style interface to your linked list. It is also declared in `simple_linked_list.decl.h`, and the important data members are:– `head` – a pointer to the first node in the linked list, or `nullptr` if it’s empty. – `tail` – a pointer to the last node in the linked list, or `nullptr` if it’s empty.The only method that comes implemented is the default constructor. You will need to implement everything else (in `simple_linked_list.h`)– Range constructor: `simple_linked_list(ITERATOR, ITERATOR)` – Initializes the list to a working state, then iterates over the range provided, adding each element to the linked list in order. This will only be called with valid iterator ranges.– `empty()` method – This method should return `true` if, and only if, there are no nodes in the linked list.– `begin()` method – This method should return a `simple_linked_iterator` that points to the head node.– `end()` method – This method should return a `simple_linked_iterator` that would compare `==` an iterator that is off the end of the list.– `front()` method – This should return a reference to the data member of the head node. Although this is obviously invalid when called on an empty list, the responsibility for checking falls upon the person using it, and you’re allowed to crash when they try.– `back()` method – This should return a reference to the data member of the tail node. Once again, although this is obviously invalid when called on an empty list, the responsibility for checking falls upon the person using it, and you’re allowed to crash when they try.– `pop_back()` method – Modify the linked list to remove the last node.– `push_back(T)` method – Add a new node containing the provided value to the end of the linked list.– `size()` method – Returns how many elements are currently in the linked list.– `clear()` method – Remove all of the nodes from the linked list to reset it to an empty state.– Destructor: `~simple_linked_list()` – This is called when your container goes out of scope, and is responsible for making sure to `delete` any `new` objects you created.#### `simple_linked_iterator`This is the class for the iterators exposed by `simple_linked_list` above. The only data member it has is the `pos` value, which is a pointer to one of the `linked_node` linked list nodes used by your linked list.You need to implement the methods so that they work properly as iterators when used in an algorithm. This will mean implementing the following methods (in `simple_linked_list.h`):– Constructor: `simple_linked_iterator(linked_node *)` – This one is actually already implemented, and allows you to construct the iterator already pointing to the given node. – Preincrement: `operator ++ ()` – Called when you increment your iterator with `++` *before* the name, i.e. `++i`. This changes the current iterator so it points to the next node, and returns a reference to the current iterator, which will be at the new position. – Postincrement: `operator ++ (int)` – Called when you increment your iterator with `++` *after* the variable name, i.e. `i++`. This also changes the current iterator so it points to the next node, but it returns another iterator that points to the original node position. – Dereference: `operator * ()` – This should return a reference to the `data` member of the `linked_node` that the current iterator points to. Checking to make sure that it’s okay to dereference is the responsibility of something else, so if someone tries to dereference something invalid, failure here is their fault, not yours. (You won’t hear that often.) – Comparison: `operator == (simple_linked_iterator &)` – This returns `true` if and only if both `simple_linked_iterators` (`*this` and the parameter) are pointing to the same node.### How To SubmitLike the other assignments for this semester, we will be doing submissions through GitHub. Make sure you do all of your development in the `development` branch. You can commit as many times as you need to, but keep in mind that this will grow the size of your repo and you may run up against the quota on turing/hopper if it gets too big.When you are finished implementing everything required and the test program is working properly, make sure you add, commit, and push the working version to the repo. Once that is done, **SUBMIT** a pull request but **DO NOT ACCEPT IT**.### Grading Considerations– Does it compile? Does it run? If it doesn’t compile and run on turing/hopper with the `Makefile` provided, no points will be awarded. – Does the output match? I have provided reference output for the driver program, so you can compare your program’s output to what is expected. This output can be found in `container.refout` – Did you change files you’re not allowed to? There are warning messages at the top of several of the files telling you not to make changes. If you make changes to these, you will receive a grade penalty. You can write your own test programs if you’d like, but do not commit them or push them to the server, and make sure the only modifications that make it to GitHub are the required ones. – Are there any memory leaks? There is a potential, when working with linked lists, to mess things up and leak memory. There is a program called `valgrind` that can/will be used to check for that. – Did you indent your code? – Indentation aids in the readability of source code, and if you’re not indenting your code blocks, the grader will legitimately dislike you for it. I’m authorizing them to mark you off if you subject them to reading that. – Did you document your code? – You need a docbox at the top of every one of the files you’re required to change including: – Your name – Your zid – Your GitHub ID – Your course section – A description of what the program does – You should add a docbox for every function that you implement, explaining what it does and what each parameter is for. – Add other comments inside your code blocks describing what you’re doing and why. – The use of `doxygen` style comments is encouraged, but not required.
In this assignment, the student will write several algorithms that use iterators to perform some simple computing tasks. They will be implemented using template functions so they will be able to be applied with any type of iterator (forward or better).I have included a `Makefile`, so you can compile this by typing `make` at the command line and hitting enter. Source code for two driver programs is included:– `do_ints` – a program that uses the functions you write to tokenize some sequences of integers and calculate various statistics along the way. You can look at the code in `do_ints.cc`, but do not make changes to that file. – `do_strings` – a program that uses the functions you write to split up some strings. You can see the code in `do_strings.cc`, but do not make changes.Both of these programs are complete **except for** the functions that are declared (but not defined) in `assign2-algos.decl.h`. You are responsible for implementing all of them. Make sure you put those in the `assign2-algos.h` file and nowhere else.### NotesRemember to continue with our routine of creating a `development` branch and making all changes to that branch, leaving `main` entirely alone. This will be necessary to submit the pull request at the end, signaling completion of your program to the graders.You will implement the required functions in the file `assign2-algos.h`. Do not commit/push any changes to the other files.You should feel free to create whatever files you want to test things locally, including writing your own simple programs to test small parts on their own, but none of them should end up becoming a part of your remote repo, and make sure you don’t change the files that have warnings not to change them.**DO NOT ADD OR COMMIT THE EXECUTABLE FILES CREATED WHILE COMPILING.** They are big and we will be compiling anyway.### Iterator Algorithms – Statistics and OutputIn `assign2-algos.h`, you will need to implement **all** of the templated functions that were declared in `assign2-algos.decl.h`.I recommend starting with the algorithms detailed in this section, as they will be slightly easier than the other set, which is described in the next section.#### `range_sum`Iterate over the range provided, add up the elements, and return the sum.#### `range_avg`Iterate over the range provided, add up and count the elements, then calculate and return the average (mean) as a `double`.#### `range_minval` Iterate over the range provided, keeping track of the minimum value found. Return that minimum value.#### `range_maxval` Iterate over the range provided, keeping track of the maximum value found. Return that maximum value.#### `range_count` Iterate over the range provided, counting the number of elements that occur within the range. Return that count.#### `print_range( ost, begin, end, pre, sep, post, width )`– `ost` is the `std::ostream` that the output should be printed to. In general, people will want to use `cout`, but you should use the one passed in so that this function can write to other streams when needed. – `begin` is an iterator to the beginning of the range to be printed – `end` is the iterator just past the last valid element of the range to be printed – `pre` is a string that gets printed one time before anything else – `sep` (separator) is a string that gets printed between each element (but not before the first or after the last) – `post` is a string that gets printed after all of the elements have been printed – `width` is the width, in characters, of the column in which the elements’ values are printed, or 0 (zero) if you do not want to use a fixed size. Set `std::setw` for details.This function should iterate over the range given, and print out the elements with the formatting determined by the other parameters. I’ve called it several times with different parameters in both driver programs, so you can get an idea of what’s expected from the reference output, if it’s not already clear to you.#### `histogram( begin, end, nums, N, divisor )`A histogram is a tool used in statistics where data is subdivided into several sub-ranges, which we will refer to as bins, and the frequency of occurrence of values within each range is measured. This is typically displayed graphically on a bar graph, but we just care about the numbers for this function.The basic description of what you need to do for this function is to iterate over every element in the range `[begin, end)`, find out which bin that element belongs in, and increment the count for the appropriate bin. Make sure the counts are already at zero before you begin.You can assume that any sequence provided for this will contain types that can be ordered (it’d break if you couldn’t).– `begin` – iterator at the beginning of the sequence we’re computing a histogram for – `end` – iterator one past the last element of the sequence we’re computing a histogram for – `nums` – an object supports the subscript `[]` operator to access integers containing the bin counts. The type is templated, so this could easily be an array or a `vector`, but it could also be any object that can be used in the appropriate way. This function will assume that it is already set up so you can read from and write to integers with indices from `nums[0]` to `nums[N-1]` without a problem. – `N` – the total number of bins, and an upper bound on the indices used with `nums` – `divisor` – divide the number by this and use the quotient to decide which bin this fits in. If the quotient is less than zero or greater than `N-1`, then do not increment any of the bins.### Iterator Algorithms for Splitting RangesThese functions, which you will implement using the iterator pattern, are useful for splitting a long sequence into smaller sub-sequences, which we shall call tokens.Although the `do_strings` driver program will use a `std::string` and the `do_ints` driver program will use a `std::vector` or a `std::list` to provide the iterators your functions will be called with, you should make sure that your algorithms are written in such a way that *any* forward iterator (or better) can be used without having to rewrite your function.We have not yet covered *exactly* what that means in lecture, but make sure you follow these rules:– While you can store your iterator’s current position into another iterator to keep track of where you were, you cannot rewind an iterator. Assume there is no `–` available for that. – Do not assume that it’s possible for your iterator to move more than one step at a time. Do not try to use pointer arithmetic or subscript operators, as this needs to be able to work on sequences that don’t support random access.Note that `std::string` can work like any other STL container, in that it has `begin()` and `end()` methods that can be used to iterate over the individual characters in the string. Similarly, you could use these algorithms with character arrays if you pass a pointer to the 0th element as its “begin”, and a pointer to the element after the last valid character (where the null character would be in a null-terminated string) as its “end”.#### `iter_token_info`This a `struct` (If you’re not familiar with structs, think of them as classes but with everything public by default). It will be used by the `get_next_token_*` functions to track where successive calls left off so they can continue until the end.– `b` – Your functions will be responsible for setting this iterator to point to the beginning of the token found. – `e` – Your functions will be responsible for setting this iterator to point right after the last element of the token found. – `n` – Your functions will be responsible for setting this iterator to point the beginning of the next token, or to then actual end of the range if there are no further tokens. – `begin()` – Returns an iterator to the beginning of the token that was found. This is useful because it allows you to use the range-based for loop on this to iterate over the sub-range represented. – `end()` – Returns the iterator representing the end of the half-open range representing the token that was found.#### `get_next_token_strict ( begin, end, delim )`, `get_next_token_greedy ( begin, end, delim )`These functions will start at `begin` and iterate until it either reaches the `end` iterator, or finds an element in the range that has the value `delim`.Your function will be responsible for setting the members of the `iter_token_info` returned appropriately. The `b` will be set to the iterator representing the beginning of the token, and the `e` member will be set to the location immediately past the end of the token, or to `end` if we reach the end of the input range.The `n` member of the `iter_token_info` struct returned must point to the beginning of the next token, or to the end of the range if no more tokens are to be found. How this is determined will be the main difference between the “strict” and “greedy” versions.– `begin` – Where to begin the search for a delimiter. – `end` – The end of the range to search. If we reach this, there are no more elements to form tokens with. – `delim` – the delimiter value, when it is found in the range, it is used to indicate that one token has ended#### Strict vs. GreedyFor the “strict” version, every delimiter begins a new token, and a delimiter found immediately after another delimiter will indicate the presence of a zero-length token. This is useful for situations like tab- or comma-separated values files, where you want the delimiter to start a new field and would actually like to be able to leave fields blank.For the “greedy” version, once a delimiter is found, the next token starts at the next position that is not a delimiter. That means that if we have several delimiters in a row, they are “eaten” and do not indicate empty tokens. One time this can be useful is in handling for whitespace in strings when you don’t want the number of spaces to matter, which is the case when parsing HTML or similar languages.“` // Let’s do an example tokenizing of integers using 0 as the delimiter source sequence: { 100 200 300 0 0 0 5 6 0 7 8 9 }strict token 0: { 100 200 300 } strict token 1: { } // empty strict token 2: { } // empty strict token 3: { 5 6 } strict token 4: { 7 8 9 }greedy token 0: { 100 200 300 } greedy token 1: { 5 6 } greedy token 2: { 7 8 9 }“`### How To SubmitLike the other assignments for this semester, we will be doing submissions through GitHub. Make sure you do all of your development in the `development` branch. You can commit as many times as you need to, but keep in mind that this will grow the size of your repo and you may run up against the quota on turing/hopper if it gets too big.When you are finished implementing everything required and the test programs are working properly, make sure you add, commit, and push the working version to the repo. Once that is done, **SUBMIT** a pull request but **DO NOT ACCEPT IT**.### Grading Considerations– Does it compile? Does it run? If it doesn’t compile and run on turing/hopper with the `Makefile` provided, no points will be awarded. – Does the output match? The output from your implementation will be tested against the output from the reference implementation for both driver programs. I have provided reference output for each of the driver programs, so you can compare your program’s output in advance. This output can be found in `do_ints.refout` and `do_strings.refout`. – Did you change files you’re not allowed to? There are warning messages at the top of several of the files telling you not to make changes. If you make changes to these, you will receive a grade penalty. You can write your own test programs if you’d like, but do not commit them or push them to the server, and make sure the only modifications that make it to GitHub are the required ones. – Did you indent your code? – Indentation aids in the readability of source code, and if you’re not indenting your code blocks, the grader will legitimately dislike you for it. I’m authorizing them to mark you off if you subject them to reading that. – Did you document your code? – You need a docbox at the top of every one of the files you’re required to change including: – Your name – Your zid – Your GitHub ID – Your course section – A description of what the program does – You should add a docbox for every function that you implement, explaining what it does and what each parameter is for. – Add other comments inside your code blocks describing what you’re doing and why. – The use of `doxygen` style comments is encouraged, but not required.
Introduction to Git and GitHub (x pts)The purpose of this assignment is for students to get set up on GitHub, learning the basic workflow that will be used for assignment submissions for the course.Note: If you are already reading this in your own GitHub repo, you can skip to the relevant portion.### Step 1: Get a GitHub AccountIn order to complete this assignment, you will need to have an account at [GitHub (`https://github.com`)](https://github.com). If you do not have one yet, it will be necessary to create one.### Step 2: Accept the Assignment InvitationYour professor will provide you with a link to the GitHub Classroom Assignment. You will need to click that invitation link and accept it. This will create a personalized `git` repo for you on GitHub that you will use to complete the rest of the assignment. GitHub will provide you with a link to that repo that you should keep, as it will be used in the steps below.### Step 3: Clone your Repo to Turing/HopperYou will need to clone the repo from the link that GitHub generates for you after acceptance of the invitation. This creates a local (to the NIU server) copy that can be edited as needed, and you can compile and test your code on this copy.`git clone YOUR_REPO_URL_GOES_HERE`When interacting with the remote (GitHub version) repo, you will be required to log in. GitHub used to accept text username/password authentication, but they made a decision to disable that authentication method, so you will need to choose one of the methods that still works and configure your Turing/Hopper session to use that when talking to GitHub.#### SSH Public Key Authentication (Recommended)One common method of authentication is to use asymmetric encryption. You generate a pair of cryptographic keys; one private (don’t ever share it), and the other public (this is the one you can share). You can use the `ssh-keygen` program on Turing or Hopper to generate your keys, and put the public key information in your GitHub account settings. This is more secure than the other option, and I recommend that you choose this.GitHub has documentation on how to do this: [https://docs.github.com/en/authentication/connecting-to-github-with-ssh/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent](https://docs.github.com/en/authentication/connecting-to-github-with-ssh/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent)John Winans recorded a video for a previous section of CSCI 340 where he went through these steps, which can be viewed at [https://www.youtube.com/watch?v=CdZa8MzLtjQ](https://www.youtube.com/watch?v=CdZa8MzLtjQ)#### GitHub Token AuthenticationYou can generate a token (a unique alphanumeric string used for authentication purposes) in the GitHub website’s settings, and make sure that the correct environment variable contains that token when the `git` command looks for it. This involves having your token in an environment variable that could potentially be read by other programs, so it’s not as secure as the SSH method above. There are instructions on the GitHub site if you want to go this route.### Step 4: Create a `development` branchA `git` repo can contain several simultaneous versions of your source code. The default branch is called `master` or `main`.You need to create a new branch, called `development`, and all of your work will be done on that branch.Creating the branch is as simple as typing `git branch development` in the directory you cloned the repo to.Once the branch is created, you can change to the new branch with `git checkout development`. Make sure you are in this branch when adding files and committing changes.**WARNING: YOU WILL LOSE POINTS IF YOU COMMIT ANY CHANGES IN THE `main`/`master` BRANCH.**### Step 5: Add Necessary Comments to the File and CommitWhen you clone the repo from GitHub, there will already be several files present. They implement a simple program that has been intentionally broken. **Before** we worry about fixing the program, we’re going to add some documentation, and commit that documentation to the repo.You must add a documentation box at the top of the `assign1.cc` file, in the following format:~~~~~ {.text} /********************************************************************************************** * NIU CSCI 340 Section YOUR_SECTION * * Assignment 1 * * YOUR FULL NAME – YOUR Z-ID – YOUR GITHUB USERNAME * * * * I certify that everything I am submitting is either provided by the professor for use in * * the assignment, or work done by me personally. I understand that if I am caught submitting * * the work of others (including StackOverflow or ChatGPT) as my own is an act of Academic * * Misconduct and will be punished as such. * * * **********************************************************************************************/ ~~~~~ **Make sure you provide your own name, section number, ZID, and GitHub username in this comment. If the grader cannot find this information, they will not be able to assign you a grade for your work.****DO NOT MAKE ANY OTHER CHANGES TO THE FILE AT THIS STAGE. THERE IS AN INTENTIONAL BUG THAT YOU SHOULD LEAVE UNFIXED FOR NOW**Once you’ve added the comment to your file, save the changes, and use `git` to add the changes to the `development` branch. This can be achieved with `git add assign1.cc`.Having added the file to the list of files whose changes will be committed, you will now be ready to do your first commit. This is as simple as typing `git commit` and typing an appropriate description of the changes you made to the code at the prompt provided.Note that commits are done to the local copy of the repo (on turing or hopper). When you’re ready for those changes to appear on the remote, GitHub repo, you will need to push those changes over.### Step 6: Fix What is BrokenIf you run `make`, you will notice that the current code does not compile. There was an error intentionally left in the C++ file. It is not hard to find, so go ahead and fix it, then repeat the process of adding the file, committing the new change separately from the commit where the comment was added.### Step 7: Push your local commits to the remote serverGraders won’t have access to your local copy of the repo, so you’ll need to make sure that the commits that you have done are present on the remote server. This is done with the command `git push`. When you run this, `git` connects to the remote server (GitHub) in this case, and all of the changes you’ve commmitted are sent to the server, where they will be visible to anyone with access to the remote repo.### Step 8: Signal your completion of the assignment by adding a pull requestWhen you have completed the earlier steps, go to your repo link in your web browser and add a pull request. A pull request is a request to have changes present in a branch merged into the `main`/`master` branch. It allows teams to work separately and have their work safely added in when done.**We** are using pull requests because they’re a good way of signaling that you have completed your assignment. You will not be able to add a pull request if you did all of your changes in the `main` or `master` branch, so it is very important to have followed the instructions to do your work in the `development` branch only.**DO NOT ACCEPT THE PULL REQUEST. JUST CREATE IT AND LEAVE IT THERE FOR THE GRADER TO SEE**### Grading Considerations– The comment inserted in the first commit should match the one provided, with your information inserted in the appropriate locations. – Did you put your name/section/zid in the comments? If we can’t link the repo to your real identity, we can’t give you any points. – You must have created and used the `development` branch. No changes should be committed in the `main` or `master` branch. – The second commit must fix the error in the file, and it must compile. Do not commit before this is the case. – The TA will be checking your repo for the pull request before considering your work to have been submitted. Make sure you make the pull request before the assignment deadline. – Although you can make whatever changes you want to your local repo, no changes other than the ones required should be committed to the repo.
Consider a basic multi-layer perceptron (MLP) with three layers, characterized by the following weight matrices: • W0 ∈ R 2×2 • W1 ∈ R 3×2 • W2 ∈ R 1×3 Answer the following questions regarding the structure and behavior of this neural network.1.1 Basic MLP a) How many weights are there in this neural network? Show the calculation. b) Compute the output of the network yˆ for the input x = (1, 1)⊤. Use the weights: W0 = 0.1 0.4 −0.5 0.6 , W1 = 0.2 −0.1 0.5 0.4 0.3 −0.6 , W2 = [0.7, −0.4, 0.9]Assume ReLU activation and show the calculation steps. c) Compare the effect of using ReLU versus sigmoid activation in layer 1 only. Compute the output for the same network and input x, and summarize the differences. d) Compute ∂L ∂W2 , assuming L = 1 2 (ˆy − y) 2 . Show its shape and intermediate steps for the forward and backward passes.1.2 Revised MLP-1: MLP with Missing Weights a) For the following network structure, calculate the output yˆ for x = (1, 1)⊤: W0 = 0.2 0.3 ⋆ −0.1 , W1 = 0.4 ⋆ ⋆ 0.6 −0.2 0.1 , W2 = [0.3, 0.5, ⋆] Missing entries (denoted ⋆) are zero. Use ReLU activation. b) Assume layer-wise normalization (mean subtraction, variance normalization) applied to z1 before activation. How does it affect the output? Compute for the network above.c) Debugging and Improving a Neural Network with PyTorch The code file mlp weights.py provides a PyTorch code template for you to experiment with the multi-layer perceptron (MLP) from part (b), which contains missing weights. The network is implemented with explicit forward passes for more transparency during training.Task: Debug and modify the given neural network so that it converges effectively during training. Initially, the missing weights are set to zero, which prevents the network from learning effectively. Your goal is to make modifications that enable successful convergence and analyze the outcomes.Constraints: • Use stochastic gradient descent (SGD) as the optimizer. • Maintain the three linear transformations defined by weight matrices W0, W1, and W2. Do not add or remove layers.• You may modify elements within each layer (e.g., activation functions, adding bias terms), but keep the given structure of the weight matrices intact.Steps to Follow: i) Initial Run: Run the provided network as-is. Document the loss curve and explain why the network fails to converge. ii) Modify and Observe: Make one modification at a time. Document each noteworthy change, including plots showing the effects on loss and parameter evolution.iii) Analyze: Compare the different modifications. Which ones improved convergence? Discuss how the initial zero values for weights led to degenerate learning, and explain how your modifications addressed these issues. Note: Since we have only a single input and output, the ”stochastic” element of SGD is not present here—it effectively functions as standard gradient descent.In Your Report: • Describe the initial issues observed. • Summarize the modifications you made and why. • Include plots for the loss curve and parameter evolution. • Analyze the impact of different changes, focusing particularly on the role of initialization in achieving effective learning.Time Frame: Spend approximately 30-60 minutes experimenting until you achieve a satisfactory solution.d) Exploring the Role of Stochasticity in Overcoming Initialization Issues Consider the problem of zero initialization in neural networks. Could true stochastic gradient descent (SGD) overcome the issue of zero-initialized weights? To better understand this, please answer the multiple-choice questions by editing the text file sgd mc answers.txt located in the A3 folder. Don’t answer them in the report you submit.Below are the multiple-choice questions included in the file: a) Why is stochastic gradient descent (SGD) called ”stochastic”? (a) Because it uses random mini-batches of data to approximate the gradient. (b) Because it computes the gradient over the entire dataset. (c) Because the learning rate changes at each step.(d) Because it always converges faster. b) What is the effect of initializing all weights to zero in a neural network? (a) All neurons in a layer receive identical gradients and learn the same features. (b) The network will converge faster due to symmetry.(c) Stochastic updates will make neurons learn distinct features. (d) Zero initialization always helps prevent overfitting. c) Could true stochastic gradient descent overcome the problem of zero-initialized weights? (a) Yes, because random mini-batches would introduce sufficient variability.(b) No, because all neurons have identical weights and thus receive identical gradients, regardless of mini-batch variability. (c) Yes, because SGD inherently breaks symmetry. (d) No, but adding bias terms would always fix it.This assignment will focus on applying Support Vector Machines (SVM) to a dataset representing simplified customer behavior metrics. The objective is to train an SVM classifier to distinguish between two customer segments based on their engagement level with a service.The dataset, D, contains the following features for each customer: • x1: Average number of visits to the service per week. • x2: Average spending per visit (in tens of dollars).The labels are defined as follows: • +1: High-engagement customer segment. • −1: Low-engagement customer segment. The given dataset consists of the following samples: D = {((2, 6), 1),((6, 2), −1),((4, 6), 1),((5, 3), −1)} Recall the soft-margin SVM formulation: min w,b 1 2 ∥w∥ 2 + C X N i=1 ξi subject to: yi(wT xi − b) ≥ 1 − ξi , ξi ≥ 0, ∀i a) Feasibility of (w1, b1) Given w1 = (0.5, −0.5) and b1 = 1, determine whether (w1, b1) is a feasible solution to the soft-margin SVM problem. Verify if all the data points satisfy the constraint for the given w1 and b1.b) Determine the Optimal Solution (w∗ , b∗ ) Determine the optimal solution (w∗ , b∗ ) for the soft-margin SVM problem for the given dataset. Use a linear kernel for simplicity. Create a coordinate system showing the data points (marking positive and negative examples), the optimal decision boundary line w∗T x − b ∗ = 0, and the margin boundaries parallel to the decision boundary at distance 1/∥w∗∥ from the decision boundary.• Assume C = 1. Explain the impact of different values of C on the decision boundary. • Calculate the objective value of the primal solution.c) Support Vectors and Their Role Identify the support vectors for the given dataset and explain their role in defining the decision boundary. Which data points are support vectors in this case, and why?d) Exploring the Dual SVM Solution Determine the optimal objective value for the dual SVM problem and find the corresponding dual variables (λ1, λ2, . . .). Use the generalized Lagrangian approach to derive the weight vector and explain how the dual formulation relates to the primal SVM solution.Use the provided Python script (solve lambdas.py) to determine the optimal objective value for the dual SVM problem. Complete the TODO in the code to define the Gram (Kernel) matrix K. Once you have filled this in, run the code to compute the dual variables (λ1, λ2, . . . ).a) Fill in the Kernel Computation: Complete the computation for the Gram matrix K in solve lambdas.py. b) Run the Code: Execute the script to determine the optimal λi values and identify the support vectors. c) Derive the Weight Vector: Using the generalized Lagrangian for the SVM, take the partial derivative with respect to the weight vector w and set it to zero to derive the weight vector. Refer to the lecture slides on the SVM dual for guidance on the critical point condition involving w and λi . This step will help you link the dual variables (λi) to the weight vector.d) Verification Task: Use the computed λi values from the script to manually verify the optimal weight vector w∗ using the derived formula. Compare your calculation to the value computed by the code. e) Relationship Between Primal and Dual: Explain how the derived w∗ relates to the primal SVM problem and how the support vectors influence the solution.f) Considerations for Scaling to Larger Datasets Discuss how the analysis methods used in this assignment would change if the dataset were significantly larger, for instance, involving 100,000 customers. Consider aspects such as computational efficiency, model complexity, and practical implementation challenges.
Let’s consider a scenario where we have a binary classification problem in machine learning, and we want to calculate the KL divergence between two probability distributions: the true distribution P(Y ) and the predicted distribution Q(Y ), where Y represents the class labels (0 or 1). Suppose we have a dataset with 100 samples, where the true distribution P of labels is as follows: • Class 0: 60 examples • Class 1: 40 examplesLet’s say our machine learning model makes predictions on this dataset, and the predicted probabilities Q for each class are as follows: • Predicted probabilities for Class 0: p • Predicted probabilities for Class 1: 1 − p with 0 < p < 1.a) Calculate the value of true distribution Entropy H(P) and write down the Entropy of the predicted distribution H(Q). b) Calculate the minimum cross-entropy Hmin(P, Q) and find the corresponding probability p. Hmin(P, Q) := min p [− X 1 i=0 P(Y = i) log Q(Y = i)]. c) Prove that KL divergence can be found with the following relationship between the cross entropy H(P, Q) and the entropy H(P) DKL(P||Q) = H(P, Q) − H(P). d) What is the minimum KL divergence of the prediction DKLmin (P||Q)?Consider a simple linear model y = wx + b + ϵ, where x, y, w, b ∈ R and ϵ ∼ N (0, σ2 ). Assume prior information such that w ∼ N (0, σ2 w) and b ∼ N (0, σ2 b ). The regularization parameters λw and λb are defined as λw = 1 σ2 w and λb = 1 σ 2 b , respectively. The training data consists of 20 data points, with code provided in this Jupyter Notebook.(a) Identify the prior means and covariances. State the prior means and covariance values for both w and b based on the given prior information. (b) Explain and implement the formula for [wMAP, bMAP] (Maximum A Posteriori estimation). State the expression for [wMAP, bMAP] in terms of the design matrix X (with an added column of ones for the intercept), the output vector y, and regularization terms. Provide a high-level explanation of the derivation steps. A detailed derivation is not required as it is available in the provided slides. Focus on summarizing the intuition behind the MAP estimate and implement the formula in code.(c) Calculate the posterior means and covariances for w and b. Provide expressions for the posterior mean and covariance matrix for the parameter vector [w, b]. For a detailed derivation and further explanation on Bayesian linear regression, see Probabilistic Machine Learning: An Introduction by Kevin P. Murphy, Chapter 7, Section 7.6.1, noting VN as posterior covariance matrix.(d) Interpret the posterior mean and covariance. Explain what the posterior mean and covariance represent for w and b after observing the data, and describe the practical significance of w.(e) Sample models from the posterior distribution and plot the results. Use the posterior mean and covariance to sample multiple sets of parameters [w, b] from the multivariate normal distribution. Plot the training data along with multiple linear models represented by these samples. Display these sampled models as semi-transparent lines to visualize the uncertainty in the predictions.In this question, we implement iterative algorithms to solve a nonlinear optimization problem. As practical application we will optimize a nonlinear model of chess win probability given ELO ratings of the players, using data from lichess.org.Please provide the code for your answers in this Jupyter Notebook (there are total 4 ”#” in this question). a) Define the objective function. Implement your chosen objective function. You may choose between the following: – Option (i): A simpler quadratic function: f(x, y) = x 2 + (y − 2)2 2– Option (ii): The cross-entropy loss for the sigmoid model, which better represents the chess ELO win probability data. Implement this function and ensure the code correctly calculates the chosen loss value and its gradient wrt the two model parameters for the given data.Note: You have the option to proceed with either one of the two objective functions. The first one is an optional, simpler fallback that might help you to get started. There is a -5% penalty on this question, if you choose not implement the cross-entropy loss option (ii).b) Implement a basic Gradient Descent algorithm for the objective function (i) or (ii). • Use step size of 0.2, total iterations of 100, and initial point of (−10, 10) for the objective function. • Change the step size to 0.01. Report and plot your observation.c) Implement the Adam algorithm for the chosen objective function. • Use step size of 0.2, total iterations of 150, and initial point of (−10, 10) for the objective function. Use default values for other parameters. Does the solution converge to the minimal objective value? Report and plot your observation.d) Finally, use the best parameters that you found via Adam (or gradient descent) to draw the best fitting sigmoid function model on top of the data points. Briefly discuss this result in comparison with the linear fit from the earlier question.
a) Let U be a subspace of R 5 defined by: U = x1 x2 x3 x4 x5 ∈ R 5 : x1 = 3×2 and x4 = 2×5 Find an orthonormal basis {u1, u2, u3}. b) Prove that the set {u1, u2, u2 + u3} is linearly independent.2. SVD and Eigendecomposition Rotation Matrices and Practical Applications: Consider the matrix A = 1 2 2 3 3 1 . a) Define the matrix B = AA⊤ and compute the matrix B. b) Singular Values from Eigenvalues: The Eigendecomposition (EVD) of matrix B is given as: B = UΛU ⊤where U is the matrix of eigenvectors, and Λ is the diagonal matrix of eigenvalues. • Explain how the eigenvalues of B relate to the singular values of A. • Compute the singular value matrix Σ for A, given that the eigenvalues of B = AA⊤ are 25, 3, and 0. c) Consider an SVD of a matrix D as follows: D = UΣV ⊤ = ” √ 3 2 − 1 2 1 2 √ 3 2 # 5 0 0 2 ” − 1 2 − √ 3 √ 2 3 2 − 1 2 #⊤ A matrix Rθ ∈ R 2×2 is a 2D rotation matrix if it has the following form: Rθ = cos θ − sin θ sin θ cos θ where θ ∈ R. Geometrically speaking, Rθv rotates v counterclockwise by angle θ, for any v ∈ R 2 , as shown in Figure 1.Figure 1: In this case, x = (1, 0) and y = (0, 1) are both rotated by θ = π 4 .Show that U and V ⊤ are both rotation matrices and find their corresponding rotational angles θU and θV ⊤ . 3. Taylor Expansion Given #»x =x1, x2, x3 ⊤ , consider a nonlinear function f : R 3 −→ R as follows: f( #»x) = 5x 2 1 + 3x 2 2 + 2x 2 3 + 4x1x2 − 2x1x3 + 6x2x3 a) Compute the Gradient and Hessian matrix of f. b) Find the second order Taylor Expansion at the point #»x0 = [0, 0, 0]⊤. c) State whether f is convex, concave, or neither convex nor concave. Prove your claim.4. Convexity For any #»x, #»y ∈ R n and any t ∈ [0, 1], a function f is said to be convex if it satisfies any of these conditions: • f(t #»x + (1 − t) #»y ) ≤ tf( #»x) + (1 − t)f( #»y ) • If f is differentiable: f( #»y ) ≥ f( #»x) + (∇f( #»x))⊤ ( #»y − #»x) • If f is twice differentiable: Hf( #»x) ⪰ 0 a) Given x ∈ R and only using the definition of convex functions given above, prove that the rectified linear unit function, ReLU(x) := max(x, 0), is convex.5. Linear Regresssion – House Price Prediction with Polynomial Features and Ridge Regression You are working on predicting house prices in a real estate market using a dataset that consists of 500 examples, each with multiple features: number of rooms, house age, area size, etc. The target variable is the house price. You decide to apply linear regression and Ridge regression (a regularized form of linear regression) to build predictive models.Your goal is to assess the generalization of these models using cross-validation and to experiment with different polynomial degrees and regularization strengths to improve the model’s performance. Data Loading: Use the following code to load the Boston Housing dataset from GitHub and initialize the DataFrame. For the model, only use the variables rm (number of rooms) and lstat (lower status population, percentage), and the target variable medv (median house value in $1,000s).import pandas as pd # Load Boston Housing Data from GitHub url = “https://raw.githubusercontent.com/selva86/datasets/master/BostonHousing.csv” df = pd.read_csv(url) # Features: ’rm’ (number of rooms) and ’lstat’ (lower status population, percentage) X = df[[’rm’, ’lstat’]] y = df[’medv’] # Target: ’medv’ (median house value in $1,000s)Implementation Hints: For managing your dataset, use pandas dataframes and for the models and training tools, utilize scikit-learn. Plotting should be done with the built-in functions or using matplotlib. You can refer to the official scikit-learn documentation for functions like train-test split, cross-validation, linear regression, and Ridge regression.For coding environments: • You can work in a Jupyter notebook in Google Colab, and export it as a .py script for final submission. • If you are already using VS Code, consider using #%% cell separators in your Python script, allowing you to run parts of your script like Jupyter notebook cells.Ensure your script includes the code for each task, such as MSE computation or the best parameter choices, and attach the result outputs to your assignment report in PDF format.a. Train-Test Split and Cross-Validation for Linear Regression with Polynomial Features Split the dataset into a training set (80%) and a test set (20%). Use 5-fold cross-validation on the training set to evaluate the performance of linear regression models with polynomial features. For each polynomial degree (from 1 to 5), compute the average mean squared error (MSE) over the five folds and report your results. Hint: Use PolynomialFeatures from scikit-learn to create polynomial features of different degrees. When using the cross val score function, set the scoring parameter to neg mean squared error.b. Cross-Validation for Ridge Regression with Polynomial Features Ridge regression introduces a regularization term controlled by a hyperparameter α. Perform 5-fold crossvalidation on the training set with Ridge regression, using polynomial features (degrees 1 to 5) and different values of α (e.g., 0.1, 1, 10, 100). Use grid search to find the best α and the optimal degree, and report both the values that minimize the cross-validation error along with the corresponding average MSE. Hint: Use GridSearchCV from scikit-learn to automate the search for the best regularization parameter α.c. Generalization and Test Set Performance Now that the best polynomial degree and regularization strength have been identified from part (b), train both the linear regression model and the Ridge regression model on the training set, and evaluate their MSE on the test set. Compare the performance of the two models, and discuss which model generalizes better to unseen data and why. Hint: Use mean squared error from scikit-learn to evaluate the models on the test set.d. Theoretical Considerations Explain why the regularization in Ridge regression helps prevent overfitting, especially when using polynomial features. How does the choice of the regularization parameter α and the polynomial degree influence the model? What might happen if α is too small or too large, or if the degree is too high?
1. [17 points] Visit metrics.torproject.org to answer the following questions about Tor: (a) [4 points] Give the total amount of advertised bandwidth of relays with the “Guard” flag (but not the “Exit” flag) and relays with the “Exit” flag (but not the “Guard” flag) on 2020-02-01. Which is more? Give one reason to explain this phenomenon.(b) [4 points] Give the median download rate of a file (in bytes per second) for a 50 KiB file and a 5 MiB file to the op-hk onion server on 2020-02-01. Can you explain the difference? (c) [5 points] The download times measured in the above were done on circuits with three nodes, randomly chosen across the globe. Based on these figures, estimate the median download rate for a 50 KiB file if Tor used only one node. You may need to make certain assumptions; write them down.(d) [4 points] Determine the growth (as a ratio) in the bandwidth spent on answering directory requests between 2017-01-01 to 2018-01-01. A directory request is a list of all Tor nodes sent by directories when a user connects to Tor. What is the main cause of this growth? Use figures to support your conclusion. 12. We have four data privacy techniques: 1. k-anonymity 2. Differential privacy 3. Secure multiparty computation (SMPC) 4. Private information retrieval (PIR) For each scenario below, two of the four data privacy techniques will be proposed to resolve the challenge. Choose the correct one, explain why it is suitable, and why the other choice is not suitable.(a) [4 points] A failing streaming entertainment company wants to revitalize its business by improving its recommendation algorithm. The recommendation algorithm takes in private data such as user location, viewing hours, and demographic information, and outputs recommendations of what shows to watch. The company will run a public contest and select the best algorithm. To run the contest, they need to give contestants access to millions of entires of private data, which is a violation of privacy if not done with a privacy-preserving method. Proposals: k-anonymity, SMPC.(b) [4 points] You want to buy a new smart device that encourages a healthy lifestyle by monitoring your daily exercise. The device needs to track your movement on a map to know how much calories you are actually expending (e.g. hiking and swimming is different from walking). However, you consider this to be a privacy risk: you do not want the app to know where you are at all times. A new company making these smart devices is willing to use a data privacy technique to protect your privacy. Proposals: differential privacy, PIR. (c) [4 points] You would like to purchase a new web domain. However, you are aware of the practice of cybersquatting; people may purchase the domain first if they know it is in demand, and sell it to you at an elevated price. You want to know if the domain is still available, but you are worried that attempting a DNS query for the domain will lead to some DNS servers purchasing it immediately for cybersquatting. To assure potential customers that it is not malicious, a DNS server is willing to cooperate with you and implement a privacy-preserving algorithm. Proposals: kanonymity, PIR.(d) [4 points] People are anxious to know if they are living in the same apartment as someone infected with the infectious CROW disease. The hospital that holds all this information is willing to run a privacy-preserving algorithm with worried potential infectees to check if someone living in their apartment has been infected. Proposals: differential privacy, SMPC.Error Correcting Codes (ECCs) can be used in unsafe transmission or storage devices to improve reliability by providing redundancy. Unlike checksums, ECCs can automatically correct errors up to a certain number of bits. In this question, you will be asked to implement the general Hamming code, which can correct any 1-bit error in a general string. (Do not use a Hamming code library — it should be your own code.) The specifications of the Hamming code are as follows; it has been slightly modified to discourage code sharing from other Hamming code implementations.1. Write the input data string as a bitstring according to ASCII. 2. Choose enough parity bits and intersperse the data bits with parity bits, so that the i-th parity bit pi is followed by exactly 2i−1 − 1 data bits. Denote the i-th bit of H as Hi ; the first bit is H1. Denote the length of H as |H|. 3. Let B(x) be the bitstring representation of the integer x, for example, B(5) = 00101. 4. Define each Mi to be a set of specific bit positions in H, such that Mi is the set of integers 1 ≤ x ≤ |H| where the i-th least significant bit of B(x) is 1. 5. Set the parity bit pi to be the XOR of all the bits of H in the positions indicated by Mi , except pi itself, which is always located at H2 i−1 : pi = M x∈Mi{2 i−1} Hx Here is a more detailed explanation of Mi . Consider the integer x = 10, so B(10) is 1010. Then the 1st least significant bit is 0, the 2nd is 1, the 3rd is 0, and the 4th is 1 (reverse the bitstring). So x belongs to M2 and M4, not to M1 and M3.To work out an example: 1. The input data string is “ab”, which becomes 0110000101100010 (16 data bits). 2. We need five parity bits, p1, p2, p3, p4, p5, as follows: H = p1p20p3110p40001011p500010 p5 can be followed by up to 15 data bits, but we ran out of data bits, so we stopped there. H3 = 0 and H8 = p4. |H| = 21. 3. For example, B(20) = 10100. 4. M1 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21} M2 = {2, 3, 6, 7, 10, 11, 14, 15, 18, 19} M3 = {4, 5, 6, 7, 12, 13, 14, 15, 20, 21} M4 = {8, 9, 10, 11, 12, 13, 14, 15} M5 = {16, 17, 18, 19, 20, 21} 3 CMPT479 A3 5. p1 = H3 ⊕ H5 ⊕ H7 ⊕ H9 ⊕ H11 ⊕ H13 ⊕ H15 ⊕ H17 ⊕ H19 ⊕ H21 = 0 p2 = H3 ⊕ H6 ⊕ H7 ⊕ . . . = 1 p3 = H5 ⊕ H6 ⊕ H7 ⊕ . . . = 0 p4 = . . . = 1 p5 = . . . = 1 (a) [20 points] Write a program that will automatically generate the correct parity bits for any input string. The input string will be the first argument of the program.Your program, called a3a, should write the parity bits in the correct order to stdout (e.g. cout or print) as characters, ”0” or ”1”. Continuing the above example, if the program is called with: ./a3a ab The program should display: 01011 (b) [20 points] Write a program that will automatically correct any one-bit error in either the parity or the data string. The parity will be the first argument of the program, and the data string will be the second argument of the program. Your program, called a3b, should output the corrected parity bits to the first line of stdout, and the corrected data string to the second line of stdout. If there is no correction to be made, you should still output the original parity bits and the data string. For example, if I run your program with: ./a3b 01011 ac Your output should be: 01011 ab The program will always be tested with the correct number of parity bits, and there will either be a one-bit error in the parity or the data string, or no error. Either type of error should be fixed. Also, note the meaning of an ASCII one-bit error: “a” (01100001) can become “i” (01101001), but “a” cannot become “b” (01100010) because that would be two bit flips.(c) [7 points] Submit two sentences in files sentence1 and sentence2, such that they have the same Hamming code (as output by part a). They should all be logical and grammatically correct sentences with no typos, and they should all include your @sfu.ca SID. Any ASCII characters that are not letters, numbers, or basic punctuation will be removed. Hint: It may be easier to construct these sentences if you use numbers somewhere in your sentence.Submission instructions All submissions should be done through CourSys. Submit the following programs: a3.pdf, containing all your written answers. Files for the programming assignment: sentence1, sentence2. Code for the programming assignment, detailed below: For the programming assignment, submit your code; do not submit any compiled files. C++: Submit a3a.cpp, a3b.cpp. I will compile them and call ./a3a . Python: Submit a3a.py, a3b.py. I will call python a3a.py .Java: Submit a3a.java, a3b.java. I will compile with javac a3a.java and then call java a3a . If there is a Makefile in your folder, the Makefile will override all of the above. This implies if you are not writing in C++, Python, or Java, you must include a Makefile. Keep in mind that plagiarism is a serious academic offense; you may discuss the assignment, but write your assignment alone and do not show or send anyone your answers and code. The submission system will be closed exactly 48 hours after the due date of the assignment. Submissions after then will not be accepted unless you have requested an extension before the due date of the assignment. You will receive no marks if there is no submission within 48 hours after the due date.
1. There is an error in each of the following uses of cryptography that degrades its security. Identify the mistake and explain how it should be done instead.(a) [4 points] Alice wants to send Bob an encrypted e-mail. She generates two ECDH key pairs: one for encryption and one for signing. She uses the public encryption key to encrypt the e-mail, and ✿✿✿✿✿✿✿✿✿ attaches ✿✿ a ✿✿✿✿✿✿✿✿✿✿ signature✿✿✿✿✿✿✿✿✿ created ✿✿✿ by✿✿✿✿✿✿ using✿ the private signing key to sign a SHA-256 hash of the e-mail. The e-mails are ✿✿✿✿✿✿ e-mail✿✿✿ is ✿ sent through SMTP. She publicizes both public keys.(b) [4 points] Bob manages a website. To store Alice’s password securely, Bob first asks Alice to encrypt it using 128-bit AES with a secret key (the key is shared with Bob). Then, Bob stores a hash of the encrypted version of the password using SHA-512 and also stores the secret key. (c) [4 points] Alice and Bob use the Diffie-Hellman protocol to establish a shared 256- bit secret key. After doing so, Alice wants to send Bob her bank account number so Bob can transfer money to her. Alice encrypts her bank number using the shared 256-bit secret key under AES in counter mode.(d) [4 points] In a private end-to-end encrypted messaging app, Alice adds Bob as a friend, which involves downloading his public 512-bit RSA key from a trusted server manging the app. To ensure that the public key is correct, the server uses its private 256-bit ECC key to sign it, which is verified by the corresponding public key that comes with the app. Having Bob’s public key allows Alice to start creating secure connections with him.2. [14 points] Cryptography relies on a series of assumptions regarding computational difficulty and key use. In each of the following cases, a commonly held assumption is broken. Discuss the impact of breaking that assumption, focusing on current cryptographic tools, how people interact with them, and how we ✿✿✿✿✿✿✿✿✿✿ (including✿✿✿ all✿✿✿✿✿✿✿✿✿ relevant✿✿✿✿✿✿✿✿ parties ✿✿✿✿✿ such ✿✿ as✿✿✿✿✿✿✿✿✿✿✿✿✿ cryptosuite ✿✿✿✿✿✿✿✿✿✿✿✿ developers)✿ should respond to these discoveries. (a) [3 points] A quick polynomial algorithm for integer factorization has been found. (b) [4 points] The private signing key used by Facebook to sign HTTPS certificates was stolen by an unknown group two months ago. (c) [3 points] An easy way to determine the input corresponding to a given SHA-2 hash has been found. (d) [4 points] Large, practical quantum computers have been constructed. (Hint: Start with Shor’s algorithm.)In this assignment, we will write programs to automatically break some weak ciphers. Please make sure to read the submission instructions carefully. Two-Time Pad [20 points] Two files, ctext0 and ctext1, have been sent to you by e-mail.Those two files were encrypted using the same one-time pad. They are exactly 400 ✿✿✿✿ 600✿ bytes each, and they both come from popular English Wikipedia articles ✿✿✿✿✿✿✿✿✿✿✿✿ downloaded✿✿✿✿ on ✿✿✿✿✿ 27th✿✿✿✿✿✿ June ✿✿✿✿✿✿✿✿✿ (around ✿ 4✿✿✿✿✿✿ PM). Find the contents of both files using crib-dragging, and submit them as ptext0 and ptext1. You can flip around ptext0 and ptext1. You may assume the plaintext to consist only of ASCII characters with the following byte values, all ranges being inclusive of both ends: • Symbols: 32 to 41, 44 to 59, 63, 91, 93. • Capital letters: 65 to 90. • Small letters: 97 to 122. The ctext file was derived by XOR’ing the plaintext (as ASCII bytes) with the 400-byte ✿✿✿✿✿✿✿✿✿ 600-byte key.Each byte of the ctext file would be the XOR of the corresponding byte of plaintext with the corresponding byte of the key (written as bit strings). If you cannot find the full texts, submit as much of the text as you can find. Padding Oracle Attack [30 points] AES — the standard block cipher in use today — had a padding algorithm that introduced vulnerabilities when combined with CBC (Ciphertext Block Chaining). In this assignment, we will investigate why it was insecure. In fact, the attacker can arbitrarily decrypt and encrypt in AES without knowledge of the key, and even without any understanding of the operations of AES. The following is an adaptation of Vaudenay’s “Security Flaws Induced by CBC Padding — Applications to SSL, IPSEC, WTLS …” paper. However, the padding scheme is intentionally different from the one used in that paper, to discourage plagiarism. A solution derived from that paper will not work for this assignment.AES encrypts plaintexts in blocks of 16 bytes at a time. If there are fewer than 16 bytes of plaintext data, AES adds padding bytes to the end of the plaintext until there are 16 bytes exactly. (During decryption, those padding bytes will be discarded.) If there are more than 16 bytes of data, AES operates on each block one by one in order, and pads the final block to 16 bytes. If there are n real bytes, then the bytes to add is exactly 16 − n copies of n. For example, suppose the plaintext we want to encrypt is: x 0 = (CA013AB4C561)16In the above, x 0 is written in hexadecimal notation, and it has 6 bytes. We want to add 10 bytes to make 16 bytes, so we will add the byte (06)16 ten times to make x, the padded version of x 0 : x = (CA013AB4C56106060606060606060606)16 Note that the minimum amount of padding is 1 byte: that is to say, if the original plaintext has a multiple of 16 bytes, then we will need to add 16 bytes of padding of (00)16 (byte 0). There will be a whole block of padding at the end. The maximum value for padding is one byte of (0E)16 = 15 ✿✿✿✿✿✿✿✿✿✿✿ (0F)16 = 15. After padding x 0 to x, we can perform AES encryption (denote the operation as C) on x to get the ciphertext C(x). C is dependent on the secret key K and the initialization vector IV ; the attacker knows IV because it is sent in the clear.Suppose x contains N blocks of data (in other words, the size of x is 16N bytes), denoted as (x1|x2| . . . |xN ). | is the concatenation operation, meaning that the bytes of x1 are followed by that of x2, and then by x3, and so on. After encryption, the resulting ciphertext is (IV |y1|y2| . . . |yN ). In CBC mode, we have: y1 = C(IV ⊕ x1) yi = C(yi−1 ⊕ xi) for i = 2, 3, . . . , N The inverse of C, the AES block encryption function, is denoted as D, the block decryption function. Note that both C and D do not perform any padding on their own; they both input and output 16 bytes of data. For any 16-byte block z, D(C(z)) = z. We will now break AES in CBC mode using a padding oracle.A padding oracle is some entity that tells the attacker if the padding of some ciphertext (IV |y1| . . . |yN ) is correct after decryption. In other words, it decrypts (IV |y) using the correct key, gets the plaintext x, and checks if x uses the correct padding scheme described above. The padding oracle has been shared with you. (See “Notes on the Padding Oracle” later for more details on how to run the padding oracle.) Suppose we are deciphering some ciphertext (IV |y1| . . . |yN ). There will be three steps. First, we will learn how to find the last byte of xN (“Decrypt byte”). Then, we will find the whole xN (“Decrypt block”). Finally, we will find all of (x1|x2| . . . |xN ) (“Decrypt”). — Decrypt byte — Extract yN from the ciphertext by taking the last 16 bytes, and yN−1 as the last 32 to 16 bytes. Denote the ith byte of yN as yN,i.Here, we want to find xN,16. 1. First, generate a random block r = (r1|r2| . . . |r15|i) with 15 random bytes, followed by a byte i. Initially i = 0. 2. Ask the padding oracle if (r|yN ) is valid. (r|yN ) contains the 16 bytes of r, followed by the 16 bytes of y. 4 CMPT479 A2 3. If the padding oracle returns “no”, increment i by 1, and then ask the padding oracle again. Keep incrementing i until the padding oracle returns “yes”. 4. Replace r1 with any other byte and ask the oracle if the new (r|yN ) has valid padding. If the padding oracle returns “yes”, similarly replace r2. Repeat until either we have finished replacing r15 and the oracle always returned “yes”, or the oracle has returned “no” while we were replacing some rk. 5. If the oracle always returned “yes” in Step 4, set D(yN )16 = i ⊕ 15.6. If the oracle returned “no” when we replaced rk in Step 4, set D(yN )16 = i⊕(k−1). 7. The final byte of xN is xN,16 = D(yN )16 ⊕ yN−1,16. — Decrypt block — After finding xN,16, the attacker can proceed to find all other bytes of xN , starting from the 15th byte xN,15, then xN,14, and proceeding backwards to xN,1. In this process, the attacker will also find D(yN )16, D(yN )15, . . . , D(yN )1 as above. The following describes how the attacker can find xN,k for any k; the attacker has already found D(yN )k+1, D(yN )k+2, . . . , D(yN )16. 1. Set r as (r1|r2| . . . |rk−1|i|D(y)k+1 ⊕(k −1)|D(y)k+2 ⊕(k −1)| . . . |D(y)16 ⊕(k −1)). Initially i = 0. 2. Ask the oracle if r|yN is valid. 3. If the padding oracle returns “no”, increment i and ask the padding oracle again. Keep incrementing i until the padding oracle returns “yes”.4. When the padding oracle returns “yes”, set D(yN )k = i ⊕ (k − 1) 5. The k-th byte of xN is xN,k = D(yN )k ⊕ yN−1,k. — Decrypt — The above shows how the attacker can decrypt the last block yN to obtain XN . To decrypt the k-th block yk, the attacker simply replaces all of the above yN with yk and yN−1 with yk−1. Write a program, decrypt, which finds the plaintext x for any ciphertext y and outputs it to standard output. It is run with: ./decrypt ciphertext ✿✿ OR✿✿✿✿✿✿✿✿✿✿ python3✿✿✿✿✿✿✿✿✿✿✿✿✿✿ decrypt.py✿✿✿✿✿✿✿✿✿✿✿✿✿ ciphertext✿✿✿✿ OR✿✿✿✿✿✿ java✿✿✿✿✿✿✿✿✿✿ decrypt✿✿✿✿✿✿✿✿✿✿✿✿✿✿ ciphertext ciphertext is a file that contains an amount of data that is a multiple of 16 bytes, and at least 32 bytes.It is formatted as IV |y1| . . . |yN , where the IV is the first 16 bytes, y1 are bytes 17 to 32, and so on. The plaintext is in ASCII. After you get the plaintext, output it to standard output. Do not add a newline. You should tackle the assignment step by step: do the “Decrypt byte” step, then the “Decrypt block” step, then the “Decrypt” step. In case you cannot finish the assignment, marks will be given for partially completing each step. 5 CMPT479 A2 Hint: Suppose you are given the ciphertext (IV |y1|y2). Write down the plaintext (x1|x2) using D, IV , y1, and y2. (It is not simply D(y1) and D(y2).)Bonus (6 points) Write a program, encrypt, which takes in some plaintext x and encrypts x using the same encryption algorithm and key that is behind the padding oracle provided. It is run with: ./encrypt plaintext ✿✿ OR✿✿✿✿✿✿✿✿✿✿ python3✿✿✿✿✿✿✿✿✿✿✿✿✿✿ encrypt.py ✿✿✿✿✿✿✿✿✿✿✿✿ plaintext✿✿✿✿ OR ✿✿✿✿✿✿ java✿✿✿✿✿✿✿✿✿✿ encrypt ✿✿✿✿✿✿✿✿✿✿✿✿ plaintext plaintext contains an amount of data that is a multiple of 16 bytes, and at least 16 bytes. It is formatted as x1|x2| . . . |xN . Output the ciphertext and the IV to standard output as IV |y1| . . . |yN . (Hint: encrypt should call decrypt as a subroutine in order to guess the right ciphertext. You only need to call decrypt once for each block. Note that you can choose your own IV.)Notes on the Padding Oracle The padding oracle should be run with: python3 oracle.py ciphertext It will decrypt the ciphertext with the secret AES key, check the padding of the plaintext, and output “1” if the padding is correct and “0” if the padding is incorrect. The padding oracle was written in Python. It is not compiled, and it can be directly run on Unix-like systems such as Ubuntu and macOS. If you want to run it on Windows, you will have to install Python and then type: python3 oracle.py ciphertext You will also have to capture the output and feed it into your own code.The command to do so is system() in C and C++, subprocess.check output() in Python, and Runtime.getRuntime().exec() in Java. You may have to look up documentation for the relevant command. Since the oracle is not compiled, the key is hardcoded into the oracle code. Do not use this key in any way. When we test your code, we will set the oracle with a different key. Your code should work independent of what the actual key is. You are also provided with a ciphertext called ciphertext for reference, with its generator ciphertext gen.py. It was encrypted with the same key as the oracle, and you can see the IV and plaintext used to create it; see if you can decrypt it correctly.Submission instructions All submissions should be done through CourSys. Submit the following files: • a2.pdf, containing all your written answers. Make sure it is not the question file. • ptext0 and ptext1, for part (a) of the programming assignment. • decrypt.{cpp, py, java}, for part (b) of the programming assignment, as well as any other code necessary to run it. This may include a Makefile. Submit your code; do not submit any compiled files. You may also submit encrypt.{cpp, py, java} for the bonus marks. The bonus marks can only be applied to this assignment. To run decrypt, for example, I will do the following: C++: I will compile ./g++ decrypt.cpp -o decrypt and then run ./decrypt ✿✿✿✿✿✿✿✿✿✿✿✿ ciphertext. Python3: I will call python3 decrypt.py ✿✿✿✿✿✿✿✿✿✿✿✿ ciphertext. Java: I will compile javac decrypt.java and then call java decrypt ✿✿✿✿✿✿✿✿✿✿✿✿ ciphertext. If you are using Python, pleaase make sure it is Python3 instead of Python2. If there is a Makefile in your folder, the Makefile will override all of the above. I will call make to compile the code, and then I will call make run. Keep in mind that plagiarism is a serious academic offense; you may discuss the assignment, but write your assignment alone and do not show anyone your answers and code. The submission system will be closed exactly 48 hours after the due date of the assignment. You will receive no marks if there is no submission within 48 hours after the due date.
1. [12 points] Read each of the following news stories about malware: (a) ENISA reports a 30% increase in crypto-jacking incidents year-on-year in 2020, and they have only increased since. Crypto-jacking uses the victim’s computing resources (usually CPU) to mine cryptocurrencies for the attacker.Crypto-jacking can be done by background scripts on a webpage. Webpages that are otherwise useful to visit are particularly powerful attack vectors. The resources stolen is not large enough to be noticeable to a victim.(b) In 2013, the New York Times reported that the Dual EC DRBG random number generator has a potential backdoor. The NSA is the sole editor of this algorithm’s standard. The backdoor allows an attacker to fully compromise cryptography based on this tool. RSA Security started using Dual EC DRBG as its standard RNG for some of its software after accepting $10 million from the NSA.(c) Pegasus is a powerful piece of malware developed by the NSO Group that has frequently been used for surveillance on high-profile targets such as politicians and human-rights activists. Attackers exploited a zero-day vulnerability in the Safari Webkit by sending a file to a victim that appears to be a GIF file, but clicking on it would cause surveillance software to be installed on their iPhone. A 2021 report by Amnesty International shows that it has been used in thousands of attacks over the three preceding years.(d) The Meris botnet broke several records for DDoS volume in 2021. It compromises MikroTik routers with a directory traversal vulnerability that allows remote attackers to steal the admin password of the device to gain full control over it. With 250,000 such routers, Cloudflare estimates that Meris targeted approximately 50 different websites a day, demanding ransoms and DDoSing websites that refused to pay. For each of the above news stories, answer the following questions and explain: i. [4 points] Which of the CIA principles is being violated? ii. [4 points] Classify the malware by method of spread (not payload). iii. [4 points] Suggest a reasonable counter-measure to defeat or prevent the attack.2. [10 points] State whether each of the following statements is true or false. For each, explain why. (a) [2 points] One major reason in why we continue to use C and C++ despite its vulnerabilities is the Saltzer-Schroeder principle of “work factor”. (b) [2 points] Buffer overflow attacks are made more powerful because of poor implementation of the principle of least privilege. (c) [2 points] Stack canaries are an example of the principle of fail-safe defaults. (d) [2 points] XSS attacks usually require the attacker to gain full control over the web server first. (e) [2 points] The vulnerability behind Heartbleed is more serious than what would have been caused by a format string vulnerability.3. [13 points] In 2015, Ion et al. investigated the differences between security practices recommended by experts and non-experts. Experts included hacker conference attendees, professionals and researchers, while non-experts were recruited from MTurk. i. [4 points] The biggest difference in security practices between experts and nonexperts was to “update software”. 35% of experts included this in their top three suggestions while only 2% of non-experts did so. Give two examples of real attacks that could have been prevented if software updates were taken more seriously. ii. [5 points] The top advice from non-experts was to use antivirus software, but experts do not agree. Experts rate the effectiveness of antivirus software much lower than non-experts. Why is that? Explain with reference to current malware capabilities. iii. [4 points] Experts and non-experts viewed password management differently. Generally, experts recommend using a password manager, while non-experts advocated for rotating passwords frequently, choosing strong passwords, and writing down passwords. Many more experts say they don’t remember all their passwords than non-experts (83% vs 48%). Explain the difference in practices with reference to two Saltzer-Schroeder design principles.You have been given login.cpp, a simple program to check if the user’s login matches a stored username and password using three different methods. Compile it and test it with user input. Normally, the program checks a secret password.txt file to match your input with the stored username and password, and grant access if they match. For your convenience, you have been provided with such a password.txt file to test your code, but you should assume the true password.txt file is different from the one you were provided when you write your exploit. There are three ways to log in using login.cpp: 1. ./login -i will check your username and password against the secret password.txt file. It uses a randomized canary to detect buffer overflows, just like stack canaries.2. ./login -j will check your username and password against the secret password.txt file. This time, its hardcoded canary is dynamically computed against your username. Furthermore, the canary is placed in a different location in memory. 3. ./login -k will check your username and password against the secret password.txt file. This time, you cannot expect to overwrite the canary correctly. The login program is simplified: upon a successful login, it shows a congratulatory message and does not do anything else. You are free to imagine that it will then allow you to perform some privileged action, such as allowing access to confidential data or launching a missile. Your username must start with your own @sfu.ca username. For example, if my e-mail is [email protected], I can choose taowang123 as my username for this assignment. This is meant to discourage plagiarism so that each student’s answer will be unique.The assignment will be marked on 20th June. (a) [15 points] Using a buffer overflow exploit, log in to the program using the first method. Submit your username and password in a file called a1a.txt, with exactly two lines, the first line being the username, and the second line being the password. (Do not write anything else in your submitted file.) (b) [15 points] Using a buffer overflow exploit, log in to the program using the second method. Submit your username and password in a file called a1b.txt exactly as in part (a). (Your username can be different from part a, but most start with your @sfu.ca username.)(c) [15 points] Using a buffer overflow exploit, log in to the program using the third method. Submit your username and password in a file called a1c.txt exactly as in part (a). (Your username can be different from part a, but most start with your @sfu.ca username.) For each part, as long as “Login successful!” appears, the attempt is considered successful even if other warning messages appear. You may choose to use escape characters in your submitted answer or not; the marker will consider both cases. All of your exploits should work on your own computer, not a dated architecture.Therefore, overwriting the return address is not part of the assignment. You should not use any information in the password.txt file: it is there only for your convenience. Hints To study the login.cpp code, you can try to modify it, for example, to log the values of the variables at different lines in the code. It may also be a good idea to learn how to use a memory disassembler like gdb to find where the variables are. Just remember to remove your modifications to test your username and password against the original login.cpp file. struct is used in this code to ensure that the variables are always placed in the right order; the compiler would not re-arrange the order of variables.Submission instructions You should submit the following files to Coursys by the deadline: • a1.pdf, with your answers to the written component. • a1a.txt, a1b.txt, a1c.txt, with your answers to the programming component. These must be textfiles, not, for example, Word documents renamed with a .txt extension. Do not zip any files. You can submit these files any number of times and the system will accept the last submission for each file, which overwrites previous submissions.You are encouraged to make submissions as early as possible. It is important to name your files correctly. Otherwise, we may not mark them! Keep in mind that plagiarism is a serious academic offense; you may discuss the assignment, but write your assignment alone and do not show anyone your answers and code. The submission system will be closed exactly 48 hours after the due date of the assignment. The 48 hours act as a no-penalty grace period. Submissions after then will not be accepted unless you have requested an extension before the due date of the assignment. You may receive no marks if there is no submission within 48 hours after the due date.Command Line Arguments C++ (and most other languages) can accept command line arguments, which are additional commands given while running the code. Suppose we compiled mycode from mycode.cpp. If we run the binary code file mycode as such: ./mycode abc 3 1 We say that mycode is run with 3 command line arguments; the first one is abc, the second one is 3, and the third one is 1. In mycode.cpp, the main function header will be written as follows: int main(int argc, char ** argv) { … } In this code, argc is an integer that counts the number of arguments (plus one, because mycode also counts), and argv is a list of character arrays that contains the arguments. For example: int main(int argc, char ** argv) { printf(“Number of arguments is: %d, first argument is %s ”, argc, argv[1]); return 0; } The output will be: Number of arguments is 4, first argument is abc 6 CMPT479 A1
