text:
# Mixed Strategy May Outperform Pure Strategy: An Initial Study

In pure strategy meta-heuristics, only one search strategy is applied for all time. In mixed strategy meta-heuristics, each time one search strategy is chosen from a strategy pool with a probability and then is applied. An example is classical genetic algorithms, where either a mutation or crossover operator is chosen with a probability each time. The aim of this paper is to compare the performance between mixed strategy and pure strategy meta-heuristic algorithms. First an experimental study is implemented and results demonstrate that mixed strategy evolutionary algorithms may outperform pure strategy evolutionary algorithms on the 0-1 knapsack problem in up to 77.8 Complementary Strategy Theorem is rigorously proven for applying mixed strategy at the population level. The theorem asserts that given two meta-heuristic algorithms where one uses pure strategy 1 and another uses pure strategy 2, the condition of pure strategy 2 being complementary to pure strategy 1 is sufficient and necessary if there exists a mixed strategy meta-heuristics derived from these two pure strategies and its expected number of generations to find an optimal solution is no more than that of using pure strategy 1 for any initial population, and less than that of using pure strategy 1 for some initial population.

## Authors

• 50 publications
• 4 publications
• 3 publications
• 4 publications
12/07/2011

### Pure Strategy or Mixed Strategy?

Mixed strategy EAs aim to integrate several mutation operators into a si...
03/01/2018

### Algorithm for Evolutionarily Stable Strategies Against Pure Mutations

Evolutionarily stable strategy (ESS) is an important solution concept in...
06/15/2014

### A Heuristic Method to Generate Better Initial Population for Evolutionary Methods

Initial population plays an important role in heuristic algorithms such ...
02/25/2019

### Pure Strategy Best Responses to Mixed Strategies in Repeated Games

Repeated games are difficult to analyze, especially when agents play mix...
08/21/1998

### Chess Pure Strategies are Probably Chaotic

It is odd that chess grandmasters often disagree in their analysis of po...
07/02/2019

### Evolving the Hearthstone Meta

Balancing an ever growing strategic game of high complexity, such as Hea...
02/12/2022

### Stochastic Strategic Patient Buyers: Revenue maximization using posted prices

We consider a seller faced with buyers which have the ability to delay t...
##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

In the last three decades, metaheuristics have been widely applied in solving combinatorial optimisation problems [1, 2]. Metaheuristics include, but are not restricted to, Ant Colony Optimization (ACO), Genetic Algorithms (GA), Iterated Local Search (ILS), Simulated Annealing (SA), and Tabu Search (TS) [3]. Different search strategies have been developed in these metaheuristics. Each search strategy has its own advantage. Therefore it is a natural idea to combine the advantages of several search strategies together. This leads to hybrid metaheuristics [4] such as hyper-heuristic [5] and memetic algorithm [6].

Mixed strategy metaheuristics [7]

belong to the family of hybrid metaheuristics. They are inspired from the game theory

[8]. A pure strategy metaheuristic is one that applies the same search method at each generation of the algorithm. A mixed strategy metaheuristic is one that selects a search method probabilistically from a set of strategies at each generation. For example, a search strategy may be mutation or crossover. Thus a classical genetic algorithm, that applies mutation with probability 0.9 and crossover with probability 0.1, belong to mixed strategy heuristics. A (1+1) evolutionary algorithm using mutation but no crossover is a pure strategy metaheuristic. Previously mixed strategy evolutionary programming, integrating several mutation operators, has been designed for numerical optimization [9]. Experimental results show that mixed strategy evolutionary programming outperforms pure strategy evolutionary programming with a single mutation operator [10].

The first goal of this paper is to conduct an empirical comparison of the performance between mixed strategy and pure strategy evolutionary algorithms (EAs for short) on the 0-1 knapsack problem. Here the performance is measured by the best fitness value found in 500 generations. In experiments, two novel mixed strategy EAs are proposed to solve the 0-1 knapsack problem.

The second but more important goal is to provide a theoretical answer to the question: when do mixed strategy metaheuristics outperform pure strategy metaheuristics? In theoretical analysis, the performance of a metaheuristic is measured by the expected number of total fitness evaluations to find an optimal solution (called the expected runtime).

Despite the popularity of hybrid metaheuristics in practice, the theoretic work on hybrid metaheuristics is very limited [11]. One result is based on the asymptotic convergence rate [12]. The asymptotic convergence rate is how fast an iteration algorithm converge to the solution per iteration [13]. It is proven in [12] that any mixed strategy (1+1) EA (consisting of several mutation operators) performs no worse than the worst pure strategy EA (using a single mutation operator). If mutation operators are mutually complementary, then it is possible to design a mixed strategy (1+1) EA better than the best pure strategy (1+1) EA.

Another result is based on the runtime analysis of selection hyper-heuristics [11]. It shows that mixing different neighbourhood or move acceptance operators can be more efficient than using stand-alone individual operators in some cases. But the discussion is restricted to simple (1+1) EAs for simple problems such as the OneMax and GapPath functions.

This paper is different from our previous work [12] in two points. The expected runtime is employed to theoretically measure the performance of metaheuristics, while the asymptotic convergence rate is used in [12]. The current paper discuss population-based metaheuristics while [12] only analysed (1+1) EAs.

The rest of this paper is organized as follows. Section 2 gives experimental results that show mixed strategy may outperform pure strategy. Section 3 provides the sufficient and necessary condition when mixed strategy may outperform pure strategy in general. Section 4 concludes the paper.

## 2 Evidence from Experiment: Mixed Strategy May Outperform Pure Strategy

This section conducts an empirical comparison of the performance between mixed strategy EAs and pure strategies EAs. A classical NP-hard problem, the 0-1 knapsack problem [14], is used in the empirical study.

### 2.1 Evolutionary Algorithms for the 0-1 Knapsack Problem

The 0-1 knapsack problem is described as follows:

 maximize ∑ni=1vixi,subject to ∑ni=1wixi≤C,

