texts: Deterministic processing on probabilistic input

texts:
I've designed an algorithm, is which responsible to process some samples from normal distribution under aegis of some deterministic steps. In other words, the algorithm generate unique response to a unique set of the random set of input.

Now I am prone to plan a title for the corresponding paper and there is a noticeable ambiguity regarding the manner by which the algorithm could be addressed...

It is neither non-deterministic nor randomized and probabilistic. What is this algorithm type? Should I name that as typical deterministic?!...

Edit: This algorithm is supposed to be fed by a number of agent coordinates (are which random normal-driven integer numbers). It should colonize the agents into groups in a specialized manner. Thus, the input is probabilistic but both the algorithm process and the output are considerably deterministic.

The current idea regarding the title is:

Optimal Communication of Agents by the Probabilistic Colonization of the Robot Swarm

But that Probabilistic word does not sound so deserving...


texts: Guessing the structure of a finger tree from the number of elements

texts:
I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger tree from the sequence efficiently, as described below, and then concat it to the original finger tree. Concat is a very cheap operation compared to adding many elements.

To construct the finger tree, I put the elements into an array, and get its length. Then I build the finger tree from the bottom up, starting with the deepest deep tree and working outwards. This should be much, much more efficient.

In order to do this, I must guess the structure of the resulting finger tree from the number of elements to be added, and I'm not sure how to do this.


texts:
Suppose we have a BPP algorithm $A$ s.t. its running time is random and is $O(n^2)$ in expectation. How do we create a new BPP algorithm $B$ to solve the same problem s.t. it has deterministic running time $O(n^2)$?
My effort:
Denote the running time of $A$ as $T$. Suppose $E(T)\leq T(n)=O(n^2)$.

Run $A$ at most $kT(n)$ steps.
If it terminates, return its output; otherwise, output Yes with probability $q$.

But I just proved that this cannot be a BPP algorithm for any $q$... Any hint please?


texts: How to represent zero as floating point number?

texts:
For the floating-point number, we have the form
$\pm d_0.d_1d_2···d_{P-1}\times\beta^E$

$\pm$ --------------------------- sign
$d_0.d_1d_2···d_{p-1}$ --------- significant
$\beta$ ---------------------------- base (int)
$0\le d_i\lt \beta$ are the significant digits
$P$ ---------------------------- precision (int)
specifies number of digits carried -> controls accuracy
$E$ ---------------------------- exponent (int)
$L\le E\le U$

$L$ -- lower
$U$ -- upper

For example, suppose $F(10,3,-10,10)$
$4.00\times10^5$ represents the number $400000$
But how are we going to represent $0$ in such case?
Are we going to give $0$ directly or $0.00\times10^0$?


texts: Studying parallel algorithms for CLRS, old edition Chapter 30.  Can some one explain with a simple example what is pointer jumping and how exactly it works ?


texts: Grammars and Parsing: Ambiguity in Sequences

texts:
BACKGROUND

I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches.

Given terminals:

"a": KEYWORD
"b": INTVAL
"c": DECVAL
"d": STRVAL

Given rules:

"E": VALUE <- INTVAL
"F": VALUE <- DECVAL
"G": VALUE <- STRVAL
"H": VALUES <- VALUE
"I": VALUES <- VALUES VALUE
"J": LINE <- KEYWORD VALUES

Not complicated, right? This specific subset of terminals and rules should be able to parse the following line:

KEYWORD DECVAL DECVAL DECVAL DECVAL

In other words, a keyword followed by one or more values should be a grammatically-correct line. DECVAL tokens should reduce to VALUE tokens, which are in turn aggregated into a series of VALUES, at which point the line reduces under rule "J".

PROBLEM

However, consider the following parse state, after the first two tokens have been shifted and the lookahead is the next DECVAL:

KEYWORD DECVAL | DECVAL

This is a shift-reduce conflict, because it could shift the lookahead DECVAL under rule "F" or reduce the DECVAL on top of the stack under the same rule ("F"). By default, most parsers will perform the shift--in which case the series will never reduce because there is a DECVAL too "deep" on the stack.

QUESTION

But how would you (for example) define a precedence in such a way as to indicate a specific rule should reduce when in conflict with itself? Is that even a good idea? Based on my own limited understanding, there should be a way to restructure the grammar rules, right? But it's not obvious to me what that is.


texts: Smarter recursion to compute #tilings of $m \times n$ board with $2 \times 1$ dominoes?

texts: So I was thinking about how to computationally (e.g., with recursion) obtain the number of tilings of an $m \times n$ board with $2 \times 1$ dominoes. If $m \leq n$, then we can use recursion on $n$ by keeping track of the which squares are filled in the $n$th column, which gives $2^m$ cases to keep track of for each value of $n$, with the cases related between $n-1$ and $n$ based on how the empty spaces in the $(n-1)$th column are filled with horizontal and vertical dominoes. I was wondering, are there any significant improvements known for this type of recursion? For example can we take advantage of symmetry somehow and e.g. only keep track of the lengths of the contiguous filled squares and contiguous empty squares? Or other improvements? If improvements are possible, does it change the asymptotics of the number of cases that need to be tracked?


texts: PAC Learnability of axis aligned rectangles

texts:
I came across a question while going through ' Understanding Machine Learning'  by Shai Ben-David.
For the class H of axis-aligned n-dimensional rectangles in R^n i.e H = {[a1, b1] × · · · × [an, bn] : ai, bi ∈ R}
Can a PAC-Learning algorithm be given for this class H, if yes what is it and how can it be proved that it satisfies the conditions for PAC Learnability?
Could someone please help me out with this?


texts:
I've been thinking for some time but can't figure a way out.
I have big bitarray i.e. 1000+ items of 10_000 bits strings, I'm searching them now linearly. (currently it is stored in one chunk of memory).

I'm looking for some better algorithm for searching/matching !

Do you have any idea ?

bitarray looks like this :

 0) 1011.... <= 10_000 bits
 1) 1100....
 2) 0010....
 3) ........
 ...........

now find index of "1100...." :

 find(1100....) = 1

50% of bits are 1, 50% are 0, always.

I could probably sort it by hamming distance, but will be time consuming! (and array grows dynamically, so i have to re-sort) and the search will still be slower if I search one by one (probably because python overhead).
Currently the search is binary op+, but as you expect doesn't scale well i.e.

#duplicate the search item to the size of array
si_dup = search_item * array_size
dist's = (array ^ si_dup).count_by_row(1s)
top_idx = dist's.argmin()

