texts: An imperative program is analogous to how a Turing machine works?

texts:
Since Turing machines has great influence on typical hardware architecture (Von Neumann) and both uses concept of state, is correct to say that an imperative program is analogous to how a Turing machine works?

  “Computability via Turing machines gave rise to imperative
  programming. Computability described via λ-calculus gave rise to
  functional programming.” — Cooper, S. B., Leeuwen, J. (2013) . Alan
  Turing: His Work and Impact.

And

  "Imperative programming languages such as Fortran, Pascal etcetera as
  well as all the assembler languages are based on the way a Turing
  machine is instructed: by a sequence of statements." - Barendregt, H.,
  Barendsen, E. (2000) . Introduction to Lambda Calculus


texts: Why isn't there a universal separator character for data files?

texts: I am not sure if this is the correct forum for this question, but... After so much time and usage of spreadsheets and data files in general, there is a need to cater for all types of files containing all sorts of characters used as a field separator. Why hasn't a universal separator character evolved so that no-one has to bother with tab vs. pipe vs. comma (with and without quoted fields) vs. whatever? You would think that there would be a dedicated key on the keyboard like the "Enter" button used for field separation that is non-printable and that would reduce the number of data file types to one (with the exception of proprietary formats).


texts:
We know that minimal edge cover for the normal graph is polynomial time solvable.
Is it also true for hypergraph?


texts: Describing the Language of a grammar in set theoretic notation where the length of strings need to be remembered

texts:
I am not well versed in this topic so please pardon any ambiguous notation.
I am trying to describe the language of this grammar in set-theoretic notation.

The Grammar is given by:

$ S \rightarrow ASA|B$

$ A \rightarrow a|b$

$ B \rightarrow BC|\epsilon$

$ C \rightarrow a|b|c$

I think I can accurately describe this language in english:

If $w=xyz$ is a string and $xyz$ are substrings of $w$ then

$|x| = |z|$, and $x$ and $z$ are made up of symbols from $\{a,b\}^*$.

Furthermore, $y$ is made up of symbols from $\{a,b,c\}^*$

Mores simply, the strings are made up of two ends that are the same $|length| \ge 0$ and made up of symbols $a,b$. And the middle part of the string is made up of any symbols from $a,b,c$ and also has a $|length| \ge 0$

How do I more formally and accurately describe the language of the grammar $L(G)$? Is it possible to do this in a set-theoretic notation?


texts: Can a purely declarative language really exist?

texts:
Wikipedia has several languages listed as declarative languages.  One of these languages listed is XSLT, which is a language for applying transformations to XML.

https://en.wikipedia.org/wiki/XSLT

As I understand it though, imperative languages say HOW to do something, while declarative languages only say WHAT to do and leave it up to the eg. compiler to figure out the imperative details.

In this light, since when writing XSLT we still say "Do transform A, then do transform B", it seems like we are still writing imperative code.

Furthermore, taking a language like C++ which is arguably imperative, it actually seems semi declarative because the optimizer can re-order instructions or, change algorithms.

In fact, a switch statement seems to be a declarative associative structure, with containing values known at compile time, letting the optimizer make the imperative details based on the type of data it stores.  It can do binary searching, jump tables, if/else if chains and more. http://www.codeproject.com/Articles/100473/Something-You-May-Not-Know-About-the-Switch-Statem

This leads to my question...

Is it possible to have a purely declarative language?  If so, what would it look like, and could an interpreter/compiler actually be made to convert anything into imperative machine code, beyond a no-op?

It also seems impossible to have a purely imperative language in modern days, as the CPU can do instruction re-ordering, speculative branch predictions, and similar, making your instructions more of hints as to what to do, as opposed to exact instructions of what to do.

Or am I completely off base here?


texts: Doubt with a problem of grown functions and recursion tree

texts:
I'm confused to conclude the recursion tree method a guess for the next recurrence:
$$T(n)=3T\left (\left\lfloor \frac{n}{2}\right \rfloor\right) +n$$
I write some costs for the levels of tree, you can see, but I'm confusing in the final guess. I know for the master theorem that the answer for the guess is like that
$$\Theta(n^{\log_2 3}) $$ but in the steps by tree and I don't belive, you can see my error (?). How can I finished or know the outcome for this method to calculate $T(n)$?
thanks,

And the final conclusion is (?)
$$=2 n^{\log_2 3}+\Theta(n^{\log_2 3})\leq cn^{\log_2 3} \rightarrow \ \ T(n)\in\Theta(n^{\log_2 3})$$ with $c=3$ ?


texts:
I am curious as to what steps one would reasonably need to take to perform an extraction-based text summarizer.

I've taken a look at some papers I've found on Google such as this one, which explains that UPGMA is the best clustering algorithm (out of the tested set). I've also found this one to be interesting, regarding single and multi-document summarization.

I'm unclear as to whether I'd need to combine these techniques for summarization or whether it would suffice to use a tool like Gensim to model a corpus of documents and just extract the sentences with the highest vector values.


texts: Generating 3SAT circuit for Integer factorization example

texts:
I read somewhere that 3SAT can be used to solve Integer Factorization.

If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given the number 6, then the factors are 2 and 3.


texts: Is binary-search really required in Chan's convex hull algorithm?

texts:
I have a little doubt about Chan's algorithm.

From Wikipedia's description we see that the second phase of an algorithm works with $K = \mathrm{ceil}(\frac{n}{m})$ subsets $Q_i$. The goal of the second phase is to compute $m$ points $\{p_1 ... p_K\}$. On $i$-th iteration the candidate $p_i$ is chosen among $\{q_1 ... q_K\}$, where $q_j \in \mathcal{CH}(Q_j)$  is a point such that every other point of $\mathcal{CH}(Q_i)$ lies to the left of line $p_{i - 1}q_j$.

According to the Wikipedia page, each point $\{q_1 ... q_K\}$ of set is searched in $\mathcal{O}(\log m)$ using binary search, which is the main reason that whole second phase takes $\mathcal{O}(Kh + Kh \log m)$, where $h$ is the size of resulting convex hull (which is unknown at the beginning).

I doubt that it is necessary to perform this binary search for every candidate-point $q_i$ on each iteration. I get that, when we just start with $p_0$, there's no other way to do this. What about the following iterations? As I think of it, on each iteration the point $q_i$ either stays the same or it changes to one of the successive point of $Q_i$ in ccw-order. And one point cannot become a candidate more than twice (or even once?). If that is the case, why can't we use $K$-pointer technique and just set $q_i \leftarrow q_{i + 1}$ while $q_i$ is not a tangent line for current iteration. There shouldn't be more than $2m$ candidate changes for each $Q_i$ for all $m$ iterations. Wouldn't the resulting complexity $\mathcal{O}(Kh + Km)$ be better than $\mathcal{O}(Kh + Kh\log m)$?

And some pictures that aren't on wiki page to give a better idea of this second phase.
The first one shows what are the candidates.

And the second one should provide an intuition about choosing $q_i$ for the next iterations.


texts: Applicabilty of master theorem (case 1) for T(n)=9T(n/3)+nlogn

texts:
I want to know if the recurrence equation $T(n) = 9T(\frac{n}{3}) + nlogn$, can or cannot be solved using master theorem.

At first, I naively went for $O(n^2)$ applying case 1 of master theorem. But then someone pointed out that $f(n)=nlogn$ and $n^{\log_3 9}$ do not have polynomial difference  and therefore master theorem cannot be used.

Then I found this proof for master theorem. Proof of case 1 is on page 2 of the document right on top of the page. The proof is based on the inequality:

$f(\frac{n}{b^i}) \leq(\frac{n}{b^i})^{\log_a b -\epsilon}$

which allows the right side of the above inequality to replace f(n) and the proof goes on from there.

As I see it, the above inequality holds for $f(n)=nlogn$ so I think master theorem can be applicable here. I want to know if I am right and if not, why?


texts: Trouble finding what this recurrence solves to

texts:
I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$

I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.


texts: The theoretical upper bounds for duplicate detection in a set of objects?

texts:
I recently had a lengthy exchange with someone about the most efficient way to remove duplicates from a collection.  The debate was mostly centered around the specific behavior of C# collections, such as HashSet(T) and HashTable(T).

I think we agreed on the fundamentals, but where we couldn’t come to an agreement was what the constraints are with very large sets.

He told me to investigate the theoretical (ie absolute) bounds for duplicate detection in a set of objects… But I don’t really know what that means.  I don’t think there’s an absolute bounds if you can break up the problem sufficiently.

There may be a point at which you can no longer use a HashSet / HashTable in .NET because I know that if you are using the framework au-naturale you are constrained by the number of unique values an Int32 can express and the amount of memory you have available.

But the issue of storage and memory issue comes much sooner than the number of unique values, which is typically what the theoretical is concerned with... For example if the data type is integers for the initial set you're removing duplicates from, you run out of memory before the numeric range of the integer type becomes a problem:

If I am storing integers, I know that there are 2^32 possible integer values.
To store an integer, I need 32 bits of space, so the total memory required to store all distinct integers is 2^32*4 bytes, which is 17.18 gigabytes.
The amount of memory that can be addressed in a 32 bit architecture is 2^32 bytes or approximately 4.295 gigabytes

Even if I’m not using a hashset, I can see that in order to store that many values, I would need at least four times the amount of memory addressable by the architecture for the initial collection.  And that's not even factoring in the duplicates we're seeking to remove.

I would also need memory proportional to the size of the initial set for the hash set implementation and hash set value storage… So the use of a hashset quickly becomes unfeasible when you exceed millions of unique values.

I’ve already asserted to him that if you had a large digit such as a long, and you had billions of values, you would not use a hashset.  Hypothetically I might store the data in distributed nodes that are pre-sorted by the unique field, or implement a distributed mapreduce sort implementation, followed by a mapreduce duplicate value removal algorithm.

He didn’t acknowledge the feasibility of the sort/remove duplicates approach though… And was quite insistent that there is an upper bound for duplicate detection.

Could anyone tell me what the ‘absolute’ bounds for duplicate detection for a set of objects is?  Or what he was was referring to by it?


texts:
A(B ∩ C) = { UV | U ∈ A, V ∈ B and V ∈ C } for the left part.

ΑΒ = { UV | U ∈ A, V ∈ B },

ΑC = { UV | U ∈ A, V ∈ c },

AB ∩ AC = { UV | U ∈ AB and AC, V ∈ AB and AC } for the right part.

How can I continue further into the proof?


texts: How can I infer inputs to a function, given an output?

texts:
Is there a way to generate a set of inputs, for a given output of a function? This may be a common thing in lisp/haskell world, but I'm not aware of it. Is this what mini-kanren does?

I understand that there may not be a general solution to this problem, since the halting problem may apply here. Say the function implementation is constrained to remove unlimited recursion. Type inference engines obviously do something similar to figure out the types of variables, I would like to generate actual values.

