text:
### josdas's blog

By josdas, history, 3 years ago, translation, ,

570А — Elections

We need to determine choice for each city. Then sum it for each candidate and determine the winner.

O(n * m)

Solutions

570B — Simple Game

Lets find which variant is interesting. For Andrew is no need a variant wherein |a - m| > 1 because we can increase probability of victory if we will be closer to m. Then we consider two variants, a = c - 1 and a = c + 1. Probability of victory will be c / n for first variant and (n - c + 1) / n for second.

We need to choose better variant, also we must keep in mind case of n = 1.

O(1)

Solutions

570C — Replacement

Lets find how replacements occur. If we have segment of points with length l,we need l - 1 operations and stop replacements for this segment. If we sum lenghts of all segments and its quantity then answer will be = total length of segments — quantity of segments. After change of one symbol length changes by 1.

Quantity of segments can be supported by array. Consider events of merging, dividing,creation and deletion of segments. For merging we need to find if both of neighbors(right and left) are points then merging occured and quantity of segments reduced by 1. Other cases can be cosidered similarly.

O(n + m)

Solutions

570D — Tree Requests

We need to write vertices in DFS order and store time of enter/exit of vertices in DFS. All vertices in subtree represent a segment. Now we can get all vertices in subtree v on height h as a segment, making two binary searches.

We can make a palindrome if quantity of uneven entries of each letter is less than 2.

This function can be counted for each prefix in bypass for each depth.

For saving the memory bit compression can be used considering that we need only parity and function is xor.

O(m * (log + 26) + n)

D had a offline solution too in O(n + m * (26 / 32)) time and O(n * 26 / 8) memory

Solutions

570E — Pig and Palindromes

We need palindrome paths. Palindrome is word which reads the same backward or forward. We can use it. Count the dynamic from coordinates of 2 cells, first and latest in palindrome.

From each state exists 4 transitions (combinations: first cell down/to the right and second cell up/to the left). We need only transitions on equal symbols for making a palindrome. Note that we need a pairs of cells on equal distance from start and end for each.

For saving memory we need to store two latest layers.

O(n3) — time and O(n2) — memory

Solutions

•
• +44
•

 » 3 years ago, # |   +3 Auto comment: topic has been translated by josdas(original revision, translated revision, compare)
•  » » 3 years ago, # ^ |   0 thanks for Editorial :)))
 » 3 years ago, # |   0 Can you explain Problem D in a bit more detail.What is meant by in and out time of vertex.What is bypass the prefix.Doesn't makes much sense to average people like me.
•  » » 3 years ago, # ^ |   +26 Some of my thoughts: we can firstly compute the depth of each vertex and use a list to record the order of vertices in each depth. Let's consider the mentioned example (see the problem). the order of vertices in each depth is: Depth 1: 1 Depth 2: 2, 3, 4 Depth 3: 5, 6 This process can help us quickly find the vertices in depth h for the required vertex v in the following. Going on, after that, we use DFS to record the in-time and out-time of each vertex. For the given example, we have the DFS order as follows: DFS order: 1, 2, 2, 3, 5, 5, 6, 6, 3, 4, 4, 1 This can be addressed by applying the following pseudo-code: time = 1; DFS(vertex u)     in[u] = time ++;     for each son v         DFS(v)     out[u] = time++; The above-mentioned two steps can be considered as a pre-processing operation. Then, for each query, denoted by , we find the answer as follows. Case 1: if h is no more than the depth of v, return "Yes". Case 2: if v has no posterity that locates in depth h, then return "Yes". Case 3: Otherwise, find the required vertices in depth h, and judge "Yes" or "No". It can be said that, Case 1 is easy to solve. Here, Case 2 and Case 3 will utilize binary search (BS) to find the answer. Clearly, we will use BS to find the most left vertex (posterity) and the most right vertex (posterity) in the Depth-list of depth h for the vertex v. The BS exploits the in-time and out-time to find the most left vertex and the most right vertex. For example, if we want to find the most left vertex in depth h for the vertex v, we use the following pseudo-code: l = 0, r = Depth[h].size() -1, ans_left = -1; while( l <= r )     m = (l + r) >> 1;     if vertex Depth[h][m] is posterity of v         ans_left = m, r = m -1;     else if the ancestor of Depth[h][m] in depth "dep[v]" is in the left of v         l = m + 1;     else         r = m -1; Here, we will utilize the in-time and out-time of a vertex to judge that: whether a vertex A is the ancestor of a vertex B, or the left/right one of the ancestor of B in the Depth-list. An accepted source code: 12519227
•  » » » 3 years ago, # ^ |   0 I read your code. I didn't get one thing. In the part-> int x = mp[make_pair(v, h)]; if( x == 1 ) puts("Yes"); else if( x == -1 ) puts("No"); else run(v, h); }Why do you even check for the value of x? Why don't you straight away use run(v, h) everytime? What is the use of even using a map? It will only be helpful if the same inputs are encountered. Right?
•  » » » » 3 years ago, # ^ |   0 It is a memorization technique.
•  » » » 3 years ago, # ^ |   0 how does that check if the letters form a palindrome? I understand why you must use dfs to find the depth of nodes but I don't see how recording the in and out times of a node in the algorithm helps you solve this problem. Can you explain a bit?
•  » » » » 3 years ago, # ^ |   0 Ok I solved it. Pretty easy to be honest, it's hard only at first.
•  » » » 3 years ago, # ^ |   0 Can you explain me your time complexity? It seems to me that for each of the m query, you do two binary searches, and count the characters between ans1 and ans2. However, if (ans2-ans1) is big, isn't it going to be slow?I see you used map there. But how does it guarantee fast time complexity? I hope my question makes sense.
•  » » » 3 years ago, # ^ |   0 How do we check whether the letters form a palindrome? Iterating through all the elements in the range might get a TLE exception.
 » 3 years ago, # |   0 Please elaborate Problem E also.You have not explained very clearly?
•  » » 3 years ago, # ^ | ← Rev. 5 →   +42 Let's assume f(x1, y1, x2, y2) be the function which gives the number of ways of going from point (x1, y1) to (x2, y2).Now, the basic recurrence without memoization can be seen as : f(x1, y1, x2, y2) : if S[x1][y1] != S[x2][y2] : return 0 if x1 > x2 or y1 > y2 : return 0 // include the base case when have two neighbouring cells or single cell // if neighbouring cells have same value return 1 // else return 0 ans = 0 ans = ans + f(x1 + 1, y1, x2 - 1, y2) ans = ans + f(x1, y1 + 1, x2 - 1, y2) ans = ans + f(x1 + 1, y1, x2, y2 - 1) ans = ans + f(x1, y1 + 1, x2, y2 - 1) return ans Also, one argument in the recursive function is dependent on other 3, if we know x1, y1 and x2, we could compute y2 because the points are such that the manhattan distance beetween (1, 1), (x1, y1) and (n, n) and (x2, y2) are same.So, we could have three arguments to the recurrence. And as there's no loop inside, time complexity of the solution after memoization would be O(n^3). But, space complexity will also be O(n^3). To make the solution run in required space (256MB), observe the fact that the current layer (equidistant set of points from (0, 0)) is only dependent on next set of layers (points with distance one more) we could write a bottom up dp with O(n^2) space. Storing just last one calculated layer everytime.I wrote top-down dp with memoization, got Memory Limit Exceeded, couldn't code bottom-up dp properly in time! :'(
•  » » » 3 years ago, # ^ |   +3 thanks a lot :) this is so much clearer (y)
•  » » » 3 years ago, # ^ |   0 Could you explain more about how your dp solutions uses O(N^2) memory instead of O(n^3)? I am struggling to understand it.
•  » » » 3 years ago, # ^ |   0 can u tell me more clear how to find y2?
•  » » » » 3 years ago, # ^ |   0 Assuming 1 based indexing and the corners to be at (1,1) and (n, m).Now, if we are at (x1, y1), it means that the count of total moves is :moves = (x1 — 1) + (y1 — 1) [Because at each step either x1 increments by one or y1 increments by one]Similarly, from bottom corner we getmoves = (n — x2) + (m — y2)So y2 = n + m — x2 — x1 — y1 + 2
•  » » » » » 3 years ago, # ^ |   0 thanks, now understand.
•  » » » 11 months ago, # ^ |   0 Can you explain the memory optimization part a bit more?? and give the code please?? Would be really helpful
 » 3 years ago, # |   +9 The problems were great, but these explanations are a bit lacking. Could you please explain the solutions in more detail?
 » 3 years ago, # |   0 Second problem was top!! Just shows how important boundary conditions are while testing. Lesson learnt.
 » 3 years ago, # |   +9 C can be solved in _ O(nlogn+mlogn) _ using a Segment Tree, storing for each node the number of operation needed to transform the whole segment, and another 2 variables pref,and suff which allows to know if the segment has a "dot"-1prefix or "dot-1suffix" :) is a simple solution but it needs more memory 12518296
•  » » 3 years ago, # ^ |   0 I solved it with the same complexity but using binary indexed tree But this overkilles the problem alot in my opinionThis solution is the sane as before but without logn
 » 3 years ago, # |   +1 For C — regarding "...Quantity of segments can be supported by array." — we actually don't need to keep the segments. Rather we keep only current value of f() — and when we put a new symbol to the string — then f() changes by +-2, +-1 or 0. This depends solely on the old symbol and 2 its neighbors.12510601
•  » » 3 years ago, # ^ |   0 I also tried to solve C this way, but got wrong answer. Could you take a look at my code? 12511578
•  » » » 3 years ago, # ^ |   0 In the edge cases else if (t == n - 1) and else if (t == 0) the cur variable is not updated.Also I believe there can be out of bound issues in those edge cases, when n is 1 — as s[t - 1] and s[1] indexes are accessed there, which is surely beyond the string limits.
•  » » » 3 years ago, # ^ |   +3 A hint: you can also avoid dealing with those edge cases if you add a letter to the beginning and to the end of the string. This operation doesn't change f(s). After that your string will be of length n + 2 and all the replacement operations on it will be between indexes 1 and n inclusive — so the neighbours will never be out of string bounds.This makes code smaller — i.e. less errors possible, faster to type and verify.This is a general idea in many tasks — instead of dealing with edge cases — extend the field of work and work inside a sub field of that.
•  » » » » 3 years ago, # ^ |   0 Oh, that's nice, thank you. Surely will use this trick next time.
•  » » » » 19 months ago, # ^ |   0 this idea can save a lot of time from a newbie's point of view,thankyou!! :)
•  » » 3 years ago, # ^ |   0 At first I was trying to come up with a solution similar to the editorial, but then I realised that a change in F is only influenced by the neighbours.Anyways, here is my solution if anybody needs more help: 12512037
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 Great, thanks, so simple :) AC 12522984
 » 3 years ago, # |   0 I am struggling with problem CCan anyone give me a simplified explanation to it?Thanks
