texts: Proving that a language is not Recursive

texts:
I have the following language:

T = {M | there exists w such that M accepts w within |w| steps}

I am trying to prove that this language is not recursive and that it is recursive-enumerable. To prove that it is NOT recursive I considered the following steps:

1) Assume that it was recursive
2) Conside input w of infinite length
3) Meaning, we get infinite steps that M can perform before halting. So we get the halting problem when considering this infinite input, and we are saying that we can decide it
4) halting problem is not decidable. contradiction

What do you think about this proof? I'm not sure that I can consider an infinite length input, and I'm not sure wither turing machines in general should deal with infinite inputs lengths.

I tried to search for answers with no luck so far. Any help would be much appreciated. Thanks.


texts:
There is a matrix of size (M x N) in which the cells are marked by one of the three letters (either 'a','b' or 'c'). Now given that there is only one cell that is marked with value 'a' but more than one cells can be marked with value 'b' or 'c'.

There is 8 ways in which one can move form one cell to another, considering rowwise, columnwise, diagonal and anti-diagonal movements to the next cell. taking the cell marked by 'a' as starting cell and cells marked by 'c' as destination cells. The length of a route is defined as the total number of steps taken while moving from starting to a destination cell without going through the cells marked by value 'b'.

What is the minimum length of the route for a given matrix with all the cells properly marked with values either 'a','b' or 'c'?  I tried using the recursive implementation which basically is taking long time (as it checks all the 8 directions and then it gives the best of them). Can I get a better solution approach may be through DP? Any help is greatly appreciated.


texts: Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states

texts:
How can you prove that any DFA accepting the language generated by the regular expression $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states?
I first attempted induction on $n$.  But I don't even see how to prove the base-case, like if $n=1$.  You need the DFA to take any string and, when it encounters a 0, get set down a track of checking that $n$ characters follow.  If it's fewer than $n$ then fine you reject.  But if there are more characters, to sort of re-set it so that it looks for the first 0 after the earlier one was found.  But DFAs don't have that kind of memory.
And once you've established the base-case, the inductive case doesn't seem clear either.  If you know the result is true up to $n$, then if you consider the regex with $n+1$ then you get a DFA which accepts it.  You intuitively want to remove the accepting states and "move them back" one vertex in the graph.  Now you have a DFA with at least $2^n$ states.  But how do you know that you needed $2^n$ accepting states so that the net number of accepting states is then $2^{n+1}$?


texts:
I am trying to understand the basics of Linked List. The definition of my LinkedList class is as follows:

public class ListNode {
 int val;
 ListNode next;
 ListNode(int x) { val = x; }

Now I am facing a problem. My code is as follows:

ListNode dummy = new ListNode(0);
dummy.next =  head;
ListNode prev = dummy;
ListNode slow = head;
head.next = null;
prev.next = slow;

ListNode temp = slow.next;
prev.next = temp;

System.out.println(dummy.next); //comes out null

Why is it coming out as null? dummy.next was pointing to head and I only changed slow and prev?

Can we use slow and head interchangeably? If yes, then why does this happen?

// head points to a Linked list starting from 1 in 1 -> 2 -> 3
ListNode curr = head;

while(curr.next!= null){
    curr= curr.next;
}

System.out.println(curr);
System.out.println(head); //these are different and head does not change


texts: Assuming finite optimal cost of a specific LP, find an optimal solution directly

texts:
Minimize $\sum^n_{i=1} c_i x_i$ subject to $\sum^n_{i=1} a_i x_i = b$ (a single constraint), $x_i \ge 0$.

Derive a simple test for feasibility of this problem

Assuming the optimal cost is finite, develop a simple method for obtaining an optimal solution directly.

For the first part, I have  $\sum^n_{i=1} a_i x_i = b \iff \text {sgn}(b)=\text{sgn}(a_i)$ for some $i \in \{1,..,n\}$ or $b = 0$.
I have trouble obtaining this simple method for part two. Could someone help me out here?
I know $ -\infty < \sum^n_{i=1} c_i x_i$ and $\sum^n_{i=1} a_i x_i = b$.


texts: Having a formal ISA specification - What does correctness mean?

texts: Does this always mean that a program can be correct in regard to that spec or is there any correctness of the spec itself ?


texts: Finding the private key in BB84 quantum cryptography

texts:
I'm trying to teach myself Quantum Cryptography for an exam I have soon, and I came across the following question:

  To establish a common key, Alice and Bob analyse a sequence of 20 photon pairs. Alice measures the photon sequence: $$1\:1\:0\:1\:0 \qquad 0\:0\:0\:1\:0 \qquad 1\:0\:1\:0\:1 \qquad 0\:1\:1\:0\:1$$ using the random series of detection bases: $$\otimes \oplus \oplus \otimes\otimes \qquad \otimes \oplus \oplus \otimes \otimes \qquad \oplus \otimes \oplus \oplus \oplus \qquad \oplus \oplus \otimes \otimes \oplus$$ while Bob is analysing the photons using the following sequence: $$⊗⊕⊗⊗⊗ \qquad ⊕⊗⊕⊕⊗ \qquad ⊗⊗⊕⊗⊕ \qquad ⊕⊗⊕⊗⊕$$ Hence find the sifted data set they get as an encryption key as in BB84.

Examining all the cases when the detection bases were the same and discarding the bits when they were not; we find that the encryption key is:

$$111\:000\:011\:101$$

Is this the right key?

Note: I apologise if this is in the wrong forum, I'm only really familiar with Math.SE, SO and EE.SE so feel free to migrate this if it's more appropriate elsewhere


texts: Is the language $\{a^n b^n c^i | i \leq n\}$ context free?

texts:
I'm trying to apply the CFL pumping lemma.
And, I've already tried words $a^pb^p$ and $a^pb^pc^p$.
Not sure where to go from here.


texts: Question about 'Software Transactional Memory' by Shavit and Touitou

texts:
I've been reading the paper Software Transactional Memory by Shavit and Touitou. I understand how STM works in general but I need to understand this paper as it is the founding paper of the concept. However, I'm missing something rather fundamental of transactions. When I reed through the paper I never see what happens when a transaction fails. In general STM should retry a transaction when it fails, until it succeeds.

What the paper proposes is the following:

When a transaction starts it acquires the ownership of all the memory locations. Next, it computes the new values of each memory reference and writes them back to global memory. Finally, the transaction releases the ownerships. The transaction has succeeded and returns "success".

If a transaction tries to acquire ownership of a memory reference that is already owned by another transaction it will "help" this transaction by  running the same transaction. But only if the owning transaction is not in the failed state or success state.

A transaction goes into the success state when it has successfully acquired all the locks. It goes into the failed state when

But, nowhere in the paper can I find something about retrying a transaction?

For example, I have applied the pseudocode in the text to this scenario:

Suppose a transaction T1 that wants to run on dataset [A, B, C] and a transaction T2 that wants to run on dataset [C, D, E]. No other transactions are running in the system.

In order of execution:

T1 successfully acquires the locks for A, B and C
T1 now has the state success because it acquired all the ownerships.
T2 wants to acquire the locks for C, D and E.
T2 can not acquire the lock for C.
T2 its status changes to Failure
T2 releases all the ownerships it had (none at the moment)
T2 knows that C is the reference that caused the failure.
T2 executes the same transaction as the process that owns C.
T2 notices that T1 already is in the success state so it aborts.
T1 safely executes its transactions and commits the changes to the global memory

So nowhere in this scenario is T1 executed again?

Any insights are greatly appreciated!


texts: Complement of a DFA without final states

texts: Let $L_1=\{Q,\Sigma,q_0,\delta,Q\}$ be a DFA that accepts a language $L$ and where all the states are also final states. If we want a DFA that accepts the complement of $L$, we swap its accepting states with its non-accepting states, that is $\overline{L_1}=\{Q,\Sigma,q_0,\delta,Q-Q\}$. In this case we have a DFA without final states. Is this still a DFA? Is it regular?


texts: Find distinict elements in an array in $O(n)$ time

texts:
Given this pseudo-code that finds the number of distinct elements in the given array:
D(A) // A is an array of numbers
U_Size = 1
For i=2 to length(A)
                  U=?
  For j=1 to U_Size
    If A[j]=A[i]
     Then U = FALSE
      j = U_Size
   if U = TRUE
     Then U_Size = U_Size +1
         A[U_Size] = A[i]
return U_Size

Time complexity for that alogrithm is $O(n^2)$

I will need to write 2 new algorithms for the same purpose in $O(n)$ according to one of each of the conditions bellow:

let's say that the numbers are integers only and inside the range of [$10,10n$], without using any sorting method
Now, there is no given range of numbers, and I can use any sorting method I want

MY SOLUTION:
for the first condition, I tried using HashSet, but I think it has a
more sofisticated solution. My pseudo-code:
countDistinctNums(int A[], int n)
  hashSet hs = new Hashset
    for i=0 to n
    // add all the elements to the HashSet
      hs.add(A[i])

    // return the size of hashset as it consists of
    // all unique elements
  Return hs.size();

for the second one, a hash table will be the optimal solution but I
think also one of the linear-sorting methods will be good enough

My questions are:

Does HashSet is a good solution for one of the conditions ( or both )?
How do I implement an HashTable for the solution of the second condition?


texts: Sorting a stack of cards with help of a computer

texts:
I have a physical stack of cards, with numbers on them (or, in reality, I have a stack of exams, with students names on them ;)). I want to sort the cards in ascending order.

This is an extremely boring task. I usually use mergesort myself (quick question: what do you use?). But say each card has a QR code. I can scan all the codes as I go through the stack using my mobile phone and then I have the list of cards and the order in which they appear.

What would be a clever way to use this information in order to tell a human how to sort the stack of cards? I imagine that the computer could somehow give me instructions of what to do so as to arrive at the sorted order. Notice that things like "take the 52nd card and place it on the top" are not nice, since I don't want to count to the 52nd card. What would you do?

I realize this question is rather subjective: what constitutes a "nice" strategy depends on the person. I just want to know what kinds of ideas you people could come up with.


texts: Set cover problem and the existence of such cover

texts:
In the set cover problem we want to find in the $\mathbb{S} \subset 2^\mathbb{U}$ the subset $\{s_i\}_{1..k}$, such that $\cup s_i = \mathbb{U}$ for given $K$, where $k \le K$.
But how to reduce the set cover problem to the set covering decision problem (determining whether is there such cover or not)? The same with problems like a TSP is always easy enough: we exclude some elements, check if the needed condition is still met and know already, are these elements needed or not. But it doesn't work here and I am stuck. I would be appreciated if you could give me some hints for this problem.


texts: Complete problems and relativization barriers for nonuniform complexity classes

texts:
Do nonuniform complexity classes like NP/poly have complete problems?

Are there relativization barriers for separations of nonuniform complexity classes?

One way to interpret the second question is by asking whether there are computable languages A and B with (P/poly)^A = (NP/poly)^A and (P/poly)^B != (NP/poly)^B). Assuming the answer to both questions is "no", one reason might be that "computable" has to be replaced by "computable/poly" (whatever that might mean) and that "polytime reductions" for complete problems have to be replaced by "polytime/poly reductions" (whatever that might mean).

