texts: Remove duplicates from dictionary in a safe and clever way

texts:
I have a dictionary that has keys and multiple values per key. Same value can be assigned to multiple keys.

For the sake of simplicity, the keys are ints and the values are strings,
so that it would look like in C#:

Dictionary<int,string[]>

As an example the dictionary is filled as follows:

{ 1, ["A","B"] },
{ 2, ["A"] }

I now have to remove duplicate values, under the condition that each key keeps at least one value (if at all possible).

So we cannot say 1 gets A, because 2 will then have no associated value anymore.

The result for the example should be:

{ 1, ["B"] },
{ 2, ["A"] }

Another example with result:

{ 1, ["A", "B"] },
{ 2, ["C", "D"] }
-->
{ 1, ["A", "B"] },
{ 2, ["C", "D"] }

One key cannot contains multiples times the same value, so the following scenario is not considered, it cannot happen:

{ 1, ["B"] },
{ 2, ["A", "A"] }

What I tried so far, but where I am not sure if I captured all edge cases or if there are more efficient or more logic ways:

If a key has only one value assigned, this is fixed. The value is removed from all other keys and the key value pair is removed from the iterating list and stored elsewhere

1.1 If after that removal one key does not have any values associated, the algorithm failed, it is not possible.

1.2 Repeat 1. until no key with only a single value is left.
Search for values that are only assigned to one key. The key value pair is removed from the iterating list and stored elsewhere
Repeat 1. to 2. until 2. does not find a result
No we have a list with only n to n relations. All keys have at least 2 values and each value is at least assigned to 2 keys.
Now we randomly remove one value from a single key.
Repeat 1. to 5. until nothing changes anymore.

Is there a standard algorithm for this requirement? I am still not sure if I considered all edge cases.


texts: Triangulating an n-sided x-monotone simple polygon as a strip?

texts: This is the problem above. Can anyone help me here?


texts: What is the official name of a specific type of combination algorithm

texts:
Say that I have the following set of variables:

[A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z]

The values represent a list of variables from a dataset.  Each variable has a certain level of correlation with the target variable $.  The correlation increases or decreases depending on the sort of combination you use against your target $.  For example, BCJX might have a higher correlation with $ than OQTVW.  I'm going to test each possible combination against the training algorithm and output it all, with their accuracy score, in a concise CSV file.  But I don't know the name of the algorithm that might combine these variables in every possible way.

In other words, I want to find the combination with the highest correlation value and the smallest dimension.


texts: Detecting cycles with weight zero in a directed graph

texts:
I am given a directed graph $G=(V, E)$ with a weight function $w: E\to\mathbb{R}$, that doesn't contain negative cycles.
I need to find an algorithm that returns true if and only if there is a cycle with weight zero in the graph.
The time complexity needs to be $O(|V||E|)$, so I thought about using Bellman-Ford algorithm, but I have two problems with that:
First, the graph doesn't necessarily connected, so I can't pick an arbitrary source vertex for the algorithm.
Second, I can't figure out how the algorithm can help me, and what I can do with its output.
I know that a similar question have been asked, but the answer just suggests to run Bellman-Ford algorithm, but as I mentioned, I can't choose a source vertex. In addition, I don't understand why the suggested answer will work at all.


texts: I'm taking a computational structures course and we just started going over context free grammars. I was confused when I started seeing lambda productions. What are they? Can't seem to find an answer anywhere.


texts: Is data received after transmission immediately stored and can that be recovered?

texts: When I send a message from one device to another, during the process during which the other device is receiving the data, is that data stored temporarily on some place on the device or is it immediately stored on the hard-drive of the device. and while using TCP when you receive an ACK does this mean that that data has been stored on the hard drive or is it stored when everything is received. For example, I am sending an essay to a server which makes a download link for another person and then send that link back to me, for sharing. Now during the process of sending that essay on the server I cancel halfway, so can I determine whether the essay was stored on its main drive or not (just an example).


texts: Time complexity of finding predecessor for a dictionary implemented as a sorted array

texts:
I'm currently reading "The Algorithm Design Manual" by Steven Skiena. On page 73, he discusses the time complexity of implementing $ Predecessor(D, k) $ and $ Successor(D, k) $ and suggests that it takes O(1) time.

If the data structure looks something like

[(k0, x), (k1, x), ...]

where the keys k0 to kn are sorted, given k, I thought the successor(D, k) would first have to search the sorted array for k ( $ O(log n) $ ) and then get the successor ( $ O(1) $ ) since the array is sorted, and hence the overall time complexity should be $ O(log n) $ instead of $ O(1) $ as mentioned in the book. This should also apply for predecessor(D, k).

For an unsorted array, the time complexity for predecessor and successor remain as $ O(n) $ since searching the unsorted array also takes $ O(n) $.

Did I misunderstand something?


texts: Given a truth table, force a contradiction

texts:
Suppose I have a formula, and a lying witness is attempting to make it evaluate to False.

  Given a truth table $c(F_1,…, F_n)$, how could you force a lying
   witness to contradict herself?

A contradiction is simply when the witness's statements are logically impossible; i.e. that $x_1,x_2$ are each True, but $x_1 \space AND\space x_2$ is False.

How can I characterize the set of all formula for which I force the witness to contradict herself?
What complexity class does this problem fall in?


texts: Halting problem of TM which recognize recursive languages is undecidable?

texts:
I am preparing for an exam and I came across this question in one of the tests.

  Halting problem of Turing machines which recognize recursive languages
  is undecidable. (True / False)

The solution given says the statement its False.

But I think the statement is True. Halting problem in itself is undecidable. We can't determine whether the Turing Machine will halt or not.

The test series has a history of wrong answers that's why I am seeking an explanation even if I am wrong.

Edit:
I was looking at the answers and I have trouble understanding the explanations. I know that 'By definition, recursive languages are decideable by Turing machines.'
I will tell you how I breakdown the question. I am given a TM and told that this TM recognizes a recursive language. How do I know that the TM will halt?


texts: Are exponential random graph models based on Maximum Entropy Principle?

texts: Can anyone shed light on whether or not ERGMs are network models based on the maximum entropy principle? Especially if we say that the available information about the network is in the form of network measures, that is, we know that that graph in question G has $x_1(G), x_2(G),...,x_k(G)$ where $x_i$ is a measure, such as, the number of edges, number of wedges, number of triangles, etc.


texts: Can memoization be applied to any recursive algorithm?

texts:
I am new to the concepts of recursion, backtracking and dynamic programming.

I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there is a  relation between memoization being applicable ONLY to top down recursive algorithms. Any explanation on the same would be greatly appreciated.

The Background to this question:

I have a naive inefficient recursive solution(below) a and wish to incorporate memoization but don't know if it is possible.

Problem Statement:  Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, Print the number of ways (non-distinct sets) this can be achieved.

Ex: Ex: N = 4 , S = {1, 2, 3}

1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1

My code:

public static int change(int n, int count, int sum) {

        if(sum == n) {
            return 1;
        }
        if(sum > n) {
            return 0;
        }
        for(int i = 1; i <=3; i++) {
            sum = sum + i;
            count += change(n, 0, sum);
            sum = sum - i;
        }
        return count;
    }


texts: Anomaly/outlier detection using fuzzy clustering

texts: I understand that fuzzy clustering using FCM produces a membership matrix for the set of data points we feed to it. What characteristics will an anomalous cluster produced during this method have? (Considering I only have unlabelled data)


texts:
I have the set:

B = {x ∈ {0,1}* | there is an equal number of 0's and 1's in x}

and therefore,

B* = {e,01,10,0011,0101,0110,1100,1010,1001,....etc}

I need to either prove or disprove that B*=B

I believe they are equal, because B* is just the concatenation of one string onto another. I think the trick is since the 0's and 1's have to be of equal number, that concatenating strings would keep the same number of 0's and 1's the same.

I just need a little help in the right direction as to prove B*=B. I was thinking of showing that if

B⊆B* and B*⊆B, that B*=B holds.

Any help would be much appreciated!


texts: Stopping condition for goal-directed bidirectional search for shortest path

texts:
So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*.

So let $l(u,v)$ be length of the (oriented) edge $u,v$, $\pi_f(v)$ the potential of vertex $v$ in forward search and $\pi_r(v)$ potential of vertex $v$ in reverse search and $d(u,v)$ length of the shortest path from $u$ to $v$. Let $s$ be start vertex, $t$ goal vertex. The algorithm selects vertices by $d(s,v)+\pi_f(v)$ forward and $d(v,t)+\pi_r(v)$ reverse.

Let's call $\mu$ the length of the shortest path found so far, $n_f$ the vertex on top of forward queue and $n_r$ the vertex on top of reverse queue. I found two ways

The obvious option is to stop forward when $d(s,n_f)+\pi_f(n_f)\geq\mu$ and reverse when $d(n_r,t)+\pi_r(n_r)\geq\mu$. It is also not needed to process edges that were already processed in the other direction. Here the $\pi_f$ and $\pi_r$ are independent can be very specific, but the algorithm may need to continue quite long after the shortest path was actually found if the potential function is significantly underestimating.
Create a pair of consistent potential functions as defined in this lecture. The requirements are given as
$$\pi_f(u) + \pi_r(u) == \pi_f(v) + \pi_r(v)$$
for each edge $u,w$ (which really means the sum has to be constant over the whole graph). Without loss of generality we can make $\pi_r(v) = -\pi_f(v)$ and use the normal stopping condition from non-goal-directed search expressed as
$$d(s,m_f)+\pi_f(m_f) + d(m_r,t)+\pi_r(m_r) \geq \mu+\pi_r(t)$$
(assuming we shift $\pi$ so that $\pi_f(s) = 0$).

This allows easier stop, but the potential function has to only indicate whether $v$ is closer to start or goal and for vertex (equally) far from both will be the same as for vertex in the middle of the shortest path. Therefore it will be less specific.

Now what I am looking for is:

anything that would give me idea which would be more efficient (without having to implement both and test them) and
whether the second can even be used if the heuristics is not monotonous, i.e. when $d(u,v) - \pi_f(u) + \pi_f(v) \ge 0$ does not hold (the linked lecture assumes that, but not doing so could save me a lot of data and I/O is a bottleneck, so I would prefer not to even though it means occasionally having to reprocess vertex).

1Some important optimization techniques can only be applied to bidirectional search.


texts: On which stage (lexical analysis, syntax analysys, and so on) is most of the compilation time spent?

