texts: Recurrence relation for the number of "references" to two mutually recursive function

texts:
I was going through the Dynamic Programming section of Introduction to Algorithms (2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the context of assembly line scheduling
(Note: Assembly line scheduling or dynamic programming is not required to answer to the question though, it is just for information so that it shall help relating the context).

$(1),(2),(3)$ are three relations as shown.
$$f_{1}[j] = \begin{cases}
       e_1+a_{1,1} &\quad\text{if } j=1\\
       \min(f_1[j-1]+a_{1,j},f_2[j-1]+t_{2,j-1}+a_{1,j})&\quad\text{if }  j\geq2\\
\end{cases}\tag 1$$
Symmetrically,
$$f_{2}[j] = \begin{cases}
       e_2+a_{2,1} &\quad\text{if } j=1\\
       \min(f_2[j-1]+a_{2,j},f_1[j-1]+t_{1,j-1}+a_{2,j})&\quad\text{if } j\geq2\\
\end{cases}\tag 2$$
(where $e_i,a_{i,j},t_{2,j-1}$ are constants for $i=1,2$ and $j=1,2,3,...,n$)
$$f^\star=\min(f_1[n]+x_1,f_2[n]+x_2)\tag 3$$

The text tries to find the recurrence relation of the number of times $f_i[j]$ ($i=1,2$ and $j=1,2,3,...,n$) is referenced if we write a mutual recursive code for $f_1[j]$ and $f_2[j]$. Let $r_i(j)$ denote the number of times $f_i[j]$ is referenced.
They say that,
From $(3)$,
$$r_1(n)=r_2(n)=1.\tag4$$
From $(1)$ and $(2)$,
$$r_1(j)=r_2(j)=r_1(j+1)+r_2(j+1)\tag 5$$

I could not quite understand how the relations of $(4)$ and $(5)$ are obtained from the three corresponding relations. (directly without any proof, is it so trivial?)
Thought I could make out intuitively that as there is only one place where $f_1[n]$ and $f_2[n]$ are called, which is in $f^\star$, so probably in $(4)$ we get the required relation.
But as I had not encountered such concept before I do not quite know how to proceed. I would be grateful if someone guides me with the mathematical prove of the derivation as well as the intuition.
[Note: However an alternative to mathematical induction shall be more helpful as it is a mechanical cookbook method without giving much insight into the problem though (but if in case there is no other way out, then even mathematical induction is appreciated if I can get the intuition behind the proof)].


texts: What is language of repeat(L) = {ww | w ∊ L}?

texts:
What is language of repeat(L) = {ww | w ∊ L} ?

My try:
I know it {ww | w ∊ (a,b)*} is context sensitive language. Here , what is meant by "repeat(L)" ?  Can you explain it ? It is not a homework question.


texts:
I came across a very peculiar recurrence relation :

  $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)}  $

with initial values $T(0) = T(1) = 1$

Any helps on how to find it


texts: Longest-path in a graph, where the path should be 'straight'

texts:
Is there any existing work done on finding paths that are geometrically straight?

I encountered a problem where I'd need to find the longest straight(-ish) path in a web of connected nodes, each of which has a defined position in euclidean space (they're taken from a picture). Specifically, I want to find all straightish paths longer than X, but finding the longest may be simpler and basically equivalent.

Essentially, this is a path-finding problem in a non-directed, non-planar graph, where the path's destination isn't known, and the path itself must be straight, for an arbitrary and somewhat loose definition of 'straight'.

While I've found path-finding algorithms that use graphs whose vertices have defined positions, they generally work by just using those positions to give each edge a weight, after which the positions are ignored. I'm not sure that couldn't be done here, but I think it'd require a complicated edge-weight function that somehow takes into account the weights of previous edges in the current path.

Perhaps you could consider it a directed graph, where edges go only geometrically away from the source node/existing path - edges that double-back towards the start can't be taken. Marking them as such may be linear. Finding all complete paths (that is, starting at a source and ending at a sink) in a directed acyclic graph is polynomial. So while all the implementations I've tried so far range from 'very inaccurate' to 'quite inaccurate and also slow', I wouldn't expect the problem to be harder than polynomial.

Edit:

Because the graph is derived from an image, the lines will generally never be perfectly straight, and while straightness is usually visually obvious, my current algorithms have measured straightness by minimizing the change in angle from point to point, or by minimizing the geometrical width of the convex hull of either the entire path, or of sections of the path individually in turn. Width being measured perpendicularly to the straight-line distance between the first point in a path and the last. The problem with either of those though, is that each point has to be processed many times (I think $N^3$), and it feels less than elegant, and more like brute force.

The source of the problem is measuring fibers in an image, where the image looks kinda like a large game of pick-up sticks - hundreds of straight fibers, of varying lengths, cris-crossing frequently. Vertices in the graph are at endpoints, intersections, and discontinuities (i.e. potential endpoints). I'd guess that machine learning techniques, or other methods of image-processing, may be better suited for the problem, as it boils down to recognition of simple objects in an image, but the purpose of my question is more to learn about graphs, rather than just solve that problem.


texts:
if $x=1.0e38=1.0 * 10^{38}$ and $y=3.0$
i want to find $ (x-x)+y $ and $(x+y)-x$
i think the value of (x-x)+y will be just substract $x-x=0 + y=3.0 = 3.0$
but how can i perfom addition of different base? $(x+y)-x$
i think the idea is addition $(x+y)$ then substract $-x$ using floating point, i tried to convert $y=3.0$ to binary such as $1.1 * 2^1$
but how about $10^{38}$ to binary ?


texts: How to find the element of the Digit Sum sequence efficiently?

texts:
Just out of interest I tried to solve a problem from "Recent" category of Project Euler (  Digit Sum sequence ). But I am unable to think of a way to solve the problem efficiently. The problem is as follows ( in the original question sequence has two ones in beginning , but it does not change the sequence ) :

  The Digit Sum sequence is 1,2,4,8,16,23,28,38,49.... where the $n^{th}$ term of sequence is sum of digits preceding it in the sequence. Find the $10^{15}th$ term of the sequence.

The naive solution can't be implemented because it takes a lot of time. I tried to reduce the problem to a case of matrix exponentiation ( that would takes $O(log ( 10^{15}))$ amount of time ) but could not come up with such a recurrence fitting the linear criteria as recurrence for this sequence is quite peculiar. It can be seen that the sequence is governed by the recurrence :

$$ a_n = a_{n-1} + d( a_{n-1} ) ..... (1 )$$

where $a_n$ is $n^{th}$ term of the sequence and $d$ is a function which when given a natural number as input returns sum of digits of the number ( eg. $\;d(786)=21$ ). My second approach was to try to find some pattern in the sequence. It can be seen that the first few terms of the sequence can be written as

   a_1 = 1
   a_2 = 1 + d( 1 )
   a_3 = 1 + d( 1 ) + d( 1 + d( 1 ) )
   a_4 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) )
   a_5 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) + d( 1 +  d(
   1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) )

From the pattern above it becomes that $n^{th}$ term of the sequence can be  generated by the following method :

Write $2^{n-1}$ $1$'s with addition symbol between them.
Leaving  the first $1$, then apply the function $d$  on the next $2^{0}$ terms then on next $2^{1}$ terms, then on next $2^{2}$ terms and so on.
Then  apply the above method recursively on arguments of each $d$ function applied.

for example if n=3 we perform the following manipulations:

    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
    1 + d( 1 ) + d( 1 + 1 ) + d( 1 + 1 + 1 + 1 )
    1 + d( 1 ) + d( 1 + d(1) ) + d( 1 + d( 1 ) + d( 1 +d( 1 ) ) )

By dynamic programming I can generate the $n^{th}$ term using the above method in time $O(log ( 2^{10^{15}} ) )$, which again is no better than the naive solution.

EDIT 1
Another thing that can be observed is that $d(a_n) = d(2^{n-1})$. For example $d(a_6)=d(23)=d(32)=5$. But I am unable to make use of this point. I again tried to find a linear recurrence relation ( for matrix exponentiation ) , but I am unable to find it.

EDIT 2

Following is the graph when the sequence is plotted for smaller range ( first $10^6$ terms of the sequence  are plotted ).

PS: I know it is not advisable to ask solutions from Project Euler. But I just want a new direction or a hint, as I have been moving in circles for past few days. If that is also unacceptable I can remove the question if suggested.


texts: Numerically stable reverse automatic differentiation of power(x, y)?

texts:
I would like to compute the adjoints $\bar x$ and $\bar y$, from a reverse automatic differentiation perspective, of the expression $x^y$. The adjoint $\bar{x^y}$ is already known; and we can assume $x \geq 0$ and $y \geq 1$.
The "easy" solution consists of rewriting the expression $x^y=e^{y \ln x}$, and proceed piece-wise from there. However, this solution proves to be unstable numerically, it gives:
$$\bar y = \bar{x^y} x^y \ln x$$
and
$$\bar x = \bar{x^y} x^{y-1} y$$
Is there any way to rewrite and/or approximate those expressions with something that is not going to numerically diverge when $x \approx 0$?


texts: Expressivity of neural networks, how much information can be stored

texts:
I want to know whether a given neural network (with a finite number of nodes) is able to store all injective maps f: D -> C, where D has cardinality k and C has cardinality N (so the number of maps is N! over (N-k)!  ).
For example is a network with 1000 nodes able to store 60 injective maps from {1,2,3} to {1,2,3,4,5}?
(By storing information I mean something like: when classifying information the network can access and use the information)
In particular I was curious if the above question can be translated to a question about the VC-dimension of a neural network. Can a question about storing injective maps in a neural network be translated to a question about the VC-dimension of a neural network?
EDIT: I’m interested in something like the following result
There are 60 functions, note that we can represent this with 6 bits
The codomain consists of 5 elements, which can be encoded by 3 bits (since 5 < 2^3)
We need to map 3 elements of the domain to an element of the co-domain, so we need 3 times 3 bits for each function
So to encode 60 functions we need 60 * 3 * 3 bits
In general we need (N! / (N-k)! ) * k * log_2(N) bits
Note that (N-k+1)^k < N! / (N-k)! < N^k
and even (N-k)^k < (N! / (N-k)! )  * k * log_2(N) < N^k
One weight in a neural network is 32 bits
If we have X weights, then we have X*32 bits
So if X*32 is smaller than log_2(N-k) * k, then it’s not possible to express all the functions in the network
[I’m actually more interested in negative results like the one I gave, sorry if that’s confusing. Positive results are welcome as well.]


texts: What are some applications of computing the permanent of a matrix?

texts:
What are some applications that require computing the permanent of a matrix?

One application I know of is related to graph theory and matchings. Apparently, the number of perfect matchings of a bipartite graph is the permanent of its incidence matrix.

I am curious to know more applications of matrix permanent.


texts: Is there any difference in the expressiveness of boolean grammars versus definite clause grammars?

