texts:
Wiki says
a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input – the number of bits required to represent it.

This answer very well explains why primality test algorithm of running time $O(n)$ is actually pseudo-polynomial time. Simply put A very simple way of thinking about it is that if you double the limit, the size of the input only increases by one bit (since the limit is part of the input), while the run time is doubled. That is clearly exponential behavior with respect to the input size.

That is, add one extra bit in the bit representation of your input and the running time will increase exponentially.

Okaaay, My doubt is, isn't it applicable to every algorithm then? Like in sorting. One might say "The main difference is that, in pseudo-polynomial time algorithms, n represents a number in the input, while in other algorithms (sorting) n represents the number of things"

To which I think, how does that matter? Searching maximum in an unsorted array of size $n$ takes $O(n)$ time, add one extra bit to $n$ and the running time will grow exponentially. Hence Shouldn't every algorithm run in pseudo-polynomial time?


texts: Design a greedy algorithm by intermingling two sequences

texts:
I find myself solving problems for a test and the next problem I still can't solve it.
There are n ordered sequences, $S_1$ to $S_n$. It is requested to  intermingling them to obtain a single sequence, but doing the minimum possible work. The sequences are interspersed by two, the interleaving sequences $A$ and $B$ a long sequence is obtained $| A | + | B |$ , and the work done is proportional to the length of the resulting sequence.

1 - Create an algorithm to perform this task, choosing pairs of sequences to be inserted in each step.

2 - What is the total cost of your algorithm, in terms of the lengths of the original sequences?

3 - Show that your algorithm delivers an optimal sequence.

I would really appreciate your help. Thanks in advance.


texts: Procedure for finding if Overflow occurs on addition

texts:
I have two 4-bit 2's complement numbers a,b, and their sum in s (Also a 4-bit 2's complement number). Using only the basic logical operations, I need to write a procedure to find if an overflow occurs. If there is an overflow, the output needs to be 1000 otherwise it is 0000.

The inputs in this procedure are a, b, s, and output is 1000 or 0000 depending on the inputs. I am allowed to use AND, OR and NOT operators

I know that there is an overflow if a and b have the same most significant bit and c has a different most significant bit but can't seem to figure out what the expression should be except that whatever the result is, needs to be ANDed with 1000 for the final result. How do I solve this?


texts:
I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same:

Maximize the value of

($\sum_{i=1}^n v_i \cdot x_i) + B \cdot \frac{W}{r}$

subject to

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

Here, $W$ and $B$ are constants, and $r$ is an integer variable with $1 \leq r \leq n$, whose behavior vis-à-vis the variables $v_i$ and $w_i$ is unknown to me.

It is obvious that if $B$ is 0, this reduces to the classical knapsack and is hence NP-complete, but is it still NP-complete otherwise?  Can we say anything about this problem considering possible behaviors of $r$?

It's been a while since I studied algorithms; please bear with me if this looks too simple (let me clarify that this question arose from research; I'm not a kid trying to cheat on homework).  I have also not found an answer in the responses to other knapsack questions asked on this forum.


texts: Solving SAT correctly on all but $poly(m)$ formulas

texts:
The question is to show that there is no deterministic polynomial time algorithm that solves SAT correctly on all but $poly(m)$ formulas of size $m$, for every $m \geq 0$ unless $P \ne NP$.

I know that if $P = NP$,  a polynomial time algorithm exists that, given a Boolean formula φ, actually produces a satisfying assignment for φ if it is satisfiable. But I can't really understand how a poly time algorithm can solve SAT correctly on only $poly(m)$ formulas, if $P \neq NP$. Am I missing something in understanding the problem or there is a catch?


texts: How many strings of length |w| are unrelated?

texts:
For sufficiently large |w|, how many of the 2^|w| strings of length |w| are entirely unrelated?
A way to define this: two strings are unrelated if their joint Kolomogorov complexity is practically equal to their individual Kolmogorov complexities added together: K(w1,w2)=K(w1)+K(w2)


texts: Why is 2^32 in a 32-bit system = 4GiB and not 4Gib?

texts: I was watching this video 32-Bit vs 64-Bit - The Advantage and at 1:19 (timestamp) the narrator mentioned the 4GB memory allocation for the 32-bit system. I later found out it should've been 4GiB but am still confused about the bit vs byte part. After all, it's a 32-"bit" and not 32-"byte" system.


texts: Calculating time complexity of a code which may be incorrect

texts:
I am a sophomore taking a course in algorithm analysis. We were asked by our professor to calculate time-complexity of several C functions, but some of them were incorrect and would result in a compile error. As far as I know time complexities of correct algorithms are calculated and then we choose which one to implement. We tried to discuss this with her but she insisted on solving those problems nevertheless stating that it doesn't matter whether the code gets executed or not.

Is there a way one can realise that the algorithm is incorrect after finding it's time complexity?

Does it make sense calculating time complexity for an incorrect program?

PS :

1) The program wasn't implementing any proven algorithms, it was just some loops.

2) This may sound like a silly question, but my professor got me confused.

Downvotes are welcome but please give your opinion.


texts: Different feature sets for training and testing?

texts:
Is it common to have a different feature set for samples in the train set and in the test set?

My use case is text categorization: when training, I use the words as the features. But when testing, I want to add hypernyms.

For example, if the training set contained the sentence "I eat a fruit", and there is a test sentence "I eat an apple", then I want to have the word "fruit" as a feature of the test sentence, in addition to its words, so that it will be classified positive. However, I don't want to add those hypernyms in the training set - if the training set contained only "I eat an apple", I don't want the sentence "I eat a fruit" to be classified positive.

So, I thought of having a small feature set for training, and a larger feature set for testing.

Is this common? If so, I would be happy to have some references.


texts: What classes of data structures can be made persistent?

texts:
Persistent data structures are immutable data structures. Operations on them return a new "copy" of the data structure, but altered by the operation; the old data structure remains unchanged though. Efficiency is generally accomplished by sharing some of the underlying data, and avoiding full copying of the data structure.
Questions:

Are there results about classes of data structures that can be made to be persistent (while keeping the same or very similar complexities)?

Can all data structures be made persistent (while keeping the same or very similar complexities)?

Are any data structures known to be unable to be made persistent (while keeping the same or very similar complexities)?


texts: How does an enumerator for machines for languages work?

texts:
In Dexter C. Kozen - Theory of Computation (2006, Springer) page 319 exercise 127 he says :

"A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices representing all and only functions in the set. For example, the complexity class P is r.e., because we can represent it by an r.e. list of TMs with polynomial-time clocks."

How exactly do you do what he is talking about for any r.e. collection of functions/languages (or complexity class like P)--enumerate the machines that solve the languages in the collection? Normally, when speaking about an enumerator, you talk about enumerating the words of a language, not a collection of languages.


texts:
How can a 4-bit two's complement operation be implemented using only boolean logic gates (AND, OR, NOR, NOT, NAND, XOR, and XNOR)?

(This question was redirected to CS from Stack Overflow)


texts:
I've been trying for hours. I'm teaching myself automata theory right now and I have this DFA:

And I'm trying to create a regex from it by removing q1 first and then q2. I already managed to remove q1 by doing it like this:

But now I'm not sure how to continue. The next step I'm trying to do is remove q2 and then read the regex from it. Even after trying to wrap my head around it for a long time I didn't really get it. Hopefully someone here can help me :)


texts: Undecidable Problem for Regular Languages

texts:
It might seems weird, but, Are there any undecidable problems concerning regular languages? I mean questions concerning the regular languages, not the problems like "Is the language of a TM regular?".

Clarification: By the questions regarding regular languages, I mean that the problem consists of regular languages, i.e. the relation between two or more regular languages, and/or about the properties of a regular language.

Thanks in advance


texts:
I am looking for an example of the "iterative lengthening search". I have searched and I was only able to find definitions like

  iterative lengthening search an iterative analog to uniform cost
  search. The idea is to use increasing limits on path cost. If a node
  is generated whose path cost exceeds the current limit, it is
  immediately discarded. For each new iteration, the limit is set to the
  lowest path cost of any node discarded in the previous iteration

I'd be deeply grateful for an example, that enables me to understand.


texts: Languages with infinitely many but finite Myhill-Nerode equivalence classes

texts:
I'm kind of new to automata theory and I'm dealing with the equivalence classes used for example in the Myhill-Nerode theorem right now; in other words aba* / a = ba*; aba* / b = ⌀, and such.

In an exercise I'm asked to find a language defined by an infinite set of equivalence classes, but where each class is actually finite. Unfortunately this seems a bit counterintuitive to me, and I can only manage to find languages with an infinite set of equivalence classes where the classes are infinite.

If someone could help me out with the reasoning, and what I'm missing here, I'd really appreciate it.


texts: Parsing family of grammars, determine if LR(k)

texts:
Consider the family of grammars $G_n,~n\geq2$.
$$S \rightarrow A_ib_i~,~for~~1\leq i \leq n$$
$$A_i \rightarrow a_jA_i~|~a_j~,~for~~1 \leq i,j \leq n~~and~~i \neq j$$

where multiple alternative right sides result from different values of $i,j$
while the terminal symbols $a_i$ and $b_i$ are not necessarily different from each other.

Show that $G_n$ has exactly $n*2^{n-1}+n^2+1$ sets of LR(0) items.
Examine if $G_n$ is LR(k) for some k.

The above exercise is similar to Exercise 4.6.7 (page 258) from the "Compilers: Principles, Techniques & Tools", 2nd Edition (a.k.a.Dragonbook) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman.

I gave it much thought and also read chapter 4 of the book that is about Syntax Analysis but I still can't figure out how to prove this. Especially for question 2. I have no clue how to draw a conclusion about if this family of grammars can be parsed by an LR(k) parser.

For part 1., I think it could be suitable to use induction to prove that this is the exact number of states for any $n \geq 2$. At first, you have to construct the LR(0) states for $G_2,~n = 2$ and prove that the states correspond to the formula we have to prove. And it happens that way, as there are 9 LR(0) states which means that $\Rightarrow n*2^{n-1}+n^2+1=2*2^{2-1}+2^2+1=4+4+1=9$. If it is helpful, I could post the state diagram for $n=2$.
Also, I don't know if this would help, but I proved that the productions for any $n$ is exactly $2n^2-n$.


texts: How to efficiently use an AVL tree to store partial sums?

texts:
Let $a_{1} , ... , a_{m} $ be real numbers $\geq 1$, where $m$ is at least 1. I am supposed to store them in an augmented AVL structure with the following operations:

-PartialSum (i): Return the $i_{th}$ partial sum.

-Change (i, y): Change the $a_{i}$ element for y.

