texts:
So there's following problem, that has been bugging me for the last few days:
A solution of a PCP $ i_{1},\dots,i_{n}$  with the cards $(x_{1} ,y_{1}),\dots,(x_{m}, y_{m})$ is considered as $k$-limited if for all $j\leq n$ we say that $|\; | x_{i_{1}}\dots x_{i_{j}}| - | y_{i_{1}}\dots y_{i_{j}}|\;| \leq k$.
So after every time we add another card to our sequence, the difference between the upper and lower part of the card should be $\leq k$.
Apparently it is decidable for a fixed $k$, that a PCP-instance has a $k$-limited solution.
We were told that we should try solving this problem with a DFA over the input alphabet $\{1,\dots,m\}$ - where the word $ i_{1},\dots,i_{n}$ will only be accepted if it is $k$-limited.
Now my problem is that I don't know how to construct a DFA that can check if a solution is $k$-limited and a PCP-solution at the same time.


texts: Prove NP-completeness of deciding whether there is an edge-tour of at most a given length

texts:
We are given a graph G, integer b < |E|, and subset F in E. The problem is to detect whether there is a cycle in the graph with length at most b and includes each edge in F. Prove that this is NP Complete.

I'm thinking of reducing from Hamiltonian Path, but still can't think of the appropriate transformation function.


texts: Suurballe's Algorithm: Proof of Correctness

texts:
I was reading about Suurballe's algorithm on Wikipedia, for the shortest
edge-disjoint paths problem, i.e. given nodes $s$ and $t$ finding a pair of paths between these nodes, whose accumulated weight is minimal.

I understand why the output consists of two $s$-$t$ paths, and the relationship between this and augmenting path flow algorithms on an intuitive level, however I fail to understand why the two paths the algorithm chooses necessarily minimize the weight.

I would appreciate if somebody could explain why the algorithm is correct. I don't have access to Suurballe's original paper and I can't follow the paper by Suurballe and Tarjan.


texts: Why is it necessary to sort according to the starting time in the interval partitioning problem?

texts:
What is the problem if we sort the intervals according to their finishing time like the interval scheduling problem? Could someone give a counterexample
?

Note- (refer here for detailed definition)

Interval Partioning Problem: Multiple Identical Resources are available and we have to partition all intervals across these resources using as few as possible. On each resource all intervals should be non overlapping.

Interval Scheduling Problem: Only one resource is available. We have to maximise the number of non-overlapping intervals we can use on that single resource.


texts: Algorithm for dual sided matching problem

texts:
Is the an algorithm that would help solve this problem:

Teams are swapping members.

Each team has preferences for members it 'wants' from other teams.

Each member has preferences for the teams its 'wants' to join.

Overall matches can only go through (be accepted) if they are balanced. i.e. the number of people leaving a team has to equal the number arriving to the team.

It feels like a stable matching or a top trading cycle problem but I'm not sure how to set it up with the constraint that what goes into a team must come out for the matches to work.

Would be very grateful for any advice

Edit:
Thank you, Aaron and Narek for helping me make the question clearer.

A valid solution would be pareto efficient and strategy proof. I did initially think of stable matching but I came to the conclusion that stable matching would lead to two few valid matches (once you put the one-in, on-out constraint).

Number of teams 10-15, each with between 2 and 10 members, each team is has five preferences of members in other teams, and each member can state 5 five preferences of teams it out join.


texts: Efficiently labelling training data in machine learning

texts:
Obviously it always depends on the specific case. However, my question is how to label data efficiently without writing a source code from scratch which solves the final problem itself?

For example, suppose that I want to use the $k$-Nearest Neighbours algorithm to classify tables from images according to their shape (square tables, rectangular tables, round tables).

For this purpose, I need to find let's say at least 500 images of various tables and then label them.

However, if I do not want to label them manually then I must write extensively a program to do this which essentially is the program I would like to have overall.

In other words, there is no point in writing from scratch an algorithm for accurately labeling data if I want to use machine learning finally because then this algorithm would solve my overall problem without machine learning. However, it is obvious that this algorithm would be very difficult to write to cover all the possible cases e.g. of tables from various images etc.

So how can I label data quickly without writing so many source code lines?


texts: How does the function to curry and uncurrying another function work?

texts:
The following is the code to curry or uncurry a function in Haskell:

curry :: ((a, b) -> c) -> a -> b -> c
curry f a b = f (a, b)

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f (a, b) = f a b

I can understand the type signature part but not the function definition. Would you please explain me how those function bodies turn a curried function into an uncurried one and vice versa?


texts:
Let us consider a product $P$ (whose factors we do not know). Given a base $b$, such that all the Modulus Residues are calculated using powers of $b$ w.r.t. $P$.

For some (unknown) power $x$ we know the corresponding residue ($R_x$), i.e.:

$b^x\bmod P = R_x$.

Query 1: Without knowing (or calculating) the factorization of $P$ and value $x$, for a given $k$, (using $R_x$) is it possible to calculate $b^{(x-k)}\bmod P = R_{(x-k)}$ efficiently?

Query 2: Can the above procedure (if known/exists) help in factorization of $P$?

I am uncertain about how to achieve 1 and its relation to factorization if any.


texts:
I have a simple turing machine with single tape.
I need to compare two words <w1>$<w2>$ and write output.
Language is all letters and numbers.

I did comparation with the {a,b} language but there are more characters.

Is only solution do it one by one in different branches? I mean read / mark the letter (enter the letter branch), go to the second word and read /mark the same letter, go to the first word, repeat?
My problem with this solution is, when I want to change something I need to remake all branches. The other problems are the error handling, when I do not find the right letter I don't want crash. How handle that?


texts: Whether same output is obtained for the two queries

texts:
Consider the following SQL Queries executed on the relation Employee:

Employee (Eid, Ename, sal)

Eid is the primary key
Queries:

S1:SELECT count (*) FROM Employee;
S2: SELECT count (Eid) FROM Employee;

Will these queries return the same result or different results?
According to me, these queries should return same values.
But my solution manual claims that the values returned should be different. It says that S1 will also include results where Eid field is empty.
But according to me, the primary key field can never be empty. So, there will never be a case where Eid field will be empty. As this field will never be empty, the output of S1 and S2 should be equal.
Can anyone please tell me whether I am correct? If not, please tell me what I am doing wrong.
Thanks in advance!


texts: Run-time of a summation function and its complexity

texts:
I am trying to analyze the running time of the following function:
def algo(array: List[int]):
    x = 1
    y = 0
    sigma = 0
    for ix in range(1, len(array)):  #len(array) always >= 1
        summation = 0
        for jx in range(ix, 0, -1):
            summation = summation + array[jx]
            if summation > sigma:
                x = jx
                y = ix
                sigma = summation
    return (x,y)

I have identified a basic unit of the algorithm to count as the number of iterations/total loops, $L$, it runs through. So for instance, if the length of array, $n$, is $1$, then $L = 1$. If, $n = 5$, then $L = 15$. The pattern follows that of the triangular numbers sequence. If you plot a set of points $(n, L)$ you will see that it kind of looks exponential. Is my line of thinking so far okay?


texts: NP-Completeness: A question about reduction and hardness

texts:
I am trying to understand the definition / meaning of reduction.

Is it correct to say that the statement "Problem $A$ reduces to Problem $B$ in $x$-time" is the same as writing $A \leq_{x} B$? For example $\text{SAT} \leq_{polynomial} \text{3-SAT}$.
If we are reducing problem $A$ to $B$ in $x$-time, does it mean that you take an instance in problem $A$, and modify it such that it becomes a valid input for problem $B$, such that the modification is done with $x$ time complexity?


texts:
A class of total functions is a PRC class if:

  The class includes all projection functions $p_i(x_1,\ldots,x_n) = x_i$ and the initial functions $n(x) = 0$ and $s(x) = x+1$.
  The class is closed under composition and primitive recursion.

  Prove that the class of all total functions is a PRC class.

Is it true if I say every total function is computable?
And then say because the class of computable functions is a PRC class, so is the class of total functions.


texts: Using decision oracle to solve optimization problem of maximum polyomino tiling

texts:
So, this problem is a kind of variant of polyomino packing which has been discussed frequently elsewhere, but I haven't been able to find anything on my particular problem. Suppose we have a list of polyominos $p_1, p_2, ..., p_n$ (not necessarily distinct), and we want to find a tiling of a rectangle of dimension $a \times b$ with $a, b \leq n$ that maximizes the number of squares covered, where we can use each $p_i$ at most once, and polyominos must be fully contained within the rectangle. Now, we have the decision problem which tells us, for a given $t$, if there is some tiling covering at least $t$ squares, and the optimization problem which is finding a tiling that covers the maximum number of squares.

There are two parts: first, if you can solve the optimization problem in polynomial time, can you solve the decision problem in polynomial time? And secondly, if you can solve the decision problem in polynomial problem, can you solve the optimization problem in polynomial time?

The first part is easy, for if we have an oracle that solves the optimization in polynomial time, solving the decision problem in polynomial time is obvious.

However, given an oracle for the decision problem, I was unable to find a way to solve the optimization problem in polynomial time. The main issue I'm facing is that the decision oracle only works for rectangular boards, which means we can't just place pieces and then use the oracle to see if the placement works, since we won't have a rectangular board if we want to exclude the piece we just placed. It isn't hard to determine the actual maximum number of tiles you can cover, and you can even find the actual pieces you need to use, but I haven't been able to figure out a way to find an arrangement of the pieces in polynomial time using the oracle. I assume there is some trick here, but I don't see it.

Here are some more details. A similar problem can be found here, so to address the commenter's question a priori we sort of hope that this problem can be solved using the decision oracle. However, there is only one difficulty with adapting this approach which makes it seem fruitless:

The oracle in the linked question is in a sense stronger because it works on any graph. In particular we can encode the notion of coloring using a modified graph. In this sense the oracle of this problem is much, much weaker since it only works on rectangular boards.


texts:
I am familiar with asymptotic notations like Big-O ,little-o. But while I am reading some papers people are using the notations like  $O(\epsilon^{1/2^d})$, $O(d)^d$ etc. I couldn't understand these notations properly. Is there any way (Lecture notes or video lectures with examples) to understand these things clearly.
Thank You.


texts: Efficient data structure for set to union of sets mapping

texts:
What I have is the following:

A mapping $f : key \rightarrow set$ that works in constant time
An inefficient mapping $g : \{key\} \rightarrow \cup_{k \in \{key\}} f(k)$ where this union is slow

Is there a data structure that would make things faster?

I could precalculate for every possible set of keys the wanted output but for a fairly large number of possible keys this isn't feasible ($O(2^n)$), despite the fact that lookup would be fast enough.

Currently I'm using a dictionary to have an efficient mapping $f$. For each value in a set of keys, I get the result by applying $f$, and do a union over the results. This is inefficient.


texts: Why add S0 -> S while converting CFG to Chomsky Normal Form

texts:
While converting CFG to CNF sometimes it is suggested to add extra step.
Add new start symbol S0 and add new derivation S0 -> S. Book Hopcroft Ullman does not suggest this step but many other articles suggest to add this step.
What is purpose of adding this extra derivation?


