texts: How to compute linear recurrence using matrix with fraction coefficients?

texts:
What I'm trying to do is generate Motzkin numbers mod a large number $10^{14} + 7$ (not prime), and it needs to compute the $n$th Motzkin number as fast as possible. From Wikipedia, the formula for the $n$th Motzkin number is defined as following:

$\qquad \displaystyle \begin{align}
  M_{n+1} &= M_n + \sum_{i=0}^{n-1} M_iM_{n-1-i} \\
          &= \frac{2n+3}{n+3}M_n + \frac{3n}{n+3}M_{n-1}
\end{align}$

My initial approach is to use the second formula which is obviously faster, but the problem I ran into is the division since modular arithmetic rule doesn't apply.

void generate_motzkin_numbers() {
    motzkin[0] = 1;
    motzkin[1] = 1;
    ull m0 = 1;
    ull m1 = 1;
    ull numerator;
    ull denominator;
    for (int i = 2; i <= MAX_NUMBERS; ++i) {
        numerator = (((2*i + 1)*m1 + 3*(i - 1)*m0)) % MODULO;
        denominator = (i + 2);
        motzkin[i] = numerator/denominator;
        m0 = m1;
        m1 = motzkin[i];
    }
}

Then I tried the second formula, but the running time is horribly slow because the summation:

void generate_motzkin_numbers_nested_recurrence() {
    mm[0] = 1;
    mm[1] = 1;
    mm[2] = 2;
    mm[3] = 4;
    mm[4] = 9;
    ull result;
    for (int i = 5; i <= MAX_NUMBERS; ++i) {
        result = mm[i - 1];
        for (int k = 0; k <= (i - 2); ++k) {
            result = (result + ((mm[k] * mm[i - 2 - k]) % MODULO)) % MODULO;
        }
        mm[i] = result;
    }
}

Next, I'm thinking of using matrix form which eventually can be speed up using exponentiation squaring technique, in other words $M_{n+1}$ can be computed as follows:
$$M_{n+1} = \begin{bmatrix} \dfrac{2n+3}{n+3} & \dfrac{3n}{n+3} \\ 1 & 0\end{bmatrix}^n \cdot \begin{bmatrix} 1 \\ 1\end{bmatrix}$$
With exponentiation by squaring, this method running time is $O(\log(n))$ which I guess the fastest way possible, where MAX_NUMBERS = 10,000. Unfortunately, again the division with modular is killing me. After apply the modulo to the numerator, the division is no longer accurate. So my question is, is there another technique to compute this recurrence modulo a number? I'm think of a dynamic programming approach for the summation, but I still think it's not as fast as this method.  Any ideas or suggestions would be greatly appreciated.


texts: Approximating a series for asymptotic upper bound

texts:
So I stumbled upon a question here to find an asymptotic bound for the recurrence
$$
T(n) = 4T(n/4) + \left( \frac {n} {\log n} \right)^2 $$

The solution shows a solution using master method to prove the answer as $O(n)$
However, I tried to solve it using substitution as:

$$T(\frac {n} {4^i}) = 4^{i+1} T(\frac {n} {4^{i+1}} ) + \sum_{j=0}^{i} \frac {n^2} {4^j {(\log \frac{n}{4^j})^2} }$$

I then get
$$
T(n) = 4^{x+1}(Base Constant) + \sum_{j=0}^{logn -1} \frac {n^2} {4^j {(log \frac{n}{4^j})^2} }$$
$x=\log n$

Now for the summation:
$$n^2\sum_{j=0}^{\log n -1} \frac {1} {4^j {(log(n) - j\log (4))^2} }$$

All logarithms to be taken base 4:
$n^2\sum_{j=0}^{\log n -1} \frac {1} {4^j {(\log (n) - j)^2} }$

Now, the first substitution I made was $t = \log n -j $

$n^2\sum_{j=1}^{\log n -1} \frac {4^t} {4^{\log n} {t^2} }$

= $n^2\sum_{j=1}^{\log n -1} \frac {4^t} {n {t^2} }$
= $n\sum_{j=1}^{\log n -1} \frac {4^t} { {t^2} }$

Using wolfram and wkipedia, the sum comes out to $Li2(4) -n Lerch Function(4,2,\log (n)-1)$

I could simple assume this is constant and that would prove my bound to be $O(n)$ as the master theore suggests, but I ahve no proof to bound the Lerch and dilogarithmic function.

Another substitution I tried was

$$ t=4^j (\log n -j)^2 $$
which gives me
$$n^2 H(n) - H((\log n)^2) $$ where $H(n)$ is the nth harmonic number
I again could not reach a bound for this, besides $\log (n) - \log (\log n) $
which is quite different from my first substitution.

If someone could help me with what error I'm making, or why the substitutions yield different results that would be great.


texts:
I don't consider myself very good at math, but nevertheless I enjoy solving optimization problems like the ones often asked in ACM ICPC (a college programming competition). I recently came across an issue while trying to solve one of such problems. I'd appreciate any help to find a linear algorithm (something better than $O(n^2)$ is still OK) for the following problem:

  Given a tree $T = (V,E)$ we want to find the size of the smallest set $V'$ such that $V'$ is a subset of $V$ and for every vertex $u$ in $V$ there's at least one vertex $w$ in $V'$ such that $\text{dist}(u,w)$ is less than or equal to $K$, where $K$ is a given natural number.

Here, note that $\text{dist}(u,w)$ is the length of the shortest path from $u$ to $w$ in the tree (in terms of hops), and tree $T$ is unweighted.

I'm very aware that there is a known greedy algorithm for $K=1$, which is in fact the cardinality of the minimum vertex cover. Solving for a general $K$ is what I'm interested in. I thought about several approaches but none of them seem to convince me. Do any of you know how to approach this?


texts: Boolean logic: why is the "opposite" of and equal to or?

texts:
In boolean logic, why is the "opposite" of AND (&) equal to OR (|)?
For example, why would  !(A & B) be equal to (!A | !B)?
I understand that not A would simply be !A, but why does AND change to OR?


texts: Searching and inserting in $O(n)$ when $n$ is the size of the key

texts:
Edit: The solution to my problem is called a trie ; according to Section 8.1 of Peter Brass book "Advanced Data Structures", for a given alphabet $A$ and a word $w$ of length $n$ on this alphabet, a trie can search $w$ in $O(n)$ and insert or delete $w$ in $O(|A| n)$. Since in my case $|A|=2$, all these operations are performed in $O(n)$. Hooray !

Context :

I am trying to put an upper bound on the worst case complexity of an algorithm. In that algorithm, I have an arbitrarily big positive integer $n$, and a map in which keys are sequences of bits of length $n$. My algorithm makes use of the INSERT and SEARCH operations in that map.
So I am searching for a data structure with the least possible worst case complexity (with respect to $n$) for INSERT and SEARCH.

My first idea was : let's assume that the map is implemented with a red-black tree. Red-black trees perform SEARCH and INSERT in $O(\log m)$ (where $m$ is the number of nodes in the tree). In the context of my algorithm, there is at most $2^n$ different keys, so insert and search should run in $O(n)$.

Problem :

Binary trees usually assume that the keys are integers, which allows to compare two keys in $O(1)$. But since $n$ is not bounded, the length of my sequences can be greater than the encoding size of integers ; then it does not seem correct to just consider that my key can simply be treated as integers and compared in $O(1)$, right?

Question:

Do there exist data structures that would allow me to insert and search in $O(n)$ (worst case) with respect to the size $n$ of the key ?

What I have for now:

1: I suppose I still can use red-black trees, but comparison between two sequences of bits of length $n$ would be $O(n)$, and then INSERT and SEARCH would become $O(n^2)$, which is not nice.

2: I have come up with a very simple kind of tree that would perform INSERT and SEARCH in $O(n)$, and I suppose someone, somewhere, did somehow the same thing but better (however, I did not find it). My solution goes like this :

Keys are only stored in the leaves of the tree, and leaves are at distance $n$ from the root
When searching or inserting, we recursively go down from the root ; on any given non-leaf node that is at distance $i$ from the root, we look at the $i$-th bit of our key : if it is 1 then go right, if it is 0 then go left.

I did not find any data structure based on this principle, but if it exists, that would be a good solution to my problem.


texts: How do I show that an equivalence class of a language containing an empty string is infinite

texts:
The question is as follows:

  Let $L$ be a language (not necessarily regular) over an alphabet. Show
  that if the equivalence class containing the empty string $[ \epsilon ]$
  is not $\{ \epsilon \}$, then it is infinite.

How do I go about answering this? Would I need to use Myhill-Nerode theorem? From what I've read there's a corollary from the theorem that if a language defines an infinite set of equivalence classes, it is not regular. I'm not sure if that helps answer my question though.


texts: Detecting face like patterns using CNN based face detector

texts:
I have a CNN based object detector trained on WIDER Face dataset. It can successfully detect human faces in a given image.

Now, I am trying to detect abstract face and minimalistic face patterns in clouds or houses etc but having no success.

Initially, I thought I could lower the detection threshold to detect such patterns, but such scheme didn't work.

My question is there any way other than collecting and labelling such training examples (face like patterns) to solve this problem.


texts: Valgrind: what is the difference between a store and a modify?

texts:
I am using the Vlagrind lackey tool to examine the full memory reference string of a running computer program and wonder what the difference between a "store" and a "modify" might be - and do these differences reflect a real difference in category of memory manipulation, or are they merely a convenience for the user/programmer of Valgrind's lackey tool?

The comments on the lk_main.c source code give these examples of (a) A store:

movl %eax, (%ebx)

And (b) a modify

incl (%ecx)

I appreciate this is a question about a specific piece of software, but what I really want to know is if it is valid to consider stores and modifies as, in effect "stores" - as much texts on memory seem to regard the two basic operations as load (read) and store (write).


texts: How to define the stability (or convergence) of a ordering of a list of node

texts:
I have a problem which requires ordering nodes in a graph based on some given statistics. However, the given statistics of each node may be very hard to compute. Thus, I will use some sampling techniques to compute approximate statistics for each node. With more samples, the approximate estimated statistics will be more close to the exact one.

However, I want to terminate the sampling process when the ordering of nodes based on the statistics is stable. In this problem, I do not need to know the exact statistics of each node. The right ordering of these nodes is what matters.

So, my question is that is there any metric to define the stability of a ordering? How can I make sure that the ordering converges such that the ordering will not be changed notably?


texts: What problems of procedural programming does OOP solve in practice?

texts:
I have studied the book "C++ Demystified". Now I have started to read "Object-Oriented Programming in Turbo C++ first edition (1st edition)" by Robert Lafore. I do not have any knowledge of programming which is beyond these books. This book might be outdated because it's 20 years old. I do have the latest edition, I am using the old because I like it, mainly I am just studying the basic concepts of OOP used in C++ through the first edition of Lafore's book.

