text:
# Ordered pair

An ordered pair is a collection of two objects such that one can be distinguished as the first element and the other as the second element. An ordered pair with first element a and second element b is usually written as (a, b).

(The notation (a, b) is also used to denote an open interval on the real number line; context should make it clear which meaning is meant. To distinguish the two meanings, the ordered pair $\displaystyle (a,b)$ is sometimes written as $\displaystyle \langle a,b\rangle$ .)

Two ordered pairs (a1, b1) and (a2, b2) are equal if and only if a1 = a2 and b1 = b2.

The set of all ordered pairs whose first element is in some set X and second element in some set Y is called the Cartesian product of X and Y, and written X × Y. Subsets of X × Y are binary relations.

Ordered triples and n-tuples (ordered lists of n terms) are defined recursively from this definition: an ordered triple (a,b,c) can be defined as (a, (b,c) ): two nested pairs. This approach is mirrored in programming languages: It is possible to represent a list of elements as a construction of nested ordered pairs. For example, the list (1 2 3 4 5) becomes (1, (2, (3, (4, (5, {}))))). The Lisp programming language uses such lists as its primary data structure.

In axiomatic set theory, where all mathematical objects are given set-theoretic definitions, the ordered pair (a, b) is usually defined as the Kuratowski pair (a, b)K := {{a}, {a,b}}. The statement that x is the first element of an ordered pair p can then be formulated as

Yp : xY

and that x is the second element of p as

(∃ Yp : xY) ∧ (∀ Y1p, ∀ Y2p : Y1Y2 → (xY1xY2)).

Note that this definition is still valid for the ordered pair p = (x,x) = { {x}, {x,x} } = { {x}, {x} } = { {x} }; in this case the statement (∀ Y1p, ∀ Y2p : Y1Y2 → (xY1xY2)) is trivially true, since it is never the case that Y1Y2.

The above definition of an ordered pair is "adequate", in the sense that it satisfies the characteristic property that an ordered pair must have (namely: if (a,b)=(x,y), then a=x and b=y), but also arbitrary, as there are many other definitions which are no more complicated and would also be adequate. Examples for other possible definitions include

1. (a,b)reverse:= { {b}, {a,b} }
2. (a,b)short:= { a, {a,b} }
3. (a, b)01:= { {0,a}, {1,b} }

The "reverse" pair is almost never used, as it has no obvious advantages (nor disadvantages) over the usual Kuratowski pair. The "short" pair has the disadvantage that the proof of the characteristic pair property (see above) is more complicated than for the Kuratowski pair (the axiom of regularity has to be used); moreover, as the number 2 is in set theory sometimes defined as the set { 0, 1 } = { {}, {0} }, this would mean that 2 is a pair, 2 = (0,0)short.

For a more general treatment, see Product (category theory). Category theory tells us that although many objects may play the role of pairs, they are all equivalent in the sense of being categorically isomorphic.

## Rosser definition

In Logic (1953), Rosser uses a different definition, one which requires that a definition of the natural numbers be in place. Let Nn be the set of natural numbers, and define

$\displaystyle \phi(x) = \{ z : \exists y\in x : (y\in Nn \wedge z = y + 1) \vee (y \not\in Nn \wedge z = y) \}$

That is, φ(x) contains the successor of every natural number in x, together with all the non-numbers from x. In particular, it does not contain the number 0, so that for any sets A and B, $\displaystyle \phi(A) \not= \{0\} \cup \phi(B)$ .

Then the ordered pair (A,B) may be defined by adjoining 0 to each element of φ(B), and uniting the result with φ(A):

$\displaystyle (A,B) = \phi(A) \cup \{x : \exists y \in\phi(B) : x = y\cup\{0\} \}$

The component A may be recovered from the pair by extracting all the elements of the pair that do not contain 0, and vice-versa for B.


text:
### Grant McDermott

Assistant Professor
Dept. of Economics
University of Oregon

# Why economists love auctions

Some background first: South Africa's power market is utterly dominated by (a) coal and (b) Eskom, the parasitical parastatal monopoly. In a bid to encourage both fuel diversification and competition, the government has determined that 3,725 MW of new capacity up until 2030 should consist of renewable sources operated by independent power producers (IPPs). This translates to roughly 10,000 GWh of actual future electricity generation.

Ignoring the fact that this is small potatoes in the scheme of things $$-$$ less than 5% of the country's current 240 TWh annual electricity consumption $$-$$ the point that I want to make here is mostly about how those IPPs are chosen.

Having played with various schemes, authorities eventually settled on something called the Renewable Energy Independent Power Producer Procurement Programme (REIPPPP). This is effectively a competitive bidding process, whereby applicants submit a guaranteed price that they are willing to accept for electricity that they generate in the future. In other words, it looks a lot like the idealised auction market advocated in economic textbooks.

So how have things turned out? Well, the results from the third round of bidding have just come in. (The previous bidding rounds were held in 2011 and 2012, respectively.) It would appear that things are progressing rather well:
The six successful solar PV bidders, which shared an allocation of 435 MW, were particularly aggressive with their pricing. Fully indexed prices using April 2011 as the base year showed that the average solar PV price fell from R2.75/kWh in bid-window one to 88c/kWh in the third round.

[...]Similarly, the price of onshore wind fell from R1.14/kWh in round one to 89c/kWh in round two and to only 66c/kWh in the latest round. A total of 787 MW was allocated across the seven wind projects

[...]Prices for the two 100-MW-apiece CSP [concentrated solar power] projects declined from R2.68/kWh in the first window to R1.46/kWh.
We must of course be careful not to draw too many conclusions from the above figures. For one thing, the average price that South Africans currently pay for electricity remains lower than any of the above bids. Although, it is scheduled to approach (and even exceed, in the case of wind) them in coming years:

Even then, just because a small portion of wind or solar energy is expected to "reach grid parity" within the next five years, doesn't mean that the game is up for fossil fuels. There are major problems with peak balancing, intermittency and load-following constraints that renewables need to overcome, which I and many others have discussed at length before.

However, a 68% drop in the bid price of solar PV since 2011 $$-$$ say nothing of wind and CSP bids falling by nearly 45% $$-$$ is clearly impressive. Many people will see this as a evidence of how quickly renewable technologies are progressing. I wouldn't dispute that, but I also see it as a vindication of the auction system that was used for determining the winning bids.

It is something that South Africa's electricity sector could use a lot more of.

format: plain


text:
# Projecting interval uncertainty through the discrete Fourier transform

This repository provides a method that can propagate interval uncertainty through the discrete Fourier transform while yielding the exact bounds on the Fourier amplitude and Power Spectral Density function. The algorithm applies to real sequences of intervals. The method allows technical analysts to project interval uncertainty present in the time signals to their Fourier amplitude without making assumptions about the error distribution at each time step. Thus, it is possible to calculate and analyse system responses in the frequency domain without conducting extensive Monte Carlo simulations in the time domain. The applicability of this method in practice is demonstrated by a technical application.

Disclaimer: This code was developed for illustration purposes and for proof-of-concept. Thus this code is not optimized for large-scale applications. An optimized version of the code is currently under development.

## References

De Angelis, M.; Behrendt, M.; Comerford, L.; Zhang, Y.; Beer, M. (2021): Forward interval propagation through the discrete Fourier transform, The 9th international workshop on Reliable Engineering Computing, arXiv:2012.09778.

## Installation

Clone the git repository on your machine, cd to the repository, open a Python3 interpreter and import the interval Fourier transform ans other useful packages

from fourier.transform import transform as intervalDFT
from fourier.application import application as app
from fourier.number import number as int_num
import numpy
from numpy import (arange, cos, exp, linspace, mean, pi,  sin, zeros)
from matplotlib import pyplot, cm

## Signal generation and interval DFT

At first time and frequency parameters and an analytical PSD function are needed to model a stochastic process.

### Define parameters

wu = 2.2975 # upper cut-off frequency
T = 350 # total time length

dt = 2*pi /(2*wu) # timestep size
dw = 2*pi / T # frequency step size

t = numpy.arange(0,T,dt) # time vector
w = numpy.arange(0,wu,dw) # frequency vector

### JONSWAP power spectrum

The JONSWAP power spectrum is utilised to generate stochastic processes. The required parameters are:

alpha = 0.0081 # spectral energy parameter
w_p = 0.7 # peak frequency
gamma = 3.3 # peak enhancement factor
sigma1 = 0.07 # spectral width parameter for w <= w_p
sigma2 = 0.09 # spectral width parameter for w > w_p
spectrum = app.jonswap_spectrum(w,alpha,w_p,gamma,sigma1,sigma2)

### Plot the JONSWAP power spectrum

ax = app.plot_line(w,spectrum,figsize=(18,6),xlabel=r'#$x$',ylabel='$x$',color=None,lw=1,title='JONSWAP power spectrum',ax=None,label=None)
ax.set_ylabel('Power Spectral Density [m$^2$s]',fontsize=20)

### Generate time signal and intervalize it

To generate a stochastic process the spectral representation method is utilised. This signal is then intervalized with interval uncertainty ±0.1. Both signals are plotted.

sea_waves = app.stochastic_process(spectrum,w,t)
pm = 0.1
sea_waves_interval = intervalDFT.intervalize(sea_waves, pm)

ax = app.plot_line(t,sea_waves,figsize=(18,6),xlabel='Time [s]',ylabel='Wave height [m]',color='rebeccapurple',lw=1,title='Signal from stationary power spectrum',ax=None,label=None)
sea_waves_interval.plot(xlabel='Time [s]',ylabel='Wave height [m]',title=r'Signal with $\pm$ '+str(pm)+' information gaps (intervals)')

### Compute the Fourier transforms

Compute the Fourier transform of the crisp signal and the interval Fourier transform for the interval signal with the selective method and the interval method. Also compute the periodogram of respective (bounded) Fourier amplitudes.

FA = intervalDFT.Fourier_amplitude(sea_waves)
BI,BS = intervalDFT.compute_amplitude_bounds(sea_waves_interval)
BI.insert(0,int_num.Interval(0,0))
BS.insert(0,int_num.Interval(0,0))

FA = app.periodogram(FA, t, dt)
BI = app.periodogram(BI, t, dt)
BS = app.periodogram(BS, t, dt)

### Plot the interval Fourier transform

The amplitude of the crisp signal and both bounded Fourier amplituted are plotted.

ax = app.plot_line(w,FA,figsize=(18,6),xlabel=r'#$x$',ylabel=r'$x$',color=None,lw=1,title=None,ax=None,label='Interval uncertainty: $\pm$ '+str(pm)+'')
app.plot_bounds(x=w,bounds=BI,color='cornflowerblue',alpha=0.4,ax=ax)
app.plot_bounds(x=w,bounds=BS,color='orangered',alpha=0.6,ax=ax)
ax.set_ylabel('Power Spectral Density [m$^2$s]',fontsize=20)
ax.tick_params(direction='out', length=6, width=2, labelsize=14)

## Application to a SDOF system

The system under investigation is a offshore wind turbine simplified to a SDOF system. The parameters are set to

R = 3 # outer radius
r = 2.8 # inner radius
h_pile = 60 # height
rho_steel = 7800 # density of steel
c = 1e5 # stiffness
k = 1e6 # damping coefficient

Get the natural frequency w0 and the damping ratio xi

w0,xi = app.wind_turbine(R,r,h_pile,rho_steel,c,k)

The response can be obtained by pushing the (intervalised) signal through the frequency response function

freq_response_precise = app.frequency_response(w,FA,w0,xi)
freq_response_BI_low,freq_response_BI_high = app.frequency_response_interval(w,BI,w0,xi)
freq_response_BS_low,freq_response_BS_high = app.frequency_response_interval(w,BS,w0,xi)

Those responses can be plotted

