texts: How to convert 010111 to decimal using only odd numbered positions while still applying the correct positional exponent?

texts:
I am trying to understand what this question is asking in terms of conversion. I know how to convert binary to decimal and vice versa, but the method you need to use has me confused.

I need to convert 010111 to decimal using only odd numbered positions while still applying the correct positional exponent in the conversion. What I did was take every odd numbered position from base 2 digit from 010111 so "111" I skipped every other number and took the digit from that position (if that makes sense) I only had three digits so I added a 0 to make it 4 bit 0111 which equals 7 in decimal. I know this is wrong but why??

This is the question: - Imagine that a processor is faulty and reads only odd-numbered positions when converting binary numbers to decimals, but it applies the correct positional exponent in the conversion. In radix 10, the binary number 010111 converted by this processor would be:

The mock test answer says the result is 2 but I cannot figure out why


texts: Lower bound for comparison algorithm - checking whether permutation is odd or even

texts:
I consider problem:  proving lower bound for comparison algorithm that check whether permutation is odd or even.
I know that this bound is $\Omega(n\lg n)$.

Could you give me a clue ?


texts: Prove that this language is not context-free

texts:
I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L=\{0^{2^n}∣n \geq 0\}$ is not context-free.

There is no pattern of 0's that can be recreated by a pushdown automata but alas I need to prove this. I know you start off assuming it is by being able to create a substring $uvxyz$ where $v$ and $y$ are raised to the $i$th power where $i≥0$. I'm having trouble from there, any help in this and the understanding would be greatly appreciated.


texts: Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?

texts:
http://www.algorithmist.com/index.php/UVa_10918

The above link is a solution to UVa 10918 Problem. The problem is based on Dynamic Programming. I am not able to understand this approach to the problem. I have coded the solution but the approach is completely different. I want to understand the given approach. The problem is:

Determine in how many ways can a 3xN rectangle be completely tiled with 2x1 dominoes.

I only want to know how these recurrence relations came:

f(n)=f(n-2)+2*g(n-1)
g(n)=f(n-1)+g(n-2)

where f(n)=number of tilings of a 3xN rectangle
g(n)= number of tilings of a 3xN rectangle with one of its corner squares removed


texts: How can follow this this guide to construct a graph with matrix/reachability

texts:
Let's we have k matrices. For example we have 3 now,  where first one is 8x5  ($a_1$ x $b_1$), second one is 5 x 6 ($a_2$ x $b_2$) and last one is 6 x 8 ($a_3$ x $b_3$). And our goal is to figure out if possible to multiply within any given matrices and reach a matrix of dimension x and y, when x and y is given ahead of time. In this example, (8x5) x (5x6) x (6x8), end up a 8x8 matrix.   The hints is given, but I cannot visualize. Any more help is appreciated. can understand the first step, but have not idea about the second one.

First, we can define nodes in the graph as the values of each $a_i$
and each $b_i$, and put an edge from $a_i$ to $b_i$.
Second, Whenever there is a chain of matrices $M_{i1},...M_{ik}$, we
can multiply, then x=$a_{i1}$ has an edge to $b_{i1} =a_{i2}$, and
$a_{i2}$ has an edge to $b_{i2}$ =$a_{i3}$, and so on, up until
$b_{ik}$ =y. So there could be a path from x to y in this
graph.
Third, Inversely, for any path from x to y, the edges form a chain of
matrices that we can multiply, which create a x x y matrix.
therefore, x is reachable from y in the graph iff there is a
chain of matrices which from the x x y matrix.

The first step create something like this ?
>  x-->
> n8-->n5
> n5-->n6
> n6-->n8
>   -->y

What is $M_{i1}$, $a_{i1}$ and $b_{i1}$? How does that differ to $a_{1}$ ?


texts: Hungarian method: seemingly different algorithms from different sources?

texts:
When I look online for examples of the Hungarian method for solving the min-weight assignment problem, for example here, it involves iterating on the cost matrix; subtracting entries from the rows and columns.
However, in section 17.2 of the book, Combinatorial optimization polyhedra and efficiency by Schrijver, a seemingly different algorithm is presented. Here, we start with a matching $M$, assign $W_M$ and $U_M$ as the edges on the left and right of the bi-partite graph that haven't been covered by the matching, describe path lengths as $l_e=w_e$ if the edge is in $M$ and $l_e=-w_e$ otherwise and find a min path from $U_M$ to $W_M$. Then, reset $M$ to $M'$, the symmetric difference between the path $P$ and $M$.
These two algorithms seem very different to me. Are they somehow the same under the cover?


texts: Upper bound on the number of edges relative to the height of a DFS tree

texts: Let $T$ be a depth-first search tree of a connected undirected graph $G$ and $h$ be the height of $T$. How do you show that $G$ has no more than $h \times |V|$ edges where $|V|$ is the number of vertices in $G$?


texts: The significance of bounded parameters in complexity

texts:
A lot of complexity results are given with respect to bounded cases where results are more favourable.

For example, the graph isomorphism problem — which is GI-complete in general — is known to be tractable in cases where degree is bounded.

But every time I see such a result, I have a nagging voice in my head telling me that for any input graph the degree must be bounded. I find it hard to intuitively resolve the resulting cognitive dissonance.

I understand that bounding a parameter allows for considering it as a constant rather than a variable in the complexity analysis. But that seems almost like a semantic game since you can still define the bound to be arbitrarily large so long as it's fixed.

Perhaps the message to be gleaned from these bounded results is that if you assume the parameter in question to generally be small, the worst case is more favourable. But this seems rather vague to me since one can define "small" arbitrarily.

The nagging voice tells me I'm still missing something ... that something hasn't clicked.

To distil a question out of this: when one sees such a bounded-parameter result, what should one intuitively conclude about the problem in practice with respect to that parameter?

What is the importance of such a result?


texts: Is there a reversible transform that reduces the number of distinct values?

texts:
The idea is to take a sequence like $\langle 1,2,3,4 \rangle$ and reduce it to something like $\langle 1,2,2,3 \rangle$, or something similar. The key point is that there are fewer distinct values $\{1,2,3\}$ vs $\{1,2,3,4\}$. In the case that the number of distinct values cannot be reduced, i.e. $\langle 0,0,0,0 \rangle$, it would output the same value $\langle 0,0,0,0 \rangle$. An algorithm that doesn't always decrease the number of distinct values is ok, as long as it doesn't increase the number of distinct values, or as long as it does so only rarely. The output sequence length can be less than or equal to the input sequence length, and the input sequence is bounded by $[0,255]$, but the output sequence need not be, though they should be integers in the range $(-\infty,+\infty)$. Another restriction on the input, if it helps at all, is that it's a restricted growth string. A property of restricted growth strings that might be useful is that the first $0$ in the sequence always comes before the first $1$, the first $1$ before the first $2$, and so on. So a valid sequence might look something like $\langle 0,0,1,0,2,1,1,0,2 \rangle$.

As an example, consider this simple algorithm. First, construct a "dictionary" from the input sequence consisting of all distinct values in the input. So, for the input sequence $\langle 1,2,2,3 \rangle$, the dictionary would be $\langle 1,2,3 \rangle$. It then iterates over the input, doing two things: replacing the input value with its position in the dictionary, and rotating the dictionary left by one. For most inputs, this will do little to reduce the number of distinct values, but for the input sequence $\langle 1,2,3,4 \rangle$, it will output $\langle 0,0,0,0 \rangle$. This can be inverted by applying a similar algorithm. Starting with the same dictionary, iterate over the output, successively replacing the values in the output with the value in the dictionary at that output value's index (that is, if $D$ is our dictionary and $i$ is a value in our output sequence, replace that value with $D_i$) and then rotate the dictionary to the left by one.


texts: Is necessarily the following language not decideable

texts:
For A,B that are not decidable, does AB U BA not necessarily decidable?

I think that the answer is NO. Not necessarily.
I thought about the following example, but it does not refute exactly:

If we take A and A complement, and without losing generality the empty word is in A, than every word in A' is also in AA' U A'A, but I can't use it to show that every word in A is also in AA' U A'A.

If someone can help me how can I show that also A is in AA' U A'A the problem will be solved.

thank you very much.


texts: The language of any constant-time Turing machine is regular

texts:
Suppose we have a Turing machine $M$ so that there is a constant $t$ such that the Turing machine always runs in time $t$ or less. Prove that the language of $M$ is regular.

This seems to be a pretty well-known fact, but despite my research, I cannot seem to find a proof of this anywhere. Does someone know of one?


texts: Is the 0-1 Knapsack problem where value equals weight NP-complete?

texts:
I have a problem which I suspect is NP-complete. It is easy to prove that it is NP. My current train of thought revolves around using a reduction from knapsack but it would result in instances of 0-1-Knapsack with the value of every item being equal to its weight.

Is this still NP-complete? Or am I missing something?


texts: How to find the most unique vectors in a set?

texts:
A question bridging math and computer science, I have on the order of 10000 vectors each of a equal but high dimension, say 6 or 7 dimensions. I want to find a given number of 'unique' vectors in the set, the number generally equal to the dimension of the vectors. In math terms I believe I want to find a subset of vectors that has the biggest angle from its neighbours in that sub set. Vector length is also a factor, i.e. a unique but nearly zero length vector is less preferred than one less unique in angle but has a finite length.

An example:

1: [1 2 4 1 5]

2: [1 1 2 1 3]

3: [1 2 4 1 4]

...

9999: [2 1 1 2 2]

10000: [4 5 4 2 1]

vectors 1 and 3 are quite similar, 2 less so, 10000 is most different. I think the dot product and higher order 'angle' is the best measure of uniqueness, though there may be better.

Visually, collapsing the dimension down to 2, the vectors below in black represent the full set, the vectors in red are the subset of seven most unique.

Concept update: 03/05/2018

I have recently stumbled upon the concept of the Latin hypercube, and the higher dimensional mathematics behind it that attempt to find an even spread of higher-dimensional vectors. I don't know exactly how this could be applied, but it has been the closest concept so far. Can anyone see how it might be applicable to the problem?


texts: Algorithm to convert rendered number back into symbolic form

texts:
If you have a number such as $3.14626437$ and you need to know what symbols create it, as far as I know, there are two tools:

1- ISC

2- wolframalpha

and the answer is $\sqrt2+\sqrt3$

I am wondering what algorithm these websites are using and how much is their complexity?


texts: I'm aware of a large amount of literature on the problem of graph layout. Usually this involves taking a list of nodes and edges, and choosing locations and paths for both respectively. Are there any algorithms that take graphs where the node locations are already known, and produce paths for the edges?


texts: A monotonically nondecreasing function $ f(n) $ s.t $ f \in O(n^2) $ and $ f \notin o(n^2) $ but also $ f \in \Omega(n) $ and $ f \notin \omega(n) $

