texts: Use Rice's theorem to show that the language of optimisable Turing machines is undecidable

texts:
I have an assignment to do and I'm quite stuck with the following question :

Use Rice's theorem to show that
$ \qquad L' = \{ \langle M \rangle \mid \; (\exists \text{ TM } M') \; [ L(M') = L(M) \text{ and } M' \text{ has less than 29 states} ] \}$
is undecidable.

I have absolutely no idea how to proceed.
Would someone be kind enough to, at least, give me some clues?
EDIT
First, I wrote the question wrong. It is now '$M'$ has less than 29 states' (not 'steps')."
Here's what I'm thinking after more reading and consulting other students at school.
Rice's theorem :

$L = \{ \langle M \rangle \mid L(M) \text{ has some property } P \}$ where :

$P$ is non-trivial, i.e. there exists at least one machine $M_1$ such that $\langle M_1 \rangle \in L$, and at least one machine $M_2$ such that $\langle M_2 \rangle \not \in L$.

$P$ is indeed a property of the language of TMs, i.e. whenever $L(M_a) = L(M_b)$, we have $\langle M_a \rangle \in L$ if and only if $\langle M_b \rangle \in L$.

Then, $L$ is undecidable.

So here, the property is "$M'$ has less than 29 states".
We can show that this property is non-trivial.
Let's take the language "abcdefghijklmnopqrstuvwxyz0123456789" (only one string is accepted). We can build a TM $M$ this way :
-> Enter in state $q_0$
-> In $q_0$ : if you read "a", proceed to $q_a$, otherwise go to $q_{reject}$ and halt.
-> In $q_a$ : if you read "b", proceed to $q_{ab}$, otherwise go to $q_{reject}$ and halt.
$\vdots$
-> In $q_{abcdefghijklmnopqrstuvwxyz012345678}$ : if you read "9" go to $q_{accept}$, otherwise go to $q_{reject}$ and halt.
So here we got 3 "basic states" : $q_0$, $q_{reject}$ and $q_{accept}$ and we have $|abcdefghijklmnopqrstuvwxyz0123456789| - 1$ states (there is no $q_{abcdefghijklmnopqrstuvwxyz0123456789}$ because when we read "9" at the end, we go to $q_{accept}$). So that's 26 + 10 - 1 = 35 states. We have a total of 35 + 3 = 38 states.
Unless I am wrong, there can't be a TM $M'$ that can test wether a string $w$ belongs to that language without having at least 38 states !
So the property "$M'$ has less than 29 steps" is non-trivial as there is at least one TM that respects it, and at least one that does not.
Now, $P$ is indeed a property of the language of TMs, because any two machines $M_1$ and $M_2$ such that $L(M_1) = L(M_2)$ implies :
$\langle M_1 \rangle  \in L' \Leftrightarrow L(M_1) = L(M_2) \Leftrightarrow \langle M_2 \rangle \in L'$.
(I know there is at least one missing clause in there, but I can't figure how to write it, it's got something to do with that "$M'$ has less than 29 steps")
So, according to Rice's theorem, $L'$ is undecidable.


texts:
There seems to be various implementations of algorithms that find the connected components of a graph.

I have not found, however, an algorithm or implementation for finding which of the connected components are also complete. Does anybody know of one?

Thank you!


texts: TM for $0^{5^n}$. Describing a turing machine that decides the language consisting of all strings of zeroes whose length is a power of 5

texts:
I am trying to describe a TM that decides the language $A=\{0^{5^n} \mid n\ge0\}$.
I know how to do this for $0^{2^n}$, marking off every other 0 in each pass. In my case would it work marking off every fifth 0 in each pass? It would reject if there are an even number of 0s. Every pass reduces the number of 0's by a fifth until there are no more 0s.


texts: It looks like most of today's algorithm analysis is done in models with constant-time random access, such as the word RAM model. I don't know much about physics but from popular sources I've heard that there's supposed to be a limit on information storage per volume and on information travel speed, so RAMs don't seem to be physically realizable. Modern computers have all these cache levels which I'd say makes them not very RAM-like. So why should theoretical algorithms be set in RAM?


texts: Checking the validity of a pyramid of dominoes

texts:
I came across this question in a coding interview and couldn't figure out a good solution.

You are given 6 dominoes. A domino has 2 halves each with a number of spots. You are building a 3-level pyramid of dominoes. The bottom level has 3 dominoes, the middle level has 2, and the top has 1.

The arrangement is such that each level is positioned over the center of the level below it. Here is a visual:

         [ 3 | 4 ]
    [ 2 | 3 ] [ 4 | 5 ]
[ 1 | 2 ][ 3 | 4 ][ 5 | 6 ]

The pyramid must be set up such that the number of spots on each domino half should be the same as the number on the half beneath it. This doesn't apply to neighboring dominoes on the same level.

Is it possible to build a pyramid from 6 dominoes in the arrangement described above? Dominoes can be freely arranged and rotated.

Write a function that takes an array of 12 ints (such that arr[0], arr[1] are the first domino, arr[2], arr[3] are the second domino, etc.) and return "YES" or "NO" if it is possible or not to create a pyramid with the given 6 dominoes.

Thank you.


texts:
I'm currently writing my bachelor thesis and explain some algorithms where the XOR-operation is used.

Can I use "XORing" or "XORed" in my thesis or is this too informal?

For example: "xoring the plaintext with the stream cipher results in the cypher text" and "the plaintext is XORed with the stream cipher..."

Also what would be the correct way to write it? Completly lowercase or with an uppercase XOR?

Hope this is the right community to ask this question.


texts: Find X contiguous segments in a range of integers

texts:
I've been struggling with the following problem: how do I find all possible sub-ranges in a range of integers where each segment is at least length 1, and I specify the total number of segments? A couple examples:

segments=2, range=(0,5)
> [0,1],[2,5]
> [0,2],[3,5]
> [0,3],[4,5]

segments=3, range=(0,8)
> [0,1],[2,3],[4,8]
> [0,1],[2,4],[5,8]
> [0,1],[2,5],[6,8]
> [0,1],[2,6],[7,8]
> [0,2],[3,4],[5,8]
> [0,2],[3,5],[6,8]
> [0,2],[3,6],[7,8]
> [0,3],[4,5],[6,8]
> [0,3],[4,6],[7,8]
> [0,4],[5,6],[7,8]

This feels like a recursion problem because I need to iterate over a varible number of for-loops, but I don't see how to make it work.


texts: What is the the relation between the amount of data transmitted and line distance?

texts: I am wondering what is the relation between line distance and the amount of data transmitted on that line. I know only the basic of computer science. Let's say I want to calculate the time it takes for 100 GB to transfer over a line with the speed of 100MBps. If I just divide them, I will get 1000 seconds but in my online class, the lecturer said the time depends on the line distance. Since it is an introductory course, he doesn't explain anymore. So my question is, how is it relevant and why? I know the simple answer should be the resistance of the line increase as it got longer but does the resistance affect on the needed time significantly? How could I calculate the needed time with distance?


texts: Find vectors with elements of finite fields that sum up to given value

texts:
Given a universe $U$ consisting of k sets of vectors with each vector $\vec{v} \in {\mathbb{F}_{p^m}}^n $. Given also another vector $\vec{c} \in {\mathbb{F}_{p^m}}^n$.
Now decide if there is a set $X$ with $|X| = |U|$ and $X_i \in U_i, i = 1,2,...,k$ such that $\sum\limits_i X_i = \vec{c}$. If there is, output this set.

In other words, I want to find a combination of one element out of each set that sums up to the given vector, given that the vectors' entries can only be the results of modulo operation with a given integer. I hope the problem becomes clear.

I want to find an efficient algorithm to solve this problem. It seems to me that it is NP-complete, but I find no other NP-complete problem that I can reduce. If there is one, existing algorithm (if any) to that other problem could be used for this problem.
I looked at integer programming, but I did not find anything with respect to finite fields.

Any ideas?


texts:
Let A and B be two integers, where their size is constrained to 2 bits in binary. There exists a function F, which outputs integers of the same size, where F(A) = F(B) = Y. For example, A = 01, B = 10, and Y = 11.

There exist some possible functions, such as G(X) = X xor 10. Another could be H(X) = X + 01 (ignoring overflow). However, in terms of their results, many of these would essentially be the same function, mapping the same inputs to the same outputs.

What is the "common denominator", so to speak, that would allow seeing all functions as the same?

The purpose of this is to be able to "increment" a function. In the first example, suppose I do not know what F is, and I want to write a program to find it. I know that F(A)=F(B), so I could write a loop to try all the possible functions by "incrementing" the function after each iteration, until the function that has F(A)=F(B) is found. Ultimately this will be used on larger sized, and possibly differently sized, inputs and outputs


texts: Polynomially related lengths under two different encodings

texts: I'm reading through "Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20 and I came across this concept of a function that is polynomially related to input lengths obtained using some encoding scheme. Let $$Len:D_{\Pi}\rightarrow \mathbb Z^+$$ be a function that maps instances $\in D_{\Pi}$ (the set of instances of decision problem $\Pi$) to positive integers (lengths). Let $x$ be the string obtained from $I\in D_{\Pi}$ under some encoding $e$. If there exist polynomials $p$ and $p'$ such that $$Len(I) \le p(|x|)$$ and $$|x| \le p'(Len(I)),$$ We say that $Len$ is polynomially related to the input lengths obtained by the encoding $e$. I cannot digest that; my understanding is that two encodings are polynomially related if converting from one another requires a polynomial amount of time. Can anybody clarify things a bit?


texts:
In its section Properties of binary trees Wikipedia states:

  The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is (n+1), where only 1 node exists in bottom-most level to the far left.

I wonder about the precise statement used here. In my opinion every binary tree with $n$ nodes has exactly $n+1$ nil links (or missing children). A proof by induction is easy. (In fact that is equivalent to the statement some lines above: "a perfect binary tree with $\ell$ leaves has $n=2\ell-1$ nodes".)

Question: what am I missing here? Has Wikipedia different assumptions on binary trees?

As an illustration, a non-complete binary tree with 12 nodes and 13 nil-pointers, marked as square nodes. It can also been seen as a perfect binary tree with 25 nodes, the squares indicating leafs.


texts:
I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only iteration".

There was even a highly upvoted thread with a highly upvoted answer that said yes it's possible.

Now I'm not saying they're wrong. It's just that that answer counters my meagre knowledge and understanding about computing.

I believe every iterative function can be expressed as recursion, and wikipedia has a statement to that effect. However, I doubt the converse is true. For one, I doubt non-primitive recursive functions can be expressed iteratively.

I also doubt hyper-operations can be expressed iteratively.

