text:
Search by keywords or author
• Vol. 1, Issue 1, 016003 (2022)
Shiyao Fu1、2、3、*, Zijun Shang1、2、3, Lan Hai1、2、3, Lei Huang1、2、3, Yanlai Lv1、2、3, and Chunqing Gao1、2、3、*
Author Affiliations
• 1Beijing Institute of Technology, School of Optics and Photonics, Beijing, China
• 2Ministry of Industry and Information Technology of the People’s Republic of China, Key Laboratory of Information Photonics Technology, Beijing, China
• 3Ministry of Education of the People’s Republic of China, Key Laboratory of Photoelectronic Imaging Technology and System, Beijing, China
• show less
Shiyao Fu, Zijun Shang, Lan Hai, Lei Huang, Yanlai Lv, Chunqing Gao. Orbital angular momentum comb generation from azimuthal binary phases[J]. Advanced Photonics Nexus, 2022, 1(1): 016003 Copy Citation Text show less

Abstract

Since Allen et al. demonstrated 30 years ago that beams with helical wavefronts carry orbital angular momentum (OAM), the OAM of beams has attracted extensive attention and stimulated lots of applications in both classical and quantum physics. Akin to an optical frequency comb, a beam can carry multiple various OAM components simultaneously. A series of discrete, equally spaced, and equally weighted OAM modes comprise an OAM comb. Inspired by the spatially extended laser lattice, we demonstrate both theoretically and experimentally an approach to producing OAM combs through azimuthal binary phases. Our study shows that transition points in the azimuth determine the OAM distributions of diffracted beams. Multiple azimuthal transition points lead to a wide OAM spectrum. Moreover, an OAM comb with any mode spacing is achievable through reasonably setting the position and number of azimuthal transition points. The experimental results fit well with theory. This work presents a simple approach that opens new prospects for OAM spectrum manipulation and paves the way for many applications including OAM-based high-security encryption and optical data transmission, and other advanced applications.

Video Introduction to the Article

1 Introduction

Similar to macroscopic objects, particles such as photons,1 electrons,2 and neutrons3 can also carry angular momentum. The angular momentum of a photon is of two types, with the spin angular momentum (SAM) corresponding to circular polarization4 and the orbital angular momentum (OAM) determining the helical wavefronts of a beam.5 Actually, OAM is an inherent feature of a beam whose complex amplitude comprises a helical term $exp(ilφ)$, where $l$ is the OAM eigenvalue and known as the topological charge associated with an OAM value $lℏ$ ($ℏ$ is the reduced Planck’s constant) per photon, and $φ$ denotes the azimuthal angle.6,7 One or more phase singularities determined by multiple OAM components are present for an OAM beam, thus leading to a doughnut-shaped transverse intensity.8 OAM offers an additional degree of freedom and leads to new possibilities for photonics research. Over the past 30 years, beams carrying OAM have found a wide variety of applications, including large-capacity communications,913 rotation detection,1416 optical tweezers and manipulation,17,18 imaging,19 gravitational wave detection,20,21 and quantum information processing.22,23

Previous research has provided a variety of schemes to generate OAM beams, such as direct output from a laser2428 or endowing a Gaussian beam with spiral phases outside the laser resonator.2934 Nevertheless, most of the aforementioned methods concentrate only on the generation of single or simple multiplexed OAM modes. Beams carrying a wide series of discrete, equally spaced, and manipulated OAM components with identical intensities, namely the OAM comb, are conducive to current OAM-based scenarios. For instance, multiplexed OAM multicasting enables one-to-multichannel data transmission, further enlarging the dimensions of OAM-based optical communications.35 The OAM comb can also act as a flexible key for holographic encryption and decryption.36,37 Currently, schemes such as mode iteration,38 pattern-search algorithm,39 adaptive modification,40 and pinhole plates41 have been reported to tailor the OAM spectrum or produce an OAM comb. However, these schemes may face problems such as long response or calculation time, complex systems, and lower diffraction efficiency, which motivated us to develop a simple, flexible, and functional approach to selectively manipulate OAM combs.

In this study, we overcome the aforementioned limitations by demonstrating a specially designed azimuthal $0-π$ binary phase-only grating for the selective manipulation of OAM combs. Several transition points were embedded in a spiral phase along the azimuth to tailor the OAM spectrum of the diffractive beams. The number and position of the azimuthal transition points were optimized to produce arbitrary OAM combs, where the optimized results were fixed and could be employed for various scenarios at any time. A proof-of-principle experiment was performed to demonstrate the performance of the proposed azimuthal binary-phase gratings. These favorable results were in good agreement with our simulations. This study offers a real-time, flexible, simple, and accurate method for generating beams with complicated OAM spectra, which paves the way for classical/quantum optical communications, holographic encryption and decryption, and other advanced applications in the future.

2 Results and Discussion

2.1 Azimuthal Phase Modulation: From Continuation to Binarization