texts:
I am trying to look for an example of a monotonically non-decreasing function $ f(n) $ such that:
$ f(n) \in O(n^2) $ and $ f(n) \notin o(n^2) $ but also $ f(n) \in \Omega(n) $ and $ f(n) \notin \omega(n) $. The domain could also be all real numbers.
I considered different variations of piecewise functions, for example I considered the function $$ f(n)=
\begin{cases}
 n^{2-\frac{1}{n}} &\text{if}\, n =2k+1\\
 n^{1+\frac{1}{n}}&\text{if}\, n=2k\\
\end{cases} $$
which satisfies the growth rate conditions, but is clearly not monotonically non-decreasing.
I would be happy to hear your ideas, thank you.


texts: What is the algo used for Phonetic Search

texts:
I am new to the field of text mining. Could not figure out what to search on google so am here for the same help.
When we talk of approximate / fuzzy string match. searching for RAT would give RAAT too. i have used utl_match.edit_distance in oracle. searching for BAAT would give BAT. but if i search for RAT. it would return BAT, CAT, etc. How does google bring the phonetically same rhyming / sounding words eg if some one does'nt know spelling of 'Schwaznegger', even then correct data is brought by google. For 'levenshtein distance', cat and bat are pretty close but for google. closest to cat is kat not bat. Please tell me what we call such a search and what algorithms are used for it.
 Thanking you in advance for patience.


texts: Connection betweem treewidth and feedback vertex set

texts:
I've learnt during graph algorithms studies that if a treewidth of a graph is greater than k+1 then there's no feedback vertex set of size k in this graph.
I would like to understand why...I mean, I understand that if it's enough to remove k vertices to make the grapy acyclic, so there must be a tree composition whose width is at most k,. but I cant fully understand the connection.
Can someone please elaborate it?
Thanks in advance


texts: How does supercompilers relate to macro tree transducers?

texts: Supercompilers can be used as a generalisation of deforestation of a functional program. Macro Tree Transducers composition can be used to the same effect, using a completely different approach. What is the relationship between those?


texts:
Given a deterministic DPA, is it possible to tell whether it halts on all possible inputs?  Is this problem decidable?

The standard halting problem is "Given a DPDA and an input $x$, determine whether it halts on input $x$", and that problem is decidable.  But what about the variant above?


texts:
I am new to this forum as I want to explore data structures and algorithms in depth.
I want to know from experts here what books or other resources would be best for someone like me who can be considered just above a beginner as far as data structures and algorithms is concerned.


texts: Circuit size for "at least n inputs are true"

texts:
Say you have $m$ boolean inputs, and you are given a threshold $n$. You need to construct a boolean circuit  that evaluates to true if at least $n$ of the inputs true. You may use AND, OR, NOT, or XOR gates (restricted to fan-in two, with arbitrary fan-out). Asymptotically how small can you make this circuit?

Any reasonably tight upper bound would be appreciated. I keep on thinking of ways to recursively construct such a circuit but I can't find anything good. Also, any results for any other reasonable basis of allowed gates would also be useful.


texts: How to reduce this regular expression into DFA

texts:
$(a(aa|b)^*ab|b)((ba|a)(aa|b)^*ab|bb)^*((ba|a)(aa|b)^*)^*|a(aa|b)^*$

I know long algorithmic procedures but since regex is large I tried a lot by substituting common patterns for some regex definition but didn't seem to help.

What can be done so that this regex can be converted to DFA easily.


texts: State complexity of converting epsilon-NFAs to NFAs without epsilon transitions

texts:
I am well-aware of the result showing that one can convert an epsilon-NFA (that is, an NFA with epsilon transitions) $A$ to an NFA without epsilon transitions $A'$, where $L(A) = L(A')$.

Is there a similar result comparing the state complexities of $A$ and $A'$? That is, if one has an epsilon-NFA $A$ with $n$ states, is it true that there exists an equivalent NFA without epsilon transitions $A'$ that also has $n$ states?


texts: Approximation algorithms for indefinite quadratic form maximization with linear constraints

texts:
Consider the following program:
\begin{align}
\max_x ~& x^TQx
\\ \mbox{s.t.} ~& Ax \geq b
\end{align}
where $Q$ is a symmetric (possibly indefinite) matrix and the inequality is element-wise and constrains feasible solutions to a convex polytope.

This is NP-hard to solve, but what are known approximation results?

A relevant result is given by (Kough 1979). It is shown that this program can be optimized using Benders' decomposition to within $\epsilon$ of the optimum. However, the paper does not seem to clearly specify what this means, or the complexity of the procedure.

I believe the $\epsilon$-approximation is in the usual sense employed in the field of mathematical programming, that is, if $OPT$ is the optimal value of the program, $ALG$ is the result of the above procedure and $MIN$ is the minimal value attainable by a feasible solution,
$$
\frac{ALG-MIN}{OPT-MIN} \geq (1-\epsilon).
$$
Or something of the sort.

Questions:

Is the mentioned procedure a polynomial-time algorithm?
Are there known polynomial-time algorithms yielding approximations to the above program in the traditional sense, i.e. $ALG \geq \alpha OPT $ for some $\alpha < 1$, constant or not.

  Update: I don't think it's possible to get an $\alpha OPT$ approximation for general quadratic programming for a very simple
  reason: in negative definite instances, the optimum is negative.

  Still, it would be interesting to know if approximations are possible
  when the quadratic form is nonegative in the feasible set. Also, it
  would be nice to know the complexity of the Bender's decomposition
  method.

-

  Kough, Paul F. "The indefinite quadratic programming problem."
  Operations Research 27.3 (1979): 516-533.


texts: Approximation scheme for finding best product of matrices that minimizes $||Ax - y||$ for given $x,y$

texts:
Given a set of $N$ $n \times n$ matrices $A_1,\ldots,A_N$, and two vectors $x,y$, the problem is to find a product of up to $K$ matrices $A = A_{j_1}A_{j_2}\cdots A_{j_k}$ so that $Ax$ is as close to $y$ as possible in terms of euclidean distance. The problem can be shown to be NP-hard e.g. by reduction from subset sum. However the problem seems so hard that I have a hard time believing there is even a polynomial time strong approximation algorithm. Also there is the issue of how to define the quality of the approximation. The problem is invariant under scaling $x$ and $y$ so probably we should assume $x$ has length $1$ and an approximation gets within distance $\epsilon ||y||$ of the optimal solution, where $y \neq 0$ and $\epsilon > 0$ can be chosen arbitrarily small.

Anyway like I said, I believe there is no polynomial time strong approximation algorithm but I'm having a hard time thinking of how a proof might go. If someone could help me resolve this question about whether a polynomial time strong approximation algorithm exists, that'd be great.


texts: Why base of log is insignificant while considering time complexity?

texts:
If so, then $O(log_2 n)$ = $O(log_{10} n)$ = $O(log_e n)$. It is very wired that computer scientist treat them equally.

Considering,

$(log_2 n)$ = $m$, meaning $n$ = $2^m$

$(log_{10} n)$ = $m$, meaning $n$ = ${10}^m$

$(log_e n)$ = $m$, meaning $n$ = $e^m$

So, does it mean that $O(2^m)$ = $O({10}^m)$ = $O(e^m)$

Is, base treated to have $O(1)$ time complexity, hence neglected?

NOTE: I want to understand in terms of computer science and not in terms of mathematics.

How does it explain the computer science part? Mathematician will explicitly mention $log_e$, but when we talk in terms of CS (time complexity) it doesn't matter, why? I have put a note also. Duplicated answer proved mathematical explanation.


texts: Why do Amdahl's law and Gustafson's law give us different speedups, when applied on the same task?

texts: I am given a task, where exactly 50% of the work is parallelizable. When applying Amdahl's law to calculate speedup when using 2 processing units instead of one, I get a different result than the one I get when calculating the same speedup using Gustafson's law. I don't understand why is that.


texts: A heuristic for finding an edge cycle cover

texts:
I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph.

In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-4, 1-3-4-5 and 1-2-3-4-5. The last cycle does not add any further information about the cyclic structure of my graph that's why I don not want to process it.

I made few searches and found out there is the Edge Cycle Cover and finding the minimum is NP-HARD problem. I'm not sure if it is exactly what I'm looking for.

So, any help understanding this problem? Is there a heuristic to get only a subset of cycles for each vertex in the graph? it does not have to be minimal!


texts:
So, there are multiple possible definitions of "np-complete", two of which being:

A decision problem $L$ is np-complete if and only if:  $L \in \text{NP}$  and  $\forall L' \in \text{NP}: L' \preceq_{p} L$
A decision problem $L$ is np-complete if and only if:  $L \in \text{NP}$  and  there exists a np-complete problem $L \in \text{NP}$ such that: $L' \preceq_{p} L$

My question is, why are those two definitions equivalent, or put differently, (why) is np-complete an equivalence class?

If it is an equivalence class I can understand equivalence of the above two definitions, but I fail to see why this is the case, since the (one-to-many) poly-time reduction $\preceq_{p}$ is not symmetric... :-/


texts: Prove function in little-oh of a big-theta function

texts:
I'm having trouble with this homework question.

Prove if $f(n)$ is $o( g(n) )$ and $g(n)$ is $\Theta( h(n) )$, then $f(n)$ is $o(h(n))$.

I know I need to use the precise definition of a limit, but I'm not sure how to apply it to this proof. Any help would be appreciated.


texts: Creating a Grammar that is equivalent to "RegEx A, RegEx B, or BOTH"

texts:
I have the following problem, create a Grammar on the Language {1,0} that accepts

  "strings with a length divisible by 3, or strings with a number of 0s divisible
  by 3, or BOTH".

I created grammars for each part, but I'm not sure how to account for the "BOTH" clause.

I started by making a regular expression:

1*(01*01*01*)+|((0|1)(0|1)(0|1))+

Then I made the following Grammars for each of the two main parts:

1*(01*01*01*)+

becomes

S_1 -> 1F | F
F   -> 1F | 0G
G   -> 1G | 0H
H   -> 1H | 0M
M   -> F | (empty)

and

((0|1)(0|1)(0|1))+

becomes

S_2 -> 0C | 1C
C   -> 0D | 1D
D   -> 0E | 1E
E   -> S | (empty)

My question is, if I just use the central or in the regular expression and start the complete Grammar by branching to one of the two Grammars I made with no cross over*, will it somehow potentially compromise the "or BOTH" requirement in some cases? Or is that extra requirement just a red herring and will be necessarily satisfied by covering both of the base requirements? As far as I can tell, both are more or less completely independent of one another.

*ie just tack the two together with this at the start:

S -> S_1 | S_2
...


texts: Reducing 3CNF to Clique: Why do we omit negated literals?

texts:
I have an example for a reduction of 3CNF to Clique, there is one thing I don't get about it, hopefully you could clarify it.  The reduction works like this:

  Construct a graph G = (V, E) as follows:

  Vertices: Each literal corresponds to a vertex.

  Edges: All vertices are connected with an edge except the vertices of
  the same clause and vertices with negated literals.