Is the answer to the first two questions "no", if we insist on "polytime reductions" and "computable (oracle) languages"? Are there reasonable notions of "polytime/poly reductions" and "computable/poly" languages for which the answers become "yes"?


texts: How to prove that for a full binary tree $T$ there's a series of frequencies such that Huffman alg. will produce $T$?

texts:
How to prove that for a full (each node that's not a leaf has 2 nodes) binary tree $T$ of $n$ leaves there's a series of frequencies $f_1,f_2,...,f_n$ such that if we use Huffman algorithm on the series we'll get $T$?

First in order to get frequencies from $T$ we can assign the probability of $\frac{1}{2^d}$ to each node where $d$ is the depth of a given node. The root node will have the probability of $1$ which means $100$%. After one traversal of $T$ we could fill the array with the frequencies of the leaves of $T$ (only leaves correspond to the the actual values to be encoded).

I'm not sure how to prove that if we apply Huffman algorithm to the frequencies one of the trees will happen to be $T$. It seems like if we build a tree from the frequencies each time such that the new tree is different (if possible) from the previous tree we'll eventually build $T$. Also we know that Huffman tree is always a full tree.

The Huffman algorithm is as follows (as described in Algorithm Design by Jon Kleinberg, Eva Tardos):

Huffman(S) {
  if |S|=2 {
    return tree with root and 2 leaves
  } else {
    let y and z be lowest-frequency letters in S
    S’ = S
    remove y and z from S’
    insert new letter ω in S’ with f_ω=f_y+f_z
    T’ = Huffman(S’)
    T=add two children y and z to leaf ω from T’
    return T
  }
}


texts:
if pipelining is devided to polyfunctional pipelining and monofunctional pipelining(im sorry im not a native speaker the name may be incorect)
and the polyfunctional pipelining is futher devided to STATIC and DYNAMIC, then what is the differance between static and dynamic and what is the overall differance between poly and monofunctional?


texts: What can be learned from the weights in a neural network?

texts:
I'm very new to neural networks, and have been trying to figure some things out.  So, let's say you come across a neural network which has 100 inputs, a hidden layer with 200 nodes, and 32 outputs. Let's also say that you, the "discoverer" of this particular instance of a neural network, are able to read the weights of the individual neurons. What could you figure out about it's function?

1) Are you able to determine what the algorithm or logic is contained within the neural network?  Other than feeding in all possible inputs and studying the outputs it produces.

2) If you were given information about the connection of the neural network (maybe the network isn't fully connected), would solving question one above be easier?


texts: Which class of neural network problem is this?

texts:
I have managed to describe a problem in quantum computing as the optimization of a function f(graph,vector), over graphs and real vectors.
For a given graph, I can optimize the vector with standard methods (say, gradient descent), but the search over graphs has to be a brute force random search, because I don't know what makes a graph 'good' for this application.

In any case, computing the value of f for a given graph and a given vector takes a time of the order of seconds, so even if I already knew good graphs the optimization of the vector would be feasible yet time consuming.

What I would love to try is to train a NN to find good pairs of graphs and vectors. Where do I start from? What kind of NN problem is this?


texts:
From Types and Programming Languages by Pierce

  A term $t$ is in normal form if no evaluation rule applies to it—
  i.e., if there is no $t'$ such that $t -→ t'$.

and

  A term $t$ is typable (or well typed) if there is some $T$ such that $t : T$.

In the pure simple typed lambda calculus:

  we consider another fundamental theoretical property of the
  pure simply typed lambda-calculus: the fact that the evaluation of a well-
  typed program is guaranteed to halt in a ﬁnite number of steps—i.e., every
  well-typed term is normalizable.

Does a term being normalizable mean the same as the term has a normal form?

Here is a term which has no normal form in the untyped lambda calculus:

  Recall that a term that cannot take a step under the evaluation relation is
  called a normal form. Interestingly, some terms cannot be evaluated to a nor-
  mal form. For example, the divergent combinator

  $$omega = (λx. x x) (λx. x x);$$

  contains just one redex, and reducing this redex yields exactly omega again!
  Terms with no normal form are said to diverge.

In the pure simple typed lambda calculus,

is $omega$ typable (i.e. well-typed)?
is $omega$ normalizable?
does $omega$ have a normal form?


texts: Are runtime bounds decidable for anything nontrivial?

texts:
Problem  Given a Turing machine $M$ which has known runtime ${O}(g(n))$ with respect to input length $n$, is the runtime of $M \in {O}(f(n))$?

Is the above problem decidable for some nontrivial pairs of $g$ and $f$?A solution is trivial if $g(n) \in O(f(n))$.

This is related to the problem Are runtime bounds in P decidable? (answer: no). One can derive from Viola's answer that if $f(n)\not \in o(n)$ and $f(n)\not \in O(g(n))$ then the problem is undecidable.

The requirement that $f(n)\not \in o(n)$ is because the $M'$ in Viola's proof need $O(n)$ time to find its input size. Thus Viola's proof could not work when $f(n)=1$.

It would be interesting if we can decide on the run time of sublinear time algorithms. A special case is when we have arbitrary $g(n)$ and $f(n)=1$.


texts: In what sense is the Mandelbrot set "computable"?

texts:
The Mandelbrot set is a beautiful creature in Mathematics.

There are a lot of beautiful images of this set created with high precision, so obviously this set is "computable" in some sense.

However, what concerns me is the fact that it is not even recursively enumerable - simply because the set is uncountable. This could be resolved by requiring some sort of finite representation of the points.

Furthermore, although we know for sure that a lot of points belong to the set and others do not, there are also a lot of points whose membership in the set we don't know. All the images we've seen so far may include a lot of points that "up to n iterations kept in bound," but those points may not actually belong to the set.

So, for a given point with a finite presentation, the problem "Does this point belong to the set?" has not been proved to be decidable yet, if I am right.

Now, in what sense (by which definition) can we say the Mandelbrot set is "computable"?


texts: How to generate stereo image pair from a stationary mono camera?

texts: I have a stationary mono camera which captures a single image frame at some fps. Assume the camera is not allowed to move,how do i generate a stereo image pair of the acquired frame? Is there any algorithms exists for this? If so, do they available in Open-CV?


texts: Finding issues in concurrent implementation of carpark overflow control

texts:
Firstly, I am revising for my Concurrent Programming exam and have come across the following question from a previous exam paper. I have attempted to answer it, and will try and convey this effort; I'm very stuck with this question and not sure how to further progress.

Question

This question is from a 2011 Past Paper from my University created by the Examining Body that year.
Examiners: Professor E K Burke
Dr P Sage
and the internal examiners

  A car park has 100 parking spaces. Because of building work max cars must be accommodated in an overflow area which is accessed via the main car park. Entrance to the main and overflow areas is controlled by two automatic barriers as follows.

  When the car park is empty both barriers are closed.
  Normally, the main barrier is raised as a car approaches and is lowered immediately the car has entered.
  An exception occurs immediately after the main car park is full i.e. when it has 100-max cars in it. As the next car approaches the overflow barrier is raised first, then the main barrier is raised. Once the car has entered the main car park the overflow barrier remains raised and the main barrier is lowered. The normal main barrier action described above then resumes.

  Consider the following program which is intended to control the two barriers.

  All instructions, o1, o2, o3, m1, m2, m3 and m4, are atomic. You may assume that $0 < \max \leq 100$.

int #cars=0;

process Main {
while (true)
 {
 m1: <#cars++>;
 m2: <openMainBarrier>;
 m3: <closeMainBarrier>;
 m4: <if (#cars==100)
     break>;
 }
}

process Overflow {
int max;
o1: <input(max)>;
 while (true)
 {
   o2: <if (#cars==100-max+1)  break>;
   o3: <openOverflowBarrier>;
 }
}

  The program terminates only if both processes terminate. Explain why the program may not terminate.
  Explain why, even if the program does terminate, it may not operate as specified.
  By introducing the use of semaphores, ensure that program does terminate and operates as specified. You must only use atomic instructions. You may introduce new additional non-semaphore variables but you must not alter the scope of #cars and max.

My attempt

Most semaphore exercises I have looked at so far often have the main process in a while(true){...} infinite loop, thus, termination has never been an issue before - it is normally not addressed in these short exercises.

It is because of this I am having difficulty trying to produce an answer for 2) and 3). The question does not even appear to address cars leaving the car park, which leads me to understand this isn't an infinite ongoing cycle type process, but will terminate when both car parks reach maximum capacity?

In this instance, the only thing I can think of is that the process will not terminate in the event the main carpark or overflow carpark does not reach capacity, however I feel this answer is not 'clever' enough and I'm worried I may be missing something.

I have attempted 3) as follows but I am worried this is incorrect as I'm not sure if I am supposed to handle cars leaving the car park, or if I am supposed to ignore that in order to force it to terminate.

