texts: Maximise the value of the minimum weight intra edge

texts:
I've been doing review problems for a midterm and I came across this one
problem that I haven't been able to solve. The problem essentially says
that given a complete graph $G=(V,E)$ partition the vertices into
two subsets $A$ and $B$ such that weight of the smallest intra edge
(i.e. an edge $e=(u,v)$ such that $u$ and $v$ belong to the same subset)
is maximized. The graph has $n$ vertices and $k$ weighted edges.
The edges with no weight can be assumed to have infinite weight. The
required runtime is $O((n+k) \log k)$.
I thought of this in two ways:

Arrange the edge weights in increasing order and for every edge
$(u,v)$, place $u$ and $v$ in different subsets.

Arrange the edge weights in decreasing order and for every edge
$(u,v)$, place $u$ and $v$ in the same subset until all the vertices
have been placed in some subset.

The second approach doesn't work because there could be a smaller edge
among two vertices in the same subset.
Could someone please help me with this?


texts: Shortest-Path for Weighted Directed Bipartite Graphs

texts:
I did a research project in which I seek to move a car through zones from origin to destination. This allows for the formulation of a bipartite graph because only adjacent zones can be connected. Each edge has a non-negative weight of time. I look to find the shortest path between source and sink, given the weights and directions of the edges. The structure of the graph is quite simple, all adjacent zones are connected. The bipartite graph looks this this.

My question is what is the best shortest-path algorithm for such a graph?


texts: Is the dynamic programming pairwise alignment algorithm considered greedy?

texts:
I'm a freshman in Computer Science and I'm studying bioinformatics sequence alignment algorithms.
My understanding of a greedy algorithm is one that takes the best decision for a particular instance in order to find a general best decision. By that definition, would the basic dynamic programming pairwise alignment algorithm be considered greedy?


texts:
Show that NP is closed under concatenation.

This is a homework problem and I would appreciate some guidance. I began by saying the following:

Let $A$ and $B$ exist in NP. Let $V_1$ and $V_2$ be verifiers for $A$ and $B$, respectively.

Is it as simple as saying build two NTMs $M_1$ and $M_2$ that decide $A$ and $B$ and then concatenate them and build a new machine to decide?


texts: Designing context free grammar for a language with range restriction on repetition of alphabets

texts:
I am having issue with designing contex free grammar for the following language:

$L = \{0^n 1^m \, | \, 2n \leq m \leq 3n \}$

I can design for the individual cases i.e. for $m \geq 2n$ and $m \leq 3n$ but don't know how should i combine both. Or is it a different approach altogether?


texts: Given two sequences of the same size, how many longest common subsequences can they have?

texts:
For simplicity assume that both have the same size N.

the lengh of this subsequence can be at most N, so maybe it's

max(C(N,1), C(N,2), ... , C(N,N))?


texts: Best algorithm for sequencing reducible control flow graph

texts:
I have a reducible control flow graph with only natural loops, produced from a simple DSL. Every node keeps a list of successors and a list of predecessors. I need to make a sequence of nodes out of this CFG with following properties:

All predecessors of a block are located before this block, with the exception of backward edges of loops. This implies that all dominators of a block are located before this block.
All blocks that are part of the same loop are contiguous, i.e., there is no non-loop block between two loop blocks.

What would be the most efficient algorithm to produce such a sequence?

For illustration consider following CFG (left) with desired output (right).

CFG has been produced from a DSL which is roughly equivalent to pseudocode:

    for(; a && b; c++) {
        if (d) {
          dostuff1();
        } else {
          dostuff2();
        }
        dostuff3();
    }
    dostuff4();

Here is also CFG itself in python:

from collections import defaultdict

class Node:
    def __init__(self, id, name):
        self.id = id
        self.name = name
        self.succ = []

class Graph:
    def __init__(self):
        self.graph = defaultdict(Node)

    def addNode(self, node):
        self.graph[node.id] = node

    def addEdge(self, uid, vid):
        self.graph[uid].succ.append(self.graph[vid])

g = Graph()

g.addNode(Node(0, "Entry"))
g.addNode(Node(1, "For-Loop-Entry"))
g.addNode(Node(2, "Logical-And-Left"))
g.addNode(Node(3, "Logical-And-Right"))
g.addNode(Node(4, "For-Loop-Test"))
g.addNode(Node(5, "If"))
g.addNode(Node(6, "If-Consequent"))
g.addNode(Node(7, "If-Alternative"))
g.addNode(Node(8, "For-Loop-Body"))
g.addNode(Node(9, "For-Loop-Update"))
g.addNode(Node(10, "Body"))
g.addNode(Node(11, "Exit"))

g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(2, 4)
g.addEdge(3, 4)
g.addEdge(4, 5)
g.addEdge(4, 6)
g.addEdge(6, 7)
g.addEdge(6, 8)
g.addEdge(7, 9)
g.addEdge(8, 9)
g.addEdge(9, 10)
g.addEdge(10, 1)
g.addEdge(5, 11)


texts: Why k- Vertex Cover is not in PTIME when it can be expressed in FO-logic

texts:
We can express property that graph has vertex cover of size at most k with first order formula:

$$\exists x_1 \exists x_2...\exists x_k (\forall y \forall z (E(z,y) \ \rightarrow \ \bigvee_{1 \leq i \leq k} y=x_i \ \vee \ \bigvee_{1 \leq i \leq k} z=x_i))$$

