texts: I need good book about algorithms, which explains recursion, backtracking and depth first recursion for beginners

texts:
I'm learning programming, Python 3 in particular, and I have a good book "Beginning Python - From Novice to Professional" by Magnus Lie Hetland, but the book doesn't explain algorithms at all, and I'm having truoble understanding some codes which include recursion since I'm new to 'CS-style' programming, I have moderate to good experience with mathematical code writing and reading/analyzing in MATLAB, which I use mainly for signal-processing and similar techniques of purely mathematical nature, but I'm totally new to the fundamentals of algorithms such as recursion and backtracking and depth-first recursion/search, I have good background in discrete mathematics and set theory, and I'm familiar with the fundamentals os CS like graphs and trees and memory/CPU structures since I'm an electronics engineer, what I really need is a good book(s) about algorithms.
After reading 9 chapters of Hetland's book, nearly half of it, I can say that I have good understanding of the fundamentals of Python 3 and OOP, but the book very often asks the reader to refer to Python's standard library as it doesn't explain many topics, some of which are very necessary, the book also doesn't include any small-projects or programs for practice and skill development, which are really big flaws in my humble opinion!! Although the web is full with video tutorials/courses as well as wikis and other sorts of educational websites, but I think the best way to learn anything is to get a good book describing the material in a structured way, so I got a copy of the infamous book "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, but after looking at the table of contents and reading the preface and the introduction of t part 1 of the book, I got to think that this book isn't what I'm looking for.
So I very much appreciate any other suggestions of books explaining algorithms for biginners, as well as good books for learning Python 3, Java and C, especially books with many practice/exploration projects and programs.
Thank you!


texts: In propositional logic how is the negation equivalent?

texts:
I am unable to understand how the negation of a sentence into CNF actually makes sense, hopefully somebody can explain it to me in understandable terms!
Given the sentence: If the battery is charged (A) and the screen is not cracked (B) then the phone is working (C)
The following makes perfect sense:
(A ∧ B) => C
I cannot get my head around how the negated form is true or how it works:
¬A ∨ ¬B ∨ C
I am struggling because "not A" means if the battery is not charged? So I cannot see how if the battery is not charged or the "screen is cracked" or the "phone is usable".
If A is false, so battery is not charged, how is that applying ¬A to it does not make it now true?
Any help would be appreciated.


texts:
I have a question about the regular operation 'star' in computational theory.

IF $A$ is $\{ good , bad \}$ then

$A^* = \{ \varepsilon , good, bad , goodgood, goodbad, badgood , \dots \}$

What is the exact "regular operation" mean then ?

Can we use $^*$ operation only for regular language ? I don't think so.

$L = \{0^n1^n \mid n \ge 0 \}$ is a famous example of a non-regular language, but it seems we can create $L^*$?


texts: How hard is it to solve for $P$ in $A = PBP^{-1}$?

texts:
From graph isomorphism, we know that two graphs A and B are isomorphic if there is a permutation matrix P such that
$A = P \times B \times P^{-1}$

So, to solve the problem, if two graphs are isomorphic, we need to find such a permutation matrix P. The problem is believed to be NP (and NP complete for the case of subgraph isomorphism). However, I found an example to solve for P which seemed promising to me and can be found in
http://en.wikipedia.org/wiki/Permutation_matrix
in section: solving for P.

The confusion I have now is, does that work for larger matrices? very large? am I right the above equation is hard to solve and can be candidate for a cryptographic system?


texts: Ambiguity with the Top View of a binary tree

texts:
What exactly is the top view of a binary tree?

I find great ambiguity and lack of clarity from the articles I find.

For example, this is what is used to demonstrate the top view on geeksforgeeks:

       1
    /     \
   2       3
  /  \    / \
 4    5  6   7

They go on to say that the top view is 4 2 1 3 7. The problem here is that they leave a lot of speculation on what isn't the top view. Consequently it becomes ambiguous to implement in code.

Stackoverflow examples are not any better. Hackerrank's example is even worse.

So I have signed up here hoping someone will tell me explicitly what the top view is because I have been trying to find out for 2 days. For instance, what is the top view of this tree:

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

And if I may be bold to ask, why is it important?


texts: kth smallest element using Randomized select

texts:
I have recently started studying Randomized algorithms on my own. I am refering to Rajiv motwani - randomized algorithms book.
Objective - find kth smallest element using radomized select in $O(n^\frac{3}{4} \log n)$ time

My attempt:

From array of n elements, pick randomly $n^\frac{3}{4}$ elements. Now from k th smallest element, at distance of $\sqrt n$ on either sides, I call sample point as $R_l, R_h$ respectively and elements at that place in array are $a, b$ respectively.
Now i pick all elements between a and b and call as P. If P falls in middle, then kth smallest element will be in right P picked up.
Aim is to find bad probability - probability that my choosen P does not contain kth smallest element. THis happens when all $n^\frac{3}{4}$ random points picked up are either on left side of kth smallest element or on right side of kth smallest element ie., my P will be on left side of kth smallest element or on right side of kth smallest element
Applying chebeshev inequality
$P(|\bar x - x| > \epsilon) < \frac{\text{Var}(\bar x^2)}{\epsilon^2}$ , $\bar x $ is Expectation of $n^\frac{3}{4}$ points falling on left side of kth smallest element and $\text{Var}(\bar x^2)$ is the corresponding variance.
ie., what is the probability that all my $n^\frac{3}{4}$ points are at $\epsilon$ distance on left side of kth smallest element or on right side of kth smallest element?
But Rajiv Motwani book considers
$\epsilon = \sqrt n$ which means that all $n^\frac{3}{4}$ points fall on left side of $x-\sqrt n$ and $x+\sqrt n$. Ideally should it be on left side of x and right side of x at some small epsilon distance? Kindly clarify here.


texts:
How does one pick an optimal block size for a cache with a specific size limit? For example, if I have a size limit of 900 bits for the whole cache, including tags and validity bits and everything, how do I choose the best block size to maximize utilized space? I assume it's different for directly-mapped caches vs. set-associative vs. fully-associative.

Brute forcing would be guessing and checking, but that seems inefficient. Is there a formula or something?


texts:
$a^ib^jc^k | (i = j)$ then k is even?

I can write it as
$a^ib^ic^k$ where k is even

OR

$a^ib^jc^k where (i != j)$

Both are DCFL and union of DCFL may be DCFL, but I think because of OR operator it gives a sense of parallelism and hence NCFL.

I haven't tried to make a DPDA for it, because in exam I might not be have much time to draw.

I don't think it is DCFL.

Theoretically, is this approach right ?


texts: Algorithmically find a formal grammar for a recursively enumerable formal language

texts:
The algorithmic problem is as follows.
The input is the source code of a program accepting an integer as input and outputting a finite binary sequence. This program defines a recursively enumerable formal language.
The output is a formal grammar generating this language.
How can we solve this problem?


texts:
I'm confused about the complexity of the following code:

for(i=1; i<=n; i = 2*i)
     for(j=1; j<=i; j++)
        print A[j]

I know that the first loop is logn, but I'm confused on what the second for loop would be since j is bound to i. Is this simply O(logn)?

I've plotted out the output as follows and thought it would be O(nlogn):

Assuming n = 8 or higher

i=1  j=1
i=2  j=1,2
i=4  j-1,2,3,4
i=8  j=1,2,3,4,5,6,7,8


texts: What is the size of a queue associated with a resource when the resource becomes a bottleneck?

texts:
In Software Performance and Scalability: A Quantitative Approach - Henry H. Liu, the author is presenting a scenario where the hardware becomes a bottleneck. In one ot the tests, he is checking the number disk (read/write) operations. In particular, the number of disk writes as the number of threads increases (see figure below).

After this, he states that: "A rule of thumb is that a resource is a bottleneck when the queue length associated with it is over 2 per unit. Since the RAID 0 configuration used for this test had four disks, the threshold would be 8. This threshold of 8 had been exceeded with a
write average queue length of 20 with 4 threads. With 16 threads, the associated average write queue length even went up to 132, which was over 16 times the threshold value of 8. It is clear that the system was disk write bottlenecked."

My question is: Why a resource is a bottleneck when its queue length is over 2? Why is not over 1? why is not over 1000000? why 2?


texts: Using pumping lemma to prove that $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ is irregular

