texts: Are the functions always asymptotically comparable?

texts:
When we compare the complexity of two algorithms, it is usually the case that either $f(n) = O(g(n))$ or $g(n) = O(f(n))$ (possibly both), where $f$ and $g$ are the running times (for example) of the two algorithms.

Is this always the case? That is, does at least one of the relationships $f(n) = O(g(n))$ and $g(n) = O(f(n))$ always hold, that is for general functions $f$,$g$? If not, which assumptions do we have to make, and (why) is it ok when we talk about algorithm running times?


texts:
Given this formula how do you calculate the following? I don't understand, can some one explain?

                      1
MTTF(System) = ------------------------
           [Summation]      1
                       ------------
                          MTTFi

(was going to upload an image of the formula but "they" don't let me)

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


texts: Application of lambda function in Simply Typed Lambda Calculus

texts:
I'm just getting started with STLC (Simply Typed Lambda Calculus) and I'm trying to understand an evaluation rule I've been given in some lecture notes by my professor. What it says is the following:

(λx. x(λx. x)) (u r) evaluates to (u r) (λx. x)

I don't really get this at all. Can someone point out which step I'm misunderstanding in my evaluation;

(λx. x(λx. x)) (u r) // Start state, not evaluated

(λx. λz. z) (u r) // Replacing occurences of x in first lambda function with the
                  // second lambda function, and then renaming the input variable x
                  // in the second lambda function (this is allowed, right?)

r                 // x gets replaced by u (no occurences) and z gets replaced by r
                  // - resulting in the final result r.


texts: Solve the recurrence $f(n+1)=f(n)^2,\, f(0)=2$

texts:
I have a problem with an exercise asking me to solve the following recurrence:
$$f(n+1)=f(n)^2, \quad f(0)=2$$
Can someone explain how to solve this? I tried but couldn't.


texts: Why is T not a minimum spanning tree of G?

texts:
The Problem: Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G.
        a. True of false: T is a spanning tree of G?
         b. True of false: T is a minimum spanning tree of G?

I read from Single source shortest paths problem  is a problem  "in which we have to find shortest paths from a source vertex v to all other vertices in the graph."  I read from Partial Solutions that only one of the options is true.

From my intution and the statements above, I reasoned that a is true while b is false. This is because if T is a minimum spanning tree of G, be definition it should also be a spanning tree of G. I am trying to show that b is false with a counterexample but I can't find/draw a graph in which T isn't a min spanning tree.

Can anyone show me a counterexample to b? To me, Dijkstra's algorithm is similar to Prim's algorithm to find MSt, so in the end T should be a min spanning tree.


texts:
Let's define the sequence of $k$-Fibonacci numbers as
$$ F_i = 2^i, ~~ 0 \leq i \leq k-1 $$
$$ F_i = F_{i-1} + \dots + F_{i-k}, ~~ i \geq k $$

I have a problem which requires to compute $n$-th $k$-Fibonacci number modulo $10^9 + 7$ efficiently. $n$ can be as large as $10^6$, $k$ can have any value between $1$ and $n$, time limit is $1$ second.

When $k$ is small enough i can use matrix-power approach for computing $n$-th members of linear recurrent sequences. This requires $O(k^3 \log(n)$ operations which is not feasible when $k > 250$ since takes more than one second.

When $k$ is large but $n$ is small i can compute this exactly by definition with $O(nk)$ operations. This approach is also not feasible when $k,n \approx 10^5$ or larger.

So how can i compute them faster? I neither derived nor found on the web any useful formulas which allow to represent this recurrence with smaller depth. Thus i believe that it's more an algorithmic than combinatorial question.


texts: How to decide which bytes will form a packet ?(computer networks)

texts:
In wireless communication , I understand what it means to transmit a "bit" but I wanted to understand what exactly does it mean by a packet .

*******POST EDIT/RECEIVING INITIAL ANSWERS*******
I got the following question , which is also there in my comment ,

How to decide which bytes should form one packet of data ?
What distinguishes one packet from another ?

for the following query

*****EDIT CLOSES HERE ****

There will be a signal of certain frequency, $ \omega $ which is transmitted .If the amplitude crosses a threshold then it means then we say that a "bit" about the information which is interpreted or encoded by a signal of frequency $ \omega $ is detected or received .
(Please correct me If I am wrong)

Similarly , I would like to understand what exactly a "packet of data" in networking means electronically(logically or physically maybe) . What is the definition of a packet ?

Still if the previous version of this question is required then its in the following link :

https://hastebin.com/tejapuvace.coffeescript

Looking forward to replies , thanks a lot .


texts:
The following is the Problem 1.4 in [1]:

Finding an Eulerian path. Show that if a connected graph has two vertices of odd degree and we start at one of them, Fleury's algorithm will produce an Eulerian path, and that if all vertices have even degree, it (Fleury's algorithm) will produce an Eulerian cycle no matter where we start.

Reference

[1] C. Moore and S. Mertens, The Nature of Computation, Oxford University Press, 2015.

I have tried to answer this question for a long time, but I don't have any idea. By the way, this question is not my homework, I am just interested in solving this question.


texts: Algorithm to compute $n^{\log k}$ in $O(\log\log k)$

texts: I was given this exercise and I think I have to use a variation of Gauss repeated squaring, but I can not figure out how to produce $\log\log k$ in steps, like when you divide $k$ by $2$ to compute $\log k$ in steps. Any ideas?


texts: Behaviour of Regular Registers for Multiple Writer Case ( in context of Safe, Regular and Atomic Registers)

texts:
From the link below I understand the behaviour of different kinds of registers.
However that raises few more queries in my mind.

https://stackoverflow.com/questions/8871633/whats-the-difference-between-safe-regular-and-atomic-registers

What is behaviour of Regular registers when there are overlapping writes? Why do we study only MRSW regular registers? Do they behave like safe registers when there are overlapping writes? I mean, that the value read will be some legal value but may not be the one of the actually written ones.
For clarity need some sort of proof/illustration for the above. Since regular registers are said to be quiescently consistent even on overlapping writes we should have some value which was actually written by one of those writes.
In case of safe registers, if a read and write overlap the value read is any legal value that register could accommodate. So, is it also okay to conclude that we will see the same behaviour if there are multiple writes together?

I will also be thankful if you could point me to the tutorial with these questions covered.


texts: An intuitive explanation for LR grammars?

texts: With LL grammars, there seems to be a very intuitive explanation, in terms of first and follow tables.( The first letter/s encountered in a particular state, can only mean a particular rule). With LR grammars however such an explanation seems to be difficult. Of course you could go through the entire construction of the DFA and so on. But is there a general principle or a few of them, that can give an intuitive understanding of LR grammars as a whole?? What is the intuition behind the item sets??


texts: Comparing the efficiency of algorithms with finite input sizes

texts:
I'm a non-CS grad student working on an algorithm which would be an alternative to conventional GPS position estimation algorithms. My advisor insists that I must compare the run-time of these algorithms. I understand that simply timing the two algorithms is not a good measure for comparison for several reasons but I'm having trouble finding a good way to compare them.

I am familiar with big-O notation, but my understanding is that it is a good measure for understanding how an algorithm scales as the size of the input approaches infinity. For GPS problems, the size of the input depends  on the number of available satellites which is obviously finite (probably never larger than 25 or so).

For such a scenario what would be the best way to compare efficiency?


texts:
I am an electrical engineer and trying to make a transition into machine learning.  I read in multiple articles that I have to learn data structures and algorithms, before this I have to learn about mathematical proofs.  I started studying it on my own using the material available on MIT's OCW, while I did grasp the concepts of induction and well ordering etc..
I've been struggling with the exercises for a very long time and it's really frustrating.  I can easily deal with any type of proofs that I saw before (e.g. once I saw the proof of a recurrence question I became pretty good at proving them).  My problems start when I face an unusual question.  I feel like I am memorizing the proofs rather than learn how to prove.
Is there any way (or any resources) that can improve my proving skills in a way that whenever I see an unusual question (like the checkers tiles and chess tiles type of questions) I don't have to stare at them for 2 hours before giving up?


texts: DML , ML with restricted dependent types

texts:
Refering to this paper
 Dependent ML: An Approach to Practical
Programming with Dependent Types

Have defined datatype 'alist ( int ) Its not clear why they have used int as a parameter rather than a nat directly.

datatype ’a list (int) =
    nil(0) | {n:nat} cons(n+1) of ’a * ’a list(n)
fun(’a)
    append (nil, ys) = ys
  | append (cons (x, xs), ys) = cons (x, append (xs, ys))
withtype {m:nat,n:nat} ’a list(m) * ’a list(n) -> ’a list(m+n)

In there base paper Dependent Types in Practical Programming they have defines it like ’a list of nat which makes more sense :

datatype ’a list = nil | cons of ’a * ’a list
typeref ’a list of nat with (* indexing the datatype ’a list with nat *)
    nil <| ’a list(0)
  | cons <| {n:nat} ’a * ’a list(n) -> ’a list(n+1)

fun(’a)
    append(nil, ys) = ys
  | append(cons(x, xs), ys) = cons(x, append(xs, ys))
where append <| {m:nat}{n:nat} ’a list(m) * ’a list(n) -> ’a list(m+n)

The first declaration  looks elegant and In second its not clear  why to use <| inside where clause ? Can anyone help me with this.


texts: how to find all negative weight cycles(elementary circuit) in a strongly connected directed graph?

texts:
I can use Bellman-Ford to get some of the elementary negative weight cycles in a graph. It's not guaranteed to always get all of them.
(Elementary Cycle: A cycle is elementary if no vertex but the first and last appears twice.)
But I want to find ALL elementary negative weight cycles. Even taking each vertex as the source will not always get ALL negative weight cycles.
Take this graph for example:

With Bellman-Ford, starting from any vertex, I can only get one cycle "U→H→U".
The cycle "U→S→U" is always missing.
Is there any algorithm with which I can find all negative weight cycles reliably?


texts: How to write program to list all the function values without repeating?

texts:
Suppose I have a (recursive) function $f:\Bbb N\rightarrow\Bbb N$ whose range is infinite, and I want to list all the function values without repeating.

That is, if $f(0)=1,f(1)=1,f(2)=5,f(3)=6,f(4)=6,f(5)=2$, I need a program with outputs $1,5,6,2$ I need it to firstly list $1$, then $5$, then $6$ and then $2$.

My idea is: Start from $0$, firstly output $f(0)$, and then increase $0$ by $1$ to get $1$, look at what is $f(1)$, if it is equal to $f(0)$, then we do not output it, otherwise we output $f(1)$. And then look at $f(2)$, if it is equal to at least one of $f(0),f(1)$, then we do not write it out, otherwise we output $f(2)$. But so far I found my knowledge too poor to write a program in psudocode...

My attempt:

x := 0;

while (n < x)

{ if (f(n)=f(x));

 n := n+1;

else

return f(x)}

I think maybe this code is problematic. Could someone please tell me some way to write it? This is such a minor part of my math course that we are not taught how to write psudocodes and now I feel a bit frustrated...

Other simple ways to do it would also be appreciate. Thanks in advance to you all who may help!

To sum up, I wish to see a psudocode to out put all the values of the function:

$f':\text{n↦the nth value in the enumeration that isn't a repeat of a previous value}$
 where $f$ is a recursive function. Apologize for my poor knowlege of computing. I have no backgroud of computing and even not know what is "memory", only psudocode is readable for me... And actually I just need the psudocode program to prove that this function is recursive.

