text:
I decided this semester to take an algorithms course, in an attempt to finally learn some discrete math. As of late, we have been talking about graph algorithms. The problem is that, having never thought much about graphs, I don’t have a great deal of intuition for them. So I want to devote a post to try to help myself understand this material better.

The problem we are currently concerned with is the following. Let ${G = (V, E)}$ be an undirected graph, such that each edge ${e \in E}$ has a “weight” or “cost” ${w(e) \in \mathbb{R}}$ associated with it. The problem is to find a minimal spanning tree. That is, a subtree ${T \subset G}$ containing all the vertices and such that ${\sum_{e \in T} w(e)}$ is minimal. The naive approach of listing every possible tree and calculating the weights for each of them is horribly inefficient here, as the number of trees on a complete graph of size ${n}$ grows super-exponentially.

1. Trees

To start with, I will recall the definition of a tree. All graphs will be undirected.

Definition 1 A tree is a connected graph containing no cycles.

Intuitively, one has the standard picture of a node branching out into several nodes, each of which branch into several other nodes, and so on. In fact, with the above definition one can show in fact the precise analog of the preceding statement: the “geometric realization” of a tree (when considered as a simplicial complex) is contractible. The above definition is precise, and furthermore is equivalent to the following. An easy consequence of the definition, that we will use, is that a connected subgraph of a tree is tree.

Given a graph ${G}$, we are interested in the following problem: Is there a subgraph ${T \subset G}$ which is a tree and which contains every vertex of ${G}$? Such a subgraph is called a spanning tree. Physically, there are reasonable instances where one might wish to find one, such as in building a pipeline system. The claim is that a spanning tree always exists. To see this, we shall use the following characterization of trees:

Proposition 2 A graph is a tree if and only if it is connected and removing any edge would make it disconnected.

So trees are precisely the minimal connected graphs.

Proof: Let ${G=(V,E)}$ be a tree, and let ${e}$ be an edge in ${G}$ from ${v_1}$ to ${v_2}$. The claim is that the graph ${G-e}$, which is just the pair ${(V, E-\left\{e\right\})}$, is disconnected. For if there were a path ${\rho}$ between ${v_1}$ and ${v_2}$ that did not pass through ${e}$, then we could consider ${\rho}$ and the reversal of ${e}$ to get a cycle. This proves one direction.

For the other, suppose ${G}$ is a minimal connected graph. Then if ${G}$ had a cycle ${v_1 v_2 \dots v_n}$, where ${v_1 = v_n}$, then we can remove the edge ${v_1 v_2}$ without destroying any connectedness—indeed, all the ${v_i}$ are still connected to each other by the rest of the cycle. From this we can see that spanning trees exist:

Proposition 3 Let ${G}$ be a connected graph. Then ${G}$ has a spanning tree.

Proof: Indeed, we can take ${G}$, and choose a subgraph of ${G}$ that is minimal with respect to being connected (i.e. such that removing any edge would disconnect it). We have seen that this is a tree, and it is clearly spanning.

Example 1 In fact, we now see an algorithm for determining a spanning tree in a graph. Namely, we construct a sequence of graphs ${G^{(0)}=G, G^{(1)}, G^{(2)}, \dots}$. The algorithm starts with ${G^{(0)}=G}$. Given ${G^{(n)}}$, we try removing each of the edges, one at a time, and test whether the resulting smaller graph is connected. If none of these ${G^{(n)}-\left\{e\right\}}$ graphs (for ${e \in G^{(n)}}$ an edge) is connected, then we stop at ${G^{(n)}}$, which we have seen is a tree. If we get something that is connected, we let ${G^{(n+1)}}$ to be ${G^{(n)}}$ with this edge removed. It is obvious that this algorithm is correct from the above discussions. But it is not necessarily efficient. To determine whether a graph is connected, we could for instance perform a breadth-first search, whose time is linear in the size of the graph. This graph has at most ${|E|}$ steps, each of which may involve ${|E|}$ breadth-first searches, each of which takes ${O(|E|)}$ time. So the algorithm runs in cubic time.

We have the following additional simple characterization of trees.

Proposition 4 A connected graph ${G = (V, E)}$ is a tree if and only if$\displaystyle |E| = |V|-1.$

Proof: The idea is that adding an edge to a graph can connect two connected components. So adding an edge can cut down the number of components by at most one. Thus if ${G=(V,E)}$ has one less edge than vertex, if we remove one of its edges, then it will be disconnected as there will be too few edges to make the graph connected. So if we have ${|E|=|V|-1}$, then ${G }$ is a minimal connected graph.

Conversely, suppose ${G=(V,E)}$ is a tree. Then if we remove an edge from ${E}$, we find that the new graph ${G- \left\{e\right\}}$ is disconnected—so it is a disjoint union of trees. It must be the union of two trees or the edge ${e}$ could not join them into one connected graph ${G}$. If we induct on the size of the tree, we can compute the vertex and edge counts of ${G}$ by those of the two subcomponents. From this the result becomes clear.

2. Minimum spanning trees

There is a more serious problem. In practice, the graphs for which we want a spanning tree may be weighted, with each edge assigned to a cost, and we will want a spanning tree that minimizes the cost.

Definition 5 A weight on a graph ${G=(V,E)}$ is a function ${w: E \rightarrow \mathbb{R}}$. A spanning tree ${T \subset G}$ is said to be minimal if the sum$\displaystyle \sum_{e \in T} w(e)$

is minimized, over spanning trees.

If we take the identity weight ${w \equiv 1}$ on our graph, then any spanning tree is a minimum spanning tree. Indeed, this is immediate because any two spanning trees have the same cardinality (namely, ${|V|-1}$).

We would now like an algorithm to obtain a minimum spanning tree. The algorithms we shall use will be greedy; that is, they shall add edges starting with the smallest weight (possibly subject to some condition). To approach the idea of building a minimum spanning tree from nothing, we shall need some induction. Namely, we will start with a subgraph that is known to be contained in a minimal spanning tree, and we will want to grow that to a bigger subgraph that is still contained in a minimal spanning tree. We will keep doing this until all the vertices of ${G}$ have been incorporated, at which point we will necessarily have a minimal spanning tree.

To make things convenient, we fix some notation. Let ${G=(V,E)}$ be a graph.

Definition 6 A subgraph ${H \subset G}$ is said to cut ${G}$ into sets ${S, T}$ if ${G = S \cup T}$ (disjoint union) and no edge of ${H}$ is between ${S }$ and ${T}$.

In other words, if we add all the vertices of ${G}$ to ${H}$ to get a new graph ${H'}$, then ${S}$ and ${T}$ are just unions of disjoint connected components of ${H'}$.

Proposition 7 (The cut property) Let ${G=(V,E)}$ be a graph, and let ${H \subset G}$ be a subgraph of ${G}$ which is contained in a minimal spanning tree. Suppose ${H}$ cuts ${G}$ into a disjoint union ${S \cup T}$. Then if ${e \in E}$ is an edge from ${S}$ to ${T}$ (in ${G}$) of minimal weight, then ${H \cup \left\{e\right\}}$ is contained in a minimal spanning tree.

Of course, there is a guarantee that ${e \notin H}$.

Proof: Let us suppose that ${H}$ is contained in the minimum spanning tree ${T}$. Then ${T}$ contains all the vertices of ${G}$, and it is connected, so there is an edge ${e' \in T}$ from ${S }$ to ${T}$. This edge does not belong to ${H}$ by hypothesis.

The claim is that ${T - \left\{e'\right\} \cup \left\{e\right\}}$ is still a minimum spanning tree, which clearly contains ${H \cup \left\{e\right\}}$. To see this, we note that ${T \cup \left\{e\right\}}$ necessarily has a cycle. This cycle has an edge ${e}$ going from ${S}$ to ${T}$, so it must contain another edge ${e'}$ going from ${T}$ to ${S}$.

Now ${T'=T - \left\{e'\right\} \cup \left\{e\right\}}$ is connected (since removing on edge in a cycle does not change connectedness), and it is thus a tree because

$\displaystyle |T'| = |T - \left\{e'\right\} \cup \left\{e\right\}| = |T| = |V|-1.$

The claim is that it is a minimal spanning tree. But the weight of ${T'}$ can be at most the weight of ${T}$, since ${e'}$ has at least the same weight as ${e}$. It follows that ${T}$ is a minimum spanning tree as well.

3. Kruskal’s algorithm

Based on the above “cut property,” we can define an efficient way of finding minimum spanning trees. As described, we will grow them, step by step. Let us now describe an algorithm due to Kruskal.

We will start the tree with a graph ${T^{(0)}}$ that is not a tree—namely, the empty graph on the vertices of ${G}$. Successively we will add edges to this graph to join connected components, making a sequence of graphs ${T^{(0)}, T^{(1)}, T^{(2)}, \dots}$. To do this, we will need an auxiliary data structure ${\mathbf{Set}}$.

In detail, here is the algorithm. We start by placing each of the vertices of ${G}$ into its own set. So we have a collection ${C_0}$ of sets. At each stage ${i}$, we will have a collection ${C_i}$ of sets that contains the connected components of the graph ${T^{(i)}}$; since ${T^{(0)}}$ is the empty graph, it is clear that ${C_0}$ is the set of connected components of ${T^{(0)}}$.

We now construct the ${T^{(i)}}$ inductively. We start by generating a sorted list of the edges ${E}$, sorted by weight in ascending order. We list the edges ${e_1, \dots, e_N}$. We now add edge ${e_1}$ to the graph ${T^{(0)}}$, making a new graph ${T^{(1)}}$.

We then consider the components in ${C_0}$ that contain the vertices of ${e_1}$ and join them to make the new collection ${C_1}$ of sets; clearly ${C_1}$ is the collection of connected components of ${T^{(1)}}$. To decide whether to add ${e_2}$ to the graph ${T^{(1)}}$, we look through the collection ${C_1}$ and determine whether ${e_2}$ joins two connected components of ${T^{(1)}}$. If it does, we add ${e_2}$; if not, we don’t.

Inductively, the construction is as follows. At stage ${i}$, let us suppose inductively that ${T^{(i-1)}}$ has been constructed, and that the vertices of ${G}$ are partitioned into a collection of sets ${C_{i-1}}$ that represents the connected components of ${T^{(i-1)}}$. Then we split into two steps:

1. If ${e_i}$ connects two connected components of ${T^{(i-1)} }$ (as we can check by a look at ${C_{i-1}}$), then we let ${T^{(i)} = T^{(i-1)} \cup \left\{e_i\right\}}$, and we merge the two connected components in ${C_{i-1}}$ corresponding to the endpoints of ${e_i}$.
2. If the endpoints of ${e_i}$ lie in the same connected component of the partial graph ${T^{(i-1)},}$ then we just take ${T^{(i)}= T^{(i-1)}}$.

The algorithm stops when ${|V|-1}$ edges have been added.

Theorem 8 Given a connected weighted graph ${G = (V,E)}$, Kruskal’s algorithm always produces a minimal spanning tree.

Proof: This will be a straightforward argument from the cut property. Let us inductively suppose that ${T^{(i-1)}}$ is contained in a minimal spanning tree; then we shall show that ${T^{(i)}}$ is too.

