# Polar Codes for Channels with
Insertions, Deletions, and Substitutions

Henry D. Pfister  Duke University  Ido Tal  Technion

###### Abstract

This paper presents a coding scheme for an insertion deletion substitution
channel. We extend a previous scheme for the deletion channel where polar
codes are modified by adding “guard bands” between segments. In the new
scheme, each guard band is comprised of a middle segment of ‘1’ symbols, and
left and right segments of ‘0’ symbols. Our coding scheme allows for a regular
hidden-Markov input distribution, and achieves the information rate between
the input and corresponding output of such a distribution. Thus, we prove that
our scheme can be used to efficiently achieve the capacity of the channel. The
probability of error of our scheme decays exponentially in the cube-root of
the block length.

##  I Introduction

In many communications systems, symbol-timing errors can result in insertion
and deletion errors. For example, the insertion deletion substitution (IDS)
channel maps a length-$N$ input string to a finite output string by sampling
an i.i.d. output process for each input that selects between insertion,
deletion, and substitution. These types of channels were first studied in the
1960s [1, 2] and modern coding techniques were first applied to them in [3].
Over the past 15 years, bounds on the capacity of synchronization error
channels have been significantly improved [4, 5, 6, 7, 8].

In [9, 10], a capacity-achieving coding scheme is introduced for the deletion
channel based on polar codes. The construction and proof builds upon many
earlier results (e.g., [11, 12, 13, 14, 15, 16, 17, 18, 19]); see [10] for a
detailed description of these connections.

The construction in [9, 10] is based on generating codewords consisting of
smaller blocks separated by guard bands. After reception, the overall output
sequence is separated into blocks associated with the smaller input blocks.
However, the separation process changes the effective channel experienced by
the small blocks. In particular, the guard bands are long blocks of zeros and
the separation process removes all zeros on either side of the small block.
The analysis in [9, 10] shows that the resulting channel, dubbed the trimmed
deletion channel (TDC), polarizes weakly and has the same mutual information
rate as the original deletion channel. Due to the possibly unbounded memory in
the deletion channel, the standard extension [20] to strong polarization does
not work. Instead, strong polarization can be shown for the polar combining of
these small blocks due to the independence provided by the guard bands. These
elements complete the achievability proof for the deletion channel.

In this paper, we apply roughly the same coding scheme to the IDS channel. The
main difference is that separating the overall output sequence into smaller
blocks is more challenging. For the deletion channel, an input that only
contains zeros always gives an output that only contains zeros. Thus, the
separation process consists of parsing into small blocks and removing zeros
from the edges. For the IDS channel, an input only containing zeros typically
gives an output containing both zeros and ones. Fortunately, the expected
fraction of zeros will be noticeably larger than the fraction of ones. This
observation along with a more complicated parsing process can be used to
separate the overall output sequence into blocks associated with the smaller
input blocks.

The key challenge is designing the parsing process so that the effective
channel experienced by the small block can be analyzed. In particular, our
parsing process produces segments that can be seen roughly as the IDS output
of an input consisting of a prefix of zeros, the original input data, and a
suffix of zeros. For all the small output blocks, the prefix and suffix
lengths are i.i.d. random variables with a known distribution. We refer to the
resulting channel as the dirty zero-padded (DZP) IDS channel. To establish the
coding theorem for the IDS channel, we must show three things. First, that our
parsing of the IDS channel output gives small blocks whose joint input-output
distribution matches that of the DZP channel. Second, that the DZP channel
polarizes weakly and has the same mutual information rate as the original IDS
channel. Third, that the trellis representation of the joint input-output
distribution of the IDS channel [3] can be modified to give the joint input-
output distribution of the DZP channel. In this work, we establish these three
elements and describe the first two elements herein.

By combining the parsing process described in this paper with the results of
[9, 10], one gets the following theorem. Due to space limitations, many
details are deferred to the extended version of this paper.

######  Theorem 1.

Fix a regular hidden-Markov input process and a parameter $\nu\in(0,1/3]$. The
rate of our coding scheme approaches the mutual information rate between the
input process and the binary IDS channel output. The encoding and decoding
complexities are $O(\Lambda\log\Lambda)$ and $O(\Lambda^{1+3\nu})$,
respectively, where $\Lambda$ is the blocklength. For any $0<\nu^{\prime}<\nu$
and sufficiently large blocklength $\Lambda$, the probability of decoding
error is at most $2^{-\Lambda^{\nu^{\prime}}}$.

The structure of this paper is as follows. In Section II we define the IDS
channel, and also a close variant which we term the “dirty zero padding IDS
channel” (DZP). Section III details how encoding is done. In Section IV, we
define two decoding methods. Namely, we first define a decoding method
executed by a genie, which is in possession of some extra information (it
knows where the “commas” which separate the outputs corresponding to certain
input blocks are). The utility of the genie’s decoding method is that it is
easy to analyze (the DZP channel is used in the analysis). We then a define
second decoding method: Aladdin’s decoding method. Since Aladdin is a mere
mortal, he does not have knowledge of where the above commas lie. That is,
Aladdin’s method is the one we can actually implement. The main trick is to
show that with very high probability, the genie’s decoder and Aladdin’s
decoder produce the exact same result.

##  II Channel models

In this section, we define the IDS and DZP channels.

###  II-A Dobrushin’s Channel and the IDS Channel

In 1967, Dobrushin introduced a general class of channels with synchronization
errors and proved a random coding theorem for that class [2]. The model
consists of a finite input alphabet $\mathcal{X}$ and a conditional
distribution $p_{Y|X}(\cdot|x)$ over finite output strings
$\mathcal{Y}\subseteq\mathcal{X}^{*}=\cup_{n=0}^{\infty}\mathcal{X}^{n}$ given
$x\in\mathcal{X}$, where $\epsilon$ denotes the empty string of length $0$.
For the input $\mathbf{x}=(x_{1},x_{2},\ldots,x_{N})\in\mathcal{X}^{N}$, the
channel output is generated by drawing $Y_{n}\sim p_{Y|X}(\cdot|x_{n})$ i.i.d.
and concatenating to get

$\mathbf{Y}=Y_{1}\odot Y_{2}\odot\cdots\odot Y_{N}.$

For example, the binary deletion channel with deletion probability
${p_{\text{d}}}$ has $\mathcal{X}=\\{0,1\\}$ and
$\mathcal{Y}=\\{\epsilon,0,1\\}$ with non-zero probabilities
$P_{Y|X}(\epsilon|x)={p_{\text{d}}}$ and $P_{Y|X}(x|x)=1-{p_{\text{d}}}$ for
all $x\in\mathcal{X}$. Similarly, the binary IDS channel we consider has IDS
probabilities $({p_{\text{i}}},{p_{\text{d}}},{p_{\text{s}}})$,
$\mathcal{X}=\\{0,1\\}$, and
$\mathcal{Y}=\left\\{\epsilon,0,1,00,01,10,11\right\\}$ with non-zero
probabilities $P_{Y|X}(\epsilon|x)={p_{\text{d}}}$,
$P_{Y|X}(x|x)=1-{p_{\text{i}}}-{p_{\text{d}}}-{p_{\text{s}}}$,
$P_{Y|X}(\overline{x}|x)={p_{\text{s}}}$,
$P_{Y|X}(0x|x)=P_{Y|X}(1x|x)={p_{\text{i}}}/2$ for all $x\in\mathcal{X}$.

While we focus on this binary IDS channel for concreteness, the approach
described here should generalize to any well-behaved binary-input Dobrushin
channel for which the output distribution associated with the all-zero input
is distinguishable from finite shifts of the output distribution associated
with the all-one input. For simplicity, we focus on the case where they are
distinguishable simply by counting ones and zeros.

Define $\alpha_{0|x}$ ($\alpha_{1|x}$) as the expected number of $0$ ($1$)
symbols at the output of the channel, given that the input was
$x\in\mathcal{X}$. Note that the expected length of an output, given that the
input was $x\in\mathcal{X}$ is $\alpha_{0|x}+\alpha_{1|x}$. We require that
this sum is independent of $x$, and denote it as

$\beta=\alpha_{0|0}+\alpha_{1|0}=\alpha_{0|1}+\alpha_{1|1}\;.$ (1)

We also require an “advantage” to $x$ at the output, if the input was $x$.
That is, we require that

$\alpha_{0|0}>\alpha_{1|0}\qquad\mbox{and}\qquad\alpha_{1|1}>\alpha_{0|1}\;,$
(2)

and denote

$\gamma\triangleq\frac{\min\\{\alpha_{0|0}-\alpha_{1|0},\alpha_{1|1}-\alpha_{0|1}\\}}{2}>0\;,$
(3)

where the inequality follows by (2).

Informally, the above “advantage to the input at the output” will allow us to
differentiate between a long input of $0$ symbols and a long input of $1$
symbols. Specifically, fix a window length $h>0$ and an $x\in\mathcal{X}$.
Then, generate an output sequence of length at least $h+1$ and optionally
remove the first output bit. Then, we count the number of $0$ symbols
contained in the first $h$ positions of the string. If it is at least $h/2$,
then we declare that $x=0$; otherwise, we declare that $x=1$. The following
lemma states that we have a very high chance of guessing correctly, for large
enough window length $h$.

######  Lemma 2.

Let $x\in\mathcal{X}$ be fixed, and let a window length $h\geq h_{0}$ be
given, where $h_{0}$ is a constant dependent on the channel. Let $\mathbf{Y}$
be a string of length $h$ generated by truncating the output associated with
the all-$x$ input where the first output bit is optionally removed. Then, the
probability that $\mathbf{Y}$ contains fewer than $h/2$ bits equal to $x$ is
less than

$\mathrm{err}_{h}\triangleq e^{-h\cdot c_{0}}\;,$

where $c_{0}$ is a positive constant dependent on the channel.

###### Proof:

See Appendix. ∎

