texts: What are the reasons for and against using normalized floating point?

texts:
Floating point number formats can be normalized or not, meaning that ‘normal’ floating point numbers have an implicit (hidden) leading bit 1 in the significand. For example, the binary IEEE 754 formats are normalized, but the decimal IEEE 754 formats are not, i.e., they have an explicit leading bit (or number).

The advantage I see is the larger range or precision possible. (Larger range if compared to a format with one less exponent bit; greater precision if compared to a format with one less significand bit.)

However, the downsides I see are:

Dealing with a more complex format during computations, e.g., normalization steps, the existence of subnormals.
The loss of significance information. With, e.g., decimal IEEE 754 formats, the number of significand digits can be expressed. This would be a very useful feature, e.g., when encoding measurements. I would think that such information could also be exploited during computations.

On the whole, I feel that the larger range or greater precision that can be got with one extra bit does not justify the loss of a qualitative aspect, significance information. So my question is:

What are (other) reasons for or against using a normalized floating point format?

Perhaps the reason is historical and now the choice would be different; also this information is of interest to me. Perhaps the arguments I gave are not valid; it would then be interesting to know why.


texts: Is it possible to use machine learning to interpret a programming language and guess it's output

texts:
I know machine learning can make some predictions. With enough input data and example output data a machine can accept an image as input and determine that the image is likely a "flower" (output).

Could the same method apply to an interpretive programming language? Let's say Python for example. The inputs on every "line" of python would be existing memory and the new "line" of syntax. So if x = 2 (some data in ram as say CPython would set it instead of the actual syntax). Our new line of syntax is x + 2. The output is 4 (perhaps the updated ram state could also be considered an output). With enough sample input and output could a machine learning algorithm effectively "invent" it's own python interpreter? Perhaps our invented interpreter would determine there is a 98% chance that 2 + 2 results in 4.

A few people are asking why would anyone would want to do this. Curiosity mostly and certainly reading too much Godel, Escher, Bach. I think it's interesting because:

Perhaps it would find novel optimizations. Computers already find new strategies in chess. Why not interpreters or compilers?
The idea of a programming language interpreting syntax probabilistically, that doesn't even have to follow strict rules, is interesting. Can we go from 2 + 2 = 4 to 2 plus 2 equal four to Please add two and two.
Making a really horrible python interpreter would be funny.


texts:
I am just starting out learning code.

The output of the following code is OOOXOXOO, but I don't see how X can be printed twice. How does a=2 more than once?

a = 1
while a < 3:
    b = 1
    while b < 3:
        if a == 2:
            print ("X"),
        print ("O"),
        b = b + 1
    print ("O"),
    a = a + 1


texts: How can I find the strongest postcondition for those two Hoare triples?

texts:
I'm trying to solve an exercise in which I have to find the strongest post-condition of the two Hoare triples.

\begin{gather*}
    (| a=9 |)\ a=2; b=a+1; a=b*b;\ (| ?? |)\\
    (| i=-j |)\ i=i+1; j=j-1;\ (| ?? |)
\end{gather*}
For the first one, I found post condition as  $a > b$. For the second one, I found $j = |i|$. However, it seems like they are not the strongest. What are the strongest postconditions for those triples and why?


texts: Why is the halting problem decidable for LBA?

texts:
I have read in Wikipedia and some other texts that

  The halting problem is [...] decidable for linear bounded
  automata (LBAs) [and] deterministic machines with finite memory.

But earlier it is written that the halting problem is an undecidable problem and thus TM can't solve it! Since LBA are defined as a type of TM, should the same not hold for them?


texts: Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones


texts: Characterizing the range of a polytime function

texts:
Is it true that an infinite language is in P iff it is the range of a length increasing polytime function?  I ask because I know that it is a basic result in computability theory that a set is recursive iff it is the range of an increasing recursive function and I was wondering if there might be an analogue in complexity theory.

I know that the "length increasing" (or at least monotone increasing) is a necessary one because otherwise we could construct the Halting Problem:  Just have a polytime algorithm test computation histories for a given Turing machine $M$ on input $x$ and map valid halting ones to $(M,x)$.   I also know that every language in P reduces to any NP-complete language and these languages are not in P (unless of course P=NP), but I think my question might be different: I am interested in the exact image of a function over ${\Sigma}^{*}$ and not if it happens to be properly contained in an NP-complete set.  However, I don't know where to go from there. I would greatly appreciate any hints or counterexamples to demonstrate that my conjecture is false.  Thanks.


texts: Space complexity of using a pairwise independent hash family

texts:
I'm trying to analyze the space complexity of using the coloring function $f$ which appears in "Colorful Triangle Counting and a MapReduce Implementation", Pagh and Tsourakakis, 2011,  https://arxiv.org/abs/1103.6073.
As far as I understand, $f:[n] \rightarrow [N]$ is a hash function, that should be picked uniformly at random out of a pairwise independent hash functions family $H$. I have a few general questions:

Does the space complexity required by $f$ is affected by the fact that $H$ is $k$-wise independent? Why? (If it does, then also- how?)
What do we know about $|H|$? What if $H$ is $k$-wise independent?
Is there a more space-efficient way to store $f$ than storing an $N \times m$ matrix that maps each vertex to its color, using O($N m$) storage words?
Does the total space complexity which is required in order to use $f$ as described in the paper is $|H| \cdot O(\text{space complexity of storing } f)$?

Best regards


texts: PDA accepting all words not of the form $b^na^n$

texts:
I am studying Automata theory. DFAs and NFAs seem pretty straightforward to me, but I don't quite understand how to design push-down automata for context-free languages.
If I have context-free language where the
input  alphabet is $\{a,b\}$
$L = \{w \text{ where }w\text{ is NOT of the form }b^n a^n\}$
How would I design a push-down automata for it? What are the steps I would need to take, and what would it look like (formal description)?


texts: A regular expression for strings with at most one triple of adjacent zeroes

texts:
I am trying to come up with a regular expression for the following language:

  The set of all strings with at most one triple of adjacent 0s.

What does "triple of adjacent 0s" mean? Does it mean 010101, or something else?


texts: What method(s) can I use in general to proof HALT doesn't reduce to given language?


texts:
This is from betting domain which has something that is called a long list: a list of a "home team win/draw/away team win"  markets for 13 games.
A punter can select any combination of the possible outcomes which are encoded in a following way:

1 - home team wins
2 - draw
4 - away team wins
3 - home team wins or draw
5 - home team wins or away team wins
6 - draw or away team wins
7 - home team wins or draw or away team wins

Meaning a [3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7] represents a selection where punter put following bets:

"home team wins or draw" in a first game
"home team wins"  in games 2-12
"home team wins or draw or away team wins"  in 13th game

After games are finished there will be another 13 elements list representing winning outcomes, for example: [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] means that in a first game away team won and in all other games home team won.

The question is if I'm missing any properties within those numbers that will make finding a winning bets easier than comparing each number one by one? Like in our case case checking if there are bets that has 4,5, 6 or 7 for the first game and 1, 3, 5 or 7 for rest of them.


texts:
I am looking for a mathematical formula / algorithm to find the negation of a 8-bit hexadecimal without having to expand into a binary form.

E.g;

0000BDDA -> 48602

FFFF4226 -> -48602

Need to get from 0000BDDA -> FFFF4226 without 2' complements / expanding it to binary.

I've been cracking my head at it but to no avail.

Any ideas?


texts:
I have stumbled across this question about the Random restart algorithm in search problems:
Random restart is technique which used for:
a)algorithms for search in space state when they get stuck
b)algorithms for informed search for better solution
c)algorithms for uninformed search for better solution
d)algorithms for local search for better solution
My thoughts are : it's a) or d) but I cannot decide since random restart is used for local search but we don't need better solution, however I haven't found anywhere that random restart helps us getting unstuck?


texts: Given an algorithm, is it possible to find all other equivalent algorithms for the same computable function in the same model

texts:
For any computable-function, there may be multiple different algorithms (possibly countably infinite). For example, sort has many different implementations/algorithms, that we know of or that we have found so far. They all produce the same output for the same input.
Given any specific computable-function or even a specific instance of an algorithm/implementation (for any model of computation, functional in lambda calculus, imperative in turing machines, or any other) for it, is it possible to enumerate/find all other equivalent algorithms/implementations for that same computable-function, for the same model.
ie. If I have an algorithm or even a specification for sort, it is possible to find the other algorithms for sort?


texts:
I think the following question is a mix of the Traveling Salesman Problem and the Subset-sum Problem, which makes it really hard (for me) to solve... .
The problem is stated as follows:

There are a total of $n$ cities.
The salesman must start his journey at a certain city, and return to that specific city at the end of his tour.
Whenever the salesman reaches a city he hasn't been to, he can earn $r_i$ dollars there. $r$ is a positive real number, and $i$ denotes the city number.
The salesman can visit the same city more than once, but he cannot earn extra cash there.
The salesman does not have to visit every city.
By traveling from city $i$ to city $j$, a cost of $f_{ij}$ is incurred everytime. $f_{ij}$ is a positive real number. (This is like a negative weighted edge.)
The problem asks whether there exists a route for the salesman to earn a net revenue of at least $k$ dollars.

This problem is clearly in NP, but how should I prove that it is NP-complete?
Since the salesman can wonder around the same cities, can I still map this question to the 3-SAT problem (like the subset-sum case) and prove that it is NPC?
Many thanks.


texts: brute-force canonical labelling of a simple graph

texts: I am looking for an example that shows how to canonically label a graph using brute-force approach. An example with a 3 vertex or 4 vertex simple graph is preferred.


texts:
We have the following

i <- 0
j <- 0
x <- 1
y <- 1
z <- 1
c <- 1
u <- 1
while i<n do
   i <- i+1
   j <- i
   x <- x*i
   z <- x
   y <- i+1
   y <- x*y
   while j<2*i do
      j <- j+1
      z <- z*j
   od
   c <- z div (x*y)
od

I want to find the loop invariant for both while-loops.

I applied the algorithm some times to understand what it does:

The inner while loop calculates the following: $$z=z\prod_{m=1}^{2i-1}(i+m)=x\prod_{m=1}^{2i-1}(i+m)$$ or not? Is this also the loop invariant of the inner while loop?

So I got the following results:

First loop:

i=1
j=i=1
x=1
z=x=1
y=i+1=2
y=x*y=2
inner while loop: z=x(i+1)=2
c = z div (x*y) = 2 div 2 = 1

Second loop:

i=2
j=i=2
x=1*2=2
z=x=2
y=i+1=3
y=x*y=2*3=6
inner while loop: z=x(i+1)(i+2)(i+3)=2*3*4*5
c = z div (x*y) = 2*3*4*5/2*6=10

Third loop:

i=3
j=i=3
x=2*3=6
z=x=6
y=i+1=4
y=x*y=24
inner while loop: z=x(i+1)(i+2)(i+3)(i+4)(i+5)=6*4*5*6*7*8
c = z div (x*y) = 6*4*5*6*7*8/6*24=5*7*8=280

Is everything correct? But what exactly calculates the algorithm? What is a general formula of the results?