I need this structure to retain the AVL properties and both of these functions to be in $O(logn)$. The problem is that my approach doesn't let me have that asymptotic bound on CHANGE.

My approach goes like this: Let i be the key, and also store the relative $i_{th}$ partial sum in each node, the value for a as well.

Thus each of my nodes has:

Key = The $i_{th}$ element of the series input.
Sum = The $i_{th}$ partial sum so far.
Val = The value of $a_{i}$ for this node.

By doing that, the operation PartialSum will be identical to Search, thus being in $O(logn)$.

Unfortunately my approach doesn't work so well with change. By storing the partial sums in every node, if a lower node changes, all of the tree's sums are to be recomputed, being in $O(n)$.

I am trying to take a different approach but I'm confused. Can someone HINT me here?


texts: How can you convert the depth of a boolean circuit to its size?

texts:
I know that the depth of a circuit is the maximal length from an input gate to the output gate of the circuit and its size is its number of gates.
Is there a formula that you can go from depth to size and can someone explain the steps?


texts: Which of the following is a more appropriate complexity for this reccursive function?

texts:
Given the following recurrence relation:
\begin{gather*}
h(A) =
\begin{cases}
  0,\qquad \qquad \text{ }\text{ }\text{ }A=0\\
  1+h(A-1),\text{ }\text{ }A\text{ is odd} \\
  1+h(\frac{A}{2}),\qquad \text{otherwise}
\end{cases}
\end{gather*}
which of the following choices best describes its complexity?
A) $h(A)\in\theta(\log_2A)$
B) $h(A)\in\Omega(\log_2A),\text{ }h(A)\in\mathcal{O}(A)$
The book that I'm reading has selected choice $A$, however I feel like $B$ should be the answer. We know that the complexity is at minimum $\log_2A$ (best case when it's a power of $2$), but it could be higher than that and have a few more steps depending on what $A$ is. What am I missing here?


texts: Why values can not be replaced with their extensionally equal values in an intensional system?

texts:
Thomas Streicher states in Investigations into Intensional Type Theory(§Introduction p.5) that:

  Although in Intensional constructive set theory (Intensional Type Theory) one can do most of the things one wants to do... certain theorems simply do not hold due to the lack of extensionality. A typical example is that from $t\in B a$ and $p\in Id A ab$ one is not allowed t conclude that $t\in Bb$ where $A$ is a type and $B$ is a family of types indexed over $A$.(But of course one is allowed to infer $t\in Bb$ from $t\in Ba$ and $a=b\in A$ !)

An almost similar thin is mentioned in Definition of extensional and propositional equality in Martin-Lof extensional type theory
:

  The (Id-DefEq) means that extensional equality is baked into the type system: if you have a type constructor :((:)→)→ then you can use a value of type   in a context expecting   if  and  map equal inputs to equal outputs. Again this is not true in an intensional system, where   and  might be incompatible if they're syntactically different.

Why is that? Isn't it that two functions that are producing exactly same output for their inputs, equal? So why can't one be replaced with another in a context? What makes definitionally equal functions eligible to be replaced with each other, but not the extensionally equal ones?


texts: Proof of completeness for CFG having twice as many zeroes as ones

texts:
One possible CFG containing twice as many zeros as ones can be,

S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ

(This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other possible CFGs can be S→ϵ|1S00S|00S1S|0S1S0|S00S1 or S→ϵ|1S00S|00S1S|0S1S0|01S0S which some might say is better because of less redundancy)

Now I want to prove that this grammar is correct. It involves two steps

1) Prove that all the strings generated by this CFG contain twice as many zeroes as ones.(Consistency)

2) All the strings containing twice as many zeroes as ones are generated by this grammar.(Completeness)

It is trivial to see that all the strings that this grammar generates, contains twice as many zeroes as ones.

The difficulty is in the second part. How to prove that this grammar generates all the strings containing twice as many zeroes as ones?

My solution: One way to do is to make cases.

Let's say $L$ be the language containing all the strings having twice as many zeroes as ones. If a string $s\in L $, that means

$f(s) = n_{0}(s) - 2*n_{1}(s) = 0$

Now let's say we are at origin on x-axis and we move 1 step step right if we encounter 0 and move two step left if we encounter 1. In the end we should end at origin because $f(s)=0$. Now taking cases like when we remain only right side of the origin, when we remain left side of the origin, when we cross the origin in between of the string we can prove that our grammar generate the string.
(I am not going into detail as my problem is not related to this approach to the solution).

But I want to do it in more general way, without taking cases. Because I think that the general method in which we can prove it can be useful to prove the general question of grammar having 0s and 1s in ratio a:b, where a and b are any constants.


texts:
I know that in order to build i's failure link, I compare i's and j's success links:
If they are the same (if a = b), then i's failure link should point to state j + 1.
If they aren't the same, we go to the state pointed by j's failure link and do the same. (we stop when we fail at the initial state)
How do you compute the last state's "failure" link? For example if the pattern is "ABA":

How do we compute that after we found a match, we should go to state 1? State 3 doesn't have a character it's expecting to see, so how do we do it?


texts: I've implemented a program for computing eigenvectors of some random, symmetric, $N$x$N$ matrix using the power method.  I have found difficulty in calculating all $N$ eigenvectors consistently, almost every time the algorithm fails to converge for all $N$.  The Wikipedia page on the power method tells me this algorithm is not guaranteed to converge for all $N$ eigenvectors, can someone suggest a way for me to encourage convergence, at least in a majority of the cases?  Is this possible?  If not, can someone suggest a better algorithm for computing eigenvectors?


texts: Reducing amount of possible states solving Pacman by searching

texts:
I consider simplified Pacman game:

movement is discrete (on the grid),
ghosts move deterministically based on difference between their and Pacmans coordinates,
ghosts move every second turn,
ghosts always chase Pacman, never reversed,
the maze has no exit, success is when Pacman collects all the dots.

The most natural representation of the states space is a bit big as it consists of:

Pacmans position,
ghosts positions,
boolean if ghosts have moved in previous turn,
remaining dots positions.

Hence I want to reduce it significantly, but I have no idea how to do it.


texts:
I have been trying to find a solution both theoretical and practical to my problem but I just can't. The question is you have x players that should play some rounds y of games in groups of 4. Now if a player was in a game with somebody else, he is not allowed to be ever again with that player in the same group. Now the question is give n groups that satisfy this conditions. With n being maximal amount of possible groups.

My first approach was to just take a player put him into a group, now for the next player check the array already_played_with_players of the first player for the second player if he's not in add him and add the players he played with to the already_played_with_players array. Proceed so too for the next two players. Then mark these 4 players as in a group and take the next player out of the pool and so on.

This is not some educational question, but a real world problem. I would like to organize a game tournament, but so that people meet new people and don't play with the same people again. I already ask multiple people mathematicians, physicians, computer scientist, but the solution was not really evident to anybody. So I was wondering if the problem is NP-complete? I know I would need to find a reduction from another NP-complete problem to my problem to prove that, but I don't even know how to formalize my problem exactly.


texts: Find an algorithm that finds a minimal hitting set for sets limited in size

texts:
Given a family of sets $F=\{S_1,...,S_m\}$, where $S_i{\subseteq}\{1..n\}$, with the assumption that the maximum size of any set $S_i$ is at most $k$ ($|S_i|{\leq}k\ {\forall}i\in\{i..n\}$).

I'm tasked with finding a hitting set $H$, a set that contains at least one member from each set $S_i$ ($H{\cap}S_i\ne\emptyset\ {\forall}i\in\{1..n\}$). And to prove that the algorithm gives produces a set that is at most k times larger than the minimal hitting set.

What algorithm does it and how do I prove that it does it.

I've tried the greedy algorithm (take the number that covers the most sets, remove those sets, repeat).

I've also tried making the problem into a two sided graph where one side is the numbers, the other side are the sets and edges connect sets with their members, and applying a minimum cover set algorithm.

For both instances I couldn't show that the hitting set it gives is at most a set k times larger than the minimum.


texts: Find the error in the following “proof” that $O(n) = O(n^2)$

texts:
Let $f(n) = n^2 , g(n) = n$, and $h(n) = g(n)−f(n)$. It is clear that $h(n) ≤ g(n) ≤ f(n)$ for all $n ≥ 0$. Therefore, $f (n) = \max(f (n), h(n))$. Thus,
$O(n) = O(g(n)) = O(f(n) + h(n)) = O(\max(f(n), h(n))) = O(f(n)) = O(n^2)$.

Can you explain why this statement is wrong?


texts:
I've been trying to internalize some of the basic sorting algorithms recently, and to do so I've been looking at their wikipedia pages to refresh myself with how they work, and then coding my own "version" of the algorithm from there.

I did this with MergeSort recently, and I got an algorithm that for what I can tell works but I'm not sure it runs in O(nlogn) time like MergeSort does.  Here's my code, it's in Python:

def mergeSortAlgorithm(x):

    listOfLists = []

    for i in range(len(x)):
        temp = [x[i]]
        listOfLists.append(temp)                          #I first put every item in the array into
                                                      #its own list, within a larger list -> divide step

                                                      #so long as there is more than one sorted list, then we need to keep merging
    while(len(listOfLists) != 1):
        j = 0

                                                      #for every pair of lists in the list of lists, we need to merge them
        while(j < len(listOfLists)-1):
            tempList = merge(listOfLists[j], listOfLists[j+1])
            listOfLists[j] = tempList
            del listOfLists[j+1]                          #I shift the new list to index j, and delete the second list from the now-merged pair at index j+1
            j = j+1                                       #increment the value of j, basically a counter
        print(listOfLists)

    print(listOfLists[0], "is sorted!")

def merge(a, b):                                          #function to merge two lists in order
    newList = []
    count1, count2 = 0, 0

                                                      #basically, walk through each list, adding whichever element is smallest
    while((count1 < len(a)) and (count2 < len(b))):

        if(a[count1] > b[count2]):
            newList.append(b[count2])
            count2 = count2 + 1                           #update the counter along b

        elif(a[count1] < b[count2]):
            newList.append(a[count1])
            count1 = count1 + 1                           #update the counter along a

        elif(a[count1] == b[count2]):                     #if they're equal, add the value from a first
            newList.append(a[count1])
            newList.append(b[count2])
            count1, count2 = count1 + 1, count2 + 1       #update the counter on each

    if(count1 < len(a)):                                  #if the while loop exited with left-over values in a, add them
        for f in range(count1, len(a)):
            newList.append(a[f])
    elif(count2 < len(b)):                                #do the same for b - the values are already in order so you're good
        for k in range(count2, len(b)):
            newList.append(b[k])

    return newList