###  II-B Dirty-Zero-Padding IDS channel

The DZP channel $W^{\star}$ is defined by the IDS channel $W$, the input
blocklength $N_{0}$, and two probability distributions over $\mathcal{X}^{*}$,
$P_{\mathrm{padLeft}}$ and $P_{\mathrm{padRight}}$. Given the length-$N_{0}$
input string $\mathbf{x}$, we first pass $\mathbf{x}$ through the IDS channel
$W$ and let $\mathbf{y}_{\mathrm{middle}}$ denote the output. Next, we draw
two independent vectors $\mathbf{y}_{\mathrm{left}}$ and
$\mathbf{y}_{\mathrm{right}}$ according to the probability distributions
$P_{\mathrm{padLeft}}$ and $P_{\mathrm{padRight}}$, respectively. The output
of the DZP channel is then given by

$\mathbf{y}^{\star}=\mathbf{y}_{\mathrm{left}}\odot\mathbf{y}_{\mathrm{middle}}\odot\mathbf{y}_{\mathrm{right}}\;.$
(4)

We will specify $P_{\mathrm{padLeft}}$ and $P_{\mathrm{padRight}}$ later. For
now, let us say informally that $\mathbf{y}_{\mathrm{left}}$ and
$\mathbf{y}_{\mathrm{right}}$ are the result of passing strings of ‘0’ symbols
through the channel $W$. Hence the name: we pad $\mathbf{y}$ from the left and
right by vectors corresponding to zeros “dirtied” by passing through the
channel $W$.

Informally, the following lemma states that, in the limit as $N_{0}\to\infty$,
the mutual information rates of $W$ and $W^{\star}$ are equal. As will become
apparent later, the maximum possible length of $\mathbf{y}_{\mathrm{left}}$
and the maximum possible length of $\mathbf{y}_{\mathrm{right}}$ both grow
sub-linearly in $N_{0}$. Hence, the condition of the lemma is not vacant.

######  Lemma 3.

Let $\mathbf{X}\in\mathcal{X}^{N_{0}}$ be a random vector of length $N_{0}$.
Let $\mathbf{Y}$ and $\mathbf{Y}^{\star}$ be the outputs gotten when
$\mathbf{X}$ is input to the IDS channel $W$ and the DZP channel $W^{\star}$,
respectively. Let $N_{0}$ be large enough so that the maximum length that
$\mathbf{y}_{\mathrm{left}}$ can take and the maximum length that
$\mathbf{y}_{\mathrm{right}}$ can take are both at most $N_{0}-1$. Then,

$\frac{I(\mathbf{X};\mathbf{Y})-2\log_{2}N_{0}}{N_{0}}\leq\frac{I(\mathbf{X};\mathbf{Y}^{\star})}{N_{0}}\leq\frac{I(\mathbf{X};\mathbf{Y})}{N_{0}}\;.$

###### Proof.

It suffices to prove the inequalities for the numerators since the
denominators all equal $N_{0}$. The inequality
$I(\mathbf{X};\mathbf{Y}^{\star})\leq I(\mathbf{X};\mathbf{Y})$ follows by the
data-processing inequality, since $\mathbf{X}$, $\mathbf{Y}$, and
$\mathbf{Y}^{\star}$ form a Markov chain, in that order. We will show that

$I(\mathbf{X};\mathbf{Y})-2\log_{2}N_{0}\leq
I(\mathbf{X};\mathbf{Y}^{\star})\;.$ (5)

Let us first denote
$\mathbf{Y}^{\star}=\mathbf{Y}_{\mathrm{left}}\odot\mathbf{Y}_{\mathrm{middle}}\odot\mathbf{Y}_{\mathrm{right}}$,
as described above. Next, note that we can assume w.l.o.g. that
$\mathbf{Y}=\mathbf{Y}_{\mathrm{middle}}$. Finally, note that $\mathbf{X}$,
$(\mathbf{Y}^{\star},|\mathbf{Y}_{\mathrm{left}}|,|\mathbf{Y}_{\mathrm{right}}|)$,
and $\mathbf{Y}$ form a Markov chain, in the order, where $|\cdot|$ denotes
the length of a string. Thus,

$\displaystyle I(\mathbf{X};\mathbf{Y})$ $\displaystyle\leq$ $\displaystyle
I(\mathbf{X};\mathbf{Y}^{\star},|\mathbf{Y}_{\mathrm{left}}|,|\mathbf{Y}_{\mathrm{right}}|)$
$\displaystyle\leq$ $\displaystyle
I(\mathbf{X};\mathbf{Y}^{\star})+H(|\mathbf{Y}_{\mathrm{left}}|)+H(|\mathbf{Y}_{\mathrm{right}}|)$
$\displaystyle\leq$ $\displaystyle
I(\mathbf{X};\mathbf{Y}^{\star})+2\log_{2}(N_{0})\;,$

because both $|\mathbf{Y}_{\mathrm{left}}|$ and
$|\mathbf{Y}_{\mathrm{right}}|$ can take at most $N_{0}$ different values.
Thus, (5) holds and the proof is complete. ∎

##  III Encoding

Suppose for a moment that we were coding not for the IDS channel $W$, but for
the DZP channel $W^{\star}$. First of all, recall that the channel $W^{\star}$
accepts a block of length $N_{0}$ bits. We choose a typically “large” $N_{0}$.
However, instead of only sending a single block of length $N_{0}$, we send
$\Phi$ such blocks, denoted
$\mathbf{x}(1),\mathbf{x}(2),\ldots,\mathbf{x}(\Phi)$. The important point to
note is the output: denote the output of $W^{\star}$ corresponding to
$\mathbf{x}(i)$ as $\mathbf{y}^{\star}(i)$. We assume that the output
corresponding to the above input is
$(\mathbf{y}^{\star}(1),\mathbf{y}^{\star}(2),\ldots,\mathbf{y}^{\star}(\Phi))$,
as opposed to
$\mathbf{y}^{\star}(1)\odot\mathbf{y}^{\star}(2)\odot\cdots\odot\mathbf{y}^{\star}(\Phi)$.
That is, we assume that the output blocks corresponding to the input blocks
are _punctuated_. Namely, given the output corresponding to $\Phi$ blocks, we
can distinguish the output corresponding to input block $\mathbf{x}(i)$. This
is in stark contrast to $W$, in which no such punctuation is given.

For this setting, one can both encode and decode using polar codes; this is
very similar to what was done in [10] with the DZP channel playing the role of
the block-TDC channel. Given the information symbols and frozen indices, the
information symbols are mapped to a polar codeword of length $\Phi N_{0}$
using polar encoding. Also, extending the ideas in [3, 10], we can build a
trellis for calculating the joint probability of $\mathbf{x}$ being the input
to $W^{\star}$ and $\mathbf{y}^{\star}$ being the output (building such a
trellis involves the use of $P_{\mathrm{padLeft}}$ and
$P_{\mathrm{padRight}}$). Finally, using Lemma 3 and essentially the same
proof as [10], this coding scheme can approach the capacity of the IDS channel
$W$. Due to lack of space, we do not go into further details.

Our coding scheme for the IDS channel $W$ consists of two phases. In the first
phase, we produce the blocks
$\mathbf{x}(1),\mathbf{x}(2),\ldots,\mathbf{x}(\Phi)$ by taking the whole
polar codeword and adding commas to separate into blocks of length $N_{0}$.
Then, we imagine these blocks being transmitted over $W^{\star}$. In the
second phase, we add guard bands (defined shortly) between the above blocks.
The result is a long codeword that is transmitted over the channel $W$.
Loosely speaking, the purpose of the guard bands is to allow the decoder to
simulate the operation of $W^{\star}$ on the blocks
$\mathbf{x}(1),\mathbf{x}(2),\ldots,\mathbf{x}(\Phi)$, even though we are in
fact transmitting over the channel $W$.

Denote $N=2^{n}$, $N_{0}=2^{n_{0}}$ and $\Phi=2^{n_{1}}=2^{n-n_{0}}$, where
$n_{0}=\lceil n\nu\rceil$ and $\nu$ was fixed in Theorem 1. Let

$\mathbf{x}=\mathbf{x}(1)\odot\mathbf{x}(2)\odot\cdots\odot\mathbf{x}(\Phi)$
(6)

be a vector of length $N$, consisting of blocks $\mathbf{x}(i)$, each of
length $N_{0}$. We denote by $g(\mathbf{x})$ the result of adding guard bands
to $\mathbf{x}$. For this, let us denote
$\mathbf{x}=\mathbf{x}_{\mathrm{I}}\odot\mathbf{x}_{\mathrm{II}}$, where
$\mathbf{x}_{\mathrm{I}}$ and $\mathbf{x}_{\mathrm{II}}$ are the left and
right halves of $\mathbf{x}$, each of length $N/2$.

$\displaystyle g(\mathbf{x})$
$\displaystyle\triangleq\begin{cases}\mathbf{x}&\text{if }n\leq n_{0}\\\
g(\mathbf{x}_{\mathrm{I}})\odot\mathbf{g}_{n}\odot
g(\mathbf{x}_{\mathrm{II}})&\text{if }n>n_{0},\end{cases}$ (7)

where $\mathbf{g}_{n}$ is termed the guard band and defined as follows. Denote
by $\mathbf{0}(\ell)$ and $\mathbf{1}(\ell)$ a string of $\ell$ consecutive
‘$0$’ symbols and a string of $\ell$ consecutive ‘$1$’ symbols, respectively.
Let

$\ell_{n}\triangleq 2^{\lfloor(1-\xi)(n-1)\rfloor}\;,$

where $\xi\in(0,1/2)$ is a ‘small’ constant determined by the difference
between $\nu$ and $\nu^{\prime}$ in Theorem 1. Then,

