texts: Reducing from Hamiltonian Cycle problem to the Graph Wheel problem

texts:
EDIT: This question is different from the other in a sense that unlike it this one goes into specifics and is intended to solve the problem. In the previous post, the only answer was a hint. In this post, the answer is a proper solution.

Is there a way to "polynomialy" reduce the problem of finding graph wheel $W_{n}$ to the problem of detecting Hamiltonian Cycle
(or vice versa) ? The ultimate goal is to show that finding $W_n$ is NP-complete problem. So far I can show that the problem is in NP. To show that I claim that given an input of graph it is possible in polynomial time to check every vertex and to make sure that it has three edges(except the hub): one goes to the hub, one goes to the next vertex and one to the previous vertex. By checking every vertex in this fashion one can make sure the "ticket" indeed represents $W_{n}$.

As far as converting from the Hamiltonian Cycle problem to the problem of fining $W_n$ goes I have encountered that $W_n$ has many Hamiltonian cycles inside it.It is easy to see if one imagines a wheel with  a hub and bunch of spokes. Every triangle created by the spokes forms a Hamiltonian cycle as well as any other "closed loop" formed inside a given $W_{n}$.

The intriguing part is the fact that only one vertex is in "the way" and that vertex is the hub. Is the hub of the wheel main culprit in figuring out the conversion ?


texts: Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$

texts:
I am looking for an unrestricted grammar which generates the following language:

$\{ a^1\#a^2\#a^3\# \dots \#a^k \mid k >0 \}$

That is, words like $a\#aa\#aaa\#aaaa\# \dots \# \text{$k$ times '$a$'}$.


texts: Determining whether a CFG is $LL(k)$ for any $k$?

texts:
In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable.

Is there a similar result showing that it is undecidable whether a given CFG is an $LL(k)$ grammar for some choice of $k$?  Or is this problem known to be decidable?


texts: Is my proof of my greedy algorithm to find subsequence correct?

texts:
Credit to KleinBerg and Taros Book

Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. Purchases at stock exchanges—what’s being bought— are one source of data with a natural ordering in time. Given a long sequence $S$ of such events, your friends want an efficient way to detect certain “patterns” in them—for example, they may want to know if the four events:

{buy Yahoo, buy eBay, buy Yahoo, buy Oracle}

occur in this sequence $S$, in order but not necessarily consecutively. They begin with a collection of possible events (e.g., the possible transactions) and a sequence $S$ of $n$ of these events. A given event may occur multiple times in $S$ (e.g., Yahoo stock may be bought many times in a single sequence S). We will say that a sequence $S'$ is a subsequence of $S$ if there is a way to delete certain of the events from S so that the remaining events, in order, are equal to the sequence $S'$. So, for example, the sequence of four events above is a subsequence of the sequence

{buy Amazon, buy Yahoo, buy eBay, buy Yahoo, buy Yahoo, buy Oracle}

Their goal is to be able to dream up short sequences and quickly detect whether they are subsequences of $S$. So this is the problem they pose to you: Give an algorithm that takes two sequences of events—$S'$ of length $m$ and $S$ of length $n$, each possibly containing an event more than once—and decides in time $O(m+n)$ whether $S'$ is a subsequence of $S$.

Here is my pseudocode to this solutions:

set i and j to 1
when i <= S.length & j <= S'.length{
    if S(i) is the same as S'(j)
    then increment i and j by 1
    else just increment i
}
if ( j > S'.length) {
    return true
else
    false

My proof of correctness of optimality:

Let $A = (j_1,\cdots,j_m)$ be the sequence found by our greedy solution and hence return true, and let $B = (l_1,\cdots,l_n)$, be the sequence found by an optimal solution and also returns true.

We prove by induction that the greedy algorithm will succeed in returning true if a match was found and will ensure that $j_m \ge l_n$, showing that the greedy is as optimal as the optimal solution.

Base:
Consider the case where $m = 1$ and $n = 1$, then the algorithm let $j_1$ of $A$ and $l_1$ of $B$ be the first events found and hence $j_1 >= l_1$.

IH:
Now the case where $m > 1$ and $n > 1$, and assume $m-1 < A.\text{length}$ and $n-1 < B.\text{length}$, and by the IH, we have found events matching the subsequence and hence also $j_{m-1}$ and $l_{n-1}$, has a match, giving use $m-1 \ge n-1$. Knowing that the next for either solutions would be at $j_m$ and $l_n$ and hence $A=B$, and hence $j_m \ge ln$. Hence the greedy is as good as the optimal.
///

Would this be a way to prove the optimality as I cannot find another optimal that takes more than $O(n+m)$, hence just showing that the optimal and greedy would give the same result.?? Very confused.

Thanks in advance.


texts: What would be the probabilty of a randomly generated tree to be a Red-Black Tree

texts:
The question is not related to the homework

I was working on a homework, and the specification was to generate a random tree with n elements(n being in the thousands for the assignment) and asked me how many of the trees generated were RBT. I have been iterating to the millions now, so I began to wonder what was the probability of this happening, that a tree with lets say 1000 randomly inserted elements, that have randomly generated colors(red or black) is a Red-Black Tree.


texts: Finding a subset in bipartite graph violating Hall's condition

texts:
We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are conected to some of the vertices from $U$. If for every choice of $U$ we have $|U| \leq |V|$ (Hall's condition) then there exists a perfect matching (Hall's theorem).

But in our graph we know there is no such matching. That means there exists some set of vertices $U$ violating Hall's condition, and I'd like to find it with complexity around $O(n^3)$ - hints instead of full solutions are most welcome.

What I already tried was finding the maximum matching first, and then searching for our subset, but I couldn't figure out how to do this. Also, I thought of ways of reducing this problem to some max-flow (as you do with the maximum matching) but it also seemed to me like a dead end.


texts:
Let's say we have 10 people, each with a list of favorite books. For a given person X, I would like to find a special subset of X's books liked only by X, i.e. there is no other person that likes all of the books in X's special subset. I think of this special subset as a unique "fingerprint" for X.

I would appreciate suggestions on an approach for finding such sets. (While this reads like a homework problem, it is related to a problem in my biology research that I am trying to solve.)


texts:
Data structures are seen as important, equal to algorithms. This view is especially encouraged in situations, where appropriate data structure is the main factor that allows an algorithm to exist and to perform at satisfying complexity.

However, despite the additional features of data structures (e.g. organization, like in trees storing entries according to less-like relation), all that data structures do is keeping information unchanged between algorithm's actions. Can this generic feature of data structures be izolated and defined in abstract way?


texts:
How would you go about proving that this Language is Context free.  I'm having issues with drawing the PDA for this.

I need to prove Prove that the language L = {w | number of 11s in w is more than the number of 010s} is context free.

I so far assume that when a string of 11s occur add x to the stack and when 010s add y to the stack, but I'm having issues drawing that part out the part were you check to see if the number of x's in the stack is greater then the number of y's.

Update based on GoodDeeds answer, just need to clearify something
Basic PDA Input, Pop -> Push

"Whenever a 11 is encountered, and the top of the stack is not a y, push an x. Else, pop a y."

So in this case whenever a 11 is encountered do I draw out the transition like example A or B?


texts: What is the best way to prove (S+)+ = S+?

texts:
Lets say I have the below language:

S = {a, b}

So if we apply Kleene plus to that language, it is something like:

S+ = {a, b, aa, bb, ... ..}

If we apply Kleene plus to above language again, It is something like:

(S+)+ = {a, b, aa, bb, aaa, bbb ... ..}

What are the best words/way to describe that  (S+)+ = S+?

Obviously, S+ is all concatenations of words in S excluding the /\ (the empty string)

In this case, (S+)+ is all concatenations of words in S+ excluding  /\

So that means (S+)+ includes the words in S+. Is this a good proof?


texts: Why Modus ponens works with Horn clauses and Generalized Modus ponens requires definite clauses?

texts:
I am reading the Artificial Intelligence: A Modern Approach book and in the chapters about logic i noticed that in propositional logic the Modus ponens inference rule (used by the forward and backward chaining algorithms) requires the KB to be a conjunction of Horn clauses, while in first order logic the Generalized Modus ponens requires that the clauses are definite clauses.

The reason why it is like that is not explained anywhere.
I would say that even in propositional logic we should consider only definite clauses because a goal clauses is like: Symbol1 Λ .. Λ Symboln => False and even if i can apply the Modus ponens rule i would add to the KB False which i don't think it's useful at all.

So does anyone know why there's that difference and we don't just use definite clauses in both cases?


texts: Can Dijkstra's algorithm be modified to return paths with ascending edge-id's?

texts:
Say that each edge in a directed graph is labelled with an ID. I want to run Dijkstra on the graph to find the shortest path between $source$ and $destination$, with the additional restriction that the shortest path must be in order of ascending ID's. For example, if the path is from $ A \to B \to C $, then $ID(Edge_{AB}) < ID(Edge_{BC})$.

Is this feasible in polynomial time with some modification of Dijkstra?


texts: Show that for any real constants $a$ and $b$, where $b > 0$, $(n + a)^b = \Theta(n^b)$

texts:
I'm currently studying growth of function chapter in Introduction to Algorithm. In exercise 3.1-2 the question is:

  Show that for any real constants $a$ and $b$, where $b>0$,
  $(n + a)^b = \Theta(n^b)$.

I understand I need to find constants $c_1$, $c_2$, $n_0 > 0$ where

  $0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$ for all $n \geq n_0$.

But I don't understand what should I do after above step. Looking at the solution, it shows

  $n + a \leq n + |a|$
  $n + a \leq 2n$, when $|a| \leq n$

and

  $n + a \geq n - |a|$
  $n + a \geq \frac{n}{2}$ , when $|a| \leq \frac{n}{2}$

How did they come up with $n + a \leq n + |a|$ and $n + a \geq n - |a|$ just from $0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$ ? Are they derived from $0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$  ? Or are they just a general knowledge that can help solve this problem?

Please help me to understand them.

Thank you!

UPDATE:
I have updated the question to be more specific.


texts: Polynomial LP-based algorithm for cost minimization of DAG weights modification

texts:
Given a DAG $G=(V,E)$, with non-negative weights $ w_e \, \forall e\in E$, we want to modify (increase/decrease) the weights such that:

$\forall u,v\in V$ and $\forall p_1\neq p_2 $ paths from $u$ to $v$, the weights ratio of $p_1$ and $p_1$ is at most 2.
After modifications, the weights are non-negative

The cost of modifying the weight of an edge $e$ is $ c_e \, \forall e\in E$. The goal is to minimize the total cost of modification, namely $\sum_{e\in E}c_e|w_e-w'_e|$, where $w'_e$ is the weight of $w_e$ after the modification.

When formalizing this problem as a LP, there's an exponential number of constraints (as the number of paths between all the vertices is exponential). I thought maybe there's a property of the DAG that can be helpful, either to avoid the exponential number of constraints, or to establish an oracle for the LP.

Any ideas?


texts:
Let $f(n) = (\log n)^n$
   and   $g(n) = n^2$

By taking a large value, I could make out that $f(n) > g(n)$ .

I want to know if $f(n) \in \Theta(n^2)$ . For proving this, I need to find out the value of $c$ such that
$f(n) \le c \cdot g(n)$ .

How do I find the value of $c$ ? By seeing the function it seems like no $c$ exists. But I am not able to prove or disprove it.

Please help.


texts: Asking for references on errors, testing, system failures etc

texts:
I am looking for references that talk about the following subject:
Software programs are in general complex systems. That is, if we decompose them  into components and we make sure that each component is working correctly then we stil can have a lot of failures that arise from the interactions between the different components. Moreover, the assumption of being able to test separate component debatable. Often those components are also complex systems on their own. And even if we we test very small and indivisible components, we can still argue that making sure the component is working on 1000 cases (using unit testing for example) doesn't mean it's perfect. It probably have many hidden and undiscovered bugs.
Any book, talk, article, tweet etc. about the subject will help. Especially if it talks about how the community cope with this phenomenon.
Thanks


texts: Swap space management during pure demand paging

texts:
The following is a doubt that I came across while doing a OS home assignment - however, it seems more concept-based than a straightforward coding question, so IMHO I don't think the homework tag is appropriate for this.

In a pure demand paging scheme for multiple processes running at the same time, given a fixed amount of RAM and Swap memory, what happens in the following 2 cases w.r.t the swap space, when

A process encounters a page-fault, and there are no free frames available in the RAM, hence requiring one of the pages from the process' chunk of Kernel Frames to be written out to swap (for simplicity, I'm not considering the copy-on-write case). Explicitly, where in the Swap space would this frame be written, and what data structures need to be updated for that?
When a process needs to page-in a particular page, where does it look in the Swap memory, and how would it know if that particular page be present in Swap at all ?

