text:
# Program synthesis

In computer science, program synthesis is the task to construct a program that provably satisfies a given high-level formal specification. In contrast to program verification, the program is to be constructed rather than given; however, both fields make use of formal proof techniques, and both comprise approaches of different degrees of automatization. In contrast to automatic programming techniques, specifications in program synthesis are usually non-algorithmic statements in an appropriate logical calculus.[1]

## Origin

During the Summer Institute of Symbolic Logic at Cornell University in 1957, Alonzo Church defined the problem to synthesize a circuit from mathematical requirements.[2] Even though the work only refers to circuits and not programs, the work is considered to be one of the earliest descriptions of program synthesis and some researchers refer to program synthesis as "Church's Problem". In the 1960s, a similar idea for an "automatic programmer" was explored by researchers in artificial intelligence.[citation needed]

Since then, various research communities considered the problem of program synthesis. Notable works include the 1969 automata-theoretic approach by Büchi and Landweber,[3] and the works by Manna and Waldinger (c. 1980). The development of modern high-level programming languages can also be understood as a form of program synthesis.

## 21st century developments

The early 21st century has seen a surge of practical interest in the idea of program synthesis in the formal verification community and related fields. Armando Solar-Lezama showed that it is possible to encode program synthesis problems in Boolean logic and use algorithms for the Boolean satisfiability problem to automatically find programs.[4] In 2013, a unified framework for program synthesis problems was proposed by researchers at UPenn, UC Berkeley, and MIT.[5] Since 2014 there has been a yearly program synthesis competition comparing the different algorithms for program synthesis in a competitive event, the Syntax-Guided Synthesis Competition or SyGuS-Comp.[6] Still, the available algorithms are only able to synthesize small programs.

A 2015 paper demonstrated synthesis of PHP programs axiomatically proven to meet a given specification, for purposes such as checking a number for being prime or listing the factors of a number.[7]

## The framework of Manna and Waldinger

Non-clausal resolution rules (unifying substitutions not shown)
Nr Assertions Goals Program Origin
51 ${\displaystyle E[p]}$
52 ${\displaystyle F[p]}$
53 ${\displaystyle G[p]}$ s
54 ${\displaystyle H[p]}$ t
55 ${\displaystyle E[{\text{true}}]\lor F[{\text{false}}]}$ Resolve(51,52)
56 ${\displaystyle \lnot F[{\text{true}}]\land G[{\text{false}}]}$ s Resolve(52,53)
57 ${\displaystyle \lnot F[{\text{false}}]\land G[{\text{true}}]}$ s Resolve(53,52)
58 ${\displaystyle G[{\text{true}}]\land H[{\text{false}}]}$ p ? s : t Resolve(53,54)

The framework of Manna and Waldinger, published in 1980,[8][9] starts from a user-given first-order specification formula. For that formula, a proof is constructed, thereby also synthesizing a functional program from unifying substitutions.

The framework is presented in a table layout, the columns containing:

• A line number ("Nr") for reference purposes
• Formulas that already have been established, including axioms and preconditions, ("Assertions")
• Formulas still to be proven, including postconditions, ("Goals"),[note 1]
• Terms denoting a valid output value ("Program")[note 2]
• A justification for the current line ("Origin")

Initially, background knowledge, pre-conditions, and post-conditions are entered into the table. After that, appropriate proof rules are applied manually. The framework has been designed to enhance human readability of intermediate formulas: contrary to classical resolution, it does not require clausal normal form, but allows one to reason with formulas of arbitrary structure and containing any junctors ("non-clausal resolution"). The proof is complete when ${\displaystyle {\it {true}}}$ has been derived in the Goals column, or, equivalently, ${\displaystyle {\it {false}}}$ in the Assertions column. Programs obtained by this approach are guaranteed to satisfy the specification formula started from; in this sense they are correct by construction.[10] Only a minimalist, yet Turing-complete, functional programming language, consisting of conditional, recursion, and arithmetic and other operators[note 3] is supported. Case studies performed within this framework synthesized algorithms to compute e.g. division, remainder,[11] square root,[12] term unification,[13] answers to relational database queries[14] and several sorting algorithms.[15][16]

### Proof rules

Proof rules include:

For example, line 55 is obtained by resolving Assertion formulas ${\displaystyle E}$ from 51 and ${\displaystyle F}$ from 52 which both share some common subformula ${\displaystyle p}$. The resolvent is formed as the disjunction of ${\displaystyle E}$, with ${\displaystyle p}$ replaced by ${\displaystyle {\it {true}}}$, and ${\displaystyle F}$, with ${\displaystyle p}$ replaced by ${\displaystyle {\it {false}}}$. This resolvent logically follows from the conjunction of ${\displaystyle E}$ and ${\displaystyle F}$. More generally, ${\displaystyle E}$ and ${\displaystyle F}$ need to have only two unifiable subformulas ${\displaystyle p_{1}}$ and ${\displaystyle p_{2}}$, respectively; their resolvent is then formed from ${\displaystyle E\theta }$ and ${\displaystyle F\theta }$ as before, where ${\displaystyle \theta }$ is the most general unifier of ${\displaystyle p_{1}}$ and ${\displaystyle p_{2}}$. This rule generalizes resolution of clauses.[17]
Program terms of parent formulas are combined as shown in line 58 to form the output of the resolvent. In the general case, ${\displaystyle \theta }$ is applied to the latter also. Since the subformula ${\displaystyle p}$ appears in the output, care must be taken to resolve only on subformulas corresponding to computable properties.
• Logical transformations.
For example, ${\displaystyle E\land (F\lor G)}$ can be transformed to ${\displaystyle (E\land F)\lor (E\land G)}$) in Assertions as well as in Goals, since both are equivalent.
• Splitting of conjunctive assertions and of disjunctive goals.
An example is shown in lines 11 to 13 of the toy example below.
This rule allows for synthesis of recursive functions. For a given pre- and postcondition "Given ${\displaystyle x}$ such that ${\displaystyle {\textit {pre}}(x)}$, find ${\displaystyle f(x)=y}$ such that ${\displaystyle {\textit {post}}(x,y)}$", and an appropriate user-given well-ordering ${\displaystyle \prec }$ of the domain of ${\displaystyle x}$, it is always sound to add an Assertion "${\displaystyle x'\prec x\land {\textit {pre}}(x')\implies {\textit {post}}(x',f(x'))}$".[18] Resolving with this assertion can introduce a recursive call to ${\displaystyle f}$ in the Program term.
An example is given in Manna, Waldinger (1980), p.108-111, where an algorithm to compute quotient and remainder of two given integers is synthesized, using the well-order ${\displaystyle (n',d')\prec (n,d)}$ defined by ${\displaystyle 0\leq n' (p.110).

Murray has shown these rules to be complete for first-order logic.[19] In 1986, Manna and Waldinger added generalized E-resolution and paramodulation rules to handle also equality;[20] later, these rules turned out to be incomplete (but nevertheless sound).[21]

### Example

Example synthesis of maximum function
Nr Assertions Goals Program Origin
1 ${\displaystyle A=A}$ Axiom
2 ${\displaystyle A\leq A}$ Axiom
3 ${\displaystyle A\leq B\lor B\leq A}$ Axiom
10 ${\displaystyle x\leq M\land y\leq M\land (x=M\lor y=M)}$ M Specification
11 ${\displaystyle (x\leq M\land y\leq M\land x=M)\lor (x\leq M\land y\leq M\land y=M)}$ M Distr(10)
12 ${\displaystyle x\leq M\land y\leq M\land x=M}$ M Split(11)
13 ${\displaystyle x\leq M\land y\leq M\land y=M}$ M Split(11)
14 ${\displaystyle x\leq x\land y\leq x}$ x Resolve(12,1)
15 ${\displaystyle y\leq x}$ x Resolve(14,2)
16 ${\displaystyle \lnot (x\leq y)}$ x Resolve(15,3)
17 ${\displaystyle x\leq y\land y\leq y}$ y Resolve(13,1)
18 ${\displaystyle x\leq y}$ y Resolve(17,2)
19 ${\displaystyle {\textit {true}}}$ x<y ? y : x Resolve(18,16)

As a toy example, a functional program to compute the maximum ${\displaystyle M}$ of two numbers ${\displaystyle x}$ and ${\displaystyle y}$ can be derived as follows.[citation needed]

Starting from the requirement description "The maximum is larger than or equal to any given number, and is one of the given numbers", the first-order formula ${\displaystyle \forall X\forall Y\exists M:X\leq M\land Y\leq M\land (X=M\lor Y=M)}$ is obtained as its formal translation. This formula is to be proved. By reverse Skolemization,[note 4] the specification in line 10 is obtained, an upper- and lower-case letter denoting a variable and a Skolem constant, respectively.

After applying a transformation rule for the distributive law in line 11, the proof goal is a disjunction, and hence can be split into two cases, viz. lines 12 and 13.

Turning to the first case, resolving line 12 with the axiom in line 1 leads to instantiation of the program variable ${\displaystyle M}$ in line 14. Intuitively, the last conjunct of line 12 prescribes the value that ${\displaystyle M}$ must take in this case. Formally, the non-clausal resolution rule shown in line 57 above is applied to lines 12 and 1, with

• p being the common instance x=x of A=A and x=M, obtained by syntactically unifying the latter formulas,
• F[p] being truex=x, obtained from instantiated line 1 (appropriately padded to make the context F[⋅] around p visible), and
• G[p] being x ≤ x ∧ y ≤ x ∧ x = x, obtained from instantiated line 12,

yielding ${\displaystyle \lnot (}$truefalse) ∧ (x ≤ x ∧ y ≤ x ∧ true${\displaystyle )}$, which simplifies to ${\displaystyle x\leq x\land y\leq x}$.

In a similar way, line 14 yields line 15 and then line 16 by resolution. Also, the second case, ${\displaystyle x\leq M\land y\leq M\land y=M}$ in line 13, is handled similarly, yielding eventually line 18.

In a last step, both cases (i.e. lines 16 and 18) are joined, using the resolution rule from line 58; to make that rule applicable, the preparatory step 15→16 was needed. Intuitively, line 18 could be read as "in case ${\displaystyle x\leq y}$, the output ${\displaystyle y}$ is valid (with respect to the original specification), while line 15 says "in case ${\displaystyle y\leq x}$, the output ${\displaystyle x}$ is valid; the step 15→16 established that both cases 16 and 18 are complementary.[note 5] Since both line 16 and 18 comes with a program term, a conditional expression results in the program column. Since the goal formula ${\displaystyle {\textit {true}}}$ has been derived, the proof is done, and the program column of the "${\displaystyle {\textit {true}}}$" line contains the program.

This procedure produces only a single operator of the form p?s:t taken from line 58. This is not a programming language because it is not Turing Complete. There are no commands e.g. ASSIGNMENT, IF/ELSE, FOR/WHILE or recursive programs, that are needed to make a language Turing Complete. It should be labeled as such: a way to create a single logical operator, not a way to create programs in general. Perhaps “Operator Synthesis” could be used. A method to build a wheel is not a method to build an automobile.[citation needed]

## Notes

1. ^ The distinction "Assertions" / "Goals" is for convenience only; following the paradigm of proof by contradiction, a Goal ${\displaystyle F}$ is equivalent to an assertion ${\displaystyle \lnot F}$.
2. ^ When ${\displaystyle F}$ and ${\displaystyle s}$ is the Goal formula and the Program term in a line, respectively, then in all cases where ${\displaystyle F}$ holds, ${\displaystyle s}$ is a valid output of the program to be synthesized. This invariant is maintained by all proof rules. An Assertion formula usually is not associated with a Program term.
3. ^ Only the conditional operator (?:) is supported from the beginning. However, arbitrary new operators and relations can be added by providing their properties as axioms. In the toy example below, only the properties of ${\displaystyle =}$ and ${\displaystyle \leq }$ that are actually needed in the proof have been axiomatized, in line 1 to 3.
4. ^ While ordinary Skolemization preserves satisfiability, reverse Skolemization, i.e. replacing universally quantified variables by functions, preserves validity.
5. ^ Axiom 3 was needed for that; in fact, if ${\displaystyle \leq }$ wasn't a total order, no maximum could be computed for uncomparable inputs ${\displaystyle x,y}$.

## References

1. ^ Basin, D.; Deville, Y.; Flener, P.; Hamfelt, A.; Fischer Nilsson, J. (2004). "Synthesis of programs in computational logic". In M. Bruynooghe and K.-K. Lau (ed.). Program Development in Computational Logic. LNCS. 3049. Springer. pp. 30–65. CiteSeerX 10.1.1.62.4976.
2. ^ Alonzo Church (1957). "Applications of recursive arithmetic to the problem of circuit synthesis". Summaries of the Summer Institute of Symbolic Logic. 1: 3–50.
3. ^ Richard Büchi, Lawrence Landweber (Apr 1969). "Solving Sequential Conditions by Finite-State Strategies". Transactions of the American Mathematical Society. 138: 295–311. doi:10.2307/1994916. JSTOR 1994916.
4. ^ Solar-Lezama, Armando (2008). Program synthesis by sketching (Ph.D.). University of California, Berkeley.
5. ^ Alur, Rajeev; al., et (2013). "Syntax-guided Synthesis". Proceedings of Formal Methods in Computer-Aided Design. IEEE. p. 8.
6. ^ SyGuS-Comp (Syntax-Guided Synthesis Competition)
7. ^ Charles Volkstorf (7 Jan 2015). "Program Synthesis from Axiomatic Proof of Correctness". arXiv:1501.01363 [cs.LO].
8. ^ Zohar Manna, Richard Waldinger (Jan 1980). "A Deductive Approach to Program Synthesis". ACM Transactions on Programming Languages and Systems. 2: 90–121. doi:10.1145/357084.357090.
9. ^ Zohar Manna and Richard Waldinger (Dec 1978). A Deductive Approach to Program Synthesis (PDF) (Technical Note). SRI International.
10. ^ See Manna, Waldinger (1980), p.100 for correctness of the resolution rules.
11. ^ Manna, Waldinger (1980), p.108-111
12. ^ Zohar Manna and Richard Waldinger (Aug 1987). "The Origin of a Binary-Search Paradigm". Science of Computer Programming. 9 (1): 37–83. doi:10.1016/0167-6423(87)90025-6.
13. ^ Daniele Nardi (1989). "Formal Synthesis of a Unification Algorithm by the Deductive-Tableau Method". Journal of Logic Programming. 7: 1–43. doi:10.1016/0743-1066(89)90008-3.
14. ^ Daniele Nardi and Riccardo Rosati (1992). "Deductive Synthesis of Programs for Query Answering". In Kung-Kiu Lau and Tim Clement (ed.). International Workshop on Logic Program Synthesis and Transformation (LOPSTR). Workshops in Computing. Springer. pp. 15–29. doi:10.1007/978-1-4471-3560-9_2.
15. ^ Jonathan Traugott (1986). "Deductive Synthesis of Sorting Programs". Proceedings of the International Conference on Automated Deduction. LNCS. 230. Springer. pp. 641–660.
16. ^ Jonathan Traugott (Jun 1989). "Deductive Synthesis of Sorting Programs". Journal of Symbolic Computation. 7 (6): 533–572. doi:10.1016/S0747-7171(89)80040-9.
17. ^ Manna, Waldinger (1980), p.99
18. ^ Manna, Waldinger (1980), p.104
19. ^ Manna, Waldinger (1980), p.103, referring to: Neil V. Murray (Feb 1979). A Proof Procedure for Quantifier-Free Non-Clausal First Order Logic (Technical report). Syracuse Univ. 2-79.
20. ^ Zohar Manna, Richard Waldinger (Jan 1986). "Special Relations in Automated Deduction". Journal of the ACM. 33: 1–59. doi:10.1145/4904.4905.
21. ^ Zohar Manna, Richard Waldinger (1992). "The Special-Relations Rules are Incomplete". Proc. CADE 11. LNCS. 607. Springer. pp. 492–506.
• Zohar Manna, Richard Waldinger (1975). "Knowledge and Reasoning in Program Synthesis". Artificial Intelligence. 6 (2): 175–208. doi:10.1016/0004-3702(75)90008-9.
• Jonathan Traugott (1986). "Deductive Synthesis of Sorting Programs". Proceedings of the International Conference on Automated Deduction. LNCS. 230. Springer. pp. 641–660.


text:
Browse Questions

# The number of $\sigma$-bonds and $\pi$-bonds in $XeO_4$ are

$\begin{array}{1 1}(a)\;4\sigma\text{ bonds and }o\pi\text {bonds}\\(b)\;4\sigma\text{ bonds and }4\pi\text {bonds}\\(c)\;2\sigma\text{ bonds and }2\pi\text {bonds}\\(d)\;0\sigma\text{ bonds and }4\pi\text {bonds}\end{array}$

Can you answer this question?

According to VSEPR theory in $XeO_4$ there are $4\sigma$ bonds and $4\pi$ bonds in tetrahedral structure of $XeO_4$
Hence (b) is the correct answer.
answered Mar 5, 2014

format: plain


text:
NZ Level 7 (NZC) Level 2 (NCEA)
Log Laws, Log Properties with Natural Logs

Interactive practice questions

Which of the following expressions is equivalent to $\ln\left(\frac{15}{8}\right)$ln(158)?

$\ln\left(15-8\right)$ln(158)

A

$\ln15-\ln8$ln15ln8

B

$\frac{\ln15}{\ln8}$ln15ln8

C

$\ln120$ln120

D

$\ln\left(15-8\right)$ln(158)

A

$\ln15-\ln8$ln15ln8

B

$\frac{\ln15}{\ln8}$ln15ln8

C

$\ln120$ln120

D
Easy
Less than a minute

Rewrite $\ln3+\ln5$ln3+ln5 as a single logarithm.

Rewrite each of the following expressions as single logarithms.

Outcomes

M7-6

Manipulate rational, exponential, and logarithmic algebraic expressions

91261

Apply algebraic methods in solving problems


text:
You are currently browsing the monthly archive for January 2011.

Last week I gave a talk at the Trinity Mathematical Society at Trinity College, Cambridge UK.  As the audience was primarily undergraduate, I gave a fairly non-technical talk on the universality phenomenon, based on this blog article of mine on the same topic.  It was a quite light and informal affair, and this is reflected in the talk slides (which, in particular, play up quite strongly the role of former students and Fellows of Trinity College in this story).   There was some interest in making these slides available publicly, so I have placed them on this site here.  (Note: copyright for the images in these slides has not been secured.)

As I have done in the last three years, I am spending some time at the beginning of this year converting some of my posts on this blog into book format.  This time round, the situation is a bit different because the majority of mathematical posts last year came from three courses I have taught: random matrices, higher-order Fourier analysis, and measure theory.  These topics are sufficiently unrelated to each other, and to the other mathematical posts from 2010, that I am thinking of having as many as four distinct books this time around, though my plans are not yet definite in this regard.

In any event, I have started the process by converting the measure theory notes to book form, a draft copy of which is now available here.  I have also started up a stub of a book page for this text, though it has little content at present beyond that link.    I will be continuing to work on it in parallel with the rest of the conversion process.  As always, any comments and corrections are very welcome.

Let ${G}$ be a compact group. (Throughout this post, all topological groups are assumed to be Hausdorff.) Then ${G}$ has a number of unitary representations, i.e. continuous homomorphisms ${\rho: G \rightarrow U(H)}$ to the group ${U(H)}$ of unitary operators on a Hilbert space ${H}$, equipped with the strong operator topology. In particular, one has the left-regular representation ${\tau: G \rightarrow U(L^2(G))}$, where we equip ${G}$ with its normalised Haar measure ${\mu}$ (and the Borel ${\sigma}$-algebra) to form the Hilbert space ${L^2(G)}$, and ${\tau}$ is the translation operation

$\displaystyle \tau(g) f(x) := f(g^{-1} x).$

We call two unitary representations ${\rho: G \rightarrow U(H)}$ and ${\rho': G \rightarrow U(H')}$ isomorphic if one has ${\rho'(g) = U \rho(g) U^{-1}}$ for some unitary transformation ${U: H \rightarrow H'}$, in which case we write ${\rho \equiv \rho'}$.

Given two unitary representations ${\rho: G \rightarrow U(H)}$ and ${\rho': G \rightarrow U(H')}$, one can form their direct sum ${\rho \oplus \rho': G \rightarrow U(H \oplus H')}$ in the obvious manner: ${\rho \oplus \rho'(g)(v) := (\rho(g) v, \rho'(g) v)}$. Conversely, if a unitary representation ${\rho: G \rightarrow U(H)}$ has a closed invariant subspace ${V \subset H}$ of ${H}$ (thus ${\rho(g) V \subset V}$ for all ${g \in G}$), then the orthogonal complement ${V^\perp}$ is also invariant, leading to a decomposition ${\rho \equiv \rho\downharpoonright_V \oplus \rho\downharpoonright_{V^\perp}}$ of ${\rho}$ into the subrepresentations ${\rho\downharpoonright_V: G \rightarrow U(V)}$, ${\rho\downharpoonright_{V^\perp}: G \rightarrow U(V^\perp)}$. Accordingly, we will call a unitary representation ${\rho: G \rightarrow U(H)}$ irreducible if ${H}$ is nontrivial (i.e. ${H \neq \{0\}}$) and there are no nontrivial invariant subspaces (i.e. no invariant subspaces other than ${\{0\}}$ and ${H}$); the irreducible representations play a role in the subject analogous to those of prime numbers in multiplicative number theory. By the principle of infinite descent, every finite-dimensional unitary representation is then expressible (perhaps non-uniquely) as the direct sum of irreducible representations.

The Peter-Weyl theorem asserts, among other things, that the same claim is true for the regular representation:

Theorem 1 (Peter-Weyl theorem) Let ${G}$ be a compact group. Then the regular representation ${\tau: G \rightarrow U(L^2(G))}$ is isomorphic to the direct sum of irreducible representations. In fact, one has ${\tau \equiv \bigoplus_{\xi \in \hat G} \rho_\xi^{\oplus \hbox{dim}(V_\xi)}}$, where ${(\rho_\xi)_{\xi \in \hat G}}$ is an enumeration of the irreducible finite-dimensional unitary representations ${\rho_\xi: G \rightarrow U(V_\xi)}$ of ${G}$ (up to isomorphism). (It is not difficult to see that such an enumeration exists.)

In the case when ${G}$ is abelian, the Peter-Weyl theorem is a consequence of the Plancherel theorem; in that case, the irreducible representations are all one dimensional, and are thus indexed by the space ${\hat G}$ of characters ${\xi: G \rightarrow {\bf R}/{\bf Z}}$ (i.e. continuous homomorphisms into the unit circle ${{\bf R}/{\bf Z}}$), known as the Pontryagin dual of ${G}$. (See for instance my lecture notes on the Fourier transform.) Conversely, the Peter-Weyl theorem can be used to deduce the Plancherel theorem for compact groups, as well as other basic results in Fourier analysis on these groups, such as the Fourier inversion formula.

Because the regular representation is faithful (i.e. injective), a corollary of the Peter-Weyl theorem (and a classical theorem of Cartan) is that every compact group can be expressed as the inverse limit of Lie groups, leading to a solution to Hilbert’s fifth problem in the compact case. Furthermore, the compact case is then an important building block in the more general theory surrounding Hilbert’s fifth problem, and in particular a result of Yamabe that any locally compact group contains an open subgroup that is the inverse limit of Lie groups.

I’ve recently become interested in the theory around Hilbert’s fifth problem, due to the existence of a correspondence principle between locally compact groups and approximate groups, which play a fundamental role in arithmetic combinatorics. I hope to elaborate upon this correspondence in a subsequent post, but I will mention that versions of this principle play a crucial role in Gromov’s proof of his theorem on groups of polynomial growth (discussed previously on this blog), and in a more recent paper of Hrushovski on approximate groups (also discussed previously). It is also analogous in many ways to the more well-known Furstenberg correspondence principle between ergodic theory and combinatorics (also discussed previously).

Because of the above motivation, I have decided to write some notes on how the Peter-Weyl theorem is proven. This is utterly standard stuff in abstract harmonic analysis; these notes are primarily for my own benefit, but perhaps they may be of interest to some readers also.

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our paper “A note on approximate subgroups of ${GL_n({\bf C})}$ and uniformly nonamenable groups“. In this short note, we obtain a new proof of a “noncommutative Freiman” type theorem in linear groups ${GL_n({\bf C})}$. As discussed in earlier blog posts, a general question in additive (or multiplicative) combinatorics is to understand the structure of approximate groups – subsets ${A}$ of genuine groups ${G}$ which are a symmetric neighbourhood the identity (thus ${id \in A}$ and ${a^{-1} \in A}$ whenever ${a \in A}$), and such that the product set ${A \cdot A := \{ ab: a,b \in A \}}$ is covered by ${K}$ left (or right) translates of ${A}$ for some bounded ${K}$. (The case ${K=1}$ corresponds to the case of a genuine group.) Most of the focus in multiplicative combinatorics has been on the “discrete” case when ${A}$ is a finite set, though continuous cases are also of interest (for instance, small balls around the identity in a Lie group are approximate groups).

In the discrete case, examples of approximate groups include:

• Finite groups;
• Balls in a discrete abelian group, or more generally a discrete nilpotent group, with boundedly many generators;
• Extensions of the latter type of balls by finite groups;
• Approximate groups ${A}$ that are controlled by one of the previous examples ${B}$, in the sense that ${A}$ has comparable cardinality to ${B}$, and can be covered by boundedly many translates of ${B}$.

It was conjectured independently by Helfgott and Lindenstrauss (private communication) that these are in fact the only examples of finite approximate groups. This conjecture is not yet settled in general (although we, with Tom Sanders, are making progress on this problem that we hope to be able to report on soon). However, many partial results are known. In particular, as part of the recent paper of Hrushovski in which model-theoretic techniques were introduced to study approximate groups, the following result was established:

Theorem 1 If ${n=O(1)}$, then every approximate subgroup of ${GL_n({\bf C})}$ is controlled by a nilpotent approximate subgroup.

This result can be compared with Jordan’s theorem (discussed earlier on this blog) that every finite subgroup of ${GL_n({\bf C})}$ is virtually abelian (with a uniform bound on the index of the abelian subgroup), or the special case of Gromov’s theorem for linear groups (which follows easily from the Tits alternative and the work of Milnor and of Wolf) that every finitely generated subgroup in ${GL_n({\bf C})}$ of polynomial growth is virtually nilpotent.

Hrushovski’s proof of the above argument was quite sophisticated; one first transplants the problem using model-theoretic techniques to an infinitary setting, in which the approximate group induces a locally compact topological group structure, which can be played off against the Lie group structure of ${GL_n({\bf C})}$ using the machinery of a paper of Larsen and Pink, as discussed in this previous blog article.

Two further proofs of this theorem were obtained by ourselves, as well as in the most recent version of a similar preprint by Pyber and Szabo. The arguments used here are variants of those used in earlier papers of Helfgott, and are based on establishing expansion of sets that generated Zariski-dense subgroups of various Lie groups (such as ${SL_n({\bf C})}$). Again, the machinery of Larsen and Pink (which controls how such approximate subgroups intersect with algebraic subgroups) plays a central role.

In this note we give a new proof of this theorem, based primarily on a different tool, namely the uniform Tits alternative of Breuillard. Recall that the Tits alternative asserts that a finitely generated subgroup of ${GL_n({\bf C})}$ is either virtually solvable, or contains a copy of a free group on two generators. In other words, if ${A}$ is a finite symmetric neighbourhood of the identity of ${GL_n({\bf C})}$, then either ${A}$ generates a virtually solvable subgroup, or else some power ${A^m}$ of ${A}$ contains two elements ${x,y}$ that generate a free group. As stated, ${m}$ may depend on ${A}$. However, the uniform Tits alternative makes the stronger assertion that one can take ${m=m(n)}$ to be uniform in ${A}$, and depend only on the dimension parameter ${n}$.

To use this alternative, we have the following simple observation, that asserts that multiplication by two elements that generate a free group forces a small amount of expansion:

Lemma 2 Let ${A, B}$ be finite sets, such that ${B}$ is symmetric and contains two elements ${x,y}$ that generate a free group ${F_2}$. Then ${|A \cdot B| \geq |A|}$.

We remark that this lemma immediately establishes the classical fact that any group that contains a copy of ${F_2}$ is not amenable, an observation initially made by von Neumann.

Proof: By foliating ${A}$ into cosets of ${F_2}$ and translating, we may assume without loss of generality that ${A \subset F_2}$. Observe that for every element ${a}$ in ${A}$, at least three of the four elements ${ax, ay, ax^{-1}, ay^{-1}}$ has a longer word length than ${a}$, while lying in ${A \cdot X}$. Furthermore, all such elements generated in this fashion are distinct (as one can recover the initial word ${a}$ from the longer word by truncation). The claim follows. $\Box$

This can be combined with a lemma of Sanders (also independently established by Croot and Sisask), that asserts that for any approximate group ${A}$, and any ${r=O(1)}$, one can find a smaller version ${S}$ of ${A}$ – also a symmetric neighbourhood of the identity – with the property that ${S^r \subset A^4}$, while ${S}$ remains of comparable size to ${A}$. (One should think of ${A}$ as being like a ball of some radius ${R}$, in which case ${S}$ is analogous to a ball of radius ${R/r}$). In particular, ${A \cdot S^r \subset A^5}$ still has size comparable to ${A}$. Inspecting the size of the sets ${A, A \cdot S, A \cdot S^2, \ldots, A \cdot S^r}$, we conclude (if ${r}$ is large enough) from the above lemma that ${S}$ cannot contain two elements that generate a free group. Indeed, a slight modification of this argument shows that for any ${m = O(1)}$, if we take ${r}$ sufficiently large depending on ${m}$, that ${S^m}$ does not contain two elements that generate a free group. Applying the uniform Tits alternative, this shows that ${S}$ generates a virtually solvable subgroup of ${GL_n({\bf C})}$. From the known product theory for such groups (due to Breuillard and Green), ${S}$ (and hence ${A}$) is therefore controlled by a virtually nilpotent group, as desired.

Tamar Ziegler and I have just uploaded to the arXiv our paper “The inverse conjecture for the Gowers norm over finite fields in low characteristic“, submitted to Annals of Combinatorics. This paper completes another case of the inverse conjecture for the Gowers norm, this time for vector spaces ${{\bf F}^n}$ over a fixed finite field ${{\bf F} = {\bf F}_p}$ of prime order; with Vitaly Bergelson, we had previously established this claim when the characteristic of the field was large, so the main new result here is the extension to the low characteristic case. (The case of a cyclic group ${{\bf Z}/N{\bf Z}}$ or interval ${[N]}$ was established by Ben Green and ourselves in another recent paper. For an arbitrary abelian (or nilpotent) group, a general but less explicit description of the obstructions to Gowers uniformity was recently obtained by Szegedy; the latter result recovers the high-characteristic case of our result (as was done in a subsequent paper of Szegedy), as well as our results with Green, but it is not immediately evident whether Szegedy’s description of the obstructions matches up with the one predicted by the inverse conjecture in low characteristic.)

The statement of the main theorem is as follows. Given a finite-dimensional vector space ${V = {\bf F}^n}$ and a function ${f: V \rightarrow {\bf C}}$, and an integer ${s \geq 0}$, one can define the Gowers uniformity norm ${\|f\|_{U^{s+1}(V)}}$ by the formula

$\displaystyle \|f\|_{U^{s+1}(V)} := \left( \mathop{\bf E}_{x,h_1,\ldots,h_{s+1} \in V} \Delta_{h_1} \ldots \Delta_{h_{s+1}} f(x) \right)^{1/2^{s+1}}$

where ${\Delta_h f(x) := f(x+h) \overline{f(x)}}$. If ${f}$ is bounded in magnitude by ${1}$, it is easy to see that ${\|f\|_{U^{s+1}(V)}}$ is bounded by ${1}$ also, with equality if and only if ${f(x) = e(P)}$ for some non-classical polynomial ${P: V \rightarrow {\bf R}/{\bf Z}}$ of degree at most ${s}$, where ${e(x) := e^{2\pi ix}}$, and a non-classical polynomial of degree at most ${s}$ is a function whose ${s+1^{th}}$ “derivatives” vanish in the sense that

$\displaystyle \partial_{h_1} \ldots \partial_{h_{s+1}} P(x) = 0$

for all ${x,h_1,\ldots,h_{s+1} \in V}$, where ${\partial_h P(x) := P(x+h) - P(x)}$. Our result generalises this to the case when the uniformity norm is not equal to ${1}$, but is still bounded away from zero:

Theorem 1 (Inverse conjecture) Let ${f: V \rightarrow {\bf C}}$ be bounded by ${1}$ with ${\|f\|_{U^{s+1}(V)} \geq \delta > 0}$ for some ${s \geq 0}$. Then there exists a non-classical polynomial ${P: V \rightarrow {\bf R}/{\bf Z}}$ of degree at most ${s}$ such that ${|\langle f, e(P) \rangle_{L^2(V)}| := |{\bf E}_{x \in V} f(x) e(-P(x))| \geq c(s,p, \delta) > 0}$, where ${c(s,p, \delta)}$ is a positive quantity depending only on the indicated parameters.

This theorem is trivial for ${s=0}$, and follows easily from Fourier analysis for ${s=1}$. The case ${s=2}$ was done in odd characteristic by Ben Green and myself, and in even characteristic by Samorodnitsky. In two papers, one with Vitaly Bergelson, we established this theorem in the “high characteristic” case when the characteristic ${p}$ of ${{\bf F}}$ was greater than ${s}$ (in which case there is essentially no distinction between non-classical polynomials and their classical counterparts, as discussed previously on this blog). The need to deal with genuinely non-classical polynomials is the main new difficulty in this paper that was not dealt with in previous literature.

In our previous paper with Bergelson, a “weak” version of the above theorem was proven, in which the polynomial ${P}$ in the conclusion had bounded degree ${O_{s,p}(1)}$, rather than being of degree at most ${s}$. In the current paper, we use this weak inverse theorem to reduce the inverse conjecture to a statement purely about polynomials:

Theorem 2 (Inverse conjecture for polynomials) Let ${s \geq 0}$, and let ${P: V \rightarrow {\bf C}}$ be a non-classical polynomial of degree at most ${s+1}$ such that ${\|e(P)\|_{U^{s+1}(V)} \geq \delta > 0}$. Then ${P}$ has bounded rank in the sense that ${P}$ is a function of ${O_{s,p,\delta}(1)}$ polynomials of degree at most ${s}$.

This type of inverse theorem was first introduced by Bogdanov and Viola. The deduction of Theorem 1 from Theorem 2 and the weak inverse Gowers conjecture is fairly standard, so the main difficulty is to show Theorem 2.

The quantity ${-\log_{|{\bf F}|} \|e(P)\|_{U^{s+1}(V)}^{1/2^{s+1}}}$ of a polynomial ${P}$ of degree at most ${s+1}$ was denoted the analytic rank of ${P}$ by Gowers and Wolf. They observed that the analytic rank of ${P}$ was closely related to the rank of ${P}$, defined as the least number of degree ${s}$ polynomials needed to express ${P}$. For instance, in the quadratic case ${s=1}$ the two ranks are identical (in odd characteristic, at least). For general ${s}$, it was easy to see that bounded rank implied bounded analytic rank; Theorem 2 is the converse statement.

We tried a number of ways to show that bounded analytic rank implied bounded rank, in particular spending a lot of time on ergodic-theoretic approaches, but eventually we settled on a “brute force” approach that relies on classifying those polynomials of bounded analytic rank as precisely as possible. The argument splits up into establishing three separate facts:

1. (Classical case) If a classical polynomial has bounded analytic rank, then it has bounded rank.
2. (Multiplication by ${p}$) If a non-classical polynomial ${P}$ (of degree at most ${s+1}$) has bounded analytic rank, then ${pP}$ (which can be shown to have degree at most ${\max(s-p,0)}$) also has bounded analytic rank.
3. (Division by ${p}$) If ${Q}$ is a non-clsasical polynomial of degree ${\max(s-p,0)}$ of bounded rank, then there is a non-classical polynomial ${P}$ of degree at most ${s+1}$ of bounded rank such that ${pQ=P}$.

The multiplication by ${p}$ and division by ${p}$ facts allow one to easily extend the classical case of the theorem to the non-classical case of the theorem, basically because classical polynomials are the kernel of the multiplication-by-${p}$ homomorphism. Indeed, if ${P}$ is a non-classical polynomial of bounded analytic rank of the right degree, then the multiplication by ${p}$ claim tells us that ${pP}$ also has bounded analytic rank, which by an induction hypothesis implies that ${pP}$ has bounded rank. Applying the division by ${p}$ claim, we find a bounded rank polynomial ${P'}$ such that ${pP = pP'}$, thus ${P}$ differs from ${P'}$ by a classical polynomial, which necessarily has bounded analytic rank, hence bounded rank by the classical claim, and the claim follows.

Of the three claims, the multiplication-by-${p}$ claim is the easiest to prove using known results; after a bit of Fourier analysis, it turns out to follow more or less immediately from the multidimensional Szemerédi theorem over finite fields of Bergelson, Leibman, and McCutcheon (one can also use the density Hales-Jewett theorem here if one desires).

The next easiest claim is the classical case. Here, the idea is to analyse a degree ${s+1}$ classical polynomial ${P: V \rightarrow {\bf F}}$ via its derivative ${d^{s+1} P: V^{s+1} \rightarrow {\bf F}}$, defined by the formula

$\displaystyle d^{s+1} P( h_1,\ldots,h_{s+1}) := \partial_{h_1} \ldots \partial_{h_{s+1}} P(x)$

for any ${x,h_1,\ldots,h_{s+1} \in V}$ (the RHS is independent of ${x}$ as ${P}$ has degree ${s+1}$). This is a multilinear form, and if ${P}$ has bounded analytic rank, this form is biased (in the sense that the mean of ${e(d^{s+1} P)}$ is large). Applying a general equidistribution theorem of Kaufman and Lovett (based on this earlier paper of Green and myself) this implies that ${d^{s+1} P}$ is a function of a bounded number of multilinear forms of lower degree. Using some “regularity lemma” theory to clean up these forms so that they have good equidistribution properties, it is possible to understand exactly how the original multilinear form ${d^{s+1} P}$ depends on these lower degree forms; indeed, the description one eventually obtains is so explicit that one can write down by inspection another bounded rank polynomial ${Q}$ such that ${d^{s+1} P}$ is equal to ${d^{s+1} Q}$. Thus ${P}$ differs from the bounded rank polynomial ${Q}$ by a lower degree error, which is automatically of bounded rank also, and the claim follows.

The trickiest thing to establish is the division by ${p}$ claim. The polynomial ${Q}$ is some function ${F(R_1,\ldots,R_m)}$ of lower degree polynomials ${R_1,\ldots,R_m}$. Ideally, one would like to find a function ${F'(R_1,\ldots,R_m)}$ of the same polynomials with ${pF' = F}$, such that ${F'(R_1,\ldots,R_m)}$ has the correct degree; however, we have counterexamples that show that this is not always possible. (These counterexamples are the main obstruction to making the ergodic theory approach work: in ergodic theory, one is only allowed to work with “measurable” functions, which are roughly analogous in this context to functions of the indicated polynomials ${Q, R_1,\ldots,R_m}$ and their shifts.) To get around this we have to first apply a regularity lemma to place ${R_1,\ldots,R_m}$ in a suitably equidistributed form (although the fact that ${R_1,\ldots,R_m}$ may be non-classical leads to a rather messy and technical description of this equidistribution), and then we have to extend each ${R_j}$ to a higher degree polynomial ${R'_j}$ with ${pR'_j = R_j}$. There is a crucial “exact roots” property of polynomials that allows one to do this, with ${R'_j}$ having degree exactly ${p-1}$ higher than ${R_j}$. It turns out that it is possible to find a function ${P = F'(R'_1,\ldots,R'_m)}$ of these extended polynomials that have the right degree and which solves the required equation ${pP=Q}$; this is established by classifying completely all functions of the equidistributed polynomials ${R_1,\ldots,R_m}$ or ${R'_1,\ldots,R'_m}$ that are of a given degree.


text:
# Difference between revisions of "Metrizable implies monotonically normal"

This article gives the statement and possibly, proof, of an implication relation between two topological space properties. That is, it states that every topological space satisfying the first topological space property must also satisfy the second topological space property
View all topological space property implications | View all topological space property non-implications
|
Property "Page" (as page type) with input value "{{{stronger}}}" contains invalid characters or is incomplete and therefore can cause unexpected results during a query or annotation process.
Property "Page" (as page type) with input value "{{{weaker}}}" contains invalid characters or is incomplete and therefore can cause unexpected results during a query or annotation process.

## Statement

Any metrizable space is monotonically normal. In fact, we can construct an explicit monotone normality operator using the metric.

## Definitions used

### Metrizable space

Further information: Metrizable space

### Monotonically normal space

Further information: Monotonically normal space

## Proof

### Construction of the operator

Suppose $(X,d)$ is a metric space. We construct a monotone normality operator on $X$ as follows. For any two closed subsets $A$ and $B$ of $X$:

• For every $a \in A$, let $U_a$ be the open ball about $a$ of radius $d(a,B)/2$. Here, $d(a,B)$ is the infimum of the distances $d(a,b)$ for $b \in B$. Note that since $B$ is closed and $a \notin B$, $d(a,B) > 0$.
• Analogously, for every $b \in B$, define $V_b$ to be the open ball about $b$ of radius $d(A,b)/2$.

Then, the sets:

$U = \bigcup_{a \in A} U_a, \qquad V = \bigcup_{b \in B} V_b$

are the required disjoint open subsets.

### Proof of disjointness

The disjointness of $U$ and $V$ follows from the triangle inequality. It suffices to prove that for every $a \in A$ and $b \in B$, $U_a \cap V_b = \emptyset$. To see this, note:

$d(a,b) \ge d(a,B), \qquad d(a,b) \ge d(A,b)$

Thus:

$d(a,b) \ge d(a,B)/2 + d(A,b)/2$

This, along with the triangle inequality yields that the balls $U_a$ and $V_b$ cannot intersect.

### Proof of monotonicity

We need to show that if $A' \subseteq A$ and $B' \supseteq B$, then the open set about $A$ becomes smaller, and the open set about $B$ becomes larger. This is clear from the definitions, because $A'$ has fewer balls, and the radii of the balls also become smaller. Similarly $B'$ has more balls, and the radii of the balls also become larger.


text:
Data Model¶

Scenario data following the IAMC format¶

Over the past decade, the Integrated Assessment Modeling Consortium (IAMC) developed a standardised tabular timeseries format to exchange scenario data. Previous high-level use cases include reports by the Intergovernmental Panel on Climate Change (IPCC) and model comparison exercises within the Energy Modeling Forum (EMF) hosted by Stanford University.

The table below shows a typical example of integrated-assessment scenario data following the IAMC format from the CD-LINKS project. The pyam package is geared for analysis and visualization of any scenario data provided in this structure.

Illustrative example of IAMC-format timeseries data
via the IAMC 1.5°C Scenario Explorer ([1])

Refer to data.ene.iiasa.ac.at/database for more information on the IAMC format and a full list of previous use cases.

The variable column¶

The variable column implements a “semi-hierarchical” structure using the | character (pipe, not l or i) to indicate the depth.

Semi-hierarchical means that a hierarchy can be imposed, e.g., one can enforce that the sum of Emissions|CO2|Energy and Emissions|CO2|Other must be equal to Emissions|CO2 (if there are no other Emissions|CO2|… variables). However, this is not mandatory, e.g., the sum of Primary Energy|Coal, Primary Energy|Gas and Primary Energy|Fossil should not be equal to Primary Energy because this would double-count fossil fuels.

Refer to the variable list in the documentation pages of the IAMC 1.5°C Scenario Explorer to see the full list of variables used in the recent IPCC Special Report on Global Warming of 1.5 ºC (SR15).

The year column¶

In its original design, the IAMC data format (see above) assumed that the temporal dimension of any scenario data was restricted to full years represented as integer values.

Two additional use cases are currently supported by pyam in development mode (beta):

• using representative sub-annual timesteps

• using continuous time via pandas.datetime, replacing the name of the year column by time

Please reach out to the developers to get more information on this ongoing work.

The pyam.IamDataFrame class¶

A pyam.IamDataFrame instance is a wrapper for two pandas.DataFrame instances (read the docs):

• data: The data table is a dataframe containing the timeseries data in “long format”. It has the columns of the long data format ['model', 'scenario', 'region', 'unit', 'year', 'value'].

• meta: The meta table is a dataframe containing categorisation and descriptive indicators. It has the index pyam.META_IDX = ['model', 'scenario'].

The standard output format is the IAMC-style “wide format”, see the example above. This format can be accessed using pyam.IamDataFrame.timeseries(), which returns a pandas.DataFrame with the index pyam.IAMC_IDX = ['model', 'scenario', 'region', 'variable', 'unit'] and the years as columns.

Filtering¶

The pyam package provides two methods for filtering scenario data:

An existing class:IamDataFrame can be filtered using pyam.IamDataFrame.filter(col=...), where col can be any column of the data table (i.e., [‘model’, ‘scenario’, ‘region’, ‘unit’, ‘year’]) or any column of the meta table. The returned object is a new pyam.IamDataFrame instance.

A pandas.DataFrame with columns or index ['model', 'scenario'] can be filtered by any meta columns from a pyam.IamDataFrame using pyam.filter_by_meta(data, df, col=..., join_meta=False). The returned object is a pandas.DataFrame down-selected to those models-and-scenarios where the meta column satisfies the criteria given by col=... . Optionally, the meta columns are joined to the returned dataframe.

References¶

1

Daniel Huppmann, Elmar Kriegler, Volker Krey, Keywan Riahi, Joeri Rogelj, Katherine Calvin, Florian Humpenoeder, Alexander Popp, Steven K. Rose, John Weyant, and et al. IAMC 1.5 °C Scenario Explorer and Data hosted by IIASA (release 2.0). Integrated Assessment Modeling Consortium & International Institute for Applied Systems Analysis, 2019. URL: https://data.ene.iiasa.ac.at/iamc-1.5c-explorer, doi:10.5281/zenodo.3363345.


text:
# Homework Help: Contact forces homework problem

1. Oct 7, 2005

Hello,

I have a problem and I would like to check my answers:

A mass m1 rests on top of another mass m2 , which in turn rests on a frictionless horizontal surface. A light cord is attached to
m2 ,which is used to pull on it witha force F.

a) Find the acceleration ofeach object when the surface between the two objects is frictionless.
I found for m1 : a1 =0 ( since frictionless between the surface of the 2 objects)
For m2 : a2 =F/ m2

b) Find the acceleration of each object when the surface the two objects is rough enough to ensure that m1 does not slide on m2

