text:
\section{Introduction}
The design of efficient procedures for searching in a discrete structure is a
fundamental problem in discrete mathematics \cite{Ahlswede,Aigner} and computer science \cite{Knuth}.
Searching is a basic primitive for building and managing operations of an information system as ordering,
updating, and retrieval.
The typical example of a search procedure is binary search which allows to
retrieve an element in a sorted list of size $n$ by only looking at $O(\log n)$
elements of the list.
If no order can be assumed on the list, then it is known that any procedure
will have to look at the complete list in the worst case.
Besides these two well characterized extremes, extensive work has also been
devoted to the case where  the underlying structure of the search space is a partial order.
Partial orders can be used to model lack of information on the totally ordered
elements of the search space \cite{Linial} or can naturally arise from the
relationship among the elements of the search space,
like in hierarchies used to model knowledge representation \cite{Wermelinger},
or in tree-like indices for information retrieval of large databases \cite{Ben-Asher}.
For more about applications of tree search see below.

In this paper, we focus on the case where the underlying search space is a
tree-like partially ordered set and tests have nonuniform costs.
We investigate the following problem.

\begin{figure}
\centering
\includegraphics{prob-defi.pdf}
\caption{An example of the tree search problem,
$T$ is the input tree and $D$ is a decision tree with $cost(D) = 7 = cost^D(a) = cost^D(c)$.
If the vertices of the tree $T$ represent the parts of a device to assemble,
the decision tree corresponds to the assembly procedure that at time 0 joins $e$ with $b$;
then at time $3$ joins $b$ with $c$ and $e$ with $g$.
At time $4$ the joining of  $d$ with $c$ and $e$ with $f$ is started.
Finally, at time $6$ part $a$ is joined with part $c$ and the procedure ends by time $7$.}
\label{fig:problem-defi}
\end{figure}

\noindent
{\sc The Tree Search Problem with non-uniform costs}

{\em Input}: A tree $T=(V, E)$ with non-negative rational costs assigned to the edges
defined by a $c : e \in E \mapsto c(e) \in \mathbb{Q}$.

{\em Output}: A strategy that minimizes (in the worst case) the cost spent to identify
an initially unknown vertex $x$ of $T$ by using {\em edge queries}.
An {\em edge query} $e = \{u, v\} \in E$ asks for the subtree $T_u$ or $T_v$
which contains $x$, where $T_u$ and $T_v$ are the
connected components of $T-e$, including the vertex $u$ and $v$ respectively.
The cost of the query $e$ is $c(e)$.
The cost of identifying a vertex $x$ is the sum of the costs of the queries asked.

\smallskip

More formally, a strategy for the Tree Search Problem with nonuniform costs
over the tree $T$ is a  \emph{decision tree} $D$ which is a rooted binary tree
with $|V|$ leaves where every leaf $\ell$
is associated with one vertex $v \in V$ and every internal node\footnote{For
the sake of avoiding confusion between the input tree and the decision tree, we
will reserve the term vertex for the elements of $V$ and the term $node$ for
the vertices of the decision tree $D$.}
$\nu \in V(D)$ is associated with one test $e = \{u, v\} \in E$.
The outgoing edges from  $\nu$ are associated with the possible outcomes of the
query, namely, to the case where the vertex to identify lies in $T_u$ or $T_v$ respectively.
Every vertex has at least one associated leaf.
The actual identification process can be obtained  from $D$ starting with the
query associated to the root and moving towards the leaves based on the answers received.
When a leaf $\ell$ is reached, the associated vertex is output
(see Fig.~\ref{fig:problem-defi} for an example).

Given a decision tree $D$, for each vertex $v\in V(T)$,
let $\mathit{cost}^D(v)$ be the sum of costs of the edges associated
to nodes on the path from the root of $D$ to the leaf identifying $v$.
This is the total cost of the queries performed when the
strategy $D$ is used and $v$ is  the vertex to be identified.

In addition, let the cost of $D$ be defined by
$$
\mathit{cost}(D) = \max_{v\in V(T)} \mathit{cost}^D(v).
$$
This is the worst-case cost of identifying a vertex of $T$ by the decision tree $D$.
The optimal cost of a decision tree for the instance represented by the tree $T$
and the cost assignment $\ensuremath{\mathbf{c}}$ is given by
$$
\mathit{OPT}(T,\ensuremath{\mathbf{c}}) = \min_{D} \mathit{cost}(D),
$$
where the $\min$ is over all decision trees $D$ for the instance $(T, c)$.

\smallskip
\noindent
{\bf Previous results and related work.}
The Tree Search Problem has been first studied under the name of
tree edge ranking \cite{IyeRatVij91,laTGreSch95,Lam98optimaledge,Makino2001,Dereniowski08},
motivated by multi-part product assembly.
In \cite{Lam98optimaledge} it was shown that in the case where the tests have uniform cost,
an optimal strategy can be found in linear time.
A linear algorithm for searching in a tree with uniform cost was also provided in \cite{Mozes}.
Independently of the above articles, the first paper where the problem is
considered in terms of searching in a tree is \cite{Ben-Asher}, where the more
general problem of searching in a poset was also addressed.

The variant considered here in which the costs of the tests are non-uniform
was first studied by Dereniowski \cite{Dereniowski06} in the context of edge ranking.
In this paper, the problem was proved NP-complete for trees of diameter at most 10.
Dereniowski also provided  an $O(\log n)$ approximation algorithm.
In \cite{CicaleseJLV12} Cicalese et al.\  showed that the tree search problem
with non-uniform costs is strongly NP-complete already for input trees of
diameter 6, or maximum degree 3, moreover, these results are tight.
In fact, in \cite{CicaleseJLV12}, a polynomial time algorithm computing the
optimal solution is also provided for diameter 5 instances and an $O(n^2)$
algorithm for the case where the input tree is a path.
For arbitrary trees, Cicalese et al.\ provided
an $O(\frac{\log\ n}{\log \log \log n})$-approximation algorithm.

\smallskip
\noindent
{\bf Our Result.} Our contribution is both on the algorithmic and on the complexity side.
On the one hand, we provide a new approximation algorithm for the tree search problem with non-uniform costs
which improves upon the best known guarantee given in \cite{CicaleseJLV12}.
In Section 3 we will prove the following result.

\begin{theorem}\label{thm:main}
There is an $O(\log n / \log\log n)$-approximation algorithm
for the Weighted Tree Search Problem that runs in polynomial time in $n$.
\end{theorem}

In addition, we show that the tree search problem with non-uniform costs is NP-hard already
when the input tree is a spider\footnote{By \emph{spider} we mean a tree
with at most one vertex of degree greater than 2.}
of diameter 6.

\smallskip

\noindent
{\bf More about applications.}
We discuss some scenarios in which
the problem of searching in trees with non-uniform costs naturally arises.

Consider the problem of locating a buggy module in a program in which the
dependencies between different modules can be represented by a tree.
For each module we can verify the correct behavior independently.
Such a verification may consist in checking, for instance, whether all branches
and statements in a given module work properly. For different modules, the cost
of using the checking procedure can be different (here the cost might refer to
the time to complete the check). In such a situation, it is important to device
a debugging strategy that minimizes the cost incurred in order to locate the
buggy module in the worst case.

Checking for consistency in different sites keeping distributed copies of
tree-like data structures (e.g., file systems) can be performed
by maintaining at each node some check sum information about the subtree rooted at that node.
Tree search can be used to identify the presence of ``buggy nodes'', and
efficiently identifying the  inconsistent part in the structure, rather than
retransmitting or exhaustively checking  the whole data structure.
In \cite{Ben-Asher}, an application of this model in the area of information retrieval is also described.

Another examples comes from a class of problems which is in some sense dual to the previous ones:
deciding the assembly schedule of a multi-part device.
Assume that the set of pairs of parts that must be assembled together can be represented by a tree.
Each assembly operation requires some (given) amount of time to be performed
and while assembling two pieces, the same pieces cannot  be involved in any other assembly operation.
At any time different pairs of parts can be assembled in parallel.
The problem is to define the schedule of assembly operations
which minimize the total time spent to completely assembly the device.
The schedule is an edge ranking of the tree defined by the assembly operations.
By reversing the order of the assembly operation in the schedule we obtain a
decision tree for the problem of searching in the tree of assembly operation
where each edge cost is equal to the cost of the corresponding assembly.

\section{Basic lower and upper bounds}

In this section we provide some preliminary results which will be useful in the
analysis of our algorithm presented in the next section. We introduce some
lower bounds on the cost of the optimal decision tree for a given instance
of the problem. We also recall  two exact algorithm for constructing optimal
decision tree which were given in  \cite{CicaleseJLV12}. The first is an
exponential time dynamic programming algorithm which works for any input tree.
The second is a  quadratic time algorithm for instances
where the input tree is a path.
Finally, we show a construction of 2-approximation decision trees for spider graphs.

\smallskip

Let $T$ denote the input tree and $\ensuremath{\mathbf{c}}$ the cost function.
It is not hard to see that, given a decision tree $D$ for $T$ we can extract
from it a decision tree for the instance of the problem
defined on a subtree $T'$ of $T$ and the restriction of $\ensuremath{\mathbf{c}}$ to the vertices in $T'$.
For this, we can repeatedly apply the following operation: if in $D$ there is a
node $\nu$ associated with an edge $e = \{u, v\}$, such that $T_u$ (reps.
$T_v$) is included $T - T'$ then remove the node $\nu$ together with the
subtree rooted at the child of $\nu$ corresponding to the case
where the vertex to identify is in $T_u$ (resp.\ $T_v$).
Let $D'$ be the resulting decision tree when the above step cannot be performed anymore.
Then, clearly $cost(D', \ensuremath{\mathbf{c}}) \leq cost(D, \ensuremath{\mathbf{c}})$. We have shown the following (also observed in \cite{CicaleseJLV12}).

\begin{lemma}\label{lem:subtree}
Let $T'$ be a subtree of $T$. Then, $\mathit{OPT}(T, \ensuremath{\mathbf{c}}) \geq \mathit{OPT}(T', \ensuremath{\mathbf{c}})$.
\end{lemma}

