Category: Uncategorized

Question 2: Add Two Number

The description of the question can be in the link

https://leetcode.com/problems/add-two-numbers/

 

  1. My code for the question:

code

Idea: The full idea is clear that we need to take out the number one by one and then do the sum. The first thing needs to be careful is the carry for the number. Next thing we need to be careful is when the last digits are calculated, we need to make sure that there is no extra 1 there to be appended.

BABA IS YOU LEVEL: Solitary Island

  1. Stage 00: Poem
    • Push down the line is twice
    • Push violet into the block next to it
    • Push the rose underneath the work baba
    • Push up the word rose
    • Use rose to touch baba to get the win
  2. Stage 01: Float
    • Make the rule” Rock is you “
    • Use rock to touch the flag
  3. Stage 02:Warm River
    • Make the rule” River is hot and float”
    • Go through everything that is floating to touch the flag.
  4. Stage 03: Bridge Building:
    • Push rock to sink one block of water
    • Make rule ” rock is you ” to move the rock
    • Make the rule “rock is push ” again to sink one block of water again
  5. Stage 04: Bridge Building?
    • Use Push to sink one block of water
    • Make the rule “Rock is You”
    • Sink another block with the word”sink” from the sentence “flag is win”
    • Push word “flag” and ” win” to the very right of the place
    • Push is from the sentence “rock is you ” to make the rule “flag is win”
  6. Stage 05:Victory Spring
    • Use two cog to sink the water next to the word”win”
    • push the line  text is float next to the win and push the word”win” back
    • Deactivate the rule” text is float” to clear the paths
    • Make the rule“ baba is w.in”
  7. Stage 06:Research Facility
    • Push the bolt to the line where keke and the word”skull” is.
    • Push the bolt one grid right to make sure it moves rightward.
    • Push the word ” defeat”  leftward to take the place of the word “hot”
    • Then keep tapping space to let the bolt push away the word “skull”
    • Go downward to push out the word “win” and the only thing needs to be noticed is that you should keep waiting until the bolt comes out.
    • Then make the rule “bolt is win”
  8. Stage 07: Assembly Team
    • Push the word “baba” to the most left. Then use the word to make two robots standing on two different lines.
    • Sink one block of water with one robot.
    • Make the rule: baba is you
  9. Stage 08: Tiny Pond
    • Make the rule: key is flag
    • Make the rule: flag is you and open. As one key has already been transferred into a flag. Use on flag to sink the water and use the other flag to push the word “win” out
    • Make the sentence “flag is win ” and “baba is you “
  10. Stage 09:Catch the thief
    • Push down the rule “baba is you”
    • Make rule “robot is baba”
    • Push word “win ” out
    • Make rule “baba is win”
  11. Stage 10:

BABA IS YOU Level : Lake

  1. Stage 01: ICY Water:
    • Push away the word “sink”.
    • Push the word “wall” onto the jelly underneath the flag.
    • 推走单词“sink”
    • 将wall这个单词推到jelly上。这样就可以碰到flag了。
  2. Stage 02:Turns
    • Make the sentence”star is sink and push”. Then push the star onto the skull to eliminate the skull.
    • Push the word “crab” up one grid, push the word”is” under it and push them together to make the sentence”crab is baba is you”. Then the crab outside the wall will become baba and you can control it to touch the flag.
    • 首先组成句子“star is sink and push”。然后把star推到skull上使得skull消失。
    • 其次组成句子：crab is baba is you 。这样墙外的crab变成baba从而可以操纵它去碰旗子。
  3. Stage 03:Affection:
    • Make the sentence “Love is move.” Then wait until the heart is coming out of the grass.
    • 组成句子“love is move ”然后让爱心走出草丛即可。
  4. Stage 04：Pillar Yard
    • Push the pillars to make a queue horizontally next to the star wall. Then push the pillar line into the wall. After that, push the word”pillar” to make the sentence “pillar is you”.
    • 将柱子拍成一排，和旗子在同一水平线。之后将一整串柱子推进去。再然后用”pillar”去组成句子”Pillar is you “
  5. Stage 05:Brick Wall
    • Directly make the sentence: baba is win.
    • 直接组成句子“baba is win”
  6. Stage 06:Lock
    • Push two keys to open two horizontally aligned doors.
    • Use rock to make two sentences: Rock is push and Rock is open.(vertically and horizontally)
    • Push the stone to open the door.
    • 先用钥匙打开两扇门。
    • 用Rock 组成两句句子：Rock is push; Rock is open.
    • 用石头开门。
  7. Stage 07：Novice Locksmith
    • Make” key is push” vertically and ” key is open”horizontally with same “is”.
    • Push the key to open the door. Them make the sentence “door is push” to push the door away to get to the flag.
    • 先用一个“is”组成“key is push ” 和“key is open ”两句话。第一句竖直第二句水平。
    • 然后用钥匙开门再组成一个句子“door is push”。之后再把门推开。
  8. Stage 08：Locked in
    • Push the work “jelly” to make the sentence” wall is jelly”
    • Make the sentence “baba is win”
    • 先推单词“jelly”组成句子“wall is jelly”。
    • 然后组成句子“ baba is win”.
  9. Stage 09：changeless
    • Deactivate the sentence” Rock is rock”(This makes the rock unchangeable).
    • Then make the sentence “Rock is flag”
    • 首先打乱句子”Rock is rock”
    • 然后组成句子“Rock is flag”
  10. Stage 10: Two Doors
    • Make the sentence “Door is you”. Then push the remaining part of the sentence right next to the corresponding part of the sentence” door is you” (is by is and you by push).place Keke one grid left to the word”door”.
    • Push two “is” to the left first and then push the word “push” and ” you “to the left.
    • Then use keke to push the word keke and door to the left. Repeat the procedure with the door as the sentence changes to “Door is you”
    • Stop until “you ” is two blocks away from the word”key”
    • Use keke again to push the word”keke” and “door ” to the left again.
    • This time push the word “is ” of the right sentence to the bottom of the sentence “Door is you ” Then push up one grid and push the is next to word”key”.
    • push sentence “door is you ” one grid down and  push the word you one grid left. This time you become the key.
    • control the key to make the sentence flag is win and touch the flag.
  11. Stage 11: Jelly Throne
    • Generate the sentence “Jelly is baba” with the is from sentence “flag is push”
    • Make the sentence “Flag is win””
    •  组成句子” Jelly is baba”
    • 用墙内的baba 去组成句子“flag is win”
  12. Stage 12:Crab Storage
    • First make the sentence “flag is open” vertically. Then open the door
    • make the sentence “baba is baba”
    • Push the word “crab” to make the sentence”crab is win”
    • 首先组成句子flag is open去用旗子开门
    • 然后组成句子 baba is baba
    • 最后将crab推至顶部组成 crab is win
  13. Stage 13: burglary
    • Make rules” star is open” and ” wall is shut”
    • Use star to open the wall
    • Deactivate the rule “key is defeat”
    • Make the sentence ” key is win”
    • 首先组成句子“star is open” 和“wall is out”
    • 推走单词key 使得“key is defeat”失效
    • 组成句子“key is win”
  14. Extra 1: Submerged ruins
    • Push the rock left to the word”crab”
    • Use the word “rock” and “is ” to make the sentence “Rock is you”
    • Control the Rock to walk into the place guarded by crabs while keep baba outside.
    • Control baba to push the word “crab” in to complete sentences.
    • control rock to touch the flag.
    • 首先将单词Rock推至crab 左边。
    • 组成句子rock is you
    • 操控Rock 和baba使得Rock 走到flag边上，保持baba在外
    • 用在外面的baba把右上角的句子推完整
    • 用rock去触碰旗子
  15. Extra 2:Sunken Temple
    • Push rock and jelly in to finish the sentence.
    • Push the word”rock” to make the sentence rock is you (not vertically, push away baba instead)
    • Make the sentence ” rock is push” and “baba is you ” together with one “is”
    • push rock next to the crab and is next to the rock
    • Push is and rock together to let rock in.
    • make the sentence “rock is you ” again. Then use rock to touch the flag.

 

 