texts:
Definite clause grammars have been around a long time and are included in logic languages such as Prolog.

They can be translated into (are just syntactic sugar for) Prolog programs and are therefore I assume turing complete (unless I have missed an important limitation of DCGs relative to full Prolog).

Prolog is a logic programming language and of course supports the Boolean operators.

Boolean grammars were introduced much more recently and are typically described as an advance on previous approaches.
It is not immediately obvious why they might be more expressive than DCGs.

Don't both DCGs and Boolean grammars come down to expressing linguistic rewrite rules as:

  LHS(attributes...) -> RHS1(attributes...) [<boolean operator> RHS2(attributes)]*

E.g.

  S -> NP VP |
       S V O |
       foo & bar & not Z

What are the limitations of DCGs?

How do Boolean grammars differ?

I think Boolean grammars don't make use of attributes. That ought to make them less expressive rather than more. I see no reason why you shouldn't use attributes with Boolean grammars in principle however.

I should clarify what I mean by expressive. I mean it in both senses:

Is the set of languages that can be parsed using one bigger or different than the other
&
Does the written formalism express a language more compactly and intuitively

Though those are really different questions.


texts: Is order of bits in byte really not of concern?

texts:
What I can't wrap my head around is sentence repeated everywhere I look, that order of bits in byte is not important(not of my, as a programmer, concern).
My question then is if there is possibility that it makes difference?

For example, I crate a binary file with just 0x1 in it (represented on my machine as 00000001). What keeps other machine to read the same byte as 128(10000000) ?
Is there standard for msb placement in file, memory that guarantees compability or am I missing something trivial/obvious along?

EDIT:
Thanks to dirk5959's answer I found out that my machine is little-endian for bytes and the same is for bits in byte. Additional question is, if it is a rule or there is some architecture that behaves different?


texts: Travelling Salesman Problem with Memoization

texts:
I coded a solution for the famous Travelling Salesman Problem but my code does not work properly, although it seems okay.

In a grid of size m x n, you are allowed to move only down/right, and
you need to go from the top-left corner to the bottom-right corner.
Each sell has a reward value. How much is the maximum reward you can
collect?

def travellingSalesman(m, n, rewards, memo={}):

  if m == 0 or n == 0:    return 0
  if (m, n) in memo:      return memo[(m, n)]
  if (n, m) in memo:      return memo[(n, m)]

  # Base case
  if m == 1 and n == 1:   return rewards[0][0]

  # maximum rewarding one of the grids m-1 x n - m x n-1 plus reward of the current cell
  memo[(m, n)] = max(travellingSalesman(m-1, n, rewards, memo), travellingSalesman(m, n-1, rewards, memo)) + rewards[m-1][n-1]

  return memo[(m, n)]

if __name__ == '__main__':
  print(travellingSalesman(m=3, n=3, rewards=[[0,4,2],
                                              [3,2,0],
                                              [4,1,0]]))

The function below returns 6, but it should return 8 with the path: 0-> 3 -> 4 -> 1 -> 0
Can you enlighten me about the problematic/missing part of this code? Thanks!


texts: How to understand the storing mechanism used in external merge sort

texts:
I was reading about external merge sort from the wikipedia article link, according to it:

  External sorting is required when the data being sorted do not fit
  into the main memory of a computing device (usually RAM) and instead
  they must reside in the slower external memory (usually a hard drive).
  External sorting typically uses a hybrid sort-merge strategy. In the
  sorting phase, chunks of data small enough to fit in main memory are
  read, sorted, and written out to a temporary file. In the merge phase,
  the sorted subfiles are combined into a single larger file.

Suppose we have a RAM which can only hold 2 chunks of data and we have 6 chunks of data to sort. Please see the below diagram:

Since our memory can hold 2 chunks of data so the first step 1 sounds plausible since we are sorting only pairs of numbers (5,6), (3,4) (1,2). In the step 2 we merge the data and now our chunk size is 4. My question is how do you now load this 4 chunk of data into memory now? Since your memory cannot accept more than 2 chunks of data then how do you load and sort them? How did you sort while merging chunks of data here? I have visited several links, but not able to understand this concept.

You must be performing some kind of sorting while merging the data as well right?


texts: Placing 1d items in a 2d grid with constraints

texts:
I'M looking for an algorithm (preferably polynomial) for the following problem:

Input:
- an M x N grid, where each square can be either empty or occupied
- a list of items
- a list of constraints

Output:
the grid, such that all items are placed and the constraints aren't violated.

Each item is a 1d block of length k. Different items may have different length, and there may be several items with the same length. Items can't ovelap each other.

Example 1:
Given 1 x 5 grid and 2 items of lengths 1, 2 respectively. The following solutions are acceptable:

11100

10110

11010

and so forth.

Example 2:
Given 3 x 5 grid and 2 items of lengths 1, 2 respectively. The following solutions are acceptable:

00110
10000
00000

11000
10000
00000

etc.

Possible constraints:
a. Isolation - items may not touch each other. e.g. the following solutions is illegal:

Example 1:

11100

Example 2:

11000
10000
00000

However this is a legal solution:

01100
10000
00000

i.e. touching diagonals are legal.

b. Facing - 2 items must be placed one in front of the other. e.g.

11000
00000
11000

What I did so far is to find a solution for a simpler problem, where the grid is 1d and the only possible constraint is Isolation. I solved it by representing it as a search problem, and using A* with the heuristic: sum of lengths of items not placed yet. The problem is that it suffers from state explosion which will only deteriorate in higher dimensions.


texts: Algorithm for Filling Regions with Small Gaps

texts:
I am looking for an algorithm that fills a region with one color, but the edge of the region is not completely closed (i.e. one or more gaps are being left). The result is like the use of the Paint Bucket Tool with Gap Size option in Adobe Flash. We can assume that the input of the algorithm has to specify the largest size (straight line distance) of the gap.

My straightforward idea is (1) to fill the gaps in the edges (as shown in this webpage), and then (2) use the flood fill algorithm to perform the filling on a closed region. I have done (2) by using a recursive algorithm, but how should (1) be done?

Any alternative idea are also welcomed. Thanks!


texts: What is the difference between Big(O) and small(o) notations in asymptotic analysis?

texts:
What is the difference between $O$ (big oh) and $o$ (small oh) notations in asymptotic analysis? Even though I understand that $o$ is used for a bound that is not tight, is it allowed to use $O$ notaion for a bound that is also not tight? For example can I say that $5n=O(n^3)$?

I am also confused by what this statement in CLSR means
 "The main difference is that in $f(n) =O(g(n))$, the bound $0 \le f(n) \le cg(n)$ holds for some constant $c > 0$, but in $f(n) = o(g(n))$, the bound $0 \le f(n) < cg(n)$ holds for all constants $c > 0$." As the value of $c$ will differ in the inequality "$0 \le f(n)< cg(n)$ for all $n > n_0,c>0$. " for different $n_0$.


texts: Runtime analysis of sorting an array with known number of inversions

texts:
I'm having difficulties with analyzing the worst-case runtime of this following case:

I'm given an array that has $n$ natural numbers. Out of all $\binom{n}{2} = \frac{n(n-1)}{2}$ possible pairs there are $\frac{n(n-1)}{2} - 5n$ inversions. Inversion is defined like this: $a[i] < a[j],\ i>j$.

So of course you can sort the array in $O(n \log n)$ time but can you do any better than this? I've looked online and saw that inversion sort time is in $\Theta(n+I)$ where $I= \text{# inversions}$ but then I get that $I=\Theta(n^2)$ so it doesn't really help me.


texts: Is universality problem of single state NPDA decidable?

texts:
I came across following problem:

  Given single state non deterministic pushdown automata $M$, whether $L(M)=\Sigma^*$ is decidable?

Now I know

for DPDA/DCFG/DCFL, universality problem is decidable.
for NPDA/NDCFG/NDCFL, universality problem is undecidable.

However I am not sure whether the same problem is decidable or not for single state NPDA. I know for every NPDA, there is equivalent single state NPDA. So the language classes of NPDA and single state NPDA are equivalent. But does having single state restriction makes universality problem decidable? For example, if that single state is final state (for non final single state, the language will be empty), can we simply check if there is looping transition on that state labeled with all symbols in its alphabet $\Sigma$ and decide its universality. That is, if there are such transitions then its language is equivalent $\Sigma^*$. However if the looping transition is missing label even for a single symbol, then its not equivalent to $\Sigma^*$. If yes, does this means that universality problem of single state NPDA is decidable even though it is of same language class as NPDAs?


texts: How proof of Hoffman algorithm greedy property starts with optimal tree T?

texts:
In this paper Claim 1 states that x and y are smallest probability and there is optimal code tree in which this two characters are siblings at the maximum depth. In proof to that claim, author starts with tree T which has b and c at the maximum depth of tree. I can't understand why tree T is called optimal, because if x and y have smallest probabilities, then tree T cannot be optimal because Hoffman algorithm won't build such tree. I think my problem here is with understanding what optimal tree means.

If someone comes from CSLR this is about lemma 16.2 and proof to that.


texts:
I have the following example that I have to prove

{a>7 ^ b>=0} n:=a-b {n<a ^ a+b>=0}

Using the Consequence Rule I assumed that the P is true

{true} n=a-b {n<a ^ a+b>=0}

so logically, the Q should be true, but I'm not sure if that'd be enough.


texts: Show there exists a turing machine with the following properties

texts:
I'm struggling to understand a question I've been given. The question asks:
Let $\psi$ be a boolean formula in $n$ variables. There are $2^n$ different combinations of assigning
values to the variables. Consider the problem of deciding whether (strictly) more than $2^{n−1}$
of these assignments satisfy the formula $\psi$. We will call the language that corresponds to this
decision problem, $L$.

From this I can tell that if $x_1, x_2, ..., x_n$ are the $n$ variables which can be either true or false. I understand why there would be $2^n$ different assignings for the formula, as each variable can be assigned 1 of 2 values. But then what is $\psi$ exactly, is it an assignment such as $\psi$=($x_1 \lor x_2 \lor ... x_n$). But then the later part of the question doesn't make any sense. Can someone please explain in more detail what it means by "deciding whether (strictly) more than $2^{n−1}$ of these assignments satisfy the formula $\psi$"?

The question is then to show that there exists a turing machine $M$ and polynomials $T$ and $p$, with the following properties:

• For every input $x$, $M$ terminates after at most $T(|x|)$ steps.

• If $x\in L$, then $Pr_{t∈\small\{0,1\small\}^{p(|x|)}}$[$M$ accepts $<x, t>$] $>$ 1/2.

• If $x\notin L$, then $Pr_{t∈\small\{0,1\small\}^{p(|x|)}}$[$M$ rejects $<x, t>$] $≥$ 1/2