•  » » 3 years ago, # ^ |   +10 Consider the simplest case: The string, of length L, is formed by all dots. Clearly f(s) = L - 1.Imagine there k strings of consecutive dots of length L1, L2, ... Lk, separated by non-dot characters, the answer is just taking the sum of respective reductions, namely,Let's see how we can perform updates in constant time.Case 1: A segment's boundary becomes a non dot character. Number of dots reduced by 1, and number of segments is reduced by at most 1, depending on whether the segment is of length 1 or not. So the answer is reduced by at most 1.Case 2: A segment's boundary is extended by 1, but not merging other segments. Number of dots is increased by 1, number of segments unchanged. So the answer is increased exactly by 1.Case 3: A new segment is added (of length 1). This is the same as Case 2.Case 4: One segment is broken by two non empty segments (otherwise, it's just case 1). In this case, number of dots is reduced by 1, the number of segment is increase by 1. So the answer is reduced by 2.Case 5: Two non empty segments are merged. Number of dots is increased by 1, and the number of segments is reduced by 1. So the answer is increased by 2.So you need to check neighbors of the changing position to see which case the operation falls into and update the answer in constant time accordingly.
•  » » » 3 years ago, # ^ |   0 Thanks alot I solved it correctly ... But when i surfed the internet , i found an algorithm (data structure) called suffix array . Can it be used to solve this problem?
•  » » 3 years ago, # ^ |   0 Have a look at this comment. Comment Here...
•  » » 3 years ago, # ^ |   0 Each substitution on s[xi] (ci' -> ci) will only effect s[xi]'s two neighbors(s[xi-1] and s[xi+1], if it has). Only need to recalculate the value on (s[xi-1], s[xi], s[xi+1]).
 » 3 years ago, # |   0 Auto comment: topic has been updated by josdas (previous revision, new revision, compare).
 » 3 years ago, # |   0 Hi, I can't figure out what's wrong with my solution for D... Here it is: http://codeforces.com/contest/570/submission/12521712 Please help!
 » 3 years ago, # |   0 Problem D : Beware, Even printf , scanf giving TLE ;( using fast I/O got ACCEPTED .
•  » » 3 years ago, # ^ |   0 Your solution O(m * log * 26 + n). It is close to time limit.
•  » » » 3 years ago, # ^ |   0 I know, My bad , this was the solution i cud get along.
 » 3 years ago, # |   0 Could someone please give an in depth explanation of the dp in question E? I understand the dp which would require O(n^3), since you can find the other coordinate via the manhaten distance, but I am struggling to grasp the dp that would require O(n^2) memory
 » 3 years ago, # | ← Rev. 8 →   0 I did problem C using set and I have n+m*log(n) time complexity,here is my submission.Anyway this is a interesting way to solve this problem and execution time is very near to the algorithm that work in n+m time complexity.
 » 3 years ago, # |   0 I am not able to understand why in problem B second variant probability is (n-c+1)/n . why it is not (c+1)/n .
•  » » 3 years ago, # ^ |   0 If A is greater than the number of M, we are winning on any value from A to N.
 » 3 years ago, # | ← Rev. 2 →   0 PROBLEM 570C-REPLACEMENTfor the test case:3 3...1 .2 a3 bans should be:200correct me if i am wrong
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Where is the input string?
•  » » » 3 years ago, # ^ |   0 string was s= ...
•  » » 3 years ago, # ^ |   0 YesF(...) = 2 (... -> .. -> .)F(.a.) = 0 (.a.)F(.ab) = 0 (.ab)
 » 3 years ago, # |   0 For the first hour, I ended up solving the wrong problem C. now I am curious how to approach this problem, If instead of replace the operation was of insert . How would be approach the problem. eg : s="..as..qwert...." first query is 1 h s'="h..as..qwert...."
•  » » 3 years ago, # ^ |   0 Instead of an array using a balanced search tree. The need for surgery to insert and retrieve an item.
 » 3 years ago, # |   0 Can someone explain the author's solution of the tree-requests, i am trying to understand the xor part of the code but couldn't find any explanations..Here the link to the author's solution-http://codeforces.com/contest/570/submission/12523757
 » 3 years ago, # | ← Rev. 2 →   0 Can you perhaps provide more explanations in your solution to problem 570E? For example, what are stored in the array ou[dd][dd] and in[dd][2 * dd]? What is sotred in the array Si? Also, what does the variable ts represent?Thank you!
•  » » 3 years ago, # ^ |   0 ou[x][y] the position of the cell (x, y) on the diagonal.in[x][y] the number and position of the diagonal of the coordinate cell.
 » 3 years ago, # | ← Rev. 3 →   0 http://codeforces.com/contest/570/submission/12779125 why this solution get WA15??
 » 3 years ago, # |   0 In D question, I did not understand the XOR part. Could someone explain me?
 » 3 years ago, # |   0 Hi.Regarding Div.2 Problem C, I got WA on test 7 but it is very large.Can anyone help me with some test case?Here is my submission.
 » 3 years ago, # |   0 Problem D.I use technique similar to finding LCA,in order to find parent at i-th depth.But I have time limit,is this normal or the problem is in my code?code
 » 3 years ago, # |   0 Can anyone explain how the bit compression is used in problem D ?
 » 8 months ago, # |   0 In 570B Can anyone explain me the case when n is odd and the m is selected at middle of 1 to n range. (Say n=5 and m=3).Can't here we select both n/2 and n/2+2 as answer for a?


text:
# Thread: don't think there is a solution