$\mathbf{g}_{n}\triangleq\underbrace{\mathbf{0}(\ell_{n_{0}})}_{\mathbf{g}_{n}^{\mathrm{left}}}\odot\overbrace{\underbrace{\mathbf{1}(\ell_{n})}_{\mathbf{g}_{n}^{\mathrm{midleft}}}\odot\underbrace{\mathbf{1}(\ell_{n})}_{\mathbf{g}_{n}^{\mathrm{midright}}}}^{\mathbf{g}_{n}^{\mathrm{mid}}}\odot\underbrace{\mathbf{0}(\ell_{n_{0}})}_{\mathbf{g}_{n}^{\mathrm{right}}}\;.$
(8)

We note that $\mathbf{g}_{n}^{\mathrm{left}}$ and
$\mathbf{g}_{n}^{\mathrm{right}}$ are not, in fact, functions of $n$.

##  IV Decoding

We now consider two settings for decoding. In both settings, a vector
$g(\mathbf{x})$ is transmitted over the IDS channel $W$, and the corresponding
output is $\mathbf{y}$. Both settings differ only in their preliminary step,
which parses the received vector $\mathbf{y}$ into $\Phi$ sub-vectors. In the
first setting, which we call “genie parsing”, an all-knowing genie receives
the output $\mathbf{y}$ and adds commas in certain appropriate places. Recall
from (6) that $\mathbf{x}$ is comprised of $\Phi$ blocks. After adding commas
to the output, the genie produces for each block $\mathbf{x}(i)$ a
corresponding output $\mathbf{y}^{\star}(i)$. The result is a series of
outputs
$\mathbf{y}^{\star}=(\mathbf{y}^{\star}(1),\mathbf{y}^{\star}(2),\ldots,\mathbf{y}^{\star}(\Phi))$,
where for each $i$, the probability law of $\mathbf{y}^{\star}(i)$ given
$\mathbf{x}^{\star}(i)$ is the DZP channel
$W^{\star}(\mathbf{y}^{\star}(i)|\mathbf{x}(i))$. We then use the methods
described in [10] to decode $\mathbf{x}$ from $\mathbf{y}^{\star}$.

The second setting is called “Aladdin parsing”. As before, $g(\mathbf{x})$ is
transmitted and $\mathbf{y}$ is received. The goal of Aladdin is to produce
the same sequence $\mathbf{y}^{\star}$ as the genie. Since Aladdin is a mere
mortal, he does not have the knowledge required to guarantee that he will add
commas in the appropriate places.

This raises the question, “Why does the genie output have dirty zero-
padding?”. An all-knowing genie could produce the IDS output sequences
$\mathbf{y}(1),\ldots,\mathbf{y}(\Phi)$. But, our genie chooses a weaker
strategy (based on an i.i.d. dither sequence) so that Aladdin can hope to
match the genie’s parsing by making use of the guard bands. Thus, we will show
that Aladdin can succeed in producing $\mathbf{y}^{\star}$ with very high
probability.

###  IV-A Genie parsing

Recall from (7) that the codeword we transmit is comprised of blocks
$\mathbf{x}(i)$, $1\leq i\leq\Phi$, separated by guard bands. Let
$\mathbf{g}(i)$ denote the guard band between $\mathbf{x}(i)$ and
$\mathbf{x}(i+1)$, where $\mathbf{g}(i)$ equals $\mathbf{g}_{n^{\prime}}$ for
some $n_{0}<n^{\prime}\leq n$ which is a function of $i$. Now we recall from
(8) that each guard band $\mathbf{g}(i)$ is comprised of four blocks, which we
denote $\mathbf{g}^{\mathrm{left}}(i)$, $\mathbf{g}^{\mathrm{midleft}}(i)$,
$\mathbf{g}^{\mathrm{midright}}(i)$, and $\mathbf{g}^{\mathrm{right}}(i)$, for
$1\leq i\leq\Phi-1$. The genie receives the output $\mathbf{y}$, and adds
commas between all the blocks because the genie can distinguish which
substring of $\mathbf{y}$ equals $\mathbf{y}(i)$, the output corresponding to
$\mathbf{x}(i)$. It can also distinguish which part of $\mathbf{y}$
corresponds to $\mathbf{g}^{\square}(i)$, where
$\square\in\\{\mathrm{left},\mathrm{midleft},\mathrm{midright},\mathrm{right}\\}$.
We denote the relevant part of $\mathbf{y}$ as $\mathbf{d}^{\square}(i)$,
where “d” stands for “dirty”.

Recall from (4) that, in order to return

$\mathbf{y}^{\star}(i)=\mathbf{y}_{\mathrm{left}}(i)\odot\mathbf{y}(i)\odot\mathbf{y}_{\mathrm{right}}(i)\;,$

the DZP channel $W^{\star}$ must pad $\mathbf{y}(i)$ from the left and right.
This padding is according to the probability distributions
$P_{\mathrm{padLeft}}$ and $P_{\mathrm{padRight}}$, which have yet to be
specified. Now, we define how the genie produces
$\mathbf{y}_{\mathrm{left}}(i)$ and $\mathbf{y}_{\mathrm{right}}(i)$ from the
following punctuated segment of $\mathbf{y}^{\star}$,

$\mathbf{d}^{\mathrm{midright}}(i-1),\mathbf{d}^{\mathrm{right}}(i-1),\mathbf{y}(i),\mathbf{d}^{\mathrm{left}}(i),\mathbf{d}^{\mathrm{midleft}}(i)\;.$

In doing this, we _implicitly define_ $P_{\mathrm{padLeft}}$ and
$P_{\mathrm{padRight}}$ as the distributions of
$\mathbf{y}_{\mathrm{left}}(i)$ and $\mathbf{y}_{\mathrm{right}}(i)$. Before
we proceed, we encourage the reader to validate the following points:
$\mathbf{y}_{\mathrm{left}}(i)$ and $\mathbf{y}_{\mathrm{right}}(i)$ are
independent and their distributions

  * •

depend on the channel statistics of $W$;

  * •

are not functions of $i$;

  * •

are not functions of either $\mathbf{x}(i)$ nor $\mathbf{y}(i)$.

Consider an index $1<i<\Phi$ (not the first nor last block). We now describe
how $\mathbf{y}_{\mathrm{left}}(i)$ depends on
$\mathbf{d}^{\mathrm{midright}}(i-1)$ and $\mathbf{d}^{\mathrm{right}}(i-1)$.
The description of how $\mathbf{y}_{\mathrm{right}}(i)$ depends on
$\mathbf{d}^{\mathrm{left}}(i)$ and $\mathbf{d}^{\mathrm{midleft}}(i)$ is
given by reflection symmetry. Before diving into the details, we emphasize
that $\mathbf{y}_{\mathrm{left}}(i)$ will consist of some suffix of
$\mathbf{d}^{\mathrm{right}}(i-1)$. Since $\mathbf{d}^{\mathrm{right}}(i-1)$
is the result of sending a string of zeros,
$\mathbf{g}^{\mathrm{right}}(i-1)$, we will indeed pad $\mathbf{y}(i)$ with a
string of “dirty zeros”. Here are the details.

  1. 1.

The genie considers the length of $\mathbf{d}^{\mathrm{midright}}(i-1)$.

    1. (a)

If it is less than $h$, where

$h\triangleq\frac{\ell_{n_{0}}\cdot\beta}{4}\;,$

the genie pads $\mathbf{d}^{\mathrm{midright}}(i-1)$ from the left. This is
done by conceptually drawing a string from $p_{Y|X}(\cdot|1)$ and prepending
$\mathbf{d}^{\mathrm{midright}}(i-1)$ with the string. In practice, we use
independent random variables to simulate $p_{Y|X}$. This is repeated until the
length of $\mathbf{d}^{\mathrm{midright}}(i-1)$ is at least $h$.

  2. 2.

The genie considers the concatenated string

$\mathbf{z}=\mathbf{d}^{\mathrm{midright}}(i-1)\odot\mathbf{d}^{\mathrm{right}}(i-1)\;.$

It places a window of length $h$ at the right side of
$\mathbf{d}^{\mathrm{midright}}(i-1)$. That is, the window starts at $z_{s}$
and ends at $z_{e}$, where $e=|\mathbf{d}^{\mathrm{midright}}(i-1)|$ and
$s=e-h$.

  3. 3.

The genie draws a random integer $\rho=\rho^{\mathrm{left}}(i)$ uniformly from
$\\{1,2,\ldots,h\\}$. We think of $\rho$ as a “random dither”.

  4. 4.

The genie shifts the window by $\rho$ positions right. That is, $\rho$ is
added to both $s$ and $e$.

    1. (a)

If the window falls off $\mathbf{z}$, that is, if $e>|\mathbf{z}|$, the genie
chooses $\mathbf{y}_{\mathrm{left}}=\epsilon$, the empty string. Otherwise,
the genie continues to the next step.

  5. 5.

The genie counts the number of ‘$0$’ symbols in the window (i.e., the
cardinality of $\\{s\leq i\leq e|z_{i}=0\\}$),

  6. 6.

If the count is at least $h/2$, the genie sets $\mathbf{y}_{\mathrm{left}}$ to
the remainder of $\mathbf{z}$ after deleting $z_{1}$ to $z_{e}$ and then
finishes by returning $\mathbf{y}_{\mathrm{left}}$.

  7. 7.

Otherwise, the genie shifts the window one frame right. That is, $h$ is added
to both $s$ and $e$.

    1. (a)

If the window falls off $\mathbf{z}$, that is, if $e>|\mathbf{z}|$, the genie
chooses $\mathbf{y}_{\mathrm{left}}=\epsilon$, the empty string. Otherwise,
the genie continues to the next step.

  8. 8.

We set $\mathbf{y}_{\mathrm{left}}$ to the remainder of $\mathbf{z}$ after
deleting $z_{1}$ to $z_{e}$ and then finish by returning
$\mathbf{y}_{\mathrm{left}}$.

