texts: Lambda calculus outside functional programming?

texts:
I'm a university student, and we're currently studying Lambda Calculus. However, I still have a hard time understanding exactly why this is useful for me. I realize if you do loads of functional programming it might be useful, however I reckon that it's not really needed for learning functional programming, what do you think?

Secondly, is there any use for Lambda Calculus within the realm of Computer Science but outside of functional programming languages?


texts: max, min gradient and other terms in Neural Network

texts:
This  link  contains a demo that trains a Convolutional Neural Network on the MNIST digits dataset in browser.

I am not getting below terms-
1. max, min gradient in each layer.
2.max, min activation in layers

3.Forward time per example

4.Backprop  time per example

Classification loss
L2 (a pooling mechanism??! but what this means?) Weight decay loss

What are the meanings of above terms according to given context (webpage demo)?


texts: Can someone help solve recurrence relation?

texts:
It says to solve the recurrence exactly for n a power of 2.

T(n) = {1}, if n = 1

T(n) = {5T(n/2) + (n lg n)^2, otherwise

I'm supposed to use Θ notation to express my answer.

Normally I would try to look for the characteristic equation but for this one I'm lost.

Is this the first step?

T(n) - 5T(n/2) = (n lg n )^2

This is not a duplicate as it has not been posted there.


texts:
Suppose you have $n$ nonequal sets $S_1, \ldots, S_n$ and some constant $0 \le k < n$. The goal of set clustering is to find a partition of the set $\mathbf{S} = \{S_1, \ldots, S_n\}$ such that the sum of the total distance for each subset of $\mathbf{S}$ is minimized and such that $\mathrm{cardinality}(\mathbf{S}) = k$ (in reality, this latter constraint is not quite so tight, but the size of $\mathbf{S}$ must be less than $k$, and hopefully near it). The total distance $d$ of a set $X \in \mathbf{S}$ is $d(X) = \sum_{A, B \in X} \mathrm{cardinality}(A \ominus B)$ where $\ominus$ is symmetric difference. Assume for the purposes of the problem that the sets consume $O(1)$ space (so symmetric difference can be computed in constant time).
Is there a good greedy linear(ithmic) heuristic for this problem? Is there any literature on this problem, or similar ones?

All I've come up with so far is an $O(n^2 \log n)$ heuristic that looks like:

Set $I = \{1, \ldots, n\}$
Choose some $i \in I$
Emit a cluster $C \subset I$ containing all $m \in I$ such that $\mathrm{cardinality}(S_i \ominus S_m) \le d_\mathrm{max}$.
Set $I = I - C$
Go to step 2.

where this process occurs in each step of a binary search that finds the best value of $d_\mathrm{max}$ for a given $k$.
I was thinking that if there were some way to sort the list of sets such that nearby sets in the list have small symmetric difference, then a linearithmic solution might be easy to write.


texts: Prove that an $n$-length string has $2^n$ i18n-style abbreviations

texts:
An i18n-style abbreviation is one in which multiple letters are shortened to that number of letters. E.g., "internationalization" -> "i18n" ("nternationalizatio" is substituted with its length 18). Other abbreviations include "in17n", "i17on", "in16on", etc. I see a pattern in which words with at least 3 characters have $2^{n-2}-1$ different abbreviations. E.g.,

hat - h1t (1 possible abbreviation)
code - co1e, c1de, c2e (3 abbreviations)
words - wor1s, wo1ds, wo2s, w1rds, w1r1s, w2ds, w3s (7 abbreviations)
active - acti1e, act1ve, act2e, ac1ive, ac1i1e, ac2ve, ac3e, a1tive, a1ti1e, a1t1ve, a1t2e, a2ive, a2i1e, a3ve, a4e (15 abbreviations)

The pattern is apparent, but how do I prove that this is the case?


texts: When I want to vocalize a hexadecimal number like 0x41, so I say "forty one in hexadecimal", "four, one in hex" or what? Or do you always have to calculate and say "65 in hexadecimal notation"? I feel like that would complicate communication if I just want to tell someone what numbers I see on the paper in fornt of me, so he can write them down for example.


texts:
We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We need to find the size of bin such that wastage of unused bin is minimized.

Is this problem polynomial time solvable?


texts: Why LLVM is not suitable to design a static analyzer?

texts:
I'm reading a paper, and there is this paragraph about LLVM:

  ''it heavily relies on the static single assignment form
  (SSA) which cannot be readily used to design an abstract interpreter.
  The $\phi$-nodes need to be eliminated and other inadequate constructs need
  to be simplified using various LLVM transformation passes"

I understand the $\phi$-nodes need to be unrolled, but what are some examples of inadequate constructs in LLVM that make it unsuitable to design a static analyzer based on abstract interpretation?


texts: Hex Bit Pattern to IEEE 754 standard Floating Point Number

texts:
The question asks for the decimal number that 0x0C000000 represents if it is a floating number. I'm not too sure on how to approach this, but here's my thought process:

0x0C000000 = 0000 1100 0000 0000 0000 0000 0000 0000

The first digit is 0, so it's positive. The exponent is
 0x0C = 12 - 127 = -116.
 The mantissa is 0x0C0000 = 12 * 16 ^ -2 = 0.046875, so the final answer is 1.046874 * 2 ^ -116. While my book has similar examples that I tried to follow along with, none were exactly of this type, so I highly suspect I'm doing something wrong. Any tips, hints, or strategies would be greatly appreciated.


texts: How to draw a Non Deterministic Buchi Automaton (NBA) from the given property?

texts:
I'm new to LTL and Buchi automaton, and I have a hard time in constructing NBA from the given formula or the property. Could somebody please help me?

The following property is given, P= "Whenever process 1 is in its waiting location (w1), it will eventually enter its critical section (c1).” where AP = {w1, c1}. I have to depict an NBA for P and complement of P.

I believe that the above property, P, can be written as

  w1 -> F(c1)

and the complement of P can be written as

  ~w1 -> G ~c1

where F represents eventually, G represents always and ~ represents not (LTL formula)

Is it correct?

Can I represent '->' (i.e. implication) with Until operator in LTL?

I searched on the internet on "LTL to Buchi Automata". Sadly, I didn't understand. Can somebody please explain it to me Step by Step in layman's term?

Is there a simpler way to depict an NBA for P and complement of P?

I will be grateful. Thank you very much :)

Update: following the reply, I have few more doubts:

If the property P can be written as G(w1 -> F c1), then as per this article on  LTL model checking translation From LTL to Buchi automata (Page 26), the Buchi automata can be drawn as:

G(w1 -> F c1)

I don't know why it is different from the one given in the book (example 4.30)

I know, it is really unnecessary to use LTL here, and probably I am making things complicated, but I want to know how to depict an NBA from the (any) given property. Like you mentioned Ayrat, LTL does not have the operator ->, since it is a Boolean operator, I cannot use the method "LTL to Buchi automata" given in "Constructing Automata From Temporal Logics Formulas: Tutorial" (or can I?)

What is the correct way to construct such NBAs?

Thank you


texts: How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

texts:
I want to prove that $L=\{\langle M \rangle |L(M)\text{ is undecidable}\}$ is undecidable
I am not sure about this. This is my try :
Suppose L is decidable. Let $E$ be the decider from $L$. Let $A$ be a TM which is recognizing $A_{TM}$.
Let $S$ be a TM which works on input $\langle M,w \rangle$ in the following way(the goal is that $S$ will be a decider for $A_{TM}$):

Construct a TM $N$ which works on Input $x$ as follows: Run $M$ on $w$. If $M$ $accepts$ run $A$ on $x$ and accept $x$ if $A$ accepts.(In this case is $L(N)=A_{TM}$). If $M$ $rejects$ $w$, $accept$ $x$.(In this case is $L(N)=\Sigma^*$)
Run $E$ on $N$ and accept if N accepts. Otherwise reject

I am not sure if my reduction is the right way or not. Maybe someone can help to finish the reduction :)


texts: [Choosing tunable parameter M in Golomb/Rice Encoding]

texts: I am a Computer Science student and I study Data Compression now. I read many methods but Golomb-Rice Encoding was not clear for me.  I understand the method how it works but in the algorithm there is 'Tunable parameter $M$' that operates with the number that you want to encode. My question is how can I decide what value of $M$ to use? Is there a optimal solution for deciding $M$?


texts: Combinatorial optimization problem - What would you call this?

texts:
I'm trying to solve an optimization problem which can be described as follows.

There are four sets objects. For simplicity, let's call them :

Apples
Oranges
Pears
Lemons

The sets can contain unequal numbers of their respective objects
These objects must be organized into groups containing exactly one of each object
Each possible group can be evaluated by some merit function (ie: function of the difference between the masses of the constituent objects of the group, say)
The maximum number of groups with a merit function below some threshold must be formed with the objects in the input sets.
In the above set of groups, no object can be duplicated - it must belong uniquely to one group.

My question is not necessarily how to solve this problem - this is no doubt an extremely broad question.  What I would like to know is whether or not this problem has, or is of a class of problem, with some formal name.

Primarily, I'm looking for search terms to help research similar problems (and the types of solutions that are known for it).


texts: Transform Double Metaphone code into regex

texts:
I am using hyperscan to search through large texts for a lot of regexes. One addition should be selective phonetic search for individual words. The algorithm of choice is Double Metaphone (but please feel free to recommend any other algorithm that might be more suitable to the problem and offers at least the same quality).

To search for phonetic matches I would have to translate every single word in my large text to its phonetic code and then compare them with the phonetic code of the word to search for. This is impractical for large texts. Also, to work together with hyperscan, I have to provide the search term as regex.

So my question is if it is possible to translate the phonetic code into a regex and pass it on, so that my text can remain unmodified while being searched?


texts: Cover interval with minimum sum intervals - DP recursion depth problem

texts:
READ ME FIRST:
I have just found the official solutions online (have been looking for them for a while, but after posting this I quickly found it), and I'm currently trying to understand it. As I can tell, it uses a much simpler DP, which only uses an O(N) array.
EDIT 2
I kinda figured out what and how it does, but I still do not understand why it gives the correct answer. It uses a dp[index] -> weight sum if we select that interval and previous ones to cover [A, start_of_current].
It sorts the intervals by end time, than process each one in order. If it's start is A, we 'select' it and set it's dp[i] to it's weight. If not, it tries to find the previous selected interval whose end is closest to the current intervals start, but there is no gap in between. If found one, we 'select' the current and set it's dp[i]=it's weight + dp[j] where j is the found previous interval. If we can not find any previous, dp[i] = inf. We keep a list of the 'selected' intervals, which is, as we only push items to it, is sorted by the interval's end. When we selected one, we delete all the others from the end of this list whose cost (dp[i]) is bigger than the current one's.
What I do not get from this, is why this searching-the-closest-end yields the smallest overall weight sum, and also, why we delete all those intervals from the selection list?

Story:
This year I attended a programming competition, where we had a few interesting problems. I had trouble with some of them, and since the next round approaches, I want to clear them up.

The problem in a nutshell
We are given N weighted intervals, and a [A,B] interval. We have to cover the [A,B] interval with the given ones, in such a way, that we minimize the overall weight sum (and then the number of required intervals). We need to print the sum, the number of intervals, and then the intervals themselves. If we can not cover [A, B], we need to report that as a special value (-1).

