texts: Searching for pattern with Dynamic Time Warping

texts:
I'm creating app that allows user to authorize by drawing dynamic gesture in front of camera (actually Leap Motion sensor, but that's not the point). Every person can save their own gesture as their password, so for every user I have a time series representing the gestures where single frame is an array of values that will allow me to recognize current frame shape. Now, the authorization process will look like this:

Person begins authorization process - camera starts recording frames, let's say, for five seconds.
After recording stops, the system has to somehow check if recording contains specific user gesture.
I've decided to choose Dynamic Time Warping for this task.

I have few questions:

How to correctly search for this gesture? I have to allow person to draw the gesture faster or slower than the original, so should I cut the recording to multiple parts in multiple ways? Let's say first iteration cut by 10 frames, second by 12, third by 15 etc?
What is the right way to decide if the gesture is similar or not, what is the proper way to count the similarity (I don't want to compare it to other gestures because if person draws something completely different than any other gesture it will get classified somehow)? Also when I compare two exact same gestures, but one is faster (10 frames) and second slower (30 frames), the calculated distance is significantly lower than comparing the same gesture but with equal time. What is proper way to calculate "absolute" distance?
Currently I'm using Euclidean distance to calculate distance between each point between time series. Is it the right way?

I'm new to this topic so sorry if these questions sound stupid. I've searched for an example similar to mine, like find specific word in recorded sentence but couldn't find it.
Thank you for any help.


texts: If x operations cost O(x) amortized then how much xy operations cost?

texts:
True or False?

Say some data structure can perform $x$ operations in amortized $O(x)$ time.
Then for a big enough $y$ it can perform $xy$ operations in worst case $O(xy)$ time.

My attempt:

$x$ operations in $O(x)$ amortized means $O(1)$ expected time for $1$ operation.
Then for $xy$ operations it'd be $O(xy)$ amortized (and I think $O(x^2y)$ worst case). Therefore, the statement is incorrect.

But the answers sheet says i'm wrong. Why?


texts: Counting number of permutations respecting partial order

texts:
Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ represent $A_i < A_j$ and $A_i \geq A_j$ respectively.

Is there an efficient algorithm that counts the number of partitions of $A$ that respect the partial order? E.g. for the all-zero matrix (totally undefined partial order) it's simply $n!$ and for a matrix  containing a total order it's simply $1$.

We can assume that the partial order does not contain contradictions, e.g. we won't have $A_i < A_i$ or some chain of comparisons that violates transitivity.


texts: Proving preservation under substitution System F Omega

texts:
I am going over the proofs for the simply typed lambda calculus in the book "Types and Programming languages" by Benjamin Pierce. I am trying to find inspiration for the similar proofs for System F Omega. When I was going over the preservation under substitution proof for the simply typed lambda calculus  I was a bit puzzled.

The hypothesis of the proof is:

  If  $\Gamma ,x:S \vdash t:T $ and $\Gamma \vdash s:S$ then $\Gamma \vdash [x \mapsto s]t : T$

So far I understand the proof quite well, but for the case $T-Abs$ I'm a bit lost. The rule is shown below.

$$
  \dfrac{\Gamma ,x:T_1  \vdash t_2 : T_2}
        {\Gamma \vdash \lambda x:T_1 . t_2 : T_1 \rightarrow T_2}
$$

To prove the hypothesis for this case we use the previously proven lemmas weakening and permutation.

We assume that in this proof  $x \neq y$ and $y \notin FV(s)$.

First we list the givens:

$t = \lambda y:T_2 . t_1$
$ T = T_1 \rightarrow T_2$
The first subderivation: $\Gamma ,x:S,y:T_2 \vdash t_1 : T_2$
The second subderivation: $\Gamma \vdash s:S$ by hypothesis.

Step 1 The first step we take is using permutation on the first sub-derivation, yielding: $\Gamma ,y:T_2,x:S \vdash t_1 : T_2$. The reason why this happens is a bit unclear to me. I am assuming that the actual order of the extensions of $\Gamma$ matter for the third step.

Step 2 The second step, which is the one that is unclear to me, is applying weakening to the second sub-derivation: changing $\Gamma \vdash s:S$ into $\Gamma ,y:T_2\vdash s:S$. The reason that I find this odd is that this new form of the sub-derivation is not used anywhere in the proof.

Step 3: By the induction of our hypothesis we know that $\Gamma ,x:S,y:T_2 \vdash t_1 : T_2$ implies $\Gamma ,y:T_2 \vdash [x \mapsto s]t_1 : T_2$. And since we know that, we can apply the $T-Abs$ rule. Since that is what it basically says.  We wrap the given sub-derivation in a lambda and we have to remove the $y:T_2$ from the context because it is now introduced by the abstraction we constructed:

$$\Gamma \vdash \lambda y:T_2 . [x \mapsto s]t_1 : T_1 \rightarrow T_2$$

And finally we can move the substitution outside because we assumed that $x \neq y$ and $y \notin FV(s)$.

$$\Gamma \vdash [x \mapsto s]\lambda y:T_2 . t_1 : T_1 \rightarrow T_2$$

And this is exactly what we had to prove.

The problem I have with the second sub-derivation is that we nowhere in the prove actually used it. We never relied on that fact. Any input would be highly appreciated.


texts:
I have stumbled about the way a text file is saved by the OS.
I have typed:

printf "ab" | hexdump

and the output was:

  6261

which are the letters in reversed order. My first intent was endianess, but this cannot be true, since at this level, such abstractions must be transparent to the programmer and user. Also endian would be:

$$ab  \mapsto 6162  \mapsto 2616$$

So I wondered, why would someone save a file like that?

Greetings,
Niclas


texts: Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time

texts:
I'm trying to determine whether it is possible to decide if a system of $n$ linear equations with integer coefficients and $n$ variables has a solution in $\{0, 1\}^n$ in polynomial time.

Additionally, all of the coefficients of $A$ are in $\{-1, 0, 1\}$, but I couldn't find a way to use that.

The trivial case is if the (matrix $A$ of the) system is invertible, there is only one solution, it is easy to check whether all of them belong to $\{0,1\}$.

However, if you have infinitely many solutions, and $k$ free variable, I can't find a way to do better than check all the $2^k$ possibilities.

Do you know any algorithm to do so in polynomial time ?

I also tried to do a reduction from SAT (or some variant with n clauses and n variables in each clause, to show that it is NP complete), but because of the fact that we have $Ax = b$ and not $Ax \geq b$, I couldn't do that either.

Do you have a reduction to show that this problem is NP complete ?


texts:
In a Turing machine, what is the difference between the instruction table and the algorithm?

The instruction table seems to be an algorithm for completing the task no?


texts: Why does removing all copies of a letter preserve regularity?

texts:
Let $P(a,L)$ remove every $a$ in $L$, for example
$$ P(a,\{ab,aab,aaab,bba\}) = \{b,bb\}. $$

How to show that if $L$ is a regular language then $P(a, L)$ is also a regular language?

My attempt:

If $L$ is regular then $P(a, L)$ is regular. Namely, let $D = (Q,Σ,δ,q_0,F)$ be a DFA for $L$.

Assume every state in $L$ is reachable from $q_0$. Then we can turn $D$ into an NFA $N$ for $P(a, L)$ by adding a new state $q_{−1}$ which becomes the NFA’s start state. For each state $q ∈ L$, we add an epsilon transition from $q_{−1}$ to $q$.

Therefore, define $N$ to be
$( L ∪ \{q_{−1}\}, Σ , δ′, q_{−1},F)$

Is this the correct way to prove it?


texts: If P = NP, does SAT, or any other NP-Complete poly-reduce to any language different from $\emptyset$ or $\Sigma^*$?

texts:
I looked at Sipser ("Introduction to the Theory of Computation"), Problem 7.17:

  Prove that if P = NP, then every language in P, except $\emptyset$ and
  $\Sigma^*$, is NP-Complete.

The solution is as follows:

  Let $A$ be any language in NP and let $B$ be another language not
  equal to $\emptyset$ or $\Sigma^*$. Then there exist strings $x \in B$
  and $y \notin B$. To reduce an instance $w$ of $A$ to that of $B$, we
  just check in polynomial time if $w \in A$. If yes, we output $x$ and
  $y$ when $w \notin A$.

But I don't see why this reduction could not be applied to any language (except $\emptyset$ and $\Sigma^*$). It would not mean that the language is in P, but the reduction would be correct. The only point where I have doubts is the part where we say that $x$ and $y$ exist, do we somehow have to take into account some computing time for $x$ and $y$ ? Else the reduction would work even for unrecognizable languages for example.


texts: Is extensionality for coinductive datatypes consistent with Coq's logic?

texts:
Given a coinductive datatype, one can usually (always?) define a bisimulation as the largest equivalence relation over it. I would like to add an axiom stating that if two members of the type are related by the bisimulation, they are equal in the sense of Leibniz equality (=). Would this make the logic inconsistent?

An example for streams:

CoInductive Stream A :=
| Cons : A -> Stream A -> Stream A.

CoInductive Stream_bisim A : Stream A -> Stream A -> Prop :=
| Stream_bisim_Cons :
    forall x xs ys,
    Stream_bisim A xs ys ->
    Stream_bisim A (Cons A x xs) (Cons A x ys).

Axiom Stream_bisim_eq :
  forall A xs ys,
  Stream_bisim A xs ys ->
  xs = ys.

My intuition is that this should be safe by analogy with functional extensionality, since it should not be possible to distinguish bisimilar streams by observation. But of course I'd prefer an actual proof (or at least expert testimony) to such informalities.


texts: Is there a reduction concept in artitificial intelligence?

texts:
Is there a concept for comparing algorithms in artificial intelligence theory similar to reduction in complexity theory (Wikipedia)?

I'm asking this because I was wondering how AI algorithms are to be classified in terms of general applicability. As far as I'm aware, AI techniques are largely classified by which problem they are solving rather than how abstract/ general they are. To me, it would make sense to classify algorithms $P$ and $Q$ for different problems in terms of generality by determining whether $P$ can also—potentially by means of  a prior transformation of the input—solve $Q$.
Articles and book references are very welcome!


texts: Is mutual inductive type definition essential in coq core language?

texts:
I'm studying Coq's core language and I found that mutual inductive type definition is in it.
https://coq.inria.fr/refman/language/core/inductive.html#theory-of-inductive-definitions
Before I read the material, I had supposed that Coq translates mutual definitions in Gallina into nonmutual ones in its core language, since it allows the core language to be smaller. But it wasn't and then I started to wonder why.
For instance, even and odd can be defined mutually as follows.
Inductive even : nat -> Prop :=
| even_O : even 0
| even_S : forall n, odd n -> even (S n)
with odd : nat -> Prop :=
| odd_S : forall n, even n -> odd (S n).

However, one can write another definition without with keyword.
Inductive even_or_odd: (is_even: bool) -> nat -> Prop :=
    | even_O : even true 0
    | even_S : forall n, even false n -> even true (S n)
    | odd_S : forall n, even true n -> even false (S n).

Definition even := even_or_odd true.
Definition odd := even_or_odd false.

I agree that the former looks better than the latter. However, What I wonder is if it is always possible to rewrite any mutually defined inductive type in a nonmutual way. If then, Coq does not necessarily include the mutual definition syntax in its core language.
Does the mutual definition allow more expressions to be defined?
Is there any mutually defined type that can't be translated to a nonmutual one?
Or there isn't, but my concern about minimal core language is not a big deal?
Also, I am so sure that mutual fixpoints always can be translated to nonmutual ones. It looks much more clear to me compared to the case of inductive definition. Am I right?


texts:
I'm reading this article on a GCD algorithm described by Dijkstra:
https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD316.4.html

I'm looking at program 1.  In particular I'm trying to understand the proof that the loop terminates.  Here is program 1 (my notation is slightly different than the one in the article):

function GCD(a,b)

while a != b
    if a > b
        a = a - b
    else
        b = b - a

return a

I get that max(a,b) at loop n is strictly greater than max(a,b) at loop n+1.  Since a and b are integers greater than 0 it follows that max(a,b) is always greater than 0.  This implies a lower bound.  Therefore the while loop must terminate.

Is my understanding correct?


texts:
I think Option C is false. Following is my thought process:
Starvation in general mean Process is waiting indefinitely for the resource or to get scheduled etc. [A/c to Galvin Book]. So, here in this question, Any process needing any resource at any point can call the OWNRESOURCE function and process will surely get the resource it asked for. So, we can surely say that the process doesn't have to wait indefinitely at any point. Hence we don't have Starvation.
But, I have read that Livelock is a special kind of Starvation (Resource Starvation), Clearly the Scheme mentioned in the question suffers from Livelock. But it can't possibly suffer from Starvation.
Questions:

Is my thought process correct about Why the scheme can't make process suffer from starvation?
Is it possible in the given scheme, to have Livelock but no Starvation?

Note: I have asked similar question(deleted now) but didn't express my thoughts well and didn't have any discussion. Now, I'm very specific about my doubts and I have articulated my thoughts as well.


texts:
Say you are given the following CFG $G$:
$$
S \to S_1 \mid S_2 \\
S_1 \to AbAS_1c \mid \epsilon \\
S_2 \to BaBS_2c \mid \epsilon \\
A \to Aa \mid \epsilon \\
B \to Bb \mid \epsilon
$$

What is $L(G)$?

So far I've derived the following regular expressions:

$ S \rightarrow (a^*ba^*)^*c \mid (b^*ab^*)^*c$

So far I've come up with this $L(G)$:

$L(G) = \{ (a^nba^n)^qc \mid (b^nab^n)^*q : n,q \geq 0    \}$

When you approach the second $S_1$ do you include the $c$ ( As in, finish $S_1c$ and the go recursive)?


texts:
Tarjan's algorithm for 2-SAT is based on the truth:

  a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation.

But I don't find any reason for the right to left direction. how can the inexistence of such variable guarantee satisfaction of CNF?

I tried to follow the steps of the algorithm, and I was stuck here:

  For each component in the reverse topological order, if its variables do not already have truth assignments, set all the literals in the component to be true. This also causes all of the literals in the complementary component to be set to false.

Isn't it possible the variable is already assigned WRONGLY? When we keep assigning TRUE from the back, and we assign the FALSE in the middle, but the TRUE is to be assigned to the next variable. In this case, the feasibility breaks.

Of course this kind of case never happens because the algorithm is right and many people use this algorithm well. But so many post says it as the trivial things.

I think the reason why those assignment is possible is relevant to the skew-symmetric condition of the graph, since (x -> ~x -> y -> ~y) never has true assignments.


texts: Decision problems vs "real" problems that aren't yes-or-no

texts:
I read in many places that some problems are difficult to approximate (it is  NP-hard to approximate  them). But approximation is not a decision problem: the answer is a real number and not Yes or No. Also for each desired approximation factor, there are many answers that are correct and many that are wrong, and this changes with the desired approximation factor!

So how can one say that this problem is NP-hard?

(inspired by the second bullet in How hard is counting the number of simple paths between two nodes in a directed graph?)


texts: How are words assigned in machine language?

texts:
So, if you have an 8-bit computer and it can perform a fetch cycle, meaning it can access its memory, how do you create words the computer understands.

If LDA "load the accumulator" is in the instruction set and its just something we named for humans and the computer understands binary...

How was this idea communicated in binary.

I see it's another language, in logic, two-state system,

literal b/c logic gates are

But how do you say load and add and such

These are the human terms but what would the computer hear?


texts: Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?

texts: I learned from this post that ${\sf DTIME}^{\text{EXP}}(n^k) \neq \text{EXP}$ for a fixed $k$ for otherwise the Time Hierarchy Theorem would fail in that relativized world.  However, is it possible to prove that no oracles exist in which the Time Hierarchy Theorem fails?  Or is it just that we have not been able to discover any, that we assume that the Time Hierarchy Theorem never fails. Thanks.


texts: Are expert systems outdated, what are better alternatives to them, if any?

texts:
I need to link facts to actions through rules. If a person bought soup 10 times and he is coming at midday every day, then the system should link the fact that the person bought soup so many times, using the rule "person, consecutively buying soup 5 or more times within a month is going to buy soup with 90% confidence", to the conclusion that with 90% confidence today at midday, the same person will show up, ordering soup.

Above is an example of an expert system, however based on the research I've just done, it seems like expert systems have lost their popularity, which they had in 90s-00s. The only "popular" applications are business decision making and some medical systems. I am wondering if I should use expert systems or should I look into more "advanced" alternatives? What are the obvious disadvantages to using an expert system, besides the setup cost of conducting the research?


texts: Which algorithm can calculate an optimal allocation of students to projects?

texts:
I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects are predetermined and of fixed number and each student needs to be allocated to exactly one project. Each project needs at least one student, but can hold up to a maximum of $y$ students.

For my purposes, there will be on average between 8 to 15 projects available and 80 to 250 students to assign to these projects, resulting in average group sizes of 8 to 15 students per project. A reasonable value for $y$ is usually $\frac{n}{m}+2$.

The definition of optimal and stable as put by @Gassa:

(1) There is no student $S$ assigned to project $P$ such that $S$ likes $Q$ more and $Q$ has an empty slot; (2) there is no pair of students $(S,T)$ such that the current assignments are $S→P$ and $T→Q$, but $S→Q$ and $T→P$ would both be more preferred.

All sort relevant sources I could find so far (listed below) either require an equal number of students and projects (stable marriage) or allocate only one student to each project (exchange-stable matching [1] / the matching problem) and I find it non-trivial to adapt these algorithms for the described purpose.

Sources

[1] Pages 41ff of Algorithmics of Two-Sided Matching Problems by David J. Abraham
[2] A Systematic Approach to the Implementation of Final Year Project in an Electrical Engineering Undergraduate Course by C. Y. Teo and D. J. Ho
[3] Student Project Allocation Using Integer Programming by A. A. Anwar and A. S. Bahaj
[4] Similar (but not identical) question Assignment based on ranked preference on Stack Exchange


texts: What algorithm is suitable for very small scale, time dependent optimization?

texts:
I have a time-dependent (dynamic) optimization problem:
$$
f_t : [0;1]^2 \mapsto \mathbb{R}^+;  t \in [1, \dots, n]
$$
$f_t$ is to be maximized. That is for each $t$ I would like to find a relatively high value of $f_t$. Mostly, $f_t$ is a relatively simple, continuous, unimodal function. It changes with time, but not much and not predictably. I know only that the scale of the function goes down exponentially.

The problem is that at each time I can perform only a handful (5-10) of evaluations of $f_t$.

I am absolutely new to dynamic optimization and therefore I am looking for some simple approach. Any suggestions or references to literature are welcome.

I have considered particle swarm optimization, but the papers on PSO I read are usually dealing with at least 10 dimensional problems, so PSO may be an overkill. Also I do not know if it is appropriate to use just 5-10 particles.


texts: Counting the number of subsets with positive sum

texts:
I have some constant vector $\mathbf{s}$ on $n$ dimensions, where every element of $\mathbf{s}$ is a real number, and I would like to multiply it by every possible $n$-dimensional binary vector $\mathbf{v}_j\ (0\leq j < 2^n)$.

I only care about whether $\mathbf{s}\cdot \mathbf{v}_j > 0$. I would like to count all of the times this condition holds.

Question: As the naive algorithm has complexity $O(2^n)$, it blows up fast. What are my options for optimizing this for large $n$?


texts:
Suppose we have an algorithm for a decision problem with $n$ bit inputs that runs in $DTIME[f(n)]$ is there ways to convert to circuits of $O(f(n))$ size with AND, OR and NOT gates?

How about when we go from circuits to programs?


texts:
Suppose we are given a 3CNF, and we want to know whether k clauses from this 3CNF can be satisfied (k being any natural number)?

I'm trying to think of an efficient algorithm to solve this problem. This is sort of a variation of the MAX 3-SAT, but with a fixed k. If we have m clauses, checking naively would get $\binom{m}{k}$ comparisons, but this seems factorial (if we approximate with Sterling's formula, exponential) complexity.