1. Hi if
cosec(x)/(1-cosec(x) -cosec(x)/(1-cosec(x)=50

show that sec^2(x)=25

2. Originally Posted by dayalji
cosec(x)/(1-cosec(x) -cosec(x)/(1-cosec(x)=50
Hi dayalji and welcome to MHB!

You have a mismatched parenthesis, so it's difficult to tell what the problem is. Please correct your work.

Also, we ask that our users show their progress (work thus far or thoughts on how to begin) when posting questions. This way our helpers can see where you are stuck or may be going astray and will be able to post the best help possible without potentially making a suggestion which you have already tried, which would waste your time and that of the helper.

Can you post what you have done so far?

Originally Posted by greg1313
Hi dayalji and welcome to MHB!

You have a mismatched parenthesis, so it's difficult to tell what the problem is. Please correct your work.

Also, we ask that our users show their progress (work thus far or thoughts on how to begin) when posting questions. This way our helpers can see where you are stuck or may be going astray and will be able to post the best help possible without potentially making a suggestion which you have already tried, which would waste your time and that of the helper.

Can you post what you have done so far?
Hi Greg1313
I have written question again. Problem is the expressions cancel each other out and keep ending with zero.

If $\frac{cosec(x)}{(1-cosec(x)} - \frac{cosec(x)}{(1-cosec(x)} =50$

show that $sec^2(x)=25$

4. The left hand side of the equation you give above is identically 0, not 50.

5. I think I've found the typo . . .

Quote:
$\displaystyle \text{If }\dfrac{\csc}{1+\csc x} - \frac{\csc x}{1-\csc x} \:=\:50$

$\displaystyle \text{show that } \sec^2(x)\,=\,25$
$\displaystyle \begin{array}{cccc} \text{We have:} & \dfrac{csc x}{1+\csc x} - \dfrac{csc x}{1 - \csc x} &=&50\\ \\ & \dfrac{\csc x(1-\csc x) - \csc x)1+\csc x)}{(1+\csc x)(1 - \csc x)} &=& 50\\ \\ & \dfrac{-2\csc^2x}{1-\csc^2x} &=& 50\\ \\ & \dfrac{\frac{-2}{\sin^2x}}{1 - \frac{1}{\sin^2x}} &=& 50 \\ \\ & \dfrac{-2}{\sin^2x-1} &=& 50\\ \\ & \dfrac{-2}{-\cos^2x} &-& 50 \\ \\ &2\sec^2x &=& 50 \\ \\ & \sec^2x &=& 25 \end{array}$

.

format: plain


text:
# Spoilers should allow advanced formatting

With standard quotes, you can use advanced formatting, such as paragraphs.

> Sentence 1.
>
> Sentence 2.

Sentence 1.

Sentence 2.

However, this is impossible with spoiler blockquotes.

>! Sentence 1.
>!
>! Sentence 2.

Sentence 1. Sentence 2.

I think the spoilers should behave the save way as standard block quotes. Sometimes, it's nice to put a big explanation of the code in a spoiler, and currently I'm forced to use ugly
.

The issue is most likely caused by that spoiler block quotes are a hack, involving checking if the block quote begins with ! after rendering Markdown. This should be a part of Stack Exchange Markdown implementation in my opinion, not something implemented over actual Markdown.

Yep, definitely a bug, but for now instead of
 you could end each line with two spaces.

Foo

Bar

• Isn't... that what you do with normal markdown? – TheDoctor Apr 29 '14 at 21:44
• @TheDoctor With "normal" markdown, two newlines is a paragraph break. Adding two spaces after every line is a workaround for this. – Doorknob Apr 29 '14 at 21:45

It would be worth posting a bug report at meta.stackexchange if it hasn't already been done.

In the meantime:

>!
You can still use HTML markup to format spoiler text.

>!

>!
Like this,

>!
for example

>!

>!
Or this, even.

You can still use HTML markup to format spoiler text.

• Like this,
• for example

## Or this, even.

• It could be moved if neccessary. I'm just not sure how relevant this is to the entire network - I doubt that other sites need spoilers with paragraphs. – Konrad Borowski Apr 27 '14 at 20:02
• @xfix There was another bug with spoiler formatting that was recently fixed after a bug report was posted at meta SE. (It took a while for the admins to get round to it, mind you.) I think all the beta sites use identical themes, so the bug is almost certainly replicated in other places besides codegolf. – r3mainer Apr 27 '14 at 21:26
• Please no. HTML is so annoying to edit and view. -_- – Doorknob Apr 28 '14 at 2:24


text:
Without an after or a when.can you hear the rain?more quotes

# bauhaus: exciting

In Silico Flurries: Computing a world of snow. Scientific American. 23 December 2017

# visualization + design

The 2018 Pi Day art celebrates the 30th anniversary of $\pi$ day and connects friends stitching road maps from around the world. Pack a sandwich and let's go!

# $\pi$ Day 2015 Art Posters

2018 $\pi$ day shrinks the world and celebrates road trips by stitching streets from around the world together. In this version, we look at the boonies, burbs and boutique of $\pi$ by drawing progressively denser patches of streets. Let's go places.
2017 $\pi$ day
2016 $\pi$ approximation day
2016 $\pi$ day
2015 $\pi$ day
2014 $\pi$ approx day
2014 $\pi$ day
2013 $\pi$ day
Circular $\pi$ art

On March 14th celebrate $\pi$ Day. Hug $\pi$—find a way to do it.

For those who favour $\tau=2\pi$ will have to postpone celebrations until July 26th. That's what you get for thinking that $\pi$ is wrong.

If you're not into details, you may opt to party on July 22nd, which is $\pi$ approximation day ($\pi$ ≈ 22/7). It's 20% more accurate that the official $\pi$ day!

Finally, if you believe that $\pi = 3$, you should read why $\pi$ is not equal to 3.

All art posters are available for purchase.
I take custom requests.

Not a circle in sight in the 2015 $\pi$ day art. Try to figure out how up to 612,330 digits are encoded before reading about the method. $\pi$'s transcendental friends $\phi$ and $e$ are there too—golden and natural. Get it?

This year's $\pi$ day is particularly special. The digits of time specify a precise time if the date is encoded in North American day-month-year convention: 3-14-15 9:26:53.

The art has been featured in Ana Swanson's Wonkblog article at the Washington Post—10 Stunning Images Show The Beauty Hidden in $\pi$.

We begin with a square and progressively divide it. At each stage, the digit in $pi$ is used to determine how many lines are used in the division. The thickness of the lines used for the divisions can be attenuated for higher levels to give the treemap some texture.

Representing a number using a tree map. Each digit of the number is used to successively divide a shape, such as a square. (zoom)

This method of encoding data is known as treemapping. Typically, it is used to encode hierarchical information, such as hard disk spac usage, where the divisions correspond to the total size of files within directories.

At each level of the tree map, more digits are encoded. Shown here are tree maps for $pi$ for the first 6 levels of division. (zoom)

This kind of treemap can be made from any number. Below I show 6 level maps for $pi$, $phi$ (Golden ratio) and $e$ (base of natural logarithm).

At each level of the tree map, more digits are encoded. Shown here are tree maps for $pi$ for the first 6 levels of division. (zoom)

The number of digits per level, $n_i$ and total digits, $N_i$ in the tree map for $pi$, $phi$ and $e$ is shown below for levels $i = 1 .. 6$.

$PI PHI e i n_i N_i n_i N_i n_i N_i 1 1 1 1 1 1 1 2 4 5 2 3 3 4 3 15 20 9 12 19 23 4 98 118 59 71 96 119 5 548 666 330 401 574 693 6 2962 3628 1857 2258 3162 3855 7 16616 20244 10041 12299 17541 21396 8 91225 111469 9 500861 612330$

## Dividing the map

In all the treemaps above, the divisions were made uniformly for each rectangle. With uniform division, the lines that divide a shape are evenly spaced. With randomized division, the placement of lines is randomized, while still ensuring that lines do not coincide.

A multiplier, such as $phi$ (Golden Ratio), can be used to control the division. In this case, the first division is made at 1/$phi$ (0.62/0.38 split) and the remaining rectangle (0.38) is further divided at $/$phi$(0.24/0.14 split). The divisions of each shape can be influenced by another number and the level at which the division is performed. (zoom) Using a non-uniform multipler is one way to embed another number in the art. When a multiplier like$phi$is used, divisions at the top levels create very large rectangles. To attenuate this, the effect of the multiplier can be weighted by the level. Regardless of what multiplier is used, the first level is always uniformly divided. Division at subsequent levels incorporates more of the multiplier effect. The orientation of the division can be uniform (same for a layer and alternating across layers), alternating (alternating across and within a layer) or random. This modification has an effect only if the divisions are not uniform. The divisions of each shape can be influenced by another number and the level at which the division is performed. (zoom) ## Adjusting line thickness To emphasize the layers, a different line thickness can be used. When lines are drawn progressively thinner with each layer, detail is controlled and the map has more texture. When all lines have the same thickness, it is harder to distinguish levels. The divisions of each shape can be influenced by another number and the level at which the division is performed. (zoom) You could see this as a challenge! Below I show the treemaps for$pi$,$phi$and$e$with and without stroke modulation. The divisions of each shape can be influenced by another number and the level at which the division is performed. (zoom) When displayed at a low resolution (the image below is 620 pixels across), shapes at higher levels appear darker because the distance between the lines within is close to (or smaller) than a pixel. By matching the line thickness to the image resolution, you can control how dark the smallest divisions appear. The divisions of each shape can be influenced by another number and the level at which the division is performed. (zoom) ## Adding color Adding color can make things better, or worse. Dropping color randomly, without respect for the level structure of the treemap, creates a mess. We can rescue things by increasing the probability that a given rectangle will be made transparent—this will allow the color of the rectangle below to show through. Additionally, by drawing the layers in increasing order, smaller rectangles are drawn on top of bigger ones, giving a sense of recursive subdivision. The divisions of each shape can be influenced by another number and the level at which the division is performed. (zoom) Because the color is assigned randomly, various instances of the treemap can be made. The maps below have the same proportion of colors and transparency (same as the first image in second row in the figure above) and vary only by the random seed to pick colors. Different instances of 5 level$pi$treemaps. The proportion of transparent, white, yellow, red and blue shapes is 20:1:1:1:1. (zoom) ## Coloring using adjacency graph The color assignments above were random. For each shape the probability of choosing a given color (transparent, white, yellow, red, blue) was the same. Color choice for a shape can also be influenced by the color of neighbouring shapes. To do this, we need to create a graph that captures the adjacency relationship between all the shapes at each level. Below I show the first 4 levels of the$pi$treemap and their adjacency graphs. In each graph, the node corresponds to a shape and an edge between nodes indicates that the shapes share a part of their edge. Shapes that touch only at a corner are not considered adjacent. Different instances of 5 level$pi$treemaps. The proportion of transparent, white, yellow, red and blue shapes is 20:1:1:1:1. (zoom) One way in which the graphs can be used is to attempt to color each layer using at most 4 colors. The 4 color theorem tells us that only 4 unique colors are required to color maps such as these in a way that no two neighbouring shapes have the same color. It turns out that the full algorithm of coloring a map with only 4 colors is complicated, but reasonably simple options exist.. For the maps here, I used the DSATUR (maximum degree of saturation) approach. Different instances of 5 level$pi$treemaps. The proportion of transparent, white, yellow, red and blue shapes is 20:1:1:1:1. (zoom) The DSATUR algorithm works well, but does not guarantee a 4-color solution. It performs no backtracking. If you look carefully, one of the rectangles in the 4th layer (top right quadrant in the graph) required a 5th color (shown black). VIEW ALL # news + thoughts # Optimal experimental design Tue 31-07-2018 Customize the experiment for the setting instead of adjusting the setting to fit a classical design. The presence of constraints in experiments, such as sample size restrictions, awkward blocking or disallowed treatment combinations may make using classical designs very difficult or impossible. Optimal design is a powerful, general purpose alternative for high quality, statistically grounded designs under nonstandard conditions. Nature Methods Points of Significance column: Optimal experimental design. (read) We discuss two types of optimal designs (D-optimal and I-optimal) and show how it can be applied to a scenario with sample size and blocking constraints. Smucker, B., Krzywinski, M. & Altman, N. (2018) Points of significance: Optimal experimental design Nature Methods 15:599–600. ### Background reading Krzywinski, M., Altman, N. (2014) Points of significance: Two factor designs. Nature Methods 11:1187–1188. Krzywinski, M. & Altman, N. (2014) Points of significance: Analysis of variance (ANOVA) and blocking. Nature Methods 11:699–700. Krzywinski, M. & Altman, N. (2014) Points of significance: Designing comparative experiments. Nature Methods 11:597–598. # The Whole Earth Cataloguer Mon 30-07-2018 All the living things. An illustration of the Tree of Life, showing some of the key branches. The tree is drawn as a DNA double helix, with bases colored to encode ribosomal RNA genes from various organisms on the tree. The circle of life. (read, zoom) All living things on earth descended from a single organism called LUCA (last universal common ancestor) and inherited LUCA’s genetic code for basic biological functions, such as translating DNA and creating proteins. Constant genetic mutations shuffled and altered this inheritance and added new genetic material—a process that created the diversity of life we see today. The “tree of life” organizes all organisms based on the extent of shuffling and alteration between them. The full tree has millions of branches and every living organism has its own place at one of the leaves in the tree. The simplified tree shown here depicts all three kingdoms of life: bacteria, archaebacteria and eukaryota. For some organisms a grey bar shows when they first appeared in the tree in millions of years (Ma). The double helix winding around the tree encodes highly conserved ribosomal RNA genes from various organisms. Johnson, H.L. (2018) The Whole Earth Cataloguer, Sactown, Jun/Jul, p. 89 # Why we can't give up this odd way of typing Mon 30-07-2018 All fingers report to home row. An article about keyboard layouts and the history and persistence of QWERTY. My Carpalx keyboard optimization software is mentioned along with my World's Most Difficult Layout: TNWMLC. True typing hell. TNWMLC requires seriously flexible digits. It’s 87% more difficult than using a standard Qwerty keyboard, according to Martin Krzywinski, who created it (Credit: Ben Nelms). (read) McDonald, T. (2018) Why we can't give up this odd way of typing, BBC, 25 May 2018. # Molecular Case Studies Cover Fri 06-07-2018 The theme of the April issue of Molecular Case Studies is precision oncogenomics. We have three papers in the issue based on work done in our Personalized Oncogenomics Program (POG). The covers of Molecular Case Studies typically show microscopy images, with some shown in a more abstract fashion. There's also the occasional Circos plot. I've previously taken a more fine-art approach to cover design, such for those of Nature, Genome Research and Trends in Genetics. I've used microscopy images to create a cover for PNAS—the one that made biology look like astrophysics—and thought that this is kind of material I'd start with for the MCS cover. Cover design for Apr 2018 issue of Molecular Case Studies. (details) # Happy 2018$\tau` Day—Art for everyone

Wed 27-06-2018
You know what day it is. (details)

# Universe Superclusters and Voids

Mon 25-06-2018

A map of the nearby superclusters and voids in the Unvierse.

By "nearby" I mean within 6,000 million light-years.

The Universe — Superclustesr and Voids. The two supergalactic hemispheres showing Abell clusters, superclusters and voids within a distance of 6,000 million light-years from the Milky Way. (details)


text:
CS191 17 04 03
Zhu, Justin

# Reflecting on Speaker Notes

It isn’t all positive, where if you want to get the sense of the vote other by town meetings.

When you have multiple users separating from each other, you really cannot say how people are making the correct bindings, unless the tape s simple. Typesafe world in programming right now. Packets of aggregates have every field’s safety not guaranteed.

The hardware barriers are the things that don’t shape the Moore’s law curve.

# Gale, Shapley 1962

This is a good paper in that it utilizes certain principles of the “algorithm” and “computer” without even using the word “algorithm” or “computer”.

Colleges and marriages have a matching problem challenge that warrants more investigation. This matching problem is seen in colleges and marriages. A set of n applicants assigned m colleges and qi is the quota of the ith college, each applicant ranks the college in order of preference just as each mates rank their anticipated lovr in order of preference.

Ultimately an algorithm allows for stable assignments and a marriage problem to persist such that the ranking of the individuals is preserved across all individuals.

There exists an optimal solution for this problem. Like so, the knowledge of calculus is not presupposed and individuals do not need to know how to count. The way this question is formalized into a mathematical problem is certainly most intriguing.

# Blum, Floyd, Pratt, Rivest, Tarjan 1972

This paper is pretty interesting in discussing complexity of recursive functions. We have Rabin’s axiomatic approach, which is determining whether a legal measure of functional complexity. This definition is the number of steps needed to compute a function and the amount of machine tape needed for a computation.

This is illustrative of Turing’s Turing machine, which is pretty influential with the tape design. The decision for a machine independent complexity theory simply means that the computations have different types of computations.

For example, to compute the function within a class of multitape machines, the class with a base 2 input-output will compute certain functions for measuring complexity, independent of the class of machines.

The class of speed-up theorem illustrates the 0-1 valued recursive functions that computes the number of steps in a compression machine.

The compression theorem is the inverse of the opposite of the speed-up theorem. We are corresponding to the machine such that another computation is faster.

The number of steps needed to computer f wedges between the bounds $\Phi$ and $\Phi _i^7$

# Knuth 1976

Knuth’s 1976 paper discusses the fundamental classical question of $O(f(n))$ to stand for any function whose magnitude is bounded above by a constant times $f(n)$ for extremely large n. Classical literature often dictates that these writings of $O$ notation serves some useful purpose, but it is hard to say what purpose this is often used for.

The beginning of big O notation is formalized in the following way:

$O(f(n))$ denotes the set of all $g(n)$ such that there exist positive constants C and $n_0$ with $|g(n)|\leq C f(n)$ for all $n\geq n_0$. Meanwhile, $\Omega(f(n))$ denotes the set of all $g(n)$ such that there exist positive constants $C$ and $n_0$ with $g(n) \geq C f(n)$ for all $n \geq n_0$. This is very consistent with the big O notation learned in CS124: Data Structures and Algorithms.


text:
# Differences

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

 phy142kk:lectures:fr1 [2015/05/11 10:03]kkumar phy142kk:lectures:fr1 [2015/05/11 10:14] (current)kkumar [Diffraction grating] Both sides previous revision Previous revision 2015/05/11 10:14 kkumar [Diffraction grating] 2015/05/11 10:10 kkumar [Intensity pattern for a single slit] 2015/05/11 10:08 kkumar [Anti reflective coating] 2015/05/11 10:07 kkumar [Air wedge and Other Effects] 2015/05/11 10:06 kkumar 2015/05/11 10:03 kkumar 2015/05/11 10:02 kkumar 2015/05/11 06:40 kkumar [Lecture 39: Review Lecture II] 2015/05/06 11:31 kkumar [Lens equation] 2015/05/06 10:07 kkumar [Refractive index] 2015/05/06 10:03 kkumar [Mirror equation] 2015/05/06 09:16 kkumar 2015/05/06 09:09 kkumar [Mirror equation] 2015/05/06 09:04 kkumar [Mirror equation] 2015/05/06 09:01 kkumar [Phasor approach to LRC series circuit] 2015/05/06 08:56 kkumar [Phasor for an inductor] 2015/05/06 08:55 kkumar [LRC Circuit Analysis] 2015/05/06 08:49 kkumar [Analysis of the LC circuit] 2015/05/06 08:48 kkumar [LR circuits] 2015/05/06 05:49 kkumar [Reflection] 2015/05/06 05:41 kkumar [Transformers] 2015/05/06 05:39 kkumar [emf produced by a generator] 2015/05/06 05:37 kkumar [Motional emf] 2015/05/06 05:35 kkumar [Faraday's Law of Induction] 2015/05/06 05:33 kkumar [Faraday's Law of Induction] 2015/05/06 05:24 kkumar 2015/05/06 05:21 kkumar 2014/12/19 11:02 mdawber 2014/12/19 10:15 external edit Next revision Previous revision 2015/05/11 10:14 kkumar [Diffraction grating] 2015/05/11 10:10 kkumar [Intensity pattern for a single slit] 2015/05/11 10:08 kkumar [Anti reflective coating] 2015/05/11 10:07 kkumar [Air wedge and Other Effects] 2015/05/11 10:06 kkumar 2015/05/11 10:03 kkumar 2015/05/11 10:02 kkumar 2015/05/11 06:40 kkumar [Lecture 39: Review Lecture II] 2015/05/06 11:31 kkumar [Lens equation] 2015/05/06 10:07 kkumar [Refractive index] 2015/05/06 10:03 kkumar [Mirror equation] 2015/05/06 09:16 kkumar 2015/05/06 09:09 kkumar [Mirror equation] 2015/05/06 09:04 kkumar [Mirror equation] 2015/05/06 09:01 kkumar [Phasor approach to LRC series circuit] 2015/05/06 08:56 kkumar [Phasor for an inductor] 2015/05/06 08:55 kkumar [LRC Circuit Analysis] 2015/05/06 08:49 kkumar [Analysis of the LC circuit] 2015/05/06 08:48 kkumar [LR circuits] 2015/05/06 05:49 kkumar [Reflection] 2015/05/06 05:41 kkumar [Transformers] 2015/05/06 05:39 kkumar [emf produced by a generator] 2015/05/06 05:37 kkumar [Motional emf] 2015/05/06 05:35 kkumar [Faraday's Law of Induction] 2015/05/06 05:33 kkumar [Faraday's Law of Induction] 2015/05/06 05:24 kkumar 2015/05/06 05:21 kkumar 2014/12/19 11:02 mdawber 2014/12/19 10:15 external edit Line 45: Line 45: {{reflectionphasechange.png}} {{reflectionphasechange.png}} + ===== Air wedge and Other Effects ===== + + + {{airwedge.png}} + + For a single wavelength dark stripes will occur whenever  + + $2t=m\lambda$<html>      (m=0,1,2,..) + + and bright stripes will occur whenever  + + $2t=(m+\frac{1}{2})\lambda$<html>      (m=0,1,2,..) + + ===== Anti reflective coating ===== ===== Anti reflective coating ===== + + Ideally we would use a coating that produced an equal amount of reflection at both interfaces, but there is no suitable material with the required refractive index,  $n=1.26$,  so we use magnesium flouride MgF<sub>2. {{antreflectivecoating.png}} {{antreflectivecoating.png}} - As the two reflections both occur from more optically dense media they both experience a  $\frac{\lambda}{2}$ phase change on reflection. To have the light be out of phase we need to light that goes through the coating to have advanced by $\frac{\lambda}{2}$ for destructive interference to occur. Critically, when destructive interference occurs the light is not lost, but is instead transmitted. As the wavelength of light in a medium is given by $\lambda=\frac{\lambda_{0}}{n}$ where $n$ is the refractive index of the medium and $\lambda_{0}$ is the wavelength of the light in free space, the thickness of the coating should be $\frac{\lambda}{4n_{2}}$. + As the two reflections both occur from more optically dense media they both experience a phase change of $\pi$ on reflection which corresponds to advancing the wave by $\frac{\lambda}{2}$ . - In practice the light incident will not all be the same wavelength, so the thickness of the coating is typically chosen to work optimally in the center of the visible band (~550nm). + To have the light be out of phase we need to light that goes through the coating to have advanced by $\frac{\lambda}{2}$ for destructive interference to occur. - ===== Air wedge ===== + Critically, when destructive interference occurs the light is not lost, but is instead transmitted.  - {{airwedge.png}} + As the wavelength of light in a medium is given by $\lambda=\frac{\lambda_{0}}{n}$ where $n$ is the refractive index of the medium and $\lambda_{0}$ is the wavelength of the light in free space, the thickness of the coating should be $\frac{\lambda}{4n_{2}}$. - For a single wavelength dark rings will occur whenever  - $2t=m\lambda$<html>      (m=0,1,2,..) + ===== Intensity for double slit interference ===== - and bright rings will occur whenever  + As we now have the intensity in terms of the phase difference $\delta$ - $2t=(m+\frac{1}{2})\lambda$<html>      (m=0,1,2,..) + $I_{\theta}=I_{0}\cos^{2}\frac{\delta}{2}$ - For white light different colors will experience constructive interference at different thicknesses, leading to the colorful lines we see when an air gap is under normal light. + we should return to our diagram to find the intensity in terms of $d$ and $\theta$ + {{twoslitphase.png}} + + We can see that + + $\frac{\delta\lambda}{2\pi}=d \sin \theta$ + + giving + + $\delta=\frac{2\pi}{\lambda}d\sin\theta$ + + and the intensity is + + $I_{\theta}=I_{0}\cos^{2}(\frac{\pi d \sin \theta}{\lambda})$ + + {{figure_34_14.jpg?800}} ===== Intensity pattern for a single slit ===== ===== Intensity pattern for a single slit ===== Line 105: Line 135: but that the larger the number of slits from which diffraction occurs the sharper the maxima will be. but that the larger the number of slits from which diffraction occurs the sharper the maxima will be. + + ===== n slits ===== + + {{nslitgrating.png}} + + n=2 $\frac{I_{\theta}}{I_{0}}=\frac{(2+2\cos\delta)}{4}$ + + n=3 $\frac{I_{\theta}}{I_{0}}=\frac{3+4\cos\delta+2\cos 2\delta}{9}$ + + n=4 $\frac{I_{\theta}}{I_{0}}=\frac{4+6\cos\delta+4\cos 2\delta+2\cos 3\delta}{16}$ + + For any $n$ + + $\frac{I_{\theta}}{I_{0}}=\frac{n+\sum\limits_{k=1}^{n-1}2(n-k)\cos(k\delta)}{n^{2}}$ ===== Polarizers ===== ===== Polarizers =====


text:
# Records: [Sega Tetris (1988)]

Thread in 'Competition' started by jujube, 16 Jun 2008.

1. ### Edoa.k.a. FSY

Congratulations nightmareci! From the looks of things, even after 999 lines you still could have carried on quite easily! You actually inspired me to give this another quick go today - things were looking real good until I topped out at about 550k

I stuck some of the run up on youtube (from level 15, up to near where I died), but it's a full 11 minutes, so it might be a bit boring for people not interested in SEGA Tetris: http://www.youtube.com/watch?v=O8I9dmolCeI

2. ### Kitaru

Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.

3. ### Edoa.k.a. FSY

Impressive Kitaru, keep it up!! I don't suppose you were recording were you? I'd be interested to see your playstyle in action.

4. ### Kitaru

I have an .inp I think, yeah. Maybe I'll link it, maybe I'll record. My play style is bad, probably, haha.

5. ### Edoa.k.a. FSY

It can't be that bad if you can survive to 500k!

6. ### nightmareci

Code:
nightmareci------999999       662       2010-10-03
Recorded: Part 1 and part 2.

EDIT: I copy-pasted my code tag there from my last post, and forgot to edit the date. Fixed now.

Last edited: 10 Oct 2010
7. ### cyberguile

I didn't know there was a sega tetris leaderboard
Remember playing it on my megadrive on a pirate 180 in 1 HK cartidge when I was, like, 14
I will give it a go this evening but... the randomizer is soooooo cruel in this game lol

8. ### Zaphod77Resident Misinformer

The game actually generates a 1000 piece looping sequence each time you start a game.

The pattern doesn't continue where you leave off, instead a new pattern is generated with a new seed.

However this sequence of seeds doesn't change either. So the second game has it's own "poweron pattern" the third game has it's own "poweron pattern", etc.

The number of possible seeds is not yet known. IF someone versed in assembly can reverse engineer the generator, then the size of the seed can be calculated, and the number of possible seeds worked out.

Notably, this has a few implications

1) to max out the line counter you must survive two loops of the pattern.
2) if you get a bravo on piece 1000, you can play forever.
3) even though it has a true memoryless randomizer, some, if not all, possible games of Sega Tetris may be foreverable. There may be 1000 piece sequences the game gives out that can't be survived indefinitely.
4) The poweron pattern ends with a I, and therefore may potentially allow a tetris bravo on the last piece.