texts: Is it possible to use plants as a medium to store data? By what data structure?

texts:
my question is simple.
Is it possible to use plants as a medium to store data?

My opinion is: Possible, but we need to solve, how to distinguish 2 states.
Duplication and CRC of stored DATA is quiet simple. Growing new plants is easiest possibility, but we need to create unit, which will take care about raid and duplicating informations between all plants.

Could there be a different data-structure? What is a potential of storing data into plants? What about security? How would you write data into plants without losing that information?

No, this is not a joke. Think about it. It grows everywhere, it is protected against water, cold, wet, dry, magnetic field, shaking and so on.

Try to remember, you can use your own garden as a datastore for your music, films and data. Or just use public garden to share media, photographs, messages or opinions by connecting remotely to plants.


texts: Finding the $k$th largest element in an unsorted array

texts: What is the complexity of finding the k'th largest element in an unsorted linked list? If we sort the list, I think that the complexity is O(nlogn + k)=O(nlogn) since k < n. Is there a way of finding the kth largest element without sorting the list?


texts:
I have two arrays, X and H, where X is sorted. X[i] represents the coordinate of building i. Y[i] represents the height of building i. If building i collapses, all buildings in the interval [ X[i]+1, X[i]+H[i] ], both ends inclusive, will collapse, too. Those collapsed building may cause more buildings to collapse and so on, just like a domino effect. For each building, we want to find its range of effect, represented by the largest coordinate that will be affected.

Example

X = {5 6 9 11}

H = {2 3 1  5}

ans = {10 10 10 16}

Explanation: the collapse of building 0 will cause building 1 to collapse since 6 is in [5+1, 5+2]. The collapse of building 1 will cause building 2 to collapse since 9 is in [6+1, 6+3]. Finally, building 2 will affect [9+1, 9+1], which does not contain 11, the coordinate of building 3. So the range for building 0, 1 or 2 is 9+1=10. The range of building 3 is 11+5=16.


texts: Prove correctness of recursive Fibonacci algorithm, using proof by induction

texts:
I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction.

Here is my recursive version of an algorithm to compute Fibonacci numbers:

Fibonacci(n):
    if n = 0 then     // base case
        return 0
    elseif n = 1 then // base case
        return 1
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2)
    endif

How can I prove the correctness of this algorithm by induction?


texts: Reducing the Hamiltonian Cycle problem to the problem of finding a $m$-length Hamiltonian Cycle

texts:
I was working through some exercises regarding NP complexity, when I came across this one:

Let $mH$ be the problem of finding a Hamiltonian cycle of length $m$ ($m$ fixed) in a graph $G$. A cycle of length $m$ is a sequence of nodes $e_1,e_2,\ldots e_m$ with the property that they form a Hamiltonian cycle. Show that the problem is in NP, by reducing the Hamiltonian Cycle ($H$) problem for an arbitrary graph $G$ to $mH$. In other words show $H\leq_p mH$.

In the original formulation $m$ was a constant value.
I understand how the proof structure works, but currently I am stuck at finding a way to "adapt" a graph $G$ into a graph $G'$ which can be decided by finding an Hamiltonian cycle of length $m$.
I tried to work on some simple examples but I did not succeed in finding an approach.
I would appreciate a hint about how to proceed.


texts: is it possible to reduce $HALT_{TM}$ to $E_{TM}$?

texts:
I am wondering, if it is even possible: is it possible to reduce $HALT_{\text{TM}}$ to $E_{\text{TM}}$?

$HALT_{\text{TM}}=\{\langle M,w\rangle\mid M\text{ is a }TM\text{ and }M\text{ halts on input }w\}$

$E_{\text{TM}} =\{\langle M\rangle\mid M\text{ is a TM and } L\left(M\right)=\emptyset \}$

I tried to look online, in summaries and handouts and even in several books (including Sipser's book), but couldn't find any indication on it.

is it possible? if so, how?


texts:
I searched the exchange and couldn't seem to find an answer to this.

I am trying to find an algorithm that, given a directed acyclic graph (DAG) $G = (N,E)$ with a single root node $r\in N$, finds all connected subgraphs $G_i\subseteq G$ that contain r.

What I've attempted so far

Consider the following DAG,

To start, we have the graph:

$(\{1\},\varnothing)$

From the root, we should do a one-step search, including $m$ nodes, where $m$ ranges from $1$ to the number of children (of the root), in each subgraph. That is, the next set of subgraphs are:

$(\{1,2\},\{(1,2)\})$

$(\{1,3\},\{(1,3)\})$

$(\{1,4\},\{(1,4)\})$

$(\{1,2,3\},\{(1,2),(1,3)\})$

$(\{1,2,4\},\{(1,2),(1,4)\})$

$(\{1,3,4\},\{(1,3),(1,4)\})$

$(\{1,2,3,4\},\{(1,2),(1,3),(1,4)\})$

For each one of the above subgraphs, should we just do another one-step search?

Questions

Does anyone know of a better algorithm for recursively counting all of the subgraphs? I'm now aware that there is likely no polynomial-time algorithm (thanks to Raphael's comment) and such an algorithm may have exponential complexity in the worst-case.


texts: How to describe the language generated by S → a | S + S | S S | S * | ( S )

texts:
I am trying to solve the following problem from Aho, et al., Compilers: Principles, Techniques, & Tools (2nd ed.), exercise 2.2.2e:

  What language is generated by the following grammar? $S\rightarrow\textbf{a | }S\textbf{ + }S\textbf{ | }S\textbf{ }S\textbf{ | }S\textbf{ * | ( }S\textbf{ )}$

This looks like some combination of infix addition and postfix star operator, along with parenthesis, but I am not sure how to describe this in a clear fashion.


texts: How do Hard Drives Send and Recieve Data?

texts:
Ok. I know this is probably a commonly asked question. Before you refer me to a site or answer this yourself, I ask for you to please read this through. I have been into computers and electronics for quite a while. I have a pretty good understanding of electronics, and would like to become a computer hardware engineer eventually. For quite a while now, I have been searching for an answer to my question: How to hard drives send and recieve data, and in general, how do they work? Every site I find, simply explains the basics, of which I already am quite familiar with.

An example of what I am trying to figure out: Suppose you want to save a very small file (less than 1KB for simplicity) to a hard drive. Is there a site that explains exactly what information is exchanged between the hard drive and the rest of the computer? I would like to understand what is sent, and when it is sent ( down to ones and zeros ). I would eventually like to know enough information that, in theory, I could build a small storage device compatible with a modern computer. The more information, the better.


texts: If $L$ is recursive then so is $L^*$, and vice versa

texts:
Given a language $L$ over the alphabet $\{0,1\}$. Let $L^*= \{ w_1w_2...w_n | n \ge 0, w_1,...,w_n \in L\}$.

Prove:

If $L$ is recursive, then $L^*$ is recursive as well.
If $L^*$ is recursive, then $L$ is recursive as well.

For the first proof I have this idea:
If $L$ is recursive, then a turing machine $M_L$ can decide all the words $\{w|w \in L\}$. So $M_L$ can decide $\{w_1,...,w_n | w_1w_2...w_n \in L^*\}$ and appearently it can decide $L^*$ as well.

For the second proof I tried the same but actually it does not work that way. Any hints and ideas?


texts: Time Complexity analysis for Map-Reduce model

texts:
I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms.

As a simple example, taking average of n (= 1 billion) numbers can be done on O(n) + C (assuming division to be constant time operation). If i break this massively parallelizable algorithm for Map Reduce, by dividing data over k nodes, my time complexity would simply become O(n/k) + C + C'. Here, C' can be assumed as the startup job planning time overhead. Note that there was no shuffling involved, and reducer's job was nearly trivial.

I am interested in a more complete analysis of algorithm with iterative loops over data and involve heavy shuffling and reducer operations. I want to incorporate, if possible, the I/O operations and network transfers of data.


texts: What is the system's mean time to failure?

texts:
I have the following homework problem:

A 10 TB disk drive has an MTTF of 6,000,000 hours.  How much data can we store in a system comprised of these disks, if we want the system MTTF to be at least 1.2M hours?
If we are allowed to make it redundant (i.e., two of them operating in a parallel mode), and if the MTTR is 120 hours, what is the system MTTF?

I think it is
$\qquad \operatorname{MTTF}(\text{System}) = \frac{1}{\sum_i \frac{1}{\operatorname{MTTF}_i}}$.


texts: Why is the tape not part of the definition of a Turing Machine?

texts:
I've wondered why the tape/tapes are not part of the formal definition of a Turing Machine.  Consider, for example, the formal definition of a Turing machine on Wikipedia page.  The definition, following Hopcroft and Ullman, includes: the finite set of states $Q$, the tape alphabet $\Gamma$, the blank symbol $b \in \Gamma$, the initial state $q_0\in Q$, the set of final states $F\subseteq Q$, and the the transition function $\delta:(Q\backslash F)\times \Gamma\rightarrow Q\times\Gamma\times\{L,R\}$.  None of which is the tape itself.

A Turing Machine is always considered to work on a tape, and the transition function is interpreted as moving its head, substitution of symbol and changing state. So, why is the tape left out of the mathematical definition of a Turing machine?

From what I can see, the formal definition in itself doesn't seem to imply that the Turing Machine operates like it's often described informally (with a head moving around on a tape).  Or does it?


texts:
In operating systems, Is a transaction a process? Are they the same
concept?
Does a transaction have the same meaning in database management
systems, as in OS?

A database book says

  A transaction is defined as any one execution of a user program in a DBMS and differs from an execution of a program outside the DBMS
  (e.g., a C program executing on Unix) in important ways. "

  a transaction is an execution of a user program, seen by the DBMS as a series of read and write operations.

In OS, a running program = a process, isn't it?
Is there some theory about transactions, or is there math theory
underlying transaction management?

Thanks!


texts: Is the language of Turing Machine encodings decidable is this instance?

texts:
I have an exercise question as follows:
L is a set of all Turing Machine encodings for which the Turing Machine halts after a number of steps less than or equal to the minimum value among |w| and 1000, where w is the input to the machine
I understand from my textbook that the problem of halting before 1000 steps is decidable, however, with the introduction of the length of w I believe that L is undecidable. How would I go about showing this?


texts:
I have an adjacency matrix, call it A, representing a directed graph. I want to find all paths of length k. I know that A^k gives me the number of paths of length k between i and j, for each entry (i, j). But I want to know the actual edges in these k-length paths.

What's the best way to find all k-length paths in my graph? I read somewhere that exhaustive search on the adjacency matrix is the best way—but if so, how exactly to go about this?


texts: How to find the closest N to the power of X to the given number?

texts:
Let's say we have number 4920 and we want to find the closest $n^x$ to 4920

2 ^ 12 = 4096 but it's not the closest possible $n^x$, for example 17 ^ 3 = 4913 is closer to 4920

The question is, how do we find the closest $n^x$, where $n$ and $x$ are less than 2 digits long? (because $4913^1$ is not what I want)


texts: Estimating time cost for sorting algorithm given the average time for sorting of 1000 elements

