texts: So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input word?


texts: Reduce undecidable language to decidable language?

texts:
What happens if I build the following mapping function from $A_{\mathrm{TM}}$ to $A_{\mathrm{LBA}}$ (LBA means linear TM with a limited tape space and $A_{\mathrm{LBA}}$ is decidable):

If $M$ accepts $w$ then returns an LBA which decides the language {'111'}.

Clearly if $(M,w)$ is in $A_{\mathrm{TM}}$ then $f(M,w)$ is in $A_{\mathrm{LBA}}$ but then $A_{\mathrm{TM}}$ would be decidable!

What am I missing here?


texts: Maximise sum of "non-overlapping" numbers in square array - help with proof

texts:
A question was posted on Stack Overflow asking for an algorithm to solve this problem:

  I have a matrix (call it A) which is nxn. I wish to select a subset
  (call it B) of points from matrix A. The subset will consist of n
  elements, where one and only one element is taken from each row and
  from each column of A. The output should provide a solution (B) such
  that the sum of the elements that make up B is the maximum possible
  value, given these constraints (eg. 25 in the example below). If
  multiple instances of B are found (ie. different solutions which give
  the same maximum sum) the solution for B which has the largest minimum
  element should be selected.

  B could also be a selection matrix which is nxn, but where only the n
  desired elements are non-zero.

  For example: if A =

|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|

  => B would be

 |5 5 5 5 5|

I proposed a dynamic programming solution which I suspect is as efficient as any solution is going to get. I've copy-pasted my proposed algorithm below.

Let $A$ be a square array of $n$ by $n$ numbers.
Let $A_{i,j}$ denote the element of $A$ in the ith row and jth column.
Let $S( i_1:i_2, j_1:j_2 )$ denote the optimal sum of non-overlapping numbers for a square subarray of $A$ containing the intersection of rows $i_1$ to $i_2$ and columns $j_1$ to $j_2$.

Then the optimal sum of non-overlapping numbers is denoted S( 1:n , 1:n ) and is given as follows:

$$S( 1:n , 1:n ) = \max \left \{ \begin{array}{l}  S(   2:n , 2:n   ) + A_{1,1} \\
                             S(   2:n , 1:n-1 ) + A_{1,n} \\
                            S( 1:n-1 , 2:n   ) + A_{n,1} \\
                            S( 1:n-1 , 1:n-1 ) + A_{n,n} \\
                            \end{array} \right.$$

Note that S( i:i, j:j ) is simply Aij.

That is, the optimal sum for a square array of size n can be determined by separately computing the optimal sum for each of the four sub-arrays of size n-1, and then maximising the sum of the sub-array and the element that was "left out".

S for |# # # #|
      |# # # #|
      |# # # #|
      |# # # #|

Is the best of the sums S for:

|#      |      |      #|      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |      #|       |#      |

This is a very elegant algorithm and I strongly suspect that it is correct, but I can't come up with a way to prove it is correct.

The main difficulty I am having it proving that the problem displays optimal substructure. I believe that if the four potential choices in each calculation are the only four choices, then this is enough to show optimal substructure. That is, I need to prove that this:

|   #    |
| #   # #|
| #   # #|
| #   # #|

Is not a valid solution, either because it's impossible (i.e. proof by contradiction) or because this possibility is already accounted for by one of the four "n-1 square" variations.

Can anyone point out any flaws in my algorithm, or provide a proof that it really does work?


texts: Is maximum-leaves spanning tree np-complete?

texts:
How can we show that a maximum-leaves spanning tree is NP-complete? what other np-complete problem we can use as our reduction base?

(maximum-leaves spanning tree: does G have a spanning tree with at least K leaves? )


texts: Finding largest sum of $k$ elements below threshold

texts:
I was working on a project and am stuck in the middle unable to find an optimal method to solve this problem. Consider an array $A$ of $n$ elements. I have to choose $k$ elements such that the sum of indices is maximal under the constraint of being less than a given element $x$. My approach for this is the naive $O(n^k)$ algorithm, but this would take a lot of time for large $n$.

This is isn't a homework problem.


texts:
I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) solutions.
Now, I was thinking about the generalized problem which consider k neighbors(i.e. for the ith child we have to consider children from max(1, i-k)th place to min(n, i+k)th place) rather considering only one neighbour.
So, the problem is basically for every i in range[1, n] distribute candies in the children from max(1, i-k) to min(n, i+k) in such a way that each one gets at least one candy and if there are p children who have higher rating than ith child inside the window, then they will get more candies than the ith child.
Is there any linear time solution for this?


texts: Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?

texts:
Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing?

The motivation for this question is the fact that backtracking recursive descent parsing has a bad reputation for worst-case exponential runtime. This is presented as the reason for using other, more complicated parsing algorithms like LL, LR, packrat etc.

However, as I've been trying to hunt down a practical example of worse-than-linear parsing time for backtracking recursive descent parser, I've seen no reasonable examples.

The examples I've seen are often a deliberately bad grammar for a simple language, and the same language can be recognised by some other grammar.

So, of course, some grammars result in worse than linear time backtracking recursive descent parsing, but is the same true for (unambiguous) languages?


texts: Hash function to return only positive number from integer

texts:
What would be a good hash function that will return a positive integer value, even if the key is an negative integer value? How do I pick a hash function? So what I would want is to associate negative numbers with some positive value so I can use them later.

UPDATE: (summary)
I need to find a bijection $f: \mathbb{Z}\to\mathbb{N}$ which also has the property that:
$$
f(x) + f(y) = f(x + y)
$$


texts: What is difference between Hidden Markov Model and Non-deterministic Finite-State Machine?

texts: As the question implies, can you mention any difference between Hidden Markov Model and Non-deterministic Finite-State Machine? Are they different or the same?


texts: Prove that a language is regular if it is accepted by a DFA with more than one intial state

texts:
So I'm currently studying theory of computation, and I was wondering if you could theoretically have more than one initial state in a DFA and if you can prove that a DFA with more than one initial state can depict a regular language? So essentially, can we prove that a language is regular if and only if it is accepted by a DFA with more than one initial state?

I was experimenting with the language L which consists of all strings over the alphabet {a,b} which contains an even number of a's.

I managed to draw a DFA for this language as well as my representation for a DFA with more than one initial state. From the looks of things, it makes sense.

But is there any way that we can PROVE that a language is regular if it is accepted by a DFA with more than one state? So for any given DFA with more than one initial state, are the languages that it accepts is regular? If so, how can I prove it? I know from Kleene's Theorem that a regular language is accepted by an FA, but from the research I have done I have not been able to find anything regarding my question.


texts: Chebyshev’s inequality problem in one exercises I can't understand if I did it right or not

texts:
This is what do I have to solve:
Byron Book: Exercise 8.3 chapter 8
Verify the use of Chebyshev’s inequality in (8.6) of Example 8.16. Show that if the population
mean is indeed 48.2333 and the population standard deviation is indeed 26.5170, then at
least 8/9 of all tasks require less than 127.78 seconds of CPU time.
This is how I did it :
So first I calculated: 127.78-48.23 = 79.5
Then I wrote P(X<127) < (26.5^2)/(79.5^2) = 0.11
I don't understand if I did it right because I did not use this part : at least 8/9 of... and I think it is important.
Can anyone help me with this ? Thank you in advance.


texts:
I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture:

Let $S_{u}$ be the number of vertices in the rooted subtree of vertex $u$.
Namely, the size of the subtree of $u$. Now Let $L_{i}$ = {$S_{u}$ : $lvl(u)$ = $i$}.
Here, $lvl(v)$ denotes the level of $v$.
Also the height of a tree is the maximum level of any of its nodes.

Now the conjecture:

Let $H_{1}$ and $H_{2}$ be the heights of the rooted trees $T_{1}$ and $T_{2}$, respectively. $T_{1}$ and $T_{2}$ are isomorphic if and only if $H_{1} = H_{2}$
and for every integer $i \in [ \,1,H_{1}] \, $, the multiset $L_{i}$ of $T_{1}$ and that of $T_{2}$ are the same.

Apparently this conjecture is false because i implemented a C++ program (to solve a competitive programming task) that is based on it, but it failed system tests. Still, it may be an implementation fault, so i'd like to know if there are any counterexamples to this conjecture.


texts:
I have this simple 'assignment' problem:

We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike the general assignment formulation in Wikipedia, a task $t_c$ can only be assigned to an agent based on the task's preferred agents $ta_c \subseteq A$. For example, if we have $ta_1= \{a_1, a_3\}$, that means that task $t_1$ can only be assigned to either agents $a_1$ or $a_3$. Now, each agent $t_d$ has a quota $q_d$ where $q_d$ is positive integer. This means that $a_d$ must be assigned with $q_d$ number of tasks.

The Problem

Given above and a set of quota $\{q_1, q_2, \dotso, q_n\}$, is there an assignment of tasks to agents such that all agents meet their respective quota $q$. Note that it is not necessarily that all tasks be assigned to an agent.

Possible Solution

I have tried reformulating this problem in terms of a bipartite graph $G(A, T, E = \cup ta_c)$ and expressed as a form of matching problem where given a matching $M$, a vertex agent $a_d\in A$ is matched up to $q_d$ times or is incident to $q_d$ edges in $M$ but the vertices in $T$ is incident to only one edge in $M$. Not really like the usual matching problem which requires that the edges in $M$ are pairwise non-adjacent.

However, it was suggested by someone (from cstheory, he knows who he is) that I could actually work this out as a maximum matching problem, by replicating an agent $a_d$ into $q_d$ vertices and 'conceptually' treat them as different vertices as input to the matching algorithm. The set of edges $E$ is also modified accordingly. Call the modified graph as $G'$

It is possible to have more than 1 maximum matchings from graph $G'$. Now, if I understand this correctly, I still have to check each of the resulting maximum matchings and see that at least one of them satisfies the $qouta$ constraint of each $agent$ to actually provide the solution to the problem.

Now, I want to prove that not finding one maximum matching $M$ $\in$ set of all maximum matchings of the graph $G'$ that satisfies the $qouta$ constraint of the problem guarantees that there really exists no solution to the problem instance, otherwise a solution exist which is $M$.

I want to show that this algorithm always give correct result.

Question

Can you share to me some intuition on how I might go to show this?


texts: Pushdown automaton accepting $\{a,b\}^*$ with twice as many $a$s as $b$s

texts:
Design a pushdown automaton that can accept

  $$\{w|w\in\{a,b\}^*\text{ and $w$ has twice as many $a$s as $b$s}\} \, .$$