First thoughts
If we sort the intervals by begin time, then we can do simple 0-1 Knapsack-like DP and solve the problem. Also, if the priorities were swapped (minimize count THAN sum), a simple greedy would do it.

The limits
Basically, all interval starts and ends are in the range 1-1 000 000, and N<=100 000. All intervals lie within [A,B].

My approach
I wrote a recursive algorithm like the 0-1 Knapsack one in python, that also stored the last selected interval - thus allowing the recovering of the selection list from the DP array later. It was a (current_interval, last_covered_day) -> (cost, last_selected_interval, last_covered_day')-like function. I used a dict as a DP array, as a regular array that big would have violated memory constraints and filling it fully would also increase runtime (at least that's what I thought - but a 1000000 * 100000 array would certainly would!). I wrote the function as a recursive one so it would not fill in the entire DP array and be faster & more memory-efficient.

The problem with this
Simply, I got RecursionError: maximum recursion depth exceededs on larger datasets - 100k deep recursion was simply too much. I read since on GeeksForGeeks that it should be possible to increase it, but I am still not confident that it would be safe. My recursive function is also not tail-call optimizatiable, so that would also not work.

So my questions
Is there a way of solving this problem without DP?
If no, is filling in a full table an option with those high limits?
Maybe we can come up with a different DP approach that does not use such big tables?
Is it safe to just increase recursion depth limits with this kinds of problems?


texts: If you increase the address space for an OS, does the Phys Mem used by the program increase?

texts:
I am learning about the OS.

I know: that Address Space Size = # of pages x page size

So if I increase Address Space Size, then the number of pages increases:(not the page size). However, isn't the Virtual Page Number a one-for-one mapping to Physical Page Numbers(frames), so if the number of pages increases with the address space doesn't the frames and hence, the size of RAM used increase with address space increases?

Or, does bigger address space cause more physical frames so each frames physical memory size reduces as total memory is split among more frames.


texts: Is it true that PAC is a subset of agnostic PAC?

texts: I would like to see the proof or a refernce to it. I feel it is obvious but my tutor insists the other way (agnostic PAC is a subset of PAC, and there are problems in PAC that are not angostic PAC).


texts: Calculating number of operations in a divide and conquer approach when the input is not an exact power of 2

texts:
Here is a divide and conquer approach for finding minimum and maximum elements in an array.

MaxMin(i, j, max, min)
{
   //max and min are the references so that we can retain their value when
   //we return from the function. i and j are the indices of start and
   //end respectively.
     if (i=j) then max := min := a[i]; //Small(P)
      else if (i=j-1) then // Another case of Small(P)
      {
            if (a[i] < a[j]) then max := a[j]; min := a[i];
            else max := a[i]; min := a[j];
      }
     else
     {
           // if P is not small, divide P into sub-problems.
           // Find where to split the set.
           mid := ( i + j )/2;
           // Solve the sub-problems.
           MaxMin( i, mid, max, min );
           MaxMin( mid+1, j, max1, min1 );
           // Combine the solutions.
           if (max < max1) then max := max1;
           if (min > min1) then min := min1;
    }

}

If we analyze the complexity of this algorithm, we see that if n is the power of 2, then it does (3n/2)-2 comparisons.
My question is how many comparisons does it do if n is not an exact power of 2. I think it does more than 3n comparisons because at the base level, we are left with 3 elements(which take 3 comparisons) instead of 2 elements(which take just 1 comparison). But I am not sure about my thinking. Any help would be appreciated.


texts: Route planning for a car driver picking up people using public transport

texts:
We just had an interesting though for a routing algorithm for people carpooling. Imagine the following situation:

Person 1 is driving with his car from the south of city A to city B far in the north. He is picking up person 2 who is starting in the west of city A and person 3 who is starting in the east of city A. Person 2 and 3 only use public transport. Most likely, the optimal solution will be that they meet somewhere in the center or north part of city A and then drive on from there.

Any hints on an algorithm to find that solution?


texts: 3xN tiling problem with blocks of size 3x1 or 2x2

texts:
I know there are a number of different tiling problems and some of them have been discussed here:
Number of ways of tiling a 3*N board with 2*1 dominoes problem
Domino and Tromino Combined Tiling
DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?.
My domain has different requirements which are as below:
https://www.codingame.com/ide/puzzle/3n-tiling

Height will be 3,
tile sizes are: 2x2, 3x1, 1x3

there are possible choices for 3x6:

┌─────┬─────┐  ┌───┬───┬───┐  ┌─────┬─────┐  ┌─┬─┬─────┬─┐
├─────┼─────┤  │   │   │   │  ├───┬─┴─┬───┤  │ │ ├─────┤ │
├─────┼─────┤  ├───┴─┬─┴───┤  │   │   │   │  │ │ ├─────┤ │
└─────┴─────┘  └─────┴─────┘  └───┴───┴───┘  └─┴─┴─────┴─┘
┌─┬─────┬─┬─┐  ┌─┬─┬─┬─────┐  ┌─────┬─┬─┬─┐  ┌─┬─┬─┬─┬─┬─┐
│ ├─────┤ │ │  │ │ │ ├─────┤  ├─────┤ │ │ │  │ │ │ │ │ │ │
│ ├─────┤ │ │  │ │ │ ├─────┤  ├─────┤ │ │ │  │ │ │ │ │ │ │
└─┴─────┴─┴─┘  └─┴─┴─┴─────┘  └─────┴─┴─┴─┘  └─┴─┴─┴─┴─┴─┘

(illustration copied from Codingame problem section).

I have come up with the following DP relation:

dp[i] = (dp[i-1] + (i >= 3 ? dp[i-3] : 0) + (i >= 6 ? dp[i-6] * 2 : 0))

dp[i-1] means at each state, you can add a 1x3 (illustration below) to previous state to get to the current state.

┌─┐
│ │
│ │
└─┘

dp[i-3] means if your width is at least 3, you can stack up three 3x1 vertically to 3 states ago (width - 3) to get to current state.

┌─────┐
├─────┤
├─────┤
└─────┘

dp[i-6] means when my width is greater than or equal to 6, I can add three 2x2 squares horizontally next to each other, then put two 3x1 rectangles on top of them to 6 states ago(width - 6), in two ways, to get to current state).

┌───┬───┬───┐  ┌─────┬─────┐
│   │   │   │  ├───┬─┴─┬───┤
├───┴─┬─┴───┤  │   │   │   │
└─────┴─────┘  └───┴───┴───┘

But looks like I'm missing something, my solution for 3x12 returns 124, while it should be 154.
Any help is appreciated.

Edit:

After a lot of thoughts and getting some ideas from answers, I came up with this solutions (Image represents a top down DP approach)

Basically, based on the image,

To get to 1xN state, we can take 1 time, 1x3 and so dpHeight1[n] = dpHeight1[n-3]
To get to 2xN state, we can either take 1 time 2x2 so dpHeight2[n] = dpHeight2[n-2] or we can take 2 times 1x3: dpHeight2[n] += dpHeight2[n-3]
to get to 3xN, we can either take 1 time 3x1, so dpHeight3[n] = dpHeight3[n-1] or we can take 3 time 1x3, dpHeight3[n] += dpHeight3[n-3] or take 1 time 2x2 and 1 time 1x3, exception here is we can take 1x3 first or after we take 2x2, but they both have same count, so: dpHeight3[n] += (dpHeight1[n-3] * dpHeight2[n-2] * 2)

And this the code:

dpHeight1[0] = 1//height = 1
dpHeight2[0] = 1//height = 2
dpHeight3[0] = 1//height = 3

for (int width=1; width <= n; width++) {
    //take out one 1x3
    dpHeight3[width] = (dpHeight3[width-1])%mod

    if width >= 2 {
        dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-2])%mod
    }

    if width >= 3 {
        //put 1 time 3x1
        dpHeight1[width] = (dpHeight1[width] + dpHeight1[width-3])%mod

        //put 2 vertically stacked 3x1
        dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-3])%mod

        //take out 3 vertically stacked times 3x1
        dpHeight3[width] = (dpHeight3[width] + dpHeight3[width-3])%mod

        //take out 1 time 2x2 and put it on top of 1 time 3x1
        // or take out 1 time 3x1 and put it on top of 1 time 2x2
        dpHeight3[width] = (dpHeight3[width] + 2 * (dpHeight2[width-2] * dpHeight1[width-3]))%mod
    }
}

But still not getting the result.


texts: Rod Cutting without using dynamic approach

texts:
Question

I want to Implement Rod cutting Algorithm without Dynamic Programming Approach.

Let me Describe the problem statement.

  Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

In cormen, the Algorithm is implemented as -:

CUT-ROD (p,n)
1 if n == 0
2 return 0
3 q = - inifinity
4 for i = 1 to n
5 q =max(q, p[i]+CUT-ROD(p,n-i))
6 return q

I got this algorithm , i may explain it with a example-:

Say we want to determine maximum revenue for $n=4$,

and the profit associated with each inches i.e $i=1,2,3,4$is given as follows-:

$p[1]=1,p[2]=5,p[3]=8,p[4]=9$

Now Moving to the algorithm ,if we want to find maximum revenue for Length 4 inch ,we need to call CUT-ROD$(p,4)$.How will it process , i mean what will be its sequence!?i can explain-:

  CUT-ROD$(p,4)$ will be computed by

  maximum value of

  $p[1]+$CUT-ROD$(p,3)$
  $p[2]+$CUT-ROD$(p,2)$
  $p[3]+$CUT-ROD$(p,1)$
  $p[4]+$CUT-ROD$(p,0)$

for $i=1,2,3,4$ respectively.

Now when $i=1$, it will encounter CUT-ROD$(p,3)$

  CUT-ROD$(p,3)$ will be computed by

  maximum value of

  $p[1]+$CUT-ROD$(p,2)$
  $p[2]+$CUT-ROD$(p,1)$
  $p[3]+$CUT-ROD$(p,0)$

for $i=1,2,3$ respectively.

  CUT-ROD$(p,2)$ will be computed by

  maximum value of

  $p[1]+$CUT-ROD$(p,1)$
  $p[2]+$CUT-ROD$(p,0)$

for $i=1,2$ respectively.

  CUT-ROD$(p,1)$ will be computed by

  maximum value of

  $p[1]+$CUT-ROD$(p,0)$

for $i=1$

CUT-ROD$(p,1)$=1,CUT-ROD$(p,2)$=$max(1+1,5)=5$

CUT-ROD$(p,3)$=$max(1+5,5+1,8+0)=8$

CUT-ROD$(p,4)$=$max(1+8,5+5,8+1,9+0)=10$

MY Doubt

I implemented the $C$ code,but it is giving wrong result.I don't know why!

I guess that the sequence of the function call is wrong .Here is the code.

#include<stdio.h>
int p[100];
int result=-9999;
int count=0;
int max(int x,int y)
 {
   return (x > y)? x : y;
 }
int recrsv_top_down(int sizee)
 {
   int i;
   if (sizee<=0)
   {
     return 0;
   }
   for(i=1;i<=sizee;i++)
   {
     result=max(result,(p[i]+(recrsv_top_down(sizee-i))));
   }
   return result;
 }
