texts: in O(n) time: Find greatest element in set where comparison is not transitive

texts:
Title states the question.

We have as inputs a list of elements, that we can compare (determine which is greatest). No element can be equal.

Key points:

Comparison is not transitive (think rock paper scissors): this can be true: A > B, B > C, C > A (note this is not a valid input since there is no valid answer here, I'm only describing what "non-transitive comparison" means)
Each input array will is guaranteed to have an answer
greatest means the element must be greater than every other element
Converse property holds i.e. A > B implies that B < A

Example:

Input: [A,B,C,D]
A > B, B > C, C > A
D > A, D > B, D > C
Output: D

I cannot figure out a way to do this in O(n) time, my best solution is O(n^2).

I get stuck on every approach because of the fact that to be certain of an answer, the element needs to be explicitly compared to every other element, to prove it is indeed the answer (because comparison is not transitive).

This rules out the use of a heap, sorting, etc.


texts: How can I integrate an android app with expert systems using SWI-Prolog?

texts:
I want to build an expert system that runs on android. I am using Android Studio as my development tools and I already started to build the knowledge base using SWI-Prolog. I want to take the result from the prolog and show it in the android program. Do I need API or there is a direct way that I can communicate between the prolog and the android program ?

Thanks.


texts: How to design a turing machine for a context-free grammar? what are the steps?

texts:
How to design a Turing machine for a context-free grammar? what are the steps? for example, What are the steps to design a Turing machine for the following grammar with alphabet $\{a,b\}$.

$S\rightarrow aX\mid b$
$X\rightarrow bS\mid aX\mid \varepsilon$

This is what I come so far for the above example, in the link, any help appreciated.


texts: Count elements in the real world in constant time by weighing them

texts:
I suppose that counting n elements should be linear time, right? It takes double time to count double number of elements. But in the real world, it is faster and O(1) to weigh elements and find out the total weight so in the real world you can count n elements O(1) just by putting all the elements on a scale and dividing by the weight of one elements.

Is my reasoning correct that physically it is possible to speed up a calculation by this trick, or am I mistaken?


texts: Test data for tasks that communicate over network

texts: I am working on a load balancer that schedules tasks that communicate over network. I want to test its performance, but I'm struggling to find test data for it. Currently I try to extract relevant data from google-cluster 2019 (https://github.com/google/cluster-data), microsoft azure (https://github.com/Azure/AzurePublicDataset) and alibaba (https://www.alibabacloud.com/blog/594340). Maybe there is already such test data that I can use?


texts: Why are functional languages Turing complete?

texts:
Perhaps my limited understanding of the subject is incorrect, but this is what I understand so far:

Functional programming is based off of Lambda Calculus, formulated by
Alonzo Church.
Imperative programming is based off of the Turing machine model, made
by Alan Turing, Church's student.
Lambda calculus is as powerful and able as the Turing Machine,
meaning they are equivalent in computational power.

If functional programming is based off of Lambda Calculus and not the Turing machine, then why are some (or all) of them described to be Turing complete, and not Lambda complete or something like that? Is the term "Turing completeness" special in any way to Turing machines, or is it just a word?

Lastly, if imperative languages are based off of the Turing Machine, and computers are basically Turing machines, without infinite memory, does that mean they perform better than functional programming languages on our modern PCs?

If that's the case, then what would be the equivalent of a lambda calculus machine?

I know this seems to be 3 separate questions, but they're all closely related, and each is dependent on the previous question being a valid question to begin with.


texts: Can the Lambda Calculus or Turing Machines model signals, callbacks, sleep/wait, or buses?

texts: I have a deep appreciation for formalisms like the Turing Machine and the $\lambda$-Calculus, and enjoy studying them and learning more about how they relate to physical computers. I am now learning about writing GUI programs, and the graphical library (GTK) relies on things like signals and callbacks, which I have not seen modeled by either Turing Machines or the $\lambda$-Calculus; can either the $\lambda$-Calculus or Turing Machines model things like signals, callbacks, sleeping/waiting, or buses? If so, where can I find some good reference material to learn more? If not, why not? and are there any formalisms which are capable of expressing such things?


texts:
int n = 1000;
int cnt = 0;
for (int i = 0; i < n; i++)
   cnt++;

Is the above code O(n) or O(1)? If I run the above code many times, it still iterates 1000 times. I'm really confused. I assumed it's O(1), but I'm not sure about it. Could anyone verify this?


texts: Rules for consistency with mutual inductive families?

texts:
I'm trying to use a proof assistant to define a type and a relation that are mutually dependent on each other:

Vec : (a : Type) -> (n : Nat) -> Type0
Rel : (a : Type) -> a -> a -> Type

data Vec : (a : Type) -> (n : Nat) -> Type0 where
  Nil : Rel Nat n 0 -> Vec a n
  Cons : a -> Vec a n' -> Rel Nat (S n') n -> Vec a n

data Rel : (a : Type) -> a -> a -> Type0 where
  RRefl : (a : Type) -> (x : a) -> Rel a x x
  RSucc : (m n : Nat) -> Rel Nat m n -> Rel Nat (S m) (S n)
  RCons : (e : Type) -> (m n: Nat) -> (h1 h2 : e) -> (t1 t2 : Vec e m) ->
            Rel e h1 h2 -> Rel (Vec e m) t1 t2 ->
            (rn : Rel Nat (S m) n) ->
            Rel (Vec e n) (Cons h1 t1 rn) (Cons h2 t2 rn)

Right now, both Agda and Idris reject this definition, since Rel refers not only to Vec, but to Cons, a constructor of Vec.

I'm wondering:

Is this restriction an implementation detail, or is it critical for ensuring consistency of a type theory? i.e. if we allow this kind of mutual reference, can we prove False?
Are there standard techniques to get around this? Possibly using induction-induction or induction-recursion?

One idea I had is to define a sort of PreVec that takes a parameter of type (rel : Nat -> Nat -> Type). But will this cause problems with predicativity?


texts:
Imagine we have a random number generator where g(n+1) = f(g(n)), where f is some function (e.g linear recurrence).
I'm trying to find a system where it's fast to find many steps in the future immediately, whereas it's hard or impossible to work out a previous state.
for example, if I know state = X at time t,  I would like to calculate state at t+n steps in the future, done in order O(1) rather than having to iterate n times.

I'm assuming state has an implicit modulo of around some power of 2 so it must be restrainted to a given number of bits at each time.

Does anyone know of a system that could provide this?
Many thanks.


texts: a variant of Fitch's algorithm when it is known that one path has cost 0?

texts:
Fitch's algorithm solves the small parsimony problem - given tree topology and leaf labels, but not internal node labels, find best internal node labels (i.e. best score) for that tree. The score is the number of edges $u->v$ with different labels $L_u \neq L_v$.

I need a variant on Fitch's algorithm when it is known that there is one path from root to some leaf with cost 0.


texts: Object algebras without anonymous inner classes

texts: In de Oliveira and Cook's Extensibility for the Masses uses Java for its code (it's not about stuff specific to that language though) and the ability to create anonymous inner classes is used extensively, starting from the code in Figure 4. Yet the authors claim that they rely only on a modest set of features and the same could be done e.g. in C# (as of 2012). Would the equivalents in C#, C++, Visual Basic and other languages without anonymous inner classes involve creating ordinary classes implementing the right interface, taking the arguments and storing them in the constructor and using in a single method, and those classes would be instantiated with new instead of the interfaces?


texts: How is the Varshamov-Tenegolts code decoded?

texts:
For $0 \leq a \leq n$ the VT code $VT_a(n)$ consists of all tuples $(x_1,x_2,..,x_n) \in \{ 0,1\}^n$ such that $ \sum_{i=1}^{n} ix_i = a (mod (n+1))$

For example $VT_0(4) = \{ 0000,1001,0110,1111 \}$

Say someone has $x = 1001$ and deletes the first zero and transmits $x' = 101$. Now is the claim that a receiver who only has access to say $101$ string will be able to decode back to $1001$?
Searching on the net what I see being called as "decoding algorithm" seems to me to assume that the receiver at least has access to the sums $\sum_{i=1}^{n} ix_i$ and $\sum_{i=1}^{n-1} ix'_i$ and also knows stuff like number of 1s and 0s to the left and right of the deleted position. This doesn't make sense to me since I thought that the idea is that the receiver doesn't know anything about $x$!


texts: Applying DFS algorithm to a transition system to find reachable states

texts:
Currently working on a past exam question which tells me to compute the product of two transition systems and then use DFS to find the reachable states of the product. I learnt how to compute the product of transition systems by looking at pages 43 and 44 in the "Principles of Model Checking" book by Christel Baier and Joost-Pieter Katoen (if anyone has a copy).

I understand that the way they found the reachable states in page 44 is by tracking the value of the variable y for each state and seeing if it holds, but in my particular question I'm not using a program graph; it's a transition system that uses only sigma and gamma (as handshake actions). My first question is how do I determine what is a reachable state and what is not in a product of transition systems?

Secondly, how would I show that I used DFS on paper? I couldn't find any useful articles online about it and our lecture notes don't cover it for some reason.


texts: Can a propositional threshold connective be expressed by standard connectives?

texts:
We are given a finite set of propositional atoms $\{x_1, \dots, x_n\}$ and an integer $k$.
Can we capture through a propositional formula $\varphi$ (built from the standard connectives $\neg, \wedge, \vee$ only) the set of all models having at most $k$ atoms valued at $1$, such that the size of $\varphi$ is polynomial w.r.t. $n$? If yes, how?

The only way I see is to define $\varphi$ as an exponential-sized DNF formula containing $\binom{n}{k}$ conjunctions of literals. For instance, for n=5 and k=2, the corresponding formula would be $(\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge \neg x_2 \wedge \neg x_4) \vee (\neg x_1 \wedge \neg x_2 \wedge \neg x_5) \vee (\neg x_2 \wedge \neg x_3 \wedge \neg x_4) \vee (\neg x_2 \wedge \neg x_3 \wedge \neg x_5) \vee \dots$