Where $Pr_{t∈\{0,1\}^{p(|x|)}}$[$M$ accepts $<x, t>$] means the probability, for a give $t$ from the set $\{0,1\}^{P(|x|)}$, that M accepts the input $<x,t>$ is greater than 1/2.
This is similar to the definition of bounded error probabilistic polynomial time(BPP), except that the definition for BPP have both equalities as $≥$, so I'm
guessing I need to show that the language L is in BPP. But how would I even start the proof to show that he language is indeed in BPP. Also the definition of a language in BPP is not identical to what is mentioned in the question, so maybe there's a different approach to answering the question. Also, I don't need to explicitly find the polynomials $p$ and $T$, but instead argue that they exist.

Any help to assist me with the question would be much appreciated


texts: Dijikstra's algorithm with "hull" value catch

texts:
Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here.

Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, and a  set of pathways $1$ to $M$, with pathway $p_i$ connecting two points
$a_i,b_i$, taking time $t_i$. The goal of the problem is to find and print out the minimum time required to get from a specific point of $a$ to point $b$, along the pathways.

This looks like a Dijkstra's algorithm implementation... however there is a catch.

For every such pathway  $p_i$ connecting two points $a_i,b_i$, not only is there a time $t_i$, there is also a hull value $k_i$. You travel by water along the pathways, and your ship has a hull $K$ to begin with. From point $a$ to point $b$, the sum of the hull values along your chosen pathway must not be greater than $K$, otherwise your ship will sink, i.e the pathway is no longer valid.

For this problem, what I first tried to do was to implement it similar to how a normal Dijikstra's algorithm would be implemented.

This passed $9/15$ test cases on the grader, which I am quite proud of for a first attempt. Time wasn't an issue as it usually was, but I am getting Wrong Answer.

I then realised that I cannot just save the minimal hull value for each vertex, as each valid path has a different hull value sum. I have to implement a sort of queue/stack like structure and distinguish between each path.

However, the second I do that, I get codes that score even fewer points than my initial attempt. Time Limit becomes an issue, and I get even more Wrong Answer test cases on the practice CCC grader.

I spent two days already on this problem, and don't seem to be making any progress.

Any help will be appreciated.


texts: Minimum cardinality graph partition that removes specific edges

texts:
I have a computational problem that I want to solve. I'm not sure if it has already been studied in literature, or if so under what name. I'd appreciate any pointers to literature or suggestions for an algorithm.
Input: A connected, undirected graph G = (V, E) in which certain edges are labelled "bad".
Output: The minimum cardinality partition of V such that 1) all of the induced subgraphs of the partition are connected, and 2) none of the induced subgraphs contains a bad edge.
Thanks!


texts: Does every language that fulfills the regular Pumping conditions also fulfill the context-free ones?

texts:
Let L be a language that fulfills the properties implies by the Pumping lemma for regular languages.
Does L necessarily fulfill the corresponding properties of the Pumping lemma for context-free languages as well?