OverflowCarPark{
int max;
<input (max)>
while(true){
 down(maxFull)
 if(#cars <= 100 + max){
    down(openMainBarrier)
    up(openOverflowBarrier)
 }
  else { break; }
}

MainCarPark{
<cars++;>
while(true){
 if(#cars <= 100){
    up(openMainBarrier)
  } else if (#cars > 100 + max) { break;
  } else {
    up(maxFull);
    down(openOverflowBarrier);
 }
}

What is the recommended approach to dealing with termination here?


texts: Why does a reduction from a P-problem to an NP-complete problem not show that P=NP?

texts:
Consider the following problem, called BoxDepth:

  Given a set of $n$ axis-aligned rectangles in the plane, how big is the largest subset of these rectangles that contain a common point?

Say we proved these two statements:

There is a a polynomial-time reduction from BoxDepth to MaxClique.
There is a polynomial-time algorithm for BoxDepth with $O(n^3)$ runtime.

Why don’t these two results imply that P=NP?


texts: Typical set in Shannon's source coding theorem

texts:
I was following the textbook by David Mackay: Information theory inference and learning algorithms.

I have question on asymptotic equiparition' principle:

  For an ensemble of $N$ $i.i.d$ random variables $X^N=(X_1,X_2....X_N),$ with $N$ sufficiently large, the outcome $x=(x_1,x_2...x_N)$ is almost certain to belong to a subset of $|A_x^N|$ having only $2^{NH(x)}$ members, with each member having probability  "close-to" $2^{-NH(x)}$.

And then in the textbook, it also says that typical set doesn't nesscarry to contain the most probable element set.

On the other hand, "smallest-sufficient set" $S_{\delta}$ which defines to be:

  the smallest subset of of $A_x$ satisfying  $P(x\epsilon S_{\delta})\ge 1-\delta $, for $0\leq{\delta}\leq1. $  In other words, $S_{\delta}$ is constructed by taking the most probable elements in $A_x$, then the second probable......until the total probabily is  $\ge1-{\delta}$.

My question is, as $N$ increases, does $S_{\delta}$ approaches typical set such that these two sets will end up be equivalent of each other? If the size of the typical set is identical to the size of $|S_{\delta}|$,  then why are we even bother with $S_{\delta}$? Why can't we just take the typical set as our compression scheme instead?


texts: NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?

texts:
I have seen some problems that are NP-hard but polynomially solvable in fixed dimension.

Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer Linear Programming with fixed number of variables or constraints by Lenstras result.

Questions:

What are other examples of NP-hard problems that become polynomial time solvable if the dimension is fixed?

Are there problems for which this is not the case?

Is this always the case for problems that admit an FPTAS/pseudo-polynomial time algorithm such as Knapsack?


texts: Where is simply typed lambda calculus on the Chomsky hiererchy?

texts:
The functions definable in untyped lambda calculus are the computable functions, for which it is in turn possible to define equivalences to the concepts of Turing machines, recursive enumerability and Type-0 grammars.
But what about typed lambda calculus -- where on the Chomskian computability hierarchy are the functions definable by expressions of simply typed lambda calculus?
That is assuming that there is a natural way of transferring the idea of lambda-definability of a recursive function from untyped to simply typed lambda calculus, along the lines of:

A $k$-ary number-theoretic function $f$ is simply-typed-lambda definable iff there is a simply typable $\lambda$-term $P$ such that for all $x_1, \ldots x_k$, where $\underline{x}$ is the encoding of $x$, $P \underline{\vec{x}} =_\beta \underline{y} \text{ iff } f(\vec{x}) = y$, if $f(\vec{x})$ is defined, and $P\underline{\vec{x}}$ has no $\beta$-normal form othewise.

--- Transition from number-theoretic functions to formal languages ---
As pointed out in the comments, in order to apply lambda calculus to the concept of formal languages at all, one will have to ensure that the respective data types are actually expressible. Here are my thoughts:
I am assuming here Curry-style simply typed lambda calculus with no primitive types or constants, only term variables in the language and type variables in the type system.

Letters of the alphabet can be mapped to natural numbers by a simple enumeration,
Numbers can be encoded in lambda calculus e.g. via Church numerals,
Strings can be encoded as lists (using constructions such as $\text{cons}, \text{head}, \text{tail}$)
Booleans can be represented as Church booleans,
Boolean functions can be constructed using the if-then-else combinator, taking as an input the result of some number-theoretic function argument and outputting a truth value,

all of which, as well as the applications arising in the construction, are (as far as I can see) simply typeable, so that it is possible to define a lambda term that takes as an input an encoding of a string and returns as an output a boolean value.
The interesting question then is, it seems, what exactly can happen (i.o.w.: what is definable) in the if-then-else combinator to sort the wheat from the chaff, in such a way that the function term expressing this algorithm is still simply typable.
With this, I guess my question becomes:

Between which levels of the Chomsky hierarchy is the class of languages located such that $L$ is in the class iff there is a simply-typed-lambda-definable function $f$ such that $f(w)$ is defined if and only if $w \in L$?

With that, do we even need booleans, or is it enough to have a function do whatever to its input and we only need to distinguish whether or not it reduces to any normal form at all, independently of the type of the output?
In case I made a mistake in my encoding idea, the additional question arises of whether simply typed lambda calculus is capable of performing an appropriate encoding at all, where in the negative case the answer would be that there is simply no such definable function $f$ and hence the class will be empty?

--- Alternative formulations ---
Alternatively, are there other ways of building a correspondence between typed lambda calculus and formal languages or automata that makes it possible to locate it on the known computability scale in a meaningful way?
Or other interesting intuitions about the computational power of typed lambda calculus, other than that it is decidable?
All I could find so far was about modifications of lambda calculus corresponding to certain types of grammars, or automata to recognize strings of certain kinds of lambda expressions, but, surprisingly, nothing specifically about the computability complexity of typed lambda calculi.
I am primarily interested in Curry-style simply typed lambda calculus, but if there is anything interesting to say about e.g. polymorphic typed lambda calculus, I would be happy to learn about that, too.


texts:
I got stuck with this problem since the whole day.

When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading selecting the maximum of the edge weight or the alternate path from the other vertex.

So, we are able to solve this problem because of topological sorting which can be done only for acyclic graphs. Thus this type of question can be solved only for acyclic graph.

Now, if I present another case. What if all the edge have the same weight and we don't look in the cycle of the graph. Is this solvable. Everytime I think about this I don't see any use of topological sorting if we can choose any source considering we have to choose the maximum number of nodes(longest path).

Is this also NP Hard or can we solve this?


texts:
According to wikipedia , Definition of In-order Traversal on Binary Tree :-

1) Check if the current node is empty or null.
2) Traverse the left subtree by recursively calling the in-order function.
3) Display the data part of the root (or current node).
4) Traverse the right subtree by recursively calling the in-order function.

I want to find the similar In-order Traversal definition on Ternary Tree. I was referring the Professor Robert Sedgewick's lecture of Ternary Search Tries.
I found that if I do the In-order traversal on the Ternary Search Tree(a type of Trie data structure) for a particular searched string then visiting order of nodes should be :-

1) Check if the current node is empty or null.
2) Traverse the left subtree recursively calling in-order function.
3) Display the data part of the current node.
4) Traverse the middle subtree by recursively calling the in-order function.
5) Traverse the right subtree by recursively calling the in-order function.

Now , while solving one homework problem , I got different result from the given solution.
The problem was :- Find the In-order Traversal of the following tree :-

According to me answer should be :- AKBJCLIEDHFG
But given answer is :- AKBJCLIDEHFG

I also faced one similar question in one competitive exam as :-

According to me , Answer should be :- $QSPTRUWV$
But given answer is :- $SQPTRWUV$
Please verify whether my answers are correct or not and If I am wrong somewhere then please correct me.


texts:
I know that an equation
$$a^x \equiv b \pmod{p}$$
can be solved for $x$ in $O(\sqrt{p} \ log(p) )$ time using meet-in-the-middle technique, which relies on fact that we can rewrite the equation as follows:
$$a^{nk} \equiv ba^{h} \pmod{p},$$ where $nk - h = x$.

I want to know whether one can solve the following equation (relatively) effectively:
$$(a^x \bmod p) \equiv b \pmod{q} $$
where $p, q$ are primes and $p > q$.  I don't see how one can rewrite this one to apply meet-in-the-middle.

Problem source: I've been reading about Digital Signature Algorithm and I want to write a program that finds signature $(r, s)$ using public key only (for toy numbers), which can be done by solving for $r, s$ the following equation $$(r^s \bmod p) \bmod q = (g^{H(m)}y^{r} \bmod p) \bmod q$$


texts: Explanation of Tag, Index, and Offset in Direct Mapping Cache

texts:
I'm going through an exercise trying to store address references into a direct mapped cache with 128 blocks and a block size of 32 bytes.  The address are 20000, 20004, 20008, and 20016 in base 10.

When I start to store them, I realize that the offset is the only value that changes.  All of the examples I find determine hits and misses based on the target and index values, without mention of offset.  What is the purpose of the offset?  If the tag and index are in the cache, is it a hit regardless of the offset? Or is the offset also looked at?


texts: Find the minimum subset of a set of numbers with product divisible by a given integer

texts:
The following problem was part of a local programming contest I attended..(I solved it via the obvious Brute Force solution)
I was wondering whether there was a cleaner Dynamic Programming solution.
Problem Statement:
You have an array $a$ of $n$ integers and an integer $k$. Your task is to find a subset $m$ of a where the following 2 conditions hold:
1) $\prod\limits_{x\in m}x \equiv 0\mod k$.
2) Size of $m$ is minimal possible (size of $m \gt 0$).
Constraints:
$1 \le n \le 10^4$
$1 \le a_i \le 10^9$
$2 \le k \le 10^9$
Time Limit = 3 seconds
Memory Limit = 256 MegaBytes
(I am a beginner in the concept of DP, so I am looking for a detailed explanation and if possible. some code.  Thanks in advance :D)


texts: If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine?

texts:
Suppose, I wanted to verify the solution to $2$^$3$. Which is $8$.

The $powers~of~2$ have only one 1-bit at the start of the binary-string.

Verify Solution Efficently

n = 8
N = 3
IF only ONE 1-bit at start of binary-string:
  IF total_0-bits == N:
   if n is a power_of_2:
     OUTPUT solution verified, 2^3 == 8

A solution will always be approximately $2$^$N$ digits. Its not possible for even a non-deterministic machine to arrive to a solution with $2$^$N$ digits faster than $2$^$N$ time.

Question

Can this problem be solved efficently in non-deterministic poly-time?
Why not if the solutions can be verified efficently?


texts:
My textbook shows that when setting up a recursion tree for a recurrence, like

$$T(n) = 3T\big(\frac{n}{4}\big) + cn^2$$

you place the cn^2 term at the root to represent the cost of at the top level of recursion and the three subtrees of the root represent the costs incurred by the subproblems of size n/4.

Why do you place cn^2 at the root? How do you know that the term cn^2 should be at the root of the recursion tree?


texts: Hardness amplification of PRFs by increasing key length

texts: I was reading the GGM construction for PRFs and wondering the relation between key length and hardness. GGM construction does not seem to yield any significant improvements. Are there any PRF constructions which take into account key length for increasing hardness? Alternatively, are there any constructions which transform a $(t, \epsilon)$ PRF of key length $k$ to something like $(t^2, \epsilon)$ PRF of key length $2k$ or $k^2$?


texts:
How can one formally prove

$L \cdot L^{*} = L^{+}$

It looks obvious to me since with the concatenation you get rid of $\varepsilon$, but I cannot think of a formal proof through induction or something.


texts:
for my current project I am working with decision tables that uses expression to determine conditions. Currently the decision tables support FEEL expressions. A simple example table using feel expressions is shown below:

| visitors |           season            | dish  |
|    <4    |  "spring", "winter", "fall" | Veal  |
|  [4..8]  |       not("summer")         | soup  |
|    >8    |  "spring", "winter", "fall" | beans |
|    -     |          "summer"           | steak |

I think the table is pretty straight forward. The number of visitors determines the type of meal in any other season than summer, while in the summer the number of visitors is irrelevant.
In the example also shows the limits of complexity of the FEEL expression language. For example the not("summer") is the same as "spring", "winter", "fall".

in the future, more complex conditions have to be allowed. The use of dates for example, and it should be possible to determine if the date is in the future or not. You might expect an expression like:

Date(input) > Date.Today                    // date is in the future
Date(input).DayOfWeek != DayOfWeek.Sunday   // date cannot be a sunday
Round(input) > 10                           // the float rounded must be larger than 10

The problem we have is that the users that will use and fill these tables will be smart, but will not be able to understand code, So i cannot use straight out code as expressions.

My question is if there already is an expression language that helps user express convey functional requirements to inputs, much like the FEEL expression language, but more complex? Or can I expect to create my own expression language, by expending the current FEEL expression language.

EDIT:

I hope that i can clarify what I'm looking for in my request below. I also update the link to the language elements page.

What I hope to find is a expression language that is helps translate between unspecified code logic and human readable text. Users should be able to understand the written expression written as they will be able to read and edit the table values directly. The programming language responsible for executing the functions is not important at this point.
The complexity of the functions will be what is shown above. Feel only has limited expressions that does not support this. Other functions will be included: check if date is in the future/past/present, check if date falls on a weekend, regex pattern matching on strings, AND & OR logic