texts: I know that during compilation we need to undergo several stages like lexical analysis, syntax analysis and so on. Which of them takes the most time?


texts:
My book says lexical analysis detects reserved words.

How can lexical analysis detect whether we are using reserved words in incorrect places ?

For eg :- while(a>0) and int while = 5.

How can lexical anaylsis differentiate the usage of while in both the above examples based on the context?


texts:
search problem: find the assignment that maximize the number of satisfied clauses

For decision problem: determine whether there is an assignment that satisfies k of clauses.

optimization problem : determine the number of clauses that maximize the number of satisfied clauses ( is this correct?)

If I want to reduce search to optimization, how would I do it? Or
how do I use the number of clauses (the answer from optimization problem)  to determine the assignment (the search problem)?


texts: Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

texts:
Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept.

I understand that the pumping lemma can be used to show that if a language has a length greater than the number of states, which is the pumping length, then it may not be a regular language. However, I don't understand how a language can be rejected by a DFA based on the number of accept states it has.

For example, I know that a* \cup b* is not a regular language because of the pumping lemma, but how do I know that it is not accepted by a DFA with only 1 accept state?


texts: Algorithm for determining minimal set of covering prefixes

texts:
I have a set of strings.  My goal is to find a minimal set of longest prefixes which will match most of that set.

For instance, if my set is:

abracadabra
abracado
abramu
banana
bananasplit
bananaicecream
xylophone
zebra
zeitgeist
zello

I would want the output to be:

banana (len 6, matches 3)
abra (len 4, matches 3)
xylophone (len 9, matches 1)
ze (len 2, matches 3)

Now, this question isn't yet properly specified.  That's because I'm ranking my results on two dimensions: maximum matches, and maximum length.  My goal is to find prefixes that cover as much as of the set as possible, which are as long as possible and thus less likely to occur in strings that aren't in the set (all other things being equal, of course).

Ideally, I'd like to find a set of very long strings, ranked by how much of the set they cover.

That's my goal.  Now I'll present my work, and where I need help.

FIRST Let's specify the problem better.  We want a set of prefixes.  For each prefix, we compute its length, and the number of matches it has in the set, and order the prefixes by their product.  I'm then free to pick the top X prefixes.

I think that's a good specification.

NOW Comes an efficient implementation.  Brute force is to check every possible prefix against every string, which is complexity n * n * m (n being number of strings, m being average length of strings).

An efficient algorithm?
Something like this:

Build a prefix tree of the set
Each leaf has value 1
Work up the tree, with each parent equal to sum of its children , plus 1 if it has an entry
Now we know each prefix and how many matches it has - I believe complexity is n log n
Walk through the tree, counting length of each string (complexity n * m)
And collect all the entries, sort them by length * value (complexity n log n)

That algorithm is roughly n log n, which is efficient enough.  Will it work? How should it be improved? What's a simple way to implement it?

Finally: Since all the data is in a Postgres relational database, I believe it would be simplest to do the algorithm using relational algebra with aggregate functions. Comments on this?


texts:
A Bloom filter uses a hash function to test membership in a given set $S$, by checking if an item is present of not at the specified position.

To mitigate the effect of hash collision, multiple functions are used, yielding probabilistic bound if using universal hash.

We can use 10 bits per elements to have 'reasonable' error rate.

If we could directly build a perfect hash function for the set  $S + \infty$, where the last element is one not present in $S$, then we could use only 1 bit per element and have perfect recovery.

What are the fundamental reasons why this reasoning is wrong ?


texts:
Hope you all are doing well.
I want your assistance. I have a PDA which is accepted by the final state. I need to convert it into cfg. So I want to ask,  If I want to first convert this into acceptance by an empty stack? If yes, then what is the procedure of converting PDA (acceptance by final state) into PDA (acceptance by empty stack).
Here is the question.
Convert the following PDA to a context-free grammar.
P = ({q, p}, {0, 1}, {Z0, X}, δ, q, Z0, {p}) has the following transition function:

δ(q, 0, Z0) ={(q, XZ0)}
δ(q, 0, X) = {(q, XX)}
δ(q, 1, X) = {(q, X)}
δ(q, ε, X) = {(p, ε)}
δ(p, ε, X) = {(p, ε)}
δ(p, 1, X) = {(p, XX)}
δ(p, 1, Z0) = {(p, ε)}

Any help shall be highly appreciated.


texts: How are bitwise operators used in normalisation of floating-point numbers?

texts:
After having spent a significant amount of time googling this topic, I am still struggling to confidently answer the following question:
Identify the process using logical operators to normalise a floating-point number.

My first assumption was, we use the binary shift to remove the leading 0's (for positive numbers) or 1's (for negative numbers) and then use XOR to increase the exponent by the required amount.
I do not understand, however, what happens to the binary point.
Let's say we have the number 1.75 represented as 000001.11 in 8-bits. If I shift it to the right by one place, I lose the 1 at the end. If I shift it to the left by 4 places, how does the computer know to move the binary point between the first two bits from the left? I am lost. How do bitwise operations work in this case?
Thank you in advance for your time and help.


texts: how to derive the complexity of the randomization solution to the majority element problem

texts:
The randomization solution is from  majority-element, and the corresponding complexity given confused me very much.

The complete procedure of calculating iterations give is :
$$
\begin{split}
EV(iter_{prob}) & \le EV(iter_{modif}) \\
& \le \lim_{n\to\infty} \sum_{i=1}^n i \times\frac{1}{2^i} \\
& =2
\end{split}
$$

I wanna know how to derive $ \lim_{n\to\infty} \sum_{i=1}^n i \times\frac{1}{2^i} $, and what does it stand for.


texts: Acceptance conditions when translating LTL to Büchi automaton?

texts:
As an exercise in better understanding, I have been implementing the LTL to Generalized Büchi Automaton translation algorithm of Gerth, et al. (which is also discussed in Clarke, et al., Model Checking).

What I have ended up with seems incorrect, but also seems to accord with the discussion.  Both of the presentations state that we should create a separate multiple sets of accepting states as follows: for each "subformula of $\phi$ [the LTL property to be checked] of the type $\mu U \psi$, there will be a[n accepting] set $F \in \cal F$ which includes the nodes $q \in Q$ such that either $\mu U \psi \not \in Old(q)$, or $\psi \in Old(q)$."  By the standard translation of GBA to BA, the BA will be compelled to step through an accepting state for each of these component machines infinitely often.

Can someone clarify this definition? It seems wrong to me for a few reasons, which suggests I have failed to comprehend it:

As I understand it, the definition of "subformula" means that any formula contained, arbitrarily deeply, in $\phi$ would have its own acceptance condition.  But surely this must be wrong, because, for example, an until condition buried in a release condition might not ever need to be satisfied. Even more simply, Clarke's textbook gives as an example the property $$ (A U B) \rightarrow F C) $$ which gets translated to $$( (\neg A) R (\neg B) ) \vee ( \top U C )$$ ($\top$ is the boolean constant true; Clarke, et al. use R for "release" where Gerth, et al. use V).  In this case, the algorithm as described seems to demand that we satisfy $(\top U C)$, but this is only a disjunct.  Perhaps that is correct because parts of the graph where this disjunct has not been introduced, will be accepting for it?
The following seems to be a more difficult example of the same question: $$((p U q) R r)$$ In this case, if r holds universally, then $(p U q)$ need never hold, so I don't believe I should have a GBA acceptance condition for it.
The discussion of the algorithm directs the implementer to translate into a negation normal form, which is what gives the subformula $( (\neg A) R (\neg B) )$, above.  But this is not an "until" subformula, so does not give rise to any acceptance condition at all, which means that it's not possible to satisfy the above disjunction by satisfying this release condition.  Is this an oversight? Should one be generating acceptance conditions for these subformulas, as well?  Looking at the experimental results reported, I see that the expression $$\neg (p_1 U (p_2 U p_3))$$ is listed as not having any entries in the acceptance table.  In a sense, this agrees with my expectation, because this is equivalent to $$\neg p_1 R (\neg p_2 R \neg p_3)$$  But surely this is satisfiable by infinite traces where, for example, $\neg p_3$ is always satisfied?  So why are there no acceptance states?  There's a caption to this example, but unfortunately, it's syntactically garbled: "The rightmost column represents the number of pairs in the acceptance table of the constructed automaton.  Notice that for the safety property ...[described above]... there are no U subformulas satisfy [sic].  Yet, for the automaton to be nonempty, it has to contain a reachable cycle. [???]"  I suppose in this case, it might be that when we translate this formula we get zero sets of accepting states and so vacuously any cycle is treated as accepting?  But even so that would leave the earlier disjunctive case...


texts: Why do we use worse-case when categorising problems?

texts:
Maybe I am wrong, but I read that when we categorise problems in their respective complexity classes, we use worse-case analysis.

Why don't we use the average case?

I imagine we could have a problem in NP when we look at it's worse-case, but when we look at it's average-case we could have a really efficient algorithm. This is just intuition and not sure of an example.

For something like cryptography, I'm guessing this is not desirable.


texts: Minimum spanning tree and its connected subgraph

texts:
This problem is from the book [1]. In case of being closed as a duplication of that in [2], I first make a defense:

The accepted answer at [2] is still in dispute.
The proof given by @eh9 is based on Kruskal's algorithm.
I am seeking for a proof independent of any MST algorithms.

  Problem: Let $T$ be an MST of graph $G$. Given a connected subgraph $H$ of $G$, show that $T \cap H$ is contained in some MST of $H$.

My partial trial is by contradiction:

  Suppose that $T \cap H$ is not contained in any MST of $H$. That is to say, for any MST of $H$ (denoted $MST_{H}$), there exists an edge $e$ such that $e \in T \cap H$, and however, $e \notin MST_{H}$.
  Now we can add $e$ to $MST_{H}$ to get $MST_{H} + {e}$ which contains a cycle (denoted $C$).

  Because $MST_{H}$ is a minimum spanning tree of $H$ and $e$ is not in $MST_{H}$, we have that every other edge $e'$ than $e$ in the cycle $C$ has weight no greater than that of $e$ (i.e., $\forall e' \in C, e' \neq e. w(e') \le w(e)$).
  There exists at lease one edge (denoted $e''$) in $C$ other than $e$ which is not in $T$. Otherwise, $T$ contains the cycle $C$.

  Now we have $w(e'') \le w(e)$ and $e \in T \land e'' \notin T$, $\ldots$

I failed to continue...