Lafore's book emphasizes that "OOP" is only useful for larger and complex programs. It is said in every OOP book (also in Lafore's book) that procedural paradigm is prone to errors e.g. the global data as easily vulnerable by the functions. It is said that programmer can make honest errors in procedural languages e.g. by making a function that accidentally corrupts the data.

Honestly speaking I am posting my question because I am not grasping the explaination given in this book: Object-Oriented Programming in C++ (4th Edition) I am not grasping these statements written in Lafore's book:

  Object-oriented programming was developed because limitations were discovered in
  earlier approaches to programming....
  As programs grow ever larger and more complex, even the structured programming approach begins to show signs of strain...
  ....Analyzing the reasons for these failures reveals that there are weaknesses in the procedural paradigm itself. No matter how well the structured programming approach is implemented, large programs become excessively complex....
  ...There are two related problems. First, functions have unrestricted access to global data. Second, unrelated functions
  and data, the basis of the procedural paradigm, provide a poor model of the real world...

I have studied the book "dysmystified C++" by Jeff Kent, I like this book very much, in this book mostly procedural programming is explained. I do not understand why procedural(structured) programming is weak!

Lafore's book explains the concept very nicely with some good examples. Also I have grasped an intuition by reading Lafore's book that OOP is better than procedural programming but I am curious to know how exactly in practice procedural programming is weaker than OOP.

I want to see myself what are the practical problems that one would face in procedural programming, how the OOP will make the programming easier. I think I will got my answer just by reading Lafore's book contemplatively but I want to see with my own eyes the problems in the procedural code, I want to see how the OOP style code of a program removes the foregoing errors that would happen if the same program were to be written using procedural paradigm.

There are many features of OOP and I understand it is not possible for someone to explain me how all these features removes the foregoing errors that would generate by writing the code in procedural style.

So, here is my question:

  Which limitations of procedural programming does OOP address and how does it effectively remove these limitations in practice?

In particular, are there examples for programs which are hard to design using the procedural paradigm but are easily designed using OOP?

P.S: Cross posted from: https://stackoverflow.com/q/22510004/3429430


texts:
This post says

  Binary Space Partitioning Trees are a
  generalization to dimensions > 1 of binary search trees

which indicates the binary search trees lives in 1d space.

Is my understanding right?


texts: Choosing which workers (limited number) to use in a binary assignment problem?

texts:
First of all, I am not completely sure whether this problem belong to the category of assignment problems so feel free to correct me in this case.

The problem:

We are given a set of $m$ workers $A = \{ a_1, a_2,...a_m \}$ and a set of $n$ tasks $T = \{ t_1, t_2,...,t_n \}$. Each worker either can or cannot perform any given task and there is no cost associated with a task. The set of tasks that can be performed by a single worker $a_i$ is $T_{a_i} \subset T$. The set of tasks that can be performed by a subset of $s$ workers is given by the union of the tasks each individual worker can perform $\bigcup_{i=1}^{s} T_{a_i}$ (not necessarily the first $s$ workers).

The problem is to select $s$ workers such that the number of task that can be performed is maximized, i.e. maximize the number of elements in $\bigcup_{i=1}^{s} T_{a_i}$.

I couldn't find which category of problems this belong to, let alone any solutions. Any help in this matter would be greatly appreciated!


texts: Why don't we emphasize "length of input string" when considering time complexity of sorting algorithms?

texts:
The knapsack problem is $O(c\,n)$ where $c$ is the capacity of knapsack and $n$ is the number of items. Yet it's exponential because the size of the input is $\log(c)$.

However, why don't we emphasize length of input in other algorithms? To name one example, what would be the input size $n$ and worst case time complexity $T$ of the following input when using insertion sort:

111111111,101,11,10,1,0

Answer A: $n=6$, $T=O(n^2)$
Answer B: n = space(all_digits)+space(delimiters_between_numerics)

If B is correct, what is the time complexity $T$?


texts: Find hamming codewords in r=2^k dimensions

texts:
There is the original problem, and an equivalent problem.

The equivalent problem: construct a set $A$ that contains bit arrays of length $r-1$, where $|A|=2^{r-1}/r$ and $hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$.

Misha Lavrov gave an excellent answer on Math.SE that solves the original problem. However, I don't get his construction.

If you could prove that his algorithm solves the problem for any $r=2^k$, or provide your own algorithm that solves the problem / equivalent problem for any $r=2^k$, I'd really appreciate it.

The original problem: choose $2^r/r$ bit arrays, where each bit array is of length $r$, and $r=2^k$ for all $k \ge 2$, such that the chosen arrays can be split into 2 sets, $A$ and $B$, where

$|A|=|B|=2^{r-1}/r$
$\forall x \in A.(\exists y \in B.(hamming \space distance (x, y) = 1))$
and $\forall y \in B.(\exists x \in A.(hamming \space distance (x, y) = 1))$
$hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$
$hamming \space distance (i, j) = 3 \quad \forall i, j \in B, \space i \neq j$

Here is the answer for $k = 2$, where blue circles are chosen bit arrays.