ax = app.plot_line(w,freq_response_precise,figsize=(18,6),xlabel=r'#$x$',ylabel=r'$x$',color=None,lw=1,title=None,ax=None,label=None)
ax.fill_between(x=w,y1=freq_response_BI_low,y2=freq_response_BI_high, alpha=0.4, label='Interval', edgecolor='blue', lw=2, color='cornflowerblue')
ax.fill_between(x=w,y1=freq_response_BS_low,y2=freq_response_BS_high, alpha=0.6, label='Selective', edgecolor='red', lw=2, color='orangered')

ax.set_ylabel('Power Spectral Density [m$^2$s]',fontsize=20)
ax.set_title(r'Interval uncertainty: $\pm$ '+str(pm)+'', fontsize=20)

ax.tick_params(direction='out', length=6, width=2, labelsize=14)
_=ax.set_xlim([0.5, 1.1])

## Comparison with Monte Carlo

In this section it is illustrated how severe interval uncertainty is underestimated by Monte Carlo. To show this, a signal with interval uncertainty ±0.5 is utilised and plotted.

pm = 0.5
sea_waves_interval_05 = intervalDFT.intervalize(sea_waves, pm)
sea_waves_interval_05.plot(xlabel='Time [s]',ylabel='Wave height [m]',title=r'Signal with $\pm$ '+str(pm)+' information gaps (intervals)')

Generate some random signals between the bounds. All signals which are within or on the bounds are possible.

RAND_SIGNALS = sea_waves_interval_05.rand(N=20) # this picks out N (inner) random signals within the bounds

fig,ax = intervalDFT.subplots(figsize=(16,8))
for rs in RAND_SIGNALS:
intervalDFT.plot_signal(rs,ax=ax)
sea_waves_interval_05.plot(ax=ax)
ax.grid()
_=ax.set_xlim(0,55) # underscore here is used to suppress the output of this line

Computing the Fourier amplitude bounds and the periodogram of the interval signal

BI,BS = intervalDFT.compute_amplitude_bounds(sea_waves_interval_05)
BI.insert(0,int_num.Interval(0,0))
BS.insert(0,int_num.Interval(0,0))

BI = app.periodogram(BI, t, dt)
BS = app.periodogram(BS, t, dt)

Plotting the bounds of the Fourier amplitude in comparison to the resulting bounds obtained by Monte Carlo

BI_low=[ai.lo() for ai in BI]
BI_high=[ai.hi() for ai in BI]
BS_low=[ai.lo() for ai in BS]
BS_high=[ai.hi() for ai in BS]

fig = pyplot.figure(figsize=(18,6))
ax = fig.subplots()
ax.grid()
ax.fill_between(x=w,y1=BI_low,y2=BI_high, alpha=0.4, label='Interval', edgecolor='blue', lw=2, color='cornflowerblue')
ax.fill_between(x=w,y1=BS_low,y2=BS_high, alpha=0.6, label='Selective', edgecolor='red', lw=2, color='orangered')

n_MC = 10
for x in range(n_MC):
FX = intervalDFT.Fourier_amplitude(sea_waves_interval_05.rand())
FX = app.periodogram(FX, t, dt)
#intervalDFT.plot_line(w,FX,figsize=None,xlabel=r'#$x$',ylabel=r'$x$',color='palegreen',lw=1,title=None,ax=ax,label=None)
app.plot_line(w,FX,figsize=None,xlabel=r'#$x$',ylabel=r'$x$',color='#d7f4d7',lw=1,title=None,ax=ax,label=None)

ax.set_ylabel('Power Spectral Density [m$^2$s]',fontsize=20)
ax.set_title(r'Interval uncertainty: $\pm$ '+str(pm)+'', fontsize=20)

ax.tick_params(direction='out', length=6, width=2, labelsize=14)

Which increasing sample size, the range within the bounds of the interval signal is better covered. However, even a very high sample size is insufficient to get close to the bounds obtained by the interval DFT.

fig = pyplot.figure(figsize=(18,6))
ax = fig.subplots()
ax.grid()

n_MC = 1000
for x in range(n_MC):
FX = intervalDFT.Fourier_amplitude(sea_waves_interval_05.rand())
FX = app.periodogram(FX, t, dt)
app.plot_line(w,FX,figsize=None,xlabel=r'#$x$',ylabel=r'$x$',color='#7cc47c',lw=1,title=None,ax=ax,label=None)

n_MC = 100
for x in range(n_MC):
FX = intervalDFT.Fourier_amplitude(sea_waves_interval_05.rand())
FX = app.periodogram(FX, t, dt)
app.plot_line(w,FX,figsize=None,xlabel=r'#$x$',ylabel=r'$x$',color='#a7d9a7',lw=1,title=None,ax=ax,label=None)

n_MC = 10
for x in range(n_MC):
FX = intervalDFT.Fourier_amplitude(sea_waves_interval_05.rand())
FX = app.periodogram(FX, t, dt)
app.plot_line(w,FX,figsize=None,xlabel=r'#$x$',ylabel=r'$x$',color='#d7f4d7',lw=1,title=None,ax=ax,label=None)

ax.set_ylabel('Power Spectral Density [m$^2$s]',fontsize=20)
_=ax.set_title('Bounds estimated by MC', fontsize=20)


text:
TheInfoList

In mathematics, a plane curve is a curve in a plane that may be either a Euclidean plane, an affine plane or a projective plane. The most frequently studied cases are smooth plane curves (including piecewise smooth plane curves), and algebraic plane curves. Plane curves also include the Jordan curves (curves that enclose a region of the plane but need not be smooth) and the graphs of continuous functions.

## Symbolic representation

A plane curve can often be represented in Cartesian coordinates by an implicit equation of the form ${\displaystyle f(x,y)=0}$ for some specific function f. If this equation can be solved explicitly for y or x – that is, rewritten as ${\displaystyle y=g(x)}$ or ${\displaystyle x=h(y)}$ for specific function g or h – then this provides an alternative, explicit, form of the representation. A plane curve can also often be represented in Cartesian coordinates by a parametric equation of the form ${\displaystyle (x,y)=(x(t),y(t))}$ for specific functions ${\displaystyle x(t)}$ and ${\displaystyle y(t).}$Cartesian coordinates by an implicit equation of the form ${\displaystyle f(x,y)=0}$ for some specific function f. If this equation can be solved explicitly for y or x – that is, rewritten as ${\displaystyle y=g(x)}$ or ${\displaystyle x=h(y)}$ for specific function g or h – then this provides an alternative, explicit, form of the representation. A plane curve can also often be represented in Cartesian coordinates by a parametric equation of the form ${\displaystyle (x,y)=(x(t),y(t))}$ for specific functions ${\displaystyle x(t)}$ and ${\displaystyle y(t).}$

Plane curves can sometimes also be represented in alternative coordinate systems, such as polar coordinates that express the location of each point in terms of an angle and a distance from the origin.

## Smooth plane curve

A smooth plane curve is a curve in a real Euclidean plane R2 and is a one-dimensional smooth manifold. This means that a smooth plane curve is a plane curve which "locally looks like a line", in the sense that near every point, it may be mapped to a line by a smooth function. Equivalently, a smooth plane curve can be given locally by an equation f(x, y) = 0, where f : R2R is a smooth function, and the partial derivatives f/∂x and f/∂

Plane curves can sometimes also be represented in alternative coordinate systems, such as polar coordinates that express the location of each point in terms of an angle and a distance from the origin.

A smooth plane curve is a curve in a real Euclidean plane R2 and is a one-dimensional smooth manifold. This means that a smooth plane curve is a plane curve which "locally looks like a line", in the sense that near every point, it may be mapped to a line by a smooth function. Equivalently, a smooth plane curve can be given locally by an equation f(x, y) = 0, where f : R2R is a smooth function, and the partial derivatives f/∂x and f/∂y are never both 0 at a point of the curve.


text:
# DVI utilities

TeX outputs a file in DVI (DeVice Independent) format as a compact representation of the original document. DVI files can be translated to meet the requirements of a real physical device, such as PostScript printers (see section `Introduction' in Dvips), PCL printers (see dvilj(1)), and X displays (see xdvi(1)). In fact, DVI translators are available for virtually all common devices: see `CTAN:/dviware' (for CTAN info, see section `unixtex.ftp' in Kpathsea).

For the precise definition of the DVI file format, see (for example) the source file `web2c/dvitype.web'.

The DVI-processing programs in the Web2c distribution are not device drivers; they perform generic utility functions.

## DVIcopy: Canonicalize virtual font references

DVIcopy reads a DVI file, expands any references to virtual fonts (see section `Virtual fonts' in Dvips) to base fonts, and writes the resulting DVI file. Thus you can use virtual fonts even if your DVI processor does not support them, by passing the documents through DVIcopy first. Synopsis:

```dvicopy [option]... [indvi[.dvi] [outdvi[.dvi]]]
```

DVIcopy reads standard input if indvi is not specified, and writes standard output if outdvi is not specified.

The program accepts the following options, as well as the standard `-help' and `-version' (see section Common options):

`-magnification=integer'
Override existing magnification in indvi with integer; 1000 specifies no magnification. This is equivalent to setting TeX's `\mag` parameter.
`-max-pages=n'
Process n pages; default is one million.
`-page-start=page-spec'
Start at the first page matching page-spec, which is one or more (signed) integers separated by periods, corresponding to TeX's `\count0...9` parameters at `\shipout` time; `*' matches anything. Examples: `3', `1.*.-4'.

## DVItype: Plain text transliteration of DVI files

DVItype translates a DeVice Independent (DVI) file (as output by TeX, for example) to a plain text file that humans can read. It also serves as a DVI-validating program, i.e., if DVItype can read a file, it's correct. Synopsis:

```dvitype [option]... dvifile[.dvi]
```

DVItype does not read any bitmap files, but it does read TFM files for fonts referenced in dvifile. The usual places are searched (see section `Supported file formats' in Kpathsea). To see all the relevant paths, set the environment variable `KPATHSEA_DEBUG` to `-1' before running the program.

Output goes to standard output.

The program accepts the following options, as well as the standard `-help' and `-version' (see section Common options):

