texts: Can we ignore the postcondition in the Hoare conditional rule when there is a return statement?

texts:
I'm proving the correctness of naive string matching using Hoare logic. I have the following pseudocode:

   NaiveStringMatch(T,P)
        <precondition: T is an array of n > 0 characters
                       P is an array of m > 0 characters>

        for(s = 0 to T.length - P.length)
           <invariant: forall 0 ≤ s’ < s there is no match>
           j = 1
           while(j ≤ P.length and P[j] == T[s + j])
              <invariant: P[1 … j] matches T[s ... s + j]>
              j++
           if(j == P.length + 1)
              return s
        return -1
        <postcondition: if s > -1 then P[i] == T[i + s], 1 ≤ i ≤ m,
        and there is no s' < s for which this holds>

The thing I am struggling with is the conditional statement

if(j == P.length + 1)
   return s

In particular, the Hoare logic proof rule for conditionals, and the required postcondition, $\psi$, in this case. The conditional rule looks like this:

$$\frac{\{\phi \wedge B\}C_1 \{\psi\} \>\>\>\>\> \{\phi \wedge \neg B\}C_2 \{\psi\}} {\{\phi\} \>\> if \>\> B \>\> then \>\> C_1 \>\> else \>\> C_2 \>\> \{\psi\}}$$

My precondition, $\phi$, is this:
$$\phi = \text{for all shifts } 0 \leq s' < s \text{ there is no match, and } \\ P[1...j] \text{ match the corresponding characters in } T[s...s + j]$$

The postcondition, $\psi$, that I have been given is this:

$$\psi = \text{for all shifts } 0 \leq s' \leq s \text{ there is no match}$$

Looking a bit closer, we notice that when the inner loop terminates, then j ≤ P.length + 1. There are two cases:

1) if j < P.length + 1, then P does not match T at shift s, so the outer for loop invariant is maintained. After evaluating the if statement, we also satisfy $\psi$, since there is no match when $s' = s$.

2) if j == P.length + 1, P does match T at shift s, and the algorithm terminates, returning s. So the outer for loop invariant is maintained. Now this is where I am confused. After evaluating the if statement, how is $\psi$ satisfied here? Because after the if statement is executed, clearly we can find the shift $s' = s$ for which there is a valid match. So in my mind $\psi$ is not satisfied. Unless the return statement means we do not need to check $\psi$ and therefore we just ignore the fact that $\psi$ is not satisfied?


texts:
I'm working on a NFA to DFA conversion tool that is different from the Subset Construction and I need to test this tool.

In order to be sure that the immplementation has no bug I'd like to generate a random NFA with these properties:

The NFA should be connected
The NFA should have one initial state and one or more final states
The NFA should have ε-moves

Is there a known algorithm or a paper that explains how to generate this NFA automaton as random as possible?


texts: Finding rank of newly inserted node in AVL tree augmented with rank of node

texts: My prof was talking about how to augment a tree to efficiently find the key with a given rank. On the way to getting the right answer (store the size of the subtree rooted at each node), he proposed augmenting each node with it's rank. That way finding the node with a certain rank is a simple binary search. But he said this wouldn't work because insertion would be $\Theta(n)$. I understand that this is because in the worst case the newly inserted node has rank 0 and so the rank of each node in the tree must be incremented by 1. What I am interested in knowing is an algorithm for computing the rank of a newly inserted node. At first I thought that if a node $n$ is inserted to the left of a leaf $l$ with rank $k$ then the rank of $n$ is $k-1$, or $k+1$ if inserted right of $l$. I found a counter example to that so I know it is not the case. So how would this be done?


texts: Algorithm for computing partitions of a set of n elements into subsets of size m

texts:
I need an algorithm that can compute all the different partitions of a set of n elements into subsets of size m.

For example for $n=4$ for the set $\{a,b,c,d\}$ and $m=2$ the output should be

$\{\{\{a,b\},\{c,d\}\},\{\{a,c\},\{b,d\}\},\{\{b,c\},\{a,d\}\}\}$


texts: Concurrent priority queue with lazy increase-key

texts:
I could use a priority queue supporting the find-and-delete-min, and lazy-increase-key operations. The last term is my "invention". It should go like this:

The keys are held somewhere outside of the queue and get increased very often (more often than any other operation). Finding them is not the job of the queue. Ideally, the queue should do nothing when this happens. A later call to find-min may find out that the priority of the top element has changed and that another element is to be found. In worst case it can mean inspecting all the elements, but to me it looks like it should be fast on the average. Unfortunately, it also looks like I can't explain my idea properly... So let's assume the queue is implemented as a min-heap. When calling find-min, we find out that the priority of 1 has been increased to 9. The element is misplaced and must be moved somewhere else. The same is true for the 2. When looking at the 3, we see that its priority hasn't changed, and comparing it with the children of 2 tells us, that we've found the minimum.

- 1      -> 9
  - 2    -> 8
    - 7
    - 4
  - 3      =3
    - 6  -> 10
    - 5

The exact algorithm is unclear yet, but it could be a variant of this question.

Some practical figures: Imagine the heap being pretty large (n > 1000), key increasing being more than 10 times as common as find-and-delete-min. Moreover, bigger elements are more often increased than smaller ones. Given this, trying to restore the heap property upon each increase seems to be very wasteful.

Is there such a structure? Is there such a concurrent structure?


texts: Sorting algorithm which sorts half the possible inputs in linear time

texts:
Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time.
  (For the other half the algorithm can return anything, even a completely unsorted array.)

I know that using comparison model of sorting algorithms there is a lower bound of $\Omega(n \log n)$ so I try to make a proof by contradiction and to get to the fact that if such an algorithm exist then we can sort by comparison sort in linear time.


texts: Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?

texts:
By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes).

The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s terminated by an end-of-string character. The tape head starts at the beginning of the string. The goal is for the tape to contain the original string in reverse order, terminated by an end-of-string character, with the tape head returned to the beginning of the string when the Turing machine finally halts.

The Turing machine can use as large an alphabet as we like (so long as it contains $0$, $1$, and an end-of-string character), and can have as many states as we like. Is there a fixed Turing machine that can complete this task in time $o(n^2)$?

It's easy to do this in time $O(n^2)$ using just a few states and symbols. It seems intuitively clear that something prevents us from doing it more than a constant factor faster, but I've never been able to prove it, and I often worry late into the night about miraculous applications of network coding or voodoo magic that somehow get a logarithmic speedup...


texts: Can we count the number of inversions in time $\mathcal{O}(n)$?

texts:
It is possible to find the total number of inversions by $\mathcal{O}(n\log{}n)$ running time (extension of merge-sort algorithm for example).

Is there more asymptotically efficient way to do it? $\mathcal{O}(n)$?
Or is there any proof that’s not possible?


texts: Finding paths from the result of max flow

texts:
Suppose that I have run maxflow algorithm on a graph G and, as a result, I have a set of edges with flow on them.
I would like to enumerate all possible sets of paths that comprise the maxflow.
That is, each set of paths will make the max flow.
But I suspect there could be multiple set of such paths.


texts: Hashing a Specific Range Of a Character Array

texts:
I need to process queries to Hash various ranges of a character array. I am currently using the Arrays.hashCode from the standard java library. But the problem is that this method is too slow. Also my array remains the same throughout the process of hashing, I only am changing the range. To deal with this, I have to make an entire copy of the array everytime I process a query, and then compute the hash from the above function.

I am using Arrays.copyOfRange to create a copy everytime I process a query. I need to avoid this. So I was thinking of devising a hashing scheme of my own. This scheme should be such that I whould get a unique hash for each array range. Hashes should be same if all characters in the range are same.

Any Help on how to proceed with the making of such a hash function will be appreciated.


texts: Efficient (sublinear) approximation algorithms for matrix-vector multiplication?

texts:
Given a matrix $A \in \mathbb{R}^{n \times p}$ and a vector $x \in \mathbb{R}^p$, I am interested in computing the value of the mean matrix-vector product:

$$v = \frac{1}{n} Ax$$

If I did this using standard matrix-vector multiplication, then it would take $O(np)$ operations. I am wondering if there exists an approximate approach that can do better (that is sublinear in $n$ or $p$).


texts: Ray Tracing versus object-based rendering?

texts:
Intro graphics courses usually have a project that asks you to build a ray tracer to render a scene. Many graphics students entering grad school say that they want to work on ray tracing. And yet it seems that ray tracing is a dead field in venues like SIGGRAPH etc.

Is ray tracing really the best way to render a scene accurately with all desired illumination etc, and is it just the slow (read non-interactive) performance of ray tracers that makes them uninteresting, or is there something else ?


texts: representing set of non-overlaping string in formal notation

texts:
I want to represent a set of any substrings which come from an original string with constraint that all substrings should not be overlapped. To be more clear please consider the example below:

e.g.

orignal_string = "ABCDEFG"      // this can be any characters.
substring = {"ABC", "DE", "FG"} // right.
substring = {"A", "BCD"}        // right.
substring = {"BC", "FG"}        // right.
substring = {"AB", "ABC"}       // wrong, AB are overlapped.
substring = {"ABCD", "CDEFG"}   // wrong, CD are overlapped.

How to represent this in formal notation?


texts: Calculating miss rates of word-addressable and direct-mapped cache

texts:
This a problem in a computer architecture course that's giving me some trouble:

You have an application whose memory access pattern is a stream and its entire data set is 128kB. The data cache in  your machine has a capacity of 64kB. It is word-addressable and direct-mapped with 32B lines. It is able to fetch one line at a time.

Given the access pattern: 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, …, 32768, where each access is a 4B word.

What is the miss rate?
Can the miss rate be reduced by using a larger cache?
Can the miss rate be reduced if the size of the data set were reduced?

Here's what I think is going on:  The cache is initially empty, meaning each access will result in a compulsory miss.  So would this mean the miss rate is 100%, since no data is initially loaded and the pattern doesn't hit any address twice?

Any help understanding this would be much appreciated!


texts: Pumping lemma regular language can't be pumped

texts:
Suppose we have a regular language that describes every string with the exact length of 3.That is obviously a regular language and it still can't be pumped because there is no cyclic behavior in that string/ the corresponding dfa

Can you please help me figure out my mistake?


texts:
I know that a disadvantage of the index block system is that it can be wasteful of space if the files involved are mostly small in size, as index blocks are allocated from free space as required and at least one index block is needed for each file regardless of size. On average there is ½ block wastage per file in the index block system however what I don't understand is how the index block structure could possibly be modified to reduce this wastage.

If anyone can help it would be greatly appreciated.