In his answer(which I don't understand by the way) to my question @YuvalFIlmus said that it's not possible to convert any sequence of mathematical operations into a sequence of additions.

If YF's answer is indeed correct (I  guess it is, but his reasoning was above my head) then doesn't this mean that not every recursion can be converted into iteration? Because if it was possible to convert every recursion into iteration, I'd be able to express all operations as a sequence of additions.

My question is this:

  Can every recursion be converted to iteration and why?

Please give an answer a bright highschooler or a first year undergrad will understand. Thank you.

P.S I don't know what primitive recursive is (I do know about the Ackermann function, and that it isn't primitive recursive, but is still computable. ALl my knowledge on it comes from the Wikipedia page on the Ackermann function.)

P.P.S: If the answer is yes, could you for example write an iterative version of a non-primitive-recursive function. E.g Ackermann in the answer. It'll help me understand.


texts: What algorithm can I use for a rule based system?

texts:
I'm doing research for a system that is based on rules. The goal of the system is to fire when some of the rules are true.

Explanation (requirements/working of the algorithm):
The algorithm will run in the background of an app. There will be a lot of data available about the user. The algorithm will apply the defined Business Rules to the data. When an X amount of the rules result in true, the algorithm should fire. The goal of the algorithm is to fire when the user shows any possible problems (based on data / the business rules that result in true).

Examples of Business Rules:

  IF a user is in the app between 2-5AM more than 5 times in 2 weeks THEN the user is not sleeping at the correct times.
  IF a user moved house twice THEN a user moves house a lot

The Business Rules are in the If condition(s) then action format.
The condition can be of any type. It would be really nice if it will be "easy" to add new forms of conditions in the future and the algorithm can handle such changes.

I'm looking for an algorithm that can be of use for the goal described above. Preferably without the use of Machine Learning. So I'm looking for an up-to-date/newer version of an Expert System.

When I did research, almost every time I came back to an Expert System. I think it perfectly fits my requirements. However I can't find anything recent on Expert Systems. It looks like it is outdated, as mentioned in this post, four years ago.

I saw something like an Recommendation System in this post. Still I don't think this will solve my problem because it focuses on recommendations...

Does anyone else have ideas for an algorithm?

EDIT: Tried to add useful information


texts: Minimum number of states in dfa accepting binary number with decimal equivalent divisible by $n$

texts:
I was aware of the fact that, if DFA needs to accept binary string with its decimal equivalent divisible by $n$, then it can have minimum $n$ states.

However recently came across following text:

  If $n$ is power of $2$
  Let $n=2^m$, so number of minimum states $=m+1$.
  For $n=8=2^3$, we need $3+1=4$ states.
  Else If $n$ is odd
  Number of states $=n$.
  For $n=5$, we need $5$ states.
  Else if $n$ is even
  Keep dividing it with $2$ until you get odd quotient. The result is final odd quotient plus number of divisions done.
  For $n=20,20/2=10,10/2=5→5+2=7$ states

I was guessing:
Q1. From where all these facts came. (I know this must have come from general pattern that such DFAs follow, but then I have below doubts)
Q2. Are these points indeed correct?
Q3. If yes (for Q2), then what can be the reason for each point?
Q4. Do these three bullet points cover all cases? (I guess yes, since there is even and odd, but I am new to this, and I was guessing if any such more point is left unmentioned in my textbook, especially since I did not find any reference book (by Peter Linz and Hopcroft-Ullman) talking about this topic)


texts: How to present ping data from ICMP timestamp

texts:
The ICMP timestamp protocol is useful for determining which path — forward or reverse — is contributing to the jitter on the line.

In an ideal world, all computers would have an excellent ntpd, and time accuracy of about 1ms (the granularity of ICMP timestamp) should not be a problem:

0       145.5   146 = 75 + 71
1       142.7   142 = 72 + 70
2       140.7   140 = 70 + 70
3       146.7   146 = 76 + 70
4       148.3   148 = 77 + 71
5       157.5   157 = 87 + 70
6       167.1   167 = 96 + 71
7       166.3   166 = 95 + 71
8       167.7   167 = 97 + 70
9       159.0   159 = 88 + 71

However, in reality, as per https://stackoverflow.com/questions/20172028/awk-hping-print-difference-between-icmp-originate-receive/20186781#20186781, the data could be like this:

0       165.9   166 = -142113 + 142279
1       160.2   160 = -142118 + 142278
2       155.2   155 = -142122 + 142277
3       156.5   156 = -142121 + 142277
4       164.7   165 = -142112 + 142277
5       164.4   164 = -142111 + 142275
6       160.9   161 = -142114 + 142275
7       158.1   158 = -142117 + 142275
8       155.6   156 = -142119 + 142275
9       143.0   143 = -142131 + 142274
10      153.2   153 = -142120 + 142273
11      157.1   157 = -142115 + 142272
12      158.3   158 = -142114 + 142272
13      148.6   149 = -142123 + 142272
14      144.3   144 = -142127 + 142271
15      145.3   145 = -142125 + 142270

Which still shows that only one path is responsible for the jitter, since only one value jumps up and down randomly, whereas the other one is decreasing monotonically (probably due to an actively-running ntpd, which is correcting the time as we ping).

Another example could be less wrong-looking of the time not being synchronised, say:

0       165.9   166 = -113 + 279

Or, better yet:

0       165.9   166 = 7 + 159

Or, say, still wrong by some 10ms to 40ms, on a landline link from Alberta to Vogtland, but much less obvious:

0       165.9   166 = 59 + 107

How to make scientific sense of this data, for it to be easily presentable, and not blatantly wrong?

Feel free to assume to have between 10 to 1000 measurement points, measured over a couple of seconds or minutes.


texts: Equivalence of machine $M$ in $BPP$ and $EXP$

texts:
Ok, the proof is clear. But, if we prove that $BPP \subseteq EXP$ we should show that for every machin in $BPP$ there exists equivalent machine in $EXP$. I cannot see how the $EXP$-machine is equivalent.

If we run machine $A$ on $x$ it can accept a word $x$ with probability $0.5$. Now we can run our $EXP$-machine. It try every possible toin-cosses-result so it compute an average probability of accepting of $x$.
I don't see why it works equivalently- even if the $EXP$-machine has coin-toesses as input, it should be random in any way.


texts: Space penalties for the simulation of a non-deterministic Turing machine by a single-tape deterministic Turing machine

texts: If I have some non-deterministic Turing machine $NDTM$ running some process $Q$ and I wish to simulate the same process $Q$ with a deterministic single-tape Turing machine $DTM$, there will of course be an exponential slowdown.  However, what penalty can one expect in terms of space resources?  Unless one has access to an $RNG$, presumably one has to keep track of which configurations one has already tried?  Can we simulate the $NDTM$ with the $DTM$ using only polynomially more space?


texts: graph theory conventions, difference between a PATH and a GRAPH?

texts:
Consider this example, I did my pseudocode in python

findCycle(G):
    for each edge e in E(G):
        if isThereCycle(G-e):
            G = G - e
    return G

assume isthereCycle returns whether the graph $G$ has a cycle.

Input is a graph $G$ that contains a cycle, and the function should return a path of that cycle.

We go through each edge then remove it and see if a cycle still exists without that edge, until we are left with a graph with a single path that is a cycle. (Assume removing the edge (G - e) doesn't mutate the graph unless we do G = G - e).

I want to return a path. Is what I'm returning a path?


texts:
The problem: Exact Cover by 3-Sets (X3C)

The definition: Given a set X, with |X| = 3q (so, the size of X is a multiple of 3), and a collection C of 3-element subsets of X.  Can we find a subset C’ of C where every element of X occurs in exactly one member of C’?  (So, C’ is an “exact cover” of X).

The class US (Unique Polynomial-Time) is the class of decision problems solvable by an NP machine such that the answer is 'yes' if and only if exactly one computation path accepts.

UNIQUE-3SAT is the problem of deciding whether the 3CNF Boolean formulas have a unique solution. UNIQUE-3SAT is a known US-complete problem.

Is the version of problem Exact Cover by 3-Sets(UNIQUE-X3C) when the instances have a unique solution a US-complete problem? (which means there is a unique subset C’ as solution)

Thanks in advance!!!


texts: Minimum number of rotations of a binary tree to convert it into another

texts:
I have the following binary tree, which I'm trying to convert into the target binary tree (second tree in the post) using minimum number of tree rotations. The theoretical minimum number of rotations for this tree is 5, however, the smallest value I can figure out is 6 rotations, I have copied the rotations as well, what am I missing?

Tree:

 1
  \
   \
   3
  / \
 /   \
 2    5
    /   \
   /     \
   4      7
        /   \
       /     \
       6     11
            / \
           /   \
           9   12
          / \
          8 10

Target Tree:

     1
      \
       \
       11
      /   \
     /     \
     9      12
    /  \
   /    \
   3     10
  /  \
 /    \
 2     5
      / \
     /   \
     4   7
        / \
        6 8

The rotations I have tried so far (all of which require 6 rotations):

Order1:

Rotate left with root 7 and pivot 11
Rotate left with root 5 and pivot 11
Rotate left with root 3 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 9

Order2:

Rotate left with root 7 and pivot 11
Rotate left with root 5 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 3 and pivot 11
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 9

Order3:

Rotate left with root 7 and pivot 11
Rotate left with root 5 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 11
Rotate left with root 3 and pivot 9

Order4:

Rotate left with root 7 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 11
Rotate left with root 3 and pivot 11
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 9

Order5:

Rotate left with root 7 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 11
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 11
Rotate left with root 3 and pivot 9


texts: Enumerate probabilistic and other kinds of Turing machines together

texts:
When we talk about the enumeration of TM's, do we mean the "regular" deterministic ones? So if we want to enumerate nondeterministic or probabilistic TM's, do we need a separate enumeration?

I can see how we could describe probabilistic TM's as strings, just as we describe the deterministic TM's only now we have two transition functions. Then it also follows that checking whether some string enumerates a probabilistic TM is decidable. Perhaps one could think of a way to create some universal coding of TM's to strings that works for all different kinds of TM's? Perhaps the first ... digits of the enumeration describe what kind of TM (probabilistic, determinstic etc) it is and then follows the description of the TM in the standard fashion. So then we can enumerate all the TM's?

A related question, does a TM know it's own description? Or can we give it that information without loss of generality?


texts: When LRU is NOT the optimal replacement policy

texts: I've been googling this topic but still couldnt get a legit answer. So can someone explain with some examples that if we were to use cache memory instead of LRU we would have lower miss rate (better peformance). Or simply when LRU is not an optimal choise.


texts:
The following problem was on my final and in Gate 2006, but I don't understand how to solve it:

Different methods of memory management have different overheads:

The paging method for memory management uses two-level paging, and its storage overhead is $P$.
The storage overhead for the segmentation method is $S$.
The storage overhead for the segmentation and paging method is $T$.

  What is the relation among the overheads in the concurrent execution of the processes below?

  (a) $P < S < T \hspace{2em}$
  (b) $S < P < T\hspace{2em}$
  (c) $S < T < P\hspace{2em}$
  (d) $T < S < P$

Process    Total Size (in KB)    Number of segments
 P1              195                    4
 P2              254                    5
 P3               45                    3
 P4              364                    8

The page size is 1 KB.
The size of an entry in the page table is 4 bytes.
The size of an entry in the segment table is 8 bytes.
The maximum size of a segment is 256 KB.


texts:
We have undirected connective, weighted graph $G = (V,E)$.
we also know that for every $e,e'$ in $E$, $w(e)≠w(e')$.
Prove that $G$ has a single MSP.
Ideas?


