How to solve the bin packing problem with conflicts? I'm trying to devise an algorithm to solve the bin packing problem with conflicts (sometimes referred to as BPPC, or BPC).

The problem is defined as follows: consider a set $V$ of $n$ items, where each item $i$ has an associated positive weight $w_i$, and $n$ identical bins of capacity $C$. In addition, there is an undirected graph $G=(V,E)$ representing the conflicts between items. The problem is to assign all items to the minimum number of bins without exceeding $C$ and in such a way that no bin contains conflicting items.

Now I understand that this problem is a combination of the graph coloring problem, and the normal bin packing problem, but I can't quite figure out how to merge algorithms designed for one or the other into a single algorithm suitable for solving this problem.

I have found the following resources that should be useful.
A first line of work has been on the domain of approximation algorithms and focused on achieving results for particular classes of the conflict graph:

[1] Jansen, Klaus. "An approximation scheme for bin packing with conflicts." Journal of combinatorial optimization 3.4 (1999): 363-377.
[2] Epstein, Leah, and Asaf Levin. "On bin packing with conflicts." SIAM Journal on Optimization 19.3 (2008): 1270-1298.

In [1], the author proposes an asymptotic approximation scheme for the bin
packing problem with conflicts restricted to $d$-inductive graphs with constant
$d$. This graph class contains trees, grid graphs, planar graphs and
graphs with constant treewidth. The algorithm's number of bins within a factor of
$1 + \varepsilon$ of optimal, having runtime polynomial both in $n$ and $1/\varepsilon$. This is an algorithmic theory paper with no experimental results are provided.
In [2], the authors study both online and offline variants of BPC, again, only on specific graph classes, e.g. perfect graphs, interval graphs and bipartite graphs. They improve on previous approximation ratio by Jahnsen and Öhring for perfect graphs. As an example of the results, they create a 2.5-approximation algorithm for the perfect graph case. Again a theoretical work where no numerical examples are shown.
A second line of work is concerned with implementation and heuristics (I am including branch-and-bound algorithms on this category even though they follow a different paradigm) and includes the following publications:

[3] Muritiba, Albert E. Fernandes, et al. "Algorithms for the bin packing problem with conflicts." Informs Journal on computing 22.3 (2010): 401-415.
[4] Sadykov, Ruslan, and François Vanderbeck. "Bin packing with conflicts: a generic branch-and-price algorithm." INFORMS Journal on Computing 25.2 (2013): 244-255.

In [3], the authors present new methods for finding upper and lower bounds for the BPC optimal solution, and a couple algorithmic approaches for the BPC:

Evolutionary Algorithms and Tabu search
Branch and price (that is, branch and bound combined with a column generation scheme) using a set covering formulation.

They show benchmark results consistently improving previous methods from the literature. They also left the benchmark instances and computational results available online, which could be useful to OP or other interested people. At this link you can find conference presentation slides related to this work. They used CPLEX, which is  a commercial solver for optimization.
Finally [4], which is available at one of the authors' ResearchGate profile here. As in [3], the authors propose a branch-and-price algorithm for this problem using a set covering formulation, but the methods' details are different. They tested the approach on several instances, creating a specific variant for the case where the conflict graph $G$ is an interval graph, while also developing an approach for the general case. They tested their algorithm on both kinds of scenarios, and experimental results show their approach outperformed previous algorithms in several instances, both in terms of execution time and of achieving optimality. The work was implemented using BaPCod, a branch-and-price framework developed in C++ by a group at INRIA.

As a summary:

Having graph coloring as a particular case, it's hard to approximate the BPC. Good results have been attained using heuristic methods and branch and price with set covering formulations.
So, you could try starting with the simplest steps of the method presented by Fernandes-Muritiba et al- that is, lower and upper bounds and Evolutionary Algorithms and see if they fulfill your needs in terms of solution quality and execution time. There are several frameworks for implementing evolutionary algorithms, e.g. DEAP in Python.
If you'd rather have a general approximation guarantee, and if the conflict graph instances you work with fall within the categories of their studies, evaluate implementing algorithms from the first line of work.
I'd leave using branch and price approaches for later, especially in case of a tight development timeframe or if you don't have access to an optimization solver license.


Understanding Multilevel Caches I'm reading multi-level cache and came across a question through  which i got confused. I've read that

  Between processor and Cache Word/ Byte is transfered
  Between Cache and Main memory Block(Block of words) is transfered.
  If there is a miss in lower level cache and hit in higher level
  cache, first Block of words is transfered from higher level cache to
  lower level cache and then particular words is transferred to the
  ptocessor from lower level cache.

In case of multi-level caches cache at lower level generally has lower size as compared to cache at higher level. Hence Block size of lower level cache is generally smaller than block size of higher higher cache.

So, How actually Block of words is transferred between caches.

For instance suppose there two caches $L_1$ and $L_2$ with block size 4 words and 16 words respectively, connected with a databus having capacity to transfer 4 words at a time. Now Suppose there is a miss in $L_1$ cache and a hit in $L_2$ cache. Then Do we transfer 16 words or only 4 words from $L_2 \rightarrow L_1$

Block sizes (aka Cache line lenghts) can be different on different levels of caches. L1 caches should be optimised for the type of access the CPU does while L3 caches should be optimised for the burst lenght and data width of the attached DRAM memory.

It is possible to fill/spill only one block of the L1 with a larger block sized L2 (in your example 4 words). On write back, either the whole L2 block is marked as modified, or use sub-blocking (effectively reducing block size without raising associativity).

One advantage with using the same size is probably with exclusive caches (AMD did that many times) : As soon as a block is in L1, copied from L2, the L2 block can be made available for new data.

Edit

Many examples there : http://www.7-cpu.com/
Using different block sizes across different cache levels seems very rare : Several recent x86 use 64Bytes, ARMs 32Bytes, PowerPCs 128Bytes, but they keep the same size on all levels. Note also the bus width : Internal busses can be extremely large, able to transfer 16 or 32 bytes in one cycle.


Knapsack problem: equal profits I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal.
More formal definition of the problem from a Wikipedia article on KPs:

If all the profits are 1, we will try to maximize the number of items which would not exceed the knapsack capacity:
maximize $\sum_{j=0}^n x_j$
subject to $\sum_{j=0}^n w_jx_j \leq W$,
$x_j \in \{0, 1\}, \forall_j \in \{1, ..., n\}$

I skimmed through Knapsack Problems book (Kellerer et al', 2004) that is referenced by that Wikipedia article but couldn't find that particular problem.
I also saw some posts about this exact problem with no good answers:

Knapsack with same value
Knapsack problem with all profits equal to 1

The answer to the first post mentions Capital Budgeting problem, but the provided link doesn't discuss the case where all profits (values) are equal, which I believe can be better optimized due to its special case.
The answer to the second post mentions a naive solution in which a greedy algorithm picks minimum weight items at each step until no more items fit in the knapsack. This requires knowing the order of items by weight, which results in $O(n\log{n})$ solution.
Is there an algorithm with a better upper bound (e.g. linear time)?

Comment $\rightarrow$ answer.

Without loss of generality, we assume that all weights are strictly positive (otherwise, we can take all non-positively-weighted items ahead of time and change $W$ as appropriate).

From here, one can use an approach reminiscent of Randomized Quick-Select to solve this in expected linear time. First, define a tie breaking procedure for weights that consistently breaks ties between equal weighted items. For example, one can use the ordering of items as given in the input.

Now repeat the following procedure. Pick a random element $k$ and check if the sum of weights of all elements no heavier than $k$ (using the above tie-breaking rules) is less than $W$. If so, the optimal solution must contain all such elements, so put them all aside and recurse on the subproblem of elements heavier than k, with $W$ decreased appropriately. Otherwise, the optimal solution must be a strict subset of these elements, so discard all larger elements and recurse with the same $W$ you started with. The base case of the recursion is one where you return the empty set when $W$ is less than the cost of the cheapest item (or if no items remain).

Each round takes time linear in the input size for that round, but it takes a constant number of rounds (in expectation) to reduce the size of the instance by a constant factor, so the total running time intuitively should be expected linear. Indeed, the usual analysis of Randomized Quickselect works identically here, too, proving the result.

Here's a non-tail-recursive implementation in Python.

def uniformKnapsack(items, W):
    import random

    def subProcedure(remaining, new_W):
        # base case
        if remaining == [] or min(i[0] for i in remaining) > new_W:
            return []

        # sample random item
        random_item = random.choice(remaining)

        # split input into larger and smaller subsets based on the item
        smaller = [i for i in remaining if i < random_item]
        not_smaller = [i for i in remaining if random_item <= i]

        # compute the total cost of all smaller items
        smaller_cost = sum(i[0] for i in smaller)

        if smaller_cost <= new_W:
            # include all smaller elements and recurse on the rest with a smaller W
            return smaller + subProcedure(not_smaller, new_W - smaller_cost)
        else:
            # recurse on the smaller subset with the same W
            return subProcedure(smaller, new_W)

    # convert a list of items (a, b, c) to  a list of the form ((a, 0), (b, 1), (c, 2)) for
    # consistent tie breaking in comparison operations
    augmented_items = [(j, i) for (i, j) in enumerate(items)]

    # compute the solution over the augmented items
    solution = subProcedure(augmented_items, W)

    # return the un-augmented items from the solution
    return [i[0] for i in solution]


How come Google search never gets slower? Doesn't it have to go through the ever increasing amount of data on the internet and then rank? I heard Google creates indexes of pages. Even then, the number of indexes goes with time. Why wouldn't this slow down the search?

The google indexing and search is run in parallel using a map-reduce algorithm.
As the number of pages to index expands, so does the number of computers that google uses for the task.

Currently Google handles about 3.5 billion searches per day.
A single search uses 1 000 computers in parallel (each computer holds $\frac{1}{1000}$ of the total Google index) and takes on average 0.2 seconds.

Servers available for search are always in read-only mode. When the search index gets updated those servers are temporary unavailable for search.

Given the current amount of floor-space in its data centres Google has a maximum of about 1.7 million servers.
Obviously most of these are devoted to something other than search.


Can an NP-Complete problem be reduced to an NP problem? All NP problems can be reduced to NP-Complete problems, can an NP-Complete problem be reduced to a NP problem (non complete)?

An NP-complete problem is in NP, by definition. No reduction needed.


Permute an array in O(n) time with O(1) extra space with a given ordering function? This question arises from a problem on a problem solving site (https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately/0).

Given a sorted (ascending order) array $A$ of $N$ numbers, re-arrange the elements of A to be this order: [A[n-1], A[0], A[n-2], A[1], A[n-3], A[2], ...].  While the problem does not actually call for this specific index permutation, that's the approach I took (it will yield the correct answer).  If there is a solution that does not involve this approach, I'm interested to see it, but this question specifically is about whether or not it is possible to perform this specific data value re-arrangement without regards to the values stored in the array.

In other words, alternately interleave the maximum, minimum, 2nd-maximum, 2nd-minimum, etc.  The algorithm should run in $O(n)$ time and consume only $O(1)$ extra space.  It should work regardless of the data values in the array, including scenarios with duplicate values.

Solutions for $O(n^2)$ time with $O(1)$ space and $O(n)$ time with $O(n)$ space are straightforward.

There is a simple function that given a source index in the initial sorted array, determines its destination index in the re-arranged array.  I have a partial solution that works by starting at some index and moving through the cycles of source $=>$ destination element moving.  But I couldn't find a way to compute the locations of all the separate index-moving cycles.  Instead, after completing a cycle, I search the partially re-arranged array for pairs of values that haven't been moved yet (that hold the original, not new, ordering), and use those indices to start a new cycle (this probably means my solution is not $O(n)$ time because of this search).  But this doesn't work in general if the elements of the initial array contain duplicate values.

I have an intuition that there must must be an algorithmic move/swap index ordering dependent only on N, but I haven't been able to find one.

Reverse the last half of the array in-place and then apply one of the interleaving algorithms mentioned in this question.

That question is for even $n$, and I didn't check whether the answers work for odd $n$ as well. If they don't and it's needed you can do a left rotation to move the middle element to the end (its correct position) and then use one of the even-case algorithms to move the first $n - 1$ elements to their correct positions.


Optimizing resource management game (similar to Farmville) Given a fully deterministic single player resource management game
with a pre-known finite number of turns and reasonably simple rules
(eg, Farmville, if it were single player, deterministic, and ended
after a certain number of turns), is it usually possible to write a
computer program that can optimize the game in a reasonable amount of
time? Details:

I'm trying to create such a game (sort of a M.U.L.E. clone, but
not really). Players would compete individually to get the highest
score under a given set of starting conditions. The game must be
simple enough to be fun, but complex enough that someone can't write
a computer program to rapidly optimize it. The game is semi-tedious
(in its current form), so I encourage API/automated use.
Since the game is deterministic and finite, I realize that an
optimization algorithm must exist. So my question really is: can
someone always write an optimization algorithm that runs fast enough
to be useful?
I realize the answer depends on the actual game I write, so I'm
looking for one of these answers (roughly):

