title: EXTRACT MIN algorithm for Young tableau

text:
# Question
Title: EXTRACT MIN algorithm for Young tableau
This are two sections from a task I got.

> The Young tableau is defined as a matrix of m rows on n columns so that the bars in each row are sorted in ascending order Left to right and the elements in each column are sorted in ascending order from top to bottom. Some of the elements in the Young tableau may be $\infty$ we will refer to these elements as non-existent elements . Therefore, the Young tableau can be used to hold finite numbers.
>
> 1. Write an algorithm for EXTRACT-MIN on a non-empty Young tableau of m at n in time running $O(n+m)$
> 2. Show how to insert a new element into a non-complete Young tableau v at the size of m at n in time running $O(m+n)$

That's what I tried:

When I remove the element at the $(1,1)$ I need to move every element in the table 1 step left (and if the col is 1 so move one row up and put it on the last col) so I can solve it on $O(n\*m)$. I think that $O(m+n)$ actually measn $O(max(m,n))$

Regarding the second clause I was thinking to compare the element to insert with the element in the first col in every row until until we get to bigger one and then and then check on this row where to insert it. But again let's say that I want to insert element which will be the min on the new table, so I need to push all the elements one stop left and it takes $O(m\*n)$

# Answer
**Hint**: For EXTRACT-MIN, instead of thinking in terms of shifting rows/columns, try to replace the element at $(1,1)$ by $+\infty$. Now you just want to swap $+\infty$ with one of his neighbour until you get the invariant of a Young tableau. How can you decide where to move it?
> 3 votes

# Answer
Here you can take reference from this link, where above stated algo to find the minimum is explained in a simple way: https://www.geeksforgeeks.org/print-elements-sorted-order-row-column-wise-sorted-matrix/

And for Young Tabeleu method, you can refer this link: http://mathworld.wolfram.com/YoungTableau.html
> 1 votes

# Answer
I am agreeing with the hint provided by @md5, you simply swap the max element with (1, 1) and then swap that max element with the minimum value present in either next column or next row. This way the total number of element you compare or traverse will be ( m + n) which I think will be maximum. For the second clause you first insert the value in empty field in the matrix and then again start traversing but in backward direction and try to replace you newly inserted value with maximum value found in either in current column or previous column. Again you will end up traversing ( m + n) elements. And be sure to check for boundary cases which can save few running time.
> -1 votes

---
Tags: time-complexity, runtime-analysis, matrices
---


# Question
Title: The same transition twice in Pushdown automata (PDA)
If we want to design a PDA that accepts all words those the first half equals reverse of the second half and there is a '#' between them, "ab#ba" for example.

We start push each letter we read and when we read the symbol '#' don't push it and start popping from its next letter and check for match between the current letter and the top of the stack.

But what do we if there is no '#' symbol in the center of the string, can we do the same of usual NFA ?

I mean can we make same transitions twice, each one to distinct state ?

Example : let us be in the state 'q1', when I read the letter make a transition to the state q2 and pop the top of the stack and make a transition to the state q3 without pop ?

# Answer
> 0 votes
Yes, there are both deterministic and non-deterministic pushdown automata.

Non-determistic pushdown automatons can recognize all context-free languages, while deterministic pushdown automatons con only recognize a proper subset of the context-free languages (these languages are called deterministic context-free languages).

---
Tags: automata, pushdown-automata
---


# Question
Title: How do I solve regular expression expansion when I have "+" sign?
For example, I am given this and my output is:

11+11\* = 11, 1, 11, 111, 1111, ......

Since + means or sign, my logic is:

11 appears once or more

Then I work on solving 11\*

Is it perfect?

Thanks.

# Answer
> 0 votes
According to the place of '+', we have different argument, for example: $$1+0$$ '+' sign equivalent to union ($\cup$), so $$1\cup 0.$$ But at another example, $11^+$ means, the second 1 can repeated once or more than once.

Hence, if $+$ appears in exponent of some alphabet, we use that to show the number of repetition is at least one. other wise, if $+$ appears between some alphabet, we conclude that it work as union symbol.

---
Tags: regular-expressions
---


# Question
Title: A so-called random variable not being well-defined
Consider this algorithm:

```
 RANDOMIZED-SELECT(A, p, r, i)
1 if p == r
2  return A[p]
3 q = RANDOMIZED-PARTITION(A, p, r)
4 k = q - p + 1
5 if i == k // the pivot value is the answer
6  return A[q]
7 elseif i < k
8  return RANDOMIZED-SELECT(A, p, q - 1, i)
9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

```

The book CLRS claims that if we set $T(n)$ to be the running time of the algorithm on an input $A$ of size $n$, then $T$ is a random variable. However, I think it's not since if we define $\Omega$ to be the set of all inputs of all sizes $n$ and set $\mathcal{F}$ as $\mathcal{P}(\Omega)$ and let $T$ to be a function from $\Omega$ to $\mathbb{R}$, if $n = m$ then it doesn't follow that $T(n) = T(m)$ since the algorithm might have different running times on arbitrary inputs of the same size. Also note that the algorithm is randomized. So why does it say that $T$ is a random variable?

# Answer
I'm not sure I understand your counterargument but look at it like this:

For given $n$ define $\Omega\_n$ to be all inputs of size $n$ and $\mathcal{F\_n} = \mathcal{P}(\Omega\_n)$.

Let $(T\_{n})\_{n\in\mathbb{N}}$ be a sequence of functions:

$$T\_{n} : \Omega\_n \rightarrow \mathbb{R}$$

Clearly $\forall t,n. \\{\omega \mid T\_{n}( \omega) \leq t \\} \in \mathcal{F\_n}$, which shows that $\forall n. T\_{n}$ is a random variable on $\Omega\_n$.
> 1 votes

# Answer
Our input is specific, but the input maybe have different permutations, so we can't claim that $T$ is a function that map set of all inputs to $\mathbb{R}$. But i think, it's true that we look at $T$ as a function that map a input to a permutation, formally, let $X$ be the input of size $n$, and denote $\mathfrak S\_n$ be the group of the permutations of $X$ : $$ T:X\to \mathfrak S\_n. $$ So $T$ is a random variable that map input $X$ of size $n$ to $\mathfrak S\_n$.
> 1 votes

---
Tags: randomized-algorithms, randomness
---


# Question
Title: Are this languages can be represented by regular expressions?
1. The set of all words with the same number of 0’s and 1’s.
2. The set of all words contained in {0,1}\* that have an even number of 0’s and an odd number of 1’s.

I guess first one is NO. Second one seems no too as we get {0,1,00,11,000,111,...}. Not all of them contains even number of 0s and odd number of 1s.

Am I on the right track? If not, then give me a detailed explanation.

Thanks.

# Answer
For question 1: try to come up with a proof that the language is not regular.

Hint: Let your language be $L$ and suppose towards a contradiction that it is regular. Use the closure properties of regular languages (in particular, regular languages are closed under intersection) to show that there is some regular language $L'$ such that $L \cap L'$ is a well-known non regular language.