What could be an efficient way to check this? I must be missing something. Thanks.


texts: Need help with a specific distribution algorithm

texts:
Here is the problem:

We have an ordered To-Do list with n tasks. The duration of every task is given and tasks need to be completed in order. We need to distribute the tasks to m days. Individual tasks cannot be split between days. How can we minimize the variance of the total task duration of days?


texts: Logical conjunction of two binary decision diagrams

texts:
Compute a BDD for $B_{1} \wedge B_{2}$ by using an algorithm that applies dynamic programming. Document the execution of the algorithm by indicating pairs of BDDs $(q_{1},q_{2})$ and the BDD $q_{1} \wedge q_{2}$ computed by the algorithm. Suffice it to indicate only the effectively required pairs of BDDs. Furthermore, for an arbitrary BDD $B$ you can use the equations $B \wedge F=F$, $F \wedge B=F$, $B \wedge T=B$ and $T \wedge B=B$.

I manage to do the first steps, but then I fail, because I don't know how to find the terminal node (see question mark) and also because of the fact that $x_{2}$ does not exist in $B_{2}$:

$\text{T} \wedge \text{F} = \text{F}$
$\text{T} \wedge \text{T} = \text{T}$
$\text{F} \wedge \text{F} = \text{F}$

Can somebody help me, please?


texts: Exit Condition for Knight's Tour Using Depth-First Search

texts:
Suppose I'm using the algorithm below to perform Depth-First Search in a 2d Grid.

It seems like it should be possible to adjust it to perform a Knight's Tour with little change.

For example I would replace

for each offset in ["up", "down", "left", "right"]

with

for each offset in possible Knight moves.

EDIT: I would also call dfs() with None as the goal argument, or some position which can't be reached.

What I'm confused about is how to return the path when the goal position is undefined.

I thought of checking the length of the path each pass through the while loop and returning the path if it is as long as the total number of squares on the board, but I ran into a problem with in my get_path() function, as None (the return value of dfs() when the goal is not found) has no predecessor.

Please could someone explain how my algorithm can be modified to return a full path for a Knight's Tour?