texts:
Let $\operatorname{value}(x)$ be the result when the symbols of $x$ are multiplied from left to right according to
 $\qquad \displaystyle\begin{array}{c|ccc}
    \times & a & b & c \\
    \hline
    a & a & a & c \\
    b & c & a & b \\
    c & b & c & a
   \end{array}$

 Is $L=\{xy \mid |x|=|y| \land \operatorname{value}(x) = \operatorname{value}(y)\}$ regular?

 Is $L=\{xy \mid \operatorname{value}(x)= \operatorname{value}(y)\}$ regular?


texts: Why are inversions useful in computer science?

texts:
In the second chapter of Cormen's textbook on Algorithms, he lists a discrete mathematics exercise on so-called "inversions", defined as follows:

  Let $A[1 \ldots n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] > A[j]$, then the pair $(i, j)$ is called an inversion of $A$.

Question: Is this a mathematical concept that is used frequently in computer science? Are there some widely known applications of inversions that other people here know of? (I checked the wikipedia page for the concept, but it didn't list any).


texts: Why does Chord maintain a finger table instead of entire membership list (using SWIM)?

texts: Chord uses a finger table for querying, and it takes $O(\log n)$ to get the result. Why not maintain the entire membership list and get result in $O(1)$?


texts: Count of distinct substrings in string inside range

texts:
Having string $S$ of length $n$, finding the count of distinct substrings can be done in linear time using LCP array. Instead of asking for unique substrings count in whole string $S$, query $q$ containing indexing $(i,j)$ where $0 \le i \le  j < n$ is asking for count of distinct substring inside given query range for string $S[i..j]$.

My approach is just applying linear time construction of LCP array to each query. It gives complexity $O(|q|n)$. Number of queries could raise to order of $n$ so answering all queries makes it $O(n^2)$.

Can it be done better, than linear time for every query?

In general, if one process substring of string for which we already have suffix array, suffix tree, lcp array, are those structures not relevant anymore, and must be build from scratch again?


texts: Detecting errors changing an odd number of bits using CRC

texts:
I was studying CRC from lecture notes of Schwarzkopf but I am stuck at this statement:

If $G(x)$ is a factor of $E(x)$, then $G(1)$ would also have to be $1$.

What does this statement means? It is the third point in the third last block of the article whose link is given. I know a similar question is asked but that is a specific question. I want to understand this particular statement.


texts: Is a "tree" with $0$ vertices, $0$ edges or $1$ vertex, $0$ edges considered a valid tree?

texts:
For the following $2$ cases:

(1) $V = \emptyset, E = \emptyset $ (i.e. nothing at all)

(2) $V = \{v_0\}, E = \emptyset $ (i.e. only 1 root node $v_0$)

Are they considered a valid tree? It seems like different literature have different definitions.

I recall that I have read a data structures and algorithms book that defines "A tree is a set of nodes that either: is empty or has a designated node, called the root ...". According to this definition, (1) and (2) are both valid trees. I don't have the book on hand, but I am sure if you search the quoted sentence above in Google, you can get lots of results, as quite a lot of lecture notes follow this definition.

However, another definition of trees often met is defined in terms of graphs:

A tree is "a connected graph without a cycle".

Using this definition, my question is transformed to another question: "Is an empty graph a connected graph?" But the answer to the latter question is debatable according to here:

Is the empty graph connected?

My question is, which one is the more accepted definition?


texts: Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?

texts:
In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1]

  In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is surprisingly complex.

How to prove that?

In contrast, is there a language that is accepted by some DPDA but can't be accepted by any non-deterministic one counter machines?

Reference

[1]: John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. Boston/MA: Addison Wesley. P359.


texts:
I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST).

From my understanding:

The Nearest Neighbor Algorithm traverses a graph starting at one vertex, and then it travels to the next vertex following the edge with the shortest distance (lightest weight) between them.

An MST is a subgraph of the original graph whose vertices are all connected. The total of the edge weights in the subgraph should be as small as possible. You can use Kruskal's algorithm to find MSTs.

As I was looking at the paths taken when implementing the Nearest Neighbor Algorithm, I noticed that it could possibly sometimes return a MST.

Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?

It seems like it should be. It's terribly similar to Kruskal's algorithm (from what I have read so far). However, I never see it listed as a possible option for finding MSTs.

Thanks for any help in advance.

Edit for clarity:

The Nearest Neighbor Algorithm is described here. From what I read, it works like so:

startVertex = vertex V
for (egdes : totalEdges){
    find the edge with the smallest weight connected to vertex V that has    not been visited
}
nextVertex = vertex on the other end of the edge with the smallest weight
move to nextVertex

Here is an example:
Each vertex is visited and, looking at the red lines, you get an MST for that graph.

If you do that, you get an MST. My question is, is that a valid way of getting an MST? It seems like it is since it's so much like Kruskal's or Prim's algorithm.


texts: Power of 2 assumption in Divide and conquer

texts:
Currently doing an Algorithms course in my 2nd year of university (I am a maths student, but thankfully at Warwick University, we have quite a flexible degree). One of the topics we cover is the divide and conquer algorithmic paradigm. Some algorithms we have studied/I have read about are mergesort, max subarray problem, Strassen's algorithm etc.

When analyzing a lot of these algorithms, a simplifying assumption is generally made that the input size is a power of 2 - thus finding time complexity assuming input size is a power of 2. Surely this cannot constitute a general proof because of this assumption?


texts: What is the difference between storage media and storage devices

texts:
I am having a rather distressing confusion about whether storage media and storage devices are the same terms. I found on this yahoo answers page that there is a subtle difference but very tricky to understand.

I have googled a lot but cannot find the satisfying answer.

Can anyone kindly explain the difference between these two terms with easy-to-understand examples.

Regards


texts:
Formal grammars like regular expressions (REs) or context-free
grammars (CFGs) specify languages, i.e. sets of strings over an
alphabet.

Grammars themselves can be seen as languages, e.g.
the set of REs over $\{0, 1\}$. In that sense we
can specify a grammars by means of a meta-grammar. For example the language of all REs over a fixed alphabet can be
specified as a context-free grammar (CFG), e.g. like so

$$
   R \quad::=\quad 0 \ |\ a \ |\ RR \ |\  R+R \ |\ (R) \ |\  R^*
$$

where $a$ ranges over the ambient alphabet. One advantage of thinking of grammars in terms of their meta-grammar is that we can parse REs and check them for syntactic correctness.

What kind of meta-grammar (context-free or otherwise) allows us to
specify the language of CFGs over a given alphabet? What about subsets
of CFGs like LL(k) or LR(k)? I'm sure this has been investigated before as there are many tools that take grammars as input, e.g. parser generators.


texts: Determine the smallest $3$ numbers in a set using comparisons

texts:
Given  a set of $n$ distinct numbers, we would like to determine the smallest $3$ numbers in this set using comparisons. The elements can be determined using $n+O(\log n)$ comparisons.

This was the answer given in a multiple choice question. Now, we can easily do this using $3n\in O(n)$ comparisons. However I have been thinking about it and I can't do it in $n+O(\log n)$ comparisons.

They might be thinking about making a heap and using heapify which takes $O(n)$ time. However in heapify, the comparisons are $O(n)$ but not like $n+O\log(n)$ because every step in the heapify needs finding the minimum among $3$ numbers which takes $3$ comparisons so making a heap and finding the three minimums should be $3n$ comparisons.

So, can anyone tell me how to find three minimums in $n+O(\log n)$ comparisons or am I messing up somewhere in the heapify logic?


texts: Asymptotic complexity of function with two Input variables

texts:
Suppose I have a function with two input below.

$f(m,n) = \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000$.

Is it safe to say that $f(m,n)$ is $\mathcal{O}(m \log n)$, or is it $\mathcal{O}(n^2)$ instead? I think the first one is more representative as it includes the variable $m$. But that may not be the case if $n$ is relatively very larger than $m$.


texts: How are semaphores and test-and-set instructions connected?

texts: Cheers, so my textbook explains these parts very poorly, so I would gladly take any advice! I am confused between the test-and-set instructions, which per my book is a very common CPU instruction set, and the use of semaphores for which my book says that: a flag implemented using this way, is a semaphore. Does that mean that semaphores are a part of these instructions or the opposite? Also, if a operating system does not support semaphores, can it support test-and-set instructions and if yes, can you reach mutual exclusion this way? Thanks!


texts: Difference between decision tree and rule based reasoner

texts: I am new to this topic, and in some scientific papers I've been reading about prediction in sports I encountered the term rule based reasoner. Is it this term the same as a semantic reasoner( where the two main directions are forward and backwards chaining?). If yes, can you point out the difference between a decision tree and this? Because for me, it seems pretty much the same.


texts: Count comparisons in insertion sort that uses binary search to find correct postion

texts:
Assume a list $L$ is to be sorted using the following variation of insertion sort:  For $2 \le i \le n$, to insert key $L[i]$ do a binary search on the list $L[1..i-1]$ to find the correct position.

  How many key comparisons are done in the worst case?

I think the worst case is when $L$ is sorted in reverse order, which means each index $i$ from $i = 2$ to $n$ would require $2(\lg(i) + 1)$ key comparisons, which is $2[\sum\limits_{i=2}^n lg(i) + (n - 1)]$.  I'm pretty sure that is incorrect because I've never seen a summation like that and have no idea how to solve it.

  What is the total number of times keys are moved in the worst case?

I think this would be $\lg(i)$ moves on each iteration, or $\sum\limits_{i=2}^n lg(i)$.

Am I on the right track?


texts: Can someone explain this diagram about Slab Allocation?

texts:
I'm trying to understand how Slab Allocation works and why it is different or better than ordinary paging.

I found this diagram which I believe would be helpful if it had more explanation.

Some questions:

What do the 3KB and 7KB items represent? Must they be related somehow? Why are they packaged that way?
In the caches column, are the caches the grey boxes, or the white/blue boxes inside the grey boxes? Are the grey boxes a package of caches?
Are the slabs just the blue boxes or is the whole "Physical Contiguous Pages" a slab?

I'd really appreciate some help. THanks!


texts: Average between 2 max flow is a max flow?

texts:
I have 2 max-flow function f1,f2 that are different from one another (atleast on a single edge). I know they give each edge a natural even value.
I constrct 2 types of average functions:
A)$ g (e) = (f1(e)+f2(e))/2$
B) $h(e)=f1(e)*1/3 + f2(e)*2/3$
I want to prove or disproof their being max flow functions too.
My thoughts are to prove its true in both cases. I think for g I can look at the min-cut. I know the flow in the min-cut must be the same at that cut's capacity. So it means each edge in the cut is flowed like its capacity. Then the average is flowing the same for these edges... So g is a max flow too.
I feel the same argument shows h is max flow too. I believe it can be generelized for any fraction?
I would also like to hear whats the thoughts on my proof for g amd h? Am i right? Or did i mistake?


