User Tools

Site Tools


hw:final

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

hw:final [2012/05/02 17:04]
neu
hw:final [2016/05/06 14:58] (current)
neu
Line 1: Line 1:
 ====== Physics 2660 Final Exam ====== ====== Physics 2660 Final Exam ======
  
-**Final Exam Due Tuesday ​May 8** +**Final Exam Due Thursday ​May 12** 
-  * Online Submissions by 12:00 PM  +  * There are three questions, a total of 100 points. 
-  * Paperwork: ​4:00 PM (Turn in code/​write-ups ​at the reception desk in the Physics Office)+  * Online Submissions ​**by 9:00 AM on Thursday May 12**  
 +  * Paperwork: ​ 
 +      * Turn in code/​write-ups ​**in our normal lab room Phys 022-C between 8:00 and 10:00 AM on Thursday May 12** 
 +      * You must turn in a hard copy of all required files, otherwise I will not grade your exam. 
 +      * Prepare a stapled hard copy for each problem individually,​ and hand in the stack of hard copies bound together with a paper clip / binder clip.
  
-Rules:+**Rules:**
   * All students must work individually,​ no collaboration.   * All students must work individually,​ no collaboration.
-  * You can ask Prof. Neu questions via email or chat but the insight will be limited to **conceptual assistance or clarifications**. Pose all questions **before ​Friday 4 May 6pm**. +  * You can ask questions via email or chat or Piazza ​but the insight will be limited to **conceptual assistance or clarifications**. Pose all questions **before ​Monday 9 May at 8:00 PM**. 
-  * TA hours will be held on **Thursday 3 May  3:30-5:30pm** and **Friday 4 May 2:00-4:00pm**. These will not be standard lab-TA hours: students can come **individually** to ask questions to Aaron but then you will go and work on the questions on your own. Conceptual and clarifications on content only, no assistance in determining the solutions. ​ No examination of code will be allowed. +  * TA hours will be held on **Sunday 8 May 5:00-8:00 PM** and **Monday 9 May 4:00-7:00 PM**. These will not be standard lab-TA hours: students can come **individually** to ask questions to the TA but then you will go and work on the questions on your own. Conceptual ​questions ​and clarifications on content only, no assistance in determining the solutions. ​ No examination of code will be allowed. 
-  * Allowed resources: class texts, class notes, class web page (including solutions), and only web links provided directly from the class web pages. ​ You can use functions available in the standard C libraries we have used in class/​lab/​homeworks. +  ​* **Allowed resources:** class texts, class notes, class web page (including solutions), and web links provided directly from the class web pages. ​ You can use functions available in the standard C libraries we have used in class/​lab/​homeworks.  
-  * Your descriptions/​justifications are important for these problems, some questions will be open to interpretation. +  * Your descriptions/​justifications are important for these problems, some questions will be open to interpretation. You should provide descriptions accompanying your solutions where needed
-  * Pledge your source code/reports.+  * Pledge your source code and hard copies.
  
-:?: Email/chat any requests for problem clarifications ​to Prof. Neu by Friday, May 46pm This may be followed by a single FAQ email covering appropriate questions. **Watch for this email.** ​ After this, there will be no more discussion during the exam.+:?: Email/chat/​Piazza ​any requests for problem clarifications ​**by Monday, May 97:00 PM.** After this period, watch for **single FAQ email** covering appropriate questions ​with any necessary clarifications. **Watch for this email.** ​ After this, there will be no more discussion during the exam period.
  
  
 Tips: Tips:
 +  * Not all questions are worth the same amount of points, so plan accordingly.
   * Don't jump into coding before you have a good idea about how you want to write your program.  ​   * Don't jump into coding before you have a good idea about how you want to write your program.  ​
   * Plan your work carefully. ​     * Plan your work carefully. ​  
-  * Submit documented partial solutions if you don't have full solutions to the problems - we'll give credit for all reasonable work towards your solutions.+  * Submit documented partial solutions if you don't have full solutions to the problems - we'll give partial ​credit for reasonable ​yet incomplete ​work towards your solutions.
  
-===== 1. Chutes and Ladders ​(50) =====+===== 1. Shut the Box (30 points) =====
  
-{{:hw:chutes-and-ladders_box.jpg|}}+{{:hw:shut-the-box.jpg|}}
  