The bad thing is that this is parallelize-able (I can process it in chunks), but python is not multi-threaded :(.
Also can seem to find a DB which handle large binary-strings, that will be a way out for large sets, I think!

thanks, "locality sensitive hashing" was the key, I researched it a bit and that seem will be the solution for large bitarrays (LSH via BitSampling).
For small ones the current approach I think will be faster.


texts:
Suppose I have something like the following:

$f(x) = g(x) + O(x^n)$

And I apply a power $m$ to both sides

$f(x)^m = g(x)^m + \cdots + O(x^n)^m$

My question is whether the following is well formulated:

$O(x^n)^m = O(x^{nm})$

Thank you!


texts: Revert array shuffle faster than in O(n^2)

texts:
I want to reverse an array that was shuffled with the function

array<integer> shuffle(arr: array<integer>, f: (integer) -> integer) {
    for (i: integer = 0; i < arr.length; i++) swap(arr[i], arr[f(i)]);
    return arr;
}

The array passed to this function is [0, 1, 2, 3, ... n-1] and function f for any i returns a value that is less or equal to i. I have an array returned by the function and I want to restore the results of f(i) for each iteration. What I do currently is:

array<integer> deshuffle(arr: array<integer>) {
    array<integer> result = [];
    for (i : integer = arr.length - 1; i > 0; i++) {
        index: integer = -1;
        for (j: integer = 0; j < i + 1; j++) {
            if (arr[j] == i) {
                index = j;
                break;
            }
        }
        result.push(index);
        swap(arr[i], arr[index]);
    }
}

Here I rely on the fact that the last member of the array can only be shuffled during the last iteration, which means I can find it, push the index and reswap it back and repeat it recursively (this is kinda like the insertion sort if I remember the name correctly). But the trouble is that this code is slow (O($n^{2}$)). Is there any way to do it faster?


texts: Is a DTM with k-tapes not the same thing as a NDTM with k-branches?

texts:
In the definition of a complexity class like P, where they reference Deterministic Turing machines (DTMs), I don't see any restriction on # of tapes these DTMs are allowed to use.

If a language L is in P do all its words have to be decidable in polynomial time by a 1-tape, 2-tape,....k-tape Turing machine in polynomial time?


texts: Can the same machine word sometimes be data and sometimes be code?

texts: I have a question about machine words. We have data and a code segment in the memory which is addressed. If we take a word from it and let's say it is a code (instruction), and another one is some data. Can we have a situation that some word is sometimes code and sometimes data?


texts: checking configuration history of Turing machine using PDA

texts:
I am trying to understand the technique of using configuration history in proofs.
To prove that:
$\{<M>|M\,\,\,is\,\,\,a\,\,\,TM\,\,\,and\,\,\,L(M)=\sum^* \}\notin RE$
given $<M,w>$ we have built a Turing machine that accepts all words except M accepting configuration on w. (and then simple reduction)
To prove that:
$\{<P>|P is\,\,\, a\,\,\, PDA\,\,\, and\,\,\, L(P)=\sum^*\}\notin RE$
we showed the same proof, only that we built a PDA that accepts all the words except the accepting configuration of M on w.
Does PDA's ability to determine whether input is an accepting configuration of M on w actually means that I can simulate M's run on w with a PDA? Or testing whether configuration is an accepting configuration is different from a simulation


texts: How can an algorithm have exponential space complexity but polynomial time complexity?

texts:
For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback problems". It is said that it runs in polynomial time but uses exponential space in a dictionary.

insert F_q into Q and into D;
while Q is not empty do
  remove any set F from Q;
  output F;
  for each uG-successor F′ of F do
    if F′ is not contained in D
      insert F′ into D and Q;
    fi
  od
od

How can this be? Does an exponential number of insert operations to the dictionary not inevitably imply exponential time?


texts:
There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll incur an operating cost of $N(i)$ if you run the business out of NY; you'll incur an operating cost of $S(i)$ if you run the business out of SF. There is a moving cost $M$ if you decide to switch offices. The goal is to minimize total cost. According to the solutions, a DP solution would look like this:

$$
OPT(i, N) = N(i) + \min(OPT(i-1, N), OPT(i-1, S) + M), \\
OPT(i, S) = S(i) + \min(OPT(i-1, S), OPT(i-1, N) + M).
$$

I'm trying to figure out how one can use recursion as opposed to DP to solve this solution. My understanding is that recursion works from top to bottom and DP works bottom up. I'm just having trouble actually figuring out a viable top to bottom recursive algorithm would look like in this case.


texts:
I have a list of millions of pairs of strings, and I want to join all of the pairs that have matching members into lists without duplicates.

Example input:

[["A", "B"],
 ["A", "D"],
 ["M", "Q"],
 ["A", "F"],
 ["D", "E"],
 ["Q", "Z"]]

Example output:

[["A", "B", "D", "E", "F"],
 ["M", Q", "Z"]]

Does anyone know of an efficient algorithm for this?  I'm somewhat constrained by memory.  Anything that would square the memory from the input would not be an option.


texts:
I'm reading about the prize collecting steiner tree problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in  The Design of Approximation Algorithms  by Williamson and Shmoys). I don't understand the second line in the proof for Lemma 5.16: .

It seems to me that $V-V(T)$ is a much larger set than $U$. So, how can the total penalty for this set be upper bounded by the total penalty of a set that is much smaller?


texts:
From Counterexample-Guided Quantifier Instantiation for Synthesis in SMT:

  a $\Sigma$-theory $T$ is satisfaction complete with respect to $L$ if every $T$-satisfiable formula of $L$ is $T$-valid....
  Most theories used in SMT (in particular, all theories of a specific structure such various theories of the integers, reals, strings, algebraic datatypes, bit vectors, and so on) are satisfaction complete with respect to the class of closed first-order $\Sigma$-formulas. Other theories, such as the theory of arrays, are satisfaction complete only with respect to considerably more restricted classes of formulas.

Are there resources on satisfaction complete theories? For example, a resource to learn about the restrictions that the authors mention are needed to make the theory of arrays satisfaction complete?


texts:
I need to find a method to sort an array in $O(n)$ time complexity.
I saw this link,
however I'm not sure how to apply it to the elements I need.

Input: an array $A$ of length $n$, containing values from $1$ to $n^2$
Output: a sorted array $A$

Can someone explain in pseudocode or in words how to do this?


texts:
I struggle with few definitions in knowledge representation and seek credible help to distinguish between them. I have been searching on wikipedia and many websites for the difference between ontologies and semantic networks (not to be confused with semantic web). While the wikipedia page on semantic network never refer to ontologies, they seem extremely similar and have similar application in CS.

My guess is that semantic network are a type of ontology adapted for research on AI. However, I don't know the difference between both. So my question is simply:

Are semantic networks ontologies? If so, are they synonym? or what are the distinctions?


texts: Proving Infinite Turing Machine Language (with finite subset) is Recursively Enumerable

texts:
I'm trying to answer this question:

Let $S$ be the strings $\langle P \rangle$ accepted by the Turing Machine $P$ with input alphabet $\{a,b\}$, where $P$ accepts an infinite number of strings beginning with $a$ and a finite number of strings beginning with $b$.

Is $P$ RE?

Is $P$ co-RE?


texts: How can we show that the term $\Omega = (\lambda x.x\ x)\ (\lambda x.x\ x)$ does not have a normal form? Building on this, what is an example term different than Omega that is not normalizing (meaning a term that every reduction sequence starting from it is infinite)?


texts: Algorithm for breaking a graph into sub-graphs based on an attribute

texts:
I am a biologist doing some computational work. I encountered a problem and need some help since I don't have much algorithmic background.

The problem:
Assume we have a non-directed, weighted graph, in which every node has some categorical attribute, e.g. color. I want to break the graph into sub-graphs in which there is at most one node of each color. Decisions should be made by trying to preserve the strongest connections (edges with highest weights). For example, let's look at the graph below (I didn't include weights as this would be hard to see):

In this case, I would like to break the graph into two sub-graphs (assuming that this is what the weights indicate):

Two notes (I don't know if they matter though):

The maximal number of colors is known in advance
After the graph was broken, I don't really care about the topology anymore - I just want to know which nodes ended up together.

My questions:
My first question is: does this look familiar to you? Has this problem been solved before? Maybe it's a variant of something every CS student learns? If so, can you please refer me to relevant information/literature?
If not, Then I'd like some help on how to approach this. Can you give some ideas on how to start developing and algorithm that can solve this type of problem?
Any other advice would be useful. Thank you!


texts: Joint Kolmogorov complexity of elegant programs

texts: If $a$ and $b$ are different elegant programs (minimal program for some output), is their joint Kolmogorov complexity the sum of their individual complexities, i.e. $K(a,b) = K(a) + K(b)$?


texts: How is a type system related to a progam?

texts:
In another question about Lambda Calculus, Andrej Bauer made the comment:

  Lambda calculi of various forms are formal systems. They consist of
  abstract syntax (for terms and for types, if present), judgments
  (typing judgments and equations), and rules of inference. They are not
  programming languages (unless we prescribe operational semantics) and
  neither is it the case that a type system equals a program that checks
  types. So I think this whole question is a bit misdirected, still. Of
  course, an important aspect of a type system is how to implement it on
  a computer, which brings in questions about algorithms, etc. But a
  priori, the type system has none of that.

I understand most of this, but I cannot wrap a logical understanding around:

  neither is it the case that a type system equals a program that checks types.

My understanding of a type system is that it is a set of rules in a formal system used to determine if a type is valid in a context and that those rules, via implementation, are used to establish the validity of a use of a type in a context in a programming language.

However the statement has me thinking there is no connection, or that there is more meaning to the statement but I don't see the details to separate a type system from a program or make a logical connection between the two so that the statement makes sense.

What is the relation between a type system and a program?


texts: How to 'memoize' this recursive solution?

texts:
I was doing this problem:

A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).

Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.

    Examples:
    Input: sx = 1, sy = 1, tx = 3, ty = 5
    Output: True
    Explanation:
    One series of moves that transforms the starting point to the target is:
    (1, 1) -> (1, 2)
    (1, 2) -> (3, 2)
    (3, 2) -> (3, 5)

    Input: sx = 1, sy = 1, tx = 2, ty = 2
    Output: False

    Input: sx = 1, sy = 1, tx = 1, ty = 1
    Output: True

    Note:

    sx, sy, tx, ty will all be integers in the range [1, 10^9].

I know the solution where you split it up into the ty-tx case, or tx-ty case, and solve it recursively, but I was wondering if there is a DP solution to this. Here is my recursive solution:

public boolean reachingPoints(int sx, int sy, int tx, int ty) {
    return help(sx,sy,tx,ty);
}

public boolean help(int sx, int sy, int tx, int ty){
    if(sx==tx && sy == ty){
        return true;
    }
    if(sx>tx || sy>ty){
        return false;
    }
    if(sx==tx){
        if(ty-sy%sx==0){
            return true;
        }
    }
    if(ty==sy){
        if(tx-sx%sy==0){
            return true;
        }
    }
    return(help(sx, sy, tx%ty, ty) || help(sx, sy+sx, tx, ty));
}

How would I put this into an array? I have trouble in the memoization part of DP, and I cannot figure this one out.

Any help would greatly be appreciated.

Thank you!


texts: Regular Expressions. Reversal of concatenated strings verification

texts:
What is the significance of reversing string $v$ in the following? Can't the string $v$ contain exactly what is in the string $v^R$, since you are just choosing from the alphabet $\Sigma^*$? I don't fully comprehend this question.

  Consider the language
  $$L = \{uabcv\mid u,v\in\Sigma^*\}$$
  over the alphabet $\Sigma = \{a,b,c\}$.  Is it true that reversal of $L$ is the set
  $$L_2 = \{ucba(v^R)\mid u,v\in\Sigma^*\}\,?$$
  (Please note that the parentheses are used only to clarify that it is only the string $v$ that is reversed.)

Any help is appreciated.


texts: How to approach analysis of randomized algorithm

texts:
Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any integer between $1$ and $n$ has equal probability. A simple process using this information is to loop for some fixed number of iterations $M$ that, for ease, is a multiple of $n$, and do the following:

Randomly obtain some constant $k \leq n$ number of integers from $U$ and place them into a set $V$
For $i^* = \arg \min V$, do update $C(i^*) \leftarrow C(i^*) + 1$

Ultimately, I want to be able to investigate the quantity $P\left( | C(i) - \frac{1}{n}\sum_{j=1}^n C(j) | \leq \epsilon \right)$ for any $i$. The question I have is if this simple algorithm allows, in probability, for the values of $C(i)$ to remain close to their average values regardless of how many iterations we do. This probability is obviously of a form where one could take advantage of say Hoeffding's inequality but I am not quite sure how to make use of the algorithm structure to get to that point.

I am not very well versed in randomized algorithms and so any insight into how to approach the analysis of such a simple algorithm would be insightful.


texts: Finding Statistical Signifigance for a Classifier

texts:
I recently did work in the area of machine learning for one of my jobs and was able to build a classifier which evaluated to an F score of 85%. I also have access to correctly and incorrectly classified instances. My boss would like to make sure my classifier is good and and test it for statistical significance. I'm not quite sure what he means by this. I have taken a course in statistics quite some time ago where I did hypothesis testing and stuff with confidence intervals. Do you think that's what he means or does he want me to compare it with other algorithms? I don't want to say what kind of data set I am working with but it's comparable to something such as predicting spam or ham for email messages.

Any help or guidance on this question would be greatly appreciated. I am pretty new to the area of computer science research. But am I right in saying that statistics are used quite a lot to evaluate these types of things?

Thank you!


texts: Show that approximation ratio for a convex hull algorithm is $\pi/2$

texts:
Facts: n points in the plane, each has one of k colors, all k colors are represented.

Problem: You wish to select k points, one of each color, such that the perimeter of the convex hull is as small as possible.

Greedy algorithm: For each point p, for each color c not equal to p, select the point of color c closest to p. In the end, choose the point set that has a convex hull with the smallest diameter (diameter is the distance between the two points furthest apart.)

Why is the approximation ratio $\pi/2$?

This was an exercise on my graduate level algorithms exam. We were only given a few lines to answer so it should be simple enough, but I do not know where to start.


texts: Nash Equilibrium in Tree of Bounded Degree

texts:
I have an exercise which I can't solve.

Exercise. Consider a game where the players have $2$ pure strategies each and assume that the graph $G$ is a tree with maximum degree $3$. Give a polynomial time algorithm to decide if such a game has a pure Nash equilibrium.

The idea seems pretty obvious, every vertex of the tree and corresponding neighbouring vertices represent a "mini" game  which can be represent in normal form with size at most $2^4$. This "mini" game can decided efficiently in polynomial time.

The problem is we have $n$ such a neighbouring areas (as a number of players), therefore we need somehow iteratively going over every area and decide where we have equilibrium and if not going back to the previous neighbouring areas change actions and check the existence. On the worst case it is going to take $2^{4n}$.

But how to decide it in polynomial time?


texts: For every $L \subseteq \{a\}^*$ we have $L^*$ is regular

texts:
I want to prove that

  for every language $L\subseteq \{a\}^*$, the laguage $L^*$ is regular.

every element of $\{a\}^*$ is equivalent to a natural number based on its length, and also every language $L$ is equivalent to a subset of natural number. after that base on lemma that says

  Let $S$ be an infinite subset of $N$ and $ d = gcd(S)$, there exists a
  finite subset $U$ of $S$ such that $d = gcd(U)$

I tried to prove the problem, first I claim that for every subset of natural number like $X$ that $d_x = gcd(X)$ there exist a number $p$ such that for every number $y$ greater than $p$ that is multiples of $d_x$ we can write

$y = \sum_{x \in X, t_x\geq0} t_x x$

so now we can build $DFA$ for $gcd(L)^*$ because $L$ contains a finite subset like $U$ such that $gcd(L) = gcd(U)$ so for every $w$ with length larger than $p$ languages $U^*$ and $L^*$ are behave the same and for words with length smaller than $w$ there is finite difference and also there is finite difference between $U^*$ and $gcd(U)^*$ because for every word with length greater than $p$ they also behave the same. so we can build $DFA$ for $L^*$ so it's Regular.

I think there are some holes in my proof. I am not sure about the claim and about the correctness.


texts: How to get a piece of the Pie? Theoretical Plate Stacking Problem

texts:
This is just a theoretical problem that I found in the wild and want to know your solution.
A stack of plates is made between you a cousin and a few others.
Every  (4 to 7) many random hours the plate on the top of the stack is given a slice of pie yet at this point you can instantly replace the pie with a new empty plate the goal of the exercise is having your plate on top the longest to get the most pie.
Cousin 1: Watches when you have placed your plate on top of the pile and then after a random interval of time about long enough to avoid being called out for being unfair lets say 45min-1h places his plate on top of yours.
Cousin 2: Watches when Cousin 1s plate is on top of his and then waits the same interval to avoid being unfair.
At this point you should notice that if you no longer post neither cousin will post.
myIdea:
The goal of the problem is to get more pie the most pie. And the only way that I see it as possible is to cheat more then your cousins.
IF you put down a plate then wait the minimum random interval after cousin 2 has placed his plate then you are likely only getting an equal share of time and probability of getting pie.
Cheating method: You do the same thing as both cousins but you time the the average time between cousins 1 and 2 placing their plates. Using this average of time you take half the time and the same standard deviation. I then post after cousin 2  in this time period which gives me an equal amount of pie as cousin 1 but more then cousin 2.
Is there any way to get more pie then each of the cousins?
• Can we do this with 1 plate?
•How can we do this with 2 plates?


texts: Recurrence which cannot be analyzed by master theorem

texts:
Given the following recursion,
$$T(n)=T(\frac{n}{2})+ aT(\frac{n}{4})+n^2, $$
How can I find the minimal value for $a$ such that ${T(n)=ω(n^2)}$?

I tried to do it by tree recursion but  I did not succeed to prove it by this method.


texts: Bin packing first-fit problem in $O(n \log n)$ time

texts:
Suppose we have $n$ objects with weights $w_i \in (0,1]$ and we must
  insert them into bins with the constraint that every bin must contain
  objects which weight less than $1 \, kg$.

  The first-fit algorithm must: examine the objects with the order
  they're given $(w_1, w_2, \dots , w_n)$ and insert them into the bins,
  satisfying the above constraint. It must run in $O(n \log n)$ time,
  returning the number of bins which were used and which objects were
  inserted in each bin.

I've constructed an algorithm, using Hash Tables, where the objects' numbers are the keys and the bins' numbers are the values and it basically does this:

for(int i = 0; i < n; i++){
    sum = sum + w[i];

    if(sum < noOfBins){
        BinContent.put(i + 1, noOfBins);
    }

    else {
        noOfBins++;
        BinContent.put(i + 1, noOfBins);
    }

and then it prints noOfBins and BinContent, but I believe this algorithm is $O(n)$ and the proper way would be to use Binary Trees instead of Hash Tables.

Is the complexity of the given algorithm $O(n)$? If so, could you give me a hint on how to achieve $O(n \log n)$ time complexity?


texts: In principle, what is the relation between Artifical Intelligence and Turing machine?

texts:
I am working on my cs project about AI & Turing machines, so i know that Artifical Intelligence is meant to implement different algorithms into the machine {the computer} to solve a problem or a set of problems together and i am getting AI as: (the machine is 'programmed' on a certain algorithms to solve problems or to show intelligent behavior when solving a specific problem).

  Artifical Intelligence is usually defined as the science of making computers do things that require intelligence when done by humans.

On the other hand, Turing machine just manipulates data of {0 & 1} on a tape according to a table of rules to solve a problem {calculate the input}.

  A Turing machine is an abstract machine that manipulates symbols on a strip of tape according to a table of rules.

So, generally speaking both AI and Turing machines are meant to compute the input and transfer it to a right answer {output} so here is what iam confused about :

What a formal defination would relate both of them ?
Can i say that both algorithms of AI and a table of rules of a
Turing machine are the same ?
Can i also say that AI is about choosing the best solution between
different solutions to the input and turing machine just
shows a solution of the input ?


texts: Irregularity of L = {a^i b^(j+3)| i!=j }

texts: I have a question to find out that $L = \{a^i b^{j+3}\mid i\ne j \}$ is regular or not. I know that it is not regular. I tried with pumping lemma but I am finding just a specific number of $v$'s in $u v^i w$ that not satisfies the language condition, but not ALL $v$'s. What are the best choices for $i$ and $j$ to prove with pumping lemma that this is not a regular language?


texts: Generating number of possibilites of popping two stacks to two other stacks

texts:
Context: I'm working on this problem:

  There are two stacks here:

A: 1,2,3,4 <- Stack Top
  B: 5,6,7,8

  A and B will pop out to other two stacks: C and D. For example:

 pop(A),push(C),pop(B),push(D).

  If an item have been popped out , it must be pushed to C or D immediately.

The goal is to enumerate all possible stack contents of C and D after moving all elements.

More elaborately, the problem is this: If you have two source stacks with $n$ unique elements (all are unique, not just per stack) and two destination stacks and you pop everything off each source stack to each destination stack, generate all unique destination stacks - call this $S$.

The stack part is irrelevant, mostly, other than it enforces a partial order on the result. If we have two source stacks and one destination stack, this is the same as generating all permutations without repetitions for a set of $2N$ elements with $N$ 'A' elements and $N$ 'B' elements. Call this $O$.

Thus

$\qquad \displaystyle |O| = (2n)!/(n!)^2$

Now observe all possible bit sequences of length 2n (bit 0 representing popping source stack A/B and bit 1 pushing to destination stack C/D), call this B. |B|=22n. We can surely generate B and check if it has the correct number of pops from each destination stack to generate |S|. It's a little faster to recursively generate these to ensure their validity. It's even faster still to generate B and O and then simulate, but it still has the issue of needing to check for duplicates.

My question

Is there a more efficient way to generate these?

Through simulation I found the result follows this sequence which is related to Delannoy Numbers, which I know very little about if this suggests anything.

Here is my Python code

def all_subsets(list):
    if len(list)==0:
        return [set()]
    subsets = all_subsets(list[1:])

    return [subset.union(set([list[0]])) for subset in subsets] + subsets

def result_sequences(perms):
    for perm in perms:
        whole_s = range(len(perm))
        whole_set = set(whole_s)
        for send_to_c in all_subsets(whole_s):
            send_to_d = whole_set-set(send_to_c)
            yield [perm,send_to_c,send_to_d]

n = 4
perms_ = list(unique_permutations([n,n],['a','b'])) # number of unique sequences
result = list(result_sequences(perms_))


texts: Analysis expected depth of a binary search tree given random values?

texts:
I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys in such order in $T$, what's the expected depth/height of this tree?

My attempt is the following, suppose $x_1$ has been assigned as root, I define a random variable $L$ as

$$
L = L(x_2,\ldots,x_k | x_1) = \# \left\{x_i : x_i < x_1 ,2 \leq i \leq k\right\} =
\sum_{j=2}^k u(x_1 - x_j)
$$

This function $L$ models how many elements would go in the left subtree rooted at $x_1$, here $u(x)$ is defined as

$$
u(x) = \begin{cases}
1 & x > 0 \\
0 & otherwise
\end{cases},
$$

we also have

$$
R = k - 1 -L
$$

the number of elements at the right of $x_1$. Now the expected value for $L$ is

$$
\bar{L} = \int_{[a,b]^{k-1}} L(x_2,\ldots,x_k | x_1) p(x_2,\ldots, x_k) dx_2 \ldots dx_k = \\
\int_{[a,b]^{k-1}} \sum_{j=2}^k u(x_1 - x_j) p(x_2,\ldots, x_k) dx_2 \ldots dx_k = \\
\int_{[a,b]^{k-1}} \sum_{j=2}^k u(x_1 - x_j) p(x_j) \prod_{l=2,l\neq j}^{k}p(x_l) dx_2 \ldots dx_k = \sum_{j=2}^k \int_{[a,b]} u(x_1 - x_j) p(x_j)
dx_j = \\
(k-1) \frac{x_1-a}{b-a}
$$

We then have

$$\bar{L} = (k-1) \frac{x_1-a}{b-a} = f(x_1)$$

If we now compute the expected value for $f$ we will get the on average how many elements will go on the left subtree rooted at $x_1$, regardless of $x_1$. This is easier to compute and we get a value I would expect indeed

$$
\bar{f} = \frac{k-1}{2}
$$

We know now that given random values they will be equally distributed, we can write down the recurrence

$$
h(k) = 1 + h \left(\frac{k-1}{2} \right)
$$

which models the average height for $k$ random elements, clearly $h$ is monotonic and we can write the inequality

$$
h(k) \leq 1 + h(k/2),
$$

and therefore we end up with the solution

$$
h(k) = O(\log k)
$$

Assuming the analysis is correct the questions are:

I'm only analyzing with random inputs, what about if now I'll do deletion, how would the probabilistic model change? By deletion mean pick $y_1,\ldots, y_m \in \left\{x_1,\ldots x_k \right\}$ random and delete those, I expect a similar result, but I don't have a clue on the probabilistic model.
Is there an alternative proof maybe more combinatorial?

Thank you


texts: Worst-case expected running time for Randomized Permutation Algorithm

texts:
I have an algorithm which, when given a positive integer N, generates a permutation of the first N integers (from 1 to N) using a method called randInt(x,y). The method randInt(x,y) will generate a random integer between the numbers x and y, provided they are positive integers and y >= x.

The algorithm is given by the following pseudo-code:

1.  if (N <= 0) {
2.     return null
3.  } else {
4.     A := new int[] w/ size N and all cells initialized to 0
5.     a[0] := randInt(1,N)
6.     for (i := 1 to length(A)-1) do
7.        boolean rInA := True
8.        while (rInA) {
9.           rInA := False
10.          int r := randInt(1,N)
11.          for (j := 0 to (i-1)) do
12.             if (r = A[j]) {
13.                rInA := True
14.             }
15.          }
16.       }
17.       A[i] := r
18.    }
19. }
20. return A

My understanding of the algorithm is as follows:

The outermost for-loop will run N-1 times and for each of those iterations a random number is generated and then compared to all the previous cells of A that have been visited in previous iterations. If any of the those cells contain that randomly generated number then that number cannot be used and a new number is randomly generated (in the next iteration of that nested while-loop). This new randomly generated number is then, like before, compared to all the previously visited cells in A to check for duplication. This continues until randInt(x,y) generates a random number that is not already in the first i cells of A.

This leads me to believe that the Worst-case expected running time of the algorithm is something like:
$\sum_{i=1}^{N-1}(\alpha i)$

Now the $\alpha$ here represents the effect the while-loop has on the running time and is the point of uncertainty for me. I know that in the first iteration of the outermost for loop its unlikely that randInt will generate the one integer that A already contains (1/N I believe) so that inner-most for-loop is likely to only execute once. However, by the last iteration (of outer-most for-loop) the probability that randInt generates one of the N-1 integers already in A is $\frac{N-1}{N}$ so because of the while-loop its likely that the inner-most for-loop for that iteration (of the outer-most for-loop) will execute more like n times.

How can I use the probability introduced into the algorithm by randInt to calculate the algorithms run-time?


texts: Hoare-Logic: Requirements for imperfect data types

texts:
Theoretically, Hoare-Logic let's one prove the correctness of an algorithm, given pre- and post-condition.

However, as far as I've seen it so far, one idealizes his data-types to a mathematical set like $\mathbb{N}$ or $\mathbb{R}$.

So, even though the logic might be sound in Hoare-calculus, the discrepancies between the data types used and the data types modeled can still fail the result (e.g. Overflow for Integers).

Therefore, the question is:
Which additional conditions have to be met (after each step of the algorithm?) to accomodate for the imperfect data types actually used?


texts: Time complexity to find out the number of ways to parenthesize N matrices

texts:
I am trying to figure out the $time$ $complexity$ to find out the number of ways we can parenthesize $N$ $matrices$. I have approached this problem as, say if we have $N+1$ matrices then we can parenthesize them in $\dfrac{2N \choose N}{N+1}$ ways

For example, see the below image, here we have 3 matrices which we can represent in a tree and we have 2 nodes which we can arrange to form different unlabeled binary trees in $\dfrac{2N \choose N}{N+1}$ ways which in turn will give us the number of ways in which we can parenthesize these 3 matrices.

But the problem I am facing is that I am unable to figure out the time complexity which this method will take. Any help will be highly appreciated.


texts: Standard problem sets for metaheuristics

texts:
I'm wanting to dabble with metaheuristics and am interested to know what the "hello world" problem sets are.

In other words, what are the common problems (e.g Traveling Salesman, Vehicle Routing Problem, Maze Solving) to test various algorithms against in order to compare algorithm design?


texts: Given an algorithm, do worst case time complexity "class" vary with array and linked list?

texts:
My intuition says that I can make a sorting algorithm(may be a strange, not an useful), such that with array it have different worst case time complexity class and linked list(assuming time complexity of operation performed in linked list are same as conventionally used) with different complexity class.
But what about the sorting algorithms which are conventionally used(may be the algorithms in CLRS)?
I am assuming the implementation done on RAM model and by class I mean the set $\theta(f)$ with f as worst case running time of the algorithm


texts: 8 puzzle admissible heuristic that dominates Manhattan distance?

texts:
I have a modified 8 puzzle problem such that each transition's cost is associated with the number of the piece that is moved. So, for example, if piece "3" is moved, the move would cost 3 units.

I am trying to find an admissible heuristic that dominates the Manhattan distance, but am having trouble deriving one.

My thoughts:

Since the Manhattan distance gives us the distance of any tile from its end goal, wouldn't a heuristic that dominates the Manhattan distance not be admissible? For example, if a piece is 1 state away from its goal state, how can there be an admissible heuristic that is $>=$ 1 for that piece?


texts: what does it mean to extend an assignment?

texts:
For a constraint satisfaction problem, what does it mean for  an assignment x to extend an assignment  a?

Sorry if this is super trivial,  I did not find an answer

e.g here:  No Small Linear Program Approximates Vertex Cover Within a Factor 2 − $ \epsilon $  pg 16 x does not extend \alpha


texts:
I have a scheduling problem with the following specifications:

A single machine is used.
$n$ jobs $\mathbb{J} = \{J_1,...,J_n\}$ are available from the start $t = 0$.
Each job can be executed several times.
There is a cycle length $t = T_{max}$  and the scheduled jobs have to fit in $[0,T_{max}[$.
There are two types of constraints:

$J_i$ must be executed $m$ spaces of time after $J_j$.
$J_i$ must be executed after jobs $J \subset \mathbb{J}$ or $J_i$ mustn't be executed after jobs $J$.

The basic solution in $[0,T_{max}[$ satisfying the constraints, needs to satisfy the constraints when copied on to $[T_{max},2T_{max}[$, $[2T_{max},3T_{max}[$, $\ldots$. In particular, if $j_1 \ldots j_s$ is a solution (sequence of jobs satisfying constraints) with $j_i \in \mathbb{J}$, then $j_2 \ldots j_s j_1$, $j_3 \ldots j_s j_1 j_2 \ldots$ must also satisfy the constraints.

I want to find all possible schedules.
Is this problem solved? I would appreciate any pointers to the literature describing a solution or approximations to it.


texts: KMP Algorithm, Pratt's Minimisation/optimization of Knuth's original DFA based algorithm

texts:
The Original Knuth's Algorithm is based on DFA and it depends on the alphabet size. And Then, Pratt optimised it to be independent of Alphabet Size.

But, All the textbooks directly give the final Pratt Algorithm.  Below is the code ( the code is not really needed to answer the question) which is more or less similar to original Knuth's Algorithm ( full code) , And it builds the DFA.

My Question is, How can we (idea behind) arrive at the final current version ( Pratt optimization) from below DFA version ?

Also, Is it called minimization of DFA, But DFA minimization can be applied to a specific alphabet(regular language), Here it applies to all alphabets ?

public KMP(char[] pattern, int R) {
    // build DFA from pattern, R is the language length
    int M = pattern.length;
    dfa = new int[R][M];
    dfa[pattern[0]][0] = 1;
    for (int X = 0, j = 1; j < M; j++) {
        for (int c = 0; c < R; c++)
            dfa[c][j] = dfa[c][X];     // Copy mismatch cases.
        dfa[pattern[j]][j] = j+1;      // Set match case.
        X = dfa[pattern[j]][X];        // Update restart state.
    }
}


texts: Whether the given schedule is view serializable or not?

texts:
It is asked for whether the schedule is serializable or not?
This schedule is clearly not conflict serializable because of cycle in precedence graph.. but it could be view serializable because there is a blind write in transaction T3. What i did-
For View Equivalence:
(1) If transaction Ti reads initial value of any data item X in one schedule it must do the same in all the equivalent schedules.
(2) If transaction Ti writes the final value of any data item X in one schedule, it must do the same in all the view-equivalent schedules.
(3) If transaction Ti reads data item X written by transaction Tj, it must do the same in all the view equivalent schedules.
I am not getting which one of these three conditions is getting violated if i try to make schedule (given in attached pic) view equivalent to a serial schedule T1-T3-T2. Please help.


texts: How does a regular language satisfies the second condition of the pumping lemma

texts:
I'm a little bit confused about the second condition of the pumping lemma which are:

$|y|\geq1$
$|xy|\leq p$
$\forall i \geq 0 : x y^i z \in L$

I don't understand why the length of substrings $xy$ has to be less than the pumping length? Considering the example below:

Suppose we have a language $L = \{ w | w ∈ 1^*0+1^*\}$ and a string $s \in L$ which $L$ is a regular language.
Let the string $s = 101$ and $S$ can be split into three substring $xyz$ where $y$ can be pumped.

Therefore:

$x = \text{'1'}$ $y=\text{'0'}$ and $z=\text{'1'}$. It seems that substring $|xy|$ is somehow larger than the pumping length $p$ itself (in this case: $p=1$ since there's only one $0$), Therefore $|xy| > p$, a contradiction ! Does this mean that the language $L$ in this case is not regular ?

Or did I misunderstood something.


texts:
I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT are both in Karp's list of 21 NP-Complete problems and this is the reduction that he did [1].

PARTITION: Given ($c_1,c_2,\dots,c_n)\in\mathbb{Z}^n$, does there exist $S\subseteq\{1,2,\dots,n\}$ such that $$\sum_{i\in S}c_i=\sum_{j \not\in S}c_j$$

MAX-CUT: Given a weighted graph $G=(V,E)$ with weight function $w:E\rightarrow\mathbb{Z}$ and a target weight $W\in\mathbb{Z}^+$, does there exists $S\subseteq V$ such that $$\sum_{(u,v)\in E\::\:u\in S,\,v \not\in S}w((u,v))\geq W$$

After spending a lot of time trying to construct a reduction to prove PARTITION $\leq_p$ MAX-CUT myself, I eventually gave up and looked at Karp's paper. The problem I could not manage to solve is how you encode the equality constraint of PARTITION in a MAX-CUT instance which only has one inequality constraint. The reduction that Karp gives (which I would not have been able to come up with) is as follows:

Given a PARTITION instance $(c_1,c_2,\dots,c_n)$, construct a MAX-CUT instance $(G=(V,E),\,w,\,W)$ such that:
 $$V=\{1,2,\dots,n\}$$
 $$E=\{(u,v) \: : \: i,j\in V,\, u\neq v\}$$
 $$\forall (u,v) \in E,\,w((u,v))=c_ic_j$$
 $$W=\lceil \frac{1}{4} \sum_{i=1}^{n}c_i^2\rceil$$

I am having trouble proving the correctness of this reduction (the paper does not seem to give any justification). I can kind of appreciate the need to be squaring values - is my intuition correct that this is to account for needing to the equality constraint with an inequality constraint?

I have tried using the Cauchy–Schwarz inequality to prove this with no luck. Similarly, I have tried to relate this to the variance/covariance of two partition sets, but I'm not sure if this is helping me understand why this reduction works.

A proof plus any intuition of how one might have arrived at this reduction would be greatly appreciated.

[1] Richard M. Karp (1972). "Reducibility Among Combinatorial Problems". In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. (pdf)


texts: What is the difference between Big O and asymptotic notation?

texts: Are the two interchangeable or is there a difference?


texts:
Assume that $A$ is the set of objects  such that each object $x_i \in A$ has value $w_i$. We wish to pack these objects into group, each pack containing at least $k$ objects. Our goal is to minimize the maximum difference between the maximum and minimum value of each packs.
in other words, our goal is to minimize $L$ with the constraint that all packs should have more than $k$ object in them.

$$L = \max_{i \in \mathrm{packs}}  \left\{\max_{j \in \mathrm{pack}(i)}w_j - \min_{k \in \mathrm{pack}(i)}w_k \right\}.$$

For example for the following packing, $L$ is $\max{(30-20, 120 - 100)} = 20$.
$$[20, 30] \;\; [100,110,120]$$

I was wondering if there is a greedy algorithm that can do the job.


texts:
Is there a good (perfect) hashing algorithm for the following problem?

We have $n \ll m$ (say $n=150$ and $m=5\times 10^{12}$) and we want a hash table  to store integers up to $m$ whose prime factors are all smaller than $n$.


texts: Are there things an analog computer can do that digital computing cannot do?

texts:
The crux of the difference between analog and digital computing is the number of bits of precision available, right? Now, I know that in the Turing machine, numbers can be stored with any degree of precision since the storage medium is an infinite tape.

But in the real world, physical quantities such as energy or position are not incremented in discrete chunks, as they are in their binary. Instead, their exact values can vary continuously as they do in analog circuits.

On that basis then, are there things which, fundamentally, an analog computer can do that digital computing cannot do?


texts:
Let $n,m$ be a positive integer with $m\ge 2n$. In the set $M=\{1,2,\dots,m\}$, some elements are black and others are white. Given $2n$ nonempty subsets of $M$, the task is to determine whether there exists a subset $T\subseteq M$ consisting of $n$ black and $n$ white elements such that each of the $2n$ subsets has a nonempty intersection with $T$. Can this be done in polynomial time?
Without the color constraint, this is very similar to the hitting set problem. Choosing a subset $T$ of size $2n$ without the color constraint is easy, by choosing one representative from each of the $2n$ subsets and, if the union of these representatives has size less than $2n$, fill in with arbitrary remaining elements of $M$. But having $n$ black and $n$ white elements is not always possible, for instance if there are not enough elements of one color.


texts:
Is it possible

$NP\subseteq P^{TFNP}$ holds or
$NP\subseteq P^{UP}$ holds

without the polynomial hierarchy collapsing?

Is there problems in

one of each of the classes from $NP$, $P^{UP}$ and $P^{TFNP}$ but not in other two?
two of each pair of the classes from $NP$, $P^{UP}$ and $P^{TFNP}$ but not in last?


texts: Proof that $P$ is robust against switching between polynomially equivalent encodings

texts:
Lemma 34.1
  Let $Q$ be an abstract decision problem on an instance set $I$, and let $e_1$ and $e_2$ be polynomially related encodings on $I$. Then, $e_1(Q)\in \mathrm{P}$ if and only if $e_2(Q)\in\mathrm{P}$.

  Proof: We need only prove the forward direction, since the backward direction is symmetric. Suppose, therefore, that $e_1(Q)$ can be solved in time $O(n^K)$ for some constant $k$. Further, suppose that for any problem instance $i$, the encoding $e_1(i)$ can be computed from the encoding $e_2(i)$ in time $O(n^c)$ for some constant $c$, where $n=|e_2(i)|$. To solve problem $e_2(Q)$, on input $e_2(i)$, we first compute $e_1(i)$ and then run the algorithm for $e_1(Q)$ on $e_1(i)$. How long does this take? Converting encodings takes time $O(n^c)$ and therefore $|e_1(i)|=O(n^c)$, since the output of a serial computer cannot be longer than its running time. Solving the problem on $e_1(i)$ takes time $O(|e_1(i)|^k) = O(n^{ck})$, which is polynomial since both $c$ and $k$ are constants. $\blacksquare$

I have some questions to the proof:

Why does it only consider $e(i)$? As I know, $Q$ is binary relation on the set  of instances $I$ and the set of solution so if we say that $e(Q)$ and it should be $e(i,s)$.

Let $Q$ be an abstract decision problem: What is an instance of NP complete problem?

The proof only shows the forward direction.

Step 1. suppose that $e_1(Q)$ can be solved in polynomial time

Step 2. convert $e_2(i)$ into $e_1(i)$ to prove $e_2(Q)$ can be solved in polynomial time.

If we prove the backward direction, then we can confirm $e_1(Q)$ to be solved in polynomial time as well, am I right?


texts: Piecewise linear approximation for set of points

texts:
If we have a set of points $A$ and a known algorithm $Bestfit(A)$ to find
the best-fit straight line-segment through $A$, what would be a good algorithm to construct piece-wise linear segments (with at most $k$ segments) to give a better approximate of the set of points and reduce the error $E$?


texts: Is the class of non-regular languages closed against Kleene star?

texts:
How to prove that if a language A is not regular then A* isn't regular either?

I have tried the usual methods with no result.


texts:
This question is motivated by my answer to another question in which I stated the fact that both Betweeness and Non-Betweeness problems are $NP$-complete. In the former problem there is a total order such that the betweeness constraint of each triple is enforced while in the later problem there is a total order such that the betweeness constraint of each triple is violated.

What is the complexity of the following 3SAT variants?:

3SAT_1={($\phi$): $\phi$ has an assignment that makes every clause false}

3SAT_2={($\phi$): $\phi$ has an assignment such that exactly half of the clauses are true and the other half is false}


texts: What are the examples of the easily computable "wild" permutations?

texts:
I am looking for the function $y=f(x)$ that would map the integer interval $[0,n)$ into itself $[0,n)$. The function must be bijective, so it is a permutation of n elements. It should "randomize" the input variable, ie.

for every $x_1$ and $x_2$ that are close $|x_1 - x_2| < 100$ the outputs of the function should differ very much $|f(x_1) - f(x_2)| > n/{100}$
changing any digit in the input should change most of digits in the output
Shannon's Confusion and diffusion: http://en.wikipedia.org/wiki/Confusion_and_diffusion
There should be very little or no fixed points (for every $x$: $f(x) \neq x$).

or any combination of the above conditions.

I don't need the inverse function. It should also be easy to compute from the closed form expression (a maximum of a few thousands simple computer operations like addition, multiplication, modulo etc.) for $n=10^{100}$.

I found some examples in Google:

Linear congruential generator. Equation:

$X_{n+1} = (aX_n + c) \mod m$

Wikipedia states that: "Provided that the offset $c$ is nonzero, the LCG will have a full period for all seed values if and only if:

$c$ and $m$ are relatively prime,
$a - 1$ is divisible by all prime factors of $m$,
$a - 1$ is a multiple of 4 if $m$ is a multiple of 4.

I've tried using another function $f(x) = (ax + c) \mod m$, because I wanted to get rid of the recursion, and as long as $m$ is prime and $a \ge 1$ I get the permutation. However the result is not that "wild" or "chaotic" as I expect it to be.

Minimal perfect hash function

The concept is similar to what I'm looking for, but if I understand correctly the computation of this kind of function is very complicated and time-consuming and it cannot be expressed in a closed form as a simple expression for $n=10^{100}$.

Substitution-permutation network

I am not sure how to apply S-boxes and P-boxes to the interval [0,n), but maybe it could be used.

The question is: Could you give me some examples of functions that satisfy the above conditions (or some pointers like the mathematical term for the object I am looking for)?


texts: What is the name of the data structure that is a tree on the backend but has a list like API?

texts:
I'm looking for the name of a data structure.  It is organized like a balanced tree.  The elements need not be comparable.  Instead of asking if the tree contains a thing (like you would with a collection of comparables), you can query for any k'th element in logarithmic time.  You can insert before or after any k'th element.  So the API is a bit like a list, except all operations are logarithmic.

I think "rope" might be similar but those seem to be restricted to strings only.  It could be thought of as a segment tree, where every leaf has a weight of 1, but instead of storing the weights in the leaves the entry itself is stored.

Edit: I think it could also be referred to as an "Order Statistic Tree" but without the comparison operations.


texts: Is there a O(log n)-time algorithm to find the maximum element of a circular shift of a sorted array?

texts:
Consider this problem: You are given an array $A$ (of distinct integers) of one out of the following four types:

Ascending (e.g., 1,2,4,6);
Descending (e.g., 6,4,2,1);
Ascending rotated (a non-trivial circular shift of an ascending array, e.g., 4,6,1,2);
Descending rotated (a non-trivial circular shift of an descending array, e.g., 4,2,1,6).

The task is to determine the type and the maximum element of $A$.

Since $A$ is "sorted", is there a $O(\log n)$-time approach or is the best possible time complexity $O(n)$, as suggested in the link?


texts:
I'm trying to predict the daily positivity or negativity of stock market value through Twitter.
I researched a lot about this topic and I found this article to start.
Basically, what I've done is get from yahoo finance the date relative to Down Jones and calculate if the day was positive or negative.

For the same date, get all the tweets that contain words like I'm, feel, makes me, in order by collect only the tweets that express a sentiment.

I have a list of words (positive and negative), without score, just words.
For every day analyzed, I create a Python dictionary which has as keys the words of the list and as value a score,calculated in the following way:

score of a word = num of times the word matches tweets in a day /
                  num of total matches of all words

In order to predict the stock market I train naive bayes algorithms as data, the python dictionary with words and relative score and as target 'pos' or 'neg' according to the finance data.

I collected one year of date (from 1-1-2010 to 31-12-2010).
The length of the list of words is 18540.
I'm working with Python 3.4, tweepy and scikit-learn

The classifier doesn't work well and since I'm a novice in this field, I would like ask you if there is something wrong in my procedure or if you have some suggestions to help me.

Any help is appreciated


texts: Do languages in $\mathsf{coRE} \setminus \mathsf{R}$ have Turing machines?

texts:
What can we say about languages in $\mathsf{coRE} \setminus \mathsf{R}$? Are there Turing machines for these languages?
I know that $\overline{HP} \in \mathsf{coRE}$ doesn't have a Turing machine, and also that all the language that do have Turing machines are in $\mathsf{RE}$, so is it true that for any language that is in $\mathsf{coRE} \setminus \mathsf{R}$ there's isn't a Turing machine? I wonder why is that so, can someone elaborate?


texts:
I need to prove that the following language is not regular

  $\{c^mb^na^n \mid n>0,m\geq0\}$

But I am not sure how to do that for this particular one. I vaguely understand pumping lemma, but every example I see is in the form

  $\{a^nb^n \mid n>0\}$

Or something similiar.  This does not help me with my problem, because I dont fully understand pumping lemma and am not sure how to do it for two variables that have no dependency on each other.  I know to take a length P from L, and I also need a string s>=P.
Which then becomes P=xyz, but it is this step that confuses me.


texts:
I'm trying to learn for my exam and had the following practice question:

Take a code with the following code words.

101100010111
110001001001
101110111011

Errors of how many bits can be corrected?

The answer i received was:

The hamming distance is: 4.

Therefore only single bit errors can be corrected.

How did they conclude that only single bit errors can be corrected just by looking at the hamming distance?


texts:
Must the states of a finite state machine be worked off sequentially or could you understand the different shaped parts of the key as input and the position of the pins as states?
If not all the input is right: failure state = stays locked
If all the input is right: end state = lock opens

I was inspired by this (German grammar-school) resource, where on page 7 are diagrams of a combination lock as a finite state machine.


texts:
I came across this question:

You are given a permutation cipher defined by the bijection t: N -> N where,

t(i) = i + 10, for i < 10,
t(i) = i - 10, for 10 <= i <= 20, and
t(i) = i, for i > 20.

Assume that the first index is 0, given a message m = 'HELLO WORLD AND THIS IS A SECRET MESSAGE', what is the ciphertext c?

Where the answer was the following:

D AND THISHELLO WORL IS A SECRET MESSAGE

but i don't get how. That's now what we get if the message is spelled out diagonally
down and up over a number of rows and then read off row-by-row.


texts: Is implication(function) more fundamental than lets say conjunction(product) in type theory?

texts: According to the answer at (How to define function type in AGDA) the function type is kind of a fundamental thing in Agda and needed for bootstrapping, hence end user can not define it like what they do for conjunction(product) type and has to be predefined at the language level. Does this mean that implication(function) type is more fundamental than types like product(conjunction) since function is used in defining those types?


texts: Is it possible to write a wait free leader election algorithm?

texts:
I want to understand if there exists an algorithm which is wait free and operates on non-shared memory, asynchronously.

Finally I want to know how to derive the consensus number of this algorithm.
Googling did not work.


texts: Show that a $\alpha$-approximation algorithm is not a ($\alpha-x$) approximation algorithm for $x > $0

texts:
Suppose you have a system that consists of $m$ slow machines and $k$ fast machines. The fast machines can perform twice as much work per unit time as the slow machines. Now you are given a set of n jobs; job $i$ takes time $t_i$ to process on a slow machine and time $\frac{1}{2} t_i$ to process on a fast machine. The goal is to minimize the makespan — the maximum, over all machines, of the total processing time of jobs assigned to that machine.

Algorithm: When each job arrives, we put it on the machine that currently ends the soonest(machine with smallest current load before the job is assigned). (Note that this determination involves taking into account the speeds of the machines.) This is a 3-approximation algorithm.

I want to find an example for which the algorithm is not a $(3 - x)$-approximation algorithm for any $x > 0$.

Condering that the makespan of the resulting algorithm is $T$, to do that I thought that, since the algorithm is a $(3-x)$-approximation if $T \leq (3-x)OPT$, I would just have to find an example for which $T > (3-x)OPT$. But I cannot seem to be able to find one, all the examples I find yield $T \leq (3-x)OPT$.

I just found a very basic example, where I have 4 jobs and 2 machines, one fast and one slow. The jobs: 4, 4, 1, 2

The algorithm would  first assign job 1 to the fast machine, then job 2 to the second machine, then jobs 3 and 4 to the fast machine. This yields a makespan $T$ of $4$.

The optimal makespan $OPT$ would be assigning jobs 1, 2 and 3 to the fast machine and job 4 to the slow machine, so $OPT = \frac{9}{4}$.

But then $4 < 9 (4\frac{9}{4})$

What am I doing wrong?


texts:
I am thinking of explaining the topic of Network flow to an audience of computer sciecne students, and I want to make it more enjoyable by giving some real life examples where a software Developer may find Network Flow useful.
I want to refrain from using standard problems like Baseball problem, marriage problem, edge disjoint.
I need Ideas for such problem which needs to be represented as a graph and then using Network flow we can find the solution.


texts: Karnaugh Map: does maximal overlap always produce simplest boolean expression?

texts:
Suppose I have a 4x4 Karnaugh map with a few cells that are don't cares, and there are two ways of producing 3 groups of 4 cells. One of these ways overlaps groupings more that the other. Is one way preferable over the other?
For example:
Is F = B'D' + AD' + CD' simpler than F = B'D' + AD' + A'C (since the first one reuses more symbols), or would one say they are equally simple?


texts: Does modern type theory include specifications and implementations?

texts:
Good programming practice distinguishes between specification (at the API level) and implementation. I would have thought that this same distinction would be found in type theory. Perhaps I just don't understand what I'm reading, but I don't see it.

Apologies if I'm completely off (and corrections appreciated), but it seems that in type theory one adds new computation/rewrite rules, which in effect are at the implementation level, i.e., they compute something. (They may be "declarative," but they are used for computation.) I don't see how one adds anything like a specification.


texts: Are floating-point numbers normalised by computers or humans?

texts: I keep seeing posts and articles about how to normalise a floating-point number, why that's done and how such a number is represented in binary. But no one seems to mention who/what the normalisation process is done by in the first place. Forgive me if it sounds like a really dumb question, I'm just a beginner, but are normalised forms of these numbers generated by a computer itself, or hard-coded into it by humans?


texts:
Recall A'= $\{x \mid \phi^A_x(x)$ halts and accepts $\}$

In this article, a proof that A' not computable in A is given:
http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Flood.pdf

He constructs the function f(x)= $\phi_x^A(x)$ +1 if x in A and 0 if x not in A

Shouldn't it be f(x)= $\phi_x^A(x)$ +1 if x in A' and 0 if x not in A'

since we need $\phi^A_x(x)$ to halt and output a number provided it actually can?

then f will be computable in A and we can then go on to prove that f $\neq$ $\phi^A_x$ for the witness x


texts: Is there an available feature model and code of a dynamic software product line (DSPL)?

texts:
Dynamic Software Product Lines (DSPLS) are software product lines (SPLs) where features can be bound and unbound during program execution time.

Is there a feature model and code available of an DSPL? I.e., where the model and the implementation is freely available for research purposes? I mean for regular SPLs there is the SPLOT website for models and there are several Fuji exmaples where the implementaiton code is downloadable.

I contacted one of the authors of a review paper on DSPLs:
Hallsteinsen, S., Hinchey, M., Park, S., & Schmid, K. (2008). Dynamic software product lines. Computer, 41(4), 93-95.

He answered me that he is not aware of any available DSPL! He said that some work is government funded or sponsored by companies and in both cases it is impossible to get anything, let alone code. However, the feature model and code excerpts that I am interested in can be easily anonymised.

Is it true that there is not a single DSPL where the model and some implementation code is availiable?

Are there any research groups I could contact in this regard? Groups that might have a DSPL feature model or implementation that might be available for research? The feature model and implementation code can be anonymized.

The reason for my question is that I am interested in analyzing DSPLs, but it seems impossible to get a DSPL anywhere; although, incidentally, there a numerous papers on DSPLs.


texts: Running the Double Tree Heuristic in a given graph - some slight confusion

texts:
I'm working on an exam question that asks me to run the Double-Tree Heuristic algorithm on the following graph:

This algorithm starts by finding a minimum cost spanning tree.

My solution:

Minimum spanning tree contains edges ec, cb, dc, da

Doubling these edges to find an Euler tour: a, d, c, b, c, e, c, d, a

Removing duplicate edges: a, d, c, b, e, a

Actual solution:

Minimum spanning tree contains edges ed, ec, cb, da

Doubling these edges to find the Euler tour: a d e c b c e d a

Removing duplicate edges: a d e c b a (cost: 51)

I want to know if I have used the algorithm correctly. Can there be more than 1 specific solution to this problem?


texts: Understanding depth-limited BFS time complexity

texts:
I'm trying to implement graph power calculation using BFS. According to Wikipedia, BFS with depth limit k will suffice (I'm using adjacency list representation, my graphs are sparse, so adjacency matrix power is not optimal).

Complexity of BFS is O(V+E), running it for every vertex is trivially O(V*(V+E)). I also have depth limit k here and Wikipedia claims (in the page linked above) that running BFS with this constraint for every vertex will be O(V*E). Why is that? In the worst case when every vertex is in the "range" of k from every other vertex I'll have to search the entire graph V times, after all.


texts: Delete edges (to make it oriented) preserving the strongly connected property

texts:
A directed graph is said to be oriented if for all edges (i, j), (j, i) is not an edge. In other words, the binary relation defined by the edges is asymmetric. Given a strongly connected directed graph, you have to find whether there exists a spanning oriented subgraph which is also strongly connected. In other words, if for some nodes i,j, both (i, j) and (j, i) are edged in the graph, you have to delete at least one of the two edges, preserving the strongly connected property of the graph. If there is no such subgraph, print “impossible” else print “possible”. If it is possible, print out the edges in any such subgraph, one per line, in any order.
Credits: A homework problem from my college curriculum
My approach: We can do a DFS and if there's both the path (i, j) & (j, i), one of them will be the tree edge and the other will either be a forward or a backward edge. If the forward edge, we can delete it, if not then we'll have to delete either the tree edge or the back edge. How do I figure out which one to delete?


texts: Is the graph symbol used in dask a general notation?

texts:
Dask is a flexible library for parallel computing in Python.

This piece of code define some simple functions.

def inc(x):
    return x + 1

def double(x):
    return x + 2

def add(x, y):
    return x + y

data = [1, 2, 3, 4, 5]

output = []
for x in data:
    a = inc(x)
    b = double(x)
    c = add(a, b)
    output.append(c)

total = sum(output)

this piece of code wraps the functions above, and defer their execution.

x = dask.delayed(inc)(1)
y = dask.delayed(inc)(2)
z = dask.delayed(add)(x, y)
z.visualize()

and this task graph

question

is the symbol here a general graph notation? is this a kind of graph language, like UML for visualizing the design of a system, used to visualize the computation task?


texts: Bottom-Up Evaluation of Inherited Attributes

texts:
I came across $2$ translation schemes of Syntax Directed Translation (SDT) in compilers which are as follows :

Using a top-down translation scheme, we can implement any
$L$-attributed definition based on a $LL(1)$ grammar.
Using a bottom-up translation scheme, we can also implement any
$L$-attributed definition based on a $LL(1)$ grammar (each $LL(1)$ grammar
is also an $LR(1)$ grammar).

What these $2$ Definitions actually mean ? I am not getting ..

I am well aware of $L$-attributed definition and $S$-attributed definition of SDT and top down parsing and bottom up parsing but It is just that I am unable to recollect this information and phrase it according to the definitions given above.

It would be good, if I can get one example of both definitions so, that I can phrase it meaningfully of what is said .


texts:
We use electronics to build computers and do computation. Is computation independent of the hardware we use? Would it be possible to do whatever a computer does with pen and paper? If computation is not dependent of how we make our computers, then does the same principle which apply to a computer apply to how brain works?
I want to know if computation is an abstract object which then is realized as computers. In other words, if we visit some alien civilization we expect that our mathematicians and physicists understand the alien physics and math. Is it the same as with the notion or concept of computation?
It seems that in order to consider computation first we need consider a realization of a machine or a model. For example according to the first two lines of this question there are Turing machine, circuits and lambda calculation. How do we know that there is not another way of computation? For example, the way the brain works and does computation might not be describable by the computation which we consider in Turing machine.

To put it another way, are there axioms which we build a theory of computation based on them? like the way we build Euclidean geometry.


texts:
Me and my friends are studying for an upcoming test and this exercise is one of the harder ones for us.

We have been trying to solve it and we have been looking at similar exercises, the problem is that the explanations are too complicated for us to understand. Keep in mind we just started with this.

So, my question is: Can anyone explain this as simple as possible, I have included the exercise.


texts: Notable decidable operations on context-sensitive languages

texts:
It is not always so easy to determine which basic questions on languages are (un)decidable. Also due to Rice's theorem, many nontrivial questions on languages are undecidable.

  What are notable or significant decidable operations on context-sensitive languages (CSL)?

In other words, I'm looking for the "most complex" operations on CSLs that are decidable. References to applications are optional but would be helpful.


texts: I want to figure out whether my problem described below is reducible to the set cover problem

texts:
I have a collection of non-empty sets $S_i$, where $1 \le i \le n$, which are constructed from elements of a universe $U$.

I need an algorithm that gives me a set $T$ of minimum cardinality ($T \subseteq U$), such that $T \cap S_i \ne \phi, \forall i$, where $1 \le i \le n$.

I am not sure whether it is an NP-complete problem and can be reduced to minimum set cover in some way. I thought of reducing it to vertex cover, by taking the sets as vertices, and putting an edge between any two sets if their intersection is non-empty, but that doesn't quite seem to work either.


texts: How to output all longest decreasing sequences

texts:
Suppose I have an array of integers having length $N$. How can I output all longest decreasing sequences? (A subsequence consists of elements of the array that do not have to be consecustive, for example $(3,2,1)$ is a decreasing subsequence of $(7,3,5,2,0,1)$.) I know how to calculate the length of longest decreasing sequences, but don't know how to report all longest decreasing sequences.

Pseudocode will be helpful.


texts: How to find all paths of length up to k between two nodes in a directed graph?

texts:
Let's say I have a directed graph represented as an adjacency matrix, and I'm given two nodes $u,v$ and a parameter $k$. Let's also say that the maximal degree of a node in the graph is $d$.

What is the most efficient algorithm to find all paths of length $<=k$ from $u$ to $v$?

I know the number of such paths can be calculated efficiently using Dynamic Programming approach, but I'm looking for an algorithm that allows to get a set of actual paths.

It's clear that such algorithm would have a factor of the number of paths in its time complexity, which has $k$ in the exponent, but still, I would like to know what is the best approach for such a problem.


texts:
Sorry if this is too simplistic of a question, but over the last couple of months I have been working through the course mathematical foundations of machine learning at my college. I think I am really starting to understand backpropagation and its innerworkings of how it works, I am just hung up on this extremely little detail.

Assuming the cost function is the standard simple example of: $$J(\theta)=(a^L - y^L)^2$$

I understand that in general we define the "error" in a given layer as $$\delta^L = \frac{\partial C}{\partial z^L} $$
And for a general layer this comes out to:
$$\delta^{L-1} = (\theta^{L-1}\delta^L).*\sigma^{'}(z^L)$$

I am seeing in my professors slides and in Andrew Ng's powerpoint that this derivative for the output layer is just: $$\delta^L=a^L-y^L$$ Why is the error in the output layer not including the derivative of the activation function like we calculate for every other layer? Shouldn't this be: $$\delta^L=a^L-y^L\times \sigma^{'}(z^L)$$

Why do we not have to use the chain rule with the derivative of the activation function for the output layer? This is just driving me crazy, I know there is some simple intuition, I just can't wrap my head around it. Any insight would be greatly appreciated.


texts: Is it possible to transmit bits digitally?

texts: I have learnt that all data transmission is analog. Is there any mediums that could transmit bits digitally?


texts: Subset with modified condition, is it still NP-complete?

texts:
So I know the conditions required for a problem to be NP-Complete is that it has to lie within NP and has to be NP-hard.

The given problem I have is subset sum.

However, the conditions have been change to sum ≤ M and sum ≥ M from sum = M. To be more specific:

"If we ask if there is a subset with sum ≤ M, is the problem still NP- Complete?"
"If we ask if there is a subset with sum ≥ M, is the problem still NP- Complete?"

My initial reaction is that the two problems are no longer NP-complete since they can both be solved within polynomial time.

Check each element and see if there exists at least one smaller than M.
Add all positive integers and see if the sum of all elements is larger than M.

Since it isn't NP Hard, it cannot therefore be NP-complete.

Am I thinking/approaching this correctly?


texts: Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

texts:
What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)?

For example, in the graph below, you want to go from $(0,0) \rightarrow (-3,2)$. Normally, an algorithm like Dijkstra's algorithm would produce a sequence like:

$$\left[ (0,0) \stackrel {3}{\rightarrow} (0,3) \stackrel{\sqrt{2}}{\rightarrow} (1,2) \stackrel{4}{\rightarrow} (-3,2) \right] = 7+\sqrt{2}.$$

Full graph:

Shortest path:

Shortest non-intersecting path:

However, this path intersects itself on the euclidean plane, therefore I want an algorithm that would give me the shortest non-intersecting sequence, in this case:

$$\left[(0,0) \stackrel{3}{\rightarrow} (0,3) \stackrel{3}{\rightarrow} (0,6) \stackrel{5}{\rightarrow} (-3,2) \right] = 11.$$

This path is longer than the shortest path, but it is the shortest non-intersecting path.

Is there an (efficient) algorithm that can do this?

TikZ sources

Full graph.
Shortest path.
Shortest non-intersecting path.


texts: Would memoization make any improvement to Strassen's algorithm?

texts: Could the run-time of the Strassen's algorithm be improved by adding Memoization to it?


texts: Construction of hash function with a given distribution

texts:
Two questions about the construction of a hash function:
Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "looks like" it maps each of the $u_i$s  to a random number, chosen from the uniform distribution on $[0,1]$. One simple way to construct such $h$ is to store in the memory a table of size $n$, and saving, for each element $ u_i$, the corresponding random sample. This is obviously very inefficient, and impossible to do if $U$ is infinite (or even continuous). Are there known approaches (or lower bounds) for the discrete, finite case? Are there approaches for the continuous case (i.e. $U$ is a continuous set)?
Clarification for the continues domain case:
Suppose that $U = \mathbb{R}$. What I am after is a function $h : U \rightarrow [0,1]$ such that $h(u)$ has the property of "being random" i.e. if you sample many points from $\mathbb{R}$, and look at $h(x_1),...,h(x_m)$ they would look like numbers which were sampled from uniform distribution


texts: Will this algorithm terminate on any input?

texts:
One can compress data with straight-line grammars. An algorithm that employs this technique is called Sequitur. If I understood correctly, Sequitur basically starts with one rule representing the input and then does these three steps till the grammar does not change anymore:

For each rule, try to find any sequences of symbols in any other rule that match the rule's right hand side and replace these sequences by the rules left hand side.
For each pair of adjacent symbols in any right hand side, find all non-overlapping other pairs of adjacent symbols that are equal to the original pair. If there are any other pairs, add a new nonterminal, replace all occurrences of these pairs by the new nonterminal and add a new rule that defines the nonterminal.
For each nonterminal that appears exactly once on all right-hand sides of all rules, replace its occurrence by its definition, remove the nonterminal and the rule that defines it.

For each (non-empty) input, can one guarantee that the above algorithm terminates?


texts: Prove no DFA with four states can accept L={111}

texts:
Assume we have a language L={111}. Prove no DFA with four states can accept L.
Can’t a DFA with 4 states accept L?


texts: Solving a recurrence relation with both decrementing and slicing the element by a constant

texts:
Given:
$$f(1) = 1 \\ f(n) = 4f(n-1) + f(n/3) + f(n/8)$$
(if $n<1$ then it is still 1)
And I need to find $\Theta(f(n))$, can I do this?
$$ \Theta( f(n))  = \Theta(4f(n-1)) + \Theta(f/3)) + \Theta(f(n/8))$$
Then solve each term and get that it is $\Theta(4^n)$ ?
Or it is not possible as we basically have this:
$$ f(n) = 4 (  4f(n-2) + f((n-1)/3) + f((n-1)/8)) + f(n/3) + f(n/8) $$ etc... and by the end we have:
$$ \sum_{m=0}^{n} 4^{m} ( f((n-m)/3) + f((n-m)/8)) $$
But this seems so incorrect because then each term in the sum calls the functions again with its value, thus making another sum and another sum..
this is really crazy and I cannot comprehend it in my head, I would be thankful for any kind of hint/answer. Thanks!


texts: Contradiction between best-case running time of insertion sort and $n\log n$ lower bound?

texts: If the best case for Insertion sort & bubble sort is $O(n)$ then how is lower bound for any comparison sort is $\Omega(n\log n)$? I mean, $O(n)$ is obviously smaller than $\Omega(nlogn)$. What am I missing here?


texts: The theory behind backpropogation, gradient calculation

texts:
I am reading a book about Neural Networks, that explains the backpropagation algorithm. It explains that the error function is the sum of error of all inputs, and that the algorithm minimizes this sum, which makes perfect sense to me, but than in goes on stating that to achieve that the gradient is calculated for each input, and then summed up. This last step is not understable to me.

Is it implying that the gradient of the sum of all errors (from all inputs) is equal to sum of gradients (from all inputs), that is - that the sum of gradients equals the gradient of sum?

This seems to me like an non trivial step, but it is not explained in the book.


texts:
I have a question about definability of truth assignments. Suppose that I am working in the context of propositional logic. Let me give some definitions first.

Let $L$ be a propositional language with the set $Prop_{L}$ of propositional variables. A truth assignment is a map $v\colon Prop_{L}\to\{F,T\}$. Denote the collection of truth assignments in $L$ by $TA_{L}$. Note that in a language $L$ with $|Prop_{L}|=n$ for some $n\in\mathbb{N}$, $|TA_{L}|=2^{n}$, while in a language with $|Prop_{L}|=\aleph_{0}$ (denumerably many), $|TA_{L}|=2^{\aleph_{0}}=\mathfrak{c}$ (continuum many).

Definition 1. Let $\Sigma$ be a set of propositional formulas. The set of models of $\Sigma$ is
$$Mod(\Sigma):=\{v:v\ \mbox{is a truth assignment and $v(\varphi)=T$ for each $\varphi\in\Sigma$}\}.$$

Definition 2. Let $K\subseteq TA_{L}$. Then $K$ is definable if $K=Mod(\Sigma)$ for some set $\Sigma$ of formulas.

I have tried to prove a couple of things. In a propositional language with only finitely many propositional variables, any set of truth assignments is definable. Now, I want to show that, in a propositional language with denumerably many propositional variables, any finite set of truth assignments is definable. Imitating the idea in the proof about finite language, I have an outline of the proof about infinite language. Here is the detail:

Convention.
Let $p$ be a propositional variable and $v$ a truth assignment. Define
$$
p^{v}:=
\begin{cases}
p &\mbox{if}\ v(p)=T;\\
\neg p &\mbox{otherwise}.
\end{cases}
$$
Then it can be seen easily that $\widehat{v}(p^{v})=T$.
(Here $\widehat{v}$ denotes the extension of $v$ to the set of propositional formulas.)

Claim. In a language $L$ with $|Prop_{L}|=\aleph_{0}$, any finite set of truth assignments is definable.

Proof.
Assume that $Prop_{L}=\{p_{1},p_{2},\ldots\}$. Let $K\subseteq TA_{L}$. Assume that $K$ is finite. Then $K=\{v_{1},v_{2},\ldots,v_{k}\}$ for some $k\in\mathbb{N}$. Let $1\leq i\leq k$. For each $j\in\mathbb{N}$, define
$$\varphi^{i}_{j}:=p^{v_{i}}_{1}\wedge p^{v_{i}}_{2}\wedge\cdots\wedge p^{v_{i}}_{j}$$
and define
$$\chi_{j}:=\varphi^{1}_{j}\vee\varphi^{2}_{j}\vee\cdots\vee\varphi^{k}_{j}.$$
Let $\Sigma=\{\chi_{j}:j\in\mathbb{N}\}$. Claim that $K=Mod(\Sigma)$.

Now, the part $K\subseteq Mod(\Sigma)$ is easy. What is hard for me is the reverse inclusion: any truth assignment satisfying $\Sigma$ must be $v_{i}$ for some $1\leq i\leq k$. Since I am dealing with infinitely many propositional variables, to show that two truth assignments coincide is to show that they agree on infinitely many propositional variables. Yet I have no idea how to show that, because truth assignments in $K$ seem to involve only finitely many propositional variables. Could anyone please advise me about this?

Any suggestions would be greatly appreciated :)


texts: Why line graph is a proper subclass of claw-free graph?

texts:
A claw is the graph isomorphic to $K_{1,3}$, that is, a star graph with three edges, three leaves, and one central vertex. (see below)

A graph is claw-free if it does not contain a claw as an induced subgraph.

The line graph of G is the intersection graph of the edges of G, that represents the adjacencies between edges of G.

A graph $F$ is a line graph if there exists a graph $H$ such that $L(H) = F$.

My question is why are line graphs a subclass of claw-free graphs??
Thanks a lot!


texts:
I have some large number $n$ in base $b_1$ and I want to convert it to base $b_2$. $n$ is about a million decimal digits long, therefore it's impractical to convert it as a whole. However I don't need the entire $n$, just some arbitrary slice of it when it's converted to $b_2$

For example converting from base 10 to base 3, with a slice from digits 5-10:

n(10) = 2347892347
n(3) = 2000[11212]22021210211
m(3) = 11212 <-- the number I need

note: it doesn't matter if the slice starts from the left or the right of the number

Is there a fast method to get that slice $m$?
Any help is very much appreciated.


texts: What is the complexity of depth first traversal that don't label nodes as discovered?

texts:
I've found an algorithm that acts like a depth first traversal that don't recognizes nodes that have been visited before.

  A
 / \
B   C
 \ /
  D
  |
  E

If run on this graph, the algorithm will traverse in this order:

A, B, D, E, D, B, A, C, D, E

Is there any way I can express the run-time complexity of this algorithm in terms of edges, nodes, or the depth of the graph? I expect it would be high, I have the feeling it will be exponential, but I'm struggling to explain why.

EDIT: The real algorithm that I am analyzing is computing the result of an expression tree, only it is not run at a tree, but at a DAG. This means, that nodes that have several parents get computed once for all parents.

Simple pseudo-code for the algorithm might be:

calculate(root){
    if(root.isLeaf){
        return root.value;
    } else {
        leftval = calculate(root.left);
        rightval = calculate(root.right);
        return root.operator(leftval, rightval);
    }
}


texts: Every language that is reducible to a language in $\Sigma_i^p$ is also in $\Sigma_i^p$ . How?

texts:
The complexity class $\Sigma_{k}^{p}$ is recursively defined as follows:
\begin{align}
\Sigma_{0}^{p} & := P, \\
\Sigma_{k+1}^{p} & := P^{\Sigma_{k}^{p}}.
\end{align}

Why is every language that is reducible to a language in $\Sigma_i^p$ also in $\Sigma_i^p$?

This comes in the proof of the theorem: If there is a PH-complete problem, then PH (the polynomial hierarchy) collapses.


texts: Which one grows faster asymptotically: $\log(\log^an)$ or $\log^a(\log n)$

texts:
Could someone explain to me which function grows faster?

$f(n)=\log(\log^an)$ or $g(n)=\log^a(\log n)$


texts: How do we know for sure that EXPTIME ≠ P?

texts:
I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It makes absolute sense intuitively that this is the case, as does P≠NP. From what I understand, the time hierarchy theorem states that given more time, a turing machine can solve harder problems.

I have 2 questions:

How is the time hierarchy theorem (or anything else) used to prove that P≠EXPTIME?
If we assume P=NP and NP=EXP, P=EXP and that contradicts P≠EXP. So one of those statements MUST be false. But we can only conjecture that both these are false, and can't prove it? Is that the case?


texts:
What is the intuition behind the Geometric Burrows-Wheeler Transform? And how can I use a GBWT with blocking factor $d$ to  match a given pattern $P$  of length $|P| = m$ with

$m \ge d$
$m < d$

What benefits does it have over the standard BWT used with backward search?


texts: Interview Question: Insert switch to maximize time lightbulb spends on

texts:
Problem statement:

  You have a lightbulb for an interval of $N$ seconds, where $N$ is given.
  At time 0, the lightbulb switches on, and at time $N$, it switches off,
  regardless of any switches. From time 1 to time $N-1$ you have a maximum
  of $N-2$ switches in the form of an array called switches, which turn
  the lightbulb to the opposite of what it currently is i.e. if it's on
  it'll turn off and vice versa. For example, suppose $N = 8$ and switches
  $[1,2]$. The lightbulb will switch on at time 0, a switch at time 1 will turn it off, a switch at time 2 will turn it on, and it'll remain
  on until time 8, when it turns off. Hence, the time it remains on is
  equal to $1-0 + 8-2 = 7$.

  Now suppose you have to insert a switch in this interval, where there
  is not already a switch present. What is the maximum time the
  lightbulb remains on once you insert the switch. For example, in the
  above case, the solution would be 6 since inserting a switch at time 7
  keeps the time the lightbulb spends on maximum. Since $1-0 + 7-2 = 6$,
  the answer is 6.

I solved this using a brute force solution, using the reasoning that  if you insert a switch at time $k$, the states of the lightbulb before this wouldn't be affected, and the states of the lightbulb from time $k$ to time $N$ will be reversed, and hence you can find the time it spends on after time $k$ by $(N - k) - t$, where $t$ is the time it would spend on from time $k$ to $N$ without the inserted switch. Hence, I can calculate the time the lightbulb would spend on for each time position of the inserted switch and maximize it. However, since calculating the time the lightbulb spends on is $O(n)$ operations and I go through all possible positions, my solution is $O(n^2)$ and this caused my code to time out for some test cases.

Can someone propose a better solution?


texts: Is $ L = \{ a^n\ |\ a^n \not\in L_n \} $ Turing recognizable (recursively enumerable)?

texts:
Say $ \Sigma = \{a\} $, $M_1, M_2, ... $ is an enumeration of all TMs that recognize languages over $\Sigma$ and $L_1, L_2, ... $ are respectively the languages that are recognized by those TMs. We construct the language $ L = \{ a^n\ |\  a^n \not\in L_n \} $. Is $L$ Turing recognizable (recursively enumerable)?

My thought process is this: Say $L$ is recognizable. Then given a string $a^k$, we find $L_k$ based on the enumeration of $L_i$'s, and then we run $M_k$ on input $a^k$ to find if indeed $a^k \not\in L_k$. We must accept if $a^k \not\in L_k$, but $M_k$ is not guaranteed to halt in that case. So $L$ is not recognizable.

Now I have 2 questions:
1) Is my thought correct?, and
2) How can I make this more formal?


texts: Why is Iterative-deepening A* optimal, even without monotonicity?

texts: Why is it that Iterative-deepening A* is optimal, even without monotonicity? How can I be sure that the first goal reached is the optimal one?


texts:
What would these statements mean if f(n) and g(n) are functions over natural numbers?

g(n) is in Θ(f(n)).
and

An algorithm is in the complexity class Θ(f(n)).


texts: Recurrence Question:T(n) = T(n − √ n) + T( √ n) + θ(n)

texts: I need help to solve the recurrence T(n) = T(n−√n) + T(√n) + θ(n)


texts: Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

texts:
I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive.

the algo depends on finding a new weight function (w') that is positive for all edges and keeps the correctness of the shortest paths relations.

It does so by calculating h(s), h(d) values to be added to the w original value.

My question is, why not just find the smallest w in the graph and add it to all edges ? this will satisfy both conditions and will require less calculation.


texts: How to write Context Free Grammar with numerical restrictions

texts:
I am supposed to write a Context free grammar that generates the language:

$\qquad L(G) = \{0^{3n}1^{2n}0^{m}1^{m} : n \ge 1, m \ge 1\}$

I have the rules:

$$S \rightarrow 000S$$
$$S \rightarrow S11T$$
$$T \rightarrow 0T$$
$$T \rightarrow T1$$

This looks correct in terms of the structure of the grammar but I am not sure how to denote how to tell the grammar to terminate at the correct time given the conditions $n \geq 1$ and $m \geq 1$.


texts: Can you operate on and draw conclusions on functions described asymptotically?

texts:
This question is homework based (not using actual problem though)!

Say you have a function described as:

$$f(n) \in  O(2n^2) \, .$$

Can you then go on the treat this as:

$$f(n) = 2n^2$$

and performs mathematics on it and keep its asymptotic meaning?

In the above case could I conjecture that $f(n) \in  O(2n^2)$ implies $f(n) / 2 \in O(n^2)$ (assuming coefficients matter in this example)?


texts: Reduction of specific scheduling problem to show np-completeness

texts:
Given a Set K of n tasks, a set T of t possible time-intervalls to schedule any task, and a number k:

Is there a schedule for the tasks, such that there are at most k conflicts (time - overlaps) of the tasks?

I'm having trouble showing that this is np-complete. I don't know how to reduce it to another np-complete problem. My intuition suggests something graph-related, but I can't get anywhere.

Edit: What I thought so far:
Let the undirected Graph

G = (V;E) with V= {T} $\cup$ {K} and E = { {u,v} | u $\in$ K, v $\in$ T: u can be performed in intervall v}

So basically connect all tasks to timeslots they can be performed in.
Is there a Hamilton cycle with at most k nodes used more than once?
You will get a path along the lines of: t1-1-t2-2-t3-1-t1, which shows 1 conflict (obviously, with 3 tasks and 2 timeslots).
Every intevall-node that is visited more than once is a conflict node.
Is this correct thinking? How can I show this is np -complete?


texts:
Say that I have a superscalar processor and I am given the latency, issue and capacity (in clock cycles) for different instructions.

What is the general formula for latency bound and throughput bound? (I will convert to cost per instruction and billion instructions per second)

This field seems to be too niche to find information online.

In other words, how can I find the latency bound and throughput bound for fdiv

     Latency   Issue  Capacity
fdiv    L        I       C

where L is the number of cycles for the fdiv latency, I for issue and C for capacity?

Would $\text{latency bound} = {L \over I} \times C$ and $\text{throughput bound} = {L \over C}$?

This is not the homework problem, but a "required" definition in order to be able to start it.