This homework is… filter. All filter. You’ll feel like a barnacle afterwards. Especially since you’ll need to derive sustenance from the water around you: this homework does not have notes, so you’ll have to go to the Mathworks docs yourself! I’ll provide some links to documentation pages, and will make myself available as a resource, but this is an exercise in learning on your own. Good luck, and let me know if you have questions!The following table contains a few filter specifications: Class Type Rpass Rstop fpass fstop Butterworth bandpass 1 dB 50 dB fs/6, fs/3 fs/7, fs/2.5 Elliptic bandstop 1 dB 50 dB fs/7, fs/2.5 fs/6, fs/3 Chebyshev Type I lowpass 5 dB 40 dB fs/9 fs/8 Chebyshev Type II highpass 5 dB 40 dB fs/3 fs/4 Your task is to design them.Assume fs is 44.1 kHz. For each filter, do the following: 1. Either (a) use filterDesigner to generate a function that creates the given filter, then call that function, or(b) use fdesign and its associated functions to set filter specifications, create a filter object, and apply the filter. Use each of these strategies at least once. Since filterDesigner generates functions that use fdesign internally, it’s a useful tool to learn the syntax.2. Acquire a frequency response plot (both magnitude and phase) using fvtool.3. Apply the filter to 2 seconds of Gaussian white noise (samples from a normal distribution, assumed to be sampled at fs).4. Plot the Fourier transform of the filtered signal (using fft). It should look a lot like the filter response, as white noise has a uniform frequency spectrum. Refer to the notes for proper scaling and use of fft.5. Play back the unfiltered and filtered signals using soundsc and give your impressions: what, qualitatively, was the change the filter made?
This one is a bit longer than the last two – broadcasting and vectorization are extremely important, and they merit a bit of meditation. On The Air No reallocation, no loops, no help, no sanity… a typical day at the Copper Onion. Solve the following with vectorized operations. Broadcasting and meshgrid will be helpful here!1. Create the matrix R = −9 + 9i −8 + 9i . . . 8 + 9i 9 + 9i −9 + 8i −8 + 8i . . . 8 + 8i 9 + 8i . . . . . . . . . . . . −9 − 8i −8 − 8i . . . 8 − 8i 9 − 8i −9 − 9i −8 − 9i . . . 8 − 9i 9 − 9i (effectively a matrix of coordinates) in the tidiest way you can. (2 lines, 1 if very clever)2. Approximate ∫ 1 0 sin(t n ) dt for n = 1, 2, . . . , 50. Use trapz (the non-cumulative cousin of cumtrapz) and at least 10000 sample points. Try creating a vector of points and a vector of n values, combine them via broadcasting or meshgrid, and go from there. (3 lines)3. Let’s do something weird – like plot a sphere. (a) Create two matrices, theta and phi, as follows: [theta, phi] = meshgrid(… linspace(0, 2*pi, 5), … linspace(0, pi, 5)); (This counts as a one-liner in my book.) These will serve as our spherical coordinates θ and ϕ.(b) Find the x, y, and z coordinates they correspond to using the spherical coordinate conversions x = sin ϕ cos θ, y = sin ϕ sin θ, z = cos ϕ. 2 These should take the form of function calls and elementwise multiplies.(c) Plot these points using surf. Call pbaspect with appropriate arguments to make the axes nice and square. Provide a proper title. All the usual plotting stuff. Under The Sea Perform the following operations with overly clever indexing.All line counts include creation of data vectors/matrices. 1. Find the values in sin(linspace(0, 5, 100).*linspace(-5, 0, 100).’) which are closest to 1/2 (there are a few ties for closest), along with their 2d indices. (min, abs, and find may be useful!) (3 lines)2. Approximate the volume contained above by the surface z = e −(1−xy) 2 and below by the surface z = 1 4 √ x 2 + y 2 . You’ll have to use logical indexing to selectively sum up volume where one curve is actually over the other. (Serious bonus points if you 3d-plot the enclosed volume!) (3 lines, no plot)I Need a Vacation And now, the weather! Create the following matrices, using figure and imshow to visualize them. All these matrices are 256 × 256, and either contain floating-point values or logicals. Add a little comment describing each one (the meaning of “describe” is up to you, beyond basic technical information).Note: the notation aij means the element of A in row i, column j – i.e., A(i_index, j_index). 1. A where aij is true iff √ (i − 99) 2 + (j − 99) 2 < 29. 2. B where bij is true iff √ (i − 62) 2 + (j − 62) 2 < 58. 3. C where cij is true iff i − 4 sin( j/10) > 200.4. S = rand(256, 256, 3) with its two “lower” layers (3rd index 1 and 2) zeroed out. 5. M = A ∩ B C ( C denoting logical complement – in other words, ~). 6. Z = (C · S) + M (· denoting elementwise multiply).A Meshes & Broadcasting The concepts of broadcasting & meshgrid are often tricky to understand, so some illustrated examples are likely in order. I’ll start with meshgrid, because it comes naturally out of evaluating functions using matrices of coordinates – however, broadcasting (in my opinion) is a more versatile technique (and is often faster in practice), so keep reading to the end!A.1 The Grid Suppose you want to find the area under the surface z = x + y over the unit square (0 ⩽ x ⩽ 1, 0 ⩽ y ⩽ 1) . In order to do this in matlab, we could do a discrete Riemann sum: evaluate the function at points on a grid, transform each of those points into a rectangular prism, and sum the areas of those prisms.So… how do we create the grid of points? One way might be as follows: x = [ 0 .2 .4 .6 .8 1; … 0 .2 .4 .6 .8 1; … 0 .2 .4 .6 .8 1; … 0 .2 .4 .6 .8 1; … 0 .2 .4 .6 .8 1; … 0 .2 .4 .6 .8 1]; y = [ 0 0 0 0 0 0; … .2 .2 .2 .2 .2 .2; … .4 .4 .4 .4 .4 .4; … .6 .6 .6 .6 .6 .6; … .8 .8 .8 .8 .8 .8; … 1 1 1 1 1 1] z = x + y;Note the pattern in x and y here: each element of x contains its own x-coordinate, and each element of y contains its own y-coordinate (flipped vertically). We’re treating these matrices as gridded data: each element of x and y contains information about its corresponding point in the plane (namely, one of its coordinates).Evaluating the expression for z elementwise thus inserts the correct x & y coordinates at the correct positions in the matrix: the upper left corner has x = 0 and y = 0, so z = 0; the lower right corner has x = 1 and y = 1, so z = 2 – in general, each of the coordinates winds up in the right place, and z becomes 4 z = 0 .2 .4 .6 .8 1.0 .2 .4 .6 .8 1.0 1.2 .4 .6 .8 1.0 1.2 1.4 .6 .8 1.0 1.2 1.4 1.6 .8 1.0 1.2 1.4 1.6 1.8 1.0 1.2 1.4 1.6 1.8 2.0 which is a grid of evaluations of z = x + y. This can be used for any function (the notes show this technique used to evaluate z = exp(−x 2−y 2 ), which translates to matlab code as z = exp(-x.^2 – y.^2)), and, as such, is a handy technique.So much so that it has a name: those x & y matrices we created form a mesh, two matrices that form a gridded set of coordinates, and such meshes are typically generated not by hand (which is a pain) but by meshgrid. The following code generates identical matrices to those handcrafted above: [x, y] = meshgrid(0:.2:1); % same as before z = x + y; meshgrid takes in a vector (or two vectors, for non-square matrices) of coordinates and creates matrices which function as x, y coordinate inputs to vectorized functions. Try it out and see what it does!A.2 How To Broadcast meshgrid is usually only used where meshes are really necessary – places where being able to traverse the space of evaluation in two or three dimensions is necessary. Surface plots, like the sphere in this assignment, are one of those places: each z-coordinate needs an easy association with an x and y coordinate so that the plotting engine knows where the hell to put all the points.If, however, we just want the results of the evaluation (or want another technique to construct matrices really quickly), broadcasting is an alternative. You met broadcasting in the very first assignment when you performed C + A – an operation notably not valid in mathematics, because C and A were different shapes! They were, however, broadcastable shapes – C was a 4×4 matrix and A was a 4 × 1 column vector, so matlab simply repeated A four times and addedit to C: C + A → c11 c12 c13 c14 c21 c22 c23 c24 c31 c32 c33 c34 c41 c42 c43 c44 + w x y z → c11 c12 c13 c14 c21 c22 c23 c24 c31 c32 c33 c34 c41 c42 c43 c44 + w x y z w x y z w x y z w x y z → c11 + w c12 + w c13 + w c14 + w c21 + x c22 + x c23 + x c24 + x c31 + y c32 + y c33 + y c34 + y c41 + z c42 + z c43 + z c44 + z .Any two matrices with dimensions that can be made to match by this sort of repetition are broadcastable, and any elementwise operation may cause broadcasting to occur. For example, we could compute an elementary multiplication table very quickly using .*: first_factor = 0:9; % row vector, 1×10 second_factor = (0:9).’; % column vector (transposed), 10×1 mult_table = first_factor .* second_factor; % becomes 10×10To perform this calculation, matlab recognizes that if first_factor is repeated 10 times vertically and second_factor is repeated 10 times horizontally, both will be the same size, so it (effectively) does that, producing a 10×10 result.These examples are, of course, simple, to facilitate understanding. There’s more that can be done… but that’s up to you!
You are going to complete a program that sorts the nodes of a linked list. The program will load data from an input file specified by the user and create a linked list of pointers to data objects using the provided C++ list class. Each data object will consist of three C++ string fields which store the last name, first name, and social security number (ssn) of a hypothetical person.The last names have been chosen randomly from a set of the 500 most common last names according to the 2010 U.S. census. The first names have been chosen randomly from a set of the 250 most common male names and the 250 most common female names in the U.S. between 2010 and 2017. (It shouldn’t really matter if the data is accurate; I found it on-line, and I have posted text files containing the last names and first names used for the assignment.)The ssns have been randomly generated and have the format ddd-dd-dddd, where each character ‘d’ represents a digit. (Within each dataset, the ssns are guaranteed to be unique.) After creating the list, the program will sort the list. Items should be sorted according to last names; if last names are identical, they should be sorted according to first names; if both last and first names are identical, they should be sorted according to ssns (which are guaranteed to be unique). The sorted list will then be written to an output file. The input and output files will have the same format. The first row will be an integer indicating how many rows follow. Each row after that represents a single data object, including a last name, first name, and ssn, separated by single spaces. There will be no leading or trailing whitespace, and each row will be followed by a Unix-style newline character (‘ ’). I am providing you with code that handles most aspects of the program, and you may not make any changes to the provided code or its behavior (this will be explained further in class).The provided code includes the implementation of a simple class to store the data objects, the file loading routine that loads the data from an input file, and the file saving routine that writes the sorted data to an output file. There is also a call to a sort routine that you must fill in. You may also add additional functions, additional class definitions, or additional global variables, if you wish, but all the added code must be included below a specific comment which indicates that the code above the comment may not change. (You should even be able to include additional provided header files below the comment if you wish. If you want to do this, but your compiler does not support it, then include them at the top of the file, and mention this in your e-mail when you submit the program.) I may use the “diff” command to make sure you have not changed any code above the comment.Your program will be tested on four test cases, which I will refer to as T1, T2, T3, and T4. For each test case, a single file will exist using the format specified above; i.e., the first row will indicate the number of rows to follow, and each additional row will contain three strings representing a person’s last name, first name, and ssn.The contents of the four test cases will also adhere to the following specifications: • T1 will contain approximately (within 1 percent of) 100,000 data objects. Each data object will store a randomly selected last name, a randomly selected first name, and a randomly generated social security number (ssns are guaranteed to be unique within T1). • T2 will contain approximately (within 1 percent of) 1,000,000 data objects. Each data object will store a randomly selected last name, a randomly selected first name, and a randomly generated social security number (ssns are guaranteed to be unique within T2).• T3 will contain the same data objects as T2, but they will have already been sorted according to last names and first names, but not according to social security numbers. • T4 will contain approximately (within 1 percent of) 1,000,000 data objects. Each data object will store the same last name and the same first name (both selected randomly, but only once), and a randomly generated social security number (ssns are guaranteed to be unique within T4). Every working program will be assigned a score that is based on the CPU times that the program takes to sort the four test cases. If time1 through time4 are the CPU times required by the program when tested on T1 through T4, respectively, then the overall score for the program will be time1 + time2 + time3 + time4 (i.e., the sum of the four times). Assuming the program works (i.e., it generates the correct output for all four test cases), your program will be graded almost entirely based on this overall score just described. I expect working programs; penalties for non-working programs will be discussed in class. I reserve the right to take off a few points for poor indentation (which does not affect speed, since it is ignored by the compiler), but otherwise, you will not lose points for lack of elegance. Almost anything goes, as long as you write the program individually, and you do not violate any of the rules described here or in class.You may use any standard C++ classes or routines to which you have access, including the provided “sort” member function of the C++ list class (which provides an implementation of merge sort) or the provided “sort” function from the C++ algorithm library (which probably provides an implementation of a modified quicksort). However, you may not write code that changes the behavior of the provided code – this will be explained further in class. I will not provide my test data in advance. However, I will provide sample data that was generated the same way as my test data, and you can use this for testing. Furthermore, I will allow pre-submissions, and I will let you know roughly how your program is performing on my test data.Pre-submissions must arrive at least 48 hours before the program deadline, or I cannot guarantee they will be evaluated. More generally, expect that it may take me up to 48 hours to reply to a pre-submission. You may send multiple pre-submissions, but only one at a time (i.e., if you send a new pre-submission before I replied to your previous pre-submission, I will only evaluate the later one.) You may only submit one final program, which I will use for all four test cases. The program will not be told which test case it is dealing with; however, the program can attempt to figure out which test case it is dealing with, and it may use different strategies for each. You don’t really have to get that perfect, and in general, your program does not have to work for all possible test cases, as long as it ultimately works on my actual test data. I therefore highly encourage pre-submissions! If you send me a pre-submission, and I report back to you that the output is correct for the test data, then it does not matter what the probability of incorrect output was. I will compile all programs using the g++ compiler on an Ubuntu 22.04 virtual machine that is allocated 4 GB of RAM, and I will test the executable under this environment. No compiler optimization options will be used for any program. To be clear, I will compile the program like this: g++ . The compiler accepts C++11 features. It may accept features from C++14, C++17, and C++20, but you should check with a pre-submission if you are not sure. You may only use libraries and functions that are available with the standard, default g++ compiler on Ubuntu 22.04. If you are unsure if a library or function is valid, I strongly recommend sending a pre-submission, so I can let you know if your program compiles and runs correctly.You should not send me a Makefile (I will ignore it if you send one). Submit your program to me by e-mail to [email protected] as an attachment. Only send me your code (do not send object files, test data, or executable files). Your program is due before midnight on the night of Thursday, April 25. Barring extreme circumstances, there will be a strict late penalty of 5 points per day for programs submitted late. There is a lot of room for creativity with this assignment, so have fun with it!
You are going to write a program that manipulates stacks and queues. The program should ask the user for the name of an input text file and an output text file. The input file will contain a list of commands, one per line. Each command will direct the program to create a stack or a queue with a specified name, to push a value onto a specified stack or a queue, or to pop a value from a specified stack or a queue.(Most modern sources use the terms “enqueue” and “dequeue” to refer to insertions into and deletions from queues, respectively, but we will use the terms “push” and “pop” for both stacks and queues.) The input file will contain one command per line. To be valid, a command must follow a very specific format. The command must consist of two or three words, depending on the type of command, separated by single spaces. The line must have no leading whitespace before the first word or trailing whitespace after the last word. For the purposes of this assignment, a “word” is defined to be a sequence of letters and digits, except for words representing values of integers or doubles, which might also contain a single negative sign, and/or in the case of doubles, a single decimal point.All commands (i.e., all lines in the text file) will end with a single Unix-style newline character (‘ ’). The first word of each command must be “create”, “push”, or “pop” (using all lowercase letters). The second word must be a valid name for a stack or a queue. The first character of every name must be one of ‘i’, ‘d’, or ‘s’ (each lowercase), standing for integer, double, or string; this represents the data type that is stored in the particular stack or queue. The rest of the name must consist of only letters and digits. Both uppercase and lowercase letters are allowed, and the program should be case sensitive. If the first word is “create”, there must be a third word that will be either “stack” or “queue” (using all lowercase letters).This represents the type of list being created. No two lists may have the same name. However, two lists storing different data types (e.g., one list storing integers and another storing strings) may have the same name other than the first characters (for this case, ‘i’ or ‘s’). There cannot be a stack and a queue of the same data type that share the same name. If the first word is “push”, there must be a third word representing a value to be pushed onto the stack or queue.This value must match the appropriate type of the specified stack or queue, and it must fit in the storage of the type (e.g., an integer will fit in a 32-bit signed int); if the value is a string, it must be a single word, as defined above (i.e., containing only letters and digits). If the first word is “pop”, there must not be a third word. For the purposes of this assignment, you may assume that all commands in the input file will be valid! In other words, your program does not have to check that the lines in the input text file represent valid commands; you may assume that this will be the case, and I will only test the program on valid input files. Your program should read and process the commands in the text file. After each command is read, your program should output the string “PROCESSING COMMAND: ” followed by the text of the command and then a single Unix-style newline character. There should be exactly one space in between the ‘:’ and text of the command. All output should be written to the specified output file.Commands may also lead to additional output, as will be described below. Your program should process each command right after it is read and write the appropriate output to the output file. Your program should not need to loop through the input file more than once. So, you should not, for example, store all the commands in a list and then loop through them again. If the command is a “create” command, and the name of the stack or queue that is specified has already been created (whether it was created as a stack or a queue), the program should output the string “ERROR: This name already exists!” using the same casing as is displayed here.If the name is new, then the stack or queue should be created, and no additional output should be written. If the command is a “push” command, and the specified name does not exist, the program should output the string “ERROR: This name does not exist!” using the same casing as is displayed here. If the stack or queue does exist, the push operation should be applied, and no additional output should be written. If the command is a “pop” command, and the specified name does not exist, the program should output the string “ERROR: This name does not exist!” using the same casing as is displayed here.If the stack or queue does exist, but it is empty, the program should output the string “ERROR: This list is empty!” using the same casing as is displayed here. If the stack or queue does exist and is not empty, the pop operation should be applied, and the program should output “Value popped: “, using the same casing as is displayed here, followed by the value that is popped from the stack or queue. There should be exactly one space in between the ‘:’ and the value. For this assignment, a “pop” is assumed to both remove and return the appropriate value from the stack or queue (as is standard). You must follow these instructions exactly, so read them carefully! I will be comparing your output to my own using the “diff” command, available on Linux systems and Cygwin.Your program’s output should match mine exactly for all test cases. If there are any differences, you will lose points. Assume that the file commands1.txt exists in the current directory and contains the following text: create i1 queue create i1 queue create i1 stack create i2 stack create s99 stack push i1 50 push i1 100 push i2 -50 push i2 100 push s99 Hello push s99 World pop i2 pop s99 push s99 planet pop i2 push i2 150 pop s99 pop s99 create d99 stack push d99 0.123 push d99 -0.456 pop d99 pop s99 push dHelloWorld 0.5 pop dHelloWorld push i2 200 pop i2 pop i1 push i1 150 push i1 200 pop i1 create dHelloWorld stack create dHelloPlanet queue push dHelloWorld 3.14 pop i2 pop i2 push dHelloWorld 3.1415 push dHelloPlanet -60.5 push dHelloWorld -1 pop dHelloWorld pop dHelloPlanet pop sR2D2 create sR2D2 queue pop sR2D2 push sR2D2 123abcDEF push sR2D2 G4H5I6j7k8l9 pop sR2D2 pop sR2D2 pop sR2D2 pop dHelloWorld pop dHelloWorld pop dHelloWorld Then a sample run of your program might look like this: Enter name of input file: commands1.txt Enter name of output file: output1.txt After this run, the output file output1.txt should look exactly like this: PROCESSING COMMAND: create i1 queue PROCESSING COMMAND: create i1 queue ERROR: This name already exists! PROCESSING COMMAND: create i1 stack ERROR: This name already exists! PROCESSING COMMAND: create i2 stack PROCESSING COMMAND: create s99 stack PROCESSING COMMAND: push i1 50 PROCESSING COMMAND: push i1 100 PROCESSING COMMAND: push i2 -50 PROCESSING COMMAND: push i2 100 PROCESSING COMMAND: push s99 Hello PROCESSING COMMAND: push s99 World PROCESSING COMMAND: pop i2 Value popped: 100 PROCESSING COMMAND: pop s99 Value popped: World PROCESSING COMMAND: push s99 planet PROCESSING COMMAND: pop i2 Value popped: -50 PROCESSING COMMAND: push i2 150 PROCESSING COMMAND: pop s99 Value popped: planet PROCESSING COMMAND: pop s99 Value popped: Hello PROCESSING COMMAND: create d99 stack PROCESSING COMMAND: push d99 0.123 PROCESSING COMMAND: push d99 -0.456 PROCESSING COMMAND: pop d99 Value popped: -0.456 PROCESSING COMMAND: pop s99 ERROR: This list is empty! PROCESSING COMMAND: push dHelloWorld 0.5 ERROR: This name does not exist! PROCESSING COMMAND: pop dHelloWorld ERROR: This name does not exist! PROCESSING COMMAND: push i2 200 PROCESSING COMMAND: pop i2 Value popped: 200 PROCESSING COMMAND: pop i1 Value popped: 50 PROCESSING COMMAND: push i1 150 PROCESSING COMMAND: push i1 200 PROCESSING COMMAND: pop i1 Value popped: 100 PROCESSING COMMAND: create dHelloWorld stack PROCESSING COMMAND: create dHelloPlanet queue PROCESSING COMMAND: push dHelloWorld 3.14 PROCESSING COMMAND: pop i2 Value popped: 150 PROCESSING COMMAND: pop i2 ERROR: This list is empty! PROCESSING COMMAND: push dHelloWorld 3.1415 PROCESSING COMMAND: push dHelloPlanet -60.5 PROCESSING COMMAND: push dHelloWorld -1 PROCESSING COMMAND: pop dHelloWorld Value popped: -1 PROCESSING COMMAND: pop dHelloPlanet Value popped: -60.5 PROCESSING COMMAND: pop sR2D2 ERROR: This name does not exist! PROCESSING COMMAND: create sR2D2 queue PROCESSING COMMAND: pop sR2D2 ERROR: This list is empty! PROCESSING COMMAND: push sR2D2 123abcDEF PROCESSING COMMAND: push sR2D2 G4H5I6j7k8l9 PROCESSING COMMAND: pop sR2D2 Value popped: 123abcDEF PROCESSING COMMAND: pop sR2D2 Value popped: G4H5I6j7k8l9 PROCESSING COMMAND: pop sR2D2 ERROR: This list is empty! PROCESSING COMMAND: pop dHelloWorld Value popped: 3.1415 PROCESSING COMMAND: pop dHelloWorld Value popped: 3.14 PROCESSING COMMAND: pop dHelloWorld ERROR: This list is empty! I will provide links to this example’s input file and the output file from the course website.When I test your programs, however, I will additionally use a couple of additional test cases that I will not provide, including at least one that will be much longer (the longest test case will contain at least one hundred thousand pseudo-randomly generated commands). Typically, if you were to implement a program like this in C++, you would likely use the provided C++ list or vector class for everything. In other words, you would use it for stacks, for queues, and possibly for storing lists of stacks and queues. (There are also other provided classes you could use to store collections of stacks and queues that would allow you to access them more efficiently, but we haven’t covered those data structures yet.)Assuming you used the provided C++ list class for everything, you would probably create three separate high-level lists for the three different data types that you will be dealing with; for example, one list would store all stacks and queues holding integers (or pointers to all stacks and queues holding integers). While this would be completely reasonable, I am going to require you to create your own data structures for stacks and queues. The purpose of this assignment is not just to make sure that you understand how to use these data structures, but also to make sure that you understand how to implement these data structures, and to give you experience with several advanced aspects of C+ + including templates, inheritance, abstract classes, and polymorphism.In fact, you will need to mix these concepts together to implement this program well, and it can get confusing. I suggest you create an abstract base class called SimpleList that provides some aspects of singly linked list functionality. The base class should include protected member functions that provide the ability to insert a node at the start of the list, to insert a node at the end of the list, and to remove a node from the start of the list. You should include a private nested class called Node, which contains one field for data and another to point to the next node. See the textbook’s implementation of their List class as an example of something similar. The base class should maintain pointers to the start and end of the singly linked list. You can decide if you want to include header and/or tail nodes (a.k.a. dummy nodes or sentinel nodes) at the start and/or end of each list (but tail nodes probably don’t make sense for singly list lists). The base class should also include a private data member to store the name of the list and a public member function to retrieve it.The base class should also include two public pure virtual member functions for push and pop. The implementations of push and pop should be in derived classes, and each can be implemented as a simple, one-line member function that calls the appropriate member function of the base class (to insert at the start or end of the list, or to remove from the start of the list). You should also create two derived classes named Stack and Queue. You should use templates for all three classes so that you only need to code the base class and the derived classes once. Of course, I am leaving out a lot of details that you will have to figure out; e.g., even the constructors, which should accept the name of the stack or queue, can be syntactically confusing. In terms of the program functionality, other than class member functions, I personally used two functions to open the input and output files, a few functions for syntax checking (not required for your programs, so don’t bother with this), one template function to search for a SimpleList with a specified name, and one large function to parse the input file and process all the commands. Of course, the large function makes many calls to my other functions, including various member functions of my Stack and Queue classes. The large function utilizes three lists; one contains pointers to all stacks and queues of integers, another contains pointers to all stacks and queues of doubles, and the third contains pointers to all stacks and queues of strings. For these lists, you may, as I did, use the provided C++ list class. I’ll even show you my declarations: list listSLi; // all integer stacks and queues list listSLd; // all double stacks and queues list listSLs; // all string stacks and queues A new stack of integers can be created and added to the first list above with lines like these: SimpleList *pSLi; pSLi = new Stack(listName); listSLi.push_front(pSLi);Remember that your program does not have to check if commands are valid; you can assume that they will be. My program performs the checks, and it required about 150 lines of code to get that right. The total length of my program is a bit over 500 lines (including blank lines and comments, which account for about half of the lines). So, my program probably contains about (500 – 150) / 2 = 175 lines of code that implement the required functionality of this assignment. You are allowed to deviate from my suggestions if you wish, but you might lose points for anything in your code that I think is less elegant than my suggestions. The time it takes to do a push onto or a pop from a stack or queue should be worst-case O(M), where M is the total number of stacks and queues with the same data type as the current stack or queue. This is because you will need to do a linear search through the general list of the appropriate data type to find the stack or queue with the specified name, or to determine that it does not exist. (It is possible to make this more efficient using hash tables or balanced binary search trees, which we will learn about later in the course, but you don’t need to worry about that.) To search through one of the general lists for a stack or queue with some specified name, you will probably need to rely on iterators. I suggest creating a template function so that you only need to write a single function to search through the appropriate list. Once the appropriate stack or queue is found, the push or pop itself should be a worst-case constant time operation.This would not be the case if you use a vector or other resizable array to store nodes in your SimpleList class. (You would be able to achieve average constant time operations, but not worstcase constant time operations.) I am requiring that you use singly linked lists, which ensure worst-case constant time for push and pop if implemented correctly. Your program must be written in C++, and it must compile and run correctly using “g++” with either Cygwin (freely available for Windows) or Ubuntu (a popular distribution of Linux). I will test your program under one of these two environments. You may use C++11 features if you wish; if you do, depending on your compiler, you might have to specify the “-std=c++11” flag if you are using an older compiler.You may use C++14, C++17, C++20, or C++23 features as well, but only if the default compiler that comes with either Cygwin of Ubuntu supports them. (I’m not certain which C++20 and C++23 features are supported by g++.) Note: If you find yourself getting strange compiler errors involving templates, of course you may come to me with questions, but you might want to first check out this website, which I consider very helpful: https://isocpp.org/wiki/faq/templates Your grade will depend not only on correctness, but also style, elegance, comments, formatting, adherence to proper C++ conventions, and anything else I think constitutes good programming. You should include one comment at the top of your code with your name and a brief description of what the program does. You should also include comments above functions, class definitions, non-trivial member functions (either by their declarations or their implementations), and anywhere else where you think the code is doing something that is not obvious. Comments should be brief and should not state something that is obvious.This is an individual programming assignment. It is fine to ask each other questions, but you should not share code. Hopefully, you will be able to use some of the techniques you learned from the first programming assignment as you implement this one. Submit your program by e-mail sent to [email protected]. Send your code only (no executables or object files) as an attachment. I will compile your program and test it on my test cases. The assignment is due before midnight on the night of Tuesday, April 9. You may send me early pre-submissions, and I would let you know if they are working for my test cases, but I won’t look over your code until I am grading your final submissions. (It will typically take up to 48 hours to reply to pre-submissions, so you need to send them at least that long before the deadline to guarantee a reply.) This is a tough assignment, so get started early!
You are going to write a program that keeps track of mysterious creatures known as foobars. Every foobar has a name. For the purposes of this assignment, each name will be a string consisting of uppercase and lowercase letters and digits. It is possible that multiple foobars will have the same name.Foobars like to line up; when they do, it gives them strength. Foobars who are not standing in a line have zero strength. Ordinary foobars who are standing in a line have a strength equal to their position in the line. For example, if they are at the front of the line, their strength is 1, and if they are at the back of the line, their strength is N, where N is the number of foobars in the line. Some foobars have special status. For example, some foobars are foos. A foo’s strength is equal to their position in the line multiplied by 3. Some other foobars are bars. A bar’s strength is equal to their position in the line plus 15. (Some foobars are neither foos nor bars; these are what I referred to as “ordinary foobars” earlier. No foobar is both a foo and a bar.)Your program will read a sequence of foobars from a text file. Each line represents one foobar and contains two words. The first word will be “foobar”, “foo”, or “bar”, representing the type of foobar. The second word will be the name of the foobar. The information in the file represents a sequence of foobars standing in a line. The first line of the file represents the foobar at the back of the line; the last line of the file represents the foobar at the front of the line. There will be no leading or trailing whitespace, a single space between words, and a Unix-style newline character at the end of each line of the file.I will provide you with a text file called “sampleInput.txt”, with the following content (some of the names may seem odd): foobar R2D2 foo Carl foo Algorithms bar IAmABar bar xyz foo 123q456 foo CooperUnion bar DataStructures foobar xyz foo CooperUnionYour program should ask the user the for the name of the input file (e.g., “sampleInput.txt”) and the name of an output file (e.g., “sampleOutput.txt”). Do not hardcode filenames in your code. The output file should store information about the same foobars as the input file in the same order. Each line of the output file should list the name of the foobar (which might be a foo or a bar), followed by a single space, followed by their strength, followed by a single Unix-style newline character. A sample run of the program might look simply like this:Enter the name of the input file: sampleInput.txt Enter the name of the output file: sampleOutput.txt If you process the given file “sampleInput.txt”, and store the results in “sampleOutput.txt”, as indicated in the sample run, then the contents of “sampleOutput.txt” should look exactly like this: R2D2 10 Carl 27 Algorithms 24 IAmABar 22 xyz 21 123q456 15 CooperUnion 12 DataStructures 18 xyz 2 CooperUnion 3I am requiring that you store the information about each foobar in an object. Since every foo is a foobar, and every bar is a foobar, it makes sense to use a class hierarchy. A simple class diagram for such a hierarchy might look like this: Note that Foobar is the base class, a.k.a. superclass (not abstract, since some foobars are neither foos nor bars). Foo and Bar are derived classes, a.k.a. subclasses. The name of each foobar and its current position in a line should be stored in the base class as private data members. The base class should also have public member functions to set the position in a line, to get the name, and to get the strength (which is based on the position in the line).The member function to get the strength should be virtual, and it should be overridden in the derived classes. There should also be a protected member function to get the position (the derived classes will need this to determine the strength). The name should only be set once, in the base class’s constructor. The constructor should initially set the position to 0, meaning that the foobar is not currently in a line. Your program should loop through the input file only once, in a single pass, adding information about each foobar into a vector of pointers to Foobar objects. You can use the vector class’s“push_back” member function to add each pointer to the vector. (Although push_back is worstcase linear, because sometimes the vector needs to grow larger, it is implemented in such a way that it has amortized constant time.) After processing the input, your program should then loop through the vector backwards to update the position of each foobar (the final foobar in the vector is in line position 1, indicating the front of the line). Then, the program should loop through the vector forwards to display the information about each foobar to the output file.Note that I am not claiming this is the easiest way to implement this program; it almost certainly is not. The goal here is to force you to gain familiarity with various, important, object-oriented concepts that will be useful for later programs. Here are some additional suggestions: • I’m allowing you to place all your code in a single file, including your class definitions, the member function implementations, and the regular functions that implement your program. However, don’t put all your code in a single function. I suggest using separate functions to read the input file, to update the strength of foobars, and to write the output file. In particular, it is considered good convention to keep the “main” function of a program short.• Don’t use unnecessary global variables. Declare your main vector locally in “main” and pass it to other functions that use it by reference. • In the function that processes the input file, read each line of the input file one line at a time, using the provided “getline” function (part of the C++ standard library). I guarantee that the input file will be properly formatted (your code does not have to check). • Create an object of type “stringstream” (a provided class) for each line of input, and then read the words (indicating the type and name of the creature) from it just as if you were reading from standard input. Then, dynamically allocate a foobar, foo, or bar object, and add the pointer to it to your vector. When you allocate the object, pass the constructor the name of the foobar (the initial position should have a default value of 0).• After processing the input file, call another function to loop through the objects in the vector backwards, updating the line positions appropriately. Note that the strengths should not be stored in the objects; they are based on the position, which is stored. • In another function, loop through the vector in order, invoke appropriate member functions to get the names and strengths of the foobars, and write this information to the output file. Your grade will depend not only on correctness, but also style, elegance, comments, formatting, adherence to proper C++ conventions, and anything else I think constitutes good programming.You should include one comment at the top of your code with your name and a brief description of what the program does. You should also include comments above functions, class definitions, non-trivial member functions (either by their declarations or their implementations), and anywhere else that you think the code is doing something that is not obvious. Comments should be brief and should not state something that is obvious. This is an individual programming assignment. It is fine to ask each other questions, but you should not share code.Submit your program by e-mail to [email protected]. Send your source code only (no executables or object files) as an attachment. I will compile your program and test it on my test cases. I will not release my test cases to students; they will be much larger than the provided test case. (My largest input file contains millions of lines; I guarantee it will be small enough such that strengths of foobars do not overflow 32-bit integers.) The assignment is due before midnight on the night of Tuesday, March 12. You may send me early pre-submissions, and I will let you know if they are working for my test cases, but I won’t look over your code until I am grading your final submissions. (It will typically take up to 48 hours to reply to pre-submissions, so you need to send them at least that long before the deadline to guarantee a reply.) I advise you to get started early, especially if this is your first time writing an object-oriented program.
For this assignment, first, you are going to create a hash table class. Then, you are going to write a program that uses your hash table class to load a “dictionary” and spell check a “document”. For the purposes of this assignment, a valid word is defined as any sequence of valid characters, and the valid characters are letters (capital A – Z and lowercase a – z), digits (0 – 9), dashes (-), and apostrophes (‘).Every other character is considered a word separator. A dictionary is defined as a list of recognized words. The dictionary is guaranteed to contain exactly one word per line, with no leading or trailing spaces, followed by a single, Unix-style newline character ( ). Some of the words in the dictionary might not be valid (i.e., they may contain invalid characters). When loading the dictionary, invalid words, as well as words that are too long (see below), can optionally be ignored. The dictionary does not specify the meanings of words; it just lists them.The document to spell check may be any valid text file. Each line in the document will end with a single, Unix-style newline character. When spell checking the document, your program should indicate every unrecognized word, including the line number on which it occurs. Words should only be allowed to grow up to 20 characters. If a word in the document is too long, you should indicate the line number on which this occurs along with the first 20 characters of the word.The first line in the document is line 1. Words in the document that include digits (perhaps in addition to other valid characters) are technically valid but should not be spell checked (i.e., your program should ignore them). In the document, as previously stated, every character that is not a valid word character is a word separator; e.g., the string “abc@def” represents two valid words, “abc” and “def”. Therefore, there cannot be invalid words in the document.Your program should be case insensitive, and all capital letters in both the dictionary and the document should be converted to lowercase immediately upon seeing them. Your program must be written in C++. In order to implement this task efficiently, you will use a hash table. You must implement a hash table class using separate files, including a header file and a source code file. Not every member function of the class will be necessary for this assignment, but you will reuse this class for your next two assignments. Since our textbook provides code for the separate chaining and quadratic probing collision resolution strategies, I am requiring that you use either linear probing or double hashing. (Linear probing is a bit simpler to implement, and you will not receive any extra credit if you choose double hashing.)You are welcome to look at the book’s code for the other two strategies, but keep in mind that the instructions I am specifying for your hash table class make this different than the book’s implementation in several ways. For example, the book uses templates for its hash table class, but you will not. Also, your hash table class will allow the programmer to associate additional data with each entry, while the book’s implementation does not. More details about the requirements for your hash table class will be discussed later in this handout and in class. I will also discuss the use of void pointers in class. To process the dictionary, simply insert every word in the dictionary into the hash table.To spell check the document, locate every valid word in the document (keeping track of line numbers), and lookup (i.e., search for) each word in the hash table to see if it is recognized. You should assume that an average dictionary contains about 50,000 words, but that some might be as large as 1,000,000 words. This is my way of telling you that you should implement a rehash member function! A sample dictionary, a bit on the small side (approximately 25,000 words), will be posted on the course home page. Your program should prompt the user for the name of the dictionary file, the name of the document file to be spell-checked, and the name of the file where output should be written. Your program should indicate how long, in seconds, it takes to read the dictionary and how long it takes to spell check the document, measured in terms of CPU time.(These times should be displayed to standard output, not to the output file.) Your program must compile and run correctly using the g++ compiler on either Cygwin or Ubuntu. Your hash table implementation must include a header file called “hash.h” and a source code file called “hash.cpp”. The spell-checking code, and the rest of the main program, should be included in a separate file. You should also provide a makefile named “Makefile” that I can use to compile your program. I will provide a sample makefile that I used for my version of the program (also shown on the final page of this handout). I will also provide my version of “hash.h” (also shown later in this handout).You may reuse these two files directly if you wish. These files will also be posted on the course home page and discussed in class. A sample document, a sample run of the program using that document, and a sample output file appear on pages 3 and 4 of this handout. The document text file used for this sample run, as well as the dictionary used, will be available from the course home page. Your output file should adhere exactly to the format shown, and all output messages should be worded exactly the same way, with the same spacing. I will use “diff” to compare your output to mine, and you will lose points for any differences. (Of course, I will test your programs on multiple test cases involving different documents and dictionaries of various sizes.)The output displayed to standard output does not have to match my formatting, as long as the content is the same. Pages 5 and 6 of this handout show my “hash.h” file. Your hash table class must implement the same public member functions as mine. Note that the “getPointer”, “setPointer”, and “remove” member functions will not be used for this assignment; however, they will be used for future assignments! It is OK if you do not implement these member functions now. The specifics of this header file, and also the “Makefile” (shown on page 7 of this handout), will be discussed in more detail in class. Both files will also be made available to you from the course home page. When your assignment is complete, e-mail me ([email protected]) your program, including your source code files, your header file(s), and your makefile (even if you use the provided files).Do NOT send me your executable or object files (.o files). In addition to correctness, your grade may also depend on the efficiency and elegance of your code and adherence to proper C++ style. Your program is due before midnight on the night of Tuesday, September 24. Below are the lyrics to “Supercalifragilisticexpialidocious” from “Mary Poppins”. This represents the contents of the document “lyrics.txt” used in the sample run shown on the next page.This file will also be posted on the course home page. Um-deedledeedledeedle um-deedleday Um-deedledeedledeedle um-deedleday Um-deedledeedledeedle um-deedledeedle Um-deedledeedledeedle um-um um-um um-um For example… Supercalifragilisticexpialidocious Even though the sound of it is something quite atrocious If you say it loud enough you’ll always sound precocious Supercalifragilisticexpialidocious Um-deedledeedledeedle um-deedleday Um-deedledeedledeedle um-deedleday Um-deedledeedledeedle um-deedleday Super-super Supercali Super Supercalifragi So when the cat has got your tongue there’s no need for dismay Just summon up this word and then you’ve got a lot to say But better use it carefully or it can change your life For example… Yes? One day I said it to me girl and now me girl’s me wife Supercalifragilisticexpialidocious Even though the sound of it is something quite atrocious If you say it loud enough you’ll always sound precocious Supercalifragilisticexpialidocious Supercalifragilisticexpialidocious Even though the sound of it is something quite atrocious If you say it loud enough you’ll always sound precocious Supercalifragilisticexpialidocious Supercalifragilisticexpialidocious Even though the sound of it is something quite atrocious If you say it loud enough you’ll always sound precocious Supercalifragilistic Supercalifragilistic Supercalifragilisticexpialidocious Below is a sample run using the sample dictionary provided on the course home page and a text file that contains the lyrics to “Supercalifragilisticexpialidocious” from “Mary Poppins”.Enter name of dictionary: DICT/wordlist_small Total time (in seconds) to load dictionary: 0.031 Enter name of input file: FILES/lyrics.txt Enter name of output file: out_lyrics_small.txt Total time (in seconds) to check document: 0 The output file should look exactly like this: Long word at line 1, starts: um-deedledeedledeedl Unknown word at line 1: um-deedleday Long word at line 2, starts: um-deedledeedledeedl Unknown word at line 2: um-deedleday Long word at line 3, starts: um-deedledeedledeedl Unknown word at line 3: um-deedledeedle Long word at line 4, starts: um-deedledeedledeedl Unknown word at line 4: um-um Unknown word at line 4: um-um Unknown word at line 4: um-um Long word at line 8, starts: supercalifragilistic Long word at line 11, starts: supercalifragilistic Long word at line 13, starts: um-deedledeedledeedl Unknown word at line 13: um-deedleday Long word at line 14, starts: um-deedledeedledeedl Unknown word at line 14: um-deedleday Long word at line 15, starts: um-deedledeedledeedl Unknown word at line 15: um-deedleday Unknown word at line 17: super-super Unknown word at line 18: supercali Unknown word at line 19: supercalifragi Unknown word at line 21: has Unknown word at line 21: there’s Unknown word at line 21: dismay Unknown word at line 23: better Unknown word at line 23: carefully Unknown word at line 27: yes Unknown word at line 29: girl’s Long word at line 31, starts: supercalifragilistic Long word at line 34, starts: supercalifragilistic Long word at line 36, starts: supercalifragilistic Long word at line 39, starts: supercalifragilistic Long word at line 41, starts: supercalifragilistic Unknown word at line 44: supercalifragilistic Unknown word at line 45: supercalifragilistic Long word at line 46, starts: supercalifragilistic Below and on the next page, I am providing you with the header file (“hash.h”) for my hash table implementation. This file will also be posted on the course home page. #ifndef _HASH_H #define _HASH_H #include #include class hashTable { public: // The constructor initializes the hash table. // Uses getPrime to choose a prime number at least as large as // the specified size for the initial size of the hash table. hashTable(int size = 0); // Insert the specified key into the hash table. // If an optional pointer is provided, // associate that pointer with the key. // Returns 0 on success, // 1 if key already exists in hash table, // 2 if rehash fails. int insert(const std::string &key, void *pv = nullptr); // Check if the specified key is in the hash table. // If so, return true; otherwise, return false. bool contains(const std::string &key); // Get the pointer associated with the specified key. // If the key does not exist in the hash table, return nullptr. // If an optional pointer to a bool is provided, // set the bool to true if the key is in the hash table, // and set the bool to false otherwise. void *getPointer(const std::string &key, bool *b = nullptr); // Set the pointer associated with the specified key. // Returns 0 on success, // 1 if the key does not exist in the hash table. int setPointer(const std::string &key, void *pv); // Delete the item with the specified key. // Returns true on success, // false if the specified key is not in the hash table. bool remove(const std::string &key); private: // Each item in the hash table contains: // key – a string used as a key. // isOccupied – if false, this entry is empty, // and the other fields are meaningless. // isDeleted – if true, this item has been lazily deleted. // pv – a pointer related to the key; // nullptr if no pointer was provided to insert. class hashItem { public: std::string key {“”}; bool isOccupied {false}; bool isDeleted {false}; void *pv {nullptr}; hashItem() = default; }; int capacity; // The current capacity of the hash table. int filled; // Number of occupied items in the table. std::vector data; // The actual entries are here. // The hash function. int hash(const std::string &key); // Search for an item with the specified key. // Return the position if found, -1 otherwise. int findPos(const std::string &key); // The rehash function; makes the hash table bigger. // Returns true on success, false if memory allocation fails. bool rehash(); // Return a prime number at least as large as size. // Uses a precomputed sequence of selected prime numbers. static unsigned int getPrime(int size); }; #endif //_HASH_H This page shows the simple makefile, named “Makefile”, that I used for my program. This will also be posted on the course home page. I will also explain the use of makefiles in class. spell.exe: spellcheck.o hash.o g++ -o spell.exe spellcheck.o hash.o spellcheck.o: spellcheck.cpp hash.h g++ -c spellcheck.cpp hash.o: hash.cpp hash.h g++ -c hash.cpp debug: g++ -g -o spellDebug.exe spellcheck.cpp hash.cpp clean: rm -f *.exe *.o *.stackdump *~ backup: test -d backups || mkdir backups cp *.cpp backups cp *.h backups cp Makefile backups
You are going to create a class called “heap” that provides programmers with the functionality of a priority queue using a binary heap (a.k.a. heap) implementation. Each item inserted into the binary heap will specify a unique string id, an integer key, and optionally any pointer. The implementation of the class should use pointers to void, in order to handle pointers to any type of data.When a heap is declared, a capacity will be passed to its constructor representing the maximum number of items that may be in the heap at one time; the heap will never be allowed to grow past its initial capacity (although it is simple to implement a resize operation).I have written a program that uses my own implementation of the class. I will provide you with that program (useHeap.cpp) and with a Makefile. You should not change my source code file! You are allowed to -std=add c++11 or other flags to the Makefile if you need to. Both files will be discussed in class and can be obtained from the course home page. Your heap will also make use of the hash table class that you created for the previous programming assignment.This assignment asks you to fill in the missing heap.cpp and heap.h files, and to correct or add to your hash.cpp file if necessary, so that everything works. This implies that your heap class must include at least the following: a constructor that accepts an integer representing the capacity of the binary heap; a public member function, insert, used to insert a new item into the heap; a public member function, deleteMin, that removes and returns the item with the lowest key from the heap; a public member function, setKey, providing both increaseKey and decreaseKey functionality; and a public member function, remove, that allows the programmer to delete an item with a specified id from the heap. In class we will discuss the parameters of these member functions and their return values. In addition, your class should contain private data members and private member functions that allow you to elegantly and efficiently implement the required public member functions. I will discuss my own implementation in class, and it is described on the next page.In class, we will look at a sample run of the program and discuss the provided code. This program only passes string ids and integer keys to the insert member function of the heap class, but again, the insert member function should also optionally accept any pointer that can be stored and associated with the id. In the future, you will be using the class you are creating for this assignment to implement an algorithm involving graph data structures, and this functionality will be necessary. Also, note that the integer keys will not necessarily be positive integers.All operations should be implemented using average-case logarithmic time (or better) algorithms. In order to achieve setKey and remove in average-case logarithmic time, your program needs to be able to map an id to a node quickly. Since each id can be any arbitrary string, a hash table is useful for this purpose. Searching a heap to find an item with a particular id would require linear time, but a hash table in which each hash entry includes a pointer to the associated node in the heap allows you to find the item in constant average time. Apart from the calls to the hash table member functions, which are worst-case linear time but average-case constant time operations, all heap operations should use worst-case logarithmic time algorithms, and the insert operation should use an average-case constant time algorithm.My heap class contains four private data members. Two are simple integers representing the capacity and the current size of the heap. The third is a vector of node objects containing the actual data of the heap; each node contains a string id, an integer key, and a pointer to void that can point to anything. (I made “node” a private nested class within the heap class.) The fourth private data member is a hash table. Since the heap constructor is provided with the maximum size of the heap, you may construct the hash table to be large enough such that there is a small likelihood of a rehash, but that is up to you (I’ll discuss how to do that in class). Note that since items get removed from the heap, but only lazily deleted from the hash table, it is still possible that a rehash of the hash table will be necessary.Your heap.h file should contain the class definition of your heap class, including the declarations of its public and private data members and member functions. The heap.cpp file should contain the implementation of the class. I don’t think you should need to implement any functions other than the member functions of the class in this file (I did not).As usual, you will be graded not only on the correctness of your program, but also on the appropriateness of the decisions that you make, the elegance (and perhaps the formatting) of your code, and on the appropriate use of C++ concepts and routines.The following page shows the declarations of the constructor and the public member functions of my heap class along with my comments describing their functionalities, parameters, and return values. I am not showing the declarations of my private data members or private member functions here, but I will provide certain additional excerpts from my code; these will be posted on the course webpage and discussed further in class.E-mail me ([email protected]) your program, including all source code files, head files, and your Makefile (including any provided files that you use without making changes). Your program must compile and run using either Ubuntu or Cygwin. The program is due before midnight on the night of Tuesday, October 22. . // // heap – The constructor allocates space for the nodes of the heap // and the mapping (hash table) based on the specified capacity // heap(int capacity); // // insert – Inserts a new node into the binary heap // // Inserts a node with the specified id string, key, // and optionally a pointer. They key is used to // determine the final position of the new node. // // Returns: // 0 on success // 1 if the heap is already filled to capacity // 2 if a node with the given id already exists (but the heap // is not filled to capacity) // int insert(const std::string &id, int key, void *pv = nullptr); // // setKey – set the key of the specified node to the specified value // // I have decided that the class should provide this member function // instead of two separate increaseKey and decreaseKey functions. // // Returns: // 0 on success // 1 if a node with the given id does not exist // int setKey(const std::string &id, int key); // // deleteMin – return the data associated with the smallest key // and delete that node from the binary heap // // If pId is supplied (i.e., it is not nullptr), write to that address // the id of the node being deleted. If pKey is supplied, write to // that address the key of the node being deleted. If ppData is // supplied, write to that address the associated void pointer. // // Returns: // 0 on success // 1 if the heap is empty // int deleteMin(std::string *pId = nullptr, int *pKey = nullptr, void *ppData = nullptr); // // remove – delete the node with the specified id from the binary heap // // If pKey is supplied, write to that address the key of the node // being deleted. If ppData is supplied, write to that address the // associated void pointer. // // Returns: // 0 on success // 1 if a node with the given id does not exist // int remove(const std::string &id, int *pKey = nullptr, void *ppData = nullptr);
1.1 Description Figure 1: An example map of the city Lee wants to show his new invention, a special mirror, to his friends. These friends are scattered over the city, which consists of n nodes connected by m undirected edges. It takes wi time to pass through an edge, i = 1, …, m. Figure 1 shows a map of a city. For a path from the starting node s to the ending node t, Lee decided that he must go through k specific undirected edges E = {e1, e2, . . . , ek}.Please note that: 1. There is no pass order requirement for these specific edges; 2. If e1 = (u, v), Lee could pass the edge from u to v, he also could pass the edge from v to u. Lee could start from different nodes and end at different nodes. In addition, a pair consisting of a starting node sj and an ending node tj corresponds to a set of edges Ej , j = 1, …, q, which Lee must pass through. Since time is of the essence in the city, Lee needs to find the shortest possible path through all the specified edges.Here is a detailed example around Figure 1 with q = 2: 1. Lee starts from node s1 = 1 and ends at node t1 = 5. Besides, he is required to pass through an undirected edge E1 = {(1, 6)}(i.e. edge between 1 and 6). Then, his path is 1 → 6 → 1 → 3 → 7 → 5; 2. When Lee starts from node s2 = 2 and ends at node t2 = 7, he has to pass through two undirected edges E2 = {(1, 3),(1, 2)}. Therefore his path is 2 → 1 → 3 → 7.1.2 Input • The first line contains three integers n, m, and q, indicating the number of nodes n, the number of edges m, and the number of planned paths q.• The next m lines each contain three integers u, v, and w. These represent an edge between nodes u and v, with a traversal time of w. The edge described in the i-th line is numbered i. • For each of the next q blocks, the first line contains an integer ki .The following line contains ki integers e1, e2, . . . , eki , indicating the indices of the edges Lee must pass through. • The next q lines each contain two integers si and ti , indicating the starting point si and the ending point ti of each path.1.3 Output • q lines, i-th line indicating the smallest amount of time of i-th paths. Sample Input 1 7 9 2 1 2 3 5 4 3 3 1 1 6 1 9 3 4 2 1 4 4 3 2 2 3 7 1 5 7 2 1 4 2 1 3 1 5 2 7 Sample Output 1 22The graph of Sample 1 is shown in Figure 1. Sample Input 2 See attached q1sample2 . in Sample Output 2 See attached q1sample2 . out Sample Input 3 See attached q1sample3 . in Sample Output 3 See attached q1sample3 . outProblem Scale & Subtasks • k ≤ 5, q ≤ 100, wi ≤ 2 × 103 , 5 • n ≤ 1000, n − 1 ≤ m ≤ 2 × 103 , and 1 ≤ s, t ≤ n Test Case No. Constraints 1-2 m, n ≤ 100 3-5 n ≤ 500 6-10 n ≤ 10002.1 Description (a) The graph of 0-th day (b) The graph of 1-th day (c) The graph of 2-th day Figure 2: An example map of the park.Heath wants to have a date with his beloved Kathy. He decides to invite Kathy for a walk in a huge park. This park can be described as an undirected dynamic graph, consisting of n flowerbeds and m undirected edges connecting these flowerbeds. Each edge is filled with violets, Kathy’s favorite flower. The i-th edge has wi violets, i = 1, …, m.There are q + 1 days Heath could choose to have the date. Besides, at the beginning of i-th day, i = 0, 1, 2, …, q, the number of violets on a set of edges will change, where ki edges will be affected. Please note that i = 0 indicating the park has not changed yet.Heath wants to plan a no-duplicate-node path where he and Kathy will start from point si and end their tour at point ti . He hopes to maximize the minimum number of violets encountered on any noduplicate-node path throughout the entire path. You are expected to give him the maximum number of these values each day.A detailed example around Figure 2 with q = 2 is provided in the following. Heath will choose one of the 3 days to date: • At the beginning of 0-st day, the graph is shown in Figure 2(a); • At the beginning of 1-st day, k1 = 1. The value on edge (2, 3) changes to 4; • At the beginning of 2-nd day, k2 = 2. The value on edge (3, 4) changes to 1 and the value on edge (1, 3) changes to 5;Take Figure 2(a) as an example, Heath wants to start from 1 and end at 4 on 0-th day. There are three no-duplicate-node paths he can choose to date: 1. 1 → 2 → 3 → 4, with the number of violets on the path being 2, 1, and 4 respectively, and the smallest number is 1; 2. 1 → 3 → 4, with the number of violets on the path being 3, 4 respectively, and the smallest number is 3;3. 1 → 4, with the number of violets on the path being 6, and the smallest number is 6. Therefore, we choose the path with the largest minimum number, which is 1 → 4, and the answer is 6.2.2 Input • The first line contains two integers n and m, indicating there are n flowerbeds and m paths; • The next m lines each contain three integers u, v, and w, representing a path between flowerbeds u and v, lined with w violets;• The next line contains an integer q, the number of changes that will occur; • For each of the next q blocks, the first line contains an integer ki , the number of paths affected by the change. The following ki lines for each contain three integers a, b, and c, indicating that the path between flowerbeds a and b now has c violets;• For next q + 1 lines, there including two integer si , ti indicating that Heath will start from flowerbed si and end at flowerbed ti .2.3 Output • q + 1 integer, indicating the maximum number of fewest violets after every change. Sample Input 1 4 5 1 2 2 2 3 1 1 3 3 3 4 4 1 4 6 2 1 2 3 4 2 1 3 5 3 4 1 1 4 2 4 1 2 Sample Output 1 6 4 4 The dynamic graph of Sample 1 is shown in Figure 2. Sample Input 2 See attached q2sample2 . in Sample Output 2 See attached q2sample2 . out Sample Input 3 See attached q2sample3 . in Sample Output 3 See attached q2sample3 . outProblem Scale & Subtasks • 1 ≤ si , ti ≤ n, • m ≤ 2 × 104 , q ≤ 100, wi ≤ 104 , and • Heath can always reach t starting from s. Test Case No. Constraints 1-2 m, n ≤ 100 and ki = 1 3-5 n ≤ 100 and ki ≤ 10 6-10 n ≤ 104 and ki ≤ 103.1 Description Figure 3: An example map of La Mancha Land Don plays the role of a hero in the La Mancha Land parade, defeating monsters and obtaining treasures. Don has two attributes: health points (HPs) and spirit points (SPs). Since Don is very powerful, she can decide these values herself. Her adventure map can be viewed as an undirected simple connected graph with n nodes and m edges. Don needs to start from her hometown s and reach the treasure location t.Each time she passes an edge, her spirit point decreases by 1. Additionally, each edge has a monster with an attack power of ai . If Don’s spirit point is t, she loses ai t health points. The monsters cannot be defeated. Therefore, if Don passes through the same edge twice, she will suffer damage twice.To entertain the parade-goers, she wants to reach the destination at the most desperate moment, which means her spirit and health points are both exactly 0. While preparing her costume for the performance, she asks you to determine the minimum initial health points she needs to achieve her goal.Taking Figure 3 as an example, if Don starts from node 1 and ends at node 3, she has two paths to choose from: • 1 → 2 → 3: at node 1, Don has SP = 2 and HP = 4; and at node 2, Don has SP = 1 and HP = 3; and at node 3, his SP = 0 and HP = 0, which satisfies the requirement. • 1 → 3: at node 1, SP = 1, HP = 5; at node 3, SP = 0, HP = 0. Therefore, the minimum number of health points Don needs to maintain at the starting node is 4.3.2 Input • The first line contains four integers n, m, s, and t, indicating the number of nodes n, the number of edges m, Don starts from node s and ends at node t; • The next m lines each contain three integers u, v, and ai , representing an edge between node u and v, the attack power of monster is ai .3.3 Output • One integer, indicating the least health point Don needs. Sample Input 1 3 3 1 3 1 2 2 1 3 5 3 2 3 Sample Output 1 4The graph of Sample 1 is shown in Figure 3. Sample Input 2 See attached q3sample2 . in Sample Output 2 See attached q3sample2 . out Sample Input 3 See attached q3sample3 . in Sample Output 3 See attached q3sample3 . outProblem Scale & Subtasks Test Case No. Constraints 1-2 m, n, αi ≤ 10 3-6 n ≤ 103 , m ≤ 2 × 103 and αi ≤ 10 7-8 n ≤ 2 × 104 , m ≤ 4 × 104 , and αi = 1 9-10 n ≤ 2 × 104 , m ≤ 4 × 104 , and αi ≤ 100
1.1 Description Warrior has two important attributes, magic point(MP) and health point(HP). These two values are determined by the warrior at the beginning.The magic city can be regarded as an undirected simple connected tree (data structure) with n nodes and m edges. the warrior will walk in the city, from any starting leaf node to destination t which is the root node. Every time the warrior passes an edge, the magic point of the warrior will be reduced by 1. At the same time, there is a monster with attack power on each edge, and the warrior will fight with it. If the magic point of the warrior before passing this edge is k, and the attack power of the monster on this edge is w, then the battle when passing this edge will consume max(0, w − k) healthy points.The warrior wants to ensure that his magic point and health point are both zero when reaching node t at this time. Please find the minimum health point that the warrior needs at any beginning nodes. For example, let’s take n = 2, m = 1, and t = 1, there is only one edge (1, 2) with a monster whose attack power is 9. The warrior needs at least 8 healthy points as the warrior will spend 8 = max(0, 9−1) healthy points to cross this edge.Input 1 2 1 1 2 9 Output 8 Figure 1: Example. 4 1.2 Input • The first line has three integers n, m, t where n and m present the number of nodes and edges respectively. • The next m lines, each with three integers u, v, w, means there is an edge between the nodes u and v, and the attack power of the monster on the edge is w.(u and v = 1, 2, …, n) 1.3 Output • The minimum health point that the warrior needs at the beginning. Sample Input 1 8 7 1 1 2 5 2 3 5 3 4 5 4 5 5 5 6 5 6 7 5 7 8 5 Sample Output 1You can build a new tree and find the minimal health point that the warrior needs at the leaf node. Figure 2: The new tree of Sample 1 Sample Input 2 8 7 1 1 2 5 2 3 1 2 4 7 1 5 4 5 6 1 6 7 2 5 8 3 Sample Output 2Same with Sample 1, the maximal minimal health point is 8 at leaf node 4. Sample Input 3 See attached q1sample . in Sample Output 3 See attached q1sample . out Problem Scale & Subtasks • t = 1, m = n − 1, and 0 ≤ w Test Case No. Constraints 1-4 2 ≤ n < 10 5-8 10 ≤ n < 100 9-10 100 ≤ n ≤ 1000 5 Figure 3: The new tree of Sample 22.1 Description You are an outstanding employee of a supermarket. There are n items in the supermarket, each with a unique ID; there are also k shelves, which form a ring by connecting the first and last shelf. Your bag has a limited capacity, and you can only take a series of items whose total number is smaller or equal to bag size. Let’s take n=6, k=4, bag size=3 for example.Then ’n=6’ means there are 6 pieces of items in total, ’k=4’ stands for that there are 4 shelves in total and the selves’ ids are 0, 1, 2, 3 respectively. The four shelves are placed in a ring, such that shelf 0 is placed is right in front of shelf 1 and right behind shelf 3.Your bag has the size of 3, so you can take things whose whole number is smaller or equal to 3. The supermarket categorizes items using a hashing method: each item’s ID determines its assigned shelf number, calculated by id%k. The shelves are numbered from 0 to k − 1, and on each shelf the items are placed in descending order of their IDs, from front to back. 6 4 3 15 23.6 23 3.6 198 4.2 7 5.3 9 15.6 1453 31.1Here ,you can record them in tuples (shelf num, id, value), and you will get the following tuples: (3, 15, 23.6), (3, 23, 3.6), (2, 198, 4.2), (3, 7, 5.3), (1, 9, 15.6), (1, 1453, 31.1) After the hashing function and the sorting procedure, the final result is shown on the upper right, we can find out which shelf each item belongs to.Today, your boss is in a great mood and has given you the opportunity to take any continuous sequence of items from the shelves for free. However, there are two important restrictions: • You are only allowed to take thing continously, and the continuous sequence of items whose total number must be smaller or equal to bag size.Here you are not allowed to take (1,9,15.6), (1,1453,31.1) and (3,15,23.6) simultaneously. • You cannot take an equal number of items from any two shelves. The number of items taken from each shelf must be different. Here you are not allowed to take (1,9,15.6), (2, 198, 4.2) and (3,23,3.6) simultaneously, because that is illegal.• If there exists one and only one empty shelf between any two shelves with goods, we can skip it and consider the goods between the two non-empty shelves to be continuous; but if there are multiple continuous empty shelves between any two shelves with goods, we cannot connect them and consider them to be disconnected.Here, since there is nothing on shelf 0, we can ignore the shelf 0 and assume that (3, 7, 5.3) and (1, 1453, 31.1) are items placed next to each other and can be taken together. One optimal solution is taking 2 items from the third shelf and 1 item from the first shelf, yielding 23.6 + 5.3 + 31.1 = 60.0. In normal cases, what is the maximum total value of the items you can take for free? Please try to write a code to solve it.2.2 Input The first line contains three integers: n, k (the base for the hash operation), bag size (representing the total number of items you can take). In the next n lines, each line contains two values: • id[i] (a positive integer where 1 ≤ i ≤ n), • value[i] (the value of item i, a positive floating-point number where 1 ≤ i ≤ n).2.3 Output Output the maximum sum of values in a subinterval of size bag size, rounded to one decimal place, ensuring that the number of items taken from each shelf is unequal. 7 Sample Input 1 6 4 2 15 3.6 23 93.6 198 4.2 7 5.3 9 15.6 1453 41.1 Sample Output 1 97.2 Sample Input 2 9 6 5 3289 6652.7 7803 3590.7 659 5622.2 1542 7875.3 4563 3198.4 8757 2979.0 7777 8263.7 1068 387.7 7134 4324.3 Sample Output 2 27503.7 Sample Input 3 See attached q2sample . in Sample Output 3 See attached q2sample . out 2.4 Problem Scale & Subtasks Hint: bag size might be larger than n, k. k> 0, id > 0, value > 0 Test Case No. Constraints 1-3 0 < n ≤ 10 4-5 0 < n ≤ 100 6-7 0 < n ≤ 1000 8-10 0 < n ≤ 5000 11-12 0 < n ≤ 100000, bag size = 1
1.1 Description Given an n-length list, the value ai in the list satisfies that ai ∈ {1, …, n} and i = 1, …, n. Then, numbering each element ai in the list as bi , bi = i.Please find the minimum number of elements that should be deleted so that the list of remaining elements has the same elements as the list of their corresponding numbers.For example, given a list A = {2, 1, 2, 2, 4}, and its number list N = {1, 2, 3, 4, 5}. We need to delete the 3-rd and 5-th elements from lists A and N because numbers 3 and 5 are not in the list A. Then, the list A = {2, 1, 2} and its number N = {1, 2, 4}. However, since 4 is not in the list A, we need to delete the 3-rd element from lists A and N. Finally, we get the list A = {2, 1} and its number list N = {1, 2}, where the list A = {2, 1} has the same elements as its number list N = {1, 2}. Conclusively, we delete 3 elements from the list A.1.2 Input • The first line contains a positive integer n. • The second line contains the n-length list. 1.3 Output • The minimum number of deleted elements. Sample Input 1 5 2 1 2 2 4 Sample Output 1 3 Sample Input 2 5 1 3 4 2 5 Sample Output 2 0 For a list A = {1, 3, 4, 2, 5}, its number list is N = {1, 2, 3, 4, 5}. We do not need to delete any element from lists A and N since the list A has the same elements as its number list N. 4 Sample Input 3 See attached sample . in Sample Output 3 See attached sample . outProblem Scale & Subtasks For 100% of the test cases, 1 ≤ n ≤ 2 ∗ 105 . Test Case No. Constraints 1-6 n ≤ 10 7-8 n ≤ 100 9-10 n ≤ 2 ∗ 105 Hint Hint1 : You can use a queue to store elements that are not in a given list but are in its list of numbers.2.1 Description John is learning a new programming language called A++. Having just mastered loops, he is excitedly writing many programs that contain only loop structures. However, he does not know how to compute the time complexity of his programs. So he turns to you for help. What you need to do is to write a program to calculate the time complexity for each program that John writes.The loop structure in A++ is as follows: F i x y … // code block to be executed E Here ”F i x y” indicates creating a variable i initialized as x, then compare i with y, and enter the loop if and only if i is smaller or equal to y. Each time the execution of the code block inside the loop ends, i will be changed to i + 1. Then i will be compared with y to determine whether to enter the loop again. The loop ends when i becomes larger than y.Both x and y can be positive integers or the variable n. n represents the size of the data and must be retained during time complexity calculations. It cannot be treated as a constant. The value of n is much greater than 100. x is guaranteed to be smaller or equal to y.”E” indicates the end of the loop. When the loop ends, any variables created within that loop are also destroyed. Note: For the sake of convenience in writing, the uppercase letter O is used to represent the standard notion of Θ when describing time complexity in this problem.2.2 Input The first line contains a positive integer t, indicating that John writes t (1 ≤ t ≤ 10) programs in total (the programs contain only loop structures). Note that the loop structures are allowed to be nested. The following lines describe the t programs in order.For each program, the first line contains a positive integer L (1 ≤ L ≤ 20000), indicating the number of lines in this program. The next L lines describe the program in detail: each line is either in the form of ”F i x y” or ”E”, where i is a lowercase letter (it is guaranteed that i will not be letter ”n”), x andy are either variable n or positive integers smaller than 100, and x is guaranteed to be smaller or equal to y. Since John has mastered loops quite well, there will be no syntax errors in his programs. i.e. F and E are guaranteed to match each other and he will not use variables that haven’t been destroyed in a loop.2.3 Output Output t lines, each indicating the time complexity of a program, in the order of the input. In this problem, time complexity is either in the form of O(1) or O(nˆw), where w is a positive integer smaller than 20000. O(1) means constant time complexity and O(nˆw) means that the time complexity is O(n w) Sample Input 1 6 2 F i 1 1 E 2 F x 1 n E 4 F x 5 n F y 10 n E E 4 F x 9 n E F y 2 n E 4 F x 9 n F y n n E E 4 F y 1 99 F x n n E E Sample Output 1 O (1) O(n ^1) O(n ^2) O(n ^1) O(n ^1) O (1)Problem Scale & Subtasks Test Case No. Constraints Properties 1-3 L ≤ 10 A 4-6 L ≤ 500 7-10 L ≤ 20000 A: For each program, the first L/2 lines are in the form of ”F i x y”, and the lines from L/2 + 1 to L are in the form of ”E”.
1.1 Description You are given a sequence of integers ai of length n. Additionally, you are given m operations to perform on this sequence. Each operation is one of the following: – Given k, x, y, c, update the value of ak using the formula: ak =(x 2 + ky + 5x) mod P ∗ c Obviously, the resulting value will be between [1 − P, P − 1], where c = ±1. – Query the sum of all elements in the sequence, i.e., compute: Xn i=1 ai– Query the maximum number of distinct values in the sequence if each element is multiplied by either 1 or −1 (you can flip the sign of some elements and count the maximum number of distinct numbers). Your task is to process these operations efficiently.1.2 Input The first line contains three integers n, m and P (1 ≤ n, m ≤ 106 , 1 ≤ P ≤ 106 ) — the length of the sequence, the number of operations and the divisor in modulo operation, respectively. The second line contains n integers, representing the original value of the array a, denoted as a1, a2, …, an (−P < a[i] < P).Each of the next m lines contains a description of one of the following types of operations: – For update operations, the line will contain five integers 1, k, x, y, c (1 ≤ k ≤ n, 0 ≤ x, y >n for C++ and n = scanner.nextLong() for Java to get the input n. And the other operations for long and long long are quite same as int. Hint2 : The process of Sample Input 1 can be described as in the Figure 1. Hint3 : This problem can be easily solved by following the above process from bottom to top. Hint4 : Consider how using the data structure, such as dictionary or list, to store the indices of li and ri can help solve the problem.
1.1 Description You are given a tree with n nodes, where each edge in the tree has a corresponding weight denoting the length of each edge. The nodes in the tree are colored either black or white. Your task is to calculate the sum of distances between every pair of black nodes in the tree. Let B = {b1, b2, …} a set of black nodes, then the answer is formulated as: Ans = |B X |−1 i=1 X |B| j=i+1 dist(bi , bj ) where |B| denotes the number of the black nodes in the tree, and dist(bi , bj ) is the length of the simple path from the i-th to j-th black node.Write a program to calculate the sum of distances on the tree between every pair of black nodes Ans in the given tree. 1.2 Input The first line contains an integer n, representing the number of nodes in the tree. The second line contains n space-separated integers {c1, c2, . . . , ci , . . . , cn} where ci is either 0 or 1.ci = 1 indicates that the i-th node is black, and ci = 0 indicates that the i-th node is white. The following n − 1 lines, {l1, l2, . . . , lp, . . . , ln−1}, denoting the structure of the tree follow, each line lp contains 2 integers qp and wp, denoting an edge of length wp between the p + 1-th node and the qp-th node.1.3 Output Output the sum of distances for every pair of black nodes in the tree. Sample Input 1 5 0 1 1 1 1 1 1 1 2 3 2 3 1 Sample Output 1 18 4 This sample considers a tree with 5 nodes: 1 2 3 4 5 1 2 2 1 The 1-st node is white, and 2-, 3-, 4-, 5-th nodes are black. The length of edge: (2-nd, 1-st): 1, (3-rd, 1-st): 2, (4-th, 3-rd): 2, (5-th, 3-rd): 1. Ans = ((1 + 2) + (1 + 2 + 2) + (1 + 2 + 1)) + (2 + 1) + 2 + 1 = 18.Sample Input 2 9 0 1 0 1 1 1 1 1 1 1 2 1 3 2 2 2 1 5 2 5 3 1 2 7 1 Sample Output 2Three additional large-scale samples are included in the provided files, namely, A samplecase1.in/.ans, A samplecase2.in/.ans and A samplecase3.in/.ans. Problem Scale & Subtasks For 100% of the test cases, 1 ≤ n ≤ 105 , 1 ≤ qp−1 < p, 1 ≤ wp ≤ 1000 Test Case No. Constraints 1-4 n ≤ 100 5-7 n ≤ 1000 8 qp = p 9 qp = 1 10 No additional constraintsHint It can be proven that the given structure is definitely an unrooted tree. For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It may be too small for this problem. You need other data types, such as long long for C/C++ and long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Use scanf(“%lld”,&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the input n. And the other operations for long and long long are quite same as int. For Python users, if there occurs a RecusrionError, see here.2.1 Description Mario bought n math books and he recorded their prices. The prices are all integers, and the price sequence is a = {a0, a2, …ai , …, an−1} of length n (n ≤ 100000). Please help him to manage this price sequence. There are three types of operations: • BUY x: buy a new book with price x, thus x is added at the end of a.• CLOSEST ADJ PRICE: output the minimum absolute difference between adjacent prices. • CLOSEST PRICE: output the absolute difference between the two closest prices in the entire sequence. A total of m operations are performed (1 ≤ m ≤ 100000). Each operation is one of the three mentioned types. You need to write a program to perform given operations. For operations ”CLOSEST ADJ PRICE” and ”CLOSEST PRICE” you need to output the corresponding answers.2.2 Input The first line contains two integers n and m, representing the length of the original sequence and the number of operations. The second line consists of n integers, representing the initial sequence a. Following that are m lines, each containing one operation: either BUY x, CLOSEST ADJ PRICE, or CLOSEST PRICE (without extra spaces or empty lines).2.3 Output For each CLOSEST ADJ PRICE and CLOSEST PRICE command, output one line as the answer. Sample Input 1 3 4 7 1 9 CLOSEST_ADJ_PRICE BUY 2 CLOSEST_PRICE CLOSEST_ADJ_PRICE Sample Output 1 6 1 6 Sample Input 2 6 12 30 50 39 25 12 19 BUY 4 CLOSEST_PRICE BUY 14 CLOSEST_ADJ_PRICE CLOSEST_PRICE BUY 0 CLOSEST_PRICE BUY 30 BUY 12 CLOSEST_PRICE BUY 20 CLOSEST_PRICE Sample Output 2 5 7 2 2 0 0 Two additional large-scale samples are included in the provided files, namely, B samplecase1.in/.ans and B samplecase2.in/.ans.Problem Scale & Subtasks For 100% of the test cases, 2 ≤ n, m ≤ 1 × 105 , 0 ≤ ai , x ≤ 1012 Test Case No. Constraints 1-4 n ≤ 103 , m ≤ 103 5-6 There is no CLOSEST PRICE operation 7-9 ai and x are uniformly distributed at random within the range [0, 1012] 10 No additional constraintsHint For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It may be too small for this problem. You need other data types, such as long long for C/C++ and long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Use scanf(“%lld”,&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the input n. And the other operations for long and long long are quite same as int. For Python users, if there occurs a RecusrionError, see here.
1.1 Description Imagine a group of n players that are located in different floors. The i-th player (for each i such that 1 ≤ i ≤ n, where i is an integer) is characterized by the following: • pi , a unique starting floor level • hi , a starting HP (Health Points) value • di , a direction of movement, either U indicating that the i-th player is going upward or D indicating that the i-th player is going downwardAll players move simultaneously at the same speed in their respective directions. When two players meet, they engage in a battle. The player with the lower health is eliminated instantaneously, while the other continue to move in the same direction at the same speed but with a reduced HP by 1. In a case where two players have identical HP, they are both eliminated simultaneously after the battle. Your task is to determine the final HP of the surviving players.1.2 Input The first line of input contains an integer n, representing the number of players. The next n lines follow. The i-th line contains three values: pi , hi , di – an integer representing the starting floor level for the i-th player, an integer representing the HP value for the i-th player, and a character representing the direction of movement for the i-th player.1.3 Output For each surviving player, output their remaining HP on a separate line, in the order of their input. Sample Input 1 5 5 11 U 4 15 U 3 17 U 2 77 U 1 30 U Sample Output 1 11 15 17 77 30 4 Sample Input 2 5 5 3 U 4 7 D 1 5 U 3 5 D 8 6 U Sample Output 2 3 7The following figures show the visual representations for both input samples in their initial positions, respectively.Problem Scale & Subtasks For 100% of the test cases: • 1 ≤ n ≤ 106 • 1 ≤ pi ≤ 108 (for each i such that 1 ≤ i ≤ n) • 1 ≤ hi ≤ 100 (for each i such that 1 ≤ i ≤ n) • di ∈ {U, D} (for each i such that 1 ≤ i ≤ n) Test Case No. Constraints 1-4 n ≤ 1 000 5-8 n ≤ 10 000 9-10 No additional constraints2.1 Description Jack Sparrow, the legendary pirate of the Seven Seas, sets sail to an inhabited island in search of a buried treasure. Guided by his map, he believes the treasure lies within a weird-looking trench. The trench stretches across a width of n. For any given point from i − 1 to i on the trench’s x-coordinate, the depth is represented by di (for each i such that 1 ≤ i ≤ n, where i is an integer).Jack is wondering about the size of the largest treasure that could possibly fit inside the trench. Wanting to maximize his haul, he turns to you, a trusted member of his crew, to make the calculations. By largest, Jack means the maximum area – the product of width and height – of the rectangular treasure chest that can be buried within the trench’s confines. For example, the following figure shows the largest possible treasure that can fit in a trench with n = 8 and d = [6, 2, 5, 4, 5, 1, 4, 4]. Could you give these calculations a look for our legendary pirate?2.2 Input The first line contains an integer T, representing the number of Jack Sparrow’s queries. The descriptions of T queries follow. Each query is described in the following format: • The first line contains an integer n representing the width of the trench. • The second line contains n integers separated by a space representing the depths of the trench.2.3 Output Output T lines. The j-th line contains the answer to the j-th query. Sample Input 1 2 8 6 2 5 4 5 1 4 4 3 2 7 4 Sample Output 1 12 8Problem Scale & Subtasks For 100% of the test cases: • 1 ≤ T ≤ 10 • 1 ≤ n ≤ 106 • 1 ≤ di ≤ 106 (for each i such that 1 ≤ i ≤ n) • The sum of n over all queries, denoted as N, does not exceed 106 in each test case. Test Case No. Constraints 1-2 n ≤ 10 3-4 n ≤ 1 000 5-8 N ≤ 10 000 9-10 No additional constraintsHint Hint 1: For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It may be too small for this problem. You need other data types, such as long long for C/C++ and long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Use scanf(“%lld”,&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to output the answer query. And the other operations for long and long long are quite same as int.Hint 2: Sailing through the vast expanse of the Seven Seas, Jack Sparrow found himself drawn to an intriguing map. Tantalized by the prospect of hidden riches, he anchored near a mysterious island with an unusual trench. As he examined the trench’s varying depths, he pondered the size of the treasure that might be buried within. Carefully, he sought the counsel of a trusted crew member to calculate the chest’s potential dimensions. Knowing the importance of this task, the crew member took to the challenge, hoping to maximize the treasure for their legendary captain.
1.1 Description In a queue, people are supposed to stand in ascending order of their heights. However, due to some confusion, the order of the queue gets disrupted. Your task is to determine the number of disorder pairs in the queue.A disorder pair is defined as a pair of people (pi , pj ) such that i < j and pi is taller than pj in the queue, which means their order is reversed.For example, consider a queue with 5 people: [180, 160, 175, 170, 170]. In this case, there are 6 disorder pairs: (180, 160), (180, 175), (180, 170), (180, 170), (175, 170) and (175, 170). Please note that (170, 170) is not considered as a disorder pair. Write a program to calculate the number of disorder pairs in a given queue.1.2 Input The first line of input contains an integer N (1 ≤ N ≤ 106 ), representing the number of people in the queue. The second line contains N space-separated integers p1, p2, . . . , pN (1 ≤ pi ≤ 109 ), representing the heights of people in the queue.1.3 Output Output a single integer, the number of disorder pairs in the queue. Sample Input 1 6 1 2 3 4 5 6 Sample Output 1 0 Sample Input 2 5 180 160 175 170 170 Sample Output 2 6Problem Scale & Subtasks Test Case No. Constraints 1-4 N ≤ 1000 5-8 N ≤ 10000 9-10 N ≤ 106Hint For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It may be too small for this problem. You need other data types, such as long long for C/C++ and long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Use scanf(“%lld”,&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the input n. And the other operations for long and long long are quite same as int.2.1 Description Renko Usami observes space through a telescope when she notices a fantastic phenomenon – the number of stars in the fields follows a mathematical pattern. Specifically, let’s denote the number of stars in the Nth field by fN , then fN satisfies the following expression, and a, b are given positive integers. fN = afN−1 + bfN−2 (N ≥ 2)Now Renko Usami is curious about how many stars in the nth field, but the nth field is too far away to be observed through her cheap astronomical telescope. Since there are so many stars, she only cares about the value of the number of stars modulo m. In other words, she want to know fn mod m. Fortunately, Renko Usami is able to observe the two closest star fields to her, and the numbers of stars in fields are f0 and f1. Unfortunately, she is going to be late again for her appointment with Merry. Can you write a program for her to calculate fn mod m?2.2 Input The only line of the input contains 6 integers n(1 ≤ n ≤ 1018), a, b, f0, f1(1 ≤ a, b, f0, f1 ≤ 100), m(1 ≤ m ≤ 2 × 109 ). – the meanings of these numbers are shown in the problem description.2.3 Output Output a single integer – fn mod m. Sample Input 1 4 1 1 1 1 1000 Sample Output 1 5 Sample Input 2 468908 34 29 33 30 998244353 Sample Output 2 829261643Problem Scale & Subtasks For 100% of the test cases, 1 ≤ n ≤ 1018, 1 ≤ a, b, f0, f1 ≤ 100, 1 ≤ m ≤ 2 × 109 . Test Case No. Constraints 1-2 n ≤ 10 3-5 n ≤ 106 6-10 No additional constraintsHint Hint1 : For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It may be too small for this problem. You need other data types, such as long long for C/C++ and long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Use scanf(“%lld”,&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the input n. And the other operations for long and long long are quite same as int.Hint2 : Here’s a simple definition of the modulo operation. Your output should be the remainder of the Euclidean division of fn by m, where fn is the dividend and m is the divisor. And for the modulo operation the following equation holds: (x + y) mod m = ((x mod m) + (y mod m)) mod mHint3 : When a and b are 1, fn is Fibonacci Sequence. Here is a way to compute the Fibonacci Sequence by using matrices: 1 1 1 0 f1 f0 = f2 f1 The Matrix 1 1 1 0 is called transition matrix. Also, note that matrix multiplication is associative. By multiplying the transition matrix n − 1 times, we can get the fn.
1.1 Description If you have ever played Genshin Impact, you must remember “Divine Ingenuity: Collector’s Chapter” event. In this event, players can create custom domains by arranging components, including props and traps, between the given starting point and exit point.Paimon does not want to design a difficult domain; she pursues the ultimate “automatic map”. In the given domain with a size of m × n, she only placed Airflow and Spikes. Specifically, Spikes will eliminate the player (represented by ‘x’), while the Airflow will blow the player to the next position according to the wind direction (up, left, down, right represented by ‘w’, ‘a’, ‘s’, ‘d’, respectively).The starting point and exit point are denoted by ‘i’ and ‘j’, respectively. Ideally, in Paimon’s domain, the player selects a direction and advances one position initially; afterward, the Airflow propels the player to the endpoint without falling into the Spikes. The player will achieve automatic clearance in such a domain.However, Paimon, in her slight oversight, failed to create a domain that allows players to achieve automatic clearance. Please assist Paimon by making the minimum adjustments to her design to achieve automatic clearance.Given that the positions of the starting point and exit point are fixed, you can only adjust components at other locations. You have the option to remove existing component at any position; then, place a new direction of Airflow, or position a Spikes.1.2 Input The first line of input contains two integers m and n, representing the size of the domain. m lines follow, each containing n characters. The characters must be one of ‘w’, ‘a’, ‘s’, ‘d’, ‘x’, ‘i’ and ‘j’. It is guaranteed that there is only one ‘i’ and ‘j’ on the map, and they are not adjacent.1.3 Output Output a single integer, representing the minimum number of changes needed. Sample Input 1 3 3 dsi ssd jdd Sample Output 1 1You can make one modification to transform the domain as Fig. 2, allowing automatic clearance by choosing to move left initially. → ↓ i ↓ ↓ → j → → Figure 1: Original Domain in Sample 1 → ↓ i ↓ ↓ → j ← → Figure 2: Modified Domain in Sample 1 Sample Input 2 4 4 jxsx xdxa dxax xwxi Sample Output 2You can make 4 modifications to transform the domain as Fig. 4, and choose to move upwards initially. j x ↓ x x → x ← ↓ x ← x x ↑ x i Figure 3: Original Domain in Sample 2 j ← ← x x → ↑ ← ↓ x ← ↑ x ↑ x i Figure 4: Modified Domain in Sample 2 You can find More Sample in the attached file on BB.Problem Scale & Subtasks Test Case No. Constraints 1-4 3 ≤ m, n ≤ 20 5-8 3 ≤ m, n ≤ 500 9-10 3 ≤ m, n ≤ 2000 Hint Hint1 : The player cannot move outside the domain, and initially, they can choose any direction to move from the starting point. Hint2 : Consider the scenario where the cost is 0 when the player moves with the wind and 1 otherwise. What can the original problem be transformed into?2.1 Description Give you a graph with n vertices and m edges. No two edges connect the same two vertices. For vertex ID from 1 to n, we do the following operation: If any two neighbors of a vertex have a k× relationship in terms of their IDs, we add a new edge between them. In other words, for any vertex i = 1 to n, if u = kv or v = ku, we add an edge (u, v), where u, v ∈ Neighbor(i). Besides, if there is already an edge between u and v, no operation is taken.After the operation, we want you to output the BFS order starting from vertex s. Please traverse all neighbors in ascending order of their IDs when expanding a vertex.2.2 Input The first line of input contains four integers n, m, k and s. m lines follow, each containing two integers a, b, indicating that there is an edge between a and b. There is no self-loop and repeated edges.2.3 Output Output the smallest BFS order of the new graph. Sample Input 1 5 5 2 3 1 2 1 3 2 3 3 4 4 5 Sample Output 1 3 1 2 4 5 Figure 5: Original Graph Figure 6: Modified Graph As shown in Fig. 6, due to the 2× relationship between neighbors 2 and 4 of vertex 3, We add a new edge (2, 4) to the original graph. You can find More Sample in the attached file on BB.Problem Scale & Subtasks For 100% of the test cases, 1 ≤ n, m ≤ 105 , 2 ≤ k ≤ 105 . Test Case No. Constraints 1-4 n, m ≤ 100 5-7 n, m ≤ 1000 8-10 n, m ≤ 100000Hint Hint1 : For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It may be too small for this problem. You need other data types, such as long long for C/C++ and long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Use scanf(“%lld”,&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the input n. And the other operations for long and long long are quite same as int.Hint2 : Note that we deal with the vertices in increasing order. For example, in the following graph, when k = 2, we will add an edge between 2 and 4 when dealing with 3. Then 1 and 2 become the neighbors of 4, and we will add an edge between 1 and 2.However, in the following graph, we add an edge between 2 and 4 when dealing with 5. Then 1 and 2 become the neighbors of 4. But we have already visited vertex 4 (before visiting 5), so we will not add an edge between 1 and 2.3 Obstacle (optional) This question is optional and will not be included in the grade. 3.1 Description In the piggy kingdom, there are n cities and m roads connecting them. A road connects two different cities. For some reason, there are obstacles on some of the roads. The city 1 and city n are two important cities of the kingdom, and many people travel between these two cities. However, because of the obstacles, it may need more time to go from 1 to n. Now, the pig king wants to remove the obstacles. Since it takes a lot of time and money to remove the obstacles, the king decides to only remove two of them. Suppose the distance between city 1 and city n decreased by D after removing the obstacles. The king wants to know the maximum value of D. Your task is to find this value.3.2 Input The first line of input contains two integers n and m. m lines follow, each containing four integers a, b, c, d, indicating that there is a road between a and b with length c. If d is 0, there is no obstacle on the road. If d is 1, there is an obstacle on the road. There might be more than one road between two cities.It is guaranteed that one can travel from city 1 to city n via the roads without obstacles. 3.3 Output Output a single integer, representing the maximum value of D. Sample Input 1 5 7 1 2 1 0 2 3 2 1 1 3 9 0 5 3 8 0 4 3 5 1 4 3 9 0 4 5 4 0 Sample Output 1The original distance is 17, and the distance after removing the two obstacles is 11. You can find More Sample in the attached file on BB.Problem Scale & Subtasks For 100% of the test cases, 1 ≤ n, m, c ≤ 105 . Test Case No. Constraints 1-2 n, m ≤ 10 3-5 n, m ≤ 100 6-7 n, m ≤ 1000 8-10 n, m ≤ 100000 Hint Hint1 : For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It may be too small for this problem. You need other data types, such as long long for C/C++ and long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Use scanf(“%lld”,&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the input n. And the other operations for long and long long are quite same as int. Hint2 : Do not get stuck on the original graph. Try to build a new graph to solve the problem.
This assignment contains a set of problems that are to be completed in one C file. For this assignment, you are provided a skeleton file (with some code) in the assignment page called smallprogram8skeleton.c. The file has the following definition of a typedef struct. typedef struct{ char * fname; //first name char * lname; //last name char * show; //favorite show }record_t; The typedef struct has three members that are all character pointers to a respective heap (dynamic string). In this assignment, you are managing a dynamic array of the typedef struct. The file will compile on Eustis and run, however it is not fully completed. In this assignment you are going fill in the remainder code. The remainder code will involve implementing 4 user defined functions for each problem. The file must be named smallprogram8_lastname_firstname.c, where lastname and firstname is your last and first name (as registered in webcourses). For example Dr. Steinberg’s file would be named smallprogram8_Steinberg_Andrew.c. Make sure to include the underscore character _. If your file is not named properly, points will be deducted. The script the graders use will pull your name from the file name properly. It is imperative you follow these steps so you can get your points! Small Program 8 Page 1 Testing on Eustis It is your responsibility to test your code on Eustis. If you submit your assignment without testing on Eustis, you risk points being deducted for things that may behave differently on your operating system. Remember, you cannot dispute grades if your code didn’t work properly on Eustis all because it worked on your machine. The Eustis environment gives the final say. Plan accordingly to test on Eustis!! The Python Script File! Read Carefully! A python script has been provided for you to test your code with a sample output of Dr. Steinberg’s solution. This script will check to make sure your output matches exactly with Dr. Steinberg’s solution file as the graders are using this to grade your assignments. The script removes leading and trailing white space, but not white space in the actual text. If there is anything off with the output (including the expected answer), the script will say your output is not correct. This includes your output producing the correct answer, however there is something off with the output display. The script does not point directly where your mistake(s) are in the code. It will only produce a success or unsuccessful output message as a whole. If you get an unsuccessful output my suggestion is to look at the sample solution text file provided to see what is different from your answer and Dr. Steinberg’s when comparing. If you have extra white space or new lines or even just missing a space/new line, you will lose points that won’t be changed! Make sure you place the python script in the same directory as your C file. You can use the ls command to check to see if the following items are in the directory. ls You should these three files in your directory. 1. Your C File. 2. The Python Script File 3. Sample Solution Text File If you have these three files. You are ready to run the script. Use the following command to test your code with Dr. Steinberg’s provided solution sample. python3 sp8test.py If the script says your output is incorrect, checkout the sample text file that was generated (a new text file will be created from the script that contains YOUR output). If your numbers are off or different from Dr. Steinberg’s, then that means there is something not right with code’s logic and calculating the answer. However if your numbers match with Dr. Steinberg’s solution, Small Program 8 Page 2 then that means there is extra/missing white space or newlines detected. Compare the text file generated by the script with solution text file line by line to find the missing/extra white space or newlines. Once you believe you found the error, rerun the script to see if the output matches. Now, you are probably wondering how the graders will know if you have memory leaks in your code. The script the graders are using involves valgrind which checks for memory leaks. You will learn more about this in CS1, but it’s good to be exposed to this tool and understand how it works. In your test script, valgrind will be executed with your code. The script will check to see if you have any memory leaks. If your code has no memory leaks, then a message like this will be displayed to the terminal. You may run into getting the correct output with this memory leak message. Please note that if you submit code that has correct output, but memory leaks will result in point deductions. Figure 1: Sample of valgrind informing the user that memory leaks have occurred. The Rubric Please see the assignment page for the established rubric on webcourses. Comment Header Make sure you place a comment header at the top of your C file. You will use single line comments to write your name, professor, course, and assignment. For example, Dr. Steinberg’s header would be: //Andrew Steinberg //Dr. Steinberg //COP3223C Section 1 //Small Program 8 Small Program 8 Page 3 Missing a comment header will result in point deductions! The Solution Text File You are provided a solution file that was created by Dr. Steinberg’s Python Script. Now you may notice some strange things about the file. In this assignment, you are going to write statements that involve interacting with the user. Now you are probably wondering from the solution text file where the interaction is happening? The fact is that the Python script handles the interaction. The script creates an input stream that feeds it input. That is why you don’t see the input directly in the text file. For example, the text file on line 1 says Enter a size for the dynamic array: What would you like to do?. Here this looks like we should be typing input, however the python script has already fed it input. That is why you don’t see the values except for the results. In each problem, a screenshot of the C file being executed manually without the Python script shows how it looks on a normal run. Carefully look at the output in the pictures provided. Note: The arrow symbolizes that the text wrapped onto the next line of the pdf file. In the text file itself it is actually one whole line. Small Program 8 Page 4 samplesolutionsp8.txt Enter a size for the dynamic array: What would you like to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Insert was selected… Enter the first name: Enter the last name: Enter favorite show: What would you like ,→ to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Insert was selected… Enter the first name: Enter the last name: Enter favorite show: What would you like ,→ to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Insert was selected… Enter the first name: Enter the last name: Enter favorite show: What would you like ,→ to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Display was selected… ——————————— myarray[0].fname = Kasey myarray[0].lname = Moss myarray[0].show = The Lucy Show myarray[1].fname = Estrella myarray[1].lname = Holder myarray[1].show = Loki myarray[2].fname = Zara myarray[2].lname = Forbes myarray[2].show = Modern Family ——————————— What would you like to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Insert was selected… Enter the first name: Enter the last name: Enter favorite show: What would you like ,→ to do? Small Program 8 Page 5 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Insert was selected… Array is full…Need to doubleIt… Enter the first name: Enter the last name: Enter favorite show: What would you like ,→ to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Display was selected… ——————————— myarray[0].fname = Kasey myarray[0].lname = Moss myarray[0].show = The Lucy Show myarray[1].fname = Estrella myarray[1].lname = Holder myarray[1].show = Loki myarray[2].fname = Zara myarray[2].lname = Forbes myarray[2].show = Modern Family myarray[3].fname = Adam myarray[3].lname = Goldberg myarray[3].show = The Goldbergs myarray[4].fname = Terrence myarray[4].lname = Shaffer myarray[4].show = The Good Place ——————————— What would you like to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Remove was selected… Select an index of record to remove… What would you like to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Display was selected… ——————————— myarray[0].fname = Kasey myarray[0].lname = Moss Small Program 8 Page 6 myarray[0].show = The Lucy Show myarray[1].fname = Estrella myarray[1].lname = Holder myarray[1].show = Loki myarray[2].fname = Zara myarray[2].lname = Forbes myarray[2].show = Modern Family myarray[3].fname = Terrence myarray[3].lname = Shaffer myarray[3].show = The Good Place ——————————— What would you like to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Insert was selected… Enter the first name: Enter the last name: Enter favorite show: What would you like ,→ to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Display was selected… ——————————— myarray[0].fname = Kasey myarray[0].lname = Moss myarray[0].show = The Lucy Show myarray[1].fname = Estrella myarray[1].lname = Holder myarray[1].show = Loki myarray[2].fname = Zara myarray[2].lname = Forbes myarray[2].show = Modern Family myarray[3].fname = Terrence myarray[3].lname = Shaffer myarray[3].show = The Good Place myarray[4].fname = Harry myarray[4].lname = Potter myarray[4].show = Stranger Things ——————————— What would you like to do? Small Program 8 Page 7 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Insert was selected… Enter the first name: Enter the last name: Enter favorite show: What would you like ,→ to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Display was selected… ——————————— myarray[0].fname = Kasey myarray[0].lname = Moss myarray[0].show = The Lucy Show myarray[1].fname = Estrella myarray[1].lname = Holder myarray[1].show = Loki myarray[2].fname = Zara myarray[2].lname = Forbes myarray[2].show = Modern Family myarray[3].fname = Terrence myarray[3].lname = Shaffer myarray[3].show = The Good Place myarray[4].fname = Harry myarray[4].lname = Potter myarray[4].show = Stranger Things myarray[5].fname = Gary myarray[5].lname = Foley myarray[5].show = The Flight Attendant ——————————— What would you like to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Remove was selected… Select an index of record to remove… What would you like to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Display was selected… Small Program 8 Page 8 ——————————— myarray[0].fname = Kasey myarray[0].lname = Moss myarray[0].show = The Lucy Show myarray[1].fname = Estrella myarray[1].lname = Holder myarray[1].show = Loki myarray[2].fname = Zara myarray[2].lname = Forbes myarray[2].show = Modern Family myarray[3].fname = Terrence myarray[3].lname = Shaffer myarray[3].show = The Good Place myarray[4].fname = Harry myarray[4].lname = Potter myarray[4].show = Stranger Things ——————————— What would you like to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Insert was selected… Enter the first name: Enter the last name: Enter favorite show: What would you like ,→ to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Display was selected… ——————————— myarray[0].fname = Kasey myarray[0].lname = Moss myarray[0].show = The Lucy Show myarray[1].fname = Estrella myarray[1].lname = Holder myarray[1].show = Loki myarray[2].fname = Zara myarray[2].lname = Forbes myarray[2].show = Modern Family myarray[3].fname = Terrence myarray[3].lname = Shaffer myarray[3].show = The Good Place Small Program 8 Page 9 myarray[4].fname = Harry myarray[4].lname = Potter myarray[4].show = Stranger Things myarray[5].fname = Tiffany myarray[5].lname = Rivera myarray[5].show = Full House ——————————— What would you like to do? 1: Insert a record 2: Display records 3: Remove record 4: Exit Enter an option: Exiting… Small Program 8 Page 10 Problem 1 Write the definition of the user-defined function insert. The function takes three arguments. The first argument is the reference to a heap of record_t. The function will insert a new record into the heap. Make sure to take into consideration if malloc doesn’t work! Once the heap is updated, the reference is returned. Also, make sure to take into consideration if the array is full! If it is full, you will display Array is full…Need to doubleIt… to the terminal and call doubleIt which you will implement in problem 2. The following figure shows the output. Figure 2: Sample output for problem 1. Problem 2 Write a user defined function called doubleIt that will double the size of the dynamic array. For example, if the dynamic array initially holds at max 5 elements, then doubleIt will create a new dynamic array that holds 10 elements (it will also copy the content from the initial dynamic array). The user defined function takes two arguments in the call. The first argument is a pointer to the heap that contains your initial dynamic array. The second argument is an integer that holds a primitive integer value representing the size. The function returns a reference to the heap that contains the new dynamic array. You cannot use realloc or any built in memory function for this question. If realloc or any built in memory function is used, then no credit is given for the question. Note you will need to modify the insert function bit as doubleIt should be called from insert. Think about when the function would be invoked! Make sure to take into consideration if malloc doesn’t work! Problem 3 Write a user defined function called removeRecord that delete a specific content of the dynamic array. The function takes three arguments. The first argument is the reference to the dynamic array, the second argument represents the current size of the array (meaning valid entries it holds), and the last argument is the index of the value to be remove. Make sure to consider the scenario if the index is out of bounds. The function returns a primitive value that represents the new current size of the dynamic array. Otherwise display the message Invalid Index and return the current size if the remove cannot happen due to invalid index. Hint: Use the shift technique for removing. Small Program 8 Page 11 Problem 4 Write a user defined function called freeRecords. The function takes two arguments. The first argument is the reference to the dynamic array and the second is the current size of the array. The function gives back memory from the heap. Nothing is returned from the function.
For each problem in the assignment, you will create the definition of the user-defined function that is asked in the description. If you do not create a user-defined function for each of the problems, then you will receive no credit for the problem. Creating user-defined functions is good practice! You also must write the function prototypes! Missing function prototypes will result in points being deducted. Function prototypes are also good practice as well. The file must be named smallprogram7_lastname_firstname.c, where lastname and firstname is your last and first name (as registered in webcourses). For example Dr. Steinberg’s file would be named smallprogram7_Steinberg_Andrew.c. Make sure to include the underscore character _. If your file is not named properly, points will be deducted. The script the graders use will pull your name from the file name properly. It is imperative you follow these steps so you can get your points! Testing on Eustis It is your responsibility to test your code on Eustis. If you submit your assignment without testing on Eustis, you risk points being deducted for things that may behave differently on your operating system. Remember, you cannot dispute grades if your code didn’t work properly on Small Program 7 Page 1 Eustis all because it worked on your machine. The Eustis environment gives the final say. Plan accordingly to test on Eustis!! The Python Script File! Read Carefully! A python script has been provided for you to test your code with a sample output of Dr. Steinberg’s solution. This script will check to make sure your output matches exactly with Dr. Steinberg’s solution file as the graders are using this to grade your assignments. The script removes leading and trailing white space, but not white space in the actual text. If there is anything off with the output (including the expected answer), the script will say your output is not correct. This includes your output producing the correct answer, however there is something off with the output display. The script is going to run 5 unique scenarios for each problem (5 Test Cases). Each test case contains a different set of input values being used to ensure your code produces the correct answer. Back in your previous assignments, Dr. Steinberg would provide 1 sample solution that you would upload to Eustis. Now, there are 5 solution text files you are going to need to upload to Eustis. Before you test your program, your directory in Eustis should look something like this: If you have these files, you are ready to run the script. Use the following Figure 1: Your setup for testing on Eustis. 5 sample txt files (provided for you in Webcourses), your C program, and the python test script. command to test your code with Dr. Steinberg’s provided solution sample. python3 sp7test.py After you run the script, 5 new text files are going to be generated. These files are the solution output for each test case. If the script says your output is incorrect, checkout the sample text file that was generated (a new text file will be created from the script that contains YOUR output). If your numbers are off or different from Dr. Steinberg’s, then that means there is something not right with code’s logic and calculating the answer. However if your numbers match with Dr. Steinberg’s solution, then that means there is extra/missing white space or newlines detected. Compare the text file generated by the script with solution text file line by line to find the missing/extra white space or newlines. Once you believe you found the error, rerun the script to see if the output matches. Small Program 7 Page 2 Figure 2: Your Eustis setup after running the script in Eustis. The Rubric Please see the assignment page for the established rubric on webcourses. Comment Header Make sure you place a comment header at the top of your C file. You will use single line comments to write your name, professor, course, and assignment. For example, Dr. Steinberg’s header would be: //Andrew Steinberg //Dr. Steinberg //COP3223C Section 1 //Small Program 7 Missing a comment header will result in point deductions! Small Program 7 Page 3 Problem 1 Write a user defined function called deblank that takes a string phrase output and a string phrase input argument and copies the input argument with all blanks removed and stores the result in the output string. Blanks are the white spaces in a string. For this problem, declare the strings of size 20 and ask the user to input one to store. Display the output result in the main function. The following figure shows a sample output in the terminal. Figure 3: Sample output for problem 1. Make sure it matches for the python script. Problem 2 Write a user defined function called pluralize that takes a noun as a string input and will pluralize the word. The result should be displayed in the main function. Note the following rules about noun plurals: a) If noun ends in “y”, remove the “y” and add “ies”. b) If noun ends in “s”, “ch”, or “sh”, add “es”. c) In all other cases, just add “s”. For this problem, declare a string of size 20 and ask the user to input one. The following figure shows a sample output in the terminal. Figure 4: Sample output for problem 2. Make sure it matches for the python script. Small Program 7 Page 4 Problem 3 Write a user defined function called fact that takes a one word string as input and determines how many letters, digits, and punctuation characters it contains. The results should be displayed in the user defined function. For this problem, declare a string of size 20 and ask the user to input one. The following figure shows a sample output in the terminal. Figure 5: Sample output for problem 3. Make sure it matches for the python script. Problem 4 Write a user-defined function called substring that takes two strings as arguments. If the second string (in the argument) is contained, the memory address at which the contained string begins is returned. For example, substring(“turkey”, “key”) would return the memory address of the k in “turkey”. Otherwise return a NULL pointer. In the main function, ask the user for the two strings. Once the strings are entered, call the user defined function. Once the function has returned a resulting value, display message of the result. For example substring(“turkey”, “key”) would cause the message “Substring key exists!” to be displayed. The function call substring(“store”, “too”) would cause the message ”Substring too doesn’t exist!” to be displayed. Note: The strings are only single words. Do not worry about sentences! You cannot use the built in strstr() function to solve this problem or any built in memory function! Using any of these functions will result in a score of 0 for this question. You can assume that the first string argument is always bigger than the second string argument. For this problem, declare a string of size 20 and ask the user to input one. The following figure shows a sample output in the terminal. Super Big Hint: Your function is going to return an address type value, think about how your user defined function header would look. You should have notice something during lectures. Figure 6: Two sample outputs for problem 4 when the substring exists and doesn’t exists. Make sure it matches for the python script. Small Program 7 Page 5
For each problem in the assignment, you will create the definition of the user-defined function that is asked in the description. If you do not create a user-defined function for each of the problems, then you will receive no credit for the problem. Creating user-defined functions is good practice! You also must write the function prototypes! Missing function prototypes will result in points being deducted. Function prototypes are also good practice as well. The file must be named smallprogram6_lastname_firstname.c, where lastname and firstname is your last and first name (as registered in webcourses). For example Dr. Steinberg’s file would be named smallprogram6_Steinberg_Andrew.c. Make sure to include the underscore character _. If your file is not named properly, points will be deducted. The script the graders use will pull your name from the file name properly. It is imperative you follow these steps so you can get Small Program 6 Page 1 your points! Testing on Eustis It is your responsibility to test your code on Eustis. If you submit your assignment without testing on Eustis, you risk points being deducted for things that may behave differently on your operating system. Remember, you cannot dispute grades if your code didn’t work properly on Eustis all because it worked on your machine. The Eustis environment gives the final say. Plan accordingly to test on Eustis!! The Python Script File! Read Carefully! A python script has been provided for you to test your code with a sample output of Dr. Steinberg’s solution. This script will check to make sure your output matches exactly with Dr. Steinberg’s solution file as the graders are using this to grade your assignments. The script removes leading and trailing white space, but not white space in the actual text. If there is anything off with the output (including the expected answer), the script will say your output is not correct. This includes your output producing the correct answer, however there is something off with the output display. The script is going to run 5 unique scenarios for each problem (5 Test Cases). Each test case contains a different set of input values being used to ensure your code produces the correct answer. Back in your previous assignments, Dr. Steinberg would provide 1 sample solution that you would upload to Eustis. Now, there are 5 solution text files you are going to need to upload to Eustis. Before you test your program, your directory in Eustis should look something like this: After you run the script, 5 new text files are going to be generated. These Figure 1: Your setup for testing on Eustis. 5 sample txt files (provided for you in Webcourses), your C program, and the python test script. files are the solution output for each test case. If you have these files, you are ready to run the script. Use the following command to test your code with Dr. Steinberg’s provided solution sample. python3 sp6test.py Small Program 6 Page 2 Figure 2: Your Eustis setup after running the script in Eustis. The Rubric Please see the assignment page for the established rubric on webcourses. Comment Header Make sure you place a comment header at the top of your C file. You will use single line comments to write your name, professor, course, and assignment. For example, Dr. Steinberg’s header would be: //Andrew Steinberg //Dr. Steinberg //COP3223C Section 1 //Small Program 6 Missing a comment header will result in point deductions! Small Program 6 Page 3 Problem 1 Write a user defined function called meanMinMax that takes an int array as an argument. The function will use the array that is declared in the main function that contains SIZE elements. The function will calculate the mean of the values stored in the array and also determine the max and min values inside the array within the function definition. These results will be displayed in the user defined function definition. The following figure shows a sample output of the problem. Read the Important section of this assignment to understand the array you are using for all of these problems. Figure 3: Sample output from problem 1. Make sure it matches for the python script. Problem 2 Write a user defined function called mySort that takes an int array (same one from the previous problem) as an argument. The function will sort the array in increasing order. Do not use any built in sorting function. If a built in sorting function is used, then no credit will be given for this problem. The following figure shows a sample output of the problem. Call the display function after calling mySort in the main function. Figure 4: Sample output from problem 2 from calling display after mySort. Make sure it matches for the python script. Small Program 6 Page 4 Problem 3 Write a user defined function called doubleShift. This function shifts values over by 2 indexes to the right (increasing index) in the array. Here is an example when the array has 5 elements before and after the function is called. The function takes the int array (same one from previous problems) as an argument. Figure 5: Sample of how doubleShift works with an array of 5 elements. Call the display function after calling doubleShift in the main function. Figure 6: Sample output from problem 3 from calling display after doubleShift. Make sure it matches for the python script. Small Program 6 Page 5 Problem 4 Write a user-defined function called reverse. The function flips the position of the values in reverse order. The following figure shows a sample with an array of 5 elements. You cannot use Figure 7: Sample of how reverse works with an array of 5 elements. an additional array for this problem. If an additional array is used, then points will be deducted. Call the display function after calling reverse in the main function. Figure 8: Sample output from problem 4 from calling display after reverse. Make sure it matches for the python script.
