texts: Find the origin and the destination of a trip from a serie of tickets

texts:
I was asked to design an algorithm that solves the following problem :

  Consider a travel from city A to city B, made of several trips by
  train through other cities in between. With an access to the
  unordered list of train tickets from which you can read the cities of
  departure and arrival of each trip, find A and B.

Unfortunately, I was unable to give an efficient algorithm when I needed to (in pseudo code), but once I got home, I came up with this answer (in JavaScript).

var tickets = [
    {from:'Paris', to:'Berlin'},
    {from:'London', to:'Paris'},
    {from:'Zurich', to:'Milan'},
    {from:'Berlin', to:'Zurich'}
    ];

function getTrip(tickets)
{
    var ticket = tickets.shift();
    var trip = {from:ticket.from, to:ticket.to};

    while(tickets.length > 0)
    {
        ticket = tickets.shift();

        if(ticket.from == trip.to)
        {
            trip.to = ticket.to;
        }
        else if(ticket.to == trip.from)
        {
            trip.from = ticket.from;
        }
        else
        {
            tickets.push(ticket);
        }
    }

    return trip;
}

var trip = getTrip(tickets);

console.log('The trip was from %s to %s', trip.from, trip.to);

While this might look like a very simple problem, I am still curious to see if there is a more efficient solution (for both time and space) or simply considerations I completely forgot. This may not need to be in JavaScript (especially if the language gives greater control over some aspects of the problem).


texts: Throwing an error when initializing an object in c++

texts:
Let's say that when initializing a pet class, I wanted to exclude or disallow dogs or cats as species. What would be the proper way to throw an invalid_argument exception?

using std::string;
#include <stdexcept>
using std:: invalid_argument;
struct Pet {
  const string name;
  long age = 0;
  const string species;
  Pet() : name("Dan"), age(0), species("alligator"){}
  Pet(const string & the_name, const string & the_species): name(the_name),
  species(the_species), age(0) {};
};


texts: Mean geodesic distance between two points in Delaunay Graph

texts:
If I have a Delaunay Graph, what is the mean geodesic distance between two randomly chosen nodes.
I know that in a small world network, it is in O(log(N)), with N being the number of nodes.

Thank you!


texts: Find the best set of triples of objects, using each object at max one time

texts:
I stumbled upon an interesting problem and I'm stuck with it, since I can't find parallels to other problems or algorithms to solve it.

We have a set of objects $O = \{a,b,c,...,z\}$, objects can make triples, e.g. $T=(a,b,c)$  $a,b,c \in O$ and we have a set of triples $X = \{T_1, ... T_n\}$. Each triple is assigned a value $c: X \rightarrow \mathbb{R}$

not every object has to be in a triple
an object can be in multiple triples
there can be triples using the same objects, but in a different order e.g. $(a,b,c),(c,a,b)$

Goal: Find the subset of triples $S \subseteq X$, where $\forall x \in \bigcup S: \exists y \in \bigcup S => y =x$ (Every object may appear at most once in the selection) with maximum $\sum_{T \in S} c(T)$ (maximum value of selection).

Is there a fast way to get the maximum? If not, is there any fast strategy that may produce a good result?

A simple greedy strategy would be to sort the triples descending by value and take a triple into the subset if all of it's objects are unused. This can be done in $O(n \log n)$, but does not produce the optimal result.


texts: How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP?

texts:
The following theorem (from "The Design of approximation algorithms" by Williamson & Shmoys, pg 43) states:

  For any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm for the
  traveling salesman problem on $n$ cities, provided $P  \neq NP$. In fact, the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$.

This theorem is given without a proof. It only explains, before the theorem formally stated, that for any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm. This part is clear. But the claim that the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$ is not obvious to me. Could someone give me a hint how to prove it or sketch of proof?


texts: Is any language that can express its own compiler Turing-complete?

texts:
A comment over on tex.SE made me wonder. The statement is essentially:

  If I can write a compiler for language X in language X, then X is Turing-complete.

In computability and formal languages terms, this is:

  If $M$ decides $L \subseteq L_{\mathrm{TM}}$ and $\langle M \rangle \in L$, then $F_L = \mathrm{RE}$.

Here $L_{\mathrm{TM}}$ denotes the language of all Turing machine encodings and $F_L$ denotes the set of functions computed by machines in $L$.

Is this true?


texts:
For AVL-Tree there exists the following Rotations for Balancing:

Left Rotation
Right Rotation
Left-Right Rotation
Right-Left Rotation

My Question is about the Naming for the Double-Rotations. Sometimes a Left-Right Rotation is defined as a Left-Rotation followed by a Right-Rotation. This is for me the logical case. Sometimes a Left-Right Rotation is defined as a Right-Rotation followed by a Left-Rotation.

Is there a reason for this different definitions? I think it is only a Exchange of the terms - but why?


texts: How to draw Turing machine for multiplying a number by 2 in base 10

texts:
I'm trying to design a turing machine that given a number in base 10 multiplies it by 2.
The problem seems trivial if the number is represented in binary so what I've thought is try to convert it from base 10 to base 2, multiply it by 2 and convert it again.
But I'm not quite sure if I'm taking the wrong path or not. Maybe there is a simpler way. Any hints or suggestions?


texts:
Assume a randomly ruffled pack of n cards with numbers from 1 to n. Each time we pick the top card from the pack (while there are still cards) and we put them according to the following rules:

The first card goes to the top of a stack

For every new card k,or

(i) the k is put on the top of an already existed stack, if the value of the top card of a existed stack is bigger than the value of the card k or

(ii) we create a new stack righter than the other stacks and with the card k.

The game is completed after n rounds when there are no more cards on the first pack of cards.

The problem asks to find the optimal algorithm for minimum stacks and prove that this one is the optimal. Thanks in advance.


texts: Minimum Product Weight in a Graph with 2 weight functions

texts:
Hello Community,
Given an undirected graph G = (V,E) where E has 2 weight functions w1(e) --> {1,2,..9} and w2(e) --> {1,2...9} with given a source vertex s and destination vertex t. we can measure
the weight of this path with respect to w1 and with respect to w2 separately.The two weights
are denoted, respectively, by w1(p) and w2(p). The product weight of a path p is defined as w(prod) p = w1(p) * w2(p). We wish to find the minimum product-weight paths from s to t in G.

 First, I tried Dijkstra on the graph to find the shortest paths with respect to w1 and w2. But after several test cases where the weights might be the same, it fails.
 Second, I tried MST algorithm(Kruskal's). It does not get a unique path when the weights are the same which does not lead to the best solution.
 Third, BFS and DFS will traverse through the graph, but I am clueless on how it will give the minimum product weight path.

 Any help related to this problem is much appreciated.


texts: What is a good method for modelling combinatorial tree (sport competition results)?

texts:
Probably newbie question here, please point me out to relevant theories/tutorials if needed :

let say I want to evaluate the probabilities of the final rankings for a sport competition
the competition involved 8 teams, but I can simplify the problem to 4 contestants (say A - B - C - D)

the competition is splitted into n journeys during which every team faces another team (and only one). So with 4 contestants, I have 2 matches per journey
at the end of a match, 6 different points attributions are possible (depending on the score)

After one journey, there are 36 different possible combinations in terms of team's points. So the model looks like a tree with a journey at each level.

Even if I simplify the situation to 2 journeys left, I can't think of a elegant way to implement this problem rather than "manually" creating the tree with all the possible combinations at each level and counting the leaves ?

I'm not familiar with this kind of problem so I'm not sure about the path forward.


texts: Problem with understanding proof of the Space Hierarchy Theorem

texts:
The Space Hierarchy Theorem states that

If $f(n)$ is space contructible, then for any $g(n) \in o(f(n))$ we have $SPACE(f(n)) \neq SPACE(g(n))$

An example of a SHT proof can be found here or here but they are generally based on the same idea differing only in technical details. We would like to find a language $L$ such that $$L \in SPACE(f(n))$$ and $$\forall{g \in o(f(n))}: L \notin SPACE(g(n)).$$ So the proof claims that a language that fulfills these constraints is the following (for the sake of this post we do not care about $M$s whose description is too short for the asymptotic behavior of their space complexity to kick in) $$ L = \{ \langle M \rangle: M\text{ rejects }\langle M \rangle\text{ using }\leq f(|\langle M \rangle|)\text{ space}\} $$ and it describes a TM that accepts this language in $f(n)$ space. Then it tries to prove the second constraint using diagonalization argument in the following way:

Suppose there is $M'$ such that $L(M') = L$ and $M'$ is of $g(n) \in o(f(n))$ space complexity. Then

If $M'$ accepts $\langle M' \rangle$ then (from assumption) $\langle M'\rangle \in L$ then (from definition of $L$) $M'$ rejects $\langle M' \rangle$
If $M'$ rejects $\langle M' \rangle$ then (from assumption) it does so in $o(f(n))$ space then (from definition of $L$) $\langle M'\rangle \in L$ then (from assumption) $M'$ accepts $\langle M' \rangle$

Contradiction. Therefore such $M'$ does not exist.

So what bothers me is that in the argument above we could just as well take a TM $M''$ that runs in $f(n)$ space and the argument would still hold, therefore breaking the first constraint.


texts: Is it possible to write a fully-decidable type system for the J language?

texts:
I'm experimenting with the J array language, a dynamically-typed array language with mutable assignment, subtyping, and function overloading (just like traditional APL).
It is unclear to me whether statically typing the J language (without subtyping) without need for type annotation is possible.
Given that J's types are well-bounded not considering array dimensions (only arrays of simple types such as string, int, box, etc.), do the options below allow sound and decidable inference?:
Mutable assignment: Is giving a mutable value a union type to derive multiple ASTs and choose the appropriate AST at runtime correct? Are there better alternatives?
Polymorphism and overloading: Since J simple types are well bounded (which apparently makes Hindley-Milner compatible with function overloading), can I essentially forget about the array part i.e. type Arrayof Int becomes Int, leaving array dimension checks to the runtime?
Thanks!


texts: How the $EX(f)$ is evaluated in symbolic model checking?

texts:
I was reading the symbolic model checking, So there it has mentioned that we can represent the set of states and transition relations of any transition system with the help of ROBDDs.

I was trying to understand how the below  would have executed step by step.