Previous studies have illustrated that a continuous azimuthal phase, namely a spiral phase plate (SPP), can bring a pure single OAM mode for the incident beams.29 In other words, such spiral phase $Pspp=lφ$ mod $2π$ with $|l|$ nodal lines can transform a Gaussian beam into an OAM beam with topological charge $l$. As displayed in Fig. 1(a), if we binarize the continuous azimuthal phase as 0 and $π$ with the binarization threshold $Pth=π$: $PB={0,if Psppwhere $PB$ denotes the phase distribution of the azimuthal binary phase, one can obtain a petal-like pattern with $|2l|$ petals. The OAM spectrum of such beam can be diagnosed through helical harmonic decomposition,42 where two main OAM components with a topological charge $±l$ are present. Some high-order helical harmonic terms $±Nl$ ($N$ is an integer) also emerged. Such phenomena imply that the binarized azimuthal phase can produce multiple symmetric OAM components with respect to the fundamental mode $l=0$. If the binarization threshold replaced by other values belongs to section [$0,2π$), the OAM spectra of diffractive beams turn out to be diversified. As displayed in Fig. 1(b), we choose seven various binarization thresholds $Pth$ as $π/4$, $π/2$, $3π/4$, $π$, $5π/4$, $3π/2$, and $7π/4$ to binarize the continuous azimuthal phase with one nodal line ($l=1$), and analyze the OAM spectra of the diffraction beams. Obviously, the OAM spectra can be tuned under various binarization thresholds $Pth$. In addition, there is an azimuthal transition point $φκ$ in each binary phase, the position of which is surely determined by $Pth$, as shown in the second line of Fig. 1(b). That is, one can understand that the positions of azimuthal transition points induce redistributions of the azimuthal phase, giving rise to various OAM spectra. Meanwhile, the complementary two binary phase distributions ($PB1+PB2=2π$) lead to the same OAM spectra, resulting from the relative phase difference of $0-π$ binarized phase modulation.

Figure 1.Binarizing continuous azimuthal phases into $0-π$ azimuthal binary phases. (a) The binarization of continuous azimuthal phases with one and two nodal lines (the first- and second-order SPPs) under the threshold $Pth=π$. The binarized phase can produce symmetric OAM components with respect to $l=0$ mode, compared with the corresponding continuous azimuthal phases. (b) The $0-π$ phase binarized under various binarization threshold $Pth$ as $π/4$, $π/2$, $3π/4$, $π$, $5π/4$, $3π/2$, and $7π/4$, respectively. First to fourth lines in panel (b): the phase distribution, the phase versus the azimuthal angle $φ$, the simulated far-field diffraction pattern, and the corresponding calculated OAM spectrum.

2.2 Azimuthal Binary Phase with Multiple Transition Points

Next, we discuss what happens if multiple azimuthal transition points are brought in. The phase distribution of a $0-π$ binary phase-only grating with ($K+1$) various azimuthal transition points within one grating period reads $PB(φ)=π∑κ=0K(−1)κ+1rect(φφκ−0.5),φ∈[0,2π),$with $φκ$ as the $κ$’th transition point and $κ=0,1,2,…,K$. The diffraction field of such a grating for an incident Gaussian beam can be calculated approximatively through Fourier transformation (Supplementary Note 1), which contains multiple diverse OAM components. As an example, Fig. 2 displays the evolution of the obtained OAM spectra with respect to azimuthal transition points. The first, second, third, and fourth lines show the transition points, the corresponding azimuthal binary phase distributions, far-field diffractions, and OAM spectra, respectively. Four azimuthal transition points are chosen here as $φ0=0$, $φ1=1.4564$, $φ3 =2.6703$, and $φ4=3.3015$. If there are two transition points only, the phase distribution is simple and the obtained OAM spectrum emerges as a hill-shaped envelope. When all the three transition points are introduced, the binary phase gets a little more complicated but the final OAM spectrum turns out to be structured as seven different OAM components whose topological charges range from $−3$ to $+3$ are present and show nearly equal intensities, i.e., a kind of OAM comb. Such phenomena imply that an azimuthal $0-π$ binary phase is an effective pathway to tailor OAM combs, providing that the number and value of azimuthal transition points are well selected.

Figure 2.The evolution of the obtained OAM spectra with respect to azimuthal transition points. Four transition points as $φ0=0$, $φ1=1.4564$, $φ2=2.6703$, and $φ3=3.3015$ are introduced orderly in the azimuthal section [$0,2π$) as an example to demonstrate OAM spectrum variation. From top to bottom are the azimuthal transition points, the corresponding azimuthal binary phases, far-field diffraction patterns, and OAM spectra. Obviously, the number and value of transition points determine the final obtained OAM spectra.

2.3 OAM Comb Manipulation

To produce the desired OAM combs, a feasible way is to find a proper set of transition points. From the scalar diffraction theory, the far-field diffraction $E$ of an incident plane wave can be calculated approximatively by the Fourier transform of the transmittance function of azimuthal binary phases. Thus, $E$ from Eq. (2) reads $E=F[exp(iPB)]$, where $F$ denotes Fourier transformation. On the basis of helical harmonic $exp(ilφ)$, the diffraction field $E$ can be decomposed into the summation of infinite helical term with various complex weights $al$:42$E(r,φ)=12π∑l=−∞+∞alexp(ilφ).$

The complex weights in Eq. (3) read $al=12π∫02πE(r,φ)exp(−ilφ)dφ.$

Actually, $|al|2$ corresponds to the intensity of OAM channel $l$. By now, a mind map of OAM comb manipulation emerges clearly, as the azimuthal transition points lead to azimuthal nodal lines determine the diffraction fields, and such fields further determine the intensity of each OAM channel $|al|2$. In other words, the final OAM spectrum is a function of azimuthal transition points $φκ$ as $|al|2=f(φκ)$ indeed (Supplementary Note 2). To find a proper set {$φκ$} for the desired OAM comb, several evaluation parameters are necessary. Here two parameters are introduced, one of which is the efficiency defined as $η=(Σl∈L|al|2)/Σl∈Z|al|2$, where $L$ and $Z$ denote the set of topological charges of desired OAM comb and the integer set separately. The other is the uniformity as $U=2 min|al|2/(max|al|2+min|al|2$), where $l∈L$, min{} and max{} denote taking the minimum and maximum, respectively. Note that $η$ must be $<1$ because a single phase-only grating cannot produce coaxial multiplexed OAM modes with desired OAM distributions, and there must be irrelevant and undesired OAM modes.38 {$φκ$} calculation is available through iteration embedded numerical simulation. In each iteration, one must evaluate the value of $η$ and $U$ to decide how to adjust the transition points set {$φκ$} until an ideal scenario where the finally calculated transition points contribute to highest efficiency $η$ and uniformity $U$. Usually such process is complex and time-consuming, which incommodes the practical application of OAM comb. Zhou and Liu43 have already demonstrated numerical solutions for $0-π$ binary Dammann gratings, which can expand the incident beam along the $x$ direction to achieve a one-dimensional (1D) equal-intensity laser array with both high efficiency and high uniformity. In Ref. 43, multiple lateral ($x$) transition points are introduced within one grating period $T$, resulting in multiple presented diffraction orders ($x$-expanded modes) featured as $Σexp(i2πmx/T)$, where $m$ corresponds to the $m$’th diffraction order. Here, we move from “$x$-space” to “$φ-space$,” where the azimuthal ($φ$) transition points in one azimuthal period ($Π=2π$) lead to OAM superposed modes ($φ$-expanded modes) featured as $Σexp(ilφ)=Σexp(i2πlφ/Π)$. The resulting fields in the above two “spaces” have identical forms. Their only difference is that one expands the incident beam along the $x$ coordinate while the other along the $φ$ coordinate. Such phenomena imply that the numerical solutions given in Ref. 43 are also effective to be employed in the azimuth to produce various OAM superposed modes with equal intensities.

We map the numerical solutions presented in Ref. 43 from “$x$-space” to “$φ$-space” (Supplementary Note 3) to generate azimuthal $0-π$ binary phases, calculate the far-field diffractions through the scalar diffraction theory for incident Gaussian beams, and then analyze the OAM spectra (Supplementary Note 4). As displayed in Fig. 3(a), an azimuthal binary phase can produce nine equal-intensity OAM modes with topological charges ranging from $−4$ to $+4$. It has six azimuthal transition points as 0, 0.4190, 0.8087, 1.7963, 2.8693, and 3.7127. The efficiency and the uniformity of the obtained OAM comb are calculated as 78.32% and 99.61%, which are high enough for OAM comb manipulation. In addition, we also attempt to generate OAM combs with other OAM mode intervals $Δl$. Such manipulation is based on the scaling property of the Fourier transform, where if $F{f(x)}=F(u)$, then $F{f(x/a)}=|a|F(au)$ with $a$ the scale factor. So, here scaling the azimuthal phase $φ$ contributes to $F{TB(φ/Δl)}∝Σlexp(iΔllφ′)$, where $φ′$ is the azimuthal angle in the far field. As an example, we scale the azimuthal angle in Fig. 3(a) with scale factors $Δl=2$ and $Δl=3$, and the final obtained OAM combs are given in Figs. 3(b) and 3(c). Note that the OAM comb is present through normalized intensity, where the calculated or experimentally measured intensity of each OAM channel is normalized with respect to the maximum intensity among all the present OAM channels. In both of the two scenarios, there are also nine OAM modes with equal intensities. However, their topological charge distributions are totally different; one is $−8$ to $+8$ with $Δl=2$, the other is $−12$ to $+12$ with $Δl=3$. Such phenomena illustrate that it is practicable to produce OAM combs with various OAM mode intervals through azimuth scaling and provide a more flexible scheme of OAM comb manipulation. Additionally, OAM range is limited to $−15$ to $+15$ here. When extending such a present range, in Figs. 3(b) and 3(c) one can see undesired side OAM modes distributions similar to Fig. 3(a), but the only difference is the space between adjacent OAM channels.

Figure 3.OAM comb manipulation with various OAM mode intervals. From left to right are azimuthal transition points, the corresponding binary phases, far-field diffractions, and OAM combs, respectively. All the OAM combs in (a), (b), and (c) consist of nine OAM components, but their OAM mode intervals are different as 1, 2, and 3, respectively. The interval difference results by scaling the azimuthal phase $φ$.

Proof-of-principle experiments are also carried out to show the practical operability (Supplementary Notes 5–7). In the experiment, we encode the azimuthal $0-π$ binary phase onto a liquid-crystal spatial light modulator (SLM) to accomplish the phase-only modulation. The OAM spectra are analyzed with the back-converted method as a series of spiral phases ($l1,l2,…,lN$), also known as anti-SPPs in some literature, are encoded simultaneously on the SLM and then the intensity of center bright spot is calculated to represent the relative intensity of the OAM channel $−l1$, $−l2,…,−lN$. We first generate an OAM comb consisting of 64 OAM states ranging from $−63$ to $+63$ with the OAM mode interval $Δl=2$. The experimentally captured intensity patterns and OAM spectrum and its corresponding simulation results are given in Fig. 4(a). The uniformity of the experimental result is evaluated as 92.04%, which is lower than that of the simulation at 98.16%. In addition, the similarity, which implies the consistency between the experimental and theoretical results suggested by the work44,45 is evaluated as 96.49%. We also generate an OAM comb consisting of 32 OAM states ranging from $−62$ to $+62$ with the OAM mode interval $Δl=4$, the results of which are shown in Fig. 4(b). In this case, the uniformities of the experimental and simulated results are 90.95% and 98.86%, respectively, and the similarity is analyzed as 93.36%. The numbers of azimuthal transition points {$φκ$} for the above two cases are 70 and 68 separately (Supplementary Note 6). The measured OAM spectra in the experiment show little difference compared with simulation, where the intensities emerge in some irrelevant OAM channels and some power is likely to leak from desired to undesired OAM components. In fact, such “leakage” is meaningless and makes no physical sense because inevitable interchannel crosstalk is introduced during the data-processing of the back-conversion-based OAM spectrum measurement.

Figure 4.Experimentally generated OAM combs. (a) Experimental results of an OAM comb consisting of 64 OAM states ranging from $−63$ to $+63$ with the OAM mode interval $Δl=2$. (b) Experimental results of an OAM comb consisting of 64 OAM states ranging from $−62$ to $+62$ with the OAM mode interval $Δl=4$. In both of the cases the OAM spectra are measured through anti-SPP based OAM back-conversion.

3 Conclusions

We showed that binarizing a spiral phase into $0-π$ binarization results in multiple OAM components that are symmetric with respect to the fundamental mode ($l=0$) of equal intensity. In this case, there are two azimuthal transition points constituting the two nodal lines that divide phases 0 and $π$. When more transition points are introduced, the resulting OAM spectrum becomes more complex. Nevertheless, the OAM distribution can be tailored by adjusting the number and value of azimuthal transition points to accomplish arbitrary OAM comb manipulations. Finding a proper set of azimuthal transition points is crucial for OAM comb manipulation; however, it is complicated because of repetitive iterations. Therefore, based on previous reports on the numerical solutions of lateral transition points to construct a 1D beam lattice that expands the incident beam along the $x$ axis, we build a mapping between the $x$ axis in Cartesian coordinates and the $φ$ axis in polar coordinates, thus transforming the optimal solution of transition points along the $x$ axis into that of the azimuth along the $φ$ axis to accomplish a fast binary phase calculation. In the simulation, we successfully produce various OAM combs following the above hypothesis. We also show how to adjust the mode interval between adjacent OAM modes inside the OAM comb by scaling the azimuthal coordinates. In the proof-of-principle experiment, OAM combs consisting of up to 64 OAM components with the largest absolute value of OAM state 63 are generated, whose uniformity reaches 92.04% and fits well with the theory. We also attempt to adjust the OAM mode interval in practice and produce an OAM comb comprising 32 OAM components whose OAM states range from −62 to +62 with a mode interval of 4. The uniformity is evaluated to be 90.95%. The favorable experimental results illustrate that our proposed method exhibits good performance for tailoring OAM combs in practice.

In addition, the OAM states can be shifted by illuminating the $0-π$ binary phase-only grating with a higher-order optical vortex. Alternatively, this may be done by integrating the $l$’th order spiral phase with the proposed binary azimuthal phase to shift the OAM components by $l$, as in Ref. 46. In this manner, OAM combs whose components are asymmetric with respect to the fundamental mode ($l=0$) can also be achieved.

The ability to generate a beam with a specifically tailored OAM spectrum is crucial for OAM applications; e.g, the unique key of holographic encryption and decryption.36,37 In addition, the proposed approach provides a convenient method for the practical generation of high-dimensional OAM combs, namely, an available high-dimensional Hilbert space; thus, it can find potential in high-dimensional photon entanglement and will inspire applications in quantum key distribution and quantum teleportation.47 Iteration methods are typically employed to optimize phase-only gratings to produce a multiplexed OAM beam. However, these complicated processes are time-consuming and may be inconvenient for practical applications. Herein, we demonstrate a simple approach in which azimuthal binary phases are introduced to manipulate arbitrary OAM combs with equal mode intensities. Furthermore, the azimuthal transition points can be easily calculated by mapping the numerical solutions of the binary lateral phases. In summary, our proposal opens new avenues for OAM comb manipulation and lays the foundation for applications in many OAM-based systems.

Shiyao Fu is currently an associate professor at Beijing Institute of Technology. He received his PhD in electronic science and technology from Beijing Institute of Technology in 2019. His current research interests cover complex structured fields manipulation, novel solid-state lasers, and their applications in critical engineering. He has published one book and more than 40 peer-reviewed papers. He has 18 authorized patents. He was selected for the national postdoctoral program for Innovative Talents. He won the Wang Da-Heng Optics Prize, and his doctoral dissertation was recognized by the Chinese Institute of Electronics. He is a senior member of the Chinese Optical Society.

Chunqing Gao is a professor in the School of Optics and Photonics, Beijing Institute of Technology, China since 2001. He received his BS degree and MS degree in optics from Beijing Institute of Technology, and received his PhD in physics from Technical University Berlin, Germany. The current research in his group mainly focuses on novel laser systems, laser beam manipulation, and related applications. He has published three books and more than 260 scientific papers in journals and conferences. He has 30 authorized patents in the fields of optics and lasers.

Biographies of the other authors are not available.

Shiyao Fu, Zijun Shang, Lan Hai, Lei Huang, Yanlai Lv, Chunqing Gao. Orbital angular momentum comb generation from azimuthal binary phases[J]. Advanced Photonics Nexus, 2022, 1(1): 016003


text:
BGWM.mean.estim {Branching} R Documentation

## Estimation of the mean matrix of a multi-type Bienayme - Galton - Watson process

### Description

Calculates a estimation of the mean matrix of a multi-type Bienayme - Galton - Watson process from experimental observed data that can be modeled by this kind of process.

### Usage

BGWM.mean.estim(sample, method=c("EE","MLE"), d, n, z0)

### Arguments

 sample  nonnegative integer matrix with d columns and dn rows, trajectory of the process with the number of individuals for every combination parent type - descendent type (observed data). method  methods of estimation (EE Empirical estimacion, MLE Maximum likelihood estimation). d  positive integer, number of types. n  positive integer, nth generation. z0  nonnegative integer vector of size d, initial population by type.

### Details

This function estimates the mean matrix of a BGWM process using two possible estimators, empirical estimator and maximum likelihood estimator, they both require the so-called full sample associated with the process, ie, it is required to have the trajectory of the process with the number of individuals for every combination parent type - descendent type. For more details see Torres-Jimenez (2010) or Maaouia & Touati (2005).

### Value

A list object with:

 method  method of estimation selected. m  A matrix object, estimation of the d \times d mean matrix of the process.

### Author(s)

Camilo Jose Torres-Jimenez cjtorresj@unal.edu.co

### References

Torres-Jimenez, C. J. (2010), Relative frequencies and parameter estimation in multi-type Bienaym? - Galton - Watson processes, Master's Thesis, Master of Science in Statistics. Universidad Nacional de Colombia. Bogota, Colombia.

Maaouia, F. & Touati, A. (2005), 'Identification of Multitype Branching Processes', The Annals of Statistics 33(6), 2655-2694.

BGWM.mean, BGWM.covar, rBGWM, BGWM.covar.estim

### Examples

## Not run:
## Estimation of mean matrix from simulated data

# Variables and parameters
d <- 3
n <- 30
N <- c(10,10,10)
LeslieMatrix <- matrix( c(0.08, 1.06, 0.07,
0.99, 0, 0,
0, 0.98, 0), 3, 3 )

# offspring distributions from the Leslie matrix
# (with independent distributions)
Dists.pois <- data.frame( name=rep( "pois", d ),
param1=LeslieMatrix[,1],
param2=NA,
stringsAsFactors=FALSE )
Dists.binom <- data.frame( name=rep( "binom", 2*d ),
param1=rep( 1, 2*d ),
param2=c(t(LeslieMatrix[,-1])),
stringsAsFactors=FALSE )
Dists.i <- rbind(Dists.pois,Dists.binom)
Dists.i <- Dists.i[c(1,4,5,2,6,7,3,8,9),]
Dists.i

# mean matrix of the process from its offspring distributions
m <- BGWM.mean(Dists.i,"independents",d)

# generated trajectories of the process from its offspring distributions
simulated.data <- rBGWM(Dists.i, "independents", d, n, N,
TRUE, FALSE, FALSE)$o.c.s # mean matrix empiric estimate from generated trajectories of the process m.EE <- BGWM.mean.estim( simulated.data, "EE", d, n, N )$m

# mean matrix maximum likelihood estimate from generated trajectories
# of the process
m.MLE <- BGWM.mean.estim( simulated.data, "MLE", d, n, N )\$m

# Comparison of exact and estimated mean matrices
m
m - m.EE
m - m.MLE

## End(Not run)

[Package Branching version 0.9.4 Index]

format: plain


text:
# How do you express 56,700,000 in scientific notation?

Feb 20, 2017

$56 , 700 , 000 = 5.67 \times {10}^{7}$

#### Explanation:

In scientific notation, we write a number so that it has single digit to the left of decimal sign and is multiplied by an integer power of $10$.

Note that moving decimal $p$ digits to right is equivalent to multiplying by ${10}^{p}$ and moving decimal $q$ digits to left is equivalent to dividing by ${10}^{q}$.

Hence, we should either divide the number by ${10}^{p}$ i.e. multiply by ${10}^{- p}$ (if moving decimal to right) or multiply the number by ${10}^{q}$ (if moving decimal to left).

In other words, it is written as $a \times {10}^{n}$, where $1 \le a < 10$ and $n$ is an integer.

To write $56 , 700 , 000$ in scientific notation, we will have to move the decimal point seven points to the left, which literally means dividing by ${10}^{7}$.

Hence in scientific notation $56 , 700 , 000 = 5.67 \times {10}^{7}$ (note that as we have moved decimal seven points to the left we are multiplying by ${10}^{7}$.

May 11, 2017

A = $5.67 \cdot {10}^{7}$

#### Explanation:

Generally scientific notation is as follows:

Have a large integer $a b c 00000$
When we have scientific notation, we normally take the first digit of the integer, $a$ and then place a decimal point then putting the digits $b$ and $c$.

Furthermore, we then find out the total amount of digits need to create the number by using the following formula:

=

$\text{0m} + 2$

Where:

$\text{m}$ = "amount of"

All the best!

Aug 8, 2018

$5.67 \cdot {10}^{7}$

#### Explanation:

The key realization is that when we write numbers in scientific notation, we want one digit before the decimal point.

In our case, we must loop it $7$ times to the left. The number of times we loop it is our exponent, and looping left makes it positive. Thus, we have

$5.67 \cdot {10}^{7}$

Hope this helps!


text:
# Algorthm: Given a set of points, width around line, find line to capture maximum points

I want to know if there is an algorithm for this problem.

I have a list of points given as (x,y) values and a given distance. I want to draw a line through the set of data points so that the size of the set of points that is within the given distance from the line is maximized. That is, this line

Does an algorithm for this problem exist?

• What have you tried? Where did you get stuck? I don't know if this is at all helpful, but my gut instinct says to look into the dual plane. – jmite Jul 31 '14 at 18:28
• What's your notion of distance from a point $P$ to a line $L$? Is it orthogonal distance (i.e., the length of the line segment that is orthogonal to $L$ and that connects $P$ to $L$)? Or is it shortest distance (i.e., the distance from $P$ to the closest point on $L$)? Or vertical distance (the length of the vertical line segment that connects $P$ to $L$), as in linear regression? This leads to several different variations on the problem, just as different definitions of residual lead to linear regression / PCA / etc. – D.W. Jul 31 '14 at 18:45
• If your notion of distance is orthogonal distance, you might want to look at the technique used in training SVMs to find a support vector with maximal margin; I suspect that might be applicable to your problem. – D.W. Jul 31 '14 at 18:50

If your notion of distance is "vertical distance", similar to how residuals are computed during ordinary linear regression, this problem can be solved with linear programming.

Let $y=ax+b$ be the equation of the desired line; here $a,b$ are unknowns. Suppose we are given a list of points $(x_i,y_i)$. The vertical distance from $(x_i,v_i)$ to the line $y=ax+b$ is

$$|ax_i+b-y_i|.$$

Suppose we want this distance to be at most $d$, where $d$ is given. In other words, we want

$$|ax_i+b-y_i| \le d.$$

This is equivalent to

$$y_i-d \le ax_i+b \le y_i+d,$$

which gives two linear inequalities. (Recall that $x_i,y_i,d$ are known, and $a,b$ are unknown.) Given $k$ points, you get $2k$ linear inequalities. Now you can use linear programming to find $a,b$ that satisfy all of these linear inequalities.

You can even find the minimal value of $d$ such that such a line exists. Simply treat $d$ as an additional unknown, and minimize $d$ subject to the $2k$ linear inequalities above.

• Sorry for not mentioning, but I did in fact mean vertical distance, so this is exactly what I was looking for. – Onye Jul 31 '14 at 21:01


text:
# How to interpret shapley force plot for feature importance?

I am trying to practice and learn shapley value approach to explain my predictions on a binary classification problem. However am having difficulty in understanding the below plot.

1) Does it indicate the day_2_balance influences prediction to 1? or does blue values leads to prediction 1

2) What about the axis scale? (-4.357 to 5.643)

