texts: Find all routes between two nodes where the nodes are on different graphs, and each graph must be used, and in order

texts:
I want to find all possible train routes from the user's chosen city A to city Z, given that for any combination of cities there is defined one or more combinations of one or more graphs that can be traversed.

The graphs are defined in KML files, and the valid combinations are also pre-defined.

The number of valid combinations varies between one and around seventy. The number of graphs used varies between typically one or two, up to, in complex cases, as many as six.

A typical (albeit more complex than average) combination of graphs for a given pair of inputs looks like this WX+SU+GC+CM. This means you must traverse graph WX, starting at node 'A' (the user's specified origin) to any node that is also found on graph SU, and then traverse graph SU from that node to any node that is also found on graph GC, then traverse node GC from that node to any node found on CM, and finally traverse graph CM from that node to the destination 'B'.

Graphs WX and graphs CS intersect at two points 'C' and 'D' each with one path possible on graph WX.

Graph CS and MA intersect at around fifteen different points

MA and GM intersect at several points.

What is the best way to find all valid routes between the two cities?

Note the rules:

Graphs must be used in order (first WX, then CS, then MA, then GM)
Once you have left a graph you must not use it again (so if you use an edge found on CS, you cannot subsequently use a edge from WX, although if that edge is ALSO found on WX, there is no problem)
At least one edge must be used from each set - you cannot skip any set.

Is it best to just put all of the edges from all the graphs into one graph, find all the routes (depth-first search?), and then after doing this check if the edges can be visited in order?

E.g.,

The route:  A-B-C-D-E-F-G

Where

A-B is found on graphs 1, 2, 3, 4
B-C found in graphs 1, 2, 3, 4
C-D found in graphs 3, 4
D-E found in graphs 2, 4
E-F found in graphs 2, 3
F-G found in graphs 3, 4

is NOT valid, because you cannot traverse it without going back a graph, either at node 4, or node 5.


texts: Determining the DP subproblem given a problem

texts:
I'm reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems.

For example, consider 2 similar problems.

Given a set of 1, 2, and 3 steps you can take, find the total number of ways to reach X steps.

Given a set of 1, 2, 3 coins, find the total number of ways to reach X amount.

After doing both problems, I've found that the main difference in the problems is that for coins, order does not matter. If you have 1 coin and 3 coin, it's the same as if you have a 3 coin and 1 coin. With steps, order matters. Taking 1 step then 3 step is different than taking 3 step then 1 step.

With that, the correct subproblem it seems for the coins is given 1 coin, how many ways can we reach X amount. Thus you build out your solution first with 1 coin, then add a coin, and then add a coin.

With the stairs problem, it seems like the subproblem is given a set of stairs with just 1 step, how many ways can we climb up. Then do it for 2 steps, and so on until you reach X.

I'm wondering if there's some intuition behind how to choose these subproblems. It seems like just as easily, you could say for the stairs problem the subproblem can be given the ability to take 1 step only, how many ways are there to climb up X steps. Now add the ability to take 2 steps, and so on.

Any tips to think through these problems would be greatly appreciated!


texts: Producing a total or partial order from an inconsistent relation

texts:
Imagine I want to construct a total order from a set of elements, $E$, but the comparison function produces results that are non-deterministic. I produce a list of element pairs (e, e) through repeated application of the comparison function, such that each element in the set is represented at least once.
How can I use this input to produce a total order? What is the class of algorithms that can be applied here?

For greater clarity, I'll provide a concrete example.
What are the best pizza toppings?
My set of elements $E$ includes some popular pizza toppings: pepperoni, cheese, mushroom, pineapple, bellpepper, olive.
Then for each of my friends, I pick randomly sized subsets of toppings and ask my friend to put them in order from best to worst. My friends dutifully reply, and create the input for my algorithm:

cheese, pepperoni, olive
cheese, pineapple, mushroom, olive
bellpepper, mushroom, olive
pepperoni, cheese, olive
cheese, bellpepper

There does seem to be a fuzzy order here (everyone agrees olives are the worst) but my friends have not arrived at consensus about which is the better pizza topping: cheese or pepperoni. Considering where items occur in the inputs, and how frequently they occur, I would probably produce an order something like this.

cheese > pepperoni > bellpepper > pineapple > mushroom > olive

I'm just not sure how to go about formalizing this and making it work for much larger inputs.

I think the solution probably involves graphs and weighted edges, but I lack sufficient familiarity with graph algorithms to recognize whether this is a named area of study. I already came across "topological sorting" but that only works for directed acyclic graphs, and I am specifically interested in inputs that cannot produce a DAG.
I also noticed that this problem seems similar to voting for elected representatives. Is it, in fact, the same class of problem?


texts: Decidability of "Is this regular expression prefix-free?"

texts:
Say that string $x$ is a prefix of a string $y$ if there exists a string $z$ such that $xz = y$, and say that $x$ is a
proper prefix of $y$ if in addition $x \not= y$. A language is prefix-free if it doesn’t contain a proper
prefix of any of its members.
$$
\text{Prefix-FreeREX} = \{(R) \mid R \text{ is a regular expression and $L(R)$ is prefix-free}\}
$$
I was wondering about how to prove that Prefix-FreeREX is decidable. Also why does a similar approach fail to show that Prefix-FreeCFG is decidable?


texts: If L is context free and R is regular then R – L must be context free?

texts:
Hi I am wondering if L is a CFL and R is RL then would the difference R - L be a context free language?
The difference might be the CF part of the language left then it would be, but I'm not sure how I could go about proving this without giving an example


texts: I know after some reading Amdahl law is a embarrassingly parallel programming model. Embarrassingly parallel means there is no communication and tasks work independently. Am I to assume a parallel and a non parallel aspect of the program is embarrassingly parallel?  If not, what makes it embarrassingly parallel?


texts: Ways to implement a decision making process involving complex rules

texts:
I'm investigating different solutions for solving what looks like a decision making problem. Although the domain I'm working on is different, for the problem at hand, it's quite easy explaining with an example of online shopping cart.

Suppose you have a shopping cart like you have in every online retailer but this one checks some criteria and allow you to proceed only if the cart conforms to some criteria. Those criteria can depend on:

a property of the item you add to your cart (ex: minimum quantity allowed for the item you add)
combinations of the items you add (ex: if you have in your cart an item from sports category, you need to add an item from nutrition category)
properties of the cart itself (ex: option to give multiple orders from the same cart but only if certain type of items are in the cart)
and many other rules with exceptions...

So at a given time, your cart is in one of two states: valid or invalid. It starts with the state invalid: An empty cart. And at each action you take the state changes.

Some of the actions that change the state of the cart are:

adding an item to cart
changing a property of the item added, like color, size, quantity, etc
changing a property of the cart, like applying a discount code.

What I'm trying to achieve is to find a clean way to decide after every action, whether the cart is in a valid state or not.

The current code base for this is a mess. A method of hundreds lines of code, taking 15 arguments and filled with ifs and fors.

I wonder what are the possible solution patterns I can use to refactor this into a cleaner and maintainable implementation.

I've investigated finite state machines but couldn't figure out how to represent this into states and actions. Decision making trees I've seen are for pretty simple flows when you can answer yes or no easily. And they were implemented with nested ifs and elses which is quite similar to the current (messy) solution. My investigation lead me to AI and expert systems but I stopped there. As you can guess, I have no previous experience dealing with these kind of problems. Maybe what I'm trying to solve is a complex one and it's ok to have complex solutions to complex problems. But maybe this is a generic problem where you can give some direction to focus my research.


texts:
You have two friends, call them A and B. They each are given two wine bottles: one bottle holds k_1 litres and the other k_2 litres. Both A and B can perform these operations:
- completely fill a wine bottle with wine
- completely empty a wine bottle
- pour the wine of one bottle into the other bottle, making sure to stop only when either the bottle being filled is full or if when the bottle being emptied is completely empty. Assume the litres of wine are all positive ints.

Q: Determine if there exist a seq of operations that leaves exactly k_3 litres of wine in the bigger wine bottle. Try representing this as a graph problem.

My idea: define the vertices to be a pair of integers in a graph. I got this as a recent interview question. But couldn't solve the entire problem in time. Then they said you could have apparently applied some algo to this problem too, and that it had a complexity that was fast enough. Any ideas?


texts: Tree traversal with conditional summing values from nodes

texts:
Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can be random number).
What i want to do is traverse tree and for each node i want to sum values from all descendant nodes except descendants with lower rank and all nodes under them (irrespective of rank).

My naive solution is to recursively traverse subtree for each node and stop recursion as soon as i find node with lower rank, summing values on my way back to root of subtree. However this feels to me like suboptimal solution. It is possible to have sums for all nodes settled after one traversal?

Edit: There are no special relationships between nodes and also tree doesnt have any special properties. Tree is not binary tree as each node can have <0,Integer.MAX_VALUE> children.

To more describe my naive solution, in worst case - that is each node has only one descendant (its basically linked list) and ranks are sorted ascending to the root this solution would be O(n^2).


texts:
EDIT: The most general case I need is not a tree but any Directed Acyclic Graph.

I have a directed acyclic graph.

I need to sort it in a list so that in the list every node comes after any node it can walk to in the graph.

So far so good, just use a topological sorting algorithm.

However, I have an additional constraint: Each node in the graph is colored, and I need to find a sorting so that the list is as cohesive as possible. In other words, if you walk the list, you should see a change in colors as few times as possible.

Other thoughts:

I need an efficient algorithm. No iterating through all possible sortings.
The set of colors is typically much smaller than the set of nodes in the graph.
If no efficient exact algorithm is possible, I would be happy with a heuristic one that is likely to produce good results.
There is some information that one could potentially use for the heuristic: The colors are also partially ordered, and this ordering of the colors is correlated to the ordering of the nodes. I.e. a node is likely (but not guaranteed) to have a color that is "smaller than" the color of its parent node.
You can think of the problem this way: I have a set of jobs, and each job can depend on the output of several other jobs (if x depends on y there is an arrow from x to y). There is an overhead associated with setting up the data needed for each job, but this overhead is significantly reduced if the previous job had the same "color". The whole set of jobs is typically executed many thousand times, so if one can find an not too expensive way to improve the order of the jobs, that will pay off.

So far I have come up with this algorithm which works well most times, but not always:

first pass:

Define the order "<=" so that x <= y if y can walk to x in the graph.

find any topological sort of the nodes and put it in the list L
(L is sorted from smallest to largest w.r.t the partial ordering "<=" )

W = []
for x in L:
   find the earliest y in W so that color(x)==color(y) && there is no z in W with z > y and x > z
   if y exists:
       insert x in W after y.
   if y does not exist and there is no z in W with x > z:
       place x at the beginning of W
   else:
       place x at the end of W

second pass:

 for each continuous group G of colors in W:
    for x in G in reverse order:
       find the latest y in W so that color(x)==color(y) && there is no z in W with z > x and z < y
       if y exists:
           move x directly before y in W