I'm thinking of a couple of scenarios where this might be useful:

func blowup(x): 1/x

I would like some sort of static checker to figure out that this function will cause problems if x=0.

func launch(x): ...launch missle x miles...
func isSafe(y): if x > 10 then true else false
func main(): x=.1; if isSafe(x): launch(x)

In this case, I would like to not only infer values of launch, but I would like to take isSafe as a constraint and tell me at compile time (since all information is available) that x of .1 not a good value.

Btw, I'm not looking for a library to do this. What I would love is either the name of this concept (beyond the generic 'static checking') and reference material which describes this idea (easily read papers, books, etc.). I should also mention that I'm aware of tools such as quickcheck. I'm not looking for a probabilistic way of inferring values. I would like a deterministic way of inferring values as early as possible, even if that means that my solution limits the types of expressions I can express.


texts: Are regular languages closed under sort (Parikh image)?

texts: Assume $L$ is a regular language over an ordered alphabet.  Is the language built by taking every word in $L$ and sorting it always a regular language?


texts:
I have to write a grammar for the following language:
$$\{1^{n^2} \mid n\geq 1 \}$$
I am having trouble figuring out the production rules. I was thinking of using the fact that $n^2$ can be written as the sum of first $n$ odd numbers but couldn't proceed any further.


texts: what are the weakest preconditions of these following statements

texts:
what is the meaning of postcondition and weakest postcondition in terms of programing and what are weakest postconditons of following statements.
1. a=2*(b-1)-1   {a>0}
2. b=(c+10)/3    {b>6}
3. a=(a+2*b-1)   {a>1}
4. a=2*b+1;b=a-3 {b<0}


texts: Do data structures help to reduce complexity of operations, at the cost of something else?

texts:
I often heard that using data structures help to reduce (time or space) complexity of some operations.

I wonder if that is achieved at the cost of something else?
When solving a problem, is something still conserved, over all
choices of data structures and algorithms, just like the
conservation of energy? Such as some kind of overall (time or space)
complexity of an algorithms and a data structure being used?


texts: Prove that a hamiltonian DAG has a single topological sort

texts:
I've been straggling a little proving the argument "a hamiltonian directed acyclic graph has a single topological sort".

This is pretty much the idea of what I've come along:

lets prove by contradiction. so lets assume a hamiltonian DAG has at least 2 topological sorts.
If there're few topological sorts - it means one of the following options:
either there're at least 2 vertices that aren't dependent. meaning both of these vertices could be with 0 in-degree. but it contradicts the fact that the graph is hamiltonian (there's a hamilton path in G)
either there exists a vertex that splits to 2 branches. such that the neighboring vertices could appear in different order in the topological sort. but it contradicts that the graph is hamiltonian because in such a case - after choosing a branch, we won't be able to visit the vertices of the second branch. however if we do have this possibility, we have come to a cycle that ends in the vertex that split to 2 branches. (contradiction to the graph being a DAG)
Finally we get contradiction to our assume - thus the original statement is correct.

Would appreciate your thoughts and suggestions about the idea of proof.


texts: Algorithm to check the 2∀-connectness property of a graph

texts:
A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of G.

I know the basic idea is to build a DFS searching tree and then check each edge is not on a circle with DFS. Any help would be appreciated.

What I expect to see is a detailed algorithm description(especially the initialization of needed variables which is obscure sometimes), complexity analysis could be omitted.


texts:
I'm curious. I've been working on this datatype in OCaml:

type 'a exptree =
  | Epsilon
  | Delta of 'a exptree * 'a exptree
  | Omicron of 'a
  | Iota of 'a exptree exptree

Which can be manipulated using explicitly typed recursive functions (a feature that has been added quite recently). Example:

let rec map : 'a 'b. ('a -> 'b) -> 'a exptree -> 'b exptree =
  fun f ->
    begin function
    | Epsilon -> Epsilon
    | Delta (t1, t2) -> Delta (map f t1, map f t2)
    | Omicron t -> Omicron (f t)
    | Iota tt -> Iota (map (map f) tt)
    end

But I've never been able to define it in Coq:

Inductive exptree a :=
  | epsilon : exptree a
  | delta : exptree a -> exptree a -> exptree a
  | omicron : a -> exptree a
  | iota : exptree (exptree a) -> exptree a
.

Coq is whining. It doesn't like the last constructor, and says something I don't completely understand or agree with:

Error: Non strictly positive occurrence of "exptree" in "exptree (exptree a) -> exptree a".

What I can understand is that inductive types using a negation inside their definition like type 'a term = Constructor ('a term -> …) are rejected, because they would lead to ugly non well-founded beasts like (untyped) λ-terms.
However this particular exptree datatype seems innocuous enough: looking at its OCaml definition, its argument 'a is never used in negative positions.

It seems that Coq is overcautious here.
So is there really a problem with this particular inductive datatype?
Or could Coq be slightly more permissive here?

Also, what about other proof assistants, are they able to cope with such an inductive definition (in a natural way)?


texts: Distance to $k$th nearest neighbor efficiently for arbitrary $k$

texts:
Problem.  Given $X$ a finite metric space of cardinality $n$, construct a data structure in subquadratic time such that the query distance to the kth nearest neighbor of x can be resolved in sublinear time (independent of $k$) for arbitrary $k \leq n$ and $x \in X$.
What I have tried. I am aware of the existence of kdtrees, ball-trees, and cover trees. Under some assumptions (which I'm willing to make), I know that these structures can resolve the query distance to the nearest neighbor of x in sublinear time (often $O(\log(n))$), but I haven't been able to find similar results for the $k$th nearest neighbor for arbitrary $k$.
It seems that, often, one is interested in $k$ values that are small compared to $n$, and that, in those cases, the algorithms mentioned in the previous paragraph can be adapted at the cost of a multiplicative constant of the order of $k$. My problem is that I am interested in $k$ values that are potentially of the order of $n$.


texts: Examples of Analysis of Branch and Bound Method

texts:
I am solving a graph problem, which can be formulated as an integer programme. Based on computer experiments, it seems that the branch and bound method works well. I would like to analyse the running time, and wonder whether there have been other problems where branch and bound method was used and the theoretical bounds on the running time has been established?

On another note, if anyone knows any examples of problems where the range of possible values that a variable in a linear programme can take, I'd also be interested in.


texts: Algorithm to choose the best team of 6 Pokémon given a constraint

texts:
Apologies if this is a duplicate. I searched for some time and the closest I could find was the Knapsack Problem, which does not fit because I have a fixed team size & a different value function.

I have $N \approx 50$ Pokémon, from which I need to choose a team of six to attack an enemy. Each pokemon can survive for a certain time "$t$" against the enemy, and each pokemon does a certain amount of damage per second "$DPS$" to the enemy. I may or may not defeat the enemy, but I would like to optimize the damage I can do to it within the time limit of 300 seconds without my entire team dying.

These data are sufficient to determine the optimal team. The damage done by a team, which fights in order of highest > lowest $DPS$, is the sum
$$Damage(DPS_i, t_i) = \sum_{i=1} DPS_i * \hat{t_i} $$
where $0<\hat{t_i}<t_i$ is the amount of time each pokemon battled for. Typically the first few pokemon will battle until they die ($\hat{t_i}=t_i$), one pokemon will win with a fraction of its health remaining ($0<\hat{t_i}<t_i$), and the rest may never get to battle ($\hat{t_i}=0$).

The optimization problem can be phrased as follows:

Maximize the function $Damage(DPS_1, ST_1, ..., DPS_6, ST_6)$
Given the constraint that $\sum_i t_i >300$

It is clear that this can be brute-forced by checking the damage and survival time of all team combinations. This is not an option because it takes too long.

Another possibility was to start with the highest-DPS team and then make "trades" in order of highest gain in $t$ per sacrifice of $DPS$. However I'm not convinced this will converge to the optimal solution.

I would be very thankful for any suggestions or references to analogous problems.


texts:
As it says in the title:

  Are there problem instances which we know to be unsolvable?

Or equivalently

  Are there any promise problems with a finite number of possible inputs
  which are undecidable?

Please note:
I realize that many computational problems are known to be unsolvable, but to the best of my knowledge (limited it may be) all must take an infinite number of inputs. Therefore, their existence does not imply that there cannot be an infinite number of algorithms each solving a subset of these problems.

Remark: I only wish to consider well-defined problems, i.e. every input has a correct output.

On a related note, is there a complexity hierarchy for promise problems with only a finite number of possible inputs?


texts: What is the difference between operator and function?

texts:
We have operator and operands, function and formal arguments. Is the difference purely lexical (we use alphanumerics for funciton identifiers but identify operators with special characters, e.g. "+" and ">=") or it is syntactical, like I guessed here

f(a,b) -- prefix notation used for functions
a.f(b) -- infix notation for method invocation (used in OOP)
a f b  -- infix notation without dot and parenthesis used in operator invocations

so that when we write a + b we have an operator but "+"(a, b) (both ways are acceptable in VHDL) makes it a function? Do tools treat them differently? Can you differentiate them? Can you say that this is not a function, it is an operator or vice-verse? When I read the definitions in wikipedia, I do not see that syntax is a distinguishing feature of a concept. So, is it right that operators and functions are synonyms, two different words for the same thing, same meaning, same notion? I have such guess but have never seen it stated explicitly. Please agree with my guess or say what is the difference.


texts: NP-Complete reductionTrue/False question explanation

texts:
Why is the above statement true? my understanding is:

(1)3SAT reduces to X implies X is NP-complete or harder.

(2)Set Cover reduces to X implies X is neither NP-Complete nor harder.

This contradiction gets me a bit lost as to why  the conjunction of 1 and 2 implies that X exists in P. I'm hoping someone can explain this to me. Note: both 3SAT and Set Cover are NP-Complete.


texts: Why not do these checks on the number of clauses in 3-SAT?

texts:
I've been writing a 3-SAT solver for fun and comparing its performance against the solver pycosat. My solver vastly outperforms pycosat in two special cases, where I solve by doing simple, obvious checks, which pycosat doesn't seem to do (based on the time it takes to solve these cases).

I presumed that these checks would be known and commonly incorporated into solvers. Is that the case? Why would a solver not bother doing them?

The checks are based on the following:

Let $\phi$ be a CNF with $n$ variables and $m$ disjunctions, where each disjunction has exactly 3 distinct variables and no two disjunctions have the same literals.

1) If $m < 8$, then $\phi$ is satisfiable.

2) If $m > 7* \binom{n}{3}$, then $\phi$ is unsatisfiable. ($\binom{n}{k}$ is the binomial coefficient.)

The proof is simple but tedious. I can provide it if needed.


texts:
Im studying a book called "Engineering a compiler" by Linda Torczon and Margaret Cooper. In the second chapter which discusses lexical analysis they mention three aproaches to writing a lexical analyser: 1. Table-driven, 2. Direct coded and 3. Hand coded.