$$
  \exists_{f({v'})}[\,\underbrace{f({v'})}_\text{ROBDD of set of states}\,\land\, \underbrace{R({v}, {v'})}_\text{ROBDD of transition relation}\,]
 $$

So here the $f(v')$ is in ROBDD form and $R({v}, {v'})$ is also given in ROBDD form and now the $\land$ operation is performed on two ROBDDs , that I know how to perform. But where I stuck was

How does the there exists will be evaluated $\exists_{f(v')}$ after you get the resultant ROBDD of $f(v') \land R({v}, {v'})$ ?
After you perform the above operation you'll finally get some ROBDD representing the set of states, so from that set of states how will I get back the list of states ?


texts: What information do we get from a compiler's parse tree?

texts:
In the compiler course by Alex Aiken on Coursera, more specifically lecture 05-02 Context Free Grammars,  the professor says that CFGs give answers of the type yes/no, i.e. whether the given string of tokens is valid or not. He adds that it is also desirable to know how a particular string of tokens is in the language; for this purpose he introduces parse trees.

Why is the "how" part important?


texts: Transforming SAT to Quadratic Programming in polynomial time

texts:
I would like to show that Quadratic Programming is NP-hard.

I am currently reading a couple of papers which state that QP is NP-Hard and prove it by transforming SAT to QP, however I am finding the diction quite tough since I am just a beginner in the field. Would anyone happen to know the answer to this question who can maybe explain it to me in simpler terms?


texts:
Given an array with size of $n$ and except from $\sqrt{n}$ ( lower value ) elements in the array, all of the other elements are integers between the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$]
I will need to write an algorithm that sorts that array in $\Theta$($n$)
Furthermore, will the same mission could be performed if, now it is given that except from $n/2$ ( lower value ) elements in the array, all of the other elements are integers between the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$]
And how about $n/log(n)$ ( lower value )?
( In this time thare are ( $n$ - $n/log(n)$ ) ( lower value ) integers in the given bounds )
Note - We can not know where are the the integers located in the array

MY METHOD: For the first question I tried to seperate the array to 2 arrays, and then for the array with the numbers inside the bounds of
[$\sqrt{n}$, $n$$\sqrt{n}$] - I have converted the elements to $n$
based and sorted it with counting-sort. For the second array - sort it
with any other sorting method and then merge the 2 arrays

My questions are:

Does my approach is correct to the first question ( in terms of run-time, algorithm )?
What would be the best solution for the other question asked


texts: What is the probability that an expanding bipartite graph exists with the property, |V1|=|V2|?

texts:
I want to find a bound on the above problem, and show that a random graph has a positive probability of being an expanding bipartite with the property, |V1|=|V2|. I am not getting, where should I start.

Apologies for not writing my understanding, I am very much stuck.


texts: Is this statistical group summation unambiguously reversible?

texts:
Let $X$ be a finite multisubset of $\mathbb{N}^2$. Let's introduce the following notation:
$A$ is a set of all first elements of pairs from $X$ and $B$ is a set of all second elements of pairs from $X$.
$cnt_1(n) = |\{(n,  b)|(n, b) \in X\}|$ (that is a number of elements in a corresponding set).
$cnt_2(n) = |\{(a,  n)|(a, n) \in X\}|$
$sum_1(n) = \sum_{(n,b) \in X}b$
$sum_2(n) = \sum_{(a,n) \in X}a$
$Y=\{(a, cnt_1(a), sum_1(a))|a \in A\}$
$Z=\{(b, cnt_2(b), sum_2(b))|b \in B\}$
The question: Given only $Y$ and $Z$ is it always possible to unambiguously reconstruct $X$?

Equivalently, phrased in terms of SQL: Given an (unordered) set of 2-tuples (X) of natural numbers:
CREATE TABLE X (
    a int,
    b int
);

the following statistical summaries and are derived:
Y:
SELECT a, COUNT(1) AS ca, SUM(b) AS bs FROM X GROUP BY a ORDER BY a;

Z:
SELECT b, COUNT(1) AS cb, SUM(a) AS as FROM X GROUP BY b ORDER BY b;

Is it possible to unambiguously re-construct X when knowing only Y and Z?


texts: How to decode multiple-digit gamma codes and get the gap sequence?

texts:
How to decode gamma code ($\gamma$ code):

1110001110101011111101101111011

and get the gap sequence?

Detailed information about Gamma codes ($\gamma$ codes) with brief example of decoding can be found here.

But in their example there is only case when gamma code ($\gamma$ code) consists of one digit only, how to deal with multiple digits binary string?


texts:
Are there any programming languages where algebraic data types can be expressed not only by using intersection and disjoint union but also a standard set union (intersection + disjoint union)?

Do such types even make sense?

If so, could you provide practical example of use?


texts: Show that functions in O(1) can't grow faster than their composition with themselves

texts:
Let $f(n)$ be a function s.t $f(n)\geq 1 $ for every $n$.

I want to disprove that if  $f(n) = \omega (f(f(n)))$
 then it means that  $f(n) = O(1)$.

I thougt of 2 approaches to show that this statement is incorrect:

Give an Example of a function that $f(n) = \omega (f(f(n)))$ for it,

for example: $f(n) = \sqrt n$

and then I'm supposed to get a contradiction, and show that $\sqrt n \neq O(1)$
but that's the step I'm stuck at, but I'm not sure how that contradiction is derived. I mean formally, because I understand it by intuition.

Start with the function that suffice $f(n) = O(1)$  and then show that it's impossible to get the condition under that function (It's sort of going from the end to the beginning)

what's the right approach and how do I get it right?


texts:
I have made two DFA’s for $ L= \{a^n b^n a | n\ge0\}$.

First one has several states. The second one is accepting an empty string also.

Somebody please guide me the correct one.

Zulfi.


texts: Converting Binary Search Tree into Decreasing Ordered Linked List

texts:
Given a BST with n nodes, the algorithm should create a linked list that contains a decreasing order sorted array. The algorithm should have a worst case time complexity O(n). The signature of the function should be toList(T, L), where T is the root of the tree and L is a linked list.
The only operation that allowed to use in the linked list is InsertFront.
My attempt:
toList(T , L){
   if (T == null) return
   toList(T.right , L)
   InsertFront(T)
   toList(T.left , L)
}

What do you think about that?
Any suggestions will be great!
Thanks a lot!


texts:
I have been doing some research into the limits of computation and I have come across the terms intractable and undecidable. Are these two terms the same thing?

What does intractable mean and what is an example of an intractable and undecidable problem?


texts: Do any two spanning trees of a simple graph always have some common edges?

texts: I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far.  But I couldn't prove or disprove this either.  How to prove or disprove this conjecture?


texts: How to find a cut in a graph with additional constraints?

texts:
I have a complete undirected graph $G=(V,E)$ with positive non-null rational weights $c:E \to \mathbb{Q}^+_{*}$ on the edges, such that $c(v,v) = 0$ for all $v$, and a subset $C \subset V$.
I would like to find (if it exists) a subset $S \subset V$ such that $\delta(S) < 2$, $S$ contains at least one vertex of $C$, and $S \ne C$.  Here $\delta(S)$ represents the sum of the weights of the edges that cross the cut $(S, V \setminus S)$.
Is there a polynomial-time algorithm for this problem?
I have thought of two possible approaches:

Create a new graph $G'$ using as edge weights $c'(v,w) = -c(v,w)$ and adapt (by updating some LP formulation or DP approach) the max-cut optimization version to this case;
Reduce this problem in the problem of partitioning $V$ into two vertex sets $X,Y$ so that the sum of the weights of the edges crossing the cut is < 2, and $X$ and $Y$ each contain at least one vertex of $C$. However, I couldn't think of any approach to solve this problem, yet.

I know the max-cut problem is hard, which makes me wonder whether there is a polynomial-time algorithm for this problem.
Remark: The proposed solution does not need to follow the presented approaches, they are presented just to help the reader.
I am facing this problem in a fractional separation routine of a routing MILP formulation.


texts: Heuristics to Find Circuits Allowing for Vertex Revists

texts:
I'm currently working on a project discussing applications of the Delaunay Triangulation, and the primary use-case is applications to TSP (or relaxations of the problem).

See: http://www.lancaster.ac.uk/staff/letchfoa/articles/triangulations.pdf for context.

One snag in the approach is that it occasionally produces non-Hamiltonian graphs (no Hamiltonian cycles).  This forces us to consider relaxations of TSP where revists are allowed.  In particular, given a Delaunay graph $G = (V,E)$, where the edges $E$ are weighted, I wish to find the minimum weight circuit when revisits are allowed.

I'm sure the usual heuristics apply here (nearest-neighbor, simulated annealing, ant colony, etc.) but I'm looking for any major research in this direction.  I had difficulty finding anything substantial after a few hours research.  This is perhaps because I'm having difficulty putting the problem into words, which brings me to my next question: is there a common name for this problem, so that I can search the literature more efficiently?

Thanks,
Jon

PS: Attached is one such non-Hamiltonian triangulation.  I had initially hoped these cases would be very uncommon, but unfortunately this one arose from a data set representing city locations (see: http://www.math.uwaterloo.ca/tsp/world/countries.html).


texts: Behavior of different multiplied and added time complexities

texts:
Θ - Tightly bound

O - Upper bound

Ω - Lower bound

I understand that for addition, the max asymptotic value is taken, for example...

if ƒ1(n) = O(n) and ƒ2(n) = O(n log n), then ƒ1 + ƒ2 = O(max(ƒ1, ƒ2) = O(n log n)

and for multiplication, the multiplied asymptotic value is taken, for example...

if ƒ1(n) = O(n) and ƒ2(n) = O(n log n), then ƒ1 * ƒ2 = O(ƒ1 * ƒ2) = O((n^2)log n)

My question is, what happens to the formulas for adding and multiplying functions of different growth rates when other bounds besides upper bounds (such as Ω - Lower bound and Θ - Tightly bound) are used?


texts: Algorithm to solve constraint satisfaction problems

texts:
I have group of people. Each person can be described by few characteristics:

age, occupation, city, favorite_color

I would like to generate 60 random people and combine them into pairs.
With a constrain that no person in a pair can share any characteristic, for example I can't have two people in a pair whose favorite_color is green.

I was thinking about using Backtracking algorithm to solve it.

What other algorithms I could use to solve this particular problem?
I would like to research and implement some.


texts: what is weak extensionality in $\lambda$-calculus?

texts:
I was reading the book lambda calculi , encountered  an equality theory called "the rule of weak extensionality", which is shown as follows.

$\frac{M \, = \, N}{\lambda x.M \, = \, \lambda x.N}$

Yes, it is obviously true.

But why it is called the rule of weak extensionality? what is weak? what is extensionality here means?

I think the reason should be interesting.


texts:
The probably approximately correct (PAC) learning model is defined as:

A concept class $C$ is said to be PAC-learnable if there exists an algorithm $A$ and a polynomial function $poly(·,·,·,·)$ such that for any $ε>0$ and $δ>0$, for all distributions $D$ on $X$ and for any target concept $c∈C$, the following holds for any sample size $m≥poly(1/ε,1/δ,n,size(c))$:

$Pr[R(hs)≤ε]≥1-δ$

where $R(hs)$ is the generalization error over a sample $S$ of size $m$ containing instances of variable $X$ following distribution $D$ and $size(c)$ is the maximal cost of the computational representation of $c∈C$.

I know $poly(1/ε,1/δ,n,size(c))$ is a polynomial. But what is the explicit form of $poly(1/ε,1/δ,n,size(c))$? What are the variables? What is its degree?


texts: Analysis of updating vertex and one example?

texts:
I see the following image on google:

And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should used sorted array or binary heap for implementation? non of others get us this Amortized Cost?


texts: Determining minimum number of edges to remove in a bipartite graph so the maximum path length is 2

texts:
I stumbled upon the following problem during my research.

I have a bipartite graph, and I want to determine the minimum number of edges to to remove so that the maximum path length in the resulting graph is 2.

Is this problem NP-hard? I was trying to come up with a polynomial time algorithm (and failed) and also tried to prove its NP-hardness, but also having a hard time.


texts: What is the algorithm for a decider to get the language accepted by a DFA?

texts:
I am trying to understand the larger problem of the decidability of the equality of two DFAs. I understand that this problem can be solved using minimizing DFAs, but my textbook states this can be done using symmetric difference.

Theorem: Let $EQ$ be a language, where $EQ$ = $\{<A,B> \mid \text{A and B are both DFAs and L(A) = L(B)}\}$.
In my notation, $L(X)$ stands for the language that DFA $X$ recognizes.

Prove that $EQ$ is decidable. This relies on the symmetric difference of 2 sets.

Proof: Let $Q$ be a decider defined as:

On input $<A,B>$ do:

Construct a DFA $C$ such that $L(C) = (L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B)) $
Run $<C>$ on the algorithm used to determine if the language recognized by a DFA is $\emptyset$  (We proved this is decidable before, and I have no issues with that).
If that algorithm accepts, then $Q$ accepts
If that algorithm rejects, then $Q$ rejects

For $Q$ to be a decider, we must prove that $Q$ will halt. Since we have proven that the algorithm used in step 2 is decidable, it will halt. So I have no problems with steps 2-4.

But the first step, how can I prove that constructing $C$ in that way will halt? I understand that the symmetric difference will result in a regular language because of the closure properties, but how can a decider actually carry out this process and be guaranteed to halt?

So this is my primary question, what is the algorithm for determining the language that a DFA accepts? I.e. given DFA $X$, how can I determine $L(X)$ (Again, this must halt, so we can't try every string in existence or something like that).

Some follow up questions are: What if the DFA in question accepts an infinite set of strings, how can we possibly represent that on the decider's tape (or if the complement of $L(A)$ is infinite, etc.)? How can a decider determine the compliment of a set? And if $L(C)$ ends up being an infinite set of strings, how can we process that so that we can construct DFA $C$?

My book simply states

  These constructions are algorithms that can be carried out by Turing
  machines.

which drives me nuts! Prove it.


texts: Context-free grammar for tautologies in one variable

texts:
Construct a context-free grammar for the set of tautologies in $p$ - that is, the set of formulae in $\{p, \text{true}, \text{false}, \land, \lor, \lnot, (, )\}$ which evaluate to $\text{true}$ for any assignment to $p$.

My first step is to construct a CFG for all propositional formulae:
$$ S \rightarrow S \land S \mid S \lor S \mid ( S ) \mid \lnot S\mid p \mid \text{true } \mid \text{ false} $$

What can I do from here?


texts: Constructing a random Hamiltonian Cycle (Secret Santa)

texts:
I was programming a little Secret Santa tool for my extended family's gift exchange.  We had a few constraints:

No recipients within the immediate family
Nobody should get who they got last year
The whole thing should be a cycle (Sandy gives to George, George to Tom, Tom to Susan, Susan back to Sandy)

So at this point, I think what I'm looking at is a directed graph, and I want to find a random Eulerian Hamiltonian Cycle.

Naively, I would say:

Start with a random vertex
Randomly choose a neighbour that hasn't been hit yet
Recurse until you reach a cycle (solution) or find a node with no neighbours (backtrack and choose a different random neighbour)

But this doesn't give all permutations equal weight.  Flipping a coin to choose the first neighbour could greatly limit subsequent possibilities, like in the graph below:

A -> [B, C]
B -> [C, D, E]
C -> [A, D, E]
D -> [A, B, E]
E -> [A, B]

If in the example above I start with A, I could choose B or C at 50% probability each.

If I choose B, the only cycle is 1) A->B->C->D->E->A
If I choose C, there are multiple paths: 2) A->C->D->B->E->A, 3) A->C->E->B->D->A

So with my naive approach, I would choose cycle 1 50% of the time, and 2 and 3 25% of the time each.

The route I ended up taking this year was to shuffle all of the vertices, and then check if it was in fact an admissable cycle.  But this gets less efficient as there are more constraints.

Is there an efficient way to generate a random Hamiltonian Cycle where each cycle has equal probability?

Edit:

By "efficient" I mean more efficient in runtime and/or space than generating the set of every Hamiltonian Cycle, and then choosing one at random.


texts: Which of these simple data structures is most efficient when implementing a Dequeue?

texts:
A deque is a double ended queue of course. So if I can either use 2 stacks, or 2 queues, or 1 stack and 1 queue, which two would I use to have the fastest implementation? Can we derive the complexity for InsertLeft, InsertRight, and RemoveLeft, and RemoveRight?

I was thinking of using 2 stacks. Call 1 stack 'left' and the other 'right'. All operations are now order O(1) because if InsertLeft inserts items at stack called 'left' and InsertRight inserts in stack called 'right'. Both stacks maintain the front and the end of the sequence respectively. Am I correct?


texts: Number of planar graphs with linear edges, given a fixed embedding

texts:
Suppose we are given a set of $n$ points on the plane.  How many different planar graphs can we form on those $n$ vertices, assuming that each edge must form a straight line between the two vertices it connects?
I'm interested in either showing for every set of points there are $2^{o(n\log(n))}$ planar graphs; or showing that there exists a set of points with $2^{\Omega(n\log(n))}$ different planar graphs.

I recently asked a similar question without the constraints that the edges form a straight line, and the answer I got directly utilizes this fact. I didn't specify this in the previous question, but I am actually interested only in graphs with those constraints. So, if anyone knows where I can find material about the number of such graphs, I would be glad to know about it as well.
Thanks in advance!


texts: Calculating the running time of Quicksort's PARTITION procedure

texts:
I am confused about calculating the PARTITION procedure's running time.
PARTITION procedure is used in the Quicksort Algorithm to partition the array $A[p...r]$
I analyzed the PARTITION procedure provided in the book Introduction to Algorithms:
  PARTITION(A, p, r)
1.  x= A[r]
2.  i= p-1
3.  for(j = p to r-1)
4.       if(A[j]<= x)
5.         i= i+1
6.         exchange A[i] with A[j]
7.  exchange A[i+1] with A[r]
8.  return i+1

Now what I figured out that:

Every procedure except lines $3-6$ has a constant time i.e: $\Theta(1)$
For loop would execute $r-1-p+1$ times.

Thus the running time should be: $\Theta(r-p)$
While the book quotes:

The running time of PARTITION on the subarray $A[p...r]$ is $\Theta(n)$ where $n= r-p+1$.

Could someone please help me out in knowing how to prove the aforementioned complexity?
Thank you.


texts:
I come from an electronics background. I know that there are three types of implementations of multithreading (see Computer Architecture: A Quantitative Approach, 5th Edition):

Fine-grain multithreading issues instructions for different threads after every cycle.
Coarse-grain multithreading only switches to issue instructions from another thread when the current executing thread causes some long latency events (like page fault etc.)
Simultaneous multithreading issues multiple instructions from multiple threads in one cycle. The processor must be superscalar to do so.

Does that mean that SMT is an extension of fine-grain and coarse-grain multithreading, and fine-grain and coarse-grain multithreading are only suitable for single core processor?

What is the exact difference between SMT and the other approaches?


texts: What practical/efficient algorithms exist for minimum weighted set cover problem (MIN-WSCP)?

texts:
For TSP there are well known heuristic and approximation solutions which run in low-polynomial time, like Christofides / 2-OPT and so on.

I need a practical, fast algorithm, ideally sub-quadratic complexity, to solve the minimum weighted set cover problem (which is NP hard). It solves subproblems in a genetic algorithm so needs to be fast rather than optimal. Are there any standard algorithms used to solve this?


texts: Bridging inductive natural number and bits?

texts:
Most popular representation for the natural numbers in type systems is:

  Inductive nat : Set :=
  | 0 : nat
  | S : nat -> nat.

However, digital computers usually represent numbers as bit sequences, arranged into bytes.

The above inductive definition is fine for highly theoretical needs and mathematical proofs, but quite far from and inefficient for real computations, especially, with a very large numbers. Even addition causes a lot of operations.

There surely also are formal verification abstractions for the bit-arrays.

The question is, how to bridge these two representations, for example, to transform a program, using S and 0 into a program, which uses more efficient type for N-byte number (maybe, it's called bit-vector - not sure)?

Of course, limitation to the size of the number may apply.

Are there any theories, which deal with automatic conversion of a program expressed in S-0-notation to a program in "bit-vector" notation and operations? Maybe, there are some stable approaches and even optimizing translators to that?


texts: Collection of inference rules viewed itself as a judgment

texts:
I'm confused about the intended meaning of the following passage from Bob Harper's Practical Foundations for Programming Languages:

  A collection of rules is considered to define the strongest judgment form that is closed under, or respects, those rules.

The author goes on to explain the italicized words.

Is this to be understood as saying that a collection of rules defines a unique judgment which somehow encompasses all judgments derivable from those rules?

If so- of what does this unique judgment consist? Does this necessarily include formal hypothetical judgments? Does it include some kind of union/conjunction of "orthogonal" applications of the rules? (eg $\overline{\text{zero nat}}$ and $\overline{\text{zero even}}$)

If not- what's the correct interpretation?


texts: Schedule tasks from a weighted list with time frame constraints

texts:
I'm attempting to create an automatic scheduler from a list of tasks I have available. Here are the key points:

Each task has been given a priority beforehand and the algorithm should try to maximize the total 'priority points' it can get from the tasks it schedules.
There should be no overlap between any tasks.
Each task might have several time constraints.

Here's an example:

$$
\begin{array}{c|c|c|c}
\text{Task} & \text{Duration (min)} & \text{Time Frames} & \text{Priority} \\
\hline
\text{Read a book} & 80 & \text{5:00pm-8:00pm} & 2 \\
\text{Go to the store} & 45 & \text{5:00pm-7:00pm} & 5 \\
\text{Eat popcorn} & 15 & \text{6:00pm-8:00pm} & 1 \\
\text{Ask the internet} & 25 & \text{5:00pm-6:00pm,7:00pm-8:00pm} & 8 \\
\text{Exercise} & 60 & \text{5:00pm-7:00pm} & 6
\end{array}
$$

And a schedule it could make would be (each character is 5 mins):

| 5:00-6:00 | 6:00-7:00 | 7:00-8:00 |
| Store || Exercise |   |Ask||E|    |

Which scores a total of 20 points (which I believe is the maximum in this example)

I realize this problem may be NP-Hard so, because of the nature of this project, the solution doesn't need to be optimal.

What I've come up with so far is something like the following:

Sort the task list based on priority (t*lg(t))
Find each 'block' of time, divided on each time frame boundary of the tasks (t) and store in a set. Then sort the set (f*lg(f)).
For every block, attempt to place a task, starting with the highest priority, at the earliest point available in the block. Repeat until there is no room for any task in the block. (t)
Extend the end of the block to the end of the next block and repeat 3. If no task can fit into the earliest point, move the earliest point to the beginning of the next block used for the beginning. (For instance, block 1 is filled as much as possible, so it is expanded to the beginning of block 1 to the end of block 2. No tasks can start at the beginning of the remaining space between blocks 1 and 2, so it moves the beginning of the active block up to the beginning of block 2).
Repeat 4 until there are no more blocks. (f)

Total: f*t + f*lg(f) + t*lg(t)

This greedy algorithm doesn't seem ideal and it will certainly fail horribly in some scenarios (such as a 60 min, high priority task from 1:00-3:00, and a lower priority task from 1:00-2:00). What is the best way to approach this problem?


texts:
I have been practicing with some Machine Learning algorithms for OCR, but I have a doubt about the glyph concept. For example in the UCI repository:

https://archive.ics.uci.edu/ml/machine-learning-databases/letter-recognition/letter-recognition.names

where it says:

4. Relevant Information:

   The objective is to identify each of a large number of black-and-white
   rectangular pixel displays as one of the 26 capital letters in the English
   alphabet.  The character images were based on 20 different fonts and each
   letter within these 20 fonts was randomly distorted to produce a file of
   20,000 unique stimuli.  Each stimulus was converted into 16 primitive
   numerical attributes (statistical moments and edge counts) which were then
   scaled to fit into a range of integer values from 0 through 15.  We
   typically train on the first 16000 items and then use the resulting model
   to predict the letter category for the remaining 4000.  See the article
   cited above for more details.

and when I see the file letterdata.csv I find something like this:

"letter","xbox","ybox","width","height","onpix","xbar","ybar","x2bar","y2bar","xybar","x2ybar","xy2bar","xedge","xedgey","yedge","yedgex"
"T",2,8,3,5,1,8,13,0,6,6,10,8,0,8,0,8

So for what I have read this first line refers to the character T that has certain values according to the attributes:

7. Attribute Information:
     1. lettr   capital letter  (26 values from A to Z)
     2. x-box   horizontal position of box  (integer)
     3. y-box   vertical position of box    (integer)
     4. width   width of box            (integer)
     5. high    height of box           (integer)
     6. onpix   total # on pixels       (integer)
     7. x-bar   mean x of on pixels in box  (integer)
     8. y-bar   mean y of on pixels in box  (integer)
     9. x2bar   mean x variance         (integer)
    10. y2bar   mean y variance         (integer)
    11. xybar   mean x y correlation        (integer)
    12. x2ybr   mean of x * x * y       (integer)
    13. xy2br   mean of x * y * y       (integer)
    14. x-ege   mean edge count left to right   (integer)
    15. xegvy   correlation of x-ege with y (integer)
    16. y-ege   mean edge count bottom to top   (integer)
    17. yegvx   correlation of y-ege with x (integer)

while some attributes are easy to understand, but I have a problem to visualice this in my head; I mean a glyph it is not like a grid in which a handwritten character is put on? something like this:

]

but where is the individual pixel data on the dataset letterdata.csv that I mentioned at the beginning of the question?
Also and for not opening another question thread, how these glyphs are generated and if there is a glyph reader in which I can put the data like: "T",2,8,3,5,1,8,13,0,6,6,10,8,0,8,0,8
and I can visualize the corresponding letter.
Any help?


texts: Knapsack Problem with Constraints on Item Values

texts:
Given $n$ items with weights $w_1,...,w_n$ and values $v_1,...,v_n$, and a weight limit $W$, the purpose is still maximizing the total value of items to be carried (while not exceeding the weight limit). Now, a new constraint is, once an item with value $v_i$ is taken, all items whose value is greater than $v_i$ must also be taken. (It is okay to assume that all $v_i$'s are different)
My purpose is to achieve this in $O(n)$ time, and here is my attempt (suppose the input is an array $A$ of tuples $(w_i, v_i)$):

Calculate total weight of the items: $W_{\mathrm{total}}\gets \sum_{i=1}^n w_i$;

while $(W_{\mathrm{total}} > W)$ do:
2.1 $p\gets$ median of values in $A$;
2.2 $R\gets$ items whose value is greater than $p$;
2.3 $L\gets A\setminus R$; (items whose value is smaller than $p$)
2.4 $W_R\gets$ $\sum_{A[i]\in R}w_i$;
2.5 $W_{\mathrm{total}}\gets W_R$;
2.6 $A\gets R$;

$W\gets W- W_{\mathrm{total}}$; (the remaining capacity)

Repeat step 2 for the array $L$, generating the array $L'$;

Return $L'\cup A$;

Notice that the algorithm for finding the median costs linear time.
I presume that my algorithm costs $O(n)$ time since, for every iteration in each while loop, the input size halves--but I am not 100% confident of that. So does this algorithm really cost linear time? If not, what amendments can be made, or is there a general idea for designing such an algorithm that costs linear time? Any help will be much appreciated! :)


texts: Proving this language is not context free using the pumping lemma

texts:
I am trying to prove why the below language is not context free. Note: this should be carried out by applying the pumping lemma for context free languages.

To prove something with the pumping lemma, we firstly need to choose an arbitrary m > 0. After that we need to formulate the string (alpha below) we are going to reach a contradiction with. But how do I formulate that string? Rational thinking lead me to believe it's the following:

What do I do next?
I have no idea about the length of $w$, and therefore the above approach seems kind of useless.

Is the solution to constrain $w$ to be of length at most $m$?
But again, I wouldn't know what to do from there.


texts: how to prove the following is a bijection?

texts:
I have a translation function which translates $\lambda$-terms to another representation let me call it $G_\lambda$, as follows.

$\chi(x)$               $=$    $ X^2$       if  $ x \notin \Gamma$

$\chi(x)$               $=$    $X$        if $ x:X \in \Gamma $

$\chi(\lambda x.t_1)$   $=$    $abs(X^1,\chi(t_1))$ and do $\Gamma,x:X^1$

$\chi(t_1 \, t_2)$      $=$    $app(\chi(t_1),\chi(t_2))$

where to translate $\chi(\lambda x.t_1)$, it creates a distinct $X^1$ and add a pair $x:X$ to set $\Gamma$.

$\chi(x)$ look $x$ in $\Gamma$, so we can use already added $X^1$ as bound variable or create a distinct $X^2$ for the free variable $x$.

so, a $\lambda$-term $\lambda x.yx$ will be $abs(X^1.app(Y^2,X^1))$.

I think $\chi$ is a bijection. It is obvious that function $\chi$ maps one $\lambda$-term to one $G_\lambda$ representation, so it is injective.

My problem is that since $X^1$ and $X^2$ are created fresh, if you translate a $\lambda$-term $\lambda x.yx$  twice, then you will have two representation such as $abs(X^1.app(Y^2,X^1))$ and $abs(A^1.app(B^2,A^1))$, which are equal terms but not syntactically same.

But how can i prove from $G_\lambda$ to $\lambda$-term is a surjective?


texts: How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?

texts:
I'm stuck on problem 9.4 from The Nature of Computation which reads:

  Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this to a simple exponential, i.e., to solve TSP in $O(2^npoly(n))$ time. Can you do this without using an exponential amount of memory? Hint: work out Problems 3.31 and 3.32.

The first part is relatively straightforward. Given a graph, a set of previously visited vertices, a start vertex, and a target vertex, go through all neighbors of the start vertex that haven't been visited already and recursively solve the TSP starting from the neighbor. Then add the distance between start and neighbor to each and return the minimum. The base case, which returns $0$, occurs when $start = target$ and all vertices have been visited.
There are $2^n$ possible inputs for the set of previously visited vertices and $n^2$ possibilities for the start and target vertices. Since each call performs $O(n)$ work we get a dynamic programming algorithm with time complexity $O(2^n \cdot n^2 \cdot n) = O(2^npoly(n))$.

The tricky part is the exponential amount of memory, since the cache used by dynamic programming might grow exponentially large. What do the hints suggest?
Problem 3.31 asked to solve Hamiltonian Path in $2^npoly(n)$ time, which could be done with the same idea I presented just now.
Problem 3.32 is more promising. It asked to show that the number of Hamiltonian paths from $s$ to $t$ can be computed in $2^npoly(n)$ time and $poly(n)$ space by evaluating the following expression:

$$\sum_{S\subseteq V}(-1)^{|S|}|q(S)|,$$

where $q(S)$ is the set of paths from $s$ to $t$ of length $n-1$ not visiting any vertex in $S$. ($|q(S)|$ can be computed relatively easily by iterating the adjacency matrix of $V\setminus S \quad n-1$ times.)
To prove this claim first observe that the number of Hamiltonian paths can be expressed like so:

$$|q(\emptyset)| - |\bigcup_{v_i}q(\{v_i\})|$$

which is the total number of paths minus the number of non-Hamiltonian paths, i.e. the paths not visiting some vertex $v_i$ (all of length $n-1$). Using the inclusion-exclusion-principle the second term can be rewritten as

$$|\bigcup_{v_i}q(\{v_i\})| = -\sum_{S\subseteq V\setminus \emptyset}(-1)^{|S|}|\bigcap_{v_i\in S}q(\{v_i\})|$$

Some further thought will then reveal the equivalence $q(A) \cap q(B) = q(A \cup B)$. (A path that avoids everything in $A$ and everything in $B$ also avoids everything in the union of $A$ and $B$. Similarly a path that avoids everything in $A$ or $B$ also avoids everything in $A$ and everything in $B$.)
With this our expression then becomes

$$|q(\emptyset)| + \sum_{S\subseteq V\setminus \emptyset}(-1)^{|S|}|q(S)| = \sum_{S\subseteq V}(-1)^{|S|}|q(S)|\qquad \Box$$

So how does this help finding the shortest traveling salesman tour? I see two options. Either use the algorithm laid out just now as a subroutine. Or reuse the ideas from the proof.
The first option seems pretty fruitless to me. Any instance of TSP that isn't defined on a fully connected graph can be converted to such an instance by adding in the missing edges with astronomically large weights. Counting the number of Hamiltonian paths on any subset $S$ of such a graph then becomes trivially easy. Every permutation of vertices is a Hamiltonian path so it's $|S|!$. Problem 3.32 seems of absolutely no help then.
The second approach breaks down because I can't find a way to fruitfully apply the inclusion-exclusion-principle. For that I'd need some sort of measure. But the one thing that suggests itself, the length of of the shortest traveling salesman tour on $S$, isn't one. $tsp(A \cup B) \neq tsp(A) + tsp(B)$ where $A \cap B = \emptyset$.


texts: What techniques can I use to hand-write a parser for an ambiguous grammar?

texts:
I'm writing a compiler, and I've built a recursive-descent parser to handle the syntax analysis. I'd like to enhance the type system to support functions as a valid variable type, but I'm building a statically typed language, and my desired syntax for a function type renders the grammar temporarily* ambiguous until resolved. I'd rather not use a parser generator, though I know that Elkhound would be an option. I know I can alter the grammar to make it parse within a fixed number of steps, but I'm more interested in how to implement this by hand.

I've made a number of attempts at figuring out the high-level control flow, but every time I do this I end up forgetting a dimension of complexity, and my parser becomes impossible to use and maintain.

There are two layers of ambiguity: a statement can be an expression, a variable definition, or a function declaration, and the function declaration can have a complex return type.

Grammar subset, demonstrating the ambiguity:

basetype
  : TYPE
  | IDENTIFIER
  ;

type
  : basetype
  | basetype parameter_list
  ;

arguments
  : arraytype IDENTIFIER
  | arraytype IDENTIFIER COMMA arguments
  ;

argument_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN arguments CLOSE_PAREN
  ;

parameters
  : arraytype
  | arraytype COMMA parameters
  ;

parameter_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN parameters CLOSE_PAREN
  ;

expressions
  : expression
  | expression COMMA expressions
  ;

expression_list
  : OPEN_PAREN CLOSE_PAREN
  | OPEN_PAREN expressions CLOSE_PAREN
  ;

// just a type that can be an array (this language does not support
// multidimensional arrays)
arraytype:
  : type
  | type OPEN_BRACKET CLOSE_BRACKET
  ;

block
  : OPEN_BRACE CLOSE_BRACE
  | OPEN_BRACE statements CLOSE_BRACE
  ;

function_expression
  : arraytype argument_list block
  | arraytype IDENTIFIER argument_list block
  ;

call_expression
  : expression expressions
  ;

index_expression
  : expression OPEN_BRACKET expression CLOSE_BRACKET
  ;

expression
  : function_expression
  | call_expression
  | index_expression
  | OPEN_PAREN expression CLOSE_PAREN
  ;

function_statement
  : arraytype IDENTIFIER argument_list block
  ;

define_clause
  : IDENTIFIER
  | IDENTIFIER ASSIGN expression
  ;

define_chain
  : define_clause
  | define_clause COMMA define_chain
  ;

define_statement
  : arraytype define_chain
  ;

statement
  : function_statement
  | define_statement SEMICOLON
  | expression SEMICOLON
  ;

statements
  :
  | statement statements
  ;

Example parses:

// function 'fn' returns a reference to a void, parameterless function
void() fn() {}
// the parser doesn't know which of these are types and which are variables,
// so it doesn't know until the end that this is a call_expression
Object(var, var, var, var)
// the parser only finds out at the end that this is a function declaration
Object(var, var, var, var) fn2() {}
(Object(var, var, var, var) ())
(Object(var, var, var, var) () {})
// the parser could possibly detect the "string" type and figure out that
// this has to be a define statement or a function declaration, but it's
// still ambiguous to the end
Object(Object(string, Object), string[]) fn3() {}
Object(Object(string, Object), string[]) fn4 = fn3;

My basic approach has been to write functions that could parse the unambiguous components of this subset of the grammar, and then flatten the more complex control flow into individual functional blocks to capture state in function calls. This has proved unsuccessful, what techniques can one use to solve this kind of problem?

*There is likely a better word for this


texts: sort array with some of the elements in a known range

texts:
Let $A$ be an array of n elements. We know that $n - \lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$ (the other $\lfloor \sqrt n \rfloor$ elements may or may not be in the range). I need to sort the array in $\Theta (n)$.
I thought of partitioning the array to 3 subarray:

elements smaller than $\sqrt n$
element in range $\sqrt n$ to $n\sqrt n$
element bigger than $n\sqrt n$

the first and last subarrays can be sorted with insertion sort in $O(n)$ because there are at most $\lfloor \sqrt n \rfloor$ elements in those arrays. The second array have between $n - \lfloor \sqrt n \rfloor$ to $n$ elements in range $\sqrt n$ to $n\sqrt n$ so using counting sort will run in $O(n\sqrt n)$. Using bucket sort where each bucket has all the elements in subrange with n integers each bucket can be sorted with counting sort in O(n) and  there are $\sqrt n$ buckets so the sort will also take $O(n\sqrt n)$.
My problem is how to sort that second array in $O(n)$? I assume it is something to do with the amount of buckets or maybe the subrange of each bucket, as sorting the second array costs $O(number\_ of\_buckets * O(number\_of\_elements\_in\_bucket + number\_of\_integers\_in\_range))$


texts: Longest processing time rule on unrelated machines

texts:
I am trying to solve the job secheduling problem using the Longest processing time rule, that is: We seek to minimize the makespan by first sorting the jobs in decreasing order of processing time, then the algorithm makes one pass through the jobs in any order; when it comes to job $j$, it assigns $j$ to the machine whose load is smallest so far.

When the machines are idential, this is a $\frac{3}{2}$-approximation algorithm. But how about when the machines have different speeds? Let's say for example that we have 2 machines, one machine has speed 1 and the other one has seep 2. How would we calculate the lower bounds for this algorithm?

What I tried:

If we have less or equal jobs than machines, then $OPT \geq \frac{1}{2}max_j p_j$ (where $p_j$ is the processing times of a job).
If we have more jobs than machines, then $OPT \geq p_j$

But this yields a 3-approximation algorithm if we sum the inequalities. Is this correct?


texts:
Input : An matrix $A$, whose entries are from $\mathbb{Z}$ (set of integers)

Output: det A (determinant of matrix A)

Question : Suppose we are solving this problem over $\mathbb{Q}$ using gaussian elimination, what could be the size of numerators and denominators of the intermediate results?

Gaussian elimination: By doing row elementary operations we will getting upper triangular matrix $U$, so $A = P_1\times P_2 \times P_2 ..P_k U$, where each $P_i$ is a permuatation matrix.

Please note that there efficient methods for the computation of determinant like modular determinant computation etc, but I want to compute with the method described above.


texts: How to find nearest number in a sequence that is strictly smaller than given number

texts: Given a sequence of numbers $l_1, \ldots, l_k$, I want to find for each $i$ the nearest numbers to the left and right of $l_i$ (if any) that are strictly smaller than $l_i$. Is it possible to do this in linear time?


texts: Machine Learning to draw a topology of elements

texts:
I'm exploring the idea of using machine learning to draw a topology of elements. For example, imagine a tree representing geological hierarchy (country -> province -> city). All countries are at the top-most level, then the provinces for each country, followed by the provinces splitting into cities at the 3rd vertical level.
The vertical positions of the elements are trivial to compute:

Country ->  0 %
Province -> 33%
City -> 66%

in a canvas going vertically down as the % increases.
However, I'm having trouble thinking of how to format the data to determine the horizontal position. I'm aware that there are non-ml algorithms to draw topologies, but I'm exploring this as a proof of concept.
My plan right now is to assign each element id,parentId,rank properties where

id is a unique id
parentId is the id of the parent element
rank is 1/2/3

However, I feel like this isn't the best way to represent the data to feed into the ml model.
I'm welcome to any guidance/recommendations on how to better represent the problem.


texts: If base 2 looks like a square wave, and base 3 looks like this, what does base e look like?

texts:
In computing, base 2 is a 0 and a 1 / on and off in a transistor. Base 3 is -1, 0 and 1.

Electronically/in computing how would/could base e be represented visually?


texts: Reviews of work in the field of partial evaluation (post 1993)

texts:
I'm looking for relatively new reviews of research work on partial evaluation. The most recent work I've found is "Tutorial notes on partial evaluation" by Charles Consel and Olivier Danvy (1993). The book Partial Evaluation and Automatic Program Generation (1993) also gives a comprehensive overview of the work in this field.

In particular, I want to write a brief overview of the history of this field of research. And with the sources I've found so far, I only have enough to write about it up to the early 90s.

Terminology: In the literature, other more-or-less interchangeable terms are sometimes used instead of "partial evaluation". Like "mixed computation" (introduced by A.P. Ershov) and, as Respawned Fluff has mentioned, "program specialization". "Partial deduction" seems to be used in the context of partial evaluation applied to logic programming.


texts: Bounded waiting and starvation free in critical section problem

texts:
i have 4  question regarding relation between starvation and bounded waiting.

1.Does starvation-freedom imply deadlock-freedom?

My Answer-:

From here,

definition of starvation free is

  Freedom from Starvation -:Every thread that attempts to acquire the lock eventually succeeds

  Freedom from Deadlock -:f some thread attempts to acquire the lock, then some thread (not necessarily the thread referred to in the if statement; emphasis added) will succeed in acquiring the lock.

so i can state that starvation-freedom imply deadlock-freedom

2.Does starvation-freedom imply bounded-waiting?

Approach-:

  Starvation free implies  that every thread that will attempt to acquire lock will succeed.

on the other hand

  bounded wait insures that  there exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections
  after a process has made request to enter its critical section and before that request is granted

which implies that there must not be any starvation.

Am i correct? but the explanation is  here confuses me.

Please help me out !!

Thanks!!!


texts: We know $L^+=L^\star\backslash\{\epsilon\}$. How do we interpret that $\{\epsilon\}^+=\{\epsilon\}$?


texts:
Consider this problem:

$\qquad\displaystyle \mathsf{FPATH} = \{\langle G, a_1,\dots,a_n\rangle \mid G \text{ is a digraph with directed path } (a_1,\dots,a_n)\}$

It's allowed to visit nodes outside the sequence, but a1 must be visited before a2 and so on.

I am having big trouble trying to show that this language is NL-complete. I have tried finding an algorithm for a TM that decides this problem in NSPACE(log n), but I can't seem to find a good solution. I know that PATH is NL-complete, so I guess I can use that fact. My problem is finding an algorithm that somehow has to know that is has been through the sequence $a_1$ to $a_n$, but how can I do this when the worktape only can use $\log n$ space?


texts: Are EAX , EBX registers 64 bit in length in modern processors

texts: The EAX, EBX and ECX registers on a cpu are they 64 bits for a 64-bit cpu ?


texts: Why doesn't $O(1)+O(2)+\cdots+O(n)$ have an interpretation?

texts:
In CLRS (on pages 49-50), what is the meaning of the following statement:

  $\Sigma_{i=1}^{n} O(i)$ is only a single anonymous function (of $i$), but is not the same as $O(1)+O(2)+\cdots+O(n)$, which doesn't really have an interpretation."


texts: How can a distributed system cooperate to determine rules of its environment?

texts:
I'm sorry if this question is silly or elementary. I'm not a computer scientist so I don't know the vocabulary to use to ask this question. Thus I've produced an analogy to explain the challenges I'm facing in my program. Please do point me in the right direction, I don't know what I need to learn to solve this problem:

An Analogous Puzzle:

Assume you are given a new house with 4 rooms. But this house is very strange; each room has 1-3 lights in it and 1-3 light switches. Some diabolical electrician has wired the house very strangely so that the switches can control lights in other rooms of the house. Furthermore, the behavior of the lights and switches may depend which lights are on at the time.

For instance a switch in room 1 may turn on on a light in room 2 if a light in room 4 is off, but it won't if room 4 is lit up. Almost all the light switches have a very strange relationship to some of or all of the other lights in this way. But they're not random, in their behavior: given the same state of the house a light switch will have the same effect as it did.

Now imagine you and 3 friends each occupy a room and are able to do one action in the house at a time. You can talk to each other by calling or texting each other on your cell phones, but every minute costs money, or every text costs money so you want to communicate as little as possible (thus you want to be efficient).

What I need to figure out is the answer to the following question:

How do you and your 3 friends need to communicate (what information do you need to share with each other) in order for the 4 of you to work together to deduce the wiring rules that govern the lights?

Does each person need to know the state of each room? Or do they only need to know the state of each room when something unexpected happens? How do they deduce the rules that govern the lights?

I need to find a universal way for the agents to infer the rules underlying the system efficiently. That's basically it.

In a more complicated scenario (thousands or millions of rooms), does anything change? What do I need to learn to solve this puzzle in a way that scales?

One other consideration: if necessary for a scalable algorithm you can recruit other friends from outside the house and give them information. I'm not sure why you would need to, but that's also a possibility.

That is the puzzle I have: many agents, mainly identical and independent are interacting with the same system.

I need to find an algorithm of cooperation/communication that results in the system as a whole, or each individual agent to infer/deduce (or even just behave in accordance with) the underly rules of the environment.


texts:
Say I have an image, represented as a 2D array of pixel values. Also, say I have a set of points on that image where each has a current (x, y) position and a Destination (x, y) associated with it. I want to find a path for each point to its Destination so that the points do not collide with each other in (x, y, t) where t is time.

Imagine dots moving continuously across a screen so that they go to their respective destinations and do not hit into each other. The paths do not need to be the shortest paths.

How do people recommend going about this problem? I have heard the options of an A* search and running a simulation, where dots feel a "repulsive force" when they become too close to each other. Thanks!


texts: Finding an MST with one adding and removing vertex operation

texts:
I am facing the following problem: Given an undirected complete Euclidean weighted graph $G(V, E)$ and its MST $T$. I need to remove an arbitrary vertex $v_i \in V(G)$, and given a vertex $v_j \notin V(G)$, I have to calculate the MST of $$G^{'}((V(G) \backslash \{v_i\})\cup\{v_j\}, (E\backslash\{(v_i, v_k): v_k \in V(G)\})\cup\{(v_k, v_j): v_k \in V(G^{'})\}),$$ i.e, the graph $G$ with the vertex $v_j$ (and edges from $v_j$ to every other vertex) and without the vertex $v_i$ (and its respective edges). To solve this, we can apply some well-known MST algorithms, such as Prim's, Kruskal's, Borukva's algorithm. Neverthless, if we do this we would not use the already existing MST $T$, i.e., we would calculate a new whole MST. So, I would like to know if there is any way to reuse the existing MST $T$.
There are two similar questions to this here (with edges, considering only the removing of them), and here (with vertex, considering only the adding of them).
The vertices are points in $\mathbb{R}^2$, and the weight on each edge is the Euclidean distance between the two points.