function dfs(grid, start, goal)
    stack = Stack()
    stack.push(start)
    discovered = set()
    discovered.add(start)
    predecessors = dict()
    predecessors[start] = None

    while stack not empty:
            current = stack.pop()
            if current == goal:
                    return get_path(predecessors, start, goal)
            for each offset in ["up", "down", "left", "right"]
                    new = current + offset
                    if new not in discovered and new is on board:
                            stack.push(new)
                            discovered.add(new)
                            predecessors[new] = current

    return None

function get_path(predecessors, start, goal):
    current = goal
    path = []
    while current != start:
        path.append(current)
        current_pos = predecessors[current]
    path.append(start)
    path.reverse()
    return path


texts:
I am reading about dependent types theory in the Homotopy Type Theory online book.

In section 1.3 of the Type Theory chapter, it introduces the notion of hierarchy of Universes: $\mathcal{U}_0 : \mathcal{U}_1 : \mathcal{U}_2 : \cdots$, where

  every universe $\mathcal{U}_i$ is an element of the next universe $\mathcal{U}_{i+1}$. Moreover, we assume that our universes are cumulative, that is that all the elements of the $i^{\mathrm{th}}$ universe are also elements of
  the $(i+1)^{\mathrm{th}}$ universe.

Yet, when I look at the formation rules for the various types in appendix A, at first glance, if a universe appears above the bar as a premise, the same universe appears below. For instance for the coproduct types formation rule:

$$\dfrac{\Gamma \vdash A : \mathcal{U}_i \quad \Gamma \vdash B : \mathcal{U}i}{\Gamma \vdash A + B : \mathcal{U}_i}(+\mbox{-}FORM)$$

So my question is why is a hierarchy necessary? Under what circumstances do you need to jump from a universe to one higher in the hierarchy? It is really not obvious to me how given any combination of $A_m: \mathcal{U}_i$, you can end up with a type $B$ that is not in $\mathcal{U}_i$. In more details: the formation rules in sections of the appendix A.2.4, A.2.5, A.2.6, A.2.7, A.2.8, A.2.9, A.2.10, A.3.2, either mention $\mathcal{U}_i$ in the premise and judgement, or just in the judgement.

The book also hints that there is a formal way to assign universes:

  If there is any doubt about whether an
  argument is correct, the way to check it is to try to assign levels consistently to all universes appearing in it.

What is the process for assigning levels consistently?

$\mathcal{U}:\mathcal{U}$ would lead to the Russell paradox.
Avoiding the Russell paradox is explicitly mentioned in the book (page 24). It also goes into more details page 54, 55 that is uses “Russell-style universes” rather than “Tarski-style universes”. So at a very high level, I take for granted that the theory wants to avoid the paradox. Unfortunately I don't have the background to make sense of out that directly. What I am after in this question, is really just scratching the surface by getting some examples of things in $\mathcal{U}_j$ and not in $\mathcal{U}_i$ for $j > i$ and may be anything else that give me a feel for how the hierarchies work.


texts: How many permutations for generating a specific binary search tree?

texts:
The keys 2, 4, 6, 7, and 8 have been inserted, one by one, in some unknown order, into an initially empty BST.  The result is this BST:

There are 120 different permutations of the five keys, but not all of these would lead to this particular BST being built.  How many of the permutations will generate this particular BST?


texts: What is the complexity of this matrix transposition?

texts:
I'm working on some exercises regarding graph theory and complexity.
Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically I just have to give an algorithm to transpose an $N \times N$ matrix.

My first thought was to loop through all rows and columns and simply swapping values in each of the $M[i,j]$ place. Giving a complexity of $O(n^2)$ But I immediately realized there's no need to swap more than once, so I can skip a column every time e.g. when I've iterated over row i, there's no need to start iteration of the next row at column i, but rather at column i + 1.

This is all well and good, but how do I determine the complexity of this. When I think about a concrete example, for instance a 6x6 matrix this leads to 6 + 5 + 4 + 3 + 2 + 1 swaps (disregarding the fact that position [i,i] is always in the right position if you want to transpose a $N \times N$ matrix, so we could skip that as well).
This looks alot like the well-known arithmetic series which simplifies to $n^2$, which leads me to think this is also $O(n^2)$. There are actually $n^2/2$ swaps needed, but by convention the leading constants may be ignored, so this still leads to $O(n^2)$. Skipping the i,i swaps leads to $n^2/2 - n$ swaps, which still is $O(n^2)$, but with less work still..

Some clarification would be awesome :)


texts:
I am wondering how to prove that Subgraph Isomorphism is NP Complete.  Wikipedia indicates that the CLIQUE problem can be used to demonstrate this, but I can't figure out how. I also found this link that demonstrates how Subgraph Isomorphism reduces to CLIQUE, but I can't figure out how to reverse it.  Subgraph isomorphism reduction from the Clique problem

Here is a formal example of the problem from DASGUPTA 8.10:
Given as input two undirected graphs G and H, determine whether G is a subgraph of H (that is, whether by deleting certain vertices and edges of H we obtain a graph that is, up to renaming of vertices, identical to G), and if so, return the corresponding mapping of V (G) into V (H).


texts:
Is there an easy to use software that implements term-rewriting? Or do I need to write my own parser for it?
I am looking for something that will take in a fixed set of user-specified rules and will be able to reduce arbitrary terms under those rules. Is there a standard tool for doing such rewrites?


texts: Avoiding overflow when comparing between 16-bit numbers

texts:
Let's say I have a 16-bit number system. and let $a, b$ a 16-bit numbers in this system.
I know that the numbers I can represent in this system are between $−32,768$ and $32,767$.

Let's say I want to compare between $a$ and $b$ where $a, b$ are near those limits. for example: $a=30,000$ and $b=-30,000$.
I want to compare these numbers using only logical operators (using assembly-like language). I mean that I can't use '$<$' or '$>$' and I can use '$==$' only to compare with $0$.

So I thought about this idea:
for determining if $a==b$, I can use the XOR and then check if the result equals $0$.

I want to figure out how to determine, using this method, if a is greater than b or if a is less than b?

I want hints and good thoughts, and maybe a different ideas than mine. In addition, if you think that the XOR'ing idea isn't useful or it won't work, I'd like to know why.


texts: Algorithmic information theory with stochastic algorithms?

texts:
Suppose we define a class of algorithms that is allowed to sample i.i.d. Bernoulli bitstrings of arbitrary length, and use these to generate outputs. If we are allowed to use algorithms like this, then intuitively, "white noise" images like this one are easy to generate (i.e they have a low description length algorithm allowing random noise, even though it is essentially maximum k-complexity), namely we just run a for loop width x height times and pick black/white randomly.
I've tried to look online for "stochastic algorithmic complexity" and some other keywords, but haven't found anything relevant. Is there a term that I can search for to read about this idea, of defining an algorithmic complexity measure of objects/classes of objects using algorithms that are allowed to use randomness?


texts: What edge-set is required to make a non-cyclic directed disconnected graph initial?

texts:
Is there an algorithm to find the minimum set of edges required from a new node in order to make a disconnected directed graph initial?

Example -

input:

a -> b;
b -> c;
b -> d;
e -> f;
f -> g;

output:

n -> a;
n -> e;

Result:

Thanks!


texts: Algorithm which finds the maxmal solution that satisfies the following constraints

texts:
I have $a_1, a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ and an upper bound $U$ and $n$ linear equations of the form:

$k_1 * a_1 + b_1 = x$

$k_2 * a_2 + b_2 = x$

$\dots$

$k_n * a_n + b_n = x$

Additional info where $r \in \{ 1,2,\dots , n \}$:

$a_r$ is prime
$0 \leq b_r < a_r $
$k_r b_r, U, n, \in N_0$ and $(a_r\in N)$

I'm looking for an algorithm that computes the largest $x$ which satisfies all of the given equations such that for the given upper bound $U$ the additional constraint $x \leq U$ holds. If there is no such $x$ a simple "no solution" as output is fine.

First Example:

Given data:
$a_1 = 3, a_2 = 5$ and $b_1 = 1, b_2 = 2$ and $U = 20$

The $n$ equations with substituted values:

$k_1 * 3 + 1 = x$

$k_2 * 5 + 2 = x$

