texts: Finding total valid strings of length N that could be formed using characters A,B and C which satisfies given criteria

texts:
You have to find out the number of good strings of length N characters in size which you can make using characters A B and C.

A string is a good String if it satisfies the following three criteria:

The total number of C in the string should not be greater than equal to 4.
There should not be more than two consecutive A's in the string.
Any two B's should be at least two characters apart.

How do I find total possible good strings for N length string?

Any psudo code will really help. Thank you.


texts: Which of the following sequences could not be the sequences of nodes examined in a binary search tree?

texts:
Suppose that we have numbers between $1$ and $1000$ in a binary search tree and want to search for the number $363$. Which of the following sequences could not be the sequences of nodes examined

a) 924,220,911,244,898,258,362,363$

b) 925,202,911,240,912,245,363

c) 2,399,387,219,266,382,381,278,363

d) 935,278,347,621,299,392,358,363

e) 925, 202, 911, 240, 912, 245, 363

I know that $d$ and $e$ are not valid sequences, my professor told us so. I know it has something to do the range between jumping from node to node, which has something to do with the following property of BST's

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

I just don't see it, been trying to simulate the path sequence with no clear breakthrough.


texts: Using Induction to prove that $n^3log^4n=O(n^4)$

texts:
I need to prove the following asymptotic relation for the purpose of cacluating a recurrence relation:
$$n^3log^4n=O(n^4)$$
I tried and failed to do it with induction, which, if possible using basic Calculus 1 level math, I would like you to help me with.
I am not required to do it with induciton or anything, I just wondered if I can do it.

I was able to prove it though, in a differet manner:
$$f \in o(g) \Rightarrow f \in O(g)$$
$$lim_{n\to \infty} \frac{n^3log^4n}{n^4}=0$$
Using L'Hôpital's rule 4 times, which proves that:
$$n^3log^4n=o(n^4)$$
By the definitino of $o$.

Therefore it also follows that $$n^3log^4n=O(n^4)$$

For the basis of the induction let $n=1$ and with $c=1$:
$$f(1) = 1^3log^4(1) = 0 \leq 1=1^4 \cdot 1=c \cdot g(1)$$
From here I think that it would be enough to show that:
$$log^4(n) \leq n$$
Although I am not sure how to continue from here.


texts: How can Kruskal's algorithm return different spanning trees?

texts:
We assume that we have the same graph G.

In introduction to Algorithms by Cormen it's said that it`s possible depending on how it breaks ties when the edges are sorted into order.

I have trouble visualizing the answer given:

  Suppose that A is an empty set of edges. Then, make any cut that has (u, v)
  crossing it. Then, since that edge is of minimal weight, we have that (u, v) is
  a light edge of that cut, and so it is safe to add. Since we add it, then, once
  we finish constructing the tree, we have that (u, v) is contained in a minimum
  spanning tree.

