texts: Rice–Shapiro theorem in computation theory

texts:
I am trying to learn the Rice–Shapiro theorem on my own. Here is the theorem:

  Let $Γ$ be a set of computable functions such that the set $R_Γ$ is recursively enumerable. We have $f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.

I will appreciate if anybody helps me to make the theorem crystal clear.
I just want to know what it really means and how I can use it to say that a set is not r.e., for example the set Empty or TOT.


texts:
Given a matrix $M \in \mathbb{R}^{n \times m}$ and a set $S \subset \{1, \ldots, n\}$, let $M_{S, {\rm row}}$ be the matrix obtained by picking the rows of $M$ from the set $S$. Similarly, given $S' \subset \{1, \ldots, m\}$  we let $M_{S', {\rm col}}$ be the matrix obtained by picking the columns of $M$ in $S'$.

Now the problem is as follows. Given matrices $A, B, C$  what is
$$ {\rm min}_{S \subset \{1, \ldots, n\}} ~~~~{\rm rank}~  \left( \begin{array}{cc} A & B_{S, {\rm col}} \\ C_{S^c, {\rm row}} & 0 \end{array} \right) $$

In other words, when you choose columns of $B$ corresponding to a set $S$, you have to choose rows of $C$ corresponding to the complement of $S$.

The dimensions here need to match in order for the question to make sense. In particular, we should have $A \in \mathbb{R}^{n \times n}, B \in \mathbb{R}^{n \times m}, C \in \mathbb{R}^{l \times m}$, and the $0$ in the lower-right-hand-corner has cardinality $|S| \times |S|$ depending on the set $S$.

This feels like it should be NP-hard but I'm having a lot of trouble coming up with a reduction.


texts: Graph of size n with girth >2k and minimum degree more than n^1/k

texts:
I'm stuck at a proof about Graphs in the context of Graph Spanners. A Lemma says:
Let $G$ be a graph with $n$ vertices and $m$ edges. If $G$ has girth more than $2k$, then $m\leq n^{1+\frac{1}{k}}$.
The proof is made by contradiction where repeatedly any node from $G$ of degree at most $\lceil n^\frac{1}{k}\rceil$ and any edges incident to that node is removed, until there is no such node anymore. This step leads to a subgraph $G'$ of $G$ of minimum degree more than $\lceil n^\frac{1}{k}\rceil$.
The conclusion is that $G'$ must have girth at most $2k$ and therefore also $G$, which is a contradiction.
I don't understand the conclusion: Why must $G'$ have girth at most $2k$? Why is it not possible that $G$ has girth more than $2k$ and minimum degree more than $\lceil n^\frac{1}{k}\rceil$?

I don't really see an answer to this question, so I would be very grateful if someone can help me.


texts: Why the Cook-Levin reduction is not a parsimonious reduction?

texts:
In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is one in which certificates of an NP language are mapped bijectively on the certificates of SAT. I am not sure why the reduction is already not parsimonious.

The reduction basically converts the snapshots $Z_1, Z_2, \dots, Z_{T(n)}$ ($Z_i$ contains the state, the symbols of the two tapes currently under head in the $i$th step) of an oblivious NP machine into a SAT formula, where $T(n)$ is the runtime of the NP machine. The main observation used for converting the sequence of snapshots into a SAT formula is that every $Z_i$ is a function of previous $Z_i$s.

Following is Cook-Levin's proof from Arora-Barak.


texts:
I'm trying to evaluate the time complexity of the following :

foo (n)
    if n ≤ 1
        return 1
    if n is odd
        for i=1 to n
            print i
        return foo(n-1) + 1
    if n is even
        i=n
        while i>2
            j=1
            while j<i
                j=j*2
            i=i/3
        return 2 * foo(n-1)

my attempt was to produce a recurrence relation broken into cases:

if $n \leq 1$ then :

$T(n)=\theta(1)$

if $n $ is odd then the for loop is executed $n$ times and we return a problem of size $n-1$ so :

$T(n)= T(n-1) + \theta(n)$

if $n$ is even then the inner while loop is executed $\theta(log_6(n))$ times and the outer while loop is executed $O(log_3(n)) $ times so totally that would be $O(log_3(n))= O(log(n))$ , and we return a problem of size $n-1$ twice so:

$T(n) = 2T(n-1) + O(log(n))$

ultimately :

$T(n) = T(n-1)+n $ if $n$ is odd

$T(n) = 2T(n-1)+log(n) $ if $n$ is even

$T(n) = 1 $ if $n = 1$

since whenever $n$ is odd , $n-1 $ is even , $n-2 $ is odd and so on..
that had me confused. Any ideas of how to solve this?


texts: Algorithm to construct timeline graph with arrival and departure times

texts:
So I am trying to construct a timeline graph for threads interacting with synchronization functions e.g. pthread_mutex_lock.

I have the following information:

1- thread ids

2- ids for the synchronization functions

3- Arrival times of the threads at the synchronization functions e.g. the time at which the thread encountered pthread_mutex_lock

4- Crossing time i.e. the time at which the thread crossed in to the critical section (e.g. crosses pthread_mutex_lock)

My idea:

1- Sort all the times (both arrivals and crossings)

2- for each time construct the event i.e. thread x arrived/crossed at synchronization y.

The questions:

1- The time complexity for this will be O(n log n) where n is the number of events (i.e arrival and crossing)?

2- Any possible imporvements/alternative ways/existing algorithms?

cheers!


texts: Semantic information collections on the web. (Semantic Wikipedia)

texts:
There are lots of technologies supporting semantic information markup even as wiki software.

I am wondering if there is any kind of broad information collection project like Wikipedia which features semantic markup of those information.

Google didn't bring up a project like this (only for very specific topics like software) or i just didn't find the right keyword.

Does anyone know about something like this?


texts: Is finding a weight-balanced tree NP-hard?

texts:
In the following, we consider binary trees where only the leaves have weights.
Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves.
Let $T.l$ and $T.r$ be the left child and right child respectively.

We define the imbalance $I(T)$ of a binary tree $T$ as follows:

$$I(T) = \begin{cases}
0 & size(T) = 1\\
|W(T.l) - W(T.r)| + I(T.l) + I(T.r) & size(T)>0
\end{cases}$$

Examples

  a.)  *        b.)  *
      / \          /   \
     *   5        *     *
    / \          / \   / \
   *   3        1   5 3   3
  / \
 1   3

Tree a. has imbalance 5 (2 + 1 + 2) and tree b. has imbalance 4 (4 + 0 + 0).

Consider the following problem:

Input: a list of $n$ positive integers $W = (a_1, \ldots, a_n)$, and an integer $k$.

Query: is there a binary tree $T$ with leaf weights $W$
such that $I(T) \leq k$?

  Is this problem $\mathsf{NP}$-hard?

The case $k = 0$ is easy.
There is a simple algorithm which goes as follows ($Q$ is a priority queue):

  for $w \in W$: $Q.push(w)$
  while $Q.size > 1$:
  2.1. pop the two smallest elements $w_1$ and $w_2$ form $Q$.
  2.2. if $w_1 = w_2$ then $Q.push(2*w_1)$
  2.3. else return "No"
  return "Yes"


texts: Approximation Algorithm for the Unique Coverage Problem

texts:
I was reading about the $\mathcal{O}(\frac{1}{\log n})$ approximation algorithm for the Unique Coverage Problem from these notes.

The gist of the algorithm is as follows:

  Partition the elements into $\log n$ classes according to their degrees, i.e., the number of sets that cover the element. So class $i$ contains all the elements which are covered with at least $2^i$ and at most $2^{i+1}$ sets.
  Let $i$ be the class of the maximum cardinality.
  Choose any set with probability $\frac1{2^i}$

Then in Lemma 3, they go on to show that

  Lemma 3: The expected number of the elements uniquely covered from class $i$
  is $\frac{1}{e^2}$ fraction of the element in class $i$.

I was able to follow the algorithm till here but I am completely stumped as to how they arrived at the statement immediately following lemma 3

  Therefore, the total profit of uniquely covered elements is at least
  $\frac{1}{e^2 \log n} \times \text{opt}$

How did they arrive to this conclusion? They didn't even show what the upper bound is for this maximization algorithm. What am I overlooking?

It is trivial to prove that the expected number of unique elements covered by the algorithms is $\frac{n}{e^2}$ since it directly follows Lemma 3 but that is about all that I am able to observe :/


texts: How can I find spans where the distance between two poly-lines is more or less than some threshold?

texts:
I have two poly-lines. I would like to find segments of these lines where the minimum distance between them is higher (or lower) than some threshold.

I.e. I want to find the parts of the lines highlighted in squiggly pink here:

My best attempt is to split each line into some equally sized segments, and then use dynamic programming to find the closest corresponding points on each line. This is efficient, and works, but will of course be off by some amount from the real points where the minimum distance is reached. Making the segments smaller will make the solution better (but slower), but I have a feeling a continuous and exact solution is possible?


texts: A HUGE GAP in time: Complete problem for $\mathrm{strict}$-$\mathrm{SUBEXP}$

texts:
Normally, $\mathrm{SUBEXP}$ is defined to be the intersection of all $\mathrm{DTIME}(2^{n^\epsilon})$. That means each problem in this class has infinitely many exponential time algorithms with the exponent arbitrarily polynomially ($n^\epsilon$) small.

We all know that another closely related definition is also lurking around. Denote this stricter notion by $\mathrm{strict}$-$\mathrm{SUBEXP}$, we mean the class of computational decision problems such that  for each one of them, there exists ONE algorithm that runs in time less than $2^{n^\epsilon}$ for every $\epsilon$.

Is there any m-complete problem for $\mathrm{strict}$-$\mathrm{SUBEXP}$?

m-completeness: being complete by a Karp polynomial-time reduction


texts: I think the number of cliques in a graph is generally exponential in the of vertices of that graph. Does anyone know any reference for that?


texts: Does a graph diameter equal to DFS tree depth?

texts:
given an unweighted graph, does the graph diameter equal to the maximum DFS tree depth?

and the same about BFS?

regarding both directed and undirected graphs.

thanks :)


texts: Is there an example of Dinitz's algorithm running with the worst time complexity?

texts:
I am trying to find a network, where Dinic's algorithm makes $|V|^2*|E|$ steps. Clearly it cannot be a network with $3$ or less vertices, but I am not able to come up with a working example for quite a while now.

Any idea?


texts:
My professor mentioned the below statement in class but without a proof. I am trying to prove it for myself as I don't understand 100% why this is always the case.
Given is A, a subset of {0,1}$^*$.

ε $\in\ A^+$ <-> ε $\in\ A$, where ε is the empty word.
I thought of doing a proof by contradiction to show -> by assuming the empty word is not part of A$^+$.

Any help is much appreciated!


texts: Can I say ≤ O(f(x)) rather than = O(f(x)) if the bound is not tight?