int main()
 {
    int size,i,result;
    printf("enter the size of rod\n");
    scanf("%d",&size);
    printf("enter the profit of assocaited length\n");
    for(i=1;i<=size;i++)
    {
     printf("enter profit assocaited with length %d \n ",i);
     scanf("%d",&p[i]);
    }
    printf("\n***************OUTPUT*****************\n");
    result=recrsv_top_down(size);
    printf("Maximum profit is %d\n",result);
    return 0;
}

Sorry for the long post , but i have no option!!!

Please help me out !


texts: Convex Hull algorithm - why it can't be computed using only comparisons

texts:
Say I want to compute a covnex hull of given points on the plane. I would like to write an algorithm, that only compares the points and doesn't do any arithmetic operations. Wikipedia states, that:

  The standard $\Omega(n \log n)$ lower bound for sorting is proven in the decision tree model of computing, in which only numerical comparisons but not arithmetic operations can be performed; however, in this model, convex hulls cannot be computed at all.

Why is it so? I can't find any justification for it anywhere, I know it to be intuitively true, but how come it's a necessity?


texts:
Given the definition of 'record': "a collection of field values for a given entity", is this a set of field values for ALL the fields of the entity, or only one particular field [so that you get a different set for each field]?
Also, is the relationship b/w a field & field value essentially equivalent to a function?
NOTE: Total beginner learning data struc. & algos.


texts: Suffix array and counting distinct substrings of specific length

texts:
I am trying to use the suffix array, and the LCP array to count all distinct substrings of a specified length.

I started with the algorithm for counting ALL distinct substrings. I solved it after this explanation: https://www.geeksforgeeks.org/count-distinct-substrings-string-using-suffix-array/  . The problem right now is that I can't figure out how to only count the substrings of my given length, and not all possibilities.

I also computed the array which tells me how many suffixes are lexicographically smaller than suffix_array[i].

Any ideas what I could use to do it?


texts: Show that the language of words with even sum of positions of a letter is regular

texts:
Let $\Sigma=\{a,b\}$, and let $S(a)$ be sum of the positions of $a$ of string $S$. I want to prove $$L=\{S\in \Sigma^{*} \mid S(a)=0(\bmod 2)\}$$ is regular.

What I was thinking is to do somehow keep track of sum of positions of $a (\bmod 2)$ For that I was thinking to do like take set of states as $\{0,1\}\times \{0,1\} \times \{0,1\}$. And starting state $\{0,0,0\}$. My aim to is to keep track sum of positions of $a$ at first component. So starting from initial state, if it read consecutive $x,b$s then it will go to $(0,0,x(\bmod 2))$ then after reading $y,a$s it goes to $(xy+y(y+1)/2(\bmod 2),y(\bmod 2),x(\bmod 2)$ after reading $z,b$s it goes to $(xy+y(y+1)/2 \bmod 2),y(\bmod 2),(x+y)z+(x+y)(x+y)/2(\bmod 2)$ ... and so on. And set accepting state ${0}\times {0,1}\times {0,1}$. I believe its working but I don't understand how to define on each state.


texts:
I'm creating a experimental toy language for my own education purposes (an impure typed Lisp based on Clojure - https://github.com/mikera/kiss)

I think I understand the concept of each expression in the language having a return type.

However some expressions may contain flow control statements that mean that the expression will not return normally, e.g.

An early function return
A break within a loop
A continue / recur within a loop
A goto (the horror...)

I'm not sure how to represent these in my type system. Should such things alter the type of the expression? Or should I have a parallel mechanism that enumerates alternative ways the expression may be exited?


texts: Push down automata acceptance by Empty stack and final state

texts:
I have a very basic question.  Can we have a PDA which can accept a string by  both final states and empty stack?
Can the same PDA accept by the two modes simultaneously ? If there are final states for acceptance and in addition to that at some point in time the input string is read completely and simultaneously the stack is empty but the state is non-final. Will it be accepted in that case ?


texts: number of subsegments that contain A[i] as the minimum

texts:
I've recently been thinking about this problem.

Given an array $A$ containing $n$ integers and an index $i$, find the number of subgements of $A$ containing $A[i]$ as their minimum.

To better illustrate the problem, consider the array $A = [5, 1, 7]$ and we want to find the number of subsegments containing $A[1] = 1$ as their minimum. Clearly the answer is 4 and we can easily enumerate them: $[1], [5, 1],[5, 1, 7], [1, 7]$.

What the fastest way to compute the number of subsegments?


texts:
If there is an interrupt from every keypress (or one for keydown, one for keyup, one for keypress?) how does the OS handle so many interrupts at the same time. A person typing at 120WPM would be sending more than 500 interrupts per minute. How does a process ever finish if there is a context switch for the CPU to handle the interrupt 500 times per minute.

I must be missing something here?


texts: Regular expression for a binary number that includes "10" and has an odd number of 0's

texts: I have been struggling trying to write a regular expression for a binary number that includes "10" and has an odd number of 0's, so far I have (1) * (00) * 10(1010)   * (00) * (1) * but it doesn't accept 0100 for example or 010101 etc, also if I write a finite automata for this how do I prove its correctness ?


texts: Conversion from octal numerical system to binary numerical system

texts:
I know that in order to convert a numeral in base-8 to a numeral in base-2 I can write each octal digit as a binary word of 3 bits.

I know that 2^3 = 8 that is exactly the dimension of the base of the octal system.

I just cannot understand the fundamental reason why it works. Is it just a coincidence?


texts: Given a set of LTL formulas, on which states does the Kripke structure hold?

texts:
I'm currently learning about LTL and CTL formulas and to get a better understanding I try to manually interpret the formulas over a given Kripke structure. Since I'm not 100% sure if my results are correct I would appreciate if anyone can verify them.
Task:
I showed on which states the given LTL formular hold.
Some LTL notation notes:
$X$ equals $\bigcirc$
$G$ equals  $\Box$
$F$ equals  $\diamond$

$Fc = \{\}$
My interpretation: $Fc$ means that on all paths $c$ holds sometimes the future. Since all paths come along $t4$ it doesn't hold for any state.

$G(b \vee c) = \{\}$
My interpretation: For all paths holds globally b or c.

$G(Fb) = \{t0, t1, t2, t3, t4, t5, t6\}$
My interpretation: For all paths holds globally that eventually b will be true.

$G(b \Rightarrow (Xa \Rightarrow Xb)) = \{t0, t1, t2, t3, t4, t5, t6\}$
My interpretation: Since $Xa \Rightarrow Xb$ is true for every state the implication $b \Rightarrow (Xa \Rightarrow Xb)$ must hold for all states too sinde $? \Rightarrow true$ is always true.

$a U (b U c) = \{t1, t3, t4, t5\}$
My interpretation: Following paths are valid: aaaaabbbc, bbbbc, c, ccc. Therefore the states $t1, t3, t4, t5$ are valid.

So can anybody confirm my results?


texts: Bounds for Akra-Bazzi versus Master theorem

texts:
I had my final exam today in an advanced algorithms course. In it there were two recurrence relations and I used the Akra-Bazzi theorem to solve them. After the examination I was discussing the problem with one of my colleagues and they apparently got a different bound using Master theorem. My question is which of this two bounds are tighter?

The recurrences were:

$1)\quad T(n) = 8T\left(\frac{(2n-1)}{4}\right)+n^3+n\log n$

$2)\quad T(n) = 3T(n/2)+n\log^2 n $

Now, correct me if I'm wrong but Akra-Bazzi gives 1) as $\Theta(n^3\log n )$ and 2) as $\Theta(n\log^2 n )$
Can somebody please verify 2) by Akra-Bazzi? I checked and regularilty condition doesn't hold for 2) .


texts: Is there a relation between the size of the domain/range of a function and its computability?

texts:
This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately.

I think there is no relation with the range as the range of the Halting problem is {0,1} and the range of the successor function is infinite. But I feel like I'm missing some subtleties here.


texts:
I was reading a paper here, and it mentioned "quotient structure" in the following sentence (third page, second paragraph of the paper)

  In order to obtain a representation of terms truly isomorphic to
  λ-terms, we need to build a quotient structure, quotient the set of
  raw terms with respect to alpha-equivalence. This construction based
  on a quotient corresponds very closely to the of presentation from
  standard textbooks on λ-calculus.

I am hoping that someone could point me a good tutorial on quotient structures.


texts:
So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says

"L contains palindromes that don’t ever have the same character occur twice in a row."

Let Σ = {a, b, c}

Let L = {w ∈ Σ∗| w = {w1, w2, . . . , wn} is a palindrome, and wi 6= wi+1 ∀ 0 ≤ i < n}.

In other words, L contains palindromes that don’t ever have the same character occur twice in a row.

In the second part can someone guide me how to make it's PDA or give an idea.


texts:
There are a number of collections of network (or graph) data sets freely available on the web, e.g.

http://snap.stanford.edu/data/index.html
http://www.cc.gatech.edu/dimacs10/downloads.shtml

I am looking for dynamic network data sets, i.e. networks whose structure varies over time. They seem to be quite rare: The SNAP collection contains only a few "temporal" graphs.

Do you known any other possible sources?


texts: Finding Triples that satisfy modulo equation in $O(n\log n)$ time

texts:
Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that satisfy the equation

$$a^2 + b^3 = c^4 \mod n\,,$$

where $a,b,c \in\{0,1,....,n-1\}$ and $n$ is any natural number.

Does anybody have any idea how to do this? Obviously checking all values yields $O(n^2)$ time.

I am able to compute the triples for a given value of $c$ within the desired bound since you can build a BST in $O(n\log n)$ time where the keys are the particular modulo values in $b^3$ and the values are the number of instances they appear. Then by calculating $((c^4 \!\!\mod n) + n - (a^2 \!\!\mod n)) \!\!\mod n$ for every value of $a$ and doing a search for that key in $b$ we achieve the desired runtime.

How can I achieve the same result for every value of $c$ rather than a specific one though?

I presume the $O(n\log n)$ run-time comes from some form of binary search, sorting or binary search tree but I am not sure exactly how to achieve this for all the values of $c$ rather than a specific one. Any help is appreciated. Thank you.


texts: What does the following symbols or expression mean?


texts: What does $\mathbf{Q}^+$ mean in approximation texts?

texts:
Often, in a lot of texts concerning approximation algorithms I see the following notation (for example, here in page 19 of the PDF or the first page of the introduction):

  ... and a cost function on vertices $c:V\to \mathbf{Q}^+$ ...

Is this just the positive rationals? Or is this something else?


texts: Can you reduce a precedence graph or do *all* relevant nodes need to be connected

texts:
Let's say we have the following simple transaction-schedule:

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
     | w(x) |
     |      | w(x)

T1 comes before T2, so in the precedence graph, we draw an arrow from T1 to T2. T2 comes before T3, so we draw an arrow from T2 to T3.

My question is: is it also necessary to draw an arrow from T1 to T3? T1 comes before T3, and the definition of a precedence graph says nothing about not drawing a line from Tx to Ty if there is some arbitrary Tz inbetween.

On the other hand, T1 -> T2 -> T3 implies T1 -> T3, and as the graph gets larger things will get a bit messy. Is it okay to 'reduce' a precedence graph?

If the answer to the above question is yes, here is a follow up - consider the following schedule:

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
 w(y)|      |
     | w(x) |
     | w(z) |
     |      | w(y)
     |      | w(z)

In the precedence graph, for the operations on x we draw an arrow from T1 to T2, for y an arrow from T1 to T3, and for z an arrow from T2 to T3. Would you be allowed to omit the arrow 'caused' by element z?