The algorithm correctly sorts what I give it, but I'm thinking that the runtime is more like $O(\log n\cdot \log n\cdot n)$ because the outer while loop in mergeSortAlgorithm() will do $\log n$ passes, as will the inner while loop, and the merge() algorithm will take in total $n$ operations.

Is that right?  If so, in what respect does my algorithm differentiate from MergeSort?  (i.e. where am I going wrong?)

Thanks so much for your help, please let me know if you have further questions I can help explain.


texts: Neural Network Normalization and de-Normalisation of data

texts:
I am developing a simple backprop neural network with n inputs and 1 output. I am using a sigmoid activation function. [Aforge.Net]

I have read that it is good to normalise the input and output data prior to training, which I have done using a simple linear relation (max/min mapping) to normalise between [0, 1].

My question is, what happens when upon using the NN after training, I get inputs that are larger/smaller than the max/min of the training sets (used for normalisation)? Should I be storing new max/mins and using these to re-normalise my new inputs? or do I just normalise the data with the parameters used in the training set and simply give the network inputs that may be greater than 1 or less than 0?


texts: Inheritance, and dynamic access to members/attributes and methods in Java-like languages

texts:
I have a question about inheritance in Java-like OO programming languages. It came up
in my compiler class, when I explained how to compile methods and their invocation. I was using Java as example source language to compile.

Now consider this Java program.

class A {
  public int x = 0;
  void f () { System.out.println ( "A:f" ); } }

class B extends A {
  public int x = 1;
  void f () { System.out.println ( "B:f" ); } }

public class Main {
  public static void main ( String [] args ) {
    A a = new A ();
    B b = new B ();
    A ab = new B ();

    a.f();
    b.f();
    ab.f();
    System.out.println ( a.x );
    System.out.println ( b.x );
    System.out.println ( ab.x ); } }

When you run it, you get the following result.

A:f
B:f
B:f
0
1
0

The interesting cases are those that happen with the object ab of
static type A, which is B dynamically. As ab.f() prints out

B:f

it follows that method invocations are not affected by the compile-time type of the object the method is invoked with.  But
System.out.println ( ab.x ) prints out 0, so member access is affected by compile-time types.

A student asked about this difference: should not the access of members and methods be
consistent with each other?
I could not come up with a better answer than "that's the semantics of Java".

Would you know a crisp conceptual reason why members and methods are
different in this sense? Something I could give my students?

Edit: Upon further investigation, this seems to be a Java idiosyncrasy: C++ and C# act differently, see e.g. Saeed Amiri's comment below.

Edit 2: I just tried out the corresponding Scala program:

class A {
  val x = 0;
  def f () : Unit = { System.out.println ( "A:f" ); } }

class B extends A {
  override val x = 1;
  override def f () : Unit = { System.out.println ( "B:f" ); } }

object Main {
  def main ( args : Array [ String ] ) = {
    var a : A = new A ();
    var b : B = new B ();
    var ab : A = new B ();
    a.f();
    b.f();
    ab.f();
    System.out.println ( "a.x = " + a.x );
    System.out.println ( "b.x = " + b.x );
    System.out.println ( "ab.x = " + ab.x ); } }

And to my surprise this results in

A:f
B:f
B:f
a.x = 0
b.x = 1
ab.x = 1

Note that the overrise modifiers are necessary. This surprises me because Scala compiles to the JVM, and moreover, when I compile and execute the Java program at the top using the Scala compiler/runtime, it behaves like the Java program.


texts: So I've been struggling for the past hour with $G=(\{S\},\{a,b\},P,S)$ with productions $S\to aaSb | abSbS | \varepsilon$. I need to prove whether this grammar is ambiguous or not. Thus far I think it is ambiguous, possibly cuz of abSbS, but not sure (mainly since I have no idea how to prove it's not) . Can anyone help? I tried several words to no avail.


texts: Graph search or shortest path algorithm for graph with multiple “goals”?

texts:
I did a project in a class using A* search to solve an 8-puzzle.
But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles.
I’m not sure whether something like A* search could still work or not. I have trouble fathoming how a heuristic might be designed.
Are their other shortest path algorithms or search algorithms that are better suited for this kind of problem?


texts: What's the difference between physically based rendering and global illumination?

texts: I know that Physically based rendering means we try to simulate how light actually works in real world and global illumination is bouncing back of light when it strikes a surface. But what's actual difference between them and how are they related?


texts:
Hopefully this is not a duplicate

How do I prove a Language L={a,b,c} is decidable or not

I read somewhere that if a turing machine accepts a language and halts on every input string then the language is decidable.

Having said that how do i design / prove that a turing machine accepts {a b c}

I am new to concepts of automata and compelexity so please don't kill me if this is too basic for a question


texts: Languages recognized by finite state automata of polynomially growing size

texts:
In the course of my research (condensed matter physics stuff), I stumbled over the following concept:

The class of regular languages can be defined via finite state machines (FSM):
A language $L$ is regular iff there is an FSM which accepts $L$.
Clearly every finite language is regular.

I am interested in the following (larger) class of languages (call it $\mathcal{L}^?$) over some finite alphabet $\Sigma$ with relaxed conditions:

  A language $L$ is in $\mathcal{L}^?$ $:\Leftrightarrow$

  There is a sequence of FSMs $(M_n)_{n\in\mathbb{N}}$ such that

  $w\in L\,\Leftrightarrow\,$ $M_{|w|}(w)$ accepts
  $|M_n|\leq \operatorname{Poly}(n)$

  Here $|w|$ denotes the length of word $w$ and $|M|$ is the size of the
  FSM $M$, i.e., its number of states.

Obviously all languages $L\subseteq \Sigma^\ast$ are included if one drops the second requirement, as the sublanguages $L_n\subseteq L$ of words with fixed length $n$ are finite. But for a generic language $L_n$ with fixed length words, the minimal accepting FSA has a size exponentially growing in $n$ (is this correct? I sketched just a naive counting argument...).

As I'm no computer scientist, I was wondering whether this concept is already known in automata theory / computability theory (and if so, how it is called). Due to my lack of expertise, I just do not know where to start.

I would be very happy if you could ...

either provide a pointer to the relevant topic of automata theory (terms I have to look for, relevant publications)
or give an alternative characterization of this class (maybe it's just equivalent to one of the well-known language classes?)

Thank you in advance!


texts: Is every linear-time algorithm a streaming algorithm?

texts:
Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear time algorithms. This is a bit bold as in general, a linear time algorithm can jump around at will (random access) which a streaming algorithm can not; it has to investigate the elements in order. I may perform multiple passes, but only constantly many (for linear runtime).

Therefore my question:

  Can every linear-time algorithm be expressed as a streaming algorithm with constantly many passes?

Random access seems to prevent a (simple) construction proving a positive answer, but I have not been able to come up with a counter example either.

Depending on the machine model, random access may not even be an issue, runtime-wise. I would be interested in answers for these models:

Turing machine, flat input
RAM, input as array
RAM, input as linked list


texts: Is all data stored in computers stored as machine code?

texts:
I know that the most basic (and least abstract) code for programming is machine code (with binary of 0s and 1s being the typical machine code).
I also know that computers can save data even if they are turned off, by different types of computer memory (storage device memory, RAM and other computer system devices which can "remember" some data).
Is all data stored in computers ("all data remembered in a given computer memory") stored as machine code?
Is what's saved in a computer's "memory" (and becoming actually effective by electrical current correctly distributed to the computer system) just binary machine code in the sense that if I could read and understand that data directly without an operating system interfacing it for me it should appear in my mind as machine code, or rather, is it something else?


texts:
What is the most effective way of finding median from $N$ numbers within given range ? It is guaranted that $N \leq 10^{9}$.

The input consists of $L$ lines.

Each line consists either of:

a)  S X , which means store number $X$, where $X \leq 10^{9}$.

or

b)F X Y,  which means find median from stored numbers within range $(X,Y)$. where $1 \leq X,Y \leq 10^{9}$

For each F X Y ( median range request ) it should print the median from all stored numbers within range $(X, Y)$

Example:

Suppose the input:

S 20
S 10
S 22
S 30
S 25
F 21 30
S 5
S 7
S 9
F 5 20

Output:

   Median from range (21, 30) : 25
   Median from range (5, 20) : 9

Explanation:

The first median request for range (21, 30) satisfie 3 numbers: 22 25 30 where the median is 25.

The second median request for range (5, 20) satisfie 5 numbers: 5, 7, 9, 10, 20 and we pick up the median which is 9.

The mean is not guaranted to be close to median. The requests for storing S do not have to go consecutevly.


texts: What's the vertex cover of the null graph?

texts: Let $N(G)$ be the null graph. What's the number of vertex cover for this graph? I wanted to modify the reduction from SAT to vertex cover by adding vertices that are not connect to any vertices.


texts: Using random projections for locally sensitive hashing

texts:
I recently came to see that this library sparselsh uses random projection to perform locally sensitive hashing of documents.

The proof is such that based on cosine similarity to the vector. In other words if the dot product of a random projection vector and a feature vector > 0, it would mean that the angle is obtuse and <0 if the angle is acute. However, i cannot seem to understand it.

Assuming v is a feature vector containing a bag of words, and the random projection vector being drawn from a normal distribution. I can safely say that v will never have negative elements since the bag of words vector can never have a negative value. In this case, How would there be a situation when r.v give an obtuse angle? Am i misunderstanding something?

I have referred to this question but to no avail. Locality-sensitive hashing random projection

Let me state my confusion clearer.

Consider a 2 dimensional vector space, Given that r.v < 0 if the angle between the two vectors are less than 90degrees and >0 when they are above 90 degrees. This would mean that the probability of the blue vector dot product with another data point giving a r.v > 0 is zero. This would mean that i can only draw vectors in the negative space?


texts: Sorting a list of strings in lexicographic order of sorted strings