`-dpi=real'
Do pixel movement calculations at real pixels per inch; default 300.0.
`-magnification=integer'
Override existing magnification in indvi with integer; 1000 specifies no magnification. This is equivalent to setting TeX's `\mag` parameter.
`-max-pages=n'
Process n pages; default is one million.
`-output-level=n'
Verbosity level of output, from 0 to 4 (default 4):
• 0: Global document information only.
• 1: Most DVI commands included, and typeset characters summarized.
• 2: Character and movement commands explicitly included.
• 3: DVI stack and current position calculations included.
• 4: Same information as level 3, but DVItype does random positioning in the file, reading the DVI postamble first.
`-page-start=page-spec'
Start at the first page matching page-spec, which is one or more (signed) integers separated by periods, corresponding to TeX's `\count0...9` parameters at `\shipout` time; `*' matches anything. Examples: `1', `5.*.-9'.
`-show-opcodes'
Show numeric opcode values (in decimal) for DVI commands, in braces after the command name. This can help in debugging DVI utilities. We use decimal because in the DVI format documentation (in `dvitype.web', among others) the opcodes are shown in decimal.

### DVItype output example

As an example of the output from DVItype (see section above), here is its (abridged) translation of the `story.dvi' resulting from running the example in The TeXbook, with `-output-level=4' and `-show-opcodes' on.

```...
Options selected:
Starting page = *
Maximum number of pages = 1000000
Output level = 4 (the works)
Resolution = 300.00000000 pixels per inch
numerator/denominator=25400000/473628672
magnification=1000;       0.00006334 pixels per DVI unit
' TeX output 1992.05.17:0844'
Postamble starts at byte 564.
maxv=43725786, maxh=30785863, maxstackdepth=3, totalpages=1
Font 33: cmsl10--loaded at size 655360 DVI units
Font 23: cmbx10--loaded at size 655360 DVI units
Font 0: cmr10--loaded at size 655360 DVI units

42: beginning of page 1
87: push {141}
level 0:(h=0,v=0,w=0,x=0,y=0,z=0,hh=0,vv=0)
88: down3 -917504 {159} v:=0-917504=-917504, vv:=-58
92: pop {142}
...
104: putrule {137} height 26214, width 30785863 (2x1950 pixels)
113: down3 5185936 {159} v:=655360+5185936=5841296, vv:=370
117: push {141}
level 1:(h=0,v=5841296,w=0,x=0,y=0,z=0,hh=0,vv=370)
118: right4 12265425 {146} h:=0+12265425=12265425, hh:=777
[ ]
123: fntdef1 23 {243}: cmbx10
145: fntnum23 {194} current font is cmbx10
146: setchar65 h:=12265425+569796=12835221, hh:=813
147: w3 251220 {150} h:=12835221+251220=13086441, hh:=829
151: setchar83 h:=13086441+418700=13505141, hh:=856
...
164: setchar82 h:=17448202+565245=18013447, hh:=1142
165: x0 -62805 {152} h:=18013447-62805=17950642, hh:=1138
166: setchar89 h:=17950642+569796=18520438, hh:=1174
[A SHORT STORY]
167: pop {142}
level 1:(h=0,v=5841296,w=0,x=0,y=0,z=0,hh=0,vv=370)
...
550: pop {142}
level 0:(h=0,v=42152922,w=0,x=0,y=0,z=0,hh=0,vv=2670)
551: down3 1572864 {159} v:=42152922+1572864=43725786, vv:=2770
555: push {141}
level 0:(h=0,v=43725786,w=0,x=0,y=0,z=0,hh=0,vv=2770)
556: right4 15229091 {146} h:=0+15229091=15229091, hh:=965
561: setchar49 h:=15229091+327681=15556772, hh:=986
[ 1]
562: pop {142}
level 0:(h=0,v=43725786,w=0,x=0,y=0,z=0,hh=0,vv=2770)
563: eop {140}
```

Explanation:

• The DVItype options are recorded at the beginning, followed by global information about the document, including fonts used.
• Each DVI command is preceded by its byte position in the file (`42:', `87:', ...), and (because of the `-show-opcodes') followed by its decimal opcode value in braces (`{141}', `{142}', ...).
• The `level' lines record information about the DVI stack; `h' and `v' define the current position in DVI units, while `hh' and `vv' are the same in pixels.
• Text sequences are summarized in brackets, as in `[A SHORT STORY]' and the `[ 1]'.


text:
D - Islands War

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

i 番目の橋は、西から i 番目の島と西から i+1 番目の島を接続しています。

ある日、いくつかの島同士で争いが起こり、島の住人たちから M 個の要望がありました。

あなたは橋をいくつか取り除くことでこれら M 個の要望全てを叶えることにしました。

### 制約

• 入力は全て整数である
• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq a_i < b_i \leq N
• (a_i, b_i) は全て異なる

### 入力

N M
a_1 b_1
a_2 b_2
:
a_M b_M

### 入力例 1

5 2
1 4
2 5

### 出力例 1

1

### 入力例 2

9 5
1 8
2 7
3 5
4 6
7 9

### 出力例 2

2

### 入力例 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

### 出力例 3

4

Score : 400 points

### Problem Statement

There are N islands lining up from west to east, connected by N-1 bridges.

The i-th bridge connects the i-th island from the west and the (i+1)-th island from the west.

One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:

Request i: A dispute took place between the a_i-th island from the west and the b_i-th island from the west. Please make traveling between these islands with bridges impossible.

You decided to remove some bridges to meet all these M requests.

Find the minimum number of bridges that must be removed.

### Constraints

• All values in input are integers.
• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq a_i < b_i \leq N
• All pairs (a_i, b_i) are distinct.

### Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

### Output

Print the minimum number of bridges that must be removed.

### Sample Input 1

5 2
1 4
2 5

### Sample Output 1

1

The requests can be met by removing the bridge connecting the second and third islands from the west.

### Sample Input 2

9 5
1 8
2 7
3 5
4 6
7 9

### Sample Output 2

2

### Sample Input 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

### Sample Output 3

4


text:
# Calculating the cross product of 2 vectors without using the torque formula

For the scenario described as the follows:

Two vectors $$\vec{s}$$ and $$\vec{t}$$ lie in the xy plane. Their directions are, respectively, a° and b° measured counterclockwise from the positive x axis. Find the magnitude and the direction of $$\vec{s}\times\vec{t}$$

I read that the magnitude of $$\vec{s}\times\vec{t}$$ is calculated by $$rs|sin(a°-b°)|$$. I'm confused as to why we can calculate it using sin(a°-b°) and what's the geometrical/physical meaning of doing it this way. Based on my knowledge, the only way I came up with is moving $$\vec{t}$$ so that its tail is at the head of $$\vec{s}$$. then we can calculate it as if calculating the torque using $$\tau=Fl$$

• What do you want to compute? The torque $\vec F\times \vec r$? May 21, 2021 at 18:11
• Roughly speaking, the magnitude of the cross product is the determinant of matrice given by the two vectors expressed on the plane they are defined within. And the geometrical interpretation of this determinant is that it is the area of the parallelogram given by these two vectors. Hence you have a $\sin$ function. May 21, 2021 at 18:18
• @kyril I want to compute $\vec{s}\times\vec{t}$, but I don't understand the solution described in my question as I only know how to calculate 2 vectors as if calculating a torque... May 21, 2021 at 18:26
• I'm sorry I'd like to help, but I don't understand what $s$ and $t$ are... May 21, 2021 at 21:15

## 3 Answers

The magnitude of the vector product of s and t is: st[sin(angle between s and t)]. In the given problem, that angle is the difference between the two angles measured from the x axis. In your diagram, s would be the radius and t would be F, but there is no reason to assume that F is vertical, and you have not specified the angles from the x axis (assumed horizontal?).

Well you are not wrong but it would ethically be an injustice to physics if we described it that way . This is because cross product comes first and then torque. So we say that $$\tau$$ is the cross product of $$\vec S$$ and $$\vec F$$ and not the other way round.$$\vec \tau = \vec S \times \vec F$$ It was simply defined that cross product of two vectors $$\vec A$$ and $$\vec B$$ is AB$$sin \theta$$ ($$\theta$$ being the angle between the two vectors) and have direction as given by screw rule because many quantities like torque were found to obey such results. Besides it is the only way where we can define pseudo vectors like torque that describe motion not along a line but along a plane and are directed perpendicular to such a plane .

Here is another way to evaluate the vector cross product of two vectors using a determinate.

For any two vectors $$\vec s$$ and $$\vec t$$ $$\ {\vec s \times \vec t} = \begin{vmatrix} \vec i & \vec j & \vec k \\ s_x & s_y & s_z \\ t_x & t_y & t_z \end{vmatrix}$$ $$\vec i$$, $$\vec j$$, and $$\vec k$$ are unit vectors along the $$x$$, $$y$$, and $$z$$ axes of a Cartesian coordinate system. $$s_x$$ , $$s_y$$, and $$s_z$$ are the components of $$\vec s$$ along the axes, and $$t_x$$ , $$t_y$$, and $$t_z$$ are the components of $$\vec t$$ along the axes.


text:
# Why is it natural to look for solutions involving dimensionless quantities?

While studying the Heat Equation, I got stuck in a statement in my book. It says:

We have seen that the combination of variables $\displaystyle \frac{x}{\sqrt{Dt}}$ is not only invariant with respect to parabolic dilations but also dimensionless. It is then natural to check if there are solutions of the Heat Equation involving such dimensionless group. (...) it makes sense to look for solutions of the form:

$\displaystyle u^{*}(x,t)=\frac{q}{\sqrt{Dt}}U\left( \frac{x}{\sqrt{Dt}} \right)$

where $U$ is a (dimensionless) function of a single variable."

Why is the bold text so? I don't see why it is intuitive to search for such solutions.

-
–  rob Aug 20 '14 at 2:05
For completeness, it would be good if you could specify which book you are using. –  Emilio Pisanty Aug 20 '14 at 9:09

Let's say your goal is to describe the shape of some object, such as a box.

You could create a completely arbitrary ruler and measure the three axes of the box, coming out for example with lengths of 11.72, 23.44, and 35.16 of your arbitrary ruler units.

Or you might look at your results more closely and think hmm, something is going on here, since the second two lengths are exact multiples of the first one.

So instead of using arbitrary units, you make the box into its own ruler by choosing pairs of sides and looking at the ratios of their lengths. By the rules of division, such ratios are of course dimensionless, since for example your original arbitrary units would cancel out in the ratio.

But look at the result! Instead of (11.72, 23.44, 35.16), you have stripped out the arbitrary noise created when you defined and arbitrary ruler. As a direct result, your "theory of box" instead becomes a much more interesting sequence such as (1, 2, 3) or (1/3, 2/3, 1), depending on which side you pick as your divisor (or "1") unit of natural length. Such simpler ratios immediately suggest that the box is composed of smaller, more fundamental units.

Physics, and in particular the Standard Model, is of course far more complicated that a simple box. But it too is rich in same-to-same ratios (about two dozen total) that measure different magnitudes of identical quantities. For those pairs, you can again use the ratio trick to strip out any "arbitrary ruler" noise and come up with more fundamental, and hopefully insightful, values for fundamental "size and shape" constants that define the exact "shape" of the Standard Model.

For example, the absolute invariance that special relativity imparts to the speed of light makes c into a brain-dead obvious choice for the natural unit of anything involving velocity. Thus c=1, and any other velocity simply uses that unique velocity as its divisor. The charge of an electron is another good divisor choice, though there you can see that there is some wiggle room in the choices, since you could also argue that the -1/3 charge of a down quark might in some way be more "fundamental."

-
nice, but what if one dimension is time and another is space how would they cancel out in a ratio? –  Nikos M. Aug 20 '14 at 2:07
In that somewhat special case you use c, which is itself a ratio of space over time, as the bridge for defining a self-consistent shared unit, giving one nanosecond of time equaling about 0.3 meters of space. –  Terry Bollinger Aug 20 '14 at 2:16
of course, the comment was just a means for clarification in the answer –  Nikos M. Aug 20 '14 at 2:17
It's a good question, since it points out that there is a certain degree of art or even convenience in some of the choices. –  Terry Bollinger Aug 20 '14 at 2:44

Dimensionless equations have the advantage that they work for any value of the parameters. They are scale invariant. So the solution in terms of a single dimensionless variable applies to all values of $D$ and $t$.

It also allows the definition of characteristic values for the dynamic variables. In your example, one could say $u_0$ = $\frac{q}{\sqrt{Dt}}$, and $x_0 = \sqrt{Dt}$. These set the scale of both the independent and dependent variable. It allows, for example, one to say when a value is "big" (greater than the characteristic value), or "small" (less than the characteristic value). It's a little strange in this case because these characteristic values change with time. Things are a bit clearer when they are constants. Then you would have, for example, a characteristic length, period.

Now if we define dimensionless variable, say $\upsilon = u(x,t)/u_0$ and $\chi = x/x_0$, we can write the much simpler, and more universal equation $$\upsilon(\chi, t) = U(\chi)$$ and "large" and "small" are set by whether or not $\chi$ and $\upsilon$ are greater than or less than unity. A further feature is that a plot on dimensionless axes will have values on the $x$ and $y$ axis that center around $1$. The plots are cleaner, and also universal.

