text:
# Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it because of master theorem), and to find an upper bound, I use induction. I tried to show that $T(n)\leq cn^{2}\log n$ but that did not work, I got $T(n)\leq cn^{2}\log n+n^{2}$. Then I tried to show that, if $T(n)\leq c_{1}n^{2}\log n-c_{2}n^{2}$, then it is also $O(n^{2}\log n)$, but that also did not work and I got $T(n)\leq c_{1}n^{2}\log(n/2)-c_{2}n^{2}+n^{2}$. What trick can I do to show that? Thanks

-
What happens when $n$ is odd or just not a power of $2$? –  Dennis Gulko Mar 3 '13 at 12:37
We can ignore these cases –  bigO Mar 3 '13 at 12:39
In that case perhaps it would be better to write $t(2n)=4t(n)+n^{2}$? –  Daniel Littlewood Mar 3 '13 at 12:42
Its probably $T(\lfloor \frac{n}{2} \rfloor)$, but the floor doesn't make a difference when analysing asymptotic behaviour. –  Ivan Loh Mar 3 '13 at 12:48

If $T(\frac{n}{2}) \leq c(\frac{n}{2})^2\log_2(\frac{n}{2})+T(1)$, then \begin{align} T(n)=4T\left(\frac{n}{2}\right)+n^2 & \leq 4c\left(\frac{n}{2}\right)^2\log_2\left(\frac{n}{2}\right)+4T(1)+n^2 \\ &=cn^2\log_2(n)-cn^2+4T(1)+n^2 \\ &\leq cn^2\log_2(n)+T(1) \end{align} for $c \geq 1+3T(1)$.

-
Thanks, but i did not understand how you get -cn^2 at the 3rd line? –  bigO Mar 3 '13 at 13:01
i get it now, thank you! –  bigO Mar 3 '13 at 13:05

By way of enrichment we solve another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = 4 T(\lfloor n/2 \rfloor) + n^2.$$

Furthermore let the base two representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$

Then we can unroll the recurrence to obtain the following exact formula for $n\ge 1$ $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 4^j \left( \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} \right)^2 = \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k\right)^2.$$

Now to get an upper bound consider a string of one digits which yields $$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k\right)^2.$$

Note that this bound is attained and cannot be improved. It simplifies to $$\left(4 \lfloor \log_2 n \rfloor - \frac{8}{3}\right) \times 4^{\lfloor \log_2 n \rfloor} + 4 \times 2^{\lfloor \log_2 n \rfloor} - \frac{1}{3}.$$

The lower bound is for the case of a one digit followed by a string of zeros and yields $$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^{2\lfloor \log_2 n \rfloor}.$$ It simplifies to $$(1+\lfloor \log_2 n \rfloor) 2^{2\lfloor \log_2 n \rfloor}.$$

Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$\color{#006}{\lfloor \log_2 n \rfloor 2^{2 \lfloor \log_2 n \rfloor} \in \Theta\left(\log_2 n \times 2^{2 \log_2 n}\right) = \Theta\left(\log n \times n^2\right)}.$$

These are both in agreement with what the Master theorem would produce.

This MSE link has a series of similar calculations.

-


text:
Page updated: October 23, 2020
Author: Curtis Mobley
View PDF

# Historical Notation

As noted in Level 1, diﬀerent ﬁelds of science have developed diﬀerent terminology and notation for the same physical quantities. Tabel shows the ”historic” and ”modern” notations seen in oceanograpic literature. The recommended (modern) notation came into use the late 1970s and is employed, for example, in Jerlov (1976) and further reﬁned in Morel and Smith (1982). The historic notation is generally found in works published before the late 1970’s, most notably in Preisendorfer’s 1977 opus magnum Hydrologic Optics.

 Quantity SI Units Recommended Symbol Historic Symbol radiant energy $J$ $Q$ $U$ radiant power $W$ $\Phi$ $P$ radiant intensity $W\phantom{\rule{2.6108pt}{0ex}}s{r}^{-1}$ $I$ $J$ radiance $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}\phantom{\rule{2.6108pt}{0ex}}s{r}^{-1}$ $L$ $N$ plane irradiance $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}$ $E$ $H$ downward plane irradiance $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}$ ${E}_{d}$ $H\left(-\right)$ upward plane irradiance $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}$ ${E}_{u}$ $H\left(+\right)$ scalar irradiance $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}$ ${E}_{o}$ $h$ downward scalar irradiance $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}$ ${E}_{od}$ $h\left(-\right)$ upward scalar irradiance $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}$ ${E}_{ou}$ $h\left(+\right)$ vector irradiance $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}$ $\stackrel{\to }{E}$ $\stackrel{\to }{H}$ vertical net irradiance $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}$ ${E}_{d}-{E}_{u}$ — emittance $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}$ $M$ $W$ photosynthetically available radiation $photons\phantom{\rule{2.6108pt}{0ex}}{s}^{-1}\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}$ $PAR$ or ${E}_{PAR}$ —

Table 1: Terms, units, and symbols for radiometric quantities commonly used in hydrologic optics. The quantities as shown represent broadband measurements. For narrow band (monochromatic) measurements, add the adjective “spectral” to the term, add $n{m}^{-1}$ to the units, and add a wavelength index $\lambda$ to the symbol, e.g., spectral radiance, ${L}_{\lambda }$ or $L\left(\lambda \right)$, with units of $W\phantom{\rule{2.6108pt}{0ex}}{m}^{-2}\phantom{\rule{2.6108pt}{0ex}}s{r}^{-1}\phantom{\rule{2.6108pt}{0ex}}n{m}^{-1}$. PAR is inherently broadband.

It is occasionally convenient to distinguish conceptually between photons leaving a surface and photons arriving at a surface. In radiative transfer theory, ﬁeld radiance ${L}^{-}$ refers to the radiance of photons arriving at a surface; this is the quantity measured by a radiance meter. Surface radiance ${L}^{+}$ is the radiance attributed to a real or imaginary surface emitting photons. Irradiance $E$ refers to photons incident onto a surface; the corresponding measure of photons leaving a surface is denoted by radiant exitance or emittance $M$. Likewise, intensity can be subdivided into ﬁeld intensity ${I}^{-}$ and surface intensity ${I}^{+}$. The ﬁgure summarizes this hierarchy of radiometric concepts.

format: plain


text:
• Volume 30, Issue 5

May 1988,   pages  1-442

• Indications of superconductivity in the 200–300K range in the Bi-Ca-Sr-Cu-O system

Some of the Bi-Ca-Sr-Cu-O compositions show indications of onset of superconductivity in the 200–300 K region, possibly due to the intergrowth of different layered sequences.

• Circular orbits of an electron around a proton in Schwarzschild geometry

The energy of an electron in circular orbits around a proton in Schwarzschild geometry has been investigated and is found to be red shifted. The electrical dipole moment of such a system is also estimated.

• Non-statistical structures in12C(15N,4He)23Na reaction

The data on theϑlab=7° excitation functions of12C(15N,4He)23Na reaction betweenEcm=9.42 and 17.33 MeV for 28 states upto an excitation energy of 8.940 MeV in23Na have been subjected to statistical analysis. In addition to statistical fluctuations, the results of the analysis indicate the existence of non-statistical structures atEcm=10.66, 10.93, 11.38, 12.62, 13.16, 15.32 and 16.18 MeV.

• The minimax technique in relativistic Hartree-Fock calculations

Using the set of trial spinors$$\left\{ {N_i \left( {_{\hat \Omega _i u_i }^{u_i } } \right), i = 1, \ldots , N} \right\}$$ and the Dirac-Coulomb Hamiltonian (HDC) we discuss the role of the minimax theorem in relativistic Hartree-Fock calculations. In principle, the minimax theorem guarantees the occurrence of an upper bound. We also consider a scaling of the functionsui and discuss the condition to derive the relativistic hypervirial theorem; the variational procedure represented by the condition serves as an example of the minimax technique. Single zeta calculations onH2+,H2 and He are analysed. The effect of enlarging the basis is investigated for the He atom. The “upper bound” obtained by usingcoherent basis spinors differs from the result of the (random) linear variation using the kinetically balanced basis set by an amount which is at most of orderc−4. Use of thecoherent basis set is advocated.

• Temperature variation of the Debye-Waller factors of metal and halide ions in CsCl-Br solid solutions between room temperature and 90°K by powder X-ray diffraction

Solid solutions of CsCl-Br in different molal concentrations were prepared and X-ray diffractograms taken. The integrated intensities of the Bragg peaks have been estimated and structure factors were obtained. The crystal lattice in each of these solid solution samples is made up of a random distribution of Cs+, Cl and Br ions depending upon the molal concentration. A pseudo-atom model has been proposed in which the Cs+ ions occupy (000) position and a pseudo-atom occupies (1/2 1/2 1/2) position. The presence of incoherence scattering in these solid solutions has been considered by applying the necessary correction to the atomic scattering factors. The integrated intensities have been analysed and the temperature variation of the Debye-Waller factors of the metal (Cs+) ion and the pseudo ion (CB) have been estimated.

• Specific heat of YBa2Cu3O7−x from 4.2 to 60 K

The specific heat of superconducting oxide compound, YBa2Cu3O7 −x, is studied using a quasi-adiabatic calorimeter from 4.2 to 60 K. The analysis of the specific heat data below 15 K gives a value of 17 mJ/mole K2 for the electronic heat capacity coefficient. The value ofθD(0) is determined to be 397±8 K. The variation ofθD with temperature was calculated in the temperature range 4.2 to 60 K.

• Lattice dynamics of MgSiO3 perovskite

A lattice dynamical study of the geophysically important mineral MgSiO3 in its orthorhombic perovskite phase, with space group Pnma (D2h16) has been carried out using a rigid ion model, with the potential consisting of Coulombic and short-ranged interactions. With the help of program DISPR, the ionic charges and radii were optimized using the equilibrium conditions. The resulting potential model is employed to predict the elastic constants and the phonon dispersion relations. The computed long wavelength optic modes are in good agreement with the corresponding experimental Raman and infrared active bands. The phonon density of states has been obtained and is used to evaluate the specific heat, the mean square displacements and thermal parameters of atoms.

• Threshold pump strain for parametric amplification inn-indium antimonide

Phenomenological approach has been used to determine the threshold pump strain by assuming that at this strain the pump generates an electric field for which the drift velocity of the carriers equals the sound velocity. Numerical values obtained forn-InSb have been compared with similar studies which are based on Boltzmann transport approach.

• Mass enhancement factor for Pd and Pt

We report calculations of the mass enhancement factors for Pd and Pt by comparing the physical quantities using the interpolation scheme band structure, with the corresponding experimental data. Our results are compared with other theoretical calculations.