Thank a lot to you all who leave answers and comments!


texts:
What is the space complexity of quicksort?
I was doing some research and found some saying it is $O(1)$, some saying it's $O(\log n)$, and some saying $O(n)$. Not sure what to believe, even though $O(\log n)$ seems to make the most sense for me. Does it all depend on the pivot point that is chosen?


texts:
I was tasked to order some functions in respect to the $\mathcal{O}$ notation, and have some problems with the following ones:

$n^{\ln(7)} = \mathcal{O}(n^{3})$: I can't find a more elegant proof for this other than using L'Hôpital's rule and a numerical approximation of $\ln(7)$:

$\lim_{n\to\infty} \frac{n^{\ln(7)}}{n^3} = \lim_{n\to\infty} \frac{n^{ \approx1.94591014906}}{n^3} = \lim_{n\to\infty} \frac{n^{\approx1.94591014906-3}}{3*2*1} = 0 $

(The last equal sign is valid, since the exponent is negative.)
Is there a better way to do this ?

Furthermore I have no idea how to prove $8^{\log_2 n} = \mathcal{O}(5^n)$. I tried to apply the limit rule but to no avail. I think it is intuitively clear, since $\log_2 n$ grows slower than $n$, but I don't know how to argue that rigorously.

Thanks for any answers.


texts: Can this system of polynomial equations be solved in polynomial time?

texts:
I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we  find a solution to the system:

\begin{align}
ax^{1}+by^{1}+cz^{1}+\cdots&=k_{1}\\
ax^{2}+by^{2}+cz^{2}+\cdots&=k_{2}\\
ax^{3}+by^{3}+cz^{3}+\cdots&=k_{3}
\end{align}
so on ... till
$$ax^{n}+by^{n}+cz^{n}+\cdots=k_{n}$$

for variables $x,y,z\in \{1,2\ldots, n\}$.

The value of constants $a$,$b$,$c$... remain same in all these equations.

And these constants can also be equal to each other. For e.g: $a = b$ so that values of $x$ and $y$ can become interchangeable. In such cases one working solution is suffice.

Can we find a solution or determine none exist in polynomial time?

Edit: For the sake of clarity here is a simple example.

If $n=3$, I know $x,y,z$ can only take 1, 2 or 3 as their values. So if I have $x + y + z = 9$, I clearly know that $x, y$ and $z$ are all 3. But if I have $x + y + z = 6$, I don't know whether they are $2,2,2$ or $1,2,3$. Then I can make use of $x^2 + y^2 + z^2 = 14$. Then I will know they are $1,2,3$.


texts: Finite languages are Turing decidable - contradiction

texts:
Let's say that I define the language $L$ over the alphabet $\{0, 1\}$ to be a language containing only one word, $w$, where:

$$ w =
 \begin{cases}
      1 & \text{if the continuum hypothesis is true}\\
      0 & \text{otherwise.}
  \end{cases}
$$

$L$ is finite, therefore there is a Turing Machine which can decide whether or not the word $1$ is in $L$. On contrary, continuum hypothesis is independent of $ZFC$, which means that it cannot be proven nor disproved from the standard Zermelo–Fraenkel set theory. As a consequence, we cannot know if $1$ or $0$ is in $L$. Then, how can we build a Turing Machine which can decide $L$?


texts: Are there problems for which quantum computers don't even give a (nontrivial) polynomial speedup?

texts:
This question is in a sense the converse of Will quantum computers out-scale classical computers at P-problems?. We know that there are oracle problems (e.g. unstructured search) for which we can prove that quantum computers can only give a fixed polynomial speedup (in that case quadratic) for the number of oracle consultations. Are there any problems where we can prove that quantum computers can only give a constant speedup? Or even rule out a constant greater than 1?

(I'm excluding oracle problems where there's no quantum speedup for the trivial reason that the classical time complexity is already constant!)


texts: How can I prove the languages of incompressible words is undecidable?

texts:
I have hard time understanding the proof by contradiction for the claim "$L=\{x : K(x) \ge |x| \}$" is undecidable ".

The proof is as follows :

  M' = " On input $n$

  Enumerate over all $n$-bit strings $x$ in lexicographical order
  Simulate M on each $x$, where $M$ is the Turing machine that decides $L$.
  Output first $x$ which $M$ accepts.
  "

  Since TM $M'$ produced incompressible using only $O(\log n)$ to specify $n$, we
  can compress incompressible strings which is a contradiction.

I understood the $M'$ construction. However, I do not understand where exactly is the contradiction happening? According to me, $M'$ outputs $x$ which is in-compressible(ensured by TM $M$) but how does it is also compressible at same time?


texts: Why selection sort will require $O(N)$ time

texts:
As per the example given in this MIT OCW link URL  https://ocw.mit.edu/courses/civil-and-environmental-engineering/1-124j-foundations-of-software-engineering-fall-2000/lecture-notes/sorting/

Why selection sort requires $O(N)$ time since the number of exchanges is at most N. Pls give example algorithm that prove this fact. Below is excerpt taken from same MIT OCW URL for reference

Selection sort is easy to implement; there is little that can go wrong with it. However, the method requires $O(N^2)$ comparisons and so it should only be used on small files. There is an important exception to this rule. When sorting files with large records and small keys, the cost of exchanging records controls the running time. In such cases, selection sort requires $O(N)$ time since the number of exchanges is at most $N$.


texts: Is it possible to query a Knowledge Graph using only Matrix operations?

texts:
I am interested in formulating a knowledge graph query in a matrix multiplication/dot product/inner product.

I have found by chance the paper Variational Reasoning for Question Answering with Knowledge Graph which uses a inner product in the last operation (look the picture).

The problem is that the paper is not thoroughly explained the process of inference. It's written "we use beam search" but is not explained. Read:

  During inference, we are only given the question q, and ideally we want to find the answer by computing $\arg \max \log (P_{θ_1}(y|q)P_{θ_2} (a|y, q))$. However, this computation is quadratic in the number of entities and thus too expensive. Alternatively, we can approximate it via beam search.

I think that there is an implicit inner product structure inside the beam search algorithm but I haven't found any explanation through google.

Can someone explain better the above mentioned inner product?


texts:
Given a graph $G(V, E)$, consider the following algorithm:

Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$)
Let $v$ be one of the vertices with degree equal to $d$
Remove all vertices adjacent to $v$ and add them to the proposed vertex cover
Repeat from step 1. until in $G$ there are only vertices with degree $0$ (no edges in the graph)

At the end the removed vertices are a vertex cover of the given $G(V, E)$, but is it a minimum vertex cover? Is there an example where the algorithm does not find a minimum vertex cover?


texts: Prove or disprove $T(n) = T(\lfloor\frac{n}{2}\rfloor+1)+1=O(\log(n))$

texts:
Lets define function $T(n)$ as
\begin{align*}
T(1) &= T(2) = 1\\
T(n) &= T(\lfloor\frac{n}{2}\rfloor+1)+1 \text{, where }n\ge 3.\\
\end{align*}
Does $T(n)=O(\log(n))$? I have no idea how to prove or disprove this, so I'll be glad for any help.


texts: Efficiently check if any vertex has a path to its partner vertex

texts:
So I have a directed graph that looks something like:

I'm trying to make an algorithm that can go through all the vertices and tell me whether we have any path from an upper case letter to its lowercase version, or a path from a lowercase letter to its upper case version. In the above example, we have a path from C to c.  We also have a path from B to b, from a to A, from E to e, and from G to g.  I'd like the algorithm to find at least one of these paths.

The algorithm can stop looking if it just finds one such case where this happens. Each vertex points to at most one different vertex, so the out-degree of every vertex is either zero or one. I'm trying to get this done efficiently (linear time) and can put whatever extra information in the vertices to do it. I've been attempting to use the DFS algorithm to do it because you can work with ancestry but I'm not sure if it works for specific vertex relationships efficiently.