texts: Name for this algorithm to roughly shuffle infinite list with finite memory

texts:
A couple of friends and I were talking about the best way to attempt to shuffle a infinite list, given finite memory.
We immediately concluded that you could not do so, at least not in the same sense that you could shuffle a finite list.
But we devised an approximation.

Initialize: Draw from the infinite list $L$, a array of items $W$ which we will call the window, of size $w$ items ($w\in\mathbb{Z}$)

Output
To output an element from our shuffled list:

$i\leftarrow rand(0:w)$  -- Generate a random integer $i$, with $0\le i < w$
$r\leftarrow W[i]$ -- select the item to return
$W[i]\leftarrow head(L)$ -- replace it with the first item in the infinite list
$L\leftarrow tail(L)$ -- remove that item that we took
Output $r$

So the basic idea is that we give a random item from a finite window, which we take with replacement from the infinite list.

Now I am sure this is not a new idea.
So I am looking for a name for it, so I can look into it and read up on its properties. Eg it is clear that by increasing $w$ increases the "entropy" in some sense. But I am not sure if for a fixed $w$ if over time it converges to a steady state for the expected positional distance between adjacent output items.

Also so that if I end up implementing and using it in my current work, I can cite the right paper.


texts: Intermediate code generation and three address code

texts:
I have a Compiler Design course this semester but unfortunately the professor teaching this course have some issues with text book which is Compilers, Principles, Techniques & Tools by Alfred Aho and others.
For the section Intermediate Code Generation there is a slide which introduce a method to do so. I provide a photo here, the top is some definitions and the bottom is an example of the method which has no clear algorithm in the slide or even on the web:

I've searched for the method for hours but not a single PDF or Youtube video were found.
Does anybody know anything about this method? What are the steps? What are these Semantic Stack and others?
Here is the link for slide for clearance:
Full Slide


texts: Sampling maximal shortest paths in a graph?

texts:
Let S be the set of all possible shortest paths in a directed graph. A path s in S is said to be maximal if it is not a subpath of another path in S i.e. it cannot be extended to another shortest path.

Let M be the set of all maximal paths in S.

Does anyone know how to efficiently sample paths from  M. Ideally, I would like the probability of sampling the longer paths in M to be higher.

Example: In the directed triangle, (1,2,3), we have 3 maximal paths, 1->2->3, 2->3->1, and 3->1->2


texts: Given a Turing machine , How to construct a efficient boolean circuit?

texts:
The proof of $P\subseteq P_{\\poly}$, Let $M$ is a Turing machine with $T(n)$ is running time and  goal here is to design a boolean circuit of size $O(T(n))$ (for more detail see Arora and Barak page no -105 ).

The idea is that you can compute configuration $c_i$ from configuration $c_{i−1}$ by examining the content of 3 adjacent cells  (i.e. by constant size circuit).

First Case :
Let us consider that snapshot is the configuration of Turing machine i.e. requires $O(T(n))$ size.

Number of variables $x_{i,j}$, where $i$ represents a row in table and $j$ represent the colum( cook -levin reduction proof)  are $T(n) \times T(n)$ many. Now when we combine the constant size circuits of all variables then size of the resultant circuit is going to be $T(n) \times T(n)$ ,which is polynomial but  my goal was to design a circuit of size $O(T(n))$.

Second case : Let us consider that snapshot is  machine's state and symbols read by all heads. let us consider they are $z_1,z_2 \cdots z_{T(n)}$ and size of each $z_i$ is constant string. To compute a snapshot $z_{i+1}$for this computation I need $z_i$, all old head positions and current head symbol .This all are constant size string, so I need only constant size circuit to encode the computation (current head position only depends upon the three symbol in the table in cook - levin theorem, or In other words, it is a map say $M$: $\tau^3 \mapsto \tau$, $\tau$ is a tape alphabet. So the total size of the circuit is $O(T(n))$

Question : To design a boolean circuit of size $O(T(n))$ for Turing machine $M$ with running time $T(n)$?


texts: Computing the "at least k friends in common" graph

texts:
Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order to show them friend recommendations.

What is the most efficient way to do this? Does this problem have a name?

Apart from the naive solution (check all pairs - complexity $O(N^2 d)$ where $d$ is the average degree), the best I could come up with is the following:

For every vertex, gather all pairs of its neighbors. The current vertex is one of their "friends in common".
Count pairs that occur more than k times.

The complexity is something like $O(N d^2)$ which is strictly better.

It seems that there should be a more efficient solution (though obviously not better than $O(N^2)$ in the worst case), but I can't see any particular structure in the problem pointing toward it.


texts: How can I solve this problem using dynamic programming?

texts:
I'm stuck in this problem and I would need some help:

Given an array arr, in each step, 1, 2 or 5 units have to be incremented to all but one item of the array. The goal is to find the minimum number of steps to all items to be equal.

First example

arr = [1, 1, 5]

1) [1 (+2), 1 (+2), 5] = [3, 3, 5]
2) [3 (+2), 3 (+2), 5] = [5, 5, 5]

Solution: 2 steps

Second example

arr = [2, 2, 3, 7]

1) [2 (+1), 2 (+1), 3, 7 (+1)] = [3, 3, 3, 8]
2) [3 (+5), 3 (+5), 3 (+5), 8] = [8, 8, 8, 8]

Solution: 2 steps

I have tried some things but I'm really stuck.

I consider a base case when all items are already equal. In another case, I try to find all the possible solutions by incrementing 1, 2 and 5 to every item but one in the array:

def equal(arr):

    if (allElementsIdentical(arr)):
        return 0

    min = sys.maxsize
    for i in [1, 2, 5]:
        for j in range(len(arr)):

            #Increment all items by "i", except item at index "j"
            newArr = arr.copy()
            for k in range(j):
                newArr[k] += i
            for k in range(j + 1, len(newArr)):
                newArr[k] += i

            movements = 1 + equal(newArr)
            if movements < min:
                min = movements
    return min

This solution doesn't work because recursion never ends. E.g.

[1, 1, 5] -> [1, 2, 6] -> [1, 3, 7] -> [1, 4, 8] -> [1, 5, 9] -> ...

Is it my initial approach correct? How can I break it down in subproblems?


texts:
I'm trying to create a procedure in MySQL/MariaDB with optional filters for each participating table. Assuming the tables are $A, B, C, \ldots$, each table may or may not be filtered, and the result is that of each table having their respective optional filters applied. $A$ and $B$ have the relation A (1) -> (*) B, and similarly, B (1) -> (*) C and so on. (A (1) -> (*) B is the pseudo-ERD notation of one-to-many relation, where a member of $A$ has 0..* members of $B$ but a member of $B$ belongs to exactly 1 member of $A$)
With that, I've thought of the following function to filter & join each pair of tables:
/*
  F(): filter
  L: left side
  R: right side
*/

if(L.filter is NULL and R.filter is NULL) {
  return fullJoin(F(L), F(R))
} else if(L.filter not NULL and R.filter is NULL) {
  return leftJoin(F(L), F(R))
} else if(L.filter is NULL and R.filter not NULL) {
  return rightJoin(F(L), F(R))
} else { // both not NULL
  return innerJoin(F(L), F(R))
}

The filter function F() would be something like SELECT * FROM table WHERE input == NULL or input == column. The function is first applied to 4 tables as follows:
fn(fn(fn(A,B),C),D)

where the result of said function fn is considered to have a not NULL filter.
Additionally, I think the function fn can be packed into the following:
SELECT * FROM L FULL JOIN R
WHERE (R.input == NULL || R.input = R.column)
AND (L.input == NULL || L.input = L.column)