Algorithms, Chapter 5: Greedy algorithms
"Minimum Spanning tree subgraph"@StackOverflow


texts: Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

texts:
It is a classic problem to simulate a fair coin with a biased one.
According to Fair Coin (wiki),

John von Neumann gave the following procedure:

Toss the coin twice.
If the results match, start over, forgetting both results.
If the results differ, use the first result, forgetting the second.

In the worst case, the procedure may not terminate.
Problem: Is it possible to design an algorithm which guarantees termination in the worst case? What is the technique to solve such an impossibility problem?


texts: Does PDA epsilon transition only transition when there's no more input?

texts: For the Pushdown Automata episilon transition $\epsilon$ which is shorthand for $\epsilon; \epsilon / \epsilon$, does this mean that at any point, regargless of if there is input or not, you can transition to the next state?  Or does it only transition to the next state when there is no more input?


texts: Showing that a language is NP Complete (advice)

texts:
I am currently getting ready for my final exam in computational models. I know that there aren't any rules or rule of thumb to show that a language is NP-complete and each problem has its own tricks, but I am really struggling with questions where they give me a language and showing that the language is NP-complete by showing that an NPC problem is polynomial reducible to the given language.

So I wanted to ask for advice. How can I approach such problems? Are there any steps that I can take before to help me somehow? Or is it just literally figuring out which NPC problem is "closest" to the the given language and try to construct a polynomial reduction?

I'd appreciate any advice. Thank you.


texts: Why can't we flip the answer of a NDTM efficiently?

texts:
I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) states that it is unclear how another NDTM $T$ can determine in $O(n^{100})$ time how to flip $M$’s answer.

My Problem is as follows: A NDTM outputs $1$ iff there exists a sequence of non-deterministic choices that leads to the accepting state. Furthermore, there exists a universal NDTM $NU$ that can simulate every NDTM with only a small (logarithmic) overhead. So why can’t we construct T as follows: First, simulate M with the universal NDTM which should be possible in time $O(n\log n)$. Then output 1 – M’s answer. This would mean that we can flip the answer of any linear NDTM in time $O(n\log n)$.


texts: Given a Tree decomposition, How to find the tree decomposition of its subgraph?

texts:
You are given a tree decomposition of a large graph with not so small bounded tree-width.

Suppose now you need to solve a dynamic programming problem inside a subgraph and does not have time to do another costly tree decomposition.

How do I find the tree decomposition of a subgraph given the decomposition of its "father" graph?

(I googled for some data structure inside each bag of the tree decomposition but I haven't found anything.)

Thanks in advance.


texts:
When trying to decide on the choice of a programming language for a
specific task, people will often tell me: "use this language because it
has the best library for the type of problems you are addressing".

I would rather choose my language for its intrinsic qualities as a
programming medium. That implies that libraries should be more
universally usable.

What work has there been to create programming libraries that could be
programmed and used in different languages, being mechanically adapted
from one to the other on the basis of a standardized interface
language/formalism (or any other mean)? How succesful has it been?

For example, I found one system that claims to do that : Microsoft's .NET
Framework.
They say it is based on a Common Language Specification (CLS) which is defined in the ECMA-335 Standard: Common Language Infrastructure.

Are there others? What about free-software frameworks?

Pointers to relevant papers or web sites are an answer. A survey would
be best.

Note (June 7, 2013): this question is more controversial than is visible.
However, I cannot fathom the nature of the controversy. Some people
support the question and/or make cogent comments. But the people who
seem unhappy about it just downvote without a word of explanation. I
am sure they have a good reason to do so. But it would better help our
understanding of the issues, or possibly of the lack of issues, if
they were a little more explicit as to what irks them.


texts: Prove that $L=\{x\mid K(x) \leq |x|-c\}$ is recognizable, where $x \in \{0,1\}^*$

texts:
Basically I want to prove that the set of all c-compressible binary strings is recognizable.

My goal is to construct a turing machine $N$ such that, given an input string $x$, $N$ accepts $x$ if there exist a turing machine $M$ and a string $s$ such that $M(s) = x$, and $|\langle M \rangle|+|s| \leq |x|-c$. Since both $|\langle M \rangle|$ and $|s|$ are bounded by $|x|$, there are only finitely many $M$ and $s$ to run through, and the output of each $M(s)$ is either $x$ or not $x$, hence the algorithm halts in finite time, and so $N$ is a decider for $L$.

But this is clearly not the case because $L$ is not co-recognizable. Where is the flaw?


texts: Why does the solution of an NP problem have to be polynomial size?

texts:
I've read in "Introduction to Algorithms" (CLRS) that formal language $L$ is NP-language if and only if there is a polynomial verification algorithm $A(x, y)$ and a constant $c$ such that $$L=\{x\in\{0,1\}\mid \exists y \text{ with } |y| \leq |x|^c\text{ and } A(x, y)=1 \}\,.$$

What is the purpose of the constraint: $|y| \leq(|x|^c)$?


texts: Need help with a set-associative cache memory problem

texts:
I'm studying for my Computer Architecture exam next week, and I'm having problems understanding how a set associative cache works and how to solve related problems like this one :

"A set-associative cache memory uses a set of 8 words. A replacement procedure based on FIFO algorithm is implemented by means of 3-bit counter associated with each word in the set. A value in the range 0-7 is thus recorded for each word. When a hit occurs, the counter associated with the referenced word is set to 1; those with values originally lower than the referenced one are put in its place and put all others in reverse order. If a miss occurs the algorithm implemented the new word put in its place, show that this procedure works with this message "start ABCDEFGHIJKABCDEFLMNGHD end". Start with initial 8 words. then compute the miss ratio."

here is what I've tried so far ... I've inserted the first 8 letters into the cache, and then checked the following 15 letters for hits and misses whenever there is a miss I remove the oldest letter in the cache and replace it with the new one... not sure if my solution is correct to this point or not and I can't figure out the part about the counter and the part about the reverse order

I greatly appreciate any time taken to explain this to me as I don't understand the wording of the problem, and need a general guideline on how to solve such problem.
Thank you very much in advance.


texts:
I have two conditions A and B in a form of "ast tree".
How can I check that B is more strict than A?
I.e. if B is true then A is always true.

Example

A:
x = 1 and (b = 2 or c = d)

B:
y = 5 and x = 1 and (b = 2 or c = d)

Does B include A -> true

A:
x = 1 and (b = 2 or c = d)

B:
y = 5 and x = 1 and (b = 2 or c = d)

Does B include A -> false

This seems to be a common task for a specialist in logical math.
But I have only very basic knowledge about logical arithmetics.
Any articles/studies about subject appreciated.


texts:
Does $P=NP$ implies $3SAT$ reduces to $2SAT$?

If so then from $2SAT$ is $NL$-complete can we conclude $NP=NL$?


texts: Why do Shaefer's and Mahaney's Theorems not imply P = NP?

texts:
I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ?

Here's my reasoning:  Create a language $L$ which is equal
to SAT intersected by an infinite decidable sparse set.  Then $L$ must also be
sparse.  Since $L$ it is not trivial, affine, 2-sat, or Horn-sat, by
Shaefer's theorem it must be NP-complete.  But then we have a sparse
NP-complete set so by Mahaney's theorem, P=NP.

Where am I going wrong here?  I suspect that I am misunderstanding/misapplying Shaefer's theorem but I don't see why.


texts: Check whether an interval is contained in a union of intervals

texts:
Initial Problem:

  Given an interval $[A, B]$ and a set of intervals $S = \{[S_{11},
S_{12}], [S_{21}, S_{22}], [S_{31}, S_{32}], \ldots, [S_{N1}, S_{N2}]\}$
  with $S_{11}\leq S_{21}\leq \cdots \leq S_{N1}$ output True if and only if
  $[A, B]$ is completely contained in the union of all intervals in $S$,
  and False otherwise.

What is the best-time-complexity algorithm we can do this? Surely, there is a way to do this in $O(N)$ naively but is there any technique we could use to, say, lower the complexity down to $O(\log N)$ or anything better than $O(N)$?


texts:
It is NP-hard to approximate maximum 3D matching problem even if each element occurs exactly in two triples. I'm interested in the following decision version of 3D matching.

Informally, Given a set of triples $F$ of elements such that each element occurs exactly in two triples, Is there a subset of $F$ such that each element occurs in exactly one triple?

  Is this decision problem solvable in polynomial time? Is it $NP$-complete?


texts: Saving time finding a result by guessing first?

texts:
I am currently taking a graduate course about Image Processing in electrical engineering and while this question doesn't particularly relate to the class itself but rather some concepts in the algorithms we utilize.

One of the algorithms that we utilized was called, "Image Correlation" in order to find a "match" from using a segment of the picture and almost convolving it into the main picture. Below is an example of how this algorithm is implemented to find the correlation in the picture.

From Digital Image Processing by Rafael C. Gonzalez and Richard E. Woods...

My question is, instead of starting from the top left, why can't we estimate where the result is first before implementing the algorithm? Wouldn't it save time to know where you would like to start the process?


texts:
How exaclty do you determine this specific codes runtime is theta(n^2)??I can see theres two while loops which go from i and j to n but would like a more precise way of determing this? If someone could explain is simple terms as I am very new to this I would appreciate it.

def f(n):

i = 0

  while i < n:

   j = 0

     while j < n:

      j = j + 1

 i = i + 5


texts: Show that for every language there exists a harder language

texts:
I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that:
$$
A \leq_T B
$$
but:
$$
B \not \leq_T A
$$
If it is $A \leq_TB$ and $B \leq_T A$, this is easy since we can just let $B := \bar{A}$, but for the above I could not think of anything. Any help ?


texts:
I am writing an hashing algorithm to be used in key-value data store. That is for each key the location of the data is determined. The structure of the data store is given a key, a value needs to be retrieved OR given a key and value we determine a location to store the value. We want the keys to be designed/modified such that whole storage space is uniformly used. In my application, if there too many collisions, we would be forced to evict certain data items. The input is a key and output of the mechanism sought is a "better key" that reduces the collision.
I assume that key would not have more than 64 bits. For uniform distribution in the data store I want key bits to be shuffled appropriately so that all the data do not collide in the same slot of data store.
The approach I am thinking is to have a predefined padding table, from where we take rest of the bits and shuffle whole thing to produce a new key. For Example, for a smaller key value which can be accommodated in a byte, we pad rest of seven bytes (for 8 byte word). In case of 2 byte long key, we have another pad of 6 bytes and so on. I am not sure if this is an efficient way to do the job, but exploring should worth it.
If this is a good way, want to understand from you, how can I create such a table? What bits should be filled in it etc. Will be glad if there any pointers.
The idea of padding bits is to create uniform distribution. For Example, if the key is a very small number 0xab (say) then the padding bits could be 0x12345cdeadbeef00 such that we could OR the two things to form 0x12345cdeadbeefab. Now we shuffle the whole thing such that the resultant key is uniformly distributed in the storage space.


texts: Why is $L=\{\langle M \rangle \mid |L(M)| \geq k\}$ not recognizable?

texts:
Here $M$ denotes a turing machine.

By set theory, $L = \overline{E_{TM}} \cap \overline{L_0} \cap \overline{L_1}$ where $L_i=\{\langle M \rangle \mid |L(M)|=i\}$. And I know that $\overline{E_{TM}}$ is recognizable.

That is about all I know at this point. I suppose I need to use mapping reducibility to prove $L$ is not recognizable, but am not sure how.


texts: Why isn't P and P/poly trivially the same?

texts: The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf). Now, why can't a polynomial-sized circuit be simulated in polynomial time?