-Chutes and Ladders is a popular children'​s ​game in the US (alternatively known as Snakes and Ladders in the UK)It has simple rules and is good teaching how to count and understand simple directions.+Variants of the game [[http://​en.wikipedia.org/​wiki/​Shut_the_Box|Shut ​the Box]] have been around since the 12th centuryToday it goes by many names and some version of it is played on every continent.
  
-C&​L ​is a classic land-accumulation ​game in which the objective is to move forward, covering a set amount ​of 100 units of space. The victor ​is the player who does this firstin the least amount of movesPerturbations exist in one's path that can alter one's position in non-linear way: +Shut the Box is a simple ​game played with two dice and some number ​of numbered tiles. The point of the game is to take successive turns rolling ​the two dice and eliminating numbered tilesturning them over as the sum is achievedAny number of tiles can be turned over after given roll as long as the sum matches the sum of the dice from the roll. The version of Shut the Box we will consider here has tiles numbered ​1-12
-  * Backwards – falling down a slide/chute OR +
-  * Forwards – climbing up a ladder +
-Each player spins a fair spinner or rolls a fair single 6-sided die, allowing a movement forward ​of between ​and 6 unitsHere is what the standard board looks like:+
  
-{{:​hw:​chutes-and-ladders_board.jpg|}}+Play starts with all tiles turned up. As an example, consider rolling on the first roll a 3 and a 4. Their sum is 7. In this case, one could **either** flip down the tiles for 3 and 4, or 2 and 5, or 1 and 6, or 1 and 2 and 4, or any combination whose sum is 7. One could even flip down the **one** tile for the sum of the numbers, 7. The player'​s turn continues with more rolls. Later in the turn, if one rolls a 2 and a 3, but 1, 2, 3, 4 and 5 are already turned over, then the player'​s turn is over, since none of the remaining tiles can be summed to match the sum of the dice rolled. If one rolls a 1 and a 4, but 1, 2, 3, and 5 are turned over, then one might be tempted to turn over the 4 BUT in fact the turn is over. Play proceeds until one cannot flip any more tiles. A final score for a player'​s turn is determined by summing the values of the tiles that remain. Clearly, lower scores are optimal.
  
-Play starts **off the board** and **proceeds with the first roll**, each player taking ​single turn. (2 May: There was an error in the original instructions regarding the starting position.)+The game is best played in a group of people, each person taking turns to achieve ​the best/lowest score, claiming as their prize **ultimate glory** or, in some cases, ​**a small amount of previously agreed-upon stakes**.
  
-Besides being a simple game for childrenC&L is a nice, simple system that can easily be simulated using a Monte Carlo technique:​ +For this portion of the final examyou will run thousands of single-player "​pseudogames"​ of Shut the Box. 
-  * Completely deterministic +
-  * Random path length but rolls limited to between [1,6] +
-  * Paths non-linear but well-defined+
  
-Here you will simulate the game of C&L with the goal of answering some simple questions about the game play. Use the standard board layout that is displayed above (some online versions might be differentold versions might be different – it is your responsibility to make sure to use the version I expect you to use). NBAssume the “winner” is the first with ≥100, not ==100. To answer the questions below **you will need to simulate thousands of C&L matches -- pseudomatches!**+Write your simulationcall it <​username>​_shutthebox,​ such that it accepts ​the following command line arguments: 
 +  ​* ​number of pseudogames ​to run 
 +  ​strategy number, either 1 or 2 (see below), or, if no value is given, for running both strategies simultaneously
  
-Write your simulation, call it clsim, such that it accepts the following command line arguments: 
-  * number of players 
-  * number of pseudomatches 
  
 +The output of your program should print to screen:
 +  - The strategy tested, including its name
 +  - The number of pseduogames tested
 +  - The worst (highest) possible score
 +  - An estimate of the probability of achieving the worst possible score
 +  - An estimate of the probability of "​shutting the box", ie, in a given turn what is the probability of rolling the dice such that you turn down all the tiles over the course of a turn, effectively achieving a score of 0.
  
