texts: Given a rng that outputs 0 or 1 with an equal probability, make a rng that generates 1 with a probability p

texts:
So this was an interview question I had a few weeks back that I just haven't been able to think of how to solve...

  Given a random number generator that returns 0 or 1 with a 50% chance of either, describe how you would implement a function that returns 1 with a probability $p$ and 0 with a probability $1-p$

So you can only use calls to that initial RNG to return either 0 or 1. What I was able to reach with the interviewer was that we know that the RNG basically generates a random float $f$ [0,1] and returns $0$ if $f < 0.5$, $1$ if $f \geq 0.5$.

I can solve it if $p=0.25$... basically I call the RNG twice, if both turn up 1's then I return 1 because the probability of that happening is $\frac{1}{4}$... and I can expand that solution to any $p$ where $p = \frac{1}{2^x}$, but how do I do that arbitrarily? I have a feeling this is somewhat similar to how floating point numbers are represented internally because I know they are represented using negative powers of two as well...

I thought this question was really fascinating, but it also seems to be nontrivial to solve... Any idea how to continue with a solution?


texts: Is it common in the literature to define regular languages and serialization languages as programming languages?

texts:
Often when I create programs I use operating-programming language such as Bash for automating OS operations, structure ("markup") language such as HTML to define structures, styling language such as CSS to style structures, and programming (behavior defining) language such as JavaScript, to define the "nature of interaction" with programming by user interface.

But there are two other types of languages I sometimes use when creating programs:
Regular languages such as POSIX basic regular extensions or PERL compatible regular extensions, and Serialization languages such as JSON or YAML; from my experience, it is reasonable to assume that the former type can be combined with generally all operating-programming languages and behavior defining languages, while the latter type I usually combined with JavaScript.

Is it common in the (Computer Science) literature to define regular languages and serialization languages as programming languages (as sharpening the behavior of a program)?


texts: Subset sum into a consecutive range vs. standard subset sum

texts:
The following problems live in integer domain.

I want to find a subset of $\{x_0, x_1, \ldots, x_{n-1}\}$ such that the subset's elements sum to any number in a prescribed interval $[X,X+k]$, $k\geq 1$.

We call the above problem A.

An obvious approach is to solve $k+1$ standard subset sum problems with targets $X, X+1,\ldots,X+k$ . I would be satisfied once my algorithm finds a solution to any of these problems.

Now I am wondering, does there exist a single standard subset problem B: $\{y_0,y_1,\ldots,y_{m-1};Y\}$ where $Y$ is the target, such that if I solved B, I equivalently solved A, additionally, the conversion from B's solution to A's solution is fast, preferably in linear time.

To make it simpler, I am only considering $k=1$.

Thank you!


texts:
We are given $N$ sets of $M$ non-unique elements each.
The amount of overlap (computed as the element count in the set intersection) between the elements of these sets is stored in a $N \times N$ matrix.

The aim is to find a way of grouping the $N$ sets into two classes, where one class has roughly 67% of the sets and the other one has the rest, such that the overlap of elements between the two groups is minimal. The group elements are the union of all elements of their assigned sets, and the overlap is defined as the element count in the group intersection.

Could you please suggest me an algorithm to find such groupings?


texts: Literature on network-flow (optimization) approximation algorithms

texts:
I've been searching on literature on approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree.

However, I have been looking in several well-known algorithm books but, I haven't yet found something. Most books don't go beyond Ford-Fulkerson and/or Edmond-Karp in respect to network-flow problems, and the sections explaining approximation algorithms discuss some algorithms not relating to network-flow optimization.

Could someone point me towards appropriate literature? I prefer books instead of papers.


texts:
I am trying to make sure my intuition for the following question from an assignment is correct

Prove or disrove: if $G = (V, E)$ is a graph and $I_1$ and $I_2$ are independent sets in $G$, then $I_1 \cap I_2$ is
an independent set in $G$.

Answer: This statement is true. Consider arbitrary nodes $x, y \in I_1$ and $u, v \in I _2$. Since $I_1$ and $I_2$ are independent sets in $G$, there is no edge between $\{x, y\}$ and there is no edge between $\{ v, u \}$. Similarly, here is no edge between $\{x, u\}$ and $\{v, y\}$ because otherwise, $I_1$ and $I_2$ would have to have nodes that are adjacent two each other. We see that $I_1 \cap I_2 = \emptyset$ and therefore, the statement that $I_1 \cap I_2$ is
an independent set in $G$ is vacuously true.

Is this approah necessarily true for any two independent sets in a graph? I would appreciate any feedback


texts:
Radix sort is theoretically very fast when you know that the keys are in a certain limited range, say $n$ values in the range $[0\dots n^k -1]$ for example.  If $k<\lg n$ you just convert the values to base $n$ which takes $\Theta(n)$ time, do a base $n$ radix sort and then convert back to your original base for an overall $\Theta(nk)$ algorithm.

However, I've read that in practice radix sort is typically much slower than doing for example a randomized quicksort:

  For large arrays, radix sort has the lowest instruction count, but
  because of its relatively poor cache performance, its overall
  performance is worse than the memory optimized versions of mergesort
  and quicksort.

Is radix sort just a nice theoretical algorithm, or does it have common practical uses?


texts: I have seen numerous ways to reduce CNF-SAT to SS, but is there any way to reduce SS to SAT (or one of its variations)? I have tried researching it, but all it brings up is the (apparently) much more common opposite reduction.


texts: Is an $\mathcal{O}(n\times \text{Number of clusters})$ clustering algorithm useful?

texts:
I am a physicist, with little formal training in computer science - please don't assume I know even obvious things about computer science!

Within the context of data analysis, I was interested in identifying clusters within a $d$-dimensional list of $n$ data-points, for which the dimensionality $d$ could be $\sim100$, whilst the number of data-points could be $\sim 1,000,000$, or perhaps more.

I wanted the points with a cluster to be close together, with distance measured in the Euclidean manner,
$$
d(\vec x,\vec y) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2}
$$
As long as the clustering was reasonably accurate, I wasn't bothered if the exactly correct result was obtained. i.e. if of my $\sim1,000,000$, $\sim1,000$ points were wrongly categorized, it wouldn't matter much.

I have written a short algorithm that can perform typically at $\mathcal{O}(n)$ (from trials of up to $n\sim5,000,000$ and some theoretical analysis) and worst-case $\mathcal{O}(n^2)$ (from my theoretical evaluation of the algorithm). The nature of the algorithm sometimes (but not always) avoids the so-called chaining problem in clustering, where dissimilar clusters are chained together because they have a few data-points that are close.

The complexity is, however, sensitive to the a priori unknown number of clusters in the data-set. The typical complexity is, in fact, $\mathcal{O}(n\times c)$, with $c$ the number of clusters.

Is that better than currently published algorithms? I know naively it is a  $\mathcal{O}(n^3)$ problem. I have read of SLINK, that optimizes the complexitiy to $\mathcal{O}(n^2)$. If so, is my algorithm useful? Or do the major uses of clustering algorithms require exact solutions?

In real applications is $c\propto n$?, such that my algorithm has no advantage. My naive feeling is that for real problems, the number of "interesting" clusters (i.e. not including noise) is a property of the physical system/situation being investigated, and is in fact a constant, with no significant dependence on $n$, in which case my algorithm looks useful.


texts: Context-freeness of $\{a^nb^mc^k \mid n \leq m \leq k\}$ and its complement

texts:
Was analysing old exam, still, even in home condition can answer this:

Determine which of the following languages over the alphabet $\{a,b,c\}$ are context-free. Prove the claim.
(a) $L_1 = \{a^nb^mc^k \mid n \leq m \leq k\}$,
(b) $L_2 = \{a,b,c\}^* \setminus L_1$, that is, $L_2$ is the complement of $L_1$ from (a).

Any help would be appreciated, it doesn't seem like CFL to me, but I struggle to apply pumping lemma here.


texts: Algorithm to Check for Upper Bound of Levenshtein Distance

texts:
I am looking for an algorithm that checks if the Levenshtein distance between two strings $s_1$ and $s_2$ is less than a certain upper bound $B$. I know, there are plenty of algorithms for calculating the Levenshtein distance, but I expect a possible efficiency gain in scenarios where $B$ << $Levenshtein(s_1, s_2)$, because an algorithm not aiming to determine the actual distance, but just aiming to answer the question whether the distance is below $B$ or not, can terminate earlier, as soon as it becomes clear that the distance must surpass $B$.
For such an algorithm, I have the idea of using a recursive function which takes the parameters $s_1$, $s_2$ and $B$ checks if the first character of $s_1$ and $s_2$ are equal, and recursively calls itself (with a potentially decremented $B$ and accordingly adapted $s_1$ and $s_2$). The function would sort out all scenarios where $B$ falls below 0. (And of course, the function will make use of the trivial lower bounds of $Levenshtein(s_1, s_2)$.) If no recursion branch is left, the algorithm would terminate, asserting $Levenshtein(s_1, s_2) \geq B$.
But before reinventing the wheel, I wanted to ask if there are already existing solutions for my problem. I googled this and didn't find any, but maybe my google results were just polluted with the Levenshtein Distance Algorithms. If there is no such algorithm yet, is my approach a good idea, or are there more efficient ways which I oversee?


texts: Concluding $SPACE(n^2) \neq SPACE(n^7)$ from universal turing machine running time

texts:
Let $M_U$ be an universal Turing machine which fulfills the following condition:

  If $M$ running $x$ takes $f(x)$ space, then $M_U$ running on $\langle \langle M\rangle,x\rangle$ takes $(f(|x|))^3+2\cdot|x|+|\langle M\rangle|$ space.

Why can we conclude from the above that ${\sf Space}(n^2) \neq {\sf Space}(n^7)$?


texts:
How would one prove that the following scheme definition is an ordered stream of integers

(define integers (cons-stream 1 (add-streams ones integers)))


texts: Efficiently storing and modifying a reorderable data structure in a database

texts:
I'm trying to create a list curation web app. One thing that's important to me is being able to drag-and-drop reorder items in the list easily. At first I thought I could just store the order of each item, but with the reordering requirements, that would mean renumbering everything with a higher order (down the list) than the place where you removed or where you inserted the moved item. So I started looking at data structures that were friendly to reordering, or to both deletion and insertion. I'm looking at binary trees, probably red-black trees or something like that. I feel like I could with great effort probably implement the algorithms for manipulating those.
So here's my actual question. All the tree tutorials assume you're creating these trees in memory, usually through instantiating a simple Node class or whatever. But I'm going to be using a database to persist these structures, right? So one issue is how do I represent this data, which is kind of a broad question, sure. I would like to not have to read the whole tree from the database to update the order of one item in the list. But then again if I have to modify a lot of nodes that are stored as separate documents, that's going to be expensive too, even if I have an index on the relevant fields, right? Like, every time I need to manipulate a node I need to actually find it in the database first, I think.
Also, I obviously need the content and order of each node on the front end in order to display the list, but do I need the client to know the whole tree structure in order to be able to send updates to the server, or can I just send the item id and its new position in the list or something?
I'm sorry if this veers too practical but I thought someone might want to take a crack at it.