texts: about the complexity of recursive sequence

texts:
If i have a recursive sequence $a_1=4$ and $a_{n}=a_{n-1}^{2}-2$ in $\mathbb{Z}_{M_{n}}$ where $M_n=2^n-1$

how i can calculate the complexity time of this sequence ? if we put it in the loop for n-1 iteration .

pseudocode :

S=4;
i=2;

While($i<n$,

$S=S^2-2 (\mod M_n)$

If( S==0  then Break[]);

);

im not sure that overall complexity is $O(log^3(M_n))$


texts: Loop-local variable in Cytron's SSA algorithm

texts:
I am trying to write a compiler that converts a simple imperative language to SSA form, but I am having trouble with loops. As an example, I have some code that looks like:

fun count() {
    i = 0;
    while(i < 10) {
        x = i + 1
        i = x;
    }
    return i;
}

I then convert it to a control flow graph that looks like this:

0 ->
    predecessors                = []
    successors                  = [1,2]
    dominators                  = [0]
    strict dominators           = []
    dominatees                  = [0,1,2]
    dominance frontier          = []
    inverse dominance frontier  = []
    immediate dominator         = none
    immediate dominatees        = [1,2]
    instructions                =
        r := 0
        i := 0
        if i >= 10 goto 2 else goto 1