Goodbye

Sometimes, saying goodbye is as easy and simple as a short phrase like “Gracias Manu” and “Menba Out”. Sometimes you miss the players not only for his play, but also for his role played in the entire childhood. I just feel like my childhood and youth has gone with the retirement of these figures, and it will never come back.

We need to learn to say goodbye, to these heroic figures, inspiring players, and our own memory.

 

Comment on C++

Lecture 1

  1.  #include is really useful when you want to use facilities that is not in the core language. include the library name you want to use inside the <> symbol after it.
  2. Cout is the command to display values.
  3. All the statement must end with ” ; “.
  4. Source code is the fundamental component of a computer program that is created by a programmer.
  5. C++ is a compiled language so you need to translate the source code in a file that the computer can execute. This file is generated by the compiler and is called the object code ( .obj )
  6. Source code is portable between two different platforms while object code cannot.
  7. Variables in C++:
    1. Need to be declared fist.
    2. Can be initialized when declared( with variablename(value)).
    3. There are several built-in type:
      1. int ,short int,long int, unsigned int, unsigned short int etc
      2. float, double, long double.
      3. char unsigned char ,bool
      4. enum  (B. Strousgrup , 2013, The C++programming language, fourth edition. pp50)
    4. One can implement his own type: e.g. class.
    5. The variable with const type must be initialized when it is declared and can not be modified later.
    6.  <iosmanip>:  The standard library provides manipulators corresponding to the various format states and state changes.
    7. <vector > contains the implementation of the standard-library vector container.
    8. <Algorithm> is a collection of routines for manipulating standard-library style containers
  8. Anything declared in a scope will be destroyed when it goes out of the scope.
  9. “break”  terminates the execution of the nearest enclosing loop.
  10. “continue”  Statement to jump to the beginning of the next iteration in the nearest enclosing while statement.
  11. The output of the function should also be declared.
  12. The separation of the condition for loop is made by notation” ; “, not “,”!!!
  13. In the single statement for scopes, the braces can be omitted.
  14. Vector operations.(Notice that the v.end() returns an iterator to the memory place one past the last element.)
  15. switch: a switch selects among a set of alternatives (with case label). The expression in the case labels must be a constant expression of integral or enumeration type.
  16. Passing arguments problem: in the function, the value of the variable is not used directly. Instead, they make a copy of the value in the variable and modify the value of it.
  17. One can use “& xx” for passing arguments.
  18. One can use ” const & xx ” for passing argument by const reference.

 

