Two Northeastern University students Elizabeth and James have proposed the following new sorting algorithm: (a) Prove that the call NEW-SORT(A, 1, n) correctly sorts the input array A[1 : n], where n represent length of A. (b) Give a recurrence for the worst-case running time of NEW-SORT and a tight asymptotic Θ-notation) bound on the worst-case running time. (c) Compare the worst-case running time of NEW-SORT with that of insertion sort, merge sort, heapsort, and quicksort. Do the students deserve a straight A in the course?In our Algorithms class, 8 students are avid chess players. Each of these 8 students has a “rating” that measures their quality as a chess player. The higher the rating, the better they are. For the purposes of this problem, assume that everyone keeps their chess rating a private secret; however, when two players have a chess match, the person with the higher rating wins 100% of the time. These highly-competitive students have asked you to create various comparison-based algorithms to resolve some questions they have about their relative chess ratings. For each of these questions, your algorithm will be a sequence of matches (e.g. A vs. B, C vs. D) that will solve the problem in the most efficient way. (a) The students want you to sort them according to their chess rating, from best (1st) to worst (8th). Prove that there does not exist an algorithm that is guaranteed to solve this problem in 15 or fewer matches. (b) The students want you to determine which player has the highest chess rating and which player has the lowest chess rating. Create an algorithm that is guaranteed to solve this problem in 10 matches, and clearly explain why there does not exist an algorithm that is guaranteed to solve this problem in 9 or fewer matches. (c) The students want you to determine which player has the highest chess rating and which player has the second-highest chess rating. Create an algorithm that is guaranteed to solve this problem in 9 matches, and clearly explain why there does not exist an algorithm that is guaranteed to solve this problem in 8 or fewer matches.Let A be an array of n non-negative integers, where the maximum element is k. If k = O(n), then Counting Sort is an O(n) time algorithm to sort our array A. This is a significant improvement over comparison-based sorting algorithms which are at best O(n log n). (a) Let A = [4, 5, 0, 1, 3, 4, 3, 4, 3, 0, 3]. Walk through each step of the Counting Sort algorithm on this input array, to produce the correct output of [0, 0, 1, 3, 3, 3, 3, 4, 4, 4, 5]. (b) We say that a sorting algorithm is stable provided that whenever there are two equal elements (x and y), where x appears before y in the input, then x must appear before y in the sorted output. For example, in the above input array A, if we highlight the three numbers marked 4 using the colors red, white, and blue (in that order), then in the sorted output array, our 4’s will be listed red, white, and blue (in that order). Clearly explain why the Counting Sort algorithm is stable. (c) Consider Quicksort and Heapsort. For each of these two sorting algorithms, explain whether the algorithm is stable. If the answer is YES, briefly explain why. If the answer is NO, provide a simple counterexample to show that stability is not guaranteed.LeetCode (www.leetcode.com) is a popular website for Northeastern MSCS students, especially when preparing for job interviews. https://leetcode.com/problemset/algorithms/ There are over a thousand “coding challenges” from which students can practice and improve their skills in Algorithm Analysis and Design, and the website supports numerous programming languages, including C, Java, and Python. In this Programming Project, you will create a portfolio consisting of TWO LeetCode problems on Dynamic Programming you will solve over the next two weeks. You can choose ANY set of TWO problems from the following site (click on ”Dynamic Programming” to filter the results), but see the following note first. Important Note: You can pick anything excluding the DP problems except the problems we will discuss in class during Week 5 − 6: • Fibonacci or Climbing Stairs – Leetcode 70. Climbing Stairs – Leetcode 509. Fibonacci Number • Rod Cutting – Leetcode 1547. Minimum Cost to Cut a Stick (similar problem) • Longest Common (or Increasing) Sub-sequence – Leetcode 1143. Longest Common Subsequence – Leetcode 300. Longest Increasing Subsequence • Activity-Selection – Leetcode 435. Non-overlapping Intervals (closest equivalent) • Knapsack or Coin Change – Leetcode 322. Coin Change – Leetcode 416. Partition Equal Subset Sum (0/1 Knapsack variant) • House Robber – Leetcode 198. House Robber NOTE: To maximize your learning and problem-solving skills, we encourage you to explore these concepts through fresh challenges. The idea is for you to get more exposure to problem-solving, so for your own benefit, please stay away from these problems![Read Carefully] This HW offers a lot of flexibility but there are four important rules: (I) If the problem took you less than 30−40 minutes to solve, you may not include it in your portfolio. (Since then the question was an exercise for you, rather than a problem or a challenge.) (II) You may only include problems you have solved after Sep 22, 2024. (III If you click on the LeetCode “Solution” or “Discuss” button before you solve the problem or look at any online resources for hints to solve a LeetCode problem, especially sites such as Chegg, GitHub, Stack Overflow, and Quora, you cannot include it in your portfolio. (You may look at these sites after you solve the problem.) (IV) Under no circumstance may you use Co-Pilot, LLMs or any other AI-assisted programming tools.Here is how your portfolio will be assessed. (a) (8 marks) For each of the problems you are including in your portfolio (two problems), provide the problem number, problem title, difficulty level, and the screenshot (showing all the details, submission time, etc) of you getting your solution accepted by LeetCode. You will receive up to 4 marks for each problem you submit. Here is an example from a sample portfolio: Longest Palindromic Substring (medium) You will get full credit for any correct solution accepted by LeetCode, regardless of the difficulty of the problem, and regardless of how well your runtime and memory usage compares with other LeetCode participants. (b) (2 marks) For one of the two problems you solved, explain the various ways you tried to solve this problem, telling us what worked and what did not work. Describe what insights you had as you eventually found a correct solution. Reflect on what you learned from struggling on this problem, and describe how the struggle itself was valuable for you. Reflect on what might be causing the obstacle (e.g. lack of familiarity with a particular data structure, lack of knowledge about a fast and efficient algorithm, etc.) Note: For your reflections, write a minimum of 250 words.Extra Challenge Question (practice ONLY ) Alice in a Coding Interview Attention: This question is crafted for students seeking an extra challenge. You’re welcome to skip this and submission is NOT required. Alice is a second-year M.S. of Computer Science student in our beautiful Vancouver Campus. She has recently participated in a coding interview with a tech company in Vancouver. During the interview, she faces the following question which also happens to be one of the main topics of Week 3 of our Algorithm class. • Let’s say you are running an e-commerce platform, and you want to identify the top k most popular products in your store based on customer purchase history. Given an integer array nums and an integer k, return the k most (frequently sold) popular product IDs. You may return the answer in any order. If you were Alice, how would you approach this question? (a) First, try to quickly come up with a brute-force solution. This should not take more than 10 minutes. Your only concern should be the correctness of your algorithm, not its efficiency. – Write a simple pseudocode for your algorithm, briefly describe the time complexity of your algorithm, and code it up in Python. (b) Now, try to see if you can optimize your algorithm in (a), and come up with a more efficient solution. There is no requirement on how fast your solution needs to be, it just needs to be better than the one given in (a). – Write a simple pseudocode for your algorithm, briefly describe the time complexity of your algorithm, and code it up in Python.(c) Finally, with the learning from the previous two steps, I want you to come up with a decent solution for this problem. Note that your algorithm’s time complexity must be better than O(nlogn), where n is the array’s size. – Write a simple pseudocode for your algorithm, briefly describe the time complexity of your algorithm, and code it up in Python.
Hello! I’m the Happy Question, a unique puzzle in your journey of complexity and code. You earn 8 marks just by reading me! Isn’t that a delightful linear algorithmic problem to solve? In the world of algorithms, where efficiency and speed often reigns supreme, it’s easy to get caught up in the pursuit of optimal solutions. But what about the journey itself? Sometimes, the most rewarding experiences aren’t about the final destination, but the process we embark upon. This concept, known as delayed gratification, is the idea of forgoing immediate pleasure for a larger, more satisfying reward in the future. Invitation: Before we dive into our algorithmic puzzle, let’s explore the idea of delayed gratification a bit further. Take a few minutes to read about the ”Marshmallow Experiment” here: https: //jamesclear.com/delayed-gratification Puzzle: Now, let’s consider the world of algorithms through the lens of delayed gratification. Can you identify and describe an algorithm that: • Prioritizes immediate gratification: Perhaps an algorithm that seeks a quick solution, even if it’s not the most efficient or accurate. • Embraces delayed gratification: An algorithm that might take more time or computational resources upfront, but ultimately leads to a superior outcome. Wondering what should you submit for this question? Nothing! Remember, in the midst of searching for optimal solutions, it’s okay to pause and appreciate the journey. After all, in Algorithm Land, the Happy Question reminds us that sometimes, being present and engaged is a reward in itself!Background In this assignment, we’ll explore an advanced hybrid sorting algorithm that combines the strengths of multiple sorting techniques to achieve both efficiency and guaranteed worst-case performance. This algorithm is used in some standard library implementations of sorting functions. Algorithm Description: The algorithm works as follows: – Start with a divide-and-conquer approach similar to Quicksort. – Track the recursion depth during the sorting process. – If the recursion depth exceeds a certain threshold (typically 2 log2 (n), where n is the number of elements), switch to a heap-based sorting method. – For small subarrays (typically less than 16 elements), use an insertion-based sorting method. Note: You don’t need to implement Insertion sort, Quicksort or Heapsort from scratch. (a) Implement the described hybrid sorting algorithm in a programming language of your choice (Preferably Python). Include helper functions for the divide-and-conquer approach, heapbased sorting, and insertion-based sorting. (b) Analyze the time complexity of this hybrid algorithm. Discuss best-case, average-case, and worst-case scenarios. (c) Conduct an empirical analysis: – Generate arrays of various sizes (e.g., 100, 1000, 10000, 100000 elements) with random, nearly sorted, and reverse sorted data. – Compare the performance of this hybrid algorithm with standard Quicksort, Heapsort, and Insertion Sort). Present your results in tables or graphs. (d) Briefly discuss general trends and observation from (c) and suggest one or two practical realworld applications where this hybrid algorithm might be particularly useful.Play one or more games of “Guess My Number”, which you can do so on this website: https://www.mathsisfun.com/games/guess_number.html What you will do is change the Range of numbers from 1 to 1000, and then click on Start. The computer will pick a random integer between 1 and 1000, with each number equally likely to be chosen. After each guess, the computer will tell you whether your guess was correct, whether it was too high, or whether it was too low. The game stops when you have correctly guessed the computer’s number. For example, when I did this game, I was able to get the computer’s number in 10 guesses. (a) Attach a screenshot of you winning this game in at most 10 guesses. (No proof or explanation is necessary – all you need to do is insert a .jpg image, just as I did above.) (b) Suppose the range of numbers is between 1 and n, where n is a positive integer. If n = 15, prove that the game can always be won in at most 4 guesses, no matter what the computer’s number is. Clearly explain how your “guessing algorithm” works. (c) Let T(n) be the maximum number of guesses required to correctly identify an integer between 1 and n. For example, you have shown above that T(15) = 4. Determine a recurrence relation for T(n), and apply the Master Theorem to show that T(n) = Θ(log n). (d) For each integer n, let A(n) be the average number of guesses required to correctly guess the computer’s number, where each of the target numbers from 1 to n is equally likely to be chosen. For example, you can show that A(15) = 49 15 using your algorithm from part (b). Determine the exact value of A(1023), carefully justifying all of the steps in your calculation.(a) Draw the recurrence tree for the following recurrence formula (only the first three levels): (b) Write the recurrence for the following recurrence tree: (c) Let f(n) and g(n) be two functions, defined for each positive integer n. By definition, f(n) = O(g(n)) if there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c · g(n) for all n ≥ n0. Determine if the following statements are correct or incorrect, and briefly justify your answer in each case. – 4 n = O(2n ) – n 1000 = O(2n )An investment company has an AI-powered model that predicts stock prices for n consecutive days. Given these predictions, determine the maximum possible profit that can be made by buying and selling a single stock. Note: Due to potential tax implications associated with day trading, we assume that only a single purchase and sale are allowed. Your solution should just return the maximum possible profit. Sample Input: [100, 115, 90, 120, 85, 130] Sample Output: 35 Explanation: The maximum profit can be achieved by buying at 85 and selling at 130, resulting in a profit of 130 – 85 = 35. (a) Naive Approach: Describe (single paragraph) the idea and logic behind your brute force solution and its time complexity. (b) Pseudocode: Now, design a DAC algorithm and provide detailed pseudocode for your algorithm, ensure that the pseudocode is comprehensive, and add comments when necessary to enhance its readability. Design a O(n log n) DAC algorithm for this problem to qualify for full credit. (c) Algorithm Analysis: Analyze the time complexity of your proposed DAC algorithm from part (b). Write the recurrence relation for your algorithm and apply the Master Theorem to determine its complexity.Extra Challenge Question (practice ONLY ) Closest Pair Problem in Supply Chain Management Attention: This question is crafted for students seeking an extra challenge. You’re welcome to skip this and submission is NOT required. In our class, we explored the standard closest pair problem in a 2D plane. Now, let’s consider a practical application in the field of supply chain management. Imagine a scenario with numerous suppliers and vendors dispersed across a geographical region. These suppliers might be factories or farms producing goods, while vendors could be markets or retail stores requiring these goods. A key goal in this context is to enhance supply chain efficiency by reducing transportation costs and time. Minimizing travel distance is crucial not only for cost reduction but also for lowering environmental impact. (a) Modified Algorithm: Discuss how you would modify the standard closest pair algorithm to address the needs of the stakeholders in the scenario described above. Focus on the aspects of the algorithm that would be adapted or enhanced to optimize matching between suppliers and vendors, taking into account factors like distribution of locations and varying supply and demand. (b) Algorithm Analysis: Analyze the time complexity of your proposed algorithm from part a. Write the recurrence relation for your algorithm and apply the Master Theorem to determine its complexity. Compare this with the complexity of the standard closest pair algorithm, and explain any differences or similarities. (c) Pseudocode: Provide a detailed pseudocode for your modified algorithm, similar to the one discussed in class. Ensure that the pseudocode is comprehensive and reflects all the modifications you proposed in part a. Highlight any steps that specifically address the supply chain scenario.
You’ll write several functions in RISC-V, using our web-based RISC-V interpreter, with parameter passing, a local variable, and proper stack management. The interpreter is here: https://riscv.jhibbele.w3.uvm.edu You may work individually or with a partner. Graduate students must work individually. 1.1 First function Write RISC-V code to implement this function: int f1(int p) { int k = 18; k = p + k; return k; } And then create a “main” (actually, just a label), and call this function with the parameter 12. Your function should start at a label named f1. Use the pattern of “one parameter, one local variable” as a framework for your function. Use the a0 register for the parameter; use a0 also for the local variable k; use a0 and a1 to do your calculation; and put the return value in a0. You’ll need 16 bytes (four words) of storage on the stack, so the first four instructions in your function should be these: f1: addi sp, sp, -16 # reserve 4 words on the stack sw ra, 12(sp) # save ra sw s0, 8(sp) # save s0 addi s0, sp, 16 # set s0: top of stack and the last four lines of your function should be: lw s0, 8(sp) # restore s0 lw ra, 12(sp) # restore ra addi sp, sp, 16 # restore the stack pointer jalr x0, ra, 0 # return (jump to ra) Be sure to put the return value in a0. You’ll also need to save p and k on the stack, in the region you reserve. Here’s a diagram of the stack: 1 Call the function by putting 12 into a0 and executing jal ra, f1. This will let f1 return to the instruction after the function call. After the function returns, you should see the value 30 in the a0 register. Before you call the function, set the stack pointer to a non-zero value, such as 64: addi sp, x0, 64 and then set the parameter and call the function: addi a0, x0, 12 jal ra, f1 1.2 A second function Write RISC-V code to implement this function: int f2(int p1, int p2) { if ( p1 > p2 ) return p1; else if ( p1 < p2 ) return p2; else return 0; } Use two parameters. There are no local variables, so you can use allocate four words for the stack: ra, s0, and the two parameters. Your stack should look like this: 1.3 Local variables Whenever you want modify a local variable, you should first load the variable from the stack into a register, then make the modification, and then save the updated value back to the stack. So for example, if the local variable i is in sp + 16, and I want to increment i, then I could do the following: lw a0, 16(sp) addi a0, a0, 1 sw a0, 16(sp) 1.4 Code examples I’ve put example RISC-V code, showing how various high-level structures are coded in RISC-V, in the class repo in gitlab. 2 2 Testing Put your code in a file named riscv.netid.s. As you change your code in the interpreter, be sure to save it (there is no autosave feature). Use comments liberally—comment every line. This will help you organize your thoughts and keep track of what your code is doing. Watch the values of the registers as your code runs. Use breakpoints as appropriate. Coding in assembly language takes practice and concentration and attention to detail. 3 What to Submit Submit your file riscv.netid.s containing your f1 and f2 and f3 and your main (which will contain a call to each function). 4 Graduate Students Students taking the course for graduate credit, and undergraduates for a bit of extra credit: write two additional functions: intdiv() and intsqrt(). 4.1 Integer division Write RISC-V code to implement this function: int intdiv(int numer, int denom) { if ( denom = 0 ) { numer = numer – denom; q = q + 1; } return q-1; } Given integers numer and denom, this will produce the largest integer q such that q × denom ≤ numer. 4.2 Integer square root It’s straightforward to approximate the square root of positive real number by using an iterative technique. For an integer p, we can define the integer square root of p to be the largest integer n such that n 2 ≤ p, and we can employ the same iterative technique, using integer arithmetic. Write RISC-V code to implement this function: int intsqrt(int p) { if ( p < 0 ) error 8; int i0 = p >> 1; // this divides p by 2 if ( i0 > 0 ) { int i1 = ( i0 + p / i0 ) >> 1; // this divides by 2 while ( i1 < i0 ) { i0 = i1; i1 = ( i0 + p / i0 ) >> 1; // divide by 2 3 } return i0; } else { return p; } } Use your intdiv function to do the division. To call intdiv, put the first parameter in a0 and the second parameter in a1. After the function returns, the result will be in a0. Put your two functions in a file named riscv-grad.netid.s. 4
You’ll write two CUDA programs. You may work with a partner, but graduate students must work individually. Do not wait until the last minute! The use of the systems in the VACC is unpredictable, and there could be a surge in use at the end of the semester! Or, if you have a system with an Nvidia GPU, you can download and install the CUDA development environment and do the work on your own system.See specific instructions and examples in the CUDA: How-To presentation.For this assignment, use cudaMalloc() and cudaMemcpy(). (Don’t use unified memory.) (1) Dot product Do the dot-product example from class: compute the dot product of two float vectors of length N. Calculate the elapsed time for the GPU computation and for the same computation on the CPU. Calculate the GPU elapsed time two ways: not including the memory copies, and then including the memory copies. Set the values of the u and v vectors to random numbers in the range (0, 1). (Use the Linux drand48() function.)The first part of Lecture 4-E (CUDA Part Three) shows how to measure elapsed time on the GPU, and Lecture 4-F (CUDA How-To) shows how to measure time on the CPU. Implement this function: __global__ void dotp( float *u, float *v, float *partialSums, int n ); Use 256 threads per thread block and 256 blocks. Accumulate each thread block’s result in shared memory, and do parallel reduction on the shared memory, as described in the lectures.Also, compute the relative error. The relative error between two scalar values x and y is |x − y| / |x|, with x 6= 0. (Compute the relative error on the CPU.) You should see a relative error of about 1 × 10−6 . Do this for n = 256 ∗ 256. You do not need to use a grid-stride loop. (2) Matrix-vector product Implement a matrix-vector product function: __global__ void MxV( float *M, float *x, float *y, int n); This will do the calculation y = Mx, given the n × n matrix M and the n × 1 vector x. 1 Each thread will do a dot product: thread i will do the dot product of row i of M with the vector x and put the result in y[i]. (This is a separate program altogether from the first program–you’re not using your dot-product function here.) Don’t use a grid-stride loop: assume that n is less than #blocks × #threads per block. Use 256 threads per thread block, and pick a value of n such as n = 5000. This matrix-vector multiplication will require a huge number of floating-point operations: each entry in y will require n multiplications and n additions; so the total number of multiplications will be n 2 , and the total number additions will be n 2 . Calculate the elapsed time for the GPU computation and for the same computation on the CPU. Calculate the GPU elapsed time two ways: not including the memory copies, and then including the memory copies. Set the entries of M and of x to uniformly distributed random numbers in the range (0, 1). Again, use cudaMalloc() and cudaMemcpy(). (Don’t use unified memory.) Write a function to do the matrix-vector product on the CPU, and compute the relative error between your two solutions. The relative error between two vectors u and v is given by relerr = ||u − v|| / ||v||, (1) assuming v is not zero. || · || is the norm of a vector; the two-norm ||u|| is given by ||u|| = (Pn 1 u 2 i ) 1/2 . When I run, I see about a 3x speedup with n = 5000, and my relative error is on the order of 1 × 10−8 . My GPU time is about 40 ms including the memory copying and less that 1 ms without the memory copies. Graduate Students Implement matrix multiplication: the kernel to multiply two n × n matrices is straightforward: // computing C = A*B float sum = 0.0; int col = threadIdx.x + blockDim.x * blockIdx.x; int row = threadIdx.y + blockDim.y * blockIdx.y; int numEltsPerRow = n; // #elements in each row if (col < n && row < n) { sum = 0.0; for (k = 0; k < n; k++) sum += A[row * numEltsPerRow + k] * B[k * numEltsPerRow + col]; C[row * numEltsPerRow + col] = sum; } This kernel computes a single matrix element in the product. And as long as n
You’ll write a problem to simulate the processing of machine instructions in a CPU. These instructions are similar in form to RISC-V instructions, which we’ll study in detail. You may work individually or with a partner.2 Instructions An instruction is a four-byte (32-bit) integer. 2.1 Instruction format The fields of an instruction are located in fixed positions in these 32 bits, as shown in the following diagram: Undergraduates: assume that an immediate value is non-negative. Graduate students: treat signed immediate values correctly, using two’s complement representation (see below). In your program, the instructions will be stored in an integer array (or list) that represents the memory of the system.2.2 Registers A register is a storage location for a single four-byte integer. There are a small number of registers. They are named R0, R1, …, Rn-1. The register R0 is a read-only register that always has the value zero.2.3 Instructions to implement In the following, Rd denotes the destination register; Rs1 is the first source register, and Rs2 is the second source register. Implement the following instructions: NOOP opcode = 0 (0000). Do nothing. ADD Rd, Rs1, Rs2 opcode = 1 (0001). Add the contents of Rs1 and Rs2 and put the result in Rd. ADDI Rd, Rs1, immed opcode = 2 (0010). Add the contents of Rs1 to the immediate value and put the result in Rd. BEQ Rs1, Rs2, immed opcode = 3 (0011). If the contents of Rs1 and Rs2 are the same, then set next pc to pc + immed; otherwise do nothing. JAL Rd, immed opcode = 4 (0100). Save pc + 1 to Rd and set next pc to the contents of pc + immed. LW Rd, immed(Rs1) opcode = 5 (0101). Load the value from memory location immed + Rs1 and put that value into Rd. SW Rs1, immed(Rs2) opcode = 6 (0110). Store the value from Rs1 into memory location immed + Rs2. RETURN opcode = 7 (0111). Terminate the processing of instructions. 3 The Program The basic function of a microprocessor can be described in pseudocode: while true: fetch the next instruction, which is the instruction at location pc set next_pc to pc + 1 decode the instruction execute the instruction // JAL will change next_pc; BEQ could change next_pc set pc to next_pcWrite a program to implement this. Create a CPU class and an Instruction class. CPU should have these member variables: • pc: an integer • next pc: an integer • memory: an array (list) of MEM SIZE integers • regs: an array (list) of NUM REGISTERS integers Set NUM REGISTERS to 16 and MEM SIZE to 65536. (In Python, memory and registers will be integer lists.) Put the value zero into each register and into each memory location initially.The Instruction class should have these five member variables: opcode, Rd, Rs1, Rs2, and immed. All are integers. The instructions themselves will be in the memory array/list. The variable pc is an index into this array. So for example, if the value of pc is 100, then then next instruction fetched would be the integer at position 100 in the array/list.3.1 Building instructions Write a function to take the components that make up an instruction (the opcode, the destination register, source register #1, source register #2, the immediate value) and build a four-byte instruction. Not every instruction will have each of these components. I did the following: def build_instruction(opcode, Rd, Rs1, Rs2, immed): instr = opcode
You’ll write a program to simulate the behavior of a hardware memory cache. You can use the language of your choice. You may work either by yourself or with a partner, except students taking the course for graduate credit must work individually.1.1 High-level summary You’ll write two functions: the first is to read a word from address A; and the second is to write a word to address A. Each of these functions first looks in the cache. If the word at A is in the cache, then the read function will read the value (a single word); and the write function will write the value (again, a single word).If the word at A is not in the cache, then you’ll read a cache block from memory into the cache and update the cache data structures. Remember: data is read from memory to the cache a whole block at a time. A word is four bytes.1.2 Memory hierarchy Model the memory as an array of bytes. Each memory access will read or write one word (four bytes). Check that each address is aligned on a four-byte boundary, and assert (or exit) if it isn’t. Also check that each memory access is in range, and assert (or exit) if it isn’t. In Python, use a bytearray; in C use a char[].You’ll model a little-endian system, with 32-bit words: so for example if memory[56] = 45 and memory[57] = 12 and memory[58] = 3 and memory[59] = 7, then the word referenced by address 56 would be 45 + 256 ∗ (12 + 256 ∗ (3 + 256 ∗ 7)) = 117640237. When a range of values is loaded into the cache, the number of bytes loaded will thus be a multiple of four.1.3 Cache structure Recall how the index, tag, and block offset are computed from an address. For example suppose we have the following: • a 64K memory (and 16-bit addresses) • a 1K cache • 64-byte cache blocks • four-way associativity Then: 1 • there are 210/2 6 = 16 cache blocks (since 1024 = 210 and 64 = 26 ). • and 16/4 = 4 cache sets (because the cache is four-way set associative) • so we need two bits for set selection (the index; two bits let us specify the value 0, 1, 2, or 3) • and six bits for byte selection in a block (six bits lets us specify a value in the range 0 to 63, inclusive) • which means that the tag is 16 − 2 − 6 = 8 bits in length1.4 Parameters Your simulator should let you specify these parameters: • the size of a memory address, in bits (and then set the size of the memory to 2 to the power #bits) • the size of the cache, in bytes (must be a power of 2) • this size of a cache block, in bytes (must be a power of 2) • the associativity of the cache (must be a power of 2) • whether the cache is a write-back or write-through cacheDo not hardcode any of these values —they should be configurable. Use a variable or a #define to represent each of them. But, assume a write-allocate cache: on a write miss, the block containing the memory address in question is first brought into the cache.1.5 Data structures Here’s how I approached this: by considering the fundamental component of a cache to be a set, consisting of one or more cache blocks. Each set then has k blocks, where k is the associativity. So, for example, a two-way associative cache of size 64K with 64-byte blocks will have 1024 blocks and 512 sets. (And a direct-mapped cache has k = 1.)So, you can model your cache as a group of sets (for example, as an array or list of sets). You might instead choose to model the cache as a group of cache blocks, with some efficient way to mark set membership for each block.Each cache block will need a tag and two additional attributes: dirty/clean and valid/invalid. Initially, mark each cache block as invalid. When you load a block from memory into the cache, mark that block as valid and clean.When we write to particular block in the cache, we mark it as dirty. The cache data structure itself can be a global variable. The memory is just an array of bytes. It can be a global variable.In Python, create a class for cache, cache set, and cache block. In C, these can be structs. (Yes, you may use C++ or Java if you’d like.) Use the least-recently-used (LRU) algorithm to control block replacement in a set: if you need to replace one of the blocks in a set, then pick the block that was least recently used. The key data structure you’ll need in order to implement LRU is a tag queue. The tag queue can be an array of integers.Each set will have a tag queue. Initialize the tag queue for each set to invalid values, such as -1. (Zero is a valid tag, so you must not initialize the tag-queue entries to zeros.) Here’s an example of how the queue will work. Suppose we have a four-way associative cache: then the tag queue for each set will have four positions. Now suppose the queue for a particular set is currently [4, 8, 12, 16], and that the most recently accessed tag is always kept in the last position.• then, after an access having tag=4, the queue will be [8, 12, 16, 4] • and after an access having tag=12, the queue will be [8, 16, 4, 12] • and after an access having tag=4, the queue will be [8, 16, 12, 4] • and after an access having tag=6, the queue will be [16, 12, 4, 6] • and after another access having tag=4, the queue will be [16, 12, 6, 4]In this way, the least-recently accessed tag is always in the first position. When you need to replace one of the blocks in this set, you’ll replace the block having the tag that is in the first position. (Another way of thinking about this: the tag queue is a priority queue in which the priority is the access time; and later access time means higher priority.) At a high level, your cache consists of a group of arrays representing the cache blocks. Each of these arrays will have auxiliary information with it (a tag, the dirty/clean bit and the valid/invalid bit, and some way to show which set this array belongs to).A read from memory thus consists of copying a range of values from your memory array to one of the arrays representing a cache block. A write to memory consists of copying a value to one of these arrays. The setting for write-through vs. write-back will determine when and if you also copy data from one of the cache-block arrays back to your memory array.All reads or writes will be for a single word (four bytes). A write-through cache will write a single word to the memory (in addition to writing the word to the cache).1.6 Algorithm Here’s the high-level algorithm for an access to memory location A. This is the full algorithm for both Part One and Part Two. For Part One, you’ll implement only part of this. compute the block offset b, index i, and tag t check each tag in set i if t is found at position j in set i and the valid flag at position j is set // this is a cache hit // depending on whether this is read or write, do one of the following either read the specified word or write the specified word // on a write: for a write-through cache, write the word also to memory // on a write: for a write-back cache, mark the block as dirty set the tag for this block set the valid flag for this block update the tag queue for this set else // cache miss // try to find an unused block in set i if the valid flag for any block is set i is false // use that block update the tag queue set the valid flag for this block to true if this is a read read a cache block from memory into that block else write to that cache block if a write-through cache then write to memory also set the dirty flag for this block set the tag for this block else // must evict a cache block find the least-recently used block, by checking the tag queue for this set update the tag queue set the tag for the target block if this is a write-back cache 3 if the target block is dirty write back the block if this is a read read the correct block from memory into this block else // this is a write-allocate cache, so do the following read the correct block from memory into this block write the value to the block if this is a write-through cache write the value to memory also1.7 Functions Create two functions: one to read a word from memory, and one to write a word to memory. For example: in C, my functions would look like this: Word readWord(unsigned int address); void writeWord(unsigned int address, Word word); Word is a typedef to an int. In Python, I might do this: read_word(address) write_word(address, word) where read word() returns the value read from the specified address and write word() writes the provided word to the specified address.Again, check each address for four-bit alignment and for range 0 ≤ address < memSize, where memSize is the number of bytes in the memory. Almost all of the processing of these two functions is identical, so it makes sense to write a single underlying function that each of these can call.Each of these functions first looks in the cache. If the desired word is found in the cache, then it is returned (for a read) or modified (for a write). Otherwise, the cache block containing the desired word is brought into memory.1.8 Output In order to observe the behavior of the simulated cache, print output describing what happens in response to a read or write. For example, with a 64 K memory (16-bit addresses), a 1K cache, 64-byte blocks, and associativity = 1 (a direct-mapped cache), then in response to a read from address 56132, your functions should print out a string in this form (details will depend on whether this is a hit or miss, and whether an eviction is necessary): read miss + replace [addr=56132 index=13 tag=54: word=56132 (56128 – 56191)]If there is a read or write miss with a replacement necessary, then print out which tag, in which block index was evicted (the block index is the index of a block in its set): [evict tag 4, in blockIndex 0] And after each read or write, print the tag queue for the set that was accessed, in this format: [ 12 20 32 54 ] Check: 56132 = 110110 1101 000100, so the block offset is 000100 = 4; four bits are needed for the index (1024 / 64 = 16), giving the index 1101; and the tag is 110110 = 54. 4 Here’s another example of the information you should print: read miss + replace [addr=17536 index=2 tag=68: word=17536 (17536 – 17599)] [evict tag 32, in blockIndex 1] [write back (8320 – 8383)] [ 36 44 64 68 ]Print the eviction information only for a read or write miss + replace, and print the write-back info only for a write-back cache (and only if the evicted cache block is dirty). Here’s an example of the information to print for a write: write miss + replace [addr=8320 index=2 tag=32: word=7 (8320 – 8383)] [evict tag 28, in blockIndex 1] [write back (7296 – 7359)] [ 16 12 20 32 ] And again, print the eviction information only for a miss + replace, and print the write-back info only for a write-back cache (and only if the evicted cache block is dirty).1.9 Other notes Initialize memory so that memory[i] = i for each four-byte aligned value i with 0 ≤ i < memSize, where i is a four-byte integer. So in this way, memory[i] holds the lowest-order byte of i, memory[i+1] holds the second-lowest-order byte of i, memory[i+2] holds the third-lowest-order byte of i, and memory[i+3] holds the highest-order byte of i. This way, if I read the four-byte value at memory address a, the value will be a. This represents little-endian storage: the least-significant byte of a multi-byte value is stored first; and then the next byte; etc.; and the most-significant byte is stored last. See slides 18-20 in Lecture 3-A. The least-significant byte of the 32-bit integer v is given by v // 256, using integer division. The next least-significant byte is v // (256*256), etc. Initialize the tag queue for each block to have -1 in each position (not zero, since zero is a valid tag). Initialize the tag for each block to -1, for the same reason. Set the valid flag for each block in the cache to false initially.2 Part One Implement a direct-mapped cache that supports only read hits. To test this, “prefill” the memory with specially chosen values in specially chosen locations, as described above. For example, suppose I have a direct-mapped cache with this structure: • 64 K memory, with 16-bit address • 1024-byte cache • 64-byte cache blocks This means the cache contains 1024/64 = 16 cache blocks. Six bits are required for the block offset, and four bits for the index. This leaves 16 − 4 − 6 = 6 bits for the tag.Consider the address 46916 = 101101 1101 000100. The block offset is 4, the index is 13, and the tag is 45. So if I store a value at the four bytes starting at cache.sets[13].blocks[0].data[4], then when I read from address 46916, I should get the value 46916, because of the way that I prefilled. (In my program, each set has one or more blocks; in a direct-mapped cache, each set has a single block.) Another example: the address 13388 corresponds to 001101 0001 001100, so the block offset is 12, the index is 1, and the tag is 13. Print the block offset, index, and tag for each address, and make sure that you are calculating these correctly. 5 2.1 Testing For the part-one code (direct-mapped cache, only reads), use the sequence of reads in part-one-addresses.txt. The output for this sequence of reads appears in testD.out. 3 Part Two Handle read and write misses, associative caches, the tag queue, and write-through/write-back behavior. 4 Testing In the class gitlab site, you’ll find three files: testA-wb.out, testB-wb.out, testC-wb.out; and testA-wt.out, testB-wt.out, testC-wt.out (wb is write-back; wt is write-through). They show my output for a sequence of reads and writes with various cache configurations and various read and write sequences. Verify that you are getting the same results. All of these correspond to the sequences of reads/writes that appear in part-two-addresses.txt.5 What to Submit Submit your source code. 6 Graduate Students Students taking the course for graduate credit, and undergraduates who want a bit of extra credit: add a command-line option that will represent the name of an ASCII file. This file will have lines this form: • a line having a single hexademical value, representing an instruction address • or a line having a hexadecimal value, followed by a space and either R or W, and a second hexadecimal value, representing a data address. “R” represents a read from the data address, and “W” represents a write to that data address Here are a few example lines: 0x7f0dff69386a 0x7f0dff69386c 0x7f0dff69386f R 0x7f0dff8b3e00 0x7f0dff693876 W 0x7f0dff8b3bd8 0x7f0dff69387d 0x7f0dff693884 0x7f0dff693887 R 0x7f0dff8b3f90 If a filename is provided, then process each line of the file using your cache simulator. Keep track of reads, read misses, read hits, writes, write misses, and write hits. At the end, print info and statistics, like this: —————————————– cache size = 2048 cache block size = 64 cache #blocks = 32 cache #sets = 8 cache associativity = 4 cache tag length = 27 write back —————————————– 6 # reads = 17600 # read misses = 2662 (15.12%) # read hits = 14938 (84.88%) # writes = 8800 # write misses = 142 (1.61%) # write hits = 8658 (98.39%) I’ve created trace files from different programs and put them in gitlab: curl.atrace.out, cholesky.atrace.out, rand-accesses.atrace.out. Try your simulator on each. Vary the characteristics of the cache. Then, implement separate instruction and data caches that are each half as large as the single unified cache you implemented before. Run your programs again and see which configuration (unified cache vs. split cache) performs better, in terms of the percentage of read hits and write hits. 7
In this assignment, you will complete a cloud-based chat app that you started on the previous assignment, where clients exchange chat messages through a Web service. You are given a simple chat server that apps will communicate with via HTTP. You will use the retrofit2 library to implement your Web service client, following the software architecture described in class. You will use the same code base as in the previous assignment, but you should enable synchronization with the chat server by setting this flag in Settings to true: public static final boolean SYNC = true; The main user interface for your app presents a screen with a text box for entering a message to be sent, and a “send” button. The rest of the screen is a list view that for now will just show the messages posted by this app, as well as the name under which you are registered at the server. The user chat name can only be set when registering with the server. The interface to the cloud service, for the frontend activities, should be a service helper class. This is a POJO (plain old Java object) that is created by an activity upon its own creation and encapsulates the logic for performing Web service calls. There are several operations that this helper class supports: • Register with the cloud chat service. • Post a message: Add a chat message to a request queue, to be uploaded to the server. Unlike the previous assignment, this upload will not be done immediately. Instead the message will be added to the local chat message database, and this database periodically synchronized with the server in the background. This synchronization should also refresh the list of peers registered with the chat service. • Start and stop message synchronization: For this assignment, these operations will enable and disable background synchronization of the chat database with the server. They are invoked by the lifecycle methods in the main activity. All of these operations are asynchronous, since you cannot block on the main thread. When a message is generated, it is added to the database with its message sequence number set to zero. The sequence number is finally set to a non-zero value when the message is eventually uploaded to the chat server; see the protocol below. The flag is always non-zero for messages downloaded from the chat server. Note that you cannot use this message sequence number as a primary key in your database, because its value is set by the chat server, but you will have to add local messages to the database immediately, without communicating with the server. The database also stores a list of the other clients registered with the chat service. This list, the list of chatrooms and the list of chat messages, are periodically refreshed by synchronizing with the chat service. For simplicity, you can assume that a complete list of chat clients is downloaded on each request. However, you should be more intelligent with downloading of new chat messages. Assuming that the chat service assigns a unique sequence number to each chat message it receives, the app can retrieve the sequence number of the most recent chat message that it has received from the database and provide this to the chat server. The chat server will respond with all chat messages that it has received since that last chat message seen by the client. This synchronization should be done at the same time that the client is uploading messages to the server. So, the protocol for synchronizing with the chat server, once the client is registered, is as follows: 1. The client uploads all messages stored in its database that have not yet been uploaded to the server. It also provides the sequence number of the last message it has received (along with its own UUID and sender id to identify itself) 2. The server adds these messages to its own database, assigning each message a unique sequence number. 3. The server responds with a list of all of the registered clients, and a list of all the chatrooms, and a list of the messages that it has received since it last synchronized with the client. The client updates the messages it has just uploaded with their sequence numbers and inserts the new messages (from other clients) received from the chat server. It also updates the list of chat clients and chatrooms with the lists received from the server, inserting new records and updating existing client records with client metadata1 . Since we have been using sender chat names as foreign key 1 So all peers, chatrooms and messages downloaded from the server are “upserted” into the local database. references for senders of messages, you will be able to maintain the correct relationships between clients and messages in your database. As before, the service helper class should use the WorkManager Lite API to submit request messages to the chat server. This ensures that communication with the chat server is done on a background thread. Single-threaded execution of requests will be sufficient, and greatly simplify things. Request Processing There are three forms of request messages: RegisterRequest, PostMessageRequest and SynchronizeRequest. Two of these messages are spawned by the UI using the service helper, as before. The third is periodically spawned by a background service. Define three concrete subclasses of an abstract base class, Request, for each of these cases. The basic interface for the Request class is as before: public abstract class ChatServiceRequest implements Parcelable { public UUID appID; // installation id public Date timestamp; public double latitude; public double longitude; // Application-defined HTTP request headers. public abstract Map getRequestHeaders();; // Define your own Response class, including HTTP response code. public ChatServiceResponse getResponse(retrofit2.Response response); } The time and location information is used to record the last known location of the client at the server. The business logic for processing these requests is defined in a class called RequestProcessor. This is again a POJO class, which then invokes the business logic as represented by three methods, one for each form of request: public class RequestProcessor { public Response perform(RegisterRequest request) { … } public Response perform(PostMessageRequest request) { … } public Response perform(SynchronizeRequest request) { … } } The request processor in turn will use an implementation class, RestMethod, that encapsulates the logic for performing Web service requests. This classes uses retrofit2 to wrap a type-safe API around an okHttp client stub, using the Gson library to marshall and unmarshall between POJO obects (actually entity objects) and JSON. The public API for this class has the form2 : public class RestMethod { … // See lectures. public Response perform(RegisterRequest request) { … } public StreamingResponse perform(SynchronizeRequest request, StreamingOutput out) { … } } The server expects these HTTP request headers: 1. “X-App-Id”, (a UUID identifying the installation). 2. “X-Timestamp” (a long integer timestamp for the request). 3. “X-Latitude” and “X-Longitude” (two double GPS coordinates). These headers are added by RequestProcessor.process(request), which then uses the visitor pattern to dispatch to the logic for processing the request. Synchronization with the Server The background synchronization of messages with the server is done using the WorkManager Lite API, invoked in ChatHelper.startMessageSync (which is called in ChatActivity.onCreate). Define a periodic request by instantiating this class: public class PeriodicWorkRequest extends WorkRequest { public PeriodicWorkRequest (Class _class, Bundle data, int interval); } The request specifies the class of the worker and the interval between executions of the periodic request (in minutes): PeriodicWorkRequest syncRequest = new PeriodicWorkRequest(SynchronizeWorker.class, …); WorkManager.getInstance(context) .enqueuePeriodicUniqueWork(syncRequest); The SynchronizeWorker object instantiates the request processor and calls it with a SynchronizeRequest message. The worker object is invoked with a period specified as one of the arguments to the PeriodicWorkRequest constructor. The reason that we use 2 We have no use for the case for PostMessageRequest in RestMethod in this assignment, because the message is logged in the database and asynchronously uploaded by the WorkManager Lite service. You can leave the case in the API for PostMessageRequest, for the sake of making this assignment upwardcompatible with the previous assignment, even though RequestProcessor will never execute it. our own home-brewed WorkManager Lite API is that WorkManager requires this period to be no less than fifteen minutes! Syncronization is disabled in ChatHelper.stopMessageSync, which should be invoked in ChatActivity.onStop, where it is important that the original synchronization request object be passed to the work manager operation for cancelling that operation: WorkManager.getInstance(context) .cancelPeriodicUniqueWork(syncRequest); As before, the logic for synchronizing with the server is defined in a worker object (whose class is provided in the PeriodicWorkRequest object enqueued with Work Manager Lite): public class SynchronizeWorker extends Worker { … } The worker just instantiates the request processor and invokes the logic for performing synchronization. For streaming requests, the streaming is done in the request processor, not in the REST implementation (RestMethod). The latter just handles the mechanics of managing the network connection with the server. Therefore, the input to the synchronization request in the REST method has a second argument of this type: public interface StreamingOutput { public void write(OutputStream out); } and the response from the synchronization request has this type: public class StreamingResponse { public InputStream getInputStream(); public ChatServiceResponse getResponse(); public void disconnect(); } Unlike the other RestMethod operations, that perform all necessary I/O on the network connection, and then close this connection before returning to the request processor, the streaming request operation (for synchronization) executes the request with HTTP request headers and URI alone set, and then returns the open connection to the request processor. The latter can send data to the server by writing to the connection output stream (layering a JsonWriter stream over this) and receive data by reading from the connection input stream (layering a JsonReader over this). It is the responsibility of the request processor in this case to close the connection when done! For synchronization, your service should transparently handle the case where communication is not currently possible with the server, either because the device is not currently connected to the network or because communication with the server times out. The client-side information that needs to be persisted is already in the database: Those messages that have a sequence number of zero, indicating that they have not yet been uploaded, and the maximum sequence number for the messages so far downloaded from the server. The latter can be obtained by querying the local database. Running the Server App You are provided with a server app, written using Java JAX-RS (Jersey). You can use it just by executing the jar file. It takes several optional command line arguments: • –host host-name: The name of the host the server is running on (default is the result of executing InetAddress.getLocalHost().getCanonicalHostName()). • –port port-number: The port the server is binding to (default 8080). • –bg true|false: Whether the server is running in the background (it does not read a line of input to terminate, if running in the background; default false). • –log log-file-name: Where to write the server log (default “server.log”). If you want to see the behavior of the server, without relying on your own code, you can use the curl command-line tool to send Web requests to the server. The following command will synchronize messages with the server: curl -X POST -H “Content-Type: application/json”
-d @messages.json –H ‘X-Latitude: …’ … ‘http://host-name:8080/chat//sync?last-seq-num=0’ The query string parameter specifies the sequence number of the last message received by the client (The first message has a sequence number of 1). The file messages.json should contain a list of all chatrooms and a list of messages to be uploaded, in JSON format. For example: { “chatrooms” : [ { “name” : “_default” } ], “messages” : [ { “id”:1,”seqNum”:0,”chatroom”:”_default”,”messageText” : “hello” “timestamp”:…,”latitude”:…,”longitude”:…, “sender”:”joe”,”senderId”:1 }, { “id”:2,”seqNum”:0,”chatroom”:”_default”,,”messageText”:”…” “timestamp”:…,”latitude”:…,”longitude”:…, “sender”:”joe”,”senderId”:1 } ] } This will produce a JSON output of the form: { “peers” : [ {“id”:1,”name”:”joe”,”timestamp”:0,”latitude”:0.0,”longitude”:0.0} ], “chatrooms” : [{“name “:”_default”}], “messages” : [ {“id”:1,”seqNum”:1,”chatroom”:”_default”,”messageText”:”hello”, “timestamp”:…,”latitude”:…,”longitude”:…,”sender”:”joe”}, {“id”:2,”seqNum”:2,”chatroom”:”_default”,”messageText”:”goodbye”, “timestamp”:…,”latitude”:…,”longitude”:…,”sender”:”joe”} ] } The response includes a list of all clients registered with the service, and a list of messages uploaded to the service since the last time this client synchronized (including messages just uploaded by the client itself). The messages database should be updated with the downloaded message, by “upserting” the downloaded messages (updating the sequence numbers for messages that were uploaded from the current device). The peer database should be updated with the client information downloaded from the server, by “upserting” the downloaded client records (updating existing client records with metadata). Using sender names as foreign keys to peer records in the local database will ensure that downloaded messages remain correctly linked to their sender records. For debugging purposes, you can query for the messages that have been uploaded as follows: curl -X GET … ‘http://host-name:8080/chat/messages’ You can also query a remote server logs, in case you have problems3 : curl -X GET … ‘http://host-name:8080/chat/log Submitting Your Assignment Once you have your code working, please follow these instructions for submitting your assignment: 1. Create a zip archive file, named after you, containing a directory with your name. E.g.
if your name is Humphrey Bogart, then name the directory Humphrey_Bogart.
2. In that directory you should provide the Android Studio project for your app.
3. In addition, record mpeg videos of a demonstration of your assignment working. Make sure that your name appears at the beginning of the video. For example, put your name in the title of the app. Do not provide private information such as your email or cwid in the video. 4. For this assignment, you should demonstrate your app working against a running server in EC2 that you will be provided with. Make sure that this is defined as the base URI for the server when you are registering. Use the debugging commands to show the messages on the server, at the beginning and end of your demo videos. 3 If your server is running on your local machine, you can just read the log file directly. Your solution should be uploaded via the Canvas classroom. Your solution should consist of a zip archive with one folder, identified by your name. Within that folder, you should have a single Android Studio project, for the app you have built. You should also provide videos demonstrating the working of your assignment. Your testing should demonstrate at least two devices registered at the server, messages being added, and messages from one device becoming visible at the other device. Do this for both devices.
In this assignment, you will implement a simple cloud-based chat app, where clients exchange chat messages through a Web service. You are given a simple chat server that apps will communicate with via HTTP. You will use the retrofit2 library to implement your Web service client, following the software architecture described in class. The main user interface for your app presents a screen with a text box for entering a message to be sent, and a “send” button. The rest of the screen is a list view that for now will just show the messages posted by this app, as well as the name under which you are registered at the server. The user chat name can only be set when registering with the server. The interface to the cloud service, for the frontend activities, is a service helper class. This is a POJO (plain old Java object) that is created by an activity upon its own creation, and encapsulates the logic for performing Web service calls. For now, this helper class supports two operations: • Register with the cloud chat service. This operation will only succeed if the requested client name has not already been registered by a different client. • Send a message to the cloud chat service. Both of these operations are asynchronous, since you cannot block on the main thread. Registration should generate a unique client identifier (using the Java UUID class) to identify the app installation. Save this with the desired user name, and a sender identifier (a long integer, set to -1 initially) in a shared preferences file when the user performs registration. Sending of chat messages is not enabled until registration succeeds (at which point the client will have a non-negative server-assigned sender identifier). More use will be made of these identifiers in the next assignment. Chat messages are stored in a database for the app, as before. In addition to the message text, store the timestamp of the message (a Java Date value, stored in the database as a long integer), a unique sequence number for that message (a long) set by the chat server (see below) and the identity of the sender (another long, provided by the chat server). In addition a message will contain location information about where the sending device was when the message was sent. When a message is generated, its sequence number is set to a non-zero value and the message added to the local database. When the message is uploaded to the chat server, the response includes the server-generated sequence number and the message is updated with this in the database. For now, the UI will just display a list of the messages sent by the client. In the next assignment, you will synchronize with a chat database stored on the server. Web Services There are two forms of request messages that are sent to the chat server: RegisterRequest and PostMessageRequest. Two concrete subclasses of an abstract base class, ChatServiceRequest, are defined for each of these cases. The basic interface for the ChatServiceRequest class is as follows: public abstract class ChatServiceRequest implements Parcelable { public UUID appID; // installation id public Date timestamp; public double latitude; public double longitude; // Application-defined HTTP request headers. public abstract Map getRequestHeaders();; // Define your own Response class, including HTTP response code. public ChatServiceResponse getResponse(retrofit2.Response response); } public abstract class ChatServiceResponse implements Parcelable { public String responseMessage; // Human readable public int httpResponseCode; public String httpResponseMessage; public abstract Boolean isValid(); } The business logic for processing these requests in the app should be defined in a class called RequestProcessor. This invokes the business logic as represented by two methods, one for each form of request: public class RequestProcessor { public void perform(RegisterRequest request) { … } public void perform(PostMessageRequest request) { … } } The request processor in turn will use an implementation class, RestMethod, that encapsulates the logic for performing Web service requests. This classes uses retrofit2 to wrap a type-safe API around an okHttp client stub, using the Gson library to marshall and unmarshall between POJO obects (actually entity objects) and JSON. The public API for this class has the form: public class RestMethod { … // See lectures. public Response perform(Register request) { … } public Response perform(PostMessage request) { … } } The server expects these HTTP request headers: 1. “X-App-Id” (a UUID identifying the installation). 2. “X-Timestamp” (a long integer timestamp for the request). 3. “X-Latitude” and “X-Longitude” (two double GPS coordinates). You can just define fixed constants for the GPS coordinates. The forms of requests are: 1. For a registration request, you can supply the chat name for the client as a query parameter chat-name, and the remaining parameters as application-specific HTTP request headers (see above). The peer object should not be inserted into the database until the user has successfully registered. 2. For a message posting request, you will want to include the posted message in a JSON entity body. The message will be a JSON object corresponding to the Message entity class defined in earlier assignments, with a new field, seqNum, for the sequence number that will be assigned to the message in the next assignment. In the next assignment, we will see a more realistic way for exchanging messages with the server. Running in the Background Both the registration and message posting must be done asynchronously, on background threads. The registration is done while the user is waiting for confirmation, so we will do that in a foreground service, that uses a notification to inform the user of the progress of the registration. For posting messages, in preparation for the next assignment where we synchronize messages with the chat server, the recommended practice is to use the WorkManager API. However, there is one aspect of this API that is pragmatically difficult: It requires at least fifteen minutes between periodic requests! So we will work with our own homebrewed version, that we will call WorkManager Lite, that removes this restriction. It does not have the power or resilience of the original (e.g., it does not ensure that requests are not lost if the low memory killer stops the process), but it does the work of scheduling jobs on background threads and acquiring partial wake locks. The WorkManager Lite API is similar enough to the original that it should be relatively simple for you to get your app working with WorkManager, if you wish, but it is not required for this assignment. To use the WorkManager Lite API, you define the logic for a worker thread by subclassing this definition (the subclass must define a binary constructor with the same signature as that in this base class): package edu.stevens.cs522.chat.base.work; public abstract class Worker { protected Worker(Context context, Bundle data); public abstract boolean doWork(); } The code base you are provided with includes a worker for posting a single message: public class PostMessageWorker extends Worker { private final Message message; … } Define a one-time work request, e.g., to upload a message to the server, by instantiating the following class, where the bundle argument contains initial data for the execution of the work request (e.g., the message to be uploaded): public class OneTimeWorkRequest extends WorkRequest { public OneTimeWorkRequest(Class _class, Bundle data); } The request is enqueued to be executed on a background thread by the work manager itself: public class WorkManager { public static WorkManager getInstance(Context context); public void enqueueUniqueWork(OneTimeWorkRequest request; } You should complete the logic in the ChatHelper object, to use WorkManager Lite to schedule the uploading of a chat message to the server in the background. Running the Server App You are provided with a server app, written using Java JAX-RS (Jersey). You can use it just by executing the jar file1 . It takes several optional command line arguments: • –host host-name: The name of the host the server is running on (default2 is localhost). • –port port-number: The port the server is binding to (default 8080). • –bg true|false: Whether the server is running in the background (it does not read a line of input to terminate, if running in the background; default false). • –log log-file-name: Where to write the server log (default “server.log”). On the Android emulator, IP address 10.0.2.2 is the synonym for the loopback interface for the host machine on which the emulator is running. This should allow your app on an AVD to connect to the server running on the host machine, but it doesn’t. On the other hand, targeting the actual IP address on your network of the host machine does appear to work. Another wrinkle is that by default Android does not allow cleartext Web traffic. Since we don’t want to deal with keystores and truststores for this assignment, you can enable cleartext traffic3 with this network configuration: This is specified as the configuration in the application manifest: If you want to see the behavior of the server, without relying on your own code, you can use the curl command-line tool to send Web requests to the server. For example: curl –X POST –D headers –H ‘X-App-Id: …’ … ‘http://host-name:8080/chat?chat-name=joe’ This sends a POST request to the specified (registration) URI, and places the response headers in a file called headers. The desired user name is passed as a query parameter chat-name, and the UUID for the new registration is passed as a request header (using the -H option for curl). The contents of the response header file will be of the form: 1 The server will also be running on host in Amazon EC2. Details will be provided through Canvas. 2 Depending on your OS, you may have to explicitly specify the IP address of the machine on which you are running the server. 3 You should obviously never do this in a production system. HTTP/1.1 201 Created Location: http://host-name:8080/chat/1 Content-Length: 0 When a client has been registered, the Location response header will record the URI for that client. The last segment will contain the identifier for the client, that you should use in the URI of all subsequent client requests to post and synchronize messages. For development purposes, the chat server allows a chat name to be re-registered. However, we cannot have two different clients with the same chat name synchronizing at the same time with the server. Therefore, the re-registration of a chat name invalidates the previous registration, and the previous client will no longer be able to interact with the server. Different registrations with the same chat name are distinguished by the application id, that is provided with each Web service request. If you need to re-register with the server, you will have to uninstall and re-install the app, so re-registering with the server is effectively starting as a new client. The following command will post a message to the server: curl -X POST -H “Content-Type: application/json” -d @message.json –H ‘X-Latitude: …’ … -D headers ‘http://host-name:8080/chat//messages’ The file message.json should contain a single message as a JSON object. For example: { “id” : “…”, “seqNum” : “0” “appID” : “123e4567-e89b-12d3-a456-426655440000”, “chatroom” : “_default”, … “sender”: “joe” } The contents of the response header file will be of the form: HTTP/1.1 201 Created Location: http://host-name:8080/chat/messages/17 Content-Length: 0 The last segment of the URI is the global sequence number of the message, and the copy of the message in the local database should be updated with this once the message has been uploaded. You can think of it as the primary key on the server database. The server contains some debug commands that allow you to interrogate it. For example, you can test if a client is registered as follows: curl -X GET –H ‘X-App-Id: 123e4567-e89b-12d3-a456-426655440000’ ‘http://host-name:8080/chat’ You can query for the messages that have been uploaded as follows: curl -X GET ‘http://host-name:8080/chat/messages’ Finally you can query for the log at the server as follows: curl -X GET ‘http://host-name:8080/chat/log’ Submitting Your Assignment Once you have your code working, please follow these instructions for submitting your assignment: 1. Create a zip archive file, named after you, containing a directory with your name. E.g. if your name is Humphrey Bogart, then name the directory Humphrey_Bogart. 2. In that directory you should provide the Android Studio project for your app. In addition, record mpeg videos of demonstrations of your assignment working. You should show the app launching from Android Studio, with completed parts in RequestProcessor visible, and running Make sure that your name appears at the beginning of the video. For example, put your name in the title of the app. Do not provide private information such as your email or cwid in the video. You should demonstrate your app working against a running server, either on your local machine or on a server in EC2 that you are provided with. You supply the base URI for the server as part of registration4 (to facilitate testing on your local machine first of all). Use the debugging commands to show the messages on the server, at the beginning and end of your demo videos. Your solution should be uploaded via the Canvas classroom. Your solution should consist of a zip archive with one folder, identified by your name. Within that folder, you should have a single Android Studio project, for the app you have built. You should also provide a completed rubric, that contains a report on your solution, as well as videos demonstrating the working of your assignment. Use the debug commands to verify registration and get a list of all messages at the server, and to display the long at the end of your testing. 4 The base URI should not include the context root, chat.
In this assignment, you will combine the client and server apps from the previous Chat app assignments into a single Chat app, that will allow bidirectional communication between different Android devices. One of the problems with the previous server app is that it does a blocking message receive on the main UI thread when you press the “Next” button. This means that the whole app freezes up until a client sends a message. This is against best practice for Android programming, and we will fix this in the current assignment. The trick is to define the logic for waiting for incoming messages on a separate background thread. The Android component responsible for managing this thread is called a Service. It is like an Activity, but without a UI. In this assignment, you work with a single application. This has a foreground activity, ChatActivity, that displays messages received and also allows messages to be sent (so the app is now like a two-way radio). A background service, ChatService, handles the sending and receipt of messages in the background. This service should define a background thread, that waits for incoming messages without blocking on the main UI thread. It also defines a background thread for sending messages (use a handler thread for this). Define the service as one that the main chat activity binds to when it starts up. The background service needs to bind to a UDP port for sending and receiving messages. The chat service will provide functionality to the UI for sending messages. It provides a binder for allowing the UI to call into a service operation for sending a message. The interface provided to the UI client is called IChatService, and just provides a single send operation. For this assignment, assume that the UI and services are always in the same process, so you can return the binder as a callback object that provides a reference to the sending service API for the main activity. In addition, when a message is received by the background service, it needs to update the UI with the new message received. In the case where the new message is added to the message database, this is catered for automatically by the observer that the UI registers with the live data when the database is initially queried. Note that since the message will be received in a background thread (managed by the service), you are allowed to use synchronous persist operations to add data to the database. You should also add any messages sent by this device to the message database, so the list of messages will include messages both sent and received. Since every message has a foreign key reference to the sender record in the database, this record will need to be added to the database. Before the app can send any messages, the user must first “register” (available as an action from the task bar context menu). When a user registers, they choose a name, a peer record with this name is added to the database, and both the name and the primary key for this record are saved in settings. The app will not send any messages until the user has registered. There is no longer a “Next” button in this app, for synchronously requesting the next message. However, we still have a floating action button, for sending a message, as with the chat client in the previous assignment: The sending of the message will again be performed on a background thread. For simplicity, we will use a single (bound) service to manage the threads for sending and receiving messages. To test this app, you will now run two or more instances of the same app on different devices. You should demonstrate communication in both directions between at least two devices. Create two or more devices as before and run the Chat app on each of the two devices. Let’s assume that you are doing UDP forwarding1 , so you have this code in your service: chatConnection = factory.getUdpConnection(chatPort); In the code, the Chat app always binds to UDP port 6666 for receiving messages. The DatagramConnection library always sends messages to the local host (identified by address 10.0.2.2 on the Android emulator). The user of the chat app identifies the device they want to send a message to by a UDP port number on the host machine (i.e., your laptop). You must set up forwarding from that port on the host machine to UDP port 6666 on the recipient machine. You can set up this redirection as you have done for earlier assignments. For example: $ telnet localhost 5554 auth auth-token redir add udp:6666:6666 quit $ telnet localhost 5556 auth auth-token redir add udp:6667:6666 quit This forwards messages on (UDP) port 6666 on the host machine to port 6666 on the first device that was started (so the emulator allows telnet connections at TCP port 5554), and forwards messages on port 6667 on the host machine to port 6666 on the second device that was started (so the emulator allows telnet connections at TCP port 5556). Both machines listen on local port 6666. With the definitions above, the first machine should send to port 6667 on the host machine, while the second machine should send to port 6666 on the host machine. The emulator forwards UDP packets sent to ports 6666 and 6667 to port 6666 on the appropriate device (emulator-5554 and emulator-5556, respectively, in this example). As in the previous assignment, your app should provide an activity for listing the peers with whom you have been in communication with, and another activity for listing details of a particular peer. You use the same database as in the previous assignment for this app, now used to save both messages received and messages sent. Submitting Your Assignment Once you have your code working, please follow these instructions for submitting your assignment: 1 The DatagramConnection library also provides you with the options of UDP or SMS connection. UDP is the option that makes the most sense for this kind of application, if it works on the emulator. 1. Create a zip archive file, named after you, containing a directory with your name. E.g. if your name is Humphrey Bogart, then name the directory Humphrey_Bogart. 2. In that directory you should provide the Android Studio project for your Android app. 3. You should also provide an APK file for your compiled project. In addition, record short mpeg videos of a demonstration of your assignment working. Make sure that your name appears at the beginning of the video. For example, put your name in the title of the app. Do not provide private information such as your email or cwid in the video. See the rubric for what the videos should demonstrate. You must also provide a completed rubric for the assignment. Your solution should be uploaded via the Canvas classroom. Your solution should consist of a zip archive with one folder, identified by your name. Within that folder, you should have a single Android Studio project, for the app you have built. You should also provide a completed rubric in the root folder, as well as videos demonstrating the working of your assignment.
In this assignment, you will augment the UI of the chat app from the previous assignments with a multi-pane interface. You will also get some practice with dialogs. Finally, we will incorporate some aspects of Material Design into the user interface. Part 1: Multi-pane Navigation of Chat Rooms Up until now, we have been assuming a single chat room for all chat messages. In this assignment, we will generalize this to allow multiple chat rooms. The chat server from the previous assignments already supports multiple chat rooms, since each chat message includes a chat room as a field in the JSON object, although you only had to support communication through a “default” chat room. In this assignment, we will extend this with the ability for the chat app to navigate between chat rooms using a multi-pane UI. Ideally this would be used for a tablet interface, however it should also work for a large cell phone or small tablet. We will assume a multi-pane layout for the main activity in the chat server app, as long as the device is in landscape orientation. 1. For a device in landscape orientation, show a user interface that has a navigation pane for chat rooms on the left (say 1/3 to ¼ of the screen), listing the chat rooms that are available. Selecting one of these chat rooms from the list should open up, in the main pane, a list of messages posted to that chat room (along with the identity of the poster). Specify the fragments for the navigation pane (list of chatrooms) and for the details pane (list of messages for a chatroom) in the layout for the activity (using the fragment element). The chat room view should initially be empty. 2. Otherwise, just show a list of the chat rooms. Selecting one of these chat rooms should replace the navigation pane with a details pane to display the messages in that chat room. In other words, the behavior of your app in portrait orientation, when viewing chat messages, is the same as it was in the previous assignment, for the “default” classroom. Your app should be able to dynamically switch between these two forms of user interfaces as the orientation of the device changes. Android will perform this switching for you, as long as you enable adaptation to orientation changes in display settings, as shown in Assignment Five. The main change in the data model for your app is that you will need to add an entity type for chat rooms to the database, referenced by the chat room name in message entities: @Entity(indices = {@Index(value = {“name”}, unique = true)}) public class Chatroom implements Parcelable { @PrimaryKey(autoGenerate = true) public long id; public String name; } There is no separate interface for adding chat rooms. For simplicity, new chat room records are added to the server database as messages are added to the database, avoiding duplicates based on the chat room name. The main activity, ChatServerActivity, now has two fragments: 1. ChatroomsFragment for displaying a menu of chat rooms. 2. MessagesFragment for displaying a list of messages for the current chat room. Each has their own view model, managed by the parent activity. In addition, the main activity and the messages fragment share a view model for the currently selected chat room. When the user selects a chat room, the chat rooms fragment calls into the activity to change the current chat room messages. If the device is in landscape mode, this just involves setting the selection in the view model: If the device is in portrait mode, the activity must in addition use a fragment transaction to replace the chat rooms fragment with the messages fragment (leaving the chat rooms fragment on the back stack in case the user returns to it with the “back” key): The floating action button in this activity is used to receive the next message. When pressed, it blocks until a message is received. A toast message will tell the user in which chat room a message was received (It may not be the current chat room). Part 2: Dialogs for dialogues We will also incorporate framents in the chat client, in this case adding a dialog (using a DialogFragment) to post a message. We add a floating action button to an essentially empty user interface, to launch the dialog for sending a message1 . When pressed, it should display a dialog message that prompts the user for the text of the message. The user confirms the message to be sent by pressing a SEND button on the dialog. You should also provide a CANCEL button on the dialog. Note that the user can always cancel a dialog by pressing the BACK button, but also providing a CANCEL button can be good human factors. Follow these guidelines for the dialog class: 1. The class should inherit from DialogFragment. 2. The class should define a static method, called launch, that encapsulates the logic for launching the dialog. This dialog should create the dialog fragment, pass it any arguments from the client, and then use the show() method to launch the dialog. 3. Define an explicit interface that defines any functionality that the dialog fragment requires from the parent activity. The fragment should bind to the activity with this interface in the onAttach callback. 1 This will make more sense in the next assignment, when we combine these apps, with message receipt done in the background, and message sending initiated by pressing the floating action button. 4. In general you can define the dialog user interface either in onCreateView or in onCreateDialog. To get you used to the more flexible and general way of doing things, you should always create your dialog UI in onCreateView. You may still want to define some customization logic in onCreateDialog, e.g., ensuring that there is no title bar for the dialog, but the UI should be defined in onCreateView. 5. In general, the business logic for updating any databases or invoking background services should be defined in the parent activity, invoked from the dialog through the parent interface. In this case, the actual logic for sending a message is performed by the activity, implementing this interface: public interface IMessageSender { public void send(String destinationhost, String chatroom, String chatname, String text); } The dialog just presents the interface for getting the details for the message to be sent. Submitting Your Assignment Once you have your code working, please follow these instructions for submitting your assignment: 1. Create a zip archive file, named after you, containing a directory with your name. E.g. if your name is Humphrey Bogart, then name the directory Humphrey_Bogart. 2. In that directory you should provide the Android Studio projects for your Android apps. 3. Also include the APK files for your projects in the root filder. 4. Include a completed rubric and the videos demonstrating your working assignment. In addition, record short mpeg videos of a demonstration of your assignment working. Your videos should demonstrate starting the server app, showing a list of chatrooms, navigating to the messages in a chatroom, and using the client app (with a dialog) to add chatrooms and add messages to the chatrooms. You should demonstrate the server app working both the single-pane and dual-pane interfaces, using different orientations (portrait vs landscape. Make sure that your name appears at the beginning of the video. For example, put your name in the title of the app. Do not provide private information such as your email or cwid in the video. Your solution should be uploaded via the Canvas classroom. Your solution should consist of a zip archive with one folder, identified by your name. Within that folder, you should have a single Android Studio project, for the app you have built. You should also provide a completed rubric, as well as videos demonstrating your working app.
Develop two aspects of the user experience design for a hypothetical app for which the assignments in this class could be the basis. The assignments you have been working on are implementing a peer-to-peer chat app, although cloud-based chat apps are more common. Don’t simply describe a chat app, we already have lots of those. Integrate some other forms of functionality into the chat functionality. Use your imagination. Remember that the user experience design focuses on the user experience, not on the technology used to achieve that experience. Part 1: Persona Design Give a persona design for the archetypal user of your app. As explained in the lectures, a persona design should include a portrait of this user, including a photograph to personalize them (the photograph should not be of you or some famous personality). You should also provide a description of their goals (at least one goal for each of the cognitive goal categories discussed). Part 2: Context Scenario Give a “day in the life” scenario for the user of your app, revealing contact points where the app is part of their experience. The scenario should include communication with other users via messaging, the organization of this communication into conversations, the exchange of location (GPS) information in this communication, and the use of maps to organize this location information. Again, your scenario should not mention how the app achieves what it is supposed to do, “magical thinking” is okay at this point in the design. You should be clear about what forms of user goals the app is attempting to achieve. Your document should be uploaded as a PDF document, approximately two pages (one for each part of the specification). You should also provide an overall report, as an appendix, that describes (briefly) the process you followed in the design, e.g., any research you did via the Web, where you obtained photographs, etc. You should also provide a completed rubric. Your solution should be a single combined PDF document, uploaded via the Canvas classroom.
In this assignment, you will build on the previous assignment in two ways: 1. You will use ViewModel as a backing store for your activities. 2. You will replace the use of ListView with the more versatile and efficient RecyclerView. You can think of this as taking off the training wheels in your handling of lists of data in the UI. You should follow these guidelines for your implementation. First, you are given the implementation of the ChatViewModel for the ChatServer activity. Complete this activity to only access the database indirectly, through the view model. Also complete the implementations of the view models for the other activities, and incorporate the use of these view models into the activities. Second, in your main activity where you displayed the messages received in a ListView, use a RecyclerView instead. You are given an adapter MessageAdapter that uses the Recycler.Adapter class to connect the list of messages resulting from a query to the recycler view. The MessageAdapter class uses the layout resource R.layout.message as the layout resource for each row in your recycler view. In the adapter class, you are given a ViewHolder nested class that specifies the layout for each row in the list of messages, and you should complete the adapter to specify how the text views in this layout are initialized with data from a message (sender and message text). The activities for viewing peer information also use recycler views (to show the list of peers, or the list of messages from a peer). You should use the generic class TextAdapter, which supports a list of objects that are displayed just by calling their toString() operations. The interesting wrinkle is how to support clicking on a peer in the list of peers, since RecyclerView does not support OnItemClickListener. See the TextAdapter class for an approach that does this, by registering an OnClickListener object on each row of the RecyclerView (and complete the code). Since the point of using ViewModel is to cache the result of a database query, and re-use it if the device orientation changes and the activity is destroyed and recreated, you need to enable dynamic orientation changes in the device. You can do this in the display settings of the device: In Assignment 7, you will see how to provide different user interfaces for portrait and landscape orientation of the device. Submitting Your Assignment Once you have your code working, please follow these instructions for submitting your assignment: 1. Create a zip archive file, named after you, containing a directory with your name. E.g. if your name is Humphrey Bogart, then name the directory Humphrey_Bogart. 2. In that directory you should provide the Android Studio projects for your apps. In addition, record short mpeg videos of your apps working. Make sure that your name appears at the beginning of the videos. For example, put your name in the title of the app. Do not provide private information such as your email or cwid in the video. The videos should demonstrate running the app from Android Studio, where the code including the viewmodel definitions are clearly visible, exiting the app, then rerunning the app and demonstrating that the saved state from the previous run (messages for the chat app) are still present when the app is restarted. Make sure that you send messages from several peers to the chat server. Also, show by logging (using the logcat window) that a reorientation event causes the activity to be destroyed and recreated, but the view model is not destroyed until you leave the activity. You only need to show this for the main activity. Your solution should be uploaded via the Canvas classroom. Your solution should consist of a zip archive with one folder, identified by your name. Within that folder, you should have two Android projects, for the apps you have built. You should also provide videos demonstrating the working of your assignments, the schema generated as a Json file by Room, as well as a completed rubric.
In this assignment, you will redo Assignment Three, where you saved messages and chat peers in a database. In this assignment, you will use the Room ORM to interface with the SQLite database, and you will use LiveData to make your application reactive to updates in the database. This includes querying the database asynchronously, and updating the user interface using the observer pattern when the query is completed. Since content providers use a low-level SQLite API, and the whole point of Room is to lift the level of the API up to the level of entity objects in the domain model, we will use an in-app database without a content provider for this and all future assignments. For now, we will not use a ViewModel to persist the UI state between rotation events. Also, we will for simplicity use a ListView, and a simplified version of the ArrayAdapter, for a list of messages or peers. When we query the database, e.g. for the list of messages, we get back a LiveData object that wraps the query result as a list of message objects. When the query completes in the background, the observer is called to update the UI with a new list of domain objects. However, the array adapter does not provide an operation for updating its backing store, only for adding items to the store. We will therefore work with our own custom array adapter, subclassing the same BaseAdapter base class as ArrayAdapter, that provides this operation. Another issue with ArrayAdapter is that it assumes that there is a single TextView in each row of the ListView where data is to be shown, and calls the toString() operation on the corresponding data object. We will make the UI for the chat object slightly more sophisticated by showing each row in the list of messages as two lines: The sender name on the first line and the message below it. We will define a subclass of our custom array adapter for doing this. You should follow these guidelines for your implementation. First, annotate the Message and Peer entity classes that you defined in the previous assignment, to specify that these are to be stored in a Room-managed database. You should specify that the sender field in a Message object is a foreign-key reference to the Peer record for the sender. Since this foreign key does not reference the primary key of the peer object (We still have a long integer primary key because Android assumes it is there), you are required to define a unique index on the name field of the Peer object. You are also strongly advised, and required for the purposes of this assignment, to declare a (non-unique) index on the sender foreign key in the Message object, otherwise checking integrity constraints will generate linear searches of the entire table of messages. Second, define a subpackage called databases. In this class, define the database adapter class ChatDatabase, as well as the DAO classes MessageDao and PeerDao. These classes are largely complete, you just have to add annotations for Room. The PeerDao class requires you to implement an “upsert” operation in Room: The operation first queries the database for a peer, and updates that record if found, otherwise it inserts a new record. These operations must be made part of the same database transaction to avoid race conditions between the query and the subsequent actioni. You should not change the signatures of the DAO operations. The bulk query operations always return LiveData observable results, but we will allow the insert and update operations to be performed on the main thread for this assignment only. Third, in your main activity you will again display the messages received in a ListView, with an array adapter holding the list of messages. However, the messages will be stored in the database, with a query returning a LiveData list of messages, and with an observer that reacts to an update in the list of messages by updating the adapter on the listview. As in the previous assignment, provide another UI (accessible using the options menu from the action bar) for displaying a list of the peers. This UI just lists peers by name in a list view. You should in this assignment load the list of peers from the database, instantiating the Peer DAO in the activity for viewing chat peers. If the user selects one of these peers, then provide in a third UI information about that peer (their currently known GPS coordinates, and the last time that a message was received from that user). Also display a list of messages just from this peer. You should pass the peer entity to this subactivity, as before. Submitting Your Assignment Once you have your code working, please follow these instructions for submitting your assignment: 1. Create a zip archive file, named after you, containing a directory with your name. E.g. if your name is Humphrey Bogart, then name the directory Humphrey_Bogart. 2. In that directory you should provide the Android Studio projects for your apps (both client and server). In addition, record short mpeg videos of your apps working. Make sure that your name appears at the beginning of the videos. For example, put your name in the title of the app. Do not provide private information such as your email or cwid in the video. The videos should demonstrate running the app from Android Studio, where the code including the database definition with annotations is clearly visible, exiting the app, then rerunning the app and demonstrating that the saved state from the previous run (messages for the chat app) are still present when the app is restarted. Make sure that you send messages from several peers to the chat server. Your solution should be uploaded via the Canvas classroom. Your solution should consist of a zip archive with one folder, identified by your name. Within that folder, you should have two Android projects, for the apps you have built. You should also provide videos demonstrating the working of your assignments, the schema generated as a Json file by Room1 , as well as a completed rubric. 1 You can find the generated schema in the app/schemas subfolder of the Android Studio project.
In this assignment, you will extend the chat server app from the previous assignment. The previous app just saves messages received in an array in the activity UI. If the user navigates away from the activity, and then returns to it, there is a good chance that the messages already received will have been lost, due to the way that Android manages resources in the activity life cycle. For example, in the example of the “treasure hunt” from the previous assignment, if a team leader navigates away from the chat app and the low memory killer kills the app before the team leader navigates back to it, all the messages received so far are lost. We will in this assignment persist both messages received, and information about people that xhave sent us messages, to a persistent database. Another motivation is that we are so far violating one of the most basic tenets of Android programming, that no blocking operations should be performed on the main UI thread. In this assignment, we will continue to do network communication on the main thread, as well as insert records into the database on the main thread. However, we will use cursor loaders and loader managers to perform querying of the database on a background thread. In the next assignment, we will see how to do this using the Room database programming framework, and the lifecycle-aware observer pattern. Your app should target Android API Level 33. You should follow these guidelines for your implementation. First, define a subpackage of your application, called contracts. Define classes in this package called MessageContract and PeerContract, that define content URIs and content paths, as well as content types. They should also define (as final static String constants) the names of the columns in your database. For each operation, define a typespecific read operation that reads the value of the column from a cursor, and a typespecific write operation that adds the value in a column to a ContentValues object. For example: public static final String MESSAGE_TEXT = “message-text”; public static String getMessageText(Cursor cursor) { return cursor.getString(cursor.getColumnIndexOrThrow(MESSAGE_TEXT)); } public static void putMessageText(ContentValues values, String text) { values.put(MESSAGE_TEXT, text); } The base class BaseContract defines some operations common to all contract classes. Second, extend the Message and Peer entity classes that you defined in the previous assignment, with a constructor that initializes the fields from an input cursor, and a method that writes the fields of the entity to a ContentValues object (for insertion into a database): public interface Persistable { public void writeToProvider(ContentValues out); } public class Message implements Parcelable, Persistable { … public Message(Cursor cursor) { this.messageText = MessageContract.getMessageText(cursor); … } … public void writeToProvider(ContentValues values) { MessageContract.putMessageText(values); … } } Third, in your main activity where you display the messages received in a ListView, use the SimpleCursorAdapter class to connect the cursor resulting from a query to the list view. There are two constructors for SimpleCursorAdapter. You should use the form of the constructor that accepts flags for configuring the requerying behavior of the adapter. If you leave this as zero, then by default the adapter will not try to requery the database on the main thread: public SimpleCursorAdapter(Context context, int layout, Cursor c, String[] from, int [] to, int flags); You should use the layout resource R.layout.message as the layout resource for each row in your list view. This defines a layout of two text views, one above the other, for each row. Display the title and authors of each book1 : String[] from = new String[] { MessageContract.SENDER, MessageContract.MESSAGE_TEXT }; int[] to = new int[] { R.id.sender, R.id.message }; Fourth, use cursor loaders and the loader manager to query the provider. The ChatServerActivity activity uses the loader manager to query the content provider for a list of all messages (Use MessageContract.CONTENT_URI to identify the content in the loader). ViewPeersActivity uses the loader manager to query the content provider for 1 In the other activities, where you use android.R.layout.simple_list_item_1 as the row layout in the listview, the single textview field has id android.R.id.text1. a list of all chat peers messages (Use PeerContract.CONTENT_URI to identify the content in the loader). When it launches ViewPeerActivity to view the details for a chat peer, it should pass a peer entity object (as a Parcelable extra) to the subactivity; the latter will then need to use a loader manager to query the content provider for a list of all messages, filtered for that particular sender. Define all callbacks for the loader manager as methods in your activities, not in separate callback objects. Note that your apps should never use the startManagingCursor or managedQuery operations, nor should they provide an initial cursor for the constructor for SimpleCursorAdapter (How would you get it?). However, it is all right in general to use the SimpleCursorAdapter class, using the second constructor that provides a flag that indicates that the query should not be managed by the activity. Just do not use the first, deprecated constructor that causes queries to be managed on the UI thread. Fifth, implement the database in a content provider. Define a single content provider with two tables, visible to the app, and distinguished by their URIs that have the same authority but different content paths. One table stores the messages that have been received, while the second table stores information about the peers from whom we have received messages. Define a subpackage called providers. In this class, define the content provider class ChatProvider. This class defines: 1. Useful string literals such as such the SQL commands to create the database), DATABASE_NAME (the name of the file containing the database), MESSAGE_TABLE (the name of the table containing message information) and PEER_TABLE (the name of the table containing peer information), and DATABASE_VERSION (an integer that is used for versioning your database). 2. A private static inner class called DatabaseHelper that extends SQLiteOpenHelper with your logic for creating the database and upgrading where necessary. The content provider, on startup, instantiates this helper class in order to obtain a reference to the database. 3. The content provider operations for inserting a message or upserting a chat peer, and for querying for all messages and all peers. The other cases for these operations, and the update and delete operations, are unnecessary for this application. When you receive a message, extract the name of the sender and other metadata on the message (the timestamp and GPS coordinates), and update the database record for this peer, or insert a record if this is the first time we have heard from this peer. 4. Note that you will need, in the provider query operation for messages, to register the cursor as a content observer for changes in the content (messages), identified by a URI. When a message is inserted, in the provider insert operation, notify any observers of the content. This ensures that the list of messages in the UI is updated when a new message is received. See the lecture material for more about this. Your solution should consist of two apps, Chat-Client-Oneway and Chat-ServerOneway. The client app is unchanged from the previous assignment. The chat server should follow the guidelines described above above: Use cursor loaders and the loader manager for querying all messages received so far, for querying all peers from whom we have received messages, and for querying messages received from a particular chat peer. It is okay to insert or “upsert” peer and message information into the database, when a message is retrieved, on the main thread. Submitting Your Assignment Once you have your code working, please follow these instructions for submitting your assignment: 1. You should submit two Android Studio projects: chat client and chat server. 2. Create a zip archive file, named after you, containing a directory with your name. E.g. if your name is Humphrey Bogart, then name the directory Humphrey_Bogart. 3. In that directory you should provide the Android Studio projects for your apps. 4. You should also provide APK files for your compiled projects2 . 5. Also include in the directory a completed rubric for your submission. In addition, record short mpeg videos of demonstrations of your assignment working. Make sure that your name appears at the beginning of each video. For example, put your name in the user interface of the app. Do not provide private information such as your email or cwid in the video. The videos should demonstrate running the app, exiting the app, then rerunning the app and demonstrating that the saved state from the previous run (messages for the chat app) are still present when the app is restarted. Make sure that you send messages from several peers to the chat server. Be careful of any “free” apps that you download to do the recording, there are known cases of such apps containing Trojan horses, including key loggers. Your solution should be uploaded via the Canvas classroom. Your solution should 2 You can find the APK file for a project here: app/build/outputs/apk/debug/app-debug.apk directory. consist of a zip archive with one folder, identified by your name. Within that folder, you should have two Android Studio projects, for the apps you have built. You should also provide videos demonstrating the working of your assignment. Make sure that your video shows the server app being launched from the Android Studio project based on content providers and loaders, and that you show the data persisted even after you leave the app and return to it.
In the next several assignments, we are going to be developing a pair of chat apps that communicate in a peer-to-peer fashion. One app is a chat client, that only sends messages, while another app is a chat “server” that collects messages from the clients. For example, this might be used in a “treasure hunt” where hunters are divided into teams, and members of a team communicate with the team leader through the chat app. We will have to learn some more Android before we can develop this into an app that supports bidirectional communication (from a team leader to team members). Develop an app that targets the API version 33 of the Android platform for your submission for this assignment (also set minSdkVersion to 26). Set the targetSdkVersion and the compileSdkVersion to API 33. Test your assignment on emulated devices of your choice. You should also customize the name of the app in the title bar, with your own name. You will complete two apps so that they will speak to each other peer-to-peer using UDP sockets. These apps are very simple and violate some of the design guidelines for Android apps, such as not performing network communication on the main thread. We will see later how to fix this. You are provided with two apps. ChatServer has a single button, Next. When you press it, it waits to receive a UDP datagram packet from the network on a designated port, and appends the message in the packet to a list of messages that are displayed on the screen. ChatClient has a message editor window and a button, Send. When you press SEND, the contents of the message edit window are sent to the server. On real devices, the client and server apps might communicate by broadcasting over a Bluetooth or WIFI network that they are both connected to. Since the emulator does not implement the WIFI1 or Bluetooth stacks, for the sake of this assignment we will just have the server bind to a server port, and the client then sends messages to that port. For machine addressing, the client will send to the loopback interface for the host machine on which both the client and server AVDs execute, and adb will then redirect messages to the server UDP port on the host machine to the corresponding port on the server AVD. Every message that the client sends will include metadata, including the name of the sender. Currently the name is specified in the client UI. Eventually, in a future assignment, you will add an activity that allows this name to be defined as part of a registration process for the app. In addition, provide another UI ViewPeersActivity in the chat server (accessible using the options menu from the action bar) for displaying a list of the peers. This UI just lists peers by name in a list view. The list of peers is maintained in the main chat server activity, and is passed to the subactivity for displaying the list of peers as a parcelable array list extra. If the user selects one of these peers, then provide in a third UI ViewPeerActivity information about that peer (their currently known GPS coordinates, and the last time that a message was received from that user). The GPS coordinates are part of the metadata that is transmitted with every message. For now, they are just declared as constants in the chat client. If we have time later in the course, we will add functionality for tracking the location of a device. The information about the peer that is chosen is passed as a parcelable extra to this third UI. Make sure that the output is properly formatted, and that you follow best practices in localizing the user interface. For example, these string templates are provided for displaying peer information in ViewPeerActivity: User Name: %s Last Seen: %s GPS: %f, %f You can instantiate these templates with information from the messages, e.g.: getString(R.string.view_location, peer.latitude, peer.longitude) 1 The emulator with a system software stack for version 25 or greater does support WIFI, but we will work with point-to-point communication rather than debugging WIFI broadcast. To prepare for future assignments, and to get some practice with parcels and the Parcelable interface, define entity classes that contain the interesting state about messages and chat peers. Define these in an entities subpackage of your app. You have two kinds of entities: a message and a peer (message sender): public class Message implements Parcelable { public long id; public String chatroom; public String messageText; public Date timestamp; public Double latitude; public Double longitude; public String sender; } public class Peer implements Parcelable { public long id; public String name; public Date timestamp; public Double latitude; public Double longitude; } All of these entity objects should implement the Parcelable interface. This involves writing a method that writes the state of the entity object to an output parcel, and a constructor that reconstitutes the state of an entity from an input parcel. Also complete the implementation of the CREATOR static field for the entity class, that implements the Parcel.Creator interface. The library you are provided with includes utilities that you will find helpful, for reading and writing information such as dates. You should follow this strategy to get the client and server to talk to each other: 1. Create separate virtual devices (AVDs) for the client and server. Let’s say you call these ChatClient and ChatServer, respectively. 2. In the Android Studio editor for the ChatClient project, choose the ChatClient device from the drop-down menu for selecting the device to run on (AS should connect the Android debugger to that emulator for the logcat window): 3. Similarly, make sure that the chat server app runs on the ChatServer device. 4. Run the server and client chat apps. Assuming that you ran the client first, followed by the server, the corresponding AVDs have administrative port numbers 5554 and 5556, respectively. The apps are not yet communicating, because they are running on their own network stacks. The apps are using the following library interface to communicate: public interface IDatagramConnection { public void receive(Datagram packet); public void send(Context context, Datagram packet; public void close(); } The client uses the send operation to send a message, while the server uses the receive operation to receive a message, waiting if no message is ready yet. The close operation is used to free up network resources (e.g. unbinding from a network port). A datagram has string data and a string address (source or destination, depending on context). There are three possible implementations of this interface for you to use. Option 1: UDP communication This is the choice that is the most appropriate for this type of application. It is lightweight, since we do not attempt to detect and correct lost packets. The server binds to the default UDP port for the application: int port = getResources().getInteger(R.integer.app_port); DatagramConnectionFactory factory = new DatagramConnectionFactory(); IDatagramConnection serverConnection = factory.getUdpConnection(port); The destination address on the client specifies the UDP port on the server to which messages should be sent, which should always be 6666: The server has bound to a UDP port on the server guest machine. How do we connect these two virtual machines, that are running on their own virtual networks? You need to bind the server UDP port to a UDP port on the host machine upon which you’re running these two AVDs. This is easy to do. The server binds to UDP port 6666 on its guest Ethernet interface (10.0.2.15). The default destination network address for packets in the UDP implementation of DatagramConnection will send packets to the host loopback interface (10.0.2.2 on the AVD, 127.0.0.1 on the host machine). You now need to forward packets sent to that address on the host machine, to the server port on its virtual machine. You will telnet to the console of the server emulator and redirect UDP traffic sent to port 6666 to the same port on the emulator. Use the console port for emulator5556 (the chat server device, if you started it second) in this. telnet localhost 5556 Then authenticate with your emulator authorization token2 , and execute the redir command on the emulator console to forward UDP packets sent to port 6666: auth auth-token redir add udp:6666:6666 You can find out more about network redirection here: https://developer.android.com/studio/run/emulator-networking.html#connectingOption 2: TCP communication TCP is a poor choice for this kind of application, because of the overhead of setting up and tearing down a TCP connection for a small chat message. It is provided because there are known bugs with the UDP stack on the Android emulator. The approach is broadly similar to that above for UDP, except specifying the TCP IDatagramConnection implementation: IDatagramConnection serverConnection = factory.getTcpConnection(port); To set up TCP forwarding, use the adb command in the platform-tools subdirectory of the Android installation3 to perform this redirection, by typing these lines in the OS (bash or Windows) shell: adb devices -l adb -s emulator-id emu avd name adb –t transport-id forward tcp:6666 tcp:6666 The first command lists the devices connected to adb, including their transport identifiers. The second command provides the name of the emulator from its identifier (e.g. emulator-5554, emulator-5556, etc), and is useful as a reality check. The third command 2 The emulator will tell you were to find the authorization token. 3 https://developer.android.com/studio/command-line. forwards packets sent to TCP port 6666 on the host machine to TCP port 6666 on the device identified by the transport identifier. Use the transport id for emulator-5556 (the chat server device, if you started it second) in the third command. The implementation of the TCP stack on the Windows emulator has a bug where a packet is sometimes received with no data. The code for receiving a packet on the server should detect this and return immediately if it happens: serverConnection.receive(receivePacket); if (receivePacket.getData() == null) { Log.d(TAG, “….no data, skipping….”); return; } The client will have to (manually) resend the packet if this happens. The frequency with which this happens is nondeterministic. Option 3: SMS communication SMS is not a strange choice for sending chat messages, there are numerous apps that add additional functionality atop SMS and MMS (e.g., Signal for secure messaging). An SMS implementation is provided here because of the issues with UDP and TCP4 . The constructor for this implementation is slightly different, requiring a context to obtain access to SMS resources: IDatagramConnection serverConnection = factory.getSmsConnection(this); Now when the client specifies a destination for a message, it specifies a “telephone number” to which the SMS message should be sent. On the emulator, you can use the adb port number for the target emulator as the destination. For example, assuming the server is identified as emulator-5556, you would specify 5556 as the destination: 4 However, this being Android, SMS brings issues of its own. Although text messaging has worked for several years on the emulator, it has stopped working with API 31. So, if you are using SMS for communication, you will have to run your apps on an API 30 emulator. Also, do not include the “{“ character in your messages, it appears to scramble the character encoding on the emulator. The library you are provided with requests permissions for SMS and network access. Unlike network permissions, SMS permissions are not granted when the app is installed. Instead, you need to specifically grant SMS permissions to both the client and the server apps: If you use the messaging app on the client or server device, you can see the SMS messages that are exchanged. When you receive a text message on the server, you will also receive a notification. You should turn off text message notifications to prevent this: If the code for receiving a packet on the server executes on the main thread (which it does for this and some subsequent assignments), the operation will not block waiting if a packet has not yet been received. This is because receipt of SMS messages is processed by a broadcast receiver, which must execute on the main thread. If this thread is blocked, the broadcast receiver cannot execute and the system becomes deadlocked. In a later assignment, receipt (and sending) of packets will be done on background threads, as is required for Android. For the moment, the following code on the server for receiving a packet gives up if nothing is currently available: serverConnection.receive(receivePacket); if (receivePacket.getData() == null) { Log.d(TAG, “….no data, skipping….”); return; } The server app is just an observer of SMS messages, that are processed by the main messaging app. You may make the server app the default messaging app, but do not do this on anything except a development device, since it is missing critical functionality for the default messaging app. Note that the Play Store forbids use of SMS permissions unless an app is a default messaging app. Library Module The client and server apps include some functionality in an external module, imported as an AAR file5 . The settings.gradle file should include this line: include ‘:app’, ‘:cs522-library’ The build.gradle file for the app should include these dependencies: implementation project(“:cs522-library”) implementation ‘com.google.guava:guava:28.1-android’ Note: You must make sure to declare in the manifest the permissions that the app will require. The library already declares permissions for network and SMS access. You will need to declare other permissions in later assignments, when chat messages are persisted. Submitting Your Assignment Once you have your apps working, please follow these instructions for submitting your assignment: 1. Create a zip archive file, named after you, containing a directory with your name. E.g. if your name is Humphrey Bogart, then name the directory Humphrey_Bogart. 2. In that directory you should provide the Android Studio projects for your apps. 3. Also include in the directory a completed rubric for your assignment. This is to help you self-evaluate, though a falsified rubric is grounds for (potentially significant) penalty points. 4. You should also include the APK (Android Package) files for your applications, generated by Android Studio, package up your application for installation on a device. These are the files app/build/outputs/apk/debug/app-debug.apk in each project (Rename these appropriately and put them in the root folder of your submission). 5. In addition, record short MP4 videos (note the allowable format) demonstrating your deployments working. Make sure that your name appears at the beginning of the video. For example, put your name in the title of the app. Do not provide private information such as your email or cwid in the video. Be careful of any “free” apps that you download to do the recording, there are known cases of such apps containing Trojan horses, including key loggers. 6. Your video should record client devices sending multiple messages and those messages being received on the server. You can use one client device to send messages with different chat names. Include both client and server devices, running on the emulator, in a video. Show the server list of peers subactivity being launched, and the details for a single peer activity being launched from this. 5 To add this module into an existing project, click File | New | New Module and select Import .JAR/.AAR Package. To replace the module in a project where you have already imported it, replace the AAR file in the cs522-library directory of the project. Your solution should be uploaded via the Canvas classroom. Your solution should consist of a zip archive with one folder, identified by your name. Within that folder, you should have two Android projects, for the apps you have built, as well as the completed rubric and videos demonstrating your app working.
This assignment involves building and deploying a simple Hello World app. This exercise involves: • Building an Android app with a user interface (activity). • Accepting user input in the app. • Displaying the user input The Android developer website provides a wealth of information about Android, including instructions for building and running your first Android app: http://developer.android.com/training/basics/firstappHowever, you should avoid using the Android Studio wizard to create activities, since it introduces several complications. Create an empty project (with no activities initially), with package name edu.stevens.cs522.hello, and then add an empty activity. Configure the target platform for the app to be Android API Level 33 (Tiramisu). In the application manifest, the element will specify the theme that styles the application: … The theme itself should be specified in a file res/values/themes.xml: Do not leave the theme as the Google material design theme that the wizard in Android Studio prefers. We will be using that theme later, when we incorporate elements of material design into the app. You will need to create an element as a child of the element in the manifest, and this will need to specify the right action (to make this the activity launched for the app) and category (to make sure it shows on the app launcher): The activity itself displays a layout that includes a prompt, a text box for user input, and a button for signaling when user input is ready. This should be defined as a layout resource in res/layout/activity_main.xml: The prompt string is defined as a string resource in res/values/strings.xml: What is your name? You should also define a name for the app that includes your own name as a string resource, so that it is displayed at the top of the app screen (see the application element above): XYZ’s First App Create a class for the main activity of this app, whose onCreate method inflates this layout on the device screen: public class MainActivity extends Activity { @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.activity_main); } } However, this app will not react to user input. You will need to add a callback for button presses (Don’t forget to put a text label on the button in the view). You can make the activity itself be this callback object: public class MainActivity extends Activity implements View.OnClickListener { @Override protected void onCreate(Bundle savedInstanceState) { … button = (Button) findViewById(R.id.button); button.setOnClickListener(this); } @Override public void onClick(View v) { … } } On receiving the button press, the callback should get the input text from the text box, and launch another activity using an explicit intent: Intent intent = new Intent(this, ShowActivity.class); intent.putExtra(ShowActivity.MESSAGE_KEY, text); startActivity(intent); The child activity displays this text on its screen: public class ShowActivity extends Activity { public final static String MESSAGE_KEY = “message”; @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.activity_show); String message = getIntent().getStringExtra(MESSAGE_KEY); … } } For the layout for this child activity, make it a linear layout with a single text view, and programmatically set the string to be displayed in the activity. You should run the app on a virtual Android device of your choice (e.g. a Pixel 4), or on your own physical device if you prefer and if it supports the API. You can watch the processing of your application (insert log statements in your code for more information) in the logcat window in Android Studio. Once you have your code working, please follow these instructions for submitting your assignment: 1. Create a zip archive file, named after you, containing a directory with your name. E.g. if your name is Humphrey Bogart, then name the directory Humphrey_Bogart. 2. In that directory you should provide the Android Studio project for your Android app. 3. Also include in the directory a completed rubric where you self-evaluate your submission. 4. In addition, record a short mpeg (MP4) video of a demonstration of your deployment working. Make sure that your name appears in the video. It should appear in the title bar of the app while it is running. Do not provide private information such as your email or cwid in the video. Your solution should be uploaded via the Canvas classroom. Your solution should consist of a zip archive with one folder, identified by your name. Within that folder, you should have one Android project, for the app you have built. You should also provide a completed rubric for your solution, as well as a video showing the app working.
For this assignment, you are to write a recursive ray tracer. For ray tracing, you need to create an image of a scene including several objects and models. You may specify the scene in the code and output the resulting image to a file or to the screen. The type of image file you use is your choice, but the user must be able to specify the desired width and height of the resulting image through the command line or an input file. You are are allowed to use the C++ standard template library, algebra.h, algebra.cpp files from Assignment 2 and the provided files. No other libraries files are to be used. The Interface No graphical user interface is required for this assignment. The user must be able to specify the image resolution (width and height), for example through command line arguments. All other interactions are designed at your discretion. Donated Code You have been provided with the following files: • main.cpp – The main point of entry into the application, including an example of how to populate and save a 2D image. • polyroots.cpp, polyroots.h – Routines for solving quadratic functions. Maybe useful for intersection tests. 1 To compile and run the provided program, execute: qmake -project QT+=widgets qmake make ./a4 The provided code illustrates an example of populating and saving a 2D image to a file, output.png. As a test, it loops through the pixels and sets the RGB tuple for that pixel. You need to modify this code to colour the pixels based on the algorithm for a recursive ray tracer. A suggested to-do list, in an order that will help you is as follows: • Generate scene specifications for the camera and image plane. Compute the rays for each pixel. • Implement sphere intersection. • Generate scene specifications for a virtual sphere object that should be visible by the camera. • Colour the scene using a binary colour scheme (eg. red versus blue) where an intersection with the sphere generates one colour, and no intersection generates another. • Generate scene specifications for a light source. Implement the Phong illumination model. • Generate shadow rays and shadows. • Add support for triangles and quads. • Support reflection via recursive secondary rays. You may wish to create helper methods, helper classes or use data structures such as queues or stacks, depending on your design. C++ standard template library offers stacks, queues and other collection mechanisms which may be used. Describe your design decisions in your README. Bonus (30 Marks) This assignment is a decent amount of work. However, if you have time, and the creative inclination, there are a lot of ways this can be made much more interesting. You are encouraged to experiment with the code and implement these sorts of changes, as long as you have already met the assignment’s basic objects. The maximum additional marks from bonuses is 30. It is at the discretion of the TA to determine coolness factors in awarding bonus points. • Read scene and light specifications from an input file. (up to 5 marks) 2 • Dynamic eye position and viewing direction specification. (up to 5 marks) • Refraction (recursive). (up to 10 marks) • Simple anti-aliasing as discussed in class. (up to 5 marks) • Use a triangle mesh in OBJ format in the scene. (up to 5 marks) • Animated MD2 (a sequence of images generated by ray-tracing). (up to 5 marks) • Add other primitives such as cones, cylinders or other implicit surfaces. (5 marks each, up to 15 marks) • Generate an OpenGL user interface to create and preview the scene for ray tracing. This interface should include controls to position, orient and scale objects within the scene. (10 marks) • Support texture mapping and/or bump mapping (5 marks each) • Support CSG operations (intersect, union, diff, etc). (10 marks) • Efficiency Improvements: – Intensity Threshold: If the accumulated mirror reflectance is less than epsilon, cease recursive on the branch. (up to 5 marks) – Bounding Boxes: (Extends mesh bonus) Compute a bounding box to check for intersections before performing whole OBJ intersections. (up to 5 marks) – Spatial Partitioning: Modify your intersection routine to use a spatial partitioning scheme (eg. BSP trees, uniform spatial subdivision or octrees). (up to 10 marks) • Provide an alternative rendering style (eg. toon shading). (up to 5 marks, based on coolness factor) If you make an amazing modification (an actual feature, not an unintended bug…), document it in your README and it will be considered and graded at the discretion of the TA for a maximum of 10 marks. If you make extensive changes, additionally offer a “compatibility mode” by default. You should support at least the user interface required by the assignment. You can activate your extensions either with a special command line argument or a menu item. Document this in your README file. 3 Non-functional Requirements (20 Marks) Documentation 1. You must provide a README file. A sample one has already been provided. 2. Your README file should contain: (a) Your name and UCID. (b) Short description of algorithms you implemented to complete the program. This includes how you have designed your ray tracer. (c) A brief description of the data-structures used to implement the assignment. This includes what classes you chose to use and their purpose. (d) A brief description of each of image and what portion of the assignment it illustrates. 3. Due to speed issues, you must provide at least three screenshots of your assignment demonstrating its capabilities. Your submitted images must show each of the features you have implemented. You will not receive marks for features that are not demonstrated in the images you submit. Additional screenshots are necessary to demonstrate any implemented bonuses. Screenshots should be named ‘firstname.lastname a3 #.png’ where # is 1 − n for n screenshot images. Source Code 1. All your source code must be written in C/C++ and properly commented. OpenGL and Qt are not to be used for this assignment unless it is for a bonus. Your source code must compile on the lab machines in MS 239 without any special modifications. Your source code must be clear and well commented. 2. You will lose marks for inefficient code and a slow demo sample. 3. You may reuse source code: (a) which has been provided by the instructor for use in the course, (b) which has been written by you which implements basic data structures, such as linked lists or arrays, (c) which you have received permission from the instructor or one of the TAs of CPSC 453 prior to handing-in your assignment, 4. Any instances of code reuse by you for this assignment must be explicitly mentioned within the README file. Failure to do so will result in a zero in the assignment. Please read the University of Calgary regulations regarding plagiarism http://www.ucalgary.ca/ honesty/plagiarism. 4 Functional Requirements (80 Marks Total) 1. Objects in the scene: spheres (15 marks), triangles and quads (15 marks) 2. Phong illumination model, and point light sources (20 marks) 3. Shadows (15 marks) 4. Reflection (recursive) (15 marks) Lost Marks Possible areas for deductions: • Unable to enter image resolution (width, height). • Demo scene takes too long. • You need to give us comparison images for things like antialiasing. • If your eye point is too far, or your fov is too wide, the objects near the edges will appear distorted (stretched). • For scaling to work properly, you need to normalize the ray every time you transform it. • The images shouldn’t be upside down. • The background shouldn’t obscure the view especially if using a unique background. • If images look washed out and shadow areas are gray, it is probably because you are adding the ambient light to your colour instead of ambient*material.ka. • Missing screenshots, README. Demo You are required to give an approximately 5 minute live demo to your TA. For this demo, you’ll need to construct a simple example which will compile and raytrace your scene within 30 seconds. Failure to show up at the presentation will result in a zero in the assignment. You will need to schedule your demo with your TA – they will have details about how your tutorial section demos will run. 5
For this assignment, you are to write a model loader program for OBJ files. The application is able to select an OBJ file, read it in, and render the mesh in a number of ways on the screen. As with prior assignments, a number of affine transformations may be performed on the model. It also provides the user with options for changing the view and drawing. To facilitate this, the program has a number of user input tools through the mouse, keyboard, and menu. The assignment will be written in C++ using the Qt GUI toolkit. In this assignment you will be working with OpenGL commands for drawing, using matrices for transformations and supporting basic GUI for interaction. A number of example models have been provided. The user may choose which model to load and render it on the screen. Even though models come in different sizes it should still be centered and fit within the viewable window on loading. This may require determining the model’s dimensions, and calculate the default transformation required to reposition the model or the view. Standard model and view transformations will be available. These are mostly the same from prior assignments, however the view will be transformed based on the “lookat” setup, and the model will rotate based on trackball rotation. To visualize the view transformations, a patterned square will be drawn and fixed in the scene, similar to our gnomon from Assignment 2. Many of the provided models are characters adapted from the MD2 files of the old Quake engine. These characters have both a main mesh as well as a weapon or prop mesh. To support these characters, the application must be capable of loading in additional OBJ files. Since the props are in the same coordinate system as the main mesh, they will need to have the same transformations 1 applied as the main mesh. This forms a small example of a hierarchical model with the main mesh the parent of the prop mesh. We will refer to these props as submodels, and they inherit the transformations of their parent model. Three main drawing modes will be supported: wireframe, face and textured. The first two we saw in Assignment 1. To support texturing, the application must be able to select a texture (2D image) and apply the texture coordinates to the model. These texture coordinates are found within the OBJ model, with one texture coordinate (u, v) for each vertex. To ensure nice rendering of the scene, normals need to be computed for the model. The two modes are face normal – where each vertex on the same face receive the same normal, generating a flat shading style; and vertex normal – where each vertex has its own normal, computed as an average of the adjacent face normals, generating Phong shading style. Normals may be optionally displayed on the mesh. An easy approach is to generate a small line with one point located at the vertex or center of the face, and the other point some small length away in the direction of the normal. Toggling between face and vertex mode should visualize different normals. Lastly, one should be able to select a currently active model. This selected model (and any of its associated submodels) is affected by the model transformations. Additionally, when loading a texture, it is applied to the selected model. For full marks, 3D picking must be used for selection. For partial marks, an additional menu should be created allowing the application to select between loaded models. You are are allowed to use the existing Qt matrices, the matrices you created in Assignment 2 or helper matrices in the glm library. You may also wish to use the QFileDialog and QImage class for file and image loading. A perpsective projection has been implemented and should be used for the assignment. The Interface The user interface will be written in Qt. You will need to implement the following functionality. The letters in ”()” indicate the keyboard short cut; remember – both upper and lower case should work for the keyboard shortcut. • A File menu with the following menu items: – Open Model (CTRL+O): Load a new model. This becomes the selected model – Open Submodel (CTRL+B): Load a new model (eg. a weapon), setting the selected model as its parent. This new becomes the selected model. – Load Texture (CTRL+T): Load a texture for the selected model – Reset Models (R): Reset models to their default positions 2 – Reset View (R): Reset camera view – Reset All (A): Reset models and camera – Clear (C): Clears all models – Quit (Q): Exit the program. (This one is already implemented – do not break it!) • A Draw menu, with the following menu items: – Wireframe (W): Draw the scene in wireframe mode. – Face (F): Draw the scene in face mode. – Textured (T): Draw the scene in textured mode. – A nested Normals menu, with the following menu items: ∗ Face (CTRL+F): Draw the scene using face normals ∗ Vertex (CTRL+V): Draw the scene using vertex normals ∗ Show Normals (N): Toggle between drawing normals indicators Face and Vertex should use radio buttons to indicate which state is selected. – Select Model (S): Turns on picking mode to select a currently active model. Picking mode is deactivated when a user selects a model, or presses the escape key (ESC) (and clears the selection). Wireframe, Face and Textured should use radio buttons to indicate which state is selected. • Mouse Movements: – Operations are initiated by pressing the appropriate mouse button and terminated by releasing that button. The SHIFT and CTRL modifiers cause the view movements to be used instead. – LMB: Translate the selected model, or if none, all models, along the X and Y axis. – MMB: Translate the selected model, or if none, all models, along the Z axis. Only use the horizontal change in mouse position. – RMB: Rotate the selected model, or if none, all models, using trackball rotation. – LMB with SHIFT: Translate the position of the camera along the X and Y axis. – MMB with SHIFT: Translate the position of the camera along the Z axis. Only use the horizontal change in mouse position. – RMB with SHIFT: Rotate the up direction of the camera. Only use the horizontal change in mouse position. – LMB with CTRL: Translate the camera’s look at location along the X and Y axis. 3 – MMB with CTRL: Translate the camera’s look at location along the Z axis. Only use the horizontal change in mouse position. – The maximum and minimum scales should be restricted to a reasonable range. You will need to make reasonable decisions about how much to scale or rotate for every pixel’s worth of mouse motion. For example, if the mouse isn’t moving, there should be no scaling or rotation. An on-screen display, such as a status bar, should indicate: which drawing mode (Wireframe, Face or Textured), which normal style (Face or Vertex) and which model is selected. As with previous assignments, this is implemented in C++ with Qt. We have provided some code for you that sets up a window and draws an example triangle. You will need to add the required functionality. As with Assignment 1, when building your data buffers to send to the provided shaders (ie. vertices, per-vertex colours, per-vertex normals and per-vertex texture coordinates), use Vertex Buffer Objects and Vertex Array Objects. This is a more efficient display style. Donated Code You have been provided with the following files: • main.cpp – The main point of entry into the application. • window.cpp, window.h – The application window, to which you may add widgets. • renderer.cpp, renderer.h – A widget that will display your rendering. This is where the core part of your code will go. • objModel.cpp, objModel.h – Routines for loading OBJ files. You may wish to add code here. • per-fragment-phong.vs.glsl, per-fragment-phong.fs.glsl – Simple phong shader code. • textured-phong.vs.glsl, textured-phong.fs.glsl – Phong shader code that supports textures. • models.zip – A collection of OBJ models. • demos.zip – A simple example of transformations, including code for trackball rotations which you will likely want to adapt for this assignment. 4 To compile and run the provided program, execute: qmake -project QT+=widgets qmake make ./a3 The provided code creates a simple starter UI. As a test, it draws a triangle in the center of the window. You need to modify this code to load in your models and textures, draw using the rendering styles and perform the requested transformations. A suggested to-do list, in an order that will help you is as follows: • Draw a simple patterned square in the scene (eg. checkerboard). • Load an OBJ file. You may wish to draw them in wireframe mode before face mode. • Reposition the model based on its dimensions so it fits in the center of the window. • Incorporate the model and view transformations, including virtual trackball and the camera’s look-at mechanism. • Calculate the face normals, and then the vertex normals, passing them off to the shader. Then optionally draw the normals on the model. • Add support for one submodel using the provided weapons. Be able to transform it separately from the main model. • Add support for textures. • Add support for 3D picking. • Add support for multiple models and submodels. You may wish to create helper methods, helper classes or use data structures such as queues or stacks, depending on your design. C++ standard template library offers stacks, queues and other collection mechanisms which may be used. Describe your design decisions in your README. Bonus (20 Marks) The core of this assignment is a decent amount of work. However, if you have time, and the creative inclination, there are a lot of ways this can be made much more interesting. You are encouraged to experiment with the code and implement these sorts of changes, as long as you have already met the assignment’s basic objects. The maximum additional marks from bonuses is 20. It is at the discretion of the TA to determine coolness factors in awarding bonus points. 5 • Support animation. (up to 5 marks) – A separate folder of OBJs has been provided indicating an animated sequence. Within these sequences are mini-animations (2-10 frames each). Automatically loop through all types of animation (see animation list below) and adjust display speed to match the specified fps (10 marks), // animation list typedef enum { STAND, RUN, ATTACK, PAIN_A, PAIN_B, PAIN_C, JUMP, FLIP, SALUTE, FALLBACK, WAVE, POINT, CROUCH_STAND, CROUCH_WALK, CROUCH_ATTACK, CROUCH_PAIN, CROUCH_DEATH, DEATH_FALLBACK, DEATH_FALLFORWARD, DEATH_FALLBACKSLOW, BOOM, MAX_ANIMATIONS } animType_t; • Support animation GUI. (up to 3 marks) • Perform one of our subdivision techniques on the mesh. (up to 10 marks) • Highlight the selected model. (up to 3 marks) • Support scene generation: loading multiple models, saving and loading transformation descriptions, etc. (up to 8 marks) • Support undo/redo for transformations. (up to 5 marks) • Provide an alternative rendering style. (up to 5 marks, based on coolness factor) 6 If you make an amazing modification (an actual feature, not an unintended bug…), document it in your README and it will be considered and graded at the discretion of the TA for a maximum of 10 marks. If you make extensive changes, additionally offer a “compatibility mode” by default. You should support at least the user interface required by the assignment. You can activate your extensions either with a special command line argument or a menu item. Document this in your README file. Non-functional Requirements (20 Marks) Documentation 1. You must provide a README file. A sample one has already been provided. 2. Your README file should contain: (a) Your name and UCID. (b) Short description of algorithms you implemented to complete the program. This includes how you set up the submodel transformations and calculate the normals. (c) A brief description of the data-structures you used to implement the assignment. This includes what matrices you chose to store in the renderer.cpp and their purpose. 3. You must provide at least one screenshot of your assignment demonstrating its capabilities. Additional screenshots are necessary to demonstrate any implemented bonuses. Screenshots should be named ‘firstname.lastname a3 #.png’ where # is 1 − n for n screenshot images. Source Code 1. All your source code must be written in C/C++ and properly commented. All graphics rendering must be done using OpenGL. All event handling and windowing must be performed via Qt. Your source code must compile on the lab machines in MS 239 without any special modifications. Your source code must be clear and well commented. 2. You will lose marks for inefficient and slow implementations. 3. You may reuse source code: (a) which has been provided by the instructor for use in the course, (b) which has been written by you which implements basic data structures, such as linked lists or arrays, (c) which you have received permission from the instructor or one of the TAs of CPSC 453 prior to handing-in your assignment, 7 4. Any instances of code reuse by you for this assignment must be explicitly mentioned within the README file. Failure to do so will result in a zero in the assignment. Please read the University of Calgary regulations regarding plagiarism http://www.ucalgary.ca/ honesty/plagiarism. Functional Requirements (80 Marks Total) Modelling & Rendering (40 Marks) 1. Simple patterned square is drawn. It is affected by view, but not model transformations. (3) 2. UI for loading models. (2) 3. Draw model and be able to toggle between wireframe (2), face (2) and textured (10). This includes 2D texture loading for the selected model. 4. Compute and optionally display indicators for face normals (5) and vertex normals (7). 5. Render using face normals – flat shading (2) and vertex normals – smooth shading (2). 6. Support weapon submodel loading. (5) Transforming (25 Marks) 1. On model loading, model fits within window and is centered. (5) 2. Model transformations: translation (3) and trackball rotation (5). 3. Submodel transformations: hierarchical – moves independently or with parent model. (3) 4. View transformations: translate camera position (3), translate camera lookat location (3), rotate through camera’s up-direction (3) UI Interaction (15 Marks) The user should be able to: 1. Access pull down menus for controls as specified. (3) 2. Display on-screen feedback for current mode and selected object as specified. (2) 3. Able to select models (5) – full marks for 3D picking; maximum 2 for menu listing. 4. Mouse controls for model and view as specified. (5) 8 Lost Marks Possible areas for losing marks: • Model is non-uniformly stretched on loading. • Model is cropped on loading. Model is clipped or cropped on initial rotation. • On load, model does not rotate about its center, nor the center of the window. • Specific model values are hardcoded into the program. • Application redraw slows down over time. • Draw updating is not live with mouse movements. • Transformations are buggy, jerky, uneven, too fast or too slow. • No screenshot. No README. Demo You are required to give an approximately 5 minute live demo to your TA. Failure to show up at the presentation will result in a zero in the assignment. You will need to schedule your demo with your TA – they will have details about how your tutorial section demos will run. 9