What does it mean to make a cut? I`m familiar with Kruskal's algorithm but nowhere in the process do I see cuts being made. It's either we unite two trees and add the edge to A or we reject the edge and continue on.


texts: Average number of exchanges during first partition stage in Quicksort

texts:
I am trying to understand average no of exchanges in Quicksort.
Here is the code to partition the array -
 private static int partition(double[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        double v = a[lo];
        while (true) {

            // find item on lo to swap
            while (less(a[++i], v))
                if (i == hi) break;

            // find item on hi to swap
            while (less(v, a[--j]))
                if (j == lo) break;      // redundant since a[lo] acts as sentinel

            // check if pointers cross
            if (i >= j) break;

            exch(a, i, j);
        }

        // put v = a[j] into position
        exch(a, lo, j);

        // with a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
        return j;
    }

To start with in first partition stage -
There are total comparisons as below $ C_N= N +1 $
so exchanges in worst case should be  $ \frac{N}{2} - 1 $
But am not able to deduce number of exchanges in first partition
stage which is  $ \frac{(N-2)}{6} $
can someone explain how to deduce this?


texts: Packing objects into bins to minimize the number of bins

texts:
There is a list of objects. Each object cannot be in a bin with some other objects. How can I find the minimum number of bins required to hold all the objects (and the objects in them)?

My current algorithm:

For each object in the list, see if any of the currently existing bins will hold it. If yes, stick it in the first bin we come to that will hold it. If we exhaust the list of bins without finding a bin, create a new bin and stick the object into it.

Will this algorithm find the minimum number of bins? If not, what algorithm will (NP-hard algorithms OK: I have only about 12 objects)?

Feel free to add any tags you think appropriate - I'm not sure which one is


texts: Proving that $f(n) = o(g(n))$ implies $2^{f(n)} = o(2^{g(n)})$

texts:
I can't find a counterexample to
$$f(n) = o(g(n)) \text{ implies } 2^{f(n)} = o(2^{g(n)})\,,$$
but I do not know a formal way of proving it. Can anyone lead me in the right direction? I asked this exact question yesterday in Stack Overflow by accident (meant to post here) but no one could come up with a valid way of approaching this question.

This is "little-$o$" notation by the way. So a strict upper bound
It should be for monotonically increasing functions


texts:
Show that the following formula is a law of
LTL, i. e. the formula is satisfied on all paths in all models

 G(p → X q) ∧ G(q → F p) ∧ p → G F p

I dont know how to go about that. Whats the standard procedure to go about checking the satisfiability of all  paths in all models for a given LTL formulae?


texts:
I'm currently studying for my algorithms final and I came across a practice problem that I can't seem to figure out. Here's the problem:

  Consider the following set of difference constraints:

x1 - x4 <= 1
x2 - x1 <= 2
x2 - x4 <= 0
x3 - x1 <= 1
x4 - x1 <= -1
x4 - x3 <= -2

  What is the solution that will be provided by the shortest path based algorithm for this set of constraints?

I know that you are supposed to create a graph using these constraints, so that there is one edge per constraint and one node per variable. So, for this problem, there would be four nodes: x1, x2, x3, and x4. There would also be six edges because there are six constraints. The first constraint should make an edge from x4 to x1 with a weight of 1. The second constraint should make an edge from x1 to x2 with a weight of 2. The rest of the constraints are made into edges following the same pattern.

So after you create the graph, you're supposed to run a shortest path algorithm on it, and it somehow gives you the values for each variable. This is the part that I am unsure about.

The answer that I got when I did this was that x1 = 0, x2 = -1, x3 = 0, and x4 = -2. Unfortunately, this doesn't work because of the first and third constraints.

Can someone walk me through how to get the right answer using the shortest path based algorithm for this question? Thanks!


texts: Howto formally go about proving that two LTL formulas are equivalent?

texts:
Do they need to "unwind" exactly to the same set of paths or does it suffice when one set is contained in the other ?

Or is it sufficient to argue that M,s satisfies both LTL formulas for any starting s and a model M, that is, reaching with both at "true" ?

Generally.

Let $M$ be any model. Further, let $s$ be any state $M$ might be in.

Let $\phi$ and $\psi$ be two LTL formulas.

If $\forall$ paths $\pi$ in $M$ starting at $s$ it holds that $\pi \models \phi \leftrightarrow \pi \models \psi $ then we say  $\phi$ and $\psi$ are equivalent ($\phi \equiv \psi$).

More succinct

$(\pi \models \phi \leftrightarrow \pi \models \psi) \rightarrow (\phi \equiv \psi)$.

Example. Prove that $\neg G \chi \equiv F \neg \chi$.

If we can show that $(\pi \models \neg G \chi \leftrightarrow \pi \models F \neg \chi)$ we would have proven that $(\neg G \chi \equiv F \neg \chi)$. So we reduce to the former.

Step 1. We show that $(\pi \models \neg G \chi \rightarrow \pi \models F \neg \chi)$:

$\{(\pi \models \neg G \chi) \leftrightarrow (\pi \not\models G \chi) \leftrightarrow (\forall i \geq 1, i \in \mathbb{N}. \pi^i \not\models \chi)\} \rightarrow \{(\exists i \geq 1, i \in \mathbb{N}. \pi^i \not\models \chi) \leftrightarrow (\exists i \geq 1, i \in \mathbb{N}. \pi^i \models \neg\chi) \leftrightarrow (\pi \models F \neg \chi)\}.$

Step 2. We show that $(\pi \models F \neg \chi  \rightarrow \pi \models \neg G \chi)$:

$\{(\pi \models F \neg \chi) \leftrightarrow (\exists i \geq 1, i \in \mathbb{N}. \pi^i \models \neg\chi) \leftrightarrow (\exists i \geq 1, i \in \mathbb{N}. \pi^i \not\models \chi)\} \rightarrow \{?\}.$ How do I get back?

Ok. I can semantically understand that if for every model and any path in it, it is true eventually that $\neg \chi$ holds, it cannot be the case that generally for every model and any path in it $\chi$ will hold. How can I write this down formally?

Would for $\{?\}$: $\{\neg (\forall i \geq 1, i \in \mathbb{N}. \pi^i \models \chi) \leftrightarrow (\neg (\pi \models G \chi)) \leftrightarrow (\pi \not\models G \chi) \leftrightarrow (\pi \models \neg G \chi)\}$ be a valid argumentation ? It looks different than Step 1. and anyway is there a rule to pull $\neg$ "out" from $\not\models$ this way ?


texts:
I have a set of coordinates, in practice gps coordinates.
Some of them are in clusters and some of them are scattered. Which are which is allready determined. Thus I know which ones are in a particular group and which are not.

The ones in a cluster I want to graphically mark as a group by drawing an outline around them similar to this image.

Is this a problem that can be solved by any well know algorithm?


texts:
I am debugging an FFT.  My FFT uses complex numbers in polar form, $(r,\theta)$.

I am trying to establish that it works, with a unit test.  My real values are all correct, after a polynomial multiplication...

However, I pad out my polynomials to a power of two with complex zeros, and when the multiplication is complete, I have random angle values in the polar form of the complex numbers.

For instance, I multiply the following polynomials, listed in standard form by their coefficients:

$$
A = \lbrace1,2,3\rbrace\\
B = \lbrace4,5,6\rbrace\\
$$

And I am expecting the answer to be:
$$
C = \lbrace (4,0),(13,0),(28,0),(27,0),(18,0),(0,0),(0,0),(0,0)\rbrace
$$

However, my FFT returns this exactly (ignoring floating point errors), except the last three terms are:

$$
C = \lbrace \ldots,(0,4.518),(0,0.4769),(0,2.2877)\rbrace
$$

My question is whether these angle values in the extra terms are expected, or whether this is a sign of something going wrong in my FFT code?

(this is tricky for me, because it seems like everything is calculating correctly; and shouldn't it not work at all in a d&c if something is wrong?)


texts: How to write a closed term with this type?

texts:
X→Y →(X+Y)×Y

I'm confused about how to get the type (X + Y).
If I assume m: (X + Y), n: X, k: Y
then I can get $${m:X+Y \vdash \lambda n:X.\lambda k:Y.<m, k>}$$
which get the right type. But I can't reduce the context m: X + Y.
So, could anyone tell me how to make it? Thanks a lot.


texts: How to generate an instance for an NP_hard proof, where each element has two inputs?

texts:
I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (ECP). So we have:

(ECP): Let $X = \{x_1, x_2, \dots, x_{2n}\}$ be a set of positive integers, does there exist a partition of $X$ into two subsets $X_1$ and $X_2$, such that $\sum_{x_i \in X_1}x_i = \sum_{x_i \in X_2}x_i = B$, where $B$ is a positive integer, and such that $|X_1|=|X_2|$?

The inputs for my scheduling problem are a set of $n$ jobs, where each job has a processing time $p_i$ and a due date $d_i$. So, my instance has jobs where processing times are linked to the integers from the Partition problem, i.e. $p_i=x_i$.

The issue that I have is this:
If I assign a common due date for all jobs, i.e. $d_i=d$, then the problem is not NP-hard. So, how I can generate the instance with non-equal due dates? For example, can I use the same integers $x_i$ for the due dates (e.g. $d_i=B-x_i$)? Is it Ok if I use the job id ($i$) in the due dates (e.g. $d_i=B-2i^2$)?

p.s. I realized that I cannot use the $x_i$ of one job in the due date of another job, as then those jobs will be related to each other thai is not correct. Actually, that makes even very simple problems to be NP-hard.


texts: How to compute function rolling averages maximum for each possible interval length?

texts:
I'm searching for a fast way to calculate

$$ g(k):=\max_{0<i<T-k} {\frac{1}{k} \sum_{j=i}^{i+k} f(j)}$$

for $ 0<k \le T $ given some discrete function $f$ defined on $ [0; T]$.

Is there algorithm to do it faster then naive $O(n^2)$? If so, how?


texts: Conversion from nondeterministic PDA to deterministic PDA

texts: Why is the conversion from nondeterministic PDA to deterministic PDA not possible?


texts: Quicksort $T(n)_{best}=\Omega(n\log n) $ proof

texts:
About the proof that quicksort has $T(n)_{best}=\Omega(n\log n)$.

I can't find this specific aspect anywhere online which is strange. I'm going through a proof for this in a book and I don't understand something, it says that about analyzing the "cost" of a level in the recursion tree that:

  Since the recurrence relation for quicksort is: $T_{best}=
 T(i-1)+T(n-i) + n$, then the cost of the root is $n$, and the cost of
  the level below it is $n-1$, in general: if a level has $x$ vertices,
  then the cost of the next level is smaller by $x$.

How is that possible? It's easy to see that each complete level has a total cost of $n$.

Also about the first level, if we plug $i=1$ to the equation, we indeed see that one recursive call (say left) leaves a "cost" of $n-1$ but the second call (say right) has a cost of $1$ so the total for the first level is $n$ and not $n-1$..

  The proof then goes on to say that level $i-1$ has at most $2^{i-1}$
  vertices, therefore the cost of level $i$ is at least
  $n-(1+2+...2^{i-1}) > n- 2^{i}$, therefore the cost of each of the
  $\log n $ levels is $\Omega (n)$.

Does anyone understand the part that I'm asking about?

Alternatively, is there a proper rigorous proof for this somewhere online?


texts: Finding a closed form for a discrete sum using generating functions

texts:
Consider this sum: for context sake, the summand appears in the counting of the possible ways to have one cigarette box empty and the other having left N cigarettes when both boxes start with N cigarettes in the Banach cigarette problem ; so there is a combinatorial explanation which I do not consider here.

$$ \sum_{i=0}^{N} \binom{2N-i}{N} 2^i = 2^{2N} $$

I wish to know how one would go about finding this closed form using generating functions. More precisely, how would you evaluate

$$ \sum_{N \geq i} \binom{2N-i}{N} x^N $$

Thanks!


texts:
I found this problem in a book. It supposedly minimizes the number of Support vectors rather than maximizing the margin:

$min_{\alpha,b} \frac{1}{2}\sum_{i=1}^{m}\alpha_{i}^{2}$
$s.t.\quad y_{i}(\sum_{j=1}^m\alpha_{j}y_{j}(x_{i}\cdot x_{j})+b)\ge1 \quad \forall i\in \{1,...m\}$

(for simplicity, I've omitted the slack variables - let's assume the problem is linearly sperable.)

I don't understand how this was derived. we get $w=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i}$ from the regular lagrangian for the SVM problem, in which $w$ is squared - thus, when we derive by $w$ and equate to 0, we get the formula for $w$. But here, $w$ is already replaced with the same expression. It makes sense - we still want to express the seperator as some combination of the input vectors. But how do you get this mathematically for this different problem?

Also, I understand that using l1 norm for $\alpha_{i}$ should make the number of support vectors even lower. how come?


texts: Could I simulate the implementation of memory components

texts:
I am currently reading the IEEE paper A Memory-Efficient Parallel String Matching
Architecture for High-Speed Intrusion Detection by Kai Zheng,  Bin Liu,  Xin Zhang, and  Yunhao Liu.

In the paper they propose a model for
 a memory-efficient multiple-character-approaching architecture
consisting of multiple parallel DFAs.

I have read the paper and I have understood to an extent.

But when I think of implementation, could I simulate the SRAM, LE,BCAM etc.. as in the case of a network simulator (NS-2,OPNET,OMNET).


texts: State-elimination on FSA, after epsilon-removal construction

texts:
I want to define the language of this FSA with a regular expression. I have learned that by state-elimination, I would be able to find a regular expression.

But there are already some epsilon transitions in this FSA.

My question is:

Should I first follow the epsilon-removal construction, and then do state elimination?

Or can I use state-elimination directly on this FSA?


texts: Breadth First Search actually require specifically Queue instead of any other type of Collection?

texts:
As far as I know, Breadth-First-Search [BFS] theory traditionally requires a Queue to process a given level of a graph (i.e: wiki seems to assume so).

But does BFS really actually require a Queue, rather than just any type of Collection?

A Queue is a Collection
A Set is also a Collection, for example

Wiki states that BFS...

  "explores all of the neighbor nodes at the present depth prior to
  moving on to the nodes at the next depth level."

What about that quote requires specifically a Queue?  Why would BFS not work if implemented with any other type of Collection besides a Queue?

It seems to me that as long as any Collection is used to explore "all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level", by storing such neighbor nodes in that Collection and ensuring the entire Collection is emptied (or otherwise completely processed or explored) before moving on to the next depth level, then the level-ordering requirement of BFS is achieved?

I understand that a Queue would ensure a certain order (i.e: left-to-right) while processing/exploring within a given level; but is that ordering within a given level really necessary such that the algorithm still meet the requirements of BFS?  Otherwise why is order within a given level actually necessary?


texts: Probability of string misidentified in Bloom filter

texts:
I'm attempting a question related to Bloom filters:

  Our Bloom filter uses $3$ different independent hash functions $H_1, H_2, H_3$ that each take any string as input and each return an index into a bit-array of length $n$. Each index is equally likely for each hash function.

  To add a string into the set, feed it to each of the $3$ hash functions to get $3$ array positions. Set the bits at all these positions to $1$. For example, initially all values in the bit-array are zero. In this example $n = 10$:

Index: 0 1 2 3 4 5 6 7 8 9
Value: 0 0 0 0 0 0 0 0 0 0

  After adding the string "word", where $H_1($"word"$)=4$, $H_2($"word"$)=7$ and $H_3($"word"$)=8$:

Index: 0 1 2 3 4 5 6 7 8 9
Value: 0 0 0 0 1 0 0 1 1 0

  Bits are never switched back to $0$. Consider a Bloom filter with $n=9000$ buckets. You have added $m=1000$ strings to the filter.

  a) What is the probability that the first bucket has $0$ strings hashed to it?

  b) To check whether a string is in the set, feed it to each of the $3$ hash functions to get $3$ array positions. If any of the bits at these positions is $0$, the element is not in the set. If all bits at these positions are $1$, the string may be in the set; but it could be that those bits are $1$ because some of the other strings hashed to the same values. You may assume that the value of one bucket is independent of the value of all others.

  What is the probability that a string which has not previously been added to the set will be misidentified as in the set. That is, what is the probability that the bits at all of its hash positions are already $1$?

For the first part, probability that a certain string is not hashed by $H_1$ to first bucket is $8999/9000$. Probability that that string isn't hashed by any of the $3$ functions is therefore $(8999/9000)^3$. Probability that none of the strings is hashed by any of the hashing functions to the first bucket is then $(8999/9000)^{3000}$.

I hope so far I'm going on the right track. I'm completely confused by the second part though. Am I supposed to use some specific probability distribution for this?

Edit: after Yuval's comment, here's an attempt at the second part:
We're supposed to find the probability that $3$ specific buckets (say buckets no. $p,q,r$) already have a string hashed to them. This is

$$P(p=1,q=1,r=1)=1-P((p=0)\cup(q=0)\cup(r=0))$$

The union can be calculated as (denoting events $p=0, q=0, r=0$ as $p_0, q_0, r_0$ respectively)

$$P(p_0\cup q_0\cup r_0)=\\P(p_0)+P(q_0)+P(r_0)-P(p_0,q_0)-P(q_0,r_0)-P(r_0,p_0)+P(p_0,q_0,r_0)$$

$P(p_0),P(q_0),P(r_0)$ will be the same as the answer to the first question. $P(p_0,q_0)$ will be (using similar logic as in part a) $\big(\frac{8998}{9000}\big)^{3000}$. $P(p_0,q_0,r_0)$ will be $\big(\frac{8997}{9000}\big)^{3000}$. Plugging all these values in, we get the answer.

Is this okay?


texts: Relation between space and time complexity for machines with write once read many (WORM) memory

texts:
While thinking about different calculi for predicate logic (like natural deduction and sequent calculus), I noticed that these calculi are (often) presented in a form suitable for "human computers". A "human computer" is limited to use write once read many (WORM) memory when processing large amounts of data. Pure functional programming also seems to favor a WORM memory model. In fact, it seems to me that the WORM memory model is so natural that classifying it as unconventional computing might underestimate its importance. (Understanding the strengths and limitations of the computing resources available to humans is important.)

What is known about the relation between space and time complexity for machines with WORM memory? What are the keywords to google for available material related to these questions? Do we known whether the time complexity will remain the same, if a small (for example C*log(WORM memory)^n) amount of normal memory is added?


texts: Efficient algorithm to enumerate all simple directed graphs with n vertices

texts:
I'm actually writing a piece of code to try and test various conjectures on directed graphs, and when possible, find a minimal counter example to the conjecture being tested.

For that, I need to enumerate all possible simple directed graphs D=(V,A) (simple in the sense that multiple arcs, 2-cycles, or (u, u) arcs are not allowed).

I have for the moment a naive method, which consists in building all the possible functions

F: S --> {-1, 0, 1} where S = {(u, v) in VxV such that u > v} and V is the vertex set.

Then, F(u, v) = 1 <==> (u, v) in A, F(u, v) = -1 <==> (v, u) in A, and F(u, v) = 0 <==> (u, v) not in A and (v, u) not in A.

There are 3^(n(n-1)/2) (n the number of vertices) such functions, and I'm pretty sure that this is a much bigger number than the actual number of unlabeled simple directed graphs.

This does enumerate all labeled directed graphs, but it's an overkill because I do not care about labels, so ultimately I generate way too many graphs, and test conjectures several times on graphs that are similar (their only difference is the vertex labels).

My question is: is there a simple algorithm to enumerate unlabeled simple directed graphs ?

And since I'm confident such an algorithm exists, a quick description would be very welcome.


texts: How to find all the contiguous subsequence of an array is less than O(N^2) time complexity?

texts:
I am unable to find product of every contiguous subsequence of an array in less than O(N^2) time complexity.

What actually i want to do is find the number of contagious subsequence whose product of elements is either odd or multiple of 4. The problem here is time i want an algorithm which can make it happen in O(N).

public class PrintAllSubArrays {

    public void printSubArrays(int [] arrA){

        int arrSize = arrA.length;
        //start point
        for (int startPoint = 0; startPoint <arrSize ; startPoint++) {
            //group sizes
            for (int grps = startPoint; grps <=arrSize ; grps++) {
                //if start point = 1 then
                //grp size = 1 , print 1
                //grp size = 2, print 1 2
                //grp size = 3, print 1 2 3 ans so on
                for (int j = startPoint ; j < grps ; j++) {
                    System.out.print(arrA[j] + " ");
                }
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        int [] arrA = {1,2,3, 4};
        new PrintAllSubArrays().printSubArrays(arrA);
    }

}

This question is part of a problem from a finished programming contest: "Squared Subsequences" (April 2020)


texts: When talking about the length of a path in a graph, what exactly is a skip?

texts:
I'm studying for a final and when looking for the shortest path in a graph from one vertex to another, what is meant by k-skips?

One website defines it as the ability to change the weight of one edge to zero, as if you don't include it in the path distance.

Another one defines it as:

  $P*$ is a k-skip shortest path from s to t, if it includes at least a vertex out of every k consecutive vertices in P

Which I can't seem to understand. I would appreciate some clarification in the matter.


texts: Understanding commutativity and associativity for primitive types

texts:
In Elements of Programming Interviews, authors talk about a tip for understanding how to use primitive types (int, double, etc).

  Be aware that commutativity and associativity can be used to perform operations in parallel and reorder operations.

I'm having trouble even imagining what these means in the context of bits. For anyone who better grasps what this means, could you explain it and flesh it out with some examples?


texts: Similarities between Babbage's difference engine and the Turing machine

texts: What would you consider similarities between the difference engine and the Turing machine? At this point I feel I know how they both function, yet I can't point out any worthwhile similarities between the two. And how do these two relate to modern phones? Other than the first two being milestones of computational science. I have this task as an assignment.


texts: Fuzzy, nonsequential string search algorithm?

texts:
Is there an algorithm that can find p + stuff within t, where stuff is any set of characters, not just HTML markup?

Sample text to search (t):

some HTML markup Some text and more text
and
some more
 text in addition to more unknown text

Sample pattern to find (p):

Some text and more text and some more text

Is there an existing algorithm that can find p + stuff within t,

That is, the algorithm should return:

Some text and more text
and some more
 text

given an unknown set of HTML/other markup and characters? The best I can describe this is . in regular expressions, any number of characters.

It sounds like Levenschtein distance is sort of what I'm looking for, but I haven't seen (or figured out) a way to use it in this way.

My current algorithm recursively tracks start and end indices, eventually narrowing t down to p + stuff, but I think it could be more efficient. The algorithm is also only best match since the set of stuff is unknown. I'm using a lot of regular expressions to estimate what could be in t. Maybe it's better to use an algorithm that works by-character instead of word?


texts:
A) Let $L$ be a regular language. according to the theorem there is an DFA which accepts the language.

Describe shortly how to change the DFA to NFA which Accepts $L^R$, where R is reverse.

There is no need to write how to build formally or proof or correctness.

B) True or False: if $L$ is not regular then $L^R$ is not regular

My solution:

A) First of all because we want Reverse the accepting state would become the start and the rejecting states will become accepting, also change the direction of the edges to the oppositse side.
but when it comes to changing it to NFA im a bit stuck.

B) I think its true since it doesnt matter if it reversed if its regular then of course $L^R$ will be regular as well.

Is this the way for A and B?


texts: In pipelining (at least, in MIPS), why is the incremented program counter address saved in the IF/ID pipeline register?

texts:
In D. Paterson's book, Computer Organization and Design, Fifth Edition, there is a paragraph that says

  Instruction fetch: The top portion of Figure 4.36 shows the
  instruction being read from memory using the address in the PC and
  then being placed in the IF/ID pipeline register. The PC address is
  incremented by 4 and then written back into the PC to be ready for the
  next clock cycle. This incremented address is also saved in the IF/ID
  pipeline register in case it is needed later for an instruction, such
  as beq. The computer cannot know which type of instruction is being
  fetched, so it must prepare for any instruction, passing potentially
  needed information down the pipeline.

I'm trying to understand why an incremented address must be saved in the IF/ID pipeline register, at least in MIPS. I understand that it might be needed by some instruction somewhere later.

However, how does an instruction such as beq use the program counter value?


texts:
Another question is about the reasons for calling P/poly "P/poly".  My question is instead about its (verbal) syntax rather than its compositional semantics:

How is "P/poly" pronounced (in English)?

Like "p polly"?
Like "p slash polly"?
Like "p given polly"? (Maybe the slash for advice is analogous to slash or vertical bar for conditional probability: $\mathsf{P}(A/B)$.)

I hope it's OK to ask such a trivial question.  I'd rather not develop a bad habit during self study.


texts: How to enhance my skills as a programmer

texts:
I want to learn Cryptography and so I am interested to master C-programming.

I know the basic concepts of C-programming  like how to use an array,pointers etc.

I want to develop myself so that I can find the different loopholes in the security of different cryptosystems.

Basically I want to work in Attacking of Cryptosystems apart from developing my skills in theory.

Will someone suggest me some goods or a list of books(say) which are just above the beginner's level and which will establish me as a good programmer?

I will be extremely thankful if someone could help.


texts: How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$

texts:
I'm not very certain about how to deal with asymptotics when they are in the denominator. For $$O\left(\frac{n^2}{\log{\frac{n(n+1)}{2}}}\right)$$, my intuition tells me that it should be treated in a similar way as little o. Would that be correct?

Also, is this in any way comparable with $O(n)$ or $O(n^2)$?


texts: Local type argument synthesis when type variable does not appear in arguments

texts:
I am implementing the techniques described in the classic Local Type Inference paper. Specifically, I am implementing the type argument synthesis algorithm from section 3.

My algorithm seems to mostly work, but it doesn’t seem to produce reasonable results when a quantified type variable appears in the result of a function, but not in its arguments. For context, I’ve reproduced the $\text{App-InfAlg}$ rule here:

$$
\dfrac{\begin{align}\tt\Gamma \vdash f \in All(\overline{X}) \overline{T} \rightarrow R \qquad &\tt \Gamma \vdash \overline{e} \in \overline{S} \qquad \lvert\overline{X}\rvert > 0\\
\tt\emptyset \vdash_\overline{X}\overline{S} <: \overline{T} \Rightarrow \overline{C}&\qquad\tt \sigma \in \bigwedge \overline{C} \Downarrow R
\end{align}}
{\tt\Gamma \vdash f(\overline{e}) \in \sigma R \Rightarrow f[\sigma \overline{X}](\overline{e})}
(\text{App-InfAlg})
$$

The most important piece here is the $\tt\emptyset \vdash_\overline{X}\overline{S} <: \overline{T} \Rightarrow \overline{C}$ premise, which invokes the constraint generation algorithm. Importantly, though, it only generates constraints using $\tt\overline{S}$ and $\tt\overline{T}$, which correspond to the argument types (that is, the types to the left of the arrow). This is problematic for types like this, which include type variables that only appear in the result:

$$
\tt All(X, Y)(X) \rightarrow Y
$$

Or, even more simply:

$$
\tt All(X)() \rightarrow X
$$

In this case, my implementation happily infers the type of the above two functions to be $\tt Y$ and $\tt X$, respectively, which are clearly not valid types, since they are type variables that have escaped their scope!

My guess is that my implementation is wrong, and the algorithm accounts for this case. In that situation, I would expect the algorithm to either reject the applications or infer $\tt Bot$ as the result type. However, I don’t see how this could possibly be accounted for, since the algorithmic inference rule only uses $\tt R$ for the purposes of turning the constraints $\overline{C}$ into the substitution set $\sigma$.

How does the algorithm handle this situation?


texts: Solving the part-of-speech tagging problem with HMM

texts:
There is a famous part-of-speech tagging problem in Natural Language Processing. The popular solution is to use Hidden Markov Models.

So that, given the sentence $x_1 \dots x_n$ we want to find the sequence of POS tags $y_1 \dots y_n$ such that $y_1 \dots y_n = \arg\max_{y_1 \dots y_n}p(Y,X)$.

By Bayes Theorem, $P(X,Y)=P(Y)P(X \mid Y)$.

Solving POS by HMM implies the assumptions: $p(y_i \mid y_{i-1})$ and $p(x_i \mid y_i)$.

The question is there are any particular reason why we prefere to solve it by generative model with a lot of assumption and not directly by estimating $P(Y \mid X)$, given the training corpus it's still possible to estimate $p(y_i \mid x_i)$.

The second question, even when we convinced that the generative model is preferred why to calculate is as $P(Y,X)=P(Y)P(X \mid Y)$ and not $P(X,Y)=P(X)P(Y \mid X)$. In case we have an appropriate generative story I can use $P(X,Y)=P(X)P(Y \mid X)$ as well, is it mentioned somewhere that assumed generative story is preferred.


texts:
If you observe the results of many image segmentation algorithms, you can notice the occurrence of region borders where a human observer wouldn't draw one, for instance across slow gradient/textured areas. This seems to be a universal phenomenon.

I have annotated the image below with yellow arrows to show what I am thinking about.

My question is twofold: is there a fundamental reason why these occur ? How can we detect such lines ?


texts: How to compute (x MOD y) with just SUM and MULT gates?

texts:
It is known that $\{ SUM, MULT \}$ is Turing-complete, i.e. every Turing machine has an equivalent circuit made up of $SUM$ and $MULT$ gates.

By the way, I could not come up with designing $MOD$ function with $SUM$- and $MULT$-only circuit. How can one construct such a circuit?

P.S. The Turing machine is simple. Assuming $\#x\#y\#$ as the input, it suffices to go back and forth and cross $y$ of the remaining entries of $x$ as much as possible.


texts:
In the book Type Theory and Functional Programming [Thompson, S 1999] the author explains the relationship between specifications, types and proofs of functions:

The equivalent specifications can be thought of as suggesting different program development methods: using the ∃∀ form, we develop the function and its proof as separate entities, either separately or together, whilst in the ∀∃ form we extract a function from a proof, post hoc.
This analysis of specifications makes it clear that when we seek a program to meet a specification, we look for the first component of a member of an existential type; the second proves that the program meets the constraint part of the specification.

On this same topic, the commenter writes:

Specifications are in a way "more detailed" types. Or, state the other way, types are more basic specifications. Martin-Lof type theory is precisely about fusing the two ideas into one.

My question is: What is the evidence that that types are more basic specifications, and specifications are more detailed types?


texts:
I want to implement simple elevator algoirthm.

people in different floors orders the elevator and the destination floor they want to get to (so you get a {from,to} alert from different floors).

So I got a simple strightforward solution :

once elevator start going in specific direction (lets say up) it will continue doing so , and serve all request of ppl want to go up (only if at the time they were made they were from higher floor in respect to the elevator) until serving the last one. all the request will be kept in an array, so on each floor you can check if someone wants to go on the same current direction.

In addition ill save in two vars (on for up direction and one for down direction) the highest and lowest points of request - hight floor that somebody wants to go up from there , and lowest floor that sombody want to get to lower floors from there - and the elevator allways will be  travling between these two points picking all the ppl that want to go on the same direction.

Does this solution make sense/work ? is there something as simple that make more sense?

I saw some priorities queue suggestions while searching in google but didnt really understand what the need of them ..

Thanks for your feedback .


texts: Calculate Miss rate of L2 cache given global and L1 miss rates

texts:
If I have a Global miss rate of all caches of a total of 5.41% and the miss rate of a single level cache of 9.13%, how can I effectively calculate how much the second level cache miss rate need to be?

I found this where it says that the Local miss rate equals misses in a cache divided by the total number of memory accesses to this cache (Miss rate L2) and Global miss rate equals misses in a cache divided by the total
number of memory accesses generated by the CPU
(Miss Rate L1 x Miss Rate L2).

So if I divide 5.41% / 9.13% it  equals 0.5926% for my second level cache. Is this assumption correct?


texts: Is this applet implementation for the Go-Back-N ARQ protocol correct?

texts:
I was reading a textbook describing the Go-Back-N (GBN) protocol with Finite State Machines as pictured below:

$\Lambda$ just means "initial state" or "no action", depending on the context. My questions are

This is the interactive animations link to GBN https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content/interactiveanimations/go-back-n-protocol/index.html.
Let's say we are sending packet 0, packet 1 and packet 2, and packet 1 is lost beforen it arrive receiver. So when it is timeout, GBN will make sender re-send packet 1 and packet 2,
And I found an interesting thing which is,if you try the link with above scenario and you send packet 3 just before timeout occurs,this action reset the timer, because you can see the timeout is postponed(otherwise you will see packet 1,2,3 flying in screen).But according to the sender's FSM, after you send packet 3, timeout occurs immediately, then the sender will re-send packet 1 and packet 2, but it didn't happen as timeout is postponed, which
contradicts the fact that time is only get reseted when base = nextseqnum?

On the receiver's FSM, why it needs to set expectedseqnum = 1 and make a packet based on it? why we cannot set expectedseqnum = 0 as the only initialized action?


texts: Testing whether polynomial is in algebra of other polynomials

texts:
A collection $\Sigma$ of polynomials is an algebra if: (1) $\lambda f + \eta g \in \Sigma$ for any $f,g \in \Sigma, \lambda,\eta \in \mathbb{R}$ and (2) $f,g \in \Sigma$ implies $fg \in \Sigma$. We say that $P$ is in the algebra of $\{P_1,\dots,P_n\}$ if $P$ is in the smallest algebra containing $P_1,\dots,P_n$.

I was wondering if there was a way, on any computer math software, to check whether a given $P$ as in the algebra of a given collection $P_1,\dots,P_n$.

Example: take $n \ge 1$ and let $P_1 = x_1+\dots+x_n, P_2 = x_1^2+\dots+x_n^2,\dots P_n = x_1^n+\dots+x_n^n$. Then all $n$ of the following symmetric functions are in the algebra generated by $P_1,\dots,P_n$: $$x_1+\dots+x_n$$ $$x_1x_2+\dots+x_{n-1}x_n$$ $$x_1x_2x_3+\dots+x_{n-2}x_{n-1}x_n$$ $$\dots$$ $$x_1\dots x_n$$

I'd appreciate any help.


texts: Are consensus (and atomic broadcast) protocols limited by single node's resources?

texts:
The main question is the following:
When designing a system supporting atomic broadcast, can it be proved theoretically that the performance & scalability dimensions (i.e. latency, throughput, dataset size) of the system are limited by the performance of a single node?

To give an example:
A system based on partitioned-logs, like Apache Kafka, can provide ordering guarantees in a single partition, but it can't provide any ordering guarantees between different partitions. However, this gives Kafka the capability to scale to extremely large datasets. I was contemplating whether it would be possible to create a system that could provide the ordering guarantee for the whole dataset, while also allowing the dataset's size to increase in the same quasi-linear way.

My speculative answer to this is no for the following reason:
It's been proved that the atomic broadcast problem is equivalent to the consensus problem [1]. Based on the fact that the consensus problem requires an elected leader, which drives the consensus process, I concluded that the scaling capabilities of such a system is limited by the resources of a single node.

Are there any flaws in my thinking ?

[1]: https://en.wikipedia.org/wiki/Atomic_broadcast#Equivalent_to_Consensus


texts: What is the amount of programs for which we can solve the halting problem?

texts:
The halting problem is undecidable of course.
This implies that there is at least one program for which we cannot decide whether it halts or not, because theoretically, if all we know is that the halting problem is undecidable, it could still be that there is a program that can decide for every program except itself whether it halts or not.

So I am wondering, for what percentage of programs can we solve the halting problem?
That is, if we assign a Gödel number G to every program. What is the value of the limit with respect to G to infinity of:

  ${s}/n$

where s = the number of programs with Gödel number 1 to G, for which we can decide whether it halts or not.

and n = the number of programs with Gödel number 1 to G, for which we cannot decide whether it halts or not.

I am not looking for a specific answer like 75%. I am looking for an answer like: less than 0.01 % or more than 9.99%, or anything really that gives a hint at an answer.


texts: How could one construct a TLB so that not all the bits of the presented address need match to result in a hit?

texts: I was wondering besides the typical matching of all bits in the presented address to the resulting page, is there another way of doing so? what are the benefits/ cons and how would one go about doing so?


texts: Finding potential function for dynamic array

texts:
About dynamic array, doubling it's size with every element that is beying its limit:

From what I understand, the number of operations between the $n$th element and the $n+1$th  depending on if $n+1$ is $2^k + 1$ (for some $k \in \mathbb{N}$).

If so, we need to allocate a new array and copy the last n elements + the new element. From what I see, if I define a potential function $\phi(n)$ then it should be $\phi(n+1) = \phi(n/2) + n/2 + 1$

Explanation: $\phi(n/2)$ is the last time we expanded the array, $n/2$ are the next elements that were inserted to only one (the last) array, and $1$ is the current element.

However, from what I saw (wikipedia) the actual function is  $\phi(n) = 2n - N$ where $n$ is number of elements and $N$ is array length.

Either way, $\phi(n) \le 2n$, and my HW assignment was to show it is bounded by $3n$ :(

Is $3n$ a too big bound or am I missing something?
Is the $\phi$ equal to the one wiki has (I can't see how...)? how do they differ

EDIT: I now have a new notion about the answer - using the bank / accounting method. My initial array has size of 2. The assignment is to show that paying 3 for each insertion will ensure I'm never in "overdraw". I know that if I only pay 2 for each insertion, then when I insert the first 2 elements, I paid 4 and used only 2, when I insert the 3rd, I use 3 and pay only 2 (so I use 1 from the bank, which leaves only 1 there). In the 4th insertion I'll add another 1 to the bank, but in the 5th insertion I'll have to overdraw!

So, clearly $2n$ isn't enough!! which makes me think $3n$ will do.

I know what I added here might contradict my first notion, and I don't understand to actually answer this. Any help will be appreciated. Thanks

$2nd$ EDIT:

The HW assignment is to show a specific $\phi(n)$ so that $a(n) = t(n) + \phi(n) - \phi(n-1)$, where:

$a(n)$ is the amortized value of the $n$th insertion
$\phi(n)$ is the potential function
$t(n)$ is the actual value the insertion is worth ($1$ or $n+1$)

It's easy to see that, using the Wikipedia function ($\phi(n) = 2n - m$ [m is the array's size]$)$, if $t(n) == 1$ then $a(n) = t(n) + \phi(n) - \phi(n-1)$ is actually $a(n) = 1 + [(2n - m) - (2(n-1) - m)]$ which is $1 + 2 = 3$. But what about when $t(n) = n+1$?


texts: This is probably a duplicate of this question, but I need a somewhat blunter answer.  Let's say I have a polynomial time algorithm that finds an assignment that satisfies more than $\frac{7}{8}$ of the clauses of a satisfiable 3SAT instance.  Do I collect my million dollars from the Clay Institute for proving $P=NP$?


texts:
I bought a great puzzle called Icosoku. Wikipedia describes it as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-triangular snap-in tiles with black dots and 12 yellow pins for the corners. The pins are printed with the numbers from 1 to 12, and the triangular tiles have up to three dots in each of their corners. The object of the game is, for any arrangement of the pins, to choose the positions and orientations of the triangles so that the total number of dots on the five joining corners of each pin equals the number of the pin."

I created a computer program which solves this puzzle by randomly choosing any two triangular tiles and then exchanging them (giving each tile a random orientation) if and only if the total discrepency (which can be measured in various ways) between each number on the pins and the total number of dots on the five joining corners of each pin decreases. But I have found that it takes hundreds or even thousands of iterations to finally get a solution for most initial configurations. I would like my program to take less time. Any suggestions?


texts: Why is the Boolean hierarchy contained in the class $P^{NP}$?

texts: My textbook says: "The Boolean hierarchy is contained in the class $P^{NP}\subseteq\Sigma^P_2\cap\Pi^P_2$." However, it provides neither a proof nor a proof sketch nor some hint. How can I convince myself that the claim is true?


texts: What if p and q are not distinct in RSA Crypto System? What could go wrong?

texts: In RSA Crypto System we choose p and q such that they are distinct primes. Calculate n=pq and phi=(p-1)(q-1). Then e is chosen for public key (n,e) s.t. gcd(e,phi)=1


texts: Reachability games with banned vertex repetition

texts:
I have bumped into this problem while working on something model checking related and can't seem to find materials or efficient solutions for it. I couldn't even find a name for it.

We have a directed graph as our input, a starting vertex and two special vertices, the winning vertices for player A and B.

The vertices are partitioned between the two players, and starting from the starting vertex one player can move the game to another one along the edges if the current vertex belongs to them, just like in parity games or reachability games. We know that there is a path from the starting vertex to at least one of the winning vertices. The goal is to make the game reach your winning vertex, the only trick is that whatever path the game describe there can't be a repeated vertex. That is, if you would make a move that would force the gameplay to eventually repeat a vertex, you can't make that move.

It can be easly solved in 2^n n^2 where n is the graph size, but i couldn't find anything faster. I can't even prove np membership. Any ideas? :)


texts:
Consider the sequence of machine instruction given below:
\begin{array}{ll} \text{MUL} & \text{R5, R0, R1} \\  \text{DIV} & \text{R6, R2, R3} \\   \text{ADD} & \text{R7, R5, R6} \\  \text{SUB} & \text{R8, R7, R4}  \\ \end{array}
In  the above sequence, $R0$ to $R8$ are general purpose registers. In the instructions shown, the first register shows the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following $4$ stages: $(1)$ Instruction Fetch and Decode $(IF)$, $(2)$ Operand Fetch $(OF)$, $(3)$ Perform Operation $(PO)$ and $(4)$ Write back the result $(WB)$. The $IF, OF$ and $WB$ stages take $1$ clock cycle each for any instruction. The $PO$ stage takes $1$ clock cycle for $ADD$ and $SUB$ instruction, $3$ clock cycles for $MUL$ instruction and $5$ clock cycles for $DIV$ instruction. The pipelined processor uses operand forwarding from the $PO$ stage to the $OF$ stage. The number of clock cycles taken for the execution of the above sequence of instruction is _________.
I got the answer as 15 however the correct answer is 13. Am I doing something wrong or is the answer key at fault?
The link for reference: https://gateoverflow.in/8218/gate2015-2-44


texts: solving max cut problem on a huge graph (500 x 500) using Semidefinite Programming with CVXOPT

texts:
So I am learning to do SDP relaxation on graph problems, and for this max cut problem I am given a 500*500 graph, and I am using the straightforward
relaxation. $W$ is the weight matrix, $X = u u^T$ where $u$ is the original variables.

$$ \max < (I-W),X> $$
$$ s.t. X_{ii} = 1, \forall i$$
$$ X \succeq 0$$

Problem is:

The solver I am using is CVXOPT, for which I have to convert X into a REALLY long variable, and for CVXOPT I have to paraphrase the constraint into huge matrices (largest ~ 250000 * 125250, but sparse), and load them into the cvxopt.solver.sdp(), but at this line python simply gives up and crashes (jupyter notebook says the kernel has died). I have used CVXOPT's sparse matrix feature for the massive constraint matrices (cost vector must be dense), and it's still not working out.

So my question is: is there any way to work around this? I'm open to anything, rephrasing the problem, using a different solver, or maybe just write the damped newton method for log barrier method myself. I am contemplating about CVXPY, but seeing that it uses CVXOPT as one of its solvers, I don't think I want to waste my time if it's gonna come out the same, and similar reason for writing my own program.


texts: Existence of Hamiltonian cycle in a 3-regular $C_n$-free graph

texts: I know that Hamiltonian cycle problem in $3$-regular triangle-free graphs is $NP$-complete. I would like to know how far we can stretch this result. Observing that a triangle is just $C_3$ cycle, what is the longest fixed-length cycle $C_g$ such that deciding the existence of Hamiltonian cycle in $3$-regular $C_g$-free graphs is still $NP$-complete?


texts: How to show that the product of two binary numbers can be determined in AC1?

texts: I was working on a proof to determine that a product cannot be done in AC0, how can a proof that can be done in AC1?


texts: In theory, should neuromorphic computers be more efficient than traditional computers when performing logic?

texts:
There is this general sentiment about neuromorphic computers that they are simply "more efficient" than von Neuman.
I've heard a lot of talk about neuromorphic computers in the context of machine learning.
But, is there any research into performing logic and maths in general on such computers? How would one translate arithmetic, logic and algorithms and into "instructions" for a neuromorphic computer, if there are no logic structures in the hardware itself?
It is common to draw parallels with a brain in this context, so here's one: Brains are great at recognising faces and such, but I don't think I can do maths faster than an Arduino (and that thing doesn't need much energy).


texts: Longest subarray with at most two different values - Runtime complexity for a DP solution

texts:
Consider the problem of finding, for a given input array, the longest subarray with at most two different values.

For example:

Input: [3,3,3,1,2,1,1,2,3,3,4]
Ans = 5, the longest subarray would be [1,2,1,1,2].

Input: [1,2,3,2,2]
Ans = 4, the longest subarray would be [2,3,2,2].

Below is dynamic programming solution to this problem (in Python, hopefully it's easy to read) using a sliding window that holds a "valid subarray" (the subarray of elements between indices i and j always holds two values at most).

I read on e.g. LeetCode that this solution has a runtime complexity of $O(N)$ where $N$ is the length of the input array, but that's not immediately clear to me since we have two nested loops with $i$ and $j$ and $0\leq i\leq j\leq n$.

Why is the worst-case runtime complexity of this solution $O(N)$ and not $O(N^2)$?

Here's the DP solution in question with those nested loops holding a subarray between $i$ and $j$:

    def longest_subarray_holding_two_diff_values (input_array):
        ans = i = 0
        count = collections.Counter()

        for j, x in enumerate(input_array):
            count[x] += 1

            while len(count) >= 3:
                count[input_array[i]] -= 1
                if count[input_array[i]] == 0:
                    del count[input_array[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans


texts:
I'm looking for the correct terminology in regard to map (dictionary) data structure.
When I'm talking about the semantics of the values stored in map in the direction from keys to values, I'd say, for example

messages keys are mapped to message strings

When I'm using the opposite direction - describing the values first, I'd need to say something like

message strings are ??? by message keys ("being mapped by" just doesn't feel right here)


texts: What is the diffrence between a carry bit and overflow


texts:
I developed an algorithm with the following multi-variate complexity:
$$O((k^n+kn)l^{kn}),$$
where $n,k,l$ are variables.

I have very little knowledge of complexity theory, and I'm not sure whether this expression can be simplified. Since $k^n$ dominates $kn$ it seems reasonable to $O(k^nl^{kn})$. Is this correct?
Assuming $l\ge 2$, can the expression be simplified even further?


texts: How to create this pushdown transducer? (formal languages and automata)

texts:
Create a pushdown transducer that translates $a^m b^{2m}c^{m+n}$ into $b^{n-m}$, with $n\geq m \geq 0$.
How should I use the stack to remember or to compute how many characters of c to read? And how can I output $b^{n-m}$?

I have also tried to simplify the problem and firstly create a pushdown automata for $a^m b^{2m}c^m$, but I didn't succeed.

Thank you!


texts: What is the trick of "adding a huge number" for in the reduction from 3-Partition?

texts:
Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following figure.

In the $\textsf{3-Partition}$ instance, there are $n$ elements $(a_1, \cdots, a_i, \cdots, a_n)$. The target sum $t$ is $t = \frac{\sum a_i}{n/3}$.

In the reduction, $B$ is a huge (constant) number and each $a_i$ is represented by a $(B + a_i) \times (B + a_i)$ square. The blank in the rectangle will be filled by unit ($1 \times 1$) squares.

Questions:
I don't quite understand the trick of "adding a huge number $B$" in the reduction. I guess it is used to force that any packing scheme will give a solution to $\textsf{3-Partition}$. But how?

  Question 1: What is the trick of "adding a huge number" for in the reduction from $\textsf{3-Partition}$? Specifically, why does this reduction work? Why is this trick necessary, i.e., why wouldn't the reduction work if we left out $B$ (set $B=0$)?

I tried to identify the flaw of the proof of "any packing gives a 3-partition" but could not get the key point.

Actually I have also seen other reductions from $\textsf{3-Partition}$ that also use this trick. So,

  Question 2: What is the general purpose of this trick of "adding a huge number" in the reductions from $\textsf{3-Partition}$ (if there is)?

Note: This problem is from the video lecture (from 01:15:15) by Prof. Erik Demaine. I should have first checked the original paper "Packing squares into a square". However, it is not accessible to me on the Internet. If you have a copy and would like to share, you can find my mailbox in my profile. Thanks in advance.


texts: Proving that a set of operations can't generate one integer from a given one

texts:
Given two numbers, $n$ and $m$, are there some mathematical methods of deducing $m$ from $n$ using limited number of elemantary operations?

Example:  335 can be deduced from 2000 using division by 2, addition of 5 and division by 3: $((2000/2)+5)/3) = 335$.

I need to prove that 1889 can't be derived from 2019 using the following 3 operations:

$n+7$ ;
$n*2$;
$n/3$ (if divisible).

All I come up with is some sort of breadth-first search.


texts: Time complexity of a language whose alphabet has a single symbol

texts:
Consider a language $L$ such that $L \subseteq \Sigma^*$, where the cardinality of $\Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L \subseteq \{a\}^*$.

Can anything be said about the time complexity of $L$? Is it the case that $L \in P$?

I can't come up with any example of a language with a single symbol that is not in $P$.


texts: About the paper Privacy-preserving in association rule mining using an improved discrete binary artificial bee colony

texts:
I don't understand two parts in this paper:

The min notion on page 4 line 357 (equation 10d): I understand this as to find all the $M_{10}$, $M_{11}$, $M_{01}$ first and then try to minimize the expression in the brackets of equation 10d. Is it correct? Or does it mean to find the min first and then use that to compute $M_{10}$, $M_{11}$, $M_{01}$?
Figure 2 (the pseudocode of employee bee mechanism) on page 5, the condition says that $rand_{(0,1)}X_i \ge 0,5$ where $X_i$ is a vector of size $d$. I don't understand why they can compare a vector with a number. I think that they made a mistake here.

Thank you so much for helping me clearing out my confusion.


texts: Does P=NP imply polynomial solutions to #P?

texts: Is it true that $\#P$-complete problems could possibly be solved in polynomial time if P=NP? I know that even some counting problems related to polynomial time decision problems are $\#P$-complete, so even if P=NP it may not necessarily be true.  My confusion is over how we write the answer to a $\#P$-complete problem since it may be exponential in the size of the input (for example up to $2^n$ truth assignments to a SAT instance on $n$ variables).  Therefore, I cannot understand how, even if we find a fast way for computing something like the permanent of a matrix, we could still expect to write the answer in polynomial time. Am I missing something about the definition of $\#P$?


texts:
I've read that "Every problem in NP can be reduced to every NP-complete problem".
I want to know why the term "Every" is important.If we have one problem in NP that is reduced to one NP complete problem then what will be the problem.


texts: What algorithm is appropriate for a thermostat controlling the heating of a room with floor heating?

texts:
I built my own thermostat that controls the boiler heater for the radiant floor heating in my house and I would like to develop / implement a smarter temperature control algorithm. What I am specifically interested in is the ability to predict when to turn on the heating so that a certain temperature is achieved according to a schedule.

Suppose I want the temperature at 7 am to be 22 degrees Celsius. During the night I want it to be at 18C. Currently, I set the schedule up so that the heating is started at 6 am but depending on how cold it is during the night, an hour may be too little and the temperature does not rise to 22C or it may be to much and the temperature overshoots. I would like an algorithm that would automatically calculate the appropriate time at which to start heating.

I keep searching online and most results are for industrial uses and/or for heating systems that can be modulated such as electrical heaters. The heating system in my house consists of a boiler that heats the water in the floor tubing and I cannot modulate the output, I can only tell it to start or to stop via a mechanical relay that opens or closes a solenoid valve. This, I believe, renders a PID algorithm inappropriate. Fuzzy logic and just PI control may be suitable but can they be made to work with varying set points?

Supervised machine learning is overkill for my needs and I don't want to spend weeks to train it.

What other options would I have?


texts:
Till now, I always gave each db-table an id-column (generally with the table name and an underscore as a prefix, e.g. employee_id), and I also never have seen another approach to unique a db-table-record in practice. But on the other hand during my studies, I often have seen other columns that act as a primary key, for instance: an email/url as priamary key for a table user/photo.

At the moment I'm designing a database that contains a table first_name (because a human can have more than one first name).
The scheme of this table first_name:{[first_name_id:integer,first_name:string]}.
But to avoid duplicate, I would like to use the first_name as a primary key. And I also have a table employee with the column email address that also can be used as a primary key, becuase its unique.

My loss is that I dont know if I should use this approach, becuase its uncommon in practice and maybe it will cause any trouble during the programming part. So my questions is:
An ID (auto increment integer) always as primary key for each db-table?


texts: What is the height of avl tree with n nodes

texts: what is the height of avl tree with n nodes ? Can you explain it with formula ? I couldn't find any formula to solve this problem.


texts: Expressing semantics of an array as a function

texts:
An assignment questions asks the following:

  Consider an array 'var a : array[1..10] of real'.  Express the
  semantics of this array as a function, defining the domain and
  codomain (you might also be able to write the rule).  In this
  programming language, the subrange '1..10' is viewed as a genuine
  type, so we can comfortably say that 'a[13]' is a type error.

I've come up with a semantic that works as a function, that is: f(a[$x$]) -> $y$ where $x$ is a type defined by the numbers $1$ to $10$ and $y$ is the set of all Real numbers. Does this seems correct?

Would there be any difference if I wrote the function in the opposite way, that is: f($y$) -> a[$x$] ?


texts: Prove that $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive

texts:
I'm stuck on this problem:

Given $f:\mathbb{N} \rightarrow \mathbb{N}$ a partial recursive function that is also injective and total. Prove that the function $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ $$f^{-1} = \left\{\begin{array}{rcl} x & \mbox{if} & f(x) = y \\ \uparrow & \mbox{otherwise}\end{array}\right.$$ is partial recursive.

So to prove that a function is partial recursive I have to show that I can build it from basic recursive functions (successor, projection and constant) by applying composition, primitive recursion and then minimization.

I don't know what form $f$ has, but I think I can use it to construct $f^{-1}$. The only problem is that I don't know what to write...


texts: How do I count the exact number of executed commands for a MIPS program?

texts:
I want to know what the best way is to count the number of executed commands for a given MIPS program. Let's say we're given a simple for loop that counts from $0$ to $100$. For this I would write the following MIPS code:

li $s1, 0
li $t0, 100

for_loop:
    addi $s1, $s1, 1
    beq $s1, $t0, exit
    j for_loop

exit:

Since I have $2$ li's before the loop, that would be $+2$ commands and then within the for_loop, the 99 loops pass for addi, beq and j which makes it $99⋅3$ and then $2$ for addi and beq. That makes it a total of $301$ executed commands. Is my answer correct? If not then what is the correct procedure to count the number of executed commands and if in the future I come across a more complex example, then how should I deal with it?


texts:
In the plot squared length of Fourier coefficients vs frequency, the peak gives the strongest frequency. does it give the accurate value of period??
Is it like a single frequency in frequency domain corresponds to a range of periods??


texts: Normalize a Matrix with constraints on lines and columns

texts:
Context

I'm working on load-balancing traffic between client and server nodes.

Assumptions:

every server has a static weight that represents its computational power: $W^0_i$
we are able to measure with reliability the latency between a client and a server ($rtt_i(j)$ is the latency to reach server $j$ from client $i$)

Currently, clients reach a servers using a full-meshed round-robin. That means all clients "talk" to all servers with an equal probability: $P(j | client=i) = \frac{1}{|server|}$

$|server|$ is the cardinal of the server set (ie the number of servers).

Representing it as a matrix gives something like this:

           server 1  server 2
client 1     W1        W2
client 2     W1        W2

Business need

Now, I'd like to use the latency measure to adjust those probabilities. So I'd like to re-define that matrix $A$ with the first approximation:

$$A = \left \{ a_{i,j} = \frac{W^0_j}{rtt_i(j)} \right \}$$

Id est: all initial static weights are "weighted" by the round trip time.

It has two constraints:

all clients have the same load, so $$\forall p,q \sum_j a_{p,j} = \sum_j a_{q,j}$$
all servers are well-sized, so they have to receive the same amount of traffic as before. $$\forall j,k, \frac{\sum_i a_{i,j}}{\sum_i a_{i,k}} = \frac{W^0_j}{W^0_k}$$

An error of a specified precision can be tolerated.

Effective question

Applying directly the weighting of the weights ($\frac{W}{rtt}$), the two constraints may not be satisfied.

To achieve that, I guess I'd need to normalize the matrix in some way to verify and satisfy those constraints.

What kind of algorithm (or algorithm-class) would ensure a result (and convergence, if the process is iterative)?


texts: How to determine the size of training data using VC dimension?

texts:
I want to determine the size of training data ($m$) when I know the parameters $VC(H)$, $δ$ and $e$. As I know the $VC$ bound satisfy this equation:

$$ \mathrm{error}_{\mathrm{true}}(h) \le \mathrm{error}_{\mathrm{train}}(h) + \sqrt\frac{VC(H) \times \ln\left(\frac{2m}{VC(H)} + 1\right) + \ln(4δ)}m
$$

but how can I determine the size of training data ($m$) if I know the others?


texts: Is it known whether the MD5 algorithm is surjective?

texts:
Does MD5 map to all possible 128 bit numbers? To put it another way:
For every 128 bit number y, does there exist at least one x for which md5(x) = y?

The answer probably is yes, for arbitrary x, and probably no proof exists. However, feel free to prove me wrong :)

But what if I impose some kind of limit on x, e.g. x <= x_max? Of course, for very small x_max the answer is no. But what is the minimum value of x_max for which the answer likely becomes yes? Or the maximum value for which the answer can be shown to be no?

I'm not really interested in the exact value for x_max, rather in the approximate order of magnitude.


texts: Multiple Optimal Solutions in Dynamic Programming

texts:
In 2-D dynamic programming problems like Edit Distance and binary knapsack, there can be multiple optimal solutions. By tracing back from the last element in the matrix one could trace out all the possible solutions.

Here's the question: How to count the number of unique optimal solutions without backtracking? Is it even possible?

I've been stuck on this problem for a while. Any help would be appreciated.

Example:
The edit distance between two strings, TREE and TOR is 3.However, it has four optimal solutions.

1)
TREE
TOR_

Replace(R,O),
Replace(E,R),
Delete(E)

2)
TREE
TO_R

Replace(R,O),
Delete(E)
Replace(E,R)

3)
TREE
T_OR

Delete(R),
Replace(E,O),
Replace(E,R)

4)
T_REE
TOR__

Insert(O),
Delete(E),
Delete(E)


texts: the correctness of 2-satisfiability problem algorithm by using implication graph

texts:
I learned finding a solution of 2-sat problem algorithm below.

The point are below

(1) when constructing the implication graph

(2) finding there is no occurrence of a variable x and its negation x' in any SCC in the graph.

(3) then there is always the solution at this 2-SAT problem.

it means that all false 2-SAT problem have a variable x and its negation x' in SCC of its implication graph.

I cannot understand this point (3).

How can I prove it has a solution if only if there is no x and x' in a SCC?

It looks like to me, although there is no x and x' in SCC, it can be false.


texts: Reinforcement learining basics - is it possible to deal with environment with random events

texts:
As part of data science course I would like to solve particular problem with reinforcement learning algorithm.
I believe I understand general concept, however the problems I had read about up till now had no random factor included. I would like to ask if it's valid to assume that reinforcement learning algorithm will be able to find "good" (somewhat close to optimal) solution when, at each step, one or more random events can occur, provided that we know the probability of those events?
For practical example that I can think of: let's say we have to find exit from labyrinth as quick as possible, on each turn we can decide to rest or move. If we move, we become more tired, which increases probability that we will fall and twist our ankle (if this happens our speed is reduced for several turns). We know what's the probability of falling on each turn, but we do not know if this will really happen or not. During rest we reduce probability of falling.
In my project I would like to include several (around 5) of such random events.
Is it correct to assume that reinforcement learning algorithm should be able to find a valid solution, despite such random factors? We can define "valid" as, for example, in 90% of cases taking less than X turns. If yes, I would highly appreciate if you could point me in right direction, or to any materials describing practical solutions to such problems.
Thank you in advance for your input and sorry in case this question is really basic (hopefully not)!


texts: Boolean algebraic expression vs Propositional logic expression

texts:
There is a lot of similarity between Propositional logic and Boolean algebraic expressions.

Similar aspects :

1) Both has variables of two states.

2) Operations of Boolean algebra and propositional logic are similar.

3) Simplification of formula expressed in logic can be minimized using Boolean algebra and vice versa.

My doubt is are they both same? If same, why studying differently? I mean why can't Propositional logic can be directly applied to digital logic instead of introducing Boolean algebra again(academically)?


texts:
What would be a good way representing:
i. Given a key, return all the data values associated with that key
AND
ii. Given a data value, return all the keys that are associated with that data.

So far, all I can think of is to maintain all keys in a sorted linked list where each "key" node has a key value and a vector of pointers to data nodes (in addition to linked list bookkeeping). Likewise, maintain all data values in a sorted linked list and each "data" node has a data value and a vector of pointers to the relevant keys.

Could you please offer me a hint for a more appropriate solution to this problem?


texts: What is complexity class $\oplus P^{\oplus P}$

texts:
What does the complexity class $\oplus P^{\oplus P}$ mean? I know that $\oplus P$ is the complexity class which contains languages $A$ for which there is a polynomial time nondeterministic Turing machine $M$ such that $x \in A$ iff the number of accepting states of the machine $M$ on the input $x$ is odd.

But what does $\oplus P^{\oplus P}$ mean? I just can't follow what it actually does :)

What are practical consequences of such complexity class and how it is possible to show that $\oplus P^{\oplus P} = \oplus P$?


texts: Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

texts:
We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the predicate $P$, but we would like to sample or choose an element uniformly at random from $S' = \{ i \mid i \in S \wedge P(i) \}$.

The naive approach is to scan $S$ and for example record all the integers or indices for which $P$ holds, then choose one of them uniformly at random. The downside is that in the worst-case, we need $|S|$ space.

For large sets or in say a streaming environment the naive approach is not acceptable. Is there an in-place algorithm for the problem?


texts: Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

texts:
I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)

$\alpha$ denotes the start and end vertex of the Eulerian path

Step 1 - Calculate minimum spanning tree $T$

Step 2 - Calculate the set of verices $O$ with odd degree in $T$

Step 3 - Form the subgraph of $G$ using only the vertices of $O$

This is starting to get confusing

Step 4 - Construct a minimum-weight perfect matching $M$ in this subgraph

Step 5 - Unite matching and spanning tree $T$ and $M$ to form an Eulerian multigraph

I am NOT satisfied

Did I do something wrong or did I simply just hit an sub-optimal solution.
It is not hard to see that the Eulerian path easily could be improved by either connection $G \rightarrow H$ or $A \rightarrow B$ as illustrated underneath:


texts:
I was revising Computer Science and I got these two doubts to which I've found contradictory answers on Google:

In a serial communication which bit is sent first?
When using a parity bit with ASCII is it set on the LSB or MSB?

Logically thinking I thought the answers should be 1- MSB first and 2 - set on LSB. Am I right?

Thanks in advance.

Gabriele


texts: How do you swap consecutive boxes on a Turing Machine tape?

texts:
I can't figure out how to swap boxes on a Turing Machine tape.

So for example, I have a tape that says

a 1 0 1 1 1 0
^

And I want to move that a over so that it is in the middle. (but my end goal is not important here)

How do I get the Turing Machine to do

1 a 0 1 1 1 0
  ^

1 0 a 1 1 1 0
    ^

etc...


texts:
Problem description
We are given two sorted arrays of even numbers: A and B.
Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd number to predict which set an element belongs to. If an element is smaller than X, it will be assigned to A,and if it is bigger - to B.  The value should be optimal, meaning the number of improperly matched values should be minimal.
For example, if A = [2,4,6] and B = [6, 10, 12]. Separating value 3 would cause 2 mismatched values 4 and 6. Optimal would be 5 or 7, both causing one improper matched element.
The algorithm is supposed to return an optimal separating value (only one of there are many) and the number of mismatched items.
My ideas
At first I thought about using Binary Search for each element of A to find a number of elements of B smaller than it. Then repeat for B.
A better idea would be to generate candidates for such separating numbers. For example, if we only  have values 10, 50, 100 we don't have to check all odd numbers, we can just check 9, 11, 51, 101. We could then calculate prefix sums, indicating how many numbers from A are bigger than the checked value and how many elements from B are smart than that value. The sum of the two sums for a number would be the total number of errors. The only thing left is to find the value with minimal errors.
Is this approach even near optimal, maybe we can find a better way. Also, calculating such prefix sums can be tricky because if we want not to care about the range of numbers we would have to find a way to skip some numbers and that makes our iteration harder, although possible.
What are your ideas? Some pseudocode or code in Python is very welcome.


texts: Prove that L $\in$ NP implies L* $\in$ NP

texts:
I have been trying to solve this problem with witness theorem. So the problem is as below:
Define $L^* := \{x \in \Sigma^*|$there exists k and $x_1,...,x_k\in L$ such that $x=x_1x_2...x_k\}$. Prove that $L \in NP$ implies $L^* \in NP$.

So my initial thought is to find a witness language $\in P$ for $L^*$ from the fact that L has a witness language L1 $\in P$. However, I am not sure how to find the right partition of x such that I can use the witness $(x_1,y_1),...,(x_k,y_k) \in L1$.

Does anyone have any thought on it? Much appreciated!


texts: How to prove that the minimum square partition of a 3X2 rectangle has 3 squares

texts:
This question is motivated by an older question about tiling an orthogonal polygon with squares.

Given a $3\times 2$ rectangle like the first image, the second image is a square partition of that rectangle.

A square partitioning is a covering by non-overlapping squares; the entire rectangle must be covered, all the squares must be disjoint.
A minimum square partitioning is a square partitioning, for which is no square partitioning that is made of a lesser number of squares.

  How can we prove that the second image is a minimum square partitioning of the $3\times 2$ rectangle?

Can we generalize this to ${\rm M{\small IN}S{\small QUARES}}(R_{w,h=w-1})=w$? (see followup question )


texts: How to prove that 3-coloring is decidable?

texts:
In order to prove that 3-coloring is decidable, is it sufficient to say:

Each node in the graph has 3 possible colors
Therefore we can enumerate over all $3^n$ possibilities and then check that no two edges connect nodes with the same color

Does that prove that 3-coloring is decidable?  Or do I need to construct a Turing machine for a proper proof?

By 3-coloring I'm talking about the graph coloring problem; i.e. assign one of 3 colors to each node in an undirected graph such that no two adjacent nodes have the same color.


texts: Edge coloring optimization using dynamic programming

texts:
The problem is to find an algorithm that colors all the edges in any arbitrary tree T with a root r, let's say in blue and red, such that the number of blue edges is maximal and there isn't more than three blue edges in a row on any path starting at r.

Update:

I've tried a top-down solution, but I'm not able to figure out how to build the recursion using the condition of maximum three consecutive edges.

Maybe the bottom-up approach will be better. There I'd start colouring all edges with blue and write down the longest color sequence present on any path to the leaves. Then, if the sequence length is equal three, I have no other option than coloring the edge in red.

I'm not sure if this is always leading to the optimal result, cause it looks more greedy than dynamical.

The question is, how to get the optimal result? And how to be sure it's correct?


texts: Sorted array with odd indexed elements swapped randomly

texts:
A sorted array $\mathcal{A}$ with even number of elements is given. Consider $\mathcal{A}$ be partitioned from the middle such that both parts ($\mathcal{A}_1, \mathcal{A}_2$) contain equal number of elements. We choose some arbitary odd indexed (index with $1,5,9$ etc.) elements from $\mathcal{A}_1$ and swap them with some other random odd indexed elements of $\mathcal{A}_2$. Even indexed elements of $\mathcal{A}$ remain untouched.

We need to device an algorithm to check whether an element $\mathcal{x}$ exists in $\mathcal{A}$ in $O(\log n)$ time.


texts: algorithm for finding the radius of a graph

texts:
The eccentricity of a vertex v is the length of the shortest path from that vertex to the furthest vertex from v in an undirected graph. The diameter of an undirected graph is the maximum eccentricity of any vertex. The radius of an undirected graph is the smallest eccentricity of any vertex. A center is a vertex whose eccentricity is the radius. Assuming a connected, unweighted, undirected graph G, give an algorithm to compute the radius of G.

I am using the definitions given above to compute a radius for a connected, unweighted, undirected graph.  So far, my algorithm consists of this:

For each vertex $v$ in graph$ $G, use Bellman-Ford to find the furthest vertex from $v$ (longest of the shortests paths found).

record the path $s_0,s_1,s_2,\ldots,s_n$ for vertexes $1,2,3,\ldots,n$.
Note: the order of the chosen vertexes is arbitrary, as long as all vertexes are analyzed once and only once.

Compare all paths $s_0,s_1,s_2,\ldots,s_n$ and return the shortest path in the set of recorded paths.

My question is if this algorithm works, or if it doesn't, how I can modify it to fix it or make it better.  I know that Bellman-Ford computes the shortest path to every vertex in the graph so doing this for every vertex in the graph would be pretty exhaustive, perhaps even unnecessary.


texts: Number of probes in a successful search in open address hashing

texts:
Given an open-address hash table with $\alpha$ < 1, the expected number of probes in a successful search is at most $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$

I read this in a book and the proof starts by saying

Searching for k follows the same probe sequence as inserting it. If $k$ is the $i+1$th key inserted into the table, then $\frac{1}{1-\frac{i}{m}}$ is the maximum expected number of probes for the search.

However I don't understand how $\frac{1}{1-\frac{i}{m}}$ gives the number of maximum probes needed. Imagine we have $n=5$ and $m=10$ with linear probing. Now if we want to insert the 6th key, based on the fraction above it should take us at most $\frac{1}{1-\frac{5}{10}}=2$ probes. However imagine if slots 0 through 4 were occupied in our table and we start at index 0, then I guess it would take 5 probes to find an empty slot, right?


texts: How is $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $} a regular language?

texts:
My understanding is that a machine with finite states cannot keep track of the n's being the same  in $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $}, similar to the case with how $a^nb^n$ is not a regular language. For instance, if we take a string $aaaa ab bb$, where the fifth a and the following b are $s$, how is this valid? We have a disproportionate amount of a's to b's. Using the pumping lemma, I feel that this is disproven easily if $y$ (from $xyz$ division) is any number of a's at the beginning.

If this can be proven using a DFA, what is it?


texts:
I am involved in a first year programming and algorithms course. In a recent lecture, I decided to present the material using live coding, which essentially meant that I sit behind the keyboard and write code and evaluate it, using emacs to facilitate the process.

This was quite successful and students commented on how much they appreciated the more (inter)active format. As this was my first attempt using this teaching format, I know that it did not run perfectly. Some of the problems were related to being not as savvy with emacs as I should be, and others were to do with allowing student questions to take me too far from my script. I know I can do better.

  What are some guidelines for giving lectures (and other demonstrations) using live coding lectures?
  What are the pitfalls to avoid?


texts: How to prove for string of triplets that it is a Regular Language?

texts:
Let Σ2 = {0, 1}, and define Σ = Σ23. Informally, Σ* is the set of triples of the form (a, b, c) where a, b, c are single binary digits.
Consider a string s ∈ Σ* : it is a sequence of such triples. Have to “verify” binary addition of numbers in the first two coordinates by checking that it is equal to the third. Let A be the language of such triples such that the concatenation of the first coordinates, as a number, and the concatenation of the second coordinates, as a number, sum to be equal to the third.

For example, if w = (0, 1, 1)(1, 1, 1)(0, 0, 1)(1, 0, 1), this is encoding 01012 + 11002 = 11112,
which is false; therefore, w ∉ A. How to prove A is Regular ?

Only thing I could think of is somehow has to prove for Reversal is Regular and then this could be proved, but no further idea.


texts: Multitape Turing machine with multiple non-blank tapes

texts:
A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank.

Are there any formulations of a Turing machine that allow other tapes to be not blank? Why does the condition that the input only appears on one tape exist?


texts: Indoor path prediction with machine learning and pattern matching

texts:
Ok. You'll have to bear with me because I'm new to this. I have an idea for a research project. It involves trying to predict a path that someone might take in an indoor environment. My idea is to use smartphones to gather various sensor readings(accelerometer, gyroscope, magnetometer...) while the person walks his normal paths.

Step 1: Collect enough repetition of this data and use machine learning to mine the data. What I'm looking for is whether the direction changes can be identified. So once I run the machine learning algorithm I should get a sequence of predicted directions for example: Path 1: Straight, straight, Left, Left, Right, Right, Straight... which I'll use later in step 2.

Step 2: Here we see if we can predict the path ahead of the person and maybe even the destination at the end of that path. What I'm thinking of is to use a pattern matching approach. So as the directions of the path the person is currently walking on keeps coming in it should be trying to match with the sequence of directions that I have already gotten from the machine learning process. So if the current directions are Straight, Straight, left, left, right, right, straight... then the pattern matching should match the path the person is walking on to Path 1.

What I'm having difficulty with is where the two steps meet. I can already use some machine learning algorithms to predict the directions with a satisfying level of accuracy. But I don't quite know how to get from there to pattern matching. Any amount of help would be greatly appreciated. And if my writing is not specific enough or difficult to understand I'll be happy to clarify.


texts: Can subtracting o(1) from the parameter of a function change its Θ-class?

texts:
I would like to know if it is possible that two functions $f(n), g(n)$ can exist such that both of the following conditions are met:

$g(n) = o(1)$
$f(n-g(n)) \neq \Theta (f(n))$

I though I found $1/n$ and $1/n^2$ but I think I got it all wrong.

Is it even possible?!


texts: Identifying Coffman conditions in a given situation with deadlock

texts:
Let's suppose there are N processes and we have the following code:

atomic <int> c = 0;
semaphore b = 0;

proc P(i){
   ...
   if(c.getAndInc() < N - 1){
      b.wait();
   }
   else{
      b.signal();
   }
   ...
}

A deadlock will occur as N - 2 processes will be blocked by $ b.wait() $.
I'm trying to identify how the Circular wait condition holds, being a necessary condition as it is.

(Circular wait means that "A set $\{ P_0, P_1, ..., P_n \}$ of waiting processes must exist such that $P_0$ is waiting for a resource held by $P_1$, $P_1$ is waiting for a resource held by $P_2$, ..., $P_{n-1}$ is waiting for a resource held by $P_n$, and $P_n$ is waiting for a resource held by $P_0$". This quote is from the book "Operating System Concepts", by Silberschatz, Galvin and Gagne.)

In other words, as there is deadlock, the circular wait condition must hold, but I just don't see it. Is there anything I am misunderstanding?

Thanks!


texts: Strongly connected subgraph that contains no negative cycles

texts:
Is there an efficient algorithm that solves the following decision problem:

  Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected spanning subgraph of $G$ that has no negative cycles?

A strongly connected spanning subgraph of $G$ is a strongly connected subgraph of $G$ that shares the same vertices with $G$. You can look to this paper for the definition. In this paper the authors present an approximation for the minimum strongly connected subgraph problem, which is different from the problem stated in this question.

A naive approach to this problem is to find a negative cycle of the graph using the Ford-Bellman or Floyd-Warshall algorithm, deleting an edge from this cycle, and repeating while the graph is still strongly connected. But this naive approach has poor time complexity because we will potentially run the Ford-bellman algorithm and check for strong connectivity many times -- moreover I am unable to prove if this algorithm is correct in all instances.


texts:
Is it true that $ 2^{O(3k)} = 2^{O(k)} $?
But It should be different from  $ O(2^{k}) = 2^{O(k)} $ ?
I will be happy for simple explanation.
Thanks.


texts: Insertion and deletion complexities for a linked list and array

texts:
I have the following table that compares different operation complexities for a linked list and array:

                        Linked List |   Array   |   Dynamic Array
Deletion at ending      O(n)        |   O(1)    |   O(n)
Insertion in middle     O(n)        |   O(n)    |   O(n)
Deletion in middle      O(n)        |   O(n)    |   O(n)

Can anyone please explain why:

Deletion for Dynamic Array is O(n)?
Insertion and deletion in middle for all data structures is O(n)?

Thanks


texts: Given a directed acyclic graph (DAG) - what can you say about each case?

texts:
Suppose $G$ is a DAG with $n$ vertices, and $v$ is a vertex of $G$. What can we say regarding $v$ if the following holds:

A. In all topological sorts, $v$ is at the end of the list.

So my initial answer is that $v$ is the "sink" vertex, but in some case its not always correct, can't seem to find a feature that cant be said on $v$?

B. In all topological sorts, $v$ is at the top of the list.

So this one is the opposite which is the source vertex and has arrows coming out of him and no one points to him.


texts:
I need to prove or disprove $DTIME(n^2)=NL$. It kind of feel obvious that I need to disprove it, because if I have non-deterministic machine $M$ that uses $\log n$ space, then it meets at most $|Q| n\log n\ 2^{\log n}=|Q|\log n \ n^2 = \omega(n^2)$ ($Q$ denotes the number of states) different configurations, which bounds the running time, therefore intuitively it looks like I'll need more then $n^2$ to run $M$.
Can someone explain to me how would you approach to these types of problems? Because I always find my self resorting to "trial and error" with diagonalization and padding arguements.
Thanks in advance.


texts:
I'm trying to find an algorithm for finding all faces in a wireframe mesh.  Wireframe means only the vertices and edges are given as input.  There is no restriction on the number of edges a resulting face can have and the face can be convex or concave.

Simple Example

In a wireframe of a square-based Pyramid there are 5 faces - the base is a square and the sides are triangles.

The algorithm should produce 5 sets of edges (since there are 5 faces).  One set of edges would contain the 4 edges that make up the square base and then 4 sets of 3 edges for each side of the pyramid.

Bonus

It would be a bonus if the algorithm can create an edge winding resulting in all faces pointing inwards or outwards.


texts: primitive recursion on untyped lambda calculus

texts:
Does a definition of primitive recursion exist for the untyped lambda calculus? Does the definition of primitive recursion require typing for natural numbers?

The only definitions I can find are for the typed lambda calculus: http://www.math.nagoya-u.ac.jp/~garrigue/lecture/2013_tenbo/recfun_en.pdf. Perhaps if I just ignore the types it will still be valid?


texts: Algorithm to determine whether two regexes are equivalent

texts:
Given two arbitrary regular expressions, is there an "efficient" algorithm to determine whether they match the same set of strings?

More generally, can we compute the size of the intersection of the two match sets?

What algorithms are there to do this, and what complexity class do they live in?

If we disallow the Kleene star, does that alter the picture at all?


texts: $k$ vertex-disjoint paths cover in Directed Acyclic Graph

texts:
The problem is that: in a directed acyclic graph $G$, I want to know the maximum vertices that can be covered by $k$ vertex-disjoint paths.

Obviously, the value of $k$ is smaller than the minimum path coverage of $G$. Are there any approximation algorithms that can solve this problem?


texts:
We are given two numbers N and K.

N <= 10^9.

K<=min{1000,(N*(N-1))/2}

We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K.

If N was <= 10^3. It would be a simple Dynamic programming question.

https://www.geeksforgeeks.org/number-of-permutation-with-k-inversions/

can we optimize it?


texts:
I know there is a polynomial time algorithm for 2-coloring. But should the answer be "No" or should it be "Maybe"?
Since 2-coloring is in NP and we dont know if there is a reduction of any NP-complete to 2-color.


texts:
The Berman-Hartmanis conjecture discusses one-way functions (functions with hard to compute inverse functions).

As a step to solving the conjecture, if one-way functions could be reduced to a canonical or universal one-way function from which all one-way functions could be derived, this would be a major plus...

In a similar way, Turing devised a universal machine and Cook NP-completeness.

The question is then, are there universal one-way functions (discussed in the literature)? Can they be defined through NP-completeness?


texts:
By unique words we understand the such word $w$ that every character in the word occur at most once, for example:
$\Sigma = \{a,b,c\}$
$w = abc$, $v = abca$

$w$ is unique, $v$ is not.

Now, we have a problem:

We have given an alphabet $\Sigma$. We have a given length of word $|w| = n$. How to recognize using $NFA$ whether $w$ is unique?

$NFA$ is expected to has polynomial number of states regard to $n$.

Please hint me.


texts:
Without sound synthesis, what is a good way of making a program that plays guitar notes from an array of stored sounds?
What I have in mind is to make note as a function of vibration speed such as N (V) which returns an int index of the sound to be played and the vibration speed itself as a multivariate function of 3 variables distance, thickness and tension so V (d, t, n) = ₩ n  - ₩ t -  ₩ d;
Where ₩ is some coefficient foreach variable. And negative represents  an inversely propotional relationship.
My qyestion may seem a bit broad, but how to improve such a model and is it mathmatically sound?


texts: TM that accepts all strings is recognizable or not?

texts:
Lets say we have the following language $L = \{\text{$M$ is a TM such that $M$ accepts all strings}\}$, is this recognizable or not? I have a feeling it is unrecognizable, if this statement is correct could anyone provide me with a proof?

My current reasoning is that since the set of all strings is infinite, the "recognizer" TM will never be able to test all strings thus never be able to accept a given TM.

Please give me your thoughts on this.


texts: Height of AVL tree with balance condition of 2

texts: The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed imbalance condition between two child nodes would be 2), how could I find the maximum height of such a tree. Would I need to solve some kind of recurrence relation or fibonacci sequence. Is there an easier way of figuring out the maximum height of a tree with a balance condition of 2 by using what we already know? Thanks.


texts: Edge-connectivity of a weighted undirected graph

texts:
My question consists of two parts.

Let say the edge connectivity of a graph is K. I would like to change the edge connectivity value to L (> K). What is the best possible way to do so?

My guess: Obviously, we have to increase the edge weight of one of the critical edges (edges of the min-cut), but among the set of critical edges which edge should we choose?

After changing the weight of one of the critical edges, how could we find the new edge connectivity of the graph [assume we have already computed the edge connectivity of the previous graph]?