texts:
Assuming that an implementation of a sorting algorithm takes 0,01 seconds to sort 1000 elements, how long would it take to sort 100 million elements?

What do I need to know about my the algorithm to estimate the time? Is its time complexity given in $\mathcal{O}$-notation sufficient to find that out?

In my example the algorithm is Bubblesort, of which I know that it is extremely inefficient for sorting long lists and I also know that the average case is $\mathcal{O(n^2)}$, however I am unsure how much depends on the concrete implementation, which is not given. I also am interested in the general approach towards the problem.

My train of though is that since Bubblesort is $\mathcal{O(n^2)}$ in the average case, the time cost is $c\cdot n^2$ for some constant time cost of an elementary operation $c$ (can I even assume that it is constant?).
So $c \cdot 1000^2=0,01 \iff c=10^{-8}$, which would instantly give me acces for time cost for any list length $n$. I am aware that $\mathcal{O(n^2)}$ does not mean that $n^2$ is the only factor in the cost equation, but it is the leading one as $n$ grows. Is this the correct approach?


texts: Can a 600 MB text file with digits of the square root of 2 be compressed to 600 KB?

texts:
I have a simple script to calculate gaps in a sequence of digits of the square root of 2 (or any other multi-precision constant).
As input, I generated files with the bigfloat module in Python:
from bigfloat import sqrt, precision

MAX_PRECISION_BITS: int = 1 << 30
CONSTANT = 2

precision_bits: int = 8
while precision_bits < MAX_PRECISION_BITS:
    with open(f"input/square_root_of_{CONSTANT}_with_{precision_bits}_bits.txt", 'w') as fd:
        fd.write(str(sqrt(CONSTANT, precision(precision_bits))))
        fd.flush()
    precision_bits *= 2

Although I can run the script any time, I decided to compress the input files, and I was surprised that a 646.5 MB got compressed to 632 KB, ie less than 1 MB! This value was obtained with the standard Zip method that is available in Mac OS X. I performed a diff command in the original and expanded file to check for possible differences and none was found.
I understand that every decimal digit takes about 3.32 bits, and the square root of 2  is conjectured to be normal, so I was expecting a compression to 40% or so.
How is this compression attained?


texts: That time does it mean? Is it a polynomial time?

texts:
I was reading an article and I saw this one:
'under the Exponential Time Hypothesis, Split Contraction cannot be solved in time $2^{o(l^{2})}\cdot n^{O(1)}$ where $l$ is the vertex cover number of the input graph'.

And next. 'it is easy to see that Split Contraction can be solved in time $2^{O(n\log n)}$'.

Could you please tell me what are these times? What are its name?


texts: How does one find a non-quadratic residue modulo $p$?

texts:
I was wondering how one can find a non-quadratic residue modulo $p$ and what the runtime of this algorithm would be.

I thought that one can use the Legendre Symbol

$$ \left( \frac{a}{p} \right) = a^{ \frac{(p-1)}{2} } \pmod p $$

if the Legendre Symbol returns -1 then its a non quadratic residue and if its a quadratic residue it would return 1. To do this it's easy find a randomized algorithm, since only half the elements are quadratic residues, then one guesses any element at random, say $a \in Z^*_p$ and if the Legendre Symbol returns -1 the return success. Since half the elements are not quadratic residues, it would take about 2 iterations in expectation to find one.

I was wondering, is this algorithm correct? It seems that its completely symmetrical for finding quadratic residues. I am not sure that is strange, but it seems weird to me. Is it correct that the two algorithms are basically the same?


texts: Find a diffrent minimal spanning tree for a graph

texts:
For my homework I have a problem that I can't solve and it makes me wonder about 2 different MST:

Let $G=(V,E)$ be a graph that has a minimum spanning tree $T$.
I want to find another minimum spanning tree $T'$ that has at least 1 different edge $e'$
such that the weight of $e'$ is differ from any weight of edges in $T$.

If $T'$ doesn't exist I can claim that every 2 different MST must have the same weight for each edge.
My intuition says that this claim is wrong but on the other hand I can't find example of $T'$ to contradict this claim.


texts:
I would like a way to hide a piece of information from Alice and Bob. Let's say this piece of information lets Alice and Bob vote me off the island. If Alice had this information she could vote me off even if Bob did not want that. Likewise if Bob had this information he could vote me off the island even if Alice did not want that. However I'd like Alice and Bob to be able to vote me off the island if they both agree that its in their interest. So I'd like to give Alice and Bob a piece of information such that they can combine that information to vote me off the island.

One very simple method I thought of was to encrypt the information. Give the encrypted information to them. And give them each half the key that I encrypted that infomation with. I wasn't however sure how secure this was or what problems there might be with it. Additionally this is (deliberately) just like some of the naively proposed methods by which back doors might be added to encryption. I'm trying to consider what is wrong with this from a mathematical stand point. So does this method have some known theoretical issue (not issues in practice)? Is there an efficient algorithm that attacks it? If this method is a bad method then is there a good method? If not then is it possible for there to be a good method?


texts: What is the number of degrees of freedom of my problem in this Simulated Annealing context?

texts:
I'm trying to apply a Simulated Annealing technique to solve my (NP-complete) optimization problem. I'm using this book to help myself out.

In the section on Simulated Annealing and more specifically in the section on practical suggestions for beginners, the authors state:

  Change in temperature stage: can take place as soon as one of the 2 following conditions is satisfied during the temperature stages:
  - $ 12 \cdot N$ pertubations accepted;
  - $ 100 \cdot N$ pertubations attempted,
  $N$ indicating the number of degrees of freedom (or parameters) of the problem

Because I'm still relatively new to Simulated Annealing, I'm willing to trust this guideline blindly for a first implementation.

A (non-optimal) solution to the problem is represented by a vector of integers $\mathbf{[a_1, a_2, a_3, ..., a_n]}$ with $ 0 < a_i \leq f(i), \forall i \in \mathbb{N} : 0 < i \leq n$.

What is the degree of freedom ($N$) here? Is it $n$?

Additionally, for this not to be a yes/no question:
Intuitively, why is this a bad/mediocre/good (pick one) guideline  ?
(i.e. why $\underline{12} \cdot N$ and $\underline{100} \cdot N$?)


texts: How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs?

texts:
As in I don't know what is the difference between say the conferences SODA, STOC or FOCS. Measured in terms of such conferences, where would such a result be publishable?

This is not a "technical" question.
I want to understand how importantly does the community view this question if hypothetically someone does this.

May be you can just comment and not write an "answer"


texts: Question for "Only if" part for the theorem "A language is Turing-recognizable iff some enumerator enumerates it."

texts:
I am trying to prove the theorem

  A language is Turing-recognizable iff some enumerator enumerates it.

I proved the "if" part, but I have no idea of proving the "only if" part, so I searched a proof for the "only if" part of this theorem. In the proof that I found,  it says

  Let $\sum$ be the alphabet of the Turing machine $M$, and let $s_1$, $s_2$, ... be a list of all possible strings of $\sum^{*}$. We define the enumerator $E$ as follows:
  1. Run $M$ for $i$ steps on each input $s_1$, $s_2$, ... , $s_i$.
  2. If any computation of $M$ accepts, print out the accepted string.

In this proof, I can't understand why do we need to run $M$ for only $i$ steps. I think the number of simulation steps may not be enough to simulate strings. Is it guaranteed that simulating $M$ finishes in $i$ steps?


texts: Presentation of context rules for the lambda-calculus

texts:
Reading Chris Hankin's book, "An Introduction to Lambda Calculus for Computer Scientists", I learnt that the rules for reductions in the pure  $\lambda$-Calculus are the $\beta$-reduction rule,
$$(\lambda x.M)N = M[x:= N]$$
and also these:
$$\frac{M=N}{N=M}$$
$$\frac{M=N}{MZ=NZ}$$
$$\frac{M=N}{ZM=ZN}$$
$$\frac{M=N}{\lambda x.M = \lambda x.N}$$
The author calls this "The Theory $\lambda$"; and although he formally defines contexts, he does not use them there.

Now, some other works -- for example, Didier Rémy's "Type Systems for Programming languages" -- seem to imply that there are only the $\beta$-reduction rule, and a context-rule:
$$(\lambda x.a)v \to a[x:= v]$$
$$\frac{a\to a'}{e[a]\to e[a']}$$
Here $e[]$ is an evaluation context, "$a$" is an arbitrary term, and "$v$" is a value (which the author defines to be an abstraction -- variables, he says, are not values).