where is the value of item , the weight of item , and the knapsack capacity.

 xi={1if item i is selected in the knapsack,0otherwise.

A solution is represented by a vector (a binary string)

. If a solution violates the constraint, then it is called infeasible. Otherwise it is called feasible.

There are several ways to handle the constrains in the knapsack problem [15]. The method of repairing infeasible solutions is used in the paper since it is more efficient than other methods [16]. Its idea is simple: if an infeasible solution is generated, then it will be repaired to a feasible solution. The repairing procedure is described as follows:

input ;
if  then
is infeasible;
while ( is infeasible) do
select an item from the knapsack;
set ;
if  then
is feasible;
end if
end while
end if
output .

There are different select methods in the repairing procedure. Two of them are described as follows.

1. Random repair: select an item from the knapsack at random and remove it from the knapsack.

2. Greedy repairing: sort all items according to the order of the ratio , then select the item with the smallest ratio and remove it from the knapsack.

The fitness function is defined as

 f(→x)=n∑i=1xivi, if →x is feasible,

Thanks to the repairing method, no need to define the fitness for infeasible solutions.

A pure strategy EA for solving the 0-1 knapsack problem is described as follows.

input a fitness function;
generation counter ;
initialize population ;
an archive keeps the best solution in ;
while  is less than a threshold do
children population mutated from ;
if a child is an infeasible solution then
then repair it into a feasible solution;
end if
new population selected from ;
update the archive if the best solution in is better than it;
;
end while
output the maximum of the fitness function.

A mixed strategy EA for solving the 0-1 knapsack problem is almost the same as the above algorithm, except one place:

choose a mutation operator probabilistically;
children population children mutated from .

The description of mutation operators is given in the next subsection. The selection operator is the same in pure strategy and mixed strategy EAs. A mixed strategy then means a probability distribution of choosing mutation operators.

### 2.2 Pure Strategy and Mixed Strategy Evolutionary Algorithms

Four pure strategy EAs are constructed based on four different mutation operators. The first mutation operator is standard bitwise mutation. It is independent on the 0-1 knapsack problem. The related EA is denoted by PSb.

• Bitwise Mutation. Flip each bit to with probability .

The second mutation operator is problem-specific. It is based on heuristic knowledge: an item with a bigger value is more likely to appear in the knapsack. The related EA is denoted by PSv.

• Mutation based on values. If a bit , then flip it to with probability

 vi∑nj=1vj. (1)

If a bit , then flip it to with probability

 1/vi∑nj=11/vj. (2)

The third mutation operator is based on heuristic knowledge too: an item with a smaller weight is more likely to appear in the knapsack. The corresponding EA is denoted by PSw.

• Mutation based on weights. If a bit , then flip it to with probability

 1/wi∑nj=11/wj. (3)

If a bit , then flip it to with probability

 wi∑nj=1wj. (4)

The fourth mutation operator is constructed from heuristics knowledge: first calculate the ratio between the value and weight for each item:

 ri=viwi. (5)

Then an item with a bigger ratio is more likely to appear in the knapsack. The related EA is denoted by PSr.

• Mutation based on the ratio between value and weight. If a bit , then flip it to with probability

 ri∑nj=1rj. (6)

If a bit , then flip it to with probability

 1/ri∑nj=11/rj. (7)

Two novel mixed strategy EAs are designed in the experiments. One is to set a fixed probability distribution of choosing mutation operators for all generations. The algorithm is called static, denoted by MSs.

• statically mixed strategy: choose each mutation operator based on a fixed probability, for example, for the four pure strategies.

The other is to dynamically adjust the probability distribution of choosing mutation operators. If a better solution is generated by applying a mutation operator this generation, then the operator will be chosen with a higher probability. This kind of mixed strategy EAs is called dynamic, denoted by MSd.

• dynamically mixed strategy: The updating procedure of the mixed strategy is the same as that in [9]. For each individual in population , update its mixed strategy as follows. If the individual’s parent generates a child via mutation PS and the child is selected into population , then assign the probabilities of choosing mutation PS and other mutation PS’ to be

 Pt+1(PS)=Pt(PS)+1−Pt(PS)4,Pt+1(PS′)=Pt(PS′)−Pt(PS′)4,PS′≠PS,

Otherwise assign

 Pt+1(PS)=Pt(PS)−Pt(PS)4,Pt+1(PS′)=Pt(PS′)+1−Pt(PS′)4,PS′≠PS,

### 2.3 Experiments

Experiments are conducted on different types of instances of the 0-1 knapsack problem. According to the correlation between values and weights, the instances of the problem are classified into three types

[14, 15]: given two positive parameters and ,

1. uncorrelated knapsack: and uniformly random in ;

2. weakly correlated knapsack: uniformly random in ; and uniformly random in (if for some , , then the random generation procedure should be repeated until );

3. strongly correlated knapsack: uniformly random in ; and ;

In the experiments, and are set to be and .

Based on the capacity, the instances of the knapsack problem are classified into two types [14, 15]:

1. restrictive capacity knapsack: the knapsack capacity is small, where

2. average capacity knapsack: the knapsack capacity is large, where

Hence we will compare two mixed strategy EAs and four pure strategy EAs on six different types of instances below:

1. uncorrelated and restrictive capacity knapsack,

2. weakly correlated and restrictive capacity knapsack,

3. strongly correlated and restrictive capacity knapsack,

4. uncorrelated correlated and average capacity knapsack,

5. weakly correlated and average capacity knapsack,

6. strongly correlated and restrictive average capacity knapsack.

Furthermore the experiments are split into two groups based on the repairing method: (1) greedy repair, (2) random repair.

The experiment setting is described as follows. For each type of the 0-1 knapsack problem, three instances with 100, 250 and 500 items are generated at random. The population size is set to 10. The maximum of generations is 500. The initial population is chosen at random.

Tables 1 and 2 give the experimental results. The number in the table is the best fitness values found in 500 generations. It is averaged over 10 independent runs for each instance.

Following a simple calculation, we see that the dynamically mixed strategy EA, MSd, is the best in 77.8% instances and equally the best in 2.8% instances. If we compare the statically mixed strategy EA with the four pure strategies, then we see that MSs is better than the four pure strategy EAS in 36.1% instances (marked in italic type in the tables).

Experimental results show mixed strategy EAs outperform pure strategy EAs in up tp 77.8% instances, but not always. Naturally it raises the question: under what condition, a mixed strategy EA may outperform a pure strategy EA. This question is seldom answered rigorously before.

## 3 Support of Theory: Mixed Strategy May Outperform Pure Strategy

In this section, we conduct a theoretical comparison of the performance between mixed strategy metaheuristics and pure strategy metaheuristics.

### 3.1 Meta-heuristics and Markov Chains

Without lose of generality, consider the problem of maximising a fitness function:

 maximize f(x), (8)

where is a variable and its definition domain is a finite set.

The metaheuristics considered in the paper are formalised as Markov chains. Initially construct a population of solutions

; from , then generate a new population of solutions ; from , then generate a new population of solutions , and so on. This procedure is repeated until a stopping condition is satisfied. A sequence of populations is then generated

 Φ0→Φ1→Φ2→⋯.

An archive is used for recording the best found solution so far. The archive is not involved in generating a new population. In this way, the best found solution is preserved for ever (called elitist). The metaheuristics algorithm with an archive is described below. In the algorithm, the number of fitness evaluations for each generation is invariant.

set counter to 0;
initialize a population ;
an archive keeps the best solution in ;
while the archive is not an optimal solution do
a new population is generated from ;
update the archive if the best solution in is better than it;
counter is increased by ;
end while

The procedure of generating from can be represented by transition probabilities among populations:

 P(X,Y):=P(Φt+1=Y∣Φt=X), (9)

where populations are variables and are their values (also called states). The transition probabilities form the transition matrix of a Markov chain, denoted by .

###### Definition 1.

If a transition matrix for generating new populations is independent of , then it is called a pure strategy. A mixed strategy is a probability distribution of choosing a pure strategy from a set of strategies.

In theory, the stopping criterion is that the algorithm halts once an optimal solution is found. It is taken for the convenience of analysing the first time of finding an optimal solution (called hitting time). If includes an optimal solution, then assign

 Φt=Φt+1=Φt+2=⋯

for ever. As a result, the population sequence is formulated by a homogeneous Markov chain [17].

Since a state in the optimal set is always absorbing, so the transition matrix can be written in the canonical form,

 P=(IORQ), (10)

where is a unit matrix,

a zero matrix and

a matrix for transition probabilities among non-optimal populations. denotes the transition probabilities from non-optimal populations to optimal populations.

Let denote the expected number of generations needed to find an optimal solution when is at state for the first time (thereafter it is abbreviated by the expected hitting time). Clearly for any initial population in the optimal set, is . Let represent all populations in the non-optimal set and the vector denote their expected hitting times respectively

 →m=(m(X1),m(X2),⋯)T.

Since the number of fitness evaluations for each generation is invariant, the total number of fitness evaluations (called runtime) equals to the expected hitting time the number of fitness evaluations of a generation.

The following theorem [18, Theorem 11.5] shows that the expected hitting time can be calculated from the transition matrix.

###### Theorem 1 (Fundamental Matrix Theorem).

The expected hitting time is given by

 →m=(I−Q)−1→1, (11)

where is a vector all of whose entries are , the matrix is called the fundamental matrix.

Two special values of the expected hitting time are often used to evaluate the performance of metaheuristics. The first value is the average of the expected hitting time, given by

 ¯m=1∣S∣∑X∈Sm(X). (12)

where denotes the set of all populations. The average corresponds to the case when the initial population is chosen at random.

The second value is the maximum of the expected hitting time, given by

 max{m(X);X∈S}, (13)

The maximum corresponds to the case when the initial population is chosen at the worst state.

The population set is divided into two parts: denotes the set of all populations which don’t include any optimal solution and the set of all populations which include at least one optimal solution.

### 3.2 Drift Analysis

Drift analysis is used for bounding the expected hitting time of metaheuristics [19]. In drift analysis, a distance function is a non-negative function. Let represent all populations in the non-optimal set and denote the vector

 (d(X1),d(X2),⋯)T.
###### Definition 2.

Let be the Markov chain associated with ametaheuristic and be a distance function. For a non-optimal population , the drift at state is

 Δ(X):=d(X)−∑Y∈Snond(Y)P(X,Y).

The drift represents the one-step progress rate towards the global optima. Since the Markov chain is homogeneous, the above drift is independent of .

The following theorem is a variant of the original drift theorem [17, Theorems 3 and 4].

###### Theorem 2 (Drift Analysis Theorem).

(1) If the drift satisfies that for any state , and for some state , then the expected hitting time satisfies that for any initial population , and for some initial population .

(2) If the drift satisfies that for any state , and for some state , then the expected hitting time satisfies that for any initial population , and for some initial population .

###### Proof.

We only prove the first conclusion. The second conclusion can be proven in a similar way.

The notation is introduced in the proof as follows: given two vectors and , if for all , and for some , , then write it by . Similarly given two matrices and , if for all , and for some pair , , then write it by .

Let denote the vector whose entries are , the vector whose entries are and a matrix whose entries are . The condition of the theorem can be rewritten in an equivalent vector form:

 →d−Q→d=→1+→e,

where .

Then we have

 →d−Q→d−→1−→e=→0, (I−Q)−1(→d−Q→d−→1−→e)=→0, (I−Q)−1(→d−Q→d−→1)=(I−Q)−1→e.

Now let’s bound the right-hand side. Since , so entry for some . is a transition matrix, and the spectral radius of are less than , so

. Since no eigenvalue of

is , for the -column of , at least one entry is greater than (otherwise will be an eigenvalue of ). Thus entry for some . Then and

 (I−Q)−1→e≻→0.

Hence we get

 (I−Q)−1(→d−Q→d−→1)≻→0, →d≻(I−Q)−1→1.

From the Foundational Matrix Theorem, we know that

 (I−Q)−1→1=→m.

Then we get This inequality implies the conclusion of the theorem. ∎

The following consequence is directly derived from the Fundamental Matrix Theorem.

###### Corollary 1.

Let the distance function , then the drift satisfies for any state in the non-optimal set.

###### Proof.

From the Fundamental Matrix Theorem: . Then we write it in the entry form and it gives for any state in the non-optimal set. ∎

### 3.3 One Pure Strategy is Inferior or Equivalent to another Pure Strategy

In the subsection, we investigate the case that it is impossible to design a mixed strategy better than a pure strategy. Consider two metaheuristics: one using a pure strategy PS1 (PS1 for short) and another using a pure strategy PS2 (PS2 for short). Let be the vector representing the expected hitting times with respect to PS1 and the distance function . For PS1, denote its corresponding drift at state by :

 ΔPS1(X)=d(X)−∑Y∈SnonPPS1(X,Y)d(Y),

where represents the transition probability from to . According to Corollary 1, the drift for all in the non-optimal set.

For PS2, denote the corresponding drift at state by :

 ΔPS2(X)=d(X)−∑Y∈SnonPPS2(X,Y)d(Y).

First we propose the “inferior” condition.

###### Definition 3.

If the drift of PS1 and that of PS2 satisfy for any state , and for some state , then we call PS2 is inferior to PS1.

We consider the mixed strategy metaheuristic derived from PS1 and PS2 (MS for short) at the population level: the probability of choosing a search strategy is the same for all individuals. Suppose population is at state , we denote the probability of choosing PS1 by and the probability of choosing PS1 by . The sum

###### Lemma 1.

If PS2 is inferior to PS1, then for any mixed strategy metaheuristics derived from PS1 and PS2, the expected hitting time of MS satisfies that for any initial population , for some state .

###### Proof.

Let denote the drift associated with MS. For any state , the drift of MS is

 ΔMS(X)= d(X)−∑Y∈SnonPMS(X,Y)d(Y) = PX(PS1)[d(X)−∑Y∈SnonPPS1(X,Y)d(Y)] + PX(PS2)[d(X)−∑Y∈SnonPPS2(X,Y)d(Y)] = PX(PS1)ΔPS1(X)+PX(PS2)ΔPS2(X).

Since PS2 is inferior to PS1, we know that for any state , and for some . Therefore for any state , and for some state .

Applying the Drift Analysis Theorem, we get the conclusion: the expected hitting time satisfies that for any initial population , and for some initial population . ∎

From the above lemma, we infer two corollaries.

###### Corollary 2.

If PS2 is inferior to PS1, then for any mixed strategy MS derived from PS1 and PS2, its average of the expected hitting time is greater than that of PS1.

###### Proof.

According to the above lemma, the expected hitting time satisfies that for any initial population , and for some initial population . From the definition of average,

 ¯m=1∣S∣∑X∈Sm(X),

then we get . ∎

###### Corollary 3.

If PS2 is inferior to PS1, then for any mixed strategy MS derived from PS1 and PS2, its maximum of the expected hitting time is not less than that of PS1.

###### Proof.

According to the above lemma, the expected hitting time satisfies that for any initial population . Then we get

 max{mMS(X);X∈S}≥max{mPS1(X);X∈S}

and prove the conclusion. ∎

Next we propose the “equivalent” condition.

###### Definition 4.

If the drift of PS1 and that of PS2 satisfy for any state , then we call PS1 is equivalent to PS2.

The following lemma is direct corollary of the Drift Analysis Theorem.

###### Lemma 2.

If PS2 is equivalent to PS1, then for any mixed strategy MS derived from PS1 and PS2, its the expected hitting time satisfies that for any initial population .

### 3.4 One Pure Strategy is Complementary to Another Pure Strategy

In the subsection, we investigate the case that it is possible to design a mixed strategy better than a pure strategy. We propose the “complementary” condition. Like the previous subsection, the distance function .

###### Definition 5.

If the drift of PS1 and that of PS2 satisfy for some state , then we call PS2 is complementary to PS1.

###### Lemma 3.

If PS2 is complementary to PS1, then there exists a mixed strategy MS derived from PS1 and PS2, and its the expected hitting time satisfies that for any initial population , and for some initial population .

###### Proof.

First we construct a mixed strategy derived from PS1 and PS2. The construction follows a well-known principle: at one state, if a pure strategy has a better performance than the other at a state, then the strategy should be applied with a higher probability at that state.

1. When is at state , if the drift is greater than the drift , then the probability of choosing PS1 is set to 1, that is, .

2. When is at state , if the drift equals to the drift , then the probability of choosing PS1 is set to any value between , that is, .

3. Since PS2 is complementary to PS1, so there exists one state such that the drift is larger than the drift . When is at such a state , then the probability of choosing PS2 is set to any value greater than , that is, .

In this way a mixed strategy MS is constructed from PS1 and PS2.

Next we bound the drift of the mixed strategy. For any state , the drift of the mixed strategy is

 ΔMS(X)= d(X)−∑Y∈SnonPMS(X,Y)d(Y) = PX(PS1)[d(X)−∑Y∈SnonPPS1(X,Y)d(Y)] + PX(PS2)[d(X)−∑Y∈SnonPPS2(X,Y)d(Y)] = PX(PS1)ΔPS1(X)+PX(PS2)ΔPS2(X).

Based on the construction of the mixed strategy, the analysis of the drift is classified into three cases.

1. : in this case, the probability of choosing PS1 is 1, that is, . Thus the drift satisfies:

2. : in this case, the drift satisfies:

3. : in this case, the probability of choosing PS2 is greater than 0, that is, . Thus the drift satisfies:

Summarising all three cases, we see that the drift of the mixed strategy satisfies: for any state , and for some state .

Finally applying the Drift Analysis Theorem, we come to the conclusion: the expected hitting time satisfies: for any initial population , and for some initial population . ∎

From the above lemma, we draw two results about the average and maximum of the expected hitting times.

###### Corollary 4.

If PS2 is complementary to PS1, then there exists a mixed strategy MS derived from PS1 and PS2 and its average of the expected hitting time is less than that PS1.

###### Proof.

According to the above lemma, the expected hitting time satisfies: for any initial population , and for some initial population . From the definition

 ¯m=1∣S∣∑X∈Sm(X),

then we get . ∎

###### Corollary 5.

If PS2 is complementary to PS1, then there exists a mixed strategy MS derived from PS1 and PS2 and its maximum of the expected hitting time is no more than that PS1.

###### Proof.

According to the above lemma, the expected hitting time satisfies: for any initial population . Then we get

 max{mMS(X);X∈S}≤max{mPS1(X);X∈S}

and prove the conclusion. ∎

### 3.5 Complementary Strategy Theorem

Combining Lemmas 1, 2 and 3 together, we obtain our main result about mixed strategy metaheuristics. It gives an answer to the question: under what condition, mixed strategy metaheuristics may outperform pure strategy metaheuristics.

###### Theorem 3 (Complementary Strategy Theorem).

Consider two metaheuristics: one using pure strategy PS1 and another using pure strategy PS2. The condition of PS2 being complementary to PS1 is sufficient and necessary if there exists a mixed strategy MS derived from PS1 and PS2 such that: for any initial population , and for some initial population .

Furthermore the condition of PS2 being complementary to PS1 is sufficient and necessary if there exists a mixed strategy MS derived from PS1 and PS2 such that: the expected runtime of MS is no more than that of PS1 for any initial population , and less than that of PS1 for some initial population .

###### Proof.

Given PS1 and PS2, their relation is classified into exact three exclusive types: PS2 is inferior, or equivalent, or complementary to PS1. Thus combining Lemmas 1, 2 and 3 together, we get the desired first conclusion.

Since the expected runtime equals to the expected hitting time the number of fitness evaluations of a generation, we obtain the second conclusion. ∎

The theorem can be explained intuitively as follows.

1. If one pure strategy is inferior to another pure strategy, then it is impossible to design a mixed strategy with a better performance. So mixed strategy metaheuristics doesn’t always outperform pure strategy metaheuristics.

2. If one pure strategy is complementary to another one, then it possible to design a mixed strategy better than the pure strategy. But it does not mean all mixed strategies will outperform the pure strategy.

3. The construction of a better mixed strategy metaheuristics should follow a general principle: if using a pure strategy has a better progress rate (in terms of the drift) than that using the other at a state, then the strategy should be applied with a higher probability at that state. This principle is general, but the design of a better mixed strategy is strongly dependent on the problem.

For the average of the expected hitting time, we may obtain a similar consequence after combining Corollaries 2, 4 and Lemma 2 together.

###### Corollary 6.

The condition of PS2 being complementary to PS1 is sufficient and necessary if there exists a mixed strategy MS derived from PS1 and PS2 and its average of the expected hitting time is less than than that of PS1.

But the sufficient and necessary condition for the maximum of the expected hitting time is more complex.

### 3.6 An Example

Consider an instance of the 0-1 knapsack problem: the value of items and for , the weight of items and for . The capacity . The fitness function is

 f(x)=⎧⎪⎨⎪⎩n,if s1=1,s2=⋯sn=0,∑ni=1si,if s1=0,infeasible ,otherwise. (14)

For the four pure EAs described in the previous section, it is easy to verify that

1. PSr is equivalent to PSb,

2. PSw is inferior to PSb,

3. PSv is complementary to PSb.

Applying the Completerary Strategy Theorem, we know that

1. combining PSr with PSb will not shorten the expected runtime;

2. combining PSw will PSb will not shorten the expected runtime too;

3. but combining PSv with PSb may reduce the expected runtime.

## 4 Conclusions

The main contribution of the paper is the Complementary Strategy Theorem. From the theoretical viewpoint, the theorem provides an answer to the question: under what condition, mixed strategy metaheuristics may outperform pure strategy metaheuristics. The theorem asserts that given two metaheuristics where one uses a pure strategy PS1 and the other uses a pure strategy PS2, the condition of PS2 being complementary to PS1 is sufficient and necessary if there exists a mixed strategy MS derived from PS1 and PS2 such that: the expected runtime of MS is no more than that of PS1 for any initial population , and less than that of PS1 for some initial population . To the best of our knowledge, no similar sufficient and necessary condition was rigorously established based on the runtime analysis of hybrid metaheuristics before. This is a step to understand hybrid metaheuristics in theory.

Besides the above theoretical analysis, experiments are also implemented. Experimental results demonstrate that mixed strategy EAs may outperform pure strategy EAs on the 0-1 knapsack problem in up to 77.8% instances. In the experiments, the performance of an EA is measured by the fitness function value of the archive after 500 generations.

It should be mentioned that a huge gap exists between empirical and theoretical studies. In experiments, the optimal solution is usually unknown in most instances, then the expected runtime is unavailable; in theory, it is difficult to analyse the best solution found in 500 generations or in any fixed generations.

## Acknowledgement

This work is supported by the EPSRC under Grant EP/I009809/1, the National Natural Science Foundation of China under Grant 60973075 and Ministry of Industry and Information Technology under Grant B0720110002.

## References

• Glover and Kochenberger [2003] Fred Glover and Gary A Kochenberger. Handbook of Metaheuristics. Springer, 2003.
• Gendreau and Potvin [2010] Michel Gendreau and Jean-Yves Potvin. Handbook of Metaheuristics. Springer, 2010.
• Blum and Roli [2003] Christian Blum and Andrea Roli.

Metaheuristics in combinatorial optimization: Overview and conceptual comparison.

ACM Computing Surveys, 35(3):268–308, 2003.
• Blum et al. [2008] Christian Blum, Andrea Roli, and Michael Sampels. Hybrid Metaheuristics: an Emerging Approach to Optimization. Springer, 2008.
• Burke et al. [2003] E. Burke, G. Kendall, J. Newall, E. Hart, P. Ross, and S. Schulenburg. Hyper-heuristics: An emerging direction in modern search technology. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pages 457–474. Springer, 2003.
• Neri et al. [2011] Ferrante Neri, Carlos Cotta, and Pablo Moscato. Handbook of memetic algorithms, volume 379. Springer, 2011.
• He and Yao [2005] J. He and X. Yao. A game-theoretic approach for designing mixed mutation strategies. In L. Wang, K. Chen, and Y.-S. Ong, editors, Proceedings of the 1st International Conference on Natural Computation, LNCS 3612, pages 279–288, Changsha, China, August 2005. Springer.
• Dutta [1999] P.K. Dutta. Strategies and Games: Theory and Practice. MIT Press, 1999.
• Dong et al. [2007] H. Dong, J. He, H. Huang, and W. Hou. Evolutionary programming using a mixed mutation strategy. Information Sciences, 177(1):312–327, 2007.
• Shen and He [2010] L. Shen and J. He. A mixed strategy for evolutionary programming based on local fitness landscape. In

Proceedings of 2010 IEEE Congress on Evolutionary Computation

, pages 350–357, Barcelona, Spain, 2010. IEEE Press.
• Lehre and Özcan [2013] Per Kristian Lehre and Ender Özcan. A runtime analysis of simple hyper-heuristics: To mix or not to mix operators. In Proceedings of FOGA 2013, 2013.
• He et al. [2012] J. He, F. He, and H. Dong. Pure strategy or mixed strategy? In Jin-Kao Hao and Martin Middendorf, editors, Evolutionary Computation in Combinatorial Optimization (LNCS 7245), pages 218–229. Springer, 2012.
• Varga [2009] R.S. Varga. Matrix Iterative Analysis. Springer, 2009.
• Martello and Toth [1990] S. Martello and P. Toth. Knapsack Problems. John Wiley & Sons, Chichester, 1990.
• Michalewicz [1996] Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, New York, third edition, 1996.
• He and Zhou [2007] J. He and Y. Zhou. A comparison of GAs using penalizing infeasible solutions and repairing infeasible solutions II: Avarerage capacity knapsack. In L. Kang, Y. Liu, and S. Y. Zeng, editors, Proceedings of the 2nd International Symposium on Intelligence Computation and Applications (ISICA’2007), LNCS 4683, pages 102–110, Wuhan, China, September 2007. Springer.
• He and Yao [2003] J. He and X. Yao. Towards an analytic framework for analysing the computation time of evolutionary algorithms. Artificial Intelligence, 145(1-2):59–97, 2003.
• Grinstead and Snell [1997] C.M. Grinstead and J.L. Snell. Introduction to Probability. American Mathematical Society, 1997.
• He and Yao [2001] J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127(1):57–85, 2001.


text:
## CryptoDB

### Paper: Automatic Search of Cubes for Attacking Stream Ciphers

Authors: Yao Sun , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China DOI: 10.46586/tosc.v2021.i4.100-123 URL: https://tosc.iacr.org/index.php/ToSC/article/view/9330 Search ePrint Search Google Cube attack was proposed by Dinur and Shamir, and it has become an important tool for analyzing stream ciphers. As the problem that how to recover the superpolys accurately was resolved by Hao et al. in EUROCRYPT 2020, another important problem is how to find “good” superpolys, which is equivalent to finding “good” cubes. However, there are two difficulties in finding “good” cubes. Firstly, the number of candidate cubes is enormous and most of the cubes are not “good”. Secondly, it is costly to evaluate whether a cube is “good”.In this paper, we present a new algorithm to search for a kind of “good” cubes, called valuable cubes. A cube is called valuable, if its superpoly has (at least) a balanced secret variable. A valuable cube is “good”, because its superpoly brings in 1 bit of information about the key. More importantly, the superpolys of valuable cubes could be used in both theoretical and practical analyses. To search for valuable cubes, instead of testing a set of cubes one by one, the new algorithm deals with the set of cubes together, such that the common computations can be done only once for all candidate cubes and duplicated computations are avoided. Besides, the new algorithm uses a heuristic method to reject useless cubes efficiently. This heuristic method is based on the divide-and-conquer strategy as well as an observation.For verifications of this new algorithm, we applied it to Trivium and Kreyvium, and obtained three improvements. Firstly, we found two valuable cubes for 843-round Trivium, such that we proposed, as far as we know, the first theoretical key-recovery attack against 843-round Trivium, while the previous highest round of Trivium that can be attacked was 842, given by Hao et al. in EUROCRYPT 2020. Secondly, by finding many small valuable cubes, we presented practical attacks against 806- and 808-round Trivium for the first time, while the previous highest round of Trivium that can be attacked practically was 805. Thirdly, based on the cube used to attack 892-round Kreyvium in EUROCRYPT 2020, we found more valuable cubes and mounted the key-recovery attacks against Kreyvium to 893-round.
##### BibTeX
@article{tosc-2021-31683,
title={Automatic Search of Cubes for Attacking Stream Ciphers},
journal={IACR Transactions on Symmetric Cryptology},
publisher={Ruhr-Universität Bochum},
volume={2021, Issue 4},
pages={100-123},
url={https://tosc.iacr.org/index.php/ToSC/article/view/9330},
doi={10.46586/tosc.v2021.i4.100-123},
author={Yao Sun},
year=2021
}

format: plain


text:
# Homework Help: Tension in a string at an angle

1. Feb 9, 2010

### BikeSmoth

1. The problem statement, all variables and given/known data
A wire of negligible mass is used to hang a 2.15 kg picture. The ends of the wire are attached to the top 2 corners of the picture. Each end of the wire forms an angle of 15.0 degrees from the horizontal. What is the tension in the wire?

2. Relevant equations
$$\Sigma$$F=ma

3. The attempt at a solution
This is my latest and posiibly best attmept so far, but I don't have anyone to tell me if its right or not.
$$\Sigma$$F+(-ma)=2Tsin$$\theta$$-ma=0
2Tsin15-19.737=0
T=38.1N

2. Feb 9, 2010

It's correct

3. Feb 9, 2010

### dacruick

on which wire would you like the tension for?

4. Feb 9, 2010

### rock.freak667

Yes it looks correct to me.

Though you should put ΣFy=0 when the picture is in equilibrium and then rearrange to get T.

2Tsinθ-mg=0

5. Feb 9, 2010

### BikeSmoth

there is only one wire with the picture connected at the two ends hanging down.

6. Feb 9, 2010

### BikeSmoth

well it looks like my brilliant self put 9.18 instead of 9.81 in my calculator and subsequently got the question wrong. Man I hate online homework so much!!!!!!!!!!!!!!!!!!!


text:
# Aleph-Null

## Theorem

Let $\omega$ denote the minimal infinite successor set.

$\omega = \aleph_0$

where $\aleph$ denotes the aleph mapping.

## Proof

For all $n \in \omega$, $n \notin \mathcal N'$ by the definition of the infinite cardinal class.

Therefore, $\omega \le \aleph_0$.

$\Box$

Moreover, $\omega \in \mathcal N'$ by Minimal Infinite Successor Set is Infinite Cardinal.

Therefore, $\aleph_x = \omega$ for some ordinal $x$.

It follows that $\aleph_0 \le \aleph_x$ since $0 \le x$ and the definition of the aleph mapping, so $\aleph_0 \le \omega$.

Thus, $\aleph_0 = \omega$.

$\blacksquare$


text:
# What is the radius of this circle?

Polygon $ABC$ is an equilateral triangle. Three congruent semicircular arcs are drawn on the three sides and towards the interior of the triangle. The terminal points of the semicircular arcs are the three vertices of the triangle $ABC$. Semicircle $C_1$ of diameter $AB$ Semicircle $C_2$ of diameter $BC$ Semicircle $C_3$ of diameter $CA$

A small circle $F$ is drawn such that it is tangent internally to $C_1$ and $C_3$ and externally to $C_2$

What is the radius of circle $F$?

Here is the picture

Using coordinates . . .

For convenience of notation, let $h=\sqrt{3}$.

Let $B = (-1,0),\;C=(1,0),\;A=(0,h)$.

Let $P$ be the center of the required circle.

Then $P=(0,1+r)$, where $r$ is the unknown radius.

Let $c(P,r)$ denote the circle centered at $P$, with radius $r$.

Let $M$ be the midpoint of segment $CA$.

Then $M=\bigl({\large{\frac{1}{2}}},{\large{\frac{h}{2}}}\bigr)$.

Let $s(M,1)$ denote the semicircle centered at $M$, with radius $1$, as shown in the diagram.

Let $T$ be the point where $c(P,r)$ meets $s(M,1)$.

Since $c(P,r)$ and $s(M,1)$ are tangent to each other at $T$, it follows that the points $M,P,T$ are collinear.

Then since $MT=1$ and $PT=r$, we get $MP=1-r$, hence by the distance formula \begin{align*} &MP^2=(1-r)^2\\[4pt] \implies\;&\left({\small{\frac{1}{2}}}-0\right)^{\!2}+\left({\small{\frac{h}{2}}}-(1+r)\right)^{\!\!2}=(1-r)^2\\[4pt] \implies\;&r=\frac{4h-1-h^2}{4(4-h)}\\[4pt] &\phantom{r}=\frac{4\sqrt{3}-4}{4(4-\sqrt{3})}\\[4pt] &\phantom{r}=\frac{3\sqrt{3}-1}{13}\approx .3227809558\\[4pt] \end{align*}

From the red triangle in the picture we infer $$(1-r)^2=\left({1\over2}\right)^2+\left(r+\left(1-{\sqrt{3}\over2}\right)\right)^2\ ,$$ and this leads to $$r={3\sqrt{3}-1\over13}\ .$$

Although I think using coordinates is the best way to solve these types of problems, it's fun to find other solution.
The figure below is pretty apparent and gives us the construction for the circle. Let the side of the triangle be $2R$

Using the Law of Cosines we get $MH=R\sqrt{2-\sqrt{3}},\ MD=R\sqrt{5-2\sqrt{3}}\$ (note that we are using $\cos 105^{\circ}=\dfrac{\sqrt{2}+\sqrt{6}}{4}$). We also have $DE\cdot MD=AD\cdot DH$, which gives us $$\frac{R^2(\sqrt{3}-1)}{MD^2}=\frac{DE}{MD}\Rightarrow \frac{\sqrt{3}-1}{5-2\sqrt{3}}=\frac{IE}{R-IE}$$ That last equation simplified to $$IE=\frac{\sqrt{3}-1}{4-\sqrt{3}}R=\frac{3\sqrt{3}-1}{13}R$$


text:
# What is your eyesight worth?

## What would you give up your eyesight for?

25 vote(s)
71.4%

1 vote(s)
2.9%

4 vote(s)
11.4%
4. ### some higher amount

5 vote(s)
14.3%
1. Jun 19, 2006

### 0TheSwerve0

Would you give up your eyesight (permanently) for a billion dollars? A million?

2. Jun 19, 2006

### Staff: Mentor

The last guy I dated was blind in one eye. I would have never known if he hadn't told me. When you have only one eye left, that eye becomes very precious.

Last edited: Jun 19, 2006
3. Jun 19, 2006

### wolram

What ever thoughts did you have when you posted this ?

4. Jun 19, 2006

### Cyrus

If I went blind, I'd kill myself. (Not being cute, in all seriousness, I would)

I could manage being deaf, but blind.....no.

5. Jun 19, 2006

### loseyourname

Staff Emeritus
I guess I'm the only one to answer positively. I'd gladly go blind for a billion dollars. Gordon Gund lives a better life than I.

6. Jun 19, 2006

### rcgldr

Here's a similar example, be careful what you wish for:

redsox.wmv

7. Jun 19, 2006

### wolram

OWWWch, i nearly droped my lap top, the thought of it sends me cock eyed.

8. Jun 19, 2006

### silkworm

If I had no vision I would cease to have any memory whatsoever and a very decreased level of ability to learn and be productive. I'd much rather be confined to a wheelchair or a bubble than to be blind, I just don't think I'd adjust well. I'm very dependent on my vision.

9. Jun 19, 2006

### Astronuc

Staff Emeritus
I would not voluntarily give up my sight for any amount of money.

If I went blind, I'd make do somehow.

10. Jun 19, 2006

### Moonbear

Staff Emeritus
Those are my sentiments as well.

11. Jun 19, 2006

### Tzemach

There are many things that are worth much more than money, and most of them we get for free. Life, health, sight and even love (the stuff you buy isn't really love) we should be thankful for these gifts and not worry about money. If we lose one of them most of us would willingly part with all our money to get it back.

12. Jun 19, 2006

### heartless

I wonder how people voting for at least billion of dollars imagine their life without a sight. Even if you have all of this you cannot enjoy your money because you're blind, and things you want for money you usually don't have require an eyesight.

Last edited: Jun 19, 2006
13. Jun 19, 2006

### mattmns

At this point in my life, no amount of money would suffice. However, I voted for "some higher amount" (not seeing the first option )

14. Jun 19, 2006

### moose

If it was a matter of my family starving and living on the streets, then that would be a different matter....

*talking in future tense*

15. Jun 19, 2006

### 0TheSwerve0

Can't remember, I was watching tv when I thought of it. I asked LYN if he would give up his eyesight for a billion dollars and he basically said hells yes. I was pretty surprised and couldn't accept the arguments he was making for it, so I decided to start a poll to see if it was me that was the crazy one. As usual, it wasn't

16. Jun 20, 2006

### BobG

Wow, some surprising results. The overwhelming majority would give their eyesight up for free.

I picked some higher amount, since it came the closest to reflecting how I'd feel about losing my eyesight.

17. Jun 20, 2006

### Mk

Thank you so much! I will be glad to ignore that link.

Some stuff on the internet you don't want to see. Seriously, it has a negative impact on the rest of your day.

18. Jun 20, 2006

### loseyourname

Staff Emeritus
I really wonder why people think life as a blind person would be so terrible. Gordon Gund might be the only blind billionaire, but there are others that have plenty of money, and others that have no money, that have lives just as fulfilling and rich as my own. It isn't my eyesight that makes me a happy person.

19. Jun 20, 2006

### Staff: Mentor

Heh.

:grumpy:

20. Jun 20, 2006

### scott1

100,000,000,000.17$$\frac{1}{2}$$

21. Jun 21, 2006

### rcgldr

Oh come on MK, if you're a true fan of team, what's the problem of a little inconvenience to see them win?

22. Jun 21, 2006

### ndnbolla

I know the poll is over but I would have gone with 1 billion or even more dollars.

If you really think about it, a difference can be made in the world with a billion dollars. Think of the possibilites that this money could be invested in to actually help the rest of the world whether it would be towards getting kids in poverty with potential to get into MIT into MIT or just investing in a research to cure AIDs. Who knows, maybe that kid in poverty could develop the cure for aids?

Being blind isn't as bad as you think (but how would I know?). I still have my other four senses. The only bad thing I can think of is not being able to know if you had a roach in you lunch or not. (Taken from Seinfeld. )

Maybe I have gone into this a little too deep, otherwise this is probably Fox's next premesis for a reality show. :)

Edit: NM I guess the poll isn't over, I just needed to log in.

Last edited: Jun 21, 2006
23. Jun 21, 2006

### JamesU

I meant to choose billion, not million BTW


text:
# Class tensor_grid (o2scl)¶

template<class vec_t = std::vector<double>, class vec_size_t = std::vector<size_t>>
class tensor_grid : public o2scl::tensor<double, std::vector<double>, std::vector<size_t>>

Tensor class with arbitrary dimensions with a grid.

This tensor class allows one to assign the indexes to numerical scales, effectively defining a data set on an n-dimensional grid. To set the grid, use default_grid(), set_grid() or set_grid_packed().

By convention, member functions ending in the _val suffix return the closest grid-point to some user-specified values.

Slicing

New o2scl::tensor_grid objects can be obtained by fixing any set of indices using copy_slice_interp().

Fixing all but two indices also results in a o2scl::table3d object, and five functions perform this task in different ways. The function copy_table3d_align() copies a two-dimensional slice to a o2scl::table3d object presuming that the grid in the o2scl::table3d object has already been set and exactly matches the corresponding sizes for the selected tensor indices. This function does not check that the grids between the two objects match, it only ensures that they have the same size. In order to copy to a o2scl::table3d object and set its grid to match that from the unfixed indices in the o2scl::tensor_grid object, the function copy_table3d_align_setxy() can be used. The function copy_table3d_interp() uses interpolation to extract values from the o2scl::tensor_grid object. It allows the user to select indices to be fixed and then uses the values in the grid in the o2scl::table3d object for the indices which vary. Alternatively copy_table3d_interp_values() allows the user to specify values on the grid for the indices to be fixed and uses the grid in the o2scl::table3d object for the indices which vary. Finally, copy_table3d_interp_values_setxy() acts like copy_table3d_interp_values() except that it sets the o2scl::table3d grid to be the same as the grid in the o2scl::tensor_grid object which corresponds to the indices which are being varied.

Notes and Todos

Todo

Class tensor_grid: It is possible for the user to create a tensor_grid object, upcast it to a tensor object, and then use tensor::resize() to resize the tensor, failing to resize the grid. Following this, grid access functions will access random parts of memory or segfault. This can be fixed by ensuring that resize functions are virtual and have a version in tensor_grid which ensure that the grid and tensor data are matched. The problem is that the resize functions are templates, so they cannot be virtual.

• Future: Create a swap function for the grid similar to the data swap function in the parent ref o2scl::tensor class?

• Future: Only allocate space for grid if it is set.

• Future: as with ref o2scl::tensor, generalize to other base data types.

• Future: The function ref interp_linear_partial() appears to be a generalization of ref copy_table3d_interp_values_setxy(), so there may be some code duplication between the two that can be avoided.

Note

Currently, HDF5 I/O is only allowed if the tensor is allocated with std::vector-based types, and the interpolate() function only works with ublas-based vector types.

Constructors and Destructors

inline tensor_grid()

Create an empty tensor with zero rank.

template<class size_vec_t>
inline tensor_grid(size_t rank, const size_vec_t &dim)

Create a tensor of rank rank with sizes given in dim.

The parameter dim must be a vector of sizes with length rank. If the user requests any of the sizes to be zero, this constructor will call the error handler.

inline tensor_grid(std::vector<uniform_grid<double>> &ugs)

Create a tensor with a grid defined by a set of o2scl::uniform_grid objects.

inline virtual ~tensor_grid()

Destructor.

Method to check for valid object

inline void is_valid() const

Check that the o2scl::tensor_grid object is valid.

Copy constructors

inline tensor_grid(const tensor_grid<vec_t, vec_size_t> &t)

Copy using operator()

inline tensor_grid<vec_t, vec_size_t> &operator=(const tensor_grid<vec_t, vec_size_t> &t)

Copy using operator=()

Set functions

template<class vec2_t>
inline void set_val(const vec2_t &grdp, double val)

Set the element closest to grid point grdp to value val.

template<class vec2_t, class vec3_t>
inline void set_val(const vec2_t &grdp, double val, vec3_t &closest)

Set the element closest to grid point grdp to value val.

The parameters closest and grdp may be identical, allowing one to update a vector grdp with the closest grid point.

Get functions

template<class vec2_t>
inline double get_val(const vec2_t &gridp)

Get the element closest to grid point gridp.

template<class vec2_t, class vec3_t>
inline double get_val(const vec2_t &gridp, vec3_t &closest)

Get the element closest to grid point gridp, store grid values in closest and return value.

The parameters gridp and closest may refer to the same object.

inline const vec_t &get_grid() const

Get grid.

Resize method

template<class size_vec2_t>
inline void resize(size_t rank, const size_vec2_t &dim)

Resize the tensor to rank rank with sizes given in dim.

The parameter dim must be a vector of sizes with a length equal to rank. This resize method is always destructive, and the grid is always reset.

If the user requests any of the sizes to be zero, this function will call the error handler.

Grid manipulation

inline bool is_grid_set() const

Return true if the grid has been set.

template<class vec2_t>
inline void set_grid_packed(const vec2_t &grid_vec)

Set the grid.

The grid must be specified for all of the dimensions at once. Denote $$(\mathrm{size})_0$$ as the size of the first dimension, $$(\mathrm{size})_1$$ as the size of the second dimesion, and so on. Then the first $$(\mathrm{size})_0$$ entries in grid must be the grid for the first dimension, the next $$(\mathrm{size})_1$$ entries must be the grid for the second dimension, and so on. Thus grid must be a vector of size

$\sum_{i=0}^{\mathrm{rank}} (\mathrm{size})_i$

Note that the grid is copied so the function argument may be destroyed by the user after calling set_grid_packed() without affecting the tensor grid.

Todo

In set_grid_packed(): Define a more generic interface for matrix types

template<class vec_vec_t>
inline void set_grid(const vec_vec_t &grid_vecs)

Set grid from a vector of vectors of grid points.

inline void default_grid()

Use a default grid which just uses the index.

template<class vec2_t>
inline void set_grid_i_vec(size_t ix, const vec2_t &grid_vec)

Set grid for one index from a vector.

inline void set_grid_i_func(size_t ix, std::string func)

Set grid for one index from a function.

inline void set_grid(std::vector<uniform_grid<double>> &ugs)

Set grid from a vector of uniform grid objects.

Note

This is called by one of the constructors.

template<class rvec_t>
inline void copy_grid(size_t i, rvec_t &v) const

Copy grid for index i to vector v.

The type rvec_t must be a vector with a resize method.

inline double get_grid(size_t i, size_t j) const

Lookup jth value on the ith grid.

inline void set_grid(size_t i, size_t j, double val)

Set the jth value on the ith grid.

inline size_t lookup_grid_val(size_t i, const double &val, double &val2) const

Lookup index for grid closest to val, returning the grid point.

The parameters val and val2 may refer to the same object.

inline size_t lookup_grid(size_t i, double val) const

Lookup index for grid closest to val.

template<class vec2_t, class size_vec2_t>
inline void lookup_grid_vec(const vec2_t &vals, size_vec2_t &indices) const

Lookup indices for grid closest point to vals.

The values in vals are not modified by this function.

inline size_t lookup_grid_packed_val(size_t i, double val, double &val2) const

Lookup internal packed grid index for point closest to val and store closest value in val2.

This version, rather than o2scl::tensor_grid::lookup_grid_val() can be useful because it gives the index of the grid point in the internal grid vector object.

inline size_t lookup_grid_packed(size_t i, double val) const

Lookup internal packed grid index for point closest to val.

Slicing to tensor_grid objects

template<class size_vec2_t, class vec2_t>
inline tensor_grid copy_slice_interp(size_vec2_t &ifix, vec2_t &vals) const

Copy an abitrary slice by fixing 1 or more indices and use interpolation to return a new tensor_grid object.

Slicing and converting to table3d objects

inline void convert_table3d_sum(size_t ix_x, size_t ix_y, table3d &tab, std::string x_name = "x", std::string y_name = "y", std::string slice_name = "z") const

Convert to a o2scl::table3d object by summing over all but two indices.

template<class size_vec2_t>
inline void copy_table3d_align(size_t ix_x, size_t ix_y, size_vec2_t &index, table3d &tab, std::string slice_name = "z") const

Create a slice in a o2scl::table3d object with an aligned grid.

This function uses the grid associated with indices ix_x and ix_y, to copy data to a slice named slice_name in the table3d object tab . All other indices are fixed to values specified by the user in index and the values of index[ix_x] and index[ix_y] are used for temporary storage.

If the table3d object does not currently have a grid set, then the grid is automatically set to be the same as that stored in the tensor_grid object associated with ranks ix_x and iy_y. If the o2scl::table3d object does have a grid set, then the values returned by o2scl::table3d::get_nx() and o2scl::table3d::get_ny() must be equal to the size of the tensor in indices ix_x and ix_y, respectively. If a slice named slice_name is not already present in tab, then a new slice with that name is created.

The error handler is called if ix_x is the same as ix_y, or if either of these two values is greater than or equal to the tensor rank.

template<class size_vec2_t>
inline void copy_table3d_align_setxy(size_t ix_x, size_t ix_y, size_vec2_t &index, table3d &tab, std::string x_name = "x", std::string y_name = "y", std::string slice_name = "z") const

Create a slice in a table3d object with a new aligned grid.

template<class size_vec2_t>
inline void copy_table3d_interp(size_t ix_x, size_t ix_y, size_vec2_t &index, table3d &tab, std::string slice_name = "z") const

Copy to a slice in a table3d object using interpolation.

This function uses the grid associated with indices ix_x and ix_y, and the tensor interpolation function to copy the tensor information to the slice named slice_name in the table3d object tab . All other indices are fixed to values specified by the user in index and the values of index[ix_x] and index[ix_y] are used for temporary storage.

If a slice named slice_name is not already present in tab, then a new slice with that name is created.

The error handler is called if ix_x is the same as ix_y, or if either of these two values is greater than or equal to the tensor rank.

Note

This function uses the tensor_grid::interp_linear() for the interpolation.

template<class vec2_t>
inline void copy_table3d_interp_values(size_t ix_x, size_t ix_y, vec2_t &values, table3d &tab, std::string slice_name = "z", int verbose = 0) const

Copy to a slice in a table3d object using interpolation.

template<class vec2_t>
inline void copy_table3d_interp_values_setxy(size_t ix_x, size_t ix_y, vec2_t &values, table3d &tab, std::string x_name = "x", std::string y_name = "y", std::string slice_name = "z") const

Copy to a slice in a table3d object using interpolation creating a new table3d grid.

inline void from_table3d_fermi(const table3d &t3d, std::string slice, size_t n_points, double low = 0.0, double high = 0.0, double width = 0.0)

Create from a table3d object.

Clear method

inline void clear()

Clear the tensor of all data and free allocated memory.

Interpolation

inline void set_interp_type(size_t interp_type)

Set interpolation type for interpolate()

template<class range_t = ub_range, class data_range_t = ubvector_range, class index_range_t = ubvector_size_t_range>
inline double interpolate(double *vals)

Interpolate values vals into the tensor, returning the result.

This is a quick and dirty implementation of n-dimensional interpolation by recursive application of the 1-dimensional routine from interp_vec, using the base interpolation object specified in the template parameter base_interp_t. This will be very slow for sufficiently large data sets.

Idea for Future:

It should be straightforward to improve the scaling of this algorithm significantly by creating a “window” of local points around the point of interest. This could be done easily by constructing an initial subtensor. However, this should probably be superceded by a more generic alternative which avoids explicit use of the 1-d interpolation types.

Note

This function requires a range objects to obtain ranges of vector objects. In ublas, this is done with ublas::vector_range objects, so this function will certainly work for tensor_grid objects built on ublas vector types. There is no corresponding std::range, but you may be able to use either ublas::vector_range or Boost.Range in order to call this function with tensor_grid objects built on std::vector. However, this is not fully tested at the moment.

template<class vec2_size_t, class vec3_size_t, class vec2_t>
inline double interp_linear_partial(const vec2_size_t &ix_to_interp, vec3_size_t &ix, const vec2_t &val) const

Obtain a value by looking up some indices and interpolating the others.

To call this function, the arguments should be of the following form

• The vector ix_to_interp should be a list of indices to interpolate. The size of ix_to_interp must be at least 1 or larger but smaller than or equal to the full tensor rank. All entries in ix_to_interp should be smaller than the full tensor rank.

• The vector ix should have a size equal to the tensor rank, but values stored in entries corresponding to the indices in ix_to_interp will be ignored

• The vector val should be a list of values to be interpolated and should have a size equal to that of ix_to_interp .

Todo

In tensor_grid::interp_linear_partial(): Double check and document if the vector “ix_to_interp” needs to be ordered. I’m pretty sure it doesn’t, so long as the ordering in c val and c ix_to_interp are consistent.

template<class vec2_t>
inline double interp_linear(vec2_t &v) const

Perform a linear interpolation of v into the function implied by the tensor and grid.

This performs multi-dimensional linear interpolation (or extrapolation) It works by first using o2scl::search_vec to find the interval containing (or closest to) the specified point in each direction and constructing the corresponding hypercube of size $$2^{\mathrm{rank}}$$ containing v. It then calls interp_linear_power_two() to perform the interpolation in that hypercube.

This function calls the error handler if the user tries to interpolate an empty tensor.

Idea for Future:

This starts with a small copy, which can be eliminated by creating a new version of interp_linear_power_two which accepts an offset vector parameter so that the first interpolation is offset. Remaining interpolations don’t need to be offset because the tensor has to be created from the previous interpolation round.

template<class vec2_t>
inline double interp_linear_power_two(vec2_t &v) const

Perform linear interpolation assuming that all indices can take only two values.

This function works by recursively slicing the hypercube of size $$2^{\mathrm{rank}}$$ into a hypercube of size $$2^{\mathrm{rank-1}}$$ performing linear interpolation for each pair of points.

Note

This is principally a function for internal use by interp_linear().

template<class vec2_t, class vec3_t>
inline void interp_linear_vec0(vec2_t &v, vec3_t &res) const

Perform a linear interpolation of v[1] to v[n-1] resulting in a vector.

This performs multi-dimensional linear interpolation (or extrapolation) in the last n-1 indices of the rank-n tensor leaving the first index free and places the results in the vector res.

Note

The type vec2_t for the vector res must have a resize() method.

template<class vec2_t, class vec3_t>
inline void interp_linear_power_two_vec0(vec2_t &v, vec3_t &res) const

Perform linear interpolation assuming that the last n-1 indices can take only two values.

This function performs linear interpolation assuming that the last n-1 indices can take only two values and placing the result into res.

Note

The type vec2_t for the vector res must have a resize() method. This is principally a function for internal use by interp_linear_vec0().

template<class vec2_t, class vec3_t>
inline void interp_linear_vec(vec2_t &v, size_t ifree, vec3_t &res) const

Perform a linear interpolation of v into the tensor leaving one index free resulting in a vector.

This performs multi-dimensional linear interpolation (or extrapolation) in the last n-1 indices of the rank-n tensor leaving the first index free and places the results in the vector res.

Idea for Future:

This function could be more efficient.

inline tensor_grid<vec_t, vec_size_t> rearrange_and_copy(std::vector<index_spec> spec, int verbose = 0, bool err_on_fail = true) const

Rearrange, sum and copy current tensor to a new tensor.

Idea for Future:

Some code duplication between this function and the one in the tensor class.

Note

Experimental

inline tensor_grid<vec_t, vec_size_t> rearrange_and_copy(std::string spec, int verbose = 0, bool err_on_fail = true)

Rearrange, sum and copy current tensor to a new tensor (string input version)

template<class vecf_t, class vecf_size_t>
friend void hdf_output(o2scl_hdf::hdf_file &hf, tensor_grid<vecf_t, vecf_size_t> &t, std::string name)
template<class vecf_t, class vecf_size_t>
friend void hdf_input(o2scl_hdf::hdf_file &hf, tensor_grid<vecf_t, vecf_size_t> &t, std::string name)

Protected Attributes

vec_t grid

A rank-sized set of arrays for the grid points.

bool grid_set

If true, the grid has been set by the user.

size_t itype

Interpolation type.


text:
# Insights into the structural, electronic, and magnetic properties of Fe2−xTixO3/Fe2O3 thin films with x = 0.44 grown on Al2O3 (0001)

Research paper by Teresa Dennenwaldt, Maike Lübbe, Michael Winklhofer, Alexander Müller, Markus Döblinger, Hasan Sadat Nabi, Maria Gandman, Tzipi Cohen-Hyams, Wayne D. Kaplan, Wolfgang Moritz, Rossitza Pentcheva, Christina Scheu

Indexed on: 11 Sep '14Published on: 11 Sep '14Published in: Journal of Materials Science

#### Abstract

The interface between hematite (α-Fe2IIIO3) and ilmenite (FeIITiO3), a weak ferrimagnet and an antiferromagnet, respectively, has been suggested to be strongly ferrimagnetic due to the formation of a mixed valence layer of Fe2+/Fe3+ (1:1 ratio) caused by compensation of charge mismatch at the chemically abrupt boundary. Here, we report for the first time direct experimental evidence for a chemically distinct layer emerging at heterointerfaces in the hematite—Ti-doped-hematite system. Using molecular beam epitaxy, we have grown thin films (~25 nm thickness) of α-Fe2O3 on α-Al2O3 (0001) substrates, which were capped with a ~25 nm thick Fe2−xTixO3 layer (x = 0.44). An additional 3 nm cap of α-Fe2O3 was deposited on top. The films were structurally characterized in situ with surface X-ray diffraction, which showed a partial low index orientation relationship between film and substrate in terms of the [0001] axis and revealed two predominant domains with $$(0001) _{{{\text{Fe}}_{2} {\text{O}}_{3} }} \;||\;(0001) _{{{\text{Al}}_{2} {\text{O}}_{3} }},$$ one with $$[10\bar{1}0]_{{{\text{Fe}}_{2} {\text{O}}_{3} }} \;||\;[10\bar{1}0]_{{{\text{Al}}_{2} {\text{O}}_{3} }},$$ and a twin domain with $$[01\bar{1}0]_{{{\text{Fe}}_{2} {\text{O}}_{3} }} \;||\;\;[10\bar{1}0]_{{{\text{Al}}_{2} {\text{O}}_{3} }}.$$ Electron energy loss spectroscopy profiles across the Fe2−xTixO3/Fe2O3 interface show that Fe2+/Fe3+ ratios peak right at the interface. This strongly suggests the formation of a chemically distinct interface layer, which might also be magnetically distinct as indicated by the observed magnetic enhancement in the Fe2−xTixO3/α-Fe2O3/Al2O3 system compared to the pure α-Fe2O3/Al2O3 system.


text:
Advertisement Remove all ads

# Find the Sum of First 22 Terms of an Ap in Which D = 7 and 22nd Term is 149. - Mathematics

Find the sum of first 22 terms of an AP in which d = 7 and 22nd term is 149.

Advertisement Remove all ads

#### Solution

d = 7

a22 = 149

S22 = ?

an = a + (n − 1)d

a22 = a + (22 − 1)d

149 = a + 21 × 7

149 = a + 147

a = 2

S_n = n/2(a+a_n)

=22/2(2+149)

= 11(151)= 1661

Is there an error in this question or solution?
Advertisement Remove all ads

#### APPEARS IN

NCERT Class 10 Maths
Chapter 5 Arithmetic Progressions
Exercise 5.3 | Q 7 | Page 113
Advertisement Remove all ads

#### Video TutorialsVIEW ALL [5]

Advertisement Remove all ads
Share
Notifications

View all notifications

Forgot password?
Course


text:
Dependencies Version
SatPy 0.9.0
PyResample 1.10.1
Trollimage 1.5.3
PyKdtree 1.3.1

In December 2012 EUMETSAT extended the EARS services to include a new service with the purpose of supporting European users with cloud information from polar orbiting satellites in near real time.

This EARS-NWC service provides the parameters Cloud Mask, Cloud Type and Cloud Top Temperature and Height (CTTH) as derived using the Polar Platform System (PPS) software package from the NWC SAF. The products are derived from AVHRR data received at the EARS core stations with a reception coverage including Europe and the North Atlantic. Products are disseminated on EUMETCast (EUMETSAT data channel 1) with a timeliness better than 30 minutes, and available in netCDF4 format. The geolocation information is available on a tie-point grid and stored in each product.

At the moment the satellites contributing to the service are Metop-B and NOAA-19.

## Loading and concatenating the cloud type granules¶

In [1]:
from satpy import Scene
from satpy import find_files_and_readers
from datetime import datetime

DATA_DIR = "/home/a000680/laptop/Nordisk/EARS_NWC/data/case_20180314/ears"

start_time=datetime(2018, 3, 14, 10, 5),
end_time=datetime(2018, 3, 14, 10, 11),
scene = Scene(filenames=myfiles)

(0, ['/home/a000680/usr/src/satpy/satpy/etc/readers/nc_nwcsaf_pps.yaml'], ['nc_nwcsaf_pps'])

/usr/lib64/python2.7/_abcoll.py:391: FutureWarning: iteration over an xarray.Dataset will change in xarray v0.11 to only include data variables, not coordinates. Iterate over the Dataset.variables property instead to preserve existing behavior in a forwards compatible manner.
return list(self)
/usr/lib64/python2.7/_abcoll.py:391: FutureWarning: calling len() on an xarray.Dataset will change in xarray v0.11 to only include data variables, not coordinates. Call len() on the Dataset.variables property instead, like len(ds.variables), to preserve existing behavior in a forwards compatible manner.
return list(self)
/home/a000680/.local/lib/python2.7/site-packages/h5py/__init__.py:36: FutureWarning: Conversion of the second argument of issubdtype from float to np.floating is deprecated. In future, it will be treated as np.float64 == np.dtype(float).type.
from ._conv import register_converters as _register_converters

Now we have loaded and concatenated the ct field of the Cloudtype product granules in the time window given by the start amd end times above

In [2]:
print(scene['ct'].data.shape)
print(scene['ct'].data.compute())

(4320, 2048)
[[ 2  2  2 ...  6  6  6]
[ 2  2  2 ...  6  6  6]
[ 2  2  2 ... 10  6  6]
...
[ 7  6  6 ...  2  2  2]
[ 7  6  6 ...  2  2  2]
[ 7  6  6 ...  2  2  2]]

Also the geolocation has been unpacked. That is the the full resolution geolocation information has been recreated from the tie point grid by interpolating and extrapolating the longitudes and latitudes on the tie point grid. This is accomplished using the python-geotiepoints tool, but this is transparent to the user:

In [3]:
print(scene['ct'].area.lats.shape)

(4320, 2048)

Now let’s visualise the cloudtype data using the Nowcasting SAF palette read from the file:

In [4]:
scene.load(['cloudtype'])
scene.show('cloudtype')

Out[4]:
<trollimage.xrimage.XRImage at 0x7f2b283864d0>

# Load all CTTH granules, concatenate, reproject, generate composite image, and save to disk¶

In [5]:
from glob import glob
import os.path

In [6]:
DATA_DIR = "/home/a000680/laptop/Nordisk/EARS_NWC/data/case_20180314/ears"

## Make a list of all CTTH files in the directory, both bzipped and unpacked ones:¶

In [7]:
myfiles = glob(os.path.join(DATA_DIR, "*CTTH_C*.nc.bz2"))
myfiles = myfiles + glob(os.path.join(DATA_DIR, "*CTTH_C*.nc"))

## Generate the scene object¶

In [8]:
scene = Scene(filenames=myfiles, reader='nc_nwcsaf_pps')

## Load the cloud height composite image¶

In [9]:
scene.load(['cloud_top_height'])

/home/a000680/.local/lib/python2.7/site-packages/dask/local.py:271: RuntimeWarning: invalid value encountered in less_equal
return func(*args2)
/home/a000680/.local/lib/python2.7/site-packages/dask/local.py:271: RuntimeWarning: invalid value encountered in greater_equal
return func(*args2)

## Resample the data to the pre-defined "euron1" area¶

In [10]:
lscn = scene.resample('euron1', radius_of_influence=5000)

No handlers could be found for logger "pyresample.kd_tree"

In [11]:
lscn.show('cloud_top_height')

Out[11]:
<trollimage.xrimage.XRImage at 0x7ffa384eae50>

## Save the image to file¶

In [11]:
dt_start = lscn.attrs['start_time'].strftime('%Y%m%dT%H%MZ')
dt_end = lscn.attrs['end_time'].strftime('%Y%m%dT%H%MZ')
lscn.save_dataset(
'cloud_top_height', filename='./ears_nwc_ctth_{starttime}_{endtime}.png'.format(starttime=dt_start, endtime=dt_end))


text:
# Calculate: 24^2\div2^5+10^3\div40+2^2 \times 3^3 \times 5^2\div30^2

## Expression: ${24}^{2}\div{2}^{5}+{10}^{3}\div40+{2}^{2} \times {3}^{3} \times {5}^{2}\div{30}^{2}$

Write the division as a fraction

$\frac{ {24}^{2} }{ {2}^{5} }+{10}^{3}\div40+{2}^{2} \times {3}^{3} \times {5}^{2}\div{30}^{2}$

Write the division as a fraction

$\frac{ {24}^{2} }{ {2}^{5} }+\frac{ {10}^{3} }{ 40 }+{2}^{2} \times {3}^{3} \times {5}^{2}\div{30}^{2}$

Write the division as a fraction

$\frac{ {24}^{2} }{ {2}^{5} }+\frac{ {10}^{3} }{ 40 }+\frac{ {2}^{2} \times {3}^{3} \times {5}^{2} }{ {30}^{2} }$

Factor the expression

$\frac{ {6}^{2} \times {4}^{2} }{ {2}^{5} }+\frac{ {10}^{3} }{ 40 }+\frac{ {2}^{2} \times {3}^{3} \times {5}^{2} }{ {30}^{2} }$

Factor the expression

$\frac{ {6}^{2} \times {4}^{2} }{ {2}^{5} }+\frac{ {10}^{3} }{ 40 }+\frac{ {2}^{2} \times {3}^{3} \times {5}^{2} }{ {15}^{2} \times {2}^{2} }$

Write the expression in exponential form with the base of $2$

$\frac{ {6}^{2} \times {2}^{4} }{ {2}^{5} }+\frac{ {10}^{3} }{ 40 }+\frac{ {2}^{2} \times {3}^{3} \times {5}^{2} }{ {15}^{2} \times {2}^{2} }$

Factor the expression

$\frac{ {6}^{2} \times {2}^{4} }{ {2}^{5} }+\frac{ {10}^{3} }{ 40 }+\frac{ {2}^{2} \times {3}^{3} \times {5}^{2} }{ {5}^{2} \times {3}^{2} \times {2}^{2} }$

Cancel out the common factor ${2}^{2}$

$\frac{ {6}^{2} \times {2}^{4} }{ {2}^{5} }+\frac{ {10}^{3} }{ 40 }+\frac{ {3}^{3} \times {5}^{2} }{ {5}^{2} \times {3}^{2} }$

Evaluate the power

$\frac{ 36 \times {2}^{4} }{ {2}^{5} }+\frac{ {10}^{3} }{ 40 }+\frac{ {3}^{3} \times {5}^{2} }{ {5}^{2} \times {3}^{2} }$

Simplify the expression

$\frac{ 36 }{ 2 }+\frac{ {10}^{3} }{ 40 }+\frac{ {3}^{3} \times {5}^{2} }{ {5}^{2} \times {3}^{2} }$

Cancel out the common factor ${5}^{2}$

$\frac{ 36 }{ 2 }+\frac{ {10}^{3} }{ 40 }+\frac{ {3}^{3} }{ {3}^{2} }$

Simplify the expression

$\frac{ 36 }{ 2 }+\frac{ {10}^{3} }{ 40 }+3$

Cancel out the common factor $2$

$18+\frac{ {10}^{3} }{ 40 }+3$

$21+\frac{ {10}^{3} }{ 40 }$

Evaluate the power

$21+\frac{ 1000 }{ 40 }$

Cancel out the common factor $40$

$21+25$

$46$


text:
## Semi-isometric CR immersions of CR manifolds into Kähler manifolds and applications.(English)Zbl 07417794

Summary: We study the second fundamental form of semi-isometric CR immersions from strictly pseudoconvex CR manifolds into Kähler manifolds. As an application, we give a precise condition for the CR umbilicality of real hypersurfaces, extending an well-known theorem by Webster on the nonexistence of CR umbilical points on generic real ellipsoids. As other applications, we extend the linearity theorem of Ji-Yuan for CR immersions into spheres with vanishing second fundamental form to the important case of three-dimensional manifolds, and prove the “first gap” theorem in the spirit of Webster, Faran, Cima-Suffridge, and Huang for semi-isometric CR immersions into a complex Euclidean space of “low” codimension. Our new approach to the linearity theorem is based on the study of the first positive eigenvalue of the Kohn Laplacian.

### MSC:

 32W10 $$\overline\partial_b$$ and $$\overline\partial_b$$-Neumann operators 32V20 Analysis on CR manifolds 32V40 Real submanifolds in complex manifolds
Full Text:

### References:

 [1] R. BEALS and P. C. GREINER, “Calculus on Heisenberg Manifolds”, Annals of Mathemat-ics Studies, Vol. 119. Princeton University Press, Princeton, NJ, 1988. [2] E. BEDFORD and P. FEDERBUSH, Pluriharmonic boundary values, Tôhoku Math. J. (Sec-ond Series) 26 (1974), 505-511. · Zbl 0298.31012 [3] D. M. BURNS and C. L. EPSTEIN, Embeddability for three-dimensional CR-manifolds, J. Amer. Math. Soc. 3 (1990), 809-841. · Zbl 0736.32017 [4] S. CHANILLO, H.-L. CHIU and P. YANG, Embeddability for 3-dimensional Cauchy-Riemann manifolds and CR Yamabe invariants, Duke Math. J. 161 (2012), 2909-2921. · Zbl 1271.32040 [5] J.-H. CHENG and J. M. LEE, The Burns-Epstein invariant and deformation of CR struc-tures, Duke Math. J. 60 (1990), 221-254. · Zbl 0704.53028 [6] S.-S. CHERN and J. K. MOSER, Real hypersurfaces in complex manifolds, Acta Math. (1974) 133 (1974), 219-271. [7] J. A. CIMA and T. J. SUFFRIDGE, A reflection principle with applications to proper holo-morphic mappings, Math. Ann. 265 (1983), 489-500. · Zbl 0525.32021 [8] J. P. D’ANGELO, “Several Complex Variables and the Geometry of Real Hypersurfaces”, Studies in Advanced in Mathematics, Vol. 8, CRC Press, Boca Raton, FL, 1993. [9] S. DRAGOMIR, On pseudohermitian immersions between strictly pseudoconvex CR mani-folds, Amer. J. Math. 117 (1995), 169-202. · Zbl 0827.32020 [10] S. DRAGOMIR and G. TOMASSINI, “Differential Geometry and Analysis on CR Mani-folds”, Progress in Mathematics, Vol. 246, Birkhäuser, Boston, 2006. [11] P. EBENFELT, X. HUANG and D. ZAITSEV, Rigidity of CR-immersions into spheres, Comm. Anal. Geom. 12 (2004), 631-670. · Zbl 1066.32033 [12] P. EBENFELT and D. N. SON, Umbilical points on three dimensional strictly pseudoconvex CR manifolds I: manifolds with U (1)-action, Math. Ann. 368 (2017), 537-560. · Zbl 1375.32056 [13] P. EBENFELT, D. N. SON and D. ZAITSEV, A family of compact strictly pseudoconvex hypersurfaces in C 2 without umbilical points, Math. Res. Lett. 25 (2018) 75-84. · Zbl 1408.32033 [14] J. J. FARAN, The linearity of proper holomorphic maps between balls in the low codimen-sion case, J. Differential Geom. 24 (1986), 15-17. · Zbl 0592.32018 [15] J. J. FARAN, The nonimbeddability of real hypersurfaces in spheres, Proc. Amer. Math. Soc. 103 (1988), 902-904. · Zbl 0656.32015 [16] S. GALLOT, D. HULIN and J. LAFONTAINE, “Riemannian Geometry”, Universitext, Springer-Verlag, Berlin, third edition, 2004. · Zbl 0636.53001 [17] C. R. GRAHAM and J. M. LEE, Smooth solutions of degenerate Laplacians on strictly pseudoconvex domains, Duke Math. J. 57 (1988), 697-720. · Zbl 0699.35112 [18] X. HUANG, On a linearity problem for proper holomorphic maps between balls in complex spaces of different dimensions, J. Differential Geom. 51 (1999), 13-33. · Zbl 1042.32008 [19] X. HUANG and S. JI, Every real ellipsoid in C 2 admits CR umbilical points, Trans. Amer. Math. Soc. 359 (2007), 1191-1204. · Zbl 1122.32027 [20] S. JI and Y. YUAN, Flatness of CR submanifolds in a sphere, Sci. China Math. 53 (2010) 701-718. · Zbl 1204.32024 [21] J. M. LEE, Pseudo-Einstein structures on CR manifolds, Amer. J. Math. 110 (1988), 157-178. · Zbl 0638.32019 [22] J. M. LEE and R. MELROSE, Boundary behavior of the complex Monge-Ampère equation, Acta math. 148 (1982), 159-192. [23] S.-Y. LI, G.-J. LIN and D. N. SON, The sharp upper bounds for the first positive eigenvalue of the Kohn-Laplacian on compact strictly pseudoconvex hypersurfaces, Math. Z. 288 (2018), 949-963. · Zbl 1396.32017 [24] S.-Y. LI and H.-S. LUK, An explicit formula for the Webster pseudo-Ricci curvature on real hypersurfaces and its application for characterizing balls in C n , Comm. Anal. Geom. 14 (2006), 673-701. · Zbl 1113.32008 [25] S.-Y. LI and D. N. SON, CR-Analogue of Siu-@@-formula and applications to rigidity prob-lem for pseudo-hermitian harmonic maps, Proc. Amer. Math. Soc. 147 (2019), 5141-5151. · Zbl 1429.32037 [26] S.-Y. LI and D. N. SON, The Webster scalar curvature and sharp upper and lower bounds for the first positive eigenvalue of the Kohn-Laplacian on real hypersurfaces, Acta Math. Sin. (Engl. Ser.) 34 (2018), 1248-1258. · Zbl 1404.32071 [27] S.-Y. LI, D. N. SON and X. WANG, A new characterization of the CR sphere and the sharp eigenvalue estimate for the Kohn Laplacian, Adv. Math. 281 (2015), 1285-1305. · Zbl 1319.53032 [28] T. TAKAHASHI, Minimal immersions of Riemannian manifolds, J. Math. Soc. Japan 18 (1966), 380-385. · Zbl 0145.18601 [29] N. TANAKA, “A Differential Geometric Study on Strongly Pseudoconvex Manifolds”, Lec-tures in mathematics, Vol. 9, Kinokuniya Book-store Co., Tokyo 1975. [30] X. WANG, On a remarkable formula of Jerison and Lee in CR geometry, Math. Res. Lett. 22 (2015), 279-299. · Zbl 1320.32040 [31] S. M. WEBSTER, Pseudo-hermitian structures on a real hypersurface, J. Differential Geom. 13 (1978), 25-41. · Zbl 0379.53016 [32] S. M. WEBSTER, The rigidity of CR hypersurfaces in a sphere, Indiana Univ. Math. J. 28 (1979), 405-416. · Zbl 0387.53020 [33] S. M. WEBSTER, Holomorphic differential invariants for an ellipsoidal real hypersurface, Duke Math. J. 104 (2000), 463-475. · Zbl 0971.32019 [34] Wien, Austria son.duong@univie.ac.at
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
## Rubik's Cube Comb

For discussing Olympiad Level Combinatorics problems
Fahim Shahriar
Posts: 138
Joined: Sun Dec 18, 2011 12:53 pm

### Rubik's Cube Comb

A $3 \times 3$ Rubik's cube has different colors on its each sides.
In how many different ways the cube can be arranged ?
Name: Fahim Shahriar Shakkhor
Notre Dame College

nafistiham
Posts: 829
Joined: Mon Oct 17, 2011 3:56 pm
Location: 24.758613,90.400161
Contact:

### Re: Rubik's Cube Comb

see the permutations part.
$\sum_{k=0}^{n-1}e^{\frac{2 \pi i k}{n}}=0$
Using $L^AT_EX$ and following the rules of the forum are very easy but really important, too.Please co-operate.

Fahim Shahriar
Posts: 138
Joined: Sun Dec 18, 2011 12:53 pm

### Re: Rubik's Cube Comb

I'm saying what I did.

The centers are fixed. Excluding centers there 20 small cubes outside. 8 of them are in the corners and 12 in middles.

12 middles can be arranged in 12! ways and as each middles has two colors, permutation for middles = $12!\times 2$

8 corners can be arranged in 8! ways and each has 3 colors. (According to rules they should be arranged in $3!=6$ ways. But actually they can be in 3 ways. Do it practically.) So permutations of corners = $8!\times 3$

TOTAL = $12!\times 2\times 8!\times 3$
Last edited by Phlembac Adib Hasan on Mon Jan 28, 2013 3:01 pm, edited 1 time in total.
Reason: use \times instead of x(to show a $\times$)
Name: Fahim Shahriar Shakkhor
Notre Dame College

sakibtanvir
Posts: 188
Joined: Mon Jan 09, 2012 6:52 pm
Location: 24.4333°N 90.7833°E

### Re: Rubik's Cube Comb

How?? Shouldn't it be $12! \times 2^{12} \times 8! \times 3^{8} ???$
I don't know If I am right or wrong...For the corner pieces the approach should be as below:
"There are $8$ corner pieces,Each piece having $3$ colors.For our advantage,at first we assume that each corner piece is painted with a distinct color(Not with the combination of 3).The permutation will be $8!$.Now we consider their position at this time we assume the corner pieces painted with 3 colors(their original state!).Name the Pieces as below:$A,B,C,D,E,F,G,H$.Notice,$A$ can hold 3 positions,$B$ can hold 3 positions,.....,H can hold 3 positions.So the total number of arrangement for the corner pieces will be $8! \times 3^{8}$.I have spent those word just to clarify my idea.
An amount of certain opposition is a great help to a man.Kites rise against,not with,the wind.

Fahim Shahriar
Posts: 138
Joined: Sun Dec 18, 2011 12:53 pm

### Re: Rubik's Cube Comb

@sakibtanvir. You're right. I did the permutation for only one piece and forgot to do for others. Thanks to correct me..

So finally we get
$12! \times 2^{12} \times 8! \times 3^{8}$
Name: Fahim Shahriar Shakkhor
Notre Dame College


text:
# Let $f:[0,a]\rightarrow[0,\infty)$ be a continuous function such that $f(t)\leq e^{\int_{0}^{t}f(s)ds}-1$ for all $t\in[0,a]$. Prove that $f\equiv0$

Let $$f:[0,a]\rightarrow[0,\infty)$$ be a continuous function such that $$f(t)\leq e^{\int_{0}^{t}f(s)ds}-1$$ for all $$t\in[0,a]$$. Prove that $$f\equiv0$$.

I have thought like this: Assume $$F(t)=\int_{0}^{t}f(s)ds\implies F'(t)=f(t)$$ . Then $$F'(t)\leq e^{F(t)}-1$$. Now how can proceed.

Since $$F'(t) \leq e^{F(t)} -1$$ rearranging and multiplying we get the inequality $$e^{-F(t)-t} (F'(t)+1) \leq e^{-t}$$ $$\implies \frac {d}{dt} e^{-F(t)-t} \geq \frac {d}{dt} e^{-t}$$ $$\implies e^{-F(t)-t} \geq e^{-t}$$ $$\implies e^{F(t)} \leq 1$$ $$\implies F(t)\leq 0$$ But we know $$F$$ is non negative and hence $$F\equiv 0$$ So $$f\equiv 0$$


text:
# 11.03 Volume of pyramids and cones

Lesson

### Pyramids

A pyramid is formed when the vertices of a polygon are projected up to a common point (called a vertex).  A right pyramid is formed when the apex is perpendicular to the midpoint of the base.

We want to be able to calculate the volume of a pyramid. Let's start by thinking about the square based pyramid.

#### Exploration

Think about a cube, with side length $s$s units.  Now lets divide the cube up into 6 simple pyramids by joining all the vertices to the midpoint of the cube.

This creates $6$6 square based pyramids with the base equal to the face of one of the sides of the cube, and height, equal to half the length of the side.

$\text{Volume of Cube }=s^3$Volume of Cube =s3

$\text{Volume of one of the Pyramids }=\frac{s^3}{6}$Volume of one of the Pyramids =s36

Now lets think about the rectangular prism, that is half the cube.  This rectangular prism has the same base as the pyramid and the same height as the pyramid.

Now the volume of this rectangular prism is $l\times b\times h=s\times s\times\frac{s}{2}$l×b×h=s×s×s2= $\frac{s^3}{2}$s32

We know that the volume of the pyramid is $\frac{s^3}{6}$s36 and the volume of the prism with base equal to the base of the pyramid and height equal to the height of the pyramid  is $\frac{s^3}{2}$s32.

 $\frac{s^3}{6}$s36 $=$= $\frac{1}{3}\times\frac{s^3}{2}$13×s32 Breaking $\frac{s^3}{2}$s32 into two factors $\text{Volume of pyramid}$Volume of pyramid $=$= $\frac{1}{3}\times\text{Volume of rectangular prism}$13×Volume of rectangular prism Using what we found in the diagrams $=$= $\frac{1}{3}\times\text{Area of base}\times\text{height }$13×Area of base×height Previously shown

So what we can see here is that the volume of the pyramid is $\frac{1}{3}$13 of the volume of the prism with base and height of the pyramid.

Of course this is just a simple example so we can get the idea of what is happening.

Volume of Pyramid

$\text{Volume of Pyramid }=\frac{1}{3}\times\text{Area of base }\times\text{Height }$Volume of Pyramid =13×Area of base ×Height

#### Practice questions

##### question 1

Find the volume of the square pyramid shown.

##### question 2

A small square pyramid of height $4$4 cm was removed from the top of a large square pyramid of height $8$8 cm forming the solid shown. Find the exact volume of the solid.

##### question 3

A right square pyramid has a height of $24$24 cm and a volume $2592$2592 cm3. What is its base length of the pyramid?

### Cones

The volume of a cone has the same relationship to a cylinder as we just saw that a pyramid has with a prism.

That is:

Volume of Right Cone

$\text{Volume of Right Cone }=\frac{1}{3}\times\text{Area of Base }\times\text{Height of cylinder}$Volume of Right Cone =13×Area of Base ×Height of cylinder

$V=\frac{1}{3}\pi r^2h$V=13πr2h

The mathematical derivation of the formula for the volume of a cone is beyond this level of mathematics, so for now it is suffice to know the rule and how to use it.

#### Practice questions

##### QUESTIOn 4

Find the volume of the cone shown.

##### QUESTION 6

Find the radius of a cone that has a volume of $12441.02$12441.02 cm3 and a height of $30$30 cm.


text:
Precalculus (6th Edition) Blitzer

$\frac{11\pi}{6}$ radians
To convert degrees to radians, multiply degrees by $\frac{\pi}{180 °}.$ So 330° = 330 ° x $\frac{\pi}{180 °}$ = $\frac{11\pi}{6}$ radians.