I have a solution as the following. The notation seems to follow "An Introduction to Formal Languages and Automaton" by  Peter Linz, where $\delta$ is the transition function with three arguments: current state, input, current stack top; $\lambda$ as the second argument of $\delta$ means empty string $\epsilon$ in some other textbooks, and $\lambda$ as the third argument of $\delta$ means the transition ignores the current stack top. The $\lambda$ on the right hand side means "pop the top element of the stack".

I have several confusions,

1) I am not sure what the right-hand side notation means. For example, does the right hand side of $\delta(q_1,a,A)=\{[q_2，A]\}$ means pushing an $A$ into the stack? Or it means the stack top stays $A$ without a new $A$ pushed to it?

If this means "push", then what about $\delta(q_1,a,C)=\{[q_2，C]\}$? $C$ seems to mark the bottom of the stack. We push another $C$ to the stack when there is already a $C$ in it?

2) I think the solution might be wrong. I don't see why it accepts $aab$. Tracing this string, I think the transition is the following based on the design (if the big letter at the right-hand side means pushing a new symbol),

$q_0,\lambda \to_\lambda q_1,C\to_a q_2,CC \to_\lambda q_1,ACC \to_a q_2,AACC \to_\lambda q_1,AAACC \to_b q_1,AACC$

It is very strange and I feel very confused. Hope someone can help! Thank you!


texts:
The domino tiles can be listed in an orderly way as shown in the figure :

figure link

Write a function such that given two variables ("minor" and "major") where "minor" is the  lowest value and "major" the highest value of a domino tile, calculate its order number associated with the previous figure.

Example : given a domino tile with numbers 1 and 5, the function must calculate the order number 11. Given a tile with numbers 4 and 6 the function must calculate the order number 24

From  the domino tile with numbers (0,0) to (1,6) the function "6 * minor + major" works but  from the next domino tile, the function begins to fail and I can't find a better function. Can someone help me please?


texts:
As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In other words, order matters. Certainly it will be much more than the Catalan number.

What would the problem be if you have n-ary trees instead of binary ?

Are these known problems?  reference ?


texts: Proving equivalency of regular expressions

texts:
x,y are regular expressions, prove this:
(xy+x)$^*$x = x(yx+x)$^*$*
(* in this expression is kleene star)

I am looking for a method that is applicable to prove such questions.
I know that proof needs to show that:

1) (xy+x)$^*$x => x(yx+x)$^*$

2) x(yx+x)$^*$ => (xy+x)$^*$x

My attempt is like this:

1) (xy+x)$^*$x =

= x(y+epsilon)$^*$x  by pulling x out -the x on the left is the one pulled out

= x(yx+x)$^*$    by distributing the last x

2) x(yx+x)$^*$

= x(y+epsilon)$^*$x   by pulling the x out -the right x is the one pulled out

= (xy+x)$^*$x         by distributing the first x

Does this make sense?
Thanks!


texts:
I would like to know what are the differences between (a,b)-tree and a B-tree. It has been a few days I am studying different papers and I am seeing different definitions that make me confused.

For example in External Memory geometric Data Structure by Lars Arge on Page 3 he says

  Normally, the N data elements are stored in the leaves (in sorted order) of an (a; b)-tree T , and elements in the internal nodes are only used to guide searches.

So the N data elements are stored in the leaves and internal nodes are only used to guide searching, they don't contain any data element other than the leaves. While in B-trees it is not so, In B-tree internal nodes contain their own different elements and every element of an internal node is used as a separator of its children. In fact it is a data element that is moved up.  Like this

But from (a,b) Trees, it says

  A B-Tree is a (a,b)-tree with a = ceil(b/2).

Which is in contradiction with the structure of internal nodes, Furthermore it shows that internal nodes have different elements than the leaves and all of the elements are not stored in the leaves. They may be stored in the internal nodes as well. In the insertion phase, some of the elements of the nodes are moving up to the parent as the separator.

I would like to know what are the elements in the internal nodes of B-trees and (a,b)-trees?

Thanks in advance.


texts: Notation for operational semantics that can be used in code comments

texts:
I'm defining an intermediate language for a multi-backend code generator that I'm writing.  I want to document the operational semantics for this intermediate language in a way that is readable both from within the source code and generated documentation (ocamldoc).  The notation introduced used in "Types and Programming" languages is great for a book, but I don't want to try to do the prerequisite over conclusion style notation via ASCII art.

Is there a widely recognized notation for operational semantics that doesn't require non-ASCII characters?  I looked through various RFCs but can't find any that use a non-natural language way of specifying semantics.


texts: Code metric for code redundancy or code cloning

texts:
Is there a common code metric for "code redundancy" or "code cloning"?

I think I read somewhere a definition, where the LOC (lines of code) of
the redundant code was measured.

I also searched for references, but didn't find a paper that seemed like an good or trustworthy reference.


texts:
I am recently learning the theory behind Coq and learnt that positivity condition guarantees termination of the program. But my question is, what would you think of the following definition?

Inductive t : Set := b : t | c : ((t -> unit) -> unit) -> t.

Sure it won't compile in Coq, but would it jeopardize termination guarantee? More precisely, in this definition, t is in a positive position as well, isn't it? So can I say theoretically speaking this should have also been a valid definition? Otherwise do you have any counter example?

My thought is, (t -> unit) -> unit should be isomorphic to t according to Yoneda lemma so it should be pretty safe, isn't it?


texts: Find value of $a$ or $b$ of two XOR equations

texts: Is it possible to find $a$ or $b$ given that $a \oplus b = c$ and $c \oplus b = a$ when I only have the value of $b$?


texts: Recurrence relation for a star and a dot wildchar pattern

texts:
. Matches any single character, * Matches any sequence of characters (including the empty sequence).

dict = ["cat", "cats", "and", "sand", "dog"].

pattern = "* t", -> true (can match cat)

pattern = ".a *" -> true (can match cat, cats, can also match sand, because * can also express empty sequence)

Is below recurrence relation captures the solution correctly?

DP[i][j] = True if i characters of string matches with j characters of pattern

DP[len(string)+1][len(pattern)+1] = False
DP[0][0] = True
DP[i][j] = DP[i-1][j]  if pattern[i] == "*"
           DP[i-1][j-1] if pattern[i] == "."
           DP[i-1][j-1] if (string[i] == pattern[j]) == any character


texts: operate infinite times over a regular language

texts:
Let $T:Σ^*\to Σ^*$ be an operation such that $T(L)$ is regular for all regular languages $L \in Σ^*$.

Is it possible to prove $T^∞(L)$ is regular?

$T^∞(L)=\bigcup_{i=1}^{\infty}{T^{i}\left(L\right)}$


texts: Is Karp Reduction identical to Levin Reduction

texts:
Definition: Karp Reduction
A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ such that for every $x$, $x\in A$ if and only if $f(x)\in B$.
Definition: Levin Reduction
A search problem $V_A$ is Levin reducible to a search problem $V_B$ if there is polynomial time function $f$ that Karp reduces $L(V_A)$ to $L(V_B)$ and there are polynomial-time computable functions $g$ and $h$ such that

$\langle x, y \rangle \in V_A \implies \langle f(x), g(x,y) \rangle \in V_B$,

$\langle f(x), z \rangle \in V_B \implies \langle x, h(x,z) \rangle \in V_A$

Are these reductions equivalent?

I think the two definitions are equivalent. For any two $\mathsf{NP}$ languages $A$ and $B$, if $A$ is Karp reducible to $B$, then $A$ is Levin reducible to $B$.
Here is my proof:
Let $x$ and $\overline{x}$ be arbitrary instances of $A$ while $x'$ be that of $B$.
Suppose $V_A$ and $V_B$ are verifiers of $A$ and $B$.
Let $y$ and $\overline{y}$ be arbitrary certificates of $x$ and $\overline{x}$ according to $V_A$.
Let $z$ be that of $x'$ according to $V_B$.
Construct new verifiers $V'_A$ and $V'_B$ with new certificates $y'$ and $z'$:
$V'_A(x,y'):$

$y'=\langle 0,\overline{x},\overline{y}\rangle$: If $f(x)\ne f(\overline{x})$, reject.
Otherwise output $V_A(\overline{x},\overline{y})$.
$y'=\langle 1,z\rangle$: Output $V_B(f(x),z)$.

$V'_B(x',z'):$

$z'=\langle 0,z\rangle$: Output $V_B(x',z)$.

$z'=\langle 1,x,y\rangle$: If $x'\ne f(x)$, reject.
Otherwise output $V_A(x,y)$.