texts: What is the difference between abstract and concrete data structures?

texts:
I thought associative array (i.e. map, or dictionary) and hashing table were the same concept, until I saw in Wikipedia that

  For dictionaries with very small numbers of bindings, it may make
  sense to implement the dictionary using an association list, a linked
  list of bindings. ...

  The most frequently used general purpose implementation of an
  associative array is with a hash table: an array of bindings, together
  with a hash function that maps each possible key into an array index.
  ...

  Dictionaries may also be stored in binary search trees or in data
  structures specialized to a particular type of keys such as radix
  trees, tries, Judy arrays, or van Emde Boas trees. ...

So, I think, my problem lies in that I don't know that associative array (i.e. map, or dictionary) is an abstract data type and hashing table is a concrete data structure, and different concrete data structures can be used to implement the same abstract data type.

My questions would be

What is the difference and relation between abstract data structures and concrete data structures?
What examples are for each of them (abstract and concrete data structures)? The more the better.
Is there a list of what concrete data structures can be used to implement what abstract data structures? It would be nice to have one.


texts: Language is recursive, hence recursively enumerable

texts:
I was going through a book of proof and I read:

  If L is recursive, L is r.e.

And the proof goes:

Let L be recursive, hence there is a TM that decides it
Convert an halt state to a normal state
Add to program that when it enters this state it goes to infinite loop

How can this be a proof for it?


texts: Is $G_2(V_2,E_2)$ a subgraph of $G_1(V_1,E_1)$ given number of vertices and adjacency matrix for both?

texts:
Given $n_1$ and $n_2$ number of verteces and the adjacency matrix for both graphs, one should determine whether $G_2$ is a subgraph of $G_1$.

I am supposed to use C++ for this, and though I could probably come out with a solution including $20$ for functions, it's most likely not the best approach to the exercise.

Do I have to(?):

Assume the graphs have $n_2$ common vertices (because this has to be in order for $G_2$ to be a subgraph of $G_1$, right?)
Check to see if any of the $\begin{pmatrix}n_1\\ n_1-n_2\end{pmatrix}$ possibly resulting graphs after the removal of $n_1-n_2$ vertices from $G_1$ is equal to $G_2$

Althogh not sure how to compute the above.

This must be an easy exercise since it's for beginners in graphs, but I guess there's just something I am missing. Could you give me some hints on how to approach this in a better way? I've looked for this one a while, hopefully it's not a duplicate.


texts: How must Grovers algorithm be modified in order to solve 3-SAT?

texts:
Grover's algorithm was designed for a database with exactly one item that matches a given search criterion, and can be used to find that very item.

However, when checking whether a given formula is in 3-SAT, I don't know how many items match the search criterion (i.e. how many interpretations satisfy the formula) and I just want to know whether there is at least one. So, what steps have to be taken in order to make Grover's algorithm suitable for 3-SAT?


texts: Decidability of Turing Machines with input of fixed length

texts:
I'm learning about undecidability, and found this question:

Is this language decidable, make a proof:
    L = { M : machine M halts for every input of length not exceeding 100 }

Update: This is translated from an exam paper some years ago, and I'm quite sure it means that machine M should halt for every input with length from 0 to 100, and that it is no constraints on the tape size.

Update2: The solution given below, and hence the origin of this post, is for an variant of this question with fixed number of steps and input. Sorry for the confusion.

I came to the conclusion that this is an undecidable language.

My logic is as follows: Lets say for the sake of contradiction that it is possible to construct a machine $M_R$, that takes as input an arbitrary input $(M,x)$, and reduces this to $M'$. $M'$ has the property so that $(M,x) \in M_{HALT}$ iff $M' \in L$, this means that $M$ halts on all $x$ of input with maximum length of 100.

Then run $M$ on $x$, if it halts then accept.

And shows that $M_R$ decides the halting problem, and in hence a contradiction and proves that his is not decidable.

But in the solution it is written that this question is decidable:

  You can simulate $M$ on all inputs of length 100 or less (you can
  generate such input in a loop and use the universal Turing machine to
  simulate M on x), it is only $|\Sigma|^{100}$ possible inputs of
  length 100, that is finite.


texts: Is this a Fixed Parameter Tractable algorithm?

texts:
Suppose my algorithm runs in time $O(nL^2)$, where $n$ is the size of the input, and $L$ some other parameter, which can get arbitrarily large w.r.t. $n$. My algorithm does not run in polynomial time, since $L$ can get arbitrarily large w.r.t. $n$. So I'd like to categorize it elsewise.
Fixed Parameter Tractable algorithms, with regards to some defined parameter $k$, run in time $O(f(k)\times n^{O(1)})$, where $f$ is any function.

Would it be correct to state that my algorithm is Fixed Parameter Tractable (FPT) with regards to the parameter $L$?


texts: Back Substitution Method for solving recursive equation

texts: Does back substitution method work for any recursive equation? If not is there any generalized form for recursive equation?


texts:
I would like to delete the $\epsilon$-production from the context free grammar with the following rules P:

$$S \rightarrow ASB , BSA, \epsilon$$
$$A \rightarrow aS$$
$$B \rightarrow bB, b$$

Now we were only given this algorithm for that task:

collect all variables from which the empty word is derivable.

-> which in this case is only S

Add to the new rules P' every rule $A \rightarrow \alpha'$, with $\alpha \neq \epsilon$, for which P had a rule $A \rightarrow \alpha$, so that $\alpha'$ results from $\alpha$ by erasing all variables that were collected in step 1.

In this case I would erase $S \rightarrow \epsilon$ and since P included $A \rightarrow aS$ I would add $A \rightarrow a$ to P', giving me:

$$S \rightarrow ASB , BSA$$
$$A \rightarrow a$$
$$B \rightarrow bB, b$$

The grammar with these rules does not, however yield the same language as P, in fact the S never disappears. Can anybody please tell me what I'm doing wrong and how to do it correctly?


texts: Why not implement Union-Find structure using root as the direct parent?

texts: I just learned about using UF with union by rank and path compression. A path can be compressed via attaching a node to its root after Find is called on the node. If the goal here is to flatten the tree, why not just implement the tree such that each node is directly attached to its root (instead of its true parent)? That way, maximum compression would be achieved from the start. What is the con of this as long as union by rank is used along with it?


texts: An $O(n)$ algorithm to FFT-evaluate an FFT evaluation

texts:
This question is from a practice exam in my algorithms class. I'm posting the question and the answer listed in that practice exam:

  Let $W$ be an $n\times n$ matrix whose $(i,j)$-th entry is $\omega_n^{ij}$, where $\omega_n$ is a principal $n$th root of unity. Let $X=(X_0,\dots,X_{n-1})$ be an $n$-vector. The product $W \times X$ can be computed in $O(n\log n)$ time. Let $FFT(X)$ denote the vector that results by applying the FFT evaluation algorithm to the vector $X$.

  Describe an $O(n)$ algorithm to compute $FFT(FFT(x))$.

  Answer: $FFT(FFT(x))$ is $W^2\times X$
  $(W^2)_{jk} = 0$ if $j+k$ is not a multiple of $n$, and $n$ otherwise.

I'm confused about everything:
1. How does this run in $O(n)$? To compute $(W^2)_{jk}$ I'm already  iterating through $n^2$ elements....
2. Why is $FFT(FFT(x)) = W^2\times X$?
3. Why is $(W^2)_{jk} = 0$ if $j+k$ is not a multiple of $n$, $n$ otherwise?

I would appreciate an answer that isn't too advanced as my math skills are limited to basic undergrad math classes of an engineering major.


texts: How to create a LR(k) grammar for an arbitrary k

texts: Is there a simple procedure for constructing a grammar that is LR(k) but not LR(k-1) for any k?


texts: lambda-calc program which halts on only one input

texts:
Does there exist a normal-form lambda calculus program $f$ such that

$f (\lambda x . x)$ normalizes
For all normal form $e \ne \lambda x . x$, $f e$ does not normalize


texts: How to solve the recurrence: T(n) = n*T(n-1) + n?

texts:
In a an exercise I'm required to analyze the runtime of recursive function:

 foo(n)
     for i from 1 to n
         work() // O(1)
         foo(n-1)
     end for
 end foo

The recurrence relation I understand from the code is: T(n) = n*T(n-1) + n

But I'm failing trying to analyze it using the iterative method since I don't see a repeating pattern when I'm opening some of the terms

How do I solve this recurrence ?


texts: Maximum value of $\{ i \land n \mid a \leq i \leq b \}$

texts:
I was doing problems in "Leetcode" and found a problem that I could not solve.

Given a non-negative number $n$ and two non-negative numbers $a$ and $b$, consider every number $i$ such that $a \leq i \leq b$ and among those find the maximum value of $n \& i$ where $\&$ means bitwise and.

I could only solve when $a=0$ by finding the most significant bit location  in $b$ and in $n$ and comparing both and find that $i$ should be $b$ or let location of most significant bit be $k$ from right then it must be $1111111.......1$ $(k-1)$ times.

But when $a \neq 0$ I am struck.  Can anybody help me?

P.S : I am finding the question and I will post it's link by tomorrow.


texts:
How would a CPU know if a piece of data is in cache or RAM or on disk?

This would imply there's some sort of meta addressing scheme on where everything is.


texts: which Pipelining architecture, should i use and how to distinguish them!

texts:
Is there any specific architecture to pipelining that we must follow to perform "operand-forwarding" inorder to avoid its harzards?

My tutor seem to have, there are different architecture. And he taught us 3 different, and i am not even sure how to know which one to use.


texts: Difference between a regular and a stationary source?

texts:
As far as I understand a stationary source is a regular source but it's not necessarily true the other way around.

And a stationary source is a source for which its distribution is unaffected by a "time shift" ?

Can someone clarify the definition and difference of the two?


texts: Selecting a subtree in an array representation of a binary tree

texts:
Consider a zero-indexed array representation of a binary tree (as in a binary heap), where

0 is the root
The left child of i is L(i) = 2*i+1.
The right child of i is R(i) = 2*i+2.

Is there a simple predicate S such that S(i,j) means j is in the subtree rooted at i? It should preferably be quickly computable with something like numpy.

For example, A092754 is the set of nodes in the left subtree of the root 0.


texts:
Does a non deterministic Turing machine which is a decider halt on all branches for all inputs??

I know it must halt on all branches for a string not in language, but for a string in language, NDTM requires only one accepting branch so even if some other branch is infinite, NDTM will still accept the string


texts: Algorithm for packing various shapes inside of a rectangle

texts:
Say I am given a rectangle of width $W$ and length $L$. I now have to fit as many regular shapes of area $A$ into this rectangle as possible. For example, if the shape is a circle, I need to fit as many circles of area $A$ into the rectangle as possible. All the shapes trying to be packed in a given instance are identical, we also assume we are living in 2D.

What would be the general way to approach this problem? Can it be done with a program or is this a mathematical question?


texts: Pumping lemma for $\{110^n10^{n-m}1^m: 1\le m<n\}$

