Overview In discrete‐time signal processing, it is often necessary to convert a signal from one sampling rate to another. A common example is the conversion from the sampling rate of a compact disk (CD); signal (44.1 KHz) to that of a Digital Audio Tape (DAT) signal (48 KHz). Another example is the aud io standard in High‐Definition Television (HDTV) transmission, where at least three sampling rates are supported (32, 44.1, and 48 KHz). Although in principle we may convert the signal back to analog form and resample at the desired rate, it is usually preferable to perform t he entire conversion digitally. This is clue to many considerations including the fact that conversion to analog form often introduces noise in the signal, and that digital signal processing can be much more cost‐effective and flexible. This MATLAB project asks you to perform a sampling rate conversion on segments of audio signals. The input audio signals are quantized to 8 bits and sampled with a sampling frequency of 11,025 Hz. You are required to convert the signal to a sampling rate of 24,000 Hz in a computationally efficient manner. Although one conceptual way of realizing this sampling rate conversion process is to upsample the signal, lowpass filter, and downsample it, a more clever implementation can lead to an implementation that is many times more efficient. To do this, you can exploit various aspects of class to optimize the system, such as multistage filter implementation, filter design, and polyphase implementation. By the end of the project, you hopefully will have a much better understanding of both the theoretical aspect of the system as well as various issues in implementing a practical DSP system at a software level. Project Goal A sampling rate converter which produces an output signal with a sampling rate which is M L times the original sampling rate can be specified as shown in Figure 1. Figure 1: Sampling rate conversion system. For an ideal sampling rate converter, the lowpass filter in Figure 1 is an ideal lowpass filter with cutoff frequency ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ = LM c ππ ω ,min The goal of this project is to design an efficient DSP algorithm that implements the system in Figure 1 subject to the following constraints: • The system performs the correct sampling rate conversion from 11,025 Hz to 24,000 Hz. In particular, do not assume that 11,025 Hz ≈ 11,000 Hz. x[ ] n y n[ ] Lowpass filter ↑ L ↓ M f1997 If the system in Figure 1 is an ideal sampling rate converter , when the input x[n] is a unit impulse δ n],[ the output y[n] has a Fourier transform ( ) jω eY which corresponds to an ideal lowpass filter with a cutoff frequency at ωc = (11,025/ 24,000)π. For an equivalent system which you are to implement, when the input x[n] is a unit impulseδ n][ , the output y[n] must have a Fourier transform ( ) jω eY which is an approximation of a lowpass filter, and meets the specifications shown below in Table 1. Passband Cutoff (ωp) 000,24 025,11 π Passband Ripple ±0.1 dB or less Stopband Frequency (ωs) 1.2ωp Stopband Attenuation 70 dB or more Phase Constraints |max grpdelay ‐ min grpdelay| ≤ 720 in the passband Table 1 If your sampling rate conversion system functions properly, you should meet the specifications in Table 1, and when you play the output audio signal at 24,000 Hz, it should sound the same as the input audio signal played at 11,025 Hz. You should get a rough estimate of the efficiency of your design by determining how much computation was required to perform the sampling rate conversion on the Wagner.wav signal. The method which you will use to count the number of operations will be described shortly. You are to write a MATLAB function srconvert such that the command srconvert(in) takes the input signal in with an associated sampling rate of 11,025 Hz, and returns an output signal at a sampling rate of 24,000 Hz. (See the section on writing MATLAB functions.) Once your function srconvert.m is finalized, run the command y=srconvert([1 zeros(1,3000)]);. This will produce a vector y which contains the response of your system to a unit impulse. Then call verify(y) to verify that your design meets the design specification. The Files The project zip file contains the audio files and MATLAB functions which you will need for this project. To access the zip file, click on the link below where you found this file on the web site. In testing your system, you may find it helpful to first use a unit impulse as input to your system and then later try using real audio signals as inputs and listening to the outputs. To load a sound file into a vector x, type x=wavread(′filename.wav′);. To write a sound file for the MATLAB vector x into the current directory, type wavwrite(x,sampfreq, ′filename.wav′). You may test your system using any of the audio signals, although you should use the Wagner.wav signal to benchmark your system performance. f1997 MATLAB Utilities You may find the following MATLAB functions useful for your design. examlpf(h, wp, vs) ‐ allows you to examine the passband ripple, the group delay, as well as the stopband attenuation of the lowpass filter whose impulse response is h. It generates three simultaneous plots. The first one zooms in on the passband with cutoff frequency wp. The second plot measures the group delay in the passband, and the third plot is simply the magnitude response over the entire frequency range (-π,π). The passband (wp) and stopband (ws) cutoff frequencies are normalized by π/2. That is, a cutoff frequency at π/2 should be entered as 0.5. poly1(h, M) ‐ returns a matrix E whose i th row corresponds to the i th polyphase components of the FIR filter h, obtained via type I decomposition with downsampling factor M. fftfilt(h , x) ‐ convolves the signal x with the filter h using the FFTs. Beware that this command might not always leads to a more efficient implementation than conv(h ,x), depending on the length of the signals. upsample(h ,L) ‐ returns an upsampled version of h by a factor L, without any interpolation. downsample(h ,M) ‐ downsamples h by M. Computation Counts MATLAB does not automatically record the number of floating point operations (flops) in your algorithm, so to measure your computational efficiency, you’ll have to determine the required number of multiplies and adds yourself. You can make this process somewhat automated by inserting a counter to be updated each time the filter function is called, but you should also do a hand calculation to double check. Do not include in the flops count the computation involved in designing any filters you need. Example MATLAB Function To give you an example of how to write a MATLAB function, here is the code from the file poly1.m. function E=poly1(h,M) % % Performs type I polyphase decomposition of h in M components. % The ith row of E corresponds to the ith polyphase component. % Assumes that the first point of h is index 0. % h = [h zeros(1, ceil(length(h)/M)*M-length(h))]; E = reshape(h, M, length(h)/M); f1997 Tips The old homework problem in the Appendix might be useful as a guideline to efficient implementation of an interpolation filter. You may also find useful page 85 of the Vaidyanathan paper cited below. P. P. Vaidyanathan, “Multirate digital filters, filter banks, polyphase networks, and applications: A tutorial,” Proceedings of the IEEE, vol. 78, pp. 56‐92, Jan. 1990. https://www.systems.caltech.edu/dsp/ppv/papers/ProcIEEEmultirateTUTExtra.pdf (Available 7/08) Appendix – An Old Homework Problem: x[ ] n ( ) c Let represent a signal which is obtained by sampling a continuous time audio signal x t / 44.1 kHz T using an ideal C/D converter shown in Figure A1. Assume that the sampling rate is 1 = . Figure A1 We wish to design a 4x (4 times) oversampling digital FIR interpolation filter. One way to do this is to use the single‐stage design of System 1 shown in Figure A2. Figure A2: System 1 The filter h n[ ] with Fourier transform )( j H e ω is designed using the window method with a Kaiser window. Suppose the filter h n[ ] is designed to meet Specification 1: Specification 1: 1 1 ( )1 , j j H e ω ω 2 H e( ) , δ δ ωω δ ω ω π − ≤ ≤+ ≤ ≤ ≤ ≤ where 1 ω = 0.23π 2 , ω = 0.27π 4 , and δ 10− = h n[ ] . (a) Using a Kaiser window, estimate the length of the filter which meets Specification 1. (b) Using the filter length estimate for in part(a), estimate the number of multiplications per second required in System 1 if the system is implemented in polyphase form using four polyphase components. h n[ ] An alternate way to design the 4x oversampling interpolation filter is to use the two‐stage design of System 2 shown in Figure A3. x[ ] n ↑ 4 1 y n[ ] h n[ ] ( ) x[ ] n c x t C/D T f1997 Stage 1 Stage 2 2 y n[ ] f1997 ) Figure A3: System 2 The filters and with frequency responses 1 h n[ ] 2 h n[ ] 1( j H e ω and 2 ( j H e ) ω , respectively, are designed using the window method with Kaiser windows. Suppose that these filters are designed to meet Specification 2. Specification 2: 1 1 1 2 1 2 1 2 1 1 ( )1 , 2 () , 2 ( )1 , () , j j j H e H e H e H e ω ω ω δ δω jω ω δ ω ωπ δ δω ω δ πω ω π ′ ′ ≤ ≤+ ≤ ≤ ≤ ′ ′ ′ ≤ ≤+ ≤ ≤ −≤ ′ − ≤ ≤ − where δ δ ′ = +− 1 1,ω1 , ω2 , and δ are given previously. (c) Show that System 2 is equivalent to System 1 with 1 2 He H e H e ( ) ) ()( j jj ω ω ω h n[ ] j = 2 (d) Show that if the filters and h [ ] n are designed using Kaiser windows to meet Specification 2, then the resulting equivalent system in System 1 will have a filter 1 H e )( ω which meets Specification 1. (You may assume that the filters designed have magnitude responses which are monotonically decreasing in the transition band from the passband to the stopband). (e) Using Kaiser windows, estimate the lengths of the filters and h which meet Specification 2. 1 h n[ ] [ ] n h n[ ] h n[ ] 2 (f) Using the filter length estimates for and in part (e), estimate the number of multiplications per second required in System 2 if each stage is separately implemented in polyphase form using two polyphase components. What are the computational savings in multiplications, if any, over System 1? 1 2 x[ ] n ↑ 2 1 h n[ ] 2 ↑ 2 h n[ ]One area in which discrete-time signal processing has enjoyed widespread use is in the field of speech processing. In this project we consider various issues relating to applying digital filtering to speech. Specifically, in this project, we consider the effect of all-pass filtering on speech.Historically, DSP courses have put considerable emphasis on design techniques for both IIR and FIR filters, as discussed in Chapter 7 of the course text. A variety of filter design algorithms are now implemented in common software packages such as fdatool in Matlab. This makes it unnecessary for most practitioners to learn the details of the design algorithms; however, ceding the design function to a software package makes it more important to understand the properties of different types of optimal filters, the meanings of the design parameters, and some of the trade-offs between filter classes.In the context of IIR filter design, we suggest that you read Sections 7.0 and 7.1 including Example 7.1.Project AssignmentYour writeup should have a summary of how you went about this project (anywhere from one to five pages, not to exceed five pages). In addition to the five page maximum, you can include any appropriate Matlab plots. Do NOT turn in any Matlab code. The total number of pages including description and plots should not exceed ten pages.The writeup will receive a grade which reflects our assessment of your level of understanding of the various issues involved and the effort that you put into it.Throughout this project it will be necessary to play audio files which you will have manipulated in Matlab. The functions sound and soundsc (sound scaled) work well for doing this on most hardware platforms.A common “folk theorem” states that the ear is insensitive to phase, i.e. that for audio, phase distortion is inaudible. If that is correct, then processing audio with an all-pass filter should not result in perceived distortion. This project tests this conjecture. The all-pass filter that we consider is of the form.For this part of the project, the file projIA.mat will need to be first loaded into Matlab. To access the project zip file, click on the link below where you found this file on the web site. After downloading the zip file, copy its contents into your Matlab working directory and type load projIA. The bk and ak coefficients above are stored in the variables b and a respectively; b(k + 1)= bk and a(k + 1)= ak.One area in which discrete-time signal processing has enjoyed widespread use is in the field of speech processing. In this project, we consider IIR and FIR filter design in the context of enhancing speech corrupted by additive noise. While this relies somewhat on material Chapters 6 and 7, some aspects can be started earlier.This project is an excellent introduction to the issues discussed in Hardware Implementation Considerations for Removing Noise.Historically, DSP courses have put considerable emphasis on design techniques for both IIR and FIR filters, as discussed in Chapter 7 of the course text. A variety of filter design algorithms are now implemented in common software packages such as Matlab. This makes it unnecessary for most practitioners to learn the details of the design algorithms; however, ceding the design function to a software package makes it more important to understand the properties of different types of optimal filters, the meanings of the design parameters, and some of the trade-offs between filter classes.In the context of IIR filter design, we suggest that you read Sections 7.0 and 7.1 including Example 7.1. Also, read the examples in Section 7.3.1, but focus on what Butterworth and Chebyshev filters are rather than on the details of the bilinear transformation. For the discussion of FIR filter design, the suggested reading is Sections 7.5, 7.6, and 7.7 through 7.7.1. We will not be going into the details of the issues raised in Section 7.7.1, but we would recommend at least reading that section to get a sense of what some of those issues are.Project AssignmentYour writeup should have a summary of how you went about it (anywhere from one to five pages, not to exceed five pages). In addition to the five page maximum, you can include any appropriate Matlab plots. Do NOT turn in any Matlab code. The total number of pages including description and plots A should not exceed 10 pages.The writeup will receive a grade which reflects our assessment of your level of understanding of the various issues involved and the effort that you put into it.Throughout these projects it will be necessary to play audio files which you will have manipulated in Matlab. The functions sound and soundsc work well for doing this on most hardware platforms.For this project, the file projIB.mat will need to be first loaded into Matlab. To access the project zip file, click on the link below where you found this file on the web site. After downloading the zip file, copy its contents into your Matlab working directory and type load projIB.In this part of the project, it may be helpful to use Matlab’s order estimation functions (e.g. buttord, cheb1ord, …). A caveat in the use of these functions is that Matlab’s definition of ‘ripple’ differs between the IIR and FIR filter design functions. Do the Matlab Ripple project before proceeding with this project.This project is concerned with designing a low-pass filter for the removal of high-pass noise from a speech signal. The noisy signal is stored in the variable noisy and was sampled at 44100 (fs) Hz. It consists of a summation of a speech signal which was band-limited at 4 kHz using a low-pass filter with a very narrow transition band, and a noise signal which was filtered at 4 kHz using a high-pass filter with a very narrow transition band. To filter the noise we must design a discrete-time filter with the following parameters:Because it may take a few iterations to get each filter right, we suggest you write a .m Matlab script for each filter.Note that in this part of the project, you may end up with very high order filters since the specifications are rather severe. You can try to implement the IIR filters according to the specs using Matlab’s built in tools (such as the fdatool or the command line tools butter, cheby1, cheby2, and ellip—type “help signal” for more information). If you do so, you will notice that the resulting systems might not be stable. There are several reasons for this, the most important of which being coefficient quantization—even with floating point precision. This issue arises because the specifications are very tight and some of the filter types have all of their poles concentrated near z = 1.Fortunately, there is a workaround. What you need to do is to group the poles and zeros for the desired filter in pairs (conjugate or not) to create smaller stable second order filters of the form N(z)/D(z) where N(z) and D(z) are at most second order polynomials in z. A cascade of such filters will produce the desired system, and Matlab will be able to analyze it. The drawback is that you will have to implement your own methods to generate the plots and simulate the system.Design a DT filter of each of the following types based on the specifications given above:Butterworth, Chebyshev Type I, Chebyshev Type II, Elliptic, Parks-McClellan, Kaiser.For each of the designs,Filter noisy using your de-noising filter. Listen to the filtered and original files. How do they compare?The frequency characteristics of nonstationary signals vary as a function of time. This requires Fourier analysis of these signals to be localized and time-dependent, resulting in analysis methods known as time-frequency distributions. One elementary time-frequency distribution based on the FFT is the short-time Fourier Transform (STFT). The STFT applied to speech is often called a speech spectrogram. Spectrograms are well suited to analyze speech signals with their time-varying narrowband features.In this project, you will:The project zip file contains the audio files and MATLAB functions which you will need for this project. To access the zip file, click on the link below where you found this file on the web site.The spectrogram of a signal x[n] is defined as:where w[n] is the window used. The window will determine what portion of the signal is used for analysis and controls the frequency resolution of the spectrogram. The parameter n denotes the reference position of the window on the signal. Let the window be of length Nwin and nonzero only in the interval 0 ≤ k ≤ (Nwin – 1). The above equation reduces to:It is easy to construct spectrograms in Matlab since the STFT involves only windowing and the FFT. This project will require extensive use of the Matlab function spectrogram. It is suggested you take some time to fully understand the details of the spectrogram function. This can be done by typing help spectrogram at the Matlab prompt. For a more graphical presentation of the help (including figures) try doc spectrogram. A few important points about the spectrogram function for this project:The MATLAB function diary may be helpful to keep track of commands when you are experimenting. Create separate M-file(s) to be able to rerun and test parts of your code. Do not turn in a log of all the commands you tried, just the source code that was relevant to solve the different parts of the project. In addition to this source code, please turn in the required plots, keeping in mind that you are expected to generate reasonable graphics.Generate a discrete-time linear FM chirp signal x[n] using a sampling frequency of 5 MHz and letting the chirp rate be m = 4.0 X 109. Assume that the continuous-time chirp lasts 200 ms. Generate a spectrogram for this signal Xn(w) using 256-point FFT’s, a 256-point triangular window and an overlap of 255 samples between sections. (The MATLAB function triang can be used to construct the triangular window.)The window used to compute the STFT determines the frequency resolution of the analysis. In this section, you will examine the effect of the window on the spectrogram of a voiced speech signal. You will need two speech files in the project zip file: s1.mat and s5.mat. Load in these files by typing load sl and load s5 at the Matlab prompt. Assume these speech signals are sampled at 8 kHz. If you wish to listen to these files, the Matlab function soundsc can be used to autoscale and play signals.The exercises below depend on the frequency structure of human speech. Voiced human speech is produced by buzzing from the vocal cords (glottal excitation) into the resonant frequencies (formants) of the vocal tract. At high frequency resolution, we can see the individual harmonics of the glottal excitation signal at multiples of its pitch frequency. At low frequency resolution, the individual harmonics are blurred, but the emphasis applied by the vocal tract resonances is more obvious in the wide peaks. As the lips, teeth and tongue change the shape of the vocal tract, the resonant frequencies (formants) change the sound to correspond to various recognizable vowel sounds. Thus, the specific formant frequencies determine the vowel sound perceived by the listener.There are different methods to estimate a signal from a modified STFT. In this section, you will estimate the signal by determining the signal y[n] which produces the smallest error for the following criterion:Write a Matlab function to implement this estimation from a modified STFT. To simplify the programming, assume that the STFT that you are processing was created with 1024-point FFT’s and a 256-point rectangular window with segments overlapping by 128 points.One way to approach this problem is to look at how a STFT is constructed with the parameters above. The first column of the STFT is constructed by taking the first segment of the signal in time and computing its FFT. In this case, that would be the 1024 point FFT of the first 256 points zero-padded to length 1024. The second column of the STFT is constructed by taking the next segment of the signal in time and computing its FFT. Since the segments overlap by 128 points, this would mean the 256 points from 128 to 383 are zero-padded to length 1024, and the 1024 point FFT is computed.Now, if we want to estimate the signal from a modified STFT, we reverse the concepts above. Using the first column of the modified STFT, we can take an IFFT and the first 256 points should correspond to the time signal from 0 to 255. The IFFT of the second column of the modified STFT can be computed and the first 256 points will correspond to the time signal from 128 to 383. And we can repeat this for the remaining columns. Note that there are now two estimates of the time signal from 128 to 255 since the IFFT’s of the first two columns overlap in time. Because of the error criterion we are using (and the rectangular windows), we can just take the average of the estimates at each point. If we continue doing this, note that except for 128 points at the beginning and the end of y[n], there are two estimates at every point in time. This illustrates the redundant information in the STFT.The only input variable to this function, besides the modified STFT, will be the number of samples of the spectrogram (note: this could also be determined from the modified spectrogram itself). Also assume that the output signal y[n] will be real and that modifications to the STFT are made in a manner such that IDFT of each slice of Xn(k) will also be real. Even if conjugate symmetry is satisfied, taking the inverse DFT with the Matlab function ifft may result in a nonzero imaginary component due to precision error. In this case, take the real part of the ifft result to eliminate the precision error. Also, note that the MATLAB function spectrogram will only compute Xn[k] for 0 ≤ k ≤ 512 since the original sequence was real, so you will have to reconstruct Xn[k] for 513 ≤ k ≤ 1024 to be able to compute a 1024-point inverse DFT.Test this function by using the unmodified spectrogram of the speech signal in vowels.mat as an input to your program and comparing the output to the original signal. Plot the difference between the input and output.First, load in the speech signal from vowels.mat and compute the spectrogram using a 256-point rectangular window with an overlap of 128 points per section, 1024-point FFT’s, and assuming a sampling rate of 8 kHz. Then compress the time scale by a factor of 2 by throwing out every other slice in time, and use the function from the previous section to obtain a faster speech signal with the same frequency content. Plot the speech signal before and after time scale modification. Listen to the signals to verify that your processing is working correctly.In this project you will explore and compare various parametric and non-parametric techniques for power density spectrum (PDS) estimation. The goal is to approximate the PDS with non-parametric direct methods, such as the periodogram, periodogram averaging, and the non-parametric indirect Blackman-Tukey method. You will also investigate parametric all-pole modeling for PDS estimation. In the process, you will have a chance to sort through many issues involving finite length signals and the DFT.Suggested Reading: Sections 10.6, 10.7, and 11.0 to 11.5.You are given a signal that is the result of passing white Gaussian noise with variance one ( ) through a system . Figure 1: GeneratingThe goal is to estimate the PDS of , . Recall that:Thus estimating is equivalent to estimating . Your goal is to construct estimates of from the samples of the colored noise .The data for this project is contained in the file pj2data.mat.Copy this file into the local directory where you are working. This file contains two vectors. The vector y is a 512-point vector representing the discrete time signal . The vector Hejw2 is a 512-point DFT representing samples of the magnitude-squared response . It is the desired response that you are trying to estimate from . Hejw2 is given to you as a baseline for error calculation.You can load the data into your MATLAB environment using the load command. Just cd to the directory where you copied pj2data.mat and at the prompt type:load pj2dataYour MATLAB environment will now have two vectors y and Hejw2 defined in it. Warning! If you had other variables named y and Hejw2 they will be overwritten by the load command.Figure 2: Plots of the data in pj2data.matAs a first exercise you may want to plot the data y and Hejw2. They are plotted above for your convenience. Note that the k-indices on Hejw2 represent sampled values in the interval (i.e. ).In this project you are using the data to construct estimates of , where .Error Criterion: The error criterion is defined as the discrete-squared-error in the frequency domain. An expression for the estimation error is given in (1): Autocorrelation Estimate: The autocorrelation function of a wide-sense stationary signal $y[n]$ is defined as: In this project, the autocorrelation estimate provided by the observed data of length is: Project Write-UpThis project contains several problems, each of which address some aspect of spectral analysis. The write-up should include a summary of how you went about the project, any relevant plots and, at minimum, address all the questions asked in each of the problems. The total, including your description and plots, should not exceed 14 pages (i.e., 14 sides).In addition, this project will be graded not only on content and correctness, but also on neatness and style of presentation. Thus, although not a requirement, it is recommended that you typeset this report using Latex, Microsoft Word, or some other typesetting program.You can save your figures off the figure window in MATLAB by clicking export and saving as .eps, .bmp, .tiff, etc. If embedding images into MSWord, be warned that JPEG quality is low. Bitmaps or TIFFs might be better than JPEGs.Functions you may find useful in this project include fft(), fftshift(), fliplr(), conv(), downsample(), xcorr(), toeplitz(), levinson(), freqz(), sum(), abs(), transpose(), ones(), zeros(), triang(). Look at the appropriate help files in MATLAB to see how to use them.The function xcorr() in MATLAB calculates the finite autocorrelation between two sequences. Calculate the following sequence= xcorr(y, y, ‘biased’)This is similar to the convolution of two finite sequences and . For the first part of this exercise, show this fact using the following example:The two plots you get should be the same, except for a scaling factor.What does xcorr calculate if you replace ‘biased’ with ‘unbiased’? where is the length of . Explain why the Fourier transform of this autocorrelation function is a positive, real function.The PDS is the Fourier transform of the autocorrelation function defined in . The Fourier transform of is an estimate of the PDS, which is the 64-point periodogram of using a rectangular window. The periodogram can be calculated directly from without first convolving it with itself: Take a 64-point DFT of and then find its magnitude squared. This will give you a 64-point DFT representing .For the last part of this exercise, plot three figures:What is the relationship between the three signals in A.3.a, A.3.b and A.3.c ?Estimate the PDS of using only the first 32-points of the data. Do this by taking the 64-point periodogram. Plot the 64 DFT points of the desired frequency response, , and your estimate of the PDS at on the same plot. Calculate the estimation error as given in .Estimate the PDS using all 512 points. Do this by taking the 1024-point periodogram of . Similar to Problem B.1, plot the 64 DFT points of the desired frequency response, , and your estimate of the PDS at those frequencies on the same plot. Calculate the estimation error as given in .Estimate the PDS using periodogram averaging. Write a script to find the 64-point periodogram of every 32 non-overlapping samples and average the results (i.e. there will be 512/32 = 16 periodograms to average). The expression for the periodogram averaging is:Similar to Problem B.1, plot the 64 DFT points of the desired frequency response and your estimate on the same plot. Comment on any differences between this estimate and the previous two. Calculate the estimation error as given in .In this problem you will use the indirect Blackman-Tukey method to estimate the PDS of . The Blackman-Tukey method requires you to first estimate the autocorrelation of . Use the following three steps to generate your Blackman-Tukey estimate:Similar to Problem B.1, plot 64 DFT points of the desired frequency response and your estimate on the same plot. Calculate the estimation error as given in .Format the errors you found in Problems B.1-B.4 in a table and discuss your results.Estimate the PDS of using all-pole modeling. Here the stable impulse response in Figure 1 is modeled with a class of stable filters with the following structure .The goal is to fit an all-pole model to the data and use that model to estimate .Formulate the Yule-Walker equations for 2nd through 7th order all-pole models, and solve for the coefficients to estimate . Use the values of as estimated in Problem B.4. In a table, list the coefficients and the prediction error you found for . For which order is the prediction error minimum? (hint: check out the levinson command in MATLAB)Draw the lattice implementation for .In addition to finding the denominator coefficients, you must also find the gain factor . In the Yule-Walker estimation method, the minimum mean-squared value for in the th-order predictor is given byPlot the estimation error as defined in as a function of . You may find the command freqz() helpful. Comment on any interesting features of this error curve. What does this imply about the system function ? What is your best estimate of the number of poles in ? Compare the prediction error to the estimation error. Show how this equation is obtained. Use and find the estimation error in . Compare s with the estimates s in Problem C.2. Explain how this estimator is obtained. Repeat C.3.a for this estimator.MATLAB contains functions calledView the help files for these functions and explore their use in the context of Problems B.1, B.2, B.3 and C. Show how these commands can provide the same results which you obtained for these relevant problems . Do not use these functions to find answers in the previous problems in the project.
5/5 - (1 vote) Let us assume a two-class classification problem where each class is modeled by a 2D Gaussian distribution G(μ1, Σ1) and G(μ2, Σ2). 1. Generate 100,000 samples from each 2D Gaussian distribution (i.e., 200,000 samples total) using the following parameters (i.e., each sample (x,y) can be thought as a feature vector): 1 1 1 1 1 0 0 1 2 4 4 2 1 0 0 1 Notation: x y 2 2 0 0 x y Note: this is not the same as sampling the 2D Gaussian functions; see “Generating Gaussian Random Numbers“on the course’s webpage for more information on how to generate the samples using the Box-Muller transformation. A link to C code has been provided on the webpage. Since the code generates samples for 1D distributions, you would need to call the function twice to get a 2D sample (x, y); use (μx, σx) for the x sample and (μy, σy) for the y sample. Note: ranf() is not defined in the standard library and that you would need to implement it yourself using rand(); for example: /* ranf – return a random double in the [0,m] range.*/ double ranf(double m) { return (m*rand())/(double)RAND_MAX; } (m=1 in our case) a. Assuming P(ω1) = P(ω2) i. Design a Bayes classifier for minimum error. ii. Plot the Bayes decision boundary together with the generated samples to better visualize and interpret the classification results. iii. Report (i) the number of misclassified samples for each class separately and (ii) the total number of misclassified samples. iv. Plot the Chernoff bound as a function of β and find the optimum β for the minimum. v. Calculate the Bhattacharyya bound. Is it close to the experimental error? b. Repeat part (a) for P(ω1) = 0.2 and P(ω2) = 0.8. For comparison purposes, use exactly the same 200,000 samples from (a) in these experiments. 2. Repeat parts (1.a) and (1.b) using the following parameters (i.e., you need to generate new sample sets): 1 1 1 1 1 0 0 1 2 4 4 2 4 0 0 8 3. Repeat part (2.b) (i.e., P(ω1) ≠ P(ω2)) using the minimum-distance classifier and compare your results (i.e., misclassified samples) with those obtained in part (2.b). For comparison purposes, use exactly the same 200,000 samples as in part 2. 5/5 - (1 vote) 1. In the previous assignment, you designed a Bayes classifier assuming the following 2D Gaussian distributions: 1 1 1 1 1 0 0 1 2 4 4 2 1 0 0 1 In this assignment, you will assume that you do not know the true parameters of the Gaussian distributions and that you need to estimate them from the training data using the Maximum Likelihood (ML) approach. a. Using the same 200,000 samples from the previous assignment, estimate the parameters of each distribution using ML. Then, classify all 200,000 samples assuming P (ω1) = P (ω2); count the number of misclassified samples and compare your results to those obtained in assignment 1. b. Repeat experiment (1.a) using 1/100 of the samples from each distribution (randomly selected) to estimate the parameters of that distribution using ML. Then, classify all 200,000 samples assuming P (ω1) = P (ω2); count the number of misclassified samples and compare your results to those obtained in experiment (1.a). 2. Repeat problem 1 using the samples (same as in Assignment 1) from the following 2D Gaussian distributions: 1 1 1 1 1 0 0 1 2 4 4 2 4 0 0 8 3. Face detection using skin color is a popular approach. While color images are typically in RGB format, most techniques transform RGB to a different color space (e.g., chromatic, HSV, etc.). This is because RGB values are more sensitive to changes of brightness due to illumination changes. a. Implement the skin-color methodology of [Yang96 “A Real-time Face Tracker”] which uses the chromatic color space. To build the skin color model, use Training_1.ppm (and ref1.ppm), shown in Figure 1, which are available from the course’s webpage. To test your method, use Training_3.ppm (and ref3.ppm) and Training_6.ppm (and ref6.ppm), which are also available from the course’s webpage. To quantitatively evaluate the performance of your method, generate ROC plots (i.e., false positives (FP) vs false negatives (FN)) by varying the skincolor threshold. A FP would be a non-face pixel which was classified as skincolor while a FN would be a face pixel which was classified as non-skin color. To compute the FPs and FNs for each test image, use the corresponding reference images. b. Repeat (3.a) using the YCbCr color space In the YCbCr color space, the luminance information is contained in Y component; and, the chrominance information is in Cb and Cr. Therefore, Y should not be used in the skin color model. The RGB components can be converted to the YCbCr components using the following transformation: Y = 0.299R + 0.587G + 0.114B Cb = -0.169R – 0.332G + 0.500B Cr = 0.500R – 0.419G – 0.081BFigure 1. Training_1.ppm and ref1.ppm images. For comparison purposes, plot the ROC curves in the same graph. Note: Irfanview is a nice tool for image display/manipulation. Sample code to read/write color images in PPM format can be found in my CS 302 webpage: https://www.cse.unr.edu/~bebis/CS302/ Information on the PPM image file format can be found here: https://paulbourke.net/dataformats/ppm/ https://www.cse.unr.edu/~bebis/CS302/Lectures/IP.ppt 5/5 - (1 vote) In this project, you will implement the eigenface approach [2] and perform experiments to evaluate its performance and the effect of several factors on recognition performance. 1. Eigenface implementation Read carefully and understand the steps of the eigenface approach. Use jacobi.c from “Numerical Recipes in C” for computing the eigenvalues/eigenvectors of a symmetric matrix (Warning: the [0] location of an array is NOT used in “Numerical Recipes”; start storing your data at location [1]). Your program should run in two modes: training and testing. Training: In training mode, your program will read in the training face images and compute the average face and eigenfaces. It will then project each training face image onto the eigenspace and compute its representation in that space (i.e., the coefficients of projection Ωk , k=1,2,..,M, where M is the number of training face images). Finally, your program will store into a file the coefficients Ωk , the average face, and the eigenfaces. Testing: In testing mode, your program will read in the coefficients Ωk , the average face, and the eigenfaces. Then, it will decide how many eigenfaces to keep (i.e., this could be done in an interactive mode where the user determines the percentage of the information to be preserved). Use the images in a test set (see below) to evaluate face recognition performance. Given a test image, your program will need to project it onto the eigenspace and compute its projection coefficients Ω. To recognize the face in the test image, you will need to find the closet match Ωk to Ω (i.e., distance in face space (difs)). Let’s call ek = ||Ωk − Ω|| where the distance is computed using the Mahalanobis distance. Very important: to make sure that your program works correctly, try the following: given an image I, (i) project it onto the eigen-space, (ii) reconstruct it using all eigenfaces; let’s call the reconstructed image ˆ I , (iii) compute ||I – ˆ I || (i.e., distance from face space (dffs) using Euclidean distance). The difference should be very small; if it is not, then your code is not working correctly. Do not proceed unless you have been able to verify this step. 2. Datasets To test eigenface recognition, you will use images from the FERET face database [1]. FERET contains a large number of images acquired during different photo sessions and has a good variety of gender, ethnicity and age groups. The lighting conditions, face orientation and time of capture vary. In this project, you will concentrate on frontal face poses named as fa (frontal image) or fb (alternative frontal image, taken during a different photo session). All faces have been normalized with regards to orientation, position, and size. Also, they have been masked to include only the face region (i.e., upper body and background were cropped out). The first subset (fa) contains 1204 images from 867 subjects while the second subset (fb) contains 1196 images from the 866 subjects (i.e., there is one subject in fa who is not in fb). You have been provided with two different sizes for each image: low resolution (16 x 20) and high resolution (48 x 60). All datasets can be downloaded from the course’s webpage: FA_L (fa, low resolution), FA_H (fa, high resolution) FB_L (fb, low resolution), FB_H (fb, high resolution) The file naming convention for the FERET database is as follows: nnnnn_yymmdd_xx_q.pgm where nnnnn is a five digit integer that uniquely identifies the subject, yymmdd indicates the year, month, and date when the photo was taken, xx is a lowercase character string (i.e., either fa or fb), and q is a flag (e.g., indicating whether the subject wears glasses – not always present). 3. Experiments (a) Use fa_H for training (i.e., to compute the eigenfaces and build the gallery set) and fb_H for testing. So, there will be 1203 images for training and 1196 images for testing (query). (a.I) Show (as images) the following: o The average face o The eigenfaces corresponding to the 10 largest eigenvalues. o The eigenfaces corresponding to the 10 smallest eigenvalues. (a.II) Choose the top eigenvectors (eigenfaces) preserving 80% of the information in the data as the basis. Project both training and query images onto this basis after subtracting the average face to obtain the eigen-coefficients. Then, compute the Mahalanobis distance between the eigen-coefficient vectors for each pair of training and query images as the matching distance. Please note that for each query image, there will be 1203 matching distances (i.e., obtained by matching the query with each image in the gallery dataset).Choose the top N face gallery images (i.e., N is a parameter, see below) having the highest similarity score with the query face. (i.e., N smallest matching distances). If the query image is among the N most similar faces retrieved, then it is considered as a correct match, otherwise; it is considered as an incorrect match. Count the number of correct matches and divide it by the total number of images in the test set (e.g., 1196) to report the identification accuracy. Draw the Cumulative Match Characteristic (CMC) curve [1] by varying N from 1 to 50. CMC shows the probability of the query being among the top N faces retrieved from the gallery. The faster the CMC curve approaches the value one, the better the matching algorithm is (see graph below). (Part a.III) Assuming N=1, show 3 query images which are correctly matched, along with the corresponding best matched training samples. (Part a.IV) Assuming N=1, show 3 query images which are incorrectly matched, along with the corresponding mismatched training samples. (Part a.V) Repeat (a.II – a.IV) by keeping the top eigenvectors corresponding to 90% and 95% of the information in the data. Plot the CMC curves on the same graph for comparison purposes. If there are significant differences in terms of identification accuracy in (a.II) and (a.V), try to explain why. If there are no significant differences, explain why too. (b) In this experiment, you will test the performance of the eigenface approach on faces not in the gallery set (i.e., intruders). For this, remove all the images of the first 50 subjects from fa_H; let’s call the reduced set as fa2_H. Perform recognition using fa2_H for training (gallery) and fb_H for testing (query). In this experiment, use the eigenvectors corresponding to 95% of the information in the data. To reject intruders, you would need to threshold ek (i.e., accept the match only of ek < T). In this case, the choice of the threshold T is very important. A high threshold value will increase False Positives (FP) while a low threshold value will decrease the number of True Positives (TP). To find out what is a good threshold value, you would need to vary the value of T and compute (FP, TP) for each value. Then, you would need to plot the (FP, TP) values in a graph (i.e., ROC graph; see below). 0.7 0 1 1 false positive rate true positive rate # true positives # non-intruders (positives) 0.1 # false positives # intruders (negatives) Graduate Students Only – Experiments using low-resolution face images. (c) Repeat experiment (a) using fa_L for training (gallery) and fb_L for testing. (d) Remove all the images of the first 50 subjects from fa_L; let’s call the reduced set as fa2_L. Repeat experiment (b) using fa2_L for training (gallery) and fb_L for testing. (e) What is the effect of using low-resolution images? Are there any significant differences in identification performance? Explain. References [1] Phillips, J. and Moon, H. and Risvi, S. and Rauss, J., “The FERET Evaluation Methodology for Face Recognition Algorithms”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 10, pp. 1090-1104, 2000. [2] M. Turk and A. Pentland, Face Recognition Using Eigenfaces, Computer Vision and Pattern Recognition Conference, 1991.In this assignment, you will experiment with two different classifiers for gender classification: SVMs and Bayesian classifier.Data Set and experiments: The dataset to be used in your experiments contains 400 frontal images from 400 distinct people, representing different races, with different facial expressions, and under different lighting conditions. The 400 images have been equally divided between males and females. Histogram equalization has been applied to each normalized image to account for different lighting conditions.The data, which is available from the course’s webpage, contains images of two different sizes: 16×20 and 48×60; you would need to experiment with each image size separately and compare your results. For each classifier, you need to report the average error rate using a three-fold cross-validation procedure. For this, we have randomly divided the dataset three times as follows: Fold 1: Training (69M, 65F), Validation (73M, 60F), Test (58M, 75F) Fold 2: Training (62M, 72F), Validation (58M, 75F), Test (80M, 53F) Fold 3: Training (71M, 63F), Validation (67M, 66F), Test (62M, 71F) Note that the validation set is typically used for parameter optimization. Since you will not need to optimize any parameters in this assignment, use both the validation set and test set for testing purposes by simply combining them into one set. Using each fold, compute the test error and then average all three errors to report the average error.For each image, we have pre-computed its eigen-face representation; you should be training/testing each classifier using the first 30 eigen-features only (i.e., the ones corresponding to the top 30 eigenvectors). The file naming convention for each file is as follows: trPCA_xx for training, valPCA_xx for validation, and tsPCA_xx for testing; see “descr” file for more information. Note that the eigenvalues and eigenvectors have been provided in the files EVs_xx and PCs_xx for completeness, however, you will not need them in your experiments.Experiment 1: Apply Support Vector Machines (SVMs) for gender classification. You will be using the LibSVM implementation. Experiment both with polynomial and RBF kernels as well as different C values. For consistency, try d=1, 2, and 3 for the polynomial kernel (note that LibSVM provides two extra parameters for the polynomial kernel; to be consistent with the lecture, set γ=1 and c0=0). In the case of the RBF kernel, try σ=1, 10, and 100. For the C value, try C=1, 10, 100, and 1,000. Report your best results both for the 16×20 and 48×60 datasets. Warning: make sure that the data is provided in the format required by LibSVM; otherwise, it will not work correctly.Experiment 2: For comparison purposes, apply the Bayes classifier for the same problem. Model the male and female classes using a Gaussian distribution and use ML estimation to estimate the parameters for each class. Use equal prior probabilities (e.g., P(ω1)= P(ω2)). Compare your results with those obtained using SVMs.1. Cover Page. The cover page should contain Project title, Project number, Course number, Student’s name, Date due, and Date handed in. 2. Technical discussion. This section should include the techniques used and the principal equations (if any) implemented. 3. Discussion of results. A discussion of results should include major findings in terms of the project objectives, and make clear reference to any figures generated. 4. Division of work: Include a statement that describes how the work was divided between the two group members. 5. Program listings. Includes listings of all programs written by the student. Standard routines and other material obtained from other sources should be acknowledged by name, but their listings should not be included. A hard copy is required for items 1-4, submitted to the instructor in the beginning of the class on the due date. Item 5 should be emailed to the instructor, as a zip file, before class on the due date.
In this assignment, you will utilize the basic skills you learned in the first week of class; you will assign values to variables, use some of MATLAB’s basic functions, and perform some simple arithmetic operations on scalars and matrices. You should also use this assignment as a way to get comfortable with the help and doc functions. For your final submission, as always, please suppress all outputs with semicolons. Separate each question into separate sections. It may be good to get into the habit of beginning your scripts with clc, clear and close all. Don’t remember what these do? Use help! 1. Create scalar variables with the following values: • log10(26) • 5e j 2π 3 • arctan(√ 15) + 34 • √ 3 2 + j 1 2 Give these variables unique and reasonable names. Using these variables (not the expressions) create a column vector with each variable as an entry. 2. You should have two complex variables from the previous question. Multiply the two together (using the variables again) and save that as a variable. Compute the real part, imaginary part, magnitude and angle of the resulting complex number and create a row vector using those values as entries. 3. Now with the two vectors from the previous questions, create and save as variables two 4×4 matrices as follows: • Regular matrix multiplication (make sure the vectors are in the right order! I want a 4×4 matrix, not a scalar, i.e. an outer product, not an inner product) • Transpose (regular transpose not conjugate transpose) the column vector and multiply it elementwise with the row vector. Then use repmat to extend this row vector to a 4×4 matrix (use help or doc if you don’t remember how to use repmat). 4. With these two matrices, perform the following operations (save the results as variables): • Add the first and two times the second • Elementwise multiply them • Subtract two from every entry in the first matrix • Conjugate transpose either one 1 ECE-210B Homework 1 5. Take the angle of the complex number in question 2 and convert it to degrees (check out rad2deg). It should be an integer. Save the value as n. Then create these two row vectors: • A length 2000 vector with equally spaced entries from 1 to n • A vector with entries starting at one up to n with entries spaced at intervals of 0.3 (the vector may turn out to not include n) You will be using both linspace and the colon operator here. Make sure to use the right one for each!In this homework, you will review some of the topics discussed in class this week, including approximating derivatives and integrals and different matrix operations. You will also see that for loops are usually not the best idea in MATLAB… 1. Here you will be approximating derivatives and integrals on the sine function. • Create two vectors with entries evenly spaced between 0 and pi. One vector should be of length 100 and the other should be of length 1000. Then apply these vectors to the function sin(2x). • Approximate the derivative of this function by taking differences of adjacent elements and dividing by the space between them. Do this for both vectors. • What function should this be? (I hope you know this…) Check this by applying the original evenly-spaced vectors to this function, taking the elementwise difference between the resulting vectors and the derivative vectors and computing the magnitudes of the max differences between them. Which length produces better results? • Now use cumsum and cumtrapz to approximate the integral of sin(2x). Do this for both lengths as before. • Subtract 0.5 from every element of each integral vector to center their graphs at 0. Then compare the computed vectors with the analytic antiderivative as before. Return the magnitude of the max error for each of the four cases. • Plot the best approximation for the integral. Add a title to the plot. 2. Perform the following matrix operations: • Use reshape to create the 10×10 matrix A = 1 11 … 91 2 12 … 92 . . . . . . . . . . . . 10 20 … 100 . • Flip A upside down. • Flip the 3rd row left to right. • Create a row vector which is the column wise sum of the entries of A. • Create a column vector which is the row wise product of the entries of A (Check out prod). • Delete the 6th row. 3. Create a 300×500 matrix B where Bij = i 3+j 3 i+j+2 . Do this, and time how long each one takes with tic toc, using three methods: • Using a for loop without preallocation. • Using a for loop with preallocation. • Using only elementwise matrix operations (meshgrid may be useful here).In this homework, you will review logical indexing in MATLAB, a very important technique used to efficiently index a matrix or vector. You will also have a chance to work with functions in a separate file. 1. Roll the Dice In this part you will work with imshow and logical indexing. • Create 100×100 matrices A, B and C of all ones. • In matrix A, set the values of the entries aij equal to zero if p (i − 25)2 + (j − 75)2 < 10 or p (i − 75)2 + (j − 25)2 < 10. (Hint: Use meshgrid to create the indices, then logical indexing on A using |, & or˜). • In matrix B, set the values of the entries bij equal to zero if p (i − 25)2 + (j − 25)2 < 10 or p (i − 75)2 + (j − 75)2 < 10. • In matrix C, set the values of the entries cij equal to zero if p (i − 50)2 + (j − 50)2 > 10. • Now use figure and imshow to plot: – The complement of C – A – The next 3 faces of a die (so 3-5) on three separate figures. Use whatever logical operations (&, |, or˜) are necessary to accomplish this. 2. Fun with find Write a function to return the value and index of a number in a vector / matrix that is closest to a desired value. The function should be called as [val, ind] = f indClosest(x, desiredV alue). This function can be accomplished in less than five lines. You will find abs, min and/or find useful, Hint: You may have some trouble using min when x is a matrix. To convert the matrix to a vector, you can use y = x(:). Show that it works by finding the value closest to 3/2 (and index of said value) in sin( linspace(0,5,100) ) + 1. 3. Calculus Nostalgia This problem will reacquaint you with the first derivative test and points of inflection. • Write a function, called signSwitch, in a separate file which inputs a vector v and outputs a vector with the indices i which represent a sign change in v; i.e. report 15 if the sign changed in v between index 14 and index 15. Do not consider going from positive or negative to zero. We could loop through and check this condition at every point – don’t do that. Instead think of a way to use logical indexing: One suggestion is to write conditions on the vector and some kind of shifted version of itself. Beware however, when you do this you will have non-overlapping points. It is up to you to figure out what to with them. This will be a local function (see the documentation if you forgot what this means). • Now we will write the main function, call it whatever you’d like, which will perform all the analysis. The function will input two vectors representing the x and y coordinates of the graph of the function and will return a vector with the approximate indices of the local extrema and a vector with the approximate indices of the points of inflection. • First have the function take the first derivative (approximately, see homework 2). Then use your local function to apply the first derivative test to see where the approximate local minima and maxima are. 1 ECE-210B Homework 3 • Next, have the function take the second derivative. Then use your local function again to find approximately where the points of inflection are. • Finally, have the function plot all this information using figure then plot(x,y,xminmax,yminmax,’ko’,xpoi,ypoi,’r*’). This will plot the function then plot black circles on the local minima and maxima and red stars on the points of inflection. • Apply your function to x 5 − 8x 3 + 10x + 6 sampled at 10000 points on [-3,3].1. Professor Mintchev has just assigned you 20 tedious Gram Schmidt Orthonormalization problems! Luckily, you are a master of MATLAB so you decide to build a function which can handle them all for you in short time. Note: This homework has been assigned in all three ECE-210 sections. • Create a function called gramSchmidt. The input to the function should be a 2-D array, each column of which is a vector in the original linearly independent set of vectors. Implement GS to create an orthonormal set of vectors from these. Store them as columns in an output matrix, similar to the input format. Feel free to use the norm function if needed. • After you’ve created this function, you’d like a way to test if it works. Create another function called isOrthonormal which has a single 2-D array as the input. The function should return 1 if all columns are orthonormal and 0 otherwise. Be careful with this – direct floating point equality comparison is a bad idea. Instead apply a threshold to the difference of the two numbers like so: if |x − xˆ| > then … The eps function might be useful here. You can add a nice big fudge factor to make the tolerance big enough that it works, just don’t make it huge. (Note that there is also the matter of spanning the same space as the original matrix, don’t worry about this condition) • Finally, we would like to estimate another vector as a linear combination of these orthonormal vectors. (Project the vector onto the space of the orthonormal vectors.) Implement a function called orthoProj which takes a vector to be estimated and and array of orthonormal columns as arguments and outputs the estimated vector. • Test all of the above functions on some random complex vectors. (use rand to make a random vector) First test the case where there are more elements in each vector than the number of vectors. Then test the case where the number of vectors is equal to the number of elements in a vector. Compare the errors. • Uniformly sample sin(x) on [0, 2π]. Generate 5 Gaussians with the equation 1 √ 2πσ2 exp −(x − µ) 2 σ 2 Give each Gaussian standard deviation 1 (σ = 1) and pick the mean from a linearly spaced vector ranging from 0 to 2π. (µ ∈ {0, π/2, π, 3π/2, 2π}) Consider using ndgrid for compact code. Plot the Sinusoid and Gaussians on the same plot. Give axis labels and a title. Use gramSchmidt to create an orthonormal set of vectors from the Gaussians. Use orthoProj to estimate the sinusoid from that set of vectors. Create a 2×1 subplot. Plot the sinusoid and the estimated sinusoid together on the upper plot. Plot the orthonormal basis functions on the lower plot. Give all plots proper labels and titles.In this homework, we will go through a few advanced data structures in MATLAB, such as cell arrays, classes, chars, as well as dataset importing in MATLAB. You will be importing in the fisheriris dataset and encapsulating it in classes. After obtaining all the data, you will be required to write some methods for the class you just created. Also note that some operations will require you to do some research, but not too much! 1. Load in the fisheriris dataset with the command load fisheriris. You should obtain a 150×4 matrix called meas, as well as a 150×1 cell array called species in your workspace. This is a very popular dataset, and you can quickly google fisheriris to see what the columns of meas represent. • Create a class called Flower in its own .m file. In your Flower class, you should have the following properties – petalWidth (double), petalLength(double), sepalWidth (double), sepalLength (double) and species (char). The ith species corresponds to the ith row of information in meas. Note that you do not need to specify the data type of the properties when you are declaring a class the following properties are just here to impress on you what type of properties you would be expecting. • Create a constructor for your class. It should take in 4 doubles and a char array corresponding, in order, to the five properties of your class. • Now, import the entries from meas and species into MATLAB and store them in a 150×1 cell array of Flower instances. You can either use a for loop to import the entries, or use a more elegant way to make all entries in one line (this would require some research on object formation in MATLAB). Either way is ok. However, note that the name of the species are stored as cell arrays; make sure to extract from the cell as a char and remove trailing white spaces before storing them in the Flower instances. There is a single function that will do this, which you should be able to find with a quick google search. • Create a method called getSWidth for the Flower class, which will return the sepal length of the object. Use this on the 30th Flower in your cell array, and check (using ==) that this is the correct value by looking that the corresponding entry in meas. • Create another method called report for the Flower object, which will print out a statement on the command window and report the details about the Flower object. This function does not need to return anything. It should print out a statement of the following form if the flower is 5.1 cm in sepal length, 3.5 cm in sepal width, 1.4 cm in petal length and 0.2 cm in petalWidth, and the species is setosa, for example: “The length and width of its sepal are 5.1 cm and 3.5cm respectively, while the length and width of its petal are 1.4cm and 0.2cm respectively. It belongs to the setosa species.”This homework deals with digital filters in a low-level sense. You are expected to know a bit about the z-transform, but if you are not in Signals and Systems, please contact me separately for some additional information on this homework if you need it. Read the parts carefully and make sure to complete every part of the homework. This homework requires you to produce a few plots; I want nice plots! Axis labels and titles are a must. 1. For this question, you will be working with the discrete system described by the transfer function: H(z) = 2 5 z 2 + 1 4 z + 1 7 1 3 z 3 − 1 8 z + 3 2 • Store this transfer function as numerator and denominator polynomials. Be VERY careful setting this up. Check the documentation for zplane to see how discrete transfer functions are handled in MATLAB. • Compute the poles and zeros using a specific MATLAB function. (Make sure you use the right one for discrete signals and not the one used mostly for continuous signals!) • Create a poly zero plot using a different MATLAB function. You may use either the poles and zeros themselves or the numerator and denominator polynomials. • Use impz to compute the impulse response of this transfer function. Compute only the first 50 points of it (there is a way to do this in the function itself). Make a stem plot of the impulse response. • Let x[n] = (− 4 5 ) n . Then use filter to apply the transfer function (or filter) to the signal. In subplots, plot the before and after. • The above is the easiest way to apply a filter, but you also ought to be able to do this analytically, using either convolution in MATLAB or the product of z-transforms. Show me you know how to do this! That is, plot the same answer achieved in another way. You don’t have to take any inverse z-transforms to do this! Note that if you use convolution with the impulse response, you’ll get a longer vector than when you used filter. Therefore, only plot the first n points where n is the length of the vector result from the previous part. 2. In this question, you will be ”designing” a bandpass filter (probably unrealistic but it’s what I came up with). A bandpass filter is a system which only allows a certain band of frequencies from a signal to pass. 1 ECE-210B Homework 6 • Last question you converted a transfer function in tf form to one in zpk form. Now we will do the opposite. Compute numerator and denominator vectors for a transfer function with k = 0.01 and these zeros and poles: zeros : −1, 1 poles : 0.9e j π 2 , 0.9e −j π 2 , 0.95e j 5π 12 , 0.95e −j 5π 12 , 0.95e j 7π 12 , 0.95e −j 7π 12 • Create a pole-zero plot. • Now compute the frequency response of this filter using freqz . Use n = 1024 points and return an H frequency response vector and a w frequency vector. DO NOT use the option to plot the frequency response. You will be manually creating the plots. • The H vector is a complex vector. That means it has both magnitude gain (via abs) and phase (via angle). Using subplots, plot the magnitude and phase against the w frequency vector. A few things to note (and will be expected in addition to proper plots): – Plot the magnitude in dB. You can convert a gain x to dB via 20log10(x). – Plot the phase in degrees. You will notice if you do that, the plot will have weird sharp edges. Remove them using unwrap before converting to degrees. – Show units in the axis labels. (Remember the frequency vector, w, has units radians not radians per second.) – Remember the frequency vector, w, only goes from 0 to π. Make sure to use xlim, xticks and xticklabels.In this assignment, you will reinforce what we did in lecture today regarding MATLAB’s filter toolbox. For each of the following questions, you will create a filter, create magnitude-phase plots for the filter and apply the filter to a signal. Follow these steps: • Generate MATLAB code for filters using the filter design toolbox in the signal processing toolbox (filterDesigner). • Create a filter object by calling the generated code. • Use the DSP toolbox’s version of freqz on the filter object. Make sure to include the sampling frequency in the function call as this is hardly mentioned in the documentation. For example, if f ilter is a filter object, n is the number of points (you can use 1024) and fs is the sampling frequency, run [H, f] = freqz(f ilter, n, fs). Note I use f instead of w since by including the sampling frequency, MATLAB scales the frequencies from [0, π] to [0, fs/2]. Hence these frequencies have units of Hertz. Keep that in mind when including units in your plots and setting the axis limits. • Create magnitude-phase plots akin to homework 6 except for the difference mentioned above regarding f. • Apply the filter to the signal using filter. • Lastly, plot the Fourier Transform of the final result using fft and plot. Refer to the notes for the proper way to use fft and obtain the proper scaling. This may seem daunting, but with properly defined functions, you may only have to do most of the work once. However, I still want unique titles for plots (maybe pass in a string?). 1. Generate a signal that consists of a sum of sine waves of frequencies 1 to 50 kHz. Set t to be from 0 to 2 seconds, using an interval of 0.001s. signal = 50000 X f=1 sin(2πf t) 2. Create a Butterworth lowpass filter with a sampling frequency of Fs = 100 kHz, a passband frequency of Fpass = 10 kHz, a stopband frequency of Fstop = 20 kHz, a passband attenuation of Apass = 5dB, and a stopband attenuation of Astop = 50dB. 1 ECE-210B Homework 7 3. Create a Chebychev I highpass filter with a sampling frequency of Fs = 100 kHz, a passband frequency of Fpass = 35 kHz, a stopband frequency of Fstop = 15 kHz, a passband attenuation of Apass = 2dB, and a stopband attenuation of Astop = 40dB. 4. Create a Chebychev II bandstop filter with a sampling frequency of Fs = 100 kHz, a passband frequency of below the frequency Fpass1 = 5 kHz and above Fpass2 = 45 kHz, a stopband frequency of between Fstop1 = 15 kHz Fstop2 = 35kHz, a passband attenuation of Apass = 5dB, and a stopband attenuation of Astop = 50dB. 5. Create a Elliptic bandpass filter with a sampling frequency of Fs = 100 kHz, a stopband frequency of below the frequency Fstop1 = 15 kHz and above Fstop2 = 35 kHz, a passband frequency of between Fpass1 = 20 kHz Fpass2 = 30 kHz, a passband attenuation of Apass = 5dB, and a stopband attenuation of Astop = 50dB.
Goal The goal of this assignment is to familiarize you with Python and help you understand information retrieval by building a simple information retrieval system.—### What to do In this assignment you will build a simple information retrieval engine that processes a set of documents, creates an inverted index to speed up information retrieval, and returns a ranked list of document filenames that match the specified keyword search, along with relevance scores and a breakdown of weights for all keywords.You will actually need to build two different Python programs: `pine-index.py` and `pine-search.py`, as follows.#### Pitt INformation retrieval Engine / Indexer Program (`pine-index.py`) This program will read all files that are in subdirectory `input/` (assuming they are all text files) and construct an inverted index. Before constructing the inverted index, the program should: * convert all characters to lower case, * eliminate punctuation, * eliminate numbers, and * perform stemming using the `nltk` stemmer.The inverted index should have for every word: a list of documents the word appears in, along with how many times the word appeared per document. Additionally, for every word, there should be a count of how many documents the word appears in (in order to compute its inverse document frequency). There should also be a count of the total number of documents. All this information needs to be in a single data structure (suggest *dict*).Before the program terminates, it should store the created data structure as a JSON object in a file named `inverted-index.json`.> Directory `input/` has nine sample documents (`doc1.txt` … `doc9.txt`) that can be used for testing your program. You are encouraged to test your program with other documents as well. We will grade your programs with additional document collections as well. >#### Pitt INformation retrieval Engine / Search Program (`pine-search.py`) This program will read the JSON object from file `inverted-index.json` and a set of keywords from file `keywords.txt` and will produce an ordered list of document filenames, along with their relevance scores and a breakdown of weights for all keywords.The keyword file will contain one set of keywords per line, that are space separated. It may have one ore more lines. > A sample `keywords.txt` file is provided. >The relevance score for each document will be computed as explained in class. > w(key, doc) = (1 + log2 freq(key,doc)) * log2 (N / n(doc)) > where n(doc) is the number of documents that contain keyword key and N is the total number of documents >The output of your program should be in the following format:“` ———————————————————— keywords = pittsburgh steelers[1] file=doc3.txt score=3.532495 weight(pittsburgh)=0.362570 weight(steelers)=3.169925 … “` > A sample output, for the keywords contained in the `keywords.txt` file is provided in the file `output.txt` >Note that in cases of documents with the same relevance score, their ranks are tied and the same number is used for all (for example, there are four documents ranked [5] in the sample output. You should order those by filename order.### Important notes about grading It is absolutely imperative that your python programs: * run without any syntax or other errors (using Python 3) — we will run them using the following command: `python3 pine-index.py` and `python3 pine-search.py` * strictly adhere to the format specifications for input and output, as explained above.Failure in any of the above will result in **severe** point loss.### Allowed Python Libraries You are allowed to use the following Python libraries: “` argparse collections csv json glob math nltk os pandas re requests string sys time xml “` If you would like to use any other libraries, you must ask permission by Sunday, January 27, 2019, using [piazza](https://cs1656.org).—### How to submit your assignment For this assignment, you must use the repository that was created for you after visiting the classroom link. You need to update the repository to include files `pine-index.py` and `pine-search.py`, as described above, and other files that are needed for running your program. You need to make sure to commit your code to the repository provided.We will clone all repositories shortly after midnight: * the day of the deadline **Tuesday, February 5th, 2019** * 24 hours later (for submissions that are one day late / -5 points), and * 48 hours after the first deadline (for submissions that are two days late / -15 points). **No submissions will be accepted that are more than two days late, i.e., after midnight on Thursday, February 7th, 2019.**### About your github account It is very important that: * Your github account can do **private** repositories. If this is not already enabled, you can do it by visiting * You use the same github account for the duration of the course. * You use the github account that you already specified using TopHat.Goal The goal of this assignment is for you to gain familiarity with SQL.—### What to doIn this assignment you are asked to: * update a skeleton Python script (`moviepro.py`) in order to read input from CSV files and insert the data into the `cs1656.sqlite` database, and * provide SQL queries that answer 12 questions.The provided skeleton Python script includes database initialization commands and also includes commands to run the SQL queries and store their output in separate output files, which you should not modify. What you should update are the parts of the script that are responsible for reading in the input data (and inserting it into the database) and for specifying the 12 SQL queries.### Database SchemaThe schema of the database is embedded in the `moviepro.py` Python script and should not be modified. It is as follows: * Actors (aid, fname, lname, gender) * Movies (mid, title, year, rank) * Directors (did, fname, lname) * Cast (aid, mid, role) * Movie_Director (did, mid)### Reading input from CSV filesYour program should read input from the following CSV files: * `actors.csv`, containing data for the Actors table, * `cast.csv`, containing data for the Cast table, * `directors.csv`, containing data for the Directors table, * `movie_dir.csv`, containing data for the Movie_Director table, and * `movies.csv`, containing data for the Movies table.All the data should be inserted into the appropriate tables into the `cs1656.sqlite` database. Sample insert statements have been provided in the `moviepro.py` script, but you are not restricted to doing the insertions in exactly the same way.Samples of all these files are provided as part of this repository.### QueriesYou are asked to provide SQL queries that provide answers for the following questions. Note that **actors** refers to both male and female actors, unless explicitely specified otherwise. Also note that you should not rely on the data provided in the sample CSV files for any of the answers; the datasets will be replaced with bigger files. Finally, please note that you may define views, etc, as part of other queries.* **[Q01]** List all the actors (first and last name) who acted in at least one film in the 80s (1980-1990, both ends inclusive) and in at least one film in the 21st century (>=2000). Sort alphabetically, by the actor’s last and first name.* **[Q02]** List all the movies (title, year) that were released in the same year as the movie entitled `”Rogue One: A Star Wars Story”`, but had a better rank (Note: the higher the value in the *rank* attribute, the better the rank of the movie). Sort alphabetically, by movie title.* **[Q03]** List all the actors (first and last name) who played in a Star Wars movie (i.e., title like ‘%Star Wars%’) in decreasing order of how many Star Wars movies they appeared in. If an actor plays multiple roles in the same movie, count that still as one movie. If there is a tie, use the actor’s last and first name to generate a full sorted order.* **[Q04]** Find the actor(s) (first and last name) who **only** acted in films released before 1985. Sort alphabetically, by the actor’s last and first name.* **[Q05]** List the top 20 directors in descending order of the number of films they directed (first name, last name, number of films directed). For simplicity, feel free to ignore ties at the number 20 spot (i.e., always show up to 20 only).* **[Q06]** Find the top 10 movies with the largest cast (title, number of cast members) in decreasing order. Note: show all movies in case of a tie.* **[Q07]** Find the movie(s) whose cast has more actresses than actors (i.e., gender=female vs gender=male). Show the title, the number of actresses, and the number of actors in the results. Sort alphabetically, by movie title.* **[Q08]** Find all the actors who have worked with at least 7 different directors. Do not consider cases of self-directing (i.e., when the director is also an actor in a movie), but count all directors in a movie towards the threshold of 7 directors. Show the actor’s first, last name, and the number of directors he/she has worked with. Sort in decreasing order of number of directors.* **[Q09]** For all actors whose first name starts with an S, count the movies that he/she appeared in his/her debut year (i.e., year of their first movie). Show the actor’s first and last name, plus the count. Sort by decreasing order of the count.* **[Q10]** Find instances of nepotism between actors and directors, i.e., an actor in a movie and the director having the same last name, but a different first name. Show the last name and the title of the movie, sorted alphabetically by last name.* **[Q11]** The Bacon number of an actor is the length of the shortest path between the actor and Kevin Bacon in the *”co-acting”* graph. That is, Kevin Bacon has Bacon number 0; all actors who acted in the same movie as him have Bacon number 1; all actors who acted in the same film as some actor with Bacon number 1 have Bacon number 2, etc. List all actors whose Bacon number is 2 (first name, last name). You can familiarize yourself with the concept, by visiting [The Oracle of Bacon](https://oracleofbacon.org).* **[Q12]** Assume that the *popularity* of an actor is reflected by the average *rank* of all the movies he/she has acted in. Find the top 20 most popular actors (in descreasing order of popularity) — list the actor’s first/last name, the total number of movies he/she has acted, and his/her popularity score. For simplicity, feel free to ignore ties at the number 20 spot (i.e., always show up to 20 only).—### Important notes about grading It is absolutely imperative that your python program: * runs without any syntax or other errors (using Python3) — we will run it using the following command: `python3 moviepro.py` * strictly adheres to the format specifications for input and output, as explained above.Failure in any of the above will result in **severe** point loss.### Allowed Python Libraries You are allowed to use the following Python libraries (although not all are needed): “` argparse collections csv json glob math os pandas re requests string sqlite3 sys time xml “` If you would like to use any other libraries, you must ask permission by Monday, February 11, 2019, using [piazza](https://piazza.cs1656.org).—### How to submit your assignment For this assignment, you must use the repository that was created for you after visiting the classroom link. You need to update the file `moviepro.py` as described above, and add other files that are needed for running your program. You need to make sure to commit your code to the repository provided. We will clone all repositories shortly after midnight: * the day of the deadline **Sunday, February 17, 2019** * 24 hours later (for submissions that are one day late / -5 points), and * 48 hours after the first deadline (for submissions that are two days late / -15 points).Our assumption is that everybody will submit on the first deadline. If you want us to grade a late submission, you need to email us at `[email protected]`### About your github account It is very important that: * Your github account can do **private** repositories. If this is not already enabled, you can do it by visiting * You use the same github account for the duration of the course. * You use the github account that you specified during the test assignment.The goal of this assignment is for you to gain familiarity with association rule mining and (in the process) to also advance your Python skills.—### What to do — arma.py In this assignment you are asked to implement a simplified version of the A-Priori **a**ssociation **r**ule **m**ining **a**lgorithm, in Python. You should name your program `arma.py`. It should be called as follows:`python arma.py input_filename output_filename min_support_percentage min_confidence`(or just `python` if python version 3 is your default python setup)where: * `input_filename` is the name of the file that contains market basket data that is the input to your program. The format for the input file is provided below. A sample file `input.txt` is provided together with this repository.> **Input Format:** The input data should be provided as a CSV file, in the following format: `transaction_id, item_1, item_2, item_3, …` > for example: “` 1, A100, A105, A207 2, A207 3, A100, A105 “` > Notes: > * Item names could consist of either numbers (0-9) or characters (a-zA-z) or combinations of numbers and characters. No spaces or puncuation characters are allowed in item names. > * The CSV files may or may not contain whitespace between values.* `output_filename` is the name of the file that will store the required output of your program. The file should contain the frequent item sets and the association rules that you discovered after processing the submitted input data. The required format for the output file is provided below. Sample output files (matching the input file provided) are provided together with this repository.> **Output Format:** The output data should be provided as a CSV file, where every row is in one of the following formats: `S, support_percentage, item_1, item_2, item_3, …` > to denote that this is a frequent item**s**et or: `R, support_percentage, confidence, item_4, item_5, …, ’=>’, item_6, item_7, … ` > to denote that this is an association **r**ule. The keys “S” and “R” are verbatim and no other substitution is needed. > It should be noted that the items listed in the frequent itemset case (item 1, item 2, item 3, …) should be in lexicographic order, the items listed to the left of the => sign in the association rule case (item 4, item 5, …) should be in lexicographic order and so should the items listed in the right size of the => sign in the association rule case (item 6, item 7, …). > The `support_percentage` should be the support percentage (expressed as a floating number between 0 and 1 with 4 decimal points) for the specific frequent itemset or for the specific association rule (and both should be above the user-specified min_support_percentage). > The `confidence` should be the confidence percentage (expressed as a floating number between 0 and 1 with 4 decimal points) for the specific association rule (and should be above the user-specified min_confidence). > You should list in the output file all the frequent itemsets that you discover in the input file (S) and all the association rules that you can generate using the A-Priori method (R), that satisfy the min support percentage and min confidence requirements. > > Here’s an example output file: “` S, 0.3000, A105 S, 0.2500, A100 S, 0.2000, A100, A207 S, 0.2000, A105, A207 S, 0.1500, A100, A105, A207 R, 0.1500, 0.5000, A105, ’=>’, A100, A207 “`> Important Note: You should print 4 decimal points for all floating point numbers (e.g., use %.4f in your print statement). > Note: Your program may print additional messages; these will not be considered. You are encouraged to use this mechanism for debugging or progress reporting purposes. Only the results contained in the output file, in the specified format, will be considered. > The repository contains three output files as follows:| Input Filename | Output Filename | Minimum Support Percentage | Minimum Confidence | | — | — | — | — | | input.csv | output.sup=0.5,conf=0.7.csv | 0.5 | 0.7 | | input.csv | output.sup=0.5,conf=0.8.csv | 0.5 | 0.8 | | input.csv | output.sup=0.6,conf=0.8.csv | 0.6 | 0.8 | * `min_support_percentage` is the minimum support percentage for an itemset / association rule to be considered frequent, e.g., 5%. This should be provided as a floating point number (out of 1), e.g., 0.05, 0.4, 0.5 are used to denote 5%, 40%, and 50% respectively. You should not include a percent symbol.* `min_confidence` is the minimum confidence for an association rule to be significant, e.g., 50%. This should be provided as a floating point number (out of 1), e.g., 0.05, 0.4, 0.5 are used to denote 5%, 40%, and 50% respectively. You should not include a percent symbol.An example call to your program could be as follows: `python3 arma.py input.csv output.csv 0.5 0.7`—### What to do — A-Priori AlgorithmThe A-Priori algorithm utilizes the subset property for frequent itemsets, enabling significant pruning of the space of possible itemset combinations. Assuming a provided min support percentage and a min confidence, the i-th step of the algorithm works as follows:**Step i:**• Consider all the candidate frequent itemsets of size i. Let’s name them CFI(i). • Count how many times each itemset in CFI(i) appears in our input data. This is the support count, which is turned into the support percentage by dividing with the total number of transactions. • The itemsets in CFI(i) whose support percentage is at least as much as the min support percentage become the verified frequent itemsets, or VFI(i). • Using itemsets in VFI(i) generate all plausible candidate itemsets of size +1, i.e., CFI(i + 1). This makes use of the subset property. For example, for ABC to be in CFI(3), all of AB, BC, and AB need to be in VFI(2).This process starts with CFI(1) being all individual items and terminates on Step k, when CFI(k + 1) is empty.The above process generates all the frequent itemsets, i.e., VFI(i), for 1 A,C * C=>A,B * A,B=>C * A,C=>B * B,C=>Aand compute their support and confidence. Note that the support of all these rules is the same as the support of the frequent itemset from which they came, i.e., {A,B,C}.—### Important notes about grading It is absolutely imperative that your python program: * runs without any syntax or other errors (using Python 3) — we will run it using the following command: `python3 arma.py …` * strictly adheres to the format specifications for input and output, as explained above.Failure in any of the above will result in **severe** point loss.### Allowed Python Libraries You are allowed to use the following Python libraries: “` argparse collections csv glob itertools math os pandas re requests string sys “` If you would like to use any other libraries, you must ask permission by Friday, March 8, 2019, using [piazza](https://piazza.cs1656.org).—### How to submit your assignment For this assignment, you must use the repository that was created for you after visiting the classroom link. You need to create the file `arma.py` as described above, and add other files that are needed for running your program. You need to make sure to commit your code to the repository provided. We will clone all repositories shortly after midnight: * the day of the deadline **Sunday, March 24, 2019** (i.e., 0:15am, Monday, March 25, 2019) * 24 hours later (for submissions that are one day late / -5 points), and * 48 hours after the first deadline (for submissions that are two days late / -15 points).Our assumption is that everybody will submit on the first deadline. If you want us to grade a late submission, you need to email us at `[email protected]`### About your github account It is very important that: * Your github account can do **private** repositories. If this is not already enabled, you can do it by visiting * You use the same github account for the duration of the course. * You use the github account that you specified on tophat.The goal of this assignment is for you to gain familiarity with Graph Databases in general, and with Neo4j and, its query language, Cypher, in particular.—### What to doIn this assignment you are asked to: * download neo4j locally, * download the Movies database locally, * provide Cypher queries that answer 8 questions, and * write a Python script (‘movie-queries.py’) that will run your solutions for the 8 queries and store the query output in a file.### Database ModelWe will use the Movies database , which has the following node labels: * Actor * Director * Movie * Person * User and the following relationship types (i.e., edge labels): * ACTS_IN * DIRECTED * FRIEND * RATEDThe nodes in the Movies database have a number of attributes, including the following: * name (for Actor/Director/Person/User) * birthday (for Actor/Director/Person/User) * title (for Movie) * genre (for Movie)### SetupYou are asked to follow the installation instructions and to utilize the lab material provided through `Recitation 09` (March 22, 2019). This will enable you to have a locally running neo4j server, along with an interactive query interface. You will also be able to download the Movies database directly into neo4j.Please note that although we will use the same database model for testing your submissions. However, it will not necessarily be identical to the one you will download.### Connecting to neo4j using PythonAs part of this repository, you are provided with a sample Python script (`cypher_sample1.py`) that connects to the local graph database (which you have established by following the previous steps).### QueriesYou are asked to provide Cypher queries that provide answers for the following questions. Note that **actors** refers to both male and female actors, unless explicitly specified otherwise.* **[Q1]** List the first 20 actors in descending order of the number of films they acted in. *OUTPUT*: actor_name, number_of_films_acted_in* **[Q2]** List the titles of all movies with a review with at most 3 stars. *OUTPUT*: movie title* **[Q3]** Find the movie with the largest cast, out of the list of movies that have a review. *OUTPUT*: movie_title, number_of_cast_members* **[Q4]** Find all the actors who have worked with at least 3 different directors (regardless of how many movies they acted in). For example, 3 movies with one director each would satisfy this (provided the directors where different), but also a single movie with 3 directors would satisfy it as well. *OUTPUT*: actor_name, number_of_directors_he/she_has_worked_with* **[Q5]** The Bacon number of an actor is the length of the shortest path between the actor and Kevin Bacon in the *”co-acting”* graph. That is, Kevin Bacon has Bacon number 0; all actors who acted in the same movie as him have Bacon number 1; all actors who acted in the same film as some actor with Bacon number 1 have Bacon number 2, etc. *List all actors whose Bacon number is exactly 2* (first name, last name). You can familiarize yourself with the concept, by visiting [The Oracle of Bacon](https://oracleofbacon.org). *OUTPUT*: actor_name* **[Q6]** List which genres have movies where Tom Hanks starred in. *OUTPUT*: genre* **[Q7]** Show which directors have directed movies in at least 2 different genres. *OUTPUT*: director name, number of genres* **[Q8]** Show the top 5 pairs of actor, director combinations, in descending order of frequency of occurrence. *OUTPUT*: director’s name, actors’ name, number of times director directed said actor in a movie### Output Format (ignore at your own risk!)You are asked to store the output for running all Cypher queries by your python script in a **single** file, named `output.txt`. For each query, you should have a header line `### Q1 ###`, followed by the results of the query (one row at a time, with commas separating multiple fields). If you do not provide an answer for the query, you should still print the header line in your output file, but leave a blank line after it. Answers should be ordered by query number and separated by a blank line as well.For example, for the following question:Q0: show the 3 oldest actors in the database, with the oldest one first. *OUTPUT*: name, idThe corresponding Cypher query should be: “` match (n:Actor) return n.name, n.id order by n.birthday ASC LIMIT 3 “`The output file should be as follows: “` ### Q0 ### Claudia Cardinale, 4959 Oliver Reed, 936 Anthony Hopkins, 4173 “`Finally, there should be an empty line between different results.—### Important notes about grading It is absolutely imperative that your python program: * runs without any syntax or other errors (using Python 3) — we will run it using the following command: `python3 movie-queries.py` * generates file `output.txt` with the answers of all 8 queries * strictly adheres to the format specifications for output, as explained above.Failure in any of the above will result in **severe** point loss.### Allowed Python Libraries You are allowed to use the following Python libraries: “` argparse collections csv glob json math neo4j.v1 numpy os pandas re requests statistics string sqlite3 sys “` If you would like to use any other libraries, you must ask permission by Wednesday, April 3th, 2019, using [piazza](https://piazza.cs1656.org).—### How to submit your assignment For this assignment, you must use the repository that was created for you after visiting the classroom link. You need to create the file `movie-queries.py` as described above, and add other files that are needed for running your program. You need to make sure to commit your code to the repository provided. We will clone all repositories shortly after midnight: * the day of the deadline **Friday, April 12th, 2019 (i.e., at 12:15am, Saturday, April 13th, 2019)** * 24 hours later (for submissions that are one day late / -5 points), and * 48 hours after the first deadline (for submissions that are two days late / -15 points).### About your github account It is very important that: * Your github account can do **private** repositories. If this is not already enabled, you can do it by visiting * You use the same github account for the duration of the course. * You use the github account that you specified during the test assignment.The goal of this assignment is to familiarize you with classification systems in general and with decision tree classifiers in particular.### What to do — dec_tree.py You are asked to write a Python program, called `dec_tree.py` that will 1. read a decision tree (stored in a plain text file), 2. read a test data set (stored in a csv file, with the first row having the variable names), and 3. evaluate the test data using the provided decision tree and provide statistics.Your program should be invoked as: “` python3 dec_tree.py tree.txt test.csv “`### (1) Decision Tree Format The decision tree will be provided as a text file and will essentially be the output from the ID3 Decision Tree Classifier.A sample decision tree is provided below and also included as file `tree.txt` within this repository: “` color black: bad (2) color blue | fruit blueberries: good (2) | fruit grapes: bad (1) color green | fruit blueberries: bad (2) | fruit grapes: good (2) color red | fruit blueberries: bad (1) | fruit grapes: good (1) “`The above was generated by the `treegen.py` program which is also included within this repository. The format is fairly straightforward: the above tree corresponds to a two-level decision tree, with `color` being the first variable (valid options: `black`, `blue`, `green`, and `red`) and `fruit` the second variable (valid options: `blueberries` and `grapes`). There are only two labels: `good` and `bad`. The numbers in parentheses denote how many samples each rule was built upon.Your program **should handle decision trees up to 3 levels deep**.Please note that although you are encouraged to experiment with the `decision-tree-id3` module (https://svaante.github.io/decision-tree-id3/index.html), used by the `treegen.py` program, as part of preparing your assignment, you are **not allowed to use the decision-tree-id3 module in your submission**.### (2) Test Data Format The test data set will be provided as a CSV file. The first row will contain the variable names. A sample test data file, named `test.csv`, is provided within this repository. The first 3 lines of the file are shown below: “` “day_of_week”, “fruit”, “color” “mon”, “blueberries”, “black” “mon”, “blueberries”, “blue” “`Please note that the number of variables in the test data set is greater than or equal to the number of variables specified in the decision tree file. In this example, `day_of_week` was not part of the decision tree.### (3) How to evaluate the decision tree Given the decision tree and the test data input files, you are asked to do two things: 1. for each row in the test data set, find which rule from the decision tree it will match against, and 2. keep track of how many times each rule in the decision tree was matched and print these statisticsYour program should only print the statistics for all rules and it must follow the same format as in the decision tree format.For example, the correct output for running your program with the provided `tree.txt` and `test.csv` files should be the following (included in the repository as `output.txt`): “` color black: bad (6) color blue | fruit blueberries: good (3) | fruit grapes: bad (2) color green | fruit blueberries: bad (4) | fruit grapes: good (5) color red | fruit blueberries: bad (2) | fruit grapes: good (4) UNMATCHED: 1 “`Note that you must include a line at the end if the test data contain rows that were not matched by any decision tree rules.**Important Hint** In order to solve this assignment, you are strongly encouraged to read the documentation for the `exec()` python command https://docs.python.org/3/library/functions.html#exec### Important: special-cases.txt If you do something in your code that you would consider a special case, then you are requested to submit an extra file, along with your submission, named `special-cases.txt`, where you described in plain text what the special case(s) is/are and how you handled it/them in your program. We will use this mechanism instead of asking such questions in piazza.### Important notes about grading It is absolutely imperative that your python program: * runs without any syntax or other errors (using Python 3) * strictly adheres to the format specifications for input and output, as explained above.Failure in any of the above will result in **severe** point loss.### Allowed Python Libraries (Updated) You are allowed to use the following Python libraries (although a fraction of these will actually be needed): “` argparse collections csv json glob math numpy os pandas re requests string sys time “` If you would like to use any other libraries, you must ask permission by Sunday, April 14th, 2019, using [piazza](https://cs1656.org).### About your github account It is very important that: * Your github account can do **private** repositories. If this is not already enabled, you can do it by visiting * You use the same github account for the duration of the course * You use the github account that you specified at the beginning of the course### How to submit your assignment For this assignment, you must use the repository that was created for you after visiting the classroom link. You need to update the repository to include your own python files as described above, and other files that are needed for running your program. You need to make sure to commit your code to the repository provided. We will clone all repositories shortly after midnight the day of the deadline **Saturday, April 20th, 2019 (i.e., at 12:15am, Sunday, April 21st, 2019)**. There are no late submissions allowed for this assignment.
Goal: To gain a better understanding of search algorithms and symbol tables by implementing an autocompletion engine.## Background: In order to make typing on a mobile device quick and easy, an autocomplete feature is commonly implemented to try to guess what word a user wishes to type before they are finished. Such a feature requires extensive use of search algorithms.## Specifications: * First, download a copy of the English dictionary that you will use for this project from [here](https://people.cs.pitt.edu/~nlf4/cs1501/handouts/dictionary.txt) and place it in your repository folder * **Do not** add this file to your git repository, however! (i.e., do not run `git add dictionary.txt`). * You must implement a De La Briandais (DLB) trie data structure (as described in lecture) to use in your project. * When your program is run, it should first create a new DLB trie and add all of the words in `dictionary.txt` to that trie (this will be the dictionary trie). * Once the dictionary trie is established, you should prompt the user to start typing a word. For this project, you will be writing only a simple program to test autocomplete functionality. Due to complexities with gathering single character input in Java, you should accept a single character at a time, each followed by `Enter`. After each character, present the user with the list of predictions of the word that they are trying to type. If the user types a number (1-5), you should consider the user to have selected the corresponding prediction, and restart the process for a new word. Consider `$` to be a terminator character; if the user enters a `$`, consider the characters input so far to be the full word as intended (regardless of suggestions). Finally, if the user enters a `!` at any point, your program should exit. * To generate the list of predictions, your program should not only consult the dictionary trie, but also keep track of what words the user has entered in the past. If the user has previously entered the same sequence of characters as a prefix to a word, you should prioritize the words that most frequently resulted from this sequence previously. If the user has never entered the current sequence before, or has entered fewer than 5 words with the current seequence as a prefix (i.e., not enough words to complete the list of 5 predictions), your program should suggest words from dictionary.txt that have the current sequence as a prefix. * You program should propose at most 5 suggestions at a time. If there are fewer than 5 suggestions available from the user’s history and the dictionary trie, then only print out the available suggestions. * If the current sequence of characters has not been entered by the user before and does not appear in `dictionary.txt`, you should display a message to the user stating that no predicions were found, and allow the user to continue entering characters one at a time. Once the user enters a “$”, you should consider the word to be finished and add it to the user’s history so that you can predict it in the future. * Your program should run in a case sensitive manner in order to allow for easier prediction of proper nouns and acronyms. * The design of the data structure that keeps track of a user’s previously entered words is entirely up to you. You must create a file named `approach.txt` that both describes your approach to implementing this symbol table and justifies your decision to take this approach. Note that this file does not need to be extensive, just a few lines so the TA is aware of what to look for in your code and why you chose this approach. * The history of the user’s entered words should persist across runs of your program. To enable this, your program should save a representation of this data structure to the file `user_history.txt` before exiting. * Do not add this file to your git repository! (i.e., do not run `git add user_history.txt`) It should be generated by your program if it does not exist. * Each time the user enters a character, you should use Java’s [`System.nanoTime()`] (https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#nanoTime–) to calculate how long your program takes to find the predictions. You should display this time along with the list of predictions. * After the user enters `!`, your program should output the average time that was required to produce a list of predictions.An example run of the program would proceed as follows:“` Enter your first character: t(0.000251 s) Predictions: (1) t (2) ta (3) tab (4) tab’s (5) tabbedEnter the next character: h(0.000159 s) Predictions: (1) thalami (2) thalamus (3) thalamus’s (4) thalidomide (5) thalidomide’sEnter the next character: e(0.000052 s) Predictions: (1) the (2) theater (3) theater’s (4) theatergoer (5) theatergoer’sEnter the next character: r(0.000225 s) Predictions: (1) therapeutic (2) therapeutically (3) therapeutics (4) therapeutics’s (5) therapiesEnter the next character: e(0.000182 s) Predictions: (1) there (2) there’s (3) thereabout (4) thereabouts (5) thereafterEnter the next character: 3WORD COMPLETED: thereaboutEnter first character of the next word: t(0.000128 s) Predictions: (1) thereabout (2) t (3) ta (4) tab (5) tab’sEnter the next character: h(0.000094 s) Predictions: (1) thereabout (2) thalami (3) thalamus (4) thalamus’s (5) thalidomideEnter the next character: e(0.000085 s) Predictions: (1) thereabout (2) the (3) theater (4) theater’s (5) theatergoerEnter the next character: r(0.000145 s) Predictions: (1) thereabout (2) therapeutic (3) therapeutically (4) therapeutics (5) therapeutics’sEnter the next character: e(0.000130 s) Predictions: (1) thereabout (2) there (3) there’s (4) thereabouts (5) thereafterEnter the next character: !Average time: 0.000145 s Bye! “`## Submission Guidelines: * **DO NOT** add `dictionary.txt` to your git repository. * **DO NOT** add `user_history.txt` to your git repository, it must be generated by your program. * **DO NOT SUBMIT** any IDE package files. * You must name your main program file `ac_test.java`. * You must be able to compile your program by running `javac ac_test.java`. * You must be able to run your program by running `java ac_test`. * You must fill out `info_sheet.txt`. * Be sure to remember to push the latest copy of your code back to your GitHub repository before the the assignment is due. At the deadline, the repositories will automatically be copied for grading. Whatever is present in your GitHub repository at that time will be considered your submission for this assignment.## Additional Notes: * You are free to use any data structures written by you, the textbook authors, or in the Java standard library to implement the user history symbol table. However, if you use code that you do not write yourself, you must research the runtime of that particular implementation and discuss that in your `approach.txt`. * Note that if your user history predictions contain a word that is also contained in the dictionary predictions, this word should not be presented as a suggestion to the user twice in the same prompt (e.g., the final list of predictions in the example above). * You do not need to implement any sort of autocorrect. You can assume that each character entered by the user is intentional. * You can assume that the user will not try to enter any numerical characters aside from selecting a prediction.## Grading Rubric: * DLB trie implemented as described in class: 20 * Dictionary predictions are correctly populated: 25 * User history predictions are correctly populated: 30 * Sufficient justification of user history approach: 10 * User interaction works as specified: 5 * Timing data presented: 5 * Assignment info sheet/submission: 5Goal: To understand the innerworkings and implementation of the LZW compression algorithm, and to gain a better understanding of the performance it offers.## High-level description: As we discussed in lecture, LZW is a compression algorithm that was created in 1984 by Abraham Lempel, Jacob Ziv, and Terry Welch. In its most basic form, it will output a compressed file as a series of fixed-length codewords. This is the approach implemented in the LZW code provided by the authors of the textbook. As we discussed in class, *variable-width* codewords can be used to increase the size of codewords output as the dictionary fills up. Further, once the dictionary fills up, the algorithm can either stop adding patterns and continue compression with only the patterns already discovered, or the algorithm can reset the codebook to find new patterns. The LZW code provided by the textbook authors simply continues to used patterns added to the codebook.For this project, you will be modifying the LZW source code provided by the authors of the text book to use variable-width codewords, and to optionally reset the codebook under certain conditions. With these changes in hand, you will then compare the performance of your modified LZW code with the provided LZW code, and further with the performance of a widely used compression application of your choice.## Specifications: 1. First download copies of the 14 example files from [https://people.cs.pitt.edu/~nlf4/cs1501/handouts/example_files/](https://people.cs.pitt.edu/~nlf4/cs1501/handouts/example_files/) and place them in the `example_files` folder of your repository. * Do not add these files to your git repository, however! (i.e., do not run `git add …` for any of these files). 1. Make a copy of `LZW.java` named `MyLZW.java`. You will be modifying this file for your assignment. Note that `LZW.java` is the example LZW code provided by the textbook. 1. Before making the required changes to `MyLZW.java`, you will need to read through the code, and run example compressions/expansions to understand how it is currently working. Note that `LZW.java` (and hence your `MyLZW.java`) requires the following library files (also developed by the textbook authors): `BinaryStdIn.java`, `BinaryStdOut.java`, `TST.java`, `Queue.java`, `StdIn.java`, and `StdOut.java`. These files have already been added to your repository. 1. With a firm understanding of the provided code in hand, you can proceed to make the following changes to `MyLZW.java`: * Make it so that the algorithm will vary the size of the output/input codewords from 9 to 16 bits. * The codeword size should be increased when all of the codewords of a previous size have been used * Modify the code to have three options when the codebook is filled up (i.e., all 16 bit codewords have been used): 1. **Do Nothing mode** Do nothing and continue to use the full codebook (this is already implemented by `LZW.java`). 1. **Reset mode** Reset the dictionary back to its initial state so that new codewords can be added. Be careful to reset at the appropriate place for both compression and expansion, so that the algorithms remain in sync. This is very tricky and may require alot of planning in order to get it working correctly. 1. **Monitor mode** Initially do nothing (keep using the full codebook) but begin monitoring the *compression ratio* whenever you fill the codebook. Define the compression ratio to be the size of the uncompressed data that has been processed/generated so far divided by the size of the compressed data generated/processed so far (for compression/expansion, respectively). If the compression ratio degrades by more than a set threshold from the point when the last codeword was added then reset the dictionary back to its initial state. To determine the threshold for resetting you will take a ratio of compression ratios [(old ratio)/(new ratio)], where old ratio is the ratio recorded when your program last filled the codebook, and new ratio is the current compression ratio. If the ratio of ratios exceeds 1.1 then you should reset. For example, if the compression ratio when you start monitoring is 2.5 and the compression ratio at some later point is 2.3, the ratio of ratios at that point would be 2.5/2.3 = 1.087, so you should not reset the dictionary. Continuing, if your compression ratio drops to 2.2, the ratio of ratios would become 2.5/2.2 or 1.136. This means that your ratio of ratios has exceeded the threshold of 1.1 and you should now reset the dictionary. Be very careful to coordinate the code for both compression and expansion so that it works correctly. * You cannot encode either a codeword size switch or a codebook reset into the compressed file useing a delimiter. You must have your compression/expansion code detect when to switch codeword sizes and reset based on the state of the codebook. * Which mode should be used should be chosen by the program during compression. Whichever mode is used to compress a file should also be used to expand the file. However, you should not require the user to state the mode to use for expansion. The mode used to compress a file should be stored at the beginning of the output file, so that it can be automatically retrieved during expansion. To establish the mode to be used during compression, your program should accept 3 new command line arguments: * “n” for Do Nothing mode * “r” for Reset mode * “m” for Monitor mode * Note that the provided LZW code already accepts a command line argument to determine whether compression or expansion should be performed (“-” and “+”, respectively), and that input/output files are provided via standard I/O redirection (“<” to indicate an input file and “>” to indicate an output file). Hence, your new arguments should be handled in addition to what is provided. For example, to compress the file foo.txt to generate foo.lzw using Reset mode, you should be able to run: “` java MyLZW – r < foo.txt > foo.lzw “` Similarly to expand foo.lzw into foo2.txt, you should run: “` java MyLZW + < foo.lzw > foo2.txt “` Note that this example does not overwrite foo.txt. This is a good approach to take in testing your programs so that you can compare foo.txt and foo2.txt to ensure that they are the same file. 1. Once all of the required changes have been made to `MyLZW.java`, you should evaluate its performance on the 14 provided example files: `all.tar`, `assig2.doc`, `bmps.tar`, `code.txt`, `code2.txt`, `edit.exe`, `frosty.jpg`, `gone_fishin.bmp`, `large.txt`, `Lego-big.gif`, `medium.txt`, `texts.tar`, `wacky.bmp`, and `winnt256.bmp`. Specifically, for each of the provided example files, measure the original file size, compressed file size, and compression ratio (original file size / compressed file size) when compressed using the following techniques: * The unmodified `LZW.java` program (i.e., 12 bit codewords) * Your `MyLZW.java` (variable width codewords) using Do Nothing mode * Your `MyLZW.java` (variable width codewords) using Reset mode * Your `MyLZW.java` (variable width codewords) using Monitor mode * Another existing compression application of your choice (e.g., 7zip, WinZIP, gzip, bzip2) You should organize your results of these compressions/expansions into a table in a text file named `results.txt` and submit it along with your code.## Submission Guidelines: * **DO NOT SUBMIT** any IDE package files. * You must name the primary driver for your program `MyLZW.java`. * You must be able to compile your game by running `javac MyLZW.java`. * You must be able to run your program as shown in the above example. * You must fill out info_sheet.txt. * Be sure to remember to push the latest copy of your code back to your GitHub repository before the the assignment is due. At the deadline, the repositories will automatically be copied for grading. Whatever is present in your GitHub repository at that time will be considered your submission for this assignment.## Additional Notes/Hints: * In the author’s code the bits per codeword (W) and number of codewords (L) values are constants. However, in your version you will need them to be variables. Clearly, as the bits per codeword value increases, so does the number of codewords value. * The TST the author uses can grow dynamically, so it does not matter how large the dictionary will be. However, for the `expand()` method an array of String is used for the dictionary. Make sure this is large enough to accommodate the maximum possible number of codewords. * Carefully trace what your code is doing as you modify it. You only have to write a few lines of code for this program, but it could still require a substantial amount of time to get to work properly. Clearly the trickiest parts occur when the bits per codeword values are increased and when the dictionary is reset. I recommend tracing these portions of code, either on paper or with output statements to make sure your compression and expansion sections are treating them correctly. One idea is the have an extra output file for each of the `compress()` and `expand()` methods to output any trace code. Printing out (codeword, string) pairs in the iterations just before and after a bit change or reset is done can help you a lot to synchronize your code properly. * Be especially careful with the dictionary reset and monitor compression ratio options. These are very tricky and take alot of thought to get to work. Think about what happens when the dictionary is reset and what is necessary to do in the `compress()` and `expand()` methods. I recommend getting the variable width codeword part of the program to work first and then moving on to implementing Reset mode and Monitor mode. * Start on this project early! Not only will the implementation be tricky, but you will need to finish the programming portion of your project with enough time left over to gather results using your code to compress the example files. * Note that `LZW.java` (and consequently your `MyLZW.java`) rely on redirecting standard in and standard out to the input and output files (respectively). An overview of I/O redirection can be found [here](https://www.tldp.org/LDP/abs/html/io-redirection.html). Note that a consequence of this is that any text printed to standard out (i.e., via `System.out.println()`) will be redirected to the output file instead of the terminal. Standard error, however, should still be displayed to the terminal, and hence, you can use `System.err.println()` to output debugging information. This I/O redirection may also complicate running MyLZW from some IDEs. If you are having trouble running MyLZW from your IDE, please try to run your program from the command line. * Consider the notes in `LZW.java` (and `TST.java`) concerning the speed of the `substring()` function. In order to run your experiments faster, you may want to edit LZW.java (MyLZW.java) and TST.java to remove all calls to `substring()`. There is no penalty for continuing to use `substring()` for this assignment, but you will experience noticeably slow performance.## Grading Rubric: * Command line arguments are interpreted as specified: 10 * Variable width keywords (9-16 bits) working properly: 25 * Reset mode implemented and working properly: 20 * Monitor mode implemented and working properly: 20 * Results: * For unmodified `LZW.java`: 4 * For variable width codewords (`MyLZW.java`) with Do Nothing mode: 4 * For variable width codewords (`MyLZW.java`) with Reset mode: 4 * For variable width codewords (`MyLZW.java`) with Monitor mode: 4 * For an appropriate popular compression application: 4 * Assignment info sheet/submission: 5Goal: To explore an advanced application of priority queues in order to gain a deeper understanding of the data structure.## High-level description: You will be writing a basic application to help a user select a car to buy. You will write a menu-based user interface driver program (to be run in the terminal, no GUI), but most of the logic will be in implementing a priority queue-based data structure. You should write a PQ-based data structure that stores objects according to the relative priorities of two of their attributes, making it efficient to retrieve objects with the minimum value of either attribute. Your data structure should further be indexable to allow for efficient updates of entered items. You will want users to be able to enter details about cars that they are considering buying. The user should then be able to efficiently retrieve the car with the lowest mileage or lowest price. These retrievals should be possible on the set of all entered cars or on the set of all cars of a specific make and model (e.g., “lowest price Ford Fiesta”, “lowest mileage Cadillac Escalade”).## Specifications: 1. First you must create a class to store data about cars to buy Specifically, this class must contain the following information: * A unique VIN number (17 character string of numbers and capital letters (but no I (i), O (o), or Q (q) to avoid confusion with numerals 1 and 0) * The car’s make (e.g., Ford, Toyota, Honda) * The car’s model (e.g., Fiesta, Camry, Civic) * The price to purchase (in dollars) * The mileage of the car * The color of the car 1. You must write a terminal menu-based driver program (again, no GUI). Specifically, your driver must present the user with the following options: 1. Add a car * This will (one at a time) prompt the user for all of the above-listed attributes of a car to keep track of 1. Update a car * This option will prompt the user for the VIN number of a car to update, and then ask the user if they would like to update 1) the price of the car, 2) the mileage of the car, or 3) the color of the car 1. Remove a specific car from consideration * This option will prompt the user for the VIN number of a car to remove from the data structure (e.g., if it is no longer for sale) * Note that this mean you will need to support removal of cars other than the minimum (price or mileage) car 1. Retrieve the lowest price car 1. Retrieve the lowest mileage car 1. Retrieve the lowest price car by make and model * This option will prompt the user to enter (one at a time) a make and model and then return the car with the minimum price for that make and model 1. Retrieve the lowest mileage car by make and model * This option will prompt the user to enter (one at a time) a make and model and then return the car with the minimum mileage for that make and model 1. Retrieval operations should not remove the car with minimum price or mileage from the datastructure, just return information about that car. Cars should only be removed via the “remove a specific car from consideration” menu option. 1. To aid in the testing of your application, you will find an example file with some test data store in this repository (`cars.txt`). Your progam should read in the contents of this file to initialize your data structure each time it is run. You can assume that this file will already exist, and you do not need to write an updated version of the data sturcture back to the file. 1. To ensure efficiency of operations, you must base your data structure around the use of heaps with indirection (making them indexable). Note that operations on either attribute (e.g., retrieve minimum price, retrieve minimum mileage) should have a logarthmic runtime (both for all cars and for a specific make and model). Updates and removals should also have a logarithmic runtime. Take care in selecting your approach to the indirection data structure to account for the types of keys you will need to store and the type and number operations that you will need to perform on them. 1. Because this project requires you to make a number of decisions about how to implement its requirements, you will need to write a documentation file explaining your implementation, and justifying your decisions. Name this file `documentation.txt`. Be sure to describe your carefully document your approach to ease the effort required to trace through your code for grading. Be sure to include descriptions of the runtime and space requirements of your approach and use them in your justification of why you think your approach is the best way to go.## Submission Guidelines: * **DO NOT SUBMIT** any IDE package files. * You must name the primary driver for your program `CarTracker.java`. * You must be able to compile your game by running `javac CarTracker.java`. * You must be able to run your program with `java CarTracker`. * You must document and justify your approach in `documentation.txt`. * You must fill out `info_sheet.txt`. * Be sure to remember to push the latest copy of your code back to your GitHub repository before the the assignment is due. At the deadline, the repositories will automatically be copied for grading. Whatever is present in your GitHub repository at that time will be considered your submission for this assignment.## Additional Notes/Hints: * You are free to use code provided by the book authors in implementing your solution. It is up to you to decide if it would be easier to modify the provided code to meet the requirements of this project or if it would be easier to start with a clean slate with all of your own code. * Your program does not need to enforce that users enter properly formatted VIN numbers, but you must design your data structure to operate efficiently on VIN numbers as specified here. This should make testing your program much easier.## Grading Rubric: * Adding a car works properly: 10 * Updating a car works properly: 10 * Removing a car works properly: 15 * Retrieval for all cars works properly: 10 * Retrieval for a given make/model works properly: 15 * Operations on either attribute are efficient due to heap-backed data structure: 15 * Validity of justitifications: 15 * Menu-based driver program works properly and has appropriately labeled options: 5 * Assignment info sheet/submission: 5Goal: To gain a better understanding of graphs and graph algorithms through practical implementation.## High-level description: Your program will analyze a given graph representing a computer network according to several specified metrics. The vertices of these graphs will represent switches in the network, while the edges represent either fiber optic or copper cables run between the switches. Your program should operate entirely via a console interface menu (no GUI).## Specifications: 1. Your program should accept a single command line argument that specifies the name of a file containing a description of a graph. Two such files are provided (`network_data1.txt` and `network_data2.txt`). The format of these files is as follows: * The first line contains a single int stating the number of vertices in the graph. These vertices will be numbered 0 to v-1. * Each following line will describe a single edge in the graph, with each of the following data items listed separated by spaces. * First, two integers specify the endpoints of the edge. * Next, a string describes the type of cable that edge represents (either “optical” or “copper”). * Next, an integer states the bandwidth of the cable in megabits per second. * Finally, an integer states the length of the cable in meters. * E.g., the line `0 5 optical 10000 25` describes an edge between vertex 0 and vertex 5 that represents a 25 meter long optical cable with bandwidth of 10 gigabits per second. * You should assume that all cables are full duplex and hence represent connections in both directions (e.g., in the example above data can flow from vertex 0 to vertex 5 at 10 gigabits per second and from vertex 5 to vertex 0 at 10 gigabits per second simultaneously). 1. You must internally represent the graph as an adjacency list. 1. After loading the graph from the specified file, your program should present the user with a menu with the following options: 1. Find the __lowest latency path__ between any two points, and give the bandwidth available along that path. 1. First, your program should prompt the user for the two vertices that they wish to find the lowest latency path between. 1. Then, your program should output the edges that comprise this lowest latency path in order from the first user-specified vertex to the second. 1. You must find the path between these vertices that will require the least amount of time for a single data packet to travel. For this project, we will simply compute the time required to travel along a path through the graph as the sum of the times required to travel each edge, where the time to travel each edge is computed as the length of the cable represented by that edge divided by the speed at which data can be send along a connection of that type. * A single data packet can be sent along a copper cable at a speed of 230000000 meters per second. * A single data packet can be sent along a fiber optic cable at a speed of 200000000 meters per second. 1. Your program should also output the bandwidth that is available along the resulting path (minimum bandwidth of all edges in the path). 1. Determine whether or not the graph is __copper-only connected__, or whether it is connected considering only copper links (i.e., ignoring fiber optic cables). 1. Find the __lowest average latency spanning tree__ for the graph (i.e., a spanning tree with the lowest average latency per edge). 1. Determine whether or not the graph would remain connected if __any two vertices in the graph were to fail__. 1. Note that you are not prompting the users for two vertices that could fail, you will need to determine whether the failure of *any pair* of vertices would cause the graph to become disconnected. 1. Quit the program.## Submission Guidelines: * **DO NOT SUBMIT** any IDE package files. * You must name the primary driver for your program NetworkAnalysis.java. * You must be able to compile your program by running `javac NetworkAnalysis.java`. * You must be able to run your program with `java NetworkAnalysis data_filename.txt` (e.g., `java NetworkAnalysis network_data1.txt`). * You must fill out info_sheet.txt. * Be sure to remember to push the latest copy of your code back to your GitHub repository before the the assignment is due. At the deadline, the repositories will automatically be copied for grading. Whatever is present in your GitHub repository at that time will be considered your submission for this assignment.## Additional Notes/Hints: * Though code for the algorithms used in the assignment has been provided by the authors of your text book, note that use of this code will require extensive adaptations to account for the needs of this project. * The assumed calculation of network latency used here is a drastic simplification for this project. Interested students are encouraged to investigate a more detailed study of computer networks independently (recommended reading: _Computer Networks: A Systems Approach_ by Peterson and Davie).## Grading Rubric * Menu interface is user-friendly: 5 * Graph is properly read and represented: 5 * Queries: * Lowest latency path computation: 15 * Bandwidth correctly reported: 5 * Copper-only connectivity: 15 * Minimum average latency spanning tree: 20 * Surviving 2 vertex failures: 30 * Assignment info sheet/submission: 5Goal:To get hands on experience with algorithms to perform mathematical operations on large integers, using RSA as an example.Note that the result of this project should NEVER be used for any security applications. It is purely instructive. Always use trusted and tested crypto libraries.## High-level description: You will be writing two programs. The first will generate a 512-bit RSA keypair and store the public and private keys in files named `pubkey.rsa` and `privkey.rsa`, respectively. The second will generate and verify digital signatures using a SHA-256 hash. You will use Java’s [MessageDigest](https://docs.oracle.com/javase/8/docs/api/java/security/MessageDigest.html) class to complete this project. In order for either of these programs to work, however, you will need to complete an implementation of a class to process large integers.## Specifications: 1. You are provided with the start of a class to process large integers called LargeInteger. LargeIntegers are represented internally as [two’s-complement](https://en.wikipedia.org/wiki/Two%27s_complement) _raw integers_ using byte arrays (i.e., instances of `byte[]`). 1. Currently, LargeInteger has the following operations implemented: * A constructor to generate an n-bit random, positive, probably prime, integer using a specified source of randomness. This constructor uses a probabilistic primality test to ensure that it is probably prime (with 2^-100 chance of being composite). * A constructor that creates a new LargeInteger based off of a provided `byte[]`. * A method to compute the sum of two LargeIntegers. * A method to determine the negation of a LargeInteger. * A method to compute the difference of two LargeIntegers. * Several other helper methods. 1. Due to the use of a two’s complement representation of the integers, LargeIntegers should always have at least one leading 0 bit (indicating that the integer is positive) in their `byte[]` representation. This property may cause the array to be bigger than expected (e.g., a 1024-bit generated prime will be represented using a length 129 byte array). 1. LargeIntegers are also be represented using a _big-endian_ byte-order, so the most significant byte is at the 0th index of the `byte[]`. 1. In order to generate RSA keys and perform RSA encryptions and decryptions, you will further need to implement the following functions: * `LargeInteger multiply(LargeInteger other)` * `LargeInteger[] XGCD(LargeInteger other)` * `LargeInteger modularExp(LargeInteger y, LargeInteger n)` * Any additional helper functions that you deem necessary. 1. You may *not* use any calls the Java API class `java.math.BigInteger`, or any other JCL class in finishing LargeInteger. The probably-prime LargeInteger constructor does call BigInteger’s probablePrime method, however, this can be the only call to BigInteger in your LargeInteger code. 1. Once LargeInteger is complete, write a program named `RsaKeyGen` to generate a new RSA keypair. 1. To generate a keypair, follow the following steps, as described in lecture. 1. Pick p and q to be random primes of an appropriate size to generate a 512-bit key 1. Calculate n as p*q 1. Calculate φ(n) as (p-1)*(q-1) 1. Choose an e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (e must not share a factor with φ(n)) 1. Determine d such that d = e⁻¹ mod φ(n) 1. After generating e, d, and n, save e and n to `pubkey.rsa`, and d and n to `privkey.rsa`. 1. Once you have your RSA keys generated, write a second program named `RsaSign` to sign files and verify signatures. This program should accept two command-line arguments: a flag to specify whether to sign or verify (`s` or `v`), and the name of the file to sign/verify. 1. If called to sign (e.g., `java RsaSign s myfile.txt`) your program should: 1. Generate a SHA-256 hash of the contents of the specified file (e.g., `myfile.txt`). 1. “Decrypt” this hash value using the private key stored in `privkey.rsa` (i.e., raise the hash value to the dth power mod n). * Your program should exit and display an error if `privkey.rsa` is not found in the current directory. 1. Write out the signature to a file named as the original, with an extra `.sig` extension (e.g., `myfile.txt.sig`). 1. If called to verify (e.g., `java RsaSign v myfile.txt`) your program should: 1. Read the contents of the original file (e.g., `myfile.txt`). 1. Generate a SHA-256 hash of the contents of the original file. 1. Read the signed hash of the original file from the corresponding `.sig` file (e.g., `myfile.txt.sig`). * Your program should exit and display an error if the `.sig` file is not found in the current directory. 1. “encrypt” this value with the key from `pubkey.rsa` (i.e., raise it to the eth power mod n). * Your program should exit and display an error if `pubkey.rsa` is not found in the current directory. 1. Compare the hash value that was generated from `myfile.txt` to the one that was recovered from the signature. Print a message to the console indicating whether the signature is valid (i.e., whether the values are the same).## Submission Guidelines: * **DO NOT SUBMIT** any IDE package files. * You must name your key generation program `RsaKeyGen.java`, and your signing/verification program `RsaSign.java`. Thus: * You must be able to compile your program by running `javac RsaKeyGen.java` and `javac RsaSign.java`. * You must be able to run your key generation program by running `java RsaKeyGen`, and your signing/verification program with `java RsaSign s ` and `java RsaSign v `. * You must fill out `info_sheet.txt`. * Be sure to remember to push the latest copy of your code back to your GitHub repository before the the assignment is due. At the deadline, the repositories will automatically be copied for grading. Whatever is present in your GitHub repository at that time will be considered your submission for this assignment.## Additional Notes/Hints: * An example of using `java.security.MessageDigest` to generate the SHA-256 hash of a file is provided in `HashEx.java` * You may find the creation of `pubkey.rsa`, `privkey.rsa`, and signature files to be most easily accomplished through the use of `java.io.ObjectOutputStream`. The format of your key and signature files is up to you. * **NEVER USE CODE FROM THIS PROJECT IN PRODUCTION CODE.** This is purely instructive. Always use trusted and tested crypto libraries.## Grading Rubric * LargeInteger * `multiply` works properly: 20 * `XGCD` works properly: 25 * `modularExp`: 10 * Key generation * p and q are generated appropriately: 3 * n and φ(n) computed appropriately: 3 * e is selected appropriately: 4 * d is selected appropriately: 5 * Key files are generated appropriately: 5 * Signing * Hash is generated correctly: 2 * Hash is “decrypted” (signed) correctly: 5 * Signature file is generated appropriately: 3 * Verification * Hash is re-generated correctly: 2 * Signature is “encrypted” (verified) correctly: 5 * Signed files are appropriated verified: 3 * Assignment info sheet/submission: 5
The purpose of this project is for you to practice writing assembly language to interact with output/input hardware. The hardware for this project is a dollar store calculator as shown below (on left): The Calculator (Mars Tool) that we are going to use for this project is shown above (on right). This tool can be found in SimpleCalculatorRegister.zip located in the CourseWeb under this project. Extract all files to your [..]/mars4 5/mars/tools directory. If you extract all files to the right directory, when you run the MARS program, you should see ”Simple Calculator (Register) V0.1” under the ”Tools” menu. Introduction to the Simple Calculator (Mars Tool) The Simple Calculator (Mars Tool) consists of two parts, LCD display and a key pad. The LCD display is connected directly to the register $t8. It simply display the value of the register $t8 on the LCD screen. Thus, whatever number your program wants to show on the calculator’s LCD screen, simply put it in the register $t8. This display supports both positive and negative number. If the value stored in the register $t8 is a negative value, a minus symbol will be displayed before the value (e.g., -123). Note that there is no dot symbol (.) on the key pad. This Simple Calculator can only display integer numbers. For this project, we will focus only on integer operations. Thus, the division must be the integer division (e.g., 5 / 2 = 2). 1 There are 16 buttons on the key pad, 0 to 9, +, −, ∗, /, =, and C (clear). This key pad is connected directly to the register $t9. If the value of the register $t9 is currently equal to 0 and a button is pressed, the Most Significant Bit (MSB) of the register $t9 (bit 31) will be 1 and the last four bit of the register $t9 (bit 0 to bit 3) will be changed according to the pressed button as shown in Table 1. Note that these buttons are disabled if the content of the register $t9 is Button b3b2b1b0 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 + 1010 − 1011 ∗ 1100 / 1101 = 1110 C 1111 Table 1: Associated Values of Buttons not equal to 0. Thus, it is your responsibility to change the content of the register $t9 to 0 when your program is ready to get a new key pad input. Note that the Simple Calculator does not use syscall. Thus, there is no special instruction for your program to wait for an input from the key pad. Your program has to loop checking the value of the register $t9 until it is not zero. The non zero value will be the input. Again, do not forget that when an input exists, the MSB of the register $t9 will be 1 and the last four digits are used to represent a pressed button. What to Do? For this project, write a MIPS assembly program such that when the program is running, the Simple Calculator will behave just like a dollar store calculator. Note that there are various kind of dollar store calculators. They may behave differently. So, let’s follow the behavior as shown in Table 2. According to the Table 2, we assume that to calculate a result, we need three variables, two for operands and one for an operator. Let’s call these operand1, operand2, and operator, respectively. According to the Table 2, if a user press operator key more than one time consecutively, this calculator will use the last pressed operator key as the operator. For example, if user press the following key 5, *, -, 9, and =, (in that order) your calculator should show the result -4 because 5 – 9 = -4. As you may notice, because of this type of behavior, we cannot have a negative number as the second operand. For example, we a user wants to calculate 49 * (-52), the user has to calculate (-52) * 49 instead which can be achieve by the following series of key presses, C, -, 5, 2, *, 4, 9, and =. Note that when user press C, -, 5, and 2, the screen should show 52 because user is actually 2 calculating 0 – 52. Requirements The following are requirements that you must follow: • Your program should be named calculator.asm • Since the Simple Calculator (Mars Tool) uses registers $t8 and $t9, do not use these registers for any other purpose. • You can only use registers $s0 to $s7 and $t0 to $t9 in your program. • Do not use any system calls (syscall). Do not worry that your calculator will run indefinitely. • No functions in your program. In other words, do not use instructions jal and jr or stack pointer ($sp). You may already learn how to create a function in assembly language and feel tempted to do so. DON’T. • No memory reference instructions are allowed (no load and store instructions). • Your program should have only the text segment (.text) and no data segment (.data). • You are not allowed to use multiplication and division instructions. Simply use loop to achieve those type of calculations. • Try not to use pseudo instructions. This project can be done by using only add, addi, sll, srl, slt, beq, bne, and j instructions and a lot of labels. Note that this requirement is not a definite requirement. If you need to use other instructions, you are allowed to do so. The main reason why we should not use pseudo instruction is because we may use this program for your last project. If you use a lot of pseudo instructions or a complex instructions, you may have to rewrite your program for your last project. Hints • Focus on a small task at a time. For example: 1. Write the program to receive a numeric keypad and show the correct number of the LCD screen 2. Extend from 1 to support a series of numeric keypad (e.g., 5, 2, and 9 should result in 529 on the LCD screen). Note that multiply by 10 can be easily achieved by shift left three follows by adding with the original number twice. 3. Extend from 2 to support C (clear) button. 4. Practice writing multiplication and division. Submission The due date of this project is stated on the CourseWeb. Late submissions will not be accepted. You should submit the file calculator.asm via CourseWeb. 3 State Input Actions 0 N/A Set operand1 and operand2 to 0 (Start) Set operator to nothing Display operand1 Go to state 1 1 0 – 9 operand1 = (operand1 * 10) + Input Display operand1 Go back to State 1 +,−,∗,/ operator = Input Display operand1 Go to State 2 = result = operand1 Display result Go to State 4 C Go to State 0 2 0 – 9 operand2 = (operand2 * 10) + Input Display operand2 Go to State 3 +,−,∗,/ operator = Input Display operand1 Go back to State 2 = result = operand1 Display result Go to State 4 C Go to State 0 3 0 – 9 operand2 = (operand2 * 10) + Input Display operand2 Go back to State 3 +,−,∗,/ result = operand1 operator operand2 Display result operand1 = result operand2 = 0 operator = Input Go to State 2 = result = operand1 operator operand2 Display result operand2 = 0 Go to State 4 C Go to State 0 4 0 – 9 operand1 = Input Display operand1 Go to State 1 +,−,∗,/ operand1 = result operator = Input Go to State 2 = Display result Go back to State 4 C Go to State 0 Table 2: Behavior of a Dollar Store Calculator 4The purpose of this project is for you to practice writing assembly language to interact with output/input hardware. The hardware for this project is a game called Simon (on left): The Simon (Mars Tool) that we are going to use for this project is shown above (on right). This tool can be found in simon.zip located in the CourseWeb under this project. Extract all files to your [..]/mars4 5/mars/tools directory. If you extract all files to the right directory, when you run the MARS program, you should see ”Simon (Register) V0.1” under the ”Tools” menu. Introduction to the Simon Game Simon is a classic game from the 70’. See https://en.wikipedia.org/wiki/Simon (game) for more detail. During the game play, the computer will play a sequence of tone and lit a button associated to each tone. Each round, a player has to play the sequence back by pressing a series of buttons. The length of the sequence starts at 1 at round 1 and increases by 1 for every round. At n th round where n ≥ 2, The computer will play a sequence of length n where the first n − 1 tones are exactly the same as the sequence at round n − 1 and the n th tone is a new one (randomly pick a new one). The game is over when a player plays a wrong sequence. Introduction to the Simon (Mars Tool) The Simple Calculator (Mars Tool) consists of four colored buttons and one start game button. These buttons are connected directly to the register $t9. If the value stored in the register $t9 is 1 currently 0, when a button is pressed, the value of the register $t9 will be changed according to the pressed button as shown below: Button Value of $t9 Blue 1 Yellow 2 Green 4 Red 8 Start Game 16 Note that if the content of the register $t9 is not equal to 0, these buttons are disabled. Thus, it is the programmer responsible to change the content of the register $t9 to 0 when the program is ready to accept the next input. For this Simon (Mars Tool), the hardware is simply an input device. It is the program responsibility to tell the hardware to light a button and play sound, play starting sound, and play game over sound. A command can be sent to the Simon game by simply change the value of the register $t8 from 0 to a specific value as shown below: Value of $t8 Command 1 light the blue button and play its associated tone 2 light the yellow button and play its associated tone 4 light the green button and play its associated tone 8 light the red button and play its associated tone 15 play the game over tone, light all colored button three times, and enable the Start Game button 16 disable the Start Game button and play starting sound Note that after the Simon game receives a command, it may take some time to process. After a received command has been processed, the Simon game will change the content of the register $t8 to 0. Thus, it is the programmer responsibility to wait until the content of the register $t8 is changed to 0 before sending the next command. What to Do? For this project, write a MIPS assembly program named simon.asm such that when the program is running, the Simon game will behave just like an actual Simon game hardware. Note that when a player plays a wrong sequence, the Simon game should play the game over tone, light all colored button three times, and enable the ”Start Game” button for the next player without restarting the program. Requirements 1. Since registers $t8 and $t9 are used for sending command and receiving button input, do not use these registers for any other purpose. 2. Your program must consist of at least two functions as follows: • playSequence: This function, when called, it will play a sequence of tones. 2 • userPlay: This function lets user play back the sequence. Note that this function should return a value to notify the caller whether user successfully play back the sequence or not. 3. You are allowed to have more functions. 4. Everything that a function needs should be passed as arguments. 5. Everything that a caller needs from a function must be passed as return values. 6. Every functions must follow the calling convention discussed in class. Submission The due date of this project is on the CourseWeb. Late submissions will not be accepted. You should submit the file simon.asm via CourseWeb.The purpose of this project is for you to practice writing backtracking with recursion in assembly language. The main goal of your program is to solve a Sudoku puzzle. The Sudoku (Mars Tool) that we are going to use for this project is shown below. This tool can be found in sudoku.zip located in the CourseWeb under this project. Extract all files to your [..]/mars4 5/mars/tools directory. If you extract all files to the right directory, when you run the MARS program, you should see ”Sudoku (Memory) V0.1” under the ”Tools” menu. Introduction to the Sudoku Puzzle (from Wikipedia) Sudoku (originally called Number Place), is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called “boxes”, “blocks”, “regions”, or “subsquares”) contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a whell-posed puzzle has a unique solution. Completed games are always a type of Latin square with an additional constraint on the contents of individual regions. For example, the same single integer may not appear twice in the same row, column, or any of the nine 3×3 subregions of the 9×9 playing board. Visit https://en.wikipedia.org/wiki/Sudoku for more information about Sudoku. 1 Introduction to the Sudoku (Mars Tool) Sudoku (Mars Tool) will fill the main memory byte-by-byte starting at the address 0xFFFF8000 with puzzle. If a square is blank, the associated memory location will be filled with 0. For example, the content of the main memory starting at the address 0xFFFF8000 associated with the puzzle shown above is as follows: Address Content row column 0xFFFF8000 0 0 0 0xFFFF8001 0 0 1 0xFFFF8002 0 0 2 0xFFFF8003 0 0 3 0xFFFF8004 0 0 4 0xFFFF8005 0 0 5 0xFFFF8006 0 0 6 0xFFFF8007 0 0 7 0xFFFF8008 0 0 8 0xFFFF8009 0 1 0 0xFFFF800A 5 1 1 0xFFFF800B 8 1 2 0xFFFF800C 0 1 3 . . . . . . . . . . . . IMPORTANT: Since the Sudoku (Mars Tool) needs to update memory contents, after you successfully assemble your program, you must press either the “Reset” or “New Puzzle” button before your run your program. This will allow the Sudoku (Mars Tool) to write data into your memory. The “Reset” button will clear the puzzle without changing the puzzle and update contents of the main memory. Similar to the “Reset” button, the “New Puzzle” button will create a new puzzle and update contents of the main memory. Note that each puzzle generated by the Sudoku (Mars Tool) will have exactly one solution. Your program MAY NOT modify contents of the memory that contain the original digits. In the above example, you are not allowed to modify contents at memory locations 0xFFFF8009, 0xFFFF800A, 0xFFFF800C, and so on. The “Check” button can be used to verify your solution. If a square contains an invalid digit, the digit will turn red. Otherwise, it will turn green. If a square of the original puzzle that contain a digit has been modified, it will turn red as well. The figure below shows the result of pressing the “Check” button when the puzzle is being solved correctly. 2 What to Do? For this project, write a MIPS assembly program named sudokuSolver.asm to solve a Sudoku puzzle. Your program must perform the following: 1. Your program must display the puzzle on the console screen of MARS. For example, for the puzzle shown on the first page, your console screen should display the following: 000000000 058020039 304008020 000907003 002010400 600302000 040200906 780090340 000000000 This step simply check that your program can read a given puzzle correctly. This part will be your partial credit in case your program cannot solve a puzzle. 2. Your program must solve the Sudoku puzzle by changing contents of main memory starting at the address 0xFFFF8000. If a data stored in a memory location is not zero, do not modify the content of that memory location since it is a part of the puzzle. If a data stored in a memory location is zero, you must change it to a non-zero value (1 – 9). Again, make sure you follow all rules of Sudoku. Once the puzzle is solved, your program should simply terminate. After your program is terminated, you should click the “Check” button to verify that the puzzle is solved correctly. 3 Recursion and Backtracking for Sudoku An idea of using recursion and backtracking to solve a Sudoku puzzle is to associate a recursive call with a cell in Sudoku. For example, suppose your solveSudoku function looks like the following: boolean _solveSudoku(int row, int column) { : } When solveSudoku(r, c) is called, this call is responsible for filling the cell at row r column c. Once it finds a number that has no conflict, it should make a recursive call to solveSudoku(r, c + 1) so that the next call will take care of row r, column c + 1. Now, consider a recursive call solveSudoku(r, c). At this call, if the cell at row r column c is available, this call has 9 possible numbers (1 – 9) to put into this row r column c. This call will pick the first number that does not have any conflict (row, column, and 3 by 3) and put it into the cell. Note that this number (choice) may or may not lead to the correct solution. If the select (no conflict) number does not lead to the solution, this call have to pick the next no conflict number. However, if this call runs out of a choice of numbers. This mean that the choice picked by the previous call does not work. So, this call have to send a signal to previous call (a return value) to tell the previous call to pick a new number. But importantly, this call should set the row r column c back to its original value (0) before returning back to the previous call. Note that some cells may already have numbers. If that is the case, the recursive calls responsible to those cells do not have to do anything. Simply call the next one. Suppose the first row is the row number 0 and the first column is the column number 0, the next page shows a pseudo code that solve a Sudoku puzzle using backtracking and recursion. Requirements 1. Your program MUST use backtracking and recursion to solve puzzles. 2. Your program must contain the function named solveSodoku. This will be your recursive function. 3. You can create as many helper function as you wish. For simplicity, at least you should have the following three helper functions: • checkRow: This function checks whether a given number is already in a give row. • checkColumn: This function checks whether a given number is already in a given column. • checkSubgrid: This function checks whether a given number is already in a subgrid where a given row and a given column is located. 4. All functions in your program must follow all calling conventions discussed in class. Submission The due date of this project is on the CourseWeb. Late submissions will not be accepted. You should submit the file sudokuSolver.asm via CourseWeb. 4 boolean _solveSudoku(r, c) { boolean p; if(r == 8 and c == 9) return true; if(c == 9) { r = r + 1; c = 0; } if(data at row r column c is not 0) return _solveSudoku(r, c + 1); else { for i = 1 to 9 { if(i has no conflict) { put i into the cell at row r column c; p = _solveSudoku(r, c + 1); if(p) return true; } } put 0 back to the cell at row r column c return false; } } Pseudo CodeThe purpose of this project is for you to build 16-bit multiplication and 16-bit division hardwares as we discussed in class in logisim. Introduction to the Multiplication Hardware The 16-bit multiplication hardware that we discussed in class is shown below: M_Ready Product 32 Multiplier 1 Multiplicant Mul 16 16 1 Clock Multiplication Hardware You can consider the above circuit as a sub-circuit named multiplication which contains the following input/output: • Multiplicand: a 16-bit input • Multiplier: a 16-bit input • Mul (1-bit input): This input will be one if the instruction is the multiplication instruction • Clock (1-bit input) • Product (32-bit output) • M Ready (1-bit output): This output will be 1 if the product is ready Note that we require to have the output M Ready because the multiplication instruction will take multiple clock cycles to produce a result. Ideally, if a CPU see the instruction mul, it will set the appropriate Multiplicant and Multiplier. Then, it will set Mul to 1 and wait until the signal M Ready to turn to 1 before it continues to the next instruction. The circuit inside will be the same as the multiplication hardware discussed in class as shown below: Multiplicand Shift left Product Write Control test Shift right Multiplier 32 bits 16 bits 32−bit Adder 32 bits 1 Inside the multiplication hardware, you need three registers, Multiplicand (32-bit), Multiplier (16-bit), and Product (32-bit). For these registers, you do not have build them from scratch. Simply use the register component under “Memory”. Similarly, for the 32-bit adder, simply use the one supplied by the logisim. Note that the above hardware is for multiplying two 16-bit numbers and produce a 32-bit result. The flowchart of this hardware is shown below: Start Multiplier0 1. Test 1a. Add multiplicand to product and place the result in Product register 2. Shift the Multiplicand register left 1 bit 3. Shift the Multiplier register right 1 bit Done Multiplier0 = 1 Multiplier0 = 0 No: < 16 repetitions Yes: 16 recetitions 16nd rep? Recall that in the first step, this hardware have to load the top 16-bit of the multiplicand register with 0s and the bottom 16-bit with Multiplicand, load the product register with 0s, and load the multiplier register with the Multiplier. After all three registers are loaded with proper values, then the algorithm can start as follows. 1. product = product + (multiplicand ∗ multiplier0 ): In this step, if multiplier0 is 0, we actually perform product = product + 0. But if multiplier0 is 1, we perform product = product + multiplicand. This can be done by adding a 32-bit (2-input) multiplexer. This multiplexer has two inputs, one from the multiplicand and another one is imply a 32-bit constant 0. Simply use the Least Significant Bit (LSB) of the multiplier register (multiplier0 ) to choose which one to go to the output as shown below: Multiplicand Product u x m 0 multiplier0 Note that before the algorithm starts, you must clear the product register which can be done in two ways: 2 (a) by writing 0. So, you also need another multiplexer to choose whether you want to write 0 or output from 32-bit adder to the product register as shown below: Multiplicand u x m u x m Product 0 multiplier0 0 Clear Product (b) use the Clear input pin of the register. Simply set it to 1 and the content will be cleared. 2. Shift multiplicand register left one bit: This step is simply update the multiplicand register by its data that has been shifted left by 1. Simply use a Shifter provided by logisim under Arithmetic. Note at the first step before the algorithm starts, you need to update multiplicand register by the input Multiplicand. So, you need a multiplexer to select which data should go to the multiplicand register (Multiplicand input or multiplicand > 1 Note that we need an ability to control what to do at each clock cycle. For example, in the first clock cycle, we need to load contents of all registers. The next clock cycle, we need to perform product = product + (multiplicand ∗ multiplier0 ). The third clock cycle, we need to perform multiplicand = multiplicand > 2, and so on. To be able to control each clock cycle, we will use a combination of counter and Read Only Memory (ROM) as shown below: Clock Mul Counter ROM M Ready When Mul is 1, it will clear the Counter to 0. At the same time, it will allow the clock signal to go to the Counter. So, the Counter will start counting up until its desired maximum value which can be set. When it reaches its maximum value, its Carry signal will be 1 which can be used for 3 the signal M Ready. The output of the Counter will be use as the address of a ROM. The content of the ROM will be control signal for each clock cycle. In other words, you can program what do you want to do at each clock cycle by content of the ROM. Note that you MUST set the maximum value of the counter to stay at a specific value based on the number of clock cycles that your hardware uses. MAKE SURE that the last output value of the ROM should maintain the output of your product register. When we grade your circuit, we will simply put value of multiplicand and multiplier, and let the clock tick until M Ready turn green without stopping the clock and check the result. Introduction to the Division Hardware The 16-bit division hardware that we discussed in class is shown below: 16 16 1 Clock Hardware Divisor Dividend Quotient 1 16 16 Remainder D Ready Division Div You can consider the above circuit as a sub-circuit named division which contains the following input/output: • Dividend: a 16-bit input • Divisor: a 16-bit input • Div (1-bit input): This input will be one if the instruction is the division instruction • Clock (1-bit input) • Quotient (16-bit output) • Remainder (16-bit output) • D Ready (1-bit output): This output will be 1 if the product is ready The division hardware that we discussed in class is shown below: Control test 32 bits 32 bits 16 bits Quotient Divisor Write Remainder Shift right Shift left 32−bit Adder Again, the above hardware is for dividing two 16-bit numbers and produce a 16-bit quotient and 16-bit remainder. The flowchart of this hardware is shown below: 4 Start 1. Subtract the Divisor register from the Remainder register and place the result in the Remainder register Remainder Test 2b. Restore the original value by adding the Divisor register to the Remainder register and placing the sum in the Remainder register. Also shift the Quotient register to the left, setting the new least significant bit to 0 3. Shift the Divisor register right 1 bit Done 2a. Shift the Quotient register to the left, setting the new least significant bit 1 Remainder >= 0 Remainder < 0 No: < 17 repetitions Yes: 17 repetitions 17rd repetition? The design concept of this division circuit will be pretty much the same as in multiplication circuit but it requires more steps. For example, when the subtraction result is less than 0, you have to restore to its original value by adding it back. Another different is the quotient, sometime we shift it left and insert a 0 but sometime we insert a 1. What to Do? For this project, start with the given starter file named muldiv.circ. This starter file contains two sub-circuits, 16-bit multiplication and 16-bit division. In both sub-circuit, the counter and ROM are provided. Simply build your multiplication and division circuits there. Once you are finish, put your circuits in the main and connect them with appropriate input/output. We will test your circuit from the main circuit. Again, you MUST set the maximum value of the counter to stay at a specific value based on the number of clock cycles that each of your hardwares use. We will not stop the clock when we check your results. Submission The due date of this project is stated in the CourseWeb under this project. Late submissions will not be accepted. You should submit the file muldiv.circ via CourseWeb.
Instructions: Create a subdirectory named “hw1” in your cs410 directory. Use that subdirectory for your files submission on this assignment. You will create the following two files in your hw1 directory: 1. a single C++ compilable file containing a program written in C++ named “hw1.cpp” 2. a “typescript” file demonstating program compilation, execution and testing. Use the commands below at the UNIX prompt to generate the typescript file: script command to start a typescript. ls -l to list files in your directory and write date/time cat hw1.cpp to print out solution file g++ -o hw1 hw1.cpp to compile program ./hw1 to execute program with test input (provided on last page) exit command to end typescript file Background: Hans Moleman needs a new pair of glasses. He’s going to try out a new optometrist in town, a Dr. Riviera. He has been involved in “cutting edge” (see pic) research (see other pic) which is why he has changed residences and started a new practice in optometry. But I digress. Dr. Nick has developed a new formula for determining the grinding thickness for lenseseses. Your program is going to do that computation. Roughly speaking, the thickness of the lenses (both the same for right and left, since Dr. Nick believes in simplicity) is dependent on both left and right visual acuity, some cliometric1 constants, and the patient’s social security number. The formula is given below 2 1 5 VA VA L thickness K IAF R K where: thickness is an integer value in cm (centimeters), LVA is left visual acuity, a positive integer, RVA is right visual acuity, a positive integer, K1 is the index of refraction constant that Dr. Nick has discovered empirically. It’s value is the constant integer value 2, K2 is the Nick Needs Money constant which ensures Dr. Nick a minimum income from each customer; currently it is 4.2, and IAF is the insurance adjustment factor IAF is the sum of the last two digits of the patient’s soc sec number. This factor is added into the thickness computation ONLY IF the patient has insurance. Why? Well, it screws up the prescription and then they have to come back to Dr. Nick for another diagnosis and more new lenses. Hence, Nick can bill the insurance companies for more money.1 We have no idea what this word means. It sounds cool and impressive, and it boosts our esteem to use it; we come off as really smart now. Don’t look it up. Specifications: Your program is to prompt the user for: Left visual acuity (LVA) and right visual acuity (RVA), both entered as integers, The last 4 digits of the patient’s social security number (this is entered as a single 4-digit integer), and Whether the patient has insurance (1 for yes) or not (0 for no). The value be read into a boolean type variable. Note: The thickness value computed should always be rounded down to the nearest integer value. You are not allowed to use conditional statements (if or if-else) in the program. Think carefully how to use the information you have input from the user, how it is stored, how boolean variables are represented. It is up to you how you want to name your variables and constants. Your program should be “user friendly” in that it should have an opening statement or greeting, user friendly and understandable prompts, and clear and concise outputs and sign-off. Here’s a good example of bad output: Hello 34 12 3456 0 22 Notice that there are NO prompts to speak of, and the output is completely unexplained. This is horrible output. Something like the following is much much better: You are using the LENS-O-MATIC program enter: left visual acuity: 34 right visual acuity: 12 ssn: 3456 ins? 0 thickness of lens: 23 cm Good luck with those glasses! And come back to see Dr. Nick ! When you submit: When you submit, you will have to enter inputs as a user of the program. Now, in order to make the output uniform for the grader and to keep them sane, ALL OF YOU will enter the same information. For this assignment, it is: left visual acuity: 20 right visual acuity: 30 last 4 of soc sec: 4567 yes for ins coverage If you have any questions about this assignment, be sure to ask your TAs or instructor.Background: After getting the right thickness of his lenses, Hans Moleman decided to become an orthopedist. To clarify, that’s a person who treat issues affecting the bones, muscles, tendons, and ligaments. He seems to have had a history of muscle cramps and pain. Towards this end, he has been doing some of his own home-grown research, writing up results of exquisite and intricate experiments on how muscular-aches occur and are mitigated or treated. For the benefit of the general public, he has published a flow chart on how one might treat or react to bone and muscular issues. His flow chart is shown on the next page. You’ll notice that, as you follow the flow in this chart (this flow chart), you eventually end up with either a recommendation or some kind of medical commentary that might help you out in the near future. Some of it is just simplistic babble, but the user might still find some value in it. Specifications: You are to write a program that implements this flowchart. Briefly, your program will prompt for and input information about the user (the sick person) and use the responses to lead to one of the “diagnostic messages” Hans has crafted. Of course, you are to do this right. Here are some requirements: You are to use if and if-else statements for decision branching. You are NOT allowed to use the switch-case statement. You are NOT to us the goto, the break, or the continue statements. You are to use logic and logically structured code to implement. Your program should greet the user and prompt for and read in their name (first name only. Assume the name is a contiguous string of non-whitespace characters). Your code should then use that name, in at least one prompt, for info after that and in the final output/diagnosis/recommendation. Your program should do what we call “input cleansing” or range checking. That is, when you prompt for information that can be validated for value, your code should do that. For example, in many of the prompts you will have, you will ask for a response of yes or no (y/n). If you input the response as a char, you can then check to see if they indeed entered ‘y’ or ‘n’ and re-prompt them if not. At the end of the execution of a “run” of this stress inquiry, your program should ask the user if they wish to start again – ostensibly for someone else. In any case, the whole line of questioning and diagnosis should repeat until no one else has muscular problems. 2 When you submit: When you run your program, use the following responses to questions as indicated by the flowchart: yes, no, no, no, no, no, no, yes enter a “yes” response to evaluate another problem answer no to all questions again, enter a “yes” response to evaluate another problem no, yes, no, yes enter a “no” response to exit the program As usual, if you have any questions about this assignment, be sure to ask your TAs or instructor. Hans MolemanInstructions: Create a subdirectory named “hw3” in your cs410 directory. Use that subdirectory for your all file submissions on this assignment. At the end of the homework assignment, these two files should be found in your hw3 directory: 1. a single C++ compilable file containing a program written in C++ named “hw3.cpp” 2. a “typescript” file demonstating program compilation, execution and testing. Use the commands below at the UNIX prompt to generate the typescript file: script command to start a typescript. ls -l to list files in your directory and write date/time cat hw3.cpp to print out solution file g++ -o hw3 hw3.cpp to compile program ./hw3 to execute program exit command to end typescript file Background: Poor Hans. For most of us, life is a trial-live one day at a time and we usually do pretty well with minimal effort. However, for Hans Moleman, life is really tough. Being nearly blind, he has a hard time seeing, something most of us take for granted. Nevertheless, he got new lenses for his glasses and that should have solved his problem. But, alas, he got the lenses at the new super store in Springfield, GalMart, which employs a Dr. Riviera who uses some ridiculous, crazy new formula for computing lens thickness. Now he can hardly see what he’s doing or where he’s going with his glasses on. SO, he needs to get back to Dr. Nick’s to have his sight re-evaluated and new lenses made. The office is 1414 feet from his house. He cannot drive in his current condition, and he’s scared to death of buses, so he’s going to walk. The thing is, Hans may or may not make it to his intended destination! Three possibilities exist: 1) he makes it to the doctor’s office; 2) he ends up back home; and 3) after a long time, he’s so far away that he is picked up by the local police and taken to a homeless shelter. You’re going to write a program that will simulate his walk across town. In fact, your program will generate 250 possible walks and gather statistics on the results. Specifications: Your program will simulate 250 walks. A “walk” begins at home and proceeds from decision point to decision point until the walk terminates. Termination happens when a decision point is: within 500 feet of Dr. Nick’s office within 50 feet of home and there are at least 5 other decision points preceding this point the 400th decision point The first of the above conditions implies that he is close enough to his intended destination to be able to see that he has arrived. The second implies that he has been walking for a while and hasn’t actually gone anywhere, so he just gives up and goes back inside and watches re-runs of the Simpsons! DOH! The third simulates a lost old man wandering off into the horizon never to return. Details: At each decision point, he will almost always turn right. This is because his eye-sight is so screwed up that his vision “pulls” him in that direction. However, every 7th decision point he turns left. Also, for the first walk, he will walk 20 feet away from his house to his first decision point. On the second walk, he walks 21 ft before the first decision point (note this is NOT the second step of the first walk), etc…Each first decision point is 1 foot further from the house than the previous one. You can choose the direction of this first move, but be consistent from walk to walk, starting in the same direction. And, the distance he walks after each decision point is given by: 0 20 1 , 21 2 , st nd d initial number of feet from the house for walk f or walk etc 1 124985 1367892 1654872235 300 21, 1 , 2, 3, … i i d d mod mod i If you are unfamiliar with an iterative formula like this, this is how it works. The first distance walked (as stated above) is 20 ft. You’ll substitute this into the second equation above to compute the 2nd distance, d2. Then substitute d2 into the equation to compute d3. Continue in this way. For his second walk, you’d start with first distance walked being 21. The output from your program should be a listing of the instances when he either goes nowhere (ends up at home) or finds his way to Nick’s office, and how many feet he traveled to get either of those two places. And, if the distance walked is greater than a mile, output that distance in miles. After that, output the percentages of times he got to Nick’s, ended up at home, and got lost in the ozone. Part of my output looks like this: Ended walk at total dist traveled (ft) Nick’s 17709 (~ 3.35398 miles) home 9493 (~ 1.79792 miles) Nick’s 17663 (~ 3.34527 miles) home 7803 (~ 1.47784 miles) home 2161 home 2742 Nick’s 18774 (~ 3.55568 miles) home 9804 (~ 1.85682 miles) home 15501 (~ 2.9358 miles) Nick’s 11444 (~ 2.16742 miles) Nick’s 17673 (~ 3.34716 miles) Also: In order to code this problem, I’d suggest you establish a coordinate system for the location of Hans, the doctor’s office and Hans’s home. Since Hans starts his walks at home, put home at (0, 0). Since Nick’s office is 1414 feet (straight line) away, put it at (1000, 1000). You can work out the rest from there. In order to compute the distance from one point to another, you will need to use the sqrt() function. It is contained in the library . Just #include it like you do the iostream library. This function will return a float type and you will need to put what you wish to find the square root of inside the parentheses. When you submit: Just submit, since there is no input from the user. And, as always, let your TAs or instructor know if you need any help.Instructions: Create a subdirectory named “hw4” in your cs410 directory. Use that subdirectory for your all file submissions on this assignment. At the end of the homework assignment, these two files should be found in your hw4 directory: 1. a single C++ compilable file containing a program written in C++ named “hw4.cpp” 2. a “typescript” file demonstating program compilation, execution and testing. Use the commands below at the UNIX prompt to generate the typescript file: script command to start a typescript. ls -l to list files in your directory and write date/time cat hw4.cpp to print out solution file g++ -o hw4 hw4.cpp to compile program ./hw4 to execute program exit command to end typescript file Background: In this assignment, you are going to write a menu driven program to help Hans out with his “health management issues”. Yep, indeed, it’s no longer enough to just take care of yourself by eating right and getting enough exercise. You had better spend a lot of money, have a personal health trainer, a membership to a gym, take way too many pills and subscribe to every hair-brained self-help scheme alive. But I digress. This program will present the user with several options concerned with improving health in varied manners. The user will choose an option, following instructions about prompted information, receive the intended recommendation, and then have the menu presented to them once again. Of course, the user can quit at any point. Your code will be implemented using functions. Now you will have your practice with them. Specifications: You are to use functions in the program. In fact, below is a description of the functions we want you to use. Your program will present a greeting and menu of options to the user. It should look something like this: Health-o-Matic Options —————————- 1. Taking a Walk! 2. Your Medications 3. Nap Time!! 4. Caloric Intake 5. Quit 1. When the user chooses option 1, the program should prompt for and read in the number of “legs” of the walk the user wishes to have. The total number of steps from the “legs” should be computed and displayed. 2. Option 2 chosen will trigger prompts for the user to input their current anxiety level (1 -> 10) and the day of the week (1 -> 7). From this information, the program will compute and output the number of pills the user should take that day. 3. If option 3 is chosen, your program is to refuse to do anything if both options 1 and 2 haven’t yet been chosen during that run of the program. That is because the computations for option 3 require the information from options 1 and 2. Now, if options 1 and 2 have indeed been chosen, then your program code for option 3 starts by prompting the user for the number of hours they slept the previous night. This information, along with the computed values from options 1 and 2, will be used to compute and output the number of minutes you may nap for. 4. Choosing option 4 will initiate prompts for body weight, body height, and room temperature. From this, the code should compute and output caloric intake allowable at that moment. 5. Choosing quit will terminate the program….of course. Details: First, you are required to use the switch statement for handling the options chosen from the menu. Secondly, you will use functions for the program and they are laid out here: 1. A function that does nothing more than displaying the greeting for the program. It should have no parameters and return nothing. 2. A function to display the menu and reads in a response (character) from the user and returns it to the main function. It should NOT “input cleanse”; any response from the user should be handled by the switch in main. 3. A function that will prompt for and read in a positive integer for the number of legs of the walk. This (cleansed) value is returned to the calling function (presumably main). 4. A function to which you pass the value returned by the preceding function, and it will output the total number of steps according to: total number of steps number of legs ! e.g. if number of legs is 4, then total number of steps = 4! = 4*3*2*1=24 steps. 5. A function that prompts for and reads in anxiety level (valid input is 1 -> 10) and returns it. 6. A function that prompts for and reads in the day (valid input is 1 -> 7) and returns it. 7. A function to which you pass the two values above (anxiety and day) and it returns the number of pills the user should take according to: number of pills anxiety day if this is non negati – , ; 0 . ve otherwise 8. A function to which you pass the number of pills and it will output it to the screen. 9. A function that prompts for and reads in the number of hours slept the previous night. 10. A function to which you pass the number of hours slept, the distance walked (i.e. total number of steps) as determined by option 1, and the number of pills as determined by option 2. It will return the number of minutes for a nap according to: 0, 1 dist walked minutes hrs slept number of pills if divide by 11. A function to output the number of minutes for a nap. It will have one parameter. 12. A function which prompts for and reads in the user’s weight, height, and room temp (along with the distance walked), then computes and returns calories according to the formula 1 cals wt ht dist walked 6 2 . temp 13. A function to which you pass the value from #12 above and it will output it. For the foregoing functions, if they are to prompt and input values, they should “cleanse input” with reasonable limits. For example, prompting for a weight should reject responses that are non-positive and those over 800lbs. When you submit: As usual, when you submit, you are all to enter the same information so as not to drive the graders crazy. Following these steps: choose option 3 (better get an error message!) choose option 4 (get an error message) choose option 1 and enter 6 (6 legs for the walk) choose option 3 (again, error!) choose option 2 and enter anxiety of 3 and day 5 choose option 3 and enter 5 hrs sleep choose option 4 and enter 250 lbs, 72 inches, and 79.7 F. quit And, as always, let your TAs or instructor know if you need any help.Background: Our friend Hans Moleman has been through a series of health problems these past weeks. Interestingly, he believes he has paid more on his bills than he should have. He feels very vulnerable with his finances because he is very bad at math. Now he wants to improve his math skills, so you are going to write a program that will help him check his work. He will be manually computing values for exponentials, trig functions, and roots of numbers. So he needs a “calculator” of sorts so he can check his answers. Specifications: Your program will begin by presenting a menu with these choices: OPTIONS ———— 1. Factorial of x 2. Exponential of x 3. Cosine of x 4. Roots of x 5. Hyperbolic sine of x 6. Quit In fact, your program should present this menu until the user chooses the quit option. You are to “function-ize” the code as much as practicable. That is, you will create functions to do much of the work, and your main will call functions, and they will call functions….and maybe even they will call functions. The idea is to make your code easier to use and read. Do not use the cmath library. When option #1 is chosen, offer to compute the factorial of any input. Prompt for the input (should only allow non-negative input less than or equal to 10) When option #2 is chosen, you will prompt for any value of x for calculating ex . You will use the formula “pattern” given in hw 4: e x = 1 + x + x2 /2 + x3 /6 + x4 /24 + x5 /120 + … = x 0 /0! + x1 /1! + x2 /2! + x3 /3! + x4 /4! + x5 /5! + x 6 /6! + … (Note: 0! = 1) The number of terms used in this calculation is 8. But that should be changeable to any positive integer at a moment’s notice! (In other words, you’d better use loop(s) for this computation.) When option #3 is chosen, the user is to be prompted for the value of x (any real value) for which to compute the cos(x). But then, they are to next be prompted for a positive integer between and including 1 and 5 representing the accuracy of the computation. This value will determine the number of terms to be included in the truncated Taylor series which calculates an approximation to the cos(x). This is that formula: cos(x) = 1 – x 2 /2! + x4 /4! – x 6 /6! + x 8 /8! … + x2k/(2k)! k = 1, 2, 3, … Thus, if one wants 2 terms, that corresponds to k = 2 in this formula and cos(x) = 1 – x 2 /2! Of course, it’s not really equal (=), but we’ll pretend. By the way, the larger k is, the better the approximation is. And if you add on terms forever, the equality is indeed guaranteed. Try it! It’s definitely worth the time. Note: k! is “k factorial” is k * (k-1) * (k-2) * … * 3 * 2 * 1 (e.g. 4! = 4*3*2 *1 = 24). And, of course, output the value. When option #4 is chosen, you will prompt for the value, x, to find the root of. But then you will prompt for which root to find: square root (n = 2), cube root (n = 3), fourth root (n = 4), or fifth root (n = 5). The formulas for the nth root calculations is written below. the kth root of A is given by this iterative formula: xn+1 = [(k-1)*xn + A/xn (k-1)] / k Use A as your first (initial) value for the root, x0. Output the designated root and return to the main menu. (If the user wants another root, they have to pick option 4 again.) Use 100 iterations for the computation. When option #5 is chosen, you are to compute the hyperbolic sine of a value, sinh(x). Here’s the formula: sinh(x) = (ex – e -x )/2 You can compute this using the exponential function from option 2. Thoughts: For this assignment, you are to use the switch-case statement to branch to the various choices for the first menu. You are forbidden to use (which is the same as ) for this assignment! You should double for a computational type. The numbers for these calculations can get big, so you will need precision on your side. Don’t make a do_everything function. Some people do this: int main() { do_everything(); return 0; } This is nothing more than renaming main; it accomplishes nothing. Leave something in main….perhaps your switch. When you submit: As usual, when you submit, you are all to enter the same information so as not to drive the graders crazy. Following these steps: option 1 x = 5 option 3 x = 1 using 8 terms option 4 x = 60 find the fifth root option 4 again for x = 729 find the 3rd root option 5 x = 2 option 2 x = 4 quit And, as always, let your TAs or instructor know if you need any help.Background: After weeks of stress, Hans Moleman is taking a vacation to Atlantis. But now, the Atlantians (those wierdos living in Atlantis) have made it so that he can’t leave to go back to home unless he jumps through the right hoops. Those “hoops” are that he first visits with enough of the inhabitants (weirdos) to satisfy the Atlantis Visitors’ Bureau. And to prove that he has done so, he has to collect the business cards of each one he visits and show the “gate keepers” as he leaves. There’s just one problem …… Hans Moleman is his own worst enemy in that he has a business card fetish: he won’t carry in his hands multiple cards unless he can stack them in such a way that no card is smaller than the card below it1 . Now, he can orient the stacked cards any way he wants, but a card can’t “hang over” (or be the same size as) the card above it. This is stupid, but oh well! It’s part of the reason why Hans Moleman is an interesting character. Fortunately for Hans Moleman, there’s an out: IF he visits enough different inhabitants, then he can get out of Atlantis regardless of how the cards are stacked. Specifications: Your program is to simulate this situation. Hans Moleman will visit at random some of the various “creatures” (inhabitants) of Atlantis, whereupon each of the creatures will say something chosen at random from a list of comments (below), and then give him their card which he will put in his pocket. Each creature has a card specific to them. What is important about their card is its dimensions: length and width (assume these are integers). Each time he gets a card, he needs to assess whether or not he can leave Atlantis (like really! No good hay-bars…only sushi restaurants.) When he confirms he has satisfied the Rules of Leavature, he needs to output1 As an example: card1 is 4 x 8, card2 is 2 x 9. These can NOT satisfy Hans Moleman’s criteria since there is no way to orient (at right angles) these two cards without one hanging over the other. As another example: card1 is 2 x 3 and card2 is 1 x 2. These two CAN satisfy Hans Moleman’s criteria since card2 can be stacked below card1 in a way that it will not hang over the top card since 1 < 2 and 2 < 3. So, you see, you must compare the cards in both orientations. Both dimensions of a lower card must not exceed either dimensions of an upper card, and at least one dimension of an upper card must be strictly greater than at least one dimension of a lower card. (Another ex: a 1 x 1 card can be below a 1 x 2 card) an exclamation that he is leaving (we’ll leave the wording up to you – make it clean) and returning home, and state with detail what gives him the right to leave. Leavature Rules are specified below. And what details are we expecting? Either output the names of the creatures’ cards and their dimension of the 6 stackable cards1 , or output the 14 different names of the 14 different creatures he got cards from. Details: You are expected to use a struct for a creature that includes its name and the dimensions of its card. You are expected to use arrays in this assignment as appropriate. For example, you could set up a const string array loaded with the sayings that the creatures can speak. Think about how you could randomly choose an entry from that array. You can assume that our hero Hans will collect no more than 150 cards. (Hmmmm, is that another hint about an appropriate use of arrays???) Leavature Rules (a.k.a. Rules of Leavature): Hans can leave if he has 6 (six) “stackable”1 cards (like, you know, n’stuff, non-overlapping); OR he has cards from 14 different creatures (implies 11 tunas’ cards and 3 sardines’ cards ain’t gonna do it!) In your code, generate a random creature before you generate a random saying. If you end up stacking cards that you had repeats of (e.g. you stack a 2 x 3 and you got two of these cards from two different creatures), we care not which creature’s card you use. Each creature has many cards. So, each time it is visited, it can hand a card to Hans Here’s the data to use (creature and their card specs): o Wanda Walrus 2 x 6 o Stanley Sardine 3 x 1 o Sylvia Seahorse 4 x 2 o Janie Jellyfish 1 x 10 o Doris Dolphin 8 x 4 o Bob Blobfish 1 x 5 o Sammy Shark 8 x 4 o Walter Whale 6 x 2 o Stevie Salmon 2 x 3 o Sheila Shellfish 1 x 3 o Daniel Octopus 3 x 7 o Mark Herrings 9 x 5 o Bernie Tuna 3 x 5 o Oscar Tilapia 5 x 3 Here’s a list of the things they can say: o Whazzup? o Duuude, totally love the horse head and human body combo!” o Looking for a card (shark)? o Are you someone famous? o You look fishy to me; or are you horsing around? o Don’t trust the salmon!!! o Here’s some advice: the shark wants you to be his chum! o Better take some paper towels if you visit the blobfish o Hey man, got any sea-weed? o Let me give you my card…my phone number is on the back o I’d gladly pay you Tuesday for a lobster roll today. o Don’t be so crabby! o Just keep swimming, swimmin, swimming, … o You just keep sinking, sinking, sinking,… Special Underwater Observation: You will find your coding easier if you were to sort your cards when gathering them. Think carefully how this has to be done. You wouldn’t want to overload your day with an overload of work when overloading your brain while coding… When you submit: seed your random number generator with 37. Please understand that we specify the seed for submission on the hopes that your output will be the same as everyone else. However, because of slight differences in how you all code, this may not work out as planned. But, we’re hoping that it pays off to some significant degree. And, as always, let your TAs or instructor know if you need any help.
Implement a dictionary using a Bag—Project 4.7 in the text (modified)Use the bag ADT provided to create an array-based implementation for bags. Then use your bag to implement the dictionary ADT provided you. This means you have to implement your dictionary using the bag functions.Test your bag and dictionary implementations with the bagtestmain.cpp file I’ve provided for you. If you are not able to fully implement all the functions of the dictionary and/or bag, you may modify the tests in bagtestmain.cpp to only exercise those functions you were able to complete.You will only get credit for those methods you test and display, so be sure you don’t leave any out.Also, you cannot add any public functions to your bag and dictionary implementations beyond those specified in the ADTs, though you may add private functions if you want.Put the following files into a zip file named student_name_Bag_Assignment and submit them to Blackboard:Note: If your ABag does not inherit Bag and/or BDictionary does not inherit Dictionary, you will not receive any credit for your work. If you use the templates I’ve provided (ABag.h and BDictionary.h) the inheritance is already done for you.*** If you completed your assignment using Visual Studios you must use Visual Studios 2017 and I would like you to submit your entire VS project directory.Your test program must exercise every function of the dictionary. For any function whose functionality is not obvious you must explain in your Word document how your test output demonstrates that function. See me if you have questions.See Blackboard for the assignment due date and the syllabus for the late policy.Rubrics (for the 70% content portion):Start by working on your “Approach” first. Once you are satisfied with your approach, then start building your program incrementally. Start with the bag and increment one feature at a time (you’ll have to stub out the features the ADT requires that you are not ready to implement yet) starting with the constructors and then working your way down the feature list using common sense to figure out which features need to be implemented first. Try your bag out with the various parameter combinations I want you to test with ( and ). When you are satisfied the bag is working then move on to the dictionary, again implementing and testing function by function.Don’t wait until the last minute. You’ll find that many of your problems you will solve while you are away from your computer and have a chance to think about the error you are seeing. This takes time.Note: KVpair, which uses the == operator for comparing the key values, will only accept objects that have also implemented the == operator. This class has been tested with the following types:It specifically does not work with the Int type (at least not in the version of C++ I am working with).A big part of this assignment is debugging your code, so do not expect your instructor to do this for you. Having completed the pre-requisite courses for this class, you should already have some experience finding coding errors and fixing them. This class will give you plenty of opportunities to further refine those skills and you can only do that by wrestling with the problem. Here are some debugging tips:Implement a Double-Threaded Binary Tree and add in-order and reverse-order printing without resorting to recursion—Project 5.2 in the textUsing the following supplied C++ files implement a right and left threaded binary search tree(see https://algorithms.tutorialhorizon.com/double-threaded-binary-tree-complete-implementation/ for more information on doubly threaded BSTs). The files provided to you come from our text, with some minor modifications, and implement a BST based dictionary. You must modify this BST-based dictionary to implement a threaded BST. Specifically, you will need to make the following modifications:Put the following files into a zip file and submit your assignment to the assignment link in Blackboard:Here is an example of my test run showing both printhelp, printInorder, and printReverse:Put all your files into a single zip file and submit it to Blackboard.If you look at the standard rubrics, the content portion is worth 70% or 87.5 points out of 125. The rubrics for the content portion of this assignment are: This is a deceptively challenging project. Do not wait until the last minute to start working on it or you will go crazy (and probably not succeed in finishing your project). I recommend that you start with your Word document and describe your implementation approach and then use that to guide your actual implementation.Break the project into pieces and think about how you are going to accomplish each piece. Start by getting the BST files I’ve given you running before making any changes to themand be sure you understand how the author has implemented his BST. Then add your Booleaninstance variables to the BSTNode.hfile and implement your setter/getter methods for your threads.Next start thinking about inserthelp. You pretty much have to gut the entire method and start from scratch. Think about node states and how each state affects the insert operation. For example the state of root when it is the only node in the tree is left and right child equal NULL. How will you add a node to root and implement your successor and predecessor pointers? Now look at the state of the second node. How is it different from the state root was in, and how does that change future insertions? For me it helps drawing the tree out as I build it, so that I can visualize what it is I am attempting to do.A big part of this assignment is debugging your code, so do not expect your instructor to do this for you. Having completed the pre-requisite courses for this class, you should already have some experience finding coding errors and fixing them. This class will give you plenty of opportunities to further refine those skills and you can only do that by wrestling with the problem. Here are some debugging tips:Make sure you take full advantage of the debugger in your development environment. Debuggers are invaluable for examining the state of pointers and variables as they make their way through the program.Implement a disk-based buffer pool class based on the LRU buffer pool replacement strategy.Implement and demonstrate a disk-based buffer pool class based on the LRU buffer pool replacement strategy. Disk blocks are numbered consecutively from the beginning of the file with the first block numbered as 0. Assume that blocks are 4096 bytes in size. Use the supplied C++ files to implement your LRU Buffer Pool based on the instructions below. Use main.cpp as the test driver and mydatafile.txt as the input file.Put the following files into a zip file and submit your assignment to the assignment link in Blackboard:Put all your source files, test files, executable, and Word document(s) into a zip file and submit it to Blackboard. Implement the three self-organizing list heuristics:Compare the cost of each heuristic by keeping track of the number of compares required when searching the list.Use the SelfOrderedListADT abstract data type and the linked-list files I have provided to implement your self-ordered lists. You may incorporate the author’s linked list implementation via inheritance or composition, which ever makes the most sense to you (I will not evaluate that aspect of your implementation). You are allowed to make changes to any of the files I have provided, except SelfOrderedListADT and test.txt, to make your implementation of SelfOrderedListADT cleaner. The same applies to the link.h (the link node implementation). You may not change SelfOrderedListADT or test.txt files.I want you to run two testsHere is a sample of a test run using strings (this sample was not run using the test file I’ve assigned you, so the values you see are not the same as those you should be seeing):Make sure that you give me enough screen shots so that I can see your entire run. You will be penalized if you do not.SelfOrderedListADT Functions: To receive credit for this assignment you must submit the following files in a zip file to Blackboard:To earn any credit at all you must submit a working program that implements and demonstrates at least one of the heuristics. You must also include all the files I asked for above or you will not receive any credit. You must also use the SelfOrderedListADT I have provided (unchanged) by establishing an inheritance relationship between your self-ordered list(s) and the ADT. Failure to do so will disqualify your project and you will not receive any credit for it.The rubrics below reflect just the content portion of the assignment rubrics (70% of the total point value of 125 points).
Assignment overview In this assignment, you will implement a set of related classes of objects: Student: A university student StudentList: A list of students Course: A course with a title, short title, class list, etc. CourseList: A class list Keep all of your methods short and simple. In a properly-written object-oriented program, the work is distributed among many small methods, which call each other. There are no methods in this entire assignment that should require more than 12 lines of code, not counting comments, blank lines, or {} lines (and many of them need no more than 3-4). Unless specified otherwise, all instance variables must be private, and all methods should be public. Also, unless specified otherwise, there should be no println statements in your classes. Objects usually do not print anything, they only return String values from toString methods. The only exceptions in this assignment are register in Course (Phase 2) and withdraw in Course (Phase 3). Testing Your Coding We have provided sample test files for each phase to help you see if your code is working according to the assignment specifications. These files are starting points for testing your code. Part of developing your skills as a programmer is to think through additional important test cases and to write your own code to test these cases. For marking, we will use longer and more comprehensive tests. Phase 1: Student and StudentList First, implement two simple classes: a Student class and a StudentList class The Student class should have: Three instance variables: the student’s first name (a String), last name (a String) and student number (an int) A constructor that has three parameters, in the above order, which are used to initialize the three instance variables. A standard toString method, which returns a String containing the student’s last and first names separated by a comma, and student number in between parentheses (as shown in the output below). ASSIGNMENT 1: Introduction to Object-Oriented Programming COMP 1020 Page 2 of 7 An equals method that checks if two Students are equal. Two students are equal if they have the same first name, last name and student number. The StudentList class should have: Three instance variables: an array of Students, the maximum size of the array (an int) and the current number of students in the array (an int) A constructor that takes one parameter: the maximum size of the array. The other instance variables must be initialized in the constructor (assume that the StudentList will be empty when constructed). A method contains(Student) that checks if the student is already in the list and returns a boolean (true if in the list or false otherwise). A method addStudent that has a parameter of type Student, adds the Student to the list only if there is enough space. This method returns a boolean (true if the student was added and false otherwise). A toString method which returns a String containing all the Students in the list, one Student per line (as shown below). You can test your classes using the supplied test program TestPhase1.java. You should get the output shown below. Frost, Miranda (123001) The list already contains: Frost, Miranda (123001) Frost, Miranda (123001) Bullion, Mister (123002) Frost, Miranda (123001) Bullion, Mister (123002) Simonova, Natalya (123003) Cannot add student: Grishenko, Boris (123004) Frost, Miranda (123001) Bullion, Mister (123002) Simonova, Natalya (123003) Phase 2: Course and CourseList Next, implement the Course class, and a CourseList. The Course class should have: A class constant: the maximum size of the wait list (you can set it to 100). Five instance variables: the title of the course (a String), the short title of the course (a String – e.g. COMP1020), the maximum class size (an int), a class list (a StudentList) and a wait list (a StudentList). A constructor that accepts three parameters, the title, short title and maximum class size. The two StudentLists should also be instantiated by the constructors. A method register(Student) that registers the Student to the appropriate list, if possible, using the rules described here: o if the student is already in the class list, nothing is to be done, and the method should print “The student [student description] is already registered to [course short title]!” o if the student is not in the class list, and space is available, the method adds the student to the class list and prints: “The student [student description] has been registered successfully to [course short title].” This method also adds the course to the course list of the student (see Changes to Student class below). o if the class list is full, then the method tries to add the student to the wait list o if the student is already on the wait list, nothing is to be done and the method should print “The student [student description] is already on the wait list for [course short title]!” o if the student is not on the wait list and space is available, the method adds the student to the wait list and prints: “The student [student description] has been placed on the wait list for [course short title].” ASSIGNMENT 1: Introduction to Object-Oriented Programming COMP 1020 Page 3 of 7 o if the wait list is full, nothing is to be done and the method prints “The wait list is full for [course short title]!” A getTitles method, that returns a String containing the course short title followed by a dash and the course title. A toString method that returns a String containing the course short title followed by a dash and the course title on the first line. On the following lines, the class list and wait list are printed (see example below). Then, implement a CourseList class. This class should have: A class constant: the maximum number of courses a student can take (set it to 100). Two instance variables: an array of Courses, and the current number of courses in the list (an int) A constructor that has no parameters, which initializes the instance variables (the CourseList should be empty when created). A method contains(Course) that returns true if the course is already in the list, false otherwise. An addCourse(Course) method (void) that adds the Course to the list. a getAllTitles method that calls the getTitles method for each Course of the list, and builds a String representation of all the courses on the list, one Course per line. A toString method that returns a String containing the full String representation (titles, class list and wait list) of all Courses in the list (as shown in the example below). Changes to Student class: Add an additional instance variable: a CourseList, containing the list of all courses the student is registered to (fully registered, not on the wait list). The constructor should instantiate the above instance variable (empty CourseList). A method addCourse(Course), that adds the Course to the CourseList. You may assume that it will never get full. A method getCourseListString, that returns a String containing “Student [student description] is registered to:” followed on the next lines by the list of course titles, using the getAllTitles method of the CourseList class. You can test your class with TestPhase2.java. You should get the output shown below. The student Frost, Miranda (123001) has been registered successfully to COMP1010. The student Bullion, Mister (123002) has been registered successfully to COMP1010. The student Simonova, Natalya (123003) has been registered successfully to COMP1010. The student Grishenko, Boris (123004) has been registered successfully to COMP1010. The student Davidov, Sacha (123005) has been registered successfully to COMP1010. The student Carver, Paris (123006) has been registered successfully to COMP1010. The student Gupta, Henry (123007) has been placed on the wait list for COMP1010. COMP1010 – Introductory Computer Science 1 Class list: Frost, Miranda (123001) Bullion, Mister (123002) Simonova, Natalya (123003) Grishenko, Boris (123004) Davidov, Sacha (123005) Carver, Paris (123006) Wait list: Gupta, Henry (123007) The student Simonova, Natalya (123003) has been registered successfully to COMP1020. The student Onatopp, Xenia (123008) has been registered successfully to COMP1020. The student Drax, Hugo (123009) has been registered successfully to COMP1020. The student Zukovsky, Valentin (123010) has been registered successfully to COMP1020. ASSIGNMENT 1: Introduction to Object-Oriented ProgrammingThe student Ourumov, Arkady Grigorovich (123011) has been registered successfully to COMP1020. The student Mishkin, Dmitri (123012) has been placed on the wait list for COMP1020. The student Lynd, Vesper (123013) has been placed on the wait list for COMP1020. The student Trevelyan, Alec (123014) has been placed on the wait list for COMP1020. The student Scaramanga, Francisco (123015) has been placed on the wait list for COMP1020. The student Jones, Christmas (123016) has been placed on the wait list for COMP1020. The student Lin, Wai (123017) has been placed on the wait list for COMP1020. The student King, Elektra (123018) has been placed on the wait list for COMP1020. COMP1020 – Introductory Computer Science 2 Class list: Simonova, Natalya (123003) Onatopp, Xenia (123008) Drax, Hugo (123009) Zukovsky, Valentin (123010) Ourumov, Arkady Grigorovich (123011) Wait list: Mishkin, Dmitri (123012) Lynd, Vesper (123013) Trevelyan, Alec (123014) Scaramanga, Francisco (123015) Jones, Christmas (123016) Lin, Wai (123017) King, Elektra (123018) The student Gupta, Henry (123007) is already on the wait list for COMP1010! COMP1010 – Introductory Computer Science 1 Class list: Frost, Miranda (123001) Bullion, Mister (123002) Simonova, Natalya (123003) Grishenko, Boris (123004) Davidov, Sacha (123005) Carver, Paris (123006) Wait list: Gupta, Henry (123007) The student Drax, Hugo (123009) is already registered to COMP1020! COMP1020 – Introductory Computer Science 2 Class list: Simonova, Natalya (123003) Onatopp, Xenia (123008) Drax, Hugo (123009) Zukovsky, Valentin (123010) Ourumov, Arkady Grigorovich (123011) Wait list: Mishkin, Dmitri (123012) Lynd, Vesper (123013) Trevelyan, Alec (123014) Scaramanga, Francisco (123015) Jones, Christmas (123016) Lin, Wai (123017) King, Elektra (123018) ASSIGNMENT 1: Introduction to Object-Oriented ProgrammingThe student Simonova, Natalya (123003) has been registered successfully to COMP2140. The student Simonova, Natalya (123003) has been registered successfully to COMP2150. The student Simonova, Natalya (123003) has been registered successfully to COMP3350. Student Simonova, Natalya (123003) is registered to: COMP1010 – Introductory Computer Science 1 COMP1020 – Introductory Computer Science 2 COMP2140 – Data Structures and Algorithms COMP2150 – Object Orientation COMP3350 – Software Engineering 1 Phase 3: Withdrawing from a Course Next implement a withdraw(Student) method in the Course class, which will withdraw the Student from the class list, if the Student is on the class list, or withdraw the Student from the wait list, if the Student is on the wait list, or do nothing if the Student is not in any of the lists. The method must print: o “The student [student description] has been withdrawn from [course short title].” if the student was on the class list. o “The student [student description] has been withdrawn from the wait list of [course short title].” if the student was on the wait list. o “The student [student description] is not on any list of [course short title].” otherwise. If the Student was on the class list, the method must also remove the Course from the Student’s CourseList. If the Student was on the class list, and there is at least one Student on the wait list, the first Student on the wait list must be registered to the class list (and removed from the wait list). When removing a Student from a class/wait list, or removing a course from a CourseList, you must fill in the gap by shifting up all the following Students/Courses. Also, don’t forget to update the counter of the current number of students or current number of courses. Important: to fully complete Phase 3, following the instructions above, you will need to add other methods to other classes(while maintaining encapsulation – every object is responsible for modifying its own instance variables). You can test your class with TestPhase3.java. You should get the output shown below: The student Frost, Miranda (123001) has been registered successfully to COMP1010. The student Frost, Miranda (123001) has been registered successfully to COMP2150. The student Bullion, Mister (123002) has been registered successfully to COMP1010. The student Simonova, Natalya (123003) has been registered successfully to COMP1010. The student Grishenko, Boris (123004) has been registered successfully to COMP1010. The student Davidov, Sacha (123005) has been registered successfully to COMP1010. The student Carver, Paris (123006) has been registered successfully to COMP1010. The student Gupta, Henry (123007) has been placed on the wait list for COMP1010. The student Onatopp, Xenia (123008) has been placed on the wait list for COMP1010. COMP1010 – Introductory Computer Science 1 Class list: Frost, Miranda (123001) Bullion, Mister (123002) Simonova, Natalya (123003) Grishenko, Boris (123004) Davidov, Sacha (123005) Carver, Paris (123006) Wait list: Gupta, Henry (123007) Onatopp, Xenia (123008) ASSIGNMENT 1: Introduction to Object-Oriented Programming COMP 1020 Page 6 of 7 Student Frost, Miranda (123001) is registered to: COMP1010 – Introductory Computer Science 1 COMP2150 – Object Orientation The student Zukovsky, Valentin (123010) is not on any list of COMP1010. COMP1010 – Introductory Computer Science 1 Class list: Frost, Miranda (123001) Bullion, Mister (123002) Simonova, Natalya (123003) Grishenko, Boris (123004) Davidov, Sacha (123005) Carver, Paris (123006) Wait list: Gupta, Henry (123007) Onatopp, Xenia (123008) The student Gupta, Henry (123007) has been withdrawn from the wait list of COMP1010. COMP1010 – Introductory Computer Science 1 Class list: Frost, Miranda (123001) Bullion, Mister (123002) Simonova, Natalya (123003) Grishenko, Boris (123004) Davidov, Sacha (123005) Carver, Paris (123006) Wait list: Onatopp, Xenia (123008) The student Frost, Miranda (123001) has been withdrawn from COMP1010. The student Onatopp, Xenia (123008) has been registered successfully to COMP1010. COMP1010 – Introductory Computer Science 1 Class list: Bullion, Mister (123002) Simonova, Natalya (123003) Grishenko, Boris (123004) Davidov, Sacha (123005) Carver, Paris (123006) Onatopp, Xenia (123008) Wait list: The student Bullion, Mister (123002) has been withdrawn from COMP1010. COMP1010 – Introductory Computer Science 1 Class list: Simonova, Natalya (123003) Grishenko, Boris (123004) Davidov, Sacha (123005) Carver, Paris (123006) Onatopp, Xenia (123008) Wait list: Student Frost, Miranda (123001) is registered to: COMP2150 – Object Orientation ASSIGNMENT 1: Introduction to Object-Oriented Programming COMP 1020 Page 7 of 7 Hand in Submit your four Java files (Student.java, StudentList.java, Course.java, CourseList.java). Do not submit .class or .java~ files! You do not need to submit the TestPhaseN.java files that were given to you. If you did not complete all phases of the assignment, use the Comments field when you hand in the assignment to tell the marker which phases were completed, so that only the appropriate tests can be run. For example, if you say that you completed Phases 1-2, then the marker will compile your files, and compile and run the tests for phases 1 and 2. If it fails to compile and run, you will lose all of the marks for the test runs. The marker will not try to run anything else, and will not edit your files in any way. Make sure none of your files specify a package at the top!Assignment overview In this assignment, you will build a version of the game Bejewelled. Bejewelled is a ‘match 3’ game, where you must match 3 or more of the same gem by moving the gems on the board. The gems can only move 1 cell up or down, left or right, and swap with neighbouring gem when moving. Upon matching, the gems that match disappear, leaving a gap, and the gems above the gap fall, filling the gap. If you are unfamiliar with the game, you can plan an online version here. Keep all of your methods short and simple. In a properly-written object-oriented program, the work is distributed among many small methods, which call each other. There are few methods in this entire assignment that should require more than 15 lines of code, not counting comments, blank lines, or {} lines. Unless specified otherwise, all instance variables must be private, and all methods should be public. Your assignment should be DRY – don’t repeat yourself. If you notice you have code that does the same function in two places, consider making a private method that can be called to do the work. If you see 3 or more lines of code that do the same thing in two different methods, consider making a private method that does that task. This is often called a ‘helper’ method. Testing Your Coding We have provided sample test files for each phase to help you see if your code is working according to the assignment specifications. These files are starting points for testing your code. Part of developing your skills as a programmer is to think through additional important test cases and to write your own code to test these cases. Phase 1: The Grid First, create the game board, named class Grid. The Grid class should have: • An instance variable to hold the board, which is a 2D array of char. • A method fillBoard(), which fills the board with random gems, overwriting whatever is in the board. • A constructor Grid(int height, int width), which creates a new game board filled with random gems. • A standard toString method, which returns a text representation of the board. To choose random gems, you can add this to your Grid class: public static char[] gems = {‘r’, ‘g’, ‘b’,’y’}; ASSIGNMENT 2: Input/output, Exceptions, and Multi-dimensional arrays COMP 1020 Page 2 of 4 public static char getRandomGem() { int choice = (int)(Math.random() * gems.length); return gems[choice]; } Phase 2: Grids from files We want to be able to save our progress. To do this, we will save our progress to a file, and be able to read these files. The save files have a special format. The top line is the dimensions of the saved board: number of rows, then number of columns. The rest of the file is the contents of the board. Example: 2 3 yrb bry Is a valid file. To do this, implement these methods in the Grid class: • A new constructor, Grid(char[][] someGrid), which creates a grid with the given data. You do not need to check if the gems are valid (in the set of letters provided). • A factory method called Grid createGrid(String filename), which reads the data the text file specified by ‘filename’, and returns a Grid object with that data. This method throws IOException if the data is not valid. Special exception messages include: o Bad dimensions for the saved file o Not enough rows of data to read o Not enough columns of data to read Your error messages should have as much detail as possible. See the sample output for what is expected. This method is quite long, due to the error handling, and will exceed the usual “15 lines of code” rule-of-thumb. • A save(String filename)method, that writes the current board to the specified file, in the save file format used. If there is an exception, it should print out the error message, and return null. Sample output: yr by bb rr java.io.IOException: No dimensions to read java.io.IOException: The size values were not numeric! java.io.IOException: There was not enough rows! Saw 5 need 10 java.io.IOException: There was not enough colums. Saw 2 need 12 yr by These should be the same: rryryb yybgbg yrrbrb yyryrr brgbgr rryryb yybgbg yrrbrb yyryrr ASSIGNMENT 2: Input/output, Exceptions, and Multi-dimensional arraysbrgbgr Phase 3: Extracting data Add the following methods to extract data from your Grid class. You will use these later in the program. • Method char[] extractRow(int rowNum) that extracts the row specified by the passed integer. 0 will fetch the first row, 1 the second (index-by-zero rules). • Method char[] extractColumn(int colNum), which extracts a single column, much like extract row. Phase 4: Checking for gems in a row Write a method named static char[] replaceSets(char[] input) in Grid that is passed a 1D array of gems, and checks if there are set of 3 or more gems in a row. Return a new array that has the gems that are in a row replaced with ‘x’ characters. Phase 5: Merge We have methods to find if there are sets of gems. Now, write the method replaceAll() in Grid. This method uses the methods created in phase 4 to mark any sets of 3 with x’s. There are some subtleties to this method. Consider: bbb bgg bgg There is a set of 3 in both the first row, and first column. If you set the first row to all x’s, then check the column, then column 0 would be xbb, and the program would not set column 0 to all x’s. A solution to this is to create a new 2D array with the sets replaced by x’s, while looking at the original to see if there are sets to be replaced. Phase 6: Drop Create method boolean drop() in class Grid. This method ‘drops’ the gems that are above cells that have an x in them. In Bejewelled, as gems disappear, the gems above them drop down. This method does the dropping step. The drop method returns true if any gems have moved. In any spots that are now empty, place random gems. This will be the gems that are ‘falling from the top’. Phase 7: Swap Create 4 public static final variables in class Grid: UP, DOWN, LEFT, and RIGHT. You can set these to any numbers you like but they all must be different numbers. Create the method void swap(int row, int col, int direction). This will swap the gem specified by row and column (indexed at 0) in the direction specified. Throw appropriate exceptions for out-of-bounds gem selection, and movement. Throw IndexOutOfBoundsException for any strange things that may happen. ASSIGNMENT 2: Input/output, Exceptions, and Multi-dimensional arraysPhase 8: Bonuses: Is that swap allowed? Ending the game? +10%: In Bejewelled, moves are only allowed if it causes a match. Update the game to enforce that rule. +20%: The game is over when there are no more moves. Update the game, and TestPhase7b.java to enforce this. Visit every gem, and see if it can move up/down/left/right. Continue the game if there is at least 1 valid move left. If you accomplish these bonus items, write that you did so in the comment section of the hand-in. Hand in Submit your one Java file (Grid.java). Do not submit .class or .java~ files! You do not need to submit the TestPhaseN.java files that were given to you unless you attempted the bonus. If you did not complete all phases of the assignment, use the Comments field when you hand in the assignment to tell the marker which phases were completed, so that only the appropriate tests can be run. For example, if you say that you completed Phases 1-2, then the marker will compile your files with appropriate test cases. If it fails to compile and run, you will lose all of the marks for the test runs. The marker will not try to run anything else, and will not edit your files in any way. Make sure none of your files specify a package at the top!Assignment overview In this assignment, you will implement a text-based game that is heavily inspired by the game NetHack. NetNack is a classic open-source console-based game, and has been ported to most operating systems. See their homepage here, or play online here. NetHack is a very deep game, and we are only borrowing basic elements from it. The key parts we are keeping are: • There is a board of size m by n. • Each element of the board may be a wall or an empty space. • Each empty space can be occupied by one character or item: either the player, an enemy, a health potion or a trap. • Commands are given by typing “up”, “down”, “left” or “right” (or just ‘u’, ‘d’, ‘l’, or ‘r’). The player will only move in that direction if the space is unoccupied, and not a wall. • If the space is occupied by a different character, the player attacks that character. Keep all of your methods short and simple. In a properly-written object-oriented program, the work is distributed among many small methods, which call each other. There are many files to hand in with this assignment, most of which are only 1 or 2 lines long. Only a few will need 20 lines of code or more. Writing good code that uses inheritance means writing the logic once, and using that logic in the subclasses. Phase 1: The board First, implement the abstract class Tile. This class represents the elements of the two-dimensional array that is the board (a Tile[][] array). The tiles will hold the game pieces or a wall. We will add more to this class later. To start, a Tile should have: • Two instance variables: a String which is the symbol that should be displayed by this tile, and a boolean which will indicate if this tile is a tile that the player can move onto (is “passable”). • A constructor that has two parameters – the String and the boolean, in that order. • Method String getSymbol()which fetches the symbol that should be displayed. • Method boolean isPassable() which indicates if the tile is passable. Now implement two subclasses of the Tile class: Wall, and OpenSpace. • Class Wall is not passable, and the symbol is a hash: # • Class OpenSpace is an empty space which is passable, and the symbol is a period: . ASSIGNMENT 3: Object-Oriented Programming, Inheritance and Polymorphism COMP 1020 Page 2 of 9 These subclasses will only contain constructors. All the other logic in them is inherited from class Tile. You can test your classes using the supplied test program TestPhase1.java. You should get the output shown below. #### #..# #..# #### Phase 2: Content Next, implement the abstract Content class, which represents items that are sitting on the Tiles. The Content class should have: • One instance variable: a String that represents the symbol that will be drawn on the map. This can be a protected variable. • A constructor that accepts only one parameter (the String). • A String getSymbol()method that returns the symbol for this item. Implement an abstract subclass of Contents named Item. Subclasses of Item will be objects in the game that the player can touch to interact with. Item should have: • A constructor with only a String parameter specifying the symbol. • An int getEffect() method that returns how much of the player’s health (“hit points”) are added, or removed by touching this item. The default value to return is 0. Now write three subclasses of Item: • Amulet: which is marked by the character “Y” on the map. This is the “Amulet of Yendor”. Picking up this item will result in winning the game. This item has no effect on hit points. This will be implemented later. In addition to returning a 0, the getEffect() method should also write “You picked up the Amulet of Yendor!” to the console. • HealthPotion: Represented by an “h” on the map, a health potion has the effect of adding 5 hit points (health) to the player. In addition to returning a 5, the getEffect() method should also write “You picked up a health potion!” to the console. • Trap: Represented by a “^” on the map, the player will lose 5 hit points when touching this item. In addition to returning a -5, the getEffect() method should also write “You set off a trap!” to the console. These three classes only contain a no-parameters constructor, and a getEffect() method. Now make the following modifications to class Tile and its subclasses: • Add an instance variable of type Content to Tile. When there is no content to a tile, this variable should be null. • Add methods removeContent(), which will set your Content instance variable to null, and a getContent() method which will return the contents of this tile, and a setContent(Content) method which will set the content of this tile. • Change the getSymbol() method to return the symbol of the content, if there is a content in the tile. Otherwise, return the symbol of the tile itself. • Add a second constructor to the Tile and OpenSpace classes, that accepts an additional parameter of type Content. The signature should be: public Tile(String, boolean, Content). The Wall class should not have a constructor of this kind, since a wall cannot have any content. ASSIGNMENT 3: Object-Oriented Programming, Inheritance and PolymorphismYou can test your class with TestPhase2.java. You should get the output shown below. #### #^Y# #^h# #### Phase 3: Combatants Combatants are the characters on the board. There is always exactly one player, and zero or more enemies. Both have “hit points” (the amount of health the combatant has). When the hit points become zero or lower, the combatant is removed from the board. Health potions can increase the player’s hit points, while traps lower the player’s hit points. Combatants have attacks which vary in strength. There are minimum and maximum attack values. Each time an attack is made, a new random attack value between the minimum and maximum is returned. This amount of health is removed from the combatant that is being attacked. Define an abstract Combatant class that is a subclass of Content. It should have: • Three instance variables: int values for the health, and minimum and maximum attack values. • A constructor which accepts parameters of type (String, int, int, int) which are the symbol, health, minimum, and maximum attack points, in that order. • Three methods: o int getHP() – returns the current number of hit points (health) o int doAttack() – return a random number between the minimum and maximum attack values, inclusive. Investigate Math.random() to do this. o void changeHP(int amount) – add this amount to the combatant’s hit points. The number could be negative. Define three subclasses of Combatant: • Player: represented by an “@” on the board, this is the playing piece the user will be able to move. The player should start with 100 hit points, and have a minimum attack value of 5, and a maximum of 10. • Troll: represented by a “t” on the board. Trolls should start with 15 hit points, and have a minimum attack value of 1, and a maximum of 10. • GreaterTroll, which is a subclass of Troll: Greater Trolls have double the hit points of Trolls, attack twice not once, and are represented by a “T” on the board. The constructor of GreaterTroll should call the constructor of Troll, then modify the hit points. The doAttack() method of GreaterTroll should call the doAttack() method in Troll twice, and return the total damage. • These three subclasses should have only a no-parameters constructor. Combatant Player Troll Greater Troll ASSIGNMENT 3: Object-Oriented Programming, Inheritance and PolymorphismAdd toString() methods to the Combatant class, and all of its subclasses, that simply returns the class name. You can test your class with TestPhase3.java. You should get the output shown below. ###### #^Y.t# #^h@.# ###### Player hp is:100 Troll hp is:15 Phase 4: Your own Enemies Create a new enemy class, of your choosing and design. This is very open ended. The only requirements are that there is a unique letter attributed with the name on the map, and that it has a unique name in the game when it is in a fight. Then, create a subclass of that enemy, that is a more specialized version of that enemy (much like Troll, GreaterTroll). In your subclass, override the changeHP method to double any values that are applied. If a 2 is passed, add 4. If a -4 is passed, use -8. Phase 5: Gameboard Create a Gameboard class that will hold and manage a 2D array of tiles that will represent the game state. To initialize the game board, data will be read in from a text file. The text file has the following format. The first row contains two integers that specify how many rows and columns are in the rectangular game board. The rest of the file gives the initial state of the game board. It has the same format as the output that we have been generating to this point: “Y” is the amulet, “@” is the player, and so on. The Gameboard class, for this phase, only needs one instance variable of type Tile[][]. Write a constructor that accepts a file name as a parameter (a String). Open that file, read the contents, and initialize your two dimensional array of tiles based on the file. It can be assumed that the file will be in the same folder as your code. Write a toString() method that returns the game board as a multi-line String. The first line should give the current health of the player, and the remaining lines should show the board. See the examples below. You can test your class with TestPhase5.java. You should get the output shown below. Make sure the supplied test data files (phase5GameBoard1.txt and phase5GameBoard2.txt) are in the same folder as the rest of your files. Health: 100 ####### #^Y.t.# #^[email protected]# #.h..h# ####### Health: 100 ############# #^Y.t…….# #^h..T..^…# #.h..h…..@# ############# ASSIGNMENT 3: Object-Oriented Programming, Inheritance and PolymorphismPhase 6: The Game Extend the Gameboard class to play a simple game with the game board we have created. Add: • Static variables to define the four possible directions. You can set these to whatever values you like: o public static final int UP o public static final int DOWN o public static final int LEFT o public static final int RIGHT • Two boolean instance variables: one indicating whether or not the game is over, and one indicating whether or not the player has won the game. Add accessor methods getWon() and getDone() for these instance variables. • void doRound(int): This method contains all the logic to control one move in the game. The parameter specifies the direction of the move: up, down, left or right. This will be a fairly large method. o If the player tries to move into a wall, the player should not move. o If the player moves into an empty space, the player should move to that space. o If the player moves onto a space where there is an Item, call getEffect() on the item, and change the user’s hit points appropriately with changeHP(). If the item is the Amulet of Yendor (Y), the game is won. Set the boolean variables appropriately. o If the player attempts to move into a space occupied by a different combatant: ▪ The player attacks that combatant. Use doAttack() to generate how many hit points the attack removes from the combatant. If the other combatant is reduced to 0 or fewer hit points, that combatant is removed from the board, and the player moves into that square. ▪ If the combatant is not at 0 or fewer hit points, the player does not move, and the combatant attacks back, reducing the health of the player. If the player is reduced to 0 or fewer hit points, the player dies and the game is over. ▪ Print out to the console the number of hit points both combatants have after the attacks are complete. ▪ Print out to the console “[enemy type] is vanquished!” when a combatant is reduced to 0 or fewer hit points. You can test your class with TestPhase6.java. Sample output is shown below, which shows fighting a combatant, and setting off a trap. Welcome to NetHack, 1020 edition. Health: 100 ############# #^Y.t…….# #^h..T..^.^t# #.h..h…..@# ############# Which way would you like to move? Valid commands are up, down, left, right. u Player attacks the Troll for 6 Troll attacks the player for 3 Player health:97 Troll health 9 Health: 97 ############# #^Y.t…….# #^h..T..^.^t# #.h..h…..@# ############# ASSIGNMENT 3: Object-Oriented Programming, Inheritance and PolymorphismWhich way would you like to move? Valid commands are up, down, left, right. u Player attacks the Troll for 8 Troll attacks the player for 4 Player health:93 Troll health 1 Health: 93 ############# #^Y.t…….# #^h..T..^.^t# #.h..h…..@# ############# Which way would you like to move? Valid commands are up, down, left, right. u Player attacks the Troll for 5 Troll is vanquished! Health: 93 ############# #^Y.t…….# #^h..T..^.^@# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. l You set off a trap! Health: 88 ############# #^Y.t…….# #^h..T..^.@.# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. u Health: 88 ############# #^Y.t…..@.# #^h..T..^…# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. l Health: 88 ############# #^Y.t….@..# #^h..T..^…# #.h..h……# ############# Which way would you like to move? ASSIGNMENT 3: Object-Oriented Programming, Inheritance and PolymorphismValid commands are up, down, left, right. l Health: 88 ############# #^Y.t…@…# #^h..T..^…# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. l Health: 88 ############# #^Y.t..@….# #^h..T..^…# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. l Health: 88 ############# #^Y.t.@…..# #^h..T..^…# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. l Health: 88 ############# #^Y.t@……# #^h..T..^…# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. l Player attacks the Troll for 6 Troll attacks the player for 5 Player health:83 Troll health 9 Health: 83 ############# #^Y.t@……# #^h..T..^…# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. l Player attacks the Troll for 6 Troll attacks the player for 2 ASSIGNMENT 3: Object-Oriented Programming, Inheritance and PolymorphismPlayer health:81 Troll health 3 Health: 81 ############# #^Y.t@……# #^h..T..^…# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. l Player attacks the Troll for 7 Troll is vanquished! Health: 81 ############# #^Y.@…….# #^h..T..^…# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. Health: 81 ############# #^Y.@…….# #^h..T..^…# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. l Health: 81 ############# #^Y@……..# #^h..T..^…# #.h..h……# ############# Which way would you like to move? Valid commands are up, down, left, right. l You picked up a The Amulet of Yendor! You win! Hand in Submit your fifteen Java files. 1. Amulet.java 2. Combatant.java 3. Content.java 4. Gameboard.java 5. GreaterTroll.java 6. HealthPotion.java ASSIGNMENT 3: Object-Oriented Programming, Inheritance and Polymorphism7. Item.java 8. OpenSpace.java 9. Player.java 10. Tile.java 11. Trap.java 12. Troll.java 13. Wall.java 14. The enemy you created 15. The subclass of the enemy you created Do not submit .class or .java~ files! Do not submit a .zip file! You do not need to submit the TestPhaseN.java files that were given to you. If you did not complete all five phases of the assignment, use the Comments field when you hand in the assignment to tell the marker which phases were completed, so that only the appropriate tests can be run. For example, if you say that you completed Phases 1-2, then the marker will compile your files, and compile and run the tests for phases 1 and 2. If it fails to compile and run, you will lose all of the marks for the test runs. The marker will not try to run anything else, and will not edit your files in any way. (Make sure none of your files specify a package at the top!)Assignment overview In this assignment, you will receive two template files, in which you will implement a set of methods. The two template files, that you will modify are: Node: A node of a LinkedList, containing some data (stored as an Object) and a reference to the next link (a Node). LinkedList: A class representing a LinkedList of Nodes. It has a reference to the first Node of the list (top). Keep all of your methods short and simple. In a properly-written object-oriented program, the work is distributed among many small methods, which call each other. Most methods in this entire assignment require no more than 10-12 lines of code, not counting comments, blank lines, or {} lines. The swap method (Phase 5) is the only exception (this one might require about 30 lines of code). Unless specified otherwise, all instance variables must be private, and all interface methods should be public. Helper methods (not supposed to be used by outside code) should normally be private. Since this assignment will be using a lot of recursion, and since recursive methods often need extra parameters, we will often implement a public interface method, which is meant to be used by outside code, and its only role will be to call the private recursive version of the method with appropriate parameters. Testing Your Coding We have provided sample test files for each phase to help you see if your code is working according to the assignment specifications. These files are starting points for testing your code. Part of developing your skills as a programmer is to think through additional important test cases and to write your own code to test these cases. For marking, we will use longer and more comprehensive tests. Phase 1: add and toString Implement these methods in the LinkedList class: The add(Object data) method: This method is the public interface to add a new piece of data at the end of the list. This method will call the addRec method defined below, with appropriate parameters. ASSIGNMENT 4: Introduction to Object-Oriented Programming COMP 1020 Page 2 of 4 The addRec(Node start, Node newNode) method: This method is the private recursive method used internally only. It will use recursive calls (to itself) to move to the end of the list, and add the newNode at the end of the list. The String toString() method: This method is the public interface to return a String representation of the list. This method will call the toStringRec method defined below, with appropriate parameters. The String toStringRec([parameters of your choice]) method: This method is the private recursive method used internally only. It will use recursive calls (to itself) to move through the list, and build a String representation of the list. The resulting String will have each data from each Node on a separate line (see example below for an example). You can test your code using the supplied test program TestingPhase1.java. You should get the output shown below. Hello World 1 2 3 Phase 2: Factory method to build a LinkedList from a file Implement this method in the LinkedList class: The LinkedList createLinkedList(String filename) method: This is a public factory method that builds and returns a new LinkedList. This is the only method of this assignment in which loops are allowed. This method must open the file corresponding to the filename parameter, read it and build the corresponding LinkedList. You can assume that there is only one token (representing the data to be stored in a Node of the LinkedList) on each line in the file. Tokens that are convertible to Integers, must be stored in the list as Integers. Tokens that are not convertible to Integers, must be stored in the list as Strings. This method must handle the exceptions related to reading a file internally (do not add a throws statement at the end of the signature of this method). You can test your code with TestingPhase2.java. The output should be equivalent to the text in the three supplied files: list1.txt, list2.txt and list3.txt. Phase 3: Sum Implement these methods in the LinkedList class: The int getSum() method: This method is the public interface to return an int representing the sum of all data in the list (see description of the next method for details). This method will call the getSumRec method defined below, with appropriate parameters. The int getSumRec([parameters of your choice]) method: This method is the private recursive method used internally only. ASSIGNMENT 4: Introduction to Object-Oriented Programming It will use recursive calls (to itself) to move through the list, and calculate the sum of the data of all Nodes of the list. For each Node, if the data is an Integer, it considers the value of the int and adds it to the sum. If the data is a String, it counts the number of characters in the String and adds it to the sum. If the data is any other kind of Object (not an Integer, not a String), it simply adds 0 to the current sum. You can test your code with TestingPhase3.java. The output of this code tells you what values are expected. Phase 4: compareTo and getSmallestNode First, implement this method in the Node class: The int compareTo(Node other) method: This method is a traditional compareTo method, which will return an int that is either < 0, == 0 or > 0. The data instance variable in each Node is going to be used to determine which Node is bigger than the other. Since many different types of data can be contained in a Node, we will follow the following rules: o Integer data is considered to be smaller than String data o If the two Nodes being compared contain Integer data, the difference between them will be returned. o If the two Nodes being compared contain String data, the alphabetical difference between them will be returned (you can simply use compareTo of Strings). o Any data that is not an Integer and not a String is considered to be bigger than Integers and Strings. No difference needs to be calculated when dealing with those and no specific int value needs to be returned as long as it is either a positive or negative number (you could use +1 or -1 for example). See TestingPhase4.java for examples. Second, implement this method in the LinkedList class: The Node getSmallestNode(Node start, Node smallest)method: This method is a public method that will also be recursive (no separate interface for this one). It will use recursive calls (to itself) to move through the list, and find the smallest Node in the list, which will be returned. The start Node represents where to start the search, and the smallest Node represents the smallest Node found so far. Using the compareTo method created previously in the Node class, this should be straightforward. You can test your code with TestingPhase4.java. The output of this code tells you what values are expected. Phase 5: getPreviousNode and swap Implement these methods in the LinkedList class: The Node getPreviousNode(Node toFind) method: This method is the public interface to return a Node representing the node that comes right before the Node toFind in the list (see description of the next method for details). This method will call the getPreviousNodeRec method defined below, with appropriate parameters. The Node getPreviousNodeRec([parameters of your choice]) method: This method is the private recursive method used internally only. It will use recursive calls (to itself) to move through the list, and find and return the Node that immediately precedes the Node to find. If the Node to find is the very first Node of the list, return null. You can assume that the Node to find is always present, that no duplicates are in the list, and that we will never call this method on an empty list. ASSIGNMENT 4: Introduction to Object-Oriented ProgrammingThe swap(Node n1, Node n2) method: This method is a public method that swaps two given Nodes in the list. Nothing needs to be returned. You have to swap the entire Nodes, not just the data (you are not allowed to add a mutator in the Node class for the data). You can assume that Nodes n1 and n2 are going to be different. Using the getPreviousNode method might be useful. This is the most complex method of the assignment (it could take up to about 30 lines of code). Make sure to think about all the links that must be modified in order to have a successful swap that will preserve the integrity of the list. Make sure to also think about all the special cases that could arise. You can test your code with TestingPhase5.java. The output of this code should allow you to see if everything worked correctly. Phase 6: Bonus phase (+20% bonus) If you are completing this bonus phase, you must mention it when submitting your assignment in the dropbox using the comments field. This bonus phase will not be evaluated if you do not specify, in the UMLearn dropbox, that you completed it. Implement these methods in the LinkedList class (if recursion is not used as described below, you will not get the bonus points): The selectionSort() method: This method is the public interface to sort the list using a selection sort algorithm, as seen in class. This method will call the selectionSortRec() method defined below, with appropriate parameters. The selectionSortRec([parameters of your choice]) method: This method is the private recursive method used internally only. It will use recursive calls (to itself) to move through the list, and sort it in place using a selection sort algorithm. The same rules defined in Phase 4 are to be used to order the Nodes. You can test your code with TestingPhase6.java. The output of this code should allow you to see if everything worked correctly. Hand in Submit your four Java files (LinkedList.java and Node.java). Do not submit .class or .java~ files! You do not need to submit the TestingPhaseN.java files that were given to you. If you did not complete all phases of the assignment, use the Comments field when you hand in the assignment to tell the marker which phases were completed, so that only the appropriate tests can be run. For example, if you say that you completed Phases 1-2, then the marker will compile your files, and compile and run the tests for phases 1 and 2. If it fails to compile and run, you will lose all of the marks for the test runs. The marker will not try to run anything else, and will not edit your files in any way. Make sure none of your files specify a package at the top!
1. This assignment will make use of the “Music & Speech” dataset of Marsyas: • You can download the dataset from: https://opihi.cs.uvic.ca/sound/music_ speech.tar.gz • This dataset has two copies of each song, delete the music/ and speech/ directories and use the files in music-wav/ and speech-wav/ directories. There are 64 music and 64 speech files. Each file has 30 seconds of audio stored as 16-bit signed integers at 22050 Hz. • Ground truth data for this dataset can be downloaded from IVLE. Format of the file is filename t (tab) label (newline), one song per line: filename1tlabel1 filename2tlabel2 … filename128tlabel128 The label field is either music or speech. 2. Follow the following steps to complete this assignment: • Read the ground-truth file (music speech.mf). • Load each wav file and convert the data to floats by dividing the samples by 32768.0. Hint: use scipy.io.wavfile.read() • Split the data into buffers of length 1024 with 50% overlap (or a hopsize of 512). Only keep complete buffers, e.g. if the last buffer only has 1020 samples, omit it. Hint: the starting and ending indices for the first few buffers are: Buffer number start index end index (not included in array) 0 0 1024 1 512 1536 2 1024 2048 . . . We recommend that you use the “array slicing” feature provided by numpy: for i in range(num_buffers): start = … end = … buffer_data = whole_file_data[start:end] • For each file, calculate time domain features for each buffer according to the given formula. Given X = {x0, x1, x2, . . . xN−1} (N = 1024 for this assignment): (a) Root-mean-squared (RMS): XRMS = vuut 1 N N X−1 i=0 x 2 i 1 (b) Zero crossings (ZCR): XZCR = 1 N − 1 N X−1 i=1 ( 1 if (xi · xi−1) < 0 0 else • After calculating the features for each buffer, calculate the mean and uncorrected sample standard deviation for each feature over all buffers for each file. • Now you have finished calculating time domain features. To calculate frequency domain features, multiply each buffer with a Hamming window. Hint: use scipy.signal.windows.hamming() • Perform a Discrete Fourier Transform for each windowed buffer. Hint: use scipy.fft(). Note: the DFT gives you both “positive” and “negative” frequencies, whose values are mirrored around the Nyquist frequency. Discard the negative frequencies (whose array indices are above N/2 for an FFT of length N). • Calculate the following frequency domain features for each spectral buffer. Given a spectral buffer X: (a) Spectral Centroid (SC): SC = PN−1 k=0 k · |X[k]| PN−1 k=0 |X[k]| (b) Spectral Roll-Off (SRO): which is the smallest bin index R such that L energy is below it. For this assignment, we will use L = 0.85. X R−1 k=0 |X[k]| ≥ L · N X−1 k=0 |X[k]| (c) Spectral Flatness Measure (SFM): SFM = exp 1 N PN−1 k=0 ln |X[k]| 1 N PN−1 k=0 |X[k]| Note: using the log-scale is useful for avoiding multiplications which may exceed the bounds of double floating-point arithmetic. • After calculating the features for each buffer, calculate the mean and uncorrected sample standard deviation for each feature over all buffers for each file. • Output your results to a new ARFF file and name it as results.arff. The header of it should be like: @RELATION music_speech @ATTRIBUTE RMS_MEAN NUMERIC @ATTRIBUTE ZCR_MEAN NUMERIC @ATTRIBUTE SC_MEAN NUMERIC @ATTRIBUTE SRO_MEAN NUMERIC @ATTRIBUTE SFM_MEAN NUMERIC @ATTRIBUTE RMS_STD NUMERIC @ATTRIBUTE ZCR_STD NUMERIC @ATTRIBUTE SC_STD NUMERIC @ATTRIBUTE SRO_STD NUMERIC @ATTRIBUTE SFM_STD NUMERIC @ATTRIBUTE class {music,speech} The format of the data section should be: @DATA RMS_MEAN1,ZCR_MEAN1,SC_MEAN1,SRO_MEAN1,SFM_MEAN1,RMS_STD1,ZCR_STD1,SC_STD1,SRO_STD1,SFM_STD1,music … Concretely, the @DATA section should be: 2 @DATA 0.057447,0.191595,128.656296,239.404651,0.329993,0.027113,0.036597,13.206525,27.957121,0.087828,music … 0.062831,0.082504,78.481380,145.886047,0.198849,0.032323,0.070962,39.388633,66.942115,0.133545,speech Note: Please keep at least 6 digits after the decimal point for output. 3. Submit a zip file to IVLE containing your source code (a single .py file) and the ARFF file. Name the zip file using your student number (e.g. A0123456H.zip). 4. Note: You may use any python standard libraries, numpy (including pylab / matplotlib) and scipy. No other libraries are permitted. Late submissions will receive no marks. 5. Grading scheme: • 4/6 marks: correct ARFF file. • 2/6 marks: readable source code (good variable names, clean functions, necessary comments).0. This assignment will use the same “music / speech” dataset that we used for assignments 1. 1. Follow the following steps to complete this assignment: • Read the ground truth music speech.mf file. • Load each wav file and splits the data into buffers of length 1024 with 50% overlap. Only keep complete buffers. • Calculate the MFCCs for each window as specified in the lecture notes. Here are more detailed steps: – Given input x(t) and output y(t), the pre-emphasis filter should be y(t) = x(t) − 0.95x(t − 1). – Use a Hamming window before the mag-spectrum calculation. – Mel-scale of frequency f is: Mel(f) = 1127 ln(1 + f 700 ). – Calculate 26 mel-frequency filters, covering the entire frequency range (from 0 Hz to the Nyquist limit). To calculate the filters, ∗ find the X-axis points of the filters (left side, top, right side). All points must be convereted into integer FFT bins; the left side should use the floor() operation; the top point should use round(); the right point should use ceil(). ∗ assign the left bin to be 0, top bin to be 1.0, right bin to be 0; linearly interpolate between the rest. – the log step should be log base 10. – scipy has DCT built-in: scipy.fftpack.dct() – do not calculate any delta-features • Calculate the mean and standard deviation for each MFCC bin over the entire file. So if there are M MFCC bins in each buffer, you will end up with a feature vector of length 2M for each song. • Write the data to an ARFF file (each line should contain the 26 means, followed by the 26 standard deviations, and finally the class). • Make two plots: the overall range of the triangular windows, and the triangular windows from 0 to 300 Hz. They should match the examples below. 2. Submit a zip file to IVLE containing your program’s source code ((a single .py file), the ARFF file and 2 plots. Name the zip file using your student number (e.g. A0123456H.zip). Late submissions will receive no marks. 3. Note: You may use any python standard libraries, numpy (including pylab / matplotlib) and scipy. No other libraries are permitted. 4. Grading scheme: • 4/9 marks: correct ARFF file. • 2/9 marks: 2 correct plots. • 3/9 marks: readable source code (good variable names, clean functions, necessary comments).1. Visualization Before performing any analysis of data, a good starting point is always trying to visualize it. What does your data look like? To visualize, plot the following pairs of features: • ZCR MEAN TIME (x-axis) and PAR MEAN TIME (y-axis) • ZCR STD TIME (x-axis) and PAR STD TIME (y-axis) Each plot should have axis labels, distinguishable markers and a legend. Save these plots as zcr-par-mean.png and zcr-par-std.png. Hint: you can use the python library arff to load an arff file. Could you use any of these features to distinguish between music and speech? Why? Keep these questions in mind for the next section. 2. Classification Build a classifier to perform classification on the features in the given ARFF file in Weka with trees.LMT (Logistic Model Tree) with 10-fold cross-validation and save the results. Choose at least one other classification algorithm with 10-fold cross-validation to build another classifier, perform classification and save the results. Compare the results of these two algorithms and save your findings to a file called classifications-results.txt. This file should answer at least these three questions: • Which algorithm gives you the best results? • Which features contribute most significantly in classification? • Where do these features come from (time, spectral or perceptual domain) and why do you think these features can contribute? You are encouraged to write down any other findings. After answering these questions, save the Weka results for the two algorithms and put them at the end of the text file. 3. Submit a zip file to IVLE containing the two plots (zcr-par-mean.png, zcr-par-std.png) and the classification-results.txt. Name the zip file using your student number (e.g. A0123456H.zip). Late submissions will receive no marks. 4. Grading scheme: • 3/7 marks: correct and well labeled plots. • 4/7 marks: results and discussion of Weka output.1. Pitch tracking and wav file synthesis Listen to scale.wav and write a program to synthesize a sinusoidal wav file which contains the same notes. You may consider the following steps: • Use open source pitch detection tools to detect the f0 of the notes in scale.wav. Hint: you can use Sonic Visualiser with pYIN plugin. • Check the output of pitch detection and find out the start and end time of each note. • Generate a sine wave for each note and concatenate them together with the same time arrangement as the original scale.wav. • Use a sampling rate of 44100Hz to save your synthesized wav file to sin scale.wav. Hint: use scipy.io.wavfile.write(). • Listen to sin scale.wav and compare it with scale.wav. Why do the same notes sound differently in these two wav files? Save your answer to comparison.txt. Hint: you can plot the time-aligned spectrograms of two wav files to find the difference. 2. Note length modification Choose one of the eight notes in scale.wav and increase the length of it by 2 seconds. You may consider the following steps: • Read the data from scale.wav and plot it. • In the plot, find a single complete period of the note. • Increase the length of the note by looping this period for several times. Hint: you can use numpy.concatenate(). • Save your modified data to long scale.wav. 3. Submit a zip file to IVLE containing your source code, two wav files and your answer to the question (comparison.txt). Name the zip file using your student number (e.g. A0123456H.zip). Late submissions will receive no marks. 4. Grading scheme: • 2/8 marks: correct wav file for task 1. • 2/8 marks: correct answer to the question in task 1. • 2/8 marks: correct wav file for task 2. • 2/8 marks: readable source code.
Developing a C program to support half-duplex layered communication. You are provided with the interface protocols (C function prototypes) for all the layers. You need to implement these layers, including the development of peer-to-peer protocols. You are responsible for implementing the C functions in layers 2,3, 4 and 5 (described below). You do not need to implement layer 1 code – I’ve included a sample layer 1 code along with a sample main program. When testing your submission we will use our own layer 1 that may be very different from the one included here – make sure your code does not depend on any specific layer 1 implementation!Sample code for l1 is in the fold
Objectives In this first project, you will familiarize yourself with VTK while experimenting with several techniques to visualize 2D scalar data. The topic here is geovisualization, in other words the visualization of geographic data. Specifically, you will be visualizing a dataset that combines bathymetry/topography data with satellite imagery of the earth surface. Your visualization will include a graphical user interface that interactively controls certain aspects of the visualization. Background Bathymetry measures the underwater depth of the ocean floor while topography measures land elevation with respect to sea level. Together, they describe the earth surface’s geometry. For simplicity, I use the term elevation below to jointly refer to both. NASA’s Blue Marble project offers high resolution elevation datasets along with satellite imagery of the earth surface acquired at different times of the year. In this project you will learn how to use VTK to create compelling interactive visualizations of the elevation data. Practically, the data consists of grayscale images (relief / topography) and color images (satellite views) with resolutions up to 86400 x 43200 (3.7 gigapixels). In each image, the earth surface is sampled at regular angular intervals spanning the domain [−π, π] × [−π/2, π/2] in spherical coordinates (see illustration below). 1/22/2020 Project 1 – Geovisualization https://www.cs.purdue.edu/homes/cs530/projects/project1.html 2/6 Specifically, each row of the image corresponds to a parallel (line of constant latitude, shown in red), while each column corresponds to a meridian (line of constant longitude, shown in blue). Note that the North and South poles (where parallels degenerate to points) are each represented by an entire row of uniform value. Task 1. Height Map Visualization and Texture Mapping (30%) Task summary Your first task consists in visualizing the elevation dataset through an interactive height map textured with the satellite image. See explanations below. Height map A height map is a mapping from a gray-scale (scalar) image to a curved surface, whereby each position associated with value in the image is mapped to the 3D position . In the case of the elevation dataset, the resulting surface matches (by definition) the earth elevation profile. Computing a height map in VTK is done with the help of the vtkWarpScalar filter, whose basic usage is demonstrated in ImageWarp.py (found here). Interactivity vtkWarpScalar provides a scale factor that allows the user to control the amount by which the image is moved up or down for a given scalar value at each point: is in fact mapped to by the algorithm, where is the scale factor. This control mechanism can be tied to a slider GUI to permit the interactive manipulation of the scale factor and update the visualization accordingly. Texture mapping Height mapping as described previously produces a geometric representation of the Earth’s surface. In the absence of additional visual cues, however, key aspects of the data, such as the continents’ coast lines, remain ambiguous. To remedy this problem you will use the available satellite image through texture mapping. In VTK, textures are stored in vtkTexture objects that can then be supplied to vtkActor to enable texture mapping during the rendering stage. Note that this mapping is only possible if the vertices of the target geometry (here, the height surface) are equipped with texture coordinates that specify their matching location on the texture. It is therefore important to point out that the supplied elevation datasets already contain texture coordinates among the point attributes. Implementation You will write for this task a program that satisfies the following requirements: Import the necessary files (elevation and satellite image) using the appropriate VTK readers (x, y) f (x, y, f) {(x, y), f} (x, y, Kf) K 1/22/2020 Project 1 – Geovisualization https://www.cs.purdue.edu/homes/cs530/projects/project1.html 3/6 Compute a height map representation of the elevation with vtkWarpScalar Texture map the satellite image onto the height map geometry Visualize the result Provide a slider bar GUI to interactively manipulate the scale factor of vtkWarpScalar Maintain consistency between visualization and GUI API Your program will have following API: > heightfield[.py] where is the path of the elevation data file and is the path of the satellite picture. Report Include in your report images of the visualization results produced by your program Make sure to select camera angles that convey the presence of a 3rd dimension Provide several images showing the results obtained for different scale factors Include close-up images Task 2. Isocontours and Color Mapping (30%) Task summary For the second task, you will visualize the elevation dataset using isocontours. Isocontours To highlight specific values of the elevation, one needs isocontours, which are also known as contour lines, isolines, or more formally level sets. An isocontour corresponds to the set of points where the considered function has a particular value (the pre-image of that function at that value). In 2D, isocontours form closed curves. Note that we will study this topic in great detail when we consider isosurfaces in the coming weeks. By selecting a number of discrete values between the minimum and the maximum values of the data set one can get a good illustration of the value distribution across the domain. To compute isocontours in the elevation dataset you will use vtkContourFilter, the API of which is discussed here. Specifically, you will create a visualization that shows isocontours associated with elevation values ranging from -10,000 meters to +8,000 meters in 1,000 meters increments. To improve the clarity of your visualization, you will wrap the isocontour into tubes using vtkTubeFilter. Note that the radius of your tubes must be selected carefully (not too big to avoid occlusion and not too small to make them easily distinguishable). To facilitate this selection you will create a GUI slider that lets you interactively modify this radius. In addition, you will apply a color map to the isocontours, in other words, assign to each isocontour a color that represents its value. Here, I am asking you to use the color scale shown below, where the maximal ocean depth will be mapped to blue, the maximum mountain height will be mapped to yellow, and values close to the sea level (either positive or negative) will be mapped to desaturated colors. The sea level itself (elevation 0) will be shown in red. Note that color maps in VTK are defined through vtkColorTransferFunction that are then supplied to the mapper via mapper.SetLookupTable(), where is the name of your color transfer function. To provide context to the isocontours, you will apply the same texture mapping solution as in the previous task, this time however to a flat geometry. Observe that you may need to tweak the blue and yellow ends of the color map defined above to improve the contrast of your isocontours with the underlying satellite image. 1/22/2020 Project 1 – Geovisualization https://www.cs.purdue.edu/homes/cs530/projects/project1.html 4/6 Implementation You will write for this task a program that meets the following requirements: Import the elevation dataset and satellite using the appropriate VTK readers Define a vtkContourFilter to create a series of isocontours in 1,000 meters increments in the interval -10,000 meters to +8,000 meters. Display the resulting curves as tubes using vtkTubeFilter Color the tubes using the indicated color scale and vtkColorTransferFunction Provide a GUI slider bar to control the radius of the tubes Texture map a satellite image to the dataset Keep visualization and GUI selection consistent API The API for your program should be as follows: > isocontour[.py] where is the path of the elevation data file and is the path of the satellite picture. Report Include in your report high quality images of the results produced by your program Provide images showing the results obtained for several radius selections Include close-up images Task 3. Putting It All Together On A Sphere (30%) Task summary For this third and final task, you will integrate height field representation, texture mapping, and isocontours and display them on a sphere to create a compelling visualization of the elevation dataset. Interactive scalar field visualization The fourth task in this project consists in combining the various visualization techniques that you implemented previously in a single visualization. Specifically, you should write a program that displays the elevation dataset as a height field, applies to it the satellite imagery using texture mapping (as done in Task 1), and visualizes isocontours as tubes (cf. Task 2). As discussed previously, your visualization should include a slider bar to control the scaling factor of the height field representation. Note that you will set the radius of the isocontours to a fixed value that you found appropriate in Task 2). Mapping to a sphere In contrast to what you did so far, you will display height field, texture, and isocontours on a sphere instead of a plane. Indeed, the results achieved so far do not convey the actual shape of the various continents due to the significant distortion that is caused by the latitude / longitude parameterization of the image. To remedy this problem we need to visualize the data directly on a sphere. To make your task easier, I am providing you with a sphere dataset that contains elevation values, normals, and texture coordinates. Note that the sphere that I am giving you is already scaled to the radius of the earth (in meters). Implementation You will write for this task a program that satisfies the following requirements: Import the elevation dataset on a sphere and satellite image using the appropriate VTK readers Apply vtkWarpScalar to visualize the elevation data as height field Provide a slider bar to control the scaling factor of vtkWarpScalar Texture map the satellite image onto the height field 1/22/2020 Project 1 – Geovisualization https://www.cs.purdue.edu/homes/cs530/projects/project1.html 5/6 Apply vtkContourFilter to create a series of isocontours in 1,000 meters increments in the interval -10,000 meters to +8,000 meters Display the resulting curves as tubes using vtkTubeFilter Color the tubes using the prescribed color map and vtkColorTransferFunction Draw the tubes directly on the height field Keep visualization and GUI selection consistent API The API for your program should be as follows: > view_earth[.py] where is the path of the elevation on a sphere data file and is the path of the satellite image. Report Include in your report high quality images of the results produced by your program Provide images showing the results obtained for several scaling factors Include images that show you results for different parts of the world and different camera perspectives Include close-up images Discussion (10%) Answer the following questions in your report. Be as specific as possible and draw from your experience in this assignment to justify your opinion. Considering the height map technique used in Task 1: 1. What properties of the dataset were effectively visualized with this technique? 2. What are in your opinion the main limitations of this technique and how could you address them? 3. How useful did you find the slider interface in your usage of the height field representation? 4. How effective do you find this visualization technique for this dataset? Considering the level sets considered in Task 2: 1. What specific aspects of the data were readily visible with isocontours? 2. How useful did you find the color map and why? Considering the sphere representation in Task 3: 1. What benefits did you see to the perform the visualization on a sphere? 2. How did the resulting visualization compare to the previous ones? Considering your findings in tasks 1, 2, and 3: 1. Did you find that the combined use of these visualization techniques in Task 3 improved upon the results of each technique applied separately? Why or why not? Datasets As indicated in preamble, the data used in this project is courtesy of NASA Earth Observatory and available on the web site of the Blue Marble project. Since the server can be slow at times, I am providing you with a local copy of the relevant files. Note that I converted the bathymetry / topography datasets to a single vtkImageData to simplify your programs. The dataset is available in 4 different resolutions for convenience. Similarly, the satellite image of the Earth is provided in 3 different resolutions. In both cases, use a low resolution version to test your implementation and use for your report the highest resolution that your computer can 1/22/2020 Project 1 – Geovisualization https://www.cs.purdue.edu/homes/cs530/projects/project1.html 6/6 handle. Note that some of these files are really large (see below) so make sure to download only what you need. Elevation datasets: small version: 540 x 270, 1.6 MB medium version: 1080 x 540, 6.0 MB large version: 2160 x 1080, 24 MB very large version: 4320 x 2160, 89 MB Same elevation datasets on sphere geometry: small version: 540 x 270, 9.2 MB medium version: 1080 x 540, 38 MB large version: 2160 x 1080, 152 MB very large version: 4320 x 2160, 608 MB Satellite image: medium version: 2160 x 1080, 573 KB large version: 5400 x 2700, 2.3 MB (very) large version: 21600 x 10800, 36 MB Report Please refer to the class syllabus for late policy and formatting guidelines of project reports. Your report should also contain your answers to the questions asked in the discussion section. As a reminder, this project must be completed individually. Submission Submit your project on Blackboard before February 4 at 11:59:59 pm. Please observe following instructions. Include the 3 program files along with any other source code you may have Make sure that your programs have the correct API! Include high resolution sample images showing results for each task. Include a PDF report describing what you have done and answering the questions asked above. The report should include high-resolution images. Additional images can be provided as part of the project submission. Include all submitted files in a single tar zip’ed directory named _p1, where is your Purdue login. Do not include any binary file Do not include any data files Do not use hardcoded paths (relative or absolute) in your programs.Objective The second assignment focuses on the visualization of three-dimensional scalar fields using isosurfaces. Specifically, we will consider a medical imaging dataset corresponding to CT scans of a female subject. Your objective will be to combine isosurfaces, transparency, clipping planes and color mapping to reveal in your visualization important anatomical structures present in the data. Background The data corresponds to CT scans of a human female head and feet, courtesy of the Visible Human Project. For each dataset I am providing you with both high and low resolution versions. The small resolution was created by halving the size of the original data along each direction (it is therefore 8 times smaller). For each resolution, you will find both a CT volume and an additional dataset corresponding to the magnitude of the gradient of the CT image. As a reminder, the gradient of a scalar field is the vector-valued derivative of the scalar field. Here however, we are only interested in the magnitude of the derivative. In each case, the CT data is of type unsigned short, yielding values between 0 and 65535, while the gradient magnitude data is of type float. Note that the small resolution is mainly provided as a convenience for the testing phase of your implementation and I expect to see high quality results at full resolution in your reports. The interesting features in this dataset 2/8/2020 Programming Assignment 2 – Isosurfaces https://www.cs.purdue.edu/homes/cs530/projects/project2.html 2/6 correspond to skin, bones, and muscles. Note that other soft tissues (e.g., fat or brain) are too difficult to extract. Overview Your experimentation with the head dataset should allow you to identify values that correspond to the skin, skull, and muscles. In the foot dataset, you will use isosurfaces to reveal the bone structure as well the skin and surrounding muscles. Note that for each dataset, the CT and gradient magnitude volumes will offer you complementary means to identify interesting features. To permit the selection of good isovalues, you will create a GUI that will let you select individual values associated with the various structures you are looking for. A slider bar will allow you to interactively browse the value range in search for the proper isovalue, while two additional slider bars will allow you to select a range of gradient magnitudes to act as a filter on the constructed isosurface. To mitigate the occlusion caused by the nested structure of the surfaces, you will be using transparency and clipping planes. The latter will allow you to cut away the occluding part of the surfaces to reveal internal structures. Finally you will use color mapping to convey quantitative properties of the selected isosurfaces. Task 1 – Interactive Isosurfacing The first task in this project consists in visualizing a 3D scalar dataset using isosurfacing while supporting the interactive modification of the corresponding isovalue. This initial step will allow you to identify a set of isovalues that correspond to the major anatomical structures present in each dataset. Specifically, skin, bones, and muscles. Implementation Write a program that uses vtkContourFilter to extract isosurfaces and ties it to a slider bar GUI to interactively manipulate the isovalue. To address occlusion issues, your program will offer interactive control over three clipping planes implemented as a vtkClipPolyData filter used with an implicit function called vtkPlanes, which allows you to clip away portions of the volume to reveal internal structures. You will also add a color bar to your render window to show the meaning of the colors used in your visualization. This is done with the help of vtkScalarBarActor. An example showing how to use this class is available here. Note that this example uses a data file contained in the VTKData distribution. If you do not have it, it can be found on github. Specifically, your program must satisfy following requirements. Take in input the name of the scalar volume to be visualized from the command line Perform an isosurface visualization of the dataset Provide a slider bar to control the isovalue to be used within a range of interesting values Ensure consistency between slider bar selection and isosurface Provide three additional slider bars GUI to control the position of three clipping planes moving along the X, Y, and Z coordinate axis, respectively Show the color scale through a color bar Optionally import the initial isovalue and initial X, Y, and Z clipping plane positions from the command line API Your program will have following API: > python isosurface.py [–val ] [–clip ] where is the 3D scalar dataset to visualize, is the optional initial isovalue to be used by the program, and are the optional initial positions of the 3 clipping planes. Report Include in your report high-quality images showing each of the major anatomical structures that you were able to extract with isosurfaces. Each image should include a color bar. Indicate the isovalues that you identified for each structure and the visual settings associated with each visualization. Use clipping planes at your discretion 2/8/2020 Programming Assignment 2 – Isosurfaces https://www.cs.purdue.edu/homes/cs530/projects/project2.html 3/6 to facilitate the visual inspection of your results. In addition, include answers to following questions in your report. 1. Which isosurfaces look the most interesting? Justify your answer. 2. How did you select the position of clipping planes? Task 2 – Value vs. Gradient Magnitude Now that you have identified interesting isosurfaces corresponding to major anatomical structures in each dataset, your second task is to color map the value of the gradient magnitude on those isosurfaces. In other words, you will visualize the values that the gradient magnitude takes at the set of positions defined by each isosurface. This visualization should give you additional insight into the properties of each isosurface. Implementation Write a program that takes both scalar volume and gradient magnitude in input as well as a set of pre-selected isovalues in Task 1 and perform the color coding of the gradient magnitude on the isosurfaces. More precisely, you will use vtkProbeFilter jointly on the geometry of the isosurfaces and on the gradient magnitude volume to associate each vertex of the isosurfaces with the corresponding gradient magnitude value. The color mapping itself will be controlled by a color map supplied by the user. Specifically, your program must meet following requirements: Take in input the name of the scalar volume and the corresponding gradient magnitude volume from the command line Take in input the name of a file containing a set of isovalues (1) to be used for isosurface extraction Perform the resampling of the gradient magnitude on these isosurfaces and apply color mapping to visualize the resulting values Optionally take in input a color map to be used for the color mapping of gradient magnitude on the isosurfaces, otherwise resort to a default color map Provide the same three sliders GUI (2) used in Task 1 to control the position of 3 clipping planes to be used in the visualization Include a color bar to document the selected color map Notes (1) The isovalues to be used by the program must be included in a file (see API below). (2) The GUI only controls the clipping planes. There is no isovalue slider for this task. API Your program will have following API: > python isogm.py [–cmap ] [–clip ] where is the 3D scalar dataset, is the corresponding gradient magnitude, is the name of a file containing the isovalues to be used, is the optional name of a file containing a color map definition with following syntax: Lines preceded by the character ‘#’ are comments and should be ignored Each non-comment line must contain a scalar value followed by the R, G, and B values of the associated color. Finally, are the optional initial positions of the 3 clipping planes. Report Include in your report images of the color mapped isosurfaces computed by your program. Indicate clearly for each surface the corresponding isovalue. Each image should include a color bar. In addition, answer following questions: 2/8/2020 Programming Assignment 2 – Isosurfaces https://www.cs.purdue.edu/homes/cs530/projects/project2.html 4/6 1. What differences can you identify between the various isosurfaces in terms of their associated gradient magnitude distribution? 2. How do you interpret these results? Justify your answer. 3. What does that tell you about the value of the resulting visualization? Explain. Task 3 – Two-dimensional Transfer Function Combining the insight you gained from Task 1 and Task 2 you will now use the gradient magnitude data to filter out unwanted portions of your isosurfaces. Specifically, Task 2 has shown you what values of the gradient magnitude coincide with certain portions of your isosurface. You can therefore use this information to discard from an isosurface uninteresting portions by specifying a gradient magnitude interval outside which isosurface points should be removed. This kind of downstream filtering can be achieved by using vtkClipPolyData again but this time you will be applying it directly to the gradient magnitude values attached to the vertices of the isosurface. In fact, you will need to use two such filters for a given gradient magnitude interval, one to discard all the values less than and one to discard all the values larger than among the values that passed the first filtering stage. Implementation You will write a program similar to the one you wrote for Task 2 except that this time, the gradient magnitude information will not be directly displayed on the isosurface after resampling but instead used to determine which points should be removed from the isosurface in the visualization pipeline. Your program should allow the user to interactively modify the selection interval to facilitate the identification of an optimal range. Specifically, your program should meet following requirements: Take in input the name of both scalar volume and gradient magnitude datasets to be processed from the command line Optionally take in input the initial isovalue to consider Provide a GUI with two slider bars to allow the user to control the range (min et max) of gradient magnitude values to select Provide an additional slider bar to control the value of the selected isovalue Provide the same GUI as in Task 1 to control the position of 3 clipping planes to be used in the visualization Perform a resampling of the gradient magnitude on the isosurface Filter the isosurface using two consecutive vtkClipPolyData consistent with the gradient magnitude range currently selected Visualize the resulting filtered isosurface Note that in contrast to Task 2, you will only be considering one isosurface at a time here. This is meant to facilitate the adjustment of the gradient magnitude range on a per surface basis. API Your program will have following API: > python iso2dtf.py [–val ] [–clip ] where is the 3D scalar dataset and is the corresponding gradient magnitude to visualize, and are the optional initial positions of the 3 clipping planes. Report Include in your report high quality images for each dataset, corresponding to each filtered isosurface, while precisely indicating the matching isovalue. Indicate for each visualization which parameters / visual settings were used to create the image. In addition, provide an answer to following questions, with images to support your answers as necessary. [gradm , gra ] in dmax gradmin gradmax [gradm , gra ] in dmax 2/8/2020 Programming Assignment 2 – Isosurfaces https://www.cs.purdue.edu/homes/cs530/projects/project2.html 5/6 1. To what extent did the gradient magnitude filtering help in refining the isosurface selection? Be specific. 2. Which isosurfaces benefited the most from this filtering? Why? Task 4 – Complete visualization Using the isovalues that you identified in Task 1 and the gradient magnitude filtering ranges that you discovered in Task 3 to precisely characterize the various anatomical structures present in the data, you will now create a visualization where all the filtered isosurfaces are shown simultaneously using color and transparency. Implementation For this final implementation task, you will write a program that incorporates the various features of the programs written so far and uses transparency in addition to clipping planes to allow for all relevant isosurfaces to be shown simultaneously without excessive occlusion. Remember to use Depth Peeling to achieve correct transparency results! Specifically, your program must satisfy following requirements. Take in input from the command line the name of both scalar volume and gradient magnitude datasets to be processed Take in input the name of a file that specifies, for each isosurface, the corresponding isovalue, the associated gradient magnitude range, and the associated color and transparency. Perform a resampling of the gradient magnitude on each isosurface Filter each isosurface using two consecutive vtkClipPolyData consistent with the gradient magnitude range selected for that isosurface Visualize the resulting filtered isosurfaces with correct colors and transparency Provide the same GUI as in Task 1 to control the position of 3 clipping planes to be used in the visualization API Your program will have following API: > python isocomplete.py [–clip ] where is the 3D scalar dataset, is the corresponding gradient magnitude to visualize, is the name of a file containing all the information necessary to select, filter, and visualize the isosurfaces. The format of this file will be as follows. Lines starting with ‘#’ will be considered comments and ignored. Each following non-comment line that is not a comment will indicate an isovalue, a gradient magnitude range (min then max value), a RGB color and an opacity. It will have the form ” ” where ” ” indicates the gradient magnitude filtering range for the isosurface, ” specify the color associated with , and is the associated opacity. Report Include in your report, high quality images showing the results produced by your method for your particular selection of parameters for each dataset. Comment on your selection of the transparency for each isosurface. How does transparency benefit your visualization? Explain. Summary Analysis Comment on the effectiveness of isosurfaces for these medical imaging datasets in your report. Isosurfaces in general are widely used in medical applications. 1. What explanation can you propose for this success? 2/8/2020 Programming Assignment 2 – Isosurfaces https://www.cs.purdue.edu/homes/cs530/projects/project2.html 6/6 2. Comment on the quality of the images you were able to obtain in each case. 3. Discuss any shortcomings of the isosurfacing technique you may have come across in this project. 4. Comment on the role and meaning of gradient magnitude to filter isosurfaces. 5. Comment on the benefits and limitations of transparency and clipping planes to enhance the visualization. Datasets The datasets are available online. All datasets are of type vtkStructuredPoints, which is itself a specialized type of vtkImageData. Feet: CT (small, large), gradient magnitude (small, large) Head: CT (small, large), gradient magnitude (small, large) Submission Submit your solution for this project on Blackboard before February 18, 2020, 11:59 pm. Refer to the instructions below. Include all program files Make sure that your programs have the correct API! For Task 4, include the necessary parameter file for each dataset named head_params.txt and feet_params.txt. Include high resolution sample images showing results for each task. Include a html or PDF report summarizing what you have done and answering all the questions asked. The report should include high-resolution images. Include all submitted files in a single directory named _p2, where is your Purdue login. Do not include binary file Do not include data files Do not use absolute paths in your code Objective The topic of this assignment is the visualization of 3D scalar fields through direct volume rendering. You will experiment with transfer function design and revisit some of the tasks of the second assignment to compare the effectiveness of isosurfacing and volume rendering in two application scenarios. Specifically, you will apply volume rendering to a medical dataset (similar to the CT volume used in the previous assignment) and to a computational fluid dynamics (CFD) simulation of turbulent combustion. Background The key to achieving good results with volume rendering is to select an effective transfer function. We saw in class that a good transfer function should reveal boundaries present in the volume, when such boundaries exist. When clear boundaries are not present, the transfer function should be designed to reveal important geometric structures in the data. In this assignment, you will be working with two datasets that illustrate these two scenarios: the CT dataset contains boundaries corresponding to the interface between different tissue types while the CFD dataset describes the spatial distribution of vorticity in a turbulent combustion and is globally smooth. The project starts by asking you to identify remarkable (iso)values in each dataset, which you will then 10/16/21, 10:23 PM Programming Assignment 3 – Volume Rendering and Transfer Functions https://www.cs.purdue.edu/homes/cs530/projects/project3.html 2/4 use as reference points to create your transfer function. The third part of the project invites you to compare the respective pros and cons of volume rendering and isosurfacing in the context of these two datasets. Tasks Task 1: Important Isosurfaces Your first task consists in determining for each dataset a set of isovalues that capture salient (remarkable) structures in the considered field. To do so, you will use the code that you wrote for the second assignment to identify important isosurfaces. In the case of the head dataset, salient isosurfaces capture boundaries corresponding to the skin, muscles, skull (and teeth). In the case of the combustion dataset, you will look for isosurfaces that reveal the sheet and tubular structures that are present in the flame. Bear in mind that fuzzy structures might be poorly captured by isovalues. Using different opacities for different isosurfaces, create for each dataset a visualization showing all isosurfaces simultaneously. Deliverables: Create two executables for this task: salient_head.py and salient_flame.py that each contain the (hardcoded) information needed to visualize the salient isosurfaces of the corresponding dataset using transparency. In both cases, your executable will obtain the name of the file to visualize from the command line (which allows us to specify an arbitrary location and resolution for the input file). > python salient_head.py > python salient_flame.py Report: Describe in the report how you selected the isovalues for each dataset. Include pictures showing each isosurface individually and other images showing all isosurfaces combined using transparency. Make sure to use the same camera setting across all images corresponding to the same dataset. To that end, refer to the code sample that showed you how to print out the current camera setting during an interactive session as well as save the current frame to file. Once you identify a suitable camera position, simply hard code the corresponding parameters in your program or create a mechanism to import those settings from file on the command line. Task 2: Transfer Function Design Now that you have found good isovalues, you will design a transfer function for each dataset based upon those values. For that, create a vtkVolumeProperty by following the example provided in Examples/VolumeRendering/Python/SimpleRayCast.py to define both color and opacity transfer functions in order to emphasize the selected isovalues. You are already familiar with vtkColorTransferFunctions from previous assignments. The opacity transfer function is defined through a vtkPiecewiseFunction. Your objective in designing the opacity transfer function is to reveal as much as possible of the internal structures of each dataset. The volume rendering itself will be performed by raycasting using a vtkSmartVolumeMapper. Note that this implementation will automatically determine the hardware resources available and perform GPU-based raycasting whenever possible. Select the compositing blend mode of vtkSmartVolumeMapper for value compositing along each ray. Your implementation should produce high-quality renderings by combining trilinear interpolation and small sampling distance along each ray: you will select SetInterpolationTypeToLinear() in the API of vtkVolumeProperty and manipulate the discretization along each ray via SetSampleDistance(). You will need to experiment with different values of the sampling distance to determine the precision necessary to obtain good results. Good results in particular should not exhibit aliasing artifacts such as moiré effect. Note that an appropriate value of the sampling distance depends both on the smoothness of the data and on the properties of your transfer function. Finally, you should activate the shading option (via ShadeOn() in vtkVolumeProperty()) in your rendering to further improve the visual quality of your results. Deliverables: create two executables dvr_head.py and dvr_flame.py that contain the information necessary to create high quality renderings of the corresponding dataset. In particular, the opacity and color 10/16/21, 10:23 PM Programming Assignment 3 – Volume Rendering and Transfer Functions https://www.cs.purdue.edu/homes/cs530/projects/project3.html 3/4 transfer functions must be hard coded in these programs. Like for the first task, your executables must obtain the name of the data file from the command line. > python dvr_head.py > python dvr_flame.py Report: Provide a detailed description (including diagram) of the various transfer functions you created along with a justification of the choices made. What method did you use to create each opacity transfer function? What do you consider to be the strengths and limitations of your solutions? Include in the report several images for each dataset that highlight the effectiveness of your transfer function and the quality of your volume rendering parameters. Task 3: Volume Rendering vs. Isosurfacing Provide for each dataset a side by side comparison between the results obtained for isosurfacing (Task 1) and volume rendering (Task 2). Make sure to use the same camera settings for both techniques in order to facilitate their comparison. No additional code should be written for this task: simply use the executables created for the previous tasks to create the images that will be included in the report. Report: Comment on the differences between the two techniques. Illustrate your argumentation by zooming on particular features of each volume. For each dataset, which technique do you find most effective? Why? Be specific. Summary Analysis Include in the report your critical assessment of volume rendering: What are in your opinion the pros and cons of this technique? Refer to the tasks of this project to justify your opinion. Data Sets You will be visualizing two datasets for this assignment. The first one is a head CT scan dataset similar to what you used for Project 2. Here, the data corresponds to a male subject, part of the Visible Human Project (National Library of Medicine). The second dataset corresponds to a computational fluid dynamics simulation of a turbulent combustion. In this case the provided scalar volume corresponds to the magnitude of the vorticity field, a quantity that is derived from the flow velocity and can be used to identify vortices in numerical datasets. Note that both datasets have been low-pass filtered (“smoothed”) to facilitate their visualization (e.g., reduce aliasing issues). The datasets are available online. All datasets are of type vtkStructuredPoints. Visible Male Head: CT scan, low resolution (unsigned short, 12.2MB) CT scan, high-resolution (unsigned short, 98MB) CFD Dataset: Vorticity magnitude (low-resolution) (unsigned short, 2.6MB) Vorticity magnitude (high-resolution) (unsigned short, 18.5MB) Submission Submit your solution for this project on Blackboard before March 15, 2021 at 11:59:59 pm. Refer to the instructions below. Include all program files (salient_head.py, salient_flame.py, dvr_head.py, dvr_flame.py) along with any other source code you may have. 10/16/21, 10:23 PM Programming Assignment 3 – Volume Rendering and Transfer Functions https://www.cs.purdue.edu/homes/cs530/projects/project3.html 4/4 Include high resolution sample images showing results for each task. Include a report briefly summarizing what you have done and answering all the questions asked. As always, the report should include high-resolution images. Include README.txt file with execution instructions (optional). Include all submitted files in a single directory named _p3, where is your Purdue login. Do not include binary file Do not include data files Do not use absolute paths in your codeObjective The topic of this assignment is vector field / flow visualization. You will study a delta wing dataset and visualize the velocity information using vector field visualization techniques. Your task will be to show the major flow structures present in the dataset (primary and secondary vortices and recirculation bubble on each side of the wing). In addition, you will visualize the spatial relationship that exists between the velocity (vector) field and the pressure (scalar) field. Refer to the corresponding instructions below. Task 1: Glyphs [20%] Your first task consists in using cutting planes to probe the vector values. Specifically, you will create a plane orthogonal to the X axis of the volume (the main axis of the wing) and sample the velocity vector field on that plane. You will need to follow an approach similar to what is demonstrated in ProbeCombustor.py for that purpose. To represent individual vectors as arrows, you will use vtkArrowSource as the source of a vtkGlyph3D filter. Use 3 plane at 3 different locations along the X axis (with normal pointing along the X direction) to capture the structures mentioned above. Show the delta wing geometry in each image for context (the corresponding geometry is provided as vtkUnstructuredGrid in a separate file). Deliverables: Create an executable named three_planes.py that contains the (hardcoded) information needed to visualize the vector glyphs on the 3 planes that you have selected. Your executable should receive the names of two files from the command line, namely the CFD file containing the vector field information and the file containing the geometry of the delta wing. > python three_planes.py Report: Explain in the report how you selected the planes used in your implementation and comment on the properties of the flow that you can discern in your visualization. Include pictures showing each cutting plane 10/16/21, 10:24 PM Programming Assignment 4 – Flow Visualization https://www.cs.purdue.edu/homes/cs530/projects/project4.html 2/3 individually (along with the associated glyphs) as well as other images showing all planes and the wing together. Task 2: Streamlines, Stream Tubes and Stream Surfaces [40%] Task 1 should provide you with a general sense of the location of interesting structures in the flow volume. Your second task now consists in using streamlines, stream tubes and stream surfaces as demonstrated in officeTubes.py and streamSurface.py to show how the flow swirls around the vortices present in the data. Deliverables: You will construct 3 visualizations for this task. A first executable showing a large number (between 50 and 200) of streamlines. A second executable showing a small number of stream tubes A third executable showing a stream surface seeded along an appropriately chosen line segment (aka rake). In each case, the seeding locations and the other parameters of the technique must be hardcoded in your program. You must choose parameter values that produce good quality results and capture the behavior of the flow around the vortices on each side of the wing. Note that each visualization should represent the velocity magnitude using color coding and the corresponding color scale should be provided for reference. Show the delta wing geometry in each image for context. > streamlines > streamtubes > streamsurfaces Report: Explain in the report how the seeding locations were chosen for each of these three techniques and how they relate to the observations made in Task 1. Task 3: Combining Scalar and Vector Visualization [20%] The scalar and vector information available for this dataset provide two complementary perspectives on the properties of the flow. For the third task of this assignment, you will combine isosurfaces of pressure with streamlines to visualize the relationship between the streamlines’ geometry and the shape of the isosurfaces. Create visualizations in which the streamline seeds and the isovalues of the isosurface are chosen in such a way as to best illustrate the correlation between the two kinds of object. Deliverables: Create an executable named combined.py that produces a visualization of the CFD dataset, combining isosurfaces of the pressure scalar field, streamlines of the velocity vector field, and geometry of the delta wing. The various parameters needed to create the visualization must be hardcoded in the program. Your executable should receive from the command line the names of the files needed to create the visualization: velocity and pressure dataset (in the same file), and wing geometry description. > python combined.py Report: Describe in the report the things you tried before arriving at the proposed solution and explain why your final selection is a good one. Show the delta wing geometry in each image for context. Task 4: Analysis [20%] 10/16/21, 10:24 PM Programming Assignment 4 – Flow Visualization https://www.cs.purdue.edu/homes/cs530/projects/project4.html 3/3 Considering your results in Task 1 and Task 2 of the assignment, comment on the effectiveness of the resulting visualizations for your understanding of this dataset. What were the pros and cons of each technique? Comment on the results you were able to achieve in Task 3 by integrating isosurfacing and vector visualization. Did you find this combination beneficial? Provide a justified answer to each of these questions in the report. Data Sets The CFD dataset used in this project is a available as a (fairly) large vtkUnstructuredGrid. The information available corresponds to the velocity (vector field) and the pressure (a scalar field). A separate file describing the geometry of the delta wing is also available (also a vtkUnstructuredGrid). Note that the CFD simulation that produced this dataset used adaptive mesh refinement, which explains the vast discrepancies that exist between the resolution of the mesh next to the wing and further away from it. 3D Flow: Velocity (vector field), and Pressure (scalar field) in double precision (vfem.vtu, 170 MB) Wing geometry (wing.vtu, 1.0 MB ) Submission Submit your solution for this project on Brightspace before April 1, 2021 at 11:59 pm. Refer to the instructions below. Include all program files (three_planes.py, streamlines.py, streamtubes.py, streamsurfaces.py, combined.py) along with any other source code you may have. Include high resolution sample images showing results for each task. Include a report summarizing what you have done and answering all the questions asked. As always, the report should include high-resolution images. Include a README.txt file with execution instructions (optional). Include all files to be submitted in a single directory named _p4, where is your Purdue login. Do not include binary file Do not include data files Do not use absolute paths in your code Use Brightspace for your submission.
1. Introduction You will implement a C++ program to decode different string of number from the input file then filtering out the information requested by the command file. This assignment focusses on array management and string handling in C++. You will also learn about string manipulation with predefined string utility functions and basic file operations. 2. Input files – The input file will contain a list of encoded id number. The input can range anywhere from 0 to 100 entries. Input might contain empty lines and spaces (empty lines and spaces need to be removed to process each entry correctly). – Each entry will be on its own line and have 2 different parts, coded characters set and id string. – The id string will consist of digits, alphabet characters, and the hash sign. – Alphabet characters in the id string will always have a number representation for it in the characters set, separated by a colon. – Semicolon is used to separate characters in the set and id string. – The id string will always come after the characters set in the entry. – Valid entry should have all 2 parts, the characters set and the id string. – Invalid entry should be ignored. – Example of valid entry: a:123;b:456;c:789;id:c11ba3#2b#a *characters set in yellow, id string in green – Example of invalid entry: a:123;b:456;c:789 – missing id string id:c11ba3#2b#a – missing characters set 3. Decoding process Example input: a:123;b:456;c:789;id:c11ba3#2b#a o Replace all the alphabet characters in the id string with its number representation in the characters set. a:123;b:456;c:789;id:c11ba3#2b#a 789114561233#2456#123 o The hash sign should be replaced by its index in the id string (after replacing all the alphabet). The first hash sign is at index 12, and the second hash sign is at index 17 789114561233#2456#123 12 17 78911456123312245617123 4. Command files – The command file will contain different criteria for filtering out id. – There will be a total of two types (case sensitive): “first4” and “last4”. o first4: those id that have its first 4 digits match with the value given in the command. o last4: those id that have its last 4 digits match with the value given in the command. – The criteria and its value will be separated by a colon. Ex: “first4:1234”, “last4:6789”. – If multiple value appears for the same criteria in the command file, then as long as the id satisfy one of those value then it should be printed to the output. o Ex: “first4:1234”, “first4:6789” => id that have 1234 or 6789 as the first 4 digits should be printed to the output. – If both criteria appear in the command file, then the id must satisfy with one of the values of each criteria in order to be in the output. o Ex: “first4:1234”, “first4:6789”, “last4:1357”, “last4:2468” = > id that have 1234 or 6789 as the first 4 digits and 1357 or 2468 as the last 4 digits should be printed to the output. – Each value in the command will be on its own line, there might be empty lines and spaces. – If the command is empty, all the valid id should be printed to the output. 5. Output files – The output file should contain all the valid id filtered out by the command file in the order they appeared in the input file (empty lines and spaced should be removed). – Each entry should be on its own line. – If there are no id that satisfy the criteria in the command file, then the output file should be empty. 6. Requirements Homework is individual. Your homework will be automatically screened for code plagiarism against code from the other students and code from external sources. Code that is copied from another student (for instance, renaming variables, changing for and while loops, changing indentation, etc. will be treated as copy) will be detected and result in ”0” in this homework. The limit is 50% similarity. 7. Turn in your homework Homework 1 needs to be turned in to our Linux server, follow the link here https://rizk.netlify.app/courses/cosc2430/2_resources/ Make sure to create a folder under your root directory, name it “hw1” (case sensitive), copy all your .cpp and .h file to this folder, “ArgumentManager.h” need to be included as well. PS: This document may have typos, if you think something illogical, please email TAs for confirmation.1. Introduction Given a list of credentials as input, you will need to implement a C++ program to add these input objects into a linked list. Within the linked list, your program needs to perform different adding, removing and sorting operations base on the given commands. This homework will focus on linked list implementation and simple sorting techniques. When submit your assignment, please name the folder on the server as “hw2”. 2. Input files – The input file will contain a list of credentials (ranging from 0 to 100). – Each credential represents a node in the linked list and should be added one by one to the end of the linked list. – Each credential will have four attributes: id, username, score, and grade. o Note: id will always contain 4 digits ranging from 0 to 9. username will always contain lowercase alphabet character (a – z), no spaces or special character included. score will range from 0 to 100. grade is given between A, B, C, D, and F. – The formatting of each credential is as follow: [id:value;username:value;score:value;grade:value] – Valid credential should have all attributes present and appear in this order: id, username, score, grade. o Example of valid credential: [id:1234;username:spongebob;score:100;grade:A] o Example of invalid credential: [id:1234;username:steve;grade:C] – missing attribute: score [id:1234;grade:B;score:85;username:batman] – out of order – Invalid credential should be ignored. – The input will not contain any empty lines or blank spaces. – In the case when the input is empty, continue to process the command. – While reading the input, and r should be removed before processing string. – Input might contain duplicate id credential or duplicate username credential, please read section 5 below on how to process duplicate cases. 3. Command files – There will be three types of command: Add, Remove, and Sort. The commands should be executed in the order that they appear (latter command should always run based on the former command’s result). o Add (index) [credential] ▪ The Add command will be followed by an integer inside parenthesis (represent the index in the linked list to be added) and then followed by a credential. ▪ If index = 0, meaning the credential should be added at the beginning of the linked list. ▪ If the index = size of the linked list, meaning the credential should be added at the end of the linked list. ▪ If the index > size of the linked list, meaning index out of bound, in this case the credential should not be added to the linked list. ▪ Ex: Add (0) [id:1234;username:tom;score:50;grade:F] add this credential at the beginning of the list ▪ Ex: Add (3) [id:1234;username:tom;score:50;grade:F] add this credential at the third index of the list, if not out of bound ▪ Add command might contain duplicate id credential or duplicate username credential, please read section 5 below on how to process duplicate cases. o Remove (attribute:value) ▪ The Remove command will be followed by an attribute and its value (placed inside parenthesis). ▪ Every credential that contains the attribute with the matching value should be removed from the linked list. ▪ Ex: Remove [grade:C] remove every credential that contain value “C” in attribute “grade”. o Sort (attribute) ▪ Sort the linked list base on the given attribute (placed inside parenthesis). ▪ Sort ascending for id. ▪ Sort alphabetically for username and grade. ▪ Sort descending for score. ▪ When sorting if two values are similar, don’t swap their position. – The command will not contain any empty lines or blank spaces. – While reading the command, and r should be removed before processing string. 4. Output files – The output file should display every credential in your linked list after executing all the command in the command file. – Each credential will be on its own line. 5. Adding Operations – When adding a credential to the linked list, the credential might contain duplicate id or duplicate username. – In the case when the credential contains duplicate id, update the previous credential’s attributes with the new credential’s attributes. o Ex: If the credential [id:2468;username:onion;score:75;grade:C] is in the linked list when adding [id:2468;username:lettuce;score:50;grade:F], since the two credential have matching id, update the username, score, and grade of the credential in the linked list to the latter credential. The username for id:2468 should be updated to lettuce, the score should be updated to 50, and the grade should be updated to F. – In the case when the credential contains duplicate username (but doesn’t have matching id), the credential should be ignored and not to be added to the linked list. – When adding from both the input and command files, always check if the credential has all the attributes present and following the order of id, username, score, grade. Invalid credential should be ignored. 6. Requirements Homework is individual. Your homework will be automatically screened for code plagiarism against code from the other students and code from external sources. Code that is copied from another student (for instance, renaming variables, changing for and while loops, changing indentation, etc. will be treated as copy) will be detected and result in ”0” in this homework. The limit is 50% similarity. 7. Turn in your homework Homework 2 needs to be turned in to our Linux server, follow the link here https://rizk.netlify.app/courses/cosc2430/2_resources/ Make sure to create a folder under your root directory, name it “hw2” (case sensitive), copy all your .cpp and .h file to this folder, “ArgumentManager.h” need to be included as well. PS: This document may have typos, if you think something illogical, please email TAs for confirmation.1. Introduction Given a matrix as input, you will need to implement a C++ program to play a mini game and find the smallest sequence that will solve the matrix. This homework will focus on stack and queue implementation. When submit your assignment, please name the folder on the server as “hw3”. 2. Input files – The first line in the input will contain two integer row and col, indicate the size of the given matrix. – The rest of the input will contain the matrix that need to be solved. – Each element will be separated by a space. – There will be no redundant spaces or empty lines. – There will be no empty input. 3. Operations – There are four operation that need to be considered when solving the matrix: o Shift up: shift all the elements in the matrix upward (corresponding to 1) o Shift right: shift all the elements in the matrix to the right (corresponding to 2) o Shift down: shift all the elements in the matrix downward (corresponding to 3) o Shift left: shift all the elements in the matrix to the left (corresponding to 4) – Elements in the matrix will either be ‘O’, ‘X’, or ‘B’. o ‘O’ will represent an open path in the matrix. o ‘X’ will act as a barrier when shifting the matrix. o ‘B’ will represent a bomb that need to be detonate. – In order to solve the matrix, all the bomb (B) in the matrix will need to be detonated. – To detonate a bomb, they need to collide into another bomb by shifting the matrix up, right, down, or left. Which two bomb collided first will be detonated. – The matrix will always have even number of bomb (B). – When two bomb detonated, a barrier (X) will be created at the index of detonation. o Ex: Shift up When shifting up, the bomb (B) marked in red collided and detonated, created two barriers (X). O B O O O O B O O B O O B B B O B X X O O B O O O O O O O O O O – When shifting the matrix, all the barrier (X) will be stationary and will not shift. – A bomb (B) will stop shifting when it meets a barrier (X). o Ex: Shift right 4. Output files – Output the sequence of moves that detonate all the bomb and solve the matrix. – If there are multiple sequence that solve the matrix (ex: 124, 211, 3214), output the smallest one. – If the matrix is already solved without any moves, output “0” for the sequence. 5. Example – Input1: the moves sequence to solve the matrix is 12 (shift up then shift right) Given O O O B O B O O O O O B O O O O O O O B Shift up B B O B B O O O O O O O O O O O O O O O Shift right O O O X X O O O O O O O O O O O O O O O O O O O B O X O B B X O B O O O O O O O O B X O O X X O O O O B – Input2: the moves sequence to solve the matrix is 141 (up, left, up) Given O O O B O X B O O O O X O O O B O X O B O B O O O O O O O B Shift up O B O B X X O O O O B X O O O O B X O O O O O O O O O O O O Shift left X O O O X X O O O O B X O O O B O X O O O O O O O O O O O O Shift up X O O O X X O O O O X X O O O O O X O O O O O O O O O O O O – Input3: the moves sequence to solve the matrix is 1341 (up, down, left, up) Given O O O B O X X O O O X B O O O O O O X O O O O O X O O O B O B O X O B O O X O B O O B O X O O O O O O O X O O O B O B O O O O O B O X O O X B O X O O O O B O O O O O O B O O O X O O X O O B O O O O X Shift up O B O B O X X O O B X O O O O O B O X O X O O O X O O O X O O O X O B O O X O O O O B O X O O B O O O O X O X O O O O O O O O O B O X O O X O O X O O O O O O O O O O O O O O O X O O X O O O O O O O X Shift down O O O O O X X O O O X O O O O O O O X O X O O O X O O O X O O O X O B O O X O O O O B O X O O O O O O O X O X O B O O B O O O O O O X O O X O O X O O O O O O O O B O O O O O O X O O X O B B O O B O X Shift left O O O O O X X O O O X O O O O O O O X O X O O O X O O O X O O O X B O O O X O O B O O O X O O O O O O O X O X X O O O O O O O O O O X O O X O O X O O O O O O O B O O O O O O O X O O X X B O O O O O X Shift up O O O X O X X O O O X O O O O O O O X O X O O O X O O O X O X O X O O O O X O O O O O O X O O O O O O O X O X X O O O O O O O O O O X O O X O O X O O O O O O O O O O O O O O O X O O X X O O O O O O X 6. Requirements Homework is individual. Your homework will be automatically screened for code plagiarism against code from the other students and code from external sources. Code that is copied from another student (for instance, renaming variables, changing for and while loops, changing indentation, etc. will be treated as copy) will be detected and result in ”0” in this homework. The limit is 50% similarity. 7. Turn in your homework Homework 3 needs to be turned in to our Linux server, follow the link here https://rizk.netlify.app/courses/cosc2430/2_resources/ Make sure to create a folder under your root directory, name it “hw3” (case sensitive), copy all your .cpp and .h file to this folder, “ArgumentManager.h” need to be included as well. PS: This document may have typos, if you think something illogical, please email TAs for confirmation.1. Introduction In this homework you will implement a C++ program that can decode messages by taking in commands and organizing them based on their priority. Given a few strings containing random characters and a list of instructions for how to decode the messages. The instructions are out of order and a priority queue must be used to initiate the commands in the proper order. When every command is put into the priority queue in the correct order and each command is performed then the program will decode a message. You will also need to build a binary search tree from the list of messages and traverse them. 2. Input files The input will contain a series of commands, each command will be put into a priority queue. Each command is case sensitive. There are 6 possible commands: ● DECODE: which will be followed by an encoded message inside of brackets ○ Ex: DECODE:[dsacd# dsafdw](2) ○ This will add a string to be decoded to a second queue that contains the messages ● REPLACE: which will contain two characters separated by a comma inside of brackets ○ Ex: REPLACE:[s,e](6) ○ Original string: slsphant ○ new string: elephant ○ This will replace all character ‘s’ to character ‘e’ in the front string of the message queue and then move that message to the end of the message queue ○ Has a priority of 6 ● ADD: which will contain two characters separated by a comma inside of brackets ○ Ex: ADD:[n,a](4) ○ original string: bann ○ New string: banana ○ This will add an ‘a’ after every ‘n’ in the front string of the message queue and then move that message to the end of the message queue ○ And has a priority of 4 ● REMOVE: which will contain a single character inside of brackets ○ Ex: REMOVE:[v](5) ○ Original string: mevssvavge ○ New string: message ○ This will remove every ‘v’ in the front string of the message queue and then move that message to the end of the message queue ○ Has a priority of 5 ● SWAP: which will contain two characters separated by a comma inside of brackets ○ Ex: SWAP:[n,a](8) ○ Original string: bnanan ○ New string: banana ○ This will turn every ‘n’ into an ‘a’ and every ‘a’ into an ‘n’; in the front string of the message queue and then move that message to the end of the message queue ○ Has a priority of 8 ● BST: ○ Ex: BST:(4) ○ This will insert the message at the front of the message queue into the BST, and take it out of the message queue. ○ Left and Right child will be based on the length of the message that is being inserted. Shorter length will go left, longer length will go right. ○ If the message that is being inserted have equal length to one of the nodes in the tree, replace that node’s data with the message that is being inserted. The last line in the input will either be “Preorder”, “Inorder”, or “Postorder” (case sensitive) which indicate the traversal method for BST. In this program there are two queues that must be used: 1. A priority queue that takes in every command sorting them based on priority. If two command share the same priority, then the first one to enqueue goes first. 2. A regular queue that takes in the messages provided by the DECODE command. Every command besides the DECODE command will affect the front of the regular queue filled with messages, modify the string, and then move that string to the back of the queue. So if there are two strings in the normal queue then they will be affected by every other command. If the message queue is empty and you are given any command other than DECODE then nothing should happen. The characters given in the ADD, REPLACE, REMOVE, or SWAP command are case sensitive. 3. Output files Print the BST base on the traversal method given in the last line of the input. Each node will be on its own line. If input is empty, output should be empty. 4. Requirements Homework is individual. Your homework will be automatically screened for code plagiarism against code from the other students and code from external sources. Code that is copied from another student (for instance, renaming variables, changing for and while loops, changing indentation, etc. will be treated as copy) will be detected and result in ”0” in this homework. The limit is 50% similarity. 5. Turn in your homework Homework 4 needs to be turned in to our Linux server, follow the link here https://rizk.netlify.app/courses/cosc2430/2_resources/ Make sure to create a folder under your root directory, name it “hw4” (case sensitive), copy all your .cpp and .h file to this folder, “ArgumentManager.h” need to be included as well. PS: This document may have typos, if you think something illogical, please email TAs for confirmation.1. Introduction You will create a C++ program to implement the B-Tree. The purpose of this homework is to let students be familiar with the B-Tree. 2. Input and Output a. Input file All values that will be added to the tree separated by a space, tab, or new line. Values will be positive. b. Command file Degree of the tree: Degree=value Level to print: Level value c. Output file The output is a single text file. Height of the tree and list of the numbers on the specified levels. If the level is empty, print Empty. d. Examples i. Example 1 input1.txt 55 60 72 command1.txt Degree=3 Level 2 output1.txt Height=2 55 72 ii. Example 2 input2.txt 13 28 1 32 81 17 72 70 77 58 51 24 25 5 55 68 24 28 8 19 15 40 91 17 37 10 20 4 33 21 command2.txt Degree=4 Level 10 Level 9 Level 2 Level 2 Level 1 Level 3 output2.txt Height=3 Empty Empty 5 19 21 33 70 77 5 19 21 33 70 77 13 28 51 1 4 8 10 15 17 20 24 25 32 37 40 55 58 68 72 81 91 iii. Example 3 input3.txt 228 72 177 9 284 1 169 263 237 63 22 148 114 183 98 149 232 100 54 236 command3.txt Degree=4 Level 3 output3.txt Height=3 1 22 54 63 98 100 148 149 169 183 232 236 263 284 3. Requirements Please create the BTree manually. The main C++ problem will become the executable to be tested by the TAs. The result file should be written to another text file (output file), provided with the command line. Homework is individual. Your homework will be automatically screened for code plagiarism against code from the other students and code from external sources. Code that is copied from another student (for instance, renaming variables, changing for and while loops, changing indentation, etc, will be treated as copy) will be detected and result in ”0” in this homework. The limit is 50% similarity. Here are some previous homework which have been found to copy each other (the main function has been deleted). 4. Turn in your homework Homework 5 needs to be turned in to our Linux server, follow the link here https://rizk.netlify.app/courses/cosc2430/2_resources/ Make sure to create a folder under your root directory, name it “hw5” (case sensitive), copy all your .cpp and .h file to this folder, “ArgumentManager.h” need to be included as well. PS: This document may have typos, if you think something illogical, please email TAs for confirmation.
1. Usage of VM To complete the programming assignment in COSC 471 course, students are required to install and use virtual machine (VM). 1.1 Installing virtual machine You can choose any VM you prefer or follow CIS department suggestions. Please search in department website and look for student resources about VMware. If you would like to use Oracle VM VirtualBox, here is some information: • For windows users, you can download VirtualBox here: https://download.virtualbo x.org/virtualbox/6.1.4/VirtualBox-6.1.4- 136177-Win.exe • For Mac OS users, you can download from here: https://download.virtualbo x.org/virtualbox/6.1.4/VirtualBox-6.1.4- 136177-OSX.dmg • For Linux kernel OS users, please check the link below and find the corresponding downloads for your OS: https://www.virtualbox.org/wiki/Linux_Downloads After downloading, please install it as directed. 1.2 Download virtual OS HD After VM software is ready, please download a virtual Ubuntu. You should be able to find Ubuntu on CIS department resources for students. We need version at least Ubuntu 18.04.0 and 64 bit is preferred. It is suggested you set the VM’s memory to be more than 2GB. 1.3 Install Guest Additions After getting into the Ubuntu system, click “Devices” and then click “install Guest Additions” You can also refer to link below for more details: https://docs.oracle.com/cd/E36500_01/E36502/html/qs-guest-additions.html If the installing above is not successful, please open terminal using ctrl+alt+t, and then install using the following commands: sudo mkdir –p /media/cdrom sudo mount -t auto /dev/cdrom /media/cdrom/ cd /media/cdrom/ sudo sh VBoxLinuxAdditions.run After installing is completed, please restart the virtual machine. 1.4 Assignment editing and importing/exporting Assignment 1 skeleton is named as pa1, a compressed file. Download your assignment skeleton through Blackboard to your hosting machine. Then drag it to your virtual machine. Here, you may need to set the “drag and drop” to be “bidirectional”. You can also refer to the following link for more details: https://docs.oracle.com/en/virtualization/virtualbox/6.1/user/guestadd-dnd.html After you import the assignment to virtual machine, you can use Visual Studio Code to view and edit the assignment. Right click the assignment folder and then “open with other Application”. Then choose “Visual Studio Code”. If you don’t have VSC installed, please download and install it. You may need to check CIS department resource for students. 2. Assignment skeleton and programming environment 2.1 Vcpkg and Eigen3 You may need to download and install Vcpkg to help you manage C and C++ library on VSC. Please refer to the links below: https://github.com/microsoft/vcpkg https://docs.microsoft.com/en-us/cpp/build/vcpkg?view=vs-2019 Eigen is a library which help you manage Linear Algebra related works. You can find Eigen library information here: https://eigen.tuxfamily.org/index.php?title=Main_Page Specifically, you can find Vector and Matrix related topics here: https://eigen.tuxfamily.org/dox/groupTutorialMatrixArithmetic.html // Example of vector std::cout
Overview Building upon the library book management system from P1, you will now enhance its security. This assignment focuses on implementing security mechanisms to protect the system from unauthorized access and ensure data confidentiality and integrity. You will implement Transport Layer Security (TLS) for secure communication, a secure login system, an authentication protocol, a secure password generator, and learn how to protect sensitive data at rest. Note: This final assignment has a hard deadline and does not include the typical 48-hour late penalty period. Your learning objectives are: a. Gain practical experience with OpenSSL for TLS implementation, secure password hashing, and data encryption. b. Understand the importance of secure password management and implement techniques for generating, storing, and transmitting passwords securely. c. Develop skills in securing network applications and protecting sensitive data in transit and at rest. The nature of this last assignment will force you to do significant amount of unsupervised learning – online research, forum scans, trial-and-error, and troubleshooting. Most likely, you will also discover (on your own) that there are more than one library package implementation of openssl standard, especially for C/C++, which might further complicate your task. So, don’t get frustrated but instead use this as a valuable learning opportunity. Back Story Avast, ye mateys! The high seas be a treacherous place, not just for ships but for the digital kind too. Word’s reached the ears of Captain Haddock that scurvy pirates be lurking in the digital ether, lookin’ to plunder precious knowledge and disrupt the crew’s peaceful book-borrowin’ ways. Professor Calculus, ever the vigilant guardian of the ship’s library, has hoisted the cybersecurity sails. He’s charted a course to reinforce the online book management system, makin’ it as sturdy as a kraken’s shell. But he needs a crew of savvy cybersecurity buccaneers to help him batten down the hatches. That’s where you fine folks come in. So swab the decks, hoist the colors, and prepare to defend the ship’s library against the digital pirates!Technical Requirements ALL P1 technical requirements fully apply to the P3. Additionally, following new requirements should be met. 1. Secure Communication • Establish TLS 1.3 connections between the clients and the server for all communication using OpenSSL 3.2.2+ (default on zone instances). This ensures confidentiality and integrity. • Use OpenSSL’s SSL_CTX functions to configure the TLS context: – SSL_CTX_set_min_proto_version() and SSL_CTX_set_max_proto_version() to set the protocol version to TLS 1.3. – SSL_CTX_set_ciphersuites() to select strong cipher suites. • Generate self-signed certificates for testing using OpenSSL’s command-line tools. Ensure your generated files are named p3server.key and p3server.crt 2. Implement a Secure Login System • Replace HELO command with USER → PASS command sequence. • USER : Used to send the username to the server. The server checks if the received username is a known value. If YES, await for the password. Otherwise follow the New User Registration Protocol (see below). • PASS : Used to send user’s password to the server. The server follows the Authentication Protocol (see below) upon receiving a password. 3. Password & Salt Generation • Generate a 5-character† random password and a 6-character random salt for each user. The password should include at least one uppercase letter, one number, and one symbol (from the set !@#$%&*). Passwords may begin with an alphanumeric character but not with special symbols. Salts should consist of printable characters excluding whitespace. – Thought not strictly necessary, consider employing OpenSSL’s RAND_bytes() to generate passwords and salts as it’s readily available. • Ensure the generated passwords are strong and random. Implement a password strength checker and regenerate passwords if they do not meet the complexity criteria 4. Salting: Use the interleaving method to salt the password, i.e, alternate salt characters and password characters staring with the first salt character. (e.g., if the salt is ’S1a2tX’ and the password is ’P4s5w’, the salted password would be ’SP14as25twX’). 5. Pre-shared key: A secret symmetric-key shared between the clients and server. This key is used to encrypt plaintext passwords any time they need to be exchanged between clients and the server. This will prevent sending plaintext passwords over-the-wire. The pre-shared key for this assignment is F24447TG 6. New User Registration Protocol: Generate a secure random password → store it securely with the username (see below) → encrypt the password using a pre-shared key → transmit the encrypted password to the client → close the connection. 7. Authentication Protocol: Decrypt the received string using the pre-shared key → salt it → generate a hash → compare the generated hash against the stored hash for the user. 8. Your client code should decrypt the received server-generated password and print it to standard output before closing the connection. 9. Storing Passwords and Salts • Salt passwords using a unique salt for each user and hash salted passwords using SHA-512 to protect against rainbow table attacks • As a homage to how Linux store passwords (in /etc/shadow), store the username, salt, and the salted password hash in a hidden file called .book_shadow. The format of this file should mimic the following: username:salt:salted_password_hash †NOTE: Typical passwords should be longer than 5-characters to avoid possible brute force attacks. We are using a shorter one simply for assignment purposes. It’s definitely not a recommendationFunctional Requirements ALL P1 functional requirements fully apply to the P3. Additionally, following new requirements should be met. 1. Fix any lingering issues in P1 before starting on P3 tasks. 2. Multiple concurrent client functionality will be fully tested in P3. Thus, consider moving away from shared memory-based solutions (if you used one in P1) to a file-based solution. 3. It’s not realistic to assume that your users know numerical book_ids. Thus, modify following P1 command syntax to avoid implementation confusions. You should, however, consider using an id value (or a hash table based approach) for efficient indexing purposes. • DETAILS • CHECKOUT • RETURN • RATE 4. The user enters the password (for the PASS command) in plaintext. Your client should encrypt it before sending to the server. 5. You must provide proof of secure communication. To do this, run Wireshark with and without TLS separately, and provide appropriately annotated screenshots in your report. Failure to provide sufficient proof of secure communication will be considered as an indication of not meeting project requirements. • Two terminal equivalents for wireshark are tcpdump and tshark. You can save your capturing session as a .pcap file, which can be later opened in wireshark for easier analysis. The wireshark manual explains how to use both. See here https://www.wireshark.org/docs/wsug_html_chunked/AppToolstcpdump. html and here https://www.wireshark.org/docs/man-pages/tshark.html Extra Credit • For an additional level of obscurity, encode passwords in base64 before encrypting them for transmission over-the-wire. Correspondingly, decode strings at the receiving end before other performing any other actions on the received data. You may also consider encoding anything else that you deem “sensitive” but make sure to provide an explanation as to why with appropriate proof of work (in screenshot form) in your report [10 points]. • Only take this next extra credit option if you have ample time, your core implementation is complete, and (to a lesser extent) you have some prior experience programming ncurses. Submissions that meet (or exceed) at least 80% of project objectives are eligible for up to 15% extra credit by integrating a ncurses based text-based user interface (TUI) https://www.gnu.org/software/ncurses/. Consider incorporating features like a login screen, menu-driven navigation for browsing and searching books, and interactive forms for user input. Instructions • Start early & backup often: This assignment requires careful planning and implementation and remember to save your progress frequently. • Don’t procrastinate!! As mentioned earlier, this assignment involves a significant amount of self learning secure network programming and cybersecurity concepts. Allow yourself plenty of time to absorb new knowledge. • Maintain clean, readable code. Adhere to Google’s C++ Style Guide or another established standard. Use one of Google’s coding standard found here https://google.github.io/styleguide/, if you don’t already follow one. • Your code must compile and run flawlessly on a standard Linux environment. Test it thoroughly using command-line tools.• Implement your solution in C++. Submit a .tgz file containing only your source code, a README with compilation instructions, and your report. • Handling parallelism is not trivial. Start with a single-client version, then gradually scale up. • Focus on core C++ socket and I/O functionalities. Avoid external libraries unless explicitly permitted. • DEADLINE: Thursday, November 21, 2024 @ 01:59:59 p.m. (hard deadline) through Moodle. Email submissions are not honored. Deliverables A complete solution comprises of: 1. Report (pdf): • Introduction: Describe your learning objectives from a cybersecurity and secure network programming perspective. Explain what you knew about secure programming techniques before starting P3 and what you hope to learn by completing P3. • Design: Explain your overall system design, key choices you made, and specific challenges you faced. • Sample Run: Include screenshots showcasing a typical interaction with your system. These can help illustrate functionality and potentially earn partial credit if certain features aren’t fully implemented. • Proof of secure communication, password specification conformity, base64 encoding (if applicable, etc). • Summary and Issues: Summarize your achievements and what you learned from a cybersecurity perspective. Explicitly list any unimplemented or buggy functionality. 2. Compressed Tarball (siue-id-p3.tgz): • Source Code Directory: Include all your C++ source code. No need to include any *.config files. Also, no need to send your self-signed certificates either (as long as they following the naming standard specified earlier). • README: Provide clear instructions on how to compile and run your code. • Makefile: A Makefile is required, especially if your project involves multiple executables or compilation flags. • Your .pcap file as proof of secure communication. Use the following command to create the compressed tarball: tar -zcvf siue-id-p3.tgz p3/. (Replace siue-id with your real siue email id and p3/ with the name of your source code directory) Your code should be a testament to your abilities, not a copy of someone else’s work. Collaborate, don’t copy! Learning from peers is great, but copying code (from classmates or online) is strictly prohibited. Cite any external resources you use for ideas, and then implement those ideas in your own way. This assignment is a challenge designed to push your boundaries and foster growth. Embrace the learning process and don’t hesitate to seek help when needed. Remember, the goal is to master these concepts, not just complete the assignment. Plagiarism, whether from classmates, online sources, or AI tools, stifles learning and compromises academic integrity. The instructor actively uses MOSS http://theory.stanford.edu/~aiken/moss/ to check for software similarity. Plagiarism has severe consequences including and will result in a failing grade. No exceptions. Some Useful Resources • Linux Man pages – found in all Linux distributions • Beej’s Guide to Network Programming – A pretty thorough free online tutorial on basic network programming for C/C++ https://beej.us/guide/bgnet/. • Linux Socket Programming In C++ – https://tldp.org/LDP/LG/issue74/tougher.html • The Linux HOWTO Page on Socket Programming – https://www.linuxhowtos.org/C_C++/socket.htm• Learn Makefiles With the tastiest examples – https://makefiletutorial.com/ • Fedora Security Team – Defensive Coding https://docs.fedoraproject.org/en-US/Fedora_Security_Team/1/html/Defensive_Coding/index.html • OpenSSL Wiki – Simple TLS Server https://wiki.openssl.org/index.php/Simple_TLS_Server • The Illustrated TLS 1.3 Connection – https://tls13.xargs.org/ • A Readable Specification of TLS 1.3 – https://www.davidwong.fr/tls13/ • Creating a Self-Signed SSL Certificate – https://linuxize.com/post/creating-a-self-signed-ssl-certificate/ • Ncurses Programming Guide – http://jbwyatt.com/ncurses.html
Your second programming assignment is to implement an Internet Relay Chat (IRC) application using the socket interface. Ever used Discord or Slack? At its core, such apps share fundamental similarities with IRC, a classic real-time communication protocol that powers many chat platforms. This assignment gives you the chance to peek under the hood and build your own simplified version of a system like Discord, exploring key networking concepts like client-server architecture, text-based communication, and handling multiple concurrent connections. While the full IRC protocol description is quite extensive (and has evolved over several RFCs), this assignment focuses on building a simplified IRC server that supports some of the most essential commands. Given our 2-week window, it’s not even realistic to implement a fully-fledged IRC client. Instead, you will primarily focus on building a robust and efficient IRC-based chat solution that can handle a bustling crowd of users, all while gracefully managing the flow of messages and ensuring everyone stays connected. In doing so, you will gain valuable experience in: a. Able to Proficiently read and interpret RFC specifications, using RFC 2812 (Internet Relay Chat Protocol) as a guide/case study. b. Implement an application using both TCP and UDP, developing a nuanced understanding of their strengths, weaknesses, and appropriate use cases. c. Master techniques for handling multiple clients concurrently d. Design and build a complete client-server system, solidifying your understanding of network communication principles. Back Story “Thundering typhoons!” roared Captain Haddock, sending a stack of shipping manifests flying. “This blasted carrier pigeon arrived three weeks late! The Unicorn nearly collided with a tanker in the fog because of this delay!” He paced the deck of his flagship, the Sirius, fuming over yet another communication mishap plaguing his burgeoning shipping empire. Lost shipments, missed client meetings, and now a near disaster – all thanks to the unreliable pigeon post. Professor Calculus, ever attentive to his friend’s woes, emerged from his cabin with a twinkle in his eye. “Haddock, my dear friend,” he announced, “I believe I have the perfect solution to your communication conundrum! I’ve been studying this fascinating new technology called IRC, Internet Relay Chat! Imagine, a network where your captains can instantly send messages to each other, join specific channels for different topics like ’Atlantic Crossings’ or ’Caribbean Trade Winds’ and even have private conversations!” Haddock, initially skeptical, perked up at the prospect of ditching the troublesome pigeons. “Blistering barnacles, Calculus! If this IRC contraption can prevent another near-collision, I’m all for it! But it better be more secure than thosegossiping seagulls! I don’t want our rivals intercepting our shipping routes!” With a mischievous grin, Calculus beckoned Haddock towards his cabin. “Come, my friend,” he said, “Let me show you the wonders of Internet Relay Chat!” Technical Requirements 1. A Tale of Two Protocols: Your IRC application will utilize both TCP and UDP for communication. • TCP: Employ TCP for the core IRC functionality, ensuring reliable delivery of messages and commands between clients and the server. • UDP: Utilize UDP for “out-of-band” communication, such as: – Heartbeat Signals: Implement a heartbeat mechanism where the server periodically sends UDP packets to clients to check if they are still active. Clients should respond with a corresponding UDP packet to confirm their presence. This helps the server maintain an accurate list of active users and efficiently manage resources. – Server Statistics: The server should periodically broadcast server statistics using UDP. These statistics could include the number of connected users, the number of active channels, CPU usage, or any other relevant performance metrics. Clients can utilize this information to monitor the server’s health and performance. – Real-time Notifications: Implement a system for delivering real-time notifications to clients using UDP. These notifications could include alerts about new users joining a channel, urgent messages, or server-wide announcements. This adds a layer of immediacy and responsiveness to your chat application. 2. Server-Side Focus: Develop a robust single server IRC application capable of handling multiple clients concurrently. Server-to-server communication is outside the scope of this assignment. 3. Protocol Conformance: Adhere to the protocol grammar specified in RFC 2812, Internet Relay Chat: Client Protocol (https://tools.ietf.org/html/rfc2812), Section 2.3.1. Utilize regular expressions (regex) for efficient message parsing. 4. Command Support: Implement the following core IRC commands: • Connection Registration (Section 3.1): – NICK: Allows a user to change their nickname. – USER: Registers a user with the server. – MODE: View or change user or channel modes. – QUIT: Disconnects a user from the server. • Channel Operations (Section 3.2): – JOIN: Allows a user to join a channel. – PART: Allows a user to leave a channel. – MODE: View or change channel modes. – TOPIC: View or change the topic of a channel. – LIST: List all channels or channels matching a given mask. – NAMES: List all visible users on a channel. • Messaging (Section 3.3): – PRIVMSG: Send a private message to a user or channel. 5. Response Codes: Implement the following numeric reply codes as defined in Section 5 of RFC 2812: • 001 (RPL_WELCOME): Welcome message upon successful connection. • 002 (RPL_YOURHOST): Server host and version information. • 004 (RPL_MYINFO): Server information. • 301 (RPL_AWAY): User is marked as away. • 322 (RPL_LIST): Channel information (from LIST command). • 323 (RPL_LISTEND): End of channel list (from LIST command).• 401 (ERR_NOSUCHNICK): No such nickname exists. • 403 (ERR_NOSUCHCHANNEL): No such channel exists. • 404 (ERR_CANNOTSENDTOCHAN): Cannot send message to channel. • 431 (ERR_NONICKNAMEGIVEN): No nickname given. • 432 (ERR_ERRONEUSNICKNAME): Erroneous nickname. • 433 (ERR_NICKNAMEINUSE): Nickname is already in use. • 461 (ERR_NEEDMOREPARAMS): Not enough parameters provided for command. • 501 (ERR_UMODEUNKNOWNFLAG): Unknown user mode flag. • 502 (ERR_USERSDONTMATCH): Cannot change mode for other users. You may implement additional reply codes to enhance your server’s functionality, but provide justification for their inclusion in your report. 6. Client Implementation: Develop a simple text-based client to interact with your server. The client should be able to connect to the server, send commands, and display received messages. Functional Requirements 1. Configuration Files: Similar to the first assignment, your server and client will utilize configuration files (server.conf and client.conf) to specify runtime arguments. Here’s the expected structure: server.conf TCP_PORT= HEARTBEAT_INTERVAL= STATS_INTERVAL= client.conf SERVER_IP= SERVER_PORT= 2. Graceful Exit: Implement graceful exit mechanisms for clients. Server is allowed to force stop. 3. chi IRC: To gain a better understanding of IRC interactions and visualize how your application should behave, explore the chi IRC project at http://chi.cs.uchicago.edu/chirc/irc_examples.html. This resource provides nicely illustrated examples of IRC commands and responses. However, absolutely no code from this or any other online source is to be used in your implementation. 4. Data Management: For managing server-side data such as user information, channels, and topics, consider using a file-based approach. This strategy offers a balance of simplicity and efficiency for this assignment. 5. UDP Port Allocation: • Client: Each client must dynamically allocate a UDP (listening) port during startup using a fixed offset (e.g., adding 1000 to its assigned TCP port). For example, if the client’s assigned TCP port is 50000, its UDP port would be 51000. • Server: The server does not need to explicitly define a UDP port because it doesn’t need to listen for incoming UDP connections. It will calculate each client’s UDP port by adding the same fixed offset to the port number reported by the client’s TCP connection. The server should maintain a mapping of nicknames/clients and their udp port numbers for out-of-band communication. 6. Case-Insensitive Commands: The server should be case-insensitive when processing commands. For example, /join, /JOIN, and /JoIn should all be treated as the same command. Logistics 1. Starter Code: Feel free to leverage the starter code from the first assignment as a foundation for this project. However, you’ll need to adapt it to handle both TCP and UDP connections as described in the Technical Requirements section. 2. Testing Environment: Leverage the zone server during testing to mimic real-world IRC behavior using it’s interconnected container network topology.3. Testing and Documentation: • Thoroughly test your application with various scenarios, documenting your process and results with screenshots. • Ensure your code compiles and runs on a Linux machine. Use Makefiles. Provide a README with clear compilation instructions in case make fails. 4. At the end of your implementation, you should be able to: • Configure the server.conf and client.conf files with the appropriate parameters. • Compile your code using the Makefile and create server and client executables. • Run your IRC server program first. • Run one or more IRC clients to connect to the server. • Perform various IRC chat functions, such as joining channels, sending private messages, and changing nicknames. • Simulate a client disconnecting abruptly and observe the server’s response to the lack of heartbeat replies. • Verify that clients receive and display the server statistics correctly. Use the /quit command in the client to initiate a graceful exit and observe the server’s response. Instructions • Start early!! This assignment is a multi-faceted adventure involving substantial RFC reading and intricate implementation. Starting early is crucial to avoid a last-minute scramble. • Begin with a minimum viable solution, gradually adding complexity and features. Maintain good version control habits throughout the development process. Start simple, finish BIG!. • Adhere to a consistent coding standard. If you don’t have a preferred one, the Google C++ coding standard https://google.github.io/styleguide/ is recommended. • Begin by reading RFC 2810, Internet Relay Chat: Architecture (https://tools.ietf.org/html/rfc2810) to gain a foundational understanding of IRC concepts and terminology. • Then, thoroughly read and understand all relevant sections of RFC #2812 Internet Relay Chat: Client Protocol https://tools.ietf.org/html/rfc2812 • Plan and design your server’s architecture and data management strategy carefully. Document any design decisions you make, especially those based on your interpretation of the RFCs, with clear explanations and citations. • Make design decisions within the boundaries of the RFC specifications. If unsure, consult the instructor for clarification. • DEADLINE: Thursday, October 31, 2024 @ 01:59:59 p.m. through Moodle. Email submissions are not honored. Deliverables A complete solution comprises of: 1. Report (pdf): • Introduction: Your objectives for the assignment and what you hope to learn. • Design: Explain your overall system design, key choices you made, and the protocol’s reply codes. • Sample Run: Include screenshots showcasing a typical interaction with your system. These can help illustrate functionality and potentially earn partial credit if certain features aren’t fully implemented. • Summary and Issues: Summarize your achievements and explicitly list any unimplemented or buggy functionality. 2. Compressed Tarball (siue-id-p2.tgz):• Source Code Directory: Include all your C++ source code. config files are not required. • Makefile: A Makefile is required, especially if your project involves multiple executables or compilation flags. • README: Provide clear instructions on how to compile and run your code, in case make fails. Use the following command to create the compressed tarball: tar -zcvf siue-id-p2.tgz source/. (Replace siue-id with your actual SIUE email login (e.g. tgamage) and source/ with the name of your source code directory (e.g. p2)) Your code should be a testament to your abilities, not a copy of someone else’s work. Collaborate, don’t copy! Learning from peers is great, but copying code (from classmates or online) is strictly prohibited. Cite any external resources you use for ideas, and then implement those ideas in your own way. This assignment is a challenge designed to push your boundaries and foster growth. Embrace the learning process and don’t hesitate to seek help when needed. Remember, the goal is to master these concepts, not just complete the assignment. Plagiarism, whether from classmates, online sources, or AI tools, stifles learning and compromises academic integrity. The instructor actively uses MOSS http://theory.stanford.edu/~aiken/moss/ to check for software similarity. Plagiarism has severe consequences including and will result in a failing grade. No exceptions. Useful Resources • Linux Man pages – found in all linux distributions • Beej’s Guide to Network Programming – A pretty thorough free online tutorial on basic network programming http://beej.us/guide/bgnet/output/print/bgnet_USLetter.pdf • Internet Relay Chat: Client Protocol RFC #2812 https://tools.ietf.org/html/rfc2812 • Internet Relay Chat: Architecture RFC #2810 https://tools.ietf.org/html/rfc2810 • Internet Relay Chat: Channel Management RFC #2811 https://tools.ietf.org/html/rfc2811 • Internet Relay Chat: Server Protocol RFC #2813 https://tools.ietf.org/html/rfc2813 • The University of Chicago χ-Project http://chi.cs.uchicago.edu/chirc/irc.html
Your first programming assignment is to implement a basic client/server application using the socket interface. The learning objectives are as follows: a. to get your feet wet on socket programming basics; b. to understand the ordering of the socket interface primitives; c. to get you exposed to Linux system calls (if you haven’t already); d. to gain a basic understanding of network protocols; and e. to set yourself up for the rest of the course. Back Story Captain Haddock, ever the avid reader, often finds himself misplacing books amidst the chaos of his sea voyages. The ship’s library, though modest, is a treasure trove of knowledge and escape for the crew, but tracking borrowed volumes has become a headache. Professor Calculus, ever the ingenious inventor, has stepped up to the challenge. Leveraging his newfound expertise from CS447 at SIUE, Calculus proposes a solution: an online library book management system accessible to the entire crew. Not only will this system keep meticulous records, but it will also allow multiple users to search, check out, and return books simultaneously, even amidst the unpredictable swells of the high seas. In this first iteration, Calculus envisions focusing on essential features like searching, checking availability, and managing borrowed books, etc, categorized into 3 modes as follows: 1. SEARCH • Given search term (title or author), return list of matching books • Given book title, return detailed information (author, availability) 2. BOOK MANAGEMENT • Given book title, check out the book (if available) • Given book title, return the book (if checked out) • List all books currently checked out 3. RECOMMENDATIONS • Given genre, provide book recommendations • Given book title and rating, record the ratingTechnical Requirements • server should be capable of accepting requests from TCP clients. • server should support concurrency (more than one client should be capable of using the library book manager at the same time). • Your protocol interaction should adhere to the following specifications. • Client Commands: 1. HELO – This is the first command issued by the client to the server. It initiates the connection and identifies the client. The correct reply code is 200. 2. HELP – This command can be issued anytime after the HELO command. It requests a list of available commands supported by the server. If this command is issued inside a mode, then the mode specific list of available commands will be listed. The correct server reply code is 200. 3. SEARCH – This command puts the client in search mode, allowing them to search for books. The correct server reply code is 210. (a) FIND – The FIND command searches for books matching the given term. The correct server reply code is 250 with a list of matching books or 304 if no books are found. (b) DETAILS – The DETAILS command requests detailed information about a specific book. The correct server reply code is 250 with the book details or 404 if the book is not found. 4. MANAGE – This command puts the client in book management mode, allowing them to check out and return books. The correct server reply code is 220. (a) CHECKOUT – The CHECKOUT command attempts to check out a book. The correct server reply code is 250 if successful, 403 if the book is unavailable, or 404 if the book is not found. (b) RETURN – The RETURN command returns a checked-out book. The correct server reply code is 250 if successful or 404 if the book was not checked out by the user. (c) LIST – The LIST command lists all books currently available for check out by the user. The correct server reply code is 250 with the list of books or 304 if no books are available. 5. RECOMMEND – This command puts the client in recommendation mode, allowing them to get book suggestions and rate books they’ve read. The correct server reply code is 230. (a) GET – The GET command requests book recommendations for a specific genre. The correct server reply code is 250 with a list of recommendations or 304 if no recommendations are found. (b) RATE – The RATE command rates a book on a scale of 1 to 5. The correct server reply code is 250 if successful or 400 if the rating is invalid. 6. BYE – This command closes the connection and requests a graceful exit. This command can be issued anytime during the interaction. The correct server reply code is 200. • Server Reply Codes: 1. 200/210/220/230 Command Success. The command success reply code is issued only when the interaction happens according to the correct specification. Examples: – 200 – The correct response code for HELO and HELP commands. – 210 Switched to Search Mode – If the SEARCH command is issued at the correct point of interaction. – 220 Switched to Manage Mode – If the MANAGE command is issued at the correct point of interaction. – 230 Switched to Recommend Mode – If the RECOMMEND command is issued at the correct point of interaction. 2. 304 NO CONTENT – This reply code indicates that the server successfully processed the request, but there is no content to send back (e.g., no search results or no checked-out books). 3. 250 – This reply code is issued in response to a correct command syntax received in the previous message from the client. data represents the requested information, such as search results, book details, or a success message. 4. 400 BAD REQUEST – This reply code indicates that the server could not understand the request due to invalid syntax or missing parameters. 5. 403 FORBIDDEN – This reply code indicates that the server understood the request, but refuses to fulfill it (e.g., trying to check out an unavailable book).NOT FOUND – This reply code indicates that the server did not find the requested resource (e.g., a book with a specific ID). 7. 500 INTERNAL SERVER ERROR – This reply code indicates that the server encountered an unexpected condition that prevented it from fulfilling the request. Functional Requirements 1. Starter Code: • Utilize the provided starter code from Moodle. Using any other base code will result in an invalid submission. • IP addresses and port numbers should be configured via server.conf and client.conf files, not hardcoded. • Run the server with ./server server.conf and clients with ./client client.conf. 2. Helper Code: • An additional helper function (p1_helper.cpp) along with a book database (books.db) is also provided to you through moodle. The helper function is intended to be used to maintain an in-memory database of books at the server side. • The Book database (books.db) is a text file that you can expand with more entries to enhance your testing. Feel free to add more books, explore different genres, or even include books that are already checked out to test various scenarios. Just remember to maintain the same format! 3. Network Setup: • The client-server connection must be TCP-based. • The server should be capable of handling multiple simultaneous client connections (hence concurrency). You have the flexibility to achieve this using either multi-threading techniques or the fork() system call. 4. Client-Server Interaction: • Clients must exit gracefully using the BYE command. The server can be terminated forcefully. • The protocol interaction should adhere to the specifications detailed in the previous section (client commands, server reply codes, etc.). • Here’s a sample (non-comprehensive) interaction. Assume the client’s IP address is 192.168.0.11 and running TCP and the server’s running on the tgamage-0 zone-server instance. Note: The server must acknowledge client IP and connection type. Client Server HELO tgamage-0 → ← 200 HELO 192.168.0.11 (TCP) CHECKOUT Dune → ← 503 Bad sequence of commands. Must enter a mode first. HELP → ← 200 Available commands: HELO, SEARCH, MANAGE, RECOMMEND, BYE SEARCH → ← 210 Ready for search! FIND Dune → ← 250 Dune MANAGE → ← 220 Ready for book management! CHECKOUT Dune → ← 250 Book checked out successfully BYE →5. Testing & Deployment: • Test your implementation with at least 2 simultaneous client connections, preferably on separate zone-server containers. • Ensure your code compiles and runs on a Linux machine. Provide a README with clear compilation instructions and any additional software dependencies. 6. At the end of your implementation, you should be able to: • Compile and run your code in a Linux machine. • Run your server program first. • Run one or more clients to connect to the server. • Perform library book manager functionality while meeting the technical requirements mentioned above. • Exit the client(s) gracefully. Instructions • Start early & backup often: This assignment requires careful planning and implementation. Don’t procrastinate, and remember to save your progress frequently. • Maintain clean, readable code. Adhere to Google’s C++ Style Guide or another established standard. Use one of Google’s coding standard found here https://google.github.io/styleguide/, if you don’t already follow one. • Your code must compile and run flawlessly on a standard Linux environment. Test it thoroughly using command-line tools. • Implement your solution in C++. Submit a .tgz file containing only your source code, a README with compilation instructions, and your report. • Handling parallelism is not trivial. Start with a single-client version, then gradually scale up. • Focus on core C++ socket and I/O functionalities. Avoid external libraries unless explicitly permitted. • DEADLINE: Thursday, September 26, 2024 @ 01:59:59 p.m. through Moodle. Email submissions are not honored. Deliverables A complete solution comprises of: 1. Report (pdf): • Introduction: Your objectives for the assignment and what you hope to learn. • Design: Explain your overall system design, key choices you made, and the protocol’s reply codes. • Sample Run: Include screenshots showcasing a typical interaction with your system. These can help illustrate functionality and potentially earn partial credit if certain features aren’t fully implemented. • Summary and Issues: Summarize your achievements and explicitly list any unimplemented or buggy functionality. 2. Compressed Tarball (siue-id-p1.tgz): • Source Code Directory: Include all your C++ source code and configuration files (server.conf, client.conf). • README: Provide clear instructions on how to compile and run your code. • Makefile: A Makefile is required, especially if your project involves multiple executables or compilation flags. Use the following command to create the compressed tarball: tar -zcvf siue-id-p1.tgz source/. (Replace siue-id with your actual SIUE ID and source/ with the name of your source code directory)Your code should be a testament to your abilities, not a copy of someone else’s work. Collaborate, don’t copy! Learning from peers is great, but copying code (from classmates or online) is strictly prohibited. Cite any external resources you use for ideas, and then implement those ideas in your own way. This assignment is a challenge designed to push your boundaries and foster growth. Embrace the learning process and don’t hesitate to seek help when needed. Remember, the goal is to master these concepts, not just complete the assignment. Plagiarism, whether from classmates, online sources, or AI tools, stifles learning and compromises academic integrity. The instructor actively uses MOSS http://theory.stanford.edu/~aiken/moss/ to check for software similarity. Plagiarism has severe consequences including and will result in a failing grade. No exceptions. Some Useful Resources • Linux Man pages – found in all Linux distributions • Beej’s Guide to Network Programming – A pretty thorough free online tutorial on basic network programming for C/C++ https://beej.us/guide/bgnet/. • Linux Socket Programming In C++ – https://tldp.org/LDP/LG/issue74/tougher.html • The Linux HOWTO Page on Socket Programming – https://www.linuxhowtos.org/C_C++/socket.htm • Learn Makefiles With the tastiest examples – https://makefiletutorial.com/
Overview: Write a multithreaded C++ program using open MP threads. I will provide a text file containing numbers that must be read into a two dimensional array. The first line of the file will have 2 integers, the number of rows in the array followed by the by the number of columns in the array. The rest of the file will contain integers that the array must be initialized to. Your program must also utilize a random number generator. I will provide source code. Notes on Compiling: This program uses the C++ high resolution timer. It was introduced in the C++ 11 standard, so you may need to explicitly tell the compiler to use the C++ 11 standard. I have included the appropriate option in the example runs below. If you do not wish to compete in the fast time competition, you do not need to include the time information in your output. Description: Your program will indicate the cell address (the row and column) of the cell with the highest neighborhood average. If there is a tie, your program must report only a single cell that ties the maximum value. I will post a solution consisting of all cells that tie the maximum value so you can be sure your solution is correct. The neighborhood of a cell is all cells that immediately border the cell, including the cell itself. For each cell, you must compute the average of numbers in the neighborhood. For example, in the following array: unsigned int M[10000][10000]; the neighborhood of cell M[2][8] consists of the following cells: M[1][7] M[1][8] M[1][9] M[2][7] M[2][8] M[2][9] M[3][7] M[3][8] M[3][9] Because the array will be large, you will need to use dynamic memory allocation (keyword new) on the heap. 1 Be careful not to go out of bounds on the array when computing neighborhoods Your program should take a command line argument indicating the number of threads that will be used. The group that has the fastest program when run with the number of threads equal to the number of available cores on a chosen computer will win a prize (of non-monetary value)! So don’t give away your speedy secrets. The openMP wiki has a nice intro to using openMP. http://en.wikipedia. org/wiki/OpenMP Note that you must have a GCC compiler version 4.3 or later to use openMP. The departrment’s home.cs.siue.edu server has a sufficient GCC version. You can download the newest version of GCC for mac and linux. You may have to install cygwin to do this with windows. Microsoft’s compiler has it too. Sample input files are attached Your program will be graded on home.cs.siue.edu, so make sure it compiles and runs correctly there. Your group must make exactly 1 submission, and your group member names should be in a comment in the first line of your file. Also, you MUST submit a MAKEFILE. A sample makefile is provided, you can use this one, or edit it for your needs. Your submission should be zipped and submitted as single file. What to Turn In: You must turn in your source code, a Makefile that will compile your source code on home.cs.siue.edu, and a README file that contains the names of your group members, and any additional information about your implementation that you think I may need to consider while grading. Turn in a single zip or tar.gz file. The README file should be a PLAIN TEXT FILE! The README must contain the group member names. If you do not wish to try for the fastest time, then you do not need to include time information in your output. Do not include any other information in your output other than what is shown in the example runs! For example, if you print out the entire array in your submission, you will receive a grade of 0 becuase we do not want to spend time parsing through a ton of unneccessary output. Example Input and Expected Output: Here are some sample runs of the program so you can see what the output looks like. Your output should look EXACTLY like mine, except that you will only show a single cell address with the largest average. The input file small3.txt contains two cells tying for the largest average The following shows the expected output with the timing output. You output should match these. These runs were made on an previous instance of the home server, the new home server is substantially faster, so you should be able to beat them. Output that does match the format shown below will recieve a grade of 0. 2 vm-02$ cat Makefile all: g++ -fopenmp -ggdb -std=c++11 matAverager.cpp -o matavg vm-02$ make g++ -fopenmp -ggdb -std=c++11 matAverager.cpp -o matavg vm-02$ ./matavg usage: exe [input data file] [num of threads to use] or usage: exe rand [num of threads to use] [num rows] [num cols] [seed value] vm-02$ ./matavg small3.txt 10 largest average: 7.66667 found at cells: (0,1) (0,2) elapsed time: 0.033653 vm-02$ ./matavg rand 10 5 5 0 largest average: 6780.75 found at cells: (4,4) elapsed time: 0.0271368 vm-02$ ./matavg rand 10 100 100 0 largest average: 8296.33 found at cells: (99,2) elapsed time: 0.0396051 vm-02$ ./matavg rand 10 1000 1000 0 largest average: 9042.44 found at cells: (966,225) elapsed time: 0.08917 vm-02$ ./matavg rand 10 1000 2000 0 largest average: 9339.83 found at cells: (999,1504) elapsed time: 0.080462 vm-02$ ./matavg rand 1 1000 2000 0 largest average: 9339.83 found at cells: (999,1504) elapsed time: 0.162964 vm-02$ ./matavg rand 4 1000 2000 3 largest average: 9370.22 found at cells: (874,617) elapsed time: 0.077152 vm-02$ ./matavg rand 1 1000 2000 3 largest average: 9370.22 found at cells: (874,617) elapsed time: 0.155171 vm-02$ ./matavg rand 10 1000 2000 3 largest average: 9370.22 found at cells: (874,617) elapsed time: 0.0878711 vm-02$ ./matavg rand 10 10000 2000 0 largest average: 9240.89 3 found at cells: (8524,739) elapsed time: 0.336246 vm-02$ ./matavg rand 1 10000 2000 0 largest average: 9240.89 found at cells: (8524,739) elapsed time: 2.0535 vm-02$ ./matavg rand 10 10000 20000 0 largest average: 9461.78 found at cells: (618,2726) elapsed time: 2.48621 vm-02$ Additional Files for this Project: 4 matAverager.cpp Page 1 of 4 #include #include #include #include #include #include #include using namespace std; // a class to get more accurate time class stopwatch{ private: std::chrono::high_resolution_clock::time_point t1; std::chrono::high_resolution_clock::time_point t2; bool timing; public: stopwatch( ): timing( false ) { t1 = std::chrono::high_resolution_clock::time_point::min(); t2 = std::chrono::high_resolution_clock::time_point::min(); } void start( ) { if( !timing ) { timing = true; t1 = std::chrono::high_resolution_clock::now(); } } void stop( ) { if( timing ) { t2 = std::chrono::high_resolution_clock::now(); timing = false; } } void reset( ) { t1 = std::chrono::high_resolution_clock::time_point::min(); t2 = std::chrono::high_resolution_clock::time_point::min();; timing = false; } // will return the elapsed time in seconds as a double double getTime( ) { std::chrono::duration elapsed = std::chrono::duration_cast(t2-t1); return elapsed.count(); } }; // function takes an array pointer, and the number of rows and cols in the array, and // allocates and intializes the two dimensional array to a bunch of random numbers void makeRandArray( unsigned int **& data, unsigned int rows, unsigned int cols, unsigned int seed ) { // allocate the array data = new unsigned int*[ rows ]; for( unsigned int i = 0; i < rows; i++ ) 5 matAverager.cpp Page 2 of 4 { data[i] = new unsigned int[ cols ]; } // seed the number generator // you should change the seed to get different values srand( seed ); // populate the array for( unsigned int i = 0; i < rows; i++ ) for( unsigned int j = 0; j < cols; j++ ) { data[i][j] = rand() % 10000 + 1; // number between 1 and 10000 } } void getDataFromFile( unsigned int **& data, char fileName[], unsigned int &rows, unsigned int &cols ) { ifstream in; in.open( fileName ); if( !in ) { cerr > cols; data = new unsigned int*[ rows ]; for( unsigned int i = 0; i < rows; i++ ) { data[i] = new unsigned int[ cols ]; } // now read in the data for( unsigned int i = 0; i < rows; i++ ) for( unsigned int j = 0; j < cols; j++ ) { in >> data[i][j]; } } int main( int argc, char* argv[] ) { if( argc < 3 ) { cerr