Thanks for all the feedback so far, I will definitely look at the links.


texts: Comparison using only bitwise operators (and return -1 or 0)

texts:
I have to use only bitwise operators to compare two numbers (represented in two's complement), and return $-1$ (represented by all $1$'s) if the numbers aren't equal or return $0$ (represented by all $0$'s) otherwise.

Say $a$ and $b$ are $W$ bits long ($W$ is not necessarily $2^n$). I find it easy to find out if both numbers are equal using $\mathsf{XOR}$: just do it like $a\ \mathsf{XOR} \ b$ and I will obtain $0$ (all $0$'s) if the two are the same. However I stuck at trying to get $-1$ when the two numbers differ, since the result of $\mathsf{XOR}$ just says which position of the two numbers differ and I have no idea how I should turn a non-zero number into $-1$.

How can I convert a non-zero number into $-1$ in two's complement representation (all bits set to $1$), while keeping it $0$ when it's not non-zero, which is a step further for the simple $\mathsf{XOR}$ comparison?

Edit: In the situation this question was originated from, subtraction was not a native operator which could be directly used. The 5-operation solution from @Evil and the answer from @D.W. should also be perfectly right when an extended collection of operators, like the subtraction, were implemented.


texts: Find an edge that is completely visible from point outside a polygon (Convex Hull)

texts:
I want to implement algorithms from this paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.5609&rep=rep1&type=pdf

In particular, I am currently dealing with the one in section 2.2.1. In page 4 (first paragraph), one algorithm step is as follows:

Find an edge $(v_k, v_{k+1})$ of $P_i$ ($P_i$ is a convex hull) that is completely visible from $s_i$ ($s_i$ is a point outside the convex hull).

My question is, how can I find a completely visible edge of a convex hull, that is completely visible from a point outside the convex hull?


texts: Finding unique topological ordering wrt to another vertex ordering

texts:
Given a directed acyclic graph with $n$ nodes labeled from $1$ to $n$, what is an efficient way to produce the unique topological ordering with lower labeled nodes prioritized over higher labeled?

In other words: in the ordering the node labeled $1$ appears as early as possible, and if there are many such orders, among them choose the order(s) where the node labeled $2$ appears as early as possible, and so on producing the unique order in the end.

I tried to apply Kahn's algorithm. Instead of picking nodes arbitrary, choose ancestors of node $1$ from nodes with in-degree zero. Among those, choose ancestors of node 2, and so on. However, I don't know whether this idea can be efficiently implemented.

Choosing the lowest labeled node does not work: a counterexample is the DAG with the nodes 1, 2, 3 and 4, and edges 3 -> 1, 2 -> 4 and 4 -> 1. If we choose the lowest-numbered node, we get the ordering (2,3,1,4) but the ordering we look for is (3,1,2,4).


texts:
I have a question whether or not CSS and HTML are regular languages.

I believe CSS is a regular language, since it should be possible to create a regular expression to match the structure of CSS.

However, I believe that HTML is not a regular language since you have nested attributes that could be defined recursively.


texts:
I have learned the Master's Theorem from the CLRS textbook (2nd Edition), the form of the Master Theorem given in the above text is associated with the proof of each and every case. So at the end I know how it works and it also explains the intuition behind the same.

The form of Master Theorem given in CLRS is as follows:

  (Master theorem) Let $a \geqslant 1$ and $b > 1$ be constants, let $f(n)$ be a function, and let $T (n)$ be deﬁned on the nonnegative integers by the recurrence

  $T(n) = aT(n/b)+ f (n)$ ;

  where we interpret $n/b$ to mean either $\lceil b/n \rceil$ or $\lfloor b/n \rfloor$. Then $T(n)$ has the following asymptotic bounds:

  If $f(n)=O (n^{log_ba - \epsilon})$ for some constant $\epsilon > 0$, then $T(n)=\Theta (n^{log_ba})$.
  If $f(n)=\Theta (n^{log_ba})$, then $T(n)=\Theta (n^{log_ba}lg n)$
  If $f(n)=\Omega (n^{log_ba + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leqslant cf(n)$ for some constant $c < 1$ and all sufﬁciently large n, then $T(n)=\Theta (f(n))$.

Now there is also a version of Master Theorem which is claimed as The Advanced Master Theorem by few sources on the web and also they claim that this version is more powerful than the one in the CLRS text.

  $T(n) = aT(n/b)+\theta(n^{k}log^{p}n)$

  where $n$ = size of the problem

  $a$ = number of subproblems in the recursion and $a \geqslant 1$

  $n/b$ = size of each subproblem

  $b > 1 , k \geqslant 0$ and $p$ is a real number.

  Then,

  if $a > b^{k}$, then $T(n) = θ(n^{log_ba})$
  if $a = b^{k}$, then

  if $p > -1$, then $T(n) = θ(n^{log_ba} log^{p+1}n)$
  if $p = -1$, then $T(n) = θ(n^{log_ba} log log n)$
  if $p < -1$, then $T(n) = θ(n^{log_ba})$

  if $a < b^{k}$, then

  if $p \geqslant 0$, then $T(n) = θ(n^{k} log^{p}n)$
  if $p < 0$, then $T(n) = θ(n^{k})$

I could not find a text from where this has been taken, as a result I do not even know whether it is valid or not and without knowing its validity it shall be dangerous to apply it. If anyone has encountered the second version of the theorem, it shall be helpful if the name of the standard text book from which this second version has been given, is shared here. I want a proof of the second version of the Master Theorem if at all it exits and if so a one to one correspondence between the cases of the theorem given in the CLRS and that in the second version. Moreover the second version seems have used $\theta$ instead of $\Theta$ and if that is the case the second version only seems to  cover case $2$ of the CLRS version which has $f(n) = \Theta(...)$


texts: How does one formulate a backtracking algorithm

texts:
I am new to learning algorithms.
I was reading backtracking algorithm for generating all strings for n bits.
If I dry run the program I know the program is giving right result.
But I didn't understood the logic can anybody please explain? What I mean is what will be be the thought process to arrive at this solution

void binary(int n)
{
    if(n < 1)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1] = '0';
        binary(n-1);
        A[n-1] = '1';
        binary(n-1);
    }
}


texts: How does this use of "apply" in Coq work?

texts:
I'm working my way through software foundations. In the Chapter titled "Tactics", I'm able to prove this theorem in Coq:

Theorem silly_ex :
     (∀ n, evenb n = true → oddb (S n) = true) →
     oddb 3 = true →
     evenb 4 = true.
Proof.
  intros H1 H2. apply H2.
Qed.

Even though I was able to get through the example, I don't understand how that is a solution. After performing intros H1 H2 I'm left with proving that evenb 4 = true. The two hypotheses I have at this state are H1 : forall n : nat, evenb n = true -> oddb (S n) = true and H2 : oddb 3 = true.

How can apply H2 solve this? Even knowing that 3 is odd doesn't fulfill the antecedent of the conditional.


texts: Solving Recurrences via Characteristic Polynomial with Imaginary Roots

texts:
In algorithm analysis you often have to solve recurrences. In addition to Master Theorem, substitution and iteration methods, there is one using characteristic polynomials.

Say I have concluded that a characteristic polynomial $x^2 - 2x + 2$ has imaginary roots, namely $x_1 = 1+i$ and $x_2 =1-i$. Then I cannot use

$\qquad c_1\cdot x_1^n + c_2\cdot x_2^n$

to obtain the solution, right? How should I proceed in this case?


texts: Partition a multiset into pairs that sum up to given numbers?

texts:
Given a multiset of $2m$ positive numbers, $S=\{s_1,s_2,\ldots,s_{2m}\}$ and given $m$ targets $t_1,t_2,\ldots,t_m$. Can we partition $S$ into $m$ pairs $(a_i,b_i)$ such that $a_i+b_i=t_i$, where $a_i\ne b_i$ and $a_i,b_i\in S$?

For example for $S=\{1,4,6,1,2,5\}$ and $t_1=7$, $t_2=t_3=6$. The answer is YES and the pairs are $(1,6)$, $(2,4)$, and $(1,5)$.


texts: Is implementation of approximate dynamic maximal matching feasible?

texts:
I'm wondering if algorithms described in:

https://ieeexplore.ieee.org/abstract/document/7782946/

http://drops.dagstuhl.de/opus/volltexte/2014/4845/

easy to implement. They seem to mention the word "simple" but I'm not sure if this is all just theoretical play of "who's going to find the best $O$", or if this can be implemented in a sane amount of time (a couple of weeks).


texts: Does "serializable" also mean that it's lockable

texts:
Here's an final exam question for a Database Fundamentals class. I've read the book, stuff online.. I can't figure out if "serializable" also means that the schedule is lockable or not. What I mean is.. I understand that for the schedule to be isolated, you have to have non-conflicting reads & writes, but then it also says "if the transactions are not isolated(i.e., serializable).."

By determining if the schedule is isolated, does this include determining if locks(lock-W(x), lock-R(x)) and unlocks can be placed inside the schedule, is "serializable" both isolated and lockable?

lockable - can locks and unlocks be placed inside the schedule at appropriate R/W-intervals.

Here's the question:

  a). Two transactions are shown below. The statements of the transaction are executed from top to bottom. Specify whether the current schedule meets the Isolated property of ACID and why or why not. If the transactions are not isolated (i.e., serializable) specify what concurrency problem may occur with this schedule. Be specific about what statement(s) in what transaction(s) causes the issue.

$$
\begin{array}{}Time&Transaction \, 1&Transaction \, 2
\\1&Read(B)&Read(B)
\\2&\_&Update(C = C + B)
\\3&Read(C)&\_
\\4&\_&COMMIT \, or \, ROLLBACK
\\5&Update(A=B+C)&\_
\\6&COMMIT\, or \, ROLLBACK&\_\end{array}
$$


texts: Lazy way of comparing ISA on code length

texts: I hope this is not too broad. I need to evaluate about 8 different ISA targets for about 12 specs. The only metric I'm intersted in is size of the output bytecode. Moreover, I'm only interested in relationship between code size for different targets, so I don't particualarly care about optimizing the code. My background is in the hardware engineering, so I don't relish the prospect of going into LLVM backend too deep. Is there an easier way to generate (non-optimal) byte code for different ISA targets?


texts: Efficient method for generating the smoothing function

texts:
The smoothing function of a boolean function with respect to one of its variables is the disjunction of its cofactors. For example given a Boolean function F(a,b,c) the cofactors with respect to a are F(0,b,c) and F(1,b,c), the smoothing function with respect to a therefore is G(b,c) = F(0,b,c) + F(1,b,c).

Now, given a circuit for F, one simple method for creating the circuit for G is to make two copies of the circuit for F, hardwire the inputs for a as 0 and 1 in the two circuits respectively and then OR the outputs. However this will double the number of gates needed. If one needs to do this for several variables, then the size of the resulting circuit grows exponentially in the number of variables removed. What bothers me the most about this is that we are creating simpler functions (as judged by the number of variables and consequently the size of the truth table) with increasing number of gates. This leads me to think that maybe there is a well known way for creating a circuit for the smoothing function using fewer gates than in the original circuit.