texts:
At the moment I am studying several questions about the arithmetical degree of some index-sets in relation to the standard-ordering on $\mathbb{Q}$. The situation is as follows: I fix some enumeration $r_0, r_1, \ldots$ of $\mathbb{Q}$ such that $<$ is decidable. Then I take
$R_e=\{r_n \mid n \in W_e\}$, where $W_e=dom(\varphi_e)$ (the domain of the $e^{th}$ partial recursive function, refering to Kleene's Normal Form Theorem). Now $R_e$ inherits the ordering from $\mathbb{Q}$.
$\textbf{Question 1}$
Define
$$
A
=
\{
e \mid (R_e,<) \cong (\mathbb{Z},<)+(\mathbb{Z},<)
\}.
$$
I try to prove that every $\Sigma_3$-set $m$-reduces to $A$ but I don't have a good idea. Does somebody see something useful I can do?
$\textbf{Question 2}$
I want to show that there exists $d$ such that the sets $\{e \mid (R_e,<) \cong (R_d,<)\}$ and $\{e \mid (R_e,<) \equiv (R_d,<)\}$ are not arithmetical at all. Does somebody has a good idea for this?


texts: what is complexity of language {a | a = x^2 }

texts: What is known complexity of language {a | a = x^2}, is it possible there exist deterministic Turing machine (one input tape and one work tape) that accept this language in linear time?


texts: Explaining why FFT is faster than DFT for the general public?

texts: How would you explain why the Fast Fourier Transform is faster than the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?


texts:
I am unable to understand that what the characteristic path length (CPL) of a graph is.

In one of its definitions, it is written that

  it is defined as the median of the means
  of the shortest path lengths connecting each vertex to all other vertices.

This is what I understand. Is it right?

Suppose we have 3 nodes A, B and C. A can reach to B and C through different paths. We consider just the two paths, AB and AC. These two are the shortest path lengths from which A can reach to B and C respectively. We will then take the mean of AB and AC. Similarly, we will calculate two more means for B and C like I calculated it for A. In the end, we will take the median of the 3 means.

Am I right?


texts: How does a program execute with respect to the operating system?

texts:
I am reading Operating Systems by William Stallings 6th edition and I came across this text,

Program execution:

A number of steps need to be performed to execute a
program. Instructions and data must be loaded into main memory, I/O devices
and files must be initialized, and other resources.

Now I am unable to understand how I/O devices and files are initialized on program execution? I assume it meant to start the I/O resources but what about the files? Please guide. Thanks


texts: Triangular Rasterisation with Barycentric Coordinates

texts:
I'm having trouble with a pretty basic function that tests whether or not a point is inside of the triangle by trying to find its barycentric points with 2 other points on the triangle. When i run my code my entire triangle fills up, but I'm also getting a fair amount of false positives. If I remove the boundbox condition I get 2 triangles reflected over imaginary line:

 bool insideTriangle(int point_test[2], int point_a[2], int point_b[2], int point_c[2])
{   //test-A = P-V1
    //test-B = P-V2
    int testMinusA[] = { point_test[0] - point_a[0],point_test[1] - point_a[1] };
    int testMinusB[] = { point_test[0] - point_b[0],point_test[1] - point_b[1] };
    float den = determinant(point_a, point_b);

    //s = determinant(P - V1, V2) / determinant(V1, V2)
    //t = determinant(V1, P - V2) / determinant(V1, V2)
    float s = determinant(testMinusA, point_b)/den;
    float t = determinant(point_a, testMinusB)/den;

    //if abs s >= 0 t>=0 and s+t < 1 then we good
    if ((s>=0 && t>= 0 && (s+t) < 1)||(s<=0 && t<=0 and (s+t)>-1)) { return true; }
    else { return false; }
}

float determinant(int point_a[2], int point_b[2])
{
    return( point_a[0] * point_b[1]) - (point_b[0] *point_a[1]);
}

So ultimately I think my question is, Are my errors caused by some misunderstanding of barycentric(ity?) based on what you can see

Note: I'm following tiny renderers tutorial, if that helps educating me in any way.


texts: Practical Implementation for Refinement Order on Integer Partitions

texts:
The refinement order on partitions of an integer $n$ can be defined as follows: $\lambda=(\lambda_1,\dots,\lambda_k)\leq\mu=(\mu_1,\dots,\mu_\ell)$ if there is a partition of the parts of $\lambda$ into blocks whose sums are the parts of $\mu$.

It is known that the problem of deciding whether $\lambda\leq\mu$ is NP-complete.  However, for a practical application I would need an algorithm which performs reasonably when $n$ is around $200$.  Ideally, this algorithm would already have a (free) implementation...

I tried the following naive approach:

find the last index $j$ such that $\mu_j>\lambda_1$
if $\mu_{j+1} = \lambda_1$ remove $\mu_{j+1}$ from $\mu$ and $\lambda_1$ from $\lambda$ and recurse
otherwise, for $j\in\{j,j-1,\dots,1\}$:

subtract $\lambda_1$ from $\mu_j$ and reorder to obtain a new partition, and recurse with this partition and the rest of $\lambda$

Although this seems to work reasonably well for many pairs $(\lambda,\mu)$ of partitions of size around $200$, it performs poorly when $\lambda$ has many small parts but is not a refinement of $\mu$.


texts: N 3d integer points in box with maximum average distance

texts:
given a 3d cube with a size of m x m x m, is there an efficient algorithm to find N integer points with the average Euclidean distance between each pair maximized? If not, is there any evolutionary approach I can take to this, so in each step the solution will be improved?

Thanks!


texts: Variant of interval scheduling (multiple machines with given availability)

texts:
I am looking for an algorithm to solve the following variant of interval scheduling : schedule some tasks on multiple machines, which are only available during a given interval of time. Two tasks cannot be performed at the same time by the same machine. I am trying to maximize the number of scheduled tasks.

More formally, we are given $m$ intervals $[B_i, E_i]$ (the machines) and $t$ tasks $[b_i, e_i]$. We must output $m$ lists $[i_1, i_2, ..., i_{k_j}]$ such that for each $1 \leq j \leq m$, $B_j \leq b_{i_1} \leq e_{i_1} \leq b_{i_2} \leq ... \leq e_{i_{k_j}} \leq E_j$, all the elements of the lists are distinct and $\sum_{j = 1}^m k_j$ is maximal (ideally t).

I thought about the greedy algorithm consisting on scheduling first the task that finishes the earliest, on the compatible machine whose last task finishes the latest (we consider every machine has at first a task finishing at the beginning of its working interval). However, this idea doesn't work, how we can see considering the instance of the problem where we have two machines, working on the intervals (0, 3) and (1, 4), with the tasks (1, 3) and (2, 4).
This way of selecting the machine on which we schedule the task is however not so stupid, and prevents other problems (the algorithm works if we are allowed to exchange the end of the working interval of the machines).

Is there a fast algorithm to solve this or is it a hard problem ?


texts: Is it possible to form a PDA for this language?

texts:
$$L=\left \{ a^nb^m|n\leq m\leq 2n \right \}$$
Is this even context free?
I am asking because by looking at the condition, for an expression that holds:$n< m<2n$ can be written as : $a^nb^nb^c (c<n)$.
Following this term(taken from geeks for geeks https://www.geeksforgeeks.org/check-if-the-language-is-context-free-or-not/) :"An expression that involves counting and comparison of three or more variables independently is not context free language, as stack allows comparison of only two variables at a time."
So here I need to make sure that number of first b's is the same as a's and the second b's are less than n$(c<n)$, which makes me think that L might not be context free(although it specified clearly to build PDA for this).


texts: Can data be compressed to size smaller than Shannon data compression limit?

texts:
I was reading about data compression algorithms and the theoretical limit for data compression. Recently I encountered a compression method called "Combinatorial Entropy Encoding", the main idea of this method is to encode the file as the characters presented in the file, their frequencies and the index of these characters permutation represented by the file.

These documents may help explaining this method:

https://arxiv.org/pdf/1703.08127

http://www-video.eecs.berkeley.edu/papers/vdai/dcc2003.pdf

https://www.thinkmind.org/download.php?articleid=ctrq_2014_2_10_70019

However, in the first document I've read that by using this method they could compress some text to less than the Shannon limit (They didn't consider the space needed to save the frequency of the characters and the space needed to save the meta data of the file). I thought about it and I found that this method won't be very efficient for very small files but on the other hand it may work well with large files. Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by $log_2$ of the reciprocal of the probability.

So I have some questions:

Does this compression method really compresses files to smaller than the Shannon limit?
Is there any compression algorithm that compresses files to less than the Shannon limit (the answer to this question as far as I know is no)?
Can a compression method that compresses files to smaller than the Shannon limit ever exist?
If combinatorial encoding really compresses files beyond the Shannon limit, isn't it possible to compress the file again and again until we reach the file size we want?


texts: Typical NP-complete/hard problems in machine learning

texts:
I know little about machine Learning, but I work on optimization (solving NP-hard problems with SAT solvers or MIP). Examples of this would be solving TSP, Steiner tree problems, path finding with constraints, etc.

I was wondering, is there any problem in ML that is NP-hard for which there are only approximations or small attempts of trying to solve them? I would like to look at them to see if my work can be applied there.

I am only interested in discrete optimization (so over integers/Booleans). Something that one could typically solve with constraint programming. Examples of such problems are scheduling tasks, finding paths in a graph given some weird constraints, TSP, vehicle routing...
My research is on constraint programming applied to graphs, so if the problem can be modelled as a graph problem, that is a plus.
My knowledge of ML is limited. I know the high-level concepts such as what regression, classification or supervised/unsupervised mean. Never actually implemented one of this ML things. I am watching a coursera class form Stanford on ML, but it is portrayed in a way that doesn't let me really see what are the NP-hard challenges.


texts: what would be the drawbacks of lecturing two programming languages simultaneously?

texts:
One colleage came with the idea/comment that it would be useful to lecture two programming languages, eg. Java and Scheme, at the same time while lecturing an Introduction to Programming course aimed for first term undergraduates.

I have my doubts that approach could stuck some students in learning the syntax of the programming language instead of the logic on how-to-program. Also I believe that some of them will get in their minds that Computer Science careers are equal to being a hardcore software developer.

While I have found some academic references about the last point I mentioned (that CS!=programming), I have not found any academic sustainable research that could prove wrong to teach two programming languages for an initial course, apart of discussions of lecturers against that idea in public forums. In ACM there is a paper in which they tried to lecture Python and Java at the same time, but the authors make so many assumptions and also mention a lot of pitfalls on their research, that I hardly believe it is a good article to be based on.

Has anybody found or read any article that mentions the advantages/disadvantages of that approach?


texts: Prove that regular languages and context-free languages aren't closed under $Perm(L)$

texts:
Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$

  Prove that both regular languages and CFLs aren't closed under $Perm(L)$.

I've tried to use several well-known languages (like $\{0^n1^n\}$) and applying $Perm(L)$ and afterward manipulate them or using the pumping lemma in order to get a contradiction, but nothing worked out.


texts: Definition of 2-CNF (a.k.a Krom) formula

texts:
In my lecturer's notes, the following definition for a 2-CNF wff is given:

  A 2-CNF formula, or Krom formula is a CNF formula F such that every clause has at most two literals.

However, there is no mention in the notes of how one might represent clauses containing a single literal L in the wff's corresponding implication graph (although I suppose one could add an edge from every other literal to L). Looking at Krom's original paper, the definition he seems to use is:

  A 2-CNF formula, or Krom formula is a CNF formula F such that every clause has exactly two literals.

This definition would seem to make a lot more sense. Which definition is correct? Am I missing something?


texts:
I'm designing a tree data structure to store strings in. One classic solution is prefix tree, but I am looking for a solution that the time to check if the string is in the storage is O(logm*logn) where m is the length of the string and n is the total number of character in Alphabet(if the string can be lower case aliphatic a-z only, n is 26).

I checked this post Data structure for storing strings, but the solution of prefix tree will take O(m) to insert.

Can I get some idea about the data structure with O(logm * logn) traverse and O(n * logm) insert time? Any general design ideas will be appreciated!

Thanks


texts: Equivalence of final state and empty stack PDA

texts:
I have done some reading on these two types of PDA and, to my layman eye, it looks like one simply 'wraps' an empty stack PDA with some extra transitions to create the final state PDA. Since these are empty string transitions and are just pushing/popping the stack bottom marker, does the set of languages a final state PDA accepts differ from the empty stack variant? My intuition says no, but I'm nowhere near conversant enough to attempt a proof.

Final state PDAs being a PDA M which accepts when input is exhausted and M is in an accepting state.
Empty stack PDAs being a PDA M which accepts when input is exhausted, M is in an accepting state, and the stack is empty.


texts: Find the closest string to a fixed set of strings

texts:
I want to find the closest string to a fixed set of strings. The strings are all equal in length, and the number of strings in the set is relatively small (compared to all the possible strings of the fixed size). For this problem you can assume the strings only contain the characters 0-9, and if needed, the length will never be longer than 32 characters.

I measure closest by hamming distance, the distance between two strings is the number of places the two strings differ. I don't care about how ties are resolved, any string with the minimum distance is acceptable.

For example, with s1 = "123" and s2 = "321", the distance between them is 2. (All the pseudo code is in Python)

def distance(s1, s2):
    return sum(a != b for a, b in zip(s1, s2))

I can complete a query in $O(n)$ time where $n$ is the number of strings in the set. The idea would be to loop over each string in the set and compute the distance between it and the target. The answer is the (first, with this implementation) string with the smallest distance.

def query(table, target):
    return min(table, key=lambda t: distance(target, t))

Is there a way to do this in less than linear time? Can the set of strings be pre-processed to allow for a faster search?

Here is a testcase/example

target = '91814154'
table = [
    '91812315',
    '77403499',
    '57579618',
    '92354796',
    '23425335',
    '97722442',
    '01824154']

distances = [4, 8, 8, 6, 8, 7, 2]

So the answer is the string '01824154'.


texts: Given a directed graph with number of nodes not exceeding 3*10^4. Each node has indegree ranging from 1 to 5 and outdegree from 1 to 5. We need to partition the graph into vertex-disjoint simple cycles. It is necessary to use all the nodes but it is not necessary to use all the edges.


texts: Are models of computation closed under composition?

texts:
It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or concatenation, or the Kleene star. And those questions seem natural to me, because they're essentially questions about the power of a model of computation that can decide precisely the languages in $C$. However, it seems just as natural to me - perhaps even more natural - to ask whether such a class is also closed under composition.

Here's what I mean by that. If I fix some subset $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$ of "decidable" languages relative to some model of computation, for any (finite) $\Sigma$, then I have also fixed some subset $\mathcal{F} \subseteq B^A$ of computable functions, for any languages $A, B$ - because each function $f : A \rightarrow B$ can be viewed as a function $\bar{f} : A \times B \rightarrow \{0, 1\}$. Given that, I would expect that for any reasonable model of computation, if $f : A \rightarrow B$ and $g : B \rightarrow C$ are computable, then $g \circ f : A \rightarrow C$ should be as well. Put in terms of the corresponding languages, I'd expect that if $L_f = \{(a, b) \in A \times B : f(a) = b\}$ and $L_g = \{(b, c) \in B \times C : g(b) = c\}$ are decidable, then $L_{g \circ f} = \{(a, c) : \exists b \in B s.t. f(a) = b \wedge g(b) = c\}$ should be decidable as well.

This seems to me like a natural question to ask of any class of languages. Is it in fact a reasonable question? If not, why? If it is, is there a better way to frame it, one that would make it more clear what we're demanding?


texts: What's the Big O runtime of a DFS word search through a matrix?

texts:
The problem is to try and find a word in a 2D matrix of characters:

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:

board =

['A','B','C','E'],

['S','F','C','S'],

['A','D','E','E']

Given word = "ABCCED", return true.

Given word = "ABCB", return false

Source: https://leetcode.com/problems/word-search/description/*

Solution:

static boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];

        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0)){
                    return true;
                }
            }
        }

        return false;
    }

    private boolean search(char[][]board, String word, int i, int j, int index){
        if(index == word.length()){
            return true;
        }

        if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || board[i][j] != word.charAt(index) || visited[i][j]){
            return false;
        }

        visited[i][j] = true;
        if(search(board, word, i-1, j, index+1) ||
           search(board, word, i+1, j, index+1) ||
           search(board, word, i, j-1, index+1) ||
           search(board, word, i, j+1, index+1)){
            return true;
        }

        visited[i][j] = false;
        return false;
    }

Assume we use a DFS to recursively check each character's 4 neighbours. What would be the correct runtime? I've read various thoughts on this but nothing conclusive.

My thoughts:

We have to check every character in the MxN matrix, so that gives us at least M*N.

Then, for each character, we check in four directions for the length of the input string, so that would give us 4*len. But then for each neighbour we go to, we potentially check each of its neighbours too, but only if they haven't already been visited. This is where I get slightly confused and I'm not sure how to calculate the correct runtime for this.

(Edited question to add exact problem and solution)


texts: Most Efficient Way to List All $n$-bit Permutations

texts:
Suppose we are tasked with expressing a randomized list of all numbers up to but excluding $2^n$ (ie. a random list of all n-bit numbers).  What are some efficient ways to do such a listing using as few bits as possible?

Attempt: My thought is that the verbose listing of all $n$-bit numbers has a lot of redundancy, so if we start by listing all $2^n$ numbers, $2^{n-1}$ of those numbers will have a number that is identical except for one bit (that has been previously listed)––so we can drop the $n^{th}$ bit of those $2^{n-1}$ numbers.  Now among that same set of $2^{n-1}$ numbers, there will be $2^{n-2}$ values that will have a number  that is identical until the last two bits, so we can drop the $n-1^{th}$ bit of those $2^{n-2}$ numbers as well.  Continuing on iteratively, we can find $2^{n-k}$ numbers that can have the final bit dropped, with $k=1,2,3,4,...n$. Finally, there is one number that can be eliminated entirely (intuitively, this makes sense because the last number in a known set can always be determined if we know all others).

Here is an example that lists all 3-bit numbers (in increasing order):

000
00
010
0
100
10
110
.

It seems like we can model the number of bits this method uses as such:
$$2^{n-1}n + 2^{n-2}(n-1) + ... + 2^1(2) + 2^{0}(1) = \sum_{k=0}^{n-1} 2^k(k+1) = 2^n(n-1)+1$$

(saving $2^n -1$ bits from the verbose $2^n*n$ version)


texts: Variation to spanning tree called Group Spanning Tree

texts:
Suppose we have a complete graph, with say 100 nodes. We divide the nodes in the graph into groups, for example 10 nodes in each group, identified by color. We want to obtain a minimum spanning tree under the constraint that at least one node will be present from each group ("group spanning tree").