These kinds of dimensionless solutions are a convenience, but they don't add anything new to the theory. Whether or not it is natural to look for them ... well, that is in the eye of the beholder. Personally, I do express equations in dimensionless form whenever possible.

In the case of the heat equation, we see that as time marches on the characteristic length gets larger, that is, the "hot region" grows, as the square root of the time variable, and the size of that region is roughly $x_0$. Similarly, the characteristic heat variable (perhaps energy density) decreases ... "gets cooler" ... as the square root of the time variable, and its value is roughly $u_0$.

-

These solutions are preferred because they directly embody the scale invariance of the equation. In general, when a physical problem has some sort of symmetry - like the parabolic dilation invariance of the heat equation - then this establishes a corresponding action of the symmetry group on the solutions. The canonical forms based on dimensionless parameters are often eigenfunctions of this symmetry.

With the heat equation, for example, $$\frac{\partial u}{\partial t}=D\frac{\partial^2 u}{\partial x^2},$$ the nontrivial symmetry is a combined dilation between space and time: on a problem that's twice the size, the solution will be the same except the heat diffusion will take four times as long. To be more precise, if you change coordinates to $x'=a x$ and $t'=a^2 t$, for some scale parameter $0<a<\infty$, then the equation is exactly the same: $$\frac{\partial u}{\partial t'}=D\frac{\partial^2 u}{\partial x'^2}.$$ This means that for any given solution $u_1(x,t)$ of the heat equation, you can always construct an infinite family of solutions, $$u_a(x,t)=a\, u_1(a x,a^2t).$$ (I have added a scale factor in $u$ as well, to keep the conserved total heat $q=\int_{-\infty}^\infty u_a(x,t)\,\text dx$ constant, though this is not strictly that necessary.)

Now, these solutions are probably different to the original one unless that one is completely flat, but as physicists we're not very interested in that and we want to remove this superfluous degree of freedom. (I should note that mathematicians are even more trigger-happy on that, too.) The problem, though, is that since they're all equivalent it's hard to pick one representative of the class. Moreover, in general, all the $u_a$ will be linearly independent, so they are in some sense different.

This is where canonical forms of the type $$u^*(x,t)=\frac{q}{\sqrt{Dt}}U(x/\sqrt{Dt})$$ come in. It should be clear that these solutions are eigenfunctions of the dilation symmetry operator $L_a$, which means that all the corresponding $u_a$ are linearly dependent, which greatly simplifies the corresponding equivalence class.

On a more formal setting, we have a bunch of symmetry operators which commute with each other and with the differential operator $L=D\tfrac{\partial^2 }{\partial x^2}$, which means that we can expand any solution of $L=0$ as a linear combination of the eigenfunctions of the $L_a$ and - crucially - the time evolution under $\tfrac\partial{\partial t}=L$ will preserve the coefficients of this expansion.

On a more pragmatic footing, it is nice that we're guaranteed the existence of such solutions because of the symmetry of the equation, but looking for them is useful because it reduces the dimensionality of the problem: we now have to solve a one-dimensional ODE rather than a two-dimensional PDE, and this is a vastly easier problem. The price we need to pay is that there is no guarantee that the special solutions we find will match the initial conditions we may need to impose, but this is generally something we're OK with, because we can use linear combinations of these special solutions to solve for arbitrary initial conditions.

-

Because it is easier for dimensionless quantities to be combined in arbitrary polynomial terms (or other terms e.g exponential) with no loss (or extra) factors. Think like "characteristic times" used in exponential factors.

Especially quantities appearing in solutions of the form $e^{a} = \sum_0^\infty \frac{a^n}{n!}$, one can see why a dimensionless quantity $a$ is necessary here. Else there would be problem matching the proper dimensions (in an infinite amount of powers).

In a sense they are invariant quantities suitable for expressing solutions in terms of them.

In an analogy with tensor analysis, if we assume for a minute that each quantity that has a dimension (e.g mass, time, etc.) can be a vector or tensor, then a dimensionless quantity can be scalar invariant.

-

The key concept is that the units of measurements you chose to use make no difference to the physical behaviour. I.e you expect the solution behaviour to be independent of the units of measurement used. This means you should get the same solution if we chose to measure $x$ is in meters, and $t$ is in seconds and $D$ is in $m^2/s$ as if we chose to measure $x$ is in furlongs and $t$ is in fortnights and D is in $furlongs^2/fortnight$.

By looking for a solution in terms of the dimensionless parameters we ensure this is occurs. In fact this is the only way it can be ensured.

-

Intuitively a lot of equations we use to describe physical phenomena such as $exp(x)$ take in only dimensionless variables. Moreover in physics we're always taking the derivative or the log of things, and it works out to be much simpler if you're not always having to deal with a dimensioned constant factor that drops out every time you take the derivative.

-


text:
Homomorphic Computation in Reed-Muller Codes

Jinkyu Cho, Young-Sik Kim, and Jong-Seon No

Abstract

With the ongoing developments in artificial intelligence (AI), big data, and cloud services, fully homomorphic encryption (FHE) is being considered as a solution for preserving the privacy and security in machine learning systems. Currently, the existing FHE schemes are constructed using lattice-based cryptography. In state-of-the-art algorithms, a huge amount of computational resources are required for homomorphic multiplications and the corresponding bootstrapping that is necessary to refresh the ciphertext for a larger number of operations. Therefore, it is necessary to discover a new innovative approach for FHE that can reduce the computational complexity for practical applications. In this paper, we propose a code-based homomorphic operation scheme. Linear codes are closed under the addition, however, achieving multiplicative homomorphic operations with linear codes has been impossible until now. We strive to solve this problem by proposing a fully homomorphic code scheme that can support both addition and multiplication simultaneously using the Reed-Muller (RM) codes. This can be considered as a preceding step for constructing code-based FHE schemes. As the order of RM codes increases after multiplication, a bootstrapping technique is required to reduce the order of intermediate RM codes to accomplish a large number of operations. We propose a bootstrapping technique to preserve the order of RM codes after the addition or multiplication by proposing three consecutive transformations that create a one-to-one relationship between computations on messages and that on the corresponding codewords in RM codes.

Note: We propose a fully homomorphic code scheme that can support both addition and multiplication simultaneously using the Reed-Muller (RM) codes which can be applicable for coded computations in distributed systems or stabilizer codes in quantum computing and can be a preceding step for constructing code-based FHE schemes. As the order of RM codes increases after multiplication, we also propose a bootstrapping technique to preserve the order of RM codes after the addition or multiplication by proposing three consecutive transformations that create a one-to-one relationship between computations on messages and that on the corresponding codewords in RM codes.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Error-correcting codesfully homomorphic encryptionhomomorphic computationpost-quantum cryptographyReed-Muller (RM) codes.
Contact author(s)
mypurist @ gmail com
History
2020-05-16: revised
See all versions
Short URL
https://ia.cr/2020/565

CC BY

BibTeX

@misc{cryptoeprint:2020/565,
author = {Jinkyu Cho and Young-Sik Kim and Jong-Seon No},
title = {Homomorphic Computation in Reed-Muller Codes},
howpublished = {Cryptology ePrint Archive, Paper 2020/565},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/565}},
url = {https://eprint.iacr.org/2020/565}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.


text:
# A Chess Puzzle, Part III: The Pawns, Knights and Kings

Part III of A Mathematical Chess Puzzle:

This is part III of my series of posts on the “Chess Density Problem”. In Part I, I introduced the problem and laid out some definitions to clarify what I meant by some of the terms such as “Board” and “Density”. In Part II I gave everyone a breather.  Hope you’ve rested up. In this one the math is going to be a bit thick, but the purpose of it all will be to prove this first theorem:

### The Chess Density Theorem – Pawn, Knight and King

DENSITY THEOREM 1: For Pawns, Knights, and Kings, their asymptotic density $\delta$ on the infinite board ($B_{\omega}$) is given by:

1.1) $\delta(P) = 1/2$.

1.2) $\delta(N) = 1/2$.

1.3) $\delta(K)= 1/4$.

In other words, on an infinite chess board, you can pack at most half of the squares with “friendly” Pawns or friendly Knights, and only a quarter of the board with friendly Kings. As a reminder, by “friendly” I mean that none of the pieces are threatening each other by standard chess rules.

### Plan of Attack

As a starting point, we can note that the solutions found on the standard 8-board can be seen as built up from simple “tile” patterns made of identical small boards:

These tiles each have the densities that are claimed by the Density Theorem above. If we can prove that no such tiles can have a greater density, we can show that this must hold for larger boards. The way which we will do this is to define a precise way to “measure” the density of any arbitrary block of squares, and prove some useful properties of that measure-function.

### Definitions

It always helps to define things precisely. There are a lot of fancy symbols, but the general ideas should be clear.

### The Pieces

The six standard Chess pieces are King, Queen, Bishop, Knight, Rook, and Pawn, which we will denote with the initials {K,Q,B,N,R,P}, respectively. To this set we will also add the “Empty” piece, denoted $\varnothing$, which indicates that a square is empty.

The set of all pieces including the empty piece will be denoted

$$\mathscr{P} = \{K,Q,B,N,R,P,\varnothing \}$$

We include that “empty” piece to allow us to explicitly specify that a square is empty.

### Control Zones

DEFINITION: The control zone of a piece X at position $x$ on a board B is the set of all other locations $y \in B$ which (by the standard rules of chess) are subject to attack by X (with no other pieces on board).

The Control Zones of the Pawn, Knight and King are shown in blue below:

Pawn

Knight

King

One thing to note about these three pieces is that their control zones can be defined by a specific finite set of integer offsets from the location of the piece itself. The same cannot be said for the other three pieces (Rook, Bishop, Queen), as their Control Zones are not defined by a fixed set of offsets, but a set of directions on the board, by which they can attack (again, assuming that there are no other pieces blocking the way).

The Control Zone directions for the Rook, Bishop and Queen are shown below.

Rook

Bishop

Queen

As we begin to work with the infinite boards we will see that this difference between the two sets of pieces profoundly affects how “dense” they can be.

In particular, on infinite boards the control zones of the Rook, Bishop and Queen are also infinite.

### Chess Positions

A lot of the definitions below are just stuff I made up. If they correspond to standard chess terms I will mark them with (standard). If I feel that the definition may not be clear, I will give an example as well.

DEFINITION: For a given board $B$ and any subset $\Omega \subseteq B$, a chess position $\Phi$ on $\Omega$ is simply a function $\Phi$ that for each location $x \in \Omega$ there is a piece $p \in \mathscr{P}$ given by $p = \Phi(x)$ at that location. That is, it is a function

$$\Phi: \Omega \rightarrow \mathscr{P}$$

For all of the chess positions we are considering for this puzzle, we only have one kind of piece on the board at the time. And so we will call them “Pawn-positions”, “Queen-positions” etc. Thus if $\Phi$ is a King-position on $\Omega$, then it is a function $\Phi: \Omega \rightarrow \{K, \varnothing\}$.

DEFINITION (standard): A Position is called Unguarded if no piece in the position is in the control zone of another piece. In other words, unguarded positions are positions where the pieces are all “mutually friendly”.

DEFINITION: If $n > 0$ is an integer and $X$ is a (non-empty) chess piece, define $\mathscr{U}(n,X)$ to be the set of all “Maximally Unguarded” X-positions using only piece $X$, on the n-Board. That is, if there are no other unguarded positions with a larger number of pieces.

### Measurement of Positions

DEFINITION: For any position $\Phi$ on $\Omega$, we can define the size ($\vert \Phi \vert$) and weight ($\Vert \Phi \Vert$) of that position by the number of elements in its domain $\Omega$ and the number of non-empty locations in its range, ie

$$\vert \Phi \vert = \vert \Omega \vert$$