Why is it important that that negated literals will not be connected? How would that effect the reduction?


texts: I want to learn Artificial Intelligence techniques by writing a game (or maybe any fun project). Can you suggest any games? Consider that I'm a beginner in AI, but have basic knowledge Algorithms and Data structures (graph algorithms and stuff like that). I'm going to use Python.


texts: Is time complexity more important than space complexity?

texts:
I've noticed quite a few cryptographic algorithms speak mainly of the time complexity of an algorithm. For example, with a hashing function h, find x given y = h(x). We normally speak on how long it will take. Or the time to find the discrete log for a public key.

Edit:

While writing this question, I pondered that maybe because for most algorithms in cryptography (that I have seen) , have O(1) space time complexity. i.e. If the solution does not work, we throw it away and encrypt.

Clarification on this will be really helpful.


texts: Are these valid counterexamples to proofs for CF languages with Non-CF complements?

texts:
Someone asked for examples of context-free languages with non-context-free complements.

The first answer says:

  The language $L_1= \{ww \mid w \in \{a,b\}^*\}$ is not context-free (as can be shown using the pumping lemma; see here).  Its complement $L_2 = \{a,b\}^* \setminus L_1$ is context-free (as shown here).

Maybe in reality this is true, but given the above information, I am not convinced this is a valid example of such a language. I have proved before that $L$ is not CF, so I have no problem accepting that. However, the CFG and proof given for $L_2$ are wrong. I can give a really simple counterexample: when the string $s=aaabaa$. Clearly $s \in L_2$ because it's not of the form $ww$. However, $s$ cannot be constructed using the CFG described for $L_2$.

Proof: The string $s$ is not of the form $A$ or $B$ since the length of the string is even. Therefore it must be of the form $AB$ or $BA$, but this is impossible because both halves of the string have the same character ($a$) in the center. Therefore $s \notin L_2$, which is a contradiction.

The second answer says:

  The example you see on Wikipedia: put $A=\{a^n b^n c^m\}$, $B=\{a^m b^n c^n\}$. It's easy to see $\overline{A}$ and $\overline{B}$ are context-free by defining a PDA; you can note that they're deterministic context-free languages, which is a class closed under complement. Therefore $\overline{A} \cup \overline{B}$ is a context-free language with a non-contextfree complement $A \cap B=\{a^n b^n c^n\}$.

This one is even easier to disprove. Sure, deterministic context-free languages are closed under complement, but they're not closed under union. Therefore, the language $\overline{A} \cup \overline{B}$ is not necessarily context free.

I am currently still taking Theory of Computing, so perhaps I've gotten something wrong or overlooked some obvious truth. Can anyone disprove my claims? If not, can you provide a valid example of a CF language with a non-CF complement?


texts: How can the length of a string be $O(\log n)$?

texts:
I have just started learning about time complexities and am currently reading Logarithmic Complexity. Here's an example of a piece of code which is $O(\log n)$:

def intToStr(i):
    '''Assumes i is a nonnegative int Returns the string representation of i'''

    digits = '0123456789'
    if i == 0:
        return '0'
    result = ''
    while i > 0:
        result = digits[i % 10] + result
        i = i // 10
    return result

So this just gives is the str of an integer. intToStr(1243) returns '1243'. I completely understand that the above function is of logarithmic complexity.

In continuation,

def addDigits(n):

    '''Assumes n is a nonnegative int
    Returns the sum of the digits in n'''
    stringRep = intToStr(n)
    val = 0
    for c in stringRep:
        val += int(c)
    return val

My book says that: (emphasis added)

  The complexity of converting $n$ to a string is $O(\log n)$, and intToStr returns a string of length $O(\log n)$. The for loop will be executed $O(\operatorname{len}(\mathit{stringRep}))$ times, i.e., $O(\log n)$ times. Putting it all together, and assuming that a character representing a digit can be converted to an integer in constant time, the program will run in time proportional to $O(\log n) + O(\log n)$, which makes it $O(\log n)$.

Can someone please explain how intToStr returns a string of length $O(\log n)$? Doesn't it just return a string of length $n$, where $n$ is the length of the integer that we pass?


texts: Interview Questions for Minimum Cost of Tasks

texts:
I got this problem as an interview questions and I was blank all the way, I thought it was pressure but as I try to do it now I am still blank, anyway to solve this problem, I am blank so a solution would be more helpful than just explaining it as I am just trying to move on from this problem and do something else, more of like a review question that i can look at for the next interview prep. Thanks in advance.

Assume that you have a list of n home maintenance/repair tasks (numbered from 1 to n) that
must be done in list order on your house. You can either do each task i yourself at a positive cost
(that includes your time and effort) of c[i]. Alternatively, you could hire a handyman who will do the
next 4 tasks on your list for the fixed cost h (regardless of how much time and effort those 4 tasks
would cost you). You are to create a dynamic programming algorithm that finds a minimum cost way
of completing the tasks. The inputs to the problem are h and the array of costs c[1], . . . , c[n].

Here is an example. [1,3,5,6,7,2,1,3,1000] is the cost array by yourself. The handyman cost is 11. For any sequence greater than or equal to 4 tasks we would add handyman to do the tasks. In this case we would add handyman for 1...4, and 5....8, hence the total cost here is 23, and it is the minimum. Note that the handyman can not do less than 4 consecutive tasks.

Here are the subproblems I was given to solve:

find and justify a recurrence (with boundary conditions) giving the optimal cost for completing the tasks
O(n)-time recursive algorithm with memoization for calculating the value of the
recurrence and a bottom up algorithm


texts: Dominating set in bounded degeneracy and bounded degree graphs

texts:
I believe Minimum Dominating Set (MDS) is NP-hard for bounded
degeneracy and their subset bounded degree graphs, but
a paper appear to suggest tractability.
Enumeration of Minimal Dominating Sets and Variants p.5

  Proposition 1. Dom admits a polynomial delay algorithm when restricted to

Strongly chordal graphs.
Graph classes of bounded degeneracy.

The delay of the algorithm is the time between enumerating two MDSs
after polynomial preprocessing (unless I have misunderstood the
definitions on p. 3).
According to graphclasses.org MDS is linear for strongly chordal graphs.

Does the paper imply $\exp(o(n))$ complexity of MDS
for graphs of bounded degeneracy (and bounded degree)?


texts:
Consider $x$ = $(0.1001)_b$ and $F$[3,2]. ($F$[3,2] is the set of all floating point numbers with 3 digits in the mantissa and 2 digits in the exponent.)
The question is $x$ in the working range [3,2]?
I am quite confused does $F$[3,2] mean $(0.111)_b$ x $2^{11}$ = $(111)_b$?


texts: Linear time algorithm to sort points of a simple polygon

texts:
In triangulating a simple polygon, using the concept of sweep line helper vertices etc, the very first step is sorting the vertices of such polygon. Apparently this very step can be done in $O(n)$ (where $n$ is the number of vertices). I'm trying to work out why... Assume there's no degenerate case (for any pair of points belonging to the polygon their $y$ coordinates are different). Because of such property a strict order exists $y_1<y_2<\ldots<y_n$, assume each point is stored in floating point $y_i = (e_i,m_i)$, I can't really see how to sort these points in linear time... could anyone give me an hint?

Source :
Computational Geometry - Algorithm and application (DeBerg et all) chapter 3:

The claim is this

  We now analyze the running time of the algorithm. Constructing the
  priority queue $\mathcal{Q}$ takes linear time...

Any kind of priority involves order relationships, so I assume some kind of ordering algorithm is used. Eventually the priority queue can be implemented using binary trees or heaps (basically these are the same thing) but It would still require $O(n \log n)$. I know ordering algorithms that run in linear time, however I don't think any of those can be applied in case of floating point numbers.


texts: Trouble with Master Theorem concerning logarithm and square root

texts:
I have trouble understanding how to apply the master theorem in the following problem:

  $$T_2(1) = 1; T_2(n) = 4T_2(2^{\log \lfloor \frac{n}{2}\rfloor}) + \sqrt{n} \text{ for } n > 1.$$

My professor first rewrote this problem as

$$ T_2(n) = 4T_2(\lfloor \tfrac{n}{2} \rfloor) + \sqrt{n} \text{ for } n > 1, $$

which I don't quite understand. As far as I'm concerned you can only rewrite the log formula that way if the logarithm has a base of 2. So basically like that:

$$ a^{\log_a x} = x. $$

Also he declared $d$ as 2, even though if it's a square root, $d$ should be 1/2. Can someone clear me up how he got to the following solution? I'm really confused since I thought I understood the theorem fairly well. The final result should be $$ T_2(n) \in \Theta(n^2). $$

I finally understood my mistake: $d$ is indeed 1/2, and therefore smaller than $\log_b a$ (=2). The 3rd case of the master theorem therefore applies.


texts: What actually is the concept of transparency? Why not call it Abstraction?

texts:
I searched this over Google few times but ended up with articles on transparency rather than an answer.
With relation to distributed database study(or distributed OS), what is the concept of transparency?
I mean in replication, fragmentation and everywhere I guess the idea is to implement these concepts but not to bother user about them. Correct me if I'm wrong but I think the idea is "User shouldn't know?". Then HOW is this transparency? Isn't it abstraction? Hiding the implementation details?


texts: Analyzing a randomized algorithm for finding an approximate median of an array

texts:
I'm given an array $A$ = ($a_1, a_2, \cdots a_n$), where n is uneven. For an element $a_i$ we denote its position in the array with $p(a_i)$. This element would be an $ε$-approximate median of the array, if after we sort it, the following inequality holds:

$$\frac12 ((1 - ε) × n) < p(a_i) \leqslant \frac12 ((1 + ε) × n)$$
For example, the array $1,2,\cdots,9$ would have $4,5,6$ as $\dfrac13$-approximate medians.

My task is to analyze the following randomized algorithm, which finds an $ε$-approximate median of the array in constant time:

  Choose $2k + 1$ elements of the array $A$: $b_1, b_2, \cdots, b_{2k+1}$, where each element is chosen uniformly randomly and independently of all the others (it is possible for an element to repeat). Using the algorithm for finding a median of an array in linear time (QuickSelect) output the median of the array the elements $b_1, b_2, \cdots, b_{2k+1}$ form.

I'm also given the following two random variables:

$K$: number of elements in $b_1, b_2, \cdots, b_{2k+1}$, which are smaller or equal to the $\dfrac12 ((1-ε)×n)$-biggest element in the original array
$A$.

$G$: number of elements in $b_1, b_2, \cdots, b_{2k+1}$, which are bigger than the $\dfrac12 ((1+ε)×n)$-biggest element in the original array $A$.

What I have to do is find the best possible upper bounds for
$$P(K \geqslant (1 + ε) E(K))$$
and
$$P(G \geqslant (1 + ε) E(G)),$$
where $E(K)$ and $E(G)$ are the expected values for the random variables. I also have to find a bound for the probability the algorithm will be successful, which depends only on $k$, not on $n$, $E(K)$ or $E(G)$.