How to  write an efficient algorithm for this, making sure it is a tree (no cycles), without iterating over the entire node set, on every pass checking presence of cycles, and also making sure that at least one node from each group is represented?


texts: Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$

texts: Given array $A$ of size $n$, we want to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$. Is there way to speed this up rather than the standard $O(n^3) $ calculation with 3 for loops. I haven't worked with sums so I don't know their properties, but I was thinking if there is some way to rewrite the formula to get faster calculations.


texts: Winning strategy of Nim game when picking from multiple piles is allowed

texts: I am studying with Game theory right now. In Nim game, in any turn, a player can move any number of stones from any one pile. I am wondering what might be the winning strategy of first player if in any move, a player can pick any number of stones from one or more piles? In this case, how the xor = 0 rule will work? Both are playing optimally.


texts: Complexity of Hamiltonian path and clique problem

texts:
I came across this question. If we want to check if a graph contains both Hamiltonian path and clique. Would this problem be NPC.

I knew that clique contains a Hamiltonian path and both problems are NPC, but I am uncertain if something would be different if we check it in same time.


texts:
How would I go about using Cartesian construction to find the intersection between a PDA and a DFA?

Is there another term for Cartesian construction? Would it be similar to the procedure for finding the intersection/union of 2 DFAs?


texts: Code families with efficient decoding algorithms

texts: Which families of the error correcting codes have an efficient decoding algorithm? I know that decoding a general linear code is NP hard (the general decoding problem). I also know that Goppa codes and alternate codes have such algorithms due to Patterson. Hamming codes also belong to this category. If someone can provide a link or some source of list of such families that would be really helpful.


texts: How to decide if two conjunctive queries cannot have any result in common

texts:
Consider the following queries:

Q1: age > 18 & age < 24 & gender = 'male'

Q2: age > 25 & gender = 'male' & major = 'CS'

Q3: age = 20 & major = 'CS'

Clearly, given any database instance $D$, we can decide $Q1(D) \cap Q2(D) = \emptyset$ and $Q2(D) \cap Q3(D) = \emptyset$. However, we cannot decide about the result of $Q1(D) \cap Q3(D)$.

I'm aware of query containment, in where the result of one query always is a subset of the results of another query. Also, I'm aware of query equivalence, in where the results of two queries should be exactly the same given any database instance.

However, I'm looking for an algorithm/terminology for my case, where before evaluating the two queries, I can decide the intersection of their results are always empty. Indeed, due to conflicting selection conditions, they cannot have any common result.


texts: Solution for a combinatorial minimization problem

texts: Let's say we have an inequality, $p \le {a \choose b}$ where $p$ is a fixed constant and $a, b$ are variables. The problem is that, we are trying to find the minimum $a$ with respect to the inequality $p \le {a \choose b}$. Is there a closed form solution (can be approximate as well/doesn't have to be exact) for that combinatorial optimization problem?


texts: Intuition behind recurrences with growth O(n log n) vs O(n²)

texts:
Been trying to get the intuition behind why two very similar recurrence relations don't follow a pattern I would expect. They are pretty well known relations:

Relation 1 -

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

Relation 2 -

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

When sketching out a tree for the first recurrence, the way I was taught to think that at every level of a tree, you are doing some amount of work.

Height 1 - do some O(n) of work
Height 2 - do some O(n) of work
Height log(n) - do some O(n) of work

Now In my head, If i visualize the work as a sum of all the work done, it seems like its $O(n\log(n))$ of work being done, which according to the master theorem is correct.

However, using the same intuition for the second recurrence is wrong as we know the master theorem tells us the answer is $O(n^2)$.

Any reason why the intuition seems to be correct for the first recurrence, and why it is wrong for the second?


texts:
I'm trying to prove NP-hardness of 3 SET PACKING, which is a following problem: given a family of sets where each set contains 3 elements, decide whether the family contains k sets that are pairwise disjoint.

I tried reducing 3 SAT, but to now avail, but reduction of any other NP-complete problem would be helpful.


texts: Computational Complexity of Integer Linear Program [with Fixed number of 'Pure Constants']

texts:
This is a follow up to the previous Question: Conditions for Linear Diophantine Equations to always have a solution

It was established in the above's answer that obtaining or testing for the existence of an solution of an ILP in $\mathbb N$ is an NP Hard Problem. This in turn makes obtaining solution for a (LDP) Linear Diophantine Problem (where $v$ > $n$) in $\mathbb N$ an NP-hard Problem too.

Now given the restricted ILP Problem with an additional constraint:

The number of unique pure constants (i.e. ones without variables, denoted by $c_0 below) permitted in any system has an fixed upper Bound (say 2) where equations are of the form:

$c_0 + c_1 x_1 + \dots + c_k x_k \ge 0$

Is this restricted version of ILP still NP-hard?


texts:
Define a "non-standard" flow to be a flow where the quantity flowing through an edge may be negative.

  Formally, given a directed graph $G$, and two designated and distinct
  vertices $s$ and $t$ (such that no edges are leaving $t$, and no edges
  are entering $s$), a non-standard flow $f : G_E \to \mathbb{R}$ is a
  valuation on the edges such that

  For each $v \in G_V\setminus \{s, t\}$, the sum of the values of $f$
  on the edges entering $v$ is equal to the sum of the values of $f$ on
  the edges leaving $v$.

Assuming all the capacities are positive, does the Max-Flow Min-Cut theorem still hold for non-standard flows?

Furthermore, is there a network with positive edge capacities, such that the maximum non-standard flow through the network is larger than the maximum (standard) flow through the network?

The standard proof for Max-Flow Min-Cut theorem uses the non-negativity of the flow to claim that each flow is smaller than each cut. I would guess that this tells us that the counterexample (if any) would have a cut that has negative flow into its incoming edges.


texts: How to determine big O of a variable loop

texts:
I want to classify the runtime of this function in big O notation. This function is multiplying two whole numbers and checks the in binary digits of the multiplicand. And adding the multiplier to the product a specific number of times if the bit is '1', dependent on the weigth of that bit.

I'm trying to figure out the classifcation of the for-loop. Since the while-loop will go through all bits of the multiplicand the while-loop will probably have a runtime of $O(n)$ whereas $n = \#digits$. The inner loop will execute $2^0, 2^1, 2^2, 2^3, 2^4...=1, 2, 4, 8, 16,...$ if the bit will be a '1'. So in total the for-loop will execute $\sum_{i=0}^{n-1}2^i$ steps, in the worst-case (if all bits are ones).

My question is, how do I write this for-loop in big O notation?

def mul(multiplier,multiplicand):
    product = 0
    pot = 1                             # power of two
    while (multiplicand > 0):
        q = divtwo(multiplicand)
        q1 = (q + q)
        if (q1 != multiplicand):        # is odd => bit 1
            for i in range(0,pot):
                product = (product + multiplier)
        multiplicand = q
        pot = (pot + pot)
    return product

P.S.: I'm not allowed to use "/" or "*". Only "+" and "-".


texts: Algorithm for finding a mouse hole in a wall in O(n) time

texts:
There is this question:

  As a result of the US Election, a wall is built along the entire Canadian border. You have been told
  there is a mouse hole in the wall, but it can only be seen when you are standing in front of it. Your
  task is to find the mouse hole by walking along the wall; however, you are standing in Minnesota
  and do not know whether the hole is East or West of your current location.

  Give an algorithm that will allow you to find the mouse hole in O(n) steps, where n is the (unknown
  to you) distance in steps from your initial location to the mouse hole.

I was thinking that to find the mouse hole in O(n) steps, I would have to go both East and West at the same time.

But seeing that I can't do this (or maybe I can?), I thought that regardless of direction I first take since I'm traveling around the US border and then around the Canadian border, I would have traveled a linear time. I'm also thinking that this problem might resemble a graph?

How can I go about writing an algorithm to describe this?


texts: NFA that ends with 0 and doesn't have 11 after the first 0

texts:
So as the title says i m trying to find this NFA. So far i thought to make an NFA that "guesses" what comes after the first 0 and i got this:

After some time trying to get rid of all the extra (7 !) states i put in i got to this beauty:

But now i cant figure out how to get rid of the one extra state. Also if you have any tips on how to go to simpler NFA's instead of what i did (like a thought process for this problem) i would appreciate it a lot. Thank you


texts: arithmetic coding for generating random number with desired distribution

texts:
Hi i want to convert random number with uniform distribution to desired distribution using arithmetic coding. It has been done in the following research paper called arithmetic distribution coding available in the following research paper.
https://arxiv.org/pdf/1408.3931.pdf
 Kindly can any one guide me how come arithmetic coding has been exploited in achieving a desired distribution. The main purpose of this is to optimized the distribution of data for transmission in gaussian noise channel.


texts: How to rule bactrack research on alphametric puzzles?

texts:
I have a funny aphametic problem:
  I A
+ I A
-----
  P B

I have to find which are the values of the letters. I know I can try backtrack with forward research, MRV heuristic and degree heuristic. Yet I'm not sure how to apply them on cryptarithms/alphametrisms.
My attempt
I tried to find the letters values with backtrack research.
Domains

$D(A) = D(I) = \{1,..., 9\}$
$D(P) = D(B) = \{0,..., 9\}$

Constraints

$10(I + I) + (A + A) = 10P + B$

So I did iterated step by step by hand on the values:

$A= \{I = 1\} \rightarrow$ consistant

$A = \{I = 1, A = 0\} \rightarrow$ consistant

$A = \{I = 1, A = 0, P = 0\} \rightarrow$ inconsistant

$A = \{I = 1, A = 0, P = 1\} \rightarrow$ inconsistant

$A = \{I = 1, A = 0, P = 2\} \rightarrow$ consistant

$A = \{I = 1, A = 0, P = 2, B = 0\} \rightarrow$ inconsistant

$A = \{I = 1, A = 0, P = 2, B = 1\} \rightarrow$ inconsistant

$A = \{I = 1, A = 0, P = 2, B = 2\} \rightarrow$ inconsistant

$A = \{I = 1, A = 0, P = 2, B = 3\} \rightarrow$ inconsistant car $A+A = 0 \neq 3$
... until we change the value from A to 2 (because I already equal to 1) so far I don't know the answer.

It seems it's going to take ages. Am I doing it right ?
Maybe the following graph might be of any help ?


texts:
I am very familiar with Dijkstra and I have a specific question about the algorithm. If I have a huge graph, for example 3.5 billion nodes (all OpenStreetMap data) then I clearly wouldn't be able to have the graph in memory, so the graph is stored on disk in a database.

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

Fetching the adjacency list of each vertex visited would require about 1,500 database queries per 10,000 nodes according to my statistical data, so that clearly is not how they do it. That would be way too slow.

How do they do it? I am trying to implement it myself.