Another immediate observation is that for a given input tree $T$, the value
$OPT(T, \ensuremath{\mathbf{c}})$ is monotonically non-decreasing with respect to the cost
of any edge. This is recorded in the following.
\begin{lemma}\label{lem:decreasec}
Let $\ensuremath{\mathbf{c}}$ and $\ensuremath{\mathbf{c}}'$ be cost assignments on a tree $T$ such that
$\ensuremath{\mathbf{c}}'(e) \leq \ensuremath{\mathbf{c}}(e)$ for every $e \in E(T)$.
Then, $\mathit{OPT}(T,\ensuremath{\mathbf{c}}) \geq \mathit{OPT}(T,\ensuremath{\mathbf{c}}')$.
\end{lemma}

The next proposition shows that subdividing an edge cannot decrease the cost of the optimal decision tree.

\begin{proposition}\label{prop:contract}
Let $\ensuremath{\mathbf{c}}$ be a cost assignment on a tree $T$.
Let $v\in V(T)$ have exactly two neighbors $u_1,u_2 \in V(T)$.
If $T'$ is obtained from $T-v$ by adding the edge $\{u_1,u_2\}$ and
$\ensuremath{\mathbf{c}}'$ is obtained from $\ensuremath{\mathbf{c}}$ by setting $\ensuremath{\mathbf{c}}'(u_1u_2) = \min\{\ensuremath{\mathbf{c}}(u_1v),\ensuremath{\mathbf{c}}(u_2v)\}$
then $\mathit{OPT}(T,\ensuremath{\mathbf{c}}) \geq \mathit{OPT}(T',\ensuremath{\mathbf{c}}')$.
\end{proposition}

The proof of Proposition~\ref{prop:contract} is deferred to the appendix.

The following two results  from \cite{CicaleseJLV12} provide exact algorithms for the construction of
optimal strategies.
More precisely, Proposition \ref{prop:exp}
provides  an exponential dynamic programming based algorithm for general trees.
Theorem \ref{thm:path} gives an $O(n^2)$ time algorithm for
the special case where the input tree is a path
and will be useful in the analysis of our main algorithm and also in the following lemma
regarding the spider tree.

\begin{proposition}[\cite{CicaleseJLV12}]\label{prop:exp}
Let $T$ be an edge-weighted tree on $n$ vertices.
Then an optimal decision tree for $T$ can be constructed in $O(2^n n)$ time.
\end{proposition}

The following theorem was proved by Cicalese et al.\ in \cite{CicaleseJLV12}
and will be useful later in the analysis of our algorithm and also in the following lemma
regarding the spider tree.

\begin{theorem}[\cite{CicaleseJLV12}]\label{thm:path}
There is an $O(n^2)$ time algorithm that constructs an optimal decision tree $D$ for
a given weighted path on $n$ vertices.
\end{theorem}

Note that for a star $T$ any decision tree $D$ has the same cost, since all the edges have to be asked in the worst case.
Hence, for a tree $T$ such that there is only one node with degree greater than $1$
we have $OPT(T, \ensuremath{\mathbf{c}}) = \sum_{e \in E(T)} c(e),$ for any cost function $\ensuremath{\mathbf{c}}$.

\begin{definition}
A tree $T$ is a \emph{spider} if there is at most one vertex in $T$ of degree greater than two.
We refer to this vertex as the {\em head} (or {\em center}) of the spider.
Moreover,  each path from the head of the spider to one of the leaves will be referred to as  a {\em leg} of the spider.
\end{definition}

\begin{lemma}\label{lem:spider}
Let $T$ be a spider.
Then there is an algorithm which computes a 2-approximate decision tree $D$ for $T$
and runs in time $O(n^2)$.
\end{lemma}

\begin{proof}
If $T$ is a path, then by Theorem~\ref{thm:path} there exists an algorithm computing
the optimal decision tree in $O(n^2)$ time.
Assume $T$ is not a path. Then $T$ contains exactly one vertex $v$ of degree at least three.
Let $S_v$ be the star induced by $v$ and the vertices adjacent to $v$. Let us denote by $w_1,\ldots,w_k$
 the vertices adjacent to $v$, where $k=\deg(v)$.
By Theorem~\ref{thm:path}, for every $i \in  \{1,\dots,k\}$ we construct the optimal decision tree $D_i$
for the path component $C_i$ of $T-v$ containing $w_i$ in time $O(|C_i|^2)$.
Note that the total running time for construction of $D_1,\dots,D_k$ is $O(n^2)$.
Finally, for $S_v$ we compute the optimal decision tree $D_v$ (in $O(n)$ time).
The decision tree $D$ for $T$ is obtained from $D_v$
by replacing the node corresponding to $w_i$ by the root of $D_i$ for every $i \in \{1,\dots,k\}$.
Clearly, the algorithm runs in $O(n^2)$ time
and $cost(D) \leq \mathit{OPT}(S_v, \ensuremath{\mathbf{c}})  + \max_{1\leq i\leq k}\{\mathit{OPT}(C_i, \ensuremath{\mathbf{c}})\}\leq 2\mathit{OPT}(T, \ensuremath{\mathbf{c}})$.
The last inequality follows since  by Lemma~\ref{lem:subtree} both $\mathit{OPT}(S_v, \ensuremath{\mathbf{c}})$ and
$\max_{1\leq i\leq k}\{\mathit{OPT}(C_i, \ensuremath{\mathbf{c}})\}$ are  lower bounds on  $OPT(T, \ensuremath{\mathbf{c}})$.
\qed\end{proof}

\section{The Algorithm}

Let $n$ be the size of the input tree  and $t = 2^{\lfloor\log\log n\rfloor+2}$
be a parameter fixed for the whole run of the algorithm.
It holds that  $2 \log n\le t\le 4 \log n$.

The basic idea of our algorithm is to construct a subtree $S$ of the input tree $T$ such that:
(i) we can construct a decision tree for $S$ whose cost is
at most a constant times the cost of an optimal decision tree for $S$;
(ii) each component of $T -S$ has size not larger than $T/t$.

This will allow us to build a decision tree for $T$ by assembling the decision tree for $S$
with the decision trees recursively constructed for the components of $T-S$.
The constant approximation guarantee on $S$ and the fact that, due to the size of the subtrees on which we recurs,
we need at most $O(\frac{\log n}{\log \log n})$ levels of recursion to show
that our algorithm gives an $O(\frac{\log n}{\log \log n})$ approximation.

\smallskip

\noindent
{\bf The subtree $S$.}
We iteratively build subtrees $S_0 \subset S_1 \subset \cdots \subset S_t \subseteq T$.
Starting with the empty tree $S_0$,
in every iteration $i \in \{1,\dots,t\}$ we pick a centroid $x_i$ of the largest connected component of the forest $T-S_{i-1}$.
The subtree $S_i$ is set to be the minimal subtree containing $x_i$ and $S_{i-1}$.
If for some $i$ we have that $S_i=T$, then we set $S = S_i = T$ and we stop the iterations.
If all $t$ iterations are completed then we set $S=S_t$.

By definition, the \emph{centroid} of a tree $T$ is a vertex $v$ such that any maximal component of $T- v$
has size at most $|T|/2$.
Therefore, we have the following lemma---which  establishes (ii) above.

\begin{lemma} \label{lem:H-components}
If $H$ is a maximal connected component of $T - S$, then $|H|\le |T|/\log n$.
\end{lemma}
\begin{proof}

We prove by induction on $k$ that after $2^k$ iterations all maximal components of $T-S_{2^k}$ have size at most $|T|/2^{k-1}$.
Let $k = 0$. We observe that by the definition of centroid, after $1 = 2^{k}$
iterations all components of $T-S_1$ have size at most $|T|/2 \leq |T|/ 2^{k-1} = 2|T|$.
This establishes the basis of our induction.

Now fix some $k > 0$ and assume (induction hypothesis) that after $2^{k-1}$ iterations all maximal components
of $T-S_{2^{k-1}}$ have size at most $|T|/2^{k-2}$.
Among these there are at most $2^{k-1}$ components that have size at least $|T|/2^{k-1}$.
In the next $2^{k-1}$ iterations we will choose a centroid in each of these components, one by one.
Choosing a centroid in a component $H$ splits $H$ into parts that have size at most half of $H$,
thus after $2^k=2^{k-1}+2^{k-1}$ steps all components of $T-S_{2^k}$ have size at most $|T|/2^{k-1}$.

Thus, if the process of constructing $S$ is stopped after $t=2^{\lfloor\log\log n\rfloor+2}$ iterations
all components have size at most $|T|/2^{\lfloor\log\log n\rfloor+1}\le |T|/\log n$.
On the other hand, if the process of constructing $S$ is stopped at some iteration $i < t$ then it means that $S =T$ and,
trivially, we have $|H| = 0$.
\qed\end{proof}

\smallskip
\noindent
{\bf The Decision Tree for $S$.}
Let $X$ contain all $x_i$ for $i\in \{1,\dots,t\}$ and vertices of degree at least three in $S$.
Note that $|X|\le 2t+1$.
Let $P_{u,v}$ be the path of $T$ whose endpoints are vertices $u$ and $v$.

We define an auxiliary tree $Y$ on the vertex set $X$.
Vertices $u,v \in X$ form an edge of $Y$
if $u$ and $v$ are the only vertices of $X$ of the path $P_{u,v}$ in $T$ with endpoints $u$ and $v$.
Let $e_{uv} = \arg \min_{e\in P_{u,v}} \ensuremath{\mathbf{c}}(e)$ (the edge of $P_{u,v}$ with minimal cost) and
$\ensuremath{\mathbf{c}}_Y(uv) = c(e_{uv})$.
Let $Z=\bigcup_{uv\in E(Y)} e_{uv}$. By Proposition~\ref{prop:exp},
we can compute an optimal decision tree $D_Y$ for $Y$  in $O(2^{2t}t)$ which is polynomial in $n$.

Let $D_X$ be obtained from $D_Y$ by changing the label of every internal node
from $uv$ to $e_{uv}$, for each $uv \in E(Y)$.
The tree $D_X$ is not a decision tree for $S$, however,
leaves of $D_X$ correspond to connected components of $S-Z$.
Notice that $cost(D_X) = cost(D_Y) = OPT(Y, c_Y)$.

Since every connected component $C$ of $S-Z$ contains at most one vertex of degree at least three,
every such component is a spider. By Lemma~\ref{lem:spider}, a decision tree $D_C$ for each such component $C \in S-Z$
can be computed in $O(n^2)$ time with approximation ratio 2.

We can now obtain the decision tree $D_S$ for $S$ by replacing each leaf in $D_X$ with the decision tree
for the corresponding component in $S-Z$. We have

\begin{eqnarray*} \label{eq:S-approx}
\frac{cost(D_S)}{OPT(S,c)} & \leq &\frac{cost(D_X) + \max_{C \in S-Z} cost(D_C)}{OPT(S, c)} \\
 & \leq &\frac{cost(D_X)}{OPT(Y, c_Y)} + \max_{C \in S-Z} \frac{cost(D_C)}{OPT(C, c)} \leq 3,
\end{eqnarray*}
where the second inequality holds because of  $OPT(Y, c_Y) \leq OPT(S, c)$ (given by Proposition \ref{prop:contract}) and
$OPT(C, c) \leq OPT(S, c)$ (given by Lemma \ref{lem:subtree}).

\smallskip
\noindent
{\bf Assembling the pieces in the Decision Tree for $T$}.
Let  $v$ be a vertex in $S$ with a neighbor not in $S$, let $S_v$ be the star induced by $v$ and its neighbors outside $V(S)$.

Let $D_v$ be a decision tree for $S_v$ (notice that they all have the same cost).
For every neighbor $w \not\in V(S)$ of $v$ we compute recursively the decision tree $D_w$ for
the component $H_w$ of $T-S$ containing $w$ and replace the leaf node of $D_v$
associated to $w$ with the root of $D_w$.
The result is a decision tree  $D'_v$ for the subtree of $T$ including $S_v$
and all the components of $T-S$ including some neighbor $w$ of $v$.

In order to obtain a decision tree $D_T$ for $T$ we now modify $D_S$ as follows:
for each vertex $v$ in $S$ with a neighbor not in $S$, replace the leaf in
$D_S$ associated with $v$ with the decision tree $D'_v$ computed above.

\begin{figure}
    \centering
    \includegraphics[width=\hsize]{fig-alg.pdf}
   \caption{The tree $S$, the important set of vertices $X$ and the auxiliary tree $Y$}
   \label{fig:alg}
\end{figure}

\noindent
{\bf The Approximation guarantee for $D_T$.}
Let $\mathit{APP}(T)=\frac{cost(D_T)}{OPT(T,c)}$ denote the approximation ratio obtained by Algorithm~\ref{alg} on the instance
$(T, c)$. Let $\mathit{APP}(k)=\max_{|T|\le k} \mathit{APP}(T)$.

\begin{lemma}\label{lem:apx}
For any tree $T$ on $n$ vertices and any cost assignment $\ensuremath{\mathbf{c}}$, we have $\mathit{APP}(T) \leq 4 \log n/\log\log n$.
\end{lemma}

\begin{proof}
For every $1 \leq k \leq n$ let $f(k)= \max\{1, 4\log k/\log\log n\}$.
We shall prove by induction on $k$ that $APP(k)\le f(k)$, which implies the statement of the lemma.

If $|T|\le t$ then our algorithm builds an optimal decision tree,
thus $APP(k)=1\le f(k)$ for $k\le t$.
This establishes the induction base.

Choose a tree $T$ as in the statement of the lemma such that $APP(T) = APP(n)$.
Let $S$ and $Y$ be the substructures of $T$ built by the algorithm as described above.
Let $\tilde{V}$ be the set of vertices of $S$ with some neighbor not in $S$.
For each $w \not \in V(S)$ let $H_w$ be the maximal component of $T-S$ containing $w$.
Let ${\cal H}$ be the set of maximal components of $T-S$.
Then, by construction, we have
\begin{eqnarray}
\mathit{APP}(T)&=&\frac{\mathit{ALG}(T)}{\mathit{OPT}(T)} \leq \frac{cost(D_S) + \max_{v \in \tilde{V}} cost(D_v) + \max_{w \not \in V(S)} cost(D_w)}{OPT(T,c)}  \label{eq:a}\\
&\leq& \frac{cost(D_S)}{OPT(S,c)} + \max_{v \in \tilde{V}} \frac{cost(D_v)}{OPT(S_v, c)} + \max_{w \not \in V(S)} \frac{cost(D_w)}{OPT(H_w, c)} \label{eq:b}\\
&\leq& 4+ \max_{H \in {\cal H}} \frac{ALG(H)}{OPT(H, c)} =  4+ \max_{H\in {\cal H}}\{\mathit{APP}(H)\} \label{eq:c}\\
&\leq& 4 + \max_{H \in {\cal H}} f(|H|) \leq 4 +  f(|T|/\log n)  \label{eq:d} \\
&=&  4 + f(n/\log n) =  4 + \frac{4 \log \frac{n}{\log n}}{\log \log n} =  \frac{4 \log n}{\log \log n},  \label{eq:e}
\end{eqnarray}
where

\begin{itemize}
\item  (\ref{eq:b}) follows from (\ref{eq:a}) because of $OPT(S,c), OPT(S_v), OPT(D_w) \leq OPT(T,c)$ (Lemma \ref{lem:subtree})
\item  (\ref{eq:c}) follows from (\ref{eq:b}) because of (\ref{eq:S-approx}) and
the fact that any decision tree for a star $S_v$ has the same cost, hence also equal to $OPT(S_v, c)$
\item  in (\ref{eq:d}) the first inequality  follows by induction and the second inequality by Lemma~\ref{lem:H-components}
\item  (\ref{eq:e}) follows from (\ref{eq:d}) because of $|T| = n$ and the definition of $f(\cdot)$.
\end{itemize}
\qed\end{proof}

\begin{lemma}\label{lem:time}
For a tree $T$ on $n$ vertices, the Algorithm~\ref{alg} builds the decision tree $D_T$ in time polynomial in $n$.
\end{lemma}

The proof of Lemma~\ref{lem:time} is deferred to the appendix.
Lemma~\ref{lem:time} and Lemma~\ref{lem:apx} now imply Theorem~\ref{thm:main}.

\algnewcommand{\LineComment}[1]{\State \(\triangleright\) #1}
\begin{varalgorithm}{TS}
\caption{Tree Search Algorithm}\label{alg}
\begin{algorithmic}[1]
\small
\Function{Main}{tree $T$, cost $\ensuremath{\mathbf{c}}$}
\State $t \gets 2^{\lfloor \log \log |T| \rfloor +2}$
\State {\bf Output} $D \gets TreeSearch(T, \ensuremath{\mathbf{c}}, t)$
\EndFunction
\Function{TreeSearch}{tree $T$, costs $\ensuremath{\mathbf{c}}$, t}
\State {\bf	if} $|T|\le t$ {\bf then}  {\bf return} optimal decision tree $D_X$ for $T$ computed by Proposition~\ref{prop:exp}
	\State $S_0 \gets \emptyset$   \label{alg:sbuild1}
   \ForAll{$i=1,\dots,t$}
      \State $x_i \gets$ centroid of a maximum size connected component of $T-S_{i-1}$
      \State $S_i \gets$ smallest subtree containing $x_i$ and $S_{i-1}$
   \EndFor   \label{alg:sbuild2}
   \State $X \gets \{x_i|\; i=1,\dots,t\} \cup \{v\in V(S)|\; \deg_S(v)\ge 3\}$
   \State $Y \gets$ tree on vertex set $X$, $uv\in E(Y)$ iff $X\cap P_{u,v}=\{u,v\}$
   \ForAll {$uv\in E(Y)$}
      \State $\ensuremath{\mathbf{c}}_Y(uv) \gets \min_{e\in P_{u,v}} \ensuremath{\mathbf{c}}(e)$
      \State $e_{uv} \gets$ edge of $P_{u,v}$ with minimum cost
   \EndFor
   \State $Z \gets \bigcup_{uv\in E(Y)} e_{uv}$
   \State Compute optimal decision tree $D_Y$ for $(Y, \ensuremath{\mathbf{c}}_Y)$ by Proposition~\ref{prop:exp}
   \ForAll {$uv\in E(Y)$}
      \State Replace label of $uv$ in $D_Y$ by $e_{uv}$
   \EndFor
   \ForAll {$H$ connected component of $Y-Z$}
      \LineComment{$H$ contains at most one vertex of degree 3 or more, i.e., $H$ is a spider}
      \State Compute 2-approximate decision tree $D_H$ for $H$ by Lemma~\ref{lem:spider}   \label{alg:spider}
      \State replace the leaf $k\in D_Y$ corresponding to $H$ by the root of $D_H$
   \EndFor
      \ForAll {$v\in V(S)$ with a neighbor not in $S$}
      \State $S_v \gets$ star induced by $v$ and its neighbors outside of $V(S)$ \label{alg:sv}
			\State Construct decision tree $D_v$ for $(S_v,\ensuremath{\mathbf{c}})$
      \ForAll {$w\in S_v\setminus \{v\}$}
         \State $U \gets $ connected component of $T-S$ containing $w$
         \State $D_w \gets TreeSearch(U, \ensuremath{\mathbf{c}}, t)$   \label{alg:recurse}
	 \State leaf of $D_v$ corresponding to $w$ $\gets$ root of $D_w$
      \EndFor
       \State replace the leaf of $D_Y$ associated to $v$ by the root of $D_v$
  \EndFor

   \Return $D_Y$
\EndFunction

\end{algorithmic}
\end{varalgorithm}
\normalsize

\section{Tree search with non-uniform costs is NP-hard on spider graphs}
In this section we provide a new hardness result which contributes to refining
the separation between hard and polynomial instances of the tree search problem
with non-uniform costs.
We show that the problem of finding a minimum cost decision tree is  hard even
for instances where the input graph is a spider and the length of every leg is three.

\smallskip

Our reduction is from the Knapsack Problem.
The input of the Knapsack Problem is given by:
a knapsack size $W$, a desired value $V$, and  a set of items, $(v_i,w_i)_{i \in [m]}$,
where $v_i$ is the value and $w_i$ is the weight of the $i$th item.
The goal is to decide whether there exists a subset of items of total value at least $V$
and whose weight can be contained in the knapsack,
i.e., whether there is a $J \subseteq [m]$ such that $\sum_{j\in J} w_j \le W$ and $\sum_{j\in J} v_j \ge V$.

From a knapsack instance we construct an instance $(S, \ensuremath{\mathbf{c}})$ for the tree search problem with non-uniform costs,
where $S$ is a spider.
Each leg will correspond to an item.
Therefore, we will speak of the $i$th leg as the leg corresponding to the $i$th item.
For each $i \in [m]$, the $i$th leg will consist of three edges:
the one closest to the head will be called {\em femur} (and referred to as $f_i$),
the middle edge will be called {\em tibia} (and referred to as $t_i$),
the end will be called the {\em tarsus} (and referred to as $s_i$).
The cost function is defined as follows:
For each $i \in [m]$, we set $c(f_i) = v_i + w_i$; $c(t_i) = v_i$ and $c(s_i) = N$, with
$N$ a large number to be determined later.

It is easy to see that in an optimal strategy,
for each $i \in [m]$ the edge $s_i$ is always queried last among the edges on the $i$th leg.
Given a decision tree $D$,
we denote by $I^D$ the set of indices of the legs for which,
in $D$, the node associated with the query to the tibia is an ancestor of the node associated with the
query to the femur.
Then,
we have the following proposition,
whose proof is deferred to the appendix.
\begin{proposition} \label{prop:knap-dectreestructure}
There is an optimal decision tree $D$ with $I^D \neq \emptyset$ and such that:

(i) for any $i \in I^D$ and $j \in [m] \setminus I^D$ the node of D associated
with the $j$th femur is an ancestor of the node associated with the $i$th tibia.

(ii) for any $i, j \in I^D$ the node of D associated with the $i$th tibia is an
ancestor of the node associated with the $j$th femur.

\end{proposition}

By this proposition, we can assume that in the optimal decision tree $D$
for at least one leg of the spider the first edge queried is a tibia. In addition, in $D$,
there is a root to leaf path where first all femurs not in $I^D$ are queried,
then all tibias in $I^D$ and finally all femurs in $I^D$
(see Fig.~\ref{fig:knap-spider} in Appendix for a pictorial example).
Then, the cost of such a decision tree is given by the maximum between the cost of the leaf on the legs with index in $I^D$
and whose tibia is queried as last,
and the cost of the central vertex of the spider.
It follows that the cost of the optimal solution is given by the following expression
$$
OPT(S, \ensuremath{\mathbf{c}}) = \min_{\emptyset \subset I \subseteq [m]} \max \left\{N + \sum_{i \not \in I} (v_i+w_i) + \sum_{i \in I} v_i ;
\sum_{i \in I} v_i + \sum_{i \in [m]} (v_i + w_i) \right\}
$$

If we set $N = \sum_{i \in [m]} (v_i + w_i) - W - V$, then we can rewrite the above expression as follows:
$$
OPT(S, \ensuremath{\mathbf{c}}) = \min_{\emptyset \subset I \subseteq [m]} \max \left\{N + \sum_{i \not \in I} w_i + \sum_{i \in [m]} v_i ;
N + W + V  + \sum_{i \in I} v_i  \right\}
$$

Now, it is easy to see that $OPT(S, \ensuremath{\mathbf{c}})$  is at most $\sum_{i \in [m]} v_i+N+W$ if an only if
$\sum_{i \not \in I} w_i \leq W$ and $\sum_{i \not \in I} v_i \geq V$, that is, if and only if
the set $[m] \setminus I$ is a solution for the knapsack problem.
Note that as the values and weights are unrelated, we can indeed choose $N$ as big as necessary for the above reduction,
which is clearly polynomial in the size of the input to the knapsack problem.

\section*{Acknowledgment}
We are very grateful to Bal\'azs Patk\'os for organizing $5^{\mathrm{th}}$  Eml\'ekt\'abla Workshop
where we collaborated on this paper.

redpajama_set_name: RedPajamaArXiv


Cnr 34th and 8th Ave.
Opened in 1929 and was the biggest hotel in New York for many years. One of the best places to see Big Bands in the 30's such as Benny Goodman (see photo). Ali would use the place after fighting across the street at the Garden. Nikola Tesla went crazy and died there (not sure if AC/DC ever stayed there. Ha!!). Castro stayed there.
Tesla's tale is intriguing. In his room #3327, he kept a safe filled with patents and super-secret ideas. One, his "Death Ray", he described thus: "The nozzle would send concentrated beams of particles through the free air, of such tremendous energy that they will bring down a fleet of 10,000 enemy airplanes at a distance of 200 miles from a defending nation's border and will cause armies to drop dead in their tracks." Goodness. Upon his death his body and the safe were whisked away. The safe was impounded by the FBI and entered Top Secret status, never to be seen again. Who knows if the Death Ray was true or not, but Tesla should definitely have turned his hand to Science Fiction.
If you like Art Deco, this place is a must. The only draw-back is there is no cafe or food service in the lobby (there's a diner though attached) so I sat there all morning and spent not a dime. It's a busy place, right on 8th Avenue and the vibe is very touristy. I sat amongst piles of suitcases and folks waiting for their coaches and cabs. Still, I was there to work and fortunately the muse flowed well sans coffee.


My Freedom Cafe is ACES's online portal where parents can keep track of deposits, items sold to their child, and submit an application for free and reduced lunch!
To sign up, click the sign up link below the log in button.
If a district code is necessary, please enter F1214.
Once an account is created, link children to the account by clicking the Add Student link that appears on the page. The child's first name, last name, date of birth, and student ID will need to be entered.
Click the Submit Application link to submit the free and reduced lunch application.
If any issues are experienced linking a child to an account, please contact Nicole Jacinthe at njacinthe@aventuracharter.org for assistance.


Well, the all new electric car is going to hit the markets soon and this will make you jump out of your skin if you are a car enthusiast to the core!
To all the car passionates out there! Here comes something special for you: the all new 2017 Chevrolet BOLT EV First drive which are the all new electric car for everyone who loves the cars a lot. Bolt EV has just reinvented what the electric vehicle should be. This Bolt EV was also named Motor Trend's 2017 Car of the Year. On other side, if we talk about some old is gold: classic vintage cars, then we can find these cars are are one of a kind and catches the eyes in fraction of seconds.
This car will have the lavish exterior to its class performance, which has a quite capacious interior and advanced technologies.
-> Electronic precision shifting is included in this.
->The tires of the car are the Michelin self-sealing tires.
-> This model includes 10.2 inch diagonal color touchscreen.
->It also has the rear vision camera.
->This model includes the complete features of LT model.
->It has the real mirror camera in the car.
->Surround vision is just perfect.
->This car has the leather-wrapped heated steering wheel.
It is just very simple pull for the paddle in the car which is there on your steering wheel as such. With this technology you can slow down the car without making any use of the actual brake pedal. This also helps in making the energy into higher electricity and then transfer the same into the battery itself.
This completely means that the braking power is there in your hands only. There are used cars for sale in different brands which you must know. If you are living in UAE, then you can acquire the luxurious cars of different brands, you can purchase your dream car from across the country and formulate them in a luxurious way.
This is also the best feature which helps you in transferring the energy into the battery when you had to slow down the vehicle. When you opt for going by car on the low mode at any damn speed then you will have to come to the complete stop just by simply lifting your foot in car off the accelerator. This also implies that you can use your brakes less and just help in increasing the range.
These 2 amazing features of one paddle and also the declaration may be just limited when the battery is completely charged up or just somewhat cold. You need to always use your brakes pedal and kit there is a requirement for stopping quickly. See the owner's manual for the complete details regarding One-Pedal Driving and also about the Ragen in Demand.
This enables you to quickly and electronically make the selection of gears which also provides a quick response. So there is no such shifter included which creates the open front passenger spacing at the time of providing seamless and the best experience. You can also buy used cars of Chevrolet or other brands that looks just ravishing.
There are also various car rental services all over the world. If you are looking for the best car rental service, then you can choose the best car rental services in Abu Dhabi and Dubai, UAE.
Once you have charged this car for half an hour then this car will go on till 25 miles per hour.
Through this the car will run for 90 miles per one hour of the charging time as such.
Through this you will be able to personalize the settings as per your schedule.
So this is the upcoming car which is the first electric car: 2017 Chevrolet BOLT EV First drive that will leave the car enthusiasts completely amazed by the best features. In this new electric car you can also know about your power too as to how much energy is being used by your classy Chevrolet Bolt EV electric car and accordingly you can proceed for driving.
Some Chevrolet fans are also the youth who just can't afford the luxe cars and so they opt for buying used cars of the brand Chevrolet and unleash their passion for driving the car at high speed which makes their adrenaline rush for sure and this will help them to make their passion of driving come true.
There are various online classified apps which helps you to get the best deals in the used cars of different brands which are your favorite to the core and makes you feel over the moon. Cars for sale in Dubai are available in different price range.


We'll Make You A Cash Offer Today! Here's How The Process Works.
We are Tennessee home buyers and we specialize in buying Brentwood houses fast. We pay cash to buy them fast, and we'll even buy them in any condition. We'll make you a fair offer and close as quickly as you'd like (even in as little as 5 days).
Selling your house through an agent is a well-known option but did you know there's another way to sell your Brentwood… that's faster?
You can sell directly to us at Middle Tennessee Home Buyers. We're not agents, we're buyers. We buy Brentwood houses fast… in any condition.
No matter what situation you're facing, we at Middle Tennessee Home Buyers are ready to help you! We buy houses in Brentwood and all surrounding TN areas. We buy houses fast, in any condition or situation, and we have the funds available to buy your house from you right away.
So, if you want to put money in your pocket and walk away from that unwanted property, we are ready to help you with our "Sell My House Fast Brentwood" Service.


IADE understands the special challenges faced by women in running businesses in Timor-Leste. Our trainers and counsellors are experienced at working with women groups, and are sensitive to gender issues. Many of our training and counselling sessions include discussion and exercises which aim to raise awareness of the challenges faces by women in business, and to offer strategies and solutions.
In addition we offer a special training programme called GET AHEAD which combines training in entrepreneurship with a gender perspective . Since many women in rural Timor-Leste have not had the opportunity to get a full education, this programme has been adapted to be able to be delivered to low-literacy participants. Our programme is focussed on providing practical examples of how women owned business can overcome obstacles to the development of their business.
If your organisation wants help to inspire women to achieve more, contact IADE's training team today.


The 12 gîte Nataïwatch bungalows are nestled in a tropical forest in the Isle of Pines.
The 12 Nataïwatch bungalows are at Kanuméra Bay. Guillaume and his wife have 35 years of experience in gîtes and are the ideal hosts to ensure your stay in very special. The gîte is in the heart of a tropical forest and just steps from the beach, the perfect location to relax with family, friends or a partner. A campsite is also available for a complete change of scene.
Pirogue Take a pirogue trip, sailing on the turquoise waters of the lagoon.


text:
Tommy Fury pulls out of Jake Paul fight, citing medical reasons
Posted Tue 7 Dec 2021 at 1:19am Tuesday 7 Dec 2021 at 1:19am Tue 7 Dec 2021 at 1:19am
Tommy Fury says his fight with Jake Paul is off. (Getty Images: Jason Miller)
abc.net.au/news/tommy-fury-pulls-out-of-jake-paul-fight/100679526
Tommy Fury, the half-brother of heavyweight champion Tyson Fury, says he has been forced to withdraw from his upcoming fight with YouTuber-turned-boxer Jake Paul due to a severe chest infection and a broken rib.
Tommy Fury says he is "heartbroken" to be pulling out of the fight with Jake Paul
He hopes to reschedule the fight for early next year
Paul will instead fight former UFC welterweight champion Tyron Woodley
Fury was due to face Paul on December 18 in Tampa, Florida.
He won on the undercard of Paul's August fight against former UFC welterweight champion Tyron Woodley.
Fury comes from a long line of boxers but has also looked to grow his celebrity outside the sport and appeared on the British reality show Love Island in 2019.
"I am absolutely heartbroken that I have been forced to withdraw from my fight with Jake Paul due to a bacterial chest infection and broken rib," the 22-year-old said in a tweet posted by his promoter Frank Warren.
"I can't express how disappointed I am and I really do hope we can get this fight rescheduled in the New Year, I want this fight to still happen more than anything."
With Fury pulling out, Paul said he would have a rematch with Woodley.
Paul and Woodley's cruiserweight fight in August ended in a split-decision victory for Paul.
"I am giving him [Woodley] $US500,000 ($710,000) extra if he can knock me out," Paul said in a video on Twitter.
Posted 7 Dec 2021 7 Dec 2021 Tue 7 Dec 2021 at 1:19am

redpajama_set_name: RedPajamaCommonCrawl


text:
AMERICAN SENIOR HIGH SCHOOL EXCELLING WITH STRENGTH THROUGH DIVERSITY!
Welcome back! The 2022 – 2023 school year is upon us and unlike previous years, it promises to be one that American Senior High School has never seen before. The effort and work that the custodial staff has put forth has made a difference in the overall aesthetics of the school site, the school looks fantastic. The cleanliness and upkeep of both the interior and exterior of the building is nothing less than spectacular. The halls are shinning, and the grounds are well-manicured. American is truly showing its colors – red, white, and blue!
Teachers have been preparing to receive the students for a successful school year. Teachers have been given guidelines promoting standards and expectations. In addition, they have been made aware of new initiatives launched by the district, M-DCPS, as well as by the school. Similarly, the data generated during the 2021 – 2022 school year has been analyzed and discussed to ensure that students are accurately placed and that instructional practices needed to help students move in a positive direction and achieve their academic goals are imbedded in the classroom.
As it has been in years past, the administrative team has had a long summer, yet a very fruitful one. The administrative team has been working diligently to provide parents, students, and staff with an institution that is worthy of their expectations. Apart from having the building cleaned and ready to receive students, the administrative team has been working hard to find teachers to replace open positions vacated by former teachers. In all, 9 new teachers, 1 new custodian and 1 new treasurer, some new to the profession and others transfers from other locations, have been hired at American Senior for the upcoming year. This continues to give American a different look and an opportunity to grow and improve on our abilities to best serve our student body.
This school year, as in previous ones, the number of courses offered at ASHS has improved. Students will now have the opportunity to take a Dual Enrollment course under a new partnership with Miami Dade College, 8 Advanced Placement (AP) courses, 5 Pre-AICE (Cambridge) courses, and up to 11 Cambridge courses. It is important to note that the 8-period day has brought additional offerings to the school. All in all, American continues to find ways to improve and excel.
Similarly, American remains committed to finding ways to improve student behavior. Students are encouraged to dress according to the student dress code and uniform policy, speak with respect to fellow classmates and adults, and treat all members of the American Senior High School community with respect. As in the past, I urge parents to work with the school community to get a unified message to our students. Parents are asked to please continue to support their children and help them become responsible and contributing members of our society.
Finally, parents, it is imperative that students are present in school all day, every day. If students are not in school, they are not learning; they are missing out on vital instruction and enriching peer discussions. Overall, the outlook of the new school year looks extremely encouraging.
I am looking forward to a successful 2022 – 2023 school year
Principal, Stephen E. Papp
stephenpapp@dadeschools.net


DOVER — Anthony Fisher bolted off the mat and into the waiting arms of coach Aaron Harris.
In mere seconds he was enveloped by Dover High teammates and friends who ran out of the stands for a hug.
Fisher continued down toward one of the doors of the gym, shaking hands and slapping high-fives with a growing crowd on his way. But Fisher kept heading to the hallway, he was looking for someone.
He finally found his teammate, Tykwan Joyner who was crouched down on the white wall near the entranceway. Fisher knelt down and gave Joyner, who had just lost in his championship match two bouts early, a hug.
Fisher's upset for the 132-pound title at the Henlopen Conference wrestling championship on Saturday was the start of a banner day for Dover.
Nick Lee was next on the mat at 138 pounds. Like Fisher, he was going against a top seed.
Fisher's task was a little tougher though. He had to knock off a defending state champion, Smyrna's Chase Archangelo.
Watching Fisher do that gave Lee even more confidence and he earned a 2-1 decision. That gave Dover multiple individual conference champions for the first time since the Senators had five in 1994.
Smyrna took home the team title and had the second-most individual champions with three. Sussex Central had four winners — Rashad Stratton (126), Justin Bennett (145), Brandon Bautista (152) and Lucas Hudson (170).
Aside from Dover's two wins, the loudest the gym got was in the final match of the night between Smryna's Tony Wuest and Caesar Rodney's Mike Clavier.
Clavier earned the first two points of the contest with a takedown in the first 30 seconds. Wuest worked for an escape, then when Clavier rushed at him, was able to execute a toss to bring Clavier to his back and record a pin in 55 seconds.
Wuest avenged a loss to Clavier via a decision during a dual meet in the regular season.
That was a theme on Saturday, Fisher had fell to Archangelo twice earlier this year. The first time he faced him, Harris had left a note in his warmup pocket.
Before his final match, Harris called Fisher over on the mat as they both took a knee for some words of encouragement.
Fisher looked to have a 2-1 decision but was called for stalling in the final seconds. It sent the match to overtime and Fisher was able to earn a takedown for the decisive two points much to the delight of the home crowd.
Greg Baum won his first career conference title at 120 pounds and Kalen Wilson earned his second championship to join Wuest as Smyrna's winners. Wuest was also named the tournament's Outstanding Wrestler.
Cam Hayes (113) was the lone winner from Caesar Rodney. Milford had two champions Kenny VanVorst (182) and Dom Hovington (220).
Cape Henlopen's Anthony Caruso won the 106 title as a freshman while Woodbridge's Dom Pierce needed overtime to earn the heavyweight title.


text:
Home » Tim Minchin » 'Matilda' at the Cambridge Theatre, 25th May 2013
'Matilda' at the Cambridge Theatre, 25th May 2013
Monday, May 27, 2013 by londoncitynights
Matilda is practically perfect in every way. It's been a long time since I saw the 1996 film, and longer since I read Roald Dahl's book. It only took about 10 minutes before the memories came flooding back. What I realised this time is that Matilda is basically Stephen King's Carrie for kids. Both stories feature precocious schoolgirls being ground down by authority figures, treated monstrously by their parents and repeatedly publicly humiliated. This intense pressure awakens latent psychic superpowers and the girls go on a roaring rampage of revenge against those that have wronged them.
The image of unleashed femininity telekinetically lashing out against oppression is fertile dramatic ground, both Matilda and Carrie being simultaneously empowering and kind of terrifying. In the end Dahl and King reach quite different conclusions; Carrie White's psychic powers transform her into an id-fuelled blindly raging, self destructive monster, while Matilda Wormwood uses hers for the pursuit of justice, setting right wrongs using precise and careful control.
This idea that control, focus and thoughtfulness is the best way to improve your life runs right through Matilda like the words in a stick of rock. After all, her telekinetic powers only manifest when her pursuit of knowledge becomes stifled, after she's victimised at school and when her library books turn up by her domineering, idiotic father. One of the most important things about Matilda's powers is that they don't appear to be a quirk of birth. Throughout the show characters talk about Matilda having so many brains that they'll escape from her head, Dahl is suggesting that the process of being stifled and repressed, or not being able to communicate your thoughts to receptive ears is like blowing too much air into a balloon. These abilities are a metaphor for the power of knowledge and her control of language. This is the thematic architecture of the production, and it brilliantly informs just about everything on stage.
The first thing you see when you take your seats is a gigantic cloud of blocks, a proscenium arch frozen in mid-explosion. Some of the blocks have letters drawn on them and as you follow the paths of letters across the stage you can decipher words like 'escape' and 'freedom' hidden in what initially seems like a random jumble. This continues in the library sequences; when two columns of books slot together in the centre of the stage they form a crossword that reads 'shush' and 'silent'. Later in Miss Honey's house the floor reads "Home Sweet Home" on the floor. This tactic not only forces the audience to put a bit of mental legwork in to understand the staging, but also simulates the process of learning to read. It's arguable that any adaptation of Matilda is inherently hypocritical, the story makes such a strong case for settling in with a book that not experiencing the story by reading the original text feels off. But the 'reading' of the stage design here somewhat alleviates any whiff of hypocrisy, as does the construction of the musical numbers.
For example, in the 'School Song' number, we see children climbing up a wall on alphabet blocks. Each letter is cleverly worked into the song's lyrics thusly,
"So you think you're A-ble,
To survive this mess by B-ing,
A prince or a princess, you will soon C,
There's no escaping trage-D.",
As the children sing each letter, the corresponding block is slotted into the wall, giving them a new handhold, enabling them to climb ever higher. The concept of children reaching new heights through language is thus realised on stage as a dynamic musical and physical process. This process is present throughout the show in the rapidly paced wordplay of Tim Minchin's lyrics. In every song there are nested double-meanings, innuendos and jokes, prodding us to engage in the process of decoding the lyrics "on the fly" as we listen to the cast machine-gun them out at us. Being nimble in decoding language like this is hugely important, if you just let the songs wash over you without paying close attention you'll miss some of the best jokes in the show. Appropriately for Matilda, the smarter you are and the more you focus on the show, the more you'll get out of it.
The thematic importance of language and careful consideration of wordplay wraps up neatly over the climax. Matilda terrifies the sinister Miss Trunchbull by exposing her past crimes in a message in a message that seems to come from beyond the grave. She levitates a piece of chalk with her mind and writes on the blackboard. This process is a representation of direct translation of thought to language without an intermediary, and Trunchbull's reaction is a stunning example of the impact the right sentence in the right place can have. Soon after this Matilda once again saves the day with her application of language. Her abominable parents are being menaced by Russian gangsters and she begins unexpectedly conversing with them in Russian - which she learnt so she could read Dostoyevsky in the original language. This feels as magical as her telekinesis, yet learning Russian is within all of our grasps if we just applied ourselves hard enough. This purity of message in the staging, the music and the narrative of message elevates Matilda over pretty much every other stage musical I've seen.
But this noble message would fall flat if it weren't for the brilliant cast. Both child and adult performers alike are outstanding. It's a brave decision to make a young child the lynchpin of an enormously elaborate West End production, but to adapt Matilda there's no way around it. If you cast the part of Matilda as a teenager or adult 'playing' a child you'd drain much of the power from the narrative. I'm not sure who played Matilda in the show I saw on the 25th as the part is revolved between three different girls; Elise Blake, Cristina Fray and Chloe Hawthorn. I'm sure they're all fantastic, but whoever it was that I saw pitched themselves expertly between vulnerability and assertiveness, achieving the not-inconsiderable goal of making a prodigious genius likeable without displaying a hint of arrogance.
Good though everyone in the cast is, it's David Leonard's scene-stealing Miss Trunchbull that dominates memories afterwards. She's a monstrous physical presence that fills the theatre every moment she's on stage. There's a hint of Tim Curry's Frank N Furter about this performance, and Leonard plays her with a knowing pantomime campness. Funny though she is, the amount we laugh at her doesn't detract from the cruelty of her sadism. This exaggerated caricature fits perfectly into the world constructed on stage. This is largely because the show is reality filtered through the perceptions of children, good and evil bisected and the motivations of adults mysterious and unknowable.
Of course, though Matilda's world is seen from a child's perspective, it's Roald Dahl's idea of a child's-eye-view. The Dahlian world is one of twisted monsters, twisted exaggerations whose entire character is dominated by their worst features. This is most obviously visible in the children of Charlie and the Chocolate Factory, who (among other things) are embodiments pride, gluttony and envy, it's there in the greedy, stupid and violent giants of The BFG and it's clear as day on stage in Matilda in the Cambridge Theatre. One trick that Dahl mastered was the creation of obviously didactic characters without the lessons they're constructed to convey ever feeling condescending.. Another was his mastery of language and his effortless ability to convey the most noble and aspirational of messages with wicked, satirical humour.
This is all present in spades in Matilda, and much of the reason it's so good is because everyone involved in the production understands this. It's a stunning achievement in musicals, an instant classic and immediately makes everything else on in the West End seem severely lacking in comparison. What a fantastic show.
'Matilda' is on in the Cambridge Theatre, hopefully for the foreseeable future.
Thanks to the Wilcox family for the ticket!
Tags: Cambridge Theatre , Matilda , musical , Roald Dahl , theatre , Tim Minchin
0 Responses to "'Matilda' at the Cambridge Theatre, 25th May 2013"


Search engine activity remained flat in June, with Google hanging onto its immense 65.5 percent market share while other search engines also held their steady audiences.
Second to Google was Yahoo with a static 15.9 percent, then came Microsoft with a slight rise from 14.1 to 14.4, Ask.com with a steady 2.9 and AOL with a slight drop from 1.5 to 1.4, according to comScore, a digital data research firm.
The relatively flat report signifies to us that users are reluctant to change search engines. A Google user is very unlikely to start using AOL for search, and vice-versa. Each search engine is serving its population satisfactorily -- usually a good thing. But Google's 10.9 billion searches and market share dominance creates fear and loathing in its competitors -- and part of the reason it's facing a government probe, with much of it spearheaded by the No.3 of search, Microsoft.


CLICK HERE TO PURCHASE HELEN!
This is the second Griffin Series guitar built for 2018. It comes with a strap and hardshell case. It is loaded with two Kent Armstrong P90s. The body is a carved piece of solid Maple. The neck is Cherry and the fretboard is Ebony with Mother of Pearl Inlays. The inside of the body features our patented Nautilus shell design and is embedded with piezo pickups. You can see this design in the last pictures above. There is a 2nd switch added that blends the piezo pickups with the P90s.
We always name each guitar that we build because we become so close with the guitar through the process. This one was named after one of my best friends' daughter Helen. She showed me a picture of a sea turtle as an example of her favorite color and the stain for this guitar matches the color as close as possible.
CLICK HERE TO PURCHASE ELLEN!
This is a very special version of our Griffin Series Semi-Hollow guitars. It comes with a strap and hardshell case. It is loaded with two Bareknuckle Super Massive humbucker sized P90 pickups. The body is a carved piece of solid Walnut. The neck is Maple and the fretboard is Ziricote with Maple Inlays. The inside of the body features our patent pending Nautilus shell design and is embedded with piezo pickups.
There is a 2nd switch added that blends the piezo pickups with the Bareknuckle HSP90s.
Several people have asked us to make a semi hollow version of our Griffin Series so we finally did it. This is the first Semi Hollow Griffin we have ever built and we love it! It has the same feel as the classic Griffin but is MUCH lighter, and similar to the Escape model, we carved one nautilus shell inside of the body (see the 2nd picture) giving it the signature Howie guitar sound.
You may have noticed that we name every guitar that we build. The story behind the name Nellie is fairly simple. One of my favorite people is John Wooden. This guitar having an all natural wood finish made my wife throw out the name "Wooden." This guitar just needed a woman's name though so we chose John Wooden's wife's name. Nellie it is! Here are the specs.
Wood: Walnut Body and Top, Hard Maple Neck, Quilted Maple Fretboard.
This is one of the latest guitars in the Howie Guitars line up. It is a solid body guitar line we are calling the Griffin Series. It is completely hand built in Longmont, Colorado USA. It is our first double octave guitar with 24 frets and has a much deeper cut away than the escape series for easy access to the high end of the fingerboard. Please check out the video to hear the guitar and learn more about how it was built. This particular guitar has Jimmy Page Les Paul wiring with 4 different push/pull knobs. Here are the specifications….
This is the latest guitar in the Howie Guitars line up. It is a solid body guitar we are calling the Griffin Series. It is completely hand built in Longmont, Colorado USA. It is our first double octave guitar with 24 frets and has a much deeper cut away than the escape series for easy access to the high end of the fingerboard. Please check out the video to hear the guitar and learn more about how it was built. Here are the specifications….


Check out Flex Like Ouu (Remix) by GuapoBandz on Artist Sounds! GuapoBandz is a rapper based in Orlando, Florida. Aiming to bring hype and energy to his listeners, GuapoBandz makes music that gets you through the tough times. Currently working on his first EP, GuapoBandz's latest release is a remix of Flex Like Ouu, with all new original lyrics. The song describes the feeling of being young and in control, doing whatever you want whenever you want. It's a song that will get listeners excited and pumped up, and just goes to show that we can expect great things from this talented artist. Give the track a listen on SoundCloud and keep an eye out for more of GuapoBandz's work.


text:
Category Archives: A People's History, Chapter 11
October 22, 2013 by sg161160
"A DOLLAR A DAY OR KANSAS."
This saying from worker strikes in Kansas puts into perspective how desperate black workers were for an increase in pay. The idea of one leaving the state of Kansas over a pay raise seems outrageous nowadays, but when you consider that these workers had to make ends meet with 75 cents a day it is clear that they had no other option. These protests lasted for seven years before finally coming to a head in 1887, when the Knights of Labor had their greatest influence. The Knights organized ten thousand sugar laborers to strike in Thibodaux, all of them demanding at least a dollar a day. However, the military was called in, martial law was enforced, and on November 22, 30 black laborers were shot and killed, and hundreds more lay wounded. "Lame men and blind women shot; children and hoary-headed grandsires ruthlessly swept down! The Negroes offered no resistance; they could not, as the killing was unexpected. Those of them not killed took to the woods, a majority of them finding refuge in this city…"
I believe Howard Zinn makes mention of this because it shows how adamant the US government was in terms of it's policies on pay for black workers. The fact that they would be willing to kill their own citizens just to quell a protest clearly demonstrates how forceful the government was when it came to civil unrest, even over such a trivial amount of money.
Posted in: A People's History, Chapter 11	|
No matter how much time passes money STILL talks louder by Jessica Bonilla
October 22, 2013 by Jessica Bonilla
Even though by the 1900 Americans have done a great job in advancing itself by building railroads and using electricity. There isn't much of a difference than the world today. Back then just building the railroads were sufficient for the convenience of exploring the U.S and make it back home for dinner, in today's society since we already have the train tracks, we work on extending train lines to help everyday commuters.
Another similarity i found in the reading is how business men J.P Morgan and John D. Rockefeller didn't have to serve their country because they paid their way out of it. As quoted below "Morgan had escaped military service in the Civil War by paying $300 to a substitute. So did John D. Rockefeller, Andrew Carnegie, Philip Armour, Jay Gould, and James Mellon. Mellon's father had written to him that "a man may be a patriot without risking his own life or sacrificing his health". Now a days you hear on the news how celebrities get away with murder and dwi because they have money to pay people off.
I think Howard Zinn uses specific key terms for instance "had escaped military services" so it can be interpreted in a positive way. Instead of using "he didn't have to serve the military or even he paid his way out of serving his country. Howard Zinn portrays Morgan as a successful business man. Usually the world escape is used in cases "she escaped her kidnapper".
Morgan it all
October 21, 2013 by sh144484
"While making his fortune, Morgan brought rationality and organization to the national economy. He kept the system stable. He said: "We do not want financial convulsions and have one thing one day and another thing another day."
In Chapter eleven of " A People's History of the United States", Zinn mentions one of the big names who had formed a monopoly in the late 1800s and early 1900s, J.P.Morgan. Morgan was the son of a banker who sold stocks for railroads, the Union Pacific and the Central Pacific. He made his own wealth by linking railroads to each other, then linking the railroads to banks, and then linking the banks to insurance. At some point, he was in charge of 100,000 miles of railroad and three insurance companies equaling more than a billion dollars in assets. Zinn mentions Morgan along with other big names because as the industry boomed, wealthy American businessmen, as called Robber barons, came into existence. They became most of the upper class, which the government pretended to have neutrality to maintain order for, but was really serving their interests. In other words, they somewhat marked a capitalist state.
President Grover Cleveland a Corporate Puppet?
October 21, 2013 October 21, 2013 by aj161734
"No harm shall come to any business interest as the result of administrative policy so long as I am President … a transfer of executive control from one party to another does not mean any serious disturbance of existing conditions." (Grover Cleveland, Chapter 11)
President Cleveland was a democrat presidential candidate in 1884, he ran against republicans candidate, James Blaine. Common perception throughout the country during the presidential campaign was that the Cleveland would stand against the big corporations and provide relief for the small and new businesses. However, after being elected, Cleveland was seen surrounded by big businesses and their interests to keep the poor and rioting rebels under control. He personally assured the industrialist and corporates that the government during his presidency won't make any such policies that would contradict their interests.
He used every opportunity to help big business and completely neglected the needs for the rest. Howard zinn gives an example of 1887 when Cleveland vetoed a relief bill of $100,000 for the Texas farmers who were suffering from drought but later on during the same year he used his gold surplus to pay off wealthy bondholders at $28 above the $100 value of each bond-a gift of $45 million. Cleveland appointed his chief adviser William Whitney as Secretary of the Navy. William started to work on "steel navy" and started to buy steel from Carnegie's plants at scandalously inflated prices. What Howard Zinn is trying to assert is that Cleveland was truly a corporate puppet, who served the industrialist with all his will. While neglecting small business, such as farmers in Texas who were not able to buy grains and seeds due to drought that had taken over their lands.
Progress and Poverty
October 21, 2013 by ag155492
Trade unions formed an Independent Labor party and nominated for mayor Henry George, the radical economist, whose Progress and Poverty had been read by tens of thousands of workers. George's platform tells something about the conditions of life for workers in New York in the 1880s. It demanded:
that property qualifications be abolished for members of juries.
that Grand Jurors be chosen from the lower-class as well as from the upperclass, which dominated Grand Juries.
that the police not interfere with peaceful meetings.
that the sanitary inspection of buildings be enforced.
that contract labor be abolished in public works.
that there be equal pay for equal work for women.
that the streetcars be owned by the municipal government.
In 1886, as a new mayor was being elected for New York City, the issues for workers were unfathomable if compared to the issues for workers in today's society. Zinn highlights Henry George's platform, and although considered a radical, these conditions accentuate how terrible and inhumane the factories were for workers, as well as the way that workers were treated. For instance, numbers three and six are particularly shocking, three because in this age, unsafe buildings are never, under any conditions, used in any way, and six for the opposite reason: women still do not, in many fields, receive equal pay for equal work, and that this is considered a radical idea along with the other items is surprising. Zinn is trying to place a clear connection between the so-called radical ideas of the late 1800's and the widely accepted ideas of today. While a few of these ideas seem rather minor, they were instrumental to emphasize to make bigger changes, one little change at a time. Although George did not win the election, he place din second, and drew attention to his cause in the process.
The People's Party
October 21, 2013 by ck158542
The People's Party otherwise known as the Populist party was founded in 1891 and dissolved in 1908. The populist party's radical causes were adopted by the democratic party at the time and had a huge impact on the political landscape. "According to Lawrence Goodwyn, if the labor movement had been able to do in the cities what the Populists did in the rural areas, "to create among urban workers a culture of cooperation, self-respect, and economic analysis," there might have been a great movement for change in the United States." (271) This anti elitist movement sided with labor unions to attack banks, railroads and unfair working environments. Zinn quotes Normal Pollak who says "Populism regarded itself as a class movement, reasoning that farmers and workers were assuming the same material position in society." (272) The movement united poor white people and black people to fight for industrial freedom. Zinn says that they were not above racist thinking but still strived for the "emancipation of all men" (273) Zinn mentions the populist party because they have a huge impact on the labor unions, the democratic party, and arguably helped create the progressive movement.
Magnates Combine to Create Unstoppable Force of Corruption
October 21, 2013 by ri153839
"… a circular marked "Private and Confidential" was issued by the three banking houses of Drexel, Morgan & Company, Brown Brothers & Company, and Kidder, Peabody & Company. The most painstaking care was exercised that this document should not find its way into the press or otherwise become public…. Why this fear? Because the circular was an invitation … to the great railroad magnates to assemble at Morgan's house, No. 219 Madison Avenue, there to form, in the phrase of the day, an iron-clad combination. … a compact which would efface competition among certain railroads, and unite those interests in an agreement by which the people of the United States would be bled even more effectively than before." (Zinn,256)
At this time, the emergence of oligopolies was considered a feat of financial ingenuity, as well as the bane of consumers and workers. For so long companies had been competing to get the most customers and to reap the highest profits. Eventually, they discovered the path to success, while counterintuitive, was to collude so they could focus on manipulating their consumers and workers for higher profits. Zinn believed that the railroad magnates coming together sealed the fate of Americans: the tycoons and their corporations would go uncontested while the working class would inevitably suffer through cruel conditions. The title of the era as "The Gilded Age" is fitting as a select few reached unparalleled heights of success while underneath, most Americans lived through the harshest conditions. Saying the working class "would be bled even more effectively than before" was not just a metaphor. In 1889 alone, over 22,000 railroad workers were killed or injured. Because the companies were working together, workers could not seek better wages or working conditions at a different company. Such became the case with most labor jobs. On top of paying meager wages, these companies would charge exorbitant prices thereby effectively putting these wages back in their own bank accounts. As a result, these companies owned and controlled Americans.
Soon companies gained control of Americans not just on an individual level but on a federal level. The United States government stood by and allowed the greedy corporations to operate while infringing upon the rights and well-being of Americans. Zinn compares the government at this time to a Marxist definition of a capitalist state, "pretending neutrality to maintain order but serving the interests of the rich." (Zinn,258) Under Grover Clevelend, the Federal bank had ran out of gold reserves. The large private banks working together saw this economic vulnerability as an opportunity for growth and took control over millions in government bonds. The government's dependence on big banks became clear as it served to protect the interest of these banks as opposed to its constituents. Thus these industries were able to operate with little to no accountability and regulations. By working together, the heads of the banking, oil, steel and railroad industries earned a lasting influence on America.
the cruel truth of society
October 21, 2013 October 21, 2013 by juntao.jiang
"Meanwhile, the government of the United States was behaving almost exactly as Karl Marx described a capitalist state: pretending neutrality to maintain order, but serving the interests of the rich. Not that the rich agreed among themselves; they had disputes over policies. But the purpose of the state was to settle upper-class disputes peacefully, control lower-class
rebellion, and adopt policies that would further the long-range stability of the system."(Zinn 258).this quote describes that the U.S.A. tried to follow themselves to Marxist ideas, in reality, they fell into the mould of Marxist capitalism. the ways government treated to upper-classes and lower-classes are totally different because government needs to contrapose different tagets with different effective ways. a integrated and well-organized policy will promote the development of the society.
"The development of a factory-like system in the nineteenth-century schoolroom was not accidental (Zinn 263)."by Joel Spring. this quotes descirbes that the importance of the Industrial Revolution on society during this time. development of a factory is just like education in nineteenth century, it is indispensable, accelerate the development of industrials can effecially improve the ecnomy of whole society. at that time, more and more inventions came out, industrals played a more important role in the society. however, as the new inventions coming out, farmers could not monopolize their product, it also brings a little loss to them. and governement didnt treat those farmers fairly and completely.
i think that Zinn was trying to say that there were always something new and good products coming to the society, they must be benefits to people. however, government couldnt ignore the people who were affected negatively. some kind of inventions replaced people' jobs. Zinn wanted government to treat all workers equally and fairly.
Government Inc.
October 20, 2013 October 24, 2013 by kj159027
"Meanwhile, the Supreme Court, despite its look of somber, black-robed fairness, was doing its bit for the ruling elite" (260)
The saying "power corrupts all, and corrupts absolutely" rings truest in the liberty bells of America. The ultimate authority of the American judicial system was founded with the ambitious intent of being above corruption. Sanctified by the lack of term limits and the illegality of accepting bribes. However, how can we suppose any thing to be perfect while it is composed of naturally imperfect men? "How could it be nuetral between rich and poor when its members were often former wealty lawyers, and almost always came from the upper class?"(260) The panel of judicial princes promptly nullified the Sherman Act focusing on language such as "commerce" and "unreasonable," (260) to orchestrate the circumvention of the people's valiant acts of self-advocation. Monopolies were suddenly cartels in every possible category omitting of course "commerce." The notion of "unreasonable" abruptly spoke only from the perspective of those within reasonable means. Meaning, a rich man's government, runs on a rich man's judgement.
Surprisingly, not only did the Supreme Court defend the rights of the people, "By this time the Supreme Court had accepted the the argument that corporations were 'persons'-," (261) but it also advocated for its tax payers. The laws labored into legitimate legislature by the layman were to be consumed and construed against said population. The Sherman Act now acted against dissenters along trade routes because this was obviously not an oppostition to power but "commerce". " Supposedly, the Amendment had been passed to protect Negro rights, but of the Fourteenth Amendment cases brought before the Supreme Court between 1890 and 1910, nineteen dealt with the Negro, 288 dealt with corporations." (261) The extengencies for the direction of action were depenedend soley on the monatary motives of the emerging financial monarchies. The likes of Rockefeller donated to Tuskegee Institute and Hampton Institute yet, America's presentation of fairness had only an eye for the fairest cases.
Posted in: A People's History, Chapter 11, Course Information	|
From Deceit to Riches
October 20, 2013 October 20, 2013 by fj157843
"Thomas Edison promised New Jersey politicians $1,000 each in return for favorable legislation". (248). In this era, fraud and deceit was the only way to have skyrocketing income. Robber Barons such as John D. Rockefeller made millions, all fueled by the poor people's pockets. The working class remained with its low wages working 12 hour shifts. "Shred efficient businessman building empires, chocking out competition, maintaining high prices, keeping wages low, using government subsidies". (251).
Then there were the lawyers, technicians, and engineerings, paid slightly more, but these were the ones keeping the scheme running in this perfectly devised system designed by the Robber Barons themselves. Ruthless tactics such as price fixing and sabotage were the norm. These banditos attained government subsidies and used it to their advantage to fund their enterprises; meanwhile the working class people could not obtain a simple housing subsidy.
Robber Barons alike to Rockefeller concentrated industry onto a saturated monopoly that controlled a great deal of markets. Many different industries depended on one another for survival, but the common denominator was, most of them needed the steel industry for survival, to supply machinery, railroad tracks, and raw material for building blocks. Although there was much carelessness during industrialization, many good things came out from industrialization. Howard Zinn relates the good things to the transcontinental railroad which connected hubs and cities to many different destinations. Steel in itself increased productivity and made possible many commercial ventures. However, too much fast progress in society is usually accompanied by cutting corners and legalized organized crime as to the point where the middle-class is almost nonexistant.


text:
Damaris Disner, creator from Chiapas
«Damaris Disner» (Tonalá, Chiapas, Mexico, October 3, 1975), playwright, cultural manager, teacher.
Imagen de Damaris Disner en la Galería Rodolfo Disner, 2021, realizada por Salvador Vázquez
Damaris is the youngest daughter of the plastic artist and ceramic muralist Rodolfo Disner Clavería. Damaris was born in Mexico City in 1975. She started writing around the age of 14. She is originally from Tonalá, Chiapas, a coastal place where she studied primary and secondary school at the "La Rosa" religious school, and high school at the Tonalá High School. She currently lives and works in the capital of Chiapas: Tuxtla Gutiérrez[1]
Damaris Disner has an infectious smile, a creative mind, and an enthusiastic and dynamic spirit. She assumes herself as curious by vocation and is also a lover of the feline spirit. She works with children's literature, theatre, mini fictions, cultural press, and seeks to break through monotony and disenchantment with her words. She affirms that in the works for children, she seeks to unravel the fears of childhood, to confront them from the perspective of the adult she learns to be. [2]
She has a degree in Communication Sciences from the Autonomous University of Chiapas, UNACH. She was a member of the literary creation workshop of the Yolanda Gómez Fuentes Children's Coexistence and Family Recreation Center and the Poetics and Narrative Seminar of the General Society of Writers of Mexico, SOGEM, in 2004 she studied dramaturgy with Enrique Polo Keratry.[3]
Since March 2, 2013, she created and has directed the Rodolfo Disner Gallery, whose name is in honor of her father, a renowned artist from Chiapas. This gallery is currently celebrating nine years of activity (2013-2022). It is located in the city of Tuxtla Gutiérrez, the capital of Chiapas. In this space, they establish a link between local children and the world of creation, with activities related to culture, art, literature, music, dance, and theater.[4]
Her literary work includes cultural articles in newspapers, state and national magazines. She has also participated in six anthologies. Her first playwriting book is entitled «La noche que habitamos» (The night we inhabit). Another of his works is «La Siguiente Esquina» (The next corner). Among the plays of his authorship are «Telemilio», and «Pitukali» [5]
She received a scholarship from the State Fund for Culture and the Arts, FECA, in 2005 and from the Program to Encourage Creation and Artistic Development, PECDA in dramaturgy, in 2006.
Mireles Gavito, Sofía. «DAMARIS DISNER LARA, DRAMATURGA INFANTIL CHIAPANECA». Revista Endehuanna.
2. López Suárez, María Gabriela (25 de mayo de 2020). «Entonces, escribo: video columna de Damaris Disner». Chiapas Paralelo (Noticias).
3. «Damaris Disner». elem.mx. Enciclopedia de la Literatura en México.
4. Ballinas, Miguel (2019). «La cultura hace mejor a una sociedad: Damaris Disner». Dia Uno Noticias (Cultura).
5. Quiroz Ceballos, Manuel Alejandro. «Dramaturgia latinoamericana: Damaris Disner (México)». Galerías del Alma. Galerías del Alma.
Ra'al Ki Victorieux marzo 5, 2022 marzo 5, 2022 Atma Unum, Chiapas, Damaris Disner, escritores, Galery, Iris Aggeler, Iris Atma, Iris México, LATAM, Mexico, mujer escritora, Ra'al Ki Victorieux, Raal Ki Victorieux, Rodolfo Disner, Salvador Vázquez, teacher, Tonalá, woman writer
Anterior Entrada anterior: UNUM ATMA: revista sobre arte, activismo y contemporaneidad
Siguiente Entrada siguiente: Damaris Disner, escritora chiapaneca


Soul Seeker is a 3D isometric ARPG where players clear room after room of enemies before taking on the boss at the end of the stage. Players can unlock hundreds of heroes that they can recruit into their party.
Pros: +Simple, easy to learn to gameplay. +Colorful and flashy visuals. +Great character artwork and graphics.
Cons: -Repetitive gameplay. -Pay to win. -Features are locked behind account-level barrier. -Play-time limited by energy system.
Take on monsters, demons, and furry little animals to save the god Hermes in Soul Seeker. Choose your hero and recruit a party of support characters to take on the forces of darkness in the service of the goddess herself. Explore different areas ranging from dark caves and lava-filled caverns to green meadows and gleaming mountain ruins. Use your skills and your party's skills to help you clear room after room of enemies and take out the boss guarding the end of every stage in true Action RPG style. Customize your party and make it stronger with hundreds of unique and powerful heroes that you can unlock as you progress further into your quest. Collect materials and use them to craft weapons and gear the you can equip on each member of your party to help them keep up with the ever-increasing power of the enemy's minions. Test your skills in automated and real-time PvP battles, tournaments, and full-scale guild sieges. Take on the Challenge Towers and clear its floors to earn rewards that will go a long way in helping you save the troubled world of Soul Seeker.
Non-Stop Action – prepare your thumbs for a workout as you slash your way through room after room of mobs culminating with massive boss fight at the end of every stage.
Recruit Heroes – unlock a large variety of heroes each with their own unique skills and stats and recruit them into your party. You can then summon them on the battlefield to fight for a short period of time.
Craft Weapons and Gear – craft powerful weapons and gear that you can equip on your chosen hero and the rest of your party to make them stronger.
Challenge Towers – eliminate wave after wave of mobs found on each floor of the Challenge Towers. Clear each floor to earn progressively better rewards.
PvP Arena – test out your party build against other players in tournaments, 5vs5, 10vs10, and Guild Siege battles.
Operating System: Androud 4.1 and up, iOS 7.0 or later.
Soul Seeker is a 3D fantasy-themed isometric ARPG developed and published by South Korean mobile and online games developer Com2uS. The game was initially scheduled to launch globally on January 29, 2015 but was pushed back to February 5, 2015 for unknown reasons. The game has been updated regularly since its launch with the last major game update rolling out in August last year which added new PvP modes and the Guild Siege feature.


text:
Q: Next.js return the 404 error page in getInitialProps Currently I am following this example on how to redirect users in getInitialProps
https://github.com/zeit/next.js/wiki/Redirecting-in-%60getInitialProps%60
The problem is, if I want to return 404 like this, it will return a blank page instead of the usual Next.js 404 error page.
context.res.writeHead(404)
context.res.end();

Please note I know using ExpressJs and using statuscode 404 works, however, for this project I am not allowed to use ExpressJs so I need to use typical nodejs writeHead to do it.

A: Implement your getInitialProps along the lines of:
    static async getInitialProps(context) {
        const {res} = context;

        ...

        if ([something went wrong]) {
            if (res) {
                res.statusCode = 404;
            }

            return {
                err: {
                    statusCode: 404
                },
            };
        }
        ...

Then in render() check if err is defined in state, in which case return the ErrorPage (default or custom one, depending on your implementation) and that's it! The statusCode inside err is just for more granular message on the ErrorPage so it needs to be passed for it as props.

A: Next v10 allows to return 404 page (not with props, but just plain as it is below)
  if (!checkItem) {
    return {
      notFound: true
    }
  }

Full code that works for me: ✅✅✅
export const getServerSideProps = wrapper.getServerSideProps(async ({ req, res, locale, query, store }) => {
  const { productId, categoryId } = query

  const checkItem = await getProductBySlugSSR(productId, categoryId, store)

  if (!checkItem) {
    return { // <-----------------does the trick here!!
      notFound: true
    }
  }

  return {
    props: {
      ...await serverSideTranslations(locale, ['common']),
    }
  }
})

Documentation: https://nextjs.org/blog/next-10#notfound-support

A: In order to do that, you'll have to render the Error page in your page.
You can do something like this:
import React from 'react'
import ErrorPage from 'next/error'

class HomePage extends React.Component {
  static async getInitialProps(context) {
    try {
      const data = await retrieveSomeData()
      return { data }
    } catch (err) {
      // Assuming that `err` has a `status` property with the HTTP status code.
      if (context.res) {
        context.res.writeHead(err.status)
      }
      return { err: { statusCode: err.status } }
    }
  }

  render() {
    const { err, data } = this.props

    if (err) {
      return <ErrorPage statusCode={err.statusCode} />
    }

    /*
     * return <Something data={data} />
     */
  }
}

If you have a custom error page, instead of importing next/error, you'll have to import your custom _error page.

A: As of NextJS 10, you can now include notFound: true in the return object of getStaticProps && getServerSideProps to redirect to the 404 page
Here are the release notes: https://nextjs.org/blog/next-10#redirect-and-notfound-support-for-getstaticprops--getserversideprops

A: import App, { Container } from 'next/app'
import React from 'react'
import Head from 'next/head'
import * as Sentry from '@sentry/node'
import Error from './_error'

require('es6-promise').polyfill()
require('isomorphic-fetch')

class MyApp extends App {
  static async getInitialProps({ Component, ctx }) {
    let pageProps = {}
    let e
    if (Component.getInitialProps) {
      try {
        pageProps = await Component.getInitialProps(ctx)
      } catch (error) {
        e = error
        Sentry.captureException(error) //report to sentry
      }
    }
    return { pageProps, e }
  }

  render() {
    const { Component, pageProps, e } = this.props
    if (e) {
      return <Error /> // customize your error page
    }
    return (
      <Container>
        <Head>
          <title> Your title</title>
        </Head>
        <Component {...pageProps} />
      </Container>
    )
  }
}

export default MyApp

This works like a charm ~
just try catch in next/app, then it works for all the pages

A: If you just have to implement the 404 PAGE like you do in cra
the code provided can be helpful:
eg.
 import AComponent from '../acomponent';
 import Error from '../error';

 const User = (data) => {

   return data.id ? <AComponent /> : <Error />
 }

 User.getInitialProps = async (ctx) => {
   const res = await fetch(...data) // list of items = []
   const data = await res.json()

   return data;
 }

A: Here's how I do it
import ErrorPage from 'next/error'

const Mycomponenet = () =>{
   if (!exists) {
        return <ErrorPage statusCode={404}/>
      }
}

A: I am using this and it works for me
res.sendStatus(404)

redpajama_set_name: RedPajamaStackExchange


George Whitfield facebook – Me!
Fiddlebox website – My duo with Helen Adam (fiddle and vocals).
Fiddlebox facebook – My duo with Helen Adam (fiddle and vocals).
Pressgang Website – Rocking folk band that I have played with since the late 80's!
Voxpop Records / Damian Clarke Website – Damian of Pressgang's solo website.
The Outcast Band Website – Folk rock band that I have done various work for over the years.
Roy Bailey Website – Folk singer Roy Bailey has a great website here.
Software Alliance Wales – Without whom I would not have been able to build this website! – they run lots of (free) courses.
Beltrami Accordions – the website for Claudio Beltrami's excellent accordions 2 of which I own!
MusicTech – The company that supplies King Major accordion MIDI systems and Sennheiser accordion microphone systems.
Alex Cooke – Took some great photos of Pressgang in the 90's – still takes great photos!
The Accordion Shop – With branches in Sunningdale and Rochdale – always a good selection of new and second hand instruments on the website.
Accordion Uprising – Great accordion interest site run by Bruce Triggs – also links to accordion noir radio which he hosts.
Accordion Revival – Website includes an in-depth look at repair methods.
Cathie Travers – Great demo of left hand and arm positions. Check out her other brilliant playing videos too!


text:
Stripping in Front of a Crowd
The dare: Baring your bare body confidence as a burlesque dancer
By Meg Ryan
Dan Winters
I've never been into playing dress-up. I've certainly never wanted to play dress-up and then take it all off until I'm bare naked. In front of an audience. I already feel sexy--I don't need a roomful of strangers to tell me I am. Then one night I found myself at a burlesque show.
The performance I saw didn't feature lap dances and poles. This was Vaudeville Nouveau, a modern take on the classic variety shows of the '20s and '30s. The burly-girls this night, Rubie Fizz and Legs Malone, were not titillators out for attention or dollar bills. They looked like regular women--beautiful and slim, to be sure, but no more or less so than you or me. And judging by their acts, smart, too. And funny. With boatloads of moxie. And the audience, men and women alike, cheered them on. I was hooked and determined to find out the difference between enjoying my 32As in the privacy of my own blouse and baring them to the world.
I headed to the New York School of Burlesque to learn the basics: shimmy, bump 'n' grind, and a simple chair dance. Headmistress Jo "Boobs" Weldon starts every class with the same directive: "Claim your space." What she actually means is "Spread out so you don't swat each other with boas," but it's also a reminder to plant your flag in the sand, in and out of class. "It's not about the strip--it's about the tease," says Rubie Fizz, my next stop on the road to my burly-q debut. The boob reveal is just the punch line. "You can do a successful striptease with just a glove peel. The key to a successful act," she says, "is to own up to who you are. That's sexy."
But this is a burlesque show we're talking about, and sexy also means stage makeup, costumes, and choreography. Rubie makes sure I get the glammy details right. This includes making me pasties from pink Swarovski crystals. To hold them in place, she recommends carpet tape (the double-sided stuff you get at hardware stores). Eyelashes? They must be worn and trimmed to follow the shape of your eye. Skin? Use Sally Hansen Airbrush Legs makeup to even out your skin tone. And, of course, glitter. I spend the next six weeks rehearsing and getting used to the feeling that moths are stuck to my eyelids. And even as I perfect my stocking peels, my evil inner voice, the one that hisses, "Who do you think you are?" keeps poking holes in my act--and my confidence: Maybe I should do extra Pilates… Maybe I oughta lay off the bagels… But the louder the voice, the more I fight. I stop working out, except for rehearsals. I increase my bagel intake.
Showtime: My makeup is glittery, my hair blown out and tied in a discreet bow, my pasties firmly in place. Host Nelson Lugo introduces me by my pseudonym (on loan from a local performer): "Miss Minerva Steel!" French cabaret music fills the hall and I take the stage with a sultry strut. (Woo-hoo!) I flirt (with "a knowing coquettishness," one observer remarked later) with a guy in the audience, poised as I slide a gorgeous foot in a '40s-style stiletto up my silk-stockinged calf, then pull a satin scarf off my neck and let it float to the floor. (More cheers!!) I peel off one stocking, then--surprise!--unleash my wavy raven locks. (Huge cheers!) I hold a long, leggy pose and slooowly remove the other stocking. Now I start undoing my shirtdress buttons (snaps, actually: I had them converted in case my nerves made me shaky), tearing it open--just as I turn my back to the audience. I bare one shoulder, then the other, then shimmy off the frock, revealing frilly lingerie. (Yeah!!) I crescendo to the Big Finish, removing one bra strap at a time as I shake my booty. One final pose and, with the flick of a wrist, off flies the bra. I grant one quick flash, turn, and sashay toward the exit. (MI-NER-VA!!!) I oblige them with one last look and disappear. (Whistles! Encore!!) Guess that "show your strengths" thing really works.
Turns out the difference between private enjoyment and public display has a lot to do with being comfortable in my body and not worrying about what others think. And it was true that I could have done it without showing boobs: To the crowd (OK, the friends I planted out there), the sexiest part was the way I took off my scarf. I'll still probably never be into playing dress-up, but I'll definitely remember how smokin' I felt batting those eyelashes.
How to do it yourself
So maybe you're not going to prance around onstage in your skivvies. (A lot of nights it would take the jaws of life just to get out of your sweats.) But you can amp up your sex appeal. Robin Antin, creator of the Pussycat Dolls pop ensemble and Vegas stage show, tells how to loosen up your buttons a bit. --Sarah Stebbins
Take dance classes Hip-hop, jazz, ballet, belly dancing--they all provide a great workout and make you feel sexy. That attitude "gets in your head," says Antin, and can change the way you carry yourself.
Break out the racy lingerie, just because. Having "a little secret can make you feel sexy and confident," says Antin, who likes a simple tank and booty-hugging jeans over her frilly things. But not too low with the jeans, she warns: "Showing your crack is never sexy."
Play peekaboo "Bangs shape your face and give you a style," she says. "It's the cutest look, which is why a lot of the Pussycat Dolls in Vegas have them." But you can't pussyfoot: Bangs have got to be long and thick--past your eyebrows, but not in your eyes.
More WH dares
Bare Body Confidence
Would You Wear the Same Dress for 2 Weeks?
Plank with Front Raise
Front-Loaded Split Squat
Why Looks Matter