What I have done so far: I computed the expected values for the two random variables. I believe they are binomially distributed, so for example for $K$ I have $2k + 1$ events each with probability $\dfrac12(1-ε)$ to happen, so
$$E(K) = (2k + 1) × \dfrac12 (1 - ε).$$
$E(G)$ turns out to be the same. Then I tried computing the two upper bounds, mentioned above with the Markov, Chebyshev and Chernoff inequalities:

Markov:
$$P(K \geqslant (1 + ε) E(K)) \leqslant \frac1{1 + ε},$$
Chebyshev (might be false):
$$P(|K - E(K)| \geqslant εE(K)) \leqslant \frac{\operatorname{Var}(K)}{ε^2 × (E(K))^2} = \frac{1}{ε(2k + 1)},$$
Chernoff:
$$P(K \geqslant (1 + ε) E(K)) \leqslant \exp\left( -\frac13 ε^2 E(K) \right).$$
Are these correct? If they are, am I correct that Chebyshev is the best one? How do I continue with finding the probability of success of the algorithm?

Thank you :)


texts: Poly-time reductions for proving EXPTIME-hardness are _not_ enough?

texts:
Wikipedia says that in order to prove EXPTIME-hardness of our problem, we need to prove that every EXPTIME problem can be poly-time reduced to our problem. Here is a "counter-example" that bugs me.

Suppose our problem can be solved in time $O(2^k)$, where $k$ is an input number to our problem instance; let it be in binary. Consider some EXPTIME-complete problem that takes a number $n$ as input. Consider a hypothetical reduction that creates our problem instance with $k=2^n$; it is is poly-time, because it computes $2^n$ by shifting $n$ times the letter $1$ to the right. Our reduction implies that the original problem can be solved in $2^{2^n}$ time. But that is not sufficient for proving EXPTIME-hardness of our problem, because we cannot derive the contradiction by assuming our problem is solveable in poly-time. Therefore, we cannot use poly-time reductions.

Where is the mistake? Is it about binary/unary encoding of numbers? Is it about meaning of $O(2^k)$ vs. $O(2^{|\text{string representing k}|})$?


texts: Why does everyone say that NFA guesses it's next state?

texts:
In the picture above e is an empty string, and a is a symbol from an alphabet. Every book or professor I have heard from, says than when we make transitions in the NFA, the NFA must guess which state to go to next. In the example above, the NFA must guess whether it should go left or right.

Why do they use the word guess? I have written a simple regular expression engine once and used dfs to go both right then left, if the right path didn't lead to a final state.


texts: What is the intuition behind Strassen's Algorithm?

texts:
I came across Strassen's algorithm for matrix multiplication, which has time complexity $O(n^{2.81})$, significantly better than the naive $O(n^3)$. Of course, there have been several other improvements in matrix multiplication since Strassen, but my question is specific to this algorithm.
If you see the algorithm, you'll notice that 7 matrices $M_1$ to $M_7$ have been defined as intermediate computation steps, and the final matrix product can be expressed in terms of these. I understand how to verify this claim, and arrive at the expression for the desired time complexity, but I'm unable to grasp the intuition behind this algorithm, i.e. why are the matrices $M_1$ through $M_7$ defined the way they are?
Thank you!


texts: shortest string containing all binary palindrome of length n as substring

texts:
I am trying to compute the shortest binary string that contains all binary palindrome of length n as substring. For example, for n=3, 00010111 is such a shortest string. However, brutal force performs really bad even for n=6, n=7 etc. Is there any optimization like branch and bound I can do here. My current optimization is following:

Use common super sequence algorithm to get an upper bound of the target string
palindrome of all 0 and all 1 is contained there hence we can place the first n position as 0 and last n position as 1
a continuous block of more than n-2 "1"s or "0"s is clearly not in shortest target string, hence this kind of situation should be avoided.

However, the above optimization is not enough, the program cannot even terminate in reasonable time for n=7.

Hence I am asking if anyone can get some further optimization


texts:
A problem $X$ is $NP$-Hard if for all $Y \in NP$, $Y \leq_P  X$. Further, if a problem $Z$ is $NP$-Complete, and $Z \leq_P  X$, then I can prove (rather mechanically) that $X$ is $NP$-Hard.

I also found that, for a given X, say TSP, to prove it is $NP$-Hard, we often find a ($NP$-Complete) Z say $HAM-CYCLE$ (Hamiltonian-Cycle), and try to show that $HAM-CYCLE$ can be reduced to a $TSP$ in polynomial time.

My confusion is, why don't we try to show that for each instance of $TSP$, there exists a corresponding instance of $HAM-CYCLE$. Specifically, what if there exists an instance of $TSP$, for which there is no corresponding instance in $HAM-CYCLE$! In this case, how can the prior knowledge about the hardness of $HAM-CYCLE$ help in inferring on TSP's hardness!

Note: I also had similar concerns with proving $NP$-complete class. However, since all $NPC$ are also $NP$, I felt, similar reduction of a known NPC problem to a given problem, say Q, works. However, for $NP$-hard case, a given problem X need not to be $NP$ at all.


texts: Better way to formulate these constraints?

texts:
I have a binary variable $x_{ijt}^k$ that is $1$ iff job $i$ is assigned to machine $j$ at time $t$ using processor $k$. I would like to express the following constraints:

If job $i$ is assigned to machine $j$ at time $t$ using processor $k$ then job $i$ cannot be assigned to machine $j'\neq j$.
If job $i$ is assigned to machine $j$ at time $t$ using processor $k$ then job $i$ cannot be assigned to machine $j$ at time $t'\neq t$ using processor $k'\neq k$.

In other words, both constraints say that once job $i$ is assigned to a machine, it must be assigned using the same processor on that machine.