The rationale of above procedure will become clearer after we explain
Aladdin’s algorithm. For now, note that it is well defined and does indeed
satisfy the requirements stated previously. The reader should also keep in
mind that getting into a substep is ‘bad’ with respect to Aladdin’s ability to
mimic the genie. That is, we would like the probability of entering substeps
1a, 4a, or 7a to be ‘small’.

We must address one last point: how the paddings for blocks $i=1$ and $i=\Phi$
are handled. The right padding for $i=1$ and the left padding for $i=\Phi$ are
as above. The left padding for $i=1$ and the right padding for $i=\Phi$ (i.e.,
the edge padding) are given by random sampling from $P_{\mathrm{padLeft}}$ and
$P_{\mathrm{padRight}}$. These choices are coupled so that the genie and
Aladdin always choose the same realizations for these edge paddings.

###  IV-B Aladdin parsing

Aladdin receives the vector $\mathbf{y}$, and as a preliminary step adds the
edge padding on the left and right (both of which are coupled to the genie’s
choices). We denote the resulting vector $\mathbf{y}_{\textrm{pad}}$.
Aladdin’s parsing is given by
$\mathrm{mimicGenie}(\mathbf{y}_{\textrm{pad}},n)$ where the recursive
function $\mathrm{mimicGenie}(\mathbf{z},m)$ is defined by:

  * •

If $m=n_{0}$, Aladdin returns $\mathbf{z}$. Otherwise,

  * •

Aladdin builds $\mathbf{z}_{\mathrm{I}}$ and $\mathbf{z}_{\mathrm{II}}$ as
follows, and then return $\mathrm{mimicGenie}(\mathbf{z}_{\mathrm{I}},m-1)$
(which contains $2^{m-n_{0}-1}$ vectors), followed by
$\mathrm{mimicGenie}(\mathbf{z}_{\mathrm{II}},m-1)$ (which also contains
$2^{m-n_{0}-1}$ vectors). Namely, Aladdin returns $2^{m-n_{0}}$ vectors.

  * •

Let $\mathbf{z}_{\mathrm{I}}$ be the left half of $\mathbf{z}$ and
$\mathbf{z}_{\mathrm{II}}$ be the right half of $\mathbf{z}$ (in case
$|\mathbf{z}|$ is odd, $\mathbf{z}_{\mathrm{I}}$ is longer than
$\mathbf{z}_{\mathrm{II}}$, by one bit). Then, Aladdin trims
$\mathbf{z}_{\mathrm{I}}$ and $\mathbf{z}_{\mathrm{II}}$.

  * •

Trimming $\mathbf{z}_{\mathrm{I}}$ is the “mirror image” of trimming
$\mathbf{z}_{\mathrm{II}}$, which is done as follows:

    * –

Aladdin places a window of length $h$ at the start of
$\mathbf{z}_{\mathrm{II}}$. That is, the window starts at $s=0$ and ends at
$e=h$. If in any stage of the algorithm the window “falls off
$\mathbf{z}_{\mathrm{II}}$”, meaning that $e>|\mathbf{z}_{\mathrm{II}}|$,
Aladdin declares failure.

    * –

Aladdin randomly and uniformly chooses a random dither $\rho^{\prime}$
uniformly from $\\{1,2,\ldots,h\\}$.

    * –

Aladdin shifts the window $\rho$ positions right by adding $\rho$ to both $s$
and $e$.

    * –

Aladdin checks if the window contains at least $h/2$ ‘$0$’ symbols. If it
does, the process continues to the next step. If it does not, Aladdin moves
the window one frame to the right by adding $h$ to both $s$ and $e$, and then
repeats this bullet point.

    * –

Aladdin trims $\mathbf{z}_{\mathrm{II}}$ by removing the first $e$ symbols.

###  IV-C Connections between Aladdin and genie parsing

Let us compare Aladdin’s parsing to that of the genie. First of all, note that
both decoders use $2\Phi-2$ random dithers during their runs (recall that
we’ve denoted a random dither as $\rho$ for the genie and $\rho^{\prime}$ for
Aladdin). To help Aladdin match the genie, these dithers can be _coupled_.
That is, for each choice of random dithers the genie makes we couple a unique
choice of random dithers that Aladdin makes. We also couple the choices of The
utility of this coupling is that, with high probability, both the genie and
Aladdin return the same vector of DZP channel outputs
$(\mathbf{y}^{\star}(i))_{i=1}^{\Phi}$.

Before describing the coupling, we note that, given the DZP parsing, the proof
of Theorem 1 follows essentially the same steps as the main result in [10].
The steps will be detailed in a forthcoming longer version of this paper [21].

For brevity, we explain the coupling in terms of just two dithers. Consider
the $\rho$ that the genie chooses for padding $\mathbf{x}(i)$ from the left,
for $i=\Phi/2+1$. We couple this $\rho$ with the $\rho^{\prime}$ Aladdin
chooses in the topmost part of the recursion, for producing
$\mathbf{z}_{\mathrm{II}}$. Typically, the midpoint of $\mathbf{z}$ is in
$\mathbf{d}^{\mathrm{midright}}(i-1)$ or $\mathbf{d}^{\mathrm{midleft}}(i-1)$.
Aladdin adds the dither $\rho$ to the window, and then shift it one frame
right, until the number of zeros is large enough. By Lemma 2 we conclude that
the number of zeros will typically not be large enough, until the window
contains some part of $\mathbf{d}^{\mathrm{right}}(i-1)$. Consider the first
time this happens, and set the Genie’s $\rho$ to the number of symbols from
$\mathbf{d}^{\mathrm{right}}(i-1)$. One can think of the genie as having a
‘shortcut’ that avoids the previous steps Aladdin took. Both Aladdin and the
Genie have the same window, at this point. If it contains enough zero symbols,
they return the same padding. If it does not, they both shift it one frame
right. At this stage, typically, the window will only contain symbols from
$\mathbf{d}^{\mathrm{right}}(i-1)$, “dirty zeros”. Thus, again by Lemma 2,
Aladdin will typically stop at this stage, as the genie always does, and both
will return the same left padding.

###  -D Proof of Lemma 2

Let $0<\delta<1$ be a constant, dependent on the channel, that we will fix
later. Recall that the expected length of an output corresponding to a single
input is $\beta$, and define

$k=\lceil h(1-\delta)/\beta\rceil\;.$ (9)

We can think of the output $\mathbf{Y}$ as being manufactured as follows. We
input the first bit ($x$) to the channel, then input $k$ more bits (all $x$),
and if the output up to this point has length less than $h+1$, inputting
however many bits (all $x$) are needed in order for the output length to be at
least $h+1$. Then, we possibly remove the first bit of the output, and set
$\mathbf{Y}$ to the first $h$ bits. We will call the output corresponding to
the $k$ input bits after the first input bit the _essential output_. Our proof
hinges on showing that the following two events occur with very high
probability: 1) all of the essential output is contained in $\mathbf{Y}$, and
2) the essential output has more than $h/2$ bits equal to $x$.

Denote by
$\mathbf{Z}=\mathbf{Z}_{1}\odot\mathbf{Z}_{2}\odot\cdots\odot\mathbf{Z}_{k}$
the essential output, where $\mathbf{Z}_{i}$ is the output corresponding to
input bit $i+1$. We find it easier to define bad events: event $A$ occurs if
the length of $\mathbf{Z}$ is at least $h-1$; event $B$ occurs if $\mathbf{Z}$
contains at most $h/2$ bits equal to $x$. Clearly, if neither $A$ nor $B$
occur, the above good events occur111Recall that the output due to the first
input bit has length at most $2$., and we correctly guess $x$.

Now, let us choose

$\delta=\min\left\\{\frac{\gamma}{2\cdot\alpha_{0|0}},\frac{\gamma}{2\cdot\alpha_{1|1}},\frac{1}{2}\right\\}\;,$
(10)

where $\gamma$ is defined in (3). Note that, indeed, $0<\delta<1$. Let

$h_{0}^{\prime}=\frac{2(\beta+1)}{\delta}-1>1\;,$ (11)

where the inequality follows from (10). Assume that $h\geq h_{0}^{\prime}$.

By Hoeffding’s bound [22, Theorem 4.12],

$P(A)\leq
2e^{\frac{-2k\left(\frac{h-1}{k}-\beta\right)^{2}}{4}}=2e^{\frac{-k\left(\frac{h-1}{k}-\beta\right)^{2}}{2}}\\\
\overset{\mathclap{(\text{a})}}{\leq}2e^{\frac{-\left(\frac{h(1-\delta)}{\beta}\right)\cdot\left(\frac{h-1}{k}-\beta\right)^{2}}{2}}\;,$

where $(\text{a})$ follows from (9). Noting the squared term on the RHS, we
next show that

$\frac{h-1}{k}>\frac{h-1}{\frac{h(1-\delta)}{\beta}+1}\geq\frac{\beta}{1-\delta/2}>\beta\;.$

Indeed, the first inequality follows from (9), noting that $h-1$ is positive,
since $h\geq h_{0}^{\prime}>1$; the second follows from (11), recalling that
$h\geq h_{0}^{\prime}$; the third follows since $\delta>0$. Thus, from the
above two displayed equations we conclude that

$P(A)<2e^{\frac{-h\left(\frac{(1-\delta)}{\beta}\right)\cdot\left(\frac{\beta}{1-\delta/2}-\beta\right)^{2}}{2}}\;.$
(12)

For event $B$, we use Hoeffding’s inequality and (9) to get

$P(B)\leq
2e^{\frac{-2k\left(\alpha_{x|x}-\frac{h}{2k}\right)^{2}}{4}}=2e^{\frac{-k\left(\alpha_{x|x}-\frac{h}{2k}\right)^{2}}{2}}\\\
\leq
2e^{\frac{-\left(\frac{h(1-\delta)}{\beta}\right)\cdot\left(\alpha_{x|x}-\frac{h}{2k}\right)^{2}}{2}}\;.$