texts:
Let $A$ be a collection of strings over the alphabet $\{0,\ldots,m-1\}$ that in total contain $n$ symbols.
Your task is to sort each of the strings internally, and then sort the resulting strings in lexicographic order. (Your algorithm doesn't have to operate this way.)
Example:
Input: 33123 15 1 0 54215 21 12
Output: 0 1 12 12 12333 12455 15

I found a way to do it in $O(m+n)$ time and $O(mn)$ space.
The space is larger than the time because I use a smart array that allows you to create an array with size $n$ and sort of giving initial values to all of the cells in $O(1)$.
I used bucket sort in order to sort each string ($O(m+n)$ time and space) and word trees in order to sort the collection $A$ itself ($O(m+n)$ time and $O(mn)$ space). but my solution is too complicated.
Does anyone have a better solution, with $O(m+n)$ time and less space, or faster than $O(m+n)$?
The solution must be deterministic so no hash maps or other statistical algorithms

My solution:
A smart array is an array of size $m$ which we can create and "initialize" in $O(1)$:
We create three arrays the size of $m$ without initializing any of them and we also keep a single integer variable called $C$.
The first array contains the data. The second array contains  pointers to a cell in the third array. The third array contains pointers to a cell in the second array. $C$ contains the number of cells initialed so far.
Suppose we would like to set the value of cell $i$ (suppose it is the first time we are doing it on this cell). Then we will go to cell $i$ in the first array and set it to the wanted val.
Now we go to cell $i$ in the second array and set it to point at cell $C$ at the third array. Set the  cell $C$ in the third array to point at cell $i$ in the second array. Increase $C$ by 1.
Suppose we would like to know if cell $j$ is trash (That means we have yet to set anything to it).
We would go to cell $j$ in the second array and look at the cell number (in the third array) that cell $j$ (in the second array) points to – we will call it $k$.
If $k>C$ then $j$ is trash (because we have only initialized $C$ cells so far and $j$ isn't one of them).
If $k<C$ we will look at what cell $k$ (in the third array) points to. If it is not $j$ then $j$ is trash. Otherwise $j$ isn't trash
That way we can know at each step if we initialized this cell and if not initialize it. So we have created and "initialized" an array of size $m$ in $O(1)$ time.
The main trick is not to initialize the entire array at the start but to find a way to know which cells we've initialized so far and initialize a cell only when we "look" at it. In the RAM model it takes $O(1)$ time to create an array of any size without initializing it.

A word tree of order m is a generalization of a TRIE. Each node contains an array of pointers to its sons. The array size is $m$.  Each node also contains a counter to say how many sets there are that are described by this node.
Because we are using smart arrays each time we add a word $A$ (a set) it only takes $O(|A|)$ time and $O(m|A|)$ space.


texts: Complexity of calculating independence number of a hypergraph

texts:
Let $G$ be a "hypergraph", a collection of vertices $V=\{v_1,v_2,\ldots,v_n\}$ and a collection of "hyperedges" $E=\{e_1,e_2,\ldots,e_m\}$, where $e_i\subseteq V$ and unlike normal edges, an edge may contain more than two vertices.

An "independent set" (http://en.wikipedia.org/wiki/Independent_set_(graph_theory)) is a collection of vertices, $U$, that does not fully contain any of the hyperedges:  $e_i\not\subseteq U$.  The "independence number" or "maximum independent set size" is the size of the largest independent set in the graph $G$.

I know that finding if there is an independent set of size $k\in\mathbb{N}$ in some normal graph $G$ is NP-Complete.  If I am not mistaken, this holds for hypergraphs as well.  However calculating the independence number is not proven to be NP.  Even approximating it is not proven in NP.

First, is there a more specific complexity class for calculating the independence number than NP-Hard?

Second, how much harder is it for a hypergraph?  Again, is there a complexity class more specific?

For related questions, a recent dissertation has been helpful to me: https://escholarship.org/uc/item/79t9b162.

Thanks!


texts:
There are some algorithm or solving a simple maze on the web; but what I am trying to solve is a bit more complicated.
Here is an example:

####################
#S #D #           #
#  # ##  ##  ###D###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #  D#  #   ###
# ### ### ## # #####
#   #     #       E#
####################

S represents the StartPoint; E represents the EndPoint. D(s) are the collecting point. I want to find the all the paths from S to E which go through D. Then I want to distinguish the shortest path.

Here is an example of A* algorithm, How can I assure that paths go through D points.

def aStar(self, graph, current, end):
    openList = []
    closedList = []
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList.append(current)
    while len(openList) is not 0:
        current = min(openList, key=lambda inst:inst.H)
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.append(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10
                if tile not in openList:
                    openList.append(tile)
                tile.parent = current
    return path

My question is that How i can modify above search algorithm so that it passes through all D points. I want all the paths included D points.


texts: Question about how can i determine if counting sort is the right option over other sorting algorithms

texts:
So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm.

Now i find that solutions for that question given by my professors are wrong because they do gave this as answer:( pseudocode)

Sorting(A,k) //where k is a value inserted by the user(?)
{
max=a[0];
for i=1 to n // n=dim
{
    if( a[i] > max) update max with a[i]
}
if( max <= k*n) then countingsort(A)

else heapsort(A);

return A;

Now that being said, if k is really a value inserted by the user, this makes that solution not really case sensitive or a proper valuation of counting sort time complexity. It seems to me that it isnt a general algorithm, which should be instead the purpose of that exercise i guess.
my solution is:

Sort(A){
    int max, i;
    int min;
    if( arr[0] > arr[1]){
        max=a[0];
        min=a[1];
    }

    for(i= 2 ; i < n ; i++){
        if(a[i] > max) max=arr[i];

        else if( a[i]< min) min=arr[i];
    }
    range= max-min; // range for counting sort
    if(range/n < log n) counting sort(A,range);

    else mergesort/heapsort(A......);

    return A;
    }

If (range/n) < logn , it means that range < nlogn, which implies it ""should"" be better than other optimal sorting algorithms.
It might be not the most accurate way but it seems like it should be something like that, shouldnt it?


texts: Which element is at its final position after the partitioning step in Quicksort?

texts:
In Algorithms, 4th Edition, I read that after the partitioning step one element is in its final position.

  The entry a[j] is in its final place in the array, for some j.

  No entry in a[lo] through a[j-1] is greater than a[j].

  No entry in a[j+1] through a[hi] is less than a[j].

And this comes from Algorithms, 4th Edition, as well:

  First, we arbitrarily choose a[lo] to be the partitioning item—the one
  that will go into its final position.

Does the pivot go into its final position for all inputs without exception?


texts: In a DAG, what is the name of the process replacing no branch path with a single vertex

texts:
In my work, I meet a process for DAG, and need to explain it in my report. So, I would like to know the name of the process.
The process is very simple. The vertices of degree two except roots and leaves are replaced to the new edge between the parent and child vertices.

This process is almost the same to what this library achieves.


texts: Covering radius of a code in the Hamming space

texts:
A deterministic $(2−2/(k+1))^n$ algorithm for $k$-SAT based on local search

　I have read this paper and I couldn't understand how to culculate the $covering$ $radius$ of a code in the Hamming space. It is defined as follows in the paper.

　We identify assignments with binary words. The set of these words of length $n$ is the $Hamming$ $space$ denoted by $H_n=\{0,1\}^n$. The $Hamming$ $distance$ between two assignments is the number of positions in which these two assignments differ. The $ball$ of radius $r$ around an assignment $a$ is the set of all assignments whose Hamming distance to $a$ is at most $r$.
　A $code$ of length $n$ is simply a subset of $H_n$. The $covering$ $radius$ $r$ of a code $C$ is defined by
$$r=\max_{u∈\{0,1\}^n}\min_{v∈C
}d(u,v),$$
where $d(u,v)$ denotes the Hamming distance between $u$ and $v$.

　The $\max$ of $\min$ is exactly the point I couldn't calculate. So I considered the instance of $C$ and tried to calculate its covering radius.
e.g.)$$C=\{000,010,011,100,101,110\}⊆H_3$$

　In this case, how can I calculate the covering radius $r$?


texts: Complete list of IEEE Software "Voice of Evidence" articles?

texts:
This month the IEEE Software magazine has published the article Voice of Evidence: A Look Back. This is a kind of impact analysis of the Voice of Evidence (VoE) series of articles.

As you know, these articles are meta-analysis about software engineering practices and they give invaluable information about which things likely work and which things do not likely work.

I wonder if anyone knows how to get the complete list of VoE references (with or without paywall).


texts: How to compare SURF points in two images

texts:
I know how to find SURF feature points and have code to find them, but I have no idea how to find the same point in 2 different images, I have
laplacian, scale, orientation, descriptor, response and x, y. If i give it a very simple image, a triangle with no bottom and place it in two different places in two different images none of the info about the points are the same, Any help appreciated on how to compare points.


texts:
Given the following formal language $L$:

$$    L=\{ww \mid w\in\{a,b\}^*\}$$

Why is $a$ not a member of this language?

So what is $\{a,b\}^*$ exactly? I thought it means $(a+b)^*$?


texts: Encoding Turing machines in binary in a simple way that gurarentee unique readability

texts:
I may come across  something like (let $X$ be a binary representation of a Turing machine $M$), I know that we can easily encode the description of the machine as sequence of numbers (by assigning a number to every symbol and arranging the description in some particular way) and then encoding this sequence by a single number (using prime numbers and powers as in Godel numbering) and then considering the binary representation of this number as the encoding of the machine, but such an encoding would be difficult to manipulate and use in say a simulation.

If we want to encode Turing machines in binary form so that we can use this encoding in a simulation, such encoding should be simple so that we can recover the instructions of machine easily for example, A pair $(q_7,x)$ would be represented as the binary number of 7 followed by some (binary) distinguished mark that indicates the end of the number that represents that state and then a representation of the symbol $x$ but I can not see how can we come with such a "mark" that do the job and guarantee unique readability.

So, suppose that we want to encode every pair $(p,q)$ of natural numbers in binary. Suppose that we will do that by exhibiting the binary representation of both p and q with a (binary) mark in-between, is there any trick that we can use to add this distinguished (binary) string that will tell us where the first number ended and where the second starts? If not, then How can we encode Turing machines in binary so that, we guarantee well-readability and we can "recover" the instructions of implementation easily.


texts: Which component sizes do we observe while randomly deconstructing a tree?

texts:
Suppose I have a connected graph with $n$ vertices and $n−1$ edges, that is in form of a tree. Now, I will add the number of vertices in the tree and uniformly randomly select a vertex. I break the graph at this selected vertex, deleting the vertex and the edges connected to it. Now, I again repeat the same thing at all of the left components (sub-trees) until I am left with one vertex for which the answer is inherently $1$. What will be the expectation of the sum obtained by adding the number of vertices recursively in such a problem?

For example, I have 3 vertices, A, B and C in which A is connected to B as well as C, but B and C are not connected. Like, B--A--C. Now, I could select any one vertex out of three with probability 1/3, so I add 3. Now, if I had selected A, I would repeat this for B and C separately adding one for each case. Otherwise, selecting B or C, I would have repeated it on A--C or B--A respectively, adding 2 and selecting each node again with probability 1/2.

I agree the problem is weakly written, here is a formulation suggested by Karolis Juodelė:
I'm looking for the expected value of $f(G) = \left|V_G\right| + \sum f(G_i)$ where $G_i$ are components remaining after removing a random vertex of $G$.


texts:
How do those matrices work? Do I need to multiple every single pixel? How about the upperleft, upperright, bottomleft and bottomleft pixels where there's no surrounding pixel? And does the matrix work from left to right and from up to bottom or from up to bottom first and then left to right?

Why does this kernel (Edge enhance):

turn into this image:


texts: how to prove that nlogn is not Θ(n) without using limits?

texts:
i'm studying an algorithms designing and analysis , and i've question about Big-theta

how can i prove that nlogn is not Θ(n) without using limits ?


texts: Can the "divide" step in a merge sort be avoided?

texts:
So merge sort is a divide and conquer algorithm. While I was looking at the above diagram, I was thinking if it was possible to basically bypass all the divide steps.

If you iterated over the original array while jumping by two, you could get the elements at at index i and i+1 and put them into their own sorted arrays. Once you have all these sub-arrays ([7,14], [3,12], [9,11] and [2,6] as shown in the diagram), you could simply proceed with the normal merge routine to get a sorted array.

Is iterating through the array and immediately generating the required sub-arrays less efficient than performing the divide steps in their entirety?


texts: Find Index In Sorted Array Such That A[i] = C1 * i + C2

texts:
I'm already know that there is an algorithm that can solve A[i]=i in O(log(n)) in a sorted array.
But I want to know if there is any kind of algorithm that also can solve A[i] = C1 * i + C2 (witch C1 and C2 are constant values) in O(log(n)) or not


texts: The time complexity of finding the kth smallest number using buckets

texts:
I've implemented kth smallest number using buckets representing the current nibble value of each element in the array where current is a value starting possibly at 64 (for 64 bits integers at most) and decrements each iteration by 4 (nibble size).

I was wondering what is the time complexity (worst) of this implementation. I think it's O(n^log64/4) which is O(n^16), is that correct?

function nthSmallest(array, k, sizeOfInt) {
    let buckets = [
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        [],
        []
    ];
    // put numbers in buckets - O(n)
    for (let i = 0; i < array.length; i++) {
        const high = (array[i] >> sizeOfInt - 4) & 0xF; // 4 = nibble size
        buckets[high].push(array[i]);
    }
    let numbers = [];
    for (let i = 0; i < buckets.length && numbers.length < k; i++) {
        if (numbers.length === k - 1 && buckets[i].length === 1) {
            return buckets[i][0];
        }
        for (let j = 0; j < buckets[i].length; j++) {
            numbers.push(buckets[i][j]);
        }
    }
    return nthSmallest(numbers, k, sizeOfInt - 4);
}


texts:
A perspective transformation of a point is defined as follows:

$ x' = \frac{M_{11}x + M_{12}y +M_{13}}{M_{31}x + M_{32}y +M_{33}} $

$ y' = \frac{M_{21}x + M_{22}y +M_{23}}{M_{31}x + M_{32}y +M_{33}} $

Now, say I wish to transform a uniform grid (blue) and obtain the transformed grid (green), as illustrated below.

My intuition tells me that the largest transformed tile (on the green grid) will  be either in the top left, top right, bottom left or bottom right corners i.e. in one of the extreme corners.

Is there a (not necessarily formal) way to prove this?


texts:
All metric spaces obey the triangle inequality which is, for three points $a,b,c$, that

$$d(a,c) \le d(a,b) + d(b,c)$$

One interesting special case of a metric space is one endowed with an ultrametric structure, in which case the triangle inequality is replaced by the stronger inequality

$$ d(a,c) \le \text{max} \{ d(a,b), d(b,c) \} \,. $$

Ultrametric spaces occur in many fields of study, and naturally describe spaces with a tree-like structure.

I have been working on a project involving spin-glasses, and one of the interesting mathematical properties of the spin-glass phase is that the space of states is ultrametric. I am wondering if there are any other examples from computer science, where ultrametricity shows up. I am particularly interested when the space of states are $n$-bit binary strings, $\{0,1\}^n$, and the distance measure $d(\cdot, \cdot)$ is the Hamming distance. Clearly $n$-bit binary strings are not ultrametric on their own, but perhaps there are situations where the $n$-bit strings are naturally restricted in such a way that over the constrained space of bit strings the ultrametric property is satisfied.


texts: Does a binary code with length 6, size 32 and distance 2 exist?

texts:
The problem is to prove or disprove the existence of $C$, s.t., $|c| = 6,\forall c\in C$; $|C| = 32$; $d(c_i,c_j)\geq2,1\leq i<j\leq32$. ($d$ stands for hamming distance)

I tried to construct a satisfying code. The best I can get is to let $C = C'\times C'$, a concatenation of $C' = \{000,011,110,101\}$, which is of size 16. 32 happens to be the theoretical upper bound of the size, now I don't know what to do next so as to solve the problem.


texts: Find offset and page number given paged virtual memory address

texts:
I ran into this question in class:
Assume a machine that is 64-bit and has 8GB memory. They use a paged virtual memory where the page size is 4KB. You run the following program:
int main() {
   int *ptr = malloc(16);
   printf("%p\n", ptr);
   return 0;
}

and get output:
0x555555756260
We're to find the virtual page number of the address and the offset.
What I'm thinking is that I first convert that to binary, figure out how many bits and which bits represent the address/offset.
But I'm not sure how to figure out the latter. How can I determine which bits in the address correspond to which?
I'd really love some guidance


texts: Number of nodes in Van-Emde-Boas tree of universe size u?

texts:
The universe size $u$ in vEB trees is square rooted at each level until $u = 2$. So, unlike search trees, the branching factor is different at each level.

The height of the tree is $h = \lg \lg(u)$ and $u$ is an even power of 2, $u = 2^{2^k}$. I tried to calculate the count using the sum:
$$\sum_{i=1}^{h-1} 2^i\,2^{i + 1}$$
But it doesn't work. Any idea on how to do the math?

Edit:
Sorry for the confusion that might be caused by the illustration. The illustration is based on the CLRS book's implementation of VEB trees, but the summary nodes are not shown.
Thinking again about it now, I would like to know the count of all the nodes including the summary nodes and their tree nodes, as well as, the count of just the nodes without the summary.


texts: What is the difference between a tight Big $O$ bound, a tight Big $\Omega$ bound and a Big $\Theta$ bound?

texts:
I occasionally see these terms used and I'm not really sure what is meant by all of them. Is it possible for an asymptotic bound that is not Big $\Theta$ bound to be "tight"? What does it mean for bounds that are not Big $\Theta$ to be tight?

Is there a difference between a tight Big $O$ bound and a Big $\Theta$ bound?


texts:
I'm considering the standard Erdös/Renyi $G(n,p)$ model where we have $n$ nodes and each possible edge is sampled independently with probability $p = \frac{1}{n^\epsilon}$.

It is relatively straightforward to show that, starting from any node $u$, the expected number of hops to reach every other node is $1/\epsilon$. However, this does not say much about the probability of having a diameter of $1/\epsilon$.
(I could apply Markov's inequality, but that gives a rather weak bound.)

Thus I'm looking for a reference to a concentration result that states that the diameter of such a random graph is $O(1/\epsilon)$ with probability at least $1 - o(1)$.


texts:
I just read the Wiki article for Simon's Problem but I don't fully understand it because I don't follow the symbolic notation used to describe functions (I am not a computer scientist).

Can someone just briefly explain it in simple language, like is it just XOR'ing two binary strings and trying to isolate each string? Also, if this problem is known to take exponential time to solve, why isn't it being used as a cryptographic primitive?


texts: How can I express the similarity between a Bing and a Google search result?

texts:
I'm working on a "semantic" browser engine where all search engines should look the same. One way to do this is to hard-code parsing rules for each site; another is to use machine-learning. Of course the latter alternative is the hip and cool one. ;)

I need a method to cluster links from search results from Bing, Google and other popular search engines. Menu links, pagination, etc, should be in a different cluster than listed search results. I've tried KMeans, it didn't work so good. DBSCAN worked fine with Google, but I couldn't easily transfer the result to Bing.

There are a lot of different features one can consider for HTML elements, in my case <a>, anchors. I've tried combining number of children (recursively), text length, number of attributes and some more. Is it possible to advice in which direction to go? I have no former experience with machine-learning, so tuning an algorithm by hand like this is not trivial.

Thankful for any feedback.


texts: Sorting post numbers in a graph in $O(n)$ time

texts: After running dfs on a graph, we get a list of n post and pre numbers. How do we sort this list in $O(n)$ time instead of $O(n\log n)$ time?


texts: Neural networks fed with training data on demand?

texts:
What I want to achieve is to build a neural network with Keras which will have to stabilize
a quadcopter I've built. The network would have three inputs: pitch, roll, yaw, acceleration x, accel y and accel z and four outputs: pwm length for motor 1, 2, 3 and 4. The problem is that the length of the pwm wave needs to fit the range from 1000 (no throttle) to 2000 (max throttle). I know I can map the output to this range, but will this work? And another problem is if it's even possible to train such a network, because I have no model data, they would be submitted real-time during training, when the mpu6050 updates the gyro and accel data, which will rely on the network's output - the speed of each motor?


texts:
I want to prove that $L(G) = \{01; 11110; 10101; 000\}$ is regular.

Is it correct if I write there exists a regular expression, which is: $(01|11110|10101|000)$?

How can I also prove it using a DFA?


texts: One-way-function based on Friedberg numberings

texts:
A one-way-function is an easy to compute function $y=f(x)$ which is hard to invert. In 2000 Levin showed an example of a function which is one-way if there are one-way functions. As far as I know, it is still not clear whether true one way-functions exist.

Now with Friedberg numbering, which roughly speaking, is a programming language with the following properties:

turing completeness
no two programs perform the same task
every computable function has a corresponding program but there's no way to find it. There is a non-existance proof of a compiler in this language. i.e. one can not programm with friedberg numberings. However, if you have for some reason a program in this language it is executable.

In the following argument has to be a a pretty basic flaw as it would establish the existance of one-way-functions if it would be right.

Suppose we have a regular programm $x_p$ in a "normal" language which computes $y = P(x_p)$. Here $P$ is the function which which maps $x_p \rightarrow y$.  Also assume a programm $x_F$ in the language of Friedberg enumberings which for some reason computes $F(x_F) = y$ too. If we invert the friedberg enumberings $F^{-1}(y) = x_F$ we have established a compiler for Friedberg numberings by inverting $F$, as we have established a mapping $x_P \rightarrow x_F$. However, we know there is no such compiler, hence our assumption $F$ is invertible is wrong. This establishes them as one-way-function as Friedberg numbering are perfectly computable, but not invertable.

Possible loopholes:

It is clear that $F^{-1}$ needs to run forever for any input $y$, as every bijective function has an inverse. However, not every bijective function has necessarily a computable inverse. There might be a mapping, but we can not compute it in finite time. I'm not sure if this changes the argument. The point is if we can invert $F^{-1}$ than we have a compiler, and if we can't than we have a one-way-function. Also $F^{-1}$ might be approximateable.
$P$ is not necessary halting for all $x_p$. Ok, lets restrict us to all halting $x_p$ (which is impossible to know beforhand)

If this argument would be right it would make Friedberg numbering a bijective one-way-function with the stronger guarantee of beeing impossible to invert instead of just beeing hard to invert.

What is wrong with this argument?


texts: Why use coroutines instead of mutable objects?

texts:
What scenarios would cause coroutines to be a better (i.e. more robust, easier to modify) answer than simple mutable objects?

For example, in Fluent Python, the following running average example is used to show what coroutines can do:

def averager():
    total = 0.0
    count = 0
    average = None
    while True:
        term = yield average
        total += term
        count += 1
        average = total / count

Why not just use a class-based object?

class Averager:

    def __init__(self,):
        self.total = 0.0
        self.count = 0
        self.average = None

    def send(self, term):
        self.total += term
        self.count += 1
        self.average = self.total / self.count
        return self.average


texts:
I have been trying to come up with a better algorithm that detects conflicts in the scenarios below.

Let's say we have 4 dancers. We pair them up and find out which ones can dance together. So, we have the dancer # combination and whether they can dance together or not.

(1,2) True
(1,3) True
(1,4) False
(2,3) True
(2,4) False
(3,4) False

At the end of the day, I want to know which group of dancers I can group together.

A group can only be formed when all of the dancers within the group can dance with each other AND no dancer outside the group can dance with any dancer in the group.

For example, group A can be formed with dancers {1,2,3} because they call can dance with each other (i.e. (1,2), (2,3), and (1,3) are True) AND no dancer outside the group can dance with them (i.e. 4 is outside the group and (1,4),(2,4),(3,4) are all false).

Now, if we change:

(2,4) -> True

grouping changes quite a bit. I can no longer group 1,2 and 3 together because even though (1,2), (1,3) and (2,3) are all True, there is a dancer (#4) that can dance with 2 (i.e. (2,4) is True).

Now, can we group 1 and 3? No. Even though (1,3) is True, there would be one dancer outside the group that CAN dance with either 1 or 3 (i.e. (2,3) and (1,2) are True).

I came up with an algorithm that simply uses some non-sophisticated logic, but I was wondering if one can frame this problem in terms of a CS or Math problem, and whether something similar has been formally solved already.

If it helps you visualize this, you can draw rectangles or circles where they overlap if they can dance together.


texts: DP Knapsack Problem With Categorical Constraint

texts:
so I'm working on a variation of the knapsack problem which includes a constraint on the number of each item from each category in addition to a weight. For instance, we have a number of books each given a genre (1 of 3  genres), and our goal is to maximize the total weight as well as include at least G books from each genre.

The recursion is found below, but when trying to convert this to a DP solution I'm having some issue. Note that the problem specifically deals with books, their categories, and maximizing an enjoyment factor up to some k. It's identical to the knapsack problem beyond the fact that the items are categorized and we need at least N items from each category.

private double S2(int W, int k, List<Book> books, int F, int SC, int C) {
    if(W == 0 || k == -1) {
        if(F <= 0 && SC <= 0 && C <= 0) {
            return 0.0;
        } else {
            return Double.NEGATIVE_INFINITY;
        }
    }

    Book b = books.get(k);
    int w = b.getWeight();
    if(W-w >= 0) {
        int newF = F;
        int newSC = SC;
        int newC = C;
        if(b.getGenre() == Book.Genre.FANTASY) {
            newF = F-1;
        }
        if(b.getGenre() == Book.Genre.SCIENCE_FICTION) {
            newSC = SC-1;
        }
        if(b.getGenre() == Book.Genre.CLASSICS) {
            newC = C-1;
        }
        return Math.max(b.enjoyment+S2(W-w, k-1, books, newF, newSC, newC), S2(W, k-1, books, F, SC, C));
    } else {
        return S2(W, k-1, books, F, SC, C);
    }
}

My DP solution involves a 5 dimensional array for W, k, F, SC, C and I'm just traversing it in 5 dimensions and filling in each value based on the recursion but it's way too slow--in fact, slower than the recursion for small n (even though it should run in polynomial time as opposed to exponential time). Is there some quicker way to traverse the subproblems in the DP solution, in some specific order?

I'm basically doing "tabular memoization" in 3 extra dimensions for the original Knapsack problem with only 1 constraint. Is my recursion wrong? Or is this to be expected?


texts:
currently i'm preparing for an exam in a high performance computing course. In this course we discuss several common parallel algorithm patterns called "dwarfs". The first dwarfs we had was the "dense linear algebra", so basically matrix multiplication. In one of the first slides there is a example for a basic matrix multiplication:
MatrixMult PRAM(A:Matrix[n], B:Matrix[n], C:Matrix[n]) {
for i from 1 to n do in parallel
    for k from 1 to n do in parallel
        for j from 1 to n do
            C[i,k] = C[i,k] + A[i,j]∗B[j,k]
}

Nothing really fancy, just the basic matrix multiplication. But below this piece of code the slide states:

• synchronized execution of the for-j-loop;
→ in the first step:
• all processors $P_{i,k}$ simultaneously access A[i,1]
• all processors $P_{i,k}$ simultaneously access B[1,k]

I don't understand why all processors access these elements at the same time. I thought every processor has a different value for i and k, so every processor should access a different element. For example, n=3:

Time step (execute first for loop in parallel on all P):

P1 -> i = 1
P2 -> i = 2
P3 -> i = 3

Time step (execute second for loop in parallel on all P):

P1 -> k = 1
P2 -> k = 2
P3 -> k = 3

Time step (execute third for loop sequential on all P):

P1 -> j = 1, i=1, k=1 ==> A[1,1] B[1,1]
P2 -> j = 1, i=2, k=2 ==> A[2,1] B[1,2]
P3 -> j = 1, i=3, k=3 ==> A[3,1] B[1,3]

Time step:

P1 -> j = 2
P2 -> j = 2
P3 -> j = 3

etc..

So in the third time step every processor would access another element. So i'm not quite sure if i understand the "do in parallel" statement correct. I thought that every statement in this loop would be executed on every processor but with different index as Joseph JáJá defines the "pardo statement" (i think it's the same like "do in parallel") as follows:

for l $\leq$ i $\leq$ u pardo statement
The statement (which can be a sequence of statements) following the pardo depends on the index i. The statement corresponding to all the values of i between l and u are executed concurrently
(from "An Introduction to parallel algorithms", Jospeh JáJá page 27)

So the question is, why do all processors access the same element and how does the "do in parallel" statement work? I'm not sure if i understood this statement.


texts: does a DFA converted from NFA always contain 2^Q states?

texts:
when converting an NFA to DFA, we create sub-sets of states in the NFA.
does it mean that every DFA-converted-from-NFA contain 2^Q states? or if some sub-sets are unreachable then they are not included in it?


texts: Mapping Reductions to Complement of A$_{TM}$

texts:
I have a general question about mapping reductions. I have seen several examples of reducing functions to $A_{TM}$

where $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine which accepts string } w\}$

which is great for proving undecidability. But say I want to prove unrecognizability instead. That is, I want to use the corollary that given $A \le_{m} B$, if $A$ is unrecognizable then $B$ is unrecognizable.

So for any arbitrary unrecognizable language $C$ which can be reduced to $\overline{A_{TM}}$ (any example language would suffice for sake of example), how can I reduce $\overline{A_{TM}} \le_{m} C$?

For simplicity, suffice to merely consider TM in $\overline{A_{TM}}$.

EDIT

For clarification, $\overline{A_{TM}} = \{ \langle M, w \rangle : M \text{ is a turing machine which does not accept string } w \}$


texts: How to find mean ,max ,min in constant time?

texts: I was asked to be able to find minimum, maximum and mean of a large array in constant time. I used 3 variables to track these statistics and updated them on every insert operation. I don't feel like it is the correct answer or maybe there is more nuance. Given that nothing was said about extra space, is this the simplest(and correct) way to do it ?


texts: Recognizing vs Deciding in defining class BPP

texts:
In Sipser's text, he writes:

  When a probabilistic Turning machine recognizes a language, it must
  accept all strings in the language and reject all strings not in the
  language as usual, except that now we allow the machine a small
  probability of error.

Why is he using "recognizes" instead of "decides"? If the machine rejects all strings that are not in the language, then it always halts, so aren't we restricted to deciders in this case?

The definition goes on:

  For $0 < \epsilon < 1/2$ we say that $M$ recognizes language $A$ with
  error probability $\epsilon$ if

  1) $w \in A$ implies $P(M \text{ accepts } w) \ge 1 - \epsilon$, and

  2) $w \notin A$ implies $P(M \text{ rejects } w) \ge 1 - \epsilon$.

So it seems like the case of $M$ looping is simply not allowed for probabilistic Turning machines?


texts: What does it mean for a grammar to be LR(0)?

texts:
I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).
For part of an assignment I had to form the DFA for a grammar, which I had no issues with. And then I have been asked whether the grammar is LR(0).
My guess is yes, but not because I understand exactly what it means. I would assume it isn't if, when creating the DFA I came across some strange behaviors that prevented the DFA making any sense (if you know what I mean/if I'm making any sense).