I'm aware that DFS can use discovery time and finish time to find if a vertex is the ancestor of another, and that this is used for cycle detection. I'm basically wondering if there is an efficient way to check if a specific node (that isn't necessarily part of a cycle) is the ancestor of another specific node. Unless, of course, this is unnecessary and there is a better way to go about it.


texts: Show that TQBF $\notin$ SPACE$((\log{n})^4)$?

texts: How do I show that TQBF $\notin$ SPACE$((\log{n})^4)$?  I know that TQBF is PSPACE complete, but is this the right approach?


texts: Proving a hash function family is weakly universal

texts:
$H$ is a family of weakly universal hash functions if for two elements $x,y$:
$$ P(h(x) = h(y)) \le \frac1m, $$
where $m$ is the size of the domain, and $h$ is chosen at random from $H$.

Given a hash family, how could one prove that it is weakly universal. I understand how to prove it isn't (proof by counter-example) but I cannot find any examples for when it is.
I apologise if this is a duplicate of another question. I was not able to find any examples online specifically for weakly universal hash functions.


texts:
I'm a bit confused on some of the notation being used for turing machines in one of our exercises in class.

The question gives us a string $\alpha \in \{0,1\}$* and the function $\mathsf{int}(\alpha)$ that changes a binary number to its base 10 form. (example, $\mathsf{int}(00010) = \mathsf{int}(10) = 2$)

Now comes the tricky part:
Define the language $L ⊆ \{0, 1, \#\}*$  by:

$L = \{\alpha\#\beta | α, \beta ∈ \{0, 1\}$* and $|\beta| ≥ \mathsf{int}(\alpha) ≥ 1 $ and $\beta \{ \mathsf{int}(\alpha) \} = 1 **\}$.

This bolded section is confusing me, and it seems like there are different variations of T.M. notation as well...

Could someone give me a rough approximation of what this might mean?

Extra:
Examples for language $L$:
 $\#111 \notin L$
$00010\#11100 \in L$
$00011\#010111 \notin L$
$00011\#11 \notin L$
$1\#\#1 \notin L$

Thanks in advance.


texts: Finding both the longest and shortest path in a convex polygon

texts: Let $S$ be a convex polygon on $n$ points. Given two points $A$ and $B$, where $A$ is left of $S$, and $B$ is right of $S$, what's an algorithm to find the shortest path from $A$ to $B$, that avoids the interior of $S$? What about the longest path?


texts: Deadlock and cycle in a resource allocation graph

texts:
Here is a resource allocation graph asked in my Operating Systems Theory midterm. The question is, "Is there a deadlock here? Explain your answer in detail"

Ra and Rb are resource sets and every dot inside of them are resources. Circles are processes. An arrow from process to a resource set means that process is requesting a resource from that set. An arrow from resource set to process means that process owns a resource from that resource set.

I want to have your opinions on this, because the lecturer's answer is conflicting with mine. Lecturer says there is a deadlock here. But my answer was, since Py and Pz are not requesting a resource, they will simply continue their execution and terminate, releasing their resources. Then Px and Pw can obtain their requested resources and keep executing. It is obvious there is a cycle in this graph as Px-Pw but this doesn't conclude us to a deadlock. Thus I can't see a way to make "there is a deadlock here"conclusion.

So is there a deadlock here?


texts: How does the CPU know to get data from or send data to a peripheral device?

texts:
We were talking today, in Intro to Programming, about machine language. I know it's a bunch of 0's and 1's. Let's say I compile the following C++ program on an x86 machine:

 #include <string>
 #include <iostream>
using namespace std;
int main()
{
cout << "Enter something";
string input;
cin >> input;
return 0;
}

Now, cin - as I understand - is an input stream. The computer gets input from the keyboard and places it in cin to be read by the program. My question is, how does the CPU know it's supposed to get input from the keyboard when, at the end of the day, the program is just 1's and 0's?

My understanding is that the machine code is kind of broken up.


texts: Markov algorithm: pick rule first, then position, or the other way around?

texts:
A Markov algorithm is a string rewriting system (well, not a set of rules but a list of rules since they need to be ordered) with a strategy for applying rules that ensures determinism.

I think the usual definition (1) is

  Find the first rule that matches, and then replace its leftmost occurence.

Another definition (2) could be

  Find the leftmost position where any rule matches, and then apply the first of the matching rules.

Does it matter? I think both should be equivalent w.r.t. the set of functions computed.

Which one is more economical for teaching?

E.g., for a simulation by a Turing machine, (2) seems better - less movements of the head, we can scan the tape once, by a finite automaton. But we need to "overscan" in case the left-hand sides of rules are not prefix-free. (Well this low-level programming is a mess any way you put it.)

Simulation of Turing machine by Markov algorithm is not a problem since we can build the rules in such a way that there is at most one match (when starting from an initial configuration), so the strategy does not matter.


texts: Known lower bounds on halting for finite machines?

texts:
It's possible to determine whether a deterministic machine with finite memory will halt in O(n) time if the machine has n possible states. You simply run the machine until it halts or visits the same state twice, which is guaranteed to happen in no more than n steps.

Can any other algorithm do this in fewer steps? Is there a proof that no such algorithm can exist?


texts: A dense NP complete language implies P=NP

texts:
We say that the language $J \subseteq \Sigma^{*}$ is dense if there exists a polynomial $p$ such that $$ |J^c \cap \Sigma^n| \leq p(n)$$ for all $n \in \mathbb{N}.$ In other words, for any given lenght $n$ there exist only polynomially many words of length $n$ that are not in $J.$

The problem I am currently studying asks to show the following

  If there exist a dense $NP$-complete language then $P = NP$

What the text suggest is to consider the polynomial reduction to $3$-$SAT$ and then construct an algorithm that tries to satisfy the given $CNF$ formula while also generating elements in $J^c.$

What I am wondering is

  Is there a more direct proof? Is this notion known in a more general setting?


texts: What is the Purpose of Augmented Grammar in LR parsers?

texts:
I was reading the LR() parsers from the Dragon Book where I came across these lines:

  To construct canonical LR(0) collection for a grammar, we define an
  augmented grammar and 2 functions, CLOSURE and GOTO.

for example say if we have a grammar like-->

S → BB
B → cB/d

Then in augmented grammar we define it as

S' → S

S → BB

B → cB/d

In the dragon book the reason for this is mentioned as,

  The purpose of this new starting state production is to indicate the
  parser when it should stop parsing and announce the acceptance of the
  input. That is acceptance occurs when only when the parser is about to
  reduce S' → S

I am unable to understand what this even means and how this augmented grammar is useful for parsing. Any help will be highly appreciated.


texts:
Given the theorem:
Let $\Sigma$ be an alphabet. The set $\mathcal{P} \left( \Sigma^{\star} \right) $ is uncountable.
In other words, there are uncountably infinite languages over any alphabet.
Can someone explain to me how does it hold for $| \Sigma | = 1$ ?


texts: Constructing a minimum spanning tree from an all-shortest path graph?

texts:
Given an $n \times n$ shortest path distance matrix $D$. And a complete graph $G(D)$ on $n$ nodes, where edge $(i, j)$ has weight $D_{ij}$. Furthermore, the distance matrix $D$ is computed for a connected network $T$ of $n$ nodes and $n-1$ edges - i.e. the shortest path distance between two nodes in $T$.

About the network $T$:

There are exactly $n$ nodes and $n-1$ edges.
The network is one connected component, thus it is a tree.
All edges have positive length.

My problem is that if I compute a minimum spanning tree $T'$ of $G(D)$ using, for instance, Kruskal's algorithm will the resulting tree $T'= T$?

I tried to argue that they are indeed equal, because if we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

I am not sure if this argument holds. How can I argue that $T' = T$?


texts: Solving $T(n)=4T(n/4)+\log n$ using master theorem

texts:
$T(n)=4T(n/4)+\log n$

I'm solving this recurrence relation by master theorem.

$a=4, b=4$ , $n^{\log_b a}=n^{\log_4 4}=n$

$f(n)=\log n=O(n^{1-\epsilon})$

when $\epsilon<1$, it is correct. So, $T(n)=\Theta(n)$.

But I'm confused how can $n$ be an asymptotically tight bound of $\log n$?

I'm not sure my solution is correct.


texts:
I am doing self study from MIT OCW exercises and I could not understand this question.

  The following rules define the binary-GCD state machine working on states in $\mathbb{N}^3$ with start state $(a,b,1)$ for $a>b>0$. If multiple rules apply, smaller numbers have precedence.

  Provided $\min(x,y) >0$, then $(x,y,e) \to $

  $(1,0,ex)$ if $x=y$
  $(1,0,e)$ if $y=1$
  $(x/2,y/2,2e)$ if $2|x \land 2|y$
  $(y,x,e)$ if $y>x$
  $(x,y/2,e)$ if $2|y$
  $(x/2,y,e)$ if $2|x$
  $(x-y,y,e)$ otherwise

The binary-GCD state machine computes the GCD of $a$ and $b$ using only division by $2$ and subtraction, which makes it run very efficiently on hardware that uses binary representation of numbers. In practice, it runs more quickly than the Euclidean algorithm state machine.

Each execution of a command (one of rules 1-7 according to algorithm) is a transition and the current state $(x,y,e)$ is stored in registers $A,B,E$. At first the values in the registers $a,b,1$

Here is the question I am having trouble with:

  Prove that the machine reaches a final state in at most $3+2\log(\max(a,b))$
  transitions.

  Hint: Strong induction on $\max(a,b)$

First, why does this state machine assume it halves the $\max(a,b)$ at every two transitions beacuse we can apply rule 4 and 7 and one extra rule to halve the $\max(a,b)$, which is more than two transitions/steps. I know it is not a common case but a case is a case unless proved.
Next I don't see where an extra 3 comes from in $3+2\log(\max(a,b))$.


texts: Let M be a k × n random matrix with iid entries such that

texts:
$M$ is a $k × n$ random matrix with iid entries such that $P(m_{i,j} = +1) =
P(m_{i,j} = −1) = 0.5.$ Let $k = O({1\over \epsilon^l})$
for some constant $l$. $v ∈ R_n$ is a fixed vector. Does a constant $l$ exist such that, with probability at least 0.9:
$(1 − ε)||v||_2 ≤{1\over \sqrt{k}} ||Mv||_2 ≤ (1 +ε )||v||_2.$
and how to find the minimum $l$.
P.S. $|| ||_2$ is the euclidian norm


texts:
For a practical task, we are asked to provide the transition table for a Turing machine that validates the number of open brackets is equal to the number of closing brackets.
The only tape symbols allowed are ( ) E B
If the number of brackets is equal (opening brackets = closing brackets) then the machine must halt in-state 'yes' and if they are not equal than it must halt in-state 'no'

Any clarification on this would be greatly appreciated! :)


texts: Minimum vertex cover algorithm with linear programming

texts:
Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value $\geq 0$, for each edge $v_av_b$ of $G$ set the constraint $x_a+x_b\geq 1$. The objective function is $\min\sum\limits_{1}^{n}{x_i}$.
Find the variable (or one of the variables) $x_i$, among the variables not set to $0$, that set to $0$ gives the minimum value of the objective function. Add the constraint $x_i=0$ to LP. Repeat until the optimal solution of LP is integer (that is each variable takes value in $\left\{0; 1\right\}$).
I am looking for a graph where the vertices associated to the variables that take value $1$ in the final optimal solution of LP are not a minimum vertex cover of $G$ (if it exists).


texts: NFA models with characters on nodes, not edges

texts:
I am attempting to understand the inner workings of the open source string matching library Hyperscan.

It takes a multiple-engine approach to the problem of generating string matches, and I'm still in the early stages of following through the debugging output to see how it does what it does.

However, one design decision already visible at this point puzzles me: when constructing an NFA, it doesn't use the traditional model of a directed graph with edges labeled with characters, and nodes labeled with whether or not they accept. Instead, it seems to use a model (*) of a directed graph with unlabeled edges and nodes labeled with a set of characters that can reach this node, along with designated special nodes for accepting strings. (specifically, it has a special NODE_ACCEPT node and a special NODE_ACCEPT_EOD node; nodes that mean "accept and ignore remaining input" have edges to NODE_ACCEPT and nodes that mean "accept if at end of input" have edges to NODE_ACCEPT_EOD)

I think this model is equivalent to the standard NFA model, but I can't find any references to this NFA model anywhere; I wonder if it goes by a standard name that I just don't know, and therefore can't search for. (My attempts just get buried in page after page of explanations of the standard NFA model)

So, has anyone seen an NFA model like this before? Are there any references I can look at to find out why one might prefer a model like this?

(On the off chance that anyone has already written up something on how the compiler and the various string matching engines embedded inside the Hyperscan library work, I'd also love any pointers to that. I primarily want to learn about state-of-the-art string-matching techniques, not about how to reverse-engineer C++.)

(*) I'm simplifying slightly here and ignoring bits of node and edge labels that seem unused at the initial stages.


texts:
Is it proper to view conditional probabilities, such as the forms:

P(a|c)

P(a|c,d)

P(a, b|c, d)

...and so forth, as being tensors?

If so, does anyone know of a decent introductory text (online tutorial, workshop paper, book, etc) which develops tensors in that sense for computer scientists/machine learning practitioners?

I have found a number of papers, but those written at an introductory level are written for physicists, and those written for computer scientists are rather advanced.


texts: Big O notation question for set insertion with sequential scan?

texts:
A friend and I are asking some questions on Big O Notation.

We have an operation that requires a sequential scan on insertion of an element O(n).
The insertion itself of an element is O(1).
We are inserting a whole set of n items.

We both agree the time for insertion is O(n+1) or simply O(n) reduced. But, we have two questions..

Does Big O Notation ever refer to the time for a set operation such as insertion of a whole set, or only to an individual elements operation on the set?
Can we ever say the time for an "insertion of a whole set of n size is O(n**2)" per the above?


texts:
I’m trying to find an algorithm that can give me an approximate solution for a wiring problem that I have been asked to look at. I believe this is closely related to finding a node weighted Steiner tree – e.g. http://www.cs.umd.edu/~samir/grant/gk98b.ps.

I have a number of connectors which have a fixed location in space and are connected together by wires. This can be represented as a graph where the connectors are nodes and the wires are edges:

Each wire needs to be surrounded by a tube to protect it and a tube can contain many wires. Two or more tubes can be joined together at a junction. In the sketch below, the black lines show the outside of the tubes and the grey circles show junctions, but with each connector still connected by the same wires as before:

Both the tubes and the junctions have a cost associated with them – for the tubes this is proportional to the length of the tube, for the junctions this is a fixed cost per junction. For example, if the tubes cost \$10 per metre and the junctions cost \$5 each, 1 metre of tubes with two junctions would be 10 + 5 + 5 = \$20.

I would like to find a layout that minimises the cost of the total length of tube + the cost of the junctions. I don’t think it’s quite the same problem as the reference above – I need to ensure that that the wires connecting between the connectors do not change, only the intermediate junctions between them. My real application has approximately 300 nodes and 1500 edges.

Thanks,

Rich


texts: I want to calculate/estimate the energy consumption for the different convolutional neural networks. Is there any possibility to measure the energy consumed by AlexNet for example with a tool or with Keras or something else?


texts: sum selected nodes of a set in $\log n$ time

texts:
Given a sum operation of a dynamic set $S$ of length $n$ which includes integer pairs $(x, y)$. The sum operation is defined as taking two inputs $a$ and $b$ such that $a \leq b$. The sum operation should return the sum of y values of all pairs $(x, y)$ such that $a \leq x \leq b$ in $\log n$ time.
My goal is to come up with a data structure that supports the operation described above.
My attempt: If we need the operation in $\log n$ time, we definitely need a self-balanced tree. In this problem, I choose splay-tree. The amortized complexity of splay-tree for insert, search, and delete are all in $\log n$ time. Is the amortized complexity of sum operation in $\log n$ as well? If yes, how can we prove this?


texts: Does integer programming $\in$ NP imply $NP=CoNP$?

texts:
Although it is relatively simple to see that integer linear programming is NP-hard, whether it lies in NP is a bit harder. Therefore, I'm wondering whether the following reasoning shows that $ILP\in NP$ implies $NP=CoNP$.

To be precise, I am considering the decision variant of ILP over a non-unary input encoding, so the problem is: given an integer matrix $A$; an integer vector $b$,  does there exist an integer vector $y \in Z_n$ with $Ay \leq b$?

The main issue here is that if we take such an $y$ as NP-certificate, it might be of exponential size in terms of the input, but this of course does not mean a certificate cannot exist.

My idea was that if we assume ILP in NP, we can use a discrete version of the Farkas lemma (see here) to transform an ILP instance with the answer NO to an ILP instance with the answer YES, which then would imply that ILP is in coNP. So we get an NP-complete problem in coNP, which implies that $NP=coNP$. Since most people think $NP\neq coNP$, this is 'evidence' for ILP not being in NP.

However, I'm not sure if my reasoning is correct. In particular, does this 'discrete Farkas lemma' work in polynomial time and create an ILP of polynomial size of the original one?


texts: Monotone boolean satisfiability with at most k 1s is NP-Complete

texts:
I am to prove that monotone boolean formula satisfiability checking when at most k variables are set to 1 is an NP-Complete problem.  Proving that it is in NP is easy, but I'm having difficulty showing that it is in NP-Hard.  I have seen this, but I would rather not use its solution, as the textbook for the course I am self studying does not present Dominating Sets as an NP-Complete problem.  The NP-Complete problems presented in my book(Dasgupta, Papadimitriou, and Vazirani) are the following: 3SAT, Traveling Salesman, Longest Path, 3D-Matching, Knapsack, Independent Set (related to Dominating Set from what I understand), Vertex Cover, Clique, Integer Linear Programming, Rudrata Path, and Balanced Cut.

From my understanding of the problem, if you restrict the clauses to 2 literals each, then this directly parallels the vertex cover problem, and is thus NP-hard.  I was wondering if there was any way that I could use this fact to say that the unrestricted problem is also NP-Hard.  I intuitively feel that this should work, because the restricted version is a subset of the restricted version, so in at least some cases the problem is NP-hard.  Since you always take the worst case scenario, could you extend this to NP-hardness for the unrestricted problem?  If so, how would I word that (this is for a self study, not to be turned in), in the proper form?  Because my above explanation has a roundabout method of showing the point.

tl;dr Can you prove that something is np-hard by showing that a subproblem is np-hard?  I intuitively feel like you should, but want to confirm.


texts: Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?

texts:
Let $G=(V,E)$ be an undirected graph without self-loops or parallel edges.

Is the following statement true?
If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge, then $G$ is connected.

I've proved it for $|E|=n-1$:

Per induction:
Start:
For $\left|V\right|=1$ the graph is trivially connected.

Induction step:
Let the statement be shown for all graphs  $G=\left(V,E\right)$ where $\left|V\right|=n-1$ and $|E| = n-2$.

Let further $G=\left(V,E\right)$ with $\left|V\right|=n$ and $|E| = n-1$ be given.

We're now looking for an induced sub graph  $G|_{V^\prime}$ where $V^\prime\subset V, \left|V^\prime\right|=n-1$, so that  $G|_{V^\prime}$ has at least $n-2$ edges.

(Any such sub graph can have at most $n-2 $ edges, as there'll always be at least one edge that originally lead to the removed node)

Let's now assume that every sub graph $G|_{V^\prime}$ has less than     $n-2$ edges.
Then, the removed node in any sub graph would have at least $2$ edges.

Thus, every node must have at least $2$ edges, and therefore there'd have to exist at least $n$ edges in the graph.

Therefore, there's at least one sub graph $G|_{V^\prime}$ with $n-2$ edges, for which our induction assumption holds. And because there is one edge from $G|_{V^\prime}$ to the erased edge, we get that $G$ is connected.

Therefore, the induction is completed.

However, if I try to generalize the above proof, the same style leads to an inequality that only holds if $|E|>|V|$.

Therefore, if the above proof can be generalized, how would it look? If not, what's an example where it fails?


texts: Calculating the complexity of an algorithm exercises

texts:
I am really bad at calculating correctly the complexity of a given algorithm. I would like to know if there is some book or online resources where I can find many exercises that ask to calculate the complexity of a given algorithm.

Thank you!


texts: Proving that the cover time for graph is exponential in the worst case

texts:
How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$?

The cover time is the expected length of a random walk that visits all vertices.


texts: Can anyone explain me what is a trampolined interpreter? I am versed with relevant concepts viz. procedural languages, continuations etc but am finding difficulty understanding the definition/need for trampolining. Please help.


texts: Prove Vertex-Cover of maximum degree 3 is NPC

texts:
This is a homework question. I need to prove that the following language is in NP Complete:

  3-VERTEX-COVER = $\{\langle G,k\rangle \mid$ G is an undirected graph, each vertex in $G$ has at most $3$ incident edges, and there is a vertex cover of size $k$ in $G\}$

Showing that it is in NP is easy. Now, to show that it is in NPC I thought about showing a reduction from Vertex-Cover. But I can't seem to think of what to do with a graph I get as <G,k> which is in Vertex-Cover, to make each vertex degree at most 3 without changing the vertex-cover property. Any hints?


texts: Are some Integer programming formulations completely useless for relaxation?

texts:
I was tasked with constructing an integer programming formulation for an NP-hard problem, and then with specifying its LP relaxation and the resulting approximation factor.

The problem is that, while my integer programming formulation is correct and clever (I like to think), it seams that its relaxation is completely useless. In fact, the LP relaxation seams like it would always lead to the worst possible solution to the original problem.

Is this possible? Is there some known way of deriving a proof that an LP relaxation of an IP problem can only be so good, some way of telling you when to quit looking?


texts: How would Computer Science help the world in the novel coronavirus outbreak

texts: This may seem off-topic question but I am really wondering how CS folks could help in situations like coronavirus. What novel problems arise from such disease? From CS and ML/AI perspectives, is there anything that Computer Scientists could do to better combat the coronavirus?


texts:
So in this paper I'm reading (https://adamsmith.as/papers/fdg2013_shortcuts.pdf), the authors talk about an $NP^{NP}$-complete problem, in relation to Answer Set Programming. I know what P, NP, etc. are but I don't unerstand what they mean with $NP^{NP}$. Also I can't Google it because Google doesn't recognize superscript.

I did find out it's also mentioned in this book, but they still don't provide an explanation.

Can anyone ecplain this class of problems to me?


texts: Minimum depth of a leaf in a tree that corresponds to a comparison-based sorting algorithm

texts:
The lower bound of comparisons in a comparison-based sorting algorithm is $\log_2 n!=Θ(n\log n)$. Yet there can be less comparisons needed in an algorithm.
If you take a sorted array, it will take $n-1 = O(n)$ comparisons (with insertion sort) to sort the array — comparing every adjacent pair of numbers. I don't understand then how is $\log_2 n!=Θ(n\log n)$ the lower bound.

I also don't understand the corresponding trees to the sorting-based algorithms:
each leaf in the tree corresponds to one of the permutations of the $n$ numbers. If the minimum number of comparisons needed is $\log_2 n!$ then the depth of every leaf should be at least $\log_2 n!$, yet I saw that it's possible for a leaf to be with depth of $O(n)$.

Can there be leaves with depth even smaller than $n-1$?


texts: Algorithm for coherent motion. Which bus is app user on?

texts:
I am currently working on an app with a map of the city, with markers for each bus. As a feature, the phone should show which bus the user is on.

To achieve this I am working on building a function that consumes a stream of a set of buses and their positions (Stream<Set<Tuple2<BusId, Location>>>), and a stream of phone location, to produce a Stream of bus predictions. The prediction should contain a confidence level.

The function should return the current prediction in real-time, and handle scenarios where the user changes the bus.

How could this be accomplished?

Both streams contain very precise locations at a rate of once every second.


texts:
Assume the $\mathcal{F} = \{\, f_{s} \,\}_{s \in \{\, 0,1 \,\}^{*}}$ be a family of computable functions, where $f_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$.

Let $F_{n}$ be a distribution of functions $f_s$ where $s$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$, and let $RF_n$ denote the uniform distribution over the set of all functions from $\{\, 0,1 \,\}^n$ to $\{\, 0,1 \,\}^n$.

So, $F_{n} = f_{\{\, 0,1 \,\}^{n}}(x)$ for a fixed $x \in \{\, 0,1 \,\}^{n}$, right?

Then we say $\mathcal{F}$ is a family of PRFs if for every PPT $A$,
$$\left\vert \Pr \left[ A^{F_{n}}\left( 1^{n} \right) = 1 \right] - \Pr \left[ A^{RF_{n}}\left( 1^{n} \right) = 1 \right] \right\vert < \varepsilon \left( n \right)$$

This definition is seems correct, but it implies that $A$ can ask the query of $f_{s}$ for at most $poly(n)$ times, $s$ may be different, but $x$ is always the same. It looks strange.

How about let $F^{\prime}_{n}$ be distribution of functions $f_s$ whose input $x$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$ with any fixed $s$, and let $RF^{\prime}_n$ denote the uniform distribution over the set $\{\, 0,1 \,\}^n$.

So $F^{\prime}_{n} = f_{s}\left( \{\, 0,1 \,\}^{n} \right)$ for a fixed $s \in \{\, 0,1 \,\}^{n}$, right?

Then we say $\mathcal{F}$ is a family of PRFs if for every PPT $A$,
$$\left\vert \Pr \left[ A^{F^{\prime}_{n}}\left( 1^{n} \right) = 1 \right] - \Pr \left[ A^{RF^{\prime}_{n}}\left( 1^{n} \right) = 1 \right] \right\vert < \varepsilon \left( n \right)$$

This definition implies that $A$ can ask the query of $f_{s}$ for a fixed key $s$ at most $poly(n)$ times.

Is the first definition is correct? Why not choose the another one?

Or even they are both wrong, $F_{n} = f_{\{\, 0,1 \,\}^{n}}\left( \{\, 0,1 \,\}^{n} \right)$?? It makes me confused.


texts: Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$

texts:
I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it?

Possible errors:

It first prove the case $\text{height(x)=0},$ then it says "For inductive steps, consider a node $x$ that has positive height".

From my understanding of inductive proof, the base case should be able to trigger the inductive statement. I mean: the "first domino" should trigger the next one, so the statement should be something like non-negative height.
It says "each child has a black-height of either $\text{bh}(x)$ or $\text{bh}(x)-1$", but when applying, only the latter is used: $(2^{\text{bh}(x)-1}-1)+(2^{\text{bh}(x)-1}-1)+1=2^{\text{bh}(x)}-1$.

Paragraph from the book:


texts: How to define a context free grammar from a regular language?

texts:
I wonder how do you clasify S->a (where a is a Terminal Symbol)

It can be right linear,left linear and context free at the same time?

So the only way to distinguish them is to see what productions there are with Non-terminal symbols (like S in this example)

0) If I see S->a it can be (left/right/context-free) impossible to know

1) If I see only production in the form of S->a and S-> aS then it is right lineair

2) If I see only production in the form of S->a and S-> Sa then it is left lineair

3) If I see a mix (left and right) of the form of S-> aS and S-> Sa then I know that it is context free