3) What does base value mean?

4) When I hover around the pink color , I see few more column names with some values. What do they indicate?

5) does the size of features represent their importance? Meaning PEEP_min=5 has a larger size than other features?

6) What does higher to lower and lower to higher indicate?

Can someone help me with this?

Taken from this question on Github and if you are using a tree-based classifier like XGBoost:

This is because the XGBoost Tree SHAP algorithm computes the SHAP values with respect to the margin not the transformed probability. So the values you are seeing are log odds values (what XGBoost would output if pred_margin=True were set).

This means, the values on the force diagram are not showing the probabilities and it totally makes sense if they are not between 0 and 1.

• Thanks. Upvoted Nov 10, 2020 at 12:37

I've never practiced this package myself, but I've read a few analyses based on SHAP, so here's what I can say:

1. A day_2_balance of 532 contributes to increase the predicted output. In this area, such a value of day_2_balance would let to higher predictions.
2. The axis scale represents the predicted output value scale. The actually predicted value is in bold font (-2.98). I don't know if the min and max values of the scale represent true min and max of the model predicted values. They more likely result from automatic scaling of the plot.
3. Base value should be the mean value of the estimator over the whole input space.
4. Those indicate the other features of which value influence the prediction to a higher value. Features are sorted by local importance, so those are features that have lower influence than those visible.
5. Yes, but only locally. On some other locations, you could have other contributions
6. higher/lower is a caption. It indicates if each feature value influences the prediction to a higher or lower output value.

From the example plot, you can draw the following interpretation: "sample n°4100 is predicted to be -2.92, which is much lower than the average predicted value (~0.643), mostly due to the specific values of features PEEP_min(5), Fi02_100_max (50), etc., and although day_2_balance is 532".

• Hi, upvoted for the help.but when my output class is 0 or 1 why does it predict it as -2.92? I mean am working on binary classification problem Dec 27, 2019 at 9:08
• Sorry, did not get that at first sight. Explanations above are for regression. I'm not quite sure how it works for multi-output cases (including classification), this should be some kind of score for the selected class, higher score meaning that the prediction tends towards this class. So in that case, the tested class would not be favoured by the model, due to the explanations listed in my original answer. As this is a binary problem, if you try the other class, you should get reversed results, with more red. Dec 27, 2019 at 21:55

After much consideration, I reached out the following points:

• Visualization of the first prediction's explanation shap.force_plot(explainer.expected_value, shap_values[0,:], X.iloc[0,:]) according to this doc shows:

1. features pushing the prediction higher are shown in red (e.g. $$\text{SHAP}_\text{day_2_balance} = 532$$), those pushing the prediction lower are in blue (e.g. $$\text{SHAP}_\text{PEEP_min} = 5$$ , $$\text{SHAP}_\text{Fi02_100_max} = 50$$, etc.) when $$\text{Model}_\text{predicted output} = -2.92$$ for your binary classification model.

2. Apart from @Sarah answer, the scale of SHAP values based on the discussion in this issue could transform via inverse_transform() as follows:

x_scaler.inverse_transform(shap_values)

3. Based on Github the base value:

The average model output over the training dataset has been passed

• $$\text{Model}_\text{Base value} = 0.6427$$
• In other words, it is the mean prediction which can be computed by:
Y_test.mean()

4. They haven't been shown due to their contributions to the quality rating are nearly zero.

5. Yes. This amount of contribution (magnitude) also has been highlighted under "Feature impact" in Figure 4 of the paper from Lundberg et al. [Nature BME] slightly better on the feature named "Total volume" with annotation as follows:

• in your case feature contributions to push the prediction to the left (lower end) for a certain observation:

$$\text{Feature impact}_\text{PEEP_min} > \text{Feature impact}_\text{Fi02_100_max} > \text{Feature impact}_\text{MV_dur_vae} > etc.$$

6. Features have a positive impact pushing the prediction higher ( are indicated in red), those have a negative impact pushing the prediction lower ( are shown in blue).

• Note: It is possible to compute the mean of variables using:
X_train.mean()

Although this issue is under discussion, from my personal perception it depends on their positive or negative impact local values. It would drive the prediction to the left or right for a certain observation. $$\text{SHAP}_\text{predicted} > \text{variable}_\text{mean}$$  or  $$\text{SHAP}_\text{predicted} < \text{variable}_\text{mean}$$


text:
# Variation of the universal property for the field of fractions

Consider the universal property for the fraction field of an integer domain:

Let $R$ be a integral domain, $F(R)$, its fraction field, $K$ some field and $f:R\rightarrow K$ a injective ring homomorphism, i.e. $R$ is embedded via $f$ in $K$. Then there exists a unique field homomorphism $g:F(R)\rightarrow K$ such that $g\circ \varepsilon =f$, where $\varepsilon$ is the map that embeds $R$ in $F(R)$.

To make things clear, this is what I understand to be a field resp. ring homomorphism:

$\bullet$ Let $R,S$ be fields. Then a field homomorphism $f$ is a map $f:\rightarrow S$ such that $f(x+y)=f(x)+f(y)$, $f(xy)=f(x)f(y)$ and $f(1)=1$.

$\bullet$ Let $R,S$ be (not necessarily unitary) rings. Then a ring homomorphism $f$ is a map $f:\rightarrow S$ such that $f(x+y)=f(x)+f(y)$, $f(xy)=f(x)f(y)$.

Notice that a ring homomorphism doesn't have to fulfill $f(1)=1$, even if the rings are both unitary. In particular, a ring homomorphism doesn't have to be injective. (These definitions are in conformity with the Mathworld definition)

My question is, what happens if we require in the above proposition that $g$ is only a ring homomorphism ? Does then $f$ have to be still injective, such that this proposition has to hold ? I wasn't able to construct a (nontrivial) counterexample where $f$ is not injective and $g$ is a ring homomorphism and the above holds.