texts:
How can I prove that the language $L=\{110^n 10^{n-m} 1^m \mid 1 \le m < n \}$ is not regular using pumping lemma?

I chose the word $w = 110^{2p} 10^{2p-q} 1^q$ to prove the non-regularity.
Then I started partitioning the word to $xyz$ with $|y| \ge 1$, $|xy| \le p$ and for each $i\ge 0$, $xy^iz$:

\begin{align*}
x &= 110^r\\
y &= 0^s\\
z &= 10^{2p - q} 1^q\,,
\end{align*}
where $r + s = p$
and $s > 0$.

The second partition:
\begin{align*}
x &= 1\\
y &= 10^{2p}\\
z &= 10^{2p-q}1^q\,.
\end{align*}

However, I got stuck at this point because I am not really sure how to find the other partitions and how the choose the correct $i$ for those which I already have.
Any help with this will be appreciated.


texts: Why the time complexity for following pseudocode is O(n^2)?

texts:
So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS.
Here's the rod-cutting problem statement: Given a rod of length n inches and a table of prices pi for i = 1, 2,…n, determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces.
Then, I saw the following pseudocode for solving this problem using top-down approach using memoization:

In the above pseudocode, p is an array, n is an integer.
What I can't understand here is that the time complexity of this algorithm is O(n^2). I saw that reason behind this as shown in the book is following:

The running time of this procedure is O(n^2) since each subproblem is
solved exactly once, and to solve a subproblem of size i, we run
through i iterations of the for loop. So the total number of
iterations of the for loop, over all recursive calls, forms an
arithmetic series, which produces O(n^2) iterations in total.

Although I understand that the for loop in the else block will make the time complexity O(n) but I can't understand how this will form O(n^2)? Can someone please help me to understand it?


texts: Number of elements with lower index equal to some element, for all items on an array

texts:
Let $A$ be an array of size $n$, and $f(i, r, a_r)$ be the number of indices $k$ such that $a_k$ = $a_r$ and $i \le k \le r$.

Example to clarify:

Imagine the array: $[1, 2, 3, 2, 2, 3, 4, 5]$. $f(0, 3, a_3)$, for example, would be equal to 2, because there are 2 elements in the array that appear before $a_3$ (which is 2) and are equal to it.

I've heard one of my colleagues talk about using a Fenwick Tree, but I don't see how that could be done.

I'd like to know if there´s a way to solve this problem in $O(n)$. By solving it I mean finding every value of $f$ for a fixed $i = 0$ and $r = [0, n-1]$

Space isn't really a problem, as long as it's polynomial.


texts: Express semantic duplicates of records formally

texts:
I'm working on a paper about record linkage and duplicate detection and want to visualize my definitions of "hard" and "semantic" duplicates.
Hard ones are a 100% match; where's only true or false-
Semantic ones have different variations but still are representing the same thing.

Now I'd like to write it as a set but actually I have forgotten all about this.

Here are my thoughts about it.
All 4 records are part of the Set "Persons" p

For both: Values are already filtered according to custom settings.
Hard Duplicates

  {[Name]Max; [Surname] Mustermann} ≙

  {[Name]Max; [Surname] Mustermann} ≠

  {[Surname]Max; [Name] Mustermann} ≠

  {[Name]Max; [Surname] M.}

Semantic Duplicates

  {[Name]Max; [Surname] Mustermann}

  {[Name]Max; [Surname] Mustermann} ≙

  {[Surname]Max; [Name] Mustermann ≙

  {[Name]Max; [Surname] M.} ≙

Any help is appreciated


texts: Are DCFLs closed under concatenation with a regular language?

texts:
I have found various opinions saying they are (a link to one is given in D.W.'s comment). However, a proof that DCFLs themselves are not closed under concatenation found here on StackExchange seems to be applicable also to concatenation with regular languages:

  Pick the languages:

  $L_1 = \{a^ib^jc^k | i \neq j \}$ and $L_2 = \{a^ib^jc^k | j \neq k\}$; both are DCFL and $L_3 = 0L_1 \cup L_2$ is DCFL, too.

  $L_0 = 0^*$ is DCFL (regular)

  But $L_{conc} = L_0 \cdot L_3 = 0^* L_3$ is not DCFL.

  Proof: Suppose that $L_{conc}$ (which is the concatenation of two DCFLs) is DCFL.

  If we intersect $L_{conc}$ with the regular language $0a^*b^*c^*$, we should get a DCFL language:

  $L_{conc} \cap \{0a^*b^*c^*\}$ = $0L_1 \cup 0L_2$. suppose $0L_1 \cup 0L_2$ is a DCFL, so $L_1 \cup L_2$ should be a DCFL too, but:

  $L_1 \cup L_2 = \overline{\overline{L_1} \cap \overline{L_2}} = \overline{\{a^ib^ic^i\}}$ which is not DCFL $\Rightarrow$ contradiction.

  ($\{a^ib^ic^i\}$ is not DCFL and the class is closed under complement.)

Is there a reason why the presented disproof wouldn't apply to concatenation with regular languages and if so, is there a more understandable proof of the closure then the one referenced?


texts: Posterior of a DP in a Dirichlet process mixture model

texts:
Draws from a Dirichlet process (DP) are discrete, and exhibit clustering behaviour.

Dirichlet Processes

The Dirichlet Process ($DP$) is a stochastic process used in Bayesian nonparametric modelling. It can be thought as a distribution over probability distributions: its samples are probability distributions whose marginals are a Dirichlet distribution (Ferguson 1973; Antoniak 1974).
Formally, given a distribution $H$ on a probability space $\Theta$, we say that $G$ is distributed according to a $DP$ with parameter $\alpha$ and base distribution $H$ (written $G \sim DP(\alpha, H)$) if, for any finite measurable partition $A_1, \dots A_N$ of $\Theta$, we have $G(A_1, \dots G(A_N)) \sim Dir(\alpha H(A_1)), \dots, \alpha H(A_N)$.
$H$ plays the role of the average of the $DP$, since $E[G(A)] = H(A)$ for every measurable set $A \subset \Theta$.
The draws of a $DP$ are discrete (Blackwell and MacQueen 1973) and exhibit a clustering behaviour: if $\Theta_1, \dots, \Theta_n$ are sampled from a $DP$, the posterior probability for $\Theta_{n+1}$ is
$$P(\Theta_{n+1}|\Theta_1, \dots, \Theta_n) =
\frac{ \alpha H + \sum\limits_{i=1}^{n}\delta_{\theta_i}}{\alpha + n} $$  where $\delta_{\theta_i}$, is the unit mass measure over $\Theta$. The probability of ending up with an already sampled value is proportional
to the number of times it has already been sampled.

Suppose I draw $G_{1:5}$ distributions from a DP. Then the posterior probability for $G_6$ is given by (Blackwell and MacQueen, 1973):

$ \mathbb{P}(G_6 \mid G_{1:5} )= \frac{\alpha H + \sum^5_{i=1} \delta_{G_i} }{\alpha + 5} $.

Understanding this calculation is where I get confused. Suppose $G_{1:5}$ are univariate Gaussian $\mathcal{N}(\mu,\sigma^2)$ and I get five $(n=5)$ draws as so:

$G_1 = \mathcal{N}(0,1); \quad G_2 = \mathcal{N}(0,1); \quad G_3 = \mathcal{N}(1,1); \quad G_4 = \mathcal{N}(1,1); \quad G_5 = \mathcal{N}(2,1); \quad $

Then the posterior probability of $G_6$ is given as:

$\mathbb{P}(G_6 \mid G_{1:5} )= \frac{\alpha H + (1 + 1) + (1+1) +1}{\alpha +5} = \frac{\alpha H + 5}{\alpha +5}$

This is my understanding of the posterior but I do not think it is right. Help would be appreciated (I have misunderstood the delta function I believe, or at least the sum of it).


texts: Constructively deciding whether a decidable predicate holds universally

texts:
I am trying to obtain the proof of the proposition:

$(\forall x \in \mathbb{N}, P(x)) \vee (\neg \forall x, P(x))$

given that the property $P$ is decidable for every $x \in \mathbb{N}$, i.e.

$\forall x \in \mathbb{N}, P(x) \vee \neg P(x)$

This is easy to prove (even without using the decidability of $P$) if I include the law of excluded middle, i.e.,

$\forall P, P \vee \neg P$.

However, I am trying to obtain a constructive proof for the same. Is the proposition true without including the law of excluded middle? If so, how do I prove it? This seemingly simple property is needed to prove something about a complex system, and I am trying to not use the law of excluded middle unless it's absolutely necessary.

The best I could come up with is the following:

$\forall y, (\forall x \le y, P(x)) \vee \neg (\forall x \le y, P(x))$

I do not know how to proceed beyond this (or if this is even useful).

Any help would be appreciated.


texts:
I'm trying to understand what is wrong with the following proof of the following recurrence

$$
T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n
$$
$$
T(n) \leq 2\left(c\left\lfloor\frac{n}{2}\right\rfloor\right)+n \leq cn+n = n(c+1) =O(n)
$$

The documentation says it's wrong because of the inductive hypothesis that
$$
T(n) \leq cn
$$
What Am I missing?


texts: Efficient algorithm to find an vertex that is not an articulation vertex

texts:
This is a question from the book The Algorithm Design Manual by Steven Skiena, Page no- 201.

Articulation vertex : An articulation vertex of a graph (undirected) G is a vertex whose deletion disconnects G.

Given  : Graph (undirected) $G = (V,E)$

Find : A vertex not an articulation vertex

Here is how i tried. I know a brute force way to solve the problem. A1 is the brute force algorithm given below.

Algorithm A1

Pick a vertex say $v$.
Delete the vertex temporarily from $G$ (say $G'$ is a new graph).
Run DFS on $G'$.
If graph $G'$ is connected return (V).
Else repeat (step 1 to step 4) for all vertice of $G$.

Runtime : $O(V(V + E))$

For better running time algorithm i tried to come up with a claim.

My Claim : A vertex is an not articulation vertex if in a DFS tree it involves in a back edge.

If the above claim is true then i only need to run the DFS algorithm once that means running time $O(V + E)$.
So I have two questions 1) Is the claim correct 2) find an efficient algorithm which runs in $O(V + E)$. time.


texts: Decomposing a polynomial over GF(2) into sparse factors mod $x^{2^k}$

texts:
There is a lot of work on decomposing these polynomials to irreducible factors without the modulo $x^{2^k}$ part. That doesn't really work for this problem (apart from giving some upper bound on the sparseness) because the modulo $x^{2^k}$ effectively allows dividing anything by any polynomial that has $1$ in it, so divisibility tests don't work: everything is divisible by anything that matters. Also I don't care about irreducibility, but I do care about sparseness, and no decomposition algorithm that I could find takes that into account.

For the sparseness, what I want to minimize is the total count of non-zero coefficients while disregarding the constant $1$ in factors. So $x + 1$ has a "cost" of 1, and $(x^2 + 1)(x^7 + x^4 + 1)$ has a "cost" of 3.

Sometimes the common algorithms work, $x^7+x^6+x^5+x^4+x^3+x^2+x+1$ can be factored into $(x + 1)(x^2 + 1)(x^4 + 1)$ by standard polynomial factorization (without even using that the coefficients are elements of GF(2)), which is great because all the factors are sparse and there is nothing sparser. But this just worked because, viewed "backwards", multiplying out the factors did not rely on reduction modulo $x^8$, and that the result is sparse is a coincidence. So for example I want to factor:

$x^7 + x^5 + x^3 + x + 1$ into $(x + 1)(x^3 + 1)(x^4 + 1)$
$x^7 + x^6 + x^4 + x^2 + 1$ into $(x^2 + 1)(x^7 + x^4 + 1)$

I could not find an efficient existing algorithm to do so.

So far I have been doing the decomposition in a fairly brute force manner:

# initialize with single-factor
for i in range(256):
    factor[i] = i
    cost[i] = popcnt(i) - 1
# search for improvements
for t in range(4):
    for x in range(1, 256):
        for y in range(1, 256, 2):
            p = clmul(x, y) & 0xff
            if cost[x] + cost[y] < cost[p]:
                cost[p] = cost[x] + cost[y]
                factor[p] = y

But this approach is hopeless for polynomials with a degree of 32 or especially 64. The range of t can actually be smaller, this process converges in very few iterations even for higher degrees - the problem is the inner loops.

Converting it to a circuit-SAT problem (plus binary searching over the number of nonzero coefficients) works well sometimes but other times the SAT solver really struggles with it.


texts: Sum and intersection of different complexity classes

texts:
It is known the fact that $NP$ class is closed on sum and intersection. But, what about another complexity classes?

Ok, I have to make my question more precise:

For example: Let $C$ be any complexity class $L_1 \in C, L_2 \in C$.

Is it possible that
$$ 1) \ L_1 \oplus L_2 \not \in C, \oplus \text{ is a symmetric difference}$$
$$ 2) \ L_1 \cup L_2 \not \in C$$
$$ 3) \ L_1 \cap L_2 \not \in C$$

