CSCI 2520 Data Structures and Applications Assignment Four Deadline: 23:55, May. 16, 2020 Total Marks: 100 Submission: In this Assignment, you need to answer question 1 and question 2 in one pdf file. For question 3 and 4, you need to provide .c file for each question, which can be compiled and give the correct answer, the name should be q3.c and q4.c respectively. Then compress all 4 files (one pdf file for q1 & q2 and three .c files for q3 and q4 respectively) as one zip named as your_student_id_assign4.zip and submit it via Blackboard. 1. Shortest-Path Algorithm (20 marks) Use Dijkstra’s algorithm to calculate the shortest distance from VS to all vertices and the shortest path from VS to VF. Note: Please use the table used in lecture (Shortest-Path Algorithm) to represent each step. Example: Initial Step Step 1 2. Minimum Spanning Tree (20 marks) Given an undirected graph, find the minimum spanning tree. The number of the edge connecting vertex a and vertex b is ab. Like the edge with weight 1 in the graph, its number is 02. (1) Use Prim’s Algorithm starting from vertex 0 to find the minimum spanning tree, write the number of the edge added into the minimum spanning tree in turn (if there are many edges satisfy requirement, choose the edge with minimum number). Please use the table used in lecture (Prim’s Algorithm) to represent each step. Example: Initial Step Step 1 (2) Use Kruskal’s Algorithm and write the number of the valid edge with minimum merging cost in turn (if there are many edges satisfy requirement, choose the edge with minimum number). 3. The diameter of a graph (30 marks) Definition: The distance d(u, v) between two vertices u and v is defined as the length of a shortest path from u to v. The diameter of a graph is the greatest distance between any pair of vertices. Now give you a undirected graph, get the diameter of the graph. The first line of input is the number of nodes N and edges M. Next M lines, contains three positive integers x, y, w means an undirected edge between vertex x and vertex y with length w. (The data guarantees that the graph is connected.) Input: 5 7 1 2 3 1 4 4 4 5 2 2 3 3 3 5 1 1 3 2 3 4 1 Output: 4 4. The power of the team. (30 marks) We want to build the best team to solve a problem. Now there are n great people on the waiting list. Everyone has different strengths and weaknesses. The power of the team is the sum of the strength of the teammate multiplied by the minimum weakness of the team.(Cannikin Law). Since the budget is not sufficient, we can only choose at most k people. You need to solve this problem by finding the maximum power of the team you can have.(Hint: use heap to solve it) The first line of input is n and k. (1<= k <= n <= 10000) The following two lines are the strengths and weaknesses of the n people. All the values are less than 10000. For example: Input: 5 3 1 2 3 4 5 5 4 3 2 1 Output: 18 (There are two different ways to get the answer. You can choose the 1, 2, 3 and 2, 3, 4 )
The University of Sydney Page 1 QBUS6860 Visual Data Analytics Weekly Assignment 8 Dr Demetris Christodoulou Discipline of Accounting MEAFA Research Group http://sydney.edu.au/business/research/meafa The University of Sydney Page 2 Weekly Assignment 8 o The Weekly Assignment 8 asks to investigate the changing relation over time between income per capita and life expectancy o Theory suggests that as income per capita for a country increases, there would be more investment in education, public health, technology and pro-social initiatives in that country, thus improving living conditions overall and life expectancy at birth o More specifically, the graph objective to be analysed is defined as: “The changing relation between GDP per capita and life expectancy from 1961 to 2017” Hint: think of GDP per capita as an explanatory variable that can help explain the variation in life expectancy The University of Sydney Page 3 Weekly Assignment 8 The data is available from the World Bank Open Data initiative. o The life expectancy at birth by jurisdiction is found here: https://data.worldbank.org/indicator/sp.dyn.le00.in o The GDP income per capita (in constant 2010 UDD) by jurisdiction is found here: https://data.worldbank.org/indicator/NY.GDP.PCAP.KD o These datasets contain jurisdiction-level observations for life expectancy and GDP per capita o From these links you can download the CSV or Excel files – look for these links: o You are required to manage the data to prepare it for analysis. You are also required to validate the data as in every assignment The University of Sydney Page 4 Weekly Assignment 8 o We do not know in advance the answer to the graph objective question and we must investigate the changing relation between the two variables using a visual mining approach. o Thus, you are required to use your knowledge from Week 9 to analyse the graph objective using appropriate visual mining methods. Hint: not all visual methods are useful for this assignment. o Do not use any transformations. The data must be analysed exactly as provided by the World Bank links in their nominal values The University of Sydney Page 5 Weekly Assignment 8 o You are required to produce data just one graph that will show the changing relation between the two variables over time. This data graph must qualify as a high-quality data graph as discussed in weeks 1-6. o The graph objective is multidimensional involving observations on jurisdictions, years, GDP per capita and life expectancy. It is up to you how to design the graph, but you may want to consider using interactive features or using the motion retinal variable o You are not required to do any particular research on this research question, but you may want to do so if it helps you understand the question better The University of Sydney Page 6 Weekly Assignment 8 o You will be evaluated on the quality of data management, data validation, and the quality of the data graph o You will be evaluated on the application of appropriate visual data mining methods o You need to submit the Tableau workbook (.twbx), a Word or PDF report, and the managed Excel or CSV dataset
Module Code MAT00033I/MAT00035I BA, BSc and MMath Examinations 2018/9 Department: Mathematics Title of Exam: Probability and Statistics/Statistics option – Statistical Inference II and Linear Models Time Allowed: 3 hours Allocation of Marks: Each question carries 30 marks. The marking scheme shown on each question is indicative only. Instructions for Candidates: This paper contains five questions. Answer all questions. The first two pages of the question booklet contains tables of probabilities and quantiles you may use in your answers. Please write your answers in ink; pencil is acceptable for graphs and diagrams. Do not use red ink. Materials Supplied: Answer booklet Calculator Do not write on this booklet before the exam begins. Do not turn over this page until instructed to do so by an invigilator. Page 1 (of 9) MAT00033I/MAT00035I The following four tables contain quantile information for use in answering exam questions. All probabilities refer to the lower tail of distributions, i.e. the probability mass to the left of particular quantiles. p=0.5 p=0.9 p=0.95 p=0.975 n=7 0 1.41 1.89 2.36 n=8 0 1.40 1.86 2.31 n=9 0 1.38 1.83 2.26 Table 1: Selected quantiles for the t−distribution with n degrees of freedom. e.g. P (t7 < 1.40) = 0.9. p=0.5 p=0.9 p=0.95 p=0.975 0 1.28 1.64 1.96 Table 2: Selected quantiles for the unit normal distribution N(0, 1). e.g. P (z < 1.28) = 0.9. p= 0.9 p= 0.95 p= 0.975 k= 6 10.64 12.59 14.45 k= 7 12.02 14.07 16.01 k= 8 13.36 15.51 17.53 k= 9 14.68 16.92 19.02 k= 10 15.99 18.31 20.48 k= 11 17.28 19.68 21.92 k= 12 18.55 21.03 23.34 Table 3: Selected quantiles for the χ2-distribution with k degrees of freedom. e.g. P (χ26 < 10.64) = 0.9. Page 2 (of 9) MAT00033I/MAT00035I λ =1 λ =2 λ =3 λ =4 λ =5 P(X≤ 6 ) 0.89 0.76 0.61 0.45 0.31 P(X≤ 7 ) 0.95 0.87 0.74 0.60 0.45 P(X≤ 8 ) 0.98 0.93 0.85 0.73 0.59 P(X≤ 9 ) 0.99 0.97 0.92 0.83 0.72 P(X≤ 10 ) 1.00 0.99 0.96 0.90 0.82 P(X≤ 11 ) 1.00 0.99 0.98 0.95 0.89 P(X≤ 12 ) 1.00 1.00 0.99 0.97 0.94 P(X≤ 13 ) 1.00 1.00 1.00 0.99 0.97 P(X≤ 14 ) 1.00 1.00 1.00 0.99 0.98 P(X≤ 15 ) 1.00 1.00 1.00 1.00 0.99 P(X≤ 16 ) 1.00 1.00 1.00 1.00 1.00 Table 4: Values of the cumulative mass function for Poisson distributions with rate param- eters λ = 1, . . . , 5. e.g. P (X ≤ 6 | X ∼ Poisson(λ = 1)) = 0.89. Page 3 (of 9) Turn over MAT00033I/MAT00035I 1 (of 5). Body Mass Index (BMI) is used to measure a person’s weight relative to their height. Medics from the UK’s National Health Service want to estimate the average BMI of all the country’s residents. They provide you with the following data and summary statistics, and ask you for advice. 18.87 22.92 17.82 29.98 23.65 17.9 24.44 25.69 Table 5: BMI measurements in Kg/m2 for n = 8 individuals. x¯ = n−1 n∑ i=1 xi = 22.66, σˆ 2 = (n− 1)−1 n∑ i=1 (xi − x¯)2 = 18.20. You suggest that a confidence interval would be a more informative estimate than just a single number, and you start to explain what a confidence interval is. (a) (i) Explain the difference between the level and the coverage of a confidence interval.  (ii) For a Frequentist statistician the probability of an event corresponds to the fraction of times the event occurs in a long series of trials. In the context of the confidence interval for average BMI and its probabilistic behavior, what would constitute a trial?  (b) (i) Clearly stating all relevant statistical assumptions, derive a confidence interval with level 1 − α = 0.95 given the extra assumption that the estimated population variance, σˆ2, is the true population variance.  (ii) Derive another confidence interval with level 1 − α = 0.95 without the assumption that the estimated population variance is the true population variance.  (iii) For the confidence interval computed in part (b)(i), how many measure- ments would have been needed to achieve a confidence interval with width less than 1 Kg/m2?  (c) You find out that the measurements you are analyzing are collected from pa- tients that have visited hospital in the last year. How might this affect the validity of the estimate? Which of the statistical assumptions may have been violated?  Page 4 (of 9) MAT00033I/MAT00035I 2 (of 5). Imagine a country’s legal system is overwhelmed with cases to make judgment on. The government decides to produce an algorithm for deciding whether or not a suspect is innocent of a crime based on data collected by the security services. The algorithm performs a statistical hypothesis test. (a) (i) Describe in words appropriate hypotheses for the algorithm to test.  (ii) Describe the two different types of error that the algorithm could make. Describe how the terms size, significance and power relate to these er- rors.  (iii) Consider the case in which the hypothesis test leads to the decision not to convict a suspect. Strictly speaking, what should we conclude about the suspect’s innocence and about the evidence collected by the security services?  (b) The data from the security services consist of counts of the number of crime scenes a suspect was seen at over the past year. It is assumed that the number of crime scenes a totally innocent citizen is seen at (just by coincidence) is well described by a Poisson distribution with rate parameter λ = 3. (i) Describe appropriate hypotheses for the test, referring to both the suspect and the count data.  (ii) Derive a rejection rule for the test so that it is significant at level α = 0.01.  (iii) A particular suspect has been seen at 12 crime scenes. Does your test classify them as guilty?  (iv) Compute a p-value for the test and explain how its value relates to the observed count data.  Page 5 (of 9) Turn over MAT00033I/MAT00035I 3 (of 5). You are asked by a colleague at the medical school to help interpret a linear model they have fitted using the computer program R. (a) In lectures we looked at some ways to score linear models (i) For what behavior were models rewarded?  (ii) For what properties were the models punished?  (iii) The R2 statistic could be used to score a linear model, it also played a key part in ANOVA calculations. Describe in words what the R2 statistic quantifies, and give a formula for computing it in terms of the mean response value y¯, the individual response values yi, and the model’s fitted values yˆi i = 1, . . . , n.  (b) R has also performed an ANOVA for the model but your colleague does not understand the results. (i) The model’s response variable is the age of an individual at death and the covariates measure aspects of their lifestyle. Why would the medic be interested in the ANOVA procedure?  (ii) Each row of the ANOVA table corresponds to a statistical hypothesis test. What are the precise assumptions under which the tests are valid and what are the hypotheses being tested?  (iii) What is the role of the F-distribution in the ANOVA procedure? How are the parameters for the distribution calculated for each test?  Page 6 (of 9) continued on next page continued from previous page MAT00033I/MAT00035I 3 (of 5) cont. (c) Your colleague shows you the ANOVA table Analysis of Variance Table Response: y Df Sum Sq Mean Sq F value Pr(>F) x_1 1 3.0696 3.0696 12.7001 0.0007317 *** x_2 1 6.1795 6.1795 25.5665 4.437e-06 *** x_3 1 0.3129 0.3129 1.2946 0.2597951 x_4 1 1.5506 ???? ???? 0.0139934 * Residuals 59 14.2604 ???? — Signif. codes: 0 *** 0.001 ** 0.01 * 0.05 . 0.1 1 (i) Show how the estimated variance for the model errors can be computed from values in the ANOVA table. Hint: the estimated variance for the model errors is 0.2417 (to 4 d.p.).  (ii) Show how the R2 statistic for the full model can be computed from val- ues in the ANOVA table. Hint: the R2 statistic is 0.4379 (to 4 d.p.).  (iii) Fill in the three missing cells (currently filled with ????) of the ANOVA table.  Page 7 (of 9) Turn over MAT00033I/MAT00035I 4 (of 5). A statistician is defending her linear model, and predictions consistent with it. (a) Describe in words, in summation notation and in vector notation what is meant by the model’s sum of squ
ared residuals (SSE) for a linear model with regression coefficient vector β˜.  (b) Write down the formula for βˆ, the least-squares estimator for the regression coefficients, and describe the way in which it is optimal.  (c) Suppose that you are using the least-squares estimator βˆ to predict previously observed response values and that your colleague is using a different estima- tor βˆ + δ. (i) Show that the difference in the sums of squares of errors can be written as SSE(βˆ + δ)− SSE(βˆ) = −2(y −Xβˆ)TXδ + δTXTXδ.  (ii) If δTXTXδ is non-negative then SSE(βˆ + δ)− SSE(βˆ) ≥ −2(y −Xβˆ)TXδ. Explain how you know δTXTXδ must be non-negative.  (iii) Show that (y −Xβˆ)TX = 0.  (d) You have now shown that SSE(βˆ + δ)− SSE(βˆ) ≥ 0 for any δ. Explain what this means if you and your colleague were to use the previously observed data to test your models. Can we prove that the least- squares estimates will do better on unobserved data in the future?  Page 8 (of 9) MAT00033I/MAT00035I 5 (of 5). Staff in the mathematics department are looking at the relationship between stu- dents’ A-level grades and their degree classifications. Aggregated count data for n = 400 graduates are given in Table 6. For the purposes of this question we will refer to the groupings of grades as grade categories. 3rd 2:2 2:1 1st F-E 3 12 15 10 C-D 9 26 41 6 B-A 13 64 142 59 Table 6: Numbers of students achieving particular A-level grades and degree classifications. (a) (i) Estimate the marginal probabilities for a student to fall into each A-level category, and the marginal probabilities of falling into each degree cate- gory.  (ii) Given that each student’s A-level grade and degree classification are probabilistically independent, estimate the number of students achiev- ing each combination of A-level grade and degree classification.  (iii) Clearly explaining all steps, test the hypothesis at significance level α = 0.05 that the degree classifications are independent of the A-level grades. To save time on routine calculations, you can assume that the relevant test statistic takes value 15.12. (You are not expected to calculate a p-value for this test).  (b) Your colleague suggests that you merge the F-E and C-D categories of A-level results and repeat the test. (i) Why might your colleague make this suggestion?  (ii) Now that the some categories are merged there are aspects of the null hy- pothesis that are no longer being tested (e.g. if getting an F-E rather than a C-D grade has an effect on degree classification). Without performing any formal calculations, what can you say about the relative power of the test with the merged cells?  (iii) Describe a hypothesis test that is guaranteed to reject the null hypothesis every time the null is false. State the power of this test.  (iv) Your colleague is experimenting with different tests. She constructs one test with significance 0.05 and a second test with significance 0.01. The second test is a likelihood ratio test. What can the Neyman-Pearson lemma tell her about the relative power of the tests, and why?  Page 9 (of 9) End of examination. SOLUTIONS: MAT00033I/MAT00035I 1. (a) (i) The coverage is the probability that the computed confidence interval will contain the true numerical value of the quantity we are estimating. The level is a lower bound on the coverage. 5 Marks (ii) The coverage is a probability that corresponds to the proportion of re- peated experiments producing data from which confidence intervals containing the true parameter are calculated. In this case repeated ex- periments/trials would involve randomly sampling new sets of people from the population and measuring their BMI. 5 Marks (b) (i) We begin by assuming that the measurements are well described as an iid sample from a Normal distribution with mean µ and variance σ2, i.e. the finite population of BMI measurements for all residents is approximated by the infinite population of possible values that can be taken by the random variables. Since the mean of a set of normal random variables is also normal and since the expectation and variance of the mean are µ and σ2/n, it follows that X¯ ∼ N(µ, σ2/n)⇔ t(X) := n 1/2(X¯ − µ) σ ∼ N(0, 1). Since the quantity t(X) is unit normal we can compute the probability of it falling inside a particular interval using pre-computed quantiles. We proceed to rearrange the inequalities that define the interval to derive the formula for our confidence interval 1− α = P [ zα/2 ≤ n 1/2(X¯ − µ) σ ≤ z1−α/2 ] = P [ X¯ − n−1/2σz1−α/2 ≤ µ ≤ X¯ − n−1/2σzα/2 ] . Plugging in the values x¯ = 22.66, σ2 = σˆ2 = 18.2, n = 8, z1−α/2 = −zα/2 = 1.96 we arrive at the interval R(X) = [ 22.66− √ 18.2/8× 1.96, 22.66 + √ 18.2/8× 1.96 ] = [19.70, 25.62] . 5 Marks (ii) When the same distributional assumptions hold but the population vari- ance is estimated from the data the statistic t(X) := n1/2(X¯ − µ) σˆ ∼ tn−1 11 SOLUTIONS: MAT00033I/MAT00035I follows a t-distribution. The same algebraic manipulations performed for the previous question now lead us to the confidence interval R(X) = [ x¯− √ σˆ2/n× t1−α/2,n−1, 22.66 + √ σˆ2/n× t1−α/2,n−1 ] = [ 2.66− √ 18.2/8× 2.36, 22.66 + √ 18.2/8× 2.36 ] = [19.09, 26.23] . 5 Marks (iii) The width of the first confidence interval is 2n−1/2σz1−α/2. For this to be less than one we require 2n−1/2σz1−α/2 < 1, ⇔ (2σz1−α/2)2 < n ⇔ 279.72 < n. This implies that we would need to measure at least 280 people to pro- duce such a confidence interval. 5 Marks (c) This new finding undermines the assumption that the measured BMIs are iid samples from the total UK population. More specifically, we may sus- pect that the subpopulation of people visiting hospital in the last year are systematically different from the total population. This might mean that the mean of the subpopulation sampled from is not the same as the mean of the total population, which is what we are trying to estimate. 5 Marks Remarks. Standard confidence interval material was covered extensively in lec- tures and in homeworks. TD2 is tested here when the students look up normal quantiles. Total: 30 Marks 2. (a) (i) The natural null hypothesis is that the suspect is innocent, the corre- sponding alternative hypothesis is that the suspect is guilty. 2 Marks (ii) The algorithm/test could reject the null hypothesis when the null hy- pothesis is true. We called this type I error. The algorithm could also fail to reject the null hypothesis when the null hypothesis is false. We called this type II error. 4 Marks The size of a test is the probability of making a type I error, the sig- nificance is an upper bound on the size. The power is one minus the 12 SOLUTIONS: MAT00033I/MAT00035I probability of making a type II error. 4 Marks (iii) The theory for statistical hypothesis testing makes clear that failing to reject the null hypothesis is not the same as saying that the null hypoth- esis is true, i.e. failing to show the suspect is guilty is not the same as saying he is innocent. The test is really a test of the evidence: the test asks whether the evidence is sufficient to convince us of the suspect’s guilt. 5 Marks (b) (i) As suggested in the question, we will assume that the number of times an innocent citizen is seen an a crime scene is a Poisson random variable with rate parameter λ = 3. We will also assume that the number of times a criminal is seen at a crime scene is Poisson distributed with rate parameter λ1 > 3, so that the expected count for a criminal is higher than that for an innocent citizen. Denoting the count as X , we write H0 : X ∼ Poisson(λ = 3) vs. H1 : X ∼ Poisson(λ = λ1 > 3). 4 Marks (ii) A sensible rejection rule would reject the ‘innocent’ hypothesis (H0) when the count for a suspect exceeds some critical value denoted c. For the test to have significance α = 0.01 we require that the probability of rejecting H0 when H0 is true is smaller than α. P [X ≥ c : H0] = 1− P [X ≤ c
− 1 : H0] ≤ α, ⇔1− α ≤ P [X ≤ c− 1 : H0] . From the table at the front of the exam booklet we can see that this state- ment holds true for c−1 = 12, 13, . . .. The lowest critical value (leading to the most powerful test) is c = 13. Explicitly, our rejection rule be- comes: ‘Reject the hypothesis that the suspect is innocent if he is seen at 13 or more crime scenes in the past year’. 5 Marks (iii) A suspect seen at 12 crime scenes would not trigger the rejection rule. We do not reject the ‘innocent’ hypothesis. 1 Mark (iv) The p-value is the probability that new data distributed according to the specifications of the null hypothesis would take a value even more ex- treme than the value we have just observed, i.e. p = P [X ≥ 12 : H0] = 1− P [X ≤ 11 : H0] = 1− 0.98 = 0.02 5 Marks 13 SOLUTIONS: MAT00033I/MAT00035I Remarks. A similar question, taking from Dekking et. al., was looked at in a revision class towards the end of term. Question is relevant to TD1 and TD2. Total: 30 Marks 3. (a) (i) The model scores we looked at in lectures rewarded models which did well at predicting previous observations having been optimized to fit those same observations. In practice this was quantified by the maximum value of the likelihood for the model parameters. 3 Marks (ii) The models were punished if they had many parameters, or degrees of freedom. 3 Marks (iii) The R2 statistic arises as the fraction of the variance of the response variable that can be explained by the model. It is computed as R2 = n−1 ∑n i=1(yˆi − y¯)2 n−1 ∑n i=1(yi − y¯)2 . 4 Marks (b) (i) The medic would be interested in the ANOVA because it will help them identify covariates that are useful for predicting the age at which at individual will die. 3 Marks (ii) The ANOVA procedure assumes that the model error terms are iid nor- mal. We also need to provide an order in which the coefficients for co- variates are to be tested. Given such an order, row k contains information relevant to the test between H0 : βk = 0 ∩ βj 6= 0, j = 1, . . . , k − 1, H1 : βk 6= 0 ∩ βj 6= 0, j = 1, . . . , k − 1, i.e. we test the null hypothesis that the kth coefficient is zero against the alternative hypothesis that it is non-zero, where both hypotheses assume that preceding coefficients are non-zero. 4 Marks (iii) The distributions of the test statistics for each test/row are F-distributions given the respective null hypotheses are true. We use quantiles of these distributions to calculate critical values for the tests. The F-distributions are parameterized by two degrees of freedom: one relating to the num- ber of degrees of freedom in the part of the model being tested, the other relating to the number of degrees of freedom for error (given the full model). We denoted these quantities pk and n− p in lectures. 3 Marks 14 SOLUTIONS: MAT00033I/MAT00035I (c) (i) The unbiased estimate for the variance of the residuals can be computed by dividing the sum of squares for the residuals by the number of de- grees of freedom for them. Both of these quantities can be found in the ANOVA table. σˆ2 = 1 n− p n∑ i=1 (yi − yˆi)2 = Sum of squares of residuals degrees of freedom for residuals = 14.2604 59 =0.2417 3 Marks (ii) The R2 statistic is computed by dividing the sum of squares attributable to the model by the total sum of squares. The former is the sum of the sums of squares attributable to each covariate. The latter is the sum of the sums of squares for the the covariates plus the sum of squares attributable to the errors R2 = Sum of squares of fitted values Total sum of squares = 3.0696 + 6.1795 + 0.3129 + 1.5506 3.0696 + 6.1795 + 0.3129 + 1.5506 + 14.2604 =0.438. 3 Marks (iii) The missing values are Mean Sq4 = Sum Sq4 Df4 = 1.5506 1 = 1.5506, Mean Sqresid = Sum Sqresid Dfresid = 0.2417 (which we have already computed), and F = Mean Sq4 Mean Sqresid = 1.5506 0.2417 = 6.4154. 15 SOLUTIONS: MAT00033I/MAT00035I The completed table is as follows Analysis of Variance Table Response: y Df Sum Sq Mean Sq F value Pr(>F) x_1 1 3.0696 3.0696 12.7001 0.0007317 *** x_2 1 6.1795 6.1795 25.5665 4.437e-06 *** x_3 1 0.3129 0.3129 1.2946 0.2597951 x_4 1 1.5506 1.5506 6.4153 0.0139934 * Residuals 59 14.2604 0.2417 — Signif. codes: 0 *** 0.001 ** 0.01 * 0.05 . 0.1 1 4 Marks Remarks. The ANOVA material tested here is routine. The question requires students to have remembered the meaning and structure of ANOVA calculation without asking for many calculations. Total: 30 Marks 4. (a) The SSE is the sum of squared differences between the model’s predic- tions for data quantities and the values for those quantities that are actu- ally observed. We write this formally as SSE(β˜) = ∑ (yi − xTi β˜)2 = (y −Xβ˜)T (y −Xβ˜). 5 Marks (b) The OLS estimate for the true vector of regression coefficients is βˆ = (XTX)−1XTy. The estimate is optimal insofar as minimizing the SSE βˆ = argminβ˜ ( SSE(β˜) ) . . 5 Marks 16 SOLUTIONS: MAT00033I/MAT00035I (c) (i) Using the vector notation, the difference between the two SSEs is ∆SSE =SSE(βˆ + δ)− SSE(βˆ) =(y −X(βˆ + δ))T (y −X(βˆ + δ)) − (y −Xβˆ)T (y −Xβˆ) =((y −Xβˆ)−Xδ)T ((y −Xβˆ)−Xδ) − (y −Xβˆ)T (y −Xβˆ) =(((( (((( ((( (y −Xβˆ)T (y −Xβˆ)− 2(y −Xβˆ)TXδ + (Xδ)T (Xδ) −((((((( (((( (y −Xβˆ)T (y −Xβˆ) =− 2(y −Xβˆ)TXδ + (Xδ)T (Xδ) 5 Marks (ii) Xδ is a vector of length n just like yˆ = Xβˆ is. The product δTXTXδ − (Xδ)TXδ is the squared modulus of this vector, which cannot be a neg- ative quantity. Equivalently, we can write (Xδ)TXδ = n∑ i=1 (Xδ)2i and see that the product is a sum of squared (real) quantities. 5 Marks (iii) (y −Xβˆ)TX =(y −X(XTX)−1XTy)TX =(yT − yTX(XTX)−1XT )X =yT (X −X(XTX)−1XTX) =yT (X −X) =yT0 = 0 5 Marks (d) The optimality result means that if we went back and tried to predict the previously observed data with our linear model, the model using the OLS es- timates would achieve a smaller sum of squared residuals. We cannot prove that the OLS estimates will lead to a smaller sum of squared residuals for unobserved data in the future. 5 Marks Remarks. The question tests TD3. Final question is more open-ended than most. Total: 30 Marks 17 SOLUTIONS: MAT00033I/MAT00035I 5. (a) (i) The marginal probabilities for the A-level grade categories are (0.100, 0.205, 0.695). The marginal probabilities for the degree classifications are (0.0625, 0.2550, 0.4950, 0.1875). 3 Marks (ii) The joint probabilities consistent with the assumption of independence follow from multiplying the marginal probabilities. The expected counts follow from multiplying the probabilities by n = 400. Doing this, we arrive at the figures 3rd 2:2 2:1 1st F-E 2.50 10.20 19.80 7.50 C-D 5.12 20.91 40.59 15.38 B-A 17.38 70.89 137.61 52.12 3 Marks (iii) Our assumptions are that, collectively, the counts are well described by a multinomial distribution. Pearson’s χ2-test further assumes that the test statistic t(O) = ∑ i,j (Oij − Eij)2 Eij is approximately χ2-distributed with (ni − 1)(nj − 1) degrees of free- dom. Our test hypotheses concern the probabilities of any individual falling into a particular pair of categories. More specifically, our null hy- pothesis states that all the joint probabilities pij are the products of the marginal probabilities pi,· and p·,j . Our alternative hypothesis states that this relationship is violated for at least one pair of categories, i.e. H0 : pij = pi,·p·,j ∀i, j, H1 : ∃(i, j) such that pij 6= pi,·p·,j. The test’s rejection rule tells us to reject the null hypothesis when the test statistic exceeds a critical value c. The result here is that t(O) = 15.12 > c = χ22×3 = 12.59 so we do reject the null hypothesis. 8 Marks (b) (i) Pearson’s χ2-test is based on approximations that improve as the ex- pected counts for every category increase. When the expected counts are low we cannot be as confident that the test is well calibrated in terms of its significance. 4 Marks 18 SOLUTIONS: MAT00033I/MAT00035I (ii) When we are unable to test an
d criticize the null hypothesis in as much detail it becomes harder to reject the null when it is false. It is thus harder to avoid type II error. We would therefore expect the test with the merged categories to have less power than the first test. 4 Marks (iii) A test that rejects the null no matter the values taken by the data will al- ways reject the null, so will always reject the null when the null is false. Its power is 1. 4 Marks (iv) The Neyman-Pearson lemma cannot help your colleague here. It would be able to tell her that the likelihood ratio is more powerful if the other test had the same significance level, but it doesn’t. 4 Marks Remarks. Opportunities to access TDs 1 and 2. Questions (c)(ii) and (c)(iv) require genuine understanding of results covered in lectures. Total: 30 Marks 19
CS 113 Assignment Working with classes and objects (reading files, instance methods) Due on Friday, May 1 at 4:00 pm. Automatic extensions to May 7 if needed. Part I: In the first part of this assignment, you will create a BaseballPlayer class which will represent a baseball player on a team. 1. Create a new directory called baseball. In that directory, create a BaseballPlayer class with the following instance variables: int number; String firstName; String lastName; String position; char battingArm; char throwingArm; int weight; int height; // height in inches String birthDate; // in format mm/dd/yyyy String birth1; String birth2; Be sure that all the variables have private access modifiers. 2. Create a constructor for the BaseballPlayer object which takes parameters corresponding to each of the above instance fields. 3. Create set and get methods for each of the above instance fields. 4. Create a method called getFullName which returns a String which consists of the firstName followed by the lastName, with a space between. 5. Create a method called getHanded which returns a String which consists of the battingArm, followed by a slash, followed the throwingArm, like this: B/R (this means both hands to hit (switch-hitter) and right hand to throw) 6. Create a method called getBirthplace which returns a String which consists of the contents of the String birth1, followed by a comma, followed by a space, followed by the contents of the String birth2 7. Create a method called getHeightString which returns a String which shows the height in feet and inches, like this: 6’2″ . The height field is in inches. Hint: to insert a quote mark inside a string, escape it with a backslash. 8. Create a method called getBirthYear which returns an int that is equal to the year listed in the birthdate string (yyyy). 9. Create a method called getAge which returns an int that is the difference between 2019 and the birthYear (hint: call getBirthYear) 10. Create a method called toString which returns a String consisting of the number, the full name (use the getFullName method), the position, the batting/throwing arm (use the getHanded method), the height (use the getHeightString method), the weight, the age, and the birthplace (use getBirthplace method). Format your results so they look like this: 5 Nick Williams RF L/L 6’3″ 195Lbs 26yrs Galveston, Texas 11. To debug your BaseballPlayer.java file, I recommend that you write a small client class which tests each of your methods to ensure that they work as designed. Part 2: In this part of the assignment, you will write a client a program to use and manipulate your BaseballPlayer class 1. Download the file phillies2019.txt into the same directory as your BaseballPlayer.java file. This .txt file contains a list of records containing the Spring 2019 roster for the Philadelphia Phillies, the local baseball team. There are exactly 29 lines in the file; the first line is a header showing the fields in each record, and the rest of the lines are the 28 players on the Spring 2019 roster. The first two lines of phillies2019.txt look like this: Number,Firstname,lastname,Position,Bats,Throws,wt(lbs),height(in),birthdate,birth1,birth2 23,Aaron,Altherr,RF,R,R,223,77,1/14/1991,Landstuhl,Germany The fields in each record are comma delimited. 2. Create a new client class with a filename BaseballRoster.java which contains a main method to run the program. The BaseballRoster program should do the following: (1) Create an array of BaseballPlayer objects to hold all the players in the roster. (2) Open the phillies2019.txt file and read in each line, using a Scanner (note that you will want to skip the first line). Use a try-catch block around the code that opens the file; if a FileNotFound Exception is caught, your code should issue a sensible error message and exit (call System.exit(-1)). (3) Within each line, use the “split” method that we learned in class to break the line into its comma-separated components, and then pass each component (after converting it to the proper type, if necessary), to the BaseballPlayer constructor and put the new object in the array of baseball players. Take careful note of the type of each parameter in the constructor, and be sure to pass that field as that type, as the split method turns everything into separate String values. For example, for the number field, it expects an int, and for the battingArm field, it expects a parameter of the char type. You can use the Integer.parseInt method to convert a String to an int type; to convert a String to a char, you may simply pass it to the charAt method (e.g. values.charAt(0)). (4) Once the array is created, use a loop (either a regular for loop or an enhanced for loop) to print out a roster of all the players (see the example printout). (5) Create a search function in the form of a loop which prompts the user for whether they wish to search for player number, player name (either last or first), or player birthplace (state or, if not US, country). Your function should produce a listing of all players that meet those criteria. If there are no matches, issue an appropriate error message and ask again. Continue to loop until the user presses 0 (see the example printout). Challenge: Create another version of BaseballRoster (call it BaseballRoster2.java) which uses an ArrayList, rather than an array, to store the BaseballPlayer objects. How to hand in your assignment: Upload your BaseballPlayer.java, BaseballRoster.java, and, if you chose to do the challenge problem, the BaseballRoster.java files, along with your reflection. The “official” due date for this assignment is May 1, but, since this is part of your final exam grade, you may have an “automatic extension” to 11:59 pm on May 7 if needed. The Reflection must include: a. Name and email b. What was/were the most difficult part(s) of this assignment, if anything? c. What did you like about this assignment, if anything? d. What did you particularly dislike about this assignment, if anything? e. How much time, approximately, did you spend coding on this assignment? f. Any other comments about the assignment? I hope you enjoy this assignment! Thank you for being such a great class! Example runs: java BaseballRoster Player Roster: 23 Aaron Altherr RF R/R 6’5″ 223Lbs 28yrs Landstuhl, Germany 52 Jose Alvarez P L/L 5’11” 190Lbs 30yrs Barcelona, Venezuela 64 Victor Arano P R/R 6’2″ 220Lbs 24yrs Cosamaloapan, Mexico 49 Jake Arrieta P R/R 6’4″ 225Lbs 33yrs Farmington, Missouri 58 Seranthony Dominguez P R/R 6’1″ 185Lbs 25yrs Esperanza, Dominican Republic 56 Zach Eflin P R/R 6’6″ 211Lbs 25yrs Orlando, Florida 48 Jerad Eickhoff P R/R 6’4″ 244Lbs 29yrs Evansville, Indiana 7 Maikel Franco 3B R/R 6’1″ 229Lbs 27yrs Azua, Dominican Republic 9 Phil Gosselin 2B R/R 6’1″ 200Lbs 31yrs West Chester, Pennsylvania 3 Bryce Harper RF L/R 6’3″ 220Lbs 27yrs Las Vegas, Nevada 16 Cesar Hernandez 2B B/R 5’10” 167Lbs 29yrs Valencia, Venezuela 37 Odubel Herrera CF L/R 5’11” 206Lbs 28yrs Zulia, Venezuela 17 Rhys Hoskins LF R/R 6’4″ 240Lbs 26yrs Sacramento, California 96 Tommy Hunter P R/R 6’3″ 250Lbs 33yrs Indianapolis, Indiana 4 Scott Kingery SS R/R 5’10” 180Lbs 25yrs Phoenix, Arizona 15 Andrew Knapp C B/R 6’1″ 204Lbs 28yrs Roseville, California 22 Andrew McCutchen RF R/R 5’11” 195Lbs 33yrs Fort Meade, Florida 46 Adam Morgan P L/L 6’1″ 37Lbs 29yrs Tampa, Florida 50 Hector Neris P R/R 6’2″ 227Lbs 30yrs Villa Altagracia, Dominican Republic 93 Pat Neshek P B/R 6’3″ 221Lbs 39yrs Madison, Wisconsin 12 Juan Nicasio P R/R 6’4″ 252Lbs 33yrs San Francisco de Macoris, Dominican Republic 27 Aaron Nola P R/R 6’2″ 200Lbs 26yrs Baton Rouge, Louisiana 24 Roman Quinn CF B/R 5’10” 170Lbs 26yrs Port St. Joe, Florida 10 J.T. Realmuto C R/R 5’10” 213Lbs 28yrs Del City, Oklahoma 30 David Robertson P R/R 5’11” 195Lbs 34yrs Birmingham, Alabama 2 Jean Segura SS R/R 5’10” 220Lbs 29yrs San Juan, Dominican Republic 21 Vince Velasquez P R/R 6’3″ 203Lbs 27yrs Mon
tclair, California 5 Nick Williams RF L/L 6’3″ 195Lbs 26yrs Galveston, Texas Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 1 Enter the number to search: 37 37 Odubel Herrera CF L/R 5’11” 206Lbs 28yrs Zulia, Venezuela Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 1 Enter the number to search: 52 52 Jose Alvarez P L/L 5’11” 190Lbs 30yrs Barcelona, Venezuela Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 1 Enter the number to search: 5 5 Nick Williams RF L/L 6’3″ 195Lbs 26yrs Galveston, Texas Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 1 Enter the number to search: 99 Sorry, no matches! Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 2 Enter the name to search: Vince 21 Vince Velasquez P R/R 6’3″ 203Lbs 27yrs Montclair, California Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 2 Enter the name to search: Maria Sorry, no matches! Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 2 Enter the name to search: Andrew 15 Andrew Knapp C B/R 6’1″ 204Lbs 28yrs Roseville, California 22 Andrew McCutchen RF R/R 5’11” 195Lbs 33yrs Fort Meade, Florida Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 3 Enter the state or (if not US) country: Pennsylvania 9 Phil Gosselin 2B R/R 6’1″ 200Lbs 31yrs West Chester, Pennsylvania Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 3 Enter the state or (if not US) country: Venezuela 52 Jose Alvarez P L/L 5’11” 190Lbs 30yrs Barcelona, Venezuela 16 Cesar Hernandez 2B B/R 5’10” 167Lbs 29yrs Valencia, Venezuela 37 Odúbel Herrera CF L/R 5’11” 206Lbs 28yrs Zulia, Venezuela Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 3 Enter the state or (if not US) country: Dominican Republic 58 Seranthony Dominguez P R/R 6’1″ 185Lbs 25yrs Esperanza, Dominican Republic 7 Maikel Franco 3B R/R 6’1″ 229Lbs 27yrs Azua, Dominican Republic 50 Hector Neris P R/R 6’2″ 227Lbs 30yrs Villa Altagracia, Dominican Republic 12 Juan Nicasio P R/R 6’4″ 252Lbs 33yrs San Francisco de Macoris, Dominican Republic 2 Jean Segura SS R/R 5’10” 220Lbs 29yrs San Juan, Dominican Republic Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 3 Enter the state or (if not US) country: Australia Sorry, no matches! Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 3 Enter the state or (if not US) country: Sorry, no matches! Enter 1 to search on player number, 2 to search on name, 3 to search on player birthplace, or 0 to quit: 0 Goodbye!
CS520: Quantitative Design and Analysis Homework 1 RULES 1. You are to work individually on the homework. Cooperation is not allowed. 2. Points are assigned to each question to reflect the amount of work involved or its level of difficulty. Your homework score will be calculated as: score = ଵ௫௨ ௧௦ ൈ . HOMEWORK PROBLEMS 1. Amdahl’s law [5pt] Assume you have a sequential program that you want to run on a parallel computers. Suppose that 90% of the original sequential execution time is parallelizable with a perfect speedup (i.e. n ൈ as fast when executed on n processors), and the remaining 10% is not parallelizable. What is the minimum number of processors needed to yield a total/overall speedup of 5? 2. Amdahl’s law [15pt] Suppose that the typical workload that runs on your processor consists of programs with 50% floating‐ point instructions, 30% memory instructions (loads and stores), and 20% others (integer, logic, etc.). Suppose that each floating‐point instruction takes 2 cycles to compute, memory instruction takes 4 cycles to compute, and other instruction takes 1 cycle to compute. For the next generation of your processor, you are evaluating between design A which improves floating‐point instruction performance by 40%, and design B which improves memory instruction performance by 35%. Design A increases the processor die area by 10% while Design B increases the processor die area by 12%. (a) Compute the overall speedups for design A and design B over the base processor design. Which design (A vs. B) gives the highest speedup and by how much? (b) If your goal is to improve performance per increase in die area, which design (A vs. B) is closest to your goal? By how much? 3. Performance Evaluation [10pt] Suppose that you are considering between a pipelined processor design vs. non‐pipelined processor design. With pipelined design, you can breakdown the processor into five pipeline stages, resulting in five times improvement in clock frequency. However, since you need to make the instructions more standardized and simpler, you end up with twice as many instructions to represent a typical program. In addition, imperfections in the pipeline due to dependences, cache misses, etc. result in lower efficiency of the throughput, resulting in a 25% increase in the number of cycles needed to execute an instruction. How much speedup or slowdown does the pipelined design have over the non‐pipelined design? 4. Performance Evaluation [15pt] Suppose that we have two machines A and B. The following table shows the execution times for programs that make up a benchmark suite for machine A, machine B, and a reference machine X. Program Exe. time of X Exe. time of A Exe. time of B P1 100 40 20 P2 200 100 150 P3 50 40 20 P4 80 10 15 (a) Calculate the overall speedup of machine A versus reference machine X, using geometric mean. (b) Calculate the overall speedup of machine B versus reference machine X, using geometric mean. (c) Calculate the overall speedup of machine B versus reference machine A by computing the speedup for each program, and then taking the geometric mean of the speedups. (d) Calculate the overall speedup of machine B versus machine A, by taking the ratio of part (b) and part (a). (e) Calculate the geometric standard deviation of machine A versus machine X. 5. Power Wall [10pt] Suppose that scaling factor in the next process generation is λ= 0.7 (meaning that transistor length is reduced by the scaling factor.) With limited voltage scaling, suppose that we want to keep the dynamic power consumption constant in the next generation while also shrinking the die size by 10%. How much should we reduce clock frequency to achieve that? Note, capacitance C is also linearly scaled by the transistor scaling factor, λ. 6. Chip Cost [10pt] Compare three chips with the following manufacturing parameters: Chip Die Size (mm2) Defect rate (per cm2) A 400 0.018 B 350 0.04 C 200 0.04 In all scenario, assume that N= 13.5, a 300 mm wafer is used, the wafer costs $1000, and the wafer is the only cost that we consider. Compute the chip cost for each scenario through the following stages: (a) Compute number of dies that can be manufactured on one wafer (b) Compute the number of good dies that can be manufactured on one wafer (c) Compute the chip cost for each scenario. 7. Instruction Set Architecture [15pt] Assume that instruction operands are represented in 8 bits, memory addresses are 64 bits, and register addresses are 6 bits. (a) For each instruction set architecture shown in the following figure, how many opcodes, memory operands, and register operands are there, and what is the total code size? Stack Accumulator Register Load‐Store Push A Load A Load R1, A Load R1, A Push B Add B Add R1, B Load R2, B Add Store C Store C, R1 Add R3, R1, R2 Pop C Store, C, R3 Answer: Style Num opcodes Num Mem Addr Num Reg Addr Total Code Size Stack Accumulator Register (Reg‐Mem) Register (load‐store) (b) Suppose that the code sequence is to compute A = B+C, B = A+C, and D = A‐B. Assuming that all of A, B, C, and D are initially in memory, list the sequence of instructions needed to perform that computation for the different styles of ISA (Stack, Accumulator, Register (Reg‐Mem), and Register (Load‐Store)). After that, count the number of codes, memory operands, and register operands and total code size. For register machines (Reg‐Mem and Load‐Store), assume that you have unlimited number of registers. Code: Style Num opcodes Num Mem Addr Num Reg Addr Total Code Size Stack Accumulator Register (Reg‐Mem) Register (load‐store) 8. Instruction Set Architecture [20 pt] Registers that are visible to the software are often referred to the architecture registers. Various processors have different number of architecture registers. The purpose of this exercise is to assess the impact of having various number of registers on the code complexity. Suppose that the code sequence is to compute A=B+C, B=A+C, and D=A‐B. Assume that all of A, B, C, and D are initially in memory. List the sequence of instructions for Register (load‐store) ISA, and compare the number of loads and stores that you need in order to do the computation when: (a) There are 2 architecture registers. (b) There are 3 architecture registers.
Page 1 of 5 CONT316 Examination – 2018/19 DO NOT REMOVE FROM EXAM VENUE Plymouth University TIME ALLOWED Two hours DATE TIME FACULTY Science and Engineering SCHOOL Engineering ACADEMIC YEAR 2018/19 STAGE Three INSTRUCTIONS TO CANDIDATES: Candidates are not permitted to look at the examination paper until instructed to do so. MODULE CODE: CONT316 Examination MODULE TITLE: Systems, Instrumentation and Control Answer ALL questions. Semester 2 Exam Page 2 of 5 CONT316 Examination – 2018/19 Q1. (a) The fundamental SI units for use in mechanical technology is mass (M), length (L) and time (T). Express the following quantities in terms of fundamental units M, L and T. (i) Speed (ii) Power (iii) Energy (6 marks) (b) Describe the difference between accuracy and precision in an instrument. (4 marks) Q2. (a) A pressure gauge of range 0-10 bar has an inaccuracy of ± 2% of the full scale reading. Calculate the maximum error in the reading. (2 marks) (b) Briefly describe the workings of a potentiometric transducer. (4 marks) (c) If a transducing spring deflects 0.04m when subjected to a force of 8KN, find the input force for an output displacement of 0.08m. (4 marks) Q3. (a) Define sensitivity in an instrument. (3 marks) (b) Determine the measurement sensitivity of a thermocouple with the given input and output readings: Input (degrees) Output (mV) 200 2 400 4 600 6 800 8 1000 10 (5 marks) (c) Define the setup of a thermocouple thermometer. (2 marks) (Over…/) Page 3 of 5 CONT316 Examination – 2018/19 Q4. (a) Define and explain the principles of a restriction flow sensor. (4 marks) (b) Define the gauge factor (GF) of a metallic strain gauge and calculate the change in a nominal wire (metallic) resistance of 120Ώ that results from a strain of 1000 mm/m. (4 marks) Equation to be used: GF = ε ΔR/R (c) Briefly describe the application of pitot-static tubes. (2 marks) Q5. (a) Define and explain the principles of accelerometers. (3 marks) (b) By equating Newton’s second law and Hooke’s law show that = ∆. (3 marks) (c) The acceleration in the mass-spring system is defined as: = ∆ Where K = Spring constant in N/m m = Seismic mass in Kg ∆x = Spring extension in m Calculate the maximum measurable acceleration for an accelerometer having a seismic mass of 0.03 Kg and a spring constant of 2.5 x 103N/m. Maximum mass displacement is ± 0.025 m. (4 marks) (Over…/) Page 4 of 5 CONT316 Examination – 2018/19 Q6 (a) Draw the circuit diagram of a non-inverting operational amplifier when it is used for signal amplification in instrumentation defining all relationships. (4 marks) (b) An inverting operational amplifier is required to produce an output that ranges from 0 to -3V when the input goes from 0 to 80mV. By what factor is the resistance in the feedback arm greater than that in the input? Equation to be used: 0 = −2 1 (3 marks) (c) Define the phenomenon of piezo-electric effect. (3 marks) Q7. (a) The general form of a second-order control system is given as follows: () () = 22 + 2 + 2 The time response of second-order system depends on the value of damping factor (ζ). Sketch the typical response for a step input for an under-damped second-order control system outlining the rise time, settling time, peak overshoot and peak time. (4 marks) (b) Define each parameter in (a) above. (4 marks) (c) A system has an input voltage of 12V which is suddenly applied by a switch being closed. State the input as an s (Laplace Domain) function. (2 marks) Q8. Deduce the system transfer function relating C(s) to R(s) for the block diagram shown in Figure Q8. (10 marks) Figure Q8 (Over…/) R G1 G2 F H G3 C + ε _ + + R(s) Page 5 of 5 CONT316 Examination – 2018/19 Q9. (a) Define a stable control system in terms of system poles and zeros. Sketch the poles and zeros on the s-plane. (3 marks) (b) The characteristic equation for a closed loop system is given by: F(s) = s5 + 2 s4 + 2 s3 + 4 s2 + 11 s + 10 = 0 Using the Routh-Hurwitz array, determine the stability of the system. (7 marks) Q10. (a) Find the Laplace transform () of () given below and hence find the output (). () = 18̈ − 7̇ + 2 ; (0) = 3, ̇(0) = 0 (5 marks) (b) Find the Inverse Laplace transform of: () = 1(−7)(−3) (5 marks) [Note: () = − ℎ () = 1 + ] – END OF PAPER –
ECE 485/585 – Microwave Design Techniques Spring Term 2020 Take-home Midterm The exam is posted on Wednesday, May 13 at noon and is due on Thursday, May 14 at noon. By submitting this take-home exam, you certify that you have not used or consulted any resources other than the class notes, class homework assignments, class lab notes, information posted on the Canvas class space, and the textbook while working on the following problems. Total number of points: 40 pts. 1. (10 pts.) A waveguide load with an impedance of 377W for the dominant mode is to be matched to an air-filled rectangular waveguide at 10 GHz using a quarter-wave matching transformer. All waveguide sections have the same cross-sectional dimensions (WR-90). The quarter-wave section is realized by filling the space inside the waveguide section with a dielectric material. Determine the required dielectric constant of the dielectric material and the physical length of the quarter-wave section. Discuss limitations of this matching technique. For ECE585 students only: What is the return loss of the quarter-wave matching transformer at = 11 GHz? 2. (a) (4 pts.) An air-filled rectangular waveguide contains a solid rectangular conductor of width w and thickness t placed in parallel to the waveguide axis, as shown in the cross-sectional view below. Determine the cutoff frequency and phase velocity of the fundamental (dominant) propagation mode of this structure. (Assume all conductors to be perfect.) (b) (2 pts.) Consider two microstrip lines A and B with identical dimensions (strip width and ground plane spacing) but on different substrates of relative permittivities %,’ and %,( where %,’ < %,( (% = 1 for both dielectrics). If both microstrips are fabricated to have length 8⁄ at the operating frequency, which line is physically longer? Explain. metallic waveguide conductor a b t w x y 3. (14 pts.) Without using tables, derive the impedance, ABCD, and scattering parameters for the two-port network shown below. Determine the insertion loss and return loss of the network. The port impedances are: /0 = ; /3 = 2, where is purely resistive. 4. (10 pts.) A four-port network has the scattering parameters shown below (all four port impedances are equal to 5). Now, ports 3 and 4 are connected with a lossless transmission line having characteristic impedance 5 and electrical length . For the resulting two-port network, determine the insertion loss and phase delay between ports 1 and 2 in terms of , , , and . Give numerical values for = 0.3 exp(−30°) ; = 0.8; = 0.7 exp(−30°) = 0.7 exp(−45°) and = 60°. () = K 0 0 0 00 0 00 L For ECE585 students only: Also determine the return loss at port 1. Port 1 Port 2 Z 3∙Z
THE UNIVERSITY OF SYDNEY SCHOOL OF MATHEMATICS AND STATISTICS Discrete mathematics and graph theory Semester 1, 2020 MATH2069 Quiz 2 – Sample Student Number: Signature This is the Sample Quiz for the topology component of Math2069. The real quiz contributes 15% towards your final assessment in Math2069. The sample quiz will give you an idea of the sorts of questions that you might be asked in Quiz 2. The real quiz will be similar to this one in difficulty but the questions will be different. Quiz 2 covers material from Lecture 7-1 to Lecture 11-3. The style of the quiz will be similar to the Replacement Quiz for Quiz 1. You will be asked to enter answers to the questions, rather than having to select from different multiple choice options. There will be 8-10 questions with most questions having multiple parts as this gives you more opportunities to gain marks. The solutions to the Sample Quiz will be made on Monday in week 11. It is strongly recommended that you try and to complete this quiz without looking at the solutions. Quiz 2 will be run in canvas during the Practice class in week 12. That is, the quiz will run 2-3pm, Friday May 22. Precise details of how to access the quiz will be given on the day. You will have 50 minutes to complete the quiz. This quiz paper has four pages and 10 questions. MATH2069: Quiz 2 – Sample © 2020 The University of Sydney Discrete mathematics and graph theory MATH2069 Time allowed: 40 minutes 1. Consider the graphs Which of the following is true? a) All of these graphs are isomorphic. b) 퐺 is isomorphic to 퐺′, but is not isomorphic to 퐺′′. c) None of these graphs are isomorphic. d) 퐺′ is isomorphic to 퐺′′, but is not isomorphic to 퐺. 2. Consider the graph Which of the following is true? a) 퐺 is a forest, and Δ(퐺) = 2. b) 퐺 is a tree, and Δ(퐺) = 2. c) 퐺 is isomorphic to 푃5, and Δ(퐺) = 2. d) 퐺 is bipartite, and Δ(퐺) = 0. 3. Which of the following is true? a) Both (0, 2, 2, 2, 4, 4, 4, 4, 4) and (0, 1, 1, 2, 2, 4, 5, 5) are graphic. b) (0, 2, 2, 2, 4, 4, 4, 4, 4) is graphic, but (0, 1, 1, 2, 2, 4, 5, 5) is not graphic. c) (0, 2, 2, 2, 4, 4, 4, 4, 4) is not graphic, but (0, 1, 1, 2, 2, 4, 5, 5) is graphic. d) Neither (0, 2, 2, 2, 4, 4, 4, 4, 4) nor (0, 1, 1, 2, 2, 4, 5, 5) are graphic. 4. Consider the following graph 퐺. Which of the following is true? a) 퐺 has an Eulerian trail, and is Hamiltonian. b) 퐺 has an Eulerian trail, but is not Hamiltonian. c) 퐺 does not have an Eulerian trail, but is Hamiltonian. d) 퐺 does not have an Eulerian trail, and is not Hamiltonian. 5. Consider the tree MATH2069: Quiz 2 – Sample Page 2 of 4 MATH2069 Quiz 2 – Sample 1 2 3 4 5 6 What is the Prüfer sequence of this tree? a) (2, 4, 5, 3) b) (6, 1, 3, 3) c) (1, 6, 3, 3) d) (6, 3, 3, 1) Questions 6 and 7 concern the following weighted graph: 1 3 2 2 1 2 2 3 2 1 2 1 2 2 2 6. What is the weight of a solution of the Chinese Postman Problem? a) 28 b) 32 c) 33 d) 18 7. What is the weight of a minimal spanning tree? a) 14 b) 26 c) 18 d) 28 8. Consider the graph How many spanning trees does this graph have? a) 8 b) 1 c) 3 d) 4 9. Consider the two graphs: MATH2069: Quiz 2 – Sample Page 3 of 4 Discrete mathematics and graph theory MATH2069 Which of the following is true? a) 휒(퐺) = 2, 휒(퐻) = 2 b) 휒(퐺) = 3, 휒(퐻) = 3 c) 휒(퐺) = 4, 휒(퐻) = 2 d) 휒(퐺) = 3, 휒(퐻) = 2 10. Which of the following is true? a) 휒(푃5) = 2, 휒(퐶5) = 2, and 휒(퐾5) = 5.b) 휒(푃5) = 2, 휒(퐶5) = 3, and 휒(퐾5) = 4.c) 휒(푃5) = 2, 휒(퐶5) = 3, and 휒(퐾5) = 5.d) 휒(푃5) = 4, 휒(퐶5) = 3, and 휒(퐾5) = 4. This is the last page of the quiz paper. MATH2069: Quiz 2 – Sample Page 4 of 4
CSE316 Assessment 1: Coursework Tasks: In this assignment, students are asked to improve the efficiency or security of authenticated key exchange (AKE) protocols. Codes of AKE protocols in TLS, IEEE 802.15.6 and Bluetooth will be given as examples; and methods to improve the efficiency and security will be introduced. Students are going to realize lightweight AKE protocols or security-enhanced AKE protocols using the introduced methods or their own proposed methods. In particular, each student should 1. Realize a lightweight AKE protocol or a security-enhanced AKE protocol of his/her choice; 2. Write a short report (in MS word, single column, 11 font size, and in Calibri font style). The report is expected to include the following parts: a) a brief description of protocol; b) experimental platform (e.g., hardware, software); c) results, e.g., runtime, screenshots for the experiment. The example codes are in Python, but students can use their preferred programming language for the tasks. Marking scheme: Total points: 100 (contribute 20% to the overall assessment) Item Marks Realisation 30 Testing 30 Quality of implementation 20 Quality of report 20 Submission Each student should submit a short report and codes to ICE, without coursework cover. Deadline: Sunday, 17 May 2020, 23:59
EGH446: Semester 1, 2020. 1 EGH446: Autonomous Systems: Project Parts A & B Due Date: See blackboard, 2020. Weight: 60 % Overview: Major Project. Groups of 2 students. Project Overview †‡ The aim of this group-based project is to investigate and implement control and guidance approaches for a ground or an aerial autonomous system. The goal is to design the necessary subsystems to build an autonomous vehicle that is able to navigate to a goal location on an optimal path while avoiding obstacles. See appendix A and B for detailed requirements. During this project, the group must develop the following subsystems: • A guidance subsystem that enable the vehicle to follow waypoints. • A path planning sub-system that construct a trajectory to a goal location. • A collision avoidance subsystem that steer clear of walls and static obstacles. The aim to minimise the time taken to achieve the goal, given any random location within the workspace. The group may use the following subsystems from the provided Simulink library: • Laser/Lidar subsystem. • Obstacle detection subsystem. At the start of the project, the team is given: • A high fidelity dynamic simulation environment in Matlab/Simulink in which to build their ground or aerial autonomous system. • A getting started guide for the simulation environment. • Basic stabilisation approach for each vehicle. • A Simulink library with control/guidance/navigation blocks that can used to validate your implemented approach. † c©Queensland University of Technology, 2020. EGH446: Autonomous Systems. School of Electrical Engineering and Robotics, Queensland University of Technology. ‡Please report errors within this document to [email protected] EGH446: Semester 1, 2020. 2 Submission Requirement and Assessment The final submission must contain for part A, two reports and the final implemented solution using the simulation environment provided. For part B, a single report and the final implemented solution using the simulation environment provided. Reports and software should be compressed in a ZIP file and submitted to blackboard. Each group will submit: 1. The group’s solution implemented within the provided simulation environment in Matlab/Simulink (i.e. submit the whole Simulink file so that the solution can be simulated by the marker). 2. Report(s) addressing requested information. 3. See BB for more details. Please review the CRA sheet to see how your submission will be graded. Important Instructions and Rules 1. In this project you will be required to investigate and implement suitable algorithms for automation using concepts covered in lectures. Your learning will be at a more detailed level than covered in the teaching material. • It is suggested you initially attempt lower automation levels before increasing automation complexity. Initially, using the position only waypoint capture is conceptually easier, but the path planning and obstacle approaches are required for higher level performance. 2. You may not use pre-designed navigation or guidance blocks/algorithms available in the Simulink library. 3. You may need to tune the provided base stabilisation approaches provided (optional). 4. Students should divide the work and take ownership for a subsystem(s) and document their work in the report. 5. These sub-systems are coupled, and design decisions in each sub-system impacts the other system (in the sense that all sub-systems need to work together). Students will need to negotiate their design decisions with each other. 6. On request the unit coordination may give permission for submission by an individual who completes all systems by themselves. They will be marked according to the same CRA. 7. Note that QUT’s policy on plagiarism applies to this project: https://www.library.qut.edu.au/ http://studysmart.library.qut.edu.au/module6/6_5/ http://www.citewrite.qut.edu.au/academichonesty/avoidplagiarism.jsp EGH446: Semester 1, 2020. 3 A (30 %) Part A Requirements: Due Week 7, 20th April. 1. Given the basic dynamics and stabilisation, design a guidance logic to navigate waypoints. 2. Report on the following: (a) Total mission time. (Time it takes the vehicle to visit all waypoints). (b) Provide a detailed explanation of your guidance subsystem. Include a block diagram of the overall design, include plots and necessary diagrams to support your explanations. (c) Implement and report on average cross track error. (d) In terms of your position controller, report on the following performance parameters: rise time (the time needed by the control system to reach the desired value after a perturbation), peak overshoot (the highest value reached by the response before reaching the desired value), settling time (the time required to reach and stay within 2% of final value) and steady-state error. Use as step function x = 10 m, y = 0 m, with initial heading θ0 = 30 0. See below. Y X (10,0) !” = 30″ (0,0) Example path Figure 1: Example setup for position controller design EGH446: Semester 1, 2020. 4 B (30%) Part B Requirements: Due Week 12, 28th May Given the dynamics of a robot, design the necessary subsystems to allow this robot to navigate in an indoor envi- ronment (see Fig. 2). The environment contains obstacles that must be avoided by your robot while navigating towards a target waypoint. The navigation consists in visiting 5 waypoints. Specifications: 1. Robot • Initial position (x, y) = (2, 2) m • Initial heading, θ= 0 deg • Robot radius: 0.25m 2. Waypoints and obstacles • Number of waypoints: 5 • Location (x, y) of each waypoint: Generated randomly within the area boundaries. • Area boundaries XWorldLimits: [0 26], YWorldLimits: [0 20.5] in m. • Waypoints must not overlap walls or obstacles. • Number of obstacles: 12. • Obstacles positions are given. • Obstacle height is such that block any aerial robot path. 3. Task • All waypoints must be visited, either ordered or unordered. Robot stop at the last waypoint. • Robot trajectories must not cross wall or obstacles. • Minimum distance between your robot and obstacles and walls is equal to robot radius. Trajectory must not come closer than this value to any wall or obstacle. • The mission time should be no longer than 7 min. • Obstacles must be avoided using the onboard sensor. 4. Reporting (single report) (a) Each student must include a statement of contribution in the report. (b) Provide an explanation of the path planner algorithm used. Provide details on parameters used, working principle, advantages and disadvantages, reasons for choosing the algorithm. (c) Provide an explanation of the obstacle collision avoidance approach used. Working principle, how is the sensor used to detect obstacles and how is this information integrated with the guidance subsystem. (d) Provide an explanation on which subsystems from part A were re-used and how the guidance approach from part A was used in part B. EGH446: Semester 1, 2020. 5 Robot location Waypoint 1 Waypoint 3 Waypoint 5 Waypoint 2 Waypoint 4 Robot location obstacles Trajectories Figure 2: Example setup for the task Supplementary information: 1. Obstacles are given by obstacles.mat, third column is optional (r=1, g=2, b=3). Is used by the robot visualizer to differentiate obstacles by color. obstacles = X Y Color 4 4 1 8 8 2 8 2 3 8 18 1 2 12 3 14 14.5 2 22 14 1 16 6 3 23 4 2 24 18 1 12 4 2 21 9 3 2. Map is given by complexMat.mat. Logical and probabilistic versions of the map are given by logical occupancy map.mat and probabilistic occupancy map.mat, respectively. A ’1’ or ’0’ (logical) represent occupied or free cells. A ’0.9990’ or ’0.0010’ (probabilistic) represent probabilities for occupied or free cells, respectively.