-
Well, precisely the link you wrote defines homom. of rings as mapping unit to unit in case we have unitary rings, so why you say otherwise? –  DonAntonio Dec 7 '12 at 19:06
The universal property doesn't just talk about rings ( = always unital), but rather it takes place in the category of rings, where the morphisms are of course the homomorphisms of rings, not just the homomorphisms of the underlying rngs ( = no unit required). Why do people always keep applying this forgetful functor (probably because they think that forgetful functors are identities). –  Martin Brandenburg Dec 7 '12 at 20:18
@DonAntonio I'm afraid this is a terminology issue: It is true that a homomorphism between unitary rings has to map the unit to the unit. But it's also true, that we can forget about the unitary structure between the rings and view them only as rings. Then a homomorphism. doesn't have to map the unit to the unit (although units are present in the rings). [...] –  temo Dec 8 '12 at 13:14
[...] Consider for example the mapping $f:\mathbb{Z}\rightarrow \mathbb{Z}, \ x\mapsto 0$. The $\mathbb{Z}$'s are unitary rings, but we don't take the units into consideration, so $f$ is only a ring homomorphism (and not a unitary ring homomorphism). –  temo Dec 8 '12 at 13:17
Ohm, that's fine @temo. It's just that you said that in the link above they so and so, and they didn't. –  DonAntonio Dec 8 '12 at 13:19

Let $f: R \rightarrow K$ be a rng homomorphism with $R$ an integral domain and $K$ a field. Note that $f(1)f(1)=f(1)$ so $f(1)$ is a solution to the equation $x^2-x$ in particular $f(1)=1$ or $f(1)=0$.


text:
# XNA - Making 2D Hexagons Connect With Each Other

I'm working on a top-down 2D strategy game in XNA, and the tiles are hexagons. I can't have a grid because of the game mechanics, so everything has its own location, and every tile object is stored in a list. What I'm trying to do is have it so that if you place a tile close to the side of another tile, they will snap together and become one object. I can't seem to figure out how to get what side it should snap to.

The red represents the different sections I want to check for mouse clicks in (these would of course not be an actual texture in the game). The white represents the area where if you clicked, it wouldn't allow you to place a tile because it would be on top of another. The closest thing I can think of is to have a larger hexagon around the actual tile that's divided into triangles from the center to the edges, but I'm not sure how to do this.

And I'm gonna move it to Windows Phone with Monogame and I don't think the phone is fast enough to make some sort of thing that checks colors for each sector, so I don't think it can be texture based. I feel like there's some kind of relatively simple math to do this but I can't seem to figure it out.

Compare a line between the center of the nearest hex shape within a close radius of the mouse and the mouse itself and get the angle of the line between them relative to the horizontal axis of the grid. Then you could use a function like.

public Vector2 CalcHexPositionFromAngle(double angle, Vector2 point, double radius)
{
//assume the angle is in degrees and shed any numbers over 360 eg: 427 becomes 67
while(angle >= 360)
{
angle -= 360;
}

//This is a trick using the nature of truncation in most programming laguages
int tempAngle = angle/60;

//now we just multiply the number by 60 to bring it back up
//to an increment of 60 degrees and add half that again to find an angle between
//corners in the hex shape
int angleOfPlacement = (tempAngle*60) +30;

//assume the angle is in degrees (If angle is in radians forget this step)

//calculate the new position.

return new Vector2(p_X,P_Y);

}

This should give you the new position for your hex given that it is handed the the

angle in degrees between the originating hex you are snapping to and the mouse

the vector2 that is the center position of the originating hex you are snapping to

and radius or (half the distance between opposing faces of your hex shapes)

Note: this function takes degrees but can easily be adapted for radians.

The way I might approach it is to create a list of all possible hex center locations during the initialization stage before the game loop starts. Then during the game loop, if there is a mouse click within 1.5 tile radius (or whatever dist you think is approp) of a white tile, simply iterate the list and find the closest list Point to the click point. If the mouse click is closer to the result than it is to the white tile center, use that result as the center of the new tile you want to place. It can all be done using distaceSquared to avoid a bunch of square rooting too.

Better yet, simply store 6 relative offset vectors for each possible neighbor's center location. Then when a mouse click occurs near a white placed hex, iterate through the 6 offests and find the one closest to (mouseClick - whiteHexCenter). The new Hex should be placed such that its center is at (offsetResult + whiteHexCenter).


text:
Magyar Information Contest Journal Articles

# Problem I. 276. (October 2011)

I. 276. Huffman coding is an algorithm to compress data. You should get familiar with the algorithm to some extent and make a presentation about it. By using the string INFORMATIKA + MATEMATIKA'', demonstrate the steps of creating the code. Your presentation should be as clear as possible, show each step of the encoding process, and should contain an animation in the case, e.g., of creating and visiting the tree. Create action buttons to switch between slides and start the animation.

The file containing your presentation (i276.pptx, i276.odp,. . . ) should be submitted in a compressed file i276.zip.

(10 pont)

Deadline expired on November 10, 2011.

Sorry, the solution is available only in Hungarian. Google translation

Mintamegoldásként Antal János Benjámin Nyíregyházi, 12. osztály diák (i276ajb.ppt) és Fényes Balázs Budapesti, 9. osztály tanuló (i276fb.pptx) megoldásait mellékeljük.

### Statistics:

 6 students sent a solution. 10 points: Antal János Benjamin, Fényes Balázs, Jákli Aida Karolina. 7 points: 3 students.

 Our web pages are supported by: Morgan Stanley


text:
### IBPS RRB PO 2017 Question 3

Instructions

In these questions, relationships between different elements is shown in the statements. The statements is followed by two conclusions. Study the conclusions based on the given statement and select the appropriate answer.

Question 3

# Statement K $$\geq$$ L > M $$\geq$$ N Conclusions I. N $$\leq$$ K II. N<K

Solution

In conclusion 1, it is given that N<=K. That's not possible as N is less than or equal to M which is absolutely less than K. Conclusion 2 is valid as it mentions that N < K. Hence, only conclusion 2 will follow.


text:
# The Cumber Manifesto

I propose we stop calling imaginary and complex numbers imaginary and complex numbers. I propose we throw them all in the same bucket called "Cumbers". This has several advantages, which I shall briefly enumerate.

First is the instant association with a cucumber. Now I don't have kids, so I don't know if Cucumbers are the new Broccoli, but when I was a kid I loved cucumbers as much as I do today. (Though I loved broccoli too, so...) Cucumbers are cool and green and friendly. When written down, Cumbers can even resemble a long cucumber: (3 + 4*j).

Second is just avoiding the names which can lead to confusion in children and some teenagers. I'd like young children to learn algebra, but young children may not be able to fully grasp that one word can have completely different meanings. So when they hear "Imaginary" they think "This doesn't correspond to anything real", or when they hear "Complex" they think "Oh no this is hard." This is compounded by the more important, sad fact that even high school calculus teachers don't know what complex numbers are useful for. I had a great teacher, he didn't know. He said vaguely "electrical engineering." Now I know better, know more, but that's a different subject. Calling them "Cumbers" gets rid of this potentially emotionally distressing situation in the names.

Third and finally is the humor aspect. When we're older we make jokes about Imaginary Friends and oh-so-sarcastically-hard Complex problems. But Cumbers are not without their humor. For example: "This problem is so cumbersome." You might want to call a Cumber with just rationals inside a "Q-cumber". There are also a couple dirty jokes to be had.

We don't even need to change the Set sign for Cumbers! I hope you'll join me in using that term in the future.

#### Posted on 2011-07-20 by Jach

Tags: math

LaTeX allowed in comments, use $\\...\\$\$ to wrap inline and $$...$$ to wrap blocks.


text:
# Problem

Given K variables, $a_1, a_2, a_3 \dots a_K$ and a value $N$, how many ways can we write $a_1 + a_2 + a_3 \dots a_K = N$, where $a_1, a_2, a_3 \dots a_K$ are non-negative integers?

For example, if $K = 3$ and $N=2$, there are 6 solutions.

a b c
-----
2 0 0
0 2 0
0 0 2
1 1 0
1 0 1
0 1 1

## Contest Analysis: BUET Inter-University Programming Contest – 2011, UVa 12424 – 12432

Last week (2015-08-21) we practiced with this set. Some of the problems didn’t have proper constraints, which caused some headaches. This contest originally followed Google Code Jam format with two subproblems ( small and large ) for each problem. Each of the sub-problems had a different constraint on them. But when they uploaded it online, they removed both constraints from some problems, making things confusing. We ended up guessing the constraints when solving them.

During contest time, we managed to solve $B, E$, and $H$. I was stuck with $F$. Should have moved on. $C$ and $D$ were far easier than $F$. Bad decision from my end.

# UVa 12424 – Answering Queries on a Tree

Complexity: $O(logN)$
Category: Segment Tree, DFS, LCA

At first, it seemed like a problem of Heavy Light Decomposition. But after a moment I realized it can be done without HLD.

Run a dfs from any node and make the tree rooted tree. Now consider the color $X$. For every node that has color $X$, the edge from its parent will have cost $1$. Since the root can also have color $X$, we need to add a dummy node $0$ and make that root. Now, run another dfs and calculate the distance from the root to each node. We repeat this for all $10$ color and build $10$ trees. Let us call tree with the color of node $X$, $T_X$.

Now, whenever we have an update to change node $u$ from color $X$ to color $Y$, it means that the edge entering $u$ in tree $T_X$ will now have a cost $0$. Since its cost decreased, the distance from the root of all the nodes in the subtree of $u$ will be lowered by $1$. We can apply this change using preorder traversal dfs + segment tree. Do the opposite for $T_Y$. Increase the value of all nodes under subtree $u$ in $T_Y$.

And for query $u$ and $v$, find the distance between these two nodes in each of the $10$ trees. This can be done in $O(logN)$ using LCA + Segment Tree.

# UVa 12425 – Best Friend

Complexity: $O(\sqrt{N} + \sqrt[3]{N} \times \text{Complexity of } \phi (N) )$
Category: Number Theory, Euler Phi, GCD

So for given integers $N$ and $X$, we have to find out how many number $I$ are there such that $gcd(N, I) \leq X$.

In order to calculate $gcd(N,I) \leq X$, I first need to be able to calculate how many numbers are there such that $gcd(N,I) = Y$. I started with a small value of $Y$ first. So the first thing I asked myself, how many numbers are there such that $gcd(N, I) = 1$? The answer is $\phi (N)$. Then I asked how many are there such that $gcd(N, I) = 2$?

This took a moment, but I soon realized, if $gcd(N,I)$ is equal $2$, then if I divide both $N$ and $I$ by $2$, then $gcd(\frac{N}{2},\frac{I}{2})$ will be equal to $1$. Now, all I had to calculate how many $I$ are there such that $gcd(\frac{N}{2},\frac{I}{2}) = 1$. The answer is $\phi (\frac{N}{2})$.

Therefore, there are $\phi (\frac{N}{Y})$ number of $I$ such that $gcd(N,I) = Y$.

Great. Now we can calculate number of $I$ such that $gcd(N,I) = Y$. Now, all we need to do is find the sum of all number of $I$ for which $gcd(N, I) = Y$ and $Y \leq X$. GCD of $N$ and $I$ can be as high as $10^{12}$, so running a loop won’t do.

Next I thought, what are the possible values of $g = gcd(N,I)$? Since $g$ is a number that divides $N$ and $I$, $g$ must be a divisor of $N$. So I simply calculated all the divisors of $N$ using a $\sqrt{N}$ loop. Next for each divisor $d$, I calculated $\phi ( \frac{N}{d})$ which is the number of ways to chose $I$ such that $gcd(N,I) = d$.

Now, for each query $X$, all I needed to do was find sum of $\phi ( \frac{N}{d} )$, where $d$ is a divisor of $N$ and $d \leq X$. Since all values of $\phi ( \frac{N}{d} )$ was precalculated, using cumalitive sum I answered it in $O(1)$.