Why I have doubts:

From point of view algebra on sets, it is true that:
$L_1 \oplus L_2 \in C$ (and similarly for 2) and 3)). But, I can imagine after $\oplus$ there is no Turing machine from $C$ recognizes $L_1 \oplus L_2$ so it is not language from class $C$ though it seems that it is (algebra on sets says it).

Please explain because it is evident that my reasoning is cheesy.


texts: Why is the carry of any n base system equal to the radix in arithmetic?

texts: In binary the carry/borrow is 2, in hex the carry is 16. What's the reason for this?


texts: Solving shortest path problem with Dijkstra’s algorithm for n negative-weight edges and no negative-weight cycle

texts:
Although many texts state Dijkstra's algorithm does not work for negative-weight edges, the modification of Dijkstra's algorithm can. Here is the algorithm to solve a single negative-weight edge without negative-weight cycle.
Let $d_s(v)$ be the shortest distance from source vertex s to vertex v. Suppose the negative edge $e$ is $(u, v)$
First, remove the negative edge $e$, and run Dijkstra from the source vertex s.
Then, check if $d_s(u) + w(u, v) \leq d_s(v)$. If not, we are done. If yes, then run Dijkstra from $v$, with the negative edge still removed.
Then, $\forall t \in V $, $d(t) = min(d_s(t), d_s(u) + w(u, v) + d_v(t))$
Given the above algorithm, I want to modify the above algorithm again to solve n negative-weight edges and no negative weight cycle. Any hint?


texts: Finding numbers near the median in linear time

texts:
Problem:
Describe (English is enough) a linear algorithm that, given a set $S$ of $n$ distinct numbers and a positive integer $k \leq n$, returns the $k$ numbers in $S$ that are closest to the median of $S$.
Answer:
I interpret the term linear algorithm to mean one that runs in $O(n)$ time. It is not clear to me if that means worst case or average case. I would tend to think worst case.
\newline
I claim that problem may not have a unique solution. For example, if we are given
$S = \{ 1, 2, 3, 4, 5 \}$ and $k = 2$ then we have the following two valid solutions:
\newline
$S = \{ 2, 3 \}$ and $S = \{ 3, 4 \}$.
Here is my algorithm, which I do not believe meets the performance requirements
of the question:
Let ans be the set of numbers we want to return.
Compute the median of S and call that value m.

Initialize the set ans to the first k elements of S.
// One data structure to hold ans would be an array. A better choice might be
// a binary tree / heap.
for i = k+1 to n (inclusive)
       if S[i] is closer to the median then the element of ans that is farthest
            away from the median then
                update ans by replacing that element with S[i]
       end if
end for
return ans

I am assuming that we can find the median in $O(n)$ time. Depending on the data structure chosen for ans, the running time for the code will be $O( n \log k )$ which is linear in $n$.
This does not seem right to me. Is it? If it is wrong, where did I go wrong?
Does this problem even have a valid solution?


texts:
I have to prepare for a midterm and I am looking for a resource where I can practise the three basic sorting algorithms insertion sort, bubble sort and selection sort a little.

Last year they had to sort an array with n elements and the elements were integers with values between 0 and m-1 and the complexity had to be of O(n+m).

I did not find any good resources as most of them deal with more advanced topics and prepare you for interviews.

So I would be glad if someone could give me a good hint.


texts:
The below example confused me:

lw $r0, 4($r0)
sw $r0, 4($r0)
add $r0, $r0, $r0

Using MIPS 5 stage execution what are the hazards we have 1) without forwarding 2) with forwarding only in the stage of execution (exe or alu) 3) with forwarding. Add nops to eliminate hazards.


texts: How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $

texts:
I have a real function $f:\mathbb{{R}}^{d}\mapsto\mathbb{R}$, where
$d>1$. The question is how to compute the level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $.
I am a statistician knowing very few things about computer science.
I would appreciate very much if anyone could suggest some reference, methods
and/or alogirthms.