As you can well imagine, I'm having difficulty understanding in what way to manage the Swap space during pure demand management scheme, and what data structures would be essential. It would be great if you could refer to any links in your answer (I searched in "Operating System Concepts - 8th edition by Silberschatz, I couldn't find an explicit answer for my question).


texts: How to do initialization of vector for an algorithm in MATLAB?

texts:
L=4;  N=4;  N_l=2;  P=10;

w = ones(L,1);
beta = ones(L,1);
%p = zeros(L,1);
H = sqrt(.5)*(randn(N_l,N)+1i*(randn(N_l,N)));
u_l = sqrt(.5)*(randn(N,1)+1i*(randn(N,1)));
u_i = sqrt(.5)*(randn(N,1)+1i*(randn(N,1)));
v_l = sqrt(.5)*(randn(N_l,1)+1i*(randn(N_l,1)));
u_l = u_l./norm(u_l,2);
v_l = v_l./norm(v_l,2);
u_i = u_i./norm(u_i,2);
for k = 1:L
    p(k,:)=P/L;
    w'*p(k)<=P

I have to generate random vectors for p^(0), u_l and v_l for l=1...L. Now I am confused about how to generate these vectors as l=1..L is the number of users, for example, I have L=2 then the generation of vectors should like p^(1) p^(2) for u_1 u_2 v_1 v_2 and after that, I have performed steps 1 and 2 respectively, for each l. Kindly guide me I am very confused.


texts: Turing machine, tape without blanks, does it halt or no?

texts:
So I'm lost on this one. We're given a turing machine and an initial tape. Tape is infinitely long in both ways, but all the blanks are taken out. The head is the leftmost nonblank. So the question is: If the Turing machine
halts on this input, then give the output sequence; if it does not halt, then answer “does not halt” and why.

Following the turing machine it seems to halt after q1 since  is the only operation.

Edit: and, if a state has only one operation such as  does that mean it automatically should halt?


texts: Is converting boolean formulas to sum-of-products a hard problem?

texts:
My reasoning is as follows.

Every boolean formula can be expressed as a sum-of-products.
Every sum-of-produts is a list of minterms.
For each minterm, there is 1 combination of inputs that satisfy the formula.

So if I have the sum-of-products representation of a boolean formula I can tell if it satisfiable.

But that is the SAT problem, which is hard.

So the hard part of the 3 step procedure above must be transforming a boolean formula into a sum of products.

Is this reasoning right?


texts:
Subset sum

  Input: A multi set $S$ of numbers and a natural number $t$
  Question: Does $S$ contain a subset $A$ such that $\sum_{x \in A} x =
 t$? (e.g., $\{1,1,2,3,4,5\}$, by multiset it means duplicates are allowed)

  Vertex cover

  Input: An undirected graph $G$ and a number $k$.
  Question: Does $G$ have a vertex cover of size $k$?

Show: vertex cover $\leq_P$ subset sum

My work so far:
 I need to somehow transform $(G, k) \to  (S, t)$

Above is a example graph $G$ that I constructed. It's vertex covers are $\{v_1, v_3\}$ so the size of the vertex cover is $2$, thus $k = 2$.

This is basically $S$

\begin{array}{|c|c|c|c|c|}
\hline
& e_1 & e_2 & e_3 & e_4 \\ \hline
v_1 & 1& 0& 0& 1\\ \hline
v_2 &  1& 1& 0& 0\\ \hline
v_3 &  0& 1& 1& 0\\ \hline
v_4 & 0& 0&  1&1\\ \hline
\end{array}

if $e_i$ and $v_j$ is incident I put $1$; otherwise $0$

Now what I need is a target $t$ to satisfy this.

The matrix above can be written in a set to be $S = \{1001, 1100, 0110, 0011\}$ if I were to add up all these values probably in base 2 since its binary, it would give me a value but I think I need a consistent value $t$, so this wont work. I'm also unsure how to integrate the $k = 2$ into this either.

Could someone help me construct this?


texts: finding the parent index in an interval heap (stored on an array) given a child index

texts:
an interval heap is a binary tree stored on an array where the size of each node is 2.

i would like to be able to find the index of a parent and find one of the child indices given the index of a node.

an example of an interval trees indices would be:

         [0,1]

    [2,3]     [4,5]

[6,7][8,9][10,11][12,13]

or

         [1,2]

    [3,4]     [5,6]

[7,8][9,10][11,12][13,14]


texts: computationally efficient linear index to index pair mapping

texts:
Consider two index sets $S = \{0, 1, 2, 3, 4, ..., N - 1\}$ and $Q = \{0, 1, 2, ..., \frac{N(N + 1)}{2} - 1\}$. Let $R = \{(a, b)\space |\space a, b \in S, a \ge b\} = \{(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), \dots\}$. There will be $\frac{N(N + 1)}{2}$ elements in $R$. Is there a one-to-one function $f : Q \to R$ that is computationally efficient?

One application is to map the linear memory index to row and column of a triangular matrix. Another application is to map thread numbers to work items in parallel programs where the work deals with pairs of items (triangular domain problems).


texts: Can a queue automaton recognize palindromes?

texts:
Consider the language of even-length palindromes $L = \{ WW^R \mid W \in \{0,1\}^* \}$. This language is surely context free and I need an NPDA to recognize it.

But, what if we replace the stack with a queue which supports insert and delete operations? Can a queue automaton accept $L$?


texts: Context free grammar where number of a's is larger than number of b's in any prefix of the string

texts:
The prefixes of the string aabab are a, aa, aab, aaba, aabab.
If the number of a's should be greater or equal to the number of b's, the grammar would be

S -> aS | aSbS | e,

but I need it with strictly more a's than b's in any prefix.
I thought of this grammar, but I'm not sure it is correct.

S -> aS | aSAbA | a
 A -> aA | aAbA | e


texts: Max flow but distribute evenly among candidate vertices

texts:
The max-flow algorithm finds the maximum flow through a graph given edge capacities. However, if there is an option between flowing through two edges, it will typically just leverage one of those edges fully and ignore the other. One can influence which of the edges should be preferred by using "min_cost_max_flow" and setting the costs of the preferable edges lower. However, this still makes some edges preferable compared with others. What if I want the flow to be evenly distributed among edges in such a situation? Here is a toy example. We can see that max flow leverages vertex-1 and flows 4 units through it. However, it could just as easily have sent 2 units through vertex-1 and 2 units through vertex-2. How can I make it do this? To make this concrete, we can say that the variance of flow across the edges should be minimized (with flowing the max volume possible being the first goal of course).

Note: I've posted a similar question on CS stackexchange: https://stackoverflow.com/questions/64635070/max-flow-modify-networkx-source-code-so-a-few-edges-dont-hog-all-the-flow. There, I'm not looking for the optimal solution in terms of variance, but any change to the source code (with toy code sample provided) that will make the flow less concentrated on the vertex in question in the toy example.


texts: Radon transform for advanced 3d graphics and games?

texts:
The Radon transform is used to take 2d projections of an object and create a 3d representation.

It seems like it would be possible to apply such a transform in 3d graphics in games (although possibly too slow to be practical).

For example, a very simple way to display an object is to use a 3d rectangle and texture map each side. This is relatively fast but the 3d detail is limited. When a side is parallel with the visual plane it will represent the detail 100% (so the visual detail would be limited to that of the texture map). Of course it won't represent external 3d effects properly, like lighting.

But by using the Radon transform one could gain a true 3d approximation of the object from the six textures/projections used. By increasing the number of textures/projections the approximation is better.

I'm curious if the idea has potential. Possibly for high-quality 3d models it might pay off in performance and size. Of course 3d models can be optimized to limit their size which also increases speed but visually doesn't change much.


texts:
I'm trying to assign running times to loops of code to roughly get the upper asymptotic ($O$) running time.

while (j < n2) {                                   # executes n2-1 times
    int k = 0;
    while ((k < n1) && (seq[k] < seq2[j])) {       # executes (n2-1)*n1times
      k = k + 1;
      }
     // we want to insert seq2[j] at seq[k]
     // so we move seq[k] through seq[n1 - 1] to the right
     for (int i = n1; i > k; i = i - 1) {         # some n-k times
        seq[i] = seq[i - 1];
      }
     seq[k] = seq2[j];
     j = j + 1;
     n1 = n1 + 1;
}

I know this is bad but would this algorithm worst running time be something in O(n^2) because there is one main loop and then two separate nested loops inside the main loop?

Thanks


texts: Exponential reduction vs Polynomial Reduction

texts:
I'm having trouble understanding reduction. Lets say you have a decision problem A that is NP-Complete. Also, another problem B the can be reduced from A.

What can you say about B if:

1) The reduction is done in polynomial time
2) The reduction is done in exponential time

I know that if A is reduced to B means that if we knew how to solve B, then solving A would be easy. But I don't understand what 1 & 2 signify.

Would it be right to say that for 1)
B is in the same Class as A

And for 2)
That B > then NP-Complete?


texts: What is the computation model of Prolog?

texts: Several computation models have representative programming language counterparts, as, according to this answer, Snobol for rewriting systems, APL for combinators, Lisp/Scheme for lambda calculus, and off course the family of imperative languages for TMs (or more precisely RAMs). It seems to me that Prolog should also be a paradigmatic language for some model. Is this assumption true? If so, what is the name of that model?


texts: Is there any proof that says "For each problem in NP there is a randomized algorithm that solves that problem in expected polynomial time."

texts: Is it known that "For each problem in NP there is a randomized algorithm that solves it in polynomial time"? If not true then is there any proof of that. Or does it belongs to the unknown domain?