My question is: how do hand coded lexers generally work ? Are they similar to either table-driven or direct-coded ones ? Where can i find simple examples of hand coded lexers ?


texts: Maximum set packing and minimum set cover duality

texts:
I read that the maximum set packing and the minimum set cover problems are dual of each other when formulated as linear programming problems. By the strong duality theorem, the optimal solution to the primal and dual LP problems should have the same value.

However, consider a universe $U = \{1, 2, 3, 4, 5\}$ and a collection of sets: $S = \{ \{1, 2, 3\}, \{3, 4, 5\}, \{1\}, \{2\}, \{3\}\}$. From what I understand, a minimum set cover would consist of the first 2 sets in set $S$, while the maximum set packing consists of the last 3 sets. These solutions aren't in accordance with the statement of the strong duality theorem.

Given that, I don't understand how the 2 problems can be dual of each other. What am I missing?

Thank you very much.


texts: Confused about XORing and addition modulo $2$

texts:
It's my understanding that when you XOR something, the result is the sum of the two numbers mod $2$.

Why then does $4 \oplus 2 = 6$ and not $0$? $4+2=6$, $6%2$ doesn't equal $6$. I must be missing something about what "addition modulo 2" means, but what?

  100 // 4

  010 // XOR against 2

  110 = 6 // why not zero if xor = sum mod 2?


texts: What is meant by "uneven spacing" on number line when dealing with floating point numbers in computers?

texts: I read some examples online on this subject, but none of them really gave an explanation. When I visualize the number line all I can see is evenly spaced numbers, I'm not grasping the notation of "uneven spacing" when It comes to plotting the floating point values from a machine's perspective. Perhaps I am thinking about this too literally.


texts: How do you call alternatives in the grammatical productions?

texts:
I have encountered a question, which asks what is a syntactic form. This motivated me to ask myself, what is the anatomy of the grammatic rule,

     S ::= A | B | C

Anatomy established that S is called LHS whereas A | B | C is called expectedly RHS. But, how do you call the individual alternatives within the RHS? Is it related to your syntactic forms?


texts: Viterbi algorithm for shortest path calculation

texts:
I have to write an essay about shortest path calculation with Viterbi algorithm. Since I am interested in finding the path with the least weight on the network graph, I am a little bit confused how to model the network since Viterbi works only on trellis graphs. Does Viterbi require directed acyclic graph or it could be used on graph with cycles?

On this link I found some hints how Viterbi is used to compute shortest path. It seems like Bellman Ford algorithm to me, but there is some topological sorting in first step of the algorithm? Why I need it?


texts: If xor-ing a one way function with different input, is it still a one way function?

texts:
Suppose $f(x)$ is a one way function. What about $h(x)=f(x_1) \, \oplus \,f(x_2)$, where $x=x_1 || x_2$ and $\lvert x_1 \rvert = \lvert x_2\rvert$?

$\oplus$ is exclusive disjunction (xor)
$||$ is concatenation
$|u|$ is the length of $u$


texts: gauss newton algorithm - what starting values

texts:
I am trying to implement the wikipedia example of the Gauss-Newton algorithm. Although it does work as intended, when changing the starting values, it takes significantly more iterations to converge and does not always land on the same values.

I am trying to understand how the example computes the initial starting values input to the algorithm.

I would appreciate if you kept in mind in your answers that I am new to algorithms and without a strong background in maths.


texts: Describe the language generated by a given context free grammar

texts:
I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction.

$$\begin{align}
    S &\to SA \mid \epsilon \\
    A &\to aS \mid bA \mid b \\
\end{align}$$

I got this wrong on my test and my professor isn't explaining why.  Just references the pdf notes he gave us.  My answer was very incomplete as when I created parse trees to figure out a pattern for the language I came to the conclusion that a word can either have all or none both a and b.  And I couldn't find any real pattern.  I didn't even get to the proof part of the question and I was hoping someone might be able to direct me in the right direction.

With the help of Rick Decker, I got as far as seeing the language was (a+b)* but was not sure how to proceed. So by choosing a w of an arbitrary length n that is greater than 0, if we take a string and add it to the prefix of z to get zb or za, and z is an element of L than the proof holds from the derivation? How do you come up with the derivation? Does that require a proof?


texts: Selection, crossover and mutation function choice in genetic algorithms

texts:
I have been developing a GA for one of the projects I'm working on. I have everything implemented with no problems and I really like how GAs work in general, it's a really cool and relatively new concept. However I'm wondering which specific algorithms I should use for selection, crossover and mutation.

I understand that it often depends on what your data type is, for example individuals who's chromosome order is important should use crossover algorithms listed on this Wikipedia article (with maybe a few more to be added to that list), but how do I choose between them? What should I consider when I am selecting which algorithms to use for these three things?

Currently I have implemented Tournament selection, partially matched crossover and index shuffling for mutation and this gives me the exact output I want, but how do I know these are the best choice for my problem.

(P.S. This is purposefully as abstract as possible, I'm not looking for an answer to my specific problem but more how anybody can go about choosing which algorithms are best for their particular situation.)


texts: Proving that L is not regular using closure properties

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

$$L = \{\ ab^jc^j\ |\ j \geq 0\ \}\ \cup\ \{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \}$$

There is also a hint that it cannot be proven just with using the Pumping Lemma. Closure properties must also be used.

I'm having a hard time with this one. Any help would be appreciated.


texts: Relation between the size of sub-problems and number of sub-problems in a recurrence

texts:
Below is a well-known equation for generalized recurrence relation in a divide and conquer paradigm (as described in CLRS) --

$$T(n) = aT(n/b) + f(n), \quad \text{where} \quad a \gt 1 \text{ , } b \geq 1$$

If we consider a case for merge-sort, the relation will look like this --

$$T(n) = 2T(n/2) + \Theta(n) \qquad \qquad (i)$$

which is quite straight-forward, i.e. we have $2$ sub-problems of size $n/2$ each, ($1/2$ of the original sub-problem), and $\Theta(n)$ operations to merge them.

Now if we have a relation like --

$$T(n) = 3T(n/2) + \Theta(n) \qquad \qquad (ii)$$

then we can assume that there are $3$ "overlapping" sub-problems, as each of them with size $n/2$. Let's consider again --

$$T(n) = 2T(n/4) + \Theta(n) \qquad \qquad (iii)$$

now, what does it mean? Are there $2$ sub-problems with size $n/4$? How is it possible? If we divide the whole problem into $4$ equal sizes then we should need something like $4T(n/4)$ instead of $2T(n/4)$ to balance the recurrence tree (each node with 4 leaves), right? Is this relation realistic?

If this is the case, then why there is no constraint like $b < a$ ? Moreover, is there any algorithm that follows the recurrence as in $(ii)$ and $(iii)$?


texts: Is dijkstra's algorithm fastest possible algorithm for undirected graph with no additional data?

texts:
there are many similar questions, but I haven't found direct answer to this question. Consider I have undirected, weighted graph with positive weights, no additional data - hence no heuristic (so it is not possible to use A*), is Dijkstra's algorithm with Fibonacci queue fastest known algorithm in terms of big-O notation? If so, is it proved it is fastest possible algorithm? Dijkstra's with Fibonacci queue is O(|E| + |V| * log |V|)

Edit:

apparently Wikipedia answers my first part of the question:

  This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights

but do we know if it is fastest possible algorithm?


texts:
While learning depth first traversal, I realise there are two approaches that are followed.

Method 1. The first one is as given in the Forouzan's book is as follows:

Push the initial node onto the stack
Pop the stack
Process the popped out node
Push all its adjacent nodes onto the vertex
Go to step 2.

Method 2. Then there is a version of depth first traversal as given in CLRS:

Push the node onto the stack
Process the pushed node
Push one of its adjacent node onto the stack.
If there is no adjacent node to the stack top node, then pop it.
Go to step 2.

CLRS does not explain it in terms of push and pop operation on stack. However I made this push pop version equivalent to CLRS Depth First traversal explanation. This approach is also explained in this video.

I observe the following points:

The two versions yields different stack contents and processing sequence.
Method 1 pops out the node before pushing its neighbor. Method 2 pops out the node after all its descendants are processed.
Method 1 pushes all adjacent nodes and processes the stack top node while method 2 pushed one adjacent node, processes it, pushes its adjacent node. This results in different processing sequence, as can be seen below:

So which one is correct/preferable ?


texts: Why does Fleury's algorithm have to return to the starting node?

texts:
Recently, I am reading the Fleury's Algorithm part of the document [1]. There is a sentence on page 3 of this document:

  Note that, when the algorithm terminates, we must return to $v_{start}$ because every vertex has an even degree.

I don't understand why we must return to $v_{start}$. Could anyone please teach me?

Eulerian circuits by Ethan Kim (accessed Oct 14, 2016)


texts: Can a more powerful encoding of an input make an algorithm that is polynomial in the number of inputs become exponential?

texts:
This is probably a very basic question but one that I am having trouble finding a definitive answer for since this kind of thing is skimmed over in most introductory algorithms courses. Take an algorithm like DFS that runs in time polynomial in the number of inputs. In this case your input is a graph with $n$ vertices and $m$ edges, and your algorithm runs in time $O(m + n)$.

But we know that in reality we must always consider the lengths of binary encodings when calculating runtime. This is why something like the dynamic programming algorithm for Knapsack isn't actually polynomial.

DFS takes in $n + m$ "objects" as input. If we say that each object takes a fixed number of bits (e.g., each vertex takes 1 bit to encode and each edge takes 3 bits), then it makes sense to me that the algorithm is indeed polynomial in the input. But is there any reason that we need a fixed number of bits for each object? Might there exist a more powerful encoding of the input that takes $\log (m+n)$ bits, suddenly making the algorithm exponential?

One thought I had was just that there is an assumption that any practical encoding in the real world is going to require a fixed number of bits for every extra "object" given as input, whether the objects be vertices, letters in a string, etc.; thus it is most useful to think about runtimes this way. But I want to make sure since I think this is fundamental to my understanding. Thanks in advance!


texts: Say that a stack frame only contains total functions: could the maximum stack size be statically determined?

texts: Say that you have a program with only total functions, or if that is impossible, consider a subset of the program with only total functions. Is it theoretically possible to statically determine the maximum size of the stack frame at runtime? The language may have other characteristics that are relevant/necessary (such as a specific type system).


texts:
Consider the following:

A weak TM is a TM with finite tape in size $k$ which can only read its input values. note: the tape size does not include the input length.

I need to determine whether if the weak model is equivalent to a regular TM, or to explain why not and to show the equivalence to any other computational model.

I'm quiet confident that the weak TM is equivalent to a DFA with $\gamma^k\cdot q\cdot (n+k)$ states where $|\Gamma| = \gamma$, $|Q| = q$ and $|w| = n$.

My intuition is that there are at most $\gamma^k$ strings that the machine can write, there are $q$ states and the head can be stationed at one of the $n+k$ slots on the tape.

I'm having a hard time to prove it though, Anyone can shed some light?


texts: For $\sum = \{ 0,1 \}$, $A$ has strings which contain a $1$ in their middle third, and a $B$ which contain two $1$'s in their middle third

texts:
Language $A$ can also be represented as, $$A = \{ uvw \mid u,w \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^*\text{ and, }|u| = |w| \ge |v| \}$$

Language $B$ can also be represented as, $$B = \{ uvw \mid u,w \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^* 1 \Sigma^*\text{ and, }|u| = |w| \ge |v| \}$$

I have to prove that $A$ is CFL & $B$ is not a CFL.

To prove $A$ is CFL, I have to show that a  CFG can be made.
I made a CFG for this equation:

$$L = \{ uv \mid u \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^*\text{ and, }|u| \ge |v| \}$$
which is,
$$ S \to XSX \mid T1 $$
$$ T \to XT \mid X $$
$$ X \to 0 \mid 1 $$

But I am not able to make a perfect CFG for $A$ after much trying although they seem both same ..

Can I prove $B$ is not a CFL maybe by using pumping lemma ?


texts: Name for function in big O but not in little o?

texts:
Let $f(n) = O(g(n))$, but not $f(n) = o(g(n))$. That's a nice property, because it means that we cannot replace $g(n)$ with a substantially smaller function. Is there a name for this choice of $g(n)$?

Obviously this covers more cases than just $f(n) = \Theta (g(n))$. It requires the existence of $c > 0$ such that $f(n)\geq cg(n)$ for infinitely many $n$.


texts:
I'd like to start by stating this isn't homework! I'm studying for a job interview and would appreciate a second opinion. (Well, I guess it is homework, but not for school!).

I've written an algorithm (see pseudocode below) to merge two sorted lists into one sorted list. The problem requires that I implement it as a recursive divide-and-conquer algorithm. My algorithm is recursive and works but does it count as divide-and-conquer?

The reason I'm asking is that the other people working on the same problem insist D&C must divide the lists in half every time and have $O(n \log n)$ complexity, like quicksort and mergesort. My algorithm doesn't divide the lists in the middle and has a complexity of $O(n+m)$ (where $n$ and $m$ are the lengths of the lists).

To summarize my question: Does a D&C algorithm have to have $O(n \log n)$ complexity and divide the problem in half every time? Or does this algorithm count as D&C?

merge_sorted_lists(list1, list2)
    if(list1 and list2 are empty)
        return empty list

    if(list1 is empty)
        return list2

    else if(list2 is empty)
        return list1

    else if(head of list1 < head of list2)
        smaller = pop head of list1

    else if(head of list2 < head of list1)
        smaller = pop head of list2

    return smaller + merge_sorted_lists(list1, list2)

P.S. I've implemented the algorithm in Java and it works.


texts:
The Hitting Set Problem (HS) is defined as follow. Let $(C,k$)

$C = \{ S_1, S_2, ..., S_m \}$ collection of subset of S i.e. $ S_i \subseteq S , \forall i$
$k \in \mathbb{N}$

We want to know if exists ${S}' \subset S$ where $|{S}'| < k$ such that $S_i \cap S' \neq \emptyset $, $i = 1,2,...,m.$

Prove that HS is Np-Complete.

Hint: When $|S_i| = 2$, HS becomes Vertex Cover, already know to be NP-complete.


texts: if $L \in NP$ then its mapping reducible to HALT?

texts: This is true because every language in $NP$ is decidable and therefore HALTS but how do I formally show this?


texts: Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?

texts:
The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$.

$O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of insertion sort, it implies that $O(n^2)$ is upper bound of algorithm no matter what type of input is, means it doesn’t matter whether input is sorted, unsorted, reverse sorted, have same values, etc the upper bound will be same $O(n^2)$. But this is not the case of insertion sort. Insertion sort running time depends on type of input used. So when the input is already sorted, it runs in linear time and doesn’t take more that $O(n)$ time.

Therefore to write insertion sort running time as $O(n^2)$ is technically not good.

We use $\Theta$-notation to write worst case running time of insertion sort. But I’m not able to relate properties of $\Theta$-notation with insertion sort, why $\Theta$-notation is suitable to insertion sort.If $f(n)$ belong to $\Theta(g(n))$ we write it as $f(n)= \Theta(g(n))$, then $f(n)$ must satisfies the properties. And properties state that there exits constants $c_1$, $c_2$ and $n_0$ such that $0$$\leq$$c_1\cdot g(n)$$\leq$$f(n)$$\leq$$c_2\cdot g(n)$ For all $n>n_0$. How does the insertion sort function lies between the $c_1\cdot n^2$ and $c_2\cdot n^2$ for all $n>n_0$.

Running time of insertion sort as $\Theta(n^2)$ implies that it has upper bound $O(n^2)$ and lower bound $\Omega(n^2)$. I’m confused as to whether the lower bound on insertion-sort is $\Omega(n^2)$ or $\Omega(n)$.


texts: Complexity classes that are closed under subtraction

texts:
Are NP or P closed under subtraction? Im having a hard time deciding whether they are or aren't.
Question was edited

Original question:
Im having some hard time figuring out what languages are closed under subtraction.
Say you have 2 languages A, B ∈ NP. Is A\B ∈ NP? what about P?

Commenters:
My original question was extremely not accurate so i rephrased :)