1 ->
    predecessors                = [0,1]
    successors                  = [1,2]
    dominators                  = [0,1]
    strict dominators           = [0]
    dominatees                  = [1]
    dominance frontier          = [1,2]
    inverse dominance frontier  = [1]
    immediate dominator         = 0
    immediate dominatees        = []
    instructions                =
        x := i + 1
        i := x
        if i < 10 goto 1 else goto 2

2 ->
    predecessors                = [0,1]
    successors                  = []
    dominators                  = [0,2]
    strict dominators           = [0]
    dominatees                  = [2]
    dominance frontier          = []
    inverse dominance frontier  = [1]
    immediate dominator         = 0
    immediate dominatees        = []
    instructions                =
        r := i
        ret

The issue I'm running into is that when I use the algorithm for placing phi nodes described in section 5.1 of Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, I get something like this:

0 ->
    predecessors                = []
    successors                  = [1,2]
    ...
    instructions                =
        r := 0
        i := 0
        if i >= 10 goto 2 else goto 1

1 ->
    predecessors                = [0,1]
    successors                  = [1,2]
    ...
    instructions                =
        x := phi(x, x)
        i := phi(i, i)
        x := i + 1
        i := x
        if i < 10 goto 1 else goto 2

2 ->
    predecessors                = [0,1]
    successors                  = []
    ...
    instructions                =
        x := phi(x, x)
        i := phi(i, i)
        r := i
        ret