texts: Find equivalent weighted DAG sum of whose weight is minimum

texts:
When a given weighted directed acyclic graph represents some object flow, what is the most efficient algorithm to find the equivalent graph sum of which edges is minimum? Here, 'equivalent' means the end state of the objects is the same.

The picture below is the trivial example of this problem.

Above, 'simplest' means least weight sum.

updated

Sorry, my problem specification was ambiguous. I updated the sample problem explanation.

update 2

To clarify the specification, I provide mathematical formulation.

Definition 1 transport mass map

Transport mass map T is a map between directed weighted graph to a set of pairs of node and transported volume.

for example,

Definition 2 equivalence in terms of transportation

In this problem, two graphs G1 and G2 are equivalent iff T(G1) is T(G2) the same sets.

Lemma 1 equivalence relation

If G1 ~ G2 means G1 is equivalent with G2 in this sense, ~ is equivalence relation in a directed weighted graph set.

Definition 3 equivalence set

For graph G, S*(G) is a set of graph such that
if a graph g in S*(G), g~G, and vice versa.

Definition 3 minimal graph in terms of transportation

Graph G- is called minimal for G iff the sum of G-'s node weights is minimum of all graph in S*(G)

Problem statement 1

What is (the most) efficient method to find G- when G is given.

Problem statement 2 (added)

What is the method above called generally?


texts:
A bit confused about whether this grammar is ambiguous or not

C' -> C
C -> d C u C
C -> d C
C -> ε

I tried building the DFA for this but I get this in one of the states:

C -> d C DOT u C, $
    C -> d C DOT, $

Isn't this a shift-reduce conflict, so surely it means the grammar is not LR(1)? Or does it reduce regardless since $ and u are both in the follow set of C? Is this not a reduce-reduce conflict since it goes to C regardless?


texts: Using Context free language to simulate regular expression in finite automata

texts: Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n number of non-terminal to store n states in the NFA?


texts:
Given a list of $N$ coins, their values $V_1, V_2, \cdots , V_N$, and a parameter of a total sum $S$. Find the coins the sum of which is S (we can use each coin at most once).

I was recently studying the very same problem from topcoder.com but there "we can use each coin any number of times". I am just stuck here if we can use each coin only once and not multiple times.

It will be very helpful if you can help or just give a hint. (this is not my homework quiz :P)


texts: Training given pairs of similar values, not labels

texts:
I have pairs of "similar" values $(x_i, y_i)$ drawn from a space $x_i, y_i \in S$, and want to train a neural network $N$ such that $N(x_i)$ would be "close" to $N(y_i)$ for all $i$, yet, to make it useful, the overall image of $N$ would be as spread apart as possible. Note that the training data says which values are similar, but does not imply that values from different pairs are necessarily different (i.e. these aren't labels).

Defining a cost function to be something like $\frac{1}{2} \sum_i \| N(x_i) - N(y_i) \|^2$ doesn't work, because $N(x) = 0$ would then be a trivial solution. Another option I considered is to require that, assuming the inputs are distributed with zero mean and unit variance, say, the outputs would be distributed with zero mean and unit variance too. I don't know how to efficiently enforce it though, or whether it would even give good results.

I see it as a kind of unsupervised learning with some "hints" provided.

So, my question is: what kind of problem is this? How to approach it? Can you direct me to any previous similar research?


texts: Time complexity of an algorithm for finding a cycle of fixed length

texts:
I am considering the following algorithm for obtaining a cycle $C_k$ of fixed length $k$ in an undirected graph $G$. Assuming $G$ is in adjacency list form, say $r \in G$ is the root for a truncated DFS of $G$. In typical fashion, be sure to mark nodes which have been visited. Do not go beyond depth $k-1$. In this way, the (truncated) DFS finds all paths of length $k-1$ that start with $r$. Now, check that the last vertex in any such path is adjacent to $r$. If so, we have a path of length $k$ that starts an ends with $r$; i.e., a $C_k$.

Now for each $v \in V$, run the above procedure with $v$ as the root node.

Initially, I had supposed that all of the above runs in time $O(|V|(|V| + |E|))$, where $O(|V| + |E|)$ is the runtime of a complete DFS. Is this actually the case, or is the above modified DFS less efficient?


texts:
I'm seeking some clarification on a description of the RAM model in CLRS on page 23, section 2.2 (Analyzing Algorithms).

Firstly, it is mentioned that we assume integers are represented with $c\cdot\log_2 n$ bits for some constant $c\geq 1$. Now take the integer value $2$, would it not be the case that we would need more than $\log_2 2=1$ bit to represent the integer value $2$? Since we must express two as $(10)_2$? Perhaps the constant $c$ is supposed to account for this discrepancy.

Secondly I'm a bit confused by this statement:
"We require $c \geq 1$ so that each word can hold the value of $n$, enabling us to index the individual elements...". I understand that if $c$ were $0$ or negative then that would not make any sense, however, are we also to assume then that $c$ must be an integer?

Any intuitive descriptions of these basic properties would be great or relevant examples someone can come up with.


texts: Efficient way to find matching date ranges?

texts:
We have a set of problems involving date ranges - a pair of dates representing a start date and an end date. In some places, we have say 1000 of these and need to find the ones that overlap a separate set of 1000 of these. But a linear search is exponentially expensive.

So is there an algorithm that is more efficient? (For data related to a single date, using the date as the key of a hashmap works, but not much help when there is a pair of dates.)

(The source of the problem is my commercial work where there are a large number of date ranged payments that need to be matched with another large set of date ranged payments. And the environment the code runs in applies hard limits to how much CPU time can be consumed.)


texts: Finding integrality gap for maximum weight independent set

texts:
One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum weight independent set, and I need to find an integrality gap of my LP relaxation.

As far as my knowledge goes, integrality gap for maximization problem is the the maximum ratio cost(LP)/cost(ILP) over all instances of a problem. But I've been googling for a little bit, and most examples only showed how to get a lower bound of integrality gap by taking some arbitrary instance. Is it possible to get an exact ratio?


texts: Proving NP-hardness of strange graph partition problem

texts:
I am trying to show the following problem is NP-hard.

  Inputs: Integer $e$, and connected, undirected graph $G=(V,E)$, a vertex-weighted graph

  Output:  Partition of $G$, $G_p=(V,E_p)$ obtained by removing any $e$ edges from $E$ which maximizes

  $$\max \sum\limits_{G_i \in \{G_1,G_2,...,G_k\}} \frac1{|G_i|}\left(\sum_{v_j \in V_i}w(v_j)\right)^{\!2},$$

  where $G_p=G_1 \cup G_2 \cup \dots \cup G_k$ and elements of $G$ are disjoint.
  $V_i$ is the vertex set for $G_i$ and $w(v_j)$ is the weight for vertex $v_j$

Plain English explanation:
We wish to partition a graph by removing $e$ edges to maximize an objective. The objective computes for each of the resulting disjoint subgraphs the sum of the vertices for the subgraph, squares that value, and divides by the cardinality. Finally we sum this over all subgraphs.

So far I have attempted to reduce from NP-hard problems such as ratio-cut, partition (non-graph problem), and max multicut. I've also attempted to show special cases of the problem are NP-hard (less ideal). The reason I suspect this problem to be NP-hard (besides most graph partitioning problems being NP-hard) is the presence of the cardinality term and cross terms between partition weights. Any input/problem suggestions would be helpful. A NP-hard proof for any kind of specific graph would be useful.


texts: Grid treaversal with forbidden coordinates

texts:
What alorithm/heuristic can be applied to get a shortest path to all the blue coordinates below without going through red coordinates? starting and ending in bottom left(0,0).

I have list of all the blue and red coordinates.


texts: About the SOS degree of a function and optimization algorithms for the function

texts:
Given a non-negative function on the hypercube $f : \{0,1\}^n \rightarrow \mathbb{R}_{\geq 0}$ one says that it is of "SOS-degree" of $d$ (denoted as $deg_{SOS}(f) =d$) if $d$ is the minimum $k$ such that one can find some finite number (say $p$) of polynomials on the hypercube $g_i : \{0,1\}^n \rightarrow \mathbb{R}$ ($i=1,..,p$) such that $deg(g_i) \leq k/2$ and $f = \sum_{i=1}^p g_i^2(x)$

Given a function $f$ do we know anything about the hardness of computing its $deg_{SOS}(f)$ ? What is the fastest algorithm or approximation known for it?

What does it mean in the bigger picture if it turns out that $deg_{SOS}(f)$ is large say $O(n)$ ? Does this immediately imply that the minimum running time required for an algorithm to get any constant fraction approximation of $max(f)$ or $argmax(f)$ is going to be exponential time?
I feel something like this should be true but I can't see such a thing being clearly written out..

Given any $f : \{0,1\}^n \rightarrow \mathbb{R}_{\geq 0}$ we can always write it as a SOS, $f = \sum_{v \in \{0,1\}^n} f(v) i^2_v$ where $i_v : \{0,1\}^n \rightarrow  \mathbb{R}_{\geq 0}$ is the characteristic function of the vertex $v \in \{0,1\}^n$ as in $i_v(w) = \delta_{vw}$. Like for the vertex say $(0,1,0)$ one can choose its corresponding $i = (1 - x_1)x_2(1-x_3)$.
(Is there any name for these "i" functions?)
Hence we have trivially, $deg_{SOS}(f) \leq n$


texts: Acceptance of empty string by nondeterministic automaton

texts: Why is the input $\epsilon$ accepted by the nondeterministic finite automaton shown below?  Does it not leave $q_1$ and go to $q_3$?


texts: Is $\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn})$ closed under polynomial reduction?

texts:
It's well known $EXP$ is closed under polynomial reduction. It means
$\bigcup_{c \ge 1} \mathsf{DTime}(2^{c^{n}})$ is closed under polynomial reduction. But what about $\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn})$? Is it also closed under
polynomial reduction?


texts: Is there a computer which can simulate all computers?

texts:
I have looked for proof that a machine cannot compute itself in more than realtime (Which would allow infinite computing speed) and I came to the conclusion that it is impossible for any computer to simulate all other computers. However, I lack proof of this intuition.

So the idea is that the state of every (modern, non-quantum) computer can be represented as a finite bitstring (just every state of registers, memory cells, and hard-drive...). However, in order to predict what this computer would do given any state, you would need a longer or at least equally long (in some trivial cases this might work) bitstring. But since there is always a bigger computer (with a longer bitstring - representation) there is no computer which can compute all computers.

However, I am wondering about the following:

Let $f$ be a function which maps a computable function $g$ and a valid input $i_g$ of that function $g$, to the result of $g$ given $i_g$:

$$f(g,i_g) = g(i_g)$$

Can you proof that:

$$\exists i_f: f(f, i_f)  \mbox{ does not halt, while } f(i_f) \mbox{ does.}$$

Note that $i_f$ is just a bitstring, and $g$ can be represented by a program and therefore can be a bitstring too...


texts:
I am trying to get a good grasp on Monte Carlo (MC) algorithms, but I feel I am missing something fundamental.

What I don't understand is how MC improves its confidence of giving the correct solution by running more executions.

So please correct me if I am wrong and assume that $Pr[false] \leq 0.5$. Assume we need to find the number of executions so that $Pr[false] \leq 0.125$, thus improving confidence.