Focusing on the squared term on the RHS, we now prove that

$\alpha_{x|x}\geq\frac{\beta/2}{1-\delta}\geq\frac{h}{2k}\;.$

The second inequality follows easily from (9). For the first inequality, first
recall that $\beta=\alpha_{x|x}+\alpha_{1-x|x}$, by (1). Thus, it suffices to
prove that $\frac{\alpha_{x|x}-\alpha_{1-x|x}}{2}\geq\delta\alpha_{x|x}\;.$ By
(3), this will follow if we prove that $\gamma\geq\delta\alpha_{x|x}$, which
holds by (10). Thus, from the above two displayed equations we conclude that

$\displaystyle P(B)$ $\displaystyle\leq$ $\displaystyle
2e^{\frac{-\left(\frac{h(1-\delta)}{\beta}\right)\cdot\left(\alpha_{x|x}-\frac{\beta/2}{1-\delta}\right)^{2}}{2}}$
$\displaystyle=$ $\displaystyle
2e^{\frac{-\left(\frac{h(1-\delta)}{\beta}\right)\cdot\left(\frac{\frac{\alpha_{x|x}-\alpha_{1-x|x}}{2}-\delta\alpha_{x|x}}{1-\delta}\right)^{2}}{2}}\;.$

Slightly refining the above arguments, we get from (1), (3), and (10), that

$\frac{\alpha_{x|x}-\alpha_{1-x|x}}{2}\geq\gamma\geq\frac{\gamma}{2}\geq\delta\alpha_{x|x}\;.$

Thus, from the above two displayed equations we get that

$P(B)\leq
2e^{\frac{-\left(\frac{h(1-\delta)}{\beta}\right)\cdot\left(\frac{\gamma-\gamma/2}{1-\delta}\right)^{2}}{2}}=2e^{\frac{-h\left(\frac{1-\delta}{\beta}\right)\cdot\left(\frac{\gamma/2}{1-\delta}\right)^{2}}{2}}\;.$
(13)

In light of (12) and (13), let us define

$c_{0}\triangleq\frac{1}{2}\min\left\\{\underbrace{\scriptstyle{\frac{\left(\frac{(1-\delta)}{\beta}\right)\cdot\left(\frac{\beta}{1-\delta/2}-\beta\right)^{2}}{2}}}_{c_{0}^{\prime}},\underbrace{\scriptstyle{\frac{\left(\frac{1-\delta}{\beta}\right)\cdot\left(\frac{\gamma/2}{1-\delta}\right)^{2}}{2}}}_{c_{0}^{\prime\prime}}\right\\}$

and take $h_{0}\geq h_{0}^{\prime}$ large enough such that for all $h\geq
h_{0}$,

$2e^{-h\cdot c_{0}^{\prime}}+2e^{-h\cdot c_{0}^{\prime\prime}}\leq e^{-h\cdot
c_{0}}\;.$

That is, $h_{0}\triangleq\max\\{h_{0}^{\prime},\ln(4)/c_{0}\\}$.

## References

  * [1] R. Gallager, “Sequential decoding for binary channels with noise and synchronization errors,” 1961, Lincoln Lab Group Report.
  * [2] R. L. Dobrushin, “Shannon’s theorems for channels with synchronization errors,” _Problemy Peredachi Informatsii_ , vol. 3, no. 4, pp. 18–36, 1967\.
  * [3] M. C. Davey and D. J. MacKay, “Reliable communication over channels with insertions, deletions, and substitutions,” _IEEE Trans. Inform. Theory_ , vol. 47, no. 2, pp. 687–698, 2001.
  * [4] M. Mitzenmacher, “A survey of results for deletion channels and related synchronization channels,” _Probability Surveys_ , vol. 6, pp. 1–33, 2009\.
  * [5] Y. Kanoria and A. Montanari, “Optimal coding for the binary deletion channel with small deletion probability,” _IEEE Trans. Inform. Theory_ , vol. 59, no. 10, pp. 6192–6219, 2013.
  * [6] M. Rahmati and T. M. Duman, “Upper bounds on the capacity of deletion channels using channel fragmentation,” _IEEE Trans. Inform. Theory_ , vol. 61, no. 1, pp. 146–156, 2015.
  * [7] J. Castiglione and A. Kavcic, “Trellis based lower bounds on capacities of channels with synchronization errors,” in _Information Theory Workshop_. Jeju, South Korea: IEEE, 2015, pp. 24–28.
  * [8] M. Cheraghchi, “Capacity upper bounds for deletion-type channels,” _Journal of the ACM (JACM)_ , vol. 66, no. 2, p. 9, 2019.
  * [9] I. Tal, H. D. Pfister, A. Fazeli, and A. Vardy, “Polar codes for the deletion channel: Weak and strong polarization,” in _Proc. IEEE Int. Symp. Inform. Theory_ , 2019, pp. 1362–1366.
  * [10] ——, “Polar codes for the deletion channel: weak and strong polarization,” 2020, preprint arXiv:1904.13385v2.
  * [11] R. Wang, R. Liu, and Y. Hou, “Joint successive cancellation decoding of polar codes over intersymbol interference channels,” 2014, preprint arXiv:1404.3001.
  * [12] R. Wang, J. Honda, H. Yamamoto, R. Liu, and Y. Hou, “Construction of polar codes for channels with memory,” in _2015 IEEE Information Theory Workshop_ , October 2015, pp. 187–191.
  * [13] E. K. Thomas, V. Y. F. Tan, A. Vardy, and M. Motani, “Polar coding for the binary erasure channel with deletions,” _IEEE Communications Letters_ , vol. 21, no. 4, pp. 710–713, April 2017.
  * [14] K. Tian, A. Fazeli, A. Vardy, and R. Liu, “Polar codes for channels with deletions,” in _55th Annual Allerton Conference on Communication, Control, and Computing_ , 2017, pp. 572–579.
  * [15] K. Tian, A. Fazeli, and A. Vardy, “Polar coding for deletion channels: Theory and implementation,” in _IEEE International Symposium on Information Theory_ , 2018, pp. 1869–1873.
  * [16] ——, “Polar coding for deletion channels,” 2018, submitted to IEEE Trans. Inform. Theory.
  * [17] Y. Li and V. Y. F. Tan, “On the capacity of channels with deletions and states,” 2019, preprint arXiv:1911.04473.
  * [18] E. Şaşoğlu and I. Tal, “Polar coding for processes with memory,” _IEEE Trans. Inform. Theory_ , vol. 65, no. 4, pp. 1994–2003, April 2019\.
  * [19] B. Shuval and I. Tal, “Universal polarization for processes with memory,” 2018, preprint arXiv:1811.05727v1.
  * [20] ——, “Fast polarization for processes with memory,” _IEEE Trans. Inform. Theory_ , vol. 65, no. 4, pp. 2004–2020, April 2019.
  * [21] H. D. Pfister and I. Tal, “Polar codes for channels with insertions, deletions, and substitutions,” arXiv preprint in preparation.
  * [22] M. Mitzenmacher and E. Upfal, _Probability and Computing: Randomizition and Probabilistic Techniques in Algorithms and Data Analysis_ , 2nd ed. Cambridge, UK: Cambridge University Press, 2005\.


# Driving innovation through project based learning: A pre-university STEAM
for Social Good initiative

Gayathri Manikutty  AMMACHI labs
Amrita Vishwa Vidyapeetham
Amritapuri, India
0000-0003-2245-1550  Sreejith Sasidharan  AMMACHI labs
Amrita Vishwa Vidyapeetham
Amritapuri, India
0000-0002-9049-8759  Bhavani Rao  AMMACHI labs
Amrita Vishwa Vidyapeetham
Amritapuri, India
0000-0003-2626-1973

###### Abstract

The Covid pandemic is a clarion call for increased sensitivity to the
interconnected nature of social problems facing our world today. A future-
oriented education on critical issues, such as those outlined in the United
Nations Sustainable Development Goals (UN SDGs) and designing potential
solutions for such problems is an imperative skill that must be imparted to
children to help them navigate their future in today’s unpredictable world.
Towards this goal, we have been conducting 3.5 month-long mentoring sessions
for pre-university students in India to participate in a STEAM for Social Good
innovation challenge conducted annually by the Government of India. Using
digital and physical computing skills, we helped children explore creative
solutions for social problems through a constructionist approach to learning,
wherein they ideated and reflected upon the problems in their communities. The
children learnt the Engineering Design Thinking process and worked in online
groups of two or three, from concept to completion. Despite the constraints
posed by the pandemic, they explored creative ways to think about design and
innovation. They completed a variety of tasks by making, tinkering,
engineering, assembling, and programming to grasp the intricate relationship
between software and hardware. Subsequently, the children showcased their
creative abilities through video storytelling to a panel of domain experts. In
this paper, we present the children’s perspective of their experiences through
this journey, the evaluation metrics based on IEEE design principles, and our
learnings from conducting this initiative as a university-school partnership
model for 84 middle and high school students. The aspirational intent of this
initiative is to make the children better social problem solvers and help them
perceive social problems as opportunities to enhance life for themselves and
their communities.

###### Index Terms:

Experiential learning; 21st century skills; K-12 STEAM education; STEAM based
social problem solving for UN SDGs; engineering design process

##  I Introduction

Project-based learning is a constructivist, student-centred approach where
students learn by completing personally meaningful projects [1]. Constructive
social problem solving is a cognitive-behavioral process to develop positive
problem orientation and undertake community and societal social problem
solving as a conscious, rational, effortful, and purposeful activity [2]. We
adopted a pedagogical approach that purposefully situated engineering and
technology knowledge and fluency within the context of social problem-solving.
We created a project-based learning environment for student teams to research
and gather information on societal problems, ideate solutions and create
working prototypes through the engineering design process. We called our pre-
university STEAM for Social Good initiative - the Amrita ATL Marathon training
and mentorship program. This program was a IEEE TryEngineering STEM Program
executed by IEEE Kerala Section Education Society and AMMACHI Labs, Amrita
Vishwa Vidyapeetham. In this paper, we herewith present our learnings and
impact results.