Lecture 2

  1. Creating objects:
    1. Global Variable: static storage.
    2. new operator is used to create an object that we want to store it in any circumstance. For example, if we want to store a variable create during the function. In general case, if we declare the variable in the function, it will be destroyed out of the scope. Hence if we want to store it, we can use the new operator to allocate memory for storing it. Delete operator is the corresponding way of destroying a variable.
  2.  The expression ” type & b = a” means to define the b as the reference to a. i.e. no matter what value a changes into, b also changes in to that vale. Otherwise b is just initialized with value of a.
  3. If add “&” notation between the type and arguments of the function, it means that instead of returning the value of the function, we return the reference of the return of the function.
  4. POINTER!!!!!!!!:
    1. Pointer to an object is the value representing the memory address of the object.
    2. In many cases, its cheaper to pass the pointer than the whole object.
    3. The object is accessible through its pointer. (This line is important as it tells the way how we can put a function as an argument of  the other function.)
    4. Creation of a pointer: Typename & *iptr. (Here typename can be any built in type or used defined type; iptr is just the name of the pointer.)
    5. Take the value of the address of an existing object: Typename *iptr  = & a.
    6. How to access the object through its pointer : Typename i = *iptr.
  5.  The memory on the heap must be freed using the operator deleted before the end of the program. (Notice the reason is that once a new variable is created, its memory space is “locked”, no one else can store things there unless a key is insert, i.e. delete operator.)
  6. One way to do this is to use the smart pointer “->”. The smart pointer can delete automatically without using the delete operator.
  7. Pointers to function: E.g. Typedef double (*Myfuntype)(double). This line defines a type named Myfuntype which is a type of function that takes a double and return a double.
  8. Namespace: With namespaces , one can group functions, classes, typedefs, under a name.
  9. There are different naming conventions, see lecture notes 3, page 20
  10. Classes: A class is defined  to have a set of members,which can be data, function or type members. It We distinguish between class and instance of a class. (For example in the example   on page 6 of the lecture notes 4. the number takes they type complex number is called the instance of the class ComplexNumber.
  11. The instance is const argument if the member is declared const.
  12. Functions declared within a class definition are called member functions and can be invoked only for a specific variable.
  13. Data Member:  It can be plain values, references, pointers and const version of these. Const and reference members must be declare at the construction of the instance.
  14. Constructor initialize instances of classes. (For example, You construct a class called complex number. Then if you want to define a variable with type complex number, you need to initialize that variable no matter you want to put a value in it or not. Hence you need a constructor to execute this action.
  15. Default Constructor: If initialization is not done explicitly, then compiler will call the default constructor of the data member.
  16. Default constructor takes no arguments.
  17. There is one example for the constructor in the Lecture 4 page 11. The line “Explicit ComplexNumber (double, double = 0.0)”. This gives an example of the constructor and the imaginary part has already been initialized while the real part is not. It means that when we only put one number into any variable with complexnumber type, it initialized the first part of the function.
  18. A copy constructor takes an instance of the same type and create a new instance from that.
  19. The Explicit protects against implicit type conversion.
  20. For the example in the page 14 , lecture 4. The 4th line is the default constructor with initializing both dRe_ and dIm_. The fifth line is to initialize the data member with the member provided by the arguments.
  21. It is needed to use the namespace when accessing the function members of the class for implementation.
  22. Overloaded Operator: one can define the operator for the instance of the class as they wish. This is called the overlaoded operator. Computer will detect the type of the input and execute corresponding operator.
  23. There is a special syntax for the declaration of the operator members:                           Classname & operator __ (const classname  &  ) [The underlined part should be filled with the operator such as “+”]
  24. One special operator is ().
  25. The operator  “=” with argument (const reference to) the user defined class is the copy assignment.
  26. The special operator “*this” has a function that is to return a reference to the instance it was called.

Lecture 3

  1. Template functions: It gives the function to be defined based on the input argument. So the compiler will detect the type of the input provided, and then give the type to the dummy variable used in the template title( The line that looks like template<typename T>, where T is a dummy variable.)
  2. If the argument of the function uniquely determines the template type argument , then there is no need to specify the template parameter at call.
  3. If there is only one parameter in the template, then taking several input may cause compiling error as the type that should be used is not clear.
  4. In C++, one can implement template class. One may give a default type in the template line i.e.template<typename T,typename Op = std::less<T>>. If no Op is not specified, then it will take the default type.
  5. We can also do templates with non -type arguments and specialization. For example. define template function with the integer n in order to calculate the fibonacci sequence.
  6. There is also a partial templates specialization:  sometimes the function behaves differently when one of the input is of specific type.
  7. Full specialization: the behaviour might be very specific for a a particular template argument list.
  8. A (singly) linked list consists of nodes. Each node 
    1. has some data
    2. has set and get method for this data
    3. knows about the next node
    4. cal tell if it has a next node
    5. has a get method for the next node

Comment on Monte Carlo Method

There is a general notice before the start of this comment: In numerical simulation, monte carlo method is useful for larger dimension, whereas finite difference method is more useful tan Monte Carlo Method in smaller dimension.

Lecture 1

  1. The generation of the random number includes three steps: Generating independent uniform on [0,1]; generating independent standard normal; generating correlated normal.
  2. The useful RNG is Mersenne Twister, which is 219937-1.
  3. Four popular method for random normal generators:
  4. Box-Muller: advantage: easy to understand; Disadvantage: log, cos and sin are quite expensive to calculate.
  5. Marsaglia Polar Method: Advantage: Not that expensive compared with Box Muller method. Disadvantage: Need to abandon some of the random numbers, so it is not that useful when parallel is used.
  6. Marsaglia zigguart method: Advantage: fastest. Disadvantage: hardest to understand.
  7. Inverse Normal Method: Advantage: As accurate as other method,, but still costly.
  8. The normal cdf is related to the error function erf(x): Φ (x) = 1/2+1/2 erf (x/ sqrt(2)).
  9. Two ways calculate the correlated random normal numbers:
  10. Cholesky factorization and PCA decomposition to find out the method for the doing

Lecture 2

  1. Integrating a function on the range of [0,1] is just like calculating the expectation of the function under uniform distribution. Hence the integration can be estimated through calculating the average of the function evaluated at random [0,1] uniform numbers.
  2. The estimator above is unbiased and consistent.
  3. The error is to subtract estimated value from the real value. Bias is the expectation of the error. Root Mean Square Error is square root of the expectation of error square.
  4. The empirical variance can be calculated via general procedure: sum of square minus square of sum. To get the unbiased estimator, one can times the empirical variance with the fraction (N-1)/N.
  5. To calculate the number of samples needed for the required accuracy: N = (σ s(c))/ε)^2.
  6. The root means square error can be regarded as the variance of the error.
  7. When d>4 Monte Carlo Method is much more useful than finite difference method.
  8. Similar way of simulating expectation with independent and correlated density random normal. Simply invert the normal distribution and take expectation on the invnorm and original function with regard to uniform distribution. It’s similar for the correlated random normal as only need times the independent random normal with the decomposed variance covariance matrix based on Cholesky or PCA Method.
  9. The decrease of the accuracy always implies the increase of the computing time. Hence there is a trade-off between the accuracy and efficiency.

Lecture 3

  1. Variance reduction is very important in Monte Carlo Method as one may apply simple method to reduce the variance in certain circumstance.
  2. There are six ways in variance reduction.
  3. Antithetic Method: Notice that this method can only be applied for the situation when the distribution function is and even function. Advantage : The variance is always reduced. Disadvantage: Disadvantage: The computational cost doubles. Hence net benefit only if the co-variance of f(w) and f(-w) is smaller than  0.
  4. Best case: linear payoff. Worst case: symmetric payoff.
  5. Control variate. If there is another payoff f for which we know the expectation, can use g-E(g) to reduce the error in f-E(f).
  6. The good situation is f and g are near linear correlated. Worst situation is that f and g are independent.
  7. Importance Sampling: The basic idea is change of probability measure.
  8. For the last sentence in the page 20 of this lecture, the choosing of μ2 which gives the distribution of the new sampling.
  9. For the normal distribution, change of mu can be useful when one part of the tail is important,while change of σ is useful when both tails are important.

 Lecture 4

  1. Stratified Sampling: The key idea is to achieve a more regular sampling of the most important dimension in the uncertainty.
  2. Procedure: divide the [0,1] interval into M strata ——> take L samples from each strata. ML = N i.e.total sample sizes.
  3. The procedure for this simulation: Break [0,1] in to M strata ——> Take L samples U with uniform probability distribution ——> Define independent random vector from invnorm and uniform samples——> compute average for each strata and overall average.
  4. There is a trade-off between efficiency and confidence.
  5. Notice that it is better to sample more from the strata with her variability.
  6. The multivariate application is similar.
  7.  For higher dimension, the number of cube to choose sample from can be quite large. This may forces the sample chosen from each cube can be quite small. Hence the  new method called Latin Hypercube is introduced.
  8.  Latin Hypercube: Generate M points dimension by dimension ,using sampling with 1 value per stratum, assigning them randomly to the M points to give precisely one point in each stratum. ——> Take L such independently generated set of points, each giving the same average.
  9. In the special case that the function can be written in the sum of one dimension function, then there will be a very large sample size reduction by using large sample size M.

Lecture 5

  1. Quasi Monte Carlo. Standard quasi monte carlo uses the same equal weight estimator but chooses the points systematically so that the estimate is biased, error roughly proportional to 1/N and there is no confidence interval.
  2. To construct the set of points we want to use for the quasi Monte Carlo method, there is one thing called Rank-1 Lattice Rule. (see notes page 9).z is the generating vector with integer components co-prime with N.
  3. Sobol sequence: The idea of the Sobol sequence is to subdivide each dimension with into halves ,quarters etc, and in each cube the number of the sample points are the same.
  4. randomized QMC: Using randomized QMC.
  5. QMC points have the porperty that the points are more uniformly distributed through the lowest dimension. Sonsequently, itis important to think about how the dimensions are allocated to the problem. Previously, have generated correlated Normals through the decomposition of the variance co-variance matrix.

Lecture 6

  1. Finite precision arithmetic: a floating point can be represented f = x × 2n  where n is the integer expoennt which is given by some number of bits. 1/2<|x|<1 also represented by some number of digits.
  2. relative error is about 10-16 for long and 10-7 for short.
  3. For the sum, the standard error for the sum is given by the 2-S sqrt(N). where N is the size of the sum.
  4. The error can be fatal when we want to simulate the differetiation.
  5. Complex trick: involving complex number may also gives the same result but less error. We only need to take the imaginary part of the function evaluate at point (x+ i dx)). Hence one can take dx small enough. The only issue is that the function should be analytic.