4) If I see a production with a terminal symbol on the left AND on the right then I also know it is context free : like this S->aSa

Are these 5 statements correct? Am I missing scenario's to define the difference between regular and context free?


texts: Optimal parallel-time repeated modular squaring circuit

texts:
Given a 4096-bit integer $x$ and a 4096-bit RSA modulus $N$ (of unknown factorisation) what is the fastest circuit to compute $x^{2^T} \mod N$ where $T=2^{40}$. That is, what is the fastest parallel-time (i.e. lowest latency) algorithm for repeatedly squaring $x$ modulo $N$ a trillion times?

For context, I am looking to build a Verifiable Delay Function ASIC to squeeze out opportunities for parallelisation that CPUs/GPUs cannot capture.

I have found hundreds of papers in the literature that cover modular multiplication. Families of algorithms include Montgomery, Barrett, Residue Number System (RNS), sum of residues, Kochanski, Brickell. Often the optimised parameter is not latency—e.g. it can be throughput, power consumption, die area, simplicity, side channel leak resistance, etc. The fastest implementation I found does a 4096-bit modular multiplication in 607ns.

Sub-questions:

What is the optimal parallel-time algorithm for squaring a 4096-bit integer? One brute-force approach is to implement a 4096-by-4096 multiplier with $4096^2$ gates and a tree of 3-to-2 adders of depth 4096. Can we do better than that?
The algorithms discussed in the literature often do modular multiplication (as opposed to modular squaring). What latency gains can be had from designing a circuit specific to modular squaring?