Assuming my function is wrong (because it's the first draft), how is it flawed?


texts:
I'm trying to do some non-linear predictions and am going to use a random forest with Sk-learn. However my question has to do with data pre-processing.

I'm planning on using minmaxscaler to normalize the temperature, wind, and humidity data...however I have two other variables class, and month. Class is a category data feature which I'm going to use OneHotEncoder to pre-process. However do I want to normalize or do anything with the month data? (Normalize on scale of 0 to 1? Or leave 1-12?) What might be the best approach?

Thanks!


texts: The difference between $\beta$-reduction and $let$

texts:
These are the reduction rules associated with $\beta$ reduction and $let$:
$$(\lambda x. e_2) e_1 \to_{\beta} e_2 [e_1 / x]$$
$$let \,x = e_1 \textit{ in }e_2 \to e_2 [e_1/x]$$
These reduction rules are very similar.
What is the point of having $let$ as well as $\beta$-reduction?
I can't see why it is of any use.


texts:
Show that if $SAT \in P/klog(n)$ then $SAT \in P$
Assuming that there is a a constant $k \in \mathbb{N}$ such that $SAT \in P/klog(n)$, I need to prove that $SAT \in P$.
Since $SAT \in P/klog(n)$, then there is a sequence of advices $\{a_n\}_{n \in \mathbb{N}}$ of length $|a_n \le klog(n)$ and a turing machine $M$ that runs for at most $n^c$ steps (for some $c \in \mathbb{N}$ such that:
$$\phi  \in SAT \Leftrightarrow M(\phi, a_{|\phi|}) = 1 $$
I tried to show a Turing machine $U$ that runs in a polynomial time and solves $SAT$.
$U$ on an input $\phi$:

calculate the size $|\phi|$
write $a_{|\phi|}$ on start of the working tape
simulate $ M(\phi, a_{|\phi|})$ in a way that when $M$ tries to read $a_{|\phi|}$, it will read it from the start of the working tape, and the working tape of $M$ will start from offset $|a_{|\phi|}|$.
$U$ will return the same answer as $M$

Is my answer correct? It seems like I'm missing something
Help would be appreciated.


texts: I wonder if there are papers that uses max cut algorithm(s) to cluster data. For example, if an edge between two nodes $u$ and $v$ indicate that $u$ and $v$ are different, then the max-cut in some sense partition the data into two clusters in a meaningful way.


texts: Decidable language that has no finite description?

texts:
A language is a collection of strings--assuming we have an infinite number of words then concatenating this collection (keeping things simple,  normally you need to at least be able to tell where one word ends and another begins) and viewing the language as the resulting single big string, if the Kolmogorov complexity of this string is infinite can the language still be decidable?
This is asking if a language without a finite description can be decidable...also maybe sort of like asking if a language that is not constructible can still be decidable?
If I were to guess, I would say why not..? For example, a language could be given to you as an infinite table of rules (programs) for membership (that, per our condition above, can't be compressed into a smaller set of rules) paired with all words, but have only a finite number of the them be conditions for any particular word or group of words to be members. It is not your job to build such a table but once given such a table you could, when given a word, seek the rule in the table corresponding to that word (if the table is neatly organized this should be possible as to decide any particular word you ever only need to access a finite position on the table), check that word against that rule (run the program that is there on its word), and if doing so is computable for every rule in the table then the language specified by the infinite table should be decidable but at the same time not necessarily be finitely expressible.
Thanks!


texts: Examples of real world graphs that are too big for a single commodity-type machine

texts:
I've been reading on distributed systems for processing on large graphs. The most prominent examples include Pregel (developed by Google) and Apache Giraph. Most of these systems argue their existence that they are for "big data" processing, i.e., they can handle graphs that are too big to fit into a single machine.

While I'm aware that there are (a few) real world examples of graphs that are HUGE, for example, the Facebook graph (billion of nodes, trillion of edges), or the web graph, it seems to me that these are outliers and most people will rarely ever have to deal with such data sets.

  Are there examples of graphs that frequently occur in the real world (i.e. either created by humans or occurring in nature) that are so huge that they cannot be handled by a single (commodity-type) machine?


texts: Computational models where halting problem is solvable

texts: Are there computational models that can be considered useful for solving common programming problems, where it can be proven that computation will terminate for all possible inputs?


texts: Justifying a claim in the proof of the master theorem

texts:
I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true.

My argument is as follows:
Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}\right)$.
$$g(n)=\sum_{i=0}^{\log_{b}(n)-1}a^if(n/b^i)$$
Now by the definition of big O, we have that $\exists c\in\mathbb{R}, N'\in \mathbb{R    }$ such that $\forall n/b^j>N'$, we have that $$f(n/b^j)<c(n/b^j)^{\log_b{a}-\epsilon}$$
This implies that $\forall n>N'b^{\log_bn-1}$
$$g(n)=
\sum_{i=0}^{\log_{b}(n)-1}a^if(n/b^i)
\leq \sum_{i=0}^{\log_{b}(n)-1}a^ic(n/b^i)^{\log_b{a}-\epsilon}
\leq c\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}
$$
Which implies that $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\log_b{a}-\epsilon}\right)$ with $M=c$ and $N=N'b^{\log_bn-1}$.
Have I found the correct $c$ and $N$ to prove this claim for the upper bound of $g(n)$ and is this proof valid? Thanks!


texts: What's the correct algorithm to filter accumulating string concatenations?

texts:
I have a function that is receiving messages with the following pattern:

(In this picture, "string" and "message" are synonymous.)

I'm only interested in the largest messages, such as these:

over a particular window.

Is there an algorithm that can appropriately filter the messages in the desired manner over a specified window?


texts: Number of computations for multiplication