In my problem, $f\left(\theta\right)=\sum_{i=1}^{N}\log g\left(\mathbf{z}_{i};\theta\right)$,
where $g\left(\mathbf{z}_{i};\theta\right)$ is a probability density
function of $\mathbf{z}_{i}$ parameterized by a vector of parameters
$\theta$. $\mathbf{z}_1,\ldots, \mathbf{z}_N$ are observed samples. For example, $g\left(\mathbf{z}_{i};\theta\right)$ is the density function of
a normal distribution with variance $1$
$$
g\left(\mathbf{z}_{i};\theta\right)=\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{\left(y_{i}-\mathbf{x}_{i}'\theta\right)^{2}}{2}\right).
$$
Here $\mathbf{z}_{i}=\left(y_{i},\mathbf{x}_{i}\right)'$.


texts: Why can't a compiler just "think more" about optimization?

texts:
This happens to me from time to time: I compile my code with the highest optimization level (-Ofast) of the allegedly fastest compiler (GCC) of one of the fastest languages (C/C++). It takes 3 seconds. I run the compiled program, measuring performance. Then I make some trivial change (say, marking a function inline), compile it again, and it runs 20% faster.
Why? Often I'd rather wait a few minutes or even hours, but be sure that my code is at least hard to optimize further. Why does the compiler give up so quickly?
As far as I know modern architectures are super complicated and hard to a priori optimize for. Couldn't a compiler test many possibilities and see which one is the fastest? I effectively do this by making random changes in the source code, but that doesn't sound optimal.


texts: One-dimensional packing problem: Optimal decomposition of music structure

texts:
I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music.
Problem Description
Given a section range in a song in seconds (or samples) , e.g. [10,20], I can look up where this section is repeated. Then we end up with a set of repeating sections like: [[10,20], [40,50], [70,80]]. We call this a group. A group has a certain fitness given to it.
(As a sidenote, the fitness of a group is defined as a combination of the sum of similarity values and how much of the song they cover alltogether)
Our goal is to find a set of disjoint groups that altogether have the highest fitness; the optimal decomposition of the repetitions. Below are two different valid decompositions of the same song, one course, and one fine decomposition.

We are provided with a set of all candidate groups, here's a small selection, sorted top to bottom by fitness:

Current Greedy Method

Sort all candidates by fitness
Pick group G with the highest fitness
Remove any groups from candidates if they have overlap with G
Repeat from step 2 until no candidates are left

Bonus
Sometimes the candidates overlap every so slightly, which in the context should perhaps not immediately lead to disqualification.

There are options to relax the no-overlap rule. Note that each of the sections in a group has a different brightness. This brightness corresponds to a confidence, so in a group some sections are more certain to be proper repetitions than others.
For a group of sections G that we wish to add to a set of groups of sections S, we can:

simply remove sections from G if they overlap with any sections in S
trim the sides of to-be-added sections from G if they overlap with any sections in S
keep the overlapping sections in G

I hope this problem is interesting enough to you to give it a shot!
Thank you!


texts: Finding the number of ways to partition $\{1,...,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$

texts:
I am trying to think of how to optimize the following problem:

Let $S = \{1,2,...,N\}$. How many ways can $S$ be partitioned into non-empty subsets $P_1$ and $P_2$ such that  $sum(P_1) = sum(P_2)$? I have implemented an algorithm that checks all partitions of $S$ into 2 subsets $P_1$ and $P_2$, but I am wondering if there is a faster algorithm.


texts: Asymptotics of recurrence $f(x) = 8f(x/2) + O(1)$

texts:
What is the asymptotic rate of growth of the following recurrence relation?
$$
f(x) = \begin{cases}
8f(x/2) + Θ(1) & \text{ if } x^2 > M, \\
M &  \text{ if } x^2 \leq M.
\end{cases}
$$
Here $M$ is a constant.
I'm not sure how to do it with the condition on $x^2$.


texts: How do we determine p (pumping length) in pumping lemma for CFL?

texts: This has been confusing me for a while, how do we exactly choose the pumping length when we want to prove whether a language is CFL or not. For example, when we want to prove that {ww, w: {0,1}* } why do we choose p = n as 0^p 1^p 0^p 1^p ?


texts: Good "serializer" ADT implementations for Synchronization

texts:
I am looking for a library which provides a "serializer" ADT for synchronization.
(http://courses.cs.vt.edu/~cs5204/fall99/Summaries/Concurrency/serializers2.html)

Googling leads me to nowhere, unlike monitors,semaphores and other constructs, serializers are hardly discussed over the web in depth.

Any other pointers are welcome. :)


texts: Why don't they use all kinds of non-linear functions in Neural Network Activation Functions?

texts: Pardon my ignorance, but after just learning about Sigmoid and Tanh activation functions (and a few others), I am wondering why they choose functions that always go up and to the right? Why not use all kinds of crazy input functions, those that fluctuate up and down, ones that are directed down instead of up, etc.? What if used functions like those in your neurons, what is the problem, why isn't it done? Why do they stick to very primitive very simple functions?


texts:
Does anyone have any advice about how I can fast track my understanding of what these types of algorithms mean:

http://en.wikipedia.org/wiki/Monad_(category_theory)

I don't want to have to sit 3 years of maths but is there anything I can do for this to make more sense?


texts: Complexity of finding a perfect matching in directed graphs

texts:
To the best of my knowledge, finding a perfect matching in an undirected graph is NP-hard. But is this also the case for directed and possibly cyclic graphs?

I guess there are two possibilities to define whether two edges are incident to each other, which would also result in two possibilities to define what is allowed in a perfect matching:

Allowed in the perfect matching are only edges that do not share a common start or end point, i.e. antiparallel edges are not allowed in the perfect matching.
Antiparallel edge are allowed in the perfect matching, i.e. selecting edge $v_i\rightarrow v_j$ does not exclude selecting $v_ j\rightarrow v_i$.

What I've read sofar, option 1 is the typical generalization for directed graphs, but is finding a perfect matching NP-hard for both cases?


texts: Analysing the complexity of a recurrent function i+1,j*2

texts:
Let's say we start with $i = 1$, $j = 1$, $i \leq n$, and $j \leq i$ and
then increment $i = i+1$ and $j = 2j$, respectively.  The output prints
$k$ times, which represents the inner loop.
Output: print s $k$ times.
Example when $n=5$, loop will print 11 times.  How to find the
complexity function of this algorithm for $n=5$?
So far, I figured out the pattern for $n=5$, $p = 1+(2+2)+(3+3)$ which
can be generalized by $k \cdot 2^{k-1}$ for $n$ size
$1+(2+2)+(3+3+3+3)+\dots$.
The answer is $$((n+1)\log(n+1)+1)-(2^{(\log n+1)})$$ by the summation
$k \cdot 2^{k-1}$—constant when $k=1$ to $p$.
How do I go from summation to this answer?
What value should be $P$ if I do summation from $k=1$ to $P:1+(2+2)+(3+3)$?


texts:
Question:

  If a system has $32k$ bytes and each such byte has unique address(so $32k$ addresses), what is the smallest possible bits that can be use by every byte for the address ? All the bytes use the same number of bits for the address.

I thought the answer can be found by finding the value to which $2$ can be raised such that it equals $32,000$. I got $2$ raised to $ \sim 14.96$ gives $32,000$. But a byte only has $8$ bits so this can't make any sense.

Can anyone give any pointer on how to solve this problem ?


texts:
https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomputability_of_S.28n.29_and_.CE.A3.28n.29
So this is wikipedia's proof of why Busy Beaver Function is uncomputable. But I don't get two things.

How do you know that < Create_n0 | Double | EvalS | Clean > has $N$ states? I understand that < Create_n0 | Double | EvalS > has $N$ states but I don't understand why adding Clean doesn't change the number of states.

Why do we need to make a Double function? Can't we prove like this: Let's say the Turing machine < EvalS | Clean > has $n_0$ states. Let $\textrm{BadS}$ denote < Create_n0 | EvalS | Clean >. $\mathrm{BadS}$ has $n_0$ states but has more than $S(n_0)$ shifts, therefore, contradiction.


texts: Are tamper attacks considered side-channel?

texts:
Wikipedia defines side-channel attacks as:

  any attack based on information gained from the physical implementation of a cryptosystem

Usually in side channel attacks the implementations leak information (e.g., timing attack: the implementation leaks the time it takes to complete a task, etc.)

Are tampering-attacks also considered as side-channel attacks?

On one hand, tampering-attacks are (usually) attacks on the implementation itself.
On the other hand, the attack might be such that information only enters the device, and no information comes out of the device, so there is no "side-channel" that leaks the information.
(example: If we heat some access-control device, until it grants us the access. Or if we perform SQL injection that causes the device to grant the access (but leaks no secret other than that))


texts: Datastructure for lookup of single point in range (3d)?

texts:
I'm new to CS and being aware of what algorithms exist, but what data structure allows you to have fast lookups of single points within a distance in 3d?

e.g. (with 2d circles instead of 3d spheres)

I would expect the first location to return null, and the second one to return circle a.

Circles can not overlay, circles/spheres differ in radius.

I would assume this to be nearest neighbor, but maybe some optimizations can be made considering you are often outside the area?


texts: Applications of signed permutations to machine learning

texts: Are there some applications of signed permutations to machine learning? I searched on google and only found one paper. Thank you very much.


texts: Does the language defined in the details in NP-C or P?

texts:
It's known that:
$$
\textrm{CLIQUE} = \{(G,k): \mbox{G has a clique of size } k\}
$$
is $\textrm{NP-C}$, but what if every vertex has 2 neighbours (as defined in $\textrm{2d-CLIQUE}$)?
$$
\textrm{2d-CLIQUE} = \{(G,k): \mbox{every vertex in G has exactly $2$ neighbours and $G$ has a clique of size } k\}.
$$


texts: Can you insert into sorted list with time O(1)?

texts: Wondering if this was possible. If I have a sorted list, can I find the right spot for an integer and insert it, all in O(1) time? The only way I can think to do this is via having a MASSIVE hashmap with one slot for each possible integer. 2 billion different integers * 4 bytes per integer = 8 gigabytes....but it'd technically work. There has to be a better way to do this though, right?


texts: From my understanding, Turing complete means that the program or machine can complete any computation that a Turing machine can complete, which to me means any computation. So how can something like HTML or PowerPoint be Turing complete?


texts: Is there a language that cannot be polynomially reduced to?

texts: Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?


texts: Why are unbalanced partitions worse than balanced partitions in Quicksort?

texts:
I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions.

After reading this document it shows that worse case partitions are of the type $(0,(n-1)), (0,(n-2)), (0,(n-3))$ and so on. So the work on every step is $Cn, C(n-1), C(n-2)$ , it actually decreases since $C(n) > C(n-1)$. Correct me if I am wrong.

While in best case the partitions on every step can be assumed as $n/2$ on each side or $n/2$ or $n/2 - 1$ on each side. So the work done on each step, is $Cn$
 always.

So how is that better than unbalanced partitions ? The work actually decreases in every step for unbalanced partitions, while for balanced partitions the work actually remains constant on all the steps and depending on the partition algo it may even include the pivot which is already sorted.


texts: Why must a function with polymorphic type `forall t: Type, t->t` be the identity function?

texts: I am new to programming language theory. I was watching some online lectures in which the instructor claimed that a function with polymorphic type forall t: Type, t->t be the identity, but did not explain why. Can someone explain to me why? Maybe a proof of the claim from first principles.


texts: Theory of Complexity - Relation between a class and its complement

texts:
i'm in trouble trying to prove the following proposition:

Proposition If $\ C$ is a class closed under reductions and a $\ C$-Complete problem belongs to $\ coC$, then $C=coC$.

Note: $C$ can be any class.

To prove that proposition i thought to split the proof in two ways:

(*): $C \subseteq coC$

I suppose it exists such an $L \in coC$ that is $C$-Complete. For all $L' \in C$ there is a reduction $R : L \rightarrow L'$. Thus $L \in coC$ and $coC$ is closed under reductions (because $C$ is), $L' \in coC$ also, so $C \subseteq coC$.

(*): $coC \subseteq C$

That's the part i'm not able to prove.

Thank you so much.


texts:
Let's consider 128-bit LCG with modulus $2^n$ of the form:
$X_{n+1}=a \cdot X_{n} + c \mod 2^{128}$
How fast we can run it in cycles per byte? And how much of RAM it required?


texts: Is this big O notation format correct? $3^n = 2^{(O(n))}$

texts:
I am completing a university exercise deciding whether big notations are true or false.

I am stuck on this question :

  $$3^n = 2^{(O(n))}$$

I want to answer False as the format looks incorrect and I have never seen big O notation written is this way.

Is this a valid way to write big O notation?


texts: Connection between vertex cover and P=NP

texts:
I read about vertex cover and i can't understand why the following occurs. Tried to look and research on the site and in other places but still can't understand it.

In an undirected graph $G(V,E)$, vertex cover is a set of edges U so that every Edge in E has at least one end at U.

Defining the following function: $f(G,v)$ equals to the minimal vertex cover that v belongs to.

Why if it is possible to calculate in a polynomial time  the function $g(G,v)$ and it is guaranteed that $f(G,v) -5 \leq g(G,v) \leq f(G,v) +5$ then P=NP?

(Meaning if we can estimate f in a constant boundary of +5 in a polynomial time, then P=NP?)

What i think:since vertex cover is an NP-COMPLETE language, and so is the minimal vertex cover, if it is bounded by +-5, a linear bound. then if known that $g(G,v)$ can be calculated in polynomial time and we can also show that it's boundaries are $f(G,v) - 5$ and $f(G,v)+5$, then P = NP.

So regarding minimal vertex cover, the problem is $min(f(x)| x \in vertexcover(G))$. so an algorithm for minvertexcover is: initialize {cover<-0, Edges<-0}; until there are no more edges $e \in E$ in G: 1)add u,v to cover; 2)add $e_i$ to Edges; 3)remove u,v from G and adjacent edges.

Now, since $|Edges = 2 * cover|$, then for a possible solution, meaning vertex cover that covers all the edges, that possible solution will be more than Edges, so that possible solution will be bigger than 2 * Edges.

Since that possible solution $\geq 2 * Edges$, it means that the possible solution is $\geq f(G,v) + 5$, so it is bounded. now if we can calculate $g(G,v)$ in a polynomial time, it means we can calculate the possible solution in at least 2 * polynomial time, which is still polynomial. so it means that if $g(G,v)$ can be calculated in polynomial time, and the given +-5 boundary exists, then P=NP.

How to prove it correctly and efficiently? spent long days on it and would appreciate seeing how to do it correctly


texts: Creating a DFA that only accepts number of a's that are multiples of 3

texts: I am brand new to DFA's and my first exercise requires me to create a DFA instance such that the number of a's in the string is a multiple of 3. We only have two types of symbols: a, b. To my understanding something like "aaabbaaa" would work but "aabbb" would not. Any help or hints would be greatly appreciated


texts: Proof for P-complete is not closed under intersection

texts:
Unfortunately I have no idea how to show this:

  Show that the set of ${\sf P}$-complete languages is not closed under intersection.

As far as I understand my lecture notes, ${\sf P}$-completeness is defined as follows:

$A \subset \Sigma^{*}$ is complete for ${\sf P}$ iff $A \in \text{P}$ and $\forall B \in {\sf P}, B \le_L A$
$\le_L$ is ${\sf LOGSPACE}$-reduction: for $A,B \subset \Sigma^{*}$, the relation $A \le_{L} B$ is defined by
$$A \le_{L} B \quad\text{iff}\quad \exists f \in {\sf FLOGSPACE}, (x \in A \Leftrightarrow f(x) \in B)$$


texts: Data structure optimized for merging maps on partitions

texts:
My question is a request for literature or pointers that address the following abstracted problem. If I have a finite set (ex. {1..10}) over which I'd like to maintain several "partition maps":

m1 = {1..5}=1, {6..10}=2
m2 = {1..3,8..10}=3, {4..7}=4.

Afterwards I'd like to merge (generalize the operation, but use addition for demonstration) these maps:

m1 + m2 = m3 = {1..3}=4,{4,5,8..10}=5,{6,7}=6.