-Questions:​ +**Question:** Is it more likely to shut-the-box depending on the **strategy** one employs ​in the game? There are two general schools of thought: 
-  - On average, do games with four players last longer than those with two players? Why or why not?  ​**Here I mean total game duration, ie, total number of moves.** +  ​* **Strategy 1, "More-tiles-first":​** ​In every case where there is a choiceprefer to flip down the most number ​of tiles that equal the sum instead of smaller combinations of tiles. ​ In cases where there are multiple choices with the same number of tiles to flip down, choose ​the tile combination that has the highest individual value among it. 
-  ​In 10k pseudomatches,​ what is the shortest 4-player game in terms of total moves for all players? Shortest 2-player ​game? +  * **Strategy 2"​Fewer-tiles-first":​** In every case where there is a choiceprefer to flip down the smallest ​number of tiles that equal the sum instead of larger combinations of tilesIn cases where there are multiple choices with the same number of tiles to flip down, choose ​the tile combination that has the highest individual value among it.
-  - In 10k pseudomatches,​ what is the longest 4-player game?  +
-  - Assuming 3.5 seconds per move per playerwhat is the average duration ​of a 4-player game? 2-player game? +
-  - The optimal location on the board is defined as the position from which the most-frequent path to winning is shortestClearly this is someplace between 95 and 99. Howeverwhat is the optimal location between squares 21 and 60? NB: this can be simulated using many single-player pseudomatchesstarting from different locations in positions [21,60] and recording ​the number of moves needed to reach 100 in each matchA histogram of the number of moves required for winning is useful: ​the position with the distribution with the smallest mean is the most optimal.+
  
-Hand in your code electronically **[username_clsim.cpp]**. ​ Make sure to answer the questions in the comments area near the beginning of your code. **Preserve the functionality inside your code to answer all these questions -- and provide some instructions on how to run it in comments near the top of your file.** 
  