9. ### Kitaru

1x Bravo (L triple) well after the score max-out. The max-out was in... 776 lines? 77x for sure.

10. ### nightmareci

It's not a new record for me, but it is a maxout, all in one video, since YouTube allows that now.

I've developed some new techniques to survive more consistently, but I've gotten somewhat rusty at Sega Tetris, so I sometimes make placements that would work in TGM.

Maybe I'll try to outdo my old record, but I've been mostly focused on TGM lately.

Muf, Qlex, CylinderKnot and 2 others like this.
11. ### eskatre

In anticipation for the newly announced M2 port...

Played on shmupmame 4.2 using "set 4" (tetris.zip) on hardest, no bravos

mycophobia likes this.


text:
Also available:

## make latex() generate y'(x) for diff(y(x),x) ?...

I know the latex() command in Maple have many issues and I have no hope of what I will ask having a solution, but thought to ask any way.

Is there a way to make maple generate the latex for all the derivatives to use ' instead of d/dx ?

for example, given this

ode:=diff(y(x),x)=x;
latex(ode,output=string);

The Latex generated (which is correct) is

{\frac {\rm d}{{\rm d}x}}y \left( x \right) =x

but sometines I find it more readable if the latex was

y'(x)=x

which is more common in textbooks and other places. The problem also is that I am using worksheet so can't use  y'(x) as input.

But even switching to document mode, and writing it 2D math as input, the Latex output still does not match the input

So if there is a solution to this, would it require changing the latex() command itself? or can it be done at user level?

I'd like all orders of derivatives anywhere in the equation to come out as y'' etc.. so diff(y(x),x\$3) should generate the latex y'''(x) and so on.

Is there a trick to do this?

Maple 2017.2

 Page 1 of 1


text:
# What is the intuition behind the Lorentz factor from Special Relativity

Time Dilation = $1/\sqrt{ 1-v^2/c^2}$ but why? How do you get to that conclusion? I know you use Pythagoras'theorem and my current understand goes like this:

$$vt^2+ct^2=cT^2$$

then you take the square root of $Ct^2$ and from there I think you divide by $c$ to get the time dilation but I'm not sure. And if this is correct what steps do you take to get to the formula used now

• A quick search on Google returns plenty of results of the derivation, for example: archive.org/details/… – turnip Aug 17 '14 at 10:39
• @PPG I edited the question - perhaps it is more workable now. – Danu Aug 17 '14 at 10:41

To me personally, the most intuitive way of understanding SRT is to always keep in mind that, in SRT, the interval $$ds^2=-c^2dt^2+dx^2=-c^2d\tau^2$$ has to be invariant. From this simple formula, everything seems to flow naturally. In particular, it is easy to see the form of the Lorentz factor arise from here, by using $\frac{dx}{dt}=v\to dx=vdt$. Using this substitution gives us