texts: Sequential History in Herlihy and Wing's Linearizability paper

texts:
I've been reading Herlihy and Wing's paper Linearizability: A Correctness Condition for Concurrent Objects (ACM Transactions on Programming Languages and Systems, 12(3):463–492, 1990; PDF) and there's one piece of the paper that is a fairly small detail, but on which I'm stuck anyway. They define a sequential history as one satisfying two conditions:

First event of $H$ is an invocation
Each invocation, except possibly the last, is immediately followed by a matching response. Each response is immediately followed by a matching invocation.

Question 1 Since an invocation and response match iff they have the same object and process, does "each response is immediately followed by a matching invocation" imply that all events in a sequential history share the same object and process (since each event matches the prior event)?

Question 2 Later in section 2, they offer the following as an example of a sequential history, even though it involves multiple processes:

q Enc(x) A
q Ok() A
q Enq(y) B
q Ok() B
q Deq() B
q Ok(x) B
q Deq() A
q Ok(y) A
q Enq(z) A
q Ok() A

I suspect that the definition of sequential history actually doesn't include the constraint "each response is immediately followed by a matching invocation" but maybe it does and I'm just misreading it. In either case, thanks for any enlightenment anyone can provide!


texts: Find hamilton cycle in a directed graph reduced to sat problem