(P.S. Instead of $n=2^r$ dimensions in my question on Math.SE, I used $r=2^k$ here, because Misha's answer referred to bit arrays of length $r$. I hope this is not too confusing.)


texts:
I'm wondering why if I increase the number of step in a set of simulation of a random walk on a grid the distance from the origin is higher.

If I can move on the grid in 4 directions, there are 0.5 chance of getting closer to origin and 0.5 of getting farther.

This is a simple javascript example (well, here maybe I made some other errors because the points ends always with a negative x and a positive y, or maybe I just cannot rely on javascript random function in this case)

var steps = 100; //number of steps for each simulation (initially)
var simulations = 100; //number of total simulation
var points = Array.from({length:simulations}, () => ({x:0,y:0})); // init the array of points from the origin

//the 4 possible moves
var moves = [{x:0,y:1},{x:1,y:0},{x:0,y:-1},{x:-1,y:0}];
//ranom util function
var random = (max) => parseInt(Math.random() * max)

for (var s=0;s < simulations;s++) {
    //note the steps are increasing: 100,200,300,...,1000
    for (var i=1;i <= steps * s;i++) {
        let move = moves[random(4)];
        //console.log(move)
        points[s].x += move.x
        points[s].y += move.y
        //console.log(s, move)
    }
    console.log(`simulation n.${s} total steps: ${steps*s}`, points[s].x, points[s].y, `distance: ${Math.abs(points[s].x) + Math.abs(points[s].y)}` )

}

EDIT: thanks to @GASSA I fixed my code, but watching the results I'm still in doubt: the distance actually is not increased (see the graph below). Not sure what's the problem..


texts: Efficiently finding duplicates in lists of numbers

texts:
I decided to try my hand at solving the knapsack problem.

My idea involved generating $i$ tables, where $i: 1 \le i \lt n$, and each cell of an $i$ table contains one of the possible sums of the objects to fit into the knapsack. The $i$ tables will then be sorted. Then for each of the $k$ numbers to be tested, I'll run a binary search on the sorted arrays.

I realised that there may be sums which repeat. I feel like recording them will be unnecessary waste of space.

So I want to determine if for any new number $k$ to be added to the list, if $k$ is a duplicate of any number in the list. It is trivial to just search the list, but this is too inefficient, and takes $O(n^2)$ operations, making the trade off with space complexity a bad deal.

I wanted a linear time algorithm for solving this problem. I thought of a function, which takes in inputs, and the function is such that if any new input is the same as a previous input, the function will provide a certain known output. This function should work in constant time or at worst, logarithmic time.

I have tried several means of constructing the function but they failed.


texts: Prove Undecidability: TM M enters each of its states on Input W?

texts:
Consider the following problem: given a Turing Machine $M$ and an input string $w$, does $M$ enter each of its states during its computation on input $w$?

How to prove that the problem is undecidable?

I was trying to prove undecidability by Rice's theorem which states that languages having non-trivial property are undecidable. But how can I adjust the problem to the theorem?


texts: What is the fine line between time series data anlysis and time series data mining?

texts: I am trying to do thesis work in Computer science and the data mining in time series is the relevant theme, however the analysis of time series is not (it is mathematics subject). What is the fine line? Analysis is about discovery and parameter estimation of the (stochastic) model of time series, but it seems to me that data mining should do the same as well, isn't it? What is the difference and how not to cross the line? Maybe data mining ir more general than analysis, because it handles also logical models, association rules, etc.?


texts: Calculate Stages in Non-Pipelined Processor

texts:
I have tried to attempt a question where I have to find the number of stages for non-pipelined processor(8085) for below program :-

MOV #40, R00
MOV #50, R01
MOV #60, R02
SUB R02, R01
ADD R02, R01
INC R01
SUB R00, R02
HLT

What will be the no. of stages and there list here?


texts: Communication allowed in the NC^i model?

texts:
I want to verify if I am correct in my interpretation of the $\mathrm{NC}^i$ model.

In this model the input is given to at most $O(n^k)$ processors and each processor takes at most $O(\log^i n)$ time to arrive at a solution.

Can the processors communicate on any intermediate data?

How is the result whether accept or reject announced?

A fine grained problem

So the output of the algorithm can depend on partial results computed on previous processors?

There are $O(n^k)$ processors. So even if each processor computes $1$ bit of intermediate data that is useful for all processors then reading the intermediate results will itself take $\Omega(n^k)$ time then there is no way processors can finish in $O(\log^in)$ time.

So what limitations are there in the length and dependency on intermediate results?


texts:
This is not homework, but from a past exam. I do not know how to solve this one at all. Can anyone please take the time and show me how to do these? Thank you.

  Prove that $5^n \in O(6^n)$, but that $5^n \notin \Theta(6^n)$. (Doing this shows that $6^n$ bounds $5^n$ from above, but that $6^n$ is not the tightest such bound.)

I am familiar with the definitions, but it seems that $5^n$ is clearly $\lt 6^n$. and $5^n$ is not $\gt 6^n$.


texts:
I am having trouble with this problem:

  Let N3SAT denote the non-satisfiability problem for 3CNF’s. Show that $N3SAT\leq_p
UNQ$ where in UNQ, given a CNF φ we want to know whether there is a unique satisfying assignment for φ.

I am given a hint that for every 3CNF ψ, I should construct a CNF φ (in polytime) such that ψ is a NO input for 3SAT if and only if φ is a YES input for UNQ.

What I'm having problem with is constructing the CNF from a 3CNF. Isn't a 3CNF just a case of a CNF.

So, from what I understand, once I get a CNF φ that gives a yes for UNQ, then that corresponding 3CNF will give a NO for 3SAT. So somehow the truth assignments will work out in a way that both conditions are solved.

Can someone help me out?


texts: Limits on the time of computation for a UTM simulating a TM

texts:
According to source page 20, theorem 1.9, it states that there is a universal Turing machine that can simulate any Turing machine with a time overhead of
$O(\log n)$.

Can a universal Turing machine exists with less overhead? Can we prove that no such universal Turing machine exists?

If not, can we at least prove a lower bound on the overhead?


texts: What algorithm to find end state probabilities

texts:
I need help identifying what algorithm I need to solve a problem. I'm not asking for programming help here, just identifying the algorithm.

Each row of a matrix represents a state. Each element corresponds to the count of how often the current state transitions to another state. Some states are final states and do not transition at all. Some states are not reachable. There is always at least one path to one of the final states.

I need to calculate the probability of reaching all of the reachable final states and the probability for each final state.

To make this explicit here is an example of what I'm trying to accomplish.

State matrix:
$$
\begin{bmatrix}
0& 1& 0& 0& 0& 1 \\
4& 0& 3& 2& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0
\end{bmatrix}
$$

First state is always 0.
State 1 is non-terminal.
State 2 has probability of 0.
State 3 has probability of 3/14.
State 4 has probability of 2/14 or 1/7.
State 5 has probability of 9/14.

If this is a stationary distribution, then that's what I need to code to solve the problem. If not is it something else.


texts:
There is this example of regular expressions:

$$(\Sigma\Sigma)^*= \{w\mid |w|\text{ is even}\}\,.$$

From that I understand the empty string is valid as a string of even length. Is this true?


texts: Randomized Algorithms: High-Probability vs. Expectation

texts:
Hopefully this question isn't too general, but I was wondering what the relationship is between randomized algorithms that perform well with high-probability and those that perform well in expectation. My question is motivated by the definition of a randomized $\alpha$-approximation algorithm given here, namely that it is a polynomial-time algorithm that produces a solution within $\alpha$ of OPT in expectation or with high probability. I also found that the first few pages of this source provides some good insight into the high-probability vs. expectation approaches, but I still have questions.

Can you always transform an algorithm that achieves an $\alpha$-approximation in expectation to one that achieves this with high probability, and vice versa? (Ostensibly by rerunning the algorithm multiple [a polynomial number] of times.)
If not, is one harder than the other to obtain? (I would think that if you fix $\alpha$, a high-probability algorithm would always be harder to find/less likely to exist. Or maybe you can always find one, but the approximation ratio will become worse.)

Thanks for the help!


texts: Compression Bounds - Determine and Visualize for hypothesis vs VC dimension

texts:
I want to visualize or calculate the compression bounds for hypothesis classes. I learnt how to figure out the VC dimension. Let's say I define two hypothesis class. For example:
$$
H_k = \{h ∈ (0,1)_X \mid |h^{−1}(1)| ≤ k\}
$$
and
$$
H_{decst} = \{h^i_a \mid a ∈ R, i ∈ (1,2)\}, \text{ where } h^i_a((x1,x2)) = 1[x_i ≤ a].
$$
For VC dimension, I showed The VC dimension of $H_{decst}$ is 2. We can shatter the two points $x_1 = (2,0)$ and $x_2 = (0, 2)$ with the four functions $h_{0.5}, h_{1.5}, h_{1.5}, h_{2.5}$.
Also, It is not hard to see that $H_k$ shatters any set $C ⊆ N$ of size $k$, but no larger
set, since the all-1 labeling can not be realized on more than $k$ points with
$H_k$. Thus, the VC-dimension of $H_k$ is $k$.
Similarly, I want to figure out the compression bounds for $H_k$ and $H_{decst}$.


texts: Is there an abstract machine that can capture power consumption?

texts:
When reporting algorithmic complexity of an algorithm, one assumes the underlying computations are performed on some abstract machine (e.g. RAM) that approximates a modern CPU. Such models allow us to report time and space complexity of algorithms. Now, with the spread out of GPGPUs, one wonders whether there are well known models where one can take into account power consumption as well.

GPUs are well known to consume considerable amount of power and certain instructions fall into different categories of power consumption based on their complexity and location on the sophisticated chip. Hence instructions, from an energy of view, are not of unit (or even fixed) cost. A trivial extension would be assigning weights to operation cost, but I'm looking for a powerful model where an operation/instruction might cost non-constant units of energy, e.g. polynomial amount (or even more complex e.g.: function of time elapsed since start of the algorithm; or taking into account probability of failure of cooling system, which will heat up the chips, and slow down the clock frequency etc.)

Are there such models where non-trivial costs and faults can be incorporated?


texts: How do we mathematically figure out if a SVM kernel function overfits?

texts: Looking at the kernel function (Gaussian, polynomial. chi-squared, etc) how do we figure out that changing which value will cause overfitting? In my perspective, if we increase (for example) the variance term in Gaussian kernel expression, bias increases and overfit decreases. Is my understanding correct? Can the same thing be done for chi-squared and polynomial functions?


texts: How would I algorithmically "stretch" polygons on a plane by re-scaling the distances between interior points?

texts:
I've been thinking about a computational problem and could use some guidance for how to go about developing an algorithm to solve it.

On a Euclidean plane, I have a polygon A, a set of points A* bounded by A, another polygon B (that does not intersect A), and another set of points B* bounded by B. What I want is to create a mapping between points in A* and B* (not necessarily one-to-one or onto), re-scale the distances between  mapped points (the rescaling can be different for each pair of points), and then "stretch" A and B so that mapped points are still contained within their bounding polygon but are the new distances away from each other. The polygons should maintain their shape to the greatest extent possible.

As a simple example, if A and B were squares of equal size centered along the X axis, A* consisted of the center point of A, B* consisted of the center point of B, and I wanted to halve the distance between those two points, I would stretch each polygon along the X axis towards the other by horizontally extending the top and bottom edges, horizontally shift the inner edges towards each other, and leave the outer edge unchanged. The new polygons would look like rectangles that are still centered along the X axis but with each of their center points and inner edges moved a quarter of the original distance towards one another.

Another way of visualizing the transformation is to use the raisin-in-bread analogy https://www.wwu.edu/skywise/hubble_pudding.html commonly used to explain the expansion of the universe. If the points in A* and B* were raisins, the algorithm would show how shapes around those points are distorted if space-time were expanding or contracting between pairs of points.

Ideally, a solution would generalize to any number of polygons with any number of mapped interior points.

Thanks


texts:
I'm struggling to understand this factorial algorithm.

Falling(n, m):
    if m = 0
        return 1
    if m = 1
        return n
    return Falling(n, floor(m/2))*
           Falling(n - floor(m/2), ceil(m/2))

The algorithm should compute $n!/(n-m)!$

I'm analyzing it in the case of n = m, i.e it returns n! Now I'm getting the correct results from my implementation of it in Java, but the correctness of it has shaking my head.

How should I approach this?


texts: Steps to create a heuristic for solving a problem

texts:
I am completely new to AI and doing self-learning to acquire this knowledge.
I went through the different available search algorithm like BFS, DFS and A* but something that I can't understand is a heuristic function that needs to be embedded in these algorithms. I am fine with algorithms but I don't know how we find a good heuristic function for every problem. Is there any steps that needs to be take to achieve a heuristic?

Any comment would greatly appreciated.


texts: How much time (in hours) will it take to check if the number with 20 binary digits is the prime number?

texts: How much time (in hours) will it take to check if the number with 20 binary digits is the prime number, in problem it's mentioned that for number with 10 digits it took 1 hour it's also said that the number has been checked using AKS pirmality test and it's also given that log(n) is the lenght of the number to be verified.


texts: What is the formal statement of the dining philosopher's problem?

texts:
I've read about it in a few places and I'm not sure I get it.
Are the philosopher's allowed to act simultaneously?
Do they each take 1 action simultaneously, then go on to their next action?


texts: Proof of Minsky Papert Symmetrization technique

texts:
I frequently hear about the Minsky-Papert Symmetrization technique in many papers with a reference to the book of Minsky. I could not locate the book online. Could someone supply me a proof of the symmetrization technique?

For instance, it is used in Lemma $5$ in this paper http://www.csee.usf.edu/~tripathi/Publication/polynomial-degree-conference.pdf


texts:
In the definition of in-place algorithm, from Wiki, " However, this form is very limited as simply having an index to a length n array requires O(log n) bits."
How does an array index requires log n bits?
For example, A[0], 0 here just take O(1) bits, right? It is just 1 number.
I guess my question is about how an array establish its index.
An array of size n has n space for its elements, and n space for storing the index numbers 0,1,2...
I assume I am wrong, but I don't know how.


texts: Hash functions and pathological data sets

texts:
So I'm watching an Algorithms course in Coursera, and we are currently discussing hash tables. He's talking about the importance of a good hash function, and about how an ideal hash function would be a "super clever hash function guaranteed to spread every data set evenly".

Then, he explains that the problem is that such a hash function does not exist (and that for every hash function there is a pathological data set), and that the reason for this is as follows:

Fix a hash function $h: U \to \{0, 1, 2, ..., n-1\}$. By the Pigeonhole Principle, there exists a bucket $i$ such that at least $|U|/n$ elements of $U$ hash to $i$ under $h$. If a data set draws only from these, everything collides.

The bolded part is what's confusing me. Why does there exist a bucket $i$ such that at least $|U|/n$ elements of $U$ hash to $i$ under $h$? I can't really visualize what he means.


texts: Expected behavior of the maximum ranking generated in optimal assignment

texts:
Suppose n students have preferences over n different notebooks. Their preferences can be represented with a square matrix of size n where each column is a different permutation of the vector [1:n], where the first entry in the column represents the most desirable notebook for student 1, and so on. We are interested in the assignment of the notebooks to students that minimizes the sum of rankings.
For example, such allocation in the problem below
1    2    2
2    1    3
3    3    1
would be the allocation (1,2,3) with a ranking sum of 1+1+2=4.
My question is the following. If the matrix with preferences is chosen uniformly at random, what is the expected maximum ranking in the assignment that minimizes the sum of rankings? In the example above, this is 2. I am interested in the maximum value that occurs in expectation if one of the possible matrices is chosen uniformly at random.
Simulations show that for n=100, this is 6.44 and for n=200 this is 7.04.
See Expected behavior of an algorithm to minimize rankings for further details.


texts: Proving a solution for the $n$-Queens Puzzle

texts:
Given an $n$ x $n$ board, assume that $n \geq 5$ and that $n$ is not divisible by $2$ or $3$. Prove that the following positioning of $n$ queens $Q_0, Q_2, ..., Q_{n-1}$ works, i.e no two queens threaten each other:
For $0 \leq i \leq n-1$ we position the queen $Q_i$ on the field $(i, 2i \text{ } \pmod n)$.
Here we're using the ($x$-coordinate, $y$-coordinate) coordinate system, where $x$ describes the horizontal position, and $y$ the vertical. For example, in the formula above, $x$ would be $i$, and $y$ would be $2i \pmod n$.

My idea was to prove by contradiction and break up each case on how the queens are positioned to not threaten each other (horizontally, vertically and diagonally), but I can't see what follows. Can someone offer their thoughts or point me in the right direction?


texts: How do you read this context-free language?

texts:
say you want to make a Pushdown Automaton to recognize this language.

What exactly does the +1 mean? I see in the example it just pushes an a to the stack before arriving at an acceptance state but I don't quite get why.


texts:
I've read so many about the Coin Change problem, debates about wheather it is solvable using Greedy, Dynamic Programming and so on.

Nevertheless I cannot find an application of this problem.

What are applications of Coin Change problem?


texts: What is the difference between designing an algorithm that solves a problem and creating a TM that decides a language?

texts:
Question: What is the difference between designing an algorithm that solves a problem and creating a Turing machine that decides a language?
A turing machine "decides" the language if it "accepts" the language and enters a rejecting state for any input not in the language.
Don't really know what the difference is


texts:
The condition of the problem and the statement of the problem: Alice pays Bob for the fact that he, at the request of users, gives out files of interest to users. For example, the user is interested in the file #hash1. The user learns from Alice that this file is stored by Bob. The user connects to Bob and asks to start downloading the file #hash1 to his computer. Then there are two possible bad outcomes. Either Bob is dishonest and refuses to transfer the file to the user, or the user is dishonest and, after receiving the file #hash1 from Bob, lies to Alice and tells her that Bob did not send him anything.

My question is: are there any algorithms in cryptography that Alice will be able to determine the truth and not pay money to Bob (if he lies) or not stop cooperating with Bob (if the user lies)? At least partially. Thank you.

Personally, I thought that my problem relates to the topic of fair exchange (when the two sides exchange bit by bit interesting information and if one side begins to behave dishonestly, the second party immediately stops exchanging and the damage for it is minimal). However, this does not solve the problem that the user can simply lie and say that Bob did not send anything.
I just want to know if it's possible to control the work of a third-party server for Alice.


texts: Conjunctive Regular Path Queries and Subgraph Isomorphism

texts:
How do conjunctive regular path queries and subgraph isomorphism relate to each other? It seems that conjunctive regular path queries are a specialised form of subgraph isomorphism.

The follow is the definition of a conjunctive regular path query given in "Expressive Languages for Path Queries over
Graph-Structured Data":

  A conjunctive regular path query (CRPQ) $Q$ over a finite alphabet
  $\Sigma$ is an expression of the form:

  $Ans(\bar{z}) \leftarrow \bigwedge_{1\leq i \leq m} (x_i , \pi_i, y_i), \bigwedge_{1\leq j \leq t} L_j(\omega_j)$

  where,

  (i) $m > 0, t ≥ 0$,

  (ii) each $L_j$ is a regular expression over $\Sigma$,

  (iii) $\bar{x} = (x_1, \cdots , x_m), \bar{y} = (y_1, . . . , y_m)$
  and $\bar{z}$ are tuples of node variables,

  (iv) $\{\pi_1, \cdots , \pi_m \}$ are distinct path variables,

  (v) $\{\omega_1, \cdots, \omega_t\}$ are distinct path variables and
  each $\omega_j$ is among the $\pi_i$’s, and

  (vi) $\bar{z}$ is a tuple of node variables among $\bar{x}$ and
  $\bar{y}$.

  The atom $Ans(\bar{z})$ is the head of the query, the expression
  on the right of the $\leftarrow$ is its body.


texts: Approximating unique string occurrences using a small, fixed amount of memory

texts:
Is there a small-memory way to estimate how many unique strings have been encountered without needing to know the strings themselves?  The trick is that we only have a tiny amount of memory to track what strings we have seen.  Tiny like a 64 bit integer or 64 byte string. (The EZ infinite-memory solution is to keep a hash of the strings.)  The strings being tracked themselves can be very long.

To make sure "unique" is clear, let's say we receive four strings: "cat", "dog", "cow" and "cat".  We would count that as three unique strings as "cat" appears twice.

This method can be lossy!  Some hashing solution with collisions is perfectly acceptable.  Ideally the solution is more accurate for smaller amounts.  E.g. counting 2 unique strings, we can be pretty sure it's exactly 2, but if the method returns 200, that's probably a decent estimate. .

The partial solution I have been considering is:

Set the tracker value to 1
Set the counter value to 0
For each string, get its hash value.  If the tracker number is not evenly
divisible by the hash, then increment the counter and multiply the
tracker by the hash

The problem is that the tracker will quickly overflow and that will then (I assume) affect what numbers evenly divide it.


texts: CCS process for a drink dispenser with two different prices

texts:
A drink dispenser requires the user to insert a coin ($\bar c$), then press one of three buttons: $\bar d_{\text{tea}}$ requests a cup of tea $e_{\text{tea}}$, ditto for coffee, and $\bar r$ requests a refund (i.e. the machine gives back the coin: $\bar b$). This dispenser can be modeled by the following CCS process:

$$ M \stackrel{\mathrm{def}}= c.(d_{\text{tea}}.\bar e_{\text{tea}}.M + d_{\text{coffee}}.\bar e_{\text{coffee}}.M + r.\bar b.M)$$

A civil war raises the price of coffee to two coins, while the price of tea remains one coin. We want a modified machine that delivers coffee only after two coins, and acquiesces to a refund after either one or two coins. How can we model the modified machine with a CCS process?


texts: Given a set of points in the plane all laying on the axis, find the number of right angled triangles

texts: My approach:- I separated the x coordinates and y coordinates in 2 separate arrays..then i used the idea of pythagoras theorem by selecting three vertices(1 from x axis and 2 from yaxis and vice versa) but it's taking too much time..can anybody suggest me a better approach?


texts: Meaning of $\triangleright$ in programming language semantics

texts:
What does the symbol "$\triangleright$" mean programming language semantics?  I've seen it in the context of datatypes in and the evaluation of expressions in environments.

For example :

$$tenv \triangleright erht \implies tval $$

or

$$tenv[tval/x]\triangleright ebody\implies t\,.$$

Here, $tenv$ is an environment and $ebody$ is the body of some expression.


texts: How does lexical analyzer remove white spaces from source file?

texts: In compiler at phase lexical analyzer, how does lexical analyze strip out white spaces from source file?.


texts: Design a Turing Machine for binary addition

texts:
I have been working on the following problem:

Let $\newcommand{\bin}{\operatorname{bin}}\bin\colon \{0,1\}^* \to \mathbb{N}$ convert a binary representation of a non-negative integer to that integer, with the last symbol of the input being the LSB. For example, $\bin(110) = \bin(00110) = 6$ and $\bin() = 0$.
Design a Turing machine that decides the following language: $$\{x\#y\#z : x,y,z \in \{0,1\}^*
\text{ and } \bin(x) + \bin(y) = \bin(z) \}. $$

For solving binary addition, full adder seems to be a way to go. I was able to construct a half adder, now things are getting complex and I seem to be stuck, I need a way through which I can send a carry value back to a new half adder or something like that.
I have been using following sample input $1000\#0101\#1101$, which should be accepted since $8+5=13$.
Below is the state diagram I have constructed:

Sample Inputs and Expected Outputs


texts: Understanding access and insertion time of arrays

texts: Why do most implementations of arrays have constant access time and linear insertion time?


texts: Finding time complexity of a depth first traversal algorithm with a depth limit to get all node traversals starting from the root node

texts: What would be the time complexity of a depth-first traversal algorithm on a graph, that is simply trying to retrieve all nodes being visited from starting node up until a depth limit is reached (i.e. same node can be visited multiple times if cycles are present). The idea here is to retrieve an ordered list of nodes that are reached (regardless of the fact that a given node was visited previously). How would I approach this problem? Any helpful input or a link to a resource that I could refer to would be appreciated!


texts:
Regarding the quantum Toffoli gate:

is it classicaly universal, and if so, why?
is it quantumly universal, and why?


texts:
I have written an assembly program to store digits in a stack. And to print the digits I have used
loop2:
mov ah,2
int 21h
sub cl,1
jnz loop2

But this would only print them in reverse order as the SP is pointing to the last element,
Now, I have a very simple yet very interesting question, I was very curious to know
If I were to print it in the same way it was entered, how would I do that? I could use another stack but it would be quite complicated.


texts: Running-time cost of Tweaked Nested Loop

texts:
I understand that the following nested for-loop:

for(i=0; i<n/2; i++)
    for(j=0; j<n/2; j++)
         print(j)

has the runtime complexity of

which has a simplifed complexity of

but what is the resulting complexity of making j bound to i/2 in the inner loop? For instance:

for(i=0; i<n/2; i++)
    for(j=0; j<i/2; j++)
         print(j)

Would this be

?


texts:
Everyone knows "Garey & Johnson", which is my go-to reference whenever I need a problem to transform from for an NP-hardness proof. However I recently find myself in need of an APX-hardness proof, and I wonder if there is a similar (and more up to date..?) collection of problems that have been shown to be APX-hard.

Does anybody know of anything like this? I find it hard to believe that there is no website systematically collecting such problems, but my Google skills seem to be insufficient.


texts: Understanding Closest Pair Algorithm (CLRS)

texts:
I'm reading CLRS Section 33.4 Finding the closest pair of points. At exercise
33.4-2 they say

  33.4-2

  Show that it actually suffices to check only the points in the 5 array positions following each point in the array Y'

But I'm getting 4 array positions following each point in the array Y' will be suffice to check. See the fig below

Which possibility I'm missing. Can anybody point it out.


texts: What are the differences between Oracle Turing Machine and PAC?

texts:
I am having difficulty understanding the difference between PAC and Oracle Machines.  I cannot compare these two in terms of uncertainty and physical effort.
The degree of uncertainty we can tolerate in a system has been discussed ever since Turing. His oracle machines
answer questions with maximal uncertainty, and zero physical work, because they are oracles. They don't have to justify their answers.
His automatic machines, or a-machines, are what we now call standard TM. In the probabilistic
version, there is no new class of functions that we can compute which we cannot compute with deterministic TM.
The Probabilistic TM can decide which route to take depending on probabilities assigned to its transitions. In the simplest case of binary branching at every state and total random choice, it flips a coin about which route to take.
We know that in doing so we don't get anymore computable function than what we get with nondeterministic TM, but we might get to some answers more quickly.
PAC idea, however, changes things. 1-epsilon is the amount of uncertainty a PAC problem solver can tolerate in calling a solution 'approximately' correct. If epsilon=0, then you get maximal tolerance.
How this idea can be related to Turing's oracle, and to relation between certainty and amount of physical effort.


texts: Graham Scan - Why does the first and last points always belong to the convex hull?

texts:
Context

In a 2-dimensional space, suppose $p_0$ is the origin - the lowest point of the Convex Hull (CH), and suppose $p_1, ..., p_{n-1}$ are sorted by their polar angles. When applying Graham scam, I always observe that $p_1$ and $p_{n-1}$ are vertices of the Convex Hull (CH). For instance, consider the graph, for which $p_{n-1}$ is $p_{12}$.

Question

How can I show this formally, that $p_{n-1} \in CH$ and $p_1 \in CH$ for all instances?

My answer

$p_1 \in CH$ because $\angle p_{n-1}p_0p_1$ must be a left turn, since $p_0$ is the lowest point and $p_1$ has the smallest polar angle above $p_0$; similarly,
$p_{n-1} \in CH$ because $\angle p_{n-2}p_{n-1}p_{0}$ must be a left turn, since $p_0$ is the lowest point and $p_{n-1}$ has the largest polar angle above $p_0$.

Does this sound like a convincing proof?

Thank you in advance.


texts: Is set cover still NP-complete if you have a given k?

texts: Set cover is NP-complete given an arbitrary set $U$, a set $S$ of subsets of $U$, and an integer $k$. However, what if $k$ is always a constant 3? Is that problem still NP-complete?


texts: How to convert a context free grammar (could generate regular language) to a right-linear grammar

texts:
Consider the context free grammar:

$$S \rightarrow aSb \mid aSa \mid bSa \mid bSb \mid \varepsilon$$

It could generate regular language, which means it can be converted to a right linear grammar. Is there a general rule to convert CFG into a RLG? If there is no general rule, could you please show me how to convert this CFG to a RLG?


texts: If the load factor is a decimal (say 3.6), what is the length of each chain in a hash table that utilizes separate chaining?

texts: I understand that if the load factor were 2, then the length of the chain would be 2 for each index in the array, but what happens if the load factor is a decimal? Do we round up or down?


texts:
I have a question about contingent sentences. To my knowledge, contingent sentences are sentences that are neither tautologies nor contradictions.

In a textbook I read that a sentence might always be true and still be contingent.

The example given was as follows: If there never were a time when the universe contained fewer than seven things, it follows that the sentence "At least seven things exist" would always be true. Yet the sentence is contingent; its truth isn't a matter of logic. There is no contradiction in considering a possible world in which there are less than seven things.

Could someone please explain why this is the case? As well as explain the example to me?


texts: What are the axioms, inference rules, and (formal) semantics of lambda calculus?

texts:
Wikipedia says that lambda calculus is a formal system. It defines lambda calculus by giving its alphabet, and inductively describing what is inside its formal language.

Since lambda calculus is a formal system, what are its

axioms and
inference rules?

Does lambda calculus have semantics? If yes, how does an interpretation of lambda calculus look like as a mapping from what subset to another?


texts: Unable to understand a definition of an instruction in a compiler schedule

texts:
Recently I've accepted a job offer to work on compiler design. To be properly prepared I've decided to review the material. The book that is being used for that is Cooper and Torczon's Engineering a Compiler. That's the one we used in a class. On page 645 there is a definition of a schedule, but I can't figure out what it means

Here is the definition:

  Given a dependence graph $D$ for a code fragment, a schedule $S$ maps each node $n\in N$ to a nonnegative integer that denotes the cycle in which it should be issued, assuming that the first operation issues in cycle 1. This provides a clear and concise definition of an instruction, namely, the $i^{th}$ instruction is the set of operations $\{n \space | \space S(n) = i\}$

I can't understand what this is saying. Can someone phrase this in a simpler way?


texts:
I have a grammar like this:

A → BAB | B | ε
B → 00σ | ε

What is the meaning of σ in the second rule?


texts: Conversion from assembly program to low-level machine language

texts:
While studying COMPILER-DESIGN through an online book from Google Books, referenced as Compiler Design by A.A.Puntambekar, I got stuck across a line. Actually, I am more curious to know the inner-detail.

  The assembler converts the assembly-program to low-level machine
  language using two passes. A pass means one complete scan of the input
  program. The end of the second pass is the relocatable machine code.

Why the 2 passes for conversion and what are the phases involved like lexical analysis,syntax analysis,etc while conversion from assembly to machine-code??? I have very less/no idea about it.

If someone over here would like to describe those two-passes or link out to some good resources, I'd be thankful to him/her.


texts:
Given a Turing machine $M$, we say that $L(M) \in P$ if the language decided by the machine can be decided by some machine in polynomial time. We say that $M \in P$ if the machine runs in polynomial time. Note that there can be machines that run needlessly long but still decide a language in $P$. By Rice's theorem, we know that

$\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) \in P \mbox{ } \}$ is undecidable. Is it known whether:

$\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }M \in P \mbox{ } \}$ is also undecidable?


texts: Lower bound time complexity for obtaining an arbitrary entry in a hashtable

texts:
I just answered this question on StackOverflow, which asks for an efficient algorithm such that given a nonempty hashtable,
the algorithm should return a pointer to an arbitrary nonempty entry in the hashtable.
My answer was quite casual and I am not confident if my proof was correct.
I am rephrasing the problem statement below:

We are allowed to extend the insert()/remove() operations of a hashtable
We need to expose a get_arbitrary() operation that always returns a nonempty entry in the hashtable if it is nonempty, or nil if it is empty.
We are allowed to store extra data related to hashtable
Assume hash keys are uniformly distributed.
Assume insert()/remove() have memorylessly equal probability to be called on any key that exists in the hashtable.

This problem asks if it is possible to draw some relation on the lower bounds of the

time complexity of insert() $T_i(n)$
time complexity of remove() $T_r(n)$
time complexity of get_arbitrary() $T_a(n)$
space complexixty of any extra data we are storing, in addition to the original hashtable $S(n)$

One of the conjectures I thought of (as mentioned in the linked StackOverflow question) is $T_a(n) = O\left(\frac n{S(n)}\right)$,
but I am not sure if this is correct.
Also I am interested in knowing something can be said about how $T_a(n)$ relates to $T_r(n)$.