texts: Linear equation solving with special sparse coefficient matrix

texts:
Given a linear equation system of $n$ equations with unknowns $a_1,a_2,...,a_n\in [0,1]$, where the left hand side of each equation consists of not more than $k$ variables (so there are at least $n-k$ zero terms in each matrix row), what is the fastest way (in terms of time complexity) to solve such a system.

I know that simple equation-by-equation reduction will result in $\mathcal{O}(n^2)$ if I'm not mistaken. But is there a faster way of solving it (ideally linear in $n$, e.g. $\mathcal{O}(kn)$)? Because I'm new to the subject of computational linear algebra I have no idea wether or not this is possible.

EDIT: I should also say that either the coefficients in an equation are all the same and add up to zero (so they basically describe an arithmetic mean, for example $\frac{1}{2}a_1+\frac{1}{2}a_2-a_3=0$) OR the equation consists of a single variable and a value (e.g. $a_5=1$).


texts:
I am working on a HMM tagger that should be initialized with some small data and then supposedly improved with Baum-Welch algorithm on the data.

However, the number of states is huge, almost $459^2$, so the training would take ages.
For evaluation I already implemented Viterbi algorithm in which I prune and consider only the best $n$ options at that time for generating the next states.

Is something similar possible in Baum-Welch?
I would like to do the forward pass pruned like in Viterbi, backwards only if forward probability $\alpha>0$.

Then we should estimate the new transition probability like

$$a_{ij} = \frac{\sum_t \alpha(i,t)p(j|i)p(o_{t+1}|j)\beta(j,t+1)}{\sum_t \alpha(i,t)\sum_t \beta(i,t)}$$

But since we do the pruning, some $a_{ij}$ would not be computed. What about those? Should we just not change them, zero them or do we have to normalize the distributions then?


texts: How to solve for the precondition give a postcondtion that must satisfy two conditions

texts:
I tried solving past exam question but there is this one that I haven't been able to solve.

The question states that a suitable precondition should be found for the statement.

$$
 a= i +2; i++\{(a = 7)\land(i = 5)\}
$$
Here's my solution and where I got stuck:

$$
wp(a= i +2; i++,(a = 7 \land i = 5) \\
=wp(a= i +2, wp(i=i+1,a = 7\land i = 5)
$$

I've tried solving it intuitively and I arrive at the conclusion that no such value for ii should exist.

I haven't been able to find a rule to combine the two predicates of the post-condition.

Please I would like to know when solving similar questions can I change the ^ to an algebra symbol or should I take the relevant condition and find the weakest precondition with that.


texts:
I am getting ready for my end of year exams and I got stuck on this question.

Consider the following 3-process concurrent program which uses semaphores S1,

Process 1
L1:
 P(S3);
 print("N");
 V(S2);
goto L1;

Process 2
L2:
 P(S1)
 printf("O");
 V(S3);
goto L2;

Process 3
L3:
 P(S2);
 print("C");
 V(S1);
gotoL3;

Are there initial values that can be given to the semaphores so that the processes cooperate to print the string CONCONCONCO? If so, give the initial values (identify which value is to be used for which semaphore) and explain how the string is printed.

I really don't understand the question, thank you for your help.


texts:
Let us start with the optimization question,

\begin{eqnarray*}
min \{ c \vert c - f \in SOS_d \}
\end{eqnarray*}

for some function $f : \{0,1\}^n \rightarrow \mathbb{R}$ and $SOS_d $ being the cone of all polynomials on $\mathbb{R}^n$ which can be written as a sum of squares of polynomials each of degree at most $\frac{d}{2}$. This can be cast as a SDP by doing the "gram matrix" rewriting of any polynomial in $SOS_d$.

Now how do we show that the above is dual with no duality gap to this following optimization question?

\begin{eqnarray*}
&max_D \{ \tilde{\mathbb{E}}_D [f] \} \\
&s.t \\
&D : \{ 0,1\} ^n \rightarrow \mathbb{R} \\
&\sum_{x \in \{0,1\}^n} D(x) = 1 \\
& \forall u \in SOS_d \\
&\tilde{\mathbb{E}}_D [u] \geq 0
\end{eqnarray*}

where for any function $g : \{0,1\}^n \rightarrow \mathbb{R}$ we have $\tilde{\mathbb{E}}_D [g] := \sum_{x \in \{0,1\}^n} D(x)g(x)$

I tried writing a conic duality for the first to get it to look like an optimization over Lasserre maps but that approach didn't work...


texts: Confused in calculating the shortest-path using Dijkstra's Algorithm

texts:
I am required to find the shortest path using Dijkstra's Algorithm. After performing the calculations, am I getting the following values correct?:

A=0
B=13
C=8
D=20
E=14
F=25
G=31
H=38
I=46
J=52


texts:
In constraint satisfaction problems, heuristics can be used to improve the performance of a bactracking solver. Three commonly given heuristics for simple backtracking solvers are:

Minimum-remaining-values (how many values are still valid for this variable)
Degree heuristic (how many other variables are affected by this variable)
Least-constraining-value (what value will leave the most other values for other variables)

The first two are pretty obvious and simple to implement. First choose the variable that has the least values left in its domain, and if there are ties, choose the one that affects the most other variables. This way if a parent step in the solver picked a bad assignment, you are likely to find out sooner and thereby save time if you choose the variable with the least values left that affects the most other things.

Those are simple, clearly defined, and easy to implement.

Least-constraining-value is not clearly defined, anywhere I looked. Artificial Intelligence: A Modern Approach (Russel & Norvig) just says:

  It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.

Searching for "least-constraining-value" only turned up a lot of university slide shows based on this textbook, with no further information on how this would be done algorithmically.

The only example given for this heuristic is a case where one choice of value eliminates all choices for a neighboring variable, and the other does not. The problem with this example is that it this is a trivial case, which would be eliminated immediately when the potential assignment is checked for consistency with the problem's constraints. So in all the examples I could find, the least-constraining-value heuristic didn't actually benefit the solver performance in any way, except for a small negative effect from adding a redundant check.

The only other thing I can think of would be to test the possible assignments of the neighboring variables for each assignment, and count the number of possible assignments of the neighbors that exist for each possible assignment of this variable, then order the values for this variable based on the number of neighbor assignments available if that value is chosen. However, I don't see how this would offer an improvement over a random order, since this requires both testing numerous variable combinations and sorting based on the results from counting.

Can anyone give a more useful description of least-constraining-value, and explain how that version of least-constraining-value would actually yield an improvement?


texts: Fewest traversals to visit all vertices of DAG

texts:
I want to find the fewest traversals to visit all vertices of a DAG.  To take a very simple case:

Boston -> New York   -> San Francisco or Las Vegas, both to -> LA
       -> Pittsburgh -> San Francisco or Las Vegas, both to -> LA

There are lots of ways to traverse this graph, but to visit every vertex, you only need:

1. Boston -> New York   -> San Francisco -> LA
2. Boston -> Pittsburgh -> Las Vegas     -> LA

I have no preferences in how the graph is visited, and it's fine to visit the same vertex multiple times during different traversals.

(Real application: I am generating test cases for human testers and want them to help them perform their tests at every 'vertex' with as few run-throughs as possible.)


texts: How to divide services and capacities in a graph?

texts: Given a graph where some nodes can provide some services with x,y,z... capacities. A node connected to multiple nodes needs to divide these services to the connected nodes and these nodes themselves should further divide this to their connected nodes. when a node receives two services from 2 differnt nodes it is connected to it merges them and then devide them to the other nodes it is connected to. The goal is to make this division as optimal as possible while maximizing the services each node has access to. How can I do this any hints? Or is this possibly similar to some famous problem? Also what happens if at each point I do not know the topology of the whole graph?


texts: Is there a limit on the length of queries for the oracle?

texts: Consider the class $L^A$ which contains all the languages that are decided by a deterministic Turing Machine that uses $O(log(n))$ space and that can make queries to an oracle that decides $A$. My question is what is the length of query that the machine can ask the oracle? Is it $O(log(n))$ or can it be polynomial in $n$ (where $n$ is the length of the input)?


texts: How might one compute $4^{-1} \mod 17$ I know the answer is 13. I'm just not sure how to arrive at that number, and can't find any good explanations. Any help would be great


texts: How to calculate the runtime of a following code?

texts:
Could someone explain how to calculate the Big O notation for a runtime of a snippet of a code?
for (int i=0; i<list.length; i++) {
    for (int j=0; j<list.length; j++) {
        for (int k=0; k<list.length; k++) {
            if (k%2==0) {
               list[i] += list[j];
            } else {
               list[i] += list[k];
            }
       }
   }
}

From my understanding, I'm thinking it's something like O(n^3) because the statement is executive n times for every i?


texts: Schedule Optimization With Priority and Weighted Costs

texts:
I need an algorithm to determine the best itinerary for a series of events.
Each event has a time, location, and reward. Arriving at an event in time yields the reward; too late means no reward. Each event is at a physical location thus it takes time to travel from event to event. It is not necessary to attend every event.
What itinerary will yield the largest total reward?
Does anyone know if there is an existing algorithm for this or one that would be easily adapted? Given the similarity to the traveling salesman problem I am tempted to start with a weighted TSP solution and work from there.


texts: Complexity of $n \times \log n$ tiling problem

texts:
Is there a polynomial time algorithm for an $n \times \log n$ tiling problem?

For instance: Suppose $A$ is a finite alphabet. A tile is a $2 \times 2$ matrix of elements from $A$. A tiling is a matrix of tiles in which any adjacent symbols (including diagonally) in neighboring tiles are equal.

The Tiling Problem is as follows. Given a set of tiles $T$ and a sequence $C_1$ of $\log n$ tiles from $T$, is there an $n \times \log n$ tiling of $T$ whose first row is $C_1$?


texts: How can Interpreter run JIT Compiled Code

texts:
I do not understand how a program such as an interpreter can run and create code "on the fly" to run. Can someone help me understand what such a program would have to do in order to function?

I'm familiar with the process that a compiler takes the input file, creates the AST, produces the machine code, then the result is an .exe, .elf, etc. file to be run. The OS loader then takes the .exe (or .elf) file and loads that code into a memory chunk and starts execution. I understand that that process can fork and create a copy of it's process space, or create a new thread with system calls to the OS. I just don't understand how a program can run code itself. Does it just get extra space in its address space to write new code to? Does the typical CPU segmentation model even allow write access to the code segment? Is there a built in way to tell the OS Loader that the program will create and run new code on it's own?


texts:
Why is that the page size equals the size of one cache way?

My book states "A direct-mapped cache cannot be bigger than a page".


texts: If there is any research on Goal Based Programming (GBP)?

texts:
The more I think about programming and optimization, the more I think "why not just specify a goal and have the program figure out the optimal solution to it".

I am familiar with basic "optimization problems" such as finding the best fit line to a curve, or gradient descent sorts of things. What I'm talking about is way more complicated than that.

What I'm imagining is to say something like "An HTTPS server exists", and for the system to figure out how to build one. Obviously given just that info, it's not enough. It would require human-level training in programming and understanding concepts and everything.

But my question is, what could you do to build a system to support such a "goal statement"? What would the key parts be?

It seems at first, the simplest goal is "Action x is performed". This is required to change the current world into the desired (goal) world. For example, "Add" is performed on 1 and 2 is a goal stating that the "add" function is applied to the two arguments. It seems that from this foundation, you can build up higher and higher levels of abstraction to the point where you could then say "An HTTPS server exists". But this HTTPS server is a structure, not an action. So you need some way to have some intermediate goals that transcribe goals into (not actions, but) structures. Perhaps, The result of x operation exists is a simple transformation between the two.

But then I'm stuck haha. What do the goals look like in the intermediate realm? Has anyone done any research into this area? Searching doesn't yield much, though it brings up a book Goal programming and extensions which I might have to purchase.


texts:
Could anyone help me please to find who was the first person who has proved that the language of all borderless words is not regular and when was that? Could you mention the reference, please?

A word $w$ has a border $u$ if $u$ is both prefix and suffix of $w$ (and $u$ does not equal $\lambda$ or $w$).


texts:
Given $n$ drugs such that each drug $d_i$ should maintain in interval
$[c_i,h_i]$.We want to minimize number of containers to maintain
medicines in compatible interval.

My answer is as follows:
I use following greedy algorithm:
in each iteration, for remaining drugs, find an interval that have maximum number of compatible drugs, and remove that drugs, and add to container.
any one can help to find an counter example or proving above idea?


texts: Turing machine - Transition between two states by more than one condition allowed?

texts:
Is it allowed to transit between two states $q$, $q'$ by more than one condition? Thank you in advance.

e.g. coming from state $q$, the conditions $(0,0,L)$ and $(1,0,L)$ would lead to the same state $q'$. Is this formally allowed?


texts: Non Turing-Recognizable from symmetric difference

texts: I have a question about how you would find a example of a non Turing-recognizable language from the symmetric difference of two Turing-recognizable languages. I believe this is possible, but I am having problems coming up with a example in my head. Does anyone have any hints, or ideas about how to think about this?


texts: How to define and quantify computational work across different machines and encodings

texts:
Say I have the following intsruction represented in a number of languages:

| Language                   |                    Instruction                           |
|----------------------------+----------------------------------------------------------|
| English                    |                                          add six to five |
| Python                     |                                                      6+5 |
| Assembly                   |                                                 ADD(6,5) |
| MachineX,BinaryEncoding1   | 01111100000001111111100010101010101010101010101010101011 |
| MachineX,BinaryEncoding2   |       01111100000001111111100111111111111010101010101011 |
| MachineY,TernaryEncoding2  |                                 021021212121200202120202 |
| MachineZ,100004aryEncoding |                                                        p |

How might I compare the amount of computational work done by each machine? Perhaps clock operations? What framework might I use to better articulate what I mean by "computational work"?

What if the number of possible inputs implied by the original instruction was variable as well, say:

  Send message "hello dad" from virtual commodore 64 to virtual commodore VIC20 via virtual SMS


texts: Deciding whether there exists a permutation of the entries of an $n \times n$ matrix that is magic

texts:
Given an array of $n^2$ integers, what is the most efficient way to determine whether any permutation of those integers can form a magic square? "Magic square" being an arrangement of those integers on a square grid such that all rows, columns and diagonals sum to the same value.

Note that this isn't asking how to test if a given arrangement is a magic square, which would be $O(n^2)$, but whether any possible square formed from the array is magic.


texts: Finding corresponding node in a duplicate binary-tree

texts:
Given two duplicate binary trees (see the embedded picture), you are given a node in Tree A, find the same corresponding node in Tree B.

I believe the optimal approach should be traversing both trees at the same time, and when you reached the node in Tree A, you would know you have also reached the same node in Tree B.

Code example to solve this issue would be appreciated.


texts: Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum

texts:
I have found an algorithm that runs quite fast on Subset Sum problem few years ago (sometime around 2016). It basically sorts the input set in descending order (instead of the regular ascending) and does the backtracking then to arrive at results. It solves a 1,000,000 instance set in 5 minutes on my i5 8 GB RAM machine!

This year I stumbled upon this github repo:
GitHub Link for Subset Sum
by another user, who claims to have solved it in amortized O(n) complexity as per his detailed analysis available on the repo. Does this prove P=NP as well, as maybe amortized O(n) implies polynomial complexity for the problem?

P.S. that I have come across many fast Subset Sum problems but I am just curious in this specific case as it relates to my algorithm too.


texts: How to prove closure property of regular languages using regular expressions?

texts: I know that we can prove closure of two regular languages under operations like union, intersection, concatenation etc. by constructing NFAs for them but how to do the same thing using regular expressions, specifically proving that reversal of a regular language is closed using regular expression?


texts: How is Memory Segmentation done in 8086?

texts: Basically what I know is that 8086 can address up to 1 MB of locations which are divided in 4 segments(code, data, extra and stack) 64 KB each. But 64 KB * 4 is 256 KB, which doesn't add up to 1 MB(1024 KB). So what about the rest of space.


texts: What would be be a nice design pattern to code a function that implements a math function but doesn't know which parts of the equation get passed?

texts:
Take for example the Pythagorean theorem: a^2 + b^2 = c^2. This example is a little simple so please conside a function with 7 variables that are related. I would like to design the function in a way to fill in either 2 of the variables and resulting the entire set of variables derrived from the first 2.
I now have a function in that works like this: (pseudo code)
function pyth(object input) {
// known holds the known vars
var known = filter(input);

 (!(known.length === 2)) {
 // error not enough input
}

// calcute the other variable(s)
}

However is there a more elegant way? My problem is that there would be a lot of if's needed to determine which variables are known in combination.
For refference I have a real world implementation


texts: Finding a series of numbers that maximise $\ \sum f_i(x_i) $

texts:
Let $\ f_1, f_2, ... f_m : \{0, ..., m \} \rightarrow \mathbb Z $
my task is to find an algorithm that find a series of numbers $\ x_1, x_2, ..., x_m \in \{ 0, ..., m \} $ that maximise $\ \sum_{i=1}^m f_i(x_i) $ and subjects to $\ \sum_i^m x_i \le m $
To be honest I can't really wrap my head around this problem. Any suggestions on ways to look at this problem differently?


texts: Polynomial-time algorithm to solve the maximum vertex bipartite subgraph problem

texts:
I'm trying to find an algorithm that solves the maximum vertex biclique problem. I know that that algorithm can be solved in polynomial time (in contrast with the maximum edge biclique problem, which is NP-hard), and it's related somehow to transform the problem to a network flow problem, but I'm having a hard time finding it because most of the results from google are about NP-hard problems with similar wordings like maximum edge biclique problem, maximum vertex coverage and such.
Could anyone provide a link, explanation or even a pseudocode algorithm about how to solve the maximum vertex biclique problem in polynomial time?


texts: Interview question (constant-time algorithm, ILP)

texts:
A juice machine has three buttons small, medium large. Each size adds an amount of juice in a range to the cup. Eg small might add from 10-20 mL, medium from 30-35 mL, large from 40-50 mL. The exact numbers are relatively small (0-1000), integral, and known ahead of time

Input: cup size (mL), amount to fill (mL)

Output: whether or not a sequence of button presses can be constructed that is guaranteed to fill the cup with at least amount_to_fill mL while not overflowing the cup. A different sequence of button presses cannot be performed depending on how much the previous button presses ended up filling the cup, ie the sequence must be fully determined before any of the buttons are pressed.

This trivially reduces to the integer linear programming problem:

Given a,b,c,d,e,f,G (all integers, G very large, the rest relatively small)

maximize: ax+by+cz s.t. dx+ey+fz < G and x,y,z are integers

for which, the maximum can apparently be found in constant time. Denote this maximum M(a,b,c,d,e,f,G). What is the closed-form solution to M?


texts: approximation of max independent set and min vertex cover

texts:
There exists a very close and well-known relation between a vertex cover and an independent set
in a graph $G(V,E)$ ([1]): if $S$ is an independent set of $G$, then the set $V$ \ $S$ is a vertex cover of $G$. The same complementarity relation holds obviously for a maximum independent set $S$ and the set $C = V$ \ $S$ that is a minimum vertex cover of $G$.

MY question is: Both max independent set (MIS) and min vertex cover (MVC) are NP-hard and they have complementarity relation. Why MIS cannot be approximated to a constant factor in polynomial time (unless P = NP) [2], while MVC is approximable within approximation ratio 2?

Thank you!

Reference:

[1]C. Berge. Graphs and hypergraphs. North Holland, Amsterdam, 1973.
[2]https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Approximation_algorithms


texts:
I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost).

For the sake of my question, denote $n=|E|$.

Are there algorithms that will run in $O(n^2)$, or even $O(n\log(n))$, or for that matter anything less than $O(n^3)$? In my case, $n$ is ~100,000, so $O(n^3)$ is impractical for me.

'Extra' questions (should these go under a separate question?):

Do any of these supper multi-graphs (I have 2 edges from my super-source node to each of the "blue" nodes in my bipartite graph, and 2 edges from each of the "red" nodes to my super-sink node)?
Are there efficient implementations of such algorithms (that run in less than $O(n^3)$, and support multi-graphs) in C++, C, or Python?
If the answer is 'no', what are popular approximation algorithms and their associated run times?


texts:
I'm trying to construct a finite-state automaton from the following regular expression:

$$
(a|ba)(a|ba)^*(b|ab)^*
$$

I know that from
$$
(a|ba)
$$

the automaton should look something like this:

automaton http://cdn.imghack.se/images/5ab1437745d2a53d4630619819074d6c.jpg

from
$$
(a|ba)^*
$$

it should look like this I guess:

automaton2 http://cdn.imghack.se/images/e1dc6ac63c6d967086d1f40aebf62c51.jpg

and from
$$
(b|ab)^*
$$

is pretty much the same as the last one, the thing is I don't know how to unite them in one automaton.

I would appreciate any help in this matter

PS: I'm sorry for the images I'm still learning how to work with the automata editor jflap...


texts: When reading about approximation algorithms, I often find the terms "matching lower bounds". As I understand, these means to provide examples where the approximation algorithm matches the proved bound___proving that the algorithm achieves the best possible approximation ratio. Often, the approximation algorithm solves a minimization problem. What if the approximation algorithm solves a maximization problem? Are they called "matching upper bounds"?


texts: Accurate way to compute the sum of exponentials

texts:
In my work, I had to essentially compute the following quantity.

Given a sequence of positive floating point numbers $\{a_i\}_{i=1}^n$, such that

$$6000 \leq a_i \leq 7000$$

I needed to compute the following quantity (for some $n>1$, but for now can assume $n=1000$):

$$\log_2\left(\frac{\sum_{i=1}^n 2^{a_i}}{n}\right)$$

Direct computation is infeasible as the exponents are too large. So I rewrote the above expression as
$$a_1 + \log\left(\frac{1+\sum_{i=2}^n 2^{a_i-a_1}}{n}\right)$$

This also seemed a bit daunting but was better than what I had. My question was, is there a better way/algorithm to compute the above quantity? I appreciate any help on this.

The following observation might help:

$$\frac{\sum_{i=1}^n a_i}{n}\leq \log_2\left(\frac{\sum_{i=1}^n 2^{a_i}}{n}\right)\leq \max_{1 \leq i \leq n} a_i$$


texts: Signed and Unsigned Loads in a 32-bit Registers

texts:
I have a question over this quote directly out of Computer Organization and Design, 5e:

Signed versus unsigned applies to loads as well as to arithmetic. The function of a signed load is to copy the sign repeatedly to fill the rest of the register—called sign extension—but its purpose is to place a correct representation of the number within that register. Unsigned loads simply fill with 0s to the left of the data, since the number represented by the bit pattern is unsigned.
When loading a 32-bit word into a 32-bit register, the point is moot; signed and unsigned loads are identical.

(Chapter 2.4, pg 76; Patterson and Hennessy). [emphasis mine]
I do not immediately grasp why signed values do not matter for a full 32-bit word in a 32-bit register. The authors do not go on to clarify exactly why this is. My best guess from the materials of the book is because registers are to be sign agnostic with regard to the data within them and how they are interpreted is up to the assembly code? This would make sense if it weren't for the lack of a signed lw operation for MIPS, the language chosen for the text.
Thank you for any clarification on this.


texts: What is the easiest solution to check if a rational number is in the Cantor set?

texts:
To check that a rational number is in the Cantor set, I have written an algorithm to obtain its base-3 representation. To verify if the representation is periodic, I used a hash table in order to save memory.

Is there any easier solution to check that a rational number is in the Cantor set?


texts: Computing MOD_4 function using MOD_2, OR, AND, NOT gates

texts:
Define the $\newcommand{\MOD}{\text{MOD}}\MOD_q$ function from $\{0,1\}^n \rightarrow \{0,1\}$ as follows:

Let $x_1,\cdots,x_n$ be the input.  Then $\MOD_q(x_1,\cdots,x_n)=0$ if the number of 1's in $x_1,\dots,x_n$ is divisible by $q$; $\MOD_q(x_1,\cdots,x_n)=1$ otherwise.

I want to compute $\MOD_4$ using a constant depth circuit using only the following gates: $\MOD_2$ gates and the usual AND, OR, NOT gates.  Gate fan-in is unbounded.  Technically I want to show that $\MOD_4 \in \text{ACC}_0[2]$, where $\text{ACC}_0[2]$ means alternating circuit of constant depth with parity gates ($\MOD_2$ counters). Or more generally, I want to show that $\MOD_{p^k} \in \text{ACC}_0[p]$.

Can this be done?  Is there a way to compute $\MOD_4$ using $\MOD_2$, AND, OR, and NOT gates?

My attempt: If I pass the input through a $\MOD_2$ gate, then if it outputs 1 (i.e., odd) then $\MOD_4$ is also $= 1$. But $\MOD_2$ will output $0$ for the integers of the form $4k+2$ whereas $\MOD_4$ should be $1$ for those cases. I tried using OR, AND gates also but failed. I guess it will use some number theoretic property.


texts: QuickSort of linked lists optimised for duplicates

texts:
This is an past year question for a school exam that I do not suggested solutions for.

Problem Description

Quick Sort is not stable because of need to swap values in array when partition is done. If we store the values to be sorted in a linked list, we can make quick sort stable. Also, we can easily improve the performance of Quick Sort by grouping all the values that are equal to the pivot to the middle so they do not need to be considered during the subsequent partitions. Consider the following code.

function ListNode quickSort(ListNode head)
    partition(params1)
    ListNode front = quickSort(params2)
    ListNode middle = params3
    ListNode back = quickSort(params4)
    return combine(front,middle,back)

Task

Identify what should be params1,params2,params3,params4

Use pseudocode to describe the partition method. Make sure that special cases such as when there is a null in parameter is taken care of. Also, the new version of QuickSort is in-place.

I think that quickSort should return the head node of the list, but then middle seems strangely placed in the code as I would think of putting it after after partition. Also, I do not know the pseudocode standards for linked list and whether it is similar to the case of the normal one done with arrays. Can anyone help me with this?


texts: Shortest path from source to destination in directed acyclic graph

texts:
There is an approach given in this article Shortest Path in Directed Acyclic Graph to find the shortest path in O(V+E) using topological sort.

I have another approach which I think is more efficient. If use dynamic programming to store the minimum distance from a vertex to a destination than I don't need to explore that node again. Now, time complexity of this solution would be O(V+E) if I am using top to bottom approach (bottom to top approach would be O(V^2).

The advantage of this method is I don't have to find topological order first to find the minimum distance, I can find it directly.

The only disadvantage I can see of this method is, If the depth of my recursion tree is large, then I can run out of stack space and I have to use bottom to top approach. Now, if I have a sparse graph (E=O(V)), time complexity using this method would be O(V^2) but using topological sort method would be O(V) and I can use kahn's algorithm to find topological sort which is done iteratively so running out of stack space wouldn't be an issue.

Is there anything wrong in whatever I have written above?


texts:
I tried to figure out the proof of insertion operation in AVL-tree is O(log n), but I do not know how.
I also tried to find it somewhere on the Internet, but I could not find any good results. Do you guys have any ideas how do we proof that?


texts: What is the time complexity (upper bound) for this simple recursive function?

texts:
So I have function that I have written to return the maximum value between index i and index x of a given array using recursion as follows:

FindMax( A, i, j )
    if (i == j):
        return A[i]
    else:
        k = (i + j) / 2
    return max( FindMax(A, i, k), FindMax(A, k+1, j) )

What is the correct way to go about calculating the big O asymptotic time complexity of this algorithm? I would appreciate if someone could document a general way to calculate the correct complexity even if it is a different recursive function. I have spent a lot of time watching videos and reading up on the web but sadly I come up with different complexities after each.


texts: Algorithms for procedural generated mazes

texts:
For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important).