texts: Why is `map insertionsort` not to equal to`map mergesort`?

texts:
In the type theory podcast ep. 3, Dan Licata claims that the fact that for every input, insertionsort and mergesort give the same result does not imply that the result would be equal when used as higher order functions as arguments to a third function, i.e. map insertionsort does not have to equal map mergesort.

He explains this by "because you don't know that, as functions, insertionsort and mergesort are equal" but I still don't get it.

Why is this the case? A counter example would be great!


texts: Party optimization: maximum weight independent set in a tree/graph

texts:
From Cornell

  Suppose we want to throw a party for a company whose organization
  chart is a binary tree. Each employee has an associated fun value, and
  we want the set of invited employees to have the maximum total fun,
  which is the sum of the fun values of the invited employees. However,
  no one has fun if some employee and that employee's direct superior
  are both invited, so we never invite two employees who are directly
  connected in the organization chart. (The less whimsical name for this
  problem is the maximum weight independent set in a tree.)

I was trying to think of an analogous statement if the problem were a graph rather than a tree. Might we say that now we want to throw the largest possible party with ex-girlfriends/ex-boyfriends such that no one's ex-partner is invited?

In this case an edge between two members denotes a ex-relationship. We want to find the largest set such that no two members share an edge.

Is this a correct interpretation of the graph problem and is there a known polynomial time algorithm?


texts: Does this Turing Machine M decide the language of polynomials?

texts:
Does this Turing Machine decide
language of polynomials with integer coefficients which have integer roots:
The input represents a polynomial over variables x1, . . . , xn with integer coefficients.
1. Examine all possible integer values of x1, . . . , xn.
2. Evaluate the polynomial on all of them.
3. If any of them evaluates to 0, accept; else reject

From what I know I would say No, since: "M decides a language L iff M accepts all strings in L and reject all strings not in L ". Where L is the language of polynomials.  Is this correct?
Any help is appreciated!


texts:
This is not a home work question.

Is that correct to say in a flow network, if min cut is unique then max flow must also be unique?

Assume we have two max flow in a network. Then for each max flow, we can get a min cut and they are surely different.


texts: Calculate makespan of job shop solution?

texts:
I have a job shop problem with n jobs and m machines, a job shop means that not all jobs have to go through every machine.

A job shop problem can be written as such :

[[15,0,15,16],
[10,30,20,0],
[0,15,5,10]]

This would be an example of a 3 job, 4 machine problem. The matrix is 3x4, with each value being the processing time of each job on the corresponding machine.

A solution can be written as : [1,0,2]. Which is the ordering of these 3 jobs. For the sake of self-containing the problem, a solution can also be written as :

[[10,30,20,0],
[15,0,15,16],
[0,15,5,10]]

Which is a re-ordering of the problem matrix according to the order of jobs in the solution.

Precedency constraint : All operations for a single job run from lowest machine index to the highest. If a job has an operation on machine k, k+1 can not be processed.

Question : I need help making an algorithm that takes the above solution as input, and outputs its makespan. The makespan is the time required for all jobs to be processed according to a given order.

Here's an example of the solution above represented kn a gantt chart :

Making the makespan 10 + 15 + 15 + 20 = 60 units of time for all jobs to be processed.


texts: Does removal of unit production from the grammar may increase number of total production?

texts:
There are m variable in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions)

(a) O(m)
(b) O($m^2$)

(c) O($k^m$)

(d) O($2^m$)

My attempt:

He asked about number of total production remains in the minimized grammar ,
 so , if the there is no null production , it is advantage , as you know when we convert a grammar without null production , generally , removal of all production introduces new production in the resultant grammar (it can be upto set of all subset of given max RHS number of variable , so exponetial ) .

But , in given grammar , you don't have null production , so you are removing only unit production (i.e. A--->B type productions ) , resultant grammar maximum 'm' production , where m is number of variable .
example :-
S---->A
A---->B
B---->a/b/c
resultant grammar ,
S---->a/b/c
So , it is O(m) time .

  Can you explain in formal way, please?


texts: would complexity of constraint satisfaction problem bound the constrained optimization problem?

texts:
If a constraint satisfaction problem $x \in Y$ is NP-Complete.
Can I conclude that the optimization problem $^* =\text{argmax}_x (x)$ s.t. $x \in Y$ is also NP-Complete?


texts:
Consider an array $X$ of $n$ cells, each containing a number from $\{1,..., n\}$. There is at least
one duplicate number, i.e., a number that appears at least twice. I want output some duplicate number. When streaming we may pass over $X$ more than once. The inspection of a cell generates cost $1$. The cost of a run of an algorithm is the sum of all individual costs. I can at most store $\log_2n$ bit numbers.
I tried to do that with a streaming algorithm that uses additional memory $O(1)$ with costs $O(n^2)$. Is it possible to state a ramdom access algorithm that uses additional memory $O(\log_2n)$ with costs $O(n)$?.

Which algorithm solves the problem by using additional memory $O(1)$ with costs $O(n^2)$?.
Which algorithm solves the problem by using additional memory $O(\log_2n)$ with costs $O(n)$?.

My problem is similar to the cycle detection problem, but I don't know how to use the cycle detection problem to solve mine. Is there maybe a simpler way that I can't see now?


texts: Prove or disprove NP-Completeness: An optimal ordering problem

texts:
Consider assigning a single object to $n$ potential receivers. It can only be assigned to one person.

For each receiver $k$, there is a value of profit $v_k$ and a probability $p_k$.
 Fix an ordering of the receivers, then for the $i$th receiver he accept the object with probability $p_i$, if he does, we gain a value $v_i$; if he doesn't, consider the next person in the ordering.

Then the expected value we gain is

$E(V)=p_1v_1+(1-p_1)p_2v_2+\cdots +(1-p_1)(1-p_2)\cdots (1-p_{n-1})p_nv_n$

It can be easily seen: to maximize the expected value we gain, the ordering should be in the decrease of the $v$.

But since passing through the potential receivers the object defects the value of it, the $i$th receiver has a parameter $w_i$ where $w_1>w_2>\cdots>w_n$.

$v_k$ is assigned to each person $k$, and $w_i$ is assigned to the $i$th person in the ordering. For example if the $3$rd person in the ordering is person $5$, then he has $v_5$ and $w_3$.

so the expected value changes to

$E(v)=p_1w_1v_1+(1-p_1)p_2w_2v_2+\cdots+(1-p_1)(1-p_2)\cdots(1-p_{n-1})p_nw_nv_n$

Is there a polynomial algorithm to give an optimal ordering that maximizes the expected value? Or should this be NP-Complete?

Any hint is appreciated. Thanks in advance.


texts: Why do we use $\Gamma$ to denote a TM's tape alphabet?

texts:
In many formal definitions of Turing machines, the Greek letter $\Gamma$ is used to denote the tape alphabet of the TM.

What is the origin of using $\Gamma$ for this? I'm having a hard time imagining what this might stand for.


texts: Alternative algorithms for calculating x^2?

texts: I'm emulating 128-bit arithmetic. At the moment I'm calculating $x^2$ by computing $x\cdot x$. What might be some alternative methods that aren't simply dressing up multiplication?


texts:
I was referring book by Peter Linz, which defines linear grammar as follows:

  A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without restriction on the position of this variable.

The wikipedia page also defines it similar way at the top of Linear grammar page

  a linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.

By these definition, it seems that the production of the following form is allowed:

  $S\rightarrow aSb$

But next on the same page, wikipedia defines it as follows:

  linear grammars in which all nonterminals in right hand sides are at the left or right ends, but not necessarily all at the same end.

By this definition, it seems that the productions of the above form are not allowed.

Then what is correct definition?


texts: Can't evaluate original Y combinator, two other variants do work, what do I miss?

texts:
I have made an evaluator of Lambda expressions. I tried to do Y combinator, but for some reason I can't get the original one working:

$$λf.(λx.f \space (x \space x)) \space (λx.f \space (x \space x))\tag1$$

This is probably for a reason, I don't know how to interpret $f (x \space x)$ part, or my evaluator does it right-wise or  call-by-value.

However these two variants of the Y combinator do work as expected:

$$λf.((λx.(f \space (y.((x \space x) \space y)))) \space (λx.(f \space (y.((x \space x) \space y))))) \tag2$$

and

$$λf.((λx.(x \space x)) \space (λx.(f \space (λy.((x \space x) y)))))\tag3$$

Latter is evidently a self-application version of the former one.

Already, I have found that most implementations use the latter two equations:

Javascript

http://kestas.kuliukas.com/YCombinatorExplained/

Python

https://github.com/bzanchet/pycombinator/blob/master/pycombinator.py#L194

Scheme

https://github.com/calincru/Y-Combinator#the-strict-applicative-order-y-combinator

I have added parentheses for the last two expression to make it clear the order of the evaluation. For the first case, I'm not totally sure, but when I interpret it like this:

$$λf.((λx.(f \space (x \space x))) \space (λx.(f \space (x \space x))))\tag4$$

it will cause infinite loop. Also self-application version of it would simply be:

$$λf.((λx.(x \space x)) \space (λx.(f \space (x \space x))))\tag5$$

Right?

I have used my own macro run on Hy language interpreter, so I rather discuss about the abstract implementation side of the problem than specific code. But this is how I'm applying Y combinator to the standard factorial function:

$$
((( f · (( x · (f \space (x \space x))) \space ( x · (f \space (x \space x)))))\\
  ( f · ( n · (if \space (= \space n \space 1) \space 1 \space (* \space n \space (f \space (dec \space n)))))))\\
  7)\tag6
$$

Result should be: 5040.

Note: In Hy, prefix notation of the mathematical operations are used.


texts: Find an element in sorted 2D-array (matrix)

texts:
Given an $N\times N$ array, where elements are decreasing in every row and every column.

What is the fastest way to find the $(i,j)$ of a given element if it exists in the array, or return no if it does not exist in the array?


texts: What is the sequence of numbers for N = 6?

texts: The numbers in the table below are the result of executing an algorithm that has one parameter N, a non-negative integer, and produces sequences of integers as outputs. For values of N from 0 to 5, the algorithm produces the following sequences of numbers as outputs.


texts: Showing that carbon is not a complexity measure per Blum

texts:
In Computational Complexity by Papadimitriou, there is an exercise about Blum's axioms where it asks to prove that several measures for the complexity of a Turing machine satisfy them.