Give up. If you design a resource management game easy enough
for people to understand, someone could easily design an algorithm
to win it.
There's hope. Depending on how you design the game, it may or
may not be possible to write a reasonable algorithm to optimize
it. However, you have to be very careful.
Go for it. In general, there are no algorithms that can optimize
most resource management games. Barring extreme conditions, any
resource management game you design could not reasonably be
optimized by a computer.

There are Farmville strategy guides online, but they focus on
general strategy, not an explicit algorithm.
I realize this is a specific case of P != NP, and that's it
theoretically possible to create simple questions that cannot be
solved easily (eg, factor a product of two large primes) or even at
all (eg, the halting problem), but I'm wondering if resource
management games fall, in general, into the NP category.
For reference, the game will be a scaled down (and single player)
version of:

https://github.com/barrycarter/bcapps/tree/master/YAMC

In general, you cannot hope for a polytime solution to all such games.  For many such games, the problem of playing them optimally is NP-hard.

For instance, Minesweeper (on a $n\times n$ grid) is NP-hard, and thus does not have a polytime algorithm to solve it (unless $P=NP$, which most consider unlikely).  The same is true for Sudoku (on a $n^2 \times n^2$ grid) and Tetris.  Optimal play for chess, checkers, Go, and Scrabble (on a $n \times n$ grid) is either EXPTIME-complete or PSPACE-complete (depending upon whether you put a bound on the number of moves that a player can make), so they too are very unlikely to have any polytime algorithm to play them optimally (unless the polytime hierarchy collapses or something equally surprising).

In fact, I've seen some folks suggest that there's a strong connection here: the best games tend to be ones where finding the optimal solution is asymptotically hard.  If finding the optimal solution was too easy, the argument goes, the game wouldn't be fun for humans.  Obviously, this is not a rigorous argument and it is easy to come up with counterexamples, but I think there might be something to it.

There's lots more written on this sort of topic.  For a entry point and overview, see, e.g., the following:

http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
https://en.wikipedia.org/wiki/Game_complexity
https://www.ics.uci.edu/~eppstein/cgt/hard.html


State complexity of homomorphisms of regular languages Given a DFA $A = (Q, \Sigma, \delta, q_0, F)$ with $n$ states and a homomorphism $h: \Sigma \to \Gamma^*$. It is easy to see that the family of regular languages is closed under homomorphisms using regular expressions or by construction of a grammar.

My problem now is to analyze how many states are needed for a DFA $A' = (Q',\Gamma, \delta',q_0',F')$ to accept $h(L)$. First of all I tried to think of a basic construction method to get the automaton.

Let $a \in \Sigma$:

If $h(a) = \varepsilon$ then all the transitions of $a$ in $A'$ can be removed.
If $|h(a)| = 1$ then all the transitions with $a$ can be replaced with $h(a)$.
If $|h(a)| \geq 2$ then the transition of $a$ in $A'$ has to be replaced with $h(a)$ and split into $|h(a)|-1$ states each with a one symbol transition

a. If the prefixes of two unique symbols of $\Sigma$ do not share the same prefix then the resulting automaton can be extended into a DFA without adding any states(?).

b. If prefixes are shared then the resulting automaton would be an NFA, therefore it has to be converted into a DFA (using power set construction) and minimizing it.

Therefore my estimation for the state complexity in case $3a$ would be:
$$\begin{align*}|Q'| &\leq |Q| + |Q|\cdot\left(\sum_{a \in \Sigma} |h(a)| - 1\right)\\ &= |Q|\cdot(1- |\Sigma|+\sum_{a \in \Sigma} |h(a)| )\end{align*}$$

However, I'm not convinced about my construction as mentioned in step 3 and was not able to find an example of a language where the upper boundary is met. Therefore I'd be happy to see any advices.

Here is a simple construction that disproves your conjecture.

Let $a,b$ two relatively prime integers. It is known that the largest integer that cannot be represented as a non-negative integer combination of $a,b$ is $ab-a-b$.

Consider now the language $L = (0+1)^*$ and the homomorphism $h$ given by $h(0) = 0^a$ and $h(1) = 0^b$. Then $L$ is accepted by a one-state DFA, while $h(L)$ requires $ab-a-b+1$ states.


Borůvka cleanup in linear time? Given boruvka's algorithm:

MST T <- empty tree
Begin with each vertex v as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

In each phase I'd like to reduce the graph's size, by saying that after each phase - there is actually no need to remember edges that are within each component (because some were inserted to the MST T already and others are not needed). So instead of each component I'd like to put only a single vertex. The only problem comes when I try to construct my edges - an edge between two new vertices (which were two components before) is the one with the smallest weight among all the edges between a vertex in the first component and a vertex in the second. I wanted to implement this in linear time, but I don't see how I can reduce the edges as well, all in linear time?

This depends on what you mean by linear time. If you want $O(n)$, then you're out of luck, there's too many edges to consider in the worst case.

If you mean $O(n+m)$, then it is possible, and it is reasonable to consider this as linear time, as the input needs to represent the edges as well as the vertices, which takes at least $O(n+m)$ symbols.

After each round of selecting which new edges to add, we keep track of which pairs of components are being merged, then we look at these in order (any order is fine) and look at all edges from the new component to each other new component, and record the smallest we have seen. (Note that this is symmetric, so we when we find the smallest edge from new component $A$ to new component $B$, it is also the smallest from $B$ to $A$, so we only need to consider edges going to new components later in the ordering, but this doesn't affect the complexity). To achieve this we can simply look at all edges in order and update the appropriate information.


Subset sum to 0/1 knapsack How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.

Set the size of the bag to the value you are trying to reach $t$. For each element $x \in S$ add one item to the set having both its weight and value equal to $x$. The claim is the $(S, t)$ is a yes instance of the subset sums problem if and only if the optimal value of the bag is equal to $t$ (why?).


How is a nondeterminisitic automaton running on an input? A nondeterministic automaton, after reading an input symbol at some state, may jump into any of a (finite?) number of states.

Does the automaton uniformly randomly choose one out of the several states?

So different runs on the same input will give different sequence of states?

Does the automaton have to run in all the possible sequences of states on a given input? Or just one random run?

A non-deterministic automaton runs in all possible sequence of states on a given input. It is not a random run.

An input symbol is accepted only if in at least one of the runs it has reached an accepting state after reading the given input.

Hope this helps :D


What kind of error are these? I was following a discussion on a forum where a person has asked whether the following generates lexical errors or not,

  (1) char p="gate;

  (2) int /* n;

  (3) printf("%d, n);

When I tried to run them on my CPP compiler I got these errors respectively for the following 1, 2 and 3

When I looked them up on the internet they all are appearing to be Syntax errors.. Am I right? or are they lexical errors?

The C standard does not bother to distinguish between different kinds of errors encountered during parsing, but it is possible to categorise errors according to which clause of the standard applies.

The second line in your query (int /* n; -- assuming that there is no */ in the remaining program text) is covered by a requirement in the description of phases of translation, §5.1.1.2/1; in particular, in phase 3: (emphasis added)

  The source file is decomposed into preprocessing tokens and sequences of
  white-space characters (including comments). A source file shall not end in a
  partial preprocessing token or in a partial comment. Each comment is replaced by
  one space character. New-line characters are retained. Whether each nonempty
  sequence of white-space characters other than new-line is retained or replaced by
  one space character is implementation-defined.

The other two errors are also produced in phase 3, because the unmatched quote cannot be decomposed into a preprocessing token. The error is mentioned specifically in §6.4/3:

  A token is the minimal lexical element of the language in translation phases 7 and 8. The categories of tokens are: keywords, identifiers, constants, string literals, and punctuators. A preprocessing token is the minimal lexical element of the language in translation phases 3 through 6. The categories of preprocessing tokens are: header names, identifiers, preprocessing numbers, character constants, string literals, punctuators, and single non-white-space characters that do not lexically match the other preprocessing token categories. If a ' or a " character matches the last category, the behavior is undefined.

That probably justifies the use of the phrase "lexical error", at least as an informal description.


Difference between "data dependence graph", "data dependency graph", and "data flow graph" Is there a difference between a "data dependence graph" and a "data dependency graph"? I have seen both terms - sometimes used interchangeably sometimes not.

