texts: GOTO statement in programming environments for beginners?

texts:
As a student, back in the day, I was exposed to high level programming languages that not only had a GOTO statement, but on which its use was common. I also did my fair share of programming in assembly code, but always had the impression that my understanding of the semantics of subprograms was enormously facilitated by my familiarity will programs constructed without them, in high level imperative languages, even though I never used them (or felt the need) in my life as a programmer, ever since.

In my experience as a teacher, the passage from non-modular to modular programming is always a struggle, and I keep asking myself the following question:

Would the careful and well-supervised reintroduction of the jump command in languages and environments devoted to introductory lessons in programming be of help students with the passage from non-modular to modular programming?

For clarity: the usage of the GOTO statement I am talking about here is restricted to programming environments used exclusively for teaching the basics of programming, while (or where) it is still done using imperative (monoparadigm) languages. Informed opinions based on experience and/or indications of research available on the subject (I didn't find anything substantial) are really welcome.


texts: Potential function in amortized analysis

texts:
I am trying to calculate the amortized cost of a dynamic array, that's size becomes 4 times the size when the array is filled. (when you re-size, you create a new one and copy the elements there).

Here is what I am reading from. (starts at pg. 30)
This example has the array doubling when it is filled.

This is my potential function analysis so far:
But in the end I am getting 7-2i, I don't think it can be like that. I think the i's should cancel out.

Does anyone know whats wrong?

Potential of the array after the $i^{th}$ insertion is $\Phi(D_i) = 4i - 4^{\left\lceil \log_{4}i\right\rceil}$.

Assume $4^{\left\lceil \log_{4}0\right\rceil} = 0$.

The amortized cost of the $i^{th}$ insertion is:

$\^c_i = c_i + \Phi(D_i)-\Phi(D_{i-1})$

$~~~= \{ i$ if $i-1$ is an exact power of $4$

$~~~~~~~\{ 1$ otherwise

$~~~~~~~+ (4i-4^{\left\lceil \log_{4}i\right\rceil})-(4(i-1)-4^{\left\lceil \log_{4}
(i-1)\right\rceil})$

$~~~= \{ i$ if $i-1$ is an exact power of $4$

$~~~~~~~\{ 1$ otherwise

$~~~~~~~+ 4-4^{\left\lceil \log_{4}i\right\rceil}+4^{\left\lceil \log_{4}(i-1)\right\rceil}$

Case 1 ($i-1$ is an exact power of $4$):

$\^c_i = i + 4-4^{\left\lceil \log_{4}i\right\rceil}+4^{\left\lceil \log_{4}(i-1)\right\rceil}$

$~~~= i + 4-4(i-1)+(i-1)$

$~~~= i + 4-4i+4+i-1$

$~~~= 7-2i$


texts:
here is a nested loop where all the variable are integers.This is another question to the thread. I understood the solution part , but stuck in the time-complexity part.

What is the time complexity of the below code and how?

def divide(dividend, divisor):
    """
    :type dividend: int
    :type divisor: int
    :rtype: int
    """
    #Time-complexity ??
    while dividend>=divisor:
        t=0;k=divisor

        while dividend>=k:
            dividend-=k
            k<<=1
            q+=1<<t
            t+=1

    return q


texts: Solving the emptiness problem for a CFG in Chomsky normal form (linear)

texts: Given a CFG in Chomsky normal form, is there an algorithm that solves the emptiness problem in linear runtime? I thought about using depth search here, but I think it's a little bit above linear runtime.


texts: Datalog Program Equivalence with Fixed Universe Size

texts: It is well known that to compute equivalence of two Datalog programs (or equivalently of two first order formulas with the least fixed point operator) wrt all possible inputs and universes, is undecidable. If we fix the universe size to be N, it is clearly decidable in time exponential wrt N. My question is whether one can do better, maybe even in time logarithmic in N (and maybe much worse wrt the length of the programs). Note that equivalence of two nonrecursive Datalog rules can be done in constant time for all inputs, let alone for fixed N, but is NP-Complete wrt the rules' size.


texts:
How exactly does the control unit in the CPU retrieves data from registers? Does it retrieve bit by bit?
For example if I'm adding two numbers, A+B, how does the computation takes place in memory level?


texts: Narrowing the field of a combitorial game

texts:
I'm doing a challenge and it has posed a problem I am unfamiliar with.  It goes like this,  You start with two numbers, 1 and 1.  You can combine the numbers in either direction, in this case makes 2,1 and 1,2 or in the case of 3,2 it would produce 5,2 or 3,5.  Always starting from 1,1 my challenge is to try to find a pair of numbers in as few "moves" as possible.

My first pass was to build a greedy-first SSS* like algorithm.  Works well for a small space but in the end takes too long on large inputs.  So I think I have to massively narrow the search.  Or I'm sure someone has seen this before and has come up with a clever workaround.

Any help is appreciated


texts: When do insertions and deletions get enacted in a buffer tree?

texts: Buffer trees are $(a, b)$-trees in which each node in the tree gets an associated buffer for storing operations to be conducted on elements in the tree. While I appreciate the idea of amortizing the I/O cost of updates by batching updates on elements in the same block together in the buffers, what is unclear to me from the paper I linked is when these updates are supposed to be enacted. Is it when the buffer of a leaf node (defined as a node whose children are all leaves) fills up and we have to empty it? If not, then how exactly do the buffers affect tree balancing? When do the updates for keys that aren't stored in the leaves get enacted?


texts: Dividing a weighted planar graph into $k$ subgraphs with balanced weight

texts:
I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge weights. After cutting, each subgraph must be connected (i.e. there must be a path between any two vertices of the subgraph which is only composed of vertices in that subgraph).

However, unlike most existing work on graph partitioning out there, I don't intend to obtain subgraphs that contain the same approximate number of vertices. Instead, I would like these subgraphs to have similar sum of edge weights. In other words, I would like to minimize the sum of edge weights of the subgraph with maximal weight and ideally cut long (weighted) edges.

Is there a name for this problem? I wasn't able to find anything about this on the web. Also, how can I approach this problem?


texts: Sorting strings using Counting Sort in O(n), where n is the total number of characters in all the strings

texts: Suppose, you are given an array of strings of different lengths, but the total number of characters over all the strings is n. Describe an algorithm using Counting Sort to sort the strings in alphabetic order (eg. algorithm < cs < hello) in O(n) time.


texts: Proof of contention of the wait-free consensus algorithm

texts:
I know that this is a known theorem but I can't find its proof. The theorem is:

  The write-contention of any $n$-process wait-free consensus algorithm (implemented from any read-modify-write operations) is $n$.

Can someone link me to a proof or an explanation?


texts: Overflow rule in two's complement arithmetic

texts:
In the book by William Stallings the overflow rule overflow rule for 2's complement addition is stated as follows:

  Overflow rule: If two numbers are added, and they are both positive or both negative, then overflow occurs if and only if the result has the opposite sign.

Then the book gives the following examples:

Doubts:

If two numbers with the same sign are added, shouldn't the result have the same sign?  How can the result have an opposite sign (e.g., $+1+2=+3$ and $-1-2=-3$)?
Point 1 is reflected in the examples (d), (e) and (f). An overflow seem to occur in all of them  (though the word "Overflow" is not printed in example (d)), but the sign of the result is the same as that of operands.


texts: Finding $L^*$ when $L=\{a^nb^n | n \geq 1\}$

texts:
Let $L=\{a^nb^n | n \ge 1\}$, then $L^\star=L^0 \cup L^1 \cup L^2 \cup L^3 \cup \dots = \{\epsilon\} \cup \{a^nb^n\} \cup L^2 \cup L^3 \cup \cdots$ .

How to find $L^2$ and $L^3$, and is $L^2=\{a^nb^na^nb^n\}$? In this video https://youtu.be/rnGpW6RRAcw at 31:51, the professor said that $L^2 = \{a^{n_1}b^{n_1}a^{n_2}b^{n_2}\}$, how did she find this form.


texts:
The problem involves date intervals filtered by days of week. For example, the filtered interval {2001 APR 1 - 2001 APR 30, 17} corresponds to all Mondays and Sundays between April 1 and April 30. Here is the problem: given a collection of filtered date intervals, find a minimal collection of such intervals that cover exactly the same set of dates.

Initially, I naively assumed that this can be solved by sorting the intervals by start dates and merging consecutive intervals, if possible. Here is a counterexample to this approach. Consider the date interval given by the pattern $56712345671234$, where each number stands for a day of week. Assign zero-based indices to the dates in this pattern. The set of dates covered by intervals $\{0-2, 567\}$, $\{3-9, 1234\}$, $\{10-13, 12\}$ can be covered by the collection $\{0-6, 1234567\}, \{7-13, 12\}$. The merging algorithm will fail to merge any intervals and will output three intervals as the minimal cover instead of two.

Is there a well-known algorithm for this problem? Can it be solved in $O(n \log n)$ where $n$ is the number of input intervals?


texts: Check the Regularity of the folowing Languages

texts:
Let $A$ be a regular set. Consider the two sets below.

\begin{align*}
L_1 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n} \}, \\
L_2 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n} \}.
\end{align*}

Which of the following is true?

$L_1$ and $L_2$ are regular
$L_1$ is regular but $L_2$ is not
$L_2$ is regular but $L_1$ is not
Both are not regular

What I knew

$Y \in A $ only but now the relation between $y$ and $x$ is:  $Y  =  X^{n}$  and given the clause there exist associated with the value of $n$, so we can assign any value of $n$ which is $\geq 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.

Similarly on setting $n = 2$, we get $Y = X^{2}$  meaning $Y$ can be partitioned on exactly 2 halves and hence we can say $X$ is $\mathrm{half}(Y)$. And we know given a language or a set $L$ is regular, then $\mathrm{half}(L)$ is also regular.

With this understanding I came to a conclusion that $L_1$ is regular.

But, How to check the regularity of $L_2$? I also wanted to confirm my approach to $L_1$ being regular is correct.


texts: Finding largest subset that matches moments

texts:
I would like to find a algorithm that will do the following:

Given two sets $A, B \subseteq \mathbb{R}$, where $|B| > |A|$, find the largest subset $C \subseteq B$, such that:
$\qquad |\operatorname{mean}(A) - \operatorname{mean}(C) |< \delta$ and
$\qquad |\operatorname{std}(A) - \operatorname{std}(C) | < \epsilon$

I think this problem is NP-hard, but I would like a good approximation that does reasonably well. An even harder version of this is to find the larget subset $C$ that matches not just the moments, but the histogram of $A$ to some quality metric. If you have a solution, or can point to same papers that would great!
I am a neuroscientist, and this is for my research.


texts: I encountered two applications of RS codes - one in group testing, and another time someone said that a solution to an interview question was using it. But when I search for explanations, it's all about the cracks in the CD disks and such. Is there a good source that puts the math first?


texts: What are efficient ways to compute the derivatives of iterated functions?

texts:
The derivatives of iterated functions at a fixed point $z_0$ are useful in constructing a Taylors series of iterated analytic functions - in other words, the Taylors series of a dynamical system $f^t(z_0)$.

A simpler version of the problem casts light on possible approaches. Instead of iterated functions, consider composite functions and Faà di Bruno's formula The combinatorial structure integer partitions serves as the index to the summations in Faà di Bruno's formula. So the first step of evaluation is to enumerate all integer partitions of a given order.

While combinatorial structure integer partitions are associated with the derivatives of composite functions, the unlabeled version of the labeled combinatorial structure total partitions are associated with iterated functions. See Partition Diagrams for more information on the different relevant combinatorial structures. The following Mathematica code does what I need, but the cost of simplicity is that it first enumerates the labeled total partitions to compute the unlabeled total partitions. So for $n=10$, $D^{10}f^t(z_0)$, there are 282,137,824 labeled total partitions, while there are only 2,312 unlabeled partitions.

Combinatorial Examples

a(4)=5 unlabeled total partitions: (oooo),(oo(oo)),(o(ooo)),(o(o(oo))),((oo)(oo)).

b(4)=26 labeled total partitions: ((1,4),2,3), (1,(2,4),3), (1,2,(3,4)), (((1,4),2),3), ((1,(2,4)),3), ((1,2),(3,4)), (((1,4),3),2), ((1,(3,4)),2), ((1,3),(2,4)), ((1,4),(2,3)), (1,((2,4),3)), (1,(2,(3,4))), (1,2,3,4), ((1,2,4),3), ((1,2),3,4), ((1,3,4),2), ((1,3),2,4), (1,(2,3,4)), (1,(2,3),4), ((1,2,3),4), (((1,2),4),3), (((1,2),3),4), (((1,3),4),2), (((1,3),2),4), (1,((2,3),4)), ((1,(2,3)),4)

b(4) = 12 (o(o(oo))) + 3 ((oo)(oo)) + 6 ((oo(oo)) + 4 (o(ooo)) + (oooo) = 26

I would like to have an efficient way to reproduce the preceding results.

Mathematica code

TotalPartitions[0] = {{}};
TotalPartitions[1] = {{1}};
TotalPartitions[2] = {{1, 2}};
Match[l_List, pattern_] := Extract[l, Position[l, pattern]];
TP1[l_List, next_Integer] :=
  Map[( l /. # -> {#, next}) &, Match[l, _Integer] ];
TP2[l_List, next_Integer] :=
  Map[( l /. # -> Append[#, next]) &, Match[l, _List] ];
TP3[l_List, next_Integer] :=
  Map[( l /. # -> {#, next}) &, Match[l, _List] ];
TotalPartitions[n_Integer] :=
  TotalPartitions[n] =
   Flatten[ {Map[(TP1[#, n] ) &, TotalPartitions[n - 1]],
     Map[(TP2[#, n] ) &, TotalPartitions[n - 1]],
     Map[(TP3[#, n] ) &, TotalPartitions[n - 1]]}, 2];

u = TotalPartitions[4] /. _Integer -> 1
> {{{{1, 1}, 1}, 1}, {{1, {1, 1}}, 1},
>  {{1, 1}, {1, 1}}, {{1, 1}, {1, 1}},
>  {1, {{1, 1}, 1}}, {1, {1, {1, 1}}},
>  {{1, 1}, 1, 1}, {1, {1, 1}, 1},
>  {1, 1, {1, 1}}, {{{1, 1}, 1}, 1},
>  {{1, {1, 1}}, 1}, {{1, 1}, {1, 1}},
>  {{1, 1, 1}, 1}, {{1, 1}, 1, 1},
>  {1, {1, 1, 1}}, {1, {1, 1}, 1},
>  {1, 1, 1, 1}, {{1, 1, 1}, 1},
>  {{1, 1}, 1, 1}, {{{1, 1}, 1}, 1},
>  {{{1, 1}, 1}, 1}, {1, {{1, 1}, 1}},
>  {{1, {1, 1}}, 1}, {{1, 1, 1}, 1},
>  {{{1, 1}, 1}, 1}, {{{1, 1}, 1}, 1}}

SetAttributes[Z, Orderless];
Tally[Apply[List, Apply[Z, u, Infinity], Infinity]]
>  {{{1, {1, {1, 1}}}, 12}, {{{1, 1}, {1, 1}}, 3}, {{1, 1, {1, 1}}, 6},
>   {{1, {1, 1, 1}}, 4}, {{1, 1, 1, 1}, 1}}

Note that the Tally function displays the number of occurrences of labeled total partitions for each unlabeled total partition, so that $12+3+6+4+1=26$ shows how the 5 unlabeled total partitions of order 4 map to the 26 labeled total partitions. I've tried pure analytic approaches, combinatorial approaches and a hybrid of the two in my Mathematica programs Schroeder Summations and Iterate. I believe this is a useful problem in dynamics and combinatorics and merits an efficient answer.


texts: Machines whose languages are their own encoding

texts:
Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable?

I tried diagonalization but can only prove that $R = \{\langle M \rangle \mid M \text{ is a Turing Machine and } \langle M \rangle \notin L(M)\}$ is not recognizable, which does not seem to help in this case...


texts: Generating many graphs satisfying some properties

texts:
Suppose I want to generate all graphs satisfying some properties (specifically 2-connected graphs on 30 vertices with degree sequence $(4, 4, 3, 3,3, \dotsc, 3)$). Unfortunately, there are an enormous number of such graphs. Probably the fastest way to find all of them would to use nauty, but it is too slow.

Is there a way to just generate many such graphs (i.e., not needing a complete list)?

There isn't an obvious way to get nauty to output just the first 10 million graphs, for instance. Maybe this isn't even possible, I don't know how nauty works.


texts: Looking for a matching-like mapping with a spread constraint

texts:
I am doing a project on task assignment with geographic constraints which naturally leads to the following question.

Let $\mathbb{N}$ denote the set of integers. Given a finite subset $A \subset \mathbb{N}$ and a function $T: A \rightarrow \mathbb{N}$, let $R(T)$ denote the range of $T$ and define $${\rm cost}_r(T)= \sum_{i,j \in R(T)} { 1}_{\{|i-j| \leq r\}}.$$ Here $r$ is some nonnegative integer. In  words, we ``pay'' for any two points in the range of $T$ that are sufficiently close.

The problem I would like to solve is the following. Given:

a set $A \subset \mathbb{N}$
nonnegative integers $d,r,c$

does there exist a map $T: A \rightarrow N$ such that

$|T(a)-a| \leq d$ for all $a \in A$.
${\rm cost}_r(T) \leq c$.

In words, can we achieve a very spread out range for $T$ (captured in the constraint that the cost is at most $c$) while simultaneously mapping every element close to itself (captured in the constraint that $|T(a)-a| \leq d$)?

My most basic question is whether this problem is polynomial time or NP-hard. Informally it feels like this question is optimizing something nonconvex over matchings, which suggests it should be NP-hard; but the underlying ``graph'' is a simple one which only allows nodes to be matched to other nodes not to far away, and maybe there is a way to use this restrictive structure to get a polynomial time algorithm.

I call these ``matching-like'' in the title since if $c=0$ and $r=0$, the map $T$ has to be one-to-one, meaning it defines a matching.

If any one has any pointers to similar problems considered in the literature, that would be most helpful.


texts: Understanding basic queue and dequeue operations

texts:
CLRS gives the following implementation for a queue's enqueue and dequeue operations

head = 1
tail = 1

ENQUEUE(Q, x)
Q[Q.tail] = x
if Q.tail == Q.length
    Q.tail = 1
else Q.tail = Q.tail + 1

DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
    Q.head = 1
else Q.head = Q.head + 1
return x

but I'm having trouble understanding why both

if Q.tail == Q.length
    Q.tail = 1

and

if Q.head == Q.length
    Q.head = 1

are needed. What would be a conceptual (or possibly visual) explanation of these two if-statements?


texts: Problem with Understanding a Recursion Tree

texts:
Consider the recursion tree:

$T(p) = 3T(\frac{2p}{8}) + 2T(\frac{p}{8}) + O(p)$.

I determined that there are at most $1 + log_{4}\ p$ levels, because the longest simple path from root to leaf is $p \rightarrow \frac{2p}{8} \rightarrow \frac{4p}{16} \rightarrow \frac{8p}{32} \rightarrow\ ...$.

This means that the time complexity is $O(p\ log\ p)$.

Now, I stopped all my leaves in the above recursion tree have $T(1)$, but say I have the condition $T(0) + O(1)$. Does this change my solution somehow?


texts: What sort of theoretical machine would be needed to solve the tiling problem?

texts:
So theoretically, what sort of machine would we need to solve the tiling problem?

(Given a set of tiles, decide if they will tile the plane or not.)

I know we could have a Turing machine plus a "tiling oracle", but do we know what, specifically a Turing machine isn't able to do that keeps us from being able to compute the answer?


texts:
Suppose I have a simple polygon whose vertices are $p_1,\ldots,p_n$ each $p_i \in \mathbb{R}^2$. Suppose now I pick two distincts vertices $p_i,p_j, i\neq j$ Is there some algorithm I can use to test for intersections between the segment $\overline{p_i p_j}$ and some edge of the polygon?

You can assume an half edge data structure is used for the polygon and the edge $\overline{p_i p_j}$ has to be inserted, so I'm looking for a quick test I can do before inserting a possible invalid edge. The polygon isn't necessarily convex.


texts:
I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem.
it is this

If i number of people voted for A and j number of people voted for B then dp[i][j] counts the number of ways voting can happen.

dp[ i ] [ j ] = dp[ i ] [ j - 1 ] + dp[ i - 1 ] [ j ] .

basically, I want to find the number of ways candidate A is in the winning position throughout.
Can anyone explain the logic behind the dp equation ?
I think it works like this.
We have a sequence of A and B.In which A wins throughout. Now we add one more A to that sequence or add one more B to it.


texts: Is CFL closed against exchanging complementation and reversal?

texts: Let $L$ be a language such that $\overline{L}^R$ (the reversal of the complement of $L$) is context-free. Is then also $\overline{(L^R)} \in \mathrm{CFL}$?


texts: Finding a certain subset of a weighted tree

texts:
Given a rooted tree with $n$ weighted nodes and a number $1\leq k\leq n/2$, what is an efficient algorithm for finding a subset of the nodes having

$k$ elements
no node being an ancestor of another
maximal sum of the weights (among all subsets fulfilling the previous two conditions)

Edit: Comments suggest dynamic programming. Here's my failing attempt in that: sort the nodes according to weight in decreasing order. The case $k=1$ is easy of course. Take the first node. But what about moving from $k$ to $k+1$? We can't just take the next weightiest node that is not an ancestor or a grandchild of any of the nodes in the previously constructed subset and add it to the subset. This could fail already in the case $k=1$. What's the correct approach here?


texts: Let's say I am using Bloom filters to create a function to check if a word exists in a document or not.  If I pick a hash function to fill out a bit bucket for all words in my document. Then if for a given number of words, wouldn't the whole bit bucket be all 1s? If so then checking for any word will return true? What am I missing here?


texts:
In boolean circuit complexity, a circuit is just defined by a Directed Acyclic Graphs with designated input and output nodes, where the intermediate nodes compute a specific boolean function. A circuit is called a formula if the underlying graph is a tree. i.e., the fan-out of each node is $1$. Is it true that for a formula, (given that its fan-out is already $1$, by defintion) the fan-in is also constant?

In the usual definition of formulas, this is never spelt out(Its always defined as a circuit where all gates have fan-out $1$). But somehow I seem to carry around this intuitively that formulas are always bounded fan-in. (It might be partly due to the fact that poly-sized boolean formulas correspond to $\mathsf{NC^1}$ which is a complexity class defined by bounded fan-in circuits of logarithmic depth).

So my question is, if you bound the fan-out of the circuit to be $1$, does it imply even the fan-in should be constant for every gate? I tried to use a counting argument, that says that the indegree and outdegree of the graphs must sum to the same, but somehow a water tight proof eludes me. First of all, is my intuition correct?


texts: Number of Function Calls In Recursive Code

texts:
I am new to recursion. I am doing some practice questions and I was wondering what the technique is for going from some recursive code to identifying the number of function calls it makes.

function win(n)
   if n ≤ 3 let memo(n) = 'yes'
   if memo(n-2) = 'no' or memo(n-3) = 'no' let memo(n) = 'yes'
   else let memo(n) = 'no'
   let win(n) = memo(n)

  Roughly, what is the number of steps that this program uses to compute $\mathit{win}(n)$? Is $\mathrm{step}(n)$ linear in $n$, polynomial in $n$ or exponential in $n$? Is it feasible to use this code to calculate $\mathit{win}(1000)$ on a fast supercomputer? Justify your answer.


texts: Is the set partitioning problem NP-complete?

texts:
I know that the set partitioning problem defined like this:

  Given $$S = \left\{ x_1, \ldots x_n \right\}$$ find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $\displaystyle\sum_{x_i \in S_1} x_i=\sum_{x_i \in S_2} x_i.$

is NP-complete. But I don't understand why (or am not even sure if) the following problem is NP-complete:

  Given $$S = \left\{ x_1, \ldots x_n \right\}$$ find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $$| \sum_{x_i \in S_1} x_i-\sum_{x_i \in S_2} x_i |$$ is minimized.

The paper 'The Differencing Method of Set Partitioning' by Karp and Karmarkar and some others say that it is NP-complete. But, if I have a sample solution to this problem, I can not tell whether it is an optimal solution (unlike in the first problem) and therefore I feel it NP-hard. If this is not true, how can I conclude that it is NP-complete? Thanks!


texts: Why does the Pumping-lemma for context-free languages use uvwxy, but the one for regular ones uvw?

texts: Basically what the title says. Why can you "ignore" the "xy" part if you want to prove whether a language is regular?


texts: Proving that L(G) is the language defined by the CFG G

texts:
I have a context-free grammar defined by the production S:

S → aSbS ∣ bSaS ∣ ε

I need to prove that the CFG "G" can be defined as a language L(G) where

L(G) = {w ∈ {a, b}∗ ∶ na(w) = nb(w)}.

Where na(w) = number of a's in w, and nb(w) is the number of b's in w

How can I go about proving something like this? Is there a method?

Without giving the answer away.


texts: Approximation factor shorthand clarification

texts:
I'm starting to dabble in the world of approximation algorithms and had a question about the convention many papers will use when talking about the approximation factor. I know that an approximation factor will give the factor within which the algorithm will perform with respect to the optimal solution. This is pretty easy to grasp for things like a 2-factor approximation. I've also seen other literature and lecture notes refer to $1-1/\epsilon$ when giving the probability and/or percentage of the optimal that will be returned (or, put another way, how "much" of the optimal an approximation algorithm will, well, approximate).

But I've seen some papers (like Linear-Time Approximation for Maximum Weight Matching
) refer to a $1-\epsilon$ approximation ratio. For example:

  we give an algorithm that computes a (1 − ε)-approximate maximum weight matching

So my question is: are they referring to the $1-1/\epsilon$ ratio that I've been seeing elsewhere? Apologies if this is a simplistic question, I'm just getting starting in learning about these very-cool algorithms and am trying to get my head around which papers are presenting things that are extraordinary vs. not as competitive compared to the optimal solution. Thank you!


texts:
Is there a way of combining two turing machines without introducing an extra state (I don't want to increase or decrease the total number of states)? Don't worry about an accept or a reject state since they are not that important; I just want a TM to do some computation starting from a blank tape, and I want the result of that computation (some tape contents) to be used by the next TM right after the first machine halts  (i.e output redirection)

The only solution I can think of (without introducing a new state) is that I combine the halt state of first machine and the initial state of the second machine into one state, but I am decreasing the total number of states by 1.


texts: Who first invented and analysed algorithm of finding median in a stream of integers using two heaps?

texts:
There is popular problem:

  Given that integers are read from a data stream, find the median of
  elements read so far in an efficient way.

One of possible solutions:

Use max-heap for left heap (i.e. for elts lower than median) and min-heap for right heap (i.e. for elts higher than median). While receiving each new integer from the stream, add it to either left heap or right heap depending on comparison with current median. Keep left and right heaps balanced, if one of heaps bigger by one, extract top element and put to another heap.

Here is a implementation of this solution.

This question is very popular in job interviews (I had that one), many people on the internet mention this algorithm (at least a few blogs/books about coding interviews).

But this algorithm looks like "noname" algorithm because nobody mentioned author of this algorithm.

I understand how this algorithm works. But I would be glad to hear academic sources about this algorithm.


texts: What is the relation between First Order Logic and First Order Theory?

texts:
I thought that any FOT is a subset of FOL, but that does not seem to be the case, because FOL is complete (every formula is either valid or invalid), while some FOT (like linear integer arithmetic) is not complete.

So, is FOL more expressive than any of FOT? Or incomparable?

Also, the statement "there are statements that are valid in LIA but cannot be proved using axioms of LIA" is weird. How can the statement be valid if we cannot prove its validity? I always thought that if you cannot prove the validity of the statement, then you cannot claim it is valid.


texts: What is the difference between broadcast and gossip/epidemics?

texts:
Everything is in the title.
What is the difference between broadcast and gossip in the context of message-passing distributed systems?
According to Wikipedia, gossip and epidemic protocols/epidemics are synonym.
Thank you for your help.


texts: Is there a "theory" of operating systems?

texts:
Is there a theory for Operating Systems?
That is, subfields of CS have theoretical parts; i.e. PL has type theory, ML has mathematical theorems, security has a lot of provable properties, etc.
There are certain "properties" in OS, like the optimality of SJF scheduling algorithm or the dining philosophers, but these seem like small examples.
I feel like most of OS is engineering -- i.e. paging mechanisms, scheduling algorithms, thread management. Is there a "foundational theory" of Operating Systems?


texts: Covering a complete graph with n copies of an arbitrary graph: NP-complete?

texts:
Given a complete graph $G$, an arbitrary graph $H$, and a positive
  integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that
  their union is $G$, and each of them are isomorphic to $H$?

This is a problem which I believe is NP-complete, but I am unsure if it is actually so. Any ideas of how to prove this?

Notes:

If $G$ is instead allowed to be an arbitrary graph, then this is clearly at least as hard as subgraph isomorphism, which is NP-complete.
If $G$ is allowed to be an arbitrary graph, and $A_1,\dots,A_n$ are required to be isomorphic to a subgraph of $H$, instead of the entire graph $H$, then the problem can be reduced from vertex cover (which is NP-complete) by setting $H$ to be a star graph with the number of spokes equal to the number of nodes in $G$.
The problem where $H$ must also be a complete graph is called "covering design", and has some discussion here, with closed forms for when $H$ has 3 or 4 nodes. Finding algorithm for this is apparently an open problem.


texts: Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete

texts:
I'm a little stuck on this question, any help would be appreciated!

Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is NP-complete.

HCE: Given an undirected graph G and an edge e of G, does G have a Hamiltonian circuit/cycle that uses e?

I've tried to approach this by showing that HC $\leq$ HCE, but I'm wondering if my approach is too convoluted.

EDIT:

I think I have a solution.
Consider a graph $G=(V,E)$ where $V$ is the set of vertices in $G$,
and $E$ is the set of edges in $G$. Let $f(G)=G'=(V',E')$ where

\begin{alignat*}{1}
V'= & V\cup\{v_{\alpha},v_{\beta},v_{\gamma}\},v_{\alpha},v_{\beta},v_{\gamma}\notin V\\
E'= & E\cup\{(v_{\alpha},v_{\beta}),(v_{\beta},v_{\gamma})\}\cup\{\bigcup_{i\in\{\alpha,\gamma\},v\in V}(v,v_{i})\}
\end{alignat*}

Let the edge $e=(v_{\alpha},v_{\beta})$.

$G'$is the graph $G$ with three additional vertices. $v_{\alpha}$
and $v_{\gamma}$ are connected to all the vertices in $G$ and $v_{\beta}$.
$v_{\beta}$ has a degree of 2, and is only connected to $v_{\alpha}$and
$v_{\gamma}$. $f$ can be computed in p-time.

Consider some $G$ that has a HP along vertices $v_{1},v_{2},...,v_{n}$.
Then $G'$ will also have a path $v_{1},v_{2},...,v_{n}$ with each
vertex only appearing once in the path. In order to turn this path
into a HC, the three additional vertices will have to be included.
In order to do so, the path has to be extended in either $v_{n},v_{\alpha},v_{\beta},v_{\gamma},v_{1}$
or $v_{n},v_{\gamma},v_{\beta},v_{\alpha},v_{1}$. $G'$ thus have
a HC that will always include the edge $e$.

$\therefore$ G $\in$ HP $\implies$$f(G)=G'\in$ HCE

Consider some $G'$ with a HCE along some path $v_{1},v_{2},...,v_{n},v_{\alpha},v_{\beta},v_{\gamma},v_{1}$.
Since $G$ has vertices $V=V'\backslash{v_{\alpha},v_{\beta},v_{\gamma}}$,
$G$ has a HP along vertices $v_{1},v_{2},...,v_{n}$.

$\therefore$ $G'\in$ HCE $\implies G\in$ HP

And thus $G\in$ HP iff $f(G)=G'\in$ HCE. Since $f$ can run in p-time,
HP $\leq$ HCE.

$\therefore$ HCE is NP-complete.


texts: Hashfunction for unique character distributions

texts:
The original problem is given a large input file, with n input lines of random string, find the number of pairs-> meaning same number and type of characters, in the file. Constraint on type of characters is: any legal ascii(0-127) char besides 10 and 13. I am trying to implement a hashCode function for a wrapper class over a sized 128 int array that is ideally quick and results in minimal collisions.

Hence, my approach is to process each line into a int counting array of size 128 encoding the ascii set distributions into a wrapper class, then to store this array as a key in a hashtable/hashmap ( or possibly eventually to make my own hashtable implementation with linear probe to store it in). with value as the number of matching character distributions, from which I can calculate the number of pairs additively via Handshake Lemma to accumulate as I read through lines of text.

Hence to do this, I need some advice on selecting a appropriate fast hashing function that minimises collisions, and perhaps more importantly for my own understanding, the proof or a link to the proof. Initial number of total lines is given, so if there is a formula to calculate the required size, from that, it can be done.
What I have done, arbitrarily using this as my hash function so far:

public int hashCode(){
        int hash = 0;
        for (int i = 0; i<128;i++){
            hash+= b[i]*(i+1);
        }
        return (hash*this.size)%capacity;
    }

Capacity meaning the size of the hashtable itself.
In math terms n = Size of String, m = size of hashtable:
$\sum^{128}_{i=0}(x[i]*(i+1))*n \mod m$

The requirements for this hash function are:
given a constant sized 128 int array in which each value in the index is bounded maximally by length of the string
how can I come up with a unique hash.

or alternatively:
given a string of size x with unique character distributions, how can I calculate the hash value, such that another string with same character distribution has the same hash value.

Ideally it will be a fast compute hash function

Thanks!


texts: Finding a O(n) solution to: max difference of pairs array question

texts:
I don't know an O(n) solution to the following:

Given an array of n integers, find the largest difference between any two pairs in the array: however, the larger integer must have a higher index in the array than the other.

Ex: alg({9, 2, 6, 7}) = 5

It seems straightforward, yet it eludes me.


texts: How to describe this language a* (ba (cf* (g ( f +h )* bf* )* e )* a* )* in words?

texts:
I was task to describe this regular expression a* (ba (cf* (g  ( f +h )*   bf*   )*  e )*  a)* informally.
My attempt at describing it informally =  any number of a followed by any number of one b one a with any number of one c and any number of f with any number of one g with any number of f or h one b and any number of f and one e and one or more a.
I know it's wrong but I don't know what else to write. I'm just really confused
Question : What is the informal description of this language?


texts: Half precision floating point question -- smallest non-zero number

texts:
There's a floating point question that popped up and I'm confused about the solution. It states that

IEEE 754-2008 introduces half precision, which is a binary
floating-point representation that uses 16 bits: 1 sign bit, 5
exponent bits (with a bias of 15) and 10 significand bits. This format
uses the same rules for special numbers that IEEE754 uses. Considering
this half-precision floating point format, answer the following
questions: ....
What is the smallest positive non-zero number it can represent?

The answer says:
bias = 15
Binary representation is: $0 \, 00000 \, 0000000001 = 2^{-14} * 2^{-10}=2^{-24}$
I've understood the binary representation part, but how does it get to those exponents of 2??


texts: Construct this two-taped Turing Machine {(u#,v#):u,v E {a,b}* , |u| = 2|v|}

texts: I am having troubles trying to create this two-taped Turing Machine, I understand how I would get it to accept 2 strings of equal length. But to move forwards, I dont know how I would check to see if |u| = 2|v|


texts:
I want to design a binary tree with preallocated nodes, in order to avoid calling malloc/free every time I want to insert/delete a node. The problem is I don't know ahead of time how many nodes the tree will have, so I am thinking I need to allocate a block of nodes at a time, then allocate another block when the first gets used up, etc.

As far as I can tell, I need 3 data structures to accomplish this, but I'm hoping someone can recommend a simpler, more elegant method.

The three data structures I am thinking of are:

Binary tree
Stack (to store the preallocated nodes and easily find the next one to use)
Linked list (to store the different allocated node blocks so they can be located and freed eventually).

The way these would work is:

Initialization

Allocate one block of N nodes
Push each node in the block onto the Stack
Append block to Linked List.

Tree Insert

If stack is empty, allocate another block of N nodes, push them onto the Stack and append it to Linked List
Pop node from stack and store tree node data in it
Add node to tree structure, do balancing, etc

Tree Delete

Find item in tree and remove from tree
Push node back onto Stack to be used later for insert

Cleanup

Destroy tree
Traverse Linked List and delete all node blocks

Using a Stack to store all the preallocated nodes seems like a good idea, since insert/delete operations would be $O(1)$. However, each time a new block of N nodes needs to be allocated, I need to push them all onto the Stack $(O(N))$ and insert it into the Linked List $(O(1))$. Finally, cleanup at the end requires traversing the Linked List $(O(NB))$ where $NB$ is the number of node blocks allocated.

It seems to me I should able to do this with less complexity (maybe 2 data structures instead of 3). Does anyone know of a more elegant method?


texts: Is it a sufficient condition to be in NP?

texts:
Suppose the following situation.

You have a decision problem $D$.
You know that $SAT$ is $NP$-complete.
You know that $D\leq_p SAT$.

Can you conclude that $D\in NP$?
I think it's true because it means that $D$ is at least as hard as any other problem in $NP$.
As I know I am not able to post questions to answer with yes/no:
If it's true, can you give a better explanation? If it's false, can you argue why is so?
PD: it's not homework.


texts:
Steven Skiena's "Algorithm Design Manual" has the following code for the backtracking algorithm:
#include "backtrack.h"
#include "bool.h"

bool finished = FALSE;                  /* found all solutions yet? */

/*
  a[] is the array representing a partial solution.
  k is the integer representing the current position in a[].
  input is auxiliary data.
*/
backtrack(int a[], int k, data input)
{
        int c[MAXCANDIDATES];           /* candidates for next position */
        int ncandidates;                /* next position candidate count */
        int i;                          /* counter */

        if (is_a_solution(a,k,input))
                process_solution(a,k,input);
        else {
                k = k+1;
                construct_candidates(a,k,input,c,&ncandidates);
                for (i=0; i<ncandidates; i++) {
                        a[k] = c[i];
                        make_move(a,k,input);
                        backtrack(a,k,input);
                        if (finished) return;   /* terminate early */
                        unmake_move(a,k,input);
                }
        }
}

What is confusing me is the if-else: If is_a_solution is True, then the else code won't execute. But let's say we want to find all possible solutions. Then, even if you've found a solution a[0...k], wouldn't you want to continue extending the solution to see if more solutions exists down the solution tree? Essentially, why isn't the code like this:
         ...
         if (is_a_solution(a,k,input))
                process_solution(a,k,input);
         k = k+1;
         ...
```


texts: How to decompose into BCNF while preserving all functional dependencies

texts:
I have a relation R = {A,B,C} and F={AB -> C , C -> B}.
In order to check if R is in BCNF.

I checked if AB and C are both superkeys and since C is not a superkey I conclude R is not in BCNF.

After decomposing R into BCNF, I have two relations :

R1(C,B)   F1{ C -> B}
R2(A,C)   F2{ A -> C}

Now since A and C are both superkeys, I can conclude that now R(R1, R2) is in BCNF.

But after computing (F1 U F2)+, I can't derive AB -> C and so I lose that FD.

My question is, how can I decompose than into BCNF while preserving FD's?


texts: What ML methods exist to categorize signal from noise? Red noise? Spatially correlated noise?

texts:
Let's say we are given measurements of some sort.

In many cases, it is safe to assume that noise is white noise, serially uncorrelated, and zero mean with some finite variance.

But in other cases, "red noise" exists such that the noise is correlated in time. What does one do in this case? Perhaps a Gaussian Process could be used?

What methods exist to characterize spatially-correlated noise?


texts: Does big-Oh impose an ordered partition on the set of the "usual" functions?

texts:
The example in this answer proves the fact familiar to CS students - that the "big-O" is not a total order. However, most algorithm running times analyzed using big-Oh notation are not expressed in piecewise form like this example. In fact, most algorithms I am familiar with have a running time expressed in terms of polynomials, exponentiations and logs.
Consider the recursively defined class of functions which includes $f(n) = c$ for any constant $c$, $f(n) = n$, and any functions of the form $f + g, f \cdot g, \log(f), \exp(f)$ where $f,g$ are in the class. Does $O$ impose an ordered partition on this class of functions? The functions with the same big-$O$ growth is in the same part.
Here are my thoughts:
Note that specifying $f \cdot g$ is actually redundant, since $f \cdot g = \exp(\log(f) + \log(g))$. Since the functions are inductively defined, perhaps there is an inductive proof.


texts: For a given certain situation how to prove that the system will never get into the state of Deadlock

texts:
The situation is as follows

  'm' process shares 'n' resources of same type. The maximum need of
  each process does not exceed 'n' and the sum all their maximum needs
  is always less than m+n. In this set up will deadlock ever occur

This is a question from Operating System Concepts by Silberschatz, Gagne and Galvin.

I tried to prove this using using Banker's Algorithm. Initially, I assumed that the Allocated Matrix for 'm' processes is a zero matrix. And Maximum Matrix of 'm' process is 'n'. Since Need matrix is difference of Allocated Matrix and Max Matrix therefore, Need Martix is equilavent of Maximum Matrix. And at last Available Matrix is equal to 'n'.

At this point I feel stuck and not able to find a way to proceed. Looking forward for help from you guys.
Thanks in advance.


texts: Context Free Grammar $L = \{a^i(b+c)^jd^k | i0\}$

texts:
I'm trying to design a CFG that accept the words of the following language:

$$L = \{a^i(b+c)^jd^k  \mid  i<j+k; \quad  i,j,k>0\}$$

My first approximation would be to do $i = j+k$ as something like:

$S\to aSd \mid X$

$X\to aXY \mid aY $

$Y\to b \mid c$

But then I don't know how to make the jump to the $<$.


texts: In the Gas-Up problem, how is the amount of gas the same up to a cyclic shift regardless of starting city?

texts:
I'm working through Elements of Programming Interviews as practice for finding a job. I've spent a ridiculous amount of time on Problem 18.7.

  In the gas-up problem, $n$ cities are arranged on a circular road. You
  need to visit all of the $n$ cities and come back to the starting
  city. A certain amount of gas is available at each city. The total
  amount of gas is equal to the amount of gas required to go around the
  road once. Your gas tank has unlimited capacity. Call a city $c$
  ample if you can begin at $c$ with an empty tank, refill at it, then travel through each of the remaining cities, refilling at each, and
  return to $c$, without running out of gas at any point. See Figure
  18.3 for an example. [You can see Figure 18.3 on the Google Books result if you search for "Elements of Programming Interviews Problem
  18.7.]

  Given an instance of the gas-up problem, how would you efficiently [i.e. in $\mathcal{O}(n)$ time or better]
  compute an ample city, if one exists?

I couldn't figure it out. I read the hint, and I still couldn't figure it out. I gave up, and read the answer in the back of the book. I still couldn't figure it out. I searched Google and this site for a more complete solution, but didn't find one.

This is the part that's getting me:

  On closer inspection, it becomes apparent that the graph of the amount
  of gas as we perform the traversal is the same up to a cyclic shift
  regardless of the starting city.

I must not be inspecting closely enough, because this is not apparent to me at all. I tried calculating the remaining gas at each city during a traversal of an example circuit, starting at different cities (and permitting the number to be negative when necessary, as the solution suggests). There does not seem to be any relation between the series of numbers I get when starting at different cities. I understand, if we accept that the amount of gas remaining at each city is the same up to a cyclic shift, how the algorithm the solution gives would solve the problem. I cannot see how this is the case. What am I missing?


texts: What is wrong with this conditional proof of P=NP?

texts:
I have recently thought up the following proof that L=P implies P=NP.

  Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be verified in polynomial time. Since P=L, the same solution can be verified in logarithmic space. Thus NP=NL. But then NL is contained in P, which means that NP is contained in P and therefore P=NP.

By the efficient market hypothesis, I suspect this proof is flawed. I am however unable to determine the exact nature of the error. Can someone point it out?


texts: Prove Queue Automaton is equivalent to Turing Machine

texts:
A deterministic queue automaton (DQA) is like a PDA except the stack is replaced by a queue. A queue is a tape allowing symbols to be written (push) on the left-end and read (pull) on the right-end.

Actually I've proved that a 2-tape Turing Machine can simulate the DQA. Now I'm proving the DQA can simulate Turing Machine TM. Let the queue store all the input and the right-end symbol is the one being read. Suppose $a$ is the right-end symbol in the queue.

For the transition $\delta(q,a)=(r,b,L)$ in TM, it's easy to simulate. Just pull $a$ and push $b$. Now the right-end symbol would be the symbol on the left of $a$. It's like move the head in TM to the left.

My problem is I cannot find a way to simulate the transition $\delta(q,a)=(r,b,R)$. Since the symbol on the right of $a$ is actually the left-end symbol, how can I let this symbol move to the right-end? I spend several hours on this and I think answers on Internet are not very clear. Could anyone give me some hint?


texts: how did the authors of the AKS-Paper come up with the upper bound for r? and what does the multiplicative order have to do with anything?

texts:
I have been recently reading the paper "PRIMES is in P", but unfortunately a lot the steps were skipped, which led to confusion. My main problem is with the upper bound on r which was not explained at all in the paper(i don't see the connection of these bounds to the runtime of the algorithm), for example how did they come up with the upper bound O(log^5 n) for r, why is it exactly this number? why not O(log^2 n) or something else. Moreover they had set a condition for r in the second step of the algorithm. They wanted the order of r mod n to be greater than log^2 n, but i don't see why this has anything to do with polynomial runtime or why does it have to be greater than log^2 n.

Can anyone please explain why this is true? or how to derive these numbers?


texts: Upper bound derivation of expected time for finding a large cut

texts:
Given an undirected graph $G$ with $n$ vertices and $m$ edges, we build a cut as following. Initially sets (of vertices) $A$ and $B$ are empty. For each vertex $v$ we flip a fair coin and according to outcome we put $v$ either in $A$ or $B$.

Let $X$ be a r.v. denoting the cut size, i.e. the number of edges between sets $A$ and $B$. A simple calculation produces $$E[X] = \frac{m}{2}$$
(see Probability and Computing by M.Mitzenmacher & E. Upfal, pg 130).

Now, let $p = \Pr\left(X \geq \frac{m}{2}\right)$. Then
$$ \frac{m}{2} = E[X] = \sum_{i \leq m/2 -1}{i\Pr(X=i)} + \sum_{i \geq m/2}{i\Pr(X=i)}$$
$$ \leq (1-p)\left(\frac{m}{2}-1 \right) + pm.$$

I understand that for $i < m/2 -1$, $\Pr(X=i) \leq \Pr(X < m/2)$ and for $i \geq m/2$, $\Pr(X=i) \leq \Pr(X \geq m/2)$, but I don't understand how the last upper bound is derived.

Can anyone give me a hint or explain the derivation?


texts:
Suppose that we have a hash table of some size $s$ and we have a set of keys $K$. We decide to hash the keys using chaining.

Now assume that we randomly select $k \in \mathbb{N}$ keys from $K$ and hash them. Next, we perform the search operation for one of those keys.

My question is: is it true that this operation can take $O(k)$ time? Because, if we are very unlucky, it may happen that we hashed all keys to the same cell in the hash table, and then the key that we decide to search for is exactly the key that was hashed last?


texts: P/NP - Polynomial Reduction vs Certificate

texts:
I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate.

How I understand polynomial reduction is that you can use it to show that:

Problem A is in P if:

B is in P and you can reduce A to B in polynomial time -> A $\leq_p$ B

Problem A is in NP if:

B is in NP and you can reduce B to A in polynomial time -> B $\leq_p$ A

Then I read about certificates and this is how I understand the basic Idea/Components behind it:

Problem: Problem to solve
Certificate: possible solution
Certifier: Checks if the Certificate is correct

What I don't understand is:

What do you want to show with solution that uses a certificate?
When do you use one over the other ?


texts:
I was selected for a UG interview and the following was one of the questions asked:

"Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the
interviewer) have hidden a treasure which you have to find by asking
questions to me. The questions are to be of the form - "Is it under
this $n \times n$ square (where $n \le 8$)?" For each question, I
charge you some money and you have a finite amount with you. What is
the least number of questions that you can ask to find where the
treasure is?

I don't have any background in high school computer science and while discussing this problem with a senior, I discovered that the problem relates to "complexity" in computer science. Can somebody help me with this as a beginner?


texts: Space complexity for storing integers in Python

texts:
So I was watching this mock interview by an Airbnb engineer on interviewing.io (https://youtu.be/cdCeU8DJvPM?t=1224) and around ~20:11 seconds he raises an interesting point.

The question that the interviewee was trying to solve was -

Array 1 has all unique integers.
Array 2 has the same integers as array 1, except one integer missing.
The code has to find that missing integer.

The interviewee suggested we can just subtract the sum of the second array from that of the first array and that'd give us the missing integer, and since these are just sums (integers), they'd take O(1) space. But the interviewer then said it's not actually constant since a sufficiently large sum can take more space than a smaller sum.

While that is true, and I double-checked it, via -

In [1]: import sys

In [2]: sys.getsizeof(90)
Out[2]: 24

In [3]: sys.getsizeof(9000000000000000000000000000000000)
Out[3]: 40

what complexity is it then?

Is saying constant space complexity for these algorithms wrong then?


texts: When is the output of shortest path $\subset$ MST?

texts:
I was wondering if the output of an algorithm like Dijkstra was always contained in the minimal spanning tree, however, a counter example to this claim are cyclic graphs like:

The shortest path $B \rightarrow C$ is in no way contained in the MST. Are there known conditions on the graph and the edge weights that ensure that all vertex-to-vertex shortest paths are contained in the minimum spanning tree?


texts: Is there a name for doing a running total that is actually just the total of subsets?

texts:
There's a concept I've used frequently where I create an O(n) operation for finding the sum of all subsets ai...ai+L where L is the length of a subset.

  i ← 0
  j ← i - length of subsets
  subsetTotal ← 0

  while i < length of a
    subsetTotal ← subsetTotal + ai

    if j ≥ 0
      Save subsetTotal to a collection
      subsetTotal ← subsetTotal - aj

    i ← i + 1
    j ← j + 1

I know that using a O(n) loop to find the total of an entire set is known as a "running total," but what do you call that total for an O(n) operation finding the sums of subsets?

What is the term for subsetTotal in the above psuedocode?


texts: Is it decidable whether a Turing machine modifies the tape, on a particular input?

texts:
Is $L=\{\langle M,w \rangle|M\text{ does not modify the tape on input w}\}$ decidable?

We could tell if a TM does not modify the tape on any input by checking if there are no transitions in $M$ that write on the tape, but can it be decided for a given $w$?


texts:
I want to write an algorithm to find the closest pair of points among n points in an XY-plane. I have the following approach in my mind:

Find the minimum x co-ordinate(minX) and minimum y(minY) co-ordinate.
Name the point origin= (minX,minY)
Find the distance of all points from this origin and store it in a vector dist[].
Sort the vector dist[].
Traverse through the vector dist and for each i=1 to n-1, do dist[i+1]-dist[i] and keep track of the minimum of these and the pair that form this minimum.
Return minimum and the pair.

I am not sure if this algorithm would work because of how triangle inequality works.

Any help on why this algorithm should/should not work?


texts: How would you implement truly random hash functions in practice?

texts:
Suppose that $[U] = [0,...,U-1]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$.

A hash function $h:[U]\rightarrow[m]$ is truly random if

For any set of distincts elements $\{x_{1},...,x_{k}\} \subseteq [U]$ and any set of values $u_{1},...,u_{k} \subseteq [m]$ we have $Pr_{h}[h(x_{1}) = u_{1} \wedge ... \wedge h(x_{k}) = u_{k}] = \frac{1}{m^{k}}$. This of course implies  that $h(x_{i})$ is uniform random and independent of $h(x_{1}),...,h(x_{i-1}),h(x_{i+1}),...,h(x_{k})$.

I was trying to understand why this is not possible to implement efficiently in practice, and found this paper where at some point they write in the abstract:

  Hashing is fundamental to many algorithms and data structures widely
  used in practice. For theoretical analysis of hashing, there have been
  two main approaches. First, one can assume that the hash function is
  truly random, mapping each data item independently and uniformly to
  the range. This idealized model is unrealistic because a truly random
  hash function requires an exponential number of bits to describe.

I do not see how using exponential number of bits can help us come up with a truly random hash function when the universe is $[U]$ and the hash table can store at most $m$ elements.

How would you use an exponential number of bits to come up with a function that can guarantee the probabilities described above?


texts: What is the most efficient constant-space sorting algorithm?

texts:
I'm looking for a sorting algorithm for int arrays that doesn't allocate any byte other than the size of the array, and is limited to two instructions:

SWAP: swap the next index with the current one;
MOVE: moves the cursor to +1 or -1 index;

That is, you can't swap non neighboring indexes, nor swap the index 100, after you just swapped index 10. What is the most efficient algorithm - i.e., the one that uses the less amount of total moves?


texts: Computer Vision - What is spatial histogram/pyramid feature?

texts:
I am trying to re-implement the model in this paper https://arxiv.org/pdf/1511.02917v2.pdf. But the paper omitted some details in feature extraction (Section 4.1). I am new to computer vision so I am confused when the paper just said they got the spatial feature (1440 dimensional) that corresponds to a 32*32 spatial histogram, combined with a spatial pyramid, to indicate the bounding box location at multiple scales.

I guess a 32*32 spatial histogram is to divide the image into 32*32 regions and concatenate histogram for each small region together? But what does it mean to combine with a spatial pyramid, and how to end up with a 1440 dimensional spatial features.


texts: How to model a logical indicator when two inequalities hold in Integer Programming?

texts:
I have an IP program where $\forall i \in I, j \in J$ my decision variables are $x_{i,j}$. I have two sets of inequalities (one inequality for every $i,j$ pair) that are of interest which are $$a_{i,j} x_{i,j} \geq 1 \ \ \ \ \forall i \in I, j\in J$$ and $$ \sum_{j \in J} b_{i,j}x_{i,j} \leq b_{i,j}- 1 \ \ \ \ \forall i \in I, j\in J$$

I now want to introduce a logical indicator variable $\delta_{i,j}$ which equals 1 if and only if both of the inequalities are true and 0 else.
How could I implement this idea by introducing appropriate constraints for my Integer Progamming model?
I was thinking about defining a variable $\delta^1_{i,j}$ and $\delta^2_{i,j}$ which equals 1 iff the first and second inequality are true respectively and then maybe combine these two auxiliry logical variables into a single variable $\delta_{i,j}$, but I couldn't figure out exactly how to make this work.


texts: High Level Explanation of the Pumping Lemma

texts:
I have a problem that I cannot figure out regarding using the pumping lemma to prove that a language is not regular. I don't understand how I go about proving through contradiction that the language is not regular.

When I read about the pumping lemma, all I am finding are complicated explanations involving $x$, $y$, $z$ and $m$ which seems difficult to understand.

I would appreciate if someone could provide a high level overview of the pumping lemma, and possible an example of proving a language is not regular with its use.


texts:
I'm trying to prove or disprove that $\log^{k}(n) \in O(\sqrt{n}), \ \forall k > 0$. By using the free version of wolfram and testing some increasing values of $k$ I get that:

$$\lim_{n \rightarrow \infty} \frac{\log^{k}(n)}{\sqrt{n}} = 0$$

And apparently $\log^{k}(n) \in O(\sqrt{n})$, but by trying to solve this limit on paper in order to reach an appropriate proof I would need to keep applying L'Hospital rule indefinitely. Is that what I suppose to be doing? How could I proceed to build this proof?


texts:
I've been writing codes to solve a standard partition problem. I've investigated brute force, greedy, Karmarkar-Karp and complete Karmarkar-Karp algorithms.

  Standard partition problem: divding a set into two subsets such that the difference between the
  sums of the subsets is minimized.

I'm also looking at a non-standard partition problem (this is my terminology)

  Non-standard partition problem: divding a set into two subsets such that an arbitrary function of
  the sums of the subsets is minimized. In this case, furthermore, the set needn't be a set of reals, it could be e.g. a set of vectors.

In the special case in which the arbitrary function is $f(\sum_1, \sum_2)=|\sum_1- \sum_2|$, where $\sum_1$ is sum of subset one etc, the non-standard problem reduces to the standard problem.

At the moment, I can trivially generalise brute force and a greedy algorithm to the non-standard case. The former is slow and the latter incomplete and often poor, however.

Is there a better algorithm for this problem? I'm interested in complete and incomplete algorithms. Or is the problem just too general?

What if I make it even more general by permitting $f(s_1, s_2)$ to be minimised where $s$ denotes a subset, i.e. an arbitrary function of the subsets rather than the subsums.


texts: Algorithm undirected graph to directed strongly connected graph

texts: For an undirected connected graph $G=(V,E)$ given as adjacency list I want to find a directed strongly connected graph $G=(V,E')$ where each $e' \in E'$ is either $(u,v)$ or $(v,u)$ if we look at its original $e=\{u,v\}$. Also we're assuming  there are no bridges in the given graph G (which I'm checking before hand).


texts:
Possible Duplicate:
  Runtime of the binary-GCD state machine

Hello I am doing self study from MIT OCW exercises and I could not understand this question. Can anyone explain me,

First, why does this state machine assume it halves the $(max(a,b))$ at every two transitions beacuse we can follow steps 4 and 7 and one extra step to halve the $(max(a,b))$, which is more than 2 transitions/steps. I know it is not a common case but a case is a case unless proved.
Next I dont see where an extra 3 comes from in $3+2log(max(a,b))$

Question:
The binary-GCD state machine computes the GCD of a and b using only division
by 2 and subtraction, which makes it run very efficiently on hardware that uses binary
representation of numbers. In practice, it runs more quickly than the Euclidean
algorithm state machine.

Prove that the machine reaches a final state in at most $3+2log(max(a,b))$
transitions.

Hint: Strong induction on $max(a,b)$

states: $\mathbb{N}^3$

start state: $(a,b,1)$, where $a >b>0$

transitions: if $min(x,y) >0$, then $(x,y,e) \rightarrow $

the first possible state according to rules

1- $(1,0,ex)$ if $(x=y)$

2- $(1,0,e)$ if $(y=1)$

3- $(x/2,y/2,2e)$ if $(2|x \ and \ 2|y)$

4- $(y,x,e)$ if $(y>x)$

5- $(x,y/2,e)$ if $(2|y)$

6- $(x/2,y,e)$ if $(2|x)$

7- $(x-y,y,e)$ if $(otherwise)$


texts:
I don't know what this problem is called, so I haven't been able to Google for it, but I have a graph problem that I feel must have been solved many times before, and I just cannot find a good solution.
Given a directed graph, and nodes A and B, I want to find a route that takes me from A to B and back to A again, going through the fewest number of nodes. I have attempted to solve it with various versions of the shortest path problem, but it doesn't get me there. There could be a short path [A]->[1]->[2]->[B] from A to B, and one [B]->[3]->[4]->[A], that I can stitch together to get a tour that visits four nodes besides A an B (the nodes 1, 2, 3, and 4). But there might also be longer paths, [A]->[x]->[y]->[z]->[B] and [B]->[z]->[y]->[x]->[A] that ends up only visiting three nodes, because the paths overlap.
If I try to use a standard shortest-path approach, my thinking was to conceptually double the graph, so edges out of B would go into a copy of the graph, and look for the shortest path from A to A' where A' is the copy of node A. That gives me a shortest path cycle, but if I visit the same node going from B to A as I do going from A to B, then it counts as much as visiting a new node, where it should be free. The cost of visiting a node in the "copied" graph depends on the path I took in the first graph, and if I start carrying that information with me, the heap I use for finding the shortest path has to remember not only a node but a path. The state-space explodes, and so does the running time.
I am not convinced that this is something that has an efficient solution, and I might be able to brute-force something with a branch-and-bound approach that does track paths, changing the scoring of nodes in the "copied" graph. But before I start thinking along that path (no pun intended), I would like to know that I am not missing something trivial and that the problem has an efficient solution.
I would greatly appreciate any pointers to how to attack this problem, or just confirmation that it might be a problem that doesn't have an efficient solution, so I can give up on trying to find one.


texts: What is a proof of normalization of Morte?

texts: It is said that any term on the calculus of construction halts. I am studying it through  Morte, which is a bare bone implementation of the coc available on github. Is there any simple proof of normalization for the calculus of constructions? If the proof isn't simple, is there an simple intuition behind the result?


texts:
Is there anything interesting to say about an "almost BST" with directed edges?
Is there a domain where this structure naturally arises? I'm imagining a tree like the one below, but it would of course be more interesting if the tree were deeper with just a few of these strange edges.

I found this article on circuit rank which uses the term "almost tree", but it talks about circuits in undirected and directed graphs. What I'm describing is not a cycle.


texts: Is this context-free grammar correct for this regular expression?

texts:
I have created a context-free grammar

$$
\begin{align*}
&S \to S_1 \mid S_2 \\
&S_1 \to aS_3bS_4 \mid \epsilon \\
&S_2 \to bS_4 \\
&S_3 \to aS_3 \mid \epsilon \\
&S_4 \to aS_4 \mid bS_4 \mid \epsilon
\end{align*}
$$

for this regular expression

$ (aa^*b(a \cup b)^*) \cup (b(a \cup b)^*) $

Is the grammar correct or am I missing a certain route?


texts: Modification of dynamic programming for a knapsack problem

texts:
We have the following recursive function for the dynamic programming problem for a knapsack problem:

\begin{align}
V(i,w)=&max[ V(i-1,w), v_i +V(i-1,w-w_i)], \quad 1\leq i \leq n, 0\leq w \leq W \\
\end{align}
and $V(0,w)=0$.

But is it possible to add a constraint on the items to this function? If we for instance only are allowed to put one of the items 1 or 2 in: $x_1 + x_2 \leq 1$? And how to do this?


texts: NFA that accepts binary strings starting with 1 and with at least 01, or at least 010, or both

texts:
Im not sure if I am understanding this question correctly. Its a problem without a solution in my text.

Starting with 1, and at least 01 or at least 010 or both these substrings.....
So a regular expression will be given by:
$1(0+1)^*01010(0+1)^* + 1(0+1)^*01001(0+1)^* + 1(0+1)^*010(0+1)^* +  1(0+1)^*01(0+1)^* = M$

But then surely $M = 1(0+1)^*01(0+1)^*$ ???

And then the NFA can simply be drawn as a three state NFA with starting state joined by edge $"1"$ to state B then joined by edge 01 to final state. And obviously there will be $0,1$ loops on state B and the final state?

Did I miss something? Perhaps the both implies it should be $M = 1(0+1)^*01010(0+1)^* + 1(0+1)^*01001(0+1)^* $

Do i need join state B with edges $"01","010","01010" and"01001"$ to the final state?

I would draw the graph but I cant find out how to do such things here. Its only a 3 state NFA regardless of the edges. I know that much :)

I think im getting confused with these "or" parts of the question.


texts: Resolution when clauses contain more than 1 complementary literals

texts:
Let's assume that we have clauses $(l_1 \lor l_2 \lor l_3), (\neg l_1 \lor \neg l_2 \lor l_4), (l_1 \lor l_2 \lor l_5), (\neg l_1 \lor \neg l_2 \lor l_6)$, where both $l_1$ and $l_2$ are complementary literals for the clauses.

If we apply the resolution technique for $l_1$ we'll get clauses

$(l_2 \lor \neg l_2 \lor l_3 \lor l_4)$,
$(l_2 \lor \neg l_2 \lor l_3 \lor l_6)$,
$(l_2 \lor \neg l_2 \lor l_5 \lor l_4)$,
$(l_2 \lor \neg l_2 \lor l_5 \lor l_6)$

How to proceed with $l_2$ from here?


texts: Consider a t-resilient read-write shared memory system (0 < t < N) with initial failures only: faulty processes take no steps. How could one give a consensus algorithm in this system? I don't understand why the proof of the consensus impossibility doesn't work in this case?


texts:
Given a set of vectors, lets say that each coordinate is populated from an alphabet (meaning set of symbols, numbers, etc) (particular or shared alphabets are indistinct).

Is there any standard procedure for performing the following task ?

Look for sets of positions that "make the same choice" in several vectors.

That means: a subset of indices where, when we project to just those indices, there's some value that's taken on by many of the vectors.

An example:

Input
[0,-,0]
[0,+,+]
[+,+,+]
[0,0,0]
[-,+,+]

Output

2 coordinates involved ( 2 and 3), appearing in 3 vectors: x2=+ and x3=+
1 coordinate involved (1), appearing in 2 vectors:  x1=0


texts: Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own

texts:
I had an online round at a company where I was asked this question.
There are $N$ items, and you have to choose some items from them such that the total weight does not exceed $W$.
Each item has three properties, weight, profit and type. There are only two types of objects.
Type 0 item can be selected independently own their own.
A type 1 item cannot the selected on its own and needs another item of type 1.

Note: The problem does not say if this means what we have to select at least two type 1 items to select any at all, or that all the type 1 items must be in pairs.

Constraints:

$N < 10^3$

$W < 10^5$

$\mathit{weight}, \mathit{profit} < 10^5$

This is obviously (?) related to the knapsack problem, as without the restriction on the type 1 objects, it would actually be the 0-1 knapsack problem. How do I go about doing this? Any help and general ideas are extremely appreciated.


texts: Finding lowest "pass" between two points on a map?

texts:
(I expect that the hard part of this question is getting the right language for the problem.  My attempts at searching for an answer didn't get anything useful, which suggests to me that whatever they are, I'm not using them!)

Consider a map where each x,y coordinate has an associated "height" value.  If we have two points (each of which is at a local minimum height) on this map, we can consider the set of all possible paths between those two points.  Each path has a maximum height along the path; call this the "pass height" of the path.  I'm interested in the minimum value of the pass height over the set of possible paths.

I'm calling this a "lowest pass", because in real maps, these paths with minimum height are the passes through the mountains.

What is an algorithm that will allow me to determine this minimum pass height?  I'd be happy either with an algorithm that assumes a discrete grid of finitely-spaced points, or an algorithm that approximates the solution on a continuous surface with numerical iteration of some sort.

I'd also particularly like a solution that will work in a high-dimensional space, but one in 2-space would be a good start.


texts: Question on the definition of computable function and non-terminating behaviour

texts:
For example on wikipedia a function $f : \mathbb N^k \to \mathbb N$ is defined to be computable, if there exists an algorithm (in form of a Turing machine, as an $\mu$-recursive function or maybe a C++ programm) such that the following holds:

If $f(x)$ is defined, then the program will terminate on the input $x$ with the value $f(x)$ stored in the computer memory
If $f(x)$ is undefined, then the program never terminates on the input x.

My question concerns the second item, the requirement that for elements $x \notin \operatorname{dom}(f)$ we require the program to end up in an endless loop. But more natural to me would be simply to leave the behaviour unspecified in this case (i.e. just require item 1).

Like for example consider the following quite artificial function:
$$
 f(n) := \left\{ \begin{array}{ll}
  n^2 & \mbox{ if } n \equiv 0 \pmod{2} \\
  \mbox{undefined} & \mbox{ otherwise }.
 \end{array}\right.
$$
Then intuitively I would say some programming squaring its argument would compute $f : \mathbb N \to \mathbb N$, but not to the above definition as this programm would also give a result on all $n \notin \operatorname{dom}(f)$.

From a theoretical point of view this could be fixed if $\mbox{dom}(f)$
is decidable (or semi-decidable, in which case the infinite loop would be given by definition that each query $x \in \operatorname{dom}(f)$ should end up in an infinite loop by the definition of semi-decidable), as we simply
query if the argument is in $\operatorname{dom}(f)$, and if yes proceed with our algorithm, and if not just enter some idle endless loop.

From another point of view discarding item two above would be easier in proofs, as the case if $f(x)$ is undefined does not needs to be considered. But I can image that someone wants a relationship that the algorithms terminates exactly if $f$ is defined. But does this makes any difference? What would be lost if we just use item one above as the defintion of computability, i.e. $f : \mathbb N^k \to \mathbb N$ is computable, iff there exists an algorithm that computes the correct result if $f(x)$ is defined.


texts: Triangle mesh surface area after affine transformation

texts:
Let $\mathbb{M}$ be the set of all 3D triangle meshes.

Let $a:\mathbb{M} \rightarrow \mathbb{R}$ be a function that computes surface area of the mesh.

Let $\mathbb{T}$ be the set of 3D affine transformation matrices.

Let $t:\mathbb{M} \times \mathbb{T} \rightarrow \mathbb{M}$ be a function that transforms mesh $M$ with matrix $T$.

Let $\mathbb{C}$ be a set of values of unknown (at the moment) structure, with the following properties:

There is a function $c:\mathbb{M} \rightarrow \mathbb{C}$ that maps meshes to these values.
There is a function $a:\mathbb{C} \rightarrow \mathbb{R}$, such that $(\forall M \in \mathbb{M})(a(c(M)) = a(M))$, i.e. computes surface area of the mesh indirectly, via first mapping it to $\mathbb{C}$.
There is a function $t:\mathbb{C} \times \mathbb{T} \rightarrow \mathbb{C}$ such that $(\forall M \in \mathbb{M})(\forall T \in \mathbb{T})(t(c(M), T) = c(t(M, T)))$, i.e. $C$s can be transformed with the same effect on computed surface area as if transformation was applied to the mesh itself.

So, is there such $\mathbb{C}$? Obviously I don't want $\mathbb{C} = \mathbb{M}$, and prefer $a(C)$ and $t(C)$ to be of constant asymptotic complexity with respect to amount of triangles in the mesh.


texts:
I am attempting to understand the growth of the following algorithm, which is described as $n^2$ growth in the book I am reading:

"... performs of the order of $n^2$ steps on a sequence of length $n$."

Could someone please explain how this is calculated in the following code, which is also taken from the book?

If I print out the statements when the lines are executed, it first executes $n$ steps, then decreases $n-1$ steps for each loop iteration until it reaches $0$. This does not seem like exponential growth to me. Why does this grow at $n^2$?

dataset = [3,1,2,7,5]
product = 0

# algorithm begins here
for i in range(len(dataset)):
  for j in range(i + 1, len(dataset)):
    product = max(product, dataset[i]* dataset[j])


texts:
Ranked alphabet is very often used in Ranked Trees definition, like here for instance. In that example for given set $\Sigma=\{a,b,c\}$ ranks assigned by arity function $ar : \Sigma\rightarrow\mathcal{N}$ as:

$ar(a)=2, ar(b)=2, ar(c)=1$.

And Ranked Tree over $\Sigma$ is defined as:

$T_{\Sigma_r}$, the set of ranked trees, is the smallest set of terms $f(t_1,\dots,t_k)$ such that: $f\in\Sigma_r$, $k = ar(f)$, and $t_i\in T_{\Sigma_r}$ for all $1\leq i\leq k$.

The tree in this example looks like:

       b
     /   \
    a     b
   / \   / \
  b   c c   c
 / \
c   c

But what about trees like that?

       b
     /   \
    a     b
   / \   / \
  b   c c   c
  |   |
  c   a

This is also valid tree, but it is obviously is unranked.

My question: do any research regarding unranked alphabet trees exist?

What I've found so far is related only to logic for unranked trees.


texts: Negative weight cycle vs maximum weight cycle

texts:
I'm having trouble understanding why it's easy to detect negative-weight cycles (Bellman Ford) but hard to find the maximum weight cycle in an undirected graph.

If we negate the weight of each edge, we can easily find if there are any cycles with total weight > 0. However it must not be easy to find if there are any cycles with weight > 1 or else we could repeat with 2, 3, 4 etc until the answer is no.

Is this correct? Why is it so much harder to detect if there exists a cycle with weight > 1 then to find if there is a cycle with weight > 0?


texts: reduction from 3-SAT to Subset Sum problem

texts: How to reduce 3-SAT to subset sum problem?


texts: What are these notations O(1)/O(n)/O(log n)?

texts: I am a newbie here I recently read tutorials on java about collection framework. The time complexity of various objects in reading/writing data What does it mean? what is O notations? can anyone make me understand these notations and about time complexity measures using these notations


texts: How to prove the language of Turing machines that run at most $4|x|^2$ steps is not recursive?

texts:
I am trying to prove that the language

$$ L=\{M\mid M\text{ is a TM and for all }x\in \Sigma^*\text{ with }|x|>2, M\text{ on }x\text{ runs at most }4|x|^2\text{ steps}\} $$

belongs to Co-RE but not R.

Showing $\overline{L}\in$ RE is pretty much straightforward, but I also want to show that $L\notin$ R.

My idea was a reduction $\overline{H_{\text{TM}}}\le_mL$ but I struggle to figure out how to do it.

Any help/guidance will be much appreciated.


texts: Give a DFSA that accepts $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$ using as few states as possible

texts:
Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$.

Using as few states as possible, give a DFSA that accepts $L_1$.

Also give an appropriate state invariant for your DFSA.

I have a regex for it and that is $1^*(00^*11^*00^*11^*00^*11^*)1^*$.

An example of accepted strings are: 100111010001. Example of a rejected string is 01010101, since |01010101| $= 4 \mod 3 = 1 \neq 0$.

How would I draw it? Also do I come up with state invariant first or draw the dfsa first? I drew the dfsa first right now

100111010001 - gets accepted. However 01010101 also gets accepted when it should be rejected. Not sure how to limit it to just mod 3

Edit:

I believe this works. (I cant use regexes in state invariants)

$q_0$: $x$ must contain only $1$'s

$q_1$: $x$ contains 1's before any 0's and ends with a 0

..

not sure how to write the state invariant for this case


texts: Upper (or lower) envelope of some linear functions

texts:
Given some single variable linear functions $y_1=m_1x+b_1$, $y_2=m_2x+b_2$, $\ldots$, $y_n=m_nx+b_n$, the upper envelope is the function $f(x)= \max \{y_1, \ldots, y_n\}$. We know that this function is a convex piecewise linear function characterized by its breakpoints, where the slope of the function changes.  I know there exists an algorithm with  $O(n \log(n))$ complexity to find the breakpoints.
https://www.sciencedirect.com/science/article/pii/0020019089901361

Question: Can the complexity be reduced if  $m_i \geq 0$ for all $i$.


texts: Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works

texts:
I'm still a beginner in the quantum aspect of computer science (self-studying). So please bear with me if this may sound like a stupid question.

I know Hadamard gate transforms qubit into a superposition state with $\frac{1}{2}$ chance that the outcome would be 0 or 1 when the wave function collapses:

$$\frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} \text{ for }\left|0\right\rangle \\
\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} \text{ for }\left|1\right\rangle$$

For already-in-a-superposition qubit, it would be just some linear transformation.

$$\alpha\left|0\right\rangle + \beta\left|1\right\rangle \rightarrow \alpha \frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} + \beta \frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} = \frac{\alpha+\beta}{\sqrt2}\left|0\right\rangle + \frac{\alpha-\beta}{\sqrt2}\left|1\right\rangle $$

But I got really confused when I see the $\Sigma \left|x\right\rangle$ in the equation on the Wikipedia article about Deutsch–Jozsa algorithm.

  A Hadamard transformation is applied to each bit to obtain the state

Why is it doing a summation with a ever-increasing value of $x$? My understanding of a qubit is that it can only be in either $\left|0\right\rangle$, $\left|1\right\rangle$ or a superposition state.

What the equation is doing above appears to indicate that if $n$ is 2, we would get

$$\frac{1}{\sqrt{2^{3}}} \left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} \left|2\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} \left|3\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$

How do I make sense of the $\left|2\right\rangle$ and $\left|3\right\rangle$?

[Update]

As I was writing the question, I remembered that qubits in the state of $\left|1\right\rangle$$\left|0\right\rangle$ are often expressed as $\left|10\right\rangle$. Since we are working with two-state system here I figured out that the 2 and 3 should be converted into binary in this context. And therefore the expression should be interpreted as

$$\frac{1}{\sqrt{2^{3}}} (\left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}(\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} (\left|10\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} (\left|11\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$

It appears that things are making a lot more sense now. But as I take a deeper look into the expression above, two questions come to me:

Why do I see so many $\left|0\right\rangle - \left|1\right\rangle$ but not a single $\left|0\right\rangle + \left|1\right\rangle$ ? (Intuitively I expect to see just one $\left|0\right\rangle - \left|1\right\rangle$ since we can only get $\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2}$ when it is in the state of $ \left|1\right\rangle$ and there is only one qubit in $ \left|1\right\rangle$).
Why are there only $2^{n}$ possible states with each having the chance of $(\sqrt{2^{3}})^2$ when the input is $2^n+1$ qubits? Adding four $(\sqrt{2^{3}})^2$ together doesn't give us 1.


texts: MST - algorithm to add an edge to the graph

texts:
I have some difficulty proving the correctness of my solution to the following exercise. Let $G = (V,E)$ undirected connected graph, $w \colon E \to \mathbb{R}$ weight function. Let $T$ a MST (minimum spanning tree) of $G$. Now, we add a new edge $e'$ to $E$ with weight $w(e')$. Find an algorithm that updates $T$ so it will be a MST of the new graph $G' = (V,E \cup \{e'\})$. The time complexity of the algorithm should be $O(V+E)$.

Intuitively, the algorithm is quite simple: add $e'$ to $T$, and then we got one cycle closed. Remove the edge with maximal weight from this cycle, and obtain a MST of $G'$.

However, I had some difficulties prove the correctness of this algorithm formally, and would appriciate some help.

BTW. I have read this post: If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST? but unfortunately haven't fully got the proof there.

Update: I tried Steven's solution and it helped me a lot, thanks again. I also found this solution online (I add a picture), but didn't understand it well. I also don't understand why in this solution, $T'$ is the MST on $G'$ instead of a MST on $G'$. Can someone help me understand what is going on the proof there, please?


texts: Hashing by doing modulo $m$ for $m=p^2$ for a prime $p$ instead of using a prime $m$ - is it that bad?

texts:
I am doing an exercise from a Big Data course I'm taking on Coursera (this exercise is for experimenting with a big-data problem and is not for any credit or homework) , the assignment was described briefly:

  Your task is to quickly find the number of pairs of sentences that are at the word-level edit distance at most 1. Two sentences S1 and S2 they are at edit distance 1 if S1 can be transformed to S2 by: adding, removing or substituting a single word.

I am then given a large txt file that contains about $10^6$ sentences.

The way I tried to attack this problem:

Observation $1$: If the length of two sentences is greater then $1$ then they are not at an edit distance $1$.

Observation $2$: Let $A_1,...,A_5$ be five consecutive words from a sentences and let $B_1,...,B_5$ be another five consecutive words chosen from different indexes (that is if we label the words of a sentence then $B_i$ and $A_j$ does not share an index.

Five is a small arbitrary number I chose

I used something like a curried syntax to get a hashtable that keeps a 3-touple: $(X,Y,Z)$

Where I mapped each sentence as follows:

$X$ is the number of words the sentence have.
$Y$ is obtained by a hash function on the content of the words (I will soon describe this hash function)
$Z$ is a list of integers containing the index of the line in the document [the line number] that was mapped to $(X,Y)$

In C# this corresponds to an object of a type

Dictionary< int, Dictionary< int, List< int>>>

So I kept two Hashtables of the above form, where I took the first five words to hash and get $Y$ and words $6-10$ to hash and get another value of $Y$.

Then given a sentence - compute the two $Y$ values it would of gotten and look at buckets with length that differs at at most $1$ from this sentence length and share one $Y$ value this sentence.

Let me describe the hashing function I used to get $Y$ -

I took the $A_i$ (similarly with the $B_i$) and concatenated them
I looked at this string as a byte array (that is by the bits that takes to represent the numbers) I then applied a the SHA-1 hash function on it (there are no security reasons for this but I wanted something that hashes well)
I took the last $4$ bytes in the SHA-1 hash and I looked at it as a positive integer (by looking at the last $32$ bits and considering it as an integer then applying the absolute value function). Call this result $R$

$Y= R\%p^{2}$

where $p$ was chosen as follows: I counted how many lines of a given length $l$ appear (say $n_l$), for lines of length $l$ I chose $p$ s.t $$\frac{n_l}{p^2}\leq 3$$

the following is a Histogram showing $n_l$ as a function of $l$

which should give some indication of the values chosen for $p$.

However - There are too many collisions - I get about $6$ elements in each bucket.

I took one example of such a bucket and I printed those sentences (I hoped they are similar so they would have a good reason to be mapped to the same bucket) by they are very different from one another. This is a printscreen of those sentences printed to the console.

Question: Why do I get a large number of collisions ?($6$ in average on $10^5$ buckets I considered where if I had even distribution I would expect $3$ from the choice of $p$, some buckets have a few tens of elements in them)

Could the problem be that I used modulo a square of a prime and not a prime ? is it that significant?


texts:
I have a number of players, ranging from [0..N].  Each round every player is assigned a specific role, either 1, 2 or 3.  floor(N / 8) role 3's are assigned, floor(N / 4) role 2's are assigned and the rest are assigned role 1's.

At the moment, I pick people completely at random for roles 3 and 2, however, this has the issue that some people can go many, many rounds without getting a specific round.  Although the algorithm is "random", people may still get annoyed at how it seemingly isn't.

I was wondering if anyone knew of a better algorithm which still assigns roles semi-randomly but tries to reduce the chance of someone not getting a role for too long (or, the converse, where it tries to ensure a role is not chosen too often)?


texts: Finite state automaton's reaction to simultaneous events

texts:
What does happen if two events simultaneously occur at a particular state of a finite state automaton (FSA)?

For example, assume that an FSA's event table at its state $s$ is as follows:

$\delta(s,e_1)=s_1$ and $\delta(s,e_2)=s_2$. What will be the system's next state if both $e_1$ and $e_2$ occur exactly at the same time?


texts: How is the number of states in a Turing machine bounded?

texts: The definition of Turing machine says that the number of states is finite. However, I do not get how this can be true. Is the number of states in a Turing machine actually not fixed, that is not bounded? If not, can anyone explain how this is possible?


texts: draw DFA with {w|w= Σ*0100}∩{w|w≠Σ*11Σ*}

texts:
So i need to draw a DFA for this language, i know i need to separate for 2 DFAs and than combine them both.

What is the approach ?
How do i do the $\Sigma^*$ inside the DFA ?
The 0100 condition is kinda easy, also the 11 language.


texts: Vehicle Routing Problem with multiple deliveries?

texts:
I have a problem that can be reduced to the following:

  There are three types of objects, A, B, and C. For each type of object, there are a number of "pickup points" and a number of "delivery points" (eg. there are five places where you can pick up object A, and five places where you must deliver it). What is the optimal route?

It is similar to the "vehicle routing problem with pickups and deliveries", except that rather than delivering one item from one point to another there are multiple choices for pickup and delivery points.

Is there literature, or perhaps software, that treats this specific problem? Alternatively, can this problem be reduced to a more common variant?


texts: How to map structured grid data onto a regular grid efficiently?

texts:
Context:
First of all, my data:
I am working with 3D data shaped onto a structured grid made of hexahedrons with for each 8 vertices and 12 edges.
The data I'm working on is cell data (and not point data).
Every cell and every vertex possess unique IDs.
For each cell I can list every other cell sharing a common vertex.
Consequently, if two cells share 2 vertices, they share an edge, and 4 vertices are needed to share a face.
There can be internal borders ("holes").
And finally the dataset is huge !
My ultimate goal is to apply operations on the whole dataset, based on the data of "neighbouring" cells.
Here is an example in 2D of a "cross" filter where I apply an operation onto the dark red cell based onto the data of the light red cells.

For this example, let's differentiate for a given cell, adjacent faces (sharing a common edge) and opposite faces (not sharing an edge).
Then, I need to find for every given "parent" cell which are the cells sharing a face with it, I will call them neighbours at rank 1. Then for every neighbour at rank 1, which are the cells (neighbours at rank 2) sharing their face opposed to the one shared with the initial parent cell...
This definition is really tedious and would need many "brute force" loops, so I thought of mapping every cell onto a rectilinear grid. I'm not modifying or interpolating the data, just changing the "representation" by storing it into a 3D matrix.
Thus if the parent cell now is on the line i and column j, I just need to loop on cells following something like :
for ii = i-2,i+2
    UsefullData(ii,j)
for jj = j-2, j+2
    UsefullData(i,jj)

Consequently, having the data mapped in such a way would allow for really easy manipulations, the cross filter being just a simple example. In a real case I would need to access up to the neighbour at rank 100, or user more elaborate filters than the "cross" filter defined above.
But it also have its caveats:
I don't know what would be the size of my mapping matrix i.e. border cells can "extrude" from the general "shape", or my grid could form a "C" shape, or possess inner holes...
I also don't know what would be the fastest (= less computing intensive) way to build it.
The problem:
I can't think of a robust and fast way to build this matrix, especially since I don't know how to define the maximum sizes of this matrix.
Maybe another type of connectivity table, easier to build but less "human readable" would also allow for easy manipulations ?
Also, I'm working with vtk and python, but  I don't thing this is relevant to the problem.
Thank You !


texts: Big-O of iterating through nested structure

texts:
While trying to understand complexity I run into an example of going through records organized in following way:
data = [
  {"name": "category1", "files": [{"name": "file1"}, {"name": "file2"}],
  {"name": "category2", "files": [{"name": "file3"}]
]

The task requires to go through all file records which is straight forward:
for category in data:
  for file in category["files"]:
    pass

It seems like complexity of this algorithm is O(n * m), where n is length of data and m is max length of files array in any of data records. But is O(n * m) only correct answer?
Because even there are two for-loops it still looks like iterating over a global array of file records organized in nested way. Is it legit to compare with iteration over different structure like that:
data = [
  ('category1', 'file1'),
  ('category1', 'file2'),
  ('category2', 'file3'),
]
for category, file in data:
  pass

...where complexity is obviously O(n), and n is a total number of records?


texts: Calculating gradient in a neural net using batches

texts: I am a CS student learning about neural nets. Currently I am confused about how to train a neural net in batches. If I calculate error in a batch, I will get a vector of errors e.g. real1 - predicted1, real2 - predicted2, etc... How do I then calculate a single gradient value to adjust the weights with?


texts: Approximating maximal independent set with a minimal vertex cover approximation

texts:
The minimal vertex cover problem has a 2-approximation algorithm.

We can reduce the maximal independent set problem to the minimal vertex cover problem as shown here.

Does this mean that I can use the $2$-approximation for minimal vertex cover to get a $1/2$-approximation for maximal independent set?

My approach:

// is this a 1/2-approximation algorithm?
approxAlgForMaxIS(Graph G) {
    minVC = computeMinVC(G);
    maxIS = G.V - minVC;   // remove all vertices in the minVC from G
    return maxIS
}


texts:
I'm looking for a "safe" representation of DAGs. With "safe" representation I mean that it can be described by a context-free grammar. Ideally, this grammar would be suitable for a simple LR parser.

The same problem for trees instead of DAGs is already solved: Just use one of the many well-known tree representations such as s-expressions or JSON, which are all context-free with nice, efficient parsers.

But how to approach that for DAGs instead of trees?

The naive approach is a list of nodes, where each node contains refereces to their parent (head) nodes. Ignoring referential integrity, this would be a regular language. But then I need to check that all references point back to an already-parsed node. How do I ensure this? Is there a clever PDA construction for that?
Or, do I need a totally different representation of DAGs?
Or, is any generic representation of DAGs doomed to be context-sensitive? If so, is there a proof for that?

I'm aware that in natural language processing, there do exist parsers which output a "parse DAG" instead of a parse tree. But I do not see how these may help in this particular problem. Maybe these are of no help here, but their existence gives me a feeling that this problem might have a solution.

(I became inspired to this question by the LANGSEC movement, here are some Slides of them.)


texts: Sublinear query time for the $i$th element of an array after some additions?

texts:
We are given an array $A[1..n]$ of integers, and an array of 3-tuples known as queries. The query tuples $(i,j,v)$ denote additions of an integer $v$ to the subarray of $A[i..j]$. I'm interested in the query time of $A[k]$ for $1 \leq k \leq n$ between the queries.

For example, let $A = [1,2,3,4]$, and let the queries be $Q = [[1,2,5],[2,3,6],[1,3,10]]$. After the second query has been processed, say I want to find the value of $A[3]$, which would be $3+5+6=14$. Does an algorithm exists to do this in less than linear time?