For the purpose of this question, let us assume that the truth tables are too big to enumerate and the functions under consideration are not linear.


texts: Prove the time complexity of this algorithm of finding longest subarray with maximum value in the middle

texts:
I'm trying to find time complexity $T(n)$ of the algorithm by a given pseudocode:

1: for i:=1 to N do
2: begin
3:   len := 1
4:   while i - len >= 1 and i + len <= N do
5:   begin
6:     if a[i] > a[i - len] and a[i] > a[i + len] then
7:       len := len + 1
8:     else
9:       break
10:   end
11:   print(i, len)
12: end

I know that the answer is $T(n) = O(n\log n)$ but I struggle to prove that.

From the pseudocode its clear that this algorithm is designed to find the longest subarray with each element smaller then the middle one. (actually this algorithm prints the length of such array for each array element)

I can't prove it formally because I struggle with the content-dependent loop at 5-10, but informally I went like this:
Lets construct the array which will be the worst case for this algorithm.

For the sake of simplicity lets use array with 15 elements and start with array filled with zeros:
$$0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0$$
external loop will execute 15 times and each time the loop 5-10 will perform a single comparison
Now we will do the following: we divide array in two and put maximum value in the middle. Then for each half we will do the same, except the value will be decresed by 1.

We will get the following array:
$$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0$$

Now, intuitively I can see why this is the worst case for the algorithm and where $logn$ comes from, but I can't prove it properly.

As a side note I would appreciate any pointers toward where one can practice these kind of problems (concrete algorithms time complexity analysis, preferably with answers/explanations)


texts:
For the proof of Chernoff Bounds (upper tail) we suppose δ<2e−1 .
Like in this paper ([see this link ]) 1. Can you tell me why ?


texts:
Does the term schema, in the context of describing a structure, refer to the actual structure of the data, or the description of this structure? I.e. can I talk about the schema of an entity without a schema language?

For example, suppose I am writing documentation for some JSON API, that always returns a particular structure, say:

{
   "name" : "jeroen",
   "age" :  28
}

Can I say that the schema for the payload returned by this API includes required values for "name" and "age"? Or does the term exclusively refer to another document that formally describes this structure using a schema language of some sort? In that case, what is another appropriate term to refer to the recurring pattern in the structure?

The Github API, has a section titled schema: http://developer.github.com/v3/#schema. However, the word schema is not mentioned in the text itself, nor do they use any schema language. This would suggest that schema is just a general term for the structure/attributes of the output. Unless they consider english as a schema language, in which case the entire page is a schema. Hmmm.


texts:
Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?

I think the answer is yes but i'm unable to find a computation that standard Turing machine can do but this machine can't.

Any ideas?


texts: Are Time-sharing and multi-tasking operating systems same or different

texts:
My question is regarding time-sharing and multi-tasking systems.

Time-sharing operating system assigns time slot to each task while multi-tasking OS runs various jobs in parallel.