To make things even more complicated, a "data dependency graph" is sometimes also called a "data flow graph" (see e.g. here).

The term "data dependence graph" is, for example, used on the second slide here.

If there is a difference, could someone give an example of each graph type?
If there is no difference, why the two different terms?

Dependence and dependency are interchangeable terms.  In my experience, dependency (with a "y") is more common.  In my own writing I try to consistently use dependence (without a "y") for aesthetic reasons (I think it sounds better).  If you look at a dictionary you'll see that the two words are almost synonyms.  The only difference I'm aware of is that dependency (with a "y") means something specific in the field of political science (it means a territory that is controlled, or owned, by some other sovereign state.)  (This leads to my aesthetic dislike: the political dependency relation is asymmetric, while the dependence relation we use in program analysis is not.)

There are lots of minor variations between dependence graphs.  The dependences can be must dependences ("a always depends on b") or may dependences ("a could depend on b").  The graph might show control dependences in addition to data dependences (in which case it will be called a program dependence graph, and almost certainly will not be called a data-flow graph).  The dependence graph might or might not be superimposed on top of a control-flow graph.

Whether something is called a dependenc(e/y) graph or data-flow graph is pretty much also a matter of taste.  I try to avoid data-flow graph in my own writing, unless I am specifically talking about someone else's research and they have used the term data-flow graph.  (In particular, research on Dataflow computer architectures.)


Optimizing estimator of composed functions when function is known I have a problem which I'm looking to see if there is literature on:

Consider three types of actors, a Director, Aggregator, and Follower. The Director talks to multiple Aggregators, the Aggregator talks to multiple Followers. The director gives simple commands to the Aggregator, who then can portion out the commands to each Follower as she sees fit.

The question then is, how can the Director know whether or not an Aggregator can complete a given request at time step T? T+1? If T is now, then this is relatively easy as the Aggregator can simply sum up the capabilities of each of the Followers and return it, saying "this is what I can do in total." The problem then is, if the Director is doing her own optimization problem in deciding how to direct two different Aggregators, given each command she must be able to predict how the Aggregator will react. I.e., what are the Aggregator's capabilities in time step T+1 given a direction D in time step T?

Due to the complexity of the Aggregator, I think it's likely best to create an estimator across the current state of the Aggregator (or all of their followers). Further, the Aggregator can give whatever knowledge it wants to the Director, though ideally this would be of constant size no matter the size of the set of Followers. This is therefor an optimization problem on the Aggregator's side for creating an optimal estimator, which is well studied.

What I want to know: Is there any literature about creating an estimator when you know the exact function you are estimating? So if I am the aggregator, how can I tell the Director, in a constant space for the amount of information I give no matter the number of followers, the information require to best predict I would react to a given direction?

Put another way: How can I create an optimal estimator in which I have full knowledge of the shape and composition of the functions I am estimating?

I can think of a number of places where this might occur, potentially in networking, data compression, etc., though I think I don't have the necessary vocabulary. I've tried searching through aggregation, optimization, estimation, forecasting, prediction, which a number of different combinations of keywords relating to these. There is a ton of generalized work on making estimators and predictors, though none which target the assumption that they already have perfect knowledge of that which they're estimating.

Is there any literature about creating an estimator when you know the exact function you are estimating?

I think streaming algorithms may be of interest to you. A streaming algorithm is an algorithm that operates on some model of a massive 'stream' of data that is simply impossible to completely store, but it is possible to traverse it and do some computations with bounded memory. Often, it is impossible to solve even simple computations with bounded memory, but answers that are correct with high probability can be found efficiently, with techniques as random sampling, aggregating medians or probabilistic data structures.


Is {xy | x, y ∈ Σ∗ and x contains more a’s than y} regular? I've been asked to write a DFA for:
$\{xy\mid x, y \in \Sigma^*\text{ and }x\text{ contains more }a\text{’s than }y\}$ where $\Sigma=\{a,b\}$.
I don't believe this is possible. Can anyone confirm if this is not a regular language so that I'm not wasting my time if I'm correct.
Edit
Thinking again, while it's impossible to track exactly how many $a$'s are in $x$ or $y$ respectively, we know $x$ must have the number of $a>0$ at the very least and that the number of $a$'s in the string cannot be 2 since the condition of 'more' $a$'s has to be satisfied. Can you just write a DFA accepting strings with inputs containing 1 $a$, and 3+ $a$'s to satisfy the language?

Since the language does not specify what $x$ and $y$ are, you can always let $y=\varepsilon$, i.e., the empty string, then the language only requires $x$ to contain at least 1 $a$. So equivalently, the language is

$\{x\in\Sigma^*\mid x\text{ contains at least 1 }a\}$.

Now it is easy to build a DFA to accept this language.


Maximize rental income given a set of date intervals Suppose you have 1 room that you want to rent out. (AirBnb style) You want to maximize profits that you will get by renting it out.

For example:
Given intervals: [[1, 10], [2, 5], [7, 20], [23, 30]] - you could rent it out [2, 5], [7, 20] and [23, 30]

Another example: ([[1, 2], [1, 11], [5, 8], [4, 33], [18, 72]]) = 66

Note: Start and end times of the interval are inclusive

I implemented a brute force solution to this problem. First I sort by start time, then I create all possible subsets and take the longest possible value. This works. But I want to do this using Dynamic programming.

This problem screams DP, but I am not able to figure out if this has an optimal substructure.

My recurrence relation: f(i, j) = f(i + 1, j) or f(i + nums[i], j) if nums[i].start > f[i].end

Can someone help me figure out the thought behind the dp solution for the sub-problem?

Note: this problem is slightly different from job scheduling.

The most common subproblems where a particular subsequence should be selected are parametrized by the index of the last element selected. The classical, simple and brilliant example is Kadane's algorithm.

Let the given intervals are $I_1, I_2,\cdots, I_n$, where $I_j=[l_j, r_j]$.

The subproblem $DP[i]$, where $1\le i\le n$ is the maximum rent if the last interval rented is the $i$-th interval. The answer is $\max_iDP[i]$.

We could add an artificial base case, $DP[0]=0$, which says that the maximum rent is 0 if there is no interval rented.

The recurrence relation is
$$DP[i] = \text{Length}(I_i) + \max_{r_j\lt l_i} DP[j].$$

That is it, basically. There is a minor problem with the above recurrence relation, however. When we compute $DP[i]$, not all of $DP[j]$ with $r_j\lt l_i$ has been computed. I will leave it for you to resolve this minor obstacle.


Normalising fractional numbers For example $-\tfrac9{16}$.

$$\tfrac{9}{16} = \tfrac{1}{16}+\tfrac12 = 0.1001\,,$$
which when normalised becomes $0.1001\times 2^0$. Can its mantissa be $0.0001001$ in 8 bits?

If so, as $-\tfrac9{16}$ is negative, twos' complement is done to make its mantissa $1.1110111$.
How do we normalise that?

Not clear of your process, but here is how it can be done:
$\tfrac{9}{16} = \tfrac{1}{16} + \tfrac12$,
which gives you $0.1001$ in binary form. To normalize, take the first bit to be 1, which gives you $1.001 \times 2^{-1}$ which makes 3 bits for the mantissa $001$ and some bits for the exponent to represent $-1$ in twos' complement.

IEEE floating point formats don't use twos' complement for negative mantissas: they use an extra bit to indicate the sign (1 means negative).

So in the end, if exponent is 4 bit (and without any excess exponent): $1\,1111\,001$.


Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$ The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem

For instance, the Arora-Barak book explains the theorem using $g(n) = n$ and $G(n) = n^{1.5}$ - but, I can see that $n \in o(n^{1.5})$ as well! So, I'm trying to better understand what "extra" time is guaranteed by specifying that in order for $\text{NTIME}(g(n))$ to be a proper subset of $\text{NTIME}(G(n))$, $g(n + 1) = o(G(n))$, not $g(n) = o(G(n))$...

One example is $g(n) = 2^{2^{n-1}}$, $G(n) =2^{2^{n}}$.

We have $g(n) = \sqrt{G(n)}$, so $g(n) = o(G(n))$.

Meanwhile, of course, $g(n+1) = G(n)$ so $g(n+1) = \Theta(G(n))$, so $g(n+1)\neq o(G(n))$

Why double exponential?  When we add one to $n$, we want the effect to be more than a multiplicative constant (because big $O$ notation hides multiplicative, and therefore additive constants).  Let's make it simple and say that we want adding 1 to $n$ to have a polynomial effect on the value of $g(n)$.  When you add a constant to $n$:

a linear function is increased by an additive constant
an exponential function is increased by a multiplicative constant
a double exponential function is increased polynomially (by a power of two in our example, hence $g(n)^2 = G(n)$)

We can also have $g(n) = n^n$, $g(n) = n!$, etc., where $G(n) = g(n-1)$.  In general we can let $g(n) = f(n)^n$, where $f(n) = \omega(1)$ and $f$ is nondecreasing.  Then we have:

$$\lim_{n\to\infty} \frac{g(n)}{G(n)} = \lim_{n\to\infty} \frac{g(n)}{g(n+1)} = \lim_{n\to\infty}\frac{f(n)^n}{f(n+1)^{n+1}} \leq \lim_{n\to\infty}\frac{f(n)^n}{f(n)^{n+1}} = \lim_{n\to\infty}\frac{1}{f(n)} = 0$$

So we've shown $g(n) = o(G(n))$ using the limit definition (the last step is because $f(n) = \omega(1)$).  Therefore, functions like $(\log\log n)^n$ and even $\alpha(n)^n$ where $\alpha$ is the inverse Ackermann function, will do the trick for us as well.


Can I use Θ if tightest lower and upper bound are not the same? When analyzing the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same, is it bad to denote the running time in theta notation? If an algorithm has a running time of $\Theta(n)$, is it safe to assume that the upper and lower bound are the same?

When analyzing the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same, is it bad to denote the running time in theta notation?