As above, there were two cases to the above algorithm: in the second, we just had ${T^{(i)}= T^{(i-1)}}$, and there was nothing to prove. We need to show that ${T^{(i)}}$ is contained in a minimal spanning tree in the first case. To see this, let us apply the cut property to ${T^{(i-1)}}$. By assumption, there are two connected components of ${T^{(i-1)}}$ that the edge ${e_i}$ joins; thus we can partition ${V = V_1 \cup V_2}$ such that no edge of ${T^{(i-1)}}$ connects ${V_1, V_2}$ and such that ${e_i}$ does connect ${V_1, V_2}$.

We now need to show that, among the edges connecting ${V_1, V_2}$, ${e_i}$ is the one with minimal weight. But if ${e_i}$ did not have minimal weight among edges connecting ${V_1, V_2}$, there would have been an edge ${e_j, j that also connected vertices in ${V_1, V_2}$ (which cannot be in ${T^{(i-1)}}$). However, ${e_j}$ would then have been added to the graph at stage ${j}$ for joining two connected components of ${T^{(j)} \subset T^{(i-1)}}$, which is a contradiction.


text:
# How do you solve 3y - 2x = 11 and y + 2x = 9 using substitution?

Mar 10, 2018

$y = 5 \mathmr{and}$x=2#

#### Explanation:

$2 x + y = 9$
$- 2 x + 3 y = 11$

We need to solve $2 x + y = 9$ for $y$

$2 x + y = 9$
$y = 9 - 2 x$

Now substitute $- 2 x + 9$ for $y$ in $- 2 x + 3 y = 11$

$- 2 x + 3 y = 11$

$- 2 x + 3 \left(- 2 x + 9\right) = 11$

Distribute

$- 2 x + \left(3\right) \left(- 2 x\right) + \left(3\right) \left(9\right) = 11$

$- 2 x - 6 x + 27 = 11$

$- 8 x + 27 = 11$

$- 8 x = 11 - 27$

$- 8 x = - 16$

$x = \frac{- 16}{- 8}$

$x = 2$

Now substitute $2$ for $x$ in $y = - 2 x + 9$

$y = - 2 x + 9$

$y = - 2 \left(2\right) + 9$

$y = - 4 + 9$

$y = 5$

Thus,

The answers are $y = 5$ and $x = 2$

format: plain


text:
# What is the function of a diode connected to a GPIO?

I'm reading a schematic (done by a former employee) with a microcontroller, and I came across this circuit:

What is the function of D1?

Also, I think that R2 isn't necessary, because the control input come from another GPIO that always has 1 or 0 as its output.

Besides this one, there is another block of this same circuit but connected to the RESET pin of the microcontroller. This part of the circuit is used to flash the microcontroller via ISP.

R1 = 47k
R2,R3 = 10k
D1 = 1N4148

• You do realize that the GPIO does not actually have a "1" or a "0" but that it has voltages that represent these symbols? – placeholder Nov 18 '14 at 14:12
• What microcontroller are you using? – Peter Mortensen Nov 19 '14 at 17:15
• @PeterMortensen: LPC1759 – Ricardo Crudo Nov 20 '14 at 13:38

It's there to protect the B-E junction of Q1 from reverse breakdown.

For positive input voltages, the B-E junction of Q1 will conduct, and the voltage at the base will be limited to about +0.65V. As long as R1 is sized appropriately to limit the current, fairly arbitrary positive voltages can be applied to the input.

D1 provides a similar path for negative input currents, guaranteeing that the base voltage never goes below -0.65V for the same range of negative voltages.

• hmm, I got it. So, in this case it isn't necessary. I guess I know what happened. Originally this control pin was receiving signal from a DTR pin, of the old RS232 serial port, now, that I have GPIO to GPIO control, I believe I don't need it anymore. – Ricardo Crudo Nov 18 '14 at 15:23
• Clamping diodes like that are rarely "needed" as a required part of the design. Instead, they are for just-in-case situations that you don't plan for. Are you 100% certain that the power supply will never have a hiccup? That some load dump condition will never occur for a few milliseconds? That some other component on the board won't fail and cause an unexpected negative voltage? The diode certainly isn't hurting anything, so I wouldn't think removing its potential benefit is a good idea. – Dan Laks Nov 18 '14 at 16:41
• @DanLaks - nonetheless, such protections are not normally used between microcontrollers (if on the same board / supply). What we are looking at here is a discrete RS232 level shifter (complete with inverter). Probably the entire circuit is now superfluous - even if there is a difference between IO voltages, there are simpler solutions and the inversion can usually be done in software. – Chris Stratton Nov 19 '14 at 16:20
• Just to add to this: reverse breakdown in bipolar transistors happens in the 3-6V range, so you don't need that much voltage to go outside the specs of the part + at that point the device can be damaged. – Jason S Nov 19 '14 at 16:41

That is called an "input clamping" diode. It's often done with two diodes, not just one (one to Vcc as well as one to GND), and is used to "clamp" the incoming voltage to ground minus the forward voltage of the diode (or Vcc plus the forward voltage for the upper diode).

In your circuit it is specifically to remove any negative voltages from the input.

Question poster mentioned the critical info in his comment "Originally this control pin was receiving signal from a DTR pin, of the old RS232 serial port" - that's the real answer to "why"; RS232 uses negative voltages for signalling (as low as -15v), hence the (fairly large) current limiting resistor R1 and diode D1 to stop the transistor getting fried by being reverse-biased across the base-emitter junction. You don't normally see (or need) this kind of diode if it's being driven by a CPU; typically just a current limiting resistor will do.

As others have suggested, but not explicitly stated, the diode is basic input protection for an externally accessible input. I.e. the pin is likely on a connector which the user of this device drives.

On the other hand, if this control input is not external, the diode is likely not required unless it's being driven from a circuit that provides a negative voltage under normal operation (i.e. maybe its a negative going pulse like +/-5V square wave, or being driven by an AC coupled waveform). Protecting a transistor like this if negative voltages are not expected is probably pointless since something far worse has happened if your circuit is driving a negative voltage unexpectedly, and in which case the base resistor R1 likely provides enough protection anyway.

Edit:

Just noticed you mentioned that a microcontroller drives the CONTROL input, so I'd say the diode is pointless, since you've got a much bigger problem if the microcontroller is driving a negative voltage.

Also just as you alluded, if the microcontroller is always driving the output then R2 is also pointless. However, in reset state many microcontrollers will tristate their outputs, and possibly enable pull-ups. The enabled pull-ups could cause a small current to flow in the base, multiply that by a couple hundred and that's the current that would flow through the transistor. This depends on the strength of the internal pull-ups (~50 - 100kOhm is typical).


text:
# CEP – Invaluable Metric for the Hiring Process

Candidate Effectiveness Potential (CEP) is the one metric that you can rely on in your hiring process. How did we get to it in our company - and what makes it such a good indicator?

Hiring is a tedious process that takes time and devotion, and as such it should be measured and improved upon every time.

After the candidate goes past the interview stage we dedicate some time (usually up to a week) with them.  They are treated as equal team members, working on tasks that find the way to production, spending time with the team over lunch, having fun and getting to know each other better. During that time, we try to evaluate the candidate against number of key performance indicators, which help us identify the best fit for the company.

After utilizing this process for a while — and checking it against candidates who fail, and candidates who turn out to become great colleagues —  we actually came to an astonishing conclusion. All we ever needed to focus on during in-house testing of our candidates was one thing, and one thing only:

How much of your energy does the candidate consume in order to deliver the needed value?

The ratio of delivered value vs. consumed energy to deliver it is what defines the candidate’s potential. In an effort to have a fancy metric of our own, we named that Candidate Effectiveness Potential, and it has a rather simple formula:

$CEP =\frac{Value}{Energy}$

The paradigm aligns pretty well with the well-known skill/motivation matrix, and is basically our startupish version of it, focused only on energy consumption as a function of delivering value.

High value/energy ratio and low value/energy produce same CEP value, however with one big difference that results in “no hire” outcome. You don’t have the time nor established processes to teach people how to produce value. Instead, you can only guide people who are capable of producing value to become more accountable, seek minimal guidance and micromanagement.

Reasons behind consuming too much energy are widely diverse. They span from (negative) ones such as lack of motivation to ones that are result of not being comfortable enough (or being paralyzed) to assume accountability and (just) do things. But here’s the thing – you’re not interested in reasons at the moment. You just want to know how much energy do you have to invest to get the output, which is exactly what CEP tells you. It doesn’t matter how you operate – whether you email the tasks to the candidate/employee, or sit right next to him. You get exactly the same answer to the question – “do I need to iterate 10 times to get what I need, or answer tons of questions and still get it wrong?”.

## Three Reasons You Need CEP for Your Startup

### 1. If you want to build the flat-structure company, this hiring metric will get you there

Distribute decision-making power and discourage consensus seeking. This hiring process is a part of producing people who are highly independent and result-driven.

### 2. Rallies entire company’s culture around efficiency

Technology is a fast-moving business. Today, your “itch” for senior PHP developer with experience in socket programming might become obsolete when you pivot. You need people who think, learn, grow quickly, and quadruple skills every fortnight. Who understand the context, and find the way to hack the problem.

### 3. Simple, efficient, cost-effective way to significantly improve your hiring

You can fall back to the CEP indicator if you’re inexperienced in hiring. It is subjective enough to “work” because there are no “process” elements in it. Quite simply, it comes down to this: “does (s)he consume too much of my energy?”

These findings point to a new approach to hiring, one based on principles that directly affect the company culture and structure and with that results. By substituting a wide range of complex decisions with a single metric, you can get to a very accurate candidate assessment, very quickly.


text:
# Dirichlet series summation for zeta

by user1828958   Last Updated March 10, 2019 16:20 PM - source

This question is a bit different from one another online. It appear in reppresenting Dirichlet series

Do you know how the following equation is true?

$$\sum_{1}^{\infty} \frac{1}{n^s} = \sum_{1}^{\infty} n \cdot \big (\frac{1}{n^s} - \frac{1}{(n+1)^s} \big)$$

Tags :


text:
# Thermopower

The thermopower, or thermoelectric power (also called the Seebeck coefficient) of a material is a measure of the magnitude of an induced thermoelectric voltage in response to a temperature difference across that material.[1] The thermopower has units of volts per kelvin (V/K),[1] although it is more often given in microvolts per kelvin (μV/K).

Thermopower is a misnomer. What is called thermopower would be more correctly dubbed thermoelectric sensitivity as it measures the voltage or electric potential (not the electric power) induced in response to a temperature difference. Note that the unit of thermopower (V/K) is different from the unit of power (watts).

The phenomenon quantified by thermopower is called the Seebeck effect. The Seebeck effect and two related phenomena (the Peltier effect and Thomson effect) are together called the "thermoelectric effect".

## Physics of thermopower

An applied temperature difference causes charged carriers in the material, whether they are electrons or holes, to diffuse from the hot side to the cold side, similar to a gas that expands when heated.

Mobile charged carriers migrating to the cold side leave behind their oppositely charged and immobile nuclei at the hot side thus giving rise to a thermoelectric voltage (thermoelectric refers to the fact that the voltage is created by a temperature difference). Since a separation of charges also creates an electric field, the buildup of charged carriers onto the cold side eventually ceases at some maximum value since there exists an equal amount of charged carriers drifting back to the hot side as a result of the electric field at equilibrium. Only an increase in the temperature difference can resume a buildup of more charge carriers on the cold side and thus lead to an increase in the thermoelectric voltage. Incidentally the thermopower also measures the entropy per charge carrier in the material.

The thermopower of a material, represented as $S$, depends on the material's temperature, and crystal structure. Typically metals have small thermopowers because most have half-filled bands. Electrons (negative charges) and holes (positive charges) both contribute to the induced thermoelectric voltage thus canceling each other's contribution to that voltage and making it small. In contrast, semiconductors can be doped with an excess amount of electrons or holes and thus can have large positive or negative values of the thermopower depending on the charge of the excess carriers. The sign of the thermopower can determine which charged carriers dominate the electric transport in both metals and semiconductors.

Superconductors have zero thermopower since the charged carriers carry no entropy. Equivalently, the thermopower is zero because it is impossible to have a finite voltage across a superconductor. (For example, by Ohm's law, V=IR=0, since the resistance, R, is equal to zero in a superconductor.)

## Definition

If the temperature difference ΔT between the two ends of a material is small, then the thermopower of a material is defined as:

$S = - {\Delta V \over \Delta T}$

where ΔV is the thermoelectric voltage seen at the terminals in steady-state when the current is zero. (See below for more on the signs of ΔV and ΔT.)

This can also be written in relation to the electric field $E$ and the temperature gradient $\nabla T$, by the equation:

$S = {E \over \nabla T}$

Strictly speaking, these two expressions are not quite the same, and it is the first, not the second, which agrees with the practical, experimental definition. (They differ because voltage, defined here as "the quantity measured with a voltmeter", depends not only on the electric field but also the internal chemical potential gradient of electrons in the material.[2])

### Sign of the thermopower

Here, again, are the formulas for the Seebeck coefficient, with the sign made explicit:

$S = -\frac{V_{left}-V_{right}}{T_{left}-T_{right}}$
$\mathbf{E} = S\nabla T$

where "left" and "right" denote two ends of the material, and where the second equation is understood as vector multiplication. Thus, if S is positive, the end with the higher temperature has the lower voltage, and vice-versa, and the electric field will point in the same direction as the temperature gradient.

Note that there is a minus sign in the first equation, but not the second. This is because the electric field points from the higher voltage towards the lower voltages, whereas the temperature gradient points from the lower temperature towards the higher temperature.

Charge carriers tend to respond to a temperature gradient by moving in the opposite direction, i.e. from the hot end to the cold end. They tend to respond to an electric field in different ways depending on their charge: positive charges tend to move in the same direction as the field, while negative charges move in the opposite direction of the field. For equilibrium to be reached, these two tendencies have to cancel out. Thus, for purely p-type materials which have only positive mobile charges (holes), the electric field and temperature gradient should point in the same direction in equilibrium, giving S>0. Likewise, for purely n-type materials which have only negative mobile charges (electrons), the electric field and temperature gradient should point in opposite directions in equilibrium, giving S<0. In practice, real materials often have both positive and negative charge-carriers, and the sign of S usually depends on which of them predominates.

## Measurement

In practice one rarely measures the absolute thermopower of the material of interest. This is because electrodes attached to a voltmeter must be placed onto the material in order to measure the thermoelectric voltage. The temperature gradient then also typically induces a thermoelectric voltage across one leg of the measurement electrodes. Therefore the measured thermopower is a contribution from the thermopower of the material of interest and the material of the measurement electrodes. This arrangement of two materials is usually called a thermocouple.

The measured thermopower is then a contribution from both and can be written as:

$S_{AB} = S_B-S_A = {\Delta V_B \over \Delta T} - {\Delta V_A \over \Delta T}$

Superconductors have zero thermopower, as mentioned above. By using superconducting leads, it is possible to get a direct measurement of the absolute thermopower of the material of interest, since it is the thermopower of the entire thermocouple as well.

A measurement of the Thomson coefficient, $\mu$, of a material can also yield the thermopower through the relation: $S = \int {\mu \over T} dT$

## Thermoelectric power generation

The thermoelectric effect is sometimes used to generate electrical power, starting from a source of a temperature gradient. For example, some spacecraft are powered by a radioisotope thermoelectric generator, exploiting the temperature difference between a radioactively-heated plate and the cold empty space surrounding the craft. Some researchers hope that, in the future, much wider use could be made of thermoelectric power generation, including using waste heat from automobiles (see Automotive Thermoelectric Generators) and power plants. (This is a form of energy recycling.)

The efficiency with which a thermoelectric material can generate electrical power depends on several material properties, of which perhaps the most important is the thermopower. A larger induced thermoelectric voltage for a given temperature gradient will lead to a higher efficiency. Ideally one would want very large thermopower values since only a small amount of heat is then necessary to create a large voltage. This voltage can then be used to provide power.

There is an active research effort to find materials that could make cheaper and more efficient thermoelectric power generators; to learn more see the article Thermoelectric materials.

## Materials with High Seebeck Coefficient

It is important to note that a material's Seebeck Coefficient is inversely related to its carrier density. Therefore, insulators tend to have very high Seebeck coefficients, while metals have lower values due to their high carrier concentrations.

## References

1. ^ a b Concepts in Thermal Physics, by Katherine M. Blundell Weblink through Google books
2. ^ When a voltmeter is attached across a sample, what is measured is not the electric potential difference, but the electrochemical potential difference. The rest is canceled out by the contact potential with the leads of the voltmeter. This is the same reason that the built-in potential of a p-n junction cannot be measured directly with a voltmeter, but can only be indirectly inferred. For a specific discussion of this point, see Taylor, 1973, or Cai and Mahan 2006. In Cai and Mahan, the electric-field-only expression is called the "theoretical Seebeck coefficient", while the expression related to voltage or electrochemical potential is called the "phenomenological Seebeck coefficient". Further discussion is in Physics of transition metal oxides by Sadamichi Maekawa, page 323, or Thermoelectrics: Basic Principles and New Materials Developments by Nolas et al., page 38.
3. ^ Abstract: "Thermoelectric properties of perovskite type strontium ruthenium oxide", Takuji Maekawa et al., Osaka University, Japan, 2004


text:
# B Magnetic field at relativistic speed

1. Apr 29, 2016

### alba

I am trying to understand magnetism and its relation to electricity:

Suppose there are two electrons travelling side by side in deep space at 1 cm distance at .99 c

In this article http://academic.mu.edu/phys/matthysd/web004/l0220.htm it is said that the ratio $F_B/F_E$ is $v^2/c^2$ for v << c. According to that formula the magnetic pull sould be .9801 times the electrostatic repulsion. Can you tell me

- 1) what is the actual value (applying relativity, since the speed is close to c) ? Is there a big difference? Intuitively it shouldn't be smaller, yet it can't possibly get greater than 1, can it?
- 2) what happens to the trajectory of the particles due to the influence of the mutual magnetic field, does if deflect from the straight line?