I found for m1 : a1 = -f1 / m1 where f1 is the friction force due to the contact of the 2 masses.

For m2 = ( f1 + F) / m2

c) What are the magnitude and direction of the contact forces exerced by the lower object on the upper one assuming that the upper object is sliding on the lower object with a non zero coefficient of kinectic μk?

For this question isn't the same as the precedent question. we just replace
f1= μk * N?

B

2. Oct 7, 2005

### mezarashi

I think you have a typo there for the m2 part. Anyway, how I would solve it is:

F = (m1 + m2)a

Since the objects are one and whole, their accelerations are the same. No need to do separate calculations

This one doesn't even require the coefficient. The mass $$m_2$$ is on $$m_1$$, so undeniably, the force that is giving $$m_2$$ the acceleration forward is the frictional force. Thus, knowing it's acceleration from part b.

Ffric = Fm2 = m2 x a = μFn = μgm2

^_^

3. Oct 7, 2005

Thanks a lot mezarashi

4. Oct 7, 2005

### Staff: Mentor

You have the wrong sign for the friction force. The friction on m1 is in the same direction as the acceleration:
$$a_1 = f/m_1$$
$$a_2 = (F - f)/m_2$$
Of course, $a_1 = a_2 = a$, since the two blocks move together. You can solve for the acceleration.

Much easier is to realize that $a = F/(m_1 + m_2)$, as mezarashi suggested.

Last edited: Oct 7, 2005


text:
# Publications

The KAUST Visual Computing Center is placed consistently among the top academic research groups in Visual Computing (Vision, Graphics, and Visualization) worldwide. For example, csrankings.org, a publication-based ranking specific to Computer Science, rates KAUST as one of the top 10 university groups in these 3 areas since 2015.


text:
# Photoshop cs5 missing manual_9

Chia sẻ: Up Upload | Ngày: | Loại File: PDF | Số trang:36

0
52
lượt xem
12

## Photoshop cs5 missing manual_9

Mô tả tài liệu

Tham khảo tài liệu 'photoshop cs5 missing manual_9', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0)

Lưu

## Nội dung Text: Photoshop cs5 missing manual_9