texts:
I need to find a Hamiltonian cycle in a directed graph using propositional logic, and to solve it by sat solver. So after I couldn't find a working solution, I found a paper that describes how to construct a CNF formula to find an Hamiltonian path:

Xi,j - node j is in position i in the path

List of constraints:

Each node j must appear in the path
x1j ∨ x2j ∨ · · · ∨ xnj - for every node j
No node j appears twice in the path ¬xij ∨ ¬xkj for all i, j, k with i 6= k.
Every position i on the path must be occupied - xi1 ∨ xi2 ∨ · · · ∨ xin for each i
No two nodes j and k occupy the same position in the path - ¬xij ∨ ¬xik for all i, j, k with j != k
Nonadjacent nodes i and j cannot be adjacent in the path - ¬xki ∨ ¬xk+1,j for all (i, j) !∈ E and k = 1, 2, . . . , n − 1.

My question is, how can I find Hamiltonian cycle using these constraints? I understand that I need to check if there's a cycle (v1==vn), that's one thing (But I got constraint 2). Second, it's a directed graph and I don't know how can I assure that the vertices would be in the right order of the edges, I thought about this:

Every two nodes must have edges -  Xki ^ Xk+1j for each (i,j)∈ E and k = 1, 2, . . . , n − 1.

But it doesn't seem to work, any help would be appreciated.