The shift in the Indian schooling system from an instructionist model wherein
students follow tightly structured learning paths to a constructionist
project-based learning model is happening at a slow pace. In the _New Vision
for Education: Fostering Social and Emotional Learning Through Technology_
report, World Economic Forum identified sixteen critical 21st-century skills
[3]. They divided the skills into three broad categories, namely foundational
literacies (literacy, numeracy, scientific literacy, Information and
Communication Technology (ICT) literacy, financial literacy, cultural and
civic literacy), competencies (critical thinking/problem solving, creativity,
communication and collaboration), and character qualities (curiosity,
initiative, persistence/grit, adaptability, leadership, social and cultural
awareness). Adoption of these 21st-century skills into India’s educational
standards can be accelerated only by transforming the way science and
technology skills are taught and learnt, ranging from one-way content
dissemination imparted by the teacher and memorization by the learner to
student-centred, hands-on, meaningful learning experiences through project
based learning. With this in mind, the Government of India initiated the ATL
Marathon as a national level innovation challenge. This challenge is conducted
annually to enhance childrens’ understanding of wicked societal problems and
encourage them to engineer local solutions for global issues by delving deep
into the process of designing, innovating and inventing practical solutions.
Our training program focused on preparing student teams from three schools to
participate in this challenge.

Atal Tinkering Labs or ATLs are makerspaces that have been setup by the
Government of India in 10,000 schools across India to create and promote a
culture of innovation and entrepreneurship [4]. Our prior research with rural
middle school children on integrative STEAM education workshops conducted in
ATL Makerspaces has shown that such workshops improved children’s sense of
agency and interest in maker projects, robotics and computational thinking [5,
6, 7]. Since 2016, we have conducted several workshops in these makerspaces
using innovative STEAM-based curriculum. We have observed that by
incorporating arts with STEM, creativity and curiosity is fostered in children
[8, 9]. It allows for more human-centered innovations and encourages children
to think deeply about technological development that is responsive to the
needs, desires, and challenges of users [11, 10]. While doing projects in the
makerspaces, children learn 21st-century skills of creativity, communication,
collaboration and critical thinking by actively working in groups wherein they
divide tasks, manage time, work together and debate upon different ideas [12,
7]. Our prior research findings highlight the importance of hands-on
integrative STEAM education especially within a primarily instructionist
education system. In our present research, we attempted to integrate
engineering design thinking with STEAM for social problem solving through a
3.5 month mentorship and training program.

Dym et al. defined engineering design as a thoughtful process, stating that
“Engineering design is a systematic, intelligent process in which designers
generate, evaluate, and specify concepts for devices, systems, or processes
whose form and function achieve clients’ objectives or users’ needs while
satisfying a specified set of constraints” [13]. They further elaborated that
engineering design thinking is a complex cognitive and creative process which
involves several skills. This includes the ability to “tolerate ambiguity that
shows up in viewing design as inquiry or as an iterative loop of divergent-
convergent thinking; maintain sight of the big picture by including systems
thinking and systems design; handle uncertainty; make decisions; think as part
of a team in a social process; and think and communicate in the several
languages of design”. Thus by helping young children work through the
engineering design process, we can cultivate a growth mindset in them to
pursue challenging goals, practise thinking out of the box, embrace failures
and seek advice for systematically evolving their designs. The focus of the
children can be shifted from competing with others to developing openness and
creating a passion for learning.

Through our intervention, we attempted to compensate for the lack of adequate
practicality in traditional pedagogy and complement existing pedagogical
approaches with engineering design thinking skills that are currently
unaddressed for this student demographics. Our instruction method was
predominantly student centered wherein students extended and refined their
imbibed knowledge in developing new applications. In this study, we adopted
the engineering design thinking process that was proposed by IEEE
TryEngineering.org. IEEE TryEngineering.org STEM Portal is an effort to
support pre-university students and teachers from around the world with
resources and educational materials aimed at promoting quality STEM education
[14]. Our mentorship program followed the seven step process which included

  * Step 1: Identifying the problem

  * Step 2: Researching the problem

  * Step 3: Developing possible solutions

  * Step 4: Selecting the best possible solution

  * Step 5: Constructing a prototype

  * Step 6: Testing and evaluating the prototype solution

  * Step 7: Redesigning

For this research study, our research questions were:

  1. 1.

What kind of impact does engineering design thinking process have on the
learning opportunities for middle and high school students in India when it is
incorporated into a project-based social problem solving program?

  2. 2.

What kind of changes will children see in themselves in terms of adoption of
advanced technologies like artificial intelligence, internet of things, game
development, robotics and web development for social problem solving?

  3. 3.

What kind of impact does such a program have on student’s perceived
competence, autonomy and relatedness?

We hypothesized that children would get significant learning opportunities
through our egalitarian program that would be equal regardless of gender or
school locale (rural versus urban). The learning experiences we designed
included opportunities for learning how technology can positively impact lives
and opportunities for engaging in hands-on design challenges through advanced
physical and digital computing skills. Based on this, we hypothesized that
children’s perceived ability to integrate advanced technology into their
projects would be enhanced. We present evidence of the impact of the program
on children’s perceived competence, autonomy and relatedness by using the data
collected and analyzed from 54 participants. We conclude this paper by sharing
our learnings and provide recommendations for replicating this program across
India and the world over.

##  II Theoretical Framework

The self systems theory and self determination theory postulates that humans
have three fundamental psychological needs: competence, relatedness and
autonomy [15, 16]. When children have experiences with high self-system
variables, their engagement and motivation are higher [19]. We shall now
elaborate how we designed the program to boost these three needs.

###  II-A Competence

As stated earlier, the goal of our interdisciplinary pedagogy was to teach
digital and physical computing concepts and tools while also providing real-
world learning experiences. The 2011 report from the National Center on Time &
Learning (NCTL), _Strengthening Science Education: The Power of More Time to
Deepen Inquiry and Engagement_ stated that when children spent more time in a
school day in pursuit of STEM activities that were more hands-on and involved
scientific discourses, it strengthened their competencies in STEM disciplines
in a deeper way [20]. Furthermore, Bybee stated that the development of
innovative discoveries and applications requires broader and more integrative
STEM educational experience wherein students have opportunities to work
fluently and harmoniously across discipliness [21]. He also added that an
integrated STEM education should focus on issues related to the “global
commons” such as energy efficiency, environmental quality, health maintenance
and disease prevention. These issues are an integral part of social problem
solving for sustainability and the United Nations Sustainable Development
Goals (UN SDGs). Thus we can increase children’s perceived competence by
designing a cross-disciplinary pedagogical approach to teach digital and
physical computing concepts while providing hands-on, real-world learning
opportunities through social problem solving.

###  II-B Relatedness

The need for relatedness is a fundamental human need [22]. Interpersonal
relationships can help students cope up with stress and promote positive
motivational states especially during adolescent years [23]. According to the
gender role socialisation perspective, girls may benefit more from close ties
with teachers and mentors because closeness is congruent with greater
affiliation in social relationships that are expected of girls [24].
Therefore, we made every effort to provide an encouraging atmosphere to all
children during the program, wherein they could request for as many mentoring
sessions as they needed for their projects. Mentors were always courteous and
provided effort related praise as required.

###  II-C Autonomy

Prior research also states that when autonomy needs are met, students can
develop intrinisic motivation which can, in turn influence their orientation
towards different achievement goals [15, 25]. According to self systems
theory, autonomy is a crucial facilitator of engagement [16]. Several research
studies have also shown that students’ observed and self reported engagement
is linked to the support for autonomy they received from teachers [17, 18].
Therefore, we designed the program such that teachers and mentors can support
these needs by showing involvement, listening more, asking more about what
students wanted to do, encouraging students to ask questions, responding more
to student generated questions, and taught in ways that supported student
autonomy.

###  II-D Inclusivity

Another key factor in our program design was inclusivity. An inclusive STEM
program is focused on preparing underrepresented youth for the successful
pursuit of advanced STEM studies [26]. Recent research studies have shown that
such programs can reduce or reverse gender gaps in science attitudes and
overall academic achievement [27]. We actively recruited girl students and
encouraged them to form all girls’ teams to participate in the program. We
also actively sought students from rural regions to participate alongside
their urban counterparts. Three schools participated in the program - a rural
school, a semi-urban one and an urban school.

##  III Mentoring Sessions and Training Program Setup

At the start of the program, students from the three schools formed their own
teams of two or three students each. When students were unable to select their
teammates, their teachers helped them form teams. Students could form teams of
the same or mixed gender and could be an inter-school team as well. Since
students studying in grades 6 to 12 were invited to participate in this
program, teams could also be of mixed grade. The mentoring team consisted of
eleven STEM professionals, of which six were women. Nine educators from the
three schools also supported the children throughout the entire program.

The national innovation challenge organized by the Government of India called
for student participation under four broad themes, namely, _education_ ,
_social inclusion_ , _health and well-being_ and _energy and transportation_.
The organizers provided two problem statements under each theme from which the
teams could select a problem statement to work on. Alternatively, the student
teams could define their own problem statement as long as the problem
statement fell under one of the four broad themes. An example problem
statement provided by the organizers under the theme of _energy and
transportation_ was - _“Innovate solutions that reduce the carbon footprint as
well as adopt climate-resilient and low-carbon strategies to enable the
transition to a truly sustainable India”_.

Figure 1: Step 1 and Step 2: A participating team identifying and researching
a problem Figure 2: Step 3 and Step 4: Another team’s ideation exercise to
select an appropriate solution