If n is the size of universal set, and k << n the size of the range of the maps. How does one get performance (and space) closer to O(k) as opposed to O(n) (store an array)?

Edit (2017-11-14): I'm mainly interested in merge performance, lookup can be slow. To sharpen the question, there are a couple of approaches to this problem that don't quiet address this trade off:

Okasaki's Fast Mergeable Integer Maps
Erwig's Diets for Fast Set
Bonichon's A Mergeable Interval Map. This probably gives the closest of what I'm looking for, but unfortunately the exposition is a bit confusing and I'm not certain that there is the same tradeoff of merging above lookup.

Edit (2017-11-15): The application where I'm using this performs millions of merges. In the most common instance I have 4 of these maps and compute a new map. The keys are different states and the values are actually probabilities. The probabilities are discretized which is why lots of different states have the same values. It is a form of "compressed" computations. I can use an array to store these values, but this compressed form provides 100x performance currently, but I'm looking for a technique to improve upon that (I need to do billion of merges). As @D.W. described below, batched techniques would also be of interest.


texts:
In linear time logic, is $\mathbf{GF}p$ equivalent to $ \mathbf{G}p$ ?

$\mathbf{GF}p$ means that it is always the case that p is true eventually.

Let $\mathbf{G} p$ be defined as: $\forall j \ge0,\  p$ holds in the suffix $q_j, q_{j+1}, q_{j+2},\ldots$

and since:
formula $φ$ holds for state machine $M$ if $φ$ holds for all possible traces of $M$

Isn't $\mathbf{G}$ in $\mathbf{GF}p$ redundant then?


texts: Prove that language is not regular using pumping lemma

texts:
Could anyone tell me If I can prove regularity of given language using pumping lemma like I did below? If my prove is wrong could anyone tell me how to prove that the language is not regular using pumping lemma?

$$
L = \left\{ a^{n}b^{i}c^{n}\in L \mid (m,n,i >=0)\ and\ ((m +n)\%3 = 0 ) \ and\ ( m + n >= i ) \right\}
$$

I suppose that the language is regular. I know that $i,m,n >= 0$ so I will choose word from the language $w = b^{p}c^{3p}$. The condition $(m + n) \% 3 = 0$ should be fulfilled since $\forall p >= 1 : 3p \%3 = 0$.

$$|w| >= p$$

$$
\underbrace{bbbb....b|}_p\underbrace{cccc......c}_{3p}\
$$
Now i can decompose $w$ as $w=xyz$ with $\lvert y\rvert\geq1$ and $\lvert xy\rvert\leq p$.
$$x = b^{l},\  l\ge 0 \\y =b^{k}  \,,k\ge 1 \\ z = b^{m}c^{3p} \,,m\ge0 \\(l+k+m=p) \ and\ (l+k \leq p)
$$

I'll try to pump $i$ so the word won't be in language $xy^{i}z$

If I put $i = \frac{3p+1}{k}$ then i get: $$b^{l}b^{{k}{\frac{3p+1}{k}}}b^{m}c^{3p} = b^{l}b^{3p+1}b^{m}c^{3p}$$ which is not from the L because the amount of b is greater than c.


texts:
I'm designing a web app to host e-sports tournaments and want to create an algorithm that generates tournament brackets.

Given a list of participants' user ID's (minimum 4, maximum let's say 64), I want to generate a bracket in the form of a list of pairings, where each element of the pair represents a match participant or a reference to the winner of a previous match, i.e. User 1 vs. User 2, Winner of match 1 vs. User 3, and so on.

A simple example, given the array of entrants:

(user1, user2, user3, user4)

We get the end result as a set of pairs, in the logical order:

(user1, user2), (user3, user4), (winner0 vs winner1)

Where winner0 refers to the winner of match 0 (the first pair in the result set). Thus, the winner of the last match in the set is the winner of the tournament.

I need this to work with any size entrant list between 4 and 64 (or some other theoretical maximum), not just for powers of 2. When the entrant count is not a power of 2, some entrants must get one more or one fewer match in order to fill in the entire bracket. All initial placements will be random.

I suppose it's also possible to represent the result as a binary tree, but I'm not sure I will be able to apply it that way.


texts: is the problem of parallelising any program, NP-complete?

texts:
Consider a program written in a common language such as C.  Assume that it does not have any explicit parallel constructs.  Then, once it is compiled to an executable program, it will be run serially, even if the machine has multiple processors.

Now, suppose we wanted theoretically to write a "parallel compiler", which would analyze such a program and figure out what operations are safe to execute concurrently, and output an executable which would run in parallel on multiple processors, so that, no matter the timing between these threads, the program in the end will come up with the same results as with "serial compiler".

I am guessing that such a compiler, if possible, would need a very long time to calculate - I am guessing that the problem "parallelize an arbitrary program" must be at least NP-complete (possibly exp).  Is that known, and if so, is that true, and if so, can you point me to a published argument?

Let me try and formalize the problem better.  Assuming each instruction emitted by the compiler executes in unit time, then for a given number of processors, and assuming the processors communicate and access memory instantly, given that some instructions will depend on others, there is theoretically the shortest possible time to complete the program.

Let's say we want our compiler, maybe not reach this theoretical limit, but come up with instructions that will take up to 2x the theoretical limit.


texts: How to leverage the fact that I'm solving 1000's of very similar SMT instances?

texts:
I have a core SMT solver problem consisting of 100,000 bit-vector array clauses, and one 10000-dimensional bit-vector array.  Then, my program takes as input k << 100,000 new clauses, and adds them to the core SMT problem.  My goal is, for any input of k clauses, to solve the entire problem.
Is there any static optimization or learning I could do on the core problem in order to find a better way to solve each of its siblings?  For instance, is there some property of the graph of bit-vector variables being constrained in each clause that I could use as a heuristic for solving the specific instances?
Thanks!


texts: Combining merge sort with insertion sort - Time complexity

texts:
I am learning algorithms from the CLRS book on my own, without any help. It has an exercise which combines merge sort {O(n log n)} with insertion sort {O($ n^{2} $)}. It says that when the sub-arrays in the merge-sorting reach a certain size "k", then it is better to use insertion sort for those sub-arrays instead of merge sort. The reason given is that the constant factors in insertion sort make it fast for small n. Can someone please explain this ?

It asks us to show that (n/k) sublists, each of length k, can be sorted by insertion sort in O(nk) worst-case time. I found from somewhere that the solution for this is O($ nk^{2}/n $) = O(nk). How do we get this part O($ nk^{2}/n $) ?

Thanks !


texts: How can I identify described structure within a directed graph

texts:
I am extending a gcc plug-in which should be able to detect branches within a loop, which can be run by speculation (run all branches in parallel and decide later what result to keep). The question is how to find the structures in the graph which are suitable.

For now the plug-in is only able to work with loops which have two branches like an if or and if/else construct.

Basically I am looking for structures within the graph which have a single entry and exit node.

I had the idea to look for strongly connected parts in the graph.

Another idea is to use dominator relations since they are already available in the current plug-in.

The question for both approaches would be: are these approaches necessary or sufficient conditions (if suitable at all)?

Also any hints on different approaches I could have a look it would be appreciated. (e.g. Is there a name for a structure which can only be entered through a single node and exited through another?)


texts: Hough transform: difference in cartesian to polar equation

texts:
According to Wikipedia and most other resources on the internet, the relation between cartesian coordinate and polar coordinate parameters are described by the equation $x\cos{\theta}+y\sin{\theta}=d$.

However, the computer vision course in Udacity used $x\cos{\theta}-y\sin{\theta}=d$ instead, as shown in this short video https://youtu.be/2oGYGXJfjzw?t=4s.

What is the difference?


texts:
If P1<=P2 means P1 is reducible to p2,then which is true?

1 If P1 is RE But Not REC,P2 is also RE but not REC?

2.If P2 is RE But Not REC,P1 is also RE but not REC?

As per my knowledge,if P1 is undecidable then P2 is also undecidable,so if I consider this property,then as RE BUT NOT REC is also undecidable,then answer will be 1 is true.

Also I know if P2 is RE then P1 is also RE ,so as per this result,as RE BUT NOT REC is also RE,so 2 is true.

But AFAIK,both statements are not correct.Please help me with correct answer

Please clarify.


texts: Literature about a naive approach to graph isomorphism by inspecting polynomials of adjacency matrices

texts:
I describe an approach to graph isomorphism which probably has false positives, and I am curious whether there is literature indicating that it does not work.

Given two adjacency matrices $G, H$, an admittedly naive method of checking for isomorphism is to check whether for each row $u$ of $G$, there is a row $v$ of $G$ which is a permutation of row $u$, denoted by $G[u] \sim H[v]$. Slightly more strict is the question, is there a "local isomorphism" $\pi$ for which $G[u] \sim H[\pi(u)]$ for all rows. Producing a local isomorphism can be done in polynomial time by building an $n\times n$ matrix $A$ with $A[u,v] = (G[u]\sim H[v])$; then $G$ and $H$ are locally isomorphic iff $A$ has a cycle cover, and every cycle cover is a local isomorphism.

All regular graphs fool this method, obviously, so a slightly less naive approach is to compute powers $G^2, H^2, G^3, H^3,\ldots$ of the matrices and checking them for local isomorphism, exploiting the fact that you have multiple matrices by setting $A[u,v] = 0$ when you find any power such that $G^k[u]\not\sim H^k[v]$, and checking for cycle cover only at the end. An even less naive approach is to find a set of polynomials, indeed a set of arithmetic circuits, and setting $A[u,v]=0$ when we find any polynomial $p$ with $p(G)[u]\not\sim p(H)[v]$.

This looks to me like an incredibly naive approach to graph isomorphism, so I am sure somebody has already investigated it and proved a theorem such as

Thm For infinitely many $n$ there are nonisomorphic $n\times n$ matrices $G, H$ and a permutation $\pi$ such that for every polynomial $p$, $p(G)$ and $p(H)$ are locally isomorphic by that permutation: $p(G)\overset{\pi}{\sim}p(H)$.

Question: Is there such a theorem? I have looked in the literature and cannot find it.

If there is a bound on the degree $k$ that is polynomial in $n$ such that for every two nonisomorphic matrices, local isomorphism is refuted by computing $G^1, H^1, \ldots, G^{poly(n)}, H^{poly(n)}$, or if there is an easily computable family of polynomials $p_1, \ldots ,p_k$, each having polynomially-bounded length but possibly exponential degree, then we have a P algorithm for graph isomorphism. If such polynomials (or arithmetic circuits) are easy to guess, then we have a coRP algorithm. If there always exists a (family of) arithmetic circuits to witness non local isomorphism, then this gives a coNP algorithm.

Note that we can avoid the problem that the entries of high-power matrices grow too large by computing the polynomials over small fields, e.g. by computing them modulo small primes. In a coNP algorithm, the prover can provide these primes.


texts: Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)?

texts:
My book states that the language
$$L_1 = \{a^nb^n\mid n\geq 1\}$$
is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really imagine how this grammar should not be applicable or why it shouldn't be a valid type 3 grammar:
$$S \to aS \mid bS \mid b\,.$$