# UVa 12426 – Counting Triangles

Complexity: $O(N^2logN)$
Category: Two Pointer, Geo, Binary Search

We need to choose three points of a convex hull such that the area does not exceed $K$.

First, we need to know, for two points $i$ and $j$, $j>i$, what is the point $m$ such that $(i,j,m)$ forms the largest triangle possible. This can be done by selecting two points with two loops and then using a ternary search. But I used two pointer technique to find $m$ for every pair of $(i,j)$ in $O(N)$.

After that, for ever pair of $(i,j)$ I used binary search twice. Once on points $[j+1,m]$ and once on points $[m+1,n]$. Using binary search I found the point $x$ which gives the highest area that does not exceed $K$. Then I added $x-j-1$ in the first BS and $n-1-m$ in the second case.

Careful about not adding a degenerate triangle. Handle the edge cases properly.

# UVa 12427 – Donkey of the Sultan

Complexity: $O(1)$
Category: Game Theory, Combinatorics, Nim Game, Bogus Nim

This game can be converted to into a game of pile. Let the distance between the left boundary and gold coin be $x$ and the distance between diamond and silver coin be $y$. Now, instead of playing on the board, we can play with two piles of height $x$ (first pile) and $y$ (second pile).

Moving gold coin left is same as removing one coin from the first pile. Moving diamond coin left is the same as increasing second pile by one. Moving silver coin left is same as removing one coin from the second pile. Moving gold and silver coin left is same as removing one coin from both first and second pile.

Now, note that is a state of $(x,y)$ is losing and I try to increase the second pile by one, my opponent then can simply take one from the second pile and put me back to the same situation. That is, increasing the second pile has no effect in this game. This is a “Bogus” move. We will ignore this move.

Next, I drew a $5 \times 5$ table and calculated the Win or Lose state of each possible $(x,y)$. I found that only when both $x$ and $y$ are even, the first person loses. That is the second person, me, wins the game when $x$ and $y$ both are even.

What are the possible values of $x$? $x$ can only be between $a_1$ and $a_2$. Find the number of even numbers in this range. Let this be $r_1$. Next, $y$ can be between $c_1$ and $c_2$. Let the number of even numbers in this range be $r_2$. The distance between gold and diamond has no effect in this game. So we can put any amount of gap there.

Therefore, number of possible combination is $r_1 \times r_2 \times (b_2 – b_1 + 1 )$.

# UVa 12428 – Enemy at the Gates

Complexity: $O(\sqrt{M})$

This was the easiest problem in the set. In this problem, we are given $N$ nodes and $M$ edges, we have to find out how many leaves can this graph have if we maximize leaves.

The problem says the graph will be connected. So I created a star-shaped graph with it using $N-1$ edges. Let the center node be $0$ and remaining nodes be the numbers from $1$ to $N-1$. This gives me $N-1$ critical edges. Then I checked if I still have more edges left? If I do, then I need to sacrifice a critical edge.

The first edge that gets sacrifice is a special case. This is because, no matter which two nodes you connect, it will reduce the number of critical edges by $2$. There is no helping it. So let’s connect $1$ and $2$ and reduce our edge by $1$ and critical edge by $2$.

Then if we still have more edges left, then we need to sacrifice another critical length. From now on, at each step, only one critical edge will be removed. Also, this time we can add $2$ edges to the graph by removing one critical edge. Connect an edge between $(3,1)$ and $(3,2)$. Reduce $M$ by $2$ and critical edge by $1$.

Next is node $4$. We can add $3$ edges by removing $1$ critical edge now. We need to keep on doing this until all edges finish.

I guess it is possible to solve the problem in $O(1)$ but I didn’t bother with it. The number of test case was small anyway.

# UVa 12429 – Finding Magic Triplets

Complexity: $O(N:logN)$
Category: Binary Indexed Tree, Number Theory

We have to find the number of triplets such that $a + b^2 \equiv c^3$ and $a \leq b \leq c$. Here is what I did.

Iterate over $c$ from $N$ to $1$ using a loop. Let the loop iterator be $i$. Now for each $i$, we do the following:

1. Find $x = ( i \times i \times i ) \mod k$ and store $x$ in a BIT. BIT stores all occurrences of $c$ and by iterating in reverse order we make sure that all $c$ in BIT is greater or equal to $i$.
2. Let $b = ( i \times i ) \mod k$. This is the current $b$ we are working with. In BIT we have $c$ which are $c geq b$. Now all we need is to find possible values of $a$.
3. Now, take any value of $c$ from BIT. For this $c$ and current $b$, how many ways can we choose $a$ so that $a + b \equiv c$. Notice that $a$ can be anything from $1$ to $k$, or $0$ to $k-1$. Therefore, no matter what is the value of $c$ we can chose $1$ number from $0$ to $k-1$ so that $a + b \equiv c$.

Let $y = \frac{i}{k}$. This means we have $y$ segments, in which value of $a$ spans from $0$ to $k-1$. So we add $y$ for each possible $c$ we take from BIT. Let $total$ be number of $c$ we have inserted till now. So we add $total \times y$ to $result$.

4. But it’s not over yet. What about the values of $a$ that we did not use. To be more exact, let $r = i \mod k$. If $r > 0$, then we have unused values of $a$. We need to use these.

But we have to be careful. We have used up values of $a$ from $1$ to $y \times k$. So the remaining $a$ we have is $1$ to $r$. $0$ is not included.

Since we don’t have all the values from $0$ to $k-1$, we are not able to handle all possible values $c$ anymore. How many can we handle exactly?

$a + b \equiv c$
$a \equiv c – b$

But we need $a$ can only be between $1$ and $r$.

$1 \leq c – b \leq r$
$\therefore 1+b \leq c \leq r + b$

Find out how many $c$ are there with values between $1+b$ and $r+b$ from BIT. Let this value be $z$. For each of those $c$ we can use one value of $a$ between $1$ to $r$. So add $z$ to $result$.

And that’s it. Be careful when handling edge cases in BIT.

# UVa 12430 – Grand Wedding

Complexity: $O(N logN)$
Category: DFS, Bicoloring, Binary Search

The constraint was missing. I assumed $N <= 10^6$.

We have to remove some edges and then assign guards such that no edge is left unguarded and no edge has guards on both ends. We have to output the maximize the value of the edges that we remove.

Binary search over the value of edges which we need to remove. Now, let’s say we removed all edges with the value greater or equal to $x$. How do we decide that a valid assignment of guards is possible in this problem?

Suppose all the nodes in the graph are colored white. If we assign guard in a node, then we color it black. Now, two white nodes cannot be adjacent cause that would mean the edge is left unguarded. Two black nodes cannot be adjacent otherwise guards will chat with each other. That is both ends of an edge cannot have the same color in the graph. This is possible when the graph has no cycle of odd length. If a graph has no cycle, then it is bi-colorable. So all we need to do is check if the graph is bi-colorable.

Now, two special cases. If we can bicolor the graph without removing any edge, then answer is $0$. If we have to remove all edges then answer is $-1$. Why? Cause in the problem it is said we can remove proper subset of edges. The full set is not a proper subset.

# UVa 12431 – Happy 10/9 Day

Complexity: $O(log^2N)$
Category: Divide and Conquor, Modular Exponentiation, Repeated Squaring

We have to find the value of:

$( d \times b^0 + d \times b^1 + d \times b^2 + … + d \times b^{n-1} ) \mod M$
$( d ( b^0 + b^1 + b^2 + … + b^{n-1} ) ) \mod M$.

Therefore, the problem boils down to finding the value of $( b^0 + b^1 + b^2 + … + b^{n-1} ) \mod M$. We cannot use the formula of geometric progression since $M$ and $b-1$ may not be coprime. So what do we do? We can use divide and conquer. How? Let me show you an example.

Suppose $f(n) = (b^0 + b^1 + b^2 + … + b^n)$. Let us find $f(5)$.

$f(5) = b^0 + b^1 + b^2 + b^3 + b^4 + b^5$
$f(5) = (b^0 + b^1 + b^2) + b^3 ( b^0 + b^1 + b^2)$
$f(5) = f(2) + b^3 \times f(2)$
$f(5) = f(2) \times (1 + b^3)$.

From this we can design a D&C in following way:

$\text{n is odd: }f(n) = f(\frac{n}{2}) \times ( 1 + b^{n/2 + 1 })$
$\text{n is even: }f(n) = f(n-1) + b^n$
$f(0) = 1$

Just apply modular arithmetic with the whole things. Also, note that $M$ can be as large as $10^{12}$, so $(a \times b)$ will overflow if they are multiplied directly, even after making them small by modulus $M$. So use repeated squaring method to multiply them.

# UVa 12432 – Inked Carpets

Complexity: Unknown
Category: Unknown

I didn’t try this problem yet. I guess this was the stopper.

# Conclusion

It was a good set. I especially enjoyed solving $B, D$, and $F$.

## Contest Analysis: IUT 6th National ICT Fest 2014, UVa 12830 – 12839

I participated in this contest last year. Our team “NSU Shinobis” managed to solve 5 and placed in the top 10 ( failed to find the rank list ). The IUT 7th ICT National Fest 2015 is going to be held next month, so I thought I would try to up solve the remaining problems. I tried to compile detailed hints for the problems here.

# UVa 12830 – A Football Stadium

Complexity: $O(N^3)$

Given $N$ points, we have to find the largest area of the rectangle which can fit such that there is no point inside the rectangle. Points on boundaries of the rectangle are allowed.

Now imagine a rectangle which has no point inside it and also no point on its boundary. Now focus on the top boundary of that rectangle. Since there is no point on that boundary, we can extend it up until it hits a point or limit. Same can be said for the bottom, left and right boundary. That is, the largest rectangle will have its boundary aligned with the limits or points.

Now let us fix the top and lower boundary of the rectangle. How many possible values can they take? Each boundary can take values of $y$-coordinate from one of the $N$ points or the limits $0$ and $W$. Using two nested loops, we can fix them.

Next we need to fix the left and right boundary. Lets us sort the points according to $x$ first and then according to $y$. Next we iterate over the points. Initially set the left boundary of rectangle aligned to $y$-axis, that is aligned with the left boundary of Sand Kingdom.

Now, for each point, if the $y$ coordinate of the point is above or below or on the boundary we fixed then we ignore them, cause they don’t cause any problem. But if they fall inside, then we need to process this point. We put the right boundary aligned to the $x$ coordinate of this point and calculate this rectangle.

But it’s not over. We shift the left boundary over to current right boundary and continue to process remaining points.

This is a classical problem of Kadane’s Algorithm. With two nested loops to fix upper and lower boundary and another loop inside iterating over $N$ points makes the complexity $O(N^3)$.

$O(N^2)$ solution is possible, by constructing a histogram for each row ( $O(N)$ ) and the calculating area of histogram in $O(N)$. But that’s not necessary here.

# UVa 12831 – Bob the Builder

Complexity: $O(\sqrt{V}E)$
Category: Max Flow, Bipartite Matching, Dinic’s Algorithm, Path Cover

Another classical problem, though we had a hard time solving this one. Mainly cause we didn’t realize this was a path cover problem which can be solved using Max Flow.

Take each number provided and generate all child. Consider each number a node and if it possible to generate $B$ from $A$, then add a directed edge from $A$ to $B$. When you are done, you will have DAG.

Now split all the nodes in two. We are going to create a bipartite graph now. On the left side, we will have all the original nodes and on the right side we will have the copy we got by splitting the nodes. Now, for each edge between $A$ and $B$, add an edge in the bipartite graph from $A$ on the left side to $B$ on the right side.

Find the matching ( or maximum flow ) of this graph by running Dinic’s Algorithm. The answer will be $\text{Total Nodes} – \text{Matching}$.