The solution (largest $x$ which satisfies the equations and is $\leq U$ is 7 (set $k_1 = 2$ and $k_2=1$)

Second Example:

Given data:
$a_1 = 11, a_2 = 17$ and $b_1 = 1, b_2 = 2$ and $U = 20$

The $n$ equations with substituted values:

$k_1 * 11 + 1 = x$

$k_2 * 17 + 2 = x$

The solution (largest $x$ which satisfies the equations and is $\leq U$ is "no soluton" (there is no way to set $k_1$ and $k_2$ such that the equations are equal)

I'm struggling to come up with an algorithm which solves this efficiently. Currently my best approach is to compute all values of x which satisfy the first equation, then I compute all values of $x$ which satisfy the second equation and so on until I have $n$ sets, set $i$ represents the values of $x$ which satisfy equation $i$. Then I simply intersect all of them, if the result is an empty set then I output "no solution" otherwise I output the max element of the resulting set. This approach is very inefficient :/

What do you think about my approach how could I compute the largest x which satisfies all of the constraints above more efficiently?

Note: the reason I know that there is a more efficient solution is because I have encountered this problem during a programming competition. I'm expecting that the solution will use elementary number theory since prime numbers are involved. I just don't know how else to approach this.


texts: Probability distribution of runs given k bits set in an n-bit circular buffer

texts:
Imagine you have a circular buffer holding n bits. You (uniformly) randomly set k of those n bits. (This is without replacement, so you are left with a buffer of n bits of which kbits are set.)

Now you randomly select a location in the buffer. What is the probability distribution of the run of set bits starting at that location? And what is the mean length of said run?

It's trivial that P(k,n,0) = 1 - k/n (that is, the first bit will be set with a probability of k/n, so there's a 1 - k/n chance that it will be unset.).

I think this has something to do with the hyper-geometric distribution, but I am not sure.


texts: Repeated String Match: need help to understand the maximum number of repeats needed to be looked at

texts:
There's this question on LeetCode (link):

  Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution exists, return -1.

  For example, with A = "abcd" and B = "cdabcdab".

  Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

  Note:
  The length of A and B will be between 1 and 10000.

The brute force solution provided on the website is this:

  The question can be summarized as "What is the smallest k for which B
  is a substring of A * k?" We can simply try every k.

  Algorithm

  Imagine we wrote S = A+A+A+.... If B is to be a substring of S, we
  only need to check whether some S[0:], S[1:], ..., S[len(A) - 1:]
  starts with B, as S is long enough to contain B, and S has period at
  most len(A).

  Now, suppose q is the least number for which len(B) <= len(A * q). We
  only need to check whether B is a substring of A * q or A * (q+1). If
  we try k < q, then B has larger length than A * q and therefore can't
  be a substring. When k = q+1, A * k is already big enough to try all
  positions for B; namely, A[i:i+len(B)] == B for i = 0, 1, ..., len(A) - 1.

I understand this part:

  If we try k < q, then B has larger length than A * q and therefore can't
  be a substring.

But I don't follow how the writer has arrived at this other conclusion:

  When k = q+1, A * k is already big enough to try all
  positions for B; namely, A[i:i+len(B)] == B for i = 0, 1, ..., len(A) - 1.

Why can we stop at k = q+1? Why is it not necessary to try q+2 (and q+3, etc.)?


texts:
I was reading about Run-Time Environments.
In the Dragon book (2nd ed.) I came across the following presentation:

  [To implement abstractions, the] compiler creates and manages a run-time environment in which it assumes its target programs are being executed. This environment deals with a variety of issues such as the layout and allocation of storage locations for the objects named in the source program, the mechanisms used by the target program to access variables…

so I'm getting confused about points highlighted above:

How does compiler execute the code, it is only supposed to generate the intermediate code right?
And does it create runtime environment? I mean there's not a virtual machine that the program runs on, it just runs on your computer right? When does it create a runtime environment?
Isn't memory managed by the operating system? Why is allocation of storage done by the compiler and at what point? Probably what variables are needed and how much may be known by the compiler but, how does it communicate this information to the OS?


texts: Language where every prefix has almost equal a's and b's

texts:
Is the following language regular?

$$L = \{x \in \{a, b\}^* \mid \text{in every prefix \(w\) of \(x\), } 0 \le |w|_a − |w|_b \le 2\}$$
If so, give a DFA for it with as few states as possible. If you claim that it is
not regular give a pumping lemma proof that it is not regular.

I'm doing exam prep and have tried pumping this to no avail. I think I created a DFA that works but I'm not entirely sure because pumping similar examples (i.e. if the number of a's is strictly greater than b's) yielded results that are not regular. Is my DFA correct? Or is there something I can pump that will fail the lemma?


texts: How does make/scons manage dependency graph and figure out which file need to be recompiled?

texts:
what I understand is that, the file dependency is organized as a graph. Make/scons check the timestamp of each file, when a source file's timestamp is newer than the output, it re-compile everything depend on this file.

What kind of algorithm does Make/scons use to travel the graph? what if there are circles?

I have been searching around on internet but somehow I cannot find a lot of insights.

Can someone explain to me how does make/scons work?


texts:
Is the following scenario theoretically possible, or provably impossible?

Alice generates a 1 GiB file with random bits and sends it to Bob. This file is a shared dictionary they call Q. Now, Alice and Bob starts sending each other new files with arbitrary entropy, each of them < 1 MiB, but they compress them with a clever algorithm that exploits information in Q, typically breaking the Shannon limit.


texts: Can you use binary files to reverse engineer cpu architecture?

texts: I wanted to know if it was possible to add code directly to a computer without an operating system or any programming language. To do that, I thought that maybe I could use the binary files to reverse engineer the actual cpu architecture. Just a random thought but I would like to know if that is possible.


texts: Error in solution in Types and Programming Languages?

texts:
I'm reading Types and Programming Languages and trying to understand the solution to exercise 5.2.4 on untyped lambda calculus / Church numerals:

  Define a term for raising one number to the power of another.

The proposed solution says:

  $\textrm{power2} = \lambda m. \lambda n. m~n$

In an attempt to understand how this solution works, I tried it on 01 as follows:

$$ \begin{array}{ll}
& \textrm{power2}~c_0~c_1 \\
\rightarrow & c_0~c_1 \\
= & (\lambda s.\lambda z.z)~c_1 \\
\rightarrow & \lambda z.z
\end{array}$$

The result doesn't look like a Church numeral to me. Is it an error in the solution, or have I misunderstood something?


texts: In which category is the supercomputer SUMMIT according to Flynn's taxonomy?

texts:
I have read that the POWER9 processor is an SIMD processor.
I have also read that most supercomputers are MIMD based.

So is the SUMMIT supercomputer SIMD? And if it is can you name a supercomputer that is MIMD?


texts: Equivalence between the two definitions of NEXPTIME complexity class

texts:
Wiki gives two definitions for the NEXP complexity class:

$
\mathsf{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(2^{n^k})
$

where $\mathsf{NTIME}(f(n))$ is the set of decision problems that can be solved by a non-deterministic Turing machine which runs in time $O(f(n))$.

Using deterministic Turing machines as verifiers. A formal language ''L'' is in '''NEXPTIME''' if and only if there exist polynomials ''p'' and ''q'', and a deterministic Turing machine ''M'', such that

For all ''x'' and ''y'', the machine ''M'' runs in time $2^{p(|x|)}$ on input $(x,y)$
For all ''x'' in ''L'', there exists a string ''y'' of length $2^{q(|x|)}$ such that $M(x,y) = 1$
For all ''x'' not in ''L'' and all strings ''y'' of length $2^{q(|x|)}$, $M(x,y) = 0$

Is it obvious to see why these two definitions are equivalent? (if not, any way to prove they are equivalent?)


texts:
Is there a reduction from SUBSET-SUM to SAT?
Just general SAT, not 3-SAT.
Also the given multiset S only has positive integers.
SUBSET-SUM is defined as follows:
Input: a multiset S = { x1 , ... , xn } of positive integers and a positive integer t
Output:
accept if there exists a sub-multiset { y1, …, ym } ⊆ S such that y1 + ··· + ym = t
reject otherwise
x1 , ... , xn and t are encoded in binary notation.
The boolean formula SUM should be used in the reduction.
Let a1···ak, b1···bk, c1···ck be k-bit integers.
SUM(a1, ... , ak, b1, ... , bk, c1, ... , ck) is true iff (a1···ak) + (b1···bk) = c1···ck
For example, if k = 3, sum(0, 1, 1, 1, 0, 0, 1, 1, 1) is true because 011 + 100 = 111.
Can this be done?
For example, what would the boolean formula produced by the reduction look like for
S = { 010, 011, 011, 100 }
t = 110


texts:
I've watched multiple videos and read posts regarding modern cpus and how they work.

However, those ones very rarely touch the problem on the very basic level.
Like I've read about transistors and stuff but I would like to spend (a lot I guess) time to actually understand how e.g. programming a math operation like 5^5 is calculated by cpu hardware.

Do you have any ideas where to start?

p.s. my uni background is econometrics which ended up in machine learning job. Unfortunately I have no CS knowledge.

Kind Regards,
Matt

The recommended online resource I found was: Hoow do it know


texts: Finding nearest of a list of points on Euclidian plane to a given reference point

texts:
Problem formulation: Given a list $L$ of $n$ points in the Euclidian plane and a reference point $R$ also in that plane, find a closest point $P\in L$ such that, for all $X\in L$, $|PR|\le|XR|$.

Aditional constrains: Trivial algorithm will just iterate all candidate points in $L$, compute their distance to $R$ and select the closest. Complexity of that is $O(n)$, but the number of points may be huge – I need an algorithm that runs in time $O(\log n)$.

Any preprocesing (building data structures etc.) can be done with $L$ but it should run in $O(n\log n)$ time.

Problem extensions: In case that there are multiple closest points $P$ with the same distance from $R$ it would be nice if the algorithm identified that and returned all of them.

I will actually need to detect $m$ nearest points ($m$ is much smaller then $n$). I can do that by running algorithm to find single closest point $m$ times, each time excluding previously found points from search. However it would be nice it the algorithm could be extended to find $m$ closest points in one call.


texts: Travelling Salesman problem using Guided Local Search

texts:
I am doing Week_4 of https://www.coursera.org/learn/discrete-optimization/
stuck in solving TSP.
As there are a lot of methods to solve this problem, I am currently coding
Guided Local Search as described here.
This basically penalizes the longest edge and repeatedly searches that neighborhood until no improvement found. To search the neighborhood faster, it uses Fast Local search which basically marks a vertex inactive if no improving (2-Opt) moves are found.

My problem is that I do not see any improvement after the first Fast Local Search(FLS).
Any insights on this?

Also, what is the suggested method to solve TSP in order to ease?
Like I know these are methods
- Simulated Annealing with re-heat.
- Mixed Integer Programming(MIP) with Gomory Cut.
- LK(Lein-Kerninghan), LKH, ILKH heuristics
- GLS+FLS (I find this easy to start with)
- Hybrid approaches like MIP + SA.


texts: Domino tiling of a 2xN rectangle in O(ln n)

texts:
I solved this problem using Dynamic Programming in $\mathcal{O}(n)$ time. I found that is equivalent to the Fibonacci Numbers.

$F(0) = F(1) = 1$

$F(n) = F(n-1)+F(n-2)$

Where the $F(n-1)$ term is from fixing the left most domino vertically, and the $F(n-2)$ from fixing it horizontally (which implies that the domino under it must also placed horizontally).

Because the Fibonacci Numbers can be generated in $\mathcal{O}(\lg n)$ using

$F(2n) = F(n)F(n+1)+F(n-1)F(n)$

$F(2n+1) = F(n)F(n)+F(n-1)F(n-1)$

Then I try to find the same expression from the domino tiling. Again, I classify all possible tilings in two set. First, all tiling like the one below

Therefore, $F_H(n) = F(i)F(n-i-2)$. Because I want to split in the middle (or close) I consider $n=2k, i=k$ and $n=2k+1, i=k$.
Then

$F_H(2k) = F(k)F(2k-k-2) = F(k)F(k-2)$ and $F_H(2k+1) = F(k)F(2k+1-k-2) = F(k)F(k-1)$.

Then, all tiling of the form

Again, $F_V(n) = F(i)F(n-i-1)$ and when $n=2k, i=k$ and $n=2k+1, i=k$ we have

$F_V(2k) = F(k)F(2k-k-1) = F(k)F(k-1)$ and $F_V(2k+1) = F(k)F(2k+1-k-1) = F(k)F(k)$

Combining all the former expressions,

$F(2k) = F_H(2k) + F_V(2k) = F(k)F(k-2) + F(k)F(k-1)$

$F(2k+1) = F_H(2k+1) + F_H(2k+1) = F(k)F(k-1) + F(k)F(k)$

However, those final expression does not produce the same numbers. Because they look really similar I belive my approach is not completly wrong but I can not find where I make my mistake.

Final notes:

In the first classification, I fix the top most domino horizontally and if I consider a 1-tile shifted horizontal domino (left or right) under it, then the rectangle can not be tiled.
For the (correct) expression $F(2n+1)=F(n)F(n)+F(n-1)F(n-1)$, notice that $F(n)F(n)$ can be mapped to the second case, because $n+1+n = 2n+1$, but the other term $F(n-1)F(n-1)$ can not (at least in the same way), $(n-1)+2+(n-1)\neq 2n+1$. The same can be notice in $F(2n)$ and again one term can be mapped to the second case while the other can not (to the first case). I belive my mistake should be around the first case.


texts: Why does the reduction from 3SAT to IS work?

texts:
I was reading about the reduction from 3SAT (input: formula) to Independent set (input (graph, k)) in order to prove that the latter is in NP-Complete. The reduction i've seen follow the next steps:

For each clause at the input, create a node for every variable it contains in case it doesn't exist yet. Then, create a $K_3$ with these nodes.
Create an edge between a node and its negation.

An example i found:

While proving this reduction is correct, they say:

  $\Rightarrow$) If the formula is satisfiable, there is at least one true literal in each clause. Let S be a set of one such true literal from each
  clause. |S| = k and no two nodes in S are connected by an edge.

I don't understand why this works. I mean, $k$ is fixed at this point (from the input) so if $k=3$ i can take $S=\{x_1, x_3, x_4\}$. If $k=2$ i can take $S=\{x_2, x_4\}$ but if $k=1$ i can't.

Could you explain me why this works or if i am not understanding anything correctly? Thanks.


texts: backpropagation algorithm seems to be forcing output values to middle than extremes

texts:
I have been playing around with artificial neural networks lately, specifically with the prospect of trying to replace the contrastive divergence algorithm with some type of evolutionary metaheuristic technique (i have been working with PSO) to do unsupervised pre-training, but I have come up against some issues when trying to implement the backpropagation algorithm to then fine-tune the connection weights to create a classifier.

I am using a reduced version of the MNIST dataset consisting of just the '0's and '1's to try and develop a binary classifier than is capable of distinguishing between the two different classes.

The output of my network is two visible nodes that are supposed to output [1 0] if the data is classified as a '0' and [0 1] if the data is classified as a '1'

before learning with the backpropagation algorithm i have about a 30% classification error using the quadratic error, and as i perform the supervised learning, the error gets pushed towards 12.5% but stays there as if there was an asymptote.

I thought this was showing that it was improving the classification, however when i examined the output of the network, it was just showing that with each iteration, the activations of the output nodes were moving closer to [0.5 0.5] before settling there.

before backpropagation was applied it was giving output values of [0.75 0.2] (for example) - and any attempts to train it using backpropagation just pushed those values toward [0.5 0.5] rather than amplifying the difference.

can anyone offer any insight as to why this might be happening? is this a common problem when training neural networks? or does it just sound like an implementation bug? i have implemented my backpropagation algorithm in a similar fashion to that which is found here.


texts: What are the concequences of the unit type and the unit value being the same?

texts:
What are the practical and theoretical implications of the unit type and the unit value being the same or different entities?

For example, in Haskell the unit type and unit value are both spelled (). In ML, the unit type is spelled unit and it's value is ().

Are there any problems that arise from either option? Are there any significant benefits perhaps to the soundness of the type-system or the ability to reason about programs?


texts: How to show that if a relativized PH collapses, then PH collapses itself

texts:
Let $A$ be an arbitrary set in PH. Suppose PH$^A$ collapses.

I am now asked to show that PH itself must collapse.

I have remarked that, since $A$ is in PH, $A$ must in particular be in one of the $\Sigma_i$'s, say $A\in\Sigma_n$ for $n\in\Bbb N$. Also, PH$^A$ collapses, so PH$^A = (\Sigma_m)^A$ for some $m\in\Bbb N$.

But from there, I am not able to finish the proof. Is this the right way to go, and how should I finish this proof?

EDIT The exact question is the following

Give a definition of PH
Fix any set $A$. What is the lowest lever of the relativized hierarchy
PH$^A$?
Suppose that $A\in\text{PH}$ and that PH$^A$ collapses. Show that PH collapses.

Of course, 1 and 2 are irrelevant.


texts: Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines

texts:
I'm considering an automaton $A$ over a alphabet $\Sigma$, with a set of states $Q$, such that $\Sigma \subset Q$, which includes special "accept" and "blank" states not in $\Sigma$. It also has an infinite list of cells, which begins with the input string, the rest being blank. It has a transition function $\delta: Q \times Q \times Q \to Q$. The automaton computes by updating the value  of the middle cell, $a$, using $\delta(x,a,y)$. The automaton accepts if any cell is in the accept state. From what I understand, this automaton is very similar to a 1-dimensional cellular automaton, with the addition of the accept state.

I'm trying to prove that a language is recognizable by a Turing machine if and only if it can be recognized by the automaton described.

I've been trying to do a proof by construction, but I'm really lost. I did some research on cellular automata, but the material I've been finding is way over my level. I know somehow I'm going to have to construct a TM from CA, and vica versa, but I'm not even sure how to get started. I would really appreciate any help.


texts: Are there any problems in $APX - PTAS$ that are not $APX$-complete?

texts:
I have a question about the structure of the complexity class $APX$. Obviously, unless $P=NP$, no problem in the class $PTAS$ can be $APX$-complete (under the AP-reduction). However, what about the rest of problems in $APX$? Are there any problems known that are in $APX$, do not have a $PTAS$ (unless $P=NP$) and at the same time are provably not $APX$-complete (unless $P=NP$)?

For the class $NP$, Ladner's Theorem guarantees the existence of problems in $NP - P$ that are not $NP$-complete (unless $P=NP$) - the so-called $NP$-intermediate problems. I am curious if any similar result has been proved for $APX - PTAS$ with respect to approximation preserving reductions.

It is possible that the answer to this question is trivial - to be honest, the only $APX$-complete problem I know is MAX-3-SAT. However, I wonder how hard it is with respect to other problems in $APX - PTAS$.


texts: Why have only 15 bits been apportioned for the exponent in the 128-bit quad-precision datatype?

texts:
I look forward to the day we can start using quad-precision numbers, but was disappointed to see that in the specification, only 15 bits out of a whopping 128 were assigned to the exponent as shown by Wikipedia. That's only 4 bits more than we had for doubles!

This allows for great precision, but we sacrifice the high number range. In my years of programming, I have always found extremely high numbers to be pretty useful for various calculations and purposes, and sometimes the 'double' doesn't cut the mustard. It also helps simplify many algorithms when we don't need to worry about number overflow.

I was just wondering if the seemingly heavy bias towards precision had a good reason. Are there practical purposes for such extreme precision?


texts: Floating point bitwise comparator. If f1 and f2 are floating point numbers with the following properties can we always say f1 > f2?

texts:
Recall floating-point representation:
Suppose $f$ is a floating-point number then we can express f as,
If $f$ is normal:
$$(-1)^{s}\cdot2^{e-127}(1 + \sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k})$$
If $f$ is denormal/subnormal: $(e = 0)$
$$(-1)^{s}\cdot2^{-126}(0 + \sum\limits_{k=1}^{23} b_{23-k}\cdot 2^{-k})$$
where