2. Managing Actions Figure 18-6: Top: When you insert a stop, you can include instructions for the person running the action; you can type whatever you want. The message appears when that per- son triggers the action’s stop point. If you want to let folks continue with the action after they’ve preformed the step described by the message, turn on the Allow Continue checkbox. Bottom: Here’s what you see when you run the action and hit the stop point. Since a continue button wasn’t included, your only choice is to click Stop. After you’ve per- formed the part that couldn’t be recorded, click the Action panel’s Play button to finish the action. • Playback Options. If you can’t figure out where an action has gone haywire, you can make Photoshop play the action more slowly by selecting this command. In the resulting dialog box, you can choose Accelerated (normal speed), Step By Step (Photoshop completes each step and refreshes the screen before going to the next step), or “Pause For _ Seconds” (Photoshop pauses between each step for the number of seconds you specify). Editing Actions You can add, delete, or tweak an action’s steps anytime you’d like, as well as scoot them around within the Actions panel (just like Layers). To rearrange the actions in your Actions panel, just drag an action to a new position in the panel. When you see a highlighted line where you want it to go, release your mouse button. Rearranging actions is helpful when you want to keep certain actions together so they’re easier to spot (handy when you’re in Button mode [page 752]). You can also drag and drop steps within an action to rearrange them. To change an action’s settings (such as the feather amount), just double-click the relevant step while an image is open, enter a new amount in the resulting dialog box, and then click OK. Note: Clicking OK actually runs the command associated with the dialog box (feathering a selection, for example), but you can undo it by pressing �-Z (Ctrl+Z on a PC). Photoshop still remembers the new settings you entered and will use them the next time you run that action. Photoshop cs5: The Missing Manual 762
10. Noise Reducers These plug-ins range in price from $70 to$500, but don’t let that scare you; you can find tons of cheaper (and even free) offerings on the Web (though you may very well get what you pay for). Don’t be alarmed if you don’t see your favorite plug-in in the following list—it’s simply impossible to list them all here. FReQUeNtLY ASKed QUeStIoN Dude, Where’s My Plug-In? that case, if you’re on a PC you need to make sure you’ve Help! I don’t see my plug-in in the Filter menu. Did it load installed it into the right program folder (see the box on or what? page 6). If you’re on the Mac, check out the box on page 6 Peace, dear Grasshopper. You can find out whether your to learn how to launch Photoshop in 32-bit mode. plug-in loaded in a couple of ways. If you don’t get the “plug-in didn’t load” message and your When Photoshop encounters a plug-in that won’t load, it plug-in is still missing, take a peek in other menus, such presents you with a dialog box that says, “One or more as Select or File➝Automate to see if it ended up in there. plug-ins are currently not available on your system. For You can also look at the list of loaded plug-ins by choos- details, see Help➝System Info.” To see why the plug-in ing Photoshop➝About Plug-In (Help➝About Plug-In on didn’t load, choose Help➝System Info and scroll down a PC). Because so many Photoshop features are actually in the resulting dialog box until you see the plug-in in plug-ins (most filters, import and export commands, and question, along with Photoshop’s oh-so-brief explanation so on), the list is rather long, so you may need to scroll to of what went wrong. For example, if you try to learn why see if Photoshop loaded the one in question. the Variations adjustment (page 371) didn’t load in 64-bit If your plug-in is on the list but isn’t loading, about the mode, you’ll see the following line of text: “Variations NO only thing you can do is install a fresh copy of it or, better VERSION - 32-bit plug-in not supported in 64-bit - next to yet, see if a newer version is available from the developer’s the text: ‘Variations.plugin’.” website. Keep in mind that some plug-ins continue to work In CS5, if a plug-in doesn’t load, you’ve more likely than with newer versions of Photoshop, but some don’t. not encountered one that only works in 32-bit mode. In Note: For a comprehensive list of Photoshop plug-ins, visit www.adobe.com/products/plugins/photo- shop. And why, you might wonder, are some of them called “third-party” plug-ins? Because they’re made by someone other than Adobe! Noise Reducers If you’ve taken a photo in low light (in a dark restaurant, say), or if you set your cam- era to a high ISO (a setting that increases the camera’s sensitivity to light), chances are you’ve got a ton of noise—grainy-looking speckles—in your image. While you’ll find a couple of noise-reducing tricks in Chapter 11, if the image is really important, you should spring for a noise-reducing plug-in instead. Photoshop cs5: The Missing Manual 770
11. Noise Reducers Noiseware This plug-in has quickly become the noise reducer of choice for professional pho- tographers. Instead of blurring the whole image to make the noise less visible, Noise- ware analyzes the image and reduces noise only in the parts of the image that really need it. You also get a handy before-and-after view so you can see what it did. It’s available from www.imagenomic.com and costs around $50. Tip: You can often get plug-ins much cheaper if you buy them bundled together. Be sure to look for special deals on the developer’s website. Dfine This plug-in also reduces the noise in your image in a very simple and nondestruc- tive way. When you launch it and click its Measure button, Dfine scours your image for noise in areas without much detail (where noise is easiest to see). Start by trying the factory setting and then increase or decrease the noise-reduction level using the sliders (see Figure 19-2). When you find a setting you like, click OK to make Dfine make a copy of the currently selected layer and apply the noise reduction to the du- plicate instead of the original. Figure 19-2: Dfine’s handy split- screen view lets you see how much noise the plug-in removes from your image before you commit to the change. Here you see the original image on the left side of the red vertical line and the result on the right. Thanks to Nik Software’s amazing control points technology, Dfine lets you reduce noise in certain areas of your image without making a mask. It also figures out which kind of camera you used to take the photo and then applies the right amount of noise chapter 19: beyond photoshop: plug-ins 771 12. Making Selections and Masking reduction for your particular model (which makes sense because your camera is what introduced noise in the first place). You can buy Dfine for$100, but it’s cheaper if you buy it along with other Nik products, like Sharpener Pro, Color Efex Pro, Vi- veza, and more (www.niksoftware.com). Note: One nice thing about Nik Software’s plug-ins is that they all use the same window layout; so, once you learn how to use one, you can easily use ‘em all. Noise Ninja Long considered the gold standard of noise-reduction software (though the newer Noiseware may have changed that), photographers and newspapers have used this plug-in for years. It helps reduce noise (speckled imperfections) and grain (textured imperfections) while preserving details. It can tackle 16-bit images (see the box on page 45), do batch processing, and work as a Smart Filter (page 634). It’ll set you back about $80 (www.picturecode.com). Making Selections and Masking As you’ve learned in previous chapters, selecting stuff like hair and fur is really hard. Sure, you can learn some tricks, but a plug-in specifically designed for that task can make your life a heck of a lot easier and save you tons of time. That said, you’ll need a bit of patience when you start working with masking plug-ins because they’re not for the faint of heart. With practice, though, you can use them to create selections you just can’t make any other way. Note: Adobe put a lot of work into improving the Refine Edge command in Photoshop CS5. So before you plunk down cold hard cash on a masking plug-in, make sure you’re up to speed on the new enhance- ments discussed starting on page 166. Fluid Mask Fluid Mask is a powerful plug-in that helps make easier work of masking around complex areas like hair and fur. As soon as you open Fluid Mask, it analyzes your image and marks what it thinks are edges with blue lines (see Figure 19-3) so you can decide which edges you want to keep and which ones you want to zap and then create a cutout of your image to send back to Photoshop to use as a mask. You can also save your project and return to it later—a nice touch. Fluid Mask costs about$150 (www.vertustech.com). Photoshop cs5: The Missing Manual 772
13. Making Selections and Masking Figure 19-3: These blue lines mark the edges that Fluid Mask found in the image. If you use a combination of the plug-in’s tools (on the left), you can mark areas you want to keep and ones you want to throw away. Mask Pro Mask Pro helps you pick the precise colors you want to keep or remove as you build image masks. It gives you two eyedroppers to work with: Use one to select colors you want to keep and the other to select colors you want to throw away (see Figure 19-4). Then, you can use its Magic Brush to paint away the background while the program helps you along by referring to the Keep and Drop color palettes you made. Mask Pro can also extract partial color from a pixel, leaving you with a partially transparent pixel—important when you’re selecting hair or fur (the edges are so soft that they have to be partially see-through to blend in with a new background). You can also view the image in mask mode, which helps you see what the selection looks like because it’s displayed in shades of gray (just like a layer or channel mask). Mask Pro can work with 16-bit images and works as a Smart Filter though you have to turn the layer into a Smart Object first (see page 126); otherwise, the plug-in deletes the selected pixels as soon as you apply it. It costs around $160, though it’s cheaper if you buy it as part of a bundle (www.ononesoftware.com). Tip: When you install an onOne Software plug-in like Mask Pro, it shows up in the Filter menu and in a brand-new menu between Window and Help called “onOne”. chapter 19: beyond photoshop: plug-ins 773 14. Color Correction and Enhancement Figure 19-4: Because masking plug-ins are inherently complex, the folks who created Mask Pro help you get up to speed by including “Show Me How” videos and tips (shown here). Color Correction and Enhancement The plug-ins in this category can spruce up or fix the color in your images and produce a startling array of special effects while they’re at it. Read on for the scoop! Viveza As you’ve learned in previous chapters, before you adjust the color of a specific part of your image, you need to select it. Not so with Viveza. Since this plug-in made its debut in early 2008, it has revolutionized selective color and light adjustments. If you mark the areas you want to change with control points (the small gray circles shown in Figure 19-5), you can adjust the saturation, brightness, and contrast of those areas at warp speed. And Viveza performs its magic on a duplicate layer, so you don’t have to worry about it destroying your original image. It’s available from www.niksoft- ware.com and costs around$200. Color Efex Pro If you could buy just one plug-in, Color Efex Pro would be a darn good choice. Using the same control points as other Nik Software plug-ins, this one lets you selectively apply 52 enhancement filters and over 250 effects to your images—all nondestruc- tively. You can use them to enhance images in creative ways, as well as to fix color casts, smooth skin, and so on (see Figure 19-6). Drop as many control points as you want and use them to set the effect’s opacity in certain areas of your image or click the Brush button to paint the effect where you want it. The price ranges from $100 for 15 filters to$300 for all 52, and it’s available from www.niksoftware.com. Photoshop cs5: The Missing Manual 774
16. Color Correction and Enhancement Figure 19-6: Top: This split-screen preview shows you before and after versions of an image. This particular filter, called Bleach Bypass, creates a high- contrast grunge look. (If this look interests you, head over to page 778 and read about LucisArt Pro.) Bottom: The Glamour Glow filter gives the original image (left) a seriously dreamy look (right). But because Color Efex Pro applies the effect on another layer, you can always lower its opacity to blend it with the original. SkinTune, the other half of PhotoTune, is designed to produce accurate skin color based on the subject’s ethnicity. Just click a patch of skin and then select the person’s ethnicity from a pop-up menu (shown in Figure 19-8). SkinTune presents you with a row of color swatches similar to that particular skin tone; just click the one that looks best to you. It also zaps any color cast from the skin and removes the same cast from the rest of the photo. You can take a snapshot of your image and compare it with other versions produced with different settings, as well as save your settings and apply them to similar images later. Both ColorTune and SkinTune work as Smart Filters, but you have to convert your image layer to a Smart Object first (page 126). PhotoTune costs $160, and it’s available from www.ononesoftware.com. Photoshop cs5: The Missing Manual 776 17. Color Correction and Enhancement Figure 19-7: ColorTune asks you to pick the better of two images in a series of six steps. It’s by far the easiest way to color correct your images. Figure 19-8: After you choose your subject’s ethnicity, you can pick from a row of color swatches developed by the folks at onOne Software. They took countless photos of people and as- sembled their skin tones into a massive database of over 400,000 different skin types. That’s a lot of skin! chapter 19: beyond photoshop: plug-ins 777 18. Miscellaneous Plug-Ins PhotoTools This plug-in includes more than 150 photographic effects developed by the onOne team, as well as 100 extra effects from Photoshop guru Jack Davis and wedding photographer Kevin Kubota. PhotoTools helps you create beautiful portraits and vignettes, combine multiple effects into a layer mask, and more. You can export sev- eral versions of your image with different color profiles (page 48), which is handy if the result is headed to a printer or the Web. You can also apply a watermark (a par- tially transparent graphic) to your files to help protect them from copyright violators when you post them on the Web. This plug-in does its thing on its own brand-new layer so it’s nondestructive, and it can also batch-process images. The pro edition costs$260 and the standard edition, without the effects from Jack Davis and Kevin Kubota, costs $160 (unless you buy it as part of onOne’s Plug-In Suite). It’s available from www.ononesoftware.com. Miscellaneous Plug-Ins Most of the plug-ins covered in this section relate to specific tasks like enhancing detail, making enlargements, building websites, and so on, but some also alter color. LucisArt This plug-in has been around for many years and, while it’s popular in scientific and medical circles, it’s only recently begun to make a splash in the creative realm. Using a process originally developed to enhance details in images captured with electron microscopes, it brings out more detail from your image than you knew was there. Using only the luminance (lightness) info from your image, it enhances details with- out destroying highlights or shadows or shifting color (though you can control the color with a slider because you may want to shift the color a little). With this plug-in, you can vary your image in thousands of ways by tweaking just a couple of sliders, and although you could possibly reproduce some of these effects with Photoshop, you’d never know these possibilities existed if you didn’t use this software first. You can use this plug-in to tweak individual channels or work on the composite channel (page 189), and you can also blend the original back into the processed image using a slider. Figure 19-9 gives you a taste of what you can do with LucisArt. The pro version will set you back$595, but if you make your living work- ing with images, it’s money well spent; a light version that offers fewer settings and gives you limited control over mid-range contrast patterns and reducing scan lines is available for $280 for the Mac and$360 for PCs (www.lucisart.com). Photoshop cs5: The Missing Manual 778
20. Miscellaneous Plug-Ins choose from over 20 different film types to simulate the look and grain of real film, add tints, or burn the edges of your image. It works as a Smart Filter and costs about $200 (www.niksoftware.com). Figure 19-10: Silver Efex Pro, currently the most powerful black-and- white plug-in on the market, helps you create the look of black-and-white images captured on real film. If you want to add a little grain to your image, you can pick from several different options that look like real film grain. Genuine Fractals If you need to enlarge an image, this plug-in will save your bacon. It lets you create printable versions of even low-resolution images (like those made for the Web or captured with a low-quality setting on your digital camera). It can blow images up to over 1,000 percent to make honkin’ big panoramas, enlarge still frames from old videos to create higher-quality versions, and so on. It can scale any Photoshop docu- ment—even if it’s brimming with Smart Object layers (page 77), paths (page 26), or Type layers (page 76)—without losing resolution or harming the image’s quality. Just pick the pixels dimensions (if you know them), enter a percentage for the enlarge- ment, or enter the print size and resolution you want (page 243). If your image’s pro- portions don’t match those of the paper size you pick, Genuine Fractals offers you a cropping grid. It also batch-processes images. The pro version costs$300 and the standard version, without CMYK image support, runs \$160 (www.ononesoftware. com). Photoshop cs5: The Missing Manual 780


text:
## CCC '14 J2 - Vote Count

View as PDF

Points: 3
Time limit: 2.0s
Memory limit: 64M

Problem type
##### Canadian Computing Competition: 2014 Stage 1, Junior #2

A vote is held after singer A and singer B compete in the final round of a singing competition. Your job is to count the votes and determine the outcome.

#### Input Specification

The input will be two lines. The first line will contain , the total number of votes. The second line of input will be a sequence of characters, each of which will be A or B, representing the votes for a particular singer.

#### Output Specification

The output will be one of three possibilities:

• A, if there are more A votes than B votes;
• B, if there are more B votes than A votes;
• Tie, if there are an equal number of A votes and B votes.

#### Sample Input 1

6
ABBABB

#### Output for Sample Input 1

B

#### Sample Input 2

6
ABBABA

#### Output for Sample Input 2

Tie

• commented on Jan. 8, 2021, 2:40 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Feb. 26, 2021, 9:22 a.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Oct. 22, 2019, 6:09 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on May 26, 2021, 7:08 p.m.

But not everyone is as skilled as you

• commented on June 10, 2020, 10:02 a.m.

Thanks, no thanks :)

• commented on April 16, 2021, 4:59 p.m.

lol

• commented on Aug. 16, 2021, 10:21 p.m.

...


text:
# Zero Forcing and Electric Power Systems Presented on Capitol Hill

The AMS sponsored an exhibit on Zero Forcing and electric power systems at the 25th annual Coalition for National Science Funding (CNSF) Exhibition & Reception on Capitol Hill held April 30, 2019.  Professor Michael Young, Iowa State University, presented "Power Domination: How Zero Forcing is Used to Monitor an Electric Power Grid."

Dr. Young presented his work to Congressional representatives and other interested attendees by explaining:

"In our work to enhance efficiencies in our nation’s power grid, we employ tools from theoretical graph theory. To see how this works, we consider a graph with each vertex colored either blue or white. If a white vertex is adjacent to a blue vertex, and it is the only white vertex adjacent to that blue vertex, then the white vertex switches to blue. This process is referred to as the zero forcing. If the white vertices of a graph all turn blue under this process, then the beginning set of blue vertices is a zero forcing set of the graph.

Zero forcing can be used to determine where to place Phasor Measurement Units (PMUs) in an electric grid. These units measure voltage and current locally in a power grid and can be placed strategically to obtain measurements for the entire grid. More specifically, given the data that a PMU measures locally in a grid, Kirchhoff's law and Ohm's law allow for the entire grid to be measured if the PMUs form a power dominating set (meaning that these locations and their neighbors in the graph form a zero forcing set). According to the Department of Energy, the average overall cost per PMU in 2014 (cost for procurement, installation, and commissioning) ranged from \$40,000 to \$180,000. Thus, minimizing the number of PMUs installed is desirable."

The Coalition for National Science Funding (CNSF) is an alliance of over 130 organizations united by a concern for the future vitality of the national science, mathematics, and engineering enterprise. CNSF supports the goal of increased national support for the National Science Foundation's (NSF) research and education programs. The CNSF Exhibition is a well-attended annual event that features thirty-five exhibits where researchers present their work and explain the critical importance of sustained federal investments in basic scientific research.


text:
Elements
a1 = value of the first term
am = value of any term after the first term but before the last term
an = value of the last term
n = total number of terms
m = mth term after the first but before nth
d = common difference of arithmetic progression
r = common ratio of geometric progression
S = sum of the 1st n terms

## Arithmetic Progression, AP

Arithmetic progression is a sequence of numbers in which the difference of any two adjacent terms is constant. The constant difference is commonly known as common difference and is denoted by d. Examples of arithmetic progression are as follows:

Example 1: 3, 8, 13, 18, 23, 28 33, 38, 43, 48
The above sequence of numbers is composed of n = 10 terms (or elements). The first term a1 = 3, and the last term an = a10 = 48. The common difference of the above AP is d = 8 - 3 = 13 - 8 = ... = 5.

Example 2: 5, 2, -1, ...
This AP has a common difference of -3 and is composed of infinite number of terms as indicated by the three ellipses at the end.

### Formulas for Arithmetic Progression

Common difference, d
The common difference can be found by subtracting any two adjacent terms.

$d = a_{m + 1} - a_m$   or

$d = a_2 - a_1 = a_3 - a_2 = a_4 - a_3 = ...$

Value of each term
Each term after the first can be found by adding recursively the common difference d to the preceding term.

$a_{m + 1} = a_m + d$

nth term of AP
The nth term of arithmetic progression is given by

$a_n = a_1 + (n - 1)d$

or in more general term, it can be written as

$a_n = a_m + (n - m)d$

Sum of n terms of AP
The sum of the first n terms of arithmetic progression is n times the average of the first term and the last term.

$S = \dfrac{n}{2}(a_1 + a_n)$

If the last term an is not given, the following may be useful

$S = \dfrac{n}{2}[ \, 2a_1 + (n - 1)d \, ]$

If required for the partial sum from mth to nth terms, the following formula can be used

$S = \dfrac{n - m + 1}{2}(a_m + a_n)$   or   $S = \dfrac{n - m + 1}{2} [ \, 2a_m + (n - m)d \, ]$

## Geometric Progression, GP

Geometric progression is a sequence of numbers in which any two adjacent terms has a common ratio denoted by r. Example of geometric progression is

1, 3, 9, 27, ...

which is composed of infinite number of terms and with common ratio equal to 3.

### Formulas for Geometric Progression

Common ratio
The common ratio can be found by taking the quotient of any two adjacent terms.

$r = \dfrac{a_{m + 1}}{a_m} = \dfrac{a_2}{a_1} = \dfrac{a_3}{a_2} = \dfrac{a_4}{a_3} = ...$

nth term of GP
The nth term of the geometric progression is given by

$a_n = a_1 \, r^{n - 1}$   or   $a_n = a_m \, r^{n - m}$

Sum of n terms of GP
The sum of the first n terms of geometric progression is

$S = \dfrac{a_1(1 - r^n)}{1 - r}$

Sum of Infinite Geometric Progression
A finite sum can be obtained from GP with infinite terms if and only if -1.0 ≤ r ≤ 1.0 and r ≠ 0.

$S = \dfrac{a_1}{1 - r}$

## Harmonic Progression, HP

Harmonic progression is a sequence of numbers in which the reciprocals of the elements are in arithmetic progression. Example of harmonic progression is

1/3, 1/6, 1/9, ...

If you take the reciprocal of each term from the above HP, the sequence will become

3, 6, 9, ...

which is an AP with a common difference of 3.

Another example of HP is 6, 3, 2. The reciprocals of each term are 1/6, 1/3, 1/2 which is an AP with a common difference of 1/6.

To find the term of HP, convert the sequence into AP then do the calculations using the AP formulas. Then take the reciprocal of the answer in AP to get the correct term in HP.

## Relationship between arithmetic, geometric, and harmonic means

$AM \times HM = GM^2$


text:
Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+
 Title Keywords Abstract Author All