2. Apr 30, 2016

### jartsa

Force: To get the force in the other frame, divide the center of mass force by gamma, force means here simply the force that effects the electrons. Force transforms in this simple way in this simple case.

Trajectory: The separation process is time dilated. To get the timetable of the separation process in the other frame, multiply the center of mass timetable by gamma.

Last edited: Apr 30, 2016
3. Apr 30, 2016

### alba

- 1) Is the attractive force greater than .98 or smaller? gamma is 7.09, right? center of mass is at .5 cm, what is the CoM force? The repulsive electrostatic force isn't affected at all by relativistic speed?

- 2) I am asking about the trajectories, are they bent from the straight line, besides the particles slowly separating?

Last edited: Apr 30, 2016
4. Apr 30, 2016

### jartsa

1: I didn't check the link, until now. I am sure the total force changes by gamma, but the question wasn't about total force. But somehow I feel that the formula F=q*v*B should work even if v is relativistic.

2: A force on a projectile causes a bending of its trajectory. So trajectories are bent in this case.

5. Apr 30, 2016

### alba

1) Are you saying that the actual value of magnetic force is .9801 the coulomb force and no correctionis needed? Really? So, what is all the big deal of SR?
2. does magnetic field mutually generated (Lorenz force) make the trajectories converge? does this compensate the divergence ? Can you roughly figure out what happens to the particles after a seond or two?

6. Apr 30, 2016

### greswd

Use the E and B transforms for SR

7. Apr 30, 2016

### greswd

8. Apr 30, 2016

### alba

9. Apr 30, 2016

### greswd

You know what the Lorentz Force Law is? It is co-variant with SR, it applies in all cases. That is how we obtain the magnitude of the force.

In relativity Force = dp/dt where p is the relativistic momentum.

1) Yes, it cannot exceed 1.

2) It will deflect.

10. Apr 30, 2016

### alba

1) tkanks, so if without SR it is .98 it cannot increase much
2) momentum is .99*10^10 *7.098 = 7.018 *10 * 10 , right?
Lorenz force pushes the trajectories to converge, doesn't it? whereas electric exceeds magnetic force by .0199. Since you say that in the end they diverge, Lorenz force is less than .0199 , right?

11. Apr 30, 2016

### jartsa

No, I'm just thinking about a wire loop, and the fact that the magnetic field of the loop is proportional to the current in the loop, and the current in the loop is proportional to the velocity of the moving charges in the loop, if the amount of moving charges is constant. So when we know the currents of two loops, we can calculate the magnetic force between the two loops very easily, without worrying about relativity

And we can also calculate very easily magnetic force between two straight wire segments, using Ampere's law, no relativistic corrections needed.

What happens after one second is the same what happens after 1/gamma seconds in the other frame. In other words: What happens in the non-rest frame is a slow-motion version of what happens in the rest-frame. In other words high speed motion causes time dilation.

12. Apr 30, 2016

### greswd

Idk where you get those numbers from.

Both electric and magnetic forces are part of the Lorentz force.

The electric force will always exceed the magnetic force so they will always diverge.

13. Apr 30, 2016

### Staff: Mentor

This might be the best question to start with. First, look at things in the rest frame of the electrons--or at least, in their rest frame at some instant. In that frame, there is no magnetic force; there is only the electrostatic repulsion between the electrons. So in this frame, they will accelerate away from each other.

Now transform to a frame in which the electrons start out moving parallel to each other at 0.99c. Since the relative motion of the electrons must be invariant, if they diverge in one inertial frame, they must diverge in all inertial frames. So they must diverge in this new "moving" frame as well.

The above analysis should show you that one way of viewing what we call a "magnetic" field is as just what you get when you look at an electrostatic field in a frame in which the source is moving. More precisely, it's a piece of what you get.

If you look at the Wikipedia page greswd linked to, that shows the transformation of the E and B fields, you will see, if we start from a frame where the field is electrostatic--i.e., where we have nonzero E but zero B--and then transform to a different frame, where the relative velocity between the frames is perpendicular to the direction of the E field (which in this case means perpendicular to the direction of separation between the electrons), you will see that the E field increases by $\gamma$, and the B field in the new frame will be $\gamma v$ times the original E field. Since the force due to the B field has a magnitude of $v$ times the B field, the ratio $F_B / F_E$ will be $v^2$. In other words, the formula that is valid for $v << c$ is also valid for $v \rightarrow c$, as others have already pointed out.

Furthermore, if you work out the direction of the force due to the B field, you will see that it is the direction given by $v \times (v \times E)$, which, using standard identities for cross products, works out to the opposite direction from the force due to the E field. So what is happening here is that, in the moving frame, the force due to the E field increases, but a B field appears giving a force that partially opposes the force due to the E field. The net effect is that the electrons diverge in all frames, and their diverging worldlines transform just as they should by the Lorentz transformation equations.

