texts: Understanding the Diameter Constrained MST Problem

texts:
I am interested in understanding the DCMST problem, explained in this paper (http://www.dcc.ic.uff.br/~celso/artigos/cpdcmst.pdf). I don't think I understand it as I should. Here is how I understand it, we have a undirected connected graph $G=(V,E)$, a cost $c$ for every edge $e(i,j) \in E$ and a value $d$ we want to find an minimum spanning tree whose diameter is at most $d$. This paper say's that the diameter is of a tree is equal to the number of edges in
the longest path between any pair of its nodes. Does this mean that the cost or weight of the edges are not considered when computing the diameter, in other words the weights do not add any meaning for the diameter? To compute the diameter we treat every edge as constant $1$? But I would assume the weights have meaning for the MST? Also, what are we minimizing here, the spanning tree or the diameter, because I don't think it can be both?

Clearly, I am misunderstanding something here. Could someone explain this problem in more detail? I've been cracking my head with this problem for some days now.

For example if we find an MST with $k$ diameter less than $d$ , and a spanning tree with a lower diameter than k but it's total weight is greater then the MST we found prior, the correct solution would be the MST because it is most minimum and the diameter constraint is satisfied, and does not need to be the most minimum diameter? or which is the correct solution and why?


texts: Difference between DNS Spoofing and DNS Hijacking?

texts: DNS Spoofing and DNS Hijacking, both of them basically are type of attacks where the request is redirected to some other malicious website or some other web page. But I did not find some concrete difference between them, Can someone please explain the primary difference between DNS Spoofing and DNS Hijacking..


texts: Complexity of inverting a diagonal matrix

texts:
What is the complexity of inverting a $n \times n$ diagonal matrix?
From what I learn in algebra, the inverse of a diagonal matrix is obtained by replacing each element in the diagonal with its reciprocal.
So is it correct to say that the complexity of inverting a diagonal matrix is $\mathcal{O}(n)$?


texts: Is there a name for the knapsack problem with no bound on knapsack capacity?

texts:
I am investigating heuristics for optimising the packing a fixed number of knapsacks with a set of items of defined weights, however the knapsacks do not have a defined capacity limit. The objective of the optimisation is instead to find a configuration which minimises the difference in weights between the loaded knapsacks.

This differs from the traditional bin packing problem as it does not have an unlimited number of bins.

This seems to be a variant of the task scheduling problem, without a requirement for ordering.

Is there an existing name for this variant of the knapsack problem? Is it just the multiprocessor scheduling problem?

Thanks.


texts: probablistic procedure to permutate array

texts:
input : $array[1...n]$
output: permutated array
Our algorithm should be probablistic and complexity should be $O(n)$.

Could you give me hint ? My weakness is probability theory and it is why I have a problem.


texts:
If I have a constraint like $y_1 + y_2 +\dots + y_n = k$ for positive integers $y_i$, how would I minimize
$$\quad\frac{x_1 }{ y_1} + \frac{x_2 }{ y_2} + \frac{x_3 }{ y_3} + \dots + \frac{x_n }{ y_n}$$
 if all of the $x_i$ are given?

One can assume that $n\le5\cdot10^5$ and $k\le10^{12}$.


texts: What's the name of this packing problem?

texts:
I'm trying to pack sets of intervals, to find distinct buckets of intervals. The buckets should not be overlapping.
For example if I have these intervals:
A: [ [0, 10] ]
B: [ [1, 3], [5, 7] ]
C: [ [8, 10] ]

I want to get the following result:
[0, 1]: [A]
[1, 3]: [A, B]
[3, 5]: [A]
[5, 7]: [A, B]
[7, 8]: [A]
[8, 10]: [A, C]

What's the name of this problem?


texts: How to do atomic operations on systems that don't support it?

texts:
I need to sync data with WebDAV and other similar backend that do not have a concept of atomic operations. In some cases, I might need to read a file, change its content and write it back. And of course, I want to make sure that no other client read and write the same file in the meantime.

I'm wondering if there's any general technique to handle this?

I thought about having a lock file and if that file is present, no other client can write to the backend. The problem is that there could also be race conditions when creating the lock file: first I need to check if it exists and, if it doesn't, create it. But of course, another client might be doing the same operatons at the same time.

So any idea how this can be handled in general? (It doesn't have to language or OS specific as the backend could be anything, like ftp, scp, etc.)


texts: Is the halting problem undecidable or unrecognizable?

texts:
Is the Halting problem in the class of undecidable problems, or it is just in the set of unrecognizable problems?

I understand that if it is undecidable, then it is also unrecognizable. I have seen the two being used interchangeably, however I believe it is possible for a language to be recognizable but not decidable, so was hoping for clarification


texts:
From Wikipedia, Regular Language

All finite languages are regular.

and Also Regular Grammar, is a way to describe the Regular Language

Right regular grammar (also called right linear grammar).
Left regular grammar (also called left linear grammar).

From Wikipedia its Example :  a* b c* can be described as Regular Grammar..
but it generate infinite number of 'a's and infinite number of 'c's.
Recall Regular Language can be described by Regular Expression and Also Finite Language ..


texts: Any barrier result for this kind of (non-relativising) technique?

texts:
We think that non-deterministic machines are more powerful than deterministic machines, by giving an oracle access to $P\subseteq L\subseteq NP$, it seems reasonable to expect there's some $L$ that is so weak compared to $SAT$ and thus gives "relatively more" power to $P$ than to $NP$.

Suppose we're given a monotonically harder sequence of oracle access,
$$
L_0 (\in P)\leq_P L_1 \leq_P L_2\leq_P\dots\leq_P L_k= SAT,
$$
We'll have
$$
P=P^{L_0}\subseteq P^{L_1}\subseteq ... \subseteq P^{L_k}=NP\\
NP=NP^{L_0}\subseteq NP^{L_1}\subseteq ... \subseteq NP^{L_k}=\Sigma_2P
$$

Suppose we can find, in the middle $L_i$ that does not give extra power to $NP$, i.e. $NP^{L_i}\subseteq NP$, but $L_i$ is already hard enough so that, in such relativised world we could resolve $P^{L_i}\neq NP^{L_i}$, then we'll have $P\subseteq P^{L_i}\subsetneq NP^{L_i}=NP$. So my question is,

  Do we have any barrier result against this type of technique when resolving $P$ vs $NP$ ? It seems neither a relativizing technique nor a natural proof.


texts: Help in understanding exactly how lattices used as one way functions for hashing

texts:
(This question is related to homework)
I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority of the past week sifting through papers and videos in an attempt to build my understanding of the subject, but due to the intensely technical manner in which information on the subject is presented, I have not been able to answer many questions in my mind. Due to the structure of my long distance course I have no access to professors or extensive libraries so my question is one which merely seeks to increase my understanding, please bear with me.

Thus far I have understood that:
- Lattices are a collection of regularly ordered points in euclidean space (its terms like this which have caused me to be searching for answers for days)

A lattice may be defined through n vectors called a basis where n = the dimension (for now I am working in dimension 2), and any other basis can be found by applying positive or negative multiples of each vector in the basis to another vector in the basis
Defining a lattice L1 as a set of points allows one to multiply the whole set by some co-efficient which will essentially transform it into a new lattice L2
The determinant of the vectors of the basis essentially tells us the volume (area in 2 dimensions) of the parallelpiped which will be repeated to form the lattice, the lattice points being the vertices.

Having said this, I am now stuck in understanding how I move all of this to cryptography. I am on a question which asks me to compute the output for 3 inputs to a function:

'We will see that q-ary lattices give provably collision-resistent hashing. We choose integers q; a
and b. Our hash function (presented by Mikl´os Ajtai in a breakthrough paper in 1996) is a 2-variable
function: h(x, y) = ax + by mod q.
(a) For q = 5; a = 14; b = 13; compute h(17, 8), h(21, 16) and h((17, 8) - (21, 16))'

Having found the answers, h(17, 8) = 14*17 + 13*8 = 342 mod 5 = 2; h(21, 16) = 14*21 + 13*16 = 502 mod 5 = 2; h((17, 8)-(21, 16)) -> (h(-4, -8) = 14*-4 + 13*-8 = 160 mod 5 = 0

I believe this means that with the first two points the lattice has been moved by some multiple of 5 plus two, which has displaced it by two and thus formed a new lattice. While in the last case, the lattice has been moved by a multiple of its determinant and thus is the same lattice.

However, I just cannot understand the link to hashing. In an application would the points be the cleartext and the 'answer modulo 5' the output of the hash function? If so would'nt there be too many collisions as we have already seen two examples of which give the answer 2? How exactly is this linked to the shortest vector problem or short integer solution if they are not the same thing? Are q-ary lattices only an attempt to store the basic pattern needed to reproduce the lattice? and if so wouldn't the lattice itself be the cleartext and the basic pattern (given by the basis and the determinant) the answer from the hash function??? How exactly would you encrypt a message using a lattice???

I just wish I could find some text which explained this in English rather than symbols.. like this http://www.wisdom.weizmann.ac.il/~odedg/COL/cfh.pdf . I really hope I have not repeated any questions through my lack of understanding. Thanks in advance.


texts: Time complexity and space complexity in recursive algorithm

texts:
"The designer of an algorithm needs to balance between space complexity and time
complexity." - Comment on the validity of the statement in the context of recursive
algorithms.

This is a question from my university's previous paper. But i couldn't find a decent answer. Actually i am confused about how can a developer minimize the time-complexity for any recursive function. I get that if there is a tail-recursion then space complexity can be minimized. But can't get the idea of time-complexity.


texts:
Is ∀x∀y∀z[φ(x,y)∧p(y,z)->p(x,z)] equivalent to ∀x∀y∀z[φ(x,y)∧p(x,z)->p(y,z)] ?

The only thing I can think of is that this question can be answered if we show that p->q is equals (↔) το q->p, but that's not true because p->q ↔ ¬p->¬q, hence p->q is not equals to q->p. However, I do not know if my logic is correct and if it can be accepted as an answer.

I also think that the (first) ∀x∀y∀z[φ(x,y)∧ part is irrelevant and that i have to focus only to the last part.


texts: How do you calculate the running time using Big-O notatation?

texts:
I'm still new to Data Structure and Algorithm and therefore I would like to ease my doubts. I'm required to find the Big-O running time of myMethod():
 Static int doIt(int n) {
           for ←1  100 do    -> 100
             for ←1   do    -> n x 100
                 ←1;←       -> 1
           while < do       -> lg n
          ←(+)/2           -> lg n/2
        end while
        end for
        end for

    }

 static int myMethod(int n) {
                   ←1
                  ℎ ( < ) {          -> lg n
                        ()            -> ?
                         ←×2             -> lg n
        }
             1;

}

For each of the line I have inserted the answer I think would be a logical value to put e.g "-> 100". However I am not confident with the answer. These are the following questions that I would like to ask as well:

Does all while loop have a value of lg n?

If the doIt(n) method does not have a return statement, do we still add in part of calculation?

For the line with m <- (m+j)/2, the value I have inputted is lg n /2. Is that correct or is it some other value?

Whenever multiplying by 2 or dividing by 2 is it always lg 2? what if n is multiplied by 3?

Thank You


texts: Is $L = \{\langle M, w \rangle: \text{on input}\ w\ M\ \text{doesn't pass through a state}\ q\}$ decidable?

texts:
I'm trying to find whether

$$L = \{\langle M, w \rangle: \exists q.\ \text{on input}\ w\ M\ \text{doesn't pass through a state}\ q\}$$

is decidable or not.

I don't know how to proceed here. I mean, I have the feeling that I have to know which state $q$ the machine $M$ 'skipped' in order to go ahead. For instance if $q = \text{Accept}$, it means that $M(w) = \text{Reject}$ and I guess that, in this case, $L$ can be shown to be a reduction from $L_{empty}$ (written also $E_{TM}$). So if we assumed that $L$ was decidable $\implies E_{TM}$ is decidable which is not true.

But what about the case where $q \neq \text{Accept}$ state?


texts: Is reservoir sampling unnecessary if you know the length of the stream of integers?

texts:
I think I understand Reservoir Sampling.  If you have a large stream of integers then it allows you to get a sample of size k from that stream without putting it all in memory.
My question is what if you know beforehand the length of the stream?  Say the length of the stream is n.  In this case I would assume that a much simpler way to get a sample of k would be to just generate k random indices between 0 and n beforehand then as you iterate through the stream just select the integers corresponding to the indices you sampled beforehand.  What would be the downside of this? Slower maybe?


texts: Significance of model in arithmetic coding

texts: I am trying to understand the concept of arithmetic coding, i understand how the range is subdivided after each character is read from the string. But i am unable to understand why using a more accurate model compresses the string. Whether the model is static/adaptive either way the number of characters in the compressed string would be the same. What am i missing?


texts:
How is it possible to print all patterns of length $k$ contained in a string, using the FM-index and Burrows-Wheeler transform?

PROBLEM DETAIL:
The input I have is:

the text encoded with the Burrows-Wheeler Transform
the data structure of the FM-Index.

In particularly for the second element listed, I have:

$C(c)$ is a table that, for each character $c$ in the alphabet,
contains the number of occurrences of lexically smaller characters in
the text
$Occ(c, k)$  is the number of occurrences of character $c$ in
the prefix of the Burrows-Wheeler transform $1..k$

The only strategy that I've found at the moment is to reconstruct the text from the Burrows-Wheeler transform and, during that operation, for every char print the pattern that starts from it. In pseudocode,

---------------------------------------------
DATA
---------------------------------------------

bwt[n]  => burrow wheeler transform of the text
C, Occ => FM-index data structure
K => lenght of the patterns to be extracted (so extract all patterns of length k from text T)

---------------------------------------------
Algorithm
---------------------------------------------

n = |bwt|; //text length
T[0,n]; //array used to save the original text
T[--n] = bwt[0]; //first char of the original text

currentIndex = 0;

for i = 0 to |btw(T)| - 1 do
    //get original
    lastFirst = c(bwt[currentIndex]) + Occ(bwt[currentIndex], currentIndex);
    T[--n] = bwt[lastFirst];
    currentIndex = lastFirst;

    //print pattern only if we have reconstructed at least k char
    if((|btw(T)| - n) >= k) from original text
        print T[n, n+k]; //print last k char reconstructed
    endif;
endfor;

Is there a better technique or strategy to solve the problem? Is there a strategy that doesn't need to reconstruct the original text?


texts: Would a five color display have higher image quality than an RGB display?

texts:
We have five types of photo receptors in the eyes but computer color systems just use the three red, green and blue.

Three could be motivated if rod and melanopsin sensations are just linear combinations of cone sensations. Is it so or would a five color display with two additional pixel components with a frequency distribution similar to that of rods and melanopsin respectively add image quality?


texts:
I have an edge coloring problem as follows:
Suppose we have a DAG which has a source vertex s and an end vertex e, in addition, all the paths from s to e are of the same length say L. We define L colors from 1 to L. Is there an efficient edge coloring algorithm to color all the edges, such that every path from s to e uses all the L colors and every path must be labeled differently? I attach a picture below for illustration, where vertex 1 is s, vertex 10 is e.


texts: Fastest known complexity for combinatorial ILP algorithm?

texts:
I'm wondering, what is the best known algorithm, in terms of Big-$O$ notation, to solve Integer Linear Programming?

I know that the problem is $NP$-complete, so I'm not expecting anything polynomial. And I know there are lots of heuristics and such that are used in practical applications like CPLEX, but I'm more interested in the formal, worst-case complexity of an exact algorithm.

Some $NP$-complete problems have algorithms in time $O(b^n p(n))$ where $1 < b < 2$ and $p$ is a polynomial. Vertex cover, independent set and 3SAT fall into this category, but general-SAT and TSP don't (as far as we know).

Can any such statements be made about Integer Programming, or particular sub-instances?

If anyone has a reference for the related problem of Quantifier Free Presburger Arithmetic, I'd be very interested in that too.


texts: How hard is counting the number of simple paths between two nodes in a directed graph?

texts:
There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search).

However it seems that, surprisingly, the problem gets much harder if instead of testing for the existence we want want to count the number of paths.

If we allow paths to reuse vertices then there is a dynamic programming solution to find the number of paths from s to t with n edges. However, if we only allow simple paths, that don't reuse vertices, the only solution I can think of is brute force enumeration of the paths, something that has exponential time complexity.

So I ask,

Is counting the number of simple paths between two vertices hard?
If so, is it kind of NP-complete? (I say kind of because it is technically not a decision problem...)
Are there other problems in P that have a hard counting versions like that too?**


texts: Integer-array indexing (e.g. numpy.take) as function composition: where can I find more resources?

texts:
For context, one of Numpy's features is that an an array of integers can be passed as an index to an array, and this selects values at all of the specified positions, in any order with possible duplicates.

>>> import numpy
>>> a = numpy.array([0.0, 1.1, 2.2, 3.3, 4.4, 5.5])
>>> b = numpy.array([2, 4, 3, 3, 0])
>>> a[b]
array([2.2, 4.4, 3.3, 3.3, 0. ])

>>> # alternative syntax
>>> numpy.take(a, b)
array([2.2, 4.4, 3.3, 3.3, 0. ])

I think this is a feature of most array libraries/languages, as well as SIMD instruction sets (specifically "gather").

If we consider the array as a function from a single integer index to its data type (i.e. $[0, N) \to \mbox{dtype}$ for an array of length $N$), then indexing with an array of integers is function composition. This, coupled with the fact that function composition is associative has been incredibly useful in my Numpy scripts and I'd like to know if there's a theoretical literature that might go into it in more depth.

To demonstrate what I mean with an example, consider any two functions from and to non-negative integers ($\mathbb{Z}^{\ge 0} \to \mathbb{Z}^{\ge 0}$):

def f(x):
    return x**2 - 5*x + 10
def g(y):
    return max(0, 2*y - 10) + 3

Sample these functions and their composition $g(f(\cdot))$ at the first few integers in their domain:

F   = numpy.array([f(i) for i in range(10)])     # F is f at 10 elements
G   = numpy.array([g(i) for i in range(100)])    # G is g at 100 elements (enough)
GoF = numpy.array([g(f(i)) for i in range(10)])  # GoF is g∘f at 10 elements

Now array-indexing G[F] returns the same result as the sampled composition GoF:

print("G\u2218F =", G[F])    # integer indexing
print("g\u2218f =", GoF)     # array of the composed functions

G∘F = [13  5  3  3  5 13 25 41 61 85]
g∘f = [13  5  3  3  5 13 25 41 61 85]

Since integer-array indexing is function composition, it's associative like function composition:

H = numpy.arange(1000)*1.1
print("H[G][F] =", H[G][F])  # index H by G, then the result by F
print("H[G[F]] =", H[G[F]])  # index H by the result of indexing G by F

H[G][F] = [14.3  5.5  3.3  3.3  5.5 14.3 27.5 45.1 67.1 93.5]
H[G[F]] = [14.3  5.5  3.3  3.3  5.5 14.3 27.5 45.1 67.1 93.5]

and this fact can be very useful (e.g. as an optimization if you have many H's or as a simplification if you're recursing over a tree of arrays). In some applications, it borders on magical.

Is there a paper or a sub-subbranch of computer science where this sort of thing is developed in more detail? What should I read to learn more?


texts: Efficient algorithm for finding optimal sum from both arrays

texts:
I have two arrays(A,B) and a sum M. I need to find one number from each array that makes the sum M. If there is no two elements that form sum M, then nearest and less than M sum is the solution. See examples below. What is the efficient way to find the solution for this?

eg1:
A =[200,300,600,900]
B =[1000,200,300,500]
M = 900
Output : A(2), B(2)
600 from A and 300 from B sums 900.

eg1:
A =[200,300,600,1000]
B =[1000,400,600]
M = 1500
Output : A(3), B(1)
1000 from A and 400 from B sums 1400 which is near to the sum 1500.


texts: Generate scale-free networks with power-law degree distributions using Barabasi-Albert

texts:
I'm trying to reproduce the synthetic networks (graphs) described in some papers.

It is stated that the Barabasi-Albert model was used to create "scale-free networks with power-law degree distributions, $P_A(k) ∝ k^{-λ}$".

$P_A$ is a probability distribution that returns the probability of a node having degree $k$. For instance, $P_A(2)$ indicates the probability of randomly choosing a node from the network and getting a node with degree 2.

The average degree $k$ stroke seems to be 4 in one paper, with a the minimum $k$ of 2. No word about the maximum $k$. In the other paper it is not specified. It does not seem that important to define the network.

Lambda λ values are given, as is the number of nodes $n$.
Combinations are

n = 50000, λ = 3, 2.7, 2.3, with  in a paper
n = 4000 and λ = 2.5, or n = 6000 and λ = 3 in the other paper

I looked for libraries implementing the Barabasi-Albert algorithm and they seem to require different parameters than lambda and the average degree. One is NetworkX, another is GraphStream (implementation here). They work in similar ways and ask for:

n : int - number of nodes
m : int - number of edges to attach from a new node to existing nodes; the number of edges to be added at each step

How can I calculate the settings m to generate a comparable  graph?

Here are some references:

Catastrophic cascade of failures in interdependent networks, Buldyrev et al. 2010, with a separately provided Supplementary Information
Small Cluster in Cyber Physical Systems, Huang et al. 2014
Catastrophic cascade of failures in interdependent networks, Havlin et al. 2010, this is on the Arxiv and somewhat clarifies the first

Note that these papers used "generating functions" to analytically study some properties of those graphs. However, they also run simulations on those models, so they must have generated those networks somehow.

Thanks.


texts: Kolmogorov complexity vs purposefully inefficient Turing machines

texts:
It's a theorem that, although the Kolmogorov complexity of a string is relative to the Turing machine you're working with, it differs by at most a constant (basically the amount of space it takes to write an interpreter for Turing machine A inside of Turing machine B).

My question is: how does this theorem deal with the issue of Turing machines with purposefully inefficient encodings?

For example, suppose we have a universal Turing machine $M_{terrible}$ that requires its input to be repeated five times. It starts by verifying that the input is in fact of the form x ++ x ++ x ++ x ++ x, then executes the universal Turing machine $N$ on just x. Shouldn't this force the Kolmogorov complexity of strings relative to $M_{terrible}$ to be 5 times larger than they are relative to $N$? Why doesn't this violate the theorem?


texts:
Suppose we have a DAG of tasks:

Arrows represent flow (reversed dependencies: 8 must be run after 7). Some of the tasks (like 4, 5, 6) can be run in parallel (Par block). Dependent tasks (like 7, 8, 9) must be run sequentially (Seq block).

I need to parse this DAG into recursive structure of Seq and Par blocks (collections). DAG from the image above may be represented by the following structure:

Seq(
    1,
    2,
    Par(
        Seq(7, 8, 9),
        Seq(
            3,
            Par(4, 5, 6),
            10
        )
    )
)

Each DAG may be represented by a set of Seq-Par structures. I want to search for the most optimal. Optimality criteria — run in parallel as much as possible (without breaking dependencies).

More on optimality criteria: all tasks' have the same execution time T. Execution time of Seq(1, 2 ... N) equals to N * T. Par(1, 2 ... N) = T.

I believe, that this task is pretty well-known and simple. Can you, please, name some algorithm solving this problem.

If we add edge from 7 to 4 (proposal from comments), then one of representations may be:

Seq(
    1,
    2,
    Par(
        7,
        3
    ),
    Par(
        Seq(8, 9),
        Seq(
            Par(4, 5, 6),
            10
        )
    )
)


texts:
We have a database with well-formated and structured data. From time to time we get Excel - files from our clients. This Excel Files have to be imported to the database. It it very important that we dont create duplicate data so we first need to check if the data record already exists in the database.

The problem is: The records in the excel files do not contain a unique identifier. Although there are certain properties that are always included, but they are not suitable for easy comparison. In addition, the excel files contain many properties that are missing in other files and that we do not have in our database.

We are talking about tens of thousands of records here. It is not an option that this happens manually by an employee. At the very least, a large part should be handled automatically and only a small part should be manually controlled.

My question is very open. I do not know which solution I'm looking for exactly. Maybe there is a general generic algorithm for merging unstructured data with structured data?


texts: Evolutionary algorithm in stochastic environment

texts:
Consider the following model problem:

I want to use an evolutionary algorithm to optimize the starting point of particles for which it is apriori clear where they would start in state space, but not when. Once a particle is placed, it is part of the dynamics, which is stochastic, i.e. whether certain particles interact is modeled by a random variable. A mutation of the evolutionary algorithm corresponds to slightly changing the time when the particle is introduced in the system.

I have now two choices:

1) I let the stochastic dynamics evolve while the evolutionary algorithm is optimizing, i.e. after every mutation I draw a new interaction environment from the distribution. That means, the algorithm is evaluating every situation with a different environment (drawn from one fixed distribution).

2) I draw an interaction pattern for every particle apriori to have one fixed environment (we assume they can be drawn independently). Then I let the algorithm optimize my problem in that deterministic environment. I do that for several environments and take some statistic over the solution.

Does someone have experience with those two approaches and can tell me their advantages and disadvantages from a practical point of view?


texts: Enumerating all ways of pairing odd nodes

texts:
Can someone provide a brute force pseudocode for finding best connections between odd-degree nodes in the Chinese postman problem mentioned here?

For example, if the odd nodes are $B,C,D,E$, the program should output the three pairings

  BC,DE; BD,CE; BE,CD.


texts: Maximize the minimum gap while scheduling within intervals?

texts:
Problem
There are N intervals in which a particular integer can be chosen. What is the maximum possible minimum gap between each integer if one integer is chosen for each of those intervals?
For example: Input: [2,4], [0,8], [3,15], [10,20]
We shall choose 2 in [2,4], 8 in [0,8], 14 in [3,15], 20 in [10,20]
Thus answer is 6. The distances between the integers need not be equal. We just need to maximize the minimum of those distance.
My effort
I'm supposed to use a greedy algorithm here (mentioned in the question) but I can't get what do I do. I thought of sorting them according to the finishing time and then trying L = (maximum_range)/(N-1) as the first guess and starting from the first interval starting time I choose the next one at previous+L. If that is beyond the finishing time of the next one, I choose the finishing time and change the value of L to the new minimum (finishing_time - previous). If that is before starting time, I choose the starting time, else I choose the time previous+L itself. But this is not working in some cases like this: [2,4], [0,8], [3,9], [10,20] where it is choosing 2, 8, 9, 10 and giving the answer as 1. But the answer should be 4, where we choose 4, 0, 9, 13 respectively. I think my problem is with ordering them according to their finishing times, that fixes the element I start with, but in this case, the optimal solution does not start with [2,4] (least finishing time) itself, it should start with [0,8]. Sorting according to starting time also does not do anything.


texts: Is there ongoing research on Markov Chain Monte Carlo algorithms (other than Metropolis-Hastings) for use in ray tracing?

texts:
Metropolis Light Transport is an application of the Metropolis-Hastings algorithm. Its variants differ only in the used "mutation strategy".

Is there ongoing research on other Markov Chain Monte Carlo algorithms (with faster convergence rates) for use in ray tracing?

If so, I'm interested in any paper.

(Cross-posted on Computer Graphics)


texts: Transformation Function: Gonzalez and Woods

texts:
I have been reading Image Processing from Gonzalez and Woods and in the chapter Image Transformation I have come across this equation

$$
T \left(u, v\right)
=
\sum_{x=0}^{M-1}
{
  \sum_{y=0}^{N-1}
  {
    f \left(x, y\right)
    \,
    r \left(x, y, u, v\right)
  }
}
\,.
$$

I am unable to understand this mathematical notation. Any help will be highly appreciated. Thanks


texts: CFL not closed under intersection while Turing Decidable are

texts:
It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not.

Does not Turing Decidable engulf all CFLs?


texts:
I'm looking for an algorithm name to change the order of the levels of a tree. I've done something that works but there's a lot of code and the $ O(n) $ is very bad.

Here's an example, let say there are 3 levels. Each level representing something in a hierarchy project > budget > fiscal year

project = {a}
budget = {b, c}
fiscal year = {d, e}

   root
    |
    a
   / \
  b   c
 /\   /\
d  e  d e

I would like to build a tree with the level in different order

fiscal year > project > budget

   root
    / \
   d   e
   |   |
   a   a
  /\   /\
  b c  b c

budget > fiscal year > project

   root
   /  \
   b   c
  /\   /\
 d  e d  e
 |  | |  |
 a  a a  a

The initial tree can be more complicated. Each node can have more than 2 children.

    root
    /  \
   a    b     - Projects {a, b}
  / \  / \
 c  d  c  e   - Budgets {c, d, e}
 |  | /\  |
 f  g f g g   - Fiscal year with data {f, g}


texts: Can input to a Turing machine be of infinite length?

texts: Considering only the alphabet $\Sigma = \{0,1\}$, the strings which can be given as input to the Turing machines are from the set $\Sigma^{*}$. But does it make sense for the input to be an infinite binary string ? For example if a Turing machine accepts all strings starting with a 0, does a binary string of infinite zeros also belong to the language accepted by the Turing machine ?


texts: Language equivalent states in a deterministic parity automaton

texts:
Given a deterministic parity automaton $\mathcal{A}$ with state set $Q$ and a state $q \in Q$, we denote with $\mathcal{A}_q$ the same automaton with initial state $q$. Two states $p$ and $q$ are language equivalent if $L(\mathcal{A}_p) = L(\mathcal{A}_q)$.

What is an efficient algorithm to compute the set of all language equivalent pairs, i.e. $\{ (p, q) \in Q \times Q \mid L(\mathcal{A}_p) = L(\mathcal{A}_q) \}$ ?


texts: Explain this Graph Matching solved in Linear Time

texts:
I'm interested in a better explanation about the paper Computing Optimal Assignments in Linear Time for Approximate Graph Matching.

The graph edit distance is approximated  by assignments in linear time.

Briefly speaking there is an embedding of optimal assignment costs into a Manhattan metric: $φ_c(A) = [A_{uv}^← · w(uv)]_{uv∈E(T)}$. The Manhattan distance between these vectors is equal to the optimal assignment costs between the sets.

The problem is: it is not throughly explained how I find $A_{uv}^←$ and how I use Weisfeiler-Lehman to label the vertices of a tree in the following figure:

Please, explain how I find $A_{uv}^←$ and how I label that tree.


texts: What are the essential differences and similarities among "data", "Information" and "knowledge" in the context of Computer Science?

texts:
The terms "data", "information" and "knowledge" are quite interchangeably used in Computer Science. Strictly speaking, they do carry a very different meaning. I want to know their precise meanings and their context and usage.

According to my limited experience, data is simply "raw fact and figures" whereas information is "meaningful data" and knowledge is information via which one can predict the unknown or infer something new. Please correct me if I am wrong.


texts:
I'm not sure this is on-topic or even the right website, please point me in the right direction if not.

I was wondering why computers are so incredibly complex. This question is as naive as it sounds, I'm really just looking for a nice explanation of why computers can't be like the airplane from Blyton's The Faraway Tree, where you push a button to go up, down, left or right.


texts: Seeking an algorithm for finding the partition of data on an interval that maximizes the minimum fitness among the blocks

texts:
In the paper "An algorithm for optimal partitioning of data on an interval" (link) the authors describe an algorithm for partitioning data on an interval to maximize a fitness function. The fitness function they use is the sum of the fitness of each block in the partition.

My question is, how can this be done if the fitness function were instead the minimum of the fitness of each block? More precisely, how should the algorithm be if the sum in the fitness function in equation (4) was replaced by min?

My guess is that the same algorithm would work, replacing equation (6) with the following:

$$Max_j\,\{min(opt(j-1), end(j,n+1))\}.$$

I would think that this has been done before, but I am unable to find any references. Does anyone have a reference, or agree that my modification is correct?


texts:
Assume that $\forall 1 \leq i \leq n : a>0, c_i > 0 $ where $n \in \mathbb{N}$. I need to show that it is possible to compute this sum in $O(n)$ time:

$$I = \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n}$$

(a sum over all binary vectors of length $n$)
I notice that in $I$, for any fixed $1\leq i \leq n$, we have that $a^{c_i\epsilon_i} = 1$ in $2^{n-1}$ of the times, and $a^{c_i}$ in the other $2^{n-1}$ of the times. So $I$ can be written as follows:

$$2^{n-1}\cdot a^{c_1} \cdot \sum_{(\epsilon_2,...,\epsilon_n)\in \{0,1\}^{n-1}}a^{c_2\epsilon_2}\cdot ... \cdot a^{c_n \epsilon_n} + 1 \cdot \sum_{(\epsilon_2,...,\epsilon_n)\in \{0,1\}^{n-1}}a^{c_2\epsilon_2}\cdot ... \cdot a^{c_n \epsilon_n}$$

But coming to expand this for $i=2,...,n$ I immediately realize that this won't turn out to be $O(n)$. I would appreciate some guidance.


texts: How to determine the maximum valued play in Rummikub?

texts:
This question is meant as a follow-up this question and my answer here.

The question asked multiple questions about algorithms for playing Rummikub and my answer provided an algorithm that, given a set of Rummikub pieces $S$, determines whether they can be arranged as a set of valid plays (called an arrangement).

However, when we actually play Rummikub, the situation is slightly different: there is a given board state $B$ and a hand $H$. We want to empty our hand by adding pieces to the board. We assume the board $B$ has a valid arrangement.

So, the problem now becomes:

  Does there exists a subcollection $S\subseteq H$ such that there exists a valid arrangement for $S \cup B$; and
  What is the largest such subcollection $S$ ?

Obviously, we can iterate over every subcollection $S$ of $H$ and test validity for each of them, but that is inefficient. To make precise what I mean by 'efficient' here, consider the game to be played with $3,4$ or $5$ colours and the numbers $1\ldots n$ for each color.

Does there exist an polynomial (in $n$) time algorithm that solves problem 1 or 2? Or this 1 or 2 intractable (e.g. NP-hard)? Feel free ignore complications such as jokers or assume all tiles are distinct.


texts: Is $\{\langle G,x\rangle \mid x\in L(G)\}$ context-free?

texts:
Our problem is:

  Given a context-free grammar $G$ and a string $x$, decide whether $x\in L(G)$.

Is this language itself context-free?


texts: Is there a way to simplify redundant conditionals?

texts:
For example if I've this:
if a == false then return true else
if a == true and b == false return true else
if a == true and b == true then return false

can be simplified to
if a == false || b == false then return true
return false;

Truth Table would look like this:
F T = T
F F = T
T F = T
T T = F

I want to come up with a solution that can get arbitrarily big conditional but condense it to the  minimum state and get rid of cases which will never occur.
I'd imagine one way would be to generate a truth table and work your way up from there, another would be to find and combine combos with similar out comes and come up with a pattern that would keep the existing truth table intact.


texts: Why half of the medians are greater than the median of medians?

texts:
I already saw similar question  Counting elements that are greater than the median of medians but I couldn't find my answer in there.

CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of $n$ distinct numbers. This is the algorithm:

  Divide the $n$ elements of the input array into $\lfloor n/5\rfloor$ groups of 5 elements each and at most one group made up of the remaining $n$ mod 5 elements.
  Find the median of each of the $\lceil n/5\rceil$ groups by first insertion-sorting the elements
  of each group (of which there are at most 5) and then picking the median
  from the sorted list of group elements.
  Use SELECT recursively to find the median $x$ of the $\lceil n/5\rceil$ medians found in
  step 2. (If there are an even number of medians, then by our convention, $x$ is  the lower median.).
  Partition the input array around the median-of-medians $x$ using the modified
  version of PARTITION. Let $k$ be one more than the number of elements on the
  low side of the partition, so that $x$ is the $k$th smallest element and there are $n-k$
  elements on the high side of the partition.
  If $i = k$, then return $x$. Otherwise, use SELECT recursively to find the $i$ th
  smallest element on the low side if $i < k$, or the .$(i-k)$th smallest element on the high side if $i > k$.

My problem is the steps 2 and 3. It claims

  at least half of the medians found in step 2 are greater than or equal to the median-of-medians x.

Some thing that I can't understand very well. May be there is a misunderstanding in the median-of-median term. What I understand of the median-of-median is in the following:(Every group of five elements is sorted increasing)

  There is a list $A_1 \cdots A_{75}$ of input array

Step1: Sort every group of five elements
$$\overbrace{A_1A_2A_3A_4A_5}\overbrace{A_6A_7A_8A_9A_{10}}\overbrace{A_{11}A_{12}A_{13}A_{14}A_{15}} \cdots \overbrace{A_{71}A_{72}A_{73}A_{74}A_{75}}$$
step 2 of algorithm (get medians)
$$
\overbrace{A_3 A_8 A_{13} A_{18}A_{23}}\overbrace{A_{28}A_{33}A_{38}A_{43}A_{48}}\overbrace{A_{53}A_{58}A_{63}A_{68}A_{73}}
$$
Then repeat recursively (median of medians)
$$
\overbrace{A_{13},A_{38},A_{63}}
$$
$$
x = A_{38}
$$

From what I understand, in the last level we can guarantee that $A_{63}$ is greater than $x$. In step 2 only $A_{68}, A_{73}$ are greater than $A_{63}$ so they are greater than $x$ as well. Since in step 2 $A_{43}, A_{48}$ are greater than $A_{38}$ So at most five elements among 15 elements in step 2 are greater than the $x$. Then why CLRS claims that half of the medians in step2 are greater than $x$?

thanks in advance.

update

If the algorithm of finding median of medians is not what I did above, How can I find the median of medians of step2 in $O(n)$?


texts: Pumping lemma for Context-Free Languages

texts:
I have a question about a specific pumping lemma problem for Context-Free Languages.

Suppose we have the following Language:

  $L = \{a^{i}b^{j}c^{k}d^{l} \mid 0 < i < k \wedge j > l > 0 \}$

Here is my attemp to prove that the language is not context-free:

Assume $L$ is context-free. Let $n>0$ be the pumping length given by the lemma.

Let $z = a^{n}b^{n+1}c^{n+1}d^{n}$, then $z \in L$.

Than according to the lemma, $z$ can be written as $z = uvwxy$ where the following properties hold:

$|vx| \geq 1$
$|vwx| \leq n$
for every $i \geq 0$, $uv^{i}wx^{i}y \in L$.

We have 6 different possibilities for $vwx$:

$vwx = a^{i}$ where $i \leq n$
$vwx = a^{i}{b^j}$ where $i+j \leq n$
$vwx = b^i$ and $i \leq n$
$vwx = b^{i}c^{j}$ and $i+j \leq n$
$vwx = c^{i}$ with $i \leq n$
$vwx = c^{i}d^{j}$ and $i+j \leq n$

Is this right so far? The thing that I'm unsure of is if my different cases for $vwx$ are right.

How do I choose the pumping length for case 2? If I choose $i$ = 2, what if $i$ is zero ? Then I don't have any contradiction.

Thanks in advance


texts:
$F[u, u^{-1}]$ is a ring that contains the polynomials in $u$ and $u^{-1}$ with coefficients in the field $F$.

Some theorems (from https://math.stackexchange.com/questions/1382120/ft-has-undecidable-positive-existential-theory-in-the-language-cdot) are the following:

Theorem 1.

  Assume that the characteristic of $F$ is zero. Then the existential theory of $F[t, t^{-1}]$ in the language $\{+, \cdot , 0, 1, t\}$ is undecidable.

Theorem 2.

  Assume that $F$ has characteristic $p>2$. Then the existential theory of $F[t, t^{-1}]$ is undecidable.

Theorem 3.

  If the characteristic of $F$ is other than $2$, then $F[t]$ has undecidable positive existential theory in the language $\{+, \cdot , 0, 1, t\}$.

I am looking at the proof of Theorem 3 and trying to understand the last part of it.

I understand that an existential statement of $F[u, u^{-1}]$ in the language $\{+, \cdot , 0, 1, u\}$ is of the form
$$\exists x_1, \dots \exists x_n \in F[u,u'] \phi(x_1, \dots , x_n)$$
where $\phi(x_1, \dots , x_n)$ can consist of $0$, $1$ and $u$ and has the operation $+$ and $\cdot$ between $0$, $1$, and $u$.

I have a question that is related to the proof of Theorem $3$.

When we know that the existential theory of $F[u, u^{-1}]$ is undecidable in the language $\{+, \cdot , 0, 1, u\}$ and we want to show that the existential theory of $F[u, u^{-1}]$ is undecidable also in the language $\{+, \cdot , 0, 1, (u+u^{-1})/2\}$, is it correct that we have to reduce the second problem to the first one?


texts: Is there any proof that Scheduling with a resource constraint works with two resources?

texts:
I've been reading this paper: https://ac.els-cdn.com/S0304397511002623/1-s2.0-S0304397511002623-main.pdf?_tid=bc074517-2b81-4d37-bc92-a5c20dba6b23&acdnat=1527946614_083eb7104693637d83e7d26751a7d23e

where it talks about the interval scheduling problem but with n processors for k jobs.

I was wondering if there's a proof if the same algorithm would work if it was only two processors for k jobs? If there isn't can you explain why it would work?

Something similar to this question: Interval Scheduling Problem with Three Resources

but instead of 3 resources, 2 resources but I'm trying to get O(n^2) instead of O(n^3).


texts: Why should I use Huffman enoding if it makes my data longer?

texts:
I have a requirement to reduce the size of the request / response XML by compressing repetitive productID data in compatible tag.

My request / response xml looks something like below

<products>
   <id>
     2XZ
   </id>
   <compatible>
   2TR,07N,2TS,082,084,2TT,2TU,2TV,2TW,2TX,2TY,2TZ,2U0,2U1,2U2,2U3,2U4,081,083,2U5,2U6,2U7,2U8,2U9,2UA,2UB,2UC,2UD,2UE,2UF,2UG,2UH,2UI,012,014,015,016,2UJ,2UK,2UL,2UM,2UN,2UO,2UP,2UQ,2UR,2US,2UT,2UU,2UV,2UW,2UX,2UY,2UZ,2V0,2V1,2V2,2V3,2V4,2V5,2V6,2V7,2V8,2V9,2VA,2VB,2VC,2VD,2VE,2VF,2VG,2VH,2VI,2VJ,2VK,2VL,2VM,2VN,2VO,2VP,2VQ,2VR,2VS,2VT,2VU,2VV,2VW,2VX
   </compatible>
</products>

I was given a suggestion to use Huffman code to compress compatible list data.

What I am confused about is how would Huffman encoded data in the XML reduce the size of the request / response XML as the resulting stream of binary data in the compatible tag might just increase the length and size of XML.

Example: Huffman encoding first 2 product IDs generates a longer binary string
Original String: 2TR,07N
Encoded binary String: 11101100110100010101

So my XML will change from

<products>
   <id>
     2XZ
   </id>
   <compatible>
   2TR,07N
   </compatible>
</products>

TO:

<products>
   <id>
     2XZ
   </id>
   <compatible>
   11101100110100010101
   </compatible>
</products>

Am I missing something obvious here?


texts:
I was living in a country where Internet wasn't that fast so the younger me had the following idea for compressing data
Let say 2 parties want to send data to each other, we know that data can be represented by a number literally any data no matter the size can be just a giant number.
So let say the 2 parties have this perfect synchronized clock and a very fast one, I mean a clock that can count billions of billions ( equivalent of gbits of data ) in a short amount of time.
So for party 1 to send data to party 2 it only need to send 2 messages :  start counting and stop counting.
So any data can be sent using only 2 bits lol.
How hard is it to design that clock ?


texts: A text-classifier that explains its decisions

texts:
I am building a text categorizer for short sentences. In addition to telling the  user "the category of the text you entered is C", I want to be able to explain why I made this decision, in a short and understandable way. For example, I don't want to tell the user "I put your sentence into a complex 3-layered neural network and that's the answer that scored the best"; I want explanations such as "Your sentence contains the words U, V and W, that are characteristic of this category, because of sentences such as X, Y and Z that appeared in the training data".

My question is: what classification algorithms are best suited for such application?

k-nearest-neighbours seems like a good candidate, because I can tell the user "Your sentence has category C because it is similar to sentences X, Y and Z that have the same category. But its performance on text categorization problems is known to be poor. I am looking for a classifie that balances performance with explanation ability.

EDIT: After spending a lot of time looking for such a classifier, I started to build a machine-learning library called limdu, that allows the classifiers to explain their decisions. It is still under development, but, it has already helped me explain to myself and my colleagues why our classifiers fail so often...


texts: Bare Metal Operating Systems in High Performance Computing

texts:
Few years back, I stumbled across Return Infinity - the OS framework designed around flat, 64bit memory model, with minimal MMU / VM overhead, etc.

I'm wondering if there are any public benchmarks or success stories of that approach - I'm eyeing it as something to practice doing low latency / high performance computing systems.

The theoretical advantages are substantial, if you're aiming to build a specific-purpose computer system (think bare redis / memcache, fft, transcoding, scientific computing etc).


texts: Given a DFA M, formally define an NFA N such that L(N) = {x in L(M) | x = reverse(x)}

texts:
The english description of the question is (from my understanding) N accepts all strings that are both palindromic (the same forwards as it is backwards) and accepted by M. After a lot of toil and trouble, I'm not convinced that such a definition of N is even possible. My thinking is as follows:

Say M above is the DFA that accepts the language $(1 + 0)^*$. Then the desired N would describe all palindromes over the language $\{1, 0\}$. However, such a language is not regular (I think). Therefore, is it not the case that such a formal definition is not possible, as NFAs can only describe regular languages?

Perhaps I am missing some subtle nuance in the question, but I believe that such a formal definition is simply not possible. Is my thinking correct?


texts: I've been researching the specifics of adding noise injection to my input layer to fight against overfitting.  It seems as though most papers recommend a Gaussian noise vector with mean of 0 and a "small" variance, to be applied either additively or multiplicatively to the input layer.  Is this the current convention for noise injection, or is there some other resource I can be pointed towards?


texts: What is the best stream data clustering algorithm that can handle non-static, uncertain data?

texts:
I have gone through many algorithms including streaming k-means, CluStream etc and they all have their pros and cons. What is the best performing algorithm in terms of

Computational Complexity
Memory Requirement
Quality of Clusters
can handle non-static, uncertain data stream

Algorithms needs to be online i.e working on a streaming dataset rather than a static dataset


texts: Memory access on byte/word addressable memory

texts:
I'm doing a question on architecture and I've come across this question which I do not understand how to answer the question.

Q. How many bits are required to address 4G x 32-bit main memory if

a) Main memory is word addressable
b) Main memory is byte addressable

I have read this question Word- or byte-addressable? Correct terminology but it did not clear up my understanding of the question as I am NOT asking what is the difference between byte and word addressable, more specifically I want to understand this question I've written.

The answer given says we need 34 bits for byte addressable memory and 32 bits for word addressable memory. I have thought about this for a while and have come to this conclusion which I do not know if it is correct or not:

Each row in the main memory is 32 bits in width and if it is byte addressable then we have 4 bytes in each row. To select a byte from the row requires log2(4) = 2 bits. Row width + 2 = 34 bits? Similiar concept for 32 bits. Is this correct logic?


texts: Definition of Turing machines and rejection states

texts:
In some definitions of Turing machine, there is only a set of accepting states and no mention of a set of rejecting states.

But it seems to me that the definition that includes only a set of accepting states and that includes also a set of rejecting states will differ.

How can they actually be shown to be equivalent? Or is it not the case?


texts: How to find the position of camera given the known world coordinate of objects?

texts:
Assume that I have a picture of multiple objects (lets say more than 6). The world coordinate of these objects are known. The intrinsic parameters of the camera are also known. How can I find the position and the pose of the camera?

I know some of you will give me an answer like "For each object with image coordinate x and world coordinate X, we can form a equation. Then with multiple objects, we have multiple equations. Solve these equation and get the position of camera. Done." But this is not the answer I want. I want it to be more detailed.

I know that for each object we can form an equation:

lamda * x=P * X=K * [R t] * X

where K is the camera intrinsic matrix, R is the rotation matrix, t is the rotation vector, t=-R*C where C is the camera position.

The equation above can be transformed in to a homogeneous linear system of equation using Direct Linear Transformation. Depending of the specific type of Direct Linear Transformation, this homogeneous linear system of equations will contain lamda or not. Then with multiple objects, we can form a system with enough equations to find a non-trivial solution using the Singular Value Decomposition method.

The problem is that the solution (i.e. the camera matrix K*[R t]) can only be found up to scale (since if v is the solution then s*v is also a solution with whatever scalar s). Thus, we can only find (multiple) camera matrix that have the same projection, but the camera pose and position corresponding to these camera matrix are different (i.e. the exact position and pose of camera cannot be found by this method)


texts:
Say I use a perfect 128-bit hash function to construct a merkle tree.
By perfect I mean that any of the values in the $0$–$2^{128}$ range has an equal probability to be an outcome of the function, over a large enough domain of hashed entities.

Does the root have a higher collision probability than any of the leafs?

To elaborate, say that I have 1000 entities, each of which has a $p_1=1/2^{128}$ probability of colliding.
I construct the tree so that the lowest level spans the range of $2^8$ values, and upper levels span the range of two lower levels.

What is the probability of a single collision in such a tree?
What is the probability of two collisions in a single tree? $n$ collisions?


texts: Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

texts:
Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k)
polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a Homomorphism from G to H)

And if so what would the reduction look like?

Since  i am a little confused by the subject, is the following correct?

A polynomial time reduction from Clique to graph-Homomorphism is a funktion that can be calculated in polynomial time and for which if you input a yes instance of clique it returns a yes instance of graph-Homomorphism, same for no instances.


texts: Computability of a halting oracle for a specific class of machines

texts:
Let us consider the set of machines/algorithms with constant inputs (I would have preferred to say no inputs but I was told that every algorithm/machine has to have an input). We call $\mathcal{M}$ the set of all machines and define $C \in \mathcal{M}$ as follows:
$$ C(I) = \begin{cases} LOOP, \hspace{0.5cm} I \neq C\\ HALT, \hspace{0.5cm} I = C \end{cases}$$
We next define the following class of machines:
$$ \mathcal{M}_0 = \{ M \in \mathcal{M}| M(I) \text{   halts if } I \neq C \}$$
Please note that $C \not\in \mathcal{M}_0$.
Let us now search for a halting oracle $H: \mathcal{M}_0 \times \{ inputs\} \to \{ Yes, No\}$ defined as follows:
$$ H(M_0,I) = \begin{cases} Yes, \hspace{0.5cm} \text{if } M_0(I) \text{ halts }\\ No, \hspace{0.5cm} \text{if } M_0(I) \text{ does not halt} \end{cases}$$
Next we find impossible to apply the Turing's argument for such a machine. Indeed let's consider the machine $N$ with inputs in $\{Yes,No\}$ defined like so: $N(Yes)$ loops for ever and $N(No)$ halts. Then construct the function $$X(I) = N(H(I,I))$$ for all $I \in \mathcal{M}_0$. Assuming that $X \in \mathcal{M}_0$ one evaluates $$X(X) = N(H(X,X))$$ but

if $X \neq C$ follows that $X(X)$ halts hence $X(X) = N(Yes)$ which loops $\to$ contradiction
if $X = C$ follows that $X \not\in \mathcal{M}_0$ $\to$ contradiction

It follows that $X \not\in \mathcal{M}_0$ ... and we cannot apply $X$ to itself!
Question:
Is the above reasoning correct?


texts: Why is this greedy algorithm claim true?

texts:
I'm taking a course about submodular functions and their applications towards influence maximization in a network. We've been discussing a greedy algorithm for selecting $k$ initial nodes to maximize influence and I'm confused about a statement made in class.

Let $O = \{o_1, . . . , o_l\}$, and $o_{\max}$ be the element with the highest marginal contribution in $O$ at stage $i + 1$. That is: $o_{\max} = \arg\max_{o\in O} f_{S_i}(o)$. At stage $i + 1$ the algorithm selects element $a_i+1$ and we are guaranteed that its marginal contribution is the highest. In particular, its marginal contribution is also higher than the marginal contribution of the element in $O$ that has the highest marginal contribution:
$$f_{S_i}(a_i+1) \geq  f_{S_i}(o_{\max})$$

$f$ gives the expected number of nodes influenced and $f_S$ is the marginal contribution of adding set $a$ to set $S$ ie: $f_S(a) = f(S\cup a) - f(S)$
$$f_{S}(a) \geq f_S(o^*)\,.$$

This doesn't make sense to me. Consider the circle cover problem:

At timestep $t = 1$, the greedy algorithm selects $A$ and optimal selects $B$. (Greedy is on the left and optimal is on the right).

$$f_S(A) \geq f_S(B)\,,$$
but at $t=2$
the greedy selects $B$ and optimal selects $C$.
$$f_S(B) \ngeqslant f_S(C)\,,$$
because the marginal contribution of the greedy algorithm is only 4 when the optimal is 5.

Why did we say that selecting elements greedily has better marginal contributions than optimal? I'd appreciate a theoretical and possible concrete example if possible!


texts: How to prove the set of Turing machines that accept a string and its mirror is undecidable?

texts:
I'm trying to prove the undecidability of the following language.

$$L=\{\langle M \rangle\mid M\text{ is a Turing machine and there is a string }w\\\text{ s.t. }M\text{ accepts }w\text{ and }M\text{ rejects }w'\},$$
where $w'$ is the mirrored version of $w$.

I know that my first steps should be to find a reduction from $A_{\text{TM}}$, which is undecidable but the rejection part of the mirrored string is proving troublesome.


texts: The memory a page table occupies and finding the # of pages within it

texts:
Was doing some practice and saw this question:
Assume we’re working on a machine which has the following parameters:
• 16GiB of physical memory
• 22 bit virtual addresses
• 128B pages
• Each PTE in our single level table is 4B
Consider the following snippet of code.
Assume the following:
• Arrays begin on page boundaries.
• We have a function initialize that creates an array containing size integers.
• A starts at 0x20000 and B starts at 0x30000
• sizeof (int) == 4
int size = 256;
int32 t *A = initialize(size);
int32 t *B = initialize(size);
for (int i = 0; i < size; i += 32) {
    B[i] = B[size - i - 1] * A[i];
}

For the following parts, assume ”data pages” refers only to pages containing elements of
A and B (ie. not pagetable pages). Remember that we have 128B pages and each PTE
is 4B

How many unique NON-DATA, NON-CODE pages does this access pattern
traverse? (ie. page table pages)

The answer given is 2 different pages. I kinda see how they got there but there are blanks I'm hoping to fill.
Namely, this is what I understand:
A page table takes up memory and itself can have multiple pages. we are given that a PTE is 4B and a page is 128B. So that means a page in the page table would include 32 entries (or 32 VPN->PPN pairings). In the given code, we access A and B, and have the physical addresses of both.
But, how do we get from that to saying 2 pages? How do we know that the VPN of A and B differ by at least 32 vpn's? And how do we know it's not more than that?

The second part of the questions asks: Suppose this process has a
single-level page table that starts out empty and we run through this
access pattern. How much space would the page table take in memory?
Give your answer in units of PAGES (NOT BYTES).

The answer is given as $2^{10}$ -- how did they get that? I'm completely stumped on that


texts: Do relativized relations between complexity classes tell us anything about the nonrelativized relation?

texts:
The existence of relativized relations between complexity classes seems to often be treated as "circumstantial" evidence about the "true" or "real-world" (i.e. nonrelativized) relation between the classes. (For example, this lecture describes one particular oracle separation as "formal evidence" that the complexity classes are unconditionally distinct.) However, as far as I understand (please correct me if I am wrong), for complexity classes $A$ and $B$ and an oracle for a language $L$, all four of these cases are logically possible:

$A = B$ and $A^L = B^L$
$A = B$ and $A^L \neq B^L$
$A \neq B$ and $A^L = B^L$
$A \neq B$ and $A^L \neq B^L$

So presuming that at the end of the day the unrelativized result is what we really care about, what are relativized results "good for"?

I can see one application: if we happen to be able to find oracles for two languages $L$ and $L'$ such that $A^L = B^L$ and $A^{L'} \neq B^{L'}$, then that tells us that any proof that either $A = B$ or $A \neq B$ cannot relativize, and this fact saves us a lot of time by allowing us to immediately skip many potential proofs.

But do oracle results give us any evidence about the actual relation? In particular, why are oracle separations treated as "evidence" (though not a proof) that the complexity classes are unequal? How strong does the complexity-theory community consider such evidence to be? (I know that last question is subjective and hard to answer precisely.)


texts: Which is the most efficient out of Bubble Sort, Selection Sort, Insertion Sort for a identical set of elements?

texts:
Which of the sorting algorithm is (classical implementation with no enhancements) the fastest for a data set with all identical elements? And why?

How would one justify the answer to the above question logically?
Logically as in without implementing the algorithms and finding the average time consumed for few sample data sets.


texts: Order of argument application in lambda calculus

texts:
I encountered the following exercise in a textbook about logic:

$\lambda x \lambda Y(Y(x))(j)(M)$

It seems that the expected result from the textbook should be $M(j)$, since there were some type specifications on the variables. However, if I substitute $M$ for $x$, and $j$ for $Y$, then the result would become $j(M)$, which would be erroneous in terms of type.

I've seen elsewhere expressions such as:

(λa.λb.λs.λz. a s (b s z)) x y →
(λb.λs.λz. x s (b s z)) y →
λs.λz. x s (y s z)

which seems to have the same application order of arguments as the one desired by this exercise.

It actually seems to make sense if I think of function application in Haskell, but I still find it weird since I expect the rightmost argument to be substituted first for the leftmost lambda term.

Therefore, does the notation $\lambda x \lambda Y(Y(x))(j)(M)$ implicitly entail $\lambda x (\lambda Y(Y(x))(j)(M))$, which would yield the desired result? Is such implicit omission of brackets a normal convention in lambda calculus, and thus every such expression should be treated as such? Or did I misunderstand the order of argument application in lambda calculus after all?


texts: Can we compute edit distance in strongly sub-quadratic time?

texts: Can we compute the edit distance between two strings of length $n$ in strongly sub-quadratic time, i.e., in time $O(n^{2−\epsilon})$ for some $\epsilon>0$?


texts: Are all PDA equivalent to two-state-PDA?

texts:
We know algorithm to convert each PDA in the underlying grammar that generates the language the PDA recognize.
But we have also the algorithm for creating a two state pda from a grammar.
This algorithm use the first state for all the computation, with rules based on the stack and the input symbol, and when the stack is empty goes to a final state.
This  means that, for all the generic PDAs we can create a minimal PDA with only two states (and a lot of rules for the first state).
Am I right?


texts: Original proof that orders eliminate deadlocks?

texts:
A well-known approach to eliminate the possibility of a deadlock when accessing exclusive ressources is enforcing a partial (or total) order in which the ressources may be requested.

Which publication initially introduced this method?


texts: Presentation topic for computational solutions to problems involving probability

texts:
I'm looking for interesting applications of computing science for finding the probability of otherwise difficult problems. This is for an undergraduate level presentation in a probability course of around 30 minutes, from a comp sci major who has beginner to intermediate skills in both probability/statistics and comp sci.

I hope to have a topic that is interesting and can be explained without entirely relying on proofs and equations.


texts: Prove that the language of non-prime numbers written in unary is not regular

texts:
Im trying to prove that the following language is not regular.
$$\text{Notprime} = \{a^n \text{where \(n\) isn't prime}\}
  = \{\epsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots\}$$

Heres what I have:

"If Notprime were regular, then its complement would be regular also. However, the complement of Notprime is the language Prime, hence Notprime is non-regular."

Is this the right way of proving it? Any help is appreciated!


texts: Is there a formalization for the trade-off between the expressiveness and the speed of a programming language?

texts:
I do not have a strong background in theoretical computer science, so the terminology I use may not be the most ideal.
Basically the "trend" across programming languages I have noticed is that there appears to be an trade-off in the speed of a programming language (how long it takes to execute a program) and its expressiveness (saying you want something done vs saying you how you want something done, more expressive languages focus less on the "how", from this definition).
For example, in "higher-level" languages like Python or Java - it is very easy to do something like finding the index of an item in a list with a single line like list.indexOf(item). In comparison, doing the same action in a "lower-level" language like C can result in code that is much faster, but at the cost of having write the code yourself which may be several times as long.
Again, this is really just a trend I have noticed and not a hard and fast rule. Languages like C++ that are both very fast yet can also be pretty expressive at times blur the lines.
So I am curious, is there any sort of formalization in programming language theory - or even just rough rules of thumb backed by empirical studies - explicitly listing out the trade off between the expressiveness and execution speed of a programming language?
Or perhaps I am just overthinking it, and having slower code is just a unavoidable byproduct of having a more expressive language as more things are taken care of "behind the scenes" / abstracted away from during compilation, interpretation, etc.?


texts: Compressed row storage: What happens if last row is all zeros?

texts:
I am studying compressed row storage (CRS format) for storing an sparse matrix. I can't tell how this works if the matrix has a row with all entries zero, and in particular, what happens with the pointer row_ptr. Could you describe the val, col_ind and row_ptr vectors for the following matrix?

\begin{bmatrix}
 2 &  0 & 0\\
 0 &  0 & 1\\
 0 & 0 & 0
\end{bmatrix}

Looking for this, somebody suggested me "if row $i$ contains entirely zeros, you store in row-ptr$(i)$ the same as in row-ptr$(i+1)$" but what happens when the entries of last row are all 0s?


texts: In what cases is graph rewriting not enough to avoid duplicate work?

texts:
As I understand, evaluating something like the following in normal order evaluation is inefficient due to duplicate work:

double x = (x,x)
main     = double some_hard_computation

I remember someone telling me

That there are two ways to avoid this: strictness analysis (to recognise that double is strict in its one argument, and then deviating from normal order evaluation and evaluate the argument first) and graph rewriting (store pointers to some_hard_computation such that both elements of the tuple point to the same computation, and evaluating one side of the tuple automatically evaluates the other side as well).
That neither of the ways are sufficient on their own to avoid all cases where duplicate work can be introduced, and that it is best to apply both when writing a compiler.

I can imagine that strictness analysis can be hard, but in what concrete case can duplicate work be introduced when utilising graph rewriting? Or is either of the two bullet points above incorrect?

Note: while strictness analysis is done statically (as far as I know), graph rewriting is an evaluation strategy, not a compiler optimisation. It attempts to solve the same problem as the strictness analyser, but on a different level (runtime vs. compile time).


texts: Difference between large-scale optimization and equation-based simulation

texts:
Large scale optimization (for example using AMPL) can be used to solve equilibrium systems which have components with fixed mathematical relationships. What is the difference between this and using an equation-based simulation system (like Modelica) to solve an equation-based system?

Of course, most simulations have a time variable, but you can just as well have a time variable in AMPL. Are AMPL models therefore fully analogous to equation-based simulation like MapleSim/Modelica, or is there some fundamental difference between the technologies?


texts: Time interval correction for step detection algorithm

texts:
I am currently going over this paper, and in fact have already tried to implement it:
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4634483/ [1]
Paper looks at the amplitude of the step and the time between the swings. ALthough I seem to understand the general idea, I am slightly confused about one of the formulas, which describes time between steps, namely:
"To extract only one valley from a gathered group of valley candidates in a very short time range, every valley candidate is validated by checking the time distance to the recent valley using the following threshold.
$Th_v = \mu_v - (\sigma_v/\beta)$
where $\mu_v$ and $\sigma_v$ represent the average and the standard deviation of the time interval between adjacent valleys in the magnitude of acceleration, respectively. These averages and the standard deviations are calculated for recent M peaks or valleys."*
Except time threshold obviously magnitude is also taken into consideration.
So I have produced magnitudes that I obtain from my sensor:

where red dots correspond to initially discovered valleys and purple to points that should re-evaluate last valley.
So what I currently have is something like this:
1) I obtain valley at point 20. I obtain valley at Point 49. This should mean that the average distance between two valleys is 29 readings, and therefore I set my $\mu_v = 29 and \sigma = 0$, which yields me a value of $Th_v=29$ ( my $\beta = 1/3$). I also store the difference (29).
2) Then I get to point 51, which should update the $Th_v$ value. So now I calculate the mean, which I think means $(29 + (51-49))/2 = 15.5$
And calculate standard deviation, which equals $19.09$. So then when I actually plug these values in the formula above I get $Th_v = -41.909$, which should not be possible as I believe this value should be always positive to indicate the time between two valleys.
Am I dong something incorrect or do you have any idea what's wrong with my or paper's approach?
References:
[1]: Lee H, Choi S, Lee M. Step Detection Robust against the Dynamics of Smartphones. Wang X, ed. Sensors (Basel, Switzerland). 2015;15(10):27230-27250. doi:10.3390/s151027230.


texts: How to calculate the size of the page table of a process?

texts: Consider a system with A bytes of physical RAM, and B bytes of virtual address space per process. Pages and frames are C bytes in size. Every page table entry is P bytes in size. Calculate the size of the page table of a process?


texts: Recommended Reading for non-CS undergraduate student doing a research Project on Travelling Salesman Problem

texts:
I am an undergraduate student in Industrial Engineering. I have taken the topic of Travelling Salesman Problem as a Research Project for my final year. More specifically, I am focusing on Convex Hulls for solving the Euclidean TSP.

I have gone through the published literature and have found that there are no approximation bounds for solving TSP using this method. I have just a little background in TheoCS (Started reading for fun since the last 3 months).

My Question:

Additional Books / Papers needed for achieving a good understanding of the mathematical rigor of the problem.

Here's what I am currently going through:

Approximation Algorithms - Vazirani
Introduction to Algorithms - CLRS
Introduction to Graph Theory - Douglas West
Randomized Algorithms - Motwani and Raghavan

I have also completed an introductory online course on Algorithms by Udacity.

I think I may need some background reading in Computational Geometry (Currently I do not know more than what I read in the chapter from Cormen)

This is my first question here, so sincere apologies in case my question does not conform to the Community Standards.

EDIT:

A resource I stumbled across today: In Pursuit of the Traveling Salesman - Mathematics at the Limits of Computation.
This is a good book for popular reading, providing a survey of the problem and various methods that have been used to solve it.


texts: Reducing the infinite language problem to halting problem

texts:
Let: $INF = \{ w \in \Sigma^* | \quad |L(M_w)| = \infty \} $.

It is easy to show with Rices theorem that $INF$ is not decidable.
($INF$ is non-trivial because of $\emptyset$ and $\Sigma^*$).

How can you show this with a reduction onto the halting problem (for example)?

Here are my thoughts:

I had an idea of running the decider of $INF$ in its own input, but couldnt get very far.

Another idea that I just had was:

Construct a Turing machine TM M' that halts if the language is finite, and loops endlessly if it is infinite:

M'(w):
for i=0,1,...
    simulate M_w on w_i

Knowing the halting problem we cannot know if that turing machine will halt or not. We have supposedly reduced $HALT$ on $INF$. Is this correct ? (Since we take an instance of $HALT$

Can I get some feedback on my solutions ?


texts: Find a subsequence with fastest time for specific distance

texts:
I have two arrays.

seconds = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, ..., 2680]

totalMeters =  [0, 3.2, 7.1, 10.6, 14.1, 17.9, 21.5, 24.2, 27.8, 32.5, 36.9, ..., 5000]

The totalMeters array is the total meters that I have run at this specific point of time. The sampling is 2 seconds.

I would like to find where in the array is the fastest 100 meters I have run, as well as its time.


texts: Dijikstra implementation in books subtly different

texts:
I was reading about Dijkstra algorithm and was referring two books
1) Introduction to Algorithms by Cormen Section 24.3
2) Algorithm design by Kleignberg Section 4.4

And found a subtle difference in their way of show Dijkstra algorithm

book 1:

Dijkstra(G, w, s)
Initialize(G,s) d(s) = 0 initialize others to inf
S = {}
Q = G.V
while Q not equal to {}:
    u = Extract-Min(Q)
    S = S U {u}
    for each vertect v belonging to G.Adj[u] // all edges emanating from u
        Relax(u,v,w)

Note : the word in for each loop : G.Adj[u]

original snip from book

book 2:

Dijkstra(G, w, s)
Initialize(G,s) d(s) = 0 initialize others to inf
S = {}
Q = G.V
while S not equal to V:
    Select node v that is not yet added to S with at least one edge ***from S*** for which
         d'(v) = min of (d(u) + le)  // computed over all edges that
                                     // emanate from all possible
                                     // nodes in S
    Add v to S and make d(v) = d'(v)

Note : the word in for each loop : from S

original snip from book

Only I find one difference.

in book1 they are computing the neighbors of only the recently added node u. and in book2 they are computing neighbors of entire set S (see the highlighted portion "from S") (and that is not in S).

Yes, both works.

But why is there two implementations of Dijstra algorithm. Any reason
why each book has adopted a different way ?
Why should we do from entire S when we can easily do from last computed node as that is the one with the last node in the longest of the shortest path and that will decide everything ?
Am I missing something ?


texts: How to prove that algorithm returns the value which appears more than $n/2$ times in the array?

texts:
Given the following algorithm (pseudocode):

alg1(A[1,..,n])
    i <- 1
    candidate <- NULL
    count <- 0
    while(i <= n)
        if(count = 0)
            candidate <- A[i]
            count <- count + 1
        else if(candidate = A[i])
            count <- count + 1
        else
            count <- count - 1
        i <- i + 1
    return candidate

I need to prove that if a value appears more than $n \over 2$ times (let the value be named $M$) in the array then it will be returned.

$\mathbf{EDIT:}$ here's my 2 attempt. First we assume that the array $A$ contains at least 3 elements (if less then the proof is trivial). The element which appears more than $n/2$ times is $M$ else it's $M'$. Let a two-element combination of $MM'$ or $M'M$ be called $C$. Every time we traverse a $C$ the count decreases by one.

CASE 1: If the pattern is strictly alternating combinations of type $C$  then the first and the last element must be $M$ (otherwise $M$ will not appear more than $n/2$ times) and this means that after the last iteration the candidate is $M$.

CASE 2: We can see that after any number of adjacent $C$'s the counter will be $0$ and the candidate will be either $M$ or $M'$. It is given that more than $n/2$ elements of $M$ do exist in the array, so the number of $C$ combinations must be supplemented by at least $1$ occurrence of $k$ adjacent elements of $M$ either before $C$'s or after $C$'s. If it's after, then the next candidate is $M$ and it will continue to be so as long as we keep traversing $k$ elements of adjacent $M$'s. If it's before than the count will be at least $1$ before it proceeds to iterate through $C$'s and essentially it'll behave just like CASE 1.

I'm still aware that the proof is not perfect but I feel like it's an improvement. Suggestions/advice is very welcome.


texts: Why is factoring large integers considered difficult?

texts:
I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ depending on how fast division and modulus are. I'm pretty sure I've misunderstood something somewhere, but I'm not sure where. Here's what I wrote in pseudo code form.

function factor(number) -> list
    factors = new list
    if number < 0
        factors.append(-1)
        number = -number
    i = 2
    while i <= number
        while number % i == 0
            factors.append(i)
            number /= i
        i++
    return factors


texts: Context-free grammar for language with unequal numbers of a and b

texts:
I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e.

$$\{u \in \{a, b\}^* \mid \text{number of occurrences of $a$ and $b$ in $u$ are unequal} \},$$

but it seems that I keep getting specific cases instead of the general case.

Here are some that I have tried:

(S being the start Variable)

S -> A | a | b
A -> aV | bT
V -> aV | bL
L -> aV
T -> bT | aM
M -> aT

This one's problem is that you can't create 2 of the same string if it's the lesser amount of alphabet.

So I've tried

S-> A | B
A -> aV | a
V -> aV | aVb | bVa
B -> bT | b
T -> bT | aTb | bTa

This one also has problem because if you have a you need to have b on the opposite end.

Additionally, I know this is one of the huge problem in my process is that you start with 'a' or 'b' and use that as a flag for if there is more 'a' or there is more 'b'...

I've been trying to think the way where you can input an alphabet (i.e S -> aV | bV) so that I can start with any variable and I use cases or condition to go to different variable, but I end up with infinite variable situation.


texts: Enumerating all n-tuples over a finite domain

texts:
I would like to create an algorithm which takes in an integer n and returns an array whose entries give all n-tuples of nonnegative integers each of which is at most n, so like

A[n][0] = [0,0,0,...,0],
A[n][1] = [1,0,0,...,0], ...,
A[n][n^(n+1)]=[n,n,n,...,n],

that kind of thing.

If n is small, I can manually create n-many for loops to do this, but in general I would like to allow n to be large. Is there an easy workaround? Any help would be appreciated.


texts:
I have been reading a book about Decision Trees and it caught my attention the following part:

  In case of numeric attributes, decision trees can be geometrically
  interpreted as a collection of hyperplanes, each orthogonal to one of
  the axes

I tried to look for information about this in Internet, but I did not find anything. To what the author refers in this point?


texts:
N-Queens problem - maximum number of function calls.

  We say, that a backtracking algorithm (code below) 'checks' a setup of N queens, when the function isFree(n-1, y) is called for $0\leq y < n$ (so we check a possibility of placing n-th queen to already set n-1 queens). Justify that for $n\geq 4$ algorithm checks no more than $(\frac{n}{2}+1)\cdot n!$ different setups of n queens on the board. We may assume that there exists a solution for $n\geq 4$.

int queens()
{
    int k; // column
    b[0] = 0; // put a queen in the left-bottom corner
    k = 1; // move to column number 1
    while (k < n && k >= 0)
    {
        do // looking for a "free" square in column k, going up b[k]
        {b[k]++;}
        while(b[k] < n && !isFree(k,b[k]));

        if (b[k] < n) k++; // free square found
        else {b[k] = -1; k--;} // none free squares, move back to earlier column
    }

    return k; // if k=n solution found, k=-1 if there is no solution
}

At the first look, the exercise looked pretty simple to me and my solution was based on the time complexity and the symmetry of chessboard.

As we proved on the lecture, algorithm works in $O(n\cdot n!)$. I noticed that if there exists a solution for N-Queens problem, there has to be a symmetric solution, just as we "flip" the board. Using an assumption that for $n\geq 4$ the problem has a solution, it is enough to check solutions only up to $(\frac{n}{2}+1)$-th grid, because it is the middle of the board. That means: for even $n$ we check solutions up to the $(\frac{n}{2})$-th grid and for odd $n$ up to $(\frac{n}{2}+1)$-th. Then, we know that we will have a solution before we cross the middle of the board.

What I think about my answer is that it is pretty understandable and correct, as we have the time complexity and I can base my answer on it, lowering the number of solutions we have to check.

How else could I justify that the algorithm works no more than $(\frac{n}{2}+1)\cdot n!$ times, having in mind that my explanation was "not good enough" (as my teacher said)?


texts: Why does packet delivery time only count transmission time once?

texts:
Why is packet delivery time equal to transmission time + propagation delay, and not equal to 2*(transmission time) + propagation delay?

At the end of packet delivery time, doesn't that mean that those bits haven't been received?


texts:
I have a question on my homework causing some confusion.

  If L is a strict subset of L', and L' is a member of Co-NP, is L a member of Co-NP? True of False

Now I understand what belonging to Co-NP. Essentially means instead of deciding a yes instance we're deciding a no instance of the decidable problem.  I'm stuck on interpreting L' and what it is.

My guess at this point is that L is a member of Co-NP since it's a subset of L' which we're given is in Co-NP.


texts: Does every regular language have a linear grammar?

texts:
Some definitions and facts (from Wikipedia):

A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.
the left-linear or left regular grammars, in which all nonterminals in right hand sides are at the left ends;
the right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.
Collectively, these two special types of linear grammars are known as the regular grammars; both can describe exactly the regular languages.

Doubts

Fourth fact used word "collectively" and then "both". What does it actually mean?

there is both right linear and left linear grammar for all regular languages
there is either right linear or left linear grammar for all regular languages

Can all non-linear regular grammars be converted into linear regular grammars? (Is there any systematic procedure for that?)

Update

I got it now how we can translate RLG to LLG and vice versa. So any given regular language has both RLG and LLG. Now the second question is remaining: Can all non-linear regular grammars be converted into linear regular grammars?


texts: Why c_f (u, v) = f (v, u) if f (v, u) not in E?

texts: From page8 of the slide, I think $E$ is all the edges in the graph $G$. But why is $c_f (u, v) = f (v, u)$ if $f (v, u)$ is not in $E$? Why do we care about edge that is not in $E$?


texts: Is there a Context-free grammar for this language?

texts:
Is there a Context-free grammar for the following language:

$L=\{ x\#1^m|x \in \{0,1\}^* \text{ and the $m^{\text{th}}$ char in $x$ is 1} \}$

If so what is it? Because i couldn't find any. I also tried to prove there isn't (by the Pumping lemma for context-free languages), but it's given that a Context-free grammar does exist and I found an error in my "proof".

So what would be the grammar?

Here's the big picture of my proof:

Let's choose $m=n_0$ and take the word $w=0^{n_0}1\#1^{n_0+1}$ (so that $x$ is what's on the left side of $\#$) .

According to the lemma, $w$ can be written as $uvxyz$ and some conditions hold...

$|vxy| \leq n_0$

therefor, $vxy$ include only zeros ($0$'s).

Now let's choose k=2 and pump it up:

we get: $w_2=uv^2xy^2z$

which means, the number of $0$'s is now:

$n_0 + |v| + |y| \geq n_0 + 1$

(since $|vy| \geq 1$) .

Hence, the $m$th number (the $n_0$th in our case) is not $1$. It's actually $0$.

Hence, $w_2$ doesn't belong to $L$. Contradiction.

Hence, $L$ isn't Context-free.

I think i know where's my mistake in the proof:

$vxy$ isn't necessarily only $0$'s. It could have the last $n_0-1$ zero's and a $1$.


texts: Program transformations for numeric stability

texts:
There's tons of research on program transformations for optimization.  Is there any research on transformations that improve numeric stability?  Examples of such transformations might include:

Transform $\log(\exp(a)+\exp(b))$ into $\max(a,b)+\log(\exp(a-\max(a,b))+\exp(b-\max(a,b)))$
Convert multiplication of an inverse matrix times a vector into the solution to a linear system solver.
Automatically perform multiplications of small numbers in the log domain.

All the tricks I'm aware of for better numeric stability like this are pretty standard and something that every "good" numeric programmer always does.  Since the tricks are so standard and always applied, it makes sense that the compiler might be able to do them for us.


texts: Why is recursive programming problematic for branch predictors

texts:
Consider for example the following recursive program:

function fibonacci(int n) {
    if (n < 2) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

The question is now, why recursive programs are problematic for branch predictors? I think that this is due to the fact that the branch-instruction inside these programs follows a very hard to predict pattern. When considering for example fibonacci(4), it holds that

fibonacci(4) = fibonacci(2) + fibonacci(3)

fibonacci(4) = fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(2)

fibonacci(4) = fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1).

Thus the following function calls will be performed in this order:
fibonacci(2), fibonacci(3), fibonacci(0), fibonacci(1), fibonacci(1), fibonacci(2), fibonacci(1), fibonacci(0). This results in following sequence of Taken / Not Taken for the if-statement:
NT NT T T T NT T T, which is quite irregular.

My question is now, if my answer and reasoning is correct?


texts: How unallocated memory space is represented?

texts:
I'm doing C programming stuff, and I'd like to know little bit about memory management - My problem is that I'm not understanding where the computer (or the OS or the programs) stores the information related to allocated space and how the unallocated space information is processed and how it is reported as a runtime error.

I did many searches but didn't find any information about this stuff yet. Can anyone try to explain, or recommend any book or online course?


texts:
I am told to solve the recurrence
$$T(n)=10T(n/9)+n\lg(n)$$
using the Master theorem. I then try to use case 3. However, I am unable to show that for $f(n)=n\lg(n)$ then $10f(n/9) \leq cn\lg(n)$ for $c < 1$ and all sufficiently large $n$. Is it wrong to use case 3? Or does the Master theorem even apply?


texts: Applying the Pumping Lemma to aspecific string

texts:
Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$.
From my understanding of the Pumping Lemma, to show it would hold, I need to decompose $ s $ into $ s = xyz $ such that (1) $ xy^{i}z \in A, i \geq 0 $, (2) $ y \neq \epsilon $, and (3) $ |xy| \leq p $.
For cases where $ p \geq 2 $, the decomposition makes sense to me and appears to be quite trivial.  For example, when $ p = 2 $, then $ s = aaaa $, and can be decomposed into $xyz$ where $x = a, y = a, z = aa $, which satisfies the conditions above above.  Induction could be used to show this holds for larger values of $ p $.
However, I am struggling on the case where $ p = 1 $.  Here, $ s = aa $, and it seems like there are not enough symbols to decompose into $ xyz $.  My best guess would be to choose $ x = a, y = a, z = \epsilon $, but for some reason this doesn't feel legal -- can you ad-hoc assign pieces of $ xyz $ to be $ \epsilon $?  Also, I believe this decomposition would fail to satisfy condition (3) above.  Can you offer some guidance on understanding what is happening in the case where $ p = 1 $?
Thanks for your time!


texts: Dijkstra shortest path yields unintuitive results

texts:
Considering the following nodes with edge weights in red, Dijkstra's shortest path algorithm seems to return incorrect results, at least by the definition of the steps on wikipedia. By those rules, the distance from 0 to 2 will be calculated by passing through 1 instead of 3.

The final distances (from 0) would come out to:

0 -> 0

1 -> 0.2

2 -> 1000.2

3 -> 0.5

The weights in this case are bi-directional but I don't see a way for information of the connection between 2 and 3 to ever affect the final distance between 0 and 2. Am I missing something about the limitations of this algorithm on this type of graph or are the steps listed incorrect?


texts:
I'm reading this well-known paper On Universes in Type Theory.
At first I expected something similar to Setω in Agda, but it turns out that it's even something more general.
It seems to generalize the universe construction from a plain inductive-recursive type to a binder (similar to $\Pi$ and $\Sigma$).
The main question I want to ask is, what's the intention behind it?

Here's some Idris code defining usual Tarski-style universes:

mutual

  public export data U : (level : Nat) -> Type where
    GroundU : Ground -> U level
    BinderU : Binder -> (a : U level) -> (b : (x : T {level} a) -> U level) -> U level
    UnivU   : U (S level)
    LiftU   : U level -> U (S level)

  public export T : {level : Nat} -> (code : U level) -> Type

I'm trying to generalize it into something like

mutual

  public export data U : (a : Type) -> (b : (x : a) -> Type) -> Type where
    GroundU : Ground -> U a ???
    ...

What should ??? be? The author of the paper just said universes should be closed under set formers.

edit: I think ??? is simply b ...


texts:
Wikipedia defines halting set as follows:

$H = \{(i, x) |$ program $i$ halts when run on input $x\}$

Ullman defines universal language as follows

$U = \{(M, w) |$ Turing machine $M$ accepts $w\}$

This link says:

The universal TM, $U$, is a TM which takes as input an encoded machine/string pair, $(M,w)$, and performs the actions of $M$ running with input string $w$. The most important achievement is to simulate the accepting (i.e., halting) behavior of M. That is we want:
$M$ halts on $w$   if and only if   $U$ halts on $E(M,w)$
or, in notational terms,
$M↓w$  if and only if  $U↓E(M,w)$

Note that $E()$ is encoding function. Also I feel above defines universal language somewhat different than what Ullman defines. While defining universal TM, Ullman says "$M$ accepts on $w$", whereas above link says "$U$ halts on $E(M,w)$". Its accept vs halt which is I am trying to point out. I feel TM can halt with or without accepting. So I feel the definitions of universal language differs in both sources. Q1. Right?
Thats why the link says:

HALT $= \{ x ∈ \{c,1\}^*: x = E(M,w)$ where $M↓w \}$
HALT is precisely the language accepted by the Universal Turing Machine, U:
$M↓w$  if and only if  $U↓E(M,w)$

where $↓$ seems to be symbol indicating "halts"
But Ullman says:

One often hears of the halting problem for TMs as a problem similar to $L_u$ - one that is RE but not recursive. In fact, the original TM of A. M. Turing accepted by halting, not by final state. We could define H(M) for TM M to be the set of the inputs $w$ such that it halts given input $w$, regardless of whether or not $M$ accepts $w$. Then, the halting problem is the set of pairs $(M,w)$ such that $w$ is in $H(M)$

By this, I feel Ullman disagrees that halting language is what is accepted by Universal TM.
The link also says:

In particular, the universal TM accepts HALT, but no TM can decide HALT.

If I get it correct, I believe "universal TM accepts HALT" means Universal UTM can simulate HTM (accepting TM and w as input) which checks whether input TM halts on input w. Q2. Am I right with this? Q3. But then that does not mean L(UTM) = L(HTM) as said by the same link in fourth quote. Right?
Q4. Can you summarise halting problem vs universal language? I feel the link is somewhat incorrect and Ullman is correct. I believe:

Halting language L(HTM) = {(TM,w) | TM halts on w with or without accepting}

Universal language L(UTM) = {(TM,w) | TM accepts w by halting in final state}

From above definitions, Halting language is not same as Universal language

Universal language can simulate Halting language as follows: (HTM,(TM,w)) | HTM accepts (TM,w) by halting in final state when TM halts on w with or without accepting w

Am I correct with above summary understanding?


texts: Proving the language of words with equal numbers of symbols non-context-free

texts:
Possible Duplicate:
  How to prove that a language is not context-free?

I'm having a hard time figuring this out, any help is appreciated.

Let EQUAL be the language of all words over $\Sigma = \{a,b,c\}$ that have the same number of $a$’s, $b$’s and $c$’s

$\qquad \text{EQUAL} = \{ w \in \Sigma^* \mid |w|_a = |w|_b = |w|_c \}$

The order of the letters doesn't matter. How can you prove that EQUAL is non-context-free?


texts: Divide and conquer algorithm to find points beneath certain (x, y) coordinates

texts:
Let's say you have a bunch of points on a cartesian plane. For a few of these points you would like to find how many of the other points lie within their (x, y) coordinate, see below for an example:

I'm trying to solve this for a school assignment and I haven't been able to find any existing algorithms to do some research on. Does anyone have some existing algorithms to solve this and could list them?


texts: Showing that minimal vertex deletion to a bipartite graph is NP-complete

texts:
Consider the following problem whose input instance is a simple graph $G$ and a natural integer $k$.

  Is there a set $S \subseteq V(G)$ such that $G - S$ is bipartite and $|S| \leq k$?

I would like to show that this problem is $\rm{NP}$-complete by reducing either 3-SAT, $k$-CLIQUE, $k$-DOMINATING SET or $k$-VERTEX COVER to it.

I believe I can reduce the 3-COLORING problem to it so I would only need to see how to reduce one of the mentioned problems to it.  But since that would be rather messy I am wondering if someone sees an elegant reduction to the aforementioned problems.

Also, is there a name for this decision problem?