Search Results: 1 - 10 of 100 matches for " "
 Page 1 /100 Display every page 5 10 20 Item
 PLOS Computational Biology , 2011, DOI: 10.1371/journal.pcbi.1002151 Abstract: Although doxorubicin toxicity in cancer cells is multifactorial, the enzymatic bioactivation of the drug can significantly contribute to its cytotoxicity. Previous research has identified most of the components that comprise the doxorubicin bioactivation network; however, adaptation of the network to changes in doxorubicin treatment or to patient-specific changes in network components is much less understood. To investigate the properties of the coupled reduction/oxidation reactions of the doxorubicin bioactivation network, we analyzed metabolic differences between two patient-derived acute lymphoblastic leukemia (ALL) cell lines exhibiting varied doxorubicin sensitivities. We developed computational models that accurately predicted doxorubicin bioactivation in both ALL cell lines at high and low doxorubicin concentrations. Oxygen-dependent redox cycling promoted superoxide accumulation while NADPH-dependent reductive conversion promoted semiquinone doxorubicin. This fundamental switch in control is observed between doxorubicin sensitive and insensitive ALL cells and between high and low doxorubicin concentrations. We demonstrate that pharmacological intervention strategies can be employed to either enhance or impede doxorubicin cytotoxicity in ALL cells due to the switching that occurs between oxygen-dependent superoxide generation and NADPH-dependent doxorubicin semiquinone formation.
 Essa Ebtessam Asian Journal of Pharmaceutics , 2010, Abstract: In the last two decades, there was an extensive research focused on the study of synthetic amphiphilic vesicles, prepared by nonionic surfactants (niosomes). The particle size of these vesicles is critical for their intended therapeutic benefits. Formulation and processing factors affect greatly the physical characteristics of the resulted nanosystems. Therefore, the present work was adopted to investigate how proper manipulation of various formulations and processing factors on vesicular Z-average particle size. The selected variables were membrane additives, [including cholesterol (CHO), dicetylphosphate (DCP) and stearylamine (SA)], sonication time as well as drug loading factor (using mannitol and estradiol). Sorbitan monopalmitate (span 40) niosomes were prepared by the conventional thin film hydration method. Particle size, measured by Photon Correlation Spectroscopy, and polydispersity indices were measured and compared. The results indicated that CHO increased the vesicular size, with 2:1 and 1:1 (span 40:CHO) ratios showing the same size. Sonication reduced the vesicle size by 23, 35 and 42% after 10, 20 and 30 min, respectively. After 30 min, the effect of sonication was minor. The addition of charge inducing agents changed the zeta potential depending on the type of the additives. Surface charge increased the size by 24 and 11% when using DCP and SA, respectively. Drug incorporation increased the vesicle size to an extent based on its aqueous solubility. There were about 35 and 6.2% increase in vesicular size for estradiol and mannitol, respectively, supporting the partitioning of lipophilic drug within the fatty acyl side chains of the bilayer membrane.
 Orbital : the Electronic Journal of Chemistry , 2009, Abstract: The influence of the fat chain length of sorbitan surfactant was systematically explored, especially its influence on the material pore size. Then, mesoporous silica was synthesized according to a two-step process that provides intermediary stable hybrid micelles using ethoxylated derivative of fatty esters of sorbitan surfactants as the directing-structure agent and tetraethyl orthosilicate Si(OEt)4 as the silica source. Finally, the materials’ porosity could be controlled by adjusting the preparation parameters during the two steps synthesis of mesoporous silica.
 BMC Cancer , 2012, DOI: 10.1186/1471-2407-12-381 Abstract: Background Since proteins involved in chemotherapy drug pharmacokinetics and pharmacodynamics have a strong impact on the uptake, metabolism, and efflux of such drugs, they likely play critical roles in resistance to chemotherapy drugs in cancer patients. Methods To investigate this hypothesis, we conducted a whole genome microarray study to identify difference in the expression of genes between isogenic doxorubicin-sensitive and doxorubicin-resistant MCF-7 breast tumour cells. We then assessed the degree of over-representation of doxorubicin pharmacokinetic and pharmacodynamic genes in the dataset of doxorubicin resistance genes. Results Of 27,958 Entrez genes on the array, 7.4 per cent or 2,063 genes were differentially expressed by ≥ 2-fold between wildtype and doxorubicin-resistant cells. The false discovery rate was set at 0.01 and the minimum p value for significance for any gene within the “hit list” was 0.01. Seventeen and 43 per cent of doxorubicin pharmacokinetic genes were over-represented in the hit list, depending upon whether the gene name was identical or within the same gene family, respectively. The most over-represented genes were within the 1C and 1B families of aldo-keto reductases (AKRs), which convert doxorubicin to doxorubicinol. Other genes convert doxorubicin to other metabolites or affect the influx, efflux, or cytotoxicity of the drug. In further support of the role of AKRs in doxorubicin resistance, we observed that, in comparison to doxorubicin, doxorubincol exhibited dramatically reduced cytotoxicity, reduced DNA-binding activity, and strong localization to extra nuclear lysosomes. Pharmacologic inhibition of the above AKRs in doxorubicin-resistant cells increased cellular doxorubicin levels, restored doxorubicin cytotoxicity and re-established doxorubicin localization to the nucleus. The properties of doxorubicinol were unaffected. Conclusions These findings demonstrate the utility of using curated pharmacokinetic and pharmacodynamic knowledge bases to identify highly relevant genes associated with doxorubicin resistance. The induction of one or more of these genes was found to be correlated with changes in the drug’s properties, while inhibiting one specific class of these genes (the AKRs) increased cellular doxorubicin content and restored drug DNA binding, cytotoxicity, and subcellular localization.
 Theranostics , 2012, Abstract: Cholesterol plays a critical role in liposome composition. It has great impact on the behavior of liposome in vitro and in vivo. In order to verify the possible effects from cholesterol charge, surface shielding and chemical nature, two catalogs of liposomes with charged and PEGylated cholesterols were synthesized. Anionic liposomes (AL) and cationic liposomes (CL) were prepared, with charges from hemisuccinate and lysine in cholesterol derivatives, respectively. Characteristics of different formulated liposomes were investigated after doxorubicin encapsulation, using neutral liposomes (NL) as control. Results showed that after PEGylation, AL and CL liposomes displayed prolonged retention release profile, while kept similar size distribution, encapsulation efficiency, low cytotoxicity and hemolysis comparing with NL. Confocal laser scanning microscopy and flow cytometry experiments confirmed the significantly higher cell uptake from AL and CL vesicles than the NL in mouse breast carcinoma and melanoma cells, human epithelial carcinoma and hepatoma cells. It was in accordance with our corresponding cellular mortality studies of DOX-loaded liposomes. The in vivo anti-tumor effect experiments from charged liposomes also presented much higher tumor inhibition effect (70% vs 45%, p < 0.05) than NL liposomes. This is the first time reporting anti-cancer effect from charged cholesterol liposome with/without PEGylation. It may give deeper understanding on the liposome formulation which is critical for liposome associated drug research and development.
 Journal of Systems Chemistry , 2011, DOI: 10.1186/1759-2208-2-4 Abstract: Vesicles are bilayer membrane structures that encapsulate an internal aqueous compartment. Fatty acid vesicles have been studied as models of primitive cell membranes at the origin of life [1-7], and phospholipid vesicles (liposomes) have been widely studied as models of modern cell and organelle membranes [8,9] and as drug delivery vehicles [10-12]. We first observed the phenomenon of "exploding vesicles" during microscopic observations of large (approximately 4 μm in diameter) oleate vesicles containing 10 mM HPTS (8-hydroxypyrene-1,3,6-trisulfonic acid trisodium salt, a water-soluble, membrane-impermeable fluorescent dye), in 0.2 M Na-bicine buffer, pH 8.5. The vesicles were prepared by extrusion and dialysis, so that the fluorescent dye was present only inside the vesicles while the buffer was present in both inner and outer solutions [13]. To our surprise, we observed that these vesicles suddenly exploded shortly (approximately 0.5 sec) after being exposed to intense illumination from a metal halide lamp (estimated irradiance 2.5 W/mm2), and released their encapsulated dye along with smaller internal vesicles (Figure 1A; Additional File 1 Figure S1; Additional File 2). The actual vesicle rupture appeared to take place in < 2 ms (3 frames in a recording from a high-speed camera: Additional File 3); this estimate is an upper limit because of the time required for diffusion of the released dye away from the vesicle. We observed similar vesicle explosions using vesicles containing different internal fluorescent dyes, such as calcein and Rose Bengal (a photodynamic therapy drug).To distinguish between physical rupture and rapid permeabilization of the vesicle membrane, we labeled the vesicles with a membrane-localized dye (Rh-DHPE, Lissamine rhodamine B 1,2-dihexadecanoyl-sn-glycero-3-phosphoethanolamine). Upon illumination, we observed that the vesicle membrane burst open on one side and then quickly recoiled (Figure 1B; Additional File 4). When using slightly lowe
 Hiroshi Noguchi Physics , 2002, DOI: 10.1103/PhysRevE.67.041901 Abstract: Polyhedral vesicles with a large bending modulus of the membrane such as the gel phase lipid membrane were studied using a Brownian dynamics simulation. The vesicles exhibit various polyhedral morphologies such as tetrahedron and cube shapes. We clarified two types of line defects on the edges of the polyhedrons: cracks of both monolayers at the spontaneous curvature of monolayer $C_{\text {0}}<0$, and a crack of the inner monolayer at $C_{\text {0}}\ge0$. Around the latter defect, the inner monolayer curves positively. Our results suggested that the polyhedral morphology is controlled by $C_{\text {0}}$.
 Interdisciplinary Toxicology , 2008, DOI: 10.2478/v10102-010-0036-9 Abstract: Ellipticine is an antineoplastic agent, whose mode of action is based mainly on DNA intercalation, inhibition of topoisomerase II and formation of covalent DNA adducts mediated by cytochromes P450 and peroxidases. Here, the cytotoxicity of ellipticine to human neuroblastoma derived cell lines IMR-32 and UKF-NB-4 was investigated. Treatment of neuroblastoma cells with ellipticine was compared with that of these cancer cells with doxorubicin. The toxicity of ellipticine was essentially the same as that of doxorubicin to UKF-NB-4 cells, but doxorubicin is much more effective to inhibit the growth of the IMR-32 cell line than ellipticine. Hypoxic conditions used for the cell cultivation resulted in a decrease in ellipticine and/or doxorubicin toxicity to IMR-32 and UKF-NB-4 neuroblastoma cells.
 International Journal of Pharmacology , 2008, Abstract: The aim of this study is the evaluation of the effect of one group of surfactants including polyethylene glycol sorbitan esters (Tweens: 20, 40, 60 and 80) on Red Blood Cells (RBC) as a model for biological membranes. Also in this study some of physicochemical properties including Emulsification index (E24) and Foam producing activity (Fh) were studied. In this study the hemolytic effect of four surfactants from Tween category were evaluated. Surfactants solutions were prepared in McIvan`s buffer in specific concentration. 0.2 mL of RBC was mixed with 0.2 mL of one of surfactants solution incubated in four different temperatures for two different times. The absorbance of the samples was determined by UV spectrophotometer. Each test was done nine times. The results were shown by mean±SD. E24 and Fh were also determined for each surfactant solutions. In comparison of the four studied surfactants, Tween 20 have the highest hemolytic effect and the Tween 80 is the lowest one. The values of E24 and Fh have good correlation with Hydrophilic-Lipophilic Balance (HLB) values. Increasing in HLB value lead to increasing in those parameters.
 Journal of Biological Sciences , 2009, Abstract: The aim of this study is to investigate the effect of one group of surfactants including sorbitan esters (span 20, 40, 60 and 80) on biologic membrane by using human red blood cells as a model. In this study, the hemolytic effect of four surfactants from span category were evaluated. Surfactants solution were prepared in Mclvane’s buffer in specific concentration. Red blood cells were mixed with surfactants solution incubated in three different time and three temperature. The UV absorbances of the samples were determined by UV spectrophotometer. Each test was done in 9 times. Emulsification index, foam producing activity, also determined for each surfactant solution. The results showed that these agents had hemolytic effects. Span 20 caused more hemolysis and membrane demolishing effect than the others. Their hemolysis effects were enhanced by increasing temperature and time of incubation. According to hemolysis results, foam activity test and E24, the interaction between span 80 and biological membrane is the least and it means has least toxic effect on cells. Anyway because these agents are used as excipients in pharmaceutical preparations, their membrane toxic effect should be considered.
 Page 1 /100 Display every page 5 10 20 Item


text:
# Finding a proper sequence

The following function was given to me $$f(x)=\lfloor x\rfloor+\lfloor-x\rfloor$$

wherein $\lfloor x\rfloor$ is the floor function of $x$. I was asked to select a proper sequence for showing that this function has no limit at $\infty$.

Honestly, my knowledge about analysis is weak. Thank you

-

Take $$f(n)=[n]+[-n]=n-n=0, \quad n\in\mathbb{N},$$ and then take $$f\left(\frac{2n+1}{2}\right)=n+(-n-1)=-1, \quad n\in\mathbb N$$
Then you have two different sequences with different limits when $\,n\to\infty\,$ and thus the limit at $\,\infty\,$ doesn't exist.
So, according to your selected sequences, can we say if Limit$_{x\rightarrow\infty}a_n=\infty$ and $\{f(a_n)\}$ is convergent, we have Limit$_{x\rightarrow\infty}f(x)$ undefined? – Babak S. Jun 24 '12 at 11:02


text:
Contest

SIMPLE

Greedy

# PROBLEM:

Given an array B of length N. Find an array A of length N such that the number of distinct elements A_i\mod B_i\ \forall i\in \{1,2,\dots,N\} is maximised.

# EXPLANATION:

Observation: If A_i\ge B_i in the final array A, we can replace A_i with A_i\mod B_i without changing the score.

Therefore, we can only consider A_i\in \{0,1,\dots,B_i-1\} for all valid i. Then, the problem is reduced to finding an array A such that 0\le A_i<B_i and the number of distinct elements in A is maximised.

Intuition for the solution

Consider an example B=[1,7,2, 3, 2].

The set of possible values for each A_i is as follows:

• A_1=\{0\}
• A_2=\{0,1,2,3,4,5,6\}
• A_3=\{0,1\}
• A_4=\{0,1,2\}
• A_5=\{0,1\}

You want to select exactly one element from each set, such that the number of distinct elements is maximised. This can be remodelled equivalently as a simpler version of this classical problem (solution can be found here), which motivates the greedy solution!

We proceed greedily.

Generate the permutation array C of length N such that, B_{C_i}\le B_{C_{i+1}} for all valid i. This can be accomplished easily using a sorting algorithm.
Iterate over this array C; let the current index be i.

• If cnt < B_{C_i}, set A_{C_i} to cnt and increase cnt by 1.
• Else, we may set A_{C_i} to any valid value, since it doesn’t contribute to the total score. The value of cnt is not updated in this case.

It is trivial to deduce that, the number of distinct elements in A at the end is equal to the final value of cnt.

The proof of optimality is similar to the proof linked in the spoiler above, and is left to the reader as an exercise.

# TIME COMPLEXITY:

Generating the array C takes O(N\log N) with sorting. Since we iterate once over C to compute the answer, the total time complexity is thus

O(N\log N+N)\approx O(N\log N)

per test case.

# SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

• 1
• 2
• 3
• 4
• 5

0 voters

1 Like

Why don’t I print C array as output it also contains most no of unique elements possible

Because (C_i \mod B_i) is not guaranteed to be equal to C_i.
C is just an implementation detail to ease my explanation. My solution code doesn’t utilise it at all, and instead sorts an array of pairs (B_i,i) to compute the answer.

why did my solution Solution:52472444 (O(n)) give tle ?

Try to benchmark your solution with a T=10^5, N=10 max constraints testcase. It initializes a gigantic array of vectors on each iteration and this is very slow when T is large:

    while(t)
{t--;
vector<long int> v[200001];
}

can anyone tell me what is wrong with my code Solution: 52864812 | CodeChef

In the following loop

    for(int i=n-1;i>=0;i--){
if(p>0){
p--;
int ind=b[i].second;
a[ind]=p;
}
}

the value of p may be actually larger or equal to b[i].first and this is problematic.

T=int(input())
def list_to_str(l):
pattern=""
for x in l:
pattern+=str(x)+" "
print(pattern)
for _ in range(T):
n=int(input())
l1=list(map(int,input().split()))
l2=[]
l1.sort()
for x in l1:
for i in range(x):
if l2.count(i)==0:
l2.append(i)
break
else:
l2.append(0)
list_to_str(l2)
Can someone please tell where I am going wrong.

Can somebody please tell me why is my code getting tle?
Solution: 53354084 | CodeChef

Solved! I had to define my pair array outside of int main !