texts: Algorithm to generate integer sets fulfills restrictions

texts:
I'm trying to solve the following problem.

Input

positive integers $v$, $b$ and $\ell$. ($\ell\leq v\leq b\ell$.)

Output

A list $S_1, \dots, S_k$ of all possible integer multisets (a generalization of the concept of a set that, unlike a set, allows multiple instances of the multiset's elements), such that each $S_i$ fulfills following constraints:

$|S_i|=\ell$
$\sum_{s\in S_i}s=v$
for all $s\in S_i$, $s\in \{1, \dots, b\}$

For example, a solution to the instance $v=4$, $b=4$, $\ell=2$, is $[\{1,3\},\{2,2\}]$.

For now I have a recursive function working to give something not exactly the same as what I'm expecting. For the input above, it returns $[\{1,3\},\{2,2\},\{3,1\}]$. I know I can use extra steps to eliminate the duplicates but I'm wondering if there's a mathematical formula I can use? Or some other algorithm acts smarter?

Below is my code:

public static List<List<Integer>> getIntegerSets(int v, int base, int l) {
    if (v < l || l <= 0) return null;
    List<List<Integer>> result = new ArrayList<>();
    if (l == 1) {
        if (v > base) return null;
        List set = new ArrayList<Integer>();
        set.add(v);
        result.add(set);
    } else {
        for (int i = Math.min(base, l * v); i > 0; i--) {
            List<List<Integer>> list = getIntegerSets(v - i, base, l - 1);
            if (list == null) continue;
            for (List<Integer> subset : list) {
                subset.add(0, i);
                result.add(subset);
            }
        }
    }
    return result;
}

Another extended problem is, can we (use another algorithm) directly get the size of the list, which is the $k$ value, with or without duplicates, perfectly both, without executing this very function?


texts:
I need to prove that the following language is in $\mathsf{P}$:
$$ L = \{\langle x,y,z,d \rangle : xˆy \equiv z \pmod{d}\}.$$

I'm assuming I just have to prove with an algorithm or negate that it's part of NP. But I don't know how to do it with this mathematical formula.


texts: Difference between BSP model and synchronous round model in distributed computing

texts:
I've recently learned about distributed computing and the synchronous model where, assuming  a complete network and no crashes, in each round the following happens:

every node can send a message to all other nodes,
all of these messages are received by all nodes by the end of the current round, and
at the start of the next round, every node performs some local computation (taking into account received messages).

It seems to me that this model is a more specific variant of the classic BSP model of Valiant where the cost of the barrier synchronization and the local computation is ignored.

Am I missing something else that distinguishes the distributed model from the BSP model?


texts: How can it be detected that a number generator is not really random?

texts: I heard that random number generation in computers isn't really random, but there is no efficient algorithm to detect it. How can it be detected at all ?


texts: In the usb protocol a frame is send every 1msec to the device, if the host asks the device for data, how does the device send data to the host? Does it use a frame?


texts: Reachability queries on a tree in $O(1)$ time with $O(n+m)$ time preprocessing

texts:
I am given an undirected tree $T$ in the usual graph theoretic sense. Given a vertex $v$ and an edge $(v,u)$ incident to $v$, I need to answer queries of the form return any leaf of $T$ that is reachable from $v$ with a path including $(u,v)$, and no other edges incident to $v$? More informally, the restriction is that when the edge is given, we can only proceed in to that direction.

I can simply perform a DFS and return a leaf found. I think this would take $O(d)$ time, where $d$ is the diameter of $T$. However, I'd like to answer a query in $O(1)$ time. Moreover, I'd only like to allow linear preprocessing time. My idea for achieving this was to use a DFS, label leaves, and then label edges when the search backtracks. This idea might work with some additional effort, but I'm really unsure about the details.

"Graph reachability" turned up some results, but maybe they are dealing with more complex problems. I'm happy with any method that uses $O(n+m)$ preprocessing time and answers the queries in $O(1)$ time.


texts: Is there a way of objectively measuring the efficiency or quality of software or code design?

texts:
I've been thinking about ways of measuring code, and, quite frankly, I can't think of truly objective, semi-universal ways of evaluating the quality or "strength" of code to say, "Yes, this is better than that based on X, Y, and Z metrics" that are popular or exist. I've looked at SonarQube, and although I think their metrics are important, I feel like there are more fundamental concepts at work than what they have now.

But, of course, it's often said that certain languages are better than others because they have stronger guarantees or abstractions: C++ > C with abstraction, and Haskell > C++ with typing and purity and a whole slew of other features. But I was wondering whether it would be possible to actually quantify how much better one is than the other.

Are there existing papers that talk about ways of objective comparing coding paradigms or languages based on objective metrics?

A few of the resources I've found while search have to do with more business-y metrics like cost of quality or coverage of unit tests over development time. Also, measuring by number of lines seems fishy and not truly crucial (imagine if we measured math proofs' qualities by how many pages of paper it takes to print!):

http://www.infosys.com/engineering-services/white-papers/Documents/comprehensive-metrics-model.pdf
http://www.compaid.com/caiinternet/ezine/Gack-Effectiveness.pdf
http://www.compaid.com/caiinternet/ezine/Gack-Efficiency.pdf

Apparently the list of top 10 papers are also not based on measuring the efficiency of design in code, but are more focused on specific areas:

http://blog.mendeley.com/highlighting-research/the-top-10-research-papers-in-computer-science-by-mendeley-readership/


texts:
I need to detect whether a binary pattern $P$ of length $m$ occurs in a binary text $T$ of length $n$ where $m < n$.

I want to state an algorithm that runs in time $O(n)$ where we assume that arithmetic operations on $O(\log_2 n)$ bit numbers can be executed in constant time. The algorithm should accept with probability $1$ whenever $P$ is a substring of $T$ and reject with probability of at least $1 - \frac{1}{n}$ otherwise.

I think fingerprinting could help here. But I can't get it.


texts: Why if for any computable function f(n) that is less than n, then Time Hierarchy Theorem wouldn't hold?

texts:
First let's have some definition (you can find these in any complexity's textbook)

Theorem. [Gap Theorem] There is a computable time bound $t(n)$ such that DTIME[ $t(n)$ ]= DTIME[ $r(t(n))$ ] for any computable function $r$.

This theorem says that even if you have more time resources, then you cannot do more. We have another theorem that says.

Theorem. [Time Hierarchy Theorem (THT)] if f and g are time-constructible functions and f(n)=o(g(n)), then DTIME[ $f(n)$ ] $\subsetneq$ DTIME[ $g(n)$ ].

It is clear that if $f$ and $g$ are not time-constructible, then THT wouldn't hold. Time-constructible ensures that we read the whole input in the input tape of the TM.
Question: If $f$ and $g$ are not time-constructible, why then THT cannot hold? What makes THT cannot hold even if f and g are not time-constructible?
Thanks


texts: Number of FLOPs (floating point operations) for exponentiation

texts:
What is the number of floating point operations needed to perform exponentiation (power of)?

Assuming multiplication of two floats use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this? How does it work if $n$ isn't an integer?


texts: Can you take classical code and compile it to quantum code?

texts:
Is there anyway for example, to take a trivial program from C such as:

int main() {
  int i = 1 + 1;
  return 0;
}

And compile this down to some form of Quantum Abstract High-level language, i.e. Quantum C?

From what I understand, quantum arithmetic is quite tricky business that uses QFTs. My first thought was to do the following for the example above:

Initialise two qubits and set the amplitudes like following:
$$ 0|1|0|0$$

Where 0100 = 2 in decimal.

Somehow return this quantum register.

Using the amplitudes, you could perform 32-bit arithmetic with 32 qubits?

I haven't answered the notion of creating a function or returning either.

Essentially what I'm asking is the following, can we take known quantum methods (using Unitary functions to perform calculation) and apply this to classical code and if so, how?

EDIT: I've looked further and seen a few papers on Quantum Full Adders, I assume this is the way to go for addition? Is this too much? In quantum computation books that describe quantum assembly, there is not much mention of addition.


texts: Termination proof and complexity of a algorithm

texts:
I have written the following algorithm

$select(\Pi)$ select the first elements from $\Pi$. When there are no element in $\Pi$, it return $\emptyset$. Always terminates .Worst case complexity $O(1)$
$processing(e)$ function take a element $e$ as input and process it. And based on the processing it either output element $r$ or $\emptyset$. Always terminates. Complexity not known.
$update(r,\Pi,\Delta)$ function take $r,\Pi,\Delta$ as input and update criteria in the function. And based new criteria, it transfer already processing element from $\Delta$ to $\Pi$. Always terminates. Worst case complexity $O(sizeof(\Pi+\Delta))$

$\textbf{Input} - \textbf{a set of elements $\Pi$}$

$\textbf{Output} - \textbf{a set of elements $C$}$

$C$=$\emptyset$;

$\Delta$=$\emptyset$;

$e$=$select(\Pi)$;

$\textbf{While}$($e \not=\emptyset$){

$\hspace{10mm}r$=$processing(e)$;

$\hspace{10mm}\textbf{if}$($r \not=\emptyset$){

$\hspace{20mm} C$=$C\cup r$;

$\hspace{20mm} \Pi$=$\Pi-e$;

$\hspace{20mm} \Pi,\Delta$=$update(r,\Pi,\Delta)$;

$\hspace{10mm}\}\textbf{else}${

$\hspace{20mm} \Pi$=$\Pi-e$;

$\hspace{20mm} \Delta$=$\Delta\cup e$;

$\hspace{10mm}$}

$\hspace{10mm}e$=$select(\Pi)$;

}

$\textbf{return}$ $C$;

Proof Sketch ----
The termination condition of the algorithm - when $\Pi$ is $\emptyset$.
Each iteration of the loop involves a $processing$ call which always terminates. Because $processing$ does not return any results for 10 seconds, then algorithm terminates the $processing$ call and return $\emptyset$.  We can say that the algorithm always terminates since the size of $\Pi$ and $\Delta$ move in a monotone way up and down respectively, and one always moves. Thus, eventually $\Pi$ become empty and the algorithm terminates.

Can anyone please suggest to me how I can formally complete the proof?

Can anyone please suggest how we can compute the worst case complexity as we do not know the complexity of the $processing$ function? How we can use Oracle for $processing$ function in that process?