$$\Vert \Phi \Vert = \vert \{ x \in \Omega: \Phi(x) \neq \varnothing \} \vert$$

EXAMPLE: In the little 4-board below, there are four queens, and the rest are empty.

Four friendly Queens

So, following the defintion above, the board $\Omega$ is the 4×4 board, and its position function $\Phi$ maps every square to the empty piece $\varnothing$ except for the four squares that are mapped to the Queen. The size of the position $\Phi$ is simply the number of squares in $\Omega$, ie $\vert \Phi \vert = \vert \Omega \vert = 16$, while the weight of the position is the number of squares mapped by $\Phi$ to the Queen, ie $\Vert \Phi \Vert$ = 4.

DEFINITION: The for any position $\Phi$ on some board $\Omega$ its Density (denoted $\delta(\Phi)$ ) is the ratio of its weight divided by the size of the position , ie

$$\delta(\Phi) = \frac{\Vert \Phi \Vert}{ \vert \Phi \vert }$$

DEFINITION: The for any integer n>0, the n-Density (denoted $\delta_n(X)$ ) of a piece $X$ on the n-Board is the maximum density of all possible unguarded positions $\Phi \in \mathscr{U}(n,X)$ ie

$$\delta_n(X) = \max_{\Phi \in \mathscr{U}(n,X) }\delta(\Phi)$$

EXAMPLE: So, in the previous example for the unguarded queens on the 4-board, it can be seen that:

$$\delta_4(Q) = 4/4^2 = 4/16 = 1/4$$

With all of these preliminaries out of the way, we can now define what we really mean by the density of a piece on an infinite board:

DEFINITION: The Asymptotic Density (denoted $\delta(X)$ ) of a piece $X$ on the infinite board $B_\omega$ is the limit (if it exists) of the n-Density $\delta_n(X)$ of piece X as $n \to \infty$ ie

$$\delta(X) = \lim_{n \to \infty }\delta_n(X)$$

### The Linear Density Measure

For each of the pieces mentioned in the theorem above, their claimed density is of the form $\delta = 1/m$, where $m$ is some positive integer. It turns out that working with density ratios directly is tricky, so we will look at a different “measure” of density that turns out to be easier to work with, as we break a large board into tiles.

So, suppose $w$ is the weight of an X-position $\Phi$ on a set $\Omega$ of size $s$. Then the density $\delta$ is given by

$$\delta = \frac{w}{s}$$

and so if indeed $\delta=1/m$ then

$$1 = m\delta = m\frac{w}{s}$$

and therefore $mw = s$, which is to say that whenever a position has density 1/m, then we can also write

$$mw – s = 0$$

Using this fact, for any sub-position $\Upsilon \subseteq \Phi$ let’s define the “m-linear density” measure function $\Lambda_m(\Upsilon)$ by

$$\Lambda_m(\Upsilon) = m \Vert\Upsilon\Vert – |\Upsilon|$$

Intuitively, what this measure value tells you is how much over or under the expected density a position is from $1/m$. if the value is exactly zero then the density is exactly $1/m$.  We now present a lemma (ie, a small theorem we can prove now and use later):

LEMMA 1: If $\Phi$ and $\Upsilon$ are two positions defined on disjoint subsets $S$ and $T$ of a board $B_n$, and $m > 0$ is an integer then

$$\Lambda_m(\Phi \cup \Upsilon) = \Lambda_m(\Phi) + \Lambda_m(\Upsilon)$$

that is, the m-linear density of the union of two disjoint positions is the sum of the m-linear densities of each.

PROOF: Follows immediately from the fact that the size of the union of disjoint sets is the sum of the sizes, and regrouping of terms:

$$\Lambda_m(\Phi \cup \Upsilon) = m\Vert\Phi \cup \Upsilon\Vert – \vert\Phi \cup \Upsilon\vert$$

$$=m(\Vert\Phi\Vert + \Vert\Upsilon\Vert) – (\vert\Phi\vert + \vert\Upsilon\vert)$$

and so, regrouping like terms:

$$=(m\Vert\Phi\Vert – \vert\Phi\vert) + (m\Vert\Upsilon\Vert -\vert\Upsilon\vert)$$

$$= \Lambda_m(\Phi) + \Lambda_m(\Upsilon)$$

QED (Quod Erat Demonstrandum = which was to be proved).

$\blacksquare$

LEMMA 2: There exists a positive constant $C > 0$ such that the 2, 2, and 4 linear densities $\Lambda(\Omega)$ of maximal unguarded positions $\Phi$ of Pawns, Knights and Kings on the n-board are bounded by the following expressions:

$$\forall \Phi \in \mathscr{U}(n,P): 0 \le \Lambda_2(\Phi) < C * n \tag{2.1}$$

$$\forall \Phi \in \mathscr{U}(n,N): 0 \le \Lambda_2(\Phi) < C * n \tag{2.2}$$

$$\forall \Phi \in \mathscr{U}(n,K): 0 \le \Lambda_4(\Phi) < C * n \tag{2.3}$$

PROOF: We will start with the formula for the Pawn; the other proofs will be similar. We first note that for the $2 \times 2$ tile $T$ for the Pawn case, the linear density is exactly $\Lambda_2(T) = 2*2 – 4 = 0$. Is it possible to place any more than two “friendly” pawns in the tile $T$? No, because each cell in the first row attacks the diagonal cell in the second row, so you can choose at most one pawn from each “attack pair”. This means that for any unguarded pawn position $\Phi$ on the $2 \times 2$ board, its linear density is bounded by $\Lambda_2(\Phi) \le 0$.

Attack Pairs

So now what about the 2-linear density for the $n \times n$ board $B_n$? Note that if $n$ is divisible by two we can completely fill up the entire board with these 2-tiles, like this:

Tiled 8-board

Now note that since this n-board (for $n$ = 2k even) is the disjoint union of these $2 \times 2$ tiles $T_1, T_2, …T_{k^2}$, then for any unguarded position $\Phi \in \mathscr{U}(n,P)$, its 2-linear density must be the sum of the densities of these tiles (this follows from Lemma 1) But the positions on those tiles must themselves be unguarded positions, and so for each tile, $\Lambda_2 \le 0$. Therefore, we must have that:

$$\Lambda_2(\Phi) = \Lambda_2(T_1) + … + \Lambda_2(T_{k^2}) \le 0$$

since all of the terms are known to be $\le 0$. Note that we have also shown that the maximum value of 0 can be attained.

We have just shown that for all even n, and unguarded positions $\Phi$ on the n-board, the value of $\Lambda_2(\Phi)$ is bounded by 0. What about odd n, where $n = 2k+1$? In that case, we can break up the n-board into the disjoint union of $k^2$ tiles which are $2 \times 2$, $k$ tiles which are $1 \times 2$, $k$ tiles which are $2 \times 1$, plus a $1 \times 1$ square, like this:

Odd nxn Board, tiled

So now we can play the same game here, and compute the largest possible values of $\Lambda_2$ for each of these little blocks. For both the 1×2 and 2×1 tiles, we have no attack-pairs, and so we can fill both squares with pawns, giving them a maximal 2-density of $\Lambda_2 = 2*2 -2 = 2$. Similarly, we can fill the single 1×1 square with a pawn, for a 2-density of $\Lambda_2 = 2*1 -1 = 1$.

Now there are $k$ of each of the 1×2’s and 2×1’s, and $k^2$ of the 2×2’s and so altogether we can bound the 2-density of the odd n-Board by the sum of these bounds, ie

$$\Lambda_2(\Phi) = k^2 \Lambda_2(2×2) + k\Lambda_2(1×2) + k\Lambda_2(2×1) + \Lambda_2(1×1)$$

$$\le k^2*0 + k * 2 + k * 2 + 1$$

$$\le 4k + 1 \le 4k + 2$$

$$\le 2 * (2k + 1) \le 2n$$

And so, what all this means is that for the Pawns, given any unguarded position $\Phi$ on any n-Board, we can bound the largest possible value for its 2-density with a value of C=2, ie,  $\Lambda_2(\Phi) \le 2n$. This proves part (2.1).

Similarly, for the King, we can play the same game, but now using the 4-density $\Lambda_4$. In this case, we can only place one king on the 2×2 tile (since each corner attacks all the others, forming an “attack quadruple”). This gives the 2×2 tile the maximal 4-density of $\Lambda_4 = 4*1 – 4 = 0$. And in the same way, we can show that for even n, the 4-density is bounded by 0, and for the odd case where $n=2k+1$, we can place one king each on the 1×2 and 2×1’s (for a density of $4*1 – 2 = 2$), and one king on the single cell (for a density of $4*1 -1 = 3$). Putting it all together, the King’s 4-density on the odd n-board is given by

$$\Lambda_4(\Phi) = k^2 \Lambda_4(2×2) + k\Lambda_4(1×2) + k\Lambda_4(2×1) + \Lambda_4(1×1)$$

$$\le k^2*0 + k * 2 + k * 2 + 3$$

$$\le 4k + 3 \le 6k + 3$$

$$\le 3 * (2k + 1) \le 3n$$

And so for the King we can use the constant $C=3$, so $\Lambda(\Phi) \le 3n$.  This proves (2.3).

Finally, for the Knight, we have to work a bit harder. The Control Area around the knight extends beyond just a single square, and so we need to use a 4×4 tile to build up a solution. In the 4×4 tile we showed above, we were able to fill exactly half (8) with friendly knights, giving the 4×4 tile a 2-density of $\Lambda_2 = 2*8 – 16 = 0$, just like the Pawn. To prove that this is the best we can do with the 4×4 tile and knights, consider the following “attack pairs” of knights on the tile:

Knight attack-pairs

We see that there are eight pairs of mutually-attacking squares by knight moves, meaning we can choose at most one from each pair on which to put a knight. This means there can be at most eight friendly knights on any 4×4 tile. And so, just as with pawns we have $\Lambda_2 \le 0$ on any 4×4 tile.

By the same arguments we gave before, if $n$ is divisible by 4, then we can show that an unguarded knight position on an n-board has density $\Lambda_2 \le 0$, and for all other $n = 4j + k$, with $k \le 3$, we can cover the n-board by $j^2$ 4×4 tiles, $2j$ tiles on the border of size $k \times 4$, which can be shown to never have 2-linear densities greater than $\Lambda_2 = 4$, plus a $k \times k$ corner tile, with density no greater than 1. Putting this altogether, it can be shown that a value of $C=1$ is good enough for knights to bound $\Lambda_2(\Phi) \le C*n$ for any unguarded $\Phi \in \mathscr{U}(n, N)$. This proves inequality (2.2) and the Lemma.

$\blacksquare$

PROOF OF THEOREM 1

The theorem is in three parts, for the Pawn, Knight, and King. We will only show the proof for the Pawn, the other proofs are identical in structure. From Lemma 2, formula (2.1), there is a positive constant C such that for all positive integers $n$ and maximally unguarded Pawn positions $\Phi$ on the n-Board, we have

$$0 \le \Lambda_2(\Phi) < C * n$$

which by definition of $\Lambda_2$ means that

$$0 \le 2*\Vert \Phi \Vert – \vert \Phi \vert < C*n$$

Dividing both sides by $\vert \Phi \vert$ we have

$$0 \le \frac{2*\Vert \Phi \Vert}{\vert \Phi \vert} – 1 < \frac{C*n}{\vert \Phi \vert}$$

But since on the n-Board $\vert \Phi \vert = n^2$, we can use the definition of the position density $\delta(\Phi)$ to obtain

$$0\le 2\delta(\Phi) – 1 < C/n$$

in other words (adding one and dividing by 2):

$$\frac{1}{2} \le \delta(\Phi) < \frac{1}{2} + C/2n$$