I understand why a phi is necessary for i in basic block #1 and #2, but I don't understand why phis are necessary for x, and in fact they seem to break the renaming algorithm that follows (specifically, at one point where the renaming algorithm tries to pop off the S("x") stack, that stack is empty, because x was not assigned to in basic block #0). Did I somehow incorrectly implement this algorithm, or is there some subtlety I'm not understanding?


texts: Is an inﬁnite union of context-free languages always context-free?

texts:
Let $L_1$, $L_2$, $L_3$, $\dots$ be an inﬁnite sequence of context-free languages, each of
which is deﬁned over a common alphabet $Σ$. Let $L$ be the inﬁnite union of $L_1$, $L_2$, $L_3$, $\dots $;
i.e., $L = L_1 \cup L_2 \cup L_3 \cup \dots $.

Is it always the case that $L$ is a context-free language?


texts: Computer networks - Can there be an out of order frames in a noiseless channel?

texts:
In a noiseless channel can frames in the 2 layer of OSI model(Data link layer) reach to the destination out of order?
*I am studying from Computer networks 5 Edition of Andrew S. Tanenbaum


texts: Macros vs lazy evaluation in scheme inspired language

texts:
I'm writing a simple scheme inspired interpreter. I'm not calling it a scheme implementation because I don't really want to implement all the standard, only the minimal set of primitives needed to keep evolving it from it self.
I have two primitives lambda and lazy, lazy is a lazy version of lambda in the sense that it receives its arguments unevaluated and it can chooses on what evaluate
Here are both as examples:
(define foo (lambda (x) (+ 1 x)))