texts:
According to Efficient algorithms for interval graphs and circular arc graphs there is an $O(n \log n)$ algorithm for finding the max clique in an interval graph, assuming you have the interval model. Unfortunately, neither the paper nor the references actually elaborate on what the algorithm is, beyond saying that you can modify the well-known algorithm for optimally coloring interval graphs (where you greedily color the graph in the order generated by sorting the intervals lexicographically) to compute the max clique. This makes sense, as the largest color used in an optimal coloring is the size of the max clique in a perfect graph (and interval graphs are perfect). Unfortunately, beyond that, I am lost as to how to compute the max clique. The obvious approach is to modify some data structure every time the max color increases, but I can't figure out precisely what data structure to use or how to modify it.

Does anyone know a reference for this algorithm or can reinvent a description of it?


texts: Simple description of circularities in Knuth original attribute grammar paper

texts:
Knuth's original attribute grammar paper (title: Semantics of Context-Free Languages) introduced three types of circularity. More specifically section "Testing for circularity" page 134-5 figures 3.1-3. I am wondering if it's possible someone would explain in simple terms the three types of circularities. I am very confused.

I think there should be either direct or indirect dependencies.

By direct, I mean

A.attr := B.attr
B.attr := A.attr

By indirect, I mean

A.attr := B.attr
B.attr := C.attr
... maybe more steps ...
C.attr := A.attr


texts: Büchi automaton with modified acceptance condition

texts: Consider a Büchi automaton $\mathcal{A}$ with the modified acceptance condition, that an $\omega$-word $\mathcal{w}$ is accepted by $\mathcal{A}$ iff every run $\rho$ of $\mathcal{A}$ on $\mathcal{w}$ is accepting (rather than at least one run being accepting). I need to show that this automaton also accepts only $\omega$-regular languages. How do I go about doing that?


texts:
Urzyczyn: Inhabitation in Typed Lambda-Calculi (A syntactic approach) gives a proof that STLC inhabitation problem is in PSPACE (section 2, lemma 1). I don't understand certain aspects of the proof:

Lemma: There is an alternating polynomial time algorithm to determine whether a given type A is inhabited in a given basis $\Gamma$ in the STLC.

Proof.If a type is inhabited, it is inhabited by a term in a long normal form.

Question 1: what is a long normal form.

To determine if there exists a term $M$ in a long normal, satisfying $\Gamma \vdash M:A$ we proceed as follows:

If $A = A_1 \to A_2$ then $M$ must be an abstraction $M = \lambda x:A_1. M'$. Thus, we look for an $M'$ satifying $\Gamma, x:A_1 \vdash M':A_2$.

If $A$ is a type variable, then $M$ is an application of a variable to a sequence of terms.

Question 2: I thought there weren't type variables in the STLC.

We nondeterministically choose a variable z, declared in $\Gamma$ to be of type $A_1 \rightarrow \ldots \rightarrow A_n \rightarrow A$. If there is no such variable , we reject. If $n = 0$ then we accept. If $n > 0$, we answer in parallel the questions if $A_i$ are inhabited in $\Gamma$.

Question 3: it doesn't matter the actual typing of $z$ in $\Gamma$ right? as long as we consume it and don't use it again in this step.

This alternating procedure is repeated as long as there are new questions of the form $\Gamma \vdash ? : A$. We can assume that all types in $\Gamma$ are different. At each step of the procedure, the basis $\Gamma$ either stays the same or expands. Thus the number of steps does not exceed the squared number of subformulas of types in $\Gamma,A$.

Question 4: why? could someone spell out some steps of the reasoning here?


texts:
Let's say we have five packets

p1 p2 p3 p4 p5

to be sent sequentially:
and for some reasons, p3 got delayed so it the the last packet to arrive recevier.
so below is the receiving order on the receiver's end

p1 p2 p4 p5 p3

and according to the Go-Back-N Protocol, the receiver will only send acknowledge of p2 when it receive p5.
then the receiver receives p3 right after p5, and then it sends acknowledge of p3 to the sender.
But there will still be a timeout and the sender still has to re-send p4 and p5,even though the receiver did receive all packets, isn't this Go-Back-N Protocol really inefficient?


texts: In a weighted graph $G(\mathcal{V},\mathcal{E})$ where $w(i,j)$ is the weight of the edge $(i,j) \in \mathcal{E}$. How can I find a maximum weighted matching with a specific size (i.e specific cardinality).


texts: What are the sufficient conditions for weighted binary code to be self compliementary?

texts:
I was going through binary codes and found out that if the weighted binary code is self complimentary then it's weights addition will be equal to 9. Is the converse true? If not then what are the sufficient conditions for making a weighted binary code self complimentary. My research was in vain. Please help and clear my doubt.

For example: 3321 is self complimentary code. 3+3+2+1 = 9


texts: Master Method: $T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$

texts:
I'm having a hard time trying to understand how to solve this recurrence relation using the Master Method:

$$T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$$

First, we have:

$a = 10,\ b = 2$ so we have $n^{\log_2^{10}} = n^{\lg10}$

Now we need to find how $f(n)$ compares to $n^{\lg10}$.

And here I'm stuck. What do I have to pay attention to in order to know whether I'm dealing with Case 1 (and look for $O(n^{{\lg10} - \varepsilon}))$ or Case 3 (and look for $\Omega(n^{{\lg10} + \varepsilon})) $ of the method?

My attempt:

From what I know $\log(n) < n^\varepsilon\quad \forall \varepsilon > 0$. So

$$\frac{1}{\log(n)} > \frac{1}{n^\varepsilon}$$
$$\frac{n^4}{\log(n)} > \frac{n^4}{n^\varepsilon}$$

$$\implies \frac{n^4}{\log(n)} = \Omega( n^{4-\varepsilon})$$

but I have no idea how to relate this (assuming no mistakes) with one of the two cases. In Case 1 we deal with $O(\cdot)$ and not $\Omega(\cdot)$ while in the 3rd Case the form of the exponents doesn't seem to match.


texts: Create an array minimizing sum of square deviations to another array

texts:
Problem

Let y be an array of float numbers (of length $n$) bounded in the range [0,1]. I am trying to compute the array x that respects the following criteria:

x must be of length $n$ too
x must also be bounded in the range [0,1]
No two values of x must be closer to each other than $\epsilon$. That is $ \epsilon \le x_i - x_j  \space \forall i \neq j$

So far, there are an infinite number of possible solutions. There is therefore a statistic to optimize though.

The sum of square differences between x and y must be minimized. That is $\sum_{i=1}^n (x_i - y_i)^2$ must be minimized.

In short

I want to find x given y such as

$$ \begin{align}
\text{minimize}& & f(\mathbf{x}) &= \sum_{i=1}^n (x_i - y_i)^2 \\
\text{subject to}& & x_{j+1} - x_j &\geq \varepsilon, j = 1, 2, \ldots, n-1 \\
& & min(x) &\geq 0 \\
& & max(x) & \leq 1 \\
\end{align}$$

Expected Output 1

$y = [0,\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{3}{4}]$

$x = [0,\frac{1}{2}-\epsilon,\frac{1}{2},\frac{1}{2}+\epsilon,\frac{3}{4}]$

Expected Output 2

$y = [0,0,0]$

$x = [0,\epsilon,2\cdot \epsilon]$

Of course, there are cases where no solution exist. Typically, in the second example if $2\cdot \epsilon > 1$, then there are no solution. In such case, the program should throw an error.

Can you give me advice on how to go about solving this problem?


texts: Do unconditional branches cause control hazards?

texts:
Do unconditional branches, such as jump/goto instructions cause control hazards? If so, why?

I am wondering because if unconditional branches did cause control hazards, that is like saying if A were the jump foo instruction and another instruction B was the first one under foo:, B would have a control dependency on A. While this is technically true, I don't see how this would cause a hazard in a pipeline since we know with 100% certainly that B will be executed since an unconditional jump instruction A preceded it.


texts:
I have an example: m = n = p = (-1) ^ (m + n + p) * (m + n + p);
I don't know what to do with multiple "=". Should I treat them as a sign with the lowest priority or just put them in end of the answer?
That's what I get when I treat them as sign with the lowest prioryty:
M,N,=,P,=,1,NEG,M,N,+,P,+,^,M,N,+,P,+,*,=
Could you check my answer?


texts: 2 phase locking with added increment mode

texts:
Suppose that a DBMS recognizes increment as an atomic operation, in addition to the read and write operations. Let $V$ be the value of the data item $X$.

The operation  increment (X) by c sets the value of $X$ to $V + c$ in an atomic step. The value of $X$ is not available to the transaction unless the latter executes a read.

The table below shows the lock compatibility matrix for the three lock modes: share mode , exclusive mode,and increment mode.

        |    S  |   X   |   I  |

   -----------------------------
   S    |  true | false | false|
  ------------------------------
   X    | false | false | false|
  ------------------------------
   I    | false | false | true |
  ------------------------------

a) Show that ,if all the transactions lock the data that they access in the corresponding mode , the two phase locking ensures serializability.

b)  Show that the inclusion of increment mode allows for increased concurrency.

Where I got stuck:  According to the lock compatibility matrix given in the problem, while a transaction is performing an increment operation on $X$ (acquired an increment lock) other transactions can simultaneously acquire increment lock on the same item $X$ and perform increment operations just like shared mode (where if a transaction holds read lock on an item $X$ other transactions too can acquire read lock on $X$ ) where as increment lock is conflict to read and write operations. So suppose the following non-serial schedule which follows 2PL

    T1          |           T2

 lock-s(x)
 read(x)
 lock-i(x)
 x = x + v
                           lock-s(y)
                            read(y)
 lock-x(x)
 lock-s(y)
 write(x)
 unlock(x)
                          lock-i(y)(cant acquire this lock since read lock on y is not released in transaction t1 ,hence waits)
                          y = y + v

  read(y)
 lock-i(y)(cant acquire this lock since read lock on y is not released in transaction t2 ,hence t1 also waits)

 y = y + v
 lock-x(y)
 write(y)
 unlock(y)

likewise both transactions enter into deadlock. No matter what examples I try to take I get a deadlock. Can anyone please give me a schedule where the transactions don't enter into deadlock and they follow the 2PL protocol.


texts:
$L = \{ \langle M \rangle \mid \epsilon \in L(M) \}$, where $M$ is any Turing machine.

Why is the above problem undecidable? Can't we just check whether the initial state is a final state and say the TM accepts $\epsilon$ if the initial state is the final state else it doesn't? We can also just check if the TM goes to an accepting state on the blank symbol.


texts: If a problem A ≤p B, then that B ≤p A, prove or disprove

texts: I think the intuition is to disprove this by counter example, but what are 2 specific well known problems I can use as counter example?


texts: Are there two kinds of polynomial hierarchy collapses?

texts:
It seems to me that there are two different situations which get called ``PH collapse",