Is it true that the number of needed executions is $3$, since $0.5^3=0.125$?

Thanks in advance...


texts: NFA accepting $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$

texts:
I have to construct NFA that accepts language $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$.

My solution is this automata:

Can you tell me, if this is correct or not? If yes, it is possible to construct this NFA with less states?


texts: How many bits needed to describe completely random function?

texts:
I read this sentence on mit.ocw and don't understand why this completely random function would need $|U|\log n$ bits to be described?

  Unfortunately, if we choose a hash function h that happens to be a
  completely random function from U to [n], we would actually need $|U|\log n$ bits to describe it.


texts:
From  Tanenbaum's Structured Computer Organization:

  Figure 2-4(a) illustrates a pipeline with five units, also called
  stages.

  If one pipeline is good, then surely two pipelines are better. One
  possible design for a dual pipeline CPU, based on Fig. 2-4, is
  shown in Fig. 2-5. Here a single instruction fetch unit fetches pairs
  of instructions together and puts each one into its own pipeline,
  complete with its own ALU for parallel operation.

  A different approach is used on high-end CPUs. The basic idea is to
  have just a single pipeline but give it multiple functional units, as
  shown in Fig. 2-6.  The definition of ‘‘superscalar’’ has evolved
  somewhat over time. It is now used to describe processors that issue
  multiple instructions—often four or six—in a single clock cycle. Of
  course, a superscalar CPU must have multiple functional units to hand
  all these instructions to. Since superscalar processors generally have
  one pipeline, they tend to look like Fig. 2-6.

I wonder what counts as a pipeline?

In Figure 2-4(a), a pipeline consists of 5 stages.

In figure 2-5, two pipelines share the same instruction fetch unit, but why isn't it a single pipeline?

In figure 2-6, a pipeline has multiple functional units, but why isn't it multiple pipelines?

Thanks.


texts: What is more important in an algorithm, small runtime or small memory usage?

texts:
I have two client-server protocols which perform the same function but they have different complexities in time (in terms of number of operations) and space (in terms of number of objects of same type). The size on which are based the complexities is $n$.

In the fist one, the server has to send only one object and the client has to perform $n$ operations.
In the second one, the server has to send $\log n$ objects and the client has to perform $\log n$ operations.

What is the best algorithm ? Does it depend on the environment of execution ?


texts: Is $L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not accept}\ 010 \} $ Turing recognizeable?

texts:
I'm working on the following problem:

  Is the following language Turing recognizable (recursively enumerable)
  ?

  $$L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not
> accept}\ 010 \} $$

The way I see it: Suppose that a machine $M$ loops forever on $010$. If a $TM$ recognizes $L$, it should accept $M$ in that case. But that means that it should know if $M$ loops forever or not, which is not possible. So, $L$ is not Turing recognizable.

Is my proof correct, and can it be more formal?


texts:
I am investigating PAC learning (computational learning theory) as a beginner with no previous knowledge of machine learning / AI. I am investigating the model mainly from a historical point of view.

For this, the most important things are of course the results based on the model. There are enough papers out there that document these results. But I also want to write something about what was going on before PAC learning, as to sketch the historical context up to where Valiant came with the notion of the PAC model.

No papers/surveys I've found so far document this, and as someone with no real knowledge of machine learning, it is hard to find this out. I am therefore asking this soft question here, because I believe there are enough experts that can help me with this. References are highly appreciated.

When I can research and study what was going on before PAC, I might get a better appreciation as to why the academic world is so enthusiastic about the PAC model, which is also something interest to document in my historical work!


texts: Showing that the language of graphs and nodes on an odd cycle is in NL

texts:
Let L be the language containing all the pairs (G,v) where G is a directed graph and v is a vertex in G such that G contains a cycle that contains v and the number of different vertices that appear in that cycle is odd. Find the smallest class (NP, P or NL) that contains L.

Clearly L is in NP, I didn't manage to show that it is in P so I tried to show that it's NP-Complete, however the answer in the textbook is NL?


texts: Local search to find minimum degree spanning tree

texts:
Suppose for a graph $G=(V,E)$ and a spanning tree T of G, $\Delta(T)$ is the largest degree of a vertex in T, and let $\Delta^*$ be the smallest such quantity over all spanning trees of $G$.

We have the following local search procedure which can changes spanning tree $T$ into a different spanning tree $T'$: We find an edge $e$ not in $T$ and add it to $T$. This results in a cycle $C$ - call its vertices vertices $V(C)$. We then delete an edge in $C$ incident to a vertex in $V(C)$ with highest degree.

My question is this: if $\Delta(T) > \Delta^*$, can we always find an edge $e$ to add, such that the maximum degree of vertices in $V(C)$ is strictly less in $T'$ than it is in $T$?


texts: Prove $\{xy \mid |x|=|y|, x \neq y\}$ is not a linear language

texts:
Show the language
$$L = \{xy \mid |x| = |y|, x\neq y\}$$
is not linear.

I've seen and proved a pumping lemma for linear languages, mentioned here:

If $L$ is linear then there exists a constant $p$ such that for all $w \in L$ with $|w| \ge p$ there is a decomposition $w = uvxyz$ such that:

$|uvyz| \leq p$.
$|vy| > 0$.
$uv^ix^iz \in L$ for all $i \geq 0$.

I'm trying to find a counterexample string.


texts: The pumping lemma for the context free languages

texts:
I am trying to use the pumping lemma to show this is not a context
free language
$$
L = \{a^n b^{2n} a^n\mid n\ge 0\}
$$

My idea is fist assume it is a CFG language and let $n$ be the pumping lemma
integer.

Then let $u=a^n b^{2n} a^n$ be a string. I am going to use to prove it is not
a cfg language

Since $u=vwxyz$ and must follow all three conditions for the lemma.

So

$|wy|>0$ and $|wxy|\le n$ thus now I chose the first group of $a$ in the left of my string

and do

$vw^2xy^2z$ since $wy$ cannot include $b$, my $wxy$ string includes all $a$.

So then

$v w^2 x^2 z\notin L$ because $a^{n+1} b^{2n} a^n$ is not in language.

But am I correct?


texts: Graph conductance - program/code/library

texts:
Technical question: is there any open source program/code/library which can compute (minimal) conductance of a given graph, probably by some simulated annealing?

Think it is quite well-known problem, but I cannot find anything like I mentioned above, but maybe you guys know? I know that it is a NP-hard task, but anyway, probably someone has written some programs.


texts: Regularity of unary languages with word lengths the sum of two resp. three squares

texts:
I think about unary languages $L_k$, where $L_k$ is set of all words which length is the sum of $k$ squares. Formally:
$$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} $$
It is easy to show that $L_1=\{a^{n^2}\mid n\in\mathbb{N_0}\}$ is not regular (e.g. with Pumping-Lemma).
Further, we know that each natural number is the sum of four squares which implies that for $k\ge 4$ all languages $L_k$ are regular since $L_k=L(a^*)$.

Now, I am interested in the cases $k=2$ and $k=3$:

$L_2=\{a^{{n_1}^2+{n_2}^2}\mid n_1,n_2\in\mathbb{N_0}\}$, $L_3=\{a^{{n_1}^2+{n_2}^2+{n_3}^2}\mid n_1,n_2,n_3\in\mathbb{N_0}\}$.

Unfortunately, I am not able to show whether this languages are regular or not (even with the help of Legendre's three-square theorem or Fermat's theorem on sums of two squares).

I am pretty sure that at least $L_2$ is not regular but unhappily thinking is not a proof. Any help?


texts: Growth function for non-regular languages

texts:
For language $L$ over an alphabet $\Sigma$ denote $\gamma_L(n)$ as the number of words of length $n$ in the language $L$. It is known that for regular languages this function represents a sequence with rational generating function (which is equivalent to that $\gamma_L(n)$ is linear-recurrent for sufficiently large coefficients).
However, I couldn't find any information about non-regular languages. And it is not clear how to extend the result, stated above to some other types of languages.
Does anyone know the conditions for some non-regular classes of languages (for example, prefix-closed languages) to have rational geodesic growth function?


texts: Converting Regular expression to DFA by building syntax tree

texts:
There is a way to convert regular expression to DFA (deterministic finite automata)
which is to build a syntax tree and then compute first pos, last pos, follow pos, and then use a Transition technique to build DFA for that particular regular expression. But this case only works when operators in the regular expression are only . (Dot), * (star), | (or). I just want to know if the operators in the regular expression are like ?, [], - and etc. Then can i convert regular expression to DFA just like above way?

Thanks in advance.


texts:
I wrote an algorithm for a leetcode question. The question asks:

  Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

My solution for this problem consists of a breadth-first traversal of the first tree s, and a function that checks whether any subtree of s is the same tree as t. The entire solution can be found here.

I am having a tough time figuring out the time and space complexity of this solution.

I understand that the isSame function has a time and space complexity of O(n). (See my explanation below), and the isSubtree function will call isSame for every node in s. However, the size of the input to isSame changes on each call, and I am having a hard time putting both pieces together to get an overall runtime / space complexity.

Explanation of isSame time and space complexity:

For the function that checks whether two trees are the same (isSame), the worst-case time complexity occurs when the trees are indeed equivalent. In this case, we will check every node and do a constant amount of work for each node, and thus our time complexity is O(n), where n is the number of nodes in either tree (they are the same). Furthermore, the function isSame function is recursive, and our time complexity will be linear with the height of the smallest tree. In the worst case, both trees are equivalent, and they have degenerated to a linked list, in which case the number of frames on our call stack will be the same as the height, which is the same as the number of nodes, so that's O(n) for the space complexity.


texts: What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm?

texts:
The perhaps most widely known algorithm converting finite automata into rational expressions is usually known as Kleene's algorithm. However, Sakarovitch in his book Elements of Automata Theory ascribes the algorithm to McNaughton and Yamada, who have indeed described it in their paper.

It might appear like a standard situation when one algorithm is ascribed to different authors. However, things seem to be more complicated. In fact, McNaughton and Yamada dealt with a converse problem (constructing a finite automaton to a rational expression) as well and Wikipedia's article on Thompson's construction refers to this algorithm as to the McNaughton-Yamada algorithm.

For this reason, I would like to ask what is the most correct name one can use for the Kleene/McNaughton-Yamada algorithm? In fact, I would also be interested in a correct name for a generalized algorithm, which works over arbitrary, say, complete (or closed, Conway, etc.) semirings. Thank you in advance.

P.S. Sorry for not providing a link to the McNaughton-Yamada paper, but I was not allowed to post more than 2 links.


texts: Cardinality of ordered n-grams and subsets of those n-grams from a given set

texts:
Given a set T={A,B,C}, I need to know the cardinality of all ordered sequential n-grams and the total cardinality of all subsets of those n-grams.  To be clear, the subsets MUST retain order as they appear in the original set.

The ordered sequential n-grams of the set T above are {{A},{B},{C},{A,B},{B,C},{A,B,C}} and its cardinality is 6.

The total cardinality of all subsets for those n-grams is sum(1,1,1,2,2,3)=10

So, given set T, what are the formulae for #1 and #2?