I am a bit confused. I think (but I'd need confirmation) that they are saying the same thing, but Rémy's approach actually allows for the specification of evaluation strategy (because I can then decide if the context hole will be to the left or to the right, etc), while the presentation by Hankin does not.

Is this correct, or did I completely miss the point?


texts: I´m having problems with this Context Free Grammar

texts:
I am not able to convert the following language to a Context Free Grammar. The major problem is how to pump both "sides" of the word to obtain same number of 0s and 1s, but, without creating a series of 01010101.

$$L=\{0^{r_1}1^{s_1}0^{s_2}1^{r_2}\mid r_1+r_2 = s_1 + s_2,\ \ r_1,r_2,s_1,s_2 > 0\}$$

Can someone explain a solution to me?


texts: Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.


texts: How, in hardware, MIPS can access a word in the middle of an address

texts:
This is am example of a RAM address in the MIPS architecture (32 bits)

I can imagine the RAM as having 32 pins just to inform the RAM address I want to access, so I can access each of these words in the image (because I saw in this vídeo). I think, then, it should need another 32 pins to inform what's the word in that address, just like in the vídeo. I don't know, however, how the CPU could support 2 different 32 pins bus (but this is another problem).

What I don't understand, for real, is why I need and offset in the instruction "load word", if I can only access one address at the time! What if I say "load word", give the address number 2, and then say na offset of 4? It will load part of the word from the address 2, and part from the address 3? How is this possible?


texts: The Most efficient algorithm for a program that returns true if the two strings only differ by one character

texts:
We have a list of strings with the same length. Each string only contains a, b and c.(For instance : aabcc)
The program gets a string and returns true if the two strings(input and the list of strings) only differ by one character.
A = {cacab cbabc}
cbbaa : False
cbaac : True

My first thought was to solve it with brute force which the worst-case time complexity is O(n^2). Is there any way to solve it with hash table or any other data structure?


texts: An instance when you can eliminate propositional double negation in coq

texts:
Suppose st: string -> nat and X stands for the string 'X'.

Given the hypothesis not(st X <> 0), I can successfully derive

assert (st X = 0). { omega. }

But in Coq's constructive logic, a proposition of the form (P -> False) -> False does not in general imply P.

I imagine the fact that st is a function enables one to prove the above theorem.
If this is the case, then how does the omega tactic use this fact in the proof?

Though I am aware that omega is an implementation of a certain decision procedure for a weak form of arithmetic, I know almost nothing about how it works.

I am just looking for a general explanation. There's no need for many details.


texts: How a range query works on a simple B+tree

texts:
Given a B+tree indexing scheme, wondering how a database actually goes and finds records matching a range query such as the following:

CREATE TABLE foo (
  x int,
  y int
)

SELECT * FROM foo
  WHERE x > 10 AND x < 100
    AND y > 20 AND y < 200

From my understanding this would require 2 b+trees, one for each property ($x$ and $y$). Wondering if one could describe how it would go about about querying the different indexes to satisfy this query. I am having difficulty understanding how the B+tree works in practice.


texts: How do I calculate response time of a multiple core cpu when given certain information?

texts:
On my homework the question asks:

  A program executes serially in 200 seconds. If it is parallelized, 7
  seconds of overhead are required for synchronization, locking, and
  communication. Compute the execution time, ideal speedup (if there
  were no overhead required), actual speedup, and the percentage of the
  ideal speedup that is obtained for 1, 2, 4, 8, 16, 32, 64, and 128
  processors.

How do I calculate the answer to this? It is not something that has been covered in class yet and the homework is due before the next time the class meets.

My guess is that I divide 200 seconds by the number of cores and then add 7 * # cores to get the total response time. I don't think it is that simple.

Edit:
Amdahl's law says: T(n) = T(1)[B + 1/n(1-B)] where B is the percentage of the algorithm that is not parallelized and n is the number of cores. If I assume that the 7 seconds mentioned is the part of the algorithm that is not parallelized, I can get the percentage by saying:

      7sec * n
B  =  --------
       200sec

Then I plug the value for B into Amdahl's equation. Coencidentally, this gives me  the same answers as I got before when I did my own formula:

 200
 ---  +  [7 * (n - 1)]
  n

After doing a little bit of algebra, I discovered that my formula is a simplified version of Amdahl's formula. Of course all of this assumes I am correct when I read the question as if the 7 seconds are the part of the algorithm that is not parallelized.

Thanks for looking,

Zach


texts: Is there a machine or algorithm available to solve the board game "Chinese checkers"? If there is please let me know about relevant material. I have already searched over internet unfortunately i am unable to have relevant details about it.


texts: DFA for language of all strings avoiding 'aa'

texts:
I'm trying to draw a dfa for this description

The set of strings over {a, b, c} that do not contain the substring aa,

current issue i'm facing is how many states to start with, any help how to approach this problem?


texts:
This question is asked during a class of Computer Science.

  What is the transitive and reflective closure of the derivation
  relationship?

I know that if $R$ is a relationship on $A^2$, a transitivive and reflective relation on $R$ is the following $R^*$

$$R^* = R^+ \cup \{<x,x> \mid x \in A\}$$

but I don't now how to apply it to the concept of derivation


texts: How do I check if two if-stmt blocks are the same?

texts:
Consider the following two snipets of code:

If a >= 5:
   If b == 0:
     ....
   Else:
     ....
Else if a <= 5:
   ....

If a > 5:
   ....
Else If a >= 5 and b == 0:
   ....
Else If a >= 5:
   ....

Then these two constructs are logically equivalent. I am interested if there algorithms that detects if two or more constructs are the same. Papers in this field are also welcome.


texts: Can anyone tell me why this search parition for quicksort works?

texts:
private static < T extends Comparable < ?super T >> int partition(T[] a, int first, int last) {
  int mid = (first + last) / 2;
  sortFirstMiddleLast(a, first, mid, last);

  swap(a, mid, last - 1);
  int pivotIndex = last - 1;
  T pivot = a[pivotIndex];

  int indexFromLeft = first + 1;
  int indexFromRight = last - 2;
  boolean done = false;
  while (!done) {

    while (a[indexFromLeft].compareTo(pivot) < 0)
    indexFromLeft++;

    while (a[indexFromRight].compareTo(pivot) > 0)
    indexFromRight--;

    if (indexFromLeft < indexFromRight) {
      swap(a, indexFromLeft, indexFromRight);
      indexFromLeft++;
      indexFromRight--;
    }
    else done = true;
  }
  swap(a, pivotIndex, indexFromLeft);
  pivotIndex = indexFromLeft;

  return pivotIndex;
}

It doesn't seem to touch the first or last elements


texts: Linearithmic solution to finding closest pairs in an array of N elements

texts:
I am reading Algorithms 4ed by Sedgewick and Wayne. I came across this algorithm design question that asks the following:

Write a program that given an array of N integers, finds a closest pair: two values whose difference is no greater than the difference of any other pair (in absolute value). The running time of the program should be linearithmic in the worst case.

I wrote an implementation of this algorithm in javascript and ran a few tests. So far, it looks like the algorithm is correct and also linearithmic. But, I am not very good at proving correctness of algorithms or, in analyzing their time complexity (ammortized). If anyone can help me answer the following it would be great:

Is the algorithm (added later) correct?
Is the amortized time complexity linearithmic (i.e., N*lgN)?

The algorithm is given below:

function binarySearch(key, start, arr) {
    let a = arr[start-1]; // start >= 1
    let b = arr[start];
    let lo = start+1;
    let hi = arr.length-1;
    let getMid = () => Math.floor((lo+hi)/2);
    let getDiff = (a, b) => Math.abs(a-b);

    let mid;
    let diff;
    let ldiff = getDiff(a, b);
    let hidx = start;
    while(lo < hi) {
        mid = getMid();
        diff = getDiff(a, arr[mid]);
        if(diff < ldiff) {
            ldiff = diff;
            hidx = mid;
            hi = mid-1;
        }
        else {
            lo = mid+1;
        }
    }
    return { highIndex: hidx, leastDiff: ldiff };
}

function closestPair(arr) {
    // returns the nearest, closest pair
    let ldiff = null;
    let hidx;
    let lidx;
    for(let i=0; i<arr.length-1; ++i) {
        let { highIndex, leastDiff } = binarySearch(ldiff, i+1, arr);
        console.log(`hi=${highIndex} low=${i} ld=${leastDiff}`);
        if(ldiff === null || leastDiff < ldiff) {
            ldiff = leastDiff;
            hidx = highIndex;
            lidx = i;
        }
    }
    if(ldiff !== null && lidx !== null && hidx !== null) {
        return { leastDiff: ldiff, lowIndex: lidx, highIndex: hidx };
    }
    else null;
}

To test the algorithm, I had the following tests setup:

if(!module.parent) {
    let arrs = [
        [1, 7, 13, 5, 19, 27, 20, 39, 40], // 2; 19-20/39-40
        [3, 2, 10, 6, 9, 5],
        [-2, 9, 5, 25, 13, -10, -25]
    ];
    for(let arr of arrs) {
        let s = arr.sort(ascComparator);
        console.log(`sorted arr: ${s.toString()}`);
        let cp = closestPair(s);
        console.log(cp);
    }
}

The output on the console for running the tests were as follows:

sorted arr: 1,5,7,13,19,20,27,39,40
hi=1 low=0 ld=4
hi=2 low=1 ld=2
hi=3 low=2 ld=6
hi=4 low=3 ld=6
hi=5 low=4 ld=1
hi=6 low=5 ld=7
hi=7 low=6 ld=12
hi=8 low=7 ld=1
{ leastDiff: 1, lowIndex: 4, highIndex: 5 }
sorted arr: 2,3,5,6,9,10
hi=1 low=0 ld=1
hi=2 low=1 ld=2
hi=3 low=2 ld=1
hi=4 low=3 ld=3
hi=5 low=4 ld=1
{ leastDiff: 1, lowIndex: 0, highIndex: 1 }
sorted arr: -25,-10,-2,5,9,13,25
hi=1 low=0 ld=15
hi=2 low=1 ld=8
hi=3 low=2 ld=7
hi=4 low=3 ld=4
hi=5 low=4 ld=4
hi=6 low=5 ld=12
{ leastDiff: 4, lowIndex: 3, highIndex: 4 }


texts: Reconstructing a graph from set of sequences of edges

texts:
I have posted the same problem to Math Overflow, not sure where it fits better.

I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, find a "reasonable" reconstruction of the graph. There is an unknown number of vertices in the graph, but it's given that each edge in each given sequence shares a vertex with the edge next to it in the sequence. We could further assume, that all the sequences start with the same edge.

Ideally, I would need an algorithm to reconstruct the graph.

Has such problem been already studied or does anyone see a way to transform it to another known problem? So far, I can only think of genetic algorithms.


texts: Continuing the example of why it's hard to compute with univalence?

texts:
In "Towards a cubical type theory without an interval" Altenkirch and Kaposi motivate why it is hard to compute with univalence. They say:

  For example, we can define the equivalence (not ,...) between Bool and Bool and thus univ (not ,...) : Bool =_U Bool, and then using it, define a boolean b:

coe : (A =_U B) → A → B
coe (refl A) a :≡ a

b : Bool
b :≡ coe (univ (not, ...)) true

  We know that b should be false as we coerce along not, but coe was only defined for the case refl so the term b does not compute further. One may think that it would be enought to add the equation coe (univ (f,...)) ≡ f but this is not sufficient as shown by the following example. Here we use the ap (apply path) function for a P : U → U :

ap_P : A =_U B → P A =_U P B
ap_P (refl A) ≡ refl (P A)

x : P Bool =_U P Bool
x :≡ ap_P (univ (not, ...))

  To reduce this term we need to know how to transport an equivalence along an arbitrary
  type.

What I don't understand is the last sentence. Is the "arbitrary type" the result of applying P to Bool? I feel that for any given P : U → U we can write a corresponding ap_P. For example:

Maybe : U → U
Maybe A = () + A

Show : U → U
Show A = A → String

Endo : U → U
Endo A = A → A

ap_Maybe (univ (f, g, ...)) = univ (either id f, either id g, ...)
ap_Show (univ (f, g, ...)) = univ (\show -> show . g, \show -> show . f, ...)
ap_Endo (univ (f, g, ...)) = univ (\endo -> f . endo . g, \endo -> g . endo . f, ...)

Is this intuition already off? What would be a concrete P where this fails? Or is the problem that while we know how to transport an equivalence along any function P : U → U we don't know how to do it for all such functions?


texts: Valid actions of Reductions to NP-Completeness

texts:
To my understanding, as long as we can find some polytime function $f$ such that $\forall x:x \in A \Longleftrightarrow f(x) \in B, x\notin A \Longleftrightarrow f(x) \notin B$, it follows that if $A$ is NP-complete and B is in NP, then B is also in NP-complete.

My question is about what sort of 'things' we can do to obtain reductions from NP-completeness. That is, I want to know if $f$ is allowed to do anything so long as it is still done in polytime and satisfies the above property? If not, then what sort of limitations are there?


texts: In Bankers Algorithm, with three processes, in the question of need <= work(aka available). Is the need of 1 0 1 <= 0 0 2 work?

texts:
Three processes A B C.  When conducting the safety algorithm, no explanation that I've been able to find answers the question of how the processes are being compared. Is it the total processes added up, or every process individually must pass the '<=' operator, or is it like regular integers where Process A would be the most significant comparison?

https://www.youtube.com/watch?v=2V2FfP_olaA

TLDR Answer: It's individual based. Each process work/available item in the matrix, must satisfy each need.


texts:
Why do you think it is that most C++ instructors teaching college level computer sciences discourage or even forbid using strings for text, instead requiring students to use character arrays?

I am assuming this methodology is somehow intended to teach good programming habits, but in my experience I don't see anything wrong with just using strings, and they are significantly easier to use and learn.


texts:
Find whether given statement True or False? Explain.

User level threads are transparent to the kernel?

My attempt :
False. Since, user level threads are managed by a user level library however, they still require a kernel system call to operate. It does not mean that the kernel knows anything about thread management. Not at all, it only takes care of the execution part. the lock of the cooperation between user level threads and the kernel is a known disadvantage.

Somewhere it explain as : "The kernel knows nothing about user-level threads and manages them as if they were single-threaded processes".
I found another statement "User level threads are transparent to OS and kernel level threads are scheduled by OS". It seems correct.
My question is :

Are user level threads transparent to the kernel? What is meaning of transparent here?


texts: Worst case running time of lexicographical sorting of a list of n strings each of length n using merge sort

texts:
This same question has been asked here so many times by several people. This is a problem which was asked in an entrance exam.

And I am having difficulties in digesting the correct answer of this problem. Why is my approach incorrect?

Here is my approach:
The divide part of the merge sort recursively divides the list of strings into sub-lists with half number of strings each.

Then the merge part takes sorted lists from two of its child node and merge them into its own sorted list. This merging propagates upwards towards the root and the entire list is eventually sorted.

The merging works this way:
The two child-lists together have $(n1+n2) = O(n)$ strings. And for comparing two strings as the part of merging, we need to compare at most $n$ positions (since the strings are of length $n$).

So the merging takes $\theta(n*n) = \theta(n^2)$

Now the recurrence equation looks like: $T(n)= 2T(n/2) + \theta(n^2)$

Using master method $n^{log_22}=n$
And $f(n)=\theta(n^2)=\Omega(n^{log_22})$

Which is case 3 of Master method. so $T(n)=\theta(f(n))=\theta(n^2)$ should be the correct answer.


texts:
Let define $A \oplus B = \{2x \mid x \in A\} \cup \{2x + 1 \mid x \in B\}$. Prove that $A \oplus B$ is recursive if $A$ and $B$ are recursive.
I am currently having the following idea.
Since $A$ is recursive, $P_A$ the characteristic of $A$ is recursive. Similarly, $P_B$ is recursive.
So, we need to show that $P_{A \oplus B}$ is recursive.
How can I define the characteristic predicate of $A \oplus B$ in term of $P_A$ and $P_B$?


texts: Solving $UCYCLE$ in logspace - two possible approaches ? Why can't we one of them use to solve connectivity?

texts:
$$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$
There are two possible approaches to this exercise:
Solving cycle in undirected graph in log space?

https://stackoverflow.com/questions/29640543/solving-cycle-in-undirected-graph-in-log-space

These two solutions are different. The instresting solution is second one (on stackoverflow). In this case we generally implement DFS in logspace.  I can see that it does work (using DFS). However the question is:
Why we can't use this DFS algorithm to solve USTCON problem ?

However, I can see that we can't easily use this DFS to solve bipartity problem. It is not easy to count number of nodes in cycle.

Edit
Modified algorithm from stackoverflow (mentioned link) which should solve ustcon problem:

    for v_j in neighbours(s)
        current, prev = v_j, s
        repeat
            idx = neighbours(current).index(v_j)
            idx = (idx + 1) % len(neighbours(current))
            current, prev = neighbours(current)[idx], current
            if current = t then return connection between s and t
        until current adjacent to s
return no_connection between s and t


texts: Is something missing in this EXPLORE algorithm?

texts:
It took me about a week to understand how does it works, but still, I'm wondering if it actually works!

I. The algorithm EXPLORE

EXPLORE (S:sommet, D:following vertices of vertex X, visited:TAB)
var LIST;
i,j:vertices
visited[S] ←true;
LIST ←{S};
WHILE LIST ≠ 0
    selectionner i ∈ LIST
    IF ∃ j ∈ D[i] , not visited[j]
      visited[j]←true;
    ELSE LIST←LIST - {i}

II. running the algorithm

Then I tried on this Graph:

array of the following vertex of each vertex:

\begin{array}{|l|cr|}
x & \Gamma^+(x)\\
\hline
a & b,c,d\\
b & d,e\\
c & d,f \\
e & d,h \\
f & g,i \\
g & h, e \\
h & \emptyset\\
i & g,h \\
\end{array}

M: the visited tab
L: the given list, which is empty in the beginning

Explore (a,$\Gamma$,M)

M$\leftarrow${a}

L$\leftarrow${a}

$\Gamma(a) ∩ (X  \backslash  M)=bcd \ne0$

list $ \ \ \ \ \ \ \ $notvisited

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b}$ why do we add b to L??