7.4.12 Blum complexity. Time and space are only two examples of "complexity
measures" for computations. In general, suppose that we have a function $\Phi$, possibly
undefined on many arguments, mapping Turing machine-input pairs to the nonnegative integers. Suppose $\Phi$ is such that the following two axioms hold:

Axiom 1: $\Phi(M, x)$ is defined if and only if $M (x)$ is defined.

Axiom 2: It is decidable, given $M$, $x$, and $k$, whether $\Phi(M, x) = k$.

Then $\Phi$ is called a complexity measure. This elegant formulation of complexity was
developed in

M. Blum "A machine-independent theory of the complexity of recursive functions," J.ACM 14, 2, pp. 322–336, 1967.

(a) Show that space and time are complexity measures. (Notice that in this context
we do not maximize space and time over all strings of the same length, but leave the
dependence on individual strings.) Repeat for nondeterministic space and time.

(b) Show that ink (the number of times during a computation that a symbol has to
be overwritten by a different symbol) is a complexity measure.

(c) Show that reversals (the number of times during a computation that the cursor
must change direction of motion) is a complexity measure.

(d) Show that carbon (the number of times during a computation that a symbol has
to be overwritten with the same symbol) is not a complexity measure.

I am interested in the answer of (d) which I don't know how to approach.


texts: How to find the number of intervals containing a point when given a static set of intervals?

texts:
I've seen similar questions around here but I'm trying to address this problem with a slight change and maybe it makes it easier to solve.

I'm given a set of intervals $\{s_1,s_2,...,s_n\}$ where each interval has a starting point $b_i$ and an ending point $r_i$. Also, the set is not changing meaning no new intervals are inserted or removed, and no end/start points are identical.

I want to be able to return the number of intervals in $O(\log(n))$ time. I am aware of an interval tree however I actually don't have to worry about insertions and deletions so there might be something simpler.

Also, say I use an AVL tree where I use the start points as keys, and in each node I hold:

start - the start point of the interval
end - the end point of the interval
max - the max end point of an interval that is contained in the tree initiated at this node

And I search like so:

Given a point $p$, I start at the root and go down based on the max value compared to the point. If $p$ is greater than the max of the node, I'm currently at I consider it's right sub-tree. If $p$ is smaller than max, I consider the right sub-tree until I hit null or I find an interval that contains the point(based on start and end points).

This algorithm can return an interval that contains $p$ in $O(\log(n))$ time, but what if I wanna return the number of all intervals that contain it?

I understand it can be done in $O(\log(n)+k)$ time, where $k$ is the number of intervals containing the point but can't see really how.


texts: denotional semantic for while - fixed points

texts:
In my book it is written:
$$[[\text{while b do S}]] = \text{FIX F}$$, where $Fg = cond (\beta[[b]], g\circ [[S]], id). $
What is cond ?
$[[\text{if b then S1 else S2}]] = cond (\beta[[b]], [[S1]], [[S2]])$.

I don't understand why we should use $FIX$. What it is FIX ?
For me it is sufficient:
$S[[\text{while b do S}]] = cond(\beta[[b]], [[\text{while b do S}]]\circ [[S]], id)$$

DEFINITIONS

$$S_{ds}[[\text{while b do S}]] = FIX F$$
where $Fg= \text{cond}(\beta[[b]], g\circ S_{ds}[[S]], id)$

$$FIX: ((State\rightarrow State)\rightarrow (State \rightarrow State)) \rightarrow (State \rightarrow State)$$
In brackets functions are partial.


texts:
If we suppose that we are given two numbers $a$ and $b$ to add, what circuit depth do we require to add them?

I'm wondering if $a$ and $b$ are $O(n)$, and thus the amount of bits required to store $a$ and $b$ are $O(\log_2(n))$, how much time and/or space we must require to add them.

I'm interested in the general case.  However, I am wondering if there is anything else to be said about the case of adding $a+2a+1$.  It would be spectacular if we could do this addition in constant circuit depth.


texts: How to remove a universal quantifier in Lean theorem prover

texts:
I am working with two binary relations: g_o and pw_o, and I've defined pw_o below:

constants {A : Type} (g_o : A → A → Prop)

def pw_o (x y : A) : Prop := ∀ w : A, (g_o w x → g_o w y) ∧ (g_o y w → g_o x w)

I need to prove the following:

theorem prelim: ∀ x y z : A, g_o x y ∧ pw_o y z → g_o x z :=

I start with these tactics:

begin

   intros,

   cases a with h1 h2,

end

And I have this:

x y z : A,
h1 : g_o x y,
h2 : pw_o y z
⊢ g_o x z

Since pw_o is defined with a universal quantifier, I'd like to substitute w with x, then I would have (g_o x y → g_o x z) ∧ (g_o z x → g_o y x). After isolating the first conjunct with the "cases" tactic, I can use modus ponens on that first conjunct and h1.
How can I tell Lean to replace w in the definition of pw_o with x and replace x and y in the definition of pw_o with y and z, respectively?


texts: Is there any difference between extensible records and dependent maps

texts: In a typed setting, records can be thought of as a map from field to type. If there is a well-typed record merge operation (which allows overlapping fields), is there any real difference between the resulting type and a dependent map in a dependently typed language?


texts: Does the existence of a matroid structure imply that the greedy algorithm is optimal?

texts: I was going through the topic of matroid structures for the problems like Activity selection ,minimum spanning tree. I also came to know how to solve if a problem exhibits matroid structure. The statement says that problems that have matroid structure will have a greedy algorithm. But by just showing matroid structure for a problem does it mean greedy algorithm is the optimal algorithm for that problem?


texts: If a thread containing main terminates, can another thread do anything?

texts:
I'm studying threads in C and I have this theoretical question in mind that is driving me crazy.
Assume the following code:

1) void main() {
2)     createThread(...); // create a new thread that does "something"
3) }

After line 2 is executed, two paths of execution are created. However I believe that immediately after line 2 is executed then it doesn't even matter what the new thread does, which was created at line 2, because the original thread that executed line 2 will end the entire program at its next instruction. Am I wrong? is there any chance the original thread gets suspended somehow and the new thread get its chance to do something (assume the code as is, no sync between threads or join operations are performed)


texts: Maximum value a variable can hold without documentation

texts:
Suppose we work with some particular programming language (like C++) on some particular computer. Furthermore, we want to know which values are minimum and maximum for some particular numeric data type of this language. We can't use any specific tools of our language (like numeric_limits), and have no access to language or system documentation. Specifically, we don't know the lengths of our words. Is there an effective and rather precise way to find out the min/max we want to know?

We can certainly write some loop starting with zero and adding one at each step and wait for an overflow. But it is certainly not an effective way. We can write some loop and check some condition like $\log(\exp(n)) \stackrel{?}{=} n$, but I'm not sure whether this will answer our question.


texts:
Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between two nodes).

It's pretty easy to do it in $O(n^3)$ time. Is it possible to do it faster?
I think that on-line algorithm and pre-processing should help.


texts: Is every regular language Turing-decidable, and how can we prove this?

texts: I know every regular language is Turing-acceptable, but does that imply it is Turing-decidable?


texts: Deciding whether complement of context-free language is context-free

texts:
I need to find out if the following problem is decidable:

Given a context-free language $L$, decide whether its complement $\bar{L}$ is also a context-free language.

I am having trouble in defining the $TM$ I need in order to solve this problem. My thinking was to see if it is possible to construct a $TM$ that takes an encoding of a $CFL$ as input and halts in an accept or reject state depending on whether $\bar{L}$ is a $CFL$ or not. Is this line of thinking correct? If so, may I also know how to proceed further.


texts: Question concerning subset sum problem: split into 3 equal subsets

