Cellphone camera S c r e e n Camera obscura Pinhole(a) Camera obscura (b) Example design Figure 1: You will design a camera obscura with your cellphone. In this assignment, you will design a camera obscura with your cellphone camera. The camera obscura is a dark chamber (box) with a small pinhole where light is mapped to the other side of the chamber (screen). This creates an upside-down image.1. Build a lightproof dark chamber: the chamber will be only illuminated by the light from the pinhole. Play with different size of chambers if possible. Cover the screen with a white paper and the rest of insider surfaces with black papers. Be creative!2. Make a pinhole on the other side of the screen. Start with a small hole (diameterISO 800).5. Set the camera exposure time (>8 sec).6. Make an additional hole where your cellphone camera can look inside. Locate your cellphone camera close to the pinhole without occluding pinhole. Make sure this hole is completely light sealed.7. Take a picture and adjust the pinhole size and camera settings to make better sharp image.For an Android phone, you can control the exposure time and sensitivity easily. Camera FV-5 Lite is an app to grab a long exposure image. For iOS, the exposure control is highly limited. There are apps that simulate the long exposure effect by taking many images. This creates a noisy image. You may borrow an Android phone or old digital camera. You can also refer to the website: https://graphics.cs.cmu.edu/courses/ 15-463/2015_fall/hw/proj5-camera/. 2Note: Lighting is extremely important. Given Minnesota’s weather, it is difficult to find a nice cloudless day. Plan outside data capture on sunny day ahead.(1) Describe your design (dimension) with images and your camera setting. Share your awesome photos. 3 Where am I? (a) Lateral view (b) Camera obscura image (c) Original image Figure 2: You will your camera obscura to estimate depth. Using this camera obscura, you will estimate the depth of a 3D object (from pinhole). You will take a picture containing your two friends (A and B) whom you know their height in meter where they will stand at different distance from the camera as show in Figure 2(a).(1) Given the height of A in meter (HA) and pixel (hA), derive and compute the distance from A to the pinhole. (2) Given the height of B in meter (HB) and pixel (hB), derive and compute the distance from B to the pinhole. Note: You can measure pixel distance using an image viewer software, e.g., irfanview, or MATLAB.(a) Geometry (b) Image cropping Figure 3: You will your camera obscura to estimate depth. 4 Dolly ZoomYou will simulate the Dolly zoom effect using your camera obscura. You will take at least two pictures with different camera locations, e.g., taking 5 step back, ∆d, as shown in Figure 3(a). A and B will appear smaller than the first image as ∆d > 0. You can apply the zoom-in effect by scaling and cropping the image such that A appears the same as shown in Figure 3(b). You may find a reference from here: https://www-users.cs.umn.edu/~hspark/CSci5980/Lec1_Supp_DollyZoom.pdf.Write-up: (1) Predict the height of B in the second image given hB in the first image. Reason about the prediction. Hint: You may need to compute ∆d with the information in the second image.(2) Confirm the prediction by measuring the height of B in the second image. Useful MATLAB functions: (a) Load image: im = imread(filename). (b) Save image: imwrite(im, filename). (c) Resize image: im = imresize(im, scale). (d) Display image: imshow(im) or imshow(filename). (e) Measure the distance in image: display the image in a figure, select the data cursor icon in the figure toolbar, and click on the image to get the coordinates of certain pixels. Calculate the distance with the pixel coordinates.Orginal image Undistorted image k > 0 k < 0 Figure 1: Lens distortion recification. Using your cellphone camera, you will estimate intrinsic camera parameters (focal length, principal points, and lens distortion parameter).(1) Derive K matrix using your camera specification. (2) Calibrate lens distortion using the radial distortion model (single parameter, k1). Show the original image, undistorted image, and two image examples of wrong k1 as shown in Figure 1. 23 Projective Line(a) Image (b) UMN logo Figure 2: (a) You will use your cellphone camera image to compute camera poses with respect to the ground plane and measure the height of your friend given the height of an object. (b) You will paste the UMN logo to the ground plane. Take a picture of your friend with many 3D objects such as street lamps and chair where two orthogonal directions on the ground plane are visible as shown in Figure 2(a). Apply lens undistortion to make the straight lines straight.(1) Derive and compute two vanishing points and a vanishing line, and visualize them on your image similar to Figure 2(a). (2) Compute camera rotation matrix, R, and visualize 3D camera axes with respect to the ground plane axes using MATLAB plot3 function. Give a geometric interpretation of the computed rotation matrix. (3) Measure the heights of at least 3D objects given your friend’s height using the cross ratio. Verify the height measurements. (4) Project UMN logo onto the ground plane or any planar surface. You are also free to choose different logo or image. 34 Panoramic Image(a) Input images h , x h y z p p p φ = p Camera center Cylindrical surface φ (b) Geometry h φ (c) Cylindrical coordinate (d) Panoramic image Figure 3: Given a collection of input images, you will create a panoramic images by projecting onto a cylindrical surface. 4You will create a panoramic image from multiple images (at least 8 images) taken by your cellphone camera using a cylindrical projection as shown in Figure 3(a). The panoramic image will be created in (φ, h) where φ and h are angle and height coordinate of the cylindrical surface, respectively, as shown in Figure 3(c). Note that the radius and height of the cylinder are set to the focal length and height of the image, respectively.(1) Express the direction vector pφ,h =px py pz T using φ and h as shown in Figure 3(c) and 3(b).(2) Given the first and second images, compute homography, 2H1 using 4 correspondences and relative rotation from first to second, 2R1 where the first image rotation is the identity matrix I3. λu2 = Hu1 µu2 = K2R1pφ,h (1) where u1 ↔ u2 is the corresponding points in the first and second image.(3) For all images, compute the rotation matrix, iR1, and visualize the camera Z axis in 3D using MATLAB plot3 function. Hint: iR1 =i Ri−1 i−1Ri−2 · · · 2 R1.(4) Create a panoramic image by copying RGB value of original image coordinate (u, v) to the cylindrical coordinate (φ, h) as shown in Figure 3(d). You may blend overlapping pixels by taking average.1. Rotate your camera about fixed rotation center (no translation). Translation of your camera produces mis-alignment. 2. Choose 4 correspondences very carefully. 3. Lens distortion may introduce mis-alignment. 4. Objects at far distance often work better.(a) Vanishing points (b) Checkerboard pattern Figure 1: (a) You will use the vanishing points in a single image to calibrate your cameras. (b) You will use multiple images of checkerboard patterns to calibrate your camera.You will calibrate your camera (focal length, principal points, and lens distortion parameters).(1) (Single Image Calibration) Take a single image where you can estimate three vanishing points vX inf, vY inf, and vZ inf as shown in Figure 3(c). Compute f, px, and py using the vanishing points.(2) (Multiple Image Calibration) Print out the checkerboard pattern as shown in Figure 1(b) (https://www-users.cs.umn.edu/~hspark/CSci5980/code/pattern.pdf). Derive f, px, and py based on homographies from multiple images (at least 5 images).Compute the intrinsic parameters by solving the least squares system.(3) (MATLAB Toolbox Calibration) Use the existing MATLAB Calibration Toolbox (https://www.vision.caltech.edu/bouguetj/calib_doc/) to compute the intrinsic parameters (at least 20 images from different views). Verify the estimate with your solutions in (1) and (2).3 Rotation Interpolation(a) Left image (b) Right image (c) Interpolated View Figure 2: Using two images of pure rotation (a and b), you will generate interpolated view by sampling rotation (c) In HW 2, we generate a panoramic image from multiple images. In this problem, you will use two images of pure rotation (Figure 2(a) and 2(b)) to generate many views by interpolating between rotations as shown in Figure 2(c).(1) Compute the pure rotation, RR L from the homography between two images, RHL. (2) Interpolate between two rotations, { iRL} N i=1, from I3 (Left image) to R (Right image) where N > 20 is the number of interpolated rotations using SLERP. (3) Generate interpolated images similar to Figure 2(c). • Given iRL, compute homography from Left image to the interpolated image, iHL and warp it, im1 = ImageWarping(imageLeft, iHL). • Compute homography from Right image to the interpolated image, i.e., iHR =i HR LH−1 L . Warp image, im2 = ImageWarping(imageRight, iHR). • Composite two images based on distance, imInterpolated = w*im1+(1-w)*im2 where w is weight, inversely proportional to the distance. 34 Tour into Your Picture (a) Source image (b) Rectified image u11 u12 u21 u22 v11 v12 v21 v22 p (c) Vanishing point (d) 3D reconstruction (e) Tour into picture Figure 3: (a) Given a single image taken by a cellphone, you will navigate into the image. (b) You rectify the image such that the Y axis of the camera aligns with the surface normal of the ground plane. (c) You define the five principal planes using vanishing points. (d) A 3D box can be texture mapped.Take an photo with your camera of a scene where you can observe the Z vanishing point. You will virtually tour into your photo that creates 3D sensation.(1) Rectification: Rectify your image such that the surface normal of the ground plane is aligned with the Y axis of your camera using the homography between ground plane and the camera. Derive and compute the homography for the rectification. Visualize 4rectified image similar to Figure 3(b). (2) Z vanishing point: Given the rectified image, derive and compute the Z vanishing point, p (Figure 3(c)) using the four edges from the ground and ceiling planes using linear least squares (the intersection of four lines), i.e., Ax = b.1. Define the four corners (u11, u12, u21, u22) of the purple plane (Figure 3(c)) in the image.2. Define the depth of the four corner, e.g., d=1 and compute the 3D locations of the corners, U = dK−1u.3. Express the 3D locations of frontal plane, V11, V12, V21, and V22 using d, p, K, u11, u12, u21, u22, v11, v12, v21, v22.4. Express a 3D point, X, in the 3D plane (U11, U12, U21, and U22), using two parameters, e.g., X = a1µ1 + a2µ2 + a3. Apply this for the rest four planes.1. Derive and compute the homography per plane to the rectified image, i.e., sHplane1, sHplane2, sHplane3, sHplane4, sHplane5. Hint: λu = KX = Ka1 a2 a3 µ1 µ2 1 = sHplane µ1 µ2 1 .2. Derive and compute the homography per plane to a target image of pure rotation about Y axis of the camera with 20 degree (tHplane1, tHplane2, tHplane3, tHplane4, tHplane5). Derive and compute the homography from the rectified image to the target image. Hint: tHs =t Hplane sH−1 plane.3. Derive and compute the homography per plane to a target image of pure translation along Z axis of the camera with 0.2d. Derive and compute the homography from the rectified image to the target image. (4) Generate camera trajectory by interpolating rotation and translation (at least 5 discrete rotation and translation) and generate a video of navigation. 5One of key skills to learn in computer vision is the ability to use other open source code, which allow you not to re-invent the wheel. We will use VLFeat by A. Vedaldi and B. Fulkerson (2008) for SIFT extraction given your images. Install VLFeat from following: https://www.vlfeat.org/install-matlab.html Run vl demo sift basic to double check the installation is completed. (NOTE) You will use this library only for SIFT feature extraction and its visualization. All following visualizations and algorithms must be done by your code.Figure 1: Given your two cellphone images (left and right), you will extract SIFT descriptors and visualize them using VLFeat. You will extract David Lowe’s SIFT (Scale Invariant Feature Transform) features from your cellphone images as shown in Figure 1. First, take a pair of pictures with your calibrated camera (intrinsic parameter, K, and radial distortion parameter, k, are precalibrated.) as follow:1. Take the first picture and another one after moving one step right (1m).2. Common 3D objects across different depths, e,g., buildings, ground plane, and tree, appear in both images.3. Two images have to be similar enough so that the appearance based image matching can be applied, i.e., SIFT feature does not break, while maintaining the baseline between cameras (at least 1 m), i.e., similar camera orientation and sufficient translation.4. Avoid a 3D scene dominated by one planar surface, e.g., looking at ground plane.(SIFT visualization) Use VLFeat to visualize SIFT features with scale and orientation as shown in Figure 1. You may want to plot up to 500 feature points. You may want to follow the following tutorial: https://www.vlfeat.org/overview/sift.html(a) Matching from I1 to I2 (b) Matching from I2 to I1 (c) Matching from I1 to I2 after ratio test (d) Matching from I2 to I1 after ratio test (e) Bidirectional matching between I1 and I2 Figure 2: You will match points between I1 and I2 using SIFT features. (NOTE) From this point, you cannot use any function provided by VLFeat. The SIFT is composed of scale, orientation, and 128 dimensional local feature descriptor (integer), f ∈ Z128. You will use the SIFT features to match between two images, I1 and I2.(1) (Nearest neighbor search) Let two sets of features be {f1, · · · ,fN1 } from I1 and {g1, · · · , gN2 } from I2 where N1 and N2 are the number of features in image 1 and 2, respectively. Compute nearest neighbor per feature and visualize ({f1, · · · ,fN1 } → {g1, · · · , gN2 } and {g1, · · · , gN2 } → {f1, · · · ,fN1 }) as shown in Figure 2(a) and Figure 2(b). Note that the distance between two features is defined as d = kf − gk. You may use knnsearch function in MATLAB.(2) (Ratio test) Filter out matches using the ratio test, i.e., keep the match if dij1 /dij2 n then 7: n ← nr 8: F = Fr 9: end if 10: end for (2) (Epipole and epipolar line) Using the fundamental matrix, visualize epipole and epipolar lines. 7-0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 1.2 0 0.8 0.6 0.4 0.2 0 0.5 0.2 0 0 -0.2 -0.5 -0.4 -1 -0.6 -1.5 0.5 0 -0.5 0 0 0.2 -0.2 0.4 0 0.2 0.4 0.6 0.8 1 -1 -0.5 0 0.5 0.2 0 -0.2 -0.4 -1.5 -0.6 0 Figure 4: Four configurations of camera pose from a fundamental matrix.(3) (Camera pose estimation) Compute 4 configurations of relative camera poses: [R1 C1 R2 C2 R3 C3 R4 C4] = CameraPose(F, K) Input: F is the fundamental matrix and K is the intrinsic parameter. Output: R1 C1 · · · R4 C4 are rotation and camera center (represented in the world coordinate system).(4) Visualize the 4 configuration in 3D as shown in Figure 4. 8Given four configurations of relative camera pose, you will find the best camera pose by verifying through 3D point triangulation.(1) (Linear triangulation) Write a code that computes the 3D point given the correspondence, u ↔ v, and two camera projection matrices: [X] = LinearTriangulation(P1,u,P2,v) Input: P1, P2 ∈ R3×4 are two camera projection matrices, and u ↔ v ∈ R2 are their 2D correspondence. Output: X ∈ R3 is the triangulated 3D point.Hint: Use the triangulation method by linear solve, i.e.,(2) (Cheirality) Write a code that computes the number of 3D points in front of two cameras. The condition of a 3D point being in front of camera is called cheirality: idx = CheckCheirality(Y,C1,R1,C2,R2) Input: Y is a n × 3 matrix that includes n 3D points, and C1,R1/C2,R2 are the first and second camera poses (camera center and rotation). Output: idx is a set of indices of 3D points that satisfy cheirality. Hint: the point must satisfy r3(X − C) > 0 where r3 is the 3rd row of the rotation matrix (z-axis of the camera), C is the camera position and X is the 3D point. 9 (3) (Camera pose disambiguation) Based on cheirality, find the correct camera pose. Visualize 3D camera pose and 3D points together as shown in Figure 5. Hint: Use plot3 and DisplayCamera.m to visualize them. 0 50 100 0 -20 -50 -40 -60 -80 0 0 -100 20 -50 40 60 0 80 50 40 20 40 60 80 0 -20 0 20 -20 -80 -60 -40 0 -40 -20 0 20 0-80 -60 -40 -20 0 20 40 60 (a) nValid = 10 (b) nValid = 488 (c) nValid = 0 (d) nValid = 0 Figure 5: You will visualize four camera pose configurations with point cloud.(4) (Reprojection) Project 3D points to each camera and visualize reprojection, ub and measurement, u onto the image as shown in Figure 6, i.e., λ ub 1 = KR I −C X 1 where X is the reconstructed point. Reprojection Measurement Reprojection Measurement Figure 6: Visualization of measurements and reprojection.Figure 1: You will capture your cellphone images to reconstruct camera pose and 3D points.In this assignment, you will use your cellphone images (more than 5) to reconstruct 3D camera poses and points with full bundle adjustment. Make sure you have enough baseline (translation) between images for well conditioned fundamental matrix while retaining enough number of correspondences between image. Avoid a scene dominated by a planar surface, i.e., the images need to contain many 3D objects as shown in Figure 1.You will write a full pipeline of the structure from motion algorithm including matching, camera pose estimation using fundamental matrix, PnP, triangulation, and bundle adjustment. A nonlinear optimization is always followed by the initial estimate by linear least squares solution. The pipeline is described in Algorithm 1.Algorithm 1 Structure from Motion 1: [Mx, My] = GetMatches(I1, · · · , IN ) 2: Normalize coordinate in Mx and My, i.e., x = K−1x. 3: Select two images Ii1 and Ii2 for the initial pair reconstruction. 4: [R, C, X] = CameraPoseEstimation([Mx(:,i1) My(:,i1)], [Mx(:,i2) My(:,i2)]) 5: P = {P1,P2} where Pi1 =I3 0, Pi2 = RI3 −C6: R = {i1, i2} 7: while |R| < N do 8: i = GetBestFrame(Mx, My, R); 9: [Ri , Ci ] = PnP RANSAC([Mx(:,i) My(:,i)], X) 10: [Ri , Ci ] = PnP Nonlinear(Ri Ci , [Mx(:,i) My(:,i)], X) 11: Pi = RiI3 −Ci12: for f = 1 : |R| do 13: U = FindUnreconstructedPoints(X, Rf , i, Mx, My) 14: for j = 1 : |U| do 15: u = [Mx(Uj , i), My(Uj , i)] and v = [Mx(Uj , Rf ), My(Uj , Rf )] 16: x = LinearTriangulation(u, Pi , v, PRf ) 17: x = NonlinearTriangulation(X, u, Ri , Ci , v, RRf , CRf ) 18: X = X ∪ x 19: end for 20: end for 21: P = P ∪ Pi and R = R ∪ i. 22: [P, X] = BundleAdjustment(P, X, R, Mx, My) 23: end whileGiven a set of images, I1, · · · , IN , you will find matches across all images where N is the number of images similar to HW #4. Pick a reference image, Iref , and match with other images using SIFT features from VLFeat, i.e., Iref ↔ I1, · · · , Iref ↔ IN (no need to match Iref ↔ Iref ).Your matches are outlier free, i.e., bidirectional knn match → ratio test → inliers from the fundamental matrix based RANSAC. Based on the matches, you will build a measurement matrix, Mx and My: [Mx, My] = GetMatches(I1, · · · , IN ) Mx: F×N matrix storing x coordinate of correspondences My: F×N matrix storing y coordinate of correspondences The f th feature point in image Ii corresponds to a point in image Ij . The x and y coordinates of the correspondence is stored at (f, i) and (f, j) elements in Mx and My, respectively. If (f, i) does not correspond to any point in image Ik, you set -1 to indicate no match as shown in Figure 2.Important: For better numerical stability, you can transform the measurements to the normalized coordinate by multiplying K−1 , i.e., x = K−1x where x is 2D measured points in homogeneous coordinate. You can run structure from motion in the normalized coordinate by factoring out K. When visualizing projection in the image, the coordinate needs to be transformed back to original coordinate by multiplying K. F N f ,i x f , j f x i j Mx N f ,i y f , j f y i j My ( xf ,i , y f ,i) ↔ ( xf , j , y f , j) ↔ ( xf ,k , y f ,k ) −1 k −1 k Figure 2: The f th feature point in image Ii corresponds to a point in image Ij . The x and y coordinates of the correspondence is stored at (f, i) and (f, j) elements in Mx and My, respectively. If (f, i) does not correspond to any point in image Ik, you set -1 to indicate no match. 4You will write a camera pose estimation code that takes correspondences between two images, Ii1 and Ii2 where i1 and i2 are the indices of the initial images to reconstruct selected manually. [R, C, X] = CameraPoseEstimation(u1, u2) R and C: the relative transformation of the i2 image u1 and u2: 2D-2D correspondences As studied in HW #4, you will compute: 1. Fundamental matrix via RANSAC on correspondences, Mx(:,i1), My(:,i2) 2. Essential matrix from the fundamental matrix 3. Four configurations of camera poses given the essential matrix 4. Disambiguation via chierality (using 3D point linear triangulation): X = LinearTriangulation(u, Pi , v, Pj ) Write-up: (a) Inlier matches Top view Oblique view (b) 3D camera pose Figure 3: Camera pose estimation. (1) Visualize inlier matches as shown in Figure 3(a). (2) Visualize camera pose and 3D reconstructed points in 3D as shown in Figure 3(b). 5You will write a nonlinear triangulation code. Given the linear estimate for the point triangulation, X, you will refine the 3D point X =X Y Z T to minimize geometric error (reprojection error) via iterative nonlinear least squares estimation, ∆X =∂f(X) ∂X T ∂f(X) ∂X !−1 ∂f(X) ∂X T (b − f(X)). (1) Write-up: (1) Derive the point Jacobian, i.e., ∂f(X)j ∂X and write the following code. df dX = JacobianX(K, R, C, X)(2) Write a code to refine the 3D point by minimizing the reprojection error and visualize reprojection error reduction similar to Figure 5. X = NonlinearTriangulation(X, u1, R1, C1, u2, R2, C2) Algorithm 2 Nonlinear Point Refinement 1: b =u T 1 u T 2 T 2: for j = 1 : nIters do 3: Build point Jacobian, ∂f(X)j ∂X . 4: Compute f(X). 5: ∆X = ∂f(X) ∂X T ∂f(X) ∂X + λI −1 ∂f(X) ∂X T (b − f(X)) 6: X = X + ∆X 7: end forYou will register an additional image, Ij using 2D-3D correspondences. Write-up: (1) (3D-2D correspondences) Given 3D triangulated points, find 2D-3D matches, X ↔ u. (2) (Perspective-n-Point algorithm) Write a code that computes 3D camera pose from 3D-2D correspondences: [R, C] = LinearPnP(u, X) X: n × 3 matrix containing n 3D reconstructed points u: n × 2 matrix containing n 2D points in the additional image I3 R and C: rotation and translation for the additional image. Hint: After the linear solve, rectify the rotation matrix such that det(R) = 1 and scale C according to the rectification.(3) (RANSAC PnP) Write a RANSAC algorithm for the camera pose registration (PnP) given n matches using the following pseudo code: Algorithm 3 PnP RANSAC 1: nInliers ← 0 2: for i = 1 : M do 3: Choose 6 correspondences, Xr and ur, randomly from X and u. 4: [Rr, tr] = LinearPnP(ur, Xr) 5: Compute the number of inliers, nr, with respect to Rr, tr. 6: if nr > nInliers then 7: nInliers ← nr 8: R = Rr and t = tr 9: end if 10: end for Visualize 3D registered pose as shown in Figure 4. -40 -20 0 20 (a) Front view 0 10 20 30 40 50 60 0 -80 -60 -40 -20 0 20 40 (b) Top view Figure 4: Additional image registration. (4) (Reprojection) Visualize measurement and reprojection to verify the solution.Given the initial estimate Ri and ti , you will refine the camera pose to minimize geometric error (reprojection error) via iterative nonlinear least squares estimation, ∆p =∂f(p) ∂p T ∂f(p) ∂p !−1 ∂f(p) ∂p T (b − f(p)), f(p) = u1/w1 v1/w1 . . . un/wn vn/wn , u v w = RiI3 −C X 1 , b = x1 y1 . . . xn yn (2) where p =CT q T T . C ∈ R3 is the camera optical center and q ∈ S 3 is the quaternion representation of the camera rotation. It is possible to minimize the overshooting by adding damping, λ as follows: ∆p =∂f(p) ∂p T ∂f(p) ∂p + λI !−1 ∂f(p) ∂p T (b − f(p)), (3) where λ is the damping parameter. You can try λ ∈ [0, 10].Note that the conversion between quaternion and rotation matrix is given as follows: R = 1 − 2q 2 z − 2q 2 y −2qzqw + 2qyqx 2qyqw + 2qzqx 2qxqy + 2qwqz 1 − 2q 2 z − 2q 2 x 2qzqy − 2qxqw 2qxqz − 2qwqy 2qyqz + 2qwqx 1 − 2q 2 y − 2q 2 x , q = qw (R32 − R23)/(4qw) (R13 − R31)/(4qw) (R21 − R12)/(4qw) , where qw = √ 1 + R11 + R22 + R33 2 , kqk = 1 (4) 9Write-up:(1) Derive the quaternion Jacobian to rotation using Equation (4), i.e., ∂R ∂q and write the following code. Note: ignore the normalization kqk = 1. dR dq = JacobianQ(q) (2) Derive the rotation Jacobian to projection using Equation (2), i.e., ∂f(p)j ∂R where f(p)j =uj/wj vj/wj T and write the following code. Note: use vectorized form of the rotation matrix. df dR = JacobianR(R, C, X) (3) Derive the expression of ∂f(p)j ∂q using the chain rule. (4) Derive the camera center Jacobian to projection using Equation (2), i.e., ∂f(p)j ∂C and write the following code. df dC = JacobianC(R, C, X)(5) Write a code to refine the camera pose by minimizing the reprojection error and visualize reprojection error reduction as shown in Figure 5: [R, C] = PnP Nonlinear(R C, u, X) Algorithm 4 Nonlinear Camera Pose Refinement 1: p =CT q T T 2: for j = 1 : nIters do 3: C = p1:3, R=Quaternion2Rotation(q), q = p4:7 4: Build camera pose Jacobian for all points, ∂f(p)j ∂p = h ∂f(p)j ∂C ∂f(p)j ∂q i . 5: Compute f(p). 6: ∆p = ∂f(p) ∂p T ∂f(p) ∂p + λI −1 ∂f(p) ∂p T (b − f(p)) using Equation (3). 7: p = p + ∆p 8: Normalize the quaternion scale, p4:7 = p4:7/kp4:7k. 9: end for 10Measurement Linear estimate (reproj: 0.199104) Nonlinear estimate (reproj: 0.119272) (a) Reprojection error Measurement Linear estimate (reproj: 0.199104) Nonlinear estimate (reproj: 0.119272) (b) Close up Figure 5: Nonlinear refinement reduces the reprojection error (0.19→0.11). 8 Bundle Adjustment You will write a nonlinear refinement code that simultaneously optimizes camera poses and 3D points using the sparse nature of the Jacobian matrix. [P, X] = BundleAdjustient(P, X, R, Mx, My) For example, consider 3 camera poses and 2 points. The Jacobian matrix can be written as follows: J =∂f(p1,X1) ∂p1 02×7 02×7 ∂f(p1,X1) ∂X1 02×3 02×7 ∂f(p2,X1) ∂p2 02×7 ∂f(p2,X1) ∂X1 02×3 02×7 02×7 ∂f(p3,X1) ∂p3 ∂f(p3,X1) ∂X1 02×3 ∂f(p1,X2) ∂p1 02×7 02×7 02×3 ∂f(p1,X2) ∂X2 02×7 ∂f(p2,X2) ∂p2 02×7 02×3 ∂f(p2,X2) ∂X2 02×7 02×7 ∂f(p3,X2) ∂p3 02×3 ∂f(p3,X2) ∂X2 =Jp JX(5) where Jp and JX are the Jacobian for camera and point, respectively, and λ ∈ [0, 10]. The normal equation, J TJ∆x = J T (b − f(x)) can be decomposed into: A B BT D ∆pb ∆Xb = ep eX , (6) where A = J T pJp + λI, B = J T pJX, D = J T XJX + λI ep = J T p (b − f(x)), eX = J T X(b − f(x)) where pb =p T 1 · · · p T Iand Xb =XT 1 · · · XT Mwhere I and M are the number of images and points, respectively. 11The decomposed normal equation in Equation (6) allows us to efficiently compute the inverse of J TJ using Schur complement of D: ∆pb = (A − BD−1B T ) −1 (ep − BD−1 eX), ∆Xb = D−1 (eX − B T∆pb) where D is a block diagonal matrix whose inverse can be efficiently computed by inverting small block matrix: D = d1 . . . dM , D−1 = d −1 1 . . . d −1 M (7) The bundle adjustment algorithm is summarized in Algorithm 5. Note that not all points are visible from cameras. You need to reason about the visibility, i.e., if the point is not visible from the camera, the corresponding Jacobian and measurement from J and b will be omitted, respectively. 12Algorithm 5 Bundle Adjustment 1: pb =p T 1 · · · p T I T and Xb =XT 1 · · · XT M2: for iter = 1 : nIters do 3: Empty Jp, JX, b, f, Dinv. 4: for i = 1 : M do 5: d = 03×3 6: for j = 1 : I do 7: if the i th point is visible from the j th image then 8: J1 = 02×7I and J2 = 02×3M 9: J1(:, 7(j − 1) + 1 : 7j) = ∂f(pj ,Xi) ∂pj 10: J2(:, 3(i − 1) + 1 : 3i) = ∂f(pj ,Xi) ∂Xi 11: Jp =J T p J T 1 T and JX =J T X J T 2 T 12: d = d + ∂f(pj ,Xi) ∂Xi T ∂f(pj ,Xi) ∂Xi 13: b =b T u T ij 14: f =f T x T ij where µ xij 1 = RjI −Cj15: end if 16: end for 17: d = d + λI 18: Dinv = blkdiag(Dinv, d −1 ) 19: end for 20: ep = J T p (b − f) 21: eX = J T X(b − f) 22: A = J T pJp + λI, B = J T pJX, D−1 = Dinv 23: ∆pb = (A − BD−1BT ) −1 (ep − BD−1eX) 24: Normalize quaternions. 25: ∆Xb = D−1 (eX − BT∆pb) 26: end forWrite-up: You will first start with two images and 10 3D points to test your bundle adjustment program. (1) Derive Jp and JX. (2) Run Algorithm 5 and visualize the reprojection error similar to Figure 5. 139 Putting All Things Together Write-up: You will run with all images and 3D points based on Algorithm 1. (1) Visualize 3D camera pose and points as shown in Figure 6. (2) Visualize reprojection for all images. Top view Oblique view Figure 6: You will reconstruct all images and 3D points using structure from motion.
Figure 1: Histogram of oriented gradients. HOG feature is extracted and visualized for (a) the entire image and (b) zoom-in image. The orientation and magnitude of the red lines represents the gradient components in a local cell.In this assignment, you will implement a variant of HOG (Histogram of Oriented Gradients) in MATLAB proposed by Dalal and Trigg [1] (2015 Longuet-Higgins Prize Winner). It had been long standing top representation (until deep learning) for the object detection task with a deformable part model by combining with a SVM classifier [2].Given an input image, your algorithm will compute the HOG feature and visualize as shown in Figure 1 (the line directions are perpendicular to the gradient to show edge alignment). The orientation and magnitude of the red lines represents the gradient components in a local cell. function [hog] = HOG(im) Input: input gray-scale image with uint8 format. Output: HOG descriptor.You will compute the HOG descriptor of input image im. The pseudocode can be found below: Algorithm 1 HOG 1: Convert the gray-scale image to double format. 2: Get differential images using GetDifferentialFilter and FilterImage 3: Compute the gradients using GetGradient 4: Build the histogram of oriented gradients for all cells using BuildHistogram 5: Build the descriptor of all blocks with normalization using GetBlockDescriptor 6: Return a long vector (hog) by concatenating all block descriptors.2.1 Image filtering m n (a) Input image (b) Differential along x direction (c) Differential along y direction Figure 2: (a) Input image dimension. (b-c) Differential image along x and y directions. function [filter_x, filter_y] = GetDifferentialFilter() Input: none. Output: filter_x and filter_y are 3×3 filters that differentiate along x and y directions, respectively.You will compute the gradient by differentiating the image along x and y directions. This code will output the differential filters. function [im_filtered] = FilterImage(im, filter) Input: im is the gray scale m × n image (Figure 2(a)) converted to double (refer to im2double built-in function); filter is a filter (k × k matrix) Output: im_filtered is m × n filtered image. You may need to pad zeros on the boundary on the input image to get the same size filtered image. Description: Given an image and filter, you will compute the filtered image. Given the two functions above, you can generate differential images by visualizing the magnitude of the filter response as shown in Figure 2(b) and 2(c).(a) Magnitude 0 20 40 60 80 100 120 140 160 180 (b) Angle (c) Gradient (d) Zoomed eye (e) Zoomed neck Figure 3: Visualization of (a) magnitude and (b) orientation of image gradients. (c-e) Visualization of gradients at every 3rd pixel (the magnitudes are re-scaled for illustrative purpose.). function [grad_mag, grad_angle] = GetGradient(im_dx, im_dy) Input: im_dx and im_dy are the x and y differential images (size: m × n). Output: grad_mag and grad_angle are the magnitude and orientation of the gradient images (size: m × n). Note that the range of the angle should be [0, π), i.e., unsigned angle (θ == θ + π). Description: Given the differential images, you will compute the magnitude and angle of the gradient. Using the gradients, you can visualize and have some sense with the image, i.e., the magnitude of the gradient is proportional to the contrast (edge) of the local patch and the orientation is perpendicular to the edge direction as shown in Figure 3. 42.3 Orientation BinningIgnore this shaded area c ell_ siz e Store gradient mag 4,3 M N (u,v) (a) ori histo 165 15 45 75 105 135 165 S u m o f m a g nit u d e s (b) Histogram per cell Figure 4: (a) Histogram of oriented gradients can be built by (b) binning the gradients to corresponding bin. function ori_histo = BuildHistogram(grad_mag, grad_angle, cell_size) Input: grad_mag and grad_angle are the magnitude and orientation of the gradient images (size: m × n); cell_size is the size of each cell, which is a positive integer. Output: ori_histo is a 3D tensor with size M × N × 6 where M and N are the number of cells along y and x axes, respectively, i.e., M = bm/cell_sizec and N = bn/cell_sizec where b·c is the round-off operation as shown in Figure 4(a). Description: Given the magnitude and orientation of the gradients per pixel, you can build the histogram of oriented gradients for each cell. ori_histo(i, j, k) = X (u,v)∈Ci,j grad_mag(u, v) if grad_angle(u, v) ∈ θk (1) where Ci,j is a set of x and y coordinates within the (i, j) cell, and θk is the angle range of each bin, e.g., θ1 = [165◦ , 180◦ ) ∪ [0◦ , 15◦ ), θ2 = [15◦ , 45◦ ), θ3 = [45◦ , 75◦ ), θ4 = [75◦ , 105◦ ), θ5 = [105◦ , 135◦ ), and θ6 = [135◦ , 165◦ ). Therefore, ori_histo(i,j,:) returns the histogram of the oriented gradients at (i, j) cell as shown in Figure 4(b). Using the ori_histo, you can visualize HOG per cell where the magnitude of the line proportional to the histogram as shown in Figure 1. Typical cell_size is 8. 5Blo2cxk2 block Concatenation of HOG and normalization Block M N (a) Block descriptor Block M-1 N-1 (b) Block overlap with stride 1 Figure 5: HOG is normalized to account illumination and contrast to form a descriptor for a block. (a) HOG within (1,1) block is concatenated and normalized to form a long vector of size 24. (b) This applies to the rest block with overlap and stride 1 to form the normalized HOG. function ori_histo_normalized = GetBlockDescriptor(ori_histo, block_size) Input: ori_histo is the histogram of oriented gradients without normalization. block_size is the size of each block (e.g., the number of cells in each row/column), which is a positive integer. Output: ori_histo_normalized is the normalized histogram (size: (M−(block_size− 1)) × (N − (block_size − 1)) × (6 × block_size2 ).To account for changes in illumination and contrast, the gradient strengths must be locally normalized, which requires grouping the cells together into larger, spatially connected blocks (adjacent cells). Given the histogram of oriented gradients, you apply L2 normalization as follow: 1. Build a descriptor of the first block by concatenating the HOG within the block. You can use block_size=2, i.e., 2 × 2 block will contain 2 × 2 × 6 entries that will be concatenated to form one long vector as shown in Figure 5(a). 2. Normalize the descriptor as follow: hˆ i = p hi P i h 2 i + e 2 (2) where hi is the i th element of the histogram and hˆ i is the normalized histogram. e is the normalization constant to prevent division by zero (e.g., e = 0.001). 3. Assign the normalized histogram to ori_histo_normalized(1,1) (white dot location in Figure 5(a)). 4. Move to the next block ori_histo_normalized(1,2) with the stride 1 and iterate 1-3 steps above. The resulting ori_histo_normalized will have the size of (M − 1) × (N − 1) × 24. 6References [1] N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,” in CVPR, 2005. [2] P. F. Felzenszwalb, R. B. Girshick, D. McAllester, and D. Ramanan, “Object detection with discriminatively trained part based models,” TPAMI, 2010.(a) Image (b) SIFT Figure 1: Given an image (a), you will extract SIFT features using VLFeat. One of key skills to learn in computer vision is the ability to use other open source code, which allow you not to re-invent the wheel. We will use VLFeat by A. Vedaldi and B. Fulkerson (2008) for SIFT extraction given your images. Install VLFeat from following: https://www.vlfeat.org/install-matlab.htmlRun vl demo sift basic to double check the installation is completed. (Note) You will use this library only for SIFT feature extraction and its visualization. All following visualizations and algorithms must be done by your code. Using VLFeat, you can extract keypoints and associated descriptors as shown in Figure 1. (SIFT visualization) Use VLFeat to visualize SIFT features with scale and orientation as shown in Figure 1. You may want to follow the following tutorial: https://www.vlfeat.org/overview/sift.html(a) Template (b) Target (c) SIFT matches with ratio test Figure 2: You will match points between the template and target image using SIFT features. The SIFT is composed of scale, orientation, and 128 dimensional local feature descriptor (integer), f ∈ Z128. You will use the SIFT features to match between two images, I1 and I2. Use two sets of descriptors from the template and target, find the matches using nearest neighbor with the ratio test. You may use knnsearch built-in function in MATLAB. function [x1, x2] = FindMatch(I1, I2) Input: two input gray-scale images with uint8 format. Output: x1 and x2 are n × 2 matrices that specify the correspondence. Description: Each row of x1 and x2 contains the (x, y) coordinate of the point correspondence in I1 ad I2, respectively, i.e., x1(i,:) ↔ x2(i,:). (Note) You can only use VLFeat for the SIFT descriptor extraction. Matching with the ratio test needs to be implemented by yourself.4 Feature-based Image AlignmentFigure 3: You will compute an affine transform using SIFT matches filtered by RANSAC. Blue: outliers; Orange: inliers; Red: the boundary of the transformed template. (Note) From this point, you cannot use any function provided by VLFeat. The noisy SIFT matches can be filtered by RANSAC with an affine transformation as shown in Figure 3. function [A] = AlignImageUsingFeature(x1, x2, ransac_thr, ransac_iter) Input: x1 and x2 are the correspondence sets (n × 2 matrices). ransac_thr and ransac_iter are the error threshold and the number of iterations for RANSAC. Output: 3 × 3 affine transformation. Description: The affine transform will transform x1 to x2, i.e., x2 = Ax1. You may visualize the inliers and the boundary of the transformed template to validate your implementation.(a) Image (b) Warped image (c) Template (d) Error map Figure 4: You will use the affine transform to warp the target image to the template using the inverse mapping. Using the warped image, the error map |Itpl − Iwrp| can be computed to validate the correctness of the transformation where Itpl and Iwrp are the template and warped images. Given an affine transform A, you will write a code to warp an image I(x) → I(Ax). function [I_warped] = WarpImage(I, A, output_size) Input: I is an image to warp, A is the affine transformation from the original coordinate to the warped coordinate, output_size=[h,w] is the size of the warped image where w and h are the width and height of the warped image. Output: I_warped is the warped image with the size of output_size.The inverse mapping method needs to be applied to make sure the warped image does not produce empty pixel. You are allowed to use interp2 build-in function in MATLAB for bilinear interpolation. (Validation) Using the warped image, the error map |Itpl − Iwrp| can be computed to validate the correctness of the transformation where Itpl and Iwrp are the template and warped images.(a) Template (b) Initialization (c) Aligned image Figure 5: You will use the initial estimate of the affine transform to align (i.e., track) next image. (a) Template image from the first frame image. (b) The second frame image with the initialization of the affine transform. (c) The second frame image with the optimized affine transform using the inverse compositional image alignment. Given the initial estimate of the affine transform A from the feature based image alignment (Section 4) as shown in Figure 5(b), you will track the next frame image using the inverse compositional method (Figure 5(c)). You will parametrize the affine transform with 6 parameters p = (p1, p2, p3, p4, p5, p6), i.e., W(x; p) = p1 + 1 p2 p3 p4 p5 + 1 p6 0 0 1 u v 1 = A(p)x (1) where W(x; p) is the warping function from the template patch to the target image. x = u v 1 is the coordinate of the point before warping, and A(p) is the affine transform parametrized by p. function [A_refined] = AlignImage(template, target, A) Input: gray-scale template template and target image target; the initialization of 3×3 affine transform A, i.e., xtgt =Axtpl where xtgt and xtpl are points in the target and template images, respectively.Output: A_refined is the refined affine transform based on inverse compositional image alignment Description: You will refine the affine transform using inverse compositional image alignment, i.e., A→A_refined. The pseudo-code can be found in Algorithm 1.Tip: You can validate your algorithm by visualizing their error map as shown in Figure 6(d) and 6(h). Also you can visualize the error plot over iterations, i.e., the error must decrease as shown in Figure 6(i).(a) Template (b) Initial warp (c) Overlay (d) Error map (e) Template (f) Opt. warp (g) Overlay (h) Error map 0 50 100 150 200 250 300 350 400 450 Iteration 20 22 24 26 28 30 32 Error ||Itpl – Itgt|| (i) Error map Figure 6: (a,e) Template images of the first frame. (b) Warped image based on the initialization of the affine parameters. (c) Template image is overlaid by the initialization.(d) Error map of the initialization. (f) Optimized warped image using the inverse compositional image alignment. (g) Template image is overlaid by the optimized warped image. (h) Error map of the optimization. (i) An error plot over iterations.Algorithm 1 Inverse Compositional Image Alignment 1: Initialize p = p0 from input A. 2: Compute the gradient of template image, ∇Itpl 3: Compute the Jacobian ∂W ∂p at (x; 0). 4: Compute the steepest decent images ∇Itpl ∂W ∂p 5: Compute the 6 × 6 Hessian H = P x h ∇Itpl ∂W ∂p iT h ∇Itpl ∂W ∂p i 6: while kpk > do 7: Warp the target to the template domain Itgt(W(x; p)). 8: Compute the error image Ierr = Itgt(W(x; p)) − Itpl. 9: Compute F = P x h ∇Itpl ∂W ∂p iT Ierr. 10: Compute ∆p = H−1F. 11: Update W(x; p) ← W(x; p) ◦ W(x; ∆p) = W(W(x; ∆p); p). 12: end while 13: Return A_refined made of p. 77 Putting Things Together: Multiframe Tracking (a) Frame 1 (b) Frame 2 (c) Frame 3 (d) Frame 4 Figure 7: You will use the inverse compositional image alignment to track 4 frames of images. Given a template and a set of consecutive images, you will (1) initialize the affine transform using the feature based alignment and then (2) track over frames using the inverse compositional image alignment. function [A_cell] = TrackMultiFrames(template, image_cell) Input: template is gray-scale template. image_cell is a cell structure that contains a set of consecutive image frames, i.e., image_cell{i} is the i th frame. Output: A_cell is the set of affine transforms from the template to each frame of image, i.e., A_cell{i} is the affine transform from the template to the i th image.Description: You will apply the inverse compositional image alignment sequentially to track over frames as shown in Figure 7. Note that the template image needs to be updated at every frame, i.e., template←WarpImage(I, inv(A), size(template)).• Individual assignment • 2 page summary write-up with resulting visualization (more than 1 page assignment will be automatically returned.). • Submission through Canvas. • List of submission codes: – GetTinyImage.m – PredictKNN.m – ClassifyKNN_Tiny.m – BuildVisualDictionary.m – ComputeBoW.m – ClassifyKNN_BoW.m – PredictSVM.m – ClassifySVM_BoW.m • DO NOT SUBMIT THE PROVIDED IMAGE DATA • The function that does not comply with its specification will not be graded.• You are allowed to use MATLAB built-in functions except for the ones in the Computer Vision Toolbox. Please consult with TA if you are not sure about the list of allowed functions.Figure 1: You will design a visual recognition system to classify the scene categories. The goal of this assignment is to build a set of visual recognition systems that classify the scene categories. The scene classification dataset consists of 15 scene categories including office, kitchen, and forest as shown in Figure 1 [1]. The system will compute a set of image representations (tiny image and bag-of-word visual vocabulary) and predict the category of each testing image using the classifiers (k-nearest neighbor and SVM) built on the training data. A simple pseudo-code of the recognition system can found below: Algorithm 1 Scene Recognition 1: Load training and testing images 2: Build image representation 3: Train a classifier using the representations of the training images 4: Classify the testing data. 5: Compute accuracy of testing data classification. For the knn classifier, step 3 and 4 can be combined. 2You can download the training and testing data from here: https://www.cs.umn.edu/~hspark/csci5561/scene_classification_data.zip The data folder includes two text files (train.txt and test.txt) and two folders (train and test). Each row in the text file specifies the image and its label, i.e., (label) (image path). The text files can be used to load images. In each folder, it includes 15 classes (Kitchen, Store, Bedroom, LivingRoom, Office, Industrial, Suburb, InsideCity, TallBuilding, Street, Highway, OpenCountry, Coast, Mountain, Forest) of scene images.Similar to HW #2, you will use VLFeat (https://www.vlfeat.org/install-matlab. html). You are allowed to use the following two functions: vl_dsift and vl_svmtrain.5 Tiny Image KNN Classification(a) Image (b) Tiny Image Figure 2: You will use tiny image representation to get an image feature. function [feature] = GetTinyImage(I, output_size) Input: I is an gray scale image, output_size=[w,h] is the size of the tiny image. Output: feature is the tiny image representation by vectorizing the pixel intensity in a column major order. The resulting size will be w×h.You will simply resize each image to a small, fixed resolution (e.g., 16×16). You need to normalize the image by having zero mean and unit length. This is not a particularly good representation, because it discards all of the high frequency image content and is not especially invariant to spatial or brightness shifts. function [label_test_pred] = PredictKNN(feature_train, label_train, feature_test, k) Input: feature_train is a ntr × d matrix where ntr is the number of training data samples and d is the dimension of image feature, e.g., 265 for 16×16 tiny image representation. Each row is the image feature. label_train∈ [1, 15] is a ntr vector that specifies the label of the training data. feature_test is a nte × d matrix that contains the testing features where nte is the number of testing data samples. k is the number of neighbors for label prediction. Output: label_test_pred is a nte vector that specifies the predicted label for the testing data. Description: You will use a k-nearest neighbor classifier to predict the label of the testing data. 4 Kit Sto Bed Liv Off Ind Sub Cty Bld St HW OC Cst Mnt For Accuracy: 0.205333 Kitchen Store Bedroom LivingRoom Office Industrial Suburb InsideCity TallBuilding Street Highway OpenCountry Coast Mountain Forest Figure 3: Confusion matrix for Tiny+KNN. function [confusion, accuracy] = ClassifyKNN_Tiny Output: confusion is a 15 × 15 confusion matrix and accuracy is the accuracy of the testing data prediction.You will combine GetTinyImage and PredictKNN for scene classification. Your goal is to achieve the accuracy >18%. 5Figure 4: Each row represents a distinctive cluster from bag-of-word representation. function [vocab] = BuildVisualDictionary(training_image_cell, dic_size) Input: training_image_cell is a set of training images and dic_size is the size of the dictionary (the number of visual words). Output: vocab lists the quantized visual words whose size is dic_size×128.Given a set of training images, you will build a visual dictionary made of quantized SIFT features. You may start dic_size=50. You can use the following built-in functions: • vl_dsift from VLFeat. • kmeans from MATLAB toolbox. You may visualize the image patches to make sense the clustering as shown in Figure 4. Algorithm 2 Visual Dictionary Building 1: For each image, compute dense SIFT over regular grid 2: Build a pool of SIFT features from all training images 3: Find cluster centers from the SIFT pool using kmeans algorithms. 4: Return the cluster centers.Kit Sto Bed Liv Off Ind Sub Cty Bld St HW OC Cst Mnt For Accuracy: 0.512667 Kitchen Store Bedroom LivingRoom Office Industrial Suburb InsideCity TallBuilding Street Highway OpenCountry Coast Mountain Forest Figure 5: Confusion matrix for BoW+KNN. function [bow_feature] = ComputeBoW(feature, vocab) Input: feature is a set of SIFT features for one image, and vocab is visual dictionary. Output: bow_feature is the bag-of-words feature vector whose size is dic_size.Description: Give a set of SIFT features from an image, you will compute the bag-ofwords feature. The BoW feature is constructed by counting SIFT features that fall into each cluster of the vocabulary. Nearest neighbor can be used to find the closest cluster center. The histogram needs to be normalized such that BoW feature has a unit length. function [confusion, accuracy] = ClassifyKNN_BoW Output: confusion is a 15 × 15 confusion matrix and accuracy is the accuracy of the testing data prediction.Description: Given BoW features, you will combine BuildVisualDictionary, ComputeBoW, and PredictKNN for scene classification. Your goal is to achieve the accuracy >50%. 7function [label_test_pred] = PredictSVM(feature_train, label_train, feature_test) Input: feature_train is a ntr × d matrix where ntr is the number of training data samples and d is the dimension of image feature. Each row is the image feature. label_train∈ [1, 15] is a ntr vector that specifies the label of the training data. feature_test is a nte × d matrix that contains the testing features where nte is the number of testing data samples. Output: label_test_pred is a nte vector that specifies the predicted label for the testing data.Description: You will use a SVM classifier to predict the label of the testing data. You don’t have to implement the SVM classifier. Instead, you can use VLFeat vl_svmtrain. Linear classifiers are inherently binary and we have a 15-way classification problem. To decide which of 15 categories a test case belongs to, you will train 15 binary, 1-vs-all SVMs. 1-vs-all means that each classifier will be trained to recognize ‘forest’ vs ‘nonforest’, ‘kitchen’ vs ‘non-kitchen’, etc. All 15 classifiers will be evaluated on each test case and the classifier which is most confidently positive “wins”. For instance, if the ‘kitchen’ classifier returns a score of -0.2 (where 0 is on the decision boundary), and the ‘forest’ classifier returns a score of -0.3, and all of the other classifiers are even more negative, the test case would be classified as a kitchen even though none of the classifiers put the test case on the positive side of the decision boundary. When learning an SVM, you have a free parameter ’lambda’ which controls how strongly regularized the model is. Your accuracy will be very sensitive to lambda, so be sure to test many values. 8Kit Sto Bed Liv Off Ind Sub Cty Bld St HW OC Cst Mnt For Accuracy: 0.629333 Kitchen Store Bedroom LivingRoom Office Industrial Suburb InsideCity TallBuilding Street Highway OpenCountry Coast Mountain Forest Figure 6: Confusion matrix for BoW+SVM. function [confusion, accuracy] = ClassifySVM_BoW Output: confusion is a 15 × 15 confusion matrix and accuracy is the accuracy of the testing data prediction.Description: Given BoW features, you will combine BuildVisualDictionary, ComputeBoW, PredictSVM for scene classification. Your goal is to achieve the accuracy >60%.References [1] S. Lazebnik, C. Schmid, and J. Ponce, “Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories,” CVPR, 2006.• Assignment due: Apr 19 (11:55pm) • Individual assignment • Up to 2 page summary write-up with resulting visualization (more than 2 page assignment will be automatically returned.). • Submission through Canvas. • Skeletal codes can be downloaded from: https://www-users.cs.umn.edu/~hspark/csci5561/HW4_code.zip. It contains the following four codes: – main_slp_linear.m – main_slp.m – main_mlp.m – main_cnn.m • List of submission codes: – GetMiniBatch.m – FC.m – FC_backward.m – Loss_euclidean.m – TrainSLP_linear.m – Loss_cross_entropy_softmax.m – TrainSLP – ReLu.m – ReLu_backward.m – TrainMLP.m – Conv.m – Conv_backward.m – Pool2x2.m – Pool2x2_backward.m – Flattening.m – Flattening_backward.m – TrainCNN.m• A list of MAT files that contain the following trained weights: – slp_linear.mat: w, b – slp.mat: w, b – mlp.mat: w1, b1, w2, b2 – cnn.mat: w_conv, b_conv, w_fc, b_fc • DO NOT SUBMIT THE PROVIDED IMAGE DATA • The function that does not comply with its specification will not be graded.• You are allowed to use MATLAB built-in functions except for the ones in the Computer Vision Toolbox and Deep Learning Toolbox. Please consult with TA if you are not sure about the list of allowed functions.Figure 1: You will implement (1) a multi-layer perceptron (neural network) and (2) convolutiona neural network to recognize hand-written digit using the MNIST dataset. The goal of this assignment is to implement neural network to recognize hand-written digits in the MNIST data. MNIST Data You will use the MNIST hand written digit dataset to perform the first task (neural network). We reduce the image size (28 × 28 → 14 × 14) and subsample the data. You can download the training and testing data from here: https://www.cs.umn.edu/~hspark/csci5561/ReducedMNIST.zipThe zip file includes two MAT files (mnist_train.mat and mnist_test.mat). Each file includes im_* and label_* variables: • im_* is a matrix (196 × n) storing vectorized image data (196 = 14 × 14) • label_* is n × 1 vector storing the label for each image data. n is the number of images. You can visualize the i th image, e.g., imshow(uint8(reshape(im_train(:,i), [14,14]))). 3x1 w 1 y 1 a 196 x 1 10 a 10 y (a) Single linear perceptron 0 2000 4000 6000 8000 Iterations 6 7 8 9 10 11 12 13 Loss Training loss Testing loss (b) Loss 0 1 2 3 4 5 6 7 8 9 Accuracy: 0.297905 0 1 2 3 4 5 6 7 8 9 (c) Confusion Figure 2: You will implement a single linear perceptron that produces accuracy near 30%. Random chance is 10% on testing data.You will implement a single-layer linear perceptron (Figure 2(a)) with stochastic gradient descent method. We provide main_slp_linear where you will implement GetMiniBatch and TrainSLP_linear. function [mini_batch_x, mini_batch_y] = GetMiniBatch(im_train, label_train, batch_size) Input: im_train and label_train are a set of images and labels, and batch_size is the size of the mini-batch for stochastic gradient descent.Output: mini_batch_x and mini_batch_y are cells that contain a set of batches (images and labels, respectively). Each batch of images is a matrix with size 194×batch_size, and each batch of labels is a matrix with size 10×batch_size (one-hot encoding). Note that the number of images in the last batch may be smaller than batch_size.You may randomly permute the the order of images when building the batch, and whole sets of mini_batch_* must span all training data. function y = FC(x, w, b) Input: x∈ Rm is the input to the fully connected layer, and w∈ Rn×m and b∈ Rn are the weights and bias. Output: y∈ Rn is the output of the linear transform (fully connected layer).Description: FC is a linear transform of x, i.e., y = wx + b. function [dLdx dLdw dLdb] = FC_backward(dLdy, x, w, b, y) Input: dLdy ∈ R1×n is the loss derivative with respect to the output y. 4Output: dLdx ∈ R1×m is the loss derivative with respect the input x, dLdw ∈ R1×(n×m) is the loss derivative with respect to the weights, and dLdb ∈ R1×n is the loss derivative with respec to the bias.The partial derivatives w.r.t. input, weights, and bias will be computed. dLdx will be back-propagated, and dLdw and dLdb will be used to update the weights and bias. function [L, dLdy] = Loss_euclidean(y_tilde, y) Input: y_tilde ∈ Rm is the prediction, and y∈ 0, 1 m is the ground truth label. Output: L∈ R is the loss, and dLdy is the loss derivative with respect to the prediction. Description: Loss_euclidean measure Euclidean distance L = ky − yek 2 . function [w, b] = TrainSLP_linear(mini_batch_x, mini_batch_y) Input: mini_batch_x and mini_batch_y are cells where each cell is a batch of images and labels. Output: w ∈ R10×196 and b ∈ R10×1 are the trained weights and bias of a single-layer perceptron.You will use FC, FC_backward, and Loss_euclidean to train a singlelayer perceptron using a stochastic gradient descent method where a pseudo-code can be found below. Through training, you are expected to see reduction of loss as shown in Figure 2(b). As a result of training, the network should produce more than 25% of accuracy on the testing data (Figure 2(c)).Algorithm 1 Stochastic Gradient Descent based Training 1: Set the learning rate γ 2: Set the decay rate λ ∈ (0, 1] 3: Initialize the weights with a Gaussian noise w ∈ N (0, 1) 4: k = 1 5: for iIter = 1 : nIters do 6: At every 1000th iteration, γ ← λγ 7: ∂L ∂w ← 0 and ∂L ∂b ← 0 8: for Each image xi in k th mini-batch do 9: Label prediction of xi 10: Loss computation l 11: Gradient back-propagation of xi , ∂l ∂w using back-propagation. 12: ∂L ∂w = ∂L ∂w + ∂l ∂w and ∂L ∂b = ∂L ∂b + ∂l ∂b 13: end for 14: k++ (Set k = 1 if k is greater than the number of mini-batches.) 15: Update the weights, w ← w − γ R ∂L ∂w , and bias b ← b − γ R ∂L ∂b 16: end for 5x1 w 1 y 196 x 1 10 y 1 a 10 a 1 f S o ft – m a x 10 f (a) Single-layer perceptron 0 1000 2000 3000 4000 5000 Iterations 0 0.2 0.4 0.6 0.8 1 1.2 1.4 Loss Training loss Testing loss (b) Loss 0 1 2 3 4 5 6 7 8 9 Accuracy: 0.898720 0 1 2 3 4 5 6 7 8 9 (c) Confusion Figure 3: You will implement a single perceptron that produces accuracy near 90% on testing data.You will implement a single-layer perceptron with soft-max cross-entropy using stochastic gradient descent method. We provide main_slp where you will implement TrainSLP. Unlike the single-layer linear perceptron, it has a soft-max layer that approximates a max function by clamping the output to [0, 1] range as shown in Figure 3(a).function [L, dLdy] = Loss_cross_entropy_softmax(x, y) Input: x ∈ Rm is the input to the soft-max, and y∈ 0, 1 m is the ground truth label. Output: L∈ R is the loss, and dLdy is the loss derivative with respect to x.Description: Loss_cross_entropy_softmax measure cross-entropy between two distributions L = Pm i yi log yei where yei is the soft-max output that approximates the max operation by clamping x to [0, 1] range: yei = e xi P i e xi , where xi is the i th element of x. function [w, b] = TrainSLP(mini_batch_x, mini_batch_y) Output: w ∈ R10×196 and b ∈ R10×1 are the trained weights and bias of a single-layer perceptron.Description: You will use the following functions to train a single-layer perceptron using a stochastic gradient descent method: FC, FC_backward, Loss_cross_entropy_softmax Through training, you are expected to see reduction of loss as shown in Figure 3(b). As a result of training, the network should produce more than 85% of accuracy on the testing data (Figure 3(c)). 5 Multi-layer Perceptronw1 1 x 196 x 1 1 y 1 a 10 y 10 a 1 a 1 f m a mf w2 1 f S o ft – m a x 10 f (a) Multi-layer perceptron 0 1 2 3 4 5 6 7 8 9 Accuracy: 0.914553 0 1 2 3 4 5 6 7 8 9 (b) Confusion Figure 4: You will implement a multi-layer perceptron that produces accuracy more than 90% on testing data. You will implement a multi-layer perceptron with a single hidden layer using a stochastic gradient descent method. We provide main_mlp. The hidden layer is composed of 30 units as shown in Figure 4(a). function [y] = ReLu(x) Input: x is a general tensor, matrix, and vector.Output: y is the output of the Rectified Linear Unit (ReLu) with the same input size. Description: ReLu is an activation unit (yi = max(0, xi)). In some case, it is possible to use a Leaky ReLu (yi = max(xi , xi) where = 0.01). function [dLdx] = ReLu_backward(dLdy, x, y) Input: dLdy ∈ R1×z is the loss derivative with respect to the output y ∈ Rz where z is the size of input (it can be tensor, matrix, and vector). Output: dLdx ∈ R1×z is the loss derivative with respect to the input x. function [w1, b1, w2, b2] = TrainMLP(mini_batch_x, mini_batch_y) Output: w1 ∈ R30×196 , b1 ∈ R30×1 , w2 ∈ R10×30 , b2 ∈ R10×1 are the trained weights and biases of a multi-layer perceptron.Description: You will use the following functions to train a multi-layer perceptron using a stochastic gradient descent method: FC, FC_backward, ReLu, ReLu_backward, Loss_cross_entropy_softmax. As a result of training, the network should produce more than 90% of accuracy on the testing data (Figure 4(b)). 7Input Conv (3) ReLu Pool (2×2) Flatten FC Soft-max (a) CNN 0 1 2 3 4 5 6 7 8 9 Accuracy: 0.947251 0 1 2 3 4 5 6 7 8 9 (b) Confusion Figure 5: You will implement a convolutional neural network that produces accuracy more than 92% on testing data.You will implement a convolutional neural network (CNN) using a stochastic gradient descent method. We provide main_cnn. As shown in Figure 4(a), the network is composed of: a single channel input (14×14×1) → Conv layer (3×3 convolution with 3 channel output and stride 1) → ReLu layer → Max-pooling layer (2 × 2 with stride 2) → Flattening layer (147 units) → FC layer (10 units) → Soft-max. function [y] = Conv(x, w_conv, b_conv) Input: x ∈ RH×W×C1 is an input to the convolutional operation, w_conv ∈ RH×W×C1×C2 and b_conv ∈ RC2 are weights and bias of the convolutional operation.Output: y ∈ RH×W×C2 is the output of the convolutional operation. Note that to get the same size with the input, you may pad zero at the boundary of the input image.Description: This convolutional operation can be simplified using MATLAB built-in function im2col. function [dLdw, dLdb] = Conv_backward(dLdy, x, w_conv, b_conv, y) Input: dLdy is the loss derivative with respec to y. Output: dLdw and dLdb are the loss derivatives with respect to convolutional weights and bias w and b, respectively. Description: This convolutional operation can be simplified using MATLAB built-in function im2col. Note that for the single convolutional layer, ∂L ∂x is not needed.function [y] = Pool2x2(x) Input: x ∈ RH×W×C is a general tensor and matrix. Output: y ∈ R H 2 × W 2 ×C is the output of the 2 × 2 max-pooling operation with stride 2. 8function [dLdx] = Pool2x2_backward(dLdy, x, y) Input: dLdy is the loss derivative with respect to the output y. Output: dLdx is the loss derivative with respect to the input x. function [y] = Flattening(x) Input: x ∈ RH×W×C is a tensor. Output: y ∈ RHW C is the vectorized tensor (column major). function [dLdx] = Flattening_backward(dLdy, x, y) Input: dLdy is the loss derivative with respect to the output y. Output: dLdx is the loss derivative with respect to the input x. function [w_conv, b_conv, w_fc, b_fc] = TrainCNN(mini_batch_x, mini_batch_y) Output: w_conv ∈ R3×3×1×3 , b_conv ∈ R3 , w_fc ∈ R10×147 , b_fc ∈ R147 are the trained weights and biases of the CNN.Description: You will use the following functions to train a convolutional neural network using a stochastic gradient descent method: Conv, Conv_backward, Pool2x2, Pool2x2_backward, Flattening, Flattening_backward, FC, FC_backward, ReLu, ReLu_backward, Loss_cross_entropy_softmax. As a result of training, the network should produce more than 92% of accuracy on the testing data (Figure 5(b)).2 OverviewIn this assignment, you will implement a stereo reconstruction algorithm given two view images. (a) Left image (b) Right image Figure 1: In this assignment, you will implement a stereo reconstruction algorithm given two images.You can download the skeletal code and data (left.bmp and right.bmp) from here: https://www-users.cs.umn.edu/~hspark/csci5561/HW5.zip You will fill main_stereo.m that takes input images and intrinsic parameters K, and produces a stereo disparity map. 2(a) Matching from I1 to I2 (b) Matching from I2 to I1 (c) Matching from I1 to I2 after ratio test (d) Matching from I2 to I1 after ratio test (e) Bidirectional matching between I1 and I2 Figure 2: You will match points between I1 and I2 using SIFT features. You will use VLFeat SIFT to extract keypoints and match between two views using k-nearest neighbor search. The matches will be filtered using the ratio test and bidirectional consistency check. function [x1, x2] = FindMatch(I1, I2) Input: two input gray-scale images with uint8 format.Output: x1 and x2 are n × 2 matrices that specify the correspondence.Each row of x1 and x2 contains the (x, y) coordinate of the point correspondence in I1 ad I2, respectively, i.e., x1(i,:) ↔ x2(i,:). This matching function is similar to HW#2 except that bidirectional consistency check is mandatory. (Note) Except for SIFT extraction, you are not allowed to use VLFeat functions. 3Figure 3: Given matches, you will compute a fundamental matrix to draw epipolar lines. function [F] = ComputeF(x1, x2) Input: x1 and x2 are n × 2 matrices that specify the correspondence. Output: F ∈ R3×3 is the fundamental matrix.F is robustly computed by the 8-point algorithm within RANSAC. Note that the rank of the fundamental matrix needs to be 2 (SVD clean-up should be applied.). You can verify the validity of fundamental matrix by visualizing epipolar line as shown in Figure 3. (Note) Given the fundamental matrix, you can run the provided function: [R1 C1 R2 C2 R3 C3 R4 C4] = ComputeCameraPose(F, K) This function computes the four sets of camera poses given the fundamental matrix where R1 C1 · · · R4 C4 are rotation and camera center (represented in the world coordinate system) and K is the intrinsic parameter. These four configurations can be visualized in 3D as shown in Figure 4. -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 1.2 0 0.8 0.6 0.4 0.2 0 0.5 0.2 0 0 -0.2 -0.5 -0.4 -1 -0.6 -1.5 0.5 0 -0.5 0 0 0.2 -0.2 0.4 0 0.2 0.4 0.6 0.8 1 -1 -0.5 0 0.5 0.2 0 -0.2 -0.4 -1.5 -0.6 0 Figure 4: Four configurations of camera pose from a fundamental matrix.5 TriangulationGiven camera pose and correspondences, you will triangulate to reconstruct 3D points. function [X] = Triangulation(P1, P2, x1, x2) Input: P1 and P2 are two camera projection matrices (R3×4 ). x1 and x2 are n × 2 matrices that specify the correspondence. Output: X is n × 3 where each row specifies the 3D reconstructed point.Use the triangulation method by linear solve, i.e., u 1 × P1 v 1 × P2 X 1 = 0 (Note) Use plot3 to visualize them as shown in Figure 5. 0 50 100 0 -20 -50 -40 -60 -80 0 0 -100 20 -50 40 60 0 80 50 40 20 40 60 80 0 -20 0 20 -20 -80 -60 -40 0 -40 -20 0 20 0-80 -60 -40 -20 0 20 40 60 (a) nValid = 10 (b) nValid = 488 (c) nValid = 0 (d) nValid = 0 Figure 5: You can visualize four camera pose configurations with point cloud. 56 Pose DisambiguationGiven four configurations of relative camera pose and reconstructed points, you will find the best camera pose by verifying through 3D point triangulation. function [R,C,X] = DisambiguatePose(R1,C1,X1,R2,C2,X2,R3,C3,X3,R4,C4,X4) Input: R1, C1, X1 · · · R4, C4, X4 are four sets of camera rotation, center, and 3D reconstructed points. Output: R, C, X are the best camera rotation, center, and 3D reconstructed points.The 3D point must lie in front of the both cameras, which can be tested by: r T 3 (X − C) > 0 (1) where r3 is the 3rd row of the rotation matrix. In Figure 5, nValid means the number of points that are in front of both cameras. (b) configuration produces the maximum number of valid points, and therefore the best configuration is (b). 6(a) Rectified image 1 (b) Rectified image 2 Figure 6: Stereo rectification. Given the disambiguated camera pose, you will implement dense stereo matching between two views based on dense SIFT of VLFeat. function [H1, H2] = ComputeRectification(K, R, C) Input: The relative camera pose (R and C) and intrinsic parameter K. Output: H1 and H2 are homographies that rectify the left and right images such that the epipoles are at infinity.Given the disambiguated camera pose, you can find the rectification rotation matrix, Rrect such that the x-axis of the images aligns with the baseline. Find the rectification homography H = KRrectRTK−1 where R is the rotation matrix of the camera. The rectified images are shown in Figure 6. This rectification sends the epipoles to infinity where the epipolar line becomes horizontal. (Note) You can use the provided image warping function im_w = WarpImage(im, H) to check your result. 7Figure 7: Visualization of stereo match. function [disparity] = DenseMatch(im1, im2) Input: two gray-scale rectified images with uint8 format. Output: disparity map disparity ∈ RH×W where H and W are the image height and width.Compute the dense matches across all pixels. Given a pixel, u in the left image, sweep along its epipolar line, lu, and find the disparity, d, that produces the best match, i.e., d = arg min i kd 1 u − d 2 u+(i,0)k 2 ∀i = 0, 1, · · · , N where d 1 u is the dense SIFT descriptor at u on the left image and d 2 u+(i,0) is the SIFT descriptor at u+ (i, 0) (i pixel displaced along the x-axis) on the right image. Visualize the disparity map as shown in Figure 7.
1 Project Description A makefile is often used to simplify the compilation and build process of large software tools, via the GNU make [2] command. The software installation targets are primarily UNIX like operating systems. A typical makefile has the following structure [1] target: dependencies recipe(s) Given a makefile filename and an optional target as command line arguments, your task is to generate an executable ’mymake’, from a C program. It must parse the makefile and build a dependency graph for the (optional) provided target. Also, execute the recipes for the said target, by spawning a new process per recipe, via fork and exec, as determined by the graph traversal. If no target is specified as a command line argument, the first target in the makefile is chosen. Alternatively, if your first argument is a print flag (-p) followed by the makefile, you must only print the target, dependencies, and recipes in the makefile. A second type of flag (-r) followed by the makefile must print the recipe order of the target. Do not fork/exec the recipes when running either of the flags. More details are described in the following three phases: 1.1 Parsing the input makefile The makefile consists of multiple targets and each target describes the dependencies that must be satisfied before executing the recipes within a target. Recipes, rules, and commands mean the same thing. In this project makefile, each target can either have multiple dependencies with one recipe in a new line. Targets and dependencies are separated by a colon (:). Multiple dependencies for a target are separated by space. Each recipe for a target must be indented via a single tab (t, not 2/3/4/8 spaces). Recipes within the same target, must be executed in the order they appear. Blank lines are optional and improve readability. More assumptions about the file are presented later in the section 5 1 To simplify your job, we will provide a helper function that reads the contents of the makefile into a two dimensional char array. The first step is to parse these lines from a char array to accurately determine targets, dependencies, and recipes. We suggest adopting the technique described in makeargv.c from the textbook https://usp.cs.utsa.edu/usp/programs/chapter02/. One sample makefile is shown below: all : dep1 dep2 ls -l dep1: dep3 gcc -o file1.o -c file4.c file1.c dep2: gcc -o file3.o -c file3.c dep3: dep4 gcc -o file2.o -c file2.c dep4 : mkdir myproject The above makefile with no command line target, runs as ./mymake -p makefile in. It must print the target name, the dependency count and recipe count for each of the target in the Makefile. Output of one target can look like target ’all’ has 2 dependencies and 1 recipe Dependency 0 is dep1 Dependency 1 is dep2 Recipe 0 is ls -l Similarly, you must print the remaining 4 targets, their respective dependencies and recipes to get full credit for this phase. 1.2 Determining the order of recipes The makefile 1.1 when run with the recipe flag option, must print the order of recipes, such as running ./mymake -r makefile in on command line. It must pick all and look for recipes in the order – dep4, dep3, dep1, dep2. Finally, it prints the following lines: mkdir myproject gcc -o file2.o -c file2.c gcc -o file1.o -c file4.c file1.c gcc -o file3.o -c file3.c ls -l Running mymake -r makefilename will print all the recipes in order of execution, and no targets must be passed on the commandline. 2 1.3 Fork and exec the recipes. Using the data structures that model the graph, execute the recipes by forking a new process per recipe. Your program should determine which recipes are eligible to run, execute those recipes, wait for any recipe to finish, then repeat this process until all recipes finished executing. Instead, if a project is run with a specific target, say dep2, ./mymake makefile in dep2, your program must only print and then fork/exec one recipe: gcc -o file3.o -c file3.c 2 Implementation: We will provide an example framework to get started and examples to test the code. However, you are free to use your own implementation, without following the given structure. In the folder pa1, the src folder contains the code, test contains the test cases . The data structure used to store information about the target in desired ’container’ data structure looks like typedef struct target_block { char *name; //Target name char *depend[MAX_DEP]; // dependencies of target char *recipe[MAX_RECIPES_PT]; // recipes per target unsigned char dep_count; // number of dependencies in target unsigned char recipe_count; // number of recipes in target unsigned char visited; // used in DFS } target; The dependency graph uses the result of topological sort [3] – an application of Depth First Search algorithm. Given a set of targets, dependencies, and recipes, one must construct a directed graph by determining the nodes and edges as targets and dependencies, respectively. Alternatively, a less modular deisgn involves inserting the targets into a stack based on the DFS traversal, avoiding building a graph. 3 Execution: There are three ways to execute the project via $ ./mymake filename [target] $ ./mymake [-p] filename $ ./mymake [-r] filename Your executable can take upto two command line arguments. The filename argument is mandatory. If the optional arguments are provided, they must be in fixed positions. Any other variations must error out. 4 Testing As described in 2, to test your code against the provided test cases within the framework, run $ make -i test-main. The -i flag ignores the error return value and lets you test the whole suite. We 3 will use more tests cases than the ones provided. If you have not attempted extra credit, discussed later, you must modify the makefiles to suit your code. 5 Assumptions: To simplify the project, you can assume the following about the makefile: • The makefile is well formed and has no circular dependencies. • It doesnt use make variables (denoted via $), macros, or wildcards. • It can have a maximum of 128 lines and each line is upto 128 characters long • Each target can have upto 8 dependencies and one recipe. This assumption is relaxed, if you are attempting extra credit. • There can be no more than 128 targets in the makefile. Targets having 0 dependencies and 0 recipes, simulatenously, do not exist. However, targets with 0 recipes are possible. • Recipes do not spread across lines • We limit the executables to those found in default PATH environment of the CSELAB machines. Sample executables are Linux commands such as ls, cat, pwd, mkdir, or building an executable via gcc. • Each makefile has a single dependency tree. • You are free to make any reasonable assumptions not stated in this document, but do mention them early in your README file. 6 Extra credit: Unlike the makefile described earlier, one can specify multiple recipes for a target. Multiple recipes in different lines, within the same target, are executed in the order they are read. Recipes order within the same line are from left to right. Also, multiple recipes can be solved in parallel by separating them with a comma (,). For example, assume the following recipes in your makefile named makefile ec all : dep1 dep2 ls -l dep1: dep3 gcc -o file1.o -c file4.c file1.c dep2: gcc -o file3.o -c file3.c dep3: dep4 4 gcc -o file2.o -c file2.c gcc -o file4.o -c file4.c dep4 : mkdir myproject, pwd cat file1.c By executing this makefile with no targets as $ ./mymake makefile ec. The program must pick all and look for dependencies in the order — dep4, dep3, dep1, dep2. The recipes are executed as: mkdir myproject pwd cat file1.c gcc -o file2.o -c file2.c gcc -o file4.o -c file4.c gcc -o file1.o -c file4.c file1.c gcc -o file3.o -c file3.c ls -l For dep4, do not execute cat file1.c until both the previous commands finished executing. The parent must use wait system call on both the commands to avoid zombie process. If your group chooses to attempt the extra credit for an additional 10% of the project grade, you must correctly handle both parallel execution of recipes and multiple recipes per target, within the same program. 7 Deliverables: One student from each group should upload to Canvas, a zip file containing their C source code files, a makefile, and a README that includes the following details: • The purpose of your program • How to compile the program • What exactly your program does • Any assumptions outside this document • Team names and x500 • Your and your partners individual contributions • If you have attempted extra credit The README file does not have to be long, but must properly describe the above points. Proper in this case refers to – first-time user can answer the above questions without any confusion. Within your code you should use one or two comments to describe each function that you write. You do not need to comment every line of your code. However, you might want to comment portions of your code to answer why, rather than how you implement the said code. At the top of your README file and main C source file please include the following comment: 5 /*test machine: CSELAB_machine_name * date: mm/dd/yy * name: full_name1, [full_name2] * x500: id_for_first_name, [id_for_second_name] */ 8 Grading Rubric: 1. 10% Correct README contents 2. 10% Code quality such as using descriptive variable names, modularity, comments, indentation. You must stick to one style throughout the project. If you do not already have a style for C programming, we suggest adopting K&R style [4]. 3. 15% for using meaningful data structures and appropriate error checking and handling (a) 10% No program crashes or segfault (b) 5% uses appropriate data structures 4. 20% Parse the makefile accurately – determined via -p flag 5. 15% Implement the dependency graph algorithm for identifying recipe order – determined via -r flag 6. 30% Correctly call fork, exec, wait system calls not leading to fork bombs or zombie processes. 7. 10% Extra credit If your code passes the test cases, you will get 75% of the credit. The remaining 25% depends on the implementation quality and documentation, as described in points 1, 2 & 3b. 9 References: 1. Makefile rules: https://en.wikipedia.org/wiki/Makefile#Rules 2. GNU Make: https://www.gnu.org/software/make/manual/make.html 3. Topological sorting: https://en.wikipedia.org/wiki/Topological_sorting 4. K&R Style guide: https://en.wikipedia.org/wiki/Indentation_style#K&R_style 5. AND operator in make https://www.gnu.org/software/make/manual/make.html#ExecutionJeffrey Dean and Sanjay Ghemawat from Google published a research paper [1] in 2004, on a new programming model that can process very large datasets in an efficient, distributed manner. This programming model is called the “MapReduce”.The MapReduce consists of two main phases, Map and Reduce. In the ’Map’ phase, a user written map function is used to process input pairs to intermediate pairs. Then in the ’Reduce’ phase, a reduce function combines the intermediate pairs based on the keys to give the final output.Since the dataset input can be very large, there will be multiple map and reduce jobs and it is essential to maintain a synchronized system.Let us consider an example of counting the number of occurences of each word in a corpus of documents. The map function emits each word (key) it sees with a count ’1’ (value). The reduce function sums together all counts of emitted word by a particular word(key). The pseudocode for the same looks as below: map ( String key , String value ): // key : document name // value : document contents for each word w in value : EmitIntermediate (w ,”1″); reduce ( String key , Iterator values ): // key : a word // values : a list of counts int result = 0; for each v in values : result += ParseInt (v ); Emit ( AsString ( result )); The above example is taken from [1].In this project, we will mimic certain core functionalities of the MapReduce programming model using OS system calls. 1Concepts covered in this project. • Process spawning • Directory traversal • File I/O operations • Pipes • RedirectionGiven a folder with multi-level hierarchy, i.e., folders with multiple level of folders and text files. Each text file has a word per line. Your task is to count the number of words, per letter of the alphabet, i.e., compare the first letter of each word to increment the count corresponding to a letter, in the entire folder hierarchy.The result should be reported in the alphabetical order. Key parties involved in the project: • Master process – Parent process to all the spawned processes • Mapper processes – Executes the map function on the partitioned data. The number of mapper processes should be specified at the execution time as input argument • Reducer process – Executes the reduce function over the results from all the mapper process. For easiness, we have only a single reducer process for this project.There are four phases in this project. First is the data partitioning phase where the ’master’ will traverse through the folder hierarchy, identify all the files and split them equally among the mapper processes. During the second phase, the ’mappers’ will process the files alloted to them by the ’master’ and each of them will come up with a list of per letter word count. For the third phase, each ’mapper’ will send their list to the ’reducer’ process, who will combine them all to give a single list. In the last phase, the final list is then taken by the ’master’ and reported.Now let us have a look at the project implementation details. An example is provided for your understaning after the explanation of each phase. Notice: You may use any algorithm that will help you to reach the final goals. For each phase there is an expected output, unless otherwise specified. They should be in the format specified, i.e., if the results are to be stored as a text file with a specific name format in a folder with a specific name, you should follow it. !This phase aims at traversing the folder hierarchy and partitioning the files equally among the ’mapper’ processes. The ’master’ process creates a folder “MapperInput” in the current directory. It will then recursively traverses through the ’Sample’ folder hierarchy (assuming ’Sample’ is the relative or absolute, path of the folder that you passed to the executable) and divide the list of filepaths of text files with words, among ’m’ files of name format ’Mapper_i.txt’, where ’m’ is the number of ’mappers’ and i belongs to [1, 2, . . . , m]. The ’Mapper_i.txt’ should be created inside ’MapperInput’. You may use any partitoning logic that allows you to have almost same number of filepaths in each text file. For example, let there be 6 text files in ’Sample’ hierarchy and 3 mapper processes. Then each of the three ’Mapper_i.txt’ files created, will have 2 two file paths. In case the count of files is not a multiple of number of mappers, then add the extra files to ’Mapper_i.txt’ in a round robin fashion.Notice: Assume that the number of files is always greater than or equal to the number of mappers except for the case of empty folder. ! The expected outputs from this Phase are the “Mapper_i.txt” files inside “MapperInput” folder In Figure 1, ’Sample’ is the folder passed as input to your executable. F1, F2, . . . are the folders and Tfile*.txt are the text files with words. Figure 1: Data PartitioningThe master process creates ’m’ pipes, one per mapper to communicate with the reducer process. The master then spawns the mapper processes. Each mapper process will pick one file from the “MapperInput”, open each filepaths in the file and find the number of words corresponding to each letter of the alphabet. This information is then send to the reducer process via pipe by each mapper. Note to process the words as case-insensitive, i.e., take ’a’ and ’A’ as ’A’. No output is expected from this phase. The grading will be carried out based on the per letter word count algorithm, pipe setup and usage.In Figure 2, assume there are two file paths per ’Mapper_i.txt’. The ’Master’ process forks the ’mappers’. Mapper1 processes ’Mapper_1.txt’ and Mapper2 processes ’Mapper_2.txt’. Each mapper has a list with that keeps track of the per letter word count.Notice: Please do not assume that the process ids of mappers are [1, 2, . . . ]. It is upto to the OS to decide the process id. So there won’t be a one-to-one mapping between the names of text files and mapper process ids. ! 3 Figure 2: MapThe reducer process will receive the lists from each of the mapper processes via pipes and combine them to create a single list. The list is then written into a text file “ReducerResult.txt” in the current folder. Each line in the “ReducerResult.txt” will have the format as given below. There is only one space between ’letter_of_alphabet’ and ’wordcount’. letter_of_alphabet wordcount The expected output from this phase is the “ReducerResult.txt” In Figure 3, the ’reducer’ receives lists from Mapper1 and Mapper2 via two pipes. This list is then combined and written to ReducerResult.txt in the current folder. 4 Figure 3: Reduce 4.4 Phase 4 -Final Result The mapper processes will have exited by now. The ’master’ process will wait for the reducer to finish. It will then read the results from ’ReducerResult.txt and report it to standard output. But the catch here is that, the standard output is redirected to a file “FinalResult.txt” in the current folder. In MapReduce the ’master’ process exits towards the end after all the processes have completed. We are emulating that in this phase. The expected output from this phase is the FinalResult.txt which is having the same format as ReducerResult.txt In Figure 4, the ’master’ will redirect the results from standard output to ’FinalResult.txt’. Figure 4: Final Result 5 5 Execution The executable ’mapreduce’, for the project will accept 2 parameters Command Line $ ./mapreduce folderName #mappers folderName is the name of the root folder to be traversed #mappers is the number of mapper processes 6 Expected output • The Sample folder is empty or there are no files in the Sample hierarchy Command Line $ ./mapreduce Sample 4 The Sample folder is empty • The Sample folder has files in its hierarchy Command Line $ ./mapreduce Sample 4 The result is present in FinalResult.txt (below format) in the current folder A 5 B 10 C 3 . . . Z 12 7 Testing The results from the executable, ’mapreduce’, generated out of your program will be tested on folders of multiple levels. The number of files that will be present in the folders will range from ’m’ to 500, where ’m’ is the number of mappers. Note in case of empty folder, the file count will be zero. Notice: There will be an exact pattern matching algorithm used for grading the results obtained. So please be sure to adhere to the format. ! To test your code with the sample test folders, run Command Line $ make test-mapreduce Note that if you want to run explicitly on a test case, you will have to do it without the test-mapreduce target. Also, there is no auto-checking enabled for the correctness of result. The Expected_Output folder in Testcases have the expected output for each of the given test folders. 6 8 Assumptions • Number of masters = 1, 0 < Number of mappers = number of mappers except for the case of empty folder. • Only consider the file count for splitting data equally among mapper processes. Do not look at the size of the file. • Use C library file operations to read and write (FILE *, fgets, fputs, fscanf, fprintf and so on ) to and from a file in Phase 1, Phase 2 and Phase 3. • In phase 4, use OS system calls to do redirection from standard output to file. • Use pipes to communicate between Phase 2 and Phase 3. • The executable name should be ’mapreduce’, as specified in the makefile. • The template code consists of 4 phase*.c files. Add code of each phase as functions to corresponding files and call them from main.c. • Ensure to add the function prototypes to corresponding phase*.h files in ’include’ folder. • You are expected to provide proper guard mechanisms for header files. • Ensure proper error handling mechanisms for file operations and pipe handling. • Expect empty and multilevel folder hierarchies. 9 Extra credit Symbolic link or soft link is a kind of file that points to another file name. This can be extended to directories as well. Refer to [4] for more details. Consider the following example Folder1/file1.txt ——> Folder5/file6.txt ====> physical data Here file1.txt in Folder1 is a symbolic link for file6.txt in Folder5. One can interchangeably use file1.txt and file6.txt to read and write from the same physical location in the memory. The same can apply to directories. In Phase 1, there can be folders or files that are symbolic links. Your task is to identify such folders/files and avoid reprocessing them. You may assume that all the symbolic links are valid. To test this scenario with your code run Command Line $ make test-extracredits If you are attempting extra credits, mention it in the README file 10 Deliverables One student from each group should upload to Canvas, a zip file containing their C source codefiles, a makefile, and a README that includes the following details: • The purpose of your program • How to compile the program 7 • What exactly your program does • Any assumptions outside this document • Team names and x500 • Your and your partners individual contributions • If you have attempted extra credit The README file does not have to be long, but must properly describe the above points. Proper in this case refers to – first-time user can answer the above questions without any confusion. Within your code you should use one or two comments to describe each function that you write. You do not need to comment every line of your code. However, you might want to comment portions of your code to answer ‘why’, rather than ‘how’ you implement the said code. At the top of your README file and main C source file please include the following comment: /* test machine : CSELAB_machine_name * date : mm / dd / yy * name : full_name1 , [ full_name2 ] * x500 : id_for_first_name , [ id_for_second_name ] */ 11 Grading Rubric 1. 10% Correct README contents 2. 10% Code quality such as using descriptive variable names, modularity, comments, indentation. You must stick to one style throughout the project. If you do not already have a style for C programming, we suggest adopting K&R style [5]. 3. 15% Proper error handling and data structure usage 4. 15% Data partitioning and file operations 5. 20% Process handling 6. 30% Pipe communication and redirection 7. 10% Extra credit If your code passes the test cases, you will get 75% of the credit. The remaining 25% will be 1, 2 and proper data sructure usage. References [1] Dean, J. and Ghemawat, S., 2008. MapReduce: simplified data processing on large clusters. Communications of the ACM, 51(1), pp.107-113. [2] Kay, A. R.,Robbins, S., 2004. Chapter 6 – Unix Systems Programming: Communication, Concurrency And Threads, 2/E. Pearson Education India. [3] Kay, A. R.,Robbins, S., 2004. Chapter 4 – Unix Systems Programming: Communication, Concurrency And Threads, 2/E. Pearson Education India. [4] Symbolic links https://www.gnu.org/software/libc/manual/html_node/Symbolic-Links.html [5] K&R Style https://en.wikipedia.org/wiki/Indentation_style#K&R_styleIn multi-threads programming, threads can perform the same or different roles. In some multithreading scenarios like producer-consumer, producer and consumer threads have different functionality. In other multithreading scenarios like many parallel algorithms, threads have almost the same functionality.In this programming assignment, we want to work on both sides in problem “word count statistics”, which is the multithreaded version of MapReduce application in programming assignment 2. An example problem is shown in Fig. 1 below. A text file contains several lines of English characters, and this application will count the histogram of the starting letter for each word. Fig. 1, an example of “word count statistics”One idea to solve this problem is to cut the file into smaller pieces and hand it over to many workers. Then in this programming assignment, we will use multithreading to create a producer to read the file and multiple consumers to process the smaller piece data. We will have two forms of synchronization: a shared queue synchronized between producer and consumers, and a global result histogram synchronized by consumers.In multithreading “word count statistics” application, the program contains: a master thread, one producer thread and many consumer threads (shown in Fig. 2 below). The producer and consumers will share a queue for data transfering. For program execution flow, the entire program contains 4 parts: 1) the master thread initializes the shared queue, result histogram, producer thread and consumer threads; 2) the producer thread will read the input file, cut the data into smaller pieces and feed into the shared queue; 3) the consumers will read from the shared queue, compute the “word count statistics” for its data pieces and synchronize the result with a global histogram; 4) after producer and all consumers complete their work, the master thread writes the final result into the output file.Fig. 2, 4 parts of multithreading “word count statistics” In the next section, we will go through the implementation details of this project. The implementation requirements will be provided.Before we go into each part, the application comparison between PA2 (Programming Assignment 2) and PA3 (Programming Assignment 3) needs to be clarified. Even though we use the same application “word count statistics” in PA2, there are several key differences in the input file and processing flows: 1) PA2 works on different files located in different directories, but PA3 takes only one file as your input file. 2) In PA2, each file contains multiple lines and each line contains only one word. But PA3’s input file is more “natural” , which contains multiple words in each line and the file contains multiple lines. 3) PA2 uses multi-processing, which means the parent forks several children and seperate the workload. But in PA3, you only have one process but multiple threads . PA3 is mainly focused on the usage of threads and thread-safe data structures.The core of this multithreading “word count statistic” application is a thread-safe shared queue. This shared queue should be implemented as a linked-list unbounded buffer . The producer inserts the data in the tail of the linked-list and the consumer extracts the data from the head. Also, it should be implemented in a non-busy-waiting way (use “mutex lock + conditional variable” or “semaphore”).In this stage, the program needs to check the input arguments and print error messages if argument mismatch (see Section 6 execution for arguments). Then it should perform the initialization on data structure and launch the producer/consumers thread. Then the master will wait for all threads to join back (4.4 Master Finalize).The main functionality of the producer thread is to read the input file and pass the data into the shared queue (by a package). The file is required to be read by line granularity (one line at a time), thus each consumer will work on one line at a time. Since there are multiple consumers, if the EOF is reached, the producer should send notifications to consumers specifying there will be no more data. The producer terminates after sending those notifications. Note that the package is the information transferred between producer/consumers via shared queue. It should contain the data for consumers and other information if needed.The consumer will repeatedly check the queue for a new package, work on it for word count statistics , and then go back to get the next package. This will continue until receiving the EOF notification, then it will terminate. Besides package handling, it’s the consumer’s responsibility to synchronize the result with the global final histogram. Then after all consumers finish their work, the master thread could summarize it and generate the output.The word count statistics will check the beginning character of a word. The definition of a word is a continuous a-zA-Z character (shown in Fig. 3 below). Note that, all other characters are treated as space. The characters like “-”, “_” are not connecting words. Same as PA2, we don’t differentiate between uppercase and lowercase letters. Fig. 3, the word count statistics functionAfter the producer and consumers have joined back, the master thread will write the final result (global histogram) into the output file named “result.txt” . The output format should be: “%c: %d ” , and it will loop through the global histogram from ‘a’ to ‘z’ (shown in Fig. 4 below). Fig. 4, the output file format4.5 Log Printout The program will also print a log file if the argument option is specified . The log file should be named as “log.txt” . The producer and consumers should print their execution information into the log: Producer: 1. Print “producer ” when the producer is launched 2. Print “producer: %d ” for the current line number (starts from 0) Consumer: 1. Print “consumer %d ” when launched, with the consumer id (0 to number of consumers minus 1) 2. Print “consumer %d: %d ” for the consumer id and the line number it currently works on. There are some other notes when writing the log: – The print library functions are usually thread-safe, so you don’t need to use a lock or worry about messy printing (unless you meet that). – Since the execution order of threads is nondeterministic, you usually will not get a stable log print out. – EOF notification should be printed out as line number “-1”.5. Extra Credits The extra credits will be granted if a bounded buffer shared queue is implemented. The application could choose the unbounded/bounded buffer by the commandline argument option. Also the bounded buffer should have a configurable buffer size specified by commandline argument option.6. Execution Syntax, Options The “word count statistic” will take the arguments syntax: $ ./wcs #consumer filename [option] [#queue_size] – The second argument “#consumer” is the number of consumers the program will create. – The third argument “filename” is the input file name – Options have only three possibilities: “-p”, “-b”, “-bp”. 1) “-p” means printing, the program will generate log in this case. 2) “-b” means bounded buffer (extra credit), the program will use it instead of unbounded buffer. 3) “-bp” means both bounded buffer and log printing. – The last option argument is the queue size if using bounded buffer (extra credits). 7. Testing There will be 4 testing files in the “testing” folder, each of them has different scenarios specified in the first line of testfile. Also, the solution for 4 test files is contained in the “testing/sol” folder. 8. Assumptions and Hints – One line of input file has at most 1024 chars. – You are allowed to use library file IO functions (instead of open/read/write syscall). – Use the keyword “extern” in the header file for the global variable consistency. – Check if the library function is thread-safe before using them (if you use them in concurrent threads scenario). 9. Submission *(this section is modified from Programming Assignment 2 document) One student from each group should upload to Canvas, a zip file containing their C source files, a makefile, and a README that includes the following details: – Team names and x500 – How to compile the program – Your and your partner’s individual contributions – Any assumptions outside this document – What exactly your program does – If you have attempted extra credit The README file does not have to be long, but must properly describe the above points. Your source code should provide appropriate comments for functions and critical code sections (like the purpose of these code and logical execution flow). At the top of your README file and each C source file please include the following comment: /*test machine: CSELAB_machine_name * date: mm/dd/yy * name: full_name1 , [full_name2] * x500: id_for_first_name , [id_for_second_name] */ 10. Grading Policy 1. (5%) correct README content 2. (5%) appropriate code style and comments 3. (40%) passed all tests (there may be some other tests when grading) 4. (15%) correct shared queue data structure and functions (like insert, extract, non-busy-waiting, and etc. ) 5. (5%) correct thread create and join usage 6. (10%) correct global histogram usage (like synchronization) 7. (10%) correct producer functionality 8. (10%) correct consumer functionality 9. (10%) extra credit: bounded bufferSocket programming is a way of connecting two nodes (sockets) on a network to communicate with each other. One node (Server socket) listens on a particular IP address and port number, while other nodes (Clients sockets) reaches out to the server socket to build a connection.Through the programming assignment 4 (PA4), you will extend the word counting application of programming assignment 2 (PA2) using the socket programming. Similar to PA2, there will be a master process, multiple mapper processes, and a single reducer process. However, for communication, you will use socket-based TCP connections instead of pipes as shown in Figure 1 and Figure 2. 3.In PA4, you will make two executables (two separate independent programs), server program and client program. Master process is the main process of the client program. Master process spawns multiple mapper processes similar to PA2. Reducer process is the main process of the server program.Note that the reducer process is no longer spawned by the master process. The reducer process spawns a thread whenever it establishes a new TCP connection with a client. It is called a multi-threaded server. Server, Reducer and Reducer process are interchangeably used in this document. The client program has two types of clients – Master clients and Mapper clients. Master process and mapper processes can be a client. Master client implementation is extra credit.Details of master client can be found in the section 5. Extra credit. Now, Let’s fist focus on the mapper clients. Each mapper process initiates a TCP connection to the server. Once the connection is established, the mapper client sends deterministic requests, a fixed set of requests, to the server. Mappers, Mapper clients, and Master’s child processes indicate the same thing.The relationship of client processes and server threads are shown in Figure 2. < Figure 1: Process relationship of programming assignment 2 > < Figure 2: Process and thread relationships of programming assignment 4 > 3.1 The server program The server program is a multi-threaded server. The server is responsible for listening and building connections from clients. The server waits for connections on the specified port. When it receives a connection, it should spawn a new thread to handle that connection.A thread is responsible for handling requests from a client by reading client’s messages from a socket set up between them, doing necessary computation (refer to section 4. Communication Protocol) and sending responses to the client back through the socket. The thread should exit after it close the client connection. < Figure 4: Information and data structure the server maintains > Server maintains two important lists – azList and updateStatus. azList is a 1-D integer list and updateStatus is a 2-D integer list, as shown in Figure 4.The server saves the sum of all the word count results from mapper clients in the azList. updateStatus table has 3 essential attributes – MapperID, Number of updates, check in/out flag. A new entry of the updateStatus table is created when the server receives a CHECKIN request from a new mapper client (refer to the details of request commands in section 4.1 Request).You can feel free to add more columns to the table if needed. Table 1: Attributes of updateStatus Table Attribute Name E MapperID Unique mapper ID, which is greater than 0 Number of updates Incremented by 1 when receiving an UPDATE_AZLIST request from a mapper client. The value should be the same with the number of files the mapper client processes. Check In / out flag 1 – When a mapper client is checked in. 0 – When a mapper client is checked out. 3.2 The client program Client program is responsible for initiating a connection with the server on the IP address and port number given to it. It consists of 3 phases. [ Phase 1 ] File Path Partitioning – By Master Client This is exactly the same with phase 1 of PA2. You are given the codes (phase1.c and phase1.h) for phase1. This code will generate a folder “MapperInput” and “Mapper_.txt” socalled mapper files in the folder. The mapper files contain a list of file paths. MapperID starts from 1 and increments by 1. Please refer to the PA2 write-up for further details of phase 1. [ Phase 2 ] Deterministic Request Handling – By Mapper Clients Master process assigns a unique mapperID to mapper processes while it spawns mapper processes.The mapper ID starts from 1, and increments by 1. Mapper processes run in parallel. Each mapper client sets up a TCP connection to the server, and sends the following a fixed set of requests sequentially in a deterministic manner. A TCP connection is used to send all the following requests. Mapper clients can access their own mapper file in MapperIntput folder. 1. CHECKIN 2. UPDATE_AZLIST (If the mapper client has multiple file paths in its mapper file, this request is sent to the server multiple times. For example, Mapper_1.txt contains 10 lines of file paths, the mapper client sends 10 UPDATE_AZLIST requests to the server with the word count result of each file. 3. GET_AZLIST 4. GET_MAPPER_UPDATES 5. GET_ALL_UPDATES 6. CHECKOUT For mapper clients to send any requests to the server, they should be checked in first. After check-in, they can send the other types of requests to the server. After exchanging the messages with the server, they should check out, close the TCP connection, and exit. Master waits until all mapper processes are terminated. You can find details of requests in section 4. [ Phase 3 ] Dynamic Request Handling – By Master Clients Phase 3 is extra credit. You will add the master client functionality. After the master process should make sure all mapper processes are terminated, it sends any requests dynamically by reading commands from a file named “commands.txt”. It uses separate TCP connections to send the requests.You can find the details in Section 5. Extra Credits. 4. Communication Protocol Communication protocol is an application-layer protocol formed of requests and responses. Both requests and responses are integer arrays. Requests are sent from the client, received by the server. After the server does necessary computation, it responds to clients. You can find the details of the requests and responses in the section. 4.1 Request The request structure is as follows. You can find the relevant definitions in the given protocol.h. You can use them in your implementation. Table 2: Request Structure Field Name Size (# of Integer) Purpose Request Command 1 Specifies request command MapperID 1 Specified mapperID (-1 for master client) Data 26 Relevant data for the command. If there is no data, fill with zeros Table 3: Request Command Codes Request Command Command Name Data Request permission (Who can send) 1 CHECKIN Zeros Mapper clients 2 UPDATE_AZLIST Word count result of a file Mapper clients 3 GET_AZLIST Zeros Mapper clients Master clients (extra credit) 4 GET_MAPPER_UPDATES Zeros Mapper clients 5 GET_ALL_UPDATES Zeros Mapper clients Master clients (extra credit) 6 CHECKOUT Zeros Mapper clients Details of each request are as follows. ● 1. CHECKIN o [Client] Mapper clients should send this request before sending other types of requests. o [Server] Server creates a new entry in updateStatus table for a new mapper client if corresponding entry does not exist in the table. If there is an existing entry in the table, the server simply changes the check in/out field to checked-in (1). ● 2. UPDATE_AZLIST o [Client] Mapper clients send it to the server with PER-FILE word count results. If there are multiple file paths in the mapper file, this request should be sent as many as the same number of files paths. If there is no files in the mapper file, mapper clients SHOULD NOT send this message. o [Server] Server sums the word count results in the azList, and increases the number of update field of updateStatus table by 1 for the corresponding mapper client. The number of updates of a particular mapper client should be the same with the number of files paths in the mapper’s mapper file. ● 3. GET_AZLIST o [Client] These requests can be sent by both mapper clients and master clients (extra credit). If mapper clients want to send this request to the server, they should be already checked in. On the other hand, master clients can send it without check-in (extra credit).. o [Server] Server returns the current values of the azList ● 4. GET_MAPPER_UPDATES o [Client] Only mapper clients can send this request. They should be already checked in. o [Server] Server returns the current value of “number of updates” field of updateStatus table for the corresponding mapper ID. ● 5. GET_ALL_UPDATES o [Client] These requests can be sent by both mapper clients and master clients (extra credit). If mapper clients want to send this request to the server, they should be already checked in. On the other hand, master clients can send it without check-in (extra credit). o [Server] Server returns the sum of all values of “number of updates” field in the updateStatus table. ● 6. CHECKOUT o [Client] This request is the last request sent from a mapper client. After getting a response, the mapper client closes its TCP connection and terminates its own process. o [Server] Server updates check in/out field of theupdateStatus table to checked-out (0). 4.2 Response The response structure is as follows. You can find the relevant definitions in the given protocol.h. You can use them in your implementation. Table 3: Response Structure Field Name Size (# of Integer) Purpose Request code 1 Specifies type of request Response code 1 Specified response code Data 1 or 26 Relevant data from server Table 4: Response Code Response Code Meaning Purpose 0 RSP_OK Success For successful requests 1 RSP_NOK Error For unsuccessful requests Table 5: Data Returned on Success Request Command Request Name Data Returned 1 CHECKIN 1 value (mapperID) 2 UPDATE_AZLIST 1 value (mapperID) 3 GET_AZLIST 26 word count values (azList values) at that moment the request is received regardless of mapperID 4 GET_MAPPER_UPDATES 1 value (The value of the number of updates field of updateStatus table for the corresponding mapperID) 5 GET_ALL_UPDATES 1 value (Sum of all entries of the number of updates field in the updateStatus table) 6 CHECKOUT 1 value (mapperID) Servers should handle various error cases such as: – When receiving a request with unknown request code – When mapper ID is not greater than zero – When there is no corresponding entry in the updateSatus table – When a mapper client sends CHECKIN request, if it is already checked-in. – When a mapper client sends CHECKOUT request, if it is not checked-in. – Handling request permission etc. 4.3 Log Printout The server program prints the following logs in terminal. The client programs print the following logs in a log file “log_client txt” in the “log” folder. (refer to section 6. Folder Structure). Please stick closely to this output format. The following items are minimal requirements to print, so you can print additional logs or messages for failure cases. In addition, you can use a function createLogFile() to initialize a client log file in the client.c. You can find example logs in the PA4_Appendix document, and other expected outputs and logs in the “Testcases/ExpectedResult” folder. ● When the server is ready to listen. ○ [Client] None ○ [Server] Print “server is listening ”. ● Establish a TCP connection between a client and server. ○ [Client] Print “[%d] open connection ”, mapperID. ○ [Server] Print “open connection from %s:%d ”, client_ip, client_port. ● Close the TCP connection between a client and server. ○ [Client] Print “[%d] close connection ”, mapperID. ○ [Server] Print “close connection from %s:%d ”, client_ip, client_port. ● 1. CHECKIN ○ [Client] Print “[%d] CHECKIN: %d %d ”, mapperID, Response Code (response[1]), Data (response[2]) ○ [Server] Print “[%d] CHECKIN ”, mapperID (request[1]) ● 2. UPDATE_AZLIST ○ [Client] Print “[%d] UPDATE_AZLIST: %d ”, mapperID, Total number of messages sent to server. Print out this log after a mapper client sends all UPDATE_AZLIST requests to the server. ○ [Server] None ● 3. GET_AZLIST ○ [Client] Print “[%d] GET_AZLIST: %d ”, mapperID, Response Code (response[1]), and all data received from the server (26 numbers) in the same line (1 space between numbers) ○ [Server] Print “[%d] GET_AZLIST ”, mapperID (request[1]) ● 4. GET_MAPPER_UPDATES ○ [Client] Print “[%d] GET_MAPPER_UPDATES: %d %d ”, mapperID, Response Code (response[1]), Data (response[2]) ○ [Server] Print “[%d] GET_MAPPER_UPDATES ”, mapperID (request[1]) ● 5. GET_ALL_UPDATES ○ [Client] Print “[%d] GET_ALL_UPDATES: %d %d ”, mapperID, Response Code (response[1]), Data (response[2]) ○ [Server] Print “[%d] GET_ALL_UPDATES ”, mapperID (request[1]) ● 6. CHECKOUT ○ [Client] Print “[%d] CHECKOUT: %d %d ”, mapperID, Response Code (response[1]), Data (response[2]) ○ [Server] Print “[%d] CHECKOUT ”, mapperID (request[1]) 5. Extra Credits You can get extra credits by implementing the master client’s dynamic request handling (Phase3 of client program). Unlike the deterministic request handling by mapper clients, the master client dynamically sends requests by reading request commands from a command file named “commands.txt”. The master client initiates a new TCP connection to the server after it makes sure all mapper processes are terminated. When the master client sends a request, the mapperID field of the request should be set to -1. Requests from master client does not require check-in and check-out unlike mapper clients, so master client should set up a new TCP connection for each request, and close after getting a response. For example, if you use the following commands.txt, server will get successful response only for the request commands 3 (GET_AZLIST) and 5 (GET_ALL_UPDATES). For other request, it will get unsuccessful responses from the server. You can assume that 2 (UPDATE_AZLIST) doesn’t appear in the commands.txt. 1 3 4 5 6 7 < example commands.txt file > < Figure 5: Extra Credit – Master Client > 6. Folder Structure Please strictly conform with the folder structure. The conformance will be graded. You should have two project folders named “PA4_Client” and “PA4_Server”. “PA4_Client” should contain “include”, “src”, “log”, “Testcases”, and “MapperInput” folders. “PA4_Server” should contain include” and “src”. You can feel free to modify the provided Makefiles. ● “include” folder: All .h header files ● “src” folder: All .c source files ● “log” folder: log_client.txt. ● “Testcases” folder: 5 TestCase folders and ExpectedResult folder are provided for your testing. Your program will be tested with additional hidden TestCases. THe TestCases are located in this folder. Please DO NOT include this folder in the final deliverable. ● “MapperInput” folder: This folder is created as part of phase1 of the client program. Please do not include this folder in the final deliverable. ● Each top folders (“PA4_Client” and “PA4_Server”) should contain the following files. ○ Makefile ○ executable ○ commands.txt (only in PA4_Client if you attempt extra credit) 7. Execution Syntax The usage of your server program is as follows. The executable name should be “server”. ./server ● is any unsigned integer to be used as a port number The usage of your client program is as follows. The client executable name should be “client”. ./client ● the name of the root folder to be traversed. ● the number of mapper processes spawned by master. ● IP address of the server to connect to. ● port number of the server to connect to. 7. Assumptions and Hints – You should use TCP sockets. – Maximum number of mapper clients per a master client is 32. – Maximum number of concurrent connections at the server side is 50. – Mapper IDs should be greater than zero, and unique in a client program. – A client connects to a single server at any time. – A server considers multiple client requests at a time. – The server program is not terminated unless it is killed by a user. – Requests and response messages are integer arrays. – Given phase1 code handles symbolic folders and files. – Your server will get any types of requests including both successful and unsuccessful requests, so you need to handle various errors at the server side. – Commands.txt file contains any integers (>0) except for 2. – Start to work on a local host for both client and server programs, then try it on multiple machines later. 8. Submission One student from each group should upload to Canvas, a zip file containing the two project folders (“PA4_Client” and “PA4_Server”) and a README.md that includes the following details: – Team names and x500 – How to compile the client and server programs – How to run the client and server programs – Your and your partner’s individual contributions – Any assumptions outside this document – If you have attempted extra credit The README.md file does not have to be long, but must properly describe the above points. Your source code should provide appropriate comments for functions. At the top of your README.md file and each C source file please include the following comments: /*test machine: CSELAB_machine_name * date: mm/dd/yy * name: full_name1 , [full_name2] * x500: id_for_first_name , [id_for_second_name] */ 9. Grading Policy 1. (5%) Correct README content 2. (5%) Appropriate code style and comments 3. (10%) Conformance check a. (5%) Folder structure and executable names b. (5%) Log format for client logs and server logs 4. (30%) TCP connection setup between clients and server a. (10%) Set up a TCP connection between mapper client and the server b. (10%) Use threads at the server side c. (10%) Set up multiple TCP connections between mappers and the server 5. (30%) Deterministic requests handling between Mapper clients and the server a. (15%) Mapper client side b. (15%) Server side 6. (10%) Error Handling 7. (10%) Successful executions of client and server programs in different machines. 8. (10%) Extra credit – Master client’s dynamic request handling a. (5%) Set up a TCP connection between master client and the server b. (5%) Read request commands, and process send and receive the commands
1. Install Standard ML of New Jersey to your computer 2. Write/Run SML functions on Standard ML of New Jersey Interactive System 3. Write the SML functions in a text editor, then run the code on Standard ML of New Jersey Interactive System1. Write a function cube of type int ! int that returns the cube of its parameter 2. Write a function sqsum of type int ! int that takes an non-negative integer n and returns the sum of the squares of all the integers 0 through n. Your function need not behave well on negative input.3. Write a function max of type int list ! int that returns the largest element of a list of integers. Your function need not behave well if the list is empty. (refer to exercise 13 on page 85 of the textbook)Step One: Install Standard ML of New Jersey to your computer. To install on Window, please watch the video https://www.youtube.com/watch?v=hDkG2aH2iqU To install on Mac, you may watch the video at https://youtu.be/qdUnCK85CoIStep Two: Write all functions in a text editor and save the file as YourNameProjOne.sml.Step Three: Run your code and test the correctness with data Open terminal window. Use command ls see the folders/files in current folder. Use command cd .. to go into upper level folder. Use command cd folder_name to go to the subfolder. Navigate to the folder where you saved YourNameProjOne.sml file. Now type command: smlThen type command: use “YourNameProjectOne.sml” The file name must be in “ “. If everything is correct, your functions are ready to use. Sample Run on My Computer: my file was saved as CSCI461ProjOne.sml in folder Documents/CSCI461VA/Project. The file name is: CSCI461ProjOne.sml. It contains the following code: (* this is problem one *) fun cube x = x*x*x; (* this is problem two *) fun cube2 x:real = x*x*x; Here (* … *) are comments Here is the screen shot for what I have done: The due date will be announced on Blackboard.Write a quick sort function of type int list -> int list. Here is a review for quick sort algorithm. First pick an element and call it pivot. (The head of the list is an easy choice for the pivot.) Partition the rest of the list into two sublists, one with all the elements less than the pivot and another one with all the elements not less than the pivot. Recursively sort the sublists. Combine two sublists and pivot into final sorted list.The solution must follow the style of function merge sort on page 114. The help functions must be made inside let.Sample Run: Please see the screen shot below to see the sample run File to turn in: Save your function in file names YourNameProjTwo.sml and submit it via blackboard link. Due Date: Will be announced on blackboard.1. Apply the concepts of folding 2. Apply the concepts of map 3. Implement mymap which works as built-in map function in sml 4. Apply foldr, foldl, and mymap to solve some problem in on line of codeThe student shall turn in five functions. You should use mymap1 and mymap2 in problem 3, 4, and 5 if it is needed. However, the best way to do so is you use built-in map to finish problem 3, 4, and 5 first. After they work, replace map with mymap1 or mymap2. If they still work, you can say that you implement them all correctly. If it doesn’t work, then you now that your mymap1 or mymap2 maybe incorrect.1. Define a function mymap1 with the same type and behavior as built-in map function but without using map. This should be one-line of code. Use foldr or foldl) (refer to problem Exercise 24 on page 147)2. Define a function mymap2 with the same type and behavior as map. No map, foldr, or foldl can be used. (refer to problem Exercise 26 on page 147)3. Write a function ordlist of type char list -> int list that take a list of characters and returns the list of integer codes of those characters. For example, if you evaluate ordlist [#”A”, #”b”, #”C”] you should get [65, 98, 67] (refer to Exercise 2 on page 144)4. Write a function mylength fo type ‘a list -> int that returns the length of a list. You cannot use the built-in length function. (refer to Exercise 11 on page 145)5. Write a function max of type int list -> int that returns the largest element of a list of integers. Your function need not behave well if the list is empty.Sample Run: Please see the screen shot on next page Due Date: The file need to be submitted through blackboard link on time. The file name should be YourNameProjThree.sml. Due date will be announced on blackboard.• Write data constructor with parameters • Write type constructor with parameters • Write recursively defined type constructorsThe student shall turn in definition of mylist and three functions to handle mylist. In YourNameProjFour.sml file, the student needs to write the following type and functions1. Define mylist type that is the same as the one on page 172 of the textbook. 2. Define a function prod that returns the product of all integers in a mylist of integers. (refer to problem Exercise 6 on page 178)3. Write a function append of type ‘a mylist -> ‘a mylist -> ‘a mylist that takes two mylist values, a and b, and return a mylist contains all the values in a followed by all the values in b. (refer to Exercise 8 on page 178)4. Write a function reverse of type ‘a list -> ‘a list that takes a mylist x and return a mylist of all elements of x, in a reverse order. (refer to Exercise 7on page 178)Please see the screen shot on next page. Please notice how infixr 5 is used. (Refer to examples on page 174). Also please notice that the result list may not fully displayed. For instance, for list with element 1, 2, 3, 4, 5, it may only display as 1 CONS 2 CONS 3 CONS # CONS # Due Date: The file needs to be submitted through blackboard link on time. The file name should be YourNameProjFour.sml. Due date will be announced on blackboard.Please note that the students need to answer the following two questions: 1. How many solutions does it print? 2. How many of them are distinct?Then the student need to modify the program so that only the distinct solutions will be print out. Instruction on how to write and run the SWI-Prolog program: Step One: Write your program using any text editor. Save the program as YourNameProjFive.swiplStep Two: Open terminal window. Use cd command to navigate to the folder where you saved your project four program.Step Three: Type swipl. The SWI-Prolog program will runStep Four: Type consult(‘YourNameProjFour.swipl’). (must have period at the end)Step Five: Tyep length(X, 7), solution([w, w, w, w], X). (end with period) Use the semicolon after each solution to make it print them all.Add the following features to the adventure game from chapter 20 of the textbook.1. There is a gate between the fork in the path and the mountaintop. The gate is a separate location; that is, the player must move from at (you, fork) to at (you, gate) and then to at (you, mountaintop).2. To move forward through the gate, the player must first unlock it with a key.3. The key is somewhere in the maze. The player must find it and explicitly pick it up4. If the player tries to pass through the gate while still holding the key, he or she is killed by lightning. (To get the treasure, the player must first open the gate, then put down the key and then pass through)Start from the code in this chapter, which is copied below (it is also on this book’s web site. A link is provided in this module’s folder). Part of your implementation should be a general way for the player to pick thing up, carry them, and put them down. Design your solution so that it would be easy to add additional objects for the player to pick up and put down./* This is a little adventure game. There are three entities: you, a treasure, and an ogre. There are six places: a valley, a path, a cliff, a fork, a maze, and a mountaintop. Your goal is to get the treasure without being killed first.*/ /* First, text descriptions of all the places in the game. */ description(valley, ‘You are in a pleasant valley, with a trail ahead.’). description(path, ‘You are on a path, with ravines on both sides.’). description(cliff, ‘You are teetering on the edge of a cliff.’). description(fork, ‘You are at a fork in the path.’). description(maze(_), ‘You are in a maze of twisty trails, all alike.’). description(mountaintop, ‘You are on the mountaintop.’). /* report prints the description of your current location. */ report :- at(you,X), description(X,Y), write(Y), nl. /*These connect predicates establish the map. The meaning of connect(X,Dir,Y) is that if you are at X and you move in direction Dir, you get to Y. Recognized directions are forward, right, and left.*/ connect(valley,forward,path). connect(path,right,cliff). connect(path,left,cliff). connect(path,forward,fork). connect(fork,left,maze(0)). connect(fork,right,mountaintop). connect(maze(0),left,maze(1)). connect(maze(0),right,maze(3)). connect(maze(1),left,maze(0)). connect(maze(1),right,maze(2)). connect(maze(2),left,fork). connect(maze(2),right,maze(0)). connect(maze(3),left,maze(0)). connect(maze(3),right,maze(3)). /* move(Dir) moves you in direction Dir, then prints the description of your new location. */ move(Dir) :- at(you,Loc), connect(Loc,Dir,Next), retract(at(you,Loc)), assert(at(you,Next)), report, !. /*But if the argument was not a legal direction, print an error message and don’t move. */ move(_) :- write(‘That is not a legal move. ’), report. /* Shorthand for moves. */ forward :- move(forward). left :- move(left). right :- move(right). /*If you and the ogre are at the same place, it kills you. */ ogre :- at(ogre,Loc), at(you,Loc), write(‘An ogre sucks your brain out through ’), write(‘your eye sockets, and you die. ’), retract(at(you,Loc)), assert(at(you,done)), !. /*But if you and the ogre are not in the same place, nothing happens. */ ogre. /* If you and the treasure are at the same place, you win. */ treasure :- at(treasure,Loc), at(you,Loc), write(‘There is a treasure here. ’), write(‘Congratulations, you win! ’), retract(at(you,Loc)), assert(at(you,done)), !. /*But if you and the treasure are not in the same place, nothing happens. */ treasure. /* If you are at the cliff, you fall off and die. */ cliff :- at(you,cliff), write(‘You fall off and die. ’), retract(at(you,cliff)), assert(at(you,done)), !. /* But if you are not at the cliff nothing happens. */ cliff. /* Main loop. Stop if player won or lost. */ main :- at(you,done), write(‘Thanks for playing. ’), !. /* Main loop. Not done, so get a move from the user and make it. Then run all our special behaviors. Then repeat. */ main :- write(‘ Next move — ‘), read(Move), call(Move), ogre, treasure, cliff, main. /* This is the starting point for the game. We assert the initial conditions, print an initial report, then start the main loop. */ go :- retractall(at(_,_)), % clean up from previous runs assert(at(you,valley)), assert(at(ogre,maze(3))), assert(at(treasure,mountaintop)), write(‘This is an adventure game. ’), write(‘Legal moves are left, right, or forward. ’), write(‘End each move with a period. ’), report, main.
For this assignment, you will use bash create a simple course catalog for administrators to update the details of each course offered by their department. The system will store basic information about each course, allowing the user to create, read, update, and delete them. This assignment requires only the utilities used so far in the lecture notes. Do not use sed, awk, or any programming languages or utilities not yet covered in the lecture notes. Tip: Filenames in the native Linux filesystem are case-sensitive. Thus, without proper consideration, a course whose associated filename was created as cs3423.crs (based on lowercase input given for the course’s department code the time of its creation) will not also be associated with the file CS3423.crs. This is not desirable behavior, however, as user’s may unexpectedly enter either uppercase or lowercase department codes when using your script. Therefore, you may utilize a bash feature (known as “case modification” parameter expansion) that enables you to easily convert the contents of a variable to its uppercase equivalent. For example, this feature can be utilized to produce the capitalized contents of the variable containing a department code by simply writing ${dept_codeˆˆ} instead of $dept_code when building the filename you will use for a particular course. Tip: Note, that when prompted to enter a department code and course number, you should enter these values as two separate tokens separated by a space. Otherwise, it would be necessary to perform complex token-splitting to separate these values, which is outside the scope of this assignment. For example, when prompting the user: Enter a department code and course number: You should enter “cs 3423”, not “cs3423”! Storing Course Information Course information will be stored in text files. 1. Files will be stored inside a directory called data within the same directory as your script. 2. Each file will be named based on the combination of a department code and a course number, which consists of two or three letters followed by an integer with exactly four digits, followed by the extension .crs (notice that the text file does not end in .txt. Does that need to be accounted for?). 3. A course file consists of exactly five lines: • dept_code (two or three letter abbreviation) dept_name (string with probable whitespace) • course_name (string with probable whitespace) Assignment 1: Shell Scripting Page 1 of 6 • course_sched (string consisting precisely of either “MWF” or “TH”) course_start (string with no whitespace) course_end (string with no whitespace) • course_hours (credit hours, unsigned integer) • course_size (enrolled students, unsigned integer) * Department names may contain whitespace. You should account for names with multiple tokens (e.g., “ESL English as a Second Language” =⇒ dept_code = “ESL”, and dept_name = “English as a Second Language”) 4. Example file named esl3053.crs ESL English as a Second Language Literacy in a Second Language MWF 8/26/19 12/13/19 3 52 Script Execution When the script is run, the following should occur. All script output should appear exactly as it appears below. 1. Upon running your script, the user should be presented with the following menu: Enter one of the following actions or press CTRL-D to exit. C – create a new course record R – read an existing course record U – update an existing course record D – delete an existing course record E – update enrolled student count of existing course T – show total course count 2. The user then enters a one-character action (upper or lowercase), leading to one of the following. • C: a course is created (a) From the terminal, read the following one at a time: i. Department code (two-to-three character string) ii. Department name (string possibly containing whitespace) iii. Course number (integer) iv. Course name (string possibly containing whitespace) v. Course schedule (string ∈ {MWF,TH}) vi. Course start date (string with slashes) vii. Course end date (string with slashes) Assignment 1: Shell Scripting Page 2 of 6 viii. Course credit hours (unsigned integer) ix. Initial course enrollment (unsigned integer) (b) Using the values entered by the user, create a new file in the data folder based on the instructions above. (c) Update data/queries.log by adding the following line: [date] CREATED: dept_code course_num course_name where date is the output from the date command and dept_code, course_num, and course_name are the corresponding values. (d) If the course already exists, print the following error and continue with the script. The script should accept all seven inputs before checking if the record exists. ERROR: course already exists • R: read an existing course’s information (a) Prompt the user for a course department and course number: (e.g., “cs 3423”) Enter a department code and course number: (b) Search for the specified course using the provided department and number (e.g., “cs 3423”). (c) Print the course information in the following format: Course department: dept_code dept_name Course number: course_num Course name: course_name Scheduled days: course_sched Course start: course_start Course end: course_end Credit hours: course_hours Enrolled Students: course_size (d) If the course is not found, print the following error instead and continue with the script. ERROR: course not found • U: update an existing course record (a) Prompt the user for the following one at a time: i. Department code (two-to-three character string) ii. Department name (string possibly containing whitespace) iii. Course number (integer) iv. Course name (string possibly containing whitespace) v. Course meeting days (string ∈ {MWF,TH}) vi. Course start date (string with slashes) vii. Course end date (string with slashes) Assignment 1: Shell Scripting Page 3 of 6 viii. Course credit hours (unsigned integer) ix. Course enrollment (unsigned integer) (b) Search for the specified course using the course department and course number (e.g., “cs 3423”). (c) Update each of the corresponding fields based on the user input. If the user input is blank for a particular field, keep the original value from the file. (d) Update data/queries.log by adding the following line: [date] UPDATED: dept_code course_num course_name where date is the output from the date command and dept_code, course_num, and course_name are the corresponding values. (e) If the course is not found, print the following error and continue with the script. The script should accept all nine inputs before checking if the record exists. ERROR: course not found • D: delete an existing course (a) Prompt the user for a string representing the course department and number (e.g., “cs 3423”): Enter a course department code and number: (b) Delete the specified course’s file. (c) Update data/queries.log by adding the following line: [date] DELETED: dept_code course_num course_name where date is the output from the date command and dept_code, course_num, and course_name are the corresponding values. (d) Print the following message to stdout with the course’s number: course number was successfully deleted. (e) If the course is not found, print the following error instead and continue with the script. ERROR: course not found • E: update the number of enrolled students for an existing course (a) Prompt the user for a string representing the course department and number (e.g., “cs 3423”): Enter a course department code and number: (b) Prompt the user for an enrollment change amount (e.g., entering a value of 3 would represent enrolling three new students in the class, while -2 would reflect two students having dropped the course): Enter an enrollment change amount: (c) Search for the specified course using the course number. (d) Update the course record by adding the new enrollment count to the course’s current enrollment count. Negative values are allowed. (i.e., students could drop the Assignment 1: Shell Scripting Page 4 of 6 class). (e) Update data/queries.log by adding the following line: [date] ENROLLMENT: dept_code course_num course_name changed by change_amt where date is the output from the date command and dept_code, course_num, course_name, and change_amt are the corresponding values. (f) If the course record is not found, print the following error and continue with the script. The script should accept the enrollment change amount before checking if the record exists. ERROR: course not found • T: print the total number of course records (a) Print the total number of .crs files within the data directory: Total course records: total where total is the total .crs files. • If an invalid character is entered, print the following error and continue with the script. ERROR: invalid option 3. After an action is completed, display the menu again. This should go on indefinitely until CTRL-D or the end of a file is reached. Assignment Data An initial data set can be found in /usr/local/courses/ssilvestro/cs3423/Fall19/assign1. Copy this to your own assignment’s directory. Script Files Your program should consist of seven bash files with the following names (case sensitive): • assign1.bash – the main file which is initially invoked • create.bash – logic for the create option • read.bash – logic for the read option • update.bash – logic for the update option • delete.bash – logic for the delete option • enroll.bash – logic for the update enrollment option • total.bash – logic for the total option Assignment 1: Shell Scripting Page 5 of 6 Verifying Your Program Your program must work with the input provided in a1Input.txt. To test it: 1. Verify that your assignment folder has a data directory with the initial data set. 2. Execute your script and redirect a1Input.txt into it. You should not be copying or typing the contents of a1Input.txt into your terminal. Redirection must work. 3. Verify that the output and files are as expected. Submission Turn your assignment in via Blackboard. Your zip file, named abc123.zip (with your personal abc123) should contain only your seven bash files.For this assignment, you will use sed, bash, and the other utilities you have used in class to create a program for use by a municipality for both redacting sensitive information from internal communications, as well as simplifying and standardizing the format of these documents prior to their release and circulation. Your program should take the names of one or more files that are to be redacted as command line arguments. This assignment requires only sed, bash, and the other utilities used so far in class. Do not use awk, Python, or any other languages/utilities. Redaction and Substitution Rules For all files specified, the following changes should be made in place. No other changes should be made to the file. • Driver’s License numbers begin with xx DL, where xx is a two-letter state code identifying the origin of the issuing state. Following this code is a space character, then a license number composed of at least 6 digits in length. For example, the following are all valid driver’s license numbers: – TXDL 12345678 – VADL 123456 – WADL 1234567890 These numbers should be redacted by simply replacing the license number with a sequence of six X characters. • Credit Card Numbers Credit card numbers must be redacted, but it is desirable that the censored text still retain information suitable for the identification of both the type of card (i.e., the issuer), as well as its last four digits. Each card network specifies a unique first digit to the cards they issue, and typically contain 16 digits in total. American Express is an exception to this, in which the second number can only be a 4 or a 7, and the total number of digits is only 15. In summary: – Visa cards: Begin with a 4 and have 16 digits – Master Cards: Begin with a 5 and have 16 digits – American Express cards: Begin with a 3, followed by a 4 or a 7, and have 15 digits – Discover cards: Begin with a 6 and have 16 digits Card number data should be redacted as in the following examples. Note that 16 digit numbers may or may not be separated into groups of four using hyphens – this is optional. Hyphenation of American Express cards into sections of 4, 6, and 5 digits is similarly common, and also optional. Examples of the expected substitutions for each card type are as follows: Assignment 2: sed Page 1 of 4 – 5441-4839-9284-3129 → MC-3129 – 3770-123456-78900 → AMEX-8900 – 6093-2033-0662-5389 → DISC-5389 – 4291723799801302 → VISA-1302 • Texas Vehicle License Plate numbers should be similarly obliterated. Texas vehicle plates appear in one of two formats, but both will be written with the letters TX and an optional space preceding them. The first type is six alphanumeric characters, optionally separated by a hyphen in the middle. The second type begins with three alphabetic characters, followed by four digits, again optionally separated by a hyphen. Examples of valid type one Texas license plate numbers are: – TX 32P9ZP – TX 32P-9ZP – TX32P9ZP – TX32P-9ZP Examples of valid type two Texas license plate numbers are: – TX JTK8791 – TX JTK-8791 – TXJTK8791 – TXJTK-8791 These numbers should be redacted by simply replacing the license plate number with a sequence of six X characters. • Current Date Placeholder The document authors may use the shorthand symbol in order to insert the current date (i.e., today’s date). Regardless of the date on which your script is run, this placeholder should be updated with the correct current date. • Municipality Name Placeholder The authors of these documents may use the shorthand symbol in order to designate the full name of their municipality. Any such references should be replaced with the full name: City of Gainsville, Florida. Example Original redactme.txt: 1 2 Date : 3 T i t l e : Memorandum #139 4 Assignment 2: sed Page 2 of 4 5 Dear s t a f f : 6 7 Memorandum #139 ha s been amended a s f o l l o w s , i n a c c o r d a n c e w i t h t h e 8 u p da te d em pl oyee o p e r a t i o n s and p u r c h a s i n g p o l i c y ∗ : 9 10 The o n l y em pl o y e e s a u t h o r i z e d t o o p e r a t e v e h i c l e #102 ( l i c e n s e p l a t e 11 TX JTK8791 ) , v e h i c l e #162 ( l i c e n s e p l a t e TX 32P−9ZP) , and v e h i c l e #262 12 ( l i c e n s e p l a t e TX AJC−6244) a r e t h o s e em pl o y e e s who p o s s e s s t h e f o l l o w i n g 13 d r i v e r ‘ s l i c e n s e s : 14 15 TXDL 02851332 16 TXDL 00748892 17 VADL 590401 18 FLDL 104281332 19 20 F u r t h e r , u sa g e o f c i t y c r e d i t c a r d s w i l l be s t r i c t l y l i m i t e d t o t h e 21 f o l l o w i n g d e p a r tm e n t a l ca r d s , u n t i l f u r t h e r n o t i c e : 22 23 5441−4839−9284−3129 24 3770−123456−78900 25 6093−2033−0662−5389 26 4291723799801302 27 28 Thank you , 29 Mgmt 30 31 ∗ P o l i c y r e v i s i o n da t e 2/1/13 ( o r i g i n a l l y p a s s e d 7 / 1 3 / 9 2 ) . Redacted Version of redactme.txt: 1 C i t y o f G a i n s v i l l e , F l o r i d a 2 Date : 09/19/2019 3 T i t l e : Memorandum #139 4 5 Dear s t a f f : 6 7 Memorandum #139 ha s been amended a s f o l l o w s , i n a c c o r d a n c e w i t h t h e 8 u p da te d em pl oyee o p e r a t i o n s and p u r c h a s i n g p o l i c y ∗ : 9 10 The o n l y em pl o y e e s a u t h o r i z e d t o o p e r a t e v e h i c l e #102 ( l i c e n s e p l a t e 11 TX XXXXXX) , v e h i c l e #162 ( l i c e n s e p l a t e TX XXXXXX) , and v e h i c l e #262 12 ( l i c e n s e p l a t e TX XXXXXX) a r e t h o s e em pl o y e e s who p o s s e s s t h e f o l l o w i n g 13 d r i v e r ‘ s l i c e n s e s : 14 15 TXDL XXXXXX 16 TXDL XXXXXX 17 VADL XXXXXX 18 FLDL XXXXXX 19 20 F u r t h e r , u sa g e o f c i t y c r e d i t c a r d s w i l l be s t r i c t l y l i m i t e d t o t h e 21 f o l l o w i n g d e p a r tm e n t a l ca r d s , u n t i l f u r t h e r n o t i c e : 22 23 MC−3129 24 AMEX−8900 25 DISC−5389 Assignment 2: sed Page 3 of 4 26 VISA−1302 27 28 Thank you , 29 Mgmt 30 31 ∗ P o l i c y r e v i s i o n da t e 2/1/13 ( o r i g i n a l l y p a s s e d 7 / 1 3 / 9 2 ) . Script Execution Your program should be invoked through a single bash file (see below) with the filename(s) containing the sensitive data as argument(s). Example: $ assign2.bash redactme.txt Assignment Data A sample input file can be found in: /usr/local/courses/ssilvestro/cs3423/Fall19/assign2. When using this data, remember that your will be made to overwrite the files. Be sure to make a backup of the files and restore them every time you run the script. Script Files Your program should consist of exactly two files: • assign2.bash – the main file which is initially invoked • Exactly one .sed file which is used for a sed invocation run in assign2.bash. Verifying Your Program Your program must work for arbitrary files by applying the rules above. You can test your program with the input provided in redactme.txt and compare the output with redacted.txt using diff (check the man-pages on how to use it). You should create your own test cases to test for the recursion feature. Submission Turn your assignment in via Blackboard. Your zip file, named abc123.zip (with your abc123) should contain only your bash and sed files.Part A For this part of the assignment, you will create a single command which will take the contents of a passwd file (usually found in /etc/passwd) and print it in sorted order by the user’s last name (that is, their surname, not their username). Normally, you could solve this with the following options on sort: $ sort -t: -k6 /path/to/passwd You, however, must solve this problem with the utilities covered in class so far. You may (and should) use sort, but you may not use any of its options (e.g., -k, -t, etc). Example Input: 1 lkj293 : x :1539:1543: Albert Einstein :/ home / einstein :/ bin/ bash 2 kkr590 : x :1540:1544: Elvis Presley :/ home / presley :/ bin/ bash 3 nwk409 : x :1541:1545: George Washington :/ home / washington :/ bin/ bash 4 yaa265 : x :1542:1546: Bruce Banner :/ home / banner :/ bin/ bash 5 yhn211 : x :1543:1547: George Harrison :/ home / harrison :/ bin/ bash 6 lfa806 : x :1544:1548: Jane Austen :/ home / austen :/ bin/ bash 7 ilo709 : x :1545:1549: Walt Disney :/ home / disney :/ bin/ bash 8 rfd576 : x :1546:1550: Buzz Aldrin :/ home / aldrin :/ bin/ bash 9 lko889 : x :1547:1551: Marie Curie :/ home / curie :/ bin/ bash 10 cfq219 : x :1548:1552: J . R . R . Tolkien :/ home / tolkien :/ bin/ bash 11 ncz856 : x :1549:1553: Christopher Columbus :/ home / columbus :/ bin/ bash 12 pql747 : x :1550:1554: Julius Caesar :/ home / caesar :/ bin/ bash Output: 1 rfd576 : x :1546:1550: Buzz Aldrin :/ home / aldrin :/ bin/ bash 2 lfa806 : x :1544:1548: Jane Austen :/ home / austen :/ bin/ bash 3 yaa265 : x :1542:1546: Bruce Banner :/ home / banner :/ bin/ bash 4 pql747 : x :1550:1554: Julius Caesar :/ home / caesar :/ bin/ bash 5 ncz856 : x :1549:1553: Christopher Columbus :/ home / columbus :/ bin/ bash 6 lko889 : x :1547:1551: Marie Curie :/ home / curie :/ bin/ bash 7 ilo709 : x :1545:1549: Walt Disney :/ home / disney :/ bin/ bash 8 lkj293 : x :1539:1543: Albert Einstein :/ home / einstein :/ bin/ bash 9 yhn211 : x :1543:1547: George Harrison :/ home / harrison :/ bin/ bash 10 kkr590 : x :1540:1544: Elvis Presley :/ home / presley :/ bin/ bash 11 cfq219 : x :1548:1552: J . R . R . Tolkien :/ home / tolkien :/ bin/ bash 12 nwk409 : x :1541:1545: George Washington :/ home / washington :/ bin/ bash Assignment 3: awk Page 1 of 4 Script Execution (Part A) Since the fox machines do not have useful /etc/passwd files (no first and last names), you will use the one provided with this assignment. Your submission will include a bash file (assign3A.sh) with exactly one line in it (you do not need a shebang) and should take the path to the passwd file as the first argument. Do not include an awk file or any other files besides assign3A.sh. $ assign3A.sh /path/to/passwd Part B For this part of the assignment, you will only use the utilities covered in class so far (primarily awk) to create a program for printing user process information. Do not use Python or any programs/utilities not covered in class. Your program should take the output from ps -ef and print the following for each user having a username matching the abc123 format: • Username • List of commands After listing statistics for each user, the program should print the following information for all users having a username matching the abc123 format: • Line with earliest start time • Line with latest start time Do not use sed, Python, or any other languages/utilities not covered in class. Example The example below is an excerpt from the ps -ef command which your program should be able to take as input. Note that if a process began execution on a previous calendar day, its STIME value will not be in the usual “hours and minutes” format, but rather in “month and day” format. This should be accounted for properly, and thus a simple text/numerical comparison will not suffice. Assignment 3: awk Page 2 of 4 Input: 1 UID PID PPID C STIME TTY TIME CMD 2 adz110 5344 5334 0 08:47 pts /2 00:00:00 bash 3 dmq292 6908 6854 0 Jun04 pts /1 00:00:00 bash 4 adz110 7227 7150 0 Jul11 pts /9 00:00:00 who 5 erg474 7466 7461 0 08:54 pts /10 00:00:00 ls 6 dmq292 7966 7960 0 Jun04 pts /13 00:00:00 assign1 . sh if of 7 xle135 8983 8636 0 08:59 pts /15 00:00:00 ssh ctf . cs . utsarr . net 8 zeh458 9057 1980 0 08:59 pts /7 00:00:00 vim prog . c 9 rslavin 9150 9139 0 08:59 pts /16 00:00:00 ps – af 10 xle135 8636 8628 0 08:58 pts /15 00:00:00 bash Output: 1 User : adz110 2 bash 3 who 4 User : dmq292 5 bash 6 assign1 . sh if of 7 User : erg474 8 ls 9 User : xle135 10 bash 11 ssh ctf . cs . utsarr . net 12 User : zeh458 13 vim prog . c 14 15 Earliest Start Time : 16 dmq292 6908 6854 0 Jun04 pts /1 00:00:00 bash 17 18 Latest Start Time : 19 xle135 8983 8636 0 08:59 pts /15 00:00:00 ssh ctf . cs . utsarr . net Also, if there is a tie for earliest or latest start times, take the one with the UID that comes first alphabetically. Hint: Consider using sort to help with grouping. Script Execution (Part B) Your program should each be invoked through a single bash file (see below) with input taken from stdin. The resulting output should be printed directly to stdout. $ assign3B.sh < ps.in or Assignment 3: awk Page 3 of 4 $ ps -ef | assign3B.sh Assignment Data Sample input files can be found in: /usr/local/courses/ssilvestro/cs3423/Fall19/assign3. Script Files Your submission should consist of multiple files: • assign3A.sh – a bash script with a single line of code (i.e., one command) for part A • assign3B.sh – a bash script to invoke for part B. • assign3B.awk – the awk program used in assign3B.awk Verifying Your Programs Part A can be tested with the sample input provided with passwd.in. Part B can be tested with the sample input provided with ps.in. Your program should also work with arbitrary input from the ps -ef command. Submission Turn your assignment in via Blackboard. Your zip file, named abc123.zip with your personal abc123 should contain only your bash and awk files.For this assignment, you will use awk, sed, and bash to create a simple templating engine. Your program should take as input a generic template with placeholders for generic data, a set of input files containing data which should be applied to the template, and a date. Instantiated templates using the input data will be output to a subdirectory. This assignment requires only sed, awk, and bash. You may use any combination of these programs and are not required to use all of them. Do not use Python or any other languages/utilities. Hint: Since you will need to produce many files from many inputs, it may be useful to use awk to generate sed and/or bash scripts. Data Format Data will be stored in the same format as the data in Assignment 1. For each course with an enrollment greater than 50, your program will use the provided template to generate an advisory report specifically for them. 1. Data files (i.e., of the same format as those generated in Assignment 1) will be stored inside a directory specified by the user. 2. Each file within that directory will be named based on the department code (two or three uppercase alphabetic characters), a course number (exactly four digits), and ending with an extension of .crs. 3. A course file consists of exactly five lines: • dept_code (two or three character string) dept_name (string with possible whitespace) • course_name (string with possible whitespace) • course_sched (string: either TH or MWF) course_start (start with no whitespace) course_end (string with no whitespace) • credit_hours (integer) • num_students (integer representing number of enrolled students) 4. Example file named MAT1311.crs MAT Mathematics Calculus I TH 8/26/19 12/11/19 3 62 Assignment 4: More Scripting Page 1 of 4 Templating Templates will include variable names to be filled in with data using double square brackets. For any data file of the format described above, each of the variables (including the square brackets) should be substituted with the data’s actual value. Your program should work for arbitrary templates using the same variables listed below corresponding to the item values described. More than one variable may appear per line. • [[dept_code]] • [[dept_name]] • [[course_name]] • [[course_start]] • [[course_end]] • [[credit_hours]] • [[num_students]] • [[course_num]] (the course number as specified in the filename of the .crs file) • [[date]] (see below) Example Template:* 1 < html > 2 < body > 3 NOTICE OF OVERENROLLMENT – COURSE [[ dept_code ]] [[ course_num ]]←- – [[ date ]] 4 5 Dear Instructor , 6 7 8 Your course , [[ course_name ]] , scheduled from [[ course_start ]] to←- [[ course_end ]] , has exceeded normal capacity with an ←- enrollment of [[ num_students ]] students . This must be ←- corrected within thirty days or this issue will be referred ←- to the [[ dept_name ]] department for further review . 9 10 11 – Administration 12 13 14 * This is only a single example of a single template! You must assume that multiple different templates, with various combinations of variables, will be ran against your program. Experiment with exercising your program using your own custom scripts, as none will be provided to you. This is to emphasize the notion that no single template should be used as a test instrument; your script will be tested against several unknown-to-you templates. Assignment 4: More Scripting Page 2 of 4 Date Argument The third command-line argument should be a date manually entered by the user of the format MM/DD/YYYY. This value should be substituted anywhere where [[date]] appears. Output All output files should be written to the directory defined by the last argument. This directory may or may not already exist. Each file should be named by the course’s department code and number, and with the extension .warn. Script Execution Your program should be invoked through a single bash file (see below) with four arguments: data directory, template file, date, and output directory. Assuming the program executes correctly, no output should be printed to the screen. $ assign4.sh ./data assign4.template 12/16/2021 ./output Assignment Data Sample input files can be found in: /usr/local/courses/ssilvestro/cs3423/Fall19/assign4. Script Files Your program may consist of multiple files: • assign4.sh – the main file which is initially invoked (required) • .awk files • .sed files Note: If your program generates any intermediate awk or sed files during execution, name them beginning with the letter ’g’. Moreover, delete them when your program has completed. Extra Credit (5 points) Allow your program to take optional fifth and sixth arguments describing the character(s) surrounding the variables instead of double square brackets. This feature should work for the following characters as either the opening or closing symbol, “/”, “|”, “}”, and “{”. Note that these can be in any combination (e.g., starting with “{” and ending with “|”) If no fifth and sixth arguments are passed, the program should behave as normal. You may assume that if a fifth argument is passed, Assignment 4: More Scripting Page 3 of 4 a sixth will be present, too. Example: $ assign4.sh ./data assign4.template 12/16/2021 ./output ’{’ ’|’ The above invocation should replace variables in the template such as {date| instead of [[date]]. Extra credit is not given to late assignments. All requirements must be met to qualify for extra credit. Submission Turn your assignment in via Blackboard. Your zip file, named abc123.zip should contain only your bash, awk, and sed files. If you attempt the extra credit, name your file abc123_EC.zip. Without the _EC, your submission will be graded as normal.For this assignment, you will use Python 3 to create a simple templating engine. Your program should take as input a generic template with placeholders for generic data, a set of input files containing data which should be applied to the template, and a date. Instantiated templates using the input data will be output to a subdirectory. This assignment requires only Python. Do not use the command line utilities used in the previous assignment. You are encouraged to explore the Python standard library (the shutil module may be particularly useful). Data Format Data will be stored in the same format as the data in Assignment 1. For each course with an enrollment greater than 50, your program will use the provided template to generate an advisory report specifically for them. 1. Data files (i.e., of the same format as those generated in Assignment 1) will be stored inside a directory specified by the user. 2. Each file within that directory will be named based on the department code (two or three uppercase alphabetic characters), a course number (exactly four digits), and ending with an extension of .crs. 3. A course file consists of exactly five lines: • dept_code (two or three character string) dept_name (string with possible whitespace) • course_name (string with possible whitespace) • course_sched (string: either TH or MWF) course_start (start with no whitespace) course_end (string with no whitespace) • credit_hours (integer) • num_students (integer representing number of enrolled students) 4. Example file named MAT1311.crs MAT Mathematics Calculus I TH 8/26/19 12/11/19 3 62 Assignment 5: More Scripting – Python Edition Page 1 of 4 Templating Templates will include variable names to be filled in with data using double square brackets. For any data file of the format described above, each of the variables (including the square brackets) should be substituted with the data’s actual value. Your program should work for arbitrary templates using the same variables listed below corresponding to the item values described. More than one variable may appear per line. • [[dept_code]] • [[dept_name]] • [[course_name]] • [[course_start]] • [[course_end]] • [[credit_hours]] • [[num_students]] • [[course_num]] (the course number as specified in the filename of the .crs file) • [[date]] (see below) Example Template:* 1 < html > 2 < body > 3 NOTICE OF OVERENROLLMENT – COURSE [[ dept_code ]] [[ course_num ]]←- – [[ date ]] 4 5 Dear Instructor , 6 7 8 Your course , [[ course_name ]] , scheduled from [[ course_start ]] to←- [[ course_end ]] , has exceeded normal capacity with an ←- enrollment of [[ num_students ]] students . This must be ←- corrected within thirty days or this issue will be referred ←- to the [[ dept_name ]] department for further review . 9 10 11 – Administration 12 13 14 * This is only a single example of a single template! You must assume that multiple different templates, with various combinations of variables, will be ran against your program. Experiment with exercising your program using your own custom scripts, as none will be provided to you. This is to emphasize the notion that no single template should be used as a test instrument; your script will be tested against several unknown-to-you templates. Assignment 5: More Scripting – Python Edition Page 2 of 4 Date Argument The third command-line argument should be a date manually entered by the user of the format MM/DD/YYYY. This value should be substituted anywhere where [[date]] appears. Output All output files should be written to the directory defined by the last argument. This directory may or may not already exist. Each file should be named by the course’s department code and number, and with the extension .warn. Script Execution Your program should be invoked through a single bash file (see below) with four arguments: data directory, template file, date, and output directory. Assuming the program executes correctly, no output should be printed to the screen. $ assign5.py ./data assign5.template 12/16/2021 ./output Assignment Data Sample input files can be found in: /usr/local/courses/ssilvestro/cs3423/Fall19/assign5/data. Script Files Your program should consist of exactly one file: • assign5.py – the main file which is initially invoked Extra Credit (5 points) Allow your program to take optional fifth and sixth arguments describing the character(s) surrounding the variables instead of double square brackets. This feature should work for the following characters as either the opening or closing symbol, “/”, “|”, “}”, and “{”. Note that these can be in any combination (e.g., starting with “{” and ending with “|”) If no fifth and sixth arguments are passed, the program should behave as normal. You may assume that if a fifth argument is passed, a sixth will be present, too. Example: $ assign5.py ./data assign5.template 12/16/2021 ./output ’{’ ’|’ The above invocation should replace variables in the template such as {date| instead of [[date]]. Assignment 5: More Scripting – Python Edition Page 3 of 4 Extra credit is not given to late assignments. All requirements must be met to qualify for extra credit. Submission Turn your assignment in via Blackboard. Your zip file, named abc123.zip should contain only your Python file. If you attempt the extra credit, name your file abc123_EC.zip. Without the _EC, your submission will be graded as normal.For this assignment, you will use Python3 to create an alternative to the rm command. This program, rm.py, will take an arbitrary number of paths as arguments and, for each argument, move them to ∼/rm_trash . If ∼/rm_trash does not already exist, it should be created. Hint: The shutil module may prove useful. Duplicate Files If a file with the same name already exists in ∼/rm_trash , you should append -1 to the end of the filename before any extension(s) if they exist so that both files are preserved. If a file with the same name in ∼/rm_trash already has -1, the new file should be appended with -2 and automatically incremented for subsequent copies. For example, if a file named file.txt is removed 4 times, ∼/rm_trash should contain the following four files: file.txt, file-1.txt, file-2.txt, and file-3.txt. Note: It is possible that a file being removed will already have a dash and a number at the end of the name. If this is true, you should be sure not modify the original name and only append the counter. For example, if a file named newfile-1.txt is deleted twice, ∼/rm_trash should contain newfile-1.txt and newfile-1-1.txt. You may assume that there will be no conflicts in file names (e.g., rm.py file-1.txt; rm.py file.txt) Recursion Your program should recursively delete files if any argument is -r. If -r is not set, directories should be ignored and your program should print rm.py: cannot remove ’DIR’: Is a directory to STDERR once for each directory encountered where DIR is the name of the directory. When deleting recursively, simply move the directory to ∼/rm_trash using the duplicate naming rules as described above and leave the contents alone. You do not need to modify the names of the files within the removed directory. Paths If an argument does not point to a file, your program should print rm.py: cannot remove ’FILE’: No such file or directory to STDERR once for each invalid argument where FILE is the path given. When moving a file into ∼/rm_trash you should always place it at the root of the directory. For example, if /path/to/a/file.txt is passed as an argument, file.txt should be moved to ∼/rm_trash/file.txt and not ∼/rm_trash/path/to/a/file.txt. Assignment 6: Python Scripting Page 1 of 2 Program Execution Your program should be invoked as a single Python file (see below) with an arbitrary number of arguments representing paths to files (including directories). The -r option may be passed as any argument. Some examples are listed below. $ rm.py /path/to/some/file ./somefile someotherfile $ rm.py /path/to/some/file ./somefile someotherfile -r $ rm.py -r /path/to/some/file ./somefile someotherfile $ rm.py *.java Extra Credit (10 points) For extra credit, create a separate program called restore.py which, given a path to where a file used to be before it was removed with rm.py, will restore the most recent version. Hint: Consider keeping track of the original and new locations of removed files to handle situations where removed files from different paths have the same name. Note that if you use this strategy, the information will need to persist between executions of rm.py and restore.py. Attempts at extra credit will not be considered if rm.py does not work correctly. Assignment Data No sample data is included with this assignment as it should work for all files. As always, you should test your program with your own data as well to be sure that it works correctly. Program Files Your submission will consist of one or two files depending on if you attempt the extra credit: • rm.py – implementation of rm • restore.py – extra credit Submission Turn your assignment in via Blackboard. Your zip file, named LastnameFirstname.zip should contain only your rm.py and optionally restore.py. If you attempt the extra credit, name your file LastnameFirstname_EC.zip. Without the _EC, your submission will be graded as normal.For this assignment, you will use C’s I/O functions to create a simple course catalog database for administrators to update the details of each course offered by the CS department. The system will store basic information about each course, allowing the user to create, read, update, and delete them. All information for all courses will be stored as binary records in a single file. This assignment requires only the utilities used so far in the I/O lecture notes. Do not use bash, sed, awk, find, grep, Python, or any programming languages or utilities besides the C binary functions used in class. Only binary I/O functions should be used to store data to the filesystem (it is OK to use other functions when prompting the user). Note: While this assignment is similar to Assignment 1, it is not exactly the same. You should thoroughly read all of these instructions. Storing Course Information All course information will be stored in a single binary structure as records of the following structure, where courseName is the name of the course (which may contain spaces), courseSched represents the course schedule (either strings MWF or TR), courseHours is the number of credit hours for the course, and courseSize is the number of students currently enrolled in the course. 1 typedef struct 2 { 3 char courseName [64]; 4 char courseSched [4]; 5 unsigned int courseHours ; 6 unsigned int courseSize ; 7 } COURSE ; The program will store all courses using the above struct in a single file called courses.dat, located within the same directory as the program (this file is provided to you). All courses will be referenced using their course number as their index (e.g., course i will be located in the data file at relative byte off i * sizeof(COURSE). Course records will be stored in courses.dat in coursenumber order. Note that the course numbers will be specified by the user when a course is entered, and will not necessarily be sequential. If courses.dat does not exist, it should be created by the program in the current directory. You must use the files located at: /usr/local/courses/ssilvestro/cs3423/Fall19/assign7; specifically, data/courses.dat shall be used as the starting point for your database (i.e., you must use this file for all operations, not a blank/empty/zero-byte data file, nor any other file). Assignment 7: File I/O Page 1 of 4 Program Execution When the program is executed, the following actions should occur. All program output should appear exactly as it appears below. 1. Upon running your program, the user should be presented with the following menu: Enter one of the following actions or press CTRL-D to exit. C – create a new course record R – read an existing course record U – update an existing course record D – delete an existing course record 2. The user then enters a one-character action (either upper or lowercase), leading to one of the following. • C: a course is created (a) From the terminal, read the following one line at a time: i. Course number (zero-indexed integer) ii. Course name (string possibly containing whitespace) iii. Course schedule (string ∈ {MWF,TR}) iv. Course credit hours (unsigned integer) v. Course enrollment (unsigned integer) (b) Using the values entered by the user, create a new entry in the data file based on the instructions above. (c) If the course already exists, print the following error and continue with the program. The program should detect this and respond immediately after reading the course number. ERROR: course already exists • R: read an existing course’s information (a) Prompt the user for a course number: (e.g., “3423”) Enter a CS course number: (b) Search for the specified course using the provided course number (e.g., “3423”). (c) Print the course information in the following format: Course number: course number Course name: courseName Scheduled days: courseShed Credit hours: courseHours Enrolled Students: courseSize (d) If the course is not found, print the following error instead and continue with the program. Assignment 7: File I/O Page 2 of 4 ERROR: course not found • U: update an existing course record (a) Prompt the user for the following one at a time: i. Course number (zero-indexed integer) ii. Course name (string possibly containing whitespace) iii. Course schedule (string ∈ {MWF,TR}) iv. Course credit hours (unsigned integer) v. Course enrollment (unsigned integer) (b) Update each of the corresponding fields for the course based on the user’s input. If the user input is blank for a particular field (except course number), maintain the original value from the file. (c) If the course record is not found, print the following error and continue with the program. You should detect this and respond immediately after reading the course number. ERROR: course not found • D: delete an existing course (a) Prompt the user for a course number (e.g., “3423”): Enter a course number: (b) Delete the specified course’s record. Hint: You may assume thecreditHours field will never be zero for a valid course. (c) Print the following message to standard output with the course’s number: course number was successfully deleted. (d) If the course is not found, print the following error instead and continue with the program. ERROR: course not found • If an invalid character is entered, print the following error and continue with the program. ERROR: invalid option 3. After an action is completed, display the menu again. This should proceed indefinitely until CTRL-D is read, or the end of the file is reached. Locating Data For the above functionality, courses.dat should not be read sequentially to search for courses. The location of the course in courses.dat should be calculated immediately and directly accessed without performing a search (i.e., no looping!). Assignment 7: File I/O Page 3 of 4 Assignment Data Input files for testing can be found in /usr/local/courses/ssilvestro/cs3423/Fall19/assign7 including an existing .dat file and input for stdin. Copy these to your own assignment’s directory. Important: The input file assumes you are using the provided .dat file. Furthermore, each time you use the input file, you should refresh the .dat file to its original state. Compiling Your Program Your submission will include a makefile so the following command can be used to compile your code. $ make assign7 Program Files Your program should consist of up to three files: • assign7.c – the main file which is compiled (required) • assign7.h – an optional header file, if necessary • makefile – the makefile to make the assign7 executable (required) Verifying Your Program Your program must work with the input provided in a7Input.txt and courses.dat. To test it: 1. Place courses.dat in the same directory as your compiled program. 2. Execute your compiled program and redirect a7Input.txt into it. You should not be copying or typing the contents of a7Input.txt into your terminal. Redirection must work. 3. Verify that the output is correct based on the input commands. 4. Execute your program again and use your program’s menu to test that the information was correctly written to courses.dat. Submission Turn in your assignment via Blackboard. Your zip file, named abc123.zip should contain only your makefile, assign7.c, and possibly assign7.h. Do not include a .dat file.For this assignment, you will use C’s process control functions to exercise basic process creation. Your program should have the following functionality: Concurrency Given up to six commands separated by commas (a comma will be its own token, with whitespace around it) and any number of arguments each, execute all commands concurrently (i.e., in parallel and not one after the other). Each process (excluding the parent) should print their PID followed by their PPID followed by their command without arguments to stderr. Any normal behavior by the command issued should remain the same. You do not need to account for redirection or pipelining. Your program should not produce orphans. Toward verification of this, if a process’s PPID is 1, it is an orphan that has been adopted by the init process. In solving this problem, be sure that your child processes still run concurrently. Do not wait for one process to complete before starting a new one. Example $ assign8 ls -a , pwd , cat hello.txt PID: 35003, PPID: 35002, CMD: ls PID: 35004, PPID: 35002, CMD: pwd Assignment 8: Process Control Page 1 of 3 PID: 35005, PPID: 35002, CMD: cat /home/ssilvestro . .. courses Desktop Downloads this is the contents of hello.txt Note that since the processes are happening in parallel, the order of the output is not guaranteed. Compiling Your Program Your submission will include a makefile so the following command can be used to compile your code. $ make assign8 This should produce an executable file named assign8. For more information about the make utility, check the related document on Blackboard. If you attempt the extra credit, $ make assign8-2 should compile the extra credit portion to assign8-2. Extra Credit (10 points) Create a second program, assign8-2 which takes exactly two commands, with any number of arguments each, and separated by a comma. The program should pipe the output of the first command to the second using dup2(). Example $ assign8-2 ls -l , sort -k5 -n should behave as $ ls -l | sort -k5 -n Extra credit is not given to late assignments. All requirements must be met for both parts of the assignment to qualify for extra credit. Assignment Data This assignment does not include sample input files since it will only take arguments. Program Files Your submission should consist of up to five files: • assign8.c – the main file which is compiled (required) Assignment 8: Process Control Page 2 of 3 • assign8.h – an optional header file if necessary • assign8-2.c – the main file which is compiled for extra credit (required for extra credit) • assign8-2.h – an optional header file if necessary • Makefile – the makefile to make the assign8 executable (required). Submission Turn your assignment in via Blackboard. Your zip file, named abc123.zip should contain only the files described above. If you attempt the extra credit, name your file abc123_EC.zip. Without the _EC, your submission will be graded as normal.
In this project, the students are required to implement the following algorithms: Insert Sort, Select Sort, Quick Sort, and Merge Sort.One file is given:CSCI251ProjOne.java. Please study this file to understand what is going on. This file cannot be modified.One file is to implement: MySort.java. In this file, the students must provide the following public interface: public static void insertSort(int [] arr); public static void selectSort(int [] arr); public static void quickSort(int [] arr); public static void mergeSort(int [] arr);The quick sort and merge sort must be implemented by using recursive thinking. So the students may provide the following private static methods: //merge method //merge two sorted portions of given array arr, namely, from start to middle //and from middle + 1 to end into one sorted portion, namely, from start to end private static void merge(int [] arr, int start, int middle, int end);//merge sort recursive version //sort the portion of giving array arr, from begin to end private static void mergeSortRecursive(int [] arr, int begin, int end); //find pivot point for quick sort private static int pivot(int [] arr, int begin, int end); //quick sort recursive version //sort the portion of giving array arr, from begin to endprivate static void quickSortRecursive(int [] arr, int begin, int end); The student need to have and only have the above public and private static methods in his/her implementation of MySort class.Run Demo: ProjectOne.jar is available for students to download and run on their computer. The students may run to demo in the terminal window to see how program should run. The students may watch YouTube video “How to Run Jar file in the Terminal Window” or refer to the file “How to Run Jar File in the Terminal Window.pdf” on blackboard Projects folder Due Date: To be announced on blackboard.The purpose for this project is to reinforce the knowledge from Chapter Two of the textbook. The students will practice how to implement stack and queue data structure using list structure, for instance, ArrayList. The students will also apply stack and queue in real project, for instance, to check if a string isa palindrom. structure that has Last In First Out property (35%)structure that has First In First Out property (35%)(30%). This function returns true if sentence is a palindrome; falseotherwise.Sample files:Three sample files are given. The students should add necessary comments to all files and implement all functionalities in the given files. No extra functions can be added. No function name can be changed. The students should run the executable jar file to see how project should run. The students should zip whole project and submit it via blackboard link. Due Date:Will be announced on blackboardThis project is designed to help students to understand the HashTable and algorithms related to HashTable. The students need to implement two given classes: MyHashEntry and MyHashTable. Three classes are given. The students shall not modify the ProjThree.java file. However, the students should understand this file. The other two files, MyHashEntry.java and MyHashTable.java, are the files that the students need to finish. These two files, MyHashEntry.java and MyHashTable.java, must be implemented within the given design. The students cannot change the name of public methods. Please notice that the table must be implemented as generic data structure. The students may run the given executable jar file to see how the project should work. When the students run the executable jar file, the students mayenter pairs. Please notice that ID or Name are all Strings with no white space in it. Due date: will be announced on blackboard.This project is designed to help students to understand the Binary Search Tree and algorithms related to Binary Search Tree. The students need to implement two given classes: TreeNode and BinarySearchTree. Three classes are given. The students shall not modify the CSCI251ProjFour.java file. However, the students should understand this file. The other two files, TreeNode.java and BinarySearchTree.java, are the files that the students need to finish. These two files, TreeNode.java and BinarySearchTree.java, must be implemented with in the given design. The students cannot change the name of public methods. The students cannot add extra public methods. However, the students may add private methods to make the implementation more clear and easier to read. For instance, the toString method will return a String representation of a Binary Search Tree. The best way to do so is using recursive thinking. So the toString method actually is a driver method for private method nodeTravesal (see below). The implementation could be as following: public String toString(){return “(” + nodeTravesal(root) +”)”;}private String nodeTravesal(TreeNode treeNode) {if(treeNode == null)return “–‐”;return treeNode.getData().toString() + “(” + nodeTravesal(treeNode.getLeft()) +”, ” + nodeTravesal(treeNode.getRight()) + “)”;} The students may run the given executable jar file to see how the project should work. Due date: will be announced on blackboard.The purpose for this project is to reinforce the students’ knowledge on graph. The students will implement the Breadth First Search and Depth First Search for the graph. The graph will be a direct weighted graph represented in adjunct matrix form. We assume that all weights are positive integers. The graph will be initialized from keyboard. When the students input the graph of n vertices, the students actually input an n by n matrix. The matrix represents a simple direct weighted graph. There is no loop at vertex. No more than one edge from one vertex to another vertex. The vertices are numbered as 1, 2, …, n. The graph with n vertices is represented by an (n+1) by (n+1) matrix with row 0 and column 0 unused. The entry on row i and column j is the weight of edge from vertex i to vertex j. For instance, if there is an edge of weight 8 from vertex i to vertex j (i != j), then entry on row i column j of the matrix will be 8. We assume that all weights are positive integers. If there is no edge from vertex i to vertex j (i != j), then the user will input 0 for the entry on row i column j of the matrix. However, the given code will automatically change that entry to be Integer.MAX_VALUE. Two files are given. The one namedCSCI251ProjFive.java cannot be modified. However, the students should understand it. The one name MyGraph needs to be implemented. In fact, there are only two methods in this file need to be implemented. The students shall read the description of each method and implement the method accordingly. No methods declaration can be changed. No other public interface can be added. The students may run the executable jar file to see how the finished project should run. In this implementation, when there are more than one choice of the vertices, it choose the one marked with lower number first. Example Run:Suppose the graph is followingFor this graph, the student can view it as directed weighted graph. Each edge has two directions. On each direction, the weight is 1. So the array input will be:0 1 0 0 1 01 0 1 0 1 00 1 0 1 0 00 0 1 0 1 11 1 0 1 0 00 0 0 1 0 0 If we run the BFS algorithm with startVertex 6, then the output should be 6, 4, 3, 5, 2,1,If we run the DFS algorithm with startVertex 6, then the output should be 6, 4, 3, 2, 1,5,Due date will be announced on blackboard.
1. The list below comprises a number of distributions, including in each case, the support, parameter space, and density or probability mass function. Determine whether each of the distributions belongs to the exponential dispersion family. Similarly for the twoparameter exponential family of distributions. In both cases, justify your answers. (a) Double exponential (or Laplace) distribution. f(y | θ, σ) = 1 2σ exp − |y − θ| σ y ∈ R, θ ∈ R, σ > 0. (b) Uniform distribution. f(y | θ, σ) = 1 2σ θ − σ < y < θ + σ, θ ∈ R, σ > 0. (c) Logistic distribution. f(y | θ, σ) = exp((y − θ)/σ) σ {1 + exp((y − θ)/σ)} 2 y ∈ R, θ ∈ R, σ > 0. (d) Cauchy distribution. f(y | θ, σ) = 1 πσ {1 + ((y − θ)/σ) 2} y ∈ R, θ ∈ R, σ > 0. (e) Pareto distribution. f(y | α, β) = βαβ y β+1 y ≥ α, α > 0, β > 0. (f) Beta distribution. f(y | α, β) = y α−1 (1 − y) β−1 B(α, β) 0 ≤ y ≤ 1, α > 0, β > 0, where B(α, β) = R 1 0 u α−1 (1 − u) β−1 du is the beta function. (g) Negative binomial distribution. f(y | α, p) = Γ(y + α) Γ(α)y! p α (1 − p) y y ∈ {0, 1, 2, …}, α > 0, 0 < p < 1, where Γ(c) = R ∞ 0 u c−1 exp(−u) du is the gamma function. 2. Consider the linear regression setting where the responses Yi , i = 1, …, n, are assumed independent with means µi = E(Yi) = x T i β = Pp j=1 xijβj for (known) covariates xij and (unknown) regression coefficients β = (β1, …, βp) T . (i) Show that if the response distribution is normal, Yi ind. ∼ f(yi | µi , σ) = (2πσ2 ) −1/2 exp − (yi − µi) 2 2σ 2 , i = 1, …, n, then the maximum likelihood estimate (MLE) of β is obtained by minimizing the L2- norm, S2(β) = Xn i=1 (yi − x T i β) 2 . (ii) Show that if the response distribution is double exponential, Yi ind. ∼ f(yi | µi , σ) = (2σ) −1 exp − |yi − µi | σ , i = 1, …, n, then the MLE of β is obtained by minimizing the L1-norm, S1(β) = Xn i=1 |yi − x T i β|. (iii) Show that if the response distribution is uniform over the range [µi − σ, µi + σ], Yi ind. ∼ f(yi | µi , σ) = (2σ) −1 , for µi − σ ≤ yi ≤ µi + σ, i = 1, …, n, then the MLE of β is obtained by minimizing the L∞-norm, S∞(β) = max i |yi − x T i β|. (iv) Obtain the MLE of σ under each one of the response distributions in (i) – (iii) and show that, in all cases, it is a function of the minimized norm. 3. Consider the special case of the Cauchy distribution, C(θ, 1), with scale parameter σ = 1, and density function f(y | θ) = 1 π{1 + (y − θ) 2} y ∈ R, θ ∈ R, where θ is the median of the distribution. (a) Let y = (y1, …, yn) be a random sample from the C(θ, 1) distribution. Develop the Newton-Raphson method and the method of scoring to approximate the maximum likelihood estimate of θ based on the sample y. (For the method of scoring, you can use the result R ∞ 0 (1 − x 2 )/{(1 + x 2 ) 3} dx = π/8.) (b) Consider a sample, assumed to arise from the C(θ, 1) distribution, with n = 9 and y = (−0.774, 0.597, 7.575, 0.397, −0.865, −0.318, −0.125, 0.961, 1.039). Apply both methods from (a) to estimate θ. To check your results, try a few different starting values and also plot the likelihood function for θ. (c) Now consider a sample (again, assumed to arise from the C(θ, 1) distribution) with n = 3 and y = (0, 5, 9). Apply again the methods from (a) to estimate θ, using three different starting values, θ 0 = −1, θ 0 = 4.67, θ 0 = 10. Comment on the results. 4. The data in the table below show the number of cases of AIDS in Australia by date of diagnosis for successive 3-months periods from 1984 to 1988. Quarter Year 1 2 3 4 1984 1 6 16 23 1985 27 39 31 30 1986 43 51 63 70 1987 88 97 91 104 1988 110 113 149 159 Let xi = log(i), where i denotes the time period for i = 1, …, 20. Consider a GLM for this data set based on a Poisson response distribution with mean µ, systematic component β1 + β2xi , and logarithmic link function g(µ) = log(µ). (a) Fit this GLM to the data working from first principles, that is, derive the expressions that are needed for the scoring method, and implement the algorithm to obtain the maximum likelihood estimates for β1 and β2. (b) Use function “glm” in R to verify your results from part (a).1. Let yi be realizations of independent random variables Yi with Poisson(µi) distributions, where E(Yi) = µi , for i = 1, …, n. (a) Obtain the expression for the deviance for comparison of the full model, which assumes a different µi for each yi , with a reduced model defined by a Poisson GLM with link function g(·). That is, under the reduced model, g(µi) = ηi = x T i β, where β = (β1, …, βp) T (with p < n) is the vector of regression coefficients corresponding to covariates xi = (xi1, …, xip) T . (b) Show that the expression for the deviance simplifies to 2 Pn i=1 yi log(yi/µˆi), for the special case of the reduced model in part (a) with g(µi) = log(µi), and linear predictor that includes an intercept, that is, ηi = β1 + Pp j=2 xijβj , for i = 1, …, n. 2. Let yi , i = 1, …, n, be realizations of independent random variables Yi following gamma(µi , ν) distributions, with densities given by f(yi | µi , ν) = (ν/µi) νy ν−1 i exp(−νyi/µi) Γ(ν) , yi > 0; ν > 0, µi > 0, where Γ(ν) = R ∞ 0 t ν−1 exp(−t)dt is the Gamma function. (a) Express the gamma distribution as a member of the exponential dispersion family. (b) Obtain the scaled deviance and the deviance for the comparison of the full model, which includes a different µi for each yi , with a gamma GLM based on link function g(µi) = x T i β, where β = (β1, …, βp) (p < n) is the vector of regression coefficients corresponding to a set of p covariates. 3. Consider the data set from: https://www.stat.columbia.edu/~gelman/book/data/fabric.asc on the incidence of faults in the manufacturing of rolls of fabric. The first column contains the length of each roll (the covariate with values xi), and the second contains the number of faults (the response with means µi). (a) Use R to fit a Poisson GLM, with logarithmic link, log(µi) = β1 + β2xi (1) to explain the number of faults in terms of length of roll. (b) Fit the regression model for the response means in (1) using the quasi-likelihood estimation method, which allows for a dispersion parameter in the response variance function. (Use the quasipoisson “family” in R.) Discuss the results. (c) Derive point estimates and asymptotic interval estimates for the linear predictor, η0 = β1+ β2×0, at a new value x0 for length of roll, under the standard (likelihood) estimation method from part (a), and the quasi-likelihood estimation method from part (b). Evaluate the point and interval estimates at x0 = 500 and x0 = 995. (Under both cases, use the asymptotic bivariate normality of (βˆ 1, βˆ 2) to obtain the asymptotic distribution of ˆη0 = βˆ 1+ βˆ 2×0.) 4. This problem deals with data collected as the number of Ceriodaphnia organisms counted in a controlled environment in which reproduction is occurring among the organisms. The experimenter places into the containers a varying concentration of a particular component of jet fuel that impairs reproduction. It is anticipated that as the concentration of jet fuel grows, the number of organisms should decrease. The problem also includes a categorical covariate introduced through use of two different strains of the organism. The data set is available from the course website https://ams274-fall16-01.courses.soe.ucsc.edu/node/4 where the first column includes the number of organisms, the second the concentration of jet fuel (in grams per liter), and the third the strain of the organism (with covariate values 0 and 1). Build a Poisson GLM to study the effect of the covariates (jet fuel concentration and organism strain) on the number of Ceriodaphnia organisms. Use graphical exploratory data analysis to motivate possible choices for the link function and the linear predictor. Use classical measures of goodness-of-fit and model comparison (deviance, AIC and BIC), as well as Pearson and deviance residuals, to assess model fit and to compare different model formulations. Provide a plot of the estimated regression functions under your proposed model.1. The table below reports results from a toxicological experiment, including the number of beetles killed (yi) after 5 hours exposure to gaseous carbon disulphide at various concentrations. Concentration (log dose, xi) is given on the log10 scale. Log Dose, xi Number of beetles, mi Number killed, yi 1.6907 59 6 1.7242 60 13 1.7552 62 18 1.7842 56 28 1.8113 63 52 1.8369 59 53 1.8610 62 61 1.8839 60 60 Consider a binomial response distribution, and assume that the yi are independent realizations from Bin(mi , πi), i = 1,…,n. The objective is to study the effect of the choice of link function g(·), where πi = g −1 (ηi) = g −1 (β1 + β2xi). (a) Using R, fit 3 binomial GLMs for these data corresponding to 3 link functions, logit, probit and complementary log-log. Perform residual analysis for each model, using the deviance residuals. Obtain fitted values, ˆπi , under each model and compare with observed proportions, yi/mi . Obtain the estimated dose-response curve under each model by evaluating ˆπ(x) = g −1 (βˆ 1 +βˆ 2x) over a grid of values x for log dose in the interval (1.65, 1.9). Plot these curves and compare with the scatter plot of the observed xi plotted against the observed proportions. Based on all the results above, discuss the fit of the different models. (b) One of the more general (parametric) link functions for binomial GLMs that has been suggested in the literature is defined through g −1 α (ηi) = exp(αηi) {1 + exp(ηi)} α for α > 0. (1.1) Note that the logit link arises as a special case of (1.1), when α = 1. Discuss the effect of the additional model parameter α, in particular, for values 0 < α < 1 and α > 1. Provide the expression for the log-likelihood for β1, β2 and α under the link in (1.1), and discuss the complications that arise for maximum likelihood estimation under this more general model compared with the logit GLM. (You do not need to fit the model, estimates are given below.) (c) The MLEs under the model with link given in (1.1) are βˆ 1 = −113.625, βˆ 2 = 62.5 and αˆ = 0.279. (The MLEs can be obtained using the Newton-Raphson method.) Using these estimates, obtain the fitted values ˆπi and the estimated dose-response curve under the link (1.1). Compare with the corresponding results under the 3 models in (a). Obtain the deviance residuals from the model with link (1.1) and analyze them graphically. (d) Compute the AIC and BIC for the 4 models considered above to compare them. 2. This problem involves Bayesian analysis of the beetle mortality data from the previous problem. (a) Consider a Bayesian binomial GLM with a complementary log-log link, i.e., assume that, given β1 and β2, the yi are independent from Bin(mi , π(xi)), i = 1,…,8, where π(x) ≡ π(x; β1, β2) = 1 − exp{− exp(β1 + β2x)}. Design and implement an MCMC method to sample from the posterior distribution of (β1, β2). Study the effect of the prior for (β1, β2), for example, consider a flat prior as well as (independent) normal priors. Under the flat prior, obtain the posterior distribution for the median lethal dose, LD50, that is, the dose level at which the probability of response is 0.5. Finally, plot point and interval estimates for the dose-response curve π(x) (over a grid of values x for log dose). (b) Next, consider a binomial GLM with a logit link, i.e., now the yi are assumed independent, given β1 and β2, from Bin(mi , π(xi)), i = 1,…,8, where π(x) ≡ π(x; β1, β2) = exp(β1 + β2x)/{1 + exp(β1 + β2x)}. Working with a flat prior for (β1, β2), obtain MCMC samples from the posterior distributions for β1, β2, and for LD50, along with point and interval estimates for the dose-response curve π(x). (c) As a third model, consider the binomial GLM with the parametric link given in (1.1). Develop an MCMC method to sample from the posterior distribution of (β1, β2, α), and obtain the posterior distribution for LD50, and point and interval estimates for π(x). (d) Use the results from parts (a), (b) and (c) for an empirical comparison of the three Bayesian binomial GLMs for the beetle mortality data. Moreover, perform a residual analysis for each model using the Bayesian residuals: (yi/mi)−π(xi ; β1, β2) for the first two models, and (yi/mi)− π(xi ; β1, β2, α) for the third. Finally, use the quadratic loss L measure for formal comparison of the three models.1. The table below reports results from a developmental toxicity study involving ordinal categorical outcomes. This study administered diethylene glycol dimethyl ether (an industrial solvent used in the manufacture of protective coatings) to pregnant mice. Each mouse was exposed to one of five concentration levels for ten days early in the pregnancy (with concentration 0 corresponding to controls). Two days later, the uterine contents of the pregnant mice were examined for defects. One of three (ordered) outcomes (“Dead”, “Malformation”, “Normal”) was recorded for each fetus. Concentration Response Total number (mg/kg per day) Dead Malformation Normal of subjects (xi) (yi1) (yi2) (yi3) (mi) 0 15 1 281 297 62.5 17 0 225 242 125 22 7 283 312 250 38 59 202 299 500 144 132 9 285 Build a multinomial regression model for these data using continuation-ratio logits for the response probabilities πj (x), j = 1, 2, 3, as a function of concentration level, x. Specifically, consider the following model L (cr) 1 = log π1 π2 + π3 = α1 + β1x; L (cr) 2 = log π2 π3 = α2 + β2x for the multinomial response probabilities πj ≡ πj (x), j = 1, 2, 3. (a) Show that the model, involving the multinomial likelihood for the data = {(yi1, yi2, yi3, xi) : i = 1, …, 5}, can be fitted by fitting separately two Binomial GLMs. Provide details for your argument, including the specific form of the Binomial GLMs. (b) Use the result from part (a) to obtain the MLE estimates and corresponding standard errors for parameters (α1, α2, β1, β2). Plot the estimated response curves ˆπj (x), for j = 1, 2, 3, and discuss the results. (c) Develop and implement a Bayesian version of the model above. Discuss your prior choice, and provide details for the posterior simulation method. Provide point and interval estimates for the response curves πj (x), for j = 1, 2, 3. 2. Consider the “alligator food choice” data example, the full version of which is discussed in Section 7.1 of Agresti (2002), Categorical Data Analysis, Second Edition. Here, consider the subset of the data reported in Table 7.16 (page 304) of the above book. This data set involves observations on the primary food choice for n = 63 alligators caught in Lake George, Florida. The nominal response variable is the primary food type (in volume) found in each alligator’s stomach, with three categories: “fish”, “invertebrate”, and “other”. The invertebrates were mainly apple snails, aquatic insects, and crayfish. The “other” category included amphibian, mammal, bird, reptile, and plant material. Also available for each alligator is covariate information on its length (in meters) and gender. (a) Focus first on length as the single covariate to explain the response probabilities for the “fish”, “invertebrate” and “other” food choice categories. Develop a Bayesian multinomial regression model, using the baseline-category logits formulation with “fish” as the baseline category, to estimate (with point and interval estimates) the response probabilities as a function of length. (Note that in this data example, we have mi = 1, for i = 1, …, n.) Discuss your prior choice and approach to MCMC posterior simulation. (b) Extend the model from part (a) to describe the effects of both length and gender on food choice. Based on your proposed model, provide point and interval estimates for the length-dependent response probabilities for male and female alligators. 3. Consider the inverse Gaussian distribution with density function f(y | µ, φ) = (2πφy3 ) −1/2 exp − (y − µ) 2 2φµ2y , y > 0; µ > 0, φ > 0. Denote the inverse Gaussian distribution with parameters µ and φ by IG(µ, φ). (a) Show that the inverse Gaussian distribution is a member of the exponential dispersion family. Show that µ is the mean of the distribution and obtain the variance function. (b) Consider a GLM with random component defined by the inverse Gaussian distribution. That is, assume that yi are realizations of independent random variables Yi with IG(µi , φ) distributions, for i = 1,…,n. Here, g(µi) = x T i β, where β = (β1, …, βp) (p < n) is the vector of regression coefficients, and xi = (xi1, …, xip) T is the covariate vector for the ith response, i = 1,…,n. Define the full model so that the yi are realizations of independent IG(µi , φ) distributed random variables Yi , with a distinct µi for each yi . Obtain the scaled deviance for the comparison of the full model with the inverse Gaussian GLM.Consider the data set from homework 2, problem 3 on the incidence of faults in the manufacturing of rolls of fabric: https://www.stat.columbia.edu/~gelman/book/data/fabric.asc where the first column contains the length of each roll, which is the covariate with values xi , and the second column contains the number of faults, which is the response with values yi and means µi . (a) Fit a Bayesian Poisson GLM to these data, using a logarithmic link, log(µi) = β1 + β2xi . Obtain the posterior distributions for β1 and β2 (under a flat prior for (β1, β2)), as well as point and interval estimates for the response mean as a function of the covariate (over a grid of covariate values). Obtain the distributions of the posterior predictive residuals, and use them for model checking. (b) Develop a hierarchical extension of the Poisson GLM from part (a), using a gamma distribution for the response means across roll lengths. Specifically, for the second stage of the hierarchical model, assume that µi | γi , λ ind. ∼ 1 Γ(λ) λ γi λ µ λ−1 i exp − λ γi µi µi > 0; λ > 0, γi > 0, where log(γi) = β1 + β2xi . (Here, Γ(u) = R ∞ 0 t u−1 exp(−t)dt is the Gamma function.) Derive the expressions for E(Yi | β1, β2, λ) and Var(Yi | β1, β2, λ), and compare them with the corresponding expressions under the non-hierarchical model from part (a). Develop an MCMC method for posterior simulation providing details for all its steps. Derive the expression for the posterior predictive distribution of a new (unobserved) response y0 corresponding to a specified covariate value x0, which is not included in the observed xi . Implement the MCMC algorithm to obtain the posterior distributions for β1, β2 and λ, as well as point and interval estimates for the response mean as a function of the covariate (over a grid of covariate values). Discuss model checking results based on posterior predictive residuals. Regarding the priors, you can use again the flat prior for (β1, β2), but perform prior sensitivity analysis for λ considering different proper priors, including p(λ) = (λ + 1)−2 . (c) Based on your results from parts (a) and (b), provide discussion on empirical comparison between the two models. Moreover, use the quadratic loss L measure for formal comparison of the two models, in particular, to check if the hierarchical Poisson GLM offers an improvement to the fit of the non-hierarchical GLM. (Provide details on the required expressions for computing the value of the model comparison criterion.)
Problem 1 (4 points) Chapter 2, Exercise 2 (p. 52). Problem 2 (4 points) Chapter 2, Exercise 3 (p. 52). Problem 3 (4 points) Chapter 2, Exercise 7 (p. 53). Problem 4 (4 points) Chapter 10, Exercise 1 (p. 413). Problem 5 (4 points) Chapter 10, Exercise 2 (p. 413). Problem 6 (4 points) Chapter 10, Exercise 4 (p. 414). Problem 7 (4 points) Chapter 10, Exercise 9 (p. 416). Problem 8 (4 points) Chapter 3, Exercise 4 (p. 120). Problem 9 (4 points) Chapter 3, Exercise 9 (p. 122). In parts (e) and (f), you need only try a few interactions and transformations. 1 Problem 10 (4 points) Chapter 3, Exercise 14 (p. 125). Problem 11 (5 points) Let x1, . . . , xn be a fixed set of input points and yi = f(xi) + i , where i iid∼ P with E (i) = 0 and Var(i) < ∞. Prove that the MSE of a regression estimate ˆf fit to (x1, y1), . . . ,(xn, yn) for a random test point x0 or E y0 − ˆf(x0) 2 decomposes into variance, square bias, and irreducible error components. Hint: You can apply the bias-variance decomposition proved in class. Problem 12 (5 points) Consider the regression through the origin model (i.e. with no intercept): yi = βxi + i (1) (a) (1 point) Find the least squares estimate for β. (b) (2 points) Assume i iid∼ P such that E (i) = 0 and Var(i) = σ 2 < ∞. Find the standard error of the estimate. (c) (2 points) Find conditions that guarantee that the estimator is consistent. n.b. An estimator βˆ n of a parameter β is consistent if βˆ p→ β, i.e. if the estimator converges to the parameter value in probability.Introduction Homework problems are selected from the course textbook: An Introduction to Statistical Learning. Problem 1 (5 points) Chapter 4, Exercise 1 (p. 168). Problem 2 (5 points) Chapter 4, Exercise 4 (p. 168). Problem 3 (5 points) Chapter 4, Exercise 6 (p. 170). Problem 4 (5 points) Chapter 4, Exercise 8 (p. 170). Problem 5 (5 points) Chapter 4, Exercise 10 parts a-h (p. 171) Problem 6 (5 points) Chapter 5, Exercise 2 (p. 197). Problem 7 (5 points) Chapter 5, Exercise 5 (p. 198). Problem 8 (5 points) Chapter 5, Exercise 6 (p. 199). 1 Problem 9 (5 points) Chapter 5, Exercise 8 (p. 200). Problem 10 (5 points) Chapter 5, Exercise 9 (p. 201).Introduction Homework problems are selected from the course textbook: An Introduction to Statistical Learning. Problem 1 (7 points) Chapter 6, Exercise 3 (p. 260). Problem 2 (7 points) Chapter 6, Exercise 4 (p. 260). Problem 3 (7 points) Chapter 6, Exercise 9 (p. 263). Don’t do parts (e), (f), and (g). Problem 4 (7 points) Chapter 7, Exercise 1 (p. 297). Problem 5 (7 points) Chapter 7, Exercise 8 (p. 299). Find at least one non-linear estimate which does better than linear regression, and justify this using a t-test or by showing an improvement in the cross-validation error with respect to a linear model. You must also produce a plot of the predictor X vs. the non-linear estimate ˆf(X). Problem 6 (7 points) Chapter 9, Exercise 1 (p. 368). Problem 7 (8 points) Chapter 9, Exercise 8 (p. 371).Introduction Homework problems are selected from the course textbook: An Introduction to Statistical Learning. Problem 1 (10 points) Chapter 8, Exercise 4 (p. 332). Problem 2 (10 points) Chapter 8, Exercise 8 (p. 333). Problem 3 (10 points) Chapter 8, Exercise 10 (p. 334). Problem 4 (10 points) Chapter 8, Exercise 11 (p. 335). Problem 5 (10 points) Let xi : i = 1, …, p be the input predictor values and a (2s) k : k = 1, …, K be the K-dimensional output from a 2-layer and M-hidden unit neural network with sigmoid activation σ(a) = {1 + e −a} −1 such that a (1s) j = w (1s) j0 + Xp i=1 w (1s) ji xi : j = 1, …, M a (2s) k = w (2s) k0 + X M j=1 w (2s) kj σ a (1s) j Show that there exists an equivalent network that computes exactly the same output values, but with hidden unit activation functions given by tanh(a) = e a−e −a e a+e−a , i.e. a (1t) j = w (1t) j0 + Xp i=1 w (1t) ji xi : j = 1, …, M a (2t) k = w (2t) k0 + X M j=1 w (2t) kj tanh a (1t) j Hint: first derive the relation between σ(a) and tanh(a). Then show that the parameters of the two networks differ by linear transformations.
In this homework, you need to classify text paragraphs into three categories: Fyodor Dostoyevsky, Arthur Conan Doyle, and Jane Austen by building your own classifiers. The data provided is from Project Gutenberg.Please follow the steps below: • (5pts) Preprocess data: Remove punctuation, irrelevant symbols, urls, and numbers. You can remove the unrelated text in the beginning of each file.• (5pts) Construct examples: Divide each document into multiple paragraphs. Each paragraph will be one example. Text that is not part of a paragraph can be discarded or preprocessed. Report the total number of examples for each category.• (5pts) Data split: Sample these paragraphs into training and testing data.• (5pts) Feature extraction: Build a vocabulary to represent each paragraph using only training data. Consider TF-IDF features for each input example.1. Implement a Logistic Regression (LR) model with L2 regularization from scratch: J = − 1 N X N i=1 X K k=1 yik log exp fk PK c=1 exp fc + λ X d j=1 w 2 kj – (10 pts) Given this formula, show the steps to derive the gradient of J with respect to wk. – (20 pts) Write a function for mini-batch gradient descent. – (20 pts) Write a function for stochastic gradient descent. Report the results and plots for both mini-batch and stochastic gradient descent.2. (10 pts) Build and train a Multilayer Perceptron (MLP) model (i.e., a two-layer neural network) using backpropagation. Please specify the settings of the model such as the network structure, the optimizer, the initial learning rate, the loss function.• (5pts) Plot training loss and validation loss every 100 epoches. • (5pts) Use cross-validation on the training data, report the recall and precision for each category on the test and validation sets, choose the best λ(in LR) and the number of neurons in the hidden layer (in MLP) using the validation set. • (10pts) Compare both classifiers and provide an analysis for the results.Please follow the below instructions when you submit the assignment. 1. You are allowed to use packages for reading text, TF-IDF, plotting, and MLP, but you are not allowed to use packages for mini-batch gradient descent or stochastic gradient descent.2. Your submission should consist of a zip file named Assignment1 LastName FirstName.zip which contains: • a jupyter notebook file(.ipynb). The file should contain the code and the output after execution. You should also include detailed comments and analysis (plots, result tables, etc). • a pdf (or jpg) file to show the derivation steps of the gradient of J with respect to wk.(a) Softmax (5pts) Prove that softmax is invariant to constant offset in the input, that is, for any input vector x and any constant c, softmax(x) = softmax(x + c) where x + c means adding the constant c to every dimension of x. Remember that softmax(x)i = e xi P j e xjNote: In practice, we make use of this property and choose c = − maxi xi when computing softmax probabilities for numerical stability (i.e., subtracting its maximum element from all elements of x).(b) Sigmoid (5pts)Derive the gradients of the sigmoid function and show that it can be rewritten as a function of the function value (i.e., in some expression where only σ(x), but not x, is present).Assume that the input x is a scalar for this question. Recall, the sigmoid function is: σ(x) = 1 1 + e−x (c) Word2veci. (5pts) Assume you are given a predicted word vector vc corresponding to the center word c for skipgram, and the word prediction is made with the softmax function yˆo = p(o|c) = exp(u > o vc) PW w=1 exp(u> w vc) where o is the expected word, w denotes the w-th word and uw (w = 1, …, W) are the “output” word vectors for all words in the vocabulary.The cross entropy function is defined as: JCE(o, vc, U) = CE(y, yˆ) = − X i yi log(ˆyi) where the gold vector y is a one-hot vector, the softmax prediction vector yˆ is a probability distribution over the output space, and U = [u1, u2, …, uW ] is the matrix of all the output vectors.Assume cross entropy cost is applied to this prediction, derive the gradients with respect to vc.ii. (5pts) As in the previous part, derive gradients for the “output” word vector uw (including uo).iii. (5pts) Repeat a and b assuming we are using the negative sampling loss for the predicted vector vc. Assume that K negative samples (words) are drawn and they are 1,…,K respectively. For simplicity of notation, assume (o /∈ {1, …, K}).Again for a given word o, use uo to denote its output vector.The negative sampling loss function in this case is: Jneg-sample(o, vc, U) = − log(σ(u > o vc)) − X K k=1 log(σ(−u > k vc))iv. (5pts) Derive gradients for all of the word vectors for skip-gram given the previous parts and given a set of context words [wordc−m, …, wordc, …, wordc+m] where m is the context size.Denote the “input” and “output” word vectors for word k as vk and uk respectively.Hint: feel free to use F(o, vc) (where o is the expected word) as a placeholder for the JCE(o, vc…) or Jneg-sample(o, vc…) cost functions in this part – you’ll see that this is a useful abstraction for the coding part.That is, your solution may contain terms of the form ∂F (o,vc) ∂… Recall that for skip-gram, the cost for a context centered around c is: X −m≤j≤m,j6=0 F(wc+j , vc)(a) (5pts) Given an input matrix of N rows and D columns, compute the softmax prediction for each row using the optimization in 1.(a). Write your implementation in utils.py.(b) (5pts) Implement the sigmoid function in word2vec.py and test your code.(c) (45pts)Implement the word2vec models with stochastic gradient descent (SGD).i. (15pts) Write a helper function normalizeRows in utils.py to normalize rows of a matrix in word2vec.py. In the same file, fill in the implementation for the softmax and negative sampling cost and gradient functions. Then, fill in the implementation of the cost and gradient functions for the skip-gram model. When you are done, test your implementation by running python word2vec.py.ii. (15pts) Complete the implementation for your SGD optimizer in sgd.py. Test your implementation by running python sgd.py.iii. (15pts) Implement the k-nearest neighbors algorithm, which will be used for analysis. The algorithm receives a vector, a matrix and an integer k, and returns k indices of the matrix’s rows that are closest to the vector.Use the cosine similarity as a distance metric (https: //en.wikipedia.org/wiki/Cosine_similarity). Implement the algorithm in knn.py. Print out 10 examples: each example is one word and its neighbors.(d) (15pts)Load some real data and train your own word vectors. Use the StanfordSentimentTreeBank data to train word vectors. Process the dataset and use the sgd function and word2vec to generate word vectors. Visualize a few word examples. There is no additional code to write for this part; just run python run.py.Note: The training process may take a long time depending on the efficiency of your implementation. Plan accordingly! When the script finishes, a visualization for your word vectors will appear. It will also be saved as word vectors.png in your project directory.In addition, the script should print the nearest neighbors of a few words (using the knn function you implemented in 2(g)). Include the plot and the nearest neighbors lists in your homework write up, and briefly explain those results.3. Submission Instructions You shall submit a zip file named Assignment2 LastName FirstName.zip which contains: • a pdf(or jpg) file contains all your solutions for the Written part • a pdf(or jpg) file contains the word vector plot(vector.png), a brief report of your knn results. • python files(sgd.py, word2vec.py, run.py, knn.py, utils.py)You will need to use the Penn Treebank corpus for this assignment. Four data files are provided: train.txt, train.5k.txt, valid.txt, and input.txt.You can use train.txt to train your models and use valid.txt for testing. File input.txt can be used for a sanity check on whether the model produces coherent sequences of words for unseen data with no next word.(a) (10 pts) Preprocess the train and validation data, build the vocabulary, tokenize, etc. (b) (10 pts) Implement an N-gram model (bigram or trigram) for language modeling. (c) (10 pts) Implement Good Turing smoothing.(d) (10 pts) Implement Kneser-Ney Smoothing using: PKN(wi |wi−1) = max(c(wi−1, wi) − d, 0) c(wi−1) + λ(wi−1)PCONTINUATION(wi) where λ(wi−1) = d c(wi−1) |{w : c(wi−1, w) > 0}| PCONTINUATION(w) = |wi−1 : c(wi−1, w) > 0| P w0 |{w0 i−1 : c(w0 i−1 , w0) > 0}|(e) (5 pts) Predict the next word in the valid set using a sliding window. Report the perplexity scores of N-gram, Good Turing, and Kneser-Ney on the test set. (f) (10 pts) There are 3124 examples in input.txt. Choose the first 30 lines and print the predictions of next words using your N-gram model.(a) (5 pts) Initialize parameters for the model. (b) (10 pts) Implement the forward pass for the model. Use an embedding layer as the first layer of your network (e.g. tf.nn.embedding lookup). Use a recurrent neural network cell (GRU or LSTM) as the next layer. Given a sequence of words, predict the next word.(c) (5 pts) Calculate the loss of the model (sequence cross-entropy loss is suggested) e.g. tf.contrib.seq2seq.sequence loss. (d) (5 pts) Set up the training step: use a learning rate of 1e − 3 and an Adam optimizer. Set window size to be 20 and batch size to be about 50.(e) (10 pts) Train your RNN model. Calcuate the model’s perplexity on the test set. Prove that perplexity is exp total loss number of predictions (f) (10 pts) Print the predictions of next words in the same 30 lines of input.txt as in N-gram.You shall submit a zip file named Assignment3 LastName FirstName.zip which contains: • python files (.ipynb or .py) including all the code, plots and results. You need to provide detailed comments in English.This assignment focuses on convolutional neural networks. You will need to implement convolutional neural network models for two tasks: document classification and sentimental analysis.Use the same datasets as Assignment 1. Classify text paragraphs into three categories: Fyodor Dostoyevsky, Arthur Conan Doyle, and Jane Austen by building your own classifiers.The data provided is from Project Gutenberg.(a) (10 pts) Preprocess the data: build the vocabulary, tokenize, etc. Divide the data into train, validation, and test.(b) (10 pts) Initialize parameters for the model. Implement the forward pass for the model. Use an embedding layer as the first layer of your network (e.g. tf.nn.embedding lookup). Set zero paddings to the input matrix. Use at least two convolutional layers (each layer includes convolution, activation, and maxpooling).(c) (10 pts) Choose and report the number of filters and the filter size for your CNN.(d) (10 pts) Calculate the loss of the model (cross-entropy loss is suggested). Set up the training step: use a learning rate of 1e − 3 and an Adam optimizer.(e) (10 pts) Train you model and report the recall and precision of each class on test data. Tune the parameters to achieve the best performance you can.This is a multi-domain sentiment dataset with positive or negative sentiment annotations. We only use the book reviews for this assignment.There are 1000 positive book reviews and 1000 negative book reviews.(a) (10 pts) Preprocess the data: extract the review text from , build the vocabulary, tokenize, etc. Divide the data into train, validation, and test.(b) (10 pts) Initialize parameters for the model. Implement the forward pass for the model. Use an embedding layer as the first layer of your network (e.g. tf.nn.embedding lookup). Set zero paddings to the input matrix. Use at least two convolutional layers (each layer includes convolution, activation, and maxpooling).(c) (10 pts) Choose and report the number of filters and the filter size for your CNN.(d) (10 pts) Calculate the loss of the model (binary cross-entropy loss is suggested). Choose appropriate output function. Set up the training step including learning rate and optimizer.(e) (10 pts) Train you model and report the accuracy of each class and the total accuracy on test data. Tune the parameters to achieve the best performance you can.You shall submit a zip file named Assignment4 LastName FirstName.zip which contains: (Those who do not follow this naming policy will receive penalty points) • python files (.py) including all the code, comments and results.You need to provide detailed comments in English. • report(.pdf) for each task: Describe your model: size of the training set and validation set, parameters for your model, number of filters, filter size for you CNN model, loss function, learning rate, optimizer, etc. Plot for training and validation loss.Report recall and precision for task 1, and accuracy score for task 2 on test data. Further Reading: • Yoon Kim. Convolutional Neural Networks for Sentence Classification. ACL 2014. arXiv:1408.5882 • Ye Zhang, Byron Wallace. A Sensitivity Analysis of (and Practitioners’ Guide to) Convolutional Neural Networks for Sentence Classification. arXiv:1510.03820
Introduction In this first lab, you will learn how to work with an ARM processor and the basics of ARM assembly by programming some common routines. After you complete the tasks, you should demonstrate your work to a TA. 1 Working with the DE1-SoC Computer System For this course, we will be working with the DE1-SoC Computer System, which is composed of an ARM Cortex-A9 processor and peripheral components located on the FPGA on your DE1-SoC board. The IDE we will be using is the Intel FPGA Monitor Program 16.1. In this part of the lab, you will learn how to program the Computer System in ARM assembly. 1.1 Learn about the tools Before you move on, you should read the Introduction to the ARM Processor Using Altera Toolchain and acquaint yourself with the Altera Monitor Program Tutorial for ARM. You will also find it useful to refer to the ARM Architecture Reference Manual. These documents can be found on myCourses. It may help to keep these manuals open as you work. 1 1.2 Your first assembly program 1. Open the ‘Intel FPGA Monitor Program 16.1’ from the desktop icon and select File->New. Figure 1: Your first assembly program – Step 1 2 2. In the new editor window, type out the code as shown in Figure 2 and save this file as ‘part1.s’ within a new folder ‘GXX Lab1’ on your network drive. Here, GXX stands for your group number! eg. Group 1 would be G01 Lab1. The code is a simple program to find the maximum number from a list of ‘NUMBERS’ with length ‘N’. Notice the extensive use of comments! This practice should be used throughout this course, especially with assembly programming! NOTE: The indentation is important. The code will not compile if not indented as shown. Figure 2: Your first assembly program – Step 2 3 3. Open the ‘Intel FPGA Monitor Program 16.1’ from the desktop icon and select File->New Project. Figure 3: Your first assembly program – Step 3 4 4. Set the project directory to GXX Lab1 and set the project name to GXX Lab1. Select the ‘ARM Cortex-A9’ processor architecture, and click ‘Next’. Figure 4: Your first assembly program – Step 4 5 5. In the next window, under ‘Select a system’ select the ‘DE1-SoC Computer’ and click ‘Next’. Figure 5: Your first assembly program – Step 5 6 6. In the next window, under ‘Program type’ select the ‘Assembly Program‘ and click ‘Next’. Figure 6: Your first assembly program – Step 6 7 7. In the next window ‘Specify program details’, click on ‘Add…’ and select the file ‘part1.s’ created in step 1, and click ‘Next’. Figure 7: Your first assembly program – Step 7 8 8. In the next window ‘Specify system parameters’, ensure that the board is detected in the ‘Host connection’ box, and click ‘Next’. Note that the board has to be plugged in via USB and powered on to be detected. Figure 8: Your first assembly program – Step 8 9 9. In the next window ‘Specify program memory settings’, simply click ‘Finish’. Figure 9: Your first assembly program – Step 9 10 10. A dialogue box should now pop up, asking whether you would like to download the system onto the board. If you were successfully able to flash your JIC file in Lab0, click ‘No’, otherwise click ‘Yes’. Figure 10: Your first assembly program – Step 10 11 1.3 Using the IDE Now that we have created our first assembly project, let’s take a look at some of the features of the IDE and use them in order to debug this program and verify that it works as desired NOTE: This section only provides a very brief introduction to the IDE. More detailed information can and should be obtained in the documentation and by experience! 1. Figure 11 shows the useful features of the IDE when a project is opened. We can say that we are now in ‘development mode’ – where the code is not loaded onto the board and we are in the process of writing code and compiling it to check for errors. The green box highlights the different IDE window tabs, and since we are in development mode, the only useful window is the ‘Editor’ window where code can be created/modified. You can add/remove windows using the ‘Windows’ menu at the top. The red box highlights three useful buttons in development mode – ‘Compile’, ‘Load’, and ‘Compile & Load’. Their functions are self-explanatory. Actually, ‘compiling’ refers to converting higher level computer code (such as C code) into assembly instructions. What we are doing here is ‘assembling’, which refers to the conversion of assembly instructions into machine code. However, since Altera has decided to call it the ‘Compile’ button, we will stick with that name for the sake of clarity. Figure 11: Using the IDE – Development mode 12 2. When the code is loaded onto the board (by clicking either ‘Load’ or ‘Compile & Load’), we can say that we are now in ‘debug mode’. The IDE is now connected to the board via a debug server, and we can send execution instructions to the board and receive data (such as register and memory values) back from the board. The green box highlights the two important windows in this mode. In the Disassembly window, we can see the code that is being executed, as well as the current instruction when the code is paused. We also have the ability to set/remove breakpoints by clicking on the grey area to the left of the instruction. The Disassembly window is the most important window in debug mode. In the Memory window, we can see the contents of a desired memory location, but only when the program is paused! The red box highlights the useful buttons in debug mode. Using them, we can ‘Continue’, ‘Pause’ and ‘Restart’ the program execution. We can also step by a single instruction, or step over multiple instructions. Finally, we can also disconnect from the board. Figure 12: Using the IDE – Debug mode 13 3. Now let’s run the code and verify the result. Before you do this, make sure you have read the code and understand how it works, otherwise you won’t know what it is that you’re checking! Ensure that we are in debug mode and looking at the Disassembly window. Click on the ‘Continue’ button, and then click on the ‘Pause’ button. The code should stop at the B END instruction. Notice how the contents of the registers have now changed, and R0 contains the expected value! Experiment with the IDE features by restarting the program from the first instruction and arriving at the end via steps and breakpoints. Finally, note the address 0x00000038 of RESULT, as it will be used in the next part. Figure 13: Using the IDE – The Disassembly window 14 4. Now move over to the Memory window, and search for the value in the address of RESULT. Once again, we can see that the expected value has appeared in that memory location. Figure 14: Using the IDE – The Memory window 15 2 Some programming challenges Now that you have gone through a simple example in which we have given you the program to be executed, you should complete the following tasks, which will require you to write your own programs. NOTE: You will have to add the new files you will create to your current project GXX Lab1. Since the same label ‘ start’ cannot be used in multiple files, and subroutines are beyond the scope of this lab, the workaround you should use in this lab is to only have one file added to the project at any given time! 2.1 Fast standard deviation computation Suppose that you would like to use the ARM processor to compute the standard deviation of a signal X = {x1, x2, . . . , xN }. The formula for the standard deviation is: σˆ = sPN i=1(xi − µˆ) 2 N − 1 (1) where µˆ is the average value of the signal. Unfortunately, implementing this formula requires multiplication, division, and square root operations, which are not available as instructions on all processors and are slow to emulate using other instructions. The standard deviation can be approximately computed in a more hardware-friendly way using the so-called “range rule”: σˆ ≈ xmax − xmin 4 (2) where xmax and xmin are the maximum value and minimum value of the signal, respectively. Write an ARM assembly program which computes the standard deviation of a signal, using the range rule. The program should accept input values – more specifically, the number of samples in the signal and their values – using a similar approach as shown in Part 1. Save your code in a file named ‘stddev.s’ (Hint: you can reuse your code from Part 1 to compute the maximum value. Then, you can make a simple modification to this code to get code which computes the minimum. Also, remember that dividing by a power of 2 can be implemented using shift instructions.) 16 2.2 Centering an array It is often necessary to ensure that a signal is “centered” (that is, its average is 0). For example, DC signals can damage a loudspeaker, so it is important to center an audio signal to remove DC components before sending the signal to the speaker. You can center a signal by calculating the average value of the signal and subtracting the average from every sample of the signal. Write an ARM assembly program to center a signal. In this example, store the resulting centered signal ‘in place’ – i.e. in the same memory location that the input signal is passed in. The program should be able to accept the signal length as an input parameter. In order to simplify calculations, work with the assumption that only signal lengths that are powers of two can be passed to the program. Save your code in a file named ‘center.s’ 2.3 Sorting Write an ARM assembly program which sorts an array in ascending order. You could use the simple bubble sort algorithm: // Given an a r r ay A of l e n g t h N s o r t e d = f a l s e wh i le no t s o r t e d : s o r t e d = t r u e fo r i = 2 t o N : i f A[ i ] < A[ i −1], swap A[ i ] wi th A[ i −1] and s e t s o r t e d = f a l s e You could also implement a more sophisticated sorting algorithm. Store the resulting sorted array ‘in place’. The program should be able to accept the array length as an input parameter. Save your code in a file named ‘sort.s’ 17 3 Grading and report The TA will ask to see the following deliverables during the demo (the corresponding portion of your grade for each is indicated in brackets): • Largest integer program (10%) • Standard deviation program (15%) • Centering program (25%) • Sorting program (30%) A portion of the grade is reserved for answering questions about the code, which is awarded individually to group members. All members of your group should be able to answer any questions the TA has about any part of the deliverables, whether or not you wrote the particular part of the code the TA asks about. Full marks are awarded for a deliverable only if the program functions correctly and the TA’s questions are answered satisfactorily. Finally, the remaining 20% of the grade for this Lab will go towards a report. Write up a short (2-3) page report that given a brief description of each part completed, the approach taken, and the challenges faced, if any. Please don’t include the entire code in the body of the report. Save the space for elaborating on possible improvements you made or could have made to the program, such as a feature to detect empty (length 0) arrays, etc. Your final submission should be a single compressed folder that contains your report and the four assembly files – ‘part1.s’, ‘stddev.s’, ‘center.s’, and ‘sort.s’. This Lab will run for two weeks, from January 22nd to February 2nd, during which you should demo your code within your assigned lab period. The report for Lab 1 is due by 11:59 pm, February 9th.In this lab, you will learn how to use subroutines and the stack, program in C, and call code written in assembly from code written in C. 1 Subroutines 1.1 The stack The stack is a data structure which can be helpful for situations when there are not enough registers for a program to use only registers to store data. You will also need to make use of the stack when calling subroutines to save the state of the code outside of the subroutine. Review how the PUSH and POP instructions work. Note that pushing and popping can be implemented without using the PUSH and POP instructions by using other ARM instructions. Rewrite the following PUSH and POP instructions using only other instructions: • PUSH {R0} • POP {R0 – R2} Write a test program in assembly to show that your rewritten versions correctly implement PUSH and POP. You should be able to show the TA the contents of main memory changing as registers are pushed onto the stack. 1.2 The subroutine calling convention The convention which we will use for calling a subroutine in ARM assembly is as follows. The caller must: • Move arguments into R0 through R3. (If more than four arguments are required, the caller should push the arguments onto the stack.) • Call the subroutine using BL The callee must • Move the return value into R0 • Ensure that the state of the processor is restored to what it was before the subroutine call • Use BX LR to return to the calling code 1 (The state can be saved and restored by pushing R4 through LR onto the stack at the beginning of the subroutine and popping R4 through LR off the stack at the end of the subroutine.) Convert your program from Lab 1 for finding the max of an array into a program which uses a subroutine. The subroutine should return the max in R0. 1.3 Fibonacci calculation using recursive subroutine calls A recursive subroutine is a subroutine which calls itself. You can calculate the nth Fibonacci number, Fn (where F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, . . . ), using a recursive subroutine as follows: Fi b (n ) : i f n >= 2 : re turn Fi b (n−1) + Fi b (n−2) i f n < 2 : re turn 1 For example, F4 is computed as follows: Fib(4) = Fib(3) + Fib(2) = (Fib(2) + Fib(1)) + (Fib(1) + Fib(0)) = ((Fib(1) + Fib(0)) + 1) + (1 + 1) = (1 + 1 + 1) + (1 + 1) = 5 Write an assembly program which computes the nth Fibonacci number in this way. Your program should have a main section which calls the Fibonacci subroutine recursively for the above pseudocode. 2 Figure 1: C code for computing the max. 2 C Programming Assembly language is useful for writing fast, low-level code, but it can be tedious to work with. Often, high-level languages like C are used instead. 2.1 Pure C We will first go through an example of programming in straight C. • Create a new project, performing the same steps as you performed for an assembly project. However, when the New Project Wizard asks what program type you would like, select “C Program”. Click the box next to “Include a sample program with the project”, and select the “Getting Started” program. • Delete all the code in “getting started.c” and replace it with the incomplete C program shown in Figure 1. • Fill in the code with a for-loop which iterates through the array to find the maximum. • Compile and run the C program the same way you compile and run assembly programs. Notice that the disassembly viewer shows how the compiler has translated C into assembly. 2.2 Calling an assembly subroutine from C It is also possible to mix C and assembly. You will need to do this from Lab 3 onward. Perform the following steps to write a C program which calls an assembly subroutine. • Create a new C project, as you did in Section 2.1. • Add a file to your project called “subroutine.s”. (The filename does not matter, but it should have the .s extension.) • Copy the code from Figure 2 into “subroutine.s”. This code computes the maximum of two numbers and returns the result. Notice that the subroutine does not bother to save and restore the caller state. This is sometimes OK to do, in subroutines which do not change the state. • Next, edit your C program so that it contains the code in Figure 3. This code uses the assembly subroutine to compute the max of two numbers. • Compile and run the program. Find the main section and the MAX 2 section, and put breakpoints to see the processor run those sections. • Finally, rewrite your C program to find the max of a list using the MAX 2 subroutine. 3 Figure 2: Assembly code with MAX 2 subroutine. Figure 3: C code which calls MAX 2 subroutine. 4 3 Grading The TA will ask to see the following deliverables during the demo (the corresponding portion of your grade for each is indicated in brackets): • Test program with rewritten PUSH and POP instructions (15%) • Assembly code which computes the max of an array using an assembly subroutine (15%) • Fibonacci program with recursive subroutine (20%) • C code which computes the max of an array using C (15%) • C code which computes the max of an array using an assembly subroutine (15%) Full marks are awarded for a deliverable only if the program functions correctly and the TA’s questions are answered satisfactorily. A portion of the grade is reserved for answering questions about the code, which is awarded individually to group members. All members of your group should be able to answer any questions the TA has about any part of the deliverables, whether or not you wrote the particular part of the code the TA asks about. Full marks are awarded for a deliverable only if the program functions correctly and the TA’s questions are answered satisfactorily. Finally, the remaining 20% of the grade for this Lab will go towards a report. Write up a short (3-4) page report that gives a brief description of each part completed, the approach taken, and the challenges faced, if any. Please don’t include the entire code in the body of the report. Save the space for elaborating on possible improvements you made or could have made to the program. Your final submission should be a single compressed folder that contains your report and all the code files (.c and .s). This Lab will run for two weeks, from February 5th to February 16th. You should demo your code during those dates, within your assigned lab period. The report for Lab 2 is due by 11:59 pm, February 23rd.Introduction This lab introduces the basic I/O capabilities of the DE1-SoC computer – the slider switches, pushbuttons, LEDs and 7-Segment displays. After writing assembly drivers that interface with the I/O components, timers and interrupts are used to demonstrate polling and interrupt based applications written in C. 1 1 Creating the Project in the Altera Monitor Program IMPORTANT: The project is structured as outlined below to introduce concepts that are used in writing well organized code. Furthermore, drivers for configuring the Generic Interrupt Controller (GIC) will be provided in the latter part of this lab, and the driver code relies on this project structure. The code will not compile if the project is not organized as described! First, create a new folder named GXX Lab3, where GXX is the corresponding group number. Within this folder, create a new folder named drivers. Finally, within the drivers folder, create three folders: asm, src and inc. The final folder structure is shown in Figure 1. GXX Lab3 drivers asm inc src Figure 1: The project folder structure Create a new file main.c and save it in the GXX Lab3 folder. Next, open the Altera Monitor Program and create a new project. Select the created folder GXX Lab3 as the project directory, name the project GXX Lab3, set the architecture to ARM Cortex-A9 and click ‘Next’. When asked to select a system, select De1-SoC Computer from the drop-down menu and click ‘Next’. Set the program type as C Program and click ‘Next’. In the next menu, add main.c to the source files. In the System Parameters menu, ensure that the board is detected in the ‘Host connection’ dialogue box and click ‘Next’. Finally, in the memory settings menu, change the Linker Section Presents from ‘Basic’ to ’Exceptions’ and click ‘Finish’. 2 2 Basic I/O For this part, it is necessary to refer to sections 2.5.6 – 2.5.10 (pp. 8 – 10) and 3.4 (pp. 20 – 21) in the De1-SoC Computer Manual. Brief overview The hardware setup of the I/O components is fairly simple to understand. The ARM cores have designated addresses in memory that are connected to hardware circuits on the FPGA, and these hardware circuits in turn interface with the physical I/O components. In the case of most of the basic I/O, the FPGA hardware can be as simple as a direct mapping from the I/O terminals to the memory address designated to it. For instance, the state of the slider switches is available to the FPGA on bus of 10 wires which carry either a logical ’0’ or ’1’. This bus can be directly passed as ’write-data’ to the memory address reserved for the slider switches (0xFF200040 in this case). It is useful to have slightly more sophisticated FPGA hardware. For instance, in the case of the push-buttons, in addition to knowing the state of the button it is also helpful to know whether a falling edge is detected, signalling a keypress. This can be achieved by a simple edge detection circuit in the FPGA. The FPGA hardware to interface with the I/O is part of the De1-SoC computer, and is loaded when the .sof file is flashed onto the board. This section will deal with writing assembly code to control the I/O interact by reading from and writing to memory. Getting started: Drivers for slider switches and LEDs • Slider switches: Create a new assembly file called slider switches.s in the GXX Lab3/drivers/asm directory. Create a new subroutine labelled read slider switches ASM, which will read the value at the memory location designated for the slider switches data into the R0 register, and then branch to the link register. Make the subroutine visible to other files in the project by using the .global assembler directive. Remember to use the ARM function calling convention, and save the context if needed!. Next, create a new header file called slider switches.h in the GXX Lab3/drivers/inc directory. The header file will provide the C function declaration for the slider switches assembly driver. Declare the function as extern int read slider switches ASM(), and make use of preprocessor directives to avoid recursive inclusion of the header file. To help get started, code for the slider switches driver has been provided in Figure 2. Use this as a template for writing future driver code. • LEDs: Create a new assembly file called LEDs.s in the GXX Lab3/drivers/asm directory. Create two subroutines – read LEDs ASM and write LEDs ASM. Again, export both subroutines using the .global assembler directive Similar to the slider switches driver, the read LEDs ASM subroutine will load the value at the LEDs memory location into R0 and then branch to LR. The write LEDs ASM subroutine will store the value in R0 at the LEDs memory location, and then branch to LR. Create a new header file called LEDs.h in the GXX Lab3/drivers/inc directory. Provide function declarations for both the subroutines. The function declaration will not be the exact same as in the slider switches; one of these functions will have to accept an argument! 3 (a) Assembly file (b) Header file Figure 2: Code for the slider switches driver • Putting it together: Fill in the main.c file in the GXX Lab3 directory. The main function will include the header files for both the drivers, and will send the switches state to the LEDs in an infinite while loop. The code for this file is shown in Figure 3. Figure 3: Code for the main.c file Next, open the project settings and add all the driver files to the project. Compile and load the project onto the De1-SoC computer, and run the code. The LED lights should now turn on and off when the corresponding slider switch is toggled. Slightly more advanced: Drivers for HEX displays and push-buttons Now that the basic structure of the drivers has been introduced, custom data types in C will be used to write drivers that are more readable and easier to implement. In particular, the following two drivers will focus on using enumerations in C. • HEX displays: As in the previous parts, create two files HEX displays.s and HEX displays.h and place them in the correct folders. The code for the header file is provided in Figure 4. Notice the new datatype HEX t defined in the form of an enumeration, where each display is given a unique value based on a one-hot encoding scheme. This will be useful when writing to multiple displays in the same function call. Write the assembly code to implement the three functions listed in the header file. The HEX t argument can be treated as an integer in the assembly code. The subroutine should check the argument for all the displays HEX0-HEX5, and write to whichever ones have been asserted. A loop may be useful here! HEX clear ASM will turn off all the segments of all the HEX displays passed in the argument. Similarly, HEX flood ASM will turn on all the segments. The final function HEX write ASM 4 Figure 4: Code for the HEX displays.h file takes a second argument val, which is a number between 0-15. Based on this number, the subroutine will display the corresponding hexadecimal digit (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F) on the display(s). A sample program is shown in Figure 5 to demonstrate how multiple displays can be controlled in the same function call. Since the value for each display is based on a one-hot encoding scheme, the logical OR of all the displays will assert the bits for all the displays. Figure 5: Sample program that uses the HEX displays driver • Pushbuttons: Create two files pushbuttons.s and pushbuttons.h and place them in the correct folders. Write the assembly code to implement the functionality described in the header file, as shown in Figure 6 • Putting it together: Modify the main.c file to create an application that uses all of the drivers created so far. As before, the state of the slider switches will be mapped directly to the LEDs. Additionally, the state of the last four slider switches SW3-SW0 will be used to set the value of a number from 0-15. This number will be displayed on a HEX display when the corresponding pushbutton is pressed. For example. pressing KEY0 will result in the number being displayed on HEX0. Since there are no pushbuttons to correspond to HEX4 and HEX5, switch on all the segments of these two displays. Finally, asserting slider switch SW9 should clear all the HEX displays. 5 Figure 6: Code for the pushbuttons.h file 6 3 Timers For this part, it is necessary to refer to sections 2.4.2 (p. 4) and 3.2 (p. 20) in the De1-SoC Computer Manual. Brief introduction Timers are simply hardware counters that are used to measure time and/or synchronize events. They run on a known clock frequency that is programmable in some cases (by using a phase-locked loop). Timers are usually (but not always) down counters, and by programming the start value, the time-out event (when the counter reaches zero) occurs at fixed time intervals. HPS timer drivers For this section, the drivers have been provided. Download the two files HPS TIM.s and HPS TIM.h from MyCourses and place them in the correct folders. The code for the header file is shown in Figure 7. Figure 7: Code for the HPS TIM.h file This driver uses a new concept in C – structures. A structure is a composite datatype that allows the grouping of several variables to be accessed by a single pointer. They are similar to arrays, except that the individual elements of a structure can be of different datatypes! This driver will help demonstrate how structures can be useful by modifying multiple parameters easily. 7 Notice how the first subroutine HPS TIM config ASM takes a struct pointer as an argument. The reason for this is that if a struct is passed directly to a function, the compiler unpacks the struct elements at compile time and passes them as individual arguments to the function. Since in most cases the number of arguments will be greater than the number of argument registers, the compiler will place the extra arguments on the stack. This is perfectly fine if all the code is handled by the compiler, but since this lab requires handwritten assembly drivers, it causes the programmer a lot of extra overhead when retrieving the arguments in the assembly subroutine. By passing a struct pointer, the individual elements can be easily accessed at the corresponding offset from the base address passed in the pointer. For instance, the timeout element can be accessed in the assembly subroutine via a load instruction from the address in R0 offset by 0x4. Notice how the timeout struct element is given in microseconds. This hides the hardware specific details of the timer from the C programmer. Since all of the HPS timers do not run on the same clock frequency, the subroutine calculates the correct load value for the corresponding timer in order to achieve the desired timeout value. Similarly, the last three struct elements should be set to 1 to be enabled, and 0 to be disabled. The second subroutine HPS TIM read INT ASM supports multiple timer instances passed in the argument. The return value is an integer that should be interpreted as a 4-bit one-hot encoded number, with bit 0 corresponding to the S-bit of TIM0, and so on. Thus this function can be used to read the S-bit of just one timer, or can also be used to read the S-bit of all four timers, using just a single function call in both cases. Similarly, the other two subroutines also support multiple timer instances passed in the argument. A sample program that uses the HPS timer driver is shown in Figure 8. Notice how all four HPS timers are configured to have a 1 second timeout in the same function call. The program will count from 0-15 on all four HEX displays at the same rate of 1 second. It is important to remember that the configuration values in the struct are implemented at a level of abstraction above the hardware, with the aim of providing a better hardware interface to the C programmer. How these values are then used in the assembly driver is governed by the hardware documentation (De1-SoC computer manual). Recreating this sample program will prove to be a useful exercise before attempting the application in the next section. Creating an application: Stopwatch! Create a simple stopwatch using the HPS timers, pushbuttons, and HEX displays. The stopwatch should be able to count in increments of 10 milliseconds. Use a single HPS timer to count time. Display milliseconds on HEX1-0, seconds on HEX3-2, and minutes on HEX5-4. PB0, PB1, and PB2 will be used to start, stop and reset the stopwatch respectively. Use another HPS timer set at a faster timeout value (5 milliseconds or less) to poll the pushbutton edgecapture register. 8 Figure 8: Sample program that uses the HPS timer driver 9 4 Interrupts For this part, it is necessary to refer to section 3 (pp. 19-32) in the De1-SoC Computer Manual. Additional information about the interrupt drivers that are provided can be found in ’Using the ARM Generic Interrupt Controller’ which is available on myCourses. Brief introduction Interrupts are hardware or software signals that are sent to the processor to indicate that an event has occurred that needs immediate attention. When the processor receives an interrupt, it pauses the current code execution, handles the interrupt by executing code defined in an Interrupt Service Routine (ISR), and then resumes normal execution. Apart from ensuring that high priority events are given immediate attention, interrupts also help the processor to utilize resources more efficiently. Consider the polling application from the previous section, where the processor periodically checked the pushbuttons for a keypress event. Asynchronous events such as this, if assigned an interrupt, can free the processors time and use it only when required. Using the interrupt drivers Download the following files from myCourses: • int setup.c • int setup.h • ISRs.s • ISRs.h • address map arm.h Within the GXX Lab3/drivers/ directory, place C files in the src, header files in the inc, and assembly files in the asm directories. Only the ISRs.s and ISRs.h files will need to be modified in applications. Do not modify the other files Before attempting this section, get familiarized with the relevant documentation sections provided in the introduction. To demonstrate how to use the drivers, a simple interrupt based application using HPS TIM0 is shown. Note: Ensure that in the memory settings menu in the project settings, the Linker Section Presets has been changed from ‘Basic’ to ’Exceptions’! To begin, the code for the main.c file is shown in Figure 9. The int setup() function is the only thing needed to configure the interrupt controller and enable the desired interrupt IDs. It takes two arguments: an integer whose value denotes the number of interrupt IDs to enable, and an integer array containing these IDs. In this example, the only interrupt ID enabled is 199, corresponding to HPS TIM0. After enabling interrupts for the desired IDs, the hardware devices themselves have to be programmed to generate interrupts. This is done in the code above via the HPS timer driver. Instructions for enabling interrupts from the different hardware devices can be found in the documentation. 10 Figure 9: Interrupts example: The main.c file Now that HPS TIM0 is able to send interrupts, ISR code is needed to handle the interrupt events. Notice how in the while loop of the main program, the value of hps tim0 int flag is checked to see if an interrupt has occurred. The ISR code is responsible for writing to this flag, and also for clearing the interrupt status in HPS TIM0. When interrupts from a device are enabled and an interrupt is received, the processor halts code execution and branches to the appropriate subroutine in the ISRs.s file. This is where the ISR code should be written. Figure 10 shows the ISR code for HPS TIM0. In the ISR, the interrupt status of the timer is cleared, and the interrupt flag is asserted. Finally, in order for the main program to use the interrupt flag, it is declared in the ISRs.h file as shown in Figure 11. IMPORTANT: When ISR code is being executed, the processor has halted normal execution. Lengthy ISR code will cause the application to freeze. ISR code should be as lightweight as possible! Interrupt based stopwatch! Modify the stopwatch application from the previous section to use interrupts. In particular, enable interrupts for the HPR timer used to count time for the stopwatch. Also enable interrupts for the pushbuttons, and determine which key was pressed when a pushbutton interrupt is received. There is no need for the second HPS timer that was used to poll the pushbuttons in the previous section. 11 Figure 10: Interrupts example: The ISR assembly code 12 Figure 11: Interrupts example: Flag declaration in ISRs.h 13 5 Grading The TA will ask to see the following deliverables during the demo (the corresponding portion of your grade for each is indicated in brackets): • Slider switches and LEDs program (10%) • Entire basic I/O program (15%) • Polling based stopwatch (30%) • Interrupt based stopwatch (25%) Full marks are awarded for a deliverable only if the program functions correctly and the TA’s questions are answered satisfactorily. A portion of the grade is reserved for answering questions about the code, which is awarded individually to group members. All members of your group should be able to answer any questions the TA has about any part of the deliverables, whether or not you wrote the particular part of the code the TA asks about. Full marks are awarded for a deliverable only if the program functions correctly and the TA’s questions are answered satisfactorily. Finally, the remaining 20% of the grade for this Lab will go towards a report. Write up a short (3-4) page report that gives a brief description of each part completed, the approach taken, and the challenges faced, if any. Please don’t include the entire code in the body of the report. Save the space for elaborating on possible improvements you made or could have made to the program. Your final submission should be a single compressed folder that contains your report and all the code files, correctly organized (.c, .h and .s). This Lab will run for five weeks, from February 19th to March 23rd, along with Lab 4. There will be no lab sessions during reading week, March 5th to March 9th. You should demo your code within the other active weeks within your assigned lab period. The report for Lab 3 is due by 11:59 pm, March 30th.In this lab will use the high level I/O capabilities of the DE1-SoC computer. In particular, the tasks will: • Use the VGA controller to display pixels and characters. • Use the PS/2 port to accept input from a keyboard • Use the audio controller to play generated tones 1 1 VGA For this part, it is necessary to refer to section 4.2 (pp 40-43) of the De1-SoC Computer Manual. Brief overview of the De1-SoC computer VGA interface The VGA controller hardware has already been introduced in the ECSE 222 labs. The De1-SoC computer has a built in VGA controller, and the data displayed to the screen is acquired from two sections in the FPGA on-chip memory – the pixel buffer and the character buffer – which are described in sufficient detail in section 4.2.1 and 4.2.3 of the De1-SoC Computer Manual. For this lab, it is not required to make use of the double buffering feature described in the manual. VGA driver Create two files VGA.s and VGA.h and place them in the correct folders. The code for the header file is shown in Figure 1. Figure 1: Code for the VGA.h file The subroutines VGA clear charbuff ASM and VGA clear pixelbuff ASM should clear (set to 0) all the valid memory locations in the character buffer and pixel buffer respectively. VGA write char ASM should write the ASCII code passed in the third argument to the screen at the (x,y) coordinates given in the first two arguments. Essentially, the subroutine will store the value of the third argument at the address calculated with the first two arguments The subroutine should check that the coordinates supplied are valid (i.e. x = [0,79] and y = [0,59]). VGA write byte ASM should write the hexadecimal representation of the value passed in the third argument to the screen. This means that this subroutine will print two characters to the screen! (For example, passing a value of 0xFF in byte should result in the characters ’FF’ being displayed on the screen starting at the x,y coordinates passed in the first two arguments) Again, check that the x and y coordinates are valid, taking into account that two characters will be displayed. Both the above subroutines should only access the character buffer memory. Finally, the VGA draw point ASM subroutine will draw a point on the screen with the colour as indicated in the third argument, by accessing only the pixel buffer memory. This subroutine is very similar to the VGA write char ASM subroutine 2 NOTE: Use suffixes ‘B’ and ‘H’ with the assembly memory access instructions in order to read/modify bytes/half-words Simple VGA application Build a C based application to test the functionality of the VGA driver. Write three functions as shown in Figure 2 Figure 2: C functions used to test the VGA driver Use the pushbuttons and slider switches as follows: • PB0 is pressed: if any of the slider switches is on, call the test byte() function, otherwise, call the test char() function. • PB1 is pressed: call the test pixel() function. • PB3 is pressed: clear the character buffer. • PB4 is pressed: clear the pixel buffer. 3 2 Keyboard For this part, it is necessary to refer to section 4.5 (pp 45-46) in the De1-SoC Computer Manual. Brief overview of the PS/2 Keyboard Protocol For the purpose of this lab, a very high level description of the PS/2 keyboard protocol is given. A more detailed description can be found at this link. The PS/2 bus provides data about keystroke events by sending hexadecimal numbers called scan codes, which for this lab will vary from 1-3 bytes in length. When a key on the PS/2 keyboard is pressed, a unique scan code called the make code is sent, and when the key is released, another scan code called the break code is sent. The scan code set used in this lab can be found here. Two other important parameters involved are the typematic delay and the typematic rate. When a key is pressed, the corresponding make code is sent, and if the key is held down, the same make code is repeatedly sent at a constant rate after an initial delay. The make code will stop being sent only if the key is released or another key is pressed. The initial delay between the first and second make code is called the typematic delay, and the rate at which the make code is sent after this is called the typematic rate. The typematic delay can range from 0.25 seconds to 1.00 second and the typematic rate can range from 2.0 cps (characters per second) to 30.0 cps, with default values of 500 ms and 10.9 cps respectively. (a) Key ’a’ is pressed and released (b) Key “a” is pressed, held down, and then released Figure 3: Example of data received on the PS/2 bus 4 PS/2 keyboard driver Create two files ps2 keyboard.s and ps2 keyboard.h and place them in the correct folders. For this lab, simply implement a subroutine with the following specifications: • Name: read PS2 data ASM • Argument: A char pointer variable data, in which the data that is read will be stored • Return type: Integer that denotes whether the data read is valid or not • Description: The subroutine will check the RVALID bit in the PS/2 Data register. If it is valid, then the data from the same register should be stored at the address in the char pointer argument, and the subroutine should return 1 to denote valid data. If the RVALID bit is not set, then the subroutine should simply return 0. Simple keyboard application Create a simple application that uses the PS/2 keyboard and VGA monitor. The application should read raw data from the keyboard and display it to the screen if it is valid. Only the VGA write byte ASM subroutine is needed from the VGA driver, and the input byte is simply the data read from the keyboard. Note: In the program, keep track of the x,y coordinates where the byte is being written. For example, write the first byte at (0,0) and the second byte at (3,0) and so on until the first line on the screen is full, and then start writing bytes at (0,1), (3,1), (5,1) etc. A gap of 3 x co-ordinates is given since each byte will display two characters, and one more for a space between each byte. 3 Audio For this part, it is necessary to refer to section 4.1 (pp 39-40) of the De1-SoC Computer Manual Write a driver for the audio port following the same procedure introduced so far. The driver should only have one subroutine. The subroutine should take one integer argument and write it to both the left and the write FIFO only if there is space in both the FIFOs (Hint: Use the value of WSLC and WSRC in the subroutine). The subroutine should return an integer value of 1 if the data was written to the FIFOs, and return 0 otherwise. Use the driver in an application that plays a 100 Hz square wave on the audio out port. The frequency can be achieved by knowing the sampling rate of of the audio DAC. For example, if the sampling rate is 100 samples per second and a 2 Hz square wave is to be played, that means there are two complete cycles of the wave contained in 100 samples, so for 25 samples a ‘1’ should be written to the FIFOs, and for 25 samples a ‘0’ should be written to the FIFOs. For this lab, find the sampling rate from the manual and calculate the number of samples for each half cycle of the square wave. Finally, write 0x00FFFFFF and 0x00000000 to the FIFO instead of ‘1’ and ‘0’. 5 4 Grading The TA will ask to see the following deliverables during the demo (the corresponding portion of the grade for each is indicated in brackets): • VGA (30%) • P/2 Keyboard (20%) • Audio (20%) Full marks are awarded for a deliverable only if the program functions correctly and the TA’s questions are answered satisfactorily. A portion of the grade is reserved for answering questions about the code, which is awarded individually to group members. All members of your group should be able to answer any questions the TA has about any part of the deliverables, whether or not you wrote the particular part of the code the TA asks about. Full marks are awarded for a deliverable only if the program functions correctly and the TA’s questions are answered satisfactorily. Finally, the remaining 20% of the grade for this Lab will go towards a report. Write up a short (2-3) page report that gives a brief description of each part completed, the approach taken, and the challenges faced, if any. Please don’t include the entire code in the body of the report. Save the space for elaborating on possible improvements you made or could have made to the program. Your final submission should be a single compressed folder that contains your report and all the code files, correctly organized (.c, .h and .s). This Lab will run for two weeks, from March 12th to March 23rd. Demos for Lab 4 will begin in the week of March 19th to March 23rd, and demos will also be accepted in the week of March 26th to March 30th, within your assigned lab section. The report for Lab 4 is due by 11:59 pm, March 30th.In this lab, you will combine the low-level ARM programming techniques you have acquired in the course by implementing a musical synthesizer (or “synth”). 1 Make Waves We are providing you with drivers for writing to the audio codec, as well as a “.s” file with a wavetable containing one period of a 1 Hz sine wave at a sampling frequency of 48000 Hz. To play a note with frequency f using the wavetable, generate a signal using the following equations for every sampling instant t: index = (f ∗ t) mod 48000, signal[t] = amplitude ∗ table[index]. If more than one note is played at the same time, compute the sample for each note and add them together. If the index is not an integer, you can calculate table[index] by linear interpolation using the two nearest samples. For example, table[10.73] := (1-0.73)*table[10] + 0.73*table[11]. You should write a function which takes as input f and t and returns signal[t]. Use a timer to feed the generated samples to the audio codec periodically. 2 Control Waves It should be possible for the user to play the synth using a PS/2 keyboard. Table 1 shows the notes your synth should play, the key of the PS/2 keyboard each note should map to, and the frequency of the note in Hz. You should also implement a volume control with the keyboard so that the user can turn the volume (amplitude) up or down. This is the minimum functionality you must implement; you can also implement other notes and features, such as different voices. 3 Display Waves In addition to playing the waveform, you should display the waveform on the lab computer monitor, as in Figure 1. 1 Table 1: Note Mapping Note Key Frequency C A 130.813 Hz D S 146.832 Hz E D 164.814 Hz F F 174.614 Hz G J 195.998 Hz A K 220.000 Hz B L 246.942 Hz C ; 261.626 Hz Figure 1: Waveform display for a single note 4 Presentation Prepare a 10-minute presentation for the TAs and course instructor describing your synth, its software architecture, the problems you encountered during the design process, and the solutions you developed for those problems. 5 Grading You will be evaluated according to the following criteria: • Audio sounds correct (12.5%) • Note control works (12.5%) • Volume control works (12.5%) • Display works (12.5%) • Does the code follow good software development principles (style, efficiency, clear commenting, appropriate use of source files, code reuse, etc.)? (25%) • Presentation quality (25%) The final date for demoing and submitting the final report is on the last day of classes, 16th April 2018. A demo timetable and guidelines for submitting the report will be posted on MyCourses.
Requirements: • Write a WebGL program that creates and visualizes a random triangle. Name your source code hw1.html and hw1.js. The program should meet the following requirements: – Set the title of the program to “hw1” (must appear on title bar). – Set the background color to black. – Create triangle vertices at 3 random locations. Create random coordinates so that each vertex may possibly be positioned anywhere within canvas, but never outside. – Create and assign 3 random colors for the 3 vertices. These 3 colors must be linearly interpolated within the triangle. – Use drawArrays function to visualize the triangle on canvas. – Thus, every time you hit F5 (refresh) key, the canvas must display a new random triangle at a random position, with random size and random color gradient (see Fig. 1 ∼ 2). The triangle vertices must never go out of bounds. Figure 1: Random triangle 1 1 Figure 2: Random triangle 2 What to submit: • Submit all your source files (.html, .js) that are needed for compilation, including library files/folders. Missing library files/folders will lead to point deduction. How to submit: • Use Canvas Assignment Submission system to submit your source files. • Make sure to zip all your files/folders into hw1.zip, then submit your hw1.zip as a single file. Policy • Do all the assignments on Chrome Development Tools using HTML, JavaScript, and GLSL ES. • At the top of each source file, provide comments specifying the author, date, and a brief description of the file. • Source code must contain enough comments here and there to make it easy enough to follow. Insufficient comments could lead to point deduction. • Incomplete program will get almost no credit (e.g., program does not run due to compile errors or program terminates prematurely due to run-time errors). • Thou shall not covet thy neighbor’s code. If identical (or nearly identical) submissions are found among students, every student involved will get automatic zero for the assignment. The same goes for copying existing code from online source. • If a student makes multiple submissions, only the last submission will be considered valid.Requirements: • Write a WebGL program that creates and visualizes random polygons (n-gons). Name your source code hw2.html and hw2.js. The program should meet the following requirements: – Set the title of the program to “hw2” (must appear as such on title bar). – The program generates 20 random polygons at random positions with random colors (see Fig. 1). – Each polygon must have a random number of vertices (between 3 and 9). – Each polygon must continuously rotate and scale (see accompanying video on Canvas). Note that the rotation must be done in-place about its own center, not about the origin. Hint: first translate the polygon to the origin, then rotate, then translate it back to its original position. – The scaling must go back and forth between scaling factors of 1 and 0 as upperbound and lowerbound, respectively. – Each time you hit F5 (refresh), the canvas must display a new set of 20 random polygons rotating and scaling in-place (See Fig. 1 – 2). Figure 1: Rotating and scaling polygons 1 1 Figure 2: Rotating and scaling polygons 2 What to submit: • Submit all your source files (.html, .js) that are needed for compilation, including library files/folders. Missing library files/folders will lead to point deduction. How to submit: • Use Canvas Assignment Submission system to submit your source files. • Make sure to zip all your files/folders into hw2.zip, then submit your hw2.zip as a single file. Policy • Do all the assignments on Chrome Development Tools using HTML, JavaScript, and GLSL ES. • At the top of each source file, provide comments specifying the author, date, and a brief description of the file. • Source code must contain enough comments here and there to make it easy enough to follow. Insufficient comments could lead to point deduction. • Incomplete program will get almost no credit (e.g., program does not run due to compile errors or program terminates prematurely due to run-time errors). • Thou shall not covet thy neighbor’s code. If identical (or nearly identical) submissions are found among students, every student involved will get automatic zero for the assignment. The same goes for copying existing code from online source. • If a student makes multiple submissions, only the last submission will be considered valid.Requirements: • Write a WebGL program that creates symmetric sine wave animation. Name your source code hw3.html and hw3.js. The program should meet the following requirements: – Set the title of the program to “hw3” (must appear as such on title bar). – Modify wave.js (m3.zip) so that the sine wave would be symmetric across y-axis (left half and right half are like twins but moving in the opposite directions), as shown in Fig. 1. – Also see the accompanying video. Your mission is to reproduce the program shown in the video. Figure 1: Symmetric sine wave What to submit: • Submit all your source files (.html, .js) that are needed for compilation, including library files/folders. Missing library files/folders will lead to point deduction. • Make sure your library folder/files are in the right location relative to your main program (.html), such that when your main program (.html) is clicked as is, it should run without problem. 1 How to submit: • Use Canvas Assignment Submission system to submit your source files. • Make sure to zip all your files/folders into hw3.zip, then submit your hw3.zip as a single file. Policy • Do all the assignments on Chrome Development Tools using HTML, JavaScript, and GLSL ES. • At the top of each source file, provide comments specifying the author, date, and a brief description of the file. • Source code must contain enough comments here and there to make it easy enough to follow. Insufficient comments could lead to point deduction. • Incomplete program will get almost no credit (e.g., program does not run due to compile errors or program terminates prematurely due to run-time errors). • Thou shall not covet thy neighbor’s code. If identical (or nearly identical) submissions are found among students, every student involved will get automatic zero for the assignment. The same goes for copying existing code from online source. • If a student makes multiple submissions, only the last submission will be considered valid.Requirements: • Write a WebGL program that does a simple image processing task. Name your source code hw4.html and hw4.js. The program should meet the following requirements: – The program displays an image and lets user adjust the hue. (Hint: you may first convert RGB color to HSV color, then adjust the hue component). – The image should be accessed through its URL address. Do not include an actual image file in your submission. – Implement dat.gui scroll bar widget so the user can adjust hue interactively (see Fig. 1). – Also see the accompanying demo video. Your mission is to reproduce the program in the video. – The slider value should range from −180 to 180. This is because hue is typically expressed by an angle on color wheel, and the user-selected value represents how much the orignal pixel color shifts along the color wheel in terms of degree angle. Note that since 180 degree angle is the same as −180 degree angle, they should result in the same outputs. What to submit: • Submit all your source files (.html, .js) that are needed for compilation, including library files/folders. Missing library files/folders will lead to point deduction. • Make sure your library folder/files are in the right location relative to your main program (.html), such that when your main program (.html) is clicked as is, it should run without problem. How to submit: • Use Canvas Assignment Submission system to submit your source files. • Make sure to zip all your files/folders into hw4.zip, then submit your hw4.zip as a single file. Policy • Do all the assignments on Chrome Development Tools using HTML, JavaScript, and GLSL ES. 1 Figure 1: Interactive hue adjustment • At the top of each source file, provide comments specifying the author, date, and a brief description of the file. • Source code must contain enough comments here and there to make it easy enough to follow. Insufficient comments could lead to point deduction. • Incomplete program will get almost no credit (e.g., program does not run due to compile errors or program terminates prematurely due to run-time errors). • Thou shall not covet thy neighbor’s code. If identical (or nearly identical) submissions are found among students, every student involved will get automatic zero for the assignment. The same goes for copying existing code from online source. • If a student makes multiple submissions, only the last submission will be considered valid.Requirements: • Write a WebGL program that meets the following requirements. Name your source code hw5.html and hw5.js. – The program models a 3D cylinder and displays it using wireframe rendering (see Fig. 1). – The model must consist of top face (n-gon), bottom face (n-gon), and side faces (rectangles). – Each n-gon (top/bottom faces) must consist of n triangles in the form of triangle fan (see Fig. 1). – Each of the side rectangles must consist of 2 triangles (see Fig. 1). – The cylinder must be rotating constantly to show the model from various angles (see video). Figure 1: WireCylinder What to submit: • Submit all your source files (.html, .js) that are needed for compilation, including library files/folders. Missing library files/folders will lead to point deduction. 1 • Make sure your library folder/files are in the right location relative to your main program (.html), such that when your main program (.html) is clicked as is, it should run without problem. How to submit: • Use Canvas Assignment Submission system to submit your source files. • Make sure to zip all your files/folders into hw5.zip, then submit your hw5.zip as a single file. Policy • Do all the assignments on Chrome Development Tools using HTML, JavaScript, and GLSL ES. • At the top of each source file, provide comments specifying the author, date, and a brief description of the file. • Source code must contain enough comments here and there to make it easy enough to follow. Insufficient comments could lead to point deduction. • Incomplete program will get almost no credit (e.g., program does not run due to compile errors or program terminates prematurely due to run-time errors). • Thou shall not covet thy neighbor’s code. If identical (or nearly identical) submissions are found among students, every student involved will get automatic zero for the assignment. The same goes for copying existing code from online source. • If a student makes multiple submissions, only the last submission will be considered valid.Requirements: • Write a WebGL program that meets the following requirements. Name your source code hw6.html and hw6.js. – The program builds on Polyhedron GUI.js (see Fig. 1). – See the accompanying video. Your program should basically look and work like the one in the video. – Add a checkbox light? which, if checked, smoothly rotates light on top of the currently selected object using y-roll (see video). – If unchecked, the light stops rotating and stays right where it is now until it’s checked again (see video). – All other GUI menu items should work the same as before (see video). Figure 1: Rotating Light 1 What to submit: • Submit all your source files (.html, .js) that are needed for compilation, including library files/folders. Missing library files/folders will lead to point deduction. • Make sure your library folder/files are in the right location relative to your main program (.html), such that when your main program (.html) is clicked as is, it should run without problem. How to submit: • Use Canvas Assignment Submission system to submit your source files. • Make sure to zip all your files/folders into hw6.zip, then submit your hw6.zip as a single file. Policy • Do all the assignments on Chrome Development Tools using HTML, JavaScript, and GLSL ES. • At the top of each source file, provide comments specifying the author, date, and a brief description of the file. • Source code must contain enough comments here and there to make it easy enough to follow. Insufficient comments could lead to point deduction. • Incomplete program will get almost no credit (e.g., program does not run due to compile errors or program terminates prematurely due to run-time errors). • Thou shall not covet thy neighbor’s code. If identical (or nearly identical) submissions are found among students, every student involved will get automatic zero for the assignment. The same goes for copying existing code from online source. • If a student makes multiple submissions, only the last submission will be considered valid.
Problem 0: We use a “let” statement to… let x = 100; Create a zip archive containing this file and upload it to CMS before the deadline. Please check to make sure that the data uploaded are what you intend to submit. 1. For each of the following visualizations, identify the marks used and visual channels employed from the list provided. Be as exhaustive as possible. You do not need to supply the precise data attribute – you only need to write the marks and visual channels used. Possible visual channels: Aligned Position (x or y); Unaligned Position (x or y); Aligned Length; Unaligned Length; Area; Volume; Color Hue; Color luminosity; EXAMPLE: Marks: Blue rectangles Channels: Varying the vertical aligned length and horizontal aligned position of rectangles A) B) C) (Note: The row of numbered items at the top (1.SS, 2.CoS, etc.) are individual books in the series. Word position continues through the entire series of books from start to end) 2. For each of the following items in the list, please: A: Identify whether it is a canonical Javascript type B: If the type is a canonical Javascript type, please provide an example in your section using console.log(typeof( ... )). C: If applicable, identify any unusual or unexpected typeof() behavior for the type. a) number; b) int; c) unicode; d) array; e) char; f) class; g) regex; h) string; i) boolean; j) object; k) null; l) function (next page) 3. First, in 1-2 sentences, please define type coercion. Then, in your tag please provide two examples where type coercion produces an answer that is unusual or unexpected (i.e. different from Python output or a case where Python would throw an exception). For each sample, briefly explain why it is unexpected. Then, in the section put both of your code examples into of a console.log() statement so we can see the result (e.g. console.log("apple" + "orange") ) 4. Describe, in your own words, the course policy on late and unreadable work outlined in the syllabus, which is linked from the course website. Goals: Get practice using SVG elements. Your work should be in the form of an HTML file called index.html. At the top of your , please put your name and netID in aelement per problem. Wrap any SVG code for each problem in a element nested within theelement. For this homework we will not be using Javascript. Since we want you to get more experience working with SVG, we would like you to complete this assignment using handwritten SVG elements. Some problems might require numbers like pixel positions which require calculation. Feel free to use whatever tool you prefer in order to compute these, but they should appear in your turn-in homework as literal numbers in the code. You can use a color picker tool to find good colors, but once again they must appear as literal elements in the file. You may not use an SVG authoring tool like Adobe Illustrator. We can tell if you use one, and the time it would take to obfuscate their output is much greater than just doing the assignment yourself. Create a zip archive containing your HTML file and upload to CMS before the deadline. (see next page) 1. Create a 360x360 pixel SVG element. Reproduce this plot using SVG elements: The main plot region, excluding axis labels, should be a square 320x320 pixels in size, running from (20,20) to (340, 340). Reserve the remaining pixels on the outside as padding for the axis labels. Data for the points are provided at the bottom of this homework file. The chart should start with data value [0,0] in the lower left corner (pixel location (20, 340) ) and end with data value [10,10] in the upper right corner (pixel location (340, 20) ). Create a circle mark for each data point. Circle marks should be reasonably sized and in a dark color of your choosing. You should calculate the proper pixel positions for the [x, y] coordinates from the data as necessary. Remember to account for the "padding" pixels when determining positions for points. While we recommend that you hardcode point positions using the 20-340 pixel range, we will also accept submissions that use SVG group translations to relocate the plot region. Add horizontal and vertical gridlines for each integer from 1 to 10 in a light grey. Include elements for axis labels at 0, 5, and 10 as depicted in the image in Arial typeface for both the X and Y axes. They should be *centered* to the side / underneath gridlines using CSS properties (hint: text-anchor and dominant-baseline ). Your result may not look exactly like the figure; we will be grading based on your accuracy in positioning points. (next page) 2. Examine your finished canvas (or the example image). In atag, please identify: a) the marks used for each row of data b) the two visual channels used in this visualization (when answering, please ignore the annotations you added such as elements) 3. Use and elements to create your own version of a Piet Mondrian painting in a 300x300 SVG canvas. Piet Mondrian was an early 20th century artist who, as a member of the De Stijl movement, reduced his art to three primary colors and black lines in a series of famous neoplasticist works. Here are some examples: one, two, three, four. In your own neoplastic work, you must include at least 6 lines and 3 rectangles. elements must use a black stroke and elements must be either white, red, yellow, or blue fill. elements cannot have a stroke – only use a fill for them. If you want black borders, you must use elements. No other colors will be permitted. You may use any additional features you feel would add aesthetic value. If you use a tool to generate coordinates for shapes, please cite that tool. Faithfulness to art history will not be evaluated. We are not grading based on creativity, but obviously poor or incomplete submissions will be penalized. (20pts) Data for scatterplot X Y p1 1.0 9.0 p2 1.5 6.0 p3 2.5 4.0 p4 4.0 2.0 p5 5.0 1.6 p6 6.0 2.4 p7 7.0 3.0 p8 8.0 3.4 p9 9.0 3.6 Bonus problem (no extra credit offered – just for fun) Make a Python program that automatically generates the canvas, lines, labels, and circle marks for problem #2. Your program should take as input a list of dictionary objects, each with “x” and “y” values. Ideally, you should be able to configure the minimum and maximum values you want to display on the x and y axes. You can use min, max, and modulo functions to identify how many gridlines to create and identify where your major axis labels (0,5,10…) should go. Since you know the canvas area is 320x320 and you’ve defined your axis min/max values, you can use some math to figure out where your circles should go. Afterwards, use string composition to output some valid HTML. Use this to check your answer to #2. …this might also help: data = [{"x":1.0 ,"y":9.0}, {"x":1.5 ,"y":6.0}, {"x":2.5 ,"y":4.0}, {"x":4.0 ,"y":2.0}, {"x":5.0 ,"y":1.6}, {"x":6.0 ,"y":2.4}, {"x":7.0 ,"y":3.0}, {"x":8.0 ,"y":3.4}, {"x":9.0 ,"y":3.6}]Goals: Practice using d3 to create SVG elements and set their aesthetic properties. Recognize the effect of data transformations through direct data changes and through scale functions. Practice working with color scales. Your work should be in the form of an HTML file called index.html with oneelement per problem. Wrap any SVG code for each problem in a element following theelement. For this homework we will be using d3.js. In thesection of your file, pleaseimport d3 using this tag: Create a zip archive containing your HTML file and all associated data files (such asdiamonds.json) and upload it to CMS before the deadline. Submissions that do not includedata files may be penalized. Your submission will be graded using a Python web server run ina parent directory containing your zip file contents (e.g. server started in ~/student_hw, withyour homework at ~/student_hw/your_netid/hw3/index.htm) – be sure that it works.1. In your HTML, please create a 300x300 pixel SVG element. Then, select it usingd3.select() in the section of your code. Unlike in HW2 where you drew things by hand, in this problem you are going to use .append() and .style() functions to build and decorate this canvas. Please use d3 functions to create the following elements in your canvas: - A element with the word "INFO3300" centered in the exact middle of the SVG canvas. Use .attr() to locate it. You are welcome to use text-anchor or pixels to center it. The element should be styled to use a black 20px Verdana typeface. - A element at (150,150) with a 4px radius so that we can verify that the text is correctly centered. Please give it a light pink fill color and no stroke. It should appear *behind* the element. - Three (3) elements located in the white space around the text. They should be no larger than 50px x 50px. Give each of them a different stroke color and fill color. No two rectangles should overlap or be the same size. Make sure that the colors you choose make them stand out to the grader. (see next page) 2. In HW2 you reproduced a plot from scratch using SVG. Now create the same plot again, but this time use d3 functions to create it programmatically in a tag. While it should resemble the example image to the right, you don’t need to recreate it exactly, so long as your point and line positions are correct. Create a 360x360 pixel SVG element in HTML. Use a CSS style to give the canvas a 1px light grey solid border. The main plot region, excluding labels, should be a square 320x320 pixels in size, running from (20,20) to (340, 340). Reserve the remaining pixels as padding for the labels. On the last page of this assignment, we have included a code version of the dataset. Go ahead and copy it into your tag. First create x and y scale functions that map from data coordinates to SVG coordinates, using the same minimum and maximum values as the chart domain (0 to 10 for both axes). Remember to account for the "padding" pixels when determining the range of point positions. You can choose whether to implement the margins by adjusting the range of your scales or adding a element and translate(). Next, create the grid of lines for your chart. While there is a way to make gridlines using d3 axes, please manually create gridlines using a for loop. You should create one horizontal line and one vertical line for each number between 0 and 10 (inclusive) in a grey color. Afterwards, add the text labels programmatically. There are a few ways to do this. You could create an array containing the values that need labels (e.g. [0,5,10]) and then loop through it with forEach. You also could do some clever modulo arithmetic while you are looping to make lines. In either case, make a new element for each label with Arial font. Use your scales to help place the text and adjust the dominant-baseline and text-anchor attributes like you did in HW2. You may need to add or subtract a few pixels to position the text nicely. Now, add circles for each point with positions determined by your scales. You don't need to use a data join; it's fine if you just create circles one-by-one in a forEach loop. Circles should have a radius of 10px and have a dark color. 3. Instead of a element, for this question please create a element. For each of the following scales, create a sub-element and answer the following questions: ( If you have a color vision deficiency and cannot perceive hues in a color scale in order to answer a subitem, please instead describe what you see. ) (see next page) A: Is this a sequential or a divergent color scale? Do you think this an effective color scale? Justify your answer in 1-2 sentences. B: This scale is being used to color scatterplot points based on a numeric data attribute that captures the positive or negative sentiment of tweets. Values range from -1 to 1, with negative values moving towards yellow (the left side) and positive values moving towards red (the right side). Middle values remain blue. Is this an effective color scale for this task? Justify your answer in 1-2 sentences. C: To a majority of individuals, this color scale will appear to vary in both hue and luminosity (greyish blue on the left, lime green on the right). However, the hue channel of this scale is not visible for individuals with certain color vision deficiencies. This poses usability issues. Use an online color blindness image testing tool to identify and list which kind(s) of anomalous trichromatic and/or dichromatic color vision deficiencies (e.g. deuteranomaly) would cause a loss of perceivable hue variation (file included in ZIP). [ If you have color vision deficiencies that make the scale’s hue hard to interpret, you have two choices: You can either a) self-disclose your color vision deficiency and describe what the image looks like to you, or b) ask a trusted friend to describe what they see to you. ] D: A data scientist is designing a choropleth map for a new continuous, numeric county-by-county “average life expectancy” data attribute they developed. Would you recommend that they use this rainbow scale to color the counties in their map? Justify your answer in 1-2 sentences. (see last page for data for problem 2) Data for scatterplot in #1 X Y p1 1.0 9.0 p2 1.5 6.0 p3 2.5 4.0 p4 4.0 2.0 p5 5.0 1.6 p6 6.0 2.4 p7 7.0 3.0 p8 8.0 3.4 p9 9.0 3.6 For easier import into your code: data = [{"x":1.0 ,"y":9.0}, {"x":1.5 ,"y":6.0}, {"x":2.5 ,"y":4.0}, {"x":4.0 ,"y":2.0}, {"x":5.0 ,"y":1.6}, {"x":6.0 ,"y":2.4}, {"x":7.0 ,"y":3.0}, {"x":8.0 ,"y":3.4}, {"x":9.0 ,"y":3.6}] Goals: Practice using d3 to create some simple charts. Get more experience importing data and working with loops. Your work should be in the form of an HTML file called index.html with oneelement per problem. If you must add any SVG canvases programmatically, we suggest that you add a
Changing Reference Frames (30 Points) Nearly every robot task requires operating in multiple reference frames. Download and open lidarScan.mat, containing a sample lidar scan (as returned by LidarSensorCreate.m). The 681 data points correspond to the measured ranges (in meters) equally spaced over the angles [−120◦ , 120◦ ]. 1. Edit the file lidar range2xy.m to convert the raw lidar scan into 2D local robot coordinates. Assume the lidar sensor is located at the front of the robot pointing forward (i.e. the sensor pose in local coordinates is [xl , yl , θl ] = [r, 0, 0], where r is the robot radius). The robot’s x-axis points forward and y-axis points left. Assume the robot radius is 0.2 meters. Submit this function in the autograded assignment Homework 1 lidar range2xy on Canvas. 2. Edit the file robot2global.m to transform any 2D point from the local robot coordinates into global coordinates, given the robot’s pose. Submit this function in the autograded assignment Homework 1 robot2global on Canvas. 3. Edit the file global2robot.m to transform any 2D point from global coordinates into local robot coordinates, given the robot’s pose. Submit this function in the autograded assignment Homework 1 global2robot on Canvas. 4. In the same figure, plot using lidar range2xy.m the lidar scan (points in 2D) in the global reference frame assuming the robot pose is • [3, −4, 2π/3] • [0, 3, π/2] Plot each set of points (corresponding to the scan as viewed by the robot) in a different color. Make sure to label your axis and include a legend. Getting to Know the Simulator and Running a Simple Control Program (20 Points) Download the MATLAB CreateSim toolbox (download as zip) https://github.com/autonomousmobilerobots/iRobotCreateSimulatorToolbox download the latest version of the Matlab Toolbox for the Create from https://github.coecis.cornell.edu/AMR/MatlabiRobotCreateRaspPi and add both to your MATLAB path. Review the iRobot Create Simulator User Guide pages 4–10, and the MATLAB Toolbox for the iRobot Create (available on Canvas) pages 11–12. The file turnInPlace.m is a simple control program that reads the robot’s sensor data and makes the robot turn in place. You can use this function as a template for later functions you will write. Make sure the CreateSim toolbox is in your MATLAB path and run SimulatorGUI.m. This will open the simulator interface. Click the Load Map button and select box map from the files provided for this homework. Place the simulated robot anywhere on the map by clicking the Set Position button (click once to set the center location, click again to set the heading direction). Run the control program by clicking the Start button in the Autonomous group (bottom right side of the interface) and selecting turnInPlace.m. 1. What does the command SetFwdVelAngVelCreate (line 73 in turnInPlace.m) do? What are the inputs to this function? 2. The left and right wheel velocities are limited to ±0.5m/s (observe what happens when you increase cmdV and cmdW on lines 66–67 in turnInPlace.m). Edit the program limitCmds.m to appropriately scale the forward and angular velocity commands so the wheel motors don’t saturate (the shape of the trajectory should be maintained, i.e. do not simply use a max function without making sure the trajectory shape remains the same). Submit this function in the autograded assignment Homework 1 limitCmds on Canvas. 3. Edit turnInPlace.m to use limitCmds.m in the appropriate place, with wheel2Center=0.13 and maxV a value that is less than 0.5. From now on, you should always call limitCmds before sending commands to the robot via SetFwdVelAngVelCreate.m. 4. Write a function backupBump.m to have the robot drive forward at constant velocity until it bumps into something. If a bump sensor is triggered, command the robot to back up 0.25m and turn clockwise 30◦ , before continuing to drive forward again. Run the simulator and plot the robot trajectory. Note: To access the sensor data collected during simulation, type global dataStore in the MATLAB Command Window. The ground truth pose of the robot is available in dataStore.truthPose. The sensor data is collected by readStoreSensorData.m; we recommend you take a look at the function to see what sensor information is stored. 5. Write a control function, properly named, to make the robot do something new. What does the function do? Run the simulator using your new control function and plot the robot trajectory. Feedback Linearization (30 Points) The iRobot Create is a non-holonomic vehicle, so we can’t send arbitrary Vx and Vy commands to the robot. Instead we must send V and ω commands, as with SetFwdVelAngVelCreate.m. Feedback linearization approximately converts [Vx, Vy] → [V, ω] via a linear transformation. 1. Write a function feedbackLin.m to transform Vx and Vy commands into corresponding V and ω commands using the feedback linearization technique presented in class for a differential drive robot. (In other words, do not use a turn-then-move control strategy.). Assume the Vx and Vy commands are given with respect to the inertial frame. Submit this function in the autograded assignment Homework 1 feedbackLin on Canvas. 2. In the SimulatorGUI, place the robot near [0, 0] by clicking the Set Position button. For a desired local (body-fixed) control input [Vx, Vy]B = [1, 1], plot the robot trajectory for different values of . 3. Write a function visitWaypoints.m to calculate the desired [V, ω] controls to drive the robot along a series of waypoints (using feedbackLin.m appropriately). The waypoints are given as a nx2 matrix where each row is the (x,y) coordinate of a waypoint. Keep track of which waypoint is being driven 2 toward using the index gotopt, and consider the waypoint reached if the robot is within closeEnough of the waypoint location. 4. Using visitWaypoints.m as the control function with = r (the robot radius, 0.2m) and closeEnough= 0.1, plot the robot trajectories for the following sets of waypoints: [-3 0; 0 -3; 3 0; 0 3] and [-1 0; 1 0 ].Dead Reckoning (45 Points) The iRobot Create encoder information can be read from the distance and angle packets (using functions DistanceSensorRoomba and AngleSensorRoomba, respectively). These packets provide the distance the robot traveled and the angle it rotated since the sensor was last read. 1. Given a known initial configuration (x, y, θ) of the robot within a global frame, the distance traveled d and the angle the robot turned φ, compute the new configuration of the robot. Explain your calculation. Note that you cannot assume a “turn then move” scheme. (Hint: Assume that the robot’s wheels turn at a constant rate between sensor readings.) 2. Edit the function integrateOdom.m to integrate the robot odometry as calculated in part 1 (this is known as “dead reckoning”). Submit this function in the autograded assignment Homework 2 integrateOdom.m on Canvas 3. Generate a trajectory and gather data: No need to submit the control code or the simulator map and config files. (a) Define a map for the simulator. You may use the map from Homework 1 or define a new one. (b) Write a control program that will drive the robot in the simulator. The robot motion should include simultaneous non-zero forward and angular velocity (meaning the robot motion should include arcs). The program should read the odometry, either by periodically calling DistanceSensorRoomba and AngleSensorRoomba and storing the data or by periodically calling the function readStoreSensorData. Make sure the robot runs into a wall at least once. The program should be deterministic, that is the trajectory should be the same in repeated runs. (c) Using ConfigMakerGUI, create a config file that defines errors on the odometry. (d) Run the simulation without a config file (no noise is added to the sensors). Save the data. (e) From the same initial pose as the previous run, run the simulation with a config file. Save the data. 4. Plot in the same figure the true trajectory as captured by the overhead localization, the trajectory for the integrated noiseless odometry (using the function integrateOdom.m with data from the first run) and the trajectory for the integrated odometry which contains errors (using the function integrateOdom.m with data from the second run). Specify what error parameters were used. 5. Did the integrated trajectory from the first run match the overhead localization? Did you expect it to? Explain. 6. How does sensor noise affect the quality of the localization? 7. What might cause errors in odometry measurements? Expected depth measurement (30 points) In this section you will write a function that given the robot pose and the map, predicts the depth measurements. Note that the realsense sensor provides a depth image that corresponds to the depth of obstacles along the sensor-fixed x-axis, as shown in Fig 1 . create object plane of camera x y range depth Figure 1: Depth information 1. Edit the file depthPredict.m to calculate the expected depth measurements (based on the pose) for a robot operating in a known map. These depth measurement correspond to the distance between the sensor and the closest obstacle. Assume the sensor reference frame is not rotated with respect to the robot-fixed reference frame. You may want to use the provided function, intersectPoint.m, which calculates the intersection point of two line segments. Hint: why do we need to provide the sensor-fixed frame origin? Note that the Field of View (FOV) of the depth image is centered around the sensor-fixed x-axis, the first element in the vector is the leftmost point and the last element in the vector is the rightmost point. We recommend looking at the documentation of the RealSenseDist function regarding the format of the depth measurements. Submit this function in the autograded assignment Homework 2 depthPredict.m on Canvas. 2. You may continue to work with the same control program and config file from the previous section, or create new ones. Your config file should have non-zero values for the realsense noise (in the “St. Dev.” column). Make sure you are collecting and saving the following data (in dataStore): • truthPose (measurements from overhead localization) • rsdepth 2 3. In the simulator, load a map (you may use box map), load the config file and run your control function. Save the data. 4. Based on the map and dataStore.truthPose, and given that the sensor (in the simulator) is positioned 0.16m along the X-axis of the robot-fixed frame, calculate the expected depth measurements. Plot the actual (simulated) depth measurement and the expected depth measurements on the same graph. Are they identical? Do you expect them to be? Explain.Localizing a stationary robot (80 Points) A point robot is standing in place in the map described in HW3map.mat which contains the coordinates of all walls in the environment: [x1, y1, x2, y2]. The file stationary.mat contains the sensor measurements for the robot. Each line contains the range measurements in the global North, East, South and West directions. The maximum range of the sensor is less than 3 meters (a measurement of NaN indicates no obstacle within the sensing range). Assume that there is no uncertainty in the angle and that the North and South ranges have noise that is distributed N(0,0.1) and the East and West ranges have noise that is distributed N(0,0.3). All range measurements are independent of each other. Grid localization (30 points) 1. Write the function gridLocalizationStationary.m that returns the pdf representing the location of the robot. This function should accept as input the size of the grid (n × m) where n is the number of cells along the X dimension and m the number fo cells along the Y dimension. Explain how you addressed the measurement issue discussed in class (with respect to where is the measurement?). 2. Assume a 10×10 grid. What is your initial distribution? 3. Plot the pdf – the initial one and the final one (after incorporating all measurements). You may find the function plotGridBelief.m useful. 4. Calculate and plot a pdf for a grid size of 40×22. Plot the final pdf. Do you get the same possible robot location(s) as in part 3? explain. Kalman filter (30 points) 1. Write the function KFStationary.m that estimates the position of the robot using a Kalman Filter. 2. What is your prediction step. Do you need one? 3. How is the update performed? (write the equation) 4. What are you choosing as your initial distribution? why those values? 5. Plot the initial and final position and covariance estimates (1 σ) on the map. (Hint: for plotting the ellipse, do not forget the functions posted at the beginning of the semester on Canvas) 6. Try a different initial distribution. How does that affect the position estimate? 7. Would an EKF be more appropriate for this problem? explain. Test function (autograded) (10 points) 1. Edit the test function on Canvas TestFunHW3.m look for comments that begin with ‘STUDENTS’ and follow the directions. Course staff will use this function to test your code with different inputs and we are using the autograder as a way to ensure the test function runs. We are NOT testing for correctness of the algorithm. Make sure the zip file you submit on Canvas contains this function and all of the functions necessary to run it. Location estimate (10 points) 1. For both filters, would you be able to estimate the location exactly given perfect range information? Explain. (5 points) 2. You are told that the robot’s y coordinate is less than 8. Based on the various pdfs found in the previous sections, can you estimate the true position of the robot? Explain (no need to run the filters) (5 points)Dynamics and measurement functions (40 points) In lab 2, you will be localizing the robot using different filters and different measurements. In this section you will set up the required dynamics and measurement functions. 1. Given that the control action/inputs are the odometry information (distance traveled, angle turned), what function would you use as g(xt−1, ut)? Explain. (Hint: you already wrote the function in Homework 2). 2. Given that the measurement is a depth measurement, what function would you use as h(xt) to predict the measurement? Explain. (Hint: you already wrote the function in Homework 2). 3. Given that the measurement is “GPS” like information (given by the overhead localization/true pose, i.e. [x, y, θ]), explain and write a function hGPS.m that predict the measurement (This should be very simple). Submit this function in the autograded assignment Homework4 hGPS.m on Canvas. 4. In order to use an EKF, one needs to calculate the Jacobian of the update and measurement functions at a given state. Write out the Jacobian Gt = ∂g ∂xt−1 . Write the function GjacDiffDrive.m to output Gt for a particular pose x. Submit this function in the autograded assignment Homework4 GjacDiffDrive.m on Canvas. 5. Write the file HjacDepth.m to output Hdeptht at a particular xt. Explain how you calculate this. (Hint: differentiating the function is difficult, think about using finite differences instead). Submit this function in the autograded assignment Homework4 HjacDepth.m on Canvas. 6. Write out the Jacobian HGP St = ∂h ∂x . Write the function HjacGPS.m to output HGP St at a particular xt (Again, this should be VERY simple). Submit this function in the autograded assignment Homework4 HjacGPS.m on Canvas. Extended Kalman Filter(15 points) In the lab, you will be using the EKF with different measurements. To make switching between measurement types easy, in this section you will write a generic EKF that takes as input the measurement and update functions and as such, can be reused. Write the file EKF.m to perform one prediction & update step of the EKF. To make this file very generic, the functions from the previous section should be inputs to this function and should be passed as anonymous functions (details at the end of the problem set). What are the inputs to the function EKF? what are the outputs? This function is evaluated in the autograded assignment Homework4 testEKF.m on Canvas, where you will have to call your filter to produce the estimated location at time t given all the information in time t − 1 (i.e. one time step). Particle Filter(15 points) Same as the EKF, it is best to write a generic particle filter that can be reused later on. Write a function PF.m that takes in an initial particle set, odometry and depth measurements, prediction and update functions and outputs a new particle set. Assume there is an infinite wall at y = 1, the robot moved one meter forward (d = 1, φ = 0), and all 9 depth measurements are 2 meters. Create an initial particle set of size 30 with uniform distribution in x ∈ [−1, 1], y ∈ [−3, 1] and θ = 0, plot the wall, the initial particle set (x,y position only for each particle), and the particle set after one iteration of the particle filter on the same plot. Use one marker shape for the initial particles and another marker shape for the final particles. Running the filters in the simulator (115 points) 1. Write a function motionControl.m. This function should drive the robot in different directions while reacting to the bump sensor (so that the robot does not try to drive through a wall). The control should be independent of the location and deterministic. Furthermore, this function should: (a) Call the sensor information (using the function readStoreSensorData.m provided in HW 1) (b) Call integrateOdom.m and store the dead reckoning information in dataStore.deadReck (c) Have a clearly identifiable and well commented section describing how to switch between the three methods described below (EKF with GPS data, EKF with depth data, PF with depth data). You will need to be able to switch between these three methods for lab 2. See Questions 4, 5, and 6 for more details. 2. In motionControl.m, create new fields datastore.ekfMu and datastore.ekfSigma (robot pose mean and covariance, respectively). 3. Initialize dataStore.deadReck and datastore.ekfMu to the true initial pose (from dataStore.truthPose) and datastore.ekfSigma to [2, 0, 0; 0, 2, 0; 0, 0, 0.1]. Define a new variable R (process noise covariance matrix) and set it to 0.01I. Define a new variable Q (measurement noise covariance matrix) and set it to 0.001I. What are the dimensions of R and Q? 4. EKF with GPS data: (a) Create noisy GPS measurement by adding gaussian noise to the true pose. What should the noise distribution be? Record this data in dataStore.GPS. (b) In the simulator, load cornerMap and place the robot somewhere near [−4; 2; 0]. Create and load a config file with noise on the depth measurements and the odomerty. What values did you choose for the noise? Make sure the values make sense with respect to R and Q. (c) In motionControl.m, call the EKF with the noisy GPS data and the appropriate functions (dynamics and measurement). 2 (d) Run motionControl.m in the simulator. On the same figure, plot the map and three final trajectories (x,y): dataStore.truthPose (the data from overhead localization), dataStore.deadReck (from integrating the odometry only), and datastore.ekfMu (estimate from the EKF). Also plot the 1-Σ ellipses from datastore.ekfSigma. Note, you only need to plot the x,y position and not the orientation.(You may use the provided function plotCovEllipse.m or any other function that plots ellipses. If you do, make sure to cite the source). (e) Place the robot somewhere near [−4; 2; 0] again. Repeat 4(b–d) using a different initialization for the filter (we want to see what happens to the estimate if the initial belief is different): µ0 = [−2; −1.5; π/2] and Σ0 = [4, 0, 0; 0, 4, 0; 0, 0, 0.02]. (Initialize datastore.deadreckon to the same initial pose estimate µ0 here in (e).) (f) Compare the results of 4(d) and 4(e) – How does the initial estimate affect the robot’s estimate? 5. EKF with depth data: In motionControl.m, call the EKF with the depth data and the appropriate functions (dynamics and measurement). Make sure to write comments in motionControl.m on how to switch between using the GPS and depth measurements. (a) Repeat 3 and 4(b,d). Make sure the dimension of R,Q are correct. (b) Repeat 5(a) using R= 0.001I and Q= 0.01I. (c) Compare the results from 5(a) and 5(b). How do the process and measurement noise covariances affect the robot’s estimate? (d) Does the filter behave as you’d expect? Why or why not? (e) What are some of the problems with using an EKF with depth measurements? (f) What errors do you expect to see when you run the EKF on the physical robot in the lab? 6. PF with depth data: In motionControl.m, create new field datastore.particles. Generate an initial particle set of size 20, with x-location sampled from a uniform distribution between [−5, 0], y-location sampled from a uniform distribution between [−5, 5], and θ sampled from a uniform distribution between [−0.2, 0.2]. Initialize the particle weights to be uniform. Call the PF with the depth data and the appropriate functions (dynamics and measurement). Make sure to write comments in motionControl.m on how to switch between using the EKF and using the PF. (a) In the simulator, load cornerMap and place the robot somewhere near [−4; 2; 0]. Load your noisy config file and run motionControl.m. (b) Plot the initial particles on the map (plot the x,y positions as well as headings). (c) Plot the final particles on the map (x,y position only). (d) For each time step, choose the particle with the highest weight and plot it. You will get the “best” trajectory. Do this for 5 additional particles and plot the 5 trajectories on the same map. Also plot the true trajectories (from datastore.truthPose). (e) Repeat 6(a–d) using a particle set of size 500. (f) Does the filter behave as you’d expect? Why or why not? (g) How does the size of the particle set affect the robot’s estimate? (h) How else could you represent the robot’s estimate (other than just looking at the highest weight particle)? Plot the trajectory of that estimate. Is it closer to the truth? Comparing Filters (30 points) Fill out the following table: 3 Filter Assumptions about This filter is Advantages Disadvantages the system appropriate when Kalman filter Extended Kalman filter Particle filter Using functions as inputs As previously mentioned, for re-usability, we can send the dynamics, measurement and Jacobian functions as parameters to our filter. There are two ways to do this, but only one that is accepted with Autograder on Canvas. Below is a simple example and link for extra information (assume robot2global is defined elsewhere): Anonymous functions – r2g = @(pose, p_xy) robot2global(pose, p_xy); MyComplicatedFilter(r2g) function MyComplicatedFilter(converter) % some calculations to get my_pose, my_xyR y = converter(my_pose, my_xyR); return y More information: https://www.mathworks.com/help/matlab/matlab_prog/anonymous-functions.htmlIntroduction and Setup In the Simulator, load loopMap and run a control program that will drive the robot into walls (you may use the function backupBump.m or write a new function). Make sure you are collecting the following sensor data in dataStore: truthPose, bump and depth. Allow the robot to move around the environment and bump into most (if not all) walls. Access the sensor data in the MATLAB workspace by typing global dataStore, and make sure the data was collected properly. You will use this data in the two mapping sections. Remember that in the simulator, the robot radius is .16, and the sensor origin is [.13 0]. As you have seen, each bump sensor of the Create returns a value of 1 if the sensor is triggered, and 0 otherwise (with no false alarms). Initialize a 25 × 25 occupancy grid of the environment with p0(occ) = 0.5 as the prior occupancy probability for all cells (i.e. `0 = 0). The boundaries of the environment in the x and y directions are [−2.5, 2.5]. You may find the MATLAB function meshgrid.m helpful. Mapping – Occupancy Grid with Bump Sensor (45 points) 1. Plot the occupancy grid boundaries and the robot’s trajectory. Indicate with a marker (e.g. star, triangle) the locations where a bump sensor was triggered. 2. Write a function logOddsBump.m to calculate the log-odds `t(occ) of cells in the grid using only bump sensor measurements. Make sure you allow non-square grids (n × m, where n is the number of cells along the X dimension and m the number of cells along the Y dimension). What are the inputs? what are the outputs? 3. Explain the sensor model you used, assumptions you made in logOddsBump.m, and why they make sense. 4. Write a function plotOccupancyGrid.m that given the log odds and the grid, plots unoccupied cells in white, occupied cells in black, and uncertain cells in shades of gray. You may use colormap(flipud(gray)), pcolor or image to help plot the grid cells. Plot the occupancy grid at three different time steps using the log odds obtained from datastore.truthPose and datastore.bump. 5. If you had to choose for each cell whether it is occupied or free (for example, to use the map in a planning algorithm), what would you do? Apply this method to the grid at the last timestep and plot the result (each cell is assigned either 0 or 1). 6. Repeat (4,5) with a 50 × 50 grid. What do you observe? 7. What differences might you expect to observe between the map generated using simulated bump sensors and one using real bump sensor data? Why? Mapping – Occupancy Grid with Depth Information (45 points) 1. Write a function logOddsDepth.m to calculate the log-odds `t(occ) of cells in the grid using only depth sensor measurements. What are the inputs? what are the outputs? 2. Explain the sensor model you used, assumptions you made in logOddsDepth.m, and why they make sense. 3. Plot the occupancy grid at three different timesteps using the log odds obtained from datastore.truthPose and datastore.rsdepth. 4. Repeat (2,3) with a 50 × 50 grid. What do you observe? 5. What are the pros and cons of using a finer grid resolution? 6. Compare the maps generated using depth with those using the bump sensor. Is one map “better” than the other? Why or why not? 7. What differences might you expect to observe between the map generated using simulated depth sensors and one using real depth sensor data? Why? Test function (10 points) Edit the function TestOccupancyGrid.m that takes as input, • dataStore • `0 (scalar value for the prior occupancy probability of grid cells) • NumCellsX (number of cells in the X axis) • NumCellsY (number of cells in the Y axis) • boundaryX (1×2 vector representing the interval of possible values for X, for example [-2.5 2.5]) • boundaryY (1×2 vector representing the interval of possible values for Y, for example [-2.5 2.5]) outputs, • lFinalBump (final occupancy grid using bump sensor) • lFinalDepth (final occupancy grid using depth sensor) and plots final occupancy grids, one for the bump (as in part 4 of the mapping with bump sensor section) and one for the depth information (as in part 3 of the mapping with depth information section). Plots generated should have meaningful titles and labels. Submit this function in the autograded assignment Homework 5 TestOccupancyGrid.m on Canvas. Course staff will use this function to test your code with different inputs, and we are using the autograder as a way to ensure that the test function runs. We are NOT testing for correctness of the algorithm. Make sure the zip file you submit on Canvas contains this function and all of the functions necessary to run it.
1. (35 points) Regression based methods (a) Split to data into a training set (months 5 to 84) and a test set (months 85 to 108). Fit a least squares regression to training data with the following predictors: yt = β0 + β1t + β2t 2 + +β3x1t + β3x2t + … + β14x11t +β15d1t + β16d2t + β17d3t + ϵt where: xit is an indicator (dummy) for month i (i = 1, 2, , , 11). Note that we only need to use 11 of the 12 monthly indicators in the regression and we skip month 12 dit is a difference at lag i, dit = yt−i − yt−i−1. (b) (5 points) Comment on the significance of the predictors and R2 value. Compute the MSE and RMSE of the fit on the training data. 1 (c) (5 points) Compute the MSE and RMSE of the fit on the test data. (d) (25 points) Now fit a lasso regression to shrink the full model. Experiment with different penalty parameters (referred to as ’gamma’ in sklearn library) and compute the test RMSE for a few cases. Report the most significant predictors based on the lasso optimization. 2. (50 points) Tree based methods (a) (10 points) Fit a regression tree using all predictors . Experiment with a few different values for the depth of the tree and report the train and test MSE and RMSE. (b) (10 points) Fit a bagged regression tree using bagging and using all predictors. Report the train and test MSE and RMSE. (c) (15 points) Fit a random forest. Experiment with different numbers of features and report the train and test MSE and RMSE. (d) Plot the importance of the predictors for the best random forest. (e) (15 points) Fit a boosted tree. Experiment with different depths and learning rates and report the train and test MSE and RMSE. (f) Plot the importance of the predictors for the best boosted tree. 3. (15 points) Interpreting the results. (a) (10 points) Complete the below results summary table. For full regression, you can note the statistically significant predictors at 5%. For lasso you can list the predictors that remain after shrinkage and for random forest and boosted tree you can list the predictors based on the Importance measure order. List also the specifications (maximum depth, maximum number of features etc.) whenever they apply. (b) (5 points) Using the summary table, please explain which three or four predictors are the most important ones to predict the sales of Audis. Which of the methods would you recommend for predictipon for this data? 2 Table 1: Comparison Table Method Train RMSE Test RMSE Predictors Spec. Full Regression Lasso Regression Tree – Bagged Tree – Random Forest Boosted Tree
Part 1: Regression and Model Reduction for Sales Prediction: The data can be found under ’ToyotaSales.csv’. We start by seperating the data into a training set (first 96 months) and a test set (months 97 to 168). 1. (35 points) Implementing a full model with all seasonal predictors and additional polynomial terms and comparing with a reduced model. (a) (20 points) Fit a least squares regression to training data with the following predictors: yt = β0 + β1t + β2t 2 + β3t 3 = β4x1t + β5x2t + … + β15x12t + ϵt where xit is an indicator (dummy) for month i (i = 1, 2, , , 12). Note that we only need to use 11 of the 12 monthly indicators in the regression. We typically skip the first month or the last month of the year but in this case, it might be better for interpretation to skip one of the months in the middle of the year (May or June) since December is a special peak month and January is an off-peak. 1 (b) Comment on the significance of the predictors and R2 value. Compute the MSE, RMSE and MAPE of the fit on the training data. (c) Use the previous model on the test data and compute the MSE, RMSE and MAPE. Comment on the issue of overfitting. (d) (15 points) Now fit a reduced regression model that uses only one of the trend terms and only the indicators for the months of January and December: yt = β0 + β1t + β2x1t + β3x12t + ϵt (e) Comment on the significance of the predictors and R2 value. Compute the MSE, RMSE and MAPE of the fit on the training data. (f) Compare and discuss the test error performances of the full model and the reduced model. Part 2: Logistics Regression and Model Classificatıon for Market Directions: The data can be found under ’ToyotaSalesUp.csv’. We’ll try to predict whether the market for Toyota vehicles moves up (1) or down (0) in month t (the market moves up if yt > yt−1, and moves down otherise). We’ll use the lagged differences and dummies for months of December and January. We start by seperating the data into a training set (first 96 months) and a test set (months 97 to 168). 2. (65 points) Logistic Regression and Classification for Toyota Vehicles Market (a) (50 points) Using the training data, fit a logistic regression to the market direction data (up or down) in month t where the predictors are Lag 1 = yt−1 − yt−2, Lag 2 = yt−2 − yt−3, Lag 3 = yt−3 −yt−4, and Jan(indicator for January) and Dec (indicator for Dec.). (b) Comment on the significance of the predictors. (c) Convert the probability predictions from the model to a class prediction (1 or 0) by using a probability threshold of 1/2. (d) Find the confusion matrix for the classification rule and comment on the error performance. 2 (e) Implement the logistics regression model obtained for the training set on the test set. Find the confusion matrix for the classification rule and comment on the error performance on the test set. Report the AUC measure. (f) (15 points) Repeat the above for a reduced logistics regression model that only uses the predictors Lag1, Lag2 and Dec. (g) Compare the AUC on the test set for the reduced model with the AUC under the full model. Please note that the data is tricky since there are some significant ups and downs in the sales that cannot be explained with our predictors. Part 3 (Bonus Exercise): KNN Classifier for Market Directions: We use the data from Part 2. 3. (10 points) Let’s check the performance of a KNN Classifier. (a) Implement a KNN-classifier that uses the first 96 months as the input set and the months 97 to 168 as the target set using the predictors, Lag1, Lag2, Lag3 and taking the number of neighbours K = 5. Find the confusion matrix and comment on the classification error rates. (b) Experiment with the number of neighbours (K = 1, 7, 11) and commment on the classification error performance.
1. (40 points) Forecasting Coffee Prices (monthly average price index of coffee in commodity markets as reported by the IMF commodity price data portal). This continues from the first HW. (a) Plot the data and visually assess whether there is significant trend and seasonality. (b) Check the ACF and PACF plots after detrending and deasonalizing (if necessary). Check whether there is significant AC visible. (c) Fit an ARIMA model to the whole data set based on the autocorrelation structure and the patterns (trend, seasonality etc.). Explore the significance of the fitted coefficients, the residual diagnostics and assess its performance by calculating the MAE, MAPE and RMSE. 1 (d) Experiment with a different ARIMA model for comparison.Explore the significance of the fitted coefficients, the residual diagnostics and assess its performance by calculating the MAE, MAPE and RMSE. Compare with the previous model. (e) Separate the data into a training set and a test set (first 70 to 80 % of the data should be the training set and the remaining data test set). Fit the two models above on the training set and compute the forecast errors on the test set. (f) Your report for the exercise should include a table similar to the one below. 2. (40 points) We had looked at the monthly Australian Beer Production data. This time we investigate the quarterly production data starting from the first quarter of 1956 to the second quarter of 1994. (a) Plot the generated observations. (b) Fit a SARIMA(0,1,0)(0,1,0,4) model to the whole data (i.e. seasonal differencing of 4 quarters and first order differencing). Explore the significance of the fitted coefficients, the residual diagnostics and the error performance. This could be a benchmark model for other comparisons. (c) Detrend and deseasonalize the data. Plot the Auto-Correlation Function and the Partial Auto-Correlation Function of the detrended and deseasonalized data. (d) Based on the ACF and PACF, fit a SARIMA model to the whole data that has some AR and MA coefficients. Explore the significance of the fitted coefficients, the residual diagnostics and assess its performance by calculating the MAE, MAPE and RMSE. Compare with the previous benchmark model. (e) For the best model you found, find a one-quarter ahead forecast for quarter 155 (using all data available until the end of quarter 154) and report the 95 % prediction interval for your forecast. (f) Separate the data into a training set and a test set (first 70 to 80 % of the data should be the training set and the remaining data the test set). Fit the two models above on the training set and compute the forecast errors on the test set. (g) Your report for the exercise should include a table similar to the one below. 2 Table 1: Summary of Results for Exercises 1 and 2 Method Spec. RMSE (Train) RMSE (Test) Benchmark (from HW1) – Model 1 ϕ1 =, θ1 =, etc. Model 2 Model 3 (if any) The model specification includes the ARIMA specification (i.e. ARIMA (1,0,2) or SARIMA(1,0,2)(0,1,0,4)) and the fitted coefficients. 3. (20 points) Fit ordinary linear regression models to the quarterly Australian Beer Production data. (a) Fit a linear regression model that uses seasonal dummies as predictors (note that there are four quarters and three corresponding seasonal dummies are needed). Check the R2 and the significance of the coefficients and compute the MSE. (b) Fit a linear regression model that uses seasonal dummies and a linear trend term as predictors. Check the R2 , adjusted R2 and the significance of the coefficients and compute the MSE. (c) For both of the models in part a and part b, find a one-quarter ahead forecast for quarter 155 (using all data available until the end of quarter 154) and report the 95 % prediction interval for your forecasts. (d) Your report for the exercise should include a table similar to the one below. Table 2: Summary of Results for Exercise 3 Method Spec. R2 RMSE Benchmark (from HW1) – Model 1 β0 =, β1 =, etc. Model 2 Model 3 (if any)
Consider the product mix problem summarized in the table with 3 products (A, B, and C) and 5 types of resources (1,2,3,4,5). There may be multiple workers working in parallel for each resource. Assume that all workers have 8 hours per day. The number of workers in each resource and the times required for each activity (product) in each resource are given in Table 1. Table 1 process times for sub products Work stations Number of workers Activity time for A (Min/Unit) Activity time for B (Min/Unit) Activity time for C (Min/Unit) 1 5 5 5 5 2 4 3 4 5 3 4 15 0 0 4 6 0 4 3 5 8 10 10 10 1) For the given setting answer the following questions: a. What is the maximum flow rate if demand must be served in the mix determined by the demand rate (7 units of A, 5 units of B, and 4 units of C)? b. What is the bottleneck workstation, c. What is the utilization of workstations? 2) Assume that the activity times given in Table 1 are for experienced workers and the time requirements are %50 more for inexperienced workers. Also, assume that our workforce is composed of 12 experienced and 15 inexperienced workers that can be assigned to any workstation. Formulate and solve a linear program (with your favorite mathematical solver) to find the optimal workforce assignment to workstations to maximize the flow rate.
1. Forecasting Coffee Prices (monthly average price index of coffee in commodity markets as reported by the IMF commodity price data portal) (a) Plot the data and visually assess whether there is significant trend and seasonality. (b) To obtain a benchmark for errors, implement the naive one-month ahead forecast i) ˆyt = yt−1. Report the Mean Absolute Error (MAE), Mean Absolute Percentage Error (MAPE) and Root Mean Squared Error (RMSE) of the naive forecast for years 1991 through 2020. These error measures constitute a simple benchmark for all other approaches (i.e. hopefully you will obtain lower errors by more sophisticated methods). There is plenty of data in this case and we can start forecasting from 1990 but different methods require different initializations in the first year so it’s best to compare the errors from 1991 to the end of 2020 and we use 2021 for some basic testing. 1 (c) Use a 5-period moving average to forecast the one month-ahead price. Report the MAE, MAPE and RMSE of the forecast for years 1991 through 2020. Report 95 percent prediction intervals (using the RMSE estimated in years 1991 to 2020) for the onemonth ahead forecasts for year 2021. How do your prediction intervals perform for 2021? (d) Use exponential smoothing to forecast the one-month ahead price. Perform an exhaustive search for the best smoothing constant α (that leads to the minimum MSE). Report the MAE, MAPE and RMSE of the forecast for years 1991 through 2020. Report 95 percent prediction intervals (using the RMSE estimated in years 1991 through 2020) for the one-month ahead forecasts for 2021. How do these compare with the benchmark and the MA-5 forecast? (e) The data seems to have trend. Implement a naive forecast that includes trend: ˆyt = yt−1 + (yt−2 − yt−3) in order to forecast the one-month ahead price. Report the MAE, MAPE and RMSE of the forecast for years 1991 through 2020. Report 95 percent prediction intervals (using the RMSE estimated in years 1991 through 2020) for the one-month ahead forecasts for 2021. How do these compare with the previous forecasts? (f) Implement an exponentially smoothed version of the previous forecast (you can take α = 0.7 and β = 0.2): ˆy = αyt−1 + (1 − α)ˆyt−1+βzt−1+(1−β)ˆzt−1 where zt = yt−yt−1 and ˆzt = ˆyt−yˆt−1 for one-month ahead prices. Report the MAE, MAPE and RMSE of the forecast for years 1991 through 2020. Report 95 percent prediction intervals (using the RMSE estimated in years 1991 through 2020) for the one-month ahead forecasts for 2021. . How do these compare with the previous forecasts? (g) Find the values of α and β that minimize the RMSE for sixmonth ahead forecasts for years 1991 through 2020. For the optimal values of the parameters, predict the mean coffee prices for the next six months from January 2021 to June 2022. Note that ˆyt+k = αyt−1 + (1 − α)ˆyt−1 + (k + 1)(βzt−1 + (1 − β)ˆzt−1). Report the MAE, MAPE and RMSE of the six-month ahead forecast for years 1991 through 2020. (h) Your report for the exercise should include a table similar to the one below. 2 Method Spec. RMSE MAPE Benchmark – MA-5 – ES – Trend – Smoothed Trend 6-month ahead Note that the model specification for exponential smoothing is: α ∗ = …, β ∗ = … . 2. Generate 500 realizations from an AR-1 process Yt = c + ϕ1Yt−1 + ϵt where c = 50, ϕ1 = 0.6 and ϵt are normally distributed with mean zero and standard deviation 20. (a) Plot the generated observations. (b) Plot the Auto-Correlation Function (start from observation 100 to eliminate the effects of initialization). (c) Implement a naive forecast on the data ˆyt = yt−1. Compute the RMSE starting from period 100. 3. Investigating the Auto-correlation structure of the Coffee Price Index Data. (a) Plot the ACF and PACF of the coffee price index time series. State if there are interesting observations. (b) Difference the data: ut = yt − yt−1. Plot the ACF and PACF of the differences ut . State if there are interesting observations. (c) Based on the previous AC analysis, are you able to propose a model for the original data series?