But as I get it, on a single processor system, time-sharing is the only way to achieve multi-tasking.  (I don't know if I am correct on this premise.)

So, are time-sharing and multi-tasking system same or different.
And if they are different, then what are the key differences (particularly on a single-processor/single-core system with no hyper-threading support etc) ?

Thanks


texts: proof that BFS remains total after adding edge to graph

texts:
I'm trying to prove that if $G$ is a connected graph, then $BFS(u\in G)$ is total (i.e. it visits all the vertices of $G$).

The inductive proof consists in 2 cases:

(i) Prove that $\rm{BFS}$$(u \in \rm{G'})$ is total, where $\rm{G'} = G \cup (u,v) \quad u,v \in G$

(ii) Prove that $\rm{BFS}$$(u \in \rm{G'})$ is total, where $\rm{G'} = G \cup (u,v) \quad u \in G, v \not\in G$

I'm stuck at (i).

If I add a new edge $(u,v)$ to $G$, the $BFS$ will remain the same until it reaches $u$ or $v$, then it will add $v$ or $u$ to the queue (where one of them wouldn't be there). I understand that every other member of the queue is there, but there will be one more, so ignoring the fact that there is a new vertex in the queue, the $BFS$ will run in every other vertex just like it should.

How can I show formally that this new vertex in the queue will not interfere in the fact that the $BFS$ is total?


texts:
I'm trying to find an optimal solution that will work for the bridge crossing problem. In case you don't know it you can check out the Ted Ed video on it. They show how you can do it with 5 people but I'm trying to see if there is a way to do it with n number of people. The same rules apply but the optimal solution should be found regardless of how many people there are or what their individual walking speeds are.

These are the conditions of crossing the bridge:

Only 1 or 2 people can cross the bridge at the same time in the same direction.
The speed of the two people crossing is the same as the slower one.
It is night and there is only one flashlight.
The people passing the bridge must carry the flashlight.
The flashlight cannot be thrown over the bridge so it must be carried back to the other end of the bridge.


texts:
Godel proved there are true statements in arithmetic that can't be proven true in any sufficiently strong Formal Axiomatic System (FAS). The authors of this paper use similar arguments to prove there are TM's that belong to a certain complexity class that cannot be proven to belong to that class. They refer to these type of algorithms as "hidden machines".
ON THE EXISTENCE OF HIDDEN MACHINES IN COMPUTATIONAL TIME HIERARCHIES
What happens to the quesion of P?NP if there exists a TM that can solve any satisfiable 3SAT instance in polynomial steps, yet, it is impossible to prove this TM does so?


texts: what is the significance of the word "Sub-problems" in Greedy Method?

texts:
With respect to Dynamic Programming we make a statement that :

  Greedy algorithm have a local choice of the sub-problems whereas
  Dynamic programming would solve the all sub-problems and then select
  one that would lead to an optimal solution.

Now in Dynamic Programming we have some problem with recursive nature which we solve by solving the sub-problems and then obtain the global optimum but in case of Greedy approach we do not solve the problem in any recursive nature rather we find a feasible solution at every stage with the hope of finding optimal solution.

So I am unable to get the notion of sub-problems in case of Greedy Approach .


texts: What are the potential uses of a good R.N.S. system?

texts:
We can consider a Residue Number System (R.N.S.) that has efficient operations for add, multiply, and compare between two numbers.

A more rigorous definition

We can suppose that we can perform the operations above between two non-negative integers $x$ and $y$ with $x \ge y$ in time proportional to $O(x\log(x))$ with $O(\log(x^2))$ memory.  Or further, if it would possibly allow even more uses, if we could perform these operations in time linear with respect to $x$ and $y$.

What are the potential uses of this system?

For example, cryptology often uses fairly large numbers, and makes use of such a system.  Also, linear programming and systems of linear equations can make use of an efficient R.N.S.  Also, specialized processors can have R.N.S.'s built in, and could potentially compete with standarized Boolean processors.

What additional uses would this efficient system allow?


texts: DFAs can be encoded as input/output for a neural network?

texts:
I would encode DFAs (Deterministic Finite State automata) as output (or input) of a neural network for a supervised learning; it is well-known [1] that efficacy of neural network training strongly depends on adopted encoding.

How can I encode DFAs for a neural network? Are there any literature works?

I've already found some algorithms being able to extract a DFA from a recurrent neural network, but nothing about DFAs either as input or output of ANN.

[1]: Neural network encoding approach comparison: an empirical study; Investigating the Effect of Data Representation On Neural Network and
Regression; Data Mining and Neural Networks: The Impact of Data Representation.


texts: Little-O: $\forall c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in \mathbb{N}, n ≥ n_0 ⇒ g(n) \leq cf(n)$

texts:
So I'm assuming everyone's familiar with the definition of Big-O:
\begin{align}
    ∃c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in N, n \geq n_0 ⇒ g(n) ≤ cf(n)
\end{align}

Here is a variation of this: $\text(Little-O)$:
\begin{align}
\text{Let $f, g : \mathbb{N} → \mathbb{R^{≥0}}$. We say that $g$ is little-oh of $f$, and write $g ∈ o(f)$, when:}\\ \forall c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in \mathbb{N}, n ≥ n_0 ⇒ g(n) \leq cf(n)
\end{align}

As you can see, this is a stronger property than Big-O, in the sense that if $g \in o(f)$, then $g \in \mathcal{O(f)}$. Basically, we switch to universal quantification leading to a more powerful claim. In general, if the statement $\forall c \in \mathbb{R^+}, P(c)$ is true, then $\exists c \in \mathbb{R^+}, P(c)$ is also true. While $g \in \mathcal{O(f)}$ says (colloquially) that “it is possible to scale up $f$ so that it eventually dominates $g$,” $g \in o(f)$ says that “no matter how you scale $f$ (up or down), it will always eventually dominate $g$.” Or, in terms of rates of growth, $g \in \mathcal{O(f)}$ means that $g$ grows at most as quickly as $f$, while $g \in o(f)$ means that $g$ grows strictly slower than $f$. I hope you get my gist.

Can someone please prove the following challenge question for me? It would be much appreciated and I've been at it for a long time now.

Prove the following statements about Little-o:

Prove that for all positive real numbers $a$ and $b$, if $a<b$ then $n^a \in o(n^b)$.
Prove that for all functions $f, g : \mathbb{N} → \mathbb{R^+}$, if $g \in o(f)$ then $f \notin \mathcal{O(g)}$.

I see that in the $2^{nd}$ part they've restricted the range of $f$ and $g$ to exclude $0$ and that we are to use only the definitions of Little-o and Big-o in order to prove both statements.


texts: Relational calculus expression for projection (Database Management)

texts:
I recently came across this question:

Let the following relation schemas be given:

$R=(A,B,C)$

$S=(D,E,F)$

Let relations r(R) and s(S) be given. Give an expression in the tuple relational
calculus that is equivalent to the following:

a. $\pi_A(r)$

The solution provided is:

$\{t|\exists q \in r(q[A]=t[A])   \}$

But according to me, the solution should have been:

$\{t|\exists q \in r(t[A]=q[A])   \}$

Can anyone please help me in fiding out where my error is, or whether I am correct??

Thanks in advance.


texts: Find string patterns preferably in regex for string streams

texts:
I am trying to classify the data in a database columns. DB has about 90 million entries.The main goal is to find different patterns in columns to leverage it for create look alike data. The data columns has entries which can easily look like patterns as :

 CUST1212,CUST1213,CUST1214...,  number sequential after CUST
 CODE1213,CODE1242,CODE1289...   random numbers after code
 CUST1213,MUST8324,FIFA12313...
 009-123-2123,003-124-2314,006-213-5322,
 INTER122,INTER222,INTER322...,  number increasing in batch of 100
 OM|ON|TO, IO|OI|UH...,  pipe delimited
 some 6 and 7 digits number.

The issue is there are so many patterns and looks like creating patterns manually based on data is out of option.

I would really appreciate if one can point to how can I build a collection of patterns preferably by usage frequency.

What I started is 1. Segregate the data as per their length as patterns usually generate same string length, sorted them and stored them in different files. 2. Then classifying them further as per Alphabet prefix or numeric prefix. 3. For alpha-prefix segregate further on common alphabets at start.

Now seems I am lost and sincerely hoping if one can point out to me what are my options and probably best to took.

I believe if end of computation if get something like patterns in data and their frequency e.g. CUST[0-9]{4} -> 10k times, [a-zA-Z]{4} -> 50k times [0-9]{3}-[0-9]{3}-[0-9]{4} 10K times etc....., it would be great.

Thanks


texts: Sufficient condition for $xy^*z \subseteq L$ for a DFA with $n$ states

texts:
In chapter 2 of the New Turing Omnibus, the author considers an unknown finite automata with 6 states. Through trial and error, it is deduced that the words 0101, 0100101, 0100100101 are accepted. It is then stated that using the pumping lemma, it can be shown that if 01(001)^n01 is accepted for n=0,1,2,3,4,5 then all strings of the form 01(001)*01 must also be accepted.
I know of the pumping lemma but do not see how the next leap has been made. Why is it sufficient to only test n up (number of states) - 1?


texts: How to construct an NFA Ai for the given Regular property P1 and P2?

texts:
Let AP = {a; b; c}.
Consider the following regular safety properties:
(a) P1: If a becomes valid, afterwards b stays valid ad infinitum or until c holds.
(b) P2: Between two neighbouring occurrences of a, b always holds.
Construct an NFA Ai for each property Pi such that L(Ai) = BadPref(Pi).
Hint: You may use a symbolic NFA with propositional formulae over the set AP as
transition labels.

In the above question,

What is symbolic NFA?
What would be the propositional formula for P1 and P2?
How to construct an NFA from the above two statement?
Are there any concrete steps to do it?

The NFA for bad prefixes would be just the negation of an NFA right?
I have the solution for it, but I don't understand how did they arrive at the solution.
It would be great if somebody could explain or provide a link on how to do it?
Note: I hope it's not related to LTL since it is not part of the syllabus. Anyways, I believe that one can only construct NBA from the LTL or CTL formula right?
Thank you very much.


texts: Printing values of psuedo random numbers in a range

texts:
I wanted to write a program to print the values of pseudo random numbers in a range. So, i wrote the following:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
 int i=0,x;
 while(i!=10)
{
    srand(time(0));
    x=rand()%51;
    if(x>=30&&x<=45)
    {
    printf("%d\n",x);
    i++;
    }
}
return 0;
}

But this program is printing some random number between 30 and 45 10 times(the same value, say 33 ten times). Can someone please explain the flaw in this?


texts:
Less Hashing Same Performance: Building A Better Bloom Filter (Kirsch and Mitzenmacher) mentioned that we can use

  $ g_i(x) = (h_1 (x)+ih_2 (x))\pmod{p}$, where $h_1(x)$ and $h_2(x)$ are two
  independent, uniform random hash functions on the universe with range
  ${0, \dots , p − 1}$, and throughout we
  assume that $i$ ranges from $0$ to $k − 1$.

However, I notice that if $h_2(x) = 0$, all of the hash function $ g_i(x)$ will be all the same as it will become

$ g_i(x) = h_1 (x)\pmod{p}$

In the case of bloom filter, where there is only one table to update, when $h2(x)=0$, only one location will be inspected. I believe that this will make the accuracy of Bloom Filter for certain value will be worse than other values.

Do we need to have an extra clause to bump the function by $ci$ where $c$ is a constant so that it becomes

$ g_i(x) = (h_1 (x)+ih_2 (x) + ci)\pmod{p} $ ?


texts:
Right now I am working on a distributed system that sends messages from single source to many nodes. It is necessary that certain messages are sent to the same node to ensure order of processing. Using simple hashing on an important piece of the message to decide which node to send to works but leads to significantly uneven distribution. This is because some sets of messages may only occur 10 times in a day, while others might occur 1,000,000 times.

I came upon the idea to instead of use hashing, find average message counts for each recurring type (there are thousands) over a reasonable amount of time and then attempt to organize them into as-even-as-possible sets for each node. This way each node will receive a similar amount of messages.

A simple case with 2 nodes and 4 items explains this:

message_counts_by_type = [1,3,7,9]

desired result:

[
    [1,9],
    [3,7]
]

Now each node has an even amount of messages (10)

My naiive solution (which gives this result) was to break the set of message type counts into sets the size of the number of nodes

[[1,3],[7,9]]

and then select which item to give to what node with a rotating index so that on one run node1 will get the lowest number and node2 will get the highest, and on the next run the opposite.

Here it is abstracted to n nodes in python:

counts = [1,3,3,6,7,...9999]
nodes = 8

chunks = [ counts[i:i + nodes] for i in range(0,len(counts), nodes)]
# [ [1,3,3], [6,7,9] .... [9997, 9997, 9999] ]

counter = [i for i in range(0,nodes)]
# [ 1, 2, 3... nodes ]

slots = [[] for _ in counter]
# [ [], [], [], .... [] ]

for i in range(0, len(chunks)):
        chunk = chunks[i]
        for j in range(0, len(chunk)):
                slots[j].append(chunk[counter[j]])

        # rotate counter array
        # [ 1, 2, 3, 4] -> [ 4, 1, 2, 3 ]
        counter = [ counter[i-len(counter)] for i in counter ]

# get final count of each set/node
reduction = [ reduce((lambda x, y: x + y), slot) for slot in slots ]

Anyways, even though it works (better results than just hashing) I feel like this is naive and there is probably a smarter way to accomplish the same thing.

Any ideas/criticism?

Thanks.


texts: Distributive property with sum types and product types

texts:
In Philip Wadler's presentation, "Category Theory for the Working Hacker", something confused me. At about 30:52, he says:

  We need this additional construct which is called distributivity. Here it is, right? It just says "given a choice of an A or a C and a choice of a B or a C, we can get a choice of an A or a B and a C."

This is shown on the slide as:

  $$ (A + C)\times(B + C) \cong (A + B) \times C $$

Is this correct? I have the following doubts about it:

I think that, in Boolean algebra, the distributive property would give $ (A + C)\times(B + C) = (A \times B) + C $.
Given a choice of an A or a C and a choice of a B or a C, we might choose C both times, giving us only a C and a C. For example, in Haskell:

    data AorC = ACA A | ACC C       -- sum type
    data BorC = BCB B | BCC C       -- sum type
    data Prod = Prod AorC BorC      -- product type
    cAndC = Prod (ACC c1) (BCC c2)  -- choose type C both times


texts: Grammatical characterization of deterministic context-free languages

texts:
Deterministic context-free languages are commonly defined using an automaton concept, the (restricted, deterministic) pushdown automaton. To some that is confusing, as the name context-free refers to a grammar type.

I seem to remember there exists a characterization of the DCF languages using grammars. In my recollection it used a complicated equivalence on non-terminals. Can anyone provide a pointer to that work?


texts: Depth of a pipeline in a CPU's architecture

texts: I follow a course on CPU architectures and I'm making exercises at the moment. Now I encountered the word "depth of a pipeline" in one of the exercises, but I don't know what's meant by the depth of a pipeline. Is it the number of stages of the pipeline or something else? I can't find it anywhere in the syllabus.


texts: How do I find a regular expression for a particular language?

texts:
I have a language, and I want to find a regular expression for the language.  How do I do that?  Is there a step-by-step, systematic procedure for that?  Pretend I am just learning this topic; what approach can I use?

If it helps, you can assume the language is given in English (e.g., something like "$L$ is the set of words that contain at least one $a$, an even number of $b$'s, and does not contain the substring $ab$") or algebraically (e.g., $L=\{a^i b^j (abb)^k : i+2j+k=3\ell, i,j,k,\ell \in \mathbb{N}\}$).

This is intended as a reference we can point others to. Please explain your method in a form that someone new  can understand it.


texts: In shift reduce parsing why the handle always eventually appear on top of the stack and never inside?

texts:
I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the excerpt where the authors try to justify why stack is the best data structure of shift reduce parsing. They said that it is so because of the fact that :
$\dagger:$"The handle will always eventually appear on top of the stack, never inside."

The Excerpt

This fact becomes obvious when we consider the possible forms of two successive steps in any rightmost derivation. These two steps can be of the form
$$(1) S \xrightarrow[\text{rm}]{\text{*}} \alpha Az \xrightarrow[\text{rm}]{\text{*}} \alpha\beta Byz \xrightarrow[\text{rm}]{\text{*}} \alpha\beta\gamma yz $$
$$(2) S \xrightarrow[\text{rm}]{\text{*}} \alpha BxAz \xrightarrow[\text{rm}]{\text{*}} \alpha Bxyz \xrightarrow[\text{rm}]{\text{*}} \alpha\gamma xyz $$
In case $(1)$, $A$ is replaced by $\beta By$, and then the rightmost nonterminal $B$ in that right side is replaced by $\gamma$. In case $(2)$, $A$ is again replaced first, but this time the right side is a string y of terminals only. The next rightmost nonterminal $B$ will be somewhere to the left of $y$.
Let us consider case $(1)$ in reverse, where a shift-reduce parser has just reached the configuration
$$\begin{array}{rcl} \text{STACK} & \text{INPUT} \\ $\alpha\beta\gamma & yz$ \\ \end{array}$$
The parser now reduces the handle $\gamma$ to $B$ to reach the configuration
$$\begin{array}{rcl} \text{STACK} & \text{INPUT} \\ $\alpha\beta B & yz$ \end{array}$$
$\require{color}\colorbox{orange}{Since $B$ is the rightmost nonterminal in $\alpha\beta B yz$, the right end of }$ $\require{color}\colorbox{orange}{the handle of $\alpha\beta B yz$ cannot occur inside the stack. The parser can}$ $\require{color}\colorbox{orange}{therefore shift the string $y$ onto the stack to reach the configuration}$
$$\begin{array}{rcl} \text{STACK} & \text{INPUT} \\ $\alpha\beta B y & z$ \end{array}$$
in which $\beta B y$ is the handle, and it gets reduced to $A$.
In case $(2)$, in configuration
$$\begin{array}{rcl} \text{STACK} & \text{INPUT} \\ $\alpha\gamma & xyz$ \end{array}$$
the handle $\gamma$ is on top of the stack. After reducing the handle $\gamma$ to $B$, the parser can shift the string $xy$ to get the next handle $y$ on top of the stack:
$$\begin{array}{rcl} \text{STACK} & \text{INPUT} \\ $\alpha B xy & z$ \end{array}$$
Now the parser reduces $y$ to $A$.
In both cases, after making a reduction the parser had to shift zero or more symbols to get the next handle onto the stack. It never had to go into the stack to find the handle. It is this aspect of handle pruning that makes a stack a particularly convenient data structure for implementing a shift-reduce parser.

My reasoning and doubts
Intuitively this is how I feel that the statement in $\dagger$ can be justified :
If there is an handle on the top of the stack, then the algorithm, will first reduce it before pushing the next input symbol on top of the stack. Since before the push any possible handle is reduced, so there is no chance of an handle being on the top of the stack and then pushing a new input symbol thereby causing the handle to go inside the stack.
Moreover I could not understand the logic the authors have given in highlighted portion of the excerpt justifying that the handle cannot occur inside the stack, based on what they say about $B$ and other facts related to it.
Please can anyone help me understand the concept...


texts: Is there a name for this priority queue data structure?

texts:
While watching a sports tournament, I noticed that the tournament tree looks a lot like a heap. I came up with the following data structure: A complete binary tree where the leaves are elements of some set, and each internal node is the $\max$ of its two children. I came up with a BuildHeap algorithm that's $O(n)$, a GetMax algorithm that's $O(1)$, an Insert algorithm that's $O(\log n)$, and a Delete algorithm that's $O(\log n)$. The number of nodes in this "heap" is $2n-1$ where $n$ is the number of elements in the underlying set. The structure is simpler than a binary heap.

Is there a name for this data structure?

[edit]

Code:

import Data.List
import Data.Ord

data Heap a = Leaf a | Branch a (Heap a) (Heap a) deriving Show

getMax :: Heap a -> a
getMax (Leaf x) = x
getMax (Branch x _ _) = x

leaf :: Ord a => a -> Heap a
leaf = Leaf

branch :: Ord a => Heap a -> Heap a -> Heap a
branch h1 h2 = Branch (max (getMax h1) (getMax h2)) h1 h2

buildHeap :: Ord a => [a] -> Heap a
buildHeap xs = fst $ buildSubHeap (length xs) xs
  where buildSubHeap 1 (x:xs) = (Leaf x, xs)
        buildSubHeap n xs = let (leftSubHeap, remainder1) = buildSubHeap (div n 2) xs
                                (rightSubHeap, remainder2) = buildSubHeap (n - div n 2) remainder1
                            in (branch leftSubHeap rightSubHeap, remainder2)

insertIntoHeap :: Ord a => a -> Heap a -> Heap a
insertIntoHeap x (Leaf y) = branch (leaf x) (leaf y)
insertIntoHeap x (Branch m h1 h2) = branch h2 (insertIntoHeap x h1)

deleteInsignificantElement :: Ord a => Heap a -> Heap a
deleteInsignificantElement (Branch _ (Leaf x) (Leaf y)) = Leaf (max x y)
deleteInsignificantElement (Branch _ h1 h2) = branch (deleteInsignificantElement h2) h1

getInsignificantElement :: Ord a => Heap a -> a
getInsignificantElement (Branch _ (Leaf x) (Leaf y)) = min x y
getInsignificantElement (Branch _ h1 h2) = getInsignificantElement h2

replaceMax :: Ord a => Heap a -> a -> Heap a
replaceMax (Leaf x) y = Leaf y
replaceMax (Branch m h1 h2) y | getMax h1 == m = branch (replaceMax h1 y) h2
                              | getMax h2 == m = branch h1 (replaceMax h2 y)
                              | otherwise = undefined

deleteMax :: Ord a => Heap a -> Heap a
deleteMax heap = replaceMax (deleteInsignificantElement heap) (getInsignificantElement heap)

data HeapObserver a = Singleton a | PushHeap a (Heap a) deriving Show

popHeap :: Ord a => Heap a -> HeapObserver a
popHeap (Leaf x) = Singleton x
popHeap heap = PushHeap (getMax heap) (deleteMax heap)

undown :: Down a -> a
undown (Down x) = x

heapsort :: Ord a => [a] -> [a]
heapsort [] = []
heapsort xs = map undown . flattenHeap . buildHeap . map Down $ xs
  where flattenHeap heap = case popHeap heap of
                           Singleton y -> [y]
                           PushHeap y ys -> y : flattenHeap ys

example_list = [234,234245,13235,14223,12,5,41,24,132,4134,25,234, 94875937, 34059, 784, 34875, 234, 765, 909]

main :: IO ()
main = print (heapsort example_list == reverse (sort example_list))


texts: In the object oriented programming  concepts I found the term "Identity of object". What does it mean by "Identity of object"?


texts: Is there a faster algorithm for constructing the adjacency list of this graph?

texts:
My problem is to find a better algorithm to fill the adjacency list.

specs:

G = (V , E ) //the graph
V ={w} //vertex in this case each vertex is an array
E={⟨u,v⟩| u,v ∈V ∧ u>v} // edge only if u > v
u > v only if  foreach i u̸=v ∧ u[i]≥v[i]. // (u>v and v>w => u>w)

my naive code whit complexity O((v+1)*v/2) ≈ O(n^2) is

private void riempiAdj() {
    for(int i=0;i<nodi.length;i++)
        for(int j=i+1;j<nodi.length;j++)
            if(nodi[i].eMaggiore(nodi[j]))
                nodi[i].adj.inserisci(nodi[j]);
}

nodi is the array of vertex

adj is the adjacency list

AdjList.inserisci(Vertex t) add a vertex t into adjacency list O(1)

Vertex.eMaggiore(Vertex t) returns true in this > t O(1)

exist an algorithm whit complexity of O(v) or O(v*log()v)?


texts: Which data structure to use for accessing min/max in constant-time?

texts: I need a data structure which can include millions of elements, minimum and maximum must be accesable in constant time and inserting and erasing element time complexity must be better than linear.


texts: What are the implications of Homotopy Type Theory?

texts:
I've recently come across the topic of homotopy type theory and I'm interested to learn more. I have a very limited background in type theory.
Can anyone tell me, in functional programming terms or through practical examples, how exactly is HoTT going to change the way we view mathematics, and what are the implications of HoTT on proof assistants? Thanks!


texts: How do we know any problem is in NP-complete if we don't know all problems in NP?

texts:
A problem is NP-complete if:

It is in NP.
All problems in NP can reduce to it.

It's number 2 that I'm concerned with here. I would be highly surprised if we knew  every problem in NP. Based on that assumption, how do we know for sure that any problem is NP-complete? For example, how do we know that there's not some problem we don't know of that will reduce to the Boolean Satisfiability problem, but not the Clique problem? Or would such a problem be NP-Intermediate and therefore need P != NP to exist?


texts: Finding a Simple Distribution In a Binary String

texts:
Unsupervised feature discovery of text that started with its bit string representation would need to discover octets were the first-order parse of such a bit string.  This raises a question:

What is the technique called that can discover that a binary string, for example:

0100100111110010101010101011111011001000111000100101110001111110111010111110010111001010100011111110001101100101001010101111000111101011010011111001111101001111101011111011110011011001111000010100110001

has the simple model (with A x B meaning A occurs B times in the bag):

{00 x 1, 01 x 2, 10 x 3, 11 x 4}

even though it knows only that it should group bits in substrings (tokens) of the same bit length (ie: it doesn't know it should group bits in pairs)?

That is to say, if the binary string input was generated by a perl program:

for(0..100){print ( (('00') x 1, ('01') x 2, ('10') x 3, ('11') x 4)[rand(10)])}

the technique would reject, as less predictive, the distribution (model):

{0 x 7, 1 x 13}

and it would also reject a model that used 2 bit tokens on odd-numbered bit boundaries, as well as models that used 3 bit, or longer, tokens.

A related, more difficult technique, would find the model for a string generated by sampling the bag:

{0 x 1, 1 x 1, 00 x 1, 01 x 2, 10 x 3, 11 x 4}}

That is to say the bit string is a mix of token sizes.


texts: Getting sum of all numbers contained in substrings of S on a segment

texts:
I have a string of digits $S$ and K queries $l_i, r_I$ - get the sum of all numbers contained in segment of $S$ from $l_i$ to $r_i$.

For example, $S$ = 1034, $l = 1$, $r = 3$. So answer will be $1 + 10 + 103 + 3$ (note: $03$ was not counted, as it starts with $0$)

It has an obvious solution with $O(K\cdot N)$ performance, but I need the faster one. It looks like I need to use segment tree for storing these sums, but I can't figure out how to do it when $|\ S\ |>2$. If it's possible to use segment tree I'll get an $O(K\log{N})$ solution, it'll be great.

Any ideas of how to use segment tree here?


texts: Is their a better algorithm for winning a 4*4*4*4 variant of ultimate tic-tac toe?

texts: For rules please refer to https://www.hackerrank.com/challenges/ultimate-ttt .I have implemented minimax search with alpha-beta pruning. There is a time limit of 15 seconds.Which algorithms would yield better results?


texts: How to Formally define $\delta$ in a DFA?

texts:
I have made a draw of a DFA, and I have to formally define the automaton in the following format. Let $A$ be the necessary automaton :
$$A=<\Sigma,Q,q_0,\delta,F>$$

Where $\Sigma=\{a,b,c\}, Q=\{q_0,...,q_4\}, F=q_3$ and $q_0$ is the initial state.

The drawing is attached to this post:

Can I do something like $\delta_{A}(q_0,\sigma)=q_1$ for each state? should I unite a few states together?

Thank you!


texts: Hitting probability of random walk within given number of steps

texts:
Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates.

What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially?

We can travel to 4 neighbors.

that is ( i , j+1 ), ( i , j-1 ), ( i-1, j ), ( i+1 , j ) if they are inside the matrix.

If there are only 3 neighbors which are inside the matrix then the probability with which we will go to that neighbor is 1/3(for each of the three).

How to solve this problem?
I am able to find the solution for exactly k steps.

for exactly k steps problem,
I make a matrix, dp[m][n][k+1];
initial all values are zero

except dp[x][y][0]=1;

dp[a][b][q]= weighted average of probablity of neighbours.

for example dp[0][0][4] = 0.5 * dp[1][0][3] + 0.5 * dp[0][1][3];

answer will be dp[i][j][k];


texts: Local Search Optimization Algorithms in Applied Settings -- How best to explain to applied researchers?

texts:
I realize this may be an opinion-based question, but relevant nonetheless in my opinion.
Context:
I have a local search optimization algorithm, A.
I designed A to address a specific biological question.
A returns many local optima and often gets stuck near said optima.
My target audience (biologists) don't understand this. They want a single plausible answer (the global optimum) or at least many plausible answers (local optima) with low variability. The reason for this is that biologists will need to incur high cost and large effort to reach their end goal. They feel uneasy that A returns many plausible solutions.
Specifics:
The problem faced by the biologists revolves around sampling. Specifically, they would like to know, given current sampling levels, how much more sampling is required to estimate genetic diversity within species.
Unfortunately, there is no means of comparison with other algorithms because this problem hasn't been thought about in a computational light before. Biologists just sample randomly in the field. Crude estimates of necessary sample sizes range from 5-10 individuals, but sometimes only 1-2 can be reasonably collected (due to say, species rarity and/or project budget).
Algorithm A suggests sample sizes 1-2 orders of magnitude larger than the crude estimate, but the variability is large.
For instance, A might suggest anywhere from 200-250 individuals should be sampled to capture 95% of existing genetic variation for a given species.
All plausible sample sizes returned by A are close to the required 95% cutoff, yet the variation in the estimates themselves is quite large.
The makes the biologists uncomfortable because it suggests that A is not very good.
One way I try to frame things is with the analogy of climbing a mountain or hill. We want to get to the top (the global optimum), but there are a lot of obstacles (local optima) in the form of ridges and valleys in the way.
Putting this into a more CS-centric context:
The Travelling Salesman Problem (TSP) is an NP hard problem of great theoretical interest. For this reason, TSP is often solved via local search (e.g., simulated annealing (SA) or genetic algorithms (GA)). Since both SA and GA are stochastic, they will return different routes each time the algorithm is run.
Clearly, the shortest route is targeted. If many local routes are possible, why use local search in the first place?
I realize the answer to the about question is "to get a 'good enough' solution in a finite amount of computation time". However, this doesn't fit well with applied researchers.
Put another way:
In the case of TSP, why would an airport rely on a local search algorithm to find the optimal path if this could mean wasted money and resources?
My question: How can we justify the use of local search algorithms with the same kind of behaviour as A to researchers in very applied fields who otherwise lack math/stats/computer science knowledge?


texts: Why is writing down mathematical proofs more fault-proof than writing computer code?

texts:
I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs.

It seems that this is something more widespread than just my experience. Most people make software bugs all the time in their programming, and they have the compiler to tell them what the mistake is all the time. I've never heard of someone who wrote a big computer program with no mistakes in it in one go, and had full confidence that it would be bugless. (In fact, hardly any programs are bugless, even many highly debugged ones).

Yet people can write entire papers or books of mathematical proofs without any compiler ever giving them feedback that they made a mistake, and sometimes without even getting feedback from others.

Let me be clear. this is not to say that people don't make mistakes in mathematical proofs, but for even mildly experienced mathematicians, the mistakes are usually not that problematic, and can be solved without the help of some "external oracle" like a compiler pointing to your mistake.

In fact, if this wasn't the case, then mathematics would scarcely be possible it seems to me.

So this led me to ask the question: What is so different about writing faultless mathematical proofs and writing faultless computer code that makes it so that the former is so much more tractable than the latter?

One could say that it is simply the fact that people have the "external oracle" of a compiler pointing them to their mistakes that makes programmers lazy, preventing them from doing what's necessary to write code rigorously. This view would mean that if they didn't have a compiler, they  would be able to be as faultless as mathematicians.

You  might find this persuasive, but based on my experience programming and writing down mathematical proofs, it seems intuitively to me that this is really not explanation. There seems to be something more fundamentally different about the two endeavours.

My initial thought is, that what might be the difference, is that for a mathematician, a correct proof only requires every single logical step to be correct. If every step is correct, the entire proof is correct. On the other hand, for a program to be bugless, not only every line of code has to be correct, but its relation to every other line of code in the program has to work as well.

In other words, if step $X$ in a proof is correct, then making a mistake in step $Y$ will not mess up step $X$ ever. But if a line of code $X$ is correctly written down, then making a mistake in line $Y$ will influence the working of line $X$, so that whenever we write line $X$ we have to take into account its relation to all other lines. We can use encapsulation and all those things to kind of limit this, but it cannot be removed completely.

This means that the procedure for checking for errors in a mathematical proof is essentially linear in the number of proof-steps, but the procedure for checking for errors in computer code is essentially exponential in the number of lines of code.

What do you think?

Note: This question has a large number of answers that explore a large variety of facts and viewpoints. Before you answer, please read all of them and answer only if you have something new to add. Redundant answers, or answers that don't back up opinions with facts, may be deleted.


texts: When two siblings in a heap are equal, how do you bubble down?

texts:
I have a heap where both child nodes of the root are 10, and I'd like to perform an operation to remove the min value 9.

I proceed to replacing the root with its next of kin, 18. However when I bubble down, I am unsure of which direction to take.


texts: Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?

texts:
I was working through a textbook (Probability & Computing by Michael Mitzenmacher & Eli Upfal) and am not able to understand the following:

  Let $F(x)$ be given as a product
  $F(x) = \prod_{i=0}^{n} (x - a_i)$. Transforming $F(x)$ to
  its canonical form by consecutively multiplying the $i$th monomial with the product of
  the first $i-1$ monomials requires $\Theta(n^2)$ multiplications of coefficients.

A canonical form of a polynomial is $\sum_{i=0}^{n} c_i x_i$.

Why does this take $\Theta(n^2)$ time?


texts:
What is the time complexity of this algorithm? I assume that is $O(3^n)$

n=3
recLoop(int n)
{
    for(int i=0; i<3; i++)
    {
        if(n>0)
        {
             recLoop(n-1);
        }
        count++;
    }
}

n 0 1 2 3 4

count 3 9 27 81 243

From this, I get $O(3^{n+1})$

If I change my algorithm to:

recLoop(int n)
{
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<2; j++)
        {
            count++;
        }
    }
    for(int i=0; i<3; i++)
    {
        if(n>0)
        {
            recLoop(n-1);
        }
        else
            count++;
    }
}

From first nested loops $O(nm)$ so what is the total complexity of this algorithm?

n 0 1 2 3 4

count 9 33 105 321 969

The possible solution is a bit hard for me to understand and to translate my problem. I need a bit more description of my problem.


texts: In completely fair scheduler in Linux, how to calculate the initial virtual run time of a process

texts: I am trying to implement a completely fair scheduler. I want to know how to calculate the initial value of virtual run time of a process in order to insert the process into a red black tree


texts: Real-valued genetic algorithm offspring out-of-bounds

texts:
I have a fairly simple real-valued genetic algorithm that seems to work fairly well, however it currently has some issues that I'm hoping to get some help with. If we consider a 1-dimensional problem, I use the following method to produce 3 children/offspring $(c_{1,2,3})$ from 2 parents $(p_{1,2})$:
$$c_{1} = 0.5p_{1}+0.5p_{2}$$
$$c_{2} = 1.5p_{1}-0.5p_{2}$$
$$c_{3} = -0.5_{1}+1.5p_{2}$$

For example, if we consider a problem where the bounds are $0\leq x\leq 10$, and I have 2 parents with $x$-values given by $p_{1} = 2.55$ and $p_{2} = 9.92$, then we produce 3 children with the following $x$-values:

$$c_{1} = 6.235$$
$$c_{2} = -1.135$$
$$c_{3} = 13.605$$

As can be seen, child 1 will always be within the problem bounds since it's simply an average of its parents, however children 2 and 3 have $x$-values that are outside the bounds of the problem $(0\leq x\leq 10)$. As such, what I then do is simply have a loop that adds 1 to the value of child 2 and subtracts 1 from the value of child 3 until they go back within bounds, and then carry on with the rest of the algorithm. But this seems like a "cheap trick". As such, I was wondering if better methods are used to deal with children/offspring that have values outside of the problem bounds, or if my method is actually acceptable.


texts: How to prove that this language is not regular?

texts:
Given a language $L$ over the alphabet { 0, 1, [, ,, ] } where if $x \in L$ then $x$ is of the form $[x_0, \dots, x_n]$, in which each of the $x_i$ represents unique binary strings (so $x_i = x_j$ only when $i=j$). Prove that this is not a regular language.

Here is what I have. I have used the pumping lemma.

Suppose $L$ is a regular language. Let $M$ be the DFA that accepts $L$. Let $p$ be the pumping length of $L$. Given $x = [x_0,\dots,x_p] \in L$ we see that $|x| > p$ so pumping lemma applies, so $x = UVW$ where $|UV| < p$, $|v| > 0$, and $UV^iW \in L$.

Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x_i$. Therefore we have reached a contradiction, which shows that $L$ is not a regular language.

Is this a correct proof? If not, what can I do to improve it?


texts:
I am currently working through Metaheuristics by El-Ghazali Talbi where he discusses encodings of algorithms.
"Messy representations: In linear representations of fixed length, the semantics
of the values is tied to its position in the string. In messy representations, the
value associated with a variable is independent of its position. Then, each
element of the representation is a couple composed of the variable and its value.
This encoding may have a variable length. It has been introduced to improve the
efficiency of genetic operators by minimizing their disruption."
I have been unable to find a example problem where the representation has been used.

Does anyone know where these representations are commonly used?
Can someone point me towards a paper or repository with a code
example?


texts: Examples of random deployment in wireless sensors networks

texts:
I have been doing some research and have found a lot of papers on the subject of random deployment in wireless sensor networks, but I haven't found a single example of its usage. Has it been used before? What could be a very concrete context in which it could be used?
Thanks in advance.


texts: swapping between sorting algorithms for small input size left over

texts:
Is it suggested to swap between sorting algorithms? Merge sort certainly performs better on large input size however Insertion sort performs better on small input size

  Analysis based on there graph comparison of running time of Insertion sort and merge sort

How often people swap the algorithms they are using? For example sorting problem of size 100K with merge sort and then switching to insertion sort when problem size reached to 500 input size?

Is is advisable to follow such techniques? For small input size the constants(c) does matter and insertion sort having small constant size than merge sort will certainly perform better. I guess


texts: Dimension Reduction - Which feature should remove to reduce the dimension of the matrix

texts:
Let's suppose that we have the following 2 tables:

If we want to reduce the dimension by one(in every table) which feature we should remove and why ?

I am confused about the way that i should work generally in this type of problems.


texts: How much more powerful are regexes in modern programming languages compared to regular expressions from the theory of computation?

texts: Are the ones in modern programming languages equivalent to, say, Context-Free Grammars or is there an intermediate (between finite automata and CFGs) set of languages that it covers?


texts: Inequalities in a multicommodity min-cut max-flow theorem

texts:
I am reading this classic paper by Klein, Plotkin and Rao titled Excluded Minors, Network Decomposition and Multicommodity Flow.

In section 3, Theorem 3.1, they define $\hat \ell(vw) = \lceil \ell(vw)/C\rceil$, where $C$ is the sum of capacities of edges, and $\ell: E \to \mathbb R^+$ is a length function.
$dist_\ell(s_i, t_i)$ is the shortest path length from $s_i$ to $t_i$ w.r.t. $\ell$, and $dist_\hat \ell(s_i, t_i)$ is w.r.t. $\hat \ell$.
Also, there is a constraint that $\sum_{vw \in E} \ell(uw) u(vw) = 1$, where $u(vw)$ is the nonnegative capacity of the edge. (So $\sum_{vw \in E} u(vw) = C$)

Then they claim that:

$dist_\ell (s_i, t_i) \le (1/C)dist_\hat \ell (s_i, t_i)$
$\sum_{vw \in E} \hat \ell(vw) u(vw) \le 2C$

However, ignoring non-integral parts, it is the case that $\hat \ell(vw) \approx (1/C) \ell(vw)$. So, it seems to me that the inequalities should have "$C$s on the other sides", or the $\hat \ell$ should have been defined as $\hat \ell (vw) = \lceil C \cdot \ell(vw) \rceil$.

Can anyone explain this to me?


texts: Regularity of the exact middle of words from a regular language

texts:
Let $L$ be a regular language.
Is the language $L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \}$ regular?

I know it's very similar to the question here, but the catch is that it's not a simple substring of a word in a regular language, but rather an "exact middle" - we have to count the prefix and suffix length.

Therefore, I assume it's not regular, but I couldn't find a way to prove it. I also couldn't think of any way to modify the NFA of $L$ to accept $L_2$.