There are many Maze generation algorithms, but they only work on a finite grid.

What if instead you are working on an infinite grid? But you only need to know finite of the grid at a time (the application I have in mind is a character wandering around in a grid). What are some algorithms I could use?

In particular, it would be best if the algorithm wasn't biased by which parts of the maze you choose to evaluate first.

One algorithm I thought of was a modification of randomized Kruskal's algorithm. Basically, to calculate a part of the grid, you add the walls to the list, and then eliminate walls until the part of the grid you want to reveal, along with the parts of the maze already revealed, are all in the same set. This might have bias though depending on which parts you evaluate first.


texts: Difference between stable marriage problem and assignment problem

texts:
What is the difference between the stable marriage problem and an assignment problem? Both refer to a matching problem in general but what is their specific difference?
I can see clear differences in the implementation but do not see any related to the motivation. Both aim at assigning a man to a female -  both approaches take into account preferences.


texts: Average Time Complexity of Two Nested Loops

texts:
Recently I have had this question in one of my interviews.

You have 1 Million sorted integer, you have a value of $x$, compare each pair in this array and if the addition of two pair is less or equal to $x$ then increment the paircounter.

I have implemented this solution in C++ however I will write pseudocode here(I am sorry I am not very good at pseudo-code)

Initialise ARR_SIZE to 1000000

Initialise index_i to 0

Initialise pairCount to 0

Initialise x to 54321

while index_i is less than ARR_SIZE

  Initialise index_j to index_i+1

    while index_j is less than ARR_SIZE

      if array[index_i]+array[index_j] is less or equal to x

        Increment pairCount

      increment index_j

    endof while

    increment index_x

endof while

At first I said it is $O(n \log n)$ but then with the hint the second loop itself average complexity is O(n/2) so overall I said it would be $O(n\cdot n/2)$ but in Big $O$ notation it would be $O(n)$ because $n/2$ is a constant(although I was not too sure). So what is the average complexity of this overall algorithm?

PS: I know that I could have decreased the complexity by adding an extra else, index_j = ARR_SIZE, which would be $O(N)$ complexity, but I couldn't think of it during the interview.