(1) That $\exists i \geq 1$ s.t $\Sigma_i ^p = \Sigma_{i+1}^p$
(2) That $\exists i \geq 1$ s.t $\Sigma_i^p = \Pi_i^p$

Are these two different independent situations?

AFAIK the only natural relation is that $\Sigma_i^p \subseteq \Pi_{i+1}^p \subseteq \Sigma_{i+2}^p$ and I don't think this is enough to make the two above scenarios be equivalent.

Is there any natural relation even between $\Sigma_i^p$ and $\Sigma_{i+1}^p$ or between $\Pi_i^p$ and $\Pi_{i+1}^p$? For some $k > i$, if one shows that $\Sigma_k^p \subseteq \Sigma_i^p$ does that say anything about $\Pi_k^p$ vs $\Sigma_i^p$ ?

Do both these scenarios lead to the conclusion that $PH = \cup _{j \geq 1} \Sigma_j^p = \Sigma_i ^p$ ? (If yes, then can someone kindly help with the proof?)

Roughly I guess the proof has to go like this :

That inductively assume that for some $k > i$ one has shown that $\Sigma_j^p \subseteq \Sigma_i^p$ $\forall j$ s.t  $i\leq j \leq k$. Now sit at the threshold of the inductive hypothesis — and take some $L \in \Sigma_{k+1}^p$ and by truncating the first quantifier construct a language $L'$ such that $\langle x,u_1\rangle \in L'$ iff $x \in \Sigma_{k+1}^p$ with its first existential quantifier fixed to $u_1$. This makes $L' \in \Pi_{k}^p$

Now I don't know... something needs to be claimed about $L' \in \Pi_{k}^p$ to show that $L \in \Sigma_i^p$. But I don't see what goes here.


texts: How to prove correctness of a shuffle algorithm?

texts:
I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased).

The first method I use is to construct the entire list of elements and then do a shuffle on it (say a Fisher-Yates shuffle). The second method is more of an iterative method which keeps the list shuffled at every insertion. In pseudo-code the insertion function is:

insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

I'm interested in how one goes about showing the fairness of this particular shuffling. The advantages of this algorithm, where it is used, are enough that even if slightly unfair it'd be okay. To decide I need a way to evaluate its fairness.

My first idea is that I need to calculate the total permutations possible this way versus the total permutations possible for a set of the final length. I'm a bit at a loss however on how to calculate the permutations resulting from this algorithm. I also can't be certain this is the best, or easiest approach.


texts: Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?

texts:
An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.)

However, there are
different kind of algorithms, such as deterministic, non-deterministic,
and randomized algorithms, and possibly others.

Are these algorithms running on deterministic Turing Machines, or do
they have to be run on specific machines? For example:

Are nondeterministic algorithm algorithms on a deterministic Turing
machine? I heard that they are not, but are on nondeterminisitic
Turing machines, but I forget where I heard it. Or I might be wrong.
Are randomized algorithms algorithms on a deterministic Turing
machine?


texts:
∃x (P(x) → Q(x)), ∃x P(x) ⊨ ∃x Q(x)
I am trying to find the invalidity of the following sequents.
A = Set of natural number
P(x) : x is odd
Q(x) : x is not divisible by 2

What i don't understand is how can this be invalid ? There will always exist an x that is not divisible by 2 . How can we make this false.
 If i assume another model such that
A = {0,1}
P(x) = {0}
Q(x) = {}
 Now in this case if we assume q(x) to be an empty set it will not be in the model .. So the invalidity shows .Does that make sense?


texts: Given the phrase "Where NONE of the following are TRUE" and two statements how should a boolean logic be composed?

texts:
Let's have two statements

(value > 10)
(value < 25)

And a list of items with the following values

10
20
30

This is what a truth table would give

Item  Value  (value > 10)  (value < 25)
----  -----  ------------  ------------
1     10     FALSE         TRUE
2     20     TRUE          TRUE
3     30     TRUE          FALSE

Example 1

Where ALL of the following are TRUE
   value > 10
   value < 25

This one is easy and we get the following

Where (value > 10) AND (value < 25)

The result is then a single value of 20

Example 2

Where NONE of the following are TRUE
   value > 10
   value < 25

This is where I am not sure of what to generate.

This would be "simple" as it is only a NOT of the whole expression

Where NOT ((value > 10) AND (value < 25))

However, the result is then two values (10 and 30)

From what someone would think of NONE of the two statements would be something like:

Where NOT ((value > 10) OR (value < 25))

And the result would be that no items are produced.

What is the correct meaning of NONE here?


texts: If factor isn't found in P-1 algorithm, should upper bound be increased linearly (i.e. +1)

texts: I have seen some implementations of Pollard's P-1 algorithm where the upper bound is only increased by 1 if no factor is found. Such an implementation is described here. Is it sort of missing the point in terms of efficiency to only increase by 1, or is is it sill better than trial division for finding a factor? Is what they're implementing in the link really the P-1 algorithm? I've seen other sources make it sound that a certain amount of intuition is needed when choosing parameters and you shouldn't just increase by 1 each time. Am I understanding correctly?


texts:
I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard).

Let's assume that you have proven that a problem Y is NP-Hard, and you have a problem X which you know is in NP, and you would like to solve.

To solve X, which of the following reductions would be carried out?

X -> Y
Y -> X

Which of the following? i.e. would you reduce X to Y or vice-versa, if you would like to solve X which is in NP, and Y which is NP-Hard?


texts: How to prove that a custom iterative algorithm will determine all shortest paths to a graph node?

texts:
I'm not sure what the following algorithm does but it seems that it calculates the shortest paths from a node $t$.

Initially we're given a graph $G=(V,E)$ with non-negative weights $c(e) \ge0$ for each edge $e\in E$ and we're given a node $t\in V$.

The algorithm is as follows:

  Initialize array $A$ such that $A[v] = 0$ if $v=t$ else $A[v]=\infty$.

  Outer loop which is repeated continually

  $\quad$ Inner loop: we scan all edges in lexicographical order and for every $e=(u,v)\in E$ we $\quad$ do the following:

  $\qquad$ if $A[v] >A[u]+c(e)$ then $A[v] =A[u]+c(e)$

  $\quad$ if no updates were performed in the inner loop the algorithm exits.

I need to prove by induction what the algorithm does. For example for the following graph below and if $s=b$ the initialization of $A$ will be as follows:

Then the first run of the inner loop would be:

1) $A[1]$ is not bigger than $A[0]$ so we do nothing

2) $A[2]$ is bigger than $A[1]$ so $A[2]=2$

3) $A[3]$ is bigger than $A[2]$ so $A[3]=5$

The next time the inner loop will not make any updates because all the reachable nodes were already updated.

I'm not really sure if I understood correctly what the algorithm does and how to prove this inductively.

How does the fact that the algorithm checks nodes in lexicographical order come into play?


texts: What are precisely computational effects?

texts:
I'm really confused with definition of computational effects. What I knew and understood about computational effect were only that they're impure computation, but someone noticed me that computational effects includes continuation which doesn't seems to be impure. please someone reason these things.

Sorry for babbling, here is my actual questions:

What is formal(or at least precise) definition of computational effects?
If computational effects are impure things, then why continuation is included? is continuation impure?

Thx.


texts: What does it mean to have tokens at a state in a balancing network?

texts:
I was assigned as homework:

  Suppose we have a width-w balancing network of depth $d$ in a quiescent
  state $s$ called $B$. Let $n = 2^d$. Prove that if n tokens enter the network
  on the same wire, pass through the network, and exit, then $B$ will have
  the same state after the tokens exit as it did before they entered.

However, I do not understand what the question is asking (please don't actually do the problem).

I have followed chapter 12 of the art of mutlicore programming, and its still unclear what the question is asking. Let me give you my thoughts (and confusions):

What does it mean by $s$ and $B$? According to the textbook, a balancing network is quiescent if every token that arrived on an input wire has emerged on an output wire (which makes sense because we only care when the tokens pass the network, not their order). Does a quiescent state refer to which cables the tokens have entered? Or since the order doesn't matter it just means that the same number of tokens that entered left the network?

What do they refer to as "a state"? Does it means were the tokens are located and which wires they left or if we only care about quiescent states, that the total number of tokens at the beginning and the end is the same?


texts: How do I test if a polygon is monotone with respect to an arbitrary line?

texts:
Definition: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice.

Given a polygon $P$, is it possible to determine if there exists any line $L$ such that the polygon $P$ is monotone with respect to $L$? If yes, how?

Previously, I asked a related question (where I asked how to determine if a polygon is monotone with respect to a particular line), but now I am interested in the case when $L$ is not given or specified in advance.


texts: Iterative permutations, but favoring swaps of early elements

texts:
I'm familiar with the Steinhaus–Johnson–Trotter algorithm, which allows for the iterative yielding of permutations of a sequence by performing a single swap per iteration.  It has the behavior, however, that it tends to swap elements further along the sequence early in the iteration.  For 4 elements, my understanding is that the first 6 permutations will be:

$1,2,3,4$

$1,2,4,3$

$1,4,2,3$

$4,1,2,3$

$4,1,3,2$

$4,3,1,2$

What I'd like to know is whether there is similar iterative algorithm, using relatively simple changes (though obviously can't be single swaps) that yields a sequence:

$1,2,3,4$

$2,1,3,4$

$1,3,2,4$

$2,3,1,4$

$3,1,2,4$

$3,2,1,4$

Per request, here is my attempt at a better definition of the desired result:

Start with the initial sequence of $n$ elements and yield it.
For each $i \in \{2..n\}$, then $k \in \{1..i\}$
Take the element $x_i$ and place it at position $i-k$.  We will now consider the first $i$ elements and keep the remaining $n-i$ elements the same.
Yield all permutations of the remaining $i-1$ elements (using these rules) surrounding the position $i-k$.

Basically the goal is to permute each initial sequence fully before continuing to permute with later elements.


texts: What is the name for this load balancing algorithm?

texts:
While working on a practice problem I "organically" came up with a method that does well at solving my load balancing problem. I do not know what the official name is for it, but I would like to read more on it, I think maybe it is a greedy algorithm similar to the least connections algorithm.
Given m resources and n consumers where m << n.
The object is to balance the n consumers on the m resources such that the resources are equally utilized.
At each balancing step I do the following:

sort resources by utilization ascending.

sort consumer by consumption descending.
While there are unprocessed consumers, place the greediest consumer on the least utilized resource. Repeat with each next greediest and each next least utilized. When the most utilized resource is given a consumer, wrap around and still continue placing using the ordering. Do this until there are no more consumers to place on the resource queue.

Is there a name for this?


texts:
Can anyone suggest a starter book or website where I can find information and examples of putting functions under summation signs into Big Theta. basic Arihmetic , geometric, Quadratic are fine , but I would like to work on examples like
$$\sum_{i = 1}^{\log n} i \cdot n \text{ or } \sum_{i = 1}^{\log n} 10^i$$