texts: How does LZW decompress data with dictionary clearing/flushing? I understand that a space is reserved in the dictionary that represents a clear code (usually 256), but how is this code actually used when compressing and decompressing data? My thoughts for compression are that it checks the table size, and if the table size has reached the maximum size it appends the flush character to the output before resetting the dictionary. I'm not sure what it does for decompression though.


texts: Given a Turing machine M, is there a TM that computes the number of states M has?

texts: I've seen it used but I can't think of a way to construct such TM. Would appreciate any help!


texts: Constructing a binary tree with given traversals

texts:
I have given a post order & in order traversal a BST & I need to construct it. I want to know how to do this.

for eg.

Post Order : DCBGFEA

In Order : BDCAFGE

This is how I am trying to do :

From POST order it is clear that A is root. So in IN order, I consider everything right to A is at it's right sub tree & so for left.

Now, I consider A's left sub tree. It has BDC. Again from POST order, I conclude that B is root.

Now, again consider B's sub tree. It has contents DC & POST order, C has to be at root. So now I get C at root. But where to place C, at B's left or right ? It's where I am getting stuck now.

Same happening with A's right sub tree also. I place E as root of A's right sub tree. Then I conclude element below should be F, but does it come at right or left of E ?

I want to know how to tackle this problem & also is there any better approach for this to do.


texts: Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

texts:
Define the language
$\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$
where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$.
Prove that $R$ is co-recursively enumerable (co-r.e.).

So far, I have the following:
In order to prove the above, we need to show
$\qquad R^c$ =  $\{x \in \{0,1\}^\ast \mid C(x) \lt |x| \}$
is r.e. That is there exists a program $\pi$ such that the univeral TM $U$ with argument $\pi$ equals $x$ and $|\pi| \lt |x|$ (where $U(\pi) = x$ and $|\pi| \lt |x|$).
We start by enumerating all strings in $\{0,1\}^\ast$.
I have no idea where to go from this point onward.


texts: convert domain relational calculus with two same tuples to relational algebra

texts:
Given two relations $R(A, B)$ and $S(A, C)$.

I can understand the early part is the projection of attribute $A$ from $S$, which could be written as $π_a(S)$, but later part is confusing and not understandable to me.

$$ \{a| (\exists c) (S(ac)) \land (\exists b_1) (\exists b_2) ( R(ab_1) \land R(cb_2) \land b_1 > b_2 ) \}$$

Can anyone help me understand it? and how to convert this domain relational calculus to its relational algebra?


texts:
If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$.

Can anyone clarify what does this mean?


texts: Determining possible data structures given a set of required operations

texts:
This was an interview question that I was told is supposed to be an open ended discussion of the trade-offs.
You have a collection of comparable objects and want to be able to do the following:
1. Lookup, add, delete objects
2. Get and/or extract Min, max objects
3. Objects should be unique (no duplicates)

A max-heap or min-heap almost fits the criteria except you can only have easy access to either min or max but not both. I ended up saying that if we know if one of max or min is more commonly needed, build a max or min heap.

A hash table is out of the question since the elements are un-ordered although it does have O(1) lookup.

What are the most appropriate data structure(s) in this scenario?


texts: Regular expression for strings not starting with 10

texts: How can I construct a regular expression for the language over $\{0,1\}$ which is the complement of the language represented by the regular expression $10(0+1)^*$?


texts: Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter

texts:
I have been trying solve this problem for a while now for a university assignment. I'm required to build a DFA and an NFA for the above question. So far I have been able to solve the DFA but can not find a solution for a proper NFA after multiple tries.
The solution of my DFA for the language provided above:
My attempts for the NFA are down below. I apologize for my messy handwriting but these were just rough works that I was drawing out on the go.
My first attempt at solving the NFA
My second attempt at solving the NFA
My third attempt at solving the NFA


texts:
I have problems to determine the size of the following sets in dependancy of the parameters $m, n>0$:
$$M_{m,n}=\{a^iwa^{m-i}\mid 0\le i \le m,\;w\in\{a,b\}^n\}$$
It is easy to see that $|M_{m,n}|\le (m+1)\cdot 2^n$ since there are $m+1$ possibilities for $i$ and $2^n$ possibilities for $w$. If the sets would take the words $w$ from a disjoint alphabet (e.g. $w\in\{b,c\}^n$), then the number of elements would be exactly $(m+1)\cdot 2^n$. But for $w\in\{a,b\}^n$ each set $M_{m,n}$ is ambiguous in the sense that the some words could be obtained from different $i$'s and $w$'s. For example $w=a^n$ leads to the same word $a^{n+m}$ for each $i$. By the way, this example yields $|M_{m,1}|=m+2$ because there is $1$ element for $w=a $ and $m+1$ elements for $w=b$. Another ambigious example for $n=2$ is $$a^i\;ab\;a^{m-i}=a^{i+1}\;ba\;a^{m-i-1}$$ for $0\le i \le m-1$, which together with the thoughts for unary $w$'s yields $|M_{m,2}|=2m+4$.

However, for increasing $n$ it becomes more and more difficult and unfortunately I am not able to generalize my approach. What I am hoping for is that $|M_{m,n}|$ is still in $\Theta(m\cdot 2^n)$. Any help?


texts:
Given these 5 axioms of Hoare Logic:

\begin{array}{cl}
\frac{}{\{\phi([x \leftarrow E])\}\ x := E\ \{\phi(x)\}} & \mathtt{Assignment}\\\\
\frac{\{\phi\}\ P_1\ \{\eta\} \quad \{\eta\}\ P_2\ \{\psi\}}{\{\phi\}\ P_1; P_2\ \{\psi\}} & \mathtt{Sequencing}\\\\
\frac{\{\phi \land B\}\ P_1\ \{\psi\} \quad \{\phi \land \neg B\}\ P_2\ \{\psi\}}{\{\phi\}\ \mathtt{if}\ B\ \mathtt{then}\ P_1\ \mathtt{else}\ P_2\ \{\psi\}} & \mathtt{Conditionals}\\\\
\frac{\{\phi \land B\}\ P\ \{\psi\}}{\{\phi\}\ \mathtt{while}\ B\ P\ \{\psi \land \neg B\}} & \mathtt{Iteration}\\\\
\frac{\phi ⇒ \phi1 \quad \{\phi1\}\ P\ \{\psi1\} \quad \psi1 ⇒ \psi}{\{\phi\}\ P\ \{\psi\}} & \mathtt{Weakening \to Strengthening}
\end{array}

Trying to understand the following:

$\mathtt{Assignment}$

What $\phi([x \leftarrow E])$ means. In the presentation it says $\phi([x \leftarrow E])$ replaces every "free occurence" of $x$ in $\phi$ by $E$. I am confused because I thought that was what the assignment $x := E$ was doing. So my reading is: "precondition: replace each free occurrence of $x$ in state $\phi$ with $E$, program: assign $x$ to $E$, postcondition: $x \in \phi$". I am confused by both the pre and post conditions. To me it should be written $\{\phi[x] \land \phi[E]\}\ x := E\ \{\phi[x == E]\}$, that is, "given $x$ in state $\phi$ and $E$ in state $\phi$, when I assign $x$ to $E$, I get the new state where $x$ is equal to $E$". Wondering if someone could help clarify this my interpretation.

$\mathtt{Sequencing}$

This one makes sense. If program $P_1$ leads state $\phi$ to state $\eta$, and program $P_2$ leads state $\eta$ to state $\psi$, then program $P_3 := P_1 ; P_2$ leads state $\phi$ to state $\psi$.

$\mathtt{Conditionals}$

"If we're in state $\phi$ and we have variable $B$, then program $P_1$ leads to state $\psi$. Similarly for $P_2$, but when we don't have $B$ in state $\phi$"
This is essentially a sequential composition.
I would've written it as $\{\phi[B]\}\ P_1\ \{\psi\}$ and $\{\phi[\neg B]\}\ P_1\ \{\psi\}$, would be helpful to better understand the notation on why they wrote it with the $\land$. To me $\{\phi \land B\}$ says either "B is true in $\phi$ state" or "B exists in $\phi$ state", can't tell.

$\mathtt{Iteration}$

"If $B$ is in state $\phi$, and program $P$ leads to state $\psi$, then $\mathtt{while}\ B\ P$ leads to state $\psi$ without $B$". So this is an axiom.
I don't understand how this can be an axiom because there is so much that is going on (tons of iterations for example). Wondering what allows this to be an axiom.

$\mathtt{Weakening \to Strengthening}$

I don't understand this one yet.

To summarize, these are my questions:

What the notation is for having certain values in a state in the pre- or post-condition. If it's $\{\phi[B]\}$ or $\{\phi(x \leftarrow B)\}$ or $\{\phi \land B\}$ or $\{\phi(B)\}$. What the preferred notation is and its meaning. I have also seen $\{\phi[B/x]\}$
How to interpret the assignment rule.
How the while loop is allowed to be an axiom, when it does so much.

Thank you so much for the help.


texts: Nice Computational Approach to the generalized "24 Problem"?

texts:
I was wondering about the possible existence of an algorithm to essentially play an extended version of the game '24'.

Essentially, we are given N cards, each between 1 and 10. We aim to use the basic operations (+, -, *, /) and parentheses wherever we like to obtain a desired value T using all of the cards. Assuming that T is reasonably valued (i.e. not so large that it obviously cannot be reached), does there exist a non-brute force algorithm that finds at least one solution for obtaining T using a set of N cards?

Thanks!


texts:
Assume I have two Krom formulas $\psi_1, \psi_2$.  Krom formulas are propositional formulas in CNF that have 2 literals in every clause.  Each literal can be negated or unnegated.  In other words, $\psi_1,\psi_2$ are 2-CNF formulas.  For instance:
$(x_1 \vee \neg x_2) \land (\neg x_2 \vee x_3 ) \land (x_3 \vee x_4)$
I want to decide whether $\psi_1,\psi_2$ are logically equivalent, i.e., $\psi_1 \leftrightarrow \psi_2$.  Equivalently, I want to test whether  $F=(\psi_1 \vee \neg\psi_2)\wedge (\neg \psi_1 \vee \psi_2)$ is true for all assignments of $x_1,\dots,x_n$.
Is this problem tractable?


texts: How to select rows from two matrices to have one larger?

texts:
You are given two matrices $$\mathbf{A}=\begin{pmatrix}a_{11} & \ldots & a_{1n}\\\vdots & \ddots & \vdots\\a_{m1} & \ldots & a_{mn}\\\end{pmatrix},$$ and $$\mathbf{B}=\begin{pmatrix}b_{11} & \ldots & b_{1n}\\\vdots & \ddots & \vdots\\b_{m1} & \ldots & b_{mn}\\\end{pmatrix},$$ of positive numbers.

We want to find, for $1\leq j\leq n$, a subset ${S}_j\subset\{1,2,\ldots,m\}$ of at most two rows such that ${S}_i\cap{S}_j=\emptyset$ (for $i\ne j$) and $\left|\bigcup_{j=1}^n{S}_j\right|$ is as large as possible and for $i,i'\in{S}_j$, we have: $$a_{ij}\geq b_{i'j}.$$

I started by reducing the problem to a maximum matching problem. If we create $m$ nodes. For each column $1\leq j\leq n$, we create an edge between node $1\leq i\leq m$ and node $1\leq i'\leq m$ ($i\ne i'$) if there is no edge already and if $a_{ij}\geq b_{i'j}$. Next, run a matching algorithm on the created graph to find a maximum-cardinality matching ${M}$.

Do you have any hints on how to solve the problem? Am I on the right direction?


texts: Why does this algorithm not have an exponential complexity?

texts:
In this article :
Kinodynamic Motion Planning
B. Donald, P. Xavier, J. Canny, J. Reif
https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf

The authors present a PTAS algorithm that can compute a safe, close to optimal trajectory from a point A (having a certain speed vector) to a point B (having a certain speed vector). They do this by transforming the problem to finding the shortest path in a directed graph. All vertices in the resulting directed graph have an outgoing degree of 3.

I don't understand how we can find the shortest path in this directed path from one point to another (by using BFS) without the complexity being exponential, since doing a BFS from the starting point until we encounter the end point would take $O(3^x)$ with $x$ being the layer of the BFS.
Instead the complexity that is noted on page 5 of the article is this :

  $O( n( \frac{lv\gamma³}{\epsilon⁶})^d)$

$n$ being the number of bounding halfplanes on obstacles, $l$ being the length of the side of a cube in which all points are placed, $v$ is maximum velocity and $\gamma$ is maximum acceleration divided by maximum velocity. $\epsilon$ as always is the approximation value and $d$ the number of dimensions in which our problem is placed. For simplicity let $d$ be $1$.

Clearly we can see this complexity is not exponential, my question is why? Even in one dimension, we still obtain a graph in 2 dimensions (1 for position and one for velocity) and the BFS will still take exponential running time. Am I missing something?

Thanks


texts: Choosing algorithms and/or data structures at runtime based on input characteristics

texts:
I've been reading about Adaptive Computing, i.e. the idea of computer programs taking feedback from the environment at runtime to improve the output in some way. More precisely, my current focus is in Self-Optimization: how to write programs that are able to choose the best algorithm/data structure in response to changes in the input profile. In the lower end, simple heuristics are used to apply specific algorithms in special cases, eg. Tim/Quick/MergeSort using Insertion Sort (which is $O(n^2)$) when the partition size is below a certain threshold. On the other extreme we have JIT compilers that optimize/deoptimize the code at runtime according to certain metrics.

However, I haven't found so far any examples of "high-level" decisions, like automatically choosing between two distinct implementations of an algorithm or a data structure at runtime. For example, think about a AdaptiveList object with the usual operations (add,remove...) and a array-backed storage. If the program keeps inserting elements in the middle of the list (which requires moving a lot of data to free space for the new element), the AdaptiveList may choose to move the data out of the array into a linked list. If the usage pattern changes again, the AdaptiveList may decide to go back to the array storage.

The closest thing I've been able to find (other than JIT compilers, of course) are projects like ATLAS and FFTW where
the code generation/algorithm selection is done a priori and never revisited. Maybe I'm the first one to entertain such fantasies, but I doubt it. Are you aware of other papers/projects that have investigated this idea?

Thanks for reading!


texts:
We have a $N_1 \times N_2$ grid.
We have a collection of rectangles on this grid, each rectangle can be represented as a $N_1$-by-$N_2$ binary matrix $R$. We want to cover the grid with those rectangles.

Is the decision version of this set cover problem NP-complete ?

Input : Collection $\mathcal{C}=\{R_1,R_2,\dots,R_L\}$ of rectangles on the grid (input size: $N_1N_2L$), and $K \in \mathbb{N}^+$
Output : Subset $\mathcal{S}\subset\mathcal{C}$ with $|\mathcal{S}|\leq K$ and $\mathcal{S}$ containing for each cell at least one rectangle covering it.

I found that the 1D case ($N_2=1$) can be solved in polynomial time by dynamic programming: any optimal cover is going to be the union of

an optimal cover for some subproblem of covering the first $N_1-n_1$ cells.
a 1D rectangle, i.e. an interval, covering the remaining $n_1$ cells.

I don't think however DP can work for the 2D problem: for the 1D problem, you have a $N_1$ subproblems to solve, but for 2D you have $\binom{N_1+N_2}{N_2}$ subproblems (number of North-East lattice paths on the grid).

I think the problem might be NP, but I am not sure (though it seems harder than P), and I have not succeed in finding a polynomial reduction from an NP-complete problem (3-SAT, Vertex Cover,...)

Any help or hint is welcome.


texts: Arrange the array element with minimum number of swaps

texts:
Given an array with some elements in which elements can occurs multiple
times, so now how to arrange them in such order that no two same elements are together using minimum number of swaps.( it may not be possible to arrange all of them.)


texts: Residual graph of a graph with bidirectional edges?

texts:
Let's suppose we have a directed graph $G$ which has at least a pair of vertices $v,w$ such that $(v,w) \in E, (w,v) \in E$.

$e.g:$

In the example, there is an edge going from $C$ to $A$ and viceversa.

So, my question is, what would be the way to model this graph with a residual graph?


texts: The path with the highest sum of weights

texts: Mr. Katsaros owns a rectangular olive grove divided into 5 rows and 4 columns. He notes down the amount of olives (pounds) possibly obtainable from each of 20 square sections. The picking starts from the furthest north-west section and ends in the furthest south-east section. What is the maximal amount of olives that can be picked at one go if the pickers can only go directly south or directly east? Implement your algorithm using C++.   I think the right method incorporates dynamic programming. I guess the rectangular note has to be transformed into a directed graph but I don't know how. I was thinking about attributing amount from a section to the edges leading to the corresponding vertices and using Ford-Fulkerson algorithm. However, I don't know if that is the correct approach and how to implement it.


texts: What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$

texts: I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this formula?


texts: Point cloud clustering based on similarity in less than $O(n^2)$

texts:
not sure if this is the right place to ask this but here it goes.

Let's assume I have some 2D points dataset consisting of facial landmarks, and I want to cluster these based on similarity so that I can refer to a notion of "prototype" of a facial expression.

As a measure between one point set and another I could be using a sum of euclidean distances.

Is there a way to obtain a set of prototypes without passing through the landmarks $O(n^2)$ times?

To better explain what I'm thinking, let's say I'm processing a video frame by frame.

I start with the landmarks of the first frame, and I put it in my list of prototypes because I have no other reference.

Following this, for each subsequent frame, I compare it with the first "prototype" and if it's below a certain similarity threshold I assume it's not unique enough and skip it, and so until I find one set of landmarks that are dissimilar enough, so now I have two "prototypes".

From this point onward, I need to do the similarity check with two "prototypes", and so on.

Another caveat is that I would also like to be able to store the "prototype" that the current frame matches the most.

I will also need to do a second pass through a second clip for a similar matching with the "prototypes" identified in the first pass.

Is there a more efficient way to do this, other than the naive approach?


texts: Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?

texts:
I'm a bit confused by Wikipedia's tables of algorithms for the shortest path problem.
For an unweighted graph with $E$ edges and $V$ vertices, it gives the best algorithm as breadth-first search, with a time complexity of $O(V+E)$. But above that, for an undirected graph with natural-number weights, it gives the best algorithm as an $O(E)$ algorithm due to Thorup (1999). This seems faster than the $O(V+E)$ for breadth-first search despite applying to a more general problem.
Am I correct in understanding that the $O(V+E)$ breadth-first search algorithm applies to a directed unweighted graph, and for an undirected and unweighted graph, Thorup's 1999 $O(E)$ algorithm is faster even though it's capable of handling arbitrary natural number edge weights? This seems surprising to me.


texts:
My task is to develop an algorithm for the optimal arrangement of cylindrical objects in cartons. The algorithm is to have the task of placing as many products as possible into cartons, at the same time not exceeding the capacity of the carton and the permissible weight specified for the carton. Initially, I accept one size of cardboard and many different sizes and weights of products.

I made a little research and encountered a knapsack algorithm that seems the best to use for my example. This algorithm, however, most often uses only one size for objects and its value - in my case I have three dimensions X, Y, Z.

Do you know any other, better algorithms for my task? What is best to start writing the application? BTW the application would be in Python.


texts:
I recently came across these books:

Differential Geometry and Lie Groups: A Computational Perspective
Differential Geometry and Lie Groups: A Second Course

Their subject matter really intrigues me, as I really enjoy topology/geometry/analysis, but had not planned to pursue them since I also want to work in an area with very concrete application. However, I am skeptical. At one point I thought topological data analysis (TDA) was the perfect marriage of my interests, but I have found very little evidence of that field actually being used in computer science, much less in industrial or otherwise more 'practical' settings. It seems like TDA makes mathematicians feel more relevant to the data science world, but I'm not convinced that it makes them so (feel free to contradict me if you think I'm wrong on this point, but note that I want a concrete use case, not an abstract argument about its relevance). I have similar stories about coding theory, certain aspects of set theory, etcetera. They may have theoretical relevance, but is there any situation where, in the process of developing software, one might need to consult theses fields? I don't know of any.
So now my question: is there any practical field of computer science that makes advanced use of differential geometry? Medical imaging, other imaging, computer graphics, virtual reality, and some other fields come to mind as potential application areas. In my (admittedly limited) experience, however, these areas seem to use basic 3D geometry, numerical linear algebra, and sometimes numerical analysis of PDEs. Those are all very nice topics, but they do not require anything as abstract as differential geometry.
Thanks in advance.