For the first constraint, I write it as $x_{ijt}^k+x_{ij't'}^{k'}\leq 1$, for all $i,j'\neq j, k, k',t,t'$.

For the second constraint, I write it as $x_{ijt}^k+x_{ijt'}^{k'}\leq 1$, for all $i,j, k\neq k',t\neq t'$.

Can I improve this formulation?


texts:
Let $G=(V,E)$ be an undirected graph,such that ever $e\in E$ has a color-blue or red.
Given $G$ and some $s,t\in V$ ,find an efficient algorithm that find from all pathes from $s$ to $t$,one with an even amount of red edges,and minimal amount of blue edges.

For the part of the even amount of red edges,I know that I can split the vertices,$v$ to $v_o,v_e$ for odd or even amount of red edges till I reached that vertex.
But I'm not sure,how to do the part with the blue edges?
I could give some weight to the blue edges (and red 0 weight) and use Dijkstra's algorithm,but there is a solution in $O(|E|+|V|)$.
Any ideas?


texts: Proof of $\mathsf{NP}^\mathsf{BPP} \subseteq \mathsf{BPP}^\mathsf{NP}$

texts:
How to show that $\mathbf{NP}^{BPP} \subseteq \mathbf{BPP}^{NP}$?

I tried to build $NTM$ $M_{NP1}$, which uses $PTM$ $M_{BPP1}$. Show that there will always be $PTM$ $M_{BPP2}$, which uses $L ($$NTM$ $M_{NP2}$$)$ as the oracle language and repeats the actions of $NTM$ $M_{NP1}$ with the oracle $L ($$PTM$ $M_{BPP1}$$)$. Unfortunately, I could not do this. It turns out that the $NTM$ output that uses $PTM$ will also happen with some probability?

Hope You can help me to show it.


texts: Upper bound on size of derivation in CFG

texts: Suppose $G$ is a $CFG$ with $m$ variables, in which the right-hand side of all production rules has length at most $\ell$. Show that if $A\Rightarrow^*_G\varepsilon$, then there is a derivation of no more than $\frac{\ell^m-1}{\ell-1}$ steps by which $A$ derives $\varepsilon$. How close to this bound can you actually come?


texts: What's the meaning of $\log^{O(1)}(a+b)$ ? Is it simply $(\log_2(a+b))^k$ where k is calculated in constant time ? That is the base 2 logarithm usually in computer science when no other base is set, and the $O(1)$ at the log word means that the whole expression should be raised to the power of that number (which I named k) ?


texts: Is it decidable if a TM takes at least 2016 steps on all inputs?

texts:
$$L_1= \{\langle M \rangle \mid \text{\(M\) takes at least 2016 steps on all inputs} \}$$

Is this language decidable?

I will write my way of understanding it. Please answer it in the way I understand & tell if my understanding is wrong.

It means L1 is a language, which includes all such Turing machines, which takes at least 2016 steps on all inputs. So we need to say it is decidable or not...

We are talking about which machine? We are talking about that machine whose language is L1. Other TMs are input to the new turing machine as encoding of 0 &1. We need to say for all inputs (for all Turing machine encodings) the new turing machine halts or not. When it will halt? When the new turing machine can either say..."Yes, the turing machine I am considering took at least 2016 steps but still it is on progress"...it also can say "No, the turing machine you gave me went to final state before 2016 steps" If it will say either of this, then the new turing machine, language L1 is decidable.

When it will be undecidable? When the new turing machine is still on progress unable to say yes or no. So solution is run new Turing machine for 2016 steps only. If it is saying "yes, the other turing machine halted...or the other turing machine did not halt."... then for both answer our new turing machine will halt... It is simple to understand that the new turing machine will always halt... bcz it's task is just to check the other turing machine halted or not within 2016 steps.


texts: Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free?

texts:
The usual candidates for context free languages whose complement is also context free, but they are not regular are the Deterministic Context Free Languages ($DCFL$).

For example, $L=\{a^nb^n\mid n\in\mathbb N\}$ is such language.

  Is there a language, $L\in CFL\setminus DCFL$ such that $\bar L\in
 CFL$?

Since $DCFL$ is closed under complement, this is equivalent of asking whether $$CFL\cap co\text{-}CFL = DCFL$$


texts: Are some real world compression algorithms sometimes producing unexpectedly large files?

texts:
Lossless compression is not magic. It just gives the common patterns a short notation, compensating by the less common patterns ending up with a longer notation. By that logic, all lossless compression algorithms must sometimes give you a larger file back. A real world example of that is for instance giving a file containing 'a' and a line feed to gzip (2 bytes), it subsequently returns a 30 byte file. In general, compression tools do not break even for very small files.

My question is: Are some compression utilities bloating out larger files by some significant amount? (While "Give this file to 7z and watch you harddrive fail!" is cool, things like "This 4kb file will grow to 6kb." are also good.)

I can see a reason why such behaviour might not exist. If you for instance always put an extra bit to the output telling if the file is actually compressed, or just the original file in the cases where the compression fails, your output can never be worse than the original file plus 1 bit. I am however not sure if any such protection against unexpected large files is used.


texts: Testing whether a set of integers can be written as a combination of module basis elements

texts:
Input

We are given a set of basis elements, $\ v_1$,$\ v_2$ ,...,$\ v_n$ of a $\mathbb Z^m$- module and a multiset of integers  $\ B :=$ {$\ b_1, ...,  b_m$}

Desired Output

Return true if there exists a linear combination $\ a_1v_1 + a_2v_2 + ... + a_nv_n$ such that the resulting vector uses the integers $\ b_1, ... , b_m $ the same number of times that each occurs in B. Return false otherwise.

Example

Let $\ v_1 = (1,0,0,1), v_2 = (1,0,1,0) $ and $\ B =$ {$\ 0,4,2,2$}. Here the algorithm should return true since we can write $\ (4,0,2,2)$ as $\ 2v_1 + 2v_2$.

As another example, consider the same vectors with the integers {1,2,3,4}. Here we want to return false since we will never be able to write four strictly positive numbers as a linear combination of the two vectors.

So my questions are: What kind of problem is this? Can anyone prove it NP-complete or find a reasonable algorithm for it?


texts: How do I mathematically express a set generated using two loop variables within a single for loop?

texts:
I don't know the proper mathematical expression for for-loops, especially those that carry two distinctly behaving variables with each iteration.

For example, assuming n is previously defined and holds some positive integer, how I would I represent the set printed by this for-loop in mathematical notation?

// prints a set of multiples (n previously defined)
for (int j=n, k=n; k>=0; j++, k--) {
  cout << (n-j)*(n-k) << endl;
}

Forgive my crudeness, but I'm thinking something along the lines of:

$\left \{ \left ( n-j \right ) \cdot \left ( n-k \right )\forall j \left \{ n, n+1, ..., 2n \right \}  \forall k  \left \{ n, n-1, ..., 0 \right \}\right \}$

I'm lost. Should I even be using $\forall$ in this context? Any guidance is greatly appreciated!


texts: Why are NP-complete problems so different in terms of their approximation?

texts:
I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory.

One thing that I've noticed is that while many problems are NP-complete, when extended to optimization problems, some are far more difficult to approximate than others.

A good example is TSP. Although all kinds of TSP are NP-complete, the corresponding optimization problems get easier and easier to approximate with successive simplifications. The general case is NPO-complete, the metric case is APX-complete, and the Euclidean case actually has a PTAS.

This seems counter-intuitive to me, and I'm wondering whether there is a reason for this.


texts: Does basic 2 PL always ensure conflict serializability?

texts:
While going through the DBMS book by Korth, it was mentioned :

" For a set of transactions, there may be conflict-serializable schedules that
cannot be obtained through the two-phase locking protocol.

Does this imply that basic 2 PL ensures serializability but does not always ensure conflict serializability ?


texts: Why isn't every vertex connected to every other vertex in TextRank?

texts:
I've been reading up on the automatic text summarization approach TextRank, particularly for generating summaries of a text using sentence extraction as opposed to keyword or phrase extraction.

In the published paper, an example body of text and the resulting ranked graph of all sentences/vertices and their edges is given. I'm unclear as to why every vertex doesn't have an edge connecting it to every other vertex in the graph - shouldn't all sentences be compared with each other?

This doesn't seem to be addressed in the paper. One possible explanation I've produced is that there is no edge if the similarity between two sentences is 0. Does anyone know for sure?

Link to paper: https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf


texts: What is wrong with this reduction from vertex cover to binary programming?

texts:
I am trying to polynomial-time reduce the decision version of vertex cover to the decision version of binary programming.  Here are the problem statements.

Vertex Cover Decision Problem

Instance: A graph $G=(V,E)$ and an integer $k$.

Question: Does $G$ have a vertex cover of size at most $k$?

Binary Programming Decision Problem

Instance: An integer $m \times n$ matrix $A$, an integer $m$-vector $b$, and an integer $l$.

Question: Is there a a 0-1 $n$-vector $x$ with at most $l$ 1's such that $Ax \geq b$?  Here $||x||_1= \sum_{i=1}^{n}x_i$.

I found a supposed transformation here that makes $A$ an $|E| \times |V|$ matrix, where $a_{e,v}=1$ if edge $e$ is incident on vertex $v$ and $0$ otherwise.  It also sets $b$ to an all 1's vector and $l=k$.

This transformation works in one direction: if you have a vertex cover you can build $x$ by letting $x_v=1$ if vertex $v$ is included in the vertex cover and $0$ otherwise.  However, in the other direction I can easily create an example where $Ax \geq b$ but the 1's in $x$ do not create a vertex cover in the induced graph.  Can anyone provide a hint as to how to correct this?


texts: Please HELP me understand how the ISA works and how it is implemented with the microarchitecture

texts:
How is an ISA written? Is it just a bunch of binary combination encoding presets that is stored onto RAM? In other words, is it basically a “dictionary” of binary being defined as an instruction ‘word’ such as add? Once the instruction ‘word’ is recognized, does that mean an action is defined/assigned in that ‘word’? For example, let’s say 101010 is some encoding in x86 that = add, but then add = 111000, which is some electrical signal of add, then 111000 = action, then action = using ALU take register 1 and 2 and adds them? Also, is storing the result part of that action of add or is it it’s own separate thing? My guess is that it’s part of the action of add.

From my understanding and using my analogy of a dictionary , I’ve thought about it in this way. Instead of thinking of it as one complicated dictionary with meanings on meanings on meanings, I’ve split it into two dictionaries: one dictionary for the encoding of your ISA (the opcodes/instruction format) and the other dictionary for what that encoding means, meaning it’s actions. There’s a microcontroller unit with a ROM aspect that is the dictionary for my so called “action”, which are the electrical signals that correlate to decoded instruction. Then there’s your ISA, set of instructions, that’s located on your RAM which is a dictionary for the instructions when the opcode being called. Am I correct? Please tell me I am. Follow up, how is the ISA loaded into RAM to begin with? What tells it to do that? Is it the microcontroller unit? Also, how does an ISA even go about naming and defining certain registers to have a certain roles and functionalities? I’m genuinely confused. Is the ISA like an OS where as soon as the computer boots, the instructions get stored into RAM (if so, how?) and these registers immediately recognize their names and roles? I definitely feel like I have some sort of misconceptions and misunderstandings here.

Then there's also the instruction cycle which I learned about separately. It's fetch, decode, execute. What is making it do that? How is the cycle being executed? Is that programmed through the ISA? Is it some kind of hardwired thing at the microarchitecture level? If so, please explain.

Lastly, how exactly does the implementation process of the ISA and microarchitecture work? Do you create the ISA first then implement that onto the microarchitecture level? Or is it created by working hand and hand with each other? By that I mean, does Intel have two teams: one dedicated on creating the ISA and one on creating the design of the microarchitecture(hardware)? If the answer is two separate teams, I do not understand how you can go about creating your digital logic(hardware) efficiently without working close together with the ISA team. Even after creating and finishing their product, how do they implement it with one another? Please help me understand the implementation process :(


texts: Enumerating every "partnering" without repeating partners

texts:
I'm taking a class. In this class every week we have a partner. There are an even number of people in the class. We'd like avoid having repeat partners if possible so that everyone gets to work with as many people as possible. I'd like to know how many weeks we could accomplish this before we're forced to partner someone again.

More formally given a set $S$ with an even number of elements, define a "partnering" of $S$ to be a set of partitionings where each part in each partition is of size 2. The empty set is a valid partnering. The set containing any single partitioning of $S$ is a valid partnering. What the largest "partnering" we can define?

If there are $2N$ elements in $S$ then there is no partnering of size greater than $2N-1$. I've also been able to get a rough lower bound on the size of the maximal partnering. The best I've been able to do is half the size of the set but in special cases I can do a bit more. For instance if the size of the set is $2^k*N$ I can get $N+\frac{N}{2} + ... + \frac{N}{2^k}$ but that's a very special case. For powers of two this ideal since $2N-1 = N+\frac{N}{2} + ... + \frac{N}{2^k}$. Ok so for powers of two I have the answer but for other numbers I just have a lower bound.

My current method:

If you have $2N$ elements in your set you can arbitrarily split them into two groups, $A$ and $B$ of size $N$ and assign each element in each group a member of $Z_N$. Call the functions assigning these indexes $Z_a$ and $Z_b$ for the functions that assign them for each group. You can then define $N$ different partitions by first paring $a \in A$ with $b \in B$ if $Z_a(a) = Z_b(B) + k$ for each $k \in Z_n$. That gives you a partnering of size $N$ already. After those pairings have been used up you can recursively split $A$ and $B$ into two groups since no one in $A$ has been partnered with anyone in $A$ yet and likewise for $B$

Intuitively we're splitting the group in two, putting each group in a circle, and then rotating one of the circles. Then if we're lucky we can repeat the process.

Can we do any better or is this optimal? My expectation is that there must be a better result here since otherwise it would mean the size of the maximal partnering has something to do with how many times you can divide the size of the set by 2.


texts: Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?


texts:
I work at a startup and we're doing a lot of online market research to get data about supermarkets in Germany, their name, address, telephone numbers, emails and so that already exist on their website or other places on the internet. my question is: Is there any algorithm that could help us do this job faster instead of doing it manually every single day? Like insert the name of the Supermarket chain and then let it do its thing?
Thank you in advance :)


texts: Algorithm for maximum independent set in trees

texts:
While studying the dynamic programing algorithm for the maximum independent set problem in trees I thought about the following simple alternative algorithm. I tried to prove it's correctness but I do not know how to attack the proof.

The algorithm iteratively finds a two vertices $u,v$ of the tree which have maximum distance among all pairs of vertices, puts $u$ in the independent set and removes $u$ and its neighbor from the tree. This procedure is continued until no more vertices are in the tree.

Does anybody have an idea how to prove that this indeed yields a maximum independent set?


texts: How do NEF networks differ from ANNs in applications?

texts:
As I've described here, the Neural Engineering Framework (NEF) has some functional similarities to Artificial Neural Networks (ANNs). Naturally, there is also an overlap in applications between NEF-based neural networks and ANNs. For example, Spaun, which was built using the NEF, was used to recognize digits from the MNIST data set. Anecdotally, I've also seen an NEF-based network used for gesture recognition.

At both of these tasks, the ANNs vastly surpassed the NEF-based networks. So what's the point on "taking-on" the ANNs on their own turf, aside from biological plausibility? What does a NEF-based network offer application-wise that can't be filled more adequately by an ANN?


texts:
My question is related to the space-time complexity to find the values of n and c by considering this question.

AS we have seen that there are multiple solution for the above equation is possible. But I am confused which one we have to consider.

In solution1: nO = 5 and c = 101 ; this states that we are considering the input after the size of 5 and c = 101 will give us the graph of c(g(n)) closer to f(n).

In solution2: nO=1 and c=105 ; states that we are considering all input but our graph is more away than f(n)

But Big(O) always states that we have to consider the graph whose  rate of growth g(n) which is greater than or equal to given algorithms rate of growth     f(n).

So according to me the solution1 is best Although we are losing the five inputs but we are closer to our f(n)

Or there will be another logic for this ?


texts: Maximize interleaving subsequences two digit arrays/strings

texts:
Suppose I have two digit arrays, A and B as follows

A = [3,4,5,6]
B = [9,8,3]

Now, I have to interleave the two arrays which would mean to pop the first element from both the arrays, at any given point of time. One such interleaving would be as follows,

Choose 3 from A
A = [4,5,6]
B = [9,8,3]
Choose 9 from B
A = [4,5,6]
B = [8,3]
Choose 4 from A
A = [5,6]
B = [8,3]
Choose 8 from B
A = [5,6]
B = [3]
Choose 5 from A
A = [6]
B = [3]
Choose 3 from B
A = [6]
B = []
Choose 6 from A
A = []
B = []
Output array = [3,9,4,8,5,3,6]

In other words, one can choose elements from both A and B but will have to be chosen sequentially.

Now, the question is how can one produce the array that is maximal. In this case, the maximal number would be [9,8,3,4,5,6,3].

P.S. I have already come up about how to solve this with dynamic programming, with the time complexity of $O(mn)$(Here $n$ and $m$ are the lengths of the arrays A and B respectively. But I am actually looking for something more effective(maybe linear time?). The tricky situation is when choosing elements that are equal, and that is where one can optimize. Here I have assumed digits, but each of the arrays could be a separate string as well.


texts: Can someone give me an example of Non Recursively Enumerable language... i.e.  A language which no Turing machine can accept ?  What makes a language non recursively enumerable ?


texts:
As the number of Turing Machines is countably, we can create some list of them and number them 1, 2, 3,... Suppose turing machine k
 computes some function $f_k$.
Is there a turing machine S
 that can computer $f_k(k)$?

It seems like there should be, as I am fairly confident that you can write such a program in a turing-complete language. However, I am having a hard time seeing how an
$n$ state turing machine (if S
 is n states) could compute every function computed by an $n^2$ state turing machine, for example.


texts: Understanding Decision Stump in Adaboost

texts:
I am trying to understand how Adaboost works, and many of the tutorials online involve the use of a decision tree stump. For example, http://www.cc.gatech.edu/~thad/6601-gradAI-fall2013/boosting.pdf or http://www.fromdev.com/2012/04/creating-weak-learner-with-decision.html. However, I am confused on how the plot is actually generated. Say I have the following training set:

               Event 1     Event 2     Event 3
Classifier 1      -1          1          1
Classifier 2      1           -1         1
Classifier 3      1           1          -1

How should I generate a decision stump for this?


texts: How to determine if a state is a fixed point in a Hopfield network?

texts:
I have been reading a lot and I am still unsure of how to determine this. Let's say I have an initial binary state vector (1, 1, 1). How would I go about determining whether (1, 1, 1) is a fixed point in the network?

My initial understanding was to put the state through the network and if it converged to (1, 1, 1) then it is a fixed point. However I have a feeling it is not as simple as that.

Thanks.


texts:
I am guessing that this is correct for 3-EXP, 4-EXP etc...

Basically I should find a problem in 2-EXP that is not in EXP.
Any examples ?


texts: Existence of path under weight and value budgets

texts:
Consider the following problem:

Input: An undirected graph $G = (V, E)$, each edge has a non-negative weight $w_i$ and a non-negative value $v_i$. There are two vertices to represent start point $s$ and end point $t$. We are also given two values $W,V$.
Decide whether there is a simple path from $s$ to $t$ with total weight at most $W$ and total value at most $V$.

How do I show that the problem is NP-hard by reduction from PARTITION?


texts:
Can someone provide an analysis of the update and query operations of a segment tree?

I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and right sub-trees. If we could prove that one of these calls terminates fairly quickly, the time complexity would be logarithmically bounded. But how do we prove this?


texts: How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?

texts:
The HW question, on page 362 of Data Structures and Algorithms in C++: Fourth Editionby Mark Allen Weiss, reads as follows:

  Prove that merging two sorted arrays of N items requires at least 2 * N - 1 comparisons. You must show that if two elements in the merged lists are consecutive and from different lists, then they must be compared

If we are trying to find the lower bound then wouldn't the number of comparisons be N, not 2 * N - 1? If the largest element is some array Ais smaller than the smallest element in some array B then at most you would only have to do N comparisons since after all of A's elements are placed in the merged array then the remaining elements in B's can simply be appended in to the merged array.

The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2 * N - 1 seems more like it would be the upper bound since there is no way there can be more comparisons than that.

Note: I am not asking for an answer to the HW question itself as I know that is deprecated. I am confused about the implied assertion the question is making about the lower bound


texts: what is the relevance of computability when applying diagonallization?

texts:
When thinking about diagonalization, I've always glossed over whether or not the enumeration, or the diagonal is computable or not. When does it matter?
Say for example, that have an enumeration of the rational numbers in an uncomputable order, then we would have to assume that either an uncomputable enumeration of the rationals doesn't exist, or the diagonal gives an uncomputable number?
Or suppose that we had an enumeration of a countable but non-recursive set. Would diagonalization produce an uncomputable number?
Or if we assume that we have a computable enumeration of the computable real numbers, and we do diagonalization on it, then we would have to assume that the number on the diagonal is uncomputable? Something seems wrong here.
In general, what are the catches when doing diagonalization pertaining to computability?


texts: Simple Way to Convert an Adjacency Matrix to a CSR Graph and Vice Versa

texts:
Let's say for the following weighted, undirected graph:

I am given the adjacency matrix A[5][5]:

[0][3][4][0][0]
[3][2][0][0][0]
[4][0][0][6][5]
[0][0][6][0][1]
[0][0][5][1][0]

What is a simple algorithm to convert the adjacency matrix A to a CSR (compressed sparse row) graph in the format of three lists:

row_ptr[]
col_ind[]
val[]

And how about the other way around? (ie CSR to adjacency matrix)

Similar question here

Edit:

Here's the CSR representation of the graph above: (and some explanation)

Note that each value val[i] in the adjacency matrix is at the (x,y) coordinate(col_ind[i],index of row_ptr where row_ptr[index] equals i+1)of the adjacency matrix.

Additionally, the last element of row_ptr is equal to the number of edges+1.


texts: Longest increasing subsequence using 2-3 tree

texts:
While preparing for my data structures final I came across this problem:

A - a given array of integers of length n.

Propose data structure which supports the following operations:

Init(A) - initialisation of the structure given the array A. Worst case complexity: O(nlogn).
LengthOfLongest() - returns the length of the longest monotonically increasing s of A (elements). Worst case complexity: O(1).

I know that it is a well known problem, and I'm aware of the relevant wiki article. However the solution provided there is not intuitive to me.

I was given a hint that this problem can be solved as well with 2-3 rank tree for instance.

Can someone explain me the solution using 2-3 tree?

Example:
For array A = {10,9,11,8,12,7,13}
The longest subsequence is {10, 11, 12, 13} and its length is 4.


texts:
I am trying to justify the big-O order of a runtime complexity by finding a $c$ and $n_0$ that hold for it. Does the left side of the justification need to be one or higher, or can it be any value so long as it is a real number and less than the right side? For instance, is the following valid:
$$n^2/4 + 1/2 \leq c\cdot n^2\,,$$

when $c= 1$ and $n=1$:
$$3/4  \leq 1\,.$$


texts: Does a PDA follow a transition if the top stack symbol doesn't match?

texts:
Does a PDA only move states when both the input symbol matches and the symbol on the top of the stack matches?

In other words, is it possible to have two different transitions that both take the same input character but pop different stack symbols?

For example if we have a state Q0 with the two following transitions:

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

I know that a PDA will transition in regards to the input symbol but how does it handle the stack symbol that it is trying to pop?

For some reason I can not find the answer to this simple question for the life of me. I have searched and searched in my textbook and online.


texts: Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)

texts:
I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time Hierarchy Theorem.

After the assumption, I want to prove that $\mathsf{NP} = \mathsf{DTIME}(2^{n})$.

The first case $\mathsf{NP} \subset \mathsf{DTIME}(2^{n})$, is trivial.

For the second case, let $L \in \mathsf{DTIME}(2^{n})$ and $M$ be a deterministic TM that can decide it, let $$L_{\mathrm{pad}} = \left\{\left\langle x,1^{2^{\sqrt{|x|}}} \right\rangle : x \in L\right\}.$$ I am not sure how, using $L_{\mathrm{pad}}$, I can reach a conclusion that $\mathsf{NP} = \mathsf{DTIME}(2^{n})$, I feel like I am missing something and that my method is not in the right direction, or it is lacking an extra detail.


texts: Prove that it is undecidable whether a given LBA accepts a regular set

texts: I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than Turing machines. Or should I approach with reductions using computational histories of a Turing machine on an input.


texts: Why is the Black-White Bakery Algorithm considered bounded?

texts:
As stated in Lamport's papers for the bakery algorithm he states that the ticket numbers are unbounded specifically

  The range of values of number is unbounded.

and

  Fortunately, practical considerations will place an
  upper bound on the value of number[i] in any real application. For example, if processors enter the doorway
  at the rate of at most one per msec, then after a year of
  operation we will have number[i] < $2^{35}$—assuming that
  a read of number[i] can never obtain a value larger than
  one which has been written there.

What I don't understand is, why does Taubenfeld's Black-White Bakery Algorithm solves this problem and thus considered bounded.

I see no reason why the usage of the extra color register would solve such a problem?

Thanks


texts:
Question on operating system
If we execute kernel programs in the user mode and user programs in kernel mode what are some consequences


texts: Prove the ternary representation of there natural numbers is not a regular language

texts:
Choose some set in the natural numbers such that the language formed by the set under binary representation is a regular language, but is not regular under any other language formed by some base. Prove this using the pumping lemma.

I chose the set $S = \{2^i|i\in\mathbb{N}\}$. It is quite easy to prove this is a regular language under binary representation, but how would you prove that this is not regular under some other base (ie. ternary, quaternary, etc.) using the pumping lemma?


texts: Reduce our problem to a known np-complete problem

texts:
Subgraph isomorphism

We have the graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$.

Question: Is the graph G_1 isomorphic with a subgraph of $G_2$ ?

(i.e. is there a subset of vertices of $G_2, V \subseteq V_2$ and subset of the edges of $G_2 E \subseteq E_2$ such that $|V|=|V_1|$ and $|E|=|E_1|$ and is there a one-to-one matching of the vertices of $G_1$ at the subset of vertices $V$ of $G_2 f:V_1 \to V$ such that $\{u,v\} \in E_1 \Leftrightarrow \{ f(u),f(v) \} \in E$)

In order to show that the problem is in NP, could we say the following?

A non-deterministic Turing machine can first "guess" which subgraph $G$ of $G_2$ is isomorphic with $G_1$ and then verify that $G$ is isomorphic with $G$ in $O(V_1+E_1)$ steps, since if we assume that the graphs are represented as adjacency lists, $G_1$ will have $O(V_1+E_1)$ elements.

Or could I improve something?

I want to show that the problem is NP-complete, reducing the clique problem to it (Hint: assume that  the graph $G_1$ is complete)

Could you give me a hint how we could reduce the clique problem to our problem in order to show that the latter is NP-complete?


texts: Why does the principle of locality of computation not relativize?

texts:
Although I have trouble understanding oracle TMs, I appreciate that non-relativizing techniques will be needed to resolve P vs. NP (as well as most other open problems in TCS).  However, one of the techniques I've read about that does not relativize is using the fact that all of a Turing machine's computation is local and I'm wondering why this is a valid approach.

After all, the oracle tape has to be read somehow and if it is not locally then how?  As I learned through this post regarding the Time Hierarchy Theory and relativization, the oracle of a polytime OTM must be accessed via a polytime reduction so it cannot just act arbitrarily.  Is it just that the oracle tape is read only?  Or is that even if computation is local for an OTM, we just regard this aspect as irrelevant since a call to the oracle is seen as taking one step? Thanks.


texts: shortest form $s$ to $t$ stopping at $u$

texts:
Suppose you want to go from vertex $s$ to vertex $t$ in an unweighted graph $(V, E)$, but you would like to stop by vextex $u$ if it is possible to do so without increasing the length of your path by more than a factor $\alpha$. Find an efficient algorithm that would determine an optimal $s-t$ path given your preference to stopping at $u$ along the way if doing so is not prohibited costly.

Here is my try :

First perform a BFS from $s$. When you get at $t$ you know what is the shortest past in $G$ from $s$ to $t$. We denote the size of this shortest path by $P$. Now we perform an other BFS from $s$, when we get at $u$ we know what is  the shortest path $M$ from $s$ to $u$. Once again we perform a BFS from $u$ and when we get at $t$ we know what is  the shortest path $K$ form $u$ to $t$.
If $\mid M \mid+\mid K \mid \leq \alpha P$ then the optimal path $(M,K)$ is a solution. So we are performing $3$ times a BFS in $G$, thus the overall complexity is $O(X + Y)$ where $X$ is the number of edges and $Y$ the number of vertex.

Is it possible to do better? Is what I said correct?


texts: Finding a local peak in an array in O(log N)?

texts:
So I watched a couple of videos regarding this and the divide and conquer made sense to me. But I am still not convinced as to how recursing on the side with the larger number guarantees us the solution.

Please can someone explain it Mathematically.


texts: Confusion about the Time Hierarchy Theorem and relativization

texts:
I know that $\mathsf{P}^A = \mathsf{EXP}$
for any $\mathsf{EXPTIME}$-complete language $A$.

Is it true that $\mathsf{DTIME}^A(n^k) = \mathsf{EXP}$
for any fixed $k$ and any $\mathsf{EXPTIME}$-complete oracle $A$?
If not, what do these complexity classes equal and why?

I am just confused because then it seems to me that we would then have
$\mathsf{DTIME}^A(n^k) = \mathsf{DTIME}^A(n^j)$ for $k < j$ and
this would contradict the fact that the Time Hierarchy Theorem holds under any oracle.


texts: A regular expression for an automaton which accepts strings with no more than 3 consecutive zeros

texts:
This is the automaton I want to find the regular expression for:

As you see, states Q1 to Q4 are accepted and Q5 is a kind of trap. This automaton accepts strings that have no more than 3 consecutive zeros.
Can anybody help finding a regular expression for this?

Note : What I tried ...
I defined A:=(0+00+000)
So the automata accepts the strings which contain no consecutive A's. But I don't know how to find that kind of regular expression.


texts: Computer Vision algorithm to tell if camera is moving?

texts:
I'm looking for a computer vision algorithm or method that can tell if the camera is moving in a video. Or maybe an alternate way of telling if the background is moving. I have a lot of videos and only want to keep the ones where the camera is stationary.

All videos feature a person talking directly to the camera (the person is mostly stationary throughout the video). I want to keep videos where the camera is stationary, but there are a lot of videos where the person is holding the camera and walking or the camera is moving around too much

I plan to run some algorithm one by one on a collection of videos to determine which video IDs have a moving camera in them.


texts: Existence of boolean function with exponential average case hardness

texts:
Show that for every large enough $n$, there is a boolean function $f\colon \{0,1\}^n\longrightarrow\{0,1\}$, whose average case hardness is exponential. The question is taken from Arora Barak Computational Complexity textbook, Chapter-16, Ex-3.
Average case hardness of a boolean function $f$ is defined as, the largest $S(n)$ s.t. for all circuit $C_n\in \operatorname{Size}(S(n))$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $U_n$ is uniform distribution over $\{0,1\}^n$. I want to show there are boolean functions having $S(n)$ exponential in $n$. My approach is to pick a random $f$ and show via Chernoff bound, the probability of having such function is $>0$.
Formally, I am following this approach, I need to show, $\Pr_{x\in U_n}[C_n(x)=f(x)]-1/2<1/2^n$, $S(n)=2^n$ . Take $Y$ another random variable, $Y=1$ iff, $C_n[x]=f[x]$ else $0$. I express $\Pr_{x\in U_n}[C_n(x)=f(x)]=\frac{1}{2^n}\sum Y_i$,  Now, by Chernoff bound if I can bound the probability $\Pr[\frac{1}{2^n}\sum Y_i-1/2]>1/2^n$ over $C$, I can take the union bound over all $C$ to show that probability is less than $1$. But, I am not sure if I can replace $\mu$ of Chernoff bound with any constant like $1/2$.
Is my approach correct? Can anyone help with my query? $U_n$ is uniform distribution.


texts: Divide and Conquer a problem into a sub-problem to solve it efficiently

texts:
Assume that problem A cannot be solved in O(n^2) time. However, we can transform problem A into a problem B in O(n^2 log n) time, and then solve B, and finally transform the solution of B into the solution of A in O(n) time.

Prove or Disprove: The above approach shows that problem B cannot be solved asymptotically less than O(n^2) time.

My Answer->

Let time complexity (TC) of B be h(n).
So overall complexity is maximum of(h(n), n²logn) which will be greater or equal
to n²logn greater than n² considering the highest polynomial term.

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0 }.