texts: Does anyone know the answer the following questions on converting logical - physical addresses

texts:
Due to the unforeseen pandemic, I am unable to speak to my tutor about the following question. I have emailed him, but I have not had an answer for weeks. Can someone please enlighten me.

Image and question to be answered below. Please provide an explanation, as I am struggling to find an answer:


texts: An obvious approach to NP = coNP, is there a counterexample?

texts:
Let's try to solve "co3SAT" with an NTM in polynomial time.  It seems we need, more or less, to guess a proof that the formula is unsatisfiable i.e. derive a contradiction.

We've got a formula in conjunctive normal form, a big AND of OR clauses, each clause with 3 literals.  Let's suppose we adopt the following strategy:  at each stage, we expand two of of the clauses using the distributive law (AND distributes over OR), and simplify the result whenever possible.  In the end, if the formula is unsatisfiable, we should get "false" from this procedure.

Is a lower bound known for this procedure (i.e. is it known whether this necessarily uses exponential time, given that we can use the non-determinism to select the optimal order in which the clauses are expanded)?

I read a little a bit about lower bounds for resolution techniques using the pigeonhole principle, but at first glance this seems like a different problem.


texts: If someone was designing a computer language, why would they require static members to be defined outside the class?

texts:
I am new to C++ and just learned that "The declaration of a static data member in the member list of a class is not a definition. You must define the static member outside of the class declaration, in namespace scope."

I am curious about why this is. Are there particular design advantages to making the rules of the language in this way? I am not asking: "tell me what Stroustrup was thinking when he made C++" -- which I know is an unfair question on these forums. I am asking: if someone sat down to make a computer language, why might they require that static data members are defined outside of the class. What are the advantages of this? What are the disadvantages? What kinds of costs would this incur? Why would someone put this quirk in their language? (Also I'm curious, but I know it's not totally appropriate to ask here: how did this quirk end up in C++).


texts: Is it possible that the diameter of a graph be shorter than the longest shortest path?

texts:
I used networkx to find the diameter of a graph that I have. It gave a diameter of 4. However, I found that between two particular nodes, using networkx's shortest path function, the path length is 5. I also coded dijkstra's algorithm and BFS from scratch and both returned a shortest path length of 5 too.

Is anything wrong with this? Isn't the diameter of a graph the longest shortest path?

This is what I'm using: http://vlado.fmf.uni-lj.si/pub/networks/data/Erdos/Erdos02.net


texts:
Is there a site that keeps track of the "current best algorithms", e.g., for certain combinatorial optimization problems?

In the latter there exists a range of classic problems such as MIN st-CUT or MAX FLOW, for which the best algorithms seem to be somewhat hidden in the literature.


texts: Subset-sum approximation algorithm running time

texts:
in 35.5 of CLRS i have read about algorithm to find sum as large as possible, but not larger than $t.$

Essential part of this algorithm is trimming. On every step you delete all numbers which close one to another, but one to represent them all.  Good explanation of the algorithm.

At page 7 from provided link or at page 1133 of ClSR 3rd edition you can find such a statement: $z'/z>1+\epsilon/2n.$ I think $z'$ and $z$ is numbers of elements before and after trimming. But i can't understand how they got such estimation. For example at first step trimming don't actually trim any element. We can devise example of sequence and epsilon to have no trimmed elements even at second step.

Can somebody, please, explain how they got such an estimation? Thanks.


texts: TSP 200-approximation, given $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ for all nodes $x,y,z$

texts:
Input: complete, undirected graph $G=(V,E)$ and cost function $c$
Assume for all nodes $x,y,z \in V$:  $c(x,z)\le c(x,y) + 100\cdot c(y,z)$
Find a 200-approximation polynomial time algorithm for the input.
I've seen the regular 2-approximation algorithm for a graph that satisfies the triangle inequality.

Find the MST $T$ for the graph
Find Euler Cycle by doubling the edges in $T$
Find Hamiltonian Cycle by removing each vertex that appears more than once

If $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ , then $c(x,z)\le c(x,y) + c(y,z)$ , so I figure we can use the same approximation algorithm. But I'm not sure how to prove that this gives a 200-approximation.


texts: Artificial intelligence - bridge and torch problem

texts:
I am doing a artificial intelligence course as part of my computer science degree.

I am stuck on a question about searching. The question is a version of the Bridge and torch problem.

Five people need to walk from this side to the other side of a bridge at night. The bridge is not in a very good condition and will hold at most 3 people at a time. They discover that they only have one torch. This means that after one,two,or three people have crossed the bridge, somebody (one, two, or three people) will have to come back with the torch so that the next persons can cross
safely. Each of the five people (Anna, Brett, Charles, David, and Ernest) take a different time to cross the bridge. Whenever 3 people cross they can only go as fast as the slowest person in the group. Since the torch has limited battery life they need to figure out which is the fastest way to get all 5 of them across the bridge. The times each take to get across are:

1. Anna: 5 Minutes
2. Barry: 7 Minutes
3. Charles: 1 minute
4. David: 2 minutes
5. Ernest: 9 minutes

I am asked how big the search space is of the problem. This is where I am getting stuck. There are 5 people, and two sides of the bridge where they can be. There is also a variable amount of people that can cross at a time (1-3 people).

My state representation is $\{ A, B, C, D, E \}$ representing the first letter of each person, with this being the set of people on the left side of the bridge. Hence, my goal state is $\{ \}$ - all people on the right side of the bridge.

I've also worked out the sequence of moves that leads to the optimal solution - my issue is just the size of the search space.

How do I go about calculating the size of the search space?


texts: Why not use Right Recursion to avoid Left Recursion?

texts:
I am reading about Representative Grammars from book, where I encountered the following grammar:

$$ E \rightarrow E + T \ | \ T $$
$$ T \rightarrow T * F \ | \ F $$
$$ F \rightarrow (E) \ | \ id$$

The above grammar is left-recursive, which is bad. So in order to eliminate left recursion, they changed it to the following:

$$ E \rightarrow TE' $$
$$ E' \rightarrow +TE' \ | \ \epsilon $$
$$ T \rightarrow FT' $$
$$ T' \rightarrow *FT' \ | \ \epsilon $$
$$ F \rightarrow (E) \ | \ id $$

But why bother so much? Why not simply use a right recursion instead, like the following:

$$ E \rightarrow T + E \ | \ T$$
$$ T \rightarrow F * T \ | \ F$$
$$ F \rightarrow (E) \ | \ id$$

So I am confused about whether the Right Recursive Grammar I thought of is same as the original grammar or not?
If not, what's the difference?
If they are same, why don't we write all grammars as Right Recursion?


texts: Regex for divisibility by 123 in binary strings

texts:
Is there a regex that checks for divisibility by 123 in binary strings?
This question can be found in the Algorithms’ textbook by Sedgewick and Wayne official website (question 7b in the Creative Exercises section).
Creating a regex to check if a binary string is divisible by 3 is simple: (0|1(01*0)*1) *
A regex to check if a binary string is divisible by 2 is also simple: (0|1)*0
And there are many questions on the Internet asking for a regex for divisibility by 7.
However, I could not find any resources related to a regex for checking if a binary string is divisible by 123.
These are the representations of some multiples of 123 in binary:

0 = 0
123 = 1111011
246 = 11110110
369 = 101110001
492 = 111101100
615 = 1001100111
738 = 1011100010
861 = 1101011101
984 = 1111011000
1107 = 10001010011
1230 = 10011001110

There doesn’t seem to be a pattern that stands out (even though there is probably one, since the question to check 123-divisibility with a regex exists).
There are, however, some similarities in some strings:
123, 246, 492 and 984 in binary are basically the same, but 246 has an extra 0 in the end, 492 has two extra 0s in the end and 984 has three extra 0s in the end.
369 and 738 in binary are basically the same, but 738 has an extra 0 in the end.
615 and 1230 in binary are basically the same, but 1230 has an extra 0 in the end.
Any ideas for a regular expression for such strings? Thanks!


texts: Finding an unambiguous grammar of a language provided by a CFG

texts:
I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman.

In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar for the language of this Context-Free Grammar (where epsilon is the empty string):

$$S \rightarrow aS | aSbS | \epsilon$$

I'm having difficulty describing this grammar formally, but I realize the number of a's is greater than or equal to the number of b's. And the string will always begin with an a (except for the empty string).

I have attempted to break the grammar into two parts to remove the ambiguity. After a few brute force attempts, I decided to distinctly have a variable generate only a's and the other variable generate an equal amount of a's and b's.

$$S \rightarrow A | B | \epsilon$$
$$A \rightarrow aA | a $$
$$B \rightarrow BB | aAbA | ab$$

The key part is when a re-write of B to a sentential form when an A occurs, only more a's can be generated in the string.

My question is does the new grammar I created generate the same language as the previous grammar? If not, what would be the correct grammar? I realize determining if two CFG are equivalent is undecidable; but I have no method of determining if I am correct.


texts: Relationship between RAM size and 32-bit vs 64-bit word size

texts: I know that x86 supports only 4GB of RAM, and that switching to x64 greatly increases the size of RAM you can use, but I don't understand why.  Why is the maximum supported ram size related to whether the processor is 32-bit or 64-bit?


texts: Returning random integer from interval based on last result and a seed

texts:
Suppose we have an interval of integers [a, b]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are explored, the function would start to return the same first random sequence again, in the same order.
Example: a=1, b=5
3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ...

This would be easy to achieve by shuffling an array of all elements between a and b, and repeating it once the array is finished. However, this would take too much memory space, and this is not suitable for my case (I might have millions of elements).
Instead, the function I'd like to have would be more or less like this:
f(a, b, n, seed) -> n+1

Where:
a - start of interval
b - end of interval
n - last element returned from list
seed - self-explanatory
n+1 - next random element from list, calculated by using the seed and the last element returned (n)

The trick is knowing some way to get a non-repeated number from the interval based only on the element returned before and the seed. In the end, it would behave like a circular list randomized at its initialization, but without using memory space.


texts:
I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion

  This follows already from Kuratowski's theorem: a clique is at most of size 4.

I've never heard of that theorem before and the exercise indicates to proof it with the fact, that the class of planar graphs is closed under sub graphs.
Thank you for your help!


texts:
This is a homework problem and I'm not sure how to do it correctly. It says "Prove ln(n) = Θ(log2 n) with n = odd number".
Bu using Natural logarithm rules, we can somehow know this is partcially true

However, I'm stuck with this since I don't understand how to do the whole procedure.


texts: What is this fraction-like "discrete mathematics"–style notation used for formal rules?

texts:
In the paper "A Conflict-Free Replicated JSON Datatype", I encountered this notation for formally defining "rules":

What is this notation called? How do I read it?

For example:

the DOC rule doesn't have anything in its "numerator" — why not?
the EXEC and GET rules appear to have two separate terms above the line, what does that mean?
the VAR rule stands out a bit as well, since while many other rules use some sort of arrow (which I would take to mean "implies") up top this one only seems to be saying that x is an element of something.
almost everything is peppered with an initial Ap, which the text describes as "the state of replica p is described by Ap, a finite partial function" — how would a savvy reader of this notation tend to "see" that part of every rule?

This site did suggest a related question that has some very similar-looking notation, over on the question What is the significance of ⟨B, s⟩ -> ⟨B', s'⟩ as the initial rule in this question about small-step semantics? — this is tagged as Operational semantics, and that does seem to be a strong lead. Is that indeed the framework under which I should be interpreting these figures? Could you easily summarize this in "crash course" form so that, even if I can't verify the correctness of their proofs, I could at least get a bit more understanding of what they are saying in this section?


texts:
Problem

Consider the pseudocode for the sort algorithm below, which takes as input an unsorted array $A$ of $n$ integers with no duplicates.

sort(A, i, j)
  if i = j
    return
  m = floor[(i + j)/2]
  sort(A, i, m)
  sort(A, m + 1, j)
  if A[m] > A[j]
    swap A[m] and A[j]
  sort(A, i, j - 1)

Write a recurrence that characterizes the runtime of sort(A, 0, n-1).

Attempted Solution

Let $T(n)$ be the run-time of sort(A, 0, n-1)

if i = j then return $\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$

m = floor[(i + j)/2] $\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$

sort(A, i, m) $\hspace{0.1cm} = \hspace{0.1cm} T(\frac{n}{2})$

sort(A, m + 1, j) $\hspace{0.1cm} = \hspace{0.1cm} T(\frac{n}{2})$

if A[m] > A[j] then swap A[m] and A[j] $\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$

sort(A, i, j - 1) $\hspace{0.1cm} = \hspace{0.1cm} T(n - 1)$

$\therefore T(n) \hspace{0.1cm} = \hspace{0.1cm} 2 \hspace{0.1cm} T(\frac{n}{2}) \hspace{0.1cm} + \hspace{0.1cm} T(n - 1) + \hspace{0.1cm} O\hspace{0.01cm}(1)$

Is this correct? Feedback would be greatly appreciated.

Sort in Action

The sort algorithm actually works. See this example to convince yourself.

https://imgur.com/G5FUewE


texts: What is the running time of this recursive algorithm?

texts:
I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037.

This is my proposed solution to compute the $n$th value:

a n | n<1        = 0
    | n<3        = 1
    | otherwise  = head (goods n)

goods n = [x | x <- [1..], isGood x n]

isGood x n = and [ x - a(n-k) /= a(n-k) - a(n-k-k) || a(n-k-k) == 0 | k <- [1..n] ]

Note that Haskell does not automatically cache or memoize these values.

The OEIS page for the sequence gives the fact that $a(n) \leq (n+1)/2$, so the [1..] could be replaced by [1..(n+1)/2], as the algorithm will never reach an $x$ greater than $\frac{n+1}{2}$.

Attempting to count function calls, I derived the following upper bound $T(n)$, the number of function calls that the algorithm takes for an input $n$:

$$ \begin{align}
 T(n) &= \sum_{x=1}^{(n+1)/{2}} \sum_{k=1}^{n} 2~T(n-k) + 2~T(n-2 k) \\
&\leq \sum_{x=1}^{(n+1)/{2}} \sum_{k=1}^{n} ~T(n-k)\\
&\leq \sum_{x=1}^{(n+1)/{2}} \sum_{k=1}^{n} 4~T(n-1)\\
&\leq \sum_{x=1}^{(n+1)/{2}} 4~n~T(n-1)\\
&\leq 4~n~T(n-1)~\frac{n+1}{2}\\
&\leq 2~n~(n+1)~T(n-1) )
\end{align}$$

I plugged the final formula into Mathematica:

RSolve[{T[n] == 2*T[n - 1]*n*(n + 1), T[1] == 1}, T[n], n]

And got, after a little simplification: $T(n) \leq ~2^n~n!~(n + 1)!$

The average ratio between this and the Haskell program execution time, for $n \in [12,20]$ is  $2.0 \cdot 10^{39}$ and the standard deviation of the ratios is around $6.0 \cdot 10^{39}$. (Curiously enough, the log plot of the ratios appears to be a straight line).

The ratios with the first line, defining $T(n)$, have a mean and standard deviation of $4.8 \cdot 10^6$ and $1.8 \cdot 10^6$, respectively, but its plot jumps around a lot.

How can I get a better bound on the time complexity of this algorithm?

Here is the algorithm in valid C (minus forward declarations), which I believe is roughly equivalent to the Haskell code:

int a(int n){
    if (n < 1) {
        return 0;
    } else if (n < 3) {
        return 1;
    } else {
        return lowestValid(n);
    }
}

int lowestValid(int n){
    int possible = 1; // Without checking, we know that this will not exceed (n+1)/2

    while (notGood(possible, n)) {
        possible++;
    }
    return possible;
}

int notGood(int possible, int n){
    int k = 1;

    while (k <= n) {
        if ( ((possible - a(n-k)) == (a(n-k) - a(n-2*k))) && (a(n-2*k) != 0) ) {
            return 1;
        } else {
            k++;
        }
    }
    return 0;
}

The C version takes about 5 minutes to compute $a(17)$ and the Haskell version takes about the same for $a(19)$.

The first times of the versions:

Haskell: [0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0e-2,3.0e-2,9.0e-2,0.34,1.42,11.77,71.68,184.37,1815.91]
C:       [2.0e-6, 1.0e-6, 1.0e-6, 2.0e-6, 1.0e-6, 6.0e-6, 0.00003,0.00027, 0.002209, 0.005127, 0.016665, 0.080549, 0.243611, 0.821537, 4.56265, 24.2044, 272.212]


texts: What are the most used statements in programming (ranked)?

texts:
I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (or at least for one modern language).
This is for a private research project where I am writing my own bytecode assembler and compiler for a custom language.
For example, the C#-code:
int a = 0;
int b = a * 2;
DoSomething(a, b);

would have 2 assignments and 1 function call.
So I'm wondering is there any study or somethig similar, regarding the usage frequency of statement types in general?
thx in advance


texts:
I'm currently reading about functional dependencies.
I've read Armstrong's axioms about:

Relexivity: $if$ $B\subseteq A$ $then$ $A\to B$
Augmentation: $if A\to B$ $then$ $AC\to BC$
Transitivity: $if A\to B$ $and$ $B\to C$ $then$ $A\to C$

and also about:

Union Rule: $if A\to B$ $and$ $A\to C$ $then$ $A\to BC$
Decomposition Rule: $if A\to BC$ $then$ $A\to B$ $and$ $A\to C$

I also know that for a relation R(A, B, C, D, E) that:
$if A\to B$ $then$ $ACDE\to B$.
 In fact, the left side could be any superset of A.
Is there a name for this rule?
I've looked at various books but while they use it in examples, they never mention a name.


texts: How to find an arrangement of a sequence that has the lowest cost

texts:
Given is a set of $n$ items: $x_1, x_2\ldots, x_n$. Additionally, we have a non-symmetrical evaluation function $f(x_i, x_j)$ that gives a cost value of two items. Note that $f(x_i, x_j)\neq f(x_j, x_i)$.

We want to find a list $y$ containing all items from $x$ exactly once such that the total cost of $y$, given by $F(y) = \sum_{i=1}^{n-1} f(x_i,x_{i+1})$, is minimal.

How can we do this?


texts:
I'm working on an application where the user can add 'calculation' fields to a page. Every calculation field is dependent on x amount of 'number' fields and 'calculation' fields. If calculation field A has field B as one of it's components, field B cannot be dependent on field A, as that would introduce circular dependancy problems.

Example:

Field A (numeric field, dynamic) ID: 1
Field B (numeric field, dynamic) ID: 2
Field C (numeric field, dynamic) ID: 3
Field D (calculation: A + B / C) ID: 4
Field E (calculation: A * D) ID: 5

Calculation fields are stored in the database as an array. A numeric value means a reference to another field (numeric or calculation), a string means an operator (+, -, /, * etc).

So field D would be stored as [1, '+', 2, '/', 3] and field E would be stored as [1, '*', 4].

Given the fact that all fields are dynamic and can be in different orders, I need to figure out the order in which I need to calculate the fields. For example field D needs to be calculated before I can calculate field E.

What is the most efficient way to figure out in what order I need to calculate the fields?

Note: in this case the order is 1 - 2 - 3 - 4 - 5, but that won't always be the case.

I'll be using PHP for the calculations, but of course this would be a generic algorithm which wouldn't be language specific.


texts: How sub-exponential time does $\text{3SAT}$ have to be to make $\text{NP} \neq\text{EXP}$? What else would imply $\text{NP} \neq\text{EXP}$?

texts:
The exponential-time hypothesis posits that if $\mathsf{3SAT}$ has NO subexponential time algorithm (i.e. one in $\mathcal O(2^{o(n)})$), then $\mathsf{P}\neq \mathsf{NP}$.
However, I am interested in the case that it does have such an algorithm.

From posts such as this, it seems that simply finding such an algorithm will not prove $\mathsf{NP} \neq\mathsf{EXP}$, so I am wondering just how subexponential the algorithm needs to be in order to guarantee this.

More generally, is there some sort of lists of conjectures/hypotheses that would imply $\mathsf{NP} \neq\mathsf{EXP}$?


texts: Why does this particular hashCode function help decrease collisions?

texts:
I just read in Effective Java about the hashCode method:

  Store some constant nonzero value, say, 17, in an int variable called result.
  For each significant field f in your object (each field taken into account by the equals method, that is), do the following:

  a. Compute an int hash code c for the field.

  b. Combine the hash code c computed in step 2.a into result as
  follows: result = 31 * result + c;

  A nonzero initial value is used in step 1 so the hash value will be
  affected by initial fields whose hash value, as computed in step 2.a,
  is zero.

  If zero were used as the initial value in step 1, the overall
  hash value would be unaffected by any such initial fields, which could
  increase collisions. The value 17 is arbitrary. The multiplication in
  step 2.b makes the result depend on the order of the fields, yielding
  a much better hash function if the class has multiple similar fields.

And that's their implementation of hashCode:

@Override public int hashCode() {
    result = 17;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNumber;
    hashCode = result;
    return result;
}

My questions are below:

How does the initial value 17 help us decrease collisions?
How does multiplying by 31 help us decrease collisions?
Why do we use 17 and 31? I know they are prime numbers. Is that why we use them?

I tried to come up with an example of a collision using a class with two and three integer fields, but didn't succeed. I'd glad, if you gave me a simple example of a collision.