texts:
Given the following language:
$L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $
I am trying to prove that it is not regular. On the one hand my intuition tells me that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{j's}$.
However, when I try to prove that it is irregular using the pumping lemma I have trouble finding which word I should use to arrive at a contradiction.
Any suggestions?


texts:
Given a query instance $x_q$ to be classified

Let $x_1,\ldots,x_k$ be $k$ instances which are nearest to $x_q$
$$ \hat{f}(x_q) \gets \operatorname*{argmax}_{v \in V} \sum_{i=1}^k \delta(v,f(x_i)), $$
where $\delta(a,b)=1$ if $a=b$, else $\delta(a,b)=0$ (Kronecker function).

If $f$ is an objective function to be optimized, why is argmax there? Can someone explain how this function gets updated. This is for $k$-nearest neighbor function.


texts: Calculate ϴ dependent on n for an algorithm with constant c

texts:
I want to calculate ϴ dependent on n for this algorithm:

for (k = n; k < c; k++){
    j = 1;
    while(j < n){
        j++;
    }

n is the parameter. c is a constant.

I calculated the amount of operations to (c-n)*(n-1). But now I don't now how to deal with c.


texts:
Lets say I have a global dataset and I run queries over those data set.
For example my dataset would be

#id, #Name, #Employee, #Birthdate, #number_of_children
1, Nick, Nasa, 1982, 1
2, Jack, Exon, 1985, 5
3, Tom, ABCD, 1978, 0

And I can run queryies on those dataset.
sample queries would be
* #Query => #Result_ids
* (Name starts with A) => [1]
* (Birthdate before 1983 and have children ) => [1]

I want to store those queries on a data structure and I want to be able to do set operations on those queries like intersection and union. So an example union operation would be.

(Birthdate before 1983) intersection (have children) => (Birthdate before 1983 and have children)

I also want to be able to findout if one query is subset or superset of another one. For example.

(Birthdate before 1983) is superset of (Birthdate before 1980)
(Have 3 children) is subset of (Have more than 1 children)

(Name = Jack and born in 1980) is subset of (Born before 1990)

I will have a program that will have thousands of queries. And it will combine those queries to make more variety of queries. When I have a new query, I will compare it with existing queries to see if I have an exact query in store or have a superset.

Can anybody suggest me a data structure that is fast enough to store and operate on those data?


texts: Trouble understanding the master theorem, from Jeffrey Erickson's Notes

texts:
I'm looking at Jeffrey Erickson's Notes on the master theorem
(page 10).

Part (b) of the theorem states that if $T(n) = aT(\frac{n}{b})+f(n)$, $af(\frac{n}{b}) = kf(n)$ and $k>1$ then T(n) is $\Theta(n^{\log_b(a)})$. But I get a different result.

Using recursion trees we have $$T(n) = \sum_{i=0}^{\log_b(n)} a^i f\left(\frac{n}{b^i}\right) = \sum_{k=0}^{\log_b(n)} k^i f(n)\,.$$

If $k<1$ then this is $\sim f(n)$ as desired. If $k=1$ then this is $\sim \log_b(n)f(n)$ as desired. But if $k>1$ then this is an ascending geometric series, so the last term dominates. Then we have $$\sim k^{\log_b(n)}f(n) = n^{\log_b(k)}f(n)\,,$$ which is wrong; the right answer is $\Theta(n^{\log_b(a)})$. Where does my reasoning go off the rails, and what is the correct solution?

Any help is appreciated.

EDIT: I think my answer is actually right, and is equivalent to Erickson's simpler answer. Note that $k^nf(n) = k^{n-1}af(\frac{n}{b}) ... = ka^{n-1}f(\frac{n}{b^k-1}) = a^nf(\frac{n}{b^k}).$  Hence $k^{\log_b(n)}f(n) = a^{\log_b(n)}f(1) \sim n^{\log_b(a)}$.


texts: What is Ironic complexity? What are some good resources to learn about it?

texts: The term "Ironic complexity" was coined by Scott Aaronson for the stuff Ryan Williams does in the area of complexity theory. Could anyone tell me what kind of problems and approaches does Ryan Williams work upon? And is there a survey or course on it for self-study?


texts: Is language $\{a,b\}^*$ same as language $\{xy \in \{a,b\}^* \mid |x|_a = |y|_b \}$?

texts:
I need to prove or disprove if these two languages are same.
So I assume that these lanaguages are same because I think that every word from $\{a,b\}^*$ could be concatenated from two words $x$ and $y$ where $|x|_a = |y|_b$. So $x$ and $y$ must belong to $\{a,b\}^*$, too. Then I can write and prove this:

$\{a,b\}^* \subseteq \{xy \in \{a,b\}^* \mid |x|_a = |y|_b \} \wedge \{xy \in \{a,b\}^* \mid |x|_a = |y|_b \} \subseteq \{a,b\}^*$

So I assume that $z \in \{a,b\}^*$. Then $z = z_1z_2...z_i$ where $z_1,z_2,...,z_i \in \{a,b\}$

Here I stucked and I don't know (1) how to continue, (2) if the way of proving i choose is correct or not.


texts: Polynomial-time algorithm for Graph Isomorphism in case of Maximum Constrained Maximum Degree

texts:
From Wolfram:

  A polynomial time algorithm is however known for planar graphs (Hopcroft and Tarjan 1973, Hopcroft and Wong 1974) and when the maximum vertex degree is bounded by a constant (Luks 1982; Skiena 1990, p. 181).

What are the running times of such algorithms, in terms of size of the graphs? What algorithms are used in practice for graph isomorphism?


texts: In a DAG, longest path where every vertex has degree at most 2

texts:
I have a directed acyclic graph (DAG).  How I can find the longest path using only vertices with degree at most 2?

Currently, I try this

def all_simple_paths(g):
  for path in all_paths(g):
      if len(path) > 2:
          center_path = path[1:-1]
          nodes_degree = g.degree(center_path).values()
          if max(nodes_degree) <= 2:
              return path

but that might output any path, rather than the longest path.


texts: Why we do isomorphism, automorphism and homomorphism?

texts: What are the key differences between these three terms isomorphism, automorphism and homomorphism in simple layman language and  why we do isomorphism, automorphism and homomorphism ?


texts: How well does DEFLATE perform, compared to the theoretical optimum?

texts:
I know that there is an inherent limit to how much you can compress data using lossless compression.

Basically, the only thing lossless compression can do is reduce dependencies between symbols, remove repetitions, and so on, so that the result looks more like completely random data rather than what we usually see.

From what I understand, nowadays the optimal method of compression, which gets very close to the theoretical optimum of making your data look like random garbage, is arithmetical coding that doesn't really operate on the level of characters at all, but this isn't used in most applications. (I'll save the why not? for a different question).

Instead, we use algorithms like DEFLATE that combine Huffman coding and LZ77 to achieve better efficiency than either alone.

How efficient are these algorithms, as commonly implemented, compared to the optimal efficiency?


texts: A problem is NP-hard iff its complement is coNP-complete

texts:
$A$ is NP-hard iff $\overline{A}$ is $coNP$-hard, where $\overline{A}$ does mean complement of $A$.

I can't figure out why it is true. Let $A\in NP-hard$. I know that each problem in $NP$ is polynomially reducible to $A$.  So, let's "negate" $A$, then by definition: $\overline{A}\in coNP$.  However, I am not sure why $\overline{A}\in coNP-hard$.  Could you explain it me ?

My intution is that $NP$ and $coNP$ contains only decision problems, using this fact we can use machine for $A$ and negate answer.


texts: What's the difference between cache miss penalty and latency to memory?

texts: Can I say that cache miss penalty includes latency to memory? My current understanding is that cache miss penalty is the time moving data from the layer closer to main memory to it. But I'm not sure about what's the meaning of latency to memory? If they're not the same what's the overlapping part?


texts:
I have this language:

$$ L = \{ a^i b^j c^k :  i + 1000\ < j + 100 < k  \}, $$

and what I believe is that we can't prove with the Pumping Lemma that it is not context-free, because we would always be able to choose $x$ as $b$, $v$ as $b$ and $y$ as $c$. For example, suppose we have the string $a^pb^{p+1000}c^{p+10000}$. We can choose $x$ as $b$, $v$ as $b$ and $y$ as $c$, and $uv^ixu^iz$ would always belong to $L$. But I can't find a grammar for $L$.


texts: How to restore a broken minimal spanning tree?

texts:
We're given $T$ a minimal spanning tree (MST) of a non-directed, connected graph $G=(V,E)$ with non-negative weights for each edge $e \in E$. Let $e^* \in T$ be an edge in $T$ and let $G'=(V,E')$ be the graph which we get after removing $e^*$ ($E'=E\setminus \{e^*\}$). $G'$ is also connected.

I need to propose an algorithm which will run in $O(|E|)$ time and will restore $T$ such that it will yield an MST $T'$ for $G'$.

I'm really not sure if I'm in the right direction but this is what I thought of:

Let $e^*=(u,v)$.

a) We mark $e^*$ and remove it from $T$ and b) find the connected component of node $v$ by using BFS algorithm on $T$.

Now we have 2 connected components:

the first starts from $v$ let's call it $S = T\setminus e^*$
the second is $V\setminus S$

Clearly $e^*\notin S$ and $e^* \notin V\setminus S$. Also $S\neq V$ because otherwise we'd get a connected graph after the removal of $e^*$ of $n-1$ edges which would mean that there were $n$ edges in $T$ which is a contradiction since $T$ is a tree.

c) Then we start looking for a minimal edge $e'$ from $u\in V\setminus S$ to $v\in S$.

d) Once we found  $e'$ we'll add it to $T$ and we'll get $T'$.

I'm having trouble with running times.

a) we need to traverse $G$ in order to find $e^*$ so it's the running time of BFS which is $O(|E|+|V|)$ and because $G$ is connected ($|E| \ge |V|-1$) then the time is $O(|E|)$.

b) BFS again so $O(|E|)$.

c) This could also be $O(|E|)$ because in the worst case the graph could be something like this:

d) is O(1).


texts: Test cases for subtyping with dependent types

texts:
I implemented a simple type system inside Agda and I'm trying to understand, how expressive it is. The system consists from a predicative hierarchy of universes in the style of Russell, natural numbers and bounded and unbounded dependent quantifiers (there were reasons to separate these two instead of just adding an alias for ∀ A <: Top -> ...). It also permits writing universe polymorphic code, for example it's possible to represent the following functions, written in Agda:

id : ∀ α -> (A : Set α) -> A -> A
id _ _ x = x

Set' : ∀ α -> Set (suc α)
Set' α = Set α

Subtyping rules are

