texts: fraction of volume of a rectilinear grid cell within some radius of the origin

texts:
I have a sphere (radius R) on a rectilinear grid. Some cells intersect the edge of that sphere, call them 'edge cells'. Designate a given cell by indices [i,j,k] which refer to the lowest-index vertex of that cell (i.e. the inner-most cell, in the [+x,+y,+z] octant would be designated as [0,0,0]). For any given 'edge cell', how can I calculate what fraction of its volume is within the sphere of radius R?

In this figure, the purple surface is the surface of the sphere passing through some arbitrary cell, with origin [x0,y0,z0]. I want to know what fraction of the cell's volume is within this surface.

I think 'edge cells' can be calculated by finding the cells whose vertex [i,j,k] is at a radius R.

I think there should be an analytic formula to calculate the volume fraction, but I can't figure out how to setup the integral. Any help would be greatly appreciated!


texts: Minimum number of people required to invite everyone to a reunion

texts:
I'm trying to organise a large reunion though facebook. Over the years we've all drifted apart, and so there isn't anyone who is still facebook friends with everyone.

You need to be facebook friends to invite someone to the facebook event and I have invited all the people that I can. I also know that each of the uninvited people has at least one friend amongst the invited people, and by checking for 'mutual friends' I can know who they are.

In order to get everyone invited to the reunion I'm going to ask some of the invited people to invite the uninvited people.

My question is, does anyone happen to know an algorithm to find the minimum number of invited people that are required to message all of the uninvited people? I don't need anything super detailed, just something to point me in the right direction.


texts: Why we still need Short Term Memory if Long Term Memory can save temporary data?

texts:
If RAM is a short term memory and SSD is a long term memory, why don't microarchitecture of computer nowadays use SSD or another long term memory for saving temporary data like hidden variable for programming?
If it's about speed, then SSD can improve its speed, is it possible that SSD will become faster than RAM at some point?
If SSD has address for memory location and data for
opcode/instruction/operand like RAM, then will it possibly act like RAM?


texts: Polynomial time reductions using binary search

texts:
There are many NP-complete decision problems that ask the question whether it holds for the optimal value that OPT=m (say bin packing asking whether all items of given sizes can fit into m bins of a given size).
Now, I am interested in the problem whether OPT>m. Is this a decision problem or an optimization problem? It seems to be that it lies in NP (a NTM can guess a solution and it can be verified in polynomial time that the bound is met). Is it also NP-complete?

I would have said yes, because having a polynomial algorithm, we could find a solution in polynomial time for the original problem (asking whether OPT=m) by using binary search and repeatedly using the polynomial algorithm to test if OPT larger than some bound.