texts:
Are there any known "adaptive data structures", for example, which can change on-fly from array to linked-list, or from the latter to binary tree depending on access patterns to it?
For example: small number of elements: stay as array.
5-10 elements: convert itself to linked list.
More elements: convert to binary tree.


texts: Is the language $\{a^nb^{2^n}|n\geq 0\}$ Turing recognizable/decidable?

texts: I have proven that it is not regular and context free. But is it Turing decidable/recognizable? I'm thinking yes, as I am able to write a Java program for it, and by the Church-Turing thesis the power of the Turing Machine and a Java program is equivalent (or am I wrong here?).


texts: Question about the definition of strings that GNFA's accept

texts:
In Sipser's "Introduction to the Theory of Computation" it states "A GNFA accepts a string $w$ in $Σ^{*}$ if $w = w_1 w_2 · · · w_k$ , where each $w_i$ is in $Σ^{*}$".

However, wouldn't a more precise definition be "A GNFA accepts a string $w$ in $Σ^{*}$ if $w = w_1 w_2 · · · w_k$ , where each $w_i$ is in $Σ$" ?


texts: How to devise an algorithm to arrange (resizable) windows on the screen to cover as much space as possible?

texts:
I would like to write a simple program that accepts a set of windows (width+height) and the screen resolution and outputs an arrangement of those windows on the screen such that the windows take the most space. Therefore it is possible to resize a window, while maintaining  output size >= initial size and the aspect ratio. So for window $i$, I'd like the algorithm to return a tuple $(x, y, width, height)$.

I believe this is might be a variation of 2D Knapsack. I've tried going over results around the web but they mostly had a lot of background (and no implementation) that made it hard for me to follow.

I'm less interested in the fastest possible algorithm, but more in something that is practical for my specific need.


texts:
I have been given several examples I the aim is to explain why it is not a Huffman code. So, for instance, the first one was:

$\{00,01,10,110\}$

This code is not Huffman becuase it has just one codeword of maximum length whereas there should be two as a minimum.

Next, the one I hava a problem in proving:

$\{01,10\}$

Why this code is not a Huffman code?


texts: Why is Savage's Vertex Cover algorithm a 2-approximation?

texts:
Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem.

Given graph $G$, start at arbitrary node and traverse $G$ depth-first
Obtain DFS tree $T$
return $V_C =$ internal nodes of $T$.

Now I read everywhere that this algorithm is supposed to yield a 2-approximation, but the only proof I found was here, and frankly, I don't get it and it's rather longish. Unfortunately also, the original paper is nowhere to be found. At other places where this was given as an exercise, I find the hint that one should first show that the tree $T$ admits a matching $|M| \ge \frac{1}{2} |V_C|$. But if I had proved that (which I have no clue how to do), I have no idea how to use that knowledge. I don't see how I can put bounds on the output of the algorithm without an estimate for the number of internal nodes of an arbitrary tree. And the way I see it, such a tree can have between $1$ and $n-1$ leaves (consider the graphs which are a chain, or a star, respectively).
So I am puzzled. How could one show that this is a 2-approximation?


texts: Vertex cover algorithms for directed graphs?

texts:
I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a directed graph.

Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a set of edges between vertices. The edges are directed so we can have $e_{ij} = 1$ but $e_{ji} = 0$ where $i,j \in V$. Here, $e_{ji} = 0$ would mean that there is no edge from $j$ to $i$.

My problem is as follows. I would like to find the smallest subset of vertices $S \subseteq V$ such that there is a path from every vertex in S to every vertex to V. That is, for every vertex $j \in V$, there is an $i \in S$ such that either:

$e_{i,j} > 0$ (edge between $i$ and $j$)
$e_{i,{k_1}}e_{{k_1,k_2}}$...$e_{{k_t,j}} > 0$ (path from $i$ to $j$)

I will assume that $e_{ii} = 1$ to ensure that such a subset exists, as I can set $S = V$. However, this is only optimal when the set of nodes is entirely disconnected.

I'm wondering if this a vertex cover problem? If so, are there algorithms for this problem? I'm slightly confused because most vertex cover algorithms are for problems where the graph is undirected (e.g., $e_{ij} = e_{ji}$). If not, are there algorithms to solve this problem?


texts: Connection between formula size and time complexity

texts:
Supposing we have a problem $P$ with input size $n$ encoded as a boolean formula $f$ in $n$ variabes which is a multilinear polynomial. Let $f$ have the smallest degree.

Is there a connection between time complexity of $P$ and degree of $f$ and number of monomials in $f$?


texts: How is term rewriting different from unification, and what's the difference between term rewriting languages and logic programming, like Prolog?


texts: Complexity classes closed under finite union and intersection, why not infinite union and intersection?

texts:
All "nice" Complexity classes are closed under finite union and intersection. (By "nice" I mean ones with complete problems or leaf languages, e.g. P, NP, PSPACE, etc.)

But such classes are not closed under infinite union and intersection. Why?


texts: What is the complexity class of performing a perfect disassembly of binary code?

texts: I have heard that the complexity class of performing a perfect disassembly of binary is undecidable. Is this correct? Are there any proofs of this?


texts: Can anyone think of applications of a 3 way (k-way) dot product in computer science or data mining

texts:
I have developed a locality sensitive hashing algorithm for the 3-way or k-way dot product. When I say 3-way dot product I mean the following. Suppose we have

$x,y,z \in [-1,1]^{S}$ for $S \in \mathbb{N}$.

Then the 3-way dot product is

$\sum_{i = 0}^{S}x_{i}y_{i}x_{i}$.

I was hoping to find some applications of the 3-way dot product in data mining or mining massive data sets.


texts:
I am trying to understand the proof that the axis parallel rectangles are PAC learnable in the realizable case. This means that given $\epsilon, \delta$ with enough data we can find a function $h$ such that $$\mathbb{P}\left[\text{error} > \epsilon\right] \leq \delta$$
Here error can be seen as the probability of making an error with our chosen function $h$.

Now, for axis parallel rectangles (in binary classification) the usual argument goes like this, let $R$ be the true rectangle and let $R'$ be the smallest rectangle containing the positive examples, clearly $R' \subseteq R$, we consider the four rectangular strips between $R'$ and $R$. Clearly if all of them have probability $\leq \epsilon/4$ then the probability of making an error is less than $\epsilon$, so we can assume that at least one have probability of making an error $\geq \epsilon/4$.

For such a strip the probability of correctly classifying all the $m$ training examples is at most $(1 - \epsilon/4)^m$, and thus taking aunion bound over all strips we get that the probability of correctly classifying everything is less than $4(1-\epsilon/4)^m \leq 4e^{-m/4}$, and with a bit of algebra this yields that the sample complexity is $m \geq (4/\epsilon)\ln(4/\delta)$.

Here is a pdf that explains in a bit more detail, with some pictures, I just had to condense the argument as much as I can to fit it in here.

My question is, why do we have to consider the four rectangular strips separatedly, why can't we just say that the probability of the region between $R'$ and $R$ has to be greater than $\epsilon$ (because otherwise we are done), and thus using the same argument we would arrive at the better bound $m \geq (1/\epsilon)\ln(1/\delta)$?

Sorry for the long question, and thanks in advance.


texts: Do there exist coding languages where the halting problem is solvable but not trivial

texts:
Does there exist a coding language where
1. It is always possible to determine whether a computer program will halt or run forever. And
2. The answer is not always yes. (or always no)
So languages that don't allow loops, even if finite are right out.


texts: Do there exist robust structures in Conway's Game of Life?  For instance, has anyone constructed a spaceship with a shield that absorbs all small oscillators and gliders it collides with?


texts: Are conditionals necessary in computation?

texts:
I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for instance) always seemed pretty clear and intuitive!

I mean, let's assume that I have a program which starts at

int main(int argc, char** argv) // in C

How am I supposed to know what is inside argv and argc? My old, intuitive answer: if statements. Using if statements, I would decide based on the input how to execute my program... I never considered any possibility other than having the input provided under this way, and I, as a programmer, could only mess with what is after the call to the program, with the input already defined. Hence I had no doubt that I needed to use conditionals.

I have ONLY 1 PROGRAM that needs to execute for ANY input and provide the right answers, hence I can't avoid if statements. It all seemed alright, for years now... until I started to think... Could there be other ways?

What if I had a different version of my program for each possible input? The operating system or the hardware could then call a different version according to the input. Then I thought – this would simply delegate the if statements to either the operating system or the hardware, respectively.

Then I even thought, what if the user had a different computer for each different input? I know this might seem really stupid, but I'm just trying to understand the "law" behind the need for conditionals in our physical world!

Also, in this last example it could be argued that the conditional would simply have to be executed in the user's brain (when he decides which computer to use based on the intended input).