texts:
Task: Given an array $arr[a_1, a_2, \dots, a_n]$ of integers, let $A = \sum\limits _{i\in \{1, 2, \dots, n\}}a_i$.  Determine whether it is possible to spit $arr[]$ into 3 subsequences of equal sum, i.e. if $s_1 =s_2 = s_3 =\dfrac{A}{3}$ where $s_1 ,s_2 , s_3$ denoted the splitted arrays.
My thoughts: I will first examine whether there exists some sequence of numbers that sums up to $\dfrac{A}{3}$ via dp, then I will backtrack those numbers, "throw them out" (meaning I won't consider them anymore), and proceed with the remaining numbers of the array. After doing this a second time I examine whether the numbers left sum up to $\dfrac{A}{3}$ and return true if this is the case. Even though this sounds valid to me I somehow doubt the correctness of this.
Recurrence of DP: $dp[i][j] = dp[i-1][j-a_j] \text{ OR } dp[i-1][j]$
$dp[]$ is a boolean array of dimension $n \times\dfrac{A}{3}$.


texts: Given an undirected graph $G(V, E)$, how hard is it to decide whether it has an induced tree consisting of $k$ vertices, where $k$ is also given in the input?


texts: I want to make sure my understanding on P vs NP is correct. I know that NP-complete problems cannot be solved in polynomial time, and if P != NP, then all problems in NP cannot be solved in polynomial time. Furthermore, if we consider the church turing thesis, and if P != NP, then no computational formalism can solve NP-complete problems in polynomial time. Would I be fine saying this?


texts: Proving correctness of a loop that calculates the sum of array

texts:
I am trying to mathematically prove that the following program is correct:

int ArraySumC(int[] a) {
    int i = 0;
    int j = 0;

    while (i <= n) {
        j = j + a[i];
        i = i + 1;
    }

    return j;
}

When the loop ends, we want the invariant, Q, and the condition for loop termination, B'.

Q ∧ B' = Q ∧ i > n

We also want the post condition

j = sum(a[1] ... a[n])

I'm not sure how to go from here, because I don't know what Q should be. I am used to B' being an equality and thus being able to substitute one side of B' into the post condition. Should I assume that B' is i = n + 1? Or is there another way to deal with the inequality?


texts: Can polynomial depth circuits (with, let's say AND, OR, and NOT gates) be simulated in polynomial time?


texts: Representing FP relations using witnesses

texts:
Let a relation $R$ be A-polynomial if there is a polynomial $p$ and a polytime algorithm $A$ such that for each $x$:

If $(x,y) \in R$ then there is a witness $w$ of length at most $p(|x|)$ such that $A(x,w) = y$.
For each $w$ such that $A(x,w)$ halts, we have $(x,A(x,w)) \in R$.

Prove or disprove: Each $R$ in FP is A-polynomial.

My attempt: I think the statement is incorrect, and so I'm looking for a counterexample. Let $R$ be a relation in FP where the algorithm $A$ helps us decide the undecidable halting problem. I thought maybe about $R= \left\{0,1\right\}^*\times \left\{0,1\right\}^*$, but perhaps there is a simpler counterexample?


texts: Unparsing an operator grammar in the face of ambiguity

texts:
I'm using the grammar scheme of Danielsson and Norell ("Parsing Mixfix Operators"). The short version is:

user defined mixfix operators such as _+_ or if_then_else_
the precedences form a DAGs
it is known that this creates an unambiguous grammar if the operators don't share lexical tokens
otherwise, input gets rejected when the parse is ambiguous

We could define operators if_then_else_ and if_then_, then the classic example has two parse trees (as long as both operators have the same precedence; see page 5 of the paper):
if a then if b then c else d
if a then (if b then c else d)
if a then (if b then c) else d

I'm interested in unparsing, that is, given an AST, produce a string that will get accepted by the parser as unambiguous and result in the same AST - parse(unparse(ast)) = ast. This amounts to choosing where to put the parentheses. Of course, there is the trivial strategy of putting parentheses everywhere the grammar will accept them, but in the interest of legibility, I am interested in minimizing the amount of parentheses used.
The case of unambiguous grammar can be easily handled by following the non-terminals around. I can see a pretty naive method of extending this to ambiguous grammars:

Construct a potentially ambiguous string representation using the above method
Parse it back and check for ambiguity
If the parse is ambiguous, diff the parse forest and add parentheses around the subexpressions
of each node that differs
Try removing some of the parentheses one by one, testing the changes by running a parse

However, considering that parsing a grammar like this takes $O(n^3)$ and potentially superfluous parentheses are limited only by the size of the AST, I'm fairly confident this can take $O(n^4)$ time in the worst case.

Is there a better way?
Is there some exploitable structure to the ambiguities that can be found in this grammar scheme?
Is there a way to check whether a parse tree is unique faster than $O(n^3)$?
Is there a more conservative way of inserting parentheses where the parse trees differ?

Note: as this SO question explains, there is no way to decide whether parentheses are needed just by looking at a particular edge in the AST (or, in other words, impossible to define a relation of operators to operator holes in which they are, that decides this):

A cautionary example: Add another prefix operator say inc of the same precedence as if-then-else and if-then. Now assume an arbitrary set P ⊂ H x O where H is the set of operator holes and O is the set of operators. The set is meant to be a relation that tells when parentheses need to be added. Examine the expressions if a then inc b else c and if a then (inc if b then c) else d. The first requires (if-then-else.2, inc) to not be in P and the second requires the opposite. This contradicts the assumption the problem can be solved by a some kind of relation or an order. One could try to say let (inc.1, if-then) be in P making the latter expression if a then inc (if b then c) else d, but then inc if a then b becomes inc (if a then b) which has too many parentheses.


texts: Why the number of adresses stored on RAM is equal to $2^x$ when has "x" adress lines?

texts:
I know that a RAM when has 20 adress lines can store up to 2^20 data. I don't know the reason. What is that for and how?

On the image, where and what is the 2^20?


texts: Why L is defined as L = SPACE$( \log n)$ instead of L = SPACE$(\log^2 n)$ or L = SPACE$(\sqrt n)$?

texts:
$L$ is the class of languages that are decideable in logarithmic space on a deterministic Turing machine. In other words,

  L = SPACE$( \log n)$

But why $\log n$, instead of $\log^2 n$ or $\sqrt n$. This is what, I find out in the Theory of computation book by Michael Sipser Theory of computation book by Michael Sipser, Chapter 8

  Logarithmic space is just large enough to solve a number of interesting computational problems, and it has attractive mathematical properties such as robustness even when mathematical model and input encoding method change.

I am not able to understand completely, how mathematical properties and input encoding are related to defining L complexity class.


texts: Can all computational complexity results be expressed in terms of programming languages?

texts:
Computational complexity results are often explained in intuitive terms as statements about the possible efficiencies of algorithms to solve certain classes of problems.

However, on a more formal level, all (many?) results actually build on the underlying notion of Turing machines, which provides a precise way to define computation.

My question is then: can all computational complexity statements be fully expressed in terms of lines of (pseudo-)code?

If so, would that mean that one should state all results building on a finite set of "elementary operations" that are allowed in the programming language under consideration? What would be the "elementary operations" in such a context?


texts: Why is ww a linear indexed language while www is not?

texts:
I am a little bit confused on one idea regarding indexed languages.

  $\{ww \mid w \in \{a,b,c\}^* \}$ is a linear indexed language, but

  $\{www \mid w \in \{a,b,c\}^* \}$ is not a linear indexed language.

What is the difference? As far as I know, indexed languages can be recognized by stack automatons, but I am a little confused on this.


texts: What would be the appropriate learning path given these circumstances?

texts:
I've recently been trying to learn to program in python but I’ve been experiencing this overwhelming feeling of a desire to understand the underlying structure behind everything I’m doing. I want to be able to understand how computers work from the ground up, how hardware and software relate to one another and develop an intuition for their potential. I'd also like to know how all these languages that build on top of each other all rely on the same fundamentals and what those fundamentals are. Only then do I think I’ll feel comfortable and satisfied learning and working on a more superficial abstraction which I consider python to be.

Can any of you recommend a path I should take in order to satisfy this need? Whether that be a particular order of learning certain topics or more specifically any book, video, course that you might consider appropriate given my situation.

Thank you,

Mango164


texts: Application of cosine similarity to detect plagiarism

texts: Can anyone tell me how using cosine similarity to see the correlation between two documents actually shows you if someone is plagiarising the other? I understand how cosine similarity works but don't understand how using this shows how closely related they are when the cosine deals with vectors and angles. How can this relate to a document?


texts: Given a total recursive function, can you always compute its fixed-point?

texts:
We know from Kleene's recursion theorem that if $f$ is total recursive, there must be an integer $n$ for which $\varphi_n=\varphi_{f(n)}$. My question is: for every $f$ total recursive, is there a computable (total) procedure that computes such a point?

ie: $\exists g.\forall f.\varphi_{g(n)}=\varphi_{f(g(n))}$.


texts: What information needs to be saved in a Lamport clock system to deduce message causality?

texts:
By using Lamport timestamps, we can determine the causality of messages. It is however unclear to me how one would deduce this simply from the lamport timestamp of the message.

Take the following model situation: there is a casuality break when it comes to process 2:

Now, we add Lamport clocks (hopefully I have done that correctly)

I'm at loss when it comes to understanding how I can read out the correct casuality of received messages by process 2 from just the timestamps. Unless I haven't determined the timestamps properly.

It looks like there's some additional information needed to do that. Maybe to save the timestamp of the message itself, and the id of the sending process?


texts: Predicting the next number output by a random number generator

texts:
Given a start of a sequence of random numbers generated by some random number generator (of which we don't have the implementation), can we predict the next numbers in the sequence?

For example, having a series of random numbers like this

40 46 15 37 9 4
32 26 5 33 17 21
12 19 13 36 25 29

These are the output numbers from a random number generator and I want to know the pattern that was used to generate them.


texts: Parallel algorithm for finding the maximum in $\log n$ time using $n / \log n$ processors

texts:
We were presented in class with an algorithm for finding the maximum in an array in parallel in $O(1)$ time complexity with $n^2$ computers.
The algorithm was:

Given an array A of length n:

Make a flag array B of length n and initialize it with zeroes with $n$ computers.
Compare every 2 elements and write 1 in B at the index of the minimum with $n^2$ computers.
find the index with the 0 in A with $n$ computers.

The lecturer teased us it could be done with $\frac{n}{\log n}$ computers and with $\log n$ time complexity.
After alot of thinking I couldn't figure out how to do it.
Any idea?


texts:
I have a bijection problem that I cannot get my head around. It goes like this:

let f: A -> B and g: B -> C be functions such that g o f is a bijection. Prove that f must be one-to-one and that g must be onto. And also an example showing that it is possible for neither f nor g to be a bijection.

This is the problem. I do not even know where to begin. Any help is appreciated.


texts: Solution of a Toeplitz system of linear equations

texts:
I want to code a solver for nonsingular systems of $N$ linear equations in $N$ unknowns (say up to $N=100$) with an asymmetric Toeplitz matrix. I know that the Levinson algorithm can solve it in time $O(N^2)$ and I am looking for a solution with this complexity. I have seen mentions of alternative approaches such as Schur decomposition, LDU decomposition, Bareiss, Cholesky...

The equations are established in a Galois field, so that stability is not at all an issue here.

I am seeking advice for a good method to implement. My priorities are

ease of implementation,
low memory requirements.

I am not specially looking for superfast methods ($o(N^2)$), unless they are appropriate for moderate $N$, and simple.

What do you recommend?


texts: Complexity of a non-linear knapsack problem

texts:
Minimize

$$\sum_{i=1}^{n}\sum_{j=1}^{m_i}w_{i,j}v_{i,j}$$

subject to

$$\sum_{i=1}^{n}\frac{m_i}{m_i+\sum_{j=1}^{m_i}v_{i,j}} < \theta$$

$$v_{i,j}\in\{0,1\}~\forall i,~j$$

where

$w_{i,j}$ and $m_i$ are positive integers (constants)
$\theta$ is a positive real number (constant)
$v_{i,j}$ are 0-1 variables

is this problem NP-hard?

I think this is 'harder' than knapsack problem and probably should be NP-hard. I surveyed some literature but failed to understand them.


texts: How can node2vec help find similar "roles" within a graph (nodes whose connections have similar structure within the graph)?

texts:
I have a question on the node2vec algorithm described in this paper.

Node2vec is a deep learning algorithm that word2vec to graphs to learn embeddings. The authors claim that it can help find nodes with similar "roles", or nodes whose connections have similar structure within the graph (structural equivalence), such as two nodes that are both hubs.

However, it uses word2vec, specifically the Skipgram architecture. The Skipgram algorithm takes text as input and for each word, it looks within a window and finds specific nearby words within the vocabulary. Then for a word i, it then aims to learn the probability that word j appears near it, for j = 1,...,N (N being the vocabulary size). In the end, words with similar context will have similar embeddings.

Applied to a graph, each word is a node. The authors determine the window of nearby nodes by doing repeated random walks starting from that node. So from my understanding, node2vec should only be able to learn similar embeddings for nodes that are in the same community (i.e. appear in the same "context"). How can it produce similar embeddings for nodes that are in distinct communities, but who share the same structural role?

To make it clearer with an example:
Say that node A and node B have the same structure but are in different communities. Thus, they should have similar embeddings. However, the nodes that are near node A are extremely different from the nodes near node B. Thus the windows produced by random walks would be extremely different. For node A, the Skipgram architecture learns to find nodes within its window (nodes near node A), so nodes A and B should have different embeddings. So how would node2vec find similar embeddings for A and B?

Thanks so much for your help!


texts: Regular expressions accepted by programming languages but are not regular

texts:
The below definition of Regular Language is given in Wikipedia.

In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science (as opposed to many regular expressions engines provided by modern programming languages, which are augmented with features that allow recognition of languages that cannot be expressed by a classic regular expression).

The sentence in bold says that there are languages which are not regular but still are recognized by regular expressions engines of modern programming languages. Can anybody provide me an example of such a language?


texts:
Suppose that $G$ and $H$ are both expander graphs on the same node set with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$.

What can be said about the expansion of graph $G \cup H$? In particular, is the spectral gap of $G \cup H$ at least as large as the minimum of the spectral gaps of $G$ and $H$?
Does it make a difference whether $G$ and $H$ both have constant node degree?

This is certainly true for the edge expansion of $G \cup H$, since it can only increase by adding edges.
I know that spectral expansion and edge expansion are related by the Cheeger inequality, but using this route we only get a bound on the spectral expansion of $G \cup H$ that is worse than $\lambda_G$ and $\lambda_H$.


texts: Hardness of checking maximal magnitude of a sum of a subset of vectors

texts:
The problem I wish to solve is the following:

Given a set $V \subset \mathbb{Z}^2$ find the set $S \subset V$ such that $|\sum_{v \in S} v|$ is maximal.

By simply enumerating subsets we can solve this problem in $O(2^n)$. This problem feels a lot like the euclidian traveling salesmen problem to me but I can't quite make it fit. I've tried other numerical optimization techniques like giving each vector an associated scalar variable, the idea being that if the variable was 0 then you'd exclude the associated vector it and if it was 1 then you'd include it. Then the goal is to find an assignment of the variables that maximizes this (I used Lagrange's method). That pretty much just got me back to a clearly equivalent problem that I had no more hope of solving efficiently. I can't seem to find any way to do this any faster. Additionally, I'm having trouble concluding that it's NP-hard but it's my bet that it is. For such a simple problem I'd imagine it's been considered before.

Is this problem known NP-hard? Is there a reduction I just haven't seen yet? Is there some efficient algorithm I just haven't seen?


texts:
I need to test whether an integer $b$ divides another integer $a$. Both integers are “bignums”, in the cryptography range ($10^2$ to $10^4$ bits). The integers are represented in binary. Assume that the integers are positive.

Obviously, the faster the better. I'm primarily interested in fast performance when $a$ turns out to be divisible by $b$, so tricks that quickly detect certain cases of non-divisibility are not particularly useful.

I currently have code that calculates the quotient and remainder $(q,r)$ such that $a = b\,q+r$, then tests whether $r = 0$. That's obviously correct, but I'm wondering if I'm performing extra work by calculating and discarding the quotient and the exact value of the remainder.

Is there a more direct way (faster, not using more memory) to test divisibility than to perform the complete integer division?


texts: Weighted Maximum 3-DIMENSIONAL-MATCHING with restricted weights (Approx Algo)

texts:
If the weights of the weighted 3-DIMENSIONAL-MATCHING problem are restricted to let's say, 1 and 2, is there a possibility to reduce this case to the unweighted 3-DIMENSIONAL-MATCHING problem?
(Because for the unweighted version, there is a (1.5+$\epsilon$)-approximation1 algorithm, for the weighted version, there is only a 2-approx2,3 algorithm)

References:

unweighted ($1.5+\epsilon$-approx)
weighted ($2+\epsilon$-approx)
weighted ($2$-approx) by CHAN, Yuk Hei, 2009


texts: Solving a variant of the Exact cover problem

texts:
I am trying to solve a variant of the Exact cover problem where every element has to be covered exactly twice instead of once ( i.e. has to be in exactly two sets that are part of the cover).

Now, it is clear to me that this is an NP-complete problem, but I wish to know if there is any hope for some pseudo-polynomial time algorithm to solve this problem.

If relevant, the context arose from trying to recreate polyhedra from their edges: given a set of edges, decide if they constitute some polyhedron, and if they do, give a set of its faces. Thus the set I wish to cover is the set of edges, and the collection of subsets I have is that of objects that can possibly be faces (each containing the edges of the corresponding "face")


texts:
Let $L_{1}$ and $L_{2}$ be 2 languages over the same alphabet $\Sigma$.

$$A(L_1,L_2)=\{x\in \Sigma^*|\exists y,z\in L_2\text{ such that } yxz\in L_1\}$$

Assume that $L_{1}$ is regular and $L_{2}$ is context-free. The language $A(L_{1},L_{2})$:

is always a regular language
is always not a regular language
can sometimes be a regular language
cannot be context free

They say that the correct answer is 1.


texts: Find a graph for which Kruskal's algorithm achieves worst-case running time

texts:
I am working on a problem in which I must find a graph with edge weights on n vertices, for which Kruskal's algorithm achieves worst-case running time.  I am using a UNION-FIND data structure, but with no optimisations (path compression or weight/height union rules).

The version of Kruskal's which I am using is as follows:

Kruskal(G)
  for each vertex  ∈  do MAKE−SET()
  sort all edges in non-decreasing order
  for edge ,  ∈  (in the non-decreasing order) do
    if FIND  ≠ FIND() then
      colour (, ) blue
      UNION(, )
  od
  return the tree formed by blue edges

Also, MAKE-SET(x), UNION(x, y) and FIND(x) are defined as follows:

MAKE-SET()
  Create a new tree rooted at
  PARENT()=x

UNION(, )
  PARENT FIND() ≔ ()

FIND()
   ≔
  while  ≠ PARENT() do
     ≔ PARENT()
  return y

After having looked at this post, my idea was to construct a graph on n vertices, such that there are as many redundant edges as possible and at least one necessary edge which is checked last (this edge must have the greatest weight).

I've looked at the specific cases n = 4 and n = 5 and have tried to construct such graphs in these cases.  However, I am struggling to generalise to arbitrary n.

I would appreciate any hints for progressing with this problem.  Thank you.


texts: Changing a complete undecidable turing machine language

texts:
$L = \{\langle M\rangle\mid \text{M is a TM and }L(M) = \{101\}\}$ meaning M accepts only the string $101$. Which is neither co-recognizable / recognizable. Can be proven easily by $HALT \leq_m L (\text{ or } \bar{L})$ mapping reduction. Reasoning being its very to prove for all TM that none accepts 101 or none rejects 101. How do I tweak this to make this either recognizable or co-recognizable but not both?

My attempt:

$L = \{\langle M,w\rangle\mid \text{M is a TM and for some }L(M) = \{101\}\}$

$\bar{L} = \{\langle M,w\rangle\mid\text{M is a TM and for none }L(M) = \{101\}\}$

I'm trying to change it to it can accept 101 instead of it only accepts 101. And the complement is that it cant accepts 101. I'm stuck at the complament i don't think its proper and the wording of the language. I don't know if theres a easy way to change this language.


texts: What is the definition of P, NP, NP-complete and NP-hard?

texts:
I'm in a course about computing and complexity, and am unable to understand what these terms mean.

All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea what they actually mean. Wikipedia isn't much help either, as the explanations are still a bit too high level.


texts: weighted-clique to vertex cover reduction

texts:
WEIGHTED-CLIQUE

  input: a undirected graph G that has weighted edges and 2 natural numbers a, b
  question: does G have a clique of size a with total weight of b?

I want to prove that this is NP-hard (assuming weighted-clique $\in NP$)

So I would have to prove

$VertexCover \leq_P WeightedClique$

Need to show the transformation: $(G, k) \to (G', k', d)$

Which ill do by using the fact that $C$ is a vertex cover in $G = (V, E)$ whenever $\bar{C}$ is a clique in $G = (V, E)$ so $\overline{C} = |V| - C$

Hence we can let $G' = \overline{G}$ and $k' = |V| - k$.

I will draw example graphs to illustrate this:

I put 1's in $G'$ just to show that they're weighted as of right now, they have no purpose since I'm not sure how to integrate them into this problem yet.

So ultimately to prove this I need to show

  If there is a solution to $VERTEXCOVER(G, k)$, then there must be a solution to WEIGHTEDCLIQUE$(\overline{G}, |V | − k, d)$ (1)
  if there is a solution to WEIGHTEDCLIQUE$(\overline{G}, |V | − k, d)$, then there must be a solution to VERTEXCOVER$(G, k)$ (2)

I only know how to do the (2) part since the $d$ number could just be ignored.

(2) Using the fact from above where $C$ is a vertex cover we know that

If $\forall u, v \in V$, if $u, v \in C$, then $(u, v) \in E$

Taking the contrapositive

$\Leftrightarrow \forall u,v \in V$, if $(u, v) \in \overline{E}$, then $(u \in \overline{C} \text{ or } v \in \overline{C})$. Which makes it clear that $\overline{C}$ is a clique. This is also done in polynomial time since we are going over all pairs of vertices in the original graph which is done in polynomial time.

Now for (1) I'm not sure how to use the vertex cover and get some d such that it holds, if even possible.

Any help appreciated

edit: did wrong side by accident, fixed it


texts:
I want to show that reasonable advice can really speed up computation.

Show, that every time-constructible function $t$, there exists a set $S$ in time $\text{DTIME}(t^2) \setminus \text{DTIME}(t)$ that can be decided in linear time using an advice of linear length, $S \in \text{DTIME}(l) /  l$ (definition in analogy to $P / \text{poly}$), where $l(n)=O(n)$.

The problem is that I cannot come up with the structure of set.


texts: Balancing subproblems in resilience testing

texts:
You’re doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with $n$ rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung.
It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung $n/4$ or $3n/4$ depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer.

If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single jar—at the moment it breaks, you have the correct answer—but you may have to drop it $n$ times (rather than $\log n$ as in the binary search solution).

So here is the trade-off: it seems you can perform fewer drops if you’re willing to break more jars. To understand better how this trade- off works at a quantitative level, let’s consider how to run this experiment given a fixed “budget” of $k \ge 1$ jars. In other words, you have to determine the correct answer—the highest safe rung—and can use at most $k$ jars in doing so.

Suppose you are given a budget of $k = 2$ jars. Describe a strategy for finding the highest safe rung that requires you to drop a jar at most $f (n)$ times, for some function $f (n)$ that grows slower than linearly. (In other words, it should be the case that $\lim_{n\to\infty} f (n)/n = 0$.)

Anyone any insights how to solve this problem?

I know that the answer is $h = \sqrt n$. I know  that it solves the problem. But I want to know how you got that answer, there must be a general way to do it?


texts: How many algorithms solve the same problem?

texts:
Its kind of a weird question to ask but I have been asking myself this: Is there a limit to number of ways to find a solution to a particular problem.

Take the simplest problem: sorting a sequence of numbers.

Now there are a lot of algorithms to sort. Is there a limit to such algorithms? Technically, you can always flip a bit and back again, so there are infinite number of ways.

But still, simple problem as sorting, surely there must be finite number of ways to solve it.

In computer science we have computability theory which tells us whether a problem is solvable, complexity theory which tells us time and space to solve the problem. Similarly, is there something which can tell us the number of ways we can solve a particular problem?

Motivation for this question is that I'm amazed how many sorting algorithms we have. Such a simple problem and there are so many solutions!

Note: I asked this on stackoverflow. It seems that we need to precisely define how we would differentiate between two algorithms. Let's say we do it by somehow recognizing steps that are useless. That way we can say if two algorithms are doing the same thing.
What after that?
Lets take the example of sorting. All you can do is move one number from one index to other. With just this operation, surely there must be finite number of algorithms to solve the sorting problem


texts:
I have two questions

Is it possible to have 2 languages with different syntax but the same semantics? If not why not else give an example of 2 languages .

Is it possible to have 2 languages with same syntax but different semantics? If not why not else give an example of 2 languages .

I understand that the syntax is the external visible representation of a program and the semantics is the meaning of a program can some one please help answer these questions thank you.

Sorry if I wasn't clear but I was looking for examples of languages for example for the first question i have C# and VB.NET does that seem appropriate?


texts: Silly question: what counts as a "unit of work" when computing big-Oh time complexity

texts:
I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work".
It says in the textbook that certain operations take constant work, where as others take variable amount of time.
For example, adding/subtracting/multiplying/dividing two numbers take constant work. Similarly, a comparison statement also takes constant work. Lookup are also constant.
Whereas other operations such as for-loop takes a variable amount of work. For example, if a FOR-loop is to be run from $i = 0$ to $i = n-1$, and assuming whatever inside of the FOR-loop takes constant amount of time, then the total amount of work is proportional to $n$. That is, FOR-loop takes $O(n)$ time.
Something that doesn't really make sense to me is the smallest unit that can be defined as "work" in big Oh runtime analysis. What is this unit based off of? Adding two bits together? Adding two integers together?
Stemming from it are two related concerns:

certainly multiplication takes more "work" than addition. Division takes more work than subtraction. So what is the smallest unit of work here? Is the time to add two numbers a smaller amount of work than multiplying two numbers? That is, is the work of multiplication proportional to the time of addition?, $\text{work}_{\times} = c \times  \text{work}_{+}, c > 0?$

For example, are things like multiplication truly independent of the input? $k \times n = n + n + \ldots + n$ ($k$ times). So why is it considered a constant amount of work? Doesn't the same logic also apply to other programs? Say if I have $n$ conditional statement checking if a value is smaller or greater than a number $n$. Then this "constant" operation can still depend on how large my $n$ is (depending on how i implement this comparison).

Thanks for your patience.


texts: What does Arora mean by 'computational history'?

texts:
In Arora's paper, he wrote,

  Papadimitriou and Yannakakis also noted that the classical style of reduction (Cook-Levin-Karp [41, 99, 85]) relies on representing a computational history by a combinatorial problem. A computational history is a very non-robust object, since even changing a bit in it can affect its correctness. This nonrobustness lay at the root of the difficulty in proving inapproximability results.

What does he mean by this statement? In particular: what does it mean by 'computational history', and 'representing a computational history by a combinatorial problem'?

I conjecture that: [it is] a very non-robust object, he means that computation could make many many errors. So, in the last statement in the paragraph, maybe he means nonrobustness [the ability to make many errors] lay at the root of the difficulty in proving inapproximability.

Could someone tell me how nonrobustness exists in Karp/Levin reduction?


texts: Count bridging edges in a family of two component forests

texts:
I am given a (simple, undirected, connected) graph $G = (V, E)$ and a fixed spanning tree $T$ in this graph. Removing an edge $e\in E(T)$ from $T$ splits it into a spanning forest $F^e$ with two components $F_1^e$ and $F_2^e$. I am interested in the number $c(e)$ of edges in $G$ that connect $F^e$ i.e. with one vertex in $F_1^e$ and the other in $F_2^e$.

I would like to compute the number $c(e)$ for all $e$ in $T$ simultaneously. This can be done naively in $O(|V||E|)$. Is there a faster way to achieve this?

The graphs I am working with are small-world graphs. In particular the average distance between nodes in $G$ can be assumed to be small.


texts: How to solve a DP problem that minimizes a sum of cubic powers?

texts:
I am trying to practice some coding problems and I came upon this problem:

As electricity prices are soaring, there must be a way to reduce wastage by increasing the utilization of heavy duty machines, such as elevators.
We formulate the problem as follows.
There are $N$ persons $ (p_1,...,p_N)$ waiting in a queue to get into an elevator. By the way, there is only one elevator, and it travels between the ground floor to the sky floor (i.e., there are no other stoppages in between). Also, all persons are waiting on the ground floor.
Just for simplicity, we are concerned only with the utilization of the ground-to-sky journey of the elevator. Each person $p_i$ has a positive weight $w_i$.
The weight capacity of the elevator is $M$. Therefore, all persons may not be carried together. They are carried in several trips. Each person gets into the elevator according to his order in the queue. Meaning, $p_1$ gets in first, then $p_2$ and so on. Suppose at the $t$-th trip, persons $p_j$ through $p_k$ gets into the elevator. The waste factor ($WF$) of the trip $t$ is defined as

$$WF[t]=M-\sum_{i=j}^k(w_i).$$

Your task is to minimize the total waste ($TW$), which is defined as:

$$TW=\sum_{t=1}^{S-1}(WF[t])^3,$$

where $S$ is the total number of trips required to carry all the people from the ground to the sky floor. Note that the $WF$ of the last trip is not included in the $TW$ calculation.

I got completely stuck here, I figured that this can be solved via DP but I don't know how. Especially with the condition of maintaining the order.
Full problem can be found in here Problem K: Elevate the Utilization!


texts: Decision problems with complex input validation

texts:
In an answer to a question regarding input validation in decision problems, @Apass Jack wrote

  It is easy to check whether a problem instance is a valid instance or not for almost all decision problems people have been interested in. It is so easy and so common that people have become so sloppy or efficient that this verification step is usually skipped or even forgotten in the specification of an algorithm. That might be the source of your confusion.

Are there (non-pathological) decision problems for which input validation is as complex or more complex than computing the actual decision for an already validated input?


texts: Optimize binary search on Segment Tree by storing past result

texts:
Goal
Let $A[n]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($[l,r]$) of the segment the node covers, and a "sum" value equal to $\sum_{k=l}^rA_k$. I would like to perform a Weighted Random Selection on $A$, and because $S$ is a balanced binary tree, I can perform a binary search by traversing $S$ and do WRS in $\Theta(\lg n)$ time. In this case, the domain of my random variable $r$ is $[0,\sum_{k=1}^nA_k]$.
Now, suppose I delete the element $A_d,d\in[1,n]$, but because reconstructing $S$ takes $\mathcal{O}(n\lg n)$ time, I choose to let $S$ remain unmodified.
To perform WRS in this case, I am thinking that instead of starting from the first element of $A$, I can start from the $(d+1)$st element, tighten the domain of $r$ to $[0,(\sum_{k=1}^nA_k)-A_d]$ ($A$ here refers to the array before deletion, since the original values are stored in the "sum" values of the leaf nodes of $S$), and wrap back around to the start if I reach the end of $A$ while searching. The trouble is that the nice property of $\Theta(1)$ time needed at each iteration of the binary search (thanks to the balanced binary tree property of $S$) is no longer true. Now, each iteration of the binary search takes $\mathcal{O}(\lg n)$ time (summation over arbitrary segment in $S$), and since the binary search is $\Theta(\lg n)$, WRS done this way takes $\mathcal{O}(\lg^2 n)$ time.
Is it possible to perform WRS on $S$ in $\mathcal{O}(\lg n)$ time while omitting $A_d$?

Attempt at a solution
An easy way to make this operation faster is storing the cumulative sum calculated from the last iteration of binary search, and only calculate the ranged sum from the last midpoint to the current midpoint. This halves the size of the segment to be calculated at each iteration. However, this still appears to be in $\mathcal{O}(\lg^2 n)$ time. Halving the size of the segment at each iteration means $\lg(n)+\lg(\frac{n}{2})+\lg(\frac{n}{4})+...+1=\mathcal{O}(\lg \frac{n^{\lg(n)}}{2^{\lg(n)}})=\mathcal{O}(\lg^2 n)$ array accesses.


texts: Forgive me if I'm asking something that should be obvious, my experience is with software development, not computer science.  I've glanced at some articles on hyperthreading and parallel processing, but it seems like those implementations are primarily for consumer devices to persist multiple apps at the same time (listen to a music app while browsing the internet) but for non consumer implementations where there is only one primary process, like a VM exclusively used for tensorflow, would there be any benefit to the VM having additional CPU's?  There may be other OS processes going on with the VM, but the only way to calculate tensorflow faster would be to use a different hardware, like a GPU or a TPU, right?


texts: Network throughput with random delay selected from uniform distribution

texts:
Background:

I am working with IoT devices which broadcast status messages over a wireless channel periodically and at a rather high rate (500-5000 Hz). Receiving every message is not crucial but the more that are received, the better. I previously had nodes continuously synchronise clocks in order to adhere to a TDMA schedule, but this added significant algorithmic complexity to an application where 100% successful transmissions is not required. I am therefore trying a new approach based on random transmissions.

Problem Setup:

Let there be $N$ nodes, and let each node broadcast a status message of duration $A$ at least $d$ microseconds after its previous transmission, and no more than $D$ microseconds later. The exact delay for each packet is selected randomly and uniformly from the range $[d, D]$.

If packet $k$ is transmitted from a node at time $t_k$, then the transmission time of the node's next packet $k+1$ is given by $t_{k+1} = t_k + \mathcal{U}(d,D)$.

The minimum delay $d$ is a constant given by the time required for the IoT device to acquire a new measurement and schedule the next packet.

The maximum delay $D$ is a variable which should be tuned to maximise network throughput (akin to ALOHA).

Problem:

I'm trying to derive an expression for the network throughput.

I can't find any material on ALOHA with periodic transmissions, and can only find material where the probability of transmitting is poisson, and where each transmission is independent of the last.

Thank you for your help in pointing me in the right direction.


texts:
Is the follwing promise problem NP-hard?
Input: A system of quadratic equations.
Promise: The system has either one or zero solutions.
Question: Does the system have a solution?


texts:
An exercise problem once again has me stumped on a Turing Machine decidability proof.

We are given an alphabet with the strings 0 through 9.

Along with this, we have x as the infinite string of all digits in PI. (3141592...)

With L ⊆ Σ*, the language L = {A ∈ Σ*| A is a sub-sequence of x}.
(from what I understand, the definition here of a sub-sequence is  having a $x = x_1x_2x_3... $ where each $x_i$ can be constructed from Σ, then a sub-sequence of x is a finite string of the form $x_{i1}x_{i2}x_{i3} ... x_{ik}$ where $i_1 < i_2 < i_3 < ... < i_k.$

Other than that I have no idea where to start with this...

Thanks in advance.


texts: Flags register in an out-of-order processor

texts:
LW R2, 0(R1)
CMP R3, R2
CMP R7, R5

the LW instruction stalls the first CMP so the second one will execute first. Wouldn't this cause the flags register to contain the wrong value since it expects the second CMP to be the last one that updates the flags register?

I'm not sure about this one: does an ADD instruction ALWAYS update the overflow flag (1 if overflow and 0 if no overflow).

LW R2, 0(R1)
ADD R4, R3, R2
ADD R7, R5, R6

Same thing here: will the overflow flag be wrong if the first ADD wouldn't overflow but the second one will. The second ADD executes firsts and sets the overflow flag. After that the first ADD executes, doesn't overflow and sets the overflow flag to 0?


texts: Solving Hidoku problem using reduction to Hamilton path

texts:
It seems like people have discussed this reduction here:

Is Hidoku NP complete?

But it looks like the solution that was given only tells you if the Hidoku problem has a solution or not (if an hamilton path/cycle exists), what about extracting the solution itself from this reduction?

Can someone see how it is possible?

Best regards,
Tal


texts:
I get that all problems in NP can be reduced in polynomial time to some NP-Hard problem. An NP-Hard problem is also supposed to be harder or at least as hard as any NP problem.

Can an NP-Hard problem be reduced to an NP problem, which is not already an NP-Complete problem?

Also, are NP-Hard problems inter-convertible?


texts: Proof that shortest path with negative cycles is NP hard

texts:
I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is shortest?)

How would I reduce the SAT problem into the shortest path problem in polynomial time?


texts: Flipping all incoming/outgoing edges from a vertex in a DAG

texts: I'm working on a problem where I have a directed acyclic graph and I need to repeatedly flip all incoming (or outgoing, or both incoming and outgoing) edges from a single vertex. I think that resulting graph is still a DAG. Am I correct?


texts: I'm looking for a good definition of sparse graphs. Is a sparse graph effectively a big one, with millions/billions of nodes? An example from real world is the Facebook graph. Or can sparse graphs be in small networks as well?


texts: What is a fast algorithm for partitioning an array into $k$ subsets $A_1<\dots<A_n$?

texts:
Let $A$ be an array (equipped with a total ordering $\leq$) of size $n = km$ with $k\in \mathbb{N}$, such such that $A[1],\dots,A[n]$ are all distinct. What is a fast way to find a partition $A_1,\dots,A_k$ of $A$ with $|A_i| = m$ for all $i$, such that $x<y$, if $x\in A_i$ and $y\in A_j$ with $1\leq i<j$?

I have the following rough idea:

find the $i\cdot m$-th order statistic for $i = 1,\dots, k$ and put them into an (automatically) ordered list $\operatorname{pvt}$
iterate through the elements of $A$ and find for every such element (via binary search) the corresponding interval in $\operatorname{pvt}$ and insert it into the corresponding $A_i$

The first step can be done in $O(nk)$ (finding the $l$-th order statistic can be done in $O(n)$) and the second step in $O(n\log k)$, giving us $O(nk)$ in total.

Is there an obvious faster algorithm? (provided this idea works at all)


texts:
I am new to complexity theory and want to know what is structural complexity theory? what are problems theorists try to solve in this field and what is its future?
From the wikipedia:

  The structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms

I did not get the last line "rather than computational complexity of individual problems and algorithms " I mean in complexity theory we focus on complexity classes not on problems.

Thanks in advance


texts: Prove that turing machines and the lambda calculus are equivalent

texts:
It is known that a turing machine and the lambda calculus are equivalent in power. I now want to try to prove this myself. I think proving that the lambda calculus is at least as powerful as a turing machine should be relatively easy, by trying to simulate a turing machine in lambda calculus. This should be possible by storing the tape as a list with some encoding, and encoding a transition function as a lambda term.

However, I'm having trouble with proving that a turing machine is at least as powerful as lambda calculus. Any pointers on how to start trying?


texts: Goldbach Conjecture and Busy Beaver numbers?

texts:
Background: I am a complete layman in computer science.

I was reading about Busy Beaver numbers here, and I found the following passage:

  Humanity may never know the value of BB(6) for certain, let alone that of BB(7) or any higher number in the sequence.

  Indeed, already the top five and six-rule contenders elude us: we can’t explain how they ‘work’ in human terms. If creativity imbues their design, it’s not because humans put it there. One way to understand this is that even small Turing machines can encode profound mathematical problems. Take Goldbach’s conjecture, that every even number 4 or higher is a sum of two prime numbers: 10=7+3, 18=13+5. The conjecture has resisted proof since 1742. Yet we could design a Turing machine with, oh, let’s say 100 rules, that tests each even number to see whether it’s a sum of two primes, and halts when and if it finds a counterexample to the conjecture. Then knowing BB(100), we could in principle run this machine for BB(100) steps, decide whether it halts, and thereby resolve Goldbach’s conjecture.

  Aaronson, Scott. "Who Can Name the Bigger Number?" Who Can Name the Bigger Number? N.p., n.d. Web. 25 Nov. 2016.

It seems to me like the author is suggesting that we can prove or disprove the Goldbach Conjecture, a statement about infinitely many numbers, in a finite number of calculations. Am I missing somehing?


texts:
Consider a bipartite graph $G=(U, V, E)$. Each $v \in V$ represents a soccer team, and each $u \in U$ represents a mini-tournament needs to be scheduled.

If $u_i$ and $u_j$ share no common neighbor, these two tournament can be scheduled on the same day. Similarly, one can schedule multiple tournaments in one day if there is no such conflict.

Is there a way to compute the minimum number of days required to complete all the tournaments and the corresponding scheduling?


texts: Selecting higher values from arrays that are not far from each other

texts:
I have arrays $a_1...a_n$ each containing $m$ values inside. I want to select one value from each array. Let us say the selected values from each array are represented with $x_1...x_n$ and the distance amongst every selected pair of values as $d_{ij}$ (distance is simply how far the indices in the arrays are for every pair), where $1 \leq i \leq n$ and $1 \leq j \leq n$. The group of values selected should have the maximum value of $\sum_{k=1}^n x_k - \sum d_{ij}$ from all possible such sets. What technique can I use to solve this problem? Thanks.

I give an example here.

The arrays:

a1 = [1 2 10 1 1 1 1 1 1 1 1]
a2 = [3 2 2 2 8 1 3 4 5 12 1]

The values selected are $x_1 = 10$ and $x_2 = 8$ because they are close to eachother and note that we didn't select 12 from the second array. I hope this makes it clear.


texts: Why is data stored on a flash disk irretrievable if the memory chip is cracked?

texts:
All data recovery companies, regardless of skill, unanimously say that if the memory chip of a device has just a hair line crack, data recovery is impossible. Not unlikely, not expensive, but impossible. One company even stated that even the FBI can't retrieve the data. Is this true?

Why is this? I find it hard to believe if just a tiny section of an extremely common chip has a tiny crack, all of the data is completely gone.

I would have thought someone talented person somewhere would be able to patch up the area of the chip and get some of the data back...

Is it something to do with the charge? I know flash memory uses transistors to store its ones and zeroes in the form of an electrical charge. If the chip is cracked, do the transistors "short-out", turning them all to zeroes, something like that? Is the data gone rather than irretrievable?


texts:
I have a variation the shortest path problem, formulated as an ILP.
The system model is as follows:

There is a connected digraph consisting of 20 nodes, with each link having an associated weight delay which is a float. The graph is modeled as a python networkx object as follows:

g = nx.DiGraph(nx.barabasi_albert_graph(20, 2))
for u, v in g.edges:
    g[u][v]['delay'] = random.uniform(50, 1000)  # uS

There are multiple source-destination pairs and each pair has an associated 'demand' in terms of delay. The problem is modeled in python PuLP and solved using Gurobi solver.

# get cost
delay_d = nx.get_edge_attributes(self.graph, 'delay')

# get links
links = []
for i, j in self.graph.edges:
    links.append((i, j))

# instantiate the problem
prob = pulp.LpProblem("Shortest Path Problem", pulp.LpMinimize)

# create binary variables to state a link is chosen on shortest path
var_dict = {}
for flow_name in self.list_of_flows:
    for (i, j) in links:
        var = pulp.LpVariable('x_(%s,%s)_%s' % (i, j, flow_name), cat=pulp.LpBinary)
        var_dict[(i, j, flow_name)] = var

# create slack variables for every flow
delay_slack = {}
for flow_name in self.list_of_flows:
    delay_slack[flow_name] = pulp.LpVariable('d_%s' % flow_name, lowBound=0.0, cat=pulp.LpContinuous)

# formulate the objective
prob += pulp.lpSum([pulp.lpSum([delay_d[(i, j)] * var_dict[(i, j, flow_name)] for (i, j) in links])
                    for flow_name in self.list_of_flows ]) \
        + pulp.lpSum([1000 * delay_slack[flow_name] for flow_name in self.list_of_flows])

# formulate the constraints
for flow_name, flow in self.list_of_flows.items():
    # conservation of flow constraints
    for node in self.graph.nodes:
        if node == flow['source']:
            prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                    pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == 1
        elif node == flow['target']:
            prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                    pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == -1
        else:
            prob += pulp.lpSum([var_dict[(i, j, flow_name)] for (i, j) in links if i == node]) - \
                    pulp.lpSum([var_dict[(j, i, flow_name)] for (j, i) in links if i == node]) == 0

    # delay constraint
    prob += pulp.lpSum([var_dict[(i, j, flow_name)] * delay_d[(i, j)]
                        for (i, j) in links]) - delay_slack[flow_name] <= flow['qos']['delay']

# solve the optimization problem
prob.solve(pulp.GUROBI_CMD(msg=0))

There are no issues with the solution and correct results are obtained.
However, when I calculated the runtime, the results seem to be linear.

Now, I know that if an ILP satisfies the property of unimodularity, then the LP relaxation gives integer solution. Thus such an ILP can be solved in polynomial time using methods such as simplex.

However, if we look at the delay constraints, the coefficients of LHS are not integers, nor is the RHS integer. Thus it seems unimodularity property is not satisfied. Hence, shouldn't the runtime be exponential?

Can anyone explain why the runtime graph is linear?


texts: What is the name for closure-type functions that use the call-site environment?

texts:
Closures are functions that borrow the environment in which they are declared and can use and modify its variables at any times indipendently from where they're called, like in this example:

function createclosure(x)
    return function() --Anonymous closure
        print(x) --The variable x is caught and can be used anywhere
    end
end

myclosure = createclosure(123)

myclosure() --prints "123"

What I am looking for is quite the opposite: functions that borrow the environment in which they are called and can use and modify its variables:

function anti_closure()
    x = x + 10 --x is borrowed from the environment in which the function is called
    print(x)
end

function environment(x)
    print(x)
    anti_closure()
    x = x - 5
    print(x)
end

environment(23) --prints "23", "33" (from the anticlosure) and then "28" (because x was permanently modified in the anticlosure)

Is there a name for these type of functions? Are there languages that implement them? If not, why?


texts: Viterbi algorithm recursive justification

texts:
I have a question regarding recursion in Viterbi algorithm.

Define $\pi(k; u; v)$  which is the maximum probability for any sequence of length $k$, ending in the tag bigram $(u; v)$.

The base case if obvious $\pi(0,*,*)=1$

The general case.

$\pi(k,u,v) = max_{w \in K_{k-2} } \pi(k-1,w,u) \cdot q(v|w,u) \cdot e(x_k|v)$

The author justifies the recursion as folllows:

  How can we justify this recurrence? Recall that $\pi(k, u, v)$ is the highest probability for any sequence $y_{−1}...y_k$ ending in the bigram $(u, v)$. Any such sequence must have $y_{k−2} = w$ for some state $w$. The highest probability for any sequence of length $k − 1$ ending in the bigram $(w, u)$ is $\pi(k − 1, w, u)$, hence the highest probability for any sequence of length $k$ ending in the trigram $(w, u, v)$ must be $\pi(k − 1,w, u) \cdot q(v|w, u) \cdot e(x_k |v)$

I do not understand why it's actually true, I think it's possible to reach $\pi(n,u, v)$ from any $(n-1,w, u)$ not actually the maximum one $\pi(n-1,w, u)$ just because $q(v|w, u) \cdot e(x_k |v)$ might have a higher influence on the resulting $(n,u, v)$ than any $\pi(n-1,w, u)$.

I would appreciate if anyone could explain me why it's true.


texts: As I understand it when doing a DFS run when every new node is discovered and edge is added to the DFS tree from the parent of the new node to the new node. If that's the case how are back edges are created?


texts: What defines negative and non-negative type operators?

texts:
I'm working through some exercises in Robert Harper's "Practical Foundations for Programming Languages" and I'm not certain I understand what makes an occurrence of a type operator non-negative or negative in the general case.

I understand that positive type operators occur in the range of a function type, and that negative type operators occur in the domain of a function type, but I'm not sure how to generalize the additional category of non-negative based on the single given example t. (t -> bool) -> bool, which is only described as an occurrence in the domain of the domain without any mention of the interactions of further nesting. That also complicated my understanding of what makes an occurrence negative (must the occurrence on the left be positive, or just non-negative?), so now I'm just plain not sure what defines non-negative and negative type operators in the context of a function type.

For anybody who owns the book (second edition) this is chapter 14.


texts: Remove contiguous subsequence so the remaining numbers will created a sorted sequence

texts:
You are given $N$ numbers. Remove contiguous subsequence of those numbers, so the remaining numbers will create a sorted sequence. For example, if the sequence is $5$, $7$, $8$, $2$, $1$, $9$ then we have to remove subsequence $2$, $1$. I am only interested in the minimal amount of numbers removed. If this task wasn't about removing contiguous subsequence, then I would find longest non-decreasing subsequence in O(n log n) and output $N$ - $L$, where $L$ is length of this subsequence.

This task was taken from an old programming competition. I am asking this question, because I'm practising and got really stuck on this one.


texts: Understanding $\text{handle}$ in parsing problem

texts:
Originally https://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there

The BNF is defined as followed:

S -> aAb | bBA
A -> ab | aAB
B -> bB | b

The sentence is:

aaAbBb

And this is the parse tree:

Phrases: aaAbBb, aAbB, bB
Simple Phrases: bB
Handle: ?

From the book, handle is defined as followed:
B is the handle of the right sentential from $y = aBw$ if and only if:
$S \to_{rm} \cdot aAw \to_{rm} aBw$

So in my case, what's the handle? Any idea?


texts:
I am working with small data sets of N elements, usually with N = 8, 16, or 32 elements; all are positive 64-bit float numbers.  I need to identify the smallest N/2 elements.  It is not required that the smallest N/2 elements be sorted, just that I identify which ones they are from among the group of N.  Each program run must perform this sort up to a billion times, so sort speed improvements could generate useful returns for me.  Right now I am using a simple Quicksort that orders all N elements just to prove out my concept.

It is quite likely that my data are not randomly distributed, but I am not yet at the point where I can get a handle on that.

Eventually, the grand design is that this will find its way into the real world via an X-code implementation.

Any recommendations as to what my best sorting strategy ought to be?


texts: How can I determine an algorithm from a table of numbers?

texts: I need help with figuring out an algorithm from a generated numbers in a table. I was half way solving this question and I have already got the sequence for N=6, but I'm still stuck at writing the actual algorithm


texts: Canonical reference on agent-based computing

texts:
I am interested in exploring the world of BDI agents (software agents that possess "beliefs, desires, intentions", essentially the agent has knowledge of the world, a set of motivations, and carries out certain plans).

I recently read A Canonical Agent Model for Healthcare Applications [1], which left me with a lot of questions, particularly about the specialization of different agent models for particular applications.

The particular modeling language used in their examples was ProForma, and I understand that this is more for the abstract specification of an agent, and that something like 3APL can be used as an actual programming language in this regard, with syntax like:

BELIEFBASE {
    status(standby).
    at(0,0).
    location(r1,2,4).
    location(r5,6,1).
    dirty(r1).
    dirty(r5).
}

My question is, all of these systems clearly reflect years of cumulative efforts, and rather than jumping in to the deep end, I'd like to ease into this world of research a bit more slowly.  Is there a canonical reference in this area that might be able to provide a more general overview of all of these levels of organization, and where the abstractions stop and the implementations begin?

Fox J., Glasspool, D., Modgil, S. A Canonical Agent Model for Healthcare Applications. IEEE Intelligent Systems, 21(6), 21-28, 2006.


texts:
Given a polynomial circuit consisting of only $AND$ and $OR$ gates. Is it true that any such circuit is easily parallelizable i.e. it belongs to the complexity class $NC$?

I think this is the case but I can't find a source confirming it.


texts: Quotient of languages, regular quotient and their closedness

texts:
Left quotient is defined as below at this link:

Left quotient of $L1$ by $L2$:
$L1\backslash L2:= \{u\in \Sigma^*|vu\in L1$ for some $v\in L2 \}$

Wikipedia defines it as follows:

$L_1\backslash L_2=\{w|\exists x((x\in L_1)\wedge (xw\in L_2))\}$

Q1. I feel both definitions differ. Which one is correct?
Also first link says:

It can be shown that the families of regular, context-free, and type-0 languages are closed under quotient (both left and right) by a regular language. The family of context-sensitive languages does not have this closure property.

whereas wikipedia says:

The quotient of a regular language with any other language is regular.

Q2. I again feel both differ especially in case of regular quotient with CSL. Which one is correct?


texts: Maximum-density multiple-choice knapsack problem

texts:
I am looking for work done on solving a problem (specifically I'm looking for an approximation algorithm) which is very similar to a combination of two variations of the knapsack problem: maximum-density knapsack problem and multiple-choice knapsack problem.

The problem is:

We have $t$ sets $S_1,...,S_t$ of elements, where each set is of size $k$: $S_i=\{e_{i,1},e_{i,2},...,e_{i,k}\}$.
for each element $e_{i,j}$ there is a profit $p_{i,j}$ and a cost $c_{i,j}$.
It holds that $$c_{i_1,j}=c_{i_2,j},i_1 \neq i_2$$(the cost is the same for each set it only depends on the element's index in the set) so let us denote $c_{j}$ from now on.
Both the Profit and the Cost are monotonically increasing: $$c_{j_1} \leq c_{j_2} \text{ if } {j_1} \leq {j_2}$$ $$p_{i, j_1} \leq p_{i, j_2} \text{ if } {j_1} \leq {j_2}$$
The problem is to choose one element from each set to construct a set of $t$ elemets ${e_{1,j_1},e_{2,j_2},...,e_{t,j_t}}$ with profits ${p_{1,j_1},p_{2,j_2},...,p_{t,j_t}}$ and costs ${c_{j_1},c_{j_2},...,c_{j_t}}$
such that the following exprssion is maximized:
$$\frac{\sum_{i=1}^{t}p_{i,j_i}}{\sum_{i=1}^{t}c_{j_i}} = \frac{p_{1,j_1}+p_{2,j_2}+...+p_{t,j_t}}{{c_{j_1}+c_{j_2}+...+c_{j_t}}}$$
and the following expression holds for some constant $0 \leq r \leq 1$:
$$ {\sum_{i=1}^{t}p_{i,j_i}} \geq r*{\sum_{i=1}^{t}p_{i,k}}$$

Intuitively, you need to maximize the ratio between the profit and the cost while having at least some portion of the profit.

As I said this problem can probably be reduced to a combination of maximum-density knapsack problem and multiple-choice knapsack problem, so any information on that (and not specifically on the problem I stated) can be helpful as well.


texts: integer = c lg n (inputs of size n, Cormen 3rd, page 23)?

texts:
I just started with my "Algorithms" course. But my CS-background is lower than that of an average CS-student (I'm a data science student). Only had intro-2-prog course (Python/Java), that's it.

Cormen states on page 23: "...when working with inputs of size n, we typically assume that integers are represented by c lg n bits..."

How is " c lg n " derived? It's relation to the input size?
What calculation/proof is made here?
Which assumptions should one have to come to this assumption?
Which CS-field/subject (or academic/uni course?) works/operates with this notation, that should be learned prior to the "Algorithms" couse?


texts: Solving recurrence relations with two variables

texts:
I am trying to solve this recurrence relation with two variables:

$$T(n, k) = T(n - 1, k - 1) + T(n - 1, k)$$

The base cases are:

$T(n, k) = 1$ if $k = 0$
$T(n, k) = 0$ if $k > n$

I was wondering if standard techniques like characteristic polynomial and generating function would work in this situation.


texts: Given a NP Algorithm for SAT, do we expect to have Correct and Incorrect Solutions?

texts:
I am reading about Boolean Satisfiability Problem and Nondeterministic Algorithms, in the latter defination it says :

  In computational complexity theory, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations $...$ These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path

Assume we have a Non-deterministic algorithm for (SAT), does that mean the algorithm will show some computational paths leading to incorrect solutions (Non Satisfying Assignments) and other computational paths leading to correct solutions (Satisfying Assignment) ?

Or it is supposed to show only the correct solutions ?