texts: Sorting array with two elements - in place and minimal number of comparisons, lower bound

texts:
Algorithm must be in place.
I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only $1s$ and $0s$.

Decision tree give us lower bound $\log(n+1)$.  It is to weak, because we know lower bound for findiing minimum, hence our algorithm must do at least $n-1$ comparisons.  If it is lower bound ?  I don't, but I think that it is $n$.

Why Do I think that lower bound is equal to $n$ ?

Let consider array $|a|=n$ such that $a[1]=a[2]=...=a[n-1]=0$ and $a[n]=1$.

It is needed at least $n-2$ comparisons to check that there is $n-1$ equal elements. And additional $2$ comparisons to check that $1$ is greater then rest of elements.

What is it real lower bound? What about my justification ?

Edit: We assume model computation as comparison $\le$.


texts: Similarities between bubble sort and selection sort

texts:
I have been looking through different websites and forums but I can't seem to find any post about the similarities between bubble sort and selection sort. Can someone help me plese?

Thanks


texts:
What is the difference between:

normalizing the row of an adjacency matrix and taking the right eigenvector
normalizing the row of an adjacency matrix and taking the left eigenvector
normalizing the columns of an adjacency matrix and taking the right eigenvector
normalizing the columns of an adjacency matrix and taking the left eigenvector

I think that if you take the left eigenvector (number of paths coming INTO a node) you should normalize the COLUMNS, while if you are interested in the RIGHT eigenvector (number of paths outgoing from a node) you should normalize the ROWS.

Why is l1 norm used?

Thank you :)


texts: Is the search for a k-Hamiltonian Path NP-hard?

texts:
A $k$-Hamiltonian Path is an Hamiltonian Path where each node (but the last $k$ nodes on the path) is connected to his $k$ successors, and the last $k$ nodes are connected to all of their successors.

This is an Hamiltonian Path:

This is a 3-Hamiltonian Path:

How would you prove that searching for a k-Hamiltonian Path is also NP-hard (if it is)?


texts: How to avoid having to store extra information about padding (for byte size alignment) with Huffman coding

texts:
When storing the encoded Huffman bit stream in bytes, in general, either

the final byte gets padded or
a pseudo end-of-file symbol gets used

In the former case, the number of bits padded needs to be stored somewhere, requiring another 3 bits. In the latter, you will lose some efficiency due to the additional pseudo symbol.

So how can I avoid the extra cost of a pseudo symbol, and also avoiding the need to store/transmit extra bits to hold the number of pad bits?

N.B. On the one hand, I'm interested in compressing short strings, so saving 3 bits on average can shave off another 1% or so of the data.

But more importantly, getting rid of the need to send the padding info (which is only known after compressing the whole string) before the encoded data means I can more easily perform the algorithm in a streaming fashion. This is not really necessary for short strings, where everything may be kept in memory, but sometimes my strings actually do get much longer, and I don't want to have to keep that in memory (considering there are hundreds of simultaneous encodings going on).


texts:
I'm working on the following problem:
HALFCYCLE (HALFC):
Input:
A directed graph $G = (V,E)$.
Output:
Whether the longest cycle in $G$ has length $ \lfloor |V|/2 \rfloor$.

Prove that if $\mathsf{PH} \ne \mathsf{coNP}$ then HALFCYCLE is not NP-complete.

I have no idea how to solve this implication.


texts: Prove that "Finishing the degree in three years" problem is NP-Complete

texts:
I was asked in an interview the following question:

We'll define the "Finishing the degree in three years" problem in the following manner:

Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, where every course $c_i\in C$ is given a list $R_i\subseteq C$ of the precondition courses for this course, and also we are given the maximal amount of courses in each year $m_1, m_2, m_3$, and we need to decide if it is possible to finish the degree in three years. Meaning, can we divide the courses for three years $Y_1, Y_2, Y_3 \subseteq C$, such that the following conditions are satisfied:

All courses are studied within 3 years: $Y_1\cup Y_2\cup Y_3=C$.
Each courses is studied only after all of its precondition courses have been studied, meaning: for any $c_i\in Y_1: R_i\subseteq\emptyset$, for any $c_i\in Y_2: R_i\subseteq Y_1$, for any $c_i\in Y_3: R_i\subseteq Y_1\cup Y_2$.
The number of courses studied in each year is not higher than maximum allowed, meaning: $|Y_i|\le m_i$ for each $i\in\{1,2,3\}$.

Prove that the "Finishing the degree in three years" problem is NP-Complete.

I was told that the reduction should be from the clique problem but it has been a week since I've started thinking about it and I couldn't prove it. If someone can please post a thorough solution I would appreciate it a lot.


texts: Examples of exponential time linear space exact algorithms

texts: I am looking for examples of NP-complete problem-solving exact algorithms with a linear space complexity and an exponential time complexity. Algorithms which solve the k-SAT problem exactly (such as DPLL and PPSZ) are good examples. Indeed, the space they require is at most linear in the number of variables of the formulas given as input. Are there NP-complete problems for which there are (well-studied and non-trivial) exponential time & linear space algorithms?


texts: Complexity of finding factors of a number

texts:
I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division:

For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ then add $d$ and $n/d$ to the factor list. Assuming division and appending to a list are $O(1)$ operations for a CPU, this seems to be $O(\sqrt n)$.

The second is to use trial division with prime factors:

Sieve all primes up to $\sqrt n$. The time complexity of the Sieve of Eratosthenes is $O(n \log \log n)$, so this is $O(\sqrt n \log \log \sqrt n)$?
From that list of primes, repeatedly try to divide by $p$ and move on to the next prime if the current prime will not divide evenly anymore. If it does divide, add $p$ and $n/p$ to the factor list. The density of primes is $n / \ln n$, and since primes go up to $\sqrt n$ the supposed time complexity is $O(\sqrt n / \ln \sqrt n)$. However, this does not take into account dividing by primes more than once.

I would like to know if my analysis is correct. It seems counter-intuitive that trial division only takes $O(\sqrt n)$ time, but $n$ is integer size, not input length. I don't think the time complexity of the second method is correct, but I am sure it must be faster than the first (trying primes instead of all numbers within a range).


texts: how to track a uop's flag in microprocessor?

texts: Lots of processor renaming their register to achieve the goal of out-of-order,but how to track the instruction's flag,such as carry flag,overflow flag,etc?


texts:
I've seen a reduction that's done by adding another vertex to the graph and creating a path through that vertex.

Why do I need to add a vertex? Cant I just remove an edge? Lets say the graph with the HamCycle is G,s,t when removing the edge between s and t dont I get a path the goes through all the vertexes that's qualified as a Hamiltonian path?


texts: Comparison between: Maximum Absolute Difference & Min Steps in Infinite Grid

texts:
There are two questions that I am trying to draw a comparison between:

Q1: Maximum Absolute Difference
You are given an array of N integers, A1, A2 ,…, AN. Return maximum value of f(i, j) for all 1 ≤ i, j ≤ N.
f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

Q2: Min Steps in Infinite Grid
You are in an infinite 2D grid where you can move in any of the 8 directions :
    (x,y) to
    (x+1, y),
    (x - 1, y),
    (x, y+1),
    (x, y-1),
    (x-1, y-1),
    (x+1,y+1),
    (x-1,y+1),
    (x+1,y-1)

I was reading up about the Q2 and I came across this stackoverflow question. Here, the accepted answer reduces this question to given a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance)

Reading up, I think both these questions are exactly the same except that Q1 is asking for Manhattan Distance in 1D and Q2 is asking for Manhattan Distance in 2D.

I am not very clear about this. Can someone please verify my observation?


texts: Construct polygons from axis-aligned intervals

texts:
Scenario

Consider one or more curved shapes in 2D space, clipped to a rectangular viewport. For example:

Unfortunately, data that would describe these shapes precisely, is not available.

Input data

All that is available are the intersections of the shapes with a few horizonal and vertical lines, sampled at coarse intervals:

In the example at hand, the available data could be expressed like this:

y    x-ranges
-------------------------
 0   0.0 - 2.2
 1   0.0 - 4.3
 2   0.0 - 4.2
 3   0.0 - 3.7, 6.8 - 8.5
 4   0.0 - 3.6, 6.6 - 8.6
 5   0.0 - 3.8, 6.7 - 8.4
 6   0.0 - 4.7
 7   0.0 - 1.1, 3.1 - 5.3
 8   0.0 - 0.2, 3.5 - 5.2
 9
10

x    y-ranges
-------------------------
 0   0.0 - 8.4
 1   0.0 - 7.1
 2   0.0 - 6.5
 3   0.3 - 6.8
 4   0.5 - 2.4, 5.3 - 8.8
 5   6.2 - 8.5
 6
 7   2.7 - 5.4
 8   2.5 - 5.5
 9
10

It's not much, but when both sets of intervals are combined, it already allows a human viewer to "see" the original shapes quite well:

The Problem

But how would a computer algorithm go about approximating the outlines of the original shapes based on data like this?

Ignoring interpolation/smoothing for now, the problem becomes grouping and ordering the interval end-points in the correct manner to get the ordered vertices of one or more polygons corresponding to the original shapes:

In the example at hand, the output data of the algorithm could be expressed like this:

Polygon 1:
(0, 0) - (0, 8.4) - (0.2, 8) - (1, 7.1) - (1.1, 7) - (2, 6.5) - (3, 6.8) - (3.1, 7) - (3.5, 8) - (4, 8.8) - (5, 8.5) - (5.2, 8) - (5.3, 7) - (5, 6.2) - (4.7, 6) - (4, 5.3) - (3.8, 5) - (3.6, 4) - (3.7, 3) - (4, 2.4) - (4.2, 2) - (4.3, 1) - (4, 0.5) - (2.2, 0) - (0, 0)

Polygon 2:
(7, 2.7) - (6.8, 3) - (6.6, 4) - (6.7, 5) - (7, 5.4) - (8, 5.5) - (8.4, 5) - (8.6, 4) - (8.5, 3) - (8, 2.5) - (7, 2.7)

Help needed

I'm having trouble coming up with an algorithm to do this. I'd greatly appreaciate:

Clarity on what kind of problem this is, what kind of algorithm is needed, etc.
(Part of what makes this difficult for me is that I don't know what search terms to use to research this.)
Pointers to edge cases etc. that I need to consider, that I may not yet have.
Pointers to appropriate literature.
Suggestions/discussions of the algorithm itself, obviously.


texts: Is TSP a more detailed form of the "Set Inclusion" question?

texts:
Background

Set Inclusion

GIVEN: set of cards, some with blue backs, and each with a positive, integer face value.

QUESTION: Are there any [blue-backed cards] with a [face value <= L]?

2 independent variables: [blue/white cards], [integer face values]

Function A: Select a blue-backed card

face value depends on which card you select
each blue card potentially has face value <= L

thus, worst-case = [check all blue cards]

Function B: Select a face value <= L

blue back depends on which card you select
each card w/ face value <= L potentially has blue back

thus, worst-case = [check all cards w/ face value <= L]

Function B cannot exist. There is no way to verify that a selected card has a blue back, since don't know key info:

How are cards marked with a blue back?

WORST-CASE: turn over all blue-backed cards (Function A)

Travelling Salesman

GIVEN: complete graph, G(V,E), where all edges are positive, integer values.

DEFINITION: "config"

{A, B, u, v} where u & v are 2 vertices, and A & B are the remaining vertices split up as evenly as possible

DEFINITION: "optimal tour of a config"

shortest path from u to v, only going thru each vertex in A once, and
shortest path from v to u, only going thru each vertex in B once

Assume we have a function, f, that returns the optimal tour for a given config, in sub-exponential time. (EDIT: if you can prove this function must take exponential time, you've shown $P\neq NP$.)

A smallest tour must be the optimal tour of one of the configs in G.
Any config could produce the smallest tour.

NOTE: Each tour is an edge-set that can form |V|/2 or |V| configs, for even or odd |V|, respectively.

A COMPLETE GRAPH is equivalent to: set of cards, some with blue backs, and each with a positive, integer face value.

each card represents a set of edges with size = |V|
blue backs mark any edge-sets that are an optimal tour for a config
face value is the sum of the edge-set represented by the card

QUESTION: Are there any [blue-backed cards] with a [face value <= L]?

2 independent variables: [blue/white cards], [integer face values]

Consider case where L = length of smallest tour.

Only need look at blue cards (edge-sets that are an optimal tour for a config)
Only need look at cards w/ face value = L (edge-sets with sum = L)

Function A: Select blue-backed card

face value depends on which card you select
each blue card potentially has face value = L

thus, worst-case = [check all blue cards]

Function B: Select a card with face value = L

blue back depends on which card you select
each card w/ face value = L potentially has blue back

thus, worst-case = [check all cards w/ face value = L]

Unlike "Set Inclusion", now you can verify that a selected card for Function B has a blue back, by running f on the selected card's configs.

However, controlling either variable, [choosing blue card] or [choosing card w/ face value = L], causes the other to be uncontrollable.

WORST-CASE:

FACE-DOWN Approach: turn over all cards with blue back (Function A)
FACE-UP Approach:   turn over all cards with face value = L (Function B)

Question

So the final question: Is TSP-Decision a version of "Set Inclusion" that has enough information to define a Function B?

If so, does this mean that the worst-case running time of TSP-Decision is lower-bounded by the smaller of the 2 domains of Functions A and B?  i.e. min{number of blue cards, number of cards with face value = L} -- still only for the case where L = length of smallest tour.

EDIT: Both those lower-bounds are exponential, so if we can show that TSP-Decision is lower-bounded by them, we've shown that P != NP.


texts: How do I reconstruct the forest of syntax trees from the Earley vector?

texts:
Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have at least one, then the string is accepted.

Using the Earley vector to reconstruct the parsing tree(s) is less obvious. Actually, I cannot figure out how an algorithmic procedure would work, moreover the only references I found were either vague or super-technical. Could anybody shed some light on it?


texts:
In this paper, it is mentioned that BPTIME does not have a time hierarchy theorem, unlike DTIME. To quote the part where the author explains why:

It must hold that for any $x$, either $\Pr[M(x) = 1] \geq \frac{2}{3}$
or $\Pr[M(x) = 1] \leq \frac{1}{3}$. It is undecidable to test whether
a machine $M$ satisfies this property and it is also unknown whether
one can test if $M$ satisfies this property for a specific $x \in \{0,
1\}^{n}$ using less than $2^{n}$ steps.

Here are my questions:

Why is it undecidable to test for any $x$ whether for a probabilistic Turing machine $M$, whether $\Pr[M(x) = 1] \geq \frac{2}{3}$ or $\Pr[M(x) = 1] \leq \frac{1}{3}$? Can we not directly infer it from the string corresponding to the description of $\langle M \rangle$?
If (1) is "undecidable", why is the second fact (testing (1) for a specific $x \in \{0,
1\}^{n}$ using less than $2^{n}$ steps) merely "unknown"? Why doesn't the same proof of undecidability work?
How are these two facts relevant to why BPTIME does not have a hierarchy theorem? In what specific step does the diagonalization argument break down when we are trying to prove a time hierarchy theorem for BPTIME?


texts: Learning the activation function in a neural network?

texts:
Neural networks use specific activation functions, commonly used ones are tanh, ReLu.

I have seen that people have experimented with continuously parametrices activation functions, for instance here. Here, the additional parameter $\alpha$ which interpolates from logarithmus to linear to exponental, is optimized during the back-propagation step of the training.

I wonder whether much more general types of activation functions have been considered, such as Taylor-expansion of an unknown function where the coefficients are parameters in the training? It seems is a lot of degrees of freedom, that are not considered conventionally.

So my questions:

What is known about optimimality of actionation functions, apart from empirally testing? Are there mathematical proofs, for instance, that show some necessary properties for ideal learning (for instance, is monotonicity necessary, or could a sinusoidal activation function lead to optimal results too?)
If the answer to question 1 is no: Is there much research investigating the topic of learning activation functions?


texts:
Is there a name for this infinite language?

$$L = \{ 0(,1)^*(,2)^*(,3)^*....(,n)^* \;\mid n \geq 1\}$$

A string $w \in L$ is simply an ordered list of increasing integers in which every integer  $\geq 1$ can be repeated 0 or more times, for example "0", "0,1", "0,1,2,2", "0,1,2,3", "0,1,1,4,4,4,21,21".

Or perhaps a name for its unary variant: $L_U = \{ 1^{x_1}(,1^{x_1})^*,1^{x_2}(,1^{x_2})^*,...,1^{x_n}(,1^{x_n})^* \mid x_1<x_2<...<x_n\}$


texts: What are some practical problems which require the use of Kadane's algorithm?

texts:
I've worked through Kadane's and love its elegance. I am worried though, unless asked specifically about arrays and it's obvious that's what's for dinner, I won't know to use it.

What are some real-life problems and applications where this algorithm is key? How would one go about recognizing them in the wild?


texts: Learning a specific functional form with machine learning

texts:
Suppose I have only three independent features (x, y, z) as the input to some machine learning routine (e.g. neural network). From some domain knowledge, I know that the output o(x, y, z) must have the specific functional form

o(x, y, z) = f(x)*g(y)*g(z)

where the g(.) are the same function. The details of f(.) and g(.) are not known beforehand (except that f(.) is a decaying function with respect to x). Given that there is no upper limit on the sample size, is it possible to incorporate such a functional form (or in general, any specific functional form) into the machine learning routine?


texts: Non-deterministic algorithms and Tautologies

texts:
I am studying the lecture The Complexity of Propositional Proofs. Here there is a definition together with a discussion (page 3). I don't understand
that discussion.

Let $F$ denote the set of propositional formulas over the connectives $\wedge$, $\vee$, $\rightarrow$ and $\lnot$, with a countably infinite supply of propositional variables. An abstract propositional proof system is a polynomial time function $V: F \times \{0,1\}^* \to \{0,1\}$ such that for every tautology $\tau$ there is a proof $P \in \{0,1\}^*$ with $V(\tau, P) = 1$ and for every non-tautology $\tau$, for every $P$, $V(\tau, P)=0$. The size of the proof is $|P|$.
Definition equates propositional proof systems with non-deterministic algorithms for the language of tautologies.

Why does the author conclude "Definition equates propositional proof systems with non-deterministic algorithms for the language of tautologies."?


texts: Applying Akra–Bazzi with an unbounded number of summands

texts:
The Akra–Bazzi method handles recurrences of the form
$$
f(n) = \sum_{l=1}^k a_l f(n/b_l).
$$
Does it work when then number of $a \cdot f(n/b)$ is not finite, meaning that we have a sum that depends on our input $n$?
What about this:
$$ f(n) = \sum_{l=1}^{n} f(n/3^l) $$
Can I say that we need to find the $p$ so that
$$ \sum_{j=1}^{n} (\frac{1}{3^j})^p  =1,$$
and because $n \rightarrow \infty$ we can say it is an infinite geometric sum?  Or because $n$ is our input we can't say that, and the Akra–Bazzi method fails to deal with this kind of stuff? There is no internet site I found that says $k$ (which in Wikipedia is the number of $f(n/b)$) needs to be finite.


texts:
I am writing a publication about websites privacy. Quite a standard for such works [e.g., 1, 2] is to summarize categories of websites in the study, to either prove that the study is not biased, or the opposite that some privacy violations are skewed towards some categories.
I found that categories are usually IAB categories and there is a pleothora different APIs (BrandFetch, ClearBit, WebShrinker) offering resolution of website to this IAB category. However, these APIs seem to be meant for SEO analysts, with pricing fairly exceeding 1000$ for getting categories of Alexa/Tranco top 1M websites. They offer far more details (logo, Facebook link, and similar services for marketing analysis), while I want just an offline list of these IAB categories, at most business size and country would be useful.
The past works were not helpful. [1] refer to McAfee SmartFilter Internet Database (discontinued), [2] to SimilarWeb, another online service that does not seem to scale. Also Alexa lists by categories were discontinued in September 2020.
I feel like I am just not searching the right keywords. Maybe there is some plain text/csv file with all of this for top 1M websites that would solve all my issues. In parallel I am contacting SimilarWeb and WebShrinker if they would give me academic access for acknowledgement in the publication. Do you know source of such a list of top 1M websites with their IAB categories?
References
[1] Urban, Tobias, et al. "Beyond the front page: Measuring third party dynamics in the field." Proceedings of The Web Conference 2020. 2020.
[2] Trevisan, Martino, et al. "4 years of EU cookie law: Results and lessons learned." Proceedings on Privacy Enhancing Technologies 2019.2 (2019): 126-145.


texts: Compare the growth of $2^{n}$ to $n^{a}$ for all $a \in \mathbb{N}$?

texts:
How to find which of $2^{n}$ to $n^{a}$ is an (upper bound, tight bound asymptotically larger, etc..)? I tried to use the formula:

$$ \lim_{n\to\infty} \frac{f(n)}{g(n)} $$

where $f(n) = n^{a}$ and $f(n) = 2^{n}$

But I cannot figure out how to use L'Hospital's rule to solve it.  We are guaranteed that $a \in \mathbb{N}$.


texts: Quantum algorithms for logical inference - reference request?

texts:
Microsoft is committed to the building of the scalable, industrial size topological quantum computer, Visual Studio integrated programming language and SDK will be released by the end of this year (2017). From the other side, logical/symbolic methods in computer science (natural language processing, inference, knowledge management etc.) are considered to be impractical due to high complexity/computational time, that is why subsymbolic methods (neural networks, statistical methods) are used widely today.

The question is - are there quantum algorityms for speedup of classical logical problems (i.e. all the non-quantum logics - classical, non-classical, modal, defeasible, linear, categorical, adaptable, etc.), like automated theorem proving, backward and forward reasoning and so on?

I have heard that Grover search algorithm can be used for solving Boolean satisfiability problem but are there any other quantum algorityms for logics?


texts: Is there a name for this relation on CFGs?

texts:
I'm looking for the name (or a name if there isn't one already) of this relation between $G_1=\left<\Sigma_1,\mathcal{N}_1,\mathcal{R}_1,S_1\right>$ and $G_2=\left<\Sigma_2,\mathcal{N}_2,\mathcal{R}_2,S_2\right>$:
$$\exists f_\Sigma\in\Sigma_1\times\Sigma_2,f_\mathcal{N}\in\mathcal{N_1}\times\mathcal{N}_2 \text{ surjective functions s.t. }\\ \mathcal{R}_2=\left\{f_\mathcal{N}(N)\rightarrow f(\alpha)\mid N\rightarrow\alpha\in R_1\right\}\text{ and } S_2=f_\mathcal{N}(S_1) $$
where $f$ is the extension of $f_\Sigma$ and $f_\mathcal{N}$ to words ($f\in(\Sigma_1\cup\mathcal{N}_1)^*\times(\Sigma_2\cup\mathcal{N}_2)^*$).

In other words, you can map $G_1$ to $G_2$ (but not necessarily $G_2$ to $G_1$).

If the mapping function were bijective, this would be an isomorphism, but they're not.

What about if only $f_\mathcal{N}$ is  surjective, i.e. $f_\Sigma$ is bijective, or even the identity function?


texts: In control flow graphs, what is the difference between a path and a branch?

texts:
I'm studying for an exam on software testing and in my notes I found this:

Many more paths than branches. A pragmatic compromise will be needed

I cannot understand the difference between paths and branches; each time I work out the paths and branches of a graph I end up with the same number. Thanks!


texts: How many states when converting CFG to PDA

texts: When converting a CFG to a PDA I know that you get three main states, Qstart, Qloop and Qaccept. But Qloops will need a various amount of states, and my question is how many? Is there a way to find out the "worst case scenario" of how many states there can potentially be? I don't mean for one particular CFG, but in general. I'm having difficulties trying to figure out how I can calculate this...


texts: What does $\omega{(1)}\cdot O(logN)$ mean?

texts:
What does $\omega{(1)}$ mean as a factor?
In some papers, there exists some asymptotic analysis which comprises a product of multiple Landau notation like $\omega(1)\cdot O(logN)$.
In this example, what is the meaning of the additional factor $\omega(1)?$


texts:
Possible Duplicate:
  Dynamic programming table for finding similar substrings is too large

Say I have a sequence $S$ of 0s and 1s such as $S = [1, 0, 0, 1, 0, 1]$

How would I efficiently find a pair $(i, j)$ such that $j - i$ is maximum and $(\sum_{z=i}^j S_z ) \leq K$

UPDATE

The following algorithm solves the above problem in O(n).

def longest_range_min_sum(S, K):
    longest = 0
    i = 0
    running_sum = 0
    while i + longest < len(S):
        if S[i + longest] == 1:
            running_sum += 1
        if running_sum > K:
            if S[i] == 1:
                running_sum -= 1
            i += 1
        else:
            longest += 1
    return longest


texts: Are there problems that are known to be in ZPP but not in p

texts: Are there any problems that are known to be in ZPP but not in p?


texts: Difference between $O(n^2)$ and $O(m)$ for algorithms on graphs

texts: Given a graph $G$ directed with n nodes and m edges, if an algorithm solves a problem  $X$ on $G$ with a complexity $O(n^2)$, while an other algorithm solves same problem $X$ on $G$ but with complexity $O(m)$, what is the most efficient ?


texts: Complement of language $\{ x \in \{a,b,c,d\}^* : \exists$ prefix $y$ of $x$ such that $||y|_a - |y|_b|\leq 10 \}$

texts:
Is the complement of the following language a regular language?
$$L = \{ x \in \{a,b,c,d\}^* : \exists \text{ prefix }y\text{ of }x\text{ such that }||y|_a - |y|_b|\leq 10 \}$$

My first thought is that it is not a regular language because finite automata can't store the number of $a$ in $x$ and the number of $b$ in $x$, but I guess I do not understand what is the meaning of the prefix here. Could someone help me?


texts: Red-black tree. Adding a red child to a red node with a black sibling

texts: According to my lecture notes, adding a red child to a red node with a black sibling in a red-black tree, is equivalent to changing a 3-node into a 4-node in a 2-3-4 tree. I've built several red-black trees with different values to try to get to this situation, but I never seem to get to the situation where I have a red node with a black sibling, and where the value to be inserted will be inserted below the red node. I'm starting to ask myself if this situation could ever happen in a red-black tree?


texts: Testing the property of being a union of three disjoint cliques

texts:
Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of three disjoint cliques.

I've been sitting for a few hours and I don't have any idea of how to solve this one ... anyone has any ideas / leads?

I have tried to pick the vertices randomly and then conclude from the graph they make G' what it says about G , I've divided into cases by connectivity : if the connectivity is 4 or more it is easy to conclude that the Graph do not has the property . i have struggled with the math in the other cases...sorry for not posting my progress (I am new)


texts: Counting the number of comparisons in red black tree

texts:
I have an array with $N$ elements and I run an algorithm that find how many distinct elements are in the array by using a red black tree as follows:

for each element

if element not in tree

insert element to tree
increase distinct elements counter by 1

I need to find a formula to count how many comparisons the algorithm performed with $N$ as variable for both the best case and worst case.
For the best case this is pretty easy, the array include $N$ instances of the same element so each search does 1 comparison and there is no insertions, except for the first element, hence the number of comparisons is $N-1$.
But I'm having trouble with the worst case. Firstly I'm not sure what is the worst case in this scenario as red black tree balance itself after each insertion, I do know that all the elements in the array must be distinct but in order to get the worst case I will need that each search will go down the longest route to a leaf and same with the insert. How can i devise an input array that cause the worst case and how to create a formula that calculates the max number of comparisons?


texts:
I want to prove something but I am not sure if it is the right way to do it.

I have two LTS that define different semantics. A=($Q_a,Λ,\to)$, and B=$(Q_b,Λ\cup\{\beta\},\leadsto)$, where $\beta$ is a silent transition.
So if I am understanding correctly, to prove that A simulates B through a relation $R_1$,i.e, $AR_1B$ I need to prove that:
$\forall (p,q)\in R_1,\forall\sigma\inΛ$ such that $q\overset{\beta^*\sigma\beta^*}{\leadsto}q',\exists p'$ such that $p\overset{\sigma}{\to} p'$and $(p',q')\in R_1$,
and to prove that B simulates A through a relation $R_2$,i.e, $BR_2A$ I need to prove that:
$\forall (p,q)\in R_2,\forall\sigma\inΛ$ such that $p\overset{\sigma}{\to}p',\exists q'$ such that $q\overset{\sigma}{\leadsto} q'$ and $(p',q')\in R_1$.

What is confusing me is that the unobservebale actions ($\beta$) appears in one sens and not in the other and I am not sure on which sens I should put them.

Any help would be great.


texts: Proofs based on narrowing down sets of possibilities

texts:
Consider the argument made in this question based on the comparison sorting lower-bounds proof, which runs as follows.

First, the comparison sorting lower-bounds proof was recited:

For $n$ distinct numbers, there are $n!$ possible orderings.
There is only one correct sorted sequence of the $n$ numbers.
We are given that comparison ($<$) is the only operation we have that can narrow down the $n!$ possible orderings, and each comparison has only two possible outcomes.
So $\log_2(n!)$ comparisons are required.

Then, the argument was generalized:

Define a space of input possibilities
Define the goal space, a subset of the input space
Define the amount of information that is gained at each step of the computation
Calculate the information difference between the space of possibilities and the goal space and divide by the information gain per step to yield the lower bound on the number of steps.

Both arguments above rely on information arguments to prove a lower bound on the number of steps.

Question: are there proofs and/or proof strategies like the above which:

prove lower bounds,
define an input space,
define a goal space which is a subset of the input space, and
do not rely on information arguments?


texts: Difficulty in reducing non halting problem to a given problem

texts:
I am having difficulty in reducing non halting problem to the given problem to prove that language is non R.E

For eg Completeness problem of TM .

In the above problem, we accept $\Sigma^*$ if H does not halt on w . For doing that, we give an input $x$ and simulate H on w for $|x|$ steps. I don't understand how can we deduce that H does not halt on w by just simulating H on w for $|x|$ steps.

Suppose H halts on w after $k+2$ steps and $|x| = k$. Now if we simulate H on w only for $k$ steps, how can we say that H will never halt or does not halt on w? It does not halt after $k$ steps but halts after $k+2$ steps.

I think that non halting problem is whether H does not halt on w and not whether H does not halt on w in k steps.

Can someone please help me in understanding the reduction?


texts: Is it possible to create a "Time Capsule" using encryption?

texts:
I want to create a digital time capsule which will remain unreadable for some period of time and then become readable. I do not want to rely on any outside service to, for instance, keep the key secret and then reveal it at the required time. Is this possible? If not, is some kind of proof possible that it is not?

One strategy would be based on projections of future computing capabilities, but that is unreliable and makes assumptions about how many resources would be applied to the task.


texts: What are some interesting applications of the skyline problem?

texts:
You are given a set of $n$ rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each rectangle, you’re given the $x$ position of the left edge, the $x$ position of the right edge, and the height. Your task is to draw an outline around the set of rectangles so that you can see what the skyline would look like when silhouetted at night.
Source

Drawing in practice I imagine can come in different forms, for example if a building is described by a triple (leftX, height, rightX) then the output can be a left to right ordered list $\{x_{1},h_{1},x_{2},h_{2},x_{3},h_{3},x_{4},h_{4},...\}$ where each $x_{i}$ represents a vertical edge and each $h_{i}$ represents a horizontal edge.

This problem is clearly defined and there are some quite efficient algorithmic solutions, however I could not find anywhere the motivation for this problem. Why would anyone want to solve it? Are there any interesting applications where being able to solve this problem efficiently is important?


texts: Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?

texts:
I've learned from several sources that an LL(1) grammar is:

unambiguous,
not left-recursive,
and, deterministic (left-factorized).

What I can't fully understand is why the above is true for any LL(1) grammar. I know the LL(1) parsing table will have multiple entries at some cells, but what I really want to get is a formal and general (not with an example) proof to the following proposition(s):

A left-recursive (1), non-deterministic (2), or ambiguous (3) grammar is not LL(1).


texts: Can pseudo random number generator generate all possible sequences?

texts:
Suppose I have a random number generator G that takes in a seed s from the set of integers. Suppose we have a sequence of numbers Q where |Q| = k. Does there exist a seed s such that G(s) produces the sequence Q, for any Q with any length? This is an existence question; does it exist or not, the process of finding a random number generator is irrelevant. The code for G is finite as is the seed s.

My intuition is that no, moreover, it's impossible to construct such a G with these properties. Unfortunately I can't justify my intuition.


texts:
x∈ L1* ∪ L2*  ⇔ x∈ L1* ∨ x ∈L2*  ⇔ x ∈(L1)* ∨ x∈(L2)* ⇔ x ∈L1* ∪ L2* ⇔ x∈(L1∪L2)*

Is it enough to prove it this way?


texts: In the Resolution equivalence ($\neg A \implies B, B \implies C \models \neg A \implies C$) must $A$ be negated?

texts:
The sheet of equivalences given to us in class provides the the equivalences

\begin{array}{|c|c|c|}
\hline
\text{Resolution} & A \vee B, \neg B \vee C \models A \vee C &
\neg A \implies B, B \implies C \models \neg A \implies C \\
\hline
\end{array}

I noticed that the $A$ is negated. Is this necessary for proper Resolution? Or is this just an example that $A$ can be negated?

To me it makes logical sense that $A \implies B, B \implies C \models A \implies C$, but being somewhat new to the subject matter I would like to ensure that $\neg A$ is not necessary for Resolution.


texts: Algorithm for cost function maximization

texts: I have a system that takes in 'm' inputs and provides a cost value as an output. The system is a "black box" to me. The inputs can be varied and the corresponding output can be observed, however, I have no prior knowledge of the function that this box implements. Given that I can fiddle with the input values(all real valued), is there an algorithm or a learning based solution that can maximize the cost function in minimum number of iterations? I think this might be a well known problem, however, this genre is way beyond my ken and I am finding it difficult to frame the terms I should be googling for. A link or mention of the name of the algorithm or a short description of the solution would be appreciated.


texts: Flow value over edges in Max flow/Min Cut Ford Fulkerson

texts: Is it true that if a given edge e is in the min cut of a graph that there exists a max flow of the graph that has e with its full capacity?


texts: Grammar that generates a language with more "a" than "b"

texts:
I need to find a grammar that generates the language composed by all words that have more $a$ than $b$ given an alphabet $\{a,b\}$

I tried the following production rules:

S->B
B->b | ABB | BAB | BAB | BBA
A->a

with this rules it's fairly simple to proof that all the words that the grammar generates are made up with more $a$ than $b$.

How can I proof that all words made up with more $a$ than $b$ can be generated that way?


texts:
lately I'm reading about descriptive complexity, which I find is a fascinating branch of computational complexity.
I found many formulas in $\exists$$SO$ that describe problems with graphs but none that describes the 3SAT language.

Thinking about it, I came to an "atomic" description like this:

$\exists$$v$$\forall$$C$ $(P(C))$

Where $v$ is a literal, $C$ is a clause (i.e. the $OR$ of 3 literals) and $P(C)$ means that $C$ is true.

However I'm not satisfied with this definition, I don't think it captures the complexity of the 3SAT language, especially the dependence of the variables on one another. Can you tell me a correct formula to describe this decision problem? Thank you.


texts: How realistic is the i.i.d assumption in the definition of Shannon's entropy?

texts:
Let me first say I come from a physics background and have about zero exposure to computer science, so the question may be very naive. Shannon's entropy looks perfectly natural and useful from a statistical/thermal physics point of view, but now I'm trying to understand how it is applied for real computers.

Normally the messages we want to store and process in a computer have grammar and meanings, which seems to suggest the symbols constituting the message must follow some conditional probability distribution, and the utterance of the symbol at the nth position should change the probability distribution of the symbol that will appear at the (n+1)-th position. However, in Shannon's definition symbols are assumed to be independent and identically distributed random variables, which seems to be far from realistic, so how come it is still a useful concept for computers?


texts:
I understand the basic but what I dont understand is this:

so base 16 to base 10

357/16 = 22.3125 but on this example im looking at says remainder 5?


texts: Difference between Image Analysis and Computer Vision

texts: I have searched the web and I have only found the differences between Image Processing and Computer Vison (also in this website too). In addition, sometimes Image Analysis is confused with Image Processing, which is untrue. Reading the Wikipedia article, it makes me thing that Image Analysis is another name for Computer Vision. Therefore I am confused. What is the real difference of those two?


texts:
I have a hard time understanding the following lines from our lecture notes:

$f \in \text{FP}$ iff there is a transducer T that computes $f$ and there exists a polynomial $p$ such that $TIME(T(x)) \leq p(|x|).$

Note: If $f \in \text{FP},$ then $|f(x)| \leq p(|x|)$ holds for a fixed polynomial $p.$

Examples:

$f(x) = x^2$ ($x$ is a binary number)

$f(x) = $ Table of the shortest paths from a start node s in a directed graph $G,$ where $G$ and $s$ are coded as $x.$

$f(x) = 2^x$ is not in $\text{FP}.$

Can somebody please explain the examples in a dummy-friendly way?


texts: Upper bound for the time complexity of a TM in P on input x?

texts:
I am trying to show that the following problem is P-complete with respect to LOGSPACE reductions: given a Turing machine $M^*$, an input $x$ for that machine, and a number $t$ in unary, does $M^*$ accept $x$ in $t$ steps?

To do that I want to compute an upper bound on the time complexity of some TM $M$ in P on input $x$. I tried to use the maximum number of configurations, but failed because I don't know the space complexity either - I only know that space and time complexities are polynomial.


texts:
INPUT: undirected graph, s, t

OUTPUT: connectivity of s and t

I perform BFS on s AND t, each taking turns to make one traversal.

When a vertex exists in both s and t's BFS tree, we can assume it is connected.

When one tree is done traversing but the other is not, s and t are not connected.

Does such an algorithm exist or am I making stuff up?


texts: Alternative way of proving a language is $NP$

texts:
I would like to show a language $A$ is in $NP$.

I can find a TM for $A$, but I wanted to try a different approach and see if it is correct.

Let $B$ be a known problem in $NP$. If I show a polynomial time reduction $A \leq B$, will this imply $A\in NP$?

I believe it will, but I am not 100% sure.


texts: Computer science fields that deal with peer-to-peer systems

texts: I'm an undergraduate and am looking forward to becoming an academic; do the whole PhD stuff and start doing research. I'm interested in a variety of computer science related things but lately P2P technologies have really caught my interest. I have the impression that I need to choose one of the computer science fields to perform my PhD studies in, so now I'm wondering how to do  that, given my interest in P2P technologies. Would P2P fall under the area of distributed systems and such?  Which fields of computer science are most relevant to P2P systems?


texts: Show that if A is regular, then the subset containing only even language strings, is also regular

texts:
A language A, even(A) is the subset of A consisting of those strings in A of even length:

even(A) = { x∈A | |x| is even}

I need to use closure properties show that if A is regular, then even(A) is also regular.

Isn't that a definition called "A language is called a regular language if some finite automaton recognizes it", could prove even(A) is regular? How to use closure properties to prove this question?


texts: LL(1) grammar for the untyped lambda-calculus

texts:
What I want to do

I am trying to define a LL(1) grammar of the lambda-calculus.

What I did

Here is the grammar:

$Term \to Abs$
$Term \to App$
$Abs \to \lambda \ id \ . \ Term$
$App \to Var \ AppSeq$
$AppSeq \to App$
$AppSeq \to \epsilon$
$Var \to id$
$Var \to (\ Term \ )$

Here are the FIRST sets:

$FIRST(Term) = \{ \lambda, id, ( \}$
$FIRST(Abs) = \{ \lambda \}$
$FIRST(App) = \{ id, ( \}$
$FIRST(AppSeq) = \{ id, (, \epsilon \}$
$FIRST(Var) = \{ id, ( \}$

Here are FOLLOW sets:

$FOLLOW(Term) = \{ \$, ) \}$
$FOLLOW(Abs) = \{ \$, ) \}$
$FOLLOW(App) = \{ \$, ) \}$
$FOLLOW(AppSeq) = \{ \$, ) \}$
$FOLLOW(Var) = \{ \$, (, id \}$

The dragon book give the following definition:

  A grammar G is LL(1) if and only if whenever A → α | β are two
  distinct productions of G, the following conditions hold:

  FIRST(α) and FIRST(β) are disjoint sets
  if ε is in FIRST(β), then FIRST(α)  and FOLLOW(A) are disjoint sets
  likewise if ε is in FIRST(α)

Question

Are my FIRST and FOLLOW sets correct?
If no, how can I make it LL(1)?


texts: Regular expression for words in a language where each letter appears at least once

texts:
What is a regular expression or finite automaton that will accept words in the alphabet $\{a,b,c \}$ where each letter appears at least once?

Acceptable words:  $ abc, cba, cbcbcba, abbbcaabb$

Unacceptable words: $aab, babababababa, bbbbbaaaaa$

I would be interested in seeing both the regex and the automaton. Then I can place it into regexper.com

In Regular expression to show that all strings contain each symbol atleast once we find the regex

$$ (a+b+c)^*a(a+b+c)^*b(a+b+c)^*c $$

The word $cba$ does not fit, and the answer raises questions about the complexity or size.
For kicks, I draw the automaton [1].

COMMENT It's not clear to me at all this is a duplicate to the linked question.  They talk in general about deciding if

$$ \qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \} $$

is a regular language.  None of the answers address my specific case in question.  Looking at notes, my guess the alphabet is $\Sigma = \{ a,b,c\}$ and $\Sigma^\ast$ is the free monoid.  It's unclear to me what choice of $L$ returns the $L'$ I am looking for.

Or if anyone can show me how this is an intersection, complement or other regular language operation please let me know.


texts: Anyone know how to peg the price of an ERC 20 token to the value of gold? What needs to be done in the coding of the smart contract? Is there a step by step tutorial somewhere?


texts: Can we use a different encoding scheme to solve an unsolvable language?

texts:
Say we have a particular decision problem and that we have an alphabet and an encoding scheme, which gives us a language L that we say is not recursive (i.e. we do not have a Turing Machine that can decide (YES or NO) the problem).

Is it possible to use a different encoding scheme to make the problem solvable?

I have thought about suggesting that we can reduce all such problems to the halting problem, which would imply that no new encoding will allow us to make one solvable (since this would contradict the unsolvability of the halting problem).


texts:
Let be $F=(A\land B)$ and $G=\neg(\neg A \lor \neg B)$. Which of the following statements are correct

$F=G, F\equiv G, \neg F=\neg G, \neg F\equiv\neg G$?

Is there a difference?


texts: Relevance of the ZeroSum game to Heuristic search?

texts:
A question was posed to me as to the relevance of the ZeroSum game to Heuristic search algorithms.

I know that the zero sun game is a theory in which one persons gain is exactly balanced to another persons loss but I am unsure as to how this applies to Heuristics.

I think it may have something to do with how parts of the problem space are removed and as a result, the problem space is optimised?

Thank you.


texts:
I'm working on some kind of multiplayer game and for the best experience for the users I want to make sure the rooms are somewhat balanced at all time. By balancing I just mean the amount of users in the room (not score based or anything). I already figured out what the size of rooms should be and how many users there should be per room (based on a fixed maximum number of users per room). For a maximum of 4 users per room I came to the following distributions:

(total users) | (array of rooms (number is amount of users in room))
----------------------------------------------------------------------
4:              [4]
5:              [3, 2]
7:              [4, 3]
9:              [3, 3, 3]
13:             [4, 3, 3, 3]
...

I use the following code/algorithm to determine the distribution:

function calculateRoomDistribution(numUsers, maxUsersPerRoom) {
  const numRooms = Math.ceil(numUsers / maxUsersPerRoom)
  let distribution = []
  for (let i = 0; i < numRooms; i++) {
    distribution[i] = 0
  }
  for (let i = 0; i < numUsers; i++) {
    distribution[i % numRooms]++
  }
  return distribution
}

What I couldn't figure out however, is how to transition from one state to another. Let's say I have 13 users, divided over 5 rooms, respectively 4, 2, 2, 3, 2 users... I want to redistribute them into 4 rooms, with 4, 3, 3, 3 users. How would I approach such a problem? I was thinking of first removing the rooms that already have the right amount of users (4 and 3). That would leave me with [2, 2, 2]. But I noticed I would have to write a lot of edges and exceptions and I have a feeling there must be a smarter way. What type of algorithm am I looking for?


texts: Concrete and simple applications for bipartite graphs

texts: I am looking for concrete and simple problems that may be solved using bipartite graphs or bipartite graph properties. Any idea along with explanations are welcome.


texts:
I'm playing a game where I'm trying to estimate an unknown real number $x$.

An oracle exists that will answer the question of "Is a number $y$ greater than or equal to $x$?", to which the oracle will reply either yes or no. The question may be asked an $t$ number of times.

For example, with an unknown $x=9.5$, the oracle will reply yes to $15$ and no to $9$.

What's the best approach to estimate $x$? It's okay to assume my first guess $y_1$ will always be answered with yes (so I always have some "best" guess available), but now I'm tasked with getting even closer to $x$ with my second guess $y_2$, third guess $y_3$, ..., and last guess $y_t$.

I'm not necessarily looking for a solution to this problem, but at least the established name for it so I may do some research. Concepts like optimization, numerical analysis, and machine learning come to mind, but they are large, deep fields, and I'm not quite sure where to turn.

My use case for this algorithm is to discover the optimal frequency to send requests to a service which is frequency-capped by an unknown amount. When I send too fast, I get error responses (oracle says no), and when I'm below the cap, I get success responses (oracle says yes). To keep things focused on the important concept, assume the network has no delay.


texts: NP-COMPLETE:Why say "reduction algorithm computes reduction function"?

texts:
In Chap 34.3 NP-completeness and reducibility of the  book, Introduction to Algorithm(3rd Edition), the author states(the original text):

We call the function f the reduction function, and a polynomial-time algorithm F that computes f is a reduction algorithm.

In my mind, function should be a machine dependent implementation(a set of instructions) of the algorithm. Why does he say algorithm computes function?


texts: Is a device with restrictive execution policies Turing-complete?

texts:
There are devices that do not allow users to load any application they want on it, only run a limited class of applications approved by the device vendor.

Take an iPhone as an example where new applications are loaded (solely) from app-store and programs that would allow execution of arbitrary code by user (without permission of Apple) are not permitted (e.g. Flash).

Are such machines where users cannot execute arbitrary code on themselves still Turing-complete computers? Can they still be considered as universal Turing machines?


texts:
Good evening everyone!
Can someone help me with the following task?
So we have this NFA:

I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$
Unfortunately I don't understand how this is possible. If I look at the NFA, then we can accept a word that only includes one a without any b's. But the regular expression in the solution does not make that possible.  Or am I missing something?
I also converted the NFA to a DFA however that didn't help much.
Thanks!


texts:
I am reading the book by Arora and Barak, in which they try to prove there exists a langauge $U$ such that $P^{B} \neq U$.
I completely understood the proof except one problem in the end, they use crucially the fact that a Polynomial Turing Machine will halt within steps $\frac{2^{n}}{10}$ My doubt is it is not necessary, it may happen the constants in the polynomial are so high that for that particular $n$ it takes more than $2^n$ time. So how do you deal with that.It is not specified to take n large enough such that $2^n$ is greater than its running time.


texts: Convert a digraph to the corresponding undirected graph in linear time using adjacency lists

texts:
Suppose we have a directed graph $G = (V,E$) represented with adjacency lists.  Is it possible to convert $G$ into its undirected equivalent* $G'$, also represented with adjacency lists, in $O(|V|+|E|)$ time?

The obvious algorithm walks the adjacency list of each vertex $v$, and for each adjacent vertex $u$, inserts edges $(v,u)$ and $(u,v)$ into $G'$.  The issue is duplicates.  If $(u,v)$ happens to be in $G$ already, $(u,v)$ will be inserted into $G'$ twice: once when processing $v$'s adjacency list, and once when processing $u$'s.  Assuming that a well-formed graph doesn't contain any duplicate edges, we would need to check $u$'s adjacency list to see whether it contains $v$ before performing the second insertion.  But this check takes linear time in $|V|$, and we would need to perform this check for $O(|E|)$ edges, resulting in $O(|V|*|E|)$ time complexity.

*Terminology:  by "undirected equivalent" of a digraph $G=(V,E)$, I mean the directed graph $G'=(V,E')$ such that