texts: Question on interpreting logical notation, relating to alphabets, theoretical comp sci

texts:
$\exists x \in \Sigma^* (t=sx)$

Have I interpreted the above into words correctly?:

"There exists a symbol 'x', which is a member of the set which contains all possible strings of alphabet sigma, where sigma contains string 't', which is a concatenation of string x and string s."

I'm not clear on how/whether t=xs is an alphabet.

Note: an earlier version of this question, with some errors, was posted at Math.SE.


texts: Any very user friendly resources on the Baum-Welch algorithm?

texts:
I'd like to understand the Baum-Welch algorithm. I liked this video on the Forward-Backward algorithm so I'd like a similar one for Baum-Welch.

I'm having trouble coming up with good resources for Baum-Welch. Any ideas?


texts: What are the advantages of cuckoo hashing over dynamic perfect hashing?

texts:
Dynamic perfect hash tables and cuckoo hash tables are two different data structures that support worst-case O(1) lookups and expected O(1)-time insertions and deletions. Both require O(n) auxiliary space and access to families of hash functions for their operations.

I think that both of these data structures are beautiful and brilliant in their own right, but I'm not sure I see how and when one of these would be preferable over the other.

Are there specific contexts in which one of these data structures has a clear advantage over the other? Or are they mostly interchangeable?


texts:
how can I find the regular expression for this intersection  ?
I've tried to find words but it did not help too much..
$$[\; (a+b)^* c^* (a+b)^* \;] \cap [\; (c+b)^* a^* (c+b)^*\;]$$


texts: Why is the minimum height of a binary tree $\log_2(n+1) - 1$?

texts:
In my Java class, we are learning about complexity of different types of collections.

Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height of a binary tree is $\log_2(n+1) - 1$, but doesn't offer further explanation.

Can someone explain why?


texts: Is the unweighted vertex cover problem equivalent to its weighted version?

texts:
Consider the unweighted and weighted versions of the vertex cover problem (UVC and WVC for short, respectively). As UVC is a special case of WVC, is it true that $$\text{UVC} \leq_\mathrm{m} \text{WVC}$$ but $$\text{UVC} \not \equiv_\mathrm{m} \text{WVC} \enspace ?$$

I think the first part is easy to prove, since one can construct an instance of WVC by taking an instance of UVC and letting the weight of all of its vertices be the same.

I find not that easy to prove the second part though. As WVC is a generalization of UVC, intuitively $\text{WVC} \leq_\mathrm{m} \text{UVC}$ can't hold, but I'd appreciate some help to demonstrate it in a formal way.


texts:
A (T)FNP problem is induced by a NP language, say $L$. Usually in the notion of verifers, we define $L=\{x:\exists y,V(x,y)=1\}$, where $V$ is a poly-time verifier. The function version would be finding the certificate $y$ (if exist).

However, the choice of verifier could be arbitrary, for example, the verifier for $HAM-PATH$ problem could be

Determinig whether the computation path of TM configurations is valid and reaches accepting state. (The Cook-Levin way).
Determine whether a path of input graph is Hamiltonian. (The natural way)

In order to make this definition "natural", we should probably show that, undere these different choice of verifier, the definition remains equivalent, i.e. the problem do not suddenly become harder/easier just because we introduce a different verifier.

  So here's my question:
  Is the choice of verifier independent with hardness of its functional
  problem? How do we justify this?


texts: As $-1 <\sin(n) < 1$, So $n^{\sin(n)}$ is bounded, but square root of $n$ tends to infinity. Is my logic correct? But from the other perspective, $1/n \leq n^{\sin(n)} \leq n$. I am confused.


texts: Euclidean geometry theorem proving complexity

texts: Euclidean geometry is complete, so the problem of determining whether a statement $A$ is provable is computable. Do we know its time complexity?


texts: Complexity and hardness of undirected path

texts: Let $PATH = \{(G,s,t) \mid \exists \text{path from}~s\text{ to }t\text{ in }G\}$, where $G$ is a directed graph. We know that $PATH$ is $NL$ complete. I am wondering what the complexity class of $PATH$ on undirected graphs is and whether any hardness results for $PATH$ on undirected graphs are known?


texts:
Would a class in Linear Optimization/Programming be useful for a CS degree?

What is it used for or how useful is it.

Can someone please help me decide.  Thanks in advance


texts:
Let T be an AVL tree of height 3. What is the smallest number of entries it can store? Note that a tree with one node (only the root) has the height of zero and stores one element.

The only method I could think of was just drawing an AVL tree and trying to minimize the number of nodes in which I get an answer of 7.

But this method is prone to error in my opinion and I'm not even sure if my answer is correct. So is there any method or equation to solve this without having to graph it?


texts: Big O and program calls with varied input sizes

texts:
Suppose I have a program p that has time complexity $O(n)$ and a second program q that calls program p $m$ times. If we know the input size of p will be the same every one of those times (n), we can say that the complexity of q is $O(m \times n)$. This case sounds pretty simple to me.

However, suppose the input size of p varies over these $m$ times, from $0$ to $m-1$.

If we knew that p ran precisely $f(n) = a \times n$ instructions for an input of size $n$, it would be simple: q would run $a \times 0 + a \times 1 + \ldots + a \times (m-1) = am(m-1)/2$ instructions exactly, which is $O(m^2)$.

However, in this case, all we know is that $f(n)$ is below $a \times n$ for all $n$ greater than some $n_0$, by the definition of big-O. We can't say for sure that $f(0) + f(1) + ... + f(m-1)$ is below $a \times 0 + a \times 1 + \ldots + a \times (m-1)$, because we don't know that $0, 1, \ldots, m-1$ are greater than this $n_0$. For this reason, I don't think we can say that q runs in $O(m^2)$.

Is there a way, in this case, when all we know is the big-O behaviour of p, to analyze q?

What if we replace all the big-O's with big-Theta's?


texts: What's wrong with the following shuffle algorithm?


texts: Which theoretical parallel model is closest to CUDA?

texts:
Which theoretical parallel model is closest to CUDA/OpenCL programming model?

For example, it fits at some degree to the generic Parallel Random Access Machine (PRAM) model. However, that is too generic, since it makes abstraction of various memory access latencies and synchronization issues.

My question is which is the theoretical model that CUDA architecture fits closest (having in mind the hierarchical parallelism of threads and blocks of threads that cooperate)?


texts: Help understanding formal language notation

texts:
I am reading this text and it is making absolutely no sense to me. It as if it assumed I will understand. Not to mention the writer apparently had a book made and his grammar is poor. Some of the plain English sentences do not even make sense or have the letter s on the end of words where they should not be. please help me understand this:

Language generators. A language generator is a device that can be used to generate the sentences of a language. A generator seems to be a device of limited usefulness as a language descriptor. Generators can more easily read and understand them. A language generation method constructs a language generator G and capable of generating a string of language by a process called derivation. For example, consider a language L over alphabet

  ∑ = {a, b}

  L= {a^n, b^n|n ≥ 1}

  G = {  s -> asb   s -> ab   s -> 3(i need to turn this symbol the
  opposite direction)}

W = aaa bbb

Derivation:

S ⇒ asb  ⇒ aasbb  ⇒ aaabbb

i.e., S ⇒ aaabbb It means we have derived aaabbb starting from start symbol S using the rules of language generator G in finite number of steps.


