[CC150] Chapter 7 Mathematics and Probability
7.1 You have a basketball hoop and someone says that you can play one of two games.
Game 1: you get one shot to make the hoop.
Game 2: you get three shots and you have to make two of three shots.
If p is the probability of making a particular shot, for which values of p should you pick one game or the other?
Game 1: the winning probability is p.
Game 2: the winning probability is p^2(1 - p) * C^2_3 = 3p^2(1 - p)
We can easily get if p < 0.5 we should choose Game 1.
7.2 There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Assume that each ant randomly picks a direction, with either direction being equally likely to be chosen, and that they walk at the same speed.
Similarly, find the probability of collision with n ants on an n-vertex polygon.
Clearly, each ant has two choices. In total, there are 2^3 = 8 possibilities. To make sure that they do not collide, they have to choose the same direction, clockwise or counter-clockwise. In other words, the probability of collision is 1 - 2/8 = 3/4.
For n-vertex polygon, there are 2^n possibilities, and the probability of collision is 1 - 2/2^n = 1 - 2^(1-n).
7.3 Given two lines on a Cartesian plane, determine whether the two lines would intersect.
Check whether the slopes are the same. Note that we should not use x == y; instead, (x - y) < epsilon should be used due to the accuracy of floating point numbers.
7.4 Write methods to implement the multiply, subtract, and divide operations for integers. Use only the add operator.
TBF.
7.5 Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis.
TBF.
7.6 Given a two-dimensional graph with points on it, find a line which pass the most number of points.
This problem is in leetcode as Max Points on a Line.
7.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.
The main idea is to create three queues.
Remark: 1. Priority queue could also be used to reduce the find minimum operation.
2. To avoid duplicates, we only push from the chk[minidx] to the end.
Game 1: you get one shot to make the hoop.
Game 2: you get three shots and you have to make two of three shots.
If p is the probability of making a particular shot, for which values of p should you pick one game or the other?
Game 1: the winning probability is p.
Game 2: the winning probability is p^2(1 - p) * C^2_3 = 3p^2(1 - p)
We can easily get if p < 0.5 we should choose Game 1.
7.2 There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Assume that each ant randomly picks a direction, with either direction being equally likely to be chosen, and that they walk at the same speed.
Similarly, find the probability of collision with n ants on an n-vertex polygon.
Clearly, each ant has two choices. In total, there are 2^3 = 8 possibilities. To make sure that they do not collide, they have to choose the same direction, clockwise or counter-clockwise. In other words, the probability of collision is 1 - 2/8 = 3/4.
For n-vertex polygon, there are 2^n possibilities, and the probability of collision is 1 - 2/2^n = 1 - 2^(1-n).
7.3 Given two lines on a Cartesian plane, determine whether the two lines would intersect.
Check whether the slopes are the same. Note that we should not use x == y; instead, (x - y) < epsilon should be used due to the accuracy of floating point numbers.
7.4 Write methods to implement the multiply, subtract, and divide operations for integers. Use only the add operator.
TBF.
7.5 Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis.
TBF.
7.6 Given a two-dimensional graph with points on it, find a line which pass the most number of points.
This problem is in leetcode as Max Points on a Line.
7.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.
The main idea is to create three queues.
Remark: 1. Priority queue could also be used to reduce the find minimum operation.
2. To avoid duplicates, we only push from the chk[minidx] to the end.
Comments
Post a Comment