texts:
Suppose I want to broadcast from my root to all the nodes in a BFS tree. What is the time complexity of this process? I know that it is suppose to be proportional to the depth of the tree, like O(Depth). A more formal way of saying this could be O(Diameter) or maybe O(Radius of the Root) if you want to be more specific.

However, these parameters do not provide any insight. O(Depth) or O(Diameter) could be O(n) if the tree were a line. Since BFS is not guaranteeing a balanced tree or a binary tree or whatever, it does not give any topological clue to me.

Should I say O(n) then? Or should I say O(Depth) to give a more precise answer?


texts: A canonical representative, for this equivalence relation on matrices

texts:
This question is inspired by Constructing inequivalent binary matrices.

Define the equivalence relation $\sim$ as follows: If $M,N$ are two $8\times 8$ binary matrices (all elements are $0$ or $1$), say that $M \sim N$ if you can transform $M$ into $N$ by a sequence of moves, where each move picks some pair $(i,j)$ and swaps rows $i$ and $j$ and then swaps columns $i$ and $j$.  For example,
\begin{equation}
\left( \begin{array}{ccc}
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 0 \end{array} \right) \sim
\left( \begin{array}{ccc}
1 & 0 & 1 \\
0 & 0 & 0 \\
0 & 1 & 0 \end{array} \right).
\end{equation}
This equivalence relation induces a set of equivalence classes.

Is there a way to define a canonical representative for each equivalence class, so that given any matrix $M$, we can efficiently compute the canonical representative $M^*$ corresponding to the equivalence class containing $M$?  I'm hoping for a simple and efficient algorithm to compute the canonical representative.

For instance, one way to define a canonical representative for matrix $M$ would be as follows: among all matrices $N$ that are equivalent to $M$, choose the one that is lexicographically first.  However, I don't know of any fast way to compute the canonical representative corresponding to a given matrix $M$.  (One could enumerate all matrices that are equivalent to $M$ by trying all $8!$ possible permutations, and then check which one is lexicographically first, but this is inefficient: it requires $8! \approx 2^{15.3}$ steps of computation, which is too much.)  Is there a better approach?

Alternatively, is there a way to define a canonical representative for each equivalence class, so that we can quickly test any given matrix $M$ to determine whether it is in canonical form?  (i.e., there is an efficient algorithm to check this)

A good answer to this question might help solve Constructing inequivalent binary matrices.


texts: How exactly Hashing performs better than a Binary Search?

texts:
The time complexity of a Binary Search is O(log n) and Hashing is O(1) - so I've read. I have also read that Hashing outperforms Binary search when input is large, for example in millions. But I see that log n, when n is around 30 million, is roughly equal to 25.

If for such a large value of n, log n is just 25, then isn't O(log n) roughly the same as O(1)? Because O(1), basically means that the time complexity is constant. So, it could be bigger than or same as 25!?!(here I am assuming that the coefficient of log n, in the actual time usage/consumption function for Binary Search, is less than or equal to 1)

A related question I have, is regarding the calculation of time complexity of a hash algorithm. In all the literature, I barely find any mention of the time complexity of the hash function used and the division required thereafter(to calculate the index of the bucket).

So, exactly how do memory reads/access and computing a fairly complex mathematical operation(as in hash function), compete against each other, w.r.t. time consumption? One memory read/access roughly equates to what kind of basic mathematical operation, in terms of performance?


texts: When can a greedy algorithm solve the coin change problem?

texts:
Given a set of coins with different denominations $c1, ... , cn$ and a value v you want to find the least number of coins needed to represent the value v.

E.g. for the coinset 1,5,10,20 this gives 2 coins for the sum 6 and 6 coins for the sum 19.

My main question is: when can a greedy strategy be used to solve this problem?

Bonus points: Is this statement plain incorrect? (From: How to tell if greedy algorithm suffices for the minimum coin change problem?)

  However, this paper has a proof that if the greedy algorithm works for the first largest denom + second largest denom values, then it works for them all, and it suggests just using the greedy algorithm vs the optimal DP algorithm to check it.
  http://www.cs.cornell.edu/~kozen/papers/change.pdf

Ps. note that the answers in that thread are incredibly crummy- that is why I asked the question anew.


texts: The physical implementation of quantum annealing algorithm

texts:
From that question about differences between Quantum annealing and simulated annealing, we found (in commets to answer) that physical implementation of quantum annealing is exists (D-Wave quantum computers).

Can anyone explain that algorithm in terms of quantum gates and quantum algorithms, or in physical terms (a part of algorithm that depends on quantum hardware)?

Does anyone have any ideas about that?
Please tell me, if you know some links related this question.


texts: How many registers does a computer *need*?

texts:
I read about Why does a processor have 32 registers?, and others. Currently I am messing around with an OS in JavaScript, and wondering how many registers -- or more specifically, how many temporary variable slots -- you need in a computer. How many do you need? Bare minimum, what is theoretically the lower bound? Is it 2? Or is it 8? I read some CPUs had 8 at one point, why did they switch to 32 or more these days? I wonder if you can get by with only 2 registers for all computation. If so, is it very inefficient or something? These are all aspects of the main question.

As a tangent question as to why they need $X$ number, what is the ideal number of registers and why? Is there even an ideal? If not a specific number, what is a measure of idealness when it comes to figuring out how many registers your OS simulator should have. I want to avoid "unlimited" registers if at all possible, since that isn't realistic in actual hardware.


texts:
Consider a MAC protocol (ALOHA, CSMA, TDMA, etc.) that, even for very high loads, always results in a throughput of 1 (normalized with respect to the channel speed).
Why is that not good if the throughput is equal to 1?


texts: How to prove Halting problem is solvable by oracle machine

texts: How can we prove that the Halting problem is solvable by a machine with access to some oracle?


texts: Recursive algorithm to compute a sum of product like function

texts:
I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute.
The formula is as follows

$F_{i,j}(m)=\sum_{t=j}^{m}\left [ x_{ij}.\sum_{k=1}^{m}\sum_{l=j-1}^{m} F_{k,l}(m-ij) \right ]$

It's given that $F_{i,j}(m)=0$ for $m<0$.

Here  $x_{ij}$ is defined as a random number with the property that $0<x_{ij}<j$.

How do I write a recursive algorithm to compute $F_{i,j}(m)$?


texts:
I have a few math courses to pick from in my studies, and I would love some insights on which math courses from the following list are the most relevant for machine learning. I will note - to avoid this question being closed on "opinion based" cause, that my question does not involve which math courses I like or interests me, but being objectively as possible - which math courses are the most relevant for machine learning.

This are the following courses I can choose from:

Numerical Analysis
Ordinary Differential Equations 1
Topology
Theory of Functions of a Complex Variable 1
Linear Algebra 3
Number Theory
Probability for Sciences

Since I know Linear Algebra and Probability are very important for Machine Learning, I will note that I have already studied Linear Algebra 1 and 2 (which include matrices, linear transformations, linear and bilinear operators, normed vector spaces, eigenvalues and eigenvectors, diagonalization, Jordan form, hermitian spaces,  unitary and orthogonal transformations, and some more subjects), while Linear Algebra 3 syllabus' is mainly about groups, isomorphism theorems, Lagrange's theorem, group actions, Sylow's theorems, finitely generated Abelian groups, solvable groups, the symmetric group and free groups.

Also, I already had Probability 101 which is mainly discrete probability and includes basic probability theory, discrete distributions (such as Poisson, binomial, HG and more), random variables, markov's and Chebyshev's inequalities,  expected value, variance and covariance, CLT and Markov chains, while the "Probability for Sciences" course has in its syllabus continues distributions, PDF, MGF, convergence of random variables and convergence in probability, the multi-dimensional normal distribution and some more subjects.

I will also note I have studied the following math courses as well:
Calculus 1 and 2 and Discrete Math.

Thanks!


texts: Dynamic Chromosome Length in Genetic Algorithms

texts:
My inquiry concerns the length of chromosomes employed in genetic algorithms (GA), and more broadly in other classes of evolutionary algorithms.
The chromosome length is fixed throughout a GA's run. However, some work has explored the benefits of altering a related GA parameter: the size of the GA population, which is allowed to vary in size (increase or decrease) from one generation to the next in order to better explore and exploit the search space.
My question is now: given that the population size can change, is there any benefit to altering chromosome size? I haven't really come across any work on this.
I imagine this would have applications in things like cruise stopovers and finding alternate routes to a given destination.
Adding another city for instance in a run of the Travelling Salesman Problem (TSP) using GA would lead to an increase in the search space that must be explored. Take for instance a tour with 10 cities: the size of the search space is 10! = 3628800. Adding an addition city would mean that there are now an additional 36288000 (11! - 10!) tours to consider.


texts: Why are complex numbers needed to define qubits?

texts:
I have started learning about quantum computing, and I have been told that you can forget about the physics and think of qubits as a natural generalization of the notion of bit. According to this view, one should think about a qubit as a generalization of a bit, where the states $0$ and $1$ are in superposition; there is "a little bit of $0$ and a little bit of $1$".
This is all fine, I think, but if I were to model this formally, I would model a qubit as a real probability coefficient $\alpha \in [0,1] \subseteq \mathbb{R}$, representing the amount of $0$ in my qubit (thus $1-\alpha$ being the amount of $1$). Instead, in quantum computing you define a qubit as
$$\alpha_0|0\rangle + \alpha_1|1\rangle$$ where $\alpha_0, \alpha_1 \in \mathbb{C}$, and $|\alpha_0|^2 + |\alpha_1|^2 = 1$.
Given that complex numbers rarely appear in classical computer science, this seems an odd design choice if we are to approach quantum computing from a purely theoretical computer science point of view. I assume that the reason for complex numbers showing up here is that they are strictly necessary in quantum mechanics, but this is quite unsatisfactory of an answer for a theoretical computer scientist. My questions are two:

Is there an intuitive, non-physics way, of justifying these complex numbers?
Is it maybe that restricting to real numbers as coefficients yields a computational model equivalent to classical probabilistic Turing machines (in terms of efficiency)?

I would appreciate references where I could find more about the definition of qubits from a purely TCS point of view.


texts: Map a set of strings to another set of strings, optimise similarity

texts:
Suppose we have a similarity measure s : String x String -> [0, 1] and sets K, L in String with |K| <= |L|. The task is to find an injection f : S -> T such that Sum({s(k, f(k)) | k in K}) is maximised. That is, f should be an injection which maximises similarity.

My naive approach would be to compute all the similarities s(k, l) at once, then use a polynomial time bipartite graph matching algorithm such as the Hungarian algorithm or Ford-Fulkerson algorithm to compute an optimal matching. Here, I would have s be the n-gram similarity function from Kondrak's "N
-gram similarity and distance" paper.

Does anyone know of a cheaper way to go about this? I'm hoping for something which considers the whole sets, rather than pairwise similarity alone.