14. May 1, 2016

### alba

Isn't there a crucial point when the the magnetic attraction plus the Lorenz divergence will be greater than the electric repulsion? In LHC protons reach .999999991 c and therefore attraction is only 0.000000018 smaller than repulsion, can't Lorenz convergence be greater than that?

15. May 1, 2016

### Ibix

You can always transform into the rest frame of the particles. In that frame they repel due to plain vanilla electrostatic repulsion. They must, therefore, repel in all frames, or else there is a contradiction. A frame is simply a point of view. You can't make things that are moving apart start moving together by changing point of view.

16. May 1, 2016

### alba

http://i.stack.imgur.com/3ga0O.png
That is right, so, how can repulsion (electric) become attraction (magnetic) in any other frame? Can you figure out the actual rate of divergence of electrons in all frames?

Last edited: May 1, 2016
17. May 1, 2016

### Ibix

There is always a net repulsion. Your explanation for why this is so may vary. In one frame there is an electrostatic repulsion, while in another there is a stronger electrostatic repulsion and a weaker magnetic attraction.

Yes, you can figure out the rate of divergence in any frame. Probably the easiest way to do it is to work out the positions and/or velocities of the electrons as a function of time in their rest frame (more precisely the center of mass frame of the pair) and then transform those.

18. May 1, 2016

### alba

Can you do that? I can't, that's why I posted in the first place. Can you tell me if the forces are correctly representedin the picture? There are two attractive forces and only one repulsive, right? Are you saying that the convergence due to Lorenz force can never be greater than Fe-Fm?

19. May 1, 2016

### Ibix