texts:
I am learning this MIT course, which gives this formula

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

is there a table to calculate this? like $O(n^{1.5})$, $O(n^{5})$ ?

what x takes would have O(x) give $c \cdot n$  where c is a constant,


texts: How to find running time complexity of divide and conquer method without Master Theorem

texts:
I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of $T(n) = aT(\frac{n}{b}) + n^clog^k(n)$ The reason behind it has to do with drawing a tree of the subroutines and see how each level k behaves, right?

Now suppose your divide-and-conquer algorithm can be described as the following:

$T(n) = T(\frac{n}{2}) + 1.5^n$

My guess is that this is $\theta(1.5^n)$ simply because it would seem this term dominates, but I have little logical backing for my guess. How would you find the big theta to this task?

My attempt to find the answer was to draw out the first few levels of the tree, finding:

Level 1: $T(n) = 1.5^n$

Level 2: $T(n) = 1.5^{\frac{n}{2}}$

Level 3: $T(n) = 1.5^{\frac{n}{4}}$

So it seems for level k (starting at 1), the task comes out to be $1.5^{\frac{n}{2^{k-1}}}$

So as the amount of levels increase, it seems the time to perform the task is decreasing by a factor of 2?

Any help is welcome! Hints are preferred, but if you wish to provide the full answer that is fine too.


texts: Polynomially reducing NP-Complete problem clarification

texts:
I am having trouble solving the following question.

I am given a following problem X: Given a graph G, we want to know whether there is an edge e in G such that G − e is 3-colorable.

I want to show that $X \leq_p 3Col$

My attempt is to look at the complement of G, and say that the complement of G shows us that the graph plus the edge is not 3-colorable if and only if the G - e is 3-colorable.

Does this make sense and is it correct?


texts: Do fully optimizing compilers for terminating programs exist?

texts:
In Andrew W. Appel's book, Modern Compiler Implementation in ML, he says under chapter 17 that Computability theory shows that it will always be possible to invent new optimizing transformations and proceeds to prove that a fully optimizing compiler will solve the halting problem: A program Q that produces no output and never halts can easily be replaced by its optimal representation, Opt(Q), being "L: goto L". So a fully optimizing compiler can solve the halting problem.

So my question is this: Does a fully optimizing compiler exist for terminating programs? My only thoughts are the following: Even though a program is guaranteed to terminate, it can still be arbitrarily complex, and for any concrete optimizing compiler, C, one could perhaps construct a program that takes C as input and somehow produces a worse program as some kind of corner case.

Also, What are the implications of restricting ourselves to terminating programs?


texts: How consistent heuristics guarantees A* optimality without adding same node to the frontier twice or more

texts:
Taken from Artificial Intelligence A Modern Approach :

Notice how a node doesn't gets added to the frontier twice in Graph-Search, And then take a look at this :

Now obviously this is not true as in the following example :

Bucharest will be added to the frontier first with path sibiu->fagaras->bucharest, while the second path which is more optimal will be omitted.

Am i missing something or is just a false claim?


texts: Undecidability of telling if a program returns true or false

texts:
Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are allowed to give any answer (but you have to halt and give some answer on all inputs).

Is this problem undecidable? My gut says that it should be, but I can't find a reduction to the halting problem. Given a Turing machine that may or may not halt, we can set up the machine to finish with a $0$ in the case that it halts, but can't finish with anything in the non-halting case, so the oracle could just say $0$ in this case without having to figure out whether in fact the machine halts.

Note that a reduction in the other direction is simple; if you can solve the halting problem, then given a TM that either finishes with $0$ or $1$, we replace the $1$-writing step with an infinite loop to create a new TM. If the new TM halts, we say "it writes a $0$" and if it does not halt we say "it writes a $1$". This answer is guaranteed to be correct as long as the TM in fact halts with a $0$ or $1$, so we can solve the original problem.


texts: Minimize sequence storage by overlapping prefixes

texts:
I bumped into this problem today, and after a bit of pondering, I think I have a solution in $O(n^3)$, which is better than no solution or an $O(n!)$ solution, but my answer still isn't great.  Can you beat my best answer?

The Real-World Impetus

Given a set of data $C$ that consists of nonoverlapping, nonempty, unique sequences $S_1, S_2, S_3, ...$ of atomic values.  Each sequence tends to have a lot of repeated values.