Thanks!


texts: Where are file-information like "created" or "last edited" actually stored?

texts:
I can access some information about the files ("created" or "last edited") on my PC. But where are those information actually stored?

Are they stored by the operation system? Could be possible as if I transfer a file with FTP to an other PC, it has new timestamps for those information.

Or are they stored in the beginning of the file itself?

How does it work?


texts: How could one prove that for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ? Using induction

texts:
I am currently working on ways to prove this and got stuck proving it with induction.

Any tips?

How could i prove  that for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ?


texts: MIPS with one read port in the register file?

texts:
I'm studying the MIPS multi-cycle datapath, and I'm wondering what would happen if there was only one read port in the register file for certain instructions.

First, for R-type instructions, I know that it takes in 2 registers(for example, with 'add', rs and rt are both passed into read-port 1 and read-port 2 in the register file) and then added in the ALU. With only one read-port, the fetch step will be the same amount of time (fetching the instruction won't be affected), but the execution step will take 2 clock cycles instead of 1, because there will be a clock cycle for each time a register is passed in. Then, the other steps will also take the same amount of time after that.

But what about the load and store instructions? The register file takes rs and rt into the read-ports normally, but for example, sw STORES it's value in rt. Will this mean that the execution step won't be affected because rt will be passed into the "write register" port? Could anyone clear this up for me?


texts: matrix product openMP code in C runs slower in parallel than series

texts:
If I start with 4 threads when I run my code and increase thread number each time I run it, my run time decreases as you would expect. However, my run time for 1 thread is significantly smaller than my run time for 4-16 threads. How can that be? Is it an issue with the time needed to create new threads? Should I change my code or is this to be expected? Originally I thought I could have a racing issue, but I included a private clause, which I think prevents that? My code and run times/ thread are below.
1 thread: .570s
4 threads: 2.63s
8 threads: 1.40s
16 threads:.825s
32 threads: .594s
64 threads: .510s
int matrixProduct(int m, int n, int p, double *A, double *B, double *C){
  int i, j, k;

  for( i = 0 ; i < m*n ; i ++)
    C[i] = 0.0;

  #pragma omp parallel shared(A,B,C) private(i,j,k)
    {
  #pragma omp for schedule(static)
    for( i = 0 ; i < m ; i ++)    {
      for( j = 0 ; j < p ; j ++) {
        for( k = 0 ; k < n ; k ++ ){
          C[k+i*n] += A[j+i*p]*B[k+i*n];
        }
      }
    }
    }
  return 0;
}


texts: Using pumping lemma to prove {a^ib^j | i > j} non-regular

texts:
I'm having issues using the pumping lemma to prove $L_2 = \{a^ib^j \mid i > j \}$   is non-regular. It's obvious to know that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{j's}$

So I've done some digging.
On page 2 here I found a proof. However, it doesn't make sense to me.

Here is the proof, I will list my understandings as we go through the proof:

  Assume by way of contradiction that $L_2\in \mathrm{REG}$, then $L_2$ satisfies
  the conditions of the pumping lemma. Let $p > 0$ be the pumping
  constant. Consider the word $w = a^{p+1}b^p$.

Makes complete sense.

  Clearly $w \in L_2$ and $|w| > p$, so according to the pumping lemma
  there exist $x, y, z ∈ Σ^∗$ such that $w = xyz,$ $ |xy| ≤ p,$ $ |y| >
 0$ and for all $i ≥ 0$ it holds that $xy^iz ∈ L$.

Now if an $i$ is chosen to be $0$, this would conflict with $|y| > 0$? It seems it's using $L$ instead of $L2$. Is there a reasoning?

  Since $|xy| ≤ p$, then $x = a^n, y = a^m$, and $z = a^kb^{p+1}$ such that
   $m + n + k = p$, and $m > 0$.

This makes sense to me, as $z$ is equal to the rest of the $a's$ not in $x$ and $y$ plus all the $b's$.

  We pump with $i = 0$ and
  get the word $xz = a^nz = a^na^kb^{p+1}$. Since $m+n+k = p+1$ and $m >
 0$, then $n+k < p+ 1$.

Now this doesn't make sense to me. Pumping down ridding of $y$ contradicts the $|y| > 0$ rule and how does $m+n+k$ change to now equal $p+1$

  Thus, $xz \notin L_1$, in contradiction to the pumping lemma. So $L_2$ is not
  regular. Note that it is crucial to “pump down” for this language.

If you guys can help me understand this proof, that would be great thanks


texts: My code works, But how do I make this code run in a deterministic time?

texts:
The Problem:
Given 3 inputs Bounce, Ball drop height, and ball view height.

How do I calculate the number of times the observer can see the ball pass.
So my code gives correct output, but it takes a longer time as bounce approaches 1, how do I make it deterministic in nature.

def bouncingBall(h, bounce, window):
    BounceFactor = bounce
    BallDropHeight = h
    ViewerHeight = window
    BounceLeft = h
    BallSeenTimes = 1
    if bounce > 1 or bounce < 0 or window >= h or h ==0:

        return -1
    else:
        while (BounceLeft > ViewerHeight):
            BounceLeft = BounceLeft * BounceFactor
            if (BounceLeft > ViewerHeight):
                BallSeenTimes = BallSeenTimes + 2
            else:
                break
        return BallSeenTimes

I am not looking for code answers, just the direction in which I need to think.
Currently, I think If I could somehow establish a linear relationship and create a function to "guess" the passes it would be faster.


texts: Can we convert any given turing machine to a turing machine with only 2 states? if so, how?

texts:
So i remember reading somewhere that we can convert any turing machine into a turing machine with 2 states (or 3, i don't remember) but there was no proof for it and i couldn't find it either

So my question is :

For every turing machine, what is the minimum number of states that we can have after converting it to this minimal state turing machine?

and what is the properties of this turing machine that we have converted our original turing machine to?is this a standard turing machine or we do this by increasing the number of tapes or...? ( how is this possible?)

What i mean by convert is build a Turing machine which accepts the same language but only with 2 or 3 states


texts: How does one find out whether $N = a^b$ for some $b$?

texts:
I was trying to find out how to find whether $N$ is a perfect power or not for some $a$ and $b$ (so the algorithm should discover that its not a perfect power if its not expressable in the form  $a^b$).

My intuition tells me that for every value of the exponent $b$ we can binary search $a$ in the set $\{ 1,...,N-1 \}$. However, what I am not convinced yet is that this algorithm won't run forever, i.e. that we won't try new values of $b$ forever. Also, if someone has any comments on the correctness of the algorithm I suggested it would be greatly appreciated.


texts: Do real world computers use the Turing Machine mechanism?

texts:
I am a high school student in the twelfth grade. I study high-level programming, and a little bit of basic computer science.

I have recently started to understand what a Turing Machine is. I wanted to ask:

I understand that a Turing Machine is a hypothetical device used to explain the mechanisms of computing.

But is a Turing Machine conceptually the actual very basis of computers? (In the most basic level). Or do real world computing mechanisms and the Turing Machine mechanism (way of calculating things) have very little in common?


texts: What is the difference between decidability and computability?

texts: If they are different, what are the typical problems in each that do not fall on the other category? Or are the mutually exclusive or does one completely capture the other?


texts:
I have been hearing the phrases quasipolynomial, superpolynomial and subexponential.

I think know what quasipolynomial and subexponential is. I believe these are functions respectively of form $n^{\log^c n}$ and $n^{n^{1/c}}$ for some $c>1$.

What does superpolynomial mean?


texts: Why precondition strengtening is sound in Hoare logic

texts:
I have problem with understanding why precondition strengthening is sound rule in Hoare logic. The rule is:

$$
{P \implies Q, \{Q\} C \{X\} } \over {\{P\} C \{X\}}
$$

I really do not understand why precondition in consequence goes in reverse direction that implication works (modus ponens).

I can understand why post-condition weakening works because it follows modus ponens rule but I am no able to understand precondition strengthening.


texts: Adding linear constraint to continuos LP to improve performance

texts:
Consider a standard LP minimization problem of the form

$$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & A x = b\\ & x \geq 0\end{array}$$

Should I expect, on average, an improvement in the number of iterations needed to achieve optimality if adding a (tight enough) constraint of the form $c^\top x \leq m + \varepsilon$ to it? By "tight enough" I mean that $m$ is the optimal value of the problem and $\varepsilon$ is small in some sense.


texts: Is there any way to distinguish between LL(k) and LR(k) grammar?

texts:
I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar.

We also know the facts that every LL grammar is LR that is LL grammar is a proper subset of LR grammar. First one is used in top-down parsing and the second one is used in bottom-up parsing.

But is there any way to so that we can say that a given grammar is LL or LR?


texts: Enumerable disjoint subsets whose union is equal to the union of the sets

texts:
I'm given that two sets, $A$ and $B$ are enumerable. I have to show that there exist subsets $A \supset C$ and $B \supset D$ ($C$ and $D$ also enumerable) such that $C$ and $D$ are disjoint and $A\cup B = C \cup D$. I was thinking to take $A=B=\{0,1\}$ and define $C=\{n : f(n)=1\}$, $D=\{n: f(n)=0\}$.
Do you think this is right?


texts: Existence of d-regular subgraphs in a k-regular graph

texts:
The claim is as follows:
Let's say we have a $k$-regular simple undirected graph $G$ on $n$ vertices. Then, does $G$ then always have a $d$-factor for all $d$ satisfying $1 \le d \lt k$ and $dn$ being even.

I think its true, since we can construct a

$k+1$-regular graph from $G$ by adding $\frac{n}{2}$ edges for even $n$ or
$k+2$-regular graph from $G$ by adding $n$ edges for odd $n$

And the converse for the above.
We can construct a $k$-regular graph on $n$ vertices by

removing $\frac{n}{2}$ edges from a $k+1$-regular graph for even $n$.
removing $n$ edges from a $k+2$-regular graph for odd $n$.

Hence, using the converse argument, we can say that the original claim is true, since from a $k$-regular graph $G$ we can construct

$1$-factor, $2$-factor, ... $k-1$-factor for even $n$ or
$2$-factor, $4$-factor, ... $k-2$-factor for odd $n$

Is my argument correct or is there any flaw in this argument?


texts: Regular expression generating the language $L=\{w: |w|\le 5\}$

texts:
Im trying to find a regular expression to generate the language that has words with length at most 5, over $\Sigma =\{0,1\}$
How can i represent the at most ? I know i can do it if ill just write all the $2^5$ possibilties with 'or' between them. But it seem to me not the right way.
Is it even possible to represent the state : "I've choose 0, 1, or nothing" ?

I can use only the elemntary operators : $\cup , \cdot , ^*$

Also it was easyer to find a NFA that will represent L but the algorithem to get the regex from the aotomton will give me the exponential answer.


texts:
I have the following question. Is the SAT solvers are deterministic?

I mean, for example, about miniSAT and DPLL algorithm. Are they completely deterministic?

If these algorithms will return unSAT it means that certainly the solution does not exist?


texts: How come {ww} isn't regular when {uv | |u|=|v|} is?

texts:
As we know, using the pumping lemma, we can easily prove the language $L = \{ w w \mid w \in \{a,b\}^* \}$ is not a regular language.

However, the language $L_1 = \{ w_1 w_2 \mid |w_1| = |w_2| \}$ is a regular language. Because we can get the DFA like below,

DFA:

--►((even))------a,b---------►(odd)
      ▲                         |
      |--------a,b--------------|

My question is, $L = \{ w w \mid w \in \{a,b\}^* \}$ also has the even length of strings ($|w|=|w|$, definitely), so $L$ still can have some DFA like the one above. How come is it not a regular language?


texts: How to use the Pigeonhole Principle to prove a DFA has a minimum number of states?

texts:
$A = \{w \in \{a, b\}^* | $ 10th character from the end of $w$ is $b\}$
Prove if DFA $M$ has $L(M) = A$ then $M$ has at least 1024 states.

So there's only 2 characters possible at any state, aside from the 10th character, which has to be $b$. Any character after that can be a or b, since we know the 10th character from the end is $b$.
I was told that the Pigeonhole Principle would be used to prove this, as well as contradicting or using the contrapositive was the way to go.
My answer was that if we took a string $w$ with a length of less than the number of states, say 9, then the principle says that a state will have to be repeated. So a string of 10 $b$'s in a row won't reach an accepting state because the path will waste a transition to loop or repeat a state that has been traveled to. Because a string failed when it shouldn't have, that contradicts the language?
I also have a few other reasonings that may work with the Pigeonhole Principle, but I am just wondering if my reasoning makes sense.


texts: Transform unstructured flow charts into structured ones

texts:
Has anyone studied the problem of converting a generic flowchart to a semantically equivalent "structured flowchart" (i.e. one that only uses the 'if' and 'while' block structure)?

I can see this may be relevant to code generation and optimization but I've not been able to find anything on the topic.

Intuitively, I would say that the graph corresponding to a structured flowchart must have no intersecting cycle, if this is not the case some sort of auxiliary variable must be introduced.

In the picture below, for example, the graph for the unstructured flowchart has the two cycle that intersect. In case of nested loops, one would have had one of the two cycle completely contained in the other.

I'm pretty sure that there's much more than this.

Could anyone point me in the right direction?


texts:
I am trying to show that this is Turing Recognizable.

The language A, that is a DTM, T, that halts on a minimum of one input.

My justification is that of course it is because, you just need to check if an accept state is reachable. However, this seems like I am making it trivial.

Is there something larger I am missing?

EDIT: New Idea

Let M be a DTM that does this:

For every string w in the language,
simulate w on T.
if it halts, accept.

The only problem I see with this, is if a string causes it to loop forever, then it will never try the others.


texts: Rule induction principles in Harper's PFPL

texts:
I have a few small questions about section 2.4 ("Rule induction") in Practical Foundations for Programming Languages (p. 19).

(1) In the rule induction principles for nat,

  To show P(a nat) whenever a nat, it is enough to show:
  (1) P(zero nat).
  (2) for every a, if (a nat and) P(a nat), then P(succ(a) nat).

why is the bracketed "(a nat and)" clause necessary (and similarly for tree)?  This seems "natural" - we shouldn't need to prove things about syntactic entities that don't define nats - but doesn't appear in the definition given of property P "respecting the rules" defining nat/tree (also on p. 19), which is how the rule induction principle is defined.  In the proof of Lemma 2.1, the extra "a nat and" part has become part of the definition of the property P - what's going on here?

(2) I don't understand the induction step of Lemma 2.1 (succ(a) nat implies a nat).  If I were doing this proof, I'd just invert the rules for nat right away, or, using Harper's property P, say: If succ(a) is of form succ(b), then by injectivity, a equals b, hence b nat as a nat, but injectivity hasn't been proven yet.  It seems instead that Harper applies the induction hypothesis about a directly to succ(a) - I must be missing something.

(3) In a more naive framework, Lemma 2.3 would just follow from sufficiency of the = nat relation rules ("inversion"), but I don't know how to write down a proof in this style.  Why is induction even needed?

I'm sorry if these questions seem like nitpicking, but Martin-Löf/LF feels very foreign to me.  If I squint and pretend I'm doing everything in a more "traditional" operational semantics, I can read other parts of the book (with slightly different proofs), but I feel I'm missing the point in doing so.

If these questions are too tedious to answer individually, are there other references on doing semantics in this style?


texts: FLP Impossiblity Result assumption of $C_1 = e'(C_0)$

texts:
FLP86's famous proof regarding impossibility of async distributed processes with a single fault assumes in the proof of the third lemma the existence of an event $e'$ such that the neighbor configurations $C_0$ and $C_1$ can be related as

$C_1 = e'(C_0)$.

I don't get how this is possible, as it seems to me like $e'$ carries out a state transition from a 0-valent configuration to a 1-valent configuration. In addition to this being counter intuitive the proof of case 1 of lemma 3 clearly states that any successor of a 0-valent configuration has to be a 0-valent configuration. What am I missing here?


texts:
We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint?

A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$  enter a room. We want to find the index, $i$, of the tallest person in the room. We have one variable for saving that index, which is updated when we see a person who
is taller than the maximum height so far. We want to calculate the average number of times our variable is updated. For simplicity, assume that $p$ is a permutation of $\{1, 2, \dotsc, n\}$

Short answer: it is close to $\ln n$. (i.e: natural logarithm)

How can one solve such a question?


texts: Can you build a solver for a language from a solver for its complement?

texts: If you have a solver for an L in NP do you have enough information to build a solver for co-L in Co-NP? Meaning, is there a procedure that can take you from a solver for one to a solver for another?


texts: Updating the distances matrix after single edge was decreased

texts:
I was reading this question on how to update the distances matrix D of a graph after one edge was decreased, and I don't understand why it works:

The answer suggests that if the an edge (a,b) was modified - then all you have to do is iterate through every edge of the graph, and calculate: D[u][a] + w(a,b) + D[b][v].

My problem is: how do you know that D[u][a] is correct ?

I've drawn this example:

Now D[u][a] = 100
but, when the edge from a to b decreases:

Now D[u][a] should to be changed to 71 but it's not. and when I will calculate D[u][v] I would use a false D[u][a].

What am I missing here ? is the algorithm presented in the answer linked not correct ? or am I ?


texts: Decidability of directed strongly connected graphs

texts:
Consider the problem of determining if a directed graph is strongly connected.
How to phrase it as a language and prove that it's decidable.
My Thoughts :
To think of decidability given a graph I could run DFS on each node and see that all the nodes
are reachable from the original node. So it can be determined if the graph is strongly connected
in polynomial time.
But I am confused about the formal automata definition of decidability. Which says a language is
decidable if there is a Turing machine such that this language is the one exactly accepted by the
Turing machine. Now given the above logic of DFS is that enough to prove decidability
or does one have to build a turing machine ?


texts: Languages A, B ∈ NP-complete such that A⋃B = Σ*

texts: I'm pretty new to complexity theory and it seems like I stuck with this problem. We should find language $B$ such that it accepts any words rejected by $A$ but in that case, it seems that $B$ is a complement of $A$ and therefore $B$ belongs to $coNPC$. What is my mistake? Thank you!


texts: Show that the Laplace smoothing for bigrams is a valid probability distribution

texts: If we consider any smoothing technique like laplace or delta smoothing. Intuitively we can see that the we are stealing from sequences with non zero probablity and re distribute to sequences with zero probablity and there by it should be a probability distribution function. But how do we prove this mathematically say for example laplace smoothing?


texts: L1 sampling for sampling edges of a graph

texts:
I am trying to sample the edges of an undirected graph using weights. The goal is to run a sparsification algorithm on the graph. I see the point that L1 norm is best for sparsification. Can someone tell me how exactly is L1 sampling performed on edges of a graph.

To be more precise with my query, Should we vectorize the indices of the graph and then apply L1 sampling on the sub vectors and perform sparse recovery?(correct me if I am wrong) or is there a better way?


texts: What are the properties of summation with Big Omega? I have been looking online but cannot find any sources on summation with Big Omega, only for Big Oh. For example, my main inquiry is if this statement is true or not, If $a(x) + b(x) ∈ \Omega(c(x))$, then $a(x) ∈ \Omega(c(x))$ or $b(x) ∈ \Omega(c(x))$.


texts:
Does call-by-reference semantics for remote procedure call (RPC) have a real use case?  Why does call-by-reference RPC exist?  Is it useful for anything?  Is there a scenario where call-by-value can't do the job?

In a simple sentence: Do we need to have a (call by reference)-able RPC protocol? if yes, Why?

Background: Call-by-reference can be implemented for RPC.  For instance, one implementation strategy is copy & restore: the value is copied from the client to the server when you make the call, and then copied back afterwards.  There are other ways to implement it as well.


texts: How to go about working the average case run time of this trivial algorithm (and other algorithms)?

texts:
This is a similar algorithm to one I used in a previous question, but I'm trying to illustrate a different problem here.

for (int i = 0; i < numbers.length - 1; i++) {
    for (int j = i + 1; j < numbers.length; j++) {
        if (numbers[i] + numbers[j] == 10) {
            System.out.println(i+" and "+j+" add up to 10!");
            return;
        }
    }
}
System.out.println("None of these numbers add up to 10!");
return;

Basically, I realised, that I have a decent understanding of how to work out the best case run time here. I.e. the first two numbers which are fed in, add up to 10, and therefore our best-case runtime is constant time. Also, I understand that in the worst-case, none of the numbers we provide add up to 10, so we must then iterate through all loops, giving us a quadratic runtime. However, in the slides I was going through (for this particular course) I noticed that I had missed this:

Average case

• Presume that we've just randomly given
integers between 1 and 9 as input in
numbers to our previous example

• Exercise: Work out the average running time

I realise I don't have the first clue as to how to go about calculating average case run-time. I'm not asking for the answer to: "what is the average-case runtime for this algorithm?", what I need to know is, how do you work something like this out?


texts: Conditionals with normal order evaluation

texts:
From what I've read, conditionals (like the cond statement in lisp) do not need to be primitive if normal order evaluation is used.

Using lambda calculus and normal order evaluation, how can you emulate if and cond statements?

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))

(if <predicate> <consequent> <alternative>)

References to SICP are welcome, though a simpler example would be helpful.

(Definitions of cond and if taken from Section 1.1.6 of SICP)


texts: The evolution of the term "recursive" from Goedel to Church to present day

texts:
I'm currently studying some of the history of computation / computability, in the early days known as recursion theory.

I see Goedel's definition of recursive functions seems significant in his paper, and Church uses his own definition of recursive functions (in particular, primitive recursive functions).

Wikipedia talks about primitive recursive functions and seems to follow Church's definition, but compares it to u-recursive functions as well.

Other definitions online don't seem to correspond with Church's or Goedel's definition.

Can anyone clarify for me exactly who defined "recursion" in what way. Why it was defined that way. How it evolved and why it evolved.

It would very much help me join the dots in this difficult quest towards understanding the foundations of computer science.


texts: Logic behind O(n) solution for 'Maximum length sub-array having given sum'

texts:
I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum (negative numbers included),

I read that it can be solved in O(n) time complexity and O(n) space complexity, but the logic behind it is still unclear to me. I have read this solution:

Initialize sum = 0 and maxLen = 0.
Create a hash table having (sum, index) tuples.
For i = 0 to n - 1, perform the following steps:

Accumulate arr[i] to sum.
If sum == k, update maxLen = i + 1.
Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.
Check if (sum - k) is present in the hash table or not. If present, then obtain index of (sum - k) from the hash table as index. Now check if maxLen < (i - index), then update maxLen = (i - index).
Return maxLen.

Examples:

Input : arr[] = { 10, 5, 2, 7, 1, 9 }, k = 15
Output : 4
 The sub-array is {5, 2, 7, 1}.

Input : arr[] = {-5, 8, -14, 2, 4, 12}, k = -5
Output : 5

Taken from this link: https://www.geeksforgeeks.org/longest-sub-array-sum-k/

Could someone please elaborate on the solution provided for this problem?


texts: Transformation of a Product Buchi Game to a Parity Game

texts: Is there anyway to express a Product Buchi game as a parity game? There is no stochasticity in my original turn-based game and a Deterministic Buchi Automaton is constructed for LTL specifications.


texts:
First of; this is my first computer science problem, so bear with me. That said:

I'm trying to create a planning application for my summer camp (sailing school) with the goal to put everyone with different people every day (when possible).

Variables defaults

Group size: 4 (max. people per boat)
Total people: 20
Days: 5

Day 1

| Group 1 | Group 2 | Group 3 | Group 4 | Group 5 |
|---------|---------|---------|---------|---------|
| 1       | 5       | 9       | 13      | 17      |
| 2       | 6       | 10      | 14      | 18      |
| 3       | 7       | 11      | 15      | 19      |
| 4       | 8       | 12      | 16      | 20      |

Goal

Calculate an optimized roster for each of the remaining days

| Group 1 | Group 2 | Group 3 | Group 4 | Group 5 |
|---------|---------|---------|---------|---------|
| ?       | ?       | ?       | ?       | ?       |
| ?       | ?       | ?       | ?       | ?       |
| ?       | ?       | ?       | ?       | ?       |
| ?       | ?       | ?       | ?       | ?       |

People need to be spread over the boats. (If there are 17 people, no group can be size 1)
Where everyone is with a completely new group of people everyday, if possible.
Where everyone is in a different group, when possible.

What i've done

I made a script that does the following (without knowledge of any algoritm):

for (everyday) :
    reset table & people
    while (people > 0) :
        order people by:
            - currently placed people who've been in the same group
        pick the one with the most matches
        order groups by:
            - skip full groups
            - number of people from previous groups (-10 per person)
            - has been in this group (-1 per group)
            - current groupsize (-1 per person in group)
        put the one in the highest scoring group

I got pretty good results with using this, but with some fiddling and trying some other rules I found that shuffling the people before the ordering of said people who give me sometimes better/worse results. So...

I was wondering if my approach is any good?
Is this a NP-complete or NP-hard problem or neither? Is it dependant on the day the roster is made?
Is it even possible to eliminate the randomness and create an algoritm which always returns the best result?
Do you know of some similar problems/examples where I can learn from? I found the list of NP-complete problems, but I don't know which one really compares to my case.

Cheers,
Ties


texts: Asymptotics of of $T(n) = n + T(n - \sqrt{n})$

texts:
What is the asymptotic rate of growth of the following recurrence?
$$ T(n) = n + T(n - \sqrt{n}). $$
Since I cannot use the Master's Theorem here, I could not figure it out the answer. My initial guess is $n^{3/2}$, but I'm not sure.
Can anyone help me? What are the big-O and big-Omega complexities here?


texts: When is relation in 3NF but not in BCNF?

texts:
A book by Korth et al. defines BCNF as follows:

  A relation schema $R$ is in BCNF with respect to a set F of functional dependencies if, for all functional dependencies in $F^+$ of the form $α→β$, where  $α⊆R$ and $β⊆R$, at least one of the following holds:

  $α→β$ is a trivial functional dependency (that is, $β⊆α$).
  $α$ is a superkey for schema $R$.

It then defines 3NF as follows:

  A relation schema $R$ is in third normal form with respect to a set $F$ of functional dependencies if, for all functional dependencies in $F^+$ of the form $α→β$, where $α⊆R$ and $β⊆R$, at least one of the following holds:

  $α→β$ is a trivial functional dependency.
  $α$ is a superkey for $R$.
  Each attribute $A$ in $β-α$ is contained in a candidate key for $R$

So 3NF definition adds an additional 3rd condition to the BCNF definition: "Each attribute $A$ in $β-α$ is contained in a candidate key for $R$". I think we can correctly interpret this condition as $β-α$ are key attributes.

Now I was thinking about which relations are in 3NF but not in BCNF. Clearly the relation which contains the dependency that satisfies this 3rd condition can be in 3NF but not in BCNF.

The book gives following example:

  The schema dept_advisor : {s_ID, i_ID, dept_name}
  with FDs

  i_ID $→$ dept_name
  s_ID, dept_name $→$ i_ID

  Here, first FD is non trivial. Also i_ID is not a super key. Hence schema is not in BCNF. Now dept_name is a part of the candidate key (s_ID,dept_name). Hence, dept_advisor is in 3NF.

Now I came across following statement on this site, which I think I have also read in the book:

  3NF states that all data in a table must depend only on that table’s "primary key", and not on any other field in the table. At first glance it would seem that BCNF and 3NF are the same thing. However, in some rare cases it does happen that a 3NF table is not BCNF-compliant. This may happen in tables with two or more overlapping composite candidate keys.

I have two doubts:

What does it imply by using "primary key" in first sentence. Cant there be two or more candidate keys in a 3NF relation with some FDs involving one CK and remaining FDs involving other CK. This must not be the case due to the last sentence in above paragraph, which is source of 2nd doubt below. But then why use "primary key"? Should the sentence rather be "3NF states that all data in a table must depend only on that table’s candidate keys or better to say superkey"?
From definitions of 3NF and BCNF, what I felt is the relation which is in 3NF but not in BCNF should be the one having FD following 3rd condition of 3NF definition and there can be no other situation which can lead to non-BCNF but 3NF relation. If so, how is "two or more overlapping composite candidate keys" (as stated in last sentence of above paragraph) is equivalent to/lead to such FD? Or to put in different way, where are overlapping composite candidate keys in above example of dept_advisor?

Am I thinking stupidly? Am I giving unnecessary importance to these points and are in fact senseless?


texts: K-nearest along ray in large point cloud

texts:
Are there any well-known data structures known that can handle the following (need to scope whether something is possible):

Return the k-closest points to a ray shot through the cloud.
Allows quick updates of point locations (basically every point is moved every 500000 queries or so at which point around 500000 old points are removed and the same number added).

In this case the number of points in the cloud will be approximately 3.5 million. The application is in 3D graphics.


texts: Check if an array is a substring of another array

texts:
Given two sequences $A$ and $B$,
we want to check if $A$ is a subsequence of $B$ where the elements of $A$ appear in $B$ consecutively and in the same order.

Example 1.

input: $A = (4 , 6 , -5), B = (2 , 4 , 6 , -5 , 4)$,
output: Yes

Example 2.

input: $A = (2 , 6 , 4), B = (2 , 4 , 6 , -5 , 3)$,
output: No — although $B$ contains all the elements in $A$,
the order is not correct.

Example 3.

input: $A = (2 , 6 , 4), B = (2 , 3 , 6 , -5 , 4)$,
output: No — although $B$ contains all the elements of $A$ in the correct order, they are not consecutive.

Let $n$ and $m$ be the size of $A$ and $B$.

How fast can we solve this problem?

What I have tried

I have an algorithm that runs in time $O(nm)$ as follows:

  go over elements of A,
  for each of them go over elements of B and see if we can find a matching element,
  which is after the matching element for the previous element of A.


texts: Terminology for a partially unlinked doubly linked list?

texts:
Let's say you have a standard doubly link list implementation:

struct List {
    int Number;
    struct List *blink;
    struct List *flink;
};

and that you have the following list:

1 <--> 2 <--> 3 <--> 4 <--> 5

Now, in my case, I've been using the flink as a terminator of sorts, and unlinking nodes in a single direction:

1 <--> 2 <--> 3 <--| 4 <--> 5

So 3's flink is null, but 4's blink points to 3.

(Mildly unrelated, I've been doing this to allow for quick modification and restoration of linked lists, and have things like:

1 <--> 2 <--| 3 <--> 4 <--> 5
         <--> 6 <--| 7 <--> 8
                <--> 9 <--> 10 <--> 11

to build a list of 1 2 6 9 10 11. I've been using this for instances where I need data to persist that would normally (as far as my program is concerned) be destroyed when doing a depth-first traversal. Think of it almost as a stack that knows how to restore itself to a previous state.)

My question is really just "does this type of operation/technique have a well defined name?" I've been calling it "shearing", but if there's a real name that'd be nice to know.


texts: How hard is recovering a binary matrix from its check sums?

texts:
I am interested in combinatorial (worst-case) one-way functions. I came across this problem which may be related to coding theory problems (I am not an expert in coding theory).

INPUT: Two vectors $R_{n*1}$ and $C_{1*n}$.

QUESTION: Is there a binary matrix $A_{n*n}$ such that vector $R$ contains the parity check of each row in $A$ and vector $C$ contains the parity check of each column in $A$.

The parity check of a row (or column) is the sum of all bits Mod 2 (XOR operation).

  What is the time complexity of this problem? Is it NP-complete? Is it efficiently solvable? Is this a known problem in coding theory?

Also, it is interesting to know the time-complexity of a variant in which vectors $R$ and $C$ contains the integer sum of the one's in each row and column in $A$.

EDIT: It is interesting to note that the Sum problem becomes $NP$-complete if the directed graph is required to be acyclic (see the link in Yuval's answer).


texts: Possible to use Master theorem? $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$

texts:
The master theorem can be used in case of a recurrence relation of the form $T(n) = aT(\frac{n}{b}) + g(n)$

But is it possible to use the master theorem for recurrence relations of the form $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$?


texts:
My master’s dissertation subject is to analyze and implement an algorithm that would sample thermal images from camera with different frequency rates to optimize database size and processing power.
Is anyone aware of any publication related to this subject? It seems that I cannot find any information on sampling patterns for raw 2d data streams, nor algorithms that would detect or calculate if the image differs enough from previous ones and is worth capturing.


texts:
I'm writing my Bsc thesis about type systems of various languages and I want to have a short section about assembly languages. Initially I thought I'll bring up assembly as a counter example to languages with advanced type systems. My goal was to explore the reasons why assembly omits most (all?) type system features but eventually I found papers about typed assembly languages and I started to get confused.
So here are my questions:

Can we say that assembly is generally untyped? If so, what is the reason we don't have assemblers with advanced types and type checkers?
Arguments for having a typed assembly language?

Here is a list of papers about typed assembly languages from the end of the last century: http://www.cs.cornell.edu/talc/papers.html.
Links to other papers are highly appreciated!


texts:
$\oplus P$ is low for itself ($\oplus P^{\oplus P}=\oplus P$).

Are there other complexity classes $\mathcal D$ that satisfy $\mathcal D^{\oplus P}=\oplus P$?
Are there complexity classes $\mathcal C$ that satisfy $\mathcal C^{\oplus P}=\mathcal C$?


texts: Does checking the middle bit of an input require a log(n) space pointer? (Reusing space)

texts:
Let n be an even integer.

Let I be an input of length n.

Positions start at 0: the first bit is bit 0. The second bit is bit 1. etc.

The decision problem is, "Is bit n/2 equal to 1"?

The input is on a tape.

We have a single pointer to the input. We may move the pointer left or right. We cannot overwrite the input tape.

We have a single working-memory tape to compute with. We have a single pointer to it. We may write a 0 or a 1. We may move the pointer left or right. We may not move to the left of, or overwrite the start symbol of the working-memory tape. The working-memory tape is initialized to either the start symbol or immediately to the right.

Space-complexity is the position of the largest cell we write to. This way we "reuse" space.[1]

One way to decide the problem is with a counter of length O(log(n)): Initialize to 0's, then increment until the counter equals n/2, then check the bit.

That takes O(log(n)) space.

Can we do better? Or is O(log(n)) the best space-complexity we can do?

[1] If space complexity was just the total in-use space at any given point in time, we could "move around" the space we're using, using a larger total range of space, but only a smaller portion at any point in time. Defining space as the max position keeps us from "moving around" the space we're using.


texts: Suppose I have a hash table which stores the some strings. Let the index/key of this hash table be the length of the string. what is the time complexity of checking if the string of length K exists in your hashtable? is it O(1) or O(k) ?


texts:
I have a directed acyclic graph where edge (A,B) means that vertex A depends on vertex B.

Vertex deletions have the following restrictions:

When vertex B is removed, all dependent vertexes should also be removed.
When vertex  A is removed and vertex A was the only vertex that depends on B, vertex B should also be removed.

I need to list the vertixes which are deleted when

Vertex B is deleted. My solution is B, E and J because

B -- deleted
E -- because of condition 2, B is removed and B was the only vertex that depends on E
J -- because of condition 2

Vertex C is deleted. My solution is C, F, A, G, ... ?

C -- deleted
F -- because of condition 2 (C is the only vertex to F)
A -- condition 1 (depends on C)
G -- condition 2 (C is the only vertex to G)
I think here the process goes on and cascades. Is that correct?

What could be an algorithm for such vertexes dependency network which allows for the vertex deletion?

PS: this is an old exam exercise (2008/09); I use it as exercise for my one middle of June.


texts: Decomposition of graphs that uses centers

texts:
Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason (other than the potentially large size of centers) why such a notion isn't fruitful (e.g. subsumed by other notion)?

I'm looking for something similar to this:

Let $G=(V,E)$ be an undirected graph. Its central decomposition is

If $G$ is not connected: the set of central decompositions of its connected components.
If $G$ is self-centered (radius equals diameter): $G$
If $G$ is connected and not self-centered and its center is $C$: the pair $(I,O)$ where $I$ is the central decomposition of $G[C]$ and $O$ is the central decomposition of $G[V\setminus C]$ (induced subgraphs of center and its complement)

Its central width shall be the size of largest self-centered graph which appears in its central decomposition.

The notion may also use other concepts (like complements, trees etc.), but it should use centers recursively. There is no need for uniqueness.

I'm not looking for e.g. path distance decompositions (see here) where the root is the center, i.e. a map $d$ of a path $\{p_0,\dots,p_k\}$ to $V$ where $d(p_i)=\{v\in V\mid \min_{c \in C}\mathrm{dist}(v,c) = i\}$ ($C$ being the center of $G$).


texts: How to calculate the average depth of a binary tree?

texts: My professor has said that the average depth of all possible binary trees which can be formed with $n$ nodes would be $O(\sqrt n)$ and has assigned the proof of this as homework. How do I approach this problem?


texts: Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS

texts:
I was going through section of Breadth First Search of the text Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding a statement in the proof below which I have marked with $\dagger$

Theorem: (Correctness of breadth-first search)
Let $G = (V, E)$ be a directed or undirected graph, and suppose that $BFS$ is run on $G$ from a given source vertex $s \in V$. Then, during its execution, $BFS$ discovers every vertex $v \in V$ that is reachable from the source $s$, and upon termination, $d[v] = \delta(s, v)$ for all $v \in V$. Moreover, for any vertex $v \neq s$ that is reachable from $s$, one of the shortest paths from $s$ to $v$ is a shortest path from $s$ to $\pi[v]$ followed by the edge $(\pi[v], v)$.
$\left[ \delta(s,v) \rightarrow \text{Length of the shortest path from s to v}\\ d[v]\rightarrow \text{distance assigned to vertex $v$ from $s$ by BFS}\\\pi[v]\rightarrow \text{Predecessor of $v$ in the path from $s$ to $v$ in the BFS}\right]$

Proof:
Assume, for the purpose of contradiction, that some vertex receives a $d$ value not equal to its shortest path distance. Let $v$ be the vertex with minimum $\delta(s, v)$ that receives such an incorrect $d$ value; clearly $v \neq s$. We know $d[v] \geq \delta(s, v)$, and thus we have that $d[v] > \delta(s, v)$. Vertex $v$ must be reachable from $s$, for if it is not, then $\delta(s, v) = \infty \geq d[v]$. Let $u$ be the vertex immediately preceding $v$ on a shortest path from $s$ to $v$, so that $\delta(s, v) = \delta(s, u) + 1$. Because $\delta(s, u) < \delta(s, v)$, and because of how we chose $v$ , we have $d[u] = \delta(s, u)$$^\dagger$. Putting these properties together, we have
$d[v] > \delta(s, v) = \delta(s, u) + 1 = d[u] + 1 $
(The proof then continues, but I do not include the rest here...)

I could not understand the reasoning behind the statement marked with $\dagger$, $\text{"because of how we chose $v$ , we have $d[u] = \delta(s, u)$"}$


texts: Does an array count as a primitive operation when it is used as an argument in a function call?

texts:
Say I have
return A[n-1] + Sum(A, n - 2).
I counted the following primitive operations:

return A[n-2] + Sum(A, n - 2)
   1    2 3   4  5  6   7

I know accessing a certain index in A counts as 1 primitive operation, but I am not sure about A in the function call. Did I count the right number of operations?


texts: Find xor sum of all pairs raised to power of 3

texts:
We are given array $A$ of $N$ integers each in the range $1 \leq A_i \leq 2^{30}$, that is we can write each integer with at most 30 bits. The target is to compute $\sum_{1\leq i \leq N,1\leq j<i} ( A_i \text { xor } A_j )^X$. $X$ is either 2 or 3. $N$ can be up to $50000$.

I know that this can be solved in $O(N^2)$ but I was wondering if we can fast this calculation since this is pretty slow for big values of $N$. Are there any properties of xor that can be used to speed up calculations.


texts:
Let a non-deterministic machine have at most $2^{t+1}-1$ accepting paths (highest significant bit position is $t$ and lowest significant bit position is $1$).
I want to decide if the number of accepting paths $N_{accept}$ is $0$ or $>0$.
I can ask a $\oplus P$ oracle to decide if $2^t|N_{accept}$ and $2^{t+1}|N_{accept}$ as $MOD_{2^m}P=MOD_2P$ by https://complexityzoo.net/Complexity_Zoo:M#modkp.
There are three different scenarios

$2^t|N_{accept}$ and $2^{t+1}|N_{accept}$ in which case $N_{accept}=0$.

$2^t|N_{accept}$ and $2^{t+1}\nmid N_{accept}$ in which case $N_{accept}=2^t$.

$2^t\nmid N_{accept}$ and $2^{t+1}\nmid N_{accept}$ in which case $1\leq N_{accept}\leq2^t-1$.

So $N_{accept}=0\iff\oplus P$ oracle accepts twice.
Why would the above not place $coNP$ in $\oplus P$ or at least $NP^{\oplus P}$?


texts: Prove that the complement of  $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties

texts:
I want to prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties.

I understand pumping lemma can be used to prove that $\{0^n1^n \mid n \geq{} 0\}$ is not a regular language. I also understand regular languages are closed under complement operation. However, does that also imply that a non-regular language's complement is also non-regular?


texts: How much math background do you need to understand how category theory is applied to Haskell?

texts: Basically, how much math background do you need to understand how category theory is applied to Haskell? If you already have mathematical maturity, can you jump right into it, or should you be familiar with certain subjects in algebra?


texts: Calculating cache memory based on LRU algorithm

texts:
Assuming i have 4 blocks of cache memory, Using the LRU (Least Recently Used)
replacement algorithm on this following sequence of access to memory blocks: 1 2 3 4 5 2 5 4 1 5 2 3 :

1   2   3   4   5   2   5   4   1   5   2   3

1   1   1   1   5   5   5   5   5   5   5   5
    2   2   2   2   2   2   2   2   2   2   2
        3   3   3   3   3   3   1   1   1   1
            4   4   4   4   4   4   4   4   3

So in the end, the cache memory will contains this memory blocks : "5 2 1 3"

But the correct answer is "1 5 2 3"

Please tell me what am I doing wrong here!


texts: P-complete problem due to logspace reductions. What does it mean?

texts:
Prove that problem $A$ is complete in $P$ due to reductions
  computed in logarythmic space

How to understand this statement ? What should be shown ? For me:
1. $A$ is in $P$.
2. Each problem  in $P$ can be reduced in logspace to $A$

Can I use transitivity of logspace in this exercise  ?


texts: What's the relationship between "semantic type soundness" and "functional correctness"?

texts:
In the Milner Award lecture "The Type Soundness Theorem That You Really Want to Prove (and now you can)" and related Sigplan blog post (with collaborators), Derek Dreyer argues that semantic soundness is an important thing worth proving.
In the questions section, Adam Chlipala asked how to trade off complexity between proving soundness of semantic types and functional correctness, and Dreyer unfortunately said "let's take this offline," so I don't know what the answer is.
Is the answer "semantic type soundness is something to prove about a programming language, but functional correctness something one proves of a program"?
I'm still a bit confused, though, because then someone asked a follow-up question about how semantic type soundness could fail to hold. Dreyer's answer was that if someone were to add a covfefe rule that flipped an arbitrary int to 0, it could trigger someone's assertion that under certain conditions a given int is never 0. So this makes it sound like soundness proofs for semantic types do involve the details of particular programs.
In addition to an answer to Adam Chlipala's question, it would be helpful to have some simple reference for what "semantic type soundness" means - the blog post doesn't really define it, and the closest paper I could find was the RustBelt paper which only discusses "semantic type soundness" in the context of a Rust MIR-like language and Iris, but I couldn't find a more general definition.


texts:
I'm having difficulties with an exercise in a theoretical CS class.
The problem is:

let $L_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast one "a".

What is the CFG that creates $L_{2}$?

I'm struggling since 2h... I've found out that for example "abba" is not in the language, but to write it formally is quite difficult. Help would be much appreciated.


texts: Why no context switch is required in case of spinlock in operating systems?

texts: I have a query regarding the fact that how Spinlocks are advantageous in terms of context switching ?


texts: Terminology for Digitally Interpretting Environment

texts:
I am looking into coding a program that can Analyse an image and identify objects in that environment (incl their depth and contours/shape).

What is the term for this? Is there a term or area of expertise for this? 'Computer Visualisation' is too broad a term I believe. Maybe Computer Vision and Pattern Recognition (CVPR)? Object Detection? Environment Analysis?

A real world example of what I am looking to develop; autonomous cars with software that can identify and classify objects in its path (pedestrians, curb, centre line, cars, etc.). I am most likely going to use OpenCV, code in C++ and the video stream will come from a cheap drone camera. The drone wont have an infrared/ultra violet hardware component so detecting depth will need to be performed using alternate methods - maybe there are image processing algorithms that can provide a crude idea of the depth of objects.


texts: Why does Feistel encryption algorithm  encode half block every time? What would happen if the entire block is encrypted in each step?


texts: Finding the best combinations between items of 2 arrays in a sequential manner

texts:
I'm reposting this because people found the last description to be too hard to follow.

The data unit I'm working with is a pair of 2 numbers. The numbers can be any integer that is bigger than 0. Example: [X, Y]
The input is 2 arrays of these pairs, each array can have any length. Example:  A = {[1, 2], [3, 2], [5, 1]}  B = {[2, 3], [4, 5], [5, 3]}
If I combine 2 pairs, one from each array, I get a new pair like this: [X1, Y1] + [X2, Y2] = [X1 + X2, Y1 + Y2]
The output is a result of all combinations between the elements of the 2 input's where each element is the "best" and is ordered as ascending by Y

What "best" means in this case is that given [X, Y],

this pair would have the highest or equal to highest X compared to all the other pairs that might have the same Y Example:
[2, 2], [2, 2],[1, 2]
it cannot have an X equal or lower than the maximum of any other pair that has a lower Y Example: [2, 1], [4, 2],[2, 4]

To illustrate how the output can be reached

Lets take this example input:  A = {[1, 2], [3, 2], [5, 1]}  B = {[2, 3], [4, 5], [5, 3]}
First we combine every item in A with every item in B
A[1] + B[1] = [3, 5], A[1] + B[2] = [5, 7], A[1] + B[3] = [6, 5]
A[2] + B[1] = [5, 5], A[2] + B[2] = [7, 7], A[2] + B[3] = [8, 5]
A[3] + B[1] = [7, 4], A[3] + B[2] = [9, 6], A[3] + B[3] = [10, 4]
Next we order the combinations by Y
[7, 4], [10, 4], [3, 5], [6, 5], [5, 5], [8, 5], [9, 6], [5, 7], [7, 7]
Filter the combinations by the rules described above  [10, 4]

So in this example, the output is an array with the length of 1 because all other pairs with Y of 4 have lower X and all other pairs with Y > 4 have equal or lower X.

I didn't include it in the example because its not necessary but the process can be optimized by prefiltering A and B by the same rules.

Now to my problem: I'm not dealing with arrays with the length of 3 but rather several hundred and the input count isn't 2 but 5+, as you can imagine, this process can be nested like this: result5 = process(process(process(process(A, B), C), D, E)

So in practice, the potential memory use is A.size * B.size * C.size * D.size * E.size.. which is a lot more than fits in the 20something kB i have available.

What I'm looking for is an algorithm that will fetch me the same results, in the same order, one by one. The fetches will be sequential and will start from 0 so I think any algorithm that can produce all the results in the right order without sorting in the end can be modified for this. Does anybody know how this could be achieved?


texts: Electrical resistance of expander graphs

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


texts: How would I write an if-statement in continuation passing style without an if-statement?

texts:
Using continuation passing style, many common language constructs can be written in a simple language with recursion, such as loops (using trampolining), exceptions, generators and even function returns. I have found numerous examples of other language constructs, but all examples I have seen use if-statements directly. Noting the power of CPS, I got curious: Can one write an if-statement in CPS without using an if-statement directly?

The naive attempt would be something along these lines:

if_cps(condition, true_body, false_body, current_continuation)
{
    if(condition) true_body(current_continuation);
    else false_body(current_continuation);
}

but obviously this is a failure, since I used an if-statement directly.