$\Gamma(b) ∩ (X  \backslash  M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,d}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b,d}$ why do we add b to L??

$$...$$

$\Gamma(e) ∩ (X  \backslash  M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b,d,f,g,h}$ That seems normal on the aglorithm, it corresponds to

Else LIST = LIST - i

$$...$$

Until

$\Gamma(d)$

$L\leftarrow a$

which leads to the components we didn't searched for:

$\Gamma(a) ∩ (X  \backslash  M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,c,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,c}$ Still, wher the hell does this e comes in the algorithm?

$\Gamma(c) ∩ (X  \backslash  M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,c,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a}$ I'm okay with its disparition

$\Gamma(a) ∩ (X  \backslash  M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ L\leftarrow {\emptyset}$ I'm okay with its disparition

III. My ideas to make it works

if ever it doesn't work!

I wonder if something is not lacking in the algorithm, if we shouldn't add an Explore within the 'if' loop.

EXPLORE (S:sommet,  Γ, visited)
var LIST;
i,j:vertices
visited[S] ←true;
LIST ←{S};
WHILE LISTE ≠ 0
    selectionner i ∈ LISTE
    IF ∃ j ∈ D[i] , not visited[j]
      visited[j]←true;
      **EXPLORE(j,Γ,visited)**
    ELSE LISTE←LISTE - {i}


texts: Shortest tour visiting given set of nodes in knight tour graph

texts:
Problem:

Given knight tour graph $G$ ($8 \times 8$ nodes) and a set of nodes $\{ v_{1}, v_{2}, \dots, v_{n} \} = V \subset V(G)$, find a minimal length tour in $G$ that visits all nodes from $V$ (maybe others too). Each $v \in V$ must be visited exactly once.

We suppose that the graph is unweighted, so tour's length is the same as its edge count.

Question:

It comes to mind that we would try to find the shortest path between $v_{1}$ and $v_{2}$, then between $v_{2}$ and $v_{3}$, and so on. Is it true that combining these shortest paths will give the desired tour?


texts: Calculating execution time for recursive algorithm

texts:
How would I calculate the execution time, T(n), for this algorithm?

int search(int a[], int l, int r, int x) {
    int m = (l+r)>>1;
    if (l > r) return -1; // not found
    if (a[m] == x) return m;
    if (a[m] > x) return search(a, l, m-1, x);
    return search(a, m+1, r, x);
}


texts: Writing programs with a block programming environment vs. Writing programs using high level prgramming language

texts:
I'm a GCSE Computing student and I've been asked to compare writing programs in a block programming environment (I think this means using programs such as Scratch or App Inventor but I'm not entirely sure) compared to writing programs using high level programming languages such as Python, Java etc.
I'm honestly not trying to ask you to do my work for me, I just desperately need some help on the advantages and disadvantages of both ways of writing programs because we haven't really been taught it by my teacher and I haven't found much on the Internet about it.


texts: how do I simplify this particular boolean expression?

texts:
so I have spent nearly 5 hours trying to simplify this particular expression but I keep going round and round in circles. I have my hard copy notes to show you where I scribbled for hours and hours to no end. so please can someone please show me how can this be done?

$$(\overline{A}+\overline{B}+E)(\overline{A}+\overline{C}+D)(C+D+\overline{E})(\overline{B}+D)(A+E)\,.$$

I tried expansion, common, DeMorgan but I can't find my way out.


texts: Good introductions to Formal Language Theory and Formal Grammars

texts:
Does anyone know any good introductions to Formal Language theory and Formal Grammar, that cover the mathematical basis of Syntax and things like context free grammars and pushdown automata. In particular, I'd like to be able to understand:

-Parikh’s theorem

-Pentus' proof that Lambek-calculus grammars define only context-free stringsets

-the theorem of Chandra, Kozen and Stockmeyer

-Bûchi’s theorem and Doner’s theorem

Geoffrey Pullum's review http://www.lel.ed.ac.uk/~gpullum/Rev_Kracht.pdf has put me off reading a book called "The Mathematics of Language" by Markus Kracht, since I am not sure I have the required level of mathematical maturity. He writes:

"Readers of The Mathematical Intelligencer will probably get on with it well enough, but others should be warned that Kracht assumes a lot of mathematical sophistication: graduate students whose first degree is in humanities or social science may experience symbol shock. Kracht does not pamper those who crave intuitive presentations. He will not explain that a finite automaton accepts exactly those strings on which there is a run beginning in the start state and ending in a final state; he will expect you to see that immediately when he tells you (on p.96) that $L(A) = \{x \colon~ \delta(\{i_0\},x)\cap F \neq \emptyset\}$."

The review has also put me off several other introductions:

"W. J. M. Levelt’s truly excellent 3-volume 1974 textbook [6] had remarkably wide coverage (Lev- elt’s psycholinguistic interests lead him to cover work on ‘learnability’, also known as grammar induction, which Kracht does not touch on), but sadly has long been out of print. And the standard text by Partee, ter Meulen and Wall [9] is now more than fifteen years behind the leading edge of research, especially with respect to grammars and automata. (Though it was published in 1990, the Partee el al. volume reports as open the question of whether the complement of a context-sensitive stringset is always context-sensitive, which was settled in the affirmative in 1987, at Partee’s insti- tution!) Though strong on formal semantics, it completely misses important topics in other areas (parsing and computational complexity, for example), and it looks positively fusty beside Kracht’s much more up-to-date and considerably more mathematical book."

So I'd be grateful to hear if there are any introductions to this field which people can recommend.


texts: Linear time algorithm for finding $k$ shortest paths in unweighted graphs

texts:
Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$,
  the $k$-shortest-paths problem is finding the $k$ shortest simple paths
  between $s$ and $t$ in $G$.

Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem (assuming that $k$ is fixed).

I have looked at a few papers in the literature, such as "A New Implementation Of Yen's Ranking Loopless Paths Algorithm" but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein "Finding the k shortest paths" presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$.

Is there a linear-time algorithm for the $k$-simple-shortest-paths problem (in terms of $n$ and $m$) on unweighted graphs, where $k$ is fixed?


texts: Hard connected instances for Weisfeiler-Lehman test of isomorphism

texts:
There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm.

However, one of these graphs is disconnected. So what are the instances of undirected connected graphs for which WL algorithm fails?


texts:
$$t(n)=\begin{cases}n&\text{if }n=0,1,2,\text{ or }3\\t(n-1)+t(n-3)-t(n-4)&\text{otherwise.}\end{cases} $$
Express your answer as simply using the theta notation.

I don't know where to go with this.

$$t(n) - t(n-1) - t(n-3) + t(n-4) = 0$$

Is the characteristic polynomial $x^3 - x^2 - x +1 = 0$?


texts: NP Problem that cannot be solved by a quantum computer in polynomial time

texts:
Is there any NP-Problem that can't be (maybe even proven) solved by quantum computers. I'm not talking about quantum NP-Problems (if that's even a thing), but about normal NP.
If that NP Problem exists could you also use it for cryptography, since I don't want to buy a quantum computer just to be secure.

EDIT:
I'm not talking about NP-complete, because that would have no use (I think) in cryptography and also not about symmetric key encryption.


texts: Correctness of Strongly Connected Components algorithm for a directed graph

texts:
I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$.

The algorithm is the following :

Execute DFS on $G$ (starting at an arbitrary starting vertex), keeping track of the ﬁnishing times of all vertices.
Compute the transpose,
Execute DFS on $G^T$, starting at the vertex with the latest ﬁnishing time, forming a tree rooted at that vertex. Once a tree is completed, move on to the unvisited vertex with the next latest ﬁnishing time and form another tree using DFS and repeat until all the vertices in $G^T$ are visited.
Output the vertices in each tree formed by the second DFS as a separate strongly connected component.

My question is :

What is the intuition behind this middle step of computing a transpose?


texts: Is $\{ 0^p1^q0^r \mid p \neq r \}$ context-free?

texts:
Consider the following languages:
$$ \begin{align*} L_1 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0 \}, \\ L_2 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0, \; p \neq r \}. \end{align*} $$
Which one of the following statements is false?
A. $L_2$ is context-free.
B. $L_1 \cap L_2$ is context-free.
C. $\overline{L_2}$ is recursive.
D. $\overline{L_1}$ is context-free but not regular.

Doesn't the following show that $L_2$ is context-free, and so option A should be false as well?
Assume $L_2$ is context-free.
Consider the string $w = 0100 \in L_2$.
Breaking $w$ into $w= uvxyz$, where $u = \epsilon$, $v = 0$, $x = 1$, $y = \epsilon$, $z = 00$, according to the pumping lemma (with $p=r=2$), $uv^2xy^2z = 00100 \in L_2$, which is false.


texts:
Say I have three sets:

A = [banana, apple, grape]

B = [1, 2, 3, 4]

C = [Alice, Bob, Carol]

I need to design an algorithm that gives me the Cartesian Product A x B x C, but with any number of sets and any number of elements in each set. Another requirement is that the order of the elements in the Product is such:

A x B x C = [(banana, 1, Alice),
             (apple, 1, Alice),
             (banana, 2, Alice),
             (banana, 1, Bob),
              ...]

I could only come up with a recursive algorithm that ends up giving me:

A x B x C = [(banana, 1, Alice),
             (banana, 1, Bob),
             (banana, 1, Carol),
             (banana, 2, Alice),
              ...]

Obviously, A x B x C needs to have every possible combination of the elements of the sets. Also, I need an algorithm that covers the general case of any number of sets, not only three.
Is there any well-known algorithm that provides the Cartesian Product in this order that I need?

Any help or tips is much appreciated.


texts: Why is the Kth Largest Element solution using a MinHeap O(N lgK) in complexity?

texts:
This is a rather well known solution to the $k$-th order statistic problem which requires us to find the $k$-th largest number in an unsorted array with $n$ elements where $1 \leq k \leq n$:
public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

        for (int num: nums) {
            heap.add(num);

            if (heap.size() > k) {
                heap.remove();
            }
        }

        return heap.remove();
    }