And so, since $C$ is a positive constant, as $n$ goes to infinity, the value of $C/2n$ becomes vanishingly small, and in the limit goes to zero. By the definition of the asymptotic density, then, the value of $\delta(Pawn)$ is exactly 1/2, which was to be proved.

$\blacksquare$

### Unguarded Positions on the Infinite Board

So far, we have been talking about the density of unguarded positions on large but finite boards $B_n$, and their limit as $n \to \infty$ (“n goes to infinity”). But what happens when $n$ gets there? Is there a position on the infinite board $B_\omega$ that is still “unguarded”, and what do we mean by “maximal”?

If we use the finite solutions as a guide, we can quickly propose positions $\Phi_p$ on $B_\omega$ for p = Pawn, Knight, and King. Recall that a “position” on any board B is simply a function mapping every element $(x,y) \in B$ to a member of $\mathscr{P}$, the set of all chess pieces including the “empty” piece $\varnothing$. The omega board consists of all integer pairs $(x,y)$ such that x and y are greater than or equal to zero (so, the bottom left corner square is $(0,0)$).

The solutions are:

$$\Phi_P(x,y)= \begin{cases} P, & \text{if y is even} \\ \varnothing, & \text{otherwise} \end{cases}\tag{Pawn}$$

$$\Phi_N(x,y)= \begin{cases} N, & \text{if (x+y) is even} \\ \varnothing, & \text{otherwise} \end{cases}\tag{Knight}$$

$$\Phi_K(x,y)= \begin{cases} K, & \text{if x is even AND y is even} \\ \varnothing, & \text{otherwise} \end{cases}\tag{King}$$

It is relatively straightforward to see that when restricted to a finite n-Board these positions are the same as the ones using the “tiles” we defined above, and so they are still unguarded positions. But in what sense are they “maximal”? The weight of these positions are infinite, so how can one infinite position have a greater weight than another? The answer is, they are maximal in that expanding the position to include additional pieces in locations where the original position does not, must also have a hostile piece in the set.

The proof that these positions are indeed maximal, is left as an exercise to the reader.

### What the infinite solutions look like

Here are the Knight and King Positions for the infinite boards, as viewed from a great distance (the white squares are the empty ones):

King Position on the 300 Board

Knight Position on the 300-Board

This is not actually an infinite board, of course, but a 300 x 300 one. As you can see, as the number of squares on a side increases to infinity, the individual pieces blur out to form a shade of grey, about 50% black for the Knight, and 25% black for the King. Another way to define the density, is that if you were to throw a dart at one of the boards (say, the King), the odds would be 1/4 that your dart would hit a King.

In the next post, we will look at the Bishops, Rooks, and Queens, and see just how strange and different the situation becomes, especially as we venture into larger transfinite boards.


text:
# Electron distribution in a C-S bond

My lecturer said that in a $\ce{C-S}$ bond, sulfur is slightly $\delta^{-}$ and the carbon slightly $\delta^{+}$, although they have (almost) the same electronegativity. What is the cause of this phenomena if it is not electronegativity?

I think your lecturer would have been more correct had he said that the carbon-sulfur bond reacts as if the sulfur is slightly $\delta^{-}$ and the carbon slightly $\delta^{+}$.

Sulphur is a larger atom so it has more, loosely held electrons than carbon. This means that a sulfur atom is more polarizable than a carbon atom. Although carbon and sulfur have similar electronegativities, the effect of this increased polarizability for sulfur is that sulfur behaves or reacts as if the bond were polar. Take the case of nucleophilic attack on a $\ce{C-S}$ bond. As the nucleophile approaches, the $\ce{C-S}$ bond will tend to polarize because of sulfur's polarizability. And in which direction will the bond polarize? Electron density will prefer to shift such that it resides on the larger atom (charge to size effect), sulfur.

This is the same argument used in the case of a carbon-iodine bond. Again the two atoms have similar electronegativities (carbon = 2.55, iodine = 2.66), so although the bond is not polar based on electronegativity considerations, the polarizability of the iodine allows the bond to react as if it were polar when a nucleophile approaches.

• Although I think everything you said is correct, I still guess it depends on what kind of bond it is (single, double, triple) and what saturates the carbon. But in the most simplest case you are absolutely right. Sep 3 '14 at 17:51
• This was exactly what I thought, but then why isn't there a $\delta^{-}$ on sulfur if charge can be distributed there better? It seems to me that if the electrons shift towards the sulfur atom, they will become more stable because there is less interaction with the other electrons of the atom on sulfur.
– Jori
Sep 3 '14 at 18:56
• Oh wait, perhaps I get it. The electrons are of course confined to the C-S bonding MO (which is symmetric I guess?). So not until some reaction happens that breaks this bond, can the size of the sulfur atom (and its polarizability) come into play and stabilize these electrons (thus behaving as if it was $\delta^{-}$). Is that right?
– Jori
Sep 3 '14 at 19:13
• Yes, you've got it. The electronegativities are similar, so the bond is not polar. But when a reactant approaches, the polarizable bond will polarize such that electron density shifts towards sulfur (or iodine).
– ron
Sep 3 '14 at 19:21


text:
## 留言板

Effects of calcium content on the performance of HZSM-5 nanoparticles of 150 nm with Si/Al ratio = 230 in the methanol to olefin conversion were investigated. The parent and modified catalysts showed their largest yields of ethylene and propylene at 490 ͦ C and lower WHSV (= 3.3 h−1). The selectivity for propylene over HZSM-5 was 0.45 at 490 °C whereas it was promoted to 0.51 over Ca27-HZSM-5 (Ca/Al = 27). With decreasing temperature from 490 to 440, and 390 °C, the yield of propylene and ethylene remained nearly constant at 0.13−0.14 and 0.10−0.11 over Ca27-HZSM-5, respectively; more narrow than the corresponding range of yields for HZSM-5 (0.10−0.14 and 0.08−0.12). FT-IR results confirmed the formation of oxygenated and poly alkyl aromatic species in the carbon deposits. TG results indicated that oxygenate coke was formed and converted to heavier poly aromatic coke species with time. Increasing Ca in the porous structure of HZSM-5 may lead to heavier aromatic carbonaceous deposits. In general, Ca content positively affected activity through modification of the density, strength, and accessibility of Brønsted and Lewis acid sites. Long-term MTO activity test of HZSM-5 with Ca/Al = 27 showed stable performance over 100 h, although with an oscillatory feature.

Recently, the disposal of waste by beneficial and environmentally friendly methods has attracted great attention. In this work, we have studied the production of high-value carbon nanotubes (CNTs) which have remarkable applications by catalytic pyrolysis of sugarcane bagasse (SCB) as an agricultural waste using a two-stage process. Various reaction factors including the effects of zeolite catalysts (HZSM-5, HMOR, and HY), pyrolysis temperatures (450−700 °C), and SCB/ZSM-5 ratios (3−12) on SCB pyrolysis were investigated to generate CNTs from pyrolysis products. A Co-Mo/MgO catalyst was used for growing CNTs via the decomposition of pyrolysis products. The morphological structure and quality of CNTs were characterized using TEM and Raman spectroscopy, while the fresh Co-Mo/MgO catalyst was characterized by XRD and TPR analyses. The results showed that zeolite type, pyrolysis temperature, and SCB/ZSM-5 ratio had significant effects on the CNTs yield. The optimum carbon yield (24.9 wt%) was achieved using the HZSM-5 catalyst at the pyrolysis temperature of 500 °C and with the SCB/ZSM-5 ratio of 6. TEM observations confirmed the growth of bamboo-like carbon nanotubes (BCNTs) and carbon nano-onions (CNOs) in different proportions according to the reaction parameters. Also, CNTs with the largest diameter distribution range (7−76 nm) were produced using the SCB/ZSM-5 ratio of 6. Raman spectra demonstrated the production of high-quality CNTs under all studied conditions

Electrocatalytic water splitting is one of the most prospective technology for hydrogen production. Molybdenum disulfide (MoS2), as one of the most promising non-noble metal electrocatalysts, suffers from the disadvantages of limited catalytic sites and weak conductivity which urgently needs to be further optimized. Herein, the C3N4-Ti4O7-MoS2 heterostructure is constructed through a simple hydrothermal strategy. The interfacial interaction between the active components leads to more exposed active sites, the redistribution of the surface charge, the optimization of the hydrogen adsorption kinetics and stability, which makes up the typical shortcomings of MoS2. The results indicate that the interface effect endows C3N4-Ti4O7-MoS2 catalyst with excellent electrocatalytic activity for hydrogen evolution reaction (HER). The current density of 50 mA/cm2 for HER is obtained at the overpotential of 300 mV, with the lower Tafel slope (54 mV/dec) and stable catalytic activity over 33 h, which is much better than that of the pure MoS2. This work indicates that the interface effect, as an effective strategy for rational design of MoS2-based electrocatalysts, is crucial to the future development of catalytic hydrogen production.

The isomerization and hydroformylation of butene under the catalysis of Rh-BIPHEPHOS were investigated by varying the butene feed and reaction temperature. The results indicate that in the presence of syngas, with 1-butene as feed, more isomerization product (i.e. 2-butene) is detected in comparison with the hydroformylation products, whereas with 2-butene as the feed, the hydroformylation was superior to isomerization. Due to the equilibrium limit between 1-butene and 2-butene, the increase of temperature shows a great positive effect on the isomerization reaction. Furthermore, under the catalysis of Rh-BIPHEPHOS, more n-pentanal is always formed than i-pentanal, as the larger bite angle of BIPHEPHOS restricts the intermediate rearrangement in the formation of i-pentanal.

Waste gasification has the potential to contribute to China’s transition towards carbon neutrality and zero waste cities via the recirculation of waste as secondary carbon feedstock for the production of chemicals with lower/and or zero carbon footprint, green hydrogen with zero carbon footprint and CO2-neutral synthetic liquid fuels. With China’s significant coal gasification capacity and associated experiences and expertise, Coal-to-X could act as a bridge to Waste-to-X for carbon intensive sectors such as the waste management, chemical production and mobility sectors. To illustrate the opportunities in these areas, this article presented highlights from dynamic global developments in waste gasification, focusing on pioneering industrial developments in Germany between 1980’s−2000’s as well as current international developments. Lessons learnt from previous and current waste gasification project deployment are shared and enabled the identification of problems which will have to be addressed in the transition from coal gasification towards mono-waste gasification technologies. Additionally, a qualitative evaluation of gasification technologies pointed to the strengths and weaknesses of fixed-bed, fluidized-bed and entrained-flow gasification principles in their application for waste gasification.

The chemical and mineralogical characteristics of fly ash from a municipal solid waste incineration (MSWI) in China and the influence of processing parameters on heavy metals removal during leaching were investigated in this work. The fly ash particles had complex surface structure with limited specific surface area. The alkali chloride and metal salts in MSWI fly ash showed evidently impact on leaching efficiency. Metal leachability was related to their properties and speciation in fly ash. Water-soluble salts such as KCl, NaCl and CaCl2 in fly ash were easily washed out. In this study, removal efficiency by water washing was achieved to 93.1% for Cl, 41.4% for Na, 48.5% for K and 24.8% for Ca, respectively. Mineralogical analysis also revealed change of fly ash mineral phases and specification distribution after water washing. Under liquid to solid ratio of 40∶1 L/kg and treatment time of 120 min, the leaching process achieved high dropping yields of toxicity characteristic leaching procedure (TCLP) concentrations for Cu, Zn Cd and Pb (80%−100%), moderate dropping yields for As (30%−80%) and relatively low dropping yields of Ni (< 30%). In addition, heavy metals such as Pb and Zn in fly ash with twice water washing treatment at a low liquid-solid ratio could reach lower TCLP concentrations. The result indicated that the combination process of twice water washing and one acid washing could significantly reduce the environmental risk of MSWI fly ash.