texts:
Regarding the following languages $L_1$ and $L_2$, I want to prove that $L_1$ is decidable and $L_2$ is undecidable. I want to construct a turing machine which can decide $L_1$ and reduce the halting problem to $L_2$.
$L_1$:
On input $w$ the turing machine $M$ never moves it's reading/writing head left. Where $w \in \{0,1\}^*$ and $\langle M \rangle \in \{0,1\}^*$ is the input of $L_1$.
$L_2$:
On input $w$ the turing machine $M$ moves it's reading/writing head in every step (making no neutral move). Where $w \in \{0,1\}^*$ and $\langle M \rangle \in \{0,1\}^*$ is the input of $L_2$.
For $L_1$: I know that a turing machine which can't move left, has no possibility of memorizing it's progress. It only knows the state it's in, so it's similar to a DFA. The difference is, that it reads and/or writes $\{0,1\}^*$ and the blank symbol $\square$. It's also different to a right-moving turing machine because it can do a neutral move. My idea was to construct a $TM$ having two tapes. So that the original tape would scan the input and 'copy' it to the second one. The problem I came across is that I have no possibility of recognizing any loop cycles, so that if $w$ was finished, the $TM$ would never stop writing blank symbols because the tape is infinitely long. Another idea was to construct a $TM$ in which no state has a self-loop. But in this situation I still wouldn't have prevented this infinite writing and I need a $TM$ which halts on every input to prove $L_1$ is decidable.
For $L_2$:
I want to reduce the halting problem $H = \{w\#x \mid M_{w}$ halts on $x\}$ to $L_2$ so I can prove that $L_2$ is undecidable. I had the idea of this function $f(<M>,x) \mapsto$ $<M'>\#w\#x$ where I put the input of $H$ into the function and get the input for the $TM$ $M_{{L}_{2}}$ which simulates $L_2$. In addition to that I know that the definition of $M_{{L}_{2}}$ states how it never makes a neutral move but always moves and reads either left or right.


texts: Using software to calculate the complexity of an algorithm

texts:
I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some resources where I can learn to calculate the complexity of an algorithm?

Secondly, is there some software that calculates the space and time complexity for an algorithm? I have seen that cyclomatic complexity can be calculated by software.


texts: Can you automatically generate a parser for a type using type theory some how?

texts: Was wondering since all the types are spelled out constructively, and the constructions can all be reflected symbolically on a computer, if you can automatically parse expressions in a type?


texts: Efficient Fast Fourier Transform to calculate the expected value

texts:
Suppose two people A and B draw a list of cards with difference scores n = {0, 1, 2, ..., n - 1}. Let $i \in$n such that $i \in [0, n - 1].$ Let $a_i$ be the probability that the person A draws a card with score of $i$, and let $b_i$ be the probability that the person B draws a card with score of $i$. In the event in which A gets $i$ score and B gets $j$ score, we define the expected gain of A's is $(a_i * b_j) * (i - j).$ We need to calculate the expected gain of A's.
My naive solution is $O(n^2)$ which counts all cases that A and B can happen and then add them together. Is there any hint how to use FFT to make the solution run in $O(n \log n)$?


texts: How to implement the details of shotgun hill climbing to make it effective?

texts:
I am currently working on a solution to a problem for which (after a bit of research) the use of a hill climbing, and more specificly a shotgun (or random-restart) hill climbing algorithmic idea seems to be the best fit, as I have no clue how the best start value can be found.

But there is not a lot of information about this type of algorithm except the rudimentary idea behind it:

  [Shotgun] hill climbing is a meta-algorithm built on top of the hill climbing algorithm. It iteratively does hill-climbing, each time with a random initial condition $x_0$. The best $x_m$ is kept: if a new run of hill climbing produces a better $x_m$ than the stored state, it replaces the stored state.

If I understand this correctly, this means something like this (assuming maximisation):

x = -infinity;
for ( i = 1 .. N ) {
  x = max(x, hill_climbing(random_solution()));
}
return x;

But how can you make this really effective, that is better than normal hill climbing? It is hard to believe that using random start values helps a lot, especially for huge search spaces. More precisely, I wonder:

Is there a good strategy for choosing the $x_0$ (that is implementing random_solution), in particular knowing (intermediate) results of former iterations?
How to choose $N$, that is how many iterations are needed to be quite certain that the perfect solution is not missed (by much)?


texts: How do I determine if this argument is valid?

texts:
I'm studying propositional logic the section on "valid arguments".

A self-assessment question reads

"Show whether or not the following argument is valid"

$\frac{P}{C}$

I don't know what function to apply to P to calculate C.

The solution in the back of the book shows the following truth table:

Variables   Premise Conclusion
P       C      P        C
F       F      F        F
F       T      F        T
T       F      T        F  <--
T       T      T        T

So the conclusion is that the argument is invalid because the premise is true and the conclusion false.

I understand that of course, but how do I calculate Conclusion? Do I just guess what it should be?

My teacher had the following to say:

  If P is True, C is True. If P is False, C is False.

  Swap it for 'Premise - I am thirsty' & 'Conclusion - I drink some water'

  The conclusion is dependant on the premises. If there is only one, they > will never differ and a Conclusion will never be False, with a True
  Premise.

This answer flies in the face of the answer in the book.

I pointed this out to my teacher and got the following:

  My understanding is that P is the only variable; C is the conclusion that represents what P might be i.e True or False, once evaluated.

So... in conclusion I find myself still confused


texts: Sample compression scheme and bounding the VC dimension

texts:
There is a compression function takes any sample $S$, for which there exists a function $h ∈ H$ with $L_S(h)$, and compresses it to a subset of $k$ sample points. Similarly, there is a decompression function $\rho$ which maps this compressed set back to a classifier $h'$ (not necessarily in $H$), such that $h'$ makes no mistakes on the original sample $S$.
Let $C(H)$ denote the smallest natural number $k$ such that $H$ admits a compression scheme of size $k$. $\mathrm{VC}$ stands for VC dimension.
I want to prove that $$\mathrm{VC}(H) ≤ C(H).$$


texts: Reccurence $T(n) = \sqrt{n}T(\sqrt{n})+n$

texts:
Note: this is from JeffE's Algorithms notes on Recurrences, page 5.

(1). So we define the recurrence $T(n) = \sqrt{n}T(\sqrt{n})+n$ without any base case. Now I understand that for most recurrences, since we're looking for asymptotic bounds, the base case wouldn't matter. But in this case, I don't even see where we could define the base case. Is there any number we are guaranteed to hit as we keep taking square roots starting from any integer Do we just define $T(n) = a$ for $n<b$, for some reals $a$, $b$?

(2). On page 7, Erickson gets that the number of layers in the recursion tree L will satisfy $n^{{2}^{-L}} = 2$. Where is this coming from? I have no idea. I see that the number of leaves in the tree should sum to $\sqrt(n)\sqrt(n) = n$, but I have no idea where to go from there.

Any help is appreciated!

Notes I'm looking at: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf


texts: Is grammar that describes an equation in prefix (Polish) notation always unambiguous?

texts:
I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \, 5 \, * \, 4 \, 3$ using the following grammar and rightmost derivation:

$$Expr \rightarrow + \, Expr \, Expr \, | \, * \, Expr \, Expr \, | \, 0 \, | \, \dots \, | \, 9 \,$$

While I have no trouble taking the derivation and creating its parse tree, the question also asks whether the grammar is ambiguous. In the scope of what I've been taught, my only tool for proving ambiguity has been to find a different parse tree for whatever leftmost or rightmost derivation I have, thus proving multiple valid parses and ambiguity. However, I have not been told how to prove unambiguity. I am fairly confident that the grammar described above is unambiguous based partially on intuition, and partially because it's designed for prefix notation. I tried to generate new trees for a given string to prove ambiguity, but since the operator is always leftmost, I could not find any string in which multiple parse trees could be created. If I am mistaken, please let me know.

My question is this: Is it possible for grammar that describes strings using prefix (Polish) notation such as the one above to ever be ambiguous? My intuition tells me that it will always be unambiguous, but I was wondering why this might be the case.


texts: How do decompose this relation from 3NF to BCNF?

texts: Given a relation with attributes { A, X, Y, Z } and functional dependencies $AX\rightarrow Y, AX\rightarrow Y, Y\rightarrow A, Z\rightarrow B$, I would think that this would be in 3NF because there are no partial or transitive dependencies. What I don't understand is how to decompose the relation to BCNF by ensuring no relation has a determinant that is not a candidate key.


texts: Is the BPP class closed for union and intersection?

texts: Just like the title says. I want to prove that given two languages $L_1,L_2 \in BPP$, $L_1 \cup L_2 \in BPP$ and  $L_1 \cap L_2 \in BPP$


texts: Exponential search worst-case performance

texts:
I'm learning about Exponential search and I keep reading that the worst-case performance is $\log_2 i$ where $i$ is the searched index.

I tried with an array containing $1073741824$ elements ($1024\cdot1024\cdot1024$) and I searched for the $1073741823$th element (which is just $n-1$).

Therefore, I used the exponential search to get the range containing $i$ (which was $[536870912, 1073741824]$) and it took $\log_2 n$ to find. Then it took another $\log_2(n/2)$ to find the right index using Binary search in this range only.

Am I doing something wrong? Or is the complexity of the worst-case $2\log_2 n-1$ ?


texts:
I'm having a very hard time understanding what's what.

$$L_{1}\leq_{p}L_{2}$$

If $L_2$ is stated to be in $\textbf{NP}$, is it necessarily true that $L_1$ is $\textbf{NP}$-Complete? I need to show the following for an assignment, but I'm having a dispute with a fellow student because he claims that I can't claim that $L_1$ is $\textbf{NP}$-Complete...

  Suppose that $L_1\leq_p L_2\leq_p L_3$. Also suppose that $L_3$ is in $\textbf{NP}$. Explain how to solve $L_1$ deterministically in exponential time.

I say (and I could be wrong - and that's a strong possiblity since I have very little understanding of this material) that since $L_3$ is in $\textbf{NP}$, $L_2$ also has to be in $\textbf{NP}$, and so therefore $L_1$ has to be in $\textbf{NP}$. And if that's the case, then $L_1$ can easily be converted to a deterministic algorithm through a breadth first search through the non-deterministic computation tree. Is there something I'm missing?


texts: Does exponentiation reduce to multiplication or the other way around?

texts:
Is is more accurate to say that in complexity theory:

$$\text{exponentiation} \leq_p \text{multiplication}$$

or

$$\text{multiplication} \leq_p \text{exponentiation}$$

I understand that if we know how to do multiplication, then we can run multiplication in a loop in polynomial time to get the answer to the exponentiation problem.

But which of the two reflects this? Do we say exponentiation reduces to multiplication (the first one), or the other way around (the second one)?


texts: Can the Global Minimum Cut problem for a directed graph be solved using the minimum s-t-Cut

texts:
I am using the following definition of the Global Minimum Cut problem:
Given a graph $G = (V,E)$, a Cut of $G$ is a partition of $V$ into two subsets $(A,B)$.
A cut-edge of $C$ is an edge $(u,v) \in E$, with $u \in A$ and $v \in B$.
A Global Minimum Cut of $G$ is a Cut which is the Minimum in some metric.
For my purposes this metric is always considered to be a weight/capacity. For undirected graphs it is well known that the Minimum s-t-Cut from among all s-t-Cuts in the graph is equivalent to the Global Minimum Cut.
I was wondering whether or not the same approach has any application for directed graphs. In this case, it seems to me like a Global Minimum Cut seeks to destroy a graph's weak connectivity, whereas the approach over s-t-Cuts will only ever guarantee the destruction of a graph's strong connectivity. Am I missing anything that would solve this problem?


texts: Closed formula for two variable recurrence

texts:
I would like to know if there exists a closed form formula to the following recurrence:

$f(s, 0) = 1$
$f(s,b) = \displaystyle\sum_{i=1}^{min(s, b)} \left[
  (s-i+1)\times f(i, b-i) \right] $

This recurrence gives the solution to problem F of the ICPC Latin American regionals of 2019.

The problem itself can be solved in $O(n^2)$ by using dynamic programming and keeping a matrix of precomputed sums. I'm just curious about if there is some technique that allows obtaining a closed formula to recurrences like this, so I can solve it in better runtime complexity.


texts: How to reduce constrained proofs to 0-1 IP

texts:
Consider the following problem:

Can $X$ be proven in fewer than $Y$ steps, from axioms $Z$, with finitely many transition rules $\tau$?

This lies in $NP$, since if I supply a proof $M$, and individual steps can checked against the list of possible transitions $\tau$ in polynomial time, then $M$ can be checked for length $<=Y$ in linaer time, and verified for correctness in $Y*O(n^{O(1)})$

What isn't clear is how to reduce this generic "finite resource" automated theorem proving problem, to 3-SAT.

Obviously it should be reducible since $3-SAT$ is NP Complete but it's not clear how to do that.


texts: Post numbers in DFS tree of an undirected graph

texts:
How could you prove:
An edge (u,v) is part of an undirected graph G. If post(u) $<$ post(v) (i.e. the post number of u is smaller than that of v) then it implies that v is an ancestor of u in the DFS tree.

So far I have understood that it does in fact imply that so I need to prove this. I have thought of doing it by contradiction but not exactly sure how I would go about doing that.


texts: Is there a solution set for Knuth's The Art of Computer Programming series?

texts:
Is there a solution set for the books in The Art of Computer Programming series written by Donald Knuth?

I've found solutions for Concrete Mathematics using Google, but not the above series.


texts: Find similar vector by Locality Sensitive Hashing

texts:
I have many vectors in my database. They are in high dimensions such as:

$v_1$ : $\langle 23, 23, 1, 33, 103, 219, \dots \rangle$
$v_2$ : $\langle 92, 83, 1, 33, 239, 192, \dots \rangle$
...

I will use Hamming distance to calculate their difference: The
difference between $v_1$ and $v_2$ is $4$ because elements $3$
and $4$ are the same and others are difference.

Now, I want to use Locality Sensitive Hashing (LSH) to put those
vectors into different bins.

  What kind of hash function can I use for this case?

I have read some article about universal hash function, but I am
not sure can I use it and how to ensure that the probability for
the similar vectors going to the same bin is higher than those
non-similar one.

Here is the way that I think how should I use the universal hash
function for my task.

I will first divide those high dimensions vectors into sub-vectors:
$$x : 23, 23 \; | \; 1, 33 \;  | \; 103, 219 \; | \; \dots$$

sub1-x : 23 23
sub2-x : 1 33
sub3-x : 103 219

The following function will be used for each sub-vector:
$$sum_{i=0}^{r} a_{i}x_{i} \mod m$$

Basically this is a dot product, a = {a_1, a_2, ... a_i}, x =
{23, 23, 1, 33, 103, 219 ...}, m is a prime.

Different combination of {a} will form a different hash table, one hash table is used for one sub-vector.
I can now hash the data into bins, but the question is

  Is this an LSH method?  I don't know that two similar vectors  will go into the same bin with a high probability.


texts: Simplifying SOP: implementing OR with NAND

texts:
I am learning how to implement basic logic gates using NAND. I have learnt that you can use De Morgan's theorem as such:

$a+b = \bar{\bar a} + \bar{\bar b} = \overline{(\bar a *\bar b)}$

In other words, we would need two NOT gates (which are basically NAND gates), and another NAND gate.

However, I want to practise Boolean algebra simplification. Using a truth table I have formed the Sum of Products:

$f(a,b)=ab' + a'b + ab$

I have worked down a number of paths unsuccessfully. I would appreciate if someone could either show the steps of simplification, or give me some guidance on the laws to use to achieve this simplification. If there are any notation mistakes I have made, please let me know :)


texts: How do you describe a language that is generated by Context Free Grammer

texts:
I am familiar with describing Regular Expressions but when it comes to describing CFG I get confused. Do you describe it in words like you would regular expressions or do you do something like this ?

this is the CFG I am trying to describe

S -> SS
S -> XXX
X -> aX| Xa| b

I was thinking something like this

S-> SS
  ->XXXS
  ->aXXXs
  ->abXXS
  ->abXXS
  ->abXAXS
  ->abbaXS
  ->abbabS
  ->abbabS
  ->abbabXXX
  ->abbabbXX
  ->abbabbbX
  ->abbabbbb
  ->abbabbbb


texts: Increasing an edge weight. Shortest time to recompute an $MST$?

texts:
I have an $MST$ tree $T$. I increase the weight of a single edge $e$ by $c$(a non negative constant).
I need to recompute an $MST$ as fast as i can. How I do this? The idea I had in mimd is to remove $e$ from $T$. Loop over all crossing edges between the two "halves" of $T$. See which one is minimal weight. Add her instead.
This will require $O(|E|)$ time. Is there a faster idea? Or does my idea requires less than $O(|E|)$?
I suspect a more efficient algorothm exists because i do not use the fact that $e$'s weight increased.


texts: Dynamic Programming Travel Planning Problem

texts:
You want to visit n cities: $0 → 1 → 2 → · · · → n$.

For traveling between city $i$ and $i + 1$ $(0 ≤ i < n) $ you need to choose between two modes of transportation: train or plane. You are starting at the train station of city $0$ and want to end up at the airport of city $n$.

The cost of transferring between the train station and the airport of city $i$, either direction, is $b_i$. The cost of traveling from city $i$ to city $i+1$ via train is $t_i$ and by plane $p_i$.

You need to use to use the plane and train exactly $n/2$ times. Assume that $n$ is divisible by $2$.
Design an $O(n^2)$ dynamic programming algorithm that finds the cost of an optimal solution to the travel planning problem.

What I have so far is what I think is a solution to the problem without considering the $n/2$ constraint.

$Cost(x, i, y) = \begin{cases} \begin{cases}t_i & y=0\\ p_i + b_i & i-y=0 \end{cases} & i=1 \\ min\begin{cases} \begin{cases} min\begin{cases}p_i + Cost(P, i-1,y-1) \\ p_i + b_i + Cost(T, i-1,y-1) \end{cases} & y > 0 \\ inf & y=0 \end{cases} \\ \begin{cases} min\begin{cases} t_i + Cost(T, i-1,y)\\ t_i + b_i + Cost(P, i-1,y) \end{cases} & i-y > 0\\ inf & i-y = 0\end{cases}  \end{cases} & 1 < i < 0  \\ min\begin{cases}p_i + Cost(P, i-1,y-1) \\ t_i + b_i + Cost(T, i-1,y) \end{cases}  & i=n \end{cases}$

The values of $x$ correspond to different scenarios for which station at $i$ you are located at.

$x = P$

$x = T$

The value of $y$ is the number of plane rides and $i-y$ is the number of train rides $0 \le y \le i$

To get the optimal cost with $n/2$ plane rides you would call $Cost(x,i,\frac{x}{2})$


texts: Can the encodings set of a non-trivial class of languages which contains the empty set be recursively enumerable?

texts:
Let $C$ be a non-trivial set of recursively enumerable languages ($\emptyset \subsetneq C \subsetneq \mathrm{RE}$) and let $L$ be the set of encodings of Turing machines that recognize some language in $C$: $$L=\{\langle M \rangle \mid L(M) \in C \}$$

Suppose that $\langle M_{loopy}\rangle \in L$, where $M_{loopy}$ is a TM that never halts.
I wonder if  it is possible that $L \in \mathrm{RE}$?

By Rice's theorem I know that $L \notin \mathrm{R}$ (the set of recursive languages), so either $L \notin \mathrm{RE}$ or $\overline{L} \notin \mathrm{RE}$. Does it have to be the first option since $M_{loopy} \in L$?


texts: Measuring the length of a "loop" in a linked list in $O(n)$ Time?

texts:
I have been given a linked list in Python. At some point, one of the nodes is linked to a previous node creating a "tail" and a "loop":
Node1 -> Node2 -> Node3 -> Node4 -> Node5 -> Node6 -> Node3
Node1 and Node2 are considered elements of the "tail", while Node3, 4, 5 and 6 are considered elements of the "loop".
My task is to measure the length/number of elements in the "loop".
My approach was to go through the linked list and catch, when a node points towards a node, I have already passed.
However, to check if a node has been already passed, I have chosen to store all passed nodes into a list/array.
Whenever I approach the next node, I check, whether the next node is already stored in the list/array.
This approach does work, however I was hinted, that there is a way to solve this in linear complexity.
If the linked list consists of n nodes
I am adding 1 element to a list with each node
and I am also checking every element in this list with each node
I assume the complexity is something like : $\frac{n^2 + n}{2}$ which is clearly not ideal.
However I struggle to find a way to check whether I have already passed a node, without checking all previous nodes with every step. Which again would make it necessary to

Keep a list of all previous nodes and
Loop over this list in each step

which then again would increase the complexity.
Is there a way to check, whether I have already passed a node, without checking on all previous nodes?


texts: Is there an O(n log n) algorithm for 4D line simplification?

texts:
The Ramer-Douglas-Peucker algorithm for line simplification has worst-case $O(n^2)$ runtime. For suitably distributed random inputs, it has expected $O(n \log n)$ runtime complexity. In 2D, there are other algorithms with worst case $O(n \log n)$ runtime complexity, which compute exactly the same result as the Ramer-Douglas-Peucker algorithm. Since these algorithms are based on a "path (convex) hull" datastructure, it is not obvious whether they can be generalized to 4D lines.

Is there a (randomized) algorithm which has (expected) $O(n \log n)$ runtime (independent of input) for the case of 4D lines? You may assume Euclidean distances and a global absolute tolerance.


texts:
I've implemented an algorithm, that when analyzed should be running with the time complexity of $O(n \log n)$.

However when plotting the computational time against the cardinality of the input set, it seems somewhat linear and computing $R^2$ confirms this somewhat. When then sanity checking myself by plotting $n$ on the $x$-axis and $n \log_2 n$ on the $y$-axis with python, and plotting this it also seemed linear. Computing $R^2$ (scipy.stats.linregress) further confuses me, as I get $R^2=0.9995811978450471$ when my $x$ and $y$ data is created as so:

for n in range(2, 10000000):
    x.append(n)
    y.append(n * math.log2(n))

Am I missing something fundamental? Am I using too few iterations for it to matter? When looking at the graph at http://bigocheatsheet.com/ it does not seem linear at all.


texts: Conditions for an Language to be infinite

texts: given 'r' , a regular expression that does not include λ or ∅, What are the Conditions of 'r' so that L(r) would be infinite?


texts: Quantified Boolean Formula vs First-order logic

texts: Is Quantified Boolean Formula (QBF) the same as First-order logic (FOL)?


texts: Property testing of a complete multipartite graph

texts:
Propose and prove an $\epsilon$-test for the following property in the dense graph model: $G=(V,E)$ is a complete multipartite graph. That is, there exists a partition $V=V_1\cup\ldots\cup V_\ell$ such that $uw\in E$ if and only if there are $i\neq j$ such that $u\in V_i$ and $w\in V_j$.

I have been stuck at trying to solve this question for a few days. I tried to devise an algorithm along the lines GGR98 for bipartiteness testing (such as here), where we sample a sets $U$ and $S$ of size $\mathrm{poly}(1/\epsilon)$ and try to "self-correct" $S$ based on a small number of "partitions" induced by $U$. In particular, I am not sure how to define "violating edges with respect to $U$" for the above mentioned property. Any help?
EDIT: The number $\ell$ is not given to the algorithm as input. In other words, the task is to determine if there exists an $\ell$ such that the graph is complete $\ell$-partite.


texts: What is this hash of array data structure called?

texts:
I've created a data structure that is a hash of arrays with a special property: the hash keeps track of the combined order in which items are appended to its arrays.

For example (pseudocode):

h = HashOfArray()

h["a"].append(1) // accessing an unset key returns an empty array
h["b"].append(2)
h["a"].append(3)
h["b"].append(4)

h["a"]
>>> [1, 3]

h["b"]
>>> [2, 4]

h.items()
>>> [1, 2, 3, 4]

I'm struggling with coming up with a good name for this data structure. Does it have a commonly used name? I've called it HashOfArray but that fails to convey its main property: that it maintains the combined append order of the arrays.

Example implementation in Ruby:
https://gist.github.com/kajic/7981533


texts:
In the HRRN scheduling, priority formula is

P = (W+E)/E , where W: waiting time and E: estimated run time.

CPU finds the job that has highest priority value and does that job.

However, the formula is equivalent to P = 1 + W/E. If we just "minus 1" and make a new formula P' = W/E, the order of jobs does not change.

So the question is, why do we use P = (W+E)/E rather than P' = W/E? Is there any specific reason (like P must be greater than 1)? Or are they just using the original formula since it was made?


texts: What exactly does a relationship in ERwin DM signify?

texts:
I am working on a project that requires the creation of a database. Of course we have used ERwin, which seems to be a well known tool for data modeling. My team member just completed the implementation of our database in ERwin. However, the relationships between tables do not remind of how they looked in Microsoft Access. It seems as though the relationships are just created on the entire table. In Microsoft Access, the relationships were established on attributes inside the table. I guess my only question is, what do the relationships established in ERwin signify? I assume that it just has to do something with cardinality but I could be completely wrong.

Image of ERwin DM implementation: http://imgur.com/a/FkW16


texts: How to purge a linked list in $\mathcal{O}(n\log n)$ time?

texts: I was wondering how to remove duplicate values from a linked list in $\mathcal{O}(n\lg n)$ time. I have an idea that by using merge sort when we want to compare elements for choosing the small one, if they are equal advance on pointer and just consider one element. Any alternatives?


texts: Algorithm better than Greedy for Dominating set

texts: I just want to know that whether there is an algorithm better than the Greedy Algorithm for Dominating set. I know that Greedy gives $O(\log(\Delta))-approx$ and we can not do something better than $log \Delta$ for dominating set unless P=NP. But I came across this paper for $k-$ set cover which gives some improvement over $H_k$-approx for $k$-set cover. Is there something like for Dominating set also?


texts:
I'm task to solve a problem in UVA and its problem 305 in particular well its easy to program it just brute forcing stuff. Part of the task is to find the big Oh of the program using frequency count

#include<stdio.h>

const int goodjoseph[] = {2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881};
char k;

    int main(void){

        while(scanf("%u",&k) && k){

            printf("%u",k);
            printf("%d\n",goodjoseph[k-1]);
    }

        return 0;
    }

from school we were taught basics of frequency count like

int x=1;      ---- 1
while ( x<=n) ---- n-x+2 = n+1
x = x + 1;    ---- n

Total = 2n+2
thus having big o(n);

can you help me find the frequency count for

while(scanf("%u",&k) && k){


texts:
I'm trying to implement counting sort in Haskell for a list of type (Int, String). I've been trying to do it according to Wikipedia's description.

After some attempts, I gave up, because the Wikipedia description makes heavy use of mutation in different places throughout the algorithm, which I just don't know how to translate to a declarative language.

So my question is, does counting sort require mutation or can it be implemented in a language like Haskell without fancy constructs?


texts: Prove Matrix Correspondence is NP-complete

texts:
Consider the following problem. Given a $m \times n$ integer matrix $A$ and a $p \times q$ integer matrix $B$, do there exist one-to-one functions
$$r:\{1,2,...,m\} \rightarrow \{1,2,...,p\}$$
$$c:\{1,2,...,n\} \rightarrow \{1,2,...,q\}$$
where for all $1 \leq i \leq m$ and $1 \leq j \leq n$, $A[i,j] \leq B[r(i),c(j)]$?

What is the best way to show this problem is NP-complete? I am currently considering reducing the clique problem to this problem.


texts: Does NP-completeness require to find the solution?

texts:
In the paper "Computing Equilibria:A Computational Complexity Perspective" by Tim Roughgarden, they consider the problem:

Problem 2.1 (Clique).  Given a graph $G = (V, E)$ and an integer $k$:

if there is a set $K ⊆ V$ with $|K| = k$ and with $(i, j) ∈ E$ for every distinct $i, j ∈ K$, then output such a set;
otherwise, indicate that $G$ has no $k$-clique.

Then they claim that Problem 2.1 is NP-complete in the Theorem 2.7.

My question is about the part (1).  I always thought NP-completeness is for yes/no problems and thus they didn't require that the the solution be output if the decision is an yes?

So is this definition of NP-complete problem 2.1 right? Or should part (1) be rephrased as "if there is a set $K \subseteq V$ with $|K| = k$ and with $(i, j) \in E$ for every distinct $i, j \in K$, then output yes;

The Problem 2.1 is a half decision problem and half feasibility problem, what are such problems called?

P.S the paper can be found at http://theory.stanford.edu/~tim/papers/et.pdf

I went through Optimization version of decision problems and still not sure where Problem 2.1 belongs to.


texts: N songs, M instruments, how to pick K instruments to cover maximal amount of songs

texts:
I have $N$ songs, $M$ instruments.

Each song requires one or more of the $M$ instruments in order to be played.

My $K-1$ friends and I want to learn to play $K$ different instruments, and we want to pick them such that we maximize the amount of songs we will can play.

How would I efficiently solve this? I'm sure this problem maps to some well known computational problem, but nothing comes to mind at the moment.


texts: Worst case analysis of $100n + 5$ for different $n$

texts: For the function $f(n) = 100n + 5$, what is the asymptotic complexity of $f(n)$ in terms of Big O notation. I guess it is $O(n)$, but how can I prove it ?


texts:
I have an algorithm that solves the Vertex Cover problem.   The algorithm is

  Repeat while there is an edge:

  Arbitrarily pick an uncovered edge $e = uv$ and add $u$ and $v$ to the solution.  Delete $u$ and $v$ from the graph.

I know this strategy is a 2-approximation to Vertex Cover and that its worst example is the complete bipartite graph $K_{n,n}$.  In this graph, the algorithm will return a vertex cover of size $2n$ whereas the optimal solution is of size $n$.

Question: Does there exist a graph with Minimum Vertex Cover of size 10 where this strategy finds a minimum vertex cover?


texts: Eliminating $\varepsilon$-productions during elimination of left recursion

texts:
I'm following the algorithm for left recursion elimination from a grammar. It says remove the epsilon production if there is any.

I have the grammar

$\qquad S \to Aa \mid b$
$\qquad A \to Ac \mid Sd \mid \varepsilon$

I can see after removing the epsilon productions the grammer becomes

$\qquad S \to Aa \mid a \mid b$
$\qquad A \to Ac \mid Sd \mid c \mid d$

I'm confused where the $a \mid b$ for $S$ and $c \mid d$ for $A$ come from.
Can someone explain this?


texts: Being a computer organizations and architecture expert

texts:
One of the greatest challenge in learning one is how broad the literal computer science is. Just talking about memories and CPUs would just took you to endless adventure of this technology. How does the expert manage to understand all of this if I ever want to be one of them?

Maybe someone ever be on my position, not just want to survive the exam but wanted to be the expert of this field especially on the hardware side and rarely ever grasp all the concepts.


texts: A programming language that can only implement computable bijective functions?

texts: Are there programming languages(or logic) that can implement(or express) a function $f:\mathbb{N}\to \mathbb{N}$ if and only if $f$ is a computable bijective functions?


texts:
Given  $N$ circles and $Q$ points. What is the optimal solution for checking "if point is covered by any circle" for every point?
The trivial solution would be $O(QN)$.


texts:
I'm reading a theorem about existence of a simple set.
The definition of an immune set can be found from here

A set ${\displaystyle I\subseteq \mathbb {N} }$ is called immune if ${\displaystyle I}$ is infinite, but for every index ${\displaystyle e}$, we have ${\displaystyle W_{e}{\text{ infinite}}\implies W_{e}\not \subseteq I}$. Or equivalently: there is no infinite subset of ${\displaystyle I}$ that is recursively enumerable.

I am not able to understand this definition, because I couldn't come up with example.


texts:
I am trying to relate the following integer square root theorem

$\forall x: \mathbb{N}, \exists y : \mathbb{N}((y^2 \leq x) \land  (x < (y+1)^2))$

and its proof to its role as a specification of the Integer Square Root isqrt ($\lfloor \sqrt{x} \rfloor$) function in a Haskell program.

Below is a inductive proof of the theorem and the related Haskell program.
The proof was done using natural deduction in the Fitch system, hence there are notational differences between code and proof e.g. no $\leq$ in Fitch.

For my question the details of the proof are not important. I wish to focus on the base case, and the two cases involving  $\exists$-Elimination and $\lor$-Elimination.

I used Quickcheck as a reasonable check that the theorem holds in the code.

I can see that cases 1 and 2 in the proof correspond to the guard conditions in the Haskell definition of isqrt function. I did not specify, prove, and implement  the function isqrt in any structured way. I just used any examples I could find. I believe that there must some more formal transformation from proof to code that I am missing. So despite having written both the proof and code the precise correspondence between both eludes my comprehension.

Is there a technical name for this form of proof to program relation?
I would be grateful for an explanation or pointer to the literature.

module Peano where
import Test.QuickCheck

data Nat = Z | S Nat deriving Show
-- addition
(+@) :: Nat -> Nat -> Nat
Z +@ y = y
(S x) +@ y = S (x +@ y)
-- multiplication
(*@) :: Nat -> Nat -> Nat
x *@ Z = Z
x *@ S y = (x *@ y) +@ x
-- square
sqr x = x *@ x
-- equality
(=@) :: Nat -> Nat -> Bool
Z =@ Z  = True
(S m) =@  (S n) = m =@ n
_=@ _  = False

-- lesst than
(<@) :: Nat -> Nat -> Bool
Z <@ Z = False
Z <@ x | not(x =@ Z) = True
x <@ Z | not(x =@ Z) = False
(S x) <@ (S y) = x <@ y

-- less than or equal
(<=@) :: Nat -> Nat -> Bool
x <=@ y = if (x =@ y) || (x <@ y) then True else False

-- Integer square root function
isqrt Z = Z
isqrt (S x) | (sqr (S (isqrt x))) <=@  (S x) = (S (isqrt x))
            | (S x) <@ (sqr (S (isqrt x))) = isqrt x

-- test with Quickcheck
instance Arbitrary Nat where
 arbitrary = oneof [return Z, (S  <$>  arbitrary) ]

isqrtPostCondition :: Nat  -> Bool
isqrtPostCondition x  = (sqr (isqrt x) <=@ x) && (x <@ sqr(S (isqrt x)))
check = quickCheck isqrtPostCondition
-- +++ OK, passed 100 tests.


texts: Does anyone have any ideas on a seating chart optimization formula for a call center environment? There are "docks" in which the workers sit. Each dock has approximately 15 seats, some more some less. The workers are on teams and work the same schedule and sit in their dock together. The problem is there are more teams than there are docks. Some work day shift, some work mid shift, and some work night shift. The formula would need to identify where the "optimal" bay would be for each team based off of number of workers, days worked, shift start time, and shift end time. Any ideas? Thanks!


texts: How to construct and write down a Turing machine for a given language?

texts:
In my class we just started learning about Turing machines.  I think I understand the concept but am unsure how to syntactically solve any problem related to one.  I am presented with the problem:

  Build a Turing machine accepting $(b + c)^+$$\#a^+$  (Please comment your
  code. Any uncommented solutions will not be graded.)

I am unsure of how to actually begin devising this machine? Could someone please help get me started?


texts: Is this version of clustering still NP-Hard?

texts:
Let the set $A = \{a_1,...,a_n\}$ of objects and $d(a_i,aj) \quad \forall i,j\in[n] \quad i\neq j$.
Let $\;C=\{C_1,...,C_k\}$ the set of clusters, split the elements of $A$ into $C$ such as there is not $C_i$ empty.

We need to maximaze the distance between clusters which is the minimum  distance between all the elements of different clusters.

$$max_{\{C_1,...C_k\}}\ \{min_{x_i \in X} \{{min_{x_j \notin C(x_i)}}\; d(x_i,x_j))\}\} $$ where $C(x_i)$ is the cluster of $x_i$ and $\{C_1,...C_k\}$ are all the possible partitions of $C$

I think the problem above is a simplification of K-means clustering, is there any differences?


texts: Difference between ways to compare floating-point numbers

texts:
There seems to be many approaches to judge whether two floating-point numbers are identical. Here are some examples I've found:

fabs(x - y) < n * FLT_EPSILON * fabs(x) OR fabs(x - y) < n * FLT_EPSILON * fabs(y)
fabs(x - y) < n * FLT_EPSILON * fabs(x + y)
fabs(x - y) < n * FLT_EPSILON * fabs(x + y) || fabs(x - y) < FLT_MIN)
fabs(x - y) < n * FLT_EPSILON * sqrt(x * x + y * y + FLT_EPSILON * FLT_EPSILON)

I'm really confused about them. Suppose there is a best way to compare two floating-point numbers, which is the simplest as well as the most accurate, the other approaches shouldn't even exist. So these different ways must have there own pros and cons.

My question is: To do "real computations", which approach is the most accurate one?

Reference links:

http://accu.org/index.php/journals/1558 (1 and 4)

https://stackoverflow.com/a/10335601/5399734 (2 and 3)