A brief summary of this approach is that we maintain a min heap and keep polling from this heap each time its size exceeds $k$. This way, our final heap will contain $k$ elements, and these $k$ elements are guaranteed to be last $k$ elements in the sorted array  (since we have been polling minimums). Within these last $k$ elements, the minimum element is guaranteed to be the $k$-th largest so we extract the min and return that as a result.
What I don't particularly understand is why this problem is $\mathcal{O}(n \lg{(k)})$. For instance, after $\mathcal{O}(n)$ creation of the heap, we do an extraction of the minimum $n - k $ times, which would require sifting up in the heap $n - k$ times and hence, shouldn't this solution be $\mathcal{O}(n \lg{(n - k)})$?
Thanks!


texts: Analysing the algorithm of a language called CONNECTED in Sipser to show that it belongs to class P

texts:
The question and its answer is given in the following picture:

But I do not understand why stage 2 causes at most $n+1$ repetitions, and why stage 3 uses at most $O(n^2)$ steps, and I understand that the algorithm runs in $O(n^4)$ time not $O(n^3)$ as written, am I right?


texts: What complexity class does this variation of traveling salesman problem belong to?

texts:
Given a TSP instance $T$, decide whether changing the city coordinates by adding a vector of coordinates $v$ will change the optimal TSP objective by atleast $x$. The city coordinates are integers.

The problem is in PSPACE but even the verification problem seems to be NP-hard. Is that true?

If the verification problem is NP-hard, what exact complexity class does this problem belong to?


texts: Karp hardness of a simply equidistant vertex set

texts:
Following the success of the previous question:

Karp hardness of an equidistant vertex set

I continue to propse yet another computational problem. This time, we modify the notion of an equidistant vertex set to obtain the notion of a simply equidistant vertex set. A vertex set $V'\subseteq V$ is called simply equidistant if there exists some $\alpha\in \mathbb{N}$ such that for every $u, v\in V'$, there exists a simple path of length $\alpha$ connecting $u$, $v$.

Our problem:

  Input: an undirected graph $G(V,E)$ and a natural number $k$

  Output: YES if there exists a simply equidistant of size $k$,
  otherwise NO

What is the hardness of this problem?


texts: Specific quadratic 0-1 knapsack problem solvable in linear time?

texts:
I am interested in a simple variant of the quadratic knapsack problem.
Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, assume $h$ is a fixed integer such that $n \geq h \geq \left \lfloor \frac{n+1}{2} \right \rfloor$ . Consider the following problem:
$$ \mbox{minimize }  \frac{1}{h} \sum_{i=1}^{n}{(w_iv_i)^2} -  \left(\frac{1}{h} \sum_{i=1}^{n}{w_iv_i}\right)^2,$$ under the condition that:
$$ \sum_{i=1}^{n}{w_i} = h.$$

In other words, I am looking for the subset of size $h$ which minimizes the (sample) variance of that subset. I know that I can sort the values $v_i$ and then check every subset of $h$ consecutive values from left to right (it can be shown that the knapsack should contain contiguous elements for this problem). This would lead to a solution in $\mathcal{O}(n\log(n))$ time. I am curious to find out if a faster algorithm can be found (i.e. without a complete sort).


texts:
A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works.

Say, for $T(n) = T(\lceil n/5 \rceil + 36) + n \log n$

Statement: we wish to prove that $T(n) \le 5 \ n \log n$ for $n \ge 0$

Base case, $n = 0$ and $T(0) \le 0$

$T(0) = 0$

$T(0) \le 0 \log 0$

Holds, since $0 \log 0 = 0$

Inductive step, for $n > 0$

(Inductive Hypothesis is: $T(n) = 5 \ n \log n$)

$T(n) = T(\lceil n/5 \rceil + 36) + n \log n$

$\le 5 \, (\lceil n/5 \rceil + 36) \log (\lceil n/5 \rceil + 36) + n \log n$ by Ind. Hyp.

$\le 5 \, (n/5 + 36) \log (n/5 + 36) + n \log n$ by property of ceiling

$= (n + 180) \log ((n + 180)/5) + n \log n$ by algebra

This is the point where it gets hazy. According to the link, what I should do is say that for all $n \ge 180$, then

$\le (n + n) \log ((n + n)/5) + n \log n$

$= 2n \log (2n/5) + n \log n$

$= 2n \, [\log n + \log (2/5)] + n \log n$

$= 2n \log n + 2n \log (2/5) + n \log n$

$= 3n \log n + kn$ where $k = \log (2/5) * 2$

$\le 5n \log n$

Does this complete the proof? Or am I in error? I still don't understand why I can just set $n \ge 180$ and therefore get rid of the irritating arithmetic within the log.


texts: Can heuristic methods and machine learning approaches be considered alternate methods to solve NP-Complete problems?

texts:
I was watching the videos from Skiena's Computational Biology Lectures, which is also available at youtube. In those videos, the professor made a statement that, most of the problems posed to computer scientists by biologists were proved to be NP-Complete. My questions are the following ones:
( Please forgive me, if I make blunders here in asking questions. I am not from CS background.)

Do NP-Completeness imply no algorithm exist for that particular problem?
The professor was talking about heuristic approaches where normal approaches fails. Do there exist 'heuristic' approaches in computer science to solve problems? If so , Can some one give examples. (I have heard of heuristic approaches in analog circuit design in electronics. But I am not sure. Music composition is heuristic , right?)
Is Machine learning a solution to solve some computational problems, where traditional algorithmic solutions doesn't exist?


texts:
I am taking a course on natural language processing that assumes the students have some background on theory of computation. I dont, but have read up till chapter 3 of the book "Speech and Language Processing by Jufrasky".

I therefore understand the following

regular expressions and regular languages
operations on regular languages (union, cross product)
finite state automatas and the construction of FSA's given a regular expression

Unfortunately, I couldn't solve a single question below and am not even sure if my understanding of the question is correct. The red ticks are the solutions. I hope the people here can help out an NLP newbie.

Definitions for the notations are as follows:

$+$ which means ‘one or more of the previous character’. (book definition)

$\bigotimes$ cross product

So this is my most likely wrong understanding of the first statement:
$L_1+ \bigotimes L_2 + $

If I have

$L_1 = \{aa,ab,aab\}$

$L_2 = \{b,ab,abb\}$

then $L_1 + $ requires me to have at least one occurrence of $L_1$. And so $L_1+ \bigotimes L_2 + $ would result in a set that could have at least one of the element from $L_1$ concatenated with at least one from $L_2$ ? So I could get something like $aa \ aa \ b$ ? Where the two $aa$ comes from $L_1$.

Would this be correct ?


texts: Is $(X (X X)) ((X X) X) X$ the most simple representation of the identity combinator when $X = \lambda x . x KSK$?

texts:
Let combinator $X = \lambda x . x KSK$ as described by Hankin (1994).

Then $K = (X X) X$ and $S = X(X X)$.

Identity combinator however seems to have much more verbose form.

If $I = SKK$ then also $$I = (X(XX))((XX)X)((XX)X)$$

I could possibly make this a bit shorter:

$$I = (X (X X)) ((X X) X) X$$

but is this as far as you can get with representing $I$ with $X$ combinators?

I'm comparing $X$ with Baker (2001) Iota combinator $X' = \lambda x . x SK$, which seems to have dramatically less verbose counter part for $I = X'X'$ but on the other hand it takes extra $X'$ to define $S$ and $K$ compared to Hankin's.


texts: If an algorithm solves an NP problem, for what f(n) can we claim that R belongs to TIME(f(n))?

texts:
Let $R$ be some problem in NP.

Suppose algorithm of solution check M(x,y) runs in time $O(n^3)$ and uses $y$ additional information, s.t $y \leq 5 \log n$ bits.