$$c^2d\tau^2=dt^2(c^2-v^2)\to d\tau^2=dt^2\left(1-\frac{v^2}{c^2}\right)\to d\tau=(\pm)dt\sqrt{1-\frac{v^2}{c^2}}=(\pm)\frac{dt}{\gamma}$$ this is the time dilation formula. The length contraction may be similarly derived. If you like this, you may be interested in this old question of mine (although you must take care not to get confused about the notational differences).

Rather than rehash the equations which have been referenced already, I wanted to first cover the Michelson-Morley experiment. Michelson, Morley and even Lorentz were actually able to do a considerable amount of work on the prediction of the expected existence of the aether wind. The foundations of the underlying equations where strong by this point.

The shock of the discovery there was no aether wind was truly enormous. However, the machinery to explain the situation, the Fitzgerald-Lorentz length contraction hypothesis, quickly explained what was happening, however, without a theory like relativity there really was no foundation for how to understand why this was the case.

From a pure mathematical standpoint, the trick is to shift from circular angles to hyperbolic angles with the understanding that Lorentz contraction is understood in terms of hyperbolic functions.

Hyperbolic relationships are common in physics and occur in several places, from relativity to Heisenberg uncertainty.

For the math I would refer to the links and previous posts, but this should hopefully help your intuition on this a little.

• nice introduction to the conceptual history of SR, i would like to add that the turning point was the understanding and formulation of E/M equations (based on newer technology) which posited the constancy of light propagation. This went into conflict with Galilean/Newtonians notions of velocity and aether was posited as the medium through which light wave is an oscilation of. Finally the MM experiment showed there is no movement of this aether. Then unification of Mechanics and EM had to be achieved somehow, and SR was one way achieving this unification at the space-time level. – Nikos M. Aug 17 '14 at 15:27

This is how you derive the equation for time dilation.

The metric used in special relativity is the Minkowski metric:

$$ds^2 = -c^2dt^2 + dx^2 + dy^2 + dz^2$$

and the basic principle of special relativity is the the line element $ds$ is an invariant, that is all observers in all inertial frames will measure it to have the same value.

Suppose we are using the coordinates $(t, x, y, z)$ and we observe an object moving at velocity $v$ in the $x$ direction (so $dy = dz = 0)$, then:

$$ds^2 = -c^2dt^2 + dx^2 \tag{1}$$

But we expect the position of the object in our coordinates, $x$, to be given by:

$$x = vt + x_0$$

and therefore:

$$dx = vdt$$

and if we substitute this in equation (1) we get:

$$ds^2 = -c^2dt^2 + v^2dt^2 \tag{2}$$

Now shift to the frame of the moving object $(t', x', y', z')$. In these coordinates the objetc is stationary so $dx' = dy' = dz' = 0$ so:

$$ds'^2 = -c^2dt'^2 \tag{3}$$

We started out by saying that all observers will agree on the value of the line element and that means $ds = ds'$, so equating equations (2) and (3) we get:

$$c^2dt'^2 = c^2dt^2 - v^2dt^2$$

And dividing both sides by $c^2$ and taking the square root:

\begin{align} dt' &= dt \sqrt{1 - \frac{v^2}{c^2}} \\ &= \frac{dt}{\gamma} \tag{4} \end{align}

And this is the basis of the time dilation. If we want to find the time $t'$ corresponding to a time $t$ then we simply integrate equation (4), and because $\gamma$ is a constant this integrates to:

$$t' = \int_0^t \frac{dt}{\gamma} = \frac{t}{\gamma}$$

which is the equation that we all know and love.

This may seem like a long winded way of deriving the result, but note that this method is applicable to situations where the velocity is not constant. In that case the relationship between $dx$ and $dt$ is not linear, and the integral will be harder, however the working is exactly the same.

• Hah, I just wrote up my answer based on your old one - only to get another one of yours :D – Danu Aug 17 '14 at 11:03
• @Danu: damn your eyes Danu! :-) I saw a flag come up to say there was an answer while I was typing this, but I didn't bother refreshing the page to see what the answer was. Oh well, I'll leave this here for a bit as I've been more explicit about the working. Site members: please upvote Danu's answer (or both :-) as he did get in first. – John Rennie Aug 17 '14 at 11:05
• On my list of things to do is write up a blog style Q/A on the twin paradox starting with this approach to time dilation and showing how acceleration affects the calculation. – John Rennie Aug 17 '14 at 11:06
• Yes, yes, yes! Fits nicely within the context of my meta proposal - even if you want to do it independently. – Danu Aug 17 '14 at 11:17
• Why is it -c^2dt^2? why not just c^2dt^2? I'm 17 and don't even do physics at school so forgive me for higher-than-expected ignorance. Also how do I make my equations the way everyone else does it? When I write for example c^2 I have the '^' there while everyone else has a little 2 in the top right – Ray Kay Aug 18 '14 at 0:50

i would say the intuition is the simple observation (by Einstein, Lorentz, Poincare and others) of these 2 things:

1. Velocity of light ($c$) is $c$-onstant accross interial frames (extrapolated result from Maxwell-Lorentz equations)

2. The velocity of light ($c$) is an upper limit on every other velocity a material body or signal can achieve (in effect $c$ assumes a role similar to infinity in mathematics)

These two derive the relativistic velocity addition formula and the Lorentz transformations which replace the Galilean transformations.

Then one, based on the Lorentz transformations, can define a Minkowski spacetime which geometrically is characterised by having the infinitesimal interval:

$$ds^2 = -(cdt)^2 + dx^2 + dy^2 + dz^2$$

an invariant of the geometry.


text:
Open Access Publications from the University of California

## K\"ahler Geometry of non-Compact Toric Manifolds

Abstract

Toric manifolds and toric varieties have played an important and particularly illuminating role in algebraic, symplectic, and K\"ahler geometry going back at least to the 1970's. The high degree of symmetry in many cases allows one to reduce the complexity of a given geometric question, giving the impression that we can really see'' the structure. A notable example of this in the K\"ahler setting is Donaldson's classic paper [27].

Until relatively recently, this has been mostly confined to the setting of compact manifolds (complete varieties). Both the algebraic and the symplectic perspectives have come to be fairly well understood individually in the non-compact case, but there has been little application of the intersection of the two theories, which naturally comprises toric K\"ahler geometry. The notable exception to this rule is the case of toric K\"ahler cones [56, 55, 39, 17, 16]. These non-compact manifolds inherit a great deal of structure from their compact \emph{link}, which are interesting spaces in their own right. However, these manifolds are (typically) highly singular at precisely one point.

In this dissertation, we describe a procedure for the study of K\"ahler geometry on smooth non-compact toric manifolds. This involves tying together the algebraic and symplectic perspectives. We study a class of toric manifolds and show that here we can apply a non-compact version of the classical Delzant classification together with its application to K\"ahler geometry [4, 41, 24, 42]. We apply this to non-compact shrinking K\"ahler-Ricci solitons, where we propose a useful class of complete K\"ahler metrics, and ultimately prove a general uniqueness theorem for shrinking K\"ahler-Ricci solitons on non-compact toric manifolds.


text:
Control design for a pendulum on a cart

In this example we will consider control design for the basic inverted pendulum on a cart. This system has two equilibria, one where the pendulum is hanging straight down, and one where it's balancing straight up. The upper one is unstable, making it slightly more interesting to design a controller for (even if the lower equilibrium is highly relevant, it's a good model for an overhead crane moving goods).

System model

In this tutorial, we assume that we have the nonlinear dynamics of the system encodeed as a julia function ẋ = cartpole(x, u), and linearize this to get a statespace system

\begin{aligned} ẋ &= Ax + Bu\\ y &= Cx \end{aligned}

We make use of ForwardDiff.jl for the linearization. We start by defining the dynamics function

using ControlSystems, RobustAndOptimalControl, ForwardDiff, LinearAlgebra, Plots

function cartpole(x, u)
mc, mp, l, g = 1.0, 0.2, 0.5, 9.81

q  = x[1:2]
qd = x[3:4]

s = sin(q[2])
c = cos(q[2])

H = [mc+mp mp*l*c; mp*l*c mp*l^2]
C = [0.1 -mp*qd[2]*l*s; 0 0]
G = [0, mp * g * l * s]
B = [1, 0]

qdd = -H \ (C * qd + G - B * u[1])
return [qd; qdd]
end

nu = 1    # number of control inputs
nx = 4    # number of states
ny = 2    # number of outputs (here we assume that the cart position and the pendulum angle are measurable)

Linearization

The next step is to choose an operating point around which to linearize and to calculate the Jacobians $A$ and $B$:

x0 = [0, π, 0, 0]
u0 = [0]

Ac = ForwardDiff.jacobian(x->cartpole(x, u0), x0)
Bc = ForwardDiff.jacobian(u->cartpole(x0, u), u0)
Cc = [1 0 0 0; 0 1 0 0]
Λ = Diagonal([0.4, deg2rad(25)]) # Maximum output ranges
Cc = Λ\Cc # This normalizes expected outputs to be ∈ [-1, 1], a good practice for MIMO systems

we package everything into a StateSpace object and visualize its poles and zeros:

sys = ss(Ac, Bc, Cc, 0)
ControlSystems.StateSpace{ControlSystems.Continuous, Float64}
A =
0.0   0.0                  1.0  0.0
0.0   0.0                  0.0  1.0
0.0   1.9620000000000002  -0.1  0.0
0.0  23.544               -0.2  0.0
B =
0.0
0.0
1.0
2.0
C =
2.5  0.0                0.0  0.0
0.0  2.291831180523293  0.0  0.0
D =
0.0
0.0

Continuous-time state-space model
pzmap(sys)

Control design

We will design a number of different controllers. We will start with a basic PID controller. Since the PID controller in its standard form really only handles SISO systems, we will also design a state-feedback controller with an observer to estimate the full state vector $x$ based on the two measurements $y$. Lastly, we will attempt to "robustify" the state-feedback controller using the glover_mcfarlane procedure.

Since the system has an unstable pole $p \approx 4.85$rad/s, there wil be fundamental limitations on the performance of the closed loop system. A common rule-of-thumb (see, e.g., Åström and Murray) is that a single RHP pole $p$ puts a lower limit on the gain crossover frequency $\omega_{gc} > 2p$, something to take into consideration when tuning our controllers.

PID controller

Since the PID controller only accepts a single measurement, we choose the measurement of the pendulum angle for feedback. While doing so, we notice that the number of states in the model can be reduced by the function sminreal

P = sminreal(sys[2,1]) # Position state goes away, not observable
ControlSystems.StateSpace{ControlSystems.Continuous, Float64}
A =
0.0                  0.0  1.0
1.9620000000000002  -0.1  0.0
23.544               -0.2  0.0
B =
0.0
1.0
2.0
C =
2.291831180523293  0.0  0.0
D =
0.0

Continuous-time state-space model

this indicates that the state corresponding to the position of the cart is not observable from the measurement of the pendulum angle. This is slightly worrisome, but we nevertheless proceed to design a controller. By using a single measurement only, we have also introduced a zero in the system

pzmap(P)

A PID controller can be constructed using the function pid. We start our tuning by a simple P controller

C = pid(kp=1, ki=0, kd=0, series=true)
ControlSystems.TransferFunction{ControlSystems.Continuous, ControlSystems.SisoRational{Float64}}
NaNs + NaN
----------
1.0

Continuous-time transfer function model

We will attempt to perform loop shaping using the PID controller, and plot the stability margins in a Bode plot using the function marginplot