Not in my head. The forces in the diagram look plausible (there's a net repulsion) but I haven't checked them in detail.

Do you know how to calculate the electrostatic force between two charges? Coulomb's Law? If so, can you calculate the force on the two electrons if they are at rest (i.e. electrostatic repulsion only)?

20. May 1, 2016

### alba

The point of the whole question is: what does actually happen? do A and B diverge at a rate dictated by Coulomb or at a different rate? if so, is it .019 Coulomb or more or less? Do you have to correct that value due to SR or not?do you have do throw in Lorenz convergence or not?

Even if you can't or are not willing to worg out the actual values, can you answer any of those general questions?


text:
Balbharati Maharashtra State Board 12th Commerce Maths Solution Book Pdf Chapter 8 Probability Distributions Ex 8.2 Questions and Answers.

Maharashtra State Board 12th Commerce Maths Solutions Chapter 8 Probability Distributions Ex 8.2

Question 1.
Check whether each of the following is p.d.f.
(i) $$f(x)= \begin{cases}x & \text { for } 0 \leq x \leq 1 \\ 2-x & \text { for } 1<x \leq 2\end{cases}$$
Solution:
Given function is
f(x) = x, 0 ≤ x ≤ 1
Each f(x) ≥ 0, as x ≥ 0.

∴ The given function is a p.d.f. of x.

(ii) f(x) = 2 for 0 < x < 1
Solution:
Given function is
f(x) = 2 for 0 < x < 1 Each f(x) > 0,

∴ The given function is not a p.d.f.

Question 2.
The following is the p.d.f. of a r.v. X.
$$f(x)= \begin{cases}\frac{x}{8} & \text { for } 0<x<4 \\ 0 & \text { otherwise }\end{cases}$$
Find (i) P(X < 1.5), (ii) P(1 < X < 2), (iii) P(X > 2)
Solution:

Question 3.
It is felt that error in measurement of reaction temperature (in Celsius) in an experiment is a continuous r.v. with p.d.f.
$$f(x)= \begin{cases}\frac{x^{3}}{64} & \text { for } 0 \leq x \leq 4 \\ 0 & \text { otherwise }\end{cases}$$
(i) Verify whether f(x) is a p.d.f.
(ii) Find P(0 < X ≤ 1).
(iii) Find the probability that X is between 1 and 3.
Solution:
(i) f(x) is p.d.f. of r.v. X if
(a) f(x) ≥ 0, ∀ x ∈ R
(b) $$\int_{0}^{4} f(x) d x$$ = 1

Question 4.
Find k, if the following function represents the p.d.f. of a r.v. X.
(i) $$f(x)= \begin{cases}k x & \text { for } 0<x<2 \\ 0 & \text { otherwise }\end{cases}$$
Also find P[$$\frac{1}{4}$$ < X < $$\frac{1}{2}$$]
Solution:

(ii) $$f(x)= \begin{cases}k x(1-x) & \text { for } 0<x<1 \\ 0 & \text { otherwise }\end{cases}$$
Also find (a) P[$$\frac{1}{4}$$ < X < $$\frac{1}{2}$$], (b) P[X < $$\frac{1}{2}$$]
Solution:
We know that

Question 5.
Let X be the amount of time for which a book is taken out of the library by a randomly selected student and suppose that X has p.d.f.
$$f(x)= \begin{cases}0.5 x & \text { for } 0 \leq x \leq 2 \\ 0 & \text { otherwise }\end{cases}$$
Calculate (i) P(X ≤ 1), (ii) P(0.5 ≤ X ≤ 1.5), (iii) P(X ≥ 1.5).
Solution:
Given p.d.f. of X is f(x) = 0.5x for 0 ≤ x ≤ 2
∴ Its c.d.f. F(x) is given by

(i) P(X < 1) = F(1)
= 0.25(1)2
= 0.25

(ii) P(0.5 < X < 1.5) = F(1.5) – F(0.5)
= 0.25(1.5)2 – 0.25(0.5)2
= 0.25[2.25 – 0.25]
= 0.25(2)
= 0.5

(iii) P(X ≥ 1.5) = 1 – P(X ≤ 1.5)
= 1 – F(1.5)
= 1 – 0.25(1.5)2
= 1 – 0.25(2.25)
= 1 – 0.5625
= 0.4375

Question 6.
Suppose X is the waiting time (in minutes) for a bus and its p.d.f. is given by
$$f(x)=\left\{\begin{array}{cl} \frac{1}{5} & \text { for } 0 \leq x \leq 5 \\ 0 & \text { otherwise } \end{array}\right.$$
Find the probability that (i) waiting time is between 1 and 3 minutes, (ii) waiting time is more than 4 minutes.
Solution:
p.d.f. of r.v. X is given by
f(x) = $$\frac{1}{5}$$ for 0 ≤ x ≤ 5
This is a constant function.
(i) Probability that waiting time X is between 1 and 3 minutes

(ii) Probability that waiting time X is more than 4 minutes

Question 7.
Suppose error involved in making a certain measurement is a continuous r.v. X with p.d.f.
$$f(x)= \begin{cases}k\left(4-x^{2}\right) & \text { for }-2 \leq x \leq 2 \\ 0 & \text { otherwise }\end{cases}$$
Compute (i) P(X > 0), (ii) P(-1 < X < 1), (iii) P(X < -0.5 or X > 0.5)
Solution:
Since given f(x) is a p.d.f. of r.v. X
Since -2 ≤ x ≤ 2
∴ x2 ≤ 4
∴ 4 – x2 ≥ 0
∴ k(4 – x2) ≥ 0
∴ k ≥ 0 [∵ f(x) ≥ 0]

Question 8.
Following is the p.d.f. of a continuous r.v. X.
$$f(x)= \begin{cases}\frac{x}{8} & \text { for } 0<x<4 \\ 0 & \text { otherwise }\end{cases}$$
(i) Find an expression for the c.d.f. of X.
(ii) Find F(x) at x = 0.5, 1.7, and 5.
Solution:
The p.d.f. of a continuous r.v. X is
$$f(x)= \begin{cases}\frac{x}{8} & \text { for } 0<x<4 \\ 0 & \text { otherwise }\end{cases}$$
(i) c.d.f. of continuous r.v. X is given by

(ii) F(0.5) = $$\frac{(0.5)^{2}}{16}=\frac{0.25}{16}=\frac{1}{64}$$ = 0.015
F(1.7) = $$\frac{(1.7)^{2}}{16}=\frac{2.89}{16}$$ = 0.18
For any of x greater than or equal to 4, F(x) = 1
∴ F(5) = 1

Question 9.
The p.d.f. of a continuous r.v. X is
$$f(x)=\left\{\begin{array}{cl} \frac{3 x^{2}}{8} & \text { for } 0<x<2 \\ 0 & \text { otherwise } \end{array}\right.$$
Determine the c.d.f. of X and hence find (i) P(X < 1), (ii) P(X < -2), (iii) P(X > 0), (iv) P(1 < X < 2).
Solution:
The p.d.f. of a continuous r.v. X is

Question 10.
If a r.v. X has p.d.f.
$$f(x)= \begin{cases}\frac{c}{x} & \text { for } 1<x<3, c>0 \\ 0 & \text { otherwise }\end{cases}$$
Find c, E(X) and V(X). Also find f(x).
Solution:
The p.d.f. of r.v. X is
f(x) = $$\frac{c}{x}$$, 1 < x < 3, c > 0
For p.d.f. of X, we have


text:
Lower bounds on the bounded coefficient complexity of bilinear maps

Type
Publication
Journal of the ACM (JACM)


text:
# Environmental Health

Mun S Ho, Dale W Jorgenson, and Wenhua Di. 2002. “Pollution taxes and public health.” In Economics of the Environment in China, edited by Jeremy J. Warford and Yi Ning Li. Bethesda, MD: Aileen International Press.
Rong Xie, Clive E. Sabel, Xi Lu, Weimo Zhu, Haidong Kan, Chris P. Nielsen, and Haikun Wang. 2016. “Long-term trend and spatial pattern of PM2.5-induced premature mortality in China.” Environment International, 97, Pp. 180-186. Publisher's VersionAbstract

With rapid economic growth, China has witnessed increasingly frequent and severe haze and smog episodes over the past decade, posing serious health impacts to the Chinese population, especially those in densely populated city clusters. Quantification of the spatial and temporal variation of health impacts attributable to ambient fine particulate matter (PM2.5) has important implications for China's policies on air pollution control. In this study, we evaluated the spatial distribution of premature deaths in China between 2000 and 2010 attributable to ambient PM2.5 in accord with the Global Burden of Disease based on a high resolution population density map of China, satellite retrieved PM2.5 concentrations, and provincial health data. Our results suggest that China's anthropogenic ambient PM2.5 led to 1,255,400 premature deaths in 2010, 42% higher than the level in 2000. Besides increased PM2.5 concentration, rapid urbanization has attracted large population migration into the more developed eastern coastal urban areas, intensifying the overall health impact. In addition, our analysis implies that health burdens were exacerbated in some developing inner provinces with high population density (e.g. Henan, Anhui, Sichuan) because of the relocation of more polluting and resource-intensive industries into these regions. In order to avoid such national level environmental inequities, China's regulations on PM2.5 should not be loosened in inner provinces. Furthermore policies should create incentive mechanisms that can promote transfer of advanced production and emissions control technologies from the coastal regions to the interior regions.

Ying Zhou, Jonathan I Levy, James K Hammitt, and John S Evans. 2007. “Population exposure to pollutants from the electric power sector using CALPUFF.” In Clearing the air: The health and economic damages of air pollution in China, edited by Mun S Ho and Chris P Nielsen. Cambridge, MA: MIT Press. Publisher's VersionAbstract

An interdisciplinary, quantitative assessment of the health and economic costs of air pollution in China, and of market-based policies to build environmental protection into economic development.

China's historic economic expansion is driven by fossil fuels, which increase its emissions of both local air pollutants and greenhouse gases dramatically. Clearing the Air is an innovative, quantitative examination of the national damage caused by China's degraded air quality, conducted in a pathbreaking, interdisciplinary U.S.-China collaboration. Its damage estimates are allocated by sector, making it possible for the first time to judge whether, for instance, power generation, transportation, or an unexpected source such as cement production causes the greatest environmental harm. Such objective analyses can reset policy priorities.

Clearing the Air uses this information to show how appropriate "green" taxes might not only reduce emissions and health damages but even enhance China's economic growth. It also shows to what extent these same policies could limit greenhouse gases, suggesting that wealthier nations have a responsibility to help China build environmental protection into its growth.

Clearing the Air is written for diverse readers, providing a bridge from underlying research to policy implications, with easily accessible overviews of issues and summaries of the findings for nonspecialists and policymakers followed by more specialized, interlinked studies of primary interest to scholars. Taken together, these analyses offer a uniquely integrated assessment that supports the book's economic and policy recommendations.

Y. Zhou, Jonathan I Levy, James K Hammitt, and John S Evans. 2003. “Estimating population exposure to power plant emissions using CALPUFF: A case study in Beijing, China.” Atmospheric Environment, 37, 6, Pp. 815-826. Publisher's VersionAbstract
Epidemiological studies have shown a significant association between ambient particulate matter (PM) exposures and increased mortality and morbidity risk. Power plants are significant emitters of precursor gases of fine particulate matter. To evaluate the public health risk posed by power plants, it is necessary to evaluate population exposure to different pollutants. The concept of intake fraction (the fraction of a pollutant emitted that is eventually inhaled or ingested by a population) has been proposed to provide a simple summary measure of the relationship between emissions and exposure. Currently available intake fraction estimates from developing countries used models that look only at the near field impacts, which may not capture the full impact of a pollution source. This case study demonstrated how the intake fraction of power plant emissions in China can be calculated using a detailed long-range atmospheric dispersion model—CALPUFF. We found that the intake fraction of primary fine particles is roughly on the order of 10−5, while the intake fractions of sulfur dioxide, sulfate and nitrate are on the order of 10−6. These estimates are an order of magnitude higher than the US estimates. We also tested how sensitive the results were to key assumptions within the model. The size distribution of primary particles has a large impact on the intake fraction for primary particles while the background ammonia concentration is an important factor influencing the intake fraction of nitrate. The background ozone concentration has a moderate impact on the intake fraction of sulfate and nitrate. Our analysis shows that this approach is applicable to a developing country and it provides reasonable population exposure estimates.
2007. Clearing the air: The health and economic damages of air pollution in China. Cambridge, MA: MIT Press. Publisher's VersionAbstract

An interdisciplinary, quantitative assessment of the health and economic costs of air pollution in China, and of market-based policies to build environmental protection into economic development.

China's historic economic expansion is driven by fossil fuels, which increase its emissions of both local air pollutants and greenhouse gases dramatically. Clearing the Air is an innovative, quantitative examination of the national damage caused by China's degraded air quality, conducted in a pathbreaking, interdisciplinary U.S.-China collaboration. Its damage estimates are allocated by sector, making it possible for the first time to judge whether, for instance, power generation, transportation, or an unexpected source such as cement production causes the greatest environmental harm. Such objective analyses can reset policy priorities.

Clearing the Air uses this information to show how appropriate "green" taxes might not only reduce emissions and health damages but even enhance China's economic growth. It also shows to what extent these same policies could limit greenhouse gases, suggesting that wealthier nations have a responsibility to help China build environmental protection into its growth.

Clearing the Air is written for diverse readers, providing a bridge from underlying research to policy implications, with easily accessible overviews of issues and summaries of the findings for nonspecialists and policymakers followed by more specialized, interlinked studies of primary interest to scholars. Taken together, these analyses offer a uniquely integrated assessment that supports the book's economic and policy recommendations.

1998. Energizing China: Reconciling Environmental Protection and Economic Growth. Cambridge, MA: HUCE/Harvard University Press. Publisher's VersionAbstract

As China develops its booming, fossil fuel-powered economy, is it taking lessons from the history of Western industrialization and the unforeseen environmental harms that accompanied it? Given the risks of climate change, is there an imperative, shared responsibility to help China respond to the environmental effects of its coal dependence? By linking global hazards to local air pollution concerns—from indoor stove smoke to burgeoning ground-level ozone—this volume of eighteen studies seeks integrated strategies to address simultaneously a range of harmful emissions. Counterbalancing the scientific inquiry are key chapters on China’s unique legal, institutional, political, and cultural factors in effective pollution control.

Energizing China, the stage-setting publication of an ongoing program of Harvard–China research collaboration, is distinguished by its conceptual breadth and spirit of exchange. Its contributors include twenty-two Western and seventeen Chinese scholars with a disciplinary reach that includes science, public health, engineering, economics, public policy, law, business, and China studies.

Chris P Nielsen, Mun S Ho, Yu Zhao, Yuxuan Wang, Yu Lei, and Jing Cao. 2013. “Summary: Sulfur Mandates and Carbon Taxes for 2006-2010.” In Clearer Skies Over China: Reconciling Air Quality, Climate, and Economic Goals, Pp. 59-102. Cambridge, MA: MIT Press. Publisher's VersionAbstract

A groundbreaking U.S.–Chinese inquiry into the effects of recent air pollution controls and prospective carbon taxes on China's economy and environment.

China's carbon dioxide emissions now outstrip those of other countries and its domestic air quality is severely degraded, especially in urban areas. Its sheer size and its growing, fossil-fuel-powered economy mean that China's economic and environmental policy choices will have an outsized effect on the global environmental future. Over the last decade, China has pursued policies that target both fossil fuel use and atmospheric emissions, but these efforts have been substantially overwhelmed by the country's increasing energy demands. With a billion citizens still living on less than $4,000 per year, China's energy and environmental policies must be reconciled with the goals of maintaining economic growth and raising living standards. This book, a U.S.–Chinese collaboration of experts from Harvard and Tsinghua University, offers a groundbreaking integrated analysis of China's economy, emissions, air quality, public health, and agriculture. It first offers essential scientific context and accessible summaries of the book's policy findings; it then provides the underlying scientific and economic research. These studies suggest that China's recent sulfur controls achieved enormous environmental health benefits at unexpectedly low costs. They also indicate that judicious implementation of carbon taxes could reduce not only China's carbon emissions but also its air pollution more comprehensively than current single-pollutant policies, all at little cost to economic growth. Bingjiang Liu and Jiming Hao. 2007. “Local population exposure to pollutants from the electric power sector.” In Clearing the air: The health and economic damages of air pollution in China, edited by Mun S Ho and Chris P Nielsen. Cambridge, MA: MIT Press. Publisher's VersionAbstract An interdisciplinary, quantitative assessment of the health and economic costs of air pollution in China, and of market-based policies to build environmental protection into economic development. China's historic economic expansion is driven by fossil fuels, which increase its emissions of both local air pollutants and greenhouse gases dramatically. Clearing the Air is an innovative, quantitative examination of the national damage caused by China's degraded air quality, conducted in a pathbreaking, interdisciplinary U.S.-China collaboration. Its damage estimates are allocated by sector, making it possible for the first time to judge whether, for instance, power generation, transportation, or an unexpected source such as cement production causes the greatest environmental harm. Such objective analyses can reset policy priorities. Clearing the Air uses this information to show how appropriate "green" taxes might not only reduce emissions and health damages but even enhance China's economic growth. It also shows to what extent these same policies could limit greenhouse gases, suggesting that wealthier nations have a responsibility to help China build environmental protection into its growth. Clearing the Air is written for diverse readers, providing a bridge from underlying research to policy implications, with easily accessible overviews of issues and summaries of the findings for nonspecialists and policymakers followed by more specialized, interlinked studies of primary interest to scholars. Taken together, these analyses offer a uniquely integrated assessment that supports the book's economic and policy recommendations. Scott A. Venners, Binyan Wang, Jiatong Ni, Yongtang Jin, Jianhua Yang, Zhian Fang, and Xiping Xu. 2001. “Indoor air pollution and respiratory health in urban and rural China.” International Journal of Occupational and Environmental Health , 7, 3, Pp. 173-181. Publisher's VersionAbstract During the summer of 1999, information about respiratory health outcomes and relevant covariates was collected from 3,709 Chinese adults in Beijing, Anqing City, and rural communities in Anqing Prefecture. Indoor PM10 and SO2 were measured in a random sample of selected households. Using logistic regression and controlling for important covariates (excluding PM10 and SO2) and familial intraclass correlation, highly significant differences were found between study areas in the prevalences of chronic cough, chronic phlegm, wheeze, and shortness of breath, but not physician-diagnosed asthma. Generally, the lowest prevalence of respiratory symptoms was observed in Anqing City, a higher prevalence in rural Anqing, and the highest prevalence in Beijing. Median indoor concentrations of PM10 were similar in Anqing City (239 microg/m3) and rural Anqing (248 microg/m3), but much higher in Beijing (557 microg/m3). Median indoor concentrations of SO2 were similar in all three areas (Beijing: 14 microg/m3, Anqing City: 25 microg/m3, rural Anqing: 20 microg/m3). Hong Wang and John Mullahy. 2006. “Willingness to pay for reducing fatal risk by improving air quality: A contingent valuation study in Chongqing, China.” Science of the Total Environment, 367, Pp. 50-57. Publisher's VersionAbstract In China, 76% of all energy comes from coal consumption, which is the major cause of air pollution. One of the major barriers to developing sound policies for controlling air pollution is the lack of information related to the value of the health consequences of air pollution. We conducted a willingness-to-pay (WTP) study using contingent valuation (CV) methods in Chongqing, China to estimate the economic value of saving one statistical life through improving air quality. A sample of 500 residents was chosen based on multistage sampling methods. A face-to-face household interview was conducted using a series of hypothetical, open-ended scenarios followed by bidding game questions designed to elicit the respondents' WTP for air pollution reduction. The Two-Part Model was used for estimations. The results show that 96% of respondents were able to express their WTP. Their mean annual income is$490. Their WTP to save one statistical life is $34,458. Marginal increases for saving one statistical life is$240 with 1 year age increase, $14,434 with 100 yuan monthly income increase, and$1590 with 1 year education increase. Unlike developed country, clean air may still be considered as a “luxury” good in China based on the estimation of income elasticity.

Yu Lei. 2013. “Benefits to Human Health and Agricultural Productivity of Reduced Air Pollution.” In Clearer Skies Over China: Reconciling Air Quality, Climate, and Economic Goals, Pp. 291-328. Cambridge, MA: MIT Press. Publisher's VersionAbstract

A groundbreaking U.S.–Chinese inquiry into the effects of recent air pollution controls and prospective carbon taxes on China's economy and environment.

China's carbon dioxide emissions now outstrip those of other countries and its domestic air quality is severely degraded, especially in urban areas. Its sheer size and its growing, fossil-fuel-powered economy mean that China's economic and environmental policy choices will have an outsized effect on the global environmental future. Over the last decade, China has pursued policies that target both fossil fuel use and atmospheric emissions, but these efforts have been substantially overwhelmed by the country's increasing energy demands. With a billion citizens still living on less than \$4,000 per year, China's energy and environmental policies must be reconciled with the goals of maintaining economic growth and raising living standards.

This book, a U.S.–Chinese collaboration of experts from Harvard and Tsinghua University, offers a groundbreaking integrated analysis of China's economy, emissions, air quality, public health, and agriculture. It first offers essential scientific context and accessible summaries of the book's policy findings; it then provides the underlying scientific and economic research. These studies suggest that China's recent sulfur controls achieved enormous environmental health benefits at unexpectedly low costs. They also indicate that judicious implementation of carbon taxes could reduce not only China's carbon emissions but also its air pollution more comprehensively than current single-pollutant policies, all at little cost to economic growth.

2016 Dec 07

# Long-Term Trend and Spatial Pattern of PM2.5-Induced Premature Mortality in China

3:30pm to 4:45pm

## Location:

Pierce Hall 100F, 29 Oxford St., Cambridge, MA

# Shuxiao Wang

Professor, School of Environment, Tsinghua University
Alumna (Postdoctoral Fellow and Visiting Scholar) and Collaborator, Harvard-China Project

# Haikun Wang

Professor, School of Atmospheric Sciences, Nanjing University
Alumnus (Visiting Scholar) and Collaborator, Harvard-China Project


text:
ayooshkathuria/pytorch-yolo-v3

A PyTorch implementation of the YOLO v3 object detection algorithm
359 次浏览

A PyTorch implementation of a YOLO v3 Object Detector

[UPDATE] : This repo serves as a driver code for my research. I just graduated college, and am very busy looking for research internship / fellowship roles before eventually applying for a masters. I won't have the time to look into issues for the time being. Thank you.

This repository contains code for a object detector based on YOLOv3: An Incremental Improvement, implementedin PyTorch. The code is based on the official code of YOLO v3, as well as a PyTorch port of the original code, by marvis. One of the goals of this code is to improve upon the original port by removing redundant parts of the code (The official code is basically a fully blown deep learning library, and includes stuff like sequence models, which are not used in YOLO). I've also tried to keep the code minimal, and document it as well as I can.

Tutorial for building this detector from scratch

If you want to understand how to implement this detector by yourself from scratch, then you can go through this very detailed 5-part tutorial series I wrote on Paperspace. Perfect for someone who wants to move from beginner to intermediate pytorch skills.

Implement YOLO v3 from scratch

As of now, the code only contains the detection module, but you should expect the training module soon. :)

Requirements

1. Python 3.5
2. OpenCV
3. PyTorch 0.4

Using PyTorch 0.3 will break the detector.

Running the detector

On single or multiple images

Clone, and cd into the repo directory. The first thing you need to do is to get the weights file This time around, for v3, authors has supplied a weightsfile only for COCO here, and place

the weights file into your repo directory. Or, you could just type (if you're on Linux)

wget https://pjreddie.com/media/files/yolov3.weights
python detect.py --images imgs --det det

--images flag defines the directory to load images from, or a single image file (it will figure it out), and --det is the directory to save images to. Other setting such as batch size (using --bs flag) , object threshold confidence can be tweaked with flags that can be looked up with.

python detect.py -h

You can change the resolutions of the input image by the --reso flag. The default value is 416. Whatever value you chose, rememeber it should be a multiple of 32 and greater than 32. Weird things will happen if you don't. You've been warned.

python detect.py --images imgs --det det --reso 320

On Video

For this, you should run the file, video_demo.py with --video flag specifying the video file. The video file should be in .avi format since openCV only accepts OpenCV as the input format.

python video_demo.py --video video.avi

Tweakable settings can be seen with -h flag.

Speeding up Video Inference

To speed video inference, you can try using the video_demo_half.py file instead which does all the inference with 16-bit half precision floats instead of 32-bit float. I haven't seen big improvements, but I attribute that to having an older card (Tesla K80, Kepler arch). If you have one of cards with fast float16 support, try it out, and if possible, benchmark it.

On a Camera

Same as video module, but you don't have to specify the video file since feed will be taken from your camera. To be precise, feed will be taken from what the OpenCV, recognises as camera 0. The default image resolution is 160 here, though you can change it with reso flag.

python cam_demo.py

You can easily tweak the code to use different weightsfiles, available at yolo website

NOTE: The scales features has been disabled for better refactoring.

Detection across different scales

YOLO v3 makes detections across different scales, each of which deputise in detecting objects of different sizes depending upon whether they capture coarse features, fine grained features or something between. You can experiment with these scales by the --scales flag.

python detect.py --scales 1,3

ayooshkathuria
• 最近提交：2019-07-30
• 创建时间：2018-04-06


text:
# Calculate $\pi$ to an accuracy of 5 decimal places?

In this message at point 18 I saw following programming question:

Given that $\pi$ can be estimated using the function $4(1 – 1/3 + 1/5 – 1/7 + \ldots)$ with more terms giving greater accuracy, write a function that calculates Pi to an accuracy of 5 decimal places.

So I know how to implement the given function and how to choose how "far" I should calculate, but how can I tell when I've reached the "accuracy of 5 decimal places" ?

-

## migrated from programmers.stackexchange.comAug 30 '12 at 16:14

This question came from our site for professional programmers interested in conceptual questions about software development.

That converges quite slowly, I believe; Wikipedia states it'll take 500,000 iterations to get to 5 places. You'd have to read the linked paper to find out how they determined that though. :-P – Martijn Pieters Aug 30 '12 at 9:07
This is a math question – Simon Aug 30 '12 at 14:06
Just use a constant. The value of PI to 5 decimal places is known. In many cases its already a math constant. The programming question seems to ignore this fact. – Ramhound Aug 30 '12 at 14:35
@Ramhound - That's because the programming question is a sample interview question. Of course in your daily work you'd use a built-in or define your own. That wasn't the point; any idiot can hard-code the desired result of a single trial into a method. The point was to determine if you can think your way through the desired algorithm. – KeithS Aug 30 '12 at 15:44
What do you mean when you say "I know... how to choose how 'far' I should calculate"? Because that's precisely the question you are asking. – Sridhar Ramesh Aug 30 '12 at 17:16

The series you wrote is an Alternating series. The alternating series test says that for such a series, the error in the approximation is less than the absolute value of the first missing term.

In other words, if the last term you have is of the form $\pm \frac{1}{2n+1}$, then your approximation is good within $\frac{1}{2n+3}$. To be sure that this is accurate to the 5th digit, you need

$$\frac{1}{2n+3} \leq 0.00001$$

-
You are correct about the alternating series test and the error bound. One has to be careful by what is meant by accurate to 5 decimal places (which may be more an English problem than a math one). If $\pi$ were of the form $3.1416000000001233144\ldots$ you could have quite a small error change the fifth decimal point. Yes, you would have to be really unlucky. – Ross Millikan Sep 4 '12 at 15:53

You alternate adding and subtracting decreasing values. So the next value is an upper bound of the difference between your current result and Pi.

-
Now it seems obvious, thanks... – pgras Aug 30 '12 at 9:36

You can just keep going until the decimal places you are interested in don't change for two terms. Since we add and subtract alternately, and subsequent terms have less effect, you can be sure that the decimal places will never change if they don't for two turns.

Note that this series for pi is very slow!

-

4 * 1 / 400000 = 0.00001. Any term smaller than that will not contribute to the first 5 decimal places of the accumulated sum.

So in pseudo-code:

val = 0;
for d = 1; d <= 400000; d += 4
val += 1 / d
val -= 1 / (d+2)
return val*4

-
-1 Incomplete. You need to show that the terms smaller than 1E-5 don't sum to more than 1E-5. In fact, actually it's even more complicated than that, because the answer should be correctly rounded. You also potentially have loss of significance due to adding from the largest elements in the series rather than from the smallest. – Peter Taylor Aug 30 '12 at 12:46

The iteration should be simple; it's how you know when you're done, without knowing the answer, that's trickier. Basically, if you need to know the answer to 5 decimal places, then stop as soon as the 5th decimal place hasn't changed in some arbitrary number of trials.

A more elegant way (not requiring you to multiply by 4 after every step to ensure the precision of the final number is within the epsilon) is to quit as soon as you reach a value that does not change the least significant digit of the decimal value that would produce the correct value of Pi. Pi to 5 decimals is 3.14159. Divided by 4 (producing the necessary sum of the infinite series), that's .7853975. This is what you have to get to. Therefore, the largest fraction that can be summed to the series that will not affect the precision is 1E-8 (one hundred millionth).

So, the ending point is the iteration N at which $|\dfrac{-1}{2n-1} + \dfrac{1}{2n+1}| < .00000001$, so that at the end of the iteration (one iteration being a subtraction and an addition), the series sum has not changed by a greater degree than the epsilon. By inspection, we see that the sum of the two fractions will be negative, so:

$\dfrac{1}{2n+1} - \dfrac{1}{2n-1} = -0.00000001$

$\dfrac{2n-1}{(2n+1)(2n-1)} - \dfrac{2n+1}{(2n+1)(2n-1)} = -1*10^{-8}$

$\dfrac{(2n-1)-(2n+1)}{(2n+1)(2n-1)} = -1*10^{-8}$

$\dfrac{-2}{4n^2-1} = -1*10^{-8}$

$-2 = (-1*10^{-8})(4n^2-1)$

$\dfrac{-2}{-1*10^{-8}} = 4n^2-1$ <-- from here you can pretty much plug in any needed precision

$2*10^{8} = 4n^2-1$

$200000001/4 = n^2$

$50000000.25 = n^2$

$n > 7071$

Plugging this back in to check, we get $\dfrac{1}{2(7072)+1} - \dfrac{1}{2(7072)-1} = \dfrac{1}{14145} - \dfrac{1}{14143} = -0.9997*10^{-8}$ which is less significant than $-1*10^{-8}$.

So, it should take 7072 iterations, at least, of subtracting the inverse of an odd natural number, then adding the next smaller odd inverse, to arrive at a sum that will produce pi to the necessary precision. In fact, it may actually take many more to produce a value that rounds correctly to the necessary number of decimal places; if you simply truncate to the needed sig figs, this is the answer.

-

What you talk about is usually called Taylor series. Calculation is simple. Just add more terms until you reach the point, that terms don't add more accuracy for your desired precision.

-


text:
# How to solve this linear program?

I was given the following linear program with the supposed answers to be $x_1 = 45/103$, $x_2 = 27/103$, $x_3 = 31/103$. Howerver, I tried to solve it using the Simplex Algorithm with no success, online LP solvers also couldn't seem to find the solutions, but checking the answers work with the LP. Could someone please show me how to solve this?

$min$ $z,$ $subject$ $to$
$-2x_1 + x_2 + 3x_3 \leq z$
$x_1 - 4x_2 + 3x_3 \leq z$
$3x_1 + 3x_2 - 6x_3 \leq z$
$x_1 + x_2 + x_3 = 1$
$x_1,x_2,x_3 \geq 0$

I converted the above to

$Minimize$ $p = z$ $subject$ $to$
$z + 2x_1 - x_2 - 3x_3 \geq 0$
$z - x_1 + 4x_2 - 3x_3 \geq 0$
$z - 3x_1 - 3x_2 + 6x_3 \geq 0$
$x_1 + x_2 + x_3 = 1$

• Where does "$x \geq 0$" come from? – Symeof Nov 9 '15 at 8:49
• it basically says x1, x2, x3 are all greater than 0 – gametheorybeginner Nov 9 '15 at 8:50
• then try to add these 3 equations to the system – Michael Medvinsky Nov 9 '15 at 9:00
• I edited the equations to make them looking a little better (Ii hope). Is this OK for you ? – Claude Leibovici Nov 9 '15 at 9:03
• sure, I added in the constraints but it still didnt work for me. – gametheorybeginner Nov 9 '15 at 9:03

Multiply the first equation by $45$, second by $27$, third by $31$ and add them up:

$103z\geq 30x_1+30x_2+30x_3=30$

Hence $z_{min}={30\over103}$

After that just solve the system of equations letting each of the three equations equal to $z_{min}$.

• this is not valid because you are basically solving it with the answer given. I want to get the answers from scratch... – gametheorybeginner Nov 9 '15 at 9:03
• No. I did not solve from answer given. What you want is three multipliers $a,b,c$ such that the linear combination of the equations gives the same ratio over $x_1,x_2,x_3$. Note that the third equation has first two term equal, so you know the first two equation must have multipliers of ratio $5:3$ as $-2+x=1-4x$ gives $x={3\over5}$. After that you add $5(-2,1,3)+3(1,-4,3)$ to get $(-7,-7,24)$. Then you are finding $-7+3x=24-6x$ giving you $x={31\over9}$. So you know the ratio of the multipliers are $45:27:31$ – cr001 Nov 9 '15 at 9:08
• thanks for the explanation, but do you know if it is possible to use the simplex method on this problem? – gametheorybeginner Nov 9 '15 at 9:12
• Yes it is but you would still need to find the linear combination to make a multiple of $(x_1+x_2+x_3)$. – cr001 Nov 9 '15 at 9:17

I know this is old, but you could only add Z as a new variable inside your simplex formulation and let:

X1 = Z

and just change all the other variables you had as: Xn = Xn+1 So you would have this system of equations:

Min P = X1

S.T:

X1 +2X2 -X3 -3X4 >= 0

X1 -X2 +4X3 -3X4 >= 0

X1 -3X2 -3X3 +6X4 >= 0

X2 + X3 +X4 = 1

Solve using Two Phase method or Big M method (You could multiply all >= 0 constraints by -1 to simplify the problem) and then you just change back your variables:

Z = X1

Xn = Xn-1

Solving this problem gets you Z = 2/7 if I recall.


text:
# Trapezoid Perimeter Calculator

Created by Davide Borchia
Reviewed by Komal Rafay
Last updated: Mar 14, 2022

A trapezoid is a quadrangular shape, part of a broad family of convex quadrilaterals: use our trapezoid perimeter calculator to find its perimeter using any possible combinations of parameters!

## What is a trapezoid?

A trapezoid is a quadrilateral convex shape:

• Quadrilateral means that it has four sides (and four angles); and

• Convex means that it contains every segment with initial and final points inside the shape.

Trapezoids have at least a pair of parallel sides. The other sides can be either perpendicular or tilted with respect to the bases.

## The elements of a trapezoid

A characteristic set of elements identifies a trapezoid. Starting from the sides, we have:

• Two bases: the parallel sides;
• Two legs: the oblique sides;

It is possible to identify four angles. The total sum is always $360\ \degree$, which is equally divided between angles associated to the same side (complementary angles), which sum to $180\ \degree$.

⚠ Don't mistake a trapezoid for a trapezium: the latter one is a quadrilateral without parallel sides!

It is important to identify one last element, the height of the trapezoid, the distance between the bases. It will be helpful in the calculations for the perimeter.

## How to calculate the perimeter of a trapezoid

The formula of a trapezoid's perimeter is extremely simple:

$P=a+b+c+d$

Where:

• $P$ is the perimeter;
• $a$ and $b$ the parallel sides (bases); and
• $c$ and $d$ the oblique sides.

But rarely, you will have all the sides. You may have combinations of sides and angles, and sometimes the situation may also look pretty dire until trigonometry comes to our help. Let's check the possible combinations you may find!

#### Two sides, an angle, and a base

With this combination you can find easily the height $h$ of the trapezoid with the formulas:

$h=c\cdot\sin{\alpha}$

or

$h=d\cdot\sin{\delta}$

Once you know the value of $h$, you can compute the value of the other angle, and then the projection of the sides on the base $a$, which summed equal the difference of the bases:

$a-b=c\cdot\cos{\alpha}+d\cdot\cos{\delta}$

Rearranging this formula gives you the missing base!

#### Two sides, a base, and the height

With this combination, we can first find the values of the projections of the sides on the base $a$ using the reliable Pythagorean theorem. Once you find them, you can either:

• Add them to the base $b$ to find the base $a$;
• Subtract them from the base $a$ to find the base $b$.

You have all the elements to feed into the trapezoid perimeter formula now!

#### Two angles associated to opposite sides, the height and a base

This case is similar to the previous one; knowing the height and the angles (remember that they satisfy the identities $\alpha+\beta=180\ \degree$ and $\gamma+\delta=180\ \degree$), you can find the sides first and then the projections on the base $a$. From there, you can find the value of the other base.

#### The two bases, a side, and the relative angle

This combination is our favorite! By subtracting the two bases and the projection of the side on $a$, we can find the other projection. From here, with the height calculated from the side and angle, we can find the other side.

⚠ Using this combination, you will see the perimeter field in our calculator greyed out. You can't use our trapezoid perimeter calculator in reverse because of a slightly more complex formula running in the background. 🙄 You can try it in reverse in the other cases, however!

## How to use our trapezoid perimeter calculator

Using our trapezoid perimeter calculator is straightforward! If you have the values of each side of the polygon, insert them in the respective field, and you'll get the value of the perimeter.

🙋 You can use our calculators in reverse too! If you have the perimeter but one of the sides is missing, insert the value anyway, we will give you the answer. 😀

If you don't have the sides but some other combination of sides, angles, or height, click on advanced mode, you will then see all of the other variables. Choose the ones you need and insert your values there!

## Other trapezoid calculators you may find useful

Apart from the trapezoid perimeter calculator, we have many more calculators that will help you with your geometrical problems (only those, though!): try our:

## FAQ

### How to calculate the perimeter of a trapezoid?

The perimeter of a trapezoid formula is:
P = a + b + c + d
where P is the perimeter, a and b are the bases, while c and d are the sides. There are many ways to find the values of those elements: discover them on omnicalculator.com!

### What is the perimeter of a trapezoid with sides c=4 and d=3, base a=10 and α=30°?

First, you have to calculate the height of the trapezoid, using:
h = c * sin(α) = 4 * sin(30°) = 2.

Now using the Pythagorean theorem we can find the values of the projections of the sides on the base a:
sqrt(c² - h²) = sqrt(16 - 4) = 3.46 and sqrt(d² - h²) = 2.24.

Subtract these values from the base a to find b:
b = a - sqrt(c² - h²) - sqrt(d² - h²) = 10 - 3.46 - 2.24 = 4.3
and then the perimeter:
P = 10 + 4 + 3 + 4.3 = 21.3

### Can you find the perimeter of a trapezoid knowing only the angles and a base?

No. This combination of parameters would leave too much freedom to the remaining elements of the trapezoid: the other base's length would be able to vary as well as the angles of the trapezoid. It is necessary to know at least an angle in addition to these elements.

### How do I find the perimeter of an isosceles trapezoid?

In the case of an isosceles trapezoid, you can find the perimeter just by knowing the bases and one side: the two sides are identical! The formula changes slightly:
P = a + b + 2c
where P is the perimeter, a and b the bases, and c the oblique side

Davide Borchia
a (base)
in
b (base)
in
c (side)
in
d (side)
in
Perimeter
Perimeter (P)
in
People also viewed…

### Area of a circle

The area of a circle calculator will compute the surface of a circle using a radius or a diameter.

### Free fall

Our free fall calculator can find the velocity of a falling object and the height it drops from.

### Grams to cups

The grams to cups calculator converts between cups and grams. You can choose between 20 different popular kitchen ingredients or directly type in the product density.

### Unit rate

The unit rate calculator is here to give you your fraction's equivalent with one in the denominator (i.e. unit rate).


text:
[ bsd3, control, library, monad ] [ Propose Tags ]

Memoization monad transformer supporting most of the standard monad transformers and a range of memoization cache types: from default pure maps to extremely fast mutable vectors

1) Add Control.Monad.Memo.memo combinator at the point when memoization is required (i.e. recursive call)

import Control.Monad.Memo

fibm 0 = return 0
fibm 1 = return 1
fibm n = do
n1 <- memo fibm (n-1)
n2 <- memo fibm (n-2)
return (n1+n2)

2) Use approprite *eval* or *run* function to evaluate resulting MonadMemo monad:

startEvalMemo (fibm 100)

See detailed description and examples: Control.Monad.Memo

Versions 0.1.0, 0.1.1, 0.2.0, 0.3.0, 0.4.0, 0.4.1, 0.5.0, 0.5.1 CHANGES array (>=0.3), base (>=3.0 && <=5.0), containers (>=0.3), primitive (>=0.3), transformers (>=0.2), transformers-compat (>=0.3), vector (>=0.7) [details] BSD-3-Clause Eduard Sergeev eduard.sergeev@gmail.com Control, Monad https://github.com/EduardSergeev/monad-memo head: git clone https://github.com/EduardSergeev/monad-memo.gitthis: git clone https://github.com/EduardSergeev/monad-memo.git(tag 0.5.0) by EduardSergeev at Fri Aug 31 06:16:54 UTC 2018 LTSHaskell:0.4.1, NixOS:0.5.1, Stackage:0.5.1 3030 total (131 in the last 30 days) (no votes yet) [estimated by rule of succession] λ λ λ Docs available Last success reported on 2018-08-31 Hackage Matrix CI

#### Maintainer's Corner

For package maintainers and hackage trustees

[back to package description]

## Memoization

Memoization is a well known way to speed up function evaluation by caching previously calculated results and reusing them whenever a memoized function is needed to be evaluated with the same arguments again. It is usually associated with dynamic programming techiques.

## Overview

Even though it is possible to manually add memoization to the code which would benefit from it, this ad-hoc approach has usual ad-hoc drawbacks: code pollution, bugs, resistance to changes. This package however encapsulates the underlying plumbing behind its simple monadic interface MonadMemo with a single combinator memo which, when applied to monadic function, turns it into "memoized" one.

The package offers various implementation of MonadMemo (which differs in terms of performance and requirements) and it is possible to choose/change the implementation without affecting the main function code. The range of supported implementations "out of box" is limited by the range of containers provided by the standard packages installed by Haskel Platform: from default pure "fit them all" Data.Map to very fast but limiting vector. It is also possible to plug-in a custom container (from a third-party library) and run existing monadic code with it.

The default implementation of MonadMemo is also monad transformer so it can be "mixed" with other monads. The package also provides the "memoized" versions of most standard monads found in mtl.

## Example of usage

A clasic example of function which greatelly benefits from memoization is a recursively defined Fibonacci number function. A plain version of this function can be written in the following way:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

which is very inefficient (impractical for n>40).

We can rewrite this definition as a monad:

fibm :: Monad m => Integer -> m Integer
fibm 0 = return 0
fibm 1 = return 1
fibm n = do
f1 <- fibm (n-1)
f2 <- fibm (n-2)
return (f1+f2)

and even run it with Identity monad with identical inefficiency:

evalFibmId :: Integer -> Integer
evalFibmId = runIdentity . fibm

But all we need to do to make this function "computable" for reasonable argument is to add memoization for both recursive branches with memo combinator:

fibm :: (MonadMemo Integer Integer m) => Integer -> m Integer
fibm 0 = return 0
fibm 1 = return 1
fibm n = do
f1 <- memo fibm (n-1)
f2 <- memo fibm (n-2)
return (f1+f2)

then, to evaluate it with default Data.Map based memoization cache we use the following "eval*" function:

evalFibm :: Integer -> Integer
evalFibm = startEvalMemo . fibm

Now the range of the arguments it can handle is limited only by Integer computation complexity and stack memory limit.

## More Examples

### Slightly more complicated recursive function

Well known Ackerman function is a two arguments function. To memoize two argument function for2 combinator can be used, giving the following generic code:

ackm :: (Num n, Ord n, MonadMemo (n, n) n m) => n -> n -> m n
ackm 0 n = return (n+1)
ackm m 0 = for2 memo ackm (m-1) 1
ackm m n = do
n1 <- for2 memo ackm m (n-1)    -- 'for2' adapts 'memo' for 2-argument 'ackm'
for2 memo ackm (m-1) n1

evalAckm :: (Num n, Ord n) => n -> n -> n
evalAckm n m = startEvalMemo $ackm n m  ### Mutually recursive function memoization This example is taken from paper "Monadic Memoization Mixins" by Daniel Brown and William R. Cook Given the following mutually recursive function definitions: -- 'f' depends on 'g' f :: Int -> (Int,String) f 0 = (1,"+") f (n+1) =(g(n,fst(f n)),"-" ++ snd(f n)) -- 'g' depends on 'f' g :: (Int, Int) -> Int g (0, m) = m + 1 g (n+1,m) = fst(f n)-g(n,m)  How can we memoize both functions? Lets try to just add memo for both functions: -- WRONG: Will NOT compile! fm 0 = return (1,"+") fm (n+1) = do fn <- memo fm n gn <- memo gm (n , fst fn) return (gn , "-" ++ snd fn) gm (0,m) = return (m+1) gm (n+1,m) = do fn <- memo fm n gn <- memo gm (n,m) return$ fst fn - gn

GHC complains:

"Occurs check: cannot construct the infinite type: t = (t, v)
Expected type: t

Inferred type: (t, v)"

which is understandable since we are trying to use the same cache for storing "key-value" pairs of the functions of different types (fm :: Int -> m (Int,String) and gm :: (Int, Int) -> m Int). Obviously, to cache both function we will need two caches (even if the types of the functions were identical, it's not very good idea to share the same cache). And this is precisely what we have to do - use two memoization caches! The way to achieve it is to use two MemoT monad transformers one nested in another:

-- Memo-cache for 'fm'
type MemoF = MemoT Int (Int,String)
-- Memo-cache for 'gm'
type MemoG = MemoT (Int,Int) Int

-- | Combined stack of caches (transformers)
-- Stacks two 'MemoT' transformers in one monad to be used in both 'gm' and 'fm' monadic functions
type MemoFG = MemoF (MemoG Identity)

NB As usually with Haskell it isn't necessary to specify types here (or restrict them to MemoT combinations for the given example).

Then, a little bit of complication, since we use two caches now (one from the current monad transformer and another from the next, nested in the current) we need to use memol_X_ set of functions: memol0, memol1 etc. Where X specifies "sequential number" of the transformer in stack for a given cache (starting from the current). Here we use the current (0) and the next (1) for fm and gm respectively:

fm :: Int -> MemoFG (Int,String)
fm 0 = return (1,"+")
fm (n+1) = do
fn <- memol0 fm n
gn <- memol1 gm (n , fst fn)
return (gn , "-" ++ snd fn)

gm :: (Int,Int) -> MemoFG Int
gm (0,m) = return (m+1)
gm (n+1,m) = do
fn <- memol0 fm n
gn <- memol1 gm (n,m)
return $fst fn - gn evalAll = startEvalMemo . startEvalMemoT -- | Function to run 'fm' computation evalFm :: Int -> (Int, String) evalFm = evalAll . fm -- | Function to run 'gm' computation evalGm :: (Int,Int) -> Int evalGm = evalAll . gm  In fact we can also define 'gm' function in curried form: fm2 :: Int -> MemoFG (Int,String) fm2 0 = return (1,"+") fm2 n = do fn <- memol0 fm2 (n-1) gn <- for2 memol1 gm2 (n-1) (fst fn) return (gn , "-" ++ snd fn) -- 2-argument function now gm2 :: Int -> Int -> MemoFG Int gm2 0 m = return (m+1) gm2 n m = do fn <- memol0 fm2 (n-1) gn <- for2 memol1 gm2 (n-1) m -- 'for2' adapts 'memol1' for 2-argument gm2 return$ fst fn - gn

evalFm2 :: Int -> (Int, String)
evalFm2 = evalAll . fm2

evalGm2 :: Int -> Int -> Int
evalGm2 n m = evalAll $gm2 n m  ### Combining MemoT with other monads Being monad transformer, memoization monad can be combined with most of existing monads. Here we mix it with MonadWriter: fibmw :: (Num n, MonadWriter String m, MonadMemo n n m) => n -> m n fibmw 0 = tell "0" >> return 0 fibmw 1 = tell "1" >> return 1 fibmw n = do f1 <- memo fibmw (n-1) f2 <- memo fibmw (n-2) tell$ show n
return (f1+f2)

-- To run combined monad we need to sequence both 'run' functions:
evalFibmw :: Integer -> (Integer, String)
evalFibmw = startEvalMemo . runWriterT . fibmw

res = evalFibmw 6  -- > produces (8,"1021310241021351021310246")

## Custom pure cache container

From monad-memo version 0.3.0 it is possible to replace default Data.Map with another (more efficient?) implementation of internal cache-container as long as there is an instance of Data.MapLike defined for this container. The package currently defines these instances for Data.Map and Data.IntMap only.

For instance, should we decide to use unordered-containers all we need to do is to define the following instance for our container:

import Data.Hashable
import qualified Data.HashMap.Strict as H

instance (Eq k, Hashable k) => MapLike (H.HashMap k v) k v where
lookup = H.lookup

then we just need to use (evalMemoStateH.empty) instead of startEvalMemo and our memoized function will be evaluated using Hashmap as an internal container hosted in MemoState. There is usually no need to do any modification to the memoized function itself.

## Mutable arrays and vectors as MonadCache

### Array-based memoization cache

version 0.4.0 adds ArrayCache: a new MonadCache implementation based on mutable arrays (inside IO or ST s monad). The main benefit of this MonadCache is its performance: it can be an order of magnitude faser than standard Data.Map-based cache. This is due to the fact that arrays have O(1) lookup time and in-place mutable arrays also have O(1) for updates (i.e. the cache add operation).

Unfortunatelly you cannot always use this MonadCache due to array's natural limitations:

• The key must be an instance of Ix typeclass
• The bounds of the array must be known (and specified) beforehand and array cannot be resized
• Array is a continious space of values, so if the key distribution is wide and sparse the memory will be wasted (or array may not even fit into memory)

But if the nature of your memoized function permits the usage of ArrayCache you can make your code much more faster by simply switching from Map-based MonadCache to ArrayCache especially if the value type of your function can be "unboxed" (i.e. it is one of primitive types like Int or Double). "Unboxed" values are packed in unboxed arrays UArray which offer even faster execution and are the most efficient in terms of memory usage. Normally you don't have to modify your monadic function definition to run ArrayCache-based memoization: just use appropriate eval* or run* function. For instance our canonical fibm function:

fibm 0 = return 0
fibm 1 = return 1
fibm n = do
n1 <- memo fibm (n-1)
n2 <- memo fibm (n-2)
return (n1+n2)

can be run using ST array of Integers with the following function:

evalFibmSTA :: Integer -> Integer
evalFibmSTA n = runST $evalArrayMemo (fibm n) (0,n)  here the (0,n) argument defines the bounds of cache array. Is it equally easy to use unboxed version of the array, but Integer cannot be unboxed (it isn't primitive type), so lets just use Double for our function result: evalFibmSTUA :: Integer -> Double evalFibmSTUA n = runST$ evalUArrayMemo (fibm n) (0,n)

Instead of ST you can use IO monad:

evalFibmIOA :: Integer -> IO Integer
evalFibmIOA n = evalArrayMemo (fibm n) (0,n)

evalFibmIOUA :: Integer -> IO Double
evalFibmIOUA n = evalUArrayMemo (fibm n) (0,n)

### Vector-based memoization cache

For even better performance use VectorCache and its flavours (unsafe version and dynamically expandable version) which are all based on very fast vector library.

Note however that this MonadCache is even more limiting that ArrayCache since vector supports only Int as an index.

The usage is very similar to ArrayCache, but instead of range we need to specify the length of the vector:

evalFibmSTV :: Int -> Integer
evalFibmSTV n = runST $evalVectorMemo (fibm n) n evalFibmIOUV :: Int -> IO Double evalFibmIOUV n = evalUVectorMemo (fibm n) n  Use "Expandable" version to avoid specifying length parameter: import qualified Control.Monad.Memo.Vector.Expandable as VE evalFibmSTVE :: Int -> Integer evalFibmSTVE n = runST$ VE.startEvalVectorMemo (fibm n)

## Performance of different MonadCache's:

The difference in performance for different MonadCache's with Fibonacci function is demonstrated by this criterion test. The test runs memoized Fibonacci function using the following caches:

• default Map-based
• State-based with Data.IntMap
• array and unboxed array based (Array and UArray)
• vector, unsafe vector and expandable vector (both boxed and unboxed vectors)

Full report can be found here.

## Custom mutable cache

It is also possible to use a mutable container as a MonadCache not defined here. For example if we wish to use mutable hash-table from hashtables package we can do so with the following code:

{-# LANGUAGE MultiParamTypeClasses, TypeSynonymInstances, FlexibleInstances #-}

import Data.Hashable
import qualified Data.HashTable.ST.Basic as H

newtype Container s k v = Container { toTable :: H.HashTable s k v }

type Cache s k v = ReaderCache (Container s k v)

instance (Eq k, Hashable k) => MonadMemo k v (Cache s k v (ST s)) where
{-# INLINE memo #-}
memo f k = do
c <- container
e <- lift $H.lookup (toTable c) k if isNothing e then do v <- f k lift$ H.insert (toTable c) k v
return v
else return (fromJust e)

{-# INLINE fib1 #-}
fibm 0 = return 0
fibm 1 = return 1
fibm n = do
f1 <- memo fibm (n-1)
f2 <- memo fibm (n-2)
return (f1+f2)

evalFib :: Int -> Int
evalFib n = runST \$ do
c <- H.new


text:
## Re: proof of no existence of liner system over R

I've tried to solve this:
Suppose there is a linear system which S is the solution set of it, $0\in \mathbb{R}$ therefore $\left ( 0,0,0 \right ) \in S=\left \{ \left ( a,a^2,b \right )|a,b\in \mathbb{R} \right \}$.
So, now I can tell that this is homogeneous systems.
$\left ( x_1,x_2,x_3 \right )\in S$ so the linear system is homogeneous, so scalar multiplication is also a solution to the system. $-1 \in \mathbb{R}$ and
But $\forall a \in \mathbb{R}\rightarrow a^2\neq -x_2$.
therfore , and $S$ is not the solution set.