For my understanding this grammar produces the language in question and also fulfils the type 3 criteria.


texts: Are there practical usage of determinants in numerical simulation?

texts:
I know the historical importance of the link between linear systems and determinants. I also know that determinants have a beautiful connection with non-singular matrices, i.e., if a matrix is non-singular its determinant is not zero. Furthermore, determinants can be used to characterize the critical points of a $C^2$ function. However, it seems that determinants are not used in these situations anymore at least in numerical computation.

Are there practical situations that determinants are still used in numerical simulation?


texts: Data structure for a quantity to price multiplier table

texts:
Yesterday at work I came across an interesting problem that I wasn't able to figure how to structure properly. I'm relatively new to the field and was wondering if I could get some help around here.
What i have here is a table like this:

          |1-2| 3-5 | 6+ | ($)
          ________________
          |              |
10 - 100  | x9   x6   x4 |
          |              |
100 - 2000| x5   x3   x2 |
          |______________|

Where the columns shows the base price and the row shows the quantity.
The idea here is that the bigger quantity you buy, the better the price. Not only that but we would also reduce the multiplier to items with bigger base price, because otherwise the price could become too high too quickly.

The outcome I want to achieve is when given two variables - base price and quantity to find where I'm standing in the table. This means for each table entry I need two ranges.

Let me give some examples:

Base price: 1.5$
Quantity: 200
Result: x5 (multiplier)

So the actual price will be 7.5$

Base price: 10$
Quantity: 15
Result: x4

So the actual price will be 40$

How would you remember the data and how would you write something flexible and scalable so one is able to add and remove table rows easily?

I would evaluate the answers based on how clean the solution is. And by clean I mean easy to use and easy to implement. Currently in our system this table is made from 20 if statements so anything would be better I think!


texts: Is the complement of a Max Prefix Sum a Min Suffix Sum?

texts:
Given an array A of n real numbers, are the maximum prefix sum and minimum suffix sum (and vice-versa) of A complements?

I.e. Given A[1..n] and its maximum prefix subarray P[1..i], is its minimum suffix subarray S[j..n] where i+1 = j?

Or stated another way, is sum(A) = maxPrefixSum(A) + minSuffixSum(A) true?

For an array of only negative numbers, let's assume that P is empty and maxPrefixSum(A) = 0.  Similar logic applies in the opposite case.


texts: Slowdown in making nondeterministic Turing machines deterministic

texts:
For every nondeterministic Turing machine, must there exist an equivalent deterministic one that runs in no more than twice the time?
Why or why not?
Can anyone explain?


texts: Can I encode a graph in a unary alphabet

texts:
For a graph $G=(V,E)$, I build an adjacency matrix and encode it into binary, clearly.

Now, imagine the alphabet I am given is $\Sigma=\{1\}$, is there a way for me to encode any graph instance with such alphabet?

In my reasoning, I think you can, since if you can map any binary string, to a unary string, then you can transitively mapping one adjacency matrix to a unary string, hence a graph. Does this reasoning have any flaw? Is this a valid argument?


texts: how to express an intertemporal implication constraint in integer linear programming (ILP)?

texts:
I want to express the following locigal expression in an IP:

$$x_{di} \wedge x_{d'j} \Rightarrow \sum_{\substack{d'' \in D\\ i < k <j}} x_{d''k} = \sum_{i<k<j} a_{k} \ \forall \ d, d' \in D, i,j \in T, i<j$$

where $x_{dt}$ is a binary decision variable ($x_{dt} \in \{0,1\}$) and $a_{k}$ is a binary parameter.

The meaning should be as follows: $T$ represents a set of timeslots. Whenever something happens at timeslots $i$ and $j$ (i.e. $x_{di} = 1$ for some $d$, $x_{d'j} = 1$ for some $d'$, $i<j$), then there should also something be happening at all timeslots inbetween $i$ and $j$, but only if at timeslot $t$ something can actually happen ($a_t = 1$, otherwise $a_t$ is $0$).

Can anyone tell me how to do this? Thanks in advance!


texts: Determine in which class $L=\big\{\langle M_1,M_2,w\rangle\mid M_1,M_2\text{ are TM and }L(M_1)\cap L(M_2)=\{w\}\big\}$

texts:
my solution is that $L\in co-RE$ by showing that $\overline{L}\in RE$

TM $M$ on input:$\langle M_1,M_2,w\rangle$

Build TM $M_1,M_2$
Simulate $M_1$ on $x\in\Sigma^*$, before that check if $x\neq w$
If $M_1$ accepts some $x$, than Simulate $M_2$ on $x$
If $M_2$ accepts than $M$ accepts. If $M_2$ reject, that we back at $M_1$ on the next $x$

$* $ $M_1$ and $M_2$ will run on each $x$ at the most $|x|$ steps.

Is that correct?

Thanks.


texts: Can counting problems have optimal substructure?

texts:
I understand that for a problem to be solvable using dynamic programming, it needs to have the following properties:

optimal substructure
overlapping subproblems

I stumbled upon an article which states that:

  Counting problems cannot exhibit optimal substructure, because they are not optimization problems. Instead, the kinds of counting problems that are amenable to DP solutions exhibit a different kind of substructure, which we shall term disjoint and exhaustive substructure.

Is this a valid claim? The Wikipedia article on Dynamic Programming states that:

  In addition to finding optimal solutions to some problems, dynamic programming can also be used for counting the number of solutions...

This implies that counting problems can have optimal substructure. I'm confused about what the PEG article is trying to say. I've also been unable to find information on this concept of disjoint and exhaustive substructure. My guess is that PEG is being a bit pedantic and the concept of optimal substructure only makes sense in the context of optimisation problems. You can't have an optimal count, there is just one correct answer. By disjoint we mean that we're interested in subproblems where solutions don't overlap (in order to avoid duplicates, we only want to count each unique combination once) and exhaustive means we want to count all possible unique combinations.

I thought I have a reasonable understanding of dynamic programming but reading this has confused me so essentially I'm looking for clarification.

Edit:
I've found another article on this which looks useful but I'm struggling to understand the proof provided for optimal substructure. I also can't find any information on what weak ordering has to do with dynamic programming and optimal substructure.


texts: Are there programs that can 'translate' source code between any two languages?

texts:
Are there programs that can 'translate' source code between any two languages (assuming the translator has access to the requisite libraries)?

If there are, how do they work (techniques used, knowledge required, etc)? How would they feasibly be constructed?

If they aren't, what are the restrictions preventing their development? Is this an A.I complete problem (natural language translation is listed as one)?

EDIT
Conversion is only expected, when the language has the same expression power, can solve the same kind of problems and the code to be converted can be expressed in the destination language. (E.g conversion from a shell script to MATLAB isn't expected).


texts: Hamming Weight to find the sum of 1 bits in the range between A and B inclusive

texts:
I am trying to find the sum of 1 bits in the range between A and B inclusive,

where -2^31 <= A <= B <= 2^31 - 1

Input Format:

The first line contains the number of test cases T (<=1000). Each of the next T lines contains two integers A and B.

I have used Hamming Weight algorithm to solve this problem. Though I have used memoization version of Hammnig Weight algorithm, it runs out of time.

mf = [-1 for i in range(65536)]

def count_1s(x):
    """It counts the number of 1 bits in an given 32 bit integer"""
    if (x > 65535):
        return count_1s(x&0xFFFF) + count_1s(x>>16)
    elif (mf[x] != -1):
        return mf[x]
    else:
        count = 0
        while(x > 0):
            x &= (x-1)
            count += 1
        mf[x] = count
        return mf[x]

t = int(input())

for i in range(t):
    a = [int(number) for number in input().split()]
    count = 0

    for j in range(a[0], a[1]+1):
        if (j < 0):
            count += 32 - count_1s(-j-1)
        else:
            count += count_1s(j)

    print(count)

So I am in a need of improving this algorithm. Are there any ways to improve this algorithm? or I should use some other algorithm to solve this problem?

Link for Input:

https://hr-testcases.s3.amazonaws.com/56/input02.txt?AWSAccessKeyId=AKIAINGOTNJCTGAUP7NA&Expires=1416339544&Signature=5bf736TpbPUWcQZ%2FbGijtBHbVeM%3D&response-content-type=text%2Fplain

Required Output:

https://hr-testcases.s3.amazonaws.com/56/output02.txt?AWSAccessKeyId=AKIAINGOTNJCTGAUP7NA&Expires=1416339722&Signature=NUwWGdUVsvttRWx0janzsxncDtY%3D&response-content-type=text%2Fplain


texts: How do contemporary processors differ from a pure von Neumann architecture?

texts:
So I never really understood the von Neumann architecture, and have started to revise it as I wasn't in school during the lessons of the CPU. Can't really get help through my teacher as they wont respond to their email.

I have learnt about the von Neumann architecture, and now I need to know how the architecture differs from a contemporary processor.

I know that contemporary processors sometime use a mixture of Harvard and von Neumann architecture by using Harvard for the communication between the control unit and caches though for cost effective reasons von Neumann is used between the main memory and cpu.

The specification point wants to know how it differs though, and I will be very thankful for any responses that might answer the question.

Thanks!


texts: Counting subarrays that satisfy either of two conditions

texts:
We have an array of integers $a[]$, with each $|a[i]| \leq 10^{6}$, $size(a)\leq10^{5}$, and $a[i]-a[i-1]\leq100$.

Then we define the term range as a subarray $[x,y]$ of the array $a[]$,  $x \lt y$.

We need to find total number of ranges that satisfy the property that for two given ranges $([x_{1},y_{1}]$ and $[x_{2},y_{2}])$ either one or more of the below conditions are true:

1) $(y_{1} – x_{1} \neq y_{2} – x_{2})$

2) $a[x_{1}+k] – a[x_{1}+k-1] \neq a[x_{2}+k] – a[x_{2}+k–1]$ for some $k \in \{1, 2, ... y_{1}-x_{1}\}$.

How can we visualize this problem? Is this related to some classical problem?


texts:
What are the problems that are in co-NP but not in NP?

i.e, those problems where incorrect strings can be deterministically verified in polynomial time but the correct strings can't be.


texts: Is there any polytime reduction from feedback vertex set to vertex cover?

texts:
I know that feedback vertex set (FVS) problem is $\mathrm{NP}$-complete since there is a simple and nice polytime reduction from vertex cover (VC) problem to FVS.
Specifically, given a undirected graph $G$, we construct $G'$ as follow:

For every $uv \in E(G)$, we construct a new vertex $e_{uv}$, and let $V_{0} = \{ e_{uv} : uv \in E(G) \}$.
Let $V(G') = V(G) \cup V_{0}$
All the edges in $E(G)$ are in $E(G')$. As for $e_{uv} \in V_{0}$, $u,v$ are two endpoints of it, the two edges $ue_{uv}, ve_{uv}$ are both in $E(G')$. Namely, $E(G') = E(G) \cup \{ ue_{uv}, ve_{uv} : e_{uv} \in V_{0} \}$.

It is easy to see that $G$ has a vertex cover of size at most $k$ iff $G'$ has a feedback vertex set of size at most $k$. Namely, $FVS(G') = VC(G)$.
Of course, there is a polytime reduction from FVS to VC. I want to know whether there is a reduction with a simple construction. And I hope that the size of the vertex cover and the size of feedback vertex set are equalent, if possible.
Formally, assume there is a polytime reduction $\mathcal{A}$ from FVS to VC, and $G'$ is an instance of the FVS problem, $G = \mathcal{A}(G')$.
Suppose $$VC(\mathcal{A}(G')) = VC(G) = f(FVS(G'))$$
I want that $f$ is as small as possible.
Any related result is helpful. Let $k = FVS(G')$, it is unlike that $f = O(k)$, what about $O(k^2)$ or $O(k \log k)$? What if we restrict the the graph is planar (Note that the reduction from VC to FVS works for the planar version)?


texts: Parallel or efficient computation of value with momentum

texts:
I have a matrix $A$ with dimensions $M \times N$ and I want to compute $A'$ such that:

$$
A'_{i,j} = \alpha A'_{i,j-1} + (1 - \alpha) A_{i,j} \\
1 \leq i \leq M, 1 \leq j \leq N, \alpha \in [0, 1]
$$

Where $A'_{i,0}$ is some given constant.

I want to perform this computation as part of a machine learning training process on the GPU (I am using TensorFlow), but the only way to do it I can think of is with a loop over $j$, which makes the training tremendously slower (even if it's a TensorFlow loop, not a regular Python loop).

I know that being each value dependant on the previous one this is not a parallel-friendly computation, but I was wondering if there is some trick or reformulation that I am missing to make this in a smarter way.


texts: Can one quickly update CRC codes based on small change and previous CRC code?

texts:
I asked this on StackOverflow, but, alas, no answers.

I'd like to use CRC or similar codes to check whether certain very large objects are likely to be identical. The trouble is, small parts of these objects are sometimes modified, and it would be very inefficient to re-compute CRC code from the entire object. Think of multiple large images, pre-signed with CRC, and of a software the changes single pixels of some of those images and updating those images' CRCs.

Is it possible to re-compute CRC based on: previous CRC value, location of the changed byte, old value of that byte, and the new value of that byte?

If not, what signature scheme would allow that?


texts: What do we benefit from using ternary search trees rather than binary search trees?

texts:
Ternary search trees are very common in the text editing area. They could be used to implement Auto complete feature, spell checking, Partial-Match searching, Near-Neighbor Searching & many many other options.
The reason behind them being famous is their space efficiency compared to tries (Although tries are faster) & their flexibility (Compared to Hashtables).
Ternary search trees have three pointers in their data node : lokid the left kid, hikid the right kid & midkid the middle kid.
The thing that I'm missing is why do we need the middle kid ? What is the particularity of this pointer ? In which things it would be better to have that pointer rather than not having it at all ?
I was drawing some trees & i think we can realize the same thing using only 2 pointers (A binary search tree) with insertions going to the left kid if current character in the string to insert is equal or less than the character on the current node and insertions going to the right the other way around.

The following picture shows a binary tree generated from inserting words: KARIM, KARAS, SARAS.

The insertion algorithm of the above tree could be something similar to the following pseudo code :

insert(root, word){

    if(!root) {
        root = new node()
        root->char = *(word++)
    }

    if(*word > root->char)
        insert(root->right, word)

    else {
        if(*word == root->char)
            insert(root->left, word++)
        else
            insert(root->left, word)

    }
}

What could possibly be wrong with the above conception ? Am i missing something about the ternary trees which makes them superior to binary trees ?


texts:
If we have some collection of decision trees with single-variable splits and a constant value at each leaf node, the average over all trees gives some function from $\mathbb{R}^n \to \mathbb{R}$. Is it possible to efficiently find the subspace on which this function achieves its maximum? Enumerating all intersections could take exponential time in e.g. the case where each tree is a stump which bisects a different dimension.

It is possible to do better by computing bounds and doing some pruning, but I wonder whether a polynomial-time solution is possible.

If the leaf values are taken from $\{0, 1\}$ then this is a restricted max-clique problem, but I suspect it should be possible to exploit the decision-tree structure to create a faster algorithm.

Any thoughts?


texts: Hanoi towers recursive expression for EVERY algorithm

texts:
What the recursive algorithm for moving $n$ disks says, is:

If $n > 1$, move $n-1$ discs from A to B.
Move the $n$th disk from A to C.
If $n > 1$, move $n-1$ discs from B to C.

Let $T_n$ be the number of moves for moving n disks.

We have
$
T_n=2T_{n-1}+1 , T_1=1 $, so $T_n=2^n-1, n \geq 1 $

  Is it correct to say that for every algorithm solving the Hanoi Towers problem, it is true that
  $$
T_n=2T_{n-1}+c
$$
  So we would need to know $c$ (number of moves for moving the last disk from A to C) and some other $T_i$, in order to  calculate $T_ n$ for every $n$.

Thank you in advance


texts: Priority Queue - When Prioritizing Take Place?

texts:
In a Priority Queue we first enqueue according to the priority given to the element? Or we enqueue just like a queue but dequeue high the highest priority element first?
Or both ways are acceptable?


texts: I'm trying to prove this language is not context-free: {a^x b^y c^z | where x=z and x<y}

texts: So far i've tried with making x = z = p and y = 2*p, but it seems that if I place vxy to represent all b's then I can't get a contradiction.


texts: Why Does The Division Alorithim Need [Register Size] + 1 Iterations

texts:
Following this flow diagram for division hardware I made a program to "simulate" division on $N^+$.

# 4 bit version
def div(dividend, divisor)
  quotient = 0
  remainder = dividend
  divisor <<= 4

  for i in 1..5
    remainder -= divisor
    if remainder >= 0
      quotient <<= 1
      quotient |= 1
    else
      remainder += divisor
      quotient <<= 1
    end
    divisor >>= 1
  end

  return quotient
end

What I don't understand is why there needs to be an "extra" iteration of the loop. If the divisor is being shifted down the register by 1, and the register is say 64 bits, then it would take 64 iterations to clear the register. Or in my case 4. However without that extra step the algorithm does not produce the correct result. Why is that?


texts: Why can the alphabet be represented in numbers in base 256

texts:
This is in context of hashing of strings. I'm not sure why a string like, CS, could be represented as CS = 'c'*256 + 's'

Does anyone know about this?


texts: Defunctionalization is a transformation first described 1972 by John C. Reynolds to eliminate higher-order functions. Are there alternative transformations (more efficient?) to eliminate higher-order functions?


texts:
I am reading parser chapter from dragon book and I found a grammar over there -

$ S \rightarrow L=R $

$ S \rightarrow R $

$L \rightarrow *R $

$L \rightarrow id $

$R \rightarrow L $

Now I have created some of its items, not sure if they are correct -

$ I_{0} $

$S' \rightarrow .S  ; \$ $

$S \rightarrow .L=R ; \$ $

$S \rightarrow .R ; \$ $

$ L \rightarrow .*R; \$/= $

$ L \rightarrow .id; \$/= $

$ R \rightarrow .L; \$ $

$ I_{1} $

$ S' \rightarrow S.; \$ $

$ I_{2} $

$S \rightarrow L.=R ; \$ $

$ R \rightarrow L.; \$ $

Now I2 contains Shift reduce conflict but the lookahead symbol that is appearing is creating doubt I mean how $ can be lookahead symbol to shift = sign?


texts: Ullman's algorithm for subgraph isomorphism

texts:
I was trying to code the Ullman subgraph isomorphism agorithm. With respect to the Ullman subgraph isomorphism, there are two matrices, M and M'. How is M' being formed from M?

  Matrices M' are generated by systematically changing to 0 all but one of the l's in each of the rows of 0 M, subject to the definitory condition that no column of a matrix M' may contain more than one 1.

Now what i am not able to understand this line. They have said convert all elements to zero except one 1 and also each column must not have more than one 1. In order to make each column contain only one 1, more than one 1 needs to be changed to zero right? In short can anyone explain these lines clearly with an example?


texts:
Is there a rule that either every DFA contains or not, a loop(cycle in graph terminology)?

I do not seem to be able to generalize this idea in either direction.

Also if either of these is true, can we assume through DFA - NFA equivalence that the same is true for NFAs?


texts: Can anyone find a mapping from the set of all possible string to the natural numbers?

texts:
Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$?

$$h : S^* \rightarrow \mathbb{N} $$

Assume $S$ is finite. I would prefer an efficient map.

There should be nice applications of this question for perfect hashing, right?


texts: Does an ADT have multiple or only one representations/implementations?

texts:
Section 24.2  in Types and Programming Languages by Pierce defines ADTs in existential types:

  A conventional abstract data type (or ADT) consists of (1) a type name A, (2) a concrete representation type T, (3) implementations of
  some operations for creating, querying, and manipulating values of
  type T, and (4) an abstraction boundary enclosing the representation
  and operations. Inside this boundary, elements of the type are viewed
  concretely (with type T). Outside, they are viewed abstractly, with
  type A. Values of type A may be passed around, stored in data
  structures, etc., but not directly examined or changed—the only
  operations allowed on A are those provided by the ADT. ... We ﬁrst
  create an existential package containing the internals of the ADT:

counterADT =
{*Nat,
{new = 1,
get = λi:Nat. i,
inc = λi:Nat. succ(i)}}
as {∃Counter,
{new: Counter,
get: Counter→Nat,
inc: Counter→Counter}};

> counterADT : {∃Counter,
{new:Counter,get:Counter→Nat,inc:Counter→Counter}}

  We can open it for example

let {Counter,counter} = counterADT in
counter.get (counter.inc counter.new);
> 2 : Nat

Does the highlighted sentence in the following quote say that a ADT can have multiple representations/implementations?

  A key property of the kind of information hiding we are doing here is
  representation independence. We can substitute an alternative
  implementation of the Counter ADT—for example, one where the
  internal representation is a record containing a Nat rather than just
  a single Nat,

counterADT =
{*{x:Nat},
{new = {x=1},
get = λi:{x:Nat}. i.x,
inc = λi:{x:Nat}. {x=succ(i.x)}}}
as {∃Counter,
{new: Counter, get: Counter→Nat, inc: Counter→Counter}};

> counterADT : {∃Counter,
{new:Counter,get:Counter→Nat,inc:Counter→Counter}}

  in complete conﬁdence that the whole program will remain typesafe,
  since we are guaranteed that the rest of the program cannot access
  instances of Counter except using get and inc.

Do the highlighted sentences in the following two quotes say that an ADT can have only one representation/implementation?

On p377:

  In summary, the single representations of ADTs directly support
  binary operations, while the multiple representations of objects give
  up binary meth- ods in return for useful ﬂexibility. These advantages
  are complementary; nei- ther style dominates the other.

From a reply to my previous question:

  ADTs are entirely public about their unique representation. Belonging in the ADT means satisfying said representation, and so binary methods can rightfully assume that both operands have that exact representation.

Why is the inconsistency?

Thanks.