Do you mean to say that we can only prove an $\Omega(f_1)$ and an $O(f_2)$ bound, respectively, on the same cost function (such as "worst-case running time)? Then yes: you can only use $\Theta(f_1) = \Theta(f_2)$ to combine the bounds if, well, $f_1 \in \Theta(f_2)$.

If you mean to say that best case and worst case have different growth rates, then that's a different issue: "lower bound" and "best case" as well as "upper bound" and "worst case" are not the same concepts! You can have $\Theta$-bounds for either case, but they still don't combine in a meaningful way since they are talking about different cost functions.

  Also, if an algorithm has a running time of theta(n), is it safe to assume that the upper and lower bound are the same?

That's not a "safe assumption", that's the definition of $\Theta$.

I suggest you revisit the definitions of the different Landau symbols and the basics on how to use them in algorithm analysis. Maybe start reading at our reference question.


Is it theoretically exist a computer that never affected by computer virus? Is it theoretically exist a computer that never affected by computer virus?

just wonder if there could be a revolution on the computer?

Do you mean "that cannot be affected" or "that was never affected"?
Then, under what conditions? Do you mean malware in general or a more
restrictive notion of virus? And then, what is virus or malware? Is
code for automatic update of your OS considered malware or not? Maybe
you do not want to update your OS. Maybe someone has taken control of
the updating service to introduce undesirable features in your system.

The main problem with your question is probably the word
"theoretically". What is a theoretical computer?  If it is a Turing
Machine, the answer is clearly yes: they do what their finite control
says they should do. Period.

Is there a fully precise theoretical model of a real computer. That is
doubtful, if only because it is a complex physical objet and there is
a limit to our ability to fully model such an object, since
our knowledge of physics is not complete ... though I doubt that is
the main issue.

Assuming we could completely model the physical computer with a formal
system, do we fare better? Now we have (or shall have) all these great tools for
proving theorems about computers and programs. But this has limitations too. Gödel
says that not all true facts are provable, especially in a theory that
can model that much computation. But even without falling in this
black hole, do we fare better?  No because before proving anything
about the computer we need to model precisely what a computer is, and
also what it means to be affected by a virus. Even if we have a
perfect and total proof system (which we do not), how do we prove that
our theoretical specification of the problem is accurate with respect
to the physical problem with real computers. Bugs are not the
exclusive privilege of programs and proofs, you can also have them in
specifications, and some may be hard to eradicate. If your child
specifies he wants a train as a gift when it is actually a car that he
wants, what are the formal tools that will identify the specification
error - short of implementing and observing that things do not behave
as expected.

Coming back to a more practical view. Some machines are harware
protected with encryption keys that allow only trusted software.
First, many people consider this as malware by itself, as it is often
used against the owner of the computer. Then encryption can be
broken by mathematical or social means. And the protection may possibly also be circumvented by other means.

A computer that stays off-line and does not access foreign data is
unlikely to be affected. Then, there are different ways of accessing
foreign data that may be more or less risky. Using foreign code is
likely to be more risky. So the question cannot be independent of
defining  the conditions in which the computer is used.

However, even off-line, there is always the risk that the computer was
born affected by malware (to avoid the restrictive concept of virus).

You should read Ken Thomson's 1984 Turing lecture: Reflections on
Trusting Trust.

Either you trust others to some extent, or you rebuild most of the
technology from scratch by yourself, with no interference from others. May be not starting at stone age, but far enough ... assuming you do not have bugs in your own code (but if not intentionally malicious, they are less likely to be as much a problem).


Floating point format: why must `1−emax ≤ q+p−1 ≤ emax`? From the Wikipedia page on the IEEE Standard for Floating-Point Arithmetic,

  The possible finite values that can be represented in a format are determined by the base (b), the number of digits in the significand (precision, p), and the exponent (q) parameter emax:

  ...

  q must be an integer such that 1−emax ≤ q+p−1 ≤ emax (e.g., if p=7 and emax=96 then q is −101 through 90).

I can't figure out the reasoning behind the above inequality. I would've thought (in my simplicity) that it would be -emax ≤ q ≤ emax or something similar. What am I missing?

The reason we get a larger range is denormalized numbers. Generally speaking, floating point numbers have three physical parts: sign (1 bit), mantissa $M$ and exponent $e$. Most of the time we think of the number as $\operatorname{sgn} \times 1.M \times 2^{e-e_0}$, where $e_0 = 2^{|e|}-1$ (e.g. for single precision, it's 127, since the exponent is allotted seven bits). Here "$1.M$" means the number you obtain by writing $M$ as a binary string and prefixing $1.$.

For reasons having to do with underflow (non-zero numbers turning to zero), it is important to be able to store numbers very close to zero. These numbers, named denormalized numbers or subnormalized numbers, have $e = 0$ and represent $\operatorname{sgn} \times 0.M \times 2^{1-e_0}$. (This means that normal numbers cannot have $e = 0$.) This explains the extended range mentioned in the Wikipedia page.

Other numbers having special encodings are $\pm \infty$ and NaN (not a number), which represent some illegal operation (division by zero, taking the logarithm of a non-positive number, taking the square root of a negative number, and so on). For more details, consult the Wikipedia page regarding the original standard.


Fastest algorithm for connectivity problem Let $G = (V,E)$ be any undirected graph. Let $k$ be some number and $C = |u \longrightarrow v|$ where $u \longrightarrow v$ means there is a path from $u$ to $v$. We want to add $k \subseteq V \times V\ E$ edges into $G$ such that $C$ is maximised in the new graph.
Question : What is the fastest algorithm for this problem?
I can solve the above problem in $n^{O(k)}$ time by brute force method.

If I understand you correctly, you want to maximize the number of pairs of vertices that are connected.
In a connected (undirected) graph, all vertices are reachable from each other, so the number is always $n^2$.
You can always connect to components with an edge by placing it arbitrarily between the components, and this will increase the number from $a^2 + b^2 \leq (a+b)^2$ to $(a+b)^2$.
If $a \geq b \geq c$, then
$$(a + b)^2 - a^2 - b^2 \geq \max((b+c)^2 - b^2 - c^2 , (a+c)^2 - a^2 - c^2).$$
It follows that the optimal solution is to iteratively connect the two largest components in your graph, which corresponds to, given $k$ edges, connecting the $k+1$ largest components of your graph.
Finding the $k+1$ largest components can be done in $O(n+m)$ time.


Electrical resistance of expander graphs Let $G$ be a $d$-regular expander graph. What is the electrical resistance of $G$? Is it a constant independent of the number of nodes $n$ once $d$ is large enough? If not, can we give matching upper and lower bounds in terms of $n,d$?

Next time you ask a question you should try to google it first. I googled "electrical resistance expander graph" and the very first result was a paper stating that $d$-regular graphs have resistance $\Theta(1/d)$.


Find isomorphism of graph with maximal number $x$ such that $f(x)\neq x$ - assuming $NP=P$ For $f : V → V$ which is authomorphism of directed graph $G = (V, E)$,
  $$\#f = |\{v : f(v) \neq v\}|$$  For graph $G$ we denote:   $$\#G =
 \max\{\#f : \text{$f$ is isomorphism $G$} \}$$

  Prove that if $P = NP$ then function $G\to\#G$ is polynomially
  computable.

My problem is that I can't think about isomorphisms. I know that thanks to assumption in polynomial time I can check if two graphs are isomorphic. The problem is however that I can't generate candidate for checking it.

Consider the decision version of computing $\#G$:

$L=\{(G,k) | \text{$G$ has an automorphism $f$ with $\#f\ge k$}\}$

$L$ is obviously in NP (an automorphism $f$ with $\#f\ge k$ is a witness). If $\mathsf{P=NP}$ then $L\in P$, and you can compute $\#G$ in polynomial time using binary search.


Can one reduce a problem of unknown complexity to a hard problem to show hardness? In this paper (page 3 Theorem 1) the authors want to prove that their problem is NP-complete. Their method is as follows. Let their problem be known as $P$. They show that their problem can be written as a $0\text{-}1$ integer program. Then they claim that $0\text{-}1$ integer programs are NP-complete and therefore their problem $P$ is NP-complete.

I find this proof hard to believe. For the problem $P$ to be NP-hard I think one has to reduce the $0\text{-}1$ integer program into an instance of problem $P$ and not the other way around.

Please can someone explain if this proof in the paper is acceptable?

The proof is not correct.  As you've indicated the reduction needs to go in the other direction, i.e. integer programming must be reduced to their problem, not the other way around.


What is the meaning of 'breadth' in breadth first search? I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this:

  Breadth-first search is so named because it expands the frontier
  between discovered and undiscovered vertices uniformly across the
  breadth of the frontier.

However, I'm not able to understand the meaning of this statement. I'm confused about this word "frontier" and breadth of that frontier.

So, can someone please answer this question in a way which is easy to understand for a beginner like me?

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue.

The “frontier” is the set of all nodes in the search data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always pop the most recently discovered state off of the stack, thus always iterating over the deepest part of the frontier.

Consider the image below. Notice how the DFS goes straight to the deepest parts of the tree whereas BFS iterates over the breadth of each level.

Image here


Why multiple rotations might be needed after deletion in an AVL tree if after insertion there can be at most one needed? I understand that after deletion you have to retrace to update ancestors and after insertion you do the similar however at most one rotation will be performed.

The question is why is there the difference in number of potential rotations for these two operations.

To me it seems like these operations should be the reverse of each other but this difference in their properties suggests they're not. Why?

Adding one element to a set, versus deleting one element from a set, are indeed rather symmetric operations. You are right.

However, in the case where the sets are represented by a tree, the two operations turn out to be asymmetric. When adding an item one branch may be too long, and one well-chosen rotation will rebalance. When deleting an item one branch may be too short, and the local rotation needed to rebalance will change the height of the current tree, so we may be forced to repeat rotating at other spots.

So it seems that "too long" and "too short" are not symmetric for tree rotations.

There are various other set representations that are not symmetric with adding and deleting.

We can keep sets as unordered arrays. Adding is easy, just put a new item at the end. Deleting is slightly harder. Assuming we have actually found the item, it is removed in the array, and then the last item is moved to the open spot.

We can also keep sets as hash-tables, with open adressing. Then adding has a standard solution, but deleting is hard, as doing it in the naive way may make other items untraceable (when we have a method other than linear probing).


Algorithm to find the probability of a given text to be about a large topic I want the conditional probability for each topic (being the word that we give as input). For example, the text being

  have seen and reviewed your requirements you posted here.  If you can
  give me the fix criteria/category of your data mining then I can do
  this job. If you want me to define and allot criteria and categorize
  it in then charges will be extra for per categorization included.

  I have seen and reviewed your requirements you posted here.  If you can give me the fix criteria/category of your data mining then
  I can do this job. If you want me to define and allot criteria and
  categorize it in then charges will be extra for per categorization
  included.

Assume that I give a word called research as an input, I want to know

What is the likelihood/probability that the text relates to research?

What algorithms we should create to get the above?

You can try simple probabilistic graphical models, the simplest one being Naive Bayes.

One way to do this would be to represent a portion of text as a word frequency vector, that will be associated with a topic (the "class variable"). Then you use many such texts that are associated with topics to train your model (i.e. you model the probability of a frequency vector given a certain topic). Finally, given a new text you can ask what is the most likely topic assignment.

Naive Bayes, the simplest graphical model, would miss dependencies between the frequencies of the various words, but it is worth a shot as it is easy to implement. More complicated models could be used to capture these dependencies.


Minimum number of ways to write a string Consider the following question

There are K magical pens (numbered 1 through K). You are given strings P1,P2,…,PK (each of which consists of characters from 'a', 'b', …, 't') ; for each valid i, the i-th pen can only write letters from the string Pi

.

You want to write a word S
of length N. All the characters of S are between 'a' and 't' inclusive. This string must be written from left to right. To write it, you pick up some pen and start writing; after you've written some prefix of S, you can put down that pen, pick up another pen, continue writing S from the point where you put down the previous pen, later pick up another pen (any pen) and continue writing S with that pen, and so on until you write the whole string S
You may pick up each pen any number of times, including zero.
You have to find a way of writing the word S
such that the number of times you change the pen (put down the pen you're currently writing with and pick up another) is the smallest possible. If there are multiple solutions, you may find any one. It is guaranteed that it is possible to write S with the given pens.

I know that to represnt a pen as a number using bitset and solve it ,but how can i solve it
faster.

Link for the question https://www.codechef.com/ICPCIN19/problems/PENS

First observation: As first pen you can always take a pen with which you can write the longest prefix.

Let's consider given pen-strings as bit stings. For each such bit string let's generate all substrings which correspond to subsets of an initial bit string and put them in hashtable. Moreover, let's generate them in descending (by nesting) order and when we generate some bit string which is already in hashtable, we terminate this branch of recursion. So each of $2^{20}$ possible bit strings will be generated at most twice.

Precompute for each prefix of string $S$ the number of times $i$-th letter occurs in it.

Then let's walk by string $S$ from left right and on each step let's check whether current prefix can be written with a single pen. We can do it in $O(1)$ using precomputed hashtable and prefixes.

So the overall complexity is $O(2^\alpha + K + N\cdot\alpha)$, where $\alpha$ is an alphabet size ($20$ in our case).


How to validate a connect X game (Tick-Tak-Toe,Gomoku,...)? Currently I am working on a Gomoku AI (or generally Connect-X games).

Implementing the search tree was no problem, but then I got to the point where I had to implement the value function and was surprised how difficult this is to make with a decent performance.

My question is what is the most efficient algorithm to check for a win in a connect-x game.

So basically I tried 2 things:

Firstly I created an Array where I saved all board coordinates (at compile time) into a 1D Array. This means all rows,cols and diagonals point for point and traversing this array and checking the corresponding on the actual board until (if any) a X long sequence was found.

My second approach was to calculate all patterns (horizontal,vertical,diagonal) with X points each at compile time (with Template-Meta-Programming) and traversing only those for each point played on so far and terminating if any member of the sequence was missing.

The first approach was way too slow and the second one was too complex for this problem I think.

What algorithm suites this problem best?

One approach that may be useful is to represent your field by a matrix and use a matrix vector product to test whether there is a winning position. Suppose we are playing connect $3$ and are testing whether player $A$ wins by a horizontal row, in this field:

A A A _ B
B _ _ B _
B B _ B A
A A _ A A

Construct a matrix $M$ by representing player $A$'s pieces by $1$, player $B$'s pieces and empty fields by $0$:

$M = \begin{pmatrix}
1 &1&1&0&0\\
0 &0&0&0&0\\
0 &0&0&0&1\\
1 &1&0&1&1\\ \end{pmatrix}$

Now, multiply the matrix by the vector $v=(1,2,4,8,16)^T$:

$Mv = (7,0,16,27)^T$. As we are looking for adjacent $1$'s, we see that there is a value in $Mv$ equal to $7$ ($=1+2+4$), $14$ ($=2+4+8$), $28$ ($=4+8+16$), $15$ (=$1+2+4+8$), $30$ ($=2+4+8+16$) or $31$ ($=1+2+4+8+16$).

Since the first entry of $Mv$ is equal to $7$, we know there is a row of three $1$'s there.

In general, for a $k\times n$ size grid, we take the vector $v=(1, 2,4,\ldots , 2^i,\ldots, 2^n)^T$ and know that there is a connected line of length at least $x$ when any of the values $\{\sum_{i=j}^{j+y} 2^i \mid 0\leq j \leq n-y, x\leq y< 2x\}$ are present in the vector $Mv$. (we can take $y<2x$ as when $y\geq 2x+1$, there must have been a row of length $x$ already on the field)

To test for columns, we can simply take the transpose of the matrix.

To test for diagonals, rotate the field such that they become rows and add padding to construct a rectangle: e.g. given our playing field above, a rotation for a diagonal would be:

_ B _ _
_ _ _ _
A B A _
A _ B A
A _ _ A
_ B B _
_ B A _
_ A _ _

(Note that it doesn't matter whether we place the padding to the left or the right, as we only check rows)


What kind of optimization problem this belongs to? Supervised learning is: given $X$ and $Y$, we want to find a good predictive function $f$ such that $f(X)$ is "close" to $Y$. Examples include XGBoost (ensemble of decision trees), neural networks, $\ell_1$-regularized linear fit, etc.

In the problem I am encountering I have $X$. Each row of $X$ describes each day's scenario, for example, the financial market descriptors of that day. I don't have $Y$. $Y$ is the decision for each day, for example, whether I should buy/hold SP500. For each $Y$, I will have some scoring, say score(Y) system to describe whether my decision is good over a long period of time. Now, I want to find simple, robust $f$ such that $f(X)$ gets the low score. Of course, for arbitrarily complex $f(X)$, the score score(f(X)) can be very low but the higher complexity generally means worse model for the problem I am tackling on. So there should be some regularization parameter that I could tune to control the complexity of $f$. The $f$ can be anything, like supervised learning. It could be ensemble of decision trees (XGBoost, random forest, etc...), linear (L1-regularized fitting etc.). I am currently essentially hard coding my problem into a optimization problem to solve on. But I think there should be a field out there tackling such problems.

If so, what is this type of problems generally called. And what's the state of the art packages currently in python. Thank you.

Yes, many standard methods can handle this.  Your score is called a loss function.  In particular, let $\ell(x_i,y_i)$ denote the penalty (score) if on input $x_i$, your decision rule outputs $y_i$.  If $x_1,\dots,x_n$ is a training set, we define the total loss over the training set (the empirical risk) of a decision rule $f$ to be

$$L(f) = \sum_{i=1}^n \ell(x_i,f(x_i)).$$

Now your goal is to find $f$ that minimizes the total loss $L(f)$.  Many machine learning algorithms can be used in this manner, with an arbitrary loss function.  Typically, we require that the loss function be differentiable, and then we use gradient descent to find $f$ that minimizes $L(f)$.  For instance, if you are using neural networks, then you use gradient descent to find weights for the neural network that minimize $L(f)$.  Often you add a regularization term to the loss function, too, to prevent overfitting.


Examples of context sensitive syntactic constructs (statements) So, I am implementing a context sensitive syntactic analyzator. It's kind of an experimantal thing and one of the things I need are usable syntactical contructs to test it on.

For example, the following example isn't possible to parse using standard CFG (context free grammar). Basically it allows to declare multiple variables of unrelated data types and simultaneously initialize them.

int bool string number flag str = 1 true "Hello";

If I omit few details, the language used can be formally described like this:

L = {anbncn | n >= 1}

So, I would appreciate as much of similar examples as you can think of, ideally something from the area of programming languages.

Also, I am aware that current programming languages and their compilers are context sensitive, mainly thanks to semantic analysis, so I would like to state I am not looking for things like:

type checking
is variable declared?

I would preffer the examples to be actual syntactic constructs like the shown declaration example above.

Thanks in advance ;).

Here are three context-sensitive syntaxes actually found in programming languages. I don't believe I've ever seen a language which has types, names and values distributed as per your example, but it could certainly exist, and I'm sure there are even less readable syntaxes which are possible. The following are at least somewhat readable:

Syntactic whitespace, as per Python or Haskell. This is usually handled with a context-sensitive lexical scanner rather than a context-sensitive grammar, but it is certainly context-sensitive, and it could be handled with a context-sensitive grammar if you had the machinery available. (In fact, it could be cleaner to handle it in the parser, especially for languages like Haskell in which layout-sensitive parsing is optional. [Note 1])
Multi-dimensional array literals. Here, I'm not talking about languages which implement heterogeneous one-dimensional arrays as first-class types, so that an array can be an element of another array; in that case, there is no requirement that a multi-dimensional array be regular. Rather, I'm talking about languages in which multi-dimensional arrays must be regular, and so an irregular literal is a syntax error:

julia> [2 3 4;5 6 8]
2x3 Array{Int64,2}:
 2  3  4
 5  6  8

julia> [2 3 4;5 6]
ERROR: hvcat: row 2 has mismatched number of columns
 in hvcat at abstractarray.jl:993

That's a bit of a cheat, because the Julia syntax above is really syntactic sugar for a call to hvcat, as indicated in the error message. But it could have been syntactic. Fortress -- the syntactic collector's favourite vapourware language -- proposed syntactic array literals:

  The parts of higher-dimensional matrices are separated by repeated-semicolons, where the dimensionality of the result is equal to one plus the number of repeated semicolons. Here is a 3 x 3 x 3 x 2 matrix:

[ 1 0 0
  0 1 0
  0 0 1   ;;   0 1 0
               1 0 1
               0 1 0   ;;   1 0 1
                            0 1 0
                            1 0 1
  ;;;
   1 0 0
   0 1 0
   0 0 1   ;;   0 1 0
                1 0 1
                0 1 0   ;;   1 0 1
                             0 1 0
                             1 0 1 ]

  The elements in a matrix expression may be either scalars or matrices themselves. If they are matrices, then the elements along a row (or column) must have the same number of columns (or rows), though two elements in different rows (columns) need not have the same number of columns (rows). A scalar is treated as a one by one matrix. (Quoted from The Fortress Language Specification by Guy L. Steele et al, §2.3.19, p. 21)

Agreement between parameter count in function prototypes and number of arguments in function calls. Perhaps this fits in your concept of "type checking", and I don't think it adds anything interesting to your problem set. But it is certainly context-sensitive.

Notes

I stumbled upon Layout-sensitive Generalized Parsing by Sebastian Erdweg, Tillmann Rendel, Christian Kästner, and Klaus Ostermann. while writing this answer, but I haven't read it. It seems to propose a usable formalism for layout-aware parsing.


Complexity of an algorithm I tried to solve the following exercise :
What is the order of growth of the worst case running time of the following code fragment
as a function of N?
int sum = 0;
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= i*i; j++)
        for (int k = 1; k <= j*j; k++)
            sum++;

and I found that the complexity is O(n^4), however the correct answer is  :

The answer is : N^7
For a given value of i, the body of the innermost loop is executed 1^2 + 2^2 + 3^2 + ... + (i^2)^2 ~ 1/3 i^6 times. Summing up over all values of i yields ~ 1/21 N^7.

I would like some help to understand this answer and the correct way to calculate complexity in this case.

It will be easier to analyze things if we break them down into several different procedures:

int I(int n) { for (i = 1; i <= n; i++) J(i); }
int J(int n) { for (j = 1; j <= n*n; j++) K(j); }
int K(int n) { for (k = 1; k <= n*n; k++) sum++; }

Instead of measuring time complexity, let us use instead the number of times sum is incremented as our complexity measure. Also, let $I(n),J(n),K(n)$ double as the complexity of the functions with matching name.

It is not hard to see that $K(n) = n^2$. Therefore
$$
J(n) = \sum_{j=1}^{n^2} K(j) = \sum_{j=1}^{n^2} j^2.
$$
Now we invoke the formula $\sum_{j=1}^m j^2 \sim m^3/3$. Substituting $m = n^2$, we get
$$
J(n) \sim \frac{n^6}{3}.
$$
Continuing,
$$
I(n) = \sum_{i=1}^n J(i) \sim \frac{1}{3} \sum_{i=1}^n i^6 \sim \frac{1}{21} n^7.
$$
Some of these estimates are not completely rigorous, but you can make them rigorous with a bit of work.


How does equality works for qubit-vectors? A bitvector of length N has 2^N different values. How many different values has a quantum bit vector of length N? Is it possible to test two quantum bit vectors for equality?

The state of an $n$-qubit system is defined by $2^n$ complex numbers. Basically the numbers are weightings for each of the classical $n$-bit states, similar to a probability... but square-rooted.

Technically, two quantum states are equal only if all of those weights are equal. But, when it comes to the practical aspects of quantum computing, it's better to focus on continuous concepts like distance rather than discrete concepts like equality because we only get very indirect access to the weights.

For example, quantum mechanics places pretty strict limits on how well you can compare two states. If the vectors defined by the amplitudes of state $a$ and state $b$ are an angle $\theta$ apart, then the chance of any QM process correctly distinguishing between them is upper-bounded by $\frac{1}{2} + \frac{1}{2}|\sin \theta|$ or equivalently $\frac{1}{2} + \frac{1}{2}\sqrt{1 - |\langle a | b\rangle|^2}$ (look up 'Trace Distance'). Distinguishing is strictly easier than equating, and we're already failing probabilistically at distinguishing! That's why people focus more on the distances.


Is this passage from the textbook Artificial Intelligence: A Modern Approach incorrect? On page 383, section 10.2. of the Algorithms for Planning as State Space Search chapter of the textbook Artificial Intelligence: A Modern Approach, the following passage appears:

In this passage, the authors write that in the air cargo example they use there are $50^{10} \times 200^{50+10} \approx  10^{155}$ states.

Is this incorrect? Shouldn't there be $10^{50} \times 60^{200}$ states?

As far as my understanding of probability goes, there is a different state for all the different arrangements of the 50 planes, which can each be at one of 10 airports, which would give the result $10 \times 10 \times ... = 10^{50}$, and then the same reasoning applied to the placement of the packages on an airplane or at an airport gives $60 \times 60 \times ... = 60^{200}$, which together give  $10^{50} \times 60^{200}$.

Is the textbook incorrect or is my reasoning incorrect?

Yes.  You are right.  That looks like an error in the textbook.  Check their errata, or send the authors a note to let them know.


Is a door lock a finite state machine? 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.

Yes and no. Arguably, the lock is not a finite state machine, since the key can be inserted to any degree and, if it fits, rotated through any angle. However, we can abstract away these unimportant details, yes, the system can be modeled as a finite number of states: essentially, if you code up the ridges of the key as symbols in some alphabet, the lock is a DFA that accepts exactly one word (or perhaps more, if there's a master key).


What does it mean when each individual array is sorted in different array but bear no relationship to each other There's a textbook problem that talks about making a binary search dynamic, then analyzing for its amortize cost. However I'm not exactly sure what is the organization scheme of this data structure.

Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays. Specifically, suppose that we wish to support SEARCH and INSERT on a set of $n$ elements. Let $k = lg(n + 1)$, and let the binary representation of $n$ be $\langle n_{k‒1}, n_{k‒2}, \ldots , n_0 \rangle$. We have $k$ sorted arrays $A_0, A_1, \ldots , A_{k‒1}$, where for $i = 0, 1, \ldots , k − 1$, the length of array $A_i$ is $2i$ . Each array is either full or empty, depending on whether $n_i = 1$ or $n_i = 0$, respectively. The total number of elements held in all $k$ arrays is therefore $n$. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other
(Excerpt From: Thomas H. Cormen et al., “Introduction to Algorithms: Third Edition.”)

What does this mean when we have a data structure with several sorted arrays that bear no such relationship? Does it mean that they all must be sorted relative to themselves, but not to the rest? If that's the case, when you try to perform an insert or delete, conceptually, how would you know which array to insert it to or to delete from, and how would it be reshaped?

What they mean is exactly that: the invariant maintained by the data structure is that each of the arrays $A_0,\ldots,A_{k-1}$ is sorted. Nothing is maintained regarding the relative order of elements in different arrays.

The text probably goes on to describe how to perform the search, insert and delete operations. The search operation is simple: you just search the individual arrays. To insert an element, there are two cases: if $n$ is even, we just add a new array $A_0$ with the new element. Otherwise, choose the smallest $i$ such that $n_i = 0$ (possibly $i=k$). We add the new element to $A_0$, and then merge $A_0,\ldots,A_{i-1}$ to $A_i$ (in this order: merge $A_0$ and $A_1$ to $B_1$; merge $B_1$ and $A_2$ to $B_2$; and so on). Element deletion is more complicated; the data structure is only supposed to support search and insert.

The key idea is that when inserting an element, it is we (the designers of the data structure) who choose where to put it.

The text probably goes on to analyze the amortized cost of these operations. I'll leave these details to the text. (Unless it's an exercise, in which case you should work them out!)


Combinational Logic Circuits and Theory of Computation I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything I have learned recently in Theory of Computation.

I was wondering whether combinational logic circuits can implement computations in the same way finite state machines can. They seem radically different :

Finite State Machines, however, have a well-defined memory in the form of the states that it can be in.   Combinational logic circuits, however, don't have a well-defined memory so to implement algorithms that need memory they kinda use some weird method of serial connection ( see how $C_{out}$ of previous adder is connected to $C_{in}$ of current adder in the image bellow ) .

However radically different might seem, they both seems to be doing computations. For instance, both can implement an algorithm for binary addition ( and even binary multiplication ) however different those implementations might be :

FSM :

Combinational Logic Circuit  (  C, as in $C_{in}$ and $C_{out}$, stands for Carry ) :

I'm even thinking ( although still very uncertain ) that we can convert every FSM into a corresponding Combinational Logic Circuit.

So, i'm asking myself :

Can Combinational Logic Circuits also be considered a instantaneous kind of model of computation ?  Can we apply all concepts we learn in Computability Theory and Computational Complexity Theory, like space complexity and computability, to it ?

On one hand, it seems like they don't fit as a model of computation because they don't have elementary operations ( like reading/writing of a tape,  function reduction,  steps on the proof search of logical programming paradigma ), they implement their computations instantaneously.
But on the other hand, they seem to be fit as a model of computation because we can model all kinds of computation with them ( binary addition is one example ), and they can be viewed abstractly ( by only focusing on the truth-tables and the logical gates and forgetting about the physical circuit that might implement it ).
So, what do you guys think ?

Also, if it can indeed be considered as a (instantaneous kind of ) model of computation, do you guys have any example of other similar ( also a instantaneous kind of ) model of computation ?

Thanks a lot in advance

Logic circuits are common in complexity theory, where they go by the name circuits. There is a big difference between circuits and models of computation such as the Turing machine: each circuit can only handle inputs of fixed size. In order to fix this, under the circuit computation model, for every input length $n$ there is a circuit $C_n$, and together they compute a function on strings of arbitrary length. This computation model, as stated, is too strong: it can compute uncomputable functions, indeed all functions. The problem is that an infinite sequence of circuits doesn't necessarily have a finite description. In order to fix this problem, we usually demand that the circuits be uniform, that is, that they be generated by some Turing machine, which on input $n$ generates $C_n$.

The circuit model is especially popular in complexity theory, even without the uniformity restriction. The reason is the following observation: a Turing machine running in polynomial time can be converted to a (uniform) sequence of circuits of polynomial size, using essentially the ideas of Cook's theorem (which shows that SAT is NP-complete). Hence if you want to prove that a certain problem cannot be solved in polynomial time, it is enough to show that it cannot be solved by polynomial size circuits.


File size and screen recording First and foremost, I would like an academic reference on how screen recording "works."
I have tried searching online, but I only get results for the software itself.

Exactly how does screen recording work, and to what extent does the content one records effect filesize?
For instance, if I were to record my screen playing an (x) resolution video, would the final output size be proportionally larger? Why or why-not?

If this question is closed, please, I would appreciate a reference, or a better way to phrase it (or a referral to a more appropriate sub-forum).
Thanks.

Conceptually, screen recording works by taking a screenshot of the screen many times per second.  Taking a screenshot works by taking a copy of what is displayed on the screen.  To understand how that works, you need to understand how things are displayed on the screen; for that, I recommend reading about framebuffers.  The screen capture might then be stored in a compressed or uncompressed format.  The file size will be influenced by the resolution of the screen, the length of the video, and what compression is used (if any).


Show that $(\log(n))^\alpha = O(n^\beta)$ I am trying to show that $\forall \beta \gt0, \log(n^\alpha) = O(n^\beta)$, however I cannot use the limit definition, as demonstrated in similar questions on the forum.
First I show that $\log(n^\alpha) = O(n)$, using the following method:
$\log(n^\alpha) = \alpha \cdot \log(n) \leq \alpha \cdot n$
Thus for $c=\alpha^\alpha, n_0=0$, we have $(\log(n))^\alpha \leq c \cdot n$ which implies $\log(n^\alpha) = O(n)$
Now I will show $\forall \beta \gt0, \log(n^\alpha) = O(n^\beta)$, we have two cases
$\beta \ge 1$: Since $\forall n \ge1, n\leq n^\beta$, then from the above result, for $c=\alpha^\alpha, n_0 = 1$, we have $\log(n^\alpha) \le c \cdot n^\beta$ which implies $\log(n^\alpha) = O(n^\beta)$
$0 \lt \beta \lt 1$: I can't seem to find a series of inequalities, as shown above, that prove $\log(n^\alpha) =O(n^\beta)$ in this case

You can use the following identities:
$$
(\ln n)^a \le n^\beta \iff \ln (\ln n)^a \le \ln n^\beta \iff
a \ln \ln n \le \beta \ln n.
$$
This is trivial if $\alpha \le 0$, so we consider the case $\alpha > 0$.
For simplicity substitute $t= \ln \ln n$ and $\gamma = \frac{\alpha}{\beta}$. Notice that $\gamma \ge 0$. We obtain:
$
\gamma t \le  e^t \iff \gamma t - e^t \le 0
$
To show that $\alpha t \le \beta e^t$ for sufficiently large $t$, we take the derivative of $h(t) = \gamma t - e^t$:
$$
h'(t) =\gamma - e^t.
$$
This shows that for $t \ge \ln \gamma$, $h(t)$ is monotonically non-increasing.
Moreover, for $t=\ln \gamma$ we already have $h(t) \le 0$, indeed $h(\ln \gamma) =\ln \gamma-\gamma \le 0$ since the logarithm is a monotonically increasing function.
Hence, in the definition of big-Oh with $n_0$ and $c$, we can pick $n_0 = \ln \gamma = \ln \frac{\alpha}{\beta}$ and $c=1$.


Simple interepretation problem regarding Polynomial Hierarchy? So $NP$ stands for problems where we have small verifiable witnesses for $YES$ instances and $coNP$ for small verifiable witnesses for $NO$ instances. How does this work for

$P^{NP}$
$NP^{NP}$
$coNP^{NP}$
and so on?

There is a logical interpretation of the various levels of the polynomial hierarchy, which extends the witness characterization of $\mathsf{NP}$ and $\mathsf{coNP}$.

A language $L$ is in $\Sigma_k^P$ if there is a polytime predicate $f$ and a polynomial $\ell$ such that
$$
x \in L \Leftrightarrow \exists |y_1| \le \ell(|x|) \; \forall |y_2| \le \ell(|x|) \; \cdots Q |y_k| \le \ell(|x|) \; f(x,y_1,\ldots,y_k).
$$
Here:

$\exists |y| \le \ell(|x|)$ means that there exists a number $y$ whose length is at most $\ell(|x|)$ such that ...
$\forall |y| \le \ell(|x|)$ mean that for all $y$ whose length is at most $\ell(|x|)$, the following holds ...
$Q$ is $\exists$ if $k$ is odd and $\forall$ if $k$ is even.

Similarly, $L$ is in $\Pi_k^P$ if it can be written in a similar way, only starting with $\forall$.

As an example, $\mathsf{NP}^{\mathsf{NP}}$ is $\Sigma_2^P$, and consists of all languages such that
$$
x \in L \Leftrightarrow \exists |y_1| \leq \ell(|x|) \; \forall |y_2| \leq \ell(|x|) \; f(x,y_1,\ldots,y_k).
$$
As another example, $\mathsf{coNP}^{\mathsf{NP}}$ is $\Pi_2^P$.

Your third example is $\mathsf{P}^{\mathsf{NP}}$, which is $\Delta_2^P$. I'm not sure what is the logical characterization.


What is google docs solution to handling multiple users editing and reading at the same time? I have always been curious as to how google solved the solution of real time collaboration in their google docs product where they allow multiple users to edit and read the same document in real time.

I believe this is very similar to the well known readers and writers problem.

In some of the solutions that i have seen, we would need a mutex of some kind whereby the writers will have exclusive lock to the document itself and readers will not be able to read the document at all.

But in the google docs case, it is quite interesting whereby another user can read the document in real time and two users can both edit the same document at the same time without any conflicts which is very impressive to me.

Note: there is no way to know how Google does it. All we can do is speculate based on whatever information is publicly available. If you want to know, you have to ask them, not us.

Google Docs' collaborative features are reportedly an offshoot of Google Wave. Google Wave, in turn, reportedly used Operational Transformation.

As a very high-level basic overview, the fundamental idea behind OT is that each collaborator has their own local copy of the document, and the editor infers an operational transformation based on the user's inputs. These transformations can be very simple (insert character x at position y) or more complex (perform an extract method refactoring of the second code block in method foo and name the resulting method bar).

These transformations are then broadcast to the other collaborators and applied to their respective copies.


ResNet output dimensions So I am currently going over the ResNet paper and trying to understand the output dimensions of each of the layer, and it seems that I am already stuck on the first layer and its output dimension.

If I understand correctly, the size of output of a particular layer can be calculated as (ORIGINAL_SIZE - FILTER_SIZE) / STRIDE + 1

In the plain example of the ResNet, presented below on the right hand side, they claim they use 224x224 image. Therefore, when I calculate the output dimension of the 7x7 convolution with stride 2, I get

(224 - 7) / 2 + 1 = 109.5, so I round it 110.

However, in the paper they claim that their output size is 112. How would that be possible?

I managed to find an official github repository, and they use a padding of size 3, and therefore the output 112.


What does the symbol "::" mean in computer science? What does the symbol $::$ mean in the following statement?

$\forall{x}\in K :: x \longrightarrow x$

A cycle in a graph is a path that starts and ends on the same node.
Clearly, if nodes in K lie on a cycle, then $\forall{x}\in K :: x \longrightarrow x$.

Look at page 56 in the following.

https://books.google.co.in/books?id=nel4vdeLcqkC&pg=PR7&source=gbs_selected_pages&cad=2#v=onepage&q&f=false

It is a delimiter between to parts of expression. You can think of it as notation for the English phrase 'such that'.
Read your formula as $`` \forall x\in K \text{ such that } x \longrightarrow x"$.


Parallel Algorithm for Data Averaging I am trying to write an efficient Parallelised algorithm for Data Averaging. By this I mean I have a list of tuples (K, V1, V2, V3) and in the end, I want a dictionary mapping K to the average of all V1, V2 and V3 present in the list with K.

If anyone can think of something it would be much appreciated.

Thanks,
Harris Mirza

The role of three values $V_1, V_2$ and $V_3$ isn't clear for me, but anyway:

Step 1. Sort the original list in parallel by key $K$ - you'll get a list of records $(K, V_1, V_2, V_2)$, where all the records with the same key are stored together in "buckets".
Step 2. Process each bucket concurrently, calculating all the averages.

There are many parallel sorting algorithms, you can choose one depending on your computational model.


an algorithm for detecting if noisy univariate data is constant or is sum of step functions In an explicit algorithm I'm writing, there is a certain stage where I need to determine whether or not a certain noisy univariate data is constant or is sum of step functions.

For example, defining foo as the algorithm I'm after (writing in Python):

assert foo([0]*20) == False
assert foo([0]*20 + [1]*20) == True
assert foo([0]*20 + [5]*30 + [1]*70) == True

- The data in the examples is not noisy, but assume the real one is (just a bit, one can pinpoint where a step might take place by observing the plot of the data.)

I'd be happy to hear any ideas.

Every possible observation is consistent with a sum of step functions: one can use one step function per data point and fit any possible sequence of observations.  So, the question is not well-posed.  You'll probably need to impose some kind of restriction or prior on the set of sum-of-step functions you're willing to accept (e.g., a sum of at most 3 step functions).

If you make the question well-defined, it might be answerable  in a principled way using maximum likelihood.  Let $\mathcal{H}_0$ denote the set of constant functions, and $\mathcal{H}_1$ the set of sum-of-step functions you are willing to accept (e.g., with a limit on the number of step functions you're summing).  Let $\vec{x}$ denote the observed data.  Fix a probabilistic noise model.  Let $L(f)$ denote the likelihood of function $f$, i.e., the probability of observing $\vec{x}$ given that the true underlying function is $f$.  Let $L(\mathcal{H}_0) = \max \{L(f) \mid f \in \mathcal{H}_0\}$ and $L(\mathcal{H}_1) = \max \{L(f) \mid f \in \mathcal{H}_1\}$.  Then a maximum-likelihood decision rule would be: infer that the underlying data is constant if $L(\mathcal{H}_0) \ge L(\mathcal{H}_1)$, otherwise infer that the underlying data is a sum of step functions.

To implement this, you'll need an algorithm to compute $L(\mathcal{H}_0)$ and $L(\mathcal{H}_1)$, which will in turn depend on the noise model.  Computing $L(\mathcal{H}_0)$ is likely to be straightforward for reasonable noise models; e.g., if you assume iid Gaussian noise, then $L(\mathcal{H}_0)$ amounts to computing the average of the data points, choosing a constant function that is always equal to that average, and computing its likelihood.  Computing $L(\mathcal{H}_1)$ (assuming you have a restriction on the number of step functions you'll accept) is a little trickier but is doable using dynamic programming.

From a pragmatic perspective, you might also be interested in changepoint detection.


How fast can we decide whether a given DFA is minimal? Minimizing deterministic finite automata (DFAs) is a problem that has been thoroughly studied in the literature, and several algorithms have been proposed to solve the following problem:
Given a DFA $\mathscr{A}$, compute a corresponding minimal DFA accepting the same language as $\mathscr{A}$.
Most of these algorithms run in polynomial time.

However, I wonder whether the decision variant of this problem - "given a DFA $\mathscr{A}$, is $\mathscr{A}$ minimal?" - can be solved more efficiently than actually computing the minimal automaton.
Obviously, this can also be done efficiently by running for example Hopcroft's partition-refinement algorithm and then deciding whether all partitions contain precisely one state.

As Yuval Filmus suggests in his answer, the decidability variant can be solved faster, possibly by using the standard algorithms.
Unfortunately, I cannot see how (I hope I am not missing an obvious point here).

Yuval points out in the comments here that the best known algorithms (like the one above) run in time $\mathcal{O}(n \log n)$ for constant-sized alphabets. Therefore, I am not only interested in asymptotically significant gains in runtime, as these seem rather unlikely. What bothers me most is that I cannot imagine any "shortcut" that might be drawn from the fact that we are only interested in a yes-no-answer - not even a shortcut that allows for saving an asymptotically negligible amount of time. I feel that every sensible algorithm that decides the minimality of a DFA would have to actually minimize the DFA and see if anything changes during the process.

This might not be exactly the sort of answer you are looking for, but since you asked about decision problems, I thought you might be interested in the complexity of the problem. It is $\mathsf{NL}$-complete.

Now, what does it mean for a DFA to be minimal? There are two properties:

Every state is reachable: $\forall q \in Q \; \exists w \in \Sigma^*$ such that we can reach $q$ from the start state $s$ by following $w$; in symbols: $s \rightarrow_w q$.
Every pair of states is distinguishable: $\forall q,r \in Q$ with $q \neq r$  $\exists w \in \Sigma^*$ such that $q \rightarrow_w s$ and $r \rightarrow_w t$ and $|\{s,t\} \cap F| = 1$ (only one of $s,t$ is an accept state).

Notice that the $x \rightarrow_w y$ can be computed in log-space (i.e. $\mathsf{L}$; just track your current position as you follow $w$ one letter at a time). Further, there is only a finite number of alternations between $\forall$ and $\exists$ so as a consequence of the Immerman-Szelepcsenyi theorem, we have that the problem is in $\mathsf{NL}$.

The easiest way to see that it is hard for $\mathsf{NL}$ is to notice that property 1 solves $s$-$t$ directed unreachability, which is the prototypical hard problem. But even if you consider only reachable DFAs, the problem is still hard (i.e. property 2 is $\mathsf{NL}$-hard) and you can find a relatively straightforward proof in Lemma 2.2 of Cho & Huynh (1992).

Of course, I used non-determinism, so it is a bit of a cough-out in the way it differs from Hopcroft's algorithm. But we know that $\mathsf{NL} \subseteq \mathsf{L}^2$, so you can use those constructions to get yourself a more space-efficient algorithm than Hopcroft (which by its very nature has to keep track of $n$ many partitions).


Decide whether there exists a walk of weight exactly k Consider the following problem:

Input: a directed graph $G = (V,E,\omega)$ where $\omega : E \longrightarrow \mathbb{Z}$, two vertices $v_1, v_2 \in V$, and a weight $k \in \mathbb{Z}$

Question: Does there exist a walk from $v_1$ to $v_2$ with weight exactly $k$?

The weight of a walk is simply the sum of all edges in the path. Note that the walk can contain cycles.

Is this problem decidable?  Is there any algorithm to solve this problem, if I don't care about the running time?  My problem is that since we can have edges weighted with either positive or negative integers, it is hard to determine when to stop or turn back when it gets too low or too high.

For example, given the graph $G$ where $V = \{ v_1,v_2 \}$ and $E = \{e_1:(v_1,v-1), e_2:(v_1,v_2)\}$ and $\omega(e_1)=-2$ and $\omega(e_2)=1$, the question could be is there a walk from $v_1$ to $v_2$ with weight $-99$. The algorithm should say yes, as there is a walk starting from $v_1$ and self looping 50 times over edge $e_1$ before taking edge $e_2$ and terminating.

I previously asked about the complexity of a similar problem here, but there I was focused on the complexity of the problem.  Others have shown that this problem is NP-hard.  Also, the previously question asked about a path, whereas here I am asking about a walk (a vertex might be visited multiple times); the version with paths is in NP and thus decidable, but here I am asking about walks rather than paths.

Notice that this problem is not trivial, largely because we are talking about walks rather than simple paths.  There is no a priori upper bound on the length of a walk from $v_1$ to $v_2$, so just enumerating all possible walks might never terminate.  Also, the graph could contain exponentially many cycles, and the walk might visit some of them any number of times.  And, there is no obvious upper bound on the number of times that we traverse any given cycle.  In particular, it is not obvious whether this problem is in NP or not.  A straightforward reduction to integer linear programming (an integer variable for each edge, counting how many times the walk traverses that edge) runs into the difficulty that it is not clear how to ensure that you have a walk and not a flow.

We start by converting your graph into an NFA $A$, by replacing the weights with strings. Positive weights $k > 0$ are replaced by $a^k$, negative weights $k < 0$ are replaced by $b^{-k}$, and zero weights are replaced by $\epsilon$ (the empty string). We make $v_1$ the initial state and $v_2$ the only accepting state. Consider now the context-free language $L_k = \{ w : \#_a(w) - \#_b(w) = k \}$. We construct a context-free grammar for $L_k \cap A$ and check whether $L_k \cap A = \emptyset$.

The size of the generated NFA is polynomial in $n + \sum_{ij} |w_{ij}|$ where $n$ is the number of vertices and $w_{ij}$ are the weights. The size of a grammar for $L_k$ is polynomial in $k$. In order to intersect it with $A$, we convert it to a PDA, use the product construction, and then convert back. We get a CFG of size polynomial in $n + \sum_{ij} |w_{ij}| + k$. Checking emptyness takes polynomial time, so the entire algorithm takes time polynomial in $n + \sum_{ij} |w_{ij}| + k$, showing that the problem is in NP if the weights and the target sum are encoded in unary (otherwise the bound we get is only NEXP).

Interestingly, this argument doesn't work for real weights. The natural extension would be to find a basis for the weights over $\mathbb{Q}$, clear off the denominators, and have a pair of symbols $(a_i,b_i)$ for each element in the basis. The argument fails since $L_{\mathbf{k}} = \{ w : \forall i \#_{a_i}(w) - \#_{b_i}(w) = k_i \}$ is not context-free if there is more than one pair of symbols.

  Is the problem with real weights (given as linear combinations over $\mathbb{Q}$ of some $\mathbb{Q}$-linearly independent set) decidable?


Pumping lemma for an involved non context free language Hi I'm trying to show $C=\{wzzw^R|w,z\in\{0,1\}^+\}$ is not a context-free language.( I have this believe because $C=\{ww|w\in\{0,1\}^+\}$ is not a context free language.) I'm really struggling to come up with a string that captures the essence of irregularity of this language: I tried strings like $s=1^p0^p1^p0^p1^p1^p$ but there are too many cases to deal with and most of the examples I saw only use 1 or 2 cases, so I believe the direction I'm going is wrong. Can you provide a hint on which string to pick as the 'pumping string'? Thank you.

Suppose that $C$ were context-free. Then the following language would also be context-free:
$$
C' = C \cap 0(100+110)^+0.
$$
What does $C'$ look like? Suppose that $x = wzzw^R$ belongs to $0(100+110)^+0$, where $z,w \neq \epsilon$. Note that the first two symbols of $x$ are $01$, and last two are $00$. This shows that $w = 0$, and so $zz$ belongs to $(100+110)^+$. Thus $|zz| = 3m$ for some $m \geq 1$. Since $|zz|$ is even, $m = 2k$, and so $|z| = 3m/2 = 3k$. Therefore $z$ belongs to $(100+110)^+$, and we conclude that
$$
C' = \{ 0 zz 0 : z \in (100+110)^+ \}.
$$
If $C'$ were context-free, then so would be the language
$$
0^{-1} C' 0^{-1} = \{ zz : z \in (100+110)^+ \},
$$
obtained by taking left and right quotients with $\{0\}$. Finally, if we define a homomorphism $h\colon \{a,b\} \to \{0,1\}^*$ by $h(a) = 100$ and $h(b) = 110$ then the following language would also be context-free:
$$
h^{-1}(0^{-1} C' 0^{-1}) = \{ zz : z \in (a+b)^* \}.
$$
Since this language is well-known not to be context-free, we conclude that so is $C$.


Exponential analogue of NC? Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors.

I want to know about the exponential analogue, which would cover problems that can be decided in polynomial time using an exponential number of processors.

What I'm looking for is a name for this class and any known relations between this class and other complexity classes, or any canonical problems for the class. It seems straightforward that it would contain NP and co-NP, and i think it is contained within PSPACE, but I'm not sure much else about it.

Time in circuits corresponds to the depth.
Therefore by polynomial time means polynomial depth.

The number of processors is the size of the circuit,
i.e. number of the gates in the circuit.
So by exponential number of processors you allow exponential size.
This would be the class $\mathsf{DepthSize}(n^{O(1)}, 2^{n^{O(1)}})$.
But every function is already in $\mathsf{DepthSize}(2, 2^{n^{O(1)}})$
(think of the CNF of the function you want to compute).

The take away is that exponential number of processors is
too strong to be useful by itself.

One reasonable restriction to put is to limit the amount of communication
between different processes.
E.g. we each process can only communicate with
only polynomially many other processes and the messages have polynomial size.
That would be $\mathsf{PSpace}$ as explained in answers to Aterm's question on cstheory.
Another way to see it to remember that
$\mathsf{PSpace} = \mathsf{ATime}(n^{O(1)})$,
problems computable by alternating Turing machines in polynomial time.
Alternation in Turing machines is essentially forking new processes and then joining after they finish by taking the conjunction/disjunction of their return values.


Show that only a few multiples of .01 decimal are powers of 2 I am asking this to advance the argument that BigDecimal is better than float or double for representing exact amounts of currency.

Can someone refer me to a proof that between any two integers there are only four values that multiples of .01 and can be exactly represented in base 2?  Or at least confirm I'm correct in my belief that it's true?

Hint: The four values are $25/100 = 1/4$ and its multiples.

If all you want to do is store an exact amount of currency, you can use an integer which represents the amount of cents. (This is known as fixed-point arithmetic.)


Multiplying intervals in Two's complement I want to perform some interval-operations, and for addition, subtraction, and logic-/shift-operators, that works very well.

The only problem I have is the multiplication.

An interval $[a, b]$ denotes all two's complement numbers $x$ with the property $a \leq x \leq b$.

An interval-operation means that if i have a binary operation $\circ$ and two intervals $[a, b]$ and $[c, d]$, then $[a, b] \circ [c, d] = [e, f]$ means that for for an arbitrary $x \in [a, b]$ and $y \in [c, d]$: $$x \circ y \in [e, f].$$

But additionally, I want to have the most precise or a very precise interval.

"The most precise" means that there are the values $w,x \in [a, b]$ and $y,z \in [c, d]$ for which holds that $w \circ y = e$ and $x \circ z = f$

An example of an interval-operation:

$A = [7,14]$
$B = [-6, 77]$
$A + B = [1, 91]$

It's correct, because there is no value outside of $[1, 91]$ that can be reached, when adding numbers out of $A$ and $B$.

Also it's precise, because $7+(-6) = 1$ and $14+77 = 91$

It seems impossible to find an efficient algorithm that handles all the overflows correctly and finds the precise (or at least a good) interval.

Is there a good algorithm?

If $0 \leq a,b,c,d$ then $[a,b] [c,d] = [ac,bd]$. The trouble begins when numbers can be negative. If $a,b<0$ then $[a,0][b,0]=[0,ab]$. If $a<0<b$ then $[a,0][0,b] = [ab,0]$. And so on. To consider intervals straddling $0$, partition them into their positive and negative parts.

Summarizing, I wouldn't say that it is "impossible" to find an algorithm for multiplying intervals, only that you have to consider numerous cases. Good luck.