Can someone give me some light in this subject? This is really troubling me :( maybe I've overthought things and now I'm paying the price for it...


texts: Looking for a book that derives and constructs a model checking application

texts:
I am teaching myself program verification and am currently learning proof assistants. I have the book Handbook of Practical Logic and Automated Reasoning which gives the proofs necessary for the understanding of such a system, but more importantly for me it also gives an implementation of the necessary algorithms as OCAML source.

I know that some of the tools listed in Wikipedia: Model Checking tools and YAHODA: Verifications Tools Database are open source, but I also prefer it when the theory, proofs, algorithms and source code are presented at the same time reinforcing each other, and in a progression building up to a final application.

Is there such a book for model checking?

EDIT

I may have found what I am looking for in Mathematical Logic for Computer Science with Prolog source. As I don't have the book, does anyone know if this book fits the requirement?


texts: How do I approach inductive design problems with no information or context given?

texts:
As a starting point for our course in Artificial Intelligence, we are being taught induction. We received a number of homework assignments where we have to show our inductive approach for a given problem.

An example of such a problem: "Sort an array of N numbers".

Reading through the course material and online sources I feel I have grasped the first concepts of induction. I have successfully proven some statements using induction, such as the number of steps for the Tower of Hanoi problem. However, I was able to prove it because I had some information beforehand, such as the number of steps required to move the tower in the form of a formula.

In the problems handed to us, we get a sentence like the one above and are asked: "Describe the inductive approach"

Should I select an arbitrary sorting algorithm, make my own assumptions and devise my own hypothesis and try to prove that? I just want to prove that the array is indeed sorted for any given number of N. What are some exemplary steps I could take in order to provide the inductive approach given that single sentence of "Sort an array of N elements"


texts: Proof that the language is not regular (Pumping Lemma)

texts:
I have to prove that the following language is not regular:

$$\{ x | x = 10^{2n} + 10^n + 1, n ≥ 1\}$$

I am trying to prove it using Pumping Lemma, however, when I expand the expression I have both addition and multiplication.

I assume that the pumping length is three ($p=3$) and I work on the following word of this language:

$$\{ 10^6 + 10^3 + 1\}$$
$$\{ 1000000 + 1000 +1\}$$


texts: Performance differences between Go-Back-N and Selective Repeat ARQ protocols?

texts:
This is what I know:

GBN weakness is the fact that when the window size is too large, the number of packets in the pipeline grows and one packet error causes the retransmition of many packets unnecessarily.
Selective Repeat solves this by acknowleding just the suspicious packets, which sightly makes performance better, but if a wrong window size is chosen, then the reciever doesn't know if a packet is being retransmitted or another packet is being sent by first time.

So, back to the question, what other important performance differences exists between these protocols?


texts: Artificial ant colony algorithm for graph

texts:
let's assume we have ant at node $1$ and she has $\{2,3,4\}$ vertices. How do I compute which one she choose? I mean if the formula $p_{ij}(k)$ is the probability of $k$-th ant at node $i$ choose $j$ node, for example, do I take $j=2$, compute the probability and if it satisfies $random(0,1)<p_{12}(k)$, the ant choose $j=2$, if not move to next vertex $j=3$ until the inequality is satisfied?
The next question is, can you recommend me the sources, where I can find conversion from this algorithm graph version to optimizing function version. Thank you.


texts: Does applying Hadamard gate is identical to applying a measurement gate that is perpendicular to the current qubit state?

texts:
Cause applying H (hadamard gate) on a state |0> will evolve to 50% |0> and 50% |1>, assuming we are meausring along the vertical axis (Z-axis).

While applying a measurement along a horizontal axis (e.g. X-axis), will force the state to "evolve" (destroied) and let it be perpendicular to the vertical axis. In another word the state now will have a 50% chance to be measured along the vertical axis to be |0> and 50% to be |1>.

I know that measuring a state will destroy the state, while H gate is unitary and conserves the state from destruction. But I really need to know how the physics behind the Quantum Computer gates.


texts: Time complexity of nested for loop function involving mod to filter out the execution

texts:
I have to find the time complexity of the following program:

function(int n)
{
    for(int i=0;i<n;i++)                   //O(n) times
        for(int j=i;j<i*i;j++)             //O(n^2) times
            if(j%i==0)
            {  //O(n) times
                for(int k=0;k<j;k++)       //O(n^2) times
                    printf("8");
            }
}

I analysed this function as follows:

i : O(n)  : 1        2        3          4             5
j :       : 1        2..3     3..8       4..15         5..24           (values taken by j)
    O(n^2): 1        2        6          12            20              (Number of times executed)
j%i==0    : 1        2        3,6        4,8,12        5,10,15,20      (Values for which the condition is true)
    O(n)  : 1        1        2          3             4
k         : 1        2        3,6        4,8,12        5,10,15,20      (Number of times printf is executed)
    Total : 1        2        9          24            50              (Total)

However I am unable to bring about any conclusions since I don't find any correlation between $i$ which is essentially $O(n)$ and Total of k (last line). In fact I don't understand if we should be looking at the time complexity in terms of number of times printf is executed since that will neglect $O(n^2)$ execution of j-for loop. The answer given was $O(n^5)$ which I presume is wrong but then whats correct?


texts: Tape Reduction when T is not time constructible

texts: Arora and Barak showed in their book that we can simulate a $O(T(n))$ time-bounded $k$-tape Turing machine with a $O(T(n)\log{T(n)})$ time-bounded $2$-tape oblivious Turing machine. But it seems that they assume that $T(n)$ is time constructible. What if $T(n)$ is not time constructible? Can we still do this simulation efficiently?


texts: Common method for solving satisfiability problems which lie in P

texts: I know from Schaefer's Dichotomy Theorem that only a few types of satisfiability problems are in P and any other problem is NP-complete.  However, all of the algorithms I know for them use specific techniques unique to that type of problem- e.g. unit propagation for Hornsat,  linear algebraic techniques mod 2 for XORSAT, and various other techniques for 2-sat.  Is there one general polytime algorithm which works for all of these problems in P?  Thanks.


texts: Finding largest farthest increasing pairs in array?

texts:
Is there a simple linear algorithm for finding in an array A two such elements that $A[i] > A[j]$ and $i - j$ is as large as possible? If one wants to actually return the indices, then linear memory usage seems impossible to avoid. If the only result needed is the value $i - j$, i.e. the distance, can we get away with less than linear memory?

Obviously, one can use constant memory if one is willing to loop over all pairs (i, j).


texts: Shortest path form node X to nodes A, B, C in graph

texts:
I have an unweighted consistent graph and some node X(the source) and some nodes A, B, C and more. I need to find the shortest paths: X->A, X->B, X->C and so on. Note that the number of goal nodes will not be very big.

If I were looking for only one path I would use BFS. But I'm quite sure how I can use BFS to find all paths to goal nodes.

Time is of the essence here so I wanted to use one BFS call to find all paths at once. I basically only need their costs. But I don't really know how to do that.

Does Dijkstra's algorithm do that?

The ultimate goal is that for every source node(because there are more of them) find the shortest paths to goal nodes. All sources want to find paths to the same goal nodes.
And based on every path cost I want to create a consistent bipartite graph.


texts:
Given the grammar $G=(\{S, L_x, R_x, W_x\}, \{a,b\}, P, S)$ derive the words $abaaba$ and $aabbaabb$.
$$
P=\left\{
\begin{align}S\phantom{{}_x R_y}    &\to  \epsilon \mid L_x R_x,\\
    L_x \phantom{R_y}      &\to  x \mid L_x y W_y,\\
    W_x y\phantom{{}_y}    &\to  y W_x,\\
    W_x R_y                &\to  R_y x,\\
    R_x \phantom{R_y}      &\to  x \\
\end{align}\right\}$$
with $x,y$ element of $\{a,b\}$. ($x$ and $y$ may or may not be equal)
Following the rules I always end up with words of the form $xx, xyxy, xyyxyy, \ldots$.
Am I allowed to replace each $y$ differently? Otherwise I don't see any way to get words like $abaaba$.


texts: Slowdown when accessing data at page boundaries?

texts:
Hi I have a program which accesses memory words that are located X bytes apart in virtual address space. For instance, for (int i=0;<some stop condition>;i+=X){array[i]=4;}.

I measure the execution time with a varying value of X. Interestingly, when X is the power of 2 and is about page size, e.g., X=1024,2048,4096,8192..., I get to huge performance slowdown. But on all other values of X, like 1023 and 1025, there is no slowdown. The performance results are attached in the figure below.

I test my program on several personal machines, all are running Linux with x86_64 on Intel CPU.

What could be the cause of this slowdown? We have tried row buffer in DRAM, L3 cache, etc. which do not seem make sense...


texts: Why do we need a separate notation for П-types?

texts:
Main
I am confused about the motivation behind the need for a separate notation for П-types, that you can find in type systems from λ2 on. The answer usually goes like so - think about how one can represent a signature of identity function - it can be λa:type.λx:a.x or λb:type.λx:b.x. The subtle part, they say, is that these two signatures not only not equal, they are not alpha-equivalent as type variables a and b are free variables inside their correspondent abstractions. So to overcome this pesky syntactic issue, we present П binder that plays nicely with alpha-conversion.
So the question: why is that? Why not just fix the notion of alpha-equivalence?
UPDATE z:
Oh, silly of me, λa:type.λx:a.x and λb:type.λx:b.x are alpha equivalent. But why a:type -> a -> a and b:type -> b -> b arent then.
UPDATE suc z:
Aha, interesting, I guess this is a perfect example of selective blindness =D
I am reading the book Type Theory and Formal Proof, and in the chapter about lambda2 author motivates the existence of П using exactly that kind of argumentation - one cant say that \t:*.\v:t.v : * -> t -> t because this makes two alpha-equivalent terms\t:*.\v:t.v and \g:*.\v:g.v have different types, as corresponding types are not alpha-equivalent, where types like t:* -> t -> t are in fact alpha-invariant. Mind the difference between t:* -> t -> t and * -> t -> t. But, doesn't it make this argument a bit trivial, and is it even something meaningful to talk about type a -> b where a and b are unbound by any quantifiers variables.
Andrej Bauer pointed out in the comments that П is indeed resembles a lambda abstraction with a few additional bells and whistles.
All in all, I am done with that one, thank you guys.


texts: The cost of memory allocation on the (tacitly assumed) Word RAM machine?

texts:
Consider a particular algorithm that solves the binary search problem (or similar stuff) by performing $\sqrt{n}$ simple operations on numbers of
$\log(n)$ bits. Suppose this algorithm works on a Word Ram machine with
word size $w=\log(n)$. What happens if the algorithm uses a memory area
with $n$ numbers that are not initialized (like when using malloc in C)
because only a few of them are really touched/used?

Some sources (example here) say that the memory of a Word Ram machine is just there, and there is  no allocation, i.e., we simply have $n=2^w$ memory cells available since the very beginning
. Other sources give different formalizations, but still the memory
is just there. In this sense, the algorithm has complexity $O\left(\sqrt{n}\right)$.

Other sources (example here) consider the cost of performing memory allocations, so that
allocating $O(k)$ cells takes $O(k)$. In this sense, the algorithm has complexity $O(n)$ in the Word RAM model.

Even reference books (e.g., the Introduction to Algorithms by Cormen et al.) do
not provide a very formal description of the Word RAM machine. In my sense, they do not
seem to give so much attention (i.e., there is about one page, Section 2.2) to
specify very clearly the machine on which all complexities of their algorithms
are calculated. So I could not find a response to my question. The Word RAM is not as clearly and as uniformly specified as the Turing machine.

Where can I find the "true" Word RAM machine ?


texts: reduce k-colorable to 3-colorable graph problem

texts: given a graph G = (V, E) of n vertices, decide whether G is k-colorable. if I were to have an oracle that solves for 3 color, how do I use it to solve the k color graph problem?


texts:
I try to find out what is the time complexity of this program:

for (int i =0; i < n; i++)
{
    for (int j = i+1; j < n; j++)
    {
         //Do something O(1)
    }
}

I tried to find any explanation, As I see, it something like Arithmetic progression sum (n(n-1)/2).

Is it? or it's just O(n^2)


texts:
The problem: we have a list of terms $[t_1, ..., t_n]$ , and a term $t$, and we want to find which of the terms in the list can be unified with $t$. Obviously we can iterate through the list and check one-by-one whether $t_i$ unifies with $t$, but what better (i.e. faster) approaches exist? Assume we can store the list however we want.
I'm particularly interested in approaches that extend well to unification modulo a theory, but assume the empty theory to start.
This must be a basic question but I can't find good references, so any references are much appreciated.


texts: Proving big-theta complexity with constants in $f(n)$

texts:
I am working through a problem in which I have to prove that a particular $f(n) = \Theta(g(n))$. I know that for this to be true there need to exist positive constants $c_1$, $c_2$, and $n_0$ such that for all $n \geq n_0$, $c_1g(n)\leq f(n) \leq c_2g(n)$. Simply put, the goal is to pick values for the constants such that the above inequality holds. As a side note, $n$ must be a positive integer, and $c_1$ and $c_2$ can be any positive real number, correct? I haven't been able to find clarity over that.
Now, suppose the $f(n)$ has some undefined constants $a$ and $b$, such as $f(n) = n^a + n^b$. Note that this is a throwaway example. My question is this: do we need to define $c_1$ and $c_2$ in terms of the constants $a$ and $b$, or do we need to pick an actual numerical value for $c_1$ and $c_2$, and by extension, values for $a$ and $b$? The former is much more difficult to do.
I apologize in advance for the poor formatting (I simply placed any math in italics, which I know is not correct). This is my first ever post on CS stack exchange. Also, I would like to state that there was a serious attempt at researching into the above, but I couldn't find examples of how to prove $f(n) = \Theta(g(n))$ when $f(n)$ has other constants. If anyone has resources related to this, I would be very grateful.
I would appreciate any and all help. Looking forward to potential responses.


texts: Is determining if a Turing machine runs in constant time decidable if one assumes it halts?

texts:
As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts?

The decision problem, more formally:

Given a Turing machine $M$ where it is assumed it halts on all inputs, determine if it runs in $O(1)$ time.

Is this decidable?


texts: $1+\epsilon$ approximation for inapproximable problems

texts:
I am currently confused by the following situation:

1) The metric $k$-center problem is inapproximable in polynomial time within $2-\epsilon$ unless $P=NP$.
2) The metric $k$-center problem can approximated within $1+\epsilon$ in time $O(k^{O(k/ \epsilon)})$