But, there is also theorem (proven for example in Libkin's book Finite model theory) that for every given FO sentence and finite model A one can decide does:

$$A \models \varphi$$

in PTIME.

Why can't we use this for sentence expressing k-VC property, written above, and decide does any given graph has this property?


texts: How is the modular multiplication matrix unitary in Shor's Algorithm?

texts:
I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as

$$C U_{a^{2}}(|c\rangle|y\rangle)=|c\rangle\left|\left(a^{2^{i}}\right)^{c} y \bmod N\right\rangle$$
in this paper.

It's described similarly here

The issue I have is this does not seem to be unitary, since $N<2^n$, we can get stuff like this:

$$C U_{a^{2}}(|c\rangle|0\rangle)=C U_{a^{2}}(|c\rangle|N\rangle)=|c\rangle\left| 0\right\rangle$$

I don't understand how modular multiplication can possible be inversible when we explicitly choose $N < 2^n$, and so there have to be values the mod to the same result.


texts: Given an oriented graph, return true if paths have a specified length

texts:
I'm having trouble solving this exercise about graphs, I hope you can help me:

Given a graph $G = (V,E)$, two sets of vertices $A \subseteq V$ and $B \subseteq V$ (represented as arrays), and an integer $k$, verify in $O(|V|+|E|)$ if each path that starts from a vertex $v \in A$ and connect a vertex $u \in B$ have a length that is greater or equal than $k$.

So if each vertex in $A$ that connect a vertex in $B$ have a length that is greater or equat to $k$, you should return $true$; otherwise, if exists at least one vertex of $A$ that connect a vertex in $B$ on a path that have a length that is less than $k$, you should return $false$.

My problem is to guarantee the linearity on the graph's dimension. My idea was to execute $|A|$ BFSs, one for each node that is contained in $A$. But, if $|A|=|V|$ i have a complexity that's squared on the graph's dimension.

Thank you very much.

New Update : I've tried to think about the Dijkstra algorithm; in that algorithm i have one source and i have to calculate the shortest path from the source and other nodes. Still it's easy if i have one source, but if i have a set of nodes, still cannot guarantee the linearity. Please, do you have more specific hint?


texts: A scheduling problem on an oriented graph with multiple constraints

texts:
The problem is the following :

Data

An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks
A map $d: V -> \mathbb{N}$ : to be understood a function mapping tasks to a discretized duration.
a couple $(p_0, p_1) \in \mathbb{N} \times \mathbb{N}$ : to be understood as an authorized time frame.
$(w_{max_1}, w_{max_2}) \in \mathbb{N} \times \mathbb{N}$ : to be understood as a maximum wait times between tasks inside a list (definition follows) and between the realisation of same task in each list.

Definition 1 : List

We call a list (to be understood as an instanciation of all the tasks)  the following map $L : V \rightarrow [\![p_0; p_1]\!]$ such as

$\forall t \in V, L(t) + d(t) \leq p_1$
$\forall t \in V, L(t) \geq p_0$
those two are the time frame conditions (the second one is obviously redondant with the target set of the function by here to clarify)
$\forall (t_1, t_2) \in V$ such that $L(t_1) < L(t_2)$ then $L(t_1) + d(t_1) \leq L(t_2)$
This condition means that no two tasks of a list can overlap
$\forall (t_1, t_2) \in E, L(t_1) < L(t_2)$
This condition means that some tasks must happen in a definite position
For $t_1 \in V$ let $w = \displaystyle \min_{t_2, L(t_1) < L(t_2)}(L(t_2) - (L(t_1) + d(t_1))$ then $w \leq w_{max_1}$
This condition means that the delay between the end of a task and the begin of the next one must be inferior to a known duration.

Definition 2: Compatible lists

Two lists $L_1$ and $L_2$ are said to be compatible iff :

$\forall t \in V$:

$L_1(t) < L_2(t) \implies L_1(t) + d(t) \leq L_2(t)$
$L_2(t) < L_1(t) \implies L_2(t) + d(t) \leq L_1(t)$

To be understood as two lists are compatible if the same task in those two lists does not happen in an overlapping time frame.

Definition 3: Correct set of lists

Let $X = \{L_i\}$ be an ensemble of compatible lists and $n = |X|$, we say that X is a correct set of lists iff :

For $L_i \in X$, $\forall t \in V$, let $w' = \displaystyle \min_{j, L_i(t) < L_j(t), L_j \in X}(L_j(t) - (L_i(t) + d(t))$ then $w' \leq w_{max_2}$

This condition on an ensemble of lists is to be understood as : the delay between the end of an occurence of a task in a list and of the begining of the same task in another list must be inferior to a know duration.

Goal

Maximize n

This is to be understood as : pack as many lists as possible inside a time frame as long as they define a correct set (def 3) of compatible (def 2) lists (def 1).

Questions

My questions are the following :

Do you see any incoherence (or improvement in the formulation) between the maths and the text ?
What kind of known problem is this (if this one, i'm guessing some variant of job-scheduling) ?
If this is not a known problem what simplification can be made to reach one ?
If pertinent, what are the method to solve this (or the simplification of this) ? I know an optimal solution might not be achievable but something approaching might be and I'm guessing constraint programming might be something to look at.


texts:
Syntax and semantics section of this paper on probabilistic programming mentions that the return expression of the program is a function f satisfying  $
f : \sum \rightarrow \mathbb{R}^{\inf}_{\geqslant0}$ where $\sum$ is the set of states. I do no not see the need of $\geqslant0$. Why can't the return values be negative?


texts: What is a dichotomy? Whether 2-SAT itself is a dichotomy of SAT?

texts:
Recently, I am reading papers about dichotomy. I do not understant what condition can be called as a dichotomy? What is the meaning of "a question is either in P or in NP-complete"? (assume P $\neq$ NP)

For example, I've known the Schaefer's dichotomy theorem, in which a dichotomy about "whether a class of SAT is in P" is given. In this theorem, the dichotomy contains six conditions, one of them is "2-SAT".

So my question is that, whether "2-SAT" itself can be called as a dichotomy or a trivial dichotomy, because 2-SAT is in P but 3-SAT is NP-complete? In another words, I wonder that "if a special class of an NP-complete problem is in P, then this class is a dichotomy? or a trivial dichotomy?"


texts: An algorithm for getting the position index

texts:
Consider these two equation.

$$
m_1+m_2+m_3+m_4 = M_m\\
|m_1|+|m_2|+|m_3|+|m_4| = N_m
$$

where $\{m_i,M_m,N_m\}\in \mathbb{Z}$.

Given the value of $(N_m,M_m)$ we can find the different solutions for $(m_1,m_2,m_3,m_4)$. The solutions are ordered in a particular way which is best explained by giving a few examples.

For e.g. with $(N_m = 2 ,M_m = 2)$ the solutions are

{{0, 0, 0, 2}, {0, 0, 1, 1}, {0, 0, 2, 0}, {0, 1, 0, 1}, {0, 1, 1, 0}, {0, 2, 0, 0}, {1, 0, 0, 1}, {1, 0, 1, 0}, {1, 1, 0, 0}, {2, 0, 0, 0}}

For e.g. with $(N_m = 2 ,M_m = -2)$ the solutions are

{{0, 0, 0, -2}, {0, 0, -2, 0}, {0, 0, -1, -1}, {0, -2, 0, 0}, {0, -1, 0, -1}, {0, -1, -1, 0}, {-2, 0, 0, 0}, {-1, 0, 0, -1}, {-1, 0, -1,  0}, {-1, -1, 0, 0}}

For e.g. with $(N_m = 3 ,M_m = -1)$ the solutions are

{{0, 0, 1, -2}, {0, 1, 0, -2}, {1, 0, 0, -2}, {0, 0, -2, 1}, {0, 1, -2, 0}, {1, 0, -2, 0}, {0, 1, -1, -1}, {1, 0, -1, -1}, {0, -2, 0,1}, {0, -2, 1, 0}, {1, -2, 0, 0}, {0, -1, 1, -1}, {1, -1, 0, -1}, {0, -1, -1, 1}, {1, -1, -1, 0}, {-2, 0, 0, 1}, {-2, 0, 1, 0}, {-2, 1, 0, 0}, {-1, 0, 1, -1}, {-1, 1, 0, -1}, {-1, 0, -1,  1}, {-1, 1, -1, 0}, {-1, -1, 0, 1}, {-1, -1, 1, 0}}

Now what I would like is to find an efficient algorithm that can
returns the position for a given set of $(m_1,m_2,m_3,m_4)$.

So for e.g given $\{m_1,m_2,m_3,m_4\} = \{0, 0, 1, 1\}$ the algorithm should return the number 2 since the solutions is in the second position (see e.g. 1 above).

Likewise

$\{0, 0, -1, -1\}$ returns 3

$\{-1, -1, 1, 0\}$ returns 24.

Note that I don't want to generate all the solutions for finding the position.
I have shown the solution just to show the ordering specially for negative input.

Any suggestion would be appreciated. Thanks

This question was initially asked at mathematica.stackexchange.

Here is the link to that question


texts: Can terms "interpreter" and "processor" be used interchangably?

texts:
I do not ask you to respect that the processor is a physical black box whereas interpreter implementation is not that clear. As CS, you must look at the functionality aspect -- both processor (physical machine?) and interpreter (virtual machine?) execute a program (a stream of commands).

Isn't to interpret the code just means to evaluate/to execute/to process it?

There is a long article on interpretation in Wikipedia. It uses a lot of words to explain what is interpretation and it even says that it is execution of instruction stream. But nobody stood up and stated that it is just what the processor does (like the child in the "Emperor new clothes")! Why should we think that these are two different things? Processors even invented JIT-compilation (called microcoding) earlier than virtual machines.

Also, bytecode interpretation should give additional clue. It looks like machine code absolutely (to be executed by virtual machines). So, are interpreters just virtual processors?

The self-checking questions are:

What if vendor of your favorite processor discloses you a terrible secret that your instructions are not executed directly but converted into a true machine language beneath, before submitted to the real processor, is you language interpreted or machine?
What if instruction stream for a real processor is executed by emulator (virtual machine) then is it executed by the processor or interpreted?
Can the processor that executes an interpreted language (bytecode or script) is not a processor anymore but an interpreter?


texts: Why is set of Turing machine set DD = {⟨M⟩ | ⟨M⟩⟨M⟩ not in L(M)} not decidable?

texts:
To prove that the set $\mathrm{DIAG} = \{\langle M\rangle \mid \langle M\rangle \notin L(M)\}$ is not decidable, we can assume, to the contrary, that there is a Turing Machine $M$ such that $L(M) = \mathrm{DIAG}$. Consider the string $\langle M\rangle$. By definition of $\mathrm{DIAG}$, $\langle M\rangle \in \mathrm{DIAG} \Leftrightarrow \langle M\rangle \notin L(M)$. But since $L(M) = \mathrm{DIAG}, \langle M\rangle \notin L(M) \Leftrightarrow \langle M\rangle \notin \mathrm{DIAG}$. So $\langle M\rangle \in \mathrm{DIAG} \Leftrightarrow \langle M\rangle \notin \mathrm{DIAG}$, which is impossible.

I don't know how to extend this proof to prove that $DD = \{\langle M\rangle \mid \langle M\rangle\langle M\rangle \notin L(M)\}$ is not decidable. Can someone show how to do this?


texts: Clarifying statements involving asymptotic notations in soln of $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$ using recursion tree and substitution

texts:
Below is a problem worked out in the Introduction to Algorithms by Cormen et. al.
(I am not having problem with the proof but only I want to clarify the meaning conveyed by few statements in the text while solving the recurrence and the statements are given as ordered list at the end. Simply because I want to master the text.)

$$T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$$

Now the authors attempt to first find a good guess of the recurrence relation using the recursion tree method and for that they allow sloppiness and assumes $T(n)=3T(n/4) + cn^2$.

Though the above recursion tree is not quite required for my question but I felt like including it to make the background a bit clearer.
The guessed candidate is $T(n)=O(n^2)$. Then the authors proof the same using the substitution method.

In fact, if $O(n^2)$ is indeed an upper bound for the recurrence (as we shall verify in a moment), then it must be a tight bound. Why? The ﬁrst recursive call contributes a cost of $\Theta(n^2)$ , and so $\Omega(n^2)$ must be a lower bound for the recurrence. Now we can use the substitution method to verify that our guess was correct, that is, $T(n)=O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$ We want to show that $T(n)\leq d n^2$ for some constant $d > 0$.

Now there are a few things which I want to get clarified...
(1) if $O(n^2)$ is indeed an upper bound for the recurrence. Here the sentence means (probably) $\exists$ a function $f(n) \in O(n^2)$ such that $T(n)\in O(f(n))$
(2) $\Omega(n^2)$ must be a lower bound for the recurrence Here the sentence means probably $\exists$ a function $f(n) \in \Omega(n^2)$ such that $T(n)\in \Omega(f(n))$
(3) $T(n)=O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$ This sentence can be interpreted as follows assume that $T'(n) = 3T'(\lfloor n/4 \rfloor) + cn^2$ and $\exists$ a function $T(n) \in O(n^2)$ such that $T'(n)\in O(T(n))$
(4) $T(n)\leq d n^2$ for some constant $d > 0$ We are using induction to verify to the definition of Big Oh...
I feel that the author could simply have written the $T(n)$ is Upper Bounded by $n^2$ and Lower Bounded by $n^2$ or the author could have simply written $T(n) = O(n^2)$ and $T(n)=\Omega(n^2)$, did the author just use the above style of statements as pointed out in $(1),(2),(3)$ just for more clearer explanation or there are some extra meaning conveyed which I am missing out.


texts: 0 error interpolation for discrete finite value points

texts:
I am working on an algorithm that requires me to interpolate a couple trillion positive discrete points with f(x) having low finite value (for example 0 - 5). It there a specialized algorithm specific for this reduced problem that can provide 0 error interpolation?
Could you maybe point me to a few papers?

EDIT: I noticed that i can make the trillions of points become less, but then the max value of f(x) rises exponentially (if i cut them by half, the max value gets squared). If i can get for example 4 points and interpolate with a 3rd degree function, is it guaranteed to pass through all points?


texts: How can a polynomial such as $x^3 + 1$ be converted to its binary form of $1001$. Likewise, $10100001 = x^7 + x^5 + 1.$


texts: Will the Ford-Fulkerson method return any value if the residual network is ignored?

texts:
The normal Ford-Fulkerson method finds augmenting paths (as long as one exists) while including "back-flows", but if those back-flows are ignored, does there exist a flow network for which algorithm will not terminate? Assume integer capacities for each edge.

Edit: I learned that even if the back-flows are ignored, with each iteration of the algorithm, we need to show that the capacity of at least one edge will decrease. If this is the case, then when continuously iterating through and finding paths within the network, we will eventually get to a point where all edges become "filled" in the worst case. When this happens, the algorithm must terminate.


texts:
I'm reading the paper "Dual of substitution is Redecoration".
And I'm struggling with understanding the usage of the word "not-well-founded cotrees".

what is a cotree compared to a tree ? I suspect it is a tree for which all relations are inverted, but it is just my assumption.
what it is to be "well-founded" for a tree, for a cotree.

Probably, to have an insight, it would be helpful to give me examples of a well-founded and of a not-well-founded tree/cotree.


texts:
Here is insertion sort:

for i = 1 to length(A)
    x = A[i]
    j = i - 1
    while j >= 0 and A[j] > x
        A[j+1] = A[j]
        j = j-1
    end while
    A[j+1] = x
end for

My lecture notes say that the total number of basic computation steps is about

$$T = 1 + ( 5 + t_1 \times 3 ) + \dots + ( 5 + t_{n-1} \times 3 )\,,$$

where $t_i$ represents how many times the inner loop needs to run (anything between $0$ and $i$). $5$ for the basic operations in the outer loop, and $1$ for testing whether to enter the outer loop.

I understand the "1" and the "5" but not the "3". Because I think $t_i$ is not always anything between $0$ and $i$? Like say a number needs to move from position $5$ to position $1$, it repeats the inner loop meaning there will be more steps? The steps in the inner loop can possibly repeat for $n-1$ times?

So what is the basic computation steps?


texts: Why do logic gates behave the way they do?

texts:
I am a Software Developer but I came from a non-CS background so maybe it is a wrong question to ask, but I do not get why logic gates/boolean logic behave the way they do.

Why for example:

1 AND 1 = 1  // true AND true
1 OR 0 = 1   // true OR False
0 AND 1 = 0  // false AND true

And so on..
Is it a conditional definition for example, like it is like that by definition?
Or there is a logical/intuitive explanation for these results?

I have searched google, also looked at the Wiki page of logic gates for an explanation of 'why' but I can only find 'how'.
I would appreciate any answer or resources.


texts: Term for programming languages that read like sentences?

texts:
Is there a term for programming languages that read like written sentences? I'm thinking of languages like Python, where you can almost read the code aloud as a sentence, as opposed to C++ which is really arcane.

For example, in Python if 'pizza' not in animals is very clear when read aloud.

Seems like maybe there's a formal term for this?


texts:
I'm trying to write a context-free grammar (to be feeded to lark) for parsing lambda calculus expressions. Basic version of it, as presented by most sources, looks like:

expr: variable | "(" expr ")" | application | abstraction
abstraction: "λ" variable "." expr
application: expr expr

I'd like the grammar to unambiguously parse expressions taking advantage of the notational conventions mentioned here on Wikipedia.
While I'm able to modify the grammar to follow most of them, I got stuck with implementing this one: "The body of an abstraction extends as far right as possible".

For example, there are two parse trees for λx.x λa.a - it can be both an application of two abstractions ( (λx.x)(λa.a) ) or an abstraction with an application in its body ( λx.(x(λa.a)) ).
If the abstraction was greedy as it should be, only the second one would be correct.

Is it possible to write a grammar that would force (i.e., make it the only choice) greedy interpretation of abstractions? If so, how to do it?


texts:
So, I was watching a video about the conversion of $\epsilon$-NFA to a DFA. In the resulted DFA, she didn't write the state 4 in any successor set of the sets containing the state 3, and her explanation was that this happens because the state 3 has no outgoing transitions that are labeled with letters from $\Sigma$ in the input NFA. See the following image.

So my question is, if the state 3 had an outgoing transition labeled with 0 in the input NFA (see the 2nd image below), then does the state 3 contribute the states 2,4,5, and 6 in the successor set upon reading the letter 0?


texts: What is cyclomatic complexity and how relevant it is today?

texts:
I have read that cyclomatic complexity is widely used, but critique on it exists
claimed that it is based on poor theoretical foundations and an
inadequate model of software development.

I have read here page 10, second para


texts: Why is the inverted index called so and not simply index?

texts:
In my notes is represented like this:

From wikipedia:

In computer science, an inverted index (also referred to as a postings
file or inverted file) is a database index storing a mapping from
content, such as words or numbers, to its locations in a table, or in
a document or a set of documents.

Where is the inversion with respect to a normal index (like the one found at the end of books)?

Index: (in a book or set of books) an alphabetical list of names,
subjects, etc. with reference to the pages on which they are
mentioned.

Am I missing something? Like a nuance of the meaning of the name due to the fact that english is not my main language.


texts: Understanding a detail in the proof of bin packing approximation

texts:
Input: $n$ item with sizes $s_1,...,s_n$, without lose of generality, all sizes are $\leq1$.  In addition, $s_i < \delta$ for all $i$ for some constant $\delta$.
Output: Minimal numbers of bins to pack the items, where each bin has volume 1.

The scheme used is first-fit, where if the current used bins are indexed, we insert the $i_{th}$ item to bin with the lowest index it fits into. Therefore, we open a new bin only when we can't fit an item into any bin.

Denote by $OPT$ the minimal number of required bins (for some input), and by $FF$ the number of bins output by first-fit scheme, the claim is that:

$$FF \leq OPT(1+2 \delta)+1$$
The proof is divided into cases, one when $\delta\geq {1 \over 2}$
, and the second where $\delta< {1 \over 2}$.
My problem is in the later case.
In class we were shown that when the algorithm (that uses first-fit scheme) ends running, there are at least $FF-1$ bins, such that their empty space is $<\delta$. (which I understand why)
Here a
link
to the final configuration of the algorithm to make things more clear.

Then the professor claimed that: $(FF-1)(1 - \delta) \leq OPT$.
Why is that?


texts: Defining computable functions on arbitrary sets

texts:
Turing machines take inputs that are strings of symbols from some alphabet, and they give outputs that are strings of symbols from the same alphabet. To show that a function is computable, we have to exhibit a Turing machine that computes it. In the case where the function is not from strings to strings, something about this bothers me.
I will introduce the problem with a simple example. Suppose that I define a function from binary trees to binary trees, and I want to show, formally, that it's computable. To do that I would have to exhibit a Turing machine that computes it. Since binary trees are not strings, I first have to design a string representation of binary trees. For example, I could represent the tree

as ((*,*),(*)). Having done this, I can then pass binary trees to Turing machines in string form, and get trees back in string form, no problem.
But here's my problem: the representation of binary trees as strings is itself a function (in fact a bijection) from binary trees to strings. How can I know formally that this function is a computable one?
On an intuitive level I have no problem seeing that it is, but on a formal level I can't exhibit a Turing machine to verify it, because then I would need a string representation of binary trees, and we quickly get into an infinite regress. For simple things like binary trees the computability of the representation is obvious, but for more complicated sets it might not be.
Can this circle be squared --- is there a formal definition of computability for functions of arbitrary countable sets that might not admit an obvious mapping to strings of symbols?
Additional thoughts
Here is another way of explaining my question: we might choose to define a model of computation that operates inherently on trees or some other set rather than strings. Indeed, many such models of computation have been proposed, including the lambda calculus and combinator calculi (which are arguably more naturally seen as operating on trees rather than strings), the recursive functions (which operate on integers), and various cellular automata (which operate on infinite strings or two dimensional lattice configurations, rather than finite strings). It's only really historical accident that led the string-based Turing machines to become the gold standard against which other models of computation are judged.
The problem is that without being able to talk about computable mappings between these sets, it's not strictly formally possible to say whether these other models of computation are equivalent to Turing machines or not. While it usually doesn't raise any practical problems to just think of everything in terms of string representations, it seems dissatisfying that our theory of computation doesn't treat all models of computation equally, but instead privileges those whose input and output are from a particular kind of set.
So really my question is whether a theory of computation exists has been formulated that is model-agnostic, in precisely this sense of not privileging one particular kind of set for input and output. It's quite an abstract question, motivated more by a desire for formal niceness than by any practical concerns.
One suspects, for example, that the category theorists might have done some work in this direction. This is because category theory tends to talk about the properties of functions without talking much about the sets they map, so a "category of computable functions" would probably not know or care whether its underling objects were sets of strings or something else. This is an approach I would be particularly keen to read about if it exists. (I've asked another question, specifically about the category theory aspect, over at MathOverflow.)


texts: Maximizing a spanning tree in an undirected graph with double weighted edges

texts: I would like to have help in developing the algorithm for this problem.


texts: Finding simple path on grid graphs of length $l$

texts:
Let $G$ be a grid graph. We are given two vertices $s$ and $t$, and an integer $l$. The goal is to check if there exists a simple path from $s$ to $t$ of length $l$.
Brute force algorithm will give $n^l$ time algorithm as I will simply enumerate all the paths of length $l$. Are there faster algorithms for this problem?
My observation is grid graphs are bipartite graphs so all paths will be either of odd length or even length but I don't know how to use this fact. Note that in grid graphs the degree is bounded by four so from any vertice to any other vertex, number of paths of length $l$ are bounded by $4^l$. I am looking for an algorithm faster than $4^l$.


texts: Showing that Karger's contraction algorithm has exponentially small probability of finding an optimum

texts:
I'm stuck with one of my homework exercises:

Consider the following variant of Karger’s algorithm for finding a minimum s-t cut, i.e., a minimum cut separating two specific given nodes s and t:
As in the original algorithm, edges are iteratively contracted. In any iteration, let s and t denote the possibly contracted nodes that contain the original nodes s and t, respectively. To ensure that s and t do not get contracted, at each iteration any edges connecting s and t are deleted, and a random edge to contract is selected from the remaining edges.
Give an example showing that the probability that this method finds a minimum s-t cut can be exponentially small.

I know how Karger's algorithm works, but I'm not sure why the probability is exponentially small and how can I show that by giving an example.
Any hint would be helpful.


texts:
My intuition tells me that there is <=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from len_ = lps[len_- 1] .
def computeLPSArray(pat, M, lps):
    len_ = 0 # length of the previous longest prefix suffix

    lps[0] = 0 # lps[0] is always 0
    i = 1

    # the loop calculates lps[i] for i = 1 to M-1

    while i < M:
        if pat[i]== pat[len_]:
            len_ += 1
            lps[i] = len_
            i += 1
        else:
            # This is tricky. Consider the example.
            # AAACAAAA and i = 7. The idea is similar
            # to search step.
            if len_ != 0:
                len_ = lps[len_- 1]

                # Also, note that we do not increment i here
            else:
                lps[i] = 0
                i += 1

```


texts: Prove that every CFL has at least one infinite equivalence class

texts: If we define the Myhill-Nerode relation on a CFL how can i prove that there is at least one infinite equivalence class?


texts: Can someone explain why there are two summations here?

texts:
The following quote is from the book "The art of computer programming":

  (..) sentence  would presumably be used only if either $j$ or $k$ (not both) has exterior significance.

  In most cases we will use notation (2) only when the sum is finite - that is, when only a finite number of values $j$ satisfy $R(j)$ and have $a_j \neq 0$. If an infinite sum is required, for example
  $$\sum_{j=1}^{\infty} = \sum_{j \geq 1}a_j = a_1 + a_2 + a_3+\cdots$$
  with infinitely many nonzero terms, the techniques of calculus must be employed; the precise meaning of (2) is then
  $$\qquad\qquad \sum_{R(j)} a_j = \left(\lim_{n\rightarrow\infty} \sum_{R(j) \atop 0\leq j \leq n} a_j\right) + \left(\lim_{n\rightarrow\infty} \sum_{R(j) \atop 0\leq j \leq n} a_j\right),\qquad\qquad(3)$$

  (...)

And why are they exactly the same? I showed a math professor and he thinks they're labelled wrong but couldn't figure it out. I don't even get why there are two.

Sorry if the question isn't clear enough. I'm referring to the two infinite sums. As far as (2) is concerned he is only referring to what is on the left hand side of the equation with the two infinite sums. Its just a way of representing any possible series. So essentially my question is how does making any series go to infinity make two of them? Or am I misunderstanding?

Also I tried to post this in math stack exchange and it wouldn't let me so I came here since its from the book, the art of computer programming.


texts: Context-free and context-sensitive grammars in FSM with counters

texts:
Consider an extension of finite-state machines that utilizes a finite set $C$ of counters. Let's call them counter automata. Before execution, each counter $c\in C$ is set to zero. Every transition, aside from reading a character (possibly $\epsilon$), performs a counter operation – it either increments or decrements some counter $c$ by one ($c{+}{+}$ and $c{-}{-}$, respectively). Decrementation of a counter is forbidden if the counter is set to zero. Acceptation is done by accepting states, regardless of counter values.
Alphabet is of finite size.

Is every context-free language accepted by a counter automaton?
Is every language accepted by counter automata a context-sensitive one?

Please note that counter automata differ from counter machines (at least I can't prove that they're equal). The counters mustn't go below zero and there's basically only JUMP NOT ZERO operation available, aside from INCREMENT and DECREMENT.

I think that we can simulate a finite stack using a finite number of counters. We'd remember both the top and the bottom of the stack in states, and counter values would represent symbols on stack. Unfortunately, this stack would have fixed size. I don't know how to continue.


texts:
I need help with the following mock exam questions. True or false?

1.) If a non-trivial $(\neq \emptyset, \Sigma^*)$ finite set is NP-complete, then $P = NP$.

True. Every finite set is in $P$ and because of the $NP$-completeness every set in $NP$ can be reduced to this set. Is it right?

2.) $NP \subseteq coNP$ $\Leftrightarrow$ $NP = coNP$.

I don't know if the "$\Rightarrow$" case holds. I only know $P \subseteq coNP$ and $P \subseteq NP$.

3.) For every fixed $k$ the problem $k$-$CLIQUE$ can be modeled as a Constraint Satisfaction Problem.

I have no idea. We've had $3$-$COLOR$ and $3$-$SAT$ as examples but also the fact that not every NP-problem can be expressed in terms of a CSP.

Thanks in advance!


texts: RSA Encryption for specitic messages x with x = ap mod pq for ap-bq=1

texts:
I want to make a following proof but I got some difficulties with it.
Would be super if you people have any tips / advises.
Introduction:
Let (N,e) be our public key and (N,s) our private key with $N=pq$ and $ggT(\varphi(n),e)=1$, as well as $es\equiv 1\mod N$.
I want to show that since Lemma of Bézout shows, that there are $a,b\in \mathbb{N}$ so that $ap-bq=1$, the message of $x=ap\mod N$ is equal to the encrypted message $y=x^e \mod N$.
My Plan:
I started by using the Chinese remainder theorem. To show $x\overset{!}{=}y=x^e\mod N$ we need to show, that $x\overset{!}{=}x^e\mod p$ and $x\overset{!}{=}x^e\mod q$. I could also use the Chinese remainder theorem on $x=ap\mod N$.
So I need to show, that $ap \mod p=(ap)^e\mod p$. Since ap is a multiple of p, it should be $ap\equiv 0\mod p$ and so $(ap)^e=0\mod p$. It follows that $ap\mod p=(ap)^e\mod = p= 0 \mod p$.
I now need to show, that $ap\mod q=(ap)^e\mod q$. This is the part I am struggling with. I know that $ap-bq=1$ but I have no glue how this is going to help me. I was thinking about something like $ap=(bq+1)\mod q$ but i am not sure if this works / what to do next.


texts:
Let G be the grammar:

S --> ASB | λ

A --> aAb | λ

B --> bBa | ba

Use set notation to define L(G).

So I came across two different answers to this question, none of which are mine, and then compared them to mine. I'm wondering if they are all equivalent.

Answer 1: $L(G) = \{a^{n_1}b^{n_1}...a^{n_k}b^{n_k}b^{m_1}a^{m_1}...b^{m_l}a^{m_l} | n_i, m_j > 0, l \ge 0, k \ge 0, k \le l\}$

Answer 2: $L(G) = \{(a^{n}b^{n})^i(b^{m}a^{m})^i |  n \ge 0, m > 0, i \ge 0\}$

My answer: $L(G) = \{(a^{n}b^{n})^k(b^{m}a^{m})^l |  n, k, l \ge 0, m > 0\}$

My answer seems similar to the second one. Are all three of these correct for this grammar?


texts: Is there a fast solution for this set reduction problem?

texts:
Let there be a set $S$ and denote by $P=2^S$ the power set of $S$. We are given a finite subset $L = \{p_0, \ldots, p_{n-1}\}$ of $P$ and we are allowed to transform the set as follows: if two sets $p_i$ and $p_j$ share some elements, i.e. $p_i \cap p_j \neq \emptyset$, remove both $p_i$ and $p_j$ from $L$ but add their union $p_i \cup p_j$ to $L$.

What is the algorithmically fastest way to reach a state where there is no further (or almost no further) transformation of $L$ possible?

One simple way to achieve that goal is to compare all elements with each other and perform a transformation if possible, repeat until no changes are possible.

Pseudo C++-code using std::vector:

vector<Set> L = ...;
int n = L.size();

bool hasChanged = true;
while (hasChanged) {
    hasChanged = false;

    for(int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (!isDisjoint(L[i], L[j])) {
                // remove L[i] and L[j]
                swap(L.back(), L[i]);
                L.pop_back();
                swap(L.back(), L[j]);
                L.pop_back();

                // add their union
                L.push_back(getUnion(L[i], L[j]));

                hasChanged = true;
                i -= 1; // we don't want to skip the swapped element
                break;
            }
        }
    }
}

This algorithm takes $\frac{n^2-n}{2}$ comparisions in the best case and $\sum_{k=1}^n \frac{k^2-k}{2}$ comparions in the worst case. Naturally the number of comparisons needed depends on the ordering of the elements in the vector.

To provide some less abstract context: I have a set of line segments which i want to reduce. So the idea is to connect lines which are "close" to each other. A connected line does not necessarily share start or endpoints with its original lines but it can be connected to other lines in the set. How do I connect all the lines until there is no further improvement possible in the fastest way possible?


texts: What if there is a polynomial-time algorithm to minimize NFA?

texts: Knowing that NFA-minimization has been proven to be P-SPACE complete, what if there is a polynomial-time algorithm to minimize NFA? Does that imply that P = PSPACE?


texts: How to generate random adjacency matrix with given number of components in graph

texts:
I am building a graph package in C and a part of the work involves generating a random graph with a given number of components in the graph.

For example, if I wanted to generate a graph of 50 vertices and 5 components, then the module will take 50 and 5 as parameters and should be able to generate an adjacency matrix of the graph(for the time being I am implementing it using adjacency matrix only).
I have an idea that I can generate cliques of a different number of vertices and the number of cliques is exactly equal to the number of components. Then I can merge all the adjacency matrices corresponding to cliques to form the adjacency matrix of the graph.

Implementing this in C seems to be quite complicated, and I feel this is not an optimal solution as the graph will be dense every time and I can not achieve a sparse graph using this approach. Is there anything I am missing?


texts: Sorting "almost sorted" array in $O(n\log\log n)$

texts:
Given array $A$ of length $n$, we call it almost sorted if there are at most $\log n$ indices satisfying $A[i] > A[i+1]$.
Find an algorithm that sorts the array in $O(n\log\log n)$.

My attempt:

Create an array $B$ of size $\log n + 1$.
Go through the array $A$, recognize the $\log n$ pairs, and insert them into $B$.
Sort $B$ using insertion sort in time $O(\log^2 n)$.

At this point I am stuck.


texts:
Let us assume that we have two algorithms, $A$ and $B$. Based on 3 different values of a parameter, $P$, $A$ takes $a_1, a_2, a_3$ seconds and $B$ takes $b_1, b_2, b_3$ seconds. What would be a proper way to measure which algorithm is more sensitive to $P$?

To address a diverse community, I will give an analogy: let us assume that depending on whether it rains heavily (value 2), mildly (1) or none(0) at all, one crop growing procedure $A$ takes $a_1, a_2, a_3$ time and another one, $B$, takes $b_1, b_2, b_3$ time. What would be a suitable statistical methodology to determine which procedure is more dependent on ("sensitive to") raining? We can also assume that:

We are growing same crops with $A$ and $B$ on the same kind of field.
$a_i$, $b_i$ can vary over different execution and the execution times for $A$ and $B$ are reported in terms of averages and standard deviation. $a_i$, $b_i$-s' can be averages (for each $i$-th value of $P$) or just a single execution time (for the $i$th value of $P$).

I am interested in measuring the "sensitivity" of the algorithm when the variance in the execution time of an algorithm is reported in either relative ("execution time of A increased by 5%") or absolute scale ("execution time of A increased by 5 sec") or  both.

The exact problem I am working with is to compare the execution time of two distributed graph algorithms and decide which algorithm is more sensitive to underlying runtime parameters.


texts:
I am faced with the following problem;

We are provided cost quotations for shipping cost per packet by various shipping companies, let's call these quotations $Q_1 ... Q_k$.
Each Quotation is a $M \times N$ matrix with weights categories of packets along one axis and size categories along the other axis.
We are provided with a list of packets as well with respective weights and sizes such that we can convert the packages to be shipped into a 2d matrix of size $M \times N$ as well based on categorization of each packet and each cell shall contain the relevant number of packets in that weight+size category. Let's call this matrix $P$.

The total shipping cost for all the packets should we chose a shipping company '$i$' is sum of ( $Q_i \times P$ ) where '$\times$' is the element-wise multiplication of the two matrices.

We are required to find a subset of size '$w$' shipping companies (or quotations) such that the overall shipping cost is minimum.

I understand that a brute force algorithm trying out all combinations is not going to work due to the explosion of the number of combinations as '$w$' starts to increase. Moreover, I have also convinced myself that I can not iteratively build out a solution by first selecting two best quotations, merging them into one and then continue to add one more till I reach '$w$'.

Can someone help me find the relevant class of problems and suggest a solution?


texts: Under what kind of oracles are $P$ and $NP$ equivalent?

texts:
How strong have the oracles needed to be for these two classes to be proven equivalent with respect to them?

For instance: is $P^H$ = $NP^H$ (ie. is $P$ equipped with an oracle to solve the halting problem equivalent to $NP$ equipped with an oracle to solve the halting problem)?

From Theodore Baker, John Gill, and Robert Solovay. Relativization of the P=?NP problem. Siam Journal of Computing, 4:432-442, 1975 [219] we know $NP^A =P^A$ for their oracle A (which is a decision algorithm for a PSPACE complete problem).

If the oracle can perform an infinite amount of computation and return back the result in one step are these classes equal with respect to an oracle of this type? How about weaker ones? What is the weakest oracle we know of where $P$ and $NP$ are equal with respect to it?

An answer I'm looking for is something like: $P^O$=$NP^O$ with respect to an oracle O and any oracle more powerful than it.


texts: Total distance between points on a grid with time complexity lower than $O(n^2)$

texts:
I have $n$ points that form a grid with empty space and I need to find an algorithm that would calculate the total distance of those points with time complexity lower than $O(n^2)$.

An example of a grid with $n=5$ would be the following set of points:
$(1,0)$, $(0,1)$, $(2,0)$, $(2,1)$, $(2,2)$. As you can see their $x$ and $y $ coordinates can only have values from set $\{ 0, 1, 2\}$. (Thought usually n is very big $\approx 10^6$ )

In CS I would represent the grid as a matrix:

$$
        \begin{matrix}
        0 & 0 & 1 \\
        1 & 0 & 1 \\
        0 & 1 & 1 \\
        \end{matrix}
$$

In order to calculate the TOTAL distance between points I follow the procedure:

the distance for point $(1,3)$ is:
$1+\sqrt{5}+2+\sqrt{5}=3+2\sqrt{5}$

the distance for point $(2,1)$ is:
$2+\sqrt{2}+\sqrt{5}$

the distance for point $(2,3)$ is:
$\sqrt{2}+1$

the distance for point $(3,2)$ is:
$1$

the distance for point $(3,3)$ is:
$0$

So the total distance is: $7+2\sqrt{2}+3\sqrt{5}$

This approach simply calculates separately the distance and then adds it up which doesn't take into account the fact that they are positions in layers.

This doesn't look like a super unique issue - is there any existing algorithm for this or does anyone have an idea how to speed this up?

EDIT:
By Total Distance I mean a situation like this:
I pick a point and then calculate the distance between the picked point and the rest $n-1$ points. Then I choose the next point and I calculate it's distance betwenn it and the rest $n-2$ points, and so on. I then sum up all the distances to get the total.

I fixed the calculations.


texts: Pumping Lemma: Is language with equal number of "aa" and "bb" regular?

texts:
Given alphabet $\Sigma=\{a,b\}$, is the language
$$L = \{ w \mid w\text{ contains an equal number of substrings }aa\text{ and }bb \}$$
regular?
 My initial though was no, because the language $L' = \{a^nb^n\mid n\ge0\}$, is not regular, and is of the same general form as $L$. However, I am confused about how $aa$ and $bb$ being substrings affects the proof, via pumping lemma. Is it proper to select a "specific" $s$ for the pumping lemma, such as

$$s = a^p(aa)^pb^p(bb)^p\,?$$

Is there a better $s$ I could choose? In general, how would I pick an $s$ when I am dealing with a language written based upon substrings, like $L$?


texts: Proving a sorting operation in type system

texts:
I want to know how far a type system in a programming language can be beneficial. For example, I know that in a dependently typed programming language, we can create a Vector class incorporating size of the vector in the type signature. It is like a de-facto example. We can also write a function append using those signatures so that compiler proves resulting list's size will be the sum of the input lists.

Is there a way to encode, for example, in a sorting algorithm's type signature so that compiler guarantees resulting list to be a permutation of the input list? How this can be done, if it is possible?


texts: How to understand the mathematical constraint of potentials?

texts:
Good evening!
I am studying scheduling problems and I have some difficulties understanding constraints of potentials:

Let be $t_j$ the time when a task $j$ starts, and $t_i$ the time when a task $i$ starts. I'm assuming that $a_{ij}$ is the length of the task $i$ but I'm not sure. Why is a "constraint of potential"  mathematically expressed by:

$$t_j-t_i \le a_{ij}$$

Shouldn't it be the reverse, $t_j-t_i \ge a_{ij}$? If we know that the length of task $i$ is $a_{ij}$, isn't it impossible to do something in less that the necessary allocated time?


texts: $6$ Voronoi-sites without breakpoints in Fortune's Algorithm

texts:
This example is based on Fortune's algorithm.
Given $6$ Voronoi-sites, construct an example where the sweep-line already handled the $6$ points but without any Voronoi-points. Also, $3$ points or more cannot be collineair and $4$ points or more cannot form a circle
The only way I can make it to work is to put $6$ points in a circle or $6$ points collineair as you can see below. How else is this possible to make?
Note: There can be breakpoints that the sweep-line did not handle yet. (So 'behind' the sweep-line)

Below you can find a counterexample.


texts: How exactly does a two stack pushdown automaton work?

texts:
I have to explain how a 2-PDA works and then write a program (in Delphi) which simulates a 2-PDA step by step for the language $L = \{w\$w\ |\ w ∈ \{0,1\}^n\ with\ n>0\}$. So far, so good.

Now I know that a 2-PDA works with two stacks and is equivalent to a Turing Machine. It reads from an input tape and can save the current digit in either the first or the second stack. How can I decide in which stack the digit is read and/or saved? Especially since it's a computer program that should deal with that step.

Since it's equivalent to a Turing Machine, I get that one stack can deal with the left side and the other with the right side of the input. However, this is not really enough information for me to write a programm that simulates it. So how does the 2-PDA read the word, for instance, 01001$01001 from language $L$. Where does it begin? How does it accept the word?

I know, so many questions, I don't want to have them answered all in much detail but the most important thing is just how it works.


texts:
I am learning automata theory, and I am confused about this exercise:

Give context free grammar to create the following language where the
input  alphabet is $\{a,b\}$
$L = \{w \text{ where }w\text{ is NOT of the form }b^n a^n\}$

So, I understand how to create $\{b^n a^n, n\in\mathbb{N}\}$:

$$S \to bSa \mid \epsilon$$

But I am lost as to how to generate a language that is $\{w \text{ where }w\text{ is NOT of the form }b^n a^n\}$.
Help would be appreciated.


texts: Denotational semantics of expressions with side effects

texts:
I'm doing revision for a module on programming language semantics and
I'm having trouble understanding the introduction of side-effects in
expressions.

We assume a standard syntax for arithmetic expression, with the four
usual operations, plus the unary prefix and postfix operator
$\texttt{++}$, defined as in language C, applicable to variables only
as in $\texttt{V++}$, and assigment statement $\texttt{V:=E}$.

We have seen how to define the denotation function
$[\![\texttt{E}]\!]_{\mathrm{Exp}}$ when we have to evaluate an
expression $\texttt{E}$ without side-effect, to return a value
resulting from that evaluation.

In order to give a denotational semantics for expressions with side-effects, we need to change the type of the denotation function $[\![\texttt{E}]\!]_{\mathrm{Exp}}$ for expressions $\texttt{E}$, so that it returns both the value of the expression and the state as modified by the side-effects. I.e., we want to define a denotation function

$[\![\texttt{E}]\!]_{\mathrm{Exp}} : State → Int×State$

by induction on the form of expressions $\texttt{E}$. For example, in the case $\texttt{E}$ has the form $\texttt{E1+E2}$, we define:

$[\![\texttt{E1+E2}]\!]_{\mathrm{Exp}}(S) = (n_1 + n_2, S_2)$

where $(n_1, S_1) = [\![\texttt{E1}]\!]_{\mathrm{Exp}}(S)$

and $(n_2, S_2) = [\![\texttt{E2}]\!]_{\mathrm{Exp}}(S_1)$

This says first evaluate the leftmost expression $\texttt{E1}$, giving the integer value $n_1$ and updated state $S_1$, then evaluate $\texttt{E2}$ in that updated state, giving the integer value $n_2$ and updated state $S_2$; the value of the expression is $n_1 + n_2$, and evaluation has the side effect of updating the state to $S_2$.

However this does not show when side effects actually take place, and I do not know how to write the denotation function for expressions that do produce side-effects. Can you tell me how to complete the inductive definition of $[\![\texttt{E}]\!]_{\mathrm{Exp}}$, including the case where $\texttt{E}$ is of the form  $\texttt{V++}$?

Then, how should one change
 the definition of
 the denotation function $[\![\texttt{V:=E}]\!]_{\mathrm{Pgm}}$ for the assignment statement, to take account of the changes in the definition of $[\![\texttt{E}]\!]_{\mathrm{Exp}}$, which it necessarily uses?

Are there other changes that would need to be made to the denotational semantics of the language?


texts: How does this algorithm calculate the fractional part of a binary logarithm?

texts:
I'm trying to understand a binary logarithm function written by somebody else:
function log_2 (int128 x) internal pure returns (int128) {
    require (x > 0);

    int256 msb = 0;
    int256 xc = x;
    if (xc >= 0x10000000000000000) { xc >>= 64; msb += 64; }
    if (xc >= 0x100000000) { xc >>= 32; msb += 32; }
    if (xc >= 0x10000) { xc >>= 16; msb += 16; }
    if (xc >= 0x100) { xc >>= 8; msb += 8; }
    if (xc >= 0x10) { xc >>= 4; msb += 4; }
    if (xc >= 0x4) { xc >>= 2; msb += 2; }
    if (xc >= 0x2) msb += 1;  // No need to shift xc anymore

    int256 result = msb - 64 << 64;
    uint256 ux = uint256 (x) << uint256 (127 - msb);
    for (int256 bit = 0x8000000000000000; bit > 0; bit >>= 1) {
      ux *= ux;
      uint256 b = ux >> 255;
      ux >>= 127 + b;
      result += bit * int256 (b);
    }

    return int128 (result);
}

The code is written in Solidity, although that doesn't matter much for my question.
As far as I can tell, the function is split into two main parts:

Apply the find first one algorithm to determine the integer part of the binary logarithm (msb = most significant bit?).
Calculate the fractional part and add it to the integer part. This is where I lost track.

It seems to me that the second part makes use of the iterative approximation algorithm, but I'm not sure. What does the second part do, specifically?
For context, both x and result are presumed to be 64.64 bit numbers. A signed 64.64-bit fixed point number is a simple fraction whose numerator is a signed 128-bit integer and the denominator is 2^64.


texts: Karp hardness of an equidistant set in digraph

texts:
Following the success of the undirected version:

Karp hardness of an equidistant vertex set

Inspired by the success of this long ago question:

NP-hardness of problem with indices and subsets

We move on asking for the hardness of the directed version of an equidistant set.

  Input: A directed graph $G(V, A)$ and a natural number $k$

  Output: YES if $G$ has an equidistant vertex set of size $k$, otherwise NO

In this problem, we disallow opposite arcs like $(u,v)$ and $(v,u)$ to be both present in the arc set, i.e. either one of them or none.

$\DeclareMathOperator{\dist}{dist}$An equidistant vertex set is a set of vertices $V'\subseteq V$ such that for every two ordered pairs of vertices $u, v\in V'$ and $w, s\in V'$, we have $\dist(u, v) = \dist(w, s)$, where $\dist(u, v)$ is the length of a shortest path between $u$, $v$. Note that in digraph, it is possible that $dist(u,v)\neq dist(v,u)$.


texts: Is valid the notion of infinity for the NP-complete problems?

texts:
We have defined two complexity classes which have a close relation with the notion of infinity.

The first one is:

We say that a language $L$ belongs to $UP_{\infty}$ if there exist an infinite sequence of languages $L_{1}, L_{2}, L_{3} \ldots$ where for each $i \in \mathbb{N}$ every language $L_{i}$ is in $UP$, has an infinite cardinality, the set $L_{i + 1} – L_{i}$ has infinite elements and $L_{i} \subset L_{i + 1}$ such that
$\lim_{i \rightarrow \infty} L_{i} = L.$
We call the complexity class $UP_{\infty}$ as $\textit{“infinite–UP”}$.

The second one:

We say that a language $L$ belongs to $P_{\infty}$ if there exist an infinite sequence of languages $L_{1}, L_{2}, L_{3} \ldots$ where for each $i \in \mathbb{N}$ every language $L_{i}$ is in $P$, has an infinite cardinality, the set $L_{i + 1} – L_{i}$ has infinite elements and $L_{i} \subset L_{i + 1}$ such that
$\lim_{i \rightarrow \infty} L_{i} = L.$
We call the complexity class $P_{\infty}$ as $\textit{“infinite–P”}$.

We have the result:

We define a problem that we call General Quadratic Congruences. We show General Quadratic Congruences is an $\textit{NP–complete}$ problem. Moreover, we prove General Quadratic Congruences is also in $\textit{infinite–UP}$. In addition, we define another problem that we call Simple Subset Product. We show Simple Subset Product is an $\textit{NP–complete}$ problem. Furthermore, we prove Simple Subset Product is also in $\textit{infinite–P}$.

These problems are defined as follows:

$\textit{GENERAL QUADRATIC CONGRUENCES}$

INSTANCE: Positive integers $a$, $b$, $c$ and $d$, such that we have the prime factorization of $b$.

QUESTION: Is there a positive integer $x$ such that $x < c$ and $d \times x^{2} \equiv a (\mod b)$?

We denote this problem as $GQC$.

$\textit{SIMPLE SUBSET PRODUCT}$

INSTANCE: A list of numbers $L$ and a positive integer $k$ with its prime factorization, such that the prime factorization of $k$ does not contain any prime power with exponent greater than $1$.

QUESTION: Is there a subset of numbers from $L$ whose product is $k$?

We denote this problem as $SSP$.

MY QUESTION IS:

Can these properties of the NP-complete problems help us to understand better the P versus NP problem?

Let me know your answer, please…

At the same time, if you want to see the details take a look in:

https://hal.archives-ouvertes.fr/hal-01490777v2/document

Thanks in advance…


texts: Efficiently listing all last-level descendants of each root in a proper hierarchical graph (bipartite DAG)

texts:
Let G = (V, E) be a graph which is hierarchical in the sense that its vertices are arranged in levels/layers (say 1 to k) and an edge can only be from a vertex at level i to a vertex at level i+1. Vertices at level 1 and k are called the roots and the leaves, respectively. The problem is to find all descendant leaves of each root.
For instance, for the following graph,

the answer would be:
1: 12, 13
2: 12, 13
3: 12, 13, 14, 15, 16
4: 14, 15, 16

A naive solution can be to run a DFS for each root which will take O(r(n+m)) time where r is #roots, n is #vertices and m is #edges.

Can we do better?
Another way to see the same graph is that it is a bipartite DAG.


texts: How to find the original coordinates of a point inside an irregular rectangle?

texts:
I'm a third year computer science student. I'm working on a project Data-show touch screen In schools classrooms.
I'll try to explain my problem as much as I can.
The project has three main components; A computer, a Data-show and a webcam.
The teacher will plug the data-show in the computer and the computer screen will appear on the wall of the classroom to all students.
The main purpose of the project is to turn the image of the screen displayed on the classroom wall into interactive screen; when the teacher tabs with his finger on an image of a Button displayed on the wall, the webcam that is connected to the computer will capture the position of the teacher's finger and find his (x,y) coordinates for a reference point on the wall, and raise a click event in the related (x,y) position on the screen.
The screen of the computer has two dimensions; Width->X and Height->Y. And for every point in the screen such as P, it could be located on the screen using two numbers (Px,Py), where Px is the distance between the point P and the left side of the screen, and Py is the distance between the point P and the top side of the screen. In other words, the reference for all points in the screen is the top left corner of the screen.

The data-show will display an irregular Quadrilateral shape of the screen on the wall. the shapes will not be regular squares or rectangles due to the angle that the teacher puts the data-show in. What I'm asking for are the equations that will calculate the (x,y) point on the screen that represents the (x,y) tapped point on the wall.
There is mainly four shapes the data-show may display on the wall. For each shape of them the only known things are the coordinates of the four angles(corners) of the quadrilateral shape.
1. an optimal rectangle
The displayed image on wall has a very low chance to shape an optimal rectangle, but it's the basic shape that could be formed.

Suppose that the red point P'(Px',Py') represents the coordinates of the place the teacher tapped on with his finger.
To get the original (Px,Py) coordinates from the point (Px',Py') on the wall, I can do the following.

Calculate the width->X' and the height->Y' of the displayed image by the law of distance between two points.

find the ratio between X&X', and between Y&Y'. I'll call the first ratio rx and the second ratio ry.

Multiply Px' by rx to get Px, and multiply Py' by ry to get Py.

2. an optimal trapezoidal.

The displayed image on wall could also shape an optimal trapezoidal. I asked some of my friends from the applied mathematics college to help me to find the two equations to find the original coordinates of the point, and they did some calculations and came out with these two equations;
In this shape

To find X:

and to find Y I can use the same way used in the rectangle; finding the ratio between Y and the height of the trapezoidal H.

3. an irregular quadrilateral.
My question is about this shape, the data-show in most times will shape an irregular shape. Imagine this shape like

None of the shape's lines is vertical or horizontal, all lines may have different lengths and they may have different angels from each other.
My question is
I'm searching for equations that will find the original P(x,y) point of the point P'(X',Y'). Things I know are the coordinates of the points P1, P2, P3, P4, P'
What are those equations? and how are they derived?


texts: Correctness of following algorithm for 3-QCNF?

texts:
Let I have 3-QCNF formula.

Classic recursive algorithm for TQBF takes exponential time. However, following divide & conquer modification allows to do it in quadratic time (not sure about correctness, and that's the question).

ctr = 0

for i = 0..n

    Step 1. Take i'th clause, find E-quantified variable inside it.
    If can't, return 'NO'. Otherwise, if it's the clause containing 3
    variables, choose that variable v.

    Step 2. Find all 3-clauses with variable v. Move them from formula Ф
    to formula f_i. Reduce n (length of formula Ф) by number of moved
    clauses.

    Step 3. Copy f_i to f'_i.

    Step 4. Put v = 1 in f_i. Get 2-QCNF.

    Step 5. Put v = 0 in f'_i. Get 2-QCNF.

    Step 6. If f_i and f'_i have same clauses, move them to Ф.
    Increase n by number of moved clauses.

    Step 7. ctr = ctr + 1

for i = 0..ctr

    Step 1. Solve 2-QCNF Ф'^f_i. //Ф' is changed Ф.

    Step 2. Solve 2-QCNF Ф'^f'_i.

    Step 3. If both are false, return 'NO'.

return 'YES'

Notes:

Algorithm represents 3-QCNF as $\mathsf{\Phi = TAUT-CNF \land \Phi'(2-QCNF) \land (f_i(2-QCNF) \lor f'_i(2-QCNF))\land\ ..}$

Trivially, formula is false if TAUT-CNF contains clauses.

So, if TAUT-CNF has no clauses, formula is represented this way:

$\mathsf{\Phi' \land (f_i \lor f'_i)\land\ ...\ =((\Phi'\land f_i)\lor(\Phi'\land f'_i))\land\ ...}$

The question: have I violated any logical rule in my algorithm?


texts:
Prove that $L\in NC^1$ iff there exists a sequence of poly sized formulas that decides $L$.

I managed to prove the $(\impliedby)$ and I want to prove $(\implies)$.

I feel that we need to take the boolean circuit and duplicate the sub-circuits of $fan-out\gt 1$ into exact circuits but with $fan-out = 1$. I fail to argue why the resulting tree is of polynomial size and not of exponential one.


texts: Do all languages in $P$ have polynomial proofs that they are in $P$?

texts:
A proof for a language $L$ belonging to a complexity class $C$ can be framed as there existing a verifier $V$ that accepts this proof as the first part of their input and the language as the second. The verifier verifies this language is a member (a word) in the language representing the complexity class.

Verifier: (Proof for $L$ in $C$, $L$)$\longrightarrow$[0,1]

Do all languages in $P$ have a proof of the fact that they are in $P$ that can be verified in polynomial time? Given a language, determining if an arbitrary $L$ is in $P$ is undecidable; however, given a proof for a language in $P$, can that language be verified to be in $P$ in polynomial time?


texts: CFG to generate $L = \{a^{2n}b^n\} \bigcup \{a^mb^{2m}\}$

texts:
I've been struggling to find the grammar to generate the language

$$L = \{a^{2n}b^n : n \text{ is natural}\} \cup \{a^mb^{2m} : m \text{ is natural}\}.$$

I've considered

$$S \to aS|Sb|ab,$$

which works in some cases, but not all (we can derive $a^{k}b$ for example).

What considerations am I not taking into account? There first is the requirement that in a degenerate case we generate $abb$ or $aab$, and there's the consideration that we need to double the number of respective symbols each time.

A promising alternative seems to be

$$S \to aSb|a|b,$$

which balances the left and right sides such that one is always greater than the other by one, but not by a factor of two.


texts: Does the state of a cell in cellular automata has to be from a finite set?

texts: In most (all I have seen) work on cellular automata, the state of a cell is from a finite set. Such as a cell can take value from a binary set, or from among few colors. Can we define the state to be something more complicated such as a function of the coordinates of the neighbor cells? (assuming there is a initial coordinate value give to at least one cell) So for example in 2-D if my neighbor to the left has coordinate $(x,y)$ my state will take a value $f(x,y)$ where $f$ is same for all cells.


texts: Can one determinize finite automata over infinite trees?

texts:
I'm currently considering deterministic, nondeterministic, universal, and alternating automata over infinite words and trees, with Büchi, co-Büchi, Muller, Rabin, Streett, or parity acceptance conditions.

I know that over words, all these automata accept the same languages, except deterministic and universal Büchi automata, as well as deterministic and nondeterministic co-Büchi automata.

I also know that over trees, nondeterministic and alternating Muller, Rabin, Streett, and parity automata accept the same languages, and strictly more languages than nondeterministic and alternating Büchi automata.

But I hardly know anything about deterministic tree automata, and I'm having a hard time finding more in the literature. And this captures my main question, whether one can determinize nondeterministic automata over infinite trees.

After all, they are definitely used. For example, in reactive LTL synthesis, we often convert the formula to a nondeterministic Büchi word automaton, then to a deterministic parity word automaton, from which we derive a deterministic parity tree automaton.

Also note that I didn't mention the co-Büchi case when it comes to trees. I just know that, again in reactive LTL synthesis, we can alternatively convert the negated formula to a nondeterministic Büchi word automaton, then to a universal co-Büchi word automaton for the original formula, from which we can derive a universal co-Büchi tree automaton. But that alone doesn't really say anything about the relation of deterministic parity tree automata and universal co-Büchi tree automata, or does it?


texts: AI approach for exploring a static grid environment

texts:
I have a grid environment which contains in each cell a static agent. When my agent enters a cell, the static agent in this cell might take points away from me, give me points, or do nothing. My agent can not observe adjacent cells until it moves into one them, it can only move up, down, left or right.

This agent can not learn whilst it is exploring. It enters the grid from a particular corner, and may only leave from that corner. If the agent manages to successfully explore the environment and return back to the corner with positive health, then it can learn from its collected experience, which includes the (row, column) positions it visited, and the properties of the static agents located in those positions. If the agents' health drops to zero whilst exploring, game over. But I can restart the exploration as many times as I want.

Each static agent has one of three shapes, one of three colours, and one of two sizes. It also has an associated "reward", indicating how many points it adds/removes from me.

Each move in this environment costs me one point. I want to design an agent that correctly recognises the reward associated with each type of static agent in this grid.

Please may someone recommend a learning and/or evolutionary approach to solving this problem? I'm stuck at the moment because of the restriction that agent may not observe adjacent squares. I'm not sure how I can learn anything from this testing environment from the (row, column) and static agent properties encountered alone.


texts: How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?

texts:
Intersection of CFL and regular is always CFL. But according to Chomsky hierarchy diagram, regular languages lie completely inside CFL.  So, as regular set is completely inside CFL set, their intersection should be regular right ?

Am I interpreting Chomsky diagram wrongly ?


texts: What is the simplification of AB + BC + (~B)C?

texts:
AB + C is not the answer.
The correct answer is AB + BC.  HOW?


texts:
There's a class of data structures where you preprocess some other data structure in order to answer queries about it more efficiently.

That includes trivial things like sorting/hashing, less trivial things like quad trees, and includes far less trivial things such as dominator trees, interval decompositions of DAGs or distributed data structures using labelings.

I was wondering what is a common term for such data structures, and if there isn't, how to describe them best. "index-like" comes to mind, but there aren't yet any tags with the word "index" here so it does not seem to be common.


texts:
In order to select questions for an online contest, we get contributors to submit potential questions that they write themselves. Then, out of, say 100 submitted questions, we have to rate them and select the best ones, say about 30. Suppose we have 4-5 people willing to help on the final selection task. No one has time to go though all 100 proposals, but can give a grade to a subset (say, 30-35).

We can assume those raters are internally consistent (i.e., will always give the same rate to the same question) but not with each other (e.g., there may be a systematic bias between two raters).

What algorithms are there to help assign questions to raters and them try to estimate and adjust the biais so as to obtain a maximally consistent global rating without anyone having to read all the questions?


texts: Not satisfiable 3SAT instance implications

texts:
Suppose we have an instance of 3SAT that is NOT satisfiable and we say $S$.
If in $S$ there are the following $8$ clauses
$\left(a\vee b\vee c\right)\wedge\left(a\vee\bar{b}\vee c\right)\wedge\left(a\vee b\vee\bar{c}\right)\wedge\left(a\vee\bar{b}\vee\bar{c}\right)\wedge\left(\bar{a}\vee b\vee c\right)\wedge\left(\bar{a}\vee\bar{b}\vee c\right)\wedge\left(\bar{a}\vee b\vee\bar{c}\right)\wedge\left(\bar{a}\vee\bar{b}\vee\bar{c}\right)$
we have that anyway we set the Boolean value of the variables $a,b,c$, there is a clause that is false.
If in $S$ instead of $a \vee \bar{b} \vee \bar{c}$ we have
$\left(a\vee e\vee f\right)\wedge\left(a\vee\bar{e}\vee f\right)\wedge\left(a\vee e\vee\bar{f}\right)\wedge\left(a\vee\bar{e}\vee\bar{f}\right)$
this implies that anyway we set the Boolean value of the variables $a,b,c,e,f$, there is a clause that is false.
In the first case, we have
$\left(a\vee b\vee c\right)\wedge\left(a\vee b\vee\bar{c}\right)\Rightarrow \left(a\vee b\right)$
$\left(a\vee \bar{b}\vee c\right)\wedge\left(a\vee \bar{b}\vee\bar{c}\right)\Rightarrow \left(a\vee \bar{b}\right)$
$\left(\bar{a}\vee b\vee c\right)\wedge\left(\bar{a}\vee b\vee\bar{c}\right)\Rightarrow \left(\bar{a}\vee b\right)$
$\left(\bar{a}\vee \bar{b}\vee c\right)\wedge\left(\bar{a}\vee \bar{b}\vee\bar{c}\right)\Rightarrow \left(\bar{a}\vee \bar{b}\right)$
and
$\left(a\vee b\right)\wedge\left(a\vee \bar{b}\right)\wedge\left(\bar{a}\vee b\right)\wedge\left(\bar{a}\vee \bar{b}\right)$
is NOT satisfiable.
In the second case, we have
$\left(a\vee e\vee f\right)\wedge\left(a\vee \bar{e}\vee f\right)\Rightarrow \left(a\vee f\right)$
$\left(a\vee e\vee \bar{f}\right)\wedge\left(a\vee \bar{e}\vee\bar{f}\right)\Rightarrow \left(a\vee \bar{f}\right)$
and
$\left(a\vee f\right)\wedge\left(a\vee \bar{f}\right)\Rightarrow a$
and
$a\Rightarrow\left(b\vee c\right)\wedge\left(\bar{b}\vee c\right)\wedge\left(b\vee\bar{c}\right)\wedge\left(\bar{b}\vee\bar{c}\right)$
and this last conjunction is NOT satisfiable.
The question is: given a NOT satisfiable 3SAT instance, if we apply all possible implications and make the conjunction of the right side of the implications, we get a 2SAT instance (the right side of these impliacations is either the conjunction of two variables or a singol variable); is this 2SAT instance not satisfiable? If it isn't, can you give me an example?


texts:
Please consider the following triple-nested loop:

for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
        for (int k = j; k <= n; ++k)
            // statement

The statement here is executed exactly $n(n+1)(n+2)\over6$ times. Could someone please explain how this formula was obtained? Thank you.


texts: What are all the differences between the Gibbs phenomenon artefects and JPEG artefacts?

texts:
I thought the Gibbs phenomenom is the result of Fourier analysis estimation (but was it Fourier Series estimation or can it also be Fourier Transform estimation?)

JPEG uses the Discrete cosines Transform. A DCT is similar to a Fourier transform in the sense that it produces a kind of spatial frequency spectrum.

But what are the differences between the Gibbs phenomenom artefacts from Fourier and the artefacts from the Discrete Cosine?


texts: Correctness of the Betweenness centrality formula

texts:
Betweenness centrality is defined as the number of shortest paths that go through a node in the graph.The formula is:
$$\sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$$
Where $\sigma_{st}$ is the total number of shortest paths from node $s$ to node $t$ and $\sigma _{st}(v)$ is the number of those paths that pass through $v$.

However it doesn't seem to me that the formula calculates what is defined. Why do we divide by the total number of shortest paths between $s$ and $t$ each time? Shouldn't we just divide by $2$ to compensate the fact that  $s$ and $t$ will appear twice in different orders?


texts:
Let $A$ be a matrix of size $K \times N$, $K \leq N$. Let $n_1...n_K$ denote a $K$-permutation of integers $1...N$ (understood as a unique assignment of a column to every row in the matrix). How to most efficiently calculate the sum, over all $K$-permutations, of products $A[1,n_1] * A[2,n_2] * ... * A[k,n_K]$?
For example, let $K=3$ and $N=5$. One possible K-permutation is (5, 1, 3), and the corresponding product is $A[1,5] * A[2,1] * A[3,3]$. But what must be calculated is the sum of such products over all K-permutations, e.g.:
$$
A[1,1] * A[2,2] * A[3,3] + \\
A[1,1] * A[2,2] * A[3,4] + \\
A[1,1] * A[2,2] * A[3,5] + \\
A[1,1] * A[2,3] * A[3,4] + \\
A[1,1] * A[2,3] * A[3,5] + \\
A[1,1] * A[2,4] * A[3,5] + \\
...
$$
I am not even sure there is an efficient (polynomial time) solution, the most I have been able to come up with has about $2^M$ complexity which is unacceptable.


texts: Is $Ω(n\log n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?

texts:
Is $Ω(n\log n)$ the lower-bound for all sorting algorithms or just comparison-based sorting algorithms?

If the latter, is it possible for there to be general-purpose sorting algorithms which perform better than $Ω(n\log n)$?

General-purpose, for example, means you aren't assuming elements have a fixed number of bits.

The input to the algorithm is a sequence of $n$ bits.  The bits are an encoding of integers.


texts: Measuring the difficulty of SAT instances

texts:
Given an instance of SAT, I would like to be able to estimate how difficult it will be to solve the instance.
One way is to run existing solvers, but that kind of defeats the purpose of estimating difficulty. A second way might be looking a the ratio of clauses to variables, as is done for phase transitions in random-SAT, but I am sure better methods exist.
Given an instance of SAT, are there some fast heuristics to measure the difficulty? The only condition is that these heuristics be faster than actually running existing SAT solvers on the instance.

Related question
Which SAT problems are easy? on cstheory.SE. This questions asks about tractable sets of instances. This is a similar question, but not exactly the same. I am really interested in a heuristic that given a single instance, makes some sort of semi-intelligent guess of if the instance will be a hard one to solve.


texts: What are the smallest and biggest negative floating point numbers in IEEE 754 32 bit?

texts:
I am stuck with a question that asks for smallest and biggest negative floating point numbers in IEEE 754 32-bit (their representation and decimal numerical value from which one can approximate the precision of the number)? So -0, NaN and Infinity do not belong to negative rational numbers.

I have stumbled upon -3.403 x 10^38 and 2^-126. I came close to the first one actually. I tried to do some calculations but got kind of lost in the process as floating point representation is counter-intutive for me, especially when calculating negative numbers. Can someone help me to clarify my thought process for the calculations so that I can find the numbers?


texts: Finding the closest visible vertex among line segments

texts:
Given a set $S$ of line segments (possibly sharing endpoints) and a query point $q$, how fast can we find the closest visible endpoint from $q$? If $p$ is the closest visible endpoint to $q$, then, in this case, it means that the line segment $pq$ does not intersect with any other line segment in $S$.

I am trying to implement an efficient algorithm in CGAL. I have explored the nearest-neighbor and visibility structures from CGAL but could not conclude anything.


texts: How can I efficiently find the optimal order to apply special offers to a shopping cart?

texts:
Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the order to apply the special offers to minimize the final basket price?

For example, I have in my cart 4 items:

Coke \$2
Coke \$2
Sandwich \$3
Chocolate bar \$1

Total: \$8

There are two special offers in store:

Buy one get one free coke (\$2 saving).
Coke, chocolate bar and a sandwich for \$4.50 (\$1.50 saving).

One method of determining the order offers are applied might be to sort them by the savings they give. After applying the offers using this method my cart now looks like this:

Buy one get one free coke \$2
Sandwich \$3
Chocolate bar \$1

Total: \$6

There is no meal deal offer applied because after the Coke deal is applied there is not any coke items left to make a meal deal. This method of sorting by savings may seem to work, but there are cases in which it can fail, for example if the same deals were in place and my cart looked like this:

Coke \$2
Sandwich \$3
Chocolate bar \$1
Coke \$2
Sandwich \$3
Chocolate bar \$1

Total: \$12

After deals are applied, the two Coke items are substituted for the promotional offer first (it being the deal with the greatest saving). There is no other applicable deal so the algorithm ends, reducing the basket price by \$2. Obviously there is an error here because if two meal deals were applied before the coke deal, the price would have been reduced by $3.

The naive solution to this problem would be to enumerate each possible permutation of the list of special offers, and find the one that minimizes the basket total when applied. This would have a factorial runtime based on the number of special offers available.

Is it possible to improve on a factorial runtime and if not, are there any efficient approximate solutions?


texts: What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?

texts:
Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a
number (possibly one) of continuous parts. For each part independently, I then choose any integer
value and removes all occurrences of this value in the corresponding part (note that there could be
no such occurrences). After that, the person will combine all parts in the same order to achieve a new
sequence (T).  How to find out the minimum number of parts needed to split the sequence in order to achieve this goal .
 let n = size of sequence S and m = size of sequence T

Constraints: 1 <= n,m <= 2000

Input Format: n m  Sequence S   Sequence T

Output Format: if it is not possible to transform S into T output -1  otherwise, output min number of parts required.

Sample Input and Output:

Input
Output

4 24 2 7 24 7
1

7 24 7 1 4 1 7 14 7
3

3 27 4 24 7
-1

My Attempt:
I did not understand how Sequence S={4,2,7,2} can be transformed to T = {4,7}. If I followed this procedure by splitting a sequence into parts such as {4} {2} {7} {2} and then iterate from 1st index and then the 2nd index until the end, and if I encounter the same value I delete all of its occurrences. When I do this, I get  the sequence {4,2,7} and minpart is just 1.
And, for the sequence {4,7,1,4,1,7,1}, I am able to get {4,7,1} and minparts are 3.
But I do not understand, how both of these sequences: S = {4,2,7,2} and S = {4,7,1,4,1,7,1} can be transformed to the sequence T = {4,7}?


texts: Algorithm for estimating function maximizing parameters

texts:
I'm trying to find parameters $\omega, \alpha,$ and $\beta$ which maximize

$$
\sum_{i=1}^m{\left\{ -\ln(v_i) - \frac{r_i^2}{v_i} \right\}}
$$

where

$$
v_i = \omega + \alpha r_{i-1}^2 + \beta v_{i-1}^2
$$

Since numerical values for $r_i$ and $v_1$ are given my first thoughts were to use the normal equation

$$
\Theta = (X^TX)^{-1}X^Ty
$$

This I realized quickly wouldn't work because there are no observed values of $v$ to fill $y$ with. I similarly considered something along the lines of gradient descent but then again I ran into the same problem. I only have $v_1$ as a starting point but no observed $v_2, v_3$ etc. I've also found my way on the Levenberg-Marquardat wikipedia page but then again I came up empty because I can't figure out how to produce (independent, dependent) bundles under these conditions.

The problem I'm basically trying to solve is that of estimating the three parameters of a GARCH(1,1) model ($v_i$ above).

MathLab offers tools which can estimate these parameters for me but what I'm trying to do is understand how the under-the-hood algorithm works in coming up with these numbers. Even excel's solver can figure out these parameters given an initial guess but I have not been able to find how it actually works. I understand that starting from an initial guess it uses an iterative method to arrive at a solution but I can't figure out how it updates the parameters at every run.


texts: How to build an execution graph of concurrency accesses

texts:
Sorry If I don't use the right vocabulary, maybe part of my question is due to the fact that I don't know the name of what I'm searching.

I have a bounded set of operations that need to access a database. I want to create an "execution graph" of these operations that prevents conflicting accesses.
For each of this operations, I know the read set and write set.

Let's say I have four operation, a, b, c and d :

readSet(a) = {k1, k2}
writeSet(a) = {}

readSet(b) = {}
writeSet(b) = {k1}

readSet(c) = {}
writeSet(c) = {k2}

readSet(d) = {}
writeSet(d) = {}

So here I can build the graphs whit the following set of edges :

g1 -> { (b, a), (c, a) }

g2 -> { (a, b), (a, c) }

How do I build such a graph that is that is as little deep as possible ? ( i.e that maximize the parallelism ? )

What are the keywords to find litterature on this problem ?


texts: Order of storage of pointers for a linked list of length n

texts: I have a linked list in which I have kept the elements in order (increasing/decreasing). I want to be able to perform a binary search on this linked list. For this I am keeping pointers to the middle element of list of length n, n/2, n/4 so on. I am not able to figure out what would be the order of storage in this case. Any ideas?


texts: Repair operator for evolutionary algorithm

texts:
I am working on a resource allocation problem using an SPEA 2 evolutionary algorithm. The problem involves decision variables where each variable has a different domain e.g. $E_i \le d_i$ where $E_i$ is the allocation to a user and $d_i$ is individual demands. The problem involves a linear constraint such that $\sum(E_i) = total resource$. The probability of the creation of feasible off-springs after crossover and mutation operators is extremely low. So, we need a repair operator for this purpose. I need guidance for the selection of suitable repair operators and how should I apply that, I mean should we repair all solutions or some percentage.

So far I designed an operator where the of an off-spring generated is repaired as follow:
1) apply bound
2) Determine constraint violation i.e. leftover resource or over-consumed resource
3) Find unmet demand $d_i$
4) Divide remaining resource proportionally among user, so update $E_i$

This operator creates a feasible solution but I am not sure if my approach is reasonable and what percentage of solution I need to repair.

I would appreciate the guidance, comments, or any literature reference.


texts: What are the disadvantages of Fibonacci Heaps?

texts:
A Fibonacci heap is a data structure for priority queue / heap operations. It seems to have the best complexity for all operations:

Since it has the best performance, why not use it everywhere?
What are the disadvantages of it?


texts:
A directed acyclic graph $G$ is confluent, if any two vertices
  ${v_1},{v_2}$ in $G$ which have a common ancestor $u$ also have a
  common successor $w$. (I.e. if there are paths from some $u$ to both
  ${v_1}$ and ${v_2}$, then there are also paths from ${v_1}$ and
  ${v_2}$ to some $w$. Vertices $u,{v_1},{v_2}$ and $w$ do not need to
  be distinct, thus e.g. a single "line" of vertices is trivially
  confluent) Design a linear-time algorithm that determines whether
  a given DAG $G$ is confluent.

Is the "line" with $3$ vertices $u \to v \to w$ s.t. ${v_1} = {v_2}$ trivially confluent? Or is it nesseccary to have ${v_1} \ne {v_2}$ and thus the smallest number of vertices such line may have is $4$ $u \to {v_1} \to {v_2} \to w$?

Edit: Solved the problem.


texts:
I keep stumbling upon this term in my lecture notes tutorials and assignments, but I have no clue what it means, google doesnt give me anything usable at all.
Here is an example how this term is used (material in german, but self explanatory really)

So my question is: is this a regional dialect or some important technique that I have missed ?


texts:
I am trying to learn the binary number system but I keep coming up against a barrier to my comprehension. To people who are in the know this will no doubt seem an extremely elementary error so please be  kind :). The problem concerns the eighth count. I’m going to explain my reasoning up to that point alongside the counting record in the hope that my error can be pinpointed. Apologies for being long-winded. Here goes…

First count to 1 (from 0)
 We want to continue but have run out of digits. Therefore mark the                     first count with a digit on the left and begin counting from 0 again. Thus:    10 (This shows that the count is accumulative and not simply a repeat of
(1) and is  analogous to starting the tens column in decimal place                  value.)
 Simply count forward in the right column, "carrying" the 1 from the previous count to indicate place value. Thus: 11.
Repeat the procedure at (2), getting the original 1 to budge up and put a zero to the left to show place value. Thus: 100.
Count forward, thus: 101.
Repeat as per (2) and (4). We now have two left columns with 1s as their value and a fresh 0 in the right column, thus 110.
 Simply count forward in the right column as per (1), (3), (5), thus: 111.

Right, the next stage [(8)] is what baffles me. I know that the next number is 1001 but I don’t understand why. Surely if we are following the pattern I have outlined above (and, assuming this is correct) the next number should be 1101, i.e we start a new column as we did when faced with 1 on the right side at (2), (4) and (6). Instead it seems to be that when we max out on 1s (i.e. 111) we have to reset several columns at once. Why am I wrong? I know it will most likely have to do with 2 being the exponent for binary numbers but I can’t make the connection and all web explanations are overly complex. Any help gratefully received.


texts: Does a megabyte represent (2^8)^1000000 bits in base2? Isn't that more than enough combinations to represent everything?

texts:
Every introductory CompSci resource I can find goes through how 8 bits are in a byte, etc. So a byte can store some 2^8 values in binary. Then when asking about four bytes, we can assume this is (2^8)^4=2^32.

But I can't find anywhere if this pattern holds up until the total amount of hard drive or memory storage. For instance, if even a single megabyte can really hold (2^8)^1000000 bits, isn't this a number so large that it could store all data in existence everywhere in the universe many times over? The number of possible combinations from a number that large would surely never be reached. Yet in reality, we all know a megabyte isn't much.

I can't help but feel somewhere that the exponentiation must stop, and we instead multiply bytes together. Or is it really the case the numbers can get this big? Such as a gigabyte representing ((2^8)^1000)^3 bits?

If I can represent a number, let's say, 1 million in 32 bits, and I wanted to store 10^50 numbers this large, wouldn't the required bits be 2^32*10^50? First of all, I'd never need to store 10^50 of any unit of data on my hard drive, that's astronomically massive, and secondly, 2^32*10^50 is quite a small number, far below (2^8)^1000000. So what's really happening here that we need so much storage, and a megabyte isn't much?


texts: What is the term for two file formats that describe the same amount of information?

texts:
I am working on file formats conversion. Some of them can be converted back and forth to others without losing any information (fields or precision of the numbers encoded), others file format do not take into account some data or meta-data or use approximated values.
I was looking for a term to describe the first case, where two formats describe the same amount of information. I'm aware of the term isomorph that seems to describe the case quite well but I couldn't find any reference to any isomorph file format. Is there any other term used for describing the case?


texts:
Sorry if the Question sounds a little trivial.
Let A* be the set of all languages over A={a,b}. Then A can be written as {aUb}*
which is a regular expression.So this is the set of all languages(actually set of all strings) regular.Am i thinking in the right direction.


texts: Distribution of IEEE 754 single precision floating point over number line

texts:
"What is the maximum and minimum difference between two successive
  real numbers representable in IEEE 754 Single Precision and Double
  Precision Floating Point Representations respectively?"

In order to answer this question, I am unable to visualise how Floating Points are spread over the real number line, assuming the precision of real numbers is same as that of IEEE 754 single precision & double precision respectively.
So I am looking for graphs of the following two functions based on IEEE 754 single precision representations.
$f\left ( x \right ) = \left\{\begin{matrix}
 0 & ,\text{if x can't be represented in IEEE 754 single precision.}  \\
 1 & ,\text{if x can be represented in IEEE 754 single precision.}
\end{matrix}\right.$
$f\left ( n \right ) = \left\{\begin{matrix}
d, & \text{where d is the diffrence between n-th and (n-1)th floating points representable in IEEE 754 single precision. }\\
0, & \text{if n-th or (n-1)th floating point number does  not exists in IEEE 754 single precision representations.}
\end{matrix}\right.$
Considering only normalised values and zero.
and not considering Infinities, NaN and denormalised numbers.

Could anybody please help me out with these graphs so that I can understand floating points properly.


texts:
Currently I have this 4 bit CPU as shown in the schematic diagram below.

What I wish to achieve:

Add one more output register to make the CPU output a total of 8 bits
Show alphabet using the 8 bits output

My current trial:

Cout of the first IC connected to Cin of the second IC
Cascaded in a synchronous fashion

What I unsure/don't understand:

Should I connect the A~D pins of the second register to ALU?
The LOAD-bar pin is connected to LO-bar of the ALU. Should I add one more LO-bar to the ALU and connect it to the LOAD-bar of the second register?


texts: Is this algorithm for Exact Three Cover sub-exponential, because I find $length(s)/3$ combinations for $C$?

texts:
Given an input $S$ (set of elements) find an exact three cover for a list of 3-element sets named $C$.
$S$ = 1,2,3,4,5,6
$C$ = [1,2,3],[4,5,6],[3,1,2]
Algorithm
1.Sort list and delete occurrences of sets that repeat in $C$.

(eg. $[1,2,3]$ repeats because of $[3,1,2]$. Of course leave one of
the sets.)

2.Remove sets that have elements that do not exist in $S$.

(eg $[1,2,9]$... $9$ does not exist in $S$)

3.Remove sets with repeating elements.

(eg. $[1,2,2]$ is deleted from $C$)

4.Remove repeating sets

(eg. $[1,2,3]$ and $[1,2,3]$ but leave $[1,2,3]$)
After $C$ has been sorted; the worst-case length of $C$ will be
$\frac{lenght(s)!}{\left(3!\left(length(s)-3\right)!\right)}$

5.Use $length(s)$/$3$ for $K$ combinations of $C$.

(eg. there will be $2$ sets required for an Exact Three Cover of
$S$ $[1,2,3]$,$[4,5,6]$)

It seems the number of combinations will be < $2$^$\frac{lenght(s)!}{\left(3!\left(length(s)-3\right)!\right)}$ at least most of the time.
Question
Is this algorithm sub-exponential at least on average?


texts: Maximum cardinality matching of maximum weight

texts:
Given a graph, I want to find the matching with the maximum size in terms of edges, but among those matchings, given a real weight function on the edges, the one with the maximum weight. Is there an algorithm that can find such a matching in polynomial time?

To make things more concrete, here is an example bi-partite graph where the edge between 1->5 is poisoned; if you select it, you won't get a matching of largest possible size (which is 3). But if we gave this poisoned edge a large weight, the maximal weight matching will be forced to pick it, making the size of the matching less than it possibly could be.

Side note: these questions are readily extended to the min edge cover, min weighted edge cover and "is there a polynomial time algorithm for min edge cover with minimal weight".


texts: Finding often repeating substrings in multiple strings

texts:
I'm currently looking for an algorithm to find often repeating substrings in one or multiple strings. However, my search until now was not really successful. I try to illustrate the problem on the following example strings:

S1: ABCCCDxxxxxxABCCCDxxxxABCCCD
S2: xxxxxABCCCDxxxxABCCCDxxxxxxx
...
S10: xxABCCCDxxxxxxxxABCCCDxxxxxx

In the given example strings S1, S2 up to S10, the substring ABCCCD occurs multiple times, making it an often repeating substring, and thus interesting for me. However, when trying to find an algorithm that helps with finding such substrings, I often end up at the longest common substring problem, which would help me find the longest common substring between S1 and S2, however, it would ignore the repetition of the substring.

Does an algorithm exist, that can help me with this problem? Additionally, it would be quite interesting to set additional constraints, such "substring must occur at least n times" or "substring must be at least n characters" long.