-===== 2. Signal and Background (50) =====+**Make sure each piece of information is labeled properly and that you are clear on which of the two strategies you are testing**. These answers should be determined from your pseudogames. 
 + 
 +Hand in your code electronically **[<​username>​_shutthebox.cpp]**. Make sure to answer the question about the optimal strategy in a brief comments section near the top of your code. Optional: If you want to include **one histogram file (at most one!)** as support for your answer, submit it as <​username>​_shutthebox.pdf.  
 + 
 +===== 2. Texas Hold 'Em Poker (40 points) ===== 
 + 
 +{{:​hw:​poker.png|}} 
 + 
 +Before you start, [[https://​en.wikipedia.org/​wiki/​Texas_hold_%27em|read about the rules and game play]] of the popular poker variant called Texas Hold 'Em. 
 + 
 +The goal of this game is to achieve the best [[http://​www.cardplayer.com/​rules-of-poker/​hand-rankings|5-card poker hand]] among all the players. The game is played with [[https://​en.wikipedia.org/​wiki/​Standard_52-card_deck|a standard deck of 52 playing cards]]. 
 + 
 +Players are dealt two face-down cards that belong to them alone, and five community cards which are dealt in three stages and are shared by all players. Typically there is a round of betting: 
 +  * after being dealt the two "hole cards"​ 
 +  * after the first three community cards are revealed, called "the flop"​ 
 +  * after the fourth community card is revealed, called "the turn"​ 
 +  * and after the fifth and final community card is revealed, called "the river"​ 
 + 
 +As designed then, players have more of an idea about the strength of their hand on //the river// than they do before //the flop//, for instance.  
 + 
 +For this portion of the final exam, you will run thousands of two-player "​pseudohands"​ of Texas Hold 'Em poker. Your general task here is the following: Model a 1- or 2-player, single-deck Texas Hold 'Em game **from the perspective of one of the players**. The goal of your code is to answer some probability questions, and provide **win probabilities** for various hole-card / community-cards configurations at defined stages of the game. Recall each player knows nothing about the other player'​s hole cards -- hence the need to simulate lots of possible outcomes in order to know what the win probabilities are. No ante / betting / raising / calling assumptions need to be included to answer these questions. 
 + 
 +Write your simulation, call it <​username>​_poker,​ such that it accepts the following command line arguments:​ 
 +  * number of pseudohands to run, followed by  
 +  * the two hole-card identities, followed by 
 +  * three, four, or five community card identities 
 +  
 +For the card identities, use //A// for Ace, 2....9 for number cards, //T// for 10, //J,Q,K// for Jack, Queen, King, respectively. Also use //C,D,H,S// for the suits Clubs, Diamonds, Hearts, Spades. Hence the ten of Spades would be denoted //TS//, the four of Hearts //4H//, etc. 
 + 
 +Your code should expect a variable number of community cards depending on what situation you are modeling without any extra prompting. 
 + 
 +The output should minimally state the following:​ 
 + 
 +<​code>​ 
 +Simulated mmmmm pseudohands of Texas Hold 'Em:  
 +  Given hole cards xx and yy, and community cards c1,​c2,​c3,​(c4,​c5),​ the win probability is nnnnn%.  
 +  In mmmmm pseudohands of this situation, there were rrrrr instances of a Royal Flush (rf%). 
 +</​code>​ 
 + 
 +[You can add other lines reporting other single-hand outcomes like Straight Flush, Four of a Kind, etc., if you like. But take care not to have any other cluttered output printed to screen.] 
 + 
 +Questions to answer. Do so briefly in words in the header of your code. These answers should be consistent with the output reported to screen: 
 +  - 10 points: What is the probability of achieving a [[http://​www.cardplayer.com/​rules-of-poker/​hand-rankings|Royal Flush of any suit]] on or before the river in a standalone, single-player sense? //**Note** (updated 5/6) this used to read: "What is the probability of any single player in this 2-player game achieving a [[http://​www.cardplayer.com/​rules-of-poker/​hand-rankings|Royal Flush of any suit]] on or before the river?"​ updated for clarity.//​ 
 +  - 20 points: If one is dealt KC,7H and the community cards at the river are 2H,​4S,​KH,​7D,​3S,​ what is the win probability? ​  
 +  - 10 points: If one is dealt KC,7H and the community cards at the flop are 2H,4S,KH, what is the win probability? ​  
 + 
 +Although one could calculate the probabilities by hand, the answers should come from the simulated pseudohands in your code. 
 + 
 +Hints: 
 +  * Start by simulating the game at //the river// first, since the combinatorics are simplest, ie, there are fewer possibilities to consider for the opponent'​s hand. 
 +  * Also, you should start by simulating the game at //the river// first since questions 1 and 2 above only pertain to the river -- and are worth 2/3-rds of the points for this question. 
 +  * The first question requires simply counting the number of Royal Flush outcomes among the pseudohands you run. This will of course depend on what you enter for the hole and community cards. Hence I recommend writing two poker modeling functions:  
 +     - One that simply deals out many raw combinations of 2 hole cards and 5 community cards and counts how often a Royal Flush is achieved (this is what I mean by a 1-player game above), and 
 +     - One that simulates the player vs. player nature of the 2-player game 
 + 
 +Hand in your code electronically **[<​username>​_poker.cpp]**. Make sure to answer the questions in words in a brief comments section near the top of your code.  
 + 
 +===== 3. Etiquette and Efficiency on the London Underground (30 points) ===== 
 + 
 +{{:​hw:​holborn.jpg|}} 
 + 
 +Start by reading [[https://​tfl.gov.uk/​info-for/​media/​press-releases/​2016/​march/​london-underground-planspilot-of-new-escalator-arrangement-at-holborn-tube-station|this important notice]] about escalator protocols at Holborn Tube station on the London Underground. 
 + 
 +In short, the [[https://​tfl.gov.uk/​|Transit For London]] authorities have mandated that a couple of their up escalators will eschew the common convention of "walk on the left, stand on the right" in favor of the "stand on both sides" paradigm. The claim is that "walk on the left, stand on the right" approach, somewhat surprisingly,​ is in fact less efficient at transporting passengers from bottom to top of an escalator. 
 + 
 +Actually, is this so surprising? Consider the following [[http://​www.bbc.com/​news/​magazine-23444086|statistics]]:​ 
 +  * Only ~25% of Tube users choose to walk up the escalator, when the option is available, meaning a great deal of the time half the escalator is unused 
 +  * While 90% of Tube users formerly adhered to the "walk on the left, stand on the right" convention, that means 10% ignored the convention -- and a single left-side standing commuter halts all left-side walkers temporarily until their very impolite escalator ride is over. //**Note:** changed 5/6 from "a single left-side standing commuter halts all left-side walkers."​ for clarity.//​ 
 + 
 + 
 +So which approach is best? Sounds like a job for some **talented and clever University of Virginia PHYS 2660 students!** 
 + 
 +In this part of the final you will model this physical system. Consider the problem of needing to move N people from the bottom to the top of an escalator, where N is large, say N=5000. Imagine the flux of people entering the escalator is 2 persons per second and is constant. The escalator at Holborn station is really tall -- nearly 25m! -- and hence a trip from bottom to top while standing requires about 30 seconds. Walking up the escalator requires half that amount of time. The probabilities listed above should be considered to be Gaussian distributed,​ adhering to a distribution with a width that is 10% of the mean. 
 + 
 +Unlike the above problems, this one is going to be **a bit free-form** -- you are free to answer the problem in any C-programming-based way you like.  
 + 
 +All files you submit should be named in the format **[<​username>​_escalator.xx]** where xx = cpp, txt or pdf. You should write a brief report in a .txt file answering the following:  
 +  - What was your hypothesis? Ie, which escalator convention do you predict to be most efficient?​ 
 +  - What was your approach to the problem?  
 +  - What figure of merit did you design or rely on to measure the efficiency of the two conventions?​ 
 +  - How do you run your code?  
 +  - What do you conclude from your modeling? 
 +  - Are there features of the description of this model that are missing that make it less-than realistic?​ 
 +  - Are there additional tests one could do with the model to take the understanding of this system beyond the baseline? What other questions could you consider pursuing? 
 + 
 +There is no length requirement for the written portion, but **strong preference is for succinct clarity** rather than lengthy responses -- minimum word counts are //patently absurd// (IMO it is juvenile to tell students they need to respond in a minimum number of words -- this is not middle school). You know what you need to say to represent your work properly. 
 + 
 +The problem will be graded by all three of us (Eric, Rob and Prof. Neu) and your grade the average of the three. We will be grading your responses based on soundness of scientific approach, completeness and clarity. 
 + 
 +For more background information,​ check out: 
 +  * http://​www.slate.com/​blogs/​future_tense/​2016/​01/​22/​standing_on_escalators_faster_than_walking_according_to_transport_for_london.html 
 +  * http://​www.bbc.com/​news/​magazine-23444086 
 +  * http://​www.citylab.com/​commute/​2016/​01/​subway-escalator-standing-study-tfl-london/​424950/​ 
 +  * Chaos! http://​metro.co.uk/​2016/​04/​18/​chaos-as-passengers-are-told-to-stand-on-the-right-and-left-at-holborn-tube-station-5823640/​ 
 + 
 + 
 + 
 +!- 
 +===== 2. Blackjack (30 points) ===== 
 + 
 +[[http://​en.wikipedia.org/​wiki/​Blackjack|Blackjack]] is one of the simplest card games one can play, and is one of the most widely-played casino games in the world. The purpose of the game is to collect cards that come as close to or match the value or score **21**. Using a standard 52-card deck, each card has a specific value: 
 +   * cards numbered 2-10 are worth their numeric value 
 +   * jacks, queens and kings (J,Q,K) are worth 10 
 +   * aces (A) are worth either 1 or 11, and the choice of value is up to the player 
 +There is no difference in valuation depending on the suit of the cards. 
 + 
 +We will only consider a two-hand game with a single deck of cards, and the basic game play goes as follows: One hand is owned by the "​dealer",​ and the other hand is owned by the "​player"​. The player and dealer are adversaries. The dealer distributes one card face-up to the player and one face-up for himself or herself, followed by a second face-up to the player, and finally a second face-down to himself. At this point the player knows the value of his hand, but only one of the cards in the dealer'​s hand. 
 + 
 +The player wants to beat the dealer, which can happen in one of three ways: 
 +   * the player achieves 21 on the initial deal, otherwise knowns as "​blackjack!",​ without a dealer blackjack, or 
 +   * the player gets a final score higher than the dealer, but not exceeding 21, or 
 +   * the dealer gets a final score that is higher than 21, or "going bust"​ 
 + 
 +Once the initial hand is dealt, the player then has a variety of choices. In this simplified game we describe here, the choices available to the player are: 
 +   * to add a card to his hand, or "​hit",​ one by one 
 +   * to refuse any more cards, or "​stand"​ 
 + 
 +There are other options typically available in a casino-sanctioned environment (choices like "​doubling down", "​split",​ and "​surrender"​) but we will not consider those additional options here. 
 + 
 +The player can add cards until he or she is satisfied with their score. There is no minimum score that the player must achieve. If the player "​busts"​ or goes above 21, the player automatically loses.  
 + 
 +Once the player decides to stand, the dealer then reveals his or her previously face-down card. The dealer must then continue to take cards until their hand has a score of 17 or higher. Once the dealer has a hand that totals 17 or more, the values are compared, and whoever is closer to 21 -- without going over -- is the winner of the hand. Note that dealer must stand once achieving a score of 17 or more -- even if the dealer'​s hand contains an ace, which in this case would be interpreted as a value of 11.  
 + 
 +From the player'​s perspective,​ the choice of when to stand depends critically on what is in the dealer'​s hand -- **the knowledge of which is incomplete, given that one of the dealer'​s cards is still face-down.** Depending on what the dealer has in their single face-up card, it is more optimal for the player to "​hit"​ or "​stand"​. We will analyze the strategy options by playing a number of "​pseudo-hands"​ of blackjack.  
 + 
 +You should write a piece of code that is capable of simulating thousands of hands of blackjack. Each hand is independent,​ meaning that the deck is shuffled after each hand concludes.  
 + 
 +Write your simulation, call it <​username>​_blackjack,​ such that it accepts the following command line arguments:​ 
 +  * number of pseudohands to run for each scenario below 
 +  * the value of the player'​s total hand (only consider the possibilities 8,​9,​10,​11,​12,​13,​14,​15,​16 or '​all'​) 
 +  * the value of the dealer'​s face-up card (2,​3,​4,​5,​6,​7,​8,​9,​10,​A or '​all'​) 
 + 
 +(Take care to write your code in steps, adding functionality as you go, hoping to achieve the most-general case. See the grading breakdown below for guidance. Make sure to achieve the simple deliverables first, as described below, before making the code completely general -- and infinitely harder to debug.) 
 + 
 +In a single-deck game, after the initial deal, there would be only 48 cards left from which to draw the subsequent cards. However, for the purpose of this simulation and to keep computing times manageable, you can imagine that and cards taken on a "​hit"​ come from a full 52-card deck. Use this assumption for both the player'​s and dealer'​s hit cards. Hence also one should not be concerned with whether the player'​s hand is "​soft"​ or "​hard",​ ie, whether it is built with an ace. Just assume the player'​s hand has a certain value. 
 + 
 +The output of your program should print to screen: 
 +  * Report the score of the player'​s hand  
 +  * Report the value of the face-up card of the dealer 
 +  * The recommendation whether a player should "​hit"​ or "​stand"​ under these conditions 
 + 
 +The recommendation of whether to hit or stand comes from the pseudohands -- which choice more often yields a winning hand? For the '​all'​ cases, reported to screen should be a summary of all combinations -- something streamlined which efficiently reports the summary of all combinations,​ a simpler version of what is [[http://​en.wikipedia.org/​wiki/​Blackjack#​Basic_strategy|displayed here]]. However, again here we will not take into account the difference between whether the player has a "​soft"​ or "​hard"​ hand. 
 + 
 +Grading: 
 +   * 15 points: If the player has a score of 15, and the dealer has 6, should you hit or stay -- and why? 
 +   * 10 points: If the player has a score of 15, what is the recommendation for each of the possibilities for the dealer'​s initial face-up card? 
 +   * 5 points: What are the recommendations for all of the possibilities for the player'​s score (only consider the possibilities 8,​9,​10,​11,​12,​13,​14,​15,​16) in light of each of the possibilities for the dealer'​s initial face-up card? 
 + 
 +Hand in your code electronically **[<​username>​_blackjack.cpp]**. Make sure the output of your code is clear, such that it is easy to understand what you are reporting. Answer clearly the questions above in the comments of your code near the top of your file. 
 + 
 + 
 +**Note:** We are not learning here how to "count cards",​ a practice that takes into account what other cards have been played in the deck and adjusts the probabilities accordingly. ​ The legality of counting cards is something that 
 +varies by jurisdiction. Here we are only looking at **probabilities in a statistical sense**: Given no other knowledge of the sequence of the remaining cards in the deck, in a statistical sense what is the best strategy for a given player'​s hand in light of what we know about the dealer'​s hand. 
 + 
 + 
 + 
 +===== 3. Signal and Background (40 points) =====
  
 In particle physics, we build massive high-energy particle colliders in the hopes of harnessing the energy in these collisions to produce exotic forms of matter. These processes are rare, so we design our accelerator to collide particles together millions of times a second in the hopes of capturing these elusive new entities. When created, these new forms of matter decay to more common familiar particles; these mundane decay products then fly out from the collision region and interact with our particle detector. ​ This massive device, often bigger than a good-sized office building, collects all the signals for each collision, called an "​event"​ in our vocabulary; each collision event is characterized by a collection of reconstructed observables describing the momenta, energies, trajectories and multiplicities of the outgoing particles. For example, the file In particle physics, we build massive high-energy particle colliders in the hopes of harnessing the energy in these collisions to produce exotic forms of matter. These processes are rare, so we design our accelerator to collide particles together millions of times a second in the hopes of capturing these elusive new entities. When created, these new forms of matter decay to more common familiar particles; these mundane decay products then fly out from the collision region and interact with our particle detector. ​ This massive device, often bigger than a good-sized office building, collects all the signals for each collision, called an "​event"​ in our vocabulary; each collision event is characterized by a collection of reconstructed observables describing the momenta, energies, trajectories and multiplicities of the outgoing particles. For example, the file
Line 88: Line 244:
  
 Start by **looking at the data** and doing the following: Start by **looking at the data** and doing the following:
-  * Write some code to run over the data events and fill nine histograms, one for each observable. Use bins of appropriate width such that the resulting plot is not too jagged bin-to-bin; for example, for Ht use bins that are 20 units wide spanning the range [0.0, 1000.0]. Several bins will be empty but the bins in the core of the distribution will be fairly full. +  * Write some code to run over the data events and fill a histogram ​for just one of the observables,​ Ht. Use bins of appropriate width such that the resulting plot is not too jagged bin-to-bin; for example, ​a good choice ​for Ht would be to use bins that are 20 units wide spanning the range [0.0, 1000.0]. Several bins will be empty but the bins in the core of the distribution will be fairly full. 
-  * Produce a plot for each observable, plotting ​the data with black points.  +  * Plot the data with black points. Make sure the plot has all the desired elements of a good histogram
-  * Hand in these plots electronically as a single ​pdf **[username_data.pdf]**. ​There are several ways one can do this; a simple, inelegant-yet-effective way would be to insert each of your output png/jpeg files into a PowerPoint or Word document and subsequently save this collection of plots as a single pdf. **Then, secure-copy this file to galileo, and submit it electronically just like any other file you have submitted this semester.**+  * Hand in this Ht plot for data electronically as a pdf **[<​username>​_data.pdf]**. ​
  
 Next we need to **inspect our signal and background models**: Next we need to **inspect our signal and background models**:
-  * Use similar code as in the above to make histograms ​for your simulated signal events ​ However, here normalize each of the nine histograms ​to the same number of events as observed in the data. Do this by first normalizing to unit area -- meaning scale the final contents of each histogram such that the area under each is 1.00. Then scale again, this time to match the area under the data curve (hint: the area under the data curve should be the same as the number of observed data events). Use the same binning as you used for your data histograms in each variable.   +  * Use similar code as in the above to make a histogram ​for the simulated signal events ​in the variable Ht.  ​However,​ here normalize each of the histogram ​to the same number of events as observed in the data. Do this by first normalizing to unit area -- meaning ​**scale the contents of each histogram** such that the area under the curve is //1.00//**Then scale again,** this time to match //the area under the data curve// (hint: the area under the data curve should be the same as the number of observed data events). Use the same binning as you used for your data histogram.   
-  * Use the same code to run over the simulated background events, filling ​nine similar normalized-to-the-data ​histograms. +  * Use this same code to run over the simulated background events, filling ​similar normalized-to-the-data ​histogram ​for the Ht variable
-  * Produce a plot for each observable, overlaying ​the simulated signal and simulated background. Make the signal a solid red histogram, and the background an outline-only blue histogram.  +  * Hand in these plots electronically as pdfs as well **[<​username>​_SigShape.pdf]** and **[<​username>​_BkgShape.pdf]**. ​
-  * Hand in these plots electronically as a single ​pdf **[username_SBshapes.pdf]**. ​+
  
 Now we need to determine how much signal and background the data favors. We will therefore perform a two-component "​fit"​ in one of the variables, Ht. The two components are signal and background; we seek for the sum of signal and background to match as closely as possible the data across all the bins of the Ht histogram. Ht is common shorthand in the field of collider physics; it typically represents the sum of the energies of each of the reconstructed objects in the event. From your signal vs. background shapes, it should be apparent that the signature of our signal is typically more energetic (ie, favors higher Ht values) than the background. ​ Now we need to determine how much signal and background the data favors. We will therefore perform a two-component "​fit"​ in one of the variables, Ht. The two components are signal and background; we seek for the sum of signal and background to match as closely as possible the data across all the bins of the Ht histogram. Ht is common shorthand in the field of collider physics; it typically represents the sum of the energies of each of the reconstructed objects in the event. From your signal vs. background shapes, it should be apparent that the signature of our signal is typically more energetic (ie, favors higher Ht values) than the background. ​
  
-Back to our fit. There are several ways to do this. Many are computationally expensive and can easily become intractable. We will do something simple here using a chi^2 fit (see [[http://​faculty.virginia.edu/​comp-phys/​phys2660/​wiki/​doku.php?​id=notes|lecture ​10 for a review]]. Define a summed chi^2 over all of the bins of the Ht distribution:​+Back to our fit. There are several ways to do this. Many are computationally expensive and can easily become intractable. We will do something simple here using a chi^2 fit (see [[http://​faculty.virginia.edu/​comp-phys/​phys2660/​wiki/​doku.php?​id=notes|lecture ​11 for a review]]). Define a summed chi^2 over all of the bins of the Ht distribution:​
  
 \\ <​math>​\large \chi^2 = \sum_{i=1}^{k} \frac{(n_i - N_{i}^{pred})^2}{\sigma_i^2}</​math>​ \\ <​math>​\large \chi^2 = \sum_{i=1}^{k} \frac{(n_i - N_{i}^{pred})^2}{\sigma_i^2}</​math>​
  
 where: where:
-  * <​math>​ n_i </​math>​ is the number of observed events in the data in bin <​math>​ i</​math>​+  * <​math>​ n_i </​math>​ is the number of observed events in the data in bin <​math>​ i </​math>​
   * <​math>​ \sigma_i </​math>​ is the statistical uncertainty on the number of observed events in the data in bin <​math>​ i</​math>​   * <​math>​ \sigma_i </​math>​ is the statistical uncertainty on the number of observed events in the data in bin <​math>​ i</​math>​
   * <​math>​ N_{i}^{pred} </​math>​ is the sum of the predicted signal and background contributions in bin <​math>​ i</​math>​ (see below for more)   * <​math>​ N_{i}^{pred} </​math>​ is the sum of the predicted signal and background contributions in bin <​math>​ i</​math>​ (see below for more)
Line 125: Line 280:
 the problem becomes much easier. One can simply scan different values of <​math>​ f_s </​math>​ and <​math>​ f_b </​math>,​ consistent with this simple constraint, and find where the minimum of the chi^2 occurs. the problem becomes much easier. One can simply scan different values of <​math>​ f_s </​math>​ and <​math>​ f_b </​math>,​ consistent with this simple constraint, and find where the minimum of the chi^2 occurs.
  
-Write a piece of code that reads in the Ht histograms from signal, background and data and executes this simple chi^2 fit. You can do this in a crude manner (scanning all possible values) or an intelligent manner (starting with say a 50/50 mix and choosing subsequent pairs such the chi^2 is reduced, iterating until the best fractions are found). ​More credit will be give for intelligent solutions. Make sure that the code reports ​to the command line the preferred ​fractions of signal and background, <​math>​ f_s </​math>​ and <​math>​ f_b </​math>,​ that the data prefers. +Write a piece of code that reads in the Ht histograms from signal, background and data and executes this simple chi^2 fit. You can do this in a crude manner (scanning all possible values) or an intelligent manner (starting with say a 50/50 mix and choosing subsequent pairs such the chi^2 is reduced, iterating until the best fractions are found). ​  
-Hand in this code electronically **[username_chi2fit.cpp]**.+ 
 +The code should report ​to the screen: 
 +  - The chi2 value when assuming a 50/50 mix of S and B. 
 +  - The fractions of signal and background, <​math>​ f_s </​math>​ and <​math>​ f_b </​math>,​ that the data prefers, including the final chi2 value achieved 
 + 
 +Make sure these pieces of output are properly labeled when printed to screen. No other output should be produced. 
 + 
 +Hand in this code electronically **[<​username>​_chi2fit.cpp]**.
  
 +-!
hw/final.1335992647.txt.gz · Last modified: 2012/05/02 17:04 by neu