Coursework 1 – Regular Languages & Finite State Automata The objective of this assignment is to reinforce what you have learned in the lectures and tute/ lab sessions. Specifically, it covers the advanced concepts in the relational database design, using SQL for querying a relational database and analyse different database models for different applications. This assessment will measure your ability to: Apply good database design guidelines, such as normalisation, to build a well-designed database schema Analyse different database models for different applications Part A: Relational Database Design (30 Marks) Branch(BranchNo, B_Street, B_Suburb, B_Postcode, Staff_No*, Start_Date, Monthly_Bonus, Telephone1, Telephone2, Telephone3, S_Name*) Staff(StaffNo, S_Name, S_Address, Position, Salary,Branch_No*, Supervisor_No) Property(PropNo, P_Street, P_Suburb, P_Postcode, Type, NoOfRooms, WeeklyRent, AvailableForRent, AdOnOtherWebsites, Staff_No*, S_Name*) 2. Write down the highest normal form. each of these relations are in. For each of these relations, state the reasons why it doesn’t meet the next normal form. requirements. This is not required if the relation is in 3NF. 4. Where possible, combine the relations resulting from Part 3. Write down the full database schema at the end of this step, eliminating combined relations and replacing them with newly created relations.
Java ATOM Assignment 2 1 Introduction This project represents a substantive programming exercise. Like all work for this class, it is to be completed individually: any form. of collaboration is prohibited, as detailed in the syllabus. This project is considered a take home exam. Before even reading this assignment, please read the E20 manual thoroughly. Read the provided E20 assembly language examples. 2 Assignment: Assembler Yourtask is to write an E20 assembler: a program that will convert E20 assembly language into E20 machine language. Each E20 assembly language instruction can be expressed as a 16-bit E20 machine language instruction. The rules for converting between the two forms is given in the E20 manual, particularly the chapter on the E20 instruction set. For example, consider the assembly language instruction addi $1, $2, 3. The opcode is addi, used for performing addition of an immediate. In this case, we are adding the number 3 to the value currently stored in register $2, and storing the result into register $1. The corresponding machine code instruction is 0010100010000011 in binary, or 59523 in decimal, or e883 in hex. Each component of the assembly language instruction maps onto a region of its machine language counterpart. Below, we color-code each field to show how they match: addi $1, $2, 3 0010100010000011 As you can see, the first (most significant) three bits of the machine code instruction correspond to the opcode;the next three bits indicate the source register; the next three bits indicate the destination register; and the last seven bits store the immediate. Unlike the E15, in the E20, different instructions have different formats, and your program will need to take that into account. The purpose of your assembler is to make it easier to write programs for the E20 processor. Eventually, we will execute the machine code generated by your assembler on a simulated E20processor. 2.1 Input The input to your assembler will be the name of an E20 assembly language file, given on the command line. By convention, E20 assembly language files have an .ssuffix. Your program will read in the contents of the file. You may assume that the file contains well-formed E20 assembly language code. The file may contain comments, which your program should ignore. You are provided with several examples of valid E20 assembly language files, which you can use to test your assembler. Here is an example of an E20 assembly language program, in a file named loop2.s: movi $1 , 10 beginning: jeq $1 , $0, done addi $1 , $1 , -1 j beginning done: halt 2.2 Output Your program should print to stdout the E20 machine code corresponding to its input. Below is an example invocation of an assembler from Linux’s bash. In this case, we are assembling the assembly language program given above. Text in italics represents a command typed by the user. user@ubuntu: / e20$./asm.py loop2.s ram[0] = 16’b0010000010001010; // movi $1 ,10 ram[1] = 16’b1100010000000010; // beginning: jeq $1,$0,done ram[2] = 16’b0010010011111111; // addi $1,$1,-1 ram[3] = 16’b0100000000000001; // j beginning ram[4] = 16’b0100000000000100; // done: halt Your assembler should produce output in exactly the format shown above. That is: for each assembly language instruction, print a line of machine code, consisting of the memory address, followed by an equals sign, followed by a 16-bit binary number in Verilog syntax. Your program is responsible for determining the memory address of each instruction. The instructions should be printed in sequential order of their address. You are not responsible for printing the value of memory addresses that are not specified by theinput. In the above listing, each line of machine code includes a comment indicating the corresponding assembly language code. Your solution does not need to output the comments. However, outputting comments in this way may be helpful as you debug your program. Your solution will be checked mechanically, so it is important that your assembler produce machine code output identical to the machine code output above. Please avoid losing points for superficial deviations. 2.3 Testing Several example assembly code files have been provided for you. Each example file includes, in comments, the expected machine code, as well as the expected execution result. You can use these examples to verify the correctness of your assembler. However, you should not rely exclusively on these examples, as they are not sufficient to exercise every aspect of an assembler. You are therefore expected to develop your own test cases. 2.4 Starter code You may, but are not required to, use the provided starter code for this assignment, found in the files asm-starter.cpp and asm-starter.py. Please rename them to asm.cppor asm.py, as appropriate.
ADS103 Assessment 3: Programming Assignment 2 Requirements Implement a solution to the Traffic problem in a C program called traffic.c; start from the provided file. Use mutexes for mutual exclusion and condition variables for thread signalling. Create N threads and assign each a randomly chosen direction. Threads should loop attempting to enter the street a large, fixed number of times. When a thread is in the street, it should call uthread_yield() a total of N times and then exit the street. It should then call uthread_yield() at least another N times before attempting to enter the street again. The program terminates when every thread has entered the street the specified number of times. Experiment with different values of N, starting with small numbers while debugging and ending with a number that is at least twenty. Testing Test your program with N=20 and each thread performing a least 100 iterations to ensure that the two street-occupancy constraints are never violated using assert statements. Count the number of times that each of the following occupancy conditions occur: one East, two East, three East, one West, two West, and three West. Print these numbers when the program terminates. Implement a counter that is incremented each time a thread enters the street. For each thread entering the street, record the value of the counter when it starts waiting and the value when it enters the street. Subtract these two numbers to determine the thread’s waiting time and record this information in a histogram like this. if (waitingTime < WAITING_HISTOGRAM_SIZE) waitingHistogram [waitingTime] ++; else waitingHistogramOverflow ++; Print the histogram and the overflow bucket when the program terminates. If you access the histogram or other test data from multiple threads be sure to guarantee mutual exclusion for these critical sections. In this part of assignment you will implement the same traffic simulation you did in the previous question,but using semaphores as the only synchronization principle. Copy your traffic.c file from part 1 into a new file called traffic_sem.c. Now modify your implementation to replace all mutexes and condition variables with semaphores. Alternatively, start with the provided traffic_sem.c file and implement the same functionality as your traffic.c file. In previous questions you implemented the Traffic problem with semaphores and with condition variables. In both cases, you printed a histogram of waiting threads, and were able to observe its fairness. You will notice that no matter how hard you try to make the condition variable implementation fair, if you have enough cars trying to get into the street at the same time, you can’t make it fair for everyone. You will see that cars occasionally end up waiting much longer than it seems they should. The problem is that there is an inherent unfairness with wait. When a thread is woken up by a call to wait, a race between the awoken thread re-entering the critical section when returning from wait and a new thread attempting to enter (e.g.,a car coming from the cross-street) may ensue. Resolving this unfairness is tricky and not necessary for this assignment. To see what is happening in this case, let’s assume there is a long queue of cars waiting on a condition variable. When signal is called indicating that the street can accommodate another car, the thread that has been waiting the longest is awoken. This is fair as ensured by the fact that the condition-variable waiter queue is a FIFO. However, if some other thread that has not been waiting at all (or has been waiting on the mutex lock queue instead) is, at this very moment, trying to get into the critical section and it beats the awoken thread into the mutex lock and the critical section, then it may get that thread’s position in the street, bypassing the awoken thread and every thread on the waiter queue. When this happens the awoken thread must wait again; and it does this by moving all the way to the back of the waiter queue. The purpose of the uthread_yield() loop after exiting the street is to minimize how often this situation occurs. You won’t see it happen often. But, it will happen often enough that a few threads occasionally end up waiting a very long time to get into the street. You might experiment with calling uthread_yield() more times after leaving the street (or less) and see how this affects fairness. Now notice what happens to the unfairness problem in the semaphore implementation. Describe the differences you see and explain why the results are different. A thread pool is a design pattern created to exploit the concurrency of threads without having application code ever call thread_create directly. It is based on maintaining a stable pool of worker threads that are ready to execute tasks as soon as new tasks become available, blocking if no tasks need to execute. The number of available threads is typically based on a combination of available resources and the load of tasks that must be performed in sequence. One benefit of a thread pool over creating a new thread for each task is that thread creation and destruction overhead is restricted to the initial creation of the pool, which may result in better performance and better system stability. Creating and destroying a thread and its associated resources can be an expensive process in terms of time. Resources like database and network connections may also take many CPU cycles to drop and re-establish, and can be maintained more efficiently by associating them with a thread that lives over the course of more than one transaction. Thread pools also solve an important problem faced by thread systems by placing a cap on the maximum number of currently running threads. You saw in Assignment 9 why having such a cap can be important. In applications that call thread_create directly, the total number of threads will tend to be a function of the amount of parallel work that is available at any given time. However, the total number of threads should really be capped based on the hardware resources available, for example. With a thread pool, applications submit as much work as they have and the pool determines, independently, how many threads it will created to run those tasks. Thread pools (or similar concepts, like server farms) are used often in cloud computation; for example,PrairieLearn uses a pool of workers to handle requests for automatic code grading. If the number of submissions is smaller than the number of workers, then external grading jobs can be executed immediately,but most workers will remain idle (or blocked) for the majority of time. If, however, a large number of submissions is received, over and above the number of workers available for grading, then some submissions may be required to wait until a worker becomes available to run the grading job. In this assignment you will implement a simple version of a thread pool, with a fixed number of worker threads. Your implementation will be able to schedule individual tasks in the form. of function pointers, which will be executed by worker threads as they become available.
UNIX Systems Programming Assignment 1) Write a Python program that prints the frequencies of words in the text file. Your output should be similar to the one shown below (same alignments and table-like format). Submit your (1) program and (2) a snapshot (picture of at least first 7 words in your table) of your results. 2) Write a Python program that reads the text from the file and writes its translation in the file hw8PirateOutput.txt. Use the translation described by Pb.4.3 from pg. 153. Note: in your output file you are allowed to have all words in lower case. Submit the (1) python code and (2) the file hw8PirateOutput.txt. 3) Write a Python program that verifies the check digit of Universal Product Codes (UPC). The Universal Product Codes on almost all purchase items utilizes a bar code to allow for the scanning of items. Below the bar code is the sequence of digits that the bar code encodes, as illustrated below. The last digit of the product code (2) is a check digit computed as follows. Add up all digits in the odd numbered positions excluding the last check digit, and multiply the result by 3. 0+6+0+2+1+5=14 14*3=42 Add up all digits in the even numbered positions excluding the last check digit. 3+0+0+9+4=16 Take the sum of the two previous results modulo 10. (42+16) modulo 10 = 8 Subtract the result from 10 to get the checksum digit. 10-8=2 The file contains many UPCs. Your program must read them from the file, and for each UPC it must display True if the check digit verifies as described above; otherise it displays False. Take a snapshot of your output similar to the one below, and upload it with your homework. Submit ypur (1) Python code and (2) a snapshot (picture) of your results.
COMPSCI5092 Research and Professional Skills For this assignment, you will be working with an application which displays images of the Munros. These are the 282 highest mountain tops in Scotland and are named after Sir Hugh Munro who first catalogued them. You can see the full list and hear the pronunciation of the Gaelic names on the Walk Highlands2 web page (you will not be tested on the pronunciation). Using “professional” development tools. Creating applications by “composing”3 objects of different classes. Understanding and using classes created by others, as well as the standard Java libraries. Integrating these with your own code. Working with remote services. Working with graphical user interfaces. Documenting and testing your code. 2 Preparation [1] Before starting on the assignment, make sure that you have a working set of development tools and understand how to use them. See LEARN Resources Course Notes DevelopmentTools.pdf . • A Java 17 SDK • Java FX SDK 17 • Hamrest 2.2 • JUnit The following illustrates the setup process: Now that you have a clean template project, you are ready to start work on the assignment . . . The demonstration application is structured using three main classes: • A View class which handles the interface (displaying the images, and detecting user input). • A Service class which retrieves a picture from the remote service. • A Controller class which manages the other classes and determines the overall behaviour of the program. A well-designed application will allow classes to be easily replaced with different implementations. To illustrate this, our library provides: Notice that each of these (View, Service, Controller) has several implementations and an interface5 specification which defines the methods that each implementation must provide. The library provides a mechanism for you to experiment easily with different combinations of these implementations by changing values in a “property file”: 1. Open the project file src main resources properties app.properties . Lines starting with # are explanatory comments which are ignored by the system. 3. Change the Controller from SimpleController to QuizController. The application will show a random Munro. You can guess the name and the application will tell you whether you are correct or not. Choosing New will display another Munro. 5. Reset the property file back to the original values for the following exercises.
CAB401: High Performance and Parallel Computing Assignment Due: 22/10/2021 (with proposal due by 06/09/2021) Worth: 50% Individual Overview You are to select a real world software application and manually parallelize it. That is, take any application that is not written in an explicitly parallel fashion and transform. it so that it executes as efficiently as possible on a particular parallel computer. The software application can be whatever you like but you will obviously need access to its source code. It can for example be an open source application or an application that you have developed yourself, or perhaps one from your workplace. To be amenable to parallelization it will need to be relatively computationally intensive, i.e. it will need to perform. sufficient computation so that parallelizing that computation will potentially produce a noticeable difference in perceived execution time. For example, a word processing application would probably not be a good candidate as such applications are already normally adequately responsive to user interaction. Note, that some applications are more amenable to parallelization than others. It is not expected that a perfect linear speedup will be achieved for all applications – simply that your parallelization achieves as much performance improvement as is available. Hardware You can use any parallel hardware that you have access to. You can make use of parallel computers provided by QUT or any other parallel computers you personally you have access to. It can be any form. of parallel computer, e.g. multi-core, cluster, SMP, shared memory, distributed memory, GPU, etc. See criteria below regarding scalable parallelism. Software Again you can use whatever software that you have access to. This includes compilers, profilers, debuggers, libraries, etc. Some such software is available through QUT. You may use whatever programming language you wish and whatever parallel frameworks and libraries that you have access to. Submission Project Proposal, due 03/09/2021: Submit online form, describing: 1. A brief description of the sequential application that you have selected to parallelize. What does it do? Where did you find it? (1 paragraph max) 2. Discuss whether you think the proposed application performs sufficient computation so that parallelizing it will potentially produce a noticeable difference in perceived execution time. (1 paragraph max). 3. What parallel hardware and parallelization language/framework are you considering? E.g. targeting NVidia GPU programmed using CUDA. (1 paragraph max). The project proposal is designed to give you constructive feedback and to ensure you are on a productive path prior to final submission. Final Submission, due 22/10/2021, a zip file including both: 1. A report of 10-15 pages (not including appendices) describing your outcomes. The report should address the following criteria: a. An explanation of the original sequential application being parallelized, what it does (black box) and how it works (a high level description of software’s design/architecture). This might include call graphs, class diagrams, etc – whatever you find useful to describe the structure of the original sequential application. b. Your analysis of potential parallelism within the application. This might include identification of existing loops or control flow constructs where parallelism might be found. Explanation of the data and control dependences that you analysed to determine which sections of code were safe to parallelize. Which of these is likely to be of sufficient granularity to be worth exploiting? Is it scalable parallelism? A discussion of changes required to expose parallelism, such as replacing algorithms or code restructuring transformations. c. How did you map computation and/or data to processors? Which parallelism abstractions or programming language constructs did you use to perform. synchronization? d. Timing and profiling results, both before and after parallelization and a speedup graph. e. How did you test that the parallel version produced the exact same results as the original sequential version? f. A description of the compilers, software, tools, and techniques you used to parallelize the application. g. The story of how you overcame performance problems/barriers (e.g. load imbalance, memory contention, granularity, data dependencies, etc) to improving parallel performance. h. An explanation of the code that you added or modified to parallelize the application (including source code line count). i. Reflect on your outcome – What have you learnt? How successful was your attempt? Do you think you’ve done as well as is possible? What might you have done differently? 2. Your source code (both before and after versions) together with instructions for compiling, running, hardware requirements and realistic input data sets. Assessment Criteria Criteria Standards Unsatisfactory Satisfactory (50%) Good Excellent (100%) Analysis of original application (10 marks) Demonstrates a deep understanding of the original application, its structure and performance issues/bottlenecks. (Must include identification and discussion of data and control dependencies and detailed before and after detailed profiling results). Use of tools and techniques (10 marks) Demonstrates advanced use of a wide variety of parallel programming software, tools and technologies. Optimal Speedup (10 marks) Obtained very close to the best possible performance improvement for the application (must be more than 4 cores for excellent). (Must include a correctly constructed speed-up graph). Overcoming Barriers (10 marks) Demonstrated great skill and effort to achieve this outcome and overcome significant barriers to improved performance. (Include interesting before and after code snippets) Report (10 marks) Report is well structured, easy to read, reflective and insightful.
CS1160 Random Number Guessing Game Requirement Write a program that generates a random number and asks the user to guess what the number is. If the user’s guess is higher than the random number, the program should display “Too high, try again.” If the user’s guess is lower than the random number, the program should display “Too low, try again.” The program should use a loop that repeats until the user correctly guesses the random number. You should also keep a count of the number of guesses that the user makes. When the user correctly guesses the random number, the program should display the number of guesses.
t-test statistic: t0 = standard error 1. Single mean μ: estimate = x; df = n− 1 3. Difference between two means μ1 − μ2: (independent samples) 4. Difference between two proportions p1 − p2: Situation (a): Proportions from two independent samples Situation (c): One sample of size n, many yes/no items F -test statistic: f0 = s2W The Chi-square test 0 ∑ (observed − expected)2 Expected count in cell (i, j) = n Regression Inference about the intercept, β0, and the slope, β1: df = n− 2
S1.21 STATS101/101G/108 BLOCK 1 These questions are worth one mark each. 1. Pick the option that correctly completes the statement. Data from a categorical variable are: 2. Pick the option that correctly completes the statement. A study which observes the same group of individuals or units over a long period of time is called a: 3. Pick the option that correctly completes the statement. Consider a well-designed experiment involving a group of volunteers. A tail proportion of less than 5% in the randomisation test allows us to make: 4. Pick the option that correctly completes the statement. Using random sampling: 5. Pick the option that correctly completes the statement. A bootstrap confidence interval may be interpreted as an interval: group or category names for each entity. measurements or counts taken on each entity. cross-sectional study. longitudinal study. sample-to-population inference. experiment-to-causation inference. allows for the calculation of the likely size of sampling errors. will guarantee representative samples. of plausible values for the parameter. within which the parameter is certain to lie. 6. Pick the option that correctly completes the statement. All other things being equal, bigger sample sizes give: 7. Pick the option that correctly completes the statement. The null hypothesis, H , is the: 8. Pick the option that correctly completes the statement. When conducting a t-test a plot of the sample data is used to check for evidence of: 9. Pick the option that correctly completes the statement. For a Chi-square test for independence, there will be evidence against the null hypothesis if there are relatively: 10. Pick the option that correctly completes the statement. The sign (+ or -) of the sample correlation coefficient, r, is: Note: For Questions 11 to 20 be careful which option you choose because the order of the True/False options may change from question to question. 11. Decide whether this statement is True or False. wider confidence intervals. narrower confidence intervals. 0 hypothesis we test. research hypothesis. non-Normal features. independence. small differences between the observed and expected counts in one or more cells. large differences between the observed and expected counts in one or more cells. not necessarily the same as the sign of the slope of the least squares regression line. always the same as the sign of the slope of the least squares regression line. For highly skewed data the sample median is a more sensible measure of the centre than the sample mean. 12. Decide whether this statement is True or False. An observational study can be used to reliably establish the cause of an effect. 13. Decide whether this statement is True or False. Under chance alone, when comparing two groups, the difference we observe would purely and simply be due to which units just happened to have ended up in which group and nothing else. 14. Decide whether this statement is True or False. Taking larger samples will not reduce the effects of selection bias and other nonsampling errors. 15. Decide whether this statement is True or False. We can be certain that the true value of a population parameter is somewhere in a bootstrap confidence interval for that parameter. 16. Decide whether this statement is True or False. The level of confidence is the long-run success rate for a method which aims at producing confidence intervals which contain the unknown value of the parameter. False True True False True False True False False True 17. Decide whether this statement is True or False. Statistical significance implies practical significance. 18. Decide whether this statement is True or False. If the P-value for an F-test for one-way analysis of variance is large then the differences we see between the sample means could be due to chance alone. 19. Decide whether this statement is True or False. The greater the value of the Chi-square test statistic, the weaker the evidence against the null hypothesis. 20. Decide whether this statement is True or False. The correlation coefficient measures the strength and the direction of a linear relationship between two numeric variables. False True False True True False False True False True Maximum marks: 20 2 Block 2: Questions 21 to 24 These questions are worth two marks each. Questions 21 to 24 refer to the information in Appendix A. 21. Which one of the following statements about the study is false? 22. Refer to Figure 2. Which one of the following statements could be false? 23. Refer to Figure 3. Which one of the following statements is false? This study is an experiment because the participants were randomly allocated to either the TimeRestriction group or the NoTimeRestriction group. The response variable was ReportedNumber. The researchers were blinded because they did not know what number the participants actually rolled. The NoTimeRestriction group was the control group. This study had a completely randomised design. There were more participants in the NoTimeRestriction group who actually rolled a 1 than participants in the TimeRestriction group who actually rolled a 1. The standard deviation of the ReportedNumber for the NoTimeRestriction group is higher than that of the TimeRestriction group. The median ReportedNumber for the NoTimeRestriction group is less than that of the TimeRestriction group. Numbers less than 3 were reported less often by participants in theTimeRestriction group than were reported by those in the NoTimeRestriction group. Participants in the TimeRestriction group tended to report a higher number than participants in the NoTimeRestriction group reported. 24. Suppose that the researchers were also interested in seeing if the underlying mean time taken to report their number by those in the NoTimeRestriction group was different to the underlying mean time taken to report their number by those in the TimeRestriction group. Let be the difference between the underlying mean time taken to report their number by those in the NoTimeRestriction group and the underlying mean time taken to report their number by those in the TimeRestriction group. Which one the following are a correct pair of hypotheses for this test? We have evidence that the time restriction caused the participants in the TimeRestriction group to roll higher numbers. The P-value for this randomisation test is less than 5%. We have evidence that chance was not acting alone in the actual study. We may claim that the time restriction had an effect on the mean ReportedNumber. We have evidence that Group together with chance produced the observed result. μNTR − μTR H0 : ¯¯x¯ NTR − ¯¯x¯ TR ≠ 8 H1 : ¯¯x¯ NTR − ¯¯x¯ TR = 8 H0 : μNTR − μTR = 0 H1 : μNTR − μTR ≠ 0 H0 : ¯¯x¯ NTR − ¯¯x¯ TR = 0 H1 : ¯¯x¯ NTR − ¯¯x¯ TR ≠ 0 H0 : μNTR − μTR ≠ 0 H1 : μNTR − μTR = 0 H0 : μNTR − μTR = 8 H1 : μNTR − μTR ≠ 8 Maximum marks: 8 3 BLOCK 3: Questions 25 to 30 These questions are worth two marks each. Questions 25 to 30 refer to the information in Appendix B. 25. Which one of the following could not be present in the data collected? Questions 26 and 27 refer to Figure 4 and the accompanying information. 26. Which one of the following statements is false? 27. Suppose that it was decided to use t-procedures to calculate a 95% confidence interval for the difference between the proportion of those interested in politics who said that they had voted and the proportion of those not interested in politics who said that they had voted. The sampling situation for calculating the standard error of the estimate is: Nonresponse bias Interviewer effects Question effects Behavioural considerations Sampling error The bootstrap confidence interval includes the difference in the sample proportions. The smallest sample proportion is the proportion of those not interested in politics who said that they did not vote. It's a fairly safe bet that the proportion of those interested in politics who said that they had voted is somewhere between 11 and 19 percentage points higher than the proportion of those not interested in politics who said that they had voted. The majority of respondents said that they had voted. In every resample the difference in percentage points was more than five. Questions 28 to 30 refer to Figure 5 and the accompanying information. 28. The test-statistic, , for this t-test is approximately: 29. Which one of the following statements is not a correct interpretation of the P-value for this t- test? 30. A 95% confidence interval for is (0.06, 0.12). Suppose that we wish to calculate a 90% confidence interval using the same data. Which one of the following statements is false? one sample of size 3207, several response categories. one sample of size 3412, several response categories. two independent samples of sizes 3207 and 205. one sample of size 3412, many yes/no items. two independent samples of sizes 385 and 3027. t0 0.09 0.03 4.32 5.59 1.96 At the 5% level of significance we can reject the null hypothesis. At the 10% level of significance we can reject the alternative hypothesis. At the 5% level of significance we can claim that is greater than .pN pL At the 1% level of significance we can claim that is greater than .pN pL The observed difference is a statistically significant result (at the 5% level). pN − pL The 90% confidence interval will: be calculated using the same t-multiplier. be narrower than the 95% confidence interval. not include zero. be calculated using the same standard error. have a smaller margin of error. Maximum marks: 12 4 BLOCK 4 These questions are worth two marks each. Questions 31 to 42 refer to the information in Appendix C. 31. Refer to Figure 6. Which one of the following statements is false? 32. Which one of the following is a correct pair of hypotheses for this t-test? 33. Refer to the test output in Table 1. Which one of the following statements is false? If the mean were shown on the plot it would be below the median. Approximately half of the movies in this dataset grossed more in the US than in the rest of the world. This data is positively (right) skewed. There are no gross outliers in this data. We could use this plot to check the assumption of Normality for a paired data t-test on this data. H0 : μDiff ≠ 0 H1 : μDiff = 0 H0 : μDiff = 0 H1 : μDiff ≠ 0 H0 : ¯¯x¯ Diff = 0 H1 : ¯¯x¯ Diff ≠ 0 H0 : ¯¯x¯ Diff ≠ 0 H1 : ¯¯x¯ Diff = 0 H0 : μDiff = 0 H1 : μDiff > 0 34. Based on the results of this t-test, which one of the following is a correct statement? Questions 35 to 40 refer to Tables 2 & 3, Figures 7 & 8 and the information that goes with them. 35. Refer to Figure 7. Which one of the following statements is false? With 95% confidence, we estimate that the underlying mean difference in gross income is somewhere between US$5.9 million and US$14.3 million. The confidence interval is narrow compared to the range of the sample data because it is calculated using a relatively large dataset. We cannot be certain that μDiff is somewhere between US$5.9 million and US$14.3 million. ¯¯x¯ Diff is in the middle of the 95% confidence interval for μDiff . The margin of error for the 95% confidence interval for μDiff is US$2.131 million. We may claim that, on average, movies' gross income from the rest of the world is higher than it is from the US. We have very strong evidence that a movie's gross income from the rest of the world is higher than it is from the US. We may claim that a movie makes more of its gross income in the rest of the world than in the US. We have very strong evidence that, on average, movies' gross income is more in the US than in the rest of the world. It is not plausible that, on average, movies make US$10 million more in the rest of the world than in the US. Questions 36 to 39 assume that a simple linear regression is appropriate. 36. The equation for the least squares regression line for this analysis is: 37. One of the movies that had a budget of US$40 million had a total gross income of US$315 million. Under this regression analysis, the residual for this movie is approximately: 38. For movies like those in this dataset, which one of the following statements is true? With 95% confidence, we estimate (to 1 decimal place) that, on average, an increase of US$10 million in the budget is associated with: The movie with the highest budget had the highest total gross income. Only two movies had a total gross income of more than US$1250 million. As Budget increases the variability in Total tends to increase. The maximum budget for any of these movies is about US$300 million. It looks like a lot of movies have a gross income less than US$250 million. Predicted Total = 8.996 + 3.035 x Budget Predicted Total = -8.996 + 3.035 x Budget Predicted Total = 3.035 + 0.117 x Budget Predicted Total = 3.035 - 8.996 x Budget Predicted Total = 0.117 + 3.035 x Budget 48 203 −275 −203 −183 39. Refer to Table 3. Which one of the following statements is false? For movies like those in the dataset, with 95% confidence we estimate that: 40. Which one of the following statements is false? We should be wary of using the results of this regression analysis to predict the total gross income of a movie released in 2020, based on its budget of US$600 million because: a decrease in the total gross income of somewhere between US$7.34 million and US$25.5 million. a decrease in the total gross income of US$90.0 million. an increase in the total gross income of somewhere between US$28.1 million and US$32.7 million. an increase in the total gross income of US$30.4 million. an increase in the total gross income of somewhere between US$7.34 million and US$25.5 million. movies with a budget of US$82.5 million will have an underlying mean total income of between US$231.0 and US$251.8 million. movies with a budget of US$190.0 million will have an underlying mean total income of between US$266.3 and US$869.1 million. a movie with a budget of US$175.0 million will have a total income of between US$221.1 and US$823.2 million. movies with a budget of US$40.0 million will have an underlying mean total income of between US$102.4 and US$122.4 million. a movie with a budget of US$225.0 million will have a total income of between US$371.6 and US$976.2 million. 41. Suppose we wish to investigate whether, on average, some distributors have a higher total gross income from their movies than others. Given that the underlying assumptions are satisfied, which form. of analysis, using the variables Total and Distributor, is most appropriate?
COMP90015 Distributed Systems Project 2 - Decentralized Chat 2021 Semester II Synopsis • In this assignment you will transform. your existing chat program into a decentralized chat application. • You may reuse as much of your project 1 code as you wish. You may rewrite everything if you wish as well. Feedback from project 1 assessment can be used to help improve your project 2 code and report. • The basic operation and protocol from project 1 will be the same in project 2, however instead of a client and server there will be only one process which we will call a peer. The peer will act as both a client and a server in the decentralized system. • The intended operation of the chat peer is described in this slide set. • You are required to also implement one extended feature as described next. Extended Feature I As well as the base protocol that everyone must implement, each group must choose one extended feature from the list of three choices below, design the protocol as an extension to the base protocol and implement in their peer: • Room Migration – Rooms can be moved from one peer to another. E.g. before a peer quits it can send its rooms to other peers. All peers that are currently in those rooms should automatically disconnect and reconnect to the room when it has been relocated. The peer that receives a room becomes the owner of that room. Selection of which peers to send rooms to should be based on ensuring that all existing peers in those rooms can connect to the new peer where their room is migrated to. Rooms should not become “lost”, e.g. if the peer that is receiving a room also quits in the middle of receiving it and therefore does not migrate it further. Of course, if there are no neighboring peers to migrate a room to then the room is lost if the peer quits. The user of a peer should also be able to issue a command to migrate a room on a room-by-room basis. Extended Feature II • Shout – A Shout command can be used by any user currently joined in a room. The command causes a provided message to be delivered to all rooms on all peers of the network. All peers in the network includes all peers for which there is a path of connections from the shouting peer, not just those peers that are directly reachable by the shouting peer. The order of delivery at all rooms on all peers of the network must be FIFO, i.e. that the order of the messages shouted by a given user matches the order of those messages delivered at each room at each peer, regardeless of whether some peers have connected and/or disconnected in between. When the shouted message is delivered to a room, the identity of the shouter should be listed as “IP:port shouted”, where IP and port are the values as seen by the peer hosting the room that the shouting peer is currently in. Extended Feature III • File Attachment – Attach a file or files to the message. Users should have the option to download specific attachments or download all attachments for a given received message. The download should happen by one of two mechanisms: (i) directly connecting to the peer that sent the message, if the peer indicates (as metadata in the message) this is allowed (e.g. the peer would typically have a public IP address for this to work), or else the peer that sent the message uploads the attachments to the peer maintaining the room and peers receiving the message download it from that peer. When a peer is uploading or downloading files it should not block the user from issuing further commands. Note: be carefull when implementing functionality that access the local file system - this creates a strong potential vulnerability. Chat Peer The base functionality that all groups must implement is briefly: • Each peer is started by a user who interacts with the peer on the command line in the same way as interacting with the client in project 1. • Each peer will maintain the chat rooms that are created by its user. Users can only create rooms on their own peer. As explained shortly, the create and delete room commands don’t require message passing because they are only executed locally. • There is no “main hall” room in project 2. A peer that connects to another peer must first obtain a list of rooms and then join one. The exact session protocol is discussed further in. • Peers will provide a list of neihboring peers with IP address and port number, that allows other peers to search the network of peers for chat rooms, using an iterative search mechanism. • Peers will allow other peers to connect to them, to search for chat rooms and to join chat rooms and chat in them. If a peer does not have a public IP address then only peers on the same private network as the peer can connect to it. Overview of peer protocol I • Protocol aspects taken from Project 1: • List – (same as proj1) respond with a list of rooms that the peer is maintaining • Join – (same as proj1) allow a peer to join a room • Who – (same as proj1) provide a list of who is in the room • Kick – (similar to proj1) the kicked user is forcibly disconnected from the peer, and blocked from reconnecting. This is effectively a local command that does not require message passing, as explained below, since only the owner of a room can kick others and rooms created on a peer can only be created by the user of that peer. • Quit – (same as proj1) disconnect from the peer • Message – (same as proj1) the message is sent to all peers in the room • Protocol aspects that are very different to Project 1: • The identity protocol and associated messages from project 1 will not be used. Rather a peer’s IP and port number combination, e.g. 192.168.1.10:3000, as seen by the peer hosting the room, will be used and shown as the peer’s identity. The peer cannot change its identity unless it disconnects and reconnects from a different IP address and/or a different port number. • The CreateRoom functionality will exist but will only be accepted if the command was given by the user of the peer, which means that effectively no actual messages are required since this command will never be accepted by any other peers. It can therefore be directly implemented in the peer without message passing. • The Delete functionality will exist but similar to CreateRoom, the delete command is a local command only that does not require message passing. • Additional protocol aspects: Overview of peer protocol II • ListNeighbors – a peer can ask a peer for a list of peers’ network addresss that are connected to it (of course, connected peers that are joined in a room also have their network address exposed however not all connected peers must be joined in a room) • SearchNetwork – a local command that causes the peer to do a breadth first search of all peers available to it (using a combination of ListNeighbors and RoomList messages, to gather a list of chat rooms over all accessible peers and show that to the user • Connect – a local command that causes the peer to make a TCP connection to the peer as given by the user, i.e. the user gives the IP and port number • Help – a local command that lists all of the commands available to the user with their syntax that shows how to use them Initial connection to a peer From this point on, for the purposes of discussion a peer that is connecting to another peer will be called the client and the other peer will be called the server. • When a peer process is started by the user, it does not connect to any other peer initially. • The user must use the Connect command (local command) to cause the peer to make a TCP connection to another peer. The user must know the IP and port number of the peer to be connected to. • When the connection is established from client to server, the server simply waits for the client to send a command. • While connected: • The user can use the List and other commands to find rooms, join a room and start chatting, very much the same way as project 1. The biggest differences are that the user’s identity is its IP and port number (as seen by the server) and that there is no “main hall”. • The user can use the ListNeighbors and SearchNetwork command (the operation of these commands is explained further in) to search the broader network of peers. • The user must use the Quit command to disconnect from the peer. The user can then connect to another peer. • When not connected to another peer, all of the commands issued are with respect to the local peer’s room list, including the local commands CreateRoom, Delete and Kick. • The peer process quits (disconnecting any connections first) when the standard input is closed, using Ctrl-D on the terminal. Client Command Line Interface • The client must accept input from standard input. Each line of input (terminated by a newline) is interpreted by the client as either a command or a message. If the line of input starts with a hash character “#” then it is interpreted as a command, otherwise it is interpreted as a message. • The client must write all output to standard output. Since chat is asynchronous, messages may arrive at any time and will be written to standard output when they arrive. For an extended feature the command line interface should provide ways to interact with the extended feature. • If some data such as streaming video needs to be displayed, a GUI window can be opened to display that. It should be controllable from the command line and may also be controllable from the GUI window itself. JSON Format • All protocol messages, i.e. sent between client and server, will be in the form of newline terminated JSON objects. • A JSON library must be used to marshal JSON output and to unmarshal JSON objects. Do not implement JSON (un)marshalling yourself. • All data written to the TCP connection must be UTF8 encoded. • When implementing an extended feature you may dynamically change to another data format other than JSON for that feature if you wish, but the base protocol must be implemented in JSON and the base protocol must continue to work regardless of whether the feature is used or not. E.g. you may even use a separate TCP connection to transmit binary data when required and have additional default ports for those aspects. You may add some fields to the base protocol messages if you need to support your extended feature, but you cannot change any of the existing fields. Connect command The peer to connect to is not given on the command line. Rather to make a connection to another peer: >#connect 142.250.70.238:4444 [] 192.168.1.10:38283> • The room is empty [] (no room) and the identity is the IP and port number as seen by the remote peer. • Note this example is a little contrived: the peer with the public IP address 142.250.70.238 would not see the private IP address 192.168.1.10, but rather would see the public IP address of the router that the privately connected peer is getting access through to the public network. Your actual output will differ according to the specific networks that you test on. The examples in this project specification continue with these contrived IP addresses. • If the port number is not provided then the default port number is used. As well, the connect command should allow the user to optionally specify which port they would like the TCP connection to use locally when making the connection: >#connect 142.250.70.238:4444 5000 [] 192.168.1.10:5000> Help command The help command should just list the available commands and their syntax, e.g. like: >#help #help - list this information #connect IP[:port] [local port] - connect to another peer #quit - disconnect from a peer ... You can simply provide a short description of all the commands like above. Join Room Protocol The client may at any time send a Join message to the server to indicate that the client wishes to change their current room to the indicated room. { "type":"join", "roomid":"comp90015" } E.g.: [] 192.168.1.10:38283>#join comp90015 Note the format above shows [] to indicate that the client having identity 192.168.1.10:38283 as seen by the server is not in a room. We can use the empty string "" to represent not in a room. Text messages sent when not in a room are ignored. Join Room Protocol When receiving a Join message the server must follow exactly this protocol: • If roomid is invalid or non existent then client’s current room will not change. The special room given by "" indicates that the client wants to leave the room but not join another room. I.e. stay connected but not be in any room. • Otherwise the client’s current room will change to the requested room. • If the room did not change then the server will send a RoomChange message only to the client that requested the room change. • If the room did change, then the server will send a RoomChange message to all clients currently in the requesting client’s current room and the requesting client’s requested room. E.g.: { "type":"roomchange", "identity":"192.168.1.10:38283", "former":"", "roomid":"comp90015" } Join Room Protocol The client will determine from the message whether the request was successful or not and will output relevant information: • If the request was not successful: “The requested room is invalid or non existent.” • If the request was successful then either “192.168.1.10:4444 moved to comp90015” if the client was not already in a room or “192.168.1.10:4444 moved from roomid to comp90015” if the client was already in a room called roomid in this example. And on the command line: [] 192.168.1.10:38283>#join comp90015 [] 192.168.1.10:38283> 192.168.1.10:38283 moved to comp90015 [comp90015] 192.168.1.10:38283> Room Contents Message I The RoomContents message lists all client identities currently in the room: { "type":"roomcontents", "roomid":"comp90015", "identities":["192.168.1.10:38283","192.168.1.10:5000","142.250.70.238:4444"], } There is no need to indicate an owner since the owner of the room is always the peer that is sending the message. The client may at any time send a Who message to request a RoomContents message from the server for a given room: { "type":"who", "roomid":"comp90015" } Room Contents Message II e.g. [comp90025] 192.168.1.10:38283>#who comp90015 Note that obviously the server knows the identity of every client connection, so the identity of the sender is not required. Room List Message The RoomList message lists all room ids and the count of identities in each room: { "type":"roomlist", "rooms":[{"roomid":"comp90025","count":5}, {"roomid":"comp90015","count":7}, {"roomid":"CovidWillComeToAnEnd","count":4}] } The client may at any time send a List message to request a RoomList message from the server: { "type":"list" } Room Information at the Client The client displays information regarding rooms and room lists whenever they arrive. Examples have been given on previous slides. Create Room Only the user of the peer can create a room on that peer, using the CreateRoom command. There is no message associated with this command. Rather the logic is implemented locally and is the same as in project 1: • If the requested name of the room is valid and does not already exist then it is created – the room name must contain alphanumeric characters only, start with an upper or lower case letter, have at least 3 characters and at most 32 characters. • The peer outputs either e.g. “Room jokes created.” or “Room jokes is invalid or already in use.” depending on whether the local command worked or not, for the example “jokes” room. Room Ownership The owner of a room is always the peer that created it. It can only be created by the user of that peer. Therefore there is no metadata required to maintain the owner of each room. For the purposes of discussion, the “owner” of a room always refers to the peer that created it.
Computing Theory COSC 1107/1105 Sample Exercise 2 Answers 1 Assessment details 1. Consider the grammar derivations below. S ⇒ aSb⇒ aaSbb⇒ aacSdbb⇒ aacdbb S ⇒ A⇒ xAy ⇒ xxAyy ⇒ xxB@yy ⇒ xxxB@yy ⇒ xxxx@yy S ⇒ A⇒ @C ⇒ @Cy ⇒ @Cyy ⇒ @yyy (a) From the above derivations, construct rules that must exist in any context-free grammar G for which these derivations are correct. Answer: From the first derivation we can see that the rules must include S → aSb, S → cSd and S → λ. From the second derivation we can add the rules S → A, A → xAy, A → B@, B → xB and B → x. From the third derivation we can add the rules A → @C, C → Cy and C → y. As this covers all the derivation steps in all three derivations above, we get the rules below. S → aSb | cSd | A | λ A→ xAy | B@ | @C B → xB | x C → Cy | y (b) Assuming that these are all the rules in G, give L(G) in set notation. Answer: L(G) = {wxi@yj(bd(w))Rorw(bd(w))R | i 6= j, i, j ≥ 0, w ∈ {a, c}∗} where bd(w) is w with all a’s replaced by b’s and all c’c replaced by d’s, and wR is the reverse of w. This may seem a little complicated but consider a string like aabax@yycdcc. If we replaced all d’s in the grammar with c’s and b’s with a’s, then the language would be {wxi@yjwR|i 6= j, i, j ≥ 0, w1 ∈ {a, c}∗}. So all we need to do to get the language of the original grammar is replace the a’s and c’s in wR with b’s and d’s respectively. Another point to note is that this language is not the same as the one below. {w1xi@yjw2 | i 6= j, i, j ≥ 0, w1 ∈ {a, c}∗, w2 ∈ {b, d}∗, |w1| = |w2|} Note that this latter language contains strings such as aabxx@yddd, which cannot be derived by the grammar. where na(w) is the number of a’s in w, and similarly for b, c and d. (c) Is there a regular grammar for L(G)? Explain your answer. Answer: There is no regular grammar for L(G). This language is context-free but not regular because there is a need to count the number of x’s and y’s to make sure that they are different, as well as counting the number of a’s or c’s and making sure there is an equal number of b’s or d’s. (d) Construct a context-free grammar for the language below. L = {xi w1@w2 yj | i 6= 2j, i, j ≥ 0, |w1| = |w2|, w1 ∈ {a, c}∗, w2 ∈ {b, d}∗} Answer: It is best to split this up into two cases and then combine the two grammars. So let L = L1 ∪ L2 where L1 = {xi w1@w2 yj | i < 2j, i, j ≥ 0, |w1| = |w2|, w1 ∈ {a, c}∗, w2 ∈ {b, d}∗} and L2 = {xi w1@w2 yj | i > 2j, i, j ≥ 0, |w1| = |w2|, w1 ∈ {a, c}∗, w2 ∈ {b, d}∗} For a constraint like i < 2j it can be helpful to use a table like the one below. i j 2j 0 1 2 1 1 2 2 2 4 3 2 4 4 3 6 5 3 6 So for L1 we get G1 below. S → xxSy | XA A→ Ay | By X → x | λ B → aBb | aBd | cBb | cBd | @ For L2 with the constraint i > 2j the corresponding table is below. i j 2j 1 0 0 3 1 2 5 2 4 7 3 6 This leads us to the grammar G2 below. S → xxSy | C C → xC | xD D → aDb| | aDd | cDb | cDd | @ We can then combine these together for a grammar G for L = L1 ∪ L2. S → T | U T → xxTy | XA A→ Ay | By X → x | λ B → aBb| | aBd | cBb | cBd | @ U → xxUy | C C → Cy | Dy D → aDb | aDd | cDb | cDd | @ There are ways this could be simplified, but that is not required. Constructing the grammar this way gives confidence in its correctness, which is less obvious otherwise. 2. Drogo the Dreary, a distant relative of Thorin Oakenshield, has written the following discussion of intractability. There are 5 incorrect statements in the paragraph below. Identify all 5 incorrect statements and justify each of your answers. “There are a number of problems which can be solved in principle, but in practice can be very difficult to solve. These problems are often referred to as NP-complete problems, and include the Travelling Salesperson problem, 3-SAT, factorisation and vertex cover. These problems are certainly intractable, i.e. all algorithms for these problems have exponential running times. This means that they can be solved for small instances, but the rate of growth of their complexity is so fast that they cannot be solved in practice for any reasonable size. For example, the best known algorithm for the Travelling Salesperson problem can take up to 2n10 +7n2 operations for a graph of size n. This means it is in the class O(n10) and is thus intractable. Fortunately it is possible to use approximation and heuristic algorithms to find some kind of solutions to these problems, either by removing the guarantee that an optimal solution will be found, or by removing the constraint that the running time will be polynomial or less (or removing both). There are also some similar problems, such as the Hamiltonian circuit problem, which are known to be simpler to solve than the Travelling Salesperson problem and are tractable. The name NP-complete problems comes from the property that such problems have run in at most polynomial-time on a nondeterministic Turing machine.” Answer: (a) Factorisation is probably intractable, but it is not known to be NP-complete. So it is incorrect to list it as an NP-complete problem. (b) NP-complete problems are almost certainly intractable, but it is incorrect to say that these are certainly intractable. (c) The best known algorithm for the Travelling Salesperson problem is exponential, and so the statement of the running time here is certainly incorrect. (d) Algorithms with a running time of O(n10) are in the polynomial class, and hence are con- sidered tractable. (e) The Hamiltonian Circuit problem is NP-complete, as is the Travelling Salesperson problem. So these are either both intractable or both tractable, i.e. in the same complexity class. 3. The generalised Platypus game with Gandalf the White is played as follows (we will abbreviate the name of this to GPGGW). There are three machines, with two being the usual platypus machines (as in the generalised Platypus game from Assignment 2), with the third machine being Gandalf the White (which we will abbreviate to GW ), which has the transition table as below. For simplicity we assume all three machines have the same alphabet Σ. The tape is infinite in both directions, and is initially blank. q0 blank blank R q1 q0 X X R q1 q1 blank blank L q0 q1 X X L q0 where X denotes any non-blank symbol in Σ. (a) Show that the halting problem for the GPGGW is undecidable. You may use any reduction you like. Note that you may assume that the generalised Platypus problem from Assignment 2 is undecidable if you would find that helpful. Answer: The simplest proof of this will be to reduce the generalised Platypus problem from Assignment 2 (which you can assume is undecidable) to this problem. The key obser- vation is that the Gandalf the White machine never changes any cell on the tape, and never terminates. This means that the generalised Platypus game with Gandalf the White halts iff the generalised Platypus game (from Assignment 2) halts. In terms of machines, consider the diagram below. Note that the machine the GPGGW only needs the machines M1 and M2 as input. It is also possible to use a reduction from the blank tape problem to the GPGGW problem as follows. Let M be the machine we want to analyse for the blank tape problem. Then M will halt on the blank tape iff the generalised Platypus problem with Gandalf the White halts for M and GW . In terms of machines, consider the diagram below. (b) Suppose the GPGGW is played on a Turing machine with a finite tape (making the halting problem decidable), and also that there is a decidable problem A for which there is a reduction from A to the GPGGW. This information could be used as an argument that the GPGGW is NP-complete, provided that some further information is known. What further information is needed? Explain your answer. Answer: To show that a problem is NP-complete, we need to show that the problem is in NP, and that the problem is NP-hard, i.e. that there is a polynomial-time reduction to it from every other problem in NP. The simplest way to show the latter property is to find a polynomial-time reduction from a known NP-complete problem to it. So given the information above, we also need to know the following. i. That GPGGW is in NP. ii. That the problem A is NP-complete. iii. That the reduction from A to the GPGGW is polynomial-time. (c) Freddo the optimistic Frog likes playing Platypus tournaments. He particularly likes the 3- player version, for which a tournament of n machines will require n(n+1)(n+2)/6 matches. He ran a tournament for 100 machines which took 42.42 seconds on the family desktop computer. Encouraged with his success, he attempts to run a tournament with 10,000 machines, but when it was discovered the computer took well over a day without coming close to finishing, he was given a strict limit of 8 hours for all such tournament play (so that tournaments could be run at night when all the other frogs were asleep). What is the largest tournament size that Freddo can play within this limit? Show your working. We will call this number n1. Answer: A tournament of 100 machines will require 100×101×102/6 = 171, 100 matches. Doing this in 42.42 seconds means that this takes 0.000247059 seconds per match. An 8-hour limit gives Freddo 8 × 60 × 60 = 28, 800 seconds, and hence 8 × 60 × 60/(0.000247059) = 116, 571, 345 matches. When n = 886, the numebr of matches is 116, 310, 536, and for n = 887 it is 116,704,364. So n1 = 886, i.e. Freddo can play a tournament of up to 886 machines. (d) Having despaired of realising his dream of a complete 3-player tournament, Freddo hears of a similar tournament game, known as Krazy Koalas. His friend Choco tells him that he can also run a 100-machine tournament in 42.42 seconds, but the Koala tournament “only” requires n6/(1000000) matches. Given Freddo’s time limit of 8 hours, what is the largest Koala tournament he can run? Show your working. We will call this number n2. Answer: From the previous answer we know that Freddo can run up to 116, 571, 345 matches. When n = 221, we have n6/(1000000) = (221)6/(1000000) = 116, 507, 435, and when n = 222, it is 119, 706, 531. So n2 = 221, i.e. Freddo can play a tournament of up to 221 machines. (e) Freddo, being an optimist, decides he wants to investigate the two types of tournament a little further. Given he knows it takes just under 8 hours to run a Platypus tournament with n1 machines and a Koala tournament of n2 machines, how long will it take to run a Platypus tournament with n2 machines? And how long will it take to run a Koala tournament with n1 machines? Show your working in each case. Answer: A Platypus tournament with n2 = 221 machines will take 1,823,471 matches, which will take 450.5 seconds, i.e. 7.5 minutes. A Koala tournament with n1 = 886 machines will take 483,729,230,338 matches which will take 119, 509, 574.55 seconds, i.e. 3.78 years. (f) Freddo’s activities attract the attention of a spambot (secretly installed on the family desk- top), and gets an unsolicited offer from Hammy Spam Solutions to provide a host server for running his tournaments, at a cost of $(1.01)n for a Platypus tournament of n machines, where n could be as high as 10,000. After a small amount of thought, Freddo deletes the offer and tells all his family and friends to avoid Hammy Spam Solutions at all times. Explain why Freddo did this, with particular reference to the cost for a tournaments involving 100, 1,000 and 10,000 machines. Answer: The cost is exponential, and sooner or later will become far too expensive. Freddo knows he can run a Platypus tournament of 886 machines at no cost (apart from 8 hours on the familiy desktop). Consider the table below. Machines Cost ($s) 100 2.70 1,000 20,959.16 2,000 439286205.05 3,000 9207067941189.81 4,000 192972369947324000.00 5,000 4044537935523770000000.00 6,000 84770100073685200000000000.00 7,000 1776709720877430000000000000000.00 8,000 37238335563086900000000000000000000.00 9,000 780484070759879000000000000000000000000.00 10,000 163,58,287,111,890,900,000,000,000,000,000,000,000,000,000.00 Enough said! 4. (a) Construct a Turing machine M1 which recognises your student number. This machine should accept only your student number; it should reject any string of length 6 or less, and any string of length 8 or more. The only string of length 7 which it should accept is your student number. Answer: We will assume your student number is 7654321. A Turing machine which recognises this is below. There are others of course, but note that this machine rejects any string of length 6 or less, as well as rejecting any string of lenth 8 or more. (b) Which of the following machines could also be used to recognise your student number, as above? Briefly justify each of your answers. A non-deterministic PDA A deterministic PDA A non-deterministic finite state automaton (NFA) A deterministic finite state automaton (DFA) A linear-bounded automaton Answer: All of these can be used to recognise your student number. There is no memory required, and it is simple to write a DFA for it. This means that all other types of automata can be used as well. (c) Consider the following machine M2, where q2 is the first state of your machine M1 above (so the states q0 and q1 below are added to your M1, with machine constructed this way starting in q0). Explain why M2 on input xxxxxxx will always eventually terminate with success, no matter what your student number is. Answer: This machine nondeterministically replaces every x on the input tape with one of the digits 0-9. Given the input of xxxxxx to the machine, this has the effect of guessing a 7-digit number, no matter what that number is. (d) Given an input of xn (i.e. n consecutive x’s), calculate the maximum time it will take M2 to terminate, assuming that it can process 1 transition from the above machine in 3× 10−5 seconds. Show your working and explain your reasoning. Show your answers for n = 7, 10, 15 and 20 in the table below. Use the most appropriate units of time in each case. n Transitions Time 7 10 15 20 Answer: As the deterministic execution of M2 may take up to n× 10n transitions to guess the correct n-digit number, the maximum time for it to terminate will be n×10n×3×10−5 = 3n× 10n−5 seconds. Note that each number takes n transitions. n Transitions Time 7 70,000,000 2100s = 35 minutes 10 1011 34.7 days 15 1.5× 1016 14,259 years 20 2× 1021 1,901,285,269 years
Homework 1: ML 80629A (FALL 2021) Instructions: • Please include your name and HEC ID with submission. • The homework is due by 11:59pm on the due date. • The homework is worth 20% of the course’s final grade. • Assignments are to be done individually. • All code used to arrive at answers is submitted along with answers. You can convert your jupyter notebook or colab to pdf and upload it. 1 ML Fundamentals (20pt) 1. (4pt) Explain the difference between the training error and the general- ization error. Make sure to describe how to evaluate the generalization error of a model in practice including pitfalls of this approach. 2. (4pt) To increase the size of your training set you first train a model and then use it to obtain labels on an unlabelled test set. You then retrain the model with the data from your train set as well as the data from your test set. Would you expect that your final model would obtain a lower validation error? 3. (4pt) Suggest a method for regularization a K-NN model. Hint: think of what regularization accomplishes in terms of the bias/variance trade off. 4. (4pt) Recall the task of document classification where documents must be classified based on their content. If the documents are encoded in a bag-of-words format, could you use K-NN to classify them? If so, describe a distance function that might be sensible to use. Otherwise, explain why not. 5. (4pt) Describe both the advantages and the disadvantages of using a larger K when doing K-fold cross validation. 2 Regression (15pt) • Let’s explore California housing dataset. This dataset was obtained from the StatLib repository. The target variable is the median house value for California districts, expressed in hundreds of thousands of dollars ($100,000). You can load the data from scikit-learn. You can use .DESCR to gather more info about this dataset. 1. (2pt) Perform. statistical analysis by using .describe() on the data, what do you notice about the attribute values? 2. (2pt) Look at the distribution of the attribute values by plotting their histograms. Notice anything interesting? 3. (3pt) Perform. 10-fold cross-validation (with shuffle=True and random state=20160202) with a LinearRegression model. Report the mean squared error (MSE) on the validation set (averaged across folds). • Two very popular options in Linear Regression are the Lasso method and the Ridge Regression. These models are implemented in sklearn: Lasso and Ridge. Hint: If you’d like to understand Ridge Regression better, you might want to look at this example. 4. (2pt) What one word captures what Lasso and Ridge do? 5. (3pt) Perform. 10-fold CV with normal LinearRegression, Lasso, and Ridge. Compare the attribute weights (coef) of each of these meth- ods. What do you observe? 6. (3pt) Report the average MSE for each method on the validation set across folds. How do these variants of linear regression perform compared to each other? Classification (65 pt) In this exercise, you will implement Naive Bayes classifier and neural network models to carry out a text classification task. You will implement various fea- ture representations, i.e., BoW and TF-IDF and then you will do performance analysis of NNs and NB with different hyperparameter settings. The data to download is movie reviews dataset. In each file (train, vali- dation, test), each line consists of a single review text followed by a number indicating the sentiment : 0 for negative and 1 for positive. You would have to split the these data into input texts and corresponding labels.Hint: you can use the function split(’t’), pandas allows you to easily use this data. 3 Feature Representations (5pt) Transform. the input text data into the following feature representations to train some models. You can use scikit-learn tools to do this. To reduce the time for training, please set max-features = 10000 to build a vocabulary that only consider the 10k top max features ordered by term frequency across the corpus. Do not change the other parameters. For this question, we ask you for the few lines of code from sklearn that you used to encode (and only encode) the training, validation and test data into (use the default settings): 1. (3pt) Bag-of-Words features (BoW) 2. (2pt) TF-IDF features 4 Naive Bayes (15pt) 1. (5pt) Perform. the sentiment classification task with these 2 different types of features. Report which NB you used and what is the validation set accuracy in each case. 2. (10pt) Based on the classification of the model, report 5 words from the texts in the train dataset that can be inferred as positive and 5 words that are negative. 5 Neural Network (30pt) After all the required imports in your code be sure to set the random state=12345. 1. (12pt) From the BoW and TF-IDF features from above, you are going to train different neural network models. Use the option early stopping=True and train the networks by trying all the following hyperparameter combi- nations: • dimension of a first hidden layer: [4,8,16] • dimension of a second hidden layer: [0,4,8] • learning rate (after fixing the above three hyperparameters): [0.1, 0.01, 0.001] • L2 (penalty): [0.001, 0.01, 0.1] What is the best combination of hyperparameters and what is the perfor- mance on the resulting model validation set? 2. (16pt) What did you observe with the impact of different hyperparame- ters on the model accuracy? Write a brief recommendation to follow for someone trying to find the best hyprparameters for their model. 3. (2 pt) Can you recommend any other hyperparameters to tune? 6 Comparison (15pt) 1. (4pt) Determine the performance of the simplest baseline, i.e., majority voting, for this task. 2. (5pt) For each case of the feature representation (BoW and TF-IDF), report the best test performance accuracies of the Naive Bayes classifier and Neural Network that you observe. 3. (3pt) Based on these accuracy values, which is the best feature represen- tation for each type of model that we have considered? Can you think of why this is the case? 4. (3pt) Based on these accuracy values, which is the best performing model? Explain briefly why it is the case.
EngGen 131 S2 2021 Lab 12 – 1 – Course Manual (C Programming) ENGGEN 131 2021 Lab 12 Recursion HAVE YOU COMPLETED THE PREPARATION EXERCISES? Pages 173-176 of the coursebook contain the “Preparation Exercises” for this lab. You should complete these exercises before you attempt the exercises in this lab. In particular, these preparation exercises illustrate the basic concepts behind recursion. GETTING STARTED Download the .zip file called “Lab12Resources.zip” from Canvas. This file contains all of the resources that you will need to complete this lab. DEVELOPMENT ENVIRONMENT You may use any development environment of your choice. EXERCISE ONE (2 marks) Recursive reverse For this exercise you need to define a recursive function called PrintReverse() which take an integer as input, and prints the digits in this integer in reverse order. For example, the function call: PrintReverse(123456); should print: 654321 The following diagram illustrates how we can solve this problem recursively: How should the PrintReverse() function be defined? void PrintReverse(int n) { } Base case: A good base case for this problem will be when the input value, n, is less than 10 (i.e. a single digit). In this case, the digit can just be printed Recursive case: Step 1: the expression n % 10 gives you the right-most digit which can just be printed Step 2: the expression n / 10 gives you the number excluding the rightmost digit, which can then be the input to the recursive function call. EXERCISE TWO (3 marks) Recursive conversion For this exercise you need to define a recursive function called ConvertToBinary() which take an integer as input and prints the binary equivalent of this input value. There is a simple algorithm for converting a decimal number to binary: 1. repeatedly divide the number by 2 2. write down the remainder at each step 3. stop when the number reaches 0 4. the binary number is the list of remainders in reverse For example, start with the number 157. If we repeatedly divide this by 2 and write down the remainders: Division Result Remainder 157/2 78 1 78/2 39 0 39/2 19 1 19/2 9 1 9/2 4 1 4/2 2 0 2/2 1 0 1/2 0 1 Now, let’s write these remainders down in reverse: 1 0 0 1 1 1 0 1 This is the binary equivalent of the decimal number 157. You could easily write a program to perform this conversion using a loop. However, in this exercise you must write a recursive function to solve the problem. You must not use any loops in your solution. If you look at the previous example, let’s say you KNEW HOW TO print 78 in binary (1001110). In that case, to print 157 in binary all you would have to do is print 78 in binary first (note, this is n / 2), and then print 157 % 2 (in this case 1). In other words, to solve the problem of size n, the recursive step involves solving the problem for size n / 2 and then printing n % 2. So, how should the ConvertToBinary() function be defined? void ConvertToBinary(int n) { } Pay particular attention to the base case and the recursive case below. To “convert n to binary”: Base case: if n is 1, then simply print 1 Recursive case: otherwise, “convert n / 2 to binary” and then print n % 2 EXERCISE THREE (3 marks) Recursive combinations The number of combinations of m things chosen out of n is written: m n and is pronounced "n choose m". For example, there are 52 cards in a deck, all distinct. The number of possible poker hands is the number of different ways we can pick five cards from the deck: 5 52 There is an elegant recursive definition of m n as follows: Base cases 0 n = 1. That is, there is only one way to pick zero things out of n: pick nothing. n n = 1. That is, the only way to pick n things out of n is to pick them all. Recursive case If 0 < m < n, then 1 11 m n m n m n For this exercise, you should define a function called Choose() which takes two integer inputs, n and m, and which calculates m n . How should the Choose() function be defined? int Choose(int n, int m) { } For example, the following code: printf("Result = %d", Choose(6, 2)); should print: Result = 15 EXERCISE FOUR (2 marks) Time to reflect (one more time!) Over the past few weeks, you've been learning C programming and completing many different tasks. At the beginning of this C module, we asked you to reflect on your experience working together in groups when you are practicing and learning programming. Now we'd like you to reflect back on how your preferences for working in groups have changed over the course of this semester. Questions 4 – 7 (“self-regulation”) Like any subject, learning programming presents unique challenges. Everyone learns and studies in their own way and now, as you begin learning a new programming language, it may be beneficial to reflect on what strategies work best for you. “Self-regulation” of learning describes the processes that help you understand what is working or not about your behaviour and strategies for learning. Exercises 4-7 will help step you through this reflection. Questions 8 – 11 (“co-regulation”) In the ENGGEN131 course, any source code that you submit for marking should be written by yourself, however discussing ideas at a "high-level" or talking through problems with others can be helpful. You are encouraged to discuss course material or general problems with others, if you find that useful. Like “self-regulation” of learning when you study by yourself, when you study in a group or with others the term “co-regulation” of learning describes the social strategies and processes that you use when learning together with others. Exercises 8-11 will help step you through this reflection.
COMP 5416 Assignment 2 Due: 6/November/2021 23:59 Question 1 (TCP, 20%). In the following network, node A transmits packets that pass through B, C, and D, and arrive at the destination E. The bit rate of all links is R = 1 Mbit/sec. The maximum packet size in the network is 500 Bytes. Ignore the header size. The one-way propagation delay on each link is 4 msec. How long does it take to transmit 100 + s packets if TCP Reno is used, where s is the last two digits of your student number. At the beginning, ssthresh is 8 segment size (4000 bytes). B, C, and D use Store-and-Forward. No packet is lost. There is no bit-error in transmission. The size of ACK packets is negligible. The size of TCP header is negligible. ! " # $ % 2Question 2 (Token Bucket Simulation, 20%). In this task, you need to simulate and analyze a token bucket. You can reuse some the codes in Week 6 Lab. You Python code must be submitted as supplementary material. Only Python 3 is allowed. The token bucket scheduler consists of a bucket which can accommodate x tokens and a queue which can accommodate infinite packets. The arrival of packets follows an independent Poisson process with rate λ > 0 unit/second. The arrival of tokens follows a deterministic process. That it, the inter-arrival time is a constant, i.e., 1µ unit/second. We assume that λ = 1 unit/second, and µ = 1.25 unit/second. Let x = 3 + floor(s/2), where s is the last digit of your student number. For example, if your student number is 490012345, then s = 5 and x = 5. Let 1, 2, 3, 4, . . . denote the states where there are 1, 2, 3, 4, . . . packets in the buffer. Let −1,−2, . . . ,−x denote the states where there are 1, 2, . . . , x tokens in the bucket. Let 0 denote the state where there are 0 packet and 0 token. (1) By simulation, find out the unconditional stationary distribution of the system states −x,−x+ 1, . . . , 0, 1, 2, . . .. (2) By simulation, find out the conditional distribution of the the system states when a packet arrives. (3) By simulation, find out the conditional distribution of the the system states when a token arrives. (4) By simulation, find out the mean time that a packet waits in the buffer. (5) Find out the probability that a token is dropped. 3Question 3 (Multi-thread Server: Implementation, 20%). You are given the complete code for the client in Lab in Week 8. Your task is to write the TCP server. The client code is in client.py. You must not modify this code. (However, you are allowed to change ServerName and ServerPort). Only Python 3 is allowed. Different from the server in the lab, the new server must be able to serve multiple clients simultaneously. Please note that the server code in Week 8 can only accept one client! In order to serve multiple clients simultaneously. The server should run multiple threads. The server will establish a new connection socket to communicate with one new client, and each new connection socket will be managed by a new thread. You should self-study the following function: _thread.start_new_thread(). The following figure shows an example of server when two clients are sending images at the same time. The two connections are closed in the end, demonstrating that there are two concurrent transmissions before the first “Connection closed”. You also need to capture the concurrent data transmission by Wireshark. In the example in the next page, we can see that the two clients are running at 192.168.0.3, with port numbers 60458 and 60462. The server is running at 192.168.0.4, with port number 12011. The throughputs of the two connections are both positive at around the 4th second. Tasks and submissions: (1) Build up a multi-thread server which can serve multiple clients at the same time. Submit your server-side Python code. Submit your server code as Lastname_Firstname_Server.py. We will use the client in Week 8 to test against your server. (2) Test your server with three clients sending images at the same time. Capture the packets by Wireshark at the server side. You are allowed to run the server and clients in one computer using localhost. Submit your Wireshark capture. Your capture file must be smaller than 10MB. Your capture will be ignored and will not be marked if it is greater than 10MB. Submit your capture as Lastname_Firstname_Capture.pcapng (or .pcap). (3) In the main submission file, based on your capture in (2), plot the throughput vs. time of the three connections (similar to the figures in the next page). Show that they are operated in parallel. In the main file, you also need to give the three clients’ IP addresses, clients’ port numbers, server’s IP address, and server’s port number. 4You overall mark will be zero if you do not submit code in (1), no matter if you submit (2) or (3). You submission in (2) and (3) will be ignored and will not be marked if your submission in (1) does not work. You overall mark will be zero if your Wireshark capture in (2) does not match the throughput plots in (3). 5Question 4 (BER vs SNR with different modulation schemes, 20%). We aim to plot BER vs SNR curves of different modulation schemes in this question. (1) BPSK. In wireless communication, we can transmit 0 and 1 through signals −1 and 1 respectively. Both −1 and 1 signals have power of 1, so that the mean signal power is 1. This is called Binary Phase Shift Keying (BPSK). Due to the existence of noise, the received signal is −1+n or 1+n respectively, where n is the noise term. n follows normal distribution n ∼ N(0, σ2). σ2 is the power of the noise, and thus 1σ2 is SNR. If the received signal is ≥ 0, it is decoded as 1; if the received signal is < 0, it is decoded as 0. We assume that 0 and 1 are sent with equal probabilities. Compute average BER vs SNR of BPSK when SNR = [0,5,10,15,20,25] dB. Hint: What is dB? (2) 4QAM. Now we consider another modulation scheme, where we can use two orthogonal signals (x, y) to represent 2 bits. (x is usually carried by a cosine signal, and y is usually carried by a sine signal.) We can transmit 00, 01, 11, and 10 through signals (−1,−1), (−1, 1), (1, 1), and (1,−1) respectively. The signal power is 2. This is called 4 quadrature amplitude modulation (4QAM). Still, due to the existence of noise, the received signal (r1, r2) is (−1+n1,−1+n2), (−1+n1, 1+n2), (1+n1, 1+n2), and (1 + n1,−1 + n2) respectively, where (n1, n2) is the noise term. n1 and n2 are independent random variables with normal distribution, with mean 0 and variance σ2. The power of the noise calculated as E(n21 + n 2 2). The received signal is decoded as • 00, if r1 < 0 and r2 < 0; • 01, if r1 < 0 and r2 ≥ 0; • 11, if r1 ≥ 0 and r2 ≥ 0; • 10, if r1 ≥ 0 and r2 < 0; where the regions r1 < 0 and r2 < 0; r1 < 0 and r2 ≥ 0; r1 ≥ 0 and r2 ≥ 0; and r1 ≥ 0 and r2 < 0 are called decision regions (see the figure below). Compute average BER vs SNR of 4QAM when SNR =[0,5,10,15,20,25] dB. Still, we assume that bits 0 and 1 are sent with equal probabilities. You can make reasonable approximations to calculate the probabilities using Q function or erfc function through computer. It is not necessary to calculate double integral. 11 00 01 10 x y (3) 16QAM. Now we consider an even more complicated modulation scheme. We use two orthogonal signals (x, y) to represent 4 bits. x and y can be −3, −1, 1, or 3, and the represented four bits are shown in the figure below. For example, (−1,−1) represents 0101. Please note that through this arrangement, there is only one bit difference between two neighbors, which will reduce bit error rate. Still, the noise is (n1, n2). n1 and n2 are independent random variables with normal distribution, with mean 0 and variance σ2. The power of the noise is calculated as E(n21 +n 2 2). The decision regions are shown in the figure below. For example, for the received signal (r1, r2), if −2 ≤ r1 < 0 and −2 ≤ r2 < 0, it is decoded as 0101. The average signal power is (32+32)+(32+12)+(12+32)+(12+12) 4 = 10. 6y x 0001 0011 0010 0000 0101 0111 0110 0100 1101 1111 1110 1100 1001 1011 1010 1000 -1-3 1 3 1 3 -1 -3 Compute average BER vs SNR of 16QAM when SNR =[0,5,10,15,20,25] dB. Still, we assume that bits 0 and 1 are sent with equal probabilities. You can make reasonable approximations to calculate the probabilities using Q function or erfc function through computer. It is not necessary to calculate double integral. (4) Plot the BER vs SNR curves of BPSK, 4QAM, and 16QAM. You should derive a figure like Page 53 in the slides of Week 8. Discuss why improved data rate can cause higher BER. 7Question 5 (Cellular network with guard channel, 20%). Consider one cell in a cellular network. There are 60 available channels and each channel can be used by exactly one user. New user arrivals follow an independent Poisson Process with arrival rate λn and handoff user arrivals follow an independent Poisson Process with arrival rate λh. Both new and handoff users stay active for a random duration, following exponential distribution with mean 1µ . The cell reserves X channels for handoff user arrivals. As discussed in the class, new arrivals will be blocked if 60−X or more channels are occupied. Handoff arrivals will be dropped if 60 channels are occupied. We assume that λn = 2400 units/hour, λh = 600 units/hour, and 1µ = 1 minute. (1) Let X = 5. Compute the probability that a new arrival is blocked. Compute the probability that a handoff arrival is dropped. (2) If a new arrival is blocked, a $0.01 loss will be incurred; If a handoff arrival is dropped, a $0.1 loss will be incurred. Find the optimal X so that the overall loss is minimised. 8Submission Instructions: You should submit one main file and several supplementary files. You should include your answers to Q1–Q5 and explanations of your answers in the main file. You should submit your main file at “main file submission”. The main file is in the format of pdf. For Q2, you must submit your simulator at “Q2 code submission”. For Q3, you must submit your Python code at “Q3 code submission” and Wireshark capture at “Q3 capture submission”. Your code and capture will be examined against your answers in the main file. Penalty would be incurred if your code/capture does not match your answer in the main file. For Q4/Q5, you may upload Python code to calculate the result in “Q4/Q5 calculation”. Please note that, files uploaded in Q4/Q5 will be marked as intermediate steps. Wrong answers in Q4/Q5 without file uploads will incur heavier penalties. File upload File format Must upload? main file submission pdf Yes Q2 code submission Python 3 code Yes Q3 code submission Python 3 code Yes Q3 capture submission Wireshark capture Yes Q4 calculation Python 3 code No Q5 calculation Python 3 code No TABLE I FILE UPLOAD All your submissions will be checked by plagiarism examination tools. This is one assignment with multiple pieces to submit. Your submission time is equal to the submission time of the last piece. Submission instruction of Q6 (bonus question) will be released when Q6 is available in Week 12.
Research School of Computer Science Assignment 5 Theory Questions COMP3670: Introduction to Machine Learning Question 1 Properties of Eigenvalues (5+5=10 credits) Let A be an invertible matrix. 1. Prove that all the eigenvalues of A are non-zero. 2. Prove that for any eigenvalue λ of A, λ−1 is an eigenvalue of A−1. Question 2 Properties of Eigenvalues II (10 credits) Let B be a square matrix. Let x be an eigenvector of B with eigenvalue λ. Prove that for all integers n ≥ 1, x is an eigenvector of Bn with eigenvalue λn. Question 3 Distinct eigenvalues and linear independence (20+5 credits) Let A be a n× n matrix. 1. Suppose that A has n distinct eigenvalues λ1, . . . , λn, and corresponding non-zero eigenvectors x1, . . . ,xn. Prove that {x1, . . . ,xn} is linearly independant. Hint: You may use without proof the following property: If {y1, . . . ,ym} is linearly dependent then there exists some p such that 1 ≤ p < m, yp+1 ∈ span{y1, . . . ,yp} and {y1, . . . ,yp} is linearly independent. 2. Hence, or otherwise, prove that for any matrix B ∈ Rn×n, there can be at most n distinct eigenvalues for B. Question 4 Properties of Determinants (10+15=25 credits) 1. Prove det(AT ) = det(A). 2. Prove det(In) = 1 where In is the n× n identity matrix. Question 5 Eigenvalues of symmetric matrices (15 credits) 1. Let A be a symmetric matrix. Let v1 be an eigenvector of A with eigenvalue λ1, and let v2 be an eigenvector of A with eigenvalue λ2. Assume that λ1 6= λ2. Prove that v1 and v2 are orthogonal. (Hint: Try proving λ1v T 1 v2 = λ2v T 1 v2. Recall the identity a Tb = bTa.) Question 6 Computations with Eigenvalues (3+3+3+3+3=15 credits) Let A = [−1 2 3 4 ] . 1. Compute the eigenvalues of A. 2. Find the eigenspace Eλ for each eigenvalue λ. Write your answer as the span of a collection of vectors. 3. Verify the set of all eigenvectors of A spans R2. 4. Hence, find an invertable matrix P and a diagonal matrix D such that A = PDP−1. 5. Hence, find a formula for efficiently 1 calculating An for any integer n ≥ 0. Make your formula as simple as possible. 1That is, a closed form. formula for An as opposed to multiplying A by itself n times over.
ECPS 206 Lab 2 Hardware Setup ● Recommend to install the heat sinks ○ https://www.youtube.com/watch?v=E-4GaAz7XNM ● Recommend to install the case and power the fan with 3.3V or 5V. ● Connect 4 LEDs with wires and resistors (to protect LEDs) ● Connect a T-type extension board and cables ○ https://www.youtube.com/watch?v=RCIL35e47mk RPi 4: Connect with Breadboard and LEDs RPi 4: Layout ● Board & Intro: https://www.etechnophiles.com/raspberry-pi-4-gpio-pinout-specifications-and-sc hematic/ ● Pins: https://pi4j.com/1.4/pins/rpi-4b.html ● Datasheet: https://datasheets.raspberrypi.org/rpi4/raspberry-pi-4-datasheet.pdf ● Pick some GPIO XX for LED connections RPi 4: Connect RGB Light Sensor TCS34725 From To Description RPi / G TCS34725 /GND Ground for I2C Light Sensor RPi / 3V3 (PIN 1) TCS34725 / 3V3 3.3V Power for I2C Light Sensor RPi / SDA1 I2C (PIN 3) TCS34725 /SDA SDA for I2C Light Sensor RPi / SCL1 I2C (PIN 5) TCS34725 /SCL SCL for I2C Light Sensor TCS34725 / LED TCS34725 / INT Connectng these two pins together allow for softwarecontrol of bright LED on TCS34725 board ESP8266: Ambient Light sensor (photoresistor) ● Follow the instructions and example code to test connection. ○ https://www.instructables.com/id/NodeMCU-With-LDR/ ESP8266: Ambient Light sensor (photoresistor) ● Example code (link from previous slide, or check similar one in File > Examples > Analog > AnalogInOutSerial) utilizes analog signal read function. Software Setup ● Recommend to use Raspberry Pi Imager to pre-configure OS ● Refer to the link to download the Imager on your laptop to write OS image into SD card: https://www.raspberrypi.com/software/ ● How to use Imager: https://www.youtube.com/watch?v=ntaXWS8Lk34 ● If you have monitor & keyboard & mouse, choose the Raspberry Pi OS (32-bit). ● Configure WiFi: https://www.seeedstudio.com/blog/2021/01/25/three-methods-to-configure-raspberry-pi-wifi/ ● If you don’t have monitor and would like to work on SSH Linux console with cellphone hotspot, you can follow these steps in Imager: https://www.pragmaticlinux.com/2021/08/raspberry-pi-headless-setup-with-the-raspberry-pi-imager/ ● Note that after pressed Ctrl-Alt-X for Advanced options, these are recommended: ● Checked “Set hostname”. Optional to change the “raspberrypi” to preferred name. ● Checked “Enable SSH”. Select “Use password…” and type any password ● Checked “Configured WiFi”. Type your hotspot WiFi SSID & password. Change WiFi country to US (faster by delete it and type) ● Checked “Set locale settings”, choose America/… and us ● Checked “Skip first-run wizard” ● Unchecked “Play sound…”, “Eject media…”, “Enable telemetry”. ● Save to close options ● Press Write and wait for it. RPi 4: Install the Raspberry Pi OS Logged in Raspberry Pi OS via either GUI desktop or SSH. Open console: 1. Turn on I2C Interface ● sudo raspi-config ● Choose Interfacing Options > I2C > Yes 2. Install the necessary packages ● sudo apt-get update ● sudo apt-get install -y git build-essential python3-dev python3-setuptools python3-pip python3-smbus 3. Reboot ● sudo reboot 4. Install Adafruit Python TCS34725 ● git clone https://github.com/adafruit/Adafruit_Python_TCS34725.git ● cd Adafruit_Python_TCS34725/ ● sudo python3 setup.py install 5. Run the simpletest.py example in examples/ folder: python3 simpletest.py RPi 4: Install the TCS34725 python library Network issue ● Using “UCInet Mobile Access” ○ Find the MAC address of ESP8266 ■ https://techtutorialsx.com/2017/04/09/esp8266-get-mac-address/ ○ Find the MAC address of RPi 4 ■ In the terminal or SSH, Type the command “cat /sys/class/net/wlan0/address” ○ Register the MAC addresses to UCI ■ http://apps.oit.uci.edu/mobileaccess/registration/ ● Or use your cellphone hotspot function to setup manageable and isolated network ○ Recommend and it allows broadcast for other HWs. Python UDP examples for RPi ● Basic Python UDP echo client example: ○ https://pymotw.com/3/socket/udp.html ● Python UDP Send/Recv examples: ○ https://stackoverflow.com/a/27893987 ○ set the timeout to know the 5 seconds is up. C UDP Example for ESP8266 ● Reference: https://arduino-esp8266.readthedocs.io/en/latest/esp8266wifi/udp-examples.h tml ● Example: https://siytek.com/esp8266-udp-send-receive/ ● Or, you can also check in IDE: File > Examples > ESP8266Wifi > Udp. change the “your-ssid” to the Wifi network name and “your-password” if there is a password or empty otherwise. #define STASSID "your-ssid" #define STAPSK "your-password" ○ Try using RPi 4’s terminal with the following command to confirm the network is working: ○ nc -u 8888 C UDP Example for ESP8266 ● Example to get IP address from socket and blink the IP address on ESP8266 ○ https://github.com/rin67630/Blink-my-IP Hint ● Design your message format to send ○ When ESP8266 receives first message, keep the IP and port of RPi globally for later use. ○ Use sprintf and strncmp to deal with string type messages on ESP8266. ○ On ESP8266’s side, lux value can be converted to bytes buffer before sending (use itoa () ) ○ On RPi’s side, recv length is recommended to be equal to buffer length set in ESP8266. Then actual value is decoded from bytes buffer. ● The values from TCS34725 have different range (based on the settings) than the value from analog photoresistor (0-1024). It is easier to scale the value of one side to meet the yellow LED condition under normal ambient light. ○ If initially photoresistor senses 850 and TCS34725 senses 150, you can calculate like (lux - 850) / (1024-850) * (1024) + 150 on ESP8266 side. ○ Suggested settings: TCS34725_INTEGRATIONTIME_101MS and TCS34725_GAIN_4X ■ Relevant constants in python library: https://github.com/adafruit/Adafruit_Python_TCS34725/blob/996396cd095522d788b7b1 5d20fd44e566c8464e/Adafruit_TCS34725/TCS34725.py#L77 ● Onboard LEDs on ESP8266 are OFF only when HIGH value is digitalWrite. ● Use threading to create threads or shorter socket timeout with counter to control the blink white LED. Demo Video for HW2 https://uci.yuja.com/V/Video?v=3759002&node=12858963&a=1832739861 When started, RPi should turn on the white LED and send a UDP message to ESP8266 to initiate the communication. After receiving the first UDP message from RPi, ESP8266 should flash its onboard LED every 500 ms, collect the light sensor value every 500 ms, and send the average value in the last 5 seconds back to the RPi every 2 seconds via UDP. ESP8266 prints the sliding window every time it collects a sensor value. ESP8266 also prints the average when it is time to send the average value. Whenever RPi receives a message containing the remote light reading, RPi should turn off the white LED. It will turn on the green LED if the local light value is higher, or the yellow LED if the local value is within ±20% of the remote value, or the red LED if the local value is lower than the remote value. Whenever RPi receives a message containing the remote light reading, RPi should turn off the white LED. It will turn on the green LED if the local light value is higher, or the yellow LED if the local value is within ±20% of the remote value, or the red LED if the local value is lower than the remote value. Whenever RPi receives a message containing the remote light reading, RPi should turn off the white LED. It will turn on the green LED if the local light value is higher, or the yellow LED if the local value is within ±20% of the remote value, or the red LED if the local value is lower than the remote value. If RPi hasn't received a message from ESP8266 for 5 seconds, RPi flashes the white LED on and off every 500 ms to indicate an error condition (e.g. ESP8266 is accidentally turned off). It keeps flashing until another light value is received and goes back to Step 4. If RPi hasn't received a message from ESP8266 for 5 seconds, RPi flashes the white LED on and off every 500 ms to indicate an error condition (e.g. ESP8266 is accidentally turned off). It keeps flashing until another light value is received and goes back to Step 4.
STAT3006 Assignment 4—High-Dimensional Inference Due Date: 15th November 2021 Weighting: 25% Instructions • The assignment consists of three (3) problems; Problems 1 and 2 are worth 10 Marks each, and Problem 3 is worth 5 Mark. Each Mark is equally weighted and is worth 1% of the overall course grade. • The mathematical elements of the assignment can be completed by hand, in LaTeX (prefer- ably), or in Word (or other typesetting software). The mathematical derivations and ma- nipulations should be accompanied by clear explanations in English regarding necessary information required to interpret the mathematical exposition. • Computation problems can be answered using your programming language of choice, al- though R is generally recommended, or Python if you are uncomfortable with R. As with the mathematical exposition, you may choose to typeset your answers to the problems in whatever authoring or word processing software that you wish. You should also maintain a copy of any codes that you have produced. • Computer generated plots and hand drawn graphs should be included together with the text where problems are answered. • The assignment will require four (4) files containing data, that you can can download from the Assignment 4 section on Blackboard. These files are: zip.txt, golub_genes.csv, golub_labels.csv, and prostate.csv. • Submission files should include the following (which ever applies to you): – Scans of handwritten mathematical exposition. – Typeset mathematical exposition, outputted as a pdf file. – Typeset answers to computational problems, outputted as a pdf file. – Program code/scripts that you wish to submit, outputted as a txt file. • All submission files should be labeled with your name and student number and archived together in a zip file and submitted at the TurnItIn link on Blackboard. We suggest naming using the convention: FirstName_LastName_STAT3006A4_[Problem_XX/Problem_XX_Part_YY].[FileExtension]. • As per my.uq.edu.au/information-and-services/manage-my-program/student-in tegrityand-conduct/academic-integrity-and-student-conduct, what you submit should be your own work. Even where working from sources, you should endeavour to write in your own words. You should use consistent notation throughout your assignment and define whatever is required. Problem 1 [10 Marks] Consider the data set zip.txt, which contains n = 7291 rows of data, where each row is an observation Z>i = ( Yi,X > i ) ∈ R1+q, with q = 256. Here Yi ∈ {0, 1, . . . , 9} is a label indicating the digit that is represented by the vectorized 16× 16 matrix (image) Xi ∈ Rq. Part 1 [1 Mark] Select one of the digits y ∈ {0, 1, . . . , 9} and plot m = 9 unique images with Yi = y, in the same plot, as characterized by Xi . Part 2 [2 Marks] Using all n = 7291 observations of the sample X˜n = ( X˜1, . . . , X˜n ) , where X˜i = Xi−X¯n (i ∈ [n]) and X¯n = n−1 ∑n i=1Xi, obtain a solution to the optimization problem: Fˆ, Rˆ = arg min F∈Rs×q ,R∈Rq×s n∑ i=1 ∥∥∥X˜i −RFX˜i∥∥∥2 2 , for s = 4 and report the minimum value: n∑ i=1 ∥∥∥X˜i − RˆFˆX˜i∥∥∥2 2 . Part 3 [2 Marks] Using the results from Part 2, plot the forward mappings Wˆ1, . . . , Wˆn, where Wˆi = FˆX˜i, for each i ∈ [n], colored by the labels Yi. Discuss whether there appears to be differences in the distributions of the forward mapped observations Wˆ1, . . . , Wˆn, corresponding to different values of the labels Yi. Part 4 [1 Mark] Via a spectral decomposition of the Grammian G˜ = n∑ i=1 X˜iX˜ > i report the proportion of total variance that is explained by s = 4 eigenvectors corresponding to the first s largest eigenvalues. Part 5 [2 Marks] Using all n = 7291 observations of the sample Xn = (X1, . . . ,Xn), obtain a solution θˆ =( σˆ2, µˆ, Rˆ ) to the optimization problem arg max θ logLn (θ) , where logLn (θ) = n∑ i=1 log φ ( Xi;µ,RR > + σ2Iq ) = −n 2 q log (2pi)− n 2 log ∣∣RR> + σ2Iq∣∣−−1 2 trace ([ RR> + σ2Iq ]−1 S (µ) ) , S (µ) = n−1 ∑n i=1 (Xi − µ) (Xi − µ)>, and θ = (σ2,µ,R), with σ2 > 0, µ ∈ Rq, and R ∈ Rq×s, for s = 4. Part 6 [1 Marks] Using the results from Part 5, estimate the posterior expectations of the latent variables Wi: E (Wi|Xi) = ( R>R+ σ2Is )−1 R> (Xi − µ) for each i ∈ [n], and plot the estimated posterior expectations, colored by the labels Yi. Part 7 [1 Marks] Using all n = 7291 observations of the sample Xn = (X1, . . . ,Xn), use 3-layer autoencoder with some activation function a : R → R (of your choice) to obtain an s-dimensional nonlinear dimensionality reduction Wi = F (Xi) , for each i ∈ [n] and for s = 4, where F : Rq → Rs, x 7→ (a (f1x+ c1) , . . . , a (fsx+ cs)) , for some vectors f1, . . . , fs ∈ Rq and scalars c1, . . . , cs ∈ R. Then, plot W1, . . . ,Wn, colored by the labels Yi. Problem 2 [10 Marks] Consider the data set golub_genes.csv , which contains q = 3571 rows of data corresponding observations Xi ∈ Rq (i ∈ [n]), in each of the n = 72 columns. Here, each row corresponds to the expression levels of a gene j across the n cells, corresponding to the columns. The data set golub_labels.csv then contains the corresponding label corresponding to the cell type of each of the n columns of golub_genes.csv, where the cells are either labeled as “ALL” or “AML”, where ALL stands for Acute Lymphoblastic Leukemia, and AML stands for Acute Myeloid Leukemia. For each i ∈ [n], we will write Yi = 1 if cell i is ALL and Yi = 2 if cell i is AML. Part 1 [2 Mark] Let f1 (x) = f (x|Y = 1) and f2 (x) = f (x|Y = 2) be the probability density functions of the gene expression levels for ALL and AML cells, respectively. Using an maximum mean discrepancy statistic with kernel of the form.: κg (x,y) = g (‖x− y‖22) , where g (t) = exp {−βt} for β = 2−28, and using the data X1, . . . ,Xn and Y1, . . . , Yn, (assumed to be independent and identically distributed), test the hypotheses H0 : f1 = f2 versus H0 : f1 6= f2, at the α = 0.1 significance level. That is, report the test statistic, critical value, and decision that is made. If your decisions is to not reject the null hypothesis H0, then comment on whether or not you believe that the test was powerful enough to reject the null hypothesis, based on the sample size. Part 2 [2 Mark] Let f1j (x) = f (x1|Y = 1) and f2j (x) = f (x2|Y = 2) be the marginal probability density functions of the gene expression levels of the jth gene for ALL and AML cells, respectively. Let P (f) = ∫ R xf (x) dx be the mean of univariate probability density function f : R → R≥0. For each j ∈ [q], compute a p-value Pj for a test of the hypotheses H0 :P (f1j) =P (f2j) versus H0 :P (f1j) 6=P (f2j) , using the data X1, . . . ,Xn and Y1, . . . , Yn. Plot the p-values Pq = (P1, . . . , Pq) using a his- togram. Part 3 [2 Mark] Following from Part 2, plot the empirical cumulative distribution function (ECDF) for the sample of p-values: F (p;Pq) = 1 q q∑ j=1 Jp ≤ PjK , along with the cumulative distribution function of the uniform. distribution on the domain [0, 1]. Comment on whether the distribution of p-values is sub-uniform. or not, and whether or not this observation conforms with the conclusions made in Part 1. Part 4 [2 Mark] Using the Benjamini–Hochberg and Benjamini–Yekutieli methods, identify sets of genes j ∈ [q] that are significant at the false discovery rate controlled level of αFD = 0.05. Report how many of the genes are significant under each method, and report the largest p-value that was rejected under each method. Part 5 [1 Mark] Using exploratory techniques and the samples X1, . . . ,Xn and Y1, . . . , Yn, explain whether you believe that the outcomes from either of the methods applied in Part 4 are valid by way of a discussion of the required assumptions. Part 6 [1 Mark] Prove that ∞∑ j=1 δ (min {j,m}) j (j + 1) ≤ 1, for δ (k) = (2m)−1 k (k + 1), and provide a false discovery rate step-up rejection proce- dure based on this observation. Problem 3 [5 Marks] Let (X1, Y1) , . . . , (Xn, Yn) be an independent and identically distributed sample of pairs of covari- ates and responses, where Xi ∈ Rq and Yi ∈ R, where q may be larger than n. Suppose that E [Yi|Xi = xi] = β>xi, (1) for some potentially sparse β ∈ Rq (here, we take sparse to mean that many of the coordinates βj = 0 for many j ∈ [q], where β> = (β1, . . . , βq). We wish to estimate β via the so-called elastic net-penalized least squares estimator: βˆ = arg min β∈Rq 1 2n n∑ i=1 ( Yi − β>Xi )2 + λ {‖β‖1 + ‖β‖22} , (2) for some λ ≥ 0. Part 1 [1 Mark] Argue that Problem (2) is equivalent to the problem: βˆ = arg min β∈B(γ) 1 2n n∑ i=1 ( Yi − β>Xi )2 , (3) where B (γ) = { β ∈ Rq : ‖β‖1 + ‖β‖22 ≤ γ } , for some γ > 0. Part 2 [1 Mark] Plot the set B (γ) = { β ∈ Rq : ‖β‖1 + ‖β‖22 ≤ γ } for some value of γ and discuss whether you believe that elastic net-penalized least squares estimator can be sparse. Part 3 [2 Mark] Devise an algorithm for solving either Problem 2 or Problem 3. Part 4 [1 Mark] The rows of the file prostate.csv contains n = 98 pairs of covariates Xi ∈ Rq (q = 8; in the first 8 columns) and response Yi (in the 9th column), for i ∈ [n]. Assuming that these data admit the relationship (2), compute estimates of β for these data using the elastic net-penalized least squares estimator for some increasing sequence of γ (or decreasing sequence of λ ≥ 0). Plot the trajectory of the sequence of estimates as γ increases (or λ decreases).
Department of Biobehavioral Sciences Program in Movement Sciences and Education FALL SESSION, 2025 BBSR 4070: Introduction to Psychosocial Aspects of Sports / Exercise (2-3 credits) Syllabus Course Description: The purpose of this course is to provide the student with an in-depth and comprehensive understanding of the psychological and social processes in physical activity, exercise and sport (in that order). The focus is on the key theoretical psychosocial principles that are well known to govern exercise and sport behavior, including the physical, affective (emotional), and cognitive aspects. The course explores theoretical, methodological, and applied approaches to a variety of topics including: stress, motivation, cognition, mood, emotion, perceptions of the self, mental illness, exercise adherence, self-regulation and self-control, goal setting, arousal and performance, group dynamics, coaching, and burnout. My research foci are stress (see our classic article here) and motivation (here), two major areas of inquiry; consequently, there will be a particular emphasis on these topics. Prerequisites – none, but all students should know how to use a software program similar to Excel or Sheets. Major learning objectives A. Understand processes of behavior. change to promote physically active lifestyles. B. Differentiate between sport, exercise, and physical activity psychologies (collectively, movement psychology). C. Apply movement psychology knowledge for their own condition or for another person, like a friend, family member or client (students must have a strong personal stake in the course content). D. Be able to refine and articulate a publishable research question (RQ) within the movement psychologies. E. Collect data that is research, or close to research, quality. Be able to enter data, organize, data reduce, tabulate, analyze, diagram, and interpret this data. F. Produce content that is publishable or could be publishable, in other words, can be shared with others (but may not, it is your discretion) G. Master content required for the American College of Sports Medicine exercise physiologist (EP-C) credentialing examination in the section “Exercise Counseling and Behavior. Modification” (25% of exam). H. Through all experiences and with multiple sources of evidence (see below), answer the chosen movement psychology RQ. Points: 2 or 3 (2 less requirements for those taking 2 points, including the conceptual model and article rankings assignments) Course Format: The course will consist of lecture, discussion (over Zoom and the discussion board) and some interactive activities. Personal experience will be emphasized substantially, and projects will be completed based on such experiences. Students should complete the scientific reading assignments (“lead”, “key” or “featured” articles) posted on Canvas before each class, and be prepared to discuss the material in class, on the discussion board or in a separate Word document submitted to the professor. Typical nightly schedule 5:10 – 6:00: Topic 1 6:10 – 7:00: Topic 2 and/or Activity Class dismissed Optional - 7:00 – 8:00: 1-on-1 meeting time (office hours) Please, understand that I am an Associate Adjunct and not a tenure-track faculty member. There are different requirements for office hours for adjuncts. Per state statutes and TC policy - “Adjuncts/Instructors must hold office hours of one hour for every class which they teach.” Course Resources Reading assignments will be articles selected from the scientific literature and reputable (e.g., NY Times) news media reports covering these articles. Reading assignments will be posted on Canvas. Students are responsible for all information presented in class, and other highlighted course materials - whether or not discussed in class. I typically divide these resources into 4 types. How I approach these is very flexible and will vary week to week. A. Lead/key/featured articles – Each week a few articles (or book chapters) will be selected as “featured” publications. All students are expected to know this material for an engaging in-class discussion (or later write-up if not in class). B. Secondary articles - These are articles I expect you to read the abstract and be familiar with some of the tables and figures. C. Ancillary articles - Other articles you might be interested in, or we might touch on in class, but I do not expect you to read them in their entirety. D. Other supporting documents - Might even be from magazines, newspapers or social media. Relevant to the topic, but not necessarily endorsed! These often highlight misconceptions broadcasted in popular culture.