For example, in the code where I bumped into the problem, the sequences were initially something like this:

    9, 1, 1, 1, 1, 1;
    5, 5, 5, 3, 2;
    1, 1, 1, 1, 4;
    1, 7, 5, 5;
    4, 4, 4;
    ...

To access the data, there's a secondary table of offsets into the overall data to show where each sequence starts:  i.e., sequence $S_1$ starts at 1, and $S_2$ at 7, and $S_3$ at 13, and so on.  But this means that the sequences may occur in any order, and they may even overlap.

Given that the data could overlap, it occurred to me that by reordering the sequences, I could reduce the storage required.  For example, in the above data, I can reduce the size of the required storage by reordering the sequences as $S_1, S_3, S_5; S_4, S_2$:

    9, 1, 1, 1, 1, 1, 4, 4, 4;
    1, 7, 5, 5, 5, 3, 2;
    ...

By overlapping the prefixes and suffixes, we can store 16 values instead of the original 23, a considerable savings.

The Problem Statement

Generalizing this, the problem, then, is to find an algorithm for ordering an arbitrary set of sequences, so that the resulting ordering will have the maximum overall overlap of those sequences' prefixes and suffixes.

(And for what it's worth, I don't actually have to solve this for the code I was working on:  This is purely a question of academic interest at this point.)

My Best Answer

It's easy to "see" an optimal answer for trivial examples like the one above, but in the general case of a large number of sequences of arbitrary values, it gets hard quickly.  A greedy algorithm could likely at least give an acceptable answer in polynomial time, but that wouldn't be the true minimal answer.  And obviously, you can simply try every possible ordering, but $O(n!)$ is not a very nice solution either.

It occurred to me a possible solution might exist as a variation on a longest-path-through-a-weighted-graph problem.  You consider each sequence $S_1, S_2, S_3, ...$ as a node in a graph, and construct a directed edge anywhere $S_n$ has a prefix that matches a suffix of $S_m$ for all $n$ and $m$, weighted by the match length.  This results in a two-step solution:

Calculate all the edge weights.  The edge weights can be calculated trivially in $O(n^2)$, or maybe even in $O(n)$ using a trie constructed via dynamic programming.
Then for each vertex, use Dijkstra's shortest-path algorithm (or similar), inverted, to find the longest path for that vertex.  Of all the possible longest paths, then take the overall longest.  This is $O(n^3)$, or maybe $O(n^2\ log\ n)$ using priority queues.

I think this might work, with an overall time of $O(n^3)$ or maybe $O(n^2\ log\ n)$, but I haven't attempted to prove it for real (or implement it).  There might also be a better technique than Dijkstra's algorithm for "longest path in the graph when you don't care what node it starts or ends on."

Can you do better?

Here's the problem statement again:

  Find an algorithm that can efficiently order a set of sequences $S_1, S_2, S_3, ...$ such that there is maximal global overlap of their prefixes and suffixes.

Good luck; I'm curious to see if you can solve it better than I could!


texts:
On a recent trip to the London Science Museum I saw Babbage’s Analytical Engine.

Apparently this had an ALU (or equivalent). Is the Analytical Engine binary? I can build an ALU out of logic gates but I can’t conceptualise how to do it with gears. I’m trying to map across the concepts.

My question is: Can you explain in terms of logic gates how Babbage’s Analytical Engine worked?


texts: The total time require for a pipeline to execute

texts:
The book says that a total time required for a pipeline with k stages to execute n instructions is as follows.

$T  _{k,n} =[pqnk+(1-pq)(k+n-1)] \tau$

p is the probability of encountering a branch instruction.

q is the probability that execution of a branch instruction I causes a jump to a nonconsecutive address.

(Each jump requires the pipeline to be cleared)

However, I can not understand why this makes sense. The formula indicates that

  "If there is a branch instruction and is taken, the number of stages is nk. And in the remaining cases, it is (1-pq)(k+n-1)

I can understand the second case, but why is the number of stages nk in the first case? I think that the result of nk stages never occurs unless every instruction is a branch instruction so that the pipeline is cleared every time each instruction is executed. Instructions after a branch instruction which is taken can be executed in the pipeline, so it must be less than nk.
What do I miss?


texts: What is monograph and digraph in keyboard optimization problem?

texts:
I have been working on Bangla keyboard optimization. I've taken this paper as a reference. In this paper they have introduce two terms monograph and digraph. But it is not clear how they have calculate these two things. In this paper it is written -

  A monograph is an isolated key which is struck in the process of typing a text. A digraph is a sequence of two consecutive keys hit in the process of typing a text. This idea allows the distinction between rules that concern the absolute position of a given key and the relative position of two consecutive keys.

What I am assuming that digraph is those two consecutive character that are used often in any language word. Like in English language ph, qu etc. But I can not understand what is monograph.

Therefore I would need a clear explanation about monograph and digraph and what is the method to calculate these in respect to keyboard optimization problem.


texts: Modifying digraph to make it strongly connected

texts:
I came across this problem and have not been able to find a solution.

Given directed graph $G$, devise an algorithm to find the minimum number of edges to flip/change/transplant such that the modified graph $G'$ has a path from any vertex to any other vertex. That is, we can remove any edge between any two vertices and add them back to the graph any which way.

Anyone have any idea how to solve?

Clarification for edge modification:
You can edit edges any which way for a cost of one move. Once you remove an edge between any two vertices, you can reattach it to the same two vertices but flipped, or attach it to two different vertices entirely, or just have the edge go from the original source vertex to another vertex, or a different source vertex to the same destination vertex.


texts: How to find the run time complexity of nested while loops?

texts:
So this problem is pretty nasty.  I can easily find the number of iterations for each nested while loop.  The first runs log_9(n) times and the second runs log_4(n) times.  My problem that I do not know how to address is the initialization of i = n. I'm quite lost on this part so anything helps!

function p(n)
    i = n;
    while i < 5n^3 do
        x = 7n^2;
        while x < 6
            x = x/9;
        end
        i = 4i;
    end


texts: Minimize number of DFS searches in a graph

texts:
I got a weird homework question about graph.

A helicopter is going to land on an island to check the n houses after an earthquake. Some of the two-way roads connecting the houses are destroyed however the helicopter won't know beforehand. Once the the helicopter lands on a house u, they can drive to any neighboring house v if the road (u,v) is not destroyed. The rescue team would only know if a road (u,v) is destroyed or not after they arrive at either u or v. They also don't know the number of safe roads in advance. Design a strategy to minimize the number of helicopter landings, also the plan needs to have less than 2n trips along the safe roads.

My thinking is to do a DFS search on a random unvisted node. After the DFS is done, if there are still unvisited nodes, then do another DFS search from a random unvisited node again. Repeat this until all the nodes are visited. However, I don't know how to prove that this minimize the number of searches. Can anyone help me? Thanks!


texts: Why do we need/use operator precedence for Arithmetic operators?

texts:
Why do we use operator precedence rule for Arithmatic operators? Can't we simply just do the operation in a linear manner from left to right or vice-versa and deal with the operator that comes first.
For e.g. 2+3*4 = (2+3)*4 , if we do the operation from left to right.

My guess why we might do it is that, since * and / (divide and multiply) are complicated and gets even more complicated if the operands are larger, whereas + and - (plus and subtract) are simple operations.


texts: Why is it called 'throwing' an exception?

texts: I'm just wondering where the phrase "throwing" an exception came from. I understand "raising" an exception but I'm wondering if "throwing" has a reason or meaning behind it?


texts: 3-Sat reduction to facility location problem

