CSCI 570 Homework 5 1. In the network below (See Fig. 1), the demand values are shown on vertices (supply values are negative). Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Determine if there is a feasible circulation in this graph. Please complete the following steps. Figure 1 (a) Remove the lower bounds on each edge. Write down the new demands on each vertex A, B, C, D, E, in this order. (b) Solve the circulation problem without lower bounds. Write down the max-flow value. (c) Is there is a feasible circulation in the original graph? Explain your answer. 2. The organizers of the 2022 US Open Tennis Championships are working on making the draws for the first round and scheduling the matches. They are faced with several constraints in doing so. There are 2N players, seeded (ranked) from 1 to 2N. The players are divided into two halves – the top half containing players seeded 1 to N, and the bottom half containing seeds N + 1 to 2N. The first round consists of N matches among the 2N players, each being one where a top-half player plays a bottom-half player. Additionally, to keep them a bit more competitive, each match must be between players whose seeds differ by at most N0 (a given constant > N). The sports facility has courts C1, …, Cm. The matches will be scheduled in timeslots T1, …, Tk. Matches can run in parallel on different courts in a given timeslot. Assume all courts are available in all timeslots, however a single court can have at most p matches to preserve surface quality. For broadcasting reasons, in any given timeslot, there should be at least one match being played and at most r of them. The bottom-half players were given the option to make requests if they preferred to play in certain timeslots, and each of them has specified k 0 of the k timeslots that they are okay to play in. Seeded players on the other hand were given the option to make requests to avoid playing on certain courts, and each of them has specified m0 of the m courts that they do not want to play on. Describe a Network Flow/Circulation based algorithm to determine if it is possible to come up with a feasible schedule of matches based on the above constraints. 3. A company is currently trying to fill a large order of steel, brass, and pewter, measured in tons. Manufacturing each ton of material requires a certain amount of time, and a certain amount of special substance (SS), both of which are limited and are given in below table. Note that it is acceptable to manufacture a fraction of a ton (e.g. 0.5t) of material. Specifically, the company currently has 8 hours of time, and 20 units of special substance (SS). Manufacturing each ton of the three products requires: Figure 2: Table describing the amount of time taken and special substance (SS) required for each product. (a) Write down a linear program that determines the maximum amount of products (in tons) that the company can make. (b) Due to the potential danger posed by the special substance (SS), the company would like to use up as much of its supply of special substance (SS) as possible, while: i. spending at most 8 hours ii. manufacturing a total of at least 2 tons of steel plus pewter. 4. Suppose that a cement supplier has two warehouses, one located in city A and another in city B. The supplier receives orders from two customers, one in city C and another in city D. The customer in city C needs at least 50 tons of cement, and the customer in city D needs at least 60 tons of cement. The amount of cement at the warehouse in city A is 70 tons, and the number of units at the warehouse in city B is 80 tons. The cost of shipping each ton of cement from A to C is 1, from A to D is 2, from B to C is 3, and from B to D is 4. Formulate the problem of deciding how many tons of cement from each warehouse should be shipped to each customer to minimize the total shipping cost as a linear programming. You can assume that the values of units to be shipped are real numbers. 5. Write down the dual program of the following linear program. There is no need to provide intermediate steps. max(x1 − 3×2 + 4×3 − x4) subject to x1 − x2 − 3×3 ≤ −1 x2 + 3×3 ≤ 5 x3 ≤ 1 x1, x2, x3, x4 ≥ 0 6. Given an undirected graph G = (V, E), a vertex cover is a subset of V so that every edge in E has at least one endpoint in the vertex cover. The problem of finding a minimum vertex cover is to find a vertex cover of the smallest possible size. Formulate this problem as an integer linear programming problem. 7. Assume that you are given a polynomial time algorithm that given a 3- SAT instance decides in polynomial time if it has a satisfying assignment. Describe a polynomial time algorithm that finds a satisfying assignment (if it exists) to a given 3-SAT instance. 8. The graph five-coloring problem is stated as follows: Determine if the vertices of G can be colored using 5 colors such that no two adjacent vertices share the same color. Prove that the five-coloring problem is NP-complete. Hint: You can assume that graph 3-coloring is NP-complete 9. Longest Path is the problem of deciding whether a graph G = (V, E) has a simple path of length greater or equal to a given number k. Prove that the Longest path Problem is NP-complete by reduction from the Hamiltonian Path problem. 10. There are a set of courses in USC, each of them requiring a set of disjoint time intervals. For example, a course could require the time from 9am to 11am and 2pm to 3pm and 4pm to 5pm. You want to know, given a number K, if it’s possible to take at least K courses. Since you want to study hard and take courses carefully, you can only take one course at any single point in time (i.e. any two courses you choose can’t overlap). Show that the problem is NP-complete, which means that choosing courses is indeed a difficult thing in our life. Use a reduction from the Independent set problem.
CSCI 570 Homework 3 1. (Greedy) Given n rods of lengths L1, L2, . . . , Ln, respectively, the goal is to connect all the rods to form a single rod. The length and the cost of connecting two rods are equal to the sum of their lengths. Devise a greedy algorithm to minimize the cost of forming a single rod. 2. (Greedy) During a summer music festival that spans m days, a music organizer wants to allocate time slots in a concert venue to various artists. However, each time slot can accommodate only one performance, and each performance lasts for one day. There are N artists interested in performing at the festival. Each artist has a specific deadline, Di , indicating the last day on which they can perform, and an expected audience turnout, Ai , denoting the number of attendees they expect to draw if they perform on or before their deadline. It is not possible to schedule an artist’s performance after their deadline, meaning an artist can only be scheduled on days 1 through Di . The goal is to create a performance schedule that maximizes the overall audience turnout. The schedule can assign performances for n artists over the course of m days. Note: The number of performances (n) is not greater than the total number of artists (N) and the available days (m), i.e., n ≤ N and n ≤ m. It may not be feasible to schedule all artists before their deadlines, so some performances may need to be skipped. (a) Let’s explore a situation where a greedy algorithm is used to allocate n performance to m days consecutively, based on their increasing deadlines Di . If, due to this approach, a task ends up being scheduled after its specified deadline Di , it is excluded (not scheduled). Provide an counterexample to demonstrate that this algorithm does not consistently result in the best possible solution. (b) Let’s examine a situation where a greedy algorithm is employed to distribute n performance across m days without any gaps, prioritizing performances based on their expected turnouts Ai in decreasing order. If, as a result of this approach, a performance ends up being scheduled after its specified deadline Di , it is omitted from the schedule (not scheduled). Provide a counterexample to illustrate that this algorithm does not consistently produce the most advantageous solution. (c) Provide an efficient greedy algorithm that guarantees an optimal solution to this problem without requiring formal proof of its correctness. 3. (Master Theorem) The recurrence T(n) = 7T(n/2) + n 2 describes the running time of an algorithm ALG. A competing algorithm ALG′ has a running time of T ′ (n) = aT′ (n/4) + n 2 log n What is the largest value of a such that ALG′ is asymptotically faster than ALG? 4. (Master Theorem) Consider the following algorithm StrangeSort which sorts n distinct items in a list A. (a) If n ≤ 1, return A unchanged. (b) For each item x ∈ A, scan A and count how many other items in A are less than x. (c) Put the items with count less than n/2 in a list B. (d) Put the other items in a list C. (e) Recursively sort lists B and C using StrangeSort. (f) Append the sorted list C to the sorted list B and return the result. Formulate a recurrence relation for the running time T(n) of StrangeSort on an input list of size n. Solve this recurrence to get the best possible O(·) bound on T(n). 5. (Master Theorem) For the given recurrence equations, solve for T(n) if it can be found using the Master Method. Else, indicate that the Master Method does not apply. (a) T(n) = T(n/2) + 2n (b) T(n) = 5T(n/5) + n log n–1000n (c) T(n) = 2T(n/2) + log2 n (d) T(n) = 49T(n/7) − n 2 log n 2 (e) T(n) = 3Tn 4 + n log n 6. (Divide-and-Conquer) We know that binary search on a sorted array of size n takes Θ(log n) time. Design a similar divide-and-conquer algorithm for searching in a sorted singly linked list of size n. Discuss its worst-case runtime complexity. 7. (Divide-and-Conquer) We know that mergesort takes Θ(n log n) time to sort an array of size n. Design a divide-and-conquer mergesort algorithm for sorting a singly linked list. Discuss its worst-case runtime complexity. 8. (Divide-and-Conquer) Imagine you are responsible for organizing a music festival in a large field, and you need to create a visual representation of the stage setup, accounting for the various stage structures. These stages come in different shapes and sizes, and they are positioned on a flat surface. Each stage is represented as a tuple (L, H, R), where L and R are the left and right boundaries of the stage, and H is the height of the stage. Your task is to create a skyline of these stages, which represents the outline of all the stages as seen from a distance. The skyline is essentially a list of positions (x-coordinates) and heights, ordered from left to right, showing the varying heights of the stages. Take Fig. 1 as an example: Consider the festival setup with the following stages: (2, 5, 10), (8, 3, 16), (5, 9, 12), (14, 7, 19). The skyline for this festival setup would be represented as: (2, 5, 5, 9, 12, 3, 14, 7, 19), with the x-coordinates sorted in ascending order. (a) Given the skyline information of n stages for one part of the festival and the skyline information of m stages for another part of the festival, demonstrate how to compute the combined skyline for all m+n stages efficiently, in O(m + n) steps. (b) Assuming you’ve successfully solved part (a), propose a Divide-andConquer algorithm for computing the skyline of a given set of n stages in the festival. Your algorithm should run in O(n log n) steps. 9. (Dynamic Programming) Imagine you are organizing a charity event 2 8 10 12 14 16 19 3 5 7 9 5 Figure 1: Example of festival stage setup. to raise funds for a cause you care deeply about. To reach your fundraising goal, you plan to sell two types of tickets. You have a total fundraising target of n dollars. Each time someone contributes, they can choose to buy either a 1-dollar ticket or a 2-dollar ticket. Use Dynamic Programming to find the number of distinct combinations of ticket sales you can use to reach your fundraising goal of n dollars? For example, if your fundraising target is 2 dollars, there are two ways to reach it: 1) sell two 1-dollar tickets; 2) sell one 2-dollar ticket. (a) Define (in plain English) subproblems to be solved. (b) Write a recurrence relation for the subproblems (c) Using the recurrence formula in part b, write pseudocode using iteration to compute the number of distinct combinations of ticket sales to reach fundraising goal of n dollars. (d) Make sure you specify base cases and their values; where the final answer can be found. (e) What is the runtime complexity of your solution? Explain your answer. 10. (Dynamic Programming) Assume a truck with capacity W is loading. There are n packages with different weights, i.e. (w1, w2, . . . wn), and all the weights are integers. The company’s rule requires that the truck needs to take packages with exactly weight W to maximize profit, but the workers like to save their energies for after work activities and want to load as few packages as possible. Assuming that there are combinations of packages that add up to weight W, design an algorithm to find out the minimum number of packages the workers need to load. (a) Define (in plain English) subproblems to be solved. (b) Write a recurrence relation for the subproblems (c) Using the recurrence formula in part b, write pseudocode using iteration to compute the minimum number of packages to meet the objective. (d) Make sure you specify base cases and their values; where the final answer can be found. (e) What is the worst case runtime complexity? Explain your answer.
CSCI 570 Homework 4 1. (Dynamic Programming) Given n balloons, indexed from 0 to n−1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If you burst the balloon i you will get nums[lef t] · nums[i] · nums[right] coins, where left and right are adjacent indices of i. After the bursting the balloon, the left and right then becomes adjacent. Assume, nums[−1] = nums[n] = 1 and they are not real therefore you can not burst them. Design a dynamic programming algorithm to find the maximum coins you can collect by bursting the balloons wisely. Analyze the running time of your algorithm. 2. (Dynamic Programming) Suppose you are in Casino with your friend, and you are interested in playing a game against your friend by alternating turns. The game contains a row of n coins of values vi , where n is even. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money you can definitely win if you move first. Analyze the running time of your algorithm. 3. (Dynamic Programming) Jack has gotten himself involved in a very dangerous game called the octopus game where he needs to pass a bridge which has some unreliable sections. The bridge consists of 3n tiles as shown below. Some tiles are strong and can withstand Jack’s weight, but some tiles are weak and will break if Jack lands on them. Jack has no clue which tiles are strong or weak but we have been given that information in an array called BadTile(3,n) where BadTile(j, i) = 1 if the tile is weak and 0 if the tile is strong. At any step Jack can move either to the tile right in front of him (i.e. from tile (j, i) to (j, i+1)), or diagonally to the left or right (if they exist). (No sideways or backward moves are allowed and one cannot go from tile (1, i) to (3, i+1) or from (3, i) to (1, i + 1)). Using dynamic programming find out how many ways (if any) there are for Jack to pass this deadly bridge. Analyze the running time of your algorithm. Figure below shows bad tiles in gray and one of the possible ways for Jack to safely cross the bridge alive (See Fig. 1). Figure 1 4. Given a flow network with the source s and the sink t, and positive integer edge capacities c. Prove or disprove the following statement: if deleting edge e reduces the original maximum flow more than deleting any other edge does, then edge e must be part of a minimum s−t cut in the original graph. 5. Given a flow network with the source s and the sink t, and positive integer edge capacities c. Let s − t be a minimum cut. Prove or disprove the following statement: If we increase the capacity of every edge by 1, then s − t still be a minimum cut. 6. (Network Flow) (a) For the given graph G1 (see Fig. 2), find the value of the max flow. Edge capacities are mentioned on the edges. (You don’t have to show each and every step of your algorithm). Figure 2: G1 (b) For the given graph, find the value of the min-cut. (You don’t have to show each and every step of your algorithm). Figure 3 7. (Network Flow) Consider a set of mobile computing clients in a certain town who each need to be connected to one of several possible base stations. We’ll suppose there are n clients, c1, c2, . . . , cn , with the position of each client specified by its (x, y) coordinates in the plane. There are also k base stations, b1, b2, . . . , bk; the position of each of these is specified by (x, y) coordinates as well. For each client, we wish to connect it to exactly one of the base stations. Our choice of connections is constrained in the following ways. There is a range parameter R which means that a client can only be connected to a base station that is within distance R. There is also a load parameterL which means that no more thanL clients can be connected to any single base station. Given the positions of a set of clients and a set of base stations, as well as the range and load parameters, decide whether every client can be connected simultaneously to a base station. Prove the correctness of the algorithm. 8. (Network Flow) You are given a flow network with unit-capacity edges: it consists of a directed graph G = (V, E) with source s and sink t, and ue = 1 for every edge e. You are also given a positive integer parameter k. The goal is delete k edges so as to reduce the maximum s − t flow in G by as much as possible. Give a polynomial-time algorithm to solve this problem. In other words, you should find a set of edges F ⊆ E so that |F| = k and the maximum s − t flow in the graph G′ = (V, E − F) is as small as possible. Give a polynomial-time algorithm to solve this problem. 9. (Network Flow) Counter Espionage Academy instructors have designed the following problem to see how well trainees can detect SP Y ’s in an n × n grid of letters S, P, and Y . Trainees are instructed to detect as many disjoint copies of the word SP Y as possible in the given grid. To form the word SP Y in the grid they can start at any S, move to a neighboring P, then move to a neighboring Y . (They can move north, east, south or west to get to a neighbor.) The following figure shows one such problem on the left, along with two possible optimal solutions with three SP Y ’s each on the right (See Fig. 4). Give an efficient network flow-based algorithm to find the largest number of SP Y ’s. Note: We are only looking for the largest number of SP Y ’s, not the actual location of the words. No proof is necessary. Figure 4 10. (Network Flow) USC students return to in person classes after a year long interval. There are k in-person classes happening this semester, c1, c2, …, ck. Also there are n students, s1, s2, …, sn attending these k classes. A student can be enrolled in more than one in-person class and each in-person class consists of several students. (a) Each student sj wants to sign up for a subset pj of the k classes. Also, a student needs to sign up for at least m classes to be considered as a full time student. (Given: pj ≥ m) Each class ci has capacity for at most qi students. We as school administration want to find out if this is possible. Design an algorithm to determine whether or not all students can be enrolled as full time students. Prove the correctness of the algorithm. (b) If there exists a feasible solution to part (a) and all students register in exactly m classes, the student body needs a student representative from each class. But a given student cannot be a class representative for more than r (where r < m) classes which s/he is enrolled in. Design an algorithm to determine whether or not such a selection exists. Prove the correctness of the algorithm. (Hint: Use part (a) solution as starting point).
CSCI 570 Homework 2 1. In the SGM building at USC Viterbi, there is a need to schedule a series of n classes on a day with varying start and end times. Each class is represented by an interval [start time, end time], where start time is the time when the class begins and end time is when it concludes. Each class requires the exclusive use of a lecture hall. (a) To optimize resource allocation, devise an algorithm using binary heap(s) to determine the minimum number of lecture halls needed to accommodate all the classes without any class overlapping in scheduling. (7 points) (b) Analyze and state its worst-case time complexity in terms of n. (3 points) 2. The Thomas Lord Department of Computer Science at USC Viterbi is working on a project to compile research papers from various departments and institutes across USC. Each department maintains a sorted list of its own research papers by publication date, and the USC researchers need to combine all these lists to create a comprehensive catalog sorted by publication date. With limited computing resources on hand, they are facing a tight deadline. To address this challenge, they are seeking the fastest algorithm to merge these sorted lists efficiently, taking into account the total number of research papers (m) and the number of departments (n). (a) Devise an algorithm using concepts of binary heap(s). (7 points) (b) Analyze and state its worst-case time complexity in terms of m and n. (3 points) 3. In an interstellar odyssey, a spaceship embarks on a journey from a celestial origin to a distant target star, equipped with an initial fuel capacity of ’currentFuel’ units. Along the cosmic highway, there are space refueling stations represented as an array of ’spaceStations’, each defined as [distanceToStationFromOrigin, fuelCapacity]. There are ’n’ space stations between the celestial origin and the target star. The objective is to determine the minimum number of refueling stops required for the spaceship to reach the target star, which is located ’targetDistance’ light-years away. The spaceship consumes one unit of fuel per light-year traveled. Upon encountering a space station, it can refuel completely by transferring all available ’fuelCapacity’ units from the station. The challenge is to calculate the ’refuelStops’ needed for a successful voyage to the target star or return -1 if reaching the destination remains unattainable with the available fuel resources. (a) Devise an algorithm using concepts of binary heap(s). (7 points) (b) Analyze and state its worst-case time complexity in terms of n. (3 points) 4. You are tasked with performing operations on binomial min-heaps using a sequence of numbers. Follow the steps below: (a) Create a binomial min-heap H1 by inserting the following numbers from left to right: 3, 1, 13, 9, 11, 5, 7, 15. (2 points) (b) Perform one deleteMin() operation on H1 to obtain H2. (2 points) (c) Create another binomial min-heap H3 by inserting the following numbers from left to right: 8, 12, 4, 2. (2 points) (d) Merge H2 and H3 to form a new binomial heap, H4. (2 points) (e) Perform two deleteMin() operations on H4 to obtain H5. (2 points) Note: It is optional to show the intermediate steps in your submission. Only the five final binomial heaps (H1, H2, H3, H4, and H5) will be considered for grading. So, please ensure that you clearly illustrate your final binomial heaps (H1, H2, H3, H4, and H5). You can use online tools like draw.io for drawing these heaps. 5. If we have a k-th order binomial tree (Bk), which is formed by joining two Bk−1 trees, then when we remove the root of this k-th order binomial tree, it results in k binomial trees of smaller orders. Prove by mathematical induction. (10 points) 6. Given a weighted undirected graph with all distinct edge costs. Design an algorithm that runs in O(V + E) to determine if a particular edge e is contained in the minimum spanning tree of the graph. Pseudocode is not required, and you can use common graph algorithms such as DFS, BFS, and Minimum Spanning Tree Algorithms as subroutines without further explanation. You are not required to prove the correctness of your algorithm. (10 points) 7. Given a weighted undirected graph with all distinct edge costs and E = V + 10. Design an algorithm that outputs the minimum spanning tree of the graph and runs in O(V ). Pseudocode is not required, and you can use common graph algorithms such as DFS, BFS, and Minimum Spanning Tree Algorithms as subroutines without further explanation. You are not required to prove the correctness of your algorithm. (10 points) 8. There are N people with the i-th person’s weight being wi . A boat can carry at most two people under the max weight limit of M ≥ maxi wi . Design a greedy algorithm that finds the minimum number of boats that can carry all N people. Pseudocode is not required, and you can assume the weights are sorted. Use mathematical induction to prove that your algorithm is correct. (10 points) 9. Given N > 1 integer arrays with each array having at most M numbers, you are asked to select two numbers from two distinct arrays. Your goal is to find the maximum difference between the two selected numbers among all possible choices. Provide an algorithm that finds it in O(NM) time. Pseudocode is not required, and you can use common operations for arrays, such as min and max, without further explanation. Prove that your algorithm is correct. You may find proof by contradiction helpful when proving the correctness. (10 points) 10. There are N cities (city 1, to city N) and some flights between these cities. Specifically, there is a direct flight from every city i to city 2i (no direct flight from city 2i to city i) and another direct flight from every city i to city i−1 (no direct flight from city i−1 to city i). Given integers a and b, determine if there exists a sequence of flights starting from city a to city b. If so, find the minimum number of flights required to fly from city a to city b. For example, when N = 10, a = 3, and b = 9, the answer is 4 and the corresponding flights are 3 → 6 → 5 → 10 → 9. You are not required to prove the correctness of your algorithm. (10 points)
CSCI 570 Homework 1 1. Arrange these functions under the Big-O notation in increasing order of growth rate with g(n) following f(n) in your list if and only if f(n) = O(g(n)) (here, log(x) is the natural logarithm1 of x, with the base being the Euler’s number e) : 2 log(n) , 2 3n , 3 2n , nn log(n) , log(n), n log(n 2 ), nn 2 , log(n!), log(log(n n )). 2. Show by induction that for any positive integer k, (k 3 + 5k) is divisible by 6. 3. Show that 13 + 23 + · · · + n 3 = n 2 (n+1)2 4 for every positive integer n using induction. 4. Consider the following prime filtering algorithm that outputs all the prime numbers in 2, . . . , n (the pseudo code is presented in Algorithm 1). • Please prove this algorithm is correct (that is, a positive integer k that 2 ≤ k ≤ n is a prime if and only if isP rime(k) = True). • Please calculate the time complexity under the Big-O notation. Algorithm 1 Prime Filtering 1: Input: a positive integer n ≥ 2 2: initialize the Boolean array isP rime such that isP rime(i) = True for i = 2, . . . , n 3: for i = 2 . . . n do 4: for j = 2 . . . n i do 5: if i × j ≤ n then 6: isP rime(i × j) ← False 7: end if 8: end for 9: end for 5. Amy usually walks from Amy’s house (“H”) to SGM (“S”) for CSCI 570. On her way, there are six crossings named from A to F. After taking the first course, Amy denotes the six crossings, the house, and SGM as 8 nodes, and write down the roads together with their time costs (in minutes) in Figure 1. Could you find the shortest path from Amy’s house to SGM? You need to calculate the shortest length, and write down all the valid paths. 1https://en.wikipedia.org/wiki/Natural_logarithm A D B E C F 5 6 7 6 4 8 6 5 4 3 Figure 1: Problem 4’s Graph 6. According to the Topological Sort for DAG described in Lecture 1, please find one possible topological order of the graph in Figrue 2. In addition, could you find all the possible topological orders? A D B E C F G Figure 2: Problem 5’s Graph 7. A binary tree2 is a rooted tree in which each node has two children at most. A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible. For a complete binary tree T with k nodes, suppose we number the node from top to down, from left to right with 0, 1, 2, …, (k −1). Please solve the following two questions: • For any of the left most node of a layer with label t, suppose it has 2https://en.wikipedia.org/wiki/Binary_tree at least one child, prove that its left child is 2t + 1. • For a node with label t and suppose it has at least one child, prove that its left child is 2t + 1. 8. Consider a full binary tree (all nodes have zero or two children) with k nodes. Two operations are defined: 1) removeLastNodes(): removes nodes whose distance equals the largest distance among all nodes to the root node; 2) addTwoNodes(): adds two children to all leaf nodes. The cost of either adding or removing one node is 1. What is the time complexity of these two operations, respectively? Suppose the time complexity to obtain the list of nodes with the largest distance to the root and the list of leaf nodes is both O(1). 9. Given a sequence of n operations, suppose the i-th operation cost 2j−1 if i = 2j for some integer j; otherwise, the cost is 1. Prove that the amortized cost per operation is O(1). 10. Consider a singly linked list as a dictionary that we always insert at the beginning of the list. Now assume that you may perform n insert operations but will only perform one last lookup operation (of a random item in the list after n insert operations). What is the amortized cost per operation?
In this app, you will modify the payroll system code provided to you with this assignment on Blackboard in the zipped file named Starter Code. Using code examples in 10. Object-Oriented Programming – Polymorphism and Interfaces slides, this should not be too complicated. • Add a private instance variable birthDate to the Employee class. • Use class Date – also provided to you with this assignment on Blackboard – to represent an employee’s birthday. • Add get methods to class Date. • Assume that payroll is processed once per month. • Create an array of Employee variables to store references to the various employee objects. • In a loop, calculate the payroll for each Employee (polymorphically), and add a $100.00 bonus to the person’s payroll amount if the current month is the one in which the Employee’s birthday occurs. • Use the sample output provided to test your app. Submit your .java files on Blackboard as before. DO NOT INCLUDE THE OUTPUT, .java~ or .class files!
In this assignment, you will develop a Java console app to calculate tips. We will break the code for this assignment into two separate classes.This class encapsulates the tip calculation logic. It may be reused with a different user interface in a future assignment. Data Members The class should have the following private data members: • Bill amount (a double with the default value 0) • Tip percentage (an integer with the default value 20) • Party size (an integer with the default value 1) Methods The class should have the following methods: • A default constructor (optional) • Public getters and setters for the three data members. • getTotalBill() – computes and returns the total bill (bill amount plus tip). • getIndividualShare() – computes and returns the value of an equal share of the total bill (i.e., the total bill divided by the party size). Class TipApp This class encapsulates the user interface of the app. Data Members • A TipCalculator object. (This could be a local variable in the calculateTips() method if you prefer.) Methods • main() – creates an instance of TipApp (an object of itself!) and uses it to call calculateTips(). • calculateTips() – This method will contain the logic for interacting with the user at the keyboard and displaying the output of the app. Feel free to extract parts of this logic into other methods that are called by calculateTips(). 1. Create a Scanner object to read input from the keyboard. CSCI 470/502 Assignment 3: Tip Calculator Console App Page 2 of 3 2. Prompt for and read the bill amount. If an invalid numeric value is entered by the user, print an error message and repeat the process until a valid value is entered. When a valid value is entered, use it to set the bill amount data member for the TipCalculator object. 3. Prompt for and read the tip percentage. If an invalid numeric value is entered by the user, print an error message and repeat the process until a valid value is entered. When a valid value is entered, use it to set the tip percentage data member for the TipCalculator object. 4. Prompt for and read the party size. If an invalid numeric value is entered by the user, print an error message and repeat the process until a valid value is entered. When a valid value is entered, use it to set the party size data member for the TipCalculator object. 5. Call the various TipCalculator methods to produce the output. 6. Ask the user whether they want to continue (enter another bill amount, tip percentage and party size) and read their response. If the response is y or Y, go back to Step 2 and repeat. Notes • To make grading by the TA easier, remove all package statements in the .java files that you submit. • Invalid input should include values that are not numeric (which will result in a NumberFormatException when Java attempts to convert them to a number) as well as numeric values that should not be possible. For example, it would be impossible to have a negative bill amount or a party size of 0. However, a tip percentage of 0 should certainly be possible. • Both upper- and lower-case letters should be allowed in the user’s response to the “Another bill? (y/n): ” prompt. Submit your two .java files on Blackboard. Do NOT zip your files for submission yet. Sample Output A sample run of the app might look something like this: *** Tip Calculator *** Enter the bill amount: 105.37 Enter your desired tip percentage (20 equals 20%): 2a Please enter a valid tip percentage. Enter your desired tip percentage (20 equals 20%): 20 Enter the size of your party: -3 Please enter a valid party size. Enter the size of your party: 3 Sample output continues on the next page! CSCI 470/502 Assignment 3: Tip Calculator Console App Page 3 of 3 *** Your Bill *** Bill Amount: $105.37 Tip Percentage: 20% Party Size: 3 Total Bill (with Tip): $126.44 Share for Each Individual: $42.15 Another bill? (y/n): y Enter the bill amount: 78.27 Enter your desired tip percentage (20 equals 20%): 23 Enter the size of your party: 2 *** Your Bill *** Bill Amount: $78.27 Tip Percentage: 23% Party Size: 2 Total Bill (with Tip): $96.27 Share for Each Individual: $48.14 Another bill? (y/n): N Goodbye!
Objective This assignment’s objective is to write a console-based Java application with which a travel agent could present options for travel destinations to a client who wants to redeem his or her accumulated frequent flyer miles. For the sake of simplicity, we will assume all trips depart from O’Hare International Airport and that the miles represented are required for a roundtrip ticket. Depending on the distance, each destination requires a different number of frequent flyer miles to obtain a roundtrip ticket. Note that, if the client travels during the “off season”, he or she may be able to take advantage of the “off season”, or “super-saver”, mileage of a destination that requires fewer miles to obtain a roundtrip ticket to that particular destination. Input File A list of destination cities and related ticket redemption information will be read from a file (one named destinations.txt is provided for you but you may create your own). The file is formatted with one city, or destination, per line, with the first five items, or fields, separated by a semicolon ( ; ) and the last two separated by a hyphen ( – ) as shown in the example below. The six items regarding a single destination represent: The destination city name; the normal mileage needed for an economy class ticket; the “super-saver” mileage needed for an economy class ticket; the additional mileage needed for upgrading from economy to first class; the beginning month of departure during which “super-saver” mileage can be used instead of the normal mileage – the ending month of departure during which “super-saver”, mileage can be used instead of the normal mileage. Actual Input File: Berlin;17250;12750;5250;3-5 Hong Kong;30000;20250;17500;2-4 Hyderabad;30000;20000;15000;2-4 New York;10000;5000;8000;10-11 Paris;20000;15000;10000;2-4 Sidney;50000;30000;20000;5-6 Tokyo;29000;16500;5350;2-5 Vienna;17500;12500;5000;2-4 Washington, D.C.;9000;7500;2000;10-12 The above are the contents of file destinations.txt as attached to the Assignment on Blackboard. Mile Redemption Algorithm Your algorithm should 1) try to get tickets that travel the farthest, 2) use “super-saver” mileage whenever possible, 3) try to display as many different tickets as possible given the information, and, only after you have determined the destinations to which the customer can fly, 4) determine if you can use the remaining mileage for upgrade for any of the destinations to which the customer is eligible to fly (try to upgrade the longest trip first, then the next-to-longest – if there is one, etc.). CSCI 470/502 Assignment 4: Mile Redeemer Console App Page 2 of 6 The Classes Destination Write a class that encapsulates information such as the name of the destination city; normal miles required for a ticket; “super-saver” miles required to for a ticket during the “off season” months; additional miles for upgrading from economy to first class; start month of the “off season” and end month of the “off season”. Private instance variables and public accessor methods should be written for this information. MileRedeemer Write a class to encapsulate the logic for redeeming mileage. This class should have private instance variables for an array of Destination objects, and an integer to represent the remaining miles after the user’s Frequent Flyer Miles have been redeemed. Define the following methods in the MileRedeemer class: • public void readDestinations(Scanner fileScanner) For this method, we use a Scanner object as the input parameter for flexibility and reusability. For example, we could reuse the method to read files from different sources. This method should use the Scanner object to read and parse the destination data into an array of Destination objects. Before ending, the method should sort the array of Destination objects in descending order by normal mileage (see more information about sorting below). • public String[] getCityNames() This method should loop through the array of Destination objects and create an array of String objects from the city names. This array can be sorted in ascending order and returned (to be printed out by the main app) just for the display of all possible destinations. • public String[] redeemMiles(int miles, int month) For this method, miles is the total available miles, and month is the desired month of departure. To avoid writing one huge method, you can (and probably should) have the redeemMiles() method call some other methods to accomplish subtasks as part of the larger overall algorithm. This method should return an array of String objects containing descriptions of redeemed tickets to be printed out by the main app. It should also save the miles remaining after the tickets have been redeemed. • public int getRemainingMiles( ) This method should return the saved remaining miles. MileRedeemerApp This is the main app class that will have the main( ) method and will drive the entire process. First declare a Scanner object for the keyboard and prompt the travel agent for the name of the .txt file of destinations. Next, it should declare another Scanner object to read the destination records from the CSCI 470/502 Assignment 4: Mile Redeemer Console App Page 3 of 6 file. This Scanner will be the Scanner parameter passed to the readDestinations() method of the MileRedeemer class where the array of destinations will be created. Once back from readDestinations(), use getCityNames() to get and print the list of all possible destinations. Prompt the travel agent for the client’s Frequent Flyer Miles balance and for the client’s month of departure. Using these two integers, call redeemMiles() to determine the destinations available to which the client can fly and present them to the travel agent. Note that, if redeemMiles() returns an empty array, print an appropriate message such as: *** Your client has not accumulated enough Frequent Flyer Miles *** Either way, then use getRemainingMiles() to present the Frequent Flyer Miles remaining after determining the destinations to which the client can fly. After presenting the possible destinations and remaining miles, prompt the travel agent asking if he or she would like to start over. Do not ask for a new file name, do not print the header statement and do not print the list of all possible destinations again. Let the travel agent answer with ‘y’ or ‘Y’ or ‘yes’ or ‘Yes’ and, if he or she answers in the affirmative, the next thing he or she should see is a prompt to enter the client’s Frequent Flyer Miles and departure month and the process of determining a new list of possible destinations. MileageComparator Because the cities in the input text file are almost always out of order based on normal miles, the readDestinations() method will need to sort them in descending normal miles order before any redemptions can be done. The class java.util.Arrays has a static sort() method that takes an array and an implementation of Comparator. The latter is an object of a class that defines the ordering: import java.util.Comparator; public class MileageComparator implements Comparator { @Override public int compare(Destination d1, Destination d2) { return (d2.getNormalMiles() – d1.getNormalMiles()); } } Note that this class is optional as you may be able to find a different way to implement the Java interface Comparator. For example, create an inner class. Note: The array of city name strings created and returned by getCityNames() can also be sorted using a version of Arrays.sort(). There’s no need to write a Comparator in this case, though, as the “natural ordering” of the strings will be sufficient. (continued) CSCI 470/502 Assignment 4: Mile Redeemer Console App Page 4 of 6 Programming Notes Exception Handling and Input Validation For simplicity’s sake, please do not add try catch blocks for exception handling and do not do any sort of input validation. File I/O and String Parsing The Scanner class can be used to read the lines from the file. Before reading the lines, a java.util.ArrayList should be created: ArrayList destinationList = new ArrayList(); As lines are read from the input file, the lines need to be parsed, or broken into fields, using “;” as the delimiter. Instances of Destination are created and added to the array list. There are a variety of different ways to parse a String into fields. One easy way is to use the split() method of the String class. Note that the last two fields, i.e., begin month and end month for the “Frequent Flyer” months, are separated by a hyphen. To change a String to an integer to assign to the three miles instance variables and the beginning and ending month instance variables, use wrapper class Integer’s method parseInt(). After the whole file is read, the ArrayList can be converted to a normal, fixed-length array of objects: Destination[] destinationArray = (Destination[]) destinationList.toArray(new Destination[destinationList.size()]); By doing this, we can take advantage of Java’s built-in methods for sorting an array. Reading the File So that you will not have to do any exception handling, add the following at the end of the method declaration that reads the input file (no semicolon at the end of it): throws IOException IMPORTANT Please read the Java Coding and Documentation Guidelines document in Course Documents on Blackboard before submitting your final app for grading. Submitting the Assignment The assignment will be submitted on Blackboard. Please submit the three (or four) .java files on Blackboard. DO NOT ZIP THEM AND DO NOT SUBMIT THE INPUT FILE! (Exact output follows) CSCI 470/502 Assignment 4: Mile Redeemer Console App Page 5 of 6 Exact App Output Using the File destinations.txt Provided Please enter the name of the file: destinations.txt —————————————————————- WELCOME TO THE JAVA AIRLINES MILES REDEEMER APP —————————————————————- List of destination cities your client can travel to: Berlin Hong Kong Hyderabad New York Paris Sidney Tokyo Vienna Washington, D.C. —————————————————————- Please enter your client’s accumulated Frequent Flyer Miles: 49600 Please enter your client’s month of departure (1-12): 4 Your client’s Frequent Flyer Miles can be used to redeem the following tickets: * A trip to Hong Kong in Economy Class * A trip to Hyderabad in Economy Class * A trip to Washington, D.C. in Economy Class Your client’s remaining Frequent Flyer Miles: 350 —————————————————————- Do you want to continue (y/n)? y —————————————————————- Please enter your client’s accumulated Frequent Flyer Miles: 3421 Please enter your client’s month of departure (1-12): 3 *** Your client has not accumulated enough Frequent Flyer Miles *** Your client’s remaining Frequent Flyer Miles: 3421 —————————————————————- Do you want to continue (y/n)? y —————————————————————- Please enter your client’s accumulated Frequent Flyer Miles: 154351 Please enter your client’s month of departure (1-12): 7 CSCI 470/502 Assignment 4: Mile Redeemer Console App Page 6 of 6 Your client’s Frequent Flyer Miles can be used to redeem the following tickets: * A trip to Sydney in Economy Class * A trip to Hong Kong in Economy Class * A trip to Hyderabad in Economy Class * A trip to Tokyo in First Class * A trip to New York in Economy Class Your client’s remaining Frequent Flyer Miles: 1 —————————————————————- Do you want to continue (y/n)? n ————————————————————————- THANK YOU FOR USING THE JAVA AIRLINES MILES REDEEMER APP ————————————————————————-
Create a class named Invoice that a hardware store might use to represent an invoice for an item sold at the store. An Invoice should include four pieces of information as instance variables – a part number (type String), a part description (type String), a quantity of the item being purchased (type int) and a price per item (double). The class you create should has two constructors. One that initializes the four instance variables and another that takes no arguments. Provide a set and get method for each instance variable. In addition, provide a method named getInvoiceAmount that calculates the invoice amount (i.e., multiplies the quantity by the price per item), then returns the amount as a double value. If the quantity is not positive, it should be set to 0. If the price per item is not positive, it should be set to 0.0. Write a test app name InvoiceTest that demonstrates class Invoice’s capabilities. InvoiceTest should declare five different invoice instances with different hardware store items. For example, hammer, phillips head screwdriver, light switch, cordless drill and carpenter’s square. You are going to be hardcoding the values for the instance variables for each of the five objects. It is not very realistic but it is okay to do this at this point. Then, use the get methods to print each invoice, one after the other, as follows: Invoice #1 Part No.: AB-23-4312 Item Desc.: Cordless Drill Quantity: 10 Item Price: 189.00 Invoice Subtotal: $1,890.00********************************* Invoice #2 and so on. Note that, in the above, the item price for the cordless drill would have been set to 189.00. Also, note that the DecimalFormat class should be used to place a floating dollar sign and commas in the output subtotal. The code and technique to do this can be found beginning on p. 8 of lecture notes 2. The maximum subtotal will be $99,999,999.99. This amount will help you determine your edit pattern for DecimalFormat’s method format.Be sure to add the required doc box to the top of both classes and submit both .java files on Blackboard before the due date and time.
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.### Your TaskYou 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 queue### Your TaskYou 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`.### Your Task– 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.### Your TaskYou 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.### Your TaskYou 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 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.### Your TaskYou 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.
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.### Your TaskYou 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.
There are a lot of situations that come along where it’d be really nice to be able to store data in higher than one dimension. You’ll come across several of them later in the course, but you’re ready to start working with one of them now.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.### Your Task– 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.