texts:
I just read Marvin Minskys' "Form and Content in Computer Science" and found myself confused with the following paragraph:

  A startling discovery was made about multiplication itself in the
  thesis of S.A. Cook [3], which uses a result of A.L. Toom, as
  discussed in Knuth [4]. Consider the ordinary algorithm for
  multiplying decimal numbers: for two n-digit numbers this employs
  n-squared one-digit products. It is usually supposed that this is
  minimal. But suppose we write the numbers in two halves, so that the
  product is N = (#A+B)(#C+D), where # stands for multiplying by 10 subscript{n/2}.
  (The left-shift operation is considered to have negligible cost.) Then
  one can verify that

  N = ##AC + BD + #(A+B)(C+D) - #(AC+BD).

  This involves only three half-length multiplications, instead of the
  four that one might suppose were needed. For large n, the reduction
  can obviously be reapplied over and over to the smaller numbers. The
  price is a growing number of additions. By compounding this and other
  ideas, Cook showed that for any e and large enough n, multiplication
  requires less than n*(1-e) products, instead of the expected
  n-squared.

I got stuck when I read stands for multiplying by 10 ... because I didn't understand what the subscript in this example means. I tried to find it out by googling about the complexity of multiplication and stuff like that, but couldn't find the answer.

Can you point me in the right direction here? I guess that this exact part is essential for understanding the formula in the middle. I would like to find out how this computation would resolve a multiplication.


texts: How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?

texts:
According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows how to convert a grammar to a Turing machine.

How do I indeed do that and convert the Turing machine the recognizes language $L$ into an unrestricted grammar? I have tried replacing transition rules with grammar rules, but a Turing machine can have many different configurations of states as well...


texts: Something wrong when recognizing data set using Binary Artificial Neural Network

texts:
I have learnt Neural Network for a couple weeks. I just met a problem when I tried to use ANN to recognize a dataset.
So I'm gonna describe the problem:
Set A has 15 members which are in set {1, 1.5, 2, 2.5... 4}.
I need to recognize set A if it is in type 2 or not. There are 3 types:

Type 1: Sum(A) < 30
Type 2: 30 <= Sum(A) <36
Type 3: Sum(A)>=36

I'm able to recognize if A is type 1 or type 3, but something went wrong when I tried with type 2. I think because type 2 is in the middle of type 1 and type 3 so I need to do something more.

I tried 2 models of binary ANN:

The Neural network has 3 layers,input: 16 cells, hidden: 8 cells,
output 1 cell.
The Neural network has 4 layers,input: 16 cells, hidden1: 8 cells,
hidden2: 2 cells, output 1 cell.

Biases have been using through the network.

So the question is am I able to recognize the type 2 by using a single binary ANN? It means separating type 2 (class A) from type 1 and 3 (class B). And if it is possible, can you recommend the model of neural network?


texts: Relabel to front, what does topological sort according to admissible network mean?

texts:
In the CLRS book it says that "relabel to front" algorithm, which solves the maximum-flow problem, maintains a list of topologically sorted vertices in the admissible network and that vertices with zero excess flow are moved to the front of the list.

I do not fully understand what is the meaning of it. I would imagine that the vertices are sorted according to the number of admissible edges incident on it. But then how would moving vertices with no excess flow to front affects the sorting order in this case. Also how come the list is already sorted when it is initialized with random order of vertices?

Edit:

Just realized that topological sorting of vertices in the admissible network means that for every admissible edge (u,v) in the admissible network the vertex u appears before v in the list.

This does not answer the last two parts of my question though, how is that the list is already sorted when initialized and how does moving zero-excess-flow vertices to front affect the order. Thanks.


texts:
I've heard that every $n$-PDA when $n > 2$ is as powerful as $2$-PDA. Unfortunately every proof I'm able to find uses references to Turing Machines, which I haven't learned about yet. I'm sure there must exist an alternative proof, supposedly one that converts $n$-PDA to $n-1$-PDA, and then proceeds by induction, but I'm unable to find it. Any references, or hints are greatly appreciated.

What I tried: to simulate two stacks using just one, therefore going from $n$ to $n-1$. But it would also mean that $2$-PDA are as powerful as $1$-PDA, so it's clearly a wrong way.


texts: Code optimization - syntax tree vs. intermediate representation

texts:
I'm working on a compiler for my own custom language.  As I was reading an article on code optimization, I noticed that it assumed that the intermediate representation of the code had already been formed.  Though I haven't yet started writing the optimization section of my compiler, I've been going through it in my head and it seems preferable to have the optimizer operate on the syntax tree before converting to the intermediate representation.
Is there a reason to prefer one approach to the other or is mostly a matter of personal taste?
For example, suppose I have an if block like
if ( some_expression ) {
    do_stuff
}

If it could be recognized by the compiler that some_expression will always evaluate to true and have no side effects, then I could remove its computation simply by pruning the tree.
However, if I had already converted the tree to an intermediate representation, such as an assembly-ish list of simple instructions, the processes of recognizing and resolving the scenario would be (in my imagination since I haven't yet attempted to implemented this) far more complicated.


texts: Search for numerical solutions of underdetermined systems of quadratic equations

texts:
I'm looking for an algorithm that can quickly generate an approximate real number solutions of an underdetermined quadratic system. My task is to explore its algebraic variety. I'm interested in a special cases of quadratic systems that arise from mechanics:

set of variables $X = \{ x_i, y_i, z_i | 1 \leqslant i \leqslant N\}$ (3*N variables for $N \in \mathbb{N}$),

a system consists of two kinds of equations:

1) $(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2 + p_{ij} = 0$ for $i, j \in [1,N]$ and $p_{ij} \in \mathbb{R}$.

2) a more general case of 1: $(x_i-x_k)(x_j-x_k)+(y_i-y_k)(y_j-y_k)+(z_i-z_k)(z_j-z_k) + a_{ijk} = 0 $ for $i, j, k \in [1,N]$ and $a_{ijk} \in \mathbb{R}$.

It's guaranteed that variety of solutions is stable under small changes of coefficients.
Here is an example with six-dimensional variety of solutions:

(x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 - 1 = 0
(x3-x2)^2 + (y3-y2)^2 + (z3-z2)^2 - 1 = 0
(x3-x4)^2 + (y3-y4)^2 + (z3-z4)^2 - 1 = 0
(x1-x4)^2 + (y1-y4)^2 + (z1-z4)^2 - 1 = 0
(x2-x1)*(x4-x1) + (y2-y1)*(y4-y1) + (z2-z1)*(z4-z1) - 1/3 = 0
(x1-x2)*(x3-x2) + (y1-y2)*(y3-y2) + (z1-z2)*(z3-z2) - 1/3 = 0
(x2-x3)*(x4-x3) + (y2-y3)*(y4-y3) + (z2-z3)*(z4-z3) - 1/3 = 0
(x1-x4)*(x3-x4) + (y1-y4)*(y3-y4) + (z1-z4)*(z3-z4) - 1/3 = 0

First, the algorithm is allowed to process this underdetermined system for some time. After that, it should get as input a set of constraints, like $x_1 = 0$ or $z_N = 1$, that turn the system into determined and quickly generate real solutions of it. For instance, one can find 8 real solutions of the system above after constraining all of $\{x_4,y_4,z_4,y_3,z_3,z_2\}$ to zero.
I need the algorithm to be scalable so it can be applied for N=25-30, however high precision of solutions isn't required, 3-4 orders will do.

I've come up with a few approaches:

I tried to calculate Gröbner bases for such systems in Magma:

    P< x1,y1,z1,... > := PolynomialRing(RationalField(),3*N);
    I := ideal<P | my equations >;
    Groebner(I);

It works for zero-dimensional ideals, but coefficients were big even for N=7. In cases with dimensions >0, calculation took too long (with enough RAM) and I have been able to compute Gröbner bases only for small systems.
So I tried compute approximate Gröbner bases by running OpenF4 algorithm with datatype of coefficients changed on double, but the error grew significantly on each step of the computation.

Also I consider a calculation of Gröbner basis in grevlex order with subsequent transformation to lexicographic using FGLM-like algorithm.
I found this article https://arxiv.org/abs/1703.07810 and this looks useful for my purpose. I'm not familiar with such methods, but probably this is exactly what I need.

Here are my questions:

Is there a way to calculate an approximate Gröbner bases in reasonable time using my idea or any other approach, maybe for other order with subsequent transformation to lexicographic?

Can this problem be solved without Gröbner bases using methods like №3 or any other?

Any comments on my ideas and new suggestions would be highly appreciated.


texts: Finding a kernel for 1-Bounded degree deletion of $O(k^2)$ vertices

texts:
In 1-BOUNDED DEGREE DELETION problem, we are given an undirected graph G and a positive integer $k$, and the task is to find at most $k$ such vertices whose removal decreases the maximum vertex degree of the graph to at most $d$.
The question is how to find a polynomial kernel with $O(k^2)$ vertices.
This question is related to this question and to exercise 2.9 from here.
I am looking for a kernelization algorithm of at most $O(k^2)$ vertices while the previous question accepts any kernel, specifically, the answer that is provided is of $O(k^3)$.
Following this guidline about followup questions I have decided to post it as a new question.
I have been trying to modify the suggested answer without and couldn't get a better bound on the vertices. I also been checking out different approaches such 3-star packing following this paper but without any sucess.
any suggestions?


texts: Number of iterations of the Euclidean algorithm

texts:
I have a doubt about the runtime of the Euclidean algorithm; the slide of my Professor says:

The calculation of $\mathrm{GCD} (a, b)$ stops at the most after $2\log_2 a$ iterations.

Since $\log_2 a$ is the size of the input,
calculation requires a linear number of iterations.
The algorithm therefore has polynomial runtime.

I don't get how he could deduce (2) from (1), and (3) from (2); until now, the only concept of theory that he gave us is that to represent a positive integer, we need $1+\log_2 x$ bits.


texts: Lexicographically smallest down-right path in matrix

texts:
Here is the problem which I thought was simple dynamic programming, which is however not the case.

Given an $N \times M$ matrix of numbers from 1 to $NM$ (each  number occurs only once), find a path from top left to right bottom while moving right or down only. If we sort all values visited in this path it should be lexicographically smallest.

I thought smallest sum path will be the answer, but it need not be true.


texts:
If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise.

Question: does the reverse hold? Thus, if $\text{mir}(L)$ is context-free, do we always have $L$ is regular?


texts: Does the AND-compression of SAT depends on the number of SAT instances?

texts:
From a paper

  An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances $x_1,\dots,x_t$ to a single SAT-instance $y$ of size $poly(\max |x_i|)$ such that $y$ is satisfiable if and only if all $x_i$ are satisfiable.

My question is: Is $t$ treated as constant?

Another paper gives related definition, explicitly stating
that the strong AND compression must be independent of $t$.
.


texts:
I need to store a list of sequential intervals.
So for example I would to say:

{0-5} = a
{6} = b
{7-10} = c

and so on.
I need to add and remove items from this list:
.insert(d,{1,3})

will make our array:

{0} = a
{1-3} = d
{4-5} = a
{6} = b
{7-10} = c

Morehover you may need to check what items cover a range:
.itemsIn({6,8}) will return b,c.

I can keep an array with pointers to the same object instance for each value in a range but I suppose I can do a better job.
Interval tree?


texts: Partial path known in Single source shortest path problem

texts:
I'm using the A* algorithm with a consistent heuristic on a graph to determine the shortest path.

If the algorithm is exploring a node $p_1$ for which there is a existing knowledge about the optimal $k$ ($p_q,p_r,p_t,p_5$) successive nodes, then can we store $p_5$ directly into the open list? Or do we have to store the intermediate milestones (each node in the known successive optimal nodes) into the open list?

Weights are positive real numbers.


texts: Recognize end of Input in a Turing Machine

texts:
If I have a turing machime TM, can I recognize end of input on the tape?
I know that the "end of input" in a turing machine is signaled with a special character, $\sqcup$.
Can I do this -

Let $TM$ be a turing machine.
Until we reach the first $\sqcup$, continue. If we reached $\sqcup$, replace it with a special character - #.

Is it "legal" to that this?


texts: Basic Question in networking - why max data size of ip datagram 65535 BYTES and not 65535 bits?

texts:
I recently started computer networks with some understanding of algorithms and discrete mathematics. I am completely new. Kindly elaborate following -

data size of ip datagram = 16bits. So with this $2^{16} -1 = 65536$ 16 bit patterns can be generated.
My doubt:

Do we say each 16 bit pattern is 1 IP datagram or all those 65536 patterns as 1 IP Datagram?
If i consider all 65536 patterns as max data size, then max ip datagram size $= 65536$ patterns size$ = 65536*16 $ bits $= 65536*16/8$  bytes $= 65536*2$ bytes


texts: Number of independent parity checks satisfied by a code

texts:
I have been studying quantum error correction codes and as background, I am currently studying the theory of classical linear codes. Despite many efforts, I am unable to understand the following excerpt:

Any given parity check u divides Hamming space exactly in half,into those vectors which satisfy u and those that do not.Therefore,the 2^k vectors of a linear subspace in 2^n Hamming space can satisfy at most n−k linearly independent parity
checks.These parity checks together form the parity check matrix H, which is another way to define the
linear subspace.


texts:
There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of size $k$ in $G(n, p)$.

I know that $\mathbb{E}(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it?

How to show that $\mathbb{E}(X_{\log_2n})\ge1$ for $n\to\infty$? And how to show that $\mathbb{E}(X_{c\cdot\log_2n}) \to 0$ for $n\to\infty$ and a fixed, arbitrary constant $c>1$?


texts: What is memory model in computer organization?

texts:
I'm new to Computer Organization and even to this community. I didn't find anything which was simple, clear and up to the point. Any examples supporting the discussion is appreciated. I'm not looking for some text book answer.

Here's an example of my view to question: What is a Programmer's Model ?
Programmer's model shows what the CPU has available to a programmer for the execution of computer programs.
It covers the CPU resources for execution of the CPU's instruction set.
(resources like state variables, AKA registers that can affect — or be affected by — the execution of instructions)

This programmer's model would NOT detail hardware, such as how the CPU's electronic circuitry works,
how buses transport data or the I/O peripherals available.
i.e. The underlying details of how all of that is actually accomplished are hidden from the programmer.

In other words, the programmer's model would NOT cover functions that cannot be observed by CPU instructions.
[EXCEPTION: those instructions trying to detect hardware operations, such as cache behavior, read/write variances because of varying bus delays etc are excluded]

So, similarly I wish to know what is a Memory Model ?


texts:
I can't seem to find this stated explicitly anywhere, which makes me wonder if I have it all wrong.

So first, let's say we view problems in NP as degenerate problems in FNP, where the codomain of the binary relation is the set {true, false}.

Second, FSAT is known to be FNP-complete, meaning that everything in FNP can be reduced to it in polynomial time. Also, FSAT is polynomial-time reducible to SAT, which is NP-complete, and then a SAT problem can be changed to anything else in NP-complete in polynomial time. So this shows that everything in FNP-complete can be changed to something in NP-complete in polynomial time.

So the first thing shows that NP-complete $\subset$ FNP-complete, but then the second thing shows that FNP-complete $\subset$ NP-complete, which means that NP-complete = FNP-complete.

So given that, it seems like everything in FNP can be reduced to any NP-complete problem in polynomial-time.

Am I going somewhere wrong here, or do I have this all right?


texts:
Let $quasiP$ be the quasipolynomial time complexity class.

Is $E^{quasiP}=E$ false?

Is $E^{DTIME(2^{(\log n)^k})}=E$ false at every $k>1$?


texts: An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

texts:
Is there an incremental directed graph data structure that has the following properties:

Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper data-structures)
The accessible DAG is kept as a transitive reduction (notwithstanding other helper data-structures)
It should be optimized for a sparse graph (adjacency lists)
It should condense cycles as they are introduced, keeps a mapping between equivalent vertices that are all replaced with one "representative" vertex
Ability to quickly answer quickly ancestor/descendant/transitive/relationship queries (in $\mathcal{O}(1)$ or $\sim\mathcal{O}\left(\log \left|V\right|\right)$ time)
Should support vertex, edge insertion, deletion would be nice too
Mutable operations  (such as insertion) should be as output-sensitive as possible; in other words, the complexity should depend as much as possible on how much the operation must change the graph
Ability to record changes over an operation, if requested. Obviously this might necessarily increase the complexity, but the increase should be output-sensitive. Examples:

set of deleted vertices (due to condensation)
set of deleted edges (due to reduction)
set of new decendent relationships from $u$ ( example: $insert(G,u,v) \rightarrow \left\{t ~|~ path(u,t)\in G'\wedge path(u,t)\not\in G\right\}$ )
set of new ancestor relationships from $v$ ( example: $insert(G,u,v) \rightarrow \left\{t ~|~ path(t,v)\in G'\wedge path(t,v)\not\in G\right\}$ )

The closest I can find is here, implementation. I think you can build on this to do have most of the properties I list, but I am wondering if there is anything better/well known, or perhaps if there is a name for this problem.

EDIT:
Related:

What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?
What is the fastest deterministic algorithm for incremental DAG reachability?
Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?
Is there an online-algorithm to keep track of components in a changing undirected graph?
Dynamic shortest path data structure for DAG


texts: Does classification of a problem also require the algorithm used?

texts:
Just learnt that a problem in computer science can be divided into the following categories

Polynomial problems
NP problems
NP hard problems
NP complete problems

based on how long it takes to run the program

For example, suppose there is a problem P that can be solved with two algorithms say A1 and A2 where,

A1 is polynomial in nature,
A2 is non-polynomial

According to me, if P is solved using A1, then P is a polynomial problem and if P is solved using A2, then it must be an NP problem.

Am I right?

In other words, is it fair enough to say that classification of a problem does also require the algorithm that is being used to solve it?


texts:
I am working on an assignment where one of the sub questions is:

  Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \Sigma^* \to \Sigma^*$ such that for all $w \in \Sigma^*$, $w \in A$ iff $f(w) \in B$. Is it possible that $B$ is regular?

My take on this is that since context-free languages are on a 'higher' level than regular languages this is not possible. Apparently this is not the case, but I do not understand why.
Does anyone have a good explanation?


texts: Example of an algorithm that lacks a proof of correctness

texts:
We have Hoare logic. Why is it still possible that an algorithm is right but there is no proof that it's correct? Suppose the algorithm is expressed in C. Then we can argue step by step that it's doing what it's supposed to do.
So my question is:

Give me an example of an algorithm that's right but does not have a proof of correctness.

EDIT: I think a little background can help clarify where I'm going. Let me quote Scott Aaronson:

Since the 1970s, there's been speculation that P $\ne$ NP might be independent (that is, neither provable nor disprovable) from the standard axiom systems for mathematics, such as Zermelo-Fraenkel set theory. To be clear, this would mean that either

a polynomial-time algorithm for NP-complete problems doesn't exist, but we can never prove it (at least not in our usual formal systems), or else

a polynomial-time algorithm for NP-complete problems does exist, but either we can never prove that it works, or we can never prove that it halts in polynomial time.

I'm referring to the second possibility. Since Aaronson can so confidently list it as a possibility, I think there must be an existing example of type 2. That's why I'm asking this question. But it seems a quick and clear answer is not in view.


texts: Does this regular expression equal this automata?

texts:
I just came across an exercise which is to find a regular expression for the following automata, such that the regular expression and the automata generate the same language.

One solution presents the following expression:

$\qquad \displaystyle r_A = a^+b^+(c\mid ca^*b^+)^*$

However, can this be true? I think not, because the all words created from the regular expression will have at least one $b$ in it, whereas the automata accepts words without $b$, such as $aaa$.

What is your opinion?


texts: Regular expression for capturing a "C-style" string

texts:
I have started to learn automata theory and languages. I am new to regular expressions.

As a use case in real world, I would like to construct a regular expression to accept a c-style string: enclosed by double quotes, allows escape sequences (\" to escape a double quote, \ escape a backslash, \n escape a new line...) and allows all characters in between, and pretty much everything that the standard identifies as a string literal.

I don't have a specific language that the regex is to be used in, for I'm not going to use this in a program. I just want to know the theory behind constructing the regex, one step at a time. For example, Initially, how to account for the enclosing quotes ? then how to allow arbitrary sequences of characters between the quotes ? and then how to account for escaping ?

I don't have a regex tester. I just need the construction idea.

Strings that are to be accepted are, for example,

"hello world!"
"hi!\n"
"000022lkjads\t{"
"\0Hello World"

The following would be rejected

"hello

for there is no enclosing double quotes

"Hello World""

for it does not escape the quote


texts: What does it mean to have a continuous action space w.r.t. to reinforcement learning?

texts:
Last time I posted this question I got criticised for not being specific enough, hence this is my second attempt at trying to understand what it means to have a continuous action space.

Please refer to this paper, page 5 (A Survey on Policy Search for Robotics
by Marc Peter Deisenroth, Gerhard Neumann and Jan Peters. Foundations and Trends in Robotics. 2013).

The authors say:

  The RL algorithm has to manage (i) high-dimensional continuous state
  and action spaces, (ii) strong real- time requirements, and (iii) the
  high costs of robot interactions with its environment.

I do not understand how an action can be continuous, in the same way that a state-vector is continuous by virtue of having elements that are simply $x_k \in \mathbb{R}^D$ for a state vector $\mathbf{x} := [x_1,\ldots,x_K]^T$. But how can an action be quantified in the same way? It obviously can I simply do not understand how.


texts: Could a standardized ternary system be more efficient than the binary system?

texts:
Could a standardized ternary (base-3) system be more efficient than the binary (base-2) system? Binary is efficient for processing using logic gates, but can be bulky when using for file storage or file transfer. I am interested in the feasibility of a ternary system both for file storage, file transfer, and computational processing.

The following three examples show an ASCII word converted to both binary and ternary, along with the length of the sequence:

ASCII Example 1: Hello

Binary: 0100100001100101011011000110110001101111 (40 characters)

Ternary: 210011101002200222 (18 characters)

ASCII Example 2: Test

Binary: 01010100011001010111001101110100 (32 characters)

Ternary: 220200002020100202 (18 characters)

ASCII Example 3: Cat

Binary: 010000110110000101110100 (24 characters)

Ternary: 22022100102101 (14 characters)

As denoted by the character count, the length of the ternary sequence can sometimes be less than half the length of the binary sequence. Having shorter sequences would be beneficial for file transfer, file storage, and computational processing speeds. On the surface this seems preferable, but perhaps there are disadvantages or implementation flaws which I am overlooking. The following contains additional observations (which may or may not be feasible), for implementation.

File Storage

Ternary would be highly beneficial for file storage but would require hardware changes. For example, manufacturers of flash memory storage devices such as flash drives or solid state drives would have to re-architect the transistors in order to store the representation of a 0, 1, or 2. If these transistors could maintain the same size dimensions as the current transistors that store the representation of a 0 or 1, the storage capacity has the potential to double.

File Transfer (Focus on wireless transmission)

File transfer speeds appear to have potential to increase with a ternary system. In the case of wireless transmissions, binary is generally preferred over analog due to its increased ability to maintain information integrity and is easier to distinguish when interference is present. The following diagram demonstrates this principle.

Image source: https://www.predig.com/whitepaper/reducing-signal-noise-practice

I imagine the implementation of ternary in wireless systems to appear like the following diagram (drawn quickly), having the peak and trough like a binary signal along with an ‘in-between’ to represent a 2. Having an ‘in-between’ might make the signal become less interference-tolerant than binary, which could be a disadvantage.

Thanks in advance for responses. Feel free to address unconsidered factors of why ternary may or may not be feasible and/or a beneficial alternative to the binary system.

EDIT: This question was flagged as a possible duplicate question. Keep in mind that an important aspect of this question is file transmission, which has been unaddressed in previous related ternary questions.


texts: How to compare distributed systems and big data

texts:
Are there scientific papers that compare distributed systems and big data processing systems?

Big data processing systems can be batch processing systems or streaming big data processing systems.

A batch big data system is a distributed system that:

loads data into the system from relational databases, log files or other sources (usually via Apache Sqoop)
makes some computations about that data: aggregations and machine learning algorithms to train existing models or to use some models that have already been trained (via Apache Pig or Apache Spark)
stores the result in some files or exports the data to a datawarehouse system or a relational database (using Apache Sqoop)

A streaming big data system is a distributed system that:

has a streaming mechanism that allows messages/events to be delievered to the system (usually Apache Kafka)
has an engine that makes elaborations on those messages, as before elaborations can include training machine learning models or using them (Apache Spark, or Apache Storm or Apache Flink)
stores the result of elaborations or exports that result to other systems (using Apache Kafka)

What I have found so far are a lot of scientific papers about distributed systems but they don't mention streaming systems; and a lot of papers mainly empirical or marketing-oriented about big data.

The worst thing is that often, articles about big data don't mention the fact that big data systems are part of distributed systems.

Is there some material about distributed systems that explains also the systems that I have described above?


texts:
The (optimization version of) Set Cover problem is the following: given a "universe" set $S$ and a collection of subsets $S_1, \cdots, S_m \subseteq S$, we want to find the minimum cardinality set of $k$ elements $\{i_1, \cdots, i_k\}$ such that $\bigcup_{i=1}^k S_{i_j} = S$.

It is a well-known result in an introductory approximation algorithms class that this problem has no $O(\log n)$-factor approximation unless $P = NP$.

However, I'm interested in a restricted version of the problem: suppose that $|S_i| = n$ for all $i$ (i.e., all the subsets are exactly the same size). This problem turns out to still be $NP$-complete, but is there a better approximation ratio one can achieve?

I don't know if there is terminology for the problem (I dubbed it "uniform" here), because searching through Google Scholar and the arXiv has not yielded much.


texts: Running time function for an algorithm with while and for loop

texts:
I have trouble determining the running time function for algorithm below. I know that there are initially two assignment operations, int i=n and int s=0.

Also, I know that the while loop is represented by $\lfloor \log_2n \rfloor + 1$, but the for loop depends on the value of $i$ which decrements by half.

So, the first time the for loop performs $n$ times, the second time the for loop performs $n/2$ times, and so on. How can I represent this behavior?

I suppose that, at the end, the result is the product of both behaviors.

int i = n; int s = 0;
while(i > 0) {
    for(j = 1; j <= i; ++j) s++;
    i /= 2;
}


texts: Why Can't Reverse Hashing Prove $P \neq NP$?

texts: Lets assume a hashing algorithm that runs in polynomial time and produces a hash that is mathematically impossible to reverse. As far as I know, the $P=NP$ problem states that if they are indeed equal, then if an algorithm exists to verify a solution in polynomial time, then an algorithm exists to find a solution in polynomial time. In this case, we can verify a solution by just running it through the hashing algorithm and comparing the final results. However, there cannot exist an algorithm to find a solution, since the hash is impossible to reverse.


texts: Why can't we prove decidability of $L= \{ \langle M \rangle : M$ accepts $ \epsilon \}$ with a configurations graph?

texts:
Since every deterministic Turing Machine can be translated to a graph of configurations such that $M$ accepts a word $w$ iff there is a path from the initial configuration that matches $w$ to an accept configuration, we can define a decider $D$ for $L$ such that:

$D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.

Though this seems simple and valid (to me), there is a well-known result showing that $L$ is undecidable. I can't figure out what is the flaw in the proof and will be happy for any help to figure it out


texts: Prove that following graph problem is in $L$

texts:
I have some interesting problem:

  Prove that following problem is in $L$ (decidable in logarythmic
  time).   Decide if given undirected graph $G=(\{1,\ldots,n\}, E)$ such
  that $\forall_{i,j\in \{1,\ldots,n\}} i\le j \to \operatorname{dist}(1, i) \le \operatorname{dist}(1,j)$.
  Graph is represented as adjacent matrix.

This is exercise that I can't deal with it. I know USTCON problem and I suppose that it may be useful (crucial) here. However, I can't solve it. Can anyone try to  help me defeat it ?


texts: Training a model based on polynomial regression and then putting that into a linear regression, vs just using the linear regression

texts: I'm doing some machine learning work in python with sklearn. Basically the problem is trying to predict how long an event will take based on 4 correlated pieces of data. What I've been doing is I have four polynomial regression trained on each piece of data respectively. Then I take the output of these polynomial regressions and train a linear regression based on that. Testing this against historically data has show that the two step process has about 10% less sum-squared-error than just using the linear regression. Should I not be doing it this way? What is the theory behind just using a one step process vs. using both steps?


texts: Exit quickly from a maze with a local view of the maze

texts:
How to efficiently exit from a maze where you know the initial position of the player (1,1), the exit (49,49)?
You don't know the maze configuration but you know where your player is, and which direction are opened from his position.
Another point, the player can move RIGHT/DOWN/LEFT/UP, and the exit is at the bottom right.
I tried to mainly follow RIGHT/DOWN and avoid dead ends, but I think we can do better!


texts: Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$

texts:
I have the following two functions

$f(n) = n\sqrt n + n \log n$
$\log_{100} n$

And I need to classify them into the followings:

$O(n)$, and/or
$O(n^2)$, and/or
$O(n^3)$, and/or
$O(n^{1.5})$, and/or
$\omega(n)$, and/or
$o(n\log n)$ (small o)
$\theta(n^{1.5})$,

Regarding the $\theta(n^{1.5})$, I am grasping it's idea newly, where do these functions set in. Also, does the function $f(n) =n^{0.9999}$ belong to $\theta(n^{1.5})$.

I would appreciate your feedback, as from your answers I am building up the knowledge for these.


texts: We can control tcp/udp traffic using router. Then why is it in Network layer and not transport layer?

texts:
Routers make use of the IP address, etc to shape the traffic. So obviously they must reside in at least the Network layer.
However we can also shape the traffic using tcp/udp. Routers usually have the port forwarding feature which allows them to shape the tcp/udp traffic.

The IP header has a field for protocol. However that doesn't show whether the traffic is udp/tcp. This information must be present inside the payload part of the IP packet. Then why is the router able to see that information despite being in the Network Layer?


texts:
Would it be possible to apply $(\lambda x.\lambda y. x)$ to the argument $y$? It seems to me that this must not be possible as it would give a different answer if applied to a constant, call it $\alpha$ and $y$. Namely:

$(\lambda x.\lambda y. x) \alpha = \alpha$

but

$(\lambda x.\lambda y. x)y = \lambda y.y$

I am afraid that I might be making considerable mistakes but this is only the case because I have been studying $\lambda$-calculus for just one day.

Thank you very much in advance for your comments and suggestions.


texts: Find Divisible Sum Pairs in an array in O(n) time

texts:
You are given an array of n integers a0, a1, .. an and a positive integer k. Find and print the number of pairs (i,j) where i<j and i+j is evenly divisible by k (Which is i+j % k == 0). This problem has been taken from Hackerrank.

We need a solution in O(n) time.

An explanation is that we can do this by separating elements into buckets depending on their mod k. For example, you have the elements: 1 3 2 6 4 5 9 and k = 3

mod 3 == 0 : 3 6 9
mod 3 == 1 : 1 4
mod 3 == 2 : 2 5

Now, you can make pairs like so:

  Elements with mod 3 == 0 will match with elements with (3 - 0) mod k =
  0, so other elements in the mod 3 == 0 list, like so: (3, 6) (3, 9)
  (6, 9)

Further:

  There will be n * (n - 1) / 2 such pairs, where n is length of the
  list, because the list is the same and i != j. Elements with mod 3 ==
  1 will match with elements with (3 - 1) mod k = 2, so elements in the
  mod 3 == 2 list, like so: (1, 2) (1, 5) (4, 2) (4, 5)

It makes sense that (3, 6) (3, 9) (6, 9) ( all items in the 0th bucket be paired) since (a + b)% k = 0 = a % k + b % k.

What isnt clear is how the other pairs (1, 2) (1, 5) (4, 2) (4, 5) were generated by combination of elements in the 1st (mod 3 == 1) and the 2nd (mod 3 == 2) bucket and why would there be n * (n - 1) / 2 pairs.


texts: Are there any techniques for checking whether a clause is subsumed by another clause when adding it to a cnf formula?

texts: When doing variable elimination on a formula in cnf form, there is created a lot of new clauses. Is there any efficient way to check if these are subsumed by other, already existing clauses?


texts: Dividing a set of goals among two search agents

texts:
Say we had two agents and we want them both to traverse a map concurrently.

Their goal is to collectively visit a collection of certain points on the map. If there was just one agent, it would be simple enough to just implement BFS or A* and get a good solution.

But considering there are two, how can we divide the points to be visited among the two agents in such a way that no steps (or minimal steps) are wasted in visiting all the points?

Edit/Clarification:

-The points do not need to be visited in a particular order.
-If there was only one agent, I could get a possible solution with a BFS or A* where the goal state is all the points having been visited.

Edit 2: Pictures

An example of the problem might be as seen below. Agents start at the top left of the maze and the goal is a state space where all the red dots have been visited.

A possible path that might be returned by BFS with a single agent:

What I would like to achieve with multiple agents:


texts: Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

texts:
A test is consisted of $N$ multiple choice questions, each has $k$ possible answers.

A test solution is the sequence of answers $S\in[k]^N$.

Given is a black box which receives a solution as input and returns the number of correct answers. After failing a test, the student may take the test again, and the questions do not change.

In order to pass the test, a student must have at least $m\le N$ correct answers.

What is the minimal number of attempts you need to make (as a function of $N,k$ and $m$) in order to be sure to pass the test, assuming you have no knowledge about the questions in hand?
Assuming you are allowed to use randomization, how can we minimize the expected number of attempts needed?

A trivial algorithm is to "guess" an initial solution $S_0$, and then change one answer at a time until you have $m$ correct ones. This results in $1+(k-1)\cdot m$ attempts at the worst case.

For the probabilistic part, it seems some kind of an experts algorithm could work here: pick a few random tests and then construct additional tests such that answers appearing in high-scoring solutions will get higher probability.


texts: Space complexity of breadth-first search

texts:
I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$
nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor.

Why isn't it $b^d$?

Why are $1+b+b^2+···+b^{d-1}$ (the previously searched depths) maintained in memory?

If it's a matter of completeness, then (a complete implementation of) DFS would suffer from the same problem.


texts: graph trend filtering results from different maxflow algorithm

texts:
We have followed the official code of the Graph trend filtering (GTF) https://arxiv.org/abs/1410.7690, and modified the code with Ford Fulkerson Algorithm (FFA) instead of parametric maxflow. The parametric maxflow and the FFA have the same residual capacities.

We also implemented the push-relabel algorithm, but the residual capacities are different from parametric maxflow or FFA. Can anyone with experience in GTF assure that the outputs of GTF are the same even though the residual capacities are different?


texts: Practical applications of multi-prover interactive proof protocols

texts:
A multi-prover interactive proof protocol, as described here, consists of computationally unbound provers $P_1,P_2,\ldots$ which together convince a polynomial-time verifier $V$ of some proposition, under the assumption that the provers can't communicate after some initial setup. Are there practical scenarios in which such a protocol would be useful?

The linked paper gives an example of a user inserting two bank cards into an ATM to prove their identity. I'm skeptical of this use case because:

It would be difficult to physically ensure fraudulent cards are unable to communicate.
Single-prover protocols (possibly relying on cryptographic assumptions) have been sufficient for this use case so far.
The bank cards are not computationally unbounded; presumably the ATM has at least as much computational power as the cards, and could just run the honest verifier algorithm itself.

Note: Point 3 would not apply if, rather than computationally unbound provers, we considered polynomial-time provers with access to a secret. Has that class of protocols been studied?

Note: The study of this class of decision problems may have theoretical value (example) but I'm not asking about that.


texts: Counting the number of multiples of number A that perfectly divides the number B

texts:
What is the best way of counting the number of multiples of number A that perfectly divides the number B.

This is the sub problem for one of the questions I am solving on codechef.
This is the best I could come up with.

int func(int A,int B){
    int res = 0;
    int i = 1;
    while(A * i <= B){
        if(!(B %(A * i))){
            res++;
        }
        i++;
    }
    return res;
}

However,this is timing out for some of the cases. I am told that this can solved in O(sqrt(n)). Any help would be appreciated.


texts: Universal lower semicomputable semimeasure and Coding Theorem

texts:
I'm following Li and Vitanyi's book "An introduction to Kolmogorov complexity and its applications" 3ed. I'll rewrite here the definitions I need for my question.

The authors define the reference universal lower semicomputable semimeasure as

$$ \textbf{M}(x) = \sum 2^{-K(\mu)} \mu(x) $$

where the sum goes over all lower semicomputable semimeasures. Moreover, they name $\lambda_U(x)$ the probability that the reference universal monotone machine $U$ computes a string that begins with $x$ when provided with coin-flip input.

Question 1: the authors claim that the two quantities above are equal, probably intending equality up to a multiplicative constant. It seems to me, however, that the multiplicative term is not constant but is only bounded. This seems to be confirmed by the fact that they state what should be a Coding theorem as
$$ -\log(\lambda_U(x)) = -\log(\textbf{M}(x)) + O(1)$$

Unfortunately they only sketch a proof, so it's not clear (to me at least) whether that $O(1)$ is actually a constant or not.
I would like to know whether equality (up to a multiplicative constant) actually holds, and in case, a reference to a proof would be appreciated.

Question 2: The authors claim $\textbf{M}$ is the probability that the reference universal monotone machine $U$ computes a string that begins with $x$ when provided with coin-flip input, but this interpretation is only allowed if equality (up to constant) holds among the two above quantities, otherwise I feel it is not legitimate. Am I wrong?


texts: Example for a non-trivial PCP verifier for an NP-complete problem

texts:
During my involvement in a course on dealing with NP-hard problems I have encountered the PCP theorem, stating

$\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$.

I understand the technical definition of a PCP verifier, so I know in principle what kind of algorithm has to exist for every NP problem: a randomised algorithm that checks $O(1)$ bits of the given certificate for the given input using $O(\log n)$ random bits, so that this algorithm is essentially a one-sided error Monte-Carlo verifier.

However, I have trouble imagining how such an algorithm can deal with an NP-complete problem. Short of reading the proof of the PCP theorem, are there concrete examples for such algorithms?

I skimmed the relevant sections of Computational Complexity: A Modern Approach by Arora and Barak (2009) but did not find any.

An example using a $\mathsf{PCP}(\_,\ll n)$ algorithm would be fine.


texts: How does this reduction to prove undecidability account for epsilon?

texts:
I have the following proof that the Empty String problem:
   ES = {M | M accepts $\epsilon$}
 is undecidable:

$f<M,w>$ = Construct a new machine $M_2$ such that:
$M_2$ = given input x erase x from the tape and run M on w:
if M accepts w $\longrightarrow$ accept
if M rejects w $\longrightarrow$ accept
if M loops on w $\longrightarrow$ loop

I see how the function only accepts when the halting problem accepts since it only accepts when M accepts/rejects (halts).  However I don't see how it only accepts when M accepts $\epsilon$ too.  If for example M rejects $\epsilon$ then $M_2$ would accept since M halted on w. Wouldn't this be a flaw in the reduction?  How does this reduction account for $\epsilon$?


texts: Find pixel mapping matrix with minimum iterations

texts:
The Situation
 I am an electronics engineer and on a volunteer team that have built a prototype eye that has 200*200 sensors that are mapped to the optic nerve, the connection to the optic nerve is random (organic connection is grown) so I need to have the patient draw what they see, I am trying to limit the number of drawings (difficult for a blind person) the patient has to do to get the relationship between the artificial eye output and the correct perception of the image.

The Problem
Given a input image/matrix and an viewable/readable output matrix, what is an algorithm to automatically identify the encoding  with the least number of iterations.

By changing the input one pixel at a time and then examining the output, the relationship can be discovered, this is, however, very inefficient.


texts: Hueristic Algorithm to find the maximum clique

texts:
Let the algorithm be defined as follows:

Consider the following heuristic algorithm for finding the maximum size clique
in a graph. (1). Delete from the graph a vertex that is not connected
to every other vertex. (2). Repeat (1) until the remaining graph is a clique.

Now, how do I show that this algorithm does not give a solution which is within constant times of the optimal solution?
I was reading about heuristic algorithms when I came across this problem. Any sort of input is appreciated.


texts: Construction of graph with given Wiener Index

texts: Given the sum of weights of shortest paths between all vertices in a graph, how can I construct a connected graph that satisfies the given sum? That is, how can a graph with a given wiener index be created?


texts: Which algorithm to use to find all common substring (LCS case) with really big strings

texts:
I'm looking for a particular case of longest common substring (LCS) problem. In my case I have two really big strings (tens or hundreds of milions byte characters) and need  to find the LCS and other long strings.

A simplified example

$S_0$ = ABBCADGGHEEASSSCC

$S_1$ = ABDCADGGHMEASSSAC

the LCS = CADGGH (6 chars) and other long strings with 5 chars are CADGG, ADGGH and EASSS.

Which is the fastest algorithm to get all substrings with its length? (list all substrigs and legths) And in my case (very big byte substrings) which is the fastest LCS algorithm? (only get longest common substrings).

NOTE: In particular I don't have any space limit now, but this algorithm may be implemented in a mobile device in a future and is possible to have a very limited RAM/disk space (but always, at least, I have the same disk space available as the sum of file lengths).


texts: DFS produces the correct Topologically ordered sequence

texts:
Prove that DFS produces the correct topologically ordered sequence.

I am having a hard time understanding the question itself. Should I prove the correctness of DFS? Should I use the pseudocode?


texts: Hyperplane through origin which goes through most number of points

texts:
Given $M$ points in $\mathbb{R}^{N}$ (where $M$ is larger than $N$), I was wondering if there is an algorithm to find a $N-1$-dimensional hyperplane which goes through the origin and also intersects as many points as possible.

Specifically, does there exist an algorithm which runs faster than $O(M^{N})$ time? This is achieved by looking at all subspaces defined by each subset of $N-1$ points.

Furthermore, if there is no faster exact algorithm, I was wondering if there are any constant factor approximations which run faster than $O(M^{N})$. It would be greatly appreciated if someone can point me to the correct papers or references for these.


texts: How is Dynamic programming different from Brute force

texts:
I was reading up on Dynamic Programming when I came across the following quote

  A dynamic programming algorithm will examine all possible ways to
  solve the problem and will pick the best solution. Therefore, we can
  roughly think of dynamic programming as an intelligent, brute-force
  method that enables us to go through all possible solutions to pick
  the best one. If the scope of the problem is such that going through
  all possible solutions is possible and fast enough, dynamic
  programming guarantees finding the optimal solution

The following example was given

  For example, let's say that you have to get from point A to point B as
  fast as possible, in a given city, during rush hour. A dynamic
  programming algorithm will look into the entire traffic report,
  looking into all possible combinations of roads you might take, and
  will only then tell you which way is the fastest. Of course, you might
  have to wait for a while until the algorithm finishes, and only then
  can you start driving. The path you will take will be the fastest one
  (assuming that nothing changed in the external environment)

Brute Force is trying every possible solution before deciding on the best solution .

How is Dynamic Programming different from Brute Force if it also goes through all possible solutions before picking the best one , the only difference i see is that Dynamic Programming takes into account the additional factors ( traffic conditions in this case).

Am  i correct to say that Dynamic Programming is a subset of Brute Force method ??


texts: Regarding time complexity of multi-tape Turing machines

texts:
So let's say I've implemented an algorithm running in $O(n^2)$ on my 3-tape TM. What kind of time complexity would I expect for a single-tape TM?

I just don't know where to get started...


texts: What is it called when two problems are similar?

texts:
Suppose that there are two problems $P$ and $Q$.

How can I say that "solving $P$ is same thing with solving $Q$"?

For instance, if $P$ is NP-Hard, then we can say "$P$ can be solved in polynomial time iff there exists an algorithm $A$ that solves $Q$ in polynomial time".

There should be a shorter term for this, and I'm sure that is not similar.

Is equivalent the right word?


texts: Regular expression vs rational expression

texts:
Let $M$ be a monoid (e.g. $M = \Sigma^*$) and $L \subseteq M$.
Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows:

$|L| < \infty \implies L \in \mathsf{RAT}(M)$
$L_1, L_2 \in \mathsf{RAT}(M) \implies L_1 \cup L_2 \in \mathsf{RAT}(M)$
$L_1, L_2 \in \mathsf{RAT}(M) \implies L_1 \cdot L_2 \in \mathsf{RAT}(M)$
$L \in \mathsf{RAT}(M) \implies L^\ast = \bigcup_{i \geq 0} L^i \in \mathsf{RAT}(M)$
with $L^0=\{1_m\}$ and $L^{i+1} = L^iL$

And in my understanding, a rational expression is then an expression using only the operations in this definition, i.e. $$L_1 \cup L_2 \cup L_3L_4 \cup L_3^*$$.
On the other hand we have the definition of regular languages where $\mathsf{REG(M)}$ is the set of regular sets inductivly defined as follows:

$\emptyset$ is a regular expression
$\epsilon $ is a regular expression
$a \in \Sigma$ is a regular expression
if $\alpha$ and $\beta$ are regular expressions, then $\alpha\mid\beta$ is a regular expression
$\alpha^*$ and $\alpha\beta$ are regular expressions

Futhermore we know that regular languages are closed under complement unlike rational languages.
Question:
It is often stated that regular expressions are the same as rational expressions. But hence this defintion of a rational expression doesn't allow for example "the decision"-operator, ($a \mid b$), it seems that regular expressions cover more than rational ones. What am I missing out? Are they really the same and if not, where are they distinct?


texts: A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?

texts:
First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS).
I) Vectors
A vector have a axiomatic meaning, i.e., given a set $\mathcal{A}$ of objects, their objects can be called vectors if and only if they satisfy the vector space axioms $[1]$. Of course that, 3D vectors (little arrows), function, matrices and so on are different objects, but under a well defined vector addition $\boxplus$, and scalar multiplication $\boxdot$ they are the same: Vectors!
Furthermore, I think that is impossible to talk about more complicated objects like Tensors without a vector space structure underlying the mathematical usage of CS objects.
II) My doubt
So, I would like to know: arrays, lists, strings are the same object as vectors? In other words, they satisfy the vector space axioms?
$$* * *$$
$[1]$ https://en.wikipedia.org/wiki/Vector_space#Definition


texts: Can we create binomial heaps in linear time?

texts: I'm studying binomial heaps in anticipation for my finals and the CLRS book tells me that insertion in a binomial heap takes $\Theta(\log n)$ time. So given an array of numbers it would take $\Theta(n\log n)$ time to convert it a a binomial heap. To me that seems a bit pessimistic and like a naive implementation. Does anyone know of a method/implementation that can convert an array of numbers to a binary heap in $\Theta(n)$ time?


texts:
I am to come up with a function based on these premise:

Give an example of a function which is $o(\log^k n)$ for any fixed $k$, but which is also $\omega(1)$.

The answer is the iterative logarithm $\log^* n$, and I want to show each of these steps.

1) show that $\log^* n \leq \log^{k+1} n$

2) show that $\log^{k+1} n = o(\log^k n)$

3) show that $\log^* n = \omega(1)$

I am stuck on mathematics behind these step because of my lack of knowledge of the iterated Logarithm. Can I ask for assistance at this?


texts: Class activation mapping using inception-v3 network

texts:
I am using the technique of this paper: https://arxiv.org/pdf/1604.07953.pdf
to localize food objects. The difference is that I am using the next generation of google-net, inception-v3 network. For the localization problem, in the paper they modify the network cutting the last 2 inception modules to receive 14x14 grid and by adding a conv-layer and a GAP they achieve precise localization of food. In my network, the inception modules are not 9 like google-net, but 10. I thought that cutting the last 3 inception modules to receive a 17x17 grid for the localization would result to similar localization but I have not achieved this yet. You think that's a good technique or I should modify the network in other way? An opinion from here would be very helpful to make the right experiments. Thanks!


texts: Chernoff bound when we only have upper bound of expectation

texts:
If $X$ is a sum of i.i.d. random variables taking values in $\{0,1\}$ and $E[X]=\mu$, the Chernoff bound tells us that

$$\Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}$$

for all $0<\delta<1$.

If $E[X]\leq\mu$ instead, does there exist a constant $c$ such that

$$\Pr(X\geq (1+\delta)\mu)\leq e^{-c\delta^2\mu}$$

for all $0<\delta<1$?

(This question is related, but the answer there doesn't help.)


texts: Why does the following function distribute things in a binomial distribution?

texts:
I was reading the following FDS paper:

https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf

and it says that the the following hash function does not distribute things uniformly (instead it creates a binomial distribution):

$$i = (hash(g + t)) \pmod n$$

while the following did distribute things uniformly:

$$i = (hash(g) + t) \pmod n$$

Why does the above distribute things evenly while the other one doesn't?

g = is the global UID for a blob

t = tract number. (tract is the measure/units of reads and writes to a blob).

n = is the number of tract servers or a multiple of the tract servers.

hash = SHA-1 (according to the paper)

Paper Reference:

Title: Flat Datacenter Storage

Author(s): Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Yutaka Suzue

Institution(s): Microsoft Research, Univeristy of Texas at Austin