texts: "Programing in goals" as an alternative to defining APIs (from B. Victor's talk The Future of Programming )

texts:
In his talk The Future of Programming, in the third section of the talk about "programming using goals", Bret Victor says this:

  https://vimeo.com/71278954 [15:20]

  What won't work, what would be a total disaster, is---I'm gonna make up a term here---an API. This notion that you have a human
  programmer that writes against a fixed interface, that's exposed by
  some remote program. First of all, this requires the programs to
  already know about each other, right? And when you are writing a
  program in this one's language, now they're tied together, so the
  first program can go out and hunt and find other programs that
  implement the same service they're tied together. If this one's
  language changes it breaks this one. That is really brittle, it
  doesn't scale and worst of all you have... It is basically the machine
  code problem. You have a human doing low-level details that should be
  taken care of by the machine. So I'm pretty confident this will never
  happen. We are not gonna have APIs in the future. We are gonna have is
  programs that know how to figure out how to talk to each other and
  that's going to require programming in goals.

The talk is themed as a 1970's scientists view of the idyllic future, building upon and extending contemporary research ideas. Yet I found no references to research regarding this API bashing part. There is an accompanying website to the talk, which, for some reason, has absolutely no further references either.

I wish to know whether the idea of replacing APIs with "something better that does not take so much human time to work with" is something grounded in actual research, or it is an improbable wish, or if there are reasons it is impossible (I think it is).


texts: Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?

texts:
From this statement

  As there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, thus there must exist an undecidable language.

I would like to understand why similar reasoning does not work with a finite set $B$ which also has no surjection onto $\mathcal{P}(B)$!  (with $|B|=K$ and $K \in \mathbb{N}$)

Why is there a minimum need for the infinite set?

EDIT Note:

Although I chose an answer, many answers and all comments are important.


texts: I've recently viewed the paper of AlphaGo, which has done gradient-based reinforcement learning to get stronger. The learning was successful enough to beat a human master, but in this case, supervised learning with a large database of master level human games was preceded the reinforcement learning. For a complex enough game as go, one can expect that the search space for the policy function would not be smooth at all. So supposedly supervised learning was necessary to guide the policy function to a good starting point before reinforcement. Without such, applying reinforcement learning directly to a random policy can easily make the policy stuck at a bad local optimum. I could have a miunderstanding at this point; correct me if so, but to continue on: if it is hard to have "the good starting point" such as a trained policy from human expert game records, what is a way to devise one. I've had a look on NEAT and HyperNEAT, which are evolutionary methods. Do these evolutionary algorithms scale well on complex strategic decision processes and not just on simple linear decisions such as food gathering and danger avoidance? In case not, what alternatives are known? Is there any success case of a chess, go, or any kind of complex strategic game playing algorithm, where it gained expert strength without domain knowledge such as expert game examples?


texts:
Show that $L = \{a^nb^l \ | \ n \leq l \}$ is not regular

I'd like to check if my proof for this is correct.

Proof: Choose any positive integer $m$. Pick $w = a^mb^{m+1} \in L$. Note that $|w| = 2m+1 \geq m$ and $1\leq |a^m| \leq m$. Write $w=xyz$ where $x=\varepsilon$, $y=a^m$ and $z=b^{m+1}$. We have
$$xy^3z= \varepsilon(a^m)^3b^{m+1} = a^{3m}b^{m+1} \not\in L\,,$$
since $3m > m+1$ for any positive integer $m$. Thus by the contrapositive of the Pumping Lemma we can conclude that $L$ is not regular. $\square$

Although we normally close "check my work questions", this question illustrates a very common mistake with the pumping lemma, so is intended as a reference question.


texts: Partitioning planar graph cycles based on chords

texts:
Given a cycle of length > 3 in a planar graph, I'm looking to partition it into 4 sublists of length 2 or more such that:

No sublist contains two vertices with a chord between them
The last element in each sublist is the first element in the next
Every element in each sublist is adjacent to its neighbors in the original cycle
The difference in size between the sublists is kept minimal, given constraints 1 to 3

Overall I'm not really sure if this is required to be solved using graph structures, or if it's possible to transform it into something more general.


texts: Can you get O(n) with a word frequency algorithm?

texts:
By a word frequency algorithm:
An algorithm gets a document as an input, and returns each unique word along with the number of times it has appeared in the document.

For example:

in:"Hello my name is Hello"
out: {'Hello':2, 'is':1, 'my':1, 'name':1}

In my implementation, I used a hash table to store the words.

But I've seen uses of a trie, but I don't understand why this improves runtime.

I've read that you can get O(n). I assume with a trie correct?


texts: Branch and bound for minimum linear arrangement

texts:
I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost.

Let's say $G$ is a graph of $n$ nodes $\{1, 2, 3, \ldots , n\}$. For a permutation $f$ of the nodes of $G$, the  weight  of  each  edge $(x,y)$ will be $|f(x)-f(y)|$. The total weight of $G$ will be the sum of the weights of its edges.  You can think of $f$ as a relabeling of the nodes of $G$, where
$f(x)$ is the new label of node $x$.

I am trying to find a permutation $f$ that results in a minimum total weight of $G$.

Now trying to solve this, all I could come up with is finding the approximate cost that is the sum of weights of each edge completed till now (for each backtracking tree node) and proceed from the minimum cost node. I am wondering if someone can help me with a better approximation formula.


texts:
Im studying the semidecidability of First Order logic.

According to wiki

  A logical system is semidecidable if there is an effective method for
  generating theorems (and only theorems) such that every theorem will
  eventually be generated. This is different from decidability because
  in a semidecidable system there may be no effective procedure for
  checking that a formula is not a theorem

The semidecidability seems to me exactly equal to halting problem, which is NP-HARD.
1) Is it correct ?
2) So also First Order Logic is NP-HARD ?


texts: How does cycling happen in the simplex method?

texts:
I'm reading Schrijver's Theory of Linear and Integer Programming, and I have a problem understanding cycling happens in the simplex method. The simplex is described as below:

Solving $\max\{cx\mid x \geq 0; Ax \leq b\}$ At each stage a set $C_k$ is maintained, which consists of $n$ linearly independent equalities from $Ax = b$, such that $x_k$ the current vertex is determined by $C_kx_k = b_C$.

$u$ is the unique vector $u_kA = c$ where $u$ is zero in the components corresponding to equalities outside $C_k$. if $u \geq 0$ then $x_k$ is optimal. Otherwise we choose an index $i^*$ where $u_{i^*} <0$, $y$ is the unique vector such that $C_ky$ is zero in all components except $i^*$. Then $\lambda$ is defined as $\min\{\frac {b_t - (Ax_k)_t}{(Ay)_t}, (Ay)_t > 0\}$, where $t^*$ is the index acquiring the minimum. Now $x_{k+1}$ is calculated from $x_k + \lambda y$ and $C_{k+1} = C_k + t^* \setminus i^* $. Also notice $cy = uAy = -u_{i^*} > 0$ so $cx_{k+1} > cx_k$.

So the book explains when choosing $i^*$ and $t^*$ and there are several options, there are different methods for breaking ties, some of which may cause cycling that is the algorithm wouldn't terminate. Here is what I don't understand: given there are finitely many vertices and $cx_{k+1} > cx_k$ how is it possible to visit the same vertex twice hence encountering cycling??

Later, when the average time of Simplex method is being analyzed due to Borgwardt, the book explains cycling can happen only if the LP problem is degenerate. And provides a condition for being non-degenerate there is no set of $n$ linearly dependent rows in the matrix $\begin{bmatrix}c\\A\end{bmatrix}$ and there is no set of $n+1$ linearly dependent rows in $\begin{bmatrix}A &b\end{bmatrix}$. can you please explain why is this?


texts: 2-D peak finding complexity (MIT OCW 6.006)

texts:
In a recitation video for MIT OCW 6.006 at 43:30,
Given an $m \times n$ matrix $A$ with $m$ columns and $n$ rows, the 2-D peak finding algorithm, where a peak is any value greater than or equal to it's adjacent neighbors, was described as:
Note: If there is confusion in describing columns via $n$, I apologize, but this is how the recitation video describes it and I tried to be consistent with the video.  It confused me very much.

Pick the middle column $n/2$ // Has complexity $\Theta(1)$

Find the max value of column $n/2$ //Has complexity  $\Theta(m)$ because there are $m$ rows in a column

Check horiz. row neighbors of max value, if it is greater then a peak has been found, otherwise recurse with $T(n/2, m)$ //Has complexity $T(n/2,m)$

Then to evaluate the recursion, the recitation instructor says

$T(1,m) =  \Theta(m)$ because it finds the max value
$$ T(n,m) =  \Theta(1) +  \Theta(m) + T(n/2, m) \tag{E1}$$

I understand the next part, at 52:09 in the video, where he says to treat $m$ like a constant, since the number of rows never changes.  But I don't understand how that leads to the following product:
$$ T(n,m) = \Theta(m) \cdot \Theta(\log n) \tag{E2}$$
I think that, since $m$ is treated like a constant, it is thus treated like $\Theta(1)$ and eliminated in $(E1)$ above.  But I'm having a hard time making the jump to $(E2)$.  Is this because we are now considering the case of $T(n/2)$ with a constant $m$?
I think can "see" the overall idea is that a $\Theta(\log n)$ operation is performed, at worst, for m number of rows.  What I'm trying to figure out is how to describe the jump from $(E1)$ to $(E2)$ to someone else, i.e. gain real understanding.


texts: Expressing division in relational algebra in terms of other operations

texts:
So, I've been conferred upon the opinion that:

  Union, difference, cross product, selection, projection form the "complete set of relational operations".
  That is, any other relational operation can be expressed as a combination of these (excluding domain manipulation operations like aggregate functions I assume).

Question 1: Is that true ?

Question 2: If yes, can someone help me break down division in terms of those operations.


texts:
Problem to get the min. no. of swaps required for arranging pairs togethe.

There exists an array of size 2N with integers ranging from 0 to 2N-1 arranged at random. Each integer is paired with another
i.e. 0 paired with 1, 2 paired with 3,...2N-2 paired with 2N-1. What is the minimum number of swaps required to have
all pairs next to each other.
E.g. : [5,4,2,6,3,1,0,7] -> [5,4,2,3,0,1,6,7] Output 2 swaps needed

Solution: Greedy Approach

for i from 0 to 2N-2:
    if array[i] and array[i+1] does not constitute a pair:
        find the pair for the ith one and swap position with i+1 element

What is the proof for why the above greedy algorithm is optimal?


texts: Semidecidable properties of computable reals

texts:
By computable real I mean $x\in\mathbb{R}$ such that there is some computable total function $p_x$ that takes a natural number $n$ and returns a dyadic rational $r$ such that $|x-r|<2^{-n}$. I think this is probably equivalent to any other reasonable definition but I want to fix this to avoid ambiguity.

By a semi-decidable set $S$ of computable reals, I mean that there should be a program that, when given the Godel code for some $p_x$, halts exactly when $x\in S$.

One easy class of examples of semi-decidable sets of reals is given by open intervals $(a,b)$ where $a$ and $b$ are both computable.

Is it true that every semi-decidable set is open?

I think this should be true, essentially because if a computable process $P$ takes $p_x$ and then decides that $x\in S$, it must have done so using at most finitely many calls to $p_x$. But how do I know that $P$ did not do something sneaky by looking at the code for $p_x$? This should be impossible, but e.g. Rice's theorem does no apply directly because I am not assuming that $P$ decides some property of arbitrary programs, just those that happen to represent computable reals (and note that these are not even a r.e. set).


texts: Locate all locations in a sorted array where arr[i]<arr[i+1]