texts:
Suppose I just invented merge sort, but due to my limited ability was only able to prove that the running time is $O(n^2)$. However, I suspect that the running time is actually better (in reality it's $O(n \log n)$).

Technically in my paper I should say “runtime $=O(n^2)$”, but it’s somewhat misleading because people think I mean it's a tight bound (i.e. people generally  think big O actually means big theta). Therefore, I am considering saying “runtime $\leq O(n^2)$”, even though it's technically redundant. Obviously I will explain in the text what I mean, but I'm saying it many times for different equations and I don't want to keep repeating myself.

I am aware of the definitions of big O, Omega, Theta, but which is clearer in a CS paper? The paper is related to machine learning.


texts: How to cover maximum points with a fixed length line segment?

texts:
The problem is defined as:

  Given a set of $N$ points $(x_1, x_2, x_3, \ldots, x_n)$ and $L$ the fixed length of a segment.

  Find the number of maximum points which you can cover with a segment line of length $L$.

  Ranges

  $1 \leq N \leq 100 000$

  $1 \leq L \leq 10^{10}$

  $0 \leq x_i \leq 10^{10}$

I call sub-optimal ranges, ranges which are in the form $[x_n,x_n+L]$. The optimal range is the one which contains the maximum points of all ranges.

I've tried to consider the problem using that algorithm (pseudo-code):

Let be S, the set which contains all the N points.
Let be R, the set which contains ranges.
Let be maxPoints, the number of maximum points that we can have (set it to 0).
For all points p I have in my set S
     Store in R the range $[p, p+L]$
For all ranges r I have in my set R
     nPoints = 0
     For all points p I have in my set S
         If the point p is in the range r, then increment nPoints
     maxPoints = maximum value between maxPoints and nPoints
Display maxPoints

I think that the complexity of this algorithm is $O(N^{2})$, is there a way to make it faster? And is it really correct (in the sense, that it solves all cases of this problem).


texts: Intuitive way to understand the triangle spectrum?

texts:
Image on the top is in the time domain, image on the bottom is in the frequency domain.

Why do we see -2T and 2T on image of the time domain and why do we see -1/2T and 1/2T of the image in the frequency domain?


texts:
In Sipser's Theory of Computation book, it is stated while reducing ATM to REGULARTM

  We let R be a TM that decides REGULARTM and construct TM S to
  decide ATM. Then S works in the following manner.

S = “On input , where M is a TM and w is a string:

Construct the following TM M2.

M2 = “On input x:

If x has the form 0n1n, accept .
If x does not have this form, run M on input w and
accept if M accepts w.”

Run R on input < M2>
If R accepts, accept ; if R rejects, reject .”`

My question is, shouldn't M2 reject x of the form 0n1n?


texts: Example of inductive sets that are neither least nor greatest fixed point

texts: Do there exist a set of inductive rules and a fixed point of these rules but is neither the least nor the greatest fixed points?


texts:
I was told that the fastest possible algorithm for integer multiplication is $O\left(n{\log}(n)\right)$. Why would this so?

Can you please show why the fastest multiplication algorithm would have such a time complexity?


texts: Maximum bipartite matching when some nodes must be matched

texts:
Consider the problem of finding a maximum cardinality bipartite matching under the additional condition that some set $S$ of nodes (all lying on the same side of the bipartition) must be matched.

Can this problem be reduced to (ordinary) bipartite matching? Bipartite matching can be solved in $O(m \sqrt{n})$ by Hopcroft Karp or $O(n^{\omega})$ where $\omega$ is the exponent of matrix multiplication due to a recent result, or $\widetilde{O}(m^{10/7})$ in terms of the number of edges m. Do these running times carry over to this problem? I think Hopcroft-Karp can produce the same running time with some modifications, but am not sure about the others; so I'm wondering if a simple reduction to matching exists -- this would allow one to bypass an analysis of the above papers.


texts: Best random permutation employing only one random number

texts:
The ideal random permutation algorithm of Fisher and Yates (Algorithm P in Knuth vol.2) for a sequence of $n$ objects requires $n-1$ random numbers.

In some card games one first does a "cut" and then a riffle shuffle. The cutting point is a random value, the subsequent shuffling could be considered as deterministic. That is, only one random number is being used to generate the permutation, which understandably can't be ideal. On the other hand, theoretical perfection isn't always necessary in practice. I like hence to know whether, if one keeps the constraint of using one random number in a run, the quality of randomness of the permutation obtained couldn't eventually be improved through certain appropriate modifications of the procedure commonly employed in card games, if one is willing to take the trade-off of more work/time, inconvenience, etc. Such trade-offs may not be acceptable for real games, but I suppose there may be other practical applications that could advantageously exploit the same idea, thus without being required to acquire, e.g. via a chosen PRNG, the larger number of random numbers needed for executing the algorithm of Fisher and Yates.


texts: Proving a tighter upperbound (big-O) for this problem

texts:
Motivation
So the other day I had fun providing a new solution to this famous question. In the analysis part I showed that my little algorithm has space complexity: O(k) and Ω(log(k)). However, my rough logic says that we should be able to prove a tighter bound of O(min(k,log(n))), but I was unable to prove it. Moreover it seems like an interesting, general-case problem.

To save time for the reader I have changed my space complexity problem to an equivalent complexity problem (the complexity of a function [not of space or time]):
Data:
Array of size k; where elements, e, are unique integers: 0 <= e < n, for some n.
Events:
Find the average (rounded down) of the elements.
Randomly discard either all the elements > than the average, or all the elements <= the average.
We then do the same thing to the reduced array size.
We keep repeating the above steps until the array is size 1.
My Question:
Is it O(min(k,log(n))) on the number of times average is counted? and if so, how do we prove it? (NOTE that we don't care about the time it takes to calculate the average or remove the elements. This is because this questions is deliberately designed to be equivalent to my space-complexity problem.)

My thoughts:
It seems really intuitive that it's O(min(k,log(n))) because if k is n, then taking the average will always divide the elements in half. However, I can't seem to prove that it doesn't sometimes perform worse when k < n.
Thinking about this a bit we recognise that having outliers is really what makes for bad performance, so I try to imagine a worst-case scenario:
array = [1, 2, ..., (x-2), (x-1), (n-1)], where (x-1) < average < (n-1)
In this scenario, we in worst-case reduce the array size to x-1; however, by increasing k by adding any number of elements, e: (x-1) < e < (n-1), the worst-case array size (for the next iteration) is still x-1.
Moreover:
average = (x(x-1)/2 + n-1)/x
Thinking about the complexity, for a given n, worst case x:
x = average
=> x^2 - x^2/2 + x/2 = n-1
=> O(x) = O(sqrt(n))
and here x represents the biggest sub-size.
So in this artificial "worst case" scenario, we get O(sub-array size) = O(min(k,sqrt(n))), which kind of implies that the overall complexity = O(min(k,log(sqrt(n)))) = O(min(k,log(n))).
However, this proof is quite informal and I'm not sure how to show that this genuinely represents the worst-case scenario.


texts: How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable?

texts:
Let a language A =  {(M,w) : M is a TM and w is a string such that w is accepted by M in an even number of steps}.

How can I prove that this is undecidable? I have considered trying to build the ATM proof assuming this language. Language A can cover acceptance under even steps but how would I cover acceptance under uneven steps? Language A would reject in that case. How would you go about trying to build the proof via this path?

Another thing I wonder is if Rice's theorem covers this language. Would this be considered a functional property? Could I use it to prove the undecidability of this language?

Thanks


texts: Range Query Question: Removing Items from a List

texts:
My task is to input a given list of size N, then process N queries that remove an item from the list and then print it to the screen.
The input
5
2 6 1 4 2
3 1 3 1 1

would represent having a list {2 6 1 4 2}, then outputting and removing the third, then first, then third, then first, then first elements of the list, in that order. The correct output would be 1 2 2 6 4.
My first idea to solve this problem runs in O(N^2) time; simply use a dynamic array to achieve O(1) random access and worst-case O(N) removal. However, as N can be up to 10^5 in this problem, this solution is way too slow. I think that the problem is probably looking for an O(NlogN) solution.
In the end, I read the hints for this problem, and they said that this problem has an O(NlogN) solution involving Range Queries. I've learned about Segment and Fenwick Trees, as well as the sparse table algorithm, but I still don't know how to solve this problem. Can somebody please point me in the right direction?


texts: How to make NFA remember its first step?

texts:
I have to design an NFA that will take the strings "token" and token.

I can use $\lambda$ or " to the first state, but then how do I know on the final state if it should have end quotes or not?


texts:
The following is an algorithm for generating "Taxicab numbers" using a priority queue (pq). Vector is an arbitrary data type that allows for storage of two number and their cubed sum. For those unaware (although you really don't need to know), a taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: $a^3+b^3 = c^3+d^3$. An example would be $1729 = 12^3 + 1^3 = 10^3 + 9^3$.

for i = 1..n
 pq.insert( Vector(i^3+i^3,i,i) )

prev = Vector(0, 0, 0)

while not pq.empty()
 curr = pq.deleteMin()
 if prev[0] == curr[0]
      print curr[0] is a Taxicab number that can be expressed as
      prev[1]^3 + prev[2]^3 and curr[1]^3 + curr[2]^3
 prev = curr
 if curr[2] < N
     j = curr[2] + 1
     pq.insert( Vector(curr[1]^3 + j^3, curr[1], j) )

I know inserting an item into the priority queue is $O(\log n)$ but I am not sure how this relates to space usage and runtime. Can someone help?


texts: Polylogarithm growth rate proof using Polynomial growth equation

texts: In the CLRS, there's this part, where it's shown that $$\lim_{n\to\infty}\frac{(n^b)}{(a^n)} = 0$$ In the same chapter, it uses the aforementioned equation to prove that any polylogarithm function grows slower than any polynomial one, thus, $$\lim_{n\to\infty}\frac{\log b^n}{ n^a}$$ It does that by substituting lgn for n and 2^a for a in the first equation. How is it allowed to substitute the terms and prove the latter equation.


texts: Is the language of words that contain a square regular or context-free?

texts:
$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} ,   w=xyyz \wedge y \neq  \epsilon   \}$

I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and prove. The word itself $ww$ above the alphabet $a, b$ is not context-free, but here we have $(a + b) ^ {*}$ before and after, and it changes a lot, I think.

Is it possible to describe this language with a regular expression? For example
$$(a + b) ^ {*} (aa + bb + abab + baba) (a + b) ^ {*}$$
So is the language regular?


texts:
Consider an instance of TCP’s Additive Increase Multiplicative Decrease(AIMD) algorithm where the window size at the start of the slow start phase is 2 MSS and the threshold at the start of the first transmission is 8 MSS. Assume that a time out occurs during the fifth transmission. Find the congestion window size at the end of the tenth transmission.

I am bit confuse in this concept.
What I know :

Slow start and congestion avoidance are different.
Slow start is used in conjunction with congestion avoidance.

Window size for 1st transmission = 2 MSS
Window size for 2nd transmission = 4 MSS
Window size for 3rd transmission = 8 MSS
threshold reached, increase linearly (according to AIMD)
Window size for 4th transmission = ?? MSS
Window size for 5th transmission = ?? MSS
time out occurs, resend 5th with window size reduced to half (according to AIMD)
Window size for 5th transmission =  ??? MSS

What will be the Window size for 4th transmission ? 9 MSS or 10 MSS
It means i want to ask you after threshold window size should increase linearly means it  should increase by 1 MSS or 2 MSS  ( 2 MSS is given in example ) ?

What will be window size for 5th transmission ? Will it be 1 MSS or 2 MSS ?

Please clear my concept. I am so confused.


texts: What determines the "speed" of a programming language?

texts:
Suppose a program was written in two distinct languages, let them be language X and language Y, if their compilers generate the same byte code, why I should use language X instead of the language Y? What defines that one language is faster than other?

I ask this because often you see people say things like: "C is the fastest language, ATS is a language fast as C". I was seeking to understand the definition of "fast" for programming languages.


texts: How can I prove that a Regular Language is closed under Union given two languages with different alphabets?

texts: I need some help to prove that a Regular Language is closed under the union, using a DFA with two differents alphabets.


texts: What is the relationship between minimum vertex cover and minimum clique cover

texts:
Question:
 What is the relationship between minimum vertex cover of a graph G and minimum clique cover of conflict graph of G?

Thanks!

I believe the minimum vertex cover of G is equivalent to minimum clique cover of the conflict graph of G, or their sizes are  equal, but today I find a counterexample.

Example: in the figure below, a minimum vertex cover is {1, 2}, but the minimum clique cover contains one partition, that is vertext set {$e_1, e_2, e_3$}. The size of minimum vertex cover is 2, while the size of minimum clique cover is 1.

A graph is an ordered pair G = (V, E) comprising a set V of vertices, nodes or points together with a set E of edges, arcs or lines, which are 2-element subsets of V (i.e., an edge is associated with two vertices, and the association takes the form of the unordered pair of the vertices).

A vertex cover of a graph G is a set S of vertices of G such that every edge of G has at least one of member of S as an endpoint.

A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph.

A conflict graph is the graph G = (V, E) where every edge in E is represented by a vertex. Two vertices are adjacent if and only if the edges in E these vertices correspond to intersect each other.

A clique cover or partition into cliques of a graph is a partition of the vertices of the graph into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible.


texts:
I have two arrays, namely $a$ and $b$. Both have the same length $n$. I have to find the maximum value of $\sum a_i b_j$, in which every element can be used at most one time. My algorithm for solving this problem is:

Sort both $a$ and $b$ in non increasing order.
Pick the values from the array in order of greatest to smallest. Calculate their product and add them to sum.

On the arrays $a = \{2,3,4\}$ and $b = \{4,5,6\}$, the algorithm runs as follows:

Firstly, sorting the arrays: $a = \{4,3,2\}$ and $b = \{6,5,4\}$.

Then picking values from the first to last, gives the answer $(4\cdot6) + (3\cdot5) + (2\cdot4) = 24 + 15 + 8 = 47$.

Here what I have used is a greedy algorithm. How to prove its correctness? What I want to know is, how to prove that this algorithm always gives the maximum answer?


texts:
For an assignment I have to program an application to schedule conversations.
There is an event where representatives of the elementary schools talks with the representatives of high schools. They will talk about the students that will be transferred to the highschool. There are approximately 200 elementary schools and 40 high schools that will be participating in this event. The schools already know which student is transferring to which high school. The conversations will only be between representatives of E and H from student that will be transferring to H.

The rules are:

The duration of each conversation is based on the amount of
students per representatives.Each conversation last 5 minutes per student. If a group consist of 1 student, this conversation last 10 minutes.
No timeclashes
All the students of the same group will be scheduled together, so, a
representatives will only face the same representative once.
Timespan is 13.00-19.00
The waiting time of a representative is at most 20% of his time. A
waiting time is an empty timeslot between the 1st and last
conversation.
Schedules for 2 days
Each representatives participate for 1 day.

The problem is that I know that this is hard to solve, but I dont know if it's NP-hard. Right now I only know this problem is similar to a Job Shop Problem. What can I do to proof that my problem is NP-hard? I read that I need to reduce a known problem to my problem. But how do I do this? I have read different articles and books, but I still don't understand the steps to do it.


texts: How to prove the correctness of inside-out shuffle algorithm

texts:
I've read this similar question How to prove correctness of a shuffle algorithm? and I understand the answer. However I still couldn't figure out how to apply that inductive proof to a similar shuffle algorithm --- inside-out shuffling algorithm, which is as follows:

  for i from 0 to n − 1 do
      j ← random integer such that 0 ≤ j ≤ i
      if j ≠ i
          a[i] ← a[j]
      a[j] ← source[i]

source is the input array and a is the output array.

Another question I have is: would it be the same if I changed the code to the following:

  for i from 0 to n − 1 do
      j ← random integer such that 0 ≤ j ≤ i
      swap(a[j], a[i])

This is similar to the knuth algorithm except that it chooses a random element in the first i elements instead of last n-i elements. I have the feeling that they shouldn't both work, but I'm not sure.


texts: Reduction from a m-coloring to a m-partition

texts:
define a m-partition as: Given an undirected graph G = (V, E) and an integer j. Does there exist a partition of the vertices into m parts {V1, V2, ... , Vm} such that at least j of the edges have their endpoints in different parts of the partition?

I started by partitioning the graph into k parts: each partition represents 1 colouring of the graph. From there, I thought of reverting all edges: so converting all edges into non-edges and vice-versa. I'm stuck here. Am i on the right track? Thank you.


texts:
A language $L$ is in $SPP$ if there is a $GapP$ function $f$ such that

$x\in L\implies f(x)=1$ and $x\not\in L\implies f(x)=0$.

By $x\not\in L$ I think we mean $x\not\in SPP$ correct?

I would have thought $x\not\in L$ if there is no such $f$. Why is it not defined this way? In this case we have $x:f(x)\not\in\{0,1\}$. Is such $x\in L$ or $x\not\in L$?

I guess my query is it is not clear that in this case $x\in L$ and $x\not\in L$ cover all strings?


texts: What the State is, and Where it comes from, when Generating Reachability Graphs

texts:
For Timed Automata, I found Figure 1 below. For Coloured Petri Nets I found Figure 2. Both are for "Reachability Graph Construction".

However, they don't describe where they got the states from (Figure 3), for generating the reachability graph. They assume you have "states" to generate a reachability graph, but I'm not sure what these states are. In the timed automata case, I'm not sure the automata "states" are what they are describing, it seems like by "state" they mean the program state after the automata runs (or on each step). Likewise for Petri nets, the state isn't the place or the transition, but the program state. At least that's what I'm getting.

Given that, my question is how to construct the program state, so that I can then construct the reachability graph. In addition, I'm wondering what the states actually are composed of. What the state is (boolean predicates, temporal logic expressions, data, etc.).

Some more detail. From here (on Petri nets):

  A marking $M'$ is reachable from a marking $M$ if $M[s\rangle M'$ for some $s \in T^*$... The reachability set Reach(N) of N is the set of
  all markings that are reachable from the initial marking.
  [The markings have to do with the data associated to a place (a Petri net node)]... A Petri net $N = (P, T, F, M_0)$ induces several standard structures on which first-order logics may be interpreted... To specify properties of structures ... obtained from a Petri net $N$, we introduce a first-order logic FO with atomic predicates $x \to y$, $x \overset{*}{\to} y$, $x \overset{+}{\to} y$ and $init(x)$. [Then they go into the model checking part].

That just demonstrates how the Reachability Graph Construction is left out. That is, what it is composed of (in some detail), and how to construct it.

Figure 1 $\downarrow$

Figure 2 $\downarrow$

Figure 3 $\downarrow$


texts: Why is the orthogonal line segment intersection algorithm $O(n\log n+R)$ instead of $O(n\log n + Rn)$?

texts:
In the same lecture notes without providing many details it says that the complexity of the algorithm which uses a balanced search tree is $O(n\log n+R)$ where $R$ is the total amount of intersections.

However I don't understand why this is the case.

Suppose that the sweep line is travelling from top to bottom. Whenever we encounter a vertical line segment, we pick its $x$ coordinate and add it to a search tree. Assuming that we are using a balanced search tree like AVL, this operation will take $O(\log n)$ time. Now when we reach an end point of a vertical line segment, we remove its $x$ coordinate from the search tree, which is going to take $O(\log n)$ time as well.

Whenever we encounter a horizontal line segment defined by points $A$ and $B$, we have to do a range search on our search tree and use the range defined by these two points, that is $(A.x, B.x)$

Now how is this range search going to happen? We use $A.x$ and travel to the left most point in the search tree, and do the same for $B.x$, we can do this in $O(2\log n)$.

All the points in our tree between these two end points are going to be the intersecting the horizontal segment, which is going to be let's say $R$ in total, so $O(2\log n+R)$ in total.

We do this $n$ times (the amount of horizontal segments) so we get a complexity of $O(2n\log n+nR)$.


texts: How earliest that the data TLB (Translation Lookaside Buffer) can be accessed in an instruction execution pipeline?

texts:
In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is:

List item before effective address calculation has started
during effective address calculation
after effective address calculation has completed
after data cache lookup has completed

=====================================================================

I think answer is 3.

Reason- Virtual address is given for TLB look up. TLB -Translation Lookaside Buffer, here Lookaside means during Address translation (from Virtual to Physical). But virtual address must be there before we look into TLB.

Please, explain which is the correct option. According to book the answer is 2.
I think that option 2, is wrong as it is explaining for physical address resolution and not for effective address calculation.


texts: Pumping lemma to show a language is not context free

texts:
I have started pumping lemma for context-free grammar by reading Sipser's book and there are two questions right at the end end of the topic which I don't understand how to solve or where to start from?

I have to show that the following languages are not context-free

    L = { w | w = 0a  1 b   2 ab   where a, b are >= 1 }

and another question that goes like this:

    L = { w | w = x11x21...1xk where k >=0 and each xi is ∈ {0}*, and xi ≠ xj whenever i ≠ j

How would I tackle this problem? I understand pumping lemma in general but for these questions I can't seem to apply it.


texts: Where can I find a reasonable NLP CFG or CSG for English?

texts:
I'm looking to do natural language parsing and looking for how the CFG (or CSG) should be defined for English.

Surely one'd expect to find one from the internet already, but do you know where?

It needs to be in "formal grammar" form, not an implementation (e.g. a Python library).

It has to allow for as wide range of sentences as possible to be parsed correctly.

Something that I could be looking at:

S -> NP VP | VP
NP -> D N | N | N NP
VP -> V | V NP | V PP | V NP PP
PP -> P NP

But how sufficient is this?

Related:
https://english.stackexchange.com/questions/32447/is-there-an-ebnf-that-covers-all-of-english


texts: Do we include Transmission delay in Round trip time?

texts: Is RTT = $2*T_{Propagation delay}$ only. Or we include Transmission delay to send packets as well. Some examples include Transmission delay some not. I'm confused. Can anyone help.


texts: The "complexity" of the Turing machine state specification

texts:
Suppose we want to represent some arbitrary Boolean function $f(x_1,x_2,...,x_N)$ on $N$ bits. We can explicitly specify such a representation using the disjunctive normal form. For "most" Boolean functions, this representation will be of length exponential in $N$, and incompressible (as per Shannon). We will assume we have chosen such an incompressible function.

We can build a Turing machine corresponding to this circuit, which ACCEPTs an input $\mathbf{x}$ if and only if $f(\mathbf{x}) = 1$. We can then ask what complexity such a Turing machine would have.

Now, the subtlety is: since our function is incompressible, any attempt to physically represent it must, naively, be "exponentially large"... in some sense. But we can "hide" the "exponentialness" of this in various places based on how we define our Turing machine, which would appear to change its computational complexity.

How does complexity theory handle this case?

Now, if we were treating the DNF as part of the input, we could create a Turing machine and feed our DNF and some bitvector to evaluate as an "exponential-length" input. We would then know that our Turing machine would take time $O(2^N)$ just to read the DNF, so accounting for everything relative to $N$, we're in (at least) exponential time.

But, as we are "building the circuit into" the specification of the Turing machine itself, we can recognize this language in $O(N)$:

Check if the first bit is 0 or 1. Then, we have a branch to two states corresponding to $f(0,x_2,...,x_N)$ and $f(1,x_2,...,x_N)$, and transition according to the input.
Repeat with the second bit. For each possibility, we have two more states, yielding four states total: $f(0,0,...,x_N)$, $f(0,1,...,x_N)$, $f(1,0,...,x_N)$, and $f(1,1,...,x_N)$.
Continue branching until the end, and then ACCEPT/REJECT according to the specification of our function.

Of course, our Turing machine is "pathological" in that it now requires an exponential number of states. But, technically, since time complexity does not take this into account, it looks like we've gone from $O(2^N)$ to $O(N)$.

We can "fix" this to obtain a Turing machine with only one nontrivial state that recognizes the language in $O(1)$! Simply change the alphabet to be of size $2^N$, so that bitvector is viewed "atomically" as a single entry in the alphabet. Then we encode membership in our Boolean function by a single state transition to ACCEPT or REJECT based on the input. Of course, now the problem is that our "$O(1)$ machine with one state" has an exponentially large state transition table.

My question: What is the complexity of our language, expressed relative to $N$? Naively, I would like to say it's in EXPTIME, since the "exponential speedups" given by the last two Turing machines are clearly pathological, but I don't normally see this metric accounted for anywhere in complexity theory.

In general, how does complexity theory handle this? Are such pathological machines explicitly excluded in the main results of the field, and if so, what criterion do we use for excluding them?


texts:
I am trying to understand the definition of skewed circuits in these slides which is given as follows:

A circuit is skew if in each product gate, at least one product has degree $\le 1$.

I think author wants to say that each product gate is either a leaf node or one level above the leaf node.


texts: NP-hardness of problem with indices and subsets

texts:
Consider the following problem.

  Let $S=\{1,2,\dots,n\}$, and $A_{ij}\subseteq S$ for $i,j\in S$. Does there exist a strict subset $T\subset S$ such that for all $j\not\in T$, there exists $i\in T$ for which $T\subseteq A_{ij}$?

(For $T=S$, this is trivially true, so we disallow it.)

The problem is in NP: given a set $T$, it is easy to verify whether it satisfies the property. Is it also NP-hard, or does there exist a polytime algorithm?

I tried to construct such a set $T$ greedily by starting with some $i\in S$. If $i\in A_{ij}$ for all $j\not\in i$, we can choose $T=\{i\}$ and are done. Otherwise, there is some $j$ for which $i\not\in A_{ij}$, so we can try adding $j$ into the set, and iterate on the new set $T=\{ij\}$ until the process stops. The problem is that there is no guarantee that this will stop before $T$ is the whole set $S$ even if such $T\neq S$ exists.

I also thought about dynamic programming, but it's not clear what the subproblems should be in this setting. On the NP-hardness side, I thought about reducing from some problems related to sets. There are problems like subset-sum or partition, but those concern sums of elements and are not directly relevant.


texts: Can you reduce every decidable language to a regular language?

texts:
One of my previous questions on an exam was the following

Can you reduce a decidable language to a given regular language? (decidable language $\leq _m$ regular language).
If so, does this mean that you can reduce every CFL to a regular language?

The reductions are all referring to many-one reductions. My intuition tells me that this is possible as all regular languages are also decidable.


texts: Proving L = {$ { a^{2^n} \ | \ n \ge 0 } $} is not regular by use of Pumping Lemma

texts:
I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.

We have the language L = {$ { a^{2^n} \ | \ n \ge 0 } $} and we need to prove that it is not regular by use of the pumping lemma.

(i.e. L is words whose length is a power of 2: a, aa, aaaa, aaaaaaaa etc.)

I appreciate the concept of the proof so here we go:

Assuming regularity of L and using the Pumping Lemma, we have $ {a^{2^p}} = {xyz}$ where:

a) ${|y| > 0}$

b) ${|xy| \le p}$

c) $xy^iz \in L \ \forall \ i \ge 0$

(also $ |xyz|\ = 2^p \ge p$)

(notice both x and z can be empty)

I choose $ i = 2$ to get $xy^2z$ so (since $y>0$) $|xy^2z| > 2^p$

I understand that the next step is trying to prove  that $|xy^2z| < 2^{p+1}$ so that the final result is $2^p < |xy^2z| < 2^{p+1}$ and so $xy^2z$ cannot be an element of L.

However if $|y| = p$ and so $|x| = 0,\  |z| = 0$ then this is not possible as taking $y^2$ is just doubling the length of the word which makes another word that fits the language.

Am I missing something important? I have found proofs on multiple web pages (see below) that just seem to assume y cannot be of length p but as far as I can see this isn't the case.

http://cs.geneseo.edu/~baldwin/csci342/fall2012/0928pump.html
http://www.cse.buffalo.edu/courses/cse396/content/hwSol-5.pdf

Thanks very much in advance and please let me know if there is anything I should clarify.


texts: Monotone property of heuristic in $A^*$ algorithm

texts:
In the $A^*$ algorithm, the optimality of the path is guaranteed when the heuristic has the property of being admissible or monotone\consistent.

I was able to understand the admissible property, however, I am not able to wrap my head as how the monotone property guarantees that any node can be explored only once (i.e., the path that lead to that node has the shortest path). As stated in the wiki page ,

  "If the heuristic $h$ satisfies the additional condition $h(x) \le d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge), then $h$ is called monotone, or consistent. In such a case, $A^*$ can be implemented more efficiently—roughly speaking, no node needs to be processed more than once (see closed set below)—and $A^*$ is equivalent to running Dijkstra's algorithm with the reduced cost $d'(x, y) = d(x, y) + h(y) − h(x)$."


texts: Creating a Deterministic Push-Down Automaton for the Union of two languages

texts:
Suppose, we have $L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$ and $L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$. Now we want to create a Deterministic Push-Down Automaton for $L_1\cap L_2$

I've created PDA's for both languages:

$M'=(Q,\Sigma,\Gamma,\Delta,s,F)$ with $\Sigma=\{a,b\}$, $\Gamma=\{\}$, $Q=\{1,2,3,4\}$, $F=\{0\}$, $s=\{0\}$ and
\begin{align}
\Delta=\{&(0,a,\lambda,1,\lambda),(0,b,\lambda,0,\lambda)(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,3,\lambda),(2,b,\lambda,2,\lambda)\\
&(3,a,\lambda,0,\lambda),(3,b,\lambda,3,\lambda)\}
\end{align}
where $\Delta\subseteq Q_{old}\times (\Sigma \cup \{\lambda\})\times(\Gamma\cup \lambda)\times Q_{new}\times\Gamma^*$

and

$M''=(Q,\Sigma,\Gamma,\Delta,s,F)$ with definitions above and $\Sigma=\{a,b\}$, $\Gamma=\{\}$, $Q=\{1,2,3,4,5,6\}$, $F=\{6\}$, $s=\{1\}$ and
\begin{align}
\Delta=\{&(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,2,\lambda),(2,b,3,\lambda),(3,a,\lambda,4,\lambda),(3,b,\lambda,1,\lambda),\\&(4,a,\lambda,5,\lambda),(4,b,\lambda,3,\lambda),(5,a,\lambda,2,\lambda),(5,b,\lambda,6,\lambda),(6,a,\lambda,6,\lambda),(6,b,\lambda,6,\lambda)\}
\end{align}

$M'$ accepts $L_1$ and $M''$ accepts $L_2$, but how to construct $M^{\star}=M'\cap M''$ which accepts $L_1\cap L_2$?

I know, that we could possibly do this with Deterministic Finite Automata, but I want to know how it would work with PDA's.


texts: Why can PDAs have infinite stack but FSMs cannot have infinite state?

texts:
A Finite State Machine cannot accept the language
$$L = \{ 0^n1^n \mid n > 0  \} $$
because it will require infinite amount of memory to remember the number of zeros. But a Push Down Automaton can recognize it with an infinite stack.
Why are we allowing infinite storage for the stack of PDA but not for the states of an FSM? If we can do with an infinite stack, we can also do it with an infinite FSM. So, why is there no "Infinite State Machine"? What's the problem with it?


texts:
I was reading an article on Construct binary palindrome by repeated appending and trimming. The problem is Given n and k, Construct a palindrome of size n using a binary number of size k repeating itself to wrap into the palindrome. The palindrome must always begin with 1 and contains maximum number of zeros.

I solved the problem using this algorithm-

I will declare a string of size n with all the entries 0.
Leftmost character has to be 1, so to be a palindrome rightmost should also be a 1 .
Now after every k-1 places starting from start, I will put a 1.
And before every k-1 places starting from end, I will put a 1.

This algorithm has O(n) runtime. Is there anything wrong with this algorithm?

In the article, They have declared an array of size n, and then laid the index of the k sized binary to hold into an array, for example if n = 7, k = 3 arr becomes [0, 1, 2, 0, 1, 2, 0]. And then connected the indices of the k sized binary which should be same by going through the property of palindrome which is kth and (n – k – 1)th variable should be same. And then they apply dfs on 0.
For more clearance, please see the article above.

We already know which nodes would be connected to index 0 (that I have done in my algorithm), then why are we connecting all the indices ?

Is there something, I am missing?


texts: Prove that this family of hash function is $3$-wise independent, but not $4$-wise independent

texts:
Consider the hash function mapping $w$-bit keys to hash values in
  $\{0,...,m-1\}$. Suppose $w=cr$. Interpret a $w$-bit key $x$ as a
  vector $(x_1,...,x_c)$ of $c$ $r$-bit keys.

  Consider the hash family:

  $$H = \{h_{T_1,...,T_c}:T_i \in \{0,...,m-1\}^{2^r}\}$$

  where

  $$h_{T_1,...,T_c}(x) = \sum\limits_{1\le i \le c}T_i[x_i]\mod m$$

  Prove that $H$ is $3$-wise independent, but not $4$-wise independent.

  $H$ is $k$-wise independent if for inputs $x_1,...,x_k$ and output
  $v_1,...,v_k$, $\Pr[h(x_1) = v_1 \wedge ... \wedge h(x_k)=v_k] =
 \frac{1}{m^k}$

So I can certainly see why $H$ is $1$-wise and $2$-wise independent if we're choosing inputs to the hash function that must be different from each other. However, I'm having a lot of trouble seeing why the family is not $4$-wise independent, which I think lends greatly to my difficulty in proving that the family is $3$-wise independent.

So for the family to not be $4$-wise independent, if we have inputs $x_1,...,x_4$ and outputs $v_1,...,v_4$, $\Pr[h(x_1)=v_1\wedge...\wedge h(x_4)=v_4]\not = \frac{1}{m^4}$. I am trying to think of a counterexample where this will not be the case, but it seems like we need, for example, $x_4$ to be constructed in such a way that $v_4$ can be attained by some combination of $v_1,v_2,v_3$. However, all of $x_1,...,x_4$ are $w$-bit keys, so even if $x_4$ had bits taken from each of $x_1,x_2,x_3$, the output $v_4$ would still be some random sum corresponding to the $c$ $r$-bit blocks accessing each $T_i$.

Is there something I'm missing here? Perhaps it's not possible for $v_4$ to be some combination of $v_1,...,v_3$, but how else would we show that $H$ is not $4$-wise independent?


texts: Is it correct to use the pinhole camera model to get the mapping of a 3D line to a line in an image?

texts:
I've been working on a computer vision project in which I'm using the pinhole camera model to map one line of the world to one line in an image.

From previous research on the topic, I know that it is possible to map a point in the 3D world to a point in one image using the projection matrix obtained by calibrating the camera you're using to get the images of the 3D world. This mapping can be done as follows:

$ \lambda \begin{bmatrix}u \\ v \\ 1\end{bmatrix} = P \begin{bmatrix}X \\ Y \\ Z \\ 1\end{bmatrix}$,

in which $(u,v,1)$ are the coordinates of the point in the image, $(X,Y,Z,1)$ are the coordinates of the same point in the world and $P$ is the projection matrix.

A line in the image can be defined as:

$\begin{bmatrix}A & B & C\end{bmatrix}\begin{bmatrix}u \\ v \\ 1\end{bmatrix}$,

in which $(A,B,C)$ are the parameters used to describe the line. My research also taught me that perspective projections preserve lines, i.e., a straight line in the world will map to a straight line in the image.

Using the description of a line and the method used to get the mapping of points, I got this model:

$ \lambda \begin{bmatrix}A & B & C\end{bmatrix} \begin{bmatrix}u \\ v \\ 1\end{bmatrix} = \begin{bmatrix}A & B & C\end{bmatrix} P \begin{bmatrix}X \\ Y \\ Z \\ 1\end{bmatrix}$.

I've done some additional research, but so far I haven't found anything that can support this affirmation.

Is it correct to say that the mapping of a 3D line in the world to a line in an image of the world is done using the previous model?

Could anyone please point me in the right direction?

Thank you.


texts: Proof that bin packing is strongly NP-complete?

texts: Wikipedia claims that bin packing is strongly NP-complete. Unfortunately I haven't been able to find a proof. Does anyone know where to find it?


texts: Log-space reduction - How to calculate overall space needed?

texts: Assume A, B are two decision problems. Given a reduction from A to B that uses log^c1(n) space and an algorithm that solves B in log^c2(n) space, Can we determine some lower bound to the space needed by an algorithm which solves A using this reduction?


texts: L = { , M is a DFA accepting all strings except finitely many

texts:
Is the $L$ = { $<M>$, $M$ is a DFA accepting all strings except finitely many. }
decidable ? I am sort of confused about the question - what exactly does $M$ accept. How are those finitely many strings look like for a particular $DFA$? It is known that $DFA$ accepts infinite number of strings if it accepts at least one string with length $>=k$, where $k$ is the number of states. Does it mean that M doesn't accept any strings of size less then $|k|$ - since this number would be finite ?
I came up with the
 decider for $L$ call it $I$, which basically checks $M$ on accepting any strings of size less than $k$.
I = “On input $<M>$, where $M$ is a $DFA$:
1. Let $k$ be the number of states of $M$
2. Construct $k$ $DFA's$ denote them $D_i$, where $i$ goes from $0$ to $k-1$, $D_i$ accepts all strings of length exactly $i$
3. Construct a $DFA$ call it $T_i$ such that $L_i(T) = L(M) ∩ L(D_i)$.
4. Test $L_i(T) = ∅$ using the $E_{DFA}$ decider
5. if $E_{DFA} $ accepts for every $T_i$ and $E_{DFA}$ reject on $M$  => accept , otherwise reject.

Is there a simpler way of answering the question ?


texts: Is Finding A Hitting Set of Size n/2 NP-Hard?

texts:
In Hitting Set problem we are given a collection E of subsets of V and we want to find smallest subset H of V which intersects (hits) every set in E.

In decision version of the problem, we are asked if there exists a hitting set H of size at most k.

This problem is known to be NP-hard. However, I wonder if the problem is still NP-Hard when are asked if there exists a hitting set whose size is strictly less than n/2, i. e., at most n/2 - 1, (where n is the size of V).

I'm currently working on another problem and I'm convinced that the problem is NP-hard. So I'm trying to find a reduction. I've realized that if the above problem is NP-hard, then I am done.

Any help is appreciated.


texts: How to find every negative cycle in a graph

texts:
A graph with n vertices, no matter directed or not, may have maximally 2^n-n-1 negative cycles
(Think about combination of 2 to n elements and you'll figure out why 2^n-n-1. A graph that has no graph loops or multiple edges is my only concern)
and I want to find ALL of them if any, not just one of them. There are only answers to the latter question throughout the whole internet. To find a cycle means we get a list of vertices which form this cycle.
I also want to find the one negative cycle which is the smallest in one lap of traverse.
One solution, which is slow and not elegant, is to run Floyd-Warshall algorithm on the graph, and find those vertices, e.g. i, so that d[i][i]<0 (According to some researches collected in Wikipedia, this means vertex i is part of a negative cycle) and then check all 2^n-n-1 (if there are n of those i's) cycles to see if they are negative.


texts:
I have heard the word "hash" being used in different contexts (all within the world of computing) with different meanings. For example, in the book Learn Python the Hard Way, in the chapter on dictionaries it is said "Python calls them "dicts." Other languages call them "hashes."" So, are hashes dictionaries?

The other common usage of the word is in relation to encryption. I have also heard (& read) people using the word "hash" as a specific function within high-level programing.

So, what exactly is it?

Can anyone (with time and who is knowledgeable) kindly explain the nitty-gritties of "hash (or hashes)?"


texts: How can one algorithmically define the required amount of centroids in K-Means clustering?

texts:
Say I have a dataset of n vectors. These are, by nature, clustered so that there is a significant distance difference between any two points within a cluster and any two points in separate clusters.

I want to create a single centroid per single cluster. However, I cannot initially know how many clusters there are - thus I cannot pre-define the k in K-means clustering.

What is the best way to define the k in K-Means, given the dense and clear clustering of the data?


texts: The choice of programming language and the length of a program

texts:
I wonder how it's possible that:

  it can be shown that all reasonable choices of programming
  languages lead to quantification of the amount of absolute information in
  individual objects that is invariant up to an additive constant.

from the Preface to the First Edition, An Introduction to Kolmogorov Complexity and Its Applications by Li & Vitanyi.

I don't know how they defined "reasonable choice of programming language", but in my sense, it seems natural that the choice of programming language could mix the rank of the complexity. If the programming language fits the object, the program would be shorter, and if not, it would be longer.

But, if I understood it all right, the paragraph above says that no matter which programming language you choose for the strings(objects), the rank of the length of the programs would not change!

Is it really possible? and could someone explain how it's possible?

It is well known that either AND and NOT or OR and NOT can be a primitive function for a computer,

and if I want to implement AND with (OR and NOT), it goes like

NOT(NOT a OR NOT b) instead of just AND!!!


texts: Turing machine states, lost in the jungle

texts:
There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- inaccessible states in a Turing machine.   These are simply defined (look at page 43 here if you need a source) as states that are never reached.

The definition I linked to is accompanied with a state graph that shows an obviously inaccessible state.  Simplified:

(q0)-1->((q1))<-0,1-(q2)

If q0 is the start state, q2 is obviously inaccessible. This is analogous to the deliberately-disabled code that was the premise of the EL&U discussion.

But I'm wondering about those states that are inaccessible, but you will never know it, because they're just lost in the jungle.

These states all have a path from the start state in the machine's state graph. But no matter how long the machine runs, the particular combination of state and symbol to make the number transition into that state never appears.

For some of these states, static analysis can determine if they're inaccesssible.

For the rest, no analysis will ever be able to determine if the state is ever reached. For example, if you could determine whether every halt state is reached or not, you would have just solved the (unfortunately-named, but don't get me started) Halting Problem.   Let's leave out states that machines reach serendipitously if you run them long enough.

Is there a more specific term than 'inaccessible state' for this?  (It's a shame  'inaccessible states' can't mean specifically this; it would have been a nice parallel with inaccessible sets from set theory.)


texts: What is an algorithm to do this binary image segmantation task?

texts:
What I need to do is go from a binary image like this:

to a segmented structure like this:

because I have a program that operates on those separated line contours after.
As you see, those contours are not perfect, they might be slightly bent but where they meet it's always pretty much orthogonal, there are no 45 degree lines. The lines are between 3 and 20 pixels wide. The whole image is sometimes slightly rotated (less that 10 degrees) but if you find a solution that only works without rotation I could look into de-rotating stuff before. The inserted gap may be of any width (preferably 1px or 2px) as long as it entirely separates one line from another.
I thought one could do something like on page 15 of this paper (the description of what they do is on page 13). Essentially this would come down to finding one marker per line segment and then watershed, but I have no idea how to find that marker.
Just to be clear:
On any point of line intersection, this

is good, as well as this:

If easier to achieve,
this:

is acceptable too, although not preferred.
What's not ok is this:

This is not only true for three-line t-sections but also two-line corner connections (= it doesn't matter which of the two lines meeting gets shortened).
Sorry for the huge pictures, didn't know how to prevent them from turning out this big.
I am working with python and cv2 so it would be a plus if you use that. On the other hand, even a link to a re-implementable algorithm or an idea how to find markers would be fine. Also, I'm looking for a fast and easy algorithm that works on binary (0 or 255) images, not any crazy machine-learning stuff (if avoidable). I have really time but lack the right idea. Thanks in advance.


texts: Why create more faster processors despite of Processor Memory Bottleneck?

texts:
The shared bus between the program memory and data memory leads to the von Neumann bottleneck, the limited throughput (data transfer rate) between the central processing unit (CPU) and memory compared to the amount of memory. Because the single bus can only access one of the two classes of memory at a time, throughput is lower than the rate at which the CPU can work. This seriously limits the effective processing speed when the CPU is required to perform minimal processing on large amounts of data. The CPU is continually forced to wait for needed data to be transferred to or from memory. Since CPU speed and memory size have increased much faster than the throughput between them, the bottleneck has become more of a problem, a problem whose severity increases with every newer generation of CPU.

Source : https://en.m.wikipedia.org/wiki/Von_Neumann_architecture#Von_Neumann_bottleneck

There can be up to a 53% difference between the growth in speed of processor speeds and the lagging speed of main memory access.

So, if the processor-memory performance gap is so big then isn't creating more powerfull processors useless ?


texts: Hard disk scheduling - N-set-SCAN vs FSCAN

texts: I'm wondering which is a better scheduling algorithm to use. The only real difference I can see is that in FSCAN there are two queues, and when a scan begins all requests are put in one queue and the other left empty. Then during the scan the other queue is used to store new requests and deferred until all the old requests have been processed.


texts:
So I'm doing exercises from Dasgupta's Algorithms. The exercise i'm having trouble with is:

Show that, if $c$ is a positive real number, then $g(n) = 1 + c + c^2 +...+c^n$  is:

$\Theta(1)$ if $c<1$

$\Theta(n)$ if $c=1$

$\Theta(c^n)$ if $c>1$

(I dont know if this is a hint but it is included in the text:
"The moral: in big-$\Theta$ terms, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly indreasing or the number of terms if the series in unchanging")
The only one that makes sense for me is 2) where $1+1^2+..+1^n$ is the same as $n+1$, and removing the 1 gives $O(n)$. I dont know if my reasoning makes sense, but thats all i've got. I have no idea where to start or how to think on the other two. Any suggestions?


texts: If dynamically typed languages are truly statically typed, unityped languages, what is the (finite) type expression of the one type?

texts: Some claim that dynamically typed languages are in reality statically typed, unityped languages. This would imply to me that this one type should be expressible as a static, finite type expression, so can anyone provide such an expression? You can make whatever assumptions you need to make about the base types in the language, but please make sure the language would support types of unbounded size, e.g., lists, recursive types. It would also be nice if it supported records and variants, but whatever helps to illustrate the point will work. I'm also assuming that the language will be required to support some form of sum type, right?


texts: Removing max number of edges while keeping minimum distances

texts: Suppose we have a graph with vertices from 1 to n.The graph is undirected and the starting point is 1 and we have path from 1 to any other vertex.We also have positive weight on each edge and there are two types of edges - black and red. The black edges are in the form (1,x) where x is a vertex and red edges can be any pair (x,y) .My question is how can I find the maximum number of black edges I can remove so that the minimal distance from 1 to any other vertex is preserved?


texts: In LPA*, how are predecessors/successors of a vertex defined?

texts:
While trying to implement LPA* (mostly based on its description in the same authors’ paper on its derivative D*Lite), I noticed it mentions predecessors and successors of a vertex without giving a full explanation.

I understand that $Pred(u)$ is the set of all vertices from which an edge leads towards $u$, and $Succ(u)$ is the set of all vertices towards which an edge leads from $u$. Predecessors and successors must be immediate neighbors (thus e.g. a predecessor of a predecessor of $u$ is not necessarily a predecessor of $u$).

In practice, however, it is quite common to have edges that are not directional, i.e. can be traversed both ways (which is equivalent to the same two nodes being connected by two antiparallel directional edges). I infer that for two vertices $u$ and $v$ connected in this way, $u$ would be both a predecessor and a successor of $v$ (and vice versa). In other words, $Pred(u) \cap Succ(u)$ is not necessarily empty.

Am I correct to assume that predecessor and successor are defined only by the existence of an edge traversable in a given direction, and are specifically not related to start cost?


texts:
Can anybody give me a way that i can use to calculate Complexity Time problems, i mean a way that will work on any complex code whatever it was.

I can solve basic problems, but whenever the problem gets a little complex i freeze which means that my way of thinking and solving is wrong.

for example like this:


texts: Stable marriage problem with more people then priorizations

texts:
I am trying to solve a stable marriage problem where I have e.g. 20 women and 20 men, but they always only prioritise 4 pre-selected people of the opposite sex.

My algorithm distributes all men and women, so that everybody has 4 potential partners. This happens through the whole group of 20 (not in groups of 4 x 4, which would easily work). If man A has woman B in his list then he is also in her list.
The people prioritise their potential partners from 1 to 4.
My algorithm tries to find the optimal partner depending on their priorization.

This means that they marriage has to be with one of the 4 potential partners. The order of their prioritisation decides on the order the proposing and accepting matrix is gone through, similar to this animation shown in wikpedia.

So basically I have 20 rows of each proposers and acceptors, but only 4 columns.

So far I always get an almost stable solution, in which in the end only one man and one woman can not marry.

How could I solve this problem for even bigger numbers of people (rows), but always keeping 4 (or between 3 and 5) prioritisation (columns)?


texts: Probability of randomly designated subsets cover the universe

texts:
Let $U=\{1,2,\ldots,n\}$ and $S \subseteq \mathscr{P}(U)$. Let $T$ be a subset of $S$, randomly constructed selecting independently each element of $S$ with probability $p$.

Is there a polynomial time algorithm that computes:

$$\mathbb{Pr}\left[ U =\bigcup_{X \in T} X \right]$$

Or is there any equivalent famous problem?


texts: Computational complexity of logistic map

texts:
My question is pretty simple and to the point. Is there a known way to efficiently compute logistic maps to within a specified precision?  In other words, the input is a value $x$ and integers $d,n$; the desired output is the result of $n$ iterations of the logistic map applied to $x$, to $d$ bits of precision.

I know of a way to do this using exact real arithmetic but the representations of real numbers that I know and the algorithms I know all take exponential time with respect to the requested number of bits of precision.  Using fixed-point arithmetic doesn't work because each multiplication doubles the number of bits of precision needed, so the number of bits needed is exponential in the number of iterations. Is there a known efficient way to compute logistic maps to with specified precision?


texts: How do I find maximum and minimum number of times the search loop will execute when searching through an array of 1,048,576 integers

texts:
I have tried to calculate the maximum number of times the loop will search through this large array, but I am not sure if I have that correct and I also need help with or pointers of how I can calculate the number of minimum times it will search through the array using both the binary search and sequential search. Here is what I have done so far.

Maximum Number of Times with Binary Search: Maximum: $\log_2(1,048,576)= 20$ times
Maximum Number of Times with Sequential Search: Maximum: $1,048,576 + 1 ÷ 2= 524,289$ times

But I am confused about how I can obtained a solution with Minimum number for each algorithm. Any suggestions?


texts: Laser Plane Estimation for Laser-Camera system?

texts:
I have to set up a system of a laser line/ plane projector and a web camera to localize the 3D position of the laser in the camera image. I've read / come across several resources but the idea is still not quite concrete in my head.

So my intuition is that since we have a set up of a laser projector and the camera, and we want to find the position of the laser point in the image - we have to find the 'correct' laser plane that intersects with the camera / image plane. I am confused as to how we find the relative pose of this plane with respect to the camera, and how we can use this to find the 3D coordinates?


texts: How many cookies in the cookie box? -- Tiling stars

texts:
With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit in one layer:

Almost! Is there a way they could have fit? How well can we tile stars, anyway? Given that these are regular six-pointed stars, we could certainly use the well-known hexagon tilings as an approximation, like so:

Messed up the one to the upper right, whoops.

But is this optimal? There's plenty of room between the tips.

For this consideration, let us restrict ourselves to rectangular boxes and six-pointed, regular stars, i.e. there are thirty degrees (or $\frac{\pi}{6}$) between every tips and its neighbour nooks. The stars are characterised by the inner radius $r_i$ and outer radius $r_o$:

[source]

Note that we have hexagons for $r_i = \frac{\sqrt{3}}{2} \cdot r_o$ and hexagrams for $r_i = \frac{1}{\sqrt{3}} \cdot r_o$. I think it's reasonable to consider these the extremes (for cookies) and restrict ourselves to the range in between, i.e. $\frac{r_i}{r_0} \in \Bigl[\frac{1}{\sqrt{3}}, \frac{\sqrt{3}}{2}\Bigr]$.

My cookies have $r_i \approx 17\mathrm{mm}$ and $r_o \approx 25\mathrm{mm}$ ignoring imperfections -- I was going for taste, not form for once!

What is an optimal tiling for stars as characterised above? If there is no static best tiling, is there an algorithm to find a good one efficiently?


texts: Proving laws of take and drop functions using structural induction on lists

texts:
I'm trying to prove the following laws using structural induction on (finite) lists:

take m (drop n xs) = drop n (take (m + n) xs)
drop m (drop n xs) = drop (m + n) xs

for all m, n and every finite list xs (code snippets are in Haskell). I'm not sure how to tackle it though, more specifically: afaik when using induction on intervals, the first induction step is for m > n and the second for m ≤ n. Now in this case the law must also be valid for all finite lists, does that mean the proof involves prooving all the following?

case m > n: [] and (x:xs), and in the latter m + n > length xs and m + n ≤ length xs
case m ≤ n: [] and (x:xs), and in the latter m + n > length xs and m + n ≤ length xs

If yes I can update my question and show exactly where I'm stuck.

(Please don't post the entire solution, I'd just like to have some pointers. Thanks!)

UPDATE

If [] denotes the empty list and (x:xs) a list with at least one element (x is the head of the list and xs its tail), possible definitions of take and drop are:

take n [] = []
take 0 xs = []
take n (x:xs) = x : take (n - 1) xs

if n is greater than l, where l is the length of the input list, then take returns a list of length l

drop n [] = []
drop 0 xs = xs
drop n (x:xs) = drop (n - 1) xs

if n is greater than l, where l is the length of the input list, then drop returns the empty list


texts:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that we must complete. The task at vertex $v$ takes $q_v > 0$ minutes for $v \neq 0$, and we must complete all tasks. We start at Vertex $0$, and we have $q_0 = 0$.
It will obviously take us exactly $\sum_{i = 1}^{n} q_i$ total time for us to complete all of the tasks on our own  (it doesn't take any time to traverse the edges). However, suppose we have a single helper. We are allowed to dispatch the helper at any node (say $v$), and we can leave the node, go work on other tasks, and pick up the helper after $q_v$ minutes to drop it off at another node. A caveat is that the helper cannot move on its own; it must be picked up and dropped off.
Is there some sort of algorithm that allows one to find the best strategy (i.e., one that minimizes the total time) when we are allowed one helper?
A naive strategy would be a greedy strategy that always drops off the helper at the vertex with the largest $q_i$. It seems like this would minimize the time that the helper is idle; however, I have no reason to believe that this is optimal.
Does anyone have any suggestions or heuristics for an approximate solution?


texts: Is there a $O(n\frac{\log{n}}{\log{k}})$ sorting algorithm?

texts:
I am trying to figure out a sorting algorithm which can be used in $O(n\frac{\log{n}}{\log{k}})$ sorting time. I am allowed to use $k$ registers that can store key value pairs and these registers can insert a key value pair and return a key value pair in constant time. And when popping from one of these registers, it will return the smallest key.

So what I have so far is, I am thinking about having a hash function with value (highest value in array size $n$) and then put that into the registers, then will pop the registers (Which will return the smallest key value) and add those sorted values back into the array. But the main problem I have is I do not know how large $k$ will be so when I pop the values from the registers, I may have to put more values back in the registers, and was wonder how to go about this.


texts: How can I sum pixel values over a rotated rectangle?

texts:
I have an optimization problem in which I need to sum pixel values in an image over a rectangular region. This is a core component of the optimization so it will be done often and the naive solution is not fast enough.

The region can be rotated arbitrarily so that I can't use an integral image; integral images only work for axis-aligned rectangles.

Does someone know a generalization of the integral images for that problem or has a different idea?

Update:

The rectangles have different rotations, so that I can't rotate the rect.
The rectangles have a size similar to the one of the full image (each ~20%)


texts:
I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual".
It's listed on the following web-page under number 8-22: http://www.algorist.com/algowiki/index.php/Divide-TADM2E#8-22

The problem asks you to write a polynomial-time algorithm using DP which solves a special case of the Word Problem over finite groupoids:

Given a finite groupoid $G$, a word $s$ on $G$ and an $x \in G$, find out whether it is possible to parenthesize $s$, such that its evaluation will yield $x$. Example from the book:

\begin{array}{c|ccc}
&       a       &       b       &       c      \\
\hline
a       &       a      &       c      &       c  \\
b       &       a      &       a      &       b  \\
c       &       c      &       c      &       c  \\
\end{array}

For instance, consider the above multiplication table and the string
$bbbba$.
Parenthesizing it $(b(bb))(ba)$ gives $a$, but $((((bb)b)b)a$ gives $c$.

So far I managed to write a naive $O(n!)$ recursive algorithm in Python:

def i(x):
    return ord(x) - ord('a')

def mul(x, y):
    return groupoid[i(x)][i(y)]

# rewrite('abc', 1) = 'ac'
# rewrite('abc', 0) = 'cc'
def rewrite(word, i):
    return word[:i] + mul(word[i], word[i+1]) + word[i+2:]

def search(word, x):
    exists = (word == x)
    for i in range(0, len(word) - 1):
        if exists:
            break
        exists |= search(rewrite(word, i), x)
    return exists

word = sys.argv[1]
x = sys.argv[2]
exists = search(word, x)
print('Solution exists' if exists else 'Unsolvable')

Although we can memoize search, it won't give us polynomial time, since memoization space is of a factorial order. This is where I'm stuck.

The problem here is to somehow reduce the factorial search-space of all possible reductions from $s$ on $G$ to a polynomial search-space, which will depend only on $|s|$ and $|G|$. Can you please help me with that? Any other hints?


texts: Reduce ATM to the language of TM encodings where if the TM accepts w then the TM accepts ww

texts:
Today I did a test in my class, the trace was:

  Prove that the language $L =\{\langle M\rangle\mid \forall w \in \{0,1\}^\ast: M \text{ accepts
}w\implies M \text { accepts }ww \}$, is undecidable with a reduction
  from $A_{\mathrm{TM}}$.Hint: You can suppose that $w\in \{0,1\}^*$

I answered:

  Suppose that $L$ is decidable. Therefore, there is a TM $R$ such that $L(R)= L$, so we can construct a new TM $S$ that decides
  $A_{\mathrm{TM}}$. First, construct $N$ as follows:$\\$
  "On input $x$:

  if $x$ is of the form $ww$, accept
  otherwise, run $M$ on $w$ and do what $M$ does.

  Now we can construct $S$ as follows:

  Construct $N$ as above.
  Run $R$ on $N$; if $R$ accepts, accept; otherwise, reject.

Now I know this isn't correct, but I don't why. More generally, how to recognize a language of a reduction? For example, in my reduction, $S\text{ accepts } w \iff \text{the language of } N\text{ is ?} \iff \langle M,w\rangle \in A_{\mathrm{TM}} $ I think I'm missing something about reductions but I don't know what.


texts: What is this trapezoid-shaped logic component?

texts:
This is from http://www.cis.upenn.edu/~milom/cse240-Fall05/handouts/Ch05.pdf , slide 9.

From this diagram, I recognize 0001 as the opcode, which corresponds to the ADD instruction. I recognize 011, or 3, as the source register and 101, or 5, as the destination register. I know that the 1 signifies immediate mode or the second operand is directly in the instruction. From here, I know that the second operand is 11111 or -1 in decimal and that it will be sign extended (SEXT) before being added to the data in the source register.
Does anyone know what the logical component I highlighted does?

The component is shaped like an isosceles trapezoid, and has three inputs: seemingly, two data inputs and one control input.


texts: Maximum Spanning Tree vs Maximum Product Spanning Tree

texts:
So I'm kind of wondering if I'm correct on something relating to an algorithms class. Let's say I want to, for whatever reason, find the maximum spanning tree of a graph such that the edge weight is at maximum instead of minimum.

In addition, let's say I want to find a spanning tree with the maximum product-sum weight (the product of the edges of the spanning tree is at its maximum).

Assuming edge-weights must be greater than 0, would their spanning trees contain the same edges? I'm pretty sure that their spanning trees are equal.

Plus, I also believe that a modified Kruskal's algorithm searching for maximum weighted edges would create these spanning trees since you'd want the largest weights for both types of maximum trees.

Is my thinking correct?


texts:
Given a directed graph $G = (V, E)$ and a starting vertex $v_1$.

The graphs edges is this

$\{(v_1, v_2), (v_2, v_3), (v_3, v_4)\}$

basically below

$(v_1) \to (v_2) \to (v_3) \to (v_4)$

Can we traverse this graph and record the path starting at $v_1$ in $O(|V|)$ time?

For example Making a list like $[(v_1, v_2), (v_2, v_3), (v_3, v_4)]$

I'm confused whether this takes $O(|V|^2)$ worst case time because the edges are in a set


texts: Pierce's Types and Programming Languages : circular definition of terms?

texts:
In Pierce's book, on page 26-27 it is given a definition of terms for a simple language using inference rules.

In the picture below it is marked by red highlighting the problematic part.

What is Pierce referring to exactly by the red-highlighted word term in this context?

Is he referring to the terms given by the grammar on page 24 ?

In that case I see no point in defining the terms using the inference rules given in the Definition 3.2.2 because he is using the definition of terms already defined by the grammar on page 24, so there is no point in defining it again.

How should one really understand what the red-highlighted word term refers to on page 27, so that the definition 3.2.2 makes sense ?

The only way the last sentence would make sense to me if it would be changed to something like this: ... replacing each t by every possible term that has been generated inductively so far., meaning that the highlighted word term does not refer to the terms defined on page 24 but to the terms which already have been generated inductively by the inference rules given in Def 3.2.2.

What do you think ?

The grammar from page 24:

t ::=                                   terms:
      true                       constant true
      false                     constant false
      if t then t else t           conditional
      0                          constant zero
      succ t                         successor
      pred t                       predecessor
      iszero t                       zero test

From page 26:

  3.2.2. DEFINITION [TERMS, BY INFERENCE RULES]: The set of terms is defined by the following rules

  $$\begin{gather}
    \texttt{true}\in\mathcal{T} \qquad\qquad
    \texttt{false}\in\mathcal{T} \qquad\qquad
    0\in\mathcal{T}\\\\
    \frac{\texttt{t}_1\in\mathcal{T}}{\texttt{succ t}_1\in\mathcal{T}} \qquad
    \frac{\texttt{t}_1\in\mathcal{T}}{\texttt{pred t}_1\in\mathcal{T}} \qquad
    \frac{\texttt{t}_1\in\mathcal{T}}{\texttt{iszero t}_1\in\mathcal{T}}\\\\
    \frac{\texttt{t}_1\in\mathcal{T} \qquad \texttt{t}_2\in\mathcal{T} \qquad \texttt{t}_3\in\mathcal{T}}{\texttt{if t}_1\texttt{ then t}_2\texttt{ else t}_3\in\mathcal{T}}
\end{gather}$$

From page 27:


texts: Minimal shift operations to sort an array

texts:
I have been stuck on this sorting problem for a while now:

Given an array of length N find the minimum number of shift operations in order to sort the array. A shift operation is defined as shifting a value in an array to another position. For this problem however, you can only perform this shift operation on the first element in the array.

For example, let's say N = 4 and our array was [1,2,4,3].To sort this array we could perform the following shift operations:

[1,2,4,3] -> [2,4,1,3] -> [4,1,2,3] -> [1,2,3,4]

Thus, we would have to perform a minimum of 3 shift operations.

Any clues on how to approach this problem?


texts: A Turing Machine that Doesn't Move to the left

texts:
My question is if the following statement is true or false:

Does every turing-recognized $B$ language has a turing machine $M$ that recognizes $B$ and fullfiles the following statement:
For every word $w$ the belongs to $B$, $w \in B$, the writing-reading head never moves to the left?
Notice that the condition is required only for words in the language. if $w \notin B$ then the head can move to the left as usual.

The statemet seems correct to me. I think I can simulate a regular $TM$ with this "special" $TM$, while saying that every time the head moves left, it will stay put. Couldn't prove it, though.


texts: Quicksort's asymptotic performance for array of [50,...,50,100,...100]

texts:
Let's have an array where first half are of value 50 and the second half 100. What would be the asymptotic performance when sorting using Quicksort.

I think it it should be $O(n^2)$ as for array of same elements the complexity is $O(n^2)$ and this particular problem could be rewritten as sorting the first half + sorting the second hald $O(2*(\frac{n}{2})^2 + n)$ which is still $O(n^2)$.

But my schoolmates claim it should be $O(n log(n))$.. so which one is correct?


texts: Why there is no direct connection between the data bus and the accumulater register

texts:
In the data bus all the registers are connected in and out with the data bus but the AC don't have it only out also the memory don't have a direct connection with it ?
Please explain if you know


texts: Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

texts:
The well-known textbook Introduction to Algorithms ("CLRS", 3rd edition, chapter 3.1) claims the following:

$$ \sum_{i=1}^n O(i) $$

is not the same as (I'm not using DNE because the book explicitly says "is not the same as")

$$ O(1) + O(2) + \dots + O(n) $$

Why is this? How are we to explicitly represent the first summation if not with the second? As an extension of the previous question, how do we do asymptotic analysis on such a summation?


texts: CNN/Neural Network: Can I still estimate 3 parameters if my input data has insufficient parameter labels?

texts:
I am trying to simplify a CNN model. Currently, I need to train 3 different models (with the same architecture) to estimate each parameter. I am just wondering if there is a way to just train one model that outputs 3 parameters, with input images containing only single parameter label.
Say the three parameters are some kind of measure of symmetry (sym), repetitiveness (rep), roundness (rd). Each of my input images will only give a label for one of the parameters. For each parameter, there is the same number of images.
I am thinking if there is a way to accomplish this using some kind of dummy variable to block out the unavailable parameters from backpropagation?

If anyone who has experience with this scenario could give me some advice, it would be super appreciated.


texts: Number of solutions to linear system of equations over GF(2)

texts:
Linear systems of equations over the reals have either 0, 1 or infinitely many solutions. However, when applied to finite fields (specifically GF(2)), infinitely many is not an option.

Is there a fast general method to calculate the number of distinct solutions to a linear system of equations over GF(2)?

You can assume that Gaussian elimination has already been performed, so an example augmented matrix would be:

$$ \left[
    \begin{array}{ccccccccc|c}1&0&0&0&1&1&1&0&0&1\\
0&1&0&0&1&0&1&0&1&1\\
0&0&1&0&0&1&1&1&0&0\\
0&0&0&1&1&1&1&1&1&1\\
0&0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0&0\\
    \end{array}
\right] $$


texts: Degree conditions sufficient for Hall's theorem

texts:
Let $G=(L,R,E)$ be a bipartite graph, are there conditions on the degree of the vertices under which the condition of Hall's theorem is surely satisfied? (meaning a perfect matching exists in the graph).

Konig's theorem proves that every $k$-regular bipratite graph has exactly $k$ edge disjoint perfect matchings, so the answer is obviously yes for any $k$-regular bipartite graph with $k>0$ (it's not hard to see why hall's condition is satisfied in this case).

Is there a wider rule?

For example: Let $|L|=|R|=n$, What is the minimal degree as a function of $n$ of every vertex in the graph such that the graph must admit a perfect matching?

I'm also wondering if these conditions will hold in general graphs (satisfying Tutte's theorem), and if not, then are there similar conditions for general graphs.


texts: Algorithm to add sum of every possible xor-sum sub-array

texts:
I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here.

Problem Statement

XOR-sum of a sub-array is to XOR all the numbers of that sub-array.
An array is given to you, you have to add all possible such XOR-sub-array.

Example

Input

Array :- 1 2

Output :- 6

Explanation

F(1, 1) = A[1] = 1, F(2, 2) = A[2] = 2 and F(1, 2) = A[1] XOR A[2] = 1 XOR 2 = 3. Hence the answer is 1 + 2 + 3 = 6.

I found an $O(N^2)$ solution, but it was too inefficient one and wasn't accepted in the competition.

I saw the best solution of this problem on Code Chef. But in this code, I didn't understand below module, please help me to understand that.

for (int i=0, p=1; i<30; i++, p<<=1) {
    int c=0;
    for (int j=0; j<=N; j++) {
        if (A[j]&p) c++;
    }
    ret+=(long long)c*(N-c+1)*p;
}

In pseudocode:

Set $r = 0$
For $i$ from $0$ to $29$, let $p = 2^i$.

Set $c=0$
Iterate over the array $A$. For each element $A[j]$:

If $A[j] \mathbin\& p \ne 0$ then increment $c$. ($\&$ is bitwise and.)

Add $c \times (N-c+1) \times p$ to $r$


texts:
I have got following question:

Determine whether the following language is context free or not:
$$L = \{ w \in \{a,b,c\}^*: n_a (w) = n_b (w) = 2n_c (w)\}. $$

What is the meaning of $2n_c$ in the above question?


texts: I would like to know cases that an algorithm runs without any data entry.


texts: How to fool the plot inspection heuristic?

texts:
Over here, Dave Clarke proposed that in order to compare asymptotic growth you should plot the functions at hand. As a theoretically inclined computer scientist, I call(ed) this vodoo as a plot is never proof. On second thought, I have to agree that this is a very useful approach that is even sometimes underused; a plot is an efficient way to get first ideas, and sometimes that is all you need.

When teaching TCS, there is always the student who asks: "What do I need formal proof for if I can just do X which always works?" It is up to his teacher(s) to point out and illustrate the fallacy. There is a brilliant set of examples of apparent patterns that eventually fail over at math.SE, but those are fairly mathematical scenarios.

So, how do you fool the plot inspection heuristic? There are some cases where differences are hard to tell appart, e.g.

[source]

Make a guess, and then check the source for the real functions. But those are not as spectacular as I would hope for, in particular because the real relations are easy to spot from the functions alone, even for a beginner.

Are there examples of (relative) asymptotic growth where the truth is not obvious from the function definiton and plot inspection for reasonably large $n$ gives you a completely wrong idea? Mathematical functions and real data sets (e.g. runtime of a specific algorithm) are both welcome; please refrain from piecewise defined functions, though.


texts: What are algorithms for computing contours from given edges?

texts:
Let's say I have a set of edges which makes the contour, however there are too many of them and some are too long. I have to remove edges, and shorten them to make contour. I cannot add new edges!

I am looking at least for the name of the algorithm to further look how this problem is solved.

Here is the example (please don't mind the grid) -- input:

and output in pink (the pink is the real output, the rest is left for comparison -- it should be removed by algorithm I am looking for):

As you can see I have a lot of redundant edges, too long, internal ones.
Note also that this is not the convex hull problem; my shape is not convex.

The question: what are known algorithms for solving this problem?


texts: What constitutes one unit of time in runtime analysis?

texts: When calculating runtime dependence on the input, what calculations are considered? For instance, I think I learned that array indexing as well as assignment statements don't get counted, why is that?


texts: How to prove that a binary heap can't be sorted with complexity that better than O(nlogn)

texts:
I am trying to prove that you can't sort binary heap with better complexity than O(nlogn).
We proved at class that every sort based on comparison can't have better cocmplexity than O(nlogn) and  i know nothing about the items in the heap (except its a heap) so you  can't use radix sort or linear sort.
Problem is i feel like its not enough to say this things.
I don't know how i am supposed to prove it and i am searching for help.


texts: Using FFT to solve pattern matching problem with don't cares

texts:
I've studied about $FFT$ and it's use in string matching, but there are several issues that bother me. First I'll describe the problem and the solution I've seen in class:
Suppose we have alphabet $\Sigma = (a, b, \phi)$ where $\phi$ is "don't care", meaning it matches with every letter, including itself.
We have a text $T = t_{_0}t_{_1}t_{_2}...t_{_n}$, and a pattern $P = p_{_0}p_{_1}p_{_2}...p_{_m}$, assuming $n$ is much bigger than $m$. We say that we have match in index $i$ if for every $0 \leq k \leq m$:
$$P[k]=\phi  \space or\space T[i+k]=\phi \space or\space P[k]=T[i+k]$$
Therefore we introduced new "multiplication" function over $\Sigma$:
$$
f(a,b) =
\begin{cases}
0 & \text{if a = b;}\\
1 & \text{else;}\\
\end{cases}
$$
The idea was to translate every appearance of $a$ and $\phi$ to $0$, and $b$ to $1$, reverse $P \text{ (P$^R = p_{_m}p_{_m-1}p_{_m-2}...p_{_0})$}$, treat both strings as polynomial coefficient vectors and multiply them according to the regularity of $f$. Then in their product vector, $C$, indices that are 0's will tell us there's a match starting in that index in text.
In order to do that efficiently we used $FFT$, however, $FFT$ works with standard multiplication, so in order to bypass that obstacle we calculated $T^c \cdot P^R +T \cdot (P^R)^c$, where $c$ superscript means to "not" the string, for example: $(100010)^c = 011101$, and $+$ means normal addition of vectors. Now I have 2 questions bugging my mind:1) How that thing we did in "not"-ing the strings helps solving the problem about the multiplication. I mean I've tried several examples and it works, but why it works?2) If I wanted to expand this method to bigger alphabet, how could I do it? There's something very binary-oriented in the core of "not"-ing the string, relying on the fact that I have only one pair of letters that create discrepancy.


texts: I would like to show that a problem $A$ is $NP\text{-complete}$. So, I am trying to reduce 3-SAT problem to $A$. Reduction is kind of function, let say $f$. What is necessary complexity of $f$? Probably, it has be in $NP$. But, does it mean that $f$ must be a non-deterministic Turing machine working in polynomial time?


texts: distinguishing between CTL* formulas $A[FG p]$ and $AFAG p$ using transition system

texts:
It is to show, using a transition system, that the two formulas $A[FG p]$ and $AFAG p$ are not equivalent.

For me, it seems strange that they are not equivalent.

As the first one says that any computation path eventually has $p$ always true.

And the second one says that any computation path contains a state such that any path starting at this state has $p$ always true.

Aren't they equivalent?


texts: Non Regularity proof using Kolmogorov Complexity (Li - Vitanyi Theorem)

texts:
When proving a language is non regular we can use Kolmogorov complexity.
As far I know to do this we just have to use this satisfy the following conditions
Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (in lex order) such that $xy∈A$ (if n such y exits). So what completes $x$ if adding $n$ such y's brings us to an element in the set  A

Given $A \subseteq \Sigma^*$ has the following property, then it is not regular
For every $c \in \mathbb{Z^+}$ there exits $x \in \Sigma^*$, and $n \in \mathbb{Z^+}$ s.t. $Y^A_{x,n}$ exits and K-Comp $C(Y^A_{x,n}) > c + log(n)$

We are trying to show weather given a DFA will it end in a final state after certain number of steps and this process will tell us if that is not a possibility since we cannot prove regularity just non-regularity
Keeping that in mind I am trying to prove this language is not regular

Let us run through a simple example B = $\{0^n1^n | n \in \mathbb{N}\}$
Proof: Let c $\in \mathbb{N}$. Choose k $\in \mathbb{Z^+}$ such that $C(1^k) > c$, and let x = $0^k$ then we get the following$Y^A_{x,1} = 1^k$<-why? and $Y^A_{x,2} = 01^{k+1}$<- again why
therefore $C(Y^A_{x,1}) = C(1^k) > c + log(1)$ QED


texts: Bit complexity of computing the sign of an expression evaluated at an algebraic number

texts:
I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of coefficients equal to $d^2+d\tau$.

Consider also $P(t), Q(t)\in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of coefficients equal to $d^2+d\tau$.

For a root $\xi$ of $G(t)$, I want to check if $F(\frac{P(\xi)}{Q(\xi)})$ is equal to zero or not.
What is the most efficient way of doing this in terms of bit complexity?