For what $f(n)$ can we claim that $R$ belongs to $\textbf{TIME}$$(f(n))$?

I have no idea how to solve this.


texts: Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$

texts:
I'm currently struggling to come up with a proof that the following language is irregular:
$$L_2 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| \ne |w_2|\}$$
where $\Sigma = \{a, b\}$.
Now quite intuitively, the language needs to know what $|w_1|$ was in order to compare against $|w_2|$, so it has to be irregular, but I'm failing to formally prove that.
I was able to solve the previous problem from the book, which was proving that (similarly)
$$L_1 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| = |w_2|\}$$
is irregular, which was relatively simple using the pumping lemma.
So I thought maybe there was some kind of connection between the two problems, given that $L_1\cup L_2$ is regular, but there doesn't seem to be any kind of closure property I can robustly employ in order to prove that $L_2$ is irregular.
Any ideas are welcome and many thanks in advance!


texts: With restrictions, can the knapsack puzzle be solved with a greedy algorithm?

texts:
I know that with the knapsack problem in general, there is no known greedy algorithm to solve it. But, say we add the following constraints:

• All items have values equal to their weights (for all $i$, $w_i = v_i$)

• The weights are all powers of 2 (for all $w_i$ there exists $n ∈ N$ such that $w_i$ = $2^n$).

Now, a knapsack problem with the following constraints can have a greedy algorithm that selects the heaviest item which can currently fit in the knapsack until no item remaining can fit.

Will this work or is there really no way the constrained knapsack problem can be solved with a greedy algorithm?


texts: Why a language specified by a regular expression is not a complement of a given language?

texts:
I am taking a compiler MOOC online on my own time. The class is self paced. There is a question with an answer but I can't understand why the answer is correct.
Here is the question.

For any language $L$, the complement of the language (usually written
$L′$) is defined as the language that consists of all the strings that
are NOT in $L$. That is,
$L′=Σ^*−L$
It turns out that the complement of any regular language is
also a regular language. Which of the following regular expressions
define a language that is the complement of the language defined by
the regular expression: $1(01)^*$?

$(10)^*+\big((10)^*0(0+1)^*\big)+\big(1(01)^*1(0+1)^*\big)$
$\epsilon + (0(0 + 1)^*) + ((0 + 1)^*0) + \big((0 + 1)^*(00 + 11)(0 + 1)^*\big)$
$(0 + \epsilon)\big((1 + \epsilon)(0 + \epsilon)\big)^*$
$(10)^*$

Correct answers are 1 and 2. I can't understand why 3 and 4 are not correct as well since the strings generated by these languages are also not in $L$.
Any explanation is greatly appreciated.


texts:
given is a reduction from 4-SAT to 5-SAT.
How is it possible to describe such a function?
I found some informations about reduction 3-SAT to 4-SAT here, but it can't help me so much.


texts: Difference between encoding and modulation in transmission

texts:
What is the difference between encoding and modulation?

I have seen these terms used sometimes inter-changeably and sometimes differently (the ratio is 50:50).

Can somebody clearly explain this with some non-technical and technical examples both? I have searched this a lot on net and in the end I end up scratching my head.


texts: rebalance red-black tree with many violations

texts:
Every red-black tree implementation I've come across use a strategy that considers re-balancing the tree after each mutation (e.g. insert, delete, ...).

I have a situation where I graft several sub-trees from one red-black tree onto another. After these grafts I would like to consider re-balancing the resulting tree.

Are there any approaches to doing this, either applying existing techniques in a brute force manner, or strategies that would make it efficient. It isn't entirely clear that existing algorithms can be naively applied.


texts: Does the Paxos algorithm use failure detectors? If not, how can it solve consensus, given the impossibility result?


texts:
Wikipedia says:

  Complete lattices appear in many applications in mathematics and computer science

Is it just referring to the fact that the standard Boolean algebra used in computation is a complete lattice? Is there anything we gain by working at the abstract level of lattices instead of with Boolean logic specifically?

A google search doesn't find much on the subject, but I'm probably using the wrong keywords.


texts: Could a quantum computer perform linear algebra faster than a classical computer?

texts: Supposing we had a quantum computer with a sufficient number of qubits, could we use it to do linear algebra faster than we could with a classical computer? What sort of speedup could we expect? Has anyone created a quantum algorithm for linear algebra, and what is it's running time? In theory, an operation such as matrix-matrix multiplication is highly parallelizable, however in practice it requires a lot of work to implement parallel matrix-matrix multiplication that runs quickly. Would a quantum computer provide any practical advantage?


texts: Is it possible to use an adjacency matrix for Bellman-Ford algorithm?

texts: I have created a function that generates a complete, directed, and weighted graph, represented in an adjacency matrix but most Bellman-Ford implementations use an adjacency list. Is it even possible to use an adjacency matrix for Bellman-Ford without increasing significant time complexity? What would be the simplest way to use my graph-generating algorithm to the Bellman-Ford algorithm? Am I required to convert my matrix into a list?


texts:
In the book Logic in Computer Science on page 244, there is a proof that $[[E(\phi U\psi)]]$ is the least fixed point of $G(X)=[[\psi]] \cup ([[\phi]]\cap\mathop{\textrm{pre}}_\exists(X))$. I don't get the idea of point 2. I tried to understand why this proof says that $[[E(\phi U\psi)]]$ is the least fixed point of $G$.

They prove that $G^{k+1}(\emptyset)\subseteq[[E(\phi U\psi)]]$ for each $k\geq0$.
This is fine, I understand each step on their the proof, I just don't understand why this proves that $[[E(\phi U\psi)]]$ is the least fixed point of $G$...

I can prove that $G^{k+1}(\emptyset)\subseteq S$  when $S$ is the group of all the states. $G$ is still the same function, and of course that for each such $i\geq0, G^i(\emptyset)\subseteq S$. This doesn't mean that $S$ is the least fixed point, or that each fixed point contains $S$.

So why this proof claims that $[[E(\phi U\psi)]]$ is the least fixed point of $G$?


texts:
I would like an example of a quine in pure lambda calculus. I was quite surprised that I couldn't find one by googling. The quine page lists quines for many
"real" languages, but not for lambda calculus.