$s$ is the sign of $f$.
$e$ is the stored exponent of $f$. This means $e-127$ is the effective exponent of $f$.
$b_k$ is the $k$-th bit of $f$ where $b_0$ is the LSB and $b_{22}$ is the MSB.

Let $f_1$ be a floating-point number with constants $s_1, e_1,$ and $b_{1k}$.
Let $f_2$ be a floating-point number with constants $s_2, e_2,$ and $b_{2k}$.
I'm trying to find out if the following statement is true: $e_1 > e_2 > 0$ and $s_1 = s_1$ then $f_1 > f_2$.
My initial strategy was to subtract $f_2$ from $f_1$ and show that it must be strictly greater than $0$.
What I have so far.
$
\begin{align*}
f_1-f_2 &= 2^{e_1-127}(1 + \sum\limits_{k=1}^{23} b_{1,23-k}\cdot 2^{-k}) - 2^{e_2-127}(1 + \sum\limits_{k=1}^{23} b_{2,23-k}\cdot 2^{-k})\\
&= 2^{-127}(2^{e_1}(1 + \sum\limits_{k=1}^{23} b_{1,23-k}\cdot 2^{-k}) - 2^{e_2}(1 + \sum\limits_{k=1}^{23} b_{2,23-k}\cdot 2^{-k})) \\
&= 2^{-127}(2^{e_1} + \sum\limits_{k=1}^{23} b_{1,23-k}\cdot 2^{e_1-k} - 2^{e_2} - \sum\limits_{k=1}^{23} b_{2,23-k}\cdot 2^{e_2-k})\\
&=2^{-127}(2^{e_1} - 2^{e_2} + \sum\limits_{k=1}^{23} b_{1,23-k}\cdot 2^{e_1-k} - \sum\limits_{k=1}^{23} b_{2,23-k}\cdot 2^{e_2-k})\\
&=2^{-127}(2^{e_1} - 2^{e_2} + \sum\limits_{k=1}^{23}(b_{1,23-k}\cdot 2^{e_1-k}-b_{2,23-k}\cdot 2^{e_2-k}))
\end{align*}
$
Now since $e_1 > e_2 \iff e_1-e_2 > 0 \iff 2^{e_1}-2^{e_2} > 1$ we have that:
$
\begin{align*}
f_1-f_2 & > 2^{-127}(1 + \sum\limits_{k=1}^{23}(b_{1,23-k}\cdot 2^{e_1-k}-b_{2,23-k}\cdot 2^{e_2-k}))
\end{align*}
$
In order for the above to always be greater than zero I require that $\sum\limits_{k=1}^{23}(b_{1,23-k}\cdot 2^{e_1-k}-b_{2,23-k}\cdot 2^{e_2-k}) > -1$.
However, I don't know how to formally show this. Any help/hints are much appreciated as inequalities are not my strong suit.


texts: How can Turing complete machines exist theoretically if the halting problem is undecidable

texts: As the question says, if I input on the tape of a Turing complete machine a program that solves the halting problem with the correct inputs the program will never end its execution regardless of memory and time. Isn't the halting problem a computational problem that can't be executed by a Turing complete machine so that it's halts sometime?


texts: what does "vector" mean in computer science?

texts:
I am trying to understand how computers work under the hood, and I came across following sentence.

"Computer technology is based on electronic circuits able to process vectors of 0's and 1's. For that reason all data are encoded by strings of 0's and 1's."

So does the vector mean normal string/number 0 and 1?

Thank you


texts: MAX 2-SAT is polynomial time reducible to 2-SAT?

texts:
I know that 2-SAT is solvable in polynomial time and 2-SAT is NP-Hard.

I have issue about this statement:
MAX 2-SAT is polynomial-time reducible to 2-SAT. Can you explain to me how reduction looks like? I need the only intution about that, but not proof.


texts: How many random walks to start from each node?

texts:
Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of neighbors).

A random walk ends when it returns to the initial node or when the walk takes 3 steps.
If we start random walks from each node on this graph, should we start equal number of walks from each node? If so, nodes with small degrees will often return to where they started, and we will not learn big portions of the network. This is because small degree nodes are neighbors of small degree nodes more often, so there will not be many paths to walk on.

I believe there should be a way to decide on the number of walks to minimize computational costs.


texts: What happens to the cache contents on a context switch?

texts:
In a multicore processor, what happens to the contents of a core's cache (say L1) when a context switch occurs on that cache?

Is the behaviour dependent on the architecture or is it a general behaviour followed by all chip manufacturers?


texts:
I am trying to create a DFA that can recognize strings with alphabet $\{a,b,c\}$ where $a$ and $c$ appear even number of times and where $b$ appears odd number of times.

I am wondering that this may only be expressed with other methods such as Turing machine or context-free languages.

You might find it fun to think of the solution.