# UVa 12832 – Chicken Lover

Complexity: $O(M)$
Category: Expected Value, Probability, DP, Combination

If a shop can make $N$ different items, and in a single day prepares $K$ items from those $N$ items, then how many different sets of menus ($total$) can they make? $total = C^N_K$. Now, if they decide to make chicken that day for sure, how many sets of menus ( $chicken$ ) can they make now? $chicken = C^{N-1}_{K-1}$. So what is the probability $P$ that if I visit a shop I will get to eat chicken? $P = \frac{chicken}{total}$. And what is the probability that I will not eat chicken? $Q = 1- P$.

So now I know the probability of eating chicken for each shop. How do we find the expected value? We will find it using dynamic programming.

The states of dp only be the shop number. $dp(x)$ will give me the expected number of chicken that I can eat if I visit all shops starting from $x$. Our result will be $dp(1)$.

At each state, I have $P_i$ probability that I will eat chicken and $Q$ probability that I will not. So result for each state will be:

$dp ( pos ) = P \times ( 1 + dp ( pos + 1 ) + Q \times dp ( pos + 1 )$
$dp ( pos ) = P + P \times dp ( pos + 1 ) + Q \times dp ( pos + 1 )$
$dp ( pos ) = P + dp ( pos + 1 ) \times ( P + Q )$
$dp ( pos ) = P + dp ( pos + 1 )$.

In order to print the result in $\frac{A}{B}$ form, we need to avoid $double$ and use integer arithmetic in all places. I implemented my own fraction class for that purpose.

# UVa 12833 – Daily Potato

Complexity: $O(26 \times N)$
Category: String, Manacher’s Algorithm

For each query, we have to count the number of palindromes which are the substring of $S$, starts and ends with given $C$ and has exactly $X$ occurrences of $C$ in it. Since it deals with palindrome, perhaps it has something to do with Manacher’s Algorithm?

With Manacher’s Algorithm, we can find out the maximum length of palindrome in $O(N)$. But what’s more, we can actually generate an array $M$ which gives us, for each center in the extended string $E$, ( $aba$ when extended becomes ^#a#b#a#$ ) the maximum length of palindrome with that particular center. How can we use this knowledge to solve our problem? Let us consider the character$’a’$only. We can easily extend it for other characters by repeating the whole process$26$\times. Suppose we are working with center$x$. It has a palindrome from it with length$y$. Therefore, in the extended string of manacher, the palindrome starts from$x-y$and ends in$x+y$. Now, how many \times does$’a’$occurs in this palindrome? Using Cumulative Sum it is possible to answer in$O(1)$. Let that occurrence be$f = \text{# of times ‘a’ occurs in palindrome with center x}$. Let us mark this in another array$freq$. That is we mark it like$\text{freq[f]++}$, meaning we have$freq[f]$palindromes where$’a’$occurs$f$times. But wait, what if the palindrome does not start and end with$’a’$? Simple, we keep on throwing the leading and trailing character until it starts and ends with$’a’$and it will still have$f$occurrences of$’a’$in it. So we repeat this for all possible center. Now, if the query is to find the number of palindromes that starts and ends with$’a’$and$’a’$occurs exactly$X$\times, how do we solve it? First of all, our result will contain$res = freq[X]$in it. What’s more, our result will also contain$res \text{+=} freq[X+2] + freq[X+4] + freq[X+6] + …$. Why is that? Take any palindrome that contains more than$X$occurrences of$’a’$. Since they start and end with$’a’$, we can just throw them out of that palindrome and reduce the occurrence of$’a’$in it by$2$. After that, we keep on trimming down head and tail of that palindrome until we reach$’a’$again. That is, a palindrome with$Y$occurrences of$’a’$can be trimmed down to palindrome with$Y-2$,$Y-4$,$Y-6$,$…$occurrences of$’a’$. Instead of getting the result$res = freq[X] + freq[X+2] + freq[X+4] + \dots$we can just use cumulative sum again to find it in$O(1)$here. Just find the cumulative sum of alternate terms. # UVa 12834 – Extreme Terror Complexity:$O(N: logN )$Category: Adhoc This was the easiest problem. Each shop gives me some money ($income$) and then for that shop I have to give Godfather some cut ($expense$). So for each shop I get$profit = income – expense$. So I calculate profit for each shop and then sort them. I can now skip$K$shops. I will of course skip shops for which profit is negative as long as I am allowed to skip. # UVa 12835 – Fitting Pipes Again Complexity:$O(N!: N^2)$Category: Geometry, Trigonometry, Permutation, Packing Problem It’s a packing problem. At first glance, it seems like a tough problem but it’s not. Let us first define a few variables first. This is the polygon. Each polygon has two horizontal lines through it. We will call them the low and top line. Each side of the polygon has a length of$x$. The radius of the polygon is$r = \frac{x}{2} + y$. We are given the height of each polygon. But first, we will need to calculate the value of$x$and$y$. We can find their values using trigonometry.$y^2 + y^2 = x^22y^2 = x^2x = \sqrt{2y^2}$We also know that$h = y + x + y$. From that we can derive:$y + x + y = h2y+x = h2y + \sqrt{2y^2} = h2y + y\sqrt{2} = hy( 2 + \sqrt{2} ) = hy = \frac{h}{2} +\sqrt{2}$With the above, we can find the value of$y = \frac{h}{2} +\sqrt{2}$and$x = \sqrt{2y^2}$But why did we find their values? Okay, what happens when we put to polygon side by side? In order to solve this problem, we need to be able to find the distance between the center of two polygons$A$and$B$. Now if two polygons are of the same height and they are placed side by side, then the difference between their centers will be$d = r_a + r_b$. What happens when two polygons of arbitrary height come beside each other?$3$things can happen when two polygon$A$and$B$are placed side by side.$A$is on left of$B$. 1. Height of bottom line of$A$is higher than height of top line of$B$. In this case,$A$is so big that$B$slides inside the radius of$A$. 2. Height of bottom line of$B$is higher than height of top line of$A$. In this case$A$is so small that it slides inside the radius of$B$. 3. Nobody can slide inside each others radius. So$d = r_a + r_b$. We need to calculate the value of$d$for step$1$and$2$. That can also be easily done using trigonometry. Try to draw some diagram yourself. So we used$x$and$y$to find the value of$d$between two polygons. How do we use this to find the minimum width of the box? Suppose we are trying to pack the polygons in some order. Which order? We don’t know which order will give us minimum width so we try them all. There will be$N!$order. So for each order, what will be the minimum of width. First let’s take the first polygon, and put it inside the empty box such that it touches the left side of the box. We will calculate the center of each polygon relative to the left side of the box. The first box will have the center at$r_0$. Now take the second box. First, imagine there is no polygon in the box. There where will be the center of the second polygon? Ar$r_1$. Now, since there is a polygon, we will try to put it besides that one. Where will be the center now?$r_0 + d$. We will take the maximum possible center. Repeat this for the third polygon. Empty box, besides the first polygon, besides the second polygon. Take the maximum again. Repeat this for all polygon. From all polygon, find the one with the maximum center position. Add radius of that polygon to its center to find the width. Take the minimum width from all permutation. # UVa 12836 – Gain Battle Power Complexity:$O(N^2)$Category: Interval DP, LIS, Knuth Optimization First, we need to calculate the power of each Deatheater. We can do that by calculating LIS from both directions and then adding them. Once we calculate the power, we run an interval dp between$1$and$N$. The dp will have states$start$and$end$. Inside the dp a loop between start and end will run, choosing different cut sections. We will take the one with minimum value. But this results in$O(N^3)$solution. Using Knuth’s optimization we can reduce it to$O(N^2)$. # UVa 12837 – Hasmot Ali Professor Complexity:$O(100 \times |S|^2 )$Category: String, Trie, Data Structure We will create two trie trees. The first one will contain all the queries. Take a query and concatenate them in a special way. Take the first string of the query and add a$\text{‘#’}$and then reverse the second string of the query and attach it to result. That is, if we have$abc$and$pqr$as query, then special string will be$\text{abc#rqp}$. Insert all special strings for each query in the first tries. Now, let us process the main string$S$. We will take each of its suffixes and insert into the second trie. Now, when inserting the suffixes, each time a new node is created, we can say that we found a unique substring. Each time we find a unique substring we will process it further. Take the unique substring, and using brute force generate all possible special strings ( the one we made using query strings ) with the first and last characters of the unique string. We don’t need to take more than$10$characters from each end. For each of those special string we made from unique substring, we will query the first trie with it and find the node where it ends. We will add one to that node number in a global array. Once we finish processing all nodes in the second trie, we will simply traverse the first trie according to each query and print the result found in that node. # UVa 12838 – Identity Redemption Complexity: Unknown Category: Matching on General Graph I didn’t manage to solve this yet. It looks like matching on a general graph. # UVa 12839 – Judge in Queue Complexity:$O(N:logN)$Category: Data Structure, Heap We want to minimize the waiting time for each person. So first we will sort the people in descending order. Next, we will create a priority queue, which will contain all the service center along with the information about when that service center will be free. Initially, all service centers are free. Now, we take each person and take out the service center that will get free at the earliest time. The person had to originally wait$x$minutes and it took$y$minutes for the service to get free again. So the person had to wait for$x+y\$ minutes. We insert the service again inside the heap and update its free time by the time it takes to serve one person.

Repeat and keep track of the highest time a person had to wait.

# Conclusion

I hope the details are clear enough for everyone to understand. Let me know if you find any mistakes.


text:
# 18.4: Criteria for Spontaneous Change: The Second Law of Thermodynamics

Skills to Develop

• State and explain the second and third laws of thermodynamics
• Calculate entropy changes for phase transitions and chemical reactions under standard conditions

In the quest to identify a property that may reliably predict the spontaneity of a process, we have identified a very promising candidate: entropy. Processes that involve an increase in entropy of the systemS > 0) are very often spontaneous; however, examples to the contrary are plentiful. By expanding consideration of entropy changes to include the surroundings, we may reach a significant conclusion regarding the relation between this property and spontaneity. In thermodynamic models, the system and surroundings comprise everything, that is, the universe, and so the following is true:

$ΔS_\ce{univ}=ΔS_\ce{sys}+ΔS_\ce{surr} \label{$$\PageIndex{1}$$}$

To illustrate this relation, consider again the process of heat flow between two objects, one identified as the system and the other as the surroundings. There are three possibilities for such a process:

1. The objects are at different temperatures, and heat flows from the hotter to the cooler object. This is always observed to occur spontaneously. Designating the hotter object as the system and invoking the definition of entropy yields the following:
$ΔS_\ce{sys}=\dfrac{−q_\ce{rev}}{T_\ce{sys}}\hspace{20px}\ce{and}\hspace{20px}ΔS_\ce{surr}=\dfrac{q_\ce{rev}}{T_\ce{surr}} \label{$$\PageIndex{2}$$}$
The arithmetic signs of qrev denote the loss of heat by the system and the gain of heat by the surroundings. Since Tsys > Tsurr in this scenario, the magnitude of the entropy change for the surroundings will be greater than that for the system, and so the sum of ΔSsys and ΔSsurr will yield a positive value for ΔSuniv. This process involves an increase in the entropy of the universe.
2. The objects are at different temperatures, and heat flows from the cooler to the hotter object. This is never observed to occur spontaneously. Again designating the hotter object as the system and invoking the definition of entropy yields the following:
$ΔS_\ce{sys}=\dfrac{q_\ce{rev}}{T_\ce{sys}}\hspace{20px}\ce{and}\hspace{20px}ΔS_\ce{surr}=\dfrac{−q_\ce{rev}}{T_\ce{surr}} \label{$$\PageIndex{3}$$}$
The arithmetic signs of qrev denote the gain of heat by the system and the loss of heat by the surroundings. The magnitude of the entropy change for the surroundings will again be greater than that for the system, but in this case, the signs of the heat changes will yield a negative value for ΔSuniv. This process involves a decrease in the entropy of the universe.
3. The temperature difference between the objects is infinitesimally small, TsysTsurr, and so the heat flow is thermodynamically reversible. See the previous section’s discussion). In this case, the system and surroundings experience entropy changes that are equal in magnitude and therefore sum to yield a value of zero for ΔSuniv. This process involves no change in the entropy of the universe.