Lecture 7

  1. Greeks is a set of functions that measure the change of value of one derivative corresponding to change of one parameter.
  2. The error might be quite large if take random uniform vector for each X(θ + Δ θ) and X(θ – Δ θ).
  3. In order to solve this, we use same random input for both X(θ + Δ θ) and X(θ – Δ θ).
  4. Finite Difference Sensitivity  : There might be some issues when the payoff function is not continuous, hence we need to be very careful about the payoff jump at the non continuity point of the function.
  5. The probability for the payoff jumps at the interval [θ – Δ θ,θ + Δ θ] is O(Δ θ). With this, the variacne might get really large when the Δ θ is small.
  6. Hence what we want to minimise is the mean square error. And the best choice for Δ θ is N -1/5.
  7. For discontinuous second derivative, it will also makes the variance quite large.

Lecture 8

  1. Likelihood ratio method and path-wise sensitivity: In previous method we consider derivative of the density function with respect to the &theta; while the path-wise sensitivity take the derivative of the function that we want to take the expectation with.
  2. In the likelihood ratio method, we do not change the measure. We change the function we want to to take expectation with.
  3. For this method , the variance is very large when &sigma; is  small, and it is also large for &Delta; when T is small. (We are talking about estimating the price ).
  4. For path-wise sensitivity, we consider differentiate the function instead. But in this case, we need to assume that the function is differentiable. Similar thing can be applied to second order differentiation.
  5. For the discontinuous situation, we can use smooth function to approach non continuous function, and take the limit as the final result. E.g one example for smoothing is to use the cumulative normal to smooth the digital call function.
  6. The idea of these two methods are still based on simulating, hence we can calculate the expectation via the simulation method with respect to the function inside the bracket after the transformation.