We began the program by introducing the children to the Engineering Design
Process (EDP) and showed them several examples for applying the EDP in
developing and testing a prototype. The mentors then met each team
individually and helped them either select one problem statement from the
eight given problem statements or helped the team define their own problem
statement. Then we helped the teams conduct primary and secondary research on
their selected problem statement. Teams first conducted secondary research
using existing data such as books, reports or research articles to understand
why the problem exists and what has been done to address it in the past. Some
teams then went one step further and conducted primary research to gather new
data to understand who they are designing for and what kind of solution would
they potentially plan on designing. After this came the solution
identification step. Students practised divergent thinking to come up with
several different solutions and then used convergent thinking to narrow down
on the solution they wanted to finally work on. For several teams steps 1 - 4
was an iterative process. They went back and forth over the steps several
times before converging on a solution. Fig. 1 and Fig. 2 shows the research
and ideation process that two teams did during the program.

As each student team ideated on the problems and solutions, we asked them to
document their journey using presentation slides and a 1-2 minute video
capturing their chosen problem statement, the primary and secondary research
undertaken and the solution they finally selected. As part of the
documentation, we encouraged the teams to include an overview of their
understanding of EDP and how it was applied in formulating their solution.
Throughout the ideation process, mentors and school teachers provided feedback
to the teams on innovation, impact, and practicality of their solutions to
complete within the stipulated time and with the resources available in their
school ATL makerspaces.

After this step, the teams moved into the prototype development stage. Teams
built either digital prototypes or physical prototypes for their solutions as
shown in Fig. 3 and Fig. 4. During this stage, mentors gathered student teams
working on similar technologies and provided in depth training to the teams.
In all, the mentor team conducted eight hands-on workshops covering fifteen
digital and physical computing skills with varying difficulty levels. The
prototype development phase extended over a two month period wherein teams had
to work patiently over different kinds of challenges. Some teams had
difficulty working together, with inherent disagreements and leadership issues
to contend with, while some team members quit midway due to various reasons.
Some teams could not get their prototype working because its difficulty level
was a big leap from their level of understanding. So mentors had to take some
teams back to ideation stage to select a simpler solution and start all over
again. And amidst all this was also the need to handle quarantines and
innumerable difficulties the Covid Pandemic brought on with it. We have
documented our journey through this program at [31]

Figure 3: Step 5: Student developing artwork for a game prototype.

Figure 4: Step 5: Students building hardware prototypes Figure 5: Step 6:
Students testing their prototype and taking measurements to measure efficacy
of their solution.

##  IV Methods

###  IV-A Participant Profile

We started the program with 108 children forming 40 teams from three different
schools in Kerala, India. A total of 84 children (77%)(38 girls, 46 boys)
completed the program. The large attrition rate was due to the multitudinal
challenges posed by the Covid pandemic, academic pressures and the poor
network connectivity some children faced, especially those from rural regions.
The ages of the participants ranged from 10 to 16 years. The children formed
32 teams of two or three members each with 13 all-girls’ teams. Of the 84
students who completed the program, a total of 52 (22 girls) participants
completed the program impact survey. Eight participants chose not to disclose
their school location in the survey.

###  IV-B Data Collection Instrument

IEEE Pre-University team has formulated a set of three guiding design
principles for IEEE Pre-university STEM outreach programs to have the biggest
possible impact. Outlier Research and Evaluation has designed a program impact
evaluation questionnaire based on the three design principles [32]. We adapted
this impact evaluation questionnaire to collect feedback from the students
about our program.

The first design principle measures the effectiveness of the program in
teaching modes in which engineering can make a difference. Since our program
included learning opportunities for students such as meeting stem
professionals, engaging in hands-on challenges, learning technical skills and
participating in solving real-world problems, we administered a questionnaire
with eight items to measure all the learning opportunities the children
received through the program. These included

  1. 1.

In this program, I learnt how technology positively impacts people and
communities

  2. 2.

In this program, I learnt how engineers and technical professionals make an
impact on society through their work

  3. 3.

In this program, I met someone who works in the STEM

  4. 4.

I learnt to make something hands-on in this program

  5. 5.

In this program, I learnt new ways to solve problems

  6. 6.

In this program, I learnt about electronics hardware

  7. 7.

In this program, I learnt about software

  8. 8.

In this program, I learned something about different branches of Engineering

We measured students perceived competence based on their feedback on the
learning opportunities and on one additional item, namely,

  1. 1.

I am more confident as a student

The second design principle measures how actively the program recruits youth
who are in groups that are underrepresented in engineering. We measured
children’s impressions using the following two items.

  1. 1.

This program showed me how people with very different backgrounds can be
engineers and technical professionals

  2. 2.

This program was for people with very different backgrounds

The third design principle measures the quality of the program design and its
content. The entire program was designed for children to work in teams and
encouraged collaboration on projects. Because fostering student choice and
voice increases student engagement and ownership in learning, the third design
principle we used was to give each student choices on what projects they
wanted to do, who they will work with and how they will divide the work
amongst themselves. Mentors role modelled growth mindset and provided an
atmosphere of positive feedback without any judgements or comparisons. Mentors
gave opportunities for students to request for guidance as many times as the
student teams needed. To measure this, we included two items on students’
perceived autonomy and two items on supportive relationships, that is
perceived relatedness. The four items were:

  1. 1.

In this program, I had choices in what to learn

  2. 2.

In this program, I got to choose partners during learning

  3. 3.

In this program, all the adults [mentors and teachers] were friendly

  4. 4.

In this program, the other participants [children] were friendly

Additionally, to measure the quality of the program content, we administered
the Stages of Adoption of Technology (SA) [28] instrument to assess the
improvement in stages of adoption of advanced technologies by the children.
The SA instrument includes six stages which are:

  * Stage 1: Awareness

  * Stage 2: Learning the process

  * Stage 3: Understanding the application of the process

  * Stage 4: Familiarity and confidence

  * Stage 5: Adaptation to other contexts

  * Stage 6: Creative applications to new contexts

We asked the children to choose the stage of adoption that most appropriately
described their stage of adoption of advanced technologies including
artificial intelligence, internet of things, game development, robotics and
web development at the beginning and at the end of the program.

##  V Results and Discussion

In this section, we report our key findings towards the three research
questions from the program impact survey administered to the participants at
the end of the program.

H1: The experience with learning opportunities will be equal regardless of
gender and location.

All the participants believed that they had a good learning experience through
this program. Fig. 6 shows the box plots of the means which were 4.0 or above
for boys and girls and rural and urban schools. The Cronbach’s alpha for the
eight items was $\alpha=0.720$. Independent samples t-test showed that there
was no statistically significant difference between experiences with learning
opportunities between girls (4.05 ± 0.51) and boys (4.07 ± 0.51), t(50)=0.15,
p=0.88. Similarly, there was no statistically significant difference between
rural (3.96 ± 0.49) and urban schools (4.21 ± 0.48), t(45)=1.65, p=0.11. These
results provide evidence that the program provided equal learning
opportunities for all children. We also provide some excerpts from the
children’s qualitative feedback on the program in support of the above.

One of the female participants from an urban school wrote “I liked the ATL
marathon program [mentorship program] because it was like helping people with
the use of modern technology. And I love to help people and I always wanted to
know more about technology. And so this was my chance to learn much more about
technology and to help people.” (Gayathry)

Another female participant from a semi urban school agreed saying “ATL
marathon is a hands-on program that enable[s] students to solve problems
throughout Design thinking process. From this younger age itself a child is
being punctual, thinks like a mechanical engineer or a software engineer and
handles project work and school studies hand in hand. It’s really fun, mentors
and teachers are like our friends who help us whenever in need.” (Arunima)

A male participant from a rural school wrote “I like this program very much, I
learnt about new technology and how technology can help society. The most
important thing about ATL marathon was the mentors. I am very much blessed to
have my mentor. Without his help, we were unable to complete the project. His
patience, care, continuous guidance and support made this project a successful
one.” (Advaith)

Figure 6: Box plots of learning opportunities in terms of gender and school
locale

H2: Program would significantly impact children’s perceived ability to
integrate advanced technology into their projects and will impact equally
regardless of gender and location.

Fig.7 shows the radar plot with the children’s responses on the Russell’s
stage that most appropriately described their stage of adoption of advanced
technologies at the beginning and at the end of the program [29]. The plot,
split between boys and girls, shows the increase in technology adoption before
and after the program as perceived by the children. Seven students (13%) did
not think that their stage of technology usage had improved, all the other
participants (83%) reported one or more levels of improvement. We conducted a
Friedman test to compare self reported technology adoption scores before and
after the program. The results show a significant difference,
${\chi}^{2}(1)=45$, p = 0.00 in technology adoption scores. Friedman test also
showed significant different for boys ( ${\chi}^{2}(1)=25$, p = 0.00), girls (
${\chi}^{2}(1)=20$, p = 0.00), rural ( ${\chi}^{2}(1)=24$, p = 0.00), semi-
urban ( ${\chi}^{2}(1)=11$, p = 0.00) and urban ( ${\chi}^{2}(1)=5$, p =
0.03).

Figure 7: Stages of usage of technology before and after the program

H3: Program would impact children’s perceived competence, autonomy and
relatedness equally regardless of gender and location

The third finding from our STEAM engineering design thinking program is that
the participants reported high competence, autonomy and relatedness from the
program. Independent samples t-test showed that there was no statistically
significant difference between perceived competence of girls (4.25 ± 0.44) and
boys (4.17 ± 0.50), t(50)=0.62, p=0.54. There was also no statistically
significant difference between rural (4.19 ± 0.52) and urban schools (4.20 ±
0.42), t(45)=0.05, p=0.96. Likewise, there was no statistically significant
difference between perceived autonomy of girls (4.25 ± 0.78) and boys (4.22 ±
0.58), t(50)=0.18, p=0.86. There was also no statistically significant
difference between rural (4.35 ± 0.59) and urban schools (4.03 ± 0.76),
t(45)=1.60, p=0.12.