texts: Turing machine that accepts L = {#a != #b}

texts:
Trying to figure out how to make a deterministic single-tape Turing machine for the language of words comprising as many $a$'s as $b$'s.

I am very confused, because I can't figure out how I would keep track of how many $a$'s and $b$'s there would be. The method for finding $a^nb^n$ goes right and back left to do this but this language would include things like $abaaaababab$.

How can I keep track of number of $a$'s and $b$'s?


texts: Checking whether a number divides any of a set of other numbers

texts:
Consider a static set $S$ of positive numbers from range $[1..10^9]$. Is there an efficient algorithm to answer queries of the form: "Given a number $d$ is there an element $x \in S$ such that $d | x$".

Simple straightforward check takes $O(|S|)$ time per query and uses $O(|S|)$ memory.
Storing all the divisors for every element of $S$ makes query time $O(1)$ but uses too much memory and precomputation time $O(|S| \times \sqrt{|\max(S)|})$.

I'm interested in an algorithm that uses less memory than second solution (because $|S| \sim 10^6$) and still somewhat faster queries than first solution (number of queries is also $\sim 10^6$).


texts: Can Stoer-Wagner find min s-t cut for given s and t?

texts: Stoer-Wagner algorithm can be used to find global minimum cut in a graph. I'm wondering if it could be adapted to find a minimum s-t cut, given s and t. We can start a single phase with {s} but there's no guarantee that vertex t will end up in the other subset. Is there any way to do it?


texts: How to efficiently divide a grid with some predefined sub-rectangles?

texts:
Given an $M$x$N$ grid with some predefined sub-rectangles. How to divide the grid into a set of sub-rectangles, which contains the predefined sub-rectangles, so that its the number of elements is minimum and no sub-rectangle is overlapped ?

Is there any reference to the problem and it's solutions ? Is the problem NP-Hard ?

For example:
A grid contains 2 predefined (black) sub-rectangles might be divided as follow:


texts: Algorithm to write a dictionary using thousands of words to find all anagrams for a given string with O(1) complexity

texts:
Problem Statement:
Suppose we have a thousands of words and we need to maintain these words in a data structure in such a way that we should be able to find all anagrams for a given string.
I tried to achieve this with O(1) complexity.

I am looking for a algorithm to implement above scenario. I implemented this problem with below algo, but I feel that we can improve its complexity. Any suggestion will be helpful.

Algorithm:

Here is trick to utilise hash code, we can also use character histogram.

Step 1:Create an array of prime numbers.

   int primes[] = {2, 3, 5, 7, ...};

   We are using prime number to avoid false collisions.

Step 2:Create a method to calculate hash code of a word\string.

   int getHashCode(String str){
     int hash = 31;
     for(i =0 to length of str){
        hash = hash*primes['a' - str.charAt[i]];
     }
     return hash;
   }

Step 3: Now store all words in a HashMap.

void loadDictionary(String[] words){

  for( word from words for i = 0 to length of words)   {
     int hash  = getHashCode(word);
     List<String> anagrams = dictionary.get(hash);
     if(anagrams ! = null){
         anagrams.add(word);
     } else
        List<String> newAnagrams = new ArrayList<String>();
        newAnagrams.add(word);
        dictionary.put(hash, newAnagrams);
     }
  }
}

Step 4: Now here is the approach to find anagrams:

   int findNumberOfAnagrams(String str){
      List<String> anagrams = dictionary.get(getHashCode(str));
      return anagrams.size();
   }


texts: How to enumerate all partitioning of a set to k-subsets of size at most b

texts:
I'm looking for an algorithm to generate/enumerate all possibilities for partitioning a set of size $n$ to $k$ non-empty subsets, each with size at most $b$.

More specifically, given a set $V$ where $|V|=n$, how to enumerate all possibilities to choose subsets $X_1, ..., X_k \subseteq V$ such that

1) $1 \leq |X_i| \leq b$,

2) $\forall_{i \neq j} X_i,X_j  :$  $X_i \cap X_j = \emptyset$,

3) $\bigcup_{i \in \{1,...,k\}} X_i = V$,

Two partitioning are different if they do not have exactly same subsets. The order of subsets doesn't matter.

Can anyone suggest an approach to enumerate such partitioning?


texts: How is a 2-bit predictor better than a 1-bit predictor at determining loop iterations

texts:
I have read various explanations why a 1-bit branch predictor is wrong twice per loop, once at the beginning when it wrongly predicts against entering the loop and once at the end when it wrongly predicts against leaving the loop.  Makes sense.

What I don't understand is why the 2-bit predictor is better.  It seems it could even be worse, since it might well predict against entering the loop in the first place, hold to that prediction for a second time before beginning to be "right," and then still wrongly predict against leaving the loop at the end.

I could live with "in practice it turns out to not happen that way all that often," but most of these explanations don't seem to be based on such.  Rather, they seem (to me) to begin with a demonstration how the 1-bit predictor fails twice, and then merely state that the 2-bit predictor does better without demonstrating that it does.

So...what am I missing?


texts:
I recently learned about the rolling hash data structure, and basically one of its prime uses to searching for a substring within a string. Here are some advantages that I noticed:

Comparing two strings can be expensive so this should be avoided if possible
Hashing the strings and comparing the hashes is generally much faster than comparing strings, however rehashing the new substring each time traditionally takes linear time
A rolling hash is able to rehash the new substring in constant time, making it much quicker and more efficient for this task

I went ahead and implemented a rolling hash in JavaScript and began to analyze the speed between a rolling hash, traditional rehashing, and just comparing the substrings against each other.

In my findings, the larger the substring, the longer it took for the traditional rehashing approach to run (as expected) where the rolling hash ran incredibly fast (as expected). However, comparing the substrings together ran much faster than the rolling hash. How could this be?

For the sake of perspective, let's say the running times for the functions searching through a ~2.4 million character string for a 100 character substring were the following:

Rolling Hash - 0.691 seconds
Traditional Rehashing - 71.009 seconds
Just comparing the strings (no hashing) 0.100 seconds

How could the string comparing be so much faster than the rolling hash? Could it just have something to do with the particular language I tested this in? Strings are a primitive type in JavaScript; would this cause string comparisons to run in constant time?


texts: Why is finding the closest pair of points by brute force search O(n^2)?

texts:
If I have n points A, B, C, D it seems like finding the closest pair via  brute force search would go like:

Compare A to every item (n-1)
Compare B to every item (except A which it has already been compared to)
etc for every element.

This seems like it would be less than $O(n^2)$ because the you are comparing to a progressively smaller number of elements each time you go to the next element.

Can someone explain to me why this is $O(n^2)$?


texts:
I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is:

  Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, find the subset $S$ of the items that maximizes $\sum_{i \in S} w_i$ while keeping this sum at most $W$. Or the decision version: Is there a subset obeying the at-most-$W$ rule with weight at least some number $k$.

So just Knapsack except the values are the weights themselves.

The second and seemingly more common is:

  Given a set of $n$ integers, is there a non-empty subset whose sum is 0 (or equivalently, some number $k$)?

E.g., my textbook (Kleinberg and Tardos) as well as this
have the first one. Wikipedia and other websites have the second.

I believe both are NP-complete. That said, I haven't found an "obvious reduction" from one to the other that suggests why the two problems are given the same name. So my questions are:

Do quick reductions exists between the two?
Why are these given the same name in the first place?


texts: Interactive protocols for showing knots are "hard" to untie

texts:
Given two graphs $G_1$ and $G_2$, a zero-knowledge interactive protocol for a prover to convince a verifier that $G_1\not\cong G_2$ entails:

The verifier choosing a random $i\in\{1,2\}$
The verifier choosing a random permutation $\pi$
The verifier sending a graph $G_3=\pi(G_i)$ to the prover
The prover sending $j\in\{1,2\}$ to the verifier
The verifier accepting if $i=j$

A public coin Arthur-Merlin protocol for Merlin to prove to Arthur that $G_1\not\cong G_2$ is more involved, and includes Arthur publicly tossing coins to determine a hash function $h$ and a random $y$, and Merlin finding a preimage $x$ of $h$, such that $h(x)=y$.  The proof relies on the fact that the number of permutations of a given $d$-vertex graph is known, and hence two non-isomorphic graphs will "generate" a larger set, after a random permutation, than two isomorphic graphs.  Accordingly it is easier to find a preimage $x$ of $h$ if the codomain of $h$ is large.

My questions are: can the same ideas be extended to show that two knots $K_1$ and $K_2$ cannot be converted to each other in fewer than $n$ Reidemeister moves, for either protocol?

For example, would the following work as a private coin protocol to show that one knot $K_1$ cannot be easily "untied" to another knot $K_2$ in fewer than $n$ moves?

The verifier chooses a random $i\in\{1,2\}$
The verifier chooses up to $n$ random sequence of Redeimester moves
The verifier sends to the prover a knot diagram $K_3$ which is the knot diagram corresponding to $K_i$ after the random Redeimeister moves have been applied
The prover responds with $j\in\{1,2\}$
The verifier accepts if $i=j$

Similarly, for the public-coin protocol, do we know enough about applying random Reidemeister moves to a knot diagram to know how "big" a set of knot diagrams would be, after $n$ random Reidemeister moves?  That would let us know the parameters for the public coin protocol, e.g. the codomain of the hash...

EDIT

Considering @D.W.'s comments, I think it's possible for a protocol to be sound if we were to make the verifier bound to $c_{max}$ the maximum crossing number of the knot diagram presented to the prover in step 3, and if the random moves in step 2 above were doubly-stochastic, meaning that a Markov-chain on the walk of random knot moves has a uniform limiting distribution $\pi$ over all knot diagrams equivalent to $K_i$ for the chosen $i$.

If both $K_1$ and $K_2$ are of the same knot type, as long as $n$ - the number of Reidemeister moves done in step 2 - was large enough so the chain was properly mixed, a prover would not know which $i$ was chosen, because the knot diagram presented to her is randomly chosen from all knot diagrams of crossing number $\le c_{max}$ that are equivalent to $i$.


texts:
Possible Duplicate:
  A variant of the Assignment Problem

