1. Interest point detection: (a) [2 points] Write your own function for Harris corner metric using the harmonic mean (slide 29, lecture 6). Display your result for the attached image building.jpg showing your cornerness metric output. You can use built-in functions for convolution, gradients, but you must compute M yourself. Adjust α to get a good result.(b) [2 points] Write your own function to perform non-maximal suppression using ordfilt2.m or your own morphological operators function of choice. Use a circular element, and experiment with varying radii r as a parameter. Explain why/how the results change with r.(c) [2 points] Write code to search the image for scale-invariant interest point (i.e. blob) detection using the Laplacian of Gaussian and checking a pixel’s local neighbourhood as in SIFT. You may use code from tutorial 4 as a starting point. You must find extrema in both location and scale. Find the appropriate parameter settings, and display your keypoints for synthetic.png. Hint: Only investigate pixels with the LoG above or below a threshold.(d) [1 point] Compare and contrast the Harris corner metric with non-maximal supression as a keypoint detector to the Laplacian of Gaussian method. Show examples where they detect different keypoints and the same keypoints and explain why they are the same/different using synthetic.png and building.png.2. For this question you will use interest point detection for matching using SIFT. You may use a SIFT implementation (e.g. http://www.vlfeat.org/), or another, but specify what you use.(a) [0.5 points] Extract SIFT keypoints and features for book.jpg and findBook.jpg.(b) [1.5 points] Write your own matching algorithm to establish feature correspondence between the two images using the reliability ratio on Lecture 8, slide 23. You can use pdist2.m, but you must find the matches yourself. Experiment for different thresholds.(c) [2 points] Affine transformation: Use the top k correspondences from part (b) to solve for the affine transformation between the features in the two images via least squares using the Moore-Penrose psudeo inverse. Demonstrate your results for various k. Use only basic linear algebra libraries.(d) [0.5 point] Visualize the affine transformation. Do this visualization by taking the four corners of the reference image, transforming them via the computed affine transformation to the points in the second image, and plotting those transformed points. Please also plot the edges between the points to indicate the parallelogram. If you are unsure what the instruction is, please look at Figure 12 of [Lowe, 2004].(e) [1.5 points] Write code to perform matching that takes the colour in the images into account during SIFT feature calculation and matching. Explain the rational behind your approach. Use colourTemplate.png and colourSearch.png, display your matches with (2.d).3. Extra: [3 points] total (this is an optional exercise) Implement your own SURF feature descriptor, which is very similar in steps to SIFT. You can use any keypoint localization algorithm of your choice. See: http://www.vision.ee.ethz.ch/ surf/eccv06.pdf and or Algorithm 6 in http://www.ipol.im/pub/art/2015/69/.You may submit up to two days late without penalty if you do well in this exercise. (a) [2 points] Your descriptor must include: • Build your own Harr-wavlet filters • Computation of Harr-wavlet responses • Obtain the orientation using a circular neighbourhood of radius 6s.• Gaussian weighting • Rotation and scale invariance via feature window re-orientation and scale fitting (you can use bilinear interpolation instead of integral images) • Feature sub-binning into a 4×4 block of regions and 16 features per region(b) [1 points] Compare your algorithm to SIFT for the book.jpg and findBook.jpg pair, and at least two additional of your own image pairs, and discuss the pros/cons in accuracy. Don’t worry about the speed of your implementation.
1. (a) [2 points] Write your own code for computing convolution of the 2D (grayscale) image and a 2D filter. Make the output matrix be the same size as the input image. Be careful to correctly deal with the border of the image. The easiest way to do this is to “zero-pad” the image prior to convolution.(b) [1.5 points] Is it possible to write a convolution in one pixel as a dot product between two vectors? Is it possible to write the full convolution between the image and the filter via matrix multiplication?2. (a) [1 points] Given a n×n image, I, and m×m filter, h, what is the computational cost of computing h × I (the convolution)? What is the computational cost if h is a separable filter?(b) [1 points] If I first convolve an image with a Gaussian filter with σ = 3, and then convolve the output with a Gaussian with σ = 8, this gives an equivalent result as if I just convolve the image with a Gaussian with what σ?(c) [1 points] Write your own function that creates an anisotropic Gaussian filter with σx and σy as an input parameter.(d) [1 points] Convolve the attached cat.jpg with a (2D) Gaussian filter with σx = 15 and σy = 2 and visualize the result (display the result of the convolution). You can use built-in functions for convolution.(e) [1 points] The Gaussian filter in question 2.d is separable. How can you use this fact to speed up convolution? What are the vertical and horizontal filters? No need to write code.3. (a) [1.5 points] Compute magnitude of gradients for the attached images templateNoise.png and waldoNoise.png using convolution at three different scales.(b) [1 points] Write a function that localizes the template (templateNoise.png) in the image waldoNoise.png based on the magnitude of gradients. You can help yourself using findWaldo.m.4. (a) [1 points] Run the Canny edge detector on tennisCourt.jpg. Play with the parameters so that you get rid of low-contrast edges. In Matlab you can help yourself with function edge.(b) [1 points] Any idea how you could find the bounds of the court in the image? No need to write code, just brainstorm!5. [3 points] total (this is an optional exercise) Implement seam carving using Dijkstra’s algorithm for shortest paths: (a) Compute magnitude of gradients of an image(b) Build a directed image graph with a source and a sink(c) Find the connected path of pixels that has the smallest sum of gradients. A path is valid if it is connected (the neighboring points in the path are also neighboring pixels in the image), it starts in the first row of the image and in each step continues one row down. It finishes in the last row of the image. Hint: It is easier to restrict your graph, than to modify Dijkstra’s to exhibit this property.(d) You do not have to write your own Dijkstra’s algorithm. In Matlab you can use graphshortestpath. (e) Remove the pixels in the path from the image. This gives you a new image with one column less.(f) [2 points] Remove a few paths with the lowest sum of gradients. Create (fun!) examples with a few of your own images.(g) [1 points] Could you use this algorithm (with minor modifications) to segment the bull in cattle.png? A segmentation is a closed path following the boundary of the object. You can use mouse-clicks, e.g. ginput, to specify initial points on the object boundary. You will need at least two points, try to get it working with as few as possible.1 Sources 1. cat.jpg Osamu, Uchida, https://www.flickr.com/photos/13975275@N00/ 2. tennisCourt.jpg Michael, Coghlan, https://www.flickr.com/photos/mikecogh/
Exercise 1. Suppose that we have a learning scenario with 8 possible input vectors x1, . . . , x8, each being a 3-bit binary vector. We are given a training dataset D that contains {(x1, y1), . . . ,(x5, y5)}. Each label yn is either ◦ or •. The relationship between xn and yn is given by an unknown target function f : X → Y. Since there are only three variables to be learned from data, there is a total of 2 3 possible f’s we can possibly have.They are summarized in the figure below. xn yn g f1 f2 f3 f4 f5 f6 f7 f8 0 0 0 ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ 0 0 1 • • • • • • • • • • 0 1 0 • • • • • • • • • • 0 1 1 ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ 1 0 0 • • • • • • • • • • 1 0 1 ? ◦ ◦ ◦ ◦ • • • • 1 1 0 ? ◦ ◦ • • ◦ ◦ • • 1 1 1 ? ◦ • ◦ • ◦ • ◦ •The following exercises involve different choices of the hypothesis set H. You need to (i) Identify the final hypothesis g by listing the 8 entries it has for the 8 input vectors x1, . . . , x8. For example, you can write g = [◦, •, •, ◦, •, ◦, •, •]. (ii) Compute how many of the 8 possible target functions agree with g on all the three out-sample points, on two of them, one one of them, and on none of them. For example, if g = [◦, •, •, ◦, •, ◦, •, •], then it will match with three out-samples once (f4), match with two out-samples three times (f2, f3, f8), etc.(a) H has only two hypotheses h1 and h2. The first hypothesis h1 always return •, and the second hypothesis h2 always return ◦. The learning algorithm picks the hypothesis that matches the training set D the most.(b) Same as (a), but the learning algorithm picks the hypothesis that matches the training set D the least. (c) H = {h}, where h is the XOR operation. That is, h(x) = • if x contains an odd number of 1’s and h(x) = ◦ if x contains an even number of 1’s.Exercise 2. In this exercise, we shall illustrate, with a simple numerical example, that given a hypothesis set H = {h : X → {+1, −1}} and samples {(xn, yn)} N n=1, if one does not let the hypothesis function h ∈ H be independent of the samples when computing the in-sample error Ein, then the probability P(|Ein(h) − Eout(h)| > ϵ) does not necessarily obey Hoeffding’s inequality.More specifically, for the final hypothesis g picked by the learning algorithm based on the training samples, P(|Ein(g)−Eout(g)| > ϵ) does not necessarily satisfy the Hoeffding’s inequality, and we indeed require the uniform bound.Consider the following random experiment. Suppose we have 1000 fair coins. We flip each coin independently for N = 10 times.Let’s focus on 3 coins as follows: • coin1 = the first coin flipped. • coinrand = a coin you choose at random from the 1000 coins. • coinmin = the coin that had the minimum frequency of heads. (You have 1000 coins and each is flipped 10 times. So one of the 1000 coins will have the minimum frequency of heads. In case of a tie, pick the earlier one).Let V1, Vrand and Vmin be the fraction of heads we obtain for coin1, coinrand and coinmin respectively. (a) What is the probability of getting a head for coin1, of getting a head for coinrand and of getting a head for coinmin? Denote them by µ1, µrand and µmin, respectively.(b) In Python, repeat this entire experiment for 100, 000 runs to get 100,000 instances of V1, Vrand and Vmin. Plot the histograms of the distributions of these three random variables.(c) Using (b), plot the estimated P(|V1 −µ1| > ϵ), P(|Vrand −µrand| > ϵ) and P(|Vmin −µmin| > ϵ), together with the Hoeffding’s bound 2 exp(−2ϵ 2N), for ϵ = 0, 0.05, 0.1, …, 0.5.(d) Which coins obey the Hoeffding’s bound, and which ones do not? Explain why. Hint: Note that µ1, µrand and µmin are not necessarily equal to E[V1], E[Vrand] and E[Vmin] respectively. Pay particular attention to Vmin and its E[Vmin] and µmin!Exercise 3. Project Checkpoint #6 This is the final checkpoint for your project. As you can see, the amount of homework is reduced because I understand that you need more time to focus on your project.The final project report is due on Apr 30, 2022, 4:59pm Eastern Time. Please submit through gradescope. All reports must be typed using the ICML template (in LaTeX). The page limit is 10 pages. References do not count towards the page limit.Also, please upload your code to a github repository and put the link to the repository in your report. If you want to keep your repository private, you can upload to Purdue’s internal Github at https://github. itap.purdue.edu/ as a private repository and add the teaching staff as collaborators.• Every report will be reviewed by 3 teaching staff. You can treat them as the conference reviewers. • Each teaching staff will be asked to fill out a score sheet based on the following criteria listed on the course website. Your score will be the average of the scores from three independent reviewers.– Does the paper clearly state the problem that the implemented machine learning model targets? You will have to use your own language to describe the problem. Heavy penalty will be added for copying (with moderate modification of) the original paper. Does the paper identify and clearly descirbe similar works in the related work, and lists their advantages and disadvantages?– Does the paper explain the mathematical derivation well? You will have to use your own language to form the mathematical derviation. Heavy penalty will be added for copying (with moderate modification of) the original paper.– Does the paper clearly state the technical difficulties in the reimplementation and possible solutions? – Does the paper identify, describe, and analyze the effect of different engineering practices, e.g., implementation tricks and parameter/hyperparameter choices, using scientific languages? – Does the student train the implemented model using the dataset they select, and identify and solve issues that prevent the model from convergence?– Does the paper analyze the experimental behaviors of their model on selected application and compare with baselines? – Are there sufficient experiments demonstrating the success of re-implementation?– Are the limitations/assumptions clearly stated in the paper? Are there overclaim? Heavy penalty will be added for overclaim. – The amount of work in the reimplementation. – Is the paper easy to read? Are your ideas elaborated clearly?
We analyze the convergence behavior of the logistic regression when the data is linearly separable. Recall that the logistic regression tries to minimize the cross-entropy loss: θb = argmin θ∈Rd − X N n=1 n yn log hθ(xn) + (1 − yn) log(1 − hθ(xn))o , (1) where hθ(x) = 1 1+exp{−θ T x} is the sigmoid function. As usual, we assume that θ = [w, w0]. We consider the gradient descent algorithm.We know that the objective function is convex, and so we consider the gradient descent algorithm.The iterations are (if you take the derivative of J(θ) and rearrange the terms): θ (k+1) = θ (k) − αk X N n=1 (hθ (k) (xn) − yn)xn ! (2) for some choices of the step size αk.(i) Prove that if two classes of data in R d are linearly separable, then the magnitude of the slope ∥w∥2 and the magnitude of the intercept |w0| would tend to ∞. (ii) What happens if we restrict ∥w∥2 ≤ c1 and |w0| < c2 for some c1, c2 > 0? What other ways can you come up with to counter the nonconvergence issue? (iii) Does linear separability of data cause nonconvergence for the other linear classifiers that we have studied? Why?Download hw4_data.zip from Brightspace. There are two classes with class labels yn = 1 and yn = 0.(a) Show that the logistic regression loss is given by J(θ) = − X N n=1 ynxn !T θ − X N n=1 log 1 + e θ T xn .(b) Introduce a regularization term λ∥θ∥ 2 and normalize the data fidelity term so that the loss becomes J(θ) = − 1 N X N n=1 ynxn !T θ − X N n=1 log 1 + e θ T xn + λ∥θ∥ 2 . (3) Use CVXPY to minimize this loss function for the dataset I provided. Your θ should be θ = [θ2, θ1, θ0] T . Please use λ = 0.0001.(c) Scatter plot the data points by marking the two classes in two colors. Then plot the decision boundary.(d) Repeat (c), but this time using the Bayeisn decision rule. Note that since the covariance matrices are not identical, the decision boundary is not a straight line. To plot the decision boundary, you can create a grid of testing sites in the range of [−5, 10] × [−5, 10] (with 100 points along each dimension). Evaluate the decision on these testing sites. And then plot the decision using plt.contour.Let us continue to use the dataset in Exercise 2. Our goal here is to implement the kernel trick. (a) In Python, construct the kernel matrix K, where [K]m,n = exp −∥xm − xn∥ 2 /h , (4) where h = 1. Print K[47:52,47:52].(b) Let us assume that that θ = PN n=1 αnxn for some αn’s. Then θ T x = X N n=1 αn⟨xn, x⟩.The kernel trick says that we can replace ⟨xn, x⟩ by a kernel K(xn, x). Apply the kernel trick to the loss function in (3). Show that the new loss is J(α) = − 1 N y TKα − 1 T log(e 0 + e Kα) + λα TKα.(c) Implement the kernel logistic regression training in CVXPY. Report the first two elements of the regression coefficients α.(d) Scatter plot the data points and plot the decision boundary, just like what you did in Exercise 2(d).At this checkpoint, I expect you to have started reimplementing the assigned paper. Here are a couple important reminders for you.• Start simple. For the final project, we don’t need you to redo the experiment in the assigned paper. The purpose of this project is for you to reimplement the method so that it can be used for your own tasks. Therefore, start with as many assumptions as you need to keep your problem tractable. For example, you can assume the data you work on is low dimensional, or you can use simple dataset at first. The most important thing is to demonstrate something that works as soon as possible. Then, you can gradually make your program more complicated.• Leverage existing Python packages. You are allowed and encouraged to use many popular Python packages, such as numpy, TensorFlow, PyTorch, opencv, etc. For many basic operations that you want to achieve, it is likely that there are already implementations in these packages. So always check or ask first before you implement something basic by yourself.• Start early. Start early. Start early. Here are some good programming habits I appreciate. I know it might be hard to follow at first, but if you follow them for long enough time, they will gradually become your muscle memory. Furthermore, these habits will benefit you A LOT in the long run if you plan to work for a coding company.• Keep good naming conventions for your variables and functions, in which case you will not even need to write comments. Good code explains themselves. For example, here is a sample Python naming convention: https://visualgit.readthedocs.io/en/latest/pages/naming_convention.html.• Do not write functions that is too long, which will be difficult to debug. Keep a good structure for your program. Do not copy and paste the same code snippet in your program. If you want to reuse the same code snippet, write a function for it.• Do not use a lot of for loops. It will make your Python program super slow. Try to vectorize your program. See this page for more details. https://www.geeksforgeeks.org/vectorization-in-python/.• Train yourself to master debugging. It is normal that your code does not do what you want. The time to debug your code is the most valuable in terms of improving your programming skills. Everyone will have their own way to debug. My favorite debug tool is adding breakpoint in the program using pdb.set_trace().For this checkpoint, you need to create a new section in your overleaf document. In the section, write down the following things: • Write down the assumptions that you are making for your project.• Draw a diagram that describes the structure of your code. If you don’t know how to do it, simply use a box to represent each function in your program, specify what are the inputs and outputs, and connect the boxes according to your code structure. This will help us understand how you design your code.• Report any errors that you encounter when programming. If you have resolved the problem, what did you do? If not, what have you tried and why do you suspect that you cannot solve the problem?
Exercise 1 Suppose that we are given a dataset D def = {xn} N n=1, where each sample xn ∈ R d is an iid copy of the random variable X. For simplicity, we assume that the distribution of X is a multi-dimensional Gaussian of mean µ ∈ R d and covariance Σ ∈ R d×d . We further assume that the mean vector µ is known and is given.Therefore, the likelihood of observing a sample xn is fully controlled by the covariance matrix, i.e., p(xn | Σ) = 1 (2π) d/2|Σ| 1/2 expn − 1 2 (xn − µ) T Σ −1 (xn − µ) o (1)Taking into consideration of all the samples in the dataset D, the likelihood of D is p(D | Σ) = Y N n=1 1 (2π) d/2|Σ| 1/2 expn − 1 2 (xn − µ) T Σ −1 (xn − µ) o . (2)The goal of this analytical exercise is to derive the maximum-likelihood estimate of Σ: Σb ML = argmax Σ p(D | Σ). (3) To make things simpler we assume that Σ and Σe = 1 N PN n=1(xn−µ)(xn−µ) T are invertible in this exercise.(a) Recall that the trace operator is defined as tr[A] = Pd i=1[A]i,i. Prove the matrix identity x T Ax = tr[AxxT ], (4) where A ∈ R d×d .(b) Show that the likelihood function in (3) can be written as: p(D|Σ) = 1 (2π)Nd/2 |Σ −1 | N/2 exp ( − 1 2 tr” Σ −1 X N n=1 (xn − µ)(xn − µ) T #). (5) 1 (c) Let Σe = 1 N PN n=1(xn − µ)(xn − µ) T , and let A = Σ −1Σe, and λ1, …, λd be the eigenvalues of A. Show that the result from the previous part leads to: p(D|Σ) = 1 (2π)Nd/2|Σe|N/2 Y d i=1 λi !N/2 exp ( − N 2 X d i=1 λi ) (6) Hint: For matrix A with eigenvalues λ1, …, λd, tr[A] = Pd i=1 λi .(d) Find λ1, . . . , λd such that (6) is maximized.(e) With the choice of λi given in (d), prove that the ML estimate Σb ML is Σb ML = 1 N X N n=1 (xn − µ)(xn − µ) T . (7) (f) What would be the alternative way of finding Σb ML? You do not need to prove. Just briefly mention the idea. (g) If µ is also estimated from the data so that it is µb = 1 N PN n=1 xn, the ML estimate Σb ML = (1/N) PN n=1(xn− µb)(xn −µb) T will be a biased estimate of the covariance matrix because E[Σb ML] ̸= Σ. Can you suggest an unbiased estimate Σb unbias such that E[Σb unbias] = Σ? No need to prove. Just state the result.Exercise 2 In this exercise I want you to implement a Bayesian decision rule for a (super classical) problem of image segmentation. The image we work with consists of a cat and some grass 1 .The size of this image is 500×375 pixels. The left hand side of Figure 1 shows the image, and the right hand side of Figure 1 shows a manually labeled “ground truth”. Your task is to do as much as you can to extract the cat from the grass, and compare your result with the ”ground truth”.Figure 1: The “Cat and Grass” image. Preparation Steps (No need to hand in) First of all, go to the course website and download the data. Write the Python script to read the data and convert it into a data matrix. train_cat = np.matrix(np.loadtxt(‘train_cat.txt’, delimiter = ‘,’)) train_grass = np.matrix(np.loadtxt(‘train_grass.txt’, delimiter = ‘,’)) 1 Image Source: http://www.robots.ox.ac.uk/vgg/data/pets/ 2 The data matrices are 64 × K1 and 64 × K0, respectively, where K1 is the number of training samples for Class 1 (cat), and K0 is the number of training samples for Class 0 (grass).Throughout this exercise, you need to read images and extract patches. To read an image, you can call cv2 library or you can call plt.imread. For example, you can do Y = plt.imread(‘cat_grass.jpg’) / 255The decision making of this problem is performed for every pixel. Therefore, you need to write a for loop to loop through all the pixels of the image. Moreover, you need to extract 8 × 8 neighbors surrounding each pixel. These can be done using the following commands: M,N = Y.shape for i in range(M-8): for j in range(N-8): block = Y[i:i+8, j:j+8] # This is a 8×8 block # # Something #To make your life easier, it is okay to set the running index i in range(M-8) by neglecting the boundary pixels. In this case, the ground truth mask will have 8 rows and 8 columns less.The Bayesian decision rule we are going to implement is based on the posterior distribution. We define the likelihood functions: pX|Y (x|C1) = 1 (2π) d/2|Σ1| 1/2 expn − 1 2 (x − µ1 ) T Σ −1 1 (x − µ1 ) o , pX|Y (x|C0) = 1 (2π) d/2|Σ0| 1/2 expn − 1 2 (x − µ0 ) T Σ −1 0 (x − µ0 ) o , (8) and also the prior distributions pY (C1) = π1 and pY (C0) = π0. For simplicity, we assume that π1 = K1 K1+K0 and π0 = K0 K1+K0 . The Bayesian decision rule says that pY |X(C1|x) ≷ C1 C0 pY |X(C0|x), (9) which is based on the posterior distribution.(a) Substitute the multi-dimensional Gaussian likelihood (8) and the priors π1 and π0 into (9). Show that the decision rule is equivalent to − 1 2 (x − µ1 ) T Σ −1 1 (x − µ1 ) + log π1 − 1 2 log |Σ1| ≷ C1 C0 − 1 2 (x − µ0 ) T Σ −1 0 (x − µ0 ) + log π0 − 1 2 log |Σ0|. (b) Estimate µ1 , µ0 , Σ1, Σ0, π1 and π0 in Python.Report: (i) The first 2 entries of the vector µ1 and the first 2 entries of the vector µ0 . (ii) The first 2 × 2 entries of the matrix Σ1 and the first 2 × 2 entries of the matrix Σ0. (iii) The values of π1 and π0.(c) Write a double for loop to loop through the pixels of the testing image. At each pixel location, consider a 8 × 8 neighborhood. This will be the testing vector x ∈ R 64. Dump this testing vector x into the decision rule you proved in (a), and determine whether the testing vector belongs to Class 1 or Class 0. Repeat this for other pixel locations.for i in range(M-8): for j in range(N-8): block = Y[i:i+8, j:j+8] # # Something # prediction[i,j] = # Something If you do everything right, you will get a binary image. Submit this predicted binary image. Remark: My program runs for about 10-15 seconds. If your code takes forever to run, something is wrong.(d) Consider the ground truth image truth.png. Report the mean absolute error (MAE) between your prediction and the ground truth: MAE = 1 # of pixels X i,jprediction[i, j] − truth[i, j]. Report your MAE. Remark: Because we are not dealing with the boundary pixels (which explains why I set i in range(M-8)), when computing the MAE you need to set the true mask to truth[0:M-8, 0:N-8].(e) Go to the internet and download an image with similar content: an animal on grass or something like that. Apply your classifier to the image, and submit your resulting mask. You probably do not have the ground truth mask, so please just show the predicted mask. Does it perform well? If not, what could go wrong? Write one to two bullet points to explain your findings. Please be brief.Exercise 3 The objective of this exercise is to plot the ROC curve. You may want to read Chapter 9.4 and Chapter 9.5 of Prof. Stanley Chan’s book. (a) The Bayesian decision rule you derived in Exercise 2 is actually equivalent to the likelihood ratio test: pX|Y (x|C1) pX|Y (x|C0) ≷ C1 C0 τ, (10) for some threshold constant τ . Determine τ that corresponds to the decision rule in Exercise 2.(b) Implement this likelihood ratio test rule for different values of τ . For every τ , compute the number of true positives and the number of false positives. Then, we can define the probability of detection pD(τ ) and the probability of false alarm pF (τ ) as: pD(τ ) = # true positives total # of positives in ground truth pF (τ ) = # false positives total # of negatives in ground truth.Plot the ROC curve. That is, plot pD(τ ) as a function of pF (τ ). Your ROC curve should cover the range [0, 1] × [0, 1]. Remark: Generating this ROC curve will take a minute or two.(c) On your ROC curve, mark a red dot to indicate the operating point of the Bayesian decision rule.(d) Implement a linear regression classifier for this problem, and plot the ROC curve. The idea is to construct a matrix system: X1 X0 | {z } =A θ = 1 −1 | {z } =b , 4 where X1 ∈ R K1×d and X0 ∈ R K0×d are the training data matrix of Class 1 and Class 0. Solve the regression problem θb = argmin θ∈Rd ∥Aθ − b∥ 2 .During testing, write a double for loop to through all the 8 × 8 neighbors of the image pixels. The decision rule per neighbor is θb T x ≷ C1 C0 τ, (11) where θb is the trained model parameter, and x is the testing 8 × 8 neighbor. By varying the threshold τ , you can obtain another ROC curve. Plot it.Exercise 4: Project Check Point For this checkpoint, you need to play with the existing implementation that you identified in the previous checkpoint. First, please paste the paragraphs you wrote from Check Point 2 into your overleaf repository of the final project, if you haven’t done so. Then, add a new section for this checkpoint. In the new section, write about the following things:• What are the technical issues you encounter when you run the existing implementation? • Have you overcome these issues? If so, what did you do that successfully removed the issue? If not, what have you tried so far?• Generate some preliminary results, e.g., plots, numbers, etc. using the existing implementation. Present the preliminary results in the document and describe the results. Please attach the PDF generated from the repoistory to the end of your homework. This checkpoint aims to motivate you to understand your paper in concrete details. Don’t panic if you find it very hard to run the existing implementation, you can state what you have tried for this checkpoint and leverage the most of office hours to get your issue resolved.
The National Health and Nutrition Examination Survey (NHANES) is a program to assess the health and nutritional status of adults and children in the United States 1 . The complete survey result contains over 4,000 samples of health-related data of individuals who participated in the survey between 2011 and 2014.In this homework, we will focus on two categories of the data for each individual: the height (in mm) and body mass index (BMI). The data is divided into two classes based on gender. Table 1 contains snippets of the data.index female bmi female stature mm 0 28.2 1563 1 22.2 1716 2 27.1 1484 3 28.1 1651 index male bmi male stature mm 0 30 1679 1 25.6 1586 2 24.2 1773 3 27.4 1816 Table 1: Male and Female Data SnippetsUse csv.reader to read the training data files for the two classes of data. Specifically, you may call the commands below: import numpy as np import matplotlib.pyplot as plt import cvxpy as cp import csv # Reading csv file for male data with open(“male_train_data.csv”, “r”) as csv_file: reader = csv.reader(csv_file, delimiter=’,’) # Add your code here to process the data into usable form csv_file.close() # Reading csv file for female data with open(“female_train_data.csv”, “r”) as csv_file: reader = csv.reader(csv_file, delimiter=’,’) # Add your code here to process the data into usable form csv_file.close()Important: Before proceeding to the problems, please be careful that numerical solvers can perform very badly if the inputs to the problem are badly scaled, e.g. many coefficients being orders of magnitude apart; this is known as numerical instability. It is exactly the case for our matrix X. To avoid CVXPY (by default, the ECOS solver in it) returning bizarre solutions, please 1https://www.cdc.gov/nchs/nhanes/index.htm• normalize the number in male_stature_mm and female_stature_mm by dividing them with 1000, and • normalize that of male_bmi and female_bmi by dividing them with 10. This will significantly reduce the numerical error.Print the first 10 elements of each column of the dataset. That is, print • The first 10 entries of female BMI; • The first 10 entries of female stature; • The first 10 entries of male BMI; • The first 10 entries of male stature.Please submit your code, and submit your results.Consider a linear model: gθ = θ T x, (1) The regression problem we want to solve is θb = argmin θ∈Rd X N n=1 (yn − gθ(xn))2 , where D = {(xn, yn)} N n=1 is the training dataset. Putting the equation into the matrix form, we know that the optimization is equivalent to θb = argmin θ∈Rd ∥y − Xθ∥ 2 | {z } Etrain(θ) . (a) Derive the solution θb. State the conditions under which the solution is the unique global minimum in terms of the rank of X. Suggest two techniques that can be used when XT X is not invertible.(b) For the NHANES dataset, assign yn = +1 if the n-th sample is a male, and yn = −1 if the n-th sample is a female. Implement your answer in (a) with Python to solve the problem. Report your answer, and submit your code.(c) Repeat (b), but this time use CVXPY. Report your answer, and submit your code.(d) Derive the gradient descent step for this problem. That is, find the gradient ∇Etrain(θ k ) and substitute it into the equation: θ k+1 = θ k − α k∇Etrain(θ k ). If you use the exact line search, what is the optimal step size α k (for each iteration k)?(e) Implement the gradient descent algorithm in Python. Report your answer, and submit your code. Initialize θ 0 = 0. Use 50000 iterations.(f) For the gradient descent algorithm you implemented in (e), plot the training loss as a function of iteration number using plt.semilogx. Use linewidth = 8.(g) Implement the momentum method, with β = 0.9. Initialize θ 0 = 0. Use 50000 iterations. θ k+1 = θ k − α k β∇Etrain(θ k−1 ) + (1 − β)∇Etrain(θ k ) . Here, the step size α k can be determined through the exact line search.(h) For the momentum method you implemented in (g), plot the training loss as a function of iteration number using plt.semilogx. Use linewidth = 8.Hint: If you do everything right, the answers found by the analytic expression, CVXPY, and gradient descent should be the same.We want to do a classification based on the linear model we found in Exercise 2. The classifier we will use is predicted label = sign(gθ(x)), (2) where x ∈ R d is the a test sample. Here, we label +1 for male and -1 for female. Because the dataset we consider in this exercise has only two columns, the linear model is gθ(x) = θ0 + θ1×1 + θ2×2, where x = [1, x1, x2] T is the input data, and θ = [θ0, θ1, θ2] T is the parameter vector.(a) First, we want to visualize the classifier. (i) Plot the training data points of the male and female classes using matplotlib.pyplot.scatter. Mark the male class with blue circles, and the female class as red dots. (ii) Plot the decision boundary gθ(·), and overlay it with the data plotted in (a). Hint: gθ(·) is a straight line in 2D. You can express x2 in terms of x1 and other parameter.(b) Let us report the classification accuracy of male_test_data.csv and female_test_data.csv. To do so, take a testing data x and compute the prediction according to (2). (i) What is the Type 1 error (False Alarm) of classifying male? That is, what is the percentage of testing samples that should be female but you predicted it as a male. You can check the definition of Type 1 and Type 2 error on Wikipedia2 .(ii) What is the Type 2 error (Miss) of classifying male? That is, what is the percentage of testing samples that should be male but you predicted it as a female. (iii) What is the precision and recall for this classifier? For definition of precision and recall, you can refer to Prof. Stanley Chan’s book, Chapter 9.5.4, or Wikipedia.Please be sure to read the tutorial on optimization on the course website before doing this problem. Consider the following three optimization problems: θbλ = argmin θ∈Rd ∥Xθ − y∥ 2 2 + λ∥θ∥ 2 2 , (3) θbα = argmin θ∈Rd ∥Xθ − y∥ 2 2 subject to ∥θ∥ 2 2 ≤ α, (4) θbϵ = argmin θ∈Rd ∥θ∥ 2 2 subject to ∥Xθ − y∥ 2 2 ≤ ϵ. (5)(a) Set lambd = np.arange(0.1,10,0.1). Plot • ∥Xθbλ − y∥ 2 2 as a function of ∥θbλ∥ 2 2 • ∥Xθbλ − y∥ 2 2 as a function of λ • ∥θbλ∥ 2 2 as a function of λ(b) (i) Write down the Lagrangian for each of the three problems. Note that the first problem does not have any Lagrange multiplier. For the second and the third problem, you may use the notations: • γα = the Lagrange multiplier of (4), and • γϵ = the Lagrange multiplier of (5). 2https://en.wikipedia.org/wiki/Type_I_and_type_II_errors(ii) State the first order optimality conditions (the Karush-Kuhn-Tucker (KKT) conditions) for each of the three problems. See Tutorial 4 on Optimization, posted on the course website. Express your answers in terms of X, θ, y, λ, α, ϵ, and the two Lagrange multipliers γα, γϵ.(iii) Fix λ > 0. We can solve (3) to obtain θbλ. Find α and the Lagrange multiplier γα in (4) such that θbλ would satisfy the KKT conditions of (4).(iv) Fix λ > 0. We can solve (3) to obtain θbλ. Find ϵ and the Lagrange multiplier γϵ in (5) such that θbλ would satisfy the KKT conditions of (5).(v) This part follows from (iii). Fix λ > 0. By using the α and γα you found in (iii), you can show that θbλ would satisfy the KKT conditions of (4). Is it enough to claim that θbλ is the solution of (4)? If yes, why? If no, what else do we need to show? Please elaborate through a proof, if needed.By now, you should hear from us about your project assignment. We ask you to summarize in your own words the assigned paper in one or two paragraphs. Specifically, answer the following questions in your paragraph:• What is problem that the proposed method addresses? • Why is the problem important? • What are the innovations of this paper compared to previous methods?• Are there any existing implementations of the method? Which one will you start playing with? • Identify at least one key concept in the assigned paper that you are not familiar and you need to learn to reimplment the paper.Please keep these questions in your mind as you read through the paper. In this checkpoint, we want you to have an understanding of the big picture of the project and identify existing implementations that you can play with.You don’t have to answer them in dense detail. But you must reasonably address all above points in your paragraph to receive full points of this homework.
Let X be a random variable with X ∼ N (µ, σ2 ). The PDF of X is written explicitly as fX(x) = 1 √ 2πσ2 e − (x−µ) 2 2σ2 . (1)(a) Let µ = 0 and σ = 1 so that X ∼ N (0, 1). Plot fX(x) using matplotlib.pyplot.plot for the range x ∈ [−3, 3]. Use matplotlib.pyplot.savefig to save your figure.(b) Let us investigate the use of histograms in data visualization. (i) Use numpy.random.normal to draw 1000 random samples from N (0, 1). (ii) Make two histogram plots using matplotlib.pyplot.hist, with the number of bins m set to 4 and 1000.(iii) Use scipy.stats.norm.fit to estimate the mean and standard deviation of your data. Report the estimated values. (iv) Plot the fitted gaussian curve on top of the two histogram plots using scipy.stats.norm.pdf.(v) (Optional) Ask yourself the following questions: Are the two histograms representative of your data’s distribution? How are they different in terms of data representation?(c) A practical way to estimate the optimal bin width is to make use of what is called the cross validation estimator of risk of the dataset. Denoting h = (max data value−min data value)/m as the bin width, with m = the number of bins (assuming you applied no rescaling to your raw data), we seek h ∗ that minimizes the risk Jb(h), expressed as follows: Jb(h) = 2 h(n − 1) − n + 1 h(n − 1) Xm j=1 pbj 2 , (2) where {pbj} m j=1 is the empirical probability of a sample falling into each bin, and n is the total number of samples.(i) Plot Jb(h) with respect to m the number of bins, for m = 1, 2, …, 200. (ii) Find the m∗ that minimizes Jb(h), plot the histogram of your data with that m∗ . (iii) Plot the Gaussian curve fitted to your data on top of your histogram.Note: For additional discussions about this cross-validation technique, visit Introduction to Probability for Data Science, Chapter 3.2.5. More advanced materials can be found in the supplementary note of this homework.In this exercise, we consider the following question: suppose that we are given a random number generator that can only generate zero-mean unit variance Gaussians, i.e., X ∼ N (0, I), how do we transform the distribution of X to an arbitrary Gaussian distribution? We will first derive a few equations, and then verify them with an empirical example, by drawing samples from the 2D Gaussian, applying the transform to the dataset, and checking if the transformed dataset really takes the form of the desired Gaussian.(a) Let X ∼ N (µ, Σ) be a 2D Gaussian. The PDF of X is given by fX(x) = 1 p (2π) 2|Σ| exp − 1 2 (x − µ) T Σ −1 (x − µ) , (3) where in this exercise we assume X = X1 X2 , x = x1 x2 , µ = 2 6 , and Σ = 2 1 1 2 (4)(i) Simplify the expression fX(x) for the particular choices of µ and Σ here. Show your derivation. (ii) Using matplotlib.pyplot.contour, plot the contour of fX(x) for the range x ∈ [−1, 5]×[0, 10].(b) Suppose X ∼ N (0, I). We would like to derive a transformation that can map X to an arbitrary Gaussian. (i) Let X ∼ N (0, I) be a d-dimensional random vector. Let A ∈ R d×d and b ∈ R d . Let Y = AX +b be an affine transformation of X. Let µY def = E[Y ] be the mean vector and ΣY def = E[(Y −µY )(Y − µY ) T ] be the covariance matrix. Show that µY = b, and ΣY = AAT . (5)(ii) Show that ΣY is symmetric positive semi-definite. (iii) Under what condition on A would ΣY become a symmetric positive definite matrix? (iv) Consider a random variable Y ∼ N (µY , ΣY ) such that µY = 2 6 , and ΣY = 2 1 1 2 . Determine A and b which could satisfy Equation (5).Hint: Consider eigen-decomposition of ΣY . You may compute the eigen-decomposition numerically. (c) Now let us verify our results from part (b) with an empirical example. (i) Use numpy.random.multivariate_normal to draw 5000 random samples from the 2D standard normal distribution, and make a scatter plot of the data point using matplotlib.pyplot.scatter.(ii) Write a Python program using numpy.linalg.eig to obtain A given ΣY in part (b)(iv). Apply the transformation to the data point, and make a scatter plot of the transformed data points to check whether the transformation is correct.(iii) (Optional) Do your results from parts (c)(i) and (ii) support your theoretical findings from part (b)? You can find more information about Gaussian whitening in Introduction to Probability for Data Science, Chapter 5.7.4.Let us consider a polynomial fitting problem. We assume the following model: y = β0 + β1L1(x) + β2L2(x) + . . . + βpLp(x) + ϵ, (6) where Lp(x) is the p-th Legendre polynomial, βj are the coefficients, and ϵ is the error term. In Python, if you have specified a list of values of x, evaluating the Legendre polynomial is quite straight forward: import numpy as np from scipy.special import eval_legendre x = np.linspace(-1,1,50) # 50 points in the interval [-1,1] L4 = eval_legendre(4,x) # evaluate the 4th order Legendre polynomial for x (a) Let β0 = −0.001, β1 = 0.01, β2 = 0.55, β3 = 1.5, β4 = 1.2, and let ϵ ∼ Gaussian(0, 0.2 2 ).Generate 50 points of y over the interval x = np.linspace(-1,1,50). That is, x = np.linspace(-1,1,50) # 50 points in the interval [-1,1] y = … # fill this line Scatter plot the data.(b) Given the N = 50 data points, formulate the linear regression problem. Specifically, write down the expression βb = argmin β ∥y − Xβ∥ 2 . (7) What are y, X, and β? Derive the optimal solution for this simple regression problem. Express your answer in terms of X and y.(c) Write a Python code to compute the solution. Overlay your predicted curve with the scattered plot. For solving the regression problem, you can call numpy.linalg.lstsq.(d) For the y you have generated, make 5 outlier points using the code below: # … idx = [10,16,23,37,45] # these are the locations of the outliers y[idx] = 5 # set the outliers to have a value 5 # … Run your code in (c) again. Comment on the difference. (e) Consider the optimization βb = argmin β ∥y − Xβ∥1. (8)Convert the problem into a linear programming problem. Express your solution in the linear programming form: minimize x c T x subject to Ax ≤ b. (9) What are c, x, A, and b?(f) Solve the linear programming problem in Python using scipy.optimize.linprog, for the corrupted data in (d). Scatter plot the data, and overlay with your predicted curve. Hint: Remember to set bounds=(None,None) when you call scipy.optimize.linprog, because the variables in linprog are non-negative by default. For this problem, you may want to check Introduction to Probability for Data Science, Chapter 7.1.4.By now I believe you should have read the course project instructions. If not, please read them now. The objective of this series of “check points” is to keep track of your progress, so that you will not wait until the last minute and then become panic.For check point 1, I want you to complete the following tasks. 1. Go through every topic listed on the course project webpage. You don’t have to understand the technical details, but you need to know what’s the purspose of the work. Then go to this Google Form https://forms.gle/435QAHQ6n83gYW7g6 to fill in your preference. The deadline of this form is the same as the homework deadline. If you don’t finish this survey, we will have to assign your project preference randomly.2. Latex. I only accept final reports typed in Latex, using the ICML 2021 template. You can use overleaf (a free online platform) to type your report. Download the ICML template, put it in overleaf. Change the title to the paper title of your first choice, and change the author name to your name. When typing your name, please tell us: Your name, your major (e.g., ECE, AAE, etc), and your level (e.g., Online MS, PhD, Undergrad, etc)Clear the rest of the contents of in the document and attach this empty document to the end of your homework submission. (By default the ICML template uses the review mode. Please switch it to the camera ready mode.)
1 Introduction Your goal in this step is to generate code to handle programs with multiple functions. This means you will have to handle two aspects: (i) what should a caller function do to prepare for calling a subroutine; (ii) what should a callee function do to set up its local variables and environment? 1.1 Function Calls The primary mechanism for handling function calls is the program stack, which is where the local environment (activation record or frame) for each currently executing function (i.e., functions that have started executing but have not yet returned) is stored. Week 9 slides provide more details about how this program stack works. 1.2 Activation Records An activation record, or frame, stores all of the data required to execute a function. In particular, this means that the activation record stores all of the local variables in a function. We declare global variables with var declarations in Tiny code, but that doesn’t work for local variables. Why? Because a local variable is specific to that function invocation – it’s not global. Consider what would happen if you wrote a recursive function: the two versions of that recursive function each need their own copy of their local variables. An activation record is delimited by two “pointers”: the stack pointer (which is controlled with the instructions push and pop) and the frame pointer (which is controlled with the instructions link and unlink). The stack pointer points to the “top” of the stack, while the frame pointer points to the “base” of the activation record. In our stack organization, the stack conceptually grows “down”. Local variables thus have negative offsets from the frame pointer, while arguments and return values have positive offsets from the frame pointer You will need to augment your symbol table to maintain a mapping between each local variable and its slot in an activation record. (Don’t forget to reset the slot counter for each new function!) We recommend that you draw out the program stack for a simple program to understand how to correctly generate code for it. 1.3 Implementing a function call You can divide up the work done for a function call into two responsibilities: those of the caller and those of the callee. Here is what each one needs to do: Caller before the call 1. Push any registers that you want to save on the stack (using push) 2. Push a space on the stack for the return value of the callee 3. Push any arguments onto the stack 4. Call the function (using jsr) Note: in some of the outputs, step 1 is performed after 2 and 3; this is fine, as long as you are consistent and are able to correctly know where arguments/return values are Callee 1. Allocate space on the stack for all the local variables (using link) 2. Generate code, accessing local variables and arguments to the function relative to the frame pointer (Use $-n to access slots below the frame pointer, with n replaced with the slot location, and $n to access slots above the frame pointer) 3. When returning from the function, save the return value (if any) in the appropriate slot “above” the frame pointer (remember how the caller set up its portion of the stack). 4. Deallocate the activation record (using unlink) 5. Return to the caller (using ret) Caller after the call 1. Pop arguments off the stack 2. Pop the return value of the stack, remembering to store it in an appropriate place (local variable, global variable, register, etc., as needed by the source code) 3. Pop any saved registers off the stack. In this step, your code generation strategy likely means that no registers actually need to be saved on the stack by the caller, because none are “live” across the function call. If you choose not to save registers in this step, remember to add that functionality back in for the next step (register allocation) Testing your Tiny code You can test your Tiny code by using the same simulator as in the previous step. Your compiler will be tested against the inputs that we provide with the starter files and also some hidden test cases. 2 What you need to do In this step, you will be generating assembly code for function calls, as described above. You should correctly be able to handle functions with return values, functions where complex expressions are passed in as arguments (store the result in a temporary, then push that temporary onto the stack as the argument), and recursive functions. Handling errors All the inputs we will give you in this step will be valid programs. We will also ensure that all expressions are type safe: a given expression will operate on either INTs or FLOATs, but not a mix, and all assignment statements will assign INT results to variables that are declared as INTs (and respectively for FLOATs). Sample inputs and outputs are provided to you along with the starter files that you need to get started on this assignment. These contain a test case with non recursive functions (fma) and couple of test cases with recursive functions factorial2 and fibonacci. Grading In this step, we will only grade your compiler on the correctness of the generated code. We will run your generated code through the Tiny simulator and check to make sure that you produce the same result as our code. When we say result, we mean the outputs of any WRITE statements in the program (not details such as how many cycles the code uses, how many registers, etc.) 3 What you need to submit • A Makefile with the following targets: 1. compiler: this target will build your compiler. (-1 for warnings) 2. clean: this target will remove any intermediate files that were created to build the compiler. (-1 for not doing the clean properly) 3. dev: this target will print the same information that you printed in previous PA. • A shell script (this must be written in bash) called runme that runs your compiler. This script should take in two arguments: first, the input program file to be compiled and second, the filename where you want to put the compiler. You can assume that we will have run make compiler before running this script. • You should tag your programming assignment submission as cs316pa6submission Do not submit any binaries. Your git repo should only contain source files; no products of compilation. If you have a folder named test in your repo, it will be deleted as part of running our test script (though the deletion won’t get pushed) – make sure no code necessary for building/running your compiler is in such a directory.
1 Introduction 2 Liveness The first step in performing register allocation is performing a liveness analysis. We are asking you to perform liveness analysis across an entire function at once. See Week 12 (Slide 6 onwards) for more details. 2.1 Control flow graphs The first step in computing liveness is to build a control flow graph for each function in your program. To represent your control flow graph, each IR Node should know its successors (IR instructions that could possibly execute immediately after it) and predecessors (IR instructions that could possible execute immediately before it). Conditional jumps have two successors: the explicit target of the jump, and the implicit (fall-through) target of the jump. Unconditional jumps only have one successor. Function calls should be treated as straight-line IR nodes (i.e., they are not treated as branches; their successor is the instruction immediately after the call). Return nodes do not have any successors. 2.2 Computing Liveness For each IR node in a function, you should define two sets: GEN and KILL. GEN represents all the temporaries and variables that are used in an instruction, and KILL represents all the temporaries and variables that are defined in an instruction. For most instructions, this should be pretty straightforward. A few tricky cases: • PUSH instructions use the variable/temporary being pushed • POP instructions define the variable/temporary being popped • WRITE instructions use their variables. • READ instructions define their variables. • The set of variables that are live out of a node is the union of all the variables that are live in to the node’s successors. • The set of variables that are live in to a node is the set of variables that are live out for the node, minus any variables that are killed by the node, plus any variables that are gen-ed by the node. Note that in these definitions are recursive: the live-out set of a node is defined in terms of the live-in sets of its successors, which are in turn defined in terms of the live-in sets of their successors, and so on. If there is a loop in the code, then the definition seems circular. The trick to computing liveness is to compute a fixpoint: assignments to each of the live-in and live-out sets so that if you try to compute any node’s live-in or live-out set again, you’ll get the same result you already have. To do this, we will use a worklist algorithm: 1. Put all of the IR nodes on the worklist 2. Pull an IR node off the worklist, and compute its live-out and live-in sets according to the definitions above. 4. Repeat steps 2 and 3 until the worklist is empty. (Note: you can write a slower version of this code that ignores identifying nodes’ predecessors. This still works. However, we suggest you to put all the IR nodes on the worklist and process all of them. If any live-in or live-out set has changed, put all the IR nodes on the work list and repeat the process.) 3 Register Allocation Algorithm Use the bottom-up register allocation algorithm or the graph-coloring method discussed in class. For each statement, you must ensure that the source operands are in registers, and that there is a register for the destination operand. Use the liveness information you computed (i.e., the live-out set for the instruction) to determine when it is safe to free registers, and when a dirty register needs to be stored back to memory (only when the variable in the register is live). Bottom-up register allocation works at the basic-block level: any register allocation decisions you make apply for the current basic block only. This means that when you get to the end of a basic block, you must reset your register allocation. Any register that (a) holds local/global variables and (b) is dirty should be written back to the stack/global variable. Note also that because a CALL instruction jumps into another method, any global variables that are in registers when the CALL is performed should be freed immediately prior to the CALL instruction, ensuring that the correct value for the global is in memory. This is different from saving the registers on the stack prior to a function call. The latter is done so that the caller method doesn’t get its registers overwritten; the values of the registers are stored where only the caller can see them. The former is done so that the callee method sees the right values for global variables; the values need to be stored back to globals so that everyone can see them, and freed from the registers so that the caller will reload them after the callee returns. Testing your Tiny code You can test your Tiny code by using, tiny4regs.C, a version of the simulator that limits you to 4 registers. tiny4regs.C is provided to you along with the starter files. There are no test cases provided along with the starter files for this assignment. You must test your compiler with all the test cases of PA4, PA5, and PA6. In addition, we will test with some hidden test cases. 4 What you need to do Perform the liveness analysis and register allocation steps as described above, so that your compiler generates code that only uses 4 registers. Handling errors All the inputs we will give you in this step will be valid programs. We will also ensure that all expressions are type safe: a given expression will operate on either INTs or FLOATs, but not a mix, and all assignment statements will assign INT results to variables that are declared as INTs (and respectively for FLOATs). Grading In this step, we will only grade your compiler on the correctness of the generated code. We will run your generated code through the Tiny simulator and check to make sure that you produce the same result as our code. When we say result, we mean the outputs of any WRITE statements in the program (not details such as how many cycles the code uses, how many registers, etc.) 5 What you need to submit • Place all the necessary code for your compiler that you wrote yourself. • A Makefile with the following targets: 1. compiler: this target will build your compiler. (-1 for warnings) 2. clean: this target will remove any intermediate files that were created to build the compiler. (-1 for not doing the clean properly) 3. dev: this target will print the same information that you printed in previous PA. • A shell script (this must be written in bash) called runme that runs your compiler. This script should take in two arguments: first, the input program file to be compiled and second, the filename where you want to put the compiler. You can assume that we will have run make compiler before running this script. • You should tag your programming assignment submission as cs316pa7submission Do not submit any binaries. Your git repo should only contain source files; no products of compilation. If you have a folder named test in your repo, it will be deleted as part of running our test script (though the deletion won’t get pushed) – make sure no code necessary for building/running your compiler is in such a directory.
1 Introduction In this project, you’ll be doing the following: • Implementing some basic sequential logic elements (3.1). • Building three missing pieces of the LC-3 hardware (3.2). • Writing the microcode for the bulk of the LC-3 instructions (3.4). 1.1 Latches The first thing you’ll implement are sequential logic elements. These allow us to retain data in a circuit, in other words “remember” a previous value. This allows us to have logic that depends on the last event that happened in a sequence of events, in other words sequential logic. The goal of this section is to produce a register. A register is an edge-triggered sequential logic circuit element that can store a binary value. For more on this section, see Implementation: Latches 1.2 The LC-3 The LC-3 datapath we’ve discussed in class contains a lot of pieces very similar to circuits we’ve seen or even made before (e.g. an ALU, a register file with 8 edge-triggered general purpose registers, a RAM unit, etc.). One piece that we’ve mostly referred to as a “black-box” in the past is the micro-controller. It’s responsible for controlling the entire datapath and getting it to properly execute the instructions that we give it. That’s a big task! So, how does the micro-controller actually work? In this project, we’ll build a few datapath components to develop some familiarity with the LC-3, and then we’ll actually write the “microcode” which allows the micro-controller to function.The micro-controller, shown above, is a finite state machine. It has 59 possible states (holy cow!) and, thus, needs 6 bits to store all its possible states. It also has 49 output bits composed of output flags. 10 of these bits are used to determine the next state and the remaining 39 extend throughout the datapath to control other pieces of the LC-3. That would be a lot of very complex hardware—if it were built entirely in hardware. As it turns out, there is an easier way. We can actually use a ROM (Read-Only Memory) in order to specify the behavior of each distinct state in the state machine (e.g. each instruction will map to a series of entries in the ROM. Each entry in the ROM represents a micro-state, which is an individual state of the finite state machine and a component of a larger sequence of states known as a macro-state. There are 3 macro-states in the LC-3: FETCH, DECODE, and EXECUTE. Each macro-state requires between 1-5 micro-states to complete, depending on the complexity of the instruction. What does a ROM entry look like? We encourage you to go ahead and open up microcode.xlsx, on the microcode sheet, to follow along.A ROM entry is basically a long binary string. The last few bits of it handle the transition to the next state—you don’t need to worry about this at all during this project, so we’ve covered it in dark grey on the right. Do NOT modify the NEXT bits. Each of the other bits corresponds to a signal asserted onto the datapath during that clock cycle—this is what you will fill out!. We’ve simplified and removed a number of micro-states and control signals which aren’t directly a part of the LC-3’s main instructions. You are given the microcode for some of these micro-states, along with entries for the DRMUX and SR1MUX—do NOT change these. Your task is to fill in the rest and finish the LC-3 micro-controller! 1.3 Assignment Files • latches.sim – a CircuitSim file in which you will build sequential logic components. • LC3.sim – a large CircuitSim file containing the LC-3 AND a “Manual LC-3” which does not need to be modified in any way but is simply present as a tool for you while writing microcode. You should only modify the PC, CC-logic, and ALU subcircuits in this file. • microcode.xlsx – an Excel document in which you will write your microcode. Do not touch cells that have been blacked out. • ROM.dat – a text file which you can paste your microcode into and then import into the LC-3. • tests/ – a subdirectory which contains a number of test cases you can use to verify the functionality of your circuit and microcode. • proj2-tester.jar – a local tester that you can use to test all of the components of the project. This official tester is available on Gradescope (where it will be return your grade). • LC-3InstructionsDetail.pdf – a PDF with descriptions and pseudocode for each instruction. 1.4 Elements to complete 1. Implement the RS Latch, Gated D Latch, D Flip-Flop, and Register subcircuits in latches.sim. 2. Implement the ALU, PC, and CC-Logic subcircuits in LC3.sim. 3. Complete the LC-3 microcode in microcode.xlsx. 2 Setup The software you will be using for this project and all future circuit based assignments is called CircuitSim – an interactive circuit simulation package. CircuitSim is a powerful simulation tool designed for educational use. This gives it the advantage of being a little more forgiving than some of the more commercial simulators. However, it still requires some time and effort to be able to use the program efficiently. Please follow the instructions in the file ”CircuitSim Installation Guide.pdf” in Canvas, under ”Files > Course Software > CircuitSim” to install CircuitSim. All .sim files should be opened in CircuitSim. Please do not move, rename, or remove any of the provided inputs/outputs. 3 Implementation 3.1 Latches For this part of the assignment, you will build your own register from the ground up. For more information about each subcircuit, refer to your textbook. All work for this portion of the assignment will be done in the latches.sim file. 3.1.1 RS Latch In the “RS Latch” subcircuit in the latches.sim file, you will start by building a RS latch using NAND gates, as described in your textbook. RS Latch is the basic circuit for sequential logic. It stores one bit of information and has 3 important states: 1. S=1, R=1: This is called the Quiescent State. In this state the latch is storing a value, and nothing is trying to change that value. 2. S=0, R=1: By changing momentarily from the Quiescent State to this state, the value of the latch ischanged so that the output Q now stores a 1. 3. S=1, R=0: By changing momentarily from the Quiescent State to this state, the value of the latch ischanged so that the output Q now stores a 0. Once you set the bit you wish to store, change back to the Quiescent State to keep that value stored. Notice that the circuit has two output pins; one is the bit the latch is currently storing, and the other is the opposite of that bit. Note: In order for the RS Latch to work properly (for testing purposes, not for building), both R and S cannot be 0 at the same time (illegal state).3.1.2 Gated D Latch In the “Gated D Latch” subcircuit in the latches.sim file, using your RS latch subcircuit (in the Circuits tab), implement a Gated D Latch as described in the textbook. You are not allowed to use the built-in SR Latch in CircuitSim to build this circuit. The Gated D Latch is made up of an RS Latch as well as two additional gates that control when a value can be stored. The value of the output can only be changed when Write Enable is set to 1. Notice that the Gated D Latch subcircuit only has one output pin, so you should disregard the inverse output Q’ of your RS Latch.3.1.3 D Flip-Flop In the “D Flip-Flop” subcircuit in the latches.sim file, using the Gated D Latch circuit you built (in the Circuits tab), create a D Flip-Flop. A D Flip-Flop is composed of two Gated D Latches back to back, and it implements edge triggered logic. Your D Flip-Flop output should be able to change on the rising edge, which means that the state of the D Flip-Flop should only be able to change at the exact instant the clock goes from 0 to 1.3.1.4 Register In the “Register” subcircuit in the latches.sim file, using the D Flip-Flop you just created (in the Circuits tab), build a 4-bit Register. Your register should also use edge-triggered logic. The value of the register should change on the rising edge.3.2 Completing the LC3 SubCircuits All work for this section of the assignment will be done in the LC3.sim file. Note: DO NOT move the position of the inputs and outputs in the LC3 subcircuits; this could break the rest of the LC3 simulator. 3.2.1 ALU You will need to build the ALU (Arithmetic Logic Unit) subcircuit in LC3.sim. The ALU will perform one of 4 functions and Output it depending on the ALUK signal: 1. ALUK = 0b00: A + B 2. ALUK = 0b01: A & B 3. ALUK = 0b10: NOT A 4. ALUK = 0b11: PASS A You should be able to use what you learned from Project 1 to populate this subcircuit easily. 3.2.2 PC You will need to build the PC (Program Counter) subcircuit in LC3.sim. The PC is a 16 bit register that holds the address of the next instruction to be executed. During the FETCH stage, the contents of the PC are loaded into the memory address register (MAR), and the PC is updated with the address of the next instruction. There are three scenarios for updating the PC: 1. The contents of the PC are incremented by 1. Selected when PCMUX = 0b00. 2. The result of the ADDR (an address-adding unit) is the address of the next instruction. The outputfrom the ADDR should be stored in the PC. This occurs if we use the branching instruction (BR). Selected when PCMUX = 0b01. 3. The value on the BUS is the address of the next instruction. The value on the BUS should be storedinto the PC. For example, this is used during the JMP instruction. Selected when PCMUX = 0b10. The PC should only be loaded on a rising clock edge and when the LD.PC signal is on. Ensure that you don’t reach the unused case (PCMUX = 0b11) of the circuit, or else spooky stuff might happen (undefined behavior in LC-3). 3.2.3 CC-Logic You will implement the CC-Logic subcircuit in LC3.sim. The LC-3 has three condition codes: N (negative), Z (zero), and P (positive). These codes are saved on the next rising edge after the LC-3 executes Operate or Load instructions that include loading a result into a general purpose register, such as ADD and LDR. For example, if ADD R2, R0, R1 results in a positive number, then NZP = 001. The CC subcircuit should set N to 1 if the input is negative, set Z to 1 if the input is zero, and set P to 1 if the input is positive. Only 1 bit in NZP should be set at any given time. Zero is not considered a positive number. Bit 2 (the MSB) is N, Bit 1 is Z, Bit 0 is P. With that in mind, set the correct bit and implement this circuit in the CC-Logic subcircuit. Hint: you can use a comparator for this subcircuit! They are found in the Arithmetic tab in CircuitSim. 3.3 Using Manual LC-3 (for testing only) • Once you have your PC, CC-Logic, and ALU complete, you can begin playing around with the instructions and control signals to understand how the LC-3 works. • The first thing you will want to do is use the Custom-Bus, GateBUS, and LD.IR signals to set a custom IR value on the next rising edge. Until you figure out the micro-states for FETCH, you can use these steps to set your IR with any instruction you want to work on. • Once you have an idea of how FETCH works, you can load some instruction(s) in the RAM. In order to do that: 1. right-click the RAM near the bottom of the Manual LC-3 circuit 2. select “edit contents” 3. click “Load from file” 4. locate and select one of the provided test files in the project (ex: addand.dat) 5. close the edit contents menu • Now that you have loaded the RAM with a program, you can fetch instructions into the IR. – Tests inside the tests/ directory have a comment at the end of the .asm file which explains the system state after the end of the program’s execution. You must ensure that this is the system state after you have run every instruction sequentially through the simulator. – To test whether the program acted correctly, go to the ‘LC-3’ circuit and double-click into the ‘REG FILE’ element that is placed in the datapath. Note: you should not just click into the ‘REG FILE’ subcircuit, as this will not properly load the state of the specific ‘REG FILE’ element that’s built into the LC-3, just some generic REG FILE. – Bonus tip: Use Ctrl-R to reset the simulator state and easily clear RAM and registers to 0 in order to test again. 3.4 Writing the Microcode ONLY open this Excel Sheet in Microsoft Excel. Do NOT use other applications. If need help accessing Excel: https://oit.gatech.edu/email Note: We recommend you read this entire section before starting to fill out the microcode sheet. • DO NOT CHANGE: – NEXT bits (greyed out on the right side) – Values for DRMUX and SR1MUX (aleady filled in) – Any microstates that are already filled out for you As a general rule of thumb, try not to break the spreadsheet :). • Throughout this assignment, you will find the CS2110-Reference-Sheet.pdf to be very helpful. It can be found in the Canvas Files. • For information on filling out LDSR and STII, see below. • For more information on each of the control signals, see the Appendix at the end of this PDF. • For the Store instructions, ensure that you prioritize loading the address we want to write to into the MAR over loading the value we want to write with into the MDR. The autograder is expecting that you load the address first and then the value. • Now that you’ve developed some familiarity with the datapath, gotten a chance to “act as the microcontroller”, and run the execute stage of instructions on the Manual LC-3, you can complete the final part of the project: writing the microcode for a number of micro-instructions on the LC-3! • In the microcode.xlsx Excel spreadsheet, there exists a number of macro-states. Among them are FETCH, DECODE, and the EXECUTE stages for most instructions supported by the LC-3 (we’ve removed several macro-states related to trap and interrupt handling). For each macro-state, we’ve provided space for the micro-states which will make up that macro-state. For each micro-state, we’ve handled all of the logic related to transitioning to the next micro-state. We’ve also implemented a small subset of the macro-states in order to provide inspiration to you, our students (you’re welcome). • You should complete all the remaining macro-states by filling in their micro-states. • LDSR – This instruction should access memory at the value specified by the sum of the two source registers (SR1, SR2) and save the result on DR. – DR = Mem[SR1 + SR2] – The 16-bit instruction is formatted in the following: [ OPCODE | DR (3 bits) | SR1 (3 bits) | 000 (3 bits) | SR2 (3 bits) ] – Note: You need to set the condition codes (CC) for this instruction. • STII Indirect. – This instruction works similarly to STI but with one more trip to memory. To be more specific, we calculate an initial address by using the value of the PC and adding it to the offset. We access memory at this address and we use value we retrieve as an address to memory again. Then we use the new value we obtained as an address once again to access memory one last time. This final value we get from memory is the memory address where we will store the value of SR. The instruction is very similar to STI but with one more indirect address lookup on memory. – Mem[Mem[Mem[PC* + PCOffset9]]] = SR – The 16-bit instruction is formatted in the following: [ OPCODE | SR1 (3 bits) | PCOffset9 (9 bits) ] – Note: You do NOT need to set the condition codes (CC) for this instruction. We could really use your help! Fill out the micro-states for LDSR and STII in the microcode.xlsx excel sheet. 3.4.1 How to Test your Micro-code At any time that you want to test your micro-code, you can export it from the .xlsx file and apply it to LC-3 hardware by following these steps. IMPORTANT NOTE: Passing all of the tests provided does not guarantee that you have a functional datapath, any number of coincidences could cause you to get the correct output with incorrect functionality. As always, we reserve the right to grade with additional test cases. 1. At the bottom of the microcode.xlsx file select the output tab. 2. Copy all of column D from row 1 through row 64 3. Paste the result into ROM.dat 4. Ensure that ROM.dat is in the same directory as ./cs2110docker.sh (or some subdirectory) 5. Ensure that ROM.dat is populated with the correct values for the autograder to work 7. In Docker CircuitSim, open LC3.sim. Navigate to the ‘Fsm’ subcircuit. This circuit contains themicro-controller. 8. Right-click on the ROM and select “Edit contents.” 9. Select “Load from file” 10. navigate to and select “ROM.dat.” This will load the ROM. 11. Navigate to the ‘LC-3’ subcircuit. 12. You can now load a program into the RAM, following the instructions above in the Manual LC-3 sections. 13. To run the LC-3, you can manually click through the CLK signal or use ‘Ctrl-K’ to start or stop theautomatic clock. After your program has stopped executing (you can tell when it’s finished running because it will HALT and the datapath will stop changing). 14. Tests inside the tests/ directory have a comment at the end of the .asm file which explains the system state after the end of the program’s execution. To test whether the program acted correctly, go to the ‘LC-3’ circuit and double-click into the ‘REG FILE’ element that is placed in the datapath. Note: you should not just click into the ‘REG FILE’ subcircuit, as this will not properly load the state of the specific ‘REG FILE’ element that’s built into the LC-3, just some generic REG FILE. 3.4.2 Tips, Tricks, Resources This is all pretty crazy to take in at first. But it’s not the end of the world if you make sure to use the resources available to you. Here are some options: • CS 2110 Reference Sheet: Canvas → Files → CS2110-Reference-Sheet.pdf • LC-3 Instructions Detail Sheet: LC-3InstructionsDetail.pdf, in this project.zip • The Manual LC-3! • Textbook • Appendix on Datapath Control Signals in this PDF. 4 Autograder To run the autograder, run java -jar proj2-tester.jar at a command prompt in the same directory as all your deliverable files (see next section for a list). This is the same autograder that Gradescope uses, but is much easier and faster to use. The autograder should be run from the terminal. 5 Deliverables Please submit the follow files: 1. latches.sim 2. LC3.sim 3. microcode.xlsx to Gradescope under the assignment “Project 2 – LC-3 Datapath”. 6 Rules and Regulations 6.1 General Rules 2. Please read the assignment in its entirety before asking questions. 6.2 Submission Conventions 1. In order to submit your assignment, submit the files individually to the Gradescope assignment. 2. Do not submit links to files. The autograder does not understand it, and we will not manually gradeassignments submitted this way as it is easy to change the files after the submission period ends. 6.3 Submission Guidelines 2. You are also responsible for ensuring that what you turned in is what you meant to turn in. Aftersubmitting you should be sure to download your submission into a brand new folder and test it to see if it works. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your assignment must be turned in via Gradescope. Under no circumstances whatsoever will we accept any email submissions of an assignment. Note: if you were granted an extension you will still turn in the assignment over Gradescope. 3. Projects turned in late receive partial credit within the first 48 hours, as defined in the syllabus.Between 0 and 24 hours late, you can receive a maximum score of 70%. Between 24 and 48 hours late, you can receive a maximum score of 50%. We will not accept projects turned in over 48 hours late. 6.4 Is collaboration allowed? From the syllabus: 6.5 Syllabus Excerpt on Academic Misconduct The goal of all assignments in CS 2110 is for you to learn. Learning requires thought and hard work. Copying answers thus prevents learning. More importantly, it gives an unfair advantage over students who do the work and follow the rules. 3. Using code from GitHub, via Googling, from Stack Overflow, etc., is Academic Misconduct (HonorCode: Academic Misconduct includes “submission of material that is wholly or substantially identical to that created or published by another person or persons”). 4. Publishing your assignments on public repositories, github, etc, that is accessible to other students isunauthorized collaboration and thus Academic Misconduct. 5. Suspected Academic Misconduct will be reported to the Division of Student Life Office of StudentIntegrity. It will be prosecuted to the full extent of Institute policies. 6. Students suspected of Academic Misconduct are informed at the end of the semester. Suspects receive an Incomplete final grade until the issue is resolved. 7. We use accepted forensic techniques to determine whether there is copying of a coding assignment. 8. Submitting an assignment with code or text from an AI assistant (e.g., ChatGPT) is academic misconduct. Anything you did not write in your assignment will be treated as an academic misconduct case. If you are unsure where the line is between collaborating with AI and copying AI, we recommend the following heuristics: Heuristic 1: Never hit “Copy” within your conversation with an AI assistant. You can copy your own work into your own conversation, but do not copy anything from the conversation back into your assignment. Instead, use your interaction with the AI assistant as a learning experience, then let your assignment reflect your improved understanding. Heuristic 2: Do not have your assignment and the AI agent open at the same time. Similar to the above, use your conversation with the AI as a learning experience, then close the interaction down, open your assignment, and let your assignment reflect your revised knowledge. This heuristic includes avoiding using AI directly integrated into your composition environment: just as you should not let a classmate write content or code directly into your submission, so also you should avoid using tools that directly add content to your submission. Deviating from these heuristics does not automatically qualify as academic misconduct; however, following these heuristics essentially guarantees your collaboration will not cross the line into misconduct. 7 Appendix: Datapath Control Signals The microcontroller of the LC-3 has 52 bits of output signals to control program execution on the datapath. In this assignment, we will focus on 20 of them. There are four categories of signals we need to worry about: 1. Load Signals Each register has a load signal associated with it. When the load signal of a register is high (1), the value of the register will update to its input at the uptick of the clock. • LD.MAR The MAR (Memory Address Register) register holds the address of data to be read from, or written to, memory. This signal loads the MAR with the value from the bus, which should be the address of data to be read in a load signal (LD, LDR, LDI), or data to be written to in a store signal (ST, STR, STI). This address should be come from either the PC (For FETCH) or from the MARMUX (for all other memory access instructions). • LD.MDR The MDR (Memory Data Register) holds the data either read from or to be written to memory. The MDRMUX that selects between the bus (For store instructions – when data from a register is to be written to memory) and memory out (For load instructions – when data read from the memory is to be written to a register). When LD.MAR is high the MDR loads whichever the MDRMUX outputs. • LD.IR The IR (Instruction Register) holds the currently executing instruction (Contrast this to the PC, which holds the address of the next instruction to be executed, the IR holds the literal 16-bit assembled instruction which is fetched from memory at the address in the PC). The IR is only written to during the FETCH stage, so that is the only time LD.IR should be used. • LD.REG LD.REG is used for writing to the general purpose registers. When LD.REG is high (1), the DR register will load the value on the bus. In general, this signal should be active in the last state of any instruction that writes to a destination register. • LD.CC The CC (Condition Code) register is used for conditional (branching) statements. The CC itself is a three bit register, with one bit for each of (negative, zero, positive). Branching instructions (BR) use the value of the CC to determine if a branch should be taken (i.e. BRn means ’branch if cc == negative’). Because of this, the CC should always reflect the result of the previous instruction. The ’result’ of an instruction is generally whatever is written to a register in the last cycle. This means that LD.CC should be closely related to LD.REG as those loads are done in the same cycle (Because the result is already on the bus to load into the register file, we can also load it into the CC for free.) Note that not all instructions should set the condition codes. Generally, things like load instructions (LD, LDR, LDI) and all arithmetic instructions (ADD, AND, NOT) should set the CC, while things like LEA, branching, and store instructions don’t really have a ’result’ so they do not set the CC. LEA does not set the condition codes. • LD.PC The PC holds the address of the next instruction to be executed. Therefore, the value in the PC defines the control flow of the program. By default, the PC should be incremented by 1 during every FETCH stage. Branching and Jumping instructions work by setting the PC to some other value which causes the execution to jump to another point in the program. This signal should be high whenever the value of the PC should be changed, namely, in the FETCH stage and all branching and jumping instructions (There is a PCMUX which chooses the input of the PC to either increment the PC for fetch, read from the bus, or the ADDR calculation circuit – ADDR1MUX + ADDR2MUX). 2. Gate Signals All of the components on the datapath are connected by the bus. The bus is a single wire which any component can read from, and any component can assert to. However, we already know what happens when we try to assert two different signals to the same wire (Short circuits, fire, ensuing chaos and certain doom). Enter the Tri-State Buffer. The tri-state buffer works similarly to a transistor. It has an input, output, and enable bit, analogous to the source, drain and gate of the transistor. If the enable bit is high (1), then the output of the tri-state buffer will be whatever is connected to its input. If the enable bit is low (0), then the output will have no value, so it won’t ever cause a short circuit. So, we use tri-state buffers to connect each component to the datapath. That way, as long as only one tri-state buffer is enabled per clock cycle, we can move anything on the datapath and don’t have to worry about short circuits! However, this also means that we can only move one thing on the bus at a time. This is very important. It also means it is your responsibility to make sure that only one tri-state buffer on the bus is ever enabled in a given clock cycle. • GatePC This signal asserts the value of the PC to the bus. This should be used any time you want to load the PC into another register. Namely, this could be the MAR (for fetch), or R7 for saving the PC as a return address in branching and jumping instructions. • GateMDR This signal asserts the value of the MDR to the bus. In this case, the MDR should hold data read from memory, so it is being asserted to the bus to be saved to another register. Namely, this should be used to load the value of the MDR into the IR for FETCH, into a general purpose register for load instructions (LD, LDR, LDI), or back into the MAR for indirect memory access instructions (LDI, STI). • GateALU This signal asserts the output of the ALU to the bus. Remember, the ALU can output 8 different operations: A + B, A & B, ¬A, PASS A. Clearly, this signal should be active for the arithmetic instructions that use any operation that alters the value of A or B. The GateALU should also be active any time the value of a general purpose register should be written somewhere else (i.e. for storing instructions), which is when the PASS A option would be used (PASS A directly asserts the value of SR1 onto the bus). • GateMARMUX This signal asserts the output of the MARMUX onto the bus. Almost always, the value asserted onto the bus represents an address to be loaded into the MAR for loading and storing instructions (or directly into a destination register for LEA). 3. MUX Signals These signals have a range of possible values, and this range of values can differ based on the number of inputs to a given MUX (some have 2 inputs, others have 3 or 4). • PCMUX The PC has 3 options every time it is updated. During every FETCH, the PC is incremented by 1, and during branching and jumping instructions, the PC can be loaded either from the ADDR calculation circuit (ADDR1MUX + ADDR2MUX, for most branching/jumping), or read from the bus (rarely). • ADDR1MUX For memory address calculation (For data or instructions), all addresses take the form of a base register (which is usually the PC, but sometimes a general purpose register from the register file) which is added to the sign extension of some number of bits from the IR. The ADDR1MUX chooses what the base register should be, either the PC (for most instructions), or a general purpose base register (for LDR, STR, JSRR, and JMP). • ADDR2MUX For memory address calculation (For data or instructions), all addresses take the form of a base register (which is usually the PC, but sometimes a general purpose register from the register file) which is added to the sign extension of some number of bits from the IR. The ADDR2MUX chooses what that offset should be. Different instructions can allocate different numbers of bits for their immediate offset, with some having 6, 9, or 11. Each of these, IR[5:0], IR[8:0], IR[10:0], as well as a hardcoded 0 option, is sign extended to 16 bits to be added to the base register. ADDR2MUX chooses which of these is passed through. • MARMUX Most memory calculations will come through the MARMUX. The MARMUX has 2 inputs, one for the ADDR calculation circuit (ADDR1MUX + ADDR2MUX), and one to zero extend the lower eight bits of the instruction register (ZEXT(IR[7:0])). The later option is only used for TRAP instructions, which are outside the scope of this project, so you only need to worry about the former. • ALUK The ALUK selects which operation the ALU should output, from A + B, A & B, ¬A, PASS A. The first three are used for the arithmetic instruction (ADD, AND, NOT), and the PASS A operation directly outputs SR1 to the bus. This last option is used whenever the value of a general purpose register needs to be written somewhere else (Like store instructions.) 4. Memory Signals There are two signals that are used for memory access, MEM.EN and R.W. These control the behavior of the memory for read and write operations. • MEM.EN The MEM.EN signal will be high whenever the memory is accessed in any way, whether it is for reading or writing. • R.W R.W, or Read.Write is used to distinguish between memory operations that read from the memory and memory operations that write to the memory. Clearly, operations that are writing to memory (store instructions) should have R.W set to Write (1), while memory operations that read data already in memory should have R.W set to Read (0). 7.1 MUX Values We’ll take a second to clarify which selection codes correspond to which inputs in the 8 MUXes we’ve implemented on the LC-3 that you need to worry about. • MARMUX – Memory Address Register Mux 0. ZEXT (Zero-extend) input. 1. ADDR (address adder) input. • PCMUX – Program Counter Mux 00. PC+1 input. 01. ADDR (address adder) input. 10. BUS input. • DRMUX – Destination Register Mux (values given for you) 0. IR[11:9] input. 1. Constant 0b111 input. • SR1MUX – Source Register 1 Mux (values given for you) 0. IR[11:9] input. 1. IR[8:6] input. • SR2MUX – Source Register 2 Mux (determined by IR[5]) – don’t worry about this 0. SR2 input. 1. SEXT[4:0] (sign extend) input. • ADDR1MUX – Address Adder Input 1 MUX 0. PC input. 1. SR1 input. • ADDR2MUX – Address Adder Input 2 MUX 00. Constant 0x0000 input. 01. SEXT[5:0] input. 10. SEXT[8:0] input. 11. SEXT[10:0] input. • MDRMUX – MDR Input MUX – don’t worry about this Note: The selector bit for this mux should be the MIO.EN / MEM.EN signal 0. Bus. 1. Memory data output. • ALU – Bonus Entry (not exactly a MUX) 00. ADD (A + B) 01. AND (A & B) 10. NOT ( A) 11. PASS (just returns A)
Read the following instructions carefully ● For all the observations and explanations, create a single report. ● Attach screenshots in the report. ● Naming Convention: -Assignment1.zip Q1. [1 + 1] a) Learn to use the ifconfig command, and figure out the IP address of your network interface. Put a screenshot. b) Go to the webpage https://www.whatismyip.com and find out what IP is shown for your machine. Are they identical or different? Why? Q2. nslookup ([2+1] + [1+1]) a) Get an authoritative result for “google.in” using nslookup. Put a screenshot. Explain how you did it. b) Find out time to live for any website on the local DNS. Put a screenshot. Explain in words (with unit) that after how much time this entry would expire from the local DNS server. Q3. [13] a) Run the command, traceroute google.in. How many intermediate hosts do you see? What are the IP addresses? Compute the average latency to each intermediate host. Put a screenshot. [1+2+1] Note that some of the intermediate hosts might not be visible; their IP addresses will come as “***”, ignore those hosts for this assignment. b) Send 50 ping messages to google.in, Determine the average latency. Put a screenshot. [1] c) Add up the ping latency of all the intermediate hosts obtained in (a) and compare with (b). Are they matching, explain?[1+1] d) Take the maximum of ping latency amongst the intermediate hosts (in (a)) and compare with (b). Are they matching, explain? [1+1] f) Send 50 ping messages to stanford.edu, Determine the average latency. Put a screenshot. [1] g) Run the command, traceroute stanford.edu. Compare the number of hops between google.in and stanford.edu (between the traceroute result of google.in and stanford.edu). [1] h) Can you explain the reason for the latency difference between google.in and stanford.edu (see (b) & (f))? [1] Q4. [2+1] Make your ping command fail for 127.0.0.1 (with 100% packet loss). Explain how you do it. Put a screenshot that it failed. Q.5 [0.5*4 + 1] Use telnet to perform an HTTP get request on a webpage hosted at 192.168.24.12 Steps : 1. On your VM or main machine, run telnet 192.168.24.12 9900. 2. Once the connection is established, perform a GET request on /secret (Syntax : GET HTTP/1.1). 3. Now set the Host by typing Host: then press enter. This tells the server the host part of the URL 4. Now close the connection 5. If the request is successful, you will receive the response on the screen. Note the value of the X-secret header and take a screenshot of the entire response. Q6. [ 0.5*4 + 2 + 0.5*2 ] Use telnet to send an email to one of the other students using an SMTP server. Steps: 1. On your VM or main machine, run telnet 192.168.24.12 smtp 2. If everything goes well you will see 220 Welcome to CSE232 Mail Server. 3. Now identify your system by sending helo cse232.com 4. If everything goes well, you will see 250 xeon01-rs-iiitd.iiitd.edu.in on the screen. 5. Now write an email by specifying the sender, recipient, subject and the body and send it to one of your friends from Section A or Section B. a. Note: Both senders are receivers are identified by their roll numbers. So if you are 20018 and the recipient is 20019, then the sender address will be [email protected] and the recipient address will be [email protected]. 6. Note down the id of the message, take a screenshot and close the connection by typing quit 7. In order to confirm that your friend has received the mail, ask him to open his mailbox at 192.168.24.12/ where this key is unique to every student and is sent to them at their iiitd email.(DO NOT SHARE YOUR KEY WITH OTHERS). Important Note: 1. For each user, the mailbox size is 10MB and the per-message size limit is 10MB. 2. Your IPs are logged automatically by the system once you are logged into the SMTP server. 3. Any emails with attachments are automatically discarded by the server and therefore will not be sent to the recipient.
Statistical Machine Learning Q2. Implement Logistic Regression from scratch and perform binary classification using the following dataset: [Dataset for Q2]. Try both PCA+FDA and just FDA pre-processing steps before the classification and compare the results. Implement FDA yourself. Q5. How can we apply Logistic Regression in a multi-class classification problem? Extend your Logistic Regression’s implementation in Q2 to such a scenario and apply it on the IRIS dataset. Does it provide better results than the ones reported in Q4?
Instructions: 1. All your implementations should be from scratch, and preferably use a utils.py file to implement the algorithms as classes. 2. You can (preferably should) import them into a notebook and run them. 3. Make sure the notebooks are self-explanatory, easy to read, and all plots are well labeled. 4. You can use existing libraries to load the images. 5. You can use numpy library for array/matrix processing Q1. In this question, you’re going to use PCA to select the required subset of features from MNIST and then perform classification on it. a) Download the dataset from here: https://www.kaggle.com/datasets/scolianni/mnistasjpg b) Load the image dataset in your environment and convert it into a suitable format for creating an ML model. c) Implement PCA from scratch i.e. define your own PCA function or class for it. You are not allowed to use ANY pre-built implementation from any library. Note: Your implementation of PCA should be general, i.e., it can work for any dataset. d) Use kNN to train ML models on the training set of both original features and the transformed features (number of PCs = 5, 25, 125) obtained from PCA. Run the trained models on the test set and report the classification accuracies. e) Plot explained-variance (ratio of eigenvalue and sum of all eigenvalues) v/s PCs. How many PCs do you need to select to cover at least 80% of the variance? Do all this through programming. Q2.Implement k-means clustering and silhouette analysis algorithms to cluster the given data and find the optimal ‘k’ value. Also, implement fuzzy c means and report the J (objective function) value when c= optimal k.Assume m=2 and beta=0.3. Data: https://drive.google.com/file/d/1-0zx-cXze6ja777SN_NkMYVCzidU2lXw/view?usp =sharing Q3. https://drive.google.com/file/d/15-6l7_51OZ3wIw37d8a6SX2dfWxUQGl4/view?us p=sharing Implement the mean shift algorithm and perform image segmentation for the above image. Use a suitable bandwidth such that the vegetables look as separated as possible. Q4. Implement ICA from scratch to separate mixed signals – Generate a sinusoidal wave and a ramp wave. Plot them. – Use the following mixing matrix [[0.5, 1], [1, 0.5]] to mix them. Plot the mixed signals. – Now use ICA to recover the original signals and plot them. Q5.On the above data, use kNN to find HPI (continuous) and BHK (discrete) for a test instance having Age = 37 and LOAN = 142 as its feature values. Do it for k=1, 2, 3.
Objective In this Project, you have to setup an I2C Slave using the PSoC and sample 2 analog sensors using a Delta-Sigma ADC. For data visualization, you will use the Bridge Control Panel to plot the two signals. Connections Pin | Description | :———–:|————-| 2.1 | Built-in LED 2.5 | Analog Channel 0: Temperature sensor (*) 2.6 | Analog Channel 1: LDR (photoresistor) (**) 12.0 | I2C SCL 12.1 | I2C SDA (*) See the connection scheme below to hook up the photoresistor (Datasheet)(**) Please refer to the following image and to the datasheet of the component (TMP36GZ) to hook up the temperature sensorRequirements The Project will have to meet the following requirements: – Sample two analog sensors using a single 16-bit Delta-Sigma ADC (hint: you can use the Analog Mux for this) – Each sample (of each channel) has to be the average of 5 consecutive samples buffered opportunely – Set up an I2C Slave (EZI2C) to send the averaged data for the 2 channels to the Bridge Control Panel. Configure the EZI2C component as follows: 100 kbps data rate, 1 address (0x08) – The required transmission data rate is 50 Hz – Set up a Timer with an ISR at the appropriate frequency to guarantee the data transmission rate (50 Hz) of the averaged data (5 samples) – Control the operation of the device writing the value of the Control Register of the I2C slave (refer to the table below) – Set up the I2C Slave buffer of the EZI2C according to the following table (set the WHO AM I to 0xBC) – Turn on the built-in LED when the status is equal to 0b11, and turn it off otherwise (refer to the description of Control Register 1 for more info) I2C Slave Buffer Structure Address | Description | R/W | :———–:|—————|:—:| 0x00 | Control Reg 1 | R/W | 0x01 | Control Reg 2 | R/W | 0x02 | Who Am I | R | 0x03 | Ch0 Bit 15-8 | R | 0x04 | Ch0 Bit 07-0 | R | 0x05 | Ch1 Bit 15-8 | R | 0x06 | Ch1 Bit 07-0 | R | Control Register 0 Description (Address 0x00) Bit | Description | R/W | Default | :—–:|———————–|:—:|:——-:| 7 | –reserved | – | – | 6 | –reserved | – | – | 5 | Average samples bit 3 | R/W | 0 | 4 | Average samples bit 2 | R/W | 0 | 3 | Average samples bit 1 | R/W | 0 | 2 | Average samples bit 0 | R/W | 0 | 1 | Status bit 1 | R/W | 0 | 0 | Status bit 0 | R/W | 0 | The status (bits 0 and 1) can be either set to 0b00 (device stopped), 0b01 to sample the first channel (Ch0), 0b10 to sample the second channel (Ch1), and finally 0b11 to sample both channels. The register contains also the number of samples to be used for the computation of the average. Set the value of bits 2-5 of the Control Register 0 to meet the requirements of the project. Control Register 1 Description (Address 0x00) Bit | Description | R/W | Default | :—–:|———————–|:—:|:——-:| 7-0 | Timer 1 Period Value | R/W | 0 | The Control Register 1 contains the 8-bit period value of the Timer used to generate the ISR required to sample the analog channels using the Delta-Sigma ADC. Configure this register to meet the transmission data rate specified for this project. Setup and Assignment Delivery One student from the team forks this repository Each team member clones the forked repository by entering the following command in the terminal: git clone https://github.com/[your_username]/AY2021_II_HW_03.git – Open up the workspace in PSoC Creator – Activate the project with your group number – Work on your project – In your Group folder, save the Bridge Control Panel configuration files (GROUP_XX.ini and GROUP_XX.iic) inside BRIDGE_CONTROL_PANEL_CONFIG_FILES folder Evaluation
Objective In this assignment you are required to create a project using PSoC Creator, the CY8CKIT-059 KIT, a RGB LED and three 330 Ohm resistors. Context The LTEBS srl asks you to design a system able to control the color of the RGB LED through a serial port. The first time the system is powered after programming, the RGB LED should be on with a “black” color (RGB: 0,0,0). Then, with the protocol described here below, the color emitted with the RGB LED could be changed by sending commands through the serial port. The RGB LED has a common anode configuration, and must be connected as follows:The pins 2.5, 2.6, and 2.7 are the pins on the CY8CKIT-059 KIT that you must use to control the channels of the RGB LED. Connections The RED channel of the RGB Led must be connected to pin 2.7. The GREEN channel of the RGB Led must be connected to pin 2.6. The BLUE channel of the RGB Led must be connected to pin 2.5. The UART must use the pins 12.6 and 12.7 in order to communicate through the KitProg. Serial Port Communication 1. RGB Color Packet The commands to be sent through the serial port must be structured as follows: Byte (HEX) | Description | :———–:|————-| 0xA0 | Packet header (decimal value: 160) R | Red light (0x00-0xFF in Hex, 0-255 in decimal) G | Green light (0x00-0xFF in Hex, 0-255 in decimal) B | Blue light (0x00-0xFF in Hex, 0-255 in decimal) 0xC0 | Packet tail (decimal value: 192) The UART peripheral must be configured so as to trigger an interrupt when receiving a single byte (you can configure this kind of behaviour in the Advanced Tab of the UART component in PSoC Creator). A simple state machine will then allow you to perform a parsing of the received data packet:Depending on the received bytes, it is necessary to control the duty cycle of the PWM components that are connected to the RGB LED channels. Here are some working examples: Received Packet | Color | :————–:|——-| [0xA0, 0xFF, 0x00, 0x00, 0xC0] | RED [0xA0, 0x00, 0xFF, 0x00, 0xC0] | GREEN [0xA0, 0x7F, 0x00, 0x7F, 0xC0] | PURPLE If the system finds itself in one of the intermediate states of the state machine (i.e., exlcuding the IDLE and TAIL states), a 5 seconds timeout must be started in order to allow the system to go back to the idle state if no command is received in 5 seconds. 2. Timeout Configuration Byte (HEX) | Description | :———–:|————-| 0xA1 | Packet header (decimal value: 161) T | Number of seconds for timeout (1-20) 0xC0 | Packet tail (decimal value: 192) 3. Connection Command Upon receiving the character v, the system must send this string on the serial port: RGB LED Program $$$ This is required for the subsequent testing of the program through a simple GUI. Test You can test your program using a GUI designed in Kivy that we provide to you. You are required to download the zip file of the GUI, named RGB_Led_Control.zip from the course webpage. Unzip the file, and inside the folder rgbledcontrol, double click on rgbcontrol.exe. The GUI will automatically scan all the available serial ports, connect to the right one and will allow you to send a new color with the described packet structure.The GUI only work on Windows. For those of you who are using VirtualBox, please configure the display settings as follows:When using the GUI, please make sure to close all the active serial connections with the CY8CKIT-059 (e.g., CoolTerm, Bridge Control Panel, …) Setup and Assignment Delivery One student from the team forks this repository Each team member clones the forked repository by entering the following command in the terminal: git clone https://github.com/[your_username]/AY2021_II_HW_02.git – Open up the workspace in PSoC Creator – Evaluation Additional Resources: PSoC PWM Component Datasheet PSoC 5LP Interrupts PSoC 101 Video Tutorial
(100 pts) Category: socketsObjective: Implement a TCP server and TCP client application that can be used to receive and send messages from multiple clients. Description: Write a console program that takes as a command line argument the port number on which the TCP Server will listen for connection requests. A separate thread shall be created to handle the data received from each remote client and the remote clients can continue to send and receive data on the connections until either the server or the client closes the connection. The TCP server needs to maintain a list of all connected clients so that it can send out the appropriate messages. The TCP server needs to be able to receive data from clients without blocking the main application thread. The program needs to respond to user input while handling socket communications at the same time. You are free to use the SFML socket sample as a starting point.Server-60 points1) The program should continuously prompt the user for commands to execute like so:Please enter command: msg – prints to the console the last message received (if any) Last Message: last message receivedPlease enter command: clients – prints to the console a list of all connected clients (ip address and port number) like the following: Number of Clients: 2 IP Address: localhost | Port: 51717 IP Address: localhost | Port: 51718Please enter command: exit – closes all sockets and terminates the program2) The data being sent back and forth will use the following packet structure:struct tcpMessage { unsigned char nVersion; unsigned char nType; unsigned short nMsgLen; char chMsg[1000]; };The TCP server needs to have the following functionality for received messages: • If nVersion is not equal to 102 then the message is ignored.• If nType == 77 then the message should be sent to all other connected clients exactly as received (but not the client that sent the message). • If nType == 201 then the message is reversed and sent back to only the client that sent the message.Client-40 pointsIn order to test your server, write a console program that takes as a command line argument the IP Address and port number of the server as shown below:./a.out localhost 51717The program should prompt the user for inputs and display any messages received.Here are example user inputs:Please enter command: v # the user enters a “v”, a space, and then a version number. This version number is now used in all new messages. Please enter command: t # message string the user enters a “t”, a space, and then a type number, followed by the message. Be sure you are able to handle the spaces in the message string. Please enter command: q the user enters a “q” causes the socket to be closed and the program to terminate.Any messages received from the server should be displayed as followed:Received Msg Type: #; Msg: message received Turn-In Instructions Zip up your server file(s) into Lab5Server.zip and your client files into Lab5Client.zip upload these zip files on the assignment section of Canvas.Grading Rubric:AUTOMATIC GRADING POINT DEDUCTIONS PER PROBLEM: Element Percentage Deduction Details Does Not Compile 40% Code does not compile on PACE-ICE! Does Not Match Output Up to 90% The code compiles but does not produce correct outputs. Clear Self-Documenting Coding Styles Up to 25% This can include incorrect indentation, using unclear variable names, unclear/missing comments, or compiling with warnings. (See Appendix A)LATE POLICY Element Percentage Deduction DetailsAppendix A: Coding Standards Indentation: When using if/for/while statements, make sure you indent 4 spaces for the content inside those. Also make sure that you use spaces to make the code more readable. For example: for (int i; i < 10; i++) { j = j + i; }If you have nested statements, you should use multiple indentions. Each { should be on its own line (like the for loop) If you have else or else if statements after your if statement, they should be on their own line. for (int i; i < 10; i++) { if (i < 5) { counter++; k -= i; } else { k +=1; } j += i; }Camel Case: This naming convention has the first letter of the variable be lower case, and the first letter in each new word be capitalized (e.g. firstSecondThird). This applies for functions and member functions as well! The main exception to this is class names, where the first letter should also be capitalized. Variable and Function Names: Your variable and function names should be clear about what that variable or function represents. Do not use one letter variables, but use abbreviations when it is appropriate (for example: “imag” instead of “imaginary”). The more descriptive your variable and function names are, the more readable your code will be. This is the idea behind self-documenting code.File Headers: Every file should have the following header at the top /* Author: your name Class: ECE4122 or ECE6122 (section)Description:What is the purpose of this file?*/Code Comments:1. Every function must have a comment section describing the purpose of the function, the input and output parameters, the return value (if any). 2. Every class must have a comment section to describe the purpose of the class. 3. Comments need to be placed inside of functions/loops to assist in the understanding of the flow of the code.
Category: CUDAObjective: Implement a CUDA program to simulate a 2D random walk. A random walk is a mathematical process that describes a path consisting of a sequence of random steps. In this assignment, you will simulate a large number of walkers taking steps either north, south, east, or west on a grid, and calculate the average distance they travel from the origin. Description: Create a C++ application using CUDA that takes as program input arguments the Number of Walkers, and the number of steps each walker needs to take on a 2D integer grid. Use command line flags to distinguish Number Walkers (-W) and (-I) for number of steps. All the walkers start at the origin (0, 0). Your application should implement three functions that internally use different memory models to perform the calculations. 1. (30 pts) cudaMalloc 2. (30 pts) cudaMallocHost 3. (30 pts) cudaMallocManaged Your application should output to the console screen the total time each function took to perform the calculations and the average distance of the walkers from the origin and then exit. (10 pts) Minimizing calculation times for all three functions.Sample Program Flow: >Lab4 -W 1000 -I 10000 > Normal CUDA memory Allocation: >(4 spaces) Time to calculate(microsec): ??? >(4 spaces) Average distance from origin: ???.??? > Pinned CUDA memory Allocation: >(4 spaces) Time to calculate(microsec): ??? >(4 spaces) Average distance from origin: ???.??? > Managed CUDA memory Allocation: >(4 spaces) Time to calculate(microsec): ??? >(4 spaces) Average distance from origin: ???.??? >ByeTurn-In InstructionsZip up your file(s) into Lab4.zip and upload this zip file on the assignment section of Canvas.Grading Rubric:AUTOMATIC GRADING POINT DEDUCTIONS PER PROBLEM: Element Percentage Deduction Details Does Not Compile 40% Code does not compile on PACE-ICE! Does Not Match Output Up to 90% The code compiles but does not produce correct outputs. Clear Self-Documenting Coding Styles Up to 25% This can include incorrect indentation, using unclear variable names, unclear/missing comments, or compiling with warnings. (See Appendix A)LATE POLICY Element Percentage Deduction DetailsAppendix A: Coding Standards Indentation: When using if/for/while statements, make sure you indent 4 spaces for the content inside those. Also make sure that you use spaces to make the code more readable. For example: for (int i; i < 10; i++) { j = j + i; }If you have nested statements, you should use multiple indentions. Each { should be on its own line (like the for loop) If you have else or else if statements after your if statement, they should be on their own line. for (int i; i < 10; i++) { if (i < 5) { counter++; k -= i; } else { k +=1; } j += i; }Camel Case: This naming convention has the first letter of the variable be lower case, and the first letter in each new word be capitalized (e.g. firstSecondThird). This applies for functions and member functions as well! The main exception to this is class names, where the first letter should also be capitalized. Variable and Function Names: Your variable and function names should be clear about what that variable or function represents. Do not use one letter variables, but use abbreviations when it is appropriate (for example: “imag” instead of “imaginary”). The more descriptive your variable and function names are, the more readable your code will be. This is the idea behind self-documenting code.File Headers: Every file should have the following header at the top /* Author: your name Class: ECE4122 or ECE6122 (section)Description:What is the purpose of this file?*/Code Comments:1. Every function must have a comment section describing the purpose of the function, the input and output parameters, the return value (if any). 2. Every class must have a comment section to describe the purpose of the class. 3. Comments need to be placed inside of functions/loops to assist in the understanding of the flow of the code.
Category: 3D GraphicsObjective: To create a dynamic 3D graphics application using lighting, shading, model transformations, and keyboard inputs. Description: Using the code from tutorial09_Assimp create an application that loads in the suzanne.obj file and creates 4 instances of the head object. Place (rotate) each of the heads so that it faces away from the origin along the +x-axis, -x-axis, +y-axis, and -yaxis. Translate the heads so that the ears of each head just barely touch and the chin of all the heads just touches the z = 0 plane. Place a green rectangle on the z = 0 plane that is sized to just extend past the front of all the heads. Modify the keyboard inputs so that (5 points each) 1) ‘w’ key moves the camera radially closer to the origin. 2) ‘s’ key moves the camera radially farther from the origin. 3) ‘a’ key rotates the camera to the left maintaining the radial distance from the origin. 4) ‘d’ key rotates to camera to the right maintaining the radial distance from the origin. 5) The up arrow key radially rotates the camera up. 6) The down arrow radially rotates the camera down. 7) The ‘L’ key toggles the specular and diffuse components of the light on and off but leaves the ambient component unchanged. 8) Pressing the escape key closes the window and exits the program Points grading: • 30 Points – loading obj file and displaying the fours heads and the green z = 0 rectangle • 30 Points – rotating and placing the heads in the correct location and orientation • 40 Points – keyboard control • 5 pts extra credit – place a texture (of your choice) on the z=0 plane rectangle. Make sure to include the bmp file in your submission. • 5 pts extra credit make a short, narrated video of your program in action. (include it in the zip file)Turn-In InstructionsMake your required changes to the file tutorial09_several_objects.cpp and controls.cpp.Grading Rubric:AUTOMATIC GRADING POINT DEDUCTIONS PER PROBLEM: Element Percentage Deduction Details Does Not Compile 40% Code does not compile on PACE-ICE! Does Not Match Output Up to 90% The code compiles but does not produce correct outputs. Clear Self-Documenting Coding Styles Up to 25% This can include incorrect indentation, using unclear variable names, unclear/missing comments, or compiling with warnings. (See Appendix A)LATE POLICY Element Percentage Deduction DetailsAppendix A: Coding Standards Indentation: When using if/for/while statements, make sure you indent 4 spaces for the content inside those. Also make sure that you use spaces to make the code more readable. For example: for (int i; i < 10; i++) { j = j + i; }If you have nested statements, you should use multiple indentions. Each { should be on its own line (like the for loop) If you have else or else if statements after your if statement, they should be on their own line. for (int i; i < 10; i++) { if (i < 5) { counter++; k -= i; } else { k +=1; } j += i; }Camel Case: This naming convention has the first letter of the variable be lower case, and the first letter in each new word be capitalized (e.g. firstSecondThird). This applies for functions and member functions as well! The main exception to this is class names, where the first letter should also be capitalized. Variable and Function Names: Your variable and function names should be clear about what that variable or function represents. Do not use one letter variables, but use abbreviations when it is appropriate (for example: “imag” instead of “imaginary”). The more descriptive your variable and function names are, the more readable your code will be. This is the idea behind self-documenting code.File Headers: Every file should have the following header at the top /* Author: your name Class: ECE4122 or ECE6122 (section)Description:What is the purpose of this file?*/Code Comments:1. Every function must have a comment section describing the purpose of the function, the input and output parameters, the return value (if any). 2. Every class must have a comment section to describe the purpose of the class. 3. Comments need to be placed inside of functions/loops to assist in the understanding of the flow of the code.