Did I just win a million dollars or why isn't this a contradiction?
I guess my confusion comes from the unprecise statement  "in polynomial time" in 1).


texts:
Background: Recently, I obtained the following equivalent problem to SAT. We are given as input a CNF formula with $n$ variables and $m$ clauses. Suppose we have an $n$-dimensional hyper-cube centered at the origin. We perform the following cut-and-color operation $m$ times, each time for a clause.

Let’s say there are $k$ literals in this clause. For the $i$th literal with variable numbered $x$ and sign $s$, we cut the hyper-cube or what is remaining with the hyper-plane perpendicular to $x$th axis and keep the $s$-signed half. After $k$ times cutting, color the remaining part red.

If, after all clauses have been processed this way, the entire hyper-cube is red, announce UNSAT. Otherwise announce SAT.

This is the problem. Basically an uncolored part corresponds to an assignment whose reverse is satisfiable, because no clause covers this assignment or, in other words, this assignment does not contain any clause when both assignments and clauses are viewed as sets.

Phrased this way, SAT is really a geometric representation problem, and the key is to keep track of colored parts with only polynomial-sized storage.

Question: What is known about high-dimensional geometry of a hyper-cube, especially related to this problem? My current difficulty is with visualization.

Difficult example: Consider the following simple CNF formula:
$$(x_1\lor x_2)\land(x_3\lor x_4)\land\cdots\land(x_{2k-1}\lor x_{2k}),$$
or in DIMACS format

1 2
3 4
...
2k-1 2k

where $k>0$. The challenge is to represent the colored parts by (preferably polynomially many) non-overlapping clauses only. Below is the best I can do:

$k=1$:

1 2

$k=2$:

1 2
-1 3 4
1 -2 3 4

$k=3$:

1 2
-1 3 4
1 -2 3 4
-1 -3 5 6
-1 3 -4 5 6
1 -2 -3 5 6
1 -2 3 -4 5 6

$k=4$:

1 2
-1 3 4
1 -2 3 4
-1 -3 5 6
-1 3 -4 5 6
1 -2 -3 5 6
1 -2 3 -4 5 6
-1 -3 -5 7 8
-1 -3 5 -6 7 8
-1 3 -4 -5 7 8
-1 3 -4 5 -6 7 8
1 -2 -3 -5 7 8
1 -2 -3 5 -6 7 8
1 -2 3 -4 -5 7 8
1 -2 3 -4 5 -6 7 8

As you can see, it's growing exponentially.

Partial question: Do you have a way to do this example (not the general problem) using only polynomially many clauses? This is the difficulty I can't handle right now. It's easy to see that the interactions among the original clauses grow exponentially with $k$. So if you can prove that this example is impossible to do, then this non-overlapping-clauses approach won't work and we need to find something else.

Code: I posted my code here. My approach was implemented but it’s still exponential without the partial problem above solved. You can observe that.

One potential weakness is that any algorithm implementing my idea can actually count the number of satisfying assignments, solving a #P-complete problem. Not only that, it remembers in memory exactly which assignments are not satisfying (one simple way to do this is to just remember the initial clauses) and it can enumerate these without much overhead, because the final clauses are non-overlapping. Is that something enough to prove my idea is always exponential-time?


texts: If R is a regular language, is $R^3= R \circ R \circ R$ also regular?

texts:
My understanding of a regular language is that for a language to be formal, it must be able to be represented by a DFA or NFA. To prove a language is not regular you can use the pumping lemma to get a contradiction.

I am trying to figure out whether $R^3$ or $R \circ R \circ R$ is regular if R is also regular.

My understanding of the definition of $R \circ R$ is that it is kind of a transitive mapping of R?

And I think if $R \circ R$ is regular then $R \circ R \circ R$ is also regular, so I need to prove $R \circ R$ is regular which really means that I am trying to prove that regular languages are transitive?

I am not sure how I would go about doing this as I am a little confused how regular languages and transitivity relate - as I have only worked with relations for transitivity.


texts: Algorithm to get the number of iterations needed, if possible, to get an specific 2 element array

texts:
I am fairly new to algorithms and I am dealing with a problem I cannot fully translate into mathematical language.
So, I am given the array [1,1] and I can only perform one sum between their numbers per step, ie you can only pick between:
[x(s+1), y(s+1)]=[x(s)+y(s),y(s)]

or
[x(s+1),y(s+1)]=[x(s), x(s)+y(s)]

but not both at the same time
Thus,
0: [1,1]
1: [2,1],                      [1,2]
2: [3,1],        [2,3],        [3,2],        [1,3]
3: [4,1], [3,4], [5,3], [2,5], [5,2], [3,5], [4,3], [1,4]
...and so on.

The goal is to know how many steps are needed in order to get a given [x,y] array.
This far, I know that
if (min(x,y)==1) --> steps =max(x,y)-1

if (x%2 ==0 and y%2==0) (both even) --> steps= not possible
if (max(x,y)%min(x,y) == 0) (one is multiple of the other or x,y are the same ) --> steps= not possible
if (x%3 ==0 and y%3==0) (both divisble by 3) --> steps= not possible

Also I plotted for each pair (x,y) how many steps are needed, and I can see a pattern happening for every multiple of x or y, but I can't write it as a mathematical function when x or y is >= 5.
Any guidance will be much appreciated.


texts:
I am having problem with solving the following recurrence relation. $A$ is a set, there are at most $k+1$ of this set and $|A|$ is at most $n/2$.

$T(n) = O(n log k) + \sum_A T(|A|)$

I guess it can't be solved by the techniques presented in CLRS book (like master theorem), I also tried to solve it using induction on $n$ (I mean the Computational geometry approach) but I failed.

thanks.


texts: Convert for loop into math sigma notation

texts:
Have some code (written in C), need the equivalent notation for mathematics.
Is it possible using if-statements and sigma notation for this, and if so, how?

int res = 0;
for (int i=0; i < (N/2)+1; i=i+1)
  if (N % pow(2, i) == 0) res = i;

I have gotten as far as:

$$ \sum _{i=0}^{{N\over2}+1}\:(N \mod 2^i )$$ (missing the == 0 and res = i)

Ideas or a solution are welcome.


texts: why is the NL solution PATH negated unsufficient to prove unreachability

texts:
I'm currently reading into complexity classes and one think will not fit into my head.
We are investigating NLogSpace with the Path/reachability problem.
There is a nondeterministic LogSpace algorithm which can solve reachability, but its inversion does not prove nonreachability because "it could miss a path". How is it possible to miss a path? Wouldn't it imply that the reachability test might doesn't work?
Can somebody please explain it to me? Thank you.


texts: Generating a random minimum spanning tree

texts:
I am tring to find the simplest method of generating a random minimum spanning tree.

My intention is to randomly generate a Level in a game where there are n amount of fixed sized rooms existing on a grid which all connect together in a random way.

One method I have come across is to generate random points on a grid and run a Randomized incremental Delaunay triangulation algorithm (Explained quite nicely here) on it with the weights of the nodes being determined by their distances from eachother. Couple this with Kruskal's algorithm and then I will have my minimum spanning tree.

I'm relatively new to this field of Maths and was having trouble creating the Delaunay algorithm (and even more trouble understanding some libraries out there) and thought perhaps there is a simpler method to get the same result.

One method that came to mind was to create a fully connected graph of random points (much simpler for me to do) and then run Kruskal's algorithm on that, However my intuition tells me that this would not be so efficient even though I am only talking about a maximum of 10 or 15 nodes for my intended use.

Are there any other methods I should consider to generate such a graph?
I've come across the Prüfer sequence which seems incredibley simple, however with my current understanding of it I do not see how I can take into account the positions of the Rooms/Nodes on the grid or perhaps even chose where to place the nodes on the grid.


texts: Proof of sparsification lemma: What exactly does the $\pi$ operator do?

texts:
In their proof of the sparsification lemma, Impagliazzo et. al describe the following operator $\pi$:

For a familiy of sets $\mathcal{F}$, let $\pi(\mathcal{F}) \subseteq \mathcal{F}$ be the family of all sets $S$ in $\mathcal{F}$, such that no other set $S'$ in $\mathcal{F}$ is a proper subset of $S$.

I am trying to understand what this operator does. So far, I thought that it could be calculated by the following algorithm:

$$ \text{While}~\exists S_i, S_j \in \mathcal{F}: S_i \subset S_j  \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S_i$$

By the rest of the proof seems to indicate that actually, one has to remove the superset:
$$ \text{While}~\exists S_i, S_j \in \mathcal{F}: S_i \subset S_j  \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S_j$$

Which leads me to believe that I did not fully understand the description of the operator. What would be an algorithm to calculate that $\pi(F)$?