ℕ <: ℕ
α' ≤ α -> Type α' <: Type α
(∀ x -> B' x <: B x) -> Π A B' <: Π A B

The last rule holds for both bounded and unbounded quantifiers.

So

the subtyping rule for product types is covariant only
there is no the subsumption rule x : A, A <: B -> x : B
there is no the rule ∀ A -> A <: Top (Top isn't presented at all)
the subtyping relation is provably a preorder

What I'm looking for is some test cases for this variation of subtyping. Here is one example, taken from the "A calculus of constructions with explicit
subtyping" paper:

It would be ideal to have a bunch of similar definitions. Examples that require contravariant subtyping for product types or the subsumption rule are good too, since I can define some coercions. It should also be easy to add sum types if needed, or at least to represent them in terms of product types.

Please note, that I'm not interested in applications of conservative extensions (like coercive subtyping and refinement types) of type systems without subtyping. Just basic dependent subtyping stuff.


texts:
I am trying to solve following problem but unable to solve this. Can anyone tell me how to approach this kind of problems where it is not easy to make DFA.

  The minimum number of states required to construct a DFA that recognizes the language of strings over the alphabet ${a,b}$ whose tenth symbol from the right end is $a$?

I tried converting R.E of the language which is $(a+b)^*a(a+b)^9$ into DFA but couldn't convert. Can anyone convert this into DFA or provide a $generalized$ solution when it is $n^{th}$ symbol from the right hand of the string?


texts: Does $c^n = O(2^n)$ and $log_c(n) = O(log_2(n))$ for any constant $c$?

texts:
I thought they did, but recently I tried to express $3^n$ as $k \times 2^n + o(2^n)$ for some constant $k$ but wasn't able to. All I found was $3^n = (\frac{3}{2})^n 2^n$. What am I misunderstanding here?
I suppose my question applies to $log_c(n) = O(log_2(n))$ as well.


texts:
I am aware that $MA \subseteq ZPP^{NP} \subseteq \Sigma_2^{P}\cap \Pi_{2}^{P}$ and also $NP^{BPP} \subseteq MA \subseteq AM \subseteq \Pi_{2}^{P}$.

My question is: In this whole thing, where does $P^{NP}$ lie? (Obviously, $P^{NP} \subseteq ZPP^{NP}$) But, what about the relationship between $MA$ and $P^{NP}$? Which is contained in which one?

Intuitively, It is known that $MA_{EXP} \not\subset P/poly$, but for $EXP^{NP}$, no polynomial size circuit lower bound is known. Does that mean $P^{NP}$ is contained in $MA$?


texts: Find the asymptotic time complexity of the following

texts:
while(n>1){
   n = sqrt(n);
}

Where sqrt returns the root of n. n = 2^k and k is a power of 2.


texts:
According to the polynomial-time-reduction definition

"If problem $Y$ can be reduced to problem $X$ in polynomial time, we denote this by $Y \leq_p X$."

If $X$ is one of already known NP-complete problem then we can say that $Y$ is NP-complete.

From my understanding, $p$ should be always polynomial and this cannot be an exponential function such as $2^n$ or $3^n$.

However, my question is if $Y$ or $X$ already has a lower bound that is not polynomial, which is $2^n$ or $3^n$ then can I still say that $Y$ is NP-complete?

In other words, does lower bounds for $X$ and $Y$ matter?


texts: Finding many different minima of nonlinear cost function

texts:
Given a nonlinear cost function $G(\vec{x})$ of many variables, does there exist a method that allows one to find successive local minima $\vec{x}_0, \vec{x}_1, \dots$ so that $\vec{x}_n$ is orthogonal to $\vec{x}_{n-1}, \vec{x}_{n-2}, \dots, \vec{x}_0$?

Sorry for the apparent lack of effort on my part, but the field of optimization is vast and I do not have a lot of experience. I have searched for variants of a nonlinear conjugate gradient method that have the above property, but haven't been able to find anything.


texts: Restriction: polynomial time decision of instance is why needed to "decision Problem"?

texts:
I am reading book "combinatorial optimization 3rd edition(Bernhard Korte、 Jens Vygen)".

(latest version is sixth.)

There are some discriptions in this book that I don't understand

  Not all binary strings are instances of Hamiltonian Circuit but only those
  representing an undirected graph. For most interesting decision problems the in-
  stances are a proper subset of the 0-1-strings. We require that we can decide in
  polynomial time whether an arbitrary string is an instance or not:

quote from p350

  decision problem is pair P = (X,Y), where X is a language decidable in polynomial time.

quote p351

Why decision problem required that decide in polynomial time whether an arbitrary string is an instance or not?

I can't found any reasons of this restriction in the book.


texts:
It is known that any (deterministic, single-taped) Turing-machine that runs in time $o(n\log n)$, decides a regular language (e.g., see this link). Thus, there exists an equivalent Turing-machine that runs in time $O(n)$. In other words, if $t(n)=o(n\log n)$ then $$\mathsf{DTIME}\left(t\left(n\right)\right)\backslash\mathsf{DTIME}\left(n\right)=\emptyset.$$

I was wondering whether there exists an example in which the original Turing-machine was not already running in time $O(n)$.

To sum up: Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$?


texts:
Given the following grammar:

S -> A a
A -> B D
B -> b
B -> ε
D -> d
D -> ε

first would be:

B: {b,ε}
D: {d,ε}
A: {b,ε,d}
S: {b,ε,d,a}

and follow would be:

S: {$}
A: {a}
B: {d,a}
D: {a}

The LL(1) parse table should be easy to build. According to LL(1) parsing table construction I can simply follow this algorithm:

foreach(A -> α in the grammar):
  write A -> α in T[A,b], ∀  b ∈ first(α);
  if ( ℇ ∈ first(α) ):
     write A -> α in T[A,x], ∀ x ∈ follow(A);

However, this would leave T[S,a] and T[A,d] blank, so "a" and "d a" could not be parsed:

row S:
  column  b -> S -> A a
  column  d -> S -> A a
  column  $ -> S -> A a
row A:
  column  b -> A -> B D
  column  a -> A -> B D
row B:
  column  b -> B -> b
  column  d -> B -> ε
  column  a -> B -> ε
row D:
  column  d -> D -> d
  column  a -> D -> ε

When I use a tool like this: http://jsmachines.sourceforge.net/machines/ll1.html values for T[S,a] and T[A,d] are generated. Am I using a wrong algorithm for generating the parse table, is the grammar not LL1 or am I doing something else wrong?


texts:
$L_1$ is a recursively enumerable language over some alphabet
  $\Sigma$. An algorithm effectively enumerates its words as $w_1, w_2, ...$.  $L_2$ is another language over $\Sigma \cup \{\#\}$ as
  $\{w_i\#w_j : w_i, w_j \in L_1, i < j\}$ Consider the following
  assertions.

  $L_1$ is recursive implies $L_2$ is recursive
  $L_2$ is recursive implies $L_1$ is recursive

  Which statements is/are true?

I reasoned both the statements to be true.

Statement 1 is true. $L_1$ is recursive means it can lexicographically enumerate its strings. The membership question for $L_2$ can be easily settled using the decider and lexicographic enumerator of $L_1$.

Statement 2 is true. The algorithm which decides $L_2$ can be modified to accept if the input string matches either $w_i$ or $w_j$. This settles the membership question for $L_1$.

The given solution to this question however says that statement 2 is false. Could you let me know if my reasoning has gone wrong someplace?


texts: How to generate (Java) source code in academically acceptable way - using abstract syntax tree?

texts:
I am trying to do automated programming research: business software generation from the knowledge base that is implemented as Scheme (Lisp dialect) code (in the framework of http://opencog.org/ Atomspace). My question is - how to generate Java source code in academically acceptable way?

I know or I can imagine several ways:

Raw code generation: I can predict what classes and what members can be and create one large literal constant that is the source code.
Find or implement templating engine like Visual Studio's T4 templates
Find something about code generation from the UML models. I don't know yet how MDD tools implement such generation
I can genereate Java Abstract Syntax Tree in my Scheme code and then find tools generate Java source code from Java AST. Actually this could be - in my opinion - the most academically correct way that is also the best integrated in my workflow and that is the most extendable. My OpenCog Scheme Atomspace in effect is large hypergraph and Java AST is (hyper)graph to, so - AST generation reduces to the graph transformation. This seems the path to follow, isn't it?

There are some technical questions as well - are there tools that accept Java AST (in some form) and that generate Java source code? Can such AST-2-code tools be generated from the formal grammar of the programming language (https://docs.oracle.com/javase/specs/jls/se7/html/jls-3.html is example of the specification in the free, readable form)?

So - the question is - what is the best practice of code generation in the computer science academic project?


texts: Algorithm: "Minimum" maximum flow with extra capacities

texts:
Problem:

Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, find a total extra capacity needed E so that maximum flow from source to sink is greater than or equal to F and flow in each edge that has nonzero flow.

I don't know how to solve this variation of maximum flow problem. It is obvious that if maximum flow I find without extra capacities is greater than or equal to F, then there is no need for extra capacity. If it is less than F, should I add extra capacity in each edge one by one and find max flow again till I find the closest one to F (if it is not enough, then take in pairs, triplets, etc.)? This solution seems inefficient to me.


texts: Complexity for finding zeroes of sum of cosines

texts:
Consider the following equation with variable $n \in \mathbb{N}$:

$$\sum \limits_{i=1}^{k} \cos(n\theta_{i}) = 0.$$

Given $\theta_1,\dots,\theta_k$, I'd like to determine whether there exists $n \in \mathbb{N}$ such that the above equation holds.

For $k = 1$ a solution can be directly found in $O(1)$ time by taking the inverse cosine.

For $k = 2$ we can first factor it using the identity

$$\cos(A) + \cos(B) = 2\cos(\frac{A+B}{2})\cos(\frac{A-B}{2})$$

and then set both terms individually to $0$. The running time will be $O(1)$.

If all the $\theta_i$ are rational multiples of $\pi$ then the equation is periodic and solvable.

Are there general algorithms of solving for $k > 2$ and for values of $\theta_i$ for which $\cos(\theta_i)$ are algebraic numbers? If not, then are there any undecidability results like for roots of polynomials (as mentioned in the paper below)?

Undecidability in number theory.  Bjorn Poonen, Notices of the American Math Society, March 2008.

I am considering all computation to be symbolic and exact. For example $\theta_1 = \cos^{-1}(1/3)$ is a possible input.


texts: Understanding growth function of closed intervals in $\mathbb{R}$

texts:
I as studying VCdimensions and growth functions and found the following example on Wikipedia:
The domain is the real like $\mathbb{R}$. The set H contains all the real intervals, i.e., all sets of form $\{c \in [x_1, x_2] | x \in \mathbb{R}\}$ for some $x_{0, 1} \in \mathbb{R}$.
For any set C of m real numbers, the intersection $H \cap C$ contains all runs of between 0 and m consecutive elements of C. The number of such runs of ${m+1 \choose 2} + 1$, so Growth(H, m) = ${m+1 \choose 2} + 1$.
Can anyone please explain to me what does the term "all runs of between 0 and m" refer to here and why the growth function is ${m+1 \choose 2} + 1$ and not ${m+1 \choose 2}$?
Thank you very much!


texts:
I've recently learned about Prolog and Logic programming which I find pretty cool, but the compiler is currently like magic to me and I want to know how they work.
After a little bit of research I discovered that logical compilers are based on Warrens Abstract Machine (WAM). I've tried to find some information on WAM, but the Wikipedia page only describes what it is and not how it works and the book Warrens Abstract Machine: A Tutorial Reconstruction doesn't read very well for me.
Could I please have basic explanation of how WAM works?


texts: Covering a polygon with n circular rings

texts:
Question 1: Why we can/can't solve the following problem using a geometric constraint solver?
Question 2: Is there any algorithm to solve this problem?
Question 3: Can we reduce this problem into some known computational problems?

Input:
1. $C_1, ..., C_n$: Centres of $n$ circular rings.
2. $S$: A polygon of arbitrary shape in the 2D plane.

Notations:
1. $(OR_i, IR_i)$: outer radii and inner radii respectively for circular ring $i$
2. $R = \text{ring}_1 \cap \dots \cap \text{ring}_n$: the intersection of the rings (i.e., the region of space formed by their intersection: the set of points that are contained in all $n$ of the rings)

Output:
Find $(OR_1, IR_1),..., (OR_n, IR_n)$, such that region $R$  covers the polygon $S$ with minimal error area.

Error area is defined as:
$$\text{Area}(S - R) + \text{Area}(R -S)$$

Intuitively, I want an algorithm to find optimal $(OR, IR)$ for each ring to cover a given shape $S$, so the error area (the parts of $R$ outside the given shape: [$\text{Area}(R - S)$] + the parts of the shape not covered by $R$:  [$\text{Area}(S - R)$]) is minimal.

The problem differs from this problem in following ways:

The polygon should be covered by the ring formed by two circles with same centre.
This is a simpler problem in the sense that it has fewer variables. The position of the centres are given; we only need to find the inner and outer radii.


texts: How to find the number of discrete states possible by current computers?

texts:
In his famous article, "Computing Machinery and Intelligence", Allan Turing talks about discrete-state machines and the largeness of the number of states provided by that time "state-of-the-art" machine, "Manchester Machine", which he states is about 2^165,000. Link to the article

Well, that was 1950's. I'm trying to compare it with modern day computers and get an average number of states for a usual commercial machine. How can I find it?

Is it related to memory size (Turing calculates it by the number of "stores", or sheets of paper available)? If so, would this make the number of states tend to infinity due to the current possibility of writing/erasing memory at will?


texts: "Knapsack problem" with repetition, "lesser or equal" constraint, and recording all valid combinations

texts:
In a game I am developing I came across an interesting problem, that seems like it could be solved using some modified variant of the knapsack problem, but it's a bit over my head.
Let $x_i$, $ 1\leq i \leq n$ be the objects we are dealing with, and $p_i$, $ 1\leq i \leq n$ the cost associated with each item.
Suppose there exists some total budget $B$.
I now need to find all combinations of items, such that:

the sum of their costs is lesser than or equal to the budget $B$
each object $x_j$ may appear any number of times, including not at all

This doesn't seem like a traditional optimization problem anymore, since I actually need to find all combinations that fulfill these constraints. How can this be solved efficiently? I was thinking about trying to modify the dynamic programming approach employed to solve the traditional knapsack problem, but it's a bit over my head.


texts:
Why are the words in a cache line adjacent to one another?
Does this arrangement improve reading/writing performance or are there other reasons to justify this choice?


texts: Calculate physical address given a reference number and 2-level page table

texts:
How can I calculate a physical address from a reference number and a 2-level page table?
A system with a 2-level page table, and the contents of page table No. 1 of level 2 (p1, p2, offset) are: {(32, v), (45, i), (12, v), (5, v), (34, i)}. Suppose the frame size is 4KB; the address register is 32 bits, and the number of bits for level 2 (p2) of the address register is 10. Given a reference = 4225332, its physical address is...?

170292
215348
80180
162100

I'm not sure whether this is correct:
The frame size is 4KB so the number of bits for the offset is 2^12. Therefore, number of bits for p1 should be 10.
The reference number in 32-bit binary representation is: 0000 0000 0100 0000 0111 1001 0011 0100
The offset should be: 1001 0011 0100 = 2356.
The first 10 bits of the 32-bit reference is 0000 0000 01 = 1 so p1 = 1.
The next 10 bits are 00 0000 0111 which is 7. But the page table above only goes up to 4 so there should be no correct answer.
Am I correct?


texts: How to perform AND on binary "recursive repeating sequences"?

texts:
Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related to how many times this sequence is repeated, or can contain a bit either 0 or 1. Following image describes it visually:

On this image repetition is denoted by lower index number nearby ending bracket. The bits need to be expanded are denoted by regular size font.
Each sequence can produce binary sequence (sequence of bits), when we expand it.
The questions are:

Can we create a algorithm, that performs AND on two recursive repeating sequences, without expanding both of them? (The algorithm should produce third recursive repeating sequence, such when we expand it, it is AND on both expanded input sequences).
If the answer for first question is true, how such algorithm will look (for example in pseudo code) ?

Note: In practice, the numbers responsible for repetition may be very large, so expansion of whole sequence is not practical in terms of computation - but if algorithm will need to do it partially, it may be accepted.


texts: Is there an equivalence between "does this program halt" and "is this sentence provable"?

texts:
It seems, intuitively, that determining if an program halts when running on a TM should be as difficult as determining if a sentence is provable within a finite set of logical rules. Furthermore, there are as many sentences as there are program and there are as many finite set of logic rules are there are TM (there are countably infinitely many of each).

Can we interpret a universal Turing machine executing programs as equivalent, in some way, as finding the proof for all theorems for all finite set of logic rules. If a program halts on a TM then it means that the program is a theorem of some logical system, and vice-versa.

If so, how? If not, why not?


texts:
I'm having trouble proving Hoare logic questions as I'm not sure of the process that is taken to prove them. I understand that they're rules such as assignment axiom, pre-condition strengthening, post-condition weakening etc... but how you actually apply these rules to the question is a little out of my understanding.

Cheers


texts: Number of possible search paths when searching in BST

texts:
I have the following question, but don't have answer for this. I would appreciate if my method is correct :

Q. When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70, 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root node containing the value 60?

(A) 35 (B) 64 (C) 128 (D) 5040

From the question, I understand that all nodes given have to be included in traversal and ultimately we have to reach the key, 60. For example, one such combination would be :

10, 20, 40, 50, 90, 80, 70, 60.

Since we have to traverse all nodes given above, we have to start either with 10 or 90. If we start with 20, we will not reach 10 (since 60 > 20 and we will traverse right subtree of 20)

Similarly, we cannot start with 80, because we will not be able to reach 90, since 80>60, we will traverse in left sub tree of 80 & thus not reaching 90.

Lets take 10. The remaining nodes are 20, 40, 50, 70, 80, 90. Next node could be either 20 or 90. We cannot take other nodes for same earlier mentioned reason.

If we consider similarly, at each level we are having two choices. Since there are 7 nodes, two choices for first 6 & no choice for last one. So there are totally

$2*2*2*2*2*2*1$ permutations = $2^6$ = $64$

Is this a correct answer?
If not, whats the better approach?
I would like to generalize. If $n$ nodes are given then total possible search paths would be $2^{n-1}$


texts: challenge: Closing hash, linear probing, probe length 1

texts:
The challenge says that there is a hash algorithm with a bug, the bug is given if it reaches the end of the array and did not find space to save the element,
it discards it directly (that is, it does not try to place it in positions 0, 1, 2 ... as it would be correct)

In a hash table using closed hash, linear probing, probe length 1.

What is the probability that with this test we discover that the implementation n has a bug, if N = 27 and K = 42?

Example K=2, N=2:
The only case is if both hashes are 1. In this case, the first element in array [ 1 ] is first saved.
Then, the next element does not have space in array [ 1 ] and since it is the last position of the array, will discard it

I made a script to bruteforce all combinations and find the probability for the firsts N / K

The pseudocode is:

function bruteforce(array):
  hashtable=
        {0="" , 1="" , ..., ..., k-1=""}
  for element in array:
      canStoreThisCombination=False
      for j in range (element,len(hashtable)):
          if (empty(hashtable[j])):
              hashtable[j]="used"
              canStoreThisCombination=True
              break
  if not canStoreThisCombination:
      tot=tot+1

for each combination of N elements:
  bruteforce(actualCombination)

print tot/(k^n)

and got the following results:

table

Combinations for K=3

Combinations for K=4

Combinations for K=5

I'm looking for probability as an irreducible fraction


texts: Proving that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular with pumping lemma

texts:
I'm trying to understand the pumping lemma for regular languages and would like to prove that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular.

My suggestion is as follows:

Assuming $L\in{}REG$, let $p$ be the number that exists for $L$ according to the pumping lemma.

Let $w=ab^{p}ba^{p}$ with $|w|=2p+2>p$.

Since $w\in{}L$, $w$ can be written as $w=xyz=ab^{p}ba^{p}$, so that:

$|xy|\leq{}p$, in this case $xy=ab^{q}$ with $q\leq{}n-1\leq{}p$
$|y|\geq{}1$, in this case $y=b^{n}$
$\forall{}i\geq{}0,xy^{i}z\in{}L$

But for $i=0$ we have $xy^{0}z=xz=aba^{n}\in{}L$ which violates the definition of $L$, so that $L\notin{}REG$.

Does this constitute a sufficient proof with the pumping lemma or am I at least on the right track? I would appreciate any feedback.


texts: How do quantum computers find the global minimum?

texts:
If I understand correctly, quantum computers work by trying multiple methods of solving a problem simultaneously, using quantum superposition. However, if you try to "look" at a superposition-ed atom, you will find either one or the other-1 or 0. What I've heard is that this is random.

So, if you compute all these solutions, how do you know which is the best without "looking" at it? Wouldn't the result just be random, and you can only see the result of one answer? Now, I've heard that this can be solved by quantum annealing, but I don't really understand it. I'd like to know how this works in fairly layman-ish (It's a word) terms.


texts: Binary Search Tree: Replace $k$ min elements with their average

texts:
Given a valid binary search tree whose keys are unique real numbers, and a set of $k$ pointers to the $k$ minimum elements in the tree, will the BST property be maintained if I replace all $k$ elements with the average of the $k$ elements?

The BST property as given in Corman:

  Let $x$ be a node in a binary search tree. If $y$ is a node in the
  left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the
  right subtree of $x$, then $y.key \geq x.key$.

I've tried this with a few test cases for $k=3$ and a few different trees, and it seems to hold, but I'm not sure if it actually does and how I could prove it.


texts:
I want to prove that a problem $P_1$ is NP-complete. Let say that I want to do a reduction from SAT problem.

If the instance of problem $P_1$ depends on $M$ and $N$, can I specify the sturcture of the instance of the SAT problem?

More precisely, can I say that, for example, the instance of SAT problem is composed of $M\times N +1$ clauses and every clause has $M+N$ literals ?

Based on this structure of the instance of SAT problem, I construct an instance of $P_1$. Is this proof correct?


texts:
I'm trying to find the name of this problem, and with it a reasonable algorithmic solution.

Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights $a_1,\dots,a_m$, satisfying $\sum_iw_i=\sum_ja_j=1$.  The goal is to find an assignment $f:\{1,\dots,n\}\to\{1,\dots,m\}$ of the weights to the buckets such that $f$ is nondecreasing (the weights have to be in the same order as the buckets) and the sum of the weights in each bucket is "close" to the target for that bucket.

The sense of "closeness" is up to the implementation (whatever is easiest to model), but for concreteness let's suppose this is least-squares error; then we can define the error of a given assignment as $\varepsilon(f)=\sum_{i=1}^m(\sum_{j:f(j)=i}w_j-a_i)^2$, and the goal is to find the $f$ that minimizes $\varepsilon(f)$.

This problem seems similar to the knapsack problem, but there are some differences in the constraints and I don't know if this is also NP-complete. Does this problem have a name or reduce to a named problem?


texts: Do determinacy of one-step evaluation and uniqueness of normal forms apply to all (or most) languages in TAPL?

texts:
In Types and Programming Languages by Pierce, when talking about untyped arithmetic expressions in Chapter 3, there are two theorems:

$-→$  is single-step evaluation relation:

  3.5.4 Theorem [Determinacy of one-step evaluation]: If $t -→ t'$ and $t -→ t''$ , then $t' = t''$ .

$-→ ∗$ is multi-step evaluation relation:

  3.5.11 Theorem [Uniqueness of normal forms]: If $t -→ ∗ u$ and $t -→ ∗ u'$ , where $u$ and $u'$ are both normal forms, then $u = u'$.

Do the two theorems also apply to all (or most) the other languages/systems in the book, or only to the untyped arithmetic expressions?

From my limited experiences in a few programming languages, it seems that an expression is always evaluated in exactly one deterministic process, so I wonder if both theorems apply to all the languages.

Thanks.


texts: Linear codes : why has the parity check matrix dimensions $(n-k)*k$?

texts:
I am studying Quantum error correction that is based on some aspects on classical error correction.

I am reading some very basics around linear error correcting codes.

I consider a linear code [n,k]: thus it encodes k bits of information into n bits.

My question: I don't understand why the parity check matrix has $n-k$ lines.

What I understand from the topic.

If I call $x$ the column vector of the information bits I want to encode in the n-bits, I define $G$ the generator matrix such that:

$$ y = G x $$

Where $y$ is my encoded information.

The $H$ matrix is built such that its kernel is the code space. Thus, its kernel must be composed of the column vectors of $G$ as the code space is spanned by the column vectors of $G$.

All this means that the line vectors of $H$ must be orthogonal to the column vectors of $G$.

But why do we have to take $n-k$ lines in $H$, why not $n$ lines, or $2$ lines ? I guess it is a way to ensure us that the Kernel of $H$ is exactly the code space but I don't understand why this number of lines ensure this.


texts: Non-deterministic logarithmic time complexity class

texts:
Is that true that $Time(O(log(n)))=NTime(O(log(n)))$ iff $P=NP$?
It seems to me to be true, as I only need to take log on both sides, since log of a polynomial is $O(\log(n))$, but I don't know how to derive a proof from this intuition.


texts:
A partition of a set S is a separation of the set into an arbitrary number of non-empty, pairwise disjoint subsets whose union is exactly S. What manner of a data structure should be used to represent a partition of a set if the following methods need to be optimized:

moving an element from one part to another, possibly an entirely new one, and
iterating over the parts of the partition.

A naive way of prioritizing 1 would be a hash/tree/whatever mapping from set elements to "part labels", but iterating over the parts would require O(N) for first constructing the actual parts from the labels. 2 is naively prioritized as a hash/tree/whatever set of hash/tree/whatever sets, but then moving elements around, especially to new subsets, incurs that memory management overhead.

Is there a way to get the best of both worlds? The implementation I need is Python but I imagine this is a cross-language question.


texts:
I came across this hoare logic for factorials but I don't quite understand it. We multiply F and X but we're not adding up all values of F so how do we get the sum/factorial at the end?

Precondition: $\{ X > 0 \land X = x \}$

$F := 1$
while $X > 0$ do
$\quad F := F \cdot X$
$\quad X := X - 1$
od

Postcondition: $\{F = x!\}$


texts: Efficiently computing the smallest integer with n divisors

texts:
In order to tackle this problem I first observed that

$$\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1)$$

Where $\phi(m)$ is the number of (not necessarily prime) divisors of $m$. If $m$ is the smallest integer such that $\phi(m) = n$, then

$$\phi(m) = n$$
$$(e_1 + 1)(e_2 + 1)\cdots(e_k +1) = n$$

Now we must choose $e_i$ such that $\prod_{i} p_i^{e_i}$ is minimal. The choices for $p$ are trivial - they are just the primes in ascending order.

However, my first thought for choosing $e_i$ was incorrect. I thought you could simply factor $n$, sort the factors in descending order and subtract 1. Most of the time this works fine, e.g. the smallest integer with $n = 15$ divisors is:

$$15 = 5 \cdot 3$$
$$15 = (4 + 1)(2 + 1)$$
$$m = 2^4 3^2 = 144$$

But this is incorrect for $n = 16$:

$$16 = 2 \cdot 2\cdot 2 \cdot 2$$
$$16 = (1 + 1)(1 + 1)(1 + 1)(1 + 1)$$
$$m = 2^1 3^1 5^1 7^1 = 210$$

Whereas the correct answer is:

$$16 = (3 + 1)(1 + 1)(1 + 1)$$
$$m = 2^3 3^1 5^1 = 120$$

So it's clear sometimes we need to merge factors. In this case because $7^1 > 2^2$. But I don't exactly see a clean and direct merging strategy. For example, one might think we must always merge into the $2$ power, but this is not true:

$$1552 = (96 + 1)(1 + 1)(1 + 1)(1 + 1)(1 + 1)$$
$$m = 2^{96} 3^1 5^1 7^1 11^1 > 2^{96} 3^3 5^1 7^1$$

I can't immediately think of an example, but my instinct says that some greedy approaches can fail if they merge the wrong powers first.

Is there a simple optimal strategy for merging these powers to get the correct answer?

Addendum. A greedy algorithm that checks every possible merge and performs the best one on a merge-by-merge basis, fails on $n = 3072$. The series of one-by-one merges is:

$$2^2 3^1 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1 31^1$$

$$2^3 3^2 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1$$

$$2^5 3^3 5^1 7^1 11^1 13^1 17^1 19^1 23^1$$

However the optimal solution is:

$$2^7 3^3 5^2 7^1 11^1 13^1 17^1 19^1$$


texts: Interpretation of "expected cost" of an algorithm

texts:
I'm studying randomized algorithms and I sometimes come across results like

  (1) The algorithm has an expected $O(f(n))$ cost.

and

  (2) With constant probability, the cost is bounded by $O(f(n))$.

I'm perfectly fine with statements like (2), but I'm puzzled to what extent a statement like (1) is useful:
For certain probability distributions of a random variable, the expected value itself occurs with less than constant probability; for other distributions, it occurs with $1-1/n$ probability. Of course, in many cases, (1) is extended via concentration bounds to show high probability, but in cases where this isn't done, it doesn't seem that a statement on the "expected cost" lets us derive any implications on the actual performance of the algorithm, right?


texts: Proving that every graph has an order such that Bellman Ford can run in one iteration

texts:
I need to prove that for every given graph, that doesn't contain negative cycles, there is an order of edges so that Bellman-Ford algorithm will finish running after one iteration.
I could only solve it to graphs that are DAGs using topological sort, but couldn't find a way proving it for every graph.


texts: How to translate lambda calculus into (first-order, modal) logic, is it possible at all?

texts:
It is possible (using formal semantics) to translate natural language sentences into lambda expressions. So, is it possible to translate those lambda expressions into some logic, e.g. into first-order logic or into modal logic?

I am aware of the Curry-Howard correspondence, but I have not found actual translation, it is more conceptual one. I am aware of translation of lambda expressions into Answer Set Programming http://costantini.di.univaq.it/pubbls/aspopc10-Costantini.pdf and I have heard about translations into combinatory logic.

But are there translations into first order or modal logic?

Such translation would be big step into natural language processing.


texts:
I'm learning lambda calculus, however I'm quite confused about the quantifiers in lambda calculus. As far as I know, quantifiers such as "∃" are concepts of first order logic (FOL), which are not needed by lambda calculus. Moreover, I didn't find anything about quantifiers in any tutorials I have read.

However, I find this paper (Lambda Dependency-Based Compositional Semantics), in the first page of which the author used quantifier in lambda calculus.

So, are quantifiers used in lambda calculus? If so, what do they mean? Is it the same as in FOL?

Precisely, what does "∃" mean in the following lambda calculus?

λx.∃e.PlacesLived(x, e) ∧ Location(e, Seattle)


texts: Is it possible to define branches which, once taken once, will become the default forever?

texts:
Assuming I have a very simple branching:

switch on var:
  1 => branch1
  2 => branch2
  default => branch3

And I wish to implement a program that will forever take "branch2" when entering this sequence of instructions once branch2 is taken.

This is quite easy to do by adding an additional variable and setting it when branch2 is entered, however, this will keep the overhead of having to execute the control statement, I'm wondering if there is a way to remove that overhead or diminish it.

I'd be interested in knowing if:

a) This sort of optimization exists in theory ?

b) This sort of optimization is implemented languages which run in controlled environments (e.g. can use jitc) ?

c) This sort of optimization is implemented in statically compiled languages which don't need a VM/RE/etc ? (e.g. C, C++, Rust, D, Go) ?\

Edit:

Just to clarify, what I'm asking is if its possible that, once branch-x is taken once, for the instructions executed by the cpu to become:

//Code
//Instructions of branch x
//Code

rather than what we had before which was:

//Code
//Control Statement
//Code

That is in order to "skip" the overhead of having to select branch x to being with, not to optimize how that selection is done.


texts: Is it Possible to Get Maximum Weighted Input Value in a Neural Network?

texts:
Let's say that I have a standard feedforward neural network which has $M$ inputs, some number of hidden layers $N$, and a single neuron in the output.

Is it possible to construct a network such that the output neuron's output value is the maximum weighted input value?

I know that I could easily hard code something to make this happen, but I'd like to limit the construction to "standard" operations where the activation of a neuron is the dot product of the input vector and the weight vector with a bias added, then putting that value through a differentiable activation function.


texts:
I am looking for (practically) efficient algorithms to enumerate all minimum feedback arc sets of a directed graph.  What algorithms should I look at, with practical implementations in mind?

Currently I am using this algorithm to find all minimal solutions, then pick out the smallest ones:

B Schwikowski & E Speckenmeyer, On enumerating all minimal solutions
of feedback problems


texts: Is there an adjustment for Adler32 algorithm so it works well on short messages?

texts:
The Adler32 algorithm has a shortcoming as noted on Wikipedia:

  Jonathan Stone discovered in 2001 that Adler-32 has a weakness for very short messages. He wrote "Briefly, the problem is that, for very short packets, Adler-32 is guaranteed to give poor coverage of the available bits. Don't take my word for it, ask Mark Adler.  :-)"

If I am only computing a checksum on packets that are around 1,500 bytes long, is there an adjustment to Adler32 to make it work well in this case?  Alternatively, is there another algorithm that is as fast as Adler32 but does not have such weaknesses?  What about the Fletcher algorithm - does it suffer the same weakness?


texts:
So I understand that finding a solution to the 3-coloring problem takes exponential time.  However, say you had a friend who you could give a graph G to and he can say in constant time whether it is 3-colorable or not.  Is it possible to find a 3-coloring of G in polynomial time with his help? I think it might be possible but I'm not sure if my approach is correct.

Say the 3 colors are RGB.  You assign some vertex R and give G back to your friend.  If he says Yes, then keep it colored R, if No then leave it be.  Go through every vertex this way assigning R, and then with G and B afterwards.  The graph will be 3-colored at the end, but this would only take O(V*3) time.


texts:
Not talking about the actual moon lander, but an old game that was inspired by it (see screenshot).

Suppose I wanted to write a program that "plays" this game:

Can only operate the vertical thruster (on/off)
Does not know how much thrust is produced
Does not know about the vehicle's inertia, weight, etc.
Does know its current velocity / height from the ground
The program's only goal would be to aim for a descent of 10 pixels / second

What kind of algorithm would I use for this? E.g. the program would hit the thruster for 1s, evaluate its effect, if descent is too fast, try again for 2s, if it's too slow, wait for 1s, and so on.

I think that some sort of simple table-based Machine Learning algorithm would work. But it's been a few years since I took the computer learning class as a student.

What are your suggestions?


texts: CTL formula for "for every computation it is always possible to return to the initial state"

texts: In the book 'Principles of Model Checking' by Christel Baier and Joost-Pieter Katoen they state that the CTL formula for " for every computation it is always possible to return to the initial state" as  'AGEF start'. I was wondering whether the formula 'AGF start' would also be a valid one ? Is this correct ?


texts: Complexity class of maximum flow problem with random arc capacity

texts:
Given a graph $G=(N,E)$ with a special source node $s$ and sink node $t$. There is a subset of arcs $E^* \subset E$ that has the capacity drawn from a probability distribution $F$ independently. Then what is the expected maximum flow from $s$ to $t$? or the probability of the maximum flow exceeds some number $k$?

There are just a few articles in 1980s studied similar problem:

"Flow in networks with random capacities" by GR Grimmett, DJA Welsh
1982
"The maximal flow through a directed graph with random capacities" by
GR Grimmett, WCS Suen 1982

They only studied the case where G is a tree or complete graph and the answer is pessimistic. They suspected the problem in general is not in the polynomial time hierarchy but without a proof.

My questions are

What is the complexity class of this problem when both graph G
and the probability distribution $F$ are general?
What if $G$ and $E^*$ has some special structures, e.g. fixed tree width, bipartite (if $s$ and $t$ are removed) etc.?
What if $F$ is simple enough, e.g. Bernoulli?

Any ideas and relevant references are appreciated.

edit: I am actually interested in a very special kind of graph like this

so the center part of $G$ is bipartite $V \cup W$. All arcs from $s$ to $V$ have fixed capacity $c$, but all arcs from $W$ to $t$ have capacity random centered at $c$ (e.g. $Bernoulli$ between 0 and $2c$, or $Binomial (2c, 0.5)$ etc.). All arcs between $V$ and $W$ have infinite capacity.

I have some type of bipartite graphs that the expected maximum flow can be determined in polynomial time (in terms of number of node and the magnitute of $c$) for any discrete random capacities. Also there are some more complex bipartite graphs which I can only find polynomial time algorithm for Bernoulli capacity. I want to generalize this statement, either the problem is in NP or #P that a polynomial time algoirthm is unlikely, or it is actually can be determined in polynomial time.


texts: Solving unusual recurrence with two variables

texts:
I have the following recurrence relation:
$$T(n,k) = T(n-1,k)+T(n-1,k+1)$$
With the following base cases (for some given constant $C$):
For all $x \leq C$ and for any $k$: $T(x,k)=1$
For all $y \geq C$ and for any $n$: $T(n,y)=1$
I want to get a formula for $T(n,0)$. I think that it can be seen that after $i$ iterations we get the following relation:
$T(n,0) = \sum_{j=0}^i {n\choose{j}}\cdot T(n-i,j)$
But I don't know if it helps and can't proceed much further than that.
My question is $-$ what are the right techniques for dealing with recurrence with 2 variables, and in particular with this recurrence (where the second variable is increasing)?


texts:
Example

N = 9 and K=3

4 + 4 + 1 = 9 .

What I have tried.

We can not go on dividing with 2.

We can use unbounded knapsack with array elements from 2^0 to 2^32.


texts: How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

texts:
Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never encountered along that path, or every edge that is colored $c$ is visited by that path.
Given $G,s,e$, I would like to find a valid coloring that uses the minimal number of colors.  Is there an efficient algorithm for this problem?
I show below an example graph and a sample solution.  The circle on the left is the starting vertex, the filled circle on the right is the end vertex.


texts:
I'd like to know whether recent graph coloring algorithms that one can find nicely listed here have found it's place in real world applications or are they just simply pushing boundaries in this particular field of combinatoral optimization?
I already know that graph coloring naturally arises during register allocation as part of compiler optimization as well as in bandwidth allocation and scheduling problems. I also know that coloring techniques deployed in these areas are somewhat different than those provided in link. Algorithms one can find under link are mostly based on meta-heuristics and hybridizations and I believe are not helpful in register allocation, for certain.


texts: Least number of spheres enclosing other spheres but not intersecting others

texts:
Let's say I have a 3D space containing spheres (for simplicity, all with the same radius). All spheres are in two disjoint sets, $A$ and $B$. It is guaranteed that spheres from $A$ do not intersect with spheres from $B$.

How can I find the smallest possible set $C$ of spheres (of any radius) that covers all spheres from $A$ (i.e. $\cup A\subset\cup C$) but not even partially covering any spheres from $B$ (i.e.  $\cup C \cap \cup B = \emptyset$)?

If it is relevant whether the surface of a sphere is included in its points, I suppose the simplest case to implement (if required) is all open spheres (i.e. without their surface). That means it is safe if spheres from $C$ "touch" spheres from $B$ (but with zero intersection volume still).

The trivial answer is $C=A$, but I am looking for an answer that uses the least number of spheres (whose radii are not limited in any way). The spheres in $C$ may also intersect with each other freely. If possible, polynomial algorithm is preferred.


texts: Why do OS locks require hardware support?

texts:
I just read the chapter on locks in the book Operating Systems: Three Easy Pieces, and it discusses an implementation of locks (see in Figure 28.9) that involves a test-and-set hardware instruction.
The textbook emphasizes that both hardware support and OS support are necessary to build an efficient locking mechanism. Wikipedia echoes this sentiment:

Locks typically require hardware support for efficient implementation. This support usually takes the form of one or more atomic instructions such as "test-and-set", "fetch-and-add" or "compare-and-swap". These instructions allow a single process to test if the lock is free, and if free, acquire the lock in a single atomic operation.

I think I've come up with an alternative lock implementation that doesn't require hardware support. It seems to have relatively similar performance overhead, while guaranteeing mutual exclusion, so making this post to find out if I'm missing something.
Textbook Lock Implementation
I'll first summarize the textbook implementation. For setup, we need to:

Maintain a single flag (set to 0 or 1) and a queue (of thread IDs).
Maintain a separate flag for a "guard" lock, which will be a simple spin lock. Because the guard lock is meant to protect a relatively small critical section, the performance overhead of a spin lock won't be as pronounced.

When a thread wants to acquire a lock, it will do the following:

First, spin with the test-and-set instruction until you acquire the guard lock.
Once acquired, check if the flag (of the main lock) is set to 0. If it is, simply set it to 1, and the lock has been acquired! If the flag is set to 1, proceed to step 3.
Push the current thread ID onto the queue.
"Park" the current thread. This is an instruction in Solaris that basically puts a thread to sleep.

On the other hand, when a thread wants to release a lock, it will do the following:

Spin until you acquire the guard lock.
If the queue is empty, set the flag to 0, and you're done. If the queue is nonempty, proceed to step 3.
Pop a thread ID from the queue, and "unpark" the corresponding thread (wake it up).

My Implementation (without hardware support)
First, some setup:

Every lock must be initialized with some unique lock ID.
Inside the OS, maintain a "lock table." For each lock ID, the lock table will maintain a flag (0 or 1) and a queue (of thread IDs).

Then, when you want to acquire the lock:

Make a system call (which might be called something like lock) and pass in the lock ID as an argument.
Enter the OS. Since the OS manages scheduling, we guarantee mutual exclusion for the following steps.
Search the lock table for the specified lock ID. If the flag is 0, set it to 1. Then return; the lock has been acquired! If the flag is 1, proceed to step 4.
Push the calling thread to a queue.
Block the calling thread, so for now, it cannot be scheduled.

To release a lock:

Again, make a system call with the lock ID as an argument.
Entering the OS (again guaranteeing mutual exclusion), search the lock table for the specified lock ID. If the queue is empty, set the flag to 0, you're done. If not, proceed to step 3.
Pop a thread from the queue, and unblock it. It should be scheduled soon.

Note that when we are acquiring a lock, a context switch is not necessary if the lock is available, so the performance overhead should be minimal.
It's likely that I'm missing a small detail that will make me look stupid, but that's why I'm asking this question in the first place.


texts: Why are Oracle call instances bounded in the definition of FPT Turing reductions?

texts:
Let's take the following definition of a FPT Turing reduction from Flum & Grohe's book.

Let $F$ and $G$ be parameterised problems. For any instance $x$ of $F$, write $k(x)$ for the parameter of $F$ and $|x|$ for the size of $x$. For any instance $y$ of $G$, write $l(y)$ for the
parameter of $y$. An FPT Turing reduction from $F$ to $G$ is an algorithm with an oracle for $G$
that, for some computable functions $f, g : \mathbb{N} → \mathbb{N}$ and for some constant $c \in \mathbb{N}$, solves any
instance $x$ of $F$ in time at most $f (k(x)) · |x|^c$ in such a way that for all oracle queries the
instances $y$ of $G$ satisfy $l(y) ≤ g(k(x))$.

If we go through the definition in high-level terms I understand:

We have an algorithm for $F$ that is allowed to call an oracle for the problem $G$ (this is done in constant time).
The Algorithm must run in a time that is a computable function of the size of the parameter of our instance of $F$ multiplied by a polynomial function of the size of the instance of $F$.

I understand things thus far. However the final restriction that instances of the problem $y$ for which we make an oracle query must satisfy $l(y) ≤ g(k(x))$ for a computable function $g$ I do not understand. What does this say in high-level terms and why is it important? Thanks.


texts: Like transitive reduction, but removing vertices rather than edges?

texts:
Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in E$ — that is to say, the relation restricted to $x, y, z$ is transitive, there is a triangle. Let us call this situation a "local transitivity". My goal is to obtain all the subgraphs of $G$ induced by cutting middle vertices from local transitivities until none remain, which I dub "resolution".

There may be multiple solutions. For instance, consider a graph given by this relation:

  a b c d
a □ ■ ■ □
b □ □ ■ ■
c □ □ □ ■
d □ □ □ □

(It looks like a square with one diagonal.)

There are two ways it can be resolved:

  a b d        a c d
a □ ■ □      a □ ■ □
b □ □ ■      c □ □ ■
d □ □ □      d □ □ □

One way I can compute the resolutions of a graph is by giving a "non-deterministic" function $f :G \rightarrow \{G\}$ that removes any single local transitivity. Repeatedly applying $f$ to any graph, I will eventually converge to a set of induced subgraphs completely devoid of local transitivities.

One way to define $f$ is by considering all the triples of distinct vertices and checking them for local transitivity. From each matching triple, the middle vertex is extracted, and any of these vertices is cut. But there is about $|V|^3$ such triples.

Is there a better way? Is there prior art that I may study?

P.S. Answering to questions from the comments:

  Is "local transitivity" the same as a triangle? Or could it (for instance) involve more than 3 vertices?

In the case I have in mind, it is specifically triangles that I need to remove. But I can see how a generalization may be offered where, given two paths $p_1, p_2: a \dots b$ such that $|p_1| \leq n$ and $|p_2| \leq m$ (counting edges), we can remove the longer. My specific problem is then the special case with $n = 1, m = 2$.

  In your example, I think there are more than two ways it can be resolved. For example, you could remove vertex a (from the abc triangle) ...

I was thinking that it is only allowed to remove a midpoint from a triangle, so that "initial" and "terminal" vertices cannot be removed, and therefore the length of the shortest path is preserved.

  What's your question? Is your question "can I enumerate all triangles faster than $O(|V|^3)$ time?" Is your question "how efficiently can I find all possible triangle-free subgraphs?"

This and that too. Primarily, I need the triangle-free induced subgraphs. Enumerating triangles is only a means to this end, but it may be a useful technique for other algorithms, elsewhere, so would be good to know.


texts: Denotational semantics of object-oriented languages

texts:
I am interested in denotational semantics of object oriented languages. Namely, what are the common/typical denotations of objects used in the literature? Is this an interesting topic these days?

The most comprehensive article I've found dates back to 1993. That made me think that I might be missing something. Am I?


texts:
Given a network flow and there exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow.

I've had this questions with true or false and I thought it was false but apparently it is true.
Can someone please explain me how this is possible?


texts: How to choose value of additive smoothing in naive Bayes and why a higher value gives bad accuracy?

texts:
In Naive Bayes we often do additive smoothing as a fail safe. Consider the following expression:
Lets say
$$P(X_i) = \frac{count(X_i) + \alpha}{\sum_i^n count(X_i) + \alpha*total\_size}$$

How to tune the parameter $\alpha$ here. I observed that my classifier accuracy increased for value from $1$ to $N$ (where N is an Integer) and then started to decrease for higher values of $\alpha$. So why does this happen and how to choose this parameter.


texts: Proving that the set of grammars generating L or L complement is undecidable

texts:
Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that both sets are decidable and concluding that UNIVERSALITY is decidable.

UNIVERSALITY problem is $ \{ G \in CFG \mid L(G) = \Sigma^* \} $,
which is known to be undecidable.

I think that the goal is to arrive to the conclusion that UNIVERSALITY is decidable, maybe with a reduction, which means that there is a contradiction in terms of decidabilty of UNIVERSALITY.


texts: Minimum cost edge disjoint paths - NP hard?

texts:
I've been stuck on this problem for a while now. Here it is:

The Network Reliability Problem (NRP) is defined as follows: Given an undirected graph with $n$ vertices
$v_{1}, \dots, v_{n}$, a positive integer weight on each edge,  and a $n \times n$ symmetric matrix $R_{ij}$.  The objective is to find a subset $S$ of the edges such that the total cost of the edges in $S$ is minimized and for every pair of vertices
$v_i$ and $v_j$ there exist at least  $R_{ij}$  disjoint paths from $v_{i}$ to $v_{j}$ such that all paths use only edges in $S$.

I tried showing a reduction from Undirected Hamiltonian Cycle as follows, but I'm not quite sure where to go from there. Any help is appreciated!

The decision version of this problem is as follows: Is there a subset $S$ of edges such that the total cost is at most $k$ and for every pair of vertices $v_i$ and $v_j$ there exist at least  $R_{ij}$  disjoint paths from $v_{i}$ to $v_{j}$ such that all paths use only edges in $S$?

We will show that NRDP is NP-hard by reduction from UHC.  The reduction is as follows: Given an instance of UHC $G = (V,E)$, create an instance of NRDP by having $ n = |V|$ vertices and let $e = 1, e \in E$, else $e = 2$. Then, create an $n \times n$ matrix with the the vertices listed on the axes, and the cells filled in with the edge weight between the corresponding endpoints.


texts: Broadcast Problem Algorithm In Parallel Computing In Mesh, Complete Tree and Hypercube Structures

texts: Can anyone please help me design an algorithm to solve the broadcast problem in parallel for the structures mentioned?


texts: Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution

texts:
Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally $\mid w_i\mid=n$ for all $i$, then set $w'\approx w$ if also $\mid w'_i\mid=n$ for all $i$ and there are permutations $\pi_1,\pi_2$ such that $w_i[j]=w'_{\pi_1(i)}[\pi_2(j)]$. $L$ is closed under $\sim$ and $\approx$.

For example, if $100\#0000\#$ is in $L$, so is $0000\#100\#$. If $100\#110\#$ is in $L$, so are $110\#100\#$, $010\#011\#$, $011\#010\#$, etc.

Additionally, set $w'\bowtie w$ if $w'\sim w$ and $\mid w_i\mid_1=\mid w'_{\pi_1(i)}\mid_1$ for all $i$ ($\mid \cdot\mid_1$ means ``number of 1's"). $L$ is not closed under $\bowtie$.

My question is: Are there context-free languages $L$ with these properties such that $L$ can not be written as a substitution $s(L_1)$ where $s(a)=L_a\#$ for some $L_1$ and $L_a$? Is it true that such an $L$ is context-free if and only if it is a substitution? I think this in fact equivalent to the conjecture that if $L$ is closed under $\sim$ and $\approx$ and context-free, then it is in fact closed under $\bowtie$. (The intuition being: how else could the permutation invariance be enforced context-freely unless a side effect of $\bowtie$-closure?).

I have been trying to think about this in terms of matching relations ([1]). The idea is that a language is context-free if and only if for every string there is a matching (non-crossing pairing relation) and a first-order sentence that they together satisfy (so this sentence basically says that the arcs of the matching correspond to productions).

If $L$ can be written as a substitution, every string will have matching where $\#$'s are paired and the symbols of every $w_i$ are paired up with symbols in the same $w_i$. I'm trying to show that if there are arcs that cross over a $\#$, (which means there are productions that generate symbols in distinct subwords), then there is a contradiction with the invariance properties.

[1] Lautemann, Clemens, Thomas Schwentick, and Denis Thérien. "Logics for context-free languages." Computer science logic. Springer Berlin Heidelberg, 1995.


texts: I'm working on some compiler software, and I'm looking for information on canonical forms for expressing software, algorithms, mathematical expressions (including predicate logic), etc. I assume canonicalization is generally intractable, but NP algorithms and more-constrained problems (e.g. pure functions) are also interesting. Normal forms may be useful too. My goal is not to be able to represent and manipulate all programs, but some of them (the trivial ones).


texts: What is the complexity of this bubble sort algorithm?

texts:
I have been doing a little reading up on bubble sort and have read on wikipedia that it's complexity is measured as $\Theta(n^2)$

This bubble sort however is slightly more efficient. I thought this would be the best place to ask how I would work out this particular implementations complexity seeing that the number of iterations in the inner loop is reduced with each pass.

for (top = items.Length; top > 0; top--)
            {
                for (low = 0, high = 1; high < top; low++, high++)
                {
                    if (items[low].CompareTo(items[high]) > 0)
                    {
                        tmp = items[high];
                        items[high] = items[low];
                        items[low] = tmp;
                    }
                }
            }


texts: Greedy approach suggestions for assigning objects

texts:
Suppose there are three categories of people.
Type X, Type Y, Type Z.
In each type, there are two objects of subtype Type 'a' and type 'b'.
For example.
X: a1 , a2 , b1 , b2
Y: a3 , a4 , b3 , b4
Z: a5 , a6 , b5 , b6
Each object of type 'a' should be assigned with an object of type 'b'. But it is desirable not necessary to assign a type 'a' with type 'b' from different classes (X, Y, Z).
In this example, the optimal solution would be:
a1 with b5 ,
a2 with b6 ,
a3 with b1 ,
a4 with b2 ,
a5 with b3 ,
a6 with b4 .
Non -optimal solution would be :
a1 with b5 ,
a2 with b6 ,
a5 with b1 ,
a6 with b2 ,
a3 with b3 ,
a4 with b4 .
(Non -optimal because a3 and a4 are assigned with b's of same type Y)
If we generalize, there can be n- number of Types (X,Y,Z, .....and so on) with different number of a's and b's in each (but total number of a's = total number of  b's).
How to find an optimal solution?


texts: Designing a PDA that keeps track of the stack size

texts:
Would it be possible/legal to design a PDA that can use the stack as a way to keep track of the number of inputs seen? (i.e the size of the stack would act as some sort of counter).

What I was thinking:

First transition would require you to push a "1" to the stack
All future transitions would require you to pop the top of the stack (let's call this $x$) and push $x+1$ onto it.

The language of the stack would be the set of all natural numbers excluding 0.

I'm having trouble understanding whether the "push $x+1$" move would work


texts: Constrained selection of a random sample from a set of items with multiple attributes

texts:
Suppose I have a collection of N items, each of which has A different attributes, a1, a2, ..., aA.  Attribute ai can take on Vi different possible (discrete) values, distributed across the population with some kind of complicated joint probability φ(a1, a2, ..., aA).  It is quite likely that many possible combinations of attributes are either extremely rare in or entirely absent in my collection.

Now suppose I want to draw a sample of S items from my collection, and I want my final sample to satisfy a set of aggregate constraints, each having the form lij ≤ Sij ≤ uij, where Sij is the number of items in the sample for which attribute ai takes on its jth value.

What I'd like to find is an efficient way to do the following things:

Determine for certain whether or not there exists a possible sample from my collection that satisfies the constraints.
Get at least a rough idea of what fraction of possible samples from the collection will satisfy the constraints.
Efficiently select such a sample at random.  In particular, if only a very small fraction of possible samples will satisfy the constraints, I'd like a good way to do some kind of pre-filtration on the space I sample from, to reduce the number of random samples I have to draw before I get one that satisfies my constraints. Since the space of possible samples is quite large, exhaustively enumerating possibilities and filtering for satisfactory ones is not a reasonable option.

I don't have a lot of domain knowledge in this area, so even suggestions of better terminology for expressing this issue would be helpful.


texts:
I am wondering what is the difference between Bottleneck Travelling Salesman Problem and normal Travelling Salesman Problem?

Thank you


texts: O(1) distinct elements in an array implies?

texts:
Could someone explain the following question -

Given the following statement viz. Consider an input array a[1..n] of arbitrary numbers. It is given that
the array has only O(1) distinct elements. What does the statement imply ?

Thanks.


texts: Turing Recursive Definition vs General Perception

texts:
So what confuses me is that let's consider a function f. According to a definition from a text book it asserts that f is called recursive, if there is a Turing machine that computes it (for all input strings output of the machine should be equal to output of the function given the same input).

But in general, we say that a function is recursive if it calls itself or maybe firstly another function and then that other function calls our initial function again and again until some initial condition.

So these two definitions are seems to be different. Should I choose the meaning of recursion based on context or am I missing something ? Thanks in advance


texts: Adder circuit with sign bit (not twos complement)

texts:
I've found and implemented a full adder to be able to do unsigned or two's complement addition on wikipedia:
https://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder

However, in my particular case, I'd like to use a sign bit instead of twos complement, due to there being a variable (unbounded) number of bits involved.

How can i do addition and subtraction with binary numbers using a sign bit? (say, it's a separate bit, not one of the binary digits per se).

I also only have access to AND and XOR.

Edit: Potatoswatter suggested that twos complement is still able to be done with an unbounded number of bits.  What do you do when you want to add 6 bits and 8 bits together?  Also, is multiply, divide and modulo easily done in twos complement?  Keep in mind i have only AND and XOR, so don't have the ability to do if statements, the logic needs to be "branchless".

Thanks!!


texts: Matching schedules between users and providers

texts:
I have a problem I've been dealing for the past few days, and I'm pretty stuck.

Each user has a schedule for a given week, such as Mondays 9:00-12:00 and 14:00-18:00, Tuesdays... and so on. Each provider has another schedule for himself.

The problem is: Get the best k (different) solutions such that each solution assigns the minimum amount of providers to cover the entire schedule from the user? Where a solution is a set of pairs (Provider, schedule he will cover) and two solutions are considered equal if they contain the same providers (and different if they are not equal).

Also, take into account that any day could be split in sub-intervals and assigned to different providers. An example for a solution for the schedule shown before could be: {(Provider1, Monday 9:00-12:00), (Provider1, Monday 14:00-16:00), (Provider1, Monday 16:00-18:00)}

I've been looking into the Interval Partitioning Problem, Bipartite Matching Problem, and Assignment Problem, and none of them seem to adjust to my case.

Any ideas on how I could model this problem?


texts:
Suppose that there is an algorithm which sorts a sequence of $n$ elements

$$a_1, a_2, ..., a_n$$

Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers.

Is it true, given that $k \to \infty$, that:

The probability that any two of incoming sequence elements are equal, tends to $0$?
The probability that the incoming sequence is already sorted, tends to $\frac{1}{n!}$?

Why / why not?


texts: Solving consensus for a known number of processes

texts:
I was given an object with exactly 2 operations test-and-reset that sets the value of the object to 0 only if it was previously set to 1 and does not return a value and fetch-and-add(v) which adds v to the value of the object and returns the previous value.

I am almost sure the consensus number of this object is 2 and I think I found an algorithm for it (I should mention the problem is binary consensus):

if input = 0
    test-and-reset(obj)
    prev = fetch-and-add(obj, 3)
    if (prev != 2)
        decide(0)
    else
        decide(1)
else
    prev = fetch-and-add(obj, 1)
    if (prev = 0 or prev = 3)
        decide(0)
    else
        decide(1)

The problem was to find a wait-free algorithm an algorithm for n processes using any number of these objects (n is known).

The problem is that I an not sure if I am right (I'm pretty sure and this holds me back on this idea)? And if I am right no idea how to use this to solve the problem.

Thanks


texts: What is the significance of a Θ-bound on the running time of Mergesort?

texts:
While studying algorithm analysis I found that there is something called tight bound and there is some mathematical formula to support it.
Given:

  Mergesort takes $\Theta(n \log n)$ compares to sort $n$ elements.

What insight can we get from the above statement?


texts: The observation of the coreset in K-median clustering problems

texts:
I have seen two observations from the paper by Har-Peled but I do not know how to prove them
(i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is a $(k, ε)$-coreset for $P1 ∪ P2$.
(ii) If $C1$ is $(k, ε)$-coreset for $C2$, and $C2$ is a$(k, δ)$-coreset for $C3$, then $C1$ is a $(k, ε+δ)$- coreset for $C3$
Can anyone please figure it out?


texts: Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?

texts:
The wikipedia page Powerset construction says that the DFA equivalent to this $(n + 1)$-state NFA (with $n=4$ here) "requires $2^n$ states, one for each $n$-character suffix of the input".

I understand that the author wants to say that the smallest DFA equivalent to this NFA needs at least $2^n$ states.

But I can find a very much smaller DFA equivalent to this NFA just below:

Is Wikipedia wrong? Or am I? (which is much more likely)


texts: Are all computational complexity results oracle results?

texts:
When talking about the complexity of a given operation, say multiplication of numbers, one usually counts the number of "elementary operations" that are required.

For example, a common argument says that multiplying two $n$-digit numbers with the schoolbook standard method takes $O(n^2)$ operations, while more sophisticated techniques give complexities closer to $O(n)$.

In these examples, what is counted is the number of single-digit operations, but then the complexity of those operations themselves is not taken into account.
Isn't this then essentially an oracular result, in the sense that it tells us the number of operations we have to perform, provided we have a magical box solving single-digit operations?


texts: Multithreaded access to a persistent linked list data structure

texts:
I previously asked a question about persistent data structures here. After that I came across an article that introduced persistent data structures. I have got a question on the following figure from the same article, where it describes how to implement a persistent linked list:

The author says:

  Inserting a new item into a persistent singly linked list will not
  alter the existing list but create a new version with the item
  inserted into it. Instead of copying the entire list and then
  inserting the item into the copy, a better strategy is to reuse as
  much of the old list as possible.

Since the two versions (Red and Yellow + Red) have common nodes (specifically, the last three Red nodes), how can one access these two versions simultaneously, for example in a multithreaded application?


texts: What is the successor of 6 in this tree: 7 or 9?


texts: In cycle stealing mode, Does CPU gets blocked for 1 cycle or blocked till DMA transfer completion?

texts:
In cycle stealing mode, is CPU idle during data transfer between peripheral devices or idle only for 1 cycle ( during shifting of bus controls ) ?
Because I'm unable to understand these lines.

  The DMA module is transferring characters at the rate of 1200 characters per second. or one every 833 microsecond. The DMA therefore steals every 833rd cycle.

Now, I think these lines make sense only if we assume CPU is blocked for 1 cycle not during 833microsecond(during DMA transfer).
Please anyone help me where I'm wrong or am I missing something.


texts: Proving NP completness without reductions

texts: What methods are there to prove a language is NP-complete? I already know the reduction method, but are there more sophisticated/advanced methods to prove this?


texts: Does FACTORING have optimal substructure or analog to it?

texts:
Is there any approach to FACTORING that can leverage optimal substructure allowing the problem to be decomposed into smaller subproblems? That is, perhaps being unnecessarily verbose, until an easily solvable instance is encountered, at which point the ancestry of subproblems can be successively reconstructed from the sequence of solved instances to arrive finally at the solution of the original problem.

In terms of original research toward this question I considered the following two possibilities. It is not thought that either of these are to be very workable, and are here to attempt to illustrate the intended meaning of the question, which then asks whether it is likely there are approaches that could be workable that display optimal substructure or analogous structure:

The hypothetical, magical FACTOR_SUCCESSOR function, which when given an integer factorization for X, returns the integer factorization for X+1 in polynomial time in log(X). [This can be used to construct a factoring algorithm to factor N using the binary (or any other) base representation of N.] This hypothetical function seems difficult to construct since, for example, see here.
An approximation approach. This would make use of the idea that if large (>500 decimal) N is hard to factor (say a semiprime), then perhaps if N-m is k-smooth, with factors in a multiset F, and then perhaps good approximations to base representation vectors of p and q could be obtained by forming p' and q' from disjoint covering subsets of F. The choice of k determines how expressive F is in being able construct varied factors of about equal size to p and q. It is unclear both if p' and q' would be good approximations to p and q even if they were of similar size and m were small, and even if they were good approximations, the algorithm appears more of a one-shot, and not amenable to iterative betterment of that guess. This is accounting for the idea of 'randomly modifying' parts of the guess p' and q' to then give an m' < m, with the same k-smooth property, and beginning the search for selections of disjoint covering subsets of F nearby to p' and q'. It is unclear whether m' could be easily found, also if the algorithm would get stuck in a local optima, removed from p and q. Which makes it seem quite unworkable.

Edit: it is incorrect to say optimal substructure is a meaningless term since it has both a generally accepted meaning (in computer science referring to problems by which larger instances are amenable to solution using the solution of smaller instances) and also a derivable meaning in that if one considers the possible meanings of "optimal" and "substructure" put together one arrives at a conclusion that such a concatenation is likely to refer to the state of having a substructure which is in some way optimal. In the context of the solution of problems, the intended meaning naturally follows. Maybe Raphael simply doesn't like the question or the answer or both, because they're so meaningful!


texts: Recursive DP vs Graph Traversal solutions to path-based problems

texts:
I am studying some algorithms interview questions and I am seeing many path-based questions like "if a robot is at the top left of a grid and can only move down or to the right, how many paths can take it to the bottom left of the grid".  Or similarly sometimes they ask if the particular destination can be reached at all with some obstacles.

I've seen it solved with recursive DP solutions where you essentially start at the beginning state and recursively call the same function on all states reachable from the current state and the base case is when you reach the target state.  Also sometimes memoization is used to optimize it.

However I think these types of problems can also be seen as graph traversal problems.  The beginning state would be a node and each node has children which are the states that can be reached from the current node creating a directed graph. So finding a path to the target state can be done via a graph traversal algorithm.

So I guess my question is which is what are the tradeoffs for each approach? Or are they in some cases equivalent?


texts:
I'm analyzing a piece of code that has a recursive call inside a for loop such as:

def fun(n):
    for i in range(0, 256):
         if ( n > 0):
             fun(n-8)

(I only included a general piece of code not the actual version)

It is my understanding that a recursive call gets assigned T(n) = T(n-8) but what happens when it is nested inside a for loop?


texts: Complete Partial Order of Partial Functions with Different Outputs

texts: Since a partial function can be seen as a set of tuples, there is a trivial CPO defined by the subset relation on partial functions of the same (co-)domain. However, this is not really useful. What I'd need is a CPO over partial functions allowing for different outputs. I.e. two functions are ordered $f < g$ when, for all $f(x)\prec g(x)$ for some CPO $\prec$ on the codomain. It seems intuitive that this is also a CPO, but is it really? Is there a theorem out there somewhere proving it (given some properties of $\prec$)?


texts: Can a non-RE language be reduced to an RE language?

texts:
Let $L$ be recursively enumerable and $U$ be non-recursively-enumerable. Is it possible to reduce $U$ to $L$ recursively, $U\leq_R L$? Personally, I do not think this is possible. If we can reduce $U$ to $L$ by a Turing machine that always halt and we also have an Turing machine that compute $L$ (may not halt), then we connect these two parts, we will have a Turing machine to compute $U$. Then $U$ is also recursively enumerable.

I was asked to show some language $L$ is recursively enumerable first, which was OK. But afterwards, I was asked to show some language which is known not recursively-enumerable, $L_{diag}=\{w_i|M_i\text{ does not accept } w_i\}$ can be reduced to it. I.e. $L_{diag}\leq_R L$ which does not make sense to me.


texts: Is there a generic way to parallelize algorithms?

texts:
Take:

An algorithm $A$ that is analytically nice in some way, say, for some class of inputs of length $n$ it runs at $O(f(n))$ on some Turing machine.
$k+2$ independent, identical such machines.

Is there a generic method to produce algorithms $A_{in}, A_{out}, A_{1},\dots, A_k$ for which tapes can be made so that:

$A_{in}$ finishes after $O(k)$ and transforms a length-$n$ input for $A$ into $k$ inputs, each to one of $A_\ell$, $\ell \in \{1,\dots, k\}.$
Each $A_\ell$ runs in $O(f(n)/k)$
$A_{out}$ runs in $O(k)$ and combines the the outputs of the $A_\ell$ into what $A$ would have produced on the input of $A_{in}$