(define foo (lazy (x) (+ 1 (eval x))))

The idea to have lazy is not needing macros (at last in the core language, I may implement it afterwards on top of lazy).
My question is, given lazy do I need macros/hygienic at all? Isn't this primitive a lot clearer than macros? What kind of macros I can't define on top of lazy and why?


texts: If modern computers aren't actually Turing-complete, does that mean that it is possible to determine if a program run on such a computer halts?

texts:
The halting problem says that it is impossible to create a general algorithm which can for all inputs and programs determine whether they halt. However, this assumes that the programs and/or the things running them are Turing-complete.

Since all computers have a finite amount of memory and are therefor not Turing-complete, does that mean that the halting problem does not apply to a program run on a machine with finite memory?


texts: In regards to CPU instructions, why is the result of an operation stored in the source register?

texts:
Specifically when it comes to R-Type instructions, the format is

  operand, sR1, sR2, dR

where sR1, sR2 are source registers and dR is the destination register.

What I don't understand is why the operation

  ADD, R1, R2, R3

results in the sum of R2 and R3 being stored in R1. If R1 and R2 are the 'source registers' then shouldn't the sum of R1 and R2 be stored in R3, the destination register?


texts: How to prove T Z = Z for binary representation of natural numbers in Coq

texts:
I have defined an Inductive in Coq for binary representation of natural numbers as follows:

Inductive bin : Type :=
  | Z : bin
  | T : bin -> bin
  | M : bin -> bin.

and two recursive functions to convert between nat and bin types as:

Fixpoint nat_to_bin (n : nat) : bin :=
  match n with
    | O => Z
    | S n' => incr (nat_to_bin n')
  end.

and

Fixpoint bin_to_nat (b : bin) : nat :=
  match b with
    | Z => O
    | M b' => S (mult 2 (bin_to_nat b'))
    | T b' => mult 2 (bin_to_nat b')
  end.

to show that bin_to_nat is the inverse of nat_to_bin I need to prove that T Z = Z by using these tactics that I know: simpl reflexivity destruct rewrite replace induction please recommend some clues showing how to do this. Thank you!

Edit

The incr implementation is

Fixpoint incr (b : bin) : bin :=
  match b with
    | Z => M Z
    | T b' => M b'
    | M b' => T (incr b')
  end.


texts: O(1) space, O(N) complexity algorithm for buy and sell stock twice interview question

texts:
Question:  Given a time series of stock prices, what is the maximum profit you can make if you are allowed to Buy and sell the stock twice.  The second buy has to come after first sell.

Solution:  There is a O(N) time and O(N) space complexity solution, that keeps track of the maximum profit that can be made when selling at day i in a N size array.  Then it calculates the max profit by using this array in conjunction with max profit that can be made by buying at day i+1.

I would appreciate any hints on how I can get a O(N) time and O(1) space complexity solution?


texts: Corresponding noun for "side-effect-free"?

texts:
For functions or computations we have terms like:

Deterministic – Determinism
Pure – Purity

Now what is the correct corresponding noun for side-effect-free?

"Side-effect freeness"? "Side-effect freedom"? "Non-side-effective"?


texts: How to use homomophism in closure proofs?

texts:
I am having a hard time understanding homomorphism. All I seem to understand is that it is a substitution. When I look at examples of proving closure of a particular operation over a regular language, I don't understand how people come up with the substitution strings that they choose, and how they use them to produce a regular expression. Getting from the starting language to the final regular expression bewilders me.

For example, the following closure proof of an operation 'Quotient' written $L/R$, where $L$ and $R$ are regular languages:

$L/R = \{ x \mid \exists ~y \in R, \text{ where } xy \in L \}$
Define $\Sigma' = \{a' \mid a \in \Sigma\}$
Let $h(a) = a$
Let $h(a') = \lambda$
Let $g(a) = a'$
Let $f(a) = \{a, a'\}$
Then $L/R = h(f(L) ~\cap~ (\Sigma^* \cdot g(R)))$

What is the $a'$? Just another symbol? Why is that useful?
I don't understand the $f(a)$.
I don't understand what concatenating with $\Sigma^*$ yields.
I really don't understand much of it...

Can someone explain this to me in English, so I can better understand how to approach closure proofs of other operations?


texts: Equivalence of NFA and DFA - proof by construction

texts:
I was looking at the construction proof showing the equivalence of NFA and DFA from Sipser's text. It started by taking number of states of DFA as $\mathcal{P}(Q)$, where $\mathcal{P}(Q)$ is the set of subsets of $Q$.

My doubt is when we construct DFA from NFA, all the subsets may not occur in that DFA. So how could we write that the number of states of DFA constructed is $\mathcal{P}(Q)$.


texts: Theta Manipulation to show $N = \Theta(n/\log N)=\Theta(n/\log n)$

texts:
I am studying different models of computation and how algorithms can be interpreted under different models.

Here is a math(?) question that has been bugging me.

Suppose we have $n = \Theta(N\log N)$ bits as the size of input and there are N elements in the input. (The implied assumption is each element has $\Theta(\log N)$ bits).

Now we know Insertion Sort has running time of $\Theta(N^2)$ in the worst case with respect to N, the number of elements in the input.

Under the RAM model, the input is $n = \Theta(N\log N)$ bits. So we can say $N = \Theta\left(\frac{n}{\log N}\right)$. I want to show that the running time $T = \Theta\left(\frac{n^2}{\log^2n}\right)$ by first showing that $N = \Theta\left(\frac{n}{\log n}\right)$.

Since $N \leq n$, $N = \Theta\left(\frac{n}{\log N}\right)=\Omega\left(\frac{n}{\log n}\right)$. I am having trouble showing $ N = \Theta\left(\frac{n}{\log N}\right)= O\left(\frac{n}{\log n}\right)$ to be able to use the $\Theta$ notation.

In general, I am not so sure what kind of manipulations are allowed inside $\Theta$ so that its definition is intact.


texts: Comparison Based Sorting Run-time with respect to Total Number of Bits of Input

texts:
Comparison-based sorting algorithms are lower bounded by $\Omega(nlogn)$, where $n$ is the number of elements in the input list.

However, when dealing with different models of computation, such as algorithms that deal with arithmetic operations (Euclid-GCD) or, $n$, the size of the input, is no longer the number of elements but the total number of bits required to represent the input. In these cases, time complexity is measured as the number of bit operations needed with respect to the total number of bits in the input.

Looking at the post What Is Pseudo-Polynomial Time How Does It Differ From Polynomial Time?

Polynomial time is defined as:

  An algorithm runs in polynomial time if its runtime is O(xk) for some constant k, where x denotes the number of bits of input given to the algorithm.

Pseudo-polynomail time is defined as:

  An algorithm runs in pseudo-polynomial time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.

Looking at How Can We Assume That Basic Operations on Numbers Take Constant Time?

For word size $w = \theta(logn)$, standard arithmetic operations on these words take $O(1)$ time, by definition.

With these definitions in mind, I have trouble seeing how some comparison-based sorting algorithms are polynomial time with respect to both $n$, the number of elements in the input, and $x$, the total number of bits in the input; the first post I referenced makes this claim.

Why they are polynomial with respect to $n$ is pretty obvious, so I will only look at the bit representation of input $x$ for comparison-based sorting algorithms with 2 different time complexities.

Merge or Quick Sort on a List of $n$ Elements

We need $w = \theta(logn)$, as defined in CLRS, since we at least need to be able to index into an array of size $n$. Assuming all elements fit in a word, which I think is a reasonable assumption here, $x = wn = \Theta(nlogn)$. Please let me know if my $x$ is wrong!!!

Since the running time was $O(nlogn)$, the time complexity with respect to $x$ is $O(x)$. I will interpret this as meaning we need a linear number of operations on the total number of bits needed to represent this input list.

Selection Sort on a List of $n$ Elements:

I will assume the same $x = wn = \Theta(nlogn)$ for the input size. The running time is $O(n^2)$. Here I need some help: how do I write the running time cleanly in terms of $x$, like I did for Merge/Quick Sort above? The first post I referenced just used $w = 32$ bits and easily got $O(x^2)$ polynomial time but this doesn't seem right to me, since the [second post] I referenced (How can we assume that basic operations on numbers take constant time?) and CLRS stressed $w$ is not a constant but $\Theta(logn)$.

I have a similar question for counting sort, that has not been answered yet.. the first post I referenced claims it is exponential with respect to $x$ without the $k = \Theta(n)$ condition when $x = \Theta(nlogk)$ bits, but I have trouble changing from $O(n + k)$ in terms of $x$. Please help!!


texts:
According to Wikipedia:

  ...metaheuristic is a higher-level procedure or heuristic designed to
  find, generate, or select a lower-level procedure or heuristic
  (partial search algorithm) that may provide a sufficiently good
  solution to an optimization problem...

So a metaheuristic is something like a shaman (master algorithm), who tries to heal a person (solve a mathematical problem) by mixing various spells and herbs (simple heuristics). But why is Evolutionary computation considered a metaheuristic, instead of a simple heuristic:

https://en.wikipedia.org/wiki/Metaheuristic#/media/File:Metaheuristics_classification.svg

What are the simple heuristics that evolutionary computation is composed of? Is it the crossover, mutation, fitness based selection? Are these the simple heuristics?

Also related: Difference between heuristic and approximation algorithm?


texts: Prove the equality of two concatenations of words

texts:
Let $x$, $u$, $v$, $w$, $y$, $x'$, $u'$, $v'$, $w'$, $y'$ be words. If

$y'x' = xy$
$y'u'x' = xuy$
$y'v'x' = xvy$
$y'w'x' = xwy$
$y'v'u'x' = xuvy$
$y'w'v'x' = xvwy$

all hold, then I need to prove that $y'w'v'u'x' = xuvwy$.

I'm a little confused how to prove this, How can I form $y'w'v'u'x'$ from the equations above?


texts:
I try to figure out a redundant power of two-sided error randomized Karp - reduction.

It's well known fact and it is relatively hard to show that BPP is reducible by a one-sided error randomized Karp-reduction to coRP (in case of promise problem).

Without delving into details it make sense that the combination of the one - sided error probability of the reduction and the one-sided error probability of coRP leads to two-sided error probability of BPP. Of course the proof of that is not so intuitive.

The question it is possible by two-sided error randomized Karp-reduction to reduce BPP to some constant set in P? In the light of the power of one - sided randomized Karp - reduction, it make sense that two-sided randomized Karp - reduction is strong enough to reduce BPP to constant set, but how to show it formally?

Addendum:

BPP is the set of the problems that is solvable in polynomial time by two-sided error randomized algorithm, so as a result of two - sided error randomized algorithm we will get some output, them the problem in BPP can be reduced to problem P by two-sided error randomized Karp - reduction in sense that reduction is allowed to make error on both sides. Does it mean that two - sided error randomized reduction will justify the two-sided error that was made by the algorithm in solving the problem in BPP?


texts: Lower bound on online range minimum query with element value modification

texts:
Is there a known lower bound to the online Range Minimum Query (RMQ) problem with value modifications (given the array we perform online RMQ on, support dynamically modifying the values of a given element in the array)?

The Wikipedia page on range minimum queries cites the $O(n)$ preprocessing, $O(1)$ query-time algorithm for performing online RMQs on an immutable array by Farach-Colton and Bender, which they prove to be optimal.

There's also a folklore algorithm on using segment trees (or tournament trees in formal literature, see 1): https://cp-algorithms.com/data_structures/segment_tree.html. They support query, single-element value modifications, and range modifications in $O(\log n)$, while taking $O(n)$ preprocessing time.

I'm curious if there are any literature mentioning a lower bound to online RMQ with single-element value modifications and range modifications? Alternatively, are there any known efficient algorithms if we extend this problem to add element insertion/deletion?

To formalize the problem statement a bit, is there a known optimal  algorithm supporting the following online queries on an array $A$ with length $n$:

$RMQ(l,r)$ return the range minimum in A[l...r]

$Add(i,x)$ Add $x$ to $A[i]$

$AddRange(l,r,x)$ add $x$ to A[l..r] inclusive

If there's no known optimal algorithm, is there a lower bound?


texts: Constructing a promise problem equivalent to XSAT from subset sum

texts:
Consider $\Pi$ to be the problem to decide if there is a subset of numbers that sum to $0$ in the given list of integers.

How does one construct a promise problem equivalent to $xSAT$ from this? $xSAT$ is in $NP\cap coNP$.

How is it possible that the original problem was NP complete and the transformed problem is in coNP?

Doesn't this mean NO instances also have short certificates for the original problem $\Pi$?


texts: Finding maximal cardinal independent set given oracle

texts: The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the oracle. My attempt has been that first finding the maximal possible size and then try to find the set of that size by removing vertices one at a time. I understand for a given node it either has to be in or not in the set, then I noticed that that there are multiple overlaps between chain of removals and I could devise a DP algorithm of sorts. But I'm just really stuck after that and was wondering if any hint could be given.


texts: Is there any nongeneral CFG parsing algorithm that recognises EPAL?

texts:
EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar:

$S \rightarrow a a$
$S \rightarrow b b$
$S \rightarrow a S a$
$S \rightarrow b S b$

EPAL is the 'bane' of many parsing algorithms: I have yet to encounter any parsing algorithm for unambiguous CFGs that can parse any grammar describing the language. It is often used to show that there are unambiguous CFGs that cannot be parsed by a particular parser. This inspired my question:

Is there some parsing algorithm accepting only unambiguous CFGs that works on EPAL?

Of course, one can design an ad-hoc two-pass parser for the grammar that parses the language in linear time. I'm interested in parsing methods that have not been designed specifically with EPAL in mind.


texts: Proof that $\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ is not (co-)recursively enumerable

texts:
I would like to use your help with the following problem:

$L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$. Show that $L \notin RE \cup  CoRE$.

I know that to prove $L\notin RE$, it is enough to find a language $L'$ such that $L'\notin RE$ and show that there is a reduction from $L'$ to $L$ $(L'\leq _M L)$.

I started to think of languages which I already know that they are not in $RE$, and I know that $Halt^* =\{⟨M⟩ ∣ M\mbox{ halts for every input} \} \notin RE$. I thought of this reduction from $Halt^*$ to $L$: $f(⟨M⟩)=(M')$. for every $⟨M⟩$: if $M$ halts for every input  $L(M')=0^n1^n$ otherwise it would be $o^n1^n0^n$, but this is not correct, Isn't it? How can I check that $M$ halts for every input to begin with? and- is this the way to do that?


texts: i just signed up here because im struggling very hard with a problem i gotta solve. What I wanna do is reducing an Instance of 3color to an instance of Quadprog to prove that quadprog is np-hard, and i have no idea how to do that. My first idea was to match every node to a varaible of quadprog, but i have no clue how to continue. Maybe anyone here knows how to help me?


texts: Intersection of two deterministic parity automata

texts:
Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the transition function $\delta_i : Q_i \times \Sigma \rightarrow Q_i$, the initial state $q_{0i}$ in $Q_i$, and the coloring function $c_i : Q_i \rightarrow \mathbb{N}$, with $i \in\{0,1\}$.

How is the intersection of two deterministic parity automata formally defined? In particular, how are the coloring functions combined?


texts:
A couple homework problems that I've been working on, hoping I can get it done right. Can anyone confirm if my line of reasoning and regex is correct?

L = { $w \in $ {$x, y$}* | $w$ contains a maximum one instance of $xx$ }

My answer $$ ((y^*+x)^2)y^*$$

This ticks off $y, x, xx, yx, xy, yyy$, but won't allow more than one $xx$. Only issue I could find is that it doesn't allow $yxyxy$ and the like. Any tips on how to overcome this on a larger scale? Don't know if $$ (((y^*+x)^2)y^*)^*$$ is cheating, also considering that you can have $xxxx$ from that Thoughts?

L = { $w \in $ {$0, 1$}* | $w$ does not have any instances of $011$ }

My answer

$$(0^*1)^* + 1^*0^*$$

This allows $0, 01, 1, 10, 001$, etc. The only issue I seem to find is that it does not allow $00101$. Almost the same issue as last one, any ideas on how to overcome these?


texts: What is the difference between distributed representations and factors of variation in deep learning

texts:
In the field of deep learning, people often talk about factors of variation which, in my understanding (in terms of dimensionality reduction), are the latent variable directions capturing variability in the data. I also often come across the term distributed representations which are basically the features of the input data that are not mutually exclusive.

Sometimes for object recognition, one may wish to extract distributed features of the object that are invariant to small variations (which are a result of combination of many factors of variation).

On the other hand, in case of autoencoder, one needs to extract the factors of variation as completely as possible so as to minimize the reconstruction error.

In the above two cases, factors of variation seem to have two contradicting roles, nevertheless they are both referred to as useful features for intermediate layers of a deep architecture.

So what is the difference between factors of variation and distributed features? I am very confused.


texts: How can I prove the following problem is NP?

texts:
Because of the covid-19 pandemic, our firm works semi-remote working. We want to that:

Every day 2/5 of staff should be in the office.
Everyone should go to the office 2 times a week.
Teams want to go to the office together. But teams are not very strict. Some people are in 2 teams. So there may be no best solution for everyone.
Some people should be in the office some specific day of the week.

I believe that the problem is NP-hard because I can't check if some scheduling is the best scheduling in polynomial time.
But I am not sure. Is it NP-hard, NP-complete, or just a P? How can it be proven without any doubt?


texts: How do you determine the number of errors in the Welch-Berlekamp algorithm?

texts:
In the Welch-Berlekamp algorithm for decoding Reed-Solomon codes, one is given a list of points $(a_i, b_i)$ representing a message with $e$ errors on the $b_i$ in unknown locations (and $e$ is given to the algorithm). The output is a polynomial passing through all of the given points except those in which errors occurred.

The method involves solving a system of linear equations of the form

$$b_i E(a_i) = Q(a_i)$$

for all $i$ where $E$ has degree $e$ and $Q$ has degree at most $e+k$. The variables are the coefficients of $E$ and $Q$.

To ensure that $E$ has degree $e$ one usually adds the constraint that the coefficient of $x^e$ is 1 to the linear system above. However, in practice one doesn't necessarily know $e$. One inefficient (but still polynomial time) way to deal with this is to try $e$ for all values starting with $(n+k-1)/2 - 1$ going down until a solution is found.

My question is: is there a more efficient way to determine $e$? Alternatively, is there a modification to the linear system that allows one to use an upper bound on $e$ instead of the exact value?

In particular I want to use this specific decoder for Reed-Solomon codes, and not a completely different algorithm based on other techniques.

In response to DW's answer, here is my working example. Everything is done modulo 7.

plain message is: [2, 3, 2]
polynomial is: 2 + 3 t^1 + 2 t^2
encoded message is: [[0, 2], [1, 0], [2, 2], [3, 1], [4, 4]]
corrupted message is: [[0, 2], [1, 0], [2, 3], [3, 1], [4, 4]]

So the error is in the third point.

When $e=2$ the polynomial equation in question is

$$b_i(e_0 + e_1x + e_2x^2) - q_0 - q_1x - q_2 x^2 - q_3x^3 - q_4x^4 = 0$$

And plugging in $x = 0,1,2,3,4$ gives the system in matrix form:

[2, 0, 0, 6, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 6, 6, 6, 6, 0]
[3, 6, 5, 6, 5, 3, 6, 5, 0]
[1, 3, 2, 6, 4, 5, 1, 3, 0]
[4, 2, 1, 6, 3, 5, 6, 3, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 1]

The last row is the constraint that $e_2 = 1$. Applying Gaussian elimination we get

[1, 0, 0, 0, 0, 0, 1, 4, 0]
[0, 1, 0, 0, 0, 0, 3, 3, 1]
[0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 2, 1, 0]
[0, 0, 0, 0, 1, 0, 2, 2, 5]
[0, 0, 0, 0, 0, 1, 4, 5, 2]

And picking 1 for both free variables we get a solution vector of

[2, 2, 1, 4, 1, 0, 1, 1]

Which translates to

E is 2 + 2 t^1 + 1 t^2
Q is 4 + 1 t^1 + 0 t^2 + 1 t^3 + 1 t^4

And $E$ does not divide $Q$. Note that $Q$ factors as $(t + 6) (t^3 + 2t^2 + 2t + 3) \mod 7$

For $e=1$ I get a good solution:

system is:
[2, 0, 6, 0, 0, 0, 0]
[0, 0, 6, 6, 6, 6, 0]
[3, 6, 6, 5, 3, 6, 0]
[1, 3, 6, 4, 5, 1, 0]
[4, 2, 6, 3, 5, 6, 0]
[0, 1, 0, 0, 0, 0, 1]

reduced system is:

[1, 0, 0, 0, 0, 0, 5]
[0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 3]
[0, 0, 0, 1, 0, 0, 3]
[0, 0, 0, 0, 1, 0, 6]
[0, 0, 0, 0, 0, 1, 2]

solution is [5, 1, 3, 3, 6, 2]
Q is 3 + 3 t^1 + 6 t^2 + 2 t^3
E is 5 + 1 t^1
P(x) = 2 + 3 t^1 + 2 t^2 # this is correct!
r(x) = 0

Note that while the counterexample above was generated by code I wrote from scratch (it was basically the first thing I tried), one can check the solutions are valid by hand, so even if my code is buggy it's still a valid counterexample to the claim that using $e=2$ works.


texts: Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?

texts:
I was under the impression that our computers, being finite, are ultimately no more powerful than (extraordinarily large) Finite State Machines.  However, Linearly Bounded Turing Machines are also finite, but it seems that Regular Languages are strictly an improper subset of Context-Sensitive Languages.

Obviously, I'm missing something here.  What is going on?


texts: Data Structure for storing the Sweep Line Status in Sweep Line Algorithms

texts:
I have been looking into the sweep line algorithms of finding intersection of line segments and polygon partitioning using monotone polygons. The algorithms require a dynamically balanced binary tree which stores the sorted sequence of the elements in the leaves of the tree.

I am familiar with Balanced Binary trees like AVL trees where the elements are stored in the inner leaves too. I am confused on how to implement such a data structure which only stores the data in the leaves and uses the inner nodes as splitter nodes.

Please explain the data structure for storing the data in the leaves and it is helpful if any reference links are given.

Thank you.


texts: What are the most expressive, terminating languages?

texts:
I'm less interested in languages where you can write almost anything, but then are required to write an accompanying proof that what you wrote terminates.

I'm more interested in the design space of languages inherently confined to certain complexity classes by construction.

Is there any sort of theory hierarchy for sub-turing-complete languages?


texts: Examples of Regular, Context-free and Context-sensitive languages

texts:
Assume the languages:

$$
a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \}
$$
$$
b)\,  L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \}
$$
$$
c)\,L_3 = \{ w \in {0,1}^* | \, w \, \text{is a multiple of 5 (binary system) }\}
$$
$$
d)\,L_4 = \{ d^k e^m f^k | k,m \in \mathbb{N}, \, k < m\}
$$