texts:
I just wonder if solving largely monotone SAT formulas (meaning most clauses do not contain negated literals, but some do) is in any way easier than general SAT formulas? In other words, are there heuristics specially designed for solving such formulas that are not applicable to more general SAT problems? I tried but didn't find any research in this particular direction.
Of course, what is considered "most" is up to interpretation, but let's say >95% of the causes are monotone.


texts: What do the commas separating atomic events in a Relational Calculus formula means?

texts: For instance, take the example of this book here on page 30. About the formula $$ Q(x,x') = R(x), S(x,y), S(x',y), R(x') $$ described there, what do the commas mean? Is it the same as an "and" operation? Or a natural join maybe?


texts: What is complexity class for #XOR-2-SAT?

texts:
I know that given problem is in $\mathsf{FP}$: if given formula is satisfiable, then it is only needed to find out how many connected components equality (undirected) graph has. In fact problem is to count the amount of connected components.
However, is it possible to solve it using only log space? Is then the given problem is $\mathsf{FL}$-complete? Or, maybe, this problem is complete somewhere in $\mathsf{AC}$?


texts:
The following is an excerpt from the book "Introduction to the theory of Computation" by Michael Sipser, 2nd edition.

As per the book, this Turing machine accepts the language L = { w#w | w ∈{0, 1}*}. I ran this machine for few strings and it's working properly.
My doubt is, I think there is no need of keeping a transition on the state q6 for 0 and 1.
I mean, if the transition on state q6 was x -> L in place of 0,1,x->L  then also this machine will work properly. Please confirm the same.


texts: What can't you do without Turing-completeness?

texts:
I suppose that, since a Turing-complete language can simulate a Turing-machine, a non-Turing-complete language can't, but most programs do not have the simulation of a Turing machine as their purpose.

I also know that some non-Turing-complete languages can't use unbounded loops, and I suppose that making unbounded loops forbidden is enough to make a language non-Turing-complete. But it doesn't mean that it's the only way.

So, in general, what common properties or abilities of general purpose languages are only possible with a Turing-complete language?

If I decide to design a non-Turing-complete language, what common purpose functions won't I be able to implement with it?
Which common source code structures should I forbid?


texts:
Church-Turing thesis : Every effectively calculable function is a TM-computable function.

But, hypercomputation models are strictly more powerful than TM and can solve TM-uncomputable problems on the paper.

Does this imply that, for one who believes in the Church-Turing thesis, there is only two options :

There is two distincts worlds : The effective one (where Church-Turing thesis applies) and the paper
one (where Church-Turing thesis doesn't apply necessarily). That is the physical world and the ideas world of the classical
dualism theory.
All the hypercomputation models are inconsistent. Using an hyper-TM in a reasoning is the same than, for instance, using an integer both even and odd in a reasoning, this can lead to false conclusions.

?


texts: Finding paths with minimum intersections

texts:
Given a graph and a set of origin-destination $\langle o_i,d_i\rangle$ pairs. The goal is computing a set of paths such that every pair has a path and number of common vertices between paths is minimized.

If you have any relevant references to share I'd like to read them.


texts: Whether the algorithm is polynomial or not with input size which is not polynomial

texts:
A problem may require memory space which is not polynomial with respect to the input size but may still have polynomial run time.

Is this true or false? and why? any idea?


texts: How do computers *really* work? (at the most basic level)

texts:
While learning about computers I will read about RAM and Storage and the CPU, and while these explain the architecture of a computer and how parts of a computer work together, I still don't understand the fundamental workings of a computer program.
Let me take an example.
I'm on the web on a mac right now. When I push two fingers away from me on the trackpad, I understand that the trackpad is made up of a capacitive touch screen that, when your finger is placed on it, draws current and the trackpad detects that and converts it into data that explains the movement of my fingers up the screen.
However, when you have this data in binary form, or machine code, it goes through logic gates and other things to make it in scroll down on the page. But what is actually happening here? How would the computer have physical things that operate differently based on the input? What operations are carried out on the machine code that says "if data looks like 01001010 10101010... send instruction 10010010... to CPU that tells computer to scroll down". Surely if you had some logic gates that turned input x into output y, yes they would give different outputs based on the input, but unless you somehow redirected the current to the right set of logic gates every time the action was carried out, how would it go to the correct one? To me this step is still magic. Especially with computers now that have no moving parts it seems even more alien.
Could someone explain this to me?


texts: Database Access Cost Estimate - Linear Search over non-key attribute

texts:
How does one estimate the access cost for the below query given that the data is sorted according to a non-key attribute, that the data is not uniformly distributed across all possible values of said attribute and that we must use a linear scan?
SELECT * FROM EMPLOYEE WHERE DNO = X

Context
Given the following:

Total #tuples = 525 employees
Block size = 500 bytes
Tuple size = 50 bytes
#DNO = 20, {1,...,20}, and is not a key attribute

Assuming Uniform
By assuming that the data was uniformly distributed, I've calculated the cost the following way:
The blocking factor will be 10, hence the number of block files will be 53. However, we have to assume that the data is uniformly distributed and we cannot have partial blocks. Therefore each DNO will require 3 blocks. So accessing all records for a given DNO will have a cost of 3, and a probability of accessing a random DNO, $x$ is just 1/20. Therefore, the total access cost is given by
$$ E(C) = \sum_{x=1}^{20} \frac{1}{20} 3x $$
Assuming the below distribution
Here my thoughts are to split the data into 3 main clusters and perform a similar calculation to above, but I'm confused about a couple of things. For example, in cluster 1, each bucket would have probability 20/525 when looking at the whole dataset, but if looking at the cluster only, then each element would of course now have a probability of 20/200. The problem is that when calculating the number of tuples per record I set the total number of tuples to 200 which gives me the required 2 records per tuple for the whole cluster, but would it then be appropriate to use the first probability? If not, would it then be appropriate to use the second probability when adding the costs of the first cluster to the costs of the second cluster? i.e.
$$ E(C_1) = \sum_{x=1}^{20} \frac{20}{525} 2x $$
or
$$ E(C_1) = \sum_{x=1}^{10} \frac{1}{10} 2x $$
And how would you factor $C_1$ into $C_2$'s calculation?


texts:
For example the nodes in this graph should be separated into two groups (A,B,C) and (D,E,F,G).

By looking at a graph of citations, assuming that most citations are papers from the same field, can we separate papers into fields?


texts:
I'm working through Samuel Mimram's book Program = Proof. In the first chapter, he discusses recursive types in OCaml, and inductive types. An exercise he provides on the topic has me a little bit confused. In the exercise, he asks the reader to define the function induced by the inductively defined type of lists, and then show that it has a greatest fixpoint, distinct from the smallest fixpoint, and provide a concrete description of it.
I believe I'm able to define the function he mentions. If we had the type of lists of integers:
type list =
    | Nil
    | Cons of int * list

Then our induced function $F : \mathcal{P}(\mathcal{U}) \rightarrow \mathcal{P}(\mathcal{U})$ (where $\mathcal{P}(\mathcal{U})$ is the powerset of all possible values of our type list) looks like:
$$
F(X) = \{ \mathrm{Cons}(n, l) \ | \ n \in \mathbb{Z},\ l \in X \} \cup \{ \mathrm{Nil} \}
$$
In the book, we learn that the least fixpoint of such a function defines the set of values inhabiting our type. That makes sense. He also goes through a proof of the Knaster-Tarski theorem to demonstrate that such a least fixpoint will exist, due to the fact that $\langle \mathcal{P}(\mathcal{U}), \subseteq\rangle$ is a semilattice and $F$ is monotonic.
I can't find any intuition for reasoning about the greatest fixpoint of this function. My naïve assumption is simply that the greatest fixpoint would be the set of all infinite lists, but I think I'm missing a really crucial idea here, and I can't tie it down in my understanding. If anybody could provide some information or input on this, I would really appreciate it!


texts: I'm interestd in string-matching, I would like to know recent open problems in string-matching in field of bioinformatics.


texts: Space optimised versions of Coin Change and Knapsack Problems in Dynamic Programming

texts:
I have recently been focussing on DP formulation and space optimization in dynamic programming of some problems.
I have gone through the standard questions such as 0-1 Knapsack and Coin Change problems.

In the space optimization part, I haven't understood in which order should I fill the table to get the desired result. For instance, In the above 0-1 Knapsack Problem, which asks about max possible sum of values for a weight of at most w.

vector<int> dp(w + 1); // dp[j] max value that can be obtained with weight exactly j
  for (int i = 0; i < n; i++) {
    for (int j = w; j >= weight[i]; j--) // iterating from right to left here
      dp[j] = max(dp[j], val[i] + dp[j - weight[i]]);
  }

In the above snippet why the ordering is important? I am confused because for the space-optimized version of coin change problem mentioned above we iterate from left to right to get total no. of ways to get change, it goes as @qqibros answer shown here

 vector<int>dp(x+1); // dp[i]- no of ways to get coins with value exactly i
for(int i=0;i<n;i++){
  for(int j=a[i];j<=x;j++){ // iterating from left to right here
    dp[j]+=dp[j-a[i]];
  }
  cout<<dp[x]<<endl;

But if I change the above coin change problem adding the constraint that every coin can only be used exactly once, I should iterate from right to left to get the required answer.
For example,N = 4 and S = {1,2,3}, only one solution {1,3} so the output should be 1. And For N = 10 and S = {2, 5, 3, 6}, still only one solution {2, 3, 5} and the output is 1.
Just changing the line from for(int j=a[i];j<=x;j++) to for(int j=x;j>=0;j--) gives the answer.

I am not able to visualize or interpret correctly how ordering changes the value as in both cases the value only depends on previously stored values.


texts: How are hash table's values stored physically in memory?

texts:
Question:
How are hash table's values stored in memory such that space if efficiently used and values don't have to be relocated often?
My current understanding (could be wrong):
Let's say I have 3 objects stored in a hash table. Their hash functions generate these values:

0
10
20

I would presume that the pointers of these objects would not be stored at the following memory addresses because there would be huge gaps between them:

startOfHashTable + 0
startOfHashTable + 10
startOfHashTable + 20

The Wikipedia article on hash tables says that the "index" is computed as such:
hash = hashfunc(key)
index = hash % array_size

So in my example, the indices would be:

0 % 3 = 0
10 % 3 = 1
20 % 3 = 2

This gets rid of the huge gaps that I mentioned before. Even with this modulo scheme, there's problems when you add more objects to the hash table. If I add a fourth object to the hash table, I would need to apply % 4 to get the index. Wouldn't that invalidate all the % 3's that I did in the past? Would all those previous % 3's need to be relocated to the % 4 locations?


texts: Number of binary trees with given height

texts:
I was wondering how many binary trees we have with height of $h$ with $n$ nodes(another question is how many binary trees we have with height $ \lfloor{lg (n)}\rfloor$).

Edit: I forgot to add the number of nodes.