EDIT

What I did was to add another constraint -

No edges from the set: (i,j)!∈ E that are the last and the first


texts: How can $ww = www$ hold for any word $w$?

texts:
Speaking in terms of automata and regular languages, how would it be possible for a string repeating some $w$ twice equal a string repeating that same $w$ thrice? That is, why is the language

$\qquad L = \{w \in \Sigma^ * \mid ww = www\}$

not empty? The only thing I can think of is $w = abab, ww = abababab, www = abababababab$, but I don't think this is correct.


texts: Is finding all primes less than n, doable in polynomial time?

texts:
Bear in mind I'm almost a complete noob at complexity theory.

I was reading about how AKS Primality shows that numbers of size n can be shown to be prime or composite in polynomial time. Given that, does that imply finding all prime numbers less than a number n is also doable in polynomial time and thus the algorithm runs in FP. Additionally, does this imply that counting all primes less than n is not in #P?

Any ideas, or comments are appreciated Thanks!


texts: Will the minimum spanning tree not have only those edges specified by the cycle property?

texts:
I have just started to understand the "Minimum Spanning Trees" (MSTs), and had come across the cycle property. I am referring to the book - Algorithm Design by Jon Kleinberg and Eva Tardos. The statement of the property as written in the book is:

  Assume that all edge costs are distinct. Let C be any cycle in G, and let edge e = (v,w) be the most expensive edge belonging to C. Then e does not belong to any minimum spanning tree.

Now my doubt is: Are the edges of a graph (undirected graph with edges having distinct positive weights) that do not satisfy the cycle property the only ones which aren't present in the MST or will there be any other edges that don't belong to the MST and aren't covered by this property?

I am unable to come up with a proof to argue about whether such edges exist or not. Can some please give a proof for this?


texts: Edge Covering with different colored edges

texts: I have a graph with the edges already assigned colors and there are edges of the same color as well as different colors incident to each vertex.  I would like to find an edge cover (does not have to be minimal) such that no two different colored edges of the edge cover are incident to the same vertex.  I thought about trying to extend a maximal matching, but then some of those edges of the matching might have to change to accommodate the unmatched vertices.  I also thought about somehow assigning weights to the colors and changing it into an assignment problem, but this also doesn't seem to be sufficient since higher weighted colors can be used as many times as required as long as the condition (of different colored/weighted edges not incident to one another) is fulfilled.  Any suggestions or hints?


texts: why does message authentication using 2-universal family of hash functions require a prime number of possible hash values?

texts:
I am self-studying the book Intro to Algorithms 3ed by CLRS. One of the problems seems to give a piece of information that is not necessary, Problem 11-4 in the book states

  Let H be class of hash functions in which each hash function h ∈ H maps the universe U of keys to {0, 1...m-1}. We say H is k-universal if, for every fixed sequence of k distinct keys {x1, x2...xk} and for any h chosen at random from H, the sequence  is equally likely to be any of the m^k sequences of length k with elements drawn from {0, 1...m-1}

  part d (previous parts are unrelated): suppose that Alice and Bob secretly agree on a hash function h from a 2-universal family H of hash functions. Each h ∈ H maps from a universe of keys U to Zp = {0, 1, 2...p-1}, where p is prime. Later, Alice sends a message m to Bob over the Internet, where m ∈ H. She authenticates this message to Bob by also sending an authentication tag t = h(m), and Bob checks that the pair (m,t) he receives indeed satisfies t = h(m). Suppose that an adversary intercepts (m,t) en route and tries to fool Bob by replacing the pair (m,t) with a different pair (m',t'). Argue that the probability that the adversary succeeds in fooling Bob into accepting (m', t') is at most 1/p, no matter how much computing power the adversary has, and even if the adversary knows the family of H of hash functions used.

So the best thing the adversary can do is find all h' such that h'(m) = t, then find some m', t' pair that matches as many of those h' as possible. However, since the universe H is 2-universal, that means even if the adversary has narrowed it down to the smaller set of h', for each m', the value of t' is still equally likely to be any of the p possible values. Hence, the probability of the adversary's pair m', t' matching Alice and Bob's function h is exactly 1/p, assuming that the adversary has narrowed it down at first.

However, the problem stated that p is prime. In the argument I gave, at no part did I use that fact, so either my argument is wrong, or the problem has made a somewhat unnecessary condition?


texts: Variable assignment in which compiler phase

texts:
If I have a statement int a=5, in which phase will symbol table be updated with value of a (which is 5) ?

Different websites have different answers to it. In some of the websites it is written that assignment happens in syntax analysis phase and in others it is written that assignment happens in semantic analysis phase.

Which is correct?


texts: How to find the equivalence classes of a regular language

texts:
Given a language $L=\{ 0^m1^n | m \neq n \}$ over $\Sigma = \{ 0,1 \}$, how would one go about characterizing the equivalence classes of this language?
I know there isn't a formal algorithm for that, but still, can some steps always be taken?


texts: Simple proof that circuit satisfiability problem is NP-Hard

texts:
$\newcommand{\np}{\mathsf{NP}}\newcommand{\cc}{\textrm{Circuit-SAT}}$I am having difficulty understanding the $\np$-hardness proof for $\cc$ in CLRS.

$\cc = \{\langle C \rangle : C \text{ is a satisfiable combinatorial boolean circuit} \}$
Lemma: The $\cc$ problem is $\mathsf{NP}$-hard.

Can anyone provide an easy-to-understand proof?


texts: Handling untrusted string input in printf in C

texts:
I stumbled upon the MSDN Best Practices for Code Review.
Under the section “Untrusted Inputs”, I found following which I didn't understand properly. Why is the following considered safe?
printf("%s", buffer);

What kinds of guarantees does the C language give regarding the behavior of this snippet? Given that both printf(buffer) and printf("%s", buffer) are accepted by the compiler, why is one considered safer than the other — shouldn't the unsafe version be rejected?

Copied following text from the source:

Untrusted Inputs
If the input buffer comes from an untrusted source, this can result in a security attack, as the input can contain formatting specifiers that will pull data off the stack. Additionally, it can cause buffer overflows by expanding the resulting string beyond expected limits:
printf(buffer);
These should always be converted to the following:
printf("%s", buffer);


texts: How to produce all the numbers in a range [0,1,...,n] for which if 0<=k<=n, then for a positive integer x, the expression: k & x = k?

texts:
I am trying to figure out an efficient way to produce all the numbers in a given range for which, their bitwise AND with a positive integer (say x) gives the same number; that means k & x = k.

Is there a better way to do it so that I do not need to go through all the numbers from 0 to n and check for it?


texts: What can be the time complexity of an algorithm that calculates the weights of the nodes in a graph?

texts: I am trying to find the best time complexity of an algorithm that calculates the weights of all the nodes on a graph. The weight of the node is defined as the sum of the weights of the edges adjacent to it. I can argue that the algorithm is similar to the one which would calculate the degree of all the nodes and that certainly takes O(|V|+|E|) but can we say the same thing if we are trying to calculate the weights of nodes?


texts: What is the best solution to find whether the sum of an array is even or odd

texts:
I was asked this question in an interview. I was not able to find a better solution than $O(n)$ which is just going over the array and finding the sum. Can it be done any better? I am not really interested in the actual sum, I just want to know whether it's even or odd.

Or how do I prove that it cannot be done better than $O(n)$?


texts: Design a Turing Machine Checking if power is prime

texts:
I have to design a Turing Machine to do the following, but I don't really know where to start with this question. Any help would be very much appreciated.

I should design a Turing Machine accepting language $L = \{ a^p |$ p is not a prime number$\}$.
I know I should use some quality of prime numbers, but number theory never was my strong side. How do I proceed with this?


texts:
Let $G=(V,E)$ a directed graph. We define $v \in V$ to be "nearly root" of there's a path from $v$ to at least $|V|/2$ vertices. How do you find the set of all "nearly roots" in linear time?

What we've tried is to build the strongly connected graph $G_{scc}$ obtained from $G$ and then to do a topological sort. Now we went backwards and for each $U\in G_{scc}$ we count how many vertices it can reach by scanning all outgoing edges and summing up all vertices reachable from it's successors. This seems wrong since we may count vertices more than once.


texts: Link utilization of sliding window protocol

texts:
Before I ask my doubt I would like to state that problem which led me to my doubt. It can also serve as a good example scenario.

  A $20\ Kbps$ satellite link has a propagation delay of $400\ ms$. The transmitter employs the "Sliding Window protocol" scheme with Window Size set to $10$. Assuming that each frame is $100$ bytes long. What is the link utilization of transmission medium.

From the question we can make out that Window Size $(WS)$ is $10$, transmission time $(T_t)$ of a frame is $40\ ms$ , and propogation time $(T_p)$ is $400\ ms$.

Now, the solution that book proposes simply states that Link Utilization $(LU)$ for sliding window protocol can be calculated as

$$LU = \frac{WS*T_t}{T_t + 2*T_p}$$

That's where I'm facing the problem. From what I have learned about Link utilization

  It is the fraction of total time the host was busy in transmission of data. In other words, it is the ratio of total transmission time over Total Time involved in transmission.

Now if I try to fit the formula proposed in book with what I have learned, the total time involved in transmission is $T_t+2*T_p$.