The polynomial-time computable functions $g$ and $h$ are defined as below:
$g(x,y')$

$y'=\langle 0,\overline{x},\overline{y}\rangle$: Output $\langle 1,\overline{x},\overline{y}\rangle$.

$y'=\langle 1,z\rangle$: Output $\langle 0,z\rangle$.

$h(x',z')$

$z'=\langle 0,z\rangle$: Output $\langle 1,z\rangle$.

$z'=\langle 1,x,y\rangle$: Output $\langle 0,x,y\rangle$.

Let $Y_x$ be the set of all certificates of $x$ according to $V_A$ and $Z_{x'}$ be the set of all certificates of $x'$ according to $V_B$.
Then the set of all certificates of $x$ according to $V'_A$ is $0\overline{x}Y_\overline{x}+1Z_{f(x)}$ such that $f(x)=f(\overline{x})$,
and the set of all certificates of $x'$ according to $V'_B$ is $0Z_{x'}+1\overline{x}Y_\overline{x}$ such that $x'=f(\overline{x})$.
(This is derived from the accepting language of $V'_A$ and $V'_B$.)
Now let $x'=f(x)$, the rest part is easy to check.


texts: Injectivity verification in o(n) space and O(n) time

texts:
The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to solve it, e.g. via a hashmap or binary tree. Luckily, I have an untrustworthy but omnipotent oracle ally who is willing to give me hints on how to solve the problem.

The oracle is allowed to provide me $O(n)$ of hints, and I want an algorithm that will read $A$ and the oracle input (both read only) and determine either that $A$ has no duplicates, or that the oracle has given me a bad hint, in time $O(n)$ and much smaller read-write space ($O(1)$ or $O(\log n)$).

Can it be done?


texts: Is a language of some deciders decidable?

texts:
Is

$$L = \{ \langle M \rangle \mid M = (\{Q_1, Q_2, . . . , Q_{100}\}, \{0, 1\}, \{0, 1, \_\}, δ, Q_1, Q_2, Q_3) \text{ is a decider}\}$$

decidable?

I know

$$HALT_{TM}= \{ \langle M \rangle \mid M \text{ is a decider}\}$$

is not decidable, but in the case we are given a specific Turing Machine that has 100 states, alphabet $\{0,1\}$, tape alphabet $\{0, 1, \_\}$ (where _ is space), a transition function $\delta$, a start state $Q_1$, an accept state $Q_2$ and a reject state $Q_3$.

Checking that M is in the correct format is easy but is it possible to build a Turing Machine that decides $L$? I assume I can use the fact that $HALT_{TM}$ is undecidable to show that $L$ also is, but I am not sure how to proceed.

And I don't see how I could reduce $L$ to $A_{TM}$ to prove by contradiction that it is not decidable?

How should I proceed?


texts: Register images containing objects with varying distance to the cameras

texts:
I'm learning about using image registration to align two images, e.g., two photographs of the same scene taken from a slightly different location. What factors influence how well we can align the images? Does the distance to the objects in the image influence its effectiveness of alignment, and if so how? What about the amount of variation in the distances to the objects in the images: how does that influence the effectiveness of the alignment?

Background: I came across the notion of "global image registration" when reading the paper

  "Mutual information based registration of multimodal stereo videos for
  person tracking", by Stephen J Krotosky and Mohan M Trivedi, in Computer Vision and Image Understanding 2007.

I believe "global image registration" means to use one transformation function for the registration. The authors state that global image registration is accurate when all objects of interest are in the same plane. I am trying to figure out exactly what they mean.

At first, I assumed that the authors mean objects across different
    frames (then needed to have a similar distance to the camera across
    the frames), where the previously calculated registration is
    supposed to work for each frame.

Then I thought that they maybe mean the registration of a single
    image pair and that objects of interest must be in similar distance
    to the camera.

To check this, I registered two pairs of image. The first pair has a lot of depth, the second pair does not, i.e., the first pair contains objects of varying distances to the cameras. It can be seen that the latter is much better registered than the former. This suggests that my second statement is correct: an image registration based on one transformation function is not able to register an image well if there is a lot of variation in the distances to the objects in the image. Is this correct?

First image pair:

First image pair registered:

Second image pair:

Second image pair registered:


texts:
Is there a reduction from ATM to ATM-complement?

(ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$)

I have been thinking about it too much and couldn't find the answer.

I know that reduction from ATM-complement to ATM is not possible becouse if it was, ATM would not be in RE. But how can I proove/profe the other way around?


texts:
The questions is as follows with the answer:

  Q) Given the arrival and departure time of various trains in a station. Calculate the minimum number of platforms required such that no train has to wait for another train to vacate the platform. The question basically means calculate the maximum number of trains that would be present in the platform at any given time.

  Answer

  Sort the arrival time and sort the departure time, keep a count initialized to 0. compare the first element of the arrival time with the first of departure, increase the value of count if the value at current Index at arrival is less than the value index at departure and increment the arrival index, and vice versa. Keep the maximum count that you see.

MY PROBLEM: I have tried hard but I am not able to get why to sort both arrival and departure timings? As a train is single entity and you sort arrival and departure separately how can we know which train arrival matches with its departure? I am facing the same problem in closest pair problem as why to sort x points and y points separately.


texts: Does dynamic programming always add one item per sub-solution?

texts:
In the 0-1 knapsack problem, I am given a set of items with their weights and the weight that a knapsack can carry.

The objective is to maximize the number of items I can carry subject to the fact that I do not exceed the maximum weight of the knapsack.

The algorithm could be something as follows-:

weight = 0
list_of_items = {}
while weight < max_weight
for all remaining items present find one item that is equal to (weight + 1)
repeat until weight > max_weight

The key word here is "find one item".

This is my question, is it always true that we search for only 1 item each iteration for the next state/sub-solution ? Or can we search for multiple items ?

Will the next sub-solution always contain 1 value more than the previous one if it is possible to achieve ?


texts:
In a lecture video the instructor introduced the quadratic probing method for hash tables. The formula he gave was the following:

$h(k,i) = (h'(k) + c_1 + c_2i^2)$ $\% M$

where $h'$ was h "prime". So, what I am supposed to conclude for $h'(k)$ to be? Is it any different from the value I get by computing $h(k)$


texts:
I want to solve the following problem (This is a homework problem. Not looking for definite or complete answers):
Maximum One Third Cut:

Input: An undirected graph G=(V,E) where V={1,2,...,n}, such that |V| is divisible by 3, and a positive integral weight function w:E to N (on edges).
Goal: Fin a subset of vertices U subset of V such that |U|=|V|/3.
Objective: Maximize the total weight of the edges between U and its complement.

Of course, you can do that using a full search of all the possiblities. I want a more efficient algorithm though.
I'm thinking about some sort of Local Search algorithm, like Steepest Ascent Hill Climbing (SAHC), or a variation thereof (Simulated Annealing, Random Restart etc.).

States:
Could be a binary vector, where the i-th element represents whether the vertex i is in U or not (0: not in U, 1: in U), where the number 1-s is |V|/3.
Successors:
Turn one bit off, turn another on.
Heuristic Function:
Sum of all weights of edges between U and V\U. Could be computed when generating a successor, you only need to check the vertex removed and added. Perhaps states can contain a list of edges that are relevant.
Other Parameters:
Like Temprature or amount of restarts allowed could be set by testing the algorithm on graphs of varying in size, weight function and edges, and choosing the best values.

I was also thinking about Evolutionary Search.
Am I on the right track here? Are there better options perhaps?
Any suggestions would be much appreciated.Thanks!


texts: Resources for implementing dependent type theory

texts: I want to implement Martin Löf's intuitionistic type theory in a functional language such as Haskell, preferably also implementing a lexer/parser for the language. How should I start approaching it? Are there any good papers/blog posts/github repo examples that might be useful? Thanks!


texts:
Both Logic in Computer Science (Huth and Ryan, 2004) and Branching vs. Linear Time: Final Showdown (Vardi, 2002), state something to this effect (paraphrased):

  In LTL, X F p and F X p are equivalent, meaning "p is eventually true in some state that is not the current state". In CTL, AX AF p and AF AX p are not equivalent. AX AF p does mean the same as the above LTL formulas, but AF AX p means something different, which we leave as an exercise to the reader.

Both works emphasize that the meaning of AF AX p is something very strange.

From what I understand of CTL, AF AX p would mean "all paths from this state eventually reach a state where p is true in all next states", but that doesn't seem particularly strange. Am I correct in that understanding?


texts: Maximal class for which function equivalence is decidable

texts:
I previously asked if it's decidable whether two primitive recursive functions are equivalent: "primitive recursive functional equivalence". The answer was no.

Here is my followup. What is the most powerful class of functions where it can generally be decided if two functions are equivalent? That is, a function can be written such as areEqual :: fun1 -> fun2 -> Bool. By equivalent I do not mean the same algorithm but the same relation between domain and codomain.

In another question I asked if lower elementary recursion was equivalent to deterministic push down automata: "Relation of deterministic push down automata and lower elementary recursion". The answer was no, and that my thought process was wrong. My hope was that this would show that polynomial time functions (lower elementary) could be proven equivalent.

This question is in relation to what class of recursion, not machine. As such deterministic pushdown automata is not what I am looking for. If I understand the answers to my second question correctly the automata do not necessarily translate to a class of recursive functions.

I have been poking at this question for a while in a round about way probing for an answer.

The problem is intuitively solvable for simple problems. For example the even? function could be implemented in a mutual recursive manner with odd? or from mod 2. These two ways do the same thing. The question is in relation to the highest class of functions where this is possible.


texts: Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages

texts:
I'm trying to create a formal algorithm in order to determine whether
  two given regular expressions $a$, $a'$ define identical/equal or
  unequal languages and if those languages are subsets of each other?

(I'm not sure if following thoughts are correct and formal enough and I'm glad if you spot mistakes and improve my algorithm.)

Let $a$,$a'$ be regular expressions. Now, we want to determine: $$\bigg(L(a)=L(a') \text{ or } L(a)\neq L(a') \text{ and } \Big((L(a)\subset L(a') \text{ or } (L(a')\subset L(a)\Big)\bigg)$$

In order to do that, we will "convert" the regular expressions $a$ and $a'$ into DFA's $M$ and $M'$. Those automatons have minimal and non-redundant states $K=\{q_1, \cdots ,q_n\}$ and $K'=\{q_1, \cdots ,q_m\}$ with $n,m \in \mathbb{N}$.

Now, we can simply determine, whether $K=K'$ with showing $K\subseteq K'$ and $K' \subseteq K \implies K=K' \implies L(a) = L(a')$.
If the above equation is not true, then we can imply that $K\neq K' \implies L(a) \neq L(a')$.  Furthermore, with $K\neq K'$ and $K \nsubseteq K'$ and $K'\subseteq K \implies K' \subset K \implies L(a')\subset L(a)$.
Analogue: $K\neq K'$ and $K' \nsubseteq K$ and $K\subseteq K' \implies K \subset K' \implies L(a) \subset L(a')$ .

Is this enough or do I need to compare final states, transfer function and the alphabet in order to be sure $L(a)=L(a')$ etc.?


texts: Is $NP$ "minimal", i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

texts:
Suppose $\Pi$ is a decidable decision problem.

  Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard?

Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim without any unknown assumptions?


texts:
I'm trying to study for an exam and I realized I'm confused about how the TLB and data cache work.

I understand that the TLB is essentially a cache of most recently used physical addresses. However, I was looking at a diagram in my textbook (shown below), and I don't understand what's going on in it. It suddenly splits up the physical address and uses it to index the cache, I guess. But why is it showing the cache and data separately? and why is the byte offset just left floating? I'm pretty sure the cache is supposed to store data as well. I don't think its sole purpose is to determine whether or not there's a hit or miss inside of it.

I apologize for my ignorance in advance, but the book barely covers TLB's (it's like a little more than a page) and it doesn't do a very good job at explaining the relationship between a TLB and cache.


texts: Clustering of Songs (The Joe Walsh Problem)

texts:
The Eagles are a rock supergroup from the 70s and 80s, responsible for such classics as Hotel California. They have two quite distinctive sounds, one where guitarist Joe Walsh is present (for example, in Life in the Fast Lane) and one where he is absent. The latter songs have a markedly more sombre/boring feel.

I'm curious to understand the degree to which an (unsupervised) learning algorithm would be able to detect the difference between the two sounds. One could imagine that it would be easy to tell the difference between speed metal and classical music, but what about sounds by the same band.

  How would I set up such an experiment? Assume that I already have the relevant audio files in some standard format.

Note that this should also apply to other rock groups, such as AC/DC who had a change of lead singer in 1980, and possibly even to other genres, possibly even more modern music.


texts:
Given the codes below for Mark-Sweep Algorithm, what are the state of the live objects prior to mark and sweep phase?
Reference:
True - has a marked bit
False - has no marked bit

for each root variable r

Mark(r);

Sweep();

void Mark(object p)

if(!p.marked)

   p.marked = true;

 for each object q referenced by p

    Mark(q);

void Sweep()

for each object p in the heap

   if (p.marked)

       p.marked = false

   else

       heap.Release(p);


texts:
How can we compute the least Harshad number with given sum of decimal digits $S$? Harshad number in base 10 is any number divisible by sum of its decimal digits.

I think that some kind of dynamic programming should be used.  But which one?

Thanks in advance for any ideas.


texts:
I want to find set cover of this problem.
I have sets, each of cardinality 3. I want to find set cover.
This is what I am doing.
Treat each set as an edge, which is incident on each of its element.
I am considering each element as a vertex.
Now I will find minimum edge cover of this graph(hyperGraph).
Is this the right way to do?


texts:
Is there a Turing machine that halts iff P = NP? There are Turing machines that halt iff the Goldbach conjecture is false, or the Riemann hypothesis is false. How about the P vs. NP question? This is an expressiveness question, but I have not seen such a construction before.
Update: There are competitions to construct the smallest TM that halts iff Goldbach is false. The current record is 27 states. Basically the TM puts successively larger even numbers in unary on the tape and checks if there is a cut dividing the unary even number into two primes. This is the spirit that I intended; my question is not about existential, nonconstructive arguments or provability from ZFC.


texts: Widely-used and fundamental distributed algorithms

texts:
I've been reading text books about distributed algorithms. They usually present a large collection of algorithms under various hypothesis and guarantees, with their proof of correctness. But they often fail to mention the practical application of those algorithms, and their relative usefulness and importance. For instance, various forms of broadcast, snapshot, election, consensus...

My questions are :

What are the most fundamental distributed algorithms (the few ones
that you really need to know)
Could you give me very concrete cases where they are used
What are the most widely used distributed algorithms

Thanks in advance. I'm feeling overwhelmed :)


texts: How much does C# gain from its value types

texts:
C# makes an distinction between value types and reference types contrast to Java where all (except primitives types) are of reference semantics. The design decision, as I understand it, is mainly to make small objects more cache friendly, that is, for efficiency reasons.

my question is;

is there any study on how much efficiency gain does C# make by this design choice, based on evaluating real world projects.
Assuming the answer to the first question is that there is a measurable efficiency gap, will things change when JIT compilers come into play?


texts: Why do programming languages use call-by-value over call-by-name?

texts:
I am reading Software Engineering 1: Abstraction and Modelling by Dines Bjørner. One of the chapters talks a little bit about call-by-value vs call-by-name. In it, the author states that most programming languages use call-by-value, rather than call-by-name. But from what I have read in the chapter, it seems that call-by-name is a much safer method of calling functions.
For example, say we have a function like f(x, y) = y * 3, and we call it somewhere like f(infinteLoop(), 6), where infinteLoop() is some function which never terminates. If we use call-by-name, we never have to call infiniteLoop() because x is never used in the body of f. But if we use call-by-value, we need to evaluate infinteLoop(), even though it will never be used in the body of f. This will cause the program not to terminate, of course.
It seems to me that call-by-name is both safer and more efficient (since we do not need to evaluate unused expressions). So for what reason do most (or any for that matter) programming languages use call-by-value instead of call-by-name?


texts: Classify an algorithm to maximize number of tips used by liquid handlers concurrently

texts:
I'm looking for suggestions on algorithms, data structures or at least problems (so that I look for solutions in that domain) to consider. I realize that exact solution probably doesn't exist. But the more similar problems/solutions I can find the more ideas they may inspire.
We need to transfer reactants from source vials to target vials where they'll be mixed with other reactants and be a part of chemical reactions.
Settings: a liquid handling robot has up to 8 tips which can aspirate (suck in) & dispense (spit out) liquid from/to multiple vials. They can do this either simultaneously or one-by-one.
Input: list of source vials, list of target vials, mapping between source and target vials as well as volume to be transferred.
Goal: minimize time to transfer. This usually means maximize the amount of time tips work simultaneously. To simplify the problem - lets optimize (meaning group them) only dispense operations.
Example
E.g. we aspirate from Source vials and dispense to Target vials. In this example we'll use 4 tips:

Aspirate all 4 Source vials, then dispense to A1, B1, C1, D1
Dispense E1 with 1st tip, then use 1st & 3d tips to dispense to F1, H1, then dispense to G1
Use 2nd & 3d tip to dispense to A2, B2 then to C2, D2
The rest will be filled by 1 tip at a time.

Here color represents which Target Vial should receive liquid from which Source Vial:

Additional conditions

Simultaneous aspiration/dispense is possible only when vials are located in the same column.
Tips can change the spacing between them. E.g. 1st & 3d tip can either dispense to E1 & H1 or F1 & H1 simultaneously.
Tips have max volume (1mL). If you need to dispense more - you'll have to return back and aspirate more.
Volume to be dispensed is different in different locations.
We could've aspirated with 2 tips from the same vial and then transfer the same substance with these 2+ tips. But for simplicity let's not consider this option.


texts: Using Loop Dependence analysis for vectorization

texts: How exactly Loop Dependence Analysis helps in vectorization ? Are there any standard rules of safety criterias for parallizing such loops ?


texts: How do I compute the address of the next element?

texts:
I have to work on something , but I am making an error that I can not identify. Propably, it is going to sound simple to you but it's my first course on computer architecture and there is nothing in my slides or book.
"We are given a memory, where the smallest chuck of information that can be adressed is 1 byte, and we use 32 - bit memory adresses. Arrays , contain doubles, and each elememnt is an 8 - byte one."
&x[0]=0x0000A100 ."
I want to compute the adresses of &x[i] , i=1,2..
What I did thought was the right approach is:
Since, we have a memory that is byte - adressable then we can do it as such :
&x[i] and &x[i+1] have a dc offset which is  8 -byte and since it is byte adressable then :
&x[i+1] = &x[i] + 8
And I used an online calculator to get these results :

But they are wrong...


texts: Is "Reachable Object" really an NP-complete problem?

texts: I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. from 2P1N SAT to Reachable Object. This only proves that the problem is NP-hard; do we not need to prove the reverse direction (2P1N to Reachable Object) to prove NP-completeness?


texts: Find the minimum count of elements summing to a pre-defined sum

texts:
We have the following problem: Given an array of integers $\{a_1, a_2,...,a_n\}$ and a number $s$, find a contiguous sub-array of elements that sum exactly to $s$. If multiple solutions exist, find a solution that is smallest in terms of length (length of sub-array). If there is no such contiguous sub-array, output "-1".

I have thought of an $O(n^2)$ algorithm, using two pointers and prefix sums, but I cannot find an $O(n)$ algorithm. What would an $O(n)$ algorithm be like?


texts: How can $\Theta$ and $O$ complexities be different?

texts:
From the definition of the $\Theta$-notation,
$$f(n)=\Theta(g(n))\\\implies \exists n_0, \exists c_1,c_2\gt 0, \forall n\gt n_0, c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$$

We can see that the inequality is followed for all $n\gt n_0$, and hence we can say that $c_2\cdot g(n)$ is the maximum that this function can reach. Therefore, $f(n)=O(g(n))$ as well.

If we take the example of quicksort, sources say that the $\Theta$ complexity is $n\log{n}$, but $O$-complexity is given as $n^2$.

If the $O$-complexity given is true, then $f(n)\le c_2\cdot n\log{n}$ will not always be true. So in this case, how is $\Theta$-complexity different from $O$-complexity?


texts:
This demonstrates the limitations of considering expected running time of an algorithm as a useful measure. For any $n>0$, describe  a function $f:\{0,1\}^n \to \mathbb{N}$ such that

$\mathbb{E}[f] = \mathbb{E}_{x\in \{0,1\}^n}[f(x)] = n^c$ for some constant $c$
and
${\sf var}[f] = E[f^2] - (E[f])^2 = \Omega(2^n)$.

I.e., there can be performance measures $f$ which is polynomial in expectation, but variance being exponential. Give formal justification for your answer (i.e., computation of expectation and variance for the function $f$ constructed).

I'm not able to approach the problem. I guess some hint would suffice.


texts: Time and space complexity of a recursive problem (code included)

texts:
I am having trouble finding out the time and space complexity for this recursive solution. I have to create a list of words in order of word length. Each word, must be one character insertion off from the previous word. All permutations. Here is example:

For the set "a, b, at, bat, cat, bait". The possibilities are:

a -> at -> bat -> bait
a -> at -> cat
b

Here is my Javascript code to get all of these combinations:

function getLists(words) {

    const wordsByLength = {};
    for (const word of words) {
        const length = word.length;
        if (!wordsByLength.hasOwnProperty(length)) {
            wordsByLength[length] = [];
        }
        wordsByLength[length].push(word);
    }

    const lists = [];

    getListsUtil([], wordsByLength, lists);

    return lists;
}

function getListsUtil(list, wordsByLength, lists) {

    const lastWord = list[list.length - 1] || '';
    const oneOffWords = getOneOffWords(lastWord, wordsByLength);

    if (!oneOffWords.length) {
        lists.push(list);
        return;
    }

    for (const oneOffWord of oneOffWords) {
        getLongestListUtil([...list, oneOffWord], wordsByLength, lists);
    }

}

function getOneOffWords(targetWord, wordsByLength) {

    const oneOffWords = [];

    const targetWordLength = targetWord.length;
    const possibleWords = wordsByLength[targetWordLength + 1] || [];

    for (const possibleWord of possibleWords) {
        if (isWordOneOff(targetWord, possibleWord)) {
            oneOffWords.push(possibleWord);
        }
    }

    return oneOffWords;
}

function isWordOneOff(targetWord, possibleWord) {
    let isOneOff = false;
    let i = 0;
    let j = 0;

    while (i < targetWord.length && j < possibleWord.length) {
        if (targetWord[i] != possibleWord[j]) {
            if (isOneOff) {
                return false;
            }
            isOneOff = true;
            j++;
        } else {
            i++;
            j++;
        }
    }

    return true;
}

console.log(getLists(['a', 'b', 'at', 'cat', 'bat', 'bait']));

We can draw the call stack for this, it looks like this:

If we have repeating words we can get a call stack that looks like this:

a, a, a, ab, ab, ab, abc, abc, abc:

If we had this set of words:

a, b, c,  ab, bb, cb, aba, abb, abc, bba, bbb, bbc, cba, cbb, cbc

I started drawing this callstack but I didn't finish it, we see a bunch of overlapping subproblems:


texts: Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p

texts:
Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely.

Could you explain how to efficiently calculate those mod operations  through mod(2^w) and can we extend it to a more common case of mod(w +/- c)?

Another question if we mod by a constant primary number in many places they mention different tricks compilers can do to avoid expensive division operation. Any ideas about those tricks?


texts: Question about Circuit-SAT NP-Complete Proof

texts:
I have two questions about the proof that Circuit-SAT is NP-Complete from here (just the first 1.5 pages):
https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture22.pdf

The THEOREM 1 states that the size of $C_n$ is bounded by some polynomial in $n$. Where is this necessary in the proof? It seems like what really matters (coming from the reduction definition) is that we can find $C_n$ in polynomial time. I am not sure where the size comes in.
How would one "hard-wire" $G$ into the circuit in the second paragraph? I understand why it is necessary. However, wouldn't one need to also show that this hard-wiring takes polynomial time as well?


texts: Is there a name for the problem of turning a bipartite graph into two graphs?

texts:
Is there a name for the problem of turning a bipartite graph into two graphs in the following way? We form one graph from the vertices on the left, such that two vertices are made adjacent if they share a common neighbour on the right; we form the other graph similarly from the vertices on the right.

This pops up, for example, when finding collaboration relationships in a bipartite graph from scientists to papers or actors to movies.

This being a common problem, I wonder if it has a common name, and maybe specific literature on it.


texts: What is the largest sum that can be constructed with the given recipes?

texts:
There are $n$ sets of distinct positive integers, $S_1,\ldots,S_n$.
There is a set of recipes that allows us to construct tuples of integers from these sets. For example, the recipe {1,2} allows us to construct tuples of two integers: one from $S_1$ and one from $S_2$. Each integer can be used in at most one tuple. What is an algorithm that, given the sets and the recipes, constructs tuples such that the sum of integers in all tuples together is maximum? Here are some simple cases:
(a) There is a single recipe, e.g. {1,2}. Then the algorithm is simple: sort the integers in $S_1$ and in $S_2$ in descending order; pair the largest integers in each set; pair the second-largest integers in each set; keep pairing integers as long as the sum of the next pair is positive.
(b) There are two recipes {1,2} and {1,3}. Then, $S_2$ and $S_3$ are substitutes: combine them into a single set $S_4 = S_2\cup S_3$, and proceed as in (a) with the recipe {1, 4}.
(c) There are two recipes {1,2} and {1,3,4}. Then, $S_3$ and $S_4$ are complements: sort each one in descending order, and construct a new set $S_5$ in which the largest element is the sum of the largest elements in $S_3,S_4$, the second-largest is the sum of the two second-largest elements, and so on. Proceed as in (b) with the recipes {1,2} and {1,5}.
(d) The above two operations can be generalized to the case in which the set of recipes has a tree structure: there is a tree in which each node is a set, and each recipe is a path from root to leaf in the tree. The tree can be "contracted" as follows: a leaf which is the unique child of its parent can be combined with its parent as in (c); two leafs of the same parent can be combined as in (b).
Is there an efficient algorithm that works for any set of recipes?


texts: Is the runtime of binary search big omega of logarithm of n?

texts:
My question is that can we say that runtime of the binary search is $\Omega(\log n)$?

I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst case. And for this reason the time complexity of binary search is $\Theta(\log n)$.

However, I still cannot interpret if it is also $\Omega(\log n)$ even if I think (and know that) it is. So, I just need some scientific explanation.


texts: How was the ALU implemented in the first computer (i.e., Babbage's analytical engine)?

texts: I've seen circuit level implementations of ALU's before, but how are NOT/AND/ADD performed mechanically?


texts: Creating Best Clusters of Objects Based on Distance Between Them

texts:
I have an array of images. And, there is a function that calculates the distance between two images.

I wish to cluster the images based on this distance. So the clusters contain images that are all at short distance to each other.

So only the distance between two images can be used to form the clusters. An image has no usable properties on their own. As many common clustering algorithms expect objects to have usable properties, it seems I can use these algorithms.

To limit computational complexity, I've introduced a few thresholds to decide if two images may end up in the same cluster:

calculated distance (I want to optimize for shortest distance, but above a certain distance, images are not close enough to ever share a cluster)
input array distance (e.g. an image at index 23 may only cluster with images up to index 123)
creation data interval (images created more than N hours apart, may not share a cluster)

Some details:

There can be up to 100k images.
Roughly 25-50% of images will be 'unique' and do not end up in a cluster with others. Of the remainder, most will be expected to end up in clusters with a size below 10, with 5% outliers above that.
The maximum cluster size is something I want to set somewhere between 10 and 50.

Given the above and the nature of the image set, a graph (image: edge, calculated distance: vertex) would consist of disjoint parts consisting of up to a few hundred images. So the algorithm needs to be able to cluster sets of well below 1000 images.

The clusters must be optimised for distance, such that closer images end up together in a cluster. I'm aware that parameters like minimum and maximum cluster size would be needed; it's a play between creating a few large clusters with a higher maximum distance, or more smaller clusters with images that are closer together.

What kind of algorithm(s) could I use?


texts: Finding the lexicographically smallest palindrome of the same length that is lexicographically greater than or equal to given string s

texts:
I got stumped by this question during a coding challenge and I haven't come up with promising ideas for how to solve it. I am looking for hints or approaches to solve the problem, not necessarily the code.

Given a string s find the lexicographically smallest palindrome of the same length that is lexicographically greater than or equal to s.
Strings may contain only lowercase English letters.
Examples:
For s = "cbaba", the output should be smallestPalindrome(s) = "cbabc"
For s = "abcbc", the output should be smallestPalindrome(s) = "abdba"
Trickier test cases:
input: "xgdfcs", output: "xgeegx"
input: "aazzzzba", output: "abaaaaba"
input: "aiyudauzzzzuaduyie", output: "aiyudavaaaavaduyia"

Guaranteed constraints:
4 ≤ s.length ≤ 5x10^5.

My previous approach was to:

Check if word is a palindrome by moving two pointers (i, j) at both ends of the word towards the middle.
If the two characters don't match, either set i-th character equal to the j-th, viceversa, OR set both equal to some character that appears later in the alphabet.

...but I couldn't figure out how to decide which option in step 2) should be taken. Maybe there's a better approach to it.
I'm trying to avoid posting the name of the company that posed me this question to prevent future interviewees from knowing the answer in advance, so you can assume I found the question here:

Source: https://codelearn.io/training/detail/33520


texts: Digraph vertices: classification by counting outgoing walks

texts:
I'm reproducing a question I posted on MSE (yet with no answer both there and by myself).

Given a (finite) directed graph $G = (V, E)$. For each vertex $v \in V$ and a natural number $n$, let $W_v(n)$ be the number of walks in $G$ of length exactly $n$ originating at $v$. That is,
$$W_v(0) = 1 \quad\text{and}\quad W_v(n + 1) = \sum_{\substack{u \in V \\ (v, u) \in E}} W_u(n).$$
Now, for $u, v \in V$, let $u \sim v$ iff $W_u(n) = W_v(n)$ for all $n$. This equivalence of vertices induces a partitioning of $V$. What is known on the complexity of computing this partition?

(By "computing", it may have meant an algorithm that assigns each vertex $v\in V$ a number of its class, so that two vertices are equivalent iff they get assigned the same number. I do see some resemblance to the Hopcroft's DFA minimization algorithm, but still the problem being solved is different... and I see this to be a corner case of some harder problems.)


texts: Example of worst case input for Build-Max-Heap

texts: What would be an example of a worst-case input for Build-Max-Heap?  What would the "shape" of it "look like"?  I'm having trouble getting a feeling for it.


texts:
I am working on a computer organization caching problem
The Problem:  What happens if the associativity level is greater than the cache  size?

I know that associativity level is how many blocks are in a set. Say we have a 16 way set associative cache and a cache size of 15. What would happen? Would the cache break or would it turn into a fully associative cache(1 set)


texts: Min path cover for a three-layer graph with all paths traversing all layers

texts:
Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. Further, there is a feasibility matrix between colors and tastes and also one between tastes and smells. Hence, this can be thought of as a tri-partite graph; but there are edge constraints only between successive layers and not between every combination of layers; so it is a special case of a tri-partite graph (in a general tri-partite graph, there would also be edges between colors and smells). My objective is to cover all possible colors, tastes and smells with a minimal number of fruits.
Included below is a toy example. Here, we have three colors, two tastes and three smells. The connectivity is as shown on the left. The optimal solution is shown on the right. We can see that there are three paths that can cover all possible colors, tastes and smells. Hence, three fictional fruits will suffice and are the minimal required (since there are three colors and smells, we couldn't have done it with less than three).

Note: Cross-posted here: https://math.stackexchange.com/questions/3878929/minimum-edges-required-to-cover-all-vertices-of-three-way-graph. See great answer there as well.

My attempt:
One algorithm that comes to mind is the minimal path cover for a DAG. However, the well known formulation of that problem requires the paths to not share any vertices. We can see in the solution above that this constraint only gets in our way for this problem. The optimal solution does indeed have two paths that share a common taste vertex ($t_1$). Hence, it doesn't immediately apply.
Another approach involves finding the min-edge cover for the bi-partite graph between colors and tastes and another min-edge cover between tastes and smells. Then, we can go to each taste and greedily assign colors and smells from the respective min-edge covers until everything is covered. This approach has a danger: the two min-edge covers are not aware of each other. In the figure below, the situation on the left shows one possible set of min-edge covers which leads to the optimal solution. But, we could also end up with the situation on the right. In that case, we'll end up needing four fruits to cover everything which is sub-optimal.

So, how do we fix the algorithm above? We want to encourage the behavior on the left from the min-edge cover and discourage the behavior on the right. We observe that $t_1$ is a "super-vertex" with more colors and smells attached to it. So, we can assign the edges emanating from it lower costs. Then, we can modify the min-edge cover algorithm to prefer the edges with low costs. One approach would be to take the minimum of the number of colors and smells attached to each taste and divide $1$ by this. Then all edges emanating from that taste get this as the cost.
This algorithm will work for our toy example. However, how do we prove its optimality in general? And if it isn't optimal, how do we devise an optimal algorithm?


texts: Can non-metric TSP be approximated within some non-constant value?

texts:
It is known that metric TSP can be approximated within some constant value, such as 3/2 through Christofides' algorithm. It is also known that non-metric TSP cannot be approximated within some constant value (unless P= NP), thanks to Sahni and Gonzalez.

It isn't clear however if non-metric TSP can be approximated within some non-constant value, such as the number of nodes of the instance, or the largest cost on its edges? Does Sahni and Gonzalez's result still hold for these values?


texts: Minimum Hamming Distance of code for ASCII strings

texts:
I couldn't figure out how to answer the following question:
Suppose we want to transmit a string of 3 ASCII characters, and in order to be able to detect or correct the message, we append the sum of the chars at the end of the binary string. e.g.:

encode("abc") == `110000111000101100011100100110`

what is the distance of such code?
what is the distance of the same code with an additional parity check bit at the end?

all I could figure out so far is that the code is in the form of (30,21,d)
and if one bit flips, it's of course detectable, thus 'd' is at least 2, and we cannot correct errors.
But when two bits flip (or more), I can't grasp it.
It seems to me like the parity check version doesn't do a lot, and I'm not quite sure how can I make a case (if any) to maximize 'd'.

I understand the classic (7,4,3) examples, but this one had me all confused due to the number of possible strings. How should I approach it?


texts: Find most valuable subset of a node weighed tree

texts:
Suppose you got a directed acyclic graph of positvely and negatively weighed nodes $T\hspace{-0.02 in}$.

Now I have to find the the subset  $M\subseteq T$  such that the sum of

the weights of the nodes in $M$ is maximised, but if  $v \in M$  then all

children of $v$ as well as their children, and so on have to be in $M$ too.

For now my algorithm is as follows:

calculate the depth of each node (how many nodes you have to
traverse at maximum to reach one which doesn't have any children)
for all nodes $v$ of depth $n$ do the following:

add up the weight of $v$ and the weights of all children and
grandchildren,
... (you get the idea) of $v$
if the last step added up to a positive value then mark $v$ and
all children of $v$ as in $M$ and don't consider them any further
if the last step marked any node with the current depth then repeat
for this depth (since the sums changed) otherwise increment n.

This works fine for some DAGs:    (Note:  the edges are directed downwards)

As expected all nodes except the top node are in $M$

But for othes the algorithm falls short:

The algorithm outputs that  $M = \emptyset$ ,  whereas  $M=T$  should be the case.

Is there an algorithm which solves a similar problem?

If no, how can I correct my solution?  Any help is highly appreciated.

PS:    I apollogize for the use of MS Paint.  Sorry for that.


texts: What is a "slice" of a parameterized problem $(Q, \kappa)$?

texts:
In the book "Parameterized Complexity Theory" by J. Flum, and M. Grohe, there is a definition on page 7:

Definition 1.10.
Let $(Q, \kappa)$ be a parameterized problem and $\ell \in \mathbb{N}$. The $\ell$th slice of $(Q, \kappa)$ is the classical problem

$$(Q, \kappa)_\ell := \{x \in Q\ |\ \kappa(x) = \ell\}$$

Which is also referred to in the following chapters. Although I can understand the topics fairly enough, I still cannot understand the term "slice" in detail.

I kind of "memorized" that a slice of an fpt problem is solvable in PTIME. However, I do not really understand the logic behind it.

So, my question is:

  What is a slice of a parameterized problem?


texts: Is there an NP-hard problem for which no Fixed-Parameter Tractable algorithm exists?

texts:
Question
Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 parametrised problem for which no FPT algorithm exists?

The adding a parameter is needed because a NP-hard problem is normally just a question with a yes or no answer, if you want to limit some parameter you need to specify which one (even though something like $k$-Coloring might have an obvious one already), so with "specifying which parameter" one is limiting, one is "adding a parameter" to the problem. A more detailed description is included in the answer by Discrete Lizard.
I think Natural tries to exclude "trivial" parameterizations as I discuss in my first doubt in this question. Again a more detailed description is included in the answer by Discrete Lizard.

Doubt

It might be a trivial question as it perhaps is possible to always "stuff" the entire problem within the $f(k_1,k_2,..,k_m)$ part of the $f(k_1,k_2,..,k_m)n^c$ algorithm whilst setting $n=c'$ where $c'$ is an arbitrary constant. But perhaps the exact definition of FPT prevents such (ab)use of the concept of FPT.

Based on the comment of plop there indeed exists a trivial way to parameterize "any" (I assume any properly well-posed problem) problem, such that its parameterization is fpt. Those parameterizations use languages, which I assume to be what is described here. Such a "trivial" (in light of the question, not in light of difficulty) parameterization is intended to be ignored. So in the "words" of Discrete lizard: non-trivial parameter range(s) is(are) intended.


texts: Multiplication of two or more algebraic quantities

texts:
Recently, I was facing the problem how to multiply to two or more algebraic quantities in c++. For example, if the two algebraic quantities are

$$x^2-2x+3, \text{and } x-5$$

then the result of multiplication will be

$$x^3-7x^2+13x-15.$$

My question is that how to read the two algebraic quantities, find out the result of multiplication and print the result in c++.
I need hints and is there something to learn to multiply the two or more algebraic quantities by programming. If so,what is that?


texts:
The 3SUM problem has two variants. In one variant, there is a single array $S$ of integers, and we have to find three different elements $a,b,c \in S$ such that $a+b+c=0$. In another variant, there are are three arrays $X,Y,Z$, and we have to find a number per array $a\in X, b\in Y, c\in Z$ such that $a+b+c=0$. Call the first variant 3SUMx1 and the second one 3SUMx3.

Given an oracle for 3SUMx3, can we solve 3SUMx1 in linear time?

One option that comes to mind is just to create 3 replicates of the input array $S$ and run: 3SUMx3($S,S,S$). However, this may return two copies of the same item. E.g. if $S$ has only two elements, 1 and -2, then the 3SUMx1 problem has no solution, but 3SUMx3($S,S,S$) will return the fake solution $(1,1,-2)$.

I currently have a solution but it is not linear. To explain the solution, consider first the simpler problems 2SUMx1 and 2SUMx2, in which we only look for two numbers $a+b=0$ in either one array or two different arrays. Given an oracle for 2SUMx2, the problem 2SUMx1 can be solved in the following way.

Let $n$ be the number of elements in the input array $S$.

For i = 1 to log(n):
  Partition the array S to two arrays, X and Y, based on bit i of the index. I.e.:
    X contains all elements S[k] where bit i of k is 0;
    Y contains all elements S[k] where bit i of k is 1.
  Run 2SUMx2(X,Y)
  If there is a solution, return it and exit.
If no solution were found for any i, return "no solution".

This algorithm works because, if there are two different items, $a,b\in S$, whose sum is 0, then their index must have at least one bit different, say bit $i$. So, in iteration $i$ they will be in different parts and will be found by 2SUMx2($X$,$Y$). The time complexity is $O(n \log n)$.

This algorithm can be generalized to 3SUM by using trits instead of bits, and checking all possible pairs of them. The time complexity is therefore $O(n \log^2 n)$.

Is there a linear-time algorithm?


texts: How to find lower bound of f(n) for master theorem

texts:
I'm studying the master method to solving a recurrence. It describes three cases, the last one of which depends on what lower bound a function f(n) has.

I usually find out the upper bound of a function from its highest term exponent. How would I figure out its lower bound Ω?


texts:
There seem to be at least a couple different possible ways of modeling sum types in a type system, but I haven't been able to find consistent terms for referring to them:

A sum type is formed from a set of "data constructors", which are function-like entities that notionally map values of a summand type to values of the sum type. This is the model adopted by e.g. Haskell and the various flavors of ML.

A sum type is formed directly from the underlying summand types, with no data constructors, and as a consequence the sum type is a supertype of the summands (or at least behaves very much like one). This model seems to be much less common, but it's the model adopted by Ceylon, and by C++'s std::variant.

Note that this is separate from the distinction between discriminated and non-discriminated unions: both models permit the sum type to be discriminated (although only if the summands are disjoint, in the case of #2).
Are there settled terms for distinguishing these two models?


texts: Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

texts:
Every undecidable problem that I know of falls into one of the following categories:

Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the halting problem, are undecidable because you could use a purported decider for the language to construct a TM whose behavior leads to a contradiction. You could also lump many undecidable problems about Kolmogorov complexity into this camp.
Problems that are undecidable due to direct self-reference. For example, the universal language can be shown to be undecidable for the following reason: if it were decidable, then it would be possible to use Kleene's recursion theorem to build a TM that gets its own encoding, ask whether it will accept its own input, then does the opposite.
Problems that are undecidable due to reductions from existing undecidable problems. Good examples here include the Post Correspondence Problem (reduction from the halting problem) and the Entscheidungsproblem.

When I teach computability theory to my students, many students pick up on this as well and often ask me if there are any problems we can prove are undecidable without ultimately tracing back to some kind of self-reference trickery. I can prove nonconstructively that there are infinitely many undecidable problems by a simple cardinality argument relating the number of TMs to the number of languages, but this doesn't give a specific example of an undecidable language.

Are there any languages known to be undecidable for reasons that aren't listed above? If so, what are they and what techniques were used to show their undecidability?


texts: Is C++ considered a language with high or low orthogonality?

texts:
I'm looking to make a comparison of regularity in languages - specifically orthogonality.
If I were to say Java is weak in terms of orthogonality and Haskell stronger, where would C++ sit and why?


texts: Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates

texts:
A Boolean function $f : \{0, 1\}^n → \{0, 1\}$ is called monotone if changing any of the $n$ input bits $x_1, \ldots , x_n$ from $0$ to $1$ can only ever change the output $f(x_1, \ldots ,x_n)$ from $0$ to $1$, never from $1$ to
$0$.

I know how to do a simple proof of exhaustion for $f : \{0, 1\}^1$ and $f : \{0, 1\}^2$, but I do not know how to prove the following statement for $f:\{0,1\}^n$: any monotone Boolean function is computable by a circuit containing only AND and OR gates.


texts: Can converting NFA to DFA change the language?

texts:
In the context of studying the conversion from an NFA to the equivalent DFA, I came across the following NFA, which accepts all strings over the alphabet $\{0,1\}$ which contain $01$:

After I converted the NFA to the equivalent DFA, it became:

The issue is that the NFA accepts the string $101$ but the DFA doesn't.
Is my conversion wrong or is there something I am missing about the NFA to DFA conversion?


texts: Finding all circuits that contain a given edge

texts:
Given a directed graph $G = (V, E)$ and an edge $e \in E$, I'm trying to come up with an algorithm to construct the minimum induced subgraph $H$ of $G$ with the property that every circuit in $G$ that traverses $e$ is in also in $H$.

As an example, suppose graph $G$ has vertices $V = \{1,2,3,4\}$ and edges $\{(1,2), (2,1), (2,3), (3,2), (3,1), (2,4), (4,3)\}$, and $e = (4, 3)$. The subgraph $H$ that the algorithm should output consists of the two circuits $2,4,3,2$ and $2,4,3,1,2$.

Of course, this problem can be solved by enumerating all circuits of $G$, but I'm hoping that someone here can come up with something better (that is, with strongly polynomial complexity, in the size of the graph) than that.

EDIT: I just found this post that solves the problem for undirected graphs, but it doesn't provide any directions for directed graphs. I don't see a straightforward generalisation to directed graphs from that post.


texts:
I got confused by this a bit... the words of any recursively enumerable language $\mathcal{L}_{RE}$ can be enumerated by an enumerator $E$, i.e. there is an effective procedure (using lexicographic ordering of inputs) for all words $w \in L$ (with $L \in \mathcal{L}_{RE}$) to be printed by $E$.

Now suppose $E$ lists down all words $w \in L$ by taking as input the computation history of a word $w$. The computation history is derived using transitions of a Turing Machine $TM$ that recognizes $L$. $E$ operates by checking if all segments of the computation history are valid given transitions of $TM$. To print $w$, $E$ uses a homomorphism, i.e. by printing the first segment of the computation history. In this case, the set of all words that enumerated by $E$ is equal to $L$.

But if the enumerator $E$ is a Turing Machine itself, call it $TM^E$, is it accurate to say that $TM^E$ recognizes $L$? If true, there seems to be a contradiction since $E$ does not loop - since it can check whether or not a computation history input from a lexicographic ordering follows the transitions of $TM$ and results in $w$.


texts: Inverse Reinforcement Learning and Apprenticeship Learning differences

texts:
IRL as I understand is where the AI is given a policy from an "expert" and needs to solve for the reward function which best fits the policy.

And Apprenticeship Learning via IRL was explained as an expert demonstrating a skill and the reward function also has to be derived using the expert behavior.

I don't necessarily understand the difference between the two since apprenticeship learning directly uses IRL. Any explanation of differences would be helpful.


texts: Given a randomised algorithm for a problem, is there a corresponding deterministic algorithm?

texts:
Does every randomised algorithm have a corresponding deterministic algorithm solving the same problem?

I'm going to guess that the deterministic algorithm will take more time, while the randomised algorithm although it has errors will generally be faster. This is from what I have seen of them so far. Let me know if this is wrong.


texts: How can you iterate through a hash table in constant time?

texts:
I am studying data structures and the book "How to Think About Algorithms" by Jeff Edmonds (pages 46-47) claim that:

  "Hopefully, all the elements that are in your set happen to be placed into different entries in the table. In this case one can

  determine whether or not an element is contained in the set,
  ask for an arbitrary element form the set,
  determine the number of elements in the set,
  iterate through all the elements,
  and add and delete elements

  in constant time i.e independently of the number of items in the set."

when speaking about hash tables. I don't understand how it is possible to iterate through all the elements in constant time. Shouldn't it be $O(N)$ since we iterate through all of them?


texts: Minimum swaps required to convert a series into AP

texts:
Lets say i have a sequence ${6, 10, 11, 16, 17}$. Each number represents number of coins. The task is to find the minimum swaps to convert the sequence into AP
Lets say common difference is $3$.
To convert into AP, I'll do the following

Take one coin from $10$ and give it to $11$.
one from $16$ and give it to $17$.
So I will get the AP sequence with 2 swaps.
I can transfer more than one coin in a single swap.

My Approach:
First I will find a sequence with the given common difference.
Considering the above sequence, its sum is $60$.
So, $60=\frac{5}2*(2a+(5-1)*3)$
On solving, $a=6$

So creating the AP sequence, $6, 9, 12, 15, 18$

Subtracting this sequence with the above sequence,
we get $[0, -1, +1, -1, +1]$
I want to convert all the elements to zeros.
First I'll sort this sequence
$[-1, -1, 0, +1, +1]$
I'll point the first element and the last element by left and right respectively and find the sum.

If the sum is -ve then change *right to $0$ and *left to obtained sum.

If the sum is +ve then change *left to $0$ and *right to obtained sum.

If the sum is $0$, change *left and *right to $0$ and increment left and right.

At each step increment the count.

Loop will terminate when left>=right.

The final count is the answer.

I am not sure of the correctness of the algorithm.

Is there any recursive solution to it?


texts: Floating Point Arithmetic with 3 bits mantissa

texts:
Find all values of $ x ∈ R $ such that x + 1 = 1 in floating point arithmetic with 3 bits mantissa.
How do we represent number 1 in floating point arithmetic with 3 bits mantissa I wonder? After that, I think we can subtract 1 on both side? I am a little confused about representations of numbers in floating point arithmetic with a specific number of bits in mantissa.


texts: How does one prove that Big Step semantics and Small Step semantics are equivalent for IMP?

texts:
I know there is this paper but I wanted to do a special case proof for just IMP for fun. So the theorem is:

  $$ \langle P , \sigma \rangle \to_{Big} \langle \{ \} , \sigma' \rangle \iff \exists N \in \mathbf N: \langle P , \sigma \rangle \to^N_{Small} \langle \{ \} , \sigma' \rangle $$

in words; the program P in state $\sigma$ evaluates to the empty block IFF there exists a certain number of small step steps inference steps that arrives us to the same configuration, the empty program in state $\sigma'$. Note $\langle P, \sigma \rangle$ stands for a program configuration with state $\sigma$. I am assuming both small step and big step have the same sort of configuration, which might be a big assumption and hard to formalize in real code...

I am happy with just an outline/sketch since a rigurous proof might be too much work probably and I'd rather get something than nothing.

I want to focus on $\Rightarrow$ (big to small). I think one of my main difficulties is finding such an $N$ that works. But conceptually to me I think I would break the proof by induction on the program P. The program has 6 constructors/cases:

Empty Block {}
Block B which is just $\{ S \}$
Assignments $x = AExp ;$
Sequences $S_1 ; S_2$ where $S_i$ is a statement.
while statements $ While \ (BExp) \ do \ S $.
ifElse statements $If \ (BExp) \ do \ S_1 \ Else \ S_2 $.

for the first case 1) its simple we have $\langle \{ \} , \sigma' \rangle$ on the RHS for big step and on the LHS $\langle \{ \} , \sigma' \rangle$ for small step, which are the same configuration. Done.

3) For the case assignment case we have to show that the AExp expressed uin the semantics, say big step or small step evaluates to the same as the "aeval" function that recursively just evaluates a real arithmetic expression. Not sure how I can make this more rigorous but at least it is a start.

Things with Boolean expression in them also need the same beval equivalence with boolean evaluation equivalence in their corresponding semantics.

However when things involve statements I am honestly not sure what one would need to argue to show they are equivalent. Do we do induction again on each statement and then proceed by apply the inference rules as many times as possible and show they evaluate to the same final state and empty block? Or what does one need to do? Then especially, how does one find the $N$?

The inference rules I had in mind are just any standard IMP semantics:

http://fsl.cs.illinois.edu/images/b/b3/CS522-Spring-2011-PL-book-bigstep.pdf
http://fsl.cs.illinois.edu/images/6/65/CS422-Spring-2015-02c-SmallStep.pdf
https://softwarefoundations.cis.upenn.edu/plf-current/Smallstep.html
http://www.cs.cornell.edu/courses/cs6110/2009sp/lectures/lec05-fa07.pdf
http://web.cse.ohio-state.edu/~bond.213/6341/Operational-6.pdf
https://www.seas.harvard.edu/courses/cs152/2010sp/lectures/lec03.pdf


texts: If P = NP, would dynamic programming be obsolete?

texts: I know that dynamic programming is used to solve in "pseudo-polynomial time" some NP problems, like the knapsack. If P = NP, would it mean that every problem that we solve with dynamic programming would have a more efficient (polynomial) way to solve? Or are there problems that even if P = NP, we would still use dynamic programming


texts: All languages are regular, as unions of singleton languages

texts:
We know that singleton languages (languages containing exactly one word) are regular. We also know that a finite union of regular languages is also regular.

Suppose there is a non-regular language $L$. For every finite subset $\{x_1,x_2,\ldots,x_i\}$ of elements of $L$, we can take the corresponding singleton languages and compute their union. This new language (which is a subset of $L$) should be regular. Now we do the same with rest of the language.

Finally, we must have $sL_1, sL_2,\dots, sL_n,\dots$ which are all subsets of $L$ that are finite regular languages. If we take the union of $sL_1, sL_2,\dots, sL_i$, where $i$ is finite, we again have a regular language. We do this for all languages obtained from $L$.

If we keep doing such "finite" unions of regular languages, we will eventually obtain $L$, which must be regular because we obtained it from a finite union of regular languages.

This obviously isn't right, but I don't understand why.


texts:
im having some problems when it comes to Pumping Lemma of Context-free Language ... this is the Language :

$$L = \{a^n b^n c^m | n\ge 0 , 0 \le m \le 2n \}$$

Here is my attemp to prove that the language is not context-free:

Assume $L$ is context-free. Let $p,r>0$ be the pumping length given by the lemma.

Let $z=a^p b^p c^r$, then $z∈L$

Than according to the lemma, z can be written as z=uvwxy where the following properties hold:

$$|vx|≥1$$
$$|vwx|≤n$$
for every $i≥0$, $uv^iwx^iy∈L$

for the cases $i$ always had some problems ... there is one ..

$vx = a^n b^n$ (no $c$'s )

i really have some problems understanding the PL for CF Language


texts: What is the state of the art for k nearest neighbour search?

texts:
I'm not an computer scientist, but still use/have an algorithm to find the $k$ nearest neighbours from a cloud of $N$ points in $d$ (my case $d=3$) dimensional space using some distance measure (in my case Euclidean). I had some look at the literature and it appears that the standard is J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw., 3:209–226, 1977, which is a root-first tree traversal on a kd tree. This algorithm has complexity $O(dk\log N)$ for each search (after the tree has been built at cost $O(dN\log N)$). I wonder whether this is still the state of the art.

The reason I'm asking is that my own algorithm is different (also using a tree) and has (I believe) average costs of $O(dk)$ per search (but still worst case $O(dk\log N)$), provided the query point is a member of the cloud. So I was wondering whether it's perhaps worth publishing.


texts: Question about the conditions to find articulation points in a graph

texts:
I have been reading a book called The Algorithm Design Manual by Steven Skiena and one of the topics discussed there is an algorithm to find all the articulation points in a graph.
In it, we first construct a DFS tree and store the following information for each vertex in the DFS tree:

The traversal order at which we visited the vertex
The highest reachable ancestor from the tree for each vertex

After constructing the tree, the author says one of the following conditions need to be satisfied for a vertex to be an articulation vertex:

If the root has more than 1 child, it is an articulation point
If we have an edge A -> B which is a bridge, then A is an articulation point
If we have an edge A -> B (A is parent of B) and the highest reachable node from B is A, then A is an articulation point.

I wrote a program to test this and it works on the graphs I tested it against:
// lo[] contains highest index
// pre[] contains traversal order
private void dfsFindArticulationPoints(int node, int parent) {
    if(pre[node] != 0) {
        lo[parent] = Math.min(lo[parent], pre[node]);
        return;
    }

    pre[node] = index;
    lo[node] = index;
    index++;

    int childCount = 0;
    for(int child: graph[node]) {
        if(pre[child] != 0)
            childCount++;
        if(child == parent)
            continue;
        dfsFindArticulationPoints(child, node);
        lo[node] = Math.min(lo[child], lo[node]);

        // Check case 2 and 3
        if(node != 0 && pre[node] <= lo[child])
            articulationPoints.add(node);
    }

    // Check case 1
    if(node == 0 && childCount > 1)
        articulationPoints.add(0);
}

My Question:
I understand why those three conditions work. However how can I convince myself that those are the only three conditions to check?
Can somebody please prove to me that those are the only three conditions and there are no other conditions to check for?


texts:
If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently, could one not also use this algorithm to solve unbounded knapsack problems since two factors can be viewed as one value, say within the set for the knapsack problem, and the other being the number of copies of the first factor?

FACTOR 15; 3, 5

Unbounded KNAPSACK with value of 15 and the set of all integers; {5,5,5} andor {3,3,3,3,3}
Would this mean FACTOR was NP-Complete?
Would solving unbounded knapsack problems in polynomial time in this way prove P=NP?


texts: Algorithm for mapping objects of list without mapping to itself?

texts:
I want to map objects of a list, to objects of that same list, randomly, without ever mapping any given object to itself.

So given a list of objects [a, b, c] valid maps would be, for example:

   a -> b,
   b -> c,
   c -> a

or

   a -> c,
   b -> a,
   c -> b

an invalid mapping would be:

   a -> a,
   b -> c,
   c -> b

I just cannot figure out how to implement such an algorithm.

(This is for a small Secret Santa app that I am building where each person will be assigned to buy gift to one of the other participants.)


texts: Given an input and a program when can you derive the output faster than just running the program?

texts:
Given an input string W, a description of a turning machine M, and a target output string O (W,M,O) as input, when can a machine M' decide, in fewer steps than simply running M on W, if running M on W, in fact, produces O or not?

What are the circumstances under which this faster M' exists and when is this impossible, i.e. when does this problem reduce to the halting problem (seems like it does)?

Thanks!


texts: Applying information theory to processor clocks

texts:
Has there been any research on the subject of applying information theory to a processors clock? It occurred to me that a clock is actually transmitting data that is used for synchronization of different processor components. Once I started to apply information theory concepts to the clock a lot of interesting ideas came up. I.e. clock speed is equivalent to bandwidth, the two voltage levels it transmits are the equivalent to symbols making is a 2-level transmitter (duh), and the logical limitations on how to usefully apply those two symbols is equivalent to noise. Processor manufacturers increase channel capacity by increasing processor speed and processor architects try to increase information rate by designing smarter encoding/decoding techniques like pipe-lining, branch prediction, speculative execution, and even multi-core processors.

After looking at it like this, and considering that systems designers are going to greater and greater lengths to squeeze greater information rates from just two symbols, wouldn't it make sense to increase the symbol rate? I don't mean going to ternary or quaternary or any other-ary processing, but just giving the clock more symbols or using multiple "clocks". Of course the incredibly high speeds in modern processors and the extremely tiny transistor sizes tend toward not doing so, but it does introduce some interesting thought experiments.

Has anyone explored this in an academic or experimental setting?


texts: Is a minimal deviation version of set partition problem NP-Hard?

texts:
I want to know if a specific version (and what´s its name?) of the Set Partitioning Problem is NP-Complete, and if, is NP-Hard?

Problem:

Given a set of elements $e_i$ where $i={1,...,n}$, each with an associated weight $w(e_i)$, we want to find an optimum partition of these elements into a set of $S_j$ subsets where $j={1,...,k}$. Each subset $S_j$ has an objective weight $W_j$. We define a subset's weight as $w(S_j) = \sum_{{e_i}\in{S_j}} w(e_i)$ where $w(S_j)=0$ if and only if $S_j=\emptyset$.
Then the objective is to minimize the sum of the absolute deviation of the weights $w(S_j)$ w.r.t. the objective weights $W_j$:

$$min \sum_{j=1}^{k} |w(S_j) - W_j|$$

I do not really need a proof, just an actual answer and if possible, some reference to a paper or an article about it.


texts: Reasoning for awkward style of TreeMap.getHigherEntry

texts:
Consider a binary search tree (AVL, red-black, whatever). The goal "find the least key strictly greater than the specified one" ("upper_bound" in C++ STL, higherEntry//higherKey in Java, etc.) can be implemented in manner (Java-like pseudocode):

current = root;
bestsofar = null;
while (current != null) {
  if (example_key < current.key) {
    bestsofar = current;
    current = current.left;
  } else {
    current = current.right;
  }
}
// return for KV extracting
return bestsofar;

This can be improved with optimizations (e.g. C5 adds special processing case without comparings if found exact match), but the main principle remains that we use single pass from the root to a leaf.

But Java TreeMap implementation uses strange variant (the same at least in versions 8...13):

    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;

so, in some cases it backtracks using "parent" link to find the place it started passing only left-side links before final right-side dead end. (Really, all 4 key-based inexact searches utilizes this way, with minor differences and mirrored conditions.)

What case is being optimized with this approach?


texts: Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit

texts:
I have such a task at university:
we have $n$ tasks, the $i$-th of them can be done between moment $b(i)$ and $e(i)$. If we decide to perform a task in moment $x$, we finish performing it in moment $x+1$. We can perform at most 1 task at a time and we cannot interrupt performing it. Create an algorithm to check if it is possible to perform all the tasks. $b(i)$ and $e(i)$ may not be integers.

I have done some research online, but I haven't found anything concerning this problem.

Actually I think the following algorithm would work (I haven't found a counterexample yet):

iterate over all the tasks ordered by increasing $e(i)$ and for each of them try performing it the earliest possible. If cannot, return false. If all tasks are added, return true.

If this algorithm works, how could I prove it?


texts: Comparing non-deterministic and also the deterministic expressive power of FA, PDA's and TM'S

texts:
I am sorta confused and also could not find a answer online, but in terms of expressive power, .

Non-deterministic FA, PDA, TM

NFA < NPDA < NTM

Deterministic FA,PDA,TM: This is where i am confused

DFA < PDA < TM?

In a whole: ?

DFA = NFA = e-NFA = RE < DPDA < NPDA = NCFL = DCFL < NTM = DTM?

Please correct me or am i correct?


texts: Recognizing waterways in an aerial photo -- polygons from edge detection images

texts:
I am trying to recognize waterways from aerial photographs (say from Google Maps). Local governments often have GIS data that says where the waterways (and roads, buildings etc) are, but the water data in them is often somewhat inaccurate, and we might be able to improve them using aerial imagery. So we have some data already that isn't always to be trusted.

I know how to do some basic image processing on the data (unfortunately I don't have sample images to show here yet, I'm trying to imagine how I could do this, no working code yet):

I can collect some set of color values using bits of waterway in images, and figure out which pixels are closest to these colors, possibly also for other types of feature (grass, roads, buildings etc). If I set a threshold on which pixels are "close enough", I get a set of pixels that are probably waterways (but there will be a lot of noise).
I can turn the image into grayscale and use a standard edge detection algorithm to figure out where the edges are. Again, this gives me a set of pixels of like boundaries, but there will be noise and edges will be too think and/or have gaps.

What I want to have as output is a set of polygons that outline the probable waterways.

Intuitively I'd like to use the detected edges to create polygons, and the colour information to decide which of them are water, possibly making use of the government data we already have.

Is there a known way to get from the result of an edge detection algorithm to a nice set of closed polygons? Or any other tips on how to attack this problem, if there's a better way?


texts: A 2D Layout Algorithm for Small, Sparse, and Undirected Graphs with a Specific Edge Length

texts: I would like to to draw a graph where every edge $e_m$ has a predefined length of $l$. Given that the graph is small and sparse, it should be feasable. However, I did not manage to find an algorithm which does this (or one that is suitable to modify) yet I'm sure that this is a solved problem. Does anyone know of such a layout algorithm and could point me to an implementation or paper?


texts: Inclusion of complexity classes (Deterministic Turing Machine)

texts:
I can't understand what my professor wrote about these inclusions concerning deterministic classes:

$$
DTIME(f) \subseteq DSPACE(f) \subseteq \sum_{c\in\Bbb N}DTIME(2^{c(log+f)})
$$

I understood the first inclusion:

  The Turing Machine needs to do at least one step in order to check the
  next cell on tape

I didn't get the second one:

  The number of configurations of the Turing Machine with fixed space is finite, and the computation must stop within a maximum number of steps equal to these settings, otherwise wewould have a cycle.

I don't understand the argument of the summation: why that $2$ and that $c(log+f)$?
Why is it written like that?


texts: Does the word "efficient" usually refer to polynomial time or polylogarithmic time?

texts:
This question is strictly about terminology.

I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and the Wikipedia article on computational complexity theory use the word in that way.

However, other sources (e.g. the Wikipedia articles on NC and P-complete) reserve the word "efficient" for algorithms with polylogarithmic runtimes and use "tractable" for algorithms with polynomial runtimes.

This conflicting terminology is obviously confusing. Of course, any (good) formal discussion of algorithmic complexity will precisely define its terminology, but in general, are either of the two usages above clearly more conventional than the other? If someone uses the term "efficient" in an informal discussion of computational complexity without defining it, is it more likely that they mean "polynomial time" or "polylogarithmic time"?