texts: Hashing methods for validating dowloaded files

texts:
The standard algorithm to generate hashes of files which are downloaded is MD5. For example, when ISO files of Linux distributions are offered most of the time they also give the MD5 sum so that you can check if an error happened while downloading the file.

I'm aware of the fact that MD5 should not be used for password hashing as it is fast to compute. However, in the case of downloaded files I think it is desirable if it is computed fast.

Hence my question: Which hashing algorithm is recommended? What are the relevant criteria? If it is easy to find collisions of a hashing algorithm, does that automatically imply that it should not be used in scenarios where one does not expect attacks, but only "random" errors?


texts: Reducing k Vertex Cover to SAT (last clause problem)

texts:
I am working on a transformation from k Vertex Cover to SAT and I have some issues regarding the last clause in the boolean formula.

Here is my approach:
    $$\forall \text{ nodes } n_i \in V, \text{ invent variables } v_i$$
    $$\forall \text{ edges } (n_i, n_j) \in E, \text{ invent the terms } (v_i \lor v_j) \Rightarrow C_{edges}$$

Is this approach correct or am I missing something?


texts: What is the worst case running time for an algorithm that combines insertionsort and mergesort?

texts:
Suppose that we have an algorithm "combination" that uses insertionsort for $n < 100$ and mergesort for $n \geq 100$. Is the worst case running time of "combination" then $n^2$ or $n\log n$?

I was thinking that it's simply $n^2$, since the algorithm "combination" allows inputs larger than 100, in which case the worst case running time is $n^2$.


texts: What is wrong with this reasoning that finding the genus of a degree 3 bipartite graph is NP-complete?

texts:
Finding genus of a biparite graph is $NP$-complete and finding genus of a degree $3$ graph is $NP$-complete and so finding genus of a degree $3$ bipartite graph is $NP$-complete.

Though implication could be right is there any harm in reasoning this way on $NP$-completeness?


texts: Confusion regarding several time complexities including the logarithm

texts:
I am new to Advanced Algorithms and I have studied various samples on Google and StackExchange. What I understand is:

We use $O(\log n)$ complexity when  there is division of any $n$ number on each recursion (especially in divide and conquer).
I know that for binary search, we have time complexity $O(n \log n)$, I understood $\log n$ is because each time it halves the full $n$ size number list in a recursive manner until it finds the required element. But why is it multiplied with $n$ even we just traverse half of the $n$ size element for each execution so why we multiply $\log n$ with $n$?
Please give me any example explaining the complexity $O(n^2 \log n)$. I hope this will help me in understanding much better the above two questions.


texts: How to extract best illustrative sentences from documents for a given word?

texts:
I want to extract "best" sentences from the given (html) documents. Let me illustrate this with an example. I have a word "determine". Now I have hundreds of html files having paragraphs and sentences that contain this word. Out of those sentences, I want to collect and score only those that are capable of describing or illustrating the meaning of "determine". Lets go further, following are the sentences I have collected from the web (from google search for the word, vocabulary.com, merriam-webster.com, yourdictionary.com) for the word "determine":

It will be her mental attitude that determines her future.
Officials are working with state police to determine the cause of a deadly bus crash.
They are unable to accurately determine the ship's position at this time.
The program officers were determined to do better on that front.
And how did you determine that?

In my case, I would like my algorithm to filter out (4) and (5) since they seem to be incomplete sentences in the sense they won't be able to better "illustrate" the word "determine". I won't entertain (1) as well since this sentence is not stronger enough to help the reader visualize the use of the word "determine", if we assume the reader is reading the word for the first time. Now for the remaining sentences (2) and (3), I would like to rate them to find their "usefulness".

For sure this is NLP problem and requires extensive research work to achieve. But still I am new to this domain, and it would be extremely helpful if anyone could point me towards the related works. I believe this forum is the good one to put such queries related to computer science.


texts: Mathematics Courses for Computer Scientists

texts: I am looking for standard math courses (Calculus 1, Calculus 2, Linear Algebra, etc.) that were developed specifically for computer scientists, and use computer-science examples for motivation. For example, the pagerank algorithm can be used to motivate eigenvectors and eigenvalues.


texts:
As far as I understand, you receive an output from a quantum computer for an algorithm in the form of an amplitude, which is one of the many states your qubits may be in, however this amplitude is a complex number.

I understand that you have to square the amplitude to find the probability of finding that amplitude, but how do you convert that original amplitude into something relevant to the problem (i.e. that 3*5=15)? Is there coding within the algorithm to change the amplitude into a malleable answer?


texts:
In his paper The Bose-Nelson Sorting Problem (1973, Chapter 15 of A Survey of Combinatorial theory on page 163 available on Google books), Knuth says that the optimal bound of 5 comparators for a 4-input sorting network comes from an "elementary information-theoretic argument".

Information theory is not a part of my tool set, yet I have to prove this result.

I have managed to construct a 5-comparator network that solves the problem, and am trying to prove that any 4-comparator network does not work.

I have managed to prove that 3 comparators are needed if we want the top output to be the max of all inputs. In fact, for each input, at least three comparators are needed, but I cannot prove that they are different for each output.


texts: Is zero allowed as an edge's weight, in a weighted graph?

texts:
I am trying to write a script that generates random graphs and I need to know if an edge in a weighted graph can have the 0 value.

actually it makes sense that 0 could be used as an edge's weight, but I've been working with graphs in last few days and I have never seen an example of it.


texts:
I tried to solve the recurrence $T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ with the master theorem but I can't get it to work.

How many arrays exist in each step in the recursion tree?

Or can I solve this problem some other way?

Thanks.


texts: Finding minimum number of bicliques that cover nodes on one side of a bipartite graph

texts:
Let $G=(U \cup V, E)$ denotes a bipartite graph. A biclique $C = (U, V)$ is a subgraph of $G$ induced by a pair of two disjoint subsets $U' \subseteq U$, $V' \subseteq V$, such that $\forall u \in U', v \in V':  (u, v) \in E$.

I'd like to identify the minimum number of bicliques such that the nodes on one side of the bipartite graph $G$ are covered, i.e. in an optimum solution $S$, consisting bicliques induced from $G$, (1) $\forall u \in U,$ there exists at least one biclique in $S$ containing $u$, and (2) $|S|$ is minimized.

More specifically, (1) I'm investigating if the problem with these constraints already studied? (2) If the problem is in polynomial time (PTIME), NP-hard, etc. (3) If there exists an approximate algorithm to solve it in PTIME?

Can anyone suggest anything on these questions? Is that possible to reduce it from vertex-cover?

I'm aware of biclique edge cover/partition problem that aims to find the minimum number of bicliques that cover all the edges in $G$, which is not exactly what I'm looking for.

Also, it's fine if bicliques are overlapped.

One application.
In a bipartite graph consisting products and their components on each side. One may be interested in finding the minimum number of groups of components such that components in a group have been used in the same set of products and altogether cover the whole set of products. Note that the solution does not need to cover all components but all the products.


texts: How to deal with arrays during Hoare-style correctness proofs

texts:
In the discussion around this question, Gilles mentions correctly that any correctness proof of an algorithm that uses arrays has to prove that there are no out-of-bounds array accesses; depending on the runtime model, this would cause a runtime error or access to non-array elements.

One common technique to perform such correctness proofs (at least in undergrad studies and probably in automated verification) is by using Hoare logic. I am not aware that the standard set of rules containes anything relating to arrays; they seem to be restricted to monadic variables.

I can imagine adding axioms of the form

$\qquad \displaystyle \frac{}{\{0 \leq i \lt A.\mathrm{length} \land {P[A[i]/E]} \}\ A[i] := E;\ \{P\}}$

However, it is not clear to me how you would deal with an array access on the right hand side, i.e. if it is part of a complex expression $E$ in some statement $x := E$.

  How can arrays accesses be modelled in Hoare logic so that the absence of invalid accesses can and has to be proven for program correctness?

Answers may assume that we disallow array elements to be used in statements other than $A[i] := E$ or as part of some $E$ in $x := E$ as this does not restrict expressiveness; we can always assign a temporary variable the desired value, i.e. write $t := A[i];\ \mathtt{if} ( t > 0 ) \dots$ instead of $\mathtt{if} ( A[i] > 0 )\dots$.


texts:
I may be misunderstanding here-- but are interrupts only found in BIOS and not UEFI systems?

More context:
"Through standardized calls to the BIOS (“interrupts” in computer parlance), the operating system can trigger the BIOS to read and write to the disk and interface with other hardware components."

I read this in a paper I'm reading and thought that interrupts may only be accessible in BIOS.  I found some old stackoverflow answers (https://stackoverflow.com/questions/15101183/does-booting-in-efi-mode-mean-that-i-shall-not-have-access-to-bios-interrupts) that also confused me into thinking that interrupts are not programmable/accessible in UEFI.


texts: Length of the solution calculation in Breadth-first

texts:
I'm trying to figure out how to calculate the route cost on this graph (it's the missionaries and cannibals game)

I have my definition as:

Mi = Missionary on the initial side, C = Cannibal on the initial side, B = Boat [I = Boat in the Initial Side, F = Boat on the Final Side],
Mf = Missionary on the other side of the river, Cf = Cannibal on the other side of the river
State: (Mi, Ci, B, Mf ,Cf)
Initial Status: (3, 3, I, 0,0)
Final Status: (0, 0, F, 3,3)
Status Space (All the valid statuses):
{(3,3,I,0,0),(3,2,F,0,1),(2,2,F,1,1),(3,1,F,0,2),(3,2,I,0,1),(3,0,F,0,3),(3,1,I,0,2),(1,1,F,2,2),(2,2,I,1,1),(0,2,F,3,1),(0,3,I,3,0),(0,1,F,3,2),(0,2,I,3,1),(2,2,I,1,1),(3,2,I,0,1),(0,0,F,3,3)}

Rules:

1.  Bote can only carry two people
2.  One person has to drive the boat
3.  Cannibals can't outnumber the missionaries or they the missionaries will be eaten.
Cost: 1 per crossing.

Exhaustive Search (or Brute Search):

(3, 3, I, 0, 0) -> (2, 2, F, 1, 1) -> (3,2,I,0,1), -> (3,2,I,0,1) -> (3,2,1,0,1) -> (3,0,F,0,3) -> (3,1,I,0,2) -> (1,1,F,2,2) -> (2,2,F,1,1) -> (0,2,F,3,1) -> (0,3,I,3,0) -> (0,1,F,3,2) -> (0,2,I,3,1) -> (0,0,F,3,3)

According to me and the graph the route cost for Exhaustive Search would be 11.

How can I calculate the route cost for that graph for Breadth-first?