if $(v,u) \in E$ then $(v,u) \in E'$ and $(u,v) \in E'$ and
if $(v,u) \in E'$ then either $(v,u) \in E$ or $(u,v) \in E$.


texts: Why isn't converting from an NFA to a DFA working?

texts:
I am just beginning to learn computation theory. I wrote up a non-deterministic finite automata that accepts strings that contain the substring "abba":

I tried to convert it to a DFA by putting together sets of states in the NFA to be states of the DFA:

However, I just realized that my DFA doesn't accept strings such as "abbaa" that do not end in "abba." That means that my methodology was wrong. Why? I thought it would make sense to combine states of the NFA to make states of the DFA.


texts: Minimum space needed to sort a stream of integers

texts:
This question has gotten a lot of attention on SO:
Sorting 1 million 8-digit numbers in 1MB of RAM

The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\mathord{,}999\mathord{,}999]$) using only 1 MB of memory ($2^{20}$ bytes = $2^{23}$ bits) and no external storage. The program must read values from an input stream and write the sorted result to an output stream.

Obviously the entire input can't fit into memory, but clearly the result can be represented in under 1 MB since $2^{23} \geq \log_2 \binom{10^8}{10^6} \approx 8079302$ (it's a tight fit).

So, what is the minimum amount of space needed to sort n integers with duplicates in this streaming manner, and is there an algorithm to accomplish the specified task?