The effect of desulfurizer, modified TiO2 prepared by different methods on the NO emission from inferior coal burning and the adaptability of coal type were studied by using a tube furnace. The prepared Zr-TiO2 and the char were characterized by XRD, BET, SEM, XPS, TGA and XRF, and the mechanism of denitrification was explored. The results show that the addition of desulfurizer can promote NO emission. When the combustion temperature is 850℃, oxygen flow rate is 40 mL/min and the desulfurizer is MgO, the NO emission is the lowest as the catalyst of 5%Zr-TiO2 prepared by impregnation method is added, which is 51.0% lower than that with addition of pure TiO2 and 84.6% lower than that with pure coal under the same conditions. The catalyst 5% Zr-TiO2 can be applied to the coal with sulfur < 3% and ash < 30%, having a wide application range . The doping of Zr can inhibit the growth of grain, enhance the active component, increase the content of adsorbed oxygen, promote the transformation of the valence states of the elements, accelerate the devolatilization of volatiles, promote the combustion, increase the specific surface area of chars, and enhance the ability of heterogeneous reduction of chars.

A series of metal phosphides including MoP, WP, CoP and NiP was prepared by temperature-programmed reduction with hydrogen from different phosphorus precursors. The effect of phosphorus precursor and feed H2/CO ratio on the catalytic performance of metal phosphides in the methanation was investigated. In comparison with diammonium hydrogen phosphate (DAP), phytic acid (PA) as a chelating agent can effectively disperse the metal precursor, reduce the reduction temperature, promote to form pure phosphide phase, and give the phosphide catalyst a higher surface area and a smaller particle size; as a result, the metal phosphides prepared with PA as a phosphorus precursor exhibit higher catalytic activity in methanation. In addition, the catalytic activity of various metal phosphides in methanation follows the sequence of MoP > WP > CoP > NiP. A high H2/CO ratio in the feed is favorable for the methanation over the phosphide catalysts; the selectivity to methane increases with an increase in the H2/CO ratio.


text:
LTSpice - varistor component

What is the constitutive relashionship between current and voltage of a varistor in LTSpice? For example, if I set the control voltage V=1V and Rclamp=2, what is the formula to evaluate the resistance of varistor? I tried to do this simulation (I used a 10V voltage source in serie with R1=1 and a varistor), but the result it's strange for me. The current on R1 is 3A, $V(R1)=R1\cdot I(R1)=1\cdot3=3V$, but the resistance of varistor is not Rclamp=2 (is 7/3=2.3). Thank you very much.

• Why don't you plot the current when the applied voltage is a ramp - this seems likely to give you what you want. – Andy aka Nov 8 '16 at 13:36

If you read in the LTspice manual, you'll see that it says it's breakdown voltage is set by the voltage applied at its control terminals. The voltage can be of any sign, any polarity (it counts as abs(V(ctl))), and the calculation is like this: if your applied voltage is 10V, the series resistance is 1 Ohm, Rclamp=1 and the control voltage is 1V (I presume), then the varistor will breakdown at 1V (the controlling voltage), meaning from the total of 10V you'll have 10-1=9V which, divided by the total resistance of 3 Ohms results in 3A. If your source voltage is 7V, series resistance is 2 Ohms, Rclamp=1.5 and controlling voltage 3V => (7-3)/(2.5+1.5)=4/4=1A.


text:
# Expected length of a sequence that contains all words of a given length.

Fix some alphabet $\Sigma$ and a positive integer $n$. What is the expected number of random letters drawn from $\Sigma$ until all length-$n$ words are present?

For example, let $\Sigma = \{0,1\}.$ Then the string "10" contains all possible 1-letter words, ie "0" and "1". The expected length for a random string is simply the coupon-collector problem with 2 cards... so the expected length is 3.

But it's more complicated when words can overlap. For the same alphabet and $n=2$ we can see that the string "00110" has all 2-letter words, and I claim that's the shortest string that does. But what's the expected length of a random string that contains all four strings "00", "01", "10", and "11"? The usual coupon-collector approach doesn't seem to work.

Well, here's a solution, but it's not pretty.

As noted in my answer to Cover time chess board (king), there is in principle no difficulty in answering this question. Calculating the expected cover time of the set of patterns $\cal S$ reduces to calculating the expected hitting time of every possible non-empty subset $A$ of $\cal S$:

$$\mathbb{E}(\text{cover time})=\sum_A (-1)^{|A|-1} \mathbb{E}(T_A)\tag1$$

These hitting times are defined by $T_A=\inf(n\geq 0: X_n\in A)$. These, in turn, can be found using a technique from Section 14.3 (Patterns III) of Problems and Snapshots from the World of Probability by Blom, Holst, and Sandell.

For instance with strings of length two we find $$\mathbb{E}(T_{00,01,10,11})=2$$ $$\mathbb{E}(T_{00,01,10})=\mathbb{E}(T_{01,10,11})=5/2,\quad \mathbb{E}(T_{00,10,11})= \mathbb{E}(T_{00,01,11})=9/4$$ $$\mathbb{E}(T_{00,01})=\mathbb{E}(T_{00,10})=\mathbb{E}(T_{00,11})=\mathbb{E}(T_{01,10})=\mathbb{E}(T_{01,11})=\mathbb{E}(T_{10,11})=3$$ $$\mathbb{E}(T_{00})=\mathbb{E}(T_{11})=6,\quad \mathbb{E}(T_{01})=\mathbb{E}(T_{10})=4$$

Plugging all this information into (1), we find that the expected time to see all four patterns $00,01,10$, and $11$ is $19/2=9.5$.

Just for fun, I've calculated the expected time to see all eight patterns of length three to be ${89259/ 3640}= 24.5217$.

Update: This is wrong - sorry, I misread the question, I understood that we were interested in getting all permutations (words with different letters).

For $n=2$ it's not hard to see that the expected length is 5 : expected length of first run (2) + expected length of second run (2) + 1. For $n>2$ it seems more difficult.

Applying the coupon-collector approach, one would say that the expected number of tries to collect the $m$-th permutation (among $n!$ permutations) is $1/p_m = n^n/(n!-m)$ and so

$$E_n = n^n \left( \frac{1}{1} + \frac{1}{2} + \dots +\frac{1}{n!} \right)=n^n H({n!})$$

This, of course, is an approximation, because it assumes that each new letter of the sequence gives a new $n$-word, independent of the previous ones; but the overlapping must introduce some dependence. It's not clear, however, the sense of this dependence. And this, together with the fact that for large $n$ the probability of a word being a permutation (even for the "first coupon") is low, leads to think that the approximation might be reasonable. Numerical evidence sees to agree.

Eg: for $E_5 = 16777.7$, empirically I get $\approx 16730$.

Update: Actually we are not interested in getting all permutations ($n!$) but all words ($n^n$). The above coupen-collector approach can also be applied, giving us $E_n \approx n^n H(n^n) \sim n^{n+1} \log(n)$, but the independence assumption is less justified, and the result less precise.

We can regard each word as a vertex on a directed graph, or state of a doubly-stochastic Markov chain ($n$ equal non null entries in each row-column). We are asking then about the cover time of this chain. This could help to locate material. For example, here (section 2.3) it is stated as a known result (but references are missing) the asympotic

$$E_n \sim n^n \log(n)$$

Also, see here (page 11.3.3).

• Could you expand on the argument leading to mean length 5 when n=2? – Did Apr 25 '13 at 15:31
• @Did: You can easily get that result, only by misreading the problem statement ;-) updated – leonbloy Apr 25 '13 at 16:18
• Kudos for your sense of humour. (Unrelated: I am once again somewhat mystified by the way votes work on this site...). – Did Apr 25 '13 at 17:31
• Well, everyone seems predisposed to vote up any answer from a +5K user. – leonbloy Apr 25 '13 at 17:54


text:
# Lenz's Law

on . Posted in Electromagnetism

Lenz's law, abbreviated as $$\epsilon$$, is the direction of the current induced in a conductor by changing magnetic field.

## Lenz's Law formula

$$\large{ \epsilon = -N \; \frac{ \partial \Phi_B }{ \partial t } }$$
Symbol English Metric
$$\large{ \epsilon }$$  (Greek symbol epsilon) = induced EMF $$\large{V}$$  $$\large{V}$$
$$\large{ \partial \Phi_B }$$ = change in magnetic flux $$\large{Wb}$$ $$\large{Wb}$$
$$\large{ \partial t }$$ = change in time $$\large{sec}$$ $$\large{s}$$
$$\large{ N }$$ = number of turns in coil $$\large{dimensionless}$$


text:
# Measurement Studio for .NET Languages

cancel
Showing results for
Did you mean:

## write code in VB.Net to produce analog output for Advantech USB 4716

I'm still confuse on how to write code to produce analog output using advantech usb 4716

i'm using VB 2010.Net as programming language

this is previous code that i used, but when i run the program the textbox display 0. and when i measure the analog output channel using voltmeter 0 V is display.

how can i produce 5V analog output.

I already add the automation.DAQ.dll preference in my project. And i also already, setting the Instant AOCtrl1.

pls show me some guides.

Message 1 of 4
(2,580 Views)

## Re: write code in VB.Net to produce analog output for Advantech USB 4716

VB.NET isn't NI

What are you using that is NI?

Message 2 of 4
(2,577 Views)

wrong place?
Message 3 of 4
(2,573 Views)

## Re: write code in VB.Net to produce analog output for Advantech USB 4716

If you are not using any NI product, why would you be posting here???

Message 4 of 4
(2,563 Views)


text:
g++ exceptions

Recommended Posts

Not sure if this would be better in the Unix forum or not, but maybe others here have had this experience. We've got 3 binaries that we compile here. The first 2 compile and run just fine. They catch exceptions and so on just dandily. All 3 binaries share a common source base that is where the exceptions are thrown at. The third binary, when compiled, will always call terminate() when an exception is thrown (we explicitely do NOT use exception specifications to avoid the hassle they bring, and the stack trace shows no sign of an unexpected exception). We've even tried something like this: try { throw std::exception(); } catch(...) { } and terminate() is *still* called. We're pretty much at our wits end here. We can't figure out why the first 2 binaries work just fine and the third fails. As I said, they share a common source base and they use the same compile options. Is it a bug in gcc 3.3.x or am I maybe doing something wrong somewhere? We've also thrown on -fexceptions and -fno-enforce-eh-specs but to no avail. I appreciate any help ideas anyone might have.

Share on other sites
Quote:
 Original post by Chozotry {throw std::exception();} catch(...) {}and terminate() is *still* called. We're pretty much at our wits end here. We can't figure out why the first 2 binaries work just fine and the third fails. As I said, they share a common source base and they use the same compile options. Is it a bug in gcc 3.3.x or am I maybe doing something wrong somewhere?
It's always the compiler's fault isn't it? [wink]

If it's nothing but that above code, then I'd say compiler bug, but it's not nothing but the above code, is it?

Share on other sites
Of course not. :)
It's about 100,000 lines of code all mashed together to make a mess no one dares walk through. I suppose that's the only thing to do isn't it? Walk through it all one line at a time... ugh.

Share on other sites
Quote:
 Original post by ChozoOf course not. :)It's about 100,000 lines of code all mashed together to make a mess no one dares walk through. I suppose that's the only thing to do isn't it? Walk through it all one line at a time... ugh.

Better idea:

gdb ./mess_no_one_dares_walk_through...(gdb) break main...(gdb) run...(gdb) catch throw...(gdb) run...(gdb) bt...

It's possible that finding out the exact thrown exception will help you figure out what's going on... (edit: and that will at least get you to the part where the exception is being thrown) - just my 2 cents. Is it possible you have something like this in an inner branch of logic:

try{}catch(...){   terminate();}

?