I got the following comment for the same question on https://cstheory.stackexchange.com/ but I do not have the level to understand it. I googled all keywords but I still cannot find the answer.

  $d_H(\omega, \omega')$ equals the number of 1 bits in the pointwise XOR of $\omega$ and $\omega'$. So, compute the XORs, count the number of 1 bits, and compare the result to k. It is well known that one can count bits with log-depth circuits (hence polynomial-size formulas), and one easy way to do that is to sum the individual bits using repeated 3-to-2 carry-save addition. See en.wikipedia.org/wiki/Carry-save_adder if you don’t know what that is. The choice of the basis of connectives is immaterial in all this, as long as it is complete


texts: What features of a problem make it NP-complete/hard?

texts:
This isn't a question about what NP-completeness or hardness is, but about what, in general and informally, make a problem NP-complete? That is to say, what features of a problem might make me suspect a problem is NP-complete/hard?

To elaborate, for instance, lets say I’m seeing the graph coloring problem for the first time, or independent set, etc. Are there intrinsic features of these kinds of problems that might make me suspect they cannot be solved efficiently?


texts: Finding k points in a set with largest total distance (measured to nearest point in k)

texts:
We are given a set of points $S$. Given $K$ is any subset of size $k$, how do I efficiently find the following:

$\mathop{\arg\max}\limits_K$
$\sum_{x_i\in K} \mathop{\min}\limits_{x_j \in K, x_j \ne x_i}d(x_i,x_j)$


texts: Normalization in IBM hexadecimal floating point

texts:
According to the Wikipedia link of IBM hexadecimal floating point:

  Consider encoding the value −118.625 as an IBM single-precision
  floating-point value.

  The value is negative, so the sign bit is 1.

  The value 118.62510 in binary is 1110110.1012. This value is
  normalized by moving the radix point left four bits (one hexadecimal
  digit) at a time until the leftmost digit is zero, yielding
  0.011101101012. The remaining rightmost digits are padded with zeros, yielding a 24-bit fraction of .0111 0110 1010 0000 0000 00002.

  The normalized value moved the radix point two digits to the left,
  yielding a multiplier and exponent of 16+2. A bias of +64 is added to
  the exponent (+2), yielding +66, which is 100 00102.

  Combining the sign, exponent plus bias, and normalized fraction
  produces this encoding:

  S Exp         Fraction
    1 100 0010    0111 0110 1010 0000 0000 0000
  In other words, the number represented is −0.76A00016 × 1666 − 64 =
  −0.4633789… × 16+2 = −118.625

Now, the definition of normalization according to Wikipedia says that

  In base $b$ a normalized number will have the form
  $±d_0.d_1d_2d_3...×b_n$ where $d_0≠0$, and the digits
  $d_0,d_1,d_2,d_3,...$ are integers between $0$ and  $b−1$

So, how is $0.011101101012 \times 16^2$ a normalized number?
In fact this number cannot be represented as a normalized one with base $16$ exponent because the closest we can get is  $1.1101101012 \times 16^1 \times 2^2$. What am I missing here?


texts:
I am currently stuck on a question from Sipser's book of automata. The question goes like this:

  Consider the following language: V = {w|w = 0a for some a which is an
  element of HALT} U {w|w=1b for some b which is an element of
  complement of HALT }

  Prove that V is unrecognizable? Prove that complement of V is
  unrecognizable?

I kinda know that to prove them we have to use contradiction but I got stuck after that and haven't been able to come up with any solution up till now. Any pointers/hints would be appreciated.


texts: Lambda calculus without free variables is as strong as lambda calculus?

texts:
First question: How would one prove that by removing free (unbound) variables from lambda calculus, and allowing only bound variables, its power is not reduced (it is still Turing-complete) ?

Second question: Is the proposition given above really true? Is lambda calculus sans free variables really Turing-complete?


texts: Check if two separate ranges have some number in common

texts:
We are given two permutations: A of size N and B of size M. We need to process Q queries, each query is given by two ranges, one subarray range in permutation A and one in B. We should check if there is at least one same number in those two ranges.

We don't need to answer the queries online, so we can sort them in different ways.

I tried different things with segment trees, but I don't have working ideas


texts:
Hello I am trying to solve the AlienTiles problem described at alientiles.com using the A* algorithm but I cannot find any good heuristic function so far.

In AlienTiles you have a board with $N \times N$ tiles, all coloured red. By clicking on a tile, all tiles in the same row and column advance to the next color, with the colour order being red $\rightarrow$ green $\rightarrow$ blue $\rightarrow$ purple, resetting to red after purple. A goal state is a state where every tile has the same colour, as long as its not red.

Is there any good point to start? I am completely frustrated about how I am supposed to handle the problem. An easy function that I came up with was the distance of the colour of the current tile with the target tile, but it is very slow.


texts: I don't know how to prove a simple theorem used with fixpoint in Coq

texts:
I am a beginner in coq and want to prove the following theorem t1. First I used induction i and destruct j, but it got bogged down in the middle.
I would like some hints for this problem.

Function f takes two arguments of nat and returns Prop (e.g., f 2 4 = x 2 ∧ x 3 ∧ x 4 ∧ x 5).

Theorem t1 shows that a head of function f can be cut and concatenated (e.g., x 3 ∧ f 4 7 ⇔ f 3 8).

Parameter x : nat -> Prop.

Fixpoint f (o i : nat) : Prop :=
 match i with
 | S O =>  x (i+o-1)
 | S i' => f o i' /\ x (i+o-1)
 | _ => True
 end.

Theorem t1 : forall i j : nat,
    x i /\ f (S i) j <-> f i (S j).
Proof. Admitted.


texts: Algorithm for checking unambiguity in the derivation of a string

texts: It is known that given a Context Free Grammar $G$, checking that it is ambiguous or not is undecidable. But, if I have a string $s \in L(G)$, does there exist an algorithm to check whether $s$ particularly can be derived unambiguously in $G$?


texts: I thought this would be the best place for a question like this. Anyway, I was wondering what minor would go well with a Computer Science degree. I was considering a minor in math but I am not entirely sure if that could help out or not. I am currently a second semester freshman and I suppose that this is the best/latest time to decide. Open to many suggestions.


texts: Uncertainty of coroutines writing to single socket

texts:
A program runs in a low-spec hardware utilizes coroutines writes to a single socket but how does the socket know when the data should be sent as there could more coroutines writing given N time.
I find this problem similar to The halting problem even tho contexts are different.
Does anyone know how could be a one find a optimal solution to solve this problem?


texts:
From what i've learned, the HW is responsible for setting the accessed and dirty bits in the PTE of a process, and the OS is responsible for turning them off.
My question is why?
The first part, i think is because only the HW is preforming the page table walk and it's a good opportunity for it to set them (because by doing the page walk or checking the tlb, it implies that a process wanted to access/write to a page).
Does the second part have something to do with the fact that the OS manages the page cache and all the paging to the disk go through it?


texts: Could anyone prove why O(n^(log n)) < O((log n)^n)?

texts: Could someone provide a rigorous proof of why $O(n^{log n}) \leq O((\log n)^n)$ is true? I'm trying to do this by induction but it isn't working. Thanks.


texts:
I am studying cryptography and having some trouble with the PRFs
How do I show that  $f_{k}(x) =x+k^2$ mod $2^n$ is not a Psuedo Random function?  I know that I need to show that the distignuisher can tell this is not random with a better then $\frac{1}{2}$ probability but how would it do that? (I don't just want an algorithm but a means to find such an algorithm for a query attack)
Thanks


texts: How many different (full/complete) in-order binary-trees do exist?

texts:
Given be a binary tree whose elements printed in-order results in [1,2,3,4].
Q1: How many different binary-trees do exist?
Q2: How many different complete binary-trees do exist?
Q3: How many different full binary-trees do exist?

For Q1 I was able to find a solution, by using the catalan number formula:
c(n) = (2n)! / ((n + 1)! * n!) → c(4) = 14.

For Q2 and Q3 however I was not able to find an answer to those problems.
Do general formulas for n elements even exist?

Definition of full and complete.


texts: If L is regular, so is L2 (proof using closure properties)

texts:
I've got a question that asks me to explain how if a language L is regular, then so is:

$M=\{s \in \{a, b\}^* |\ \exists\ t \in L\ such\ that\ |s|_a = |t|_a\}$

I believe I would have to get M into the form: $M=\{a^i |\ i\geq0\}$ since we know that any equation of that form is regular, but I'm not quite sure how to go about that using closure properties.


texts: Looking for non-entry level implementation of foundational algorithms and data structures in python. where to look?

texts: I'm an autodidact who works best with a mix of theory and implementation examples. I'm having a hard time finding resources on implementing algorithms and data structures in Python (2.7-3.X  preferably). I found a text ...mastering basic algorithms in the python language but I find it to be far too introductory and thus cluttered with unnecessary prose, which makes it for me difficult to move efficiently over it. What I have in mind is a text or github gist or whatever really, that has some coded python imps of what I've determined to be foundational data-structures in algorithmic's(not to sure on the usage/conjugation of that). Specifically I'm looking for trees, traversal, dynamic and greedy algorithms and the like. If this question is a repeat, or adequately answered elsewhere, links are adequate replies.


texts:
Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?

My attempt:

Lets $f(n)=g(n)=n$, then $f(n).g(n)+h(n)=\Omega(n^2)+\theta(n)=\Omega(n^2)$

But given answer is $O(n)$. Now sure where I have have committed mistake or if I am missing something. How it can be $O(n)$?


texts: Finding a small Moore machine that checks the last four bits

texts:
I am looking for a Moore finite state machine that returns true if and only if the last 4 bits (the input is of bits) are 0011 or 0101, the FSM can return any value at the first 4 bits (yes, even at the 4th).

The issue is that I was asked for a 7 conditions (vertexes) limit, and despite my efforts could not create one, my questions are the following :

Is there a FSM that solve this at 7 conditions (7 vertexes)? If there is than what is it and if not how can I prove there isn't?
Is there any type of 'algorithm' to approach this? I can easily well define one if we can use as much conditions as we wish (16 for our case) but what way other than intuition can lead me to reducing to 7 conditions?


texts: Difference between LR parsing and Shift-Reduce parsing?

texts:
I'm learning natural language processing and I can't understand the difference between Shift-Reduce parser and LR parser.

As I've understood from Wikipedia, shift-reduce is just a name of a class of parsing algorithms which includes LR, LALR, SLR and other. But some articles describe algorithm of shift-reduce parsing like it is a separate algorithm. So what is the difference between algorithm of shift-reduce parsing and algorithm of LR parsing?


texts: What is the correct representation of Master Theorem?

texts:
What I'm taught in my class -

  $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$
  where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number.

  if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$
  if $a=b^k$ then,

  if $p>-1$, then $T(n)=\theta(n^{\log_ab}\log^{p+1}n)$
  if $p = -1$, then $T(n)=\theta(n^{\log_ab}\log\log n)$
  if $p<-1$, then $T(n)=\theta(n^{\log_ab})$

  if $a<b^k$, then

  if $p\geq 0$, then $T(n)=\theta(n^k\log^pn)$
  if $p<0$, then $T(n)=O(n^k)$

On certain websites, the above representation for Master Theorem is slightly different as follows -

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

This ambiguity creates a great confusion while solving problems such as :

  What is the value of the recurrence : $T(n)=T(\sqrt{n})+\theta(\log\log n)$

Substituting $n=2^m$, we get a new expression :

  $S(m)=S(\frac{m}{2})+\theta(\log m)$
  Here  $a=1$, $b=2$, $k=0$ and $p=1$

If I apply Master Theorem as per the way I am taught in class, the result I get is :

  $T(n)=\theta(\log\log\log n)$

and if I solve using the other formula, I get the result as :

  $T(n)=\theta((\log\log n)^2)$

Which is the correct one? This confusion is making me question every problem that I've solved.


texts: Normal order sequencing vs applicative order sequencing

texts:
I'm trying to understand this lecture, section 2.7. Why would the normal order sequencing print out "hello" "world" and not "world" "hello"? I may be misinterpreting the order in which the arguments are applied.

It looks like the expression

$$
((Seq (display "hello"))\; (display "world"))
$$

would evaluate to

$$
\lambda z.((display "world")\; (display "hello"))
$$

and that would, under normal order, would print out "world" "hello".

My question is whether the assumption I'm making is correct. If not, could you show the correct derivation of the end-expression?


texts: Are regular languages closed under inverse homomorphism?

texts:
Let $\Sigma$ and $\Delta$ be alphabets. Consider a
function $\varphi: \Sigma \rightarrow \Delta^*$. Extend $\varphi$ to
a function from $\Sigma^* \rightarrow \Delta^*$ such that:
\begin{eqnarray*}
\varphi(\varepsilon) & = & \varepsilon \\
\varphi(w\sigma ) & = & \varphi(w)\varphi(\sigma ), \textrm{ for any }
w \in  \Sigma ^*, \sigma  \in  \Sigma
\end{eqnarray*}
Any function $\varphi:\Sigma^* \rightarrow \Delta^*$ defined in this way
from a function $\varphi: \Sigma \rightarrow \Delta^*$ is called a
homomorphism. We can extend this definition to languages as follows:
for any language $L$ and homomorphism $\varphi$, let
$$\varphi(L)=\{\varphi(w) : w\in L\}.$$

Are regular languages are closed under inverse homomorphism?


texts: Time complexity of the following the code for(i = 1; i<=n;i++){for(int j=i+1;j<n-i;j++)}

texts:
for(int i = 1;i<=n;i++){
      for(int j = i+1;j<=n-i;j++){
        print("hello");
      }
    }

The first loop has time complexity of n and second for loop is dependent on i. That means for every i, the number of time inner for loop gets executed is: $\sum_{k=1}^{n/2}(n-2k)$ After doing some algebra, I get: $\frac{n^2}{2}-\frac{n^2}{4}-\frac{n}{2}$. This is the time complexity for inner for loop. Now we multiplying outer loop  $n*(\frac{n^2}{2}-\frac{n^2}{4}-\frac{n}{2})$. Therefore, time complexity is $\Theta (n^3)$.
But this can't be right? It should max be $\Theta n^2$. Cause inner loop doesnt get executed for every i value.$\forall i \; \; \;i>n/2$ inner loop doesnt get executed at all.


texts:
Determine the asymptotic running time of the sorting algorithm maxSort.

Algorithm maxSort(A)
Input: An integer array A
Output: Array A sorted in non-decreasing order

1. for j <- n-1 down to 1 do
2.     m <- 0
3.     for i = 1 to j do
4.         if A[i] > A[m] then m <- i
5. exchange A[m], A[j]

Can you say anything about the "best-case" function $B_{maxSort}(n)$?

With a question like this, what is the way to tackle it? I have tried counting number of executions per line, but I can't translate it into asymptotic notation. My intuition is that it has something to do with $n^2$ due to the nested for loop, but I am not sure about this.


texts: Help Understanding the Type and Complexity of my Programming Task

texts:
I'm working on a programming task that I, without good evidence, have a sneaking suspicion is NP-Complete. With that said, I would like confirmation on this if possible, as well as some suggestion for a way to approximate a reasonable solution. Lastly, if this problem is just some popular problem in disguise, I'd love to look more into that problem. I'll now describe my task.

I am attempting to design a program to optimize daily fantasy baseball rosters given certain information. The context here is that I will be designing rosters of players from various games that consists of 2 pitchers and one player that plays each other position. This is complicated by the fact that each player is assigned a salary relative to their perceived ability and there is an overall cap on how much salary can be used in total. This means I am dealing with restrictions in terms of making sure that I do not exceed the combined salary cap, while also making sure that I have players at each position. To complicate things further, I want to be able to pick a few players (1-5 or so) at each position as my favorites, and have control over what % of my teams they appear in. That is, if I make 50 teams, I'd like to be able to make it so that I can generate these teams by inputting a list like: Player X (pitcher) 5%, Player Y (First Base) 50%, and so on.

Is there any practical way I can solve (approximate fairly accurately) this problem? The overall salary limit seems to make this a tricky problem.

Thanks a lot!


texts: Alternative definitions of ZPP and probabilistic Turing Machines

texts:
There are two ways to define a probabilistic Turing Machine:

A Turing Machine that can toss coins during its computation.
A deterministic Turing Machine that takes two inputs: $(x,r)$, where $x$ is the original input and $r$ is taken from a distribution of coin tosses.

For example, Arora and Barak give an "alternative definition" for $\mathrm{BPP}$:

  Definition 7.4 (BPP, alternative definition)
  $\mathrm{BPP}$ contains a language $L$ if there exists a polynomial-time TM $M$ and a polynomial $p\colon \mathbb{N}\to \mathbb{N}$
  such that for every $x \in \{ 0, 1 \}^{∗}$, $\Pr_{r \in \{ 0,1 \}^{p(|x|)}} [M (x, r) = L(x)]\geq 2 / 3 $.

My problem is formulating a similar alternative definition for $\mathrm{ZPP}$.

$\mathrm{ZPP}$ can be defined as the class of languages with a randomized algorithm that always outputs the correct answer, and for every input the expected running time of the algorithm is polynomial.

If we want a similar alternative definition for $\mathrm{ZPP}$, then $r$ should be an infinite stream because the algorithm may need to use any number of coin tosses before it finishes (with small probability).

Is there any problem with a Turing Machine that takes as a second input an infinite long stream?


texts: How do I calculate Instruction Per Clock?

texts:
Hi! I faced a problem with calculating IPC.

I can tell the answers were derived from IPC=instruction/number of cycles.

But I have no idea why it has to be calculated that way.

Just to understand the meaning of IPC, it seems like how many instruction
can one cycle(clock) handle which obviously is not the case for this question..

Hope to get some helpful answers from here!

Thank you in advance!


texts: What are the properties of the unsided fold?

texts:
Foldl and folr are 2 very important functions for FP and Haskell, but I have never heard much about the unsided fold:

fold f [a,b,c,d] = (f (f a b) (f c d))

That is, a fold that operates on binary associative functions (so the order of application doesn't matter). If I recall correctly, this is very common in databases as it can be parallelized. So, about it, I ask:

Is it, like foldr, universal?
Like foldr, can you define every important function using it?
Is there a fusion rule for it, similar to those for foldr/build and unfoldr/destroy?
Why is it barely mentioned?
Any consideration worth mentioning?


texts:
It is known that $Parity \notin AC^0$ (nonuniform), but the proof is rather involved and combinatorial. Are there simpler, but weaker lower bounds, say for $NP \not \subseteq AC^0$ or $NEXP \not \subseteq AC^0$?

For example, can nontrivial simplifications be obtained in the proof of $NEXP \not \subseteq ACC^0$ to deal only with the special case of $AC^0$?


texts:
I have been through multiple definitions of DAG and all of them say that it is a directed graph without cycles. Also, it is said that it has topological ordering.

Now the following figure is directed graph and does not have cycles.

But looking at the ordering of edges (look at edge (2,1)), it is not topologically ordered.

Is this still a DAG or every edge must be topologically ordered for this graph to be a DAG??


texts: Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?

texts:
Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order.
Then, that language/set is decidable. Because it is trivial to devise a (halting) TM_R, using TM_G, that recognize/accepts the words/numbers of that language/set.
It is also clear (really?), that there must be a non-contracting grammar for the language of TM_G.
Now, let's suppose a we have a TM_G' that generates a decidable language not in lexicographical order. Because the language is decidable, there must exist a TM_R' that completely recognizes it. Now, it is not clear how to build TM_R' using TM_G' (probably this is a unsolvable problem (is it?). At least, it is easy how to have a semi-deciding TM_R' based on TM_G').
In any case, by assumption, TM_R' (the halting/complete recognizer) does exist. Then, we can use TM_R' to build a TM_G'' which generates the language in lexicographical order.  Hence (really?), there exists a non-contracting grammar for the language.
In sum, is the class of decidable languages equivalent to non-contracting grammars?
In other words, are there a decidable language that cannot be generated by a non-contracting grammar (type 1)?
Expressed in terms of Turing Machines: **is the power of all halting TM equivalent to the power of all linear bounded automata (a restricted type of TM equivalent to type-1 grammars).? **


texts: reducing a decision problem to a local search problem

texts:
Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states:

  If a PLS problem is NP-hard then NP = P

So assuming L is a PLS problem (polynomial local search problem) that is NP-hard, then every NP problem can be reduced to L.

Usually if  $P_1$ is reducible to $P_2$ (being two decision problems) then there is a polynomial time function $f$ such that:

$I_1$ is a positive instance of $P_1$ $\qquad$ if and only if  $\qquad$ $f(I_1)$ is a positive instance of $P_2$

However I'm not completely sure how would a reduction from a decision problem to a local search problem be.

I guess my question is: if $P$ is a decision problem which is reducible to the problem $L$, mentioned above, with the polynomial time function (or procedure) $g$ then complete the sentence:

$I$ is a positive instance of $P$ $\qquad$ if and only if $\qquad$ $g(I)$ is ....................


texts:
I came across some code and I'm trying to crack the case as to what it does:
for $0 \leq f \leq l < len(A)$, the function is
def foo(A, f, l):
  if f == l:
    return A[f]
  m = (f+l) // 2
  x = foo(A, f, m)
  c = 0
  i = f
  while i <= l:
    if A[i] == x:
      c += 1
    i += 1
  if c > (l - f + 1)/2:
    return x
  return foo(A, m+1, l)

My first guess was that it returns the majority element because the while loop and the return seems to convince me of that but when I test some input
>>> a = [1,4,3,2,1,1,4]
>>> myst(a, 0, len(a) - 1)
1

But 1 is not the majority element as it doesn't appear more than half the times. Anyone up for the challenge to find the postcondition? The help would be appreciated.


texts: Strict partitioning clustering of points in 2D space into variable (but fixed) length cluster in order to minimize distance from center

texts:
Given $\\N$ points in 2D space, one is required to cluster them into $\\M$ clusters, with each cluster of a given size $\\S_m$ such that $\sum S_m = N$, in order to minimize the sum of the distance of the points from centroid of their respective cluster. The clusters (or call them bins) are to be filled completely.

Unaware of the correct approach, I thought of solving this using k-means. In which I will first pick $\\M$ random points and will start assigning the remaining points to each of the clusters, assigning the remaining points to the nearest cluster until a given cluster is full. Then for each of the $\\M$ cluster, get the centroid and recursively iterate till the new centroid of the cluster converges with the starting point of the clusters. But this answer is wrong and it relies on the order of points traversal.

My question is whether there is an approach through k-means using which an approximate answer could be achieved efficiently (like a specific way of points' traversal) or is there any other solution which answers the problem efficiently (some level of approximations are okay).

For my specific case, I am talking about some 300-500 points to be divided into some 10-30 partitions (each roughly of the same size - not a lot of variation there). And the points could be considered to be randomly spread in a unit square.

A special follow-on to this could be a case when $\sum S_m = N - i$ where $\\i$ is a whole number less than $\\N$.


texts:
When I'm solving a question I usually spent too much time testing whether I should pump or down? Is there any formula to know when to use which?

Also, on proofing non context free grammar we use three pumping lemma, and one that's confused me is $|uvy| \le p$. I mean in the example given in the book I read, it is not even used. Can someone please tell on which situation this is will be useful?

Any help will be very appreciated.


texts: Eligibility trace and the role of gamma and lambda

texts:
From R.Sutton's book, the eligibility trace update rule is:
$$
E_t(s)\leftarrow\gamma~\lambda~ E_{t-1}(s)+\mathbb{1}(S_t=s)
$$
I wonder why do we need both $\gamma$ and $\lambda$ to assign credit to most recent states.


texts: What are the advantages of using PRNG over TRNG?

texts: True random number generators use an unpredictable physical means to generate numbers, whereas pseudo-random numbers utilize mathematical formulas to produce a certain sequence of numbers that will appear random. I know that for PRNGs the efficiency is very high because they tend to generate a large quantity of random numbers in a short amount of time. Beside reproducibility  and efficiency, what are the advantages of using PRNG over TRNG?


texts: Student Course Allocation Problem with Many Constraints

texts:
Problem statement

In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students.

$i$-th section has:

A student capacity: $cap_i$.
Two lecture timings. (Formally, each section has two elements from $S$ associated with itself, where $S$ contains all lecture timings.)
A parent course $course_i$. ($m \leq n$)

$i$-th course has:

Some lecture section(s) under it. (As mentioned above.)
A parent course category $category_i$. ($t \leq m$)

Each student has ordered all $n$ sections from $1$ to $n$ on the basis of his/her preference.

Now, each student $i$ has to be allocated $q_i$ ($2 \geq q_i \geq 1$) sections such that:

No student has been allocated more than two or more section that have the same element(s) from $S$ associated with themselves. Formally, if the sets of lecture timings of allocated sections for a student $i$ are $T_1$, $T_2$, $\cdots$, $T_{q_i}$, then allocation should ensure that $|T_1 \cup T_2 \cup \cdots \cup T_{q_i}| = 2{q_i}$.
No student has been allocated two or more sections which have the same parent course.
No student has been allocated more than $u$ sections which have a parent course which have the same course category. ($u \geq 1$) Formally, let $X$ be a list of $category_{course_{j}}$ where $j$ is any section allocated to a student. The frequency of any element in $X$ should not exceed $u$.
No section $j$ is allocated to more than $cap_j$ students.
$\sum_{j=1}^p cost(j)$ is minimized. $cost(x)$ is defined as the sum of positions of the $x$th student's allocated sections in his/her preference list. For example, a student had ordered the courses P, Q, R, S in the order: R, Q, S, P. If he/she was allocated Q and S, cost() function will return 5. (2+3)

Constraints:

$1 \leq t \leq 7$
$3 \leq m \leq 9$
$5 \leq n \leq 30$
$250 \leq p \leq 700$
$\sum_{i=1}^p q_i \leq \sum_{i=1}^n cap_i$

My take

I tried to represent the problem in the form of a k-partite graph. Doing so would have helped implement network flow algorithms like minimum-cost, maximum-flow. However, I have not been able to come up with any representation that satisfies all of the given constraints.


texts: The Algorithm Design Manual - Working with the Big Oh

texts:
I'm reading The Algorithm Design Manuel and one part is kind of confusing to me
The part that's confusing to me is how in the "Proving the Theta" section he proves that selection sort is Ω(n^2).
I mean, I understand that for some (c) c.n^2 can be a lower bound for selection sort, however I don't understand how he proves this in that section.
I would really appreciate it if you could help me understand that part.
Thanks.
.


texts: What is the best terminology for lower bound

texts:
The term lower bound comes from math and applies to more than just complexity theory. What we see is that such and such is "a" lower bound. In complexity theory should this not be phrased as "the" lower bound, or better still the lowest bound. I can see where lower is a relative term, but the complexity of a given problem would seem to have exactly one minimum. Am I being overly semantic here? what I would like to say is that the lower (or lowest) bound on the complexity of SLL(k) testing is exponential.

http://www.slkpg.com/NPcoNP.html


texts:
There is a problem which I cannot solve. If you give a tip I will be very glad.

Prove that following language is not context free:

$L= \{ a^nb^m | \gcd(n,m) = 1 \}$.

It can be proven using the pumping lemma, but how?

If I start with some prime numbers $m$ and $n$ where $m>n>2$ and pump it up from $uVxYz$, there are three possible outcomes: $a^{n + k} b^m$, $a^{n +k}b^{m +k}$, $a^n b^{m +k}$. Since I do not know whether $k$ is even or odd I cannot say something. It is certain that $a^n$ and $b^m$ will be odd. However after adding $k$ to some of them, how can I say something about whether their gcd is 1 or not?


texts: Boat riddle as a combinatorial optimization problem?

texts:
I remember a riddle about a bunch of people on a river bank, and a boat with limited capacity (lets say the boat can transport 2 people at a time). There are various relations between the people like: person $x_m$ and $x_n$ cannot sail together and cannot even stay on the same bank of the river or $x_m$ and $x_n$ always have to be together.

When I remembered this riddle, I thought whether it could be represented as an optimization problem. The criterial function would be $\min(\text{numberOfSails})$ and the conditions will be my limitations, but I am not sure whether I can model my problem like this (and I am not sure how to model all my conditions).

Could you tell me or give me a hint, how such an approach for modelling this program would look like?

At first I thought it could look something like this:

min i // i = number of sails
x_i1 + ... + x_i2 <= 2 // i-th sail can contain max 2 people
x_im + x_in <= 1 // x_m and x_n cant sail together
etc.

But there is so much wrong with this model (like considering the people left on the first bank or the people already transported) and so on, so I am not sure how to tackle this problem.


texts:
Is there a formal definition for a size of a context-free grammar? The only definition I have seen so far is on this wiki page:

  The size of a grammar is the sum of the sizes of its production rules, where the size of a rule is one plus the length of its right-hand side.

So, how does one define the size of a production rule's RHS?

For example, if I define my CFG as:

S : A
A : 'a' B | A
B : 'b'

What is the size of the production rule A?


texts: How to solve this recurrence relation using substitution method

texts:
Can anyone explain to me how to demonstrate that,

$$T (n, d) ≤ T (n − 1, d) + O(d) + d/n (O(dn) + T (n − 1, d − 1))$$

is solved by

$$T (n, d) ≤ bnd!$$
for some constant $b$ using the substitution method?

I have done this but I don't know if it is correct:

$T (n-1, d) ≤ b(n-1)d!$
$O(d) ≤ bd$
$d/n (O(dn) + T (n − 1, d − 1)) ≤ d/n (bnd + b(n-1)d(n-1)!)$


texts: Solving a T(n) recursion without Master Theorem

texts:
i have a problem solving the recursion $T(n) = T(n-20)+log(n)$, because
the Master Theorem is not applicable in this case.

This is my attempt:
$T(1) = 1$(given)
$T(n) = T(n-20)+log(n)$
$T(n) = T(n-20-20)+log(n-20)+log(n) $
...
...
$T(n) = T(n-k)+log(n-(k-20))+....+log(n)$

Let be $ k = n-1$
$T(n) = T(n-(n-1)) +log(n-(n-1-20)+...+log(n)$
$T(n) = T(1)+log(21)+....+log(n)$

Which results in:
$ 1+ \sum_{n=1}^{\frac{n}{20}} ???$(i dont know if this is correct)

I am searching for a final result, which should be $\Theta(nlog(n))$


texts: Constructing an optimal solution to bin packing using a "magical function" $\phi$

texts:
I am taking an introductory course in complexity theory, and as an exercise, we were given the following problem.

Consider the bin packing problem, with objects of positive (rational) weights $W = \{w_1, w_2, ..., w_n\}$ ($0 < w_i \leq 1 \forall i$) that should be placed in bins of capacity 1. Imagine that you are given a "magical function" $\phi$ that, given a set $W$ of weights, gives you the minimum number $k$ of bins needed to pack the corresponding objects, i.e., $\phi(W) = k$. Let $T(n)$ denote the running time of the implementation of $\phi(W)$ and construct an algorithm that returns an optimal packing and runs in $O(f(n) + g(n)T(n))$ time, where $f(n)$ and $g(n)$ are polynomials.

First, I tried to recursively make binary partitions of $W$ by using that $\phi(W_1) + \phi(W_2) = \phi(W)$ for any partition $W_1 \cup W_2 = W$ such that $W_1$ and $W_2$ separates objects that are in different bins in an optimal solution (that is, there is an optimal solution such that no weights in $W_1$ share bins with any weight in $W_2$). When we eventually get $\phi(W_j) = 1$, we know that $W_j$ corresponds to the objects in bin $j$ in an optimal solution. However, my attempts here only yield algorithms with $g(n)$ being exponential in $n$.

Second, I tried to construct the bins one by one, using that, for all bins $B_j$, $\phi(B_j) + \phi(W \setminus B_j) = k$. Again, I have yet to find an algorithm where $g(n)$ is polynomial.

It's rather frustrating, as this seems to be a simple problem. Any suggestions on where I should begin?


texts: Solving subgraph isomorphism in polynomial time

texts:
So I am a bit confused about the reduction between SAT, subgraph isomorphism (SI) and graph isomorphism (GI).
I know that GI is in NP, and that SI is NP-complete.
So I'm thinking if we can decide instances of SAT in polynomial time, then we can also solve GI and SI in polynomial time since SAT is NP-complete and if one NP-complete problem is solved, then all others are also solved.

Am I correct? Thank you!


texts: What is the difference between a simulator, emulator, and cross compiler?

texts:
As far as I understand, cross compilers, emulators, and simulators are all ways that one computer system to be able to behave like or run another computer system.
What is the difference between these concepts? Are some of them equivalent?


texts: I was just thinking about this: Does the BIOS execute on the CPU? If so, how does it handle multiple CPU architectures/instruction sets? If not, what does it execute on?


texts: How to explain/understand brackets of applicative functor [[f u1... un]]?

texts:
I am reading article about Applicative Abstract Categorial Grammars http://okmij.org/ftp/gengo/applicative-symantics/AACG.pdf and this article uses brackets [[...]] for action on terms inside applicative functors. These brackets are introduced and somehow explained in "Functional Pearl: Applicative programming with effects" http://strictlypositive.org/IdiomLite.pdf. I understand what applicative functor is and what what is functor generally (both in category theory and Haskell) but I still can not understand the meaning and value of these brackets. I understand the sentence idiomatic expression [[f x y]] means ηf * ηx * y, or, alternatively, map (f x) y - that means that [[F(tau)]] is sitting inside brackets, but I can not understand the difference between F(tau) and [[F(tau)]] in brackets (see page 4 of AACG article about context and notation). Also - brackets are not always used with 3 arguments, sometimes there are even on or none arguments!

Do those brackets have meaning, explanation and use in Haskell world? Any explanation - rigorous or not, associative and free-style of not is really appreciated.

http://learnyouahaskell.com/functors-applicative-functors-and-monoids contains example:

pure (+) <*> Just 3 <*> Just 5

Its fine, but what benefit can we get by applying brackets [[]] around this expression, what additional meaning such application created?


texts: Triangulating a simple polygon via its trapezoidal map

texts: Given a trapezoidal map of a simple polygon $P$, is it possible to compute the triangulation of $P$ in $\mathcal{O}(n)$ time?


texts: What is the difference between Hamming Distance and Manhattan Distance for non-binary data?

texts: What is the difference between Hamming Distance and Manhattan Distance for non-binary data (specifically I am comparing points in $\mathbb{R}^2$)? I understand Manhattan sums the absolute difference in the and x and y directions but doesnt hammming distance do the same thing?


texts:
During my work I've encountered this problem:

$G = \{(x_i,y_i,z_i)\}_{i=1}^{n}$ is a group of points in space ($\forall i \;\;  x_i,y_i,z_i \in \Bbb R$) and $ d \in \Bbb R^+$ is a constant.

Divide $G$ to $m$ groups (as few as possible) that follow this rule: for each pair of points in the same group, the distance between these two points is less than or equal to $d$. ($m$ should be, as said, the minimum)

I thought about solving it by turning it into a graph where each point is a node and 2 nodes are connected if and only if the distance between these 2 points is smaller than $d$. Then the solution is the same as finding a minimal cover of the graph using Cliques. This is an NP problem and thus can't be solved in polynomial time unless P=NP. So that doesn't provide a useful solution.

Does anybody have any idea how to solve this problem?


texts:
Considering programming languages with significant whitespace for indentation, such as Python or Haskell. How does this whitespace fit into the grand schemes of programming language grammars.

I can see that a "preprocessor" can convert indent changes into tokens which are then handled in grammars, yet can one also perform the parsing based upon a single grammar without changing the intrinsic complexity of the 2nd grammer?


texts:
Cryptography has the concept of homomorphic encryption.

Homomorphic encryption lets you transform binary values into an encoded form, put them through a circuit and then decode the bits, getting the same value as if the plain text bits were put through an equivelant digital circuit. (A write up of a very simple implementation in my blog: http://blog.demofox.org/2015/09/05/super-simple-symmetric-leveled-homomorphic-encryption-implementation/)

This type of encryption was sought for 30 years before someone found an answer. While improvements have been made, its still impractical - on the order of 15 minutes to AND two encoded bits.

Throwing out the security concerns that come with cryptography, are there known methods for homomorphic computation?

I'm hoping that the security portion of homomorphic encryption is what was so elusive, but that homomorphic computation itself has known methods which are quicker or easier to execute even compared to turning off the security of HE schemes.

Thanks for any info you can provide!


texts: Hamiltonian circuit for a family of graphs

texts:
For $\Sigma = \{a,b\}$, let $S_n = \{w\mid w \in \Sigma^{*} \land |w| = n\}$.

Let $C_n \subset \Sigma^{*}$ be the language of circular strings that contain as substrings all elements of $S_n$.
For instance,  $bbaaaababaabbbba \in C_4$

I have formulated the problem of finding the subset of $C_n$, formed by the circular strings with the smallest size ($=2^n$), as the problem of finding all hamiltonian circuits on the graph that has the elements of $S_n$ as vertices, and edges connecting all pairs of vertices $s_i$ and $s_j$ such that $s_i = xw$ and $s_j = wy$, with $w \in \Sigma^{n-1}$ and $x,y \in \Sigma$.

For the example above, the graph could look like this:

My question:

  Would there be a polynomial-time solution for the hamilton circuit problem restricted to this family of graphs?


texts: Is there an algorithm to overapproximate a context free grammar by a regular expression?

texts:
I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be represented by a regular expression. However, an over-approximation of context-free languages is possible with regular expressions. For example, .* over approximates all context-free languages.

My question is, does there exist a more tighter approximation of a context free language by a regular expression? In particular, given a context free grammar, can I turn it into an (over-approximate) regular expression?

One option I can think of is to

Start with the start symbol, and produce a regular expression from its alternates by joining each alternate with |.
Replace any tokens in the alternate with its regular expression representation as above.
Replace any recursion (direct or indirect) with .*.

Has there been any research in this regard?


texts: 2SAT problem testcase does not have any strongly connected components

texts:
My task is to solve the 2SAT problem.
I have read online that a good method to solve this problem would be to construct an implication graph, where each statement of the form A || B implies two edges ~A -> B and ~B -> A. Then, we can set values to each variable by finding all the strongly connected components of the graph.
However, this input is confusing to me:
 1 || 2
~1 || 3
 4 || ~2

(each line represents one or statement: ~ means "not")

When I draw the implication graph for the above input, the graph looks like this:
~3 -> ~1 -> 2 -> 4

~4 -> ~2 -> 1 -> 3

The reason this confuses me is because there are no strongly connected components in this graph at all, meaning that the strongly connected component algorithm wouldn't find any components, which means that we wouldn't be able to set values for the variables. I don't know if I'm misunderstanding the algorithm itself, or if I've drawn the graph wrong. Can somebody please help me understand my mistake?


texts: What is the average search complexity of perfect hashing?

texts: The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?


texts: What problems are believed to have an efficient algorithm?

texts:
Just out of curiosity,
What problems are believed to have an efficient algorithm, yet haven't been found such an algorithm for them?

This question came up to my mind after reading about PRIMES problem.

I hope this question is appropriate for this forum

Thanks!


texts: Is the following statement about turing machines true?

texts:
Here's the statement:

  Take a set of finite inputs from some alphabet. If for any two turing machines:

  All inputs in the set produce the same output for both machines
  In both machines, the following is true: every state transition (i.e. every row in the state table) occurs at least once for at least one of the inputs in the set before halting

  Then both machines will produce the same output as each other for any input.

This is an informal statement, it probably needs a bit of refining. But for now the question is, is this true?


texts: Language of words that begin and end with same symbol and have equal numbers of a's and b's

texts:
I wish to find the CFG for a language on two symbols (say a and b) whose words begin and terminate with the same symbol, and have equal quantities of a's and b's.  What is the thought process I should use for finding such a grammar?  What is the most natural or simplest grammar for this language?  I hope you'll explain your answer. Hopefully this will suggest some patterns I should look for when trying to synthesise a grammar for a specified language.

Here's the best solution I could come up with on my own:

$ S \to aTbbTa \mid bTaaTb$

$ T \to abT \mid baT \mid aTb \mid bTa \mid \epsilon$

I think this grammar is correct.  Informal argument: I can see that if the word is $awa$ ($w$ being a substring), then there are at least two $b$'s in $w$ that are adjacent. This suggests the form $aTbbTa$ in the first production rule. (The argument holds if the roles of the two symbols are reversed). The second set of production rules is meant to generate every possible word of the language while keeping the number of $a'$s and $b'$s equal. Symmetry suggests that the rule $abT$ should be accompanied by the rule $baT$, and $aTb$ by $bTa$. Initially was wondering if any of the rules in the second set was redundant, but I don't think so - I can think of words that couldn't be formed if any of the second set of production rules was missing. Rather I need to be sure there aren't any words from the language that my grammar can't generate.

[I guess I would need induction to prove my grammar generates every possible word in the language. But right now I'm more interested in the thought process behind coming up with a grammar, and as far as I know, induction (in general) doesn't help much in synthesising a solution/rule/formula/etc.; it principally serves to verify a purported solution.]


texts:
if a,b are both binary bit. a=0, and b=0, what is least significant bit,and most significant bit of a+b, which means 0+0?
if c is the carry bit, and c=1, what is the least significant bit,and most significant bit of a+b when a=0,b=1

My thought is 0+0=0, thus least significant bit,and most significant bit are same, which is 0. and if C is carry bit, than a+b=1, then add carry bit, which is 10, so the the least significant bit is 0, and msb is 1..am I right? someone help


texts:
Are some algorithms inherently recursive?
As in, rewriting it in tail-recursive/iterative form with a stack is still needed, and there is no way to do it otherwise.
I am asking because I struggled to implement the function stringsMatchingPrefix on a Trie tail-recursively without a stack. The stringsMatchingPrefix problem is: given a string P, find all the words in the trie with the prefix P.


texts: Why is data fragmentation not possible on main memory (RAM)?

texts:
I am wondering why data fragmentation is a problem on main memory.

On a software level, virtual addresses are used anyway. So why can one address space not be split up into multiple segments, like a hard disk might do? I don't see how the performance would be affected, as the time needed to access memory addresses does not vary. Is this just a limit of the MMU?

In other words, my question is why does a process need continuous memory segments? For example:

Process D requests a memory block that could fit into the two free segments, if the block were split into two pieces. Why can't this be done?

It would be great if you could add a source so I could read more about this topic, if you have one.


texts:
According to https://link.springer.com/article/10.1007%2Fs001530050135 (Logics that define their own semantics, Imhof 1999) the logic FO[LFP] can define its own semantics, though the proof (of corollary 6.4) is somehow fuzzy. It is known from finite model theory that Datalog is equivalent to FO[LFP] (on ordered structures). Can someone help me see (at least partially) how to write a Datalog self-interpreter? The main difficulty is to express modus-ponens considering unification without involving existential variables in heads (i.e. variables in heads which don't appear in bodies and are understood to be existentially quantified).

Another related puzzle of mine is, if LFP's data complexity is P, and its query complexity is EXPTIME, how come it can interpret itself indeed? (I have no doubt that it can as the paper above supplied two different proofs for that. also we know that provably P!=EXPTIME)


texts: What is the worst case time complexity for intersection tests with BVHs?

texts:
This question is in the context of computer graphics. We have a scene with $n$ triangles and a ray. We want to find if the ray intersects any triangle and get the closest one.

There is a datastructure called Bounding Volume Hierachy (BVH) which groups triangles and fits a bounding volume (e.g. AABBs - axis-aligned bounding boxes) around it. The idea is that if the ray does not intersect the bounding volume, it does not intersect any of the contained triangles / other bounding volumes.

Now assume a BVH with AABB bounding volumes and a scene of $n$ triangles is given. You can spend arbitrary much time for constructing the BVH, but you don't know which rays will come.

What is the worst case time complexity for intersecting a ray with such a BVH? What would a worst case scene look like?

edit: What is the worst case time complexity if triangles may not cross each other?

I thought of something like the following, where the bounding volumes intersect with themselves a lot (think of a recursive definition where the scene is continued to the center).


texts: Implementing wait-free consensus with queues

texts:
Using Herlihy's model and definition of the wait-free hierarchy, a queue (a shared object with enqueue and dequeue) has consensus number 2, because we can initialize the queue with some value, and the first process to dequeue it "wins".

However, it is also possible to do wait-free consensus with queues that start off empty (for example, given as an assignment here, question 1).

I wasn't able to come up with the algorithm - would like help.

A hand-wave explanation: Two processors run asynchronously and communicate via shared memory, with atomic reads and writes being basic operations. We want to solve the wait free consensus problem, where each process starts with a bit value and they need to agree on one of the values, in a way that is wait free: each processor can finish in a finite number of its own steps, regardless of the progress of the others. A result says that such a task can't be done, so we include objects with more powerful operations that will allow consensus. The consensus number of an object is the number of processors in the model that can reach consensus using it. The consensus number of a queue with just enq and deq is 2. Intuitively it isn't 3 because if a processor deqs empty, it can't know which of the other processors deqd the value.


texts: Is the language $L$ of coded CFG's Turing decidable?

texts:
Consider the following language

$L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$}

Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that simulates a NPDA that decide whether $w$ is indeed in $L(G)$. The TM will hold two tapes: one for the input and another to simulate the stack.

Am I in the right direction here?


texts: What kind of data structure should be used for working with dynamic sets where elements follow "normal distribution" and why?

texts:
I am wondering if Hash tables would be a good choice as it mentions dynamic sets to store data which follows normal distribution.
I have doubt in this because normal distribution has bell shaped curve which means elements near the median are more than others. So, If I use hash table then that would lead to clustering.
So, any insights regarding this would be helpful.
Edit: Common operations on a dynamic set are Find,Insert, Delete, and also
analysing what are the complexities for each operation.


texts: Proving an algorithm satisfies $\epsilon$-DP

texts:
I am trying to prove/disprove that an algorithm satisfies $\epsilon$-DP. I proved some of them but there are 3 more which I could not decide on.
Here they are:

Algorithm A takes as input a dataset D and counts the number of records in D. If the number of records is greater than eε, A prints out: “large”. Otherwise, A prints out “small”.
Algorithm A takes as input a dataset D and an integer k. It returns TRUE if D is k- anonymous and FALSE otherwise.
Algorithm A wants to answer if a certain individual’s age is above 40. To do so, A takes as input dataset D and a person’s name (eg: “John Doe”) as input. It retrieves from D the count of individuals with that name and age > 40. Then, A adds Laplace noise with mean = 0 and scale = ε. If the noisy count is > 1, A returns TRUE. Otherwise, A returns FALSE.

If anybody can help me to solve them, I would appreciate a lot.


texts: Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree

texts:
There is  a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal.

For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
For each internal node:
if any of its children is not selected, then select this node.

How do I prove that this greedy strategy gives an optimal answer? That there is no vertex cover smaller in size than the one that the above algorithm produces?


texts: Problem of making entities agree on some wavelength

texts:
I remember seeing this problem somewhere before, but don't remember what it's called and can't find it again.

It was presented as two guys having $n$ phones each that don't ring when called. Each phone from one person is connected to one phone of the other person, in some random permutation. They can each test one phone every "round", to check if they are using a connected pair of phones and thus able to communicate (this is in some way a consensus problem).
They had to devise some strategy beforehand to be able to communicate (and minimize the amount of rounds necessary).
Of course, the application behind this would be to make two entities connect on some same wavelength at the same time.

What is this problem called, also what are the best strategies?


texts: Need clarification in theorem about syntactic equations and substitutions

texts:
In the book "Constraint Handling Rules", Thom Frühwirth explains (on p. 50) "Substitutions, variants and equality" over a usual first-order logic language composed of variables, function symbols and predicate symbols.

It's the usual foundation in preparation for introducing unification.

However, one then meets the following text:

  The following classical theorem establishes the relation between
  syntactic equations and substitutions:

  Theorem 3.1

  Given two expressions $A$ and $B$ and a substitution $\theta = \{X_{1}/t_{1},...,X_{n}/t_{n}\}$, then

  $$\forall \theta \space A = B\theta \leftrightarrow (X_{1}=t_{1} \land \cdots \land X_{n}=t_{n} \rightarrow A = B).$$

"Expressions" are understood to be terms and atomic formulas $p(t_{1},...,t_{n})$ , but also sets, multisets, sequences or lists of terms.
The subsitution $\theta$ replaces the variables $X_{i}$ by the terms $t_{i}$ in the usual way.

I can't make any sense of the above theorem. It seems badly formulated. Does anyone have the "classical" source?


texts: Algorithm to test whether a language is regular

texts:
Is there an algorithm/systematic procedure to test whether a language is regular?

In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in \mathbb{N}\}$), test whether the language is regular or not.  Imagine we are writing a web service to help students with all their homeworks; the user specifies the language, and the web service responds with "regular",  "not regular", or "I don't know".  (We'd like the web service to answer "I don't know" as infrequently as possible.)  Is there any good approach to automating this?  Is this tractable?  Is it decidable (i.e., is it possible to guarantee that we never need to answer "I don't know")?  Are there reasonably efficient algorithms for solving this problem, and be able to provide an answer other than "don't know" for many/most languages that are likely to arise in practice?

The classic method for proving that a language is not regular is the pumping lemma.  However, it looks like requires manual insight at some point (e.g., to choose the word to pump), so I'm not clear on whether this can be turned into something algorithmic.

A classic method for proving that a language is regular would be to use the  Myhill–Nerode theorem to derive a finite-state automaton.  This looks like a promising approach, but it does requires the ability to perform basic operations on languages in algebraic form.  It's not clear to me whether there's a systematic way to symbolically perform all of the operations that may be needed, on languages in algebraic form.

To make this question well-posed, we need to decide how the user will specify  the language.  I'm open to suggestions, but I'm thinking something like this:

$$L = \{E : S\}$$

where $E$ is a word-expression and $S$ is a system of linear inequalities over the length-variables, with the following definitions:

Each of $x,y,z,\dots$ is a word-expression.  (These represent variables that can take on any word in $\Sigma^*$.)
Each of $x^r,y^r,z^r,\dots$ is a word-expression.  (Here $x^r$ represents the reverse of the string $x$.)
Each of $a,b,c,\dots$ is a word-expression.  (Implicitly, $\Sigma=\{a,b,c,\dots\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)
Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.
The concatenation of word-expressions is a word-expression.
Each of $m,n,p,q,\dots$ is a length-variable.  (These represent variables that can take on any natural number.)
Each of $|x|,|y|,|z|,\dots$ is a length-variable.  (These represent the length of a corresponding word.)

This seems broad enough to handle many of the cases we see in textbook exercises.  Of course, you can substitute any other textual method of specifying a language in algebraic form, if you have a better suggestion.


texts: The halting problem of Turing machines in view of enumeration of initial tape configurations

texts:
As far as I know, presentations of the (general) halting problem (cmp. Wikipedia) are referring explicitly to an ennumeration of (applicable) programs. For the purpose of my questions let's consider specificly any programs for one-head, two-symbol Turing machines with sufficient memory to store the instructions prescribed by the program and any (internal) state reached in the course of executing the program.

Such an enumeration of applicable programs could be symbolically written as

$$ p : \{ \mathsf{TM_{\text{(1 head, 2 symbols)}}} \} \leftrightarrow \mathbb N.$$

(The mapping is one-to-one since enumeration is supposed to be without gaps, and there are infinitely many Turing machine programs to be enumerated. For definiteness, the set $\mathbb N$ here denotes the whole numbers, including $0$.)

I am interested in the consequences of the input (i.e. specificly the contents of the tape, in reference to the machine head, at the start of program execution) being explicitly encoded through an enumeration as well; symbolically

$$ s : \{ \text{ starting tape configurations } \} \leftrightarrow \mathbb N;$$

specificly for instance, for input $\text{ tape contents }$ with non-blank fields on positions $1 \le a \lt b \lt c ... \lt l$ to the left of the Turing machine head  and on positions $0 \le z \lt y \lt x ... \lt r$ to the right of the head (and if applicable on position $0$ directly under the head in starting position) then

$$ s[~\text{tape contents}~] := (4^a + 4^b + 4^c ... +~4^l)/2 + 4^z + 4^y + 4^x ... +~4^r.$$

(The completely blank tape is accordingly encoded as number $0$.)

My question:
Given the above description, can the non-existence of a halting program ("DoesItHalt?") be proven regardless of the specific enumeration $p$ of Turing machine programs?
And if so, how exactly?

As an illustration of possible difficulties in trying to argue that a Turing machine program "DoesItHalt?" doesn't exist one might perhaps consider the composition

BadH := EncodeInput | DuplicateArgument | DoesItHalt? | ContrarianActor

which should have the value $p[$ BadH $]$ in the enumeration of programs,
running on input "BadI" which would be selected exactly such that

$p[$ BadH $] = s[$ BadI $]$;

where

EncodeInput is supposed to be a specific program implementing the enumeration $s$,
DuplicateArgument is a simple program to prepare the two arguments required for a (meaningful) subsequent execution of DoesItHalt?, and
ContrarianActor is a simple program whose action is just the opposite of the intended meaning of DoesItHalt?'s result.

Then it would be premature to conclude a contradiction; that program DoesItHalt? didn't function as correct halting program because the program BadH, being run on the inital tape configuration BadI, is thought to act eventually just contrary to the intended meaning of the presumed result of program DoesItHalt? evaluating (running on) the two argument values $p[$ BadH $]$ and $s[$ BadI $]$. Because:

Already the (apparently necessary) program part "EncodeInput" is questionable: It is supposed to terminate when starting on any initial tape configuration with a finite number of non-blank fields (in order to return its enumeration value). But therefore it also returns the exact same result when starting on any "suitably extended" initial tape configuration with some (still finite) additional non-blank fields "sufficiently further out". The correct enumeration values of any such "suitably extended" initial tape configuration cannot be returned by the specific "EncodeInput" program.

Then why not enumerate the specific "BadH" program of the example above precisely by such an "inaccessible" value (which obviously is not being calculated by program part DuplicateArgument either); thus defeating the attempt of arriving at a contradiction in this specific case. (Obviously, this would have to be accomodated by a suitable enumeration of all programs.)


texts: I'm trying to understand why every language has an infinite number of TMs that accept it

texts:
I found the following answer:

$L_{17} = \{ \langle M \rangle \mid \text{$M$ is a TM, and $M$ is the only TM that accepts $L(M)$} \}$.

R. This is the empty set, since every language has an infinite number of TMs that accept it.

As I know number of TMs is $\aleph_0$ and number of languages is $2^{\aleph_0}$, so how can it be possible that "every language has an infinite number of TMs that accept it"?
source of the solution here


texts: When states that are not accepting states become accepting states in NFA, what happens?

texts:
It is known that when NFA's accepting states are swapped with rejecting states, the recognized language is not complement of the original language. For some language, it may be the case that some strings that were recognized in the original NFA may still be recognized in the state-swapped NFA.

My question is, is there a language $L$ that in the original NFA a string is not recognized(rejected), but in the NFA where accepting states become rejecting states and rejecting states become accepting states the string is also rejected?


texts: Sorting algorithm for ranking hundreds of Images based on pairwise comparison

texts:
I am facing the task of designing an algorithm to rank some hundred of images (around 300). The ranking is to be based on pairwise comparison judged by human (done through Amazon mechanical Turk). I have read many papers on ranking inference based on a subset of all possible pairwise comparisons (e.g. Jamieson and Nowak 2011). But I think because I don't have many images, exact ranking should be achievable with properly designed pairwise comparison sequences using some sorting algorithm.
Nonetheless this is different from the standard array sorting in the sense that, comparison result is not known with certainty prior to arranging the pair for comparison and letting the human judge decide. Thus there is a bit of adaptive selection involved. Moreover since it is based on the perception of one human judge, no parallel processing is possible to expedite the sorting. What is worse, transitivity is not guaranteed. Therefore some standard sorting algorithms may not be applicable.
Would somebody please recommend some sorting algorithm for my task?
Many thanks!


texts: Algorithm for listing all binary trees of a given height

texts:
I've been trying to find an algorithm to list all binary trees of a given height $h$.

Note that I'm not trying to count them: the number of such trees is given in the OEIS (A001699).

All the algorithms that I have been able to see list all binary trees for a given number of nodes. A very inefficient way of solving the problem would proceed by checking all the trees with a number of nodes between $h+1$ and $2^{h+1}-1$, but this is not great at all.

Any pointers or references would be much appreciated.


texts:
I am trying to understand what is the domain for denotational semantics.

Right now the way I understand denotational semantics is that given some syntax of a program that maps to some mathematical object that represents its meaning. e.g. for example give  some arithmetic expression AExp the denotation $[\_]:AExp \to (State \rightharpoondown Int)$ :

$$ [ 1 + x ]\sigma = 1+x $$

if the state is $\sigma = \{ x:2\}$ then:

$$ [ 1 + x ]\sigma = 3 $$

So indeed given the syntax AExp using the state we can fully determine what the integer should be returned.

I also understand the denotations for statements $[\_]:State \rightharpoondown State $ which makes a lot of sense since that states the state of the program to the next after executing some code in the statement. e.g. $[\{ \}] = 1_{identity}$ the empty statement does not change the state so:

$$ [\{ \}](\sigma) = [\{ \}]\sigma = 1_{identity}(\sigma) = \sigma $$

But I can't figure out what the type should be for the denotation for identifiers. From the notes I am reading CS522 I see this:

$$ x\in Identifier \implies [\sigma] = \sigma(x) $$

which intuitively makes sense but I am having difficulties matching it to the fact that denotaitons should be CPO (Complete Partial Sets). How is the above a CPO? (or the poset, the technicality of existence of LUB/sumpremum is not that important to me). I can't see the POSET.

I guess I am not 100% how the other two are also CPOs...any enlightening comments?


texts: Mapping reduction to show NeverHalt is undecidable

texts:
I need help with showing that
$$NeverHalt_{TM} = \{\langle M\rangle \mid \text{$M$ is a TM which runs forever on every input $w$}\}$$
is undecidable by giving an explicit mapping reduction.

To show that a language reduces to any other language we must show that yes-instances are mapped to yes-instances and no-instances are mapped to no instances. We need to find a TM whose language will "help" us solve $NeverHalt_{TM}$, given $\langle M\rangle$.

I am not really sure where to go from here or in general how to proceed with undecidability problems.


texts: Must an optimization problem with a greedy algorithm belong to P?

texts:
If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the problem belongs to P?
I was told it is true that problems of this type must belong to P, but I have questions about whether this is true.
It seems to me that there should be many examples of optimization problems with non-deterministic greedy algorithms.
Are there in fact counterexamples to this claim or is it necessarily true?


texts:
Good day.
Subset sum selection problem is NP-hard.

I trying to solve following problem:
Input: a grid NxN and subset size K and radius R. Every entry in grid contains a value.
Solution: subset of size K, so that sum of all selected items and items within radius(when selected items is in center) is maximal.

Here example(with radius 1 and K=2):

On this picture 2 orange items selected. all blue and green items are added to sum also, but green item, added only once( in other words any item on grid can be taken once in final sum).

So sum of selected subse: 2xOrange(selected)+9xBlue(adjacent)+1xGreen(taken only once into account).

When radius is 0 the problem is trivial: Just choose K best items,
But when radius 1 or more is following problem NP-hard?

If yes, what is the best way to prove it ?

If no, is there an algorithm that return optimal solution?

Many thanks for help!


texts:
How do I solve the following problem with a recurrent neural network (RNN)?  What architecture should I use for the (conv)-RNN?

  Let $s \in \mathbb{R}^N$ be a musical signal. We corrupt it with some white/pink noise $\omega$ to obtain $x= s+\omega$.
  We then create a conv-RNN with $N$ input and $N$ output neurons, we feed it with input $x^{(t)}=x$ and we train it to output the sequence $y^{(t)} = x -\frac{t^2}{100^2} \omega$ for $t = 0\ldots 100$, ie. some better and better approximations to $s$.

  We repeat the same process with many different $s,w$ and we hope the resulting RNN will serve as a musical de-noiser.

  De-noising is supposed to have a chance to work because it is quite suitable for convolution-RNNs, so even if we need a lot of neurons, the number of weights to learn shouldn't be too high.

Note this isn't only about this particular problem, I chose it because it is easy to generate training data the way I said, I will be interested in anything different but related (in particular anything about a conv-RNN trained to output better and better approximations to the solution).
For example we could replace noisy musical signals by low-resolution pictures, and train the RNN to output higher and higher resolution version of the picture.

Edit - For now, I think the architecture  of the RNN should be the following :

Let $X = \text{spectrogram}(x)$ be the input, and each $X_{i,j}$ is a $16\times 16$ piece of $X$, the neighbor pieces overlap. Then the output of the $i,j$th piece of neurons at time $t+1$ is $$z_{i,j}^{(t+1)} = F(W,X_{i,j}, z_{i,j}^{(t)},z_{i\pm 1,j\pm 1}^{(t)})$$

where $W$ are the parameters of $F$ to be optimized. The output of the RNN at time $t$ is $Y^{(t)} = X-\sum_{i,j} z_{i,j}^{(t)} \delta_{i,j}$ (assembling all the pieces of spectrogram together, $z_{i,j}$ is supposed to contain some local estimation of the noise) and the error is $$E^{(t)} =\| Y^{(t)} -(X-\frac{t^2}{100^2} \Omega)\|^2, \qquad E = \sum_{t=1}^{100} E^{(t)}$$
 $F$ is itself a 3 layer perceptron, so the parameters $W$ are the weights of all those $3$ layers, and the input weights tell how the neighbor pieces $z_{i\pm 1,j\pm 1}^{(t)}$ affect $z_{i,j}^{(t+1)}$, which we hope will let the information to propagate from a piece of neurons to the neighbor.

We update the parameters from something like $$W \leftarrow W - \eta \sum_{t=1}^{100} \frac{\partial E^{(t)}}{\partial W}$$


texts: Shortest even path that goes through a vertex

texts:
Given an undirected and connected graph $G=(V,E)$ and two vertices $s,t$ and a vertex $d \in V- \{s,t\}$, we would like to define a legal path as a path from $s$ to $t$, passes through $d$ (at least once) and is of even length (regarding number of edges).

We need to find such a path that is  the shortest in $O(V+E)$ time.

I thought about BFS from $s$ to find a shortest path to $d$, and BFS from $d$ to find shortest path to $t$, but then it wouldn't necessarily be of even length.
Plus, such a path we're looking for is not necessarily simple.

Any hints?


texts:
I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where $m$ is the number of edges in the graph and $n$ is the number of vertices(for example, see wikipedia or this book, among many examples - I cannot post more than two links due to reputation constraints).

What bothers me about this is that if $m$ is small (say $m=n^{1/4}$) this seems to require less than $n$ iterations, which is odd: surely you have to at least look at every node, i.e., just to see if it has any incident edges or not?

Having looked at Hopcroft and Karp's original paper, I see they quote a running time of $O((m+n)\sqrt{n})$ which makes more sense.

So my question is: what is the reason why the running time of Hopcroft-Karp is usually quoted as $O(m \sqrt{n})$? Does this reflect an assumption that the graph is connected (I never see this stated explicitly)?


texts:
I think I'm confused about deletion in heaps, and since I have an exam today, I'm looking for your help to correct me.

I will post photos since it will makes it a bit more clear.

Note(forget about deleting the root)

What I understand is that , heaps only deletes the root element or the top. So, I made 2 solutions and I'm kindly asking which solution is the correct one.

Q:the heapness will be violated, I will have to replace it by the rightmost element bottom down right? (32)


texts: Prove that A is non-regular using K-Complexity Non regularity theorem

texts:
Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (in lex order) such that $xy∈A$ (if n such y exits). So what completes $x$ if adding $n$ such $y$'s brings us to an element in the set $A$

Given $A \subseteq \Sigma^*$ has the following property, then it is not regular
For every $c \in \mathbb{Z^+}$ there exits $x \in \Sigma^*$, and $n \in \mathbb{Z^+}$ s.t. $Y^A_{x,n}$ exits and K-Comp $C(Y^A_{x,n}) > c + log(n)$

We are trying to show weather given a DFA will it end in a final state after certain number of steps and this process will tell us if that is not a possibility since we cannot prove regularity just non-regularity

$A=\{0^{2n}1x∣n∈\mathbb{N}, x∈\{0,1\}^∗$, and $|x|=n\}$ Prove that A is non-regular using KCR
All we have to do is to pick a $x$ and $y$ s.t the concatenation $xy \in A$.
If I let $x = 0^{2n}1$ and let $y = x$, then we build the set $Y^A_{x}$ given the $x$ and $y$ from above $Y^A_{x,1} = 001(01)$ and next element in the set $Y^A_{x,2} = 00001(0101)$.
Here is where I get stuck since I know I need to show $C(Y^A_{x,1}) > c + log(1)$ would this suffice to show that because of that this language is not regular? What is the best way to split the language for $x$ and $y $


texts: How do you convert bits into a different alphabet?

texts:
I have forgotten how to do this. How do I figure out what the requirements are for a 128-bit string using a certain alphabet?
That is to say, I want to generate a UUID (128-bit) value, using only the 10 numbers for the alphabet. How many numbers do I need, and what is the general equation so I can figure this out for any alphabet of any size?
What is the equation for any n-bit value with any x-letter alphabet?
The way I do it is to guess and slowly iterate until I arrive at a close number. For powers of 10 it's easy:
Math.pow(2, 128)
3.402823669209385e+38
Math.pow(10, 39)
1e+39

For other numbers, it takes a little more guessing. Would love to know the equation for this.


texts:
I think I heard in somewhere that it has been proven that $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$, that is $\mathsf{NP} \subsetneq \mathsf{EXP}$. Is this right? Wikipedia and book resources do not seem to bring me an answer..

I just found a post similar to this, but I am not sure whether $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$.


texts: How to merge all 3-grams into smallest possible string?

texts:
There is a set of all possible letters: $A = \{ a, b, \ldots, z \}.$
Then the set of all possible 3-grams looks like that:
$A^3 = A \times A \times A = $
$\{$
$\;\;(a, a, a), $
$\;\;(a, a, b), $
$\;\;(a, a, c), $
$\;\;\;\; \ldots, $
$\;\;(a, a, z), $
$\;\;(b, a, a), $
$\;\;\;\; \ldots, $
$\;\;(z, z, y), $
$\;\;(z, z, z), $
$\}$

$|A^3| = 26^3 = 17576$

If we try to merge $aaa$ with $bbb$ we have to append $bbb$ to the end of $aaa$, because they don't overlap:
merge($aaa$, $bbb$) = $aaabbb$
If we merge $aaa$ with $aab$ we can create a smaller string of length 4:
merge($aaa$, $aab$) = $aaab$

In the best case, if we manage to always do a second kind of merge, we will be extending the resulting string by 1 character. There are $17576$ triplets, so there can be at most $17575$ single character extensions. This will result in $17575 + 3 = 17578$ characters string.

In the worst case, we will append all of the 3-grams to each other, thus creating a $17576 * 3 = 52728$ characters string.

How to combine all of them to get the total string of the minimum length?


texts: There is a huge field of study dedicated to automated theorem proving. Is there any similar research dedicated to automated algorithm design? And is there any form of "duality" between these two processes (automated theorem proving vs automated algorithm design)?


texts: What is the simplest way to understand Turing machines and the busy beaver problem?

texts: The Wikipedia description has way too much math.


texts: Calculating direct sum of 2 binary numbers

texts: If we have say,key=‘0110‘ and =‘1100‘, how will ⊕key mod 2 be calculated and what will be the answer equal to?


texts: Can we use the same reduction L1 -> L2 for coL1 -> coL2

texts:
does L1

    ≤
    p

 L2
yield that coL1

    ≤
    p

coL2 for the same reduction?


texts: Which unit (control unite or logic unit) issue instructions of load/store?

texts:
I learned that the  CPU is composed of two units

and the machine’s instructions can be categorized into three groupings: (1) the data transfer group, (2) the arithmetic/logic group, and (3) the control group.

It could be concluded that Control Unit for the control group and Arithmetic/logic for the corresponding groups

How about the data transfer group? the data reside in register, which of the two units issue store/load command?


texts: Combining Computer Science and Humanities

texts: I currently hold a bachelors in Computer science and a masters in Art History. I really want to combine the two and I know of Digital Humanities but I'm not completely aware of where Digital Humanists could work besides Museums, libraries, etc. and even at museums and the such, I imagine that the demand for Digital humanists isn't THAT large either. Does anyone have any idea of how I could combine art history and computer science and what kind of places could I work in? If I do go into digital humanities, do you think I'd be expected to work in cultural settings or could I still get a job at a purely science industry? Any response will be greatly appreciated!


texts: Time complexity of a backtrack algorithm

texts:
I've developed the following backtrack algorithm, and I'm trying to find out it time complexity.

A set of $K$ integers defines a set of modular distances between all pairs of them. In this
algorithm, I considered the inverse problem of reconstructing all integer sets which realize a given distance multiset. i.e. :

Inputs: $D=\{p_i−p_j \mod N, i≠j \},K $

Output : $P=\{p_1,p_2,...,p_K\},\qquad p_i \in \{0,1,2,...,N-1\},\qquad p_i > p_j $ for $i>j$

Simply saying, the algorithm puts $K$ blanks to be filled. Initially, puts 1 in the first blank. For the second blank it looks for the first integer that if we add to P, it doesn't produce any difference exceeding the existent differences in $D$. Then, it does so, for next blanks. While filling a blank if it checked all possible integers and found no suitable integer for that blank, it turns back to the previous blank and looks for next suitable integer for it. If all blanks are filled, it has finished his job, otherwise it means that there weren't any possible $P$'s for this $D$.

Here's my analysis so far.
Since the algorithm checks at most all members of $\{2,...,N\}$ for each blank (upper bound) there is $N-1$ search for each blank. If each visited blank was filled in visiting time, the complexity would be $O((K-1)(N-1))$ since we have $K-1$ blank (assuming first one is filled with 1). But the algorithm is more complex since for some blanks it goes backward and some blanks may be visited more that once. I'm looking for the worst case complexity i.e. the case that all blanks are visited and no solution is found.


texts:
I'm attempting to practice for an exam and I'm having some trouble on one of the practice problems. The problem asks to identify a variety of language as regular grammar, context-free grammar, context-sensitve grammar, or unrestricted grammar. It also asks that if the grammar is regular or context-free, to write out the exact grammar. I'm not having trouble with two out of the 4 pieces of language. For instance, the easiest one is as follows:

$\{a^n$ where $n\ge0$, $n\pmod 3 \not= 1\}$ can be described by the regular grammar $A \rightarrow aA \mid a$

However, the language I am struggling with is:

$$\{a^n b^m \text{ where } n>1, m\ge1, n>m\}$$

and

$$\{a^{2n} b^{3n}\text{ where }n\ge1\}$$

I believe that the first language is context-free because I know that the language $a^nb^n$ is context-free from prior examples and can be described by the grammar $A \rightarrow aAb \mid ab$, however, in this version, $b$ is taken to the $m$ power rather than the $n$ and the bounds for $m$ and $n$ are different, and I'm not sure how that affects the grammar that describes it. Frankly, I'm not sure where to start with the latter piece of language... I don't know how to determine what type of grammar describes it, let alone the grammar itself if it is context-free or regular.

Could anyone help, or at least point me in the right direction?


texts: What does "bounded above" mean in Family of Bachmann–Landau notations?

texts:
Per wiki

  |f| is bounded above by g (up to constant factor) asymptotically

with this concrete example,

$$f(n) = \log n$$

$$g(n) = n^c = n^{0.000001}$$

Does "bounded above (up to constant factor)" means $f(n)$ is above $g(n)$


texts: What is the computational power of Parsing Expression Grammars?

texts:
Parsing Expression Grammars were introduced by Bryan Ford in Parsing Expression Grammars: A Recognition Based Syntactic Foundation.. Wikipedia says that it is an open problem to provide a Context Free language that can not be recognized by a PEG.

I am trying to understand the results from this paper -- The computational power of Parsing Expression Grammars by Loff et al. However, I am struggling to understand the notation used. What does the # mean in the following quote?

  We show that PEGs are computationally "universal". Take any
  computational function $f: \{0,1\}^{*} \rightarrow \{0,1\}^{*};$ then
  there exist a computable function $g:\{0,1\}^{*} \rightarrow N$ such
  that

  $\{ f(x)\#^{g(x)}x | x \in \{0,1\}^{*}  \}$

  has a PEG.

They use a slightly different symbol in Theorem 18.

  $ L = \{ f(x){⧖}^{g(x)}x | x \in \{0,1\}^{*}  \} \in PEG $

Where they talk about the $⧖$ as the number of symbols read (interpretation mine). How do I read this?

Further, can I take this to mean that the question whether a CFL exist that can not be recognized by a PEG is settled?

Essentially, if there exist a PEG for a P complete language, then all other problems in P can be reduced to it. Given that recognizing CFLs are in P, all CFLs should be reduced to recognizing this language.

Note that a similar question was asked by another user three years back, but this is new research.


texts:
I'm trying to construct a context free grammar for the language $\{a^ib^j:2i\neq3j+1\}$. I found that when $j$ is even, there are no problems. When $j$ is odd, there are some constraints on $i$. Now these are some examples of words that may NOT be parsed by the CFG:

aab
aaaaabbb (5 a's and 3 b's)
aaaaaaaabbbbb (8 a's and 5 b's)
...

But I'm completely stuck on finding a CFG for this language. Are there any tips that might help me in finding CFG's for a more complex language? I'm able to find the CFG for simpler languages, but I find this one particularly hard.


texts:
I'm assisting with the design of an algorithm over the next week to fit the following use case:

A person walking in a store has a tablet and approaches possible customers to notify them of a competition. When a customer enters their details, upon completion of the form - a request is sent to the server, and the customer will be randomly drawn (at that point in time) for a prize.

A maximum of 4 customers are chosen, the number of customers walking into the store is not known. The store is open from 8am until 4pm.

Would there be any other way (other than the ones stipulated) to solve something like this without knowing the average customers visiting the store?

Solution 1

I was thinking a normally distributed probability is used, where the parameters could be tweaked over time to fit this allowing customers to be selected (more or less) equally through out the day.

Solution 2

Similar to solution 1, but the time throughout the day is partitioned into segments. Between the hours of 8am and 12pm, a maximum of 2 people can be chosen.

I don't quite like the idea of doing this because if a majority of the customers come in the morning, this could lead to less than the 4 prize hand out expected of the day.


texts: I'm looking for an algorithm to find unknown patterns in a string

texts:
I am trying to detect patterns in huge code bases.
I managed to filter the entire codebase into a tagged string,
as in:
ABACBABAABBCBABA

The result should be:
ABA *3
CBA *2

I'm trying to build / use an algorithm which will find ANY unknown repeating pattern inside the string. The length of the pattern, it's composition, and the number of repeats is unknow.

To be a pattern it must occur atleast twice. And have atleast 2 items.
Once I detect the patterns I can represent them back in their original context

I have tried iterating over each tag.
For each tag find the following tag in the string.
continue until adding a tag matches only one repeat - hence no more pattern.

I get lost in implemetation (in JS or Python) and I'm hoping there is a better way.
Thanks.