texts:
Suppose you are given an array of $n$ integers with duplicates in non-decreasing order. The goal is to find the locations where a value is different from its neighbor.
For example, given the array $arr={3,3,5,5,5,200,200,200,200,209}$, the output would be: ${2,5,9}$.
Obviously, this can be done in linear time. I am trying to improve upon this using a binary search.
Let $k$ be the number of output locations. In $O(k \log n)$ time we can get our answer. To find first location, check locations $2,4,8,$etc. Suppose you find that $arr[1]<arr[2^{j}$], recursively search the interval from $2^{j-1}$ to $2^j$-1.

My QUESTION: In the worst case, $k=O(n)$. I do NOT want to ever pay
$O(n \log n)$ since the naive algorithm is $O(n)$. However, I do not pay $O(n \log n)$ for $k=O(n)$ since the binary searches terminate in $O(1)$ time.
How do I prove that the algorithm is worst case $O(k \log n)$ when $k << n$ and never worse than $O(n)$?


texts: Sub-exponential for Subset Sum on the total bit length of the input

texts:
Was crawling the internet, and found this in a paper (1)

"[...], a variant of dynamic programming called
dynamic dynamic programming has been shown to have a worst-case sub-exponential time complexity of $2^{O(\sqrt x)}$ when the total bit length $x$ of the input set is used as the complexity parameter."

As I understand this claim violates the Exponential Time Hypothesis, and there has been some answers in the forum clearly stating no such sub-exponential algorithm exists, would be interesting to know what the experts in the area think about the proposed algorithm in terms of worst case complexity.

Direct link to the paper (2) explaining the dynamic dynamic approach.

(1) Thomas E. O’Neil -An Empirical Study of Algorithms for the Subset Sum Problem

(2) Thomas E. O’Neil, Scott Kerlin - A Simple $2^{O(\sqrt x)}$ Algorithm for PARTITION and SUBSET SUM


texts: How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem?

texts:
I know how to prove longest-path problem by reducing Hamiltonian Path problem.
Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-path problem is NP-hardness, not Hamiltonion Path problem)
I'm wondering if it is possible to reduce Hamiltonian Path problem to longest path problem.
Is there any way I can do that?


texts: How does reducing the Halting problem prove the reduction cannot exist?

texts:
For example, take the problem "Does M Halt on the Blank Tape?".

My approach was to reduce the halting problem to prove this problem is also undecidable. I generated a Mw by

Writing w on the tape
Moving to the leftmost blank
Running M

Then, of course there is the M-halt-on-blank function:

if(Mw halts)
    true
else false

Where I am having difficulty is understanding how this "proves" the halting problem. The halting problem is supposed to take in an input w and a machine M and tell if M halts on w. If we are creating Mw by taking w and modifying it, and running M on the modified tape, then M isn't really running on w at all. Instead, it is running on this modified tape. This would mean there is an infinite amount of w's that cannot even be run on M. So by using M-halt-on-blank as a decider, how is that solving the halting problem, and thus proving itself to be undecidable?

I understand there are a few similar posts but I am more concerned with the ends than the means for this problem, and I didn't find previous posts to answer this.


texts: Delivering to two or more locations in one go while respecting deadlines?

texts:
Assume that I have a business where people can place product orders. Each order must be delivered within a time limit, say $x$ minutes.
I need 15 minutes to make each product. However, multiple products can be made in parallel.

Assume that I know my storage (i.e., the products that were previously made and are stored), the products that are being made by the present time, and the product orders. I also have a complete weighted graph $G = (V, E)$ where the nodes are the delivery destinations and the edges are the time needed to travel between two nodes.

The problem is: How can I compute the maximum amount of products that I can deliver at multiple locations while respecting the deadline of $x$ minutes for all products?

Let's give an example. Assume that $O = \{o_1, \cdots, o_m\}$ are the product orders and $V = \{v_1, \ldots, v_n\}$ represents their delivery points. An order $o_1$ is finished and I only have to wait one minute for order $o_2$ to finish. Furthermore, I can go from my business/deposit to both places in less than $x-1$ minutes, I will surely wait for $o_2$ to finish. However, if I can't pass through both $v_1$ and $v_2$ within 15 minutes, thus I won't wait for order $o_2$ to finish.

My question is: How can I do this with multiple delivery orders coming all the time? What if I have more than one deliveryman? I don't need an optimal solution, just a good approximation is fine.


texts:
I understand that GPUs are generally used to do LOTS of calculations in parallel. I understand why we would want to parallelize processes in order to speed things up. However, GPUs aren't always better than CPUs, as far as  I know.

What kinds of tasks are GPUs bad at? When would we prefer CPU over GPU for processing?


texts: Is there an analog of "regular" for infinite strings?

texts:
Consider the sequence $s_1 = (1, 0, 1, 0,\dots)$.  It seems "regular" in a way that, e.g. $s_2 = (1, 2, 3, 4,\dots)$ is not.

I'm not sure how to formalize this intuition though. One thing which jumps out at me is that $L =\{(0 1)^n\}$ is a regular language, and $s_1$ is in some sense the limit of the strings in this language.

Is there a terminology for considering these infinite strings? Do we have something analogous to the pumping lemma, whereby we can state that any such "infinite regular" string is of the form $x y^ {\infty}z$ with $x$, $y$, $z$ finite?


texts: Linked List in Maximal Scoring Subsequences Algorithm

texts:
For a project, I'm implementing the All Maximal Scoring Subsequences algorithm. In the analysis portion of the paper, it describes an optimization that makes the algorithm run in linear time. Namely, when doing the search for the rightmost value of $j$ that satisfies $L_j < L_k$, we can search a linked list with monotonically decreasing $L_j$ values.

I'm slightly confused on how this works. If we store a pointer to the element $j$ we found during Step 3, then we must start iterating with some element in Step 1. What element would operate as the head of the linked list in this case? In other words, in Step 1, instead of searching through the whole list, what element do we start searching with?

I found these lectures notes easier to read than the actual paper. I also implemented a $O(n^2)$ version of the algorithm in Go here, which anyone may use to reference. However, I would like some help cutting the complexity down to $O(n)$. Any help would be appreciated!


texts: Algorithm always provide a $2$_$sum$ with at least ONE prime? In polynomial-time?

texts:
Function Problem: Given $N$ find a $2$_$sum$ that uses at least $ONE$ prime.

Fact: Prime Gaps grow logarithmically on average. And, in worst case if memory serves correct it grows with a bounded constant.

Take notice that $count$ (defined below) will only equal to $s$, if the $AKS$ primality statement executes $s$ times. This will find our $s$-amount primes to generate a $2$_$sum$ by finding the difference of $N$-$P$.

Algorithm

$N$ = $13$

$s$ = $binary~length~of~N$

$p$ = 0

$count$ = $0$

$primes$ = []

$WHILE$ $count$ $<$ $s$:

$~~~~~~~~~$ $p$=$p$+$1$

$~~~~~~~~~$ $IF$ $AKS$-$PRIMALITY$($p$) == $TRUE$:

$~~~~~~~~~~~~~~~~~~~$ $primes$.append($p$)

$~~~~~~~~~~~~~~~~~~~$ $count$ = $count$ + 1

$OUTPUT$ FOUND $2$_$SUM$, $(N-P)$ + $P$

$OUTPUT$ VERIFY SOLUTION $(N-P)$+$P$ == $N$

Found 2-sum:  6 + 7
Verify Solution:  True

I'm an amateur who made computer-science a hobby, and I'm not sure what would the exact time complexity would be.

Question

What would be the best estimate of the time complexity?

Would it fail if $P$ $>$ $N$? (an easy fix)


texts:
I want to make the following reduction:

HP is the Halting Problem: HP = {w#x | w, x ∈ {0,1}* , Mw halts on input x}
w is the binary coded turing machine Mw.
L3 is the problem which asks, if M accepts exactly 3 inputs.

I know HP is not decidable, so I want to show that L3 is not decidable also:

HP ≤ L3

How can I make the reduction? The problem is that I don't know how I should proof that L3 accepts exactly just 3 inputs.


texts: Find Length of longest substring with all 1's in a binary string with k queries

texts:
Given a string of size n consisting of 0s and/or 1s.you have to perform k queries and there are two types of queries possible.

"1"(without quotes): Print length of the longest substring with all '1'.
"2 X"(without quotes): where X is an Integer between 1 to n.In this query, you will change character at Xth position to '1' (it is possible that the      character at ith position was already '1')

Input Format:

First Line of input contains n and k, where n is string length and k is the number of queries.
Next line contains a string of 0's and/or 1's of length n.
Each of next k lines contains query of any one type (i.e 1 or 2).

Output Format: For each query of type 1, print in new line the maximum size of subarray
       with all 1's.

     Example Input:                        Example Output:
     5 7                                   0
     00000                                 1
     1                                     1
     2 3                                   3
     1
     2 5
     1
     2 4
     1

My Solution: O(k*n) (if most of the queries of type 1)

 if(type==1){
        int count=0, ans=0;
        for(int i=0;i<str.size();i++){  //longest len substring
            if(str[i]=='1'){
                count++;
            }else{
               ans=max(ans,count);
               count=0;
            }
        }

        printf("%d\n",ans);
 }else{
        int xth;
        scanf("%d",&xth);
        str[xth-1]='1';   //update
 }

I am not able to figure out an efficient solution, as for 'type 1' query only solution I could think of is to iterate through string every time and maintain a "count" variable with all 1's consecutively and finally update "ans" variable when ith str becomes '0'.

I am thinking of using segment tree but don't know how to do. As required good solution should be O(k*log(n)) (doing "type1" query in log(n) time)


texts: How to prove that $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular?

texts:
We know that $L=\{0^i 1^{j^2}|i> 0,j\ge 0\} $ is irregular (by the Pumping Lemma), we have to use it to prove two things:

$L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular.
$L_1$ is making all the three conditions (I don't know the exactly word at English for this...) of the Pumping Lemma.

For the first one - how do I prove it by the Pumping Lemma?

For the second - I have no idea and I'd like to get ant help!
(Because I can choose any word that I want, and I need to prove it for all the words in $L$).

Thank you!


texts: Assuming NP≠coNP, do we have a similar theorem to Ladner's?

texts:
We have that $\mathrm{NP\neq coNP\iff NP\neq NP\cap coNP}$.

So by assuming that $\mathrm{NP\neq coNP}$, can we prove the existence of intermediate problem between $\mathrm{NP}$-complete and $\mathrm{NP\cap coNP}$?


texts: How is it possible that an equational theory be terminating?

texts:
I'm a bit tripped up by this fundamental notion of an equational theory with respect to how we can possibly get termination if we have that we can always orient a set of equations either right to left or left to right. For example, consider the set of equations just being $E=\{1+x=x\}$. For signature $\Sigma$ we consider the equational theory $(\Sigma, E)$ as equivalently the term rewrite system $(\Sigma, E' \cup E'')$ where $E' = \{t \rightarrow t'\ |\ t = t'  \in E\}$, and $E'' = \{t' \rightarrow t\ |\ t = t'  \in E\}$ (source, which I may be misunderstanding; attached below). Hence, we have the set of rewrite rules in this equational theory from my understanding being $\{1+x\rightarrow x,\ x \rightarrow 1+x\}$. Hence, if we were to try and rewrite $1+x$, we would run into the issue of looping:

$$1+x \rightarrow x \rightarrow 1+x \rightarrow x \rightarrow 1+x \rightarrow\ ...$$

Hence I don't see how it would be possible to have in an equational theory any termination due to this—it's not possible to have a well-founded reduction ordering from what I can tell when equations are oriented in both directions.

I was reading about Knuth-Benedix completion algorithm and that seems to be on the right track of what I was thinking, but I'm still somewhat confused on how we can consider sets of equations oriented in both directions as a TRS without running into the above aforementioned problem.

Here is the source I mentioned above:


texts:
I often read that deciding whether or not a number $r$ is a quadratic residue modulo $n$ is an interesting (and hard) problem from number theory (especially if $n$ is not prime).

I am looking at the following special case of this problem: Let $p$ and $q$ be two different prime numbers and $n:=pq$. Given $r$ between $1$ and $n$. Decide if there exists an $x\in\mathbb{Z}/n\mathbb{Z}$ such that $x^2\equiv r\pmod{n}$.

My question is: The functional version of this problem i.e. "Find such an $x$ as above" yields an randomized algorithm for integer factoring. So it is very interesting for practical reasons like "breaking RSA". Is there any such result for the decision version of this problem? If not, what are typical problems that let us think that deciding quadratic residuosity it is a hard problem?

And furthermore, is the special case I'm looking at really a special case? Or can I solve the general case with an arbitrary $n$ with an oracle for the decision problem above?


texts: Detecting Data and Control Hazards for a mips 5 stage pipeline

texts:
I'm practicing data and control dependencies, but having trouble detecting them. For this example, I'm assuming this pipeline is fully bypassed (with forwarding). I think the only data dependency is i3 on i2. Is this correct? I also don't know how to detect the control dependency. I know there will be one because of the bne, but not sure how and on which one...
i1: lw $t0, 10($t1)
i2: lw $t4, 3($t2)
i3: addiu $t0, $t4, 3
i4: addu $t0, $t0, $t2
i5: addiu $t2, $t2, -8
i6: addiu $t1, $t1, -4
i7: bne $t1, $0, i1


texts: GCD binary representation time complexity

texts:
1.  Consider the following algorithm for deciding GCD:

“On input :

1. If z doesn’t divide x or y, reject.               O(n)

2. For i from z + 1 to min(x,y) do:                  O(2^n)

    2.1. If i divides both x and y, reject.         O(n)

3. Accept.”                                           O(1)

Analyze the algorithm’s time complexity (in big-O notation).

n is the length of the max(x,y)
So I was given an algorithm, the time complexity to the right is My addition and not part of this question. I want to make sure this is correct.
I was thinking diving binary numbers is O(n) using long devision and step 2 just adds 0 or 1 to each previous number thus making the time exponential.
Am I right ?
Also, is there an algorithm that solves this in polynomial time ?
Thanks


texts: Dijkstra's algorithm - Finding additional paths with same weight but different edges

texts:
given a network with n stations. assuming the shortest between s,t was found using dijkstra's algorithm. let that path be denoted as $(a_1,a_2,...,a_k)$

assume that between the nodes s and t, there's an at least additional path with the same weight, but with different edges(meaning both paths have different edges, nothing in common). how can we find that additional path?

My attempt: let's create an array that holds the parent. that array will be separate, so the value of $parent[v_i]$ for some vertex $v_i \in V$ stores the parent of $v_i$ in the array, in the shortest path tree that is formed by the algorithm. now, we'll initiate the first element, meaning the parent of the root to be -1, and if we find shorter path through some vertex u, we can make u the parent of the current vertex. but i am not sure it solves the problem unfortunately.

would really appreciate if you could explain what you do so i can understand it.

tried to do a research on the site, but couldn't find a similar problem with no same edges and i don't know how to solve it, so i am asking for help here

thank you very much


texts:
In the bin packing problem, we are given a set of items I={a1,...,an}, each item with weight w_a1,...,w_an, and a set of n bins with B={b1,..., bn} all bins with capacity C. I want to restrict the weights of the items to be polynomial in n. Is the problem still being NP-hard (restricting the weight of the items)?

Any information and sources about this would be appreciated.

Thanks.


texts: Priority of symbols in a notation for projections

texts:
We define an initial function called projection as $$I^k_i(n_1,\ldots,n_k) = n_i, \quad i \leq 1 \leq k, \quad k \in \mathbb{N}.$$

Suppose now that we want to define it in some programming language where we have no access to superscripting nor subscripting. Should we call it Iki or Iik?

My stand point is that it should be Iki so that we first describe the nature of function, that it comes from a set of functions that take k arguments. But, the other approach is also understandable because it emphasizes the purpose of function, that it returns the i-th coordinate.
It may also be that priorities don't go from left to right as I imagine it.

Is there any convention on priority of symbols in this type of notation?


texts: Confusion regarding terminology surrounding perceptron learning

texts:
I am having trouble understanding the terminology with perceptron learning. Is my current understanding correct? Let's say I have some data that classifies what type of flower a particular flower is. And let's say the factors taken into consideration are petal size, petal coloring, and leaf size. So my current understanding is that we take every pair of inputs and make them the axis of a graph(e.g. leaf size vs petal coloring). So in this case, we would have 3 graphs. Now, we plot the data points and see if it is linearly separable. That is, we can draw a line called a "decision boundary" that separates the data into two regions to be able to differentiate which inputs correlate with which outputs. This line is defined by $w^T \cdot x = y$. However, my first confusion is the following. How are 3 different graphs each with pairs of inputs (the 2 axis) represented using a equation of a single line that is used as the input layer of the neural network?

My second confusion is, is the objective function what defines how the $w^T \cdot x$ is to be interpreted? For instance, something like $y = 1 $ if $w^T \cdot x \geqslant 0$ and else $y = 0$. Also, as I have understood, the learning rule is supposed to be how to update consecutive weights.

Can someone please explain the situation I have laid out. I am reading Bishop's book on Neural Networks. But I am confused by the text.


texts: Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?

texts:
On wikipedia, there is a proof for the cycle property of the Minimum Spanning Tree as follows:

  Cycle Property:
  For any cycle C in the graph, if the weight of an edge e of C is
  larger than the weights of all other edges of C, then this edge cannot
  belong to an MST.

  Proof: Assume the contrary, i.e. that e belongs to an MST T1. Then
  deleting e will break T1 into two subtrees with the two ends of e in
  different subtrees. The remainder of C reconnects the subtrees, hence
  there is an edge f of C with ends in different subtrees, i.e., it
  reconnects the subtrees into a tree T2 with weight less than that of
  T1, because the weight of f is less than the weight of e.

Why does the proof assume that e belongs to MST? If e belongs to a cycle, and it belongs to MST, doesn't it immediately imply that the MST has a cycle and therefore is not a tree?

Please show me why I am not understanding this proof correctly.
i.e. How can we have an edge e already in the tree but the tree remains acyclic?


texts: What is the current fastest algorithm for finding the maximum common subgraph?

texts:
First of all, it's my first time in #ComputerScience at StackExchange so, my apologies if I'm making some newbie mistake when asking this question.

So, I'm currently researching algorithms for finding the maximum common subgraph isomorphism and after reading a lot of papers I'm still confused about what is the state-of-the-art algorithm for finding the maximum common subgraph between 2 graphs. Also, all the algorithms I've read about work with 2 graphs (directed or undirected) but none directly work with more than 2 graphs.

In summary, my questions are:

Which is considered the fastest/state-of-the-art algorithm for finding the MCSI? Is it the VF2 algorithm?
Also, does this algorithm work with more than 2 graphs at the same time?
Any alternate algorithm that works with N graphs?

Thanks in advance!


texts: generic way to convert imperative if-then-else statements into functional style?

texts:
In this question, I asked about a reference for translating imperative code to functional code. I want to ask a more specific question here.

How, in general, do we translate into functional style, a statement of the form:

if (cond) then
    do x;
else
    do y;

I know that functional languages have if-then-else statements but the expressions are only allowed to be pure. Is there a general way of doing this translation?


texts: Why do we not store the min in any of the recursive clusters in a Van Emde Boas tree?

texts:
I was reading the chapter of van Emde Boas in CLRS (page 547 section 20.3 3rd edition) and it says:

  Furthermore, the element stored in min does not appear in any of the recursive $vEB( \sqrt[\downarrow]{u})$ trees that the cluster array points to. The elements stored in a $vEB(u)$ tree V, therefore, are V.min plus all the elements recursively stored in the $vEB(\sqrt[\uparrow]{u})$ trees pointed to by V.cluster$[0..\sqrt[\uparrow]{u} - 1]$. Note that when a vEB tree contains two or more elements, we treat min and max differently: the element
  stored in min does not appear in any of the clusters, but the element stored in max does.

However, I was not sure why that was true. Usually I put more details in my question but I don't understand why the min wouldn't appear recursively too just like in proto one. Does anyone understand the justification for that paragraph? Why do we treat the min and max differently? What is special about 2 or more?


texts: MAX,MAJ variants of NP complete problems

texts:
We know that MAJSAT is PP-complete. Is it generally true that given an NP-complete problem, its majority variant is PP-complete? For example,

MAJ-Set-Splitting: are the majority of partitions of items going to split the sets?

MAJ-Subset-Sum: does the majority of partitions of items have a sum of exactly K?

etc...


texts: What is the time complexity of the below code?

texts:
i=12

while( i < n )

{

i=i^5

i=i/3

i=i∗7

}

What is the complexity of the given program?


texts: Recommended readings for Probability theory applied to algorithms

texts:
Currently, I'm delving into Analysis of Algorithms and I've discovered that I would need to improve my knowledge of Probability Theory. Any recommendation? Where do I start?
Thanks in advance!


texts: Two functions which can create any computable function by composing?

texts:
Do there exist two computable functions, a and b, which can construct every computable function by a finite serie of a's and b's which is function composed? Fx. let's take the serie, a,b,a,b,b,a,a,a , which function composed is the function, a∘b∘a∘b∘b∘a∘a∘a ( =a(b(a(b(b(a(a(a(x)))))))) ), this function is the function described by the serie, a,b,a,b,b,a,a,a. And I want to know if every program can be described, by such serie.

If such functions exist, can you tell a example of a and b?

Thanks.


texts: The meaning and relevance of the locution ''no terminating implementation'' in type theory

texts:
In the context of a discussion of Haskell https://stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-of-the-co-reader-monad, I was told that

There is no terminating implementation for the polymorphic type $(e \to a) \to a$

and that we couldn't have a function of type $((e \to a) \to a) \to e$ or a function of type $(r \to x) \to x$, for these would not be ''implementable''.
These types are well formed in the STLC, in the sense that we can construct them using the rules of type-formation. And I don't see why we can't form lambda terms of this shape, such as $\lambda c_{((a \to t) \to t)}. \, b_a$, or $\lambda p_{e \to a}.\,b_a$.
What is therefore the problem? Specifically, what is a ''terminating implementation'' in the context of the STLC? I believe this relates to the fact that $(e \to \bot) \to \bot$ is not constructively equivalent to $e$, but I would appreciate if someone could spell this out for me.


texts:
Basically, the problem is: For a set $S$ of positive numbers, find a minimal number $d$ that is not a divisor of any element of $S$, i.e. $\forall x \in S,\ d \nmid x$.

Denote $n = |S|$ and $C = \max(S) $.
Consider the function $F(x) = $ the least prime number not dividing $x$. It is easy to see that $F(x) \leq \log x$. And for a set $S$, let $F(S) = $ the least prime that doesn't divide any element of $S$.  We have an upper bound

$$F(S) \leq F(\operatorname{lcm}(S)) \leq F(C^n) \leq n \log C.$$

Therefore a simple brute-force algorithm, which enumerates all numbers from $1$ to $n \log C$ and checks if it doesn't divide any element of $S$, is polynomial and has time complexity $O(n^2 \log C)$.

The other way to solve the problem is to compute all factors for every element of $S$ and use them in brute-force algorithm to check if $x$ is an answer in $O(1)$ time. This algorithm has time complexity $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ and uses $O(n \log C)$ memory, because we don't need to compute and store factors greater than $n \log C$. For small $n$ and $C$ it performs better.

In detail, the algorithm consists of two parts:

Construct a set $\hat{S}$ composed of all factors of all elements of $S$, i.e. $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$
This can be done in $O(n \cdot \min (\sqrt{C}, n \log C))$ time and $O(n \log C)$ memory.  (Where does this come from?  For any element of $S$, we can factor it using either trial factorization with all numbers up to $\sqrt{C}$ or all primes up to $n \log C$, whichever is smaller; thus each element of $S$ can be factored in time $O(\min (\sqrt{C}, n \log C))$ time.)
Find minimal number $d \notin \hat{S}$. This step requires $O(|\hat{S}|) = O(n \log C)$ time, if checking whether $x \in \hat{S}$ can be done in $O(1)$ time.

I have two questions that I'm interested in:

Is there a faster algorithm to solve the problem?
For given $n$ and $C$, how can we construct a set $S$ with maximal least common non-divisor?


texts: How do you resolve this paradox with the invariance theorem?

texts:
The invariance theorem of kolmogorov complexity states that for two different languages with complexity functions $K_1$ and $K_2$, we have

$$\exists c.\forall s. K_1(s) \le K_2(s) + c$$

Here is an apparent paradox I found. Let the two languages be Binary Lambda Calculus and (an idealized version of) Perl, with complexity functions $K_L$ and $K_P$ respectively. I could have used other languages, but these were the easiest. Both will measure the length of the minimal program in bits.

By the invariance theorem, there exists a $c$ such that:

$$\forall s. K_L(s) \le K_P(s) + c$$

This seems reasonable. After all, we can create an (idealized) Perl interpreter in BLC. Call this interpreter $e$. Also, for a perl program $p$, there is a BLC term encoding $p$, say $t_p$. Then the program

$01et_p$

Computes the same string as $p$. This seems to imply that $c$ can equal $2 + |e| + |p|$, proving the invariance theorem for this specific case.

But actually, $t_p$ will be longer than $p$, since BLC does not encode binary data efficiently, so the above analysis does not work. Perl, on the other hand, can encode binary data efficiently.

In particular, a perl program can include the __DATA__ token, followed by arbitrary binary data. The program will then have access to this data. Note that no escape codes are necessary, as would be in a Perl string, since after seeing the __DATA__ token, perl only interprets the rest of the program as raw binary data. There is no way to "recover" from this. This __DATA__ token will be important.

Now, for the paradox. For any string $s$, we can create a perl program $p_s$ such that $|p_s| = |s| + c_P$, where $c_P$ is a constant independent of $s$ and $p_s$. This is because we can have a perl program that outputs the raw data after __DATA__. We then store the string $s$ directly in __DATA__.

Now, we will create a BLC program as follows. Let $r$ be a BLC term that takes two strings, and outputs $<s_1s_2, |s_1|>$, where $< \cdot , \cdot >$ is a pairing function.

Now, it is easy to show that there exists a string $s$ and a number $n$ such that $|s| > n$ and $K_L(s,n) \gt |s| + x$ for any constant $x$. Let $x$ equal $8 + |r| + 2c_P + 2|e| + 2c$.

Let $s_1$ be the first $n$ characters of $s$ and $s_2$ the rest of $s$. Then the BLC program $0101r01et_{p_{s_1}}01et_{p_{s_2}}$ outputs $<s,n>$, meaning that $$K_L(s,n) \le |0101r01et_{p_{s_1}}01et_{p_{s_2}}| \le 4 +|r| + 2 + |s_1| + c_P + |e| + c + 2 + |s_2| + c_P + |e| + c = |s| + x$$ a contradiction!

So, what is the resolution?

It seems that the main problem is that BLC is a prefix free language, whereas Perl is not.

Perl's __DATA__ token, a key part of the paradox, implies the Perl is not prefix free. That is because for any program with a __DATA__ token, you can add whatever bytes you like to the end of the program. Taking the contrapositive, BLC being prefix free implies that it can not encode raw binary data. The paradox should work with any prefix free and non-prefix free language.

Another thing to touch on is that Perl deals only with bytes, not bits. We can assume that idealized Perl can deals with individual bits. Or we can hardcode into $p_s$ with how many bits of the last byte to ignore, which only add a constant overhead (up to 7 bits for the useless bits at the end of the last byte, and a couple of bytes to slice the bits of the end of last byte).


texts: An axiomatic theory of computational models?

texts:
There are many different computational models, e.g. Turing machines, register machines, lambda calculus, etc.

I am wondering if there exists an axiomatization of computation, that abstracts away from the specifically constructed computational model.

I.e. is there a more general theory about computation that deals with computational machines that are not perfectly specified, but that still captures their common characteristic as computation machines?


texts: How to get Algorithm complexty based on another 2 algorithms?

texts:
I had quiz last week and it says: suppose algorithms $A_1$ and $A_2$ have worst-case time bound $p$ and $q$, respectively.
Suppose algorithm $A_3$ consists of applying $A_2$ to the output of $A_1$. (The input for $A_3$ is the input for $A_1$.)
Give a worst-case time bound for $A_3$.

How could I calculate the worst case based on the given info?


texts:
Given is a language $A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$ ; where $N^{+}$ are the natural numbers excluding 0.

I have found a type-1 grammar to describe it:

$S \to A_1A_2$

$A_1 \to aA_1cc \;| \; abcc$

$A2 \to bA_2 \; |\; \epsilon$

However, this doesn't tell me much about the language's Chomsky type. How can I know if there exists a more restricted grammar and how can I find it?


texts: What is the minimum required storage for a sparse, depth-first octree?

texts:
For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree on disk, given the following conditions:

It is very sparse (i.e., not all nodes exist), but potentially deep (a depth of 20 or beyond)
It is stored depth-first (pre-order)
All parent nodes up to the root node must be stored (i.e., it is not sufficient to store just the leave nodes)
The amount of data per node is a global constant

The best I can come up with is 6 7 bits per node: 3 bits to indicate the position of a node with respect to its parent, and 3 4 bits to store how many child nodes exist. However, intuition tells me there should be a more efficient way. Please note that algorithmic efficiency is not part of the question, as its representation in memory will be different anyways.

P.S.: Please let me know if CS is not the right SE venue for this kind of question.

Update

The resulting data structure will be stored in a file on disk, thus the need for an efficient encoding of the octree. There are additional data files that contain information associated with each existing node (e.g., solution data). To have a one-to-one relationship between nodes ("cells") in the octree file and the datasets, it is required to store all internal nodes (i.e., non-leaf nodes) in the octree file as well.

Example

An octree with 5 nodes: 0, 1, ..., 4. Their relationship is the following:

0 is the root
1 is child 0 of node 0
2 is child 1 of node 1
3 is child 5 of node 1
4 is child 1 of node 0

The resulting tree would look something like this (with missing nodes omitted)

    0
   / \
  1   4
 / \
2   3

and the nodes need to be stored 0 1 2 3 4 (pre-order depth-first).


texts: I was reading the book Introduction to Algorithms, Chapter 1. When I saw this diagram, I got confused because $\lg n$ has the largest value of time while $n!$ has the least value of time. And that doesn't make sense to me - perhaps I misunderstood this?


texts: What is M referring to when talking about memory size( 4M x 8)

texts:
In the following paragraph its talking about memory and it throws M into the L X W of memory notation and i'm confused on how 4M = 2^22. Thanks in advance

PARAGRAPH:

Memory is built from random access memory (RAM) chips. (We cover memory in detail in Chapter 6.) Memory is often referred to using the notation length   X   width (L   X   W). For example, 4M   X   8 means the memory is 4M long (it has 4M   =   2^2     X   2^20     =   2^22   items) and each item is 8 bits wide (which means that each item is a byte). To address this memory (assuming byte addressing), we need to be able to uniquely identify 2 ^ 22   different items.


texts: Responsive input sliders - is there a better way?

texts:
I am building an app where a user controls inputs via multiple sliders each with discrete steps. The app then uses the combination of slider values to run some calculations and returns back an output value.

The sliders are meant to be highly responsive, so the user can immediately see the impact of their input combination on the output value -so I have resorted to eagerly calculating ALL possible combinations of sliders and letting the client query the results in the browser itself for faster response times.

The problem is that the number of possible combinations can seriously explode. If I have 6 inputs each with 10 steps, that is 10^6 = a million possible combinations! That's way too expensive to calculate eagerly.

Is there a better way to do this? I could try to restrict the number of sliders that can be moved at any point, to lower the solution space...but wondering if there's a better solution out there.


texts: Quantum state probabilities and amplitudes - absolute value squared?

texts:
It has just appeared to me that I've overlooked a possibly important fact. When we want to calculate probability $p_x$ of measuring the state $X$ and we know the amplitude of $X$ is $\alpha$, we know that $p_x = |\alpha|^2$. Until today I thought that absolute value was not necessary anyway. However, it brings significant difference if we have complex amplitudes with non-zero imaginary parts.

For example, let's say we have a superposition of 16 states, where four amplitudes are like $\frac{i}{4}$, four like $\frac{-1}{4}$ and eight like $\frac{1}{4}$. If we keep with the recipe I wrote above, then this state is fine, as the sum of all probabilities is 1. However, if we skip the absolute value and compute probabilities like $\alpha^2$, then sum of all probabilities in the above state would be $\frac{1}{2}$ and the state would not be stable.

Is the recipe I wrote above ($p_x = |\alpha|^2$ for $\alpha$ being an amplitude of state $X$) correct? Do we calculate the absolute value of the amplitude before we square it?


texts: Is open adressing with prime steps bijective?

texts:
Who can help me with this topic: Probing with a step width that is a prime number.

I am struggling with this question about defining a hashing function $h(k, i)$ for open addressing on a table of length m, that is, with slots numbers $0, 1, 2, \dots ,m − 1$.

We know that a function $h(k, i) = h_1(k) + i \cdot h_2(k) \mod m$ produces a permutation for every $k$ if $h_2(k)$ and $m$ are relatively prime, that is, if $\operatorname{gcd}(h_2(k),m) = 1$.

We can assume that $m, w$ be integers such that the greatest common divisor $\operatorname{gcd}(m,w) = 1$.

How can I prove that the function above

$\qquad f : \{ 0, \dots,m − 1 \} \to \{ 0, \dots,m − 1 \}\\
 \qquad f(i) = i \cdot w \mod m$

is a permutation, in other words, a bijective function?


texts: Research regarding algorithm generation/discovery/heuristics

texts:
Say I have a specification of preconditions and postconditions for a function. Is there a field of computer science that studies the automated generation of functions that satisfy those specifications?

For example:
Preconditions:

I is a list
Q is a binary relation specifying a total order on the
elements in I

Postcondition:

O is a list
There exists a bimap B (and its complement B') such that

O[B[j]] = I[j], and
O[j] = I[B'[j]],
for every j, 0 <= j < n,

For every x, 0 < x < n, Q(O[x - 1], O[x]) is true.

The set of functions that satisfy this (I hope unambiguous) specification are the sorting algorithms. So, how do we get a computer to take this specification, and give us a sorting algorithm?


texts:
I know that since ~2004, Moore's law stopped working for CPU clock speed.
I'm looking for a graph showing this, but am unable to find it: most charts out there show the transistor count or the capacity per year.

Where can I find some data showing the CPU frequency of computers (anything is fine, personal computers, servers, laptops, ...) from the last few decades to today?
Raw data that I can plot myself would be fine as well (hum, probably even better).


texts: Can not follow the example for max-flow-min-cut on Wikipedia

texts: This Wikipedia example is very confusing. Its saying the max flow = min cut. But I see the max flow = 9 and the min cut = 7. If not, how does the capacity =min cut here? Which is the max flow min cut theorem.


texts: Computing all paths from root to the leaf nodes in a tree

texts:
I have a this tree, i want to print out all paths from root to all child nodes:

NOTE: I wanted to come up with a solution that does not involve passing state between recursive calls.

    a
  / | \
  b c  d
 / \    \
e  f    g
      / / | \
      h i j k

This is the my code to create and print the paths.

class Node:
    def __init__(self, data, children=[]):
        self.data = data
        self.children = children

tree = Node(
    "A",
    children=[
        Node("B", children=[Node("E"), Node("F")]),
        Node("C"),
        Node("D", children=[Node("G", [Node("H"), Node("I"), Node("J"), Node("K")])]),
    ],
)

i want to enumerate all the paths to reach from root node to all leaf nodes.This is what i have come up with.

def paths(root):
    x = []
    if root.children:
        for c in root.children:
            for el in paths(c):
                x.append(c.data + el)
    else:
        x.append("")
    return x

a = paths(tree)
print(a)

i get this output:

['BE', 'BF', 'C', 'DGH', 'DGI', 'DGJ', 'DGK']

This is partially correct, what is missing is the root node 'A' in all the paths, I am not able to think how to get that, even after thinking for 2 hours straight. I know why is it happening(because I start from child nodes of the root). what i cannot get is how to encode the root node itself.

I hope this pseudocode is clear:

function paths(N):
  path <- empty list
  if the node(N) has children
     for every child node `(C)` of `N`
        for every path `(P)` in paths(`C`)
           add to path <- `C.data` + `P`
   otherwise
      add to path <- + ""
   return path


texts: How to reduce the low-rank matrix completion problem to integer programming?

texts:
Consider the low-rank matrix completion problem:

  Given an integer $k$ and a subset of entries of some $n \times n$ matrix, fill in the rest of the entries so that the resulting matrix has rank at most $k$.

This problem is clearly in NP, since the set of additional entries is the required certificate. Therefore, it can be written as an integer program. How can one do this?

I'm having trouble seeing how to get rid of a rank constraint, even at the expense of adding integer constraints.


texts:
In the theory of NP-completeness, researchers refer to the concept of combinatorial  explosion. Some researchers use it as justification for intractability or NP-completeness. Others use it to refer to the exponential growth of possible solutions of an intractable problem while others use to refer to the apparent exponential time required to solve NP-complete problems. I am interested in formal connection to combinatorics.

  Is there combinatorial basis that captures and explains the phenomena of combinatorial explosion?


texts:
Here http://tomstechnicalblog.blogspot.com/2016/02/rxjava-understanding-observeon-and.html I've found a sentence which I do not understand:

  If you have a quad-core, you can optimally support 5 computational threads (4 cores + 1 extra thread for idle time).

What is that 1 extra thread for idle time for? Is it similar to those "normal" 4 cores?


texts: Given a JPG of a wallpaper, how can I find the smallest section which contains the pattern?

texts:
I recently made the photo

of tapestry, but I am not able to identify the smallest patch which contains the pattern.

Now I wonder: How could I write a program that does so?

A first step could be identifying axis-aligned bounding boxes (AABBs). The most simple way I can think of is having a combined quality metric:

$$error = MSE + pattern\ area$$

to combine two problems:

get a small pattern area
get a small MSE (and MSE gets better with bigger patterns)

Then just take many possible AABBs and compute their scores. The MSE would simply take the color difference in HS (HSL without L) color space.

How is this problem called? What are current state of the art solutions?
Are there algorithms which also work on more complex shapes / repetition patterns than AABBs? Can I rotate the image optimally / take shearing into account?


texts:
The way I see it, it should not be further reducible. I'm thinking λz.zq is like

lambda z: z(q) # Python, not lambda calc

and you do not know z nor q so it is not further reducible.

The below derivation (where I am wondering about the last steps) is from the new Haskell book:


texts: Is the "subset product" problem NP-complete?

texts:
The subset-sum problem is a classic NP-complete problem:

  Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ that sums to $k$?

A student asked me if this variant of the problem called the "subset product" problem is NP-complete:

  Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ whose product is $k$?

I did some searching and couldn't find any resources that talked about this problem, though perhaps I missed them.

Is the subset product problem NP-complete?


texts: Is it possible to denote "any single alphabet symbol" in an FSA state diagram?

texts:
This is a possible duplicate of the following (but not sure it answered my question):
Is it possible to support .(any symbol) or \d, \w, \W in DFA

My professor is asking for a finite automata state diagram for some language that accepts even length strings (actually it's more complicated than that, but I'm starting with that as a subset). But he didn't define the alphabet of the language (on purpose). We can assume the alphabet is definite, but I assume I can't just use an arbitrary alphabet instance.

Here is a DFA/NFA state diagram concept that I think accepts even strings (including $\epsilon$):

But what alphabet symbols / terminals should I put on the edges? It shouldn't be $\Sigma^*$. It shouldn't be $\epsilon$. Can I use $.$ ? Can I use a $*$ ? Can I use anything as long as I describe what it means?

EDIT - I just found the use of $*$ in these notes of an Illinois course (p.4):


texts: Bakery algorithm: what is the choosing[] boolean array for?

texts:
I'm studying the bakery algorithm.

do {
     choosing[i] = true;
     number[i] = max(number[0], number[1], …, number [n – 1])+1;
     choosing[i] = false;
     for (j = 0; j < n; j++) {
         while (choosing[j]); //
         while ((number[j]!= 0) && (number[j],j)<(number[i],i)));
     }
     critical section
     number[i] = 0;
     remainder section
} while (1);

Please help me know what exactly this choosing doing here. I checked this for all conditions that I could generate to understand its use. But it doesn't  seem to be making any difference. Please help me with a case.


texts: Simulation BPP by Pseudorandom Generator

texts:
I use the following scribe to study  Pseudorandom Generators.

The most intriguing question for me is how exactly PRG can be used in order to simulate BPP.

Let $A(x,r) \in BPP$, where $x$ is primary input and $r$ - randomness provided by BPP. Instead of $r$ we can provide $A$ with pseudorandom input $G(U_{d(n^c)})$ and according to the Claim 7.6 from the scribe. $A$ with pseudorandom input differs from $A$ with random $r$ in less than half of running cases. The proof of Lemma shows that if it's so, that there is a distinguisher that distinguishes $U_{d(n^c)}$ from $U_{n^c}$ with advantage at least $\frac{1}{2} - \frac{1}{3} > \frac{1}{8}$ which is contradicts to the definition of PRG.

Q: Where this advantage comes from? I simply don't understand what these numbers mean.

Q: Construction question. Why do need to run over all seeds of length $d(n^c)$ there are $2^{(d(n^c))}$ such string. For me it sounds like a strengthening of randomness because after that we use the majority as a result. But actually why do need that, why we cannot use single seed of length $d(n^c)$.

Q:Philosophical question. Why do we need PRG to be non-uniformly strong? Why we cannot use uniformly indistinguishable PRG? I saw the idea that the primary input $x$ to the $A$ can be used as advice, but I still don't understand why do we need it.


texts: How to implement mutex on single processor (single core) system other than using spinlock

texts: How does one implement mutex on a single processor system without using spinlock mechanism. Mutex is to be implemented in user space (for any user level library like pthread lib for example).


texts: What decompression algorithms have the shortest implementations?

texts:
I am writing an executable compressor for small (roughly 1 kilobyte) executable files.

I am exploring compression algorithms that are well suited for this task. The amount of time required to compress and decompress is not important for my purposes, nor is the complexity of the compressor. I am limited to 4 GB of RAM while decompressing and I am chiefly concerned with maximizing the compression ratio while minimizing the size of the decompression stub.

I am currently experimenting with arithmetic encoding using various models to predict the posterior probability. This results in a decompression stub around 200 to 300 bytes in size. I have also experimented with LZ based methods, but have rejected them because their implementation is more complex and their performance is both theoretically and empirically inferior to arithmetic encoding with context modeling.

What other compression algorithms might be useful candidates for this task?


texts: Inference rule with two conclusions or rather inverse function application

texts:
I want to express a simple correctness theorem for a term-desugaring function $\Delta$. The goal is to express that if the evaluation of a desugared term yields a value, this value is the desugared result of evaluating the original term.

Since the implication operator $\Rightarrow$ is already used in my dynamic semantics, I'd rather use an inference rule to express the implication. However, in the premise I have to introduce a variable $v$ that is the result of applying $\Delta$ to a variable bound in the conclusion. Since there is no inverse of $\Delta$ I am somewhat stuck between two odd variants to express the relation.

The first variant uses two conclusions (like multiple premises the idea is that both always hold):

$$
\frac{\Delta(t) \Downarrow v}{t \Downarrow v^\prime \quad \Delta(v^\prime) = v}
$$

This looks odd to me. The alternative would be to see the rule as a scheme subject to some substitution over the meta-variables $t$ and $v$. In that case I could also write:

$$
\frac{\Delta(t) \Downarrow \Delta(v)}{t \Downarrow v}
$$

This is obviously cleaner, but I am not quite happy with the implications (pun not intended) to the theorem: In the first case, if $v \neq \Delta(v^\prime)$ the premise still holds, but the conclusion does not, so $\Delta$ is not correct. In the second case the premise would not apply - so correctness simply does not cover the case at all.

Is there a common pattern to deal with such problems? Did I overlook something?


texts: Solve a basic mutex lock problem while preventing deadlock

texts: I am solving a problem with a bridge, where you have a one way bridge with people coming from each side. To solve this problem while preventing deadlock (two people going opposite directions on the bridge at the same time), I used a mutex lock. However, this could still result in starvation. How would I prevent starvation?


texts: Grammar for $\{ a^i b^j: j < 2i \text{ and } j \ne i \} $

texts:
For the following language, write grammar independent of the text.
$$\{a^i b^j: j < 2i \text{ and } j \ne i \} $$
I want a hint to start solving this problem. Where should I start?


texts:
Let f$(n)=O(n)$, $g(n)=\Omega(n)$ and $h(n)=\Theta(n)$.
Then $g(n)+f(n)\cdot h(n)$ is equal to what among $O(n)$,$\Omega(n)$ and $\Theta(n)$?

Also explain how to evaluate it.


texts: Is it possible to run more than one Turing Machine emulator using only one processor kernel?

texts:
I had this question on computer architecture exam and can't find an answer anywhere.
Is it possible to run several Turing Machine emulators at once using only one processor kernel?
a) Yes, by executing the instructions of every machine in turns;
b) No;
c) Yes, but you need to use OS threads.


texts: Why can optimality be preserved when inserting a new conjunct into an optimally ordered conjunction of conditions?

texts:
In a programming language with short-circuiting, a conjunction of N independent conditions has the following expected cost:

where:

t_i = the expected cost of evaluating a conjunct
p_i = the probability that a conjunct evaluates to true

I am trying to prove the following statement:

  If you have an optimally ordered conjunction of N conditions and insert a new conjunct at location k (where k is chosen to be the insertion location that minimizes expected cost), then the resulting conjunction of N+1 conditions is also optimally ordered.

I strongly suspect that the above statement is true, because I wrote a Monte Carlo simulation that tested the statement on thousands of randomly generated examples. The test identifies the optimal ordering by brute force and confirms that the optimal ordering can be created by inserting the new condition at some location k. Can anyone help provide a formal proof?


texts: Languages having only one Myhill–Nerode equivalence class

texts:
Consider the alphabet $\{a,b\}$, for which languages does the Myhill–Nerode equivalence relation have exactly one class?

From what I understand about equivalence classes, each state is considered a class. So would $\{ a^n : n>0\}$ be the one class?


texts: Searching a value in a "piecewise" ordered array

texts:
If we have an array $A$ of length $N$, which is partitioned into $\sqrt{N}$ adjacent subarrays $A(i)$, each of which is monotonically ordered from $\min(i)$ to $\max(i)$ (it is known what places have those bounds in A for each subarray), with the following conditions:

min(i) < min(i+1),
max(i) < max(i+1),
min(i+1) < max(i),
If subarrays A(i) and A(i+1) both have the j-th element, then A(i,j) < A(i+1,j),
The number of elements in subarray A(i) is strictly increasing with i

Would it be possible to search an element in the array $A$, in time $O((\log N)^k)$, for a positive $k$?  If yes how?

If not, what kind of minimal additional conditions would allow that?

Edit. The subarrays are not necessarily of equal length.
They are strictly increasing. The above stated conditions are always guaranteed.

What I have tried so far is to binary search them separately, but that is obviously going to be very inefficient.

[Note that this question has obviously nothing to do with the search of the min of max value in the array. And I am not interested in sorting the array. Just the mere search.]


texts: Proving NP Completeness of a subset-sum problem - how?

texts:
So I'm trying to understand P/NPC problems. The one I'm trying to tackle now is subset sum (we have a collection of integers $S$ and a $k$ param: is there a subset of $S$ that sum of all it's elements is equal to $k$?) problem and the proof that ss is an NPC problem by reduction from 3SAT.

I've found two PDF's that attempt to solve that, but the problem is, I don't have the foggiest idea how to 'explain in in my own words'.

Okay, some links ahead and questions related to them:

Here, on page 4th, there's a logic table for 3SAT clause that apparently proves why ss is NPC, but I don't get it - what exactly are those s and t values, and how does that table proves NPC'ness? And how k is computed in that table? It's simply not clear to me :(

Another link
on pages 5 and 6 there are another tables that appear out of nowhere with no explanation that I could understand.

So, if anybody knows what I'm talking about and could help me, please answer :). Or, if it's possible, can anybode give me a simple and straightforward proof why subset sum is NPC?


texts: How can we know if a Turing machine halts, given that it writes to finite memory?

texts:
I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine
writes to an arbitrary amount of memory, and false if it writes to a finite amount of memory cells. I am now thinking, can we somehow deduce if the machine halts based on if it writes to a finite amount of memory cells?

Link to related post: Turing machines: can a machine write to a finite number of memory cells, but not halt?


texts: Do we understand when metaheuristics are optimal? (gradient descent & simulated annealing in particular)

texts:
Gradient descent sometimes works better than simulated annealing and vice versa.

Are there conditions under which we can prove that, given perhaps a restriction on the set of allowed algorithms, one of these is optimal for solving an optimization problem?

I am particularly interested in those two examples, but in general interested in this question for metaheuristics for search and optimization problems.

(The no free lunch theorems show that (for certain problem statements) this is not possible in general, since for a uniform diatribution on problems, there usually isnt an optimal algorithm. However it might hold for special cases.)


texts: Why should leaf nodes in a red-black tree be black?

texts:
From the property of Red-Black Trees we know that:

All leaves (NIL) are black. (All leaves are same color as the root.)(Comren et al "Introduction to Algorithms")

But what is the reason that we should enforce them as Black, even though they're NILL's?


texts: Is such variant of SAT always satisfiable?

texts:
Let we have a SAT instance where every clause has length $\ge3$ (when length $2$ is allowed, it can be unsatisfiable) and each pair of literals appear only once.

Non-example: $(x\lor y\lor z)\land(x\lor y\lor t)$. Here a pair $\{x,y\}$ appears twice.

Example: $(x\lor y\lor z)\land(x\lor\overline y\lor\overline z)$. $\{x,y\}$ and $\{x,\overline y\}$ count as different pairs.

Another example is a clause $(x\oplus y\oplus z)$ reduced to CNF.

So, do there exist an unsatisfiable formula under these restrictions?


texts: Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?

texts:
For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.

My attempt to prove this was using a contradiction argument, supposing there was a common edge across 2 different min-cuts. Also, there is an edge in one min-cut that does not exist in the other, and idem for the other cut. Name these e1 and e2.

I managed to prove that the common edge must be an edge on a path between an end-point of e1 and one of e2.

There is a figure I drew to understand the situation better:


texts: Stroke Width Transform: Gradient Direction Computation

texts:
I've been trying to implement this paper from Boris Epshtein, Eyal Ofek, and Yonatan Wexler, the pioneers of Stroke Width Transform .

Having a simple image with random texts, that underwent gray scaling. Then I have produced two edge maps using two different algorithms for output comparison (for later) , Sobel and Canny (I'm also planning on Prewwit or other edge detection algorithms). I also have gradient maps x and y, using sobel.

on the segment of computing the gradient direction, given the equation:

theta = arctan( Gy / Gx )

where:

theta = is the resulting angle
Gx = is the X gradient component
Gy = is the Y gradient component
(both Gx and Gy are from the gradient maps)

I got a bit confused. If the value of Gx is 0 (zero), and we all know dividing by zero is undefined (some say it's infinity), so are we going to make theta infinity or just 0 (zero)?


texts: Can the structure of a "Complete Binary Tree", be uniquely identified if only its pre-order or post-order or in-order traversals are given?

texts:
I am unable to reason if we can construct a complete binary tree if only one of the following 3 traversals is given: pre-order, post-order, in-order.

The following is the definition of a complete binary tree:

  A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

The above definition has been taken from this link:
https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

It would be helpful if someone can prove or intuitively explain why we can or cannot uniquely construct a complete binary tree if only one of its 3 traversals is given?


texts: Calculating Size of parts of tree cut by an edge in a tree

texts:
Suppose that there are $n$ nodes, and that edge $e$ of weight $w_e$ cuts the tree into parts of size $k_e,n-k_e$. Then the average distance is
$$
 \sum_e w_e k_e (n-k_e).
$$
For example :
n=6,k=6 list=[1,2,3,4,5,6]

                    Node--------> 1
                                   \(1)<-----------Weight
                                    \
                                     3
                                (3) / \(2)
                                   /   \
                                  4     2
                             (4) / \ (5)
                                /   \
                               5     6

in this case we get
$$
\ (1 \cdot 1 \cdot 5 + 2 \cdot 1 \cdot 5 + 3 \cdot 3 \cdot 3 + 4 \cdot 1 \cdot 5 + 5 \cdot 1 \cdot 5) ={87}
$$

I'm storing the tree using adjacency lists.

1 approach might be to calculate size of elements of the list of the vertex connected by that edge recursively. For eg here if I cut $3-4$ I go the list of $4$ that contains $5,6$ then for every element in $4$ I go their list and calculate size of them and the vertex in it i.e go to list $5$ and $6$ and calculate size of their list. But I think this might be wrong or too long.

Now how do I find out the value of $k_e$ in the tree in a better and fast way?


texts:
F(n) = n-100
G(n) = n-200

I am trying to show the asymptotic relationship between these two functions using limits.

I take the limit n->∞ f(n) / g(n) and I get the result 1 which is constant c.

From the Big O theorem,

From the Big Omege theorem,

My question is: How I supposed to determine whether they are f = O(g(n)) or f = Ω(g(n))

In general, what is a good way to find the relationship between given two functions?


texts:
today in my class my professor mentioned that
Cache misses becomes more expensive as the speed of the processor increases

But he didn't explain the reason. I searched this statement over the internet and found no answer whatsoever.
According to me, this statement is true because, when the speed of the processor increases it can execute more instructions at a given clock cycle, thus a miss leads to a stoppage of more instructions from executing. So cache misses becomes expensive as processor speed increases. Is my thinking correct or am I doing it all wrong?


texts: Maximum sum after splitting into subarrays taking difference of maximum and minimum of each one

texts:
I was asked this in a hiring challenge that I gave today on HackerEarth:
Question/Problem statement:
Given an array, split them into several subarrays(possibly zero) such that you obtain maximum sum of difference between maximum and minimum in each of those subarrays.
Examples:
[1, 2 , 1 , 0, 5]

You can split them into 3 subarrays [1,2] , [1],  [0,5].
Through this split, you can obtain maximum sum like (2-1) + (1-1) + (5-0) = 6.
Another example:
[1,4,2,3]

You can split them into 2 subarrays [1,4] , [2,3].
Through this split, you can obtain maximum sum like (4-1) + (3-2)  = 4
Constraints:

Array length can be up to 106.
Array values can be between -109 to 109.

My attempt:
I made a brute force DP attempt which was partially accepted. Below is the approach.
long[] dp = new long[N + 1];

for(int i = N-1;i >= 0; --i){
    dp[i] = 0;
    int min = A[i],max = A[i];
    for(int j = i; j < N; ++j){
        min = Math.min(min, A[j]);
        max = Math.max(max, A[j]);
        dp[i] = Math.max(dp[i],max - min + dp[j + 1]);
    }
}

print(dp[0])

Issue:
Can anyone share with me how this can be solved efficiently?


texts: Is this adjustment to an rms calculation valid?

texts:
I want to calculate the RMS AC value of a signal made up of several thousand readings every second. The processor that I am using doesn't have enough memory to store a whole second of data, so I want to calculate it the sum of squares the fly.
This is the normal formula to calculate the RMS AC value, where you have to know the mean for the whole second before you can calculate the RMS:

ac_rms = sqrt (sum(square(reading-mean)) / n)

Would I get the same result if I instead use the mean from the previous second, and then apply a correction afterwards?

ac_rms = sqrt (sum(square(reading-prev_mean)) / n) - abs(mean - prev_mean)


texts: Alternative formulation of complexity class $BPP$

texts:
In Aurora and Barak, they give the following alternative definition of $BPP$:

What is the meaning of the subscript to $Pr$? Is that $Pr_{r \in_R \{0,1\}^{p(|x|)}}$? My guess is this is supposed to represent $poly(|x|)$ many coin toss results, but what is $R$? And why is this a subscript to $Pr$?


texts: User recognition through keystroke pattern

texts:
Hello thank you for taking time looking at this question. Is it possible to determine the keystroke patterns for a certain user?

My idea is that, when the user enters their username & password it must contain a specific keystroke pattern that when analyzed it could probably predict the actual user and able to differentiate other user that might know the exact username and password from hacking or entering the account.


texts: Recommendations for machine learning book?

texts: I am a microbiologist and I am currently self-studying machine learning from some open lecture videos. I am finding it pretty difficult to understand proofs that are somewhat "obvious", my poor mathematical knowledge is to blame for that. Can you please recommend a text-book that deals with the mathematical proofs of the theorems? Or approaches machine learning from the mathematical side?


texts:
So I know that $\log^*$ means iterated logarithm, so $\log^*(3)$ = $(\log\log\log\log...)$ until $n \leq 1$.

I'm trying to solve the following:

is

  $\log^*(2^{2^n})$

little $o$, little $\omega$, or $\Theta$ of

  ${\log^*(n)}^2$

In terms of the interior functions, $\log^*(2^{2^n})$ is much bigger than $\log^*(n)$, but squaring the $\log^*(n)$ is throwing me off.

I know that $\log(n)^2$ is $O(n)$, but I don't think that property holds for the iterative logarithm.

I tried applying the master method, but I'm having trouble with the properties of a $\log^*(n)$ function. I tried setting n to be max (i.e. $n = 5$), but this didn't really simplify the problem.

Does anyone have any tips as to how I should approach this?


texts: How to detect when to use radix sort in runtime

texts:
I'm implementing a stable integer sorting algorithm, I've chosen radix sort. I've tested LSD vs MSD implementation, wrote MSD/LSD hybrid implementation to reduce bandwidth pressure. The repo is here: https://github.com/KirillLykov/int-sort-bmk
Now some Figures to discuss.
First of all, radix sorts outperform significantly stable_sort on shuffled unique values in the range 0..N, where N is number of elements in the array:

On an input of randomly generated (uniform) numbers in the range 0..1e9, LSD outperforms other sorting algorithms, but MSD doesn't:

I don't have a good explanation for the last observation.
But it hinted to develop a combined radix sort implementation which will rely on MSD first and when the size of the range is smaller than 2^14 use LSD.
I've benchmarked these implementations on different distributions:

Observation is that although radix sort outperforms on random data, it performs poorly on some specific cases.
I think that a good approach is to define a criterium when/when-not use radix sort depending on the input data.
This approach was implemented in boost::spreadsort -- knowing the size of the input, min/max values they make a decision whether to use bucket sort one more time or to rely on another sorting algorithm. See for example boost::spread_sort implementation
Probably, it is possible to adapt the same analysis for radix sort yet not sure because I couldn't reverse engineer the the math behind these checks (I've read the report).
So the question is you have any ideas on how to develop criterium for using other sorting algorithms based on some (cheap to compute) observations about the input data?


texts: Pseudo-dimension of a subset of affine functions

texts:
Let's say there are two sets of affine functions.

$\mathcal{A} = \{ax +b \mid a,b \in \mathbb{R}\}$
$\mathcal{H} = \{2x + 1, x, 3x + 4, 4x\}$

I know that the $\mathrm{Pdim}(\mathcal{A}) = 2$. From my understanding the $\mathrm{Pdim}(\mathcal{H})$ is also equal to 2 as I can find $\{x_1, x_2\}$ and $z_1, z_2$ such that for all subsets $T \subseteq \{x_1, x_2\}$, there is a function $f \in \mathcal{H}$ such that $\forall x \in T, f(x) \geq z_1$ and $\forall x \notin T f(x) < z_1$.
Is my intuition correct?


texts: Remove duplicated in array with best performance

texts:
I am trying to remove duplicates from an array using the following two algorithms

   void PrintDuplicates(int[] arr)
   {
       if (arr == null)
           throw new ArgumentException("arr can't be null.");

       Hashtable table = new Hashtable();

       for (int i = 0; i < arr.Length; i++)
       {
           if (table.ContainsKey(arr[i]) == true)
           {
               // Console.WriteLine(i);
           }
           else
           {
               table.Add(arr[i], "");
           }
        }
    }

    void PrintDuplicatesWithSort(int[] arr)
    {
        if (arr == null)
            throw new ArgumentException("arr can't be null.");

        arr.ToList().Sort();

        for (int i = 0; i < arr.Length - 1; i++)
        {
            if (arr[i] == arr[i + 1])
            {
                // Console.WriteLine(i);
            }
        }
    }

Time complexity of the first algorithm to my understanding is O(n), while time complexity of the second is O(n) for sorting plus O(n-1) for the loop meaning total of O(2n-1).

However when I benchmark the code on this array int[] arr = { 4, 2, 5, 4, 1 }; the one with the higher complexity performs two times better. This implementation is using .net which uses insertion sort and implementation of hashtable that searches in O(1) according to their documentation. What am I missing here?


texts: Why does restricting size of input for NP complete problem imply a runtime of O(1)?

texts:
I've seen this statement mentioned a few times here on cs.stackexchange and have not been able to follow the logic.  The statement is 'If you restrict the input size of the problem then solving that problem (even SAT) can be done in O(1)'.

So say I restrict the size of SAT to N = 1000, now that means that solving SAT for any N <= 1000 can be done in O(1)?  That doesn't quite follow.

Can someone shed some light on this concept?


texts: Why Iterative-Deepening-DFS requires O(b*d) memory?

texts:
After reading about iterative deepening depth-first search on Wikipedia, I could understand that it just limits the depth upto which dfs can go in one iteration/call.

However, I could not understand why it is said that it requires $O(b \times d)$ memory, where $b$ is fan-out of nodes i.e. children and $d$ is max-depth.

Since it is just doing DFS multiple times, it should also only need $O(d)$ memory.

Thinking more, I thought that may be the entire graph can not be put in memory and $O(b\times d)$ is the part of graph required to be kept in memory. But does that make DFS also have $O(b\times d)$ memory requirement ? But even this does not like a good argument, because since during traversal if we are fetching the new nodes from some storage, we can do so also with $O(d)$ memory.

Also the Wikipedia page examples lead me to infer that it does not store visited[node_id] information about the nodes which stores whether node with id node_id is visited till now or not. This made me infer that graph is big.

Edit: After thinking further i think that it is right about $O(b \times d)$, since it is iterative-dfs rather than recursive-dfs. In recursive-dfs we usually take memory used by function call stack for granted. In iterative-dfs, we can find right memory-requirements. Since, now we can not implicitly remember back-tracking, we have to put all children on the stack and hence if we are going to $d$ levels, we need $O(b\times d)$ memory.


texts: How expensive is it to verify that a gate is universal?

texts:
I know that a NAND gate is considered universal because we can use it to implement an AND, OR, and NOT gate.
Given an arbitrary gate, or set of gates, how many operations would it take to verify if these gates are universal (by brute force), and does there exist a more efficient way to do this? How expensive is this in general?
With the example of the NAND gate we can construct a NOT, AND, and OR, pretty easily, but is there a systematic way to do this?
More specifically, assume we are given $n$ two input, one output gates, where the gates are specified as a truth table.
Is there a way to also generalize this to, given $n$ gates, in which all the gates take $m$ inputs and 1 output, how expensive would this be?


texts: Algorithm for clustering points in $\mathbb{R}^2$ based on pairwise distance (percolation graphs)

texts:
I haven't been able to find literature on the efficient solving of the following problem.

Given $n$ random points $x_i \in (0, 1)^2$ the unit square, obtain the flat clusters of points, such that two points are in the same cluster if their pairwise distance $d(x_i, x_j) < r$, where $r < 1$ is a fixed parameter of the problem.

The naive solution checks each pairwise distance, therefore completing in $\mathcal{O}(n^2)$ time. Is there a faster way, assuming $n$ large and $r \ll 1$?


texts: Why H-trivial monoids correspond to the variety of aperiodic monoids

texts:
I have two similar questions, one about the H-trivial monoids and one about the R-trivial monoids.

I cannot see the reason why H-trivial monoids, i.e., the monoids where H induced classes are singletons, coincide with the variety A of aperiodic monoids, also characterized as the monoids that satisfy the monoid equation $x^\omega x=x$.
Similarly, I don't understand why R-trivial monoids, i.e., the monoids where R induced classes are singletons, coincide with monoids that satisfy the monoid equation $(xy)^\omega x=(xy)^\omega$.

Here

$x^\omega$ is defined as the limit $\lim\limits_{k\rightarrow\infty} x^{k!}$.
the relation $R$ is defined as $xRy \iff xM=yM$.
the relation $L$ is defined as $xLy \iff Mx=My$.
the relation $H$ is defined as $xHy\iff xRy \land xLy$.


texts: How to find all shortest paths between two nodes in a weighted undirected graph?

texts:
How to find all shortest paths between node 1 and N in a weighted undirected graph? There can be multiple edges between two nodes.
I want to find all nodes that can be on a shortest path. For example:

10 11
1 2 1
1 3 1
3 4 2
4 5 1
5 6 1
5 10 2
1 7 1
7 8 3
7 9 2
9 10 2
8 10 1

The answer is

1
7
8
9
10

because there are two shortest ways

1 7 8 10

and

1 7 9 10