texts: If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?

texts:
I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it will mean that all problems in NP can be solved in polynomial time.

My question is: does this proof also hold the other way? I.e. if an exponential lower bound for an NP-complete problem is proved, would that mean that no problems in NP can be solved in polynomial time?


texts: Are algorithms for searching text vs searching numbers fundamentally different?

texts:
I face this problem a lot while searching phone numbers and bank account numbers, when I do remember it partially.

I save a draft in gmail with the content I am mango. Then I search it, by entering just mango and it gets me to the draft.

But when I save a draft with some number such as 123987645 and try to search by entering 12398764 i.e just one character missing I fail to find it. Also I failed when I just typed  87645.

Out of curiosity I am asking are the algorithms for finding numbers and text fundamentally different? Or I am missing something?


texts: A question on the graph induced by the transition function of a deterministic Turing machine

texts:
Let $M$ be a deterministic Turing machine with totally defined transition function $\delta$ and working alphabet $\Gamma$.  Let $Q$ denote the statespace of $M$'s finite control. Let $G_M$ be the graph induced by $\delta$ which is defined as $G_M = (V,E)$ with $V = Q$ and $(q,q') \in E$ iff there exist $a,b \in \Gamma$ and $m \in \{\pm 1\}$ such that $\delta(q,a) = (q',b,m)$.
Are there any results which translate properties of the machine $M$ to graph theoretic properties of $G_M$ and vice versa?


texts: Computing 'score' of string which preserves < relation

texts:
Is there a way to calculate some kind of numerical 'score' for arbitrary strings which when compared with score of some other string will preserve '<' relation?

I've searched for order preserving compression/hashing but what I've found is either based on precomputing with known set of strings or is a some for of lossless compression.

edit:

To clarify - I don't need it to preserve order exactly. When I need is to have guarantee that if score(A) < score(B) than A < B. If score(A) >= score(B) than it still can be true that A < B. I just would be nice if probability of incorrect relation was 'low'.


texts: Association rules during execution in lambda calculus

texts:
I learned that expressions are left associative while abstraction are right associative, however, while solving some examples i faced this problem.
Succ 3 Succ 2
when i applied left associativety i got (Succ 3) Succ) 2
which was extremely long to solve.
However, i saw this guy on the internet, he said that we should parse it as Succ (3 Succ 2) which is Succ ( Succ Succ Succ 2) and the result is 6.
AND THE ANSWER IS RIGHT!
So now i am confused, during execution, should use the left or the right rule??


texts: Solving the recurrence T(n) = 4T(n/4) + n log n with the iterative method

texts:
I'm trying to solve

$$ T(n) = 4T(n/4) + n \log_{10}n.$$

I'm having trouble with Iteration Method near the end.
As far as I went, I obtained the General Formula as:

$$4^kT(n/4^k)+n\log n+\sum (n/4^k)\log(n/4^k)$$

And trying to get the moment when it finishes iterating:

$$(n/4^k)=1$$
$$n=4^k$$
$$\log_4n=k$$

And here I get stuck. I know I have to substitute $k$ with $\log_4n$ but after that I'm lost. Can I get a bit of help with explanation of every step?

Here are some more details:

Swapped $\log_4n$ on all $k$:
$$4^{\log_4n} T(n/4^{\log_4n})+n\log_2n+\sum_{n=0}^{\log_4n}n\log n$$

From logarithm rules of $a^{log_an} = n$, it ends like this:
$$(n)(1)+n\log_2n+\sum_{n=0}^{\log_4n}n\log n$$

I'm not sure how to express the sum in $n$, but as you can see already, it is $O(n\log_2n)$, and with the Master Theorem, you obtain the same result $O(n\log n)$.


texts: "Practical coinduction" over $\mathbb N_\infty$?

texts:
I've just finished reading the paper Practical Coinduction by Kozen and Silva. What is the difference between induction over $\mathbb N$ and coinduction over $\mathbb N_\infty$?

From the paper, it seems that coinduction is almost the same as induction, but with more restrictions. In particular, it appears that most (or all) coinduction proofs over $\mathbb N_\infty$ are also valid induction proofs over $\mathbb N$.

The main restrictions the paper lists are opacity and guardedness. What examples are there of induction proofs over $\mathbb N$ that satisfy these properties (and are therefore valid coinduction proofs)? And what examples are there of induction proofs that don't satisfy these properties (and are therefore not valid coinductions)?


texts: What algorithm to compare string against multiple patterns?

texts:
My problem can be characterized as a string-search problem for a finite amount of patterns. So Aho-Corasick algorithm would be a good first choice.

However, I have certain properties that limit the scope of the problem, and I was wondering if there was another, better suited algorithm.

A set of known strings to search for (less than a thousand patterns).
The patterns are short (less than 20 characters).
The patterns are quite disjunct, in a way that most of them don't share a common prefix.
A large number of strings to search in (millions).
The strings which are searched for the patterns are short too.
Any hit would be an exact match.
I want to stop searching after the first hit has been found.


texts: Bidirectional Search on possible negative weight edges digraphs

texts:
There are plenty material about bidirectional search with non-negative edge weights. One example is this paper. I am looking for any improvements using a bidirectional approach for acyclic digraphs with possibly negative weight edges.

The main approach for mono-directional search on possibly negative edge weights is Bellman-Ford. However, i don't think there's any valid early termination criteria that makes bidirectional Bellman-Ford better than the mono-directional.

Can someone provide ideas or references for a bidirectional search on an acyclic digraphs with possibly negative edge weights?

Thanks in advance.


texts:
I'm confused about the point of adaptive arithmetic coding.
I understand that static arithmetic coding involves using preset probabilities of symbols that remain static during the whole process. I also understand that adaptive arithmetic coding involves change all probabilities after each symbol encountered.
However, what is the point of changing the probability after each symbol? Why wouldn't you just go through an entire file first and determine the probabilities and then do the arithmetic coding as a second pass?
Additionally, I don't understand how changing the probability of symbols impacts the compression? If we know the true probabilities of the symbols in the file we are compressing, then will it make the file smaller?


texts:
In short: What is the basic difference that allows model checking for hardware to be "easily" solvable, but makes it undecidable for software?

I guess it has to boil down to the difference between hardware being finite automata and software having the expressiveness of a Turing machine, which would basically mean that its the infinite amount of (randomly accessible, vs. that of a push-down automaton) memory that the Turing machine has available -- is this correct?


texts: Proof for optimal interval scheduling using a Greedy Approach