$L_1$: Since we could build an NFA which accepts its strings, it's regular.

$L_2$: Using a single stack or PDA, by pushing $0$ to the stack for every $0$ in the string and then poping from the stack for every $1$ (after the $0$s) in the string, we can determine whether the string is in the language if the stack ends up empty. Thus, $L_2$ is context-free.

$L_4$: Same as above, but this time we need $2$ stacks (LBA). Push $0$s in the first stack for every $d$, push $1$s in the second stack for every $e$ and then pop from the two stacks for every $f$. If the first stack ends up empty and second ends up non-empty, then the string belongs to the language. Thus, $L_4$ is context-sensitive.

Are the above conclusions correct? If so, please provide me with a hint for the classification of $L_3$.


texts: Partitioning a set to the maximum number of subsets summing to zero

texts:
Given a multiset of numbers $X = \{x_1, \dots, x_n\}$, such that $\sum X = 0$, how can $X$ be partitioned to the maximum number of subsets so that each subset sums to zero?

I have searched around a lot, but none of the partition or packing problem variants seem to address this particular case.


texts: Solving a recurrence relation with T(n) = 2 * T(n/3) + 5n

texts:
I have no idea how to solve this one - I end up with $\sum_{i=0}^k (2^k * 5 * 3^i)$ but I have no clue how to get any further than that (e.g. resolve the sum even further, if it's even correct to begin with).

This is the task - masters theorem is not allowed:

T(n) = 2 * T(n/3) + 5n

T(1) = 5

and we know, that n = 3^k

Thanks for all of your advice & help!


texts: Question on pseudocode for Ford-Fulkerson in Kleinberg-Tardos Text

texts:
I am looking at the following pseudocode from the Kleinberg-Tardos text "Algorithm Design".

Max-Flow
Initially f(e)=0 for all e in G
While there is an s-t path in the residual graph G_f
    Let P be a simple s-t path in G_f
    f' = augment(f,P)
    Update f to f'
    Update the residual graph G_f to be G_f'
Endwhile
Return f

This seems to make sense to me. However, prior to displaying this pseudocode, the textbook gives pseudocode for the augment subroutine:

augment(f,P)
Let b = bottleneck(P,f)
For each edge (u,v) in P
    If e = (u,v) is a forward edge then
        increase f(e) in G by b
    Else ((u,v) is a backward edge, and let e = (v,u))
        decrease f(e) in G by b
    Endif
Endfor
Return(f)

Unfortunately, the textbook does not give any implemenation details on the bottleneck() subroutine.

But what I cannot understand is why we would need to pass the flow function $f$, to the bottleneck subroutine?

It seems that the bottleneck routine is looking at a simple s-t path in the residual graph $G_f$. Hence bottleneck is only concerned with the residual capacity along each edge. When we create the residual graph I was under the impression that each edge is labeled with the corresponding residual capacity. Hence, a call such as bottleneck($P$) would seem to suffice which simply looked for the minimum capacity along the edges in $P$.

Can someone shed any light on why we pass $f$ to this bottleneck subroutine?


texts: Reducing time complexity for finding all possible triplets in an array?

texts:
So I have an array sized N. It is sure that array has all distinct elements.

I need to find sum of all possible triplets in that array and for that i need to find all possible triplets.

What i did: looping through array with three nested $for$ loops but that gives O(n^3).

I want to optimise the algorithm as n is very large(upto 10000)

Eg: Array==> {1,2,3,4,5}

Possible triplets: {1,2,3} {1,2,4} {1,2,5} {1,3,4} {1,3,5} {1,4,5} {2,3,4} {2,3,5} {2,4,5} {3,4,5}


texts: matrix multiplication speedup when the matrix elements are 0, 1 and -1

texts:
I would like to compute matrix multiplication A * B where A is Nx3 and B is 3x3. We also know that the elements of B only contains 0, 1, and -1. The content of A is arbitrary floats.
Is there any speedup we can do?


texts: Why does floating point modulus exactness matters?

texts:
Most Smalltalk dialects currently implement a naive inexact floating modulus (fmod/remainder).
I just changed this to improve Squeak/Pharo and eventually other Smalltalk adherence to standards (IEEE 754, ISO/IEC 10967), as I already did for other state of the art floating point operations.

However for adoption of those changes, I anticipate that adhering to standard will not be enough to convince my peers, so explaining in which circumstances this exactness would really matter would help me a lot. I could not find a good example by myself so far.

Does any one here knows why/when/where (IOW in which algorithm) such exactness of modulus would matter?


texts: What's the practical use of pack/unpack and gather/scatter?

texts: In parallel programming, what is the practical use for pack/unpack and gather/scatter? I searched for practical examples and didn't find any use of those.