w = exp10.(LinRange(-2.5, 3, 500))
function pid_marginplot(C)
f1 = marginplot(P*C, w)
vline!([2*4.85], sp=1, lab="Fundamental limitation", l=(:dash, :black))
ylims!((1e-3, 1e2), sp=1)
f2 = nyquistplot(P*C)
plot(f1, f2)
end
pid_marginplot(C)

We notice that the gain of the loop-transfer function $L = PC$ is much too low, and increase it, we also notice that the Nyquist plot fails to encircle to critical point, which it has to do once since we have one unstable pole. We will solve this in the end by adding integral action, but proceed for now to shape other parts of the loop. We start by lifting the Bode curve by increasing the gain:

C = pid(kp=20, ki=0, kd=0, series=true)
pid_marginplot(C)

we are now getting close to the rule-of-thumb for $\omega_{gc}$, but have a low loop gain at low frequencies. Remember, to get good disturbance rejection, we typically want a high loop gain at low frequencies. We also have an extremely small phase margin at 0.66 degrees. To fix the phase margin, we add some derivative gain. While adding derivative gain, it's also a good idea to add noise filtering (with a pure derivative term, the PID controller is not proper and can not be realized as a statespace system)

C = pid(kp=20, ki=0, kd=0.2, series=true) * tf(1, [0.01, 1])
pid_marginplot(C)

The derivative term lifted the phase at $\omega_{gc}$ and we now have very nice phase margins. We also got a slight increase in $\omega_{gc}$ while at it.

The closed-loop system will still be unstable since the Nyquist curve fails to encircle the point -1, something we can check by calling

isstable(feedback(P*C))

We make the Nyquist curve wrap around the -1 point by adding integral gain:

C = pid(kp=20, ki=0.8, kd=0.2, series=true) * tf(1, [0.01, 1])
pid_marginplot(C)

Now, the Nyquist curve looks fine and the system is stable

isstable(minreal(feedback(P*C)))
true

If we simulate a disturbance acting on this system (feedback(P, C) is the transfer function from load disturbance to output)

plot(step(feedback(P,C), 8), ylab="ϕ")

we see that we have a reasonable disturbance response.

To verify robustness properties, we plot the gang-of-four sensitivity functions:

f1 = gangoffourplot(P,C,w)
f2 = nyquistplot(P*C, Ms_circles=[1.4], Mt_circles=[1.5], ylims=(-2, 2), xlims=(-4,1))
plot(f1, f2, size=(1000,800))

This all looks nice and we appear to have reasonable robustness margins, the Nyquist curve stays outside the $M_S = 1.4$ circle and the $M_T = 1.5$ circle.

However, there is a dragon lurking behind these plots. Remember the state corresponding the the cart position that was removed above? What has happened to this state? To investigate this, we form an ExtendedStateSpace model where we have both cart position and pendulum angle as controlled outputs, while keeping only the pendulum angle as measured output:

Pe = ExtendedStateSpace(sys, C2 = sys.C[2:2, :]) # Indicate that we can only measure the pendulum angle
Gecl = feedback(Pe, ss(C)) |> minreal
plot(step(Gecl, 8), ylab=["Cart pos" "ϕ"])

We see that the cart position drifts away without ever thinking about stopping. Indeed, the PID controller is unaware of this and can not really do anything about it. We could attempt to design a second control loop that would close the loop around the cart position, but we would have to carefully manage the interactions between the two loops. Instead, we move on to a state-feedback design, a methodology that makes handling multiple outputs much more straightforward.

Pole placement and observer design

The design of a state-feedback controller typically involves two steps, designing the feedback gain and designing an observer. We will arrive at the feedback gain through pole placement, but will design the observer as a Kalman filter, i.e., by solving a Riccati equation rather than using Ackermann's formula.

When performing pole placement, there are a number of design guidlines that help you arrive at a robust design. One of these are that past process poles should be matched with an equally fast closed-loop pole. We can get an overview of the open-loop poles with dampreport

dampreport(sys)
|        Pole        |   Damping     |   Frequency   |   Frequency   | Time Constant |
|                    |    Ratio      |   (rad/sec)   |     (Hz)      |     (sec)     |
+--------------------+---------------+---------------+---------------+---------------+
| +0                 |  -1           |  0            |  0            |  -Inf         |
| -0.0833            |  1            |  0.0833       |  0.0133       |  12           |
| +4.84              |  -1           |  4.84         |  0.771        |  -0.206       |
| -4.86              |  1            |  4.86         |  0.774        |  0.206        |

we see that we have two poles at roughly $\pm 4.85$rad/s, and almost two integrators. We thus keep the fast pole, and place the unstable pole at the same location (same bandwidth but stable instead of unstable). We also try to move the integrator poles to -5 to make the system nice and fast.

desired_poles = [-4.85, -4.85, -5, -5]
L = place(sys, desired_poles, :c)
1×4 Matrix{Float64}:
-29.9726  99.5196  -24.4489  22.0244

For the observer, we make use of the function kalman. We choose the covariance matrices R1, R2 that determine the amount of noise acting on the system and on the measurements respectively. We assume that there are two noise components, both entering as forces. One disturbance force acts on the cart and the other on the pendulum. We indicate this using the matrix $B_w$.

Bw = [0 0; 0 0; 1 0; 0 1]
R1 = Bw*I(2)*Bw'
R2 = 0.0001I(ny)
K = kalman(sys, R1, R2)
4×2 Matrix{Float64}:
8.90448     -0.0161568
-0.0176244    9.83322
99.1125       0.481841
-1.31513    110.801

With our feedback gain L and the Kalman gain K, we form the controller using observer_controller

controller = observer_controller(sys, L, K)
@assert isstable(controller)
@assert isstable(feedback(sys * controller))

We may have a look at the Nyquist plot and the gang-of-four to assess robustness margins. In this case we look at the loop transfer function at the input simply because this function is SISO while the standard output-loop transfer is MIMO. This will allow us to asses robustness w.r.t. input perturbations only

nyquistplot(controller*sys, w, Ms_circles=[2.7], Mt_circles=[3], xlims=(-2, 2), ylims=(-1, 3))

The Nyquist plot shows a rather weak robustness margin, with a peak in the input sensitivity of about

2.67

and a peak in the complementary sensitivity function of around

3.02

These can be verified by calling hinfnorm2

hinfnorm2(input_comp_sensitivity(sys, controller))
(3.021191116182818, 6.672744975862733)
Hover information

If you plot with the Plotly backend, activated by calling plotly() if you have Plotly.jl installed, you can hover the mouse over the Nyquist curve and the gain circles to see frequency information etc. This is not possible when using the default GR backend, used in this documentation.

Also the gang-of-four indicate rather poor margins:

gangoffourplot(sys, controller, w, xlabel="", sigma=false, titlefont=8)


text:
# ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.EXCLUSIVE Keygen-AiR Serial Key

ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR Serial Key

(126 items)
AiR Reverb VST For Artistic ExpressionMozilla Firefox OR AOL Yahoo MSN Explorer.
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR.
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR Serial Key.
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR Incl Key.
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR Update.
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR.rar
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR.
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR.exe
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR.cfw
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR.ASP
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR.DLL
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR.txt

(126 items)
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR.
AiR Reverb VST For Artistic ExpressionMozilla Firefox OR AOL Yahoo MSN Explorer.
ArtsAcoustic.Reverb.VST.v1.2.1

Mar 8, 2018
3 weeks ago
Jupiter 8 VSTi Plugin.
5 days ago
ArtsAcoustic.Reverb.VST.v1.2.1.1.Incl.Keygen-AiR Serial.
Apr 29, 2018

A:

if you are going to update the version of the plugin than you need to get the new serial number, for that you will go to the same plugin folder where the plugin is installed, right click it and then click properties. From the properties page you will see a serials tab, there you will find the serial number and the key.

Q:

Existence of a function which is $1$ on an open set in $\mathbb{R}$, $0$ on $\mathbb{Q}$, and linear on $\mathbb{R} \setminus \mathbb{Q}$.

Does there exist a function $f : \mathbb{R} \to \mathbb{R}$ which is $1$ on an open set in $\mathbb{R}$, $0$ on $\mathbb{Q}$, and linear on $\mathbb{R} \setminus \mathbb{Q}$?
Well, I’ve managed to show that there is no such function for $m \in \mathbb{N}$, so I’ve thinked that maybe there are some function which are of this type for $m \in \mathbb{R} \setminus \mathbb{N}$ but I don’t know how to go ahead with that.
Any kind of help would be appreciated. Thanks.

A:

The answer is no. Any function $f$ which is $1$ on an open set and vanishes on a dense subset must be zero. This is proved in the following way.
Suppose that $g$ is defined on an open interval $(a,b)$ and vanishes on a dense subset of $(a,b)$. If $c$ is a real number in the interval \$(a
3da54e8ca3

This site uses Akismet to reduce spam. Learn how your comment data is processed.


text:
# Show that if $(L_1;≤_1)$ and $(L_2;≤_2)$ are both modular lattices then so is $(L_1 \times L_2;≤)$ [duplicate]

Possible Duplicate:
Cross Product of Partial Orders

Suppose that $(L_1;≤_1)$ and $(L_2;≤_2)$ are partially ordered sets. We define a partial order $≤$ on the set $L_1 \times L_2$ in the most obvious way - we say $(a,b)≤(c,d)$ if and only if $a≤_1 c$ and $b≤_2 d$.

a) Show that if $(L_1;≤_1)$ and $(L_2;≤_2)$ are both lattices, then so is $(L_1 \times L_2;≤)$.

b) Show that if $(L_1;≤_1)$ and $(L_2;≤_2)$ are both modular lattices, then so is $(L_1 \times L_2;≤)$.

c) Show that if $(L_1;≤_1)$ and $(L_2;≤_2)$ are both distributive lattices, then so is $(L_1 \times L_2;≤)$.

d) Show that if $(L_1;≤_1)$ and $(L_2;≤_2)$ are both Boolean algebras, then so is $(L_1 \times L_2;≤)$.

I am having trouble solving this problem. Any help would be appreciated.

-

## marked as duplicate by Henning Makholm, BenjaLim, tomasz, Thomas, NorbertOct 13 '12 at 17:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Well, show us what you did on (a) and where you got stuck. For example, what is the definition of "lattice". –  GEdgar Oct 11 '12 at 21:14

## 1 Answer

I've been trying to attempt this solution. Here is where I get stuck:

c) $L_1$ and $L_2$ are modular, so

$$L_1: a_1 < a_3 \rightarrow a_1 \vee (a_2 \wedge a_3) = (a_1 \vee a_2) \wedge {a_3}$$

$$L_2: b_1 < b_3 \rightarrow b_1 \vee (b_2 \wedge b_3) = (b_1 \vee b_2) \wedge {b_3}$$

$$L_1\times L_2: (a_1,b_1) < (a_3,b_3) \rightarrow (a_1,b_1) \vee ((a_2,b_2) \wedge (a_3,b_3)) = ((a_1,b_1) \vee (a_2,b_2)) \wedge (a_3,b_3)$$

For $L_1\times L_2$ we have $$(a_1,b_1) < (a_3,b_3) = a_1 < a_3 \text{ and } b_1 < b_3$$

I'm not too sure how to use all this information to prove that $L_1\times L_2$ is a modular lattice. Any guidance would be greatly appreciated.

-


text:
# How to test an EEG?

Apologies out of the gate here as I'm a CS person with not a huge amount of experience in electronics, so this might be a pretty basic question. I've built basic EEGs before, basically electrodes together with a series of active filters.

My approach in the past has always been to play with my filters until I don't see a peak at 60Hz, and I don't see huge swings when someone moves their eyes. Once that's done there's usually some kind of wave that gets spit out, but I've never really been convinced that I was seeing a real signal, and not just picking up on some other random noise, which is extremely likely.