texts: How would i go about calculating the Big Theta of the following nested loop?

texts:
for i = 0 ... log(n) - 1
    for j = 2^i + 1 ... 2^(i + 1)
         [code with Big-Theta(1) running time]

Given this piece of code the outer loop runs log(n) times. But I'm confused as to how to try to calculate the running time of the second loop so as to multiply them. Thank you for reading.


texts: Scoring metric for machine learning method

texts:
For a machine learning method X (Deep Neural Nets variant), which performs classification tasks.

In the output layer, for every label method, X also emits the uncertainty U associated with the respective prediction.

So, in case the testing dataset is very different then the predictions made by X should have a high U. (Mean of U across all labels should be high)

In the case of testing, the dataset is indeed from the same source from which training dataset was generated. For true positives, the mean of uncertainty for the correct label would be low. In the case of false positives, the mean of U would be high (ideally).

What is the principled approach to measuring the effectiveness of method X in outputting the uncertainty? In other words, what would be a good metric to understand the performance of the method in computing the uncertainty for each label?

Metric similar to Root mean squared error or others.


texts: How to make Turing machine deterministic?

texts:
My Turing machine starts with an empty tape. It writes a random word of the set $0^n1^n$ to the tape. Hopefully i made no mistakes.

My question is about the productions coming out of state $q_0$:

$δ(q_0, blank)=(0,R)$ and $δ(q_0,blank)=(blank,L)$. (see image below).

Their purpose is to generate a random amount of $0$ before going to state $q_1$. They are nondeterministic. Is there a workaround to make them deterministic?

I heard that every Turing machine can be made deterministic. But this case is a little bit strange, because instead of testing if a word on the tape is element of a set, it writes a random word of the set to the tape.


texts: What is the significance of context-sensitive (Type 1) languages?

texts: Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a push-down automaton) and Type 0 by a state machine with two stacks (or, equivalently, a tape, as is the case for Turing Machines), how do Type 1 languages fit into this picture? And what advantages does it bring to determine that a language is not only Type 0 but Type 1?


texts: What are the graph classes which takes logarithmic space in $|V|$ in circuit representation?

texts:
The $\text{SCR}$ representation of a graph $G=(V,E)$ is $C_{G}$ id the following conditions hold:

$C_{G}$ is a combinatorial circuit with memory.
$C_{G}$ has two inputs of length $n$ bits.
$C_{G}$ has $r$ gates, where $r = \mathcal{O}(n^{k})$ for some integer $k$. link
The output of $C_{G}$ is
$$C_{G}(i',j') = 0, \text{if } (v_i,v_j) \in E$$
$$C_{G}(i',j') = 1, \text{if } (v_i,v_j) \notin E$$
$$C_{G}(i',j') = ?, \text{if } (v_i \in V) \text{ or } (v_j \notin V) $$

The binary representation of $i$ is $i'$. For certain graphs there is a representation in $\text{SCR}$ that takes logarithmic space in $|V|$.

Question :  What are the graph classes(bounded degree, planar etc) which takes logarithmic space representation in $\text{SCR}$ model?


texts: What is wrong with this seeming contradiction with a paper about AND-compression of SAT?

texts:
Got a simple construction seemingly contradicting a paper assuming plausible conjecture.

Since it is unlikely the conjecture to be false, what  is wrong with the argument?

From a paper

  An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances $x_1,\dots,x_t$ to a single SAT-instance $y$ of size $\text{poly}(\max_i |x_i|)$ such that $y$ is satisfiable if and only if all $x_i$ are satisfiable. ... Unless the unlikely complexity-theoretic
  collapse $\sf coNP \subseteq NP/poly$ occurs, there is no AND-compression for SAT.

Construction:

If $x_i$ are not in CNF, convert them to CNF possibly
adding new variables. This is polynomial.

In CNF one can encode AND gate $ C := A \land B $
and OR gate $ C := A \lor B $.

The AND and OR gates have the property that for all satisfying
assignments of their CNFs we have $C \iff (A \land B)$
and $C \iff (A \lor B)$.

Let the $j$-th clause in $x_i$ be $x_{i,j} = [y_1, \ldots, y_k]$
for literals $y_m$.

Using the OR gate and new variables, compute variable
$O_{i,j} := y_1 \lor y_2 \cdots \lor y_k$.

For all clauses in $x_i$ ($O_{i,j}$) and the AND gate compute variable
$V_i := O_{i,1} \land O_{i,2} \land \cdots \land O_{i,m}$.

By construction $x_i \iff V_i$.

For all $V_i$, using the AND gate compute $F := V_1 \land \cdots \land V_t$.

$F \iff x_1 \land \cdots \land x_t$.

So the final formula $y$ is the union of the CNFs for $O_{i,j}$,$V_i$,$F$,
and a unit clause $[F]$.

$|y|$ is linear in the number of all literals, $t$ is polynomial
in $\max |x_i|$, which makes $|y|$ polynomial in $\max |x_i|$.

This appears to contradict the claim in the paper,
unless the certain collapse happens.

  What is wrong with this argument that appears to contradict the claim in the paper?

Similar construction works for OR-compression, when
at least one $x_i$ must be satisfiable.

The newly introduced variable are uniquely determined
by the original variables.

OR gate in  CNF 3 := 1 \/ 2 : [[1 2 -3],[-1 3],[-2 3]]
AND gate in CNF 3 := 1 /\ 2 : [[-1 -2 3],[1 -3],[2 -3]]


texts: What will be the Turing machine to show that the function $T(n) = n$ is time constructible?

texts: Specifically, we need a Turing machine that on input $1^n$ outputs binary representation of $n$ on output tape in $O(n)$ time. I am not able to get any thing better than trivial $O(n \log n)$ time. Any hints or solution?


texts:
In computer science papers, I see about the term 'fooling' a function.

What does it mean to fool a function against a particular complexity class? Why is it important?


texts: Prove that **PTIME** has no complete problems with respect to linear-time reductions

texts:
Prove that PTIME has no complete problems with respect to
  linear-time reductions.

I know that PTIME means all these problems that we can solve them in polynomial time. I suppose that I should use here time hierarchy theorem - I know it.

However, I have no idea how to solve it. I am beginner at this subject so I ask for explanation for dummy :)