Share on other sites
Are you using throw() specifiers somewhere? When an exception is thrown in a function with a throw specifier iirc. unexpected() is called, which by default calls terminate().

Share on other sites
We turned off exception specifications, just to make sure that wasn't it.

I'll try that gdb run through tomorrow and see what comes up. We've used a bt from the terminate() and we think that leads us back to the exception. Never know though (and it never hurts to try).

Thanks for the suggestions. If you've got any more, I'd love to hear them. This has been a heck of a confusing ordeal.

Share on other sites
Is it possible for any of your destructors to throw?

Share on other sites
There shouldn't be any. I can't guarantee it, but I'm pretty sure there aren't any. If there are... someone's in some trouble. ;)

Share on other sites
Here's the output of the gdb session:

Quote:
 (gdb) break mainBreakpoint 1 at 0x805f819(gdb) run --consoleStarting program: /soft/DEV/shane/bin/opodsrvr --console[Thread debugging using libthread_db enabled][New Thread 16384 (LWP 17972)][Switching to Thread 16384 (LWP 17972)] Breakpoint 1, 0x0805f819 in main ()(gdb) catch throw Catchpoint 2 (throw) (gdb) run The program being debugged has been started already.Start it from the beginning? (y or n) nProgram not restarted. (gdb) cont Continuing. Catchpoint 2 (exception thrown) __cxa_throw (obj=0x821052c, tinfo=0x82111e0, dest=0x82111e0 ) at /usr/local/src/gcc/gcc-3.2.2/libstdc++-v3/libsupc++/eh_throw.cc:5959 /usr/local/src/gcc/gcc-3.2.2/libstdc++-v3/libsupc++/eh_throw.cc: No such file or directory. in /usr/local/src/gcc/gcc-3.2.2/libstdc++-v3/libsupc++/eh_throw.ccCurrent language: auto; currently c++(gdb) bt #0 __cxa_throw (obj=0x821052c, tinfo=0x82111e0, dest=0x82111e0 ) at /usr/local/src/gcc/gcc-3.2.2/libstdc++-v3/libsupc++/eh_throw.cc:59#1 0x08191e34 in ApplicationSection::instanceSubNode(std::string) const ()#2 0x08182e4e in AppServerConfiguration::AppServerConfiguration(EnvironmentConfiguration const&, std::string) ()#3 0x08053654 in AppConfiguration::AppConfiguration(std::string) ()#4 0x08053c92 in AppConfiguration::init(std::string const&, std::string const&) ()#5 0x0805f8b5 in main () (gdb) cont Continuing. Program received signal SIGABRT, Aborted.0xb6cbf251 in kill () from /lib/libc.so.6(gdb) bt #0 0xb6cbf251 in kill () from /lib/libc.so.6#1 0xb6c4ccff in pthread_kill () from /lib/libpthread.so.0#2 0xb6c4d07a in raise () from /lib/libpthread.so.0#3 0xb6cbeff4 in raise () from /lib/libc.so.6#4 0xb6cc0393 in abort () from /lib/libc.so.6#5 0xb7a260c9 in __cxxabiv1::__terminate(void (*)()) (handler=0xb6cc02b8 ) at /usr/local/src/gcc/gcc-3.2.2/libstdc++-v3/libsupc++/eh_terminate.cc:47#6 0xb7a26103 in std::terminate() () at /usr/local/src/gcc/gcc-3.2.2/libstdc++-v3/libsupc++/eh_terminate.cc:57#7 0xb7a26230 in __cxa_throw (obj=0x82704a0, tinfo=0x0, dest=0) at /usr/local/src/gcc/gcc-3.2.2/libstdc++-v3/libsupc++/eh_throw.cc:77#8 0x08191e34 in ApplicationSection::instanceSubNode(std::string) const ()#9 0x08182e4e in AppServerConfiguration::AppServerConfiguration(EnvironmentConfiguration const&, std::string) ()#10 0x08053654 in AppConfiguration::AppConfiguration(std::string) ()#11 0x08053c92 in AppConfiguration::init(std::string const&, std::string const&) ()#12 0x0805f8b5 in main ()(gdb)

As you can see, it's not very helpful. The very first exception being thrown is the one that causes terminate() to be called. I'm not sure what the eh_throw.cc error is all about, but it's shown up on every version of g++ I've tried (and I've tried a lot of them). I did a quick grep on terminate just to be sure, but nothing came up. Is there anything else I could try?

Share on other sites
eh_throw.cc is a source file in the C++ Library. If you were to type 'up 7' to go back up to that frame, followed by 'list', it should show you the code where it decided to call terminate, which would probably give you an idea of why it was called in the first place.

Share on other sites
list just produces output like this:

59 in /usr/local/src/gcc/gcc-3.2.2/libstdc++-v3/libsupc++/eh_throw.cc

or

42 in /usr/local/src/gcc/gcc-3.2.2/libstdc++-v3/libsupc++/eh_terminate.cc

Nothing more. Is that something meaningful?

Share on other sites
It probably means the source file isn't there for it to get the code from. Poor you.

Share on other sites
To me it seems like the problem is in iApplicationSection::instanceSubNode(std::string) , not in the files eh_throw.cc eh_terminate.cc at all.

Share on other sites
All that is, is the try/catch block. I can replace all that's in the try {} section with throw std::exception() and have the catch block try to catch it and it'll still crash. That's what leads me to believe it's something about exceptions not being setup properly.

Share on other sites
Quote:
 Original post by ChozoAll that is, is the try/catch block. I can replace all that's in the try {} section with throw std::exception() and have the catch block try to catch it and it'll still crash. That's what leads me to believe it's something about exceptions not being setup properly.
Are you sure that an exception wasn't thrown before that?

Did you put that try catch block as the first thing in your main() function and still have this happen?

Share on other sites
Yup. The whole of main is a try { ... } catch(some exception) { } catch(some other exception) { } catch(yet another exception) { } catch(...) { }. So whatever doesn't get caught early on should get caught there, right?

Share on other sites
Well on windows (...) will catch everything, including system exception such as access violations and such. On linux, I think it will only catch C++ exceptions (which is all that the standard requires). Still, it's very strange because throwing a std::exception IS a C++ exception...

Share on other sites
Build with -g if you want gdb to report file and line numbers.

Share on other sites
Those files (eh_throw.cc and eh_terminate.cc and so on) don't exist on my machine. Anywhere. I have no idea wth they're doing in there.

Share on other sites
Are you catching by reference or by value?

It's recommended to catch by reference.

Share on other sites
Quote:
 Original post by ChozoThose files (eh_throw.cc and eh_terminate.cc and so on) don't exist on my machine. Anywhere. I have no idea wth they're doing in there.

They are not something you really need to care about. They are source files that are part of the C++ standard library. I would guess there is enough debugging info left in the library to tell you the name of the source files. When it goes here, it has already thrown, though. The problem, which may be a memory access violation, is in ApplicationSection::instanceSubNode(std::string) const

Share on other sites
They're all being caught by reference. I've heard that someone else got it to compile on Debian and Fedora. I find it really hard to believe that the distribution has anything to do with this, but who knows.

Share on other sites
Well seeing as this appears to be still unresolved let's try and narrow down the possible area of problems:

1) does a basic exception example work?

#include <iostream>using namespace std;int main ( void ){    try { throw 3; }    catch (...) { cout << "OK" << endl; }}

2) does the same example work catch std::exception and throwing std::logic_error (in <stdexcept>)?

no) FUBARed library (and/or compiler/linker) setup.
yes) it's probably something with your code.

Possibilities so far at this point:

1) destructor throws during stack unwinding from the first throw. (gdb) break catch then step through with detailed line debugging info avail would be a good idea - you might get away with a simple (gdb) continue after hitting the first exception - in theory it'll then break again on the second throw (I'm not sure exactly how stack unwinding plays about with the stack...).

2) someone was naughty and messed with the exception handlers somewhere without telling anyone.

3) If indeed someone got it compiling and working on a linux box, guesses are either FUBARed environment or you've got a wild pointer/dangling reference somewhere screwing everything up.

Share on other sites
Okay, I made a simple test:

#include <stdexcept>#include <iostream>int main(int argc, char* argv[]) {    std::string errorstr("crap");    try {           throw std::runtime_error(errorstr);    } catch(...) {        std::cout << "Caught something?" << std::endl;    }    return 0;}

And compiled with g++ -Wall. It worked just dandily. I have this code at the *start* of our module:

int main(int argc, char *argv[]){    std::set_terminate(terminate_func);    std::set_unexpected(unexpected_func);std::cout << "Before exception!" << std::endl;try {    throw 3;} catch(...) {    std::cerr << "Damn!" << std::endl;    exit(1);}std::cout << "After exception!" << std::endl;

And it calls the terminate handler after printing 'Before exception!'. 'Damn!' and 'After exception!' are never printed. Does that mean some global object might be mangling the stack? If so... how would I find it?

Share on other sites
Extremely odd. Does this code work (standalone)? What are your sources for terminate/unexpected_func?

#include <exception>#include <iostream>using namespace std;void terminate_func( void ){        cout << "terminate_func()" << endl;        abort();}void unexpected_func( void ){        cout << "unexpected_func()" << endl;        terminate();}int main ( int argc , char * argv [] ){        std::set_terminate( terminate_func );        std::set_unexpected( unexpected_func );        std::cout << "Before exception!" << std::endl;        try        {                throw 3;        }        catch ( ... )        {                std::cerr << "Damn!" << std::endl;                exit(1);        }        std::cout << "After exception!" << std::endl;}

Create an account

Register a new account

• Partner Spotlight

• Forum Statistics

• Total Topics
627664
• Total Posts
2978522

• 10
• 10
• 12
• 22
• 13


text:
# FAQ’s about Carbohydrates and other Biomolecules in JEE

Central Board of Secondary Education (CBSE) conducts the JEE (joint entrance examination) every year. It is a platform to provide admissions to the aspiring candidates across the country, into the prestigious technical colleges of our country. Candidates must work tirelessly with intensive hard work and focus for obtaining success in this examination. Chemistry is one of the easiest subjects to score good marks in the famed JEE. The questions asked in chemistry are much simpler and take lesser time as compared to the questions asked in physics or mathematics.  A few important chapters and some concepts are highly significant as there is a pattern in which these questions repeat every year. Going through these questions will give you a fair idea about your preparation status and help you to utilize the remaining time before the examination.

Q. What are the important topics in carbohydrates and other biomolecules?

Ans. Carbohydrates and other biomolecules fall under the important topics, which will help you in scoring good in JEE. Following are the concepts that should be studied carefully:

• Classification and structure of carbohydrates
• Monosaccharide
• Disaccharides
• Polysaccharides
• Amino acids
• Peptides and proteins
• Nucleic Acids

Q. How to approach a question in carbohydrates and other bio molecules?

Question: In E. coli DNA, the AT/GC ratio is 0.93. If the number of moles of adenine in the DNA sample is 558,000, calculate the number of moles of guanine present.

Solution: Number of moles of adenine must be equal to that of thymine, so

(A + T)= 558,000 + 558,000 = 1116000

Since, $\frac{A+T}{C+G}$ = 0.93

Therefore, no of moles of C + G will be,

C + G = $\frac{1116000}{0.93}$ = 1200000

Since number of moles of C = number of moles of G

$\Rightarrow$ Number of moles of guanine = $\frac{1200000}{2}$ = 600000

Books for reference

Refer NCERT textbook for class 12th. This book contains all the details in a very precise manner. A quick view of this can help you to understand the fundamental concepts and their applications. The important points are neatly mentioned in the book making it the most student-friendly book. Some other important reference books include books by O. P. Tandon and P. Bahadur. For more details download Byju’s the learning app.

#### Practise This Question

rRNA is synthesized in ________.