• # Pramana – Journal of Physics

Current Issue
Volume 93 | Issue 6
December 2019

• # Editorial Note on Continuous Article Publication

Posted on July 25, 2019


text:
# Solve for x if given

If given $$14^x + 23^{2x} = k$$

For all $k \in \mathbb{N}$. How to arrive at $x$?

• I doubt there is a clear algebraic way to handle this for general $k$. The function $f(x)=14^x+23^{2x}$ increases montonically so there is a unique solution for any natural number $k$ ...numerical methods will find it, but I doubt there will be a reasonable closed formula. Of course, I might have that wrong...but checking the form of the solution for modest $k$ doesn't suggest much. – lulu Jan 6 '17 at 14:33
• Alas, logs don't work well with sums. That is to say, $\log (a+b)$ isn't any sort of nice function of $\log a,\log b$. – lulu Jan 6 '17 at 14:38
• The answer to this question will be a set of values of $x$, and not just one value, right? – Shreyas S Jan 6 '17 at 14:38

I suggest using Newton-Raphson method. It's a numerical method, but very efficient.

The standard formulation is this:

To solve $f(x)=0$, start with an estimate $x_0$

Calculate $x_1=x_o-\dfrac {f(x_0)}{f'(x_0)}$

Continue to calculate $x_{n+1}=x_n-\dfrac {f(x_n)}{f'(x_n)}$

You should get a sequence of values $x_0, x_1, ... , x_n$ that converge to a root.

Note that this can not tell you how many roots there are - if you suspect that there more than one root, then you will have to take a number of different starting points.

In your case the equation $14^x+23^{2x}=k$ can be rewritten as $14^x+23^{2x}-k=0$, so $f(x)=14^x+23^{2x}-k$

This can be rewritten as $f(x)=e^{(\log 14)x}+e^{(2\log 23)x}-k$

Hence $f'(x)=(\log 14)e^{(\log 14)x}+(2\log 23)e^{(2\log 23)x}$

So $x_{n+1}=x_n-\dfrac {e^{(\log 14)x_n}+e^{(2\log 23)x_n}-k}{(\log 14)e^{(\log 14)x_n}+(2\log 23)e^{(2\log 23)x_n}}$

Fixed point iteration:

$$23^{2x}=k-14^x$$

$$2x=\log_{23}(k-14^x)$$

$$x=\frac12\log_{23}(k-14^x)$$

So for some $x_0\approx x$, we can use the following:

$$x_{n+1}=\frac12\log_{23}(k-14^{x_n})$$

For example, with $k=13$ and $x_0=0.3$,

$x_1=\frac12\log_{23}(13-14^{0.3})=0.3793470222$

$x_2=0.37156366654$

$x_3=0.372419725772$

etc. And $x=\lim_{n\to\infty}x_n$.

• Yes, but very slow convergence for small $k$ – tomi Jan 6 '17 at 17:46
• @tomi I agree, but the other answer took Newtons method, so... – Simply Beautiful Art Jan 6 '17 at 17:47

As already said in answers and comments, Newton method is probably the best and simplest way to find the zero of $$f(x)=14^x + 23^{2x} - k$$ From a practical point of view, I would suggest to use instead $$g(x)=\log \left(14^x+23^{2 x}\right)-\log(k)$$ which is much better conditioned (just by curiosity, plot $14^x + 23^{2x}$ and $\log \left(14^x+23^{2 x}\right)$).

As you said in a comment, using $f(x)$, the convergence is quite slow for small values of $k$.

For illustration purposes, let us use both functions for $k=0.001$ starting using $x_0=0$.

For $f(x)$, the iterates would be $$\left( \begin{array}{cc} n & x_n \\ 0 & 0 \\ 1 & -0.224353505 \\ 2 & -0.490433809 \\ 3 & -0.805641173 \\ 4 & -1.156949545 \\ 5 & -1.520584615 \\ 6 & -1.876683719 \\ 7 & -2.201538319 \\ 8 & -2.453972852 \\ 9 & -2.586800792 \\ 10 & -2.616322943 \\ 11 & -2.617534838 \\ 12 & -2.617536781 \\ \end{array} \right)$$

while, for $g(x)$, they would be $$\left( \begin{array}{cc} n & x_n \\ 0 & 0 \\ 1 & -1.706142182 \\ 2 & -2.615735506 \\ 3 & -2.617536780 \\ 4 & -2.617536781 \\ \end{array} \right)$$

The same would apply to large values of $k$.

For $k >0 \in \mathbb{N}$, the graph of $\log \left(14^x+23^{2 x}\right)$ is almost a straight line.


text:
# 001 Two sum

Original Description: Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

• 要求： 给一个数组和目标和，求数组内相加等于目标和的两个元素的index。
• 题目假设有唯一解，元素不可重复使用

• 返回： index

• 例子：
• input: [2, 7, 11, 15], target = 9
• output: [0,1]

## Solution

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
lookup = {}
for i, num in enumerate(nums):
if target - num in lookup:
return [lookup[target - num], i]
lookup[num] = i
return []


text:
## Chemistry: Principles and Practice (3rd Edition)

(a) $^{35}_{17}$Cl$^{-}$ (b) $^{39}_{19}$K$^{+}$
To find the full chemical symbol of an element/ion, we need to find the following pieces of information: elemental symbol, mass number, atomic number, and charge. (a) $^{35}_{17}$Cl$^{-}$ Looking at the periodic table, the halogen (group 17) element that has mass number closest to 35 is chlorine (Cl). To find the full chemical symbol for this element, we also need its atomic number, which is 17, according to the periodic table. We will also include the charge of the element, which is 1-, in the chemical symbol. (b) $^{39}_{19}$K$^{+}$ The alkali metals are the elements of group 1 on the periodic table. If the ion has a 1+ charge, that means that the number of protons is one greater than the number of electrons; if the number of electrons is 18, then the number of protons for this element is 19. According to the periodic table, the alkali metal with an atomic number of 19 is potassium (K). To find the mass number, we add the number of protons (19) to the number of neutrons (20) to get 39.


text:
# How to win big in eBay auctions, Part II: Winning stuff for free

So I promised I’d show how there’s a perfect Bayesian equilibrium in the eBay setup where all people pay only the price at which the bidding started, $\pi_0$. How’s that, you say? Won’t people want to bid up the price, if they’re willing to pay more?

The key to this equilibrium is, obviously, to remove the incentive to bid any higher. Since, in eBay, the highest bid up to any given point is not observed, we can describe perfect Bayesian equilibria based on beliefs for those situations if they were to come up. Thus, if any bidder bids something other than $\pi_0$ at any time except for the last moment, the other bidders can plausibly believe that this bidder has bid something ridiculously high, and so will respond by bidding up the price of the item, knowing that they have nothing to lose by doing so. This way, they can punish any bidder who deviates by bidding higher than $\pi_0$, so no one will do so.

For this equilibrium to work, we must also consider the timing and tie-breakers. eBay has structured its auction mechanism so that, once there is at least one bid on an item, all bids must be greater than the current price. This means that at most one person can bid $\pi_0$; the rest, if they will bid, must bid more. We can resolve this issue by stipulating that all bidders try to bid $\pi_0$ at some time $\tau$, and one of these, chosen randomly, does so successfully. Meanwhile, anyone who bids at some other time (rather than the last minute) is believed to have again bid something ridiculously high, and punished in the same way as the one who bids something different from $\pi_0$. Again, this will ensure that everyone bids only at $\tau$, except for maybe at the last moment when no one has time to respond to their bid.

We have to (finally) deal with what happens at the last moment. Suppose bidder $i$ is the lucky guy who successfully submitted his bid earlier at time $\tau$. At the last moment, to discourage others from trying to outbid him, now he is the one who bids ridiculously high. Knowing that they cannot win the item, no one else tries to submit a bid at the last moment.

One can formally check that this is indeed a perfect Bayesian equilibrium. Though this is unlikely to ever happen in reality, this shows the lack of uniqueness of symmetric equilibria (in the sense that all people’s strategies are ex ante the same) in eBay’s setup, and that we can get a pretty sweet outcome given the right beliefs. Pretty cool, huh?


text:
# Tag Info

46

I've had good experiences with Inkscape. It has a GUI interface, but allows you to enter coordinates directly if you want, and it's scriptable. There is a plug-in that allows you to enter LaTeX directly (for labels and such). The downside is that it is very much still in development, so sometimes you find that a feature you want is not completely ...

42

I'm learning TikZ (a drawing package for LaTeX) as we speak. It's good for two-dimensional line drawings, the syntax for specifying shapes and curves is extremely versatile, but the learning curve is steeper than LaTeX even. There is a superb gallery of TikZ examples. Here is another collection of neat TikZ examples on SE.tex.

33

I'll interpret your term diagram as "any fancy image that captures some physics". For this I can hardly recommend anything else then MetaPost. It's on par with TeX in being a little hard to learn but once you do master the basics you won't believe you could have ever used anything else (in particular, GIMP and Inkscape; good analogy here would be to TeX vs. ...

27

First of all do not use a raster graphics software like Gimp to draw pictures. This has serious disadvantages when you want to make screen readable documents (the picture pixelizes). For this purpose always use vector graphics. Wikipedia has a nice list of vector graphics software. Among them, I'd recommend the following: Inkscape (Cross-platform): ...

16

Some software I have used or has been recommended to me for physics-related work: WolframAlpha -- when I don't have Maple around, I use it for simple symbolic calculations Maxima -- free open source alternative to Maple/Mathematica Sage -- quite an interesting open source symbolic/numerical package, you can try it online at sagenb.org Scilab/GNU Octave -- ...

12

First off, physics tends to provide a very good background for people who move on to study problems in other areas, which is perhaps why there is a lot of cross-over to computer science. However, there are also a number of areas at the interface of computer science and physics which attract people from both sides: Computer hardware (which is generally ...

12

I would try matplotlib, but first check here and decide if these pictures satisfies your needs. Also click some picture and inspect source code.

11

I'll chip in here because I'm a research student and I work with a stellar evolution code (the Cambridge STARS code) more-or-less daily. Regarding some of the comments to the question, stellar evolution is actually quite fast, depending what code you use. Certainly, it isn't like hydrodynamics or N-body simulations like those used in galaxy ...

10

You can perform $\LaTeX$ search - that is, write formula in LaTeX in an appropriate search engine: http://www.latexsearch.com/ However, as one can type the same expression in different ways and with different symbols, I never used it it practice. (Anyone did?)

10

It most certainly exist outside secret labs :) Like Gerben wrote, the fields are called molecular dynamics (MD) and quantum chemistry which, as computers grow faster, will be essential tools of nanotechnology and medicine. Molecular Dynamics is currently implemented by making certain approximations in that electron motion is not explicitely modelled. In ...

9

Just for completeness, I'll leave this here: It's always possible to compose your illustrations in raw postscript! Postscript is itself a Forth-like programming language. It's particularly useful for illustrations that lend themselves to being generated procedurally. If postscript itself is too low-level, one can often write a script in some other ...

9

Sometimes raster graphics is also necessary. I often used POV-Ray to make some illustrations. It may be prepared with any size using the same script with description of the picture, that avoid scaling problem. But it is not a graphical editor and fast only for preparation of simple pictures.

9

The two main free destop programs that I know about, Stellarium and Celestia, do not include the proper motion of the stars when they move forward and backward in time. At least according to documentation that I've seen. These programs claim to do it but I have no experience with them: Home Planet (free) Starry Night (commercial) The Sky (commercial) ...

9

Related post in SO. My personal favorite is Asymtpote which is like MetaPost on steroids. A gallery is here.

9

It is probably worth your while to buy Mathematica, Maple, or Matlab, depending on your needs. I wish it weren't so, but this is one area in which the commercial tools are still vastly better than their free counterparts. If you are a student, you can buy these at fairly afforable prices. Maple 14 Student Edition is only $99. Mathematica for Students is ... 9 First of all, I do not have any experience with this, I am an Astronomy hobbyist at best. So I am just going to present what I found with minimal comment at this time. I found this web page that links to several programs: http://nbody.sourceforge.net/ They link to the University of Washington and their n-body shop. I don't know what your status must be ... 7 Yes, NASA's FTools software contains a program that will do this for you. Go to the FTools website and download a copy of the HEATOOLS. You want to specify that you want the Fimage package on the download page. Since you're running windows, you'll proabably need to download the PC-Cygwin package and install Cygwin as well as there is no native Windows ... 7 For drawing Feynman diagrams with SVG, I have developed jQuery.Feyn to make it easier (see the screenshot below). 7 There are, of course, a lot of codes floating around. Which of them you should choose, depends on what you want to calculate exactly. Here I mention four possibilities: 1) CALHEP - this package takes you from a given Lagrangian through its Feynmann rules to the calculation of cross sections. 2) xloops - this package calculates the 1-PI Feynman diagrams ... 7 No there isn't, but I've always wanted to write one. When I was an undergrad, I thought about designing quantum computer games. The idea was to make a simulation which would get people used to quantum stuff: Here were the ideas I had back then (never implemented past undergraduate daydreams): Spin-1/2 flight combat: You fly carrying a spinor, which ... 7 I've recently discovered Cadabra. A field-theory motivated approach to computer algebra I'm really impressed. 6 The industrial tool is zemax; however, it is very expensive. If you just want to make diagrams, the TeX package pst-optics might do the trick. In the gaussian beam regime, optocad (free) is a tool often used in the laser interferometer gravitational wave detector community. 6 I'd like to add that GNU Octave is a very good free alternative to Matlab. Contrary to Scilab which does not aim at being compatible with Matlab, you can practically run your Matlab scripts with Octave with very few modifications (at least with their latest version). 6 Sage is a Python based system (including Numpy and Scipy) which includes a symbolic computation module. From the Sage homepage: Sage is a free open-source mathematics software system licensed under the GPL. It combines the power of many existing open-source packages into a common Python-based interface. Mission: Creating a viable free open source ... 6 Goptical GNU-Optical Description Goptical is a C++ optical design and simulation library. Goptical is free software and is part of the GNU project. It provides model classes for optical components, surfaces and materials. It enables building optical systems by creating and placing various optical components in a 3d space and simulates light propagation ... 6 I've recently been introduced to GeoGebra, and while I haven't yet had the opportunity to use for any work, I love the interface. For geometrical diagrams it looks spectacular. I've also used XFig and gnuplot extensively. Particularly if you use$\LaTeX\$, these tools serve their purpose very very well.

6

Try Finite Element Magnetics (Link FEMM) Did I mention is free to download and use. Go figure !

6

This probably isn't exactly what you're looking for, but if you're looking for the time-independent bound states of a system, the Fourier grid Hamiltonian method may be applicable. Here is an application of it to the following strange-looking potential well: Here are a few low-energy bound states: And here are some of the high-energy ...

6

First we need to clear up a number of fundamental problems. Always use units. You give all these numbers, but no sense of whether they are meters or nanoseconds or newtons or furlongs. You should read up on significant figures. There is no point in writing out all those digits, since past the first one or two they are all uncertain. In science, writing out ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
subfloat: how to position label to the left?

How can I make \subfloat put the labels to the left of the images? It seems it only supports "top" and "bottom". I am searching for a solution without using \tabular. Thanks and regards, Jorge.

Example:

\documentclass{article}
\usepackage{subfig}
\usepackage{graphicx}
\begin{document}
\begin{figure}
\captionsetup[subfloat]{position=top}   % "position=left" is not supported!!! :(
\centering
\subfloat[]{\includegraphics[scale=0.5]{example-image-a}}
\vfill
\subfloat[]{\includegraphics[scale=0.5]{example-image-b}}
\end{figure}
\end{document}

Output (in red the location I'd like to achieve):

• What's the problem with tabular? By the way, \vfill will do nothing at all. – egreg Jul 29 '18 at 20:58
• Thanks for the observation! P.S. Nothing wrong about \tabular; just looking for an alternative solution :) – dontpanic Jul 29 '18 at 21:09

it is obtained by use of the environment \sidesubfloat from the package floatrow:

\documentclass{article}
\usepackage{floatrow}
\usepackage{graphicx}
\usepackage[label font=bf]{subfig}
\usepackage{caption}
\floatsetup[figure]{style=plain,subcapbesideposition=center}

\begin{document}
\begin{figure}
\centering
\sidesubfloat[]{\includegraphics[scale=0.5]{example-image-duck}}

\medskip
\sidesubfloat[]{\includegraphics[scale=0.5]{example-image-duck}}
\end{figure}
\end{document}

• Follow up: how can I tweak the space between the labels and the figures? I got lost trying to understand the (quite lengthy!) floatrow documentation :( – dontpanic Jul 29 '18 at 22:01
• @dontpanic, well, i also need to check documentation. i doubt that i will more successful than you. try to search on site. i will return to your question later. – Zarko Jul 29 '18 at 22:35
• OK, thanks. I've searched the forum and found some clues, but not a direct answer. I was trying (without luck) to use the following in the header: \newlength\mysep \setlength\mysep{1cm} \DeclareFloatSeparators{mysep}{\hskip\mysep}  \floatsetup[figure]{style=plain,subcapbesideposition=top,capbesidesep=mysep} – dontpanic Jul 29 '18 at 22:39


text:
## Saturday, 19 August 2017

### The Art of Becoming TrustedInstaller

If you’ve spent any time administering a Windows system post Vista you’ll have encountered the TrustedInstaller (TI) group which most system files and registry keys are ACL’ed to. If, for example you look at the security for a file in System32 you’ll notice both that only TI can delete and modify files (not even the Administrators group is allowed) and the Owner is also TI so you can’t directly change the security either.

However, if you look in the Local Users and Groups application you won’t find a TI user or group. This blog post is about what the TI group really is, and more importantly, with the aid of PowerShell and the NtObjectManager module, how you can be TI to do whatever you wanted to do.

## Where is TrustedInstaller?

If TI isn’t a user or group then what is it? Perhaps looking at the ACL more closely will give us some insight. You can use the Get-Acl cmdlet to read the security descriptor from a file and we can list the TI ACE.

We can see in the IdentityReference member that we’ve got the TI group, and it’s prefixed with the domain “NT SERVICE”. Therefore, this is a Windows Service SID. This is a feature added in Vista to allow each running service to have groups which they can use for access checks, without the overhead of adding individual real groups to the local system.

The SID itself is generated on the fly as the SHA1 hash of the uppercase version of the service name. For example the following code will calculate the actual SID:

$name = "TrustedInstaller" # Calculate service SID$bytes = [Text.Encoding]::Unicode.GetBytes($name.ToUpper())$sha1 = [System.Security.Cryptography.SHA1]::Create()
$hash =$sha1.ComputeHash($bytes)$rids = New-Object UInt32[] 5
[Buffer]::BlockCopy($hash, 0,$rids, 0, $hash.Length) [string]::Format("S-1-5-80-{0}-{1}-{2}-{3}-{4}", `$rids[0], $rids[1],$rids[2], $rids[3],$rids[4])

Of course you don’t need to do this, NTDLL has a RtlCreateServiceSid function, and LSASS will convert a service name to a SID and vice versa. Anyway, back to the point. What this means is that there’s a service called TrustedInstaller which must be running when system resources are modified. And that’s exactly what we find if we query with the SC utility.

If we start the TI service and look at the Access Token we’ll see that it has the TI group enabled.

Enough of the background, assuming we’re an administrator how can we harness the power of TrustedInstaller?

## Becoming TrustedInstaller

If you search on the Web for how to delete resources owned by TI you’ll tend to find articles that advocate manually taking ownership of the file or key, then change the DACL to add the administrators group. This is because even the usually compliant IFileOperation UAC COM object won’t do this automatically, as you’ll end up with the following dialog.

Changing the permissions on a system file isn’t exactly a great idea. If you do it wrong you could easily open up parts of your system to EoP issues, especially with directories. Explorer can make it easy to accidentally replace the security settings on all subfolders and files with little way of getting back the original values. Of course, the reason for TI is to stop you doing all this in the first place, but some people seem to really want it do it for some reason.

You might assume you could just add your current user to the TI group and that’s that? Unfortunately the LSASS APIs such as NetLocalGroupAddMembers takes a group name not a SID, and passing “NT SERVICE\TrustedInstaller” doesn’t work, as it’s not a real group, but created synthetically. There might be a magic incantation to do it, or at least a low-level RPC call, but I didn’t think it was worth the effort.

Therefore, the quick and dirty way would be to change the configuration of the TI service to run a different binary. Oddly, even though TI makes things on the system harder to mess with, it doesn’t protect its own service configuration from modification by a normal administrator. So you can issue a command such as the following to delete an arbitrary file as TI:

sc config TrustedInstaller binPath= "cmd.exe /C del path\to\file"

Start the TI service and *bang* the file is gone. Another reason this works is TI is not a Protected Process Light (PPL), which is odd because the TI group is given special permission to stop and delete PPL services. I pointed this out to MSRC (and Alex Ionescu did so in 2013, and clearly I didn’t bother to read it) but they didn’t do anything to fix it as no matter what they pretend PPL isn’t a security boundary, well until it a security boundary.

This still feels like a hack, you’d have to restore the TI service to its original state otherwise things like Windows Update will get unhappy really quickly. As the TI service has a token with the correct groups, what about just starting the service then “borrowing” the Token from it to create a new process or for impersonation?

As an admin we’ve got SeDebugPrivilege so can just open the TI process and open it’s token. Then we can do whatever we like with it. Simple really, let’s give that a try.

Well that was easy. Pat yourself on the back, grab a cold one it’s time for some Trusted Installering…

Well crap, seems we can’t create a new process or impersonate the token. That’s not much good. At the bottom of the screenshot we can see why, the token we’ve got only has TOKEN_QUERY access. We typically need at least TOKEN_DUPLICATE access to get the primary token for a new process or to create an impersonation token. Checking the security descriptor of the token using Process Hacker (we don’t even have READ_CONTROL to read it from PS) explains the reason why we’ve got such limited access.

We can see that the Administrators group only has TOKEN_QUERY access which at least matches up with the access we were granted on the token object. You might wonder why SeDebugPrivilege didn’t help here. The Debug privilege only bypass the security checks on Process and Thread objects, it doesn’t do anything on Tokens so we get no help. Are we stuck now, at least without the more destructive techniques such as changing the service binary?

Of course not. There are examples of how to get stuff running as TI such as this but they seem to rely on first getting code running at system by install a service (like psexec with the -s switch) and then stealing the the TI token and creating a new process. Needless to say, if I wanted to create a service I’d just modify the TrustedInstaller service to begin with :-)

So here’s two quick tricks to allow use to get around this permission limitation which doesn’t require any new or modified services or injecting shellcode. First, let’s deal with creating a new process. The parent of a new process is the caller of CreateProcess, however for UAC this would make all elevated processes children of the UAC service which would look somewhat odd. To support the principle of least surprise MS introduced in Vista the ability to specify an explicit parent process when creating a new process so that the elevated process could still be a child of the caller.

Normally in the UAC case you specify an explicit token to assign to the new process. However, if you don’t specify a token the new process will inherit from the assigned parent, the only requirement for this is the handle to the process we use as a parent must have the PROCESS_CREATE_PROCESS access right. As we’ve got SeDebugPrivilege we can get full access to the TI process including the right to create new child processes from it. As an added bonus the kernel process creation code will even assign the correct session ID for the caller so we can create interactive processes. We exploit this behavior to create an arbitrary process running as the TI service token on the current desktop using the New-Win32Process cmdlet and passing the process object in the -ParentProcess parameter.

2. Open the first thread in the process with THREAD_DIRECT_IMPERSONATION access. We’ll assume that the thread isn’t impersonating some lowly user.
3. Call NtImpersonateThread to steal an impersonation token.

Now as long as something else doesn’t set the main thread’s impersonation token (and you don’t do anything on a separate thread) then your PS console we act as if it has the TI group enabled. Handy :-)

## Wrap-Up

Hopefully this has given you some information about what TrustedInstaller and a few tricks to get hold of a token for that group using an admin account which would not normally be allowed. This applies equally to a number of different system services on modern Windows, which can be pain if you want to interact with their resources for testing purposes such as using my Sandbox Tools to work out what resources they can access.

Update (20170821)
Thought I should at least repeat that of course there's many ways of getting the TI token other than these 3 techniques. For example as Vincent Yiu pointed out on Twitter if you've got easy access to a system token, say using Metasploit's getsystem command you can impersonate system and then open the TI token, it's just IMO less easy :-). If you get a system token with SeTcbPrivilege you can also call LogonUserExExW or LsaLogonUser where you can specify an set of additional groups to apply to a service token. Finally if you get a system token with SeCreateTokenPrivilege (say from LSASS.exe if it's not running PPL) you can craft an arbitrary token using the NtCreateToken system call.

## Thursday, 3 August 2017

### DG on Windows 10 S: Abusing InstallUtil

This is the final blog post I’m going to do on Windows 10 S. The previous parts are here, here and here. Originally, I was going to describe a way of completely removing the SI policy on Win10S without upgrading to Pro so that you can install any applications you like *ahem* while keeping secure boot etc. intact.

However, I decided that enforcing the SI policy was more about licensing than it was about security so I’ve thought better of it. If you really want to run arbitrary applications on your own computer:

1. Don’t buy a Windows 10 S machine in the first place.
2. Or, failing that, upgrade to Pro, at least for the Surface Laptop that’s still currently free.
3. Or, failing that, work out how I removed the policy, it’s not that hard ;-)

Instead of disabling the entire policy, I’ll detail another DG bypass. In this case, it’s exploiting the same root cause as the previous one I disclosed, .NET loading untrusted code from a byte array through serialization, but with an interesting twist (*spoiler* it’s not using BinaryFormatter, well mostly). Therefore, I don’t think it makes that much difference to disclose. MS, or at least the .NET team (hi Barry), are unlikely to fix the fundamental incompatibility between DG and .NET any time soon.

## Is That You, NetDataContractSerializer?

It turns out that BinaryFormatter and .NET remoting was just too dangerous to let live and MS finally removed it from .NET. Just kidding, MS did no such thing. While MS might try and put scary, if somewhat small, warnings when you try and search for documentation on .NET remoting and BinaryFormatter, both technologies are still there in the .NET framework and no warnings are produced when using them. In fact BinaryFormatter is so awesome, it’s coming back in .NET Core 2.0 which is a bit of a shame IMHO.

What did happen in version 3.0 of the .NET Framework was the introduction of Windows Communication Foundation (WCF), a new object communication stack for accessing remote services. Learning well from the past, MS chose to use XML Web Services (well perhaps didn’t learn that well from the past) and instead of BinaryFormatter, they implemented a new serialization mechanism, Data Contracts. The canonical implementation of the WCF Data Contracts is the DataContractSerializer (DCS) class. In order to use the DCS class for serialization you are supposed to annotate your classes and properties with the DataContractAttribute and DataMemberAttribute. Explicitly annotated, Data Contracts are not that interesting, however, clearly someone decided that it’d be great if there was a way of serializing existing serializable classes. Therefore, DCS also supports serializing arbitrary classes as long as they have the SerializableAttribute annotation, for example if you have the following C# class:

namespace DCSerializer {
[Serializable]
public class Contract {
public int Value;
}
}

And run it through the DCS WriteObject method you’ll get the following XML content:

<Contract
xmlns="http://schemas.datacontract.org/2004/07/DCSerializer"
xmlns:i="http://www.w3.org/2001/XMLSchema-instance">
<Value>1234</Value>
</Contract>

In theory, there’s enough information to deserialize this XML file without any special knowledge, the namespace (DCSerializer) and the class name (Contract) and reflected in the default XML namespace and root element name respectively. However, what’s missing here is a reference to what assembly the Contract type exists in. This ambiguity is resolved by requiring that all known types (outside of some specific system types) must be specified during construction or through a resolver. This isn’t a problem in a simple, well defined web service. But it does make DCS less useful as a general, exploitable serializer.

While DCS is awesome in its own way, the requirement for specifying all types is a weakness, from a lazy developer point of view. It would be nice if you could get some of the flexibility of the more general serializers such as BinaryFormatter. This is where the similar but different NetDataContractSerializer (NDCS) class comes into the picture. Both DCS and NDCS (and the related DataContractJsonSerializer) derive from the XmlObjectSerializer class. This allows NDCS to be used for WCF services instead of DCS if you so desire. Serializing the previous class through NDCS generates the following:

<Contract
z:Id="1"
z:Type="DCSerializer.Contract"
z:Assembly="DCSerializer, Version=1.0.0.0"
xmlns="http://schemas.datacontract.org/2004/07/DCSerializer"
xmlns:i="http://www.w3.org/2001/XMLSchema-instance"
xmlns:z="http://schemas.microsoft.com/2003/10/Serialization/">
<Value>1234</Value>
</Contract>

The output from NDCS includes assembly information. Therefore NDCS works in a similar way to BinaryFormatter in that it doesn’t need any prior knowledge of the types being deserialized. This makes NDCS the equivalent of BinaryFormatter but in XML format, though to be fair .NET already had something similar with the SoapFormatter. This is a long winded way of saying, if you can find an application which will load an untrusted NDCS XML file, you can exploit it with the exact same set of serialization gadgets as you can with BinaryFormatter from my previous post. The question therefore is, does such an application exist? Let’s see just one example.

## The Ways of InstallUtil

InstallUtil is a .NET utility which is pre-installed with the .NET Framework. The utility has been available since at least v1.1 (I don’t have anything with v1.0 to check). Its purpose is to allow you to run installation code from an assembly so that you can configure system state and install your code. To use it normally, you first define a class which derives from the Installer class, annotate your class with the RunInstallerAttribute and then implement one of the main callback methods such as Install.

For example, the following class is sufficient to be executed by InstallUtil:

[RunInstaller(true)]
public class TestInstaller : Installer {
public override void Install(IDictionary stateSaver) {
Console.WriteLine("Hello from the Installer");
base.Install(stateSaver);
}
}

If you compile the class into an assembly, you can then run the installer using the following command line and it will execute the Install method in your assembly:

InstallUtil path\to\installer.dll

The interesting thing about InstallUtil is it’s a known Application Whitelisting bypass (specifically against something like AppLocker). The executable is Microsoft signed, located in a system directory and will execute code from an arbitrary assembly file passed on the command line. However, what it isn’t is a DG bypass. InstallUtil loads the assembly from a file, the file needs to be allowed to load in the SI policy, which means for Win10S we can only load existing assemblies signed by Microsoft. We might be able to find an assembly with an installer we could abuse, but I didn’t look very hard. Still, that doesn’t mean we can’t abuse InstallUtil in other ways.

If you run the simpler installer through InstallUtil, you might notice a file which gets created next to the installer assembly file which has an InstallState extension. This file begs for closer inspection. Opening it in a text editor you’ll encounter content which looks awfully familiar:

<ArrayOfKeyValueOfanyTypeanyType
xmlns:i="http://www.w3.org/2001/XMLSchema-instance"
xmlns:x="http://www.w3.org/2001/XMLSchema"
z:Id="1"
z:Type="System.Collections.Hashtable"
z:Assembly="0"
xmlns:z="http://schemas.microsoft.com/2003/10/Serialization/"
xmlns="http://schemas.microsoft.com/2003/10/Serialization/Arrays">
...

This looks a lot like the output from a NDCS serialization. To confirm we can just go looking at the code in a decompiler, the assembly doesn’t seem to be available in the reference source. InstallUtil is actually just a thin wrapper around the ManagedInstallerClass class which is implemented in the System.Configuration.Installer assembly. Poking around a bit, we find that AssemblyInstaller is using NDCS in a number of places. We’re not too interested in places where the NDCS is used to write out objects, rather, we’re more interested in places where it’s reading. For example in the Uninstall method, there’s the following code:

public override void Uninstall(IDictionary savedState) {
string installStatePath = GetInstallStatePath(Path);
if (File.Exists(installStatePath)) {
FileStream fileStream = new FileStream(installStatePath);
var ser = new NetDataContractSerializer();

// Run uninstaller...
base.Uninstall(savedState);
}
}

From this snippet of code, we can see that the untrusted install state file it loaded verbatim with a insecure NDCS class instance. If we can can convince InstallUtil to load a crafted install state file which contains a deserialization chain to load an assembly from a byte array, we can bypass DG. While we can’t load untrusted assemblies, the utility doesn’t need a specific assembly so we can just instruct it to uninstall a system assembly such as mscorlib. Don’t worry, it won’t actually do anything as mscorlib doesn’t contain any installers. Also, looking at the documentation there’s a InstallStateDir parameter we can pass to specify where the utility will look for our install state. If we copy the serialized file to c:\dummy\mscorlib.InstallState then we can get the DG bypass by running the following command:

InstallUtil /u /InstallStateDir=c:\dummy /AssemblyName mscorlib

I’ve updated my DG bypass Github repository to include this bypass as well. Run the CreateInstallState utility passing the path to the assembly to load (again it will instantiate the first public type it finds) and the output filename such as mscorlib.InstallState. Execute the previous InstallUtil command and you should get your assembly executed. Note that InstallUtil will try and delete the InstallState file after use, if you don’t want that to happen you can just set the Read-Only flag on the file and the delete will fail.

The main advantage to this DG bypass over the previous one I disclosed in AddInProcess is that it’s easy to use for persistence. Just add a scheduled task which runs InstallUtil or a LNK file in the startup folder with the appropriate command line and the code DG bypass will run when you login.
As a final note, you might wonder how InstallUtil serialized the install state prior to v4 of the Framework, specifically as NDCS was only introduced in v3.0? Dropping the v2 System.Configuration.Installer assembly into the decompiler we find it uses, *drum roll* SoapFormatter. So it’s just as vulnerable to this attack in v2, assuming you’ve got v2 compatible gadgets (most v2 installs are really v3.5 so that’s typically a yes as the gadgets I presented in the previous post were introduced in v3.0).

While this bypass exists currently in Win10S and likely in many custom DG policies, it’s easy to just ban InstallUtil as you would with AddInProcess and this would eliminate the bypass. Again I’ll give you a link to Matt Graeber’s blog post about adding new executables to your DG policy.

## Final Wrap Up

This is the end of my planned series on Win10S. Hopefully, I’ve demonstrated that regardless of the PR coming out of Microsoft that it’s not 100% secure, at least against anyone who knows you run Win10S and is willing to customize an attack to you or your organization. There will always be bypasses for DG, and the way Windows works, it’s almost impossible to completely lock it down. If it wasn’t .NET, it’d be a memory corruption vulnerability from an overlong command line parameter or something equally silly.

Does Win10S have no value what so ever? Of course not, DG is a good, if not perfect, way of limiting a system to a very a specific set of signed executables. I’d be less sceptical about Win10S if it hadn’t become so transparently a marketing ploy rather than a goal to really push the Windows platform forward. Unfortunately, I can’t see the goal of a secure Windows platform ever being reached without completely jettisoning all the reasons that Windows works for people at the moment.

I’d like to thank Matt Graeber for his knowledge of Device Guard and for doing reviews of these posts to make sure I’m not talking complete rubbish. Also shout outs to everyone looking for these sorts of issues such as Matt Nelson, Casey Smith, Alvaro Muñoz and no doubt others I’m forgetting.


text:
# Distillation

Historically, distillation has been used since 1200 BC in perfumery operations. Early forms of distillation were batch processes using one vaporization and one condensation. Purity was improved by further distillation of the condensate. Greater volumes were processed by simply repeating the distillation. Chemists were reported to carry out as many as 500 to 600 distillations in order to obtain a pure compound. In the early 19th century, the basics of modern techniques including pre-heating and reflux, were developed. In 1877 U.S. Patent was granted for a tray column for distillation of ammonia and in the subsequent years for oil and spirits. With the emergence of chemical engineering as a discipline at the end of the 19th century, scientific rather than empirical methods were applied. More accurate designs were used during the development of the petroleum industries. Today availability of powerful computers has allowed direct computer simulation of distillation columns.

## What is Distillation?

Distillation is a process by which a liquid mixture is separated into fractions with higher concentrations of certain components by exploiting differences in relative volatility. Distillation has been used widely to separate volatile components from non-volatile compounds. In industrial settings such as oil refineries and natural gas processing plants, this separation process is undertaken using a distillation column.

Distillation is one of the most important processes for separating the components of a solution. The solution is heated to form a vapor of the more volatile components in the system, and the vapor is then cooled, condensed, and collected as drops of liquid, Shown in the Figure above. By repeating vaporization and condensation, individual components in the solution can be recovered in a pure state. Essences and many pure products from the oil refinery industry are processed via distillation.

## Objective of Distillation

The basic objective of distillation is to separate the liquid mixture into two or more components. In a basic distillation column, a feed stream enters in the middle of the column and two streams leave, one at the top and one at the bottom. Components with lower boiling points are concentrated in the stream leaving the top while components with higher boiling points are concentrated in the stream leaving the bottom. Separation is achieved by controlling the column temperature and pressure to take advantage of differences in the relative volatility of the mixture components and therefore tendency to change phase. The lighter, lower boiling point components evaporate and travel up the column to form the top product, and the heavier, higher boiling point components condense and travelling down the column to form the bottom product.

## Basic principles of distillation

The mechanism involved in distillation is the differences in volatility between individual components. With sufficient heat applied, vapors are formed from the liquid solution. The liquid product is subsequently condensed from the vapor phase by the removal of the heat. Therefore, heat is used as the separating agent during distillation. In general, distillation can be carried out either with or without reflux involved. For the case of single-stage differential distillation, the liquid mixture is heated to form a vapor that is in equilibrium with the residual liquid. The vapor is then condensed and removed from the system without any liquid allowed to return to the still pot. This vapor is richer in the more volatile component than the liquid removed as the bottom product at the end of the process. However, when products of much higher purity are desired, part of the condensate has to be brought into contact with the vapor on its way to the condenser and recycled to the still pot. This procedure can be repeated many times to increase the degree of separation in the original mixture. Such a process is normally called “rectification.”

Fractionation: It is another term for distillation also called fractional distillation.
Feed: The liquid and/or gas feed into the distillation column.
Feed tray: The tray below the inlet nozzle is called the feed tray.

Heavy Component: The component with the lower relative volatility, for example, simple hydrocarbon, is a component with a higher molecular weight. It is found in higher concentrations in the bottom product of the column.
Light Component: The component with the higher relative volatility, for example, simple hydrocarbon, is a component with a lower molecular weight. It is found in higher concentrations at the top of the column.
Stripping section: It is a section that consists of trays between the bottom of the column and the feed tray. In the stripping section, the aim is to concentrate the heavier component in the liquid phase.
Rectifying section: It is a section that consists of trays between the feed tray and the top of the column. In the rectifying section, the aim is to concentrate the lighter component in the vapor phase.
Top Product: It is a product which leaves from the top of the column, also called the distillate. This product is usually passed through a heat exchanger and liquefied.
Bottom Product: It is the product that leaves through the bottom of the distillation column.
Reflux: A portion of vapor from the top of the column has been condensed to a liquid and returned to the column as a liquid above the top tray.
Reboiler: A heat exchanger at the bottom of the column which boils some of the liquid leaving the column. The vapor generated returns to the column at the bottom of the stripping section.
Vapor-liquid equilibrium (VLE) Curve: A plot of the actual composition of the lighter component in the vapor phase for a given composition in the liquid phase. Usually, it is derived from thermodynamic data.
Zeotropic mixture : It is a mixture of liquids with different boiling points. For example, nitrogen, methane, ethane, propane etc.
Azeotropic mixture: It is a mixture of two or more liquids that has a constant boiling point because vapor has the same composition as a liquid mixture.

### Principle of Separation

Distillation takes advantage of the difference in relative volatility of the feed mixture components. Generally for two or more compounds at a given pressure and temperature, there will be a difference in the vapor and liquid compositions at equilibrium due to component partial pressure. Distillation exploits this by bringing liquid and gas phases into contact at temperatures and pressures that promote the desired separation. During this contact the components with the lower volatility (typically lower boiling point) preferentially moves into the liquid phase while more volatile components move into the vapor phase.

A distillation column may use either trays or a packed bed to bring the gas and liquid into contact. For a column using trays, we can consider the changes to gas and liquid phase compositions as they both enter and exit a single tray. The liquid entering the tray will contact the gas exiting the tray, Shown in the Figure below. The hotter vapor phase heats the incoming liquid phase as it bubbles through the tray, evaporating the light components which then leaves the tray with the vapor phase. Conversely, the cooling of the vapor phase by the liquid phase will causes the heavier components of the vapor phase to condense and exit the tray with the liquid phase.

For the liquid across the tray:

CL1,heavy < CL2,heavy

CL1, light > CL2,light

TL1 > TL2

For the vapor through the tray:

CV1,heavy > CV2,heavy

CV1, light < CV2,light

TV1 > TV2

Where C is concentration and T is temperature.

When packing is used rather than trays the principle remains the same, in fact, packing is often referenced in terms of the height equivalent to a theoretical plate (HETP) i.e. what height of packing is equivalent to one theoretical plate. The packing is just an alternative method to bring the liquid and vapor phases into contact with the liquid generally flowing over the surfaces of the packing material, while the vapor passes up through the space between packing elements.

### Typical Operating Parameters

The distillation process can be improved by understanding the following operating parameters.

#### Temperature

The basic temperature profile of a distillation column is hotter at the bottom and cooler at the top. For a simple two-component distillation the temperature at the bottom is just lower than the boiling point of the heavier component. The temperature at the top of the column is just above the boiling point of the lighter component. In order to have a heavy component remain as a liquid at the bottom of the column and the lighter component stay as a gas, we set the temperature at the bottom to match this requirement. This temperature is set by adding heat via a heat exchanger. Typically the heat added to the bottom of the column is easy to control, via steam or hot oil flow rates.

At the top of the column, the situation is reverse. The light component remains as gas while the heavier component is condensed to a liquid and falls back down the column. The top temperature is set just above the boiling point of the lighter component. The temperature control situation is different at the bottom of the column because the top product is to be a liquid when we send it for storage. All of the gas coming out of the top of the column is condensed to a liquid. This liquid stream is split with some returning to the column and some going to storage. The top temperature is often controlled by changing the reflux rate, i.e. the flow rate of liquid sent back to the top of the column. A higher reflux rate means cooler liquid falling down the column against the rising warmer gas, and the top temperature is lower. Overall heat is added at the bottom of the column and heat is extracted at the top of the column. Inside the column, the temperature balance is created between the hot gas rising up the column and the cooler liquid falling down the column.

#### Pressure

There is typically a pressure gradient across the column with the pressure being higher at the bottom of the column than the top. This pressure gradient occurs as the liquid coming down the column hampers the flow of vapor up the column and imposes a pressure loss on the flow. In steady-state distillation, the pressure in the column is held constant, and the temperature is varied to control the composition of the product streams.

#### Applications

(i) Distillation is used for many commercial processes, such as the production of gasoline, distilled water, xylene, alcohol, paraffin, kerosene, and many other liquids.

(ii) Distillation is used for purifying solvents and liquid reaction products.

(iii) It is used in the manufacturing of distilled water, double distilled water used in Water for Injection, and other pharmaceutical preparations.

(iv) Toxic and costly organic solvents are used in the extraction, synthesis, and analysis of drugs. This solvent can be recovered by distillation for economic as well as environmental protection benefits.

(v) Distillation is used in the separation of volatile oils such as clove oil, anise oil, cardamom oil, eucalyptus oil, etc. from the plant extracts.

(vi) It can be used in the separation of volatile components from a mixture of two or more volatile liquids.

(vii) It can be used as a quality control method for alcohol content in liquid formulations. The alcohol is separated from formulations by distillation and alcohol content is determined.

(viii) It can be used to liquefy and separate gases from the air. For example, nitrogen, oxygen, and argon are distilled from the air.

(ix) Distillation is used in crude fermentation broths to separate alcoholic spirits.

(x) It can also be used in the fractionation of crude oil into gasoline and heating oil.

Make sure check our amazing post on: Steam Jacketed Kettle


text:
# Start a new discussion

## Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

## Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorAli Caglayan
• CommentTimeOct 30th 2018
• (edited Oct 30th 2018)

Subsections seem to break a few things about the original page by including extra things.

I am starting this thread to document what really should be ignored:

Firstly I don’t think redirects of the subsection should be included in the text, also the category: example tag should be ommitted which shouldn’t be to difficult to do.

If everybody is happy we can add this to the technical todo list

• CommentRowNumber2.
• CommentAuthorMike Shulman
• CommentTimeOct 31st 2018

By “subsections” I gather you mean !includes?

• CommentRowNumber3.
• CommentAuthorAli Caglayan
• CommentTimeOct 31st 2018

Yes, as you pointed out before the includes brought in the category tag which ideally shouldn’t be the case.


text:
# Coulomb’s law

Coulomb’s Law which is also called inverse square law is the experimental law of physics, which quantify the electrical force between the two static electrical charges, which are separated by some distance r.

The force between the two static electrical charges is called electrostatic force or coulomb’s force. This law was first published in 1785 by the French physicist Charles Augustin de coulomb. Coulomb’s Law is the first step in the development of the theory of electromagnetism. Watch the practical video of coulomb’s Law.

In this section, we will discuss the coulomb’s Law in detail so tune with us till the end.

## Coulomb’s law statement

Coulomb performed various experiments to find the force between the two stationary electrical charges. After a successful experiment, Charles Augustin de coulomb established the following law known as coulomb’s Law.

Coulomb’s law statement: The magnitude of the electrostatic force between the two stationary electrical point charges which is separated by the distance $r$ is directly proportional to the product of their charges and inversely proportional to the square of the distance between them.

Mathematically it is given as – \begin{aligned}F& \propto q_1q_2\\ F& \propto \frac{1}{r^2}\\ F &\propto \frac{q_1q_2}{r^2}\\ \text{And, therefore} \quad F &= \frac{Kq_1q_2}{r^2}\end{aligned}

## Key features of coulomb’s law

• This law is applicable only for points charges.
• K is called the proportionality constant and in a vacuum, it is expressed as $\frac{1}{4\pi\epsilon_0}$. Where $\epsilon_0$ is called the permittivity of the free space. And its numerical value is $8.85\times10^{-12} C^2N^{-1}m^{-2}$.  Any medium other than vacuum is expressed as $\frac{1}{4\pi\epsilon}$, where $\epsilon$ is called the absolute permittivity of the medium.
• The ratio of $\frac{\epsilon}{\epsilon_0}$ is $\epsilon r$ called the relative permittivity of the medium or dielectric constant of the medium and also denoted as $K$. It is a dimensionless quantity. $$\frac{\epsilon}{\epsilon_0} = \epsilon r = K$$
• The value of relative permittivity $\epsilon r$ varies from 1 to $\infty$, for vacuum, it is 1 and for air, it is nearly equal to 1 and we take 1 for simplicity in calculations, and for metals, it is $\infty$.
• If any charge is placed in the medium having relative permittivity $\epsilon r$ then the electrostatic force between them is $\frac{1}{4\pi\epsilon_0}\cdot\frac{q_1q_2}{r^2}$
• The value of $\frac{1}{4\pi\epsilon_0}$ is $9\times10^{9}Nm^2C^{-2}$.
• The force between the two-point charges always acts along the line joining these two points charges. This force is equal in magnitude but opposite in directions, irrespective of the medium in which they are placed.
• The electrostatic force is conservative in nature i.e the work done by the electrostatic force to move a charge in a close loop of any shape is zero.
• This electrostatic force is a central force, in the absence of other external forces, the angular momentum of one particle with respect to the other particle ( in two particles system) is conserved.
• Coulomb’s Law is analogous to the gravitational Law because both are inverse-square laws. \begin{aligned}F(g) &= \frac{Gm_1m_2}{r^2}\\ F(e)& = \frac{Kq_1q_2}{r^2}\end{aligned} Where $G = 6.67\times10^{-11}Nm^2kg^{-2} \text{and}\; K = \frac{1}{4\pi\epsilon_0}\; \text{is}\; 9\times10^9Nm^2C^{-2}$ After comparing both forces we get $F(e) = 10^{39}F(g)$This electrostatic force can be attractive or repulsive on the basis of the nature of the charge.
• If both charges are positive/negative then force is repulsive if they are unlike then the force is attractive.

Read Also

## Coulomb’s law in vector form

Let’s take two points charges $q_1$ and $q_2$ which are placed at point $A$ and point $B$ as shown in the following figure.

According to coulomb’s Law, the magnitude of the force on $q_1$ due to $q_2$ and the magnitude of the force on $q_2$ due to $q_1$ is given by –

$$|F_{12}| = |F_{21}| = \frac{q_1q_2}{4\pi\epsilon_0\cdot r^2}$$

Now if $r_{12}$ is a unit vector pointing from $q_1$ to $q_2$  and $r_{21}$ is the unit vector pointing from $q_2$ to $q_1$ then the force is –

$$F_{12} = \left(\frac{q_1q_2}{4\pi\epsilon_0\cdot r^2}\right)\;r_{21}$$

$F_{12}$, is the force applied from $q_2$ to $q_1$ along with unit vector $r_{21}$.

$$F_{21} = \left(\frac{q_1q_2}{4\pi\epsilon_0\cdot r^2}\right)\;r_{12}$$

$F_{12}$ , is the force applied from $q_1$ to $q_2$ along unit vector $r_{12}$.

From this, we can conclude that the unit vector $r_{21}$ is opposite to the unit vector $r_{12}$.

$$r_{21} = – r_{12}$$

Then, the second equation becomes –

$$F_{12} = -\left(\frac{q_1q_2}{4\pi\epsilon_0\cdot r^2}\;r_{12}\right)$$

$\left(\frac{q_1q_2}{4\pi\epsilon_0\cdot r^2}\;r_{12}\right)$, this force is equal to $F_{21}$, now the equation becomes – $$F_{12} = – F_{21}$$

This force is equal in magnitude but opposite in directions and this is the same as Newton’s third law.

Watch this video for more reference.

Stay tuned with Laws Of Nature for more useful and interesting content.

What is Force, Moment of Force?
What is Force, Moment of Force?

### Newsletter Updates

Enter your email address below to subscribe to our newsletter


text:
1. ## [SOLVED] Integral

How would you solve $\int \ln (\sqrt{x^2+x+1}) dx$?
I don't see any good substitution nor a good integration by part. I'm not asking the whole solution, just the way you'd solve it.
Thanks.

2. Note that $\log((x^2+x+1)^{1/2}) = \frac{1}{2}\log\Big(\frac{x^3-1}{x-1}\Big)$

$=\frac{1}{2}\Big(\log(x^3-1)-\log(x-1)\Big)$

3. $\frac{1}{2}\int1.\ln(x^2+x+1)dx=\frac{x}{2}\ln(x^2 +x+1)+$...............


text:
batch_dot is used to compute dot product of x and y when x and y are data in batch, i.e. in a shape of (batch_size). batch_dot results in a tensor or variable with less dimensions than the input. If the number of dimensions is reduced to 1, we use expand_dims to make sure that ndim is at least 2.

k_batch_dot(x, y, axes)

## Arguments

x Keras tensor or variable with 2 more more axes. Keras tensor or variable with 2 or more axes List of (or single) integer with target dimensions (axis indexes are 1-based). The lengths of axes[[1]] and axes[[2]] should be the same.

## Value

A tensor with shape equal to the concatenation of x's shape (less the dimension that was summed over) and y's shape (less the batch dimension and the dimension that was summed over). If the final rank is 1, we reshape it to (batch_size, 1).

## Keras Backend

This function is part of a set of Keras backend functions that enable lower level access to the core operations of the backend tensor engine (e.g. TensorFlow, CNTK, Theano, etc.).

You can see a list of all available backend functions here: https://keras.rstudio.com/articles/backend.html#backend-functions.


text:
How To Decide Which Software To Use For Building Automated Ngs Analysis Pipeline
6
27
Entering edit mode
11.5 years ago
Mcmahanl ▴ 300

There are so many software available for building automated NGS analysis pipeline, how one decide on which one to use. For examples, listing below are some of the software I have come across:

And any other software that I should look into?

next-gen sequencing pipeline sequencing • 10k views
0
Entering edit mode

Sometimes the solution is to be be aware of only one these ;-) . Now in all seriousness thanks for listing all these examples, this will be a great resource.

0
Entering edit mode
10
Entering edit mode
11.5 years ago
Farhat ★ 2.9k

I have experience with shell script based pipelines and Galaxy. While Galaxy provides a great front end for making pipelines, I have found it slower for running the tasks. One serious drawback with Galaxy is that it stores results at every intermediate step in all their full uncompressed glory. This, I am sure, partly accounts for the slowdown as the disk writing activity is heavy. Also, it leads to filling up of drives which can be an issue in itself especially if you are doing a lot of analyses.

Shell scripts can be really flexible and powerful but they are not as user-friendly although I am sure any kind of scripting language could deliver similar results.

6
Entering edit mode
11.5 years ago
Ryan Dale 5.0k

I write many of my NGS pipelines using Ruffus. It's really easy to run tasks in parallel. Simple pipelines are correspondingly simple to write, but at the same time it's rich enough to support very complex pipelines, too (e.g., http://www.ruffus.org.uk/gallery.html).

6
Entering edit mode
11.5 years ago
lh3 33k

From what I have heard, for NGS Galaxy is the most widely used generic pipeline. Nonetheless, I guess more people are building their own pipelines from scratch. IMHO, the difficulty of using generic pipeline comes from the difference between parallelization environments. It is pretty easy if everything runs on the same node, but LSF/SQE/PBS and the different configurations (e.g. memory and runtime limitation) make things messy.

If you are the only users of your cluster and have full control, using a generic pipeline may be not hard. A friend of mine builds a private cloud and uses Galaxy. Everything runs smoothly. If you are using nodes part of a huge cluster, probably writing your own pipeline is easier. When you can control your pipeline, you can also avoid inefficient parts easily as is mentioned by Farhat. You know, implementing an initial pipeline is not that difficult. It will take time to purify it, but the same is true if you use generic pipeline frameworks.

5
Entering edit mode
11.5 years ago
Ketil 4.1k

I don't know what you mean by "NGS analysis", but coming from a comp.sci. background, I tend to use 'make' to construct non-trivial pipelines. For our current de novo project, the current pipeline consists of primary assembly (newbler, celera and CLC), secondary assembly (SSPACE), remapping of reads (bwa index, aln, and sampe), quality evaluation (samtools idxstats and flagstas), generating graphs (gnuplot) and so on.

Since many of these steps are time consuming, and since something always fails at some point, make's ability to skip already completed files saves a lot of time, especially with some careful sprinkling of .PRECIOUS. Also, make's -j option means that my pipeline is trivially parallelized.

The downside is that it can be a bit hard to debug, but -r --warn-undefined-variables helps a bit. I'm still missing some way of separating output from subprocesses, especially when running -j 16 :-)

2
Entering edit mode

i've always wondered how people use MAKE this way. do you have validator scripts that can distinguish when an output file is not just garbarge?

1
Entering edit mode

Most of my output files are garbage. Maybe I should switch to Haskell.

0
Entering edit mode

Why would an output file be garbage? If anything, make helps against this, since it deletes temporary files when something goes wrong.

But yes, validating results is always a good idea.

0
Entering edit mode

:-) Yes! Unfortunately, the old rule of garbage in - garbage out is universal, and independent of implementation language...

2
Entering edit mode
11.5 years ago
Ben Lange ▴ 190

I have extensive experience with a large custom developed pipeline. Using a database to coordinate tasks on a private pool of commodity PCs. This approach is very flexible but exposes lots of coordination complexities with more complex workflows.

It's pretty clear that the more forking and joining you have in your workflow, the higher the complexity regardless of your approach.

Focus on what costs the most. When you're dealing with large amounts of data, storage is cheap but accessing and moving it is not. So the more localized the data is to the compute nodes the faster the throughput.

1
Entering edit mode
10.3 years ago

We have been building some genotyping pipelines in Pegasus, which is a very heavyweight platform for scientific pipelines, and is apparently NSF-funded through the 2016 Olympics in Rio. Plan accordingly.

Pegasus is very friendly with Condor, although it can be run on other batch systems with some headaches.

The nodes look like this (i've stripped away the angle brackets to conform to BioStar)

job id="ADDRG_01" namespace="align" name="java" version="4.0"
argument
-Xmx16g
-jar ${picardfolder}/AddOrReplaceReadGroups.jar INPUT=${filename}.bam
OUTPUT=${filename}.sorted.bam SORT_ORDER=coordinate RGPU= RGID=1 RGLB=bar RGPL=${platform}
RGSM=${outputprefix} CREATE_INDEX=True VALIDATION_STRINGENCY=LENIENT TMP_DIR =${picardtemp}
/argument
stdout name="${filename}.picardrg.out" link="output"/ stderr name="${filename}.picardrg.err" link="output"/
/job

0
Entering edit mode

sorry about that ;-) we need to fix XML display pronto - I'll make this a priority

1
Entering edit mode

also the main reason this has not been done so far is that I don't think I understand all the implications of properly escaping HTML, nor the conditions in which it should or shoulnd't happen, plus the escaping needs to interact with the prettyfier, also not obious how to do it, - thus I am afraid that I will open a javascript injection security hole with it

0
Entering edit mode

ok thanks - whatever helps people post more code is always good


text:
# Elementary factorization

Let $$d, e, f$$ be positive integers such that $$d(10e + f)(10f + e) = 2015$$.

Evaluate $$d \times e \times f$$.

×


text:
Skip to Main content Skip to Navigation

# A relaxed alternating CQ-algorithm for convex feasibility

Abstract : Let H1,H2,H3 be real Hilbert spaces, let C⊂H1, Q⊂H2 be two nonempty closed convex level sets, let A:H1→H3, B:H2→H3 be two bounded linear operators. Our interest is in solving the following new convex feasibility problem Find x∈C,y∈Q such that Ax=By, which allows asymmetric and partial relations between the variables x and y. In this paper, we present and study the convergence of a relaxed alternating CQ-algorithm (RACQA) and show that the sequences generated by such an algorithm weakly converge to a solution of (1.1). The interest of RACQA is that we just need projections onto half-spaces, thus making the relaxed CQ-algorithm implementable. Note that, by taking B=I, in (1.1), we recover the split convex feasibility problem originally introduced in Censor and Elfving (1994) [13] and used later in intensity-modulated radiation therapy (Censor et al. (2006) [11]). We also recover the relaxed CQ-algorithm introduced by Yang (2004) [8] by particularizing both B and a given parameter.
Keywords :
Document type :
Journal articles
Complete list of metadata

https://hal.univ-antilles.fr/hal-00776638
Contributor : User Unknown Connect in order to contact the contributor
Submitted on : Tuesday, January 15, 2013 - 8:10:16 PM
Last modification on : Monday, May 23, 2022 - 2:06:49 PM

### Citation

Abdellatif Moudafi. A relaxed alternating CQ-algorithm for convex feasibility. Nonlinear Analysis: Theory, Methods and Applications, Elsevier, 2013, 79, pp.117-121. ⟨10.1016/j.na.2012.11.013⟩. ⟨hal-00776638⟩

Record views


text:
# mx.symbol.InstanceNorm¶

## Description¶

Applies instance normalization to the n-dimensional input array.

This operator takes an n-dimensional input array where (n>2) and normalizes the input using the following formula:

$out = \frac{x - mean[data]}{ \sqrt{Var[data]} + \epsilon} * gamma + beta$

This layer is similar to batch normalization layer (BatchNorm) with two differences: first, the normalization is carried out per example (instance), not over a batch. Second, the same normalization is applied both at test and train time. This operation is also known as contrast normalization.

If the input data is of shape [batch, channel, spacial_dim1, spacial_dim2, …], gamma and beta parameters must be vectors of shape [channel].

This implementation is based on this paper 1

1

Instance Normalization: The Missing Ingredient for Fast Stylization, D. Ulyanov, A. Vedaldi, V. Lempitsky, 2016 (arXiv:1607.08022v2).

Example:

// Input of shape (2,1,2)
x = [[[ 1.1,  2.2]],
[[ 3.3,  4.4]]]

// gamma parameter of length 1
gamma = [1.5]

// beta parameter of length 1
beta = [0.5]

// Instance normalization is calculated with the above formula
InstanceNorm(x,gamma,beta) = [[[-0.997527  ,  1.99752665]],
[[-0.99752653,  1.99752724]]]

## Usage¶

mx.symbol.InstanceNorm(...)

## Arguments¶

Argument

Description

data

NDArray-or-Symbol.

An n-dimensional input array (n > 2) of the form [batch, channel, spatial_dim1, spatial_dim2, …].

gamma

NDArray-or-Symbol.

A vector of length ‘channel’, which multiplies the normalized input.

beta

NDArray-or-Symbol.

A vector of length ‘channel’, which is added to the product of the normalized input and the weight.

eps

float, optional, default=0.00100000005.

An epsilon parameter to prevent division by 0.

name

string, optional.

Name of the resulting symbol.

## Value¶

out The result mx.symbol


text:
# Quarterly Journal of the Royal Meteorological Society Template

Author
Denis Sergeev
AbstractThis paper describes the use of the LaTeX qjrms4.cls class file for setting papers for the Quarterly Journal of the Royal Meteorological Society


text:
# Math Help - use the well-ordering property to prove the Principle of Strong induction

1. ## use the well-ordering property to prove the Principle of Strong induction

use the well-ordering property to prove the Principle of Strong induction

I don't know how to start...

I know the well-ordering property is If S is a nonempy set of N, then there exists an element m ∈ S such that m≤k for all k∈S

and the Principle of Strong induction is:
Let P be property of N, assume:
1) P(1) holds
2) if P(1),...,P(n-1) hold, then P(n) holds ∀n≥2, then ∀n P(n)

2. the Principle of Strong induction is:
Let P be property of N, assume:
1) P(1) holds
2) if P(1),...,P(n-1) hold, then P(n) holds ∀n≥2, then ∀n P(n)
This is strong induction on natural numbers with usual ordering. In general, strong induction can be used on any well-ordered set, and its proof is no more difficult.

Suppose you have a set A well-ordered by <. The strong induction principle is:

If for all x in A, (for all y < x, P(y)) implies P(x), then for all x in A, P(x).

You may wonder where the base case is. The set A has the least element, call in x0. Then the premise "for all y < x0, P(y)" is vacuously true: there are no y < x0. Therefore, "(for all y < x0, P(y)) implies P(x0)" is equivalent to P(x0). The idea is that in the induction step, you have to prove P(x) from all P(y) for y < x. Since x0 is the least element, you get no help and you have to prove P(x0) directly.

The easiest way to prove strong induction is by contradiction. Assume that for all x in A, (for all y < x, P(y)) implies P(x). Also, suppose that P(x) is not universally true. Consider the set {x in A | P(x) is false} and use the well-ordering property on this set.


text:
# A finite dimensional linear programming approximation of Mather variational problem

created by granieri on 23 Jul 2009
modified on 06 Sep 2010

[BibTeX]

Published Paper

Inserted: 23 jul 2009
Last Updated: 6 sep 2010

Journal: ESAIM COCV
Year: 2009
Notes:

Published online October 9, 2009. The original paper is available on http:/www.esaim-cocv.org

Abstract:

We provide an approximation of Mather variational problem by finite dimensional minimization problems in the framework of $\Gamma$-convergence. By a linear programming interpretation as done in Evans-Gomez paper we state a duality theorem for the Mather problem, as well a finite dimensional approximation for the dual problem.


text:
# Lecture 003

Dotted Quad Notation: in 127.0.0.1 we define 127 as first quad, 0 as second, 0 as third, and 1 as fourth quad. Each quad is 8 bits long.

Flat addressing: no structure, could be a random number

• e.g. social security number

• defined by IEEE

• Networks ("LAN") use this: Ethernet, WiFi, Bluetooth

• It assumes network to be small (to avoid collision), but reality is layer 2 network is big. The assumption is incorrect, but it works fine as computing technology improved.

• 48 bits long (very big, but collision do happen)

Switch: look up address and send data to specific port.

• routing table is filled using routing protocols (VGP using Bellman-ford, Dijkstra algorithm)

• the exact protocol depends on type of network
• LANs use different due to historical reason
• Internet use BGP based on Bellman-Ford
• bridge / switch track a table of MAC address with port (and timer)

• so given a MAC address (or, in another word, Ethernet Address), it send packet to port

• initial packets are broadcasted: when a new device join the LAN, the switch does not know its MAC Address associated with port. Therefore when the first packet send to a MAC Address that is not in the current table, the message will be broadcasted. When someone respond, then the switch will associate whoever responded in some port with that MAC Address. (This is extremely insecure, but security is typically handeled at application layer.)

Hierarchical addresses: has a structure, simplify deliver packets

• e.g. postal address, telephone number

Network Functions: (only the first two will impact distributed system)

1. Packet Forwarding: (run at high frequency)
2. Network Control: executing routing protocols, update forwarding table, ... (once every minutes)
3. Network Management: adding new wires, change forward rules by traffic engineers (infrequent)

Network vs Internet:

• ownership

• scale

Money aspect: user -> content provider -> commerce -> ISPs -> ISPs...

IPv4: not flat

• it is hard to know whether an IPv4 address is used (it is too short, can't randomly generate and hope)

• packet forwarding is expensive and slow: table lookup is costly with large table size

• Routing protocol is CPU and bandwidth hungry: constructing large lookup table is costly

When ISPs gives you a network IP, then you can assign up to $2^9$ many IPs to your machines without talking to ISP. When other people outside of network send a packet to your IP, ISP only use network to send packet to your network. You are responsible to use host to the actual machine (or drop it if you want).

So routing protocol only need to identify paths to all networks, not all hosts

8bit network and 24bit host

### Class-based IP

As a solution to original IP Address

• Problem: Everybody is asking for class B (no specific reason, just fact)

• The prefix is used to identify class in routers.

Classless Interdomain Routing (CIDR):

• network predix (network) can be any size

• use a slash /26 to denote howmany network bits (or, formally, 32-bit mask like 255.255.255.192)
• help with space deplition, but hurt forwarding speed

IETF developed

• define IPv6: 128 bits address

• different chunks for geographical addressing in IPv4
• 48-bit chunk per LAN guaranteed (those 48-bit assigned to device is the same as device MAC Address (or Ethernet Address). When packet send into a LAN, LAN will start to read MAC Address, the last 48-bit.
• Chunks for Geographic addressing, with IPv4 address space (help clean up routing tables)
• Network address translation (NAT): hosts share IP address and only translated inside network

Assigning IPv4:

• Internet Corporation for Assigned Names and Numbers (ICANN) assign large chunks to Regional Internet Registries (e.g. American Registry for Internet Names (ARIN)

• Regional Internet Registries assign chunks to ISPs

• ISPs assign to Institutions

• Institutions assign to individuals

## Packet Delay

Delays:

• Propagation delay on links: proportional to the length of the link

• Processing delay on switches: depends on the speed of the router

• Queuing delay on switches: depends on the traffic load and queue size

Roundtrip Time (RTT): measure the time by ping, the fastest delay you can ever get.

• two way delay

• include server processing time

• RTT for in-kernel protocols is a bit shorter: since kernel code is counting the time, not application.

• easy to measure

Efficiency: Fully use the bandwidth on the bottleneck link Fairness: all flows have the same throughput (having same bandwith is not realistic)

Max-min Fairness:

1. Assume each connection need some bandwidth $\{1, 5, 3, 7, 9\}$. And each switch or router has some bandwidth $10$.
2. Evenly all bandwidth among all people. $\{2, 2, 2, 2, 2\}$
3. Notice that we exceed bandwidth for the first connection. Then we divide its bandwidth among others: $\{1, 2\frac{1}{4}, 2\frac{1}{4}, 2\frac{1}{4}, 2\frac{1}{4}\}$

If we put this rule into multiple routers: Longer paths are likely to experience significant congestion.

Flow Completion Time: a metric to measure performance of the network concerning the entire protocol stack - associated with ending and receiving a block of data (image, HTML, video)

Optimizing FCT is possible, e.g. in datacenter where the infrastructure is controlled by only one organization

TCP: reliable, two-way byte stream service

• reliable: bytes received correctly in order

• connection: three way handshake

• flow control: avoid sender outrun receivers and disallow receiver to drop packet due to buffer overflow

• error control: recover from packet loss, corruption, reordering

• congestion control: controls the transmit rate of the sender (too slow increase FCT, too fast result in packet loss)

• $\text{Transmit Rate} = \frac{\text{CC Window}}{\text{RTT}}$
• CC window is initialized to 10 packets and updated every RTT based on packet loss
• TCP with low RTT has higher transmit rate at the start, and it increase faster

TCP is developed during world war. This specific behavior was invented by assuming there is poor connection between US's military after nuclear impact

Edge Computing: move data center closer to the clients

Table of Content


text:
# Nested Primes

Yesterday’s post from Programming Praxis poses an interesting problem: find the largest prime n such that the result of repeatedly removing each digit of n from left to right is also always prime.

For example, 6317 would be such a number, as not only is it prime, but so are 317, 17, and 7.

This is actually a surprisingly straightforward problem, if instead of starting at the largest such number and checking to make sure that each part along the way is prime, you start with the single digit primes (2, 3, 5, and 7) and repeatedly add on numbers to the left so long as they are prime.

For example, 3 would become 13, 23, 43, 53, 73, and 83. 13 in turn would become 113, 313, and 613. It turns out though that this list doesn’t grow unbounded. Eventually each branch will terminate (a proof for why this happens would be interesting, but I’m not sure how it would work–or even if such a thing is provable short of proof by enumerating all of the solutions).

Enough on discussion though, it’s code time!

(Only Racket today as I’m running a bit short on time for my writeup. If anyone would like a Python version as well, let me know in the comments and I’ll write one up.)

; find the largest prime such that each number produced by
; removing digits from the left side is still prime
; #:root - the prime to start at, 0 for all primes
; #:limit - the largest prime to check
(define (largest-nested-prime
#:root [root 0]
#:limit [limit +inf.0])
; loop starting at the root
(let loop ([n root])
(cond
; if we're over the limit, no largest prime
[(> n limit) 0]
; otherwise, try each prefixed digit while still prime
[else
(define multiplier (expt 10 (digits n)))
; use for/fold to emulate what for/max would do
(for/fold ([best n])
([i (in-range 1 10)]
#:when (prime? (+ (* multiplier i) n)))
; return the best of the current and the nested
(max best (loop (+ (* multiplier i) n))))])))

That’s a whopping 10 lines of code if you remove the comments and collapse the define back into a single line. Not too bad for what it’s calculating.

It takes rather a while to run, but eventually you’ll get an answer:

> (largest-nested-prime)
357686312646216567629137

What I’m curious about though, is there a better way to do this? I used the trial division method of determining if a number was prime, but I wonder if either a statistical method or perhaps a sieve would work better. Perhaps it’ll be something to try one day if I get bored. 😄

One additional thing I did was to work out the nested tree structure that you get with something like this. The code is available at GitHub, but here’s a sample run just to whet your appetite:

> (nested-primes #:root 3 #:limit 1000)
'(3
(13 (113) (313) (613))
(23 (223) (523) (823))
(43 (443) (643) (743))
(53 (353) (653) (853) (953))
(73 (173) (373) (673) (773))
(83 (283) (383) (683) (883) (983)))

Here’s a nice chart of that:

My goal is to generate a list of all such primes and make a graph of them all, just to see if there’s any sort of visual pattern. I was going to include that in this post, but I have a feeling that code is going to take more than a little time to generate (and actually returning the list directly isn’t probably a good idea as that way it all has to exist in memory at the same time). So I’ll probably optimize this and post it again later. Graph visualization is fun!

If you’d like to download the full code for today’s post, you can do so here: nested primes source


text:
An electron starting from rest has a velocity that increases linearly with time i.e $v= kt$ where $k=2\;m\;s^{-2}$. The distance covered in the first 3 second is
$\begin{array}{1 1} (A) \;9\;m \\ (B) \;16\;m \\ (C)\;27\;m \\ (D)\;36\;m \end{array}$


text:
## anonymous 5 years ago find the average value f(x,y,z) = xyz over the spherical region x^2 _ y^2 + z^2 <=1

1. anonymous

take $x=rcos \phi \cos \theta, y=r \cos \phi \sin \theta, z=rcos \theta$

2. anonymous

and you plug those into the integral but what are the bounds

3. anonymous

then $f _{avg}=3/(4\pi)\int\limits_{r=0}^{1}\int\limits_{\theta=0}^{\pi}\int\limits_{\phi=0}^{2\pi}r ^{3}\sin ^{2}\theta \cos \theta \sin \phi \cos \phi drd \theta d \phi$ probably this will give you 0

4. anonymous

5. anonymous

okay I am working it right now

6. anonymous

i cant understand


text:
Periodic Trend: Effective Nuclear Charge Video Lessons

Concept: Periodic Trend: Effective Nuclear Charge

# Problem: Among elements 1–18, which element or elements have the smallest effective nuclear charge if we use Equation 7.1 to calculate Zeff? Which element or elements have the largest effective nuclear charge?

###### FREE Expert Solution

Recall that the effective nuclear charge is the force exerted by the nucleus onto an electron and is given by:

$\overline{){{\mathbf{Z}}}_{{\mathbf{eff}}}{\mathbf{=}}{\mathbf{Z}}{\mathbf{-}}{\mathbf{S}}}$

The shielding constant, S = core electrons

For the elements:

• Hydrogen: 1s → core e- = 0
• Z = 1, S = 0
• Zeff = 1 - 0 = 1
95% (157 ratings)
###### Problem Details

Among elements 1–18, which element or elements have the smallest effective nuclear charge if we use Equation 7.1 to calculate Zeff? Which element or elements have the largest effective nuclear charge?