Here f(n) is O(n2logn+n) and g(n) is O(n2logn) which satisfy the above condition at c>=1 and n0 = 0

(n^2 log n) < 1*(n^2logn+n) for all n > 0

So lower bound of solution B is g(n) i.e. O(n^2logn)

So B cannot be solved asymptotically less than O(n^2 log n) time

Therefore B cannot be solved asymptotically less than O(n^2) time


texts: Simultaneously optimal strategies for both players in zero-sum games

texts:
Given a matrix $A \in \mathbb{R}^{m \times n}$ that describes a zero-sum game. What are necessary and sufficient conditions for cases in which the k-th pure strategy of the row-player and the l-th pure strategy of the column-player are simultaneously optimal.

If I understood the definition of a saddle point correctly, the condition for the payoff matrix I'm looking for should be to have such a point.

A necessary and sufficient condition for a saddle point to exist is the presence of a payoff matrix element which is both a minimum of its row and a maximum of its column.
Therefore some entry $a_{kl}$ of the matrix needs to have the property of being the minimum of the k-th row and the maximum of the l-th column.

So if my assumptions are correct, are there payoff matrices with at least one saddle point that do not provide simultaneously optimal strategies for both players? Or in other words, are there more necessary and sufficient conditions to be satisfied?


texts: boolean circuit to decide if there's a path of at most $k$ edges from $u$ to $v$ in graph $G$