But that is only the total transmission time of one single packet over the medium. Why isn't it is $WS*T_t + 2*T_p$, since we are sending $WS$ packets without wating for acknowledgement.

The only thing I could figure out after thinking a lot about my doubt is that I am probably going wrong because of my incomplete understanding of what Link Utilization means.

I will appriciate any kind of help.


texts: When would Kosaraju's algorithm be a better choice than Tarjan's for strongly connected components?

texts:
I know both have runtime complexity $\mathcal{O} (V+E)$, but Tarjan's algorithm does a single DFS pass, whereas Kosaraju's does two DFS passes. Both need extra space (e.g. a dynamic set, often a stack, for the former to keep track of low links, and e.g. a linked list for the latter to do the second traversal in decreasing finish time order from the first traversal).

I often see textbooks (e.g. CLRS) describing Kosaraju's instead of Tarjan's algorithm. Maybe that's for pedagogical reasons, but I wonder if there is something else to it.


texts: Strings that do not contain 11 as a substring

texts:
Today I had a couple of formal language lectures. The Instructor wrote a regular expression for the alphabet $\{0,1\}$ which does not include any string which includes "11" as a substring.

She wrote that regular expression: $0^*\cup 0^*1(00^*1)^*0^*$.
I have nothing against that but after the lecture I tried to solve that problem on my own and came up with that expression:  $0^*\cup0^*(100^*)^*0^*$.

Is that true? It appears to me that I can even get rid of $0^*$ at the end of expression and simplify as $0^*\cup0^*(100^*)^*$.


texts: Does $\#W$[1]-hardness imply approximation hardness?

texts:
Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$.

Assume that $\Pi$ is $\#W$[1]-complete (a known problem for example would be counting the number of simple paths of length $k$ in a graph).

Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?

Note that when discussing a parameter which is the cost of solution it makes sense to discuss the approximation hardness (e.g. see this question), as opposed to other popular parametrizations.


texts:
I have a directed acyclic graph whose vertices are either red or black.
I want to perform edge contraction between pairs of red vertices only, and avoid introducing cycles. The goal is to have the fewest number of red vertices remaining (and no cycles. Note that after edge contraction, the resulting self-loop is removed, it does not violate the no-cycles rule).

In the example below, I could merge vertices 1 and 3, or I could merge vertices 3 and 4, but I can't merge all 3 together, since this would introduce a cycle with black vertex 2.

I want to merge as many red vertices as possible, to reduce the number of nodes in the graph. How can I do this efficiently? I don't necessarily need an optimal solution (where optimal => smallest number of remaining vertices). I potentially have 100k nodes, evenly split red and black.

There are 2 optimal solutions for the simple example shown. Here is one.


texts: Quadratic equations using 2 different approaches

texts:
I am reading Mark Newman's Computational Physics and at chapter 4 page 133 in Exercise 4.2 he asks

a) Write a program that takes as input three numbers, a, b, and c, and prints out the two solutions to the quadratic equation $ax^2 + bx + c = 0$ using the standard formula $x = −b± (b^2 − 4ac)^{1/2}/2a$ . Use your program to compute the solutions of $0.001x^2 + 1000x + 0.001 = 0$.

b) There is another way to write the solutions to a quadratic equation. Multiplying top and bottom of the solution above by $-b∓ (b^2 − 4ac)^{1/2} $, show that the solutions can also be written as $x = 2c/−b∓(b^2 − 4ac)^{1/2}$. Add further lines to your program to print these values in addition to the earlier ones and again use the program to

I tried both ways and a) gives me

[-9.99989425e-13 -1.00000000e+00]
and

b)
[-1.00000000e-06 -1.00001058e+06]

how can I understand which one is correct ? Or why is this happening ?


texts: Behavior of iterative application of LZ77

texts:
I have been experimenting with LZ77 (naively $O(n^2)$ runtime, infinite window). Applying it to the 7th Fibonacci word $abaababaabaab$ yields the correct LZ factorization:

$\qquad a,b,a,aba,baaba,ab$.

My question is about the behavior of LZ77 if we iterate it. My experiments suggest that reapplication of LZ77 to the input will yield no further patterns that were not found the first time.

By reapplication I mean, where in the first instance we treat the factors of the string as the sequence of unit symbols 'a' and 'b', in the second application the factors are the LZ factors. I was hoping to discover (over larger various texts, like the Complete Sonnets of Shakespeare) increasing gains, and possibly, "multilevel" patterns found by LZ over the sequence of factors of the previous iterate. But none of this occurred. The sequence of factors after the second iteration is exactly the same as the first.

So where is the bug in my thinking? Is there a simple proof of this given the definition of an LZ factor being the longest prefix from the current position occurring in the concatenation of the preceding LZ factors?


texts:
Here, Yuval Filmus wrote:

Unary encoding is only relevant in contexts where the length is not fixed.

Are there words without fixed size length?
Is there a Computer Science theory which describes computers which can include such words in their memory cells (while at least some words are unary) and could the output of such computers be similar to that of RAM-modeled/Turing-modeled Turing-complete computers?


texts: why does LSPACE(log space) complexity class exist but not logtime?

texts:
I noticed that in complexity classes, logspace class is defined but there is no logtime.
I was wondering how is that possible?
Normally, I would expect the opposite, It is possible to do a search query in an ordered list in time less than the time of iterating over all items (==> Logtime?). However you can't store a list in of size n in log(n) space...
So how come Logspace exists but not logtime? there's obviously something wrong with my reasoning.
Could someone please correct me?
Thanks in advance


texts: Proving that the language of TMs with finite left head moves is undecidable

texts:
I'm trying to prove that the following language is undecidable:$$
   \{ \langle M, w \rangle ~|~ M \text{ is a TM where its head moves left a finite number of times on } w \}
$$

But I'm having a bit of trouble. I know I have to do some type of reduction, but I'm not really sure what. Can a Turing Machine be simulated by one which only moves left? if so, then I think I could show $A_{TM}$ reduces to it. Any hints would be appreciated.


texts: A question on the BSS model with inequalities allowed

texts:
Let $k,M\in\Bbb N$ be fixed. In the BSS model we allow only $+,-,\times,=$ as valid operations and also an initial set of constants that are fixed for all instantiations of the algorithm. Here we relax $=$ and add $\geq,\leq$ operations.

Fix an upper bound on inputs and call this $M$.

Problem $1$ Given input $ka$ for some $a\in\Bbb N$, what is $a$?

Problem $2$ Given input $a^k$ for some $a\in\Bbb N$, what is $a$?

Is there an algorithm for both problems whose runtime depends only on $k$ using only ring operations only?


texts: Linear time parsing from star of context free language

texts:
I was wondering if there are cases in which the star closure of a language can make the resulting language easier to parse. In particular, if I have this grammar:

S -> c|AS|A
A -> aAa|bAb|e

I can see that $L(A) = \{x x^R : x \in \Sigma^*\}$ (where $x^R$ denotes the reverse of $x$). That language is not even deterministic context free since I can't determine where the switch from $x$ to $x^R$ happens looking at the top of the stack only.

Using Arden's rule, I noticed that $L(S) = L(A)^* c + L(A)^*$. So, is it possible to parse $L(S)$ without nondeterminism? I thought that a string $w$ like $aaabbaaa$ could be seen, in $L(S)$, as a concatenation of $w_1 w_2 w_3$ where $w_1 = aa$, $w_2 = abba$, $w_3 = aa$. As for this word in particular, an automaton could recognize and accept the strings by inspecting only one stack symbol at a time. Could this be generalized in some way for the whole language $L(S)$ of the example?

In particular, is $L(A)^*$ a deterministic context-free language?  Can it be accepted by a deterministic pushdown automaton?


texts: NFA for words which start and end with different letters with $O(\log(| \Sigma |))$ states

texts:
I'm trying to build a NFA for the following language
$ L = \{ \sigma_1 \sigma_2 \sigma _3 \ldots \sigma _n \mid \sigma _1 \neq \sigma _n \}$.
The catch is that for $ \Sigma $ such that $ |\Sigma|=2^k $, the NFA should have $\Theta(k)$ states.
I was thinking of representing the letters in binary but I'm not sure what I should do exactly.


texts: When are adjacency lists better than sparse matrices?

texts:
I saw several questions discussion the benefits of adjacency lists over matrices to represent a sparse undirected graph. On the other hand, none of them discuss sparse matrix representations such as scipy's coo or csr formats.

Do adjacency lists still provide benefits in this case?

Definitions of the above:

Adjacency list: a graph is represented as a dictionary, where each vertex is associated to the list of its neighbors (and the value of the edge): {i: [(neigh_1, val1), (neigh2, val_2)]}. Suppose these lists are linked lists ;
coo format: the graph is represented as a dictionary of edges: (i,j) -> value.
csr format: the matrix is stored row-wise. For each non-zero row, we have 2 arrays: indices[i] and values[i]. Example: indices[i] = [neigh_1, neigh_2], values[i] = [neigh1, neigh2].

Related: When are adjacency lists or matrices the better choice? and https://stackoverflow.com/questions/2218322/what-is-better-adjacency-lists-or-adjacency-matrices-for-graph-problems-in-c/5419933#5419933


texts: State true or false --> x = Θ(n⁴), y = Θ(n²) therefore x/y = Θ(n²)

texts:
State true or false
$x=\Theta(n^4)$, $y=\Theta(n^2)$ therefore $x/y=\Theta(n^2)$

I think the ans is true,but in the book it says false. What is the explanation?

My reason for thinking it to be true is that say for x we have a polynomial $n^4$+...... and for y we have a polynomial like $n^2$+... so if we divide x/y the ans should have the highest power of $n^2$ and the resultant polynomial will be like $n^2$+.... So it should be $\Theta(n^2)$


texts:
So I have this question to prove a statement:

$O(n)\subset\Theta(n)$...

I don't need to know how to prove it, just that in my mind this makes no sense and I think it should rather be that $\Theta(n)\subset O(n)$.

My understanding is that $O(n)$ is the set of all functions who do no worse than $n$ while $\Theta(n)$ is the set of all functions that do no better and no worse than n.

Using this, I can think of the example of a constant function say $g(n)=c$. This function will surely be an element of $O(n)$ as it will do no worse than $n$ as $n$ approaches a sufficiently large number.

However, the same function $g$ would not be an element of $\Theta(n)$ as g does do better than $n$ for large $n$... Then since $g  \in  O(n)$ and $g \not\in \Theta(n)$, then $O(n)\not\in\Theta(n)$

So is the question perhaps wrong ? I've learnt it is dangerous to make that assumption and usually I have missed something, I just can't see what it might be in this case.

Any thoughts ?
Thanks a lot..