texts: How can I efficiently find out if X is in any of N ranges of L-R numbers?

texts:
This is part of a bigger problem, which is to find out if point XYZ exists in any of n (XYZ -> XYZ) "boxes".

I'm currently splitting up the problem into a smaller one, by focusing on one dimension first and "filtering" till either a range is found, or it's not;

How can I find out if my number X is in any of n ranges with only a "beginning" and an "end" number? (preferably quicker than $O(n)$; iterating over all ranges till one suitable is found)

PS: I've already found some suggestions like "interval trees" and "segment trees", but I couldn't quickly find out if that was what I needed or not.

The reason why I post this anyway while there are other questions that help with my specific idea for a solution is because I also want to know if this is the most efficient way for my original problem; find if X is in any of n boxes.

If is helps, I expect all of those "boxes" to only have differing numeric values around one 2D plane, the end result is needed to "fence off" an A* neighbor search to specific "paths" it can navigate on.


texts: how to write a language for context-free grammar generates the empty string?

texts: How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ø}?


texts: How to prove the structured program theorem?

texts:
Wikipedia:

The structured program theorem [...] states that [...] any algorithm
can be expressed using only three control structures. They are

Executing one subprogram, and then another subprogram (sequence)
Executing one of two subprograms according to the value of a boolean expression (selection)
Executing a subprogram until a boolean expression is true (iteration)

This theorem is developed in the following papers:

C. Böhm, "On a family of Turing machines and the related programming language", ICC Bull., 3, 185–194, July 1964.
C. Böhm, G. Jacopini, "Flow diagrams, Turing Machines and Languages with only Two Formation Rules", Comm. of the ACM, 9(5): 366–371,1966.

Unfortunately, the first one is practically unavailable, and the second one, in addition to being a bit cryptic (at least for me), refers to the first, so I have problems to understand the proof. Can anyone help me? Is there a modern paper or book which presents the proof? Thanks.

UPDATE
To be exact, I would like to understand the second part of the CACM paper (section 3). The authors write in section 1 the following:

In the second part of the paper (by C. Böhm), some results of a
previous paper are reported [8] and the results of the first part of
this paper are then used to prove that every Turing machine is
reducible into, or in a determined sense is equivalent to, a program
written in a language which admits as formation rules only composition
and iteration.

Here [8] refers to the unavailable ICC Bulletin paper. It is easy to see that the above quote from Wikipedia refers to this second part of the CACM paper (the Turing machine serves as a precise definition of algorithms; "composition" means sequence; an iteration can replace a selection).


texts: Is it computable if a particular number follows the Collatz conjecture?

texts:
I was attempting to write a computer algorithm to determine if a particular number breaks the Collatz conjecture.  It is very easy to determine if a particular number falls into a loop, however I cannot think of any way to determine if a particular number is on an infinite divergent trajectory.

Is it Computable to determine whether or not a particular number is on an infinite trajectory?


texts: Nearest neighbour based on subjective human comparison - is this a thing?

texts:
I am looking for some clues as to the type of algorithm/data structure or general field of CS to look into...

I have a collection of items that I would like to have a human subjectively compare such that I can derive some consistent dataset that can be queried for k nearest neighbours for a given item that is present in the data.

i.e. if I ask a human, given item A, which item is most similar, B or C (repeated over a set of such items)

I can later present back, when queried, here are the items most similar to A.

The desire is simply to record a person's subjective comparisons of a set of items and have a means to allow them to query it.

Any pointers as to algorithms or structures to read up on would be greatly appreciated.


texts:
I read that system being in safe state doesn't guarantee that deadlock is not possible.

Can someone give me an example where system is in safe state and deadlock is possible?


texts: Given an abstract argumentation framework, is there a tool that can compute: conflict free, admissible and all extensions?

texts:
I am trying to find an online/offline tool that can compute the following:
Given an abstract argumentation framework <S, R>, where S = {a1, a2, a3, a4, a5} and the attack relation
R = {(a1, a2),(a2, a1),(a2, a3),(a3, a4),(a4, a5),(a5, a3)}. What are the:

Conflict free subsets (In this case: {}, {a1}, {a2}, {a3}, {a4}, {a5}, {a1, a3}, {a1, a4}, {a1, a5}, {a2, a4}, {a2, a5})
Admissible subsets (In this case: {}, {a1}, {a2}, {a2, a4})
Complete extensions (In this case: {}, {a1}, {a2, a4})
Grounded extensions (In this case: {})
Preferred extensions (In this case: {a1}, {a2, a4})
Stable extensions (In this case: {a2, a4})

As long as the S is 6 or less, it is reasonable to compute this on paper. But as soon as we get something like an S of size 10, we suddenly need to start computing 2^10=1024 different subsets. So I was wondering, is there some online/offline tool/platform/program that can compute this. As my S can be no larger than 10, efficiency is not a big issue here.


texts: A clarification on the taxonomy of Evolutionary Algorithms

texts:
A rather basic question but I am confused about the characterization of a certain local search method which I want to describe in the framework of EAs. In particular, consider an EA which in every step of the evolution has a neighborhood of size 2; one element in the neighborhood is the current hypothesis (hypothesis in the traditional sense of learning theory) and the other element in the neighborhood is another hypothesis that has arisen from the current hypothesis after applying some transformation/mutation.

It is clear that for such algorithms in the neighborhood we can find at most 1 hypothesis that has strictly better fitness compared to our current hypothesis (our current hypothesis is neutral compared to our current hypothesis). Thus, my question is, how would one characterize an algorithm of this form that always picks among the beneficial set if the set is non-empty, otherwise it would pick among the neutral set (at random - or with some prescribed probability distribution)? Note that the neutral set is always non-empty as the current hypothesis is always there. So, can this algorithm be described as a $(1+1)$-EA or should it be described as a $(1, 1)$-EA? Is there a difference between a $(1+1)$-EA and a $(1, 1)$-EA?

And since we are here, if anyone would be able to clarify the following I would be indebted. What is the difference between a $(1+k)$-EA and a $(1, k)$-EA for $k > 1$. As far as I have understood the comma description (i.e. $(1, k)$-EA) refers to the fact that the algorithm picks the most fit hypothesis among the $k+1$ elements in the neighborhood. The understanding that I have for $(1+k)$-EAs is that they pick at random (however that will be defined) among the hypotheses that have strictly larger fitness values compared to the current hypothesis. Is this understanding correct?

Thank you for your time in advance.


texts: $\lambda x. \lambda x.x$ vs $\lambda y. \lambda x.x$

texts:
Several times, I saw $\lambda$-terms such as $\lambda x. \lambda x.x$, where $x$ is bound by the inner lambda, which I agree.

why not just write it as $\lambda y. \lambda x.x$, so it is clear and you don't need to comment such as "where $x$ is bound by the inner lambda".

what is the point of writing  $\lambda x. \lambda x.x$, why not just write it as $\lambda y. \lambda x.x$? Usually, we don't write long lambda terms, so we have enough names to name bound variables distinctly.
why not just state that "all bound variables should be given distinct names" to avoid such vague terms and explanations?
is there a particular reason for having  $\lambda x. \lambda x.x$?

I believe it is because of the syntax of lambda terms.
I also believe banning such terms is reasonable.


texts: Proving a pattern exist in a string without revealing where

