texts: FInd a graph on a vertex set similar to another graph

texts:
I am looking for a possible algorithmic solution to this problem, but I can't figure out any.

Let's say I have a weighted graph (call it G); each vertex on this graph represents a point in a plane, and each edge has the distance as its weight.

Now I have another set of vertex, let's call it S, representing points in the same plane.

My goal is to find a new graph whose vertex are taken from S, and that should be "as similar as possible" to the graph G. For me similar means that reciprocal positions and distances for connected vertices must be similar as much as possible to those of correspondent vertices in G.

Maybe such an algorithm already exists but I did not manage to find it.

Thank you for your time!

Edit: there is no correspondences between vertices as an input of the problem. I'll try to better explain the metric of similarity; since vertices may represent geographical coordinates I would like this two properties:

Correspondent edges weight (i.e distance of connected vertices) should be as close as possible.
Correspondent edges direction (i.e. variation of connected vertices coordinates on each axis) should be as close as possible.

This kind of "reciprocal position" constraint is needed because vertices represent geographical points. Also, not every point in S has to be chosen as a vertex for the new graph since it may contains more points than the number of vertices of G.

Thanks


texts: Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

texts:
Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths connecting $s$ and $t$, each of which has weight at most $M$?  In other words, we are given an upper bound on the path weights, and we want to know whether there exists two paths from $s$ to $t$ that don't have any edge in common.

Call this problem DPBP (for disjoint pair of bounded paths).

Is DPBP NP-complete?

A variant of this problem can be solved in polynomial time.  In particular, Suurballe's algorithm can be used to find a pair of edge-disjoint paths where the sum of their weights is minimal; thus, it can be used to decide whether there exists a pair of edge-disjoint paths such that their weights sum to at most $M$.  But what about when we require each path to have weight at most $M$, instead of requiring that their two weights sum to at most $M$?


texts: Compact Shared Reduced Binary Decision Diagrams with negated identifiers

texts:
Consider a BDD implementation in which each bdd in the system has a unique positive integer identifying it (thanks to canonicity and as common implementation designs follow, by utilizing a hashmap). I was thinking of assigning a negative integer to a bdd in order to represent its negation. So say bdd id -3 will be bdd id 3 with just flipping the terminal nodes when processing them. The building blocks for new bdds would be the terminal T,F nodes, and the "ith var" bdd, where if the ith var is false then we get an id being the negation of the id of the bdd representing the ith var being true.

My question is whether such design breaks canonicity, or I can still rely on bdds having same (positive or negative) identifier to be equal.


texts:
The books I'm reading on complexity theory primarily are about complexity of decision problems by Turing machines.

I'm interested in computational complexity of circuits, both boolean and continuous circuits (I'm not sure to what extent there is a complexity theory of continuous circuits). Do you know of a good introductory text for this?


texts:
Data Description :

A database consisting of many Transits. Each transit has its own Path (both forward and backward), and each path has a set of Stops. Each stop consists of the position and the naming.

Each stop has a parent, for example, a 4-way intersection with a stop on each corner, where you can dismount transit X, and get on transit Y from the other side.

Each Path, forward or backward, is considered a unique path. (e.g, if 4 transits are present, the total number of Paths is 8).

Input :

2 points (A & B) on map, with latitude and longitude each. One is Source and one is Destination.

Output :

All possible routes between point A and point B, without duplicates (i.e, the same result with different info. Like Transit X then transit Y, but different intersection point).
For Example, one route might tell you to walk 50m to a transit that is crowded, while the other tells you to walk 200m to a transit that is relatively easier to find seats.

Ideas so far :

To find the direction, and transits to use, from point A to point B, do the following :

1- Find all stops that are around point A, using a calculation with the latitude and longitude.

2- Find all stops that are around point B, using a calculation with the latitude and longitude.

3- Get the paths for all transits that pass through all the stops around point A.

4- Go through all stops that are after the stops around point A in each of the transits, and find if any of them correspond to the stops around point B.

5- If no results are found, repeat steps 3 & 4 for each stop after the stops around point A in each of the transits, along with the stops that belong to the same parent (Finding the transits that pass through them, and checking if the stops after them in the path belong to the stops around point B, or a sibling to the stop), with a maximum of 4 transits deep (4 paths).

Results :

For finding a result that needs 2 transits to reach, the results are in average time (around 5 seconds).

But when the results needs 3 or more transits, the results take very long (around 30 seconds) if they find a result, and if the result is deep in the search, it can take minutes.

Post Information :

I'm not familiar with many search algorithms, but I don't think a tree would work here, as a tree is a set of known sources and destinations, whereas in this situation, I don't know the sources and destinations beforehand. And there are no weights for each of the paths down the tree.

And the way I'm using is the usual list search, without anything special or any optimizations, the only optimization is I don't search the same transit twice, and only search the stops after in the path.

Question :

What are possible implementations of such a search? What algorithms should I consider using?

Live Examples :

The Google Directions search.

Post Script :

I can't use the Google API because the data for the country I'm creating the search for isn't available in Google.


texts: Decision tree lower bound for finding two array elements summing to zero

texts:
I have to solve this exercise:

  Given an unordered array $A[1], \ldots, A[n]$ of positive and negative integers,
  determine if there are two indices $i \neq j$ such that
  $A[i] + A[j] = 0$. Establish a lower limit to the problem using the
  decision tree technique.

The solution should be $Ω(\log s(n))$, where $s(n)$ is number of possible solutions, in this case $n^2$.

But, I don't understand why the number of possible solutions is $n^2$ rather than $\binom{n}{2}$.


texts: What is space complexity of shrinking one array to increase another?

texts:
Say I have an array and I want to add those values to something else. What is the space complexity if I incrementally take one of those values off the first list and add it to the second? For example, I'm trying to convert a list to a string. I know that if I do the following, the space complexity will be O(N):

a = [1,2,3,4]
b = set(a)

But if instead I incrementally shrunk a, what would the space complexity be?

a = [1,2,3,4]
b = set()
for _ in range(len(a)):
    b.add(a.pop())

Now b has what I want and a is empty. Does that make it O(1) in space complexity?

If the language matters, I'm most interested in Python, but I would like to know the most general answer as well.


texts:
Heap supports insert operation in $O(\log n)$ time. And while heap supports remove min/max in $O(\log n)$ time, to remove any element (non min/max) heap takes $O(n)$ time.

However, red-black tree supports insert/remove both in $O(\log n)$ time. We can just remove the first/last element in a red-black tree to remove min/max in $O(\log n)$ time.

I do understand that heaps are used specifically to remove the min/max, but it seems like red-black trees can do what heaps can do but just faster/equal.

Is there any distinctive advantage to using heaps over red-black trees?


texts: Need help about solving a recurrence relation

texts:
I have a recurrence relation which is like the following:

$T(n) = 2T(\frac{n}{2}) + \log_{2}n$

I am using recursion tree method to solve this. And at the end, i came up with the following equation:

$T(n)=(2\log_{2}n)(n-1)-(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$ where $k=\log_{2}n$

I am trying to find a theta notation for this equation. But i cannot find a closed formula for the sum $(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$. How can I find a big theta notation for $T(n)$?


texts: Is Wadler's 'Theorems for Free' as general as Design By Contract for establishing correctness?

texts:
Philip Wadler has written a brilliant paper called 'Theorems for Free'. The big idea is that you can use types to reason about your program, and even prove simple theorems about your program.

We see these ideas about types applied in the Haskell language.

At very roughly the same time period - we have an idea from Betrand Meyer called 'Design By Contract'- which is most notably implemented in the Eiffel Language. This has the following features:

routine preconditions
routine postconditions
class invariants
check instructions (like assert)
loop invariants

The idea behind Design by Contract is software designers should define formal, precise and verifiable interface specifications for software components, which extend the ordinary definition of abstract data types with preconditions, postconditions and invariants.

Now many claim that using 'Types' in your programs leads to 'more correct programs' (via the Howard Curry Correspondence).  From what I can see - even the most advanced use of Dependent Typing in Idris and Scala is limited to Sum Types and list lengths (correct me if I'm wrong).

By contrast - the power of 'Design By Contract' in establishing the correctness of my program is more general and more powerful. (Albeit not necessarily at compile-time - but at test time). I can for example establish in my banking program that all deposits are positive, and all reported account balances are positive.

The point being - types have a fascinating future of possibilities, and are enormously powerful and compile time - but right now their practical application seems limited.

My question is: is design by contract of more general application than using theorems from types to reason about the correctness of my program at present? (Or are we just talking about two different things)


texts: Formal model of execution for Java (or general imperative language)

texts:
I'm trying to prove some statements about execution in Java programs under some heavy restrictions (basically I have a conjecture that if two methods satisfy a set of constraints for a given input then the are they equivalent - i.e., that return value and state after execution are identical). To prove this I'm looking for some sort of formalism that will let me talk about this.

I'm familiar with the operational semantics of functional languages and I could possibly translate for loops/while loops to recursive functions... I'd rather not do this and it would be nice to have some machinery so I could stay in imperative land.

More specifically, I want to reason about the state of a method at the kth step of execution. This includes global state:

Calls like this.field = 2 update our class state
Calls modifying parameters update state outside of our method:

myParam.setFoo(...)
myParam.x = y

Calls to static methods

Blah.static_side_effects()

I am assuming that all of this is deterministic. That is, I want to formalize the assumption that if any of these global updates to state occur in two methods, both of whose global and local execution states are identical, then the new state will also be identical - that each step of computation is determined precisely by global state and local state. This obviously precludes RNGs and parallelism (but I may deal with this later...).

Any ideas or sources on how I could approach this? My only thought is to treat methods as a list of statements and try to describe a statements semantics formally.

If possible I'd love to do this at the Java language level rather than the JVM level. This may not be feasible but my goal for now is to make some reasonable assumptions about my operational semantics and then take it from there.

Oh, one final note - any suggestions on how I can improve this question would be greatly appreciated. I'm kind of flailing around trying to find the right language to ask the question and if I'm abusing terminology (like local/global execution state...) I'd love to correct this.


texts: Showing resolution algorithm for 2SAT is polynomial time

texts:
I don't quite understand why the resolution algorithm completes in polynomial time for 2SAT but not 3SAT.
I'm looking at slide 42 of these slides for reference. It is clear that given two clauses of length at most 2, their resolvent has length at most 2. From $k$ propositional variables $x_1,\dots,x_k$, I see that there are $(2k)^2=4k^2$ possible clauses of the form $(a\lor b)$ where $a,b\in\{x_i\}\cup\{\lnot{x_i}\}$, so there are $O(k^2)$ possible clauses of length at most 2.
But how is this used to show that the resolution algorithm runs in polynomial time for 2SAT but not 3SAT?


texts: Understanding terms related to 2SAT algorithm

texts:
Recently I am learning about solution of the 2-satiability problem using strongly connected components. There is a theorem related to this problem given below:
Let $F = Q_lx_1 Q_2x_2\ldots Q_nx_n C$ be a quantified Boolean formula with no free variables, where each $Q_i$ is either universal or existential, and $C$ is in conjunctive normal form. That is, $C$ is a conjunction of clauses, each clause is a disjunction of literals, and each literal is either a variable, $x_i$, or the negation of a variable, $x_i$ ($1 \leq i \leq n$).

Theorem 2: The formula $F$ is true if and only if none of the following three conditions holds:
3(i) An existential vertex $u$ is in the same strong component as its complement $u’$.
3(ii) A universal vertex $u_i$ is in the same strong component as an existential vertex $u_j$ such that $j < i$ (i.e., $x_i$ is not quantified within the scope of $Q_i$).
3(iii) There is a path from a universal vertex $u$ to another universal vertex $v$. (This condition includes the case that $v = u$.)

In the proof they use this definition:
We call a vertex universal if the corresponding variable is universally quantified and existential otherwise.
But I am not familiar with the terms universal vertex and existential vertex. Can any one please explain these terms to me?


texts: Group time series events into minimal amount of buckets

texts:
I'm trying to efficiently compute events in a time series by grouping them into buckets. My goal is to have as few buckets as possible. The constraint is that events within one bucket are all within a 30 minute time window.
To get more concrete, let's assume I've got these events:

time
event

15:15
1

16:58
2

17:13
3

17:21
4

A naive approach to group those events into 30 minute intervals would result in these 3 buckets
bucket 1: 15:00-15:30 – event 1
bucket 2: 16:30-17:00 – event 2
bucket 3: 17:00-17:30 – event 3,4

A better solution with fewer buckets is possible though:
bucket 1: 15:00-15:30 – event 1
bucket 2: 16:58-17:28 – event 2,3,4

What kind of algorithm do I need to look for to efficiently find the fewest amount of buckets for this kind of data?
I'd prefer a fast solution (i.e less than $O(n^2)$) over an optimal one.


texts: if a graph G(V,E) is connected $|E|\geq|V|-1$

texts:
If a graph G(V,E) is connected the number of edges is at least the number of Vertices-1.
It is pretty evident if you think about it but how do i prove it formally?


texts: Prefix complexity of x conditioned on prefix complexity of x

texts: I wonder what is $K(x|K(x))$, $K$ denoting (Kolmogorov-Chaitin) prefix complexity. Naively, it looks like it should just be $K(x)+O(1)$. Is that right? The same question for plain Kolmogorov complexity is interesting as well.


texts: PDA that accepts if there is an "a" in the second half of the string

texts:
How could I build a PDA on $Σ = \{a,b\}$ that accepts if there is an "a" in the second half of the string?

Formally the language is the following: $L = \{xy \mid x ∈ Σ^*, y ∈ Σ^*aΣ^* \land |x| ≥ |y|\}$.


texts:
Given a tube with numbered balls (random). The tube has holes to remove a ball. Consider the following steps for one operation:

You can pick one or more balls from the holes and remember the order in which you picked the balls.
You need to tilt the pipe towards left side so that remaining balls in the pipe shifts towards left and occupy the empty space created by removing the balls.
You are not supposed to change the order in which you picked the numbered balls from the pipe. Now you put them back again in the pipe using the vacant space created by movement of balls.

Steps 1 to 3 is considered as one operation.

Find out the minimum operations required to sort the numbered balls in the ascending order.

For example:
If tube contains: $[1\ 4\ 2\ 3\ 5\ 6]$

Then we can take out $4$ and $5$ and $6$, and if we tilt pipe to the left, we get $[1\ 2\ 3]$, and we insert $(4\ 5\ 6)$ in that order to the end of pipe to get $[1\ 2\ 3\ 4\ 5\ 6]$.

So minimum number of steps required is 1.  I need to find minimum operations to sort the pipe.

Any ideas or hints on how to solve this problem?


texts:
I read a statement that was unclear to me, and was hoping to get some clarification.

It said that given a full binary tree with $n > 2$ leaves, there exists some internal node such that one third to two thirds of all $n$ leaves in the tree are its descendants.

From my understanding, I know each internal node in a full binary tree has 2 children. That said, the whole tree has $2n - 1$ nodes, which means $n - 1$ of them are internal nodes (not leaves).

I can come up with drawn examples where this is always the case, but I am not sure how to formally reason it. Any help would be greatly appreciated.


texts: Finding number of numbers <= N, containing atleast one of the digits 2,4,6,8

texts:
Given an integer $N$, I want to find the number of numbers $\le N$, that contain at least one of the digits from the set $\{2, 4, 6, 8\}$. How do I go about solving this problem?
I was thinking of constructing all possible numbers that fit into the integer size of the language that I am using, through a recursive procedure, but I am not sure how to do that. It seems complicated. Is there an alternative solution apart from taking some of the digits from the given set and constructing numbers?


texts: What does mean by the independent columns in 4NF normalization?

texts:
For a table to satisfy the Fourth Normal Form, it should satisfy the following two conditions:
It should be in the Boyce-Codd Normal Form.
And, the table should not have any Multi-valued Dependency.
The table should have at least 3 attributes and B and C should be independent for $A \twoheadrightarrow B$ multivalued dependency.
Now, I do not get the meaning of the following line "for a relation $R(A,B,C)$, if there is a multi-valued dependency between, A and B, then B and C should be independent of each other."
What does mean by independent of each other? Does the word independent mean that there should not be any FD such as $B\rightarrow C$ , or $C\rightarrow B$, or $BC \rightarrow A$?
Please help me. I did not get any proper explanation of this line or I failed to understand the meaning of the line in different sources.


texts: Turing Machine Encoding and Complement of the Diagonal Language

texts:
In trying to understand how Turing Machine encoding works, there is a question that I have come across that goes something like this:

Given that the diagonal language, $L_d = \{ w_i \mid w_i \space is \space not \space accepted \space by \space M_i \}$, what is the first string of the encoding of the complement of $L_d$ which is $\bar{L_d}$?

I am assuming also that this is operating with the alphabet of $\Sigma = \{0, 1\}$. Is there any way that it is even possible? I am confused also since $L_d$ is an undecidable language how this is possible?

Also by encoding I think that the question is referring to binary encoding with a tape alphabet $\{0, 1, B\}$ with Turing machine $M$ defined as:

$M = < Q, \{0, 1\}, \{0, 1, B\},\delta,q_1,B,\{q_2\} >$

with moves defined by:

$\delta(q_i,X_j) = (q_k,X_n,D_m) \rightarrow 0^i10^j10^k10^n10^m $

where $X_1 = 0, X_2 = 1, X_3 = B$
and Direction is given by: $D_1 = L, D_2 = R$,

and the Binary encoding of $M$ as $<M>$: $111 \space move_1 \space 11 \space move_2 \space 11 \space ... \space 11 \space move_{last} \space 111$

Update: If my understanding is correct, the correct encoding should represent a Turing machine which accepts every string since originally we do not accept any string? How would one go about formulating an encoding for such a Turing machine? Does it have to be a unique encoding, or does it just imply that any Turing machine that accepts every string is valid?


texts:
I am trying to design an efficienct algorithm to color a unicyclic graph. I know if a graph does not contain any cycles (it's a tree) then it is 2-colorable. But cycles are either 2 (is even number of vertices) or 3 (is odd number of vertices) colorable. So if there contains just one cycle then the chromatic number of this unicyclic graph should be 3 (if the cycle contains an odd number of vertices).

So enough of that. on to the algorithm.

I would start at a vertex and color it color1. Now I would perform a BSF from the originator. Then each vertex that is adjacent to the originator vertex i would color it color 2, and continue this process of switching from color1 to color 2 unless if one of the vertices has an adjacent vertex that is already colored the same color. That means i found the cycle and will color that vertex color 3. If it had an adajcent vertex that was a different color than what i was going to color it then its an even number cycle and it would be 2-colorable.

So that means, each step of the BFS I would check each vertex adjacent to the vertex selected for that step of the BFS. Therefore $O(|E|)$?

is there a more efficient algorithm to color a unicyclic graph and is my time complexity correct?


texts: Fair assignment of storage for multiple writers (load balance)

texts:
I'm trying to optimize a system with a better algorithm for allocating storage.  The system has 'N' writer processes and 'M' disks. (N < 30, M < 10. N can change, M is constant).
Any process can write to any disk and each process regularly writes a file every, say, 5 minutes, but the size of the file can be quite different. Each writer independently "chooses" which disk it writes to on a file-by-file basis; so it might write one file to Disk 2 and the next file a few minutes later to disk 8. There is no communication between writers.
This goes on forever.

In the steady state, all disks are "full" and a "deleter" process continuously deletes the oldest files until all disks are no longer "really full".  (there are two water marks: "almost full" and "really full", if that helps), so the "deleter" wants:
        Almost Full    Really Full
Disk 1       Y             N
Disk 2       Y             N
Disk 3       Y             N

I need to optimize how the writer chooses which disk to write to such that, as much as possible, different writers are writing to different disks. This is important to balance I/O load.
I had thought this wouldn't be too hard, but the more I think of it, the more problems arise. I've tried a number of things:

Randomly choose disk from those with free space. However since there aren't many disks (M is small), there is a good chance all writers will choose the same destination disk and overload the I/O system.  Bad.

Index/hash the writer number across the list of disks with free space. So if N == M, Writer 1 always ends up writing to Disk 1. However this fights with the deleter working to maintain free space by deleting the oldest files: eg, the first disk gets full but the oldest file is on a different disk.

Use first free disk. However this ends up with all writers writing to the same disk.


texts: Definition of profiling in information science

texts:
According to the Wikipedia articles,

  In information science, profiling refers to the process of
  construction and application of user profiles generated by
  computerized data analysis. This involves the use of algorithms or
  other mathematical techniques that allow the discovery of patterns or
  correlations in large quantities of data, aggregated in databases.

Although I like this definition, I would like to cite a book or article. Is there a book or article that provides the definition of profiling in information science?


texts: Is repetition the origin of countability?

texts:
The original question was "Do all non-regular languages have an uncountable number of strings?".

How can someone prove that..? I am squeezing my head but I can't figure it out.

And the other side of the coin: is a language always regular, if it has a countably infinite number of strings?

A bit more generally: is repetition (DFAs) the origin of countability (and/or vice versa?) and if so, why?

Thank you in advance for your help.


texts:
I was studying branch prediction & predication execution and faced a trouble..

I'm not quite sure whether I understood the concept of predication but based on what I have learned it is taking both taken and not taken at the same time.

For example, let's assume we have 'if' and 'else' each filled with 3 instructions.

For branch prediction, if prediction is correct, we won't have any loss in performance. But if prediction is wrong, there's a waste of 3 instructions.

For predication, either right or wrong, we will have waste of 3 instructions.
Then what is the use of predication?

Branch prediction has an accuracy over 90%(I don't know if this only applies to branches with many instructions that can learn from history).

If so, we have a low chance of wasting.

But even besides that, only when prediction accuracy is 0%, branch prediction will be same as predication.

SO where am I getting wrong?


texts: Optimal ordering - Dynamic programming on subsets

texts:
We have a set T of n elements and m subsets $R_i \subset T i = 1,...,m$.
The $S_i$ are not assumed to be different. We also define an ordering of T, a one-to-one mapping $\pi$ of $T$ onto the set of integers ${1,...n}$. That is, every $\pi(v)$ is an integer from 1 to n and all $\pi(v), v \in T$ are distinct. For a set $R \subset T$ and an ordering of $\pi$ of $V$, let $l_\pi(S)$ and $r_\pi(S)$ denote, respectively, the smallest and largest value $\pi(v)$ among all $v \in S$. The problem is to find an ordering $\pi$ that minimizes $\sum_{i=1}^m (r_\pi(S_i) - l_\pi(S_i))$.

This problem is NP-hard but is in FPT and can be solved with dynamic programming on subsets in $O^*(2^n)$

The idea here is to optimize the ordering of the first $k$ items and then go from $k$ to $k+1$ items and prove that the time complexity does not change when doing so.

But how do we optimize the ordering for the first $k$ items in just $O^*(2^n)$ time? It seems like the same problem as the initial one to me.


texts: Should one learn proofs for the correctness of algorithms? Why?

texts: I'm reading Introduction to Algorithms and would like to know if learning the proofs is worthwhile.


texts: Superscalar processors and complex instructions

texts:
I read that a supercalar processor has redundant functional units. One can read this e.g. on Wikipedia.

How do such redundant units work?

Is a complex instruction (for accelerating heavy process, for example Instructions used in Intel IPP, Integrated Performance Primitives) decomposed in micro operations befaure being dispatched among these redudant functional units?

What about hardware instructions? Like AES-NI?

I also read the Wikipedia article SMT and did not understand the following sentence:

  Superscalar means executing multiple instructions at the same time while thread-level parallelism (TLP) executes instructions from multiple threads within one processor chip at the same time.

I don't understand very well the distinction between these two things. Can somebody explain the subtleties?


texts: Finding at least two paths of same length in a directed graph

texts:
Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$.
I would like to know if there are already algorithms for calculating the following decision problem:

  Are there at least two paths between $A$ and $B$ of the same length?

How about the complexity? Can I solve it in polynomial time?

I would like to add a new constrain on the graph, maybe the problem is more solvable.
On adjacency matrix, every column is not empty. So, every node has at least one arrow on input and there is also at least one node connected to itself. So if the node is the $i$-th node, then $(i,i)$ is an edge in the graph.


texts: Worst Case running time of the Minimum Vertex Cover Approximation algorithm

texts:
Considering this factor $2$ minimum vertex cover approximation algorithm :

  Repeat while there is an edge:

  Arbitrarily pick an uncovered edge $e=(u,v)$ and add $u$ and $v$ to the
  solution. Delete $u$ and $v$ from the graph. Finally output the candidate cover.

I want to find the worst case running time of this algorithm. Since in a fully connected graph we have $O(n^2)$ edges, then the loop will run at most $O(n^2)$ times.

Here I am not sure what the maximal number of delete operations could be or perhaps for less than $O(n^2)$ edges being processed in the loop there would be some scenario with a large number of delete operations would contribute to the overall complexity.

I want to say naively that in the worst case you simply multiply the max number of edges possible with the max number of delete operations possible (both $O(n^2))$ giving $O(n^4)$, but this seems wrong.

Any insights appreciated.


texts:
I've struggled in the closure properties of the general class of languages because I couldn't use any automata concept and grammars.

In specific, I'm interested in dependency of operations.

(The operation $A$ is dependent to other operations $\Sigma$ when every class of languages is closed under some operations $\Sigma$, then it must be closed under an operation $A$.)

So there is some questions about this.

When I solve the problem about the closure properties of general class of languages(not CFL, REG, or else which is directly related to some grammar systems, machines and automata.), what concepts could I use?

For example, when I solve about the problem about full-trio
I just use the definitions of morphism, inverse morphism, intersection by regular languages but this is too weak and hard to find suitable morphisms and regular languages. So, I could use the finite state transducer(this is guaranteed by Nivat's theorem).

Is there any good textbooks for this(closure properties of general class of languages)? I read Hopcroft; Ullman, "Formal Languages and Their relation to Automata", especially Chapter 9. I think this is a good reference to study but I felt this is not enough to understand the theory fully.

And there is another question which is not really related to the original questions, so you don't need to answer it.

Several references study about only trio, full-trio, semi-AFL, AFL or some examples. Why most of the references only deal with these FLs(Family of languages)?


texts: Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT

texts:
Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a formula $\varphi$ with at most $O(n)$ clauses within time at most $p(n)$ for some polynomial $p(n)$?

Since Cook Levin Theorem shows a reduction that proves 3SAT is NPC, almost all of the literature deals only with reductions from 3SAT, and only rarely one can find in the literature reductions to 3SAT.

After searching the web I found this and other cites that have the other direction of reduction (from 3SAT to dHamPath).

Referring to some source would be highly appreciated.


texts: Unclear logic notation for PFX program rules

texts:
I'm very new to this so please bear with me.

I found this document describing the PFX language, a stack-oriented language where the instructions act on a stack and replace the arguments with the result.

The image is supposed to be the rules describing the logic of a PFX program, but being very new to logical symbols, I can barely read it.

From what I understand, the top parts are suppositions and the bottom parts are conclusions. The first one, to me, reads, if i is different from n, then if either of the vk's implies i, the program declares an error. But I can tell my understanding is deeply flawed. I searched and have found close to no similar rules.

Also, the use of the letter "i" seems unclear to me mostly.

If someone can explain with words what the rules actually mean, it would help me a lot.

Thank you.


texts: Is Dijkstra's algorithm just BFS with a priority queue?

texts: According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.


texts: Average number of full nodes in rooted m-ary tree

texts:
I am looking for a formula to express the average number of full nodes (i.e. nodes having exactly $m$ children) in a $m$-ary tree having $n$ nodes, i.e.,
$$ \mu_{n}^{(m)} = \frac{\# \text{full nodes in all $m$-ary trees having $n$ nodes} }{\# \text{nodes in all $m$-ary trees having $n$ nodes}}$$.

As to the denominator, according to this answer, it sholud be given by
$$n C_m^n = \binom{mn}{n} \frac{n}{(m-1)n + 1}$$
As to numerator, at the first glance, I tought that this answer would have provided a hint; but then I have realized that it is not the case because it gives how many trees have $n$ full nodes, but I need to know how many full nodes are in the set of all the $m$-ary trees having $n$ nodes.

Could someone help me to understand how to solve it and provide (if any) a usable formula for $\mu_{n}^{(m)}$?


texts: Does $P \neq NP$ imply $NP \neq PSPACE$?

texts:
Is it true that
$\mathsf{P} \neq \mathsf{NP}$ implies $\mathsf{NP} \neq \mathsf{PSPACE}$?

I have here some problem that is in $\mathsf{PSPACE} \setminus \mathsf{NP}$ if $\mathsf{P} \neq \mathsf{NP}$. Since I cannot find a fault in my proof, I wanted to be sure, if the upper implication holds or not.


texts: How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable?

texts:
So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.)
Question 1 :
Show the following language is decidable

$L=\{\langle G,w \rangle $ : $G$ is a grammar in normal form of Chomsky and $w$ is a word on the terminal alphabet that can be derived in $G$ by at least 2 differents derivations trees. $\}$

In other words, find an algorithm that when given a grammar that is in normal form of Chomsky and a word $w$, it concludes after a finite number of steps if yes or no $w$ can be derived by two derivations trees.
Here's my attempt (correct me if this is wrong) :
Entry : $\langle G,w \rangle $

Try every derivations in $G$ of length $2|w| -1$.
If two derivations generate $w$ stop and accept $\langle G,w \rangle $. Else stop and reject $\langle G,w \rangle $.

Question 2 :
Show that this language is Turing recognizable $K = \{\langle G \rangle : G$ is a grammar in normal form of Chomsky and $G$ is ambiguous ( can have two derivation tree for same word).$\}$ In other words, give an algorithm that when given an grammar in normal form of Chomsky, it returns "true" if $G$ is ambiguous and return "false" or doesn't stop when $G$ is not ambiguous. ( Give an answer based on the algorithm used in question 1)
My reflexion on question 2 :
For this part i am kinda lost, i know that we will use algorithm of question 1 to be able to return true but for the infinite loop part i am not sure on how to say this.
I am also not sure if i can use a word "$w$" since our entry is a grammar $G$.
Entry : $\langle G \rangle$

Apply algorithm from question 1 if it returns true,  return true. ( Because question 1 basically confirm that the CNF is ambiguous).

note sure how to handle the rest for it to loop.


texts:
Is it good to define a language $\mathcal{L}$ in NP as a language for which, given an element $x$, it is possible in polynomial-time to check whether $x \in \mathcal{L}$ or not?
Because I need to have an informal definition of that, in order to give just an idea of it, without using formalism.
Otherwise how could I define it roughly speaking?


texts: Get mathematical relation of node IDs of a subtree based on a given tree

texts:
(I was not really sure in which "stackexchange" I should put this question. I hope CS is ok.)

Let's say I have the following tree A. Every node has a unique ID, which will be counted up, beginning from 0. The ID counting is taking place in breadth-first order.

Now I want to pick out a part of the graph A. The information of the subtree is given by a node ID in the original tree A.

Example

Let's say the new tree starts with the node ID 3 of the original tree. For this example, the tree depth has an offset of 1 (because 3 is in depth 1 of the original node). The result is the following

You might have noticed that the new tree have the same structure than the old tree. The unique ID of each node in the new tree, will also be counted up in breadth-first order. In the brackets, you can see the link to the original node tree A.

Background

The reason, why I need this node link is the fact that I need to copy some node properties from the original tree node to the new tree node.

Question

What is the mathematical relation between the unique node IDs of the new tree and the node IDs of the original tree? I want to compute the ID's of the old tree, based on the ID's of the new tree.

Thanks for any help.


texts:
This is specifically a question pertaining to solving reccurences via the Master Theorem/Method, particularly for a specified $f(n)$ (as denoted below).

For a recurrence of $$T(n) = a T(\frac{n}{b}) + f(n)$$

where f(n) is $\Theta{(n)}$, would we be comparing $n^{\log_b(a)}$ with $n^{1}$ - meaning we would be comparing $log_b(a)$ with 1? Since the rate of growth is linear?

what about where f(n) is $\Theta{(1)}$ (aka some constant?), would we be comparing $n^{\log_b(a)}$ with $n^{0}$? '0' since there is no rate of growth for a constant?


texts: Pattern matching on function application

texts:
Suppose we have a function f :: a -> b and a function g :: b -> a such that f . g = id. You might say that g is the "inverse" of f (and vice versa). Could we then pattern match on something like f x on the left hand side by replacing occurences of x with g x on the right hand side? For example:

-- Here, (- 3) is the "inverse" of (+ 3), or more generally, (- n) is the "inverse" of (+ n)

subtractThree (x + 3) = x
subtractThree x = (x - 3)

This just randomly came to my mind and I'm wondering if there is something fundamentally wrong with this.

Edit: This is my first post here and I'm unsure whether this is the right kind of question for this community. Please don't hesitate to close this if this doesn't belong here.


texts: Are there any natural $\Pi_2^P$-complete problems?

texts:
I know that the quantified Boolean formula problem for a formula
$$
\psi = \forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_n \phi
$$
where $\phi$ contains no quantifiers and only the variables $x_1, \ldots, x_n, y_1, \ldots, y_n$ is an example of a $\Pi_2^P$-complete problem. However, I wonder whether there are any natural problems known to be $\Pi_2^P$-complete, just as Circuit Minimization is a natural $\Sigma_2^P$-complete problem (see Polynomial hierarchy for details)?


texts: Connection between non determinism and LL(1) conflicts

texts:
I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it.

As per my understanding non deterministic context free grammar is a context free grammar in which at some point in time during parsing, multiple actions are allowed. Also I believe non determinism occurs when we have multiple productions in grammar with same prefix of production (right hand side) bodies. Also I know we eliminate non determinism by left factoring grammar.

Wikipedia article says:

We do left factoring to eliminate FIRST-FIRST conflicts. ref
Left recursion is a special case of FIRST-FIRST conflict. ref
Substitution is used for removing FIRST-FOLLOW conflict. However that may introduce FIRST-FIRST conflict.ref
Left recursion is eliminated using rule like below ref :
$A\rightarrow A\alpha | \beta $
ios converted to
$A\rightarrow \beta A'$
$A'\rightarrow \alpha A' | \epsilon$

I have following doubts:

Since both non determinism and FIRST-FIRST conflicts are removed with left factoring and since left recursion is special case of FIRST-FIRST conflict, is non determinism a reason behind FIRST-FIRST conflict and left recursion (and also for FIRST-FOLLOW conflict)? If yes, does non determinism cause anything else and there is nothing else apart from these three (FIRST-FIRST conflict, left recursion and FIRST-FOLLOW conflict) in which non determinism manifests?
Does the solutions (left factoring, substitution and left recursion removal rule) for removing above can also remove non determinism from all grammars?
I know LL grammar should be both non deterministic and unambiguous. Does ambiguity also manifests in some way in LL parsing table or grammar? I read ambiguity can be eliminated by enforcing association and precedence between grammar symbols and this resolves SHIFT-REDUCE conflicts in LR parsers. Is anything like this required for eliminating ambiguity to make grammar a valid LL grammar?


texts: When using a hash and a collision occurs and linear probing is used how is that item found again

texts:
How is the search for the item supposed to find the specific item if the data is all clumped together and all the search is given is the output of the hash function. I don't understand how it knows which of the pieces of data is the one that corresponds to the key if linear probing has been used so it could be any of a number of pieces of data?
Thanks for any help


texts: How many times whille loop will be executed when we double the value?

texts:
Consider this loop:
for i = 1 to n
 j = i
 while j < n
  j = j + j
 end while
end for

How many times the while loop will execute? I was thinking that if we denote by $c$ number of time loop will execute then in each iteration $j$ would be equal to $2^{c-1}i < n$, then taking logarithm we get $c<log_2{n} - log_2{i} + 1$ though I'm not sure this is helpful. I want to use this in sum so I'd like it to be natural.


texts: Best problems that are prone to parallelization?

texts: What are some problems that are prone to parallelization? When I think about this, the first thing that comes to my mind is matrix multiplication, which yields to faster calculations, meaning you can get speed ups easily. Any other examples like this?


texts: An algorithm to maximize the number of parallel tasks

texts:
I have a set of compute tasks I want to schedule, these tasks have dependencies and a task may not be executed until all its dependencies are executed.

The problem can be represented as a directed acyclic graph:

The current scheduler ensures correctness, and capable of culling unneeded tasks such as k in the previous graph (assuming the end goal is i).

I am struggling to find another equivalent algorithm to maximize number of tasks running in parallel (tasks on the same line may be executed in any order):

a, b, j
c
d
e, f, h, g
i

Flatten form, what is between () may be in any order and represent parallel tasks:

  (a, b, j), (c), (d), (e, f, h, g), (i)

The idea here I want to fill the compute engine with as much work as possible.


texts: What is complement of Context-free languages?

texts:
I need to know what class of CFL is closed under i.e. what set is complement of CFL.
I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I can say that complement of CFL is included in P(right?). There is still a question whether complement of CFL is proper subset of P or the whole P. I would appreciate any ideas on how to show that complement of CFL is the whole P(if that's the case of course).


texts: Max flow algorithm for floating-point weights and E~=10*V

texts: Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e.   O(V^3) algorithms take too much time, but O(E^2) algorithms are much more preferable. More specifically, you can assume V~=1M and E~=10M where M stands for millions.


texts:
I am learning about embedded and operating systems. I would like to know the order of control flow that occurs when a user-space C application calls a function, for example, printf().
I am slightly confused as to which order is correct:
printf() -> User-space library -> system call -> kernel driver
printf() -> User-space library -> kernel driver -> system call
printf() -> System call -> user-space library -> kernel driver
printf() -> Kernel driver -> system call -> user-space library


texts: Prove that we can convert any given turing machine to a turing machine with only 3 states?

texts:
So in a book that I'm reading it says that we can convert any given Turing machine to a standard turing machine with only 6 states

furthermore we can convert any given to a turing machine with only 3 states given we have no limitation on which version of turing machine we use(multi tape, non deterministic, etc so its not a standard turing machine anymore) and obviously both the original turing machine and the converted one have the same functionality(accept the same language)

i asked this here before but no one was able to give   a proof of this, and i do not understand it either

so what's this statement based on? i tried searching the web but there was literally 0 article about this.

I think this is done the same way we can reduce any PDA to a PDA with only 3 states, but i dont know the prove of that one either, i just know its true


texts: Proving the correctness of a square summing algorithm

texts:
int sumHelper(int n, int a) {
   if (n==0) return a;
   else return sumHelper(n-1, a + n*n);
}

int sumSqr(int n) {
    return sumHelper(n, 0);
}

I am supposed to prove this piece of code which uses tail recursion to sum up the squares of numbers. That is, I need to prove that for $n ≥ 1$, $sumsqr(n)=1^2+2^2+\dots+n^2$. I have figured out the base case but I am stuck at the induction step. Any hints or help will be appreciated.


texts:
I'm trying to derive an algorithm or procedure I would use to have a human interactively rank a series of items based on importance by comparing a random-pairing of items at a time.

So, given an array of let's say 10 "things", I want to present two of the things, and have the user specify which is the more important of the two.  What I don't know is:

What is the proper name for this procedure/concept?
Would I use some form of sorting algorithm?
How could I determine when to stop?  When is the ranking "done"?
And, importantly, I would prefer not to present the same "thing" to the user in a row.  That is, if comparing Item B and Item K, user selects Item K as more important, the next iteration should not present either Item B or Item K.

What I'm after seems similar to this question: Nearest neighbour based on subjective human comparison - is this a thing?

... but I'm not interested in similarity, just relative importance.  Think prioritizing a to-do list or subjectively ranking vacation destinations, etc.

The Elo Rating System may be similar to what I'm after, as well.


texts: Base class with different logic for sub classes

texts:
Currently I have two different (A,B) classes which basically share common logic but also one of them (let’s say class A) have special additional logic. Class A pretty much contains B’s logic. I want to unite them into one base class.I thought about doing one base class which will contain all the logic, and have two sub classes which will define a flag whether or not should we execute the special logic I mentioned and then I can check this in the base class.
I guess I can also have a base class containing B’s logic (the more specific one) and then extend it to another sub class which will implement the special logic. Wanted to hear pros and cons or any other ideas that might come up. Thanks !


texts: Non-trivial bin-packing instance with 5 objects

texts:
Bin packing problem is a problem, where one has to find the minimum number of bins of size $v$ required to store $n$ objects of sizes $s_1, \ldots, s_n$. Object sizes are never greater than $v$.

For example, if $v = 10$ and the objects sizes are $2, 5, 4, 7, 1, 3, 8$, we can store objects with 3 bins: [8, 2], [7, 3], [5, 4, 1], but not with 2 bins or less, as this would leave some items unpacked. Therefore 3 is the minimum number of bins required.

The best-fit-decreasing heuristic is a packing strategy, which aims to produce a packing close to optimal. It first sorts all the items in descending order. Then it iterates over all items, and for each item attempts to find an existing bin, which can both fit the item and whose spare capacity is closest to the size of the item. If such bin exists, it puts the object in the bin. If it doesn't, it creates a new bin and puts it there.

A non-trivial bin-packing instance is an instance of the problem, which can't be optimally solved by the best-fit-decreasing heuristic.

For example, the instance $v = 7$, $n=6$ where sizes are $3, 2, 3, 2, 2, 2$ is non-trivial, because the best-fit decreasing heuristic will:

Sort the items to give $3, 3, 2, 2, 2, 2$
Put the first two items in the first bin, producing a bin $[3, 3]$
Put the next three items in the second bin, producing a bin $[2, 2, 2]$
Put the last item in the third bin, producing a packing $[3, 3], [2, 2, 2], [2]$

This is a valid packing, but non-optimal, as it requires 3 bins, and there exists a valid packing with two bins: $[3, 2, 2], [3, 2, 2]$.

Is there a non-trivial bin-packing instance with $n=5$?


texts: Determine time given algorithmic complexity as input grows?

texts:
Consider the time required to solve a problem, represented by f(n), and for sufficiently large inputs of size k, the time required to solve a problem is t. What is the typical method of determining how long, in terms of t, is necessary to solve a problem, for different kinds of f(n) and k?

For example, when f(n) is Θ(n), and the input is 2k, we know that the time is approximately 2t. But what is the standard method of determining the time, in terms of t, for problems like this? For example:

When f(n) is Θ(n3) and the input is k2 ?
f(n) is Θ(2n) and the input size is k+3 ?
f(n) is Θ(lg n) and the input size is 4k ?
f(n) is Θ(n!) and the input size is k+2 ?

This question is not asking for answers to those scenarios per se, rather, how to go about expressing the time, in terms of t, given the parameters above.


texts:
Imagine that we have a base class number that has implemented a integer and floats, but not complex numbers and that we would like to extend it to also support complex numbers:

;; this is from the number implementation
(defgeneric add ((a number) (b number))
  (:documentation "Adds two numbers together."))

(defmethod number:add ((a my-complex-number) (b my-complex-number))
  ...)

(defmethod number:add ((a my-complex-number) (b number))
  ...)

(defmethod number:add ((b number) (a my-complex-number))
  ...)

The body of the two last would be exatly the same and yet they are needed in order to do (reduce #'add list-of-numbers) since the number implementation doesn't know how to add complex numbers.

It seems to me like some sort of syntax to indicate the (or some) arguments can occur in any order. In CL I'm sure this can be fixed by making a macro that generates all the versions, but this isn't just a CL problem.

Imagine you have a number tower with an add method in Java and you extend it with a MyComplexNumber class with the same add method. How does noe make sure floatObject.add(complexObject) would work?

ComplexNumber know of the Number class hiarchy but not vice versa. Thus by importing ComplexNumber package it would be nice to "infect" the other classes add methods without changing their code.

Is there a language out there that has abstraction to solve this?


texts: Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$

texts: I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, what word should I choose? Or should I use closure-properties and if so what irregularity should I show? I am genuinely so confused. Any help is appreciated.


texts: Finding maximal and average number of time slots in an Adaptive tree walk protocol

texts:
Tried to research here and on other sites with no luck regarding finding the maximal and average number of time slots in an Adaptive tree walk protocol. i'll explain what i mean here:

In a simple(provided an image for illustration at the end of the post) Adaptive tree walk protocol, Divided by time slots where a station can only transmit at the beginning of each time slot.

If for instance stations C and A want to broadcast  in time t=0 with probability p(for simplicity) (None of the other stations want to transmit at all), Is it possible to know the maximal or average number of time slots that will pass until(including) the slot in which there will be a successful broadcast?

Simple network diagram i am asking about:

Note: for simplicity, in this question, no other station except C and A want to broadcast at all


texts: Efficiently selecting a random subset of size $m$ from a set of size $n$

texts:
This is a cross post of my question here on math.se.
I have a list of $n$ items and would like to randomly select an $m$ set from it efficiently (in terms of time complexity). Also, I want all possible subsets to be selected with equal probability. The obvious solution is to pick a random integer from $1$ to $n$ and choose the corresponding element, then repeat $m$ times, not counting the event in which one chooses and already chosen element. This becomes increasingly inefficient as $m$ approaches $n$ so for $m>n/2$ it would make sense to instead to pick a $(n-m)$-set and return its compliment.
For values of $m$ close to $n/2$, a better solution I think would be to consider each of the $n$ elements and decide either to pick that element or discard it, each time updating the probability of picking or discarding depending on the number of elements chosen vs discarded prior. Specifically, the algorithm would go as follows (python):
def randomSubset(n,m):
  L = []
  for i in range(n):
    if uniform(0,1)<m/(n-i): L,m = L+[i],m-1
  return L

However I am concerned that this may not result in each subset being chosen with equal probability.
I have two questions. First, does this algorithm pick subsets with equal probability (if so, I'd like a proof that it does and if not I'd also like a proof that it doesn't). Second, more broadly I would like to know what good solutions exist to this problem. Clearly if $m<<n$ then the first method is better than the second however at some point the second method (if it does in fact work) is better than the first. Moreover, an entirely different approach may be best in general.


texts: Minimum spanning subgraph of even degree

texts:
I have an unusual problem that I am struggling to solve. I have a set of nodes (with positive distances between them) that I want to connect into a single component. In particular, I want to form a minimum-distance spanning subgraph such that all its nodes have an even degree. Note that the subgraph can have multiple edges between a pair of nodes (multigraph). Below are some examples:

A) We have 8 nodes arranged in a circle, where adjacent nodes are separated by distance 1. We connect them into a single cycle of length 8.

B) The top figure shows all the possible distances. If we use the three single edges then we will have a subgraph of weight 1+1+3=5. But we can do better if we use double edges, giving us a total weight of 1+1+1+1=4 (bottom figure). Note that the center node has degree 4, but this is ok since it is still even.

C) Here all adjacent nodes are separated by distance 1. If we use double edges in the shape of the Sum sign (Sigma) then we will get a subgraph of weight 8. But we can do better by using single edges, giving us a total weight of 6.

D) Here the best way to include the top-right node is to use double edges.

I have come up with an outline for an algorithm for solving this problem, but it is not quite complete. First we compute the minimum spanning tree. This will give us some of the edges of the subgraph. It will also give us some nodes (leaves of the tree) with degree 1. We now greedily connect these nodes to their closest neighbours. This is the bit that I haven't quite worked out. Because if we always pick the closest neighbour then we will get the same edges as the MST. Clearly this will fail in A. So perhaps we want to prioritise connections to other degree-1 nodes. Also at the end of this step, we may still have some nodes with an odd-degree remaining which also need to be connected.

Any help would be greatly appreciated!


texts: Prove this Context-Free Grammar is Ambiguous

texts:
so I have a problem on one of my computational structures final reviews, and I cannot seem to figure it out. It's been driving me crazy, so I would like to post it here for some insight.

Prove that the following CFG is ambiguous.

S-> begin A end

A-> A;A / a / S

Terminals: begin, end, ;, a.
Variables: S, A.

I cannot seem to find a string w such that w can be derived in more than one way through this CFG. Any ideas as to how I might tackle this?


texts: probability that the vertex set {1,...,k} is component of random graph

texts:
Consider a graph with vertices 1,...,n and suppose that each of the $\binom{n}{2}$pairs of vertices is, independently, an edge of this graph with probability p.Let $P_n$ denote the probability that this graph is connected.

(a)I want to derive an expression that involves $P_k$ for the probability that the vertex set {1,...,k} is a component of this graph.

(b) I want to derive the probability that vertex 1 is a member of a component of size k.

(c)I want to express $P_n$ in terms of $P_k$, k=1,...,n-1.

(d)Using the recursion of part (c) to find $P_6$

Answer

I know the probability that random graph is connected $\sim$ $\sqrt{\frac{\pi}{2n}}$ for large n

I also know the expected value of the number of components in the random graph

$E[C]=\displaystyle\sum_{k=1}^n \binom{n}{k}\frac{(k-1)!}{n^k}$

How to use this corollary and equation of the number of components in the random graph to answer this question?
Your hints are needed.


texts:
It's said that in Zermelo–Fraenkel set theory (ZFC) one can develop all of mathematics. How about computer science?

Is it possible to define algorithms as a first step? More specifically, how to define "if x = 1 then y else z"? How about loops?


texts: Generation regular languages by context free grammar

texts:
I came across problem asking whether given statement is true and false. The statement given was as follows:

  Every Type-2 grammar can generate regular language.

I felt that Type-2 grammar means, its context free grammar and is generated by PDA. PDA is more powerful than FA which generate regular languages. Hence any Type-2 grammar should be able to generate regular language. But the answer given was FALSE saying that there are Type-2 grammars which generate "pure CFL" (non regular languages).

So I was guessing whats going on here. I have following doubts:

Is the question asking whether all CFLs are also regular? (which is not the case and thats why the given answer states "pure CFL")?
Is the question asking whether every CFG generate "all" regular languages? (which is obviously senseless and hence is FALSE?)
Is the answer FALSE because deterministic context free automata accepting on empty stack cannot even accept regular languages?


texts: Can we remove duplicates faster than we can sort?

texts:
The problem is (integer) duplicate removal, which can also be perceived as producing the image of an evaluated function (of integers):

  Given a sequence $S_\text{in}$ of $n$ integers, produce a sequence $S_\text{out}$ of elements such that any element in $S_\text{in}$ also appears in $S_\text{out}$, and all elements in $S_\text{out}$ are distinct.

Ignoring some details regarding the elements' size in bits, this can be done by sorting in $O(n \log n)$ time; or by hashing in expected time $O(n)$.

Given that we don't require $S_\text{out}$ to be sorted - is it possible to do better than sorting in the worst case?

Notes:

Some dependence on the output size (let's call it $m$) rather than $n$ is an improvement, but I'm mostly interested in getting closer to linearity in $n$.
The details I've ignored may not be so insignificant.
Algorithms need not be restricted to algebraic computation, i.e. you can tear into the bit representation if it helps.
We cannot make any assumptions regarding the input distribution.


texts: How do I prove that Context Free languages have more memory than FSM

texts: This is very much clear to me that an FSM has limited memory (sufficient to store present state). How do I prove that (intutively or otherwise) that a CFL has more memory than a DFA or NFA (thus making a CFL more powerful than FA) ?


texts: Finite state transducer that multiplies numbers

texts: How is possible to construct a finite state transducer that multiplies a number by 5? We can assume that numbers are supplied in binary notation, from least significant bits to most significant.


texts: Is it possible to use "and", "or" "not" as relation/predicate in an ontology? In order to represent causality?

texts:
If we use an ontology we can represent knowledge, using notably semantic triple <s,p,o>.

I was wondering how can I represent this:

A and B cause C

or

A or B cause C

?

I don't want to do reasoning, I only want to represent.

Is it possible to use and, or, negation as predicate/relation in an ontology?

I only see that researchers use causal networks to represent causality, but I was wondering why it is not possible in an ontology.

Thanks in advance,


texts: Understand the time complexity for this LCS (longest common subsequence) solution

texts:
I would appreciate an intuitive way to find the time complexity of dynamic programming problems. Can anyone explain me “#subproblems * time/subproblem”? I am not able to grok it.

Code for LCS -

public static String findLCS(String str1, String str2 ) {
    // If either string is empty, return the empty string
    if(null == str1 || null == str2)
        return "";
    if("".equals(str1) || "".equals(str2)) {
        return "";
    }
    // are the last characters identical?
    if(str1.charAt(str1.length()-1) == str2.charAt(str2.length()-1)) {
        // yes, so strip off the last character and recurse
        return findLCS(str1.substring(0, str1.length() -1), str2.substring(0, str2.length()-1)) + str1.substring(str1.length()-1, str1.length());
    } else {
       // no, so recurse independently on (str1_without_last_character, str2)
       // and (str1, str2_without_last_character)
       String opt1 = findLCS(str1.substring(0, str1.length() -1), str2);
       String opt2 = findLCS(str1, str2.substring(0, str2.length()-1));
       // return the longest LCS found
       if(opt1.length() >= opt2.length())
           return opt1;
       else
           return opt2;
    }
}

I am just providing the actual code instead of pseudo code (i hope pseudo code or the algo is pretty self explanatory from above)


texts:
What would be the name of the problem of a vertex cover that covers all the vertices without the requirement of covering all the edges?

Vertex cover has to answer whether or not there is a set of $k$ vertices that covers all the edges of the graph, covering therefore, all the vertices. What is the name of the problem that, similarly to vertex cover, select a subset of $k$ vertices that has direct edges to all the vertices, but without necessarily covering all the edges of the graph?


texts: Longest common subsequence solution reconstruction during DP is wrong

texts:
I've implemented longest common substring in python. I know the usual way to reconstruct the path. But, I am reading my algorithm many times, I don't understand why it doesn't work for some test-cases. I am trying to construct the solution while the longest path is being made through dynamic programming.
def lcs(s1, s2):
    n = len(s1)
    m = len(s2)

    trow = [0] * (m+1)
    table = [trow] * (n+1)

    srow = [""] * (m+1)
    solution = [srow] * (n+1)

    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                table[i][j] = table[i-1][j-1] + 1

                # Adding this character to the solution
                solution[i][j] = solution[i-1][j-1] + s1[i-1]

            elif table[i][j-1] > table[i-1][j]:
                table[i][j] = table[i][j-1]

                # Choosing the solution related to the longer path
                solution[i][j] = solution[i][j-1]

            else:
                table[i][j] = table[i-1][j]

                # Choosing the solution related to the longer path
                solution[i][j] = solution[i-1][j]

    return solution[n-1][m-1]

lcs('amin', 'kahmjiknln')
# Returns 'amin'

lcs('amin', 'aaaakahmjiknln')
# Returns 'aaaaamin'


texts: Decision problem that can be verified but not run in n^2 time

texts: A much much weaker idea similar to the P=NP question, is there a decision problem that can be verified in $O(n^2)$ time, but it can be proven that there is no algorithm that decides it $O(n^2)$ time?


texts: Finding minimum spanning tree with O(|V|)

texts:
Given an undirected weighted graph $G(V,E)$, where the number of edges is $|V|+10$, how can I find the minimum spanning tree of $G$ in $O(|V|)$?

Kruskal's algorithm is out of the question, since sorting alone is $O(|V|\log |V|)$, so I thought maybe using Prim's algorithm with minimum binary heap, but still - every iteration will cost $\log |V|$ for updating vertices keys in the heap, so altogether it's $|V|\log |V|$.
I know that the key here is to use the fact that $|E|=|V|+10$, so I start thinking maybe removing the 11 edges with the biggest weights, as long as the graph stays connected, but that's obviously a bad idea since it'll - again - require sorting.
I just can't figure it out. Any help would be greatly appreciated.


texts: Multiple choice knapsack dynamic programming

texts:
Giving a the following:

A list of a store items $T=\{t_1, t_2,...,t_n\}$.

A list of prices of each item $P=\{p_1, p_2,...,p_n\}$.

A list of quantities of each item $Q=\{q_1, q_2,...,q_n\}$respectively.

And total bill $M$.

Our goal is to find any possible list of items that its total value is equal to $M$ using dynamic programming.

My question does 0/1 weighted Knapsack problem help, where $M$ can be the capacity of the knapsack, and the weight of each item equal to the quantity of the item. If there is any other better approach  I would appreciate any references.


texts: Best known (state of science) time complexity of an array access problem

texts:
Consider an Array $A$ with $n$ values and the following operations:

get(i): Returns the value of $A[i]$
insert (x): Insert the element x into the any free place in A (not necessarily in $A[x]$ or the end of the array)
delete (x) delete the element $A[x]$

What is the best known (amortized) time complexity of all operations? Especially the delete-op seems like it needs at least $\Omega(log n)$

See also the papers in this post. However the insert operation is defined slightly different by me, does this have any effect?


texts: Is there a way to test "Turing completeness"?

texts:
I asked my algorithms teacher today the very same question that is stated in the title, but he seemed a bit unsure, either on the question or on the concept, so I thought I'd try here too.

Is there a minimal test that could determine whether a language or instruction set is Turing compete, or does a test of that sort fall into the domain of undecidability?

It might seem like a trivial or stupid question, but the reason I ask is that it would be a good way to test whether the instructions of a cellular automaton is Turing complete, and if there is such a test, maybe it could help when generating cellular automata.

I'm quite new to both cellular automata and undecidability problems, so go easy on me.


texts: How do I draw a DFA diagram when I only care about how the string ends?

texts:
Hi so this is my first week learning about automata and I have an exercise I'm going through. I'm supposed to draw a diagram for the DFA that accepts all strings of a and b where the third last symbol is a b.
So it's like : $\{a,b\}^*b\{a,b\}^2$ right?

And if I would draw it I would do this to check the end:

I believe this to be correct but I'm not sure how to draw the possibilites of a's and b's beforehand


texts: Determining how similar a given string is to a collection of strings

texts:
I'm not sure if this question belongs here and I apologize if not.  What I am looking to do is to develop a programmatic way in which I can probabilistically determine whether a given string "belongs" in a bag of strings.  For example, if I have bag of 10,000 US city names, and then I have the string "Philadelphia", I would like some quantitative measure of how likely 'Philadelphia' is a US city name based on the US city names I already know.  While I know I won't be able to separate real city names from fake city names in this context, I would at least expect to have strings such as "123.75" and "The quick red fox jumped over the lazy brown dogs" excluded given some threshold.

To get started, I've looked at Levenshtein Distance and poked around a bit on how that's been applied to problems at least somewhat similar to the one I'm trying to solve.  One interesting application I found was plagiarism detection, with one paper describing how Levenshtein distance was used with a modified Smith-Waterman algorithm to score papers based on how likely they were a plagarized version of a given base paper.  My question is if anyone could point me in the right direction with other established algorithms or methodologies that might help me.  I get the feeling that this may be a problem someone in the past has tried to solve but so far my Google-fu has failed me.


texts: Clarifications on primitive recursive function definition

texts:
I am studying primitive recursive functions and there's something that I don't quite understand: let's take the function that computes $x+y$, then, in order to show that $f(x,y)=x+y$ is primitive recursive, my lecture notes give the following equations:

\begin{cases}
   f(x,0)=x \\
   f(x,y+1) = f(x,y)+1
  \end{cases}
this first bunch makes perfect sense to me, on the other hand, looking at the equations down below, I don't get why a new function $g$ is used and also why does it have three parameters, when the sum clearly has only two? Is that $y$ the variable that supposedly holds (partial) results from computation?

\begin{cases}
   f(x,0)=u^1_1(x) \\
   f(x,y+1) = g(y, f(x,y),x)
  \end{cases}

where $g(x_1, x_2, x_3) = s(u^3_2(x_1, x_2, x_3))$.


texts:
I am a bit confused by the notation here, http://www.boazbarak.org/sos/files/lec3.pdf

Given 3 Boolean variables $x_i, x_j, x_k$ what is supposed to be the meaning of $x_i \oplus x_j \oplus x_k$?

Is this to be understood as say $((x_i \oplus x_j )\oplus x_k )$? And hence this is true for only $2$ cases $x_i =0, x_j = 1, x_k =0$ and $x_i = 1, x_j = 0, x_k = 0$ ?

But then we could have bracketed it as $(x_i \oplus (x_j \oplus x_k))$ and then the only true assignments would have looked as $x_i = 0, x_j =1, x_k = 0$ and $x_i = 0, x_j =0, x_k = 1$ and these are different.

Also one could have used commutativity to write it in other re-arranged forms and gotten different true selections!
But then the note above seems to claim that if the $x_a$s are coming as coordinates of a vector $x \in \{\pm 1\}^n$ then the product $x_ix_j x_k$ is the same as having a linear equation in those $3$ variables. Why so? (for example an assignment $x_i = x_j = x_k =1$ will evaluate to $1$ for the product but under mod 2 arithmetic $x_i + x_j + x_k = 0$ for this assignment!)

Also it is being claimed that the value of $x_ix_jx_k$ can only be $\pm 1$ (which they denote as $a_{ijk}$) for $x \in \{\pm 1\}^n$ and that is okay only if one ignores the first claim that these are supposed to be linear equations!

This $x_ix_j x_k$ product notation looks more confusing later on when they say that corresponding to two subsets $S, T \subset \{1,..,n\}$ one can take two expressions of the form $x_S = \prod_{i \in S} x_i$ and $x_T = \prod_{i \in T} x_i$ and construct $x_U = x_S x_T$ and that this somehow corresponds to doing ``$U = S \oplus T$" - and I don't know what it means to take a XOR of two subsets!


texts: Return the subset with smallest cardinality of an array whose elements sum to at least a given value

texts:
Suppose we are given an array $A[1\ldots n]$ and a value $C$.

Is there an algorithm with linear expected runtime that can produce an array that is the subset  with smallest cardinality of $A[1\ldots n]$ whose elements sum to at least $C$?


texts:
I looked at my notes from a class about fast forier transform , and the professor proved in class theorem thanks to Morgenstern , first he defined linear algorithm as a algorithm that inly uses multiplications by scalar and addtions, that he stated Morgenstern's theorem the following way

  Every linear algorithm that computes DFT (Discrete Fourier Transform) , in which the scalar are bounded in their absolute value by $C$ , takes at least $\Omega_C(n\log{n})$ addition operations.

I haven't understood his proof , if someone can give me guidlines to the proof I'll be more than happy :) [right now my proof of the theorem looks like a mess]

p.s.: In class he said we will write in each step the coeffiecents of the linear function that was just computed , then he defined a "computation advancment function" , I didn't understand his definition of this function , it was definied something like $\phi(k)=$ maximum determinant of n$\times$n matrices that were computed untill the k'th step [I probably copied wrong]


texts: Generating all the increasing subsequences

texts:
Given an array of integers, how can we generate all the increasing subsequnces  of length of 4  ?
Example: given this list
l = [1, 2, 4, 5, 3, 6]

The answer should be :
[1, 2, 3, 6]
[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 5, 6]
[1, 4, 5, 6]
[2, 4, 5, 6]

I generated this algorithm using python :
def verif(x,temp):
    work=[]
    for k in temp:
        if len(k)<4 :
            if k[-1] < x :
                work.append(k+[x])
    return work+[[x]]

temp=[[1]]
for i in range(1,len(l)):
    print(i)
    zeta=verif(l[i],temp)
    for i in zeta:
        if len(i)==4 :
            print(i)
    temp+=zeta
    zeta=[]

I want to improve my approach , which is very slow for bigger lists unfortunately , is there another algortihm which works faster ?


texts: Drawbacks of adding type equality to 1ML

texts:
In the 1ML – Core and Modules United (F-ing First-Class Modules) paper, the author gives the following example for why module types do not form a lattice under subtyping:

 f1 : {type t a; x : t int} → int
 f2 : {type t a; x : int} → int
 g = if condition then f1 else f2

  There are at least two possible types for g:

 g : {type t a = int; x : int} → int
 g : {type t a = a; x : int} → int

  Neither is more specific than the other, so no least upper bound
  exists. Consequently, annotations are necessary to regain principal
  types for constructs like conditionals, in order to restore any hope
  for compositional type checking, let alone inference.

At first glance, it seems like the problem can be remedied by adding in type equalities:

g : (t int ~ int) ⇒ {type t a; x : int} → int

However, this "solution" isn't discussed in the paper. So it feels like I'm overlooking some obvious drawback of this idea, apart from the one that it might not be possible to encode type equality in System Fω (which is the raison d'être for the paper). Does adding type equalities make type checking/inference even more problematic in other situations?


texts: Algorithms for operating on tape storage

texts: Old algorithm textbooks often covered algorithms that did well on tape drives, since tape drives used to be a common storage type on almost all computers. Since memory on modern CPUs with data prefetching is starting to more and more resemble a tape drive, I was wondering if there used to be some "canonical" books/papers back in the day on algorithms operating on tape storage? I'd be very interested in checking out what was ideas were available back then.


texts: Why Does the Fixed Point Theorem Apply to Quines?

texts:
A quine is a program that outputs its own source code without taking in any input. An example would be this (taken from here)

public class Quine {
    public static void main(String[] args) {
        char quote = 34;
        String[] code = {
"public class Quine {",
"    public static void main(String[] args) {",
"        char quote = 34;",
"        String[] code = {",
"        };",
"        for(int i=0; i<4; i++){",
"            System.out.println(code[i]);",
"        }",
"        for(int i=0; i<code.length; i++){",
"            System.out.println(quote + code[i] + quote + ',');",
"        }",
"        for(int i=4; i<code.length; i++){",
"            System.out.println(code[i]);",
"        }",
"    }",
"}",
        };
        for(int i=0; i<4; i++){
            System.out.println(code[i]);
        }
        for(int i=0; i<code.length; i++){
            System.out.println(quote + code[i] + quote + ',');
        }
        for(int i=4; i<code.length; i++){
            System.out.println(code[i]);
        }
    }
}

Running this produces exactly the same output as the source code. I've heard that the fixed point theorem applies, meaning that any turing-complete programming language will contain a quine. However, the more I thought about this the less it made sense.

The rules for the fixed point theorem in mathematics are that it must be continuous, bounded surface with no holes or 'cutting and gluing'. This seems to make no sense in terms of programming languages.

The first rule can be broken by the nature of characters as not continuous, for example there is no inbetween 'a' and 'b' in terms of ASCII encoding.

The second rule can be broken by stating that there can be infinitely many programs all equally valid, for example you could have System.out.println("");, System.out.println("a");, System.out.println("aa");...System.out.println("aaaaaaaaaaaaaaaaaaaaa");.

The third rule can be broken by saying that not all programs are valid, for example abstract System out.println(23");" is not valid, however the build output could be used as the output, ie

Main.java:2: error: class, interface, or enum expected
  public static void main(String[] args) {abstract System out.println(23");"
                                                   ^
Main.java:2: error: ')' expected
  public static void main(String[] args) {abstract System out.println(23");"
                                                                        ^
2 errors

If all but one of the rules are broken, then why does the fixed point theorem still apply?


texts: Ensure a vertex has the highest flow in max-flow algorithm

texts:
Let's suppose we have a supplier, sorting facilities, shipping companies and
a target warehouse.
We produce n packages of the product, and each goes to a different sorting facility (so every facility receives exactly one package).
A sorting facility then passes the processed product to a shipping company,
each sorting facility is only connected to a limited number of shipping companies, meaning that It can only use a limited subset of all shippers to deliver the product to the warehouse.
Now, the company owner's brother runs shipping company A and the owner really want's to help his brother start up his bussiness.
We need to ensure that all packages are delivered, but company must A deliver most of them - so It's a max flow problem with a requirement, that vertex corresponding to company A has the highest flow of all the shipping companies vertices.
Here Is a sample graph representation I have came up with. Vertex 0 is the supplier, vertices 1-6 are the sorting facilities, vertices 7-10 are the shipping companies, and 11 is the warehouse.
Now, assuming vertex 7 is the owner's brother's company, we want to get a maximum flow in this graph such that flow through 7 is greater than flow through 8, 9 or 10
How can this graph (or any of the max-flows algorithms) be modified to ensure, that the requirement holds for vertex 7?


texts:
How to reverse the order of elements in an array between indices $i$ and $j$.
Ex: For the array [A,B,C,D,E,F], calling the function reverse(array, 1,4) will modify the array to be [A,E,D,C,B,F].
I want to optimize the solution to work with multiple calls on the same array, so pre-computations allowed. What would be the most efficient way to do so?


texts: How to determine the range of a number represented in IEEE-754 format?

texts: Given a format: say 12-bit floating point with sign bit, 5 - bit biased exponent and 6- bit significant with implied bit, how do i go about determining the range of values which can be represented. I have tried various times and each time i got a different answer. I'm afraid i'm not quite sure how to approach this problem.


texts: Confusion about complementation of an NP language with oracle and coNP with oracle

texts:
Hello Stackexchangers,

I've come across a confusion in one of my exercises.

I was supposed to prove $\Pi_{n+1}^{p} = (\textit{co-NP})^{\Sigma_{n}^{p}}$, where the superscript operator in $M^{A}$ refers to a TM $M$ having access to an oracle in $A$.

I have two rules: $\Pi_{n+1}^{p} = co-\Sigma_{n+1}^p$ and $\Sigma_{n+1}^{p} = NP^{\Sigma_{n}^{p}}$. I understand we can simply do a substitution whereby $\Sigma_{n+1}^{p} = co-(NP^{\Sigma_{n}^{p}})$, but am confused as to what the brackets would mean. Is this the same as $(co-NP)^{\Sigma_{n}^{p}}$?

The former is a complement of the languages in NP having oracle access to $\Sigma_{n}^{p}$, but the latter is the set of languages where co-NP has oracle access to $\Sigma_{n}^{p}$. I was wondering if they are the same.


texts: Are Java and C# also purely interpreted languages?

texts: I was wondering about the nature of these managed languages i-e since c# and java both are converted into intermediate language and byte code respectively, and are interpreted by their respective runtime(s). So if they are somehow pure interpreted languages then is it feasible to develop any crucial application on these technologies?


texts: Analysis of finding the k-th largest element in a subsegment of an array

texts:
Given an array $A$ of length $N$. There are $Q$ queries, each queries will be in the form

What would be the c-th number in the segment A[l...r] if the array is sorted?

I've come up with an $\mathcal{O}(N\log N+Q\log^3N)$ solution:

Build a segment tree, keeping array A sorted in each subsegment.
Binary search the value v which will be the answer.
Each time we binary search, we query the segment tree:
"What will be the rank of v in the subsegment A[l...r]"

Each segment tree queries takes $\mathcal{O}(\log^2N)$ time:
$\mathcal{O}(\log N)$ time for segment tree traversal and $\mathcal{O}(\log N)$ time for binary search the rank of value in the segment.
For each segment tree queries, if the we have to call query in both left node and right node, then we have to sum up the queries.

C++ code:

int query(int currentNode, int Left, int Right, int v){
    if(LeftBound[currentNode] == Left && RightBound[currentNode] == Right){
        return lower_bound(segmentDataVector[currentNode].begin(),segmentDataVector[currentNode].end(),v) - segmentDataVector[currentNode].begin();
    }
    int half = (LeftBound[currentNode] + RightBound[currentNode])/2;
    // For simplicity, left node number will be 2*currentNode and right node number will be 2*currentNode + 1.
    if(Left <= half && half < Right){
        // Query again in both left node and right node.
        return query(2*currentNode, Left, half, v) + query(2*currentNode + 1, half + 1, Right, v);
    }else if(Right <= half){
        // Query only left node.
        return query(2*currentNode, Left, Right, v);
    }else{
        // Query only right node.
        return query(2*currentNode+1, Left, Right, v);
    }
}

And we binary search for v which query(1,1,N,v) == r-l+1-c becomes true, answering v.

After that, I came up with a better solution which takes $\mathcal{O}(N\log N + Q\log^2N)$:

Build a persistent segment tree.
Count the array A into buckets B (like counting sort).
Let B[i] be an array denoting the occurrences of i in A.
Sort the array A into array C.
Create an array D of length N, setting all elements to zero.
Let the persistent segment tree be linked with the array D.
For i in C start from minimum to maximum:
    For j in B[i]:
        D[j] = 1
        Update D[j] = 1 into current version of segment tree.
Binary search the version value v which persistent segment tree version v sums from l to r results c.
Answer B[v].

But it isn't optimized enough. I know there exists the $\mathcal{O}(N\log N + Q\log N)$ solution, but I didn't know the solution yet. My friend told me that he knows 3 solutions that are linearithmic. Please don't tell me the solution, I want to think a little bit more.

The question I want to ask is:

"Does an $\mathcal{O}(N\log N + Q)$ solution exists, regardless of memory complexity?"
If that really exists, please give me some clue/solution.

This problem is a classical problem which can be found in Codeforces(http://codeforces.com/blog/entry/9204), SPOJ MKTHNUM (http://www.spoj.com/problems/MKTHNUM/) and the anudeep's blog explanation which I don't want to read the solution yet(https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/)


texts: How to find indexes of numbers that has many occurrences?

texts:
Disclaimer: This is a simplified part of a question from my homework, addressing the point that I didn't figure out.

  let A be a 1-indexed sorted array of $n$ elements.

  There are at most 3 numbers that has at least $\lfloor n/4 \rfloor+1$
  occurrences.

  Find three indexes that will surely "hit" all such numbers. Explain why it's certain.

Because this is a sorted array, all such numbers will be stacked together, so each "number group" have a limited freedom to travel around the array.

It feels like going symmetrically for $n/4$, $n/2$ and $3n/4$ would be a wise guess, but I'm not sure how to prove it, and furthermore $n$ might not be a multiplicity of 4, so we have to round up or down the indexes.

How can I tackle such question?


texts: Distinguish Decision Procedure vs SMT solver vs Theorem prover vs Constraint solver

texts:
Those terminologies confuse me. As I understand

SAT solver: decide the satisfiability of propositional logic (using DPLL or Local Search).
Decision procedure is a procedure to decide the satisfiability of a certain decidable first-order theory.
SMT solver is a SAT solver + decision procedure.
Theorem prover indicates something like Dynamic Logic, e.g. the KeY tool
Constraint solver: I don't know.

But I see people calling Z3 a theorem prover. So I don't know how to dishtinguish those terms. And what is the most general term for all of them? Thank you.


texts: Is it possible to submit every March Madness bracket?

texts:
A few years ago Warren Buffett started offering $1 billion to anyone who could correctly predict the winner of every game in the NCAA men's basketball tournament. A 64 team (we won't count the first four play-in games) single-elimination tournament bracket like "March Madness" has 2^63 possible bracket combination, putting the odds of correctly predicting a perfect bracket around 1 in 92 quadrillion.

But what if I don't want to leave this up to chance or skill? If I wanted to submit all 2^63 possible brackets to ensure that I submitted a winner, how improbable is this? I see two limiting factors - computational time and storage space, although I might argue that this is possible.

My question is two-fold:

Given current computing limitations, how long would it take to compute all possible brackets? Particularly, how long would it take to compute one bracket, and how quickly could the fastest computer compute them all?
How much space would storing these brackets take, and is it a feasible amount of storage?

For 2, my guess is that it's a lot of data, but it's feasible. A bracket can be represented by 63 bits, each bit representing a game in the tournament and the 1 or 0 signifying whether the high or low seed won. Thus we have 2^63 brackets, each at 7.875 bytes each, for a total of roughly 72.6 exabytes of data. Given that Google is estimated to have between 10-15 exabytes of data, this is an absurd amount of data but not out of the realm of storage possibility.


texts: What does $O(\alpha(n))$ amortized time mean?

texts:
DELETE(S, i): Delete integer $i$ from the set $S$. if $i \notin S$, there is no effect.

from a set of consectutive integers like $S = \{1,2,3,5,6\}$

Provide a data structure and an algorithm for DELETE that takes $O(\alpha(n))$ amortized time

not sure what what does $O(\alpha(n))$ amortized time mean?

I was thinking AVL trees ? I know the worst case is $O(\log n)$ for that. Not sure what $O(\alpha(n))$ amortized time means though.


texts: 3-SUM hardness vs lower bounds on the complexity

texts: I've recently encountered a new (for me) notion from computational complexity theory called 3-SUM hardness which is based on the conjecture that 3-SUM problem can not be solved in $O\left(n^{2-\varepsilon}\right)$ time where $n$ is the number of reals among which we should check whether three of them sum to zero. By giving reduction from 3-SUM we get that it is unlikely that our problem could be solved in subquadratic time. From the other hand we can prove the lower bounds on the complexity of solving our problem. Then what is the difference between these two notions ? Does it just mean that giving the reduction is simpler than obtaining lower bounds or in other words we have an additional assumption (which usually remains unproved for ages :-))in our pocket that helps us prove the lower bound.


texts: Is any randomized Algorithm a probability distribution over the set of deterministic Algorithms?

texts:
If there is a finite set of Instances of size n and the set of (reasonable) deterministic algorithms is finit.
Can any randomized Algorithm be seen as a probability distribution over the set of deterministic Algorithms? And if yes, why?


texts:
I'm trying to calculate the best and worst position for each team in the ranking based on the weekly matches.

Suppose we have 4 teams with these position:

Pos.| Name   | Pts.

1  | Team A | 12

2  | Team B | 10

3  | Team C |  8

4  | Team D |  6

And during the week there are 2 matches A vs C and B vs D

If you don't know, in soccer you can win, lose or draw. A win are 3 points, draw 1 points each, lose 0 points.

In this scenario we have 9 possible combinatiosn [3^(number of matches)].

What I want to do is calculate the best and worst position each team can get based on all combination.

Of course is fairly simple to do with 4 teams (2 matches), but in real case scenario we would have about 10 matches (59000 combinations).

I guess the best way to approach the problem is to use recursion but I can't get to a real starting point.

Any help?


texts: Extending the causal memory model to wide-area distributed storage systems

texts:
In the seminal paper "Causal memory: definitions, implementations, and programming", distributed causal memory is defined to ensures that all the processes in a system agree on the relative ordering of operations that are causally related.

Its implementation:

For its implementation, each process maintains a private copy of the abstract shared causal memory. All the processes are peer-equivalent, each of which invokes (as a client) and handles with (as a server) read/write operations locally and communicates asynchronously with each other. The scenario is depicted in the following figure.

Vector clocks are used for causality tracking among operations. The key point I am concerned with is that the implementation (in section 5) keeps one entry in each vector clock per client.

Extending it to wide-area distributed data storage system:

Now consider a wide-area distributed data storage system that aims to implement a causal memory. I have the following problems concerning about the scalability of the implementation mentioned above.

My problems:

  The clients in such system can be enormous and even unpredictable. Does this mean that it is not practical (if not impossible) to adopt the vector clock mechanism that keeps one entry per client?
  If the vector clock keeping one entry per client is not feasible, how to track the causality among operations? Are there any research papers or systems on this issue?
  The architecture depicted in the figure is definitely not applicable to the wide-area distributed data storage system because we cannot simply provide an exclusive server for each client.  Then, what are the appropriate architectures in this situation?

p2p_localarea_replication http://i1.tietuku.com/26a4136815e1ff37.png


texts: How to set up a recurrence relation to analyze number of execution of the basic operation of this algorithm?

texts:
This an algorithm to count inversions in an array, this is a divide and conquer algorithm, I want to know what is the basic operation of the this algorithm and how do I set up a recurrence relation to analyze number of execution of the basic step?
The definition of basic step: The operation contributing the most to the total running time of an algorithm.
– It is typically the most time consuming operation in the algorithm’s innermost loop.
• Examples: Key comparison operation; arithmetic operation (division being
the most time-consuming, followed by multiplication)
this is the algorithm
  public static int merge(int[] arr, int[] aux, int low, int mid, int high)
    {
        int k = low, i = low, j = mid + 1;
        int inversionCount = 0;

        // while there are elements in the left and right runs
        while (i <= mid && j <= high)
        {
            if (arr[i] <= arr[j]) {
                aux[k++] = arr[i++];
            }
            else {
                aux[k++] = arr[j++];
                inversionCount += (mid - i + 1);    // NOTE
            }
        }

        // copy remaining elements
        while (i <= mid) {
            aux[k++] = arr[i++];
        }

        // no need to copy the second half

        // copy back to the original array to reflect sorted order
        for (i = low; i <= high; i++) {
            arr[i] = aux[i];
        }

        return inversionCount;
    }

    // Sort array `arr[low…high]` using auxiliary array `aux`
    public static int mergeSort(int[] arr, int[] aux, int low, int high)
    {
        // Base case
        if (high == low) {    // if run size == 1
            return 0;
        }

        // find midpoint
        int mid = (low + ((high - low) >> 1));
        int inversionCount = 0;

        // recursively split runs into two halves until run size == 1,
        // then merges them and return up the call chain

        // split/merge left half
        inversionCount += mergeSort(arr, aux, low, mid);

        // split/merge right half
        inversionCount += mergeSort(arr, aux, mid + 1, high);

        // merge the two half runs
        inversionCount += merge(arr, aux, low, mid, high);

        return inversionCount;
    }

how do I set up a recurrence relation to analyze number of execution of the basic operation? Please also provide explanation!!


texts: How to Trace Path in Proof that Regular Languages are Closed Under Reversal

texts:
I'm self studying automata theory and I need help with proving that regular languages are closed under reversal.

I have a basic proof, but am unsure about last statement in my proof. Is this sufficient? Could you help me explain why it works? Is it rigorous enough?

Problem:
For any string $w=w_1w_2\cdots w_n$, the reverse of $w$, written $w^\mathcal{R}$, is the string $w$ in reverse order, $w_n\cdots w_2w_1$. For any language $A$, let $A^\mathcal{R} = \{w^\mathcal{R} | w \in A \}$. Show that if $A$ is regular, so is $A^\mathcal{R}$.

Proof:
Let $N = (Q, \Sigma, \delta, q_0, F)$ be an DFA recognizing $A$. We construct an NFA $M = (Q', \Sigma, \delta', q_0', F')$. Let $Q' = \mathcal{P}(Q) \cup \{q'_0\}$. For this NFA, $q'_0$ is a new start state. Let $F' = \{q_0\}$, the start state of $N$.

Define $\delta'$ so that for any $q \in Q'$ and any $a \in \Sigma_\epsilon$,
\begin{equation*}
\delta'(q,a)  = \begin{cases}
F & q = q'_0, a = \epsilon\\
q'_0 & q = q'_0, a \neq \epsilon\\
\{ x |  x \in Q\ and\ \delta(x,a) = q \}&q \neq q'_0
\end{cases}
\end{equation*}

For any $w \in \Sigma^*$, there is a path from $q_0$ to $q_{acc} \in F$ in $N$ if there is a path following $w^\mathcal{R}$ from $q'_0$ to $q_0$. Therefore, $w^\mathcal{R} \in A^\mathcal{R}$ iff $w \in A$.