The second pass may seem a little puzzling, but it is just my experience that it tends to improve the results. I.e. some times it will be able to move one whole group of colors past another group and join a third group of the same color.

I think the reason that the first pass is not sufficient is that there can be complicated interdependencies between the nodes that are sorted in L after the current x you are looking at, and so you can't know the optimal placement of x in the first pass, you just have to go with something.

Any help would be great!


texts: Unknown length of chromosone in genetic algorithm

texts: I've read some about genetic algorithms and the general approach, but I haven't found anything about using it when the length of the solution is unknown. How would the generation of the initial population look like? Would mutation then include adding/removing alleless? Are there any general methods for this?


texts: Splay tree amortized analysis cost using Access Lemma

texts:
Currently studying for an algorithms exam and I came across this question and solution, but I can't understand the solution where it references nodes of depth less than $4\log n$ and not restructuring. I understand everything else except for the $4\log n$ part - thanks in advance.
The question:
Suppose that when we perform search on a splay tree containing $n$ items we splay the
deepest accessed node only when its depth is at least $4\log n$. Show that the total amortised cost of $m$ searches, where $m \ge n$, is $O(m \log n)$.
The solution:
Here we apply the Access Lemma, assigning weight 1 to all items. Then the size $s(x)$
of a node $x$ satisfies $1 \le s(x) \le n$ and the rank $r(x)$ satisfies $0 \le r(x) \le \log n$. By the Access Lemma the amortised cost of splay is bounded by $1 + 3 \log n = O(\log n)$. Moreover the amortised cost of searching for a node of depth less than $4\log n$ equals the actual cost, which is $O(\log n)$, since the tree is not restructured. Thus the total amortised cost of $m$ searches is $O(m \log n)$.


texts: How to represent circles in x-y coordinates

texts:
I would like to be able to represent circles in x-y coordinates.

Each circle contains an x and y coordinates and radius in double data type.

My goal is to compare circles with each other whether they are partially or completely overlapping.