texts:
Some time ago i read the following problem (i don't remember the article from which i read it from) :

"Suppose you are given a picture where the goal is to find waldo (from the game where is waldo), you search for a bit and don't find him so you become suspicious of the fact that waldo actually is in the picture, how can one prove to you that waldo indeed is without revealing where ? Well one can just take a very big sheet of paper, bore a hole inside it and place this sheet of paper on top of your picture so that waldo's head appears inside the hole."

My question is how could one transfer this idea to a mathematical concept ? One idea would be something along the lines of :

Let L be some language in complexity class C
given $a_1 , a_2 , ... a_n$ can one prove to you that there is a $i$ for which $a_i \in L$ without revealing for which $i$ it stands

However this falls short as it stands right now because one can just feed the same input $a$ n times for which it wishes to know appartenance to class L. So we either need to consider specific complexity class C for which the problem becomes interesting or loosen the condition of "non disclosure", and it doesn't seem that obvious. Or we could just change paradigm, my question is just how to convert the waldo idea to a computationnal model, i suspect the approach i gave isn't the right one.

Edit : I thought about it some more and the interesting question indeed seems to be finding languages for which this is possible, for instance let L bet the set of numbers divisible by 7. Given $a_1 , a_2, ...a_n$ n integers. Let p be their product then I can prove to someone easily that p is indeed their product and that p is divisible by 7 (iif one of the $a_i$ is). But by doing so I don't reveal which one.

There are two shortcomings with this however. The first one not too big is that divisibility by 7 is easy, but one could imagine harder languages. The second one is that it is not true that we don't reveal which $a_i$ is divisible by 7. If in the input we're given we have a rule of thumb to rule out all but one $a_i$ from being divisible by 7, then we know immediately which one is by knowing the whole product is divisible by 7. (Again just think of divisibility by 7 as a placeholder for "complex problem")


texts:
So here is the problem: There are n objects in a super market that you need to retrieve, then you need to go to the cashier register in the end. How do you find the best path of traversing the least distance to retrieve the objects and finally go to the cashier register?

I could only find a brute force method of finding optimal path of each permutation of paths and seeing which overall distance covers the least traversing. But this implementation is O(n!). Is there a more efficient approach?


texts:
I'm giving an array $A[0..n-1]$ and an integer $w$.  The goal is to find indices $i,j$ that maximize

$$\Phi(i,j) = A[i] + A[i+1] + \dots + A[j-1],$$

subject to the requirements that $0 \le i \le j \le n$ and $j \le i+w$.  Or, in other words, I want to find the sequential window of width at most $w$ such that the sum of the numbers in the window is maximized.

Is there an $O(n)$ time algorithm for this task?  Or, what is the most efficient algorithm for this task?

There is a trivial $O(nw)$ time algorithm, but I can't see how to do better than that.  If $w=\infty$, Kadane's algorithm solves this in $O(n)$ time, but I can't see how to generalize it to my problem.  So, can we do better than $O(nw)$ time?

I encountered this problem in the context of an image processing task I'm facing.


texts: What is the difference between a 'page' of memory and a 'frame' of memory?

texts:
WP has an adequate discussion of paging, which I think I understand.. However I am confused by the articles repeated use of the term Page Frame.

I thought frames and pages were different things.  Could someone please clarify the difference.


texts:
Does $a^n b^m$ with $n, m \ge 0$ and $m \ne n$ fail the pumping lemma?

I know it is not regular and that this can be demonstrated by using closure properties, but does the language pass the pumping lemma?

It seems to me that for any p I can pump either a or b (depending on which has a greater repetition count) without making n = m. But in an exam I am taking the answer key says it does not satisfy the pumping lemma.


texts:
I have 2 histograms that represent the height of characters in 2 images.
example:

1 **
2 ****
3 ****
.
.
.
100 ******

For these 2 histograms I compute the peaks. And To check if these 2 images are similar I compute the interseciton between the indices of the 2 images.
Example:
For image 1 the indices of the peaks are 1, 10 and 13
for image 2 the indices of the peals are 1,10, 14.
Image1 Inter Image1 = 2 So these images are similar.

But I feel that the intersection is not enough. I think that i should also use the size of the buckets of the histograms peaks.

Is there  a way to use to both of them to measure the similarity in 1 function So that I can have a stable similarity function?


texts: Having a problem understanding the execution of I/O in Von Neumann model

texts:
I might have gone too deep in my search after the answer which might be much easier than what I figured.

Essentially I wanted to figure out how I/O are executed in a Von Neumann machine, but more I read, the more confused I became.

What they are saying in "Introduction to computing systems" (Patt and Patel) and other websites covering this is that I/O devices in the VN machine has an I/O controller which works as a liaison between the I/O device(s) and the CPU which will interrupt the CPU once the I/O operation is finished.
(1. it receives the write/read request, 2. notifies the cpu and let it go back to doing whatever task it was doing, 3. interrupts it once the I/O operation is finished).

So this is some kind of Interrupt-driven I/O, but is that enough to explain how I/O are executed in VN machine?
How does a program communicate with an I/O device?
How will you explain the data transfer between memory and I/O devices?


texts: How to Define an Efficient, Optimal or Suboptimal Parallel Algorithm?

texts:
I am going through the book of Parallel Programming and a parallel algorithm is often classified as Efficient, Optimal or Suboptimal. I googled these terms but I didn't found a clear definition for them.

Define $T(n)$ as the running time of the sequential algorithm, $t(n)$ as the running time of the parallel one, $p(n)$ as the number of processing units. Hence work $w(n)=p(n)t(n)$, speedup factor $S(p)=\frac{T(n)}{t(n)}$, efficiency $E=\frac{T(n)}{p(n)t(n)}\times 100\%$.

The parallel algorithm is efficient if:

$t(n)=O(\log^c n)$ for some constant $c>0$; and
work $w(n)=T(n)O(\log^c n)$

The parallel algorithm is optimal if:

$t(n)=O(\log^c n)$ for some constant $c>0$; and
work $w(n)=O(T(n))$

Are the definitions of efficient and optimal correct? And what about suboptimal?

I am literally a noob to parallel programming and I googled a lot without a clue. Any help would be greatly appreciated. Thanks in advance.


texts: Inputting a superposition into a cNOT gate

texts:
I am unsure how to calculate what happens when you put a superposition as the control qubit into a cNOT gate or what happens when  you put a superposition as the target qubit into a cNOT gate. I know what matrix represents the cNOT and I know that each superposition would be represented by $\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle$, but would you take these two four dimensional vectors and multiply them both by the cNOT matrix? If so, in what order? I just don't quite understand.

Any help would be appreciated. Thanks!


texts: Why does $L = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belong to $\mathrm{P}$?

texts: My professor said that the non-regular language $L_{1} = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belongs to $\mathrm{P}$. I do understand that all regular languages belong to $\mathrm{P}$ as it's easy to determine and so can be computed in $\mathcal{O}(n^k)$, but why do most non-regular languages not belong to $\mathrm{P}$ but $L_{1}$ does? Is it also possible to give an example of a language $L$ that does not belong to $\mathrm{P}$?


texts: Switching Lemma and AC0 reductions between SAT problems

texts:
Have there been efforts to show (using the Switching Lemma), for example, that SAT or 3SAT cannot have an AC$^0$ reduction to 2SAT?  What are the issues or difficulties involved?

SAT and 3SAT are complete for NP, and 2SAT is complete for NL under AC$^0$ reductions.  Hence such a proof would separate NP from NL.

In the case of a 3SAT to 2SAT reduction in AC$^0$, the bottom fan-in is bounded by 3 (at least prior to the first switching).


texts:
How are computers able to tell the correct time and date every time?

Whenever I close the computer (shut it down) all connections and processes inside stop.  How is it that when I open the computer again it tells the exact correct time? Does the computer not shut down completely when I shut it down? Are there some processes still running in it? But then how does my laptop tell the correct time when I take out the battery (and thus forcibly stop all processes) and start it again after a few days?


texts: algorithm performance with insufficient input, part 2

texts:
In a previous post, I have asked:

Generally speaking, an algorithm takes some inputs and provides some output. I would like to understand how the algorithm performs when the inputs are incomplete for various real-world reasons. Are there any papers on this issue?

As a specific example, suppose

*the seller wants to sell M items
*there are N buyers each has values for the first item, second item, etc
*but buyers may not report the values for low-valued items (let us say the lowest m items) but the seller does not know the details
*the seller wants to sell M items to the buyers who have the highest values

In this situation what algorithm (other than brute-force) will have some guarantee ?


texts: Fastest possible way to check what of X is in a string

texts:
I am trying to speed up one of my application, one of the places where I can speed up is in my test if a string contains an array of strings.

example: I have the matches "dog", "cat" "apple" and the string "The dog chases the cat".

In this example would I like an algorithm that returns "dog" and "cat".
I do not care, how many times, or where in the string it is, I just want to know what of my matches exists.

The fastest algorithm i can think of for this is $\mathcal{O}(nm)$ where $n$ is the length of the string, and $m$ is the count of matches.

But my question is are there an algorithm out there, there can do this faster then $\mathcal{O}(nm)$?


texts: Is a language recursive? 2 wrong ways of solving

texts:
Let's define:
$Disagree(M_1,M_2) = \{x| $The result of $M_1$ on  $x$ different from the result of $M_2$ on  $x\}$
that means: if $M_1$ accept, $M_2$ reject and vice versa
$NPA=\{L|\exists M_1,M_2$ Nondeterministic polynomial TM $ s.t. Disagree(M_1,M_2)=L\}$
Is $NPA=R$?
I thought about this problem from 2 clashing ways:

If I choose $M_1$ to accept any input and $M_2$ to reject any input, for given $L$ each $x\in L$ will be $x\in Disagree(M_1,M_2)$ so $NPA=R$
To accept $L$, $M_1$ and $M_2$ should run on every $x\in L$ and even if it's a single step the input ($L$) is a countably infinite set, so it's impossible to run on all the $x\in L$, so $NPA\neq R$

When I saw the answer, I understood that both of my ways wrong, but I can't understand in which step?


texts: Can Dijkstra's algorithm outperform A star, in terms of vertices checked?

texts:
I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more vertices than Dijkstra's algorithm. What I'm asking however is the following. Given an A star algorithm with some heuristic which is not the heuristic returning 0, could it possibly check more vertices than Dijkstra's algorithm?

My intuition is yes, and I will show why. Consider the Figure underneath, in which we consider a large amount of discrete points in this plane, representing the vertices of the graph, and connecting arcs with cost 1 between all adjacent points, creating a grid graph. Suppose the heuristic used by A star is euclidean distance, and suppose many curved walls like the ones I drew in the middle exist in this fashion, not only the three I drew. A star in this situation would be "tricked" to go in between the walls, since the heuristic would guide it close to the point, only to find out it's a dead end (or a local optimum of some sorts if you will), and this would happen as many times as there are walls. Dijkstra would not be tricked this way. The only problem with my example here, is that Dijkstra will probably not outperform A star here. So, is my intuition wrong, or do more clever instances than this one exist in which Dijkstra can in fact outperform A star in terms of vertices checked?


texts: Assistance with Notation in the Paper Entitled: "Search Through Systematic Set Enumeration"

texts:
So I'm reading "Search Through Systematic Set Enumeration" by Ron Rymon (currently available online for free.  I'm having a problem with the notation in the following definition presented bellow:

The
Set-Enumeration
(SE)-tree
is
a
vehicle for representing
and/or
enumerating sets
in
a best-first fashion.
The
complete
SE-tree
systematically enumerates
elements
of
a
power-set using a
pre-imposed
order
on
the
underlying set
of
elements.
In
problems
where
the
search
space
is
a
subset
of
that
power-set
that
is
(or
can
be)
closed
under
set-inclusion,
the
SE-tree
induces
a
complete
irredundant
search technique.
Let
E
be
the
underlying
set
of
elements.
We
first index
E's
elements
using
a
one-to-one
function
ind: E -> $ \mathbb{N} $.
Then,
given
any
subset
S $\subseteq$ E,
we
define
its
SE-tree
view:
Definition 2.1 A Node's View
$View(ind,S) \stackrel{def}{=} \{e \in E | ind(e) \gt max_{e' \in S} ind(e')\}$

In the paper there is an example of a tree made with what appears to be E={1,2,3,4}.  I have some familiarity with set-builder notation, but much of the other parts of the "node's view" is confusing me. I skimmed ahead to see if there were clarifications, but I didn't manage to find them so either: a) the author is assuming a competency I do not have, b) the explanation is there and I couldn't find it, or c) the author is doing a horrible job as an author.
So with the hope that it is one of the first two:

I'm assuming that the prime in e' is for the complement of the set e, so if e = {1}, then e' = {2,3,4}.  Is this correct?

What is this ind function?  What would ind({3,4}) be for example?

$max_{e' \in S}$?  Is this the maximum height of the sub tree of the complement of e?
Any assistance on this would be most appreciated.


texts: Does 2-edge-colourability imply 2-colourability?

texts:
Why is it that if the edges of an undirected graph G can be grouped into two sets such that every vertex is incident to at most 1 edge from each set, then the graph is 2-colorable.

The reason that I am guessing this happens is because the graph is bipartite. But I was not sure about this... I was trying to show it was bipartite and then show thus that it was two colorable, but I didn't really know how to start showing it was bipartite. Somebody know of a rigorous way to show this? Or what the intuition for the proof is?


texts: Find the point with minimum max distance to any point in a set

texts: Say I have a set of points on a 2d plane, how do I find the point(s) where the maximum euclidian distance to any of the points in the set is minimized?