PAFBAC-301018, Intensive Course on Investments Start date: 3/21/2025 Due date: 4/4/2025 Final Project Note: All files and information related to the final project are located in the various folders starting with “Final Project” prefix on the system. The aim of this Final Project is to practically implement the ideas from the course, specifically from Chapters 7 and 8. You will be given a recent 20 years of historical daily total return data for 21 stocks, which belong in groups to 4-5 different industry sectors, one (S&P 500) equity index (a total of 22 risky assets) and a proxy for risk-free rate (1-month Fed Funds rate). In order to reduce the non-Gaussian effects, you will need to aggregate the daily data to the monthly observations, and based on those monthly observations, you will need to calculate all proper optimization inputs for the full Markowitz Model (“MM”), alongside the Index Model (“IM”). Using these optimization inputs for MM and IM you will need to find the regions of permissible portfolios (efficient frontier, minimal risk portfolio, optimal portfolio, and minimal return portfolios frontier) for the following five cases of the additional constraints: 1. This additional optimization constraint is designed to simulate the Regulation T by FINRA (https://www.finra.org/rules-guidance/key-topics/margin-accounts), which allows broker-dealers to allow their customers to have positions, 50% or more of which are funded by the customer’s account equity: 2. This additional optimization constraint is designed to simulate some arbitrary “box” constraints on weights, which may be provided by the client: 3. A “free” problem, without any additional optimization constraints, to illustrate how the area of permissible portfolios in general and the efficient frontier in particular look like if you have no constraints; 4. This additional optimization constraint is designed to simulate the typical limitations existing in the U.S. mutual fund industry: a U.S. open-ended mutual fund is not allowed to have any short positions, for details see the Investment Company Act of 1940, Section 12(a)(3) (https://www.law.cornell.edu/uscode/text/15/80a-12): 5. Lastly, we would like to see if the inclusion of the broad index into our portfolio has positive or negative effect, for that we would like to consider an additional optimization constraint: You will need to present the results in both the tabular and graphical form. with the objective to make inferences and comparisons between the sets of constraints for each optimization problem and between the MM and IM models in general. You will need to explain your observations making the connections to theory studied in the lectures. Again, you will be given 20 years of daily data of total returns for the S&P 500 index (ticker symbol “SPX”), and for ten stocks (ticker symbols see the table below) such that there are 4-5 groups of stocks with stocks in each group belonging to one industry sector and an instrument representing risk-free rate, 1-month annual Fed Funds rate (ticker symbol “FEDL01”). Note that stocks in each of the groups are different. Therefore, each groups will have its own results and conclusions. Below, please, find the table of instruments’ ticker symbols (a.k.a. tickers) for each group to work with: Below, please, find the table which shows the details for each of the stocks and which stocks belong to the same industry sector in each group. Using this data you will need to prepare an Excel spreadsheet that makes all the necessary calculations to plot a Permissible Portfolios Region, which combines the Efficient Frontier, the Minimal Risk or Variance Frontier, and the Minimal Return Frontier for a given set of constraints (1-5 above). The Minimal Return Frontier and the Efficient Frontier together are forming the Minimal Risk or Variance Frontier – it is just a matter of re-formulating the optimization problem, as follows: Minimal Risk or Variance Frontier: Minimal Return Frontier: Efficient Frontier: Two unique points that you need to find on the Efficient Frontier are of special interest: Minimal Risk Portfolio: and Efficient Risky Portfolio: This Final Project in an open-book which means that you can and should use the Instructor’s handouts and the corresponding Chapter copy reading material provided by the Instructor, as well as any additional materials provided to you. Instructor and Mentor have performed all these calculations for each of the group’s portfolios and will be able to compare your numbers, specific points and graphs to theirs. If your spreadsheet calculations are done correctly, you and we should be able to match the results with sufficient accuracy. The main tool that we would like you to use to solve the optimization problems for each point on the Minimal Risk or Variance Frontier is the Excel Solver. Please, try to learn how to use it on your own, if you have not done so already. The Mentor will be helping you to address any issues related to Solver during the Mentor sessions. To calculate large numbers of multiple points on any of the required frontiers, you will need to use the Excel Solver Table, which the Mentor will teach you how to install and use. Both Excel Solver and Excel Solver Table will also be covered in lectures with illustrations which are very similar to your Final Project. For your calculations, you need to use the full available historical data range: start date 9/17/2004; end date 9/20/2024. As it was mentioned above, you will need to calculate the solutions to two optimizations covered in lectures: The full Markowitz Model (MM); The Index Model (IM). As we have described this in detail above, each of these optimization problems MM and IM you will need to implements and solve with the following additional optimization constraints: As we have already mentioned, your task is to produce the Permissible Portfolios Region: Minimal Risk or Variance Frontier (a curve); Minimal Risk Portfolio (a point); Maximal Sharpe Ratio or Efficient Risky Portfolio (a point); Efficient Frontier (a curve); Capital Allocation Line or CAL (a straight line); Minimal Return Frontier (a curve). You will need to analyze all your results with the purpose of comparison of different constraints for each optimization problem (MM and IM), and the two optimization problem solutions between each other with same constraints. You are expected to write the details of your comparisons analysis and your explanations as to why certain results are similar and certain other results are not in the PowerPoint presentation and present your work using one or several presenters during an up-to 30-minute presentation time allocated for each group. Do not hesitate to ask Mentor, Lecturer, or TAs any questions related to this. Good luck! You are given two weeks to complete the Final Project and to prepare the presentations. We encourage you not to delay starting the work as workload is meant for several days of team work and not as a onenight, single person effort. Final Project presentations will take place on April 4th, 2025 at 8:30 PM EST. To re-iterate, in this Final Project you will need to achieve the following goals: 1. Get familiar with the markets allocated to your group, download the data, and review all the necessary information from Bloomberg slides. 2. Prepare the data for optimization problem solution (aggregate it from daily to monthly frequency), calculate all the required inputs for each of the optimization problems MM and IM, and for each of the five sets of additional optimization constraints. 3. Calculate both of the two key frontier points (maximal Sharpe Ratio and Minimal Risk), and two frontiers: the Efficient Frontier and the Minimal Return Frontier. 4. Prepare the PowerPoint presentation where you show your results, formulas and conclusions with all the details of your work. Please, aim for an up-to 30-minute presentation.
Module title & code WM993 Assessment type Development of Controllers/Observers Weighting of mark 40% Assignment brief You’re working as an electric machine control engineer and have been tasked with designing a proper controller for a DC motor for a specific operating point. The general equation of DC motors is shown below: The output is torque, which is calculated using the following equation: Where T is the electric machine torque, ωe speed of the electric machine in rad/s which is ωe = RPM, and ia and va are the armature currents and voltage respectively. The constant parameters are presented in Table 1: Table 1 Parameters of the DC motor For this project: 1 State space representation 1.1 Input, output and states [2 marks] Determine inputs, outputs and states of the systems. 1.2 State space representation [2 marks] Rearrange the equation into the standard form. of state-space representation of the system. Specify the state and output equations. 2 Linearisation The operating point at which you’re asked to design a controller is T* = 50 Nm and RPM = 1500 rpm. For this operating point: 2.1 Operating point condition [3 marks] Identify and calculate the operating point conditions, encompassing inputs, outputs, disturbances and states. 2.2 Linearisation [4 marks] Linearise the system around the operating point in the form. of: δX = AδX + BδU δY = CδX + DδU Determine the A, B, C and D matrices. Where all variables with δ show incremental variables. 2.3 Implementation and Validation [4 marks] Simulate both the nonlinear system and the linear system in Simulink, and contrast their responses to a sinusoidal input that varies around the operating point input , with an amplitude of 5% of the operating point input and a frequency of 1 rad/s, i.e. Show the block diagram of the system you used to compare linear and nonlinear systems and discuss the result. Assume that the speed signal remains constant at 1500 rpm. 3 Transfer function Convert the state space to a transfer function and analyse the system. 3.1 Convert to transfer function [2 marks] Convert the state space to a transfer function using ss2tf in MATLAB. When deriving the transfer function, there's no need to incorporate disturbances and Ba matrix. 3.2 Pole location [2 marks] Find the poles and zeros of G(S) and report them. Use pole and zero command in MATLAB. 3.3 Unit step response [2 marks] Illustrate the unit step response of G(S) and report it, using the step command in MATLAB. Report the settling time. 4 Controller Design You have been tasked to design a linear controller to control the torque of the DC electric machine at a specific operating point. It is assumed that we have access to a sensor that can measure the generated torque. 4.1 Design of controller for linearized system 4.1.1 Desing of the controller [2 marks] For the control design task, you are required to use the “Control System Designer” application in MATLAB. The objective is to eliminate any steady-state error and achieve a settling time of approximately 1 second for the output around the operating point T* = Nm and RPM* = 1500 rpm. The linear controller shouldn’t show any oscillation or overshoot. Please display the reference tracking time response and the controller effort time response. 4.1.2 Bandwidth [2 marks] Illustrate the frequency response of the reference tracking and controller effort. Based on these graphs, determine the bandwidth of the controller effort and the reference tracking, also please demonstrate the frequency of the bandwidth on the graphs. Discuss these values and explain what they reveal about the performance and requirements of the controller. 4.1.3 Controller transfer function [1 mark] Report the proportional and integral coefficients (if only one exists, indicate that the coefficient of the other is zero). Furthermore, present the transfer function of the controller, C(s). Hint: It is recommended to use a PI controller. 4.2 Validation of the control system In this section, you are required to implement the linear controller you have designed on the nonlinear system and demonstrate its performance. First, present the architecture of the controller, then implement it in Simulink, and finally discuss the results. 4.2.1 Architecture of the controller system [2 marks] Describe the control architecture you used for the control design and provide a block diagram of the linear controller applied to the nonlinear system. Additionally, explain how you implemented the linear controller to manage the nonlinear system. 4.2.2 Implement the controller without a load [3 marks] Implement the controller in Simulink and test the torque control performance. Use the nonlinear plant and assume the speed is constant at 1500 rpm. Demonstrate the tracking performance of a step torque command increasing from 50 Nm to 60 Nm at 2 sec and run the simulation for 10 sec. 4.2.3 Implement the controller with a load [4 marks] Implement the controller in Simulink and test the torque control performance. For this test, use the nonlinear plant model for the electric machine and connect it to the provided load model (load.slx). This setup will provide a variable load, as the electric machine is connected to a load, causing the speed to no longer remain constant. Demonstrate the tracking performance of a step torque command increasing from 50 Nm to 60 Nm at 2 sec and run the simulation for 10 sec. Discuss any potential degradation in tracking performance. 5 marks of this PMA are dedicated to standard scientific report formatting, referencing, and structured reporting. Item Mark Quality of figures (including the type of figure, axis titles, and units) 1 Captions of figures and tables and referring to the captions in the main text 1 Structured format for the entire report 1 Using references and the correct format for referencing 1 Academic format for the report (including table of contents, list of figures, page numbers, and appropriate font size) 1 Word count The word limit is 1600 words excluding the table of contents, table of figures and tables. Module learning outcomes (numbered) LO 1. Demonstrate a comprehensive understanding of the practical application of the different approaches to mathematical modelling and analysis of one-dimensional physical systems [AHEP:4-M1] LO 2. Derive, translate, solve & analyse 1D functional models of physical systems in sequential block diagram, transfer functions & state variable forms [AHEP:4-M1,M3] LO 3. Demonstrate understanding in model linearization and validation of the linearized models with application in automotive systems. [AHEP:4-M1] LO 4. Develop and apply controller and observer systems for dynamical systems in automotive applications, utilizing both classical and modern model based techniques. [AHEP:4-M1, LO 5. Develop integrated models of automotive systems to gain a practical understanding of multi-physics simulation techniques. [AHEP:4-M3] Learning outcomes assessed in this assessment (numbered) LO3, LO4
Final Project Assignment Econ 490 Economics of Crime I. The Assignment For your final projects, you will conduct an economic analysis of Season 3 of The Wire. The project will involve an in-class presentation as well as a 5-10 page (if single spaced) written product. The goal is to use economic concepts – how people respond to the incentives they face, how supply and demand interact, how market regulation affects prices, etc. – to explain why the characters behave as they do and how their decisions might differ from what a social planner would prefer. Each group will be assigned a set of characters on which to focus (the police, the users, the high- level drug sellers, or the street-level drug sellers). In each case, your project should address the following questions: 1. What enters this group’s (or, if you prefer, one or two individuals in the group) utility function? This can include positive incentives – what they value or what provides benefits – as well as negative incentives – what gives them disutility or what they try to avoid. 2. What are the relevant constraints they face? That is, what is stopping them from just getting as much of the things they like as they want? (Remember that costs, benefits, and constraints can be both monetary and non-monetary.) 3. How does this constrained optimization – maximizing utility under the constraints you have identified – shape the decisions they make? In other words, how does economics help us understand people’s actions, especially those that might otherwise seem illogical? 4. When other groups act, how do the incentives and constraints facing your key characters change? What would economic theory and/or the findings we’ve seen in the literature suggest should happen when those things change? Is that what actually happens? 5. Do the responses have consequences for people other than those who are making the decisions? Is your decision-maker taking the full costs of those consequences into account? Why or why not? 6. If you were a benevolent social planner, what would you change to improve social welfare? (The answer should not be “make people respond differently.” Work within the constraints of how your group of people are making their decisions and think about whether there are feasible regulations or policies that would incentivize people to reduce any socially harmful behavior. that you have identified in part 5.) There are multiple ways to structure a successful analysis. You might choose 1 or 2 characters of your assigned type and trace their behavior. through the season. Or you might choose several particular incidents that involve a range of characters and do a deeper dive into those. You do not need to analyze everything that happens in the entire season, but you should not ignore the determinants or later consequences of the decisions you discuss. Your presentation should be at least 15 minutes and no longer than 18, followed by a few minutes of Q&A. All members of the group should speak. Please be respectful of your peers and come to class even after your own presentation. Pop quizzes are still fair game through the last day of class … The goal of the presentation is to explain your key insights and present supporting evidence in a clear and engaging way; you do not need to cover every single detail that is in the written version (i.e., don’t just read your paper as the final presentation). The written product should be a more formal version of your arguments that provides supporting evidence from both the show and from the course (theory and literature), and includes all relevant citations. The presentation and paper will weigh equally towards your grade. II. The Criteria A successful final project will lay out a clear and specific economic analysis, not just intuitive arguments. In particular, an A-level project will: - Focus on a small number of key aspects of the series that demonstrate relevant economic principles o This means choosing a small number of characters or a few concrete incidents rather than trying to explain all aspects of the plot. The exact number will depend on how broadly you define an incident, but in most cases will likely be between 2 and 4. - Identify relevant incentives and constraints, as well as how events in the series change those factors o This will involve thinking broadly about monetary and non-monetary factors, and thinking carefully about what enters characters’ utility functions. - Explain decision-making using economic arguments (rather than psychological, sociological, political, or emotional reasoning) o This should involve giving specific, concrete examples such as character quotations and specific incidents showing what drives decisions, how people are maximizing subject to the constraints they face, and how market forces interact. Do not rely on broad generalizations or overall plot summaries. - Tie the analysis into the theory and literature discussed in the course o This could mean using graphs that show what happens when certain changes occur, or comparing the direction and magnitude of behavioral change to what we saw estimated in the literature, or pointing out how certain dialogue reflects the kind of maximizing we see in economic theory, or explaining why other interventions we read about might be preferable from a social perspective. You don’t necessarily need to write down a complete economic model, but don’t be afraid of using graphs, numbers, or equations if they help make your point. - Be thoughtful about the unintended consequences and/or externalities resulting from decisions, and be creative in thinking through how a social planner might adjust the choices that your decision-makers face to generate a more socially optimal outcome. Focus on how the characters you model would respond to your proposed regulation given how you are specifying their decision-making process, and why that would be welfare enhancing. - Demonstrate an understanding of the entire series (not just the first several episodes) - Give an engaging presentation that clearly summarizes the arguments and the evidence - Submit a well-structured, clearly-written analysis that builds a series of specific insights into an economic argument about why characters behaved in a certain way, the implications of their decisions, and the way in which a social planner who understands how people make decisions would improve social welfare III. Example Questions To help guide your thinking, here are a few questions for each set of characters that might motivate your analysis. You are not obligated to answer these questions in particular, nor do you need to try to answer them all at once. They are here to help spark ideas and provide examples of the kind of thinking you should be doing. You are free to (and should!) address whatever other questions you think are most interesting or enlightening. You may also address the interactions between or effects of your assigned group on others not mentioned (politicians, community members, etc.). Police – higher-level commanders (Rawls, Burrell, Colvin), the investigative team (McNulty, Kima, Daniels, Lester, Bunk, etc.), and/or the street level cops (Herc, Carv, and their colleagues) - Why do the police do street buy-and-busts? Do they help reduce drug crime and drug use? Why or why not? - What happens at Compstat meetings? How does that change what district leaders do in their districts? Does it decrease crime or not? Why? - What do the politicians say to the police, how and why does that change their decisions, and how does it in turn affect policing and crime? - Why do the police shift their emphasis to finding bodies instead of busting drugs? Does everyone (in the show or in the literature) agree that the emphasis is the best way to reduce crime? - Why does Colvin establish the safe zones? - How does police deployment change after Hamsterdam? Why? Does it work? Is the size of the change consistent with the literature? - What is Carver’s tax initiative? Is it structured in a way that everyone should want to participate? What effect should it have on the drug market? Does it? - What does Colvin argue helped cause the deterioration of police-community relationships? Does his argument have any implications for other ways to reduce crime? - Why do the top brass (and politicians) react the way they do to Hamsterdam? What does that tell us about which costs and benefits they care most about? Demand Side of the Market – Bubbles, Johnny, and the other drug (or alcohol) consumers - In a book by the creator of The Wire, there is an argument that for an addict, drugs create anarchy; economics cease to exist. Is it true in the show that the addicts never actrationally? Do we ever see users responding to price? To other incentives? - How does Hamsterdam affect quantity, price, and consumption? Is the consumer response consistent with economic theory? - How do the other attempts at drug regulation affect users? What effects do they have on consumption and overall welfare? What are the implications for how society should think about regulating drug use? - Why do Johnny and Bubbles’ behave differently? What do the differences imply about the effectiveness of different kinds of social policy across heterogeneous people? - Why do the Johns Hopkins folks get involved? Would the social planner be pleased? Why or why not? - We see Bubbles working in the legal(ish) market as well as working and consuming in an illegal market. How do those decisions interact? Why does he float back and forth? Why don’t others? - In an earlier season, we learn that Johnny is HIV positive (which at the time had less effective treatment options than it does today). Does that help explain Johnny’s behavior? Why or why not? - Is other illegal activity a complement or a substitute for drug use? What does that tell us about how drug regulations should affect other crime? Does that happen in practice? - Alcohol is a drug, too. Does the answer to the prior question help us explain the ways different characters behave while using alcohol? - Drug users are committing crimes, too (both to fund their habits and just by using illegal drugs). How does police enforcement work with drug use crimes? How does that align with our model of how people decide to commit crime? Is the enforcement we see in the show socially optimal? High-Level Dealers – Stringer Bell, Avon, Marlo, Proposition Joe (and if you wish, Brother Mouzone, although his plot line may be hard to understand without watching Season 2) - Why does Stringer Bell not care about territory? Why does Avon disagree? What implications do the different choices have for the volume of drug use and violence? For how policy might address drug-related crime? - When does Marlo choose violence and when does he say to hold off? Why? - How do the dealers decide when to put people on or take them off corners? - What do the different dealers do (or not do) with their profits? Why? - Why does Stringer cede some of his power to join with other high-level dealers? - How does the availability of product change operational decisions, user consumption, and crime? Can economic theory explain that? - Why is Stringer willing to spend so much money to become a developer? - How does Hamsterdam affect quantity, price, and the resulting profits? What happens to staff allocation? Is the supply response consistent with economic theory? - How is it possible that people have respected the Sunday truce for so long? Why would they do that? - Why does Stringer turn in his own staff for the Hamsterdam shooting? - Why do the leaders engage in wars with each other despite the risks to themselves and the constant loss of their staff? - Why do Stringer and Avon make the betrayals they do at the end? Street-Level Dealers – Bodie, Poot, Cutty, Omar and his crew, etc., and the hoppers, lookouts and touts - What is driving Cutty’s decision when he comes out of prison? What changes his mind? - Why do the guys on the street keep selling even when the risk of death is so high? How are they convinced to keep fighting their bosses’ wars despite the risk to themselves? - What role do guns (“whistles”) play in the day-to-day behavior of the dealers? - How does the opening of Hamsterdam change the costs and benefits of being a street level dealer? What happens to the lookouts, touts, and runners? Why? - Omar often runs towards danger. Is he irrational? Or does he also respond to changes in costs and benefits? (Why doesn’t he want to steal from Hamsterdam? Why does he pursue Barksdale so relentlessly?) - Why do Bodie and Poot stay in their jobs despite the danger? What does their behavior tell us about how effective particular policing strategies are likely to be? What might convince them to leave the illegal market? - The Deacon tells Colvin that taking “the game” out of dealing takes the heart out of it. What does that tell us about sellers’ risk preferences? Is that universal or limited to marginal cases? - What is the draw of Cutty’s boxing center for the kids who go? What does that tell us about how youth are making decisions about illegal work? - What happens to particular dealers when Hamsterdam closes? What happens to crime? What does that tell us about the elasticity of labor supply in the drug market?
Renewable Energy Systems Integration (RESI) S2, 2025 Part 2 Tutorial Q.1 Figure 1 shows the schematic diagram of a three-phase wind plant installed in a Micro Grid to feed a utility grid. The wind plant is connected at Bus 1 and is with six identical fixed-speed wind turbine (induction) generators. Each wind turbine generator is rated at 50Hz, 690V, 710 KVA. Figure 1 Table 1 gives the parameters of wind turbine generators in the wind plant referred to the stator in Ω/phase. Table 1
Isocontour and Volume Visualization Grade: 100 points (10% of the course grade)1. 2D Isocontour Extraction: [60 Points]Notes: • For this part of the assignment, you must write the contour extraction algorithm on your own from scratch and you are not allowed to use VTK’s isocontour filter to do this. You can use VTK to read and write the data in VTK’s polydata file format. • Your program should work for any isovalue provided by the user. Hence, submit a Python script (not a Jupyter Notebook), and your script should take the isovalue as an input parameter and write the extracted contour out as a *.vtp (VTKPolyData) file. Make sure your output file can be read in ParaView. The possible range of isovalues for the given data set is between (-1438, 630)Dataset for this task:The dataset that you will use in this assignment is a 2D slice taken from a 3D Scalar field of a Hurricane Simulation Data. The variable is Pressure. If you want to know more about the original data, please refer to this link: http://vis.computer.org/vis2004contest/index.html2. VTK Volume Rendering and Transfer Function: [40 Points]In this second half of the assignment, you will write a Python script to implement the volume rendering algorithm from the VTK library. VTK has already implemented the ray-casting algorithm that we have studied in our class. In this assignment, you will use the vtkSmartVolumeMapper() to render 3D scalar data and set a specific color and opacity transfer function. You will also use VTK’s Phong Shading feature to produce advanced lighting effects to make your volume rendering more realistic. The ambient, diffuse, and specular parameters for Phong model are given below. Here are the steps that you should follow for this task:• Load the 3D data provided with the assignment. • Create instances of vtkColorTransferFunction and vtkPiecewiseFunction (this will work as Opacity transfer function) and set them up with the values provided below in the tables. • Use vtkSmartVolumeMapper() class to perform the volume rendering • Use vtkOutlineFilter to add an outline to the volume rendered data • By default, advanced shading feature, i.e., Phong shading will be off. Create an input parameter and take input from user if the user wants to use Phong shading. If yes, then your program should turn on Phong shading while rendering. • Create a 1000×1000 sized render window to show the rendering result.Color Transfer Function Specification:Data Value Red Green Blue -4931.54 0 1 1 -2508.95 0 0 1 -1873.9 0 0 0.5 -1027.16 1 0 0 -298.031 1 0.4 0 2594.97 1 1 0Opacity Transfer Function Specification:Data Value Opacity Value -4931.54 1.0 101.815 0.002 2594.97 0.0Phong Shading Parameters that you should use:Ambient coefficient: 0.5 Diffuse coefficient: 0.5 Specular coefficient: 0.5Again, you should write a Python script (not a Notebook), and your script will take the input parameter as to whether the user wants to use Phong shading or not. Update the above README.txt file to add instructions about how to run your volume rendering script.If you have done everything as suggested, you should see images like the following for volume rendering:Without Phong shading, front, and back viewWith Phong Shading, front, and back viewDataset for this task:The dataset that you will use in this assignment is a 3D Scalar field Volume Data of a Hurricane Simulation. Loading this data in VTK will be same as loading the 2D data. The variable in the Data is Pressure. If you want to know more about the original data, please refer to this link: http://vis.computer.org/vis2004contest/index.html.How to submit?
The project deliverables are listed below: • Project middle report: The middle report should include a title and team members if you choose to work as a group. The middle report should also identify the project scope, the research questions you plan to work on, and preliminary ideas about how you are going to address the research questions. The middle report has 5 points in the final grade. • Project Final report and other documents: The final project report should be a comprehensive report including everything. The final project report has 15 points in the final grade. • Final project presentation: everyone needs to prepare 10-15 slides for presenting their final project. If you are not sure what you want to do in the project, discuss your project ideas with me via emails, phone calls, face-to-face/online meetings, etc. The project will be evaluated based on the following criteria: • Originality and novelty • Technical depth and soundness • Presentation quality The adoption of AI is rising. AI has changed the ways we explore science and conduct businesses: • AlphaGo is the first computer program to defeat a professional human Go player, the first to defeat a Go world champion, and is arguably the strongest Go player in history. • Google’s DeepMind releases structure of every known protein. • ChatGPT passes exams from law and business schools. • Reinventing search with a new AI-powered Microsoft Bing and Edge, your copilot for the web. However, many threats and attacks have also been reported targeting machine learning algorithms. For example,As we expect AI continues to change businesses, consumers, and the economy, we would also like to investigate AI related cybersecurity issues. Option 1: Machine Learning Security In this project, you will conduct research on security and privacy issues related to machine learning. If you choose this option, you can explore any ML-related security and privacy issues. The topics include, but are not limited to: • Threats and attacks in AI • Threat modeling in AI • An in-depth study of an attack on AI • A case study of a cyber-attack on AI • Security remediation in AI • Risk assessment in AI • Survey of cybersecurity in AI Project deliverables: • Project middle report • Project final report • Project presentation slides • Other related project documents Option 2: Large Language Model (LLM) Security In this project, you will conduct research on security and privacy issues related to LLM. Examples of LLMs include GPT, Llama, and BERT. If you choose this option, you can explore any LLM-related security and privacy issues. The topics include, but are not limited to: • LLM for offensive security • LLM for defensive security • LLM for risk management • LLM for compliance and auditing • Threats and attacks in LLM • Threat modeling in LLM • An in-depth study of an attack on LLM • A case study of a cyber-attack on LLM • Security remediation, e.g., defensive mechanism, in LLM • Risk assessment in LLM • Survey of cybersecurity in LLM Project deliverables: • Project middle report • Project final report • Project presentation slides • Other related project documents Option 3: Self-Selected Research Topic You have options to select a research project on your own. However, the proposed project must have a focus on security and privacy issues. You proposed project is also subject to my approval to move forward. Self-selected research topic could be your job-related projects. Project deliverables: • Project middle report • Project final report • Project presentation slides • Other related project documents If you want to extend the class project to a yearlong project (if you are also in one of my classes next semester), please indicate in your project middle report too. I will work with you to define project scope so that we can achieve more outcomes after the project is completed. Project Advising Class project is a good opportunity to demonstrate your understanding of the subject material and your abilities as a researcher. You are encouraged to discuss your project ideas with me. For campus students, we could set up regular meetings to discuss your projects. For distance students, you are welcome to discuss your projects with me through emails, phone calls, or skype. My contact information has been listed below. Please make appointment if you want to talk to me online. • Office: East Hall Room 332 • Email: [email protected] • Phone: 605-221 8193 Project Middle Report Format • 12-point standard font • Single column • Double spacing • 3-5 pages (citation pages do not count) Project Final Report Format • 12-point standard font • Single column • Double spacing • An extension of the middle report • 10 pages minimum (title and citation pages do not count): project final report is a complete report of your class project. Project final report can be extended from your middle report. Project Presentation (TBD) On-campus students are required to give project presentations in the end of the semester. Students choosing the case studies are required to make videos presenting their work. The rest of students are not required to do the presentations but are welcome to present their projects via videos or online collaboration tools such as Google Hangouts and Skype. Presentation slides are required for all the students as part of the project deliverables. All project works should be submitted through D2L. If you work as a group, submit one report per group according to the requirement.
This assignment has in total 70 base points and 10 extra points, and the cap is 70. Bonus questions are indicated using the ⋆ mark. Please specify the following information before submission: • Your Name: Yufeng Xu • Your NetID: yx3038 Problem 1: Asymptotic analysis [7+7+7 pts] (a) Show that n! = ω(n0.99n). (b) Construct two functions f,g : N → R≥0 such that f(n) = O(g(n)) but neither f(n) = o(g(n)) nor f(n) = Θ(g(n)). Show the correctness of your construction. (c) Let f(n) = n0.6 and g(n) = 22⌊loglogn⌋. Show that none of the relations Θ, O, Ω, o, ω applies between f(n) and g(n). Solution. Please write down your solution to Problem 1 here. (a) want to show n! = ω(n0.99n) ⇐⇒ ∀c > 0,∃n0 > 0 | ∀n > n0,n! > cn0.99n n Next, we prove it by showing n! = ω(n 2 ) n! > cnn2 ⇐⇒ log1 + log2 + ··· + logn > logc + n logn where LHS = log1 + log2 +(b)let ) + 2, take b = 1,n0 = 1,∀n > n0,f(n) ≤ 1 · g(n), sof(n) = O(g(n)) However, f(n) ̸= o(g(n)) and f(n) ̸= Θ(g(n)) (i)If f(n) = o(g(n)), then ∀b > 0,∃n0 > 0 such that ∀n > n0,f(n) < b · g(n) Take b = 0.1, assume ∃n0 > 0 such that ∀n > n0,f(n) < 0.1 · g(n) Take ), contradictory to our assumption that f(n) < c · g(n). Therefore, f(n) ̸= o(g(n)) (ii)If f(n) = Θ(g(n)), then ∃a,b > 0 such that ∃n0 > 0,∀n > n0,a · g(n) ≤ f(n) ≤ b · g(n) Assume such a,b,n0 exist, take 1, therefore f(n) = 0,g(n) = 1 we also know a·g(n) ≤ f(n) ≤ b·g(n), therefore a = 0, contradictory to our essumption that a > 0. Therefore, f(n) ̸= Θ(g(n)) (c)Consider n = 22k,k ∈ N, then Consider n = 22k−1,k ∈ N, then (i)Assume f(n) = O(g(n)),∃b,n0 > 0 such that ∀n > n0,f(n) > b · g(n) However, take k = max{⌈log(logn0 + 1)⌉ + 1,⌈log(10 · logb + 6)⌉ + 1}, take n = 22k−1 > n0, then , which is contradictory to f(n) ≤ b · g(n). Therefore, f(n) ̸= O(g(n)), hence f(n) ̸= Θ(g(n)),f(n) ̸= o(g(n)). (ii)Assume f(n) = Ω(g(n)), ∃a,n0 such that ∀n > n0,f(n) ≥ a · g(n). Take n = 22 > n0, then , which is contradictory to f(n) ≥ a · g(n). Therefore, f(n) ̸= Ω(g(n)), hence f(n) ̸= ω(g(n)). None of Θ,O,Ω,o,ω apply to f(n) and g(n). Problem 2: Finding the maximum/minimum [10+10⋆ pts] For an array A of n different numbers (not necessarily sorted), we want to find the largest number and the smallest number in A simultaneously. However, we have no access to A. Instead, we are given an oracle Compare that can be used to compare the numbers in A. For i ̸= j, Compare(i,j) returns i if A[i] > A[j] and returns j if A[j] > A[i] (recall that the numbers in A are different by assumption, so we cannot have A[i] = A[j] if i ̸= j). For convenience, let us assume n is even. (a) Design an algorithm which calls the Compare oracle at most 2 times and returns a pair (imax,imin) such that A[imax] (resp., A[imin]) is the largest (resp., smallest) number in A. Give the pseudocode and briefly justify its correctness. (b)⋆ Show that any algorithm has to call the Compare oracle 2 times in worst case in order to find the largest and smallest numbers in A. Solution. Please write down your solution to Problem 2 here. (a) The pseudocode is shown below:Algorithm 1 pseudocode for problem 2.1max idx ← compare(0,1) min idx ← 1− max idx i ← 2 while i < len(A) do tmp max ← compare(i,i + 1) tmp min ← 2 · i + 1−tmp max max idx ← compare(tmp max,max idx) min idx ← tmp min+min idx −compare(tmp min,min idx) i ← i + 2 end while return (max idx, min idx)This algorithm compares the first two elements for 1 time. For every two elements in the next n − 2 elements of the array, the algorithm compares for 3 times. In total, the algorithm compares 2 times. Moreover, this algorithm is correct, because if we pick the larger number from every two numbers in the sequence, the global maximal number must be among this set. On the other hand, the global minimal number must be among the set of the smaller numbers from every two numbers. (b) Let A be the set of numbers that are possibly minimum but not maximum, B be the set of numbers that are possibly maximum but not minimum, C be the set of numbers neither possibly minimum nor maximum, D be the set of numbers both possibly minimum and maximum. Assume the size of the four sets are (nA,nB,nC,nD).Initially, we have (nA,nB,nC,nD) = (0,0,0,n). The ultimate goal is (1,1,n − 2,0). With direct comparison, there are 3 types of meaningful operations(all other operations contribute to this goal less efficiently): • (nA,nB,nC,nD) → (nA + 1,nB + 1,nC,nD − 2) • (nA,nB,nC,nD) → (nA − 1,nB,nC + 1,nD) • (nA,nB,nC,nD) → (nA,nB − 1,nC + 1,nD) It is not hard to see the second and the third operations must be done n−2 times in total, whereas the first operation should be done times. Therefore, the total number of comparisons is at leastProblem 3: Solving recurrences [4×5+9 pts] (a) Find big-Θ bounds for the following recurrences (and show your bounds are correct). For the base case, simply assume T(n) = 1 for all n ≤ 2.(b) Recall the Fibonacci sequence F0,F1,F2,… defined using the recurrence Fn = Fn−1 + Fn−2 with the base case√ F0 = 0 and F1 = 1. Prove by induction that ϕn−2 ≤ Fn < ϕn for all n ≥ 1,where ϕ = (1 + 5)/2. Based on this, further show that Fn = Θ(ϕn). Solution. Please write down your solution to Problem 3 here. (a)(i) Let ), where a = 8,b = 3,f(n) = Θ(n1.5 log4 n) Because ∀p,q > 0,np = ω(logq n),log3 8 > 1.5, ∃ϵ > 0 such that f(n) = O(nlog38−ϵ) According to Master theorem, T(n) = Θ(nlog38) (ii)Assume (because( Therefore LHS > 6logn when c ≥ 12. √ √ p √ √ On the other hand, T(n) − 6logn − T(n − n) = (c n − 6)log(n) − c n − nlog(n − n). Let √ p √ √ c = 6, we want to show LHS < 0 ⇐⇒ ( n − 1)log(n) − n − nlog(n − n) < 0 ⇐⇒ 0. Let 3. There- √ p √ √ fore, f( n) − f( n − n) < 0 for n > 16, hence T(n) − T(n − n) < 6logn when n > 16. Thus √ T(n) = Θ( nlogn). (iii)View T(n) as a recursion tree. Assume the tree has k layers in total, the 0th layer has one node; the 1st layer has 2 nodes plus ; the 2nd layer has 4 nodes plus 2 the kth layer has 2k nodes with value 1, plus , where k = logn Therefore, . By integral test, ln( ) + 1. Therefore, ). Therefore, T(n) = Θ(nloglogn). (iv)View T(n) as a recursion tree. Assume the tree has k layers in total, the 0th layer has one node; √ √ the 1st layer has 5 nodes plus 2n; the 2nd layer has 25nodes plus 5 n · 2 n = 10n… the kth layer has 5 nodes with value 1, plus 2 · 5k−1n, where k = loglogn. Therefore, , where 5k = 5loglogn = 2log5·loglogn =, hence 5 ). Therefore, (b) (i) Check ϕ−2 ≤ F0 < ϕ0,ϕ−1 ≤ F1 < ϕ1. (ii) Assume for√ 1,2…k, ϕk−2 ≤ Fk < ϕk. Then Fk+1 = Fk +Fk−1 ≥ ϕk−2 +ϕk−3 = ϕk−3 ·(1+ϕ) =Hence ϕk−1 ≤ Fk+1 < ϕk+1. By induction, ϕn−2 ≤ Fn < ϕn for all n ≥ 1. (iii) Now we show that Fn = Θ(ϕn). We know Fn = Fn−1 + Fn−2, assume Fn − A · Fn−1 = (1 − A) · (Fn−1 − A · Fn−2), then 1 = −A · (1 − A), A2 − A − 1 = 0, hence or . Hence . We know that F0 = 0,F1 = 1, hence , where O(ϕn), hence Fn = Θ(ϕn). Problem 4: Counting intersection points [10 pts]Solution. Please write down your solution to Problem 4 here. The pseudocode for this problem is shown in the next page.Algorithm 2 pseudocode for problem 4.1procedure CountInt(n,A,B) A sorted ← sorted(A) ▷ sorted is implemented by merge sort, which is O(nlogn) B sorted ← sorted(B) rank ← zeros(n) ▷ zeros(n) returns an array of zeros of length n for i in range(1,n + 1) do rank[B sorted.rank(B[i])] = A sorted.rank(A[i]) ▷ rank applies binary search(O(logn)) and returns the rank of the target in a sequence. end for procedure DivConq(m,arr) if m ≤ 1 then return 0,arr end if mid ← m/2 m ← len(arr) inv1,arr1 ← DivConq(mid,arr[: mid]) inv2,arr2 ← DivConq(mid,arr[mid :]) inv ← inv1 + inv2 i,j ← 1 res ← emptylist while i ≤ len(arr1) do if arr1[i] < arr2[j] OR j > len(arr2) then res.append(arr1[i]) i ← i + 1 inv ← inv + j − 1 else res.append(arr2[j]) j ← j + 1 end if end while return inv,arr end procedure cnt,arr ← DivConq(n,rank) return cnt end procedureThis algorithm applies merge sort 2 times and binary search 2n times, which is O(nlogn). In DivConq, the sorting of arr1 and arr2, two sorted arrays, is O(n). In total, the time complexity of DivConq is O(nlogn). Therefore, the time complexity of the whole algorithm is O(nlogn). Next, we will show the correctness of this algorithm. We know if ai < aj,bi > bj, then there’s an intersection between aibi and ajbj. In other words, the task of counting intersection is equivalent to counting inversed pairs. # inversed pairs in a sequence is equivalent to # inversed pairs within its left part and right part, plus # inversed pairs across the two parts, i.e., for each entry x in the left part, how many entries in the right part are smaller than x. By sorting arr1 and arr2, this algorithm keeps the returned array sorted and counts how many inversed pairs are there across the left and the right part.
Description You will be creating a website allowing users to pick a Pokemon and get more info about the pokemon, as well as to see which pokemon have a certain ability. Setup We recommend using the same virtual environment for all projects, so you can use a common one created in CMSC388J-spring22/, the root of the class repository. Once you have a virtual environment, activate it, use the appropriate command for your system. Then, to install the necessary packages, navigate to p2/ and run pip3 install -r requirements.txt. Alternatively: pip3 install Flask requests python-dotenv. More detail on virtual environments are on the slides. For this project, we’ll be using the requests, Flask, and python-dotenv packages. If you ran the above command to install from requirements.txt, you’re all set. Project The project will not run in its starter form, because not all of the routes have been configured yet. To run your project after making some progress, refer to the Testing section below. In model.py, we’ve defined a class named PokeClient. In app.py, we create an instance of the class. This is the only instance of the class that you need. You should not modify the PokeClient class. Look at the methods in the class definition; you can call these methods with dot syntax, i.e. poke_client.get_pokemon_list() or poke_client.get_pokemon_info(self, ‘bulbasaur’). In model.py, we’ve included sample usages of the PokeClient class. If you run the model.py class directly with python model.py, you’ll see the output corresponding to each print statement in your console. We provided a base.html file from which you should extend all of your other templates. There’s an example index.html file that just displays “Poke-Info website!” when the website is first opened. You should create two more templates (so you will have a total of four HTML templates when the project is finished) for the Pokemon info and ability info pages. These pages are explained below. Implement the following functions with the corresponding routes: 1. index() – Should show a list of all Pokemon, with links to pages that give more info The list of pokemon should be seen at the route /. Each element in the list should be a link to another page which will give more info about the chosen Pokemon with a certain name. The additional Pokemon info page should be located at /pokemon/. You can get a list of Pokemon names with the get_pokemon_list() method of the PokeClient class. 2. pokemon_info(pokemon_name) – Should show all info about the specified Pokemon. We should be able to navigate to /pokemon/ and see info about the Pokemon identified by pokemon_name. The info includes the name, weight, and other data. The get_pokemon_info() method of the PokeClient class returns a dictionary with all of the info that you need. The dictionary of info will have a list of names of abilities. Each of these abilities must be presented as a clickable link to another page, located at /ability/. There should be a clearly visible link to go back to the front-page of the website, located at /. 3. pokemon_with_ability(ability_name) – Should show a list of Pokemon who have the specified ability. We should be able to navigate to /ability/ and see a list of Pokemon names identifying Pokemon that have the ability specified by ability_name. The get_pokemon_with_ability() method of the PokeClient class returns a list of Pokemon names with the ability. The list of Pokemon names should be presented as a series of clickable links that will take the website user to the info page for that Pokemon, located at /pokemon/. There should be a clearly visible link to go back to the front-page of the website, located at /. Reminder: Make lists in HTML by using what we went over in class. Testing When your current directory is flask_app/, you can simply run the command flask run in your terminal or command line to see your website. It’s important to be in the flask_app/ directory so that you can use the values set in the .flaskenv file automatically. The .flaskenv file makes it so that you don’t have to set the FLASK_APP environment variable manually and the environment is set to development so that errors will be shown in the browser instead of crashing your app. Additionally, if you reload the page when in the development mode, you can see the changes made to your website without having to manually shut down the running app and restarting it. Run your flask app, make sure you have a long list of Pokemon names that are links, and try clicking on some of them to see if the correct info page pops up. Try clicking on one of the abilities under each Pokemon to see if you get working links to the Pokemon with that ability. Check that you have a link clearly visible on the page for Pokemon info and ability info to go back to the frontpage of our website. If you check a few pokemon and abilities throughout the entire list, you should be fine, because its fairly certain that your logic is sound at that point. Submissions Make sure that you’ve tested parts of your website and that links to the frontpage exist and are clearly visible, and then zip the flask_app/ directory. The directory, along with its contents, should be zipped, not the contents of the directory. In other words, when we unzip your file, we should see the flask_app/ directory. If you have any questions on how to submit, please contact us. Grading After zipping, submit the zip file to the appropriate ELMS page. No test results will be shown. Your project will be graded according to (1) correctness, and (2) robustness. Here are the correctness requirements: Correctness: | Requirement | Points | | ——————————————————————————————————————— | — ————– | | All Pokemon visible on front page as clickable links, with no duplicate info. | 15 | | All Pokemon info returned from the PokeClient class is visible on the respective info page, with no duplicate info. | 20 | | All Pokemon names visible and presented as links to Pokemon info pages on the ability pages, with no duplicate info. | 15 | | Link on Pokemon and ability info pages to the front page clearly visible and works. | 10 | | Two more templates created for the Pokemon and ability info pages extending base.html | 10, (5 for each) | | Correct routes in app | 10 | | url_for used to create links and render_template used | 10 | | Jinja2 control flow statements used to dynamically create HTML in template files. | 10 | Robustness: An example of a small error: syntax error in a Jinja template. An example of a large error: a view function not being configured properly. The project will be graded out of a 100 points. You won’t be graded for style, but make sure your code is readable.
Description You will be implementing some basic functions in Python as practice, including using iterators and built-in functions. Setup Make sure Python 3.10 is installed on your computer. You should work on this project (and the other projects in this course) in a virtual environment. Navigate to the root of a directory you will use for this class. You should use the same environment for all projects in this course; you don’t need more than one. To create and activate one, enter the following commands in your terminal: For Mac/Linux: bash $ python3 -m venv venv # creates environment $ source ./venv/bin/activate # enters environment For Windows: bash $ py -m venv venv # creates environment $ ./venv/Scripts/activate # enters environment These instructions can also be found in the Week 1 slides. Testing this project with our public tests requires a package called pytest. To install it, run either of the following in your terminal while in your virtual environment: bash $ pip3 install -r requirements.txt bash $ pip3 install pytest Again, you must be in your virtual environment when installing packages with pip. Project In practice.py, implement the following functions: 1. hello_world() Return the string Hello, World! 1. sum_unique(l) Given a sequence of integers, return the sum of the integers, not counting duplicates, i.e. if you have two or more copies of an integer, it should be added to the final sum once. Examples: “`python sum_unique([]) 0 sum_unique([4, 4, 5]) 9 sum_unique([4, 2, 5]) 11 sum_unique([2, 2, 2, 2, 1]) 3 “` 1. palindrome(x) Given an integer or a string x, determine if x has the same value as x reversed. Examples: “`python palindrome(1331) True palindrome(‘racecar’) True palindrome(1234) False palindrome(‘python’) False “` 2. sum_multiples(num) Given a positive integer num, find the sum of all multiples of 3 and 5 upto and not including num. Examples: “`python sum_multiples(10) # Multiples: [3, 5, 6, 9] 23 sum_multiples(3) # Multiples: [] 0 sum_multiples(5) # Multiples: [3] 3 sum_multiples(16) # Multiples: [3, 5, 6, 9, 10, 12, 15] 60 “` 3. num_func_mapper(nums, funs) Given a sequence of numbers nums and a sequence of functions funs, apply each function to nums and store the result in a list. Return the list of results. Hint: The list of results should be the same length as funs. Example: “`python f_list = [sum_unique, sum] num_list = [2, 2, 2, 4, 5] num_func_mapper(num_list, f_list) [11, 15] “` 4. pythagorean_triples(n) Finds all pythagorean triples where a, b, and c (side lengths of a triangle) are all less than n units long. This function should not return distinct tuples that still represent the same triangle. For example, (3, 4, 5) and (4, 3, 5) are both valid pythagorean triples, but only the first should be in the final list. The tuple elements should be sorted in ascending order, and the list of tuples should be sorted in ascending order by the last element of the tuple. Examples: “`python pythagorean_triples(10) [(3, 4, 5)] pythagorean_triples(11) [(3, 4, 5), (6, 8, 10)] pythagorean_triples(20) [(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17)] “ 7.custom_sort(lst)` Use Python’s built-in sort function to sort the list so that the odd numbers (in the same order as in the original list) come first, and then the even numbers (also in the same order). Examples: “`python custom_sort([1, 2, 3, 4, 5]) [(1, 3, 5, 2, 4)] “` (Hint: use a lambda function) Testing Navigate into the p1/ directory and run the command pytest. You should see your test results in the terminal. Submission & Grading Compress a p1 directory into a .zip file containing practice.py and test_practice.py and submit it on ELMS after testing thoroughly; all of your work should be in this module. Do not include your virtual environment in your submission. There are 130 possible points: 13 public tests worth 10 points each. If your submission doesn’t have the practice.py and test_practice.py files, 20 points will be deducted from your score. If you include your virtual environment in your submission, 20 points will be deducted from your score.
Instructions Submission How to get the data: STAT40830 – Final Project Author Isabella Gollini This final project is based on the material up to topic 9. Instructions Create a Shiny app to read and summarise the Human Development Indicators data. The Shiny app must allow for the following: 1. Allow the user to select data for at least one country given the countries names. 2. Change the title depending on the country/countries selected. 3. Display a table with part of the data. The user must be able to select the number of rows and the columns to be displayed. 4. Produce two different plots showing different information each. The user must be able to change at least 3 input in each plot. 5. The shiny app must have built-in data for at least 5 different countries. 6. The shiny app must allow the user to upload any extra Human Development Indicators dataset (hdro_indicators_COUNTRYNAME.csv) downloaded from data.humdata.org from any available county (You can assume that all files have the same structure). Some notes: Notice that you can re-use some code you created for Assignment 1, Assignment 2, or create it from scratch. You can use functions from any R packages. Remember that in your Shiny app you must never have any file path specific to your computer. Submission Submission: upload on the Final Project assessment on Brightspace a zip file containing: 1. all the files needed to build the Shiny app (either R script or qmd files and the data), (Submissions where we cannot reproduce the Shiny app will be capped at 30 points (i.e. 50% of the final grade for this final project)) Note that only your final submission will be marked. How to get the data: (Same as Assignments 1 and 2) For the final project you will have to use the dataset of the Human Development Indicators for at least different countries of your choice from data.humdata.org/dataset/?organization=undp-human-development-reportsoffice&q=Human+Development+Indicators: Click over COUNTRYNAME – Human Development Indicators and download the dataset called Human Development Indicators for COUNTRYNAME it will give you a .csv file. (The dataset contains the following variables: country_code, country_name, indicator_id, indicator_name, index_id, index_name, value, year.) repeat this procedure for at least a second country.
Instructions Submission How to get the data: STAT40830 – Assignment 2 Author Isabella Gollini This assignment is based on the material up to topic 7. Instructions Write an R package to read and summarise the Human Development Indicators data. The R package must contain the following: 2. The output from the main function must belong to a new class 3. One printing method for the new class 4. One summary method for that class 5. One plot method for that class 6. You must provide documentation for the main function, and the R package you created. 7. One vignette showing how the main function and the three methods work with at least two dataset. Some notes: Notice that you can re-use some code you created for Assignment 1, or create it from scratch. In your functions/methods you can use functions from any packages. Remember that in an R package you must never have any file path specific to your computer. You can assume that the original data are downloaded in the working directory. Submission Submission: upload on the Assignment 2 assessment on Brightspace a zip file containing: 1. the package source (tar.gz) ( devtools::build), 2. the pdf manual (devtools::build_manual) 3. and the html or pdf vignette (devtools::build_vignettes()). Note that only your final submission will be marked. How to get the data: (Same as Assignment 1) For Assignment 2 you will have to download the dataset of the Human Development Indicators for at least different countries of your choice from data.humdata.org/dataset/?organization=undp-human-development-reportsoffice&q=Human+Development+Indicators: Click over COUNTRYNAME – Human Development Indicators and download the dataset called Human Development Indicators for COUNTRYNAME it will give you a .csv file. (The dataset contains the following variables: country_code, country_name, indicator_id, indicator_name, index_id, index_name, value, year.) repeat this procedure for at least a second country.
Instructions Submission How to get the data: STAT40830 – Assignment 1 Author Isabella Gollini This assignment is based on the material up to topic 4 (mostly about topic 4). Instructions Write a slide presentation (15-20 slides) by completing the tasks below on the Human Development Indicators data on at least two countries. (Below you will find instructions on how to download them). Use only the R package data.table unless when explicitly stated. 1. Use data.table to read in the data and assign the correct class to the variables. 2. Merge the data datasets using data.table. 3. Do some quick data exploration to know more about your data. (You are allowed to use any R package to answer this question) 5. Do at least 2 plots using some output from the analysis done in step 4. (You are allowed to use any R package to answer this question). Complete your assignment creating a Quarto presentation, check that all code and output are correctly displayed in your final document. You must add some extra not-default options to personalise the aesthetic of the slides. Upload the .css or the .tex file if use them for the personalisation. Write some prose to explain what you intend to do at each step. Remember that the code should be easy to read and to work with. You should add appropriate comments, make code efficient and use sensible notation. Submission Submission: upload on the Assignment 1 assessment on Brightspace your .Qmd file, and a rendered .pdf file of the resulting output. The .pdf file should function as a standalone file for this assignment – that is, it should show all necessary code to find answers, produce plots etc. Code needed to set things up, e.g. loading packages etc. can be hidden to make the final rendered document neater. Upload the .css or the .tex file if use them for the personalisation. Note that only your final submission will be marked. I must be able to render your .Qmd as it is, so don’t use any file path specific to your computer. You can assume that the original data are downloaded in the working directory. How to get the data: For Assignment 1 you will have to download the dataset of the Human Development Indicators for at least different countries of your choice from data.humdata.org/dataset/?organization=undp-human-development-reports-office&q=Human+Development+Indicators: Click over COUNTRYNAME – Human Development Indicators and download the dataset called Human Development Indicators for COUNTRYNAME it will give you a .csv file. (The dataset contains the following variables: country_code, country_name, indicator_id, indicator_name, index_id, index_name, value, year.) repeat this procedure for at least a second country.
• This assignment has a total of 100 points. • Please write your answer in the white space to the right of the corresponding problem. 1 Choose all that Apply – 4 x 6 points 1. What devices can be considered as an end system in the network? (a) PC (b) wireless laptop (c) web server (d) mobile phone 2. Consider two hosts A and B transmit packets through three routers S1, S2, S3. Suppose the rates of the A − S1, S1 − S2, S2 − S3, and S3 − B links are R1, R2, R3, and R4, respectively. Let R1 < R2 < R3 < R4. What should the throughput between A and B be? (a) R1 (b) R2 (c) R3 (d) R4 3. Consider a router transmitting a packet of 15KB to another router on the same universitycampus, at a data rate of 10 Mbps. Assuming delay is expressed as n·10−k (seconds), where 1 ̸= n 1, no packet will be dropped at queue. (b) If average La/r > 1, no packet will be dropped at queue. (c) If average La/r decreases, average waiting time will decrease. (d) When La/r approaches to 0, the average waiting time will also approaches to 0. (e) When La/r increase and approaches 1, the average waiting time will increase linearly. 6. A network administrator tells you that at most 800 users can be accommodated by statistical multiplexing, given that each user needs 1 Mbps bandwidth and has a 20% chance of being active. This means, the total bandwidth is no less than (choose from a and b). With TDM, 800 such users (choose from c and d) be accommodated. (a) 200 (b) 160 (c) might not (d) can surely 2 Probability and Throughput – 6 x 3 points Suppose that 3 users are sharing a 300 Mbps connection. Each user uses the link 20% of the time. Assume their internet access activity is independent from each other and the network use is distributed uniformly. 1. What is the probability that no user is using the link simultaneous at the given time? 2. What is the probability that two users are using the link simultaneous at the given time? 3. Suppose that you want to use the link. Assume that when two or more people use thebandwidth are divided fairly among them. What is the average bandwidth you will receive? 3 Delays – 5 x 5 points 1. Explain the difference between transmission delay and propagation delay. 2. Suppose a router processes packets at the rate R=1 packet per second. Packets arearriving into the router’s queue at time ticks (in seconds) shown in the table below. Compute (A) the average packet throughput in the first 10 seconds(B) the average queuing delay. Please only type in the final result in the text box. (Round your answer to 2 decimal places)Average packet throughput: Average queueing delay:Average packet throughput: Average queueing delay: (For the following questions) Consider two hosts, A and B, that are connected by switch S. The link A-S is 100Mbps and has a propagation delay of 10ms. The link B-S is 80Mbps and has a propagation delay of 30ms. (1B = 8 bit, Assume 1KB = 1000B, 1MB = 1000KB) 3. Assume that no processing delay. If A sends a 1MB packet to B, what will the end-to-enddelay be? 4. Suppose A sends 20 100KB packets to B continuously. Suppose S has a 500KB bufferfor packets, will the packet be dropped? 5. Assume the buffer is infinite. A sends 100KB packets continuously. How long willit take for A to send 100MB. What is the average throughput? 4 Bandwidth, data rate and SNR- 5 + 3 + 5 points Shannon’s ground breaking equation says that: C = Blog2(1 + SNR) where C is the data rate in bits/s achievable on the communication link (also called capacity), B is the bandwidth in Hz, and SNR is the ratio of received signal power to the receiver’s noise power. Assume that the received signal power density where R is the distance between sender and receiver. 1. Suppose a laptop tends to transmit to a WIFI station located 10m away. Assume signalpower density measured 2 meters from the laptop is Q = 12milliWatt/m2 and the noise power density at the receiver is N = 0.01milliWatt/m2. Suppose the laptop transmits at a bandwidth of 20MHz, what data rate can it achieve? (round your answer to 3 decimal places) 2. List at least two methods that can increase the data rate. 3. If the laptop intends to triple its data rate, how close should it move to the WiFi station?Assume all the other conditions are the same. (round your answer to 3 decimal places) 5 Internet concepts – 10 + 10 points 1. Mark all statements that are correct based on the classical principles of the networkprotocol stack: (-2pt per option wrong until 0) (a) HTTP, SMTP, FTP are application layer protocols. (b) All Internet components that have a network layer must run the IP protocol. (c) The Transportation layer header can be read and modified by the router. (d) The Network layer header can be read and modified by the router. (e) Transport, Network, Link, and Physical layers are implemented at the core routers (f) Suppose you send an email to your friend in another country, and your packets’ link layer header does not contain your friend’s link-layer address. (g) Reducing the size of headers improves the goodput of the network 2. Briefly answer the following questions. (a) List at least one advantage and disadvantage of protocol layering. (b) Why will two ISPs at the same level of the hierarchy often peer with each other? How does an IXP earn money?
EXPERIMENT #2 Data Storage I. OBJECTIVE In this experiment, you will design and construct a simple 2-bit, four-word shiftregister storage unit.II. INTRODUCTION Conceptually, random access memory (RAM) is a storage device arranged as a set of binary words that can be individually identified and accessed using unique addresses (see Figure 1). STORAGESAR address contents 101 word 0 0110 word 1 1100 SBR word 2 0000 1110 word 3 0000 word 4 0000 FETCH word 5 1110 word 6 1101 STORE word 7 0000Figure 1: An Eight-word Storage Unit Using 4-Bit Words To fetch a word from storage, the unique word address is placed in the Storage Address Register (SAR) and a FETCH signal is sent. The binary string or a content of the specified word appears in the Storage Buffer Register (SBR) a short time later (exactly how much later depends upon the technology used for the storage). To store a word into storage the unique word address is placed in the SAR, the binary data to be stored is placed in the SBR, and a STORE signal is sent. The binary data in the SBR is stored in the word whose address is specified in the SAR. The previous contents of the word are destroyed by the STORE operation. Cathode ray tubes, delay lines, and magnetic cores were once used for storage. In the 1970s, this was replaced by semiconductor RAMs, which are common now. You should be able to construct a storage unit from parallel-in/parallel-out shift registers, multiplexers, counters, and combinational logic. One storage technique uses serial-in/serial-out (SISO) shift-registers shifting synchronously. A single 1024-bit SISO shift register could be used to provide 1024 words of storage, where each word is a single bit (e.g. a 1024×1 RAM). Note that with a 1024-bit SISO shift register, only the output of the rightmost flip-flop and only the input to the leftmost flip-flop are available. In theory, a shift register can be built at much lower cost compared to a RAM. This is because there are far fewer pins and interconnections in shift register than in RAM. In addition, the storage cell of a shift register could be very simple, a capacitor for example. The shift operation is simply moving charge from one capacitor to the neighboring capacitor. Such shift registers are called Charge Coupled Devices (CCDs). Today, CCDs are primarily used in imaging applications, such as in digital cameras. The charge in a cell slowly decays and therefore must be refreshed before it is lost. For this reason a SISO memory based on CCDs must be continuously shifted to keep the information from being lost. Words larger than a single bit can be constructed by using more 1024-bit shiftregisters clocked synchronously. Typically, 16 such SISO shift registers would be used to construct 1024 words of storage, where each word is 16 bits long. More generally, an n-bit, m-word shift-register storage consists of n m-bit shift-registers shifting together (see Figure 2).m words Figure 2: Configuration of a Shift-register StorageAs mentioned earlier, an alternative to the above storage devices are those devices that are built with “static” logic elements (SRAM). This is a setup where the storage device can retain data so long as a specified supply voltage is maintained. These SRAM chips are readily available from a number of manufacturers with varying features and parameters.III. PRE-LAB Signal Definitions: LDSBR When LDSBR is high, the SBR is loaded with the data word DIN1, DIN0. FETCH When FETCH is high, the value in the data word specified by the SAR is read into the SBR. STORE When STORE is high, the value in the SBR is stored into the word specified by the SAR. SBR1, SBR0 The data word in the SBR; either the most recently fetched data word or a data word loaded from switches (note that when none of the LDSBR/FETCH/STORE switches is set, SBR should maintain the data in it) SAR1, SAR0 The address, in the SAR, of a word in the storage DIN1, DIN0 Data word to be loaded into SBR for storing into storage To design the shift-register storage unit, we first need to look at the required specs. The most crucial requirement is for the shift registers to shift continuously, while using the serial input and output to store and fetch the data. We can break down our circuit operation into four operations: load, read, write, and do nothing. Let’s first imagine the scenario where the circuit is turned on, but we are neither loading, reading nor writing. This is the most common state of the circuit, where no action is taken from the user – do nothing. Our requirements dictate that the shift registers must continuously shift, where any potentially stored data will be shifted out of the registers and into the void. To prevent losing any data, we will need to redirect the data shifting out of the registers back by connecting the serial output of the registers to their serial input, where the stored data will now be looping continuously in the shift registers. However, during a write operation, we do want to replace the old data with new data. To serve both purposes, a 2-to-1 multiplexer (MUX) can be placed at the serial input of the shift registers, taking either the new data or the old data depending on the current operation. But what is the ‘current operation’ at any given moment? Surely the desired operation is dictated by the user using the switches, but the inputs alone is not sufficient to tell each part of the circuit what to do. For example, if you would like to read from a specific address in the shift registers, you would first set the SAR to the specific address then you would hit the FETCH switch. But since the shift registers are constantly shifting data in and out of their serial ports, when exactly do you load the data into the SBR? How do you exactly tell what input the MUX should choose from? To solve the various problems associated with controlling and timing, it is generally not a good idea to use the inputs to directly control the various circuit components. Rather, it is almost always desired to have a centralized control logic that takes in all the inputs, process the request, and sends out various signals to control the circuit components. Figure 3 shows a general block diagram for the proposed circuit design. The most common form of a control logic is a state machine, which we will discuss in the next experiment. In this experiment, we will improvise a simpler control logic based on the requirements of our specific circuit. First, notice that our shift registers are four word long, that is, each data will take exactly four shifts/clock cycles to loop back to its original location. We can exploit this property by employing a 2-bit counter (four distinct values) to keep track of the internal data address, then use a comparator to match the internal address with the SAR. Note that since the register is always shifting, it is meaningless to indicate “absolute” storage addresses. Rather, all addresses are “relative.” If you wish to store data X in address Y, you can write the data into a random cell Z when the internal data address from the 2-bit counter matches the SAR. This (previously arbitrary) cell Z will now be associated with the address Y. Later, when we wish to fetch from address Y, we wait for the internal counter to match the SAR again – that is when cell Z once again becomes available for reading or writing. Another interpretation that might be useful is that the counter always keeps track of the address associated with data to be shifted out from serial output/into serial input of the shift register array at the up-coming clock edge. Note that to control the MUXs, the ‘select’ signals generated by the control logic has to take into account of the input switches and the comparator output (to indicate if we are currently looking at the correct address for reading/writing).Figure 3: Block diagram of the shift-register storage unit. Your pre-lab writeup should contain a written description of your circuit operation, a block diagram, operation of the controller, a logic diagram and layout documentation. HINT: Use the Pulse Generator to provide a basic clock. Continuously clock the shift-register and a counter that keeps track of which word is currently available. Use combinational circuitry (or 74LS85) to check for a match between the available word and the SAR. B. Meet with your lab partner and wire up and test your design before coming to the lab. Use either the mini-switchbox circuit that you built at the end of Lab 1 (detailed in the General Guide) or attend an open lab session to test your circuit with the real switchbox. Only the clock input needs to be de-bounced to strep through your circuit (why?). Demo Points Breakdown: 1.0 point: When LDSBR is high, the data in DIN is loaded from the switches into SBR 1.0 point: When STORE is high, the contents of the SBR are stored into the location specified in SAR 3.0 points: When FETCH is high, the data word specified by the SAR is read into the SBRIV. LAB Follow the Lab 2 demo information when debugging is completed.V. POST-LAB 1) Your post-lab writeup (notes) should contain a corrected version of your prelab writeup and an explanation of any remaining problems in the operation of the circuits. This will aid the writing of your lab report. 2) Discuss with your lab partner and answer at least the following questions in your lab report: • What are the performance implications of your shift register memory as compared to a standard SRAM of the same size? • What are the implications of the different counters and shift register chips, what was your reasoning in choosing the parts you did?VI. REPORT In your lab report, should hand in the following: • An introduction; • Written description of the operation of circuits from the pre-lab; • Block diagrams for part A; • Design steps taken for all circuits. This includes but not limited to design considerations on the SBR MUX, the Shift Register MUX, and the control logic. Truth tables/K-maps leading to the final circuit design should be included (if any); • One (1) component layout sheet, with the package layout of all circuits (DO NOT draw the interconnections! Refer to GG.20 for the proper documentation); • Circuit diagrams for all circuits; • Requested documentation from the lab; • A conclusion regarding what worked and what didn’t, with explanations of any possible causes and the potential remedies. • See also, refer to the report checklist linked on the course website.
In the world of Mortal Kombat, the ultimate battle between Scorpion and Sub-Zero is about to commence in the Earth realm. The air is thick with tension as these two legendary warriors prepare to face off in a fight to the death. Both fighters are masters of their respective arts, each with a full health bar, ready to unleash their fury upon one another. In this brutal, turn-based clash, the warriors will alternately strike at their opponent and ensure victory.As the battle unfolds, every turn counts. Will it be Scorpion, with his fiery vengeance, who claims victory? Or will Sub-Zero’s icy precision lead him to triumph? The outcome depends on the initial setup: who strikes first, and how powerful their moves can be.Your task is to simulate this epic showdown given the initial conditions – who starts the battle and determines who emerges as the victor. Prepare yourselves, for this is Mortal Kombat, where only one warrior will be left standing. Round 1, Fight!Game Description & Rules: ● Players: Scorpion and Sub-Zero. ● Turn-Based Gameplay: Players take turns to attack. ● Turns: The player specified by the first input number will take the first turn in the first round. The player who didn’t take the first turn in the previous round will start in subsequent rounds. ● Assume the branching factor = 2 and the max depth of the game tree = 5 ● You have to create the appropriate number of leaf nodes and assign them utility values (-1 if scorpion wins, and 1 if sub-zero wins)Input ● One single-digit number. The number indicates which player starts first (0 for Scorpion, 1 for SubZero). Output ● The name of the game-winner. ● The number of rounds played. ● The winner of each round. Sample Input: 0 Sample Output: Game Winner: Scorpion Total Rounds Played: 3 Winner of Round 1: Sub-Zero Winner of Round 2: Scorpion Winner of Round 3: Scorpion Now apply the alpha-beta pruning algorithm to simulate the problem and find the winner.Part 2: Games with Magic [5 Points] In a strategic game simulation, Pacman and a ghost engage in a sequence of moves across three levels of depth. The competition starts with Pacman aiming to reach a power pellet by making the first move. The ghost then attempts to thwart Pacman’s progress at the second level, followed by Pacman’s final moves to reach the pellet at the leaf nodes, where the outcomes are scored as 3, 6, 2, 3, 7, 1, 2, 0. An added strategic element is Pacman’s ability to wield dark magic, allowing him to control the ghost’s move at a specific cost, c. This cost is deducted from his score, influencing his overall strategy to reach the pellet. You are tasked with developing the function pacman_game(int c) to determine the most effective strategy for Pacman, considering whether the use of dark magic, given its cost, is beneficial.Input (c) Output 2 The new minimax value is 5. Pacman goes right and uses dark magic 5 The minimax value is 3. Pacman does not use dark magic In sample output 1, the left subtree has the highest value 6 and the right subtree has the highest value 7. If Pac-Man moves to the left and uses dark magic the result will be 6 – 2 = 4, If Pac-Man moves to the right and uses dark magic the result will be 7 – 2 = 5.And now, using Alpha-beta pruning find the final value of the root node without using dark magic. Then check whether using dark magic is advantageous for Pac-Man or not.[Hint: The final value of the root node will be 3. So using dark magic is advantageous for Pac-Man in both directions, but it’s more beneficial when Pac-Man goes right.]Part 3: Food for thought [0 Points]● Is the first player always a maximizer node? ● Can alpha-beta pruning handle stochastic environments?
PROBLEM SCENARIO CO1 On holiday, a flight currently wants to travel to Bucharest from Arad. But there is no direct way to Bucharest from Arad. However, the cities are connected with each other like a graph. The distance between the connected cities are given. The flight wants to travel through the most optimal way. To find the optimal path to travel, another information is provided: the straight line distance between any city and the final destination (Bucharest). Now apply A* search to determine the most optimal value for the route Arad to Bucharest and help the flight. You have to use the straight line distance as the heuristic value for the cities.City Heuristic value City Heuristic value Arad 366 Mehadia 241 Bucharest 0 Neamt 234 Craiova 160 Oradea 380 Eforie 161 Pitesti 100 Fagaras 176 Rimnicu Vilcea 193 Dobreta 242 Timisoara 329 Hirsova 151 Urziceni 80 lasi 226 Vaslui 199 Lugoj 244 Zerind 374For simplicity assume these notationsArad A Neamt F Bucharest Z Oradea B Craiova S Pitesti P Eforie T Rimnicu Vilcea R Fagaras O Timisoara C Dobreta V Urziceni D Hirsova N Vaslui H lasi Q Zerind E Lugoj G Mehadia LINPUTS Your txt file should take each node followed by each destination it can reach and their corresponding distance and heuristics. You are to read the file then ask the user to input the starting and the destination point.OUTPUTS The output will contain the total distance from the starting point to the destination followed by printing the nodes it followed to calculate the distance.SAMPLE INPUT In the text file:Arad 366 Zerind 75 Sibiu 140 Timisoara 118 Zerind 374 Arad 75 Oradea 71 Oradea 380 Zerind 71 Sibiu 151 … … … … … … Bucharest 0 Pitesti 101 Fagaras 211 Giurgiu 90 Urziceni 85 Giurgiu 77 Bucharest 90 … … … … … …The text file is arranged as follows:Each line starts with a node followed by the heuristic of that node Then the neighboring nodes and the distance from the parent node is given as a pair All neighboring city-distance pairs are listed after the heuristic.For example, the text file starts with Arad which has a heuristic of 366. It is the parent node to Zerind, Sibiu and Timisoara which are 75, 140 and 118 km away from Arad. Notice that since Bucharest is the End node which is why it has a heuristic of 0.In console: Start node: Arad Destination: BucharestSample output Path: Arad -> Sibiu -> Rimnicu -> Pitesti -> Bucharest Total distance: 418 kmIf there is no path found from the Start node to the End node, simply print “NO PATH FOUND”
a. Construct the joint probability distribution table for the variables Color (C) and Size (S). b. Calculate the joint probability P(C=Red,S=Large). c. Calculate the marginal probabilities P(C=Red) and P(S=Large). d. Determine whether the preferences for Color and Size are independent. e. What is the conditional probability that a respondent prefers a Small size given that they chose Red color P(S=Small∣C=Red)? ● 40 students preferred the Library in the Morning with a Quiet environment. ● 20 students preferred the Library in the Morning with Moderate noise. ● 30 students preferred the Library in the Evening with a Quiet environment. ● 10 students preferred the Library in the Evening with Moderate noise. ● 25 students preferred the Cafe in the Morning with Quiet environment. ● 15 students preferred the Cafe in the Morning with Moderate noise. ● 45 students preferred the Cafe in the Evening with a Quiet environment. ● 15 students preferred the Cafe in the Evening with Moderate noise. Questions: a. Create a joint probability distribution table for the variables Location (L), Time of Day (T), and Noise Level (N). b. Calculate the joint probability P(L=Cafe,T=Evening,N=Quiet). c. Calculate the marginal probabilities P(L=Library), and P(N=Quiet). d. Determine if the factors Location, Time of Day, and Noise Level are independent. Hint: Check if P(L=Library,T=Morning,N=Quiet)=P(L=Library)P(T=Morning)P(N=Quiet). e. What is the conditional probability that a student prefers the Library given that it is Morning and the environment is Quiet P(L=Library∣T=Morning,N=Quiet)? 4. Suppose we have three events A, B, and C within a probability space. The events A and B are known to be conditionally independent given C. This means that P(A∩B∣C)=P(A∣C)×P(B∣C). Given the following probabilities: ○ P(A∣C)=0.4 ○ P(B∣C)=0.5 ○ P(C)=0.2 Calculate the probability P(A∩B∩C). 5. Let A, B, and C be events in a probability space, where A and B are conditionally independent given C. Assume the following probabilities: ○ P(A∣C)=0.3 ○ P(B∣^C)=0.6 ○ P(C)=0.5 Calculate: P(A∩B∣C), P(A∩B∣^C) assuming A and B are conditionally independent given ^C with P(A∣^C)=0.2. 6. In a medical study, events A, B, and D represent having disease A, disease B, and taking drug D respectively. It is known that having disease A and B are conditionally independent given the use of drug D. The probabilities are given as: ○ P(A∣D)=0.4 ○ P(B∣D)=0.5 ○ P(D)=0.3 ○ P(A∣^D)=0.2 ○ P(B∣^D)=0.3 Calculate: P(A∩B∣D) and, P(A∩B∣^D) assuming A and B are also conditionally independent given ^D. 7. Consider three events E, F, and G in a probability space where E and F are conditionally independent given both G and ^G. You are given: ○ P(E∣G)=0.5 ○ P(F∣G)=0.6 ○ P(E∣^G)=0.4 ○ P(F∣^G)=0.3 ○ P(G)=0.7 Calculate: P(E∩F∣G) and, P(E∩F∣^G). 8. In a study on social media influence, researchers are trying to understand if sharing political content (Event A) and engaging in political discussions (Event B) are conditionally independent given a user’s political affiliation (Event C). Given Probabilities: P(A∣C)=0.4, P(B∣C)=0.5, P(C)=0.3 Calculate the probability that a randomly selected user from the sample shares political content and engages in discussions, given their political affiliation. 9. A company runs two different types of marketing campaigns simultaneously: email marketing (Event D) and social media ads (Event E). They want to see if these campaigns independently attract new customers (Event F) when considering the customer segment targeted (youth, adults, etc.). Given Probabilities: P(D∣F)=0.6, P(E∣F)=0.7, P(F)=0.2, P(D∣^F)=0.2, P(E∣^F)=0.1 Calculate the probability that a new customer is attracted by both the email marketing and social media ad campaigns, given that they are a part of the targeted segment. Given Probabilities: P(G∣I)=0.3, P(H∣I)=0.4, P(I)=0.5. Determine the probability that a student participates in both sports and music programs given their grade level. 11. A streaming service uses a Naive Bayes classifier to predict the genre of movies based on two features: presence of action scenes (A) and presence of scary scenes (R). The genres considered are action (X) and horror (Y). Given Probabilities: P(X)=0.6, P(Y)=0.4, P(A∣X)=0.7, P(A∣Y)=0.3, P(R∣X)=0.2 P(R∣Y)=0.8. Calculate the probability that a movie is a horror given that it contains action scenes and scary scenes. 12. A career counseling tool uses Naive Bayes to advise students on potential career paths based on their interest in mathematics (M) and their interest in biology (B). The career paths suggested are engineering (E) and medicine (D). Given Probabilities: P(E)=0.7, P(D)=0.3, P(M∣E)=0.8, P(M∣D)=0.3, P(B∣E)=0.2, P(B∣D)=0.7. What is the probability that a student is advised to pursue medicine given they have an interest in both mathematics and biology? 13. A political analyst uses a Naive Bayes classifier to predict voter behavior based on two issues: support for environmental policies (EP) and support for economic policies (EC). The classifications are progressive voter (P) and conservative voter (C). Given Probabilities: P(P)=0.5, P(C)=0.5, P(EP∣P)=0.8, P(EP∣C)=0.3, P(EC∣P)=0.4, P(EC∣C)=0.7. Estimate the probability that a voter is progressive given their support for both environmental and economic policies. Given Probabilities: ○ P(Click)=0.3, P(No Click)=0.7 ○ P(Y∣Click)=0.4, P(Y∣No Click)=0.2 ○ P(F∣Click)=0.7, P(F∣No Click)=0.3 15. A health insurance company uses Naive Bayes classification to assess the risk of chronic illness based on smoking status (smoker S or non-smoker N) and exercise frequency (regular R or irregular I). Given Probabilities: ○ P(High Risk)=0.25, P(Low Risk)=0.75 ○ P(S∣High Risk)=0.6, P(S∣Low Risk)=0.3 ○ P(R∣High Risk)=0.3, P(R∣Low Risk)=0.7 Calculate the probability that an individual is at high risk for chronic illness if they are a smoker and do not exercise regularly. Given Probabilities: ○ P(Party A)=0.45, P(Party B)=0.55 ○ P(Y∣Party A)=0.3, P(M∣Party A)=0.4, P(O∣Party A)=0.3 ○ P(L∣Party A)=0.2, P(D∣Party A)=0.5, P(H∣Party A)=0.3 ○ P(HS∣Party A)=0.25, P(C∣Party A)=0.50, P(PG∣Party A)=0.25 17. A streaming service uses Naive Bayes to decide whether to show a new sci-fi series or a romantic comedy to a user, based on their previous genre preferences (sci-fi SF, romance RM), viewing time (peak PK, off-peak OP), and subscription type (basic B, premium P). Given Probabilities: ○ P(Sci-Fi)=0.6, P(Rom-Com)=0.4 ○ P(SF∣Sci-Fi)=0.7, P(RM∣Rom-Com)=0.8 ○ P(PK∣Sci-Fi)=0.8, P(OP∣Rom-Com)=0.6 ○ P(B∣Sci-Fi)=0.5, P(P∣Rom-Com)=0.5 Estimate the probability that a premium user, who prefers sci-fi and watches during peak times, will be shown the new sci-fi series. 18. A health app predicts whether a user is at low or high risk for diabetes based on their physical activity level (active A, sedentary S), diet type (balanced B, high-sugar HS), and family history (yes Y, no N). Given Probabilities: ○ P(Low Risk)=0.7, P(High Risk)=0.3 ○ P(A∣Low Risk)=0.8,P(S∣High Risk)=0.7 ○ P(B∣Low Risk)=0.9, P(HS∣High Risk)=0.6 ○ P(Y∣High Risk)=0.4, P(N∣Low Risk)=0.85 What is the probability that a sedentary user with a high-sugar diet and a family history of diabetes is at high risk? 19. A political analyst uses Naive Bayes to estimate support (Support S or Oppose O) for a candidate based on voter registration status (Registered R, Not Registered N) and past voting frequency (Frequent F, Infrequent I, Never V). Given Probabilities: ○ P(S)=0.7, P(O)=0.3 ○ P(R∣S)=0.9, P(N∣S)=0.1 ○ P(F∣S)=0.6, P(I∣S)=0.3, P(V∣S)=0.1 ○ P(R∣O)=0.6, P(N∣O)=0.4 ○ P(F∣O)=0.2, P(I∣O)=0.5, P(V∣O)=0.3 What is the probability that a voter supports the candidate if they are registered and have never voted before? Given Probabilities: ● P(Hire)=0.7, P(Not Hire)=0.3 ● P(C∣Hire)=0.9, P(U∣Hire)=0.85 ● P(C∣Not Hire)=0.4, P(U∣Not Hire)=0.3 ● P(M∣Hire)=0.2, P(M∣Not Hire)=0.8 ● P(N∣Hire)=0.8, P(N∣Not Hire)=0.2
• Online submission: You must submit your solutions online on the course Gradescope site (you can find a link on the course Brightspace site). You need to submit (1) a PDF that contains the solutions to all questions to the Gradescope HW4 Paperwork assignment (including the questions asked in the programming problems), (2) x.py or x.ipynb files for the programming questions to the Gradescope HW4 Code Files assignment. We recommend that you type the solution (e.g., using LATEX or Word), but we will accept scanned/pictured solutions as well (clarity matters). • Generative AI Policy: You are free to use any generative AI, but you are required to document the usage: which AI do you use, and what’s the query to the AI. You are responsible for checking the correctness. Before you start: this homework only has programming problems. You should still have all questions answered in the write-up pdf. Also note that some sub-problems are still essentially math problems and you need to show detailed derivations. Problems 1 and 2 are two parts of one problem, so we suggest you read the description of both problems in tandem. This homework could be challenging and hope the following tips help: • Understanding of the gradient boosting tree concept. In particular, we use every single tree to compute a “gradient step”, and the sum of the gradient steps gives us the final predictions. • Understanding of the python notebook we provide. The code we provide aims to share implementations between the random forests and the GBDTs. Try to think about how different parts of the code could be re-utilized by the two models. • Debugging your code: always try to debug a small case. For example, use very few data points and build a tree with a depth of 2 or 3. Then, you can look at all the decision rules and data point assignments and check if they are reasonable. 1 Programming Problem: Random Forests [40 points] Random forests (RF) build an ensemble of trees independently. It uses bootstrap sampling (sampling with replacement, as discussed in class) to randomly generate B datasets from the original training dataset, each with the same size as the original one but might contain some duplicated (or missing) samples. Each sample has a multiplicity which is greater than or equal to zero. In your python implementation, you can use numpy.random.choice for the sampling procedure. . (1) The optimization problem for training each tree in RF is , (2) where ˆyi is the prediction produced by tree-b fb(·;θb) for data point xi, ℓ(·,·) is a loss function (detailed in Problem 2.5.3), and Ω(θb) is a regularizer applied to the parameters θb of model-b (that is, Ω(θb) measures the complexity of model-k). Most descriptions of ensemble learning in Problem 2.1 of the homework (below) can be also applied to RF, such as the definitions of fk(·;θk) and θk, except Eq. (3) and Eq. (4). Different methods can be used to find the decision rule on each node during the optimization of a single tree. A core difference between random forests and GBDTs (which we will describe in Problem 2) is the tree growing methods. Specifically, in the case of GBDT, we use the standard greedy tree-splitting algorithm; in the case of random forests, we greedily learn each tree using a bootstrapped data sample and random feature selection as described in class. That is, the key difference is the data that is being used (always original data in the case of GBDT or bootstrap sample for each tree in the case of RFs), and in the case of RFs we choose a random subset of features each time we grow a node. The underlying algorithm, however, is very similar. Therefore, to facilitate code reuse between this and the next problem, and also to make more fair the comparison between RFs and GBDTs, we ask you to use the same code base between this and the next problem (detailed in Problem 2.4 below). Each tree in the RF method is like the first tree in GBDT, as the RF method does not consider any previously produced trees when it grows a new tree (the trees are independent with RFs). With RFs, we simply start with ˆyi0. You need to notice this fact when re-using the code from GBDT, because Gj and Hj for tree-k in RD only depend on ˆyi0, not ˆ . Instructions 2-5 in Problem 2.5, however, can still be applied to RF tree building here. In this problem, you will implement RFs for both regression and binary classification problems. Please read Problem 2.1, 2.4, and 2.5 below before you start. 1. [20 points] Implement RF for regression task, and test its performance on Boston house price dataset used in Homework 2. Report the training and test RMSE. How is the performance of RF compared to least square regression and ridge regression? 2. [20 points] Implement RF for binary classification task, and test its performance on Credit-g dataset. It is a dataset classifying people described by 20 attributes as good or bad credit risks. The full description of the attributes can be found at https://www.openml.org/d/31. Report the training and test accuracy. Try your implementation on breast cancer diagnostic dataset , and report the training and test accuracy. 2 Programming Problem: Gradient Boosting Decision Trees [60 points] 2.1 Problem of Ensemble Learning in GBDTs Gradient Boosting Decision Trees (GBDT) is a class of methods that use an ensemble of K models (decision trees) . It produces predictions by adding together the outputs of the K models as follows: K yˆi = Xfk(xi;θk). (3) k=1 The resulting ˆy can be used for the predicted response for regression problems, or can correspond to the class logits (i.e., the inputs to a logistic or softmax function to generate class probabilities) when used for classification problems. The optimization problem for training an ensemble of models is n K min Xℓ(yi,yˆi) + XΩ(θk), (4) {θk}K k=1 i=1 k=1 where θk is the parameters for the kth model, and where ˆyi is the prediction produced by GBDT for data point xi, ℓ(·,·) is a loss function (detailed definition of losses are given in Problem 2.5.3), and Ω(θk) is a regularizer applied to the parameters θk of model-k (that is, Ω(θk) measures the complexity of model-k). , (5) where qk(·) : Rd 7→ Lk represents the decision process of the kth decision tree. That is, qk(x) assigns each data x to a leaf node j of the kth tree; it is comprised of the decision rules on all the non-leaf nodes as itsFigure 1: An example of GBDT: Does the person like computer games? Therefore, to define a tree fk(·), we need to determine the structure of the tree T ≜ (Nk ∪ Lk,E) (E is the set of tree edges), the feature dimension pj and threshold τj associated with each non-leaf node j ∈ Nk, and the weight associated with each leaf node j ∈ Lk. These comprise the learnable parameters θk of fk(·;θk), i.e., . (6) To define an ensemble of multiple trees, we also need to know the number of trees K. We cannot directly apply gradient descent to learn the above parameters of GBDT because: (1) some of the above variables are discrete and some could have an exponential number of choices, including for example, the number of trees, the structure of each tree, the feature dimension choice associated with each non-leaf node, the weights at the leaf nodes; and 2) the overall decision tree process is not differentiable meaning straightforward naive gradient descent seems inapplicable. 2.2 Overview of the GBDT algorithm The basic idea of GBDT training is additive training, or boosting. As mentioned above, Boosting is a metaalgorithm that trains multiple models one after another, and in the end combines additively to produce a prediction. Boosting often aims to convert multiple weak learners (which might be only slightly better than a random guess) into a strong learner that can achieve error arbitrarily close to zero. Boosting has many forms and instantiations, including AdaBoost [6], random forests [5, 2], gradient boosting [3, 4], etc. Note that Bagging [1] is not boosting since there is no interdependence between the trainings of the different models, rather each model in Bagging is trained on a separate bootstrap data sample. GBDT training shares ideas similar to coordinate descent in that only one part of the model is optimized at a time, while the other parts are fixed. In the coordinate descent algorithm (you implemented it for Lasso), each outer loop iteration requires one pass of all the feature dimensions. In each iteration of its inner loop, it starts from the first dimension, and optimizes only one dimension of the weight vector by fixing all the other dimensions and conditioning on all the other dimensions. Each tree in GBDT is analogous to a dimension in coordinate descent, but the optimization process is different. GBDT starts from the first tree, and optimizes only one tree per time by fixing all the previous trees and we condition on all the previously produced trees. One core difference GBDT training has from coordinate descent is that GBDT training does not have the outer loop associated with coordinate descent, i.e., it only does one pass over all the trees. If it was coordinate descent, we would optimize each coordinate only once in succession. In particular, we start from one tree, and only optimize one tree at a time conditioned on all previously produced trees. This, therefore, is a greedy strategy as we spoke about in class. After the training of one tree finished, we add this new tree to our growing ensemble and then repeat the above process. The algorithm stops when we have added tmax trees to the ensemble. In the optimization of each tree, we start from a root node, find the best decision rule (a feature dimension and a threshold) and split the node into two children, go to each of the children, and recursively find the best decision rule on each of the child nodes, and continue until some stopping criterion is fulfilled (as will be explained very shortly below). In the following, we will first elaborate how to add trees one after the other, and then provide details regarding how to optimize a single tree based on a set of previous trees (which might be empty, and so this also explains how to start with the first tree). 2.3 Growing the forest: How to add a new tree? Assume that there will be K trees in the end. Therefore, we will get a sequence of (partially) aggregated predictions , from the K trees as follows: , According to Eq. (4), fixing all the previous k − 1 trees, the objective used to optimize tree-k is , (7) Let’s simplify the first term using Taylor’s expansion, ignoring higher-order terms: . (8) After applying Taylor’s expansion to )), we have , (9) where gi and hi denote the first-order and second-order derivatives of ) w.r.t. ˆ , i.e., . (10) The second term Ω(θk) in Eq. (7) is a regularization term aiming to penalize the degree of complexity of tree-k. It depends on the number of leaf nodes, and the L2 regularization of wk. With GBDTs, it is defined as: . (11) We plugin Eq. (9) and Eq. (11) into Eq. (7), and after ignoring constants, we get Fk(θk) + const. , (12) 2.4 Growing a tree: How to optimize a single tree? Now we can start to optimize a single tree fk(·;θk). Look at the objective function in Eq. (12): it is a sum of |Lk| independent simple scalar quadratic functions of wjk for all the j ∈ Lk! How to minimize a quadratic function? This we know is easy, and similar to least square regression, the solution has a nice closed form. Hence, wjk minimizing Fk(θk) is . (13) We can plug the above optimal wjk into Eq. (12) and obtain an updated objective (14) However, there are still two groups of unknown parameters in θk, which are the tree structure T and the decision rules {(pj,τj)}j∈Nk. In the following, we will elaborate how to learn these parameters by additive training of a single tree. We will start from the root node and determine the associated decision rule (pj,τj); this rule should minimize the updated objective in Eq. (14), where Lk contains the left and right child of the root node. Then, the same process of determining (pj,τj) will be recursively applied to the left and right nodes, until a stopping criteria (as described below) is fulfilled. For each candidate decision rule (pj,τj), we can compute the improvement it brings to the objective Eq. (14). Before splitting node j to a left child j(L) and a right child j(R), the objective is (15) After splitting, the leaf nodes change to j(L) and j(R), and the objective becomesHence, the improvement (we usually call it the “gain”) is (17) (18) (19) Therefore, the best decision rule (pj,τj) on node j ∈ Nk is the one (out of the m × n possible rules) maximizing the gain, which corresponds to the decision rule that minimizes the updated objective in Eq. (14). That is, we wish to perform the following optimization: (20) We start from the root node, apply the above criterion to find the best decision rule, split the root into two child nodes, and recursively apply the above criterion to find the decision rules on the child nodes, the grandchildren, and so on. We stop splitting according to a stopping criterion is satisfied. In particular, we stop to split a node if either of the following events happens: 1. the tree has reached a maximal depth dmax; 2. the improvement achieved by the best decision rule for the node (Eq. (20)) goes negative (or is still positive but falls below a small positive threshold, in the following experiments, you can try this, but please report results based on the “goes negative” criterion); 2.5 Details of Practical Implementation 1. Learning rate η: You might notice that the tree growing in GBDT is a greedy process. In practice, to avoid overfitting on a single tree, and to give more chances to new trees, we will make the process less greedy. In particular, we usually assign a weight 0 ≤ η ≤ 1 to each newly added tree when aggregating its output with the outputs of previously added trees. Hence, the sequence at the beginning of Problem 2.3 becomes yˆi0 = 0, yˆi1 = ηf1(xi) = yˆi0 + ηf1(xi), yˆi2 = ηf1(xi) + ηf2(xi) = yˆi1 + ηf2(xi), ··· k yˆik = η X fk′(xi) = yˆik−1 + ηfk(xi), k′=1 ··· K yˆiK = η Xfk(xi) = yˆiK−1 + ηfK(xi). k=1 Note that this change must be applied in both training and during testing/inference. 0 ≤ η ≤ 1 is usually called the “learning rate” of GBDT, but it is not exactly the same as the variable we usually call the learning rate in gradient descent. 2. Initial prediction yˆi0: GBDT does not have bias term b like linear model y = wx+b. Fortunately, ˆyi0 plays a similar role as b. Hence, instead of starting from ˆyi0 = 0, we start from ˆ , i.e., the average of ground truth on the training set. For classification, it is also fine to use this initialization (the average of lots of 1s and 0s), but do not forget to transfer the data type of label from “int” to “float” when computing the average in this case. 3. Choices of loss function ℓ(·,·): ℓ(·,·) is a sample-wise loss. In the experiments, you should use least square loss ℓ(y,yˆ) = (y−yˆ)2 for regression problems. For binary classification problems, we use one-hot (0/1) encoding of labels y (y is either 0 or 1), and logistic regression (the GBDT output ˆy is the logit in this case, which is a real number and the input to logistic function producing class probability), i.e., ℓ(y,yˆ) = y log(1 + exp(−yˆ)) + (1 − y)log(1 + exp(ˆy)). (21) The prediction of binary logistic regression, which is the class probabilities, is Pr( , Pr(class = 0) = 1 − Pr(class = 1). (22) To produce a one-hot (0/1) prediction, we apply a threshold of 0.5 to the probability, i.e., 1, Pr(class = 1) > 0.5 (23) 0, Pr(class = 1) ≤ 0.5 4. Hyper-parameters: There are six hyper-parameters in GBDT, i.e., λ and γ in regularization Ω(·), dmax and nmin in stopping criterion for optimizing single tree, maximal number of trees tmax in stopping criterion for growing forests, and learning rate η. We will not give you exact values for these hyper-parameters, since tuning them is an important skill in machine learning. Instead, we will give you ranges of them for you to tune. Note larger dmax and tmax require more computations. Their ranges are: λ ∈ [0,10], γ ∈ [0,1], dmax ∈ [2,10], nmin ∈ [1,50], tmax ∈ [5,50], η ∈ [0.1,1.0]. In RFs, we do not have the learning rate, but there is another hyper-parameter, which is the size m′ of the random subset of features, from which you need to find the best feature and the associated decision rule for a node. You can use m′ ∈ [0.2m,0.5m]. 5. Stopping criteria: There are two types of stopping criteria needed to be used in GBDT/RFs training: 1) we stop to add new trees once we get tmax trees; and 2) we stop to grow a single tree once either of the three criteria given at the end of Problem 2.4 fulfills. 6. Acceleration: We encourage you to apply different acceleration methods after you make sure the code works correctly. You can use multiprocessing for acceleration, and it is effective. However, do not increase the number of threads to be too large. It will make it even slower. You can also try numba (a python compiler) with care. 2.6 Questions 1. [4 points] What is the computational complexity of optimizing a tree of depth d in terms of m and n? 2. [4 points] What operation requires the most expensive computation in GBDT training? Can you suggest a method to improve the efficiency (please do not suggest parallel or distributed computing here since we will discuss it in the next question)? Please give a short description of your method. 3. [8 points] Which parts of GBDT training can be computed in parallel? Briefly describe your solution, and use it in your implementation. (Hint: you might need to use “from multiprocessing import Pool” and “from functools import partial”. We also talked about multiprocessing in the recitation session.) 4. [20 points] Implement GBDT for the regression task, and test its performance on Boston house price dataset used in Homework 2. Report the training and test RMSE. How is the performance of GBDT compared to least square regression and ridge regression? 5. [20 points] Implement GBDT for the binary classification task, and test its performance on Creditg dataset. Report the training and test accuracy. Try your implementation on the breast cancer diagnostic dataset, and report the training and test accuracy. 6. [4 points] According to the results on the three experiments, how is the performance of random forests compared to GBDT? Can you give some explanations? References [1] Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. [2] Leo Breiman. Random forests. Machine Learning, 45(1):5–32, 2001. [3] Jerome H. Friedman. Stochastic gradient boosting. Computational Statistics and Data Analysis, 38:367– 378, 1999. [4] Jerome H. Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29:1189–1232, 2000. [5] Tin Kam Ho. Random decision forests. In Proceedings of 3rd International Conference on Document Analysis and Recognition, volume 1, pages 278–282, 1995. [6] Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197–227, 1990.