Our analysis also showed that there was statistically significant difference
between perceived relatedness of girls (4.82 ± 0.33) and boys (4.53 ± 0.51),
t(50)=2.3, p=0.03. The statistical significance in perceived relatedness
between girls and boys tells us that girls found the program to be more
emotionally supportive and less stressful than the boys. We observed during
the program that a few of the boy’s teams had significant conflicts and
disagreements among the team members which affected the overall team dynamics.
However, the support extended by the teachers and mentors helped some of those
teams to recover and complete their working prototypes successfully, while a
few boys quit the program. This is reflected in the children’s feedback. There
was no statistically significant difference between the experiences of rural
(4.58 ± 0.53) and urban school children (4.75 ± 0.32), t(45)=1.16, p=0.25.

To sum it up, STEAM based Engineering Design Thinking programs on real world
problem solving have a strong motivational aspect because they strongly
influence the universal psychological needs of competence, autonomy and
relatedness through a new social context, such as an extended after-school
training program. Such programs communicate powerful lived experiences to
adolescent children that shape their beliefs about themselves. To quote a girl
participant “From dreaming to realization of it, ATL Marathon made the
difference. This training program truly enlarged my vision of AI (Artificial
Intelligence) and made me believe that nothing is impossible! Surely this
program is recommended for each and every kid. I strongly believe that each
and every student has a silent capability and talent hidden somewhere, which
could be explored and expressed. Platforms of this magnitude serves well to at
least cater a few. Hats off to the entire team who made it possible for me.
Thank you very much from the bottom of my heart to make me believe that my
dreams can be realized.” (Saavya)

Challenges faced during program execution Due to the Covid pandemic and the
resulting school closures, we had to conduct nearly 80% of the program online.
This posed many challenges because several children had access only to
smartphones and not to laptops or desktop computers at their home. To
workaround this problem, mentors taught children alternative smartphone-based
methods to use design and prototyping tools that were primarily designed for
laptop or desktop usage. Despite being slower, many resourceful children could
develop and demonstrate working digital prototypes by just using a smartphone.

The online nature of the program made it difficult for children to collaborate
with their team mates. We encouraged them to use online collaborative tools
like Google Jamboard and Miro boards to make collaboration easier. Also,
working online on team projects made it harder for the teams to debug their
hardware issues. Towards the last three weeks of the program, we invited
student teams to come in small batches to their ATL Makerspace following
Covid-19 protocols and complete their projects.

##  VI Conclusion

Engineering design thinking is a creative process of identifying a problem,
defining the problem, designing a solution, and creating innovation in the
form of a working prototype. When integrated with social problem solving for
UN SDGs, it gives a powerful learning experience for all children regardless
of gender and school locale. Our results provide evidence that such programs
offer equal learning opportunities for children in technical and non-technical
skills, improve their perceived abilities in the use of advanced technologies
such as artificial intelligence and IoT to design solutions for the greater
good and bolster their psychological need for competence, autonomy and
relatedness. Our research shows that even young pre-university students can
think about complex systems and their interconnections and design innovative
solutions. Such a constructionist approach to project-based learning builds
student motivation and student engagement. It opens up avenues for children
towards purposeful social interactions that reshape their self-beliefs.

## Acknowledgment

We wish to express our gratitude to Sri Mata Amritanandamayi Devi, a world-
renowned humanitarian and spiritual leader without whose guidance and undying
support this research project would not have been possible. Many thanks to the
mentor team comprising of researchers from Amrita Vishwa Vidyapeetham and
alumni for helping us conduct this mentorship program. We would also like to
thank the teachers, principals, and students of Amrita Vidyalayam schools for
participating in this mentorship program and providing their valuable
feedback.

## References

  * [1] Kokotsaki, D., Menzies, V., & Wiggins, A. (2016). Project-based learning: A review of the literature. Improving schools, 19(3), 267-277.
  * [2] Chang, E. C., D’Zurilla, T. J., & Sanna, L. J. (2004). Social problem solving: Theory, research, and training. American Psychological Association.
  * [3] World Economic Forum. (2016, January). New vision for education: Fostering social and emotional learning through technology. Geneva: World Economic Forum.
  * [4] Atal Tinkering Labs. https://aim.gov.in/atl.php
  * [5] Alekh, V., Vennila, V., Nair, R., Susmitha, V., Muraleedharan, A., Alkoyak-Yildiz, M., Akshay N & Bhavani, R. R. (2018, June). Aim for the sky: Fostering a constructionist learning environment for teaching maker skills to children in India. In Proceedings of the Conference on Creativity and Making in Education (pp. 87-94).
  * [6] Manikutty, G., Frey, L. M., Natarajan, A., Chilakapati, U., & Vennila, V. (2019, December). I Can Also Make Robots! Inspiring Rural Indian Children to Learn Robotics. In 2019 IEEE Tenth International Conference on Technology for Education (T4E) (pp. 78-85). IEEE.
  * [7] Manikutty, G. (2021, October). My Robot can tell stories: Introducing robotics and physical computing to children using dynamic dioaramas. In 2021 IEEE Frontiers in Education Conference (FIE) (pp. 1-9). IEEE.
  * [8] Daugherty, M. K. (2013). The Prospect of an” A” in STEM Education. Journal of STEM Education: Innovations and Research, 14(2).
  * [9] Mukil, M. V., Manikutty, G., Vijayan, D., Rangudu, A., & Bhavani, R. R. (2019). When elephants nodded and dolls spoke: Bringing together robotics and storytelling for environmental literacy.
  * [10] Chen, Chi Wai Jason, and Kit Mei Jammie Lo. ”From teacher-designer to student-researcher: A study of attitude change regarding creativity in STEAM education by using Makey Makey as a platform for human-centred design instrument.” Journal for STEM Education Research 2, no. 1 (2019): 75-91.
  * [11] Susmitha, V., Akshay, N., Vennila, V., Muraleedharan, A., Nair, R., Velayudhan, A., … & Bhavani, R. R. (2018, December). All aboard for the joy of making! teaching user centered design and tinkering to middle school children in india. In 2018 IEEE Tenth International Conference on Technology for Education (T4E) (pp. 33-40). IEEE.
  * [12] Manikutty, G., Akshay, N., Shetty, R., & Bhavani, R. R. (2020, June). Social making: teaching children to design solutions for the global goals. In Proceedings of the 2020 ACM Interaction Design and Children Conference: Extended Abstracts (pp. 145-150).
  * [13] Dym, C. L., Agogino, A. M., Eris, O., Frey, D. D., & Leifer, L. J. (2005). Engineering design thinking, teaching, and learning. Journal of engineering education, 94(1), 103-120.
  * [14] TRYEngineering Engineering Design Process. https://tryengineering.org/volunteer-resources/stem-pedagogy/engineering-design-process/
  * [15] Niemiec, C. P., & Ryan, R. M. (2009). Autonomy, competence, and relatedness in the classroom: Applying self-determination theory to educational practice. Theory and research in Education, 7(2), 133-144.
  * [16] Connell, J. P., & Wellborn, J. G. (1991). Competence, autonomy, and relatedness: A motivational analysis of self-system processes.
  * [17] Assor, A., Kaplan, H., & Roth, G. (2002). Choice is good, but relevance is excellent: Autonomy‐enhancing and suppressing teacher behaviours predicting students’ engagement in schoolwork. British journal of educational psychology, 72(2), 261-278.
  * [18] Reeve, J., Bolt, E., & Cai, Y. (1999). Autonomy-supportive teachers: How they teach and motivate students. Journal of educational psychology, 91(3), 537.
  * [19] Roorda, D. L., Koomen, H. M., Spilt, J. L., & Oort, F. J. (2011). The influence of affective teacher–student relationships on students’ school engagement and achievement: A meta-analytic approach. Review of educational research, 81(4), 493-529.
  * [20] Traphagan, K. (2011). Strengthening science education: The power of more time to deepen inquiry and engagement. National Center on Time and Learning.
  * [21] Bybee, R. W. (2013). The case for STEM education: Challenges and opportunities. NSTA press
  * [22] Baumeister, R. F., & Leary, M. R. (1995). The need to belong: desire for interpersonal attachments as a fundamental human motivation. Psychological bulletin, 117(3), 497.
  * [23] Martin, A. J., & Dowson, M. (2009). Interpersonal relationships, motivation, engagement, and achievement: Yields for theory, current issues, and educational practice. Review of educational research, 79(1), 327-365.
  * [24] Maccoby, E. E. (1998). The two sexes: Growing up apart, coming together (Vol. 4). Harvard University Press.
  * [25] Ames, C. (1992). Classrooms: Goals, structures, and student motivation. Journal of educational psychology, 84(3), 261.
  * [26] Peters-Burton, E. E., Lynch, S. J., Behrend, T. S., & Means, B. B. (2014). Inclusive STEM high school design: 10 critical components. Theory Into Practice, 53(1), 64-71.
  * [27] LaForce, M., Zuo, H., Ferris, K., & Noble, E. (2019). Revisiting Race and Gender Differences in STEM: Can Inclusive STEM High Schools Reduce Gaps?. European Journal of STEM Education, 4(1), 8.
  * [28] Christensen, R. (1997). Effect of technology integration education on the attitudes of teachers and their students. Unpublished doctoral dissertation, University of North Texas. Available: https://digital.library.unt.edu/ark:/67531/metadc277676/?q=christensen.
  * [29] Russell, A. L. (1995). Stages in learning new technology: Naive adult email users. Computers & Education, 25(4), 173-178.
  * [30] VertSTEM Questionnaire https://misturamuibi-tijani.github.io/vertstem.html
  * [31] Second Foundation Initiative https://www.secondfoundationinitiative.org/atl-marathon/2021
  * [32] Outlier Research and Evaluation Questionnaire https://outlier.uchicago.edu/