However when I try to construct a proper solution, I always see the complication that the oracle (that asks whether OPT>m') would need to be queried more than once, and this is forbidden in the polynomial time Karp reduction.

Any solutions or remarks?
Would it make a difference if I ask whether OPT>=m?

Thanks in advance


texts: TM with double-infinity tape semi-decides the same languages as classical TM

texts:
Show that a Turingmachine with tapes that are infinite in both directions semi-decides the same languages as a classical TM. Apart from the entry-word, the tapes are filled with empty spaces and the head's on the first letter of the entry-word

Under "classical" TM we understand a TM that has a tape that starts at the first letter and is infinite at the right side.
I don't quite understand what to prove here. The only difference between the two TM's is that I can/can't hit the left border of the tape. I could make this scenario a rejected state in the double infinite TM because it can't happen on the single infinite TM.
Any tips?


texts: Do $s$-$t$ cuts partition contingent vertices?

texts:
The definition of an $s$-$t$ cut is a partition of the set of vertices $V$ into $2$ sets $(A, B)$ with $s$ in $A$ and $t$ in $B$. My understanding of set partitions is that the positioning of elements in the graph does not matter.

However, if this is the correct notion of partitioning, then can construct a pathological example. Consider the following network. $$s \to B_1 \to A_1 \to B_2 \to A_2 \to t.$$Let each of the edges have a capacity of $1$. Then the max flow is clearly $1$. If we let the $s$-$t$ cut be such that set $A$ consists of $s$, $A_1$ and $A_2$, and $B$ is the rest, then the capacity of the cut is $3$ since there is a flow of value $1$ exiting each of the $3$ vertices in $A$. This contradicts the max-flow-min-cut theorem.

Is my understanding right then that the $s$-$t$ cut is not a partition of a set but a graph? By this I mean, that the resultant two sets have to be contiguous?


texts: Identify row or column addition or deletion in a table

texts:
I'm looking for a solution which can able to identify the any row or column addition or deletion in a table of numbers.

What I have thought of as of now by using the LCS i.e. "Longest common sub-sequence" algorithm I can find out the common sub-sequence between two versions of a table but this method is not 100% correct.

For e.g.

Table version 1

 1 2 4 5 9 3
 4 9 3 7 5 3
 8 2 7 9 3 8
 9 7 2 8 2 4

After update, I remove 1 row (2nd row) and added 1 row (at same place i.e. 2nd).

Table Version 2

 1 2 4 5 9 3
 4 9 5 7 5 3
 8 2 7 9 3 8
 9 7 2 8 2 4

Added row is almost similar except 1 cell item. In this case LCS would not work as it most of the cell items would be similar and I can't able to identify row was removed first and a new row was added.


texts: How MAC-3(maintaining arc consistency-3) algorithm works?

texts:
I am studying CSP problems in artificial intelligence.  I don't understand the MAC-3 algorithm especially line number 10. Could you tell me with step by step?

1. Function AC-3MAC(Q,CV)
   1.1 Q ← {(V i ,V cv ) in arcs(G),i>cv} % start with arcs going to cv
   cv means current variable
2. Begin
3.     consistent := true;
4.     While not (empty?(Q)) and consistent
5.     Do Begin
6.         (i,j) := pop(Q);
7.         if revise(i,j)
8.         then begin
9.             consistent := not(empty?(domain[i]));
10.            Q:=Q U {(k,I) | (k,I) in arcs(G) & k<>j & k>cv}
11.        end;
12.    end;
13.    consistent←not Empty Di;
14. end;

I understand the process of AC-3 algorithm.
This is AC-3 algorithmProcedure AC3
Begin
1. Q:= {(i, j)|C ij ∈ C i ≠ j}
2. While Q not empty Do
3. Begin
4. Select or delete a pair (i, j) from Q
5. If Revise (i, j) then
6. Q:= Q ∪ {(k, i)|C ki ∈ C, k ≠ i et k ≠ j}
7. End if
8. End while
End

The below pictures represent map coloring example.I have traced manual with
AC-3 algorithm.The point I want to know is line number 1.1 in MAC algorithm.
How can I add arcs in queue with i>cv ? Furthermore ,in line number 10 how to add queue of arcs k>cv.


texts:
The question is "For a file system with 11 direct blocks, 5 indirect blocks, 2 secondary (double) indirect, 2 triple indirect blocks calculate the maximum file size allowed if block size is 2048 in a 32 bit system. OK, so I know how to calculate this by doing the following:

2048 (block size)/4 (bytes) = 512 pointers
(11*2048) + 5(512^1*2048) + 2(512^2 * 2048) + 2(512^3 * 2048) = 5.54 * 10^11

The thing I am confused is, what if we were to change the 32-bit system to a 16-bit system, how would we calculate that?


texts:
Zookeeper is based on the Zab (which is slightly different to Paxos) system.

We can do Atomic locks on top of a Zookeeper cluster.

Zookeeper provides eventual consistency.

Zookeeper provides durability.

(I'm aware that Zookeeper sacrifices Availability for Consistency and Partition Tolerance - making it CP - but I'm not asking that question here. )

My question is: Can we say that Zookeeper updates are ACD (ACID without the I)?


texts: Is it true that all languages which have polynomial circuits are in PSPACE?

texts: I just read about polynomial-size circuit families and I have a question as the title. I know P/poly is defined as the class PSIZE of languages that have polynomial-size circuits. But what about other languages in other classes that have polynomial circuits?


texts: Help needed for understanding proof of No Regret Multi Armed Bandit Algorithm

texts:
I was reading Elad Hazan's book on Online Convex Optimization(http://ocobook.cs.princeton.edu/OCObook.pdf) and am facing difficulty understanding the proof given for the No regret algorithm for MAB (Pg 102-103). It would be great if someone can provide a clarification on this.

The No-regret (sub-linear) algorithm is given in Algorithm 17 (Pg 102), and proof for no regret is shown in lemma 6.1 . I will make the description as self-contained as possible, but a more detailed presentation can be found in pgs 102-103 in the book mentioned above.

Let $\mathcal{K}=\left[1, n \right]$ denote the set of experts(arms). Let $i_t \in \mathcal{K}$, denote the expert chosen by the algorithm in the $t^{th}$ round. Let $l_t(i_t)$, denote he loss function provided by the adversary in the $t^{th}$ round. Since we are dealing with the bandit setting, we do not know $l_t(i)$ for all $i \in \mathcal{K}\backslash i_t$. Further, the loss functions ($l_t$) are assumed to be bounded between 0 and 1. The way the algorithm works is, at each round we flip a coin, with bias $\delta$. If the outcome of the coin is heads, the algorithm chooses one of the actions i.e. $i_t$, and constructs a estimate of $l_t$ as follows:
\begin{equation}
\hat{l}_t =
\begin{cases}
\frac{n}{\delta} l_t(i_t), \text{ if } i = i_t\\
0, \text{ otherwise}
\end{cases}
\end{equation}

If however, the outcome of the coin toss was tails, then it simply sets $\hat{l}_t = 0$.

It can be easily shown that by using the above scheme we have $E\left[ \hat{l}_t(i)\right] = l_t(i), \, \forall i \in \mathcal{K}$.

The regret as shown in the book is as follows.
\begin{eqnarray}
\label{Eq:1}
E[regret_T] &=& E\left[\sum_{t=1}^{T} l_t(i_t) - \sum_{t=1}^{T}l_t(i^*)\right] \\
\label{Eq:2}
& \leq& E\left[\sum_{t \not \in S_T} \hat{l}_t(i_t) - \sum_{t \not \in S_T} \hat{l}_t(i^*)  + \sum_{t \in S_T} 1 \right]
\end{eqnarray}

where $S_T \subseteq [1, T]$ denotes the round in which the coin toss was heads, and $i^* = \underset{i \in \mathcal{K}}{\text{arg min}} \sum_{t=1}^{T} l_t(i)$ . I am having a hard time showing why $E[regret_T] \leq E\left[\sum_{t \not \in S_T} \hat{l}(i_t) - \sum_{t \not \in S_t} \hat{l}_t(i^*)  + \sum_{t \in S_T} 1 \right] $. The comment in the book is that $i^*$ is independent of $\hat{l}_t$, hence validity of inequality. I did not understand what that was supposed to mean.

My Attempt:

For my attempt, I will be using the some of the notation used in the proof of that book.
We know that $\underset{i \in [1, \dotsc, n]}{\text{min}} \sum_{t=1}^T \hat{l}_t (i) \leq \sum_{t=1}^T \hat{l}_t (i), \, \forall i \in [1,n]$. Applying $E$ (expectation) on both sides we get,
\begin{eqnarray}
E\left[ \underset{i \in [1, \dotsc, n]}{\text{min}} \sum_{t=1}^T \hat{l}_t (i) \right] &\leq & E \left[\sum_{t=1}^T \hat{l}_t (i) \right], \, \forall i \in [1,n] \\
\implies E\left[ \underset{i \in [1, \dotsc, n]}{\text{min}} \sum_{t=1}^T \hat{l}_t (i) \right] &\leq & \underset{i \in [1, \dotsc, n]}{\text{min}} E \left[\sum_{t=1}^T \hat{l}_t (i) \right] \\
&=& \sum_{t=1}^T l_t (i^*)
\end{eqnarray}
, in the book it is easily shown that $E\left[\hat{l}(i)\right] = l(i)$.
In view of the above inequality, we can show

\begin{eqnarray}
E[regret_T] &=& E\left[\sum_{t=1}^{T} l(i_t) - \sum_{t=1}^{T}l_t(i^*)\right] \\
& \leq& E\left[ \sum_{t=1}^{T} \hat{l}(i_t) - \underset{i \in [1, \dotsc, n]}{\text{min}} \sum_{t=1}^T \hat{l}_t (i)   \right]
\end{eqnarray}

Clearly, I am making some mistakes in the attempt above. I will be grateful if someone can point me to those and help clarify the reasoning in the book. I say my attempt is incorrect because, in the way I have shown, I completely disregarded the set $S_T$. Without this set, the book shows the regret to be $\mathcal{O}(\sqrt{T})$, whereas with the $S_T$ set the regret is shown to be $\mathcal{O}(T^{\frac{3}{4}})$


texts: How again do certain sorting methods use $o(n \log n)$ time?

texts:
I hope this question isn't too 'soft' for here.  It's been a while $\tiny{\text{an eternity for some people's standards}}$ since I've touched this stuff, and I had a convincing explanation to this question eight minutes ago but must have misplaced it, so please help me find it again:

Most classical sorting algorithms one reads about are comparison sorts, in which a single comparison produces a binary outcome (let's break ties arbitrarily).  The motivation for this I remember is that they are general, requiring only that an ordering be prescribed over the items, and insensitive to how the items are encoded, but suffer from a $\Omega(n \log n)$-time barrier simply for reason of needing to do enough comparisons to distinguish the $n!$ possibilities.  One then meets algorithms such as radix sort, which is supposed to beat this under caveats such as the space of items being discrete and bounded, and assuming the ability to retrieve any decimal/etc. place in constant time.  But as I recently thought about it, this operation is essentially a $b$-way switch as opposed to the (ordinary) $2$-way kind used in comparison sorts.  Then radix sort would be subject to the same lower bound on time taken since the foregoing gives an improvement of $(\log b)/(\log 2)$ (at most?).  So how is radix sort ever preferable to one of the standard comparison sorts?  I know this is a contradiction, but not how so.

In my experience this kind of paradox typically dissolves when formalised.  I would rather have an intuitive reason that explains it away if such is available, though.


texts: Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori

texts:
A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$.

$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$

The goal is to search for $n\ast$. The bounds $n_{min}$ and $n_{max}$ are known apriori.

A salient property of $n\ast$ is that it has a higher probability of lying in a region around $\hat{n}$ (known apriori). The exact probability distribution, although unknown, (probably doesn't matter) can be considered as continuous CDF having a higher weighting factor around $\hat{n}$

I have already implemented a simple binary search, but I am looking for more efficient solutions that somehow account for the given probability information (i.e. $n\ast$ is concentrated around $\hat{n}$), I am looking for an efficient algorithm to find $n\ast$.  without losing accuracy.

I know that Binary search is worst-case $\mathcal{O}(log\ n)$, but $f(n)$ is so computationally expensive that I can't afford even this.


texts:
I've finished most of the material in Cormen's Intro to Algorithms book and I am looking for an algorithms book that covers material beyond Corman's book. Are there any recommendations?

NOTE: I asked this on stackoverflow but wasn't all too happy with the answer.

NOTE: Looking at most of the comments I think ideally I would like to find a book that would cover the material of the the 787 course in this course description.


texts: Regular expression at least 2 out of 3 consecutive characters should be 1

texts: How can I build a regular expression that, using only the concatenate, union and star operations, over the alphabet {0,1}, describes the language "Every three consecutive characters contain at least two 1, and the input has length at least 3"? For instance 110011, 0101 and 11 should be refused. I was thinking on using the logic from this (incomplete) DFA, but I can't figure out how to get a regular expression that follows the rule. Thanks!


texts: Optimal coverage of a $D$-dimensional grid with small blocks

texts:
I have a $D$-dimensional grid with the size $(N_1, \ldots, N_D)$, where $N_i$ are natural numbers, and a "flat block size" $M$, also a natural number. I want to find a decomposition $(m_1, \ldots, m_D)$ such that:

$\prod_{i=1}^D m_i = M$,
$R = \prod_{i=1}^D f(N_i, m_i) m_i - \prod_{i=1}^D N_i$ is as low as possible. Here $f(N,m)$ is the minimal number of blocks of length $m$ necessary to cover a 1D grid with size $N$ (or, formally, $f(N, m) = N / m$ if $N$ is a multiple of $m$, and $f(N,m) = N\,\mathrm{div}\,m + 1$ otherwise).
The number of $m_i$ equal to 1 is as high as possible (but this is low priority, the condition 2 is more important).

How should I approach this? Is there some standard algorithm this can be reduced to?

In my case $M$ is not very big (of the order of 1000). Also, an absolute minimum in all cases is not strictly required; if there is an approximate algorithm, it will do to.

(In case anyone is interested in the application, I want to use it to find work group dimensions for an OpenCL kernel with a known global size and total number of work items).


texts: Dynamic programming for subsequence metric

texts:
Let $a = a_1, \ldots, a_n, b = b_1, \ldots, b_m$ be sequences of positive integers and for any respective subsequence of length $k$, we consider $\sum_{i=1}^k (a_{x_{i}}-b_{y_{i}})^2$. Given a bound $D$, find the largest $k$ such that there exists subsequences of $a$ and $b$ such that $\sum_{i=1}^k (a_{x_{i}}-b_{y_{i}})^2\leq D$ which is polynomial and not proportial w.r.t. $D$.

Heres my attempt:

Define $Opt[i, j, k]$ to be the minimal of the metric of subsequences $a_1, \ldots, a_i$ and $b_1, \ldots b_j$ of length $k$. Then define $$Opt[i, j, k] = \begin{cases} 0 &\text{if $k =0$}\\
\min(Opt[i-1, j-1, k-1]+ (b_i-a_j)^2, Opt[i-1, j-1, k], \min_{1\leq p< i} Opt(p, j, k), \min_{p} Opt(i, p, k) &\text{if $i, j > k$}
\end{cases}$$
Then iterate through $k = 1, \ldots, min(m, n)$.

Im not too sure my answer is correct. Any thoughts?


texts:
I would like to sample a uniformly random point in a polygon...

If sample a large number they'd be equally likely to fall into two regions if they have the same area.

This would be quite simple if it were a square since I would take two random numbers in [0,1] as my coordinates.

The shape I have is a regular polygon, but I'd like it to work for any polygon.

https://stackoverflow.com/questions/3058150/how-to-find-a-random-point-in-a-quadrangle


texts: Finding an algorithm to return the $\log n$ largest element in an array

texts:
I have just proved that for every $\alpha, \beta>0 : (\log n)^\alpha=O(n^\beta)$.
Now, given an array of $n$ elements, I want to find an efficient comparison based algorithm for finding the $\log n$ largest elements in the array, and returning them in sorted order.
I will appreciate your help on what is the best way to solve this question, and how should I think when countering such a question.


texts: Prove that context free languages are not closed under swapping prefixes and suffixes

texts:
Prove that context free languages aren't closed under this operation: $ A(L) = \{ zyx \mid x,y,z \in \{0,1 \}^*, xyz \in L \} $

Obviously, we need to find a context free language $L$ such that $A(L)$ isn't context free. Here are some of my failed attempts:

Take the language $ L = \{\ 0^n1^n \mid n \in N \} $ and then (since the intersection of a context free language with a regular language is context free) we get: $ A(L) \cap 1^*0^*1^*0^*  = \{\ 1^{m}0^{n-k}1^{n-m}0^{k} \mid n,k,m \in N, m,k\le n \} $ which might look promising at first, but unfortunately this language is context free...

I also tried my luck with the following languages:
$ L = \{\ 0^n1^m0^m1^n \mid n,m \in N \} $
$ L = \{\ ww^R \mid w \in \{0,1 \}^* \} $

but these languages didn't help me either...


texts:
For a binary tree we define horizontal distance as follows:

    Horizontal distance(hd) of root = 0
    If you go left then hd = hd(of its parent)-1, and
    if you go right then hd = hd(of its parent)+1.

The bottom view of a tree then consists of all the nodes of the tree, where there is no node with the same hd and a greater level. (There may be multiple such nodes for a given value of hd. In this case all of them belong to the bottom view.) I'm looking for an algorithm that outputs the bottom view of a tree.

Examples:

Suppose the binary tree is:

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

Bottom view of the tree is: 4 2 5 6 8 7

    Ok so for the first example,
    Horizontal distance of node with value 1: 0, level = 1
    Horizontal distance of node with value 2: 0 - 1 = -1, level = 2
    Horizontal distance of node with value 3: 0 + 1 = 1, level = 2
    Horizontal distance of node with value 4: -1 - 1 = -2, level = 3
    Horizontal distance of node with value 5: -1 + 1 = 0, level = 3
    Horizontal distance of node with value 6: 1 - 1 = 0, level = 3
    Horizontal distance of node with value 7: 1 + 1 = 2, level = 3
    Horizontal distance of node with value 8: 0 + 1 = 1, level = 4

    So for each vertical line that is for hd=0, print those nodes which appear in the last level of that line.
    So for hd = -2, print 4
    for hd = -1, print 2
    for hd = 0, print 5 and 6 because they both appear in the last level of that vertical line
    for hd = 1, print 8
    for hd = 2, print 7

One more example for reference :

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

So the output for this will be :
8 4 9 10 12 5 6 11 13 14 7 15

Similarly for this example
hd of node with value 1: 0, , level = 1
hd of node with value 2: -1, level = 2
hd of node with value 3: 1, level = 2
hd of node with value 4: -2, level = 3
hd of node with value 5: 0, , level = 3
hd of node with value 6: 0, level = 3
hd of node with value 7: 2, level = 3
hd of node with value 8: -3, level = 4
hd of node with value 9: -1, level = 4
hd of node with value 10: -1, level = 4
hd of node with value 11: 1, level = 4
hd of node with value 12: -1, level = 4
hd of node with value 13: 1, level = 4
hd of node with value 14: 1, level = 4
hd of node with value 15: 3, level = 4

So, the output will be:
hd = -3, print 8
hd = -2, print 4
hd = -1, print 9 10 12
hd = 0, print 5 6
hd = 1, print 11 13 14
hd = 2, print 7
hd = 3, print 15

So the ouput will be:
8 4 9 10 12 5 6 11 13 14 7 15

I already know a method in which I can do it using a lot of extra space (a map, and a 1-D array for storing the level of the last element in that vertical line) and with time complexity of $O(N \log N)$.
And this is the implementation of this method:

void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[], int l)
{
     if(node == NULL)
             return;
     if(level == 1){
              if(lev[hd-min] == 0 || lev[hd-min] == l){
                      lev[hd-min] = l;
                      visited[hd-min].push_back(node->data);
              }
     }
     else if(level > 1)
     {
          printBottom(node->left, level-1, hd-1, min, visited, lev, l);
          printBottom(node->right, level-1, hd+1, min, visited, lev, l);
     }
}

int main()
{
    find the minimum and maximum values for hd via DFS

    int lev[max-min+1]; //lev[hd] contains the maximum level for which we have found nodes with this value of hd; initialized with 0's

    map < int, vector<int> > visited; //the nodes in the bottom view

    int h = height(root);

    for (int i=h; i>0; i--){
        printBottom(root, i, 0, min, visited, lev, i);
    }

    output visited
}

I am seeking help to do this in more optimized way, which used less space or time. Is there any other efficient method for this problem?


texts: Must a min weight subset of edges connecting all vertices form a tree?

texts:
Got this question in an exam.

In a graph where all edge weights are positive, if a subset S of the edges connects all vertices and has minimum total weight, then the edges in S form a tree?

True or false?

This seems to be the definition of a MST, but since it doesn't state anything about cycles I'm not 100% sure.


texts: Is it a problem to be a programmer with no knowledge about computational complexity?

texts:
I've been assigned an exercise in my university. I took it home and tried to program an algorithm to solve it, it was something related to graphs, finding connected components, I guess.

Then I made the most trivial thing that came into my mind and then showed to my lecturer. After a brief observation, he perceived that the runtime complexity of my solution was inviable and shown something more efficient. And there is a tradition of programmers who have no idea on what is computational complexity (I was one of those), so is it a problem if a programmer has no idea on what is computational complexity?


texts: Canonical definition of suitable encoding

texts:
I've had several Computer Science courses and, from what I recall, I've never been given a rigorous definition of suitable encoding. Definitions always tend to use effective method or some synonym to define a suitable encoding, even though the reason we are defining suitable encodings is to formalize what an effective method is. I've recently discussed it with some of my classmates and we found a few necessary condition but could not find sufficient ones.

Let $X$ be set of things and $\Sigma$ an alphabet. An encoding is an injective function $e:X\to \Sigma^*$. The associated code is $e(X):=\{e(x) : x \in X\}$. Given a subset $P\subseteq X$, we say that it is $e$-decidable is $e(P)$ is decidable (as a subset of $e(X)$).

Given two encodings $e$ and $e'$, we call translation from $e$ to $e'$ the unique function $f_{e\to e'}:e(X)\to e'(X)$ so that for all $x\in X, f_{e\to e'}(e(x))=e'(x)$.

If $f_{e\to e'}$ is computable, then any $e'$-decidable problem is also $e$-decidable. We will therefore say that $e'$ is a better encoding than $e$ and write $e\rightsquigarrow e'$. Intuitively, we want the encoding to contains as little information as possible (so to minimize the set of decidable problems) but still have enough information to know which element we're talking about (hence the injectivity of $e$).

For example, for $X=\{(M,w):\text{ Turing machine and } w \text{ word}\}$, if we call $e'$ one standard encoding and $e(M,w):=e'(M,w)b$ where $b$ is $1$ if $M$ halts on $w$ and $0$ otherwise. The halting problem is $e$-decidable but not $e'$-decidable. The function $f_{e\to e'}(ub):=u$ is computable so $e'$ is a better encoding than $e$.

We say that two encodings are equivalent, and write $e\sim e'$ if $e\rightsquigarrow e'$ and $e'\rightsquigarrow e$. Given a suitable encoding $e$, the suitable encodings are exactly those equivalent to $e$. But I feel like there should be some way to define suitable encodings without needing to give a specific one.

Let $e'$ be a an encoding so that for any encoding $e$, if $e\rightsquigarrow e'$, then $e'\rightsquigarrow e$ (and $e\sim e'$). We will call $e'$ a minimal encoding. An minimal encoding is an encoding better than any encoding it is comparable to. If $e\sim e'$, $e'$ is minimal iff $e$ is.

And encoding $e$ is called decidable if $e(X)$ is. If $e\sim e'$, $e'$ is decidable iff $e$ is.

A suitable encoding should probably be minimal and decidable but that doesn't seem to be enough to characterize them. Intuitively, there seems to be several equivalence classes of minimal decidable encodings, but there is only one that really represents what we want to call suitable encodings.

A solution could be to add "If an encoding $e$ is suitable, then for any $e'$, any non $e'$-decidable problem is not $e$-decidable.". But I'm pretty sure one can build a minimal decidable encoding for integers so that beeing even is undecidable. Let $(M_n)_n$ be an enumeration of Turing machines. We can extract two subenumerations $(M_{\varphi(n)})_n$ (resp. $(M_{\psi(n)})_n$) of machines that halt (resp. do not halt) on all inputs. Then we define $e(2n)=e'(\varphi(n))$ and $e(2n+1)=e'(\psi(n))$ where $e'$ is some suitable encoding.

Another idea is to say that the suitable encodings must somehow be more robust and so its equivalence class must be bigger. But both will be countable...


texts: Is there a term for the distribution of numbers-of-digits of a bounded uniform distribution

texts:
Let $X$ be an integer sampled uniformly from the (integer) range $\{ 0...2^k - 1 \}$ .

Now, consider the distribution of

$\#\text{bits}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log_2(X) \rfloor & \text{otherwise}
\end{cases}$

and

$\#\text{bytes}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log_{256}(X) \rfloor & \text{otherwise}
\end{cases}$

which are the numbers of bits and of bytes respectively necessary to hold $X$.

My question: Is there some commonly-used term for the one of the distributions of $\#\text{bits}(X)$ or $\#\text{bytes}(X)$ ? Or for a distribution which is very similar to them?


texts:
I wonder what will be the complexity of this algorithm of mine and why, used to check whether a graph (given in the form of neighbors list) is bipartite or not using DFS.

The algorithm works as following:

We will use edges classification, and look for back edges.

If we found one, it means there is a circle in the graph.

We will now check whether the cycle is odd cycle or not, using the the pi attribute added to each vertex, counting the number of edges participating in the cycle.

If the cycle is an odd one, return false. Else, continue the process.

Initially I thought the complexity will be O(|V| + |E|) as |V| stands for the number of vertices in the graph, and |E| stands for the number of edges in the graph, but I am afraid it might take O(|V| + |E|^2), and I wonder which option is correct and why (it may not be any of the above as well). Amortized or expected run times may also be different, and I wonder how can I check them as well. Please help me figure!

pseudo code

DFS(G=(V,E))
// π[u] – Parent of u in the DFS tree
1 for each vertex u ∈ V {
2 color[u] ← WHITE
3 π[u]← NULL
4 time ← 0}
5 for each vertex u ∈ V {
6 if color[u] = WHITE
7 DFS-VISIT(u)}

and for the DFS-Visit:

DFS-Visit(u)
// white vertex u has just been discovered
1 color[u] ← GRAY
2 time ← time+1
3 d[u] ← time
4 for each v ∈ Adj[u] { // going over all edges {u, v}
5 if color[v] = WHITE {
6 π[v] ← u
7 DFS-VISIT(v) }
8 else if color[v] = GRAY // there is a cycle in the graph
9 CheckIfOddCycle (u, v);
10 color[u] ← BLACK
// change the color of vertex u to black as we finished going over it
11 f[u] ← time ← time+1

and as for deciding what type of cycle is it:

CheckIfOddCycle(u, v)
1 int count  ← 1;
2 vertex p = u;
3 while (p! = v) {
4 p ← π[p]
5 count++ }
6 if count is an odd number {
7 S.O.P (“The graph is not bipartite!”);
8 stop the search, as the result is now concluded!

Thanks!


texts: product of fully time constructible functions is fully time constructible

texts:
How would you prove that product of two fully time constructible functions is fully time constructible?
I managed to prove for sum, but product seems more complicated


texts: Proof that pseudorandom generators implies one-way function

texts:
I'm reading proof on Wikipedia that the existence of pseudorandom generators implies the existence of one-way functions.
My understanding is that pseudorandom generators are defined as

A function $G_l:\{0,1\}^l\to\{0,1\}^m$ is a pseudorandom generator if all of the following hold:
a. $l<m$
b. $G_l\in\mathbf P$
c. For any polynomially-sized circuit $C$,
$$ \left|\Pr_{x\sim\text{Unif}\{0,1\}^l}[C(x)=1]-\Pr_{x\sim\text{Unif}(D)}[C(x)=1]\right|<\text{poly}(n),
 $$
where $D$ is the image of $G_l$.

and that one-way functions are defined as:

A function $f:\{0,1\}^n\to\{0,1\}^n$ is a one-way function if all of the following hold:

$f$ is invertible
$f\in\mathbf P$
For any polynomially-sized circuit $C$,

$$
 \Pr[f(C(f(x))=f(x)]<\text{poly}(n).
 $$

Question 1: Looking at definitions for one-way functions above, I assume that the notation $f:\{0,1\}^n\to\{0,1\}^n$ refers to a family of functions $\mathcal F=\{f_n\}_{n\in\mathbf N}$, where each $f_n$ is an invertible function $\{0,1\}^n\to\{0,1\}^n$. (And analogously for the defintion of pseudorandom generators.) Is this assumption correct?
The proof that pseudorandom generators implies one-way functions given on the Wikipedia page starts off with:

Consider a pseudorandom generator $G_l:\{0,1\}^l\to\{0,1\}^{2l}$. Let's create the following one-way function $f:\{0,1\}^n\to\{0,1\}^n$ that uses the first half of the output of $G_l$ as its output. Formally,
$$
f(x,y)\to G_l(x)
$$

Question 2: What exactly is this saying? It looks like $|x|+|y|=n$, so I'll assume for now that $|x|=l=n/2$, in which case $G_l(x)$ outputs a string of length $2l=n$.  But if $G$ ignores $y$, how can $f$ be injective?
Thanks!


texts:
On page 17 on the paper Online Learning with Predictable Sequences, we find a regret of an algorithm equal to

$$
\text{Reg}_T=\frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1)
$$
where $T$ is the entire time, $\eta$ is learning rate, $R$ is constant, and $\sigma^2$ is the variance of data. The above using arithmetic mean-geometric mean inequality can be lower bounded by

$$
\sqrt{2}R\sigma\sqrt{T+logT+1}\leq \frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1)
$$

why the left hand side is $\tilde{{O}}(\sigma\sqrt{T})$?

According to $\tilde{{O}}$ vs $O$, $\tilde{{O}}$ ignores logarithmic factors that means when $f(n) \in \tilde{O}(g(n))$ there exist a $k$ such that $f(n) \in O(g(n)\log^k g(n))$, now I have $f(T)=\sqrt{2}R\sigma\sqrt{T+logT+1}$, why I can write it $O(\sigma\sqrt{T}log^kT)=\tilde{O}(\sigma\sqrt{T})$? and what is my $k$?


texts: Are most machine learning problems the same problem? (NP-hard)

texts:
I am trying to teach P vs NP to some primarily Machine Learning folks. I wanted to come up with an introductory fact to grab their attention.
Reasoning for Question:

Most problems in Machine Learning are NP-hard.

2/3. All NP-Hard problems are the same problem - per reduction unto each-other in trivial poly-time.

Thus, it is the case that most Machine Learning problems are actually just the same problem in a different disguises. Is this true?
Timestamped: https://youtu.be/YX40hbAHx3s?t=406
An estimate on what percent of Machine Learning algorithms are NP-hard would be helpful. For example, regression is not NP-hard, but I was told that the fact that a closed form solution exists for that particular problem is a "miracle". I use the term most loosely. Many will also work.


texts: Find the length of the longest subarray having sum greater than k

texts:
I tried to solve this problem but could not do it better than $O(n^2)$.
My Algorithm:
1. Calculate prefix sum

2. for i in 1..n:
     for j in 1..i:
       if presum[i] - presum[j-1] > k:
          ans = max(ans, i - j)

Edit: I have found a solution which works in $O(n\log n)$. This solution does a binary search on the length of the subarray and chooses the maximum length of the subarray satisfying the property.
The code is as follows:
#include<stdio.h>
long long int a[1000005]={0},sum[1000005]={0},n,k;
long long int check(long long int len)
{
long long int i,c=0;
for(i=len;i<=n;i++)
{
 if((sum[i]-sum[i-len])>=k)
   c++;
}
 return c;
 }

int main()
{
 long long int i;
 scanf("%lld",&n);
 scanf("%lld",&k);
 for(i=1;i<=n;i++)
  {
  scanf("%lld",&a[i]);

  sum[i]=a[i]+sum[i-1];
  }
 long long int low=0,high=n,ans=0,count=0;
 while(low<=high)
 {
  long long int mid=(low+high)/2;
  long long int p=check(mid);
  if(p>0)
  {
   ans=mid;
   low=mid+1;
  }
  else
  {
  high=mid-1;
  }
}
if(ans==0)
    printf("-1\n");
else
    printf("%lld\n",ans);
return 0;
 }

My doubts: How does this algorithm discards the search space?
More specifically, what I want to know that suppose there does not exist any subarray of length $len$, then how can we show that there won't exist any subarray of length $>len$. The above code does the same way, whenever there does not exist any subarray of length $mid$ it removes the other half and continues to search for an answer in the lower half by decreasing the $high$ to $mid-1$.


texts: Conversion of fractional part of a hexadecimal number to binary

texts:
The Number is given as : (C012.25)Hexadecimal
I have to convert it into octal .
So I converted it into Binary First and got the result as : 1100000000010010.01000000
(Since each bit in hexadecimal represents 4 bit in binary so C=1100,0=0000,1=0001,2=0010 and for 0.25=.01000000 )
The Solution mentions the Binary conversion as 1100000000010010.00100101
Please guide me about the what was done wrong !
Also if I got the binary representation...How can I convert the binary no's fractional part (0.00100101) into octal .


texts: Can a language be the one recognized by more than one automatons?

texts:
The language recognized by an automaton is defined as the set of strings that are accepted by the automaton.

I wonder if it is possible that the languages recognized by two automatons are the same? Note, if I am correct, the most general automatons are the Turing machines, and the languages recognized by an automaton are exactly the recursively enumerable languages.

The same question if restricted to the commonly-known subfamilies of languages and their corresponding automatons (e.g. regular languages, context-free languages, context-sensitive languages)?

Thanks.


texts: Minimum number of swaps in sorting sequence

texts:
Given an array of N integer elements (not necessarily distinct), what is the minimum number of swaps (not necessarily adjacent) needed to sort the array?

I've been struggling with this problem for a few months now. I know that the elements are distinct, the answer is the number of cycles in the permutation obtained after normalizing the values and that if the swaps are adjacent bubble sort obtains the optimum number of swaps, but nothing about this one. This question asks the same, but the answers only consider distinct elements.

My approach to the problem is graph theoretical, considering a graph with a node for each element value, drawing an oriented edge from $a$ to $b$ whenever a value $a$ lies at a position where $b$ should lie in the sorted array ($a \neq b$, so no loops), the answer being the maximal (partition with most equivalence classes) partition of the edges into simple cycles (a generalization of the solution for arrays with distinct elements).

Does this problem have a known name? Any references? Any polynomial solution or complexity class ownership (P, NP, graph isomorphism equivalence etc)?


texts: What's the complexity of solving a packing LP?

texts:
Linear Programming is in polynomial time weakly
(when numbers are encoded in unary).
AFAIK it remains open if it is possible to solve LP
in polynomial time strongly (when numbers are encoded in binary).

My questions is about a special subclass of LP called Packing LP:

  Packing LP
  Variables: $\vec{x}$
  Constraints:

  $A\vec{x} \leq \vec{b}$
  $\vec{x} \geq 0$

  Objective: $\max \vec{c}^T \vec{x}$
  where $\vec{c} > 0$, $\vec{b} > 0$, and $A \geq 0$ (component-wise)

Is there a strongly polynomial-time algorithms for Packing LP or
is it "nearly as difficult" as solving LP in general?

I am interested in exact algorithms.
For approximation,
there is a strongly polynomial-time FPTAS for Packing LP
according to [Garg and Könemann, 2007].


texts: Shortest path including all nodes in a subset

texts:
Given a directed graph $G=(V, E)$, two nodes $s, t \in V$ and a subset of nodes $U \subseteq V$.
Provide an algorithm that determines if there is a shortest path from $s$ to $t$ that passes via all nodes in $U$.
I came across a solution that starts with the following steps

Run BFS on G, notate $d_s(v) \quad \forall v \in V$
Calculate $G^T$ (transposed graph)
Run BFS on $G^T$, notate $d_t(v) \quad \forall v \in V$
Build $G^{'} = (V, E^{'})$ where $E^{'} = \{(u,v)\in E | d_s(u) + 1 + d_t(v) = d_s(t)\}$

I don't quite understand the intuition for this specific build. It resembles the building of G scc with DFS which doesn't contribute much to my understanding.
Why would I want to build the graph this way and not use the shortest-path-tree I got from the first BFS execution?
EDIT: continued algorithm steps are:

Run topological sort on $G^{'}$, notate the result with $a_1, a_2,...,a_k$.
Initialize field $c(v)=0 \quad \forall v \in V$
Initialize starting node $v \leftarrow t$
For all v in the reverse topological order do: (until arriving at s)
{
$\forall (x, v) \in E^{'}$
{
if $v \in U, c(x) \leftarrow max\{c(x), c(v)+1\}$
else $c(x) \leftarrow max \{c(x), c(v)\}$
}
}
Return $c(s) == |U|$


texts: Adaptive Subsampling Bilinear Interpolation in Screenspace

texts:
The test-object is a signed distance function that is computed with ray-marching. When the ray hits an object the intersection-flag is set to 1 or otherwise set to 0. To speed up the process (since all of the computation is done on the native CPU) I implemented adaptive subsampling in screenspace. The following image shows that the subdivision works successfully:

Each of these blocks has four corners that consists of a hash structure, that by the time of writing contains: objectID, color and intersection-flag. The problem I have is that in my first successfull-test interpolating the subdivided blocks causes edge-artifacts or colors that does not align with the neighbouring blocks. I have tested the bilinear interpolator and it is working, but it does not seem to be working like expected, although some documents on this subject suggests that this is the right way to do it.

Any ideas how to fix this issue when the adaptive subsampler is based on a recursive algorithm to speed up the rendering?

Thanks


texts:
I recently learnt that a recursive function is also referred to as a circular function.

See, the recursive function cannot be a circular function because even if there is a call to function itself, it does not happen indefinitely. There is always a base case (or condition) from where the function is supposed to exit in one way or the other (either by displaying some message or returning some value).

So, is calling recursive function, a circular function not a misnomer ?


texts: Given Directed Graph G(V,E) with red/black vertices, v is good if there's a path from v to a black vertex

texts:
Given Directed Graph G(V,E) with red/black vertices, v is "good" if there's a path from v to a black vertex. in linear time.

Question: Find all the good vertices in the graph

I've come up with an algorithm which almost works.

Run SCC on G.
Sort topologically.
Run from the last SCC till the first SCC.
If we find a black node, return all the previous SCCs nodes and the current SCC's nodes (because all the nodes are reachable in the SCC).

This algorithm fails because there may be SCC's which are not connected to the SCC that we found the black node. How can I fix the algorithm to work?


texts: Understanding the heuristic used for approximate string searching through an FSA

texts:
The paper I'm looking at: Fast approximate string matching with finite automata (2009)

Explanation of the algorithm (from my understanding anyway):

A word is inputted into the automaton and from each state, a number of possible actions can be taken depending on the current symbol/character being looked at at position $pos$. These "actions" include:

Staying at the current state and deleting the character currently being pointed at by $pos$.
Taking a transition to a next state and substituting the current
character at $pos$ with the transition label used.
Taking a transition to a next state and inserting the transition
label at $pos$.

The action is decides to take is based on a cost function $f=g+h$ (where the lowest $f$ is chosen) for each action.

$g = 0$ if no edit operation is performed on the input word (i.e. the transition label taken to a next state, is the same as the current character at pos) and $g=1$ otherwise.

$h$ is the maximum between two heuristic functions $h(2)$ and $h(\infty)$.

$h(2)$ looks at the transition labels that can be reached within two
transitions from that state (note, not the current state) and
compares those reachable transitions to the next two characters in
the input word after $pos$. $h(2)$ gets $+1$ added for each character in
the input word that does not match any of the characters that the
state $s$ can reach within two transitions.
$h(\infty)$ looks at the transition labels that can be reached until
the end of the path from that state and compares that to the rest of the input word after pos. As with $h(2)$, $+1$ for each character in the input word that can't be matched to any of the reachable characters from state $s$.

Eventually this algorithm will lead to some accepting state where the path up to that accepting state is the closest accepted word to the input.

I think I understand the algorithm correctly since I tried to implement it from my understanding in Java (I'm doing it for my project, although my project only handles regular expressions of a small alphabet of around 3 different symbols as opposed to a natural language dictionary) and it seems to work to some extent and works fine for the example given in the paper, however my problem is is that I don't understand what priority is used in the case where $f$ values tie for $f=g+h$ (tied $f$ values are actually common).

The example used in the paper, inputs the word "dat" into the automaton, what I don't understand is why the algorithm goes from state 0 to state 3 (I circled this part in red) when $f=g+h$ is also 1 for the state 0 choice (I circled this part in blue).

The paper mentions

  "ties were resolved in the priority queue by giving priority to the highest word position."

but I don't understand what is meant by this.

It also mentioned:

  "In our experiments, the strategy of breaking ties so that the node that has advanced farthest in the word to be matched is given priority has proven to be far superior to any of the tiebreaking strategies we explored."


texts: How can I convert a binary number to a base-4 number with a Turing Machine?

texts:
I'm looking for some guidance to get me going. I assume (and please correct me if I'm wrong) that it'll need 2 tapes and by reading various resources, I found that it might be easier with the binary string reversed.

In any programming language, I would first convert the binary string to decimal, but is this needed/a good idea?

Also, how many states would I need?

Any kind of articles, or hints on the subject would be much appreciated!


texts: Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?

texts:
I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3):

"More precisely, for any
polynomially bounded collection of weight assignments $\{w_i\}$ $i \in [n^c]$ with weight range $[n^{c'}]$, there exists a
family $F$ of subsets of $[n]$ such that for all $j \in [n^c]$, there exists two minimal weight subsets with respect to $w_j$.

They claim that this follows from a counting argument that uses the existence of $2^{(2^n)}$ set systems. The article they cite does not contain a proof of this assertion.

Question: What proof are they thinking of? Why is their claim true?


texts: How is Memory Access Time of Processor calculated?

texts: In the Art of Assembly ebook, I have read that 8088 processor require four clock cycle to access memory (in whatever clock speed & memory speed is). How is it calculated? Is it time for processor to prepare for calculate address and put data on the bus?


texts:
I have the following basic BNF grammar:

<A>   -->  <id>  = <E>
<id>  -->  A | B | C | D | F
<E> --> <E> + <T> | <T>
<T> --> <T> * <F> | <F>
<F> --> <E> | <id>

Operator (*) should have higher precedence over (+).
However, see this statement:

A = A + B + C + D * F

The leftmost derivation (and parse tree) indicate the opposite! i.e., (+) has higher precedence than (*) since it will show up lower in the parse tree!

What am I missing here?


texts: Is there a way to determine if a collection is a palindrome within a time bound?

texts:
I'm learning about data structures, and there's a problem where, given a collection of words $X = (x_1, x_2, \dots, x_n)$ (can include duplicates), I have to find out if it's a palindrome or not. I'm looking for an algorithm that runs in $O(c n)$ time, where $c$ is the maximum length of any word in $X$.

A collection is a palindrome if all the characters in $X$ can be rearranged into a palindrome.  For example, $X =$ (nun, ap, pa) is a palindrome (since apnunpa is) and (run, urn, appa) is a palindrome (since apurnnrupa is).  The characters can be re-ordered, even within a word. The alphabet is also limited and finite.

I read about palindrome trees, but the question can be answered with a basic data structure. Any ideas on how to design an algorithm with worst-case running time $O(n)$?

Original Question:

My main question is what implementation would be best for find if a collection is a palindrome. The best one I found to remain within the time constraints would be a binary heap. What I don't get is how I can check if the characters can form a palindrome or not. My normal implementation would be to form combinations of all then check if its a palindrome, which is O(n!). Any ideas on what method works?


texts:
Let suppose a simple (FIFO) queue, where elements enter at a side and exit at the other side.

I know the classical use of queues in everyday life and computer networking. I would like to know more specific uses, for instance in distributed applications.

Are there client-server applications where we need to investigate elements of the queue which are not at its extreme sides ? (that is, elements which are not the first and the last of the queue).

Thank you.


texts: Where can I download some interesting cellular arrays for Conway's Game of Life? Arrays such as the Gosper glider gun, etc? I can find the images easily enough, but are they available somewhere in binary format? And is there an orderly library somewhere?


texts:
I have some questions regarding local search / optimization as explained in chapter 4 of the book : http://aima.cs.berkeley.edu/

In classical search (Chap 3), the search starts from an initial node, then the search continues based on strategies of BFS, DFS, etc. What I am unsure of is the process of local search (Chap 4).

Does the local search algorithm start from one node in state space? Check if constraints are satisfied? If Yes, this is goal? If not, move to neighbours?
Is the entire state space considered goal state? Even nodes that don't satisfy the constraints?
In optimization, the search is conducted in a part of search space where all constraints are met, but tries to find a better solution. In that case, what if the search algorithm moves to nodes where they don't satisfy the constraints?


texts:
I want to train a Perceptron using stochastic gradient rulefrom the stream data. I have very limited amount of memory and i can store only $N$ examples.

Suppose my population consist of point as show in the following picture:

Now suppose my first $N$ examples come in following fashion and i can classify them correctly as show in the next picture:

Now the problem is if the next $N$ examples come in this way:

and i have classified them as shown. The problem is that since i can't train perceptron for previous $N$ examples(because i can store only $N$ examples and previous $N$ examples need to be thrown away) and training on next $N$ examples contradicts the hyper-plane for previous $N$ examples.

How to train a perceptron from stream data? Do i need to store all examples or there is an alternative way?


texts: How do we evaluate semantic actions in L attributed SDT?

texts:
I came across following problem:

  $S→ER$
  $R→∗E\{print(′∗′);\}R∣ε$
  $E→F+E\{print(′+′);\}∣F$
  $F→(S)∣id\{print(id.value);\}$
  Here $id$ is a token that represents an integer and $id.value$ represents the corresponding integer value. What does this translation scheme prints for an input "$2∗3+4$"?

Here are things I am able to understand:

Since semantic actions are placed in between, but not at the end of production, this is L attributed grammar.
L attributed grammar is parsed left to right in depth first manner.
I know that semantic actions associated with synthesized attributes should be evaluated when the corresponding node is last visited during traversal (that is in postfix order) since all its children need to be evaluated first in order for parent node to synthesize its value from children.
The semantic actions associated with inherited attributes should be evaluated at first time their corresponding node is visited.

I am able to prepare parse tree for the given string:

But I am not sure how should I be evaluating semantic actions. Here, no attribute derives its value from other (all are print statements). Thus, it seems that this is both synthetic and inherited (or should I say L attribute?). Since this is also synthetic, I felt I should evaluate semantic actions when I visited the corresponding nodes at last time, i.e. in postfix order yielding "$234+*$". Is this correct? I feel I miss very basic major concept here...


texts: Computer Vision Techniques to find Slope of beach in the 2D Images?

texts:
What I am planning to do is to calculate the height and estimate the slope of the segmented Object. The camera will be static and the Object of Interest is the slope of the beach.
I am finding harder to use depth camera, as the minimum distance between slope and camera is 150 meters.

I have tried Unet Semantic Segmentation with two classes i.e. background and sand surface. After semantic segmentation what i left with is the sand surface, but i am struggling to find slope height; as one out of many options that i have tried is to run canny filter on 2D image and convert the segmented sand surface into 3D, but the distance between camera and sand surface is around 200 meters, therefore i am reluctant to use any of the 3D reconstruction approach.

And also i am not sure of any depth cameras which can cover up to 200 meters of range.
Please see the attached Picture for more information. If you require more information please let me know, :)
Thanks for your help !!!.


texts:
I was looking in here, and I noticed the best runtime for multiplication of two $n$-bits numbers is $O(n\cdot \log n \cdot 2^{O(\log^* n)}$, but I can easily notice an algorithm that runs in $O(n\cdot \log n)$.

After all, we know how to multiply two polynomials from degree $n$ in $O(n \log n)$ runtime. But multiplying polynomials is the same as multiplying two $n$-bits numbers. So we have an algorithm to multiply two $n$-bits numbers in $O(n \log n )$. Now the only problem that might occur is the carry, but in each phase we can fix that in $O(n)$ time, simply moving on the rightest bit and its left-neighbour, until the end. That is, our runtime shall remain $O(n \cdot \log n)$.

So did I make a new (and pretty obvious) discovery? Or is the wikipedia page out of date? Or perhaps I have some mistake?


texts: Algorithm to select elements from a ranked list of lists

texts:
I have a list of lists of objects. Each of the lists of objects is ranked according to a numeric field of the object. The big list is ranked according to the highest numeric value of the field of all the objects in a list of objects.

I want to select elements from each of the lists of objects, but obviously want to weight elements which are ranked higher more heavily. I also want diversity in my selection, i.e., I want some objects from every list, and for objects from any one single list to be spread out.

Can anyone suggest an algorithm? Or perhaps are there any academic papers you can refer me to, or a general topic/famous problem that this problem is related to? Thanks.


texts: A Turing Machine with undecideable Halting Status not relying on Open Problems

texts:
Is there any turing machine that it is proovably known to be undecideable, it has to fullfit the following characteristics:

Not rely on Open Problems/ Conjectures
Should not use the same machine used in diagonalization proof

In other words, is there an alternative proof that Halting problem is undecideable (other than diagonalization)?


texts:
Unfortunately (like many other authors) Fenwick does a very bad job of explaining his work (the Binary Indexed Tree) in the original text. The paper lacks a proper formal proof of why this structure should work and only provides examples. This seems to be a very widespread issue regarding this topic and no tutorial or blog post out there seems to prove the correctness of this beast.

Just to be clear, I'm not looking for intuition or an explanation of how this data structure works, I already know that, what I am asking for is a formal proof that says a tree built this way will do what it is supposed to do correctly.

There is already another question here, with a very detailed and well-written answer that still doesn't provide a proof (though the question didn't really ask for proof either) and also seems to rely on a logic much different from what is presented in the original paper so please do not mark this as a duplicate.


texts: What is the difference between symbol and enumerated datatypes?

texts:
I wonder what differences and relations are between symbol and enumerated types?

A symbol is a primitive datatype whose instances have a unique human-readable form
an enumerated type is a data type consisting of a set of named values called elements, members or enumerators of the type.

Since a data type is a set of values, what exactly is the data type "symbol",  and the data type "enumerated"?
It seems to me that a value in an enumerated type is just a symbol.
But the first quote says that "A symbol" is a data type, which contradicts with my thought that a symbol is a value.


texts:
I have encountered the following problem.

We have $N$ points in discrete coordinates,distributed through a plane with vertical axis $[1..Y]$ and horizontal axis $[1..X]$.
We can perform the action of removing all points with vertical coordinate $y$, in short removing $y$.

What is the least number of $y$'$s$ we must remove so that the number of $x$ that have points is less than $X/2$.
For example in the graph above removing 1 and 2 leaves points only in 1,3,6,9.

This seems like a NP-complete problem to me so the only solution I have developed is removing all combinations of $y'$s. I would be grateful if someone experienced in computation-theory could point me to a similar known problem (or maybe a problem this could be reduced to), any suggestion is welcome.


texts: Floor or Ceiling when getting results for N after doing Big O and Big Theta?

texts: I'm working on my data structures homework and proving Big O and Big Theta for a couple questions.  After choosing my values for C and getting to the end I'm left with the fraction 1/300 for $N_0$ for both Big O and Big Theta.  I understood from lecture that we actually take the ceiling of the fraction for Big O, making it 1.  My question is, do I also take the ceiling of Big Theta, or would it be the floor?  Since Big Theta is a lower-bound.


texts: Are there other ways to describe formal languages other than grammars?

texts: I'm looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies.


texts: Is it possible for a hash table's load factor to exceed 100%?

texts: Using probing, is it possible for for a hash table's load factor to exceed 100%? I don't too much about Hash Tables. Is this possible?


texts: What is the state of the art in encapsulated search in functional logic programming?

texts:
I am particularly interested in solutions to the problem that encapsulated search can depend on the order of evaluation.

According to [1], encapsulated search in PAKCS depends on the order of evaluation, while in MCC, it does not, but using it requires knowledge of the compiler implementation and it does not follow the Curry language specification. This was written in 2007, so it may of course be out of date now.

KiCS2 returns results from encapsulated search in the IO monad, but I do not understand why.

[1] Braßel and Huch, On a Tighter Integration of
Functional and Logic Programming, Proc. APLAS 2007


texts: Question about termination of term rewrite systems

texts:
Let $\mathcal{R} = (R, \Sigma)$ be a term rewrite system over a signature $\Sigma$ with set of basic rewrite rules $R$. It is known that $\mathcal{R}$ is terminating IF every basic rewrite rule $l \to r \in R$ has the following two properties:

The length of $l$ is strictly greater than the length of $r$.
For any variable $x$, the number of occurrences of $x$ in $l$ is $\geq$ the number of occurrences of $x$ in $r$.

I don't think that the converse is true (e.g. the term rewriting system for the theory of groups is terminating, but the first condition fails for the associativity rule). But if we know that $\mathcal{R}$ is terminating, can we perhaps say something similar but slightly weaker about the basic rewrite rules of $\mathcal{R}$? For example, if $\mathcal{R}$ is terminating, then must it be the case that every basic rewrite rule satisfies (2), and is such that the length of the left term is equal to or greater than the length of the right term (rather than strictly greater)?

In sum, I'm wondering if we can conclude anything about the syntactic properties of the basic rewrite rules of $\mathcal{R}$, if we know that $R$ is terminating.


texts: Example divide and conquer algorithm with recurrence T(n) = T(n/2) + O(n)

texts:
I'm working on some lecture notes and wondered if there was a good example algorithm for the recurrence equation

$$T(n) = T(n/2) + n$$

I know that I can do selection in this running time, but that is a probabilistic algorithm, and I was hoping not to introduce this algorithm at this point in my lecture notes. I plan to introduce the selection problem in a later chapter after describing quick-sort. Is there a good example of an algorithm that has this recurrence equation as worst-case?


texts: Does a notion of a context-free complete language exist?

texts: Is there a notion of a context-free complete language (in the analogous sense to a $NP$-complete language)?


texts: If a language L is regular then the given operation sort(L) is context free

texts:
I was asked in one of my homework tasks this next question and I'm not quite sure how to handle it:

Sort(w) is an operation which takes a string (w) from a given language and sorts the characters in an ascending order. Sort(L) is the outcome language of the operation Sort(w) on each and every string (w) in the language L.
I was asked to prove or disprove the following claim:

  If L is a regular language over the alphabet {0,1} where 0<1 then sort(L) is context free.

I would appreciate any hints or clues on how to approach this type of question.


texts:
I am attempting to match human input of titles to a list of titles, and also show likely candidates when a human enters a title not known.  Ideally I'd also have some way to suggest the human input of a truly novel title matches no known title as well.
As an example, I have a list of titles like this:
The Conspirators
The Count of Monte Cristo
The Three Musketeers
The Fencing Master

Only, my real list of titles is on the order of tens of millions long, and includes titles in different languages, including non Latin based languages.
And, as a human enters titles like these, I am attempt to find the proper name, here are examples of what humans might enter for The Three Musketeers:
The Three Musketeers
The 3 Musketeers
Three Musketeers, The
The.Three.Musketeers
the-three-musketeers
thethreemusketeers
The Three Musketeers-1844
Three Musketeers
THE THREE MUSKETEERS

For lack of a better term, at present, I'm attempting to "normalize" the titles.  For instance, that means I:

Convert input to a known case
Remove why whitespace (or characters acting like whitespace, like the - and . above)
Remove extraneous information (like 1844 above)
Fix up common issues, like replace and with &
Other domain specific fix-ups

This is done once on the known good titles, and whenever a user enters a title, a simple database lookup is done.  In the case of multiple titles matching, domain specific guesses are made (for instance, a book with more reviews wins over other options).
This works, but it requires a lot of custom logic in the string normalization, and what's worse, it requires knowledge of multiple languages.  And if users suddenly start following a new trend, like as a made up example, use = instead of spaces, then there needs to be a feedback loop where someone reviews common "misses" in the search and updates the string normalization logic.
Some other options I've briefly looked into:

Phonetic matching algorithms, like Soundex.  These sometimes work, but some of the human input doesn't sound like the target word, and these systems tend to require I know the target language, which I don't always know.
Machine Learning.  I'm at a loss here, most of the systems I've read about require cleaning of human input, which if I can do, I can match without any ML systems.
n-gram based fuzzy matching.  Much like the phonetic matching systems, this requires knowing the language, and cleaning up the text to some degree beforehand.  Also, most of the systems seem to require a lot of compute power to perform the lookup, which is a concern.

Are there better techniques to apply to this problem to find the real title from the human input?


texts:
Is English Turing-complete?
Intuitively it makes sense that English is Turing complete, since you can talk someone through building a Turing machine. But I also think there might be some operators used in programming that aren't used in person-to-person communication, at least in daily life.
Also, what level of English is required until it becomes Turing complete? For example: 1st grade? College level?


texts:
Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$

My approach was to reduce this from the Hamiltonian path and I know I should somehow force the solver to go through as many vertices as it can to get a Hamiltonian path but I am not sure how to construct such a reduction


texts: What is the right term/theory for prediction of Binary Variables based upon their continuous value?

texts:
I am working with a linear programming problem in which we have around 3500 binary variables.

Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best bound. In the solution, we get around 85-90 binaries which have value of 1 and others are zero. The objective value is around 20 to 30 million. I have created an algorithm in which I am predicting (fixing their values) 35 binaries (with the value of 1) one by one and letting the remaining ones solved through the Cplex. This has reduced the time to get the same objective to around 24 hours (the best bound is slightly compromised). I have tested this approach with the other (same type of problems) and it worked with them also. I call this approach as "Probabilistic Prediction", but I don't know what is the standard term for it in mathematics?

Below is the pseudocode:

Let y=ContinousObjective(AllBinariesSet);
WriteValuesOfTheContinousSolution();
Let count=0;
Let processedbinaries= EmptySet; //Binaries processed per iteration.
while (count < 35 ) {
    Let maxBinary =AllBinariesSet.ExceptWith(processedbinaries).Max();//Having Maximum Value between 0 & 1 (usually lesser than 0.6)
    processedbinaries.Add(maxBinary);
    maxBinary=1;
    Let z = y;
    y = ContinousObjective(AllBinariesSet);
    if (z > y + 50000) {
        //Reset maxBinary
        maxBinary.LowerBound = 0;
        maxBinary.UpperBound = 1;
        y = z;
    } else {
        WriteValuesOfTheContinousSolution();
        count=count+1;
    }
}

Explanation of the pseudo code:
Step 1: Initialize an empty list of processed binaries.
Step 2: Run the continuous solution and get the binary which has maximum value and not the part of processed binaries. Add that binary to processed binaries list.
Step 3: Fix the value of that binary to 1 and run the continuous solution again.
Step 4: If the objective is not around 99.75% of previous objective then revert to Step 1 and add the fixed binary to the list of ignored binaries.
Step 5: Repeat from Step 1 to Step 3 until we have fixed 35 binaries in the LP.
Step 6: Start the integer optimization run (mipopt in cplex) of the fixed LP.

So basically we are predicting around 40% of the binaries (with the value of 1) and at every iteration we are ensuring that the continuous objective is not reduced below 0.25% (approx. 50000) of its actual value before the previous prediction.
According to me, it's working because the solution matrix is very sparse and there are too many good solutions.


texts: Why do we distinguish between term abstraction and type abstraction in System F?

texts:
In System F, we distinguish between types and terms. Types are defined by the following BNF:

\begin{align}
A, B ::=&~\alpha && \text{(type variable)} \\
       &|~A \rightarrow B && \text{(function type)} \\
       &|~\forall \alpha. B && \text{(universal quantification)}
\end{align}

Terms are defined by the following BNF:

\begin{align}
t, u ::=&~x && \text{(variable)} \\
        &|~\lambda x : A. t && \text{(term abstraction)} \\
        &|~t~u && \text{(term application)} \\
        &|~\Lambda \alpha. t && \text{(type abstraction)} \\
        &|~t~A && \text{(type application)}
\end{align}

Can term abstraction and type abstraction be combined into a single binder? Similarly, for term application and type application? As a programmer, this distinction between terms and types at the term level seems wasteful to me. However, I'm sure that there must be a good reason for it.


texts: Examples for speech recognition systems and spoken dialogue systems

texts:
I am collecting material for a MOOC about speech technology. My aim is that students also have examples to try rather than just watching the lecture and some complimentary youtube videos. So the idea was that they could call up some spoken dialogue systems or something like that. I have quite a few phone numbers of spoken dialogue systems in german (e.g. +498003504030) but as the course is going to be taught in english I am searching for examples in the english language.

Note:

Examples that will just redirect you to a customer service representative are not of interest.
I am looking for good and bad examples. If you are aware of phone numbers for some spoken dialogue systems that you like or hate let me know
If you know a website that lists some numbers to call even better.

So far I had no luck with google and  i hope i have choose the right community on stack overflow for this. If not please accept my apologies in advance.


texts: Proof of Brzozowski's algorithm for DFA minimization?

texts:
Brzozowki's algorithm is cited widely.  Several questions here give examples or discuss its complexity. But I haven't been able to find a proof of correctness for the algorithm. How do we prove it correct?
Any proof accessible to CS undergraduates would be very welcome.


texts: Create a PDA that accepts the following language

texts:
I need to create a PDA that accepts by empty stack and accepts the language formed by strings over the alphabet $\{a, b\}$ of the form: $uw$, where $w$ is the string $u$ reversed and doubled. So, for example, if $u=ab$ then $w=bbaa$ (the $ab$ is reversed then its characters are doubled).
Examples of strings in the language: $\epsilon$, $aaa$, $baaabb$, $abbbbbbaa$, etc.
I'm really struggling with setting up a PDA that satisfies the criteria. Any help is appreciated.


texts: Is Category Theory useful for learning functional programming?

texts:
I'm learning Haskell and I'm fascinated by the language. However I have no serious math or CS background. But I am an experienced software programmer.

I want to learn category theory so I can become better at Haskell.

Which topics in category theory should I learn to provide a good basis for understanding Haskell?


texts: Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis

texts:
Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best first algorithm.

Edit: I've discovered a related question which can be referenced here:  https://stackoverflow.com/questions/10374357/why-use-dijkstras-algorithm-instead-of-best-cheapest-first-search

The statements are as follows:

•   “…lowest-cost-first search is typically
exponential in both space and time.  It
generates all paths from the start that have
a cost less than the cost of a solution.”
(Poole, 2nd ed., Section 3.5.4, last
sentence)

•   Dijkstra’s algorithm runs in time O(V^2)
(Cormen, et. al., Ch. 24)

•   Lowest-cost-first search is Dijkstra’s
algorithm where you terminate the search
after you have found the shortest distance to
the goal node.

These statements seem contradictory.
How do you resolve the contradictions?

I'm a bit confused about how to approach this question.

From what I've gathered, the answer may have to do with the fact that lowest-cost-first search is said to be an uninformed search strategy whereas, Dijkstra's is said to be an informed search strategy but I don't fully understand the implication.

The first statement confuses me the most, the part that says that:

"It (lowest cost first) generates all paths
from the start that have a cost less than the
cost of a solution"

My guess is that this statement refers to bounded arc costs which the same text further elaborates on by stating:

If the costs of the arcs are all greater than
a positive constant (bounded arc costs) and
the branching factor is finite, the lowest-
cost-first search is guaranteed to find an
optimal solution – a solution with lowest
path cost

and

The bounded arc cost is used to guarantee the
lowest-cost search will find a solution, when
one exists, in graphs with finite branching
factor. Without such a bound there can be
infinite paths with a finite cost.

However this is difficult for me to understand as I am still very much a novice student.  If anyone could help explain this I would be eternally grateful, thank you.


texts: A problem to maximize the number of edges in a cycle while minimizing the total weight

texts:
I encountered the problem below and the only solution I came up with is branch and bound like that is used in TSP and I don’t think the bound I used is good enough. Are there any better idea on this?

Consider a graph $G$ that consists of an undirected bipartite graph and another vertex $O$ that is connected to all the other vertices. Assume the weight of the edges are positive and the weights obey the triangle inequality. Find a cycle in $G$ that involves $O$ s.t. the total weight is $\leq$ some given value $t$ and maximize the total number of vertices it passes through.


texts: Getting rid of negative-cost edges in min-cost max-flow algorithmically

texts:
I have a min-cost max-flow problem. The designed network (without cycles) gives correct results using cycle cancelling, but it is way too slow. I would like to get rid of negative edges so that I can use successive shortest path.

Is there a universal way how to transform a flow network without cycles?


texts: Is equivalence of a CFG and an RG undecidable?

texts: I know that the equivalence of two context-free grammars is undecidable, but what about the equivalence of a regular grammar and a context-free grammar?


texts: Using symmetry to prune DFS tree for graph coloring problem

texts:
I am working on the graph coloring problem. I came up with the following.

Let $S^L$ be the set of all colorings with $N$ colors for a graph with $L$ nodes. This is shorthand notation for $\{1, 2, 3, ..., N\}^L$ - a string of $L$ characters each belonging to a set $S = \{1, 2, ..., N\}$.

I noticed that we can prune the search tree if we apply the symmetry. For instance coloring $1211$ is the same as coloring $2122$. Idea is that if we take the colorings where first appearances of elements are in order, all others can be mapped to them. I provide the proof below.

Let us make this more formal. So for instance in coloring $12113$, first color to appear from left to right is $1$, then $2$, then $3$, which is in order. To help us define this let $\psi$ be the function that finds the first coccurance of color $c$ in the coloring $s$, that is $\psi(c, s)$. So for example $\psi(2, 1321) = 3$

Define $\Omega = \{ s \in S^L : i < j \Rightarrow \psi(i, s) < \psi(j, s) \}$. This is the set of colorings all other coloring can be mapped to.

Mapping is easy to find. Let $s \in S^L \land s \not \in \Omega$. We just sort the $\psi(k, s)$ and map each $k$ to its position in the sorted array. This way first element that occurs will be replaced by $1$, second by $2$ etc.

Now what my algorithm does is just traverse the $\Omega$ and print out the  feasible solution with least colors used it found. This seems not to work for all cases since it finds suboptimal solutions. I checked my implementation it seems to exactly capture the algorithm described.

So my question is: Is the reasoning I provided above correct and does the $\Omega$ represent the entire $S^L$ and it is sufficient only to traverse $\Omega$ to find optimal coloring?

I think my reasoning is correct. I have been twisting my head with this for quite some time and it is frustrating since I can not find the mistake. I programmed the coloring generator where I check that each coloring can be mapped to one from the base for certain $L$.


texts: What does it mean by saying "Asymptotically more efficient"?

texts:
What does it mean when we say that an algorithm $X$ is asymptotically more efficient than $Y$ ?

$X$ will be a better choice for all inputs.
$X$ will be a better choice for all inputs except small inputs.
$X$ will be a better choice for all inputs except large inputs.
$Y$ will be a better choice for small inputs.

The link for this question is here .

http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/

I thought that an algorithm more asymptotically efficient should work for all inputs, but I am not getting the reason behind "It works for all inputs except small ones".


texts: Why interrupts can help to increase the efficiency of a user program that contains many I/O operations?

texts:
I am reading Computer Architecture & Organization by William Stallings to understand I/O operations. I get the general mechanisms of how interrupts are handled in computer systems, but the results of interrupts improving the efficiency of user programs with many I/O programs is kinda counter intuitive. As from what I know, it seems that the computer tends to be more efficient if it is dedicated to one task. So can anyone help explain more clearly why interrupts can increase the efficiency of a user program that contains many I/O operations?
Any kind of advice is welcomed


texts: Why do we focus on asymptotics when analyzing algorithms?

texts: Maybe a newbie question, but why when we analyze algorithms do we focus on asymptotics?  It seems to me the performance of algorithms on finite input sizes (after all, problems are rarely infinitely large) should be as important or more so than when they tend to infinity.  Do things simply become too complicated and nuanced if we don't allow $n \to \infty$?


texts: Why don't we use simple binary values to compress data?

texts: In Huffman's algorithm, we form a tree and than replace each character with the tree value of 1 and 0. Why don't we simply use the binary digits like $a=0$, $b=1$, $c=10$, $d=01$, $e=11$ and so on than replace them with the characters and when decompressing aplly the reverse and replace the binary digits with the alphabets?


texts: Proving intuitionistic tautologies in Agda

texts:
I am to use Agda to prove some intuitionistic tautologies. One of them is the so called Weak Peirce's Law
$$
((((A \rightarrow B) \rightarrow A) \rightarrow A) \rightarrow B) \rightarrow B
$$
I understand that there is an "equivalence" between intuitionistic tautologies and programs and their types, that is if I manage to write a function of this type, it works like a proof of this tautology.
The type of the function is wp : {A B : Set} ((((A -> B) -> A) -> A) -> B) -> B.
My question is - how do I even approach this thing? I managed to prove some other laws of intuitionistic logic, but with this one I'm kind of stuck. I imagine that somehow I'd like to get the first A -> B function and apply A to it, but how can I do that if all I get is the whole function f of type ((((A -> B) -> A) -> A) -> B)? Should I use $\lambda$'s for this?
Additional question: What does this Law even mean? There are so many implications that I can't even parse it...


texts: Introduction to complexity and computability

texts:
I'm looking for a good book that explains these subjects in a readable way.
Any suggestions ?

I currently pursuing my BSC in computer science, and I just failed to pass the course introduction to thr theory of computation and complexity.
I would like to have more reference and sources of knowledge so I can understand the subject better. Examples and solutions for various problems like proving undecidability, many to one reductions, etc can help me alot.


texts: How to detect facial landmarks - using haar and other way?

texts:
I have done some projects using haar cascade(Ex.- Face-detection,Eye inside face detection,shoe detection etc), I also have some knowledge about it. I have trained my own models learning from youtube, this site etc.

Now I want to take it to the next level.

I want to detect facial landmarks, I have used different modules to do this, I have used dLib. But I want to learn more about it and as far as I know using multiple haar will be very much inefficient.

So how can I do this?

What I want to detect from the image :


texts:
I'm having difficulty with the following question:

  Given a bit pattern with mantissa $10110000$ and exponent $0111$, what
  does the bit pattern represent in denary (i.e decimal / base 10)?

I got the right answer(!) but the wrong (or alternative) work:

Convert the exponent to denary: $0111$ is $7$
Apply this exponent to the mantissa: $10110000\rightarrow1011000$ after shifting $7$ places
Convert the mantissa to denary: $1011000$ is $88$
Set the sign: $-88$ (which is correct!)

Using a different method, the mantissa $1.0110000$ is somehow deteremined to be $-11/16$ and then $-11/16 \times 2^7 = - 88$ (I understand this shift with the exponent). However, what I don't understand is:

  How do you convert 1.0101 (mantissa) to -11/16? Is this a standard way to do it?


texts: Where does the Dynamic Link point to on the activation record

texts:
I'm a bit confused as to wear exactly the dynamic link points to on the activation record. I understand that it points to the 'top' of the instance of the callers activation record but I am unsure of where the 'top' is.

Based on an example from my textbook:

It would appear to me that the 'top' of the calling function is spatially the bottom of the calling functions activation record.

But the problem is that a couple of pages later when it discusses the static link the example has changed where the dynamic link points to:

Now it seems to be pointing at, what I would describe as, the structural top of the callers activation record.

Does where we point to change when we are including static links? I noticed that the static links point to the structural bottom like the dynamic links used to; does that having something to do with it?


texts: What is the relationship between the Markov property and optimal substructure?

texts:
Dynamic programming can only be applied to problems with optimal substructure.

The Markov property (e.g. in Markov Decision Processes, MDPs) means that the distribution of one state $x_{k+1}$ only depends on the state directly before ($x_k$, and the action $a_k$), not on more steps before. (commonly expressed as $P(X_{k+1} = x_{k+1} | X_k = x_k, X_{k-1} = x_{k-1}, \dots, X_0 = x_0) = P(X_{k+1} = x_{k+1}| X_k = x_k )$)

What is the relationship between optimal substructure and the Markov property? Does every MDP have optimal substructure? What are examples of stochastic problems which have optimal substructure but do not have the Markov property? Or is there no such relationship?


texts:
I found two definitions Reed-Muller codes being used in literature. More specifically for any $n \in \mathbb{Z}^+$ and $1 \leq d \leq n$ we define the set $RM(d,n)$ in two possible ways,

1.
$RM(d,n) = \{ f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2 \vert $f$ \text{ is a polynomial of degree at most } $d$\} $

2.
$RM(d,n) = \{ f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2 \text{ s.t} f(x) = (-1)^{P(x)} \vert $P$ \text{ is a polynomial of degree at most } $d$ \text{and  with integer coefficients of magnitude at most }d \}$

Are these the same?
In the first definition how is "degree" defined? Is $f$ assumed to be a sum over monomials where each literal occurs with power $1$ and then the final answer of the polynomial is evaluated $mod$ $2$ or is $f$ to be thought of as a generic degree $d$ polynomial such that when its input is restricted to $\mathbb{F}_2^n$ its output gets restricted to $\mathbb{F}_2$?


texts:
I am practicing questions in which I need to determine the big oh time complexity for a given piece of code. I have attempted the first 3 questions. Could anyone please confirm if the answers are  correct?

Also, I am not sure how to calculat the big oh time complexity of the code in the 4th question. Could someone please explain how to calculate it?

Thank you

1:

sum, i = 0, 0
while i**2 < n:
    sum = sum + i
    i += 2

O(n^(1/2))

2.

i, j, sum =1,1,0
while i < n**3:
    while j < n:
        sum=sum+ i
        j += 1
    i=i+n

O(n^3)

3.

i, sum = 0, 0
while i *2 < n:
    sum = sum + i
    i=i+1

O(log(n))

4.

i, sum =0,0

while i < 3 * n:
    if i %2 == 0:
        j = 1
        while j < n:
            sum = sum + j
            j=j*2
    else :
        j = 1
        while j < n:
            sum = sum * j
            j += (n // 5)
    i=i+5


texts: Single queue instruction issuing in computer architecture

texts:
I am working on this paper titled “the microarchitecture of superscalar processors by Smith and Sohi” and it says that there are 3 methods of organizing instruction queue. I know that the method “Multiple queues” is the same as the method “Scoreboard” and also the method “Multiple reservation stations” is the same as the method “Tomasulo”, but I can’t find any thing about the method “Single queue”. All it says is that there is a bit for reserving and clearing the reservation. But i don’t know how it works. Is there any design or anything that shows the architecture of this method?

Thanks in advance.


texts: Data structure for optimal deduplication of common subsets

texts:
Consider a database with the following properties:

It stores symbols (represented as 64-bit integers) and sets of symbols
Sets may contain thousands of symbols, and there may be thousands of sets which are the same except for one or two added symbols
Every set should have exactly one canonical representation (two identical sets must have identical representations in the database)

If several sets contain large common subsets, they should be highly compressible: it should be possible to represent the common subset as a set itself, and store a reference to it, similarly to most persistent data structures.

However, the requirement for a single canonical representation of a set complicates things. Inserting certain new elements may rearrange the entire data structure, removing shared subsets. What kind of data structure would allow for shared common subsets in the majority of cases? My first guess is a balanced binary tree, but I'm not sure if balancing is even necessary; all that's needed is for the same set of symbols to always result in the same tree.


texts:
Say, I would like to check a hypothesis concerning primes. Something like "there exists a prime between $n$ and $2n$ for every choice of $n$". I would like to run a code in MATLAB for choices of $n$ upto $2^{32}$ and then use that data and publish the conjecture in a journal.

The question is, what should I use to check primality. Obviously, AKS is an option but it is really really slow. I can use the in-built MATLAB function $isprime()$ which I think uses $10$ instances of Miller-Rabin. This will be way faster but the journal might reject this saying that Miller Rabin is probabilistic and that I should instead use a deterministicalgorithm since one exists.

What should I do? Use AKS? Go with MATLAB's inbuilt Miller-Rabin? Or look at other deterministic algorithms?

I don't think this is the best place to ask this. However I could not find where else to ask. Any suggestions?


texts: Finding examples of languages that are "anti-palindromic"

texts:
Let $\Sigma = \{ 0, 1 \}$. A language $L \subseteq \Sigma^* $ is said to have the "anti-palindrome" property if for every string $w$ that is a palindrome, $w\notin L$. In addition, for every string $u$ that is not a palindrome either $u\in L$ or $\mathrm{Reverse}(u) \in L$, but not both(!) (exclusive or).

I understand the anti-palindrome property, but I could not find any languages that have this property. The closest one I could find is $\Sigma^* \setminus L$, but it does not have the exclusive or part... that is, for example, both $01$ and $10$ are in $L$.

Could anyone give me an example of a language that has this propery? Or possibly even more than a single example, because I fail to see what kind of limitations this puts on a language. (Must it be non-regular? Context Free? Or not even in $R$? and etc.)


texts: Is there a name for the class of distance functions that are compatible with k-d trees?

texts:
The typical nearest neighbor search implementation for k-d trees prunes branches when the distance between the target and the pivot along the current axis exceeds the smallest distance found so far.  This is correct (doesn't wrongly prune any points) for any Minkowski distance.  Is there a broader class of well-known distance functions that are compatible?  Formally, I think the necessary and sufficient condition is just
$$
d(x,y) \ge |x_i - y_i|
$$
for $x, y \in \mathbb{R}^n$, $1 \le i \le n$.


texts: Algorithm Time complexity analysis for algorithm having two different time complexities

texts:
I'm implementing an algorithm that analyze several properties on large set of integers, the time complexity is bound to $N$ (set length) and $M$ (bits to represent the numbers). I'm having some trouble to figure out how to express its time complexity because I don't know how to handle next situation:

The asymptotic analysis establish that when $N$ is constant and $M$ grows the operations count grows at constant rate ($R1$) until it reaches a threshold that depended on the value of $N$, then the operations count does not grow anymore.

On the other hand when $M$ is constant and $N$ grows the operations count grows also at constant rate ($R2$) until it reaches a threshold that depends on the value of $M$, then, it continues growing but at a slower rate.

My understanding that the algorithm has two different time complexities depending on the values of $N$ and $M$.

Is there any way to integrate this behavior in a single Big-Oh expression?

And if not possible, how will be the right way to describe the time complexity for an algorithm with these properties?


texts:
What is the intuition behind EXPTIME being inside EXPSPACE?

When space complexity is usually smaller than time complexity or in the worse case, they are equal


texts: Linear Programming Problems with decimal solutions for problems requiring whole number solution

texts:
I have an LPP which asks for the maximum number of pairs of shoes that can be manufactured to maximize the profit. The LPP is:
$$
\begin{align}
\max\ Z&=1350x + 975y\\
\text{Subject to}:&\\
3x+1.5y&\leq275\\
2.5x+2y&\leq300\\
x, y&\geq0
\end{align}$$
The solution I obtained is $x=44.45$, $y=94.44$
Now, since $x$ and $y$ can only be positive integers, what will the final solution be? I'm confused about this step. Any help is welcome :-)


texts: Brute force Delaunay triangulation algorithm complexity

texts:
In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm uses the notion of illegal edges -- edges that may not appear in a valid Delaunay triangulation and have to be replaced by some other edges. On each step, the algorithm just finds these illegal edges and performs required displacements (called edge flips) till there are no illegal edges.

Algorithm LegalTriangulation($T$)
Input. Some triangulation $T$ of a point set $P$.
Output. A legal triangulation of $P$.
while $T$ contains an illegal edge $p_ip_j$
do
$\quad$ Let $p_i p_j p_k$ and $p_i p_j p_l$ be the two triangles adjacent to $p_ip_j$.
$\quad$ Remove $p_ip_j$ from $T$, and add $p_kp_l$ instead.
return $T$.

I've heard that this algorithm runs in $O(n^2)$ time in worst case; however, it is not clear to me whether this statement is correct or not. If yes, how can one prove this upper bound?


texts: Difference between Adjacency matrix and Laplacian matrix (Dynamical Process Perspective)

texts:
We can represent a simple connected graph $G$ using mathematically as adjacency matrix, $A$. There are other matrices related to the graph which is very useful is the Laplacian matrix $L=D-A$ where D is the diagonal matrix contains the degree of the nodes. It is mentioned that spectrum of the Laplacian matrix is useful for the dynamical perspective on networks. It has also been reported that the maximum eigenvalue i.e. $\lambda_{max}$ of adjacency matrix gives the threshold of the disease spreading process [1] (is a dynamic process).

I am not clear, what kind of information we can achieve from the spectrum of the adjacency matrix but not from Laplacian matrix and vice versa (where both are two types of dynamical process). If anyone suggest some reference or article which can clear me is also welcome.

[1] Y. Wang, D. Chakrabarti, C. Wang, and C. Faloutsos, Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint, in 22nd International Symposium on Reliable Distribute Systems (SRDS03) (IEEE Computer Society, Los Alamitos, 2003), p. 25.

Thanks a lot.


texts: What is the difference between the study of Evolutionary algorithm vs. Optimization?

texts:
I have a course named "Evolutionary Algorithm". But, our teacher is always mentioning the word "Optimization" in his lectures.

I am confused. Is he actually teaching Optimization? If yes, why is the name of the course not "Optimization"?

What is the difference between the study of Evolutionary algorithm and Optimization?


texts:
I am working in grasshopper and need a formula that can divide any surface into equal points.
I need an algorithm that can give me equidistributed points on the surface Chebyshev


texts: Modeling the problem of finding all stable sets of an argumentation framework as SAT

texts:
As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form.

Problem: Find all stable sets of an argumentation framework according to Dung's proposed framework.

Brief theory: Having an argumentation framework AF, with A the set of all arguments and R the set of the relations, a stable set is a set which attacks all arguments not in their set and there is no attack relation between arguments in the stable set.
Example:

Let's say we have an argumentation framework AF ,A={1,2,3,4}(arguments of AF) and attack relations R{1,3} and R{2,4}.
It's obvious that the set {1,2} is a stable extension of the framework because:

a)it attacks all arguments not in their set (3 and 4)

b)it's conflict free(no attacks between arguments in the set) because argument 1 does not attack argument 2 and the opposite

My exhaustive abstract algorithm:

argnum=number of arguments;

Ai[argnum-1]=relation "attacks" ,where 1<=i<=argnum

P[2^argnum-1]=all possible relations that can be generated from all the arguments

S[2^argnum-1]=empty; where S are all the stable sets

j=0; //counter for while
k=1; //counter for counting stable sets
while j<2^argnum-1
    if P[j] attacks all arguments not in P[j](check using Ai[])
        if all arguments in P[j] are conlfict-free
            S[k++]=P[j];
        end if
    end if
    j++;
end while

I want to solve the above problem either by transforming the above algorithm to CNF or by using a different algorithm and finally use a SAT Solver(or anything similar if exists) give CNF as input and get stable sets as output.

I wonder if someone can give me any feedback of how i can transform any algorithm like the above to CNF in order to be used into a SAT Solver.

I decided to use precosat.


texts: Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.

texts:
...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM.

I had this problem on my exam. From my understanding, the halting problem involves a program with some input, and that program will either output yes or no as output when comparing the input to the desired value. Then there's another program that must determine if the original program will ever halt based on the input given to it.

Thing is, I'm not sure if I understand the entire concept here. It's undecidable because we are unable to write a program that can determine if a program will always halt or stay in an infinite loop? Since it will always output as a "yes, it halted" even though the original program either halted or remained in an infinite loop.

So, I'm pretty new to all this, so bare with me. If the original question was asking me to "reduce" from the halting TM, do I apply the same principles? Or am I working out the problem differently? What is a reduction exactly, and what was I supposed to do here?