Question 2 is not asking you whether all words in $\\{0,1\\}^\*$ contain an even number of $0$s and an odd number of $1$s (that's clearly false). Rather, it wants you to consider the language defined as the set of all possible words (i.e., words from $\\{0,1\\}^\*$) that also satisfy some additional property. This additional property is having both an even number of $0$s and an odd number of $1$s.

Hint: Try to design a DFA $D$ for this language. Suppose you are reading a word from left-to-right and you want to determine whether it satisfies the above property. What do you need to remember? Encode this information in the states of $D$.
> 2 votes

# Answer
> The set of all words with the same number of 0’s and 1’s.

Isn't regular.

**Proof (by contradiction):**

Let $\ell=\\{w\in\Sigma^\*\mid \\#w\_a=\\#w\_b\\}$, and suppose $\ell$ is regular, and let $M=\\{a^nb^n\mid n\geq 0\\}$ that $M\subseteq \ell$.

It's clear that $M$ isn't regular, on the other hand, we know that intersection of two regular languages are regular (by construction method on fsm), so $$\ell\cap a^\*b^\*=M$$ But $M$ isn't regular and it contradict with the fact that intersection of two regular languages are regular, hence, $\ell$ isn't regular.

> The set of all words contained in {0,1}\* that have an even number of 0’s and an odd number of 1’s.

Check this.
> 0 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Which overhead is smaller - function call or passing variables between processes?
the question is related to networking frameworks; callback-based approach requires you to call a callback function every time you receive a new data packet; this is not a good approach for high-load and high-throughput network servers; is it faster to have a 'while-true' loop running in a separate process or a thread, checking for new packets continuously, then passing received data back to the original process, particularly in Python?

# Answer
> callback-based approach requires you to call a callback function every time you receive a new data packet; this is not a good approach for high-load and high-throughput network servers

Who claims that? Node.js, for example, which was specifically designed to avoid overhead in handing high load, uses callback functions exactly for this reason.

> is it faster to have a 'while-true' loop running in a separate process or a thread, checking for new packets continuously, then passing received data back to the original process

No. A function call will always be faster. Calling a function normally just means pushing a stack frame and setting the instruction counter. Although you don't specify what kind of packages you want to send, IP and UDP or TCP will introduce significantly bigger overhead. Note that sending such a package will normally already involve at least one function call.

You should also consider that busy polling (while true loop) will waste energy and potentially cause lots of useless context switches, if you don't have enough cores for all processes you're running.
> 2 votes

---
Tags: functional-programming, computer-networks, process-scheduling, threads, real-time
---


# Question
Title: A confidence interval algorithm for Disagreement coefficient
My question has to do with the disagreement coefficient in active learning. I've been trying to solve the following question, where I need an algorithm to derive a confidence interval for $\theta$, the disagreement coefficient of a given distribution $\cal D\_\cal X$, defined in these notes by Shai-shalev shwartz:

Let $\mathcal{H}$ be a hyposesis class. We define a pseudo-metric on $\mathcal{H}$, based on the marginal distibution $\mathcal{D\_\mathcal{X}}$ over instances, such that:

$$d(h,h')=\Pr\limits\_{x\sim D\_\mathcal{X}} \left\[h(x)\neq h'(x)\right\]$$. We define the corresponding ball of radius $r$ around $h^\*$:

$$B(h^\*,r)=\left\\{h\in\mathcal{H} | \\; d(h,h')\le r\right\\}$$

The disagreement region of a hypothesis subset $V\subseteq\mathcal{H}$ is $$DIS(V)=\left\\{x\big| \\;\exists h,h'\in V: \\; h(x)\neq h'(x)\right\\}$$

We can now define the disagreement coefficient:

> Let $\cal H$ be an hypothesis class, $\cal D$ be a distribution over $\cal X \times \cal Y$ and $\cal D\_\cal X$ be the marginal distribution, i.e., $\Pr\_{X\sim\cal D\_\cal X}(X=x)=\Pr\_{(X,Y)\sim \cal D}(X=x)$. Then given $h\in \cal H$, the $\epsilon$-disagreement coefficient is defined to be $\theta\_{h,\epsilon}=\frac{\Pr(X\in DIS(B(h,\epsilon)))}{\epsilon}.$ The $\epsilon$-disagreement coefficient of $\mathcal{H}$ is $\theta\_\epsilon = max\_{h\in\cal H} \theta\_{h,\epsilon}$.

The question is to find an algorithm that given a sequence of $m$ samples $S=(x\_1,...,x\_m)\sim D\_\mathcal{X}^m$ and $\epsilon\in\[0,1\]$, finds a confidence interval $\[\theta\_l,\theta\_u\]$ for $\theta\_\epsilon$. That is, we want to guarantee that with probability $\ge 1-\delta$ over the choice of $S$ it holds that $\theta\_l\le \theta\_\epsilon\le \theta\_u$.

# Answer
I present here the general direction rather than a complete answer.

If you had known $D=D\_\mathcal{X}$ then you could have computed $\theta\_\epsilon$ yourself, since you can compute the real distances $d(h,h')$ for all $h,h'\in\mathcal{H}$, the real balls $B(h,\epsilon)$ (where by real I mean relative to the distribution $D$), and finally given a ball you could compute its disagreement set and its mass (you actually don't really need $D$ to compute the disagreement set of some $V\subseteq\mathcal{H}$, but you do need it to compute its mass). Unfortunately you don't know $D$, so what you could try is to evaluate all the above objects relative to the empirical distribution $\hat{D}\_S(x)=\frac{1}{m}\sum\limits\_{i=1}^m \mathbb{1}\_{x=x\_i}$.

Suppose that $\forall h,h'\in\mathcal{H}$ we have $d(h,h')\neq\epsilon$. In that case there exists $\eta\>0$ such that $\forall h\in\mathcal{H}: B(h,\epsilon)=B(h,\epsilon-\eta)=B(h,\epsilon+\eta)$. Let $A$ denote the event that there exists $h,h'$ such that $|\widehat{d}(h,h')-d(h,h')|\ge\eta$, where $\widehat{d}(h,h')=\frac{1}{m}\sum\limits\_{i=1}^m \mathbb{1}\_{h(x\_i)\neq h'(x\_i)}$ is the empirical distance. Note that applying Chernoff's inequality and the union bound you can bound the probability of $A$ occurring (it decays exponentially in $m$). Conditioned on $A^C$ (the event that we were $\eta$-close to the real distance for all pairs $h,h'$), it holds that $B\_D(h,\epsilon)=B\_{\widehat{D}}(h,\epsilon)$ for all $h\in\mathcal{H}$. Thus, up to an exponentially small probability, all the $\epsilon$-empirical balls are in agreement with the real $\epsilon$ balls, which means the empirical and real disagreement sets are also equal.

Finally, to evaluate $\theta\_\epsilon$, just go over all $h\in\mathcal{H}$ and compute the empirical mass of the disagreement set of the empirical ball $B\_{\widehat{d}}(h,\epsilon)$. Conditioned on $A^C$, $\forall h\in\mathcal{H} :B\_d(h,\epsilon)=B\_{\widehat{d}}(h,\epsilon)$, and your problem is reduced to evaluating the mass of some disagreement set. Luckily, as $\mathcal{H}$ is finite, there are at most $2^{|\mathcal{H}|}$ disagreements sets, and again by Chernoff and the union bound for large enough $m$ the mass of every set in this family is close to its empirical mass (with high probability). I leave the details to you, observe that this is a distribution dependent bound (because of $\eta$) and we didn't handle the case of $d(h,h')=\epsilon$ for some pair $h,h'$. To handle this you could simply estimate the $\epsilon+\zeta$ ball instead of the epsilon ball (in this manner you will, with high probability, agree with the real $\epsilon$ ball). I leave the right choice of $\zeta$ to you (you want it positive to handle points exactly on the surface, but not too big as to include new points, where points here are in the hypotheses space). Recall that while we could use distribution dependent parameters, namely $\eta$, in the gurantees proof, our algorithm can't acess them (it does not know $D$), so $\zeta$ must be based on the empirical distances.
> 0 votes

---
Tags: machine-learning, learning-theory
---


# Question
Title: Compact representation for quantified boolean formula
I got black-box (too big to analyze) boolean formula f(...) with 3 sets of input arguments: $x\_1... x\_i, y\_1... y\_j, z\_1... z\_k$. And I want to find such values for x-arguments that for every y-arguments exist z-arguments witch satisfy formula: $(x\_1...x\_i): \forall (y\_1...y\_j) \exists (z\_1...z\_k) f(x\_1...x\_i, y\_1...y\_j, z\_1...z\_k)$

I want encode this quantified boolean formula to DIMACS CNF format and use SAT-solver to find such $x\_1...x\_i$ values.

I think its possible by iterating over all $2^j$ $(y\_1...y\_j)$ value substitutions (substitute true or false for every $y$), adding new set of z-arguments for each of them, substitute them to f(...) and joining them with conjunction: $f(x\_1...x\_i, false...false, (z\_1)\_1...(z\_1)\_k) \land f(x\_1...x\_i, false...true, (z\_2)\_1...(z\_2)\_k) \land ... \land f(x\_1...x\_i, true...true, (z\_{2^j})\_1...(z\_{2^j})\_k)$

Problem of that solution that it will generate exponential (dependent on count of y-arguments) large boolean formula with $2^j$ conjunctions and then require exponential time from size of this formula to solve SAT.

Is there a more compact way to reduce this formula to formula without quantifications? Or any other way with less complexity?

# Answer
> 1 votes
When substituted for $(x\_1, ..., x\_i)$ you have a formula in monadic predicate logic.

> The monadic class is the class of first-order formulas without function symbols, with unary (monadic) predicates only, but with arbitrary quantification.

SAT for monadic predicate logic is NEXPTIME-complete in general

> Altogether this means in particular that Monadic-Sat is complete for NEXPTIME.

with a lower bound

> $NTIME(c^{n/\log n})$, for some (other) c \> 0, is at the same time a lower bound for this problem

You'll therefore not be able to find a polynomial time reduction to SAT unless the time complexity hierarchy collapses.

Quotes from L. Bachmair, H. Ganzinger and U. Waldmann, "Set constraints are the monadic class," \[1993\] Proceedings Eighth Annual IEEE Symposium on Logic in Computer Science, 1993, pp. 75-83, doi: 10.1109/LICS.1993.287598.

# Answer
> 1 votes
You can't. You have a QBF-SAT instance. That can't be efficiently resolved/reduced to SAT (given current conjectures in complexity theory). Instead, use a QBF-SAT solver on your formula.

---
Tags: satisfiability, boolean-algebra
---


# Question
Title: Runtime of enumerating all integer vectors with a given sum where every element is greater than sqrt(k)
The problem of enumerating all lists of integers such that the list sums to a known value $k$ is well known and takes exponential time to compute.

If the problem is restricted so that the integers must be greater than $\sqrt{k}$, I feel like the runtime should now be quadratic. Is there a proof of this? More generally, if I restrict the integers to be greater than $l$, how is the runtime affected?

# Answer
The number of sequences of non-negative integers of length $\ell$ summing to $m$ is $\binom{m+\ell-1}{\ell-1}$. This shows that the number of sequences of integers, each at least $t$, summing to $k$ is $$ \sum\_{\ell=1}^{\lfloor k/t \rfloor} \binom{k-\ell t}{\ell - 1}. $$ For example, if $t = \lfloor \sqrt{k}+1 \rfloor$, then we can choose $\ell \approx \sqrt{k}/2$ to get at least $\binom{\Theta(k)}{\Theta(\sqrt{k})}$ many sequences, which is $\exp \Theta(\sqrt{k} \log k)$; this is tight up to the hidden constant.
> 3 votes

---
Tags: enumeration
---


title: A beginner book on algorithms

text:
# Question
Title: A beginner book on algorithms
I am a tenth grader. I currently learnt about sorting algorithms in java in school. I started with the book "Algorithmic Mathematics" so as learn about algorithms mathematically. I know very little calculus(just started limits) and thus, I had difficulty following it knowing that I am not mature enough to read it .Thus, I want a book that is light on calculus and has good theory on algorithms and some discrete math.

# Answer
> 3 votes
A gentle but rigorous introduction would be *Algorithm Design* by Tardos and Kleinberg. It covers all the necessary topics, and discusses the ideas and intuitions behind an algorithm before introducing it. Unlike CLRS, you don't need to "pick and choose" chapters to read as a beginner; instead, you can just follow through the chapters since they are structured in sequential order for a proper course in algorithms.

Should you need additional exercises or a different perspective, I've found the books *Algorithms* by Papadimitriou, Dasgupta, and Vazirani as well as *Algorithm Design and Applications* by Goodrich and Tamassia helpful.

**N.B.:** In most universities, typically an algorithms course (where you learn about topics like greedy algorithms, dynamic programming, graph algorithms, amortized analysis, and NP-completeness, etc.) comes *after* a data structures course (where you learn introductory notions of algorithm analysis, basic data structures such as queues, stacks, BST/balanced BST, and DFS/BFS, etc). The way I see it, the first course is usually not needed, as its contents can easily be baked into the course on algorithm design (i.e. the second course). The textbooks I reference above are the ones typically used for the second course, although they also cover any useful material from the first course, should they be required (notably missing is advanced data structures, e.g. balanced BST).

# Answer
> 2 votes
A (tough) introduction is Jeff Erickson's "Algorithms". It is available as PDF for free.

If you want to learn about how to program (how to put together the above to create useful applications), consider Downey's "Think Python" (be sure to get the second edition, as it is written for Python 3, the current version). Also a free PDF.

Much of algorithms *is* mathematics, just not the standard school/undergraduate fare. Perhaps you'd need to take a peek at some discrete math and something extra, search for William Chen's lecture notes. He wrote a large collection of them, covering from introductory material to somewhat advanced topics.

The above are just my personal favourites, you'd have to find what suits you most. Fortunately this is part of the computing curricula, looking for introductory courses will net you loads of lecture notes, exercises and whatnot.

# Answer
> 2 votes
Although it is not an introduction for beginners, knowledge of the *existence* Knuth's work on fundamental algorithms is important for a beginning Computer Scientist. One day in the future they will need to consult a copy. So for completeness, and for your future as a computer scientist put this on your "wish list":

The Art of Computer Programming, Volumes 1-4A Boxed Set. Third Edition (Reading, Massachusetts: Addison-Wesley, 2011), 3168pp. ISBN 978-0-321-75104-1, 0-321-75104-3

# Answer
> 0 votes
For Visual understanding and practical implementation, you can go with

***1.Algorithms In a Nutshell (O'Reilly)***

For problem-solving and deep diving in concepts, You can check this out

***1.Introduction to the Design and Analysis of Algorithms By Anany Levitin***

---
Tags: reference-request
---


# Question
Title: Why are Regular sets not closed under infinite unions and intersections?
Why are Regular sets not closed under infinite unions and intersections, with my flawled reasoning I came to a conclusion that since infinite unions can have no relationship between strings of a language hence it must be regular but the opposite is infact true, can you please help me understand why so, and under what conditions is generally a language considered regular then (apart from the obvious reasons, a Finite automata can be drawn, regex can be written, a set has to be finite)?

# Answer
Look at $$\ell=\\{a^p\mid p\text{ is prime}\\}.$$

This language obtain from infinite union of $$\bigcup\_{i\geq 2, i\text{ is prime}}^{\infty}L\_i$$ Where each $L\_i=\\{a^i\mid i\text{ is prime}\\}$ that have one word.

Another example is $\\{a^nb^n\mid n\in\mathbb{N}\\}$ That isn't regular and we can describe it by infinite union of regular languages $$\bigcup\_{i\geq 1}^{\infty}a^ib^i=a^1b^1\cup\dots.$$ Each $a^ib^i$ is language that have one word.

For intersection, i recommend you read the following link.
> 7 votes

# Answer
You state: *infinite unions can have no relationship between strings of a language*. Can you explain what you mean by this?

Meanwhile, *every* language is the infinite union of the singleton languages that each contain one element of the language. Clearly, not every language is regular.
> 4 votes

---
Tags: regular-languages, finite-automata, type-theory
---


# Question
Title: Four Queens Problem to a Conjunctive Normal Form
Given a chessboard with 4 rows and 4 columns (4x4)

| 1 | 2 | 3 | 4 |
| --- | --- | --- | --- |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 |

Assign a Boolean variable to each cell of the board as below (1, 2, 3, etc. are variable names) If a variable is True, then there is a queen on the corresponding cell and vice versa. Use CNF clauses to describe constraints to place a queen on cell no. 1

**use -1 to denote NOT 1**

The table below is my CNF answer. I wonder if I did the right thing?. Can you check it for me?. Thanks

| No | CNF |
| --- | --- |
| 1 | 9 ^ -5 ^ -1 ^ -13 ^ -10 ^ -11 ^ -12 ^ -6 ^ -3 ^ -14 |
| 2 | 2 ^ -1 ^ -3 ^ -4 ^ -6 ^ -10 ^ -14 ^ -5 ^ -7 ^ -12 |
| 3 | 15 ^ -13 ^ -14 ^ -16 ^ -11 ^ -7 ^ -3 ^ -12 ^ -10 ^ -5 |
| 4 | 8 ^ -7 ^ -6 ^ -5 ^ -4 ^ -12 ^ -16 ^ -11 ^ -14 ^ -3 |

# Answer
> 1 votes
No, your answer is not correct, and for some reason you have four CNFs (I didn't understand why).

I'll give you some hints, how to reduce the **Four Queens Problem** to a **CNF**. I'll use notation, which is common for boolean variables and expressions. A boolean variable $x\_{i,j}$, where $i,j \in \[1,4\]$, will be used to represent a queen in the cell $(i,j)$.

1. You need to express the first requirement, that each row and each column contains at least one queen, as a boolean expression. This can be done with the aid of the logical OR operation ($\lor$). You need to logically OR all the $x\_{i,j}$ variables separately for each row and each column. For example, this requirement for the *first row* can be expressed as:

$$x\_{1,1} \lor x\_{1,2} \lor x\_{1,3} \lor x\_{1,4}$$

2. Also you need to express the second requirement, that all the queens don't pairwise attack each other. So, for each pair $((i,j),(k,l))$ of cells, such that **a queen at the cell $(i,j)$ can attack the cell $(k,l)$**, their corresponding variables $x\_{i,j}$ and $x\_{k,l}$ can't be both equal to $true$. The boolean expression $(\lnot x\_{i,j} \lor \lnot x\_{k,l})$ guarantees just that. For example, cells $(1,1)$ and $(3,3)$ are on the main diagonal, so the boolean expression below guarantees, that two queens can't be placed simultaneously at these two cells.

$$\lnot x\_{1,1} \lor \lnot x\_{3,3}$$

You can use these two types of clauses to create a CNF, which describes this problem as a CNF satisfiability problem - however, this CNF will be long (84 clauses). That's why (I think) you were asked to write a shorter CNF, which includes only clauses, where the variable $x\_{1,1}$ is present.

---
Tags: boolean-algebra
---


# Question
Title: If in a given text the frequency of the letter A is 0.5, then the number of bits encoding in the Hoffman code for the text is 1
Studying for my finals. I saw the following question:

> Prove or disprove: If in a given text the frequency of the letter A is 0.5, then the number of bits encoding in the Hoffman code for the text is 1.

In the solution they said that this statement is true but didn't explain why. I'm trying to prove this statement for myself but struggling how to "show it". Why it's true?

# Answer
Suppose that no symbol has frequency $0$ (otherwise the claim is false).

Consider the tree $T$ built by the standard greedy algorithm to construct the Huffman code. This algorithm maintains a forest $F$ where each node $v$ is associated with a frequency $f\_v$. Initially $F$ contains a collection of isolated vertices, one per input symbol (with the corresponding frequencies). Then the algorithm greedly selects the two trees $T\_1, T\_2 \in F$ rooted in the vertices with minimum frequencies and replaces them with the tree obtained by merging $T\_1$ and $T\_2$ into a single tree via the addition of new root $r$. The frequency $f\_r$ of $r$ is the sum of the frequencies of the roots of $T\_1$ and $T\_2$.

Let $a$ be the node corresponding to symbol $A$ and suppose towards a contradiction that the depth of $a$ in $T$ is at least $2$. Let $a'$ and $b$ be the parent and the sibling of $a$ in $T$, respectively. Since $a'$ cannot be the root (it has depth $\ge 1$), it must have a sibling $x$. Some vertex $y$ of the subtree of $T$ rooted in $x$ was the root of a tree in $F$ when the isolated vertex $a$ was merged. Therefore the frequency of $y$ is at least the frequency of $a$ (othewise either $a$ or $b$ would have been merged with $y$ instead).

This is a contradiction since $f\_a + f\_b + f\_y \ge 0.5 + f\_b + 0.5 = 1 + f\_b \> 1$.
> 1 votes

---
Tags: algorithms, graphs
---


title: What does an NP reduction look like?

text:
# Question
Title: What does an NP reduction look like?
From my theory of computation lecture I recall:

> If $A \le\_m B$ and $B$ is decidable then $A$ is decidable (uses a computable function as a reduction).

> If $A \le\_p B$ and $B$ is in P then $A$ is in P (uses a polynomial function reduction).

I wanted to know if there is an analogous notion of reduction for the class NP.

# Answer
> 1 votes
Judging from your replies to nir shahar's comments above, it seems that you're really looking for a class of reduction functions that gives a necessary and sufficient condition, rather than merely a sufficient one as your question arguably implies.

If so, then the answer is rather boring: for any problem *B* in NP, a problem *A* is in NP if and only if it is nondeterministic-polynomial-time Turing-reducible to *B*, that is, if and only if there exists a Turing reduction from *A* to *B* that runs in polynomial time on a nondeterministic Turing machine, or (equivalently) that can be verified in polynomial time on a deterministic Turing machine.

I've specified *Turing*-reducible because a *many-one* reduction is not always available: if *B* is trivial (always returns "yes" or always returns "no"), and *A* is not, then there is no many-one reduction from *A* to *B*, regardless of whether *A* is in NP. However, if we require *B* to be non-trivial, then a nondeterministic-polynomial-time many-one reduction *does* have to exist. (Of course, there are other kinds of reductions besides Turing reductions and many-one reductions; but those are the most commonly discussed.)

Likewise, a polynomial-time reduction is not always available unless P = NP, because if *B* runs in polynomial time and *A* does not, then there won't be a polynomial-time reduction from *A* to *B*, regardless of whether *A* is in NP. However, if we require *B* to be NP-complete, then a polynomial-time reduction *does* have to exist, simply because that's the definition of NP-completeness.

---
Tags: complexity-theory, np
---


# Question
Title: Lower bound on worst-case time complexity of all sorting algorithms neglecting reading input and accessing elements time
We know that the worst-case time complexity of any comparison sorting algorithm is $\Omega(n\log n)$. Is there a lower bound on the worst-case running time of sorting algorithms of any type? Not just comparison-based? I.e, a lower bound on the sorting problem.

# Answer
> 2 votes
Suppose the input size is $n$. The lower bound of any algorithm (such as comparison based or non-comparison based) that solve the Sorting problem is $$\Omega(n)$$ **because we need read the input at least once**.

---
Tags: time-complexity, sorting, lower-bounds
---


# Question
Title: Would samples be considered data redundancy if they are similar to each other fairly naturally?
I am working on building ML/DL solution for a problem where that data is considered, naturally similar and I am worried if that would be considered as data redundancy.

My question is, is that so? and if yes what can I do about this then, since this is a feature of the actual real data?

# Answer
Im no expert, but if this is a feature of real data then you shouldn't really worry.

If you want to do something about this, then maybe try to use some dimension reduction techniques, such as PCA (principle component analysis) which is known to reduce redundancy in the data if used correctly.
> 1 votes

---
Tags: machine-learning, data-mining
---


# Question
Title: Counting substrings of a string that do not contain a given string
Let's say we have a string $s\[0..n-1\]$ and a pattern $p\[0..m-1\]$ with $m \< n$. I am looking for an $O(nm)$ solution to the following problem: find the number of substrings of $s$ not containing $p$ as a substring. Can you please help?

# Answer
> 1 votes
You can do this using dynamic programming.

Define $C(i)$ where $i$ ranges from $0$ to $n$:

$$C(0) = (1, 0)$$

$$ C(i) = \begin{cases} (C\_1(i - 1), 0) & \text{if $p = s\[i - 1 - m ... i - 1\]$} \\ (C\_1(i-1) + C\_2(i-1) + 1, C\_2(i-1) + 1) & \text{otherwise} \end{cases} $$

Then $C\_1(n)$ contains the answer.

The idea is that $C\_1(i)$ denotes the number of found substrings after considering the first $i$ characters and $C\_2(i)$ the length of the longest substring ending at $i - 1$ uninterrupted by $p$.

If $p$ ends at $i - 1$, then we cannot add to the number of substrings (because now the substring would contain $p$) and also we must reset the length of the current longest substring to 0.

Otherwise we can increment the length of the current longest substring by 1. Also we add that length to total substring count. In general, summing from $1 + ... + l$ gives all possible substrings of a string of length $l$. Note that this way we therefore sum all possible substrings of all substrings of $s$ not containing $p$.

Computing $C(i)$ takes $O(m)$ if $C(i - 1)$ has already been computed. We compute $C$ from $0$ to $n$, which yields a run-time of $O(nm)$.

---
Tags: strings, substrings, string-matching
---


# Question
Title: Determine if for given some $L$, $S_L={L(M) : <M>\in L}$ then for any $L$, if $S_L=RE$ then $L\in R$ is True or False and explain
> Determine if for given some $L$, $S\_L=\\{\ L(M) | \<M\>\in L \\}$ then for any $L$, if $S\_L=RE$ then $L\in R$. Correct or Incorrect and explain why.

I think the claim is incorrect, and I'm trying to explain it with cardinals. I know that for each language we have $\aleph0$ turing machines and $|RE|$ is also $\aleph0$ but I know that is countable, actually, I don't know how to make the connection if $S\_L=RE$ then is somehow is not counable.

Edit: I am looking to solve it with cardinals.

# Answer
> 2 votes
The statement is incorrect\*. Consider that

$$ RE = \\{L(M) \mid M \text{ is a turing machine} \\} $$

Thus

$$\\{ \langle M \rangle \mid M \text{ is a turing machine}\\} \subseteq L \implies S\_L =\\{\ L(M) \mid \langle M \rangle \in L \\} = RE$$

Therefore if I set

$$L = \\{ \langle M \rangle \mid M \text{ is a turing machine}\\} \cup \\{ \\#\langle M \rangle \mid M \text{ is a TM that always halts}\\}$$

where # is some character that does not occur in turing machine encodings, we have $S\_L = RE$ but $L \not\in R$ as the halting problem could be reduced to it.

<sup>* when assuming that $M$ in $S\_L$ ranges over all turing machines. Otherwise the statement is ambiguous.</sup>

---
Tags: complexity-theory, turing-machines, computability, counting
---


# Question
Title: PetersonNP, mechanical mutual exclusion proof
Good day everyone, I'm currently trying to carry out the PetersonNP (a.k.a. FilterLock) correctness proof (mutual exclusion). I've found several proof sketches on concurrency books but I'm interested in the one shown in `Distributed Algorithms` (by Nancy Lynch). I find it more convincing because lemmata required for proving it are exposed (other authors provide an intuitive approach but I need more details).

The lemma implying mutual exclusion (Assertion 10.5.5) and the three lemmata for proving it (10.5.3.1, 10.5.3.2, 10.5.4) are spelled out on pg. 287.

I want to focus on 10.5.3.\* and 10.5.4 first and consider 10.5.5 only when the others are proved.

I've been able to mechanically prove the first lemma (10.5.3.1). I carry out my proofs by hand employing sequent calculus and once I'm convinced they are correct I check them by PVS. I checked, so I'm confident the first one is correct.

I report the key concepts involved in all three proofs, as they are explained in the book:

$winner(p, c, j) = (c'i\_p\>j) \lor (c'i\_p=j\land c'pc\_p=CS)$

$comp(p, c, j)=\\ winner(p, c, j) \lor (c'i\_p=j\land c'pc\_p\in\\{cf, ct\\}) =\\ (c'i\_p\>j) \lor (c'i\_p=j\land c'pc\_p=CS) \lor (c'i\_p=j\land c'pc\_p\in\\{cf, ct\\})$

**What i tried so far:**

Lemma 10.5.3.1 states: "if process p is a competitor at level j, if $pc\_p=check\text{-}flag$, and if any process $q\neq p$ in $S\_p$ is a competitor at level j, then $turn(j)\neq p$."

I formalized the theorem as follows and proved it correct (the proof is not difficult but it is very long due the plenty many case analyses).

$Lemma10.5.3.1(c)=\forall p,q,j.\big(comp(p, c, j)\land c'pc\_p=cf \land (comp(q, c, j)\land q\neq p\land q\in c'S(p) )\big)\Rightarrow c'turn(j)\neq p$

% PROVED.

**The problem:**

I'm facing difficulties in proving 10.5.3.2 and 10.5.4 because, in first place, I'm not sure about how they should be stated in first-order logic (more details to come).

Lemma **10.5.3.2** states: "if process p is a winner at level k and if any other process is a competitor at level k, then $turn(k)\neq p$."

Up to now i tried:

First formalization attempt: $\forall p,q,j.\big( winner(p, c, j) \land comp(q, c, j) \land p\neq q \big) \Rightarrow c'turn(j)\neq p$

however the inductive hypothesis fails to hold in a few cases and Lemma 10.5.3.1 does not apply, so I suspect it to be incorrect.

I then tried to move the quantificator on q inside:

Second formalization attempt: $\forall p,j .\big( winner(p, c, j) \land \forall q.(comp(q, c, j) \land p\neq q) \big) \Rightarrow c'turn(j)\neq p$

this lemma is provable. It suffices to skolemize $p$ and $j$ and when instantiating $q=p$ the constraint $p\neq q$ becomes unsatisfiable, causing the proof to end. This alternative formalization puzzles me because I don't see how to use the innermost forall when this lemma has to be applied.

As Kay correctly pointed out, my second formalization is incorrect, and as I stated more than one year ago, the correct formalization is the first one.

**UPDATE regarding 10.5.3.2:**

On page 292 (in the context of a different argument) Nancy Lynch points out that Lemma 10.5.3.2 can not be proved by induction, *as it is*. It must be strengthened, but I don't get how to do that.

**UPDATE regarding 10.5.3.2:** The proof can be completed by induction, provided supporting lemmata are identified and employed. No change to the statement is required, neither in words nor in the formal setting.

Eventually, **Lemma 10.5.4** states: "if there is a competitor at level j, then the value of the turn(j) is the index of some competitor at level j."

I tried the following formalization:

$\forall p,q,j.comp(p, c, j)\land comp(q, c, j)\Rightarrow(c'turn(j)=p\lor c'turn(j)=q)$

but I get an unprovable case when both processes $p$ and $q$ are stopped, so I suspect this formalization is incorrect.

**UPDATE regarding 10.5.4** The lemma has been proved and the proper formalization has been added in the response.

~~Could someone suggest me the proper formalization? Or how to strengthen the statement of Lemma 10.5.3.2?~~

Thanks in advance,

# Answer
I eventually found the solution for the first problem I proposed. Lemma 10.5.3.2 CAN be proved by induction, but it requires additional lemmata for doing so. I was misled by the note on page 292, specifically by the mention of "strengthening". It is common to say that a theorem is strengthened when its inductive hypothesis is rewritten to hold in every case of interest, still, there's no standard nomenclature. There's no need to rewrite Lemma 10.5.3.2 it suffices to notice that in those seemingly unprovable cases the role of process Q only leads to contradictions.

Observing that Q must be in a contradictory situation is not immediate, it takes several suppositions that together with more lemmata cause the proof to terminate.

Some lemmata are quite obvious, namely, $level\_p=i\_p \lor level\_p=i\_p-1$. Others are not immediate to prove, like $\vert S\_p\vert=n-1 \Rightarrow Q=qq\_p$ where $qq\_p$ is the process observed by $p$. The core point is the following, finding supporting invariants is fairly easy when one knows they are necessary and sufficient.

Currently, Lemma 10.5.3.2 is proved.

**UPDATE regarding 10.5.4:**

Lemma 10.5.4 is proved. The proof again is not difficult, it requires the human prover to observe that a victim qualifying as a competitor only leads to contradictions. To do so, one has to use lemmata 10.5.3.1 and 10.5.3.2 in a single case where the inductive hypothesis ceases to work.

The formal statement is possibly the simplest among the three lemmata used to support mutual exclusion.

$\forall j. \exists p . comp(p, c, j) \Rightarrow comp(turn(j), c, j)$
> 1 votes

---
Tags: algorithms, correctness-proof, concurrency, first-order-logic, mutual-exclusion
---


# Question
Title: Is there a difference between extremely slow growing functions and constants with respect to computable functions?
So let's say we have the function $f(n)$ that gives $k$ such that $k$ is the smallest number that gives a busy beaver function $B$ value from input $k$ that is greater than $n$. Or more succinctly the smallest $k$ with $B(k) \> n$. Can there be computable functions that are not in time complexity class $O(n^c)$ for some constant $c$ but that are in $O(n^{f(n)})$. And by extension, is it true that $P = O(n^{f(n)})$?

# Answer
> 1 votes
Your definition of $f$ is $$ f(n) \> k \Longleftrightarrow B(k) \leq n. $$ Now suppose that $M$ is a Turing machine that runs in time $C n^{f(n)}$ but not in polynomial time. Since $M$ does not run in polynomial time, for every $k$ we can find $n$ such that its running time for some input of length $n$ is more than $C n^k$; this can be done effectively, by going over all strings. Having found such $n$, we can conclude that $Cn^k \< Cn^{f(n)}$ and so $f(n) \> k$, implying that $B(k) \leq n$. Since we can compute such $n$ for every $k$, this allows us solve the halting problem, showing that no such machine $M$ can exist.

As for your second question, if $g(n) \to \infty$ then every polytime machine trivially runs in time $O(n^{g(n)})$. Indeed, if the machine runs in time $Cn^C$ then since $g(n) \to \infty$, we have $g(n) \geq C$ for large $n$, and so $Cn^C = O(n^{g(n)})$. This shows that every language in $\mathsf{P}$ also lies in $\mathsf{TIME}(O(n^{f(n)})) = \bigcup\_{C \in \mathbb{N}} \mathsf{TIME}(Cn^{f(n)})$ (often we use $\mathsf{TIME}(n^{f(n)})$ to denote this class). As we have seen above, the converse also holds, and so $\mathsf{P} = \mathsf{TIME}(O(n^{f(n)}))$.

---
Tags: complexity-theory, polynomial-time, busy-beaver
---


title: $\text{DSPACE}(O(1))=\text{REG}$ Proof?

text:
# Question
Title: $\text{DSPACE}(O(1))=\text{REG}$ Proof?
I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and know that the idea is to encode the finite possibilities of memory as finite states, and also have read https://cs.stackexchange.com/a/57938/112750 . However, I still have a question that I'm unable to answer. A finite automaton needs to read the characters one by one and never look back, but a TM, though restricted to use only $O(1)$ memory, may choose to go back and forth on its input tape. How can I eliminate this kind of looking back problem and construct an automaton that is equivalent to this TM?

# Answer
There are several ways of showing this, but really there is only one core argument that needs to be understood, and that is the proof that 2-way DFAs are equivalent to DFAs.

A 2-way DFA (https://en.wikipedia.org/wiki/Two-way\_finite\_automaton) can go back and forth on its input tape, so it does not have to read the word from left to right. There are several beautiful proofs showing the equivalence of this model to standard DFAs. The basic idea is to use the notion of *crossing sequences*. You can easily find the proof online, so I'm omitting it from this answer.

Once you have this result, it's enough to show that $DSPACE(O(1))$ can be captured by a 2-way DFA. This is quite straightforward: a $DSPACE(O(1))$ TM has a read-only input tape, and a bounded size work tape. By replacing the bounded work tape with finitely many states (each capturing the entire contents of the work tape, as well as the location of the head and the state of the machine), you obtain an equivalent 2-way DFA, and you're done.

Another way of going about this, is to use the fact that with $O(1)$ space on the work tape, a halting TM can only work for $O(n)$ time, since the number of configuration basically boils down to the location of the reading head. Thus, $DSPACE(O(1))\subseteq TIME(O(n))$, and since $TIME(o(n\log n))=REG$, you obtain the result. The proof of the latter containment also makes use of crossing sequences, so it's fundamentally the same argument.
> 4 votes

---
Tags: regular-languages, finite-automata, space-complexity, complexity-classes
---


# Question
Title: Padding in proof of space hierarchy theorems
Referring to the Wikipedia proof :

Wikipedia proves the space hierarchy theorem using the following language: $$ L = \\{ (\langle M \rangle, 10^k) : \text{$M$ does not accept $(\langle M \rangle, 10^k)$ using space $f(|(\langle M \rangle, 10^k)|)$} \\}. $$

Why do we need the padding with $10^k$? How does it help us in the proof, and where does it fail if we do not consider it?

I assume that the same reasoning would be valid also for the nondeterministic version.

# Answer
Suppose that we consider instead the language $$ L = \\{ \langle M \rangle : \text{$M$ does not accept $\langle M \rangle$ in space $f(\langle M \rangle)$} \\}. $$ We want to show that $L \notin \mathsf{SPACE}(o(f(n))$, that is, that if $M$ uses space $o(f(n))$ then $L(M) \neq L$. This should be the case since $$\langle M \rangle \in L \Leftrightarrow \langle M \rangle \notin L(M).$$ But is this really true? According to the definition of $L$, $\langle M \rangle \in L$ iff $M$ does not accept $\langle M \rangle$ *in space $f(\langle M \rangle)$*. It could be that $\langle M \rangle \in L$ and $M$ accepts $\langle M \rangle$ *using more than $f(\langle M \rangle)$ space*. The latter could actually happen, since we are only guaranteed that $M$ uses space $g(n)$ for some function $g(n) = o(f(n))$, which does not preclude $g(|\langle M \rangle|) \> f(|\langle M \rangle|)$ at the *particular* value $|\langle M \rangle|$.

Adding the padding fixes this issue: it cannot be that $g(|(\langle M \rangle, 10^k)|) \> f(|(\langle M \rangle, 10^k)|)$ for all $k$, since this would contradict $g(n) = o(f(n))$.
> 3 votes

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?
I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are the lengths of the input strings a and b, respectively.

From my understanding, the worst case scenario is that each column in the addition will result in a carry, and since there are max(N, M) columns, the time complexity should be O(max(N, M))?

# Answer
If $m,n\>=0$, then $\max(m,n)\<=m+n\<=2\max(m,n)$.

So $O(\max (m,n))$ and $O(m+n)$ are the same; the two expressions are within a constant factor of each other.
> 1 votes

# Answer
Note that, when we compute binary addition of two binary strings $|A|=n,|B|=m$, we read $n+m$ bits. On the other hand the time complexity of computing the addition of two bits, are $\mathcal{O}(1)$, so we do $n+m$ additions that each of them needs $\mathcal{O}(1)$ time. As a result, the time complexity is $$\mathcal{O}(n+m).$$

**Remember that, $A+B$ need at most $\max\\{m,n\\}+1$ bits space.**
> 3 votes

---
Tags: algorithms, algorithm-analysis, arithmetic, binary, bit-manipulation
---


# Question
Title: Time complexity of an algorithm: Is it important to state the base of the logarithm?
Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = \Omega(\log{n})$, as opposed to $\Omega(\log\_2{n})$, or whatever the base might be?

# Answer
It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $\theta$ allows you to multiply by any constant.

If you take $O(2^{\log n})$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^{0.3010})$.
> 68 votes

# Answer
Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $\log\_a n = \Theta(\log\_b n)$ for all $a,b \> 1$. So there is no need to specify the base of a logarithm when using asymptotic notation.
> 50 votes

# Answer
As $\log\_xy = \frac{1}{\log\_y{x}}$ and $\log\_x{y} = \frac{\log\_z{y}}{\log\_z{x}}$, so $\frac{\log\_a{n}}{\log\_b{n}} = \frac{\log\_n{b}}{\log\_n{a}} = \log\_a{b}$. As $\log\_a{b}$ is positive constant (for all $a,b \> 1$), so $\log\_a{n} = \Theta(\log\_b{n})$.
> 15 votes

# Answer
In most cases, it's safe to drop the base of the logarithm because, as other answers have pointed out, the change-of-basis formula for logarithms means that all logarithms are constant multiples of one another.

There are some cases where this isn't safe to do. For example, @gnasher729 has pointed out that if you have a logarithm in an exponent, then the logarithmic base is indeed significant.

I wanted to point out another case where the base of the logarithm is significant, and that's cases where the base of the logarithm depends directly on a parameter specified as input to the problem. For example, the radix sort algorithm works by writing out numbers in some base $b$, decomposing the input numbers into their base-$b$ digits, then using counting sort to sort those numbers one digit at a time. The work done per round is then $\Theta(n + b)$ and there are roughly $\log\_b U$ rounds (where $U$ is the maximum input integer), so the total runtime is $O((n + b) \log\_b U)$. For any fixed integer $b$ this simplifies to $O(n \log U)$. However, what happens if $b$ isn't a constant? A clever technique is to pick $b = n$, in which case the runtime simplifies to $O(n + \log\_n U)$. Since $\log\_n U$ = $\frac{\log U}{\log n}$, the overall expression simplifies to $O(\frac{n \log U}{\log n})$. Notice that, in this case, the base of the logarithm is indeed significant because it isn't a constant with respect to the input size. There are other algorithms that have similar runtimes (an old analysis of disjoint-set forests ended up with a term of $\log\_{m/2 + 2}$ somewhere, for example), in which case dropping the log base would interfere with the runtime analysis.

Another case in which the log base matters is one in which there's some externally-tunable parameter to the algorithm that control the logarithmic base. A great example of this is the B-tree, which requires some external parameter $b$. The height of a B-tree of order $b$ is $\Theta(\log\_b n)$, where the base of the logarithm is significant in that $b$ is not a constant.

To summarize, in the case where you have a logarithm with a constant base, you can usually (subject to exceptions like what @gnasher729 has pointed out) drop the base of the logarithm. But when the base of the logarithm depends on some parameter to the algorithm, it's usually not safe to do so.
> 10 votes

# Answer
Let $f\_k(n)=\log\_kn$,$k\>2$, and let $t(n)=\log\_2n$.

You can rewrite $f\_k(n)$ as follow $$f\_k(n)=\frac{\log\_2n}{\log\_2k}$$ Now $k$ have two states:

1. $k$ is constant:

$$\lim\_{n\to \infty}\frac{f\_k(n)}{t(n)}=\lim\_{n\to \infty}\frac{\frac{\log\_2n}{\log\_2k}}{\log\_2n}=c$$ that $c$ is a constant$\>0$, hence $$t(n)=\Theta(f\_k(n)).$$ So there is no difference between $f\_k(n)$ , and $t(n)$ in terms of asymptotic notation.

2. $k$ isn't constant:

$$\lim\_{n\to \infty}\frac{f\_k(n)}{t(n)}=\lim\_{n\to \infty}\frac{\frac{\log\_2n}{\log\_2k}}{\log\_2n}=0$$

So $t(n)$ have faster growth rate and $$t(n)=\omega(f\_k(n)).$$
> 0 votes

---
Tags: algorithms, time-complexity
---


title: Pattern finding in an array of numbers

text:
# Question
Title: Pattern finding in an array of numbers
I have an array of numbers, and I need to check if there is a repeating pattern in the array. Like, for example, if I have an array A=\[1,1,6,1,1,6,1,1,6,1,1,6...\] this should return "Yes" (pattern present), 3 (for length of the pattern) or "1,1,6" (the pattern).

In contrast, if I have this array A=\[1,1,6,1,1,6,1,2,3..\], this should return "No" (because no pattern is found) or 0 (for length of longest pattern).

Does there exist an algorithm for it, that works preferably in O(nlog(n)) or O(n) time?

PS: I would like to decrible the original problem in case there is a method to solve it that hasn't occured to me yet. The original problem asks to find the length of the continued fraction sequence of an irrational number. For example, for $\sqrt{2} =\[1;(2)\]$

# Answer
> 2 votes
Your problem statement is unclear, but under reasonable assumptions:

No. You can't. If the input is an infinite sequence, you can't solve it in any finite time. To put it another way, suppose you have an algorithm that terminates after some fixed amount of time. Now consider feeding in the input \[5,5,5,5,..\] to the algorithm. Presumably, you want it to output that the input repeats "Yes, a pattern of length 1 exists". Now consider the same input, except that the billionth digit has been changed to a 7. Now, presumably you want the algorithm to output "No". Yet an algorithm that takes fewer than one billion steps of computation cannot tell the difference between those two inputs, so such an algorithm will produce the wrong output on at least one of these two inputs. You can make a similar argument that any finite algorithm will do the wrong thing on some input.

---

Alternatively: if we accept a different definition of what we mean by a "pattern", the problem is solvable efficiently. Suppose that what we mean is that we have an infinite stream of numbers and we can look as far as we like into it; and if there is any repeating sequence of period longer than one that occurs two or more times, then we are permitted to exit and output "Yes" with that sequence.

In this case, there is an efficient algorithm. Floyd's algorithm runs in $O(n)$ time and $O(1)$ space, and can be adapted to this problem. Floyd's algorithm will output a bunch of candidates for possible patterns (a candidate for the start of the repeating pattern and its length), and then you need an efficient way to check them. Fortunately, that check can be done efficiently with a rolling hash.

Unfortunately this problem statement is not consistent with your examples, as under this problem statement, when running the algorithm on any infinite stream that begins with \[1,1,6,1,1,6,...\], the algorithm is allowed to output "Yes".

---

Finally, I will answer your actual problem about continued fractions, which is a different problem. The answer to that question is yes, given $n$, you can find whether there exists a continued fraction expansion for $\sqrt{n}$ that is periodic, and find the period. Using standard algorithms for continued fractions, you can compute the numbers in the continued fraction, one at a time, so we obtain a way to iterate through the infinite stream. Now the above algorithm gives us candidates for the pattern.

All that we need is a way to verify a candidate pattern. Suppose we hypothesize that $\sqrt{n} = \[a\_0;a\_1,a\_2,\dots,a\_{k-1},a\_0,a\_1,a\_2,\dots\]$, i.e., we hypothesize the continued fraction has $a\_0,a\_1,\dots,a\_{k-1}$ repeating infinitely. This amounts to a hypothesis that

$$\sqrt{n} = a\_0 + {1 \over a\_1 + {1 \over \ddots + \sqrt{n}}}.$$

We can efficiently check this hypothesis. Note that the right-hand expression can be simplified to something of the form ${b \sqrt{n} + c \over d \sqrt{n} + e}$ by straightforward arithmetic, e.g.,

$$a\_{k-1} + {1 \over \sqrt{n}} = {a\_{k-1} \sqrt{n} + 1 \over \sqrt{n}},$$ $$a\_{k-2} + {1 \over a\_{k-1} + {1 \over \sqrt{n}}} = {(a\_{k-1} a\_{k-2}+1) \sqrt{n} + a\_{k-2} \over a\_{k-1} \sqrt{n} + 1},$$

etc. Finally, we can check the hypothesis that

$$\sqrt{n} = {b \sqrt{n} + c \over d \sqrt{n} + e}$$

by cross-multiplication, i.e., we check that

$$dn + e \sqrt{n} = b \sqrt{n} + c,$$

i.e., that $dn=c$ and $e=b$. Of course, it is known that the solutions of quadratic solutions all have periodic continued fractions, and vice versa, so this completely characterizes the situation.

---
Tags: algorithms, continuations
---


# Question
Title: Sorting an array with x sorted subarrays
I have been given two True/False questions regarding sorting an array. The questions are as following -

Question A

> Given an array A with 3n keys that contains three equal parts A\[1,n\], A\[n+1,2n\] and A\[2n+1,3n\], each with n keys. Each part is sorted. Is possible to sort the keys of A into a new array B in O(n) steps (worst case)?

Question B

> Given an array A with 10n keys that are comparable using a binary function that returns which element is bigger or if the elements are equal. The array is split into n equal parts, each with 10 keys. Each part is sorted. Is it possible to sort the keys of A into a new array B in O(n) steps (worst case)?

The solution to question A is that we can use merge() fucntion from MergeSort to sort the array.

The solution to question B is that it is not possible, as it violates the Ω(nlog(n)) lower bound for comparison based sorting algorithms

And I fail to see the difference between the two questions.. Is it because in question B we first need to apply the function? Why does it prohibits us from using merge() aswell? I don't see the logic behind the assumption that the two scenarios are different and I feel that I'm missing something important.

# Answer
> 4 votes
In the first exercise you have to merge a constant number of subarrays, i.e., $3$.

In the second exercise you'd have to merge $\Theta(n)$ subarrays, each of constant size. If you were able to produce a sorted version of the union of these subarray in time $O(n)$ using a comparison-based algorithm then you'd also have a comparison-based algorithm for the general sorting problem: Given a sequence of elements simply create $10$ copies of each element and sort the resulting sequence. Then drop the copies from the returned output.

Nothing prohibits you from also using merge() in the second case. It's just that you'd need to perform $\Omega(n)$ merges and the overall times spent will be $\Omega(n \log n)$. Consider for simplicity $n = 10 \cdot 2^k$. Even if you do the merges in a clever order (i.e., in a binary-tree fashion) you'd still need:

$$ \Omega\left( \sum\_{i=0}^{k-1} 2^{k-i} \cdot (2 \cdot 10 \cdot 2^i - 1)\right) = \Omega\left(\sum\_{i=0}^{k-1} 2^k\right) = \Omega(k2^k) = \Omega(n \log n) $$ comparisons.

# Answer
> 1 votes
**Question A**

ِYes just merge them in $\mathcal{O}(n)$.

**Question B**

Your problem reduced to merge $k$ sorted lists with $n$ elements, that can be done that in your problem can be done in $\mathcal{O}(n\log n)$.

Note that we can't do better than $\Omega(n\log n)$ because according to decision tree, number of leaves: $$\frac{n!}{(10!)^n}$$ So the height of the decision tree is $$\log\left(\frac{n!}{(10!)^n}\right)=\Omega(n\log n).$$

---
Tags: sorting, comparison, mergesort
---


# Question
Title: Largest sum of a contiguous subarray using queries of the same form
We are given an array $A\[1..n\]$. We don't have direct access to $A$, but we can query what is the sum of $A\[i..j\]$ for every interval $i..j$. We would like to find the maximum of $A\[i..j\]$ over all intervals $i..j$. How can we prove that we must make $\Omega(n\log n)$ queries?

My thought is that we can solve the problem in $O(n\log n)$ using divide and conquer. Roughly speaking, for any $1\leq i\leq j\leq n$ we can recurse on $i\dots\frac{j}{2}$, and $\frac{j}{2}+1\dots j$, return the maximum of one of the two halves or the sum of the two halves, resulting in a running time of $O(n)$. I don't think that my idea works, and I don't know why there should be at least $\Omega(n \log n)$ many queries. Any help would be appreciated.

# Answer
> 2 votes
You can solve your problem with $O(n)$ queries.

Let $Q(i,j)$ denote the result of a query on $A\[i,j\]$. This upper bound on the number of queries is trivial since you can always reconstruct $A$ with $n$ queries $Q(i,i)$ for $i=1,\dots,n$ and then solve your problem on $A$ with any algorithm (regardless of its running time).

The following greedy algorithm additionally shows that $O(n)$ time (and hence queries) suffices.

* $i \gets 1$.
* Store $(1,1)$ as a candidate solution
* For $j=2,\dots,n$:

+ If $Q(i,j) \le Q(j,j)$ then $i \gets j$.
    + Store $(i,j)$ as a candidate solution
* Return the candidate solution $(i,j)$ that maximizes $Q(i,j)$.

We now prove that the algorithm must be correct. I'm assuming that we cannot return an empty subarray (if this is not the case, it is easy to modify the algorithm and the proof). It suffices to show that an optimal solution must belong to the set of the candidate solutions.

Immediately before the first iteration of the for loop $A\[1,1\]$ is the (unique) maximum-sum contiguous subarrays of $A$ ending with index $1$. We now show by induction that when an iteration of the for loop is completed, we have that $A\[i,j\]$ is the maximum-sum contiguous subarrays of $A$ ending with index $j$ and maximizing $i$.

Let $(i',j)$ denote the maximum-sum contiguous subarrays of $A$ ending with index $j$ and maximizing $i'$. We will show that, at the end of the iteration, we must have $i=i'$. Either $i'=j$ or $i'\<j$. If $i'=j$ then we necessarily have $Q(h,j) \le Q(j,j)$ for all $h=1,\dots,i-1$. This means that the "if" condition is satisfied and the algorithm sets $i$ to $j=i'$. Otherwise $i'\<j$ and hence $A(i', j-1)$ is the maximum-sum contiguous subarrays of $A$ ending with index $j-1$ and maximizing $i'$ (otherwise a cut-and-paste argument yields a contradiction), showing that when the "if" statement is evaluated we have $i=i'$. Moreover $i'\<j$ implies that $Q(i',j) \< Q(j,j)$ showing that the condition of the "if" statement is not satisfied and $i$ is left unchanged in the considered iteration.

The correctness of the algorithm follows since there is necessarily some optimal soltion $A\[i,j\]$ such that $Q(h,j) \< Q(i,j)$ for all $h=i+1, \dots, j$.

---
Tags: algorithms
---


# Question
Title: Observations about the structure of an optimal Binary Search Tree
My question is about part 15.5 in CLRS (third edition)<sup>*</sup>, on optimal binary search trees. I am confused about the following sentences:

> Consider any subtree of a binary search tree. It must contain keys in a contiguous range $k\_i, …, k\_j$ for some $1 \leq i \leq j \leq n$. In addition, a subtree that contains keys $k\_i, …, k\_j$ must also have as its leaves the dummy keys $d\_{i-1}, … d\_j$.

(where $(k\_j)\_{j \in {\[1,\ …,\ n\]}}$ is a sorted sequence containing the keys of the nodes in the BST).

The chapter does not include proof of this statement, which does not seem obvious to me at all.

Moreover, I do not understand why the tree (key: $d\_0$, right child: (key: $k\_1$, right child: $d\_1$)) — where $d\_0$ is the dummy node corresponding to values strictly less than $k\_1$ and $d\_1$ is the dummy node corresponding to values strictly greater than $k\_1$ — is not a satisfactory counterexample. It satisfies the BST property ($d\_0 \< k\_1 \< d\_1$) and $k\_1$ is not an ancestor of $d\_0$.

---

* Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein

# Answer
Let us prove by induction on depth that for every node $v$, there exist $a\_v,b\_v$ (possibly $\pm \infty$) such that the input $x$ reaches $v$ iff $a\_v \< x \< b\_v$. This is true for the root since we can take $a\_r = -\infty$ and $b\_r = +\infty$. Now suppose that it is true for some node $v$, and let $v\_\<,v\_\>$ be its two children. Suppose that node $v$ compares $x$ to $c\_v$. Then $x$ reaches $v\_\<$ if $a\_v \< x \< c\_v$ and $v\_\>$ if $c\_v \< x \< b\_v$ (I'm not sure what happens when $x = c\_v$ — that depends on the exact definition of BST). This implies your stated property.

Your example has three nodes. The first contains the values $d\_0,k\_1,d\_1$, the second contains the values $k\_1,d\_1$, the third contains the value $d\_1$. All of these are contiguous ranges (which is a more concise way to state the property in your post).
> 3 votes

---
Tags: data-structures, trees, binary-trees, binary-search-trees
---


# Question
Title: Prove correctness of a solution to the critical section problem in general?
I was wondering if there is any formal, general way to prove the correctness of a candidate solution to the critical section problem in synchronization. For example, in the image enclosed, I have considered the Petersons solution to the critical section problem(reference: operating system concepts by Gagne)  The example is worked out for all possible scenarios of concurrent execution and an observation is made that in any scenario, at most one process enters inside the critical section, hence proving the mutual exclusion condition of the solution.
**Doubt**
Is there a better way to formally prove the above condition(and other conditions, such as bounded waiting and progress)? I wondered because the method I used above is really a brute force method and things can get pretty messy as the number of instructions increases.

# Answer
What you pointed out is a possible approach to the problem that is basically a model checking one. Check all possible combinations and observe mutual exclusion is invalidated in case 2 or more processes are in CS. Since Peterson2P satisfies ME no counterexample is ever encountered.

To prove properties like mutual exclusion, deadlock freedom, starvation freedom and FIFO access there's, in general, no standard easy way.

My answer is somewhat more sophisticated than what you might want to hear... The approach used for proving the property is important, if you are happy with a pencil-paper proof like the one you did things are going to unravel smoothly. Instead, if you wish to obtain a stronger mechanical proof you need to employ some formalism (sequent calculus or natural deduction) and as such you need to be able to encode the algorithm and correctness conditions. This is definitely an overkill unless you are deeply involved with the topic of mechanical verification.

When proving that some concurrent algorithm satisfies a property, the quickest (not simplest or most efficacious) way is by contradiction. A direct proof obviously will show the property holds and will give a deeper understanding of the causes that make it work. Instead, a model checking (brute force) approach will just tell you if the property holds or not, without shedding any light about its motivations.

To answer your first question, Peterson2P can be proved correct by direct proof employing a bunch of lemmata, namely, properties that capture the behaviour of the algorithm showing that no transition ever invalidates the desired property.

Lemma1: any process $p$ has its $flag\_p=true \iff ($ line 1 has been executed and $flag\_p=false$ has still to be executed $)$.

Lemma2: let process $p$ be waiting on while () ... and let process $q$ be in CS, then $turn=p$.

By Lemma1 and Lemma2 you can prove Lemma3:

Lemma3: let $p$ and $q$ be in CS, then $p = q$.

Or equivalently:

Lemma3-bis: let $p$ and $q$ be in CS and $p\neq q$, then $false$.

Lemma3-ter: it is never true that $p$ and $q$ in CS and $p\neq q$.

The proof is quite simple because you simply apply Lemma1 and Lemma2 twice. Suppose $p$ and $q$ are in CS and their $flag=true$ then $turn\neq p \land turn\neq q$ but that's absurd. QED.

I think this solution is better w.r.t. the brute force one because it explains (when you understand the proof) why the algorithm works but I acknowledge that finding and proving supporting lemmata is not easy or intuitive, especially in the beginning. Each lemma encodes a property giving the whole process a structure that is completely lacking in the approach you employed.

Devising correctness proofs for concurrent algorithms is remarkably hard and each algorithm exploits different strategies for granting several properties... Therefore proving them correct will require several adequate techniques.

Deadlock freedom is proved correct showing that there's always some next step to take. Namely, if the algorithm is running (not suspended) there's some next line of code that CAN be run. This kind of proof is not difficult but is extremely long and tedious due to plenty many cases analyses you have to unravel. Also notice that a contradiction proof could backfire, since there could be more cases to check w.r.t. a direct proof having its supporting lemmata.

Liveness properties like starvation freedom instead are proved through the employment of temporal logics or by implication observing several properties that together imply the lack of starvation. For instance bounded-bypass. As I mentioned before each proof has its peculiarities and sketching a general strategy for everything is very difficult.
> 1 votes

---
Tags: operating-systems, concurrency, synchronization
---


# Question
Title: Books about data structures and algorithms but specifically focusing on parallel gpgpu programming
I'm looking for a book on the subject of algorithms and data structures, but I want to specifically learn about the parallel implementations. Books that teach CUDA and OpenCL usually have small sections that briefly touch on this subject, but they are mostly focused on technicalities. I'm looking for something more fundamental and theoretical.

I hope to later apply those techniques to problems in scientific computing, computational physics and simulations. If the book touches on those subjects, that's even better, but not strictly necessary.

# Answer
> 1 votes
I think you need to look at the HPC (High-Performance Computing) - because scientific computing requires so vast amount of resources now, that it'll be impossible to stay on the edge without access to really large machines.

However I don't think you'll find a comprehensive and refined description of algorithms and data structures, used in the HPC. It'll be easy to find some books about HPC, using this or similar keywords. Two books look promising to me - this introductory book and this book, mostly focused on GPGPU.

If you want to read something more theoretical, then probably it'll make sense to read scientific papers, for example ones from this collection. You'll easily find many HPC conferences as well, which usually happen every year, for example the SC'21 (November of this year).

# Answer
> 1 votes
For GPGPU focussed parallel programming I recommend

> David B Kirk; Wen-mei W Hwu: *Programming Massively Parallel Processors: A Hands-on Approach, 3/e*, Morgan Kaufmann, 2016.

The examples are all CUDA based, but the algorithmic/data-structure ideas are all aimed at a much broader audience.

Disclaimer: Wen-mei Hwu and I were colleagues at University of Illinois, so I'm biased.

---
Tags: parallel-computing, books
---


# Question
Title: How does the TEPS benchmark work and why is it relevant to real world problems?
Graph500 is a competition for supercomputers that uses a different benchmark "Traversed Edges Per Second", which is supposed to measure some notion of the communication bandwidth ability of the computer.

However, I don't understand how this benchmark works since there doesn't seem to be a basic explanation on the site. **At a basic level, how does TEPS work, and why?**

# Answer
> 2 votes
### Benchmark Motivation

The benchmark measures the performance of some very simple graph traversal algorithms on very large graphs. These algorithms need to be executed in parallel in order to take advantage of the supercomputers' parallel computation architecture.

The benchmark's algorithms themselves do not attempt to completely solve any practical problem, but they are typical of code which will form part of such solutions. The techniques used by benchmark writers to speed up their benchmarks will therefore also be of use in speeding up solutions to real-world problems.

### Graph traversal as a supercomputer problem

Graph traversal problems, by their nature, are tricky to efficiently compute in parallel. A typical solution involves creating some kind of fringe (or work-list) of already-processed nodes and to follow each edge from each node in that fringe in some order to identify not-yet-processed nodes and add them to the fringe for later processing.

The order in which the fringe is traversed is important, and varies from algorithm to algorithm. But doing any traversal algorithm in parallel presents coordination issues.

Since the underlying data structure is a graph, not a tree, there will be multiple paths to any given node. Edges in the fringe will often connect back to nodes already processed, and these nodes must not be processed again; otherwise, the traverse will never terminate. In an undirected graph, edges can be followed from either end, so it's guaranteed that every node in the fringe will be in an edge which connects back to a previously processed node: the edge that was used to add the node to the fringe. (An edge which points back to a previously traversed node is called a *back link*.)

In addition, it's very likely that multiple nodes in the current fringe connect to the same as-yet-unprocessed node. This new node has not yet been processed, but it must only be added to the fringe once. (These edges are called *cross links*.) The graphs in the TEPS benchmarks have not been cleaned, so it's also possible for two nodes to be connected with more than one edge, or even for an edge to connect a node to itself.

So the algorithm needs to maintain information, at least a single bit but typically a bit more, which allows the processing loop to decide whether to add the node to the fringe.

At a high level, the traverse can be done in parallel by dividing the nodes in the fringe between different processing threads executing on different cores or processors. But it's not trivial for memory to be accessed at the same time by multiple processors. There must be some type of communications channel which the data flows through, and it's not practical to connect every bank of memory to every processor. Typically, each processor (or small group of processors) will be directly connected to a high-speed associative cache which contains a copy of recently referenced memory regions; these various caches need to be synchronised with each other (in the case that two processors are consulting the same datum) and with the memory itself. (That's a bit of a simplification, since there are often multiple levels of caches.)

If you could divide the problem up so that different processes were working on disjoint parts of the graph, coordination would be relatively simple. That's how large matrix computations are usually handled; the matrices are split into rectangular regions which can be (mostly) processed independently of each other. But graphs do not exhibit the same planar regularity. Edges fly around the entire graph and so multiple processors are constantly having to access data recently or even concurrently modified by different processors.

That's a lot of data moving around inside the supercomputer. Most of the work is more or less invisible to the programmer, since the "hardware" (or microcode) takes care of many of the synchronisation details. But the hardware cannot be aware of the details of the program being executed, and it is often the case that the programmer needs to interact with the caches and communications channels in order to minimize synchronisation overhead. Different computer architectures have different mechanisms for implementing this interaction, and the speed of a program will depend on the underlying data architecture and the skill of the programmer in arranging for the right data to be available in the right place before it is actually needed.

Another synchronisation problem is inherent in the irregularity of the graph data structure. In a matrix, it is likely that two rectangular regions of the same size will take roughly the same amount of time to process, making it relatively easy to divide the various computations equally between the available processors. This is not the case with graphs. You can divide the fringe into equally-sized subsets, but the number of unique descendant nodes in each subset will probably vary wildly. Real-life graphs do have clusters and concentration points (hot spots), but nothing in the data structure reveals this. It's discovered when a part of the graph turns out to require enormous computational resources, or practically none. So more interprocessor coordination is required in order to ensure that all the processors always have something to do.

In short, a good parallel solution will require both a carefully-designed high-level interprocess communication architecture as well as algorithms which can take advantage of whatever underlying data flow architecture is available on the hardware. These issues are much more apparent in graph algorithms than in more regular mathematical computations, which is why it was considered important to have a benchmark suite which specifically addresses graph algorithms.

### Overview of the TEPS benchmark.

There is a brief high-level overview in the second section of the TEPS document (which is where most of this information comes from), so I've just added a few glosses based on the comment stream to the original question.

To start with, the benchmark suite does not start with a tree. It starts with a large graph, and each benchmarked task constructs a tree, which is a connected subset of the graph.

As indicated by the benchmark overview, the benchmark consists of six phases, three of which are timed to produce the benchmark metric:

1. The benchmark randomly generates a large list of weighted edges. The number of such edges in the list is defined by the problem size. An algorithm is provided for this step, because just using a uniform random number generator to produce the pair of nodes for each edge would not produce a realistic graph. The algorithm specifies a particular non-uniformity, with parameters, so that all benchmark runs should produce graphs with similar shapes. (The weights, however, are selected uniformly in the interval (0, 1).)

The specified algorithm produces clusters whose node identifiers are themselves numerically clustered, and whose edges are clustered in the edge list. That's not realistic, and it could be exploited to artificially speed up processing. So the benchmark requires that the node identifiers be randomly shuffled, and then that the edge list itself be randomly shuffled, all of which should destroy exploitable shuffling.
2. A graph is completely specified by a list of edges, but a sequential edge list is an awful data structure to work with. So the first timed processing step turns the edge list into whatever graph data structure the benchmarker feels is convenient for their architecture and algorithms. The TEPS specification places no requirements on the datastructure, but it does require that every subsequent benchmark task (of which there are 128) start with *exactly the same graph datastructure* and nothing more. Thus, any information collected during one benchmark task cannot be recycled to speed up subsequent tasks. This preprocessing step is timed, because otherwise it might be used to offload computations specific to the tasks to be solved. Thus, the cost of the preprocessing step is amortised over the other tasks.
3. Once the graph has been preprocessed, 64 nodes are randomly selected to be used as root nodes for each of the following tasks. This is obviously not a very time-consuming problem, but the benchmark does require that the nodes be selected randomly from the set of nodes with at least one edge. (Since the edges were generated randomly, the number of edges connecting to each node will vary. In theory, it's possible that a random graph be so concentrated that there are fewer than 64 connected nodes. In practice, it's hard to imagine this actually happening, but the document does define what is to be done in that case. (Use the connected nodes no matter how few there are, rather than regenerating the entire graph.)

Generating the random list after preprocessing means that the preprocessing cannot be biased in favour of the root nodes which will be used.
4. The bulk of the benchmark consists of two straight-forward tasks, which can be found in any introductory text on graph algorithms (at least in their single-threaded form). Indeed, they will show up over and over again as the textbook advances, because they are basic building blocks for many of the more complicated graph problems.

The first of these algorithmic tasks is to construct a breadth-first search tree from each of the 64 root nodes. I understand from the comments that the word "search" is confusing, so I want to note that it is possible to search for more than one object. (In *Casablanca*, when Capt. Renault says "Major Strassen has been shot. Round up the usual suspects," he does not expect the door-to-door search to terminate when the first dissident is found.) In this case, the search is for *all* the nodes which are connected to the selected root node (which is likely to be less than all of the nodes in the graph, because no attempt was made to generate a connected graph).

The result of each of the search tasks is not just a list of nodes. It's a tree which can be traversed from the root in order to reach each of those nodes. (It's represented as a list of pairs $\<node, parent\>$.) Because this tree is created with a breadth-first traverse, the path length from the root to each node is minimal; in other words, the tree is well-balanced. This fact is useful in many algorithms which start with the construction of such a tree, so this benchmark is definitely evaluating a (part of) real-world algorithms.

The tree can be used to verify that all the nodes in the set are reachable from the root node in the original graph. The TEPS benchmark does not require full verification, I suppose because it would require an independent implementation of the same algorithm, but partial verification is at least possible and mandatory. But only the search is timed.
5. Once all 64 search trees have been constructed, the same 64 root nodes are used to find single-source shortest path trees. This is a very similar problem, which also constructs a tree from each root node to all connected nodes, but the tree is much more constrained, because it uses the edge weights which were generated in step 2. Each path to a node in the shortest-path tree must have the minimum total weight of all possible paths paths from the original graph.

If all the edge weights were equal, it would be same as the first problem, but since the weights are assigned randomly, this is not going to be the case. The solution to this problem also involves something like a breadth-first search, but instead of being organised into successive fringes, in which each fringe can be checked in arbitrary order, the traverse must check the fringe in order by increasing total weight. This creates additional communications issues when the algorithm is executed in parallel; a single-threaded solution would typically use a priority queue to produce a stream of nodes sorted by their distance from the root, but centralising node traverse between different processors through a single priority queue would create an intense memory hotspot. (I don't know the best solution to this problem.)

Again, each of the 64 subtasks in this step is timed.
6. Finally, the benchmark is computed. The assumption is that the cost of a particular subtask should be proportional to the number of edges traversed during the execution of that subtask, so the task implementations must record both the time taken and the number of edges traversed. As mentioned above, because the graph is undirected, it's expected that each edge will be traversed twice, once from each of the nodes it connects, unless the edge connects a node to itself. To correct for this difference, edges which connect two nodes are counted as "half-edges" (That is, each such edge, which is likely the vast majority of the edges traversed, is counted as 0.5 instead of 1.) The raw time and the edge count are converted into a rate by dividing the edge count by the time, giving a measure of edges per time interval; there will be 129 of these which are consolidated using a harmonic mean (and several other statistics specified in the document).

---
Tags: machine-learning, parallel-computing, benchmarking
---


title: Hiring problem from CLRS

text:
# Question
Title: Hiring problem from CLRS
Hiring problem is discussed in section 5.1 and 5.2 of the CLRS<sup>*</sup> and I'm referring this for exercise solutions.

However, for Exercise question 5.2-2 my solution deviates from the one given in the reference and mine seems be correct. I am still not satisfied with the reasoning of my solution though. Here it goes.

The Question: In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you hire exactly twice?

My solution: 1. First candidate is always going to be hired so all we have to do is to calculate the probability that only **one** candidate is hired from the remaining n - 1 candidates. So I divided it into n - 1 cases where like

case 1: If the second candidate is hired. (other than the first one only)

case 2: If the third candidate is hired.

and so on..

Now the probability of case 1:

1(anyone will be hired) * 1/2(the probability of this being more than the first) * 2/3(probability of this not being the highest till now) * 3/4 * 4/5 * 5/6.... * (n-1)/n = 1/n

Similarly for case 2: 1 * 1/2 * 1/3(must be highest till now) \*1/4... * (n - 1)/n = 1/2n

case 3: 1/3n and n-1 th case : 1/(n-1)\*n

so my answer is

1/n * (1 + 1/2 + 1/3 + 1/4... 1/(n-1))

but the solutions pdf mentions

(2^n - n - 1)/n!

My solution seems correct for n == 3 where the answer should be 3/6. So can anyone please validate this approach and guide me if this is wrong.

---

* Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein

# Answer
In fact, your result is correct and that reference solution is wrong!

Here is where that reference solution goes wrong.

> Since we view the candidate ranking as reading an random permutation, this is equivalent to the probability that a random permutation is a decreasing sequence followed by an increase, followed by another decreasing sequence.

A permutation that leads to hiring of two candidates if and only if the first candidate is not the best candidate and is better than all others candidates that come before the best candidate. There is no requirement of sequences being decreasing or increasing.

(There is a minor typo in your case 2. You meant 3/4 instead of 1/4.)

I would not say your reasoning is fully correct yet, though you have got the correct result, since I have not found a natural way to explain rigorously your way of computing the probability of each case by a product of probabilities. I am even more far away from being certain that your reasoning is wrong. It looks like you shared my feeling as well.

There are better or more rigorous ways to produce the correct result. I will let you think about it.
> 0 votes

# Answer
I think there is some problem in your approach, you are considering events in which there will be hire at 2nd or 3rd or 4th .......or n-1th place but what you didn't consider is the fact that ii should be the only hire other than the 1st one.
> 0 votes

---
Tags: algorithm-analysis, combinatorics, randomized-algorithms
---


title: Seeking an "intuitive" proof

text:
# Question
Title: Seeking an "intuitive" proof
Consider the following claim.

> Let $a\_i$'s and $y\_i$'s be positive real numbers such that: \begin{gather\*} y\_1 \leq y\_2 \leq y\_3 \ldots \leq y\_n \\ a\_1 y\_1 + a\_2 y\_2 + a\_3 y\_3 + \dots + a\_n y\_n = v \\ y\_1 + y\_2 + y\_3 + \dots + y\_n = 1 \end{gather\*} Show that there exists an $i$ such that: $$AVG(a\_i, a\_{i+1}, a\_{i+2}, \ldots, a\_n) \geq v.$$

I do have a proof for the above claim (assume the contrary; get $n$ equations; multiply $i^{th}$ equation by $y\_{i+1} - y\_i$). But, I'm looking for a more intuitive explanation — perhaps, a more "visual" or more insightful proof. Or even insights into why the above is true (without actually proving it).

# Answer
> 4 votes
Since the $y\_i$ are non-negative, you can think of $y\_1,\ldots,y\_n$ as specifying a probability distribution. One way to sample from this distribution is via the partition $$ \[0,1) = \[0,y\_1) \cup \[y\_1,y\_1+y\_2) \cup \[y\_1+y\_2,y\_1+y\_2+y\_3) \cup \cdots: $$ sample a uniform point in $\[0,1\]$, and if it falls into the $i$'th interval, output $i$.

We now further decompose these intervals, assuming that $y\_1 \leq \cdots \leq y\_n$:

* The interval $\[0,y\_1)$ is decomposed into one subinterval of length $y\_1$.
* The interval $\[y\_1,y\_1+y\_2)$ is decomposed into subintervals of length $y\_1$ and $y\_2-y\_1$.
* The interval $\[y\_1+y\_2,y\_1+y\_2+y\_3)$ is decomposed into subintervals of length $y\_1,y\_2-y\_1,y\_3-y\_2$.
* And so on. The $i$'th interval is decomposed into subintervals of length $y\_1,y\_2-y\_1,\ldots,y\_i-y\_{i+1}$.

Altogether, we obtain:

* $n$ subintervals of length $y\_1$, appearing in intervals $1,\ldots,n$.
* $n-1$ subintervals of length $y\_2-y\_1$, appearing in intervals $2,\ldots,n$.
* $n-2$ subintervals of length $y\_3-y\_2$, appearing in intervals $3,\ldots,n$.
* And so on, until a single subinterval of length $y\_n-y\_{n-1}$, appearing in the $n$'th interval.

By assumption, if we sample $i$ according to this distribution, then the expected value of $a\_i$ is exactly $v$. In particular, there must exist a subinterval length $y\_j - y\_{j-1}$ (where $y\_0 = 0$) such that the expected value of $a\_i$, *subject to the uniform point in $\[0,1\]$ falling inside a subinterval of this length*, is at least $v$. This expected value is exactly the average of $a\_j,\ldots,a\_n$.

---
Tags: intuition
---


title: Sorting elements into k subarrays

text:
# Question
Title: Sorting elements into k subarrays
> Given are $n$ integer numbers in the range $0$ to $5n$.
>
> A SubSort algorithm organizes the numbers into $k=n/100$ sets, $s\_{1}$, …, $s\_{k}$ , each containing $100$ numbers, such that the following conditions hold:
>
> i. In each set, $\_{}$, the 100 numbers are not necessarily sorted.
>
> ii. All numbers in set $\_{}$ are smaller than all numbers in $\_{}$, if and only if $ \< $.
>
> Can the worst case time complexity of SubSort algorithm be $O(n)$?

This is my solution for the problem:

We can insert all elements into an array A, and as all elements are integers in the range of $\[0,5n\]$ we can use CountingSort to sort the array. This will cost us $O(n)$ time in the worst case.

Now we can create $k$ new arrays $s\_{i},...,s\_{k}$ and copy the first 100 elements into array $s\_{i}$ and for every i\<j≤k we copy all elements from $A\[(j\*100)-((j-1)\*100)+1\]$ to $A\[j\*100\]$ to $s\_{j}$. This will cost us an additional $O(n)$ time in the worst case.

In total we have $O(n)+O(n)∈O(n)$ time complexity in the worst case.

The official solution is below:

> We can sort all numbers and then split them into sets of 100 (each set will be sorted as well, although not requested). The sorting of all the elements will be linear since all numbers are integers in the range 0 to 5 , and we can use radix sort in the following manner: Each number k is represented using base n by 6 integer keys, , 0 ≤ ≤ 5. That is a key k = 0 + 1 + 2 2+ . . 5 5 . Then we can sort the set of keys using counting sort.

I don't quiet understand what they did with the change of base and how it helps them and I wondered if maybe someone can shed some light on why their solution works, and if mine does.

# Answer
Assuming the upper bound on the maximum value of the $n$ input elements is $5n$ (as written in the question) then your solution works. Their solution works too but it is overcomplicated.

If the maximum value of the $n$ input elements is at most $n^5$, then your solution would require time $\Omega(n^5)$.

In general, if all $n$ input element are written in base $k$ (where $k$ fits in a \[constant number of\] memory word\[s\]) and are between $0$ and $k^m -1$, Radix sort takes at most $m$ iterations, each of which requires $O(n)$ time.

They chose $k=n$, so that $m \le 6$ (since $n^m - 1 \le n^5$ is equivalent to $m \le \log\_n (1+ n^5)$ and $\log\_n (1+ n^5) \le 1 + \log\_n n^5 = 1+5$). The overall time spent is then $O(m \cdot n) = O(n)$.
> 1 votes

---
Tags: sorting, counting, radix-sort
---


# Question
Title: Multiplying two integers by dividing each into 3 parts
> Integer Multiplication: $x$ and $y$ are two n-bit integers, where $n=3^k$ for some $k\>0$. We break $x$ into three parts $a$, $b$, $c$, each with $n/3$ bits; and $y$ into three parts $d$, $e$, $f$, each with $n/3$ bits. The multiplication is:
>
> $$xy = ad \cdot 2^\frac{4n}{3} + (ae + bd) \cdot 2^n + (af + cd + be) \cdot 2^\frac{2n}{3} + (bf + ce) \cdot 2^\frac{n}{3} + cf$$
>
> The multiplication can be calculated as follows:
>
> $r\_1 = ad$
> $r\_2 = (a + b)(d + e)$
> $r\_3 = be$
> $r\_4 = (a + c)(d + f)$
> $r\_5 = cf$
> $r\_6 = (b + c)(e + f)$
> $xy = r\_1 \cdot 2^\frac{4n}{3} + (r\_2 - r\_1 - r\_3) \cdot 2^n + (r\_3 + r\_4 + r\_1 - r\_5) \cdot 2^\frac{2n}{3} + (r\_6 - r\_3 - r\_5) \cdot 2^\frac{n}{3} + r\_5$
>
> Write the recurrence equation representing the algorithm and **find** the running time of this algorithm (Some logarithms you may need: $\log{3} = 0.477$, $\log{6} = 0.778$, $\log{9} = 0.954$).

For now I am only concerned with the first part of the question (the one asking for the recurrence relation).

What I can deduce from this procedure is that each of the two integers x and y is split into three parts, the variables r1 through r6 are calculated and then summed up using the formula mentioned in the last line of the problem. Since each call results in 6 calls to the same procedure, and the number of additions made is irrelevant of the size of the integer, the recurrence relation is:

$$T(n)=6T(n/3) + \theta(1)$$

Is my reasoning correct?

# Answer
Close. But consider that for example a+b isn’t an n/3 bit but an n/3 + 1 bit number, and the additions take not O(1) but O(2n/3) operations.
> 1 votes

---
Tags: recurrence-relation, recursion, divide-and-conquer
---


# Question
Title: Whats the signifgance of Conway's Game of Life?
I've seen Conway's game of life mentioned in different circles and it seems many people (myself included) have made an implementation of it at one point or another. Other than the fact that it is inherently interesting that complex patterns can arise from such simple rules and the fact that its simple enough to make a good introductory programming exercise, is there anything important about Conways game of life in particular? Or does it just happen to be the most famous cellular automata by chance.

# Answer
I'd say it's "the most famous" cellular automaton, in the sense that the structures its rules generate have been studied and given names to.

One property that it does have, that makes it more interesting than other automata, is that stable structures are fairly common in Conway's game of life.

If you try and tweak the rules (by changing the population size for creation and death) you will realize that most of the versions of GOL tend to either die instantly or immediately start to grow, so they're not very interesting.

However, there are many other interesting cellular automata, for example you can create a cellular automaton with every geometric figure that tiles the plane, for example with hexagons, and the different number of neighbors changes what sets of rules are "stable". Also, you can change the type of neighborhood you're considering, or make a continuous automata, in which the cells are infinitesimal, and define the rules in the language of vector fields.

Conway's game of life's is probably the most famous one because it was made by Conway, a very influential mathematician, and it's defined "on a checkerboard", which makes it very easy to explain and understand.
> 3 votes

# Answer
Two interesting properties: 1. There are states that have no predecessor. 2. Game of life is actually Turing complete!
> 0 votes

---
Tags: automata, cellular-automata
---


# Question
Title: Is the following language a Deterministic Context-Free Language?
I tried to show the following language is DCFL (Deterministic Context-Free Language):

$$L=\\{wo^n\mid w\in\\{a,b\\}^\*, n\_a(w)=n\_b(w)=n, |w|=2n\\}$$

I tried to show that $L$ has a DPDA (Deterministic Push-Down Automota), but I get stuck to find a DPDA for $L$.

# Answer
Your language isn't context free.

Assume $L$ is context-free. Then by the pumping lemma for context-free languages we have a constant $n\_L$ such that for every $z \in L$ with $|z| \geq n\_L$ there exists a decomposition $z = uvwxy$ with properties (i) $|vx| \geq 1$ (ii) $|vwx| \leq n\_L$ and (iii) $\\{uv^iwx^iy \mid i \in \mathbb{N}\\} \subseteq L$

Let $z = a^{n\_L}b^{n\_L}o^{n\_L}$.

Clearly for every decomposition $z = uvwxy$ satisfying (i) and (ii), $vwx$ contains at most two different characters. Then, however, $uv^2wx^2y$ cannot have the same amount of $o$'s, $a$'s and $b$'s because of (i). This leads to a contradiction to our assumption and $L$ isn't context-free.
> 3 votes

# Answer
Your language isn't context-free. If we intersect it with the regular language $a^\*b^\*o^\*$, we get one of the prototypical non-context-free languages, $\\{a^nb^no^n : n \in \mathbb{N}\\}$. Since the context-free languages are closed under intersection with a regular language, this shows that your original language isn't context-free.
> 4 votes

---
Tags: formal-languages
---