These results lead to a profound statement regarding the relation between entropy and spontaneity known as the second law of thermodynamics: all spontaneous changes cause an increase in the entropy of the universe. A summary of these three relations is provided in Table $$\PageIndex{1}$$.

 ΔSuniv > 0 spontaneous ΔSu niv < 0 nonspontaneous (spontaneous in opposite direction) ΔSuniv = 0 reversible (system is at equilibrium)

Definition: The Second Law of Thermodynamics

All spontaneous changes cause an increase in the entropy of the universe.

For many realistic applications, the surroundings are vast in comparison to the system. In such cases, the heat gained or lost by the surroundings as a result of some process represents a very small, nearly infinitesimal, fraction of its total thermal energy. For example, combustion of a fuel in air involves transfer of heat from a system (the fuel and oxygen molecules undergoing reaction) to surroundings that are infinitely more massive (the earth’s atmosphere). As a result, qsurr is a good approximation of qrev, and the second law may be stated as the following:

$ΔS_\ce{univ}=ΔS_\ce{sys}+ΔS_\ce{surr}=ΔS_\ce{sys}+\dfrac{q_\ce{surr}}{T} \label{$$\PageIndex{4}$$}$

We may use this equation to predict the spontaneity of a process as illustrated in Example $$\PageIndex{1}$$.

Example $$\PageIndex{1}$$: Will Ice Spontaneously Melt?

The entropy change for the process

$\ce{H2O}(s)⟶\ce{H2O}(l) \nonumber$

is 22.1 J/K and requires that the surroundings transfer 6.00 kJ of heat to the system. Is the process spontaneous at −10.00 °C? Is it spontaneous at +10.00 °C?

Solution

We can assess the spontaneity of the process by calculating the entropy change of the universe. If ΔSuniv is positive, then the process is spontaneous. At both temperatures, ΔSsys = 22.1 J/K and qsurr = −6.00 kJ.

At −10.00 °C (263.15 K), the following is true:

\begin{align} ΔS_\ce{univ}&=ΔS_\ce{sys}+ΔS_\ce{surr}=ΔS_\ce{sys}+\dfrac{q_\ce{surr}}{T} \nonumber\\ &=\mathrm{22.1\: J/K+\dfrac{−6.00×10^3\:J}{263.15\: K}=−0.7\:J/K} \nonumber \end{align} \nonumber

Suniv < 0, so melting is nonspontaneous (not spontaneous) at −10.0 °C.

At 10.00 °C (283.15 K), the following is true:

$ΔS_\ce{univ}=ΔS_\ce{sys}+\dfrac{q_\ce{surr}}{T}\nonumber$

$\mathrm{=22.1\:J/K+\dfrac{−6.00×10^3\:J}{283.15\: K}=+0.9\: J/K}\nonumber$

Suniv > 0, so melting is spontaneous at 10.00 °C.

Exercise $$\PageIndex{1}$$

Using this information, determine if liquid water will spontaneously freeze at the same temperatures. What can you say about the values of Suniv?

Entropy is a state function, and freezing is the opposite of melting. At −10.00 °C spontaneous, +0.7 J/K; at +10.00 °C nonspontaneous, −0.9 J/K.

### Gibbs Energy and Changes of Gibbs Energy

One of the challenges of using the second law of thermodynamics to determine if a process is spontaneous is that we must determine the entropy change for the system and the entropy change for the surroundings. An alternative approach involving a new thermodynamic property defined in terms of system properties only was introduced in the late nineteenth century by American mathematician Josiah Willard Gibbs. This new property is called the Gibbs free energy change (G) (or simply the free energy), and it is defined in terms of a system’s enthalpy and entropy as the following:

$G=H−TS \label{2}$

Free energy is a state function, and at constant temperature and pressure, the standard free energy change (ΔG°) may be expressed as the following:

$ΔG=ΔH−TΔS \label{3}$

(For simplicity’s sake, the subscript “sys” will be omitted henceforth.) We can understand the relationship between this system property and the spontaneity of a process by recalling the previously derived second law expression:

$ΔS_\ce{univ}=ΔS+\dfrac{q_\ce{surr}}{T} \label{4}$

The first law requires that qsurr = −qsys, and at constant pressure qsys = ΔH, and so this expression may be rewritten as the following:

$ΔS_\ce{univ}=ΔS−\dfrac{ΔH}{T} \label{$$\PageIndex{5}$$}$

ΔH is the enthalpy change of the system. Multiplying both sides of this equation by −T, and rearranging yields the following:

$−TΔS_\ce{univ}=ΔH−TΔS \label{$$\PageIndex{6}$$}$

Comparing this equation to the previous one for free energy change shows the following relation:

$ΔG=−TΔS_\ce{univ} \label{$$\PageIndex{7}$$}$

The free energy change is therefore a reliable indicator of the spontaneity of a process, being directly related to the previously identified spontaneity indicator, $$ΔS_{univ}$$. Table $$\PageIndex{2}$$ expands on  Table $$\PageIndex{2}$$ and summarizes the relation between the spontaneity of a process and the arithmetic signs of $$\Delta G$$ and $$\Delta S$$ indicators.

 ΔSuniv > 0 ΔG < 0 spontaneous ΔSuniv < 0 ΔG > 0 nonspontaneous ΔSuniv = 0 ΔG = 0 reversible (at equilibrium)

J. Willard Gibbs (1839–1903)

Born in Connecticut, Josiah Willard Gibbs attended Yale, as did his father, a professor of sacred literature at Yale, who was involved in the Amistad trial. In 1863, Gibbs was awarded the first engineering doctorate granted in the United States. He was appointed professor of mathematical physics at Yale in 1871, the first such professorship in the United States. His series of papers entitled “On the Equilibrium of Heterogeneous Substances” was the foundation of the field of physical chemistry and is considered one of the great achievements of the 19th century. Gibbs, whose work was translated into French by Le Châtelier, lived with his sister and brother-in-law until his death in 1903, shortly before the inauguration of the Nobel Prizes.

Gibbs energy is a state function, so its value depends only on the conditions of the initial and final states of the system that have undergone some change. A convenient and common approach to the calculation of free energy changes for physical and chemical reactions is by use of widely available compilations of standard state thermodynamic data. One method involves the use of standard enthalpies and entropies to compute standard free energy changes according to the following relation as demonstrated in Example $$\PageIndex{1}$$.

$ΔG°=ΔH°−TΔS° \label{$$\PageIndex{7}$$}$

Example $$\PageIndex{2}$$: Evaluation of ΔG°

Change from ΔH° and ΔS° Use standard enthalpy and entropy data from Appendix G to calculate the standard free energy change for the vaporization of water at room temperature (298 K). What does the computed value for ΔG° say about the spontaneity of this process?

Solution

The process of interest is the following:

$\ce{H2O}(l)⟶\ce{H2O}(g) \label{$$\PageIndex{8}$$} \nonumber$

The standard change in free energy may be calculated using the following equation:

$ΔG^\circ_{298}=ΔH°−TΔS° \label{$$\PageIndex{9}$$} \nonumber$

From Appendix G, here is the data:

Substance $$ΔH^\circ_\ce{f}\ce{(kJ/mol)}$$ $$S^\circ_{298}\textrm{(J/K⋅mol)}$$
H2O(l) −286.83 70.0
H2O(g) −241.82 188.8

Combining at 298 K:

$ΔH°=ΔH^\circ_{298}=ΔH^\circ_\ce{f}(\ce{H2O}(g))−ΔH^\circ_\ce{f}(\ce{H2O}(l)) \nonumber\\ =\mathrm{[−241.82\: kJ−(−285.83)]\:kJ/mol=44.01\: kJ/mol} \nonumber$
$ΔS°=ΔS^\circ_{298}=S^\circ_{298}(\ce{H2O}(g))−S^\circ_{298}(\ce{H2O}(l)) \nonumber\\ =\mathrm{188.8\:J/mol⋅K−70.0\:J/K=118.8\:J/mol⋅K} \nonumber$
$ΔG°=ΔH°−TΔS° \nonumber$

Converting everything into kJ and combining at 298 K:

$ΔG^\circ_{298}=ΔH°−TΔS° \nonumber$

$\mathrm{=44.01\: kJ/mol−(298\: K×118.8\:J/mol⋅K)×\dfrac{1\: kJ}{1000\: J}} \nonumber$

$\mathrm{44.01\: kJ/mol−35.4\: kJ/mol=8.6\: kJ/mol} \nonumber$

At 298 K (25 °C) $$ΔG^\circ_{298}>0$$, and so boiling is nonspontaneous (not spontaneous).

Exercise $$\PageIndex{2}$$

Use standard enthalpy and entropy data from Appendix G to calculate the standard free energy change for the reaction shown here (298 K). What does the computed value for ΔG° say about the spontaneity of this process?

$\ce{C2H6}(g)⟶\ce{H2}(g)+\ce{C2H4}(g) \nonumber$

$$ΔG^\circ_{298}=\mathrm{102.0\: kJ/mol}$$; the reaction is nonspontaneous (not spontaneous) at 25 °C.

Free energy changes may also use the standard free energy of formation $$(ΔG^\circ_\ce{f})$$, for each of the reactants and products involved in the reaction. The standard free energy of formation is the free energy change that accompanies the formation of one mole of a substance from its elements in their standard states. Similar to the standard enthalpies of formation, $$(ΔG^\circ_\ce{f})$$ is by definition zero for elemental substances under standard state conditions. The approach to computing the free energy change for a reaction using this approach is the same as that demonstrated previously for enthalpy and entropy changes. For the reaction

$m\ce{A}+n\ce{B}⟶x\ce{C}+y\ce{D},$

the standard free energy change at room temperature may be calculated as

$ΔG^\circ_{298}=ΔG°=∑νΔG^\circ_{298}(\ce{products})−∑νΔG^\circ_{298}(\ce{reactants})$

$=[xΔG^\circ_\ce{f}(\ce{C})+yΔG^\circ_\ce{f}(\ce{D})]−[mΔG^\circ_\ce{f}(\ce{A})+nΔG^\circ_\ce{f}(\ce{B})].$

Example $$\PageIndex{3}$$: Calculation of $$ΔG^\circ_{298}$$

Consider the decomposition of yellow mercury(II) oxide.

$\ce{HgO}(s,\,\ce{yellow})⟶\ce{Hg}(l)+\dfrac{1}{2}\ce{O2}(g) \nonumber$

Calculate the standard free energy change at room temperature, $$ΔG^\circ_{298}$$, using (a) standard free energies of formation and (b) standard enthalpies of formation and standard entropies. Do the results indicate the reaction to be spontaneous or nonspontaneous under standard conditions?

Solution

The required data are available in Appendix G and are shown here.

Compound $$ΔG^\circ_\ce{f}\:\mathrm{(kJ/mol)}$$ $$ΔH^\circ_\ce{f}\:\mathrm{(kJ/mol)}$$ $$S^\circ_{298}\:\textrm{(J/K⋅mol)}$$
HgO (s, yellow) −58.43 −90.46 71.13
Hg(l) 0 0 75.9
O2(g) 0 0 205.2

(a) Using free energies of formation:

$ΔG^\circ_{298}=∑νGS^\circ_{298}(\ce{products})−∑νΔG^\circ_{298}(\ce{reactants}) \nonumber$