I'm now a bit older and more foolish and I wanted to take a more intentional stab at this, but I was wondering if there's any reasonable way of testing this. My naive approach was going to be attempting to generate a signal in the nV realm as input, then trying to re-create it after processing. There are two main reasons why I think this doesn't make sense:

1. Electrodes/Skin conduct introduce noise that I can't model this way
2. I'm very unclear on exactly why an EEG works. It feels very strange to me that you'd get actual signal by strapping electrodes to your head

So how exactly do I test an EEG, and have confidence that an EEG I create is working?

• – Roger Rowland Mar 1 '17 at 6:35


text:
# mathtools brackets larger than \Bigg

I'd like to use the syntax of the mathtools package to generate brackets larger than \Bigg.

One can create larger brackets than \Bigg of specified size using

About big parenthesis larger than Bigg

However, that solution doesn't work with the \DeclarePairedDelimiter construct of mathtools.

See the MWE below. I suspect that what's needed is \Vastl, \Vastr, and \Vastm commands.

\documentclass{article}

\usepackage{mathtools}
\makeatletter
\newcommand{\vast}{\bBigg@{4}}
\newcommand{\Vast}{\bBigg@{5}}
\makeatother

\DeclarePairedDelimiter{\parens}()

\begin{document}

$\parens[\Bigg]{\dfrac{\dfrac{y}{x}}{\dfrac{a}{b}}}$

$\Vast({\dfrac{\dfrac{y}{x}}{\dfrac{a}{b}}} \Vast)\qquad \parens[\Vast]{\dfrac{\dfrac{y}{x}}{\dfrac{a}{b}}} % does not work$
\end{document}

Yes, your suspicion is right. Simply define:

\newcommand{\vastl}{\mathopen\vast}
\newcommand{\vastm}{\mathrel\vast}
\newcommand{\vastr}{\mathclose\vast}
\newcommand{\Vastl}{\mathopen\Vast}
\newcommand{\Vastm}{\mathrel\Vast}
\newcommand{\Vastr}{\mathclose\Vast}

and you can use \vast and \Vast with \DeclarePairedDelimiter.

MWE:

\documentclass{article}

\usepackage{mathtools}
\makeatletter
\newcommand{\vast}{\bBigg@{4}}
\newcommand{\Vast}{\bBigg@{5}}
\newcommand{\vastl}{\mathopen\vast}
\newcommand{\vastm}{\mathrel\vast}
\newcommand{\vastr}{\mathclose\vast}
\newcommand{\Vastl}{\mathopen\Vast}
\newcommand{\Vastm}{\mathrel\Vast}
\newcommand{\Vastr}{\mathclose\Vast}
\makeatother

\DeclarePairedDelimiter{\parens}()

\begin{document}

$\parens[\Bigg]{\dfrac{\dfrac{y}{x}}{\dfrac{a}{b}}}$

$\Vast({\dfrac{\dfrac{y}{x}}{\dfrac{a}{b}}} \Vast)\qquad \parens[\Vast]{\dfrac{\dfrac{y}{x}}{\dfrac{a}{b}}} % works now$
\end{document}

Output:

• what's the meaning of the comment % does not work on the last example. your output shows that it does work (and i have just reproduced that result). Aug 19 '15 at 13:22
• that's just a hold over from my original
– JPi
Aug 19 '15 at 13:29


text:
# How to use Monte Carlo simulation for reliability analysis?

subject area
in short
prerequisite knowledge

Monte Carlo simulation (MCS) is a simple, straightforward and robust method. The principle steps in a MCS are: (1) A set of random variables $\mathbf{X}$ that follow joint probability density function $f_\mathbf{X}(\mathbf{x})$ is defined. (2) $K$ random samples $\mathbf{x}_{(1)},\ldots,\mathbf{x}_{(K)}$ are generated from $f_\mathbf{X}(\mathbf{x})$. (3) For each sample the response of the underlying model response $h(\cdot)$ is evaluated; i.e., $h_{(i)}=h(\mathbf{x}_{(i)})$. (4) The quantities $h_{(1)},\ldots,h_{(K)}$ are aggregated; e.g., by using the sample mean $\operatorname{E}\left[h(\mathbf{X})\right] \approx \widehat{h} = \frac{1}{K} \sum_{i=1}^K h_{(i)}$.

To apply MCS to structural reliability analysis, we express the integral to evaluate the probability of failure as follows:
$$p_f = \Pr(\mathcal{F}|\mathcal{M}) = \int_{\Omega} I(\mathbf{x}) f_\mathbf{X}(\mathbf{x}) \, \operatorname{d}\mathbf{x}\,,$$ where $I(\mathbf{x})$ is an indicator function defined as:
$$I(\mathbf{x}) = \begin{cases} 1 & \text{if } g(\mathbf{x})\le 0 \\ 0 & \text{otherwise} \end{cases}\,,$$ with $g(\mathbf{x})$ as the limit state function.

Note that the above integral to evaluate $p_f$ is equivalent to the expected value of $I(\mathbf{X})$; i.e., $p_f = \operatorname{E}\left[I(\mathbf{X})\right]$. Thus, a value for the probability of failure $p_f$ can be estimated as follows:

1. Set up a reliability problem by defining the vector of uncertain model parameters $\mathbf{X}$, the joint probability density function $f_\mathbf{X}(\mathbf{x})$ of $\mathbf{X}$ and limit state function $g(\mathbf{x})$.
2. Generate $K$ random samples $\mathbf{x}_{(1)},\ldots,\mathbf{x}_{(K)}$ from $f_\mathbf{X}(\mathbf{x})$.
3. For each sample $\mathbf{x}_{(i)}$, evaluate the limit state function $g(\mathbf{x})$.
4. An unbiased estimate for $p_f$ is obtained by a weighted sum over $K$ samples: $$p_f = \operatorname{E}\left[I(\mathbf{X})\right] \approx \widehat{p} = \frac{H}{K}\,,$$ with $H = \sum_{i=1}^K I(\mathbf{x}_{(i)})$.

If MCS is employed to estimate small values of $p_f$, typically a very large number $K$ of samples is required to obtain sufficiently accurate results. This often renders MCS computationally infeasible for application in numerical reliability analysis. Especially if the analysis is based on computationally demanding models (e.g., finite element models), the computational burden to evaluate thousands of model runs is typically just too large. However, whenever it is computationally feasible to apply MCS, MCS is the most robust structural reliability method amongst all sampling-based structural reliability methods.

You can use our Online Tool for post-processing of MCS to quantify the uncertainty about the value of $p_f$ based on a conducted MCS.

tags


text:
## CryptoDB

### Paper: X-FCSR: a new software oriented stream cipher based upon FCSRs

Authors: Francois Arnault Thierry P. Berger Cédric Lauradoux Marine Minier URL: http://eprint.iacr.org/2007/380 Search ePrint Search Google Feedback with Carry Shift Registers (FCSRs) are a promising alternative to LFSRs in the design of stream cipher. The previous constructions based on FCSRs were dedicated to hardware applications. In this paper, we will describe X-FCSR a family of software oriented stream cipher using FCSRs. The core of the system is composed of two 256-bits FCSRs. We propose two versions: X-FCSR-128 and X-FCSR-256 which output respectively 128 and 256 bits at each iteration. We study the resistance of our design against several cryptanalyses. In this way, we achieve a high throughput and secure stream ciphers suitable for software applications (6.3 cycles/byte).
##### BibTeX
@misc{eprint-2007-13660,
title={X-FCSR: a new software oriented stream cipher based upon FCSRs},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography / stream cipher, FCSRs, software design, cryptanalysis},
url={http://eprint.iacr.org/2007/380},
note={this paper was accepted as a short paper at Indocrypt 2007 marine.minier@insa-lyon.fr 13782 received 25 Sep 2007, last revised 26 Sep 2007},
author={Francois Arnault and Thierry P. Berger and Cédric Lauradoux and Marine Minier},
year=2007
}


text:
Math Help - poisson/Geometric Distribution question????

1. poisson/Geometric Distribution question????

Hi Guys another question, i have not a clue on how to start this question but ill tell you what ive written for it anyway any help for this would be absolutly great!!!

Every packet of TastyBrej contains one of 10 plastic toys, all equally likely, and independantly for each packet. They can be fitted together to make a model space station. Horace has collected 9 toys so far and only need the docking module to complete the space station.
i)
Horaces mother buys packets of Tastybrek according to a poissson process, with a average rate of 1 packet per week.
a) Given that horaces mother buys x packets of tastybrek in 4 weeks, write down the probability that none contains a docking module.
b)State the total law of probabilty and use it to calculate the probabilty that, at the end of the 4 weeks, horace still doesnt have a docking module.

for part ia) i have two answers but theyre both guess
0.9^(x) or e^(-0.4)

ib) I have the total law but am unsure i about the 2nd part i have written. e^(-0.1) x e^(-0.2) x e^(-0.3) x e^(-0.4)= e^(-0.1)

the marks for this is 7marks so i doubt its this easy thank again!!!!

2. Originally Posted by rishul
Hi Guys another question, i have not a clue on how to start this question but ill tell you what ive written for it anyway any help for this would be absolutly great!!!

Every packet of TastyBrej contains one of 10 plastic toys, all equally likely, and independantly for each packet. They can be fitted together to make a model space station. Horace has collected 9 toys so far and only need the docking module to complete the space station.
i)
Horaces mother buys packets of Tastybrek according to a poissson process, with a average rate of 1 packet per week.
a) Given that horaces mother buys x packets of tastybrek in 4 weeks, write down the probability that none contains a docking module.

Mr F says: Pr(no dock | x packets in 4 weeks) ${\color{red}= (0.9)^x}$.

b)State the total law of probabilty and use it to calculate the probabilty that, at the end of the 4 weeks, horace still doesnt have a docking module.

Mr F says: Pr(no dock) = Pr(no dock | x packets in 4 weeks) Pr(x packets in 4 weeks), summed over x = 0 to infinity:

${\color{red} \sum_{x = 0}^{\infty} \left[\Pr(\text{no dock} \, | x \, \text{packets in 4 weeks}) \cdot \Pr(x \, \text{packets in 4 weeks}) \right]}$

Note that ${\color{red}\Pr(x \, \text{packets in 4 weeks}) = \frac{e^{-4} 4^x}{x!}}$.

for part ia) i have two answers but theyre both guess
0.9^(x) or e^(-0.4)

ib) I have the total law but am unsure i about the 2nd part i have written. e^(-0.1) x e^(-0.2) x e^(-0.3) x e^(-0.4)= e^(-0.1)

the marks for this is 7marks so i doubt its this easy thank again!!!!
..


text:
## Results (48 matches)

