Required reading: Wright and Recht, Ch. 9 and 10. 1 (Exercise 4 in Wright and Recht, Ch. 9) Let f be m-strongly convex and L-smooth. Define the function . (a) Prove that fm is convex with (L − m)-Lipschitz gradients. (b) Write down the proximal-gradient algorithm for the functionwhere we take fm to be the “smooth” part and to be the “convex but possibly nonsmooth” part. (c) Does there exist a steplength α such that this proximal-gradient algorithm has the same iterates as gradient descent applied to f for some (possibly different) constant steplength? Explain. (d) Find a steplength for the proximal-gradient method such thatwhere x∗ is the unique minimizer of f. 2 (Exercise 1 in Wright and Recht, Ch. 10) Consider minimization of a smooth function f : Rn →R over the polyhedral set defined by a combination of linear equalities and inequalities as follows: {x ∈Rn : Ex = g,Cx ≥ d} where E ∈Rm×n, g ∈Rm, C ∈Rp×n, and d ∈Rp, and where Cx ≥ d means that each coordinate of the vector Cx − d ∈Rp is nonnegative. Show that the first-order necessary condition for x∗ to be a solution of this problem is that there exist vectors λ ∈Rm and µ ∈Rp, such that ∇f(x∗) − ET λ − CT µ = 0, Ex∗ = g, 0 ≤ µ ⊥ Cx∗− d ≥ 0 where 0 ≤ u ⊥ v ≥ 0 for two vectors u,v ∈Rp indicates that, for all i = 1,2,…,p, we have ui ≥ 0, vi ≥ 0, and uivi = 0. Hint: Introduce slack variables s ∈Rp and reformulate the problem to the equivalent problem min f(x) x∈Rn,s∈Rp subject to Ex = g, Cx − s = d, s ≥ 0. Now define X, A, and b appropriately and use Theorem 10.5 to find the optimality conditions for this reformulation, then eliminate s. 1
Required reading: Wright and Recht, Ch. 5. Throughout the problem set, k · k stands for the 2-norm k · k2. 1 (Exercise 4(b) from Wright and Recht, Ch. 5) Consider the general additive Gaussian noise model g(x;ξ) = ∇f(x) + ξ, where ξ is an n-dimensional Gaussian random vector with mean 0 and covariance matrix σ2In. Suppose we estimate the gradient ∇f(x) using a minibatch of size s ≥ 1: , where ξ1,…,ξs are i.i.d. Gaussian random vectors as above. Show that 2 E. 2 (Exercise 6 from Wright and Recht, Ch. 5) Let f : Rn → R be an m-strongly convex function that can be expressed as an expectation of the form f(x) = Eξ[F(x;ξ)]. Assume that there exist constants Lg > 0 and B ≥ 0, such that Ek∇F(x;ξ)k2 ≤ L2gkx − x∗k2 + B2, for all x ∈ Rn where x∗ is the unique global minimizer of f. Suppose we run the stochastic gradient method on f by sampling ξ and taking steps along ∇F(x;ξ) using an epoch-doubling approach. That is, we run for T steps with steplength α, then for 2T steps with steplength α/2, then for 4T steps with steplength α/4, and so on. Let xˆt be the average of all the iterates in the tth epoch. How many epochs are required to guarantee that Ekxˆt − x∗k2 ≤ ε? 3 Consider the finite-sum objectiveA simple mini-batching strategy is to sample p ≥ 1 indices i1,…,ip ∈ {1,…,N} uniformly at random with replacement and estimate the gradient ∇f(x) by , where ξ := (i1,…,ip). Prove that, for each x ∈ Rn, Eξ[g(x;ξ)] = ∇f(x) and N E. =1 14 Consider the finite-sum objectivesatisfying the following: • The functions fi are all nonnegative and L-smooth, and there exists a point x∗ such that fi(x∗) = 0 for all i. • There exists a constant m > 0, such that k∇f(x)k2 ≥ 2mf(x), for all x ∈ Rn. That is, f satisfies the Polyak–Łojasiewicz (PL) condition, see Section 3.8 of Wright and Recht. Suppose that we run the following stochastic gradient method: Starting with an arbitrary initialization x0 ∈ Rn, at each iteration k = 0,1,2,… we generate xk+1 = xk − αg(xk;ξk), where α > 0 is a constant steplength and where g(xk;ξk) is an estimate of ∇f(xk) using a mini-batch of size p, as in Problem 3. (a) Prove that, for each k, E . Hint: Use smoothness and the result of Problem 3. (b) Assume that α ≤ L2. Prove that, under our assumptions on f, it follows from the result in (a) that E. Hint: Since each fi is L-smooth, k∇fi(x)k2 ≤ 2Lfi(x) for all x ∈ Rn (recall Problem 4(a) in Homework 1). (c) Starting from the result in (b), show that E (d) By optimizing over the choice of α in part (c), prove that our stochastic gradient method converges at an exponential rate: E[f(xk)] ≤ (1 − mα∗)kE[f(x0)], where. 2
Required reading: Wright and Recht, Ch. 6 and 7. Throughout the problem set, k · k stands for the 2-norm k · k2. 1 (Exercise 1 in Wright and Recht, Ch. 6) In the ERM example of Section 6.1, assume that the objective function f is known at the current point x, along with the vector g = Ax. Show that the cost for computing f(x + γei) for some i = 1,2,…,n is O(|A·i|) [here, |A·i| denotes the number of nonzero entries in the ith column of A] – the same order as the cost of updating the gradient ∇f. Show that a similar observation holds for the graph example in Section 6.1. 2 (Exercise 1 in Wright and Recht, Ch. 7) Show that the Euclidean projection PΩ(x) onto the unit ball Ω = {x ∈ Rn : kxk ≤ 1} is given by . 3 (Exercise 4 in Wright and Recht, Ch. 7) Consider the linear function f(x) := cTx of x ∈ Rn, where c ∈ Rn is a fixed vector. Find the minimizer of f over each of the following sets: (a) The unit ball {x ∈ Rn : kxk ≤ 1}. (b) The unit simplex {x ∈ Rn : xi ≥ 0 for all i,. (c) The box {x ∈ Rn : 0 ≤ xi ≤ 1 for all i}. 4 (Exercise 6 in Wright and Recht, Ch. 7) Let Ω ⊆ Rn be a closed and convex set and let a continuously differentiable function f : Rn → R be given. Consider one step of projected gradient descentwith an arbitrary initial point x0 ∈ Ω. Prove that, for any αk > 0, xk+1 = argmin x∈Ω and kxk+1 − xkk2 ≤ αk∇f(xk)T(xk − xk+1). 1
Required reading: Wright and Recht, Ch. 3. 1 Let a continuously differentiable function f : Rn →R and a point x ∈Rn be given, such that ∇f(x) 6= 0. Prove that the set of all descent directions for f at x is convex. 2 Let f : Rn →R be a differentiable, m-strongly convex function. Prove that , for all x ∈Rn. Hint: Use the fact that f satisfies [∇f(x) −∇f(y)]T(x − y) ≥ mkx − yk2, for all x,y ∈Rn. 3 (Exercise 5 from Wright and Recht, Ch. 3) Suppose that f : Rn → R is m-strongly convex, L-smooth, and has (unique) minimizer x∗. Use the co-coercivity property proved in Homework 1 and the fact that ∇f(x∗) = 0 to prove that the kth iterate of the steepest descent method applied to f with constant steplength satisfies , where is the condition number of the problem. 4 (Exercise 7(a-f) from Wright and Recht, Ch. 3) Let A be an N × d matrix with N < d and rank(A) = N [that is, the rows of N are linearly independent]. Consider the least-squares optimization problem minf(x), where x where b ∈RN is a given vector. (a) Assume that there exists a z such that Az = b. Characterize the solution space of the linear system Ax = b. Hint: Recall the definition of the nullspace (or the kernel) of A, ker(A) := {x ∈Rd : Ax = 0}. (b) Compute the Lipschitz constant of the gradient of f in terms of A. (c) If you run the steepest descent method on f starting at x0 = 0 with appropriate choice of steplength, how many iterations are required to find a solution with N1kAx − bk2 ≤ ε? (d) Consider the regularized problem minfµ(x), where x for some µ > 0. Find the minimizer xµ of fµ in closed form. 1(e) If you run the steepest descent method on fµ starting at x0 = 0 with appropriate choice of steplength, how many iterations are required to find a solution with fµ(x) − fµ(xµ) ≤ ε? (f) Suppose xˆ satisfies fµ(xˆ) − fµ(xµ) ≤ ε. Find a tight upper bound on f(xˆ). 2
Required reading: Wright and Recht, Ch. 2. 1 In this problem, you will prove the Cauchy–Schwarz inequality for vectors in Rn: for u = (u1,…,un)T and v = (v1,…,vn)T, |uTv| ≤ kukkvk, where k · k stands for the `2 norm k · k2. (a) Start by proving the following inequality: , for all γ > 0. Hint: First prove it for n = 1, then go from there. (b) Deduce the Cauchy–Schwarz inequality from the inequality proved in part (a). 2 (Exercise 2 from Wright and Recht, Ch. 2) Prove that the epigraph epif is a convex subset of Rn × R for any convex function f. 3 (Exercise 5 from Wright and Recht, Ch. 2) Prove that no function f : Rn → R can be simultaneously strongly convex and Lipschitz. 4 (Exercise 7 from Wright and Recht, Ch. 2) Suppose that f : Rn → R is a convex function with LLipschitz gradient and a minimizer x∗ with function value f∗ = f(x∗). (a) Show that, for any x ∈ Rn, we have . (b) Prove the following co-coercivity property: For all x,y ∈ Rn, . Hint: Apply part (a) to the following two functions: hx(z) := f(z) − ∇f(x)Tz and hy(z) := f(z) − ∇f(y)Tz. 5 (Exercise 8 in Wright and Recht, Ch. 2) Let f : Rn → R be an m-strongly convex function with L-Lipschitz gradient. (a) Show that the function is convex with (L − m)-Lipschitz gradient. (b) By applying the co-coercivity property fron the previous problem to this function q, show that the following holds for all x,y ∈ Rn: . 1
This problem set, which will not be graded and which you do not have to turn in, is meant to give you a rough idea of the material from multivariable calculus and linear algebra you should be comfortable with in order to do well in ECE 490. 1 Let f : Rn →R be a real-valued function of n real variables x1,…,xn, differentiable in each of these variables. Prove that the following identity holds for all x = (x1,…,xn)T and y = (y1,…,yn)T:where is the gradient of f evaluated at x. Hint: With x and y fixed, consider the function g(t) := f((1 − t)x + ty) of a single real variable t. Use the fundamental theorem of calculus to writewhere g0(t) denotes the derivative of g with respect to t. 2 Consider the quadratic function, where x takes values in Rn and A is a given n×n matrix. Compute the gradient ∇f(x) and the Hessian ∇2f(x) (the n × n matrix of second-order partial derivatives 3 Compute the gradient and the Hessian of the log-sum-exp function , where log denotes natural logarithm. 4 Let a matrix A ∈Rm×n and a vector b ∈Rm be given, such that ATA is invertible. Find the unique vector x∗ ∈Rn that minimizes the function f(x) = kAx − bk2 = (Ax − b)T(Ax − b) and prove that it is, indeed, unique (i.e., f(x) > f(x∗) for all x 6= x∗). 5 Let f : Rn →R be a differentiable function, such that the inequality f(y) ≥ f(x) + ∇f(x)T(y − x) holds for all vectors x,y ∈Rn. Prove that f(tx + (1 − t)y) ≤ tf(x) + (1 − t)f(y) for all x,y ∈Rn and all 0 ≤ t ≤ 1. 1 ECE 490 Homework 0 (not for turning in)6 Let e1,…,en denote the standard unit vectors in Rn, i.e., the ith coordinate of ei is equal to 1 and all other coordinates are equal to 0. Determine the eigenvalues of the matrix . 7 Let u and v be vectors in Rn, such that uTv = 06 . Show that u is an eigenvector of the matrix A = uvT and find the corresponding eigenvalue. 8 The singular values of a matrix A Rm×n are the nonnegative square roots of the eigenvalues of the symmetric matrix ATA. Consider a square matrix A Rn×n that can be written in the form n A = XσiuiviT, i=1 where σi are nonnegative real numbers and where {u1,…,un} and {v1,…,vn} are two orthonormal bases of Rn, i.e., uTi uj = δij and viTvj = δij. Here, δij is the Kronecker symbol, i.e., δij = 1 if i = j and 0 otherwise. Find the singular values of A in terms of the σi’s. 2
C Programming with bit manipulation and structs In this assignment we will learn how to inspect and modify individual bits in memory. Remember that everything in computers is represented by just a series of 0’s and 1’s. This means that the software has to remember how each part of memory is converted from 0’s and 1’s to something else. Here’s a simple example: Suppose the memory location 0xAFF5C3 contains the following: 0xAFF5C3 → 0 0 1 0 1 0 1 0 We will focus on the exact bits in memory and the powerful (but yes, low-level) C-functions which allow you to work with them. This 8-bit segment of memory could be a uint8_t type (an 8-bit integer between 0-255). In that case, 00101010 equates to 2+8+32 = 42. However, if it is a char (character), the same pattern of 00101010 equates to ‘*’ (the asterisk character). Working with bits is important because hardware control bits need to be set or cleared in order to control a computer chips. You could turn on or off on-chip peripheral devices to save battery life for example. Instructions We have provided template C files, c_prog2.c and c_prog2.h which contain comments indicating where to put each part of your code as well as directions and sample outputs. These are the two files you will turn in on canvas. In addition to this we have provided the file c_prog2_arduino.ino contains a set of function calls in the setup() function that will run your code. A sample output is provided in sample_output.txt. Please read the entire file before starting work so you understand where things go. Please do not modify the test code. Turning in the assignment: Upload c_prog2.c and c_prog2.h on Canvas Running your code. This code is designed to run in the Arduino IDE which is available to download here: Clicking the “Upload” icon will compile and upload your code to the Arduino board. The output will be displayed in the Serial monitor (Tools > Serial Monitor). The code will run once and will be repeated if you press the RESET button on the board. For those with an existing C development environment you are welcome to use other tools as well, however we will not go over this setup in class and will evaluate the code using the Arduino environment described above. To do this you will need to write a new main.c file with the testing code in setup() and redefine the printing functions in c_prog2_arduino.ino to use printf. 1 C Bitwise Operations 1.1 Bitwise operators We are going to take a number (such as your UW student ID) and mangle it beyond recognition. Write the function long mangle(long SID) which performs the following three steps on the input: 1. Right shift SID by 2 bit positions 2. Clear bit 6 (after the shift, counting from the LSB=0) 3. Complement bit 3 (e.g. 00001000). If bit 3 is one, make it 0. If bit 3 is 0, make it 1. OUTPUT EXAMPLE: Part 2.1: Enter your UW Student ID number: You entered 51218 Your mangled SID is 12812 User input on Arduino. The testing code will prompt you to enter a value for your SID to test. To do this, type a value into the Serial monitor on Arduino and click “Send”. This will send the value from your computer to the Arduino’s processor. Note that there are options for formatting the way your output is sent such as automatically adding a newline character to the end. Select “no line endings” as the testing code is not designed to handle these extra characters.1.2 More bit manipulation Write the function int bit check(int data, int bits_on, int bits_off), to check an int to see if a specific set of bits (aka a “bit mask”, called bits_on) is SET, AND that another set of bits (bits_off) is CLEAR. Returns 1 if the int called data matches the bit masks, and 0 if not. However, note there is a special case. For example, suppose I write: int data = 0xFF; // 0b11111111 bit_check(data, 0x32, 0x20); //0b11111111, 0b00110010, 0b00100000 There’s a problem! Because 0x32 & 0x20 = 0x20 , we are asking that bit 0x20 must be BOTH off and on! Your function should return -1 for any case of testing that any bit is BOTH off and on. 2 Pointer declaration and usage 2.1 Basic Pointer Declaration and use In this part we will use pointers to designate capital letters of the alphabet which are put into memory through the pre-defined array: char a_array[] = {‘A’,’B’,’C’,’D’,’E’,’F’,’G’,’H’,’I’,’J’,’K’, ‘L’,’M’,’N’,’O’,’P’,’Q’,’R’,’S’,’T’,’U’,’V’,’W’,’X’,’Y’,’Z’}; Write a function char* pmatch(char c) which will take a character and return a pointer to the element in a_array which matches it. If there is no such character (e.g. pmatch(‘m’)), then return the NULL pointer. Part 2.1: Enter a capital letter: J You entered: J 2.2 Pointer Arithmetic You can meaningfully do certain kinds of math with pointers (but e.g. x = sqrt(ptr) is meaningless). Write the function char nlet(char* ptr) where ptr is a pointer returned by pmatch. This function will return the next letter of the alphabet (NOT a pointer to the next letter of the alphabet) unless the pointer points to ‘Z’. In that case it will return -1. If the argument does not point to a capital letter A-Y, return -1. Part 2.2: The next letter after J is K Part 2.2: The next letter after Z is -1 2.3 More Pointer Arithmetic Write the function int ldif(char c1, char c2) to find the alphabet distance between two letters of the alphabet using pointer arithmetic. Include c2 in the count but not c1. For example: ldiff(’A’,’E’) == 4 is true and ldiff(’E’,’A’) == -4 is true. Check for errors. If either letter is not a capital letter, return a negative number less than −26. Part 2.3: M and Q are 4 positions apart Part 2.3: x and Q are -999 positions apart 3 Working with Structs 3.1 Defining a struct You might have used classes in a previous programming course/language. In C we don’t have classes but structs provide similar functionality to group data fields together but do not include methods. Here you are going to set up a struct to represent some data about a person, and a couple of functions which work with pointers to those structs. Modify the placeholder definition of Person in c_prog2.h to include the following fields: 1) A max 20 char string: FirstName 2) A max 30 char string: LastName 3) A max 80 char string: StreetAddr 4) A max 6 char string: ZipCode 5) A double: Height // height in meters 6) A float: Weight // weight in kg 7) A long int: DBirth // birthday (days since 1-Jan-1900) * / 3.2 Size of a struct Write a function int personSize(Person p) that returns the number of bytes required to store the person struct in memory. What do you think the number will be? What happens after we store values into it, does the size change? HINT: You can use built in library functions for this. 3.3 Displaying a Person Write a function char* per_print(person * p)which returns a formatted string to neatly print out all the data about a Person. The street address can store 80 characters (see above), if the person’s address is longer than 60 characters, only print the first 60. Do not erase memory of the last 20 characters if present. You can use functions from the standard string libraries. For example, the sprintf function can help create formatted strings with a mix of words and numbers (see the testing code in c_prog2_arduino.ino for examples). The function strcat can also be useful for concatenating strings together. OUTPUT EXAMPLE: — person report: —- First Name: Blake Last Name: Hannaford Address: 124 N. Anystreet / Busytown, WA Zip: 99499 Height: 1.97 Weight: 81.81 DOB 1/1/1900: ———————– 34780
C programming with structs and pointers In this assignment you will write (or complete) C code to print numbers and do basic arithmetic operations as well as work with the standard deck of 52 playing cards. We will represent a card by two integers: 1…13 for the cards Ace … King, and 1…4 for the suit, Hearts, Diamonds, Clubs, Spades. Instructions We have provided a template C file, c_prog1.c which contains comments which indicate where to put each part of your code as well as directions and sample outputs as well as a corresponding header file c_prog1.h. In addition to this we have provided c_prog1_arduino.ino which contains a set of function calls in the setup() function that will run a set of test cases. You do not need to modify or turn in c_prog1_arduino.ino. A sample output is provided in sample_output.txt. Running your code. This code is designed to run in the Arduino IDE which is available to download here: Clicking the “Upload” icon will compile and upload your code to the Arduino board. The output will be displayed in the Serial monitor (Tools > Serial Monitor). The code will run once and will be repeated if you press the RESET button on the board. If you need to run your code and do not have physical access to your arduino board you can use this online simulator Wokwi. This tool emulates the Arduino and prints the same output: For those with an existing C development environment you are welcome to use other tools as well (Visual Studio etc), however we will not go over this setup extensively in class and will evaluate the code based using the Arduino environment described above. To run this on your computer you will need to write a new main.c file with the testing code in setup() and redefine the printing functions at the bottom of c_prog1_arduino.ino to use printf. Coding style: For this assignment you do NOT need to follow the . All we ask is that you write your code in the “c_prog1.c” file and that code you write does not have compile errors or warnings. Warnings generated by our starter code (not a problem on most computers) are OK. Comments about how your code works can help us award partial credit if needed. Printing. We have defined a set of simplified wrapper functions for printing. Their names and function prototypes indicate which kind of data they can print: void print_int(int); void print_usi(unsigned int); void print_newl(); void print_str(char*); void print_dble(double); The code for these functions is given at the bottom of c_prog1_arduino.ino. 1 C Basics 1.1 Looping Write the count function that prints out integers one per line counting from 1… N. If you define additional variables please place these at the top of the file with a comment for the problem they are used for. SAMPLE OUTPUT: 1 2 3 (continued)… 1.2 Summations Write the sums_and_squares1 function to print numbers counting up from 1…N as before but also print the sum and the sum of the squares at the bottom of the output. SAMPLE OUTPUT: 1 2 3 (continued)… [sum(1,2,3 … N)] [sum(1^2,2^2,3^2 … N^2)] 1.3 Text Output Write the sums_and_squares2 function that prints the sum and sum of squares for numbers 1…N as before but are also labeled with text: “sum: ” and “sum of squares: ” on separate lines. SAMPLE OUTPUT: sum: [sum(1,2,3 … N)] sum of squares: [sum(1^2,2^2,3^2 … N^2)] 1.4 Text Manipulation If the length of the input is greater than N, truncate the string. The function should return a new string containing the modified text and leave the original string intact. Fill in the following function: char* length_pad(char *st, char* st_buffer, int n); Update the function sums_and_squares3 as needed to use the length_pad to print the output such that the numbers are all aligned starting in col 21 (i.e. all values have length 20). SAMPLE OUTPUT: sum: [sum(1,2,3 … N)] sum of squares: [sum(1^2,2^2,3^2 … N^2)] 2 Card Games A ‘shuffle’ is an array of 52 pairs of integers. The first of the pair is the card type (0-13 representing Ace, 2, 3, …. King) and the second representing the suit (hearts, diamonds, clubs, spades). Thus a pair of numbers describes a unique card in the deck. For example, {6,3} would describe the Six of Clubs, and {13,1} would be the King of Hearts. 2.1 Shuffling Write the function void fill(shuffle[52][2]) to fill a shuffle with 52 random integer pairs, BUT, as with your playing cards, there must be exactly one of each pair in the shuffle. Use your function to print out all the “cards” of the shuffle, 7 cards per line. Put brackets around each number pair to make the output more readable. Note that the sample output below has some spaces truncated to fit on the page. To generate a random number use the helper function int randN(int n)defined at the bottom of this file that returns a random integer between 1 and N. SAMPLE OUTPUT (some spaces truncated): [ 11 2 ] [ 11 4 ] [ 12 1 ] [ 5 4 ] [ 4 3 ] [ 7 3 ] [ 5 3 ] [ 13 4 ] [ 9 3 ] [ 2 3 ] [ 1 1 ] [ 2 4 ] [ 3 2 ] [ 2 1 ] [ 13 1 ] [ 7 4 ] [ 8 2 ] [ 4 4 ] [ 6 4 ] [ 4 2 ] [ 1 4 ] [ 7 1 ] [ 3 3 ] [ 12 2 ] [ 6 1 ] [ 12 4 ] [ 13 3 ] [ 9 2 ] [ 9 1 ] [ 3 4 ] [ 9 4 ] [ 10 2 ] [ 4 1 ] [ 8 1 ] [ 1 3 ] [ 3 1 ] [ 11 3 ] [ 8 4 ] [ 10 3 ] [ 5 1 ] [ 10 1 ] [ 13 2 ] [ 11 1 ] [ 7 2 ] [ 6 3 ] [ 8 3 ] [ 12 3 ] [ 2 2 ] [ 5 2 ] [ 1 2 ] [ 10 4 ] [ 6 2 ] 2.2 Compact Data Representation A ’hand’ is an array of seven unsigned chars. Each char represents one card. We use a four bit field in the char for each of the two numbers above: the four most significant bits [bits 7…4] represent the card number (1-13) and the lower four [bits 3…0] represent the suit. Write the following functions: a) unsigned char convert(int card, int suit) which converts two integers (from a shuffle for example) into a char as above. b) int valid_card(unsigned char card) to test if a char equals a valid integer pair in the range of playing cards (numbers 1-13 and suits 1-4) c) int gcard(unsigned char card) to get the integer suit from a char d) int gsuit(unsigned char card) to get the integer card from a char 3 Pointers and Array Manipulation 3.1 Displaying card names Write a function names(int card, int suit, char answer[]) which places a string of the name and suit of a card in the array answer[]. For example: name(11,1) → “Jack of Hearts” name(8,2) → “8 of Diamonds”. HINT: Use pointers to copy the characters one-by-one into the array answer[] to build up the final string. We have defined the following arrays at the top of the file: card_names[]={“Ace”,”2″,”3″,”4″,”5″,”6″,”7″,”8″,”9″,”10″,”Jack”,” Queen”,”King”}; suit_names[]={“Hearts”,”Diamonds”,”Clubs”,”Spades”}; Part 3.1 Test Results: >>>> 0 : 1 1 Ace of Hearts >>>> 1 : 1 2 Ace of Diamonds >>>> 2 : 1 3 Ace of Clubs >>>> 3 : 1 4 Ace of Spades >>>> 4 : 11 2 Jack of Diamonds >>>> 5 : 12 2 Queen of Diamonds >>>> 6 : 13 4 King of Spades 3.1 Dealing cards Write a function void deal(int M, unsigned char hand[7], int deck[N_DECK][2]) to deal a hand of M (0
After completing this lab, students will be able to: 1. apply a real-time preemptive operating system: RT-OS 2. Integrate a solution-focused software and hardware project with novel sensors, displays, or actuators. ● Turn In Requirements: ● Lab report and demo. Part I (4.1): Setting up Free RT-OS 1. Install FreeRT-OS operating system package for the Arduino. (use only the Canvas files linked below, they are tested on Arduino Mega board). a. Download the .zip file for the CSE/ECE474 Official FreeRTOS version [ ]. b. Unzip the folder and follow instructions to install the Arduino_FreeRTOS library [ ]. Use the “manual installation” instructions. 2. Verify operation of the initial “blink_analogRead474.ino” example under FreeRTOS. Download the CSE/ECE474 demo app [ ]. a. Plug in your analog thumbstick (or any potentiometer) to generate a varying 05VDC positive voltage on an analog input pin. b. Modify the demo app so that the analog input task uses the same pin you connect to the potentiometer/thumbstick. c. Check the baud rate of your Serial Monitor (in the Arduino IDE) to match what is in the demo code. d. Run the demo app and verify i. Light flashes ii. Analog values are printed to the Serial Monitor and they change between 0-1023 when you change the thumbstick/potentiometer. 3. In addition to these add the following tasks. Demonstrate all four running simultaneously. a. Task 3: Flash an OFF BOARD LED: ON for 100ms, OFF 200ms. b. Task 4: Configure Timer 4 and cause it to play the song you used in Lab 3 on your speaker (Mario theme or song of your choice). This task should play the theme three times (pause 1.5 sec between playbacks) and then stop itself. Part II (4.2): Project Using RT-OS, 1. Continue to run Task RT-1, defined above blinking an LED ON for 100ms, OFF 200ms. 2. Do not play sounds or compute FFTs anymore unless required by your project below. 3. Run additional tasks as required to perform a “Project”. This is your chance to get creative and challenge yourself. Figure out physical parts you want to use and functions you want to perform which are “stretch goals” beyond Lab 1 – 3 capabilities. Try to organize your project around an embedded system that solves a real world problem or use case (a game or entertainment device is ok too). Project Criteria: A successful 474 Lab 4 project will meet the following criteria: 1. Perform reliable time and digital I/O functions. This means everything in your program runs smoothly without timing glitches or other bugs. 2. Operate with high speed and high CPU load. In terms of the parameters C, P, D, the projects should have at least one task which needs to run 50 times per second or faster (P
With successful completion of this lab, you will be able to run several simultaneous tasks and ● Implement and explain a round-robin (RR), non-preemptive scheduler ● Implement and explain a RR scheduler using function pointers and timer synchronization, and a sleep() function. ● Implement and explain a scheduler using Task Control Blocks (TCBs) for each task. ● Implement a simple Interrupt Service Routine (ISR) and use it to get hardware precision for your scheduler cycle synchronization. Turn-In Requirements are included at the bottom of this document. Equipment 1) Arduino Mega Microcontroller board 2) External Arduino power supply 3) LEDs and 250 Ohm resistors 4) Small 8-Ohm Speaker 5) 4-digit 7-segment LED display Preparation Technical Requirements In Lab 3 we will implement 5 tasks with different schedulers. To demonstrate mastery of the learning objectives you must integrate the following tasks with specific scheduler types into Specific Required Configurations (see table below), but not all possible combinations are required. Tasks 1) Task 1: Flash an external LED for 250 ms every 1 second. (e.g. ON for 250ms, OFF for 750ms). 2) Task 2: Make the speaker emit the beginning of the Mario theme song (see Appendix) or a short theme song of your choice using the hardware timer techniques from Lab 2. If you choose your own please play something different from Mary had a little lamb. Task 2 should play the song and then sleep for 4 seconds, then play the song again. Directly manipulate timers to generate the signal, do not use Arduino’s tone() function. 3) Task 3: Make the 7-Segment LED display (info below) count up by 1 unit every 100 ms. 4) Task 4: After you demo tasks 1-3, Task 4 is a new task that combines and modifies tasks 2 and 3 as follows. While no music is being output, make it so the 7-segment display indicates a countdown in 10ths of a second until the next time the theme is played (check the HINT below). During the music, display the frequency (in decimal Hz.) of the current tone on your 7-Segment display. (your code doesn’t have to measure the frequency, you have it in your code somewhere). a) Task 1 runs all the time. b) Task 2 runs at the start but stops after playing the theme 2 times. c) After Task 2, start a count-down (on the 7-segment display) for 3 seconds and then restarts task 2 (original definition above) for one final time. d) Display a “smile” for 2 seconds (See Appendix B) (code this as a new task to be controlled by Task 5). The 2 second interval begins after completion of part 5c. e) Stop all tasks, except “a) Task 1” in this list. Scheduler Types We will implement three schedulers for a variable number of tasks. None of the schedulers will be pre-emptive. 1. Round Robin (RR) – like the basic Arduino loop() function. Your scheduler should be a simple loop beginning with: while(1) { (write this within the Arduino loop() function). Then call your tasks in order and repeat. Add a delay loop to cause the overall period P to meet requirements. Example RR Scheduler setup: while(1){ task1(); task2(); … taskN(); // short delay for(int i=0; i< delay_value; i++){ // code that wastes a small amount of time } // OR you can use delayMicroseconds() instead } 2. Synchronized Round Robin with ISR (SRRI) – 2.1. This scheduler will use an ISR, and replace the function calls from the RR scheduler with a pointer or index which should be incremented through: ● an array of 10 function pointers (so you can have up to 10 tasks). ● Each of the function pointers in the array shall point to a task except, ● a Null pointer shall denote the end of the actual tasks in the task array. ● Each task must have a state belonging to the set { READY, RUNNING, SLEEPING } You should create an array that stores the state for each task. ● A sleep_474(int t) function must be defined that tasks can call while they are running. When a task calls sleep_474(t), it should be stopped and its state should be changed to SLEEPING. Also, store the value of t (milliseconds) so that you can associate it with the sleeping task. If it is a task’s “turn” to run, but it is in the SLEEPING state, then do not run it. ● Every 2 milliseconds, the waiting time for any SLEEPING task must be decremented by 2. (yes, sleep calls will only be accurate to within 2ms.) If the waiting time for a task goes below 2ms, then its state must change from SLEEPING to READY. 2.2. Before running the SRRI scheduler, your code must initialize an 8-bit hardware timer to generate an interrupt for each “tick” (2ms). As with any interrupt, you must write an Interrupt service routine (ISR) for this interrupt to do something at each clock interrupt. As always, your ISR must be a very small piece of code. Guidance for this lab is to write your ISR to change a volatile global int (let’s call it sFlag) between the states { PENDING, DONE }. The ISR should perform one simple function. Set sFlag =DONE. The ISR can also keep track of time by incrementing a time int (or long int) but you might not need that. Hint: ISRs can be notoriously tricky to program and debug. That’s why the advice to Keep it Simple! Specifically, consider a minimalistic setup for initial ISR debugging 2.3. The last task in the function pointer list must be a task called schedule_sync(). This task must do an infinite loop as long as sFlag == PENDING. When sFLAG == DONE, schedule_sync() must 2.3.1. Update remaining sleep times of all sleeping tasks (we set the timer interrupt for 2ms so we know what is deltaT). 2.3.2. Wake up any sleeping task whose sleep time goes to 0. 2.3.3. Reset sFlag to PENDING 2.3.4. return Now your scheduler will complete exactly one loop every 2ms unless your tasks take more than 2ms to return to loop() (you should make sure that your tasks run for short bursts so this does not happen). Specifically include (in addition to the state information from SRRI above). 3.1. Unique ID code for the task. 3.2. A string name of the task (up to 20 characters) (Example: “LED Flasher”). ` 3.3. The total number of times the task has been started/restarted. Implement the scheduler by creating a list of all the TCBs and looping through them. Start each task or not depending on its Status. A new function called task_self_quit() must be defined which allows a task to terminate itself by manipulating its TCB, and a similar function called task_start(TCB *task) so that a task can start up another task. The scheduler must have a pointer or index which knows which task is running. Thus it knows which task called task_self_quit(). 3.4. Add a new task status: DEAD 3.5. If a task calls task_self_quit() it should be removed from the TCB list and its status set to DEAD. Keep a separate list of the dead tasks. 3.6. Another task can revive a dead task by calling task_start( tsk ) where tsk here is a pointer to the TCB of a DEAD task. The task_start(tsk) function should do this by changing tsk’s status to READY. Specific Required Configurations and Demos Demonstrate the lab by showing the following specific combinations of Tasks and Schedulers Demo Number Tasks Running at start Scheduler Type Notes or special instructions 1 T1, T2 RR 2 T1, T2 SRRI 3 T1, T2 DDS 4 T1, T2, T3 SRRI 5 T4 DDS 6 T5 DDS (T5 will start and stop additional tasks). Demo Verbal Questions: 1. What are the advantages and disadvantages, if any, of using interrupts and ISRs as opposed to using flags with “blocking” code (e.g. delay())? Are ISR driven tasks always faster? 2. Why should ISR functions be simple and small? 3. In this lab you used a Timer Interrupt. Which Timer Interrupt did you use? For each of the following Interrupt Definitions, give the relative priority with respect to the Timer Interrupt you used (higher or lower). (HINT: Check the interrupt vector table) a. SPI Serial Transfer Complete b. RESET c. Pin Change Interrupt 2 d. External Interrupt 7 e. Timer/Counter(n) overflow (n is the number of the Timer/Counter you used) 4. Why is the SSRI scheduler advantageous with respect to the RR scheduler? 5. Why would you use a TCB? Recommended Procedures (suggestions for breaking down the lab, step-by-step testing, etc. ) Wiring and driving the 7-segment display Like the 8×8 display, your 7-segment display is either common-anode common cathode. Here is a typical schematic:of a common cathode display with 4 digits. Pins 12, 9, 8, and 6 drive the negative side of all segments in a specific digit. You drive the display by scanning the digits and the segments (pins 11, 7,4,2,1,10,5,3) similar to the rows and columns of the 8×8 RAW matrix. It’s the same idea as scanning rows and columns, but instead, for each digit, you must light up the segments required to indicate each number. 7-Segment software There’s tons of good info online on the basics of driving your display [ ]. The devil is in the details like getting your wiring right, and importantly, interfacing your LED driver to the required scheduling system. The code listed in most online examples shows you what to do at a low level, but will not work with schedulers. Consider implementing the following functions to aid task building ● Convert an int to 4 digits ● Use a number in the range 0-9 to select an array indicating which of the 7 segments light up. ● Activate the output bit for a digit (0-3). ● Activate the 7 segment bits according to the array above. You can easily debug these building blocks and then it’s easier to put them together into a continuous display. As a starting point, light each digit ON for 2ms and OFF for 3ms (5ms per digit). Slower than that can be good for debugging but makes a flickering display. Lab 3-Specific Turn-In Requirements Special Grading Criteria ● See . Report: Turn in a PDF report following the and the documents. Include a section detailing each partner’s contributions, and be specific. This PDF should be turned in as a standalone document, not in a .zip file. Demo: Demonstrate all items from “Specific Required Configurations and Demos” and “Demo Verbal Questions” sections below. Code: Turn in ALL code in .ino and .c files (if applicable). Submit a zipped folder containing all .ino and .c files, and keep Arduino files in their sketch folder. Comment out (but do not delete) code which might be required for intermediate steps but is not required for the final code. This will help us give you partial credit! Appendix A: Beginning of Mario theme The notes below correspond to the beginning of the Mario theme. By converting these to the correct timer counts you can play the sounds just like Lab 2. ] // We recommend a duration of 100 ms per note #define E 659 // Hz #define C 523 // Hz #define G 784 // Hz #define g 392 // Hz #define R 0 // Rest, play no sound int song[] = {E, R, E, R, R, E, R, R, C, R, E, R, R, G, R, R, R, R, R, g, R}; Appendix B: “Smile on LED display” (If you’ve got a “better” design — go for it!)
Introduction In this lab, we will drive some digital outputs to flash an 8×8 matrix of LEDs and make a tone on your speaker. Emphasis will be placed on the correct timing of multiple tasks by verification of light motion and audio tone. Timing and frequency output will be verified on the oscilloscope. Learning Objectives With successful completion of this lab, the student will be able to ● Manipulate hardware registers/ bits, without the use of existing libraries, to perform lowlevel hardware functions. ● Coordinate multiple concurrent tasks with round-robin scheduling Equipment 1) Arduino Mega Microcontroller board, breadboards, wires 2) External Arduino power supply (recommended) 3) 3 LEDs and 250-500 Ohm resistors 4) Small 8-Ohm Speaker 5) 8×8 LED Matrix 6) 2-way thumbstick control Technical Requirements The lab will be performed and written up in teams of two. As a member of the two-person lab team, you are responsible to: 1) Work with your partner to complete the lab, writeup, and demo video. 3) Turn in at least one submission per group, and list your partner(s) in the submission comments. Report header/title page must include both team member names and student #s. Turn in requirements: each team must show achievement of the above Learning Objectives by 1) Performing all demonstrations in BOLD below. Audio tones must be “smooth” not glitchy. 2) Submit a lab writeup according to the . Required Procedures 1. Hardware bit manipulation 1.1. Wire up 3 LEDs with 500-250 Ohm series resistors (exact R-value doesn’t matter) on pins 47, 48, 49. 1.2. Create code to initialize these pins as outputs (using Arduino’s pinMode()function), and demonstrate flashing them on and off in a sequential pattern (using Arduino digitalWrite()) with a period of 1 second (and no other functions). LEDs should flash in order: 47–>48–>49–>47–>48 … etc, each LED on for 333ms. 1.3. Identify the ATMEGA2560 Port number (cap letter) and port bit numbers corresponding to pins 47-49 (your LEDs). See the . 1.4. Redo part 1.2 without using the pinMode() & digitalWrite() functions. See the for background on how to directly set up and use digital I/O pins. Satisfaction of this part requires code that: 1.4.1. Uses the defined macros such as DDR3, PORT3, etc. registers that control the pins requested in 1.1. 1.4.2. Uses these definitions to demonstrate flashing the LEDs in the same pattern of 1.2 2. 16-Bit Timer/Counter // (see page 56 of data sheet) #define TIMER4_ON_BIT PRTIM4 2.3. Write a task that starts the timer such that it generates a square wave on pin OC4A at a specified frequency. Hints: 2.3.1. Choose an appropriate waveform generation mode (Table 17-2). 2.3.2. Do not enable interrupts. 2.3.3. Set or clear all required register bits using the technique of Section 1.4 above. Best to write a bit_set() and bit_clr() or bit_set_clear() function of your own. When setting or clearing specific register bits, be sure to not change other register bits. 2.3.4. Be sure to properly initialize the output pin you need. Make sure OC4A is set up as an output via DDR4 so that its pin can drive the speaker. 2.3.5. PWM modes can be used if set for 50% duty cycle. Connect the output pin to the speaker. See the “Pro-tip” below. 2.4. Demonstrate the ability to program the 16-bit Timer/Counter to directly output the following tone sequence on your speaker (cycle it). 2.4.1. 400 Hz for 1 sec 2.4.2. 250 Hz for 1 sec 2.4.3. 800 Hz for 1 sec 2.4.4. Silence for 1 sec It should sound like . Pro Tip: Driving a speaker with a 5V square wave is not exactly “Hi-Fidelity sound”. Specifically, a bunch of harmonics will be generated because 1) it’s a square wave, 2) we are driving the speaker hard and the speaker’s cone will slam into the end of its motion range, severely distorting the sound. In my tests with a very cheap 8 Ohm speaker, sometimes the harmonics are so strong that the frequency subjectively sounds wrong (especially when playing a tune as in 2.4 above). For example, if the 2nd harmonic is too strong on a 400Hz signal, it will sound like 800Hz. Experiment with a series resistor between the output pin and your speaker to get a softer, less harsh sound with fewer harmonics (by driving the speaker with less current). The Oscilloscope can really help you out here. 3. Concurrent Tasks 3.1. Define three tasks: 3.1.1. Task A: (LED Sequence) Same as part 1.4.2 above 3.1.2. Task B: (Timer tone output) Same as 2.4 above 3.1.3. Task C: Control the operation of Task A and Task B as follows: 3.1.3.1. Task A for 2 seconds 3.1.3.2. Task B by itself with no LEDs for 4 seconds 3.1.3.3. No outputs for 1 second 3.1.3.4. Repeat the above steps 3.2.1. 3.2.1.1. Task A runs alone for 2 sec. 3.2.1.2. Task B alone for one music cycle. 3.2.1.3. Task A and Task B run at the same time for 10 sec. 3.2.1.4. No tasks for 1 sec. 3.2.1.5. Repeat 3.2.2. Use the Arduino loop() function to call the tasks in order (a basic roundrobin scheduler). Declare and clearly document some flags (global variables visible to all 3 tasks) so that Task C can “signal” Tasks A&B when to start and stop. 3.3. Modify your part 3.2 to change Task B to play the tune “Mary Has a Little Lamb” (see Appendix below for the specific frequencies) and Demonstrate recognizable glitch-free music. 4. Interactive Display Add an interactive XY LED display matrix which moves a dot around in response to thumbstick inputs. Your accessory kit should have a generic XY thumbstick and an 8×8 LED matrix like the 1088BS model here. See . “turn in requirements” here (no new requirements) 4.1. Write code following the instructions below to control the LED matrix dot with the thumbstick to create an interactive display. Demonstrate ability to reach all 64 LEDs with smooth and rapid thumbstick motion. See . 4.2. Integrate the interactive display with your speaker. Demonstrate simultaneous output of “Mary had a little lamb” with smooth function of the thumbstick and 8×8 display. SPI 8×8 Matrix (e.g. MAX7219 dot matrix) (non-RAW) Consult this by Ishaan. Sample code called is on the course website. You will not need to modify the spiTransfer() function.3,4 There are two common types of 8×8 LED matrices sold as Arduino Accessories: ● “Raw” 8×8 matrix (exposes one pin per row and one pin per column for a total of 16 connections.) ● Serial interface 8×8 matrix. Includes one or more chips to allow you to control all 64 LEDs with fewer (than 16) connections but requiring added software. Write a function that can set or clear a single LED at a specified row and column. Use it in an otherwise empty Arduino sketch to test your wiring. Now wire the thumb stick. Under the hood, the thumb stick consists of two variable voltage dividers, one senses X deflection and the other Y deflection. Plug the thumbstick into your solderless breadboard and connect its X and Y output pins to two Arduino Analog inputs. Use the arduino analogRead() function to read the X and Y values. Analog inputs convert 0-5VDC to a 10 bit int range from 0-1023. Write a function to convert this range to 0-7 (the row or column indices by which the dot will move). You might want to test your thumbstick reading / mapping function separately by using the Serial.print()function to print converted row/column data back to your PC over the USB port. Now combine reading the thumbstick with flashing the LED at the appropriate Row/Col. Specifically, in loop() 1) Read voltages from thumbstick and convert to row and column 2) Turn on the LED at {row,col} 3) Delay 50ms 4) Turn off the LED at {row,col}Turn In Requirements Learning Objectives With successful completion of this lab, the student will be able to ● Manipulate hardware registers/bits, without the use of existing libraries, to perform lowlevel hardware functions. ● Coordinate multiple concurrent tasks with round-robin scheduling. Report Turn In: Turn in a PDF report following the documents. Include a section detailing each partner’s contributions, and be specific. This PDF should be turned in as a standalone document, not in a .zip file. In-Lab Demo: Demo must include: 1. Sequential Flashing of LEDs in Part 1.4, with each LED on for 333ms. Show where the code uses the DDR and PORT registers. 2. Speaker tone output in Part 2.4. Show where the code uses the 16-bit Timer/Counter registers. 3. Operation of Task C as outlined in Part 3.2.1. 4. Operation of 3.2.1 but with Task B playing “Mary Has a Little Lamb” 5. Working LED matrix dot controller with thumbstick 6. Simultaneous output of “Mary had a little lamb” with smooth function of the thumbstick/8x8display. Be prepared to answer the following questions. 7. How could you implement the pinMode() and digitalWrite() functions? 8. How do you change the frequency of the square wave generated on OC4A? 9. How do you achieve simultaneous operation of Task A and B in Task C despite using a round-robin scheduler? Turn in ALL code in .ino and .c files (if applicable).Submit a zipped folder containing all .ino and .c files, and keep Arduino files in their sketch folder. Comment out (but do not delete) code which might be required for intermediate steps but is not required for the final code. This will help us give you partial credit! Appendix: “Mary Had a Little Lamb” of this snippet] #define c 3830 // 261 Hz #define d 3400 // 294 Hz #define e 3038 // 329 Hz #define f 2864 // 349 Hz #define g 2550 // 392 Hz #define a 2272 // 440 Hz #define b 2028 // 493 Hz #define C 1912 // 523 Hz #define R 0 int melody[] = { e, R, d, R, c, R, d, R, e, R,e, R,e, R,d, R,d, R,d, R,e, R,g, R,g, R,e, R,d, R,c, R,d, R,e, R,e, R,e, R,e, R,d, R,d, R,e, R,d, R,c, R,c };
Learning Objectives With successful completion of this lab, the student will be able to ● Install and set up Arduino IDE ● Build and run a basic sketch (program) using the Arduino Libraries ● Modify and demonstrate blinking light code and speaker output tone. ● Learn to use an oscilloscope for debugging Equipment 1) Arduino Mega Microcontroller board 2) External Arduino power supply 3) LEDs and 250 Ohm resistors 4) Small 8-Ohm Speaker 5) USB- Type-B cable (with USB-A or USB-C for computer end) (you probably got one with Arduino) (image: globetek.com) 6) Solderless Breadboard 7) Wires (either with pins (see the kits), or cut and strip your own 22AWG solid wire). Helpful Resources: If you haven’t worked with electronics before, or want to brush up, check out this list of compiled resources that will help you learn the basics. ]. For a more in depth introduction as well as additional resources on getting started with Arduinos, check out this excellent series of tutorials by Jon Froehlich: Technical Requirements In this lab we will use some standard Arduino code packages to blink an LED and to make a tone on a speaker. Required Procedures (suggestions for breaking down the lab, step-by-step testing, etc. ) 1. Part I Intro to Arduino: Install the open-source Arduino Interactive Development Environment (IDE) from on your Windows, Mac OS, or Linux computer. In case of difficulty, try , or . Then if those 1.1. Open the Arduino IDE by clicking its desktop icon (OS dependent). 1.2. Open the blink example by “File->Examples->0.1Basics->Blink”. 1.3. “Break” your code by deleting the required semicolon (“;”) on line 28 (line number shows in the lower left). Hit the checkmark (upper left) and observe the orange error messages. 1.4. Fix your bug and build the code again (checkmark) 1.5. Connect your Arduino MEGA to your PC via USB (observe steady green “ON” light indicating power) 1.6. Configure IDE for your board and connection. Remember, because C is a compiled language and different chips have varying memory and peripherals we have to select the right target platform. To do this: 1.6.1. “Tools->Board->Arduino Mega 2560 or Mega 2650”1.6.2. “Tools->Serial Port->” Select the one that says: “(Arduino Mega or Mega1.7. Upload “blink” to the Arduino (right arrow icon at the top). You should see a pair of LEDs on the board rapidly flashing. This indicates code downloading into your Arduino. After that your code automatically starts.1.8. The LED labeled “L” near the USB connector should blink 1 time every two seconds. 2. Part II: Modifying your sketch and your LED 2.1. Change the delay values from 1000ms to 200ms. Recompile (checkmark) and re-upload your sketch. 2.2. The LED should go faster. 2.3. Now unplug the USB cable from your Arduino and plug in the 120VAC power adapter. The Arduino has non-volatile memory so whenever it’s plugged into power it will automatically load the last code uploaded, so the flashing light program should run again. If not, try pressing the reset button. 3. Part III External LED Hardware 3.1. Connect a 250 Ω resistor between the cathode (short wire) of an LED and a GND/0V pin on the Arduino. (See picture below for reference) Make the resistorLED connection by either breadboard connecting, soldering, wire twisting, or alligator clip as you prefer.Connect the long LED wire with IO/PWM pin 10.3.2. Modify the blink.ino code on line 10 so that the LED pin is now pin 10 3.3. Compile and upload. Verify your LED attached to pin 10 is blinking as expected. 4. Part IV Multiple tasks 4.1. Keeping your external LED wired up, wire the 8 Ohm speaker between pin 2 and +3.3V. 4.2. Modify the blink “sketch” (code) to make clicks on the speaker. HINT: What happens if you do the same digitalWrite on pin 2? 4.3. Now add new code to blink both the on-board LED (pin 13), and the external LED (pin 10) such that one is ON when the other is OFF and the speaker clicks when the LEDs change state. 5. Part V Differing Periodicities 5.1. Modify your code so that the LEDs flash the same as 4.3, but instead of clicking, the speaker emits a continuous tone of 250Hz. Pro tip (and lab requirement): write your code so the sound turns off after a few seconds (it will drive you crazy!). Make sure your LEDs keep flashing in the correct pattern after audio stops (your code didn’t just crash). NOTE: Do not use the tone() function for this. This can cause your program to freeze up and not allow you to blink the LED. 6. Part VI Measuring signals with an oscilloscope 6.1. Read the following background information to learn how an oscilloscope works What is an oscilloscope? An oscilloscope (scope for short) is an instrument that displays a 2D graph of voltage versus time on the screen. A scope lets you see the actual electrical signal coming from or going into your microcontroller and can be very useful for debugging things like timing errors, etc. Video tutorial on the basic functions of an oscilloscope:For the purpose of this lab, these 3 systems/modules are most important: Vertical: Controls the vertical (voltage) measurement of the signal. Needs to be tuned to display the correct voltage/division (division = the vertical length of the ‘rectangles’ on the screen) Horizontal: Controls the time/division of the screen. Horizontal scale needs to be adjusted so we can see the desired horizontal/time interval of the signal. Trigger: For repeating waves/signals, the trigger ‘goes off’ at certain points of the signal so the oscilloscope can stabilize it on the display. Trigger levels are also used to capture pulses/single events. For further reading if you are interested, Tektronix has a very detailed explanation of how to operate oscilloscopes in this . It explains in excellent detail on how to tune the oscilloscope to capture the desired information. (Chapter 4, linked above is relevant to this lab) 6.2. Try measuring a waveform. Connect the oscilloscope probe to your Arduino output and ground. Try playing around with the knobs to make sure you can get a stable image of the waveform on the screen. You can also use the “Measure” button to add things like a measurement of the frequency, etc.6.3. Use the in-lab oscilloscope to show that the waveform from your Arduino is steady and demonstrate that it’s frequency is indeed 250 Hz. Explain the controls of the oscilloscope and what you need to adjust to measure the signal.. Turn In Requirements Learning Objectives With successful completion of this lab, the student will be able to ● Install and set up Arduino IDE ● Build and run a basic sketch (program) using the Arduino Libraries ● Modify and demonstrate blinking light code and speaker output tone. Report Turn In: Turn in a PDF report following the and the documents. Demo Requirements: (please see ) 1. Blink on-board LED @ 200ms 2. Blink off-board LED @ 200ms (note that one compile can demo both of these) 3. Blink on-board and off-board LEDs with speaker clicks. 4. Make a tone @ 250Hz with LEDs flashing @ 200ms without audible glitches. 5. Use the in-lab oscilloscope to show that the waveform is steady and demonstrate that it’s frequency is indeed 250 Hz. In the Demo, verbally answer the following questions: 6. What happened when you deleted the semicolon in the Blink.ino file? 7. How did you change the flashing LED from on-board to off-board? 8. How did you make the speaker emit a tone of 250Hz? 9. How did you make the speaker emit a 250 Hz tone and the LEDs flash at the right rates? Code Turn In: Turn in ALL .ino, .h and .c files in the project. Submit a zipped folder containing all code. Comment out (but do not delete) code which might be required for intermediate steps but is not required for the final code. This will help us give you partial credit! Turned in code should include functionality for the following parts above: ● Part 1.8 ● Part 2.2 ● Part 3.3 ● Part 4.2 ● Part 4.3 ● Part 5.1
Overview This assignment is designed to give you practice with several parts of the kernel API: signal handling, a bit of terminal control, and file I/O. It is probably the most algorithmically challenging of the assignments you’ve had so far, but it does not require a long program. Because you haven’t yet learned how to control terminals, the program will not use many features of terminals. It will use the ANSI escape sequences that I explained and showed examples of in class to control the position of the cursor and the screen contents. The assignment is specified by the following man-page-like description. Your job is to write a program that satisfies these requirements. The information regarding program submission is at the end of the assignment. NAME autoscroll — display a file, automatically scrolling upward one line per second if needed SYNOPSIS autoscroll [-s secs] textfile where secs is a positive integer < 60 DESCRIPTION When run with any size plain text file in a terminal window with R rows and C columns, autoscroll displays the first R-1 lines of the file in the terminal. If the number of lines in the file is R-1 or less, it terminates after displaying these lines. Otherwise, every N seconds, with N=1 by default, it scrolls the file up one line, so that the topmost line disappears and the next line in the file is displayed; but see below for further details. It also updates a clock display and an indicator of the visible lines in the file. Terminal windows have a coordinate system in which the upper-left corner is (1,1). The bottom row of the terminal window, which I’ll call the status bar, is reserved for status information and never shows any file content. In particular, it displays the current time in the format “HH:MM:SS” in the leftmost position of row R, and starting in column 10 of row R , it displays the range of line numbers of the file that are currently displayed in the format “Lines: num1-num2”, where num1 and num2 are integers, such as “Lines: 100-122”. While the program is auto-scrolling, the cursor is parked at position (R,C-2). At any time, the user can enter one of two key combinations to pause and restart autoscrolling: CTRL-Z or CTRL-C. CTRL-Z pauses scrolling. When the user enters CTRL-Z, the clock display continues to keep time but the file is not scrolled upward in the terminal. When the display is paused and the user enters CTRL-C, autoscrolling restarts. If scrolling is not paused, CTRL-C has no effect and when it is paused, CTRL-Z has no effect. The user can terminate the program at any time by sending any other terminating signal, such as SIGTERM, SIGQUIT, or SIGKILL or by by entering CTRL- on the keyboard. When any terminating signal is delivered to the process, the screen is cleared and the shell prompt returns. The following figure shows a sample of how the terminal’s area is used.• If the -s option is supplied, the rate at which the file is scrolled should be once every secs seconds. IMPLEMENTATION ISSUES • Because alarm() is not a timer, in order to get repeated alarms, the handler must set it every time it runs. (80+80+40 on each of 3 lines). autoscroll needs to reduce the range of lines it displays by 2 because of this long line. If the next line to be scrolled into view in the file is a long line, it should not display it until there is room in the terminal for the entire line, including wrapped content, to be visible. This implies that there will be space at the bottom until it can fit that line into the text display region. • In order to display the file as if it is scrolled, the program clears the screen above the status line and redraws the new range of lines. It does this every N seconds. Most terminals have a scroll buffer that saves what was in the terminal as it advances. autoscroll should clear that buffer as well. • The signal handler for the signal that alarm() sends must be able to access the text loaded into memory from the file, the positions of newline characters and many other variables. Because signal handlers do not have hooks for any data, and that data is most likely initialized in the main() function, these variables must be filescoped. • Once it has set up signal handling, read and loaded files, initialized all data structures and so on, the main() function does very little other than detecting when the user enters one of the two keyboard sequences. It just needs to make sure that it detects these key presses and always keeps the cursor parked in the lower left corner. The main() function should use the sigwait() system call with suitable processing when it returns. Read its man page. LIMITATIONS • There is no limit on the size of a file to be displayed, up to your computer’s own limits on memory and disk storage. The program should be able to open any text file that other applications can open. • The file can have lines that are longer than the width of the terminal window, but your program can assume that no line is longer than 4KB. • The program can assume that the file’s last character is a newline. Alternatively, it can allows files that do not end in a newline and it can add a newline at the end. You might find it is easier when it always ends in a newline. ERROR HANDLING If the required file argument is missing, it is an error that must be handled with a suitable usage message. If an option is supplied but is anything other than -s followed by a positive integer less than 60, it is an error. The program should report all errors on standard error along with the correct form of usage. SEE ALSO alarm(2), ioctl(3), sigwait(3), console_codes(7) Hints Debugging a program that has signal handlers and screen manipulation can be challenging. You should use a debugger such as gdb, and also use valgrind. You can also print to a second terminal window — open a second window, enter the command tty, record the output (such as /dev/pts/2) and in your program, write diagnostics to that file. Code Re-Use and Program Structure You are free to use any of the code in the class’s repository. There are a few demo programs in Chapter 9 that will be useful. All of them have GNU General Public Licenses. If you do use any of that code, the documentation should indicate which parts are not written by you. The program should be a single source code file. All functions other than main() should precede main() in the file. Instructions for Submitting the Assignment 1. Use the submithwk_cs49366 program to submit your program. To submit, if your file is ~/autoscroll.c, you’d enter $ cd ~ $ submithwk_cs49366 -t 5 autoscroll.c The program will copy autoscroll.c into the directory /data/biocs/b/student.accounts/cs493.66/hwks/hwk5/ and if it is successful, it will display the message, “File hwk5_username.c successfully submitted.” where username is your username. You will not be able to read this file, nor will anyone else except for me. But you can double-check that the command succeeded by typing the command ls -l /data/biocs/b/student.accounts/cs493.66/hwks/hwk5 2. You can do step 1 as many times as you want. Newer versions of the file will overwrite older ones. Grading Rubric This assignment is 18% of your final grade. The output must be correct and the program must conform to the rules written in the Programming Rules document on the class’s webpage. It must be thoroughly documented.
Introduction In this assignment, you will write a simple program to help a small theater sell movie tickets and confections, as well as keep track of its balance and prices. This program must allow prices to be updated, despite the number and type of goods never changing. Requirements The features described below must be in your program: • Your main method must keep track of the following, using appropriate data types: o The number of available seats, which starts at 50 o The price of a ticket, which starts at $30 o The price of popcorn, which starts at $25 o The price of soda, which starts at $10 o The price of candy, which starts at $15 o The theater’s current balance, starting at $0 • Your main method must implement a menu with the following options: o Sell tickets: Prompts the user for the number of tickets to sell. If there are enough seats available, update the number of available seats and the theater’s balance. If there aren’t enough seats, do update the balance or the number of seats available; print an error message instead. ▪ E.g.: If the theater has 10 seats available, a balance of $10, and each ticket is $5, selling 5 tickets will decrease the number of seats to 5 and increase the balance to $35. If the theater then tries to sell 7 tickets, the sale will fail: the balance will remain $35, and the number of seats remains 5. o End movie session: Resets the number of available seats back to 50. o Change ticket price: Prompts the user for the new price of a ticket, updating the appropriate variable. o Sell confection: Prompts the user if they want to sell POPCORN, SODA, or CANDY. Depending on which option is picked, increments the balance using the chosen confection’s price. o Change price of confection: Prompts the user for the confection whose price they would like to update. Then, prompts the user for the new price, updating the appropriate variable. o View balance: Shows the theater’s current balance. o View prices: Shows the current price of a ticket and of each individual confection. o Quit: Terminates the program.Deliverables • Assignment1.java (driver) Considerations • Be mindful of the data types you will use for each variable. Ask yourself what values are acceptable for that variable to hold, and that will usually tell you what data type should be used. • Remember that, unless stated otherwise, you should prefer to use “int” for data which will hold whole numbers and “double” for data that will hold numbers with a decimal component.Sample Output (user input in red) [Movie Theater Manager] 1. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 6Current balance is $0.001. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 1Sell how many tickets? 30 Sold 30 tickets at $30.00 for a total of $900.001. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 1Sell how many tickets? 25 Unable to sell 25 tickets: Only 20 seats available.1. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 3Enter new ticket price: $45.50 Ticket price updated.1. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 1Sell how many tickets? 15 Sold 15 tickets at $45.50 for a total of $682.501. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 2All seats have been vacated and cleaned.1. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 1Sell how many tickets? 42 Sold 42 tickets at $45.50 for a total of $1911.001. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 7 Current prices: Ticket: $45.50 Popcorn: $25.00 Soda: $10.00 Candy: $15.001. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 4Sell what confection? 1. Popcorn 2. Soda 3. Candy 1 Sold POPCORN for $25.001. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 5Change price of which confection? 1. Popcorn 2. Soda 3. Candy 3 Enter new CANDY price: $17.25 CANDY price updated.1. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 4Sell what confection? 1. Popcorn 2. Soda 3. Candy 3 Sold CANDY for $17.251. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 6Current balance is $3535.751. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 7 Current prices: Ticket: $45.50 Popcorn: $25.00 Soda: $10.00 Candy: $17.251. Sell tickets 2. End movie session 3. Change ticket price 4. Sell confection 5. Change price of confection 6. View Balance 7. View prices 8. Quit Enter option: 8Shutting off…
Task The find command is a very powerful command. Its man page details all of the different ways it can be used. In this assignment, you’ll write a simple version of find named sfind that implements just a few of its features. The assignment is specified by the following man-page-like description. Your job is to write a program that satisfies the requirements of this description. The information regarding program submission is at the end of the assignment. NAME sfind — find all files satisfying given test in given directory hierarchies SYNOPSIS sfind [dir1 dir2 …] [test] DESCRIPTION The sfind command searches through the given directories for all files that satisfy the given test. If no directories are given, it uses the current working directory. For each file for which the test is true, it prints the relative pathname of the file with respect to the top level directory of the search. For example, if a file named bar in the tree rooted at dir2 passes the test, the path that it prints starts with dir2. By default, this command will not follow symbolic links. When it examines a symbolic link, it tests the link itself, not its target. Only one test can be given to sfind, unlike the real find command. TESTS The following tests can be applied. -s filename The file being examined satisfies this test if it is a link to the same file as filename. This means, in particular, that it has the same inode index and is in the same filesystem as filename. -m fileglob The file being examined satisfies this test if its filename, meaning the pathname stripped of all leading directories, matches the fileglob. OUTPUT The pathname relative to the starting directory of the search is printed on a single line for every matching file. All error messages are written to the standard error stream, not standard output. EXAMPLES The following matches all files in any subdirectory of /usr whose name starts with b and ends with sh and has a single character in between. $ sfind /usr -m ’b?sh’ /usr/share/lintian/overrides/bash /usr/share/menu/bash /usr/share/doc/texlive-doc/metapost/featpost/bash /usr/share/doc/bash /usr/bin/bash The following matches all files in any subdirectory of ~ that are links to the same file as sf_scene.jpg. Here, sf_scene.jpg is in the current working directory. $ sfind ~/pictures -s sf_scene.jpg /home/stewart/pictures/desktops/DSC_2026.JPG /home/stewart/pictures/MyPhotos/SanFrancisco_2018/DSC_2026.JPG /home/stewart/pictures/MyPhotos/2018_07_08/DSC_2026.JPG EXIT STATUS 0 If it succeeded. 1 If it failed. SEE ALSO fnmatch(3), getopt(3) Error Handling The program should detect incorrect usage and report this on standard error along with the correct form of usage. Hints You should read the man page for fnmatch() and read the man page for getopt(). Notice that the test follows the directory names in this command. The getopt() man page explains how to handle this. Code Re-Use and Program Structure You are free to use any of the code in the class’s repository. There are a few demo programs in Chapter 8 that will be very useful. All of it has GNU General Public Licenses. If you do use any of that code, the documentation should indicate which parts are not written by you. The program should be a single source code file. All functions other than main() should precede main() in the file. Instructions for Submitting the Assignment 1. Use the submithwk_cs49366 program to submit your program. To submit, if your file is ~/sfind.c, you’d enter $ cd ~ $ submithwk_cs49366 -t 4 sfind.c The program will copy sfind.c into the directory /data/biocs/b/student.accounts/cs493.66/hwks/hwk4/ and if it is successful, it will display the message, “File hwk4_username.c successfully submitted.” where username is your username. You will not be able to read this file, nor will anyone else except for me. But you can double-check that the command succeeded by typing the command ls -l /data/biocs/b/student.accounts/cs493.66/hwks/hwk4 2. You can do step 1 as many times as you want. Newer versions of the file will overwrite older ones. Grading Rubric This assignment is 18% of your final grade. The output must be correct and the program must conform to the rules written in the Programming Rules document on the class’s webpage. It must be thoroughly documented.
Task This assignment requires attention to detail and it exercises several different knowledge areas. In particular, it requires a bit of command-line option parsing, reading a kernel data structure (the wtmp file), and manipulating time values. This assignment is specified by a man page. Your job is to write a program that satisfies the requirements of the following man page. The information regarding program submission is at the end of the assignment. I have written this man page to look like a “real one.” NAME logdata — print various statistics of login data of one or more users SYNOPSIS logdata [options] username … DESCRIPTION Without options, logdata prints one line for each username argument, containing the total time that the user has spent logged into the system since record-keeping was last started. If no usernames are listed, it displays this time for the current user. If there is no wtmp file, it prints a message on the standard error stream that there is no record-keeping. Otherwise, for each user to be reported, it displays the username followed by the total login time, accurate to the second, in days, hours, minutes, and seconds, as needed. If the total time is less than a day, the days field is omitted. If it is less than an hour, the hours and days are omitted, and if it’s less than a minute, only the seconds are displayed. If a username is given but there are no logins for the user, “0 seconds” is listed for that username. If any value is zero, the units for that value are not displayed. The definition of total login time for this command includes: • all time in completed login sessions, meaning those that have logouts associated with the logins, and • all time in login sessions that were terminated without a corresponding logout because there was a shutdown or a system reboot. The command excludes in the total reported time any time for which the login session is in progress at the time the command is invoked, meaning those that are still running. All times are in whole, non-negative decimal integers. Usernames are not sorted alphabetically. OUTPUT Output units are day(s) for the number of days, hour(s) for the number of hours, min(s) for the number of minutes, and sec(s) for the number of seconds. For example: boromir 1 day 9 hours 39 mins 51 secs frodo 14 hours 1 sec gandalf 22 days 42 mins The plural form of the unit should be used for any amount other than 1. In the second case, it is an implicit time of 14 hours, 0 minutes and 1 second. In the third, it is 22 days, 0 hours, 42 minutes and 0 seconds. OPTIONS The behavior of the command can be modified with the following option: -a Show the log times for all users that have entries in the file _PATH_WTMP. -s Produce a line of output at the end showing the totals for all users listed. -f Use instead of _PATH_WTMP. EXIT STATUS 0 If it succeeded. 1 If it failed. FILES /var/log/wtmp SEE ALSO last (1), utmp (5), wtmp (5) Error Handling The program should detect missing command-line arguments and report the error and correct usage. Code Re-Use and Program Structure You are free to use any of the code in the class’s repository. All of it has GNU General Public Licenses. If you do use any of that code, the documentation should indicate which parts are not written by you. The program should be a single source code file. All functions other than main() should precede main() in the file. Instructions for Submitting the Assignment 1. Use the submithwk_cs49366 program to submit your program. To submit, if your file is ~/logdata.c, you’d enter $ cd ~ $ submithwk_cs49366 -t 3 logdata.c The program will copy day2date.c into the directory /data/biocs/b/student.accounts/cs493.66/hwks/hwk3/ and if it is successful, it will display the message, “File hwk3_username.c successfully submitted.” where username is your username. You will not be able to read this file, nor will anyone else except for me. But you can double-check that the command succeeded by typing the command ls -l /data/biocs/b/student.accounts/cs493.66/hwks/hwk3 2. You can do step 1 as many times as you want. Newer versions of the file will overwrite older ones. Grading Rubric This assignment is 20% of your final grade. The output must be correct and the program must conform to the rules written in the Programming Rules document on the class’s webpage. It must be thoroughly documented.
Preface This assignment is a warm–up programming exercise. The program that you need to write is small, but you’ll have to learn a few things to write and run it. Instructions For this first assignment you’ll write a short C program. This program will have just two lines of output. The first line will contain the username of the user who runs it, along with their userid and home directory, all in a single sentence of the following form. My username is sweiss, my userid is 1220, and my home directory is /data/biocs/b/cshome/sweiss. in which sweiss is replaced by the person’s username, 1220 would be replaced by their userid, and /data/biocs/b/cshome/sweiss would be replaced by the absolute pathname of their home directory. The output must be exactly in this form, absolutely, without exceptions! The second line of output will be one of the following two lines: My shell is path-to-shell in which path-to-shell is replaced by the actual value of the SHELL environment variable or The value of my DISPLAY variable is display-variable-value in which display-variable-value is replaced by the actual value of the DISPLAY environment variable. Which line is your program supposed to output? • If your actual userid on our computer network is an even number, your program must output the SHELL variable line. • If it is an odd number, your program must output the DISPLAY variable line. If I ran this program on the server, the session would look like the following: $ hwk1 My username is sweiss, my userid is 1220, and my home directory is /data/biocs/b/cshome/sweiss. My SHELL is /bin/bash. If my userid were 1221, then the output would be $ hwk1 My username is sweiss, my userid is 1220, and my home directory is /data/biocs/b/cshome/sweiss. The value of my DISPLAY variable is localhost:10.0. Error Handling Guidance • To write this program, you’ll need to learn how to use a few of the functions and system calls we saw in Chapter 1. I suggest looking at the programs in Chapter 1 of the demos directory. There you’ll see an example from which you can start. • What is your userid on our system? Chapter 1 shows you the command for finding it. • The program has to print out the userid of the user who runs it. There is a function that can get that userid. What is it? A search of the man pages (apropos command) can find it for you. • The program needs to format the output. It’s time to learn how to use printf(). The printf() man page (Section 3 of the man pages, not Section 1) is long but it has everything that you need to know. The demo programs are a good starting point as well. • Because the program has to print a single sentence with the values of various environment variables, it will need to copy strings. This will be clear when you read Chapter 1 carefully and when you read the appropriate man pages. Functions for copying strings are abundant in C. If you’ve never used any, you can either: – read the C Language Reference Manual, Section 7.24, to learn about the functions that can do this, or – search the man pages for a set of candidates, using apropos. If you try this, use the -a option for “anding” the search terms, and try entering “copy” and “string” together. Instructions for Submitting the Assignment 1. Use the submithwk_cs49366 program to submit your program. It can be run on any cslab host, so login to a cslab host when you’re ready to submit. To submit, if your file is named myhwk.c, you’d enter $ cd ~ $ submithwk_cs49366 -t 1 myhwk.c The program will try to copy myhwk.c into the directory /data/biocs/b/student.accounts/cs493.66/hwks/hwk1/ and if it is successful, it will display the message, “File hwk1_username.c successfully submitted.” where username is your username. You will not be able to read this file, nor will anyone else except for me. But you can double-check that the command succeeded by entering the command ls -l /data/biocs/b/student.accounts/cs493.66/hwks/hwk1 2. You can do step 1 as many times as you want. Newer versions of the file will overwrite older ones. Grading Rubric This assignment is 8% of your final grade. The output must be correct and the program must conform to the rules written in the Programming Rules document on the class’s webpage. It must be thoroughly documented.
Starter code: See for the Github link. Submission: You can work on this assignment in a pair, or alone. Submit the contents of your repository via Gradescope. See Deliverables below for what to submit. If you are working with a partner, do not forget to include their name with the submission. Note: There will be no autograder for this assignment as we have no way of running a custom filesystem on Gradescope. We have provided tests. Note: Clone and start studying the starter code as soon as possible. This assignment will likely require more programming effort than previous assignments. A File System In this assignment you will build a filesystem driver that will let you a 1MB disk image (data file) as a filesystem. We also provide an that will lead you through installing FUSE and familiarizing yourself with parts of the starter code. Step 1: Install FUSE For this assignment you will need to use your VM. You’ll need to install the following packages: • libfuse-dev • libbsd-dev • pkg-config Running $ sudo apt-get install libfuse-dev libbsd-dev pkg-config should do the trick. Step 2: Implement a basic filesystem You should extend the provided starter code so that it lets you do the following: • Create files, supporting files with names at least 10 characters long • List the files in the filesystem root directory (where you mounted it) • Write to small files (under 4k) • Read from small files (under 4k) • Rename files • Delete files You will need to extend the functionality in nufs.c, which only provides a simulated filesystem to begin with. This will require that you come up with a structure for how the file system will store data in it’s 1MB “disk”. See these and for inspiration. We have provided some helper code in the helpers/ directory. You can use it if you want, but you don’t have to. However, blocks.{c,h} and bitmap.{c,h} might save you some time as these implement block manipulation over a binary disk image. Feel free to extend the functionality if needed. Some additional header files that might be useful are provided in the hints directory. These are just some data definitions and function prototypes to serve as an inspiration for abstraction layers. They are provided “as-is”, meaning you’ll need to make sense of them. Reading up on file system implementation in the OSTEP book might help. If they don’t seem helpful, you are free to implement your own abstractions. Step 3: Directories In this step, implement support for arbitrarily nested directories. The filesystem should support the following operations on directories: • Creation (mkdir) • Renaming (rename) • Listing the contents of directories (readdir) • Deleting (rmdir) • Creating files contained in directories, moving files between directories Step 4: Big files Extend the filesystem to support files larger than 4K. The files must fit into the free blocks on disk. This must include proper allocation and deallocation as the file grows or shrinks. The file system needs to be able to handle the following example situations: • at least 100 files with size 4K (part of the base assignment) • at least 5 files with size 100K • at least 1 file with size 500K Deliverables Please read the instructions carefully and ask questions. If you do not submit to the correct assignment on Gradescope, we cannot guarantee that we will grade your assignment before the end of semester. Pre-submission After doing Step 1, that is, after cloning the repository and installing FUSE, 1. Execute the command $ pkg-config –modversion fuse &> fuse_version 2. Commit the file fuse_version to your repo Main submission Modify the starter code to implement the requested functionality (steps 2, 3 and 4). Commit the code to your repository. Do not include any executables, .o files, or other binary, temporary, or hidden files (unless they were part of the starter code). Do not include any disk images. Once you are done, remember to submit your solution to Gradescope and do not forget to include your partner. Submit under Project 2: Main Submission Provided Makefile and Tests The provided Makefile should simplify your development cycle. It provides the following targets: • make nufs – compile the nufs binary. This binary can be run manually as follows: $ ./nufs [FUSE_OPTIONS] mount_point disk_image • make mount – mount a filesystem (using data.nufs as the image) under mnt/ in the current directory • make unmount – unmount the filesystem • make test – run some tests on your implementation. This is a subset of tests we will run on your submission. It should give you an idea whether you are on the right path. • make gdb – same as make mount, but run the filesystem in GDB for debugging • make clean – remove executables and object files, as well as test logs and the data.nufs. Rubric The grade is broken down into three categories: • 50% Basic functionality and FS design – Based on manual testing and using a grading script – Does the filesystem correctly and efficiently implement the requested functionality? – Do operations complete in a reasonable time? We put a 30s timeout on most test cases. – Is the file system able to store at least 100 small (≤ 4K) files? • 15% Directory functionality • 10% Big file support • 20% Style – Via manual code review – Basics: meaningful purpose statements; explanation of arguments and return values – Explicitly stated assumptions – Short, understandable functions (generally, < 50 lines) – Consistent indentation and use of whitespace – Explanatory comments for complex blocks of code – No extra binaries (.o, executable files, etc.) or superfluous files committed to your repo Hints & Tips • There are no man pages for FUSE. Instead, the documentation is in the header file: /usr/include/fuse/fuse.h (available online at • The sources for contains a few further Start with • The basic development / testing strategy for this assignment is to run your program (e.g., using make mount) in one terminal window and try file system operations on the mounted filesystem in another separate terminal window. • Read the manual pages for the system calls you’re implementing. • To return an error from a FUSE callback, you return it as a negative number (e.g. return -ENOENT). Some things don’t work if you don’t return the right error codes. • Read and write, on success, return the number of bytes they actually read or wrote. • You need to implement getattr early and make sure it’s correct. Nothing works without getattr. The modes for the root directory and hello.txt in the starter code are good default values for directories and files respectively. •