$=\left[1ΔG^\circ_{298}\ce{Hg}(l)+\dfrac{1}{2}ΔG^\circ_{298}\ce{O2}(g)\right]−1ΔG^\circ_{298}\ce{HgO}(s,\,\ce{yellow}) \nonumber$

$\mathrm{=\left[1\:mol(0\: kJ/mol)+\dfrac{1}{2}mol(0\: kJ/mol)\right]−1\: mol(−58.43\: kJ/mol)=58.43\: kJ/mol} \nonumber$

(b) Using enthalpies and entropies of formation:

$ΔH^\circ_{298}=∑νΔH^\circ_{298}(\ce{products})−∑νΔH^\circ_{298}(\ce{reactants}) \nonumber$

$=\left[1ΔH^\circ_{298}\ce{Hg}(l)+\dfrac{1}{2}ΔH^\circ_{298}\ce{O2}(g)\right]−1ΔH^\circ_{298}\ce{HgO}(s,\,\ce{yellow}) \nonumber$

$\mathrm{=[1\: mol(0\: kJ/mol)+\dfrac{1}{2}mol(0\: kJ/mol)]−1\: mol(−90.46\: kJ/mol)=90.46\: kJ/mol} \nonumber$

$ΔS^\circ_{298}=∑νΔS^\circ_{298}(\ce{products})−∑νΔS^\circ_{298}(\ce{reactants}) \nonumber$

$=\left[1ΔS^\circ_{298}\ce{Hg}(l)+\dfrac{1}{2}ΔS^\circ_{298}\ce{O2}(g)\right]−1ΔS^\circ_{298}\ce{HgO}(s,\,\ce{yellow}) \nonumber$

$\mathrm{=\left[1\: mol(75.9\: J/mol\: K)+\dfrac{1}{2}mol(205.2\: J/mol\: K)\right]−1\: mol(71.13\: J/mol\: K)=107.4\: J/mol\: K} \nonumber$

$ΔG°=ΔH°−TΔS°=\mathrm{90.46\: kJ−298.15\: K×107.4\: J/K⋅mol×\dfrac{1\: kJ}{1000\: J}} \nonumber$

$ΔG°=\mathrm{(90.46−32.01)\:kJ/mol=58.45\: kJ/mol} \nonumber$

Both ways to calculate the standard free energy change at 25 °C give the same numerical value (to three significant figures), and both predict that the process is nonspontaneous (not spontaneous) at room temperature.

Exercise $$\PageIndex{3}$$

Calculate ΔG° using (a) free energies of formation and (b) enthalpies of formation and entropies (Appendix G). Do the results indicate the reaction to be spontaneous or nonspontaneous at 25 °C?

$\ce{C2H4}(g)⟶\ce{H2}(g)+\ce{C2H2}(g) \nonumber$

−141.5 kJ/mol, nonspontaneous

### Key Concepts and Summary

The second law of thermodynamics states that a spontaneous process increases the entropy of the universe, Suniv > 0. If ΔSuniv < 0, the process is nonspontaneous, and if ΔSuniv = 0, the system is at equilibrium. Gibbs free energy (G) is a state function defined with regard to system quantities only and may be used to predict the spontaneity of a process. A negative value for ΔG indicates a spontaneous process; a positive ΔG indicates a nonspontaneous process; and a ΔG of zero indicates that the system is at equilibrium. A number of approaches to the computation of free energy changes are possible.

### Key Equations

• $$ΔS^\circ=ΔS^\circ_{298}=∑νS^\circ_{298}(\ce{products})−∑νS^\circ_{298}(\ce{reactants})$$
• $$ΔS=\dfrac{q_\ce{rev}}{T}$$
• ΔSuniv = ΔSsys + ΔSsurr
• $$ΔS_\ce{univ}=ΔS_\ce{sys}+ΔS_\ce{surr}=ΔS_\ce{sys}+\dfrac{q_\ce{surr}}{T}$$
• ΔG = ΔHTΔS
• ΔG = ΔG° + RT ln Q
• ΔG° = −RT ln K

### Glossary

Gibbs free energy change (G)
thermodynamic property defined in terms of system enthalpy and entropy; all spontaneous processes involve a decrease in G
standard free energy change (ΔG°)
change in free energy for a process occurring under standard conditions (1 bar pressure for gases, 1 M concentration for solutions)
standard free energy of formation $$(ΔG^\circ_\ce{f})$$
change in free energy accompanying the formation of one mole of substance from its elements in their standard states
second law of thermodynamics
entropy of the universe increases for a spontaneous process
standard entropy (S°)
entropy for a substance at 1 bar pressure; tabulated values are usually determined at 298.15 K and denoted $$S^\circ_{298}$$
standard entropy change (ΔS°)
change in entropy for a reaction calculated using the standard entropies, usually at room temperature and denoted $$ΔS^\circ_{298}$$


text:
# Q.8 The diagonals of a rhombus measure 16 cm and 30 cm. Find its perimeter.

Answer :

Let ABCD be a rhombus whose diagonals intersect each other at O such that AC = 16 cm and BD = 30 cm
Since, the diagonals of a rhombus bisect each other at 90°.
$$\therefore$$ OA = OC = 8 cm and OB = OD = 15 cm
In right $$\triangle$$OAB,
$$AB^2 = OA^2 + OB^2$$ (By Pythagoras property)
= $$(8)^2+ (15)^2 = 64 + 225$$ = 289
$$\therefore$$AB =$$\sqrt{289}$$= 17 cm
Since AB = BC = CD = DA (Property of rhombus)
$$\therefore$$Required perimeter of rhombus = 4 × side = 4 × 17 = 68 cm.


text:
# Solve for variable

$$0 = \frac2{r-1}-\frac3{r+4}+\frac1{r+5}$$

So to my understanding I could give them all the same denominator by multiplying their denominators with each others denominators and numerators. Or could I just flip them all around? But that would mean that 0 would be a denominator and I don't think I'm allowed to do that :p. Can someone please help me out?

Thanks!

-
Is that $0 = \frac{2}{r-1}-\frac{3}{r+4}+\frac{1}{r+5}$? –  Peter Taylor Aug 21 '11 at 12:22
Yes, sorry im really bad with those math characters :( –  John Aug 21 '11 at 12:23
peter has it right –  John Aug 21 '11 at 12:24
Yes, bring them together; your denominator would be $(r-1)(r+4)(r+5)$, and the first term of your numerator will look like $2(r+4)(r+5)$... –  Ｊ. Ｍ. Aug 21 '11 at 12:29

As clarified in Peter's comment, the problem is

$$0 = \frac{2}{r-1}-\frac{3}{r+4}+\frac{1}{r+5}\;.$$

Excluding the poles $r=1$, $r=-4$ and $r=-5$, multiply through by the product of the denominators:

$$0=2(r+4)(r+5)-3(r-1)(r+5)+1(r-1)(r+4)\;.$$

The quadratic terms cancel, which leaves

$$\begin{eqnarray} 0 &=& 18r+40-12r+15+3r-4 \\ &=& 9r+51\;, \end{eqnarray}$$

and so $r=-51/9=-17/3$.

-
Thanks a lot for your reply! However im a bit confused how you canceled the quadratic terms. Could you please elaborate on the second step you have done? Thanks again! –  John Aug 21 '11 at 12:37
@John: The quadratic terms are $2r^2-3r^2+1r^2=(2-3+1)r^2=0r^2=0$. –  joriki Aug 21 '11 at 12:47


text:
### Find the word definition

##### Wiktionary
numerical analysis

n. (context mathematics English) The study of algorithms to solve mathematical problems concerning continuous sets of values (such as the real numbers, complex numbers or vector spaces).

##### Wikipedia
Numerical analysis

Numerical analysis is the study of algorithms that use numerical approximation (as opposed to general symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics).

One of the earliest mathematical writings is a Babylonian tablet from the Yale Babylonian Collection (YBC 7289), which gives a sexagesimal numerical approximation of $\sqrt{2}$, the length of the diagonal in a unit square. Being able to compute the sides of a triangle (and hence, being able to compute square roots) is extremely important, for instance, in astronomy, carpentry and construction.

Numerical analysis continues this long tradition of practical mathematical calculations. Much like the Babylonian approximation of $\sqrt{2}$, modern numerical analysis does not seek exact answers, because exact answers are often impossible to obtain in practice. Instead, much of numerical analysis is concerned with obtaining approximate solutions while maintaining reasonable bounds on errors.

Numerical analysis naturally finds applications in all fields of engineering and the physical sciences, but in the 21st century also the life sciences and even the arts have adopted elements of scientific computations. Ordinary differential equations appear in celestial mechanics (planets, stars and galaxies); numerical linear algebra is important for data analysis; stochastic differential equations and Markov chains are essential in simulating living cells for medicine and biology.

Before the advent of modern computers numerical methods often depended on hand interpolation in large printed tables. Since the mid 20th century, computers calculate the required functions instead. These same interpolation formulas nevertheless continue to be used as part of the software algorithms for solving differential equations.


text:
There is a major confusion embedded in your mind, a term that is trying to mean too much.

That term is “Mathematics”.

If you ask the average layperson what they think of mathematics, their reaction will range from mild distaste to pure hatred. The word “mathematics” evokes boring theorems and arduously memorized proofs. It brings to mind the strange and archaic symbols used to express obvious-in-retrospect ideas.

$\sum\limits_{n=0}^\infty x_n$

If you ask someone who has studied engineering or the sciences what they think of mathematics, they will tell you that math is not something which can be loved or hated, for math is simply The Rules. It is any pattern, any symmetry, any abstraction. You can no more hate math than you can hate the fact that reality is ordered. Sure, the language of math is a bit old, but symbols are not symbolism. Math is not the language, it’s what the language says.

If you ask a mathematician what they think of mathematics, they will answer that math is the exploration of the rules. Given any axioms, math is about plumbing the logical depths that those axioms imply. It’s about listening to what the rules say and discovering new true things. It requires incredible creativity and the rewards are boundless, but it’s not for everyone.

These are three wildly different definitions for “mathematics”. Which is true?

Is math $\Sigma$ and $+$ and $\frac{1}{4}$ and the other cumbersome notation?

Is it the underlying truths of any system, regardless of the notation used?

Or is it the exploration of underlying rules, the pursuit of truth?

Mathematics is all of these things. It is a word that means too much.

Simplifience discards the term “Mathematics”. We shatter it into its component parts and use those instead.

The underlying rules of any system don’t need a special name. It’s enough to say that we have a model or a system. Anything that works has Rules which flow from Axioms.

The language and notation used to describe such rules will be referred to as the “formalization”. Models and systems have formalizations. If they work, you can figure out how they work and write it down. The specific squiggles that you use are inconsequential.

The exploration of rules in pursuit of new truths is not within our scope. Exploration of underlying rules is among the noblest of pursuits. It leads to deep and unexpected revelations which greatly expand our knowledge of the universe. It is the realm of those who wish to step beyond simplifience and discover new laws of reality.

Math is not a single word: it is one label trying to mean too many things. It is a contrive. We choose to discard the word. We shatter it and move on.


text:
# Manuals/calci/PARTP

PARTP (n,k)

where

• and are any integers.
• PARTP() shows the number of partitions of a given number.

## Description

PARTP(n,k)

• is any integer. is the number of ways.
• A partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers.
• Two sums that differ only in the order of their summands are considered the same partition.
• By convention, partitions are usually ordered from largest to smallest.
• Partition of a number is also called the number of unrestricted partition.
• When explicitly listing the partitions of a number n, the simplest form is the so-called natural representation which simply gives the sequence of numbers in the representation.
• The multiplicity representation instead gives the number of times each number occurs together with that number.

## Examples

1. PARTP(10,3) = 8
2. PARTP(54,10) = 29292

Partitions