Of course, this means defining what I mean by a quine in the lambda calculus, which I do below. (I'm asking for something quite specific.)

In a few places, e.g. Larkin and Stocks (2004), I see the following quoted as a "self-replicating" expression: $(\lambda x.x \; x)\;(\lambda x.x \; x)$. This reduces to itself after a single beta-reduction step, giving it a somehow quine-like feel. However, it's un-quine-like in that it doesn't terminate: further beta-reductions will keep producing the same expression, so it will never reduce to normal form. To me a quine is a program that terminates and outputs itself, and so I would like a lambda expression with that property.

Of course, any expression that contains no redexes is already in normal form, and will therefore terminate and output itself. But that's too trivial. So I propose the following definition in the hope that it will admit a non-trivial solution:

definition (tentative): A quine in lambda calculus is an expression of the form
$$(\lambda x . A)$$
(where $A$ stands for some specific lambda calculus expression) such that $((\lambda x . A)\,\, y)$ becomes $(\lambda x . A)$, or something equivalent to it under changes of variable names, when reduced to normal form, for any input $y$.

Given that the lambda calculus is as Turing equivalent as any other language, it seems as if this should be possible, but my lambda calculus is rusty, so I can't think of an example.

Reference

James Larkin and Phil Stocks. (2004) "Self-replicating expressions in the Lambda Calculus"
Conferences in Research and Practice in Information Technology, 26 (1), 167-173.
http://epublications.bond.edu.au/infotech_pubs/158


texts: Are any problems in P known to have logarithmic-time-verifiable certificates?

texts:
Problems in NP have certificates which can be verified in polynomial time.

It seems conceivable that there could be problems in P which have certificates which can be verified in logarithmic time.  (Such certificates would also have to be logarithmic in size, naturally.)

However, it is also conceivable that there are no such problems.  I've tried to come up with examples, but none of them have worked out so far.

Have problems like this been studied and shown to exist (or not exist)?

I can't seem to find a complexity class that would describe them in the Complexity Zoo, although it's certainly possible that there's one there and I'm just having a hard time identifying it.  (L and LOG usually refer to space, and neither LH nor NLOG looks like it necessarily captures the idea.)


texts: Number of possible balanced binary trees

texts:
A tree is balanced if the subtrees of each node differ in height by at most one.

  How many balanced binary trees can we create from $n$ nodes?


texts: Why is the number of states for DFA is 3n + 1 for this language

texts:
I'm taking online compilers course. It's long ended, so it wouldn't be cheating to ask a question on quiz here.

Let $S_i$ be the string consisting of $i$ 0's followed by $2i$ 1's. Define the language
$L_n = \{ S_i | 1 \leq i \leq n \}$. For example,

$L_3 = \{\, 011,\, 001111,\, 000111111\; \}$

For any given $n$, what is the smallest number of states needed for a DFA that recognizes $L_n$?

I know regexes a bit and I can't think of a way of expressing this with regular expression. But I thought even if it's possible it should involve some kind of backreference, and isn't backtracking impossible with DFA?

So the quiz gives the correct answer $3n + 1$ and explain it like so.

  We need states to count how many 0 we meet and how many 1 we meet, so we need 3*n+1 states including the start state.

And this explanation doesn't explain anything to me. I mean okay the $+1$ part obvious, but why is there $3n$? I mean I agree that we probably need states to count how many 0 and 1 we meet, but exactly how we're gonna do it? If anything we should have 4 states in my opinion. One recognize 0, one to recognize 1 and another two states to count the numbers of them.

Right now I'm reading articles and papers about NFA, DFA, regular expressions and backreference, but maybe the answer is much simpler?

EDIT1.
Okay, I've tried my best and constructed kind of obvious DFA for this task.

The total number of states would be $\sum_{i=1}^{n}i+2i$ which looks like arithmetic progression to me with a difference $d=(i+1)+2(i+1)-(i-2i)=i+1+2i+2-i-2i=3$ So the sum will be equal to $\frac{n(a_1 + a_n)}{2}=\frac{n(3 + (n + 2n))}{2}=\frac{n(3+3n)}{2}=\frac{3(n^2+1)}{2}$

I don't see $3n + 1$ here.

Okay, I think I finally got this. The main problem I think was that I haven't tried to actually draw automaton initially and If I would it would be much easier. So once I've noticed that it could be changed into this

And this would give $3n+1$ obviously.


texts: I was wondering if HOL (higher-order logic) can be simulated in the Calculus of Inductive constructions (CiC)


texts: Is the Kleene star of an intersection always equal to the intersection of kleene stars?

texts:
I know that the  Kleene star of an intersection is contained in the intersection of Kleene stars, but are they necessarily equal?

For example, given two formal languages, $A$ and $B$, I know that $(A\cap B)^*\subseteq A^*\cap B^*$, but does $(A\cap B)^*= A^*\cap B^*$?


texts: Chomsky hierarchy type determined by language

texts:
I have some modified automata and the task is to give the type of Chomsky hierarchy to it.
All task is between type 3 and 0 noninclusive.
For regular languages there are lot of tools and I can check it without problems, Turing Machine equivalent is also easy task, and there will be no such examples.

Now the question: is it sufficient to show that automaton can accept specified language of given type?
From what I checked it would be sufficient to show equivalence to for example to NPDA, so I assume that if machine handles language that at least NPDA accepts it would be sufficient.

For example if machine can accept $a^nb^n$, it is type 2.
If machine can accept $a^nb^nc^nd^n$ it is type 1?
If not are there better examples of such languages or what steps should I follow?


texts: How do I calculate offset from virtual address?

texts:
If the page size is 4Kbyte and the physical size of the main memory is 32Kbyte.
Now if I consider virtual address of 37064..
The page number is then 37064/4096 = 9
And according to my diagram page 9 is mapped to frame 6
But how do I calculate the offset? According to exercise it should be 200.
Thank you


texts: Outputting numbers within a range that are not in a list

texts:
How could you design an efficient algorithm that uses the least amount of memory space and outputs, in ascending order, the list of integers in the range 0..255 that are not in a randomly generated list of 100 integers?

The aim is to output the number of such integers, and determine if the randomly generated list of 100 integers included any repeats.

The naive approach would be to compare each number from 0 to 255 against the list of 100 integers. This would not be very efficient.

What would be a more efficient approach to solve this?


texts: How does augmenting linear bounded automata tape alphabets increase memory?

texts:
A linear bounded  automaton is a Turing machine that is restricted by memory.
How would augmenting  the tape alphabet of a linear bounded automaton
increase its memory? While the memory that the automata can
use is as size of the input?


texts: How do I find running time for the following divide and conquer problem?

texts:
Question is to find the runtime $T(n)$ of following problem by solving the recurrence.

$T(n)=16\cdot T(\frac{n}{4}) + n!$.

I went through the following theory.

If the recurrence relation is of the form $T(n)=aT(\frac{n}{b}) + \Theta(n^k(\log n)^p)$,where $a \geq 1$ , $b \gt 1$, $k \ge 0$ and $p$ is a real number, then:

If $a \gt b^k$, then $T(n)=\Theta(n^{\log_b a})$.
If $a=b^k$

If $p \gt -1 $, then $T(n)=\Theta(n^{\log_b a}(\log n)^{p+1})$.
If $p=-1 $ then $T(n)=\Theta((n^{\log_b a}\log \log n)$.
If $p \lt -1 $, then $T(n)=\Theta(n^{\log_b a})$.

If $a \lt b^k$

If $p \ge 0 $, then $T(n)=\Theta(n^k(\log n)^p)$.
If $p \lt 0 $, then $T(n)=O(n^k)$.

Now I want to know how do I compare the second terms of the the equations ($n!$ and $\Theta(n^k(\log n)^p) $) to obtain $k$ so that I can check which of the above case holds true ?


texts: Recurrence relation and time complexity of recursive factorial

texts:
I'm trying to find out time complexity of a recursive factorial algorithm which can  be written as:

fact(n)
{
 if(n == 1)
 return 1;
 else
 return n*fact(n-1)
 }

So I write the recurrence relation as

T(n) = n * T(n-1)

Which is correct according to this post: Recurrence relation of factorial

And I calculate the time complexity using substitution method as follows:

T(n) = n * T(n-1)  // Original recurrence relation
= n * (n-1) * T(n-2)
...
= n * (n-1) * ... * 1
= n!

But according to this post, here, both recurrence relation and time complexity are incorrect.

What am I doing wrong or not getting correctly?


texts: Does space complexity analysis usually include output space?

texts:
Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this out just by reading examples.

If a function returns a new list, should the space complexity analysis of the function include the space required for the output? There seem to be clear reasons to want to exclude the input from the analysis, but it's less clear if the output should be excluded. Does the architecture of the system matter (e.g. multi-tape turing machine vs modern RAM-based computer)?

Consider the example functions below. They all use O(1) auxiliary space but different output space (relative to the input space), so the overall space complexity changes based on whether or not you include the output space.

generate a new list from a single int input:

int[] random1(int count) {
    Random rand = new Random();
    int[] output = new int[count];
    for (int i = 0; i < count; i++) {
        output[i] = rand.Next();
    }
    return output;
}

Output space: O(2^n)

generate a new list from a list input:

int[] random2(int[] input) {
    Random rand = new Random();
    int[] output = new int[input.Length];
    for (int i = 0; i < input.Length; i++) {
        output[i] = input[i] + rand.Next();
    }
    return output;
}

Size of output: O(n)

modify the input list in place

int[] random3(int[] input) {
    Random rand = new Random();
    for (int i = 0; i < input.Length; i++) {
        input[i] = input[i] + rand.Next();
    }
    return input;
}

Size of output: O(1)


texts: Minimum unweighted anticlique (independent set) cover / partition

texts:
Suppose I have a set of integer intervals, and I want to generate a visualization like the one attached. One obvious way of accomplishing this is to put every interval in its own row; this obviously respects the constraint that no two overlapping intervals are put into the same row, but it is hard to read because the number of rows is $O(\mathrm{\#\,\,of\,\,intervals})$.

In general, I think the minimum number of rows can be calculated by finding the size of the largest clique in the graph whose nodes are intervals that has an edge iff two intervals overlap. Is there an efficient (polynomial-time, approximate if necessary) algorithm, that, given a set of integer intervals, returns a minimum sized partition of the intervals into "y-axis values" such that no two elements of a subset overlap?

I suspect this problem is equivalent to the following (but disregard this if you disagree): is there an efficient way to compute an exact vertex cover $C$ of an interval graph $G = (V, E)$ such that $\forall I \in C. I^2 \cap E = \emptyset$ and $|C|$ is minimized? It seems like this is closely related to the maximum independent set problem.


texts: Let's say you have the following sentence: "This is my first cs question posted here". How would I go about inserting the sentence into a search tree. Do I assign each word a number value and perform the insertions based on those?


texts:
I need to draw the derivation tree for $1-2-(3-4)*5*6$ from the grammar below.
 I want to know how many possible derivation trees are there from this grammar.

$$\begin{align}V_n&=\{expr,term,factor,number\}\\
V_t&= \{(,),-,*,0...9\}\\
P&=\left \{
\begin{aligned}
expr&\to expr-expr\;\mid\;term\\
term&\to term*factor\;\mid\;factor\\
factor&\to number \;\mid\; (expr) \\
number&\to 0\mid1\mid2\mid3\mid4\mid5\mid6\mid7\mid8\mid9
\end{aligned}
\right \}\\
S&=expr
\end{align}
$$

The possibilities that I can find are:

$$(1-2)-(((3-4)*5)*6)\\
1-(2-( ((3-4)*5)  *6))$$

Are there other possibilities?


texts:
Consider the following description of a subproduct tree.

We define a tree T for some points x[0] to x[n-1], and define m = log_2(n).

Tree T is represented as a matrix where each row-column entry i, j is the product of pairwise nodes in the row above it. In total, there are m rows; the 1st row is has n column entries, and the last row has 1 column entry.

In short, how does one compute the coefficients for a large n? Once m > 4, the coefficients of the entries become greater than 64-bits. Consider the product of (x - i) for i = 0 to 15. The coefficients become very large.

Unless we are working in a finite field, it seems as though one cannot construct such a subproduct tree for say n = 2^20.

Formally: http://specfun.inria.fr/bostan/publications/BoSc05.pdf

Addendum:

I understand the complexity of the operation, as stated in the next section of the paper. However, I'm unsure how one would practically approach computing the coefficients of this subproduct tree as size n grows to be large (say 2^20).

Ex, consider the following simple example:


texts: Misunderstanding of an NP-hard problem, $1||\Sigma w_jU_j$, that has polytime algorithm

texts:
The problem $1||\Sigma w_jU_j$ of minimizing the weighted number of tardy jobs in a single machine is NP-hard. This is well known and can be shown by reducing the knapsack problem to it.

Also, when the jobs have arrival times, the problem $1|r_j|\Sigma U_j$ of minimizing the number of tardy jobs in a single machine is NP-hard.

However, I was reading Minimizing the Number of Tardy Job Units Under Release Time Constraints and it proposes polytime algorithms for both problems. Am I missing something?

The only thing that I can think of is that when preemption is allowed, both problems become easy?


texts: Connecting strings in a graph is a PSPACE problem

texts:
We define the following problem as:

Let $M$ be a TM with alphabet $\Gamma$, with $\{a,b,$ #$\} \subset \Gamma$.

We define, for every natural number $n$ the graph $G_{M,n}$ by:

$V_{M,n} = \{a,b\}^n$, the vertices

$E_{M,n} = \{(x,y) : x,y \in V_{M,n} $ and  $M$ accepts the string $x$#$y$ with a run that requires at most $n^{73}$space$\}$

Now define the following language $L$:

$L = \{(<M>, x, y) : x,y \in \{a,b\}^*, |x| = |y|$ and $x,y$ are connected by a path in the above graph$\}$

I want to show $L \in PSPACE$, without using Savitch's theorem.

My attempt:

Define the following algorithm $M_0$

On input $(<M>, x, y)$ with $M$ with the above requirements:

Check if $M$ accepts the string $x$#$y$ in space $|x|^{73}$ or less; if so accept, else go to step 2.
Keep track of the set $Strings = \{x,y\}$ as a second tape.
For every string $z \in \{a,b\}^{|x|} - Strings$, add $z$ so $Strings$ and run $M_0$ on

a. $(<M>, x, z)$

b. $(<M>, z, y)$

If both accept, accept. If all strings in $\{a,b\}^{|x|}$ have not yielded accept, reject.

Now I think it's rather obvious that $L(M_0) = L$ but I'm unsure it solves it in poly. space:

Step 1. requires computing $|x|^{73}$ in unary, which takes poly. space in $|x|$. From here it is known that testing whether a machine accepts a string in some specific space, given in unary, is possible in poly. space when that unary representation is given in the input, using a universal machine. So step 1. requires poly. space in $|x|$.

Each step of the recursion in 2. requires keeping track of the strings tried which is fine. But the depth of the recursion seems to be $2^{|x|}$ which is problematic.

Can you suggest if this solution may still work, or a hint for another?


texts: How to "convert" a top-down solution to a bottom-up algorithm?

texts:
When I'm working on a algorithm problem, I can usually find a top-down solution that works with recursion.

Then for optimization purpose I try to do a bottom-up approach (dynamic programming) to remove the recursion stack, and I struggle. I have a really hard time initializing the array with the correct value, and then fill it with the answers to the sub problems.

Do you have any recommendations / tips on how to "convert" a top-down solution to a bottom-up algorithm?


texts:
I'm trying to learn augmenting paths and I got confused. I've found some other source that has the same setup that my slides have, therefore I will refer to that.
It is said that

Each augmenting path computation can be easily done in O(m) time.

in these lecture notes within a graph of m edges. I could not understand how it is O(m). Isn't trying to find an augmenting path that has capacity from source to the target an exhaustive process? Maybe I misunderstand what they mean as augmenting path computation but even if that is the case, the clarification of that would be helpful