I do know that Breadth-first I have to separate the graphs on levels and it will test each node on that level against the final result (depending on the direction, clockwise, or counterclockwise) but I'm not sure if I should take each node as a crossing (I'm getting 14 as length of the solution). For instance in the image I take the crossing from (3,3,I,0,0) to (3,2,F,0,1) as 1 and then there isn't more child-nodes on that branch so I should get back to (3,3,I,0,0) in order to reach the branch of (2,2,F,1,1) this I don't know If I should count it too or not

To get 14 I'm doing. (3, 3, I, 0, 0) -> (3,2,F,0,1) -> (2,2,F,1,1) -> (3,1,F,0,2) -> (3,2,I,0,1) -> (3,0,F,0,3) -> (3,1,I,0,2) -> (1,1,F,2,2) -> (2,2,I,1,1) -> (0,2,F,3,1) -> (0,3,1,3,0) -> (0,1,F,3,2) -> (0,2,I,3,1) -> (2,2,I,1,1) -> (0,0,F,3,3)

Because of this doubts I have troubles calculating the Length of the solution


texts:
Consider the the binary erasure channel, with input and output alphabet $\{0,?,1\}$ and channel matrix
\begin{bmatrix}
1-\lambda-\mu & \mu & \lambda\\
0 & 1 & 0\\
\lambda & \mu & 1-\lambda-\mu
\end{bmatrix}
I want to determine its capacity, i.e. maximize $I(X;Y)$ over the probabilities distribution of the input.
I have tried writing and rewriting $I(X;Y)$ in different ways but the expression gets too complicated and I can't find a way to assign values to $p(x)$ so that $I(X;Y)$ is maximized. Any suggestions? Thank you in advance.


texts: Uncertainty whether $\{a^i b^j c^k \mid i+j \le k\}$ is context-free or not

texts:
I'm having trouble with this particular language: $$\{a^i b^j c^k \mid i+j \le k\}$$

If it's not context-free, I don't know how to correctly apply the Pumping Lemma for CFLs; if it is context-free, I don't know how to create a context-free grammar that generates this language.

Which one applies? Can you help me out?


texts: Misunderstanding the Church-Rosser property

texts:
I am contemplating the Church-Rosser property and I clearly misunderstand it, but I do not exactly know why. If $x$ and $y$ are such that $x \overset{*}{\leftrightarrow} y$, then $x \overset{*}{\rightarrow} y$ and since $y \overset{*}{\rightarrow} y$, we have that both $x$ and $y$ reduce to $y$ (or $x$, for that matter). So, $x \downarrow y$. I am obviously making a mistake, but where?

$\rightarrow$ is an abstract relation on some set ("reduction"). $\overset{*}{\rightarrow}$ is its reflexive transitive closure, $\overset{*}{\leftrightarrow}$ is the associated reflexive transitive symmetric closure, $\downarrow$ is confluence.


texts: Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem

texts:
I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem.
The professor has used a while loop to find the root of the element, while I have implemented it using a recursive approach.
Which approach is better in terms of space complexity, and scalability for large arrays?

//Quick union method for Union-find algorithm. Lazy approach

import java.util.Scanner;

public class QuickUnionUF {

    private int [] id;
    public QuickUnionUF(int N)
    {
        id= new int[N];
        for(int i=0; i<id.length;++i)
        {
            id[i]=i;
        }
    }

    public int root(int p)
    {
        if(id[p]==p) return p;
        else return(root(id[p]));
    }

    public boolean isConnected(int p, int q)
    {
        return (root(p)==root(q));
    }

    public void union(int p, int q){
        int proot= root(p);
        int qroot= root(q);

        id[proot]= qroot;
    }

}

For the root function, the professor has used -

public int root(int p) {
        while (p != id[p])
            p = id[p];
        return p;
    }

https://algs4.cs.princeton.edu/15uf/


texts: Are there any online resources that list Computer Science problems and how they relate to real world scenarios?

texts:
I would like to see how CS problems/solutions/categories apply to real-world scenarios.
I never did any formal CS study, so apologies if this is a naive question.
Are there any online resources that describe such things?


texts:
If $f(n)$ is in $O(g(n))$ but not in $o(g(n))$, is it true that $f(n)$ is in $\Theta(g(n))$?

Similarly, $f(n)$ is $\Omega(g(n))$ but not in $\omega(g(n))$ implies $f(n)$ is in $\Theta(g(n))$?

If not, can you provide an explanation/counter-example, please?


texts: Spatial Locality in Cache - Which addresses are loaded?

texts:
I don't quite understand the concept of spatial locality in cacheing. I understand that on a cache miss, not only the specific address we want is loaded into the cache, but also "nearby addresses" are loaded too.

However, I can't understand WHICH addresses are loaded. I have an assignment with the following question:

The cache consists of 16 words (4 bytes for each word), and is arranged in blocks of 2 words each.
The following addresses are in BYTES in decimal base. The cache is initially empty.
12,8,24,28,36,44,48,52,60,64,68,76,136,140,144,148,152,220,224,228,220,224,228
Determine what are the addresses which are a MISS (determine whether it's a valid or a tag miss).

What is hard for me is to understand which addresses are loaded, when, for example, the address 12 is reached. Is 13 loaded into the cache? 14? 15? or maybe 11? How do I know that?

I think that if understand this fundamental question, I could answer this question with ease.


texts: Find a vertex that is equidistant to a set of vertices?

texts:
I need help with the following problem:

  Input:  An undirected, unweighted graph $G = (V,E)$ and a set of vertices $F \subseteq V$.

  Question:
  Find a vertex $v$ of $V$ such that the distance from each vertex of $F$ to $v$ is the same and all the distances are minimized?  Return None if there is no such $v$.

The runtime should be $O(|V| + |E|)$.

My thoughts were to do a breadth-first search for each vertex in $F$, so for each vertex in $F$, you store all vertices with their distances, then find the intersection of all these.

Is there a better way?


texts:
I'm learning an algorithm for graphs of maximum degree three.

My question is: should the graph of that type have at least one vertex with degree three.

For example if the maximum degree of some graph is 2, can we say that this graph is maximum degree three.

Thank you


texts: Difference between Binomial and Fibonacci heap (marking)

texts:
I am confused why Binomial heaps do not utilize marking.

Concerning Fibonacci heap children:

Each tree in a Fibonacci heap is allowed to lose at most two children before
that tree needs to be "reprocessed" at a later step. The marking step in the
Fibonacci heap allows the data structure to count how many children have
been lost so far. An unmarked node has lost no children, and a marked node
has lost one child. Once a marked node loses another child, it has lost two
children and thus needs to be moved back to the root list for reprocessing.

How do Binomial heaps not need marking? It seems like in Fibonacci, this is in place so that when a marked node loses another child, it knows to move it back to the root and reprocess. I do not understand how Binomial heaps can possibly handle this without marking.


texts: Finding a path crossing minimum number of distinct colors

texts:
Given a set $\cal D$ of unit disks in the plane and a set $C$ of colors. Every disk in $\cal D$ is colored with one of the colors in $C$. Note that multiple disks may be colored with the same color. Every color $c_i \in C$ is associated with a weight $w_i$.

for every path $p$ in the plane, we define the weight of $p$ as the sum of the weights of the colors that at least one of the circles with that color is crossed by $p$.

In addition, two points $s$ and $t$ is given in the plane and the goal is to find a path between $s$ and $t$ with the minimum total weight. What is the best approximation factor we can guarantee?


texts: Unambiguous grammar for regular expressions

texts:
How to define a non ambiguous grammar for regular expressions on the $\Sigma =
 \{a,b\}$ alphabet?

Given that:

If $\Theta = \{+, ^*, (,),\cdot, \emptyset\}$ is a set of symbols

A regular expression on $\Sigma$ is a string such that one of the following condition applies

$r = \emptyset$
$r \in \Sigma $
$r = (s+t)$ or $ r = (s\cdot t)$ or $r = s^*$


texts: why is every self-reducible language in pspace

texts: I understand that every self reducible language recursively queries its oracle with strings of length less than the input size. But how does that show that every such language can be solved in polynomial space?


texts: Is SAT in P if there are exponentially many clauses in the number of variables?

texts:
I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$.

I'd like to know why $\text{Long-SAT} \in P$. First I thought it is $\text{NPC}$ since I can do a polynomial-time reduction from $\text{SAT}$ to $\text{Long-SAT}$, no?

But maybe I can reduce $\text{2-SAT}$ to $\text{Long-SAT}$? How do I do that?


texts: Can a language recognized by a NFA be recognized by a push down or Turing machine?

texts: Every single NFA has an equivalent DFA representation so that every language recognized by NFA is recognized by the DFA, but is it also true that the language recognized by NFA is recognized by a push down automata and a Turing machine?


texts: Question about pointer in PCB structure and meaning of job queue

texts:
PCB structure exists inside kernel area. And in ready queue, which is Linked List, each Node of the queue is PCB.
And this mean PCB Node has the next address of PCB in the queue, right?? Then My question is this..

Does PCB structure has pointer field that has address of next PCB structure??

According to Wikipedia, Job Queue consists of process waiting to be allocated to Memory. But, in terms of 'process',
process means the program loaded on the Memory waiting to be executed or being executed. And how can Job Queue consists of process, that is not loaded onto the memory(I think we can't say it is process because it is not on the Memory)


texts: Complexity of variation of partition problem

texts:
I want to know whats the complexity of the following variant of the partition problem:

Partition problem:

http://en.wikipedia.org/wiki/Partition_problem

Suppose we have one set formed by integers and we want to partition the set in two subsets of the same size, the same cardinality(the same number of integers in each subset) in such a way that each subset equal a given number called S.

Let's call this problem "2-partition" like the 3 partition problem

What's the complexity of the problem is easier,is in P?

Is still in NP?

I tried looking on google but i didn`t found anything, i dont even know if the problem is mentioned in some book or publication

Thanks


texts: How to accomodate decision trees with infinite options

texts:
I know that once I have a graph or decision tree representation of a problem, there are many different ways I can get a computer to solve the problem. They're called search algorithms, and go by names such as Depth-First Search, or Breadth-First Search or A* Search, etc.

However, I have the following game that I would like to input to my computer. The game is simple, you pick ten numbers. If all ten of the numbers are the number 1, then you win.

However, there are an infinite amount of decisions that the computer could take even with picking the first number. It could choose 8, or pi, or -3, etc.

Thus, even if I use something like A* and program in a heuristic such that it's obvious to the computer that choosing 1 is the best option, the computer still wont have enough memory to evaluate the heuristic on other the other options and make an informed decision.

How can computers handle cases like this? What sort of data structures are used when dealing with situations where there is not enough memory to hold all of the data, but there is enough to hold the relevant data at any given time?

(Compressed sparse data structures come to mind, but I'm not exactly sure how they can be used here.)


texts: Why do we need "Bloom Filters" if we can use hash tables?

texts:
A Bloom filter is a probabilistic data structure designed to tell, rapidly and memory-efficiently, whether an element is in the set or no.

If we can use hash tables where we have O(1) in best time, O(n) in a very bad situations. Why do we need a new abstract data structure that look-up for an element with less certainty.
What are the scenarios where HashTables fails and demands the use of bloom filters?

When should bloom filters be used over hashtables and vice-versa?


texts:
I was asked the following question in an interview.

Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \otimes b$ is minimum, where $x\otimes y$ for to integers $x$ and $y$ is the bitwise xor operation of $x$ and $y$.

For example:

Input:

A = [3, 2, 9, 6, 1]
B = [4, 8, 5, 9]

Output

[6, 9, 6, 9]

Because when 4 is XORed with any element in A minimum value will occur when A[I] = 6

4 ^ 3 = 7
4 ^ 2 = 6
4 ^ 9 = 13
4 ^ 6 = 2
4 ^ 1 = 5

Here is my brute force solution in python.

def get_min_xor(A, B):

    ans = []

    for val_b in B:
        min_xor = val_b ^ A[0]

        for val_a in A:
            min_xor = min(min_xor, val_b ^ val_a)
            # print("{} ^ {} = {}".format(val_b, val_a, val_b ^ val_a))

        ans.append(min_xor ^ val_b)

    return ans

Any ideas on how this could be solved in sub O(MxN) time complexity?

I had the following idea in mind.
I would sort the array A in O(NlogN) time then for each element in B. I would try to find it's place in the array A using binary search.Let's say B[X] would fit at ith position in A then I would check the min XOR of B[X] ^ A[i-1] and B[X] ^ A[i+1]. But this approach won't work in all the cases. For example the following input

A = [1,2,3]
B = [2, 5, 8]

Output:

[2, 1, 1]

Here is the trie based solution

class trie(object):
    head = {}

    def convert_number(self, number):
        return format(number, '#032b')

    def add(self, number):
        cur_dict = self.head

        binary_number = self.convert_number(number)

        for bit in binary_number:

            if bit not in cur_dict:
                cur_dict[bit] = {}
            cur_dict = cur_dict[bit]

        cur_dict[number] = True

    def search(self, number):
        cur_dict = self.head

        binary_number = self.convert_number(number)

        for bit in binary_number:
            if bit not in cur_dict:
                if bit == "1":
                    cur_dict = cur_dict["0"]
                else:
                    cur_dict = cur_dict["1"]
            else:
                cur_dict = cur_dict[bit]

        return list(cur_dict.keys())[0]

def get_min_xor_with_trie(A,B):

    number_trie = trie()

    for val in A:
        number_trie.add(val)

    ans = []

    for val in B:
        ans.append(number_trie.search(val))

    return ans


texts: Do basic operators of RE (Union, Kleene star and Concatenation) have properties like associativity, commutativity, distrbutivity etc.?

texts:
So in regular algebra we have some basic operations defined such as multiplication, addition, subtraction and division.

For these operations/operators, we have some properties like commutativity, associativity and distributivity.

Is there an analogue set of properties for the operations/operators on that we do with Regular Expressions?

I also believe that the set of all regular expressions together with its operations that are defined on the members of regular expression set form an algebraic structure similar to the integers and common operators that we learn about at arithmetics.


texts:
From Wikipedia

  SPMD (single program, multiple data) is a technique employed to achieve parallelism; it is a subcategory of MIMD. Tasks are split up and run simultaneously on multiple processors with different input in order to obtain results faster.

Does a program running on SPMD runs as either multiple processes or a process
with multiple threads? If former, are the multiple processes runs the same program?
Wikipedia tries to compare SPMD with SIMD:

  In SPMD, multiple autonomous processors simultaneously execute the same program at independent points, rather than in the
  lockstep that SIMD imposes on different data. With SPMD, tasks can
  be executed on general purpose CPUs; SIMD requires vector processors
  to manipulate data streams. Note that the two are not mutually
  exclusive.

What does "at independent points" mean? Does point means time? If
yes, isn't "at independent points" contradict "simultaneously"?
Wikipedia also compares SPMD with SMP:

  Unlike SPMD, shared memory multiprocessing, also called symmetric multiprocessing or SMP, presents the programmer with a
  common memory space and the possibility to parallelize execution by
  having the program take different paths on different processors. The program starts executing on one processor and the execution
  splits in a parallel region, which is started when parallel
  directives are encountered. In a parallel region, the processors
  execute a single program on different data.  A typical example is
  the parallel DO loop, where different processors work on separate
  parts of the arrays involved in the loop. At the end of the loop,
  execution is synchronized, only one processor continues, and the
  others wait. The current standard interface for shared memory
  multiprocessing is OpenMP. It is usually implemented by
  lightweight processes, called threads.

From Section 6.3 of Computer Organization and Design, Fifth
Edition: The Hardware/Software interface by David A. Patterson, John
L. Hennessy:

  programmers normally write a single program that runs on all processors of an MIMD computer, relying on conditional statements
  when different processors should execute different sections of
  code. This style is called Single Program Multiple Data (SPMD),
  but it is just the normal way to program a MIMD computer.

I don't quite understand how SPMD and SMP are different as stated in
Wikipedia, and maybe some paraphrasing may help? In particular,
Wikipedia says in SMP, a program can take different paths on
different processors. In Patterson's book, in SPMD, a program can
also run different sections of code on different processors.

Wikipedia says "The current standard interface for shared memory
multiprocessing is OpenMP".  Is multithreading by OpenMP or PThread
on multiple processors SPMD or SMP?

Thanks.


texts: How do these additional cases fit into this Theorem about the optimal substructure of a longest common subsequence?

texts:
Theorem 15.1 (Optimal Substructure of an LCS)

Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,y_n)$ be sequences, and let $Z =(z_1,z_2,\dots,z_k)$ be any LCS.

If $x_m = y_n$, then $z_k = x_m = y_n$ and $Z_{k-1}$ is an LCS of $X_{m-1}$ and $Y_{n-1}$.

If $x_m \neq y_n$, then $z_k \neq x_m$  implies that Z is an LCS of $X_{m-1}$ and Y.

If $x_m \neq y_n$, then $z_k \neq y_n$ implies that Z is an LCS of X and $Y_{n-1}$.

format copied from related post
The above cases are intuitive and easily provable.
I do not understand additional cases not explicitly mentioned in the theorem:
What happens here:
$x_m \neq y_n$ and $z_k \neq x_m \neq y_n$
The above statement combines cases 2 and 3. Does that mean Z is an LCS of both LCS of $X_{m-1}$ and Y AND X and $Y_{n-1}$? That doesn't make sense to me.


texts: Because os is a special kind of program so does that also mean a normal program can run without os ?


texts: How to simulate a k tape non deterministic turing machine with 2 tapes?

texts:
The only thing I found online about this is the following blog: http://blog.computationalcomplexity.org/2005/03/tape-reduction.html

where they write:

  Roughly the simulation guesses every step of the transition function
  on one tape and uses the other tape to verify the transition function
  on each tape of the original machine one tape at a time.

How exactly do you guess the transition function? And if you guess it, then why do you need to verify it? Isn't the guess in non deterministic turing machines always correct?


texts: Which algorithms are usable for heatmaps and what are their pros and cons

texts:
This is a cross post from Stack Overflow, and DSP at Stackexchange since I cannot really decide which part of Stackexchange is most fitting. If this is the wrong place please tell me and I'll remove the question.

I have a matrix with numerical data. The matrix contains values from 0 to an arbitrary integer value.

Each element of the matrix is equivalent to a coordinate on a map.

I want to display that data as a heatmap overlayed the original map.

The three approaches I have found so far are

Linear interpolation. I guess the interpolation is don from the original datapoint to some set distance away from it in each direction.
Average of surrounding cells. Each empty cell gets the average value of the eight adjacent cells.
Gaussian blur as suggested on the SO thread.
Box blur with 1..n passes.

Are there any more methods? What are the pros and cons of the different approaches? What is a good source, online or print, for a discussion on heatmaps or similar problems?


texts: Does the distributive property apply to regular expressions?

texts:
Let $(Q,\Sigma,\delta, q_0, F)$ be a finite automaton, does
$$
(q_1a+q_2b)c=q_1ac+q_2bc
$$

hold for any $q_1,q_2\in Q$ and $a,b,c\in \Sigma$?

Here $Sa=\{\delta(q, a)\mid q\in S\}$ and $qa=\{q\}a$ for any $S\subseteq Q$, $q\in Q$ and $a\in\Sigma$. The operation "$+$" means set union.


texts: Avoiding loss of significance without series expansion

texts:
I have a problem on an assignment where I have to reduce the loss of significance due to subtraction for a function

$$\frac{\sin(x)}{x-\sqrt{x^2-1}}$$

without using a series expansion. I can get part way through the problem but get stuck where I can't remove the subtraction in the square root:

$$\frac{\sin(x)}{x-\sqrt{x^2-1}}\cdot\frac{x+\sqrt{x^2-1}}{x+\sqrt{x^2-1}}$$

$$x\sin(x)+\sin(x)\sqrt{x^2-1}$$

I still have the $x^2-1$ term in the square root which would cause loss of significance, I'm not sure how to get rid of this term or change it to a positive.


texts: How page table base register (PTBR) is used to locate the correct frame using Page Number?

texts:
I was reading about paging in OS , and one of the things I saw was the page table base register (PTBR).
If the CPU generates a logical address (Consists of Page number + Offset) it needs to be mapped to Physical address (Consists of Frame number + Offset).
In the mapping process there must be first a lookup in the Page table of the process to get the Frame corresponding to that page.
Now to get to the page table we need to get the location of the page table of that process in the main memory.
The starting location of the page table is stored in a register called page table base register (PTBR).
Now the page number part of the logical address is added with the value in the PTBR and the corresponding frame is found in the table as the following:

Since the PTBR stores the base physical address of the page table in memory (e.g. 14000), and the logical address contains the page number that the CPU wants to read data from. Now here is my question:

Is the page number part of the logical address is the starting address of the page?

For example: the virtual address is 16 bit and the size of each page is 1KB
page 0 --->starts at virtual address 0
page 1 --->starts at virtual address 1024
page 2 --->Starts at virtual address 2048
and so on ...
So if the CPU wants to read data from page 1, then the page number is "1024" and then this value is added to the value in the PTBR?
OR
The page number itself is added for example:  if the CPU wants to read data from "page 1", then the number "1" represents the Page number value and when it is added to PTBR value? in other way does the CPU deal with page Number or Starting address?
I know this is silly for a lot of you, but it really got me confused because I couldn't find any real example about it.


texts: Does Ford-Fulkerson always produce the left-most min-cut

texts:
When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found.

However, if you then use the left-over residual graph to produce a min-cut (by flood-filling outward from s along any edges or reverse edges with left-over capacity), it seems the same cut is obtained regardless of which flow-graph you use.

Is this true?

Is there a way to iterate over all cuts such that each iterator-step requires only polynomial time?


texts: Prize collecting Steiner tree on graph without weights on edges

texts:
I have been trying to find an easy-to-implement approximation algorithm on the problem of Prize collecting Steiner tree on node-weighted graph without weights on the edges. The closest I have come is the one in The prize collecting Steiner tree problem: Theory and Practice by Johnson, Minkoff and Phillips, but the GW algorithm provided won't work without weights on edges (I think).

The problem I'm trying to solve is:

Given a graph $G=(V,E,w)$, $w$ being a function assigning non-negative weights to nodes, and a set of query nodes $Q$, find a connected subgraph $H$ of $G$, spanning all nodes in $Q$, and also maximizing the following function

$$f(H) = \sum_{v\in V_H}w(v) + \min_{v \in V_H}\deg_H(v)$$

with $V_H \subseteq V$ being the set of nodes in $H$.

Keep in mind I need an easy to implement approximation algorithm to use as a baseline for comparison, so any LP or SDP ways to solve it, won't be of much help.


texts:
When we plan the motion of a robot we may apply the trapezoidal
decomposition of free space.  While applying the trapezoidal
decomposition we add nodes to both the centers of trapezoids and
vertical walls.
When a robot wants to traverse between obstacles it avoids the obstacles
by following the nodes added.  The nodes create a graph which provides a
smooth traverse between the obstacles (at least so we assume).  In this
case we assume that we are creating a graph using all nodes.
Is it possible to plan a graph with only using the center of trapezoid
or the center nodes of vertical walls?
My idea is; it depends on the situation (the position of obstacles, the
shape of the robot etc.)  But I could not image such graph which could
be changed to a new graph with only using the nodes on the vertical
walls. If we design the example do we need to increase the number of
edges?
I think it is not necessity to increase the number of edges to manage to
use only vertical walls' nodes, but I could not figure out how it could
be possible exactly.


texts: First Sets: If $A \to Ad\ |\ c$, what is $First(A)$?

texts:
Suppose that we have a grammar with the following rules:

$$S \to Aa\ |\ b\ |\ \varepsilon\\
A \to Ad\ |\ c$$

From looking at it I already know that $First(S) = \{b, \varepsilon, c\}$. My question is:

How to determine $First(A)$?

For instance, by looking at the rule $S \to Aa$ we know that $First(S)$ must include $First(A)$. $First(A)$ already includes $c$ (that's why $c \in First(S)$). but how to handle the rule $A \to Ad$.

Just by applying the algorithm for finding the $First$ set blindly, I will have that $First(A)$ "includes" $First(A)$, which confuses me.

As far as I understand in $A \to Ad\ |\ c$ there is a left recursion. By eliminating it we get the following rules

$A \to cA'\\
A' \to dA'$

Does this mean that $First(A)$ only contains $c$?

Does this mean that I can ignore a rule with left recursion and just look at the other (non-recursive) rules under that variable?

Thanks!


texts: Is there any standard for comparing runtimes experimentally?

texts:
My situation

I am writing a paper presenting a software module I developed and I want to compare its runtime to other modules for the same task.
I am aware of the drawbacks of runtime experiments, but please assume as given that there is no way around it in my case.
(I can and do deduce some properties theoretically, but it doesn’t suffice for everything.)

The specific scenarios I want to use for benchmarking have two parameters: the complexity $n$ of the problem and a random seed $r$ which determines the detailed problem. Mainly I want to show the dependence on $n$. Going by preliminary investigations and theory, the influence of $r$ on the runtime is minor or negligible. A single task takes at most ten minutes to complete.

Actual question

I am looking for some commonly accepted or published procedure on performing such experiments or at least a list of common pitfalls (ideally published).

What I found so far

Nothing. Internet searches turn up all sorts of unrelated results, but then I may not be using the right terminology. Including the keyword minimum, which I know to be a good standard (see below), didn’t help either.

How I would do it

Run all experiments on the same machine with potentially interfering software such as a GUI disabled as far as possible.
Subject all modules to the same selection of scenarios, i.e., the same $n$ and $r$.
For each scenario, test the different modules directly after each other in random order. With other words, the loop over the different modules is the innermost one. This should avoid bias on the different modules due to slow fluctuations of the machine’s performance (e.g., due to temperature changes). The random order should avoid bias through such effects as caching or one module always being tested after the same one.
For each $n$, take the minimum runtime over several scenarios with different seeds as the benchmark. This should avoid bias on the different modules due to short-time fluctuations of the machine’s performance that make individual runs exceptionally bad.


texts: Complexity of GF(2) and applications to cryptography

texts:
If I have a system of N polynomial equations with N unknowns in GF(2):

What are some good methods to solve them?
What's the highest value of N that can be reasonable solved?

Now, my root interest isn't GF, it's crypto.  Here's my reasoning:

Any function from a n-dimensional binary vector to {0,1} can be represented as a GF(2) polynomial function of n variables.
Thus, for instance, any cipher from (Plaintext, Key) to Ciphertext can be represented as a series of equations (one for each bit in the ciphertext), each a GF(2) polynomial of (p-bits + k-bits) variables.
Thus, if we know P and C, and we can solve systems of GF(2) equations, we can determine K.


texts: Independent set where two vertices need to have distance >= c

texts:
An independent set (IS) in a graph is a set $V' \subseteq V(G)$ of pairwise non-adjacent vertices.

I am interested in the generalization $c$-IS where two nodes in  $V' \subseteq V(G)$ need to have distance at least $c$ to any other vertex in $V'$.

Has this problem been studied before?


texts: How would you create a Turing machine that copies a string and prints it to the tape?

texts:
For example, if I have a start state of $i$ and a string $w$, how could I create a Turing machine that would halt when the tape content is $w \Box w$? The language is $\{a,b\}$.

My initial idea was a machine that:

On $i$, moves right and changes to $p$.

On $p$, if letter read is $a$, move $n+1$ cells to the right and change to $x$.

On $p$, if letter read is $b$, move $n+1$ cells to the right and change to $y$.

On $p$, if $\Box$, change to $h$.

On $x$, write $a$, move $n$ cells to the left and change to $p$.

On $y$, write $b$, move $n$ cells to the left and change to $p$.

On $h$, halt.

However, I don't think it'll work because Turing machines aren't allowed to move more than 1 cell at a time. Any help would be appreciated.


texts: Why we can't use non-deterministic turing machines in this case?

texts:
Can you explain me why we can't show decidability of problem using non-determinism ? I know that this problem (described below) is not decidability, however I can't understand why following reasoning is not working.

Problem
Given a context free grammar $G$, does there exists a word $w∈Σ^∗$ such that $w^4∈L(G)$ ?

My reasoning:
Lets show Turing machine which decide this problem. Let machine guesses some word $w$ (it is possible because word is finite and $Σ$ is finite) and check if (using CYK algorithm) $G$ generates $w^4$.

I totally don't understand why this approach doesn't work. After all, non-determinism is about guessing...


texts: I read the paper Certification-Cognizant Time-Triggered Scheduling of Mixed-Criticality Systems (Baruah and Fohler, in Proceedings of 32nd IEEE Real Time Systems Symposium, 2011; see Section 6) which proves a particular problem to be NP-hard in strong sense and in PSPACE. Then they proposed a polynomial algorithm for the same problem which is sufficient but not necessary. For this algorithm, they claim that if the algorithm finds a solution then it is correct. Does this algorithm a verifier type algorithm? I am new to the field of theoretical computer science research. If anyone may explain this concept. Thanks.


texts: Given the Equivalence relation R = { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes 1 and 2?

texts:
Given the Equivalence relation R =  { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes of 1 and 2?

I can't really see the equivalence classes of infinite sets. Only by having a drawing of all elements can I distinguish the answers, wich is not the case in the above mentioned example.

What would be the best way to tackle such problems?

Thanks!


texts: How does the token method of amortized analysis work in this example?

texts:
Below is the description of the answer to a question which says the following:

Design a data structure to support two operations for a dynamic multiset S of integers which allows duplicate values.

Insert operation for one element
Delete-larger-half(S) deletes the
    largest ceil(|S|/2) elements from S.
m insert and delete-larger-half
        operations run in O(m) time.
Also output the elements in O(|S|)
            time.

In answer unsorted array has been taken. I think delete-larger-half corresponds to deleting the |S|/2 elements with highest magnitude. Then how does deleting with median work unless there is n comparisons (i.e compare each element with the median). I suppose the amortized analysis is what is bringing out the complexity. I'm looking for an answer that can explain the token based amortized analysis by using the example in this question.

What I know already: Amortized analysis means doing some expensive work in previous steps which leads to worst case of a following step not happening as often. Every time the expensive step occurs, the probability of it happening again reduces more and more. On average it evens out giving a better amortized complexity. Example: implementing dynamic array which is probably what has been done in the solution linked below.

Link to solution: https://courses.csail.mit.edu/6.046/fall01/handouts/ps7sol.pdf

  You use an unsorted array, so insert takes O(1) worst-case time. For DELETE-LARGER-HALF,
      you use the linear-time median algorithm to find the median, then you use PARTITION to partition
      the array around the median, then you delete the larger side of the partition in O(1) time.
      For the amortized analysis, insert each item with 2 tokens on it. When you perform a DELETE-LARGER-HALF
      operation, each item in the list pays 1 token for the operation. When you delete the larger half, the
      tokens on these items are redistributed on the remaining items. If each item on the list starts with
      2 tokens, they each have one after the median finding, and then each item in the deleted half gives
      its token to one of the remaining items. Thus, there are always two tokens per item and we get
      constant amortized time.

I've not been able to understand the logic behind random assigning of token and taking it off.

In the answer, the insert has been assigned 2 tokens, the find median and partition take away 1 token total. And then deletion gives the 1 token. I understand that each time, delete-larger-half is called, the next delete-larger-half's cost reduces drastically but why exactly the values 2, 1, 1 have been chosen?


texts: Algorithm to compose identity from a set of permutations

texts: Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity permutation?


texts:
I would like to learn about different approaches to formal verification of software programs that goes beyond what Wikipedia has to offer. Ideally one would not only get an overview but also recommendations which books and articles to read next.

My goal is to be able to judge what parts of formal verification I could apply to my job as a software/network engineer. So if the overview had a practical slant it would be a plus. But I also don't mind theory at all since I have a rather solid background in pure maths.


texts: What does it mean when its said that most Turing Machines are not programmable?

texts:
I was reading this article. In its third paragraph of the third section, named The Classical computational theory of mind, it said that Most Turing Machines are not programmable. I got the literal meaning out of the statement.
I have only done Automata Theory 101 and the way I know Turing Machine, not much is making sense. A Turing Machine has a set of rules for deciding whether to write or move (LEFT or RIGHT) given current state and symbol on current cell.
Doesn't this make Turing Machine programmable as rules are decided in advance? Correct me if I am wrong. What does the writer mean when he said, "Most Turing Machines are not programmable"?


texts: Referential Transparency and Interchangeability

texts:
Being had spent hours trying to grasp referential transparency, I am finally inclined to regard this concept as confusing one rather than helpful. But maybe the problem is me...
Usually referential transparency is mentioned with regard to a function which can be replaced with another function by a compiler with the aim of incresing effectivenes in some way (let's restricted ourselves to "functions" in common programming languages sense here).
So what's the condition to be met to make possible this "replacement"? Let's consider the line given by cody:

Referential transparency is an operational notion: it describes what
happens when you evaluate a same piece of code (typically a function)
several times, namely, the return value is the same. In particular,
the evaluation context can generally be ignored when considering the
operational semantics of a referentially transparent language.

In other words, if a couple of functions always return the same value for the same argument(s), so they are interchangeable (and if they both do not affect "external world" (have no side effects) - otherwise it is supposed a compiler will not able to make the replacement).
Question #1: Is the concept of referential transparency only applicable to pure functions? If so, why is it?
For example, in terms of some logical system (let's refer this to a specification of some type of compiler or programming language, etc.) these two pretty non-pure functions can be considered interchangeable:
function DoSmthOdd1 (x) {
  launchSpaceX(); //a side effect
  var sum = K + x; // K is an external variable
  return sum;
}

function DoSmthOdd2 (x) {
  var sum = x + K;
  launchSpaceX();
  return sum;
}

Our logical system is not interested in the order an expression written by a programmer and it does not get frightened when an external variable is used "in the same (specified) way", so the compiler can replace DoSmthOdd1 with DoSmthOdd2. In the other hand, the very same logical system prescribes that the compiler must not replace two pure functions (of kind of "the same argument - the same return value") if they have different algorithm complexity (for e. g.).
Let's deem function equality to be interchangeability of two or more functions (= possibility to be replaced with each other) within the framework of a logical system. Then:
Question #2: Is referential transparency another word for conveing meaning of function equality (interchangeability) and with the only possible "the same argument - the same value" rule at that?
The issue is function equality is a binary relationship whereas referential transparency pretends to be an unary one. I can give an example of pure function (pure per se), but what is a (non-)referentially transparent function (if we consider it per se without making a comparsion with other functions)?
There is an example in the Expert Systems: Principles and Programming by Giarratano, Riley:
sum := f(x) + x; // f(x) changes the value of x passed by reference

The authors claim this function to be a non-rf because

Depending on how the compiler is written value of x might be the original value if it was saved on a stack, or the new value if x was not saved.
If one compiler evaluates expressions right to left while another evaluates left to right. In this case, f(x) + x would not evaluate the same as x + f(x) on different compilers.

But wait... all the above is just comparsion of different logical systems ("compilers"). In standard algebra f(x) + x and x + f(x) are equivalent and interchangeable but in the specification of our compiler they are not. So why do we need this analogy at all?
Question #3: Is it true that a function is referentially transparent if it can be replaced in the same way how it can be done in algebra?


texts: Summed-area table for circular range queries

texts: A summed-area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid [Wikipedia]. Is there any algorithm for quickly and efficiently generating the sum of values in a circular subset of a grid?


texts: Minimum cost problem of breaking containers in $O(n\log n)$

texts:
Can anyone kindly give me some hint on solving this?
There are $n$ water containers placed on the top of each other (container1 on top of container2, container2 on top of container3, ...), each with capacity $c_i$ and initial water $a_i$ ($a_i<c_i$).
In case of breakage of any container, all the water inside it will pour into the container below.
Each container will break if the water inside it is more than its capacity.
On the other hand, we can always break a container manually by paying the cost $p_i$.
Provide an algorithm to find the minimum cost to break the $n$th container in $O(n\log n)$.
Using a binary heap may be useful.


texts: Parallel bubble sorting on arbitrary graphs

texts:
Are there bubblesort-esque algorithms for sorting on arbitrary graphs?

I'm working on a problem in which $k$ robots are placed randomly on a graph and have to reach their respective goals as quickly as possible. The robots can only move one step at a time and no two robots can simultaneously occupy the same node, but adjacent robots are allowed to swap places. The analogy to bubble sort when $k = |V|$ and the graph is a line is almost perfect (the one difference is that I care more about the total time it takes in the real world for the robots to move and sort themselves, the makespan, rather than the number of comparisons or runtime per se. (It would also be nice to minimize the average time for a robot to get to its goal without later being displaced.)

I can prove an $O(k^2+kn)$ bound for the makespan using a simple algorithm in which the robots greedily follow shortest paths to their goals and where robot $x$ only swaps robot $y$ if $y$ is in $x$'s way and y is already at its own goal. But parallel bubblesorting an array takes only $O(n)$ time, and shearsort only takes $O(n^{1/2}\log n)$ time, so I feel like there should be a simple algorithm that is (provably) linear. I would be very happy with a linear result, even if it was just for gridlike graphs (graphs obtained by deleting nodes from grids, thus creating hallways and side rooms etc.), or for trees.


texts: Amdahl “validity of the single processor approach”

texts:
The following is Figure 1 in Gene M. Amdahl's "Validity of the single processor approach to achieving large scale computing capabilities" (1967) (PDF):

The text describes this as representing the performance (presumably vertical) as a function of the fraction of instructions that can be executed in parallel for three machines. Machine A has 32 arithmetic execution units, machine B has 3-deep pipelined execution units working on 8-element vectors, machine C has 3-deep pipelined execution units with 8-wide scalar execution (if I understood the descriptions correctly). With a note that "The probable region of operation is centered around a point corresponding to 25% data management overhead and 10% of the problem operations forced to be sequential."

How did Amdahl derive this graph and how is the graph meant to be interpreted?


texts: Decidability of languages containing bitstrings and their corresponding ones' complements

texts:
Consider strings $s \in \{0,1\}^*$. Define $c_1(s)$ to be the ones' complement of $s$; i.e., the string obtained from $s$ by inverting all of its bits. So, for example, $c_1(000111) = 111000$. Call a language $L \subset \{0,1\}^*$ ones' complement closed, or OCC, if $s' \in L$ $\iff$ $c_1(s') \in L$, provided $s'$ is not the empty string. Given these assumptions, I have a few questions.

Does there exist an OCC language that is both Turing-recognizable and not decidable?

Does there exist an OCC language $L$ with the property that both $L$ is not decidable and $\overline{L}$ is Turing-recognizable?

Does there exist an OCC language $L$ that is such that neither it nor $\overline{L}$ is Turing-recognizable?

I am having some trouble answering these questions because of how limited the alphabet $\{0,1\}$ is. I was thinking that perhaps this alphabet alone could be used to encode Turing machines, and from there we could talk about the well-known decidable/undecidable and recognizable/not-recognizable languages involving Turing machine encodings, but I'm not sure this is possible.


texts: Tree decomposition - Fastest algorithm in practise

texts:
I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph.

I found the paper "A linear time algorithm for finding tree-decompositions of small treewidth" [1] by Hans L. Bodlaender which return a tree-decompsiton with the  optimized tree-width and as the name says, the algorithm runs in linear time but since there are no (translation: I have not found ) any implementations, I am not sure if it's being used in practice or not.

Is the paper by Hans L. used in practice or does the constant factor make the algorithm useless?

[1] http://dl.acm.org/citation.cfm?id=167161

[2] http://www.treewidth.com/docs/libtw.pdf

Edit:
Linked
https://math.stackexchange.com/questions/1246421/tree-decomposition-by-hand-for-understanding


texts: Proof of the undecidability of compiler code optimization

texts:
While reading Compilers by Alfred Aho, I came across this statement:

The problem of generating the
optimal target code from a source program is undecidable in general.

The Wikipedia entry on optimizing compilers reiterates the same without a proof.
Here's my question: Is there a proof (formal or informal) of why this statement is true? If so, please provide it.


texts:
We are given the following grammar.

S-->AS/b

A-->SA/a

We have to tell if its LALR or not.

As we all know that LALR is only minimization of CLR, So first I constructed the CLR parsing table using canonical collection of LR(1) items.

In the table there was no conflict.But There is no minimization possible.Does that mean that the given grammar is LALR as there are no conflicts.


texts:
I could find that different texts follow different steps in the conversion of CFG to Chomsky Normal Form. I couldn't find any presumptions they made in the conversion steps. I have some questions regarding the conversion.

Most text books tell us about only two rules $A \rightarrow BC$ and $A \rightarrow a$. But some texts say that starting productions should not be in the right hand side. Why some stress on that rule and others not?
When talking about the rules some don't stress much on the condition of removing useless symbols. Is this condition mandatory or not?
Which is the best rule? Remove useless production, remove $\epsilon$ production, remove unit production, adjust the resulting productions so as to reflect the CNF rules.
Converting a grammar to Greibach normal form requires first converting the productions to Chomsky Normal Form?


texts: how to deduce a function subtype rule from a given function type definition

texts:
This question relates to liskov substitution principle seems to have two conventional meanings but is really a different question, so I'm posing it as a new question.

I'm doing a bit of research into an old language, Common Lisp, which defines function-type as follows:
An object f is of type (function (A) Y)  if every call (f x) is semantically equivalent to (the Y (f (the A x))).

"the" is a special operator which specifies that the value returned by the form is of the specified type.

My question is whether this definition of function-type is enough to derive subtype rules, and type intersection/union/complement rules?

For example if f is both (function (A) Y) and simultaneously of type (function (B) X), then can we say from the definition that f is of type (function ((and A B)) (and Y X)), or perhaps can we say that it is (function ((or A B)) (and X Y))?

The language (specified in the mid 1980s) specifies that the intersection rule, but not the complement nor the union rules.  The intersection of two function types is the former (function ((and A B)) (and Y X)), which might surprise some people.  I'm wondering

Whether this intersection rule follows from the definition?
Whether the rule is a contradiction?
Can we also derive the complement and union rules from the definition?
Can we derive a subtype rule?   I.e., if f is in (function (A) Y), then f is also in (function (B) X) if ...what....?

With regard to (4) we would like to say that if $Y \subset X$ and $B \subset A$, then $(A\to Y) \subset (B\to X)$, but that would violate the intersection rule.


texts: Expected number of nodes in the independent set produced by a coloring algorithm on a graph with maximal degree $k$

texts:
We have a graph with $n$ nodes and maximal degree $k$. On this graph we run a coloring algorithm that finds a maximum independent set. The algorithm colors every node green with probability $\frac{1}{k}$ and colors the node red otherwise. This is done independently for every node. Return the independent set of nodes $x$ where $x$ is green and all neighbors of $x$ are red.

Show that the expected number of nodes in the independent set is at
least $\frac{cn}{k}$ where $c$ is some constant. (That is, $c$ does not depend on $k$).

Prove that the expected approximation ratio of the algorithm is at least $\frac{c}{k}$

I have no idea where to start on showing this.
I think I have figured out that the algorithm fails with probability $1-(1-\frac{1}{k})^k$ and that for any fixed node the probability for that node being put in the independent set is $\frac{1}{k}(1-\frac{1}{k})^k$. I am not sure, however, that these results are completely correct. That might be the reason I can't find a way of showing this or I could be missing something obvious. Help would be appreciated.
For anyone wondering, this is a practice problem for an upcoming exam.


texts: Is Simon's problem a good NP-intermediate candidate?

texts:
We know that $BPP \subseteq BQP$ but we have no proof $BPP \subset BQP$
(Though we have the proof that BQP $!=$ BPP with an oracle)

Since Simon's problem (as factoring) it's easily solvable by a quantum computer, and in exponential time complexity solvable by a classical computer, that's a hint of the separation between BQP and BPP and therefore this can be a pure NP problem.
Am I right?


texts:
Why do we need to flip the kernel in 2D convolution in the first place?
What's the benefit of this?
So, why can't we leave it unflipped?
http://www.songho.ca/dsp/convolution/convolution2d_example.html

input

kernel

output

"First, flip the kernel, which is the shaded box, in both horizontal and vertical direction"


texts: A universal operator necessarily generates $\neg x$ for input $x,…,x$

texts:
I originally posted this on math.stackexchange, but then deleted it and moved it here since I think it would fit this site more.

I saw a claim in a slideshow from a basic computer architecture course that given some boolean operator $T(x_1,...,x_n)$, if it is universal then necessarily:
$$T(x,...,x)=\neg x$$
However, I found no explicit mention of this claim anywhere else, including here. Is it correct? And if so can one please provide a proof or a proof-idea? Because it was provided as a fact completely unrelated to the rest of the slides I have no idea how to approach it, and I am not sure I even have the right tools to do so.

I have already seen this question, for example, but there the proof is tailored towards a specific function. My problem is with proving the general case.


texts: How do distributed algorithms for shortest path finding handle negative cycles?

texts: I am searching the web for an answer to this question, but I have only found answers for non-distributed algorithms. I am interested in this for its application to Distance Vector routing.


texts: A leftist tree is a variant of a binary heap, where the height of the left side of the tree is usually greater than the right side. Can a leftist tree's height ever increase after extracting the root? I am pretty sure it is impossible. How can a tree's height increase after taking away a node?


texts: Procedure to automatically solve field theorems in a SMT solver

texts:
I'm working with the Welder proof assistant. Basically, this system uses basic inference rules to modify the goal one wants to proof. At a latter step, the modified goals are passed to a SMT solver to see if it can prove them. I have already written automatic induction tactics that generate by themselves the induction hypothesis.

Now I want to write a procedure that will allow me to solve automatically the following problem:

  Proof basic field theory statements using the axioms of group and
  already proved lemmas.

Could you describe successful approaches to solve this problem?

Here I leave you the kind of axioms that I want to use:

And here you have the kind of goals I would like to proof automatically:

The idea is that the procedure is given the theorem, a list of lemmas (axioms of other proved theorems) and is able to deduce by itself the goal.


texts: How to find long trails in a multidigraph

texts:
I have a certain directed multigraph (a multigraph is graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I want to find its longest directed trails (a directed trail is a directed walk in which all edges are distinct). I.e., I'm looking for long walks with repeated nodes, but distinct edges.
Note that this is an NP-hard problem, otherwise I would have asked for the longest trails, not merely long trails.
My graph has no weights and it is weakly connected (that is, if each edge were converted to an undirected edge, that undirected graph would be connected).
I define walk/trail/path length as the number of edges in the walk.
My current program is based on traversing the graph in a DFS-like manner. If allowed to run for, e.g., half an hour, it produces trails of less than satisfactory length, and I know that longer trails should be possible in that time-budget.
Note that this problem is quite similar to the problem of finding the longest path of a directed graph, but with each edge having a max allowed visits number associated with it, equal to the cardinality of the corresponding edge set in the multidigraph.
In fact, it's possible to transform my problem to the longest path problem by producing the line graph of my graph and then finding its longest paths. However, I'm hoping for a smarter, more efficient solution.
The reason I'm mentioning the digraph longest path problem is that there are certain smart solutions to that problem, but they don't seem to translate to my multidigraph longest trail problem, sadly. In particular, I'm thinking of Miguel Raggi's Arxiv paper "Finding long simple paths in a weighted digraph using pseudo-topological orderings" (1609.07450). Those and other solutions are based on finding the longest path of a DAG subgraph (or, equivalently, some feedback arc set), which seems inapplicable to my problem (unless I do the mentioned line graph transformation), but I'd be happy for somebody here to prove me wrong.
What am I looking for, then?
Either of these two:

some method of finding long trails in my multidigraph, smarter than the naive approach
some method of finding long paths in my multidigraph's line graph; but it should be more efficient than just looking for an arbitrary digraph's longest paths, i.e., it should take into account the fact that the graph that is being searched through is a line graph.

Some characteristics of my graph
It's got around 500 nodes and around 20000 edges. If the multiple edges are accounted for, the graph's got around 160000 edges.
Some characteristics of my graph's condensation
I don't know if the info on the condensation is relevant, but it might be. See the Wikipedia page for strongly connected components for definitions and examples of graph condensations: https://en.wikipedia.org/wiki/Strongly_connected_component
There are less than 200 strongly connected components (equivalently, the condensation has less than 200 nodes), and the condensation's got around 220 edges. A certain SCC consists of more than 300 original nodes, while the other SCCs only have a single original node.
Info about node in-degree and out-degree over all nodes
This too, is of dubious importance, but it may be useful. The images are just thumbnails which link to the full-sized plots (made with Vega Lite):

Note about the scatterplots: each point in the scatterplots is "transparent", so that if there's only one datapoint in the same point of the plot it's displayed less prominently than if there are multiple in the same position.


texts: Estimating P in Amdahl's Law theoretically and in practice

texts:
In parallel computing, Amdahl's law is mainly used to predict the theoretical maximum speedup for program processing using multiple processors. If we denote the speed up by S then Amdahl’s law is given by the formula:

S=1/((1-P)+(P/N)

where P is the proportion of a system or program that can be made parallel, and 1-P is the proportion that remains serial. My question is: how can we compute or estimate P for a given program?

More specifically, my question has two parts:

How can we compute P theoretically?
How can we compute P in practice?

reference: https://www.techopedia.com/definition/17035/amdahls-law


texts:
The state space is decribed with 3 boolean variables $p,q$ and $r$ (so we have 8 states total). We have an action, let's say $a$. Action $a$ can be executed when $p=\text{False}$ and $q=\text{True}$ and the result is $p=\text{True}$, $q=\text{False}$ and $r=\text{False}$

How can we describe this action with STRIPS? My problem is this: since it isn't allowed on STRIPS to have negative literals, how can I describe it? For example, $\text{precondition}(a) = \{ \neg p,q \}$.


texts:
I found this problem on an algorithmic book. I have solve the requestments about time (O(n^2)) but I can't figure out how it works.

Input: Two n-bit integers x and y, where y ≥ 1

Output: The quotient and remainder of x divided by y

function divide(x, y)

    if x = 0:
        return (q, r) = (0, 0)

    (q, r) = divide(floor(x/2), y)

    q = 2 · q
    r = 2 · r

    if x is odd:
        r = r + 1

    if r ≥ y:
        r = r − y
        q = q + 1

    return (q, r)


texts: Does there exist a Turing complete typed lambda calculus?

texts: Do there exist any Turing complete typed lambda calculi? If so, what are a few examples?


texts: Find The "Best" Permutation of Inputs to Maximize Sum of Functions (or approximate "best")

texts:
The Problem (in words)
I want to sort $N$ items where the value of item $i$ at position $p$ is given by the function $f_i(p)$. The "best" order for these items is the one that maximizes the total value of my items but I am willing to accept a "good" order if it means finding it quickly.
The Problem (in maths)
Given $N$ monotonically decreasing functions $f_i$(x) where $1 <= i, x <= N$ and a set $S = \{1, 2, 3, ..., N\}$
Find $\alpha$, a permutation of $S$ which maximizes the objective function $g(\alpha) = \sum_{i=1}^{N} f_i(\alpha(i))$
In the event that this is a hard (e.g. NP-Complete) problem, I would rather have an approximation algorithm which returns a permutation that gives some local maxima of $g$ with provable guarantees on the distance to the optimal one.
My Thoughts
I am not very familiar with optimization problems but this feels like one that should be well known. I feel that if I knew the name of it I would have been able to search it on my own.
I am able to put more constraints on $f_i$ if needed but I would prefer to allow it to be any monotonically decreasing function.
I cannot brute force this as the values of $N$ I work with lead to far too many permutations.
My initial thought was to use a greedy algorithm which chooses the highest valued remaining item starting with position 1 and iterating until position N. I know this will not produce the best result but it is possible it produces a "good enough" result. I am not comfortable with using this greedy algorithm unless I have a proof of how effective it is.


texts: Edmonds-Karp Algorithm with both directed and undirected edges?

texts:
How would this work and be implemented?

If you have directed edges pointing away from the source to a bunch of other verticies, and directed edges pointing from those vertices to a sink, but have those vertices in the middle linked by undirected edges, how would flow work and be maximized?


texts: Amount of information in scaled-down images

texts:
Does an image that is scaled down lose more Information when
calculating averages of pixels rather than selecting single pixels?

One way to scale down an image is to replace 2x2 pixel blocks with the average of those four pixels, the other way is to just select the top-left pixel (or any other) instead.

Averaging is done by summation and integer division. We reduce the Problem to just scaling 2x2 images down to 1x1 images. For black and white images there are 16 possible images, 15 of those will be black and one will be white
thus the entropy of the scaled down image is 0.337 bits. For grayscale images with 5bits per pixel results
in 4.2524 bits, with 6bits per pixel we end up at 5.251 bits.

Does averaging really lose more information than just selecting top-left pixels?

I'm aware that you lose some information due to rounding but my calculations don't seem to converge so rounding wouldn't explain everything.


texts: difference between lzw and huffman coding technique

texts:
What is the difference between the LZW and Huffman's coding of text compression ?

I've read this and
this , but I'm not able to distinguish ?


texts: Converting python/numpy code into pseudocode

texts:
I've written some code that uses numpy's array broadcasting logic and need to convert it to pseudocode. Basically, $w\in R^{T}$ and $\beta\in R^{T \times M}$. If you have the following code using numpy arrays:
T = 100
M = 10
w = np.ones(T) / T
b = np.ones((T, M))
x = (w * b).sum(axis=0)

Numpy will automatically broadcast w to the correct axis of b and x becomes the weighted average of b along axis=1. How do I convert something like this into pseudocode?


texts: Do formulas involving fewer repetitions of variables give higher numerical precision?

texts:
I'm having some trouble doing SICP exercise 2.15. Please note that this question is not closed related to Lisp. Instead, it's closely related to numerical analysis.

  Exercise 2.15.  Eva Lu Ator, another user, has also noticed the
  different intervals computed by different but algebraically equivalent
  expressions. She says that a formula to compute with intervals using
  Alyssa's system will produce tighter error bounds if it can be written
  in such a form that no variable that represents an uncertain number is
  repeated. Thus, she says, par2 is a "better" program for parallel
  resistances than par1. Is she right? Why?

This question is a little confusing when pulled out of context, so please let me explain. The formula for parallel resistors can be written in two algebraically equivalent ways: $\frac{R_1R_2}{R_1+R_2}$ and $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$. However, it seems that computing parallel resistors with the second formula would always produce higher precision than using the first one.

My question is:

Which formula is better? $\frac{R_1R_2}{R_1+R_2}$ or $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$? Here "better" means provides higher precision.
Why it is better than the other one? Please prove your answer to the first question.

Here is my effort

  After many experiments, $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$ seems to
  be the better formula. I guess that the reason behind can be conclude
  as the fewer time uncertain numbers are repeated, the less
  uncertainty is introduced, and the higher precision we can get.

But that's not enough. I expect a more scientific and more rigorous answer.


texts: How to define a generic evaluation metric

texts:
Given a system (S) that accepts a tuple of parameters ($\alpha, \beta, \gamma \dots$ etc). These parameters affect the performance of S in a different way. For instance, decreasing $\alpha$ would improve performance of S at some rate, whereas decreasing $\beta$ has a reversed effect. How can one define a performance metric that captures the effects of all parameters in a simple, clear and correct manner.

If the system exists in reality, hence measurements can be taken arbitrarily, what approach one can use to achieve an accurate metric?

I give an example to clarify the question:

Suppose I have a sorting algorithm (A). Performance of A depends on the number of input numbers, precision of the numbers (32, 64, ...) bit, or whether they are partially sorted or not (assuming this can be quantified somehow). Let's limit ourselves to only these 3 factors.
If we say A sorts 1000 numbers in 1 millisecond. This doesn't say anything about precision nor entropy of the input. How can we come up with a standard, metric, or unit to describe the performance of A using preferably a single number with a single unit so that they capture all the factors mentioned above.


texts:
If, for example, there is a problem B which have exponential time verifier - a verifier that verify on exponential time - Does it 100% means that B decidable?

On one hand I thought - If there is a verifier - why can't I just decide for each input - using the verifier? On the other hand - from what I know - if it doesn't halt we wouldn't know it...

Thanks.


texts: Tight asymptotic bound for recursive algorithm

texts:
I have this algorithm where:

$$
T(n) =
\begin{cases}
  1 & \text{if}\; n \le 1 \\
  T(n/2) + 1 & \text{otherwise} \\
\end{cases}
$$

So, evaluating for $T(0), T(1), T(2), T(3), \ldots, T(n)$, I'm getting values like:
$$ 1, 1, 2, 2, 3, 3, \ldots, n, n $$

I assume this is twice the sum of $1$ to $n$, that would be the same as $n (n+1)$ or $n^2+2$.

Is my assumption ok?


texts: Time to evaluate a product of binomials $1 + x^i$

texts:
I am considering the asymptotic analysis required to convert a polynomial of the shape
$$P(x) = \prod_{i = 1}^{n}(1 + x^{s_i})$$
to its "full" representation, for example $$P(x) = 1+x^3+x^5+x^8+x^9+x^{12}+x^{14}+x^{17}.$$
Now, it would appear to me that we perform $n$ repetitions of performing $2^i$ multiplications, as for every expansion, we double the number of terms, as an example: $(1+x^2)(1+x^4)=1+x^2+x^4+x^6$. However, this smells a bit to me.
What is the asymptotic running time of expanding $P(x)$?
Note: Evaluating the polynomial may be done in $O(n\; t \log t$) using FFT, this is one solution.


texts: Algorithmic problem with many different time/space complexity solutions

texts:
I am preparing a lesson about algorithmic thinking for beginner programmers. I would like to show them an easy to understand problem which has as many solutions as possible with different time or space complexities. Sorting quickly comes to mind but if you avoid intentionally stupid solutions such as Bogosort, you only really have O(n^2) and O(n*log n) complexities.

In this respect I love the problem for computing the n-th Fibonacci number with integer arithmetic. You can do it exponentially as a naive approach, linearly if you are a bit clever, and even logarithmically if you are smart as hell. On the other hand, fibonacci numbers would not appear very practical to novice programmers. I would like something that is related to more practical problems as I do not want the students to think that algorithm design is something really abstract and theoretical.


texts: Fast query on the number of elements in a quarter plane

texts:
I have a scatter of 2D elements on a 2D plane.
I would like an efficient algorithm to prepare and query the number of points in a quarter plane (inclusive of boundary).
The quarter plane is defined by a point $(x,y)$. All elements $(x', y')$ where $x<=x'$ and $y<=y'$ are in the quarter plane.
For example

I have elements [(1,1), (2,2), (1,2), (3,2)],
My queries are [(1,1), (2,2), (3,3)]

The program should return [1,3,4].
This is for a past competitive programming challenge (WiFi Network problem in this competition)


texts: How does Logical Block Addressing affect OS disk scheduling optimizations such as SCAN (Elevator Algorithm)?

texts:
If the OS is scanning from one edge of the disk to the other, doing so from behind the Logical Block Addressing (LBA) abstraction, although it may aim to service requests in an elevator-like way, what guarantee do we have that the physical mapping correlates to what we see as the OS?

i.e. Could it be that servicing requests in logical order would end up seeking to random physical sectors, or do logical addresses still approximately reflect physical locations?


texts: Is well-founded recursion enough for practical total functional programming?

texts:
Total functional programming is a paradigm of non-Turing-complete programming languages where any program that type checks is proven to halt.
Well-founded recursion is a recursive definition of a function such that the definition of $f(x)$ only ever makes a recursive call $f(y)$ when $y<x$ for some well-founded relation $<$.
But the wikipedia page of Total functional programming refers also to other types of provably-terminating recursion:

[Termination is guaranteed by] a restricted form of recursion, which operates only upon 'reduced' forms of its arguments, such as Walther recursion, substructural recursion, or "strongly normalizing" as proven by abstract interpretation of code.

Are there any ways that one can do better than well-founded recursion, for practical total functional programming? I've always thought of well-founded recursion as "the most general provably terminating recursion"


texts: What is a good example of an NL-complete context free language?

texts:
Setting
Exactly as the title stated:

  Give an example of an $\mathsf{NL}$-complete context free language. $\newcommand{\angle}[1]{\langle #1 \rangle}$

Current Solution

Recall in the past we proved that $E_{DFA}$ is regular, so it is also context free. $E_{DFA}$ is in $\mathsf{NL}$ since given DFA $\mathcal M$ over $n$ states, we can start at the initial state and nondeterminstically traverse through states of $\mathcal M$ for at most $n$ steps, storing only the current state ($\log n$ space). Note if there is a path to an accept state, then it must be $\le n$ steps long. So if there is no path to an accept state within $n$ steps, then $\mathcal M$ does not accept any string, thus $\mathcal M \in E_{DFA}$.

Now we show $\overline{PATH} \le_l E_{DFA}$ and since $PATH$ is $\mathsf{NL}$-complete and $\mathsf{NL} = \mathsf{coNL}$, it follows that $E_{DFA}$ is also $\mathsf{NL}$-complete. Given an instance $\angle{G,s,t}$, we construct a DFA $\mathcal M$ by letting $s \in G$ be $q_{initial}$, and $t \in G$ be $q_{accept}$. We label the edge arbitrarily from $\{0,1\}$. Clearly this can be done in log-space. So now we show
    $$\angle{G,s,t} \in \overline{PATH} \Leftrightarrow \mathcal M \in E_{DFA}.$$

Suppose $\angle{G,s,t} \in \overline{PATH}$, then there is no path from $s$ to $t$, so there is no path from $q_{initial}$ to $q_{accept}$ in $\mathcal M$, then $\mathcal M$ does not accept any strings so it is in $E_{DFA}$. Conversely, suppose $\angle{G,s,t} \not\in E_{DFA}$, then there is a path from $s$ to $t$, taking this path in $\mathcal M$ correspond to a $\mathcal M$ accepting some string, so $\mathcal L(\mathcal M) \ne \emptyset$ and $\mathcal M \not\in E_{DFA}$.

Problem

I don't think my algorithm for proving $E_{DFA} \in \mathsf{NL}$ is correct.


texts: Is the extension of every undecidable theory undecidable?

texts:
While it is not the case that the extension of every decidable theory is decidable, is it true that:

the extension of every undecidable theory undecidable?

In other words, given an undecidable theory A, is it enough to show

$$A \subseteq B$$

to prove that B is undecidable?


texts: Find the duplicates in a list of floating point numbers

texts:
I receive a list of real numbers ( float ) between $0$ and $1$.  The list has length $N+1$ and I need to find two numbers on the list which are $\le \frac{1}{N}$ apart.  Here is an example test case:

[ 0.        ,  0.31662479,  0.63324958,  0.94987437,  0.26649916,
  0.58312395,  0.89974874,  0.21637353,  0.53299832,  0.84962311,
  0.1662479 ,  0.48287269,  0.79949748,  0.11612227,  0.43274706,
  0.74937186,  0.06599665]

One possibility I came up with is to multiply by $N=17$ and to take the integer part:

[ 0,  5, 10, 16,  4,  9, 15,  3,  9, 14,  2,  8, 13,  1,  7, 12,  1]

Then I have to find the location of two numbers in this list which are identical.

I would appreciate any solution to this problem with or without the intermediate multiplication step.  Or does this problem have a particular name in the field of algorithms?


texts: Regular Expression for {W | W contains an even number of As and an odd number of Bs, but doesn't contains AB}

texts:
While studying Automata at my University, I faced the following problem from SIPSER, M textbook:

  Consider D = { w | w contains an even number of as and an odd number of bs and doesn't contains the chain ab}. Draw an DFA with 5 states that recognizes D and a Regular Expression that generated D.

I tried doing the following DFA:

With the Regular Expression b(bb)*(aa)*

And that seemed quite right for me, but for chains that goes like baab it should be refused, but it isn't.

I couldn't find a way to fix it without adding another state to the DFA.

How can it be done?


texts: An example where Knuth-Morris-Pratt Algorithm is faster than Boyer-Moore?

texts:
This page about Knuth-Moriss-Pratt Algorithm compared to Boyer-Moore describes a possible case where the Boyer-Moore algorithm suffers from small skip distance while KMP could perform better.
I'm looking for a good example (text,pattern) that can clearly demonstrate this case.


texts:
I was reading Algorithms 4th Edition by Sedgewick et al. and I found this statement when discussing about the analysis of mergesort:

  The number of compares is at most n and no less than $\lfloor n/2 \rfloor$.

The code they gave for the merge() routine is shown below:

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi)
{   int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) aux[k] = a[j++];
        else if (j > hi) aux[k] = a[i++];
        else if (less(a[j], a[i])) aux[k] = a[j++];
        else aux[k] = a[i++];
    }
}

From the code, it seems that the number of compares will be at most $\lfloor n/2 \rfloor$ since if there are $n$ elements and we only compare pairs of them, there will be $\lfloor n/2 \rfloor$ compares.

Then again, I'm sure that I'm just missing something.

Thanks for any help.


texts: Set combination data structure (And storage complexity)

texts:
I have already posted this question on Stackoverflow, but I'm starting to think that this is the right place.

I have a problem where I am required to associate unique combinations from a set (unique subsets) to a given value. e.g.: Let S={a, b, c, d}, the required data structure should perform the following:

Key -> value

{a,b} -> value1
{a,c} -> value2
{c,d} -> value3

Property 1: The length of the set in the key is fixed (In this
example it's fixed to 2).
Property 2: The data structure does not
hold all possible subsets of S.

Question 1: What is the storage complexity of a simple Map holding these values? O(N!)? (given that |S| = N and it's not fixed)

Question 2: Is there any efficient data structure that could store such elements? (The most important efficiency would be required in storage complexity)


texts: Sorting a sorted array after increasing several elements

texts:
I know that most of the efficient sort algorithms can run with a complexity of $O(n\cdot log(n))$, but this is given an unsorted array.

However, given that the initial array is already sorted, is there an algorithm that can sort the array after multiplying several elements by 2 (or increasing them by some value) with complexity of $O(n)$?


texts: Is there an algorithm to find all vertices that are inside of a shape?

texts:
In computational geometry, is there any algorithm to find all vertices that are inside of a shape?

All vertices of graph has $x$- and $y$-coordinates
Shape is a set of points with $x$- and $y$-coordinates (unicyclic graph)
I need a fast algorithm. I am trying to avoid iterating over all vertices

Example:


texts: How does an automaton model a computer or something else?

texts:
An automaton, as I have seen so far, is used to tell if a string belongs to the language that the automaton recognizes. This is determined by the final state of the automaton running on the string as an input. I wonder what role the output of the automaton plays here for this decision problem?
I saw that an automaton (e.g. a Turing machine) can  model a computer. A computer takes  a program (which can solve any problem, such as evaluating a function, optimizing a function, searching for something, ...)as an input, and outputs what the program asks the computer to do. So  when an automaton models a computer, what do the inputs, outputs, states and transition/output rules of the automaton represent?
Some also said that an automaton models an algorithm.
My understanding is that an algorithm is informally a sequence of instructions ( I can't find  the formal definition for an algorithm, and wonder what it is), while an automaton  has a set of rules for transition and output. So I wonder how to understand that an automaton models an algorithm?

1 seems to be just a special case of 2, since the decision problem is just a kind of problem that a computer can solve.

Regarding 2 and 3, if an automaton models a computer and a program is  its input, since a program represents an algorithm,  isn't an algorithm an input to an automaton instead? Thanks.


texts: Data types a la carte -- over-engineered?

texts:
I'm working through Swierstra's 2008 paper. I'm up to Section 3 eval addExample, just before 'Automating injections'. And boy! does it need automating.

Is it just me, or is the whole thing over-engineered? Compare this in the paper

   addExample :: Expr (Val :+: Add)
   addExample = In (Inr (Add (In (Inl (Val 118))) (In (Inl (Val 1219)))))

With this made-up example

addExample3 :: Expr (CoPr (CoPr Val Add) (CoPr Add Mul))
addExample3 = In (Inl (Inr (Add (In (Inl (Inl (Val 333))))
                                  (In (Inr (Inl (Add (In (Inl (Inl (Val 303))))
                                                     (In (Inl (Inl (Val 330))))
                                  )   )    )    )
                  )   )    )

(Using type constructor CoPr instead of :+: in the paper. I've used layout there just to make sure I'm balancing my parens. This is as bad as LISP.)

eval addExample3  -- ===> 966 [correct]

So it works to have type constructor/functor Add appearing twice in the Expr. There's something wrong in the design here, because the CoProduct just needs to be a set of functors. Rather than using Swierstra's :+: I could use a type-level list(?) I notice the references don't include the HList paper, even though that was some 4 years earlier.

For each 'atomic' type constructor (Val, Add) there needs to be both a Functor instance, which is essentially determined from its arity; and an Eval instance, which makes it do something useful; so later in the paper there's a Render instance for each functor, to do something else useful.

For addExample and addExample3 above, GHC can infer the type. But when it gets to the smart (so-called) constructors, you need to supply the CoProduct type of the Expr. Can't those constructors (there's one for each atomic constructor) build the Expr type as it goes? (If the needed type constructor already appears, use Inl/Inr to get to it; if it doesn't appear, append it to the end of the CoProduct and generate the Inl/r.)

(I started looking at a-la-Carte because it's claimed the approach doesn't fit with Overlapping Instances. Just not so: it was easy to adapt it to use overlaps in Hugs. That's the least of the difficulties.)


texts: General name for linked lists based on hashes

texts:
I am thinking of a particular datastructure, but don't know the name of it.

A sequence of elements may be modeled by a collection of some X, where each X consists of:

The element, serialized as a bunch of bytes.
[a] The hash of the previous X  in the sequence, based on the bytes of both parts of that X in a predictable way or [b] some mechanism to denote no such X exists, i.e. that this is the first element.

Given a database that contains (at least) all relevant Xs, and a lookup mechanism by hash, we can take a single X and reconstruct the sequence of elements from it.

What is the general name (if it exists) of this datastructure in the literature? I.e.

What is the general name of X?
What is the general name of a sequence of Xs.

Note that although this looks like (and is inspired by) a blockchain or git commit object, it is more general: any list sequence could be so rewritten.

In comparison with the blockchain / git, the above does not make any statement about distributed databases, timestamps or contents of each element. It also notably differs from git at least in the sense that it is single-parent.


texts:
According to what I have read from two different sources, cache coloring is (was?) required in order to:

Counter the problem of aliasing: Prevent two different virtual addresses with the same physical address from mapping to different cache sets. (According to a CS Stack Exchange Answer)
Exploit the spatial locality property of virtual memory: by guaranteeing that two adjacent blocks of virtual memory (not necessarily adjacent in physical memory), do not map to the same cache index. (According to Wikipedia)

These seem to me to be fundamentally different definitions, and without comprehending the motivation for cache coloring, I can't seem to understand the mechanism for selecting the number of colors required. Are they really one and the same?

If the spatial locality of virtual memory is the primary motivation, is cache coloring really required for VIPT caches, where the index of the cache is derived from the virtual memory to begin with? Or is cache coloring simply used in VIPT caches to get around aliasing?


texts: NFA string acceptance with loop of epsilon transitions

texts:
I am writing an algorithm to test whether a NFA accepts or not a string, and there is a case in which I don't know how the algorithm should behave namely:

How should the algorithm behave? Should it stop and understand that no string is accepted or should it run for infinite time?


texts: Why $T(n)=6T(n-1) + n^3$ has such a mess solution?

texts:
I tried to solve the recurrence relation
$T(n) = 6T(n-1) + n^3$ using the tree method, and figured out that the root will be $n^3$, the second level will be $6^1(n-1)^3$, the third will be $6^2 (n-2)^3$, and so on.

The formula as I understood it is: $\sum_{i=0}^n 6^i(n-i)^3$.

After entering this in Wolfram, the result is:

$$ \sum_{i=0}^n 6^i(n-i)^3 = \frac{1}{625}(-125n^3-450n^2-630n+366(6^n-1)). $$

And it doesn't look like a valid solution. Did I miss anything?


texts: What are the over-lapping sub-problems in the “Turkish Roulette” dynamic Programming challenge?

texts:
I  came about this problem looking for interesting DP problems. I tried with no luck to find which could be the overlapping sub-problems to explore and solve and tabulate. But it is my belief there are none and this problem can't be solved using DP.

Explanation of the problem rules can be seen here:

A turskish Roulette is a type of roulette which consists of:

S amount of slots, each one with a number between -64 and 64.
B amount of balls, each one with a number between -64 and 64 too.
3 <= S <= 250   &   1 <= B <= 1/S
Each ball takes 2 slots of the roulette when they settle.
For each ball, let L be the sum of the 2 slots value numbers times it's number.
If the number L is negative the player loses that amount, else he wins that amount.
The balls will always settle in the order they were introduced into the roulette, ej. If I throw the balls 1, 2 & 3 then the ball 2 will always be between 1 and 3.
The objective is to find the max profit the owner of the roulette can have(max amount a player can lose in 1 turn) given a specific roulette with S number of slots and B number of balls each of them with their respective values.

I tried implementing a solution but the apparent lack of overlapping sub-problems made it impossible.

Things I already tried is the tabulation of the max_profit for a ball given a certain amount of slots. But I'm still short of the answer.

So, are there overlapping problems that can be helpful with memoization or tabulation?