Label $\alpha$ $A$ $d$ $N$ $\chi$ $\mu$ $\nu$ $w$ prim $\epsilon$ $r$ First zero Origin
4-180e2-1.1-c0e2-0-0 $0.299$ $0.00806$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$0.0, 0.0 0 1 0 1.22605 Artin representation 2.180.6t5.b Modular form 180.1.p.a 4-180e2-1.1-c0e2-0-1 0.299 0.00806 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $0.0, 0.0$ $0$ $1$ $0$ $1.72822$ Artin representation 2.180.8t11.b Modular form 180.1.f.a
4-180e2-1.1-c0e2-0-2 $0.299$ $0.00806$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$0.0, 0.0 0 1 0 2.52796 Artin representation 2.180.12t18.a Modular form 180.1.p.b 4-180e2-1.1-c1e2-0-0 1.19 2.06 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $1.0, 1.0$ $1$ $1$ $0$ $1.05279$ Bianchi modular form 2.0.4.1-2025.2-a Bianchi modular form 2.0.4.1-2025.2-b Elliptic curve 2.0.4.1-2025.2-a Elliptic curve 2.0.4.1-2025.2-b
4-180e2-1.1-c1e2-0-1 $1.19$ $2.06$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$1.0, 1.0 1 1 0 1.15980 Elliptic curve 2.2.5.1-1296.1-b Hilbert modular form 2.2.5.1-1296.1-b Modular form 180.2.d.a 4-180e2-1.1-c1e2-0-10 1.19 2.06 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $1.0, 1.0$ $1$ $-1$ $1$ $1.92895$ Genus 2 curve 32400.b
4-180e2-1.1-c1e2-0-11 $1.19$ $2.06$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$1.0, 1.0 1 -1 1 2.08233 Genus 2 curve 32400.d 4-180e2-1.1-c1e2-0-12 1.19 2.06 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $1.0, 1.0$ $1$ $-1$ $1$ $2.11935$ Bianchi modular form 2.0.4.1-2025.2-c Elliptic curve 2.0.4.1-2025.2-c
4-180e2-1.1-c1e2-0-2 $1.19$ $2.06$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$1.0, 1.0 1 1 0 1.17790 Elliptic curve 2.0.4.1-2025.1-CMc Elliptic curve 2.0.4.1-2025.3-CMc Modular form 180.2.k.a 4-180e2-1.1-c1e2-0-3 1.19 2.06 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $1.0, 1.0$ $1$ $1$ $0$ $1.22304$ Elliptic curve 2.2.5.1-1296.1-a Hilbert modular form 2.2.5.1-1296.1-a
4-180e2-1.1-c1e2-0-4 $1.19$ $2.06$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$1.0, 1.0 1 1 0 1.43392 Elliptic curve 2.0.4.1-2025.1-CMa Elliptic curve 2.0.4.1-2025.3-CMa Modular form 180.2.k.b 4-180e2-1.1-c1e2-0-5 1.19 2.06 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $1.0, 1.0$ $1$ $1$ $0$ $1.63623$ Genus 2 curve 32400.e
4-180e2-1.1-c1e2-0-6 $1.19$ $2.06$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$1.0, 1.0 1 1 0 1.67886 Modular form 180.2.i.a 4-180e2-1.1-c1e2-0-7 1.19 2.06 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $1.0, 1.0$ $1$ $-1$ $1$ $1.76136$ Genus 2 curve 32400.a
4-180e2-1.1-c1e2-0-8 $1.19$ $2.06$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$1.0, 1.0 1 -1 1 1.85975 Genus 2 curve 32400.c 4-180e2-1.1-c1e2-0-9 1.19 2.06 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $1.0, 1.0$ $1$ $1$ $0$ $1.92433$ Elliptic curve 2.0.4.1-2025.1-CMb Elliptic curve 2.0.4.1-2025.3-CMb Modular form 180.2.k.c
4-180e2-1.1-c2e2-0-0 $2.21$ $24.0$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$2.0, 2.0 2 1 0 0.505569 Modular form 180.3.f.c 4-180e2-1.1-c2e2-0-1 2.21 24.0 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $2.0, 2.0$ $2$ $1$ $0$ $0.766783$ Modular form 180.3.l.a
4-180e2-1.1-c3e2-0-0 $3.25$ $112.$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$3.0, 3.0 3 1 0 0.203772 Modular form 180.4.k.a 4-180e2-1.1-c3e2-0-1 3.25 112. 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $3.0, 3.0$ $3$ $1$ $0$ $0.247332$ Modular form 180.4.d.a
4-180e2-1.1-c3e2-0-2 $3.25$ $112.$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$3.0, 3.0 3 1 0 0.252764 Modular form 180.4.k.c 4-180e2-1.1-c3e2-0-3 3.25 112. 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $3.0, 3.0$ $3$ $1$ $0$ $0.802078$ Modular form 180.4.k.b
4-180e2-1.1-c3e2-0-4 $3.25$ $112.$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$3.0, 3.0 3 1 0 1.10707 Modular form 180.4.d.b 4-180e2-1.1-c3e2-0-5 3.25 112. 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $3.0, 3.0$ $3$ $1$ $0$ $1.24341$ Modular form 180.4.i.a
4-180e2-1.1-c4e2-0-0 $4.31$ $346.$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$4.0, 4.0 4 1 0 0.543616 Modular form 180.5.f.c 4-180e2-1.1-c4e2-0-1 4.31 346. 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $4.0, 4.0$ $4$ $1$ $0$ $0.564725$ Modular form 180.5.f.d
4-180e2-1.1-c5e2-0-0 $5.37$ $833.$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$5.0, 5.0 5 1 0 0.525938 Modular form 180.6.d.b 4-180e2-1.1-c5e2-0-1 5.37 833. 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $5.0, 5.0$ $5$ $1$ $0$ $0.750005$ Modular form 180.6.a.f
4-180e2-1.1-c5e2-0-2 $5.37$ $833.$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$5.0, 5.0 5 1 0 0.756956 Modular form 180.6.d.c 4-180e2-1.1-c5e2-0-3 5.37 833. 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $5.0, 5.0$ $5$ $1$ $2$ $1.32622$ Modular form 180.6.d.a
4-180e2-1.1-c5e2-0-4 $5.37$ $833.$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$5.0, 5.0 5 1 2 1.80925 Modular form 180.6.a.g 4-180e2-1.1-c6e2-0-0 6.43 1.71\times 10^{3} 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $6.0, 6.0$ $6$ $1$ $0$ $0.508817$ Modular form 180.7.f.c
4-180e2-1.1-c7e2-0-0 $7.49$ $3.16\times 10^{3}$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$7.0, 7.0 7 1 0 0.106165 Modular form 180.8.d.a 4-180e2-1.1-c7e2-0-1 7.49 3.16\times 10^{3} 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $7.0, 7.0$ $7$ $1$ $0$ $0.645070$ Modular form 180.8.a.h
4-180e2-1.1-c7e2-0-2 $7.49$ $3.16\times 10^{3}$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$7.0, 7.0 7 1 0 0.677408 Modular form 180.8.a.g 4-180e2-1.1-c7e2-0-3 7.49 3.16\times 10^{3} 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $7.0, 7.0$ $7$ $1$ $2$ $1.39809$ Modular form 180.8.a.f
4-180e2-1.1-c9e2-0-0 $9.62$ $8.59\times 10^{3}$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$9.0, 9.0 9 1 0 0.503193 Modular form 180.10.a.e 4-180e2-1.1-c9e2-0-1 9.62 8.59\times 10^{3} 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $9.0, 9.0$ $9$ $1$ $0$ $0.636286$ Modular form 180.10.a.f
4-180e2-1.1-c9e2-0-2 $9.62$ $8.59\times 10^{3}$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$9.0, 9.0 9 1 2 1.18998 Modular form 180.10.a.d 4-180e2-1.1-c11e2-0-0 11.7 1.91\times 10^{4} 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $11.0, 11.0$ $11$ $1$ $0$ $0.0243028$ Modular form 180.12.a.b
4-180e2-1.1-c11e2-0-1 $11.7$ $1.91\times 10^{4}$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$11.0, 11.0 11 1 0 0.399186 Modular form 180.12.a.d 4-180e2-1.1-c11e2-0-2 11.7 1.91\times 10^{4} 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $11.0, 11.0$ $11$ $1$ $0$ $0.422881$ Modular form 180.12.a.c
4-180e2-1.1-c11e2-0-3 $11.7$ $1.91\times 10^{4}$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$11.0, 11.0 11 1 2 1.24325 Modular form 180.12.a.e 4-180e2-1.1-c11e2-0-4 11.7 1.91\times 10^{4} 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $11.0, 11.0$ $11$ $1$ $2$ $1.25467$ Modular form 180.12.a.f
4-180e2-1.1-c13e2-0-0 $13.8$ $3.72\times 10^{4}$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$13.0, 13.0 13 1 0 0.325296 Modular form 180.14.a.f 4-180e2-1.1-c13e2-0-1 13.8 3.72\times 10^{4} 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $13.0, 13.0$ $13$ $1$ $2$ $0.926340$ Modular form 180.14.a.c
4-180e2-1.1-c13e2-0-2 $13.8$ $3.72\times 10^{4}$ $4$ $2^{4} \cdot 3^{4} \cdot 5^{2}$ 1.1 $$13.0, 13.0 13 1 2 1.04915 Modular form 180.14.a.d 4-180e2-1.1-c13e2-0-3 13.8 3.72\times 10^{4} 4 2^{4} \cdot 3^{4} \cdot 5^{2} 1.1$$ $13.0, 13.0$ $13$ $1$ $2$ $1.10229$ Modular form 180.14.a.e


text:
A problem regarding the upperbound of the sum of multinomial random variables.

The description of the problem is simple: Suppose there're many balls in a box. Each ball has a score ranging in $\{c_1,\ldots,c_d\}$, and the probability that you pick a ball of score $c_i$ is $p_i$. Given a budget $C$, you are allowed to repeatedly pick balls with replacement, as long as the total score doesn't exceed $C$. Now the question is,

what's the expectation of the maximum number of balls you can pick?

The problem can also be formulated as follows: suppose $X_1,X_2,\ldots,X_k,\ldots$ are i.i.d multinomial random variables that range in $\{c_1,\ldots,c_d\}$, with corresponding probability $\{p_1,\ldots,p_d\}$ s.t. $\sum_i p_i=1$. Denote $Y_k=\sum_{i=1}^kX_i$, what's the expectation of $$K=\text{arg}\,\text{max}_t\, Y_t\quad\text{ s.t. }Y_t\leq C,$$ where $C$ is some known constant.

It's also acceptable if one can give a non-trivial high-probablity bound of $K$ (i.e., something like $\Pr[M-\epsilon<K<M+\epsilon]>1-\delta$).

My only idea is

\begin{align} \mathbb{E}[K] &= \sum_{i=1}^\infty i\Pr[K=i] \\ &\leq \sum_{i=1}^\infty i\Pr[Y_{i+1}>C] \end{align} If I am lucky, the $\Pr[Y_{i+1}>C]$ can be bounded with some concentration inequality (e.g. Chernoff bound, since each $Y_i$ is a sum of several i.i.d. random variables).

Any suggestions?

• WLOG assume $c_1 < c_2 < \ldots < c_d$. Note $K$ is bounded below and above by $\displaystyle \underline{k} = \left\lfloor \frac {C} {c_d} \right\rfloor$ and $\displaystyle \overline{k} = \left\lfloor \frac {C} {c_1} \right\rfloor$. Also $K > k$ if and only if $Y_{k+1} < C$. Therefore $\displaystyle \mathbb{E}[K] = \sum_{k=0}^{\infty} \Pr\{K > k\} = \underline{k} + \sum_{k=\underline{k}}^{\overline{k}-1} \Pr\{K > k\} = \underline{k} + \sum_{k=\underline{k}}^{\overline{k}-1} \Pr\{Y_{k+1} < c\}$ See if this help - if $\underline{k}$ is large then may be CLT can help to approximate it too. – BGM Apr 17 '17 at 17:05

You can regard this as a random walk with steps $X_i$, and you are interested in the expectation of the hitting time $\tau_C = \inf\{n\ge 0: Y_n>C\}$. The problem is rather standard, but usually there is no nice explicit expression. By simple martingale arguments you can find asymptotics: defining $X_n' = X_n - E[X_n]$, $Y_n' = Y_n - E[Y_n]$, the process $Y_n'$ is a martingale. Since $\tau_C$ is bounded, by the optional stopping theorem, $$0 = E[Y'_{\tau_C}] = E[Y_{\tau_C}] - E[X_1]E[\tau_C],$$ whence $$\frac{C}{E[X_1]} \le E[\tau_C]\le \frac{C+c_d}{E[X_1]},$$ which already gives $E[\tau_C]\sim \frac{C}{E[X_1]}$ as $C\to\infty$.
You can also estimate the probabilities $P(|\tau_C - E[\tau_C]|>a)$ by reformulating them in terms of $Y_n$ and using the large deviation techniques.