texts:
Let an undirected graph and $k\in\mathbb{N}$. Prove that there's a circuit of depth $2$, size of $n^{O(k)}$ and unlimited fan-in, which gets $\langle G,v,u\rangle$ as an input and checks if there's a path from $u$ to $v$ of at most $k$ edges.

So I'm familiar with Warshall's algorithm and I think I should utilize it here. The problem is that it seems impossible to do that with a depth-$2$ circuit.

I'd be glad if you could direct me what to do.

Thanks


texts: What is meant when we say that divergence is the only side-effect of the lambda-calculus?

texts:
In the simply typed lambda-calculus, I was told that behavioral equivalence is taken in terms of divergence because "divergence is the only side-effect of such language".

How should I understand this quotation? What does it mean that divergence is a side-effect? Perhaps that it is a phenomenon that is not directly encoded in the evaluation rules? But then, how do we know there are no other kinds of side-effects?


texts: How can I randomly sample from the set of NP Complete problems?

texts:
I'd like to create some program that can keep spitting out verification algorithms.
My verification algorithms take two inputs: problem instance, and solution (both encoded in binary), and output True or False. Every verification algorithm my program returns needs to satisfy the following criteria:

It terminates in polynomial time (in terms of size(problem instance)+size(solution))
The problem of: "Given a problem instance input, find a solution input that results in the verification  algorithm returning True" is NP-Complete.

It seems like "sampling uniformly" from this space has the same problem of sampling uniformly from the set of integers, so I'm okay with a biased sampling method. However, I'd like every NP-Complete problem to have a non-zero chance of being sampled. Because verification programs are countable, this should be doable.
One idea would be to have some initial set of NP-Complete problems, and consider things like [problem input=(problem A instance, problem B instance, ...) solution input=(problem A solution, problem B solution, ...))] and then AND the individual verifiers. You could even go more general and consider boolean functions on the individual problem's verifiers. This fails because I'm not aware of any "basis" of NP-Complete problems that by composition can give all NP-Complete problems, so we'd be missing some problems that can't be formed as compositions of our problems.
Is this studied somewhere? Or how would I do this? I'm having trouble finding the words for it.


texts: $(max,+)$ matrix product with limited number of values

texts:
I read that there is a $\Omega(n^3)$ lower bound for $(max,+)$ matrix multiplication (with $n\times n$ matrices). This is the matrix product defined as: $(A\cdot B)_{ij}:=\max^n_{k=1}\{A_{ik}+B_{kj}\}$, for some $n\times n$ matrices $A$ and $B$. This lower bound means that the trivial algorithm is the best one.

Is there a better algorithm if we restrict the values to be in a finite set? For example, all the matrix entries are $0$ or $1$. Note that this is different from Boolean matrix product.

Any reference is welcome.


texts:
I've been trying to find interesting applications of union-find that are lesser known. Here are some popular algorithms based on union-find that I know:

Kruskal's algorithm for MST
Tarjan's off-line lowerst common ancestors (LCA) algorithm 1
Solving range minimum queries using union-find by reduction to LCA (with $O(m+n)$ bound given by [Tarjan & Gabow '83, see 1]
Finding connected components
Various textbook examples

Question: What are some interesting use-cases of union-find inside a larger, more complicated algorithm that are lesser-known?


texts: Travelling Salesman: Big O Complexity when starting city is fixed

texts:
We are studying the Travelling Salesman problem in my high school class, and I am wondering what the Big O complexity of the TSP is when you MUST start and end at the same city. For example, given 4 cities labelled A,B,C,D and you MUST start and end at A, what is the big O notation for this? Is ((n-1)!)/2 for both symmetrical and asymmetric cases?

Thanks


texts: Which one of the following string is DCFL

texts:
Is odd length pallindrome DCFL or NCFL?

Like

1) $L=\{w1w^R\mid w \in \{0, 1\}^*\}$

or

2) $S\rightarrow aSa\mid bSb\mid a$

or

Suppose odd length String like

3)$S\rightarrow aSa\mid bSb\mid aSb\mid bSa\mid a\mid b$

We get information about even length palindrome, that it can never be DCFL, but what about odd length?


texts: Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?

texts:
I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related.

Suppose I have a regular expression:
RE=(aa)?(aa)

and I convert it to a grammar:
G ::= A B
A ::= C | (empty)
C ::= D D
D ::= aD | empty
B ::= D D

Can an LALR(1) parser such as Bison generate matches such that I can perform actions such as recording captures, etc... If so, is the cost linear in the size of the input?

If not, is the lower bound on this operation the cost of simulating an NFA generated by the regular expression? I know that DFAs can't perform sub-match captures.


texts: An $\mathbb F$-algebra as input to an algorithm

texts:
I want to specify, what it means to give an algebra as input to an algorithm and didn't find very much literature about it. So first I want to ask if you can recommend a book or paper that deals with the topic of complexity analysis of algebras over fields and clearly define the decision problem.

After some digging I found something and want to share it here and furthermore ask if the definitions make sense and are in compliance with literature (if there is any):

  Definition: Let $\mathbb F$ be a field and $A$ be a finitely generated commutative $\mathbb F$-algebra with additive basis $b_1,\ldots, b_n\in\mathbb F$. We now want to capture the multiplicative structure of the algebra and therefore write every product of base elements as a linear combination of all base elements:
  $$
\forall 1\leq i, j, k\leq n: \exists a_{ijk}: b_ib_j=\sum_{k=1}^n a_{ijk}b_k.
$$
  The $a_{ijk}$ are called structure coefficients. We directly have that:
  $$ A \cong \left.\mathbb{F}[b_1, \ldots, b_n] \middle/ \left<b_i b_j-\sum_{k=1}^n a_{ijk}b_k\right>_{1\leq i,j\leq n}\right..$$
  Now one can define the following decision problem:
  $$
\{(A,B)\mid A, B \text{ commutative $\mathbb F$-algebras with basis $b_1, \ldots b_n$ and } A\cong B\}.
$$
  To specify an isomorphism $\phi:A\rightarrow B$ it is sufficient to write every $\phi(b_i)$ as linear combination of the elements of a basis of $B$.

Does anything in this definition seem strange to you or do you think that one can work with it?

  Motivation: My motivation behind this is to give a very clear definition of the decision problem first to connect it to other problems, i.e. the problem of deciding polynomial equivalence: Given two polynomials $f,g\in\mathbb F[x_1, \ldots, x_n]$, we say that $f$ is equivalent to $g$ if there exists an invertible linear transformation $\tau$ on the variables such that $f(\tau(x_1), \ldots, \tau(x_n))=g(x_1, \ldots, x_n)$. In other words, two polynomials are equivalent if you can replace every variable by a linear combination of all variables to obtain the other polynomial.

I'm not sure if this helps as a motivation but the connection of this problems is established by constructing finitely generated commutative $\mathbb F$-algebras from the two polynomials that are isomorphic if and only if the polynomials are equivalent. For this I wanted to make sure that the decision problem is defined very clearly.


texts:
In college, we've seen some general formulas to compute the decimal value a of a binary representation $a_{N-1} \dots a_2 a_1 a_0$ in two's complement, $N$ being the number of bits.
For $a \ge 0$ we've seen $a= \sum_{i=0}^{N-2} a_i 2^i$, which seems correct to me if I work it out.
But for $a < 0$ our book says $a=-2^{N-1}+\sum_{i=0}^{N-2} a_i 2^i$ and this is where I go wrong.

Can someone explain with an example why this is correct or which formula is right?


texts:
In computational theory for deterministic finite automata, there is a 5-tuple representation containing $Q$, $\Sigma$, $\Delta$, $Q_0$ and $F$. I am wondering how one understands thinking about the number of states to construct such a DFA.

Example:

$$\{w \in\{0,1\}^*\mid w\text{ contains at least two $0$s but does not contain }000\}\,.$$

In the solution, there are 7 states required, $(q_0, q_1, ..., q_7)$.

How should one typically begin understanding the sequence in which they write their states to then cross $\Sigma$ and $Q$ to find the transitions?


texts: What is usually the next step after showing the VC dimension?

texts:
I am new to statistical learning. I have a structure $X$ where I showed its hypothesis class $H$ has VC dimension $d$. All I know now is that I can bound the number of examples by $m\geq \frac{1}{\epsilon}ln \frac{d}{\delta}$ and with probability at least $1-\delta$ I will get a hypothesis with error at most $\epsilon$.

My question concerns what is usually the next step(s),with regard to the big picture of learning a structure $X$, after showing its VCD?

I thought about studying other complexity measures for $X$ but wish to hear others suggestions.


texts: How to make single cycle processor pipelined?

texts:
I was asked that how can one make a single cycle processor pipelined on a CS course without any specifications regarding the design.

I suppose, that I should answer that what should be changed on architecture level.

I am familiar with the meaning of pipelining.

I came up with the following basic idea: registers should be added to hold the intermediate values between pipelining input and output, which should be controlled by a common clock (including i/o).

Is my idea a plausible answer to the question?

At my level, I do not think that I am supposed to give a working example for it, but I am happy so any.


texts: Why are most (or all?) polynomial time algorithms practical?

texts:
I read an interesting comment in a paper recently about how weirdly useful maths turns out to be. It mentions how polynomial time doesn't have to mean efficient in reality (e.g., $O(n^{999999999999999999999})$ is polynomial time, but not efficient). Yet, isn't it the case that all algorithms in polynomial time also happen to be realistic, like at most $O(n^4)$ or something? I guess my questions are:

Is this surprising?
Are there any examples of algorithms that are polynomial time but not practical?


texts: Solving the Size-Constrained Weighted Set Cover Problem

texts:
I'm wondering if anyone has experience trying to solve a weighted set cover problem over the power set (i.e. all possible subsets) of an $n$-element ground set where the number of sets included in the cover is limited by some constant $k$.

This post indicates that the problem is in $\mathcal{P}$ with running time $\mathcal{O} (m^k)$ where $m$ is the number of subsets to choose from; in my setting $m=2^n$, meaning that the given run-time would be exponential in $n$.  I am wondering if this problem can be solved in time polynomial in $n$, the size of the ground set.

I have not come across any publications addressing this problem outside of the one referenced in the link above.


texts: How Model Checking works with User Interaction

texts:
In order to understand how to apply Model Checking, I am wondering how to apply it to a pseudo-realistic async program.

Say I have the following pseudocode:

var array = []

window.onclick = a

function a() {
  setTimeout(b, 10)
}

function b() {
  setTimeout(c, 100)
}

function c() {
  var data = new Data(1)
  array.push(data)
}

function Data(integer) {
  this.integer = integer
}

The program asynchronously does a() -> b() -> c() on click and constructs a new Data object.

Say I have a specification that says "The program will eventually create a Data object on click within 200ms". Wondering what the Model Checker does to prove that this is correct in the program.

So first I rewrite my program as a state machine.

State start

Transition to State idle.

State idle

Transition click to State a.

State a

Transition setTimeout to State b.

State b

Transition setTimeout to State c.

State c

Transition "function" to State d (does var data = new Data(1); array.push(data)).

State d

Transition to State idle

Then the model checker starts at the start state and needs a "click" event to trigger going to state a. Wondering what the model checker path/trace will look like going from start to state d. That will help in understanding how to apply model checking. I don't see how to provide the click event to the model checker or how it should prove the Data statement. It seems like there needs to be some sort of testing/input generation going on but not quite sure (like for generating a fake click event for example).


texts: Question in regards to how an O(N^3) looks like using while/for loops

texts:
would the code below be considered O(N^3)?

while (...) {
   while (...) {
   }
   while (...) {
   }
}


texts: is there a mean of creating a cluster of machines, that can be seen as an entire system, using perhaps mac OS X or mac os x server, and use parallelism and GPGPU optimisation to compute all the tasks of a system,as a single machine? Kind Regards


texts: Given a DCEL, how do you identify the unbounded face

texts:
I have constructed a DCEL using the procedure described in How do I construct a doubly connected edge list given a set of line segments?.

This correctly identifies all faces, however I'm struggling to come up with a way to identify the unbounded face surrounding my graph.

So far my only idea is that by building a polygonal representation of every face, I  could find the face polygon which 'contains' all the others, but this seems kind of messy.


texts: Textbook for understanding formal grammars

texts:
I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably context-free grammars and regular grammars), but not one that specifically deals with formal grammars as an object.

Is there a good textbook for this?


texts: Pseudo random, unqiue integer numbers in a given range

texts:
I need an algorithm that gives me integer numbers with the following features:

Numbers must be in a given range $[n..m]$;
Numbers must be returned in pseudo-random order (random at visual inspection is enough; it is more important that numbers are well distributed over the given range);
Numbers may not repeat before each number in the range $[n..m]$ has been returned once;
Range may be huge (up to $2^{64}$; this excludes all list/shuffle based algorithms);
It should be possible to seed the function so it returns numbers in different order on repetition;
Algorithm should be as fast as possible and should return in constant time.

I wrote code that uses table based bit swapping and optionally XOR and/or addition. It works very well for bit-aligned $n$ and $m$. However it is a bit slow and if the range $n..m$ is not aligned to bits (i.e., $n$ other than $2^x$ and $m$ other than $2^y$), I get either gaps within the returned numbers or extremely non-constant runtime behavior.

How can this be solved?


texts: What is the meaning of uniform distribution of elements in an array?

texts: I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can someone please explain me this?


texts:
I am look for a tool with any or all of the following features:

Regular Expresstion to NFA converter that represents transitions as Binary Decision Diagrams
NFA to DFA converter
NFA minimization
NFA union/complement/intersection

Can you recommend one?


texts: Relation of deterministic push down automata and lower elementary recursion

texts:
Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata.

Deterministic context free languages can be recognized by a deterministic Turing machine in polynomial time.

The lower elementary functions are a subset of the elementary recursive
functions.

Lower elementary recursive functions are limited to polynomial time growth.

From this is it correct to derive that deterministic push down automata are of
equal power to the lower elementary recursive functions?

Edit:
My reasoning is that because the deterministic context free languages can be recognized in polynomial time that a deterministic push down automata is implementing a boolean function of up to that complexity. The lower elementary functions are also up to polynomial time. As such are they not equal in power?