texts:
You are given a set of n jobs, where each job j is associated with a size
  s(how much time it takes to process the job) and a weight w(how important the
  job is). Suppose you have only one machine that can process one unit of jobs per
  time slot. Assume all jobs are given at time t = 0 and are to be processed one by one using this machine. Let C > to be the time that job j is completed. The goal is
  to find a schedule (of all the jobs) that minimizes the weighted completion time, i.Σ(j=1 to n) wj * CjApproach 1: Process Jobs according to the highest weight firstApproach 2: Process jobs in ascending order of their sizeApproach 3: Process jobs in descending order of their density (w/s)

So basically, I need to find out which approach is optimal and why the other 2 wouldn't work. My understanding is as follows:Approach 1 wouldn't be optimal if the higher weights(w) have a greater size(s).Approach 3 wouldn't work if the weight was equal to the size in case of all the jobs. If w=s for all the jobs, you wouldn't be able to determine what to chose first.Hence, my answer is that Approach 2 would be the optimal choice out of the 3 as it focuses on minimizing w*c. Is this answer correct? Is there a better way to prove why approach 2 is the optimal choice in this question?


texts:
I need to describe an algorithm that finds a maximum matching in a given undirected and unweighted graph. The runtime needs to be linear and is a 2-approximation, that is, the matching size (number of edges) should differ from a maximum matching size not more than a factor of two.

The problem I have is coming up with a linear-time algorithm. I know how to find a maximum matching, but this takes polynomial time.


texts: Big-Endian/Little-Endian argument - paper by Danny Cohen

texts:
Reading a book I was redirected to "On holy wars and a plea for peace" paper by Danny Cohen, which covers the "holy war" between big-endians and little-endians considering byte-order.

Reaching the summary of the memory section I got confused as the author sais:

  To  the best of my knowledge only the Big-Endians of Blefuscu have
  built systems with a consistent order  which  works  across
  chunk-boundaries, registers,   instructions   and   memories.      I
  failed  to  find  a Little-Endians' system which is totally
  consistent.

Which kind of contradicts his previous text sections covering little-endian:

e.g.

  When they add the bit order and the byte order they get:

               ...|---word2---|---word1---|---word0---|
              ....|C3,C2,C1,C0|C3,C2,C1,C0|C3,C2,C1,C0|
             .....|B31......B0|B31......B0|B31......B0|

  In  this regime, when word W(n) is shifted right, its LSB moves into
  the MSB of word W(n-1).
                                     4

  English  text  strings  are  stored  in  the  same order, with the
  first character in C0 of W0, the next in C1 of W0, and so on.

  This order is very consistent with itself, with the Hebrew language,
  and (more importantly) with mathematics, because significance
  increases with increasing item numbers (address).

he even lateron sais:

  The  Big-Endians struck again, and without any resistance got their
  way. The decimal number 12345678 is stored in the VAX memory in this
  order:

                       7 8  5 6  3 4  1 2
                  ...|-------long0-------|
                 ....|--word1--|--word0--|
                .....|-C1-|-C0-|-C1-|-C0-|
               ......|B15....B0|B15....B0|

  This ugliness cannot be hidden even by the standard Chinese trick.

How did the author get to this completely different conclusion on overall consistency?

An answer does not have to only base on the text, but may also include other sources which might clear up how the statement is sound.


texts:
Are there any types of distributed databases which allows untrusted peers, like Blockchain?
If it exist, can I look its whitepapers and/or implementations?


texts: Listing all prime numbers less than an integer N

texts:
I am trying to solve this problem listing all prime numbers less than an integer but using the smallest amount of memory.

Is it possible to solve this problem using a smaller amount of memory?

int main ()
{
    int n = 10000;
    for (int i=2; i<n; i++)
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0)
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";
            }
        }
    return 0;
}


texts: 0-1 knapsack problem with minimum and maximum weight capacity

texts:
In classical 0-1 knapsack problem we have maximum allowed value for the weight - weight capacity.

Let's restrict total knapsack weight by min and max values

$$
M \leq \sum_{i=1}^{n}{w_i x_i} \leq W
$$

Is there any known algorithm for this problem?
Is there anything known which is better than brute force?

I failed to find anything about the given knapsack problem variation.


texts: What data-structure is best suited for escape analysis?

texts: I'm making a compiler using LLVM and LLVM's shadow-stack. I thought I might easy the load of the GC by using escape analysis and allocate some variables on the stack. Can I use my typed AST for this algorithm, or must I use a graph data-structure?


texts: Prove $T(n) = T(\left \lceil{\frac{n}{2}}\right \rceil) + 1 = O(\log(n))$

texts:
As the title said, prove $T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1 = O(\log(n))$
My approach is to find $c, n_0 \in \mathbb{R}_+$ such that:
$$\forall n \geq n_0, T(n) \leq c\log(n) -d \text{, where d is a constant}$$
Assume the statement is true for every $m < n$, especially $m = \left\lceil{\frac{n}{2}}\right\rceil$, therefore
$$T(\left\lceil{\frac{n}{2}}\right\rceil) \leq c \log(\left\lceil{\frac{n}{2}}\right\rceil) - d $$
$$\iff T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1$$
$$\leq c\log(\left\lceil{\frac{n}{2}}\right\rceil) - d + 1$$
$$= c\log(\left\lfloor{\frac{n}{2}}\right\rfloor + 1) - d + 1$$
$$\leq c\log(\frac{n + 2}{2}) - d + 1$$
$$= c\log(n + 2) - c\log(2) - d + 1$$
$$= c\log(n + 2) - d$$
This is where I stuck and can not go further. I need to eliminate the constant $2$ in $n + 2$. Any help and hint is welcome.
Edit: In term of master theorem. I have to solve this recurrence with substitution method.


texts: Why, really, is the Halting Problem so important?

texts:
I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine with finite memory will either halt or repeat a previous state. You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1).
It seems to me that the Halting Problem proof is nothing more than a so-called "paradox," a self-referencing contradiction in the same way as the Liar's paradox. The only conclusion it makes is that the Halting Function is susceptible to such malformed questions.
So, excluding paradoxical programs, the Halting Function is decidable. So why do we hold it as evidence of the contrary?
4 years later: When I wrote this, I had just watched this video (update: the video has been taken down). A programmer gets some programs, must determine which ones terminate, and the video goes on to explain that it's impossible. I was frustrated, because I knew that given some arbitrary programs, there was some possibility the protagonist could prove whether they terminated. I knew many real-life algorithms had already been formally proven to terminate. The concept of generality was lost somehow. It's the difference between saying "some programs cannot be proven to terminate," and, "no program can be proven to terminate." The failure to make this distinction, by every single reference I found online, was how I came to the title for this question. For this reason, I really appreciate the answer that redefines the halting function as ternary instead of boolean.


texts: Space and time complexity of balanced parentheses enumeration algorithm

texts:
Consider the following recursive algorithm for printing all balanced strings with $n$ left and right parentheses. It is called with prefix = $\epsilon$ (the empty string):

A(prefix):

If prefix contains $n$ right parens: print prefix and return.
If prefix contains more left parens than right parens: call A(prefix + ")").
If prefix contains less than $n$ left parens: call A(prefix + "(").

As an optimization, instead of counting the number of left and right parens at each step of the recursion, we carry them around (so A gets two more parameters, which are the number of parens of teach type in prefix).

For example, when $n = 3$, this outputs the following strings:

   ()()()
   ()(())
   (())()
   (()())
   ((()))


texts: Remove range of keys from Binary Search Tree in O(s+h)

texts:
I have a binary search tree with integer keys. I have to remove a range (m, n]eZ of keys from the BST in O(s + h)

where s is the number of keys to remove and h is the height of the tree.

Attempted solution:

The naive solution is just to find nodes in range and delete them and fix the tree one-by-one, but that doesn't meet the time complexity requirement as it would be O(s * h).

I have considered the fact that if a node is within the range and its left child is in range, all of the left child's right children are in range as well as if the right child of the node is in range, the left children of the right child are also in range. Both of these facts allow you to delete the entire subtree below those children by simply unlinking it. I'm having trouble converting this information into a useful algorithm.


texts: is size of maximum matching less than that of maximum k-parity k-set packing?

texts:
My application problem can be modeled as maximum k-parity k-set packing problem, which is NP-hard. I know that maximum matching is polynomial time, hence I want to reduce k-parity k-set packing into bipartite maximum matching. I am wondering if there is any relation between their size.

Maximum k-parity k-set packing problem: We're given a universe $U$, which is a union of $k$ disjoint sets, $ U = V_1 \cup \cdots \cup V_k$, and a family $ \mathcal{S} $ of subsets of $ U$, each $S$ contains exactly one vertex
from each set, i.e., $S \in V_1 \times \cdots \times V_k$. A packing is a subfamily ${\mathcal {C}} \subseteq {\mathcal {S}}  $ of sets such that all sets in  ${\mathcal{C}}$ are pairwise disjoint.  The size of that packing is  $|{\mathcal  {C}}|$. We are looking for the maximum-size packing.

In order to take advantage of polynomial time maximum matching we reduce $U$ to $U' = V_i \times V_j, i , j = 1, \cdots, k$ and $\mathcal{S}'$ be a family of subsets of $U$ such that each $S'$ contains exactly one vertex from $V_i$ and $V_j$. Let $d_{i,j}$ be the size of maximum matching and $d = \min_{i,j} \{d_{i,j} \}$.

For example in the figure below: $|C| = 2, d_{2,3} = d_{1,2} = d_{1,3} = 2$ hence $d = \min(2,2,2) = 2$.

My question: is this inequality true
$|{\mathcal  {C}}| \le d \le k \times |{\mathcal  {C}}|$ ?

I think $|{\mathcal  {C}}| \le d$ is obvious, do we also have $ d \le k \times |{\mathcal  {C}}|$?


texts: Algorithm to find min pos difference between two integers in an array

texts:
The question I'm faced with:

  Let $A[1], A[2], ...,A[n]$ be an array containing $n$ very large positive integers.

  Describe an efficient algorithm to find the minimum positive difference between any two integers in the array.

  What is the complexity of your algorithm? Explain.

I would assume you apply a Merge Sort or Quick Sort $\Theta(n(log (n))$ and then scan through the array, subtracting the second element from the previous element, all the way to the end? Or $n-1$ comparisons?

So the complexity would be $\Theta(n(log(n) + (n-1))$?


texts:
I was wondering if there is any technique in order to recognize similar functions behaviour. In particular, suppose that I implement two functions $f$ and $g$ in a certain programming language $P$ and for each input $i$, $f(i) = g(i)$. Moreover, the two functions $f$ and $g$ could be implemented in a completely different way, e.g. different algorithms that solve the same problem.

In my opinion, clone detection could be useful, but I cannot compare both tokens or ASTs since the implementations are completely different. A semantic comparison could be a possible solution, but are there other techniques that I can use?