(Not a comp.scientist, but have the basic research. Please excuse me if I've overlooked anything obvious.)

In my variant of the problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task needs to be assigned to exactly $m$ or $m+1$ agents.

It is guaranteed that this is possible: the segment $[ |A|n, |A|(n+1) ]$ intersects the segment $[ |B|m, |B|(m+1) ]$.

Each agent-task combination yields a profit, and I want to maximize the profit.

Is this a special case of one of the known problems? How can this be solved? If not practical for $n=100000$, what are good approximations and what is their complexity?

Cheers!


texts: Efficient integer multiplication using BDDs and fixed point

texts:
Suppose we have two sets A,B of size n,k respectively, being sets of nonnegative integers each encoded with N bits, and we'd like to form a set of bitstrings of length 3N and [maximum] size n*k such that they represent all possible multiplication of integers, one taken from A and one taken from B. So if one set is {1,2} and the other is {3,4} (written bitwise), the resulted set should be {1*3, 1*4, 2*3, 2*4}.

Suppose A,B are given as binary decision diagrams (BDDs) and we'd like to calculate the multiplication set also in a form of a binary decision diagram, representing the bitstrings of all multiplication results.

Now it is well known that BDDs that represent multiplication, even if A,B were of size 1 each, is of exponential size. Otherwise we could factor integers in polynomial time.

My question is whether the multiplication set can be calculated in polynomial time indeed, but by iterating BDD operations until a fixed point is achieved. This way we won't be able to factor integers (at least not easily). For example it is well known that we can calculate addition of binary numbers by iterating AND and XOR until a fixed point is reach (each step yields intermediate addition and carry, to be added again until the carry is zero).

I need that for practical implementation of mine, where indeed I have two sets of fixed-bitwidth integers represented in BDDs, and I'd like to calculate their multiplication set, without having to "decompress" the BDDs into actual numbers, as each BDD may encode many numbers.


texts: What is the result of multiplying O(n) and Ω(n)?

texts:
If $f(x) = \Omega(n)$ and  $g(x)= O(n)$, what would be the order of growth of $f(x) \cdot g(x)$ ?

First I figured it should $\Theta(n)$ , as two extremes would cancel each other and the order of growth will be same as $n$

But, where I came across this question, the answer given was $\Omega(n)$, and no proof was mentioned. Well, I didn't understand why, but intuitively I convinced myself as "you can't know for sure the upper limit of growth for $f(x) \cdot g(x)$ so you can't say it's $O(n)$, but you can be sure that it won't be lower than $\Omega(n)$"

Can someone help me in understanding this, in a more believable way?


texts: Why do all non-empty ω-regular languages have periodic members?

texts:
I was learning about Büchi Automata and couldn't understand a part where they were describing "Non-empty $\omega$-regular languages contain periodic strings"

  Let $A$ be a Büchi automaton and $s ∈ L^\omega(A)$. There is an accepting run $r$ of $A$ on $s$ such that $q ∈ \text{Inf}(r)$, for some $q$. Then, there exist finite strings $s_0$ and $s_1$ such that $s_0s_1$ is a prefix of $s$, and such that $A$, after processing $s_0$ is in $q$, and after processing $s_0s_1$ is also in $q$. Then, the periodic string $s' = s_0s_1s_1s_1 \dotsm$ is accepted by $A$ since there is a run on $s'$ that contains $q$ infinitely many times.

I bolded the part I'm having trouble understanding.
Why is it that we can say after running a prefix like $s_0$ we are in an accept state $q$?
It seems to me a prefix could easily end in some not accepting state (i.e not in $\text{Inf}(r)$).


texts: Data addresses with ADD instruction in various architectures?

texts:
How many data addresses are specified in an ADD instruction in accumulator based architecture, stack based architecture, and in the most common register-based architecture?

I'm not sure what I should look at - diagrams? Assembly code? Thank you for any help in advance!


texts: A tree which each node selected as a root results in a different topology?

texts: Show that, for every n >= 7, there exists a tree of n non-labeled nodes such that picking each of the n nodes as a root results in a different rooted tree.


texts: Powerset generation using recursion and time complexity

texts:
I have a program that generates power set of a given string, the set being the characters of the string.

public static Set subsets(String s) {
    Set subsets = new HashSet();
    if (s.length() == 0) {
        subsets.add("");
    } else if (s.length() == 1) {
        subsets.add("");
        subsets.add(s);
    } else {
        for (int i = 0; i < s.length() - 1; i++) {
            Set sets = subsets(s.substring(i + 1));
            for (String st : sets) {
                subsets.add(s.substring(0, 1) + st);
            }
            subsets.addAll(sets);
        }
    }
    return subsets;
}

I don't seem to understand how to calculate time complexity of the above implementation.I understand that String.substring and creating Set Objects are pretty expensive, but if I assume these two operations to take constant time, what would be the overall time complexity?


texts: An AVL tree is a BST, but AVL tree can be not complete, then why do we define AVL tree a BST?

texts: An AVL tree is a BST, and a BST is a complete tree, but AVL tree doesn't necessarily have to be complete. Thus, why do we define AVL tree a BST?


texts: How can we form a graph from this problem?

texts:
So from the above diagram, we can move either right or down. So a binary tree is built that way. It's written "If we had intermingled common nodes across different branches, we would have got a graph instead" I am unable to visualize how a graph can be formed out of this. Will it be a graph with only 2 columns? Please help

Source: https://loveforprogramming.quora.com/Backtracking-Memoization-Dynamic-Programming


texts: Prove that different definitions of big-Oh with n>=1 or n>N are equivalent

texts:
I am coming across two slightly different definitions of big-oh and need to prove that they are equivalent to each other:

Definition 1: f(n) = O(g(n)) if there exists constants c and N such that f(n) ≤ c g(n) for all n > N.

Definition 2: f(n) = O(g(n)) if there exists a constant c such f(n) ≤ c g(n) for all n≥1.

Intuitively I know that if we choose c large enough we can get rid of N like in definition 2. But how to prove that if definition 1 implies definition 2, and vice versa.

Assume g(n)>0 for all values of n (I need to prove this equality when it holds).


texts:
I am interested in the complexity of the restricted version of the vertex cover problem below:

Instance: A bipartite graph $G =(L, R, E)$ and an integer $K$.
Question: Is there $S \subset L$, $|S| \leq K$ and every vertex in $R$ has a neighbor in $S$ $( S$ is vertex cover for $R)$

Vertex cover is $\mathsf{P}$ if $S \subset L \cup R$ and cover $L \cup R$; and it is $\mathsf{NP}$-complete for nonbipartite graphs. However, the problem I am looking at does not fit in either cases. Any pointers where I could find an answer will be appreciated.


texts: How to generate a binary string so to minimize weighted bitwise distance?

texts:
I've got an array of weights, for example

[1, 0, 3, 5]

The distance between two strings is defined as a sum of weights for different bits, like this:

size_t distance(const std::string& str1, const std::string& str2, const std::vector<size_t>& weights) {
  size_t result = 0;
  for (size_t i = 0; i < str1.size(); ++i) {
    if (str1[i] != str2.at(i))
      result += weights.at(i);
  }
  return result;
}

and starting string for example

'1101'

I need to generate strings in the way that strings with lowest distance from the original one go first, like this:

'1001'  # changed bits: 2nd. Because it has lowest weight. Distance is 0
'0101'  # changed bits: 1st.                               Distance is 1
'0001'  # changed bits: 1st, 2nd.                          Distance is 1
'1011'  # changed bits: 2nd, 3rd.                          Distance is 3
'1111'  # changed bits: 3rd.                               Distance is 3
'0111'  # changed bits: 1st, 3rd.                          Distance is 4
'0011'  # changed bits: 1st, 2nd, 3rd.                     Distance is 4
'1100'  # changed bits: 4th.                               Distance is 5
'1000'  # changed bits: 2nd, 4th.                          Distance is 5
'0100'  # changed bits: 1st, 4th.                          Distance is 6
'0000'  # changed bits: 1st, 2nd, 4th.                     Distance is 6
'1110'  # changed bits: 3rd, 4th.                          Distance is 8
'1010'  # changed bits: 2nd, 3rd, 4th.                     Distance is 8
'0110'  # changed bits: 1st, 3nd, 4th.                     Distance is 9
'0010'  # changed bits: 1st, 2nd, 3rd, 4th.                Distance is 9

I don't need code, I need just an algorithm which gets string of length N, array of weights of the same length and i as input and generates i-th combination, without generating the whole list and sorting it.


texts: Max number of configurations of a Turing Machine

texts:
I was wondering about a result in the Sipser book which states that any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$.

Is this because a configuration consists of a state, a position of the head and the contents of the work tape, which is $\vert Q \vert \cdot f(n) \cdot \vert \Gamma \vert ^{f(n)}$. To be honest I'm not quite sure why this is equal to $2^{O(f(n))}$. Wouldn't this only be the case when your work tape alphabet consists of 2 symbols?

Probably a silly question, but thanks anyway.

Also, I did not quite understand if this result changes when we consider logspace bound Turing machines.


texts: Upper bound and lower bound of a custom function T(n)

texts:
Assume a function $T(n)$:
$$T(n)=\log{\log^{*}{n}}$$
Let's define:
$$\log^{*}{n}=\min\{i\ge{0}:\log^{(i)}{n}\le1\}$$
and:
$$\log^{(i)}{n}=\log{(\log^{(i-1)}{n})}$$
Is the following $f(n)$ function an upper bound or a lower bound of $T(n)$?
$$f(n)=\log^{*}{\log{n}}$$

To see if $f(n)$ could possibly be an upper bound, I feel like the following limit needs to be gone through:
$$\lim_{n\to\infty}{T(n)}=\lim_{n\to\infty}{\log{\log^{*}{n}}}=?$$
Now I wonder if the above limit might boil down to this:
$$\lim_{n\to\infty}{T(n)}=\lim_{n\to\infty}{\log{(\min{\{\log\log\log\cdots\log^{(0)}{n}\}})}}$$
I'm not quite sure how to solve the above limit to get an idea of the upper bound of $T(n)$. Also, the lower bound is another story which I have little idea about.


texts: Median-of-Medians algorithm, calculating the constant c

texts:
I'm having trouble understanding how the calculation of the constant $c$ in the Median-of-Medians-algorithm is build up ($cn$). The only calculation I found was on Wikipedia:

$$\frac{2g(g-1)}{g-3}$$

My question: Why is it exactly minus 1 or multiplied by 2 etc.? How did this term come together?

I do understand the other parts of the algorithm, but if we have, for example $n/7$ groups, then the constant $c$ should grow accordingly. Even though that doesn't matter in the calculation of the Big-O notation I would still like to understand it to help me understand the algorithm in it's entirety. Hope you can help me.


texts:
So hey, I've recently found this problem online and I tried hard to solve but couldn't found an efficient solution. The problem statement is:

Given and two integers $n$ and $k$ and an array $A$ containing $n$ pairs of integers of the form $(a, b)$ and $d$ defined as $d = |\sum_{x \in E} x[1] -x[0]| $ where is $E$ is a subset of $A$ containing exactly $k$ elements. Find the minimum value of $d$.

To illustrate the problem, consider $n = 3$, $k = 2$,  $A = [(2, 1), (0, 2), (1, 2)]$.

The minimum value of $d$ is $0$. We can pick $E = [(1, 2), (2, 1)]$ containing $k = 2$ values of $A$ then $d = |(1 - 2) + (2 - 1)| = |0| = 0$.

I tried to solve this problem but only came up with the brute force solution which is terrible in terms of time complexity.

  How can one solve this problem efficiently ?


texts: Some questions regarding compilers and assemblers

texts:
Lots of basic questions are there in my mind. I need to clear them.

Statement 1: A compiler converts a human-readable codes to object codes, and those are converted to a machine code (executable) by linker.

Am I right here?

At wikipedia, it is written that

Object files are produced by an assembler, compiler, or other language
translator, and used as input to the linker.

Question 1: An assembler converts assembly language code (MOV A, B ADD C) to machine code. In case of high-level language like C++, that is generated by linker above. So assembler is not used anywhere. So how can it create an object file as written above?

Intermediate code is generated to make the code run on different architectures.

Question 2: Are *.class (bytecode) files created by java compiler object files? If yes, then can we say that the JVM that runs them is a type of linker (however its not creating the executable)?

Question 3: When we compile a C++ program in Turbo C++, we get *.obj files which are the object files. Can we use them to generate the executable in some other architecture?


texts: Find the longest path from root to leaf in a tree

texts:
I have a tree (in the graph theory sense), such as the following example:

This is a directed tree with one starting node (the root) and many ending nodes (the leaves). Each of the edge has a length assigned to it.

My question is, how to find the longest path starting at the root and ending at any of the leaves? The brute-force approach is to check all the root-leaf paths and taking the one with maximal length, but I would prefer a more efficient algorithm if there is one.


texts: Strongly NP-hard problems and Dynamic Programming

texts:
Dynamic Programming seems to result in good performance algorithms for Weakly NP-hard Problems. Two examples are Subset Sum Problem and 0-1 Knapsack Problem, both problems are solvable in pseudo-polynomial time using Dynamic Programming. It turns out this is a pretty good result in most cases.

On the other hand, Strongly NP-hard Problems seem to be essentially exponential even by using Dynamic Programming. For example, the Multiple 0-1 Knapsack Problem (page 11).

Is this a true claim if I generalize my observations and state Dynamic Programming is good for Weakly NP-hard Problems but it is not suitable for Strongly NP-hard Problems?


texts: prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves

texts:
I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction

*Edit: my professor had a significant typo in this assignment, I have attempted to correct it.

I am trying to construct a proof by induction to show that the recursion tree for the nth fibonacci number would have exactly n Fib(n+1) leaves.

that is to say that the complete recursion tree generated by the function F(n), which returns the nth fibonacci number in the sequence, has the same number of leaves as the number returned by the F(n+1), the n+1st fibonacci number.

Edit:  The complete recursion tree for n = 5 would look like this

                         F(5)
                      /        \
                 F(4)           F(3)
                /   \          /    \
             F(3)   F(2)      F(2)  F(1)
            / \      /  \     /   \
         F(2) F(1) F(1) F(0) F(1)  F(0)
        /   \
     F(1)  F(0)


texts: How to use homomorphisms to prove irregularity

texts:
I'm a bit confused on how to use homomorphims
to prove irregularity or to prove that a language is not context free.
This is what I'm currently thinking:

Example 1:
Let $L = \{ a^{i}b^{j}c^{k} : i = j = k \}$ and
$h: \{a, b, c\} \rightarrow \{a, b, \epsilon\}$ be defined as follows:
$$h(x) = \begin{cases} \epsilon & x = c\\ x & o.w.\end{cases}$$
Then it follows that
$h(L) = \{a^ib^j: i=j \} = \{a^{n}b^{n}: n \ge 0 \}$.
Now because $\{a^nb^n: n \ge 0 \}$ is known to be irregular,
then so is $L$.

Example 2:
We know that $P = \{0^p : p \text{ is a primes}\}$ is irregular
(by the pumping lemma).
Defined $h: \{0\} \to \{1\}$ as $h(1)=0$.
It follows that $h(P) =  ${1^p : p \text{ is a primes}}$ and therefore is irregular.

I wrote these as answers to an exercise but
I've been told that they are incorrect.
I don't understand why?


texts: Using A* search with different heuristic values

texts:
I am currently trying to use A* to create cyclical routes (for plotting driving routes of set distances). I want to find a driving route from my start location that is as close to my specified length as possible. If it is bigger or smaller that is fine, just as close as possible

I have therefore adapted the heuristic function to:

|target distance-distance Travelled so far| + distance left to travel.

for example, I want to travel 20 miles, so my target distance is 20. At some point in the route i may have travelled 18. Therefore my h would be 20-18+2 = 2. I always pick the smallest h value, the idea being a route of 20 miles will be created finished where i starts.

I had 2 immediate issues with this.

The Start node can't be added to the closed list immediately or it will never create a cyclical route - I believe I have solved this one.
If the search goes into a cul-de-sac it gets stuck and the openlist becomes empty and the search terminates.

The second problem I cannot think of how to solve. It occurs because the successor node that would get the search out of the cul-de-sac is already in the closed list.

Can anyone help me come up with a general solution to my problem? Furthermore do you for see any other issues with my implementation?

would really appreciate any help you can give.


texts: Proving optimality of a dynamic programming algorithm

texts:
We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ reversed. In other words, we're choosing some even-length palindrome and erasing it's "right half".

The goal is to minimize the length of the word left when no further can moves be done. In example, from a bit word $100110$ we can erase $01$ from the middle, and be left with $1010$ where no moves can be done. However, starting differently, we can reduce the word to a single $10$, which is optimal. I want to compute this minimal length for a given string, for $100110$ it would be $2$.

Now, I have a dynamic-programming algorithm which I know produces right answers (it has been tested a lot), but don't know how to prove it. It computes the best result for every substring of $s$ in increasing length. For those of length $k$, the answer is surely at most $k$. Also, it's obvious that the only strings in which no moves can be done are of form $1010...$ or $0101...$. For some word we're playing on, as it's first bit can never be erased, we know the exact form of a word that will be left from it, the only thing that we lack is it's length. Now, I assumed that for a word $t$, there exist some words $x$, $y$ that $t = xy$, and if we do the optimal operations just on $x$, producing a word $x'$, then just on $y$ producing $y'$, and in the end on the word $x' y'$, we will acquire the optimal result for $t$. The last step is very easy, because we know how words $x'$ and $y'$ look like only knowing it's lengths, so there are only a couple of cases to consider. The complexity of this process is $O(n^3)$ as it spends linear time on each substring of $s$.

If $DP[i][j]$ is the answer for a substring $[i..j]$, the complete recurrence is as follows:

$$DP[i][j] = \min \{DP[i][k] + F(i,k,j) \cdot DP[k+1][j] : i \leq k < j \}.$$

where

$$
F(i,k,j) = \left\{ \begin{array}{ll}
1 & \textrm{for $s[i] = s[k+1]$ and $DP[i][k] = 1$}\\
1 - DP[i][k] \mod 2 & \textrm{for $s[i] = s[k+1]$ and $DP[i][k] > 1$}\\
DP[i][k] \mod 2 & \textrm{otherwise}
\end{array} \right.
$$

what corresponds to the fact that in some cases $y'$ can be erased using $x'$ (possibly in multiple moves) - in those cases $F(i,k,j)$ is $0$, and it's $1$ otherwise. Also note, that if $s[i] = s[i+1]$ then when dealing with $DP[i][j]$ for $j > i$ at first we initialize $DP[i][j] = DP[i+1][j]$.

For me, the assumption that $t$ can be split into $x$ and $y$ in a such a way that the mentioned procedure is optimal, is non-trivial. I'm asking for a proof that this assumption can be made, or some different solutions for this problem, either would be nice.


texts: I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.


texts: Find a minimum-cost pair of arc-disjoint paths, both within a given restricted distance

texts:
Is there a polynomial algorithm that can find a pair of arc-disjoint paths in a directed graph that has a minimum total cost, subject to the condition that both paths are within the same distance.

Given a distance $D$, and a graph $G(V,A)$, where $V$ is a set of nodes, $A$ is a set of directed links (or arcs). Each link has two additive metrics, namely, a cost (binary, $0$ or $1$) and a distance (positive integer). For a source-destination pair $(s,t)$, find a set of two paths P1 and P2, where $P_1$ and $P_2$ are arc-disjoint and path distance $L(P_1)\le D$, $L(P_2)\le D$, such that the total cost is minimized. Note that the distance and the cost of a path is the sum of the length and the cost of the links it traverses, respectively.

I knew that when the cost of each arc is integer or real, it is an NP-Complete problem, see GCSDP($k$). I do not know whether it is still NP-complete when the cost of each arc is limited to $\{0,1\}$. Anyway, I want to know if there is a polynomial solution for it.


texts: Why TurnAround Time is considered as Performance Metric for Scheduling Algorithms?

texts: I know what is turn around time but i am confused why wating time is not considred as Performance Metric for Scheduling Algorithms Since it gives the time for which a Process will wait till it gets Scheduled...This can also be Performance Metric


texts: half precision floating point multiplication

texts:
A = 0   10011   0011110111

B = 1   00011   0010011000

exponent is 15, mantissa is 10 bits and first bit is implicit. Can somebody please tell me the final answer cause I am having trouble figuring out what is happening with exponent since there are 3 extra zeroes in front of mantissa multiplication. I got that exponent is 7(00111 in binary). Thanks in advance


texts: Algorithm for seeing if there exists a min s-t cut (A,B) in a flow network with node u in A and node v in B

texts:
We are given a flow network and two nodes $u$ and $v$. We want to create an algorithm that tells us whether or not there is a minimum s-t cut so that $u$ belongs to the same side of the cut as the source node $s$ and $v$ belongs to the same side of the cut as the sink node $t$.
My initial idea was to run Ford-Fulkerson to get the residual graph $G_f$ at the end. Then use that to find all nodes reachable from $s$ in $G_f$ (call this set $A$) then $B=V-A$ where $V$ is the vertex set. Then $(A,B)$ is a min s-t cut and if $u \in A, v \in B$ output true, else false.
But since there may be more than one min cut I'm a bit stuck.


texts: Integer programming for the courier (goods delivery) scheduling problem

texts:
Model: Consider an undirected, weighted, complete graph $G = (V, E = V \times V, w: E \to \mathbb{N}^{+}, r: V \to \mathbb{N}^{+}, d: V \to \mathbb{N}^{+})$.  $s \in V$ is a source vertex.
$G$ describes a transportation network, where $V$ represents places, $E$ represents roads connecting them, $w(e)$ represents the time it takes to travel along $e$.

Imagine that a courier, initially standing at $s$, needs to deliver goods to all the other places. The consignee at place $v \in V$ ($v \neq s$) has specified a release time $r(v)$ and a deadline $d(v)$; the good for this place can only be signed for during the period $[r(v), d(v)]$. Assume that the time for sign is negligible.

The courier is free to stay at any place for an arbitrarily long time. However, it costs $c$ dollars for each time unit wasted in this way. Notice that in some scenarios, the courier has to "waste" some time to finish its job. See the example below.

Problem: Suppose the time is initially $0$ and it starts ticking immediately when the courier leaves $s$. The last good is delivered at time $T$. The goal of the task is to deliver goods to all the places (other than $s$) while minimizing $T + c \cdot (\text{units of all the wasted time})$.

An example: Consider the graph shown in the figure below.
The solution $s \to^{4} a \to^{1} a \text{ (delivering)} \to^{1} b \text{ (delivering)}$ takes $6$ time units, of which $1$ time unit is wasted, so the value of the objective function is $6 + c$.
Another solution $s \to^{2} b \to^{1} b \text{ (delivering)} \to^{1} a \to^{1} a \text{ (delivering)}$ takes $5$ time units, of which $2$ time units are wasted, so the value of the objective function is $5 + 2c$.

Want Help: I am trying to solve this problem by using Integer Programming. But I don't know how to start and I have identified some challenges to me:

Each edge can be travelled along more than once. Thus, the binary decision variables $x_{ij}$, denoting for each edge $e_{ij}$ that whether it is travelled or not, are not sufficient.
How to describe a walk using variables?
How to accumulate the time units took until some step in the walk?
How to express and accumulate the wasted "stay" time?

Note:

The solution is not restricted to Integer programming.
This is a cross-post from math.se which does not receive answers in more than 20 days.
About two months ago, I had a similar (maybe simpler; with less constraints) problem which was proved NP-hard by @Dennis Kraft (see also the comment from @G. Bach). That is why I am trying Integer programming, approximate algorithms, or heuristic methods.


texts: Understanding NFA (nondeterministic finite automaton) with a null transition

texts:
I'm reading Computer Science: An Interdisciplinary Approach. It mentioned an NFA (nondeterministic finite automaton) with a null transition, as shown above, recognizes all binary strings that do not contain bba as a substring.

I didn't quite understand why it says so. If the null transition happens before reading the bba, it stuck at state 2 and will report yes at the end?