I am looking for efficient ideas. Honestly the only idea that comes to my mind is draw a line(let's say l1) from x1,y1 to x2,y2 and the length of this line is larger than addition of r1 and r2 then it does not overlap, if r1+r2 =< l1 then it overlaps, but I don't know how to find whether it is completely overlapping or partially. Also this wouldn't work for cases where I am combining more than one circle.


texts: Average case algorithm analysis using Kolmogorov Incompressibility Method

texts:
The Incompressibility Method is said to simplify the analysis of algorithms for the average case. From what I understand, this is because there is no need to compute all of the possible combinations of input for that algorithm and then derive an average complexity. Instead, a single incompressible string is taken as the input. As an incompressible string is typical, we can assume that this input can act as an accurate approximation of the average case.

I am lost in regard to actually applying the Incompressibility Method to an algorithm. As an aside, I am not a mathematician, but think that this theory has practical applications in everyday programming.

Ultimately, I would like to learn how I can deduce the average case of any given algorithm, be it trivial or complex. Could somebody please demonstrate to me how the method can be applied to a simple algorithm? For instance, given an input string S, store all of the unique characters in S, then print each one individually:

void uniqueChars(String s) {
    char[] chars = chars[ s.length() ]
    int free_idx = 0;

    for (int i = 0; i < s.length(); i++) {
       if (! s[i] in chars) {
          chars[free_idx] = s[i]
          free_idx++;
       }
    }

    for (int i = 0; i < chars.length(); i++) {
        print (chars[i])
    }
}

Assume a linear search for checking whether the array contains an element.

The above code snippet is only for the sake of argument.
Better algorithms by which the theory can be demonstrated are acceptable, of course.

I asked this question on StackOverflow (https://stackoverflow.com/q/24619383/3813812) back in July, 2014, and have received a few helpful comments but not a definite answer. As one of the commenters pointed out, this question is better suited for Computer Science StackExchange, so I ask here today.

Some literature that I have reviewed includes:

An Introduction to Kolmogorov Complexity and Its Applications, by Ming Li and Paul M.B. Vitányi
https://www.cs.duke.edu/~reif/courses/complectures/Li/KC-Lecture1.pdf
http://www.detectingdesign.com/PDF%20Files/Kolmogorov%20Complexity%202.pdf

Among a few other resources that I do not have links to on hand.

If my understanding of the applicability of Kolmogorov complexity is inaccurate or what I ask is impractical, I would appreciate a statement with regard to the fact.


texts: I am trying to design an LL(1) Parser that accepts T = {a, b *, +, ?, E, U, (, ) }

texts:
I am trying to design an LL(1) Parser that accepts regular notation where 'E' represents epsilon, and 'U' represents "or" like ' | '.
So far I made one that accepts T = { a, b, *, +, (, ), E}
S -> T S'
S' -> + S | ε

T -> F T'
T' -> T | ε

F -> P F'
F' -> * F' | ε

P -> ( S ) | c | E

c -> D M
M -> C | ε
D -> a | b

I am having trouble on what production I should add so that it will accept 'U' and ?. so it will allow something like these:
(a* U b+)* U a U E

E

but hopefully won't allow these:
(a*)*

(a*)+

(a*)? - doesn't need optional because a* is already Zero or More

(a+)? - since this is basically a*

abE

I'll be really grateful for any kind of help I can get :D


texts: Multi Arm Bandit (MAB) -- Increasing reward function

texts:
In the general stochastic MAB model, the reward obtained at each trial is generally assumed to be independent of previous trials and obtained from some fixed (but unknown) distribution.

However, if the reward function is a monotonically increasing function of time, what would be the corresponding MAB model? Should it be adversarial? It would be really helpful if you can point me to some resources (papers, books, articles) regarding this.


texts: Is my interpretation of the SSL process correct?

texts:
Firstly, which of the two diagrams below is the more accurate or more well-explained (if both are accurate) representation of the SSL process (at a beginner's level)?

Diagram 1

Diagram 2

Also where does the "pre-master secret" in diagram 1, step 5 come from? I presume it comes from diagram 1, step 2? How is it created (is it part of the client hello)?

Additionally, why is there a need for both parties to exchange cipherSpec exchange? Wouldn't it just require the client to send the cipher specs, have the server evaluate it against is own and return a confirmation message?


texts: Is scalar variable multiplication of $0/1$ variable array possible in $MILP$?

texts:
I remember somewhere seeing the following. If $x$ and $y$ are integer variables then we cannot multiply them easily unless we know a bound $B$ on them.

  Suppose I have an array $\overline x=[x_1\dots x_n]\in\{0,1\}^n$ and $0\leq y\leq B_y$ holds and entries of $x$ and variable $y$ are integers then is it possible to multiply $y\cdot \overline x$ with no extra integer variables and only $O(n\log B_y)$ real variables in $MILP$? I want real variables $z_1,\dots,z_n$ that the $MILP$ should have with the result $z_1=y\cdot x_1,\dots,z_n=y\cdot x_n$.


texts:
I know a regular language is the one which can be expressed as a regular expression or we can create a DFA corresponding to it. Unless a language has a pattern in which one part has to match with other like in $$a^nb^n|n\geq 0 (CFG)$$ It'll be regular. Like AP Series of symbols can be easily expressed as Regular expression but GP Series can not.

But I failed to understand why the following languages are regular

  $L_1=\{wxw^R \mid w,x \in (a,b)^+\}$

  $L_2=\{wxwy \mid w,x,y \in (a,b)^+\}$

  $L_3=\{xwyw \mid w,x,y \in (a,b)^+\}$


texts: Genetic Algorithms: Converge to best solution for one, few or many environments?

texts:
Let's say we take someone's garden (A) as the environment. We want a robot to pick up a series of eggs that chickens have laid in the garden, while covering as little ground as possible (those heavy rover tracks damage the turf, you know). So we evolve a solution whereby the genes representing the robot's behaviour (i.e. we are not just evolving some chain of path states/positions) work great in that garden.

All freshly laid eggs in (A) are collected in record time.
Our algorithm has learned some tricks about navigating gardens; like driving a car for the first time. But there is more.

If I now put the same robot in a different garden (B), it may or may not do OK. It depends, I suppose, on how similar (B) is to (A) in certain key factors, i.e., will any of the tricks learned in (A) apply here? The likelihood is it will need new tricks, so I'm going to have evolve it further in (B) if I want anything like an optimal solution. Yet if I don't, at every iteration, continue to test it in (A) too, then I may be losing fitness for (A) in every new generation, yes?

So if I want a algorithm that performs well under a wide variety of circumstances, I am going to have to test it in all of those N circumstances, for all of the M candidates; will I thus need to run MxN tests on each generation? What about circumstances I didn't cover?


texts: n-queen puzzle with no 3 queens on same line

texts:
I am trying to solve n-queen puzzle with an additional stronger condition that no 3 queens can be on the same line.

Right now my algorithm is,

Generate a random permutation of [1..n].
Store "swaps" as "moves" such that it reduces number of conflicts.
Pick a "move" with non-uniform distribution on number of reduced conflicts and swap.
go back to 2 unless number of conflicts is zero.

Right now, I store number of conflicts for each queen in current board. Then I compute number of conflicts for each move. For that I just have to compute the conflicts of only swapped rows. Then I pick moves with a probability biased to highest reduce in conflicts. Then again I compute number of conflicts for each queen in next board.

Now computing conflicts for each position takes $O({n\choose2})$ time. So to compute for all of them takes $O(n^3)$.

Also there are $O({n\choose2})$ moves. So to compute conflicts for all moves needs $O({n\choose2} * 2 * {n\choose2})$ = $O(n^4)$.

So my each iteration takes $O(n^4)$ time. Is there any clever way to store the configuration in data structure such that I don't have to brute force over all queens?

no 3 queens on same line means if $3$ queens are at $(q^0_r, q^0_c), (q^1_r, q^1_c), (q^2_r, q^2_c)$ then $$\frac{q^0_r-q^1_r}{q^0_c-q^1_c} \neq \frac{q^0_r-q^2_r}{q^0_c-q^2_c}$$

Of course diagonal, horizontal and vertical constraints are same as before.  See also the pictures at this Stack Overflow question for additional explanation.

I found this problem at Hackerrank.


texts: What does a non-deterministic guess "look like"?

texts:
I have been trying to understand the solution to the following problem:
"Show that if $L_2$ and $L_3$ are Turing recognisable, then so is $L_2L_3 = \{w_1w_2 : w_1 \in L_2,w_2\in L_3\}$:
which essentially says to use non-determinism to guess a partition $w$ (say $w=xy$) and run the Turing machines $L_1$ and $L_2$ on $x$ and $y$ respectively.
I'm trying to get my head around what this non-deterministic guess "looks like", i.e. what we would say if we were to describe this implementation in more detail.
My thought is if the input string is of length $n$, then the second string $y$ could start at any of the $n$ positions, or be empty, so there are $n+1$ possible partitions. Does this mean we ultimately need to split into $2(n + 1)$ parallel/non-deterministic clones? And how do we manage this splitting in terms of transitions? We obviously don't know the length of the input ahead of time, so we can't immediately have $2(n+1)$ transitions from the start state? Would we scan the input string left to right, spawning two additional parallel threads for each character encountered, or something?
I see this "non-deterministically guess" phrase a lot in example solutions, but I feel like I'm missing a bit of intuition as to why this actually works. Any thoughts would be much appreciated.


texts: Can we find a computable function which cannot be calculated faster for any given time?

texts:
Define $T\colon \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ by:

$T(k,n) = 2^{T(k-1,n)}$

$T(0,n) = 1$

$T(1,n) = 2^n$

$T(2,n) = 2^{2^n}$

And denote the W.C. (worst case) time of computing $f(n)$ as $WC(f(n))$

Can we find computable functions $f_i\colon \mathbb{N} \rightarrow \mathbb{N}$ such that computing $f_i(n)$ takes $\Omega(T(i,n))$ W.C. and such that for every other computable function $f \equiv f_i$ (I mean $f(n) = f_i(n) \forall n \in \mathbb{N}$), we have $\lim_{n \rightarrow \infty} \frac{WC(f_i(n))}{WC(f(n))} \neq 0$?

I am in a sense trying to find a concrete example of functions that takes at least X time to compute, where X can be as large (asymptotically) as we want.

I was thinking maybe $f_i(n) =$ the $T(i,n)$'th digit of $\pi$,
but not quite sure this fulfills the second condition.


texts: How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

texts:
Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2).

G1 and G2 are two LL(1) grammars with identical alphabets:

{a, b, c, d, f}

Production rules are look like:

A -> αB

or

A -> α

and α is a non-epsilon string (of terminal symbols).

Context-free grammar G1:

S1 -> aK
K -> bC|cE
C -> cB|d
E -> bA|f
A -> abC
B -> acE

Context free grammar G2 :

S2 -> aX
X -> bZ|cY
Z -> cV|d
Y -> bU|f
V -> aQ
U -> aP
Q -> cY
P -> bZ

Automatic way is preferred.

  In additional, how can I check that the languages of two arbitrary
  context-free grammars are equal.


texts: Infeasible linear programming reduce errors to find solution

texts:
Most normal linear programming problems look like this:

We choose some point in the double shaded area that solves our optimizer and we're good to go.
However, I've come across a problem where it's fairly common to get a lp problem like this (infeasible):

I'd like to employ some metric such that the solution given reduces the errors between the closest possible solutions in any equation it does not fulfill such that it would be on the line right between the 2 solutions (something like reduce OLS or LAD).
Is there any formal algorithm for this or common way this is done?


texts: How to represent the interests of a Facebook user

texts:
I'm trying to figure out a way I could represent a Facebook user as a vector. I decided to go with stacking the different attributes/parameters of the user into one big vector (i.e. age is a vector of size 100, where 100 is the maximum age you can have, if you are lets say 50, the first 50 values of the vector would be 1 just like a thermometer).

Now I want to represent the Facebook interests as a vector too, and I just can't figure out a way. They are a collection of words and the space that represents all the words is huge, I can't go for a model like a bag of words or something similar. How should I proceed? I'm still new to this, any reference would be highly appreciated.


texts: Is there a defined set of steps or principles on how to reduce time complexity of algorithms?

texts:
I have been watching some big (Google, Facebook,..) company interview examples and usually when pair programming, they develop the most straightforward algorithm and then the interviewer asks 'could you make it faster (reduce time complexity)'.

I have worked on optimizations of algorithms too and things that immediately spring to head when I optimize is to take out as many nested loops as possible, look for sorted data, change data structures, etc.

Since algorithm optimization is a common thing I was wondering is there a defined set of steps or principles on how to approach the reduction of time complexity of algorithms? something akin to SOLID for Object-oriented programming, but for reducing time complexity.


texts:
I am given a graph $G = (V, E)$ with $N$ connected components and $G^\prime = (V^\prime, E^\prime)$, where for each $v \in V$ there is $v_1, v_2 \in V^\prime$ and for each $(u, v) \in E$ there is $(u_1, v_2), (u_2, v_1) \in E^\prime$.
I need to prove:
$$G^\prime \textrm{ has 2N connected components} \Leftrightarrow G \textrm{ is bipartite}$$
I don't know what technique or approach I need to use to prove this in either direction. I have a feeling I can use a direct proof for both directions. I have tried to come up with something but after an hour nothing has come up.


texts:
Fix a universal Turing machine $M$.

Let $A^*=\{0,1\}^n$ be the set of all binary string of length $n$.

Determine the Kolmorogov complexity $K(x)$ of each $x\in A$, w.r.t. $M$.

Just for a matter of simplicity assume that $K(x)'=\min(|x|,K(x))$.

Let $B^*=\{0,1\}^n$ be the set of all programs $y\in B$ of $T$: $x= M(y)$.

Now, suppose a parallel machine $M_p$ that can run each program $y\in B$ for each element in $A$, in parallel. So we can get the length of all the programs $y$ whose machine ended with the right string $x$, and take the minimum as $K(x)'$.

So, should I assume that the non-computability is due to the fact that some machines that has not ended jet whose inputs $y$ are less than the current minimal program  will eventually halt? What's the probability of this?

Also, maybe a measure of complexity should include a minimal length with a probabilistic confidence? Say $P(K(x)\geq l)\geq p$?


texts: Why has research on genetic algorithms slowed?

texts:
While discussing some intro level topics today, including the use of genetic algorithms; I was told that research has really slowed in this field. The reason given was that most people are focusing on machine learning and data mining.
Update: Is this accurate? And if so, what advantages does ML/DM have when compared with GA?


texts: Complexity of determining spanning bipartite graph

texts:
A procedure by induction to get maximum spanning bipartite graph (same vertex set as $G$ and the maximum possible number of edges) from given graph $G$:

Given a planar graph $G$, we need two disjoint sets $V_1$ and $V_2$. We define $V_2=V \setminus V_1$ where $V = V(G)$. In the following, $H$ is the bipartite subgraph with  $V(H)=V_1 \sqcup V_2$ and $E(H) = K_{V_1,V_2} \cap E(G)$ where $K_{V_1,V_2}$ is the complete bipartite graph on $V_1$, $V_2$.

Start with first $i$ vertices of $V$ in vertex set $V_{01} \subseteq V$ and then $V_{02} = V \setminus V_{01}$
In iteration $i$, let our current chosen vertex set be $V_{i1}$
If $\exists x \in V_{i1}$ such that $d_{H}(x) \lt \frac12 d_{G}(x)$, then consider the bipartite spanning graph $H'$ with $V(H') = V_{i1}' \sqcup V_{i2}'$ where $V_{i1}' = V_{i1} \setminus x$, $V_{i2}'= V_{i2} \sqcup x$, $E(H') = K_{V_{i1}',V_{i2}'} \cap E(G) $ This makes $\vert E(H') \geq E(H) \vert$. We are basically moving vertex $x$ which satisfies above property from $V_{i1}$ to $V_{i2}$.
Similarly do for $ V_{i2}$. If $\exists x \in V_{i2}$ such that  $d_{H}(x) < \frac{1}{2} d_{G}(x) $, move vertex $x$ to $V_{i1}$. Go to step 2.
Repeat until $(\forall x \in V(H))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$
After this $V_1 = V_{i1}$ and $V_2 = V_{i2}$. We are using the property that a spanning bipartite subgraph $H$ from $G$ is maximal in terms of the total number of edges only when $H$ with $V(H) = V_{1} \sqcup V_{2}$ satisfies the property that $$(\forall x \in V(G))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$$

Analysis of this procedure:

Could somebody help me analyze this algorithm?
Can I assume I know the degrees of the vertices in the bipartite graph $H$, in the intermediate steps?

2.1. If I can assume so, then each induction iteration has $2n$ steps. And, in the worst case, could there be $n!$ permutations of induction iteration (Any permutation of $i$ vertices is possible for the first vertex set). Is the worst-case upperbound $O(n!\times n)$?


texts: SLR(1) Table construction, FIRST and FOLLOWS

texts:
when constructing the SLR(1) table for some grammar I need to compute the FOLLOW set for all terminals in order to decide where and when to reduce.

Do I compute theme for the augmented grammar or the original one?
Is there even a difference?


texts: Is object oriented programming fundamentally different than imperative programming?

texts:
I have been using C for a while, for some reasons I learnt C++.

I can't see why object oriented is a "new" feature. For me an object is just a structure, and a set of functions which have a pointer to this structure as a parameter(the this parameter). So instead of creating structures then functions that modify them, the compiler gives you a direct way to do it.
Also for Late Binding, I see it as the same as if you had a hidden member in the structure to a function pointer. So again, nothing new in itself.

So is OO just a compiler feature to make imperative easier by automating some things ?


texts: Is there a PDA for every Type 3 Grammar?

texts: we learned that for every type 2 grammar G exists a PDA A with L(A) = L(G). But does for every type 3 grammar G exist a PDA A_G with L(A_G) = L(G)? I think it does, because type 2 grammar is a subset of type 3 grammar. Am I wrong?


texts: Understanding On-policy First Visit Monte Carlo Control algorithm

texts:
I am going through the Monte Carlo methods, and it's going fine until now. However, I am actually studying the On-Policy First Visit Monte Carlo control for epsilon soft policies, which allows us to estimate the optimal policy in Reinforcement Learning.

I am having troubles understanding the step in blue of the algorithm. Is the pair St, At NEVER supposed to appears in the given set of states ? In this case, the following pseudo-code will never get realized ? What is the specific case where St, At appears in the set of Action-States ?

Please feel free to ask more details if my question isn't clear enough.

The algorithm is taken from the reinforcement learning book written by R.Sutton and A. Barto.


texts: Finding "good" order of elements for the purpose of material minimization

texts:
I am working with metallic shapes which are curved and highly irregular. The initial order of them is random and by default they are merely sorted by size, which is simple. However the resulting order is neither optimal, nor "good".

A smaller frame means less material used, so an optimization is desired. The shapes themselves are planar, so the ordering happens in a 2D space. Ordering is also only relevant with respect to x-axis, meaning that elements are not placed above/below/diagonal to each other, but always one after the other.

Bruteforcing this is non-viable, because I am aware that this problem is NP-hard, since in order to find all possible frame-lengths I'd first need all permutations of which there are n!. In addition to this the calculation of the frame length is rather costly.

A frame with metallic shapes can be envisioned like this:

[ (((c((cCCc( ]

Where the curved symbols represent the metallic shapes and the outer brackets are the frame borders.

So far I am left thinking that finding the optimal solution is not feasible, but finding a good solution might be. There is a lot on material available on optimization and on cutting the cost of material use, mainly I am looking for advice on literature that comes as close to my challenge as possible. What should I look into?


texts: General number field sieve is slower then exhaustive search for 'small' numbers?

texts:
In an attempt to understand the efficiency of the GNFS, I've been looking at runtimes.  The calculations seem to indicate the GNFS runs slower than exhaustive search for smallish n.  For example: suppose I want to factor the number 247 (ie 13 * 19).

To do this I can just check all the numbers (exhaustive search) below
$$ \sqrt{247} \approx 16$$ to see if they divide 247.

The General number field sieve has a runtime of
$$
\approx \exp \sqrt[3]{\frac{64}{9}} (\ln n)^{1/3} (\ln \ln n)^{2/3},
$$

So calculating the GNFS runtime...
$$
\approx \exp \sqrt[3]{\frac{64}{9}} (\ln 247)^{1/3} (\ln \ln 247)^{2/3},
$$
$$
\approx \exp \sqrt[3]{\frac{64}{9}} (5.5)^{1/3} (\ln 5.5)^{2/3},
$$
$$
\approx \exp \sqrt[3]{\frac{64}{9}} (5.5)^{1/3} (1.7)^{2/3},
$$
$$
\approx \exp (1.9 * 1.8 * 1.4),
$$
$$
\approx \exp (4.87) \approx 120
$$

This is obviously bigger than 16.  What am I missing here?


texts:
It consists of one read only input memory and write only output medium. The computation proper takes place in a working memory of limited size. When stating that a problem can be solved with a certain number of bits, what we mean is that the working memory consists of that many bits. The input and working memories are divided into words of $w$ bits for a fixed parameter $w$. Random access to to input and working memory is provided. In the context of $n$ words, assume as is common , that $w = \theta(\log{n})$.

Question : What it means "In the context of $n$ words, assume as is common , that $w = \theta(\log{n})$.
"

Link : " Space-efficient Basic Graph Algorithms Link"


texts: Calculating Frequency of Terms with Zipf's Law

texts:
I'm studying for an exam and came across this question. I feel like it's much simpler than I am making it out to be, but I'm not sure.

Suppose we have a corpus in which Zipf’s Law holds. If the most frequent term occurs one million times, and the next most frequent term occurs 250,000 times, how often should we expect to see the third most frequent term? And the fourth most frequent term?

Wikipedia has the formula $$f\left(k,s,N\right)=\frac{\frac{1}{k^{s}}}{\sum\limits_{n=1}^{N}\frac{1}{n^{s}}},$$ We
but in this problem, $N$ (the number of terms) and $s$ (the value of the exponent characterizing the distribution) aren't given. Only $k$ (the rank) is given and the frequencies of each rank. I know that Zipf's Law says that the frequency of a term is inversely proportional to the term's rank, but I don't know what that constant factor would be in $f_{t}=c\cdot\frac{1}{k}$.


texts: Turing machines and their computational power

texts: Is Turing machine most powerful model of computation? Is it possible theoretically to build the model of computation which is more powerful than TM i.e is it theoretically possible to build the machine which could solve the problems that T.M cannot?Are quantum computers also the T.M or are they more powerful than T.M?


texts: Directed weighted multigraph isomorphism algorithms

texts: Are there known algorithms for the isomorphism problem for directed weighted multigraphs? If not, could one be created simply by adapting existing algorithms for graphs or digraphs, or is it entirely non-obvious?


texts:
How to find a recurrence relation for $F(n)$ the number of ways to make n cents change using only pennies (4 cents), nickels(5cents), and dimes(10cents) and ordering matters.

There are three exclusive case here

Start with pennies then new subproblem is $F(n-4)$
Start with nickels then new subproblem is $F(n-5)$
Start with dimes then new subproblem is $F(n-10)$

$$F(n) = F(n-4)+ F(n-5) + F(n-10) $$

Is there any other way to solve this problem. The above method is ok but seems like magic to beginner. Is there any systematic approach to solve this problem?

Problem is also available on https://math.stackexchange.com/questions/248853/how-to-find-recurrence-relation-for-this-problem


texts:
I was reading this and I was trying to understand the definition of $(S,\Sigma)$-CCC. The first requirement says:

  a mapping [[_]] : S → |C|, associating some object [[s]] ∈ |C| to
  any s ∈ S;

which I find very confusing and having a hard time understanding what it means. What is $S$ and what is $\Sigma$?

why do all the other requirements mean intuitively?


texts: If $f(n) = \Theta(g(n))$, do both functions bound each other for all $n$ or only sufficiently large $n$?

texts:
The following is an excerpt from CLRS:

  $\Theta(g(n))= \{ f(n) \mid  \text{ $\exists c_1,c_2,n_0>0$ such that $0 \le c_1 g(n) \le f(n) \le c_2g(n)$ for all $n \ge n_0$}\}$.

Assuming $n \in \mathbb{N}$, I was unable to find $f(n)$ and $g(n)$ such that the bound does not apply for all $n$.

Note: This question was asked with the flawed assumption that $f(n)$ and $g(n)$ necessarily have natural domains.


texts: Difference between CNOT and 2nd bit bitflip

texts: I understand how the outcome of each is supposed to be different, but in matrix form are these gates not the same? The CNOT matrix negates the second bit regardless of the input of the first.


texts: If $j − 1 < \log k < j$. Why is $j = O(\log k)$?

texts:
If $j \in Z^+$ and $k \in R^+$ and $j − 1 < \log k < j$. Why is $j = O(\log k)$? (All log's are in base 2)
I know I have to find constants where $j <= c \cdot \log k$ but I need some help with it.


texts:
Given a graph $G = (V,E)$ and a probability $p \in [0,1]$ with which each edge is sampled from the graph $G$. The goal of the stochastic matching problem with fewer queries is to find a subgraph $H \subseteq G$ of fewer* edges such that we maximize the following ratio
A realization of a graph $G = (V,E)$ with a parameter $p \in [0,1]$ is a $G' = (V',E')$ where $V' =V$ and $E'$ is formed by sampling each edge of $E$ independently with probability $p$ i.e, $E' \subseteq E$.
$\max{ \frac{\mathbb{E}[\text{Maximum matching in the realized matching of } H]}{\mathbb{E}
[\text{Maximum matching in the realized matching of } G]} }$
A naive algorithm is to query for all the edges i.e, $H=G$. The ratio would then be $1$, however when the graph is dense the number of edges queried would be $\mathcal{O}({n^2})$.
An another naive algorithm is to query a sparse graph $H= M(G)$ where $M(G)$ is the maximum matching of $G$, I would like to understand the approximation factor for this case.
Clearly the numerator is $kp $ where $k$ is the size of maximum matching. I am unsure how to compute the denominator.
Any help is appreciated. Thank you!


texts: what is the best book to gain an introductory understanding of approximation algorithms? I'm looking for something along the lines of the Sedgewick, that has examples written in a well known language and not psuedocode.


texts: Better Alternatives for Canny algorithm in Edge Detection?

texts:
Canny edge algorithm has 5 stages, from here

1. Apply Gaussian filter to smooth the image in order to remove the noise
2. Find the intensity gradients of the image
3. Apply non-maximum suppression to get rid of spurious response to edge detection
4. Apply double threshold to determine potential edges
5. Track edge by hysteresis: Finalize the detection of edges by suppressing all the other edges that are weak and not connected to strong edges.

This algorithm was originally developed for antiasymmetric edges $(f(x) = - f(-x)$, where the true edge point is at $x = 0$) such as ridge, roof and step edges, discussing here about visualization of these edegs.
(Source Academic Press, Handbook Imaging Processing Analysis)
They say only that requirements for reliable performance are good detection and good localization.

Good detection means that a true edge is highly likely to be a detected and that the likelihood of detecting an edge where there is none is low.
Good localization means that the error in the location of a detected edge relative to that of the true edge should be small.

In summary

  Canny developed mathematical forms for the criteria for low error rate and
  good localization and showed that there is a trade-off between the two
  that dictates a unique shape for the impulse response of the optimal
  detector.

Canny algorithm and Central Limit Theorem

It assumes the same assumptions to all data sets.
If Central Limit Theorem holds for the data sample, you include two such samples in one measurement.
The average of the result will be normally distributed because Canny algorithm cannot affect it, since it applies to all data sets.

Canny algorithm follows the maximum value.
This may cause it go side tract, for instance here of the paper Optical quality assurance of GEM foils by T. Hilden et al:

Possible defects in Canny algorithm

There are some situations which cause me systematic error.
I think some disturbances/defects in the corners of images may cause some systematic deviation in Canny algorithm.
This is what I do not understand and cannot specify better.

How can use estimate the situations when Canny algorithm fails?


texts: Doubt on Karger's Algorithm for Min-Cuts

texts:
I am learning Karger's algorithm for Min-Cuts.I have been solving 1 problem on it. The first part of the problem asks us to run Karger's Algorithm on a given graph. I have no problem doing that. My doubt is in the 2nd part of the question.

2nd part of the question asks to find the probability of contracting 2 vertices in each step of the algorithm.

My approach is that - Since contracting 2 vertices is equivalent to contracting an edge, because every time we contract an edge, we are contracting 2 vertices into 1, so to answer the question, I can just find the number of edges at each step 'i' in my algorithm and and find the probability.

For example, if the number of edges in step 'i' of my algorithm run is 5, I can say that Probability(Contracting 2 vertices) = 1/5. since we can pick anyone of the 5 edges.

Please help me out in finding if my approach is right or wrong.


texts:
I recently asked this very similar question on how Grovers algorithm must be modified in order to solve 3-SAT and learned that it actually needs no modification at all.

However, what I still don't get is how to determine whether a satisfying variable assignment was found after having applied Grover's algorithm. The final step (as described in wikipedia) is to measure $λ_ω$ which in the case of solving 3-SAT would give me an assignment for the variables of my formula. Do I need to check manually whether this assignment is indeed a satisfying assignment? Or is there any better way to find out whether there exists at least one match?


texts: Smallest possible sorting network for given permutation

texts:
I need to build a sorting (comparator) network using comparators for a specific permutation on a set $x_1, \dots, x_n$. The solution should not be a general sorting network that sorts every permutation. I should build the smallest possible sorting network for the given permutation (the depth of the network should be $O(\log n)$).

I am really unsure about how to approach this problem. I thought I might go through the permutation and if the number is in the correct spot then leave it, if not then place a comparator with this number as input and the number that should be here as the second input. But I don't think that the depth of such network would be $O(\log n)$. So how would I go about building the needed network?


texts: How do we know that this Karp-Lipton theorem is derived from relativizing arguments?

texts:
Luca Trevisan wrote, " The oracle $C$ tells us that we cannot have a relativizing proof that derives the $ ⊈ /$ conclusion from the $ ≠$ assumption, so a theorem such as Karp-Lipton, which derives (via relativizing arguments) the $ ⊈ /$ conclusion from a stronger assumption, is about as much as we can hope to prove using relativizing arguments. – " This is replied to the question that "The fact there exists $C$ s.t. $P^C ≠ NP^C$, but $NP^C \subset P/poly^C$ ... what does this give us?".
He wrote that Karp-Lipton theorem is proved by relativizing arguments. How do we know that this theorem is derived from relativizing arguments? I remember the proof and it has nothing about relativizing (I don't want to sketch the proof here since it takes some time and you can find it in Arora and Barak's textbook).


texts:
I am struggling with the following problem:

Given a set of finite binary strings $S=\{s_1,\ldots,s_k\}$, we say that a string $u$ is a concatenation over $S$ if it is equal to $s_{i_{1}} s_{i_{2}} \cdots s_{i_{t}}$ for some indices $i_1,\ldots, i_t \in \{1,\ldots, k\}.$

Your friend is considering the following problem: given two sets of finite binary strings $A=\{a_1,\ldots,a_m\}$ and $B=\{b_1,\ldots , b_n \}$, does there exist any string $u$ so that $u$ is both a concatenation over $A$ and a concatenation over $B$?

Your friend announces "at least the problem is in $\mathcal{NP}$, since I would just have to exhibit such a string $u$ in order to prove the answer is yes." You point out that this an inadequate explanation. How do we know the shortest string $u$ doesn't have length exponential in the size of the input?

Prove the following:
If there is a string $u$ that is a concatenation over both $A$ and $B$, then there is such a string whose length is bounded by a polynomial in the sum of the lengths of the strings in $A\cup B$.

Now, I have actually found a solution and the solution claims that the maximum length of $u$ is at most $n^2L^2$ where we assume $m \leq n$ and $L$ denotes the maximum length of any string in $A \cup B$. The solution then goes on to exhibit a proof by contradiction using the pigeonhole principle to show that if we assume $u$ has length greater than $n^2L^2$ we arrive at a contradiction.

My question is where does the bound $n^2L^2$ come from? I know that $n$ is the number of strings in set $B$ and $L$ is the max length string in $A \cup B$. But I feel as if the largest possible concatenation over both would be more like $2nL$ since we would need to include every string in both $A$ and $B$ and the longest string in either is $L$ and there are at most $n$ strings in each. What am I missing? I think I can handle the remainder of the proof once I understand where the $n^2L^2$ bound is coming from.


texts: What is the name of the domain or theoretical problem of transmitting game states in an online game

texts:
For example, in chess (or any online game), you broadcast the game state to other players at certain times (every n-milliseconds or after a move is made). Thereupon, a player's game client renders the game state in a format suitable for human interaction.

I want to do additional research on the design/transmission of multiplayer video game states, but my ignorance of the terminology is frustrating my research efforts.

What role or documented theoretical problem describes this specific piece of game system architecture?


texts: Is there a human-friendly version of the Pumping-Lemma?

texts:
I found this on Wikipedia and I'm confused by the parenthesis in the notation not that it doesn't make sense to me but is there a more natural human version? And im generally confused about all the different notations surrounding logic and quantifier.
$(\forall L \subseteq \Sigma^*)(regular(l)\Rightarrow((\exists p\geq1)((\forall w\in L)$
$((|w|\geq p)\Rightarrow((\exists x,y,z\in \Sigma^\ast )(w = xyz \land(|y|\geq 1\land|xy|\leq p \land(\forall n\geq 0)(xy^nz\in L))))))))$


texts: What's the difference between "polynomial time Turing-reducible" and "polynomial time many-to-one reducible"?

texts:
The following definitions are from Li, M., & Vitányi, P. (1997). An introduction to Kolmogorov complexity and its applications (2nd ed.), pg. 38.

A language $A$ is called polynomial time Turing-reducible to a language $B$, denoted as $A\leq_T^P B$, if given $B$ as an oracle, there is a deterministic Turing machine that accepts $A$ in polynomial time. That is, we can accept $A$ in polynomial time given answers to membership of $B$ for free.
A language $A$ is called polynomial time many-to-one reducible to a language $B$, denoted as $A\leq_m^P B$, if there is a function $r$ that is a polynomial time computable, and for every $a$, $a\in A$ iff $r(a)\in B$. In both cases, if $B\in P$, then so is $A$.

Aren't the two definitions equivalent? What's the difference?


texts: How to use frame based speech features for learning using a neural network classifier?

texts: I am doing supervised learning on speech audio files using neural networks. For this purpose, I'll have to extract features from the audio file. But since an audio file is a time varying signal, it is generally divided into multiple frames and then features like MFCC etc are extracted from each frame. So how should I encode my feature vector for each training example(audio file) considering that it will be divided into different no of frames(depending on duration of file)?


texts: Are there unary languages that are in RE but not R?

texts:
Suppose that we have an alphabet Σ = {a}. My question is, is it possible to create a language with this alphabet, which is recursively enumerable, but not recursive?

My assumption is a no, i think we can construct a deterministic finite machine, which accepts every language, constructed with a single element in its alphabet.


texts: Number of paths between two nodes in mesh topology

texts: Is there any way to find generalized formula to calculate the number of paths of different length between two nodes of the network connected in mesh topology, given that the network contains n nodes?


texts: Solve Recurrence for $T(n) = 7T(n/7) + n$

texts:
I'm trying to solve the recurrence for $T(n) = 7T(n/7) + n$.
I know using Master Theorem it's $O(n\log_7n)$, but I want to solve it by substitution method.
At level $i$, I get: $7^i T(n/7^i) + (n+7n+7^2n+ \cdots + 7^i n)$
By setting $i = \log_7n$, the above becomes:
$$7^{\log_7n}\cdot T(1) + (n + 7n + 7^2n + \cdots + 7^{\log_7n}n$$
Since $7^{\log_7n} = n$, the above finally becomes
$$n+ (n+7n+(7^2)n+ \cdots + n\cdot n)$$
This solves to $O(n^2)$ to me since $n\cdot n$ dominates, not $O(n\log_7n)$, any idea what's wrong?


texts: How are lookup tables described from the perspective of complexity theory?

texts:
Lookup tables can convert a piece of computational time into space. I remember that it was a part of a complexity theory course, but I cannot recall how it's called in its terms. I know how to use lookup tables in code to increase performance of my applications, so I don't need a definition of it in common sense.

I want to know a formal definition of an approach like lookup tables in complexity theory.


texts: Number of nodes of height $h$ in a heap or almost complete binary tree

texts:
I came up with the following statement:

  If there are $X$ nodes of height $h$ in an almost complete binary tree, there can be at most 1 node of height $h$ that is not full.

That is to say, $X-1$ must full and the last node of height $h$ may or may not be full.

Intuitively it seems right, but I can't seem to prove it. Could someone help me prove it. If the statement is false, please let me know why.


texts:
I am trying to enumerate and display all possible divisions of an n-polygon into (n-2) triangles (as in the following mathworld picture)

I know how to count how many divisions (Catalan numbers, 1, 2, 5, 14, 42, ... ), but I am struggling to find a way to generate all the C(n-2) triangulations. Can anyone point to existing software implementation, or at least to an algorithm that generates these triangles?


texts: A $k$-sorted array is one in which every element is at most distance $k$ from its position when the array is sorted.  The complexity of sorting such array is $O(n\log k)$. But if $k=1$, then $\log k=0$ so what happens? What is the complexity of sorting an array where each element is at most one place away from its sorted position?


texts: Bottom-up Mergesort vs Natural Merge Sort

texts:
I ran into natural mergesort in this Wikipedia page: https://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort
However, I can't find much information regarding:

The algorithm(s) to achieve natural mergesort, and the pros and cons of each method
How natural mergesort compares to bottom-up mergesort (pros and cons of each w.r.t the other)

In short, I'm looking for resources that would teach me algorithms to do natural mergesort, and how to weigh it against the usual bottom-up mergesort


texts: How the task is divided between multiple cores to perform in multiprocessing systems?

texts: I am trying to find  how single task is divided between two cores? what are the methods makes them work at the same time without  interfering with each other?


texts:
Im studing complexity theory and im reading this question on Quora.

According to what the guy is saying : if we are able to solve a NP-Hard problem in polynomial time we have prooved that P=NP.
But, in P we find problems that can be solved and checked in polynomial time and in this case we have only prooved that NP problems can be solved in polynomial time, but we dont know if this implies that can be also checked in polynomial time.


texts: Isoecursive Types When to Fold and Unfold

texts:
I'm trying to implement recursive types into my programming language. I've implemented extensible rows and was hoping to add some recursive typing in order to get something like this or self within a record (thus imitating objects). Recursive types would only occur in record definitions, like

record IntObject:
  val: int
  add: (IntObject -> IntObject)

Now IntObject is an alias for the type mu X. {val: int, add: (X -> X)}.

This represents an IntObject with a field val that has the type of a primitive integer, and an add method that takes in an IntObject and returns another IntObject, so I can use it like so:

IntObject(1).add(IntObject(2))

The definition of add would be something like.

record IntObject:
  def add(self, other):
    return IntObject(self.val + other.val)

Like in Python, instance method invocations have a reference to the object calling the method implicitly passed in as the first parameter. I'm not sure how Python does this, but I was thinking of doing the partial application of the instance methods at object creation. Therefore,

IntObject(1)

creates a record like this (using Haskell lambda syntax)

{val: 1, add: \other -> IntObject.add(self, other)}

I tried reading TAPL's section on recursive types, and isorecursion seems much easier to implement, especially since I will only allow records to have recursive types. What I'm unsure about is when to add folds and unfolds. TAPL says

  In Java each class definition implicitly introduces a recursive type, and invoking a method on an object involves an implicit unfold.

This is exactly what I want to do. If invoking a method introduces an unfold, that means that there needs to be a fold somewhere, and I'm unsure where to introduce that fold.

If this question is too vague, specifically since I probably haven't given enough information about the current state of my language, a general answer would suffice. Any advice regarding where to introduce folds and unfolds in an OOP language, say Java, would help a ton.


texts: DAG, search for cheapest descendants with same color

texts:
Let $G=(V,E)$ be a DAG. For each $v\in V$ you have a color $c(v): V \rightarrow \left\{c_1 \ldots c_k \right\}$ where $k$ is a fixed number, and a weight $p(v)$. For every $v \in V$ you have to find its descendant that has the same color and the lowest weight.

The problem requires an algorithm that runs in linear time.

A naive approach would use a search in topological order but that has $O(n^2)$ running time because you should perform it for every node.

Another idea could be reverse edges and do a visit starting from the sink. Then you may mantain a map that keeps updated the lowest encountered $p(v)$ corresponding to each color $c_k$, and assign the correct value to every discovered $v$. But what if there are more sinks?

Any suggestion to do this in linear time?

Edited

I'm wondering if the following may work (to simplify it keeps the lowest p(v) and not the node itself):

merge(src, dest)
  for i = 1 to k
    if src[c_i] < dest[c_i] then dest[c_i] = src[c_i]

visit(v,E,G)
  visited[v]=true
  map = [] array of k infinities
  for (v,u) in E do
    if visited(u) = false then
      map_u = visit(u, E, G)
      merge(map_u, map)
    else
      map_u = maps(u)
      merge(map_u, map)
    end if
  end for
  maps[v] = copy of map
  cost[v] = map[c(v)]
  if p(v) < map[c(v)] then map[c(v)] = p[v]
  return map

search(V,E)
  visited = new array of |V| elements
  for each v in V do: visited(v) = false
  for each v in V do:
    if visited[v] = false then visit(v, V, E)
  end for


texts: Why is it impossible to iterate over all TMs with $n$ states and $k$ symbols that halt after $m$ steps on $\epsilon$?

texts:
Define $\{\sigma(n,k,m,i)\}_{i=1}^{l_m}$ an ordered set of all TMs with $n$ states and $k$ symbols that halt after $m$ steps on $\epsilon$
There are $(2kn)^{kn}$ TMs with $n$ states and $k$ symbols, so $l_m$ is always finite and so is the range of $m$.
If we could iterate over $\sigma$ given $n,k$ for all $m,i$, then we could decide the halting problem:

Get $n,k$ from input machine
Iterate over $\sigma$ for all $m,i$ and check for each one if $\sigma(n,k,m,i)$ equals the input machine, if they are equal accept.
Reject.

This is odd because It seems very feasible to constract $\{\sigma(n,k,m,i)\}_{i=1}^{l_m}$ using elementary combinatorics. Even settling on a (computable) combinatorial formula for $l_m$ for all $m$ given $n,k$ will be enough to solve the haling problem since we will know how many machines are there that halt for each $m$, and we can simulate one step at a time for all the $(2kn)^{kn}$ machines and compare each machine that halts with the input machine until reaching $l_m$ for all $m$ without a correct comparison and reject.
Is there a fact (independent of it contradicting the Halting problem) that makes it clear why there is no computable combinatorial formula for $l_m(n,k)$? or am I missing some detail here?


texts: Fundamental motivation behind the use of bits and binary representation

texts:
This is a naive question, but what makes binary representation special from a theoretical standpoint and from the standpoint of information theory?

If for technical reasons building ternary computers where the information is encoded as trits was easier than building traditional binary computers, I get the feeling that most theoretical computer science and information theory would still use bits and base-2 representation by default.

Even if I have an intuitive feeling of why, I would have liked to know a formal explanation of that: from a purely theoretical standpoint what makes bits and binary representation special compared to any other base?

If the answer is more complex than one may first think, links to books and scientific papers are welcome.


texts: Row Major Vs Column Major Order: 2D arrays access in programming languages

texts:
Programmers prefer accessing a 2D array in Row-Major Order rather than Column-Major Order, Why?

Are there some advantages/benefits of accessing a 2D array in row-major as compare to column-major?

Like in C programming, programmers prefer row-major rather than column-major due to the way memory is being allocated to a 2D array when defined statically or dynamically.


texts: Theoretical speed gain of quad core vs. single core

texts:
I first asked this question at cstheory, but they suggested to ask my question here, so here it goes ...

I'm working on my masters thesis and I need to have theoretical value of the (average) speed gain that a quadcore processor brings compared to a singlecore processor, when they both use the same frequency. So for example the speed gain of a 2 GHz singlecore vs. 2 Ghz quadcore.

Somewhere on the internet I've read that a quadcore is 2.6 times faster than singlecore, but the author didn't mention any source so I cannot use that in my thesis.

I've been trying to calculate some things myself, but didn't come to a conclusion. I tried like this:

threads | quad core | single core | ratio
--------|-----------|-------------|-------
1       | 1         | 1           | 1
2       | 2         | 1/2         | 4
3       | 3         | 1/3         | 9
4       | 4         | 1/4         | 16
5       | 3+1/2     | 1/5         | 17.5
6       | 2+2(1/2)  | 1/5         | 15
7       | 1+3(1/2)  | 1/5         | 12.5
...

This table represents the timeslices available to execute a task (I've taken a fair 50/50 usage for each thread). For example when using a singlecore and a application uses 3 threads, each thread can work 1/3 of the time, while with a quadcore each thread can work 100% of the time, because 3 threads can be spread accross a separate core. After playing with some calculations in Excel, I could not come to any conclusion.

I'm a bit stuck and need some fresh ideas on how to get a theoretical number that represents how much faster a quad core is (on average) compared to a single core. Maybe some of you know some empirical numbers with a good reference to the source? Anyway, all the help is welcome, because I'm a bit stuck and this is the last part I need to cover in my thesis.

Thanks!


texts: Is there a general-case sweep line algorithm for line segment intersection?

texts:
I'm looking for a sweep line algorithm for finding all intersections in a set of line segments which doesn't necessarily require the general position constraint of Bentley-Ottman's algorithm (taken from Wikipedia):

No two line segment endpoints or crossings have the same x-coordinate
No line segment endpoint lies upon another line segment
No three line segments intersect at a single point.

Is there any sweep line solution to this problem? If not, is there any other algorithm that solves this problem in $\mathcal{O}((n+k) \log(n))$?


texts: Any finite Graph G with all V have at least degree of 2, is it true that every vertex is necessarily contained IN a cycle?

texts:
As title, (note: this questions is asking weather or not all vertices are contained IN a cycle not asking if the G contains a cycle.
My attempt is that:

So this graph would be an counter example that disprove that every vertex is contained in a cycle. Would like to know if this is a valid counter-example since V1 is not contained in a cycle.
PS: As I was finding examples, also observed that if the all V have exactly degree of 2, then it is necessary that all vertices are contained in a cycle. Please prove if I am missing something.


texts:
Given an arbitrary undirected graph $G = (V,E)$, I am interested in a low-polynomial time algorithm which can find several moderately large (ideally $O(n^\epsilon)$ vertices per clique for $\epsilon > 0$) cliques in $G$, provided they exist.

I am aware that the problem of finding the maximal clique is NP-hard. For my purposes, however, I don't need maximality per say. Rather, it would be helpful to have an algorithm which runs relatively quickly and with high probability finds some nontrivial cliques.

I am aware that for fixed $k$, finding a $k$-clique if it exists can be done in $n^k$ time by simply testing all subsets of $k$ vertices. This algorithm appears to be of limited use because of the exponential growth in $k$.

Does there exist an algorithm or multiple which can, with high probability, find multiple moderately large cliques in a general undirected graph?


texts: Process address space separation in L1 cache of Intel hyperthreaded CPUs

texts:
Since a processing core with hyperthreading enabled is presented as two or more cores to the operating system, it can run completely different processes with different, isolated virtual memory spaces. There must be a mechanism that guarantees process address space isolation. How is it done in Intel hyperthreaded CPUs with regards to L1 cache? I can think of three possibilities:

1) virtual-physical address mapping is done before L1 (could add delay to L1);

2) each virtual core has its own L1 cache (costs space on the die);

3) only different threads of the same process are allowed to be hyperthreaded (must be implemented in the OS kernel)

Or is it something completely different?


texts: Directed graph where DFS returns on a node before all its child nodes are visited?

texts:
Give an example of a directed graph in which a depth-ﬁrst search backs
  up from a vertex $v$ before all the vertices that can be reached from
  $v$ via one or more edges are discovered.

My professor recently asked this question as a warm up to lecture, but never answered it. I still have not figure how that is possible. Why would it return if it's not complete?

I just can't see a scenario where this would happen.

It would never return, since DFS is (essentially) recursive and it can't return without having hit all base cases.


texts:
im looking for a formal proof to demonstrate that all regular language is in L (logarithmic space).
I deduced that all regular languages has a DFA that accept them, so if i find a way to transform all DFA to a L-Space Turing Machine, i would be able to prove this.

Thanks for helping.


texts: Is it necessary to learn how to prove Mathematical theorems as a CS Student?

texts:
I've just started my undergraduate course and have tried my hands on MIT's OpenCourseWare on Discrete Math on Logic and Proofs. There was a particular question asking to prove Cantor's Theorem:

  Problem 4. If a set, $A$, is finite, then $|A| < 2^{|A|} = |\cal P(A)|$, and so there is no surjection from set $A$ to its powerset. Show that this is still true if $A$ is infinite. Hint: Remember Russell's paradox and consider $\{x \in A \mid x \notin f(x)\}$ where $f$ is such a surjection.

My question is: am I expected to prove these math theorems and should I focus on my proving skills (because they are proving to be quite difficult for me at the moment)? Do they make me a better problem solver in later courses such as Data Structures and Algorithms?


texts: What does "post-image analysis" mean in the context of formal program analysis?

texts:
I am reviewing an anonymous paper about a sort of static analysis of programs that uses the phrase "post-image analysis", or "post-image operation" without defining what that is. I am guessing it is a well-known concept in formal methods, even though a Google search has not revealed anything.

I am guessing it means an analysis of the trace of a segment of a program. Basically, you run it a little bit, you collect the trace (perhaps that's a synonym for "image"), and analyse. But I am just guessing.

Can anyone tell me what that is, or give me a pointer?


texts:
I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this:

  What is the minimum size of the largest clique in any graph with N nodes and M edges?

The hints suggest using Turan's theorem, but it's not clear to me how to get from that to a solution.

How can I solve this problem, either with or without Turan's theorem?

The full questions is here.


texts: What is the state of the algorithmic art for floating point arithmetic on complex numbers?

texts:
Most modern compilers and processors implement the IEEE 754 binary formats for floating point numbers. IEEE 754 guarantees that the addition, subtraction, multiplication, division, and square root operations on real floating point values are correctly rounded, meaning that the result of each operation is as if the operation were computed to infinite precision and then subsequently rounded according to the specified rounding mode (most commonly round to nearest, ties to even). In other words, it is guaranteed for these operations that the final floating point number is as close as possible to the true value of the operation given the mathematical values of the input floating point numbers.

A number of programming languages also offer complex floating point arithmetic. Addition and subtraction of complex floating point numbers can obviously guarantee correct rounding (treating the rounding mode as applying to each component separately), since these operations can be computed componentwise. Surely then, I assumed, the correct rounding guarantee also applies to common language-provided implementations of complex multiplication, division, and square root?

So far, I have found no evidence that this is the case, and a fair amount of evidence to the contrary. For example, this recent paper provides examples of wildly incorrect results that can be obtained from naive attempts at computing complex multiplication via multiple floating point roundings, and describes an algorithm for complex multiplication that produces results accurate to within 2 ulps (but not guaranteed 100% correctly rounded as defined above).

  Claude-Pierre Jeannerod, Christophe Monat, Laurent Thévenoux (2017). More accurate complex multiplication for embedded processors. SIES 2017.

This suggests that there is no standard/widely-used sequence of fused multiply-add tricks for doing complex multiplication with correct rounding. I've also found several references to the difficulty of computing complex division in a numerically-stable fashion.

Question 1: Given floating point inputs and outputs with $n$ exponent bits and $m$ significand bits, what is the best-known worst case time complexity for computing the correctly-rounded values of complex multiplication, division, and square root?

Question 2: Are any references available for methods for computing these complex operations with correct rounding using the real floating point operations available on a standard FPU?


texts: If L is a regular language then the language replace(L,σ,τ) is also regular

texts:
I am stuck at the following problem:

Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular.

Where $replace(L,\sigma,\tau)$ is defined as:

$replace(L,\sigma,\tau) = \{x\tau y\in \Sigma^*| x\sigma y\in L\}$.

My try:

Since $L$ is a regular language there exists a deterministic finite automaton $A=(\Sigma, Q, q_0, F, \delta_A)$ such that $L(A)=L$.

Now for each state $s\in Q$ we will define a non deterministic finite automaton $B_s=(\Sigma\cup\{\gamma\}, Q\times \{1,2\}, q_s, F\times \{2\}, \delta_{B_s})$
where $\gamma\notin \Sigma$ such that:

$\forall p\in Q,\mu\in\Sigma, \delta_{B_s}((p,1),\mu)=\{(\delta_A(p, \mu),1)\} $

$\forall p\in Q-\{s\}, \delta_{B_s}((p,1),\gamma)=\emptyset$

$\delta_{B_s}((s,1),\gamma)=\{(\delta_A(s,\sigma),2)\}$

$\forall p\in Q,\mu\in\Sigma, \delta_{B_s}((p,2),\mu)=\{(\delta_A(p, \mu),2)\} $

$\forall p\in Q, \delta_{B_s}((p,2),\gamma)=\emptyset$

Now we'all define a new non deterministic finite automaton with $\epsilon$ moves $B$ by linking he starting state of this automaton to all of the starting states of the automatons $B_{s}$ for every state $s$, And we will also link the final states of all of the $B_{s}$ automatons to the final state of the automaton $B$.

The automaton $B$ will satisfy the property $L(B)=\{x\gamma y|x\sigma y\in L\}$ ( This is probably incorrect!!!)

Now we will define an homomorphism $h:\Sigma\cup\{\gamma\}\longrightarrow\Sigma$ such that:

$\forall \mu\in\Sigma,h(\mu)=\mu$

$h(\gamma)=\tau$

Since regular languages are closed under homomorphisms we can conclude that $h(L(B))$ is regular, But $h(L(B))=h(\{x\gamma y|x\sigma y\in L\})=\{x\tau y|x\sigma y\in L\}$ and so $replace(L,\sigma,\tau)$ is regular over $\Sigma$.

Thanks for any hint or help.


texts:
I have to solve system of linear algebraic equations $AX=B$, where $A$ is a two-dimensional matrix with all elements of main diagonal equal to zero.

How to solve this problem? Iterational methods are not applied in this case.

One way is LU Decomposition method with reordering rows of $A$ to get entries in the main diagonal that are not zero, using permutation matrix. How can we quickly reorder the rows of the matrix or find the permutation matrix?

Note that the matrix dimensions are large and I have to write a program to solve SLAE in C# language, so I do not need any Matlab or Mathematica functions. Thanks!


texts:
How can I solve this recursive function using substitution method?
$$T(n) = 2T(n/3) + T (2n/3) + n^3$$
I substitute $T(n/3)$ and after that $T(n/9)$. when it goes to k-step, I'm stuck.


texts: given a weighted, directed graph. Give an O(VE)-time algorithm to find, for each vertex v∈V, the value δ∗(v)=Min u∈V{δ(u,v)}?

texts:
This is the 24.1-5 question in CLRS. I'm having a hard time understanding the questions and also how to solve it. δ(u,v) is defined as the shortest path weight from u to v if there exist a path from u to v.

Let G=(V,E) be a weighted, directed graph with weight function w:E→R. Give an O(VE)-time algorithm to find, for each vertex v∈V, the value δ∗(v)=Min u∈V{δ(u,v)}.

What I'm confusing about this question is what is δ∗(v) suppose to be. I also found the answer online but still don't really understand why it is like that. Since this is an exercise in the Bellman-Ford algorithm of CLRS. the answer said to change the RELAX operation of the algorithm. The RELAX operation in Bellman-Ford is what help achieve the shortest path weight after you run this V time for each edge in E.

the ORIGINAL-RELAX operation supposes to be like this:

RELAX(u, v, w)
if v.d > u.d + w(u,v)
   v.d = u.d + w(u,v)
   v.pi = u.pi

With v.d and u.d being the upper bound for the shortest path from source to u and v. v.pi is supposed to be its predecessor for the current upper bound.

The answer said to change the RELAX operation to this.

MOD-RELAX(u, v, w)
if v.d > min(w(u, v), w(u, v) + u.d)
   v.d = min(w(u, v), w(u, v) + u.d)
   v.pi = u.pi

I need some explaination to what the problem is asking for and why this answered it.


texts: Reducibility of 2 boolean satisfiability problems

texts:
I beg some help with this problem.

  There are 2 boolean satisfiability problems.

  Problem $A$: Determining whether an arbitrary formula of size $n$ is $satisfiable$.
  Problem $B$: Determining whether an arbitrary formula of size $n-1$ is $satisfiable$ in which $n$ is a positive integer $\ge 2$

  Prove that $A$ can be solvable if $B$ is solvable.

I guess the solution would be showing that $A$ is Turing-reducible to $B$. It means I have to show the oracle algorithm of $B$ derives the oracle algorithm of $A$.

As you see, the arbitrary formula of $B$ is $n-1$, but that of $A$ is $n$.
How can I suppose to entail the oracle algorithm about $A$ from the oracle of $B$, which is determining the formula of 1-less size than that of $B$?


texts: Shortest path between all pairs with colored nodes

texts:
I got a question from my homework in each I have the solution, but not the algorithm. I want to check if I understood it correctly.  The question is:

Let's say we have a directed graph with no cycles, it has N vertices and M edges.
Exactly 2018 vertices are colored green, and the others are black.
We know that in each shortest
path, each vertex is colored green,
perhaps without the first and the last node.

We can find the shortest path of all two pairs of nodes in:  O(___) and not less

What I tried:
If we run the Floyd Warshall algorithm on the 2018 green vertices we get the shortest path between all pairs of greens. (This is O(1) because of the green vertices amount is constant).

Now for each (u,v) in VxV:

If both u and v are green we already have the shortest path from Floyd Warshall.
If one is green and the other black, we add the edge's weight that connects the source/destination to the green group and add the Floyd Warshall result.
If both u and v, are black, we add the lightest weight of each which connects to the green group.

I think my solution is kind of messy, and I do not know if it's 100% correct.

The solution is: We can find the shortest path of all two pairs of nodes in:  O(n^2) and not less.


texts: On the hardness of satisfying K number of linear constraints

texts:
Background: Normally in linear programing we have some objective function
$$\text{maximize}\sum_{i = 1}^n a_i x_i $$
$$\text{subject to} \sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq m$$
where $a_i, b_{ji}, c_j$ are all constants given in the problem statement and each $x_i$ is an optimization variable which we may choose the value of. Note that the above problem may not have a feasible solution if all of the linear constraints cannot be satisfied at the same time. Determining if the constraints are satisfiable and optimizing the objective function can both be done in polynomial time.

Problem Statement: Consider a slightly modified version of the above problem where we don't care about the optimization function and are just given the set of constraints

$$\sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq m $$
We are interested in answering the question "can at least $k$ of these constraints can be satisfied?".

This feels NP-Hard as it it seems to amount to a combinatorial selection problem in the sense that we are now selecting a specific set of $k$ items out of $n$ possible items, and there could only be one such set of $k$ items that works.

Question: Is this problem NP-hard, what if we impose $0\leq x_i \leq 1$ for all $i$? If so, what problem could be used to construct a good reduction?


texts: Why in a min priority queue (heap based) it is called "decrease-key" and not just "set-key"?

texts:
When you call decrease-key in a min priority queue, you are basically setting the key, you can accidentally put a higher key, right? so why isn't it called "set-key" or "update-key"? why (according to Wikipedia and other sources) a min priority queue has "decrease-key" and a max priority queue has "increase-key"? why not have both "set-key" and if you decrease it or increase it, do what you should do to keep the heap property invariant?

I mean what if I call decrease-key on a min heap and give a bigger value? Will it throw an exception? Why not just call it "set-key" and handle any kind of value?


texts: Finding max average value subrectangle at least a certain size in a 2-d sparse array

texts:
So Kadane's dynamic programming solution for finding the maximum sum contiguous subinterval in a 1-d array runs in linear time, and can be adapted to give a best-known $O(m^2n)$ time solution to find a maximum sum contiguous rectangle in a 2-d array of size $m \times n$. (i.e. find max sum subarray defined by all entries satisfying upper and lower bounds for indices in both dimensions, over all choices of bounds).

However, if the 2-d array is sparse, with $N$ non-zero entries, then the running time can be improved to $O(Nn \log m)$, basically using the same brute force search over choices of start/end rows (or columns) and updating the optimal solution for each choice of start/end rows by storing the optimal solution of start/end columns for every contiguous subset of columns defined by sets of contiguous columns being repeatedly split in half into two contiguous sets of half as many columns, in a binary tree fashion, and some auxilary information is stored at each node in the tree, besides just the optimal solution of start/end column, like the optimal solution that ends at the rightmost column in the subset, or begins at the leftmost column. Then, when a new non-zero entry is added, the optimal solution and additional information is propagated from the leaf column to the root (representing the optimal solution over all columns), in constant time per propagation step, so overall $O(\log m)$ time.

Anyway, I would like to find a similarly good speed up for finding the maximum AVERAGE value contiguous 2-d subarray in a $m \times n$ array with $N$ non-zero entries. Obviously average value can be maximized by one single element in the array that has maximum value, so we put a lower bound of requiring at least $K$ cells in the subarray before finding maximum average. In terms of $m,n,N,K$, can a fast algorithm be found to solve this, i.e. faster than just assuming the input array is dense?


texts: Proof of correctness of algorithms (induction)

texts:
I am reading Algorithm's Design Manual by S.Skiena and I have a hard time understanding and proving the correctness of algorithms. I should use proof by induction and when we talk about summations and proving their formulas I can do it, I have no problem understanding why it is correct. When I get a loop on the other hand, I cannot even get started. I have a hard time combining the Loop invariant (also finding it) and the proof.

For example the following is a complete mystery (i tried reading a few similar questions on SO, but I still don't get it)

function multiply(y, z)
    if z = 0 then return(0) else
    return(multiply(cy, ⌊z/c⌋) + y · (z mod c))

I understand that I am asking a lot, but is it possible for someone to try to explain it step by step ? I am learning the book on my own, this is not a homework and I am not trying to cheat on anything, I just do not understand it.


texts: What is the correct regular expression for this language?

texts:
Consider the following problem:

$L$ is the language of regular expression $00^*11^*$. $DM(L)$ is the language obtained from $L$ by throwing away every even-length string belonging to it and for each odd-length string, removing the middle character. Determine what $DM(L)$ is, and tell whether or not it is regular.

Well, $L$ consists of all strings that have at least one $0$ followed by at least one $1$. After writing down a few strings in $L$ and then constructing $DM(L)$ from those, I came to the conclusion that $DM(L)$ consists of all even-length strings of $0$s and $1$s where all the $0$s precede all the $1$s. So, we either have an even number of $0$s followed by an even number of $1$s, or an odd number of $0$s followed by an odd number of $1$s. Note that the empty string $\epsilon$ is not in $DM(L)$. Therefore, a regular expression for $DM(L)$ is $$00(00)^*11(11)^* + 0(00)^*1(11)^*.$$ The first term of the regex takes care of even numbers of $0$s and $1$s and the second term takes care of odd numbers of both.

But, here's the official solution:

  DM(L) is regular. L consists of all strings of at least one 0 followed by at least one 1. Any even-length string in 00*11* can be constructed by deleting the middle character from a string in L. A regular expression for DM(L) can be written $00(00)^*(11)^* + (00)^*11(11)^* + 0(00)^*1(11)^*$. Note that this expression guarantees not only that the string will be in 0*1*, but that its length is even --- i.e., either even numbers of 0's and of 1's (the first two terms) or odd numbers of both (the third term).

My issue with the official solution is that it permits the strings $00$ and $11$ to be in $DM(L)$, but that is not possible since all strings in $DM(L)$ must have at least one $0$ and at least one $1$. So, what is the correct regular expression for $DM(L)$?


texts: For all oracles A, If $P^A \neq PSPACE^A$, then Does it imply that $P \neq PSPACE$?

texts:
My question related to relativized world. I would like to know about how to show that class is different from another class in the oracle world and whether this applied to our real world.
For example, let us have the following assumption: suppose for all oracles A we have $P^A \neq PSPACE^A$, then Does it imply that $P = PSPACE$?


texts:
Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages.

The first part of the answer in a book said that:

We give a DFA $A$ that is equivalent to TM $M$. Design $A$ in two stages.

We arrange the states and transitions of $A$ to simulate $M$ on the read-only input portion of the tape.
We assign the accept states of $A$ to correspond to the action of $M$ on the read/write portion of the tapeto the right of the input.

Given below the whole answer (sorry for using pictures but the answer was so long and I do not understand it and I have not enough time to write it):

But I do not understand many points:

Why the domain and the codomain of the defined function takes this form? and why only finitely many such functions exist as stated by the last line in the first paragraph?
Why the author wrote $F_{\epsilon}$ as in the third paragraph? did he used the idea of epsilon transitions?
The last paragraph in the solution I did not understand its idea at all?

Could anyone clarify the above questions for me please?

I saw an answer for the question here Single-tape Turing Machines with write-protected input recognize only Regular Languages but I did not understand it at all.


texts:
I can't find anywhere the meaning of $L^*$, given that $L$ is a language. I know $^* $ means repetition, for example $0^*$ = $\{ \epsilon, 0, 00, 000, \dots \}$. Or if $A$ is an alphabet $A^*$ are all the possible words.

Does $L^*$ mean the language whose words are the concatenation of the words of $L$?

For example if $L=\{ 01^n \mid n>0 \}$

then is $L^* = \{ 01^{n_1}01^{n_2} \dots \mid n_1>0, n_2>0, ... \} $?


texts: Is concurrent language CCS or CSP turing-equivalent in language power?

texts:
Does the concurrent language CSP (or CCS, $pi$-calculus) model interacting machines?
Is CSP (or CCS, $pi$-calculus) Turing-equivalent to other programming languages like C?


texts: How does the strong form of the PCP theorem imply the inapproximability of Max-XORSAT?

texts:
Theorem 11.4 For any constant $\delta > 0$, every problem in NP has probabilistically checkable proofs of length poly($n$), where the verifier flips $O(\log n)$ coins and looks at three bits of the proof, with completeness $1-\delta$ and soundness $1/2+\delta$.

Moreover, the conditions under which Arthur accepts are extremely simple - namely, if the parity of these three bits is even.
This theorem has powerful consequences for inapproximability. If we write down all the triplets of bits that Arthur could look at, we get a system of linear equations mod 2. If Merlin takes his best shot at a proof, the probability that Arthur will accept is the largest fraction of these equations that can be simultaneously satisfied. Thus even if we know that this fraction is either at least $1-\delta$ or at most $1/2+\delta$, it is NP-hard to tell which. This implies that it is NP-hard to approximate Max-XORSAT within any constant factor better than $1/2$.

First, I don't think it can be as simple as just checking that the parity is even. Merlin could just make Arthur accept anything by handing him a proof of all zeros, and make him reject anything with a proof of all ones. Surely the parity must instead equal some value that Arthur computes along the way.
Further, It's not a priori clear to me that Arthur would select every triplet with equal likelihood. If that wasn't the case, wouldn't it be possible for a no-instance to yield a Max-XORSAT formula where more than $1/2+\delta$ of the clauses can be satisfied even though Arthur accepts with probability less than $1/2+\delta$?
Let's take a degenerate case as an example. Arthur asks Merlin to help him decide whether a given sequence of $n$ bits $\mathbf{b}$ is all ones - $\mathbf{b=1}$ for short.  This problem is trivially in NP. And Arthur clearly doesn't need Merlin's help. But he can go out of his way to use it anyway. Here's what they do:
First Merlin gives Arthur a PCP $\mathbf{x} \in \{0,1\}^n$ (let's assume $n \gg 3$). Then Arthur checks if $\mathbf{b=1}.$ If it is, he checks that $x_1 \oplus x_2 \oplus x_3 = 1$ holds in Merlin's PCP. Otherwise, he checks either $x_1 \oplus x_2 \oplus x_3 = 1$ or $\overline{x_1} \oplus \overline{x_2} \oplus \overline{x_3} = 1$ (note that these can't both be satisfied) with equal probability 0.45. Or with probability 0.1 he checks $x_i \oplus x_j \oplus x_k = 1$ for a uniformly random triplet.
Merlin can thus convince Arthur that $\mathbf{b=1}$ by giving him, for example, the proof consisting of all ones. But if $\mathbf{b\neq1}$ there's no proof that Arthur accepts with probability greater than 0.55. This gives PCP's with completeness $1-\delta$ (indeed we also have completeness 1) and soundness $1/2+\delta$ where $\delta = 0.05$.
Now what's the Max-XORSAT formula corresponding to $\mathbf{b\neq1}$? Well, Arthur could look at any triplet $x_i, x_j, x_k$ as well as $\overline{x_1},\overline{x_2},\overline{x_3}$. So presumably it's the conjunction of all those triplets when XORed together. All but one of these clauses can be satisfied. So the fraction is very close to one. But that's nowhere near the probability that Arthur will actually accept.
PS: We need a PCP tag.


texts:
I was doing a practice question. As you can see below there is an Implication graph. To check whether the problem is satisfiable, I checked whether there were any 'bad loops'. To do so, for each literal/variable in the boolean formula, I see if there is a path from X --->-X and from -X---->X if both exist then a 'bad loop' exists and thus the problem is not satisfiable. I did that and saw that there were no such loops and thus I came to the conclusion that the 2SAT problem was satisfiable. See below:

I realized that option d (The 2SAT problem is satisfiable if a,b,c and d are set to false. I'm struggling to come to this conclusion by looking at the graph. My understanding is that you take all the paths in the graph, and see if you come to a contradiction? Can someone please let me understand how to understand option d being correct.

Thanks in advance!

The method I have come up with is to write out the arcs/edges for each implication and work backwards to derive the 2SAT boolean formula and see if it works. Does anyone know a quicker way? :)


texts: In Axioms and Hulls, Knuth defines the notion of a CC system, which is a generalization of Euclidean points in general position. While all such arrangements of points in the plane give a CC system, not all CC systems give an arrangement of points, i.e. are not realizable. Is there a polynomial-time procedure to determine if a given CC system is realizable?


texts: How to estimate floating-point precision of function?

texts:
Let's say I have a function that consists solely of floating-point operations where the last operation rounds the computed value to a predefined number of digits. And I feed this function with a range of floats.

How do I conclude - just by looking at the decimals of the operand(s), and the structure of the code / sequence of floating-point calculations - that the round-up errors may or may not yield an unexpected result?

Do you know of any rule of thumb or mathematical methodology? Anything I can put to general use? I don't want to actually test the code.

Just one example for reference; range of input, required precision, and implementation of calc() are arbitrary:

Input: 0, 0.01, 0.02 ... 999.98, 999.99, 1000 (delta = 0.01)

Required precision: Rounded accurately to 2nd decimal

Pseudo code:

function main(a) {
  res = calc(a);
  return round(res); // Rounds res to desired decimals
}

function calc(a) {
  float b = 1.1;
  return a * b;
}

Update #1:

I found an interesting blogpost on the topic: Introduction to Scientific Computing: Error Propagation

It seems to contain the mathematical tools one needs to evaluate how "error prone" a computation is.

Update #2:

I worked out the following method to estimate the error propagation and will describe how I applied it on my use case.

It would be great if you comment on my thoughts. I'm not sure if I did it right. And thanks for your help so far! :)

Pseudo code:

// Floats conform to IEEE 547

function main() {
  float a,b; // Real value between 199 and 684
  a = some_value;
  b = another_value;
  res_a = calc(a);
  res_b = calc(b);
  res = res_a + res_b;
  return round(res); // Rounds to 2nd decimal
}

function calc(x) {
  float c = yet_another_value; // Real value between 1 and 1.4
  return c * x;
}

Estimation:

As I'm using IEEE 547 floats, the machine epsilon ε is 1.1e-16.
The relative error δ is 2ε - according to the article linked under update #1.
So the absolute error of my maximal input emax won't exceed 3.8304e-13. *
That means the result will be precise up to the 12th decimal.
Since I just desire a precision of 2, the calculation does work precisely enough.

*) emax = 2ε * resmax = 2 * 1.1e-16 * 2 * 684 * 1.4 = 3.8304e-13.

Bonus consideration:

Q: Would one add up the results of calc() infinitely, how many results would be "needed" approximately to contaminate the rounded total?

A: One would have to call calc() at least 4 trillion times. \o/

e has to be at least 0.001 to force a round-up error
The maximum result of calc() is xmax = 684 * 1.4 = 957.6
e = δ * x => x = e / δ = e / 2ε = 1e-3 / (2 * 1.1e-16) = 1e+13 / 2.2
n = x / xmax = 1e+13 / (2.2 * 957.6) ≈ 4e+9


texts: Single-valued enumeration of all c.e. sets

texts:
Please help prove the following statement:

  There exists a single-valued computable enumeration of the family of computably enumerable sets.

Definitions:

1) Let $S$ be nonempty countable set (possibly finite). Any surjective map $\nu\colon \omega \twoheadrightarrow S$ from the set $\omega$ of natural numbers onto the set $S$ is called an enumeration.

2) An enumeration  $\nu$ is single-valued if $\nu$ is a bijective, i.e.  $\nu(x) \neq   \nu(y)$ for any $x \ne y$.