texts:
I'm learning about NP problems and I this problem which is a bit challenging for me.
You are given an undirected, simple graph G = (V,E) and an integer k where nodes represent cities and edges represent roads between them. You want to choose at most k cities and build a fire station in each of them such that every city can be covered within 2 hops of a fire station. For instance, consider a cycle of length 5 (C5). In this case, k = 1 would be sufficient in that we can build a fire station in any one of the cities so that every city is within 2 hops from the fire station. Now consider a path on 5 nodes (P5): v1 , v2 , v3 , v4 , v5. In this case, if k = 1, then we can build a fire station on city v3. On the other hand, on P6 (a path with six nodes, we can't build on fire station to cover all cities (we need at least two fire stations). Formally, given G = (V;E) and k, determine whether it is possible to reach all cities within 2 hops from one of the fire stations by choosing at most k cities.
I know this can solved by reducing from 3 Sat or vertex cover problems, I tried but my problem is that they are 2 hobs apart from the station, I was thinking of adding gadgets but I have problem visualizing this. any help is appreciated.


texts: Cast to boolean, for integer linear programming

texts:
I want to express the following constraint, in an integer linear program:

$$y = \begin{cases}
0 &\text{if } x=0\\
1 &\text{if } x\ne 0.
\end{cases}$$

I already have the integer variables $x,y$ and I'm promised that $-100 \le x \le 100$.  How can I express the above constraint, in a form suitable for use with an integer linear programming solver?

This will presumably require introducing some additional variables.  What new variables and constraints do I need to add?  Can it be done cleanly with one new variable?  Two?

Equivalently, this is asking how to enforce the constraint

$$y \ne 0 \text{ if and only if } x \ne 0.$$

in the context where I already have constraints that imply $|x| \le 100$ and $0 \le y \le 1$.

(My goal is to fix an error in https://cs.stackexchange.com/a/12118/755.)


texts: Does two languages being in P imply reduction to each other?

texts:
Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how?

I noticed that if $L_1$ is the empty language, and $L_2$ is the "full language" $\{ 0,1 \}^*$, there does not seem to be a reduction from $L_2$ to $L_1$, but this is not clear to me. I know how a reduction works, so that is not a problem for me.


texts: How to Concurrently Add a Row to a Relational Database

texts:
Say I have a relational database and I want to support allowing multiple writers to add create a new row in the same table. How is this implemented?
I've read a lot about locks for dealing with concurrent access to the same row with shared locks and exclusive locks for example (AKA writing locks vs reading locks) but not about how a new row is created.
How does this work for

A table on a single node with multiple writers
A distributed table that is sharded
A distributed table that is replicated


texts: How to obtain the camera extrinsic matrix without using chessboard

texts:
I'm working on a problem to find the camera position in the world system when each picture was shot.

I currently have several pictures taken from different angles, and for each picture there is only a black square on a white paper.

I have the actual size of the black square on the paper and the intrinsic matrix of the camera. And since the square is very easy to crop from each image, I can also obtain the perspective transformation matrix for each image. But I think to eventually find the camera position, the key is to get the extrinsic matrix of the camera. What I've researched is that we need to use a chessboard, but I wonder if I can continue my work without using that.


texts: Is this probability distribution data structure already discovered?

texts:
Problem formulation

I have implemented an interesting probability distribution data structure: having $n$ elements $a_1, a_2, \dots, a_n$ in the data structure with respective positive weights $w_1, w_2, \dots, w_n > 0$, upon request each $a_i$ may be returned with probability
$$\frac{w_i}{\sum_{j = 1}^n w_j}.$$

A Java implementation of my data structure can be obtained here, yet I will specify the algorithm here textually:

There are two types of nodes, relay nodes and leaf nodes. The actual elements with their actual weights are stored in leaf nodes. What comes to relay nodes, we allow only those that have both children (the tree is binary). However, each relay node know how many leaves is there in the subtree starting from that very relay node; also each relay node knows the sum of weights of all its leaves.

Whenever adding a new element, we start traversing the tree from its root, and until we reach a leaf node, we choose that relay node, whose node count is smallest; this way it maintains a logarithmic height.

What comes to the removal of an element, the data structure maintains a hashtable mapping each element to its leaf node. So, first we get the leaf node, remove it, after which, we replace the parent relay node with the sibling leaf.

Whenever sampling an element, we start from root, and choose an appropriate relay node until we reach the appropriate leaf node, whose element we return.

All three basic operations seem to run in worst-case $\mathcal{O}(\log n)$, and my benchmarking supports the observation.

A simple visualization:

Question

Is this data structure already discovered? If yes, could you tell me the name of the paper that discusses it?


texts: can a DFA with only final states be minimized?

texts:
I need to construct a DFA for a certain language with as little states as possible.
so far my "best" solution contains 15 states. however, people claim it is doable in 7 states only. I tried for several days to come up with a smaller DFA but I failed miserably. So I thought I could try to minimize it. The only possible problem is, my DFA contains only final states(one of those is both initial and final). Is it possible to minimize it?


texts:
I'm interested in studying the problem of the optimal meeting point, which can be described as follow: $n$ individuals who want to gather in a restaurant (for example). They want a fair meeting point and to minimize the time/distance for everyone.

I'm looking for information on that problem, but I've only been able to find advanced paper on this problem.

My questions:

Is it part of a more general problem?
Is graphs the best way to implement it? (the nodes are the possible meeting points, the edges are the possible roads for example..) How do current programs work, for example using maps like Google Map?
Is it P or NP?

My difficulties to understand the problem and to find more informations about it

I know it's a bit vague, but I've got some difficulties because I don't know much about this kind of problems. I was just wondering one day "how to find the best restaurant in terms of distance to meet with some friends". I don't know what is mathematically the parameter that I should minimize to be "fair" (the sum of the distances of the $n$ individuals to the meeting point? The average?...).

Response to comment: (assuming that using graph is the best way to do it)

In input, we have a graph and we have the $n$ individuals (a list of $n$ vertices if we implement it with graphs, even if it means to add them to the graph), and in output, we get the optimal meeting point (i.e. the vertex which is at the minimal distance from all the $n$ individuals).


texts:
In the ARM architecture, what happens on executing a jump instruction whose jump target address is an MMIO address (or in paging mode, a virtual address that is mapped to an MMIO address)?
Would this such an instruction abort?
If it succeeds and sets the EIP accordingly, what happens next: Will the CPU actually fetch the next instruction by reading MMIO address (which may be connected to a peripheral device)?

If it succeeds, reasoning about such a CPU seems problematic because reads and writes to IO addresses are potentially visible to the outside world, unlike DRAM. For example, the effect of out-of-order instruction prefetching will be visible to the outside world via IO.


texts: Why do presenttations of proof systems in logic and automated reasoning not include the algorithm that finds proofs?

texts:
Is is that a common way to present a proof system in the field of Logic and Automated Reasoning is to present a system of inference rules, without having to formally describe a particular algorithm or procedure to find proofs in this system?

I notice that phenomenon in both textbook as well as conference or journal papers of this field.

This can be seen in classic topics like: the Natural Deduction calculus, Hilbert calculus where only inference rules is presented.

In modern researches, I am studying about Separation Logic, thus, I would like to take some papers from this field to illustrate this observation:

Automated Cyclic Entailment Proofs in Separation Logic

Symbolic Execution with Separation Logic


texts: Aussume P != NP, are these assertions valid?

texts:
Assume $P \ne NP$, and $A$ is a problem in $P$ and $B$ is a problem which is $NP-complete$.
Are the following assertions valid?

$A \le_{P} B$
$B \le_{P} A$

My approach:

$B \le_{P} A$ isn't valid, because if $B$ is reducible in poly-time to $A$, so $B$ has to be also in $P$. But thats not possible because $P \ne NP$.
$A \le_{P} B$. Is it possible to reduce a problem in $P$ to a problem in $NP$ ? If it is, then the assertion is valid.

Question: Is my approch correct or am I missing some important point?


texts: Dijkstra algorithm modification with exactly one relaxation on a directed graph where the weights of outgoing edges of a node are the same

texts:
Consider the standard version of Dijkstra's algorithm on directed graphs. Assume it is known that the input digraph $G = (V, E)$ has the following property: for all $v \in V$ the weight of all outgoing edges $vu$ is the same.

How can one modify Dijkstra's algorithm so that exactly one relaxation is done for every vertex $v \in V$? (i. e. decreasing of current minimal path length $d_{v}$ is done exactly once for every $v$).


texts:
Consider now the grammar G

S -> (S + S)
S -> (S * S)
S -> a

Is it ambiguous?

Answer: No because there are disambiguating parentheses and so no left or right
recursion.

Can someone explain how the parentheses are disambiguating. I could understand if they were "[" and "(".

Appreciate the help


texts: Is it necessary for NP problems to be decision problems?

texts: Professor Tim Roughgarden from Stanford University while teaching a MOOC said that solutions to problems in the class NP must be polynomial in length. But the wikipedia article says that NP problems are decision problems. So what type of problems are basically in the class NP ? And is it unnecessary to say that solutions to such problems have a polynomial length output(as decision problems necessarily output either 0 or 1) ?


texts: Find non-smooth function that meets conditions

texts:
I learned the following theorem in class:
"If $T(n)$ is asymptotically non-decreasing and $f(n)$ is smooth, then $T(n) =
O(f(n)|n=b^k, k=integer)$ implies $T(n) = O(f(n))$."

I'm trying to show using a counterexample that this theorem doesn't hold if $f(n)$ is non-decreasing but not smooth. Smoothness means that $f(bn) = O(f(n))$.

From my understanding, the above conditions mean that $f(n)$ must be an exponential. Other than that, how would I go about finding a function that meets the conditions outlined above?

Since this is a homework problem, please don't give an actual function, but instead give a series of steps to take to find the function. Thanks.


texts: Do all states in a DFA must be connected?

texts:
Could I construct (for some wired reason) a DFA that has a state that is not connected to anything, and it would still be legal?

I'm studying for a test, and I found a question that asks if an infinite DFA could represent a regular language, and I want to use a regular DFA and add all the infinite states not connected to the original. Can I do that?


texts: Prove any binary tree with $n$ nodes has at least $1+\log_2 n$ levels

texts:
Prove that any binary tree with $n$ nodes has at least $1+\log_2 n$ levels.
I tried setting $n=8$ and plugging in $8\geq\log_2 8 = 8\geq 3$. But I'm not sure how I can prove this by induction.


texts: Maximizing the Sum of a Subset with Excluding pairs

texts:
I have a set of nodes S where all the nodes of an arbitrary integer value.  I Also have a set of pairs of nodes from S, indicating that those node cannot be in the same subset.  Given a subset of S, how can I determine the largest possible Sum of that subset taking into account the exclusion pairs.

Example:

S = (x1:50, x2:20, x3:30, x4:15, x5:70)

Exclusion = {(x1,x2), (x4,x5), (x2,x4)}

Starting set = (x1,x2,x4,x5)

Best Possible Sum = (x1,x5)


texts: What is the semantics of a Turing machine?

texts: Can we formalize the operational/denotational semantics of a Turing Machine? Is there any formalization in literature?


texts: Finding the lengths at which cycles exist in a graph in parallel

texts:
I'm trying to find an algorithm that can find the lengths of simple cycles in an undirected graph in parallel that benefits strongly enough from it's parallelization to be practically more efficient than what I'm currently using to find simple cycles in an undirected graph.
Basically if a graph has n nodes, I need to know if there is a simple cycle of each possible length between 2 and n in the graph. I'm currently using https://www.boost.org/doc/libs/1_55_0/boost/graph/hawick_circuits.hpp because it performs massively better than any other implementation I've found of simple cycle algorithms. However, it seems that NP-hard graph problems that rely on backtracking tend to be very tricky to parallelize.
I have access to computers that would allow me to benefit greatly from distributing the problem across CPU cores, but I'm failing to find papers or past discussions of people parallelizing this particular problem space.


texts: Efficient algorithm to compute the minimum of multiple piecewise linear functions

texts:
Let $f_i(x)$ be a continuous, convex, piecewise-linear function for $i=1,\ldots,n$. Define
$$g(x) = \min_{1\leq i\leq n} f_i(x).$$
Clearly, $g(x)$ is also a piecewise linear function. What would be a good approach to compute all the pieces? In other words, it's clear that $g(x)$ can be represented as
$$g(x) = c_k + d_k x,\quad \text{for } x\in[e_k,e_{k+1}),$$
for some choice of $(c_k,d_k,e_k)$'s.  How do I compute these $(c_k,d_k,e_k)$'s in an efficient way, given the $f_i$'s?


texts: negative weight cycle detection using dijkstra's algorithm

texts:
Can we store a struct in place of vertex.
struct {
int v, update_count;
}

run dijkstra's algorithm and whenever a node is updated we will increase update_count value. If update_count value is greater than V(no of nodes) we will know that there is negative weight cycle. Is this a viable solution.


texts: What's the difference between strong consistency and sequential consistency?

texts:
How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

  ... the result of any execution is the same as if the operations of all
  the processors were executed in some sequential order, and the
  operations of each individual processor appear in this sequence in the
  order specified by its program. A multiprocessor satisfying this
  condition will be called sequentially consistent.

Spanner docs:

  Strong Consistency    All accesses are seen by all parallel processes (or
  nodes, processors, etc.) in the same order (sequentially)5 In some
  definitions, a replication protocol exhibits "strong consistency" if
  the replicated objects are linearizable.

The 5 in that doc is a link to the wikipedia page, which apparently hasn't ever cited any sources. I can't seem to find any original source for it. The "some definitions" mentioned seem to be nowhere to find online.

What's the difference between strong and sequential consistency?


texts: Checking membership in DFA with fixed length using AC1 circuit?

texts: I'm supposed to find circuits , which can solve the question of membership in a regular language A with fixed length. The depth is limited by O(log(n)) and the size by O(n).  Divide and Conquer should be the way to go, but I always exceed the max size. Would really appreciate any help


texts: Why cannot I find any information about spanning tree for DAG ?  I must be wrong somewhere.


texts: What is the definition of a "c-competitive" algorithm? For example what does it mean, if we say that there is a 2-competitive algorithm for packet routing?


texts:
$SubsetGCD$ is described by the following:

instance: A set of positive integers $S$ and an integer $k$
question: does there exist a subset $S'$ of $S$ of size $k$ such that $GCD(S') = GCD(S)$

Prove that $SubsetGCD$ is np complete.

The hint for the problem is to reduce $VertexCover$ to $SubsetGCD$

I know what I'm supposed to do. Given an instance of $VertexCover$ convert it into the form of $SubsetGCD$ such that there exists a vertex cover of size $k$ if and only if there exists a subset $S'$ of size $k$ such that $GCD(S') = GCD(S)$

Since the vertex cover and subset are of size $k$ I feel like the vertices should correspond to the members of $S$ so that the vertex cover itself is the subset $S'$

Therefore, the important part is how to define the edges connecting the verticies. I've tried edges if the GCD of the endpoints is GCD(S), if the GCD of the endpoints is not GCD(S), edges connected to a vertex must be have GCD(S) and can't have a GCD greater than GCD(S) for all immediate neighbours etc.

I've also tried reducing Clique to the Subset GCD problem with no luck. Any help would really be appreciated!


texts: Is the reduction for HAMPATH to HAMCYCLE and UHAMPATH to UHAMCYCLE the same?

texts:
HAMPATH/UHAMPATH is A directed / undirected graph G and 2 nodes s and t and is there a hamilton path from s to t?

Likewise with HAMCYCLE/UHAMCYCLE but has a hamilton cycle on $G'$

The reduction for directed is

$HAMPATH \leq_p HAMCYCLE$

function(G, s, t)
    G' = G
    add node t' to G'
    add edges (t, t') and (t', s)
    return (G')

$(\Rightarrow)$If $(G, s, t) \in HAMPATH$, then $\{(s, v_1), \dots, (v_n, t)\}$ is a hamilton path in $G$ from $s$ to $t$ and our reduction for $G'$ has a path $\{(s, v_1), \dots, (v_n, t), (t, t'), (t', s)\}$ which is a hamilton cycle $(G') \in HAMCYCLE$

$(\Leftarrow)$ If $(G') \in HAMCYCLE$, then $\{(s, v_1), \dots, (v_n, t), (t, t'), (t', s)\}$ is a hamilton cycle in $G$. Remove the edges $(t, t')$ and $(t', s)$ and we are left with a hamilton path $\{(s, v_1), \dots, (v_n, t)\}$, $(G, s, t) \in HAMPATH$

Wouldn't this reduction also work for the undirected version i.e. $UHAMPATH \leq_p UHAMCYCLE$? I've seen on the internet another reduction where they add another node and add an edge between every vertex in G for $G'$ but wouldn't this simpler version work as well?


texts: When does knowing the number of solutions help (improve the running time)?

texts:
Combinatorics equips one with methods to find the number of solutions to discrete problems. While this is obviously an important tool for accurate gauges on the average running of an algorithm, I'm interested in whether, and if, how, one can use the knowledge of the number of solutions to improve an algorithm.

More specifically, I'm looking for examples, where having knowledge of the exact count of solutions allows one to
improve the running time of the algorithm (significantly, i.e. it should show in $\mathcal O$-notation)

An idea of how such an algorithm might look like, might be this:
For a problem of the kind "Find all possible solutions", we iteratively calculate the next solution using (one/all) previous solutions, but with the catch that every such step has an enormous increase in cost.

For such an algorithm, knowing the number of solutions would allow us to skip the last (and most expensive) step.

What would be an actual algorithm that, when knowing of the number solutions, can be significantly improved?


texts: Different application of Arden's theorem leads to different answers

texts:
So, I have to solve for the following set of equations

$q_1$ = $q_1$a + $q_2$b + $\epsilon$
$q_2$ = $q_1$a + $q_2$b + $q_3$a
$q_3$ = $q_2$a

There are two ways to do this.
I did this

$q_1$ = $q_2$b + $\epsilon$ + $q_1$a
$q_1$ = ($q_2$b + $\epsilon$)a* Applying Arden's theorem

Now substituting in $q_2$ the values of $q_1$ and $q_3$

$q_2$ = $q_2$ba*a + a*a + $q_2$b + $q_2$aa
$q_2$ = a*a + $q_2$(ba*a+b+aa)
$q_2$ = a*a(ba*a+b+aa)* Applying Arden's theorem
$q_2$ = a*a(ba*+aa)*

Now substituting in $q_3$, the answer should be

$q_3$ = a*a(ba*+aa)*a

However, the correct answer is

(a + a(b+aa)*b)*a(b+aa)*a

which can be obtained by first substituting $q_3$ in $q_2$, and then substituting $q_2$ in $q_1$, and finally solving $q_2$, $q_3$ from the obtained regular expression for $q_1$.
Can someone tell where I have gone wrong in the above method, or am I applying ardens theorem in the wrong way ?


texts: Handling epsilon productions in recursive descent parsing

texts:
I am working on a recursive descent parser for lambda calculus. In my grammar, after removing left-recursion, I am left with the following two productions:

# APPLICATION  -> ATOM APPLICATION'
# APPLICATION' -> ATOM APPLICATION' | ε

Both APPLICATION and APPLICATION' correspond to the same type of node in the AST. How should I handle parsing the second production? I know that choosing between two alternatives for a production is performed by looking up the next token in buffer, but the epsilon production confuses me.

EDIT:

Here is current implementation (Ruby) that fails to left-associate applications.

require_relative 'token.rb'
require_relative 'ast.rb'

class Parser
    def self.call(tokens)
        new(tokens).send(:parse_expr)
    end

    def self.to_proc
        method(:call).to_proc
    end

    private
        def initialize(tokens)
            @tokens = tokens
            @l = -1
        end

        def parse_expr
            if lookahead.type == :tklambda
                return ExprNode.new([parse_abstraction], @l)
            else
                return ExprNode.new([parse_application], @l)
            end
        end

        def parse_abstraction
            match_token(:tklambda)
            id = parse_identifier
            match_token(:tkdot)
            expr = parse_expr
            return AbstrNode.new([id, expr], @l)
        end

        def parse_identifier
            id_token = match_token(:tkid)
            val = id_token.value
            return IdNode.new(nil, @l, val)
        end

        def parse_application
            left_child = parse_atom
            first_atom = [:tklparen, :tkid] # FIRST(ATOM)
            # application -> atom application'
            while !lookahead.nil? and first_atom.include?(lookahead.type)
                return AppNode.new([left_child, parse_application], @l)
            end
            # application' -> atom application' | ε
            return left_child
        end

        def parse_atom
            if lookahead.type == :tklparen
                match_token(:tklparen)
                expr = parse_expr
                match_token(:tkrparen)
                return AtomNode.new([expr], @l)
            else
                return AtomNode.new([parse_identifier], @l)
            end
        end

        def match_token(type = nil)
            if !type.nil? and lookahead.type != type
                raise "Unexpected token at #{@l + 1}. Expected: #{type}, "\
                      "got: #{lookahead.type}."
            end
            @l += 1
            return @tokens[@l]
        end

        def lookahead
            return @tokens[@l + 1]
        end
end


texts: Is there a proof for the halting problem that does not involve an infinite nest of functions?

texts:
I have been doing a fair amount of research about the halting problem.

Most solutions I come across have the following pattern:

We assume we have a program H that solves the halting problem. We then define a new program P that takes a program x, and uses H(x) to figure out if x halts. If x does halt, then we make P go into an infinite loop. If x does not halt, we make P halt. Then, we run P(P). Then we get a contradiction because if P stops according to H(P), then P will actually not stop, and vice versa.

I currently assume that H takes a program which already has parameters plugged in to it. Proof: If this were not the case, we could write a simple program S that went "if input is true, halt. If input is false, run forever." Then, if H can just take the program S, not knowing what the input to S is, it seems trivial that there is no function H that can tell whether or not S will halt, since S halting depends on the input to S, and H doesn't know what the input to S is. Thus, I assume that H must be given a program whose inputs are specified.

Assuming this, it seems as though we are missing something when we run P(P). Since P(x) runs H(x), x needs to be a program with its inputs specified. Thus, we can't give P with no inputs as an input to P. Instead, we must give that second internal P some input.

Let's call the input x and assume that x's inputs are specified.

So we run P(P(x)):

P(x) will run H(x) to determine if x halts or not, and P(x) will do the opposite. Then, P(P(x)) will run H(P(x)) to determine if P(x) halts or not, and P(P(x)) will do the opposite. There's no contradiction anymore, since P(P(x)) is not the same thing as P(x).

So it seems like the only input to P that will make the proof work really is P. But if that's the case, then the inner P also needs to take P as an input, so we really need to be running P(P(P)) in order for the solution to work. But then that inner P also needs P as an input, so we really need infinite nest of functions, P(P(P(...))), in order for the proof to work.

Is there any solution to the halting problem that does not run into this issue?


texts: Essential bit content - prove that we can't use less bits than that

texts:
Let $H_0$ be $\log_2(|A|)$, where $A$ is a set.
Let $C$ be a compressor $C\colon A \to \{1,0\}^l \cup \bot$.
This is a silly question, because intuitively it seems obvious.
How can I prove that $l$ can't be less than $H_0$?
I can prove that $l = H_0$ is sufficient, but how can I prove that it can't be less.


texts: Are there any estimated, imperfect or fuzzy sorting algorithms?

texts:
I'm implementing some estimation metrics that take samples of optimisation functions and estimate their properties. One of the metrics requires the data to be sorted; however, since the metric is only an estimation, I was wondering if I could get a comparatively accurate result if the data wasn't sorted precisely, but well enough.

I would expect data could be nearly sorted in less time than actually sorting it. However, I can't find any algorithms that will do this, which I find rather odd, so I thought I'd ask around here.

My idea of "imperfectly sorted" is quite loose. It could, for example, mean:

Many elements are perfectly sorted, but some are not
Adjacent elements are not necessarily in the correct order, but when comparing groups of elements, the elements increase on average; if plotted, there would be a visible general upwards trend

For the first definition above, I suppose you could take a sub-sample of the data and just quick-sort that, but I don't imagine it'll get you much of a performance improvement without seriously reducing the quality of the estimation.

It might also be possible to take something like quicksort and limit the depth of the recursion.

Do imperfect sorting algorithms exist? Can they significantly out-perform regular sorting algorithms?