texts: What's wrong with my pumping lemma proof?

texts:
The language $L = \{0^{2n} \space |\space n \ge 0 \}$ is obviously regular – for example, it matches the regular expression $(00)^*$. But the following pumping lemma argument seems to show it's not regular. What's gone wrong?

I've found a way of splitting an input $s$ as $xyz$ satisfying the requirements of the pumping lemma but it's not true that $xy^iz\in L$ for all $i$. Doesn't that mean the language isn't regular?

In more detail, the pumping lemma for regular languages says that, if a language $L$ is regular, there exists pumping length $p \ge 1$ such that any string $s\in L$ with $|s|> p$ can be written as $s = xyz$ such that:

$\lvert y \rvert \ge 1$
$\lvert xy \rvert \le p$
$xy^iz\in L$ for all $i \ge 0$.

So, let's take $s = 0^{2p}$ and write it as $s=\epsilon\, 0 \, 0^{2p-1}$ (i.e., $x = \epsilon$, $y = 0$, $z = 0^{2p-1}$). This satisfies 1. and 2. But, taking $i=0$, we get $xy^iz = \epsilon\, 0^0\,0^{2p-1} = 0^{2p-1}$, which isn't in $L$ because its length is odd. So it looks like the language isn't regular after all.

This is intended as a reference question illustrating a common mistake in the use of the pumping lemma for regular langauges. Thanks to Ariel for spotting the issue in the original version of the question.


texts: When does strong duality fail in linear programming? I have considered the case when both primal and dual solutions are infeasible, but then there are no optimal solutions at all.


texts:
We have two integers $z, k$

We form a sequence now of first z natural numbers. i.e. $1, 2, 3, 4, \ldots z$.

Now we have to find total number of permutations of this sequence such that the sum of any two adjacent numbers is $ \le k$

( $z \leq 10^6$, $\;\;z < k < 2*z$ )

Here is what I have been able to think untill now. If k=2*z-1, the answer is z!

Now if we reduce the value of k to 2*z-2, then we take the highest pair as a group and permute with rest of the elements, we subtract this value from the previous case of k=2*z-1

i.e. dp(z,k)= z! for k=2*z-1. and dp(z,k-1)=dp(z,k)-(z-1)!*2 for k=2*z-2.

I want to know if I am going in the right direction. Any help on the closed form would be good.


texts:
I just started Unix System Programming with Standard ML and starting on page 22 Shipman begins to explain a pure functional way of avoiding the constant state changes of typing at a keyboard:

  A lazy stream is an infinite list of values that is computed lazily.
  The stream of keystrokes that a user presses on the keyboard can be
  represented as an infinite (or arbitrarily long) list of all of the
  keystrokes that the user is ever going to press. You get the next
  keystroke by taking the head element of the stream and saving the
  remainder. Since the head is only computed lazily, on demand, this
  will result in a call to the operating system to get the next
  keystroke. What’s special about the lazy stream approach is that you
  can treat the entire stream as a value and pass it around in your
  program. You can pass it as an argument to a function or save the
  stream in a data structure. You can write functions that operate on
  the stream as a whole. You can write a word scanner as a function,
  toWords, that transforms a stream of characters into a stream of
  words. A program to obtain the next 100 words from the standard input
  might look something like apply show (take 100 (toWords stdIn)) where
  stdIn is the input stream and take n is a function that returns the
  first n elements in a list. The show function is applied to each word
  to print it out. The program is just the simple composition of the
  functions. Lazy evaluation ensures that this program is equivalent to
  the set of nested loops that you would write for this in an [imperative]
  program. This is programming at a much higher level than you typically
  get with [imperative] languages.

I take it he doesn't mean just a list of the 26 letters of the alphabet, rather, something more like every possible word and combination thereof, i.e., similar to the theoretical possibility of finding yours and everyone's birthday if you look hard enough in the irrational never-repeating infinite stream of $\pi$ places. That is, somewhere in the infinite series of $\pi$ decimal places is your birthday mmddyyyy-style. Is this in fact what is meant here? Also, is this in any way related to infinite recursion?

In a similar vein, I once was told that no functional language is truly pure, and he gave the example of a function that "goes out" and gets the exact time from an atomic clock. Is this the same sort of issue, where, e.g., an infinite list of possible times is available for a list operation?


texts: Is there ANY compression type that can compress a file, and then that compressed file can be searched without uncompressing the file?


texts: Central Trinomial Coefficients best time complexity

texts:
What is the fastest known time complexity for computing central trinomial coefficients?
Let $C_n=1,1,3,7,19,51,...$ (OEIS A002426) denote the coefficient of $x^n$ in $(x^2+x+1)^n$ starting at $n=0$.
It can be shown that, if $n$ is prime, then $C_n=1 \pmod n$, because by the binomial theorem
$$(x + y)^n=\sum_{k=0}^{n} \binom{n}{k}y^kx^{n-k}=x^n+y^n\pmod n$$ so that
$$(x^2+x+1)^n = x^2+x+1\pmod n$$
follows.
The computational complexity problem I am aiming on solving is, given a large integer $n$ (say, about RSA size), I would like to verify that the congruence
$C_n=1\pmod n$
in polynomial time analogous to how $x^n=x \pmod n$ can be computed using binary exponentiation.
Thanks for help.


texts: If a language consists of an NP and coNP question, do we have to place it in P^NP^NP?

texts: If $x \in L$ only if $x \in A$ and $x \in B$, where A is an NP problem and B is a coNP problem, I cannot place $L \in NP$ or $L \in coNP$ without implying that NP = coNP right?


texts: Correctness of proof by induction for proving correctness of polynomial evaluation algorithm

texts:
This excercise is from The Algorithm Design Manual by Skiena:

My solution is this:

We will attempt a proof by induction.

First, prove that the algorithm is correct for $n = 1$ :

$n = 1$ means that $p$ will be set to $a_1$. Then, the for loop will execute once with $i = 0$, setting $p$ to $a_1x + a_0$ and returning that value, which is correct for any $x$.
Now let's assume that the algorithm returns the correct value for $n=k$. This means that when $n=k$, the function will return $a_kx^k+a_{k-1}x^{k-1}+...+a_1x+a_0$. This is done in the function by setting the first $p$ to $a_k$ and then iterating over the for loop from k-1 to 0.
Now to prove that if $n=k$ yields a correct answer, so does $n=k+1$:

Let's follow the code execution for $n=k+1$. In the first row, $p$ is set to $a_{k+1}$. Then, in the first execution of the for loop, we have $i=k$ and we set $p$ to $a_{k+1}x+a_k$. After that, we have from k-1 to 0 iterations left, which is the total amount of iterations for $n=k$. $n=k$ gave us $a_kx^k+a_{k-1}x^{k-1}+...+a_1x+a_0$ with the first $p$ set to $a_k$ and from k-1 to 0 iterations. Now we have the same thing, but the first $p$ is set to $a_{k+1}x+a_k$. We can therefore substitute this into the function result for $n=k$: $(a_{k+1}x+a_k)x^k+a_{k-1}x^{k-1}+...+a_1x+a_0=a_{k+1}x^{k+1}+a_kx^k+...+a_1x+a_0$, which is the correct result. We have thus proven, by induction, that the algorithm is correct for any $n\geq1$.

Is this correct? I'm particularly unsure about the substitution of $a_{k+1}x+a_k$ into the function result for $n=k$, is this substitution correct?


texts:
I came across the following problem in my complexity-theory course:

Given a set of numbers $A := \{a_1, \dots, a_n\} \subset_{\mathrm{finite}} \mathbb{N}$ and a number $b$ also in $\mathbb{N}$ such that the following condition applies: $a_i$ divides $a_{i+1}$ for all $i < n$ and $a_i < a_{i+1}$. Prove that this special case of subset-sum is decidable in P.

Due to the given condition, $b$ has to be a multiple of the first $a \neq 1$. Taking $a_1 \neq 1: b = a_1 \cdot x$. Finding this x takes me back to the subset-sum problem though which is surely not in P.

Any help would be appreciated.


texts: Is there any official terminology about something like double quotes "" grammar?

texts:
In many programming language string is a token.
For example:
 token               ::= '"' string
                       | digit nat

 string              ::= char string
                       | '"'

 nat                 ::= digit nat
                       | ϵ

This is a LL(1) grammar for some programming language's toke grammar.
When parsing a string, there is no need to check follow set, because there is a " at the end of each string.
Comparing with nat, string is more easy to parse.
My question is
Is there any official terminology about this kind of grammar?
Thanks.

Editing:
There was some mistake in the original grammar, thanks @rici for pointing out my mistakes.


texts:
I'm applying for a doctoral training in Cyber Security, although I come from a maths background. I've been told that my background meets the entry criteria, although for my application I would like to be able to say that I've looked into Cyber Security it at least some detail.

Given that I will have very little time to do any reading before applying (about 2 weeks), what would you recommend I read? A few chapters from an academic text, or a popular book on the topic?

Specific book/paper recommendations would be appreciated.


texts: Trying to understand the Gilmore-Lawler lower bound

texts:
For a class project we're developing a software that solves a common optimisation problem. After some research we've found out that our problem is called QAP (Quadratic Asssignment Problem) and the algorithm that is commonly used is Branch and Bound. I understand the basics of the problem and I see the need of a lower bound to compute the sollution. I came up with a trivial bound example but our teacher told us lower bounds were no trivial matter and we should do some research. After a while we've found out that the Gilmore-Lawler bound is a good one to solve our problem (or at least good enough for learning purposes).

Although I have read a couple of papers I can't get the grasp of it. The idea seems to be to convert the QAP into an LAP combining the two matrices of the original problem. I've got completely lost after that. How is the number I'm supposed to find as the lower bound calculated?

Also, I'm aware that the lower bound has to be calculated for partial solutions, but how do I do that? The lower bound, as I understood, it's calculated from the program's matrices, which are a parameter for the branch and bound algorithm and are fixed from the beginning aren't they? I'd also need an explanation for that.


texts: Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?

texts:
I have seen numerous proofs (such as this) that the Halting problem is in the class of NP. However, the Halting problem is non-computable.

Does it make sense to discuss the complexity of computing a function that cannot be computed?


texts: Betweenness Centrality measurement in Undirected Graphs

texts:
I'm working with graphs of a very large size (> 60k vertices), and want to speed up B.C. measurements. It is defined here: http://en.wikipedia.org/wiki/Betweenness_centrality The algorithm that I am using to compute B.C. is Brandes' algorithm: http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf

For undirected graphs, would running the Betweenness centrality algorithm on each of its connected components (and then combine the results) give the exact same answer as computing on the whole graph at once? I would think so (but don't have a proof) because different connected components are not related.


texts: Why is everything in computer science a power of $2$?

texts:
I have noticed this strange thing.All things related to Computers come in values which are powers of $2$.For eg. Rams come in $2,4,8$ or $16$ GB,pendrives and memory cards also come in similar values.Computers are $8,16$ or $32$ or $64$ bit values.

Everything remarkably a power of $2$.Why is everything  $2^n$?

Why?Thanks for any help!!


texts: Looking for books on creating and understanding theorems targeted at Computer Science

texts:
In studying logic to understand verifying programs I have found that there are books on logic targeted at Computer Science e.g.

Logic in Computer Science: Modelling and Reasoning about Systems
Mathematical Logic for Computer Science
Computability and Logic
Handbook of Practical Logic and Automated Reasoning

With regards to books on understating theorems targeted at Computer Science I find only one that may fit. As I don't have the book I can't say for sure.

Handbook of Logic and Proof Techniques for Computer Science

Are there any books for understating theorems targeted at Computer Science? In other words are there books for understating syntax, semantics and construction of theorems that don't rely on a heavy math background and that give examples more from the world of computer science and explain in a style more natural to a person in computer science.

EDIT

After seeking more on this topic I have come upon the phrases "informal mathematics" and "mathematical discourse" which are starting to turn up useful info from Google. In particular the following: Understanding Informal Mathematical Discourse found at Understanding Informal Mathematical Proofs


texts: Two addresses point to the same data - is the data then stored 2 times in the cache?

texts:
Let's say a program reads the addresses 0x00 cd 10 54and0x00 cd 10 50. The tag size and and index size added are just 4 bits, the cache has 8 blocks to 8 Bytes and thus 4 together make a set. The CPU is 32 bit.

Then above addresses would point to:

0x00 cd 10 50: ca 01 6b 7f ff 00 10 ee ff 41 45 e8 00 a7 56 00

and would want to write ca 01 6b 7f ff 00 10 ee into set 0 with tag 0x00 cd 10 5

Let's say further say, the cache were empty beforehand. Is the data now written once or two times?


texts: How to prove a L=L(G) without knowing the L?

texts: How does one prove L(G)=L if the language is not given and only the grammar G is given?  If there is no pattern to be seen in the grammar that would create the strings w of a language L, how would you go about doing this?


texts: Fine-grained complexity of 3-CNF formula evaluation

texts:
It's well known that 3-SAT is in NP, which means that one can evaluate a 3-CNF formula in polynomial time. However, I was wondering what the tightest upper bound is for formula verification, expressed in big-O notation or some other way.

My best guess is that 3-CNF formulas can be verified in linear time in the number of clauses. Each clause has two disjunctions and up to three negations, which should each require one step to evaluate. If you count replacing a literal with its assigned value as a step, that gives you at most 8 steps per clause. Then, once all the clauses are evaluated, you should need [# of clauses] - 1 steps to compute all the conjunctions between them. So with $x$ clauses, that's at most $8x + x - 1 = 9x - 1$ steps total, which is $O(x)$.

Obviously, if I'm wrong about that, please let me know, and if there are even better time bounds (either theoretical or practical), I would love to hear about those as well.


texts:
I often hear people talking about parallel computing and distributed computing, but I'm under the impression that there is no clear boundary between the 2, and people tend to confuse that pretty easily, while I believe it is very different:

Parallel computing is more tightly coupled to multi-threading, or how to make full use of a single CPU.
Distributed computing refers to the notion of divide and conquer, executing sub-tasks on different machines and then merging the results.

However, since we stepped into the Big Data era, it seems the distinction is indeed melting, and most systems today use a combination of parallel and distributed computing.

An example I use in my day-to-day job is Hadoop with the Map/Reduce paradigm, a clearly distributed system with workers executing tasks on different machines, but also taking full advantage of each machine with some parallel computing.

I would like to get some advice to understand how exactly to make the distinction in today's world, and if we can still talk about parallel computing or there is no longer a clear distinction. To me it seems distributed computing has grown a lot over the past years, while parallel computing seems to stagnate, which could probably explain why I hear much more talking about distributing computations than parallelizing.


texts:
Is it possible to create a Fibonacci Heap that has exactly 5 nodes: one root node and 4 children of that root?. If yes please explain the sequence of operations to do so. If it is not possible then why?

I faced this question in an interview but couldn't answer it. Hopefully can learn it from here.


texts:
Each time the camera generates a ray, the first task of the renderer is to determine which object, if any, that ray intersects first and where the intersection occurs. This intersection point is the visible point along the ray, and we will want to simulate the interaction of light with the object at this point. To find the intersection, we must test the ray for intersection against all objects in the scene and select the one that the ray intersects first. Given a ray $r$, we first start by writing it in parametric form:
                    $$r(t)=o+td\,,$$
where $o$ is the ray's origin, $d$ is its direction vector, and $t$ is a parameter whose legal range is $[0, ∞)$.

My Question is - How is the equation  $r(t)=o+td$ formed from theory? For example, why is there $+$ instead of $-$ or $*$ or $/$, etc?


texts: How to implement a maximal munch lexical analyzer by simulating NFA or running DFA?

texts:
I'm planning to implement a lexical analyzer by either simulating NFA or running DFA using the input text. The trouble is, the input may arrive in small chunks and the memory may not be enough to hold one very long token in the memory.

Let's assume I have three tokens, "ab", "abcd" and "abce". The NFA I obtained is this:

And the DFA I obtained is this:

Now if the input is "abcf", the correct action would be to read the token "ab" according to the maximal munch rule and then produce a lexer error token. However, both the DFA and the NFA have state transitions even after "ab" has been read. Thus, the maximal munch rule encourages to keep on reading after "ab" and read the "c" as well.

How do maximal munch lexers solve this issue? Do they store the entire token in memory and do backtracking from "abc" to "ab"?

One possibility would be to run the DFA with a "generation index", potentially multiple generations and multiple branches within generation at a time. So, the DFA would go from:

{0(gen=0,read=0..0)},

read "a",

{1(gen=0,read=0..1)},

read "b",

{2+(gen=0,read=0..2,frozen), 2+(gen=0,read=0..2), 0(gen=1,read=2..2)},

read "c",

{2+(gen=0,read=0..2,frozen), 3(gen=0,read=0..3)},

read "f",

{2+(gen=0,read=0..2,frozen)}.

Then the lexer would report state 2+, and since there is no option to continue, would report an error state. Not sure how well this idea would work...

For "abcd", it would work like this:

{0(gen=0,read=0..0)},

read "a",

{1(gen=0,read=0..1)},

read "b",

{2+(gen=0,read=0..2,frozen), 2+(gen=0,read=0..2), 0(gen=1,read=2..2)},

read "c",

{2+(gen=0,read=0..2,frozen), 3(gen=0,read=0..3)},

read "d",

{2+(gen=0,read=0..2,frozen), 4+(gen=0,read=0..4,frozen), 4+(gen=0,read=0..4), 0(gen=1,read=4..4)}.

Now of these, it's possible to drop the first (there is a longer match) and the third (there are no state transitions out), leaving:

{4+(gen=0,read=0..4,frozen), 0(gen=1,read=4..4)}.

Then the lexer would indicate "match: 4+" and continue reading input from state 0 using generation index 1.

Is this idea of mine, running DFAs nondeterministically, how maximal munch lexical analyzers work?


texts:
Proving that Class P is closed under concatenation.

The answer is given below:

But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?


texts: Finding the number of intersections of $n$ line segments with endpoints on two parallel lines

texts:
Let there be two sets of $n$ points:

$A=\{p_1, p_2, \dots, p_n\}$ on $y=0$

$B=\{q_1, q_2, \dots, q_n\}$ on $y=1$

Each point $p_i$ is connected to its corresponding point $q_i$ to form a line segment.

Example:

I need to write a divide-and-conquer algorithm which returns the number of intersection points of all $n$ line segments and runs in $O(n logn)$.

I was reading about Sweep Line Algorithm but found out its complexity depends on the number of intersections, which can be ${O}{n\choose 2} \subseteq O(n^2)$ (besides the fact that it isn't a divide-and-conquer algorithm).
I believe I should use the fact that each set of points has the same $y$ value, but I'm not sure how. Any suggestions?


texts: Languages of cardinality higher than $\aleph_0$

texts:
I was studying model theory and that's how I came across formal languages. I looked around but it seems as though a language (set of strings over some alphabet) is usually treated as being finite or countable. Just wondering if languages of higher cardinality have been investigated. Any references would be nice.

Thank you!

EDIT: I found an answer. Infinitary logic deals with just such a question. See here. It allows formulas of infinite length, so the collection of all such formulas could be uncountable. I guess in the CS world a formula is simply a legally formed word (based on some rules). The set of all such legal formulas could be uncountable.

I'm choosing to leave this question here as it might help another beginner like myself.

EDIT 2: Another way maths allows uncountable languages is to allow uncountably many symbols in the signature (which would be a subset of alphabet in the CS world). So even if formulas (i.e. words) can only be finitely long, there can be uncountably many of them.

I've realized the question isn't so much about formal languages as it is about logic. It was due to my ignorance that I posted the question here. My humble apologies!


texts: Median of Medians Recurrence Relation for 3-grouping

texts:
So I am trying to figure out the recurrence relation for the median of medians algorithm using groups of 3 instead of groups of 5. Per CLRS's method, my recurrence relation looks like

$$
T(n) = T(\lceil \frac{n}{3} \rceil) + T(\frac{2n}{3} + 4) + c_1n
$$

And I want to show $T(n) = O(n \lg n)$

Via substition, I assume inductively that

$T(n') = cn' \lg n'$

So by substition

$$T(n') \leq c\lceil \frac{n'}{3} \rceil \lg \lceil \frac{n'}{3} \rceil + c(\frac{2n'}{3} + 4) \lg (\frac{2n'}{3} + 4) + c_1n' $$

$$ \leq c (\frac{n'}{3} + 1) \lg (\frac{n'}{3} + 1) + c(\frac{2n'}{3} + 4) \lg (\frac{2n'}{3} + 4) + c_1n'$$

aaand now im stuck. Is there anyway i can drop the +1 and +4 from this expression to make it simpler?


texts: The number of Binary Search Tree that exist with same Postorder and Inorder

texts:
how many BST exist with same postorder and inorder traversal?

I know that in binary tree (Not BST), it is one.

but i have a book from that said for BST it is CATALAN number. i become confused.


texts: Don Knuth and MMIXAL vs. Chuck Moore and Forth -- Algorithms and Ideal Machines -- was there any cross-pollination / influence in their ideas / work?

texts:
Question:

To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms?

I'm interested in citations, interviews, articles, links, or any other sort of evidence.  It could also be evidence of the form of A and B here suggest that Moore might have borrowed or influenced C and D from Knuth here, or vice versa.  (Opinions are of course welcome, but references / links would be better!)

Context:

Until fairly recently, I have been primarily familiar with Knuth's work on algorithms and computing models, mostly through TAOCP but also through his interviews and other writings.

However, the more I have been using Forth, the more I am struck by both the power of a stack-based machine model, and the way in which the spareness of the model makes fundamental algorithmic improvements more readily apparent.

A lot of what Knuth has done in fundamental analysis of algorithms has, it seems to me, a very similar flavour, and I can easily imagine that in a parallel universe, Knuth might perhaps have chosen Forth as his computing model.

That's the software / algorithms / programming side of things.

When it comes to "ideal computing machines", Knuth in the 70s came up with the MIX computer model, and then, collaborating with designers of state-of-the-art RISC chips through the 90s, updated this with the modern MMIX model and its attendant assembly language MMIXAL.

Meanwhile, Moore, having been using and refining Forth as a language, but using it on top of whatever processor happened to be in the computer he was programming, began to imagine a world in which the efficiency and value of stack-based programming were reflected in hardware.  So he went on in the 80s to develop his own stack-based hardware chips, defining the term MISC (Minimal Instruction Set Computers) along the way, and ending up eventually with the first Forth chip, the MuP21.

Both are brilliant men with keen insight into the art of programming and algorithms, and both work at the intersection between algorithms, programs, and bare metal hardware (i.e. hardware without the clutter of operating systems).

Which leads to the question as headlined...

Question: To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms?


texts: Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge

texts:
I'm pracitcing exams towards finals,

Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$.

Prove :
for every 2 distinct MST $T,T'$ there is a sequence of $k$ MST's such that every 2 MST's $T_i,T_i+1$(+1 on the index) in the list are neighbours and at the end of the sequence we get $T$

$T' = T_1,T_2,T_3,\ldots,T_k=T$

hope to get help.


texts: Infer number of comets, based upon observations of their periodic visits to Earth

texts:
Can we algorithmically infer the number of comets that orbit the Earth, based upon periodic observations of them, if we cannot tell the comets apart?  In more detail:
The problem

There is an unknown, fixed number of comets, numComets that pass by
Earth and are visible from the ground.

Each comet takes a fixed number of years to orbit Earth.

Based only on this knowledge and the dates recorded that a comet was
sighted in the night sky, determine numComets, AND determine
the orbital period of each comet. You can use an unlimited amount of
observation data (time), but the solution in the shortest amount of
time is preferable.

Assumptions you can make

All comets look identical from the ground; there is no way to
visually identify them.

No other object will be mistaken for a comet, and all comets will be
seen.

No comet takes more than 100 years to orbit Earth, and no new comets
will be introduced.

As current answers have pointed out, the problem as it lay now is unsolvable. Would a solution be possible if numComets is known? (Even roughly get the right answer?) What modifications to the problem would have to be made otherwise, to still encasulate the spirit of the problem, and make it solvable? (or is it dead with no hope of solving accurately?)
Further assumption
All comets start at a different point in their orbit. I.e. They do not all start their orbit at the same place like racehorses coming out of a gate.
Clarification
Comets are only recorded once per year. So there is no difference between a comet that passes at the beginning of a year and at the end. The problem could just as easily have been worded as days.


texts:
Given a full binary tree of size $n$, I need to cut the tree into two by choosing an edge and removing it. I want the cutting to be as equal as possible (i.e. the two subtrees have as equal weight as possible).

Can I always cut the tree into two equal subtrees? If not, what is the lower bound for the cut (the smallest size of the smaller subtree)?

What is an algorithm I can use to find this cut?


texts: Finding small node sets that can not be avoided on paths from source to sink

texts: In a directed graph with a starting node and an ending node, how to find a small (doesn't have to be smallest. <10 for example) set S of nodes such that every possible path from the starting node to the ending node contains at least one member of set S. The graph may have loops. This may be NP hard. Is there an approximate method to find one or several such S from the graph? Enumerating and testing every candidate seems not work. thanks.


texts: How to compute the sum of this series involving golden ratio, efficiently?

texts:
Definitions

Let $\tau$ be a function on natural numbers defined as $\tau(n)=\lceil n*\phi^2\rceil$ where $n$ is some natural number and $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. This series can also be looked up here : A004957, with first few terms being $3,6,8,11,14...$ .
Let $t$ be the largest natural number such that $\tau(t) \le 10^{16}$.
Let $S_i$ for $1 \le i \le t$ be defined as $S_i=-(10^{16}-\tau(i)+1)*i+ 2*\sum_{j=\tau(i)}^{j=10^{16}} j $.

Problem
How can I compute the sum $(S_1+S_2+...S_t)$ % $7^{10}$ efficiently ? I tried thinking by matrix exponentiation, but can't come up with a method due to the form of the $\tau$ function.

PS: This question is my way of trying to solve the problem : stone game II.


texts: Change in the distances in a graph after removal of a node

texts:
Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that,

$$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G \setminus \{v\}}_{su}-d^G_{su})}$$

In other words, we are looking for the difference in distances from $s$ to every other nodes after removal of each node $v$.

Now the question: is there an algorithm with time complexity $O(n+m)$ that can calculate the vector $\operatorname{diff}$ for a given graph $G$ and node $s$? If yes, what is the algorithm (or the idea behind that algorithm)?

For a specific node $v$, we can run BFS on $G$ and $G \setminus \{v\}$ and find the $\operatorname{diff}[v]$ in $O(n+m)$, but here we want $\operatorname{diff}$ for all of the nodes.

I know that we can determine, whether $\operatorname{diff}[v] >0$ for every node $v$ (using shortest path tree of $s$), in $O(n+m)$, but is there an algorithm to find the exact value of $\operatorname{diff}$ in $O(n+m)$ time complexity?

Hints.

There are some properties in the shortest path tree that may help:

If we construct the SPT, and then add the other edges of the graph that are not in the SPT, there will be edges from one level to the next level, or edges among nodes within the same level.
When we remove a node $v$, only the distance between $s$ and the descendants of $v$ can be changed.
For a node $v$, if all the descendants have another neightbour in $G$ that is on the same level as $v$ in the SPT, then $diff[v]=0$.
For every descendant of $v$, if we keep track of the incoming edges whose other endpoint is in another subtree (subtree of siblings of $v$), we can easily update the distances for its children (Suppose that child is $v'$, the change in $diff[v]$ for such $v'$ will be $\min{(diff[v']+1,(d^{new}_{sv'}-d_{sv'})\cdot(\# \text{children whose endpoint is in the subtree of }v)+(\text{new distance of nodes whose endpoint is outside subtree of v}))}$).

We can assume that the graph is 2-vertex-connected, which means that it will not be disconnected by removing one node (otherwise we can find all the vertex cuts of size of using DFS and check each connected component separately).


texts: Differences between SISD, SIMD and MIMD architecture (Flynn classification)

texts:
I have a problem with classifying certain CPUs to the proper classes of Flynn's Taxonomy.

1. Zilog Z80

According to this article on Sega Retro, Z80 has limited abilities to be classified as SIMD:

  a limited ability for SIMD (Single Instruction, Multiple Data) with instructions to perform copy, compare, input, and output over contiguous blocks of memory;

For what I understand, Z80 is usually behaving as a SISD but when it comes to performing thing like copying or comparing Z80 is able to process multiple data using a single instruction.

How should we classify Z80 then? Is the ability to become SIMD processor a voice for or against saying that Z80 implements SIMD architecture?

2. Intel i5 (Dual core)

Form what I understand, we classify multicore CPUs as MIMD.

Is it as simple as that?

3. ARM Cortex-A15 (single core)

I'd classify the architecture of this processor as a SIMD model. Wikipedia says that it has superscalar pipeline, but as we know from Why is a superscalar processor SIMD? that multiple pipelines does not imply MIMD model.

Are "modern" single cores usually implementing SIMD model or not?


texts: Is n-dimentional assignment problem for points NP-hard?

texts:
We have $n$ sets of $k$ points in $\mathbb R^d$ and we are trying to partition them to $k$ clusters of $n$ points such that from each set every point is mapped to a different cluster and the sum of variances of each cluster is minimized, i.e., we are trying to solve the $k$-means problem but with the constraint that points from the same set can't go to the same cluster.
I know that even for $n=3,d=2$ this problem is NP-hard in $k$ but I'm trying to figure out if for constant $k$ this problem is NP-hard in $n$?
I've looked in the Wikipedia page of NP-hard problems and tried to think if I can do a reduction to one of them but i couldn't think of any way to do so.


texts:
Let $T$ be a Splay Tree. For a given permutation $\sigma$ on a set $S = \{1,2,3,...n \}$ we defined the following function:

Splay-Insert-Permutation(σ)
{
FOR i := 1 TO n DO
    T.Tree-Insert(σ(i))
    T.Splay(σ(i))
ENDFOR
}

We basically insert the elements of some permutation on $S$ one by one and perform splay after each insertion.

For $n = 3$ and $n=7$, I have found the permutations $S_{3} =  \{1,3,2 \}$ and $S_{7} =  \{1, 7, 3, 5, 2, 6, 4 \}$ to give a Splay tree $T$ with minimum height (full binary tree).

Is it possible to have more than one unique permutation for a fixed $n$ that will give a minimum height splay tree after performing the above method? Can we generalize something about them?
Thanks.


texts: How is Chinese Remainder Theorem used in the proof of correctness for RSA

texts:
Question

At the very end of (most) proofs of RSA's correctness we have something like
$$m^{ed}\equiv m\pmod p$$
$$m^{ed}\equiv m\pmod q$$
Therefore by the Chinese Remainder Theorem (CRT)
$$m^{ed}\equiv m\pmod n$$
where $n=pq$, $ed\equiv 1\pmod{\phi(n)}$ and $m<n$

It's not obvious to me what work the CRT is doing here. If anyone can help that would be great, thank you!

My working so far

CRT (as I have it) says that if we have $n=n_1...n_k$ where $n_1...n_k$ are pairwise coprime and a series of equations $x\equiv a_i\pmod{n_i}$ for $1\leq i\leq n$ then there is a unique solution for $x$ modulo $n$

To find $x$ we can use $$x=\left(\sum_{i=1}^ka_im_iy_i\right)\bmod n$$ where $m_i=n/n_i$ and $y_i=m_i^{-1}$ (mod $n_i$)

So for the RSA proof we let $x=m^{ed}$ and say we have $x\equiv m\pmod p$ and $x\equiv m\pmod q$

Let $q' = q^{-1}\pmod p$ and $p'=p^{-1}\pmod q$

Therefore using the above equation we have
\begin{align}
x&=(mqq'+mpp')\bmod n\\
&=m(qq'+pp')\bmod n
\end{align}
So I need to show that $qq'+pp'\equiv 1\pmod n$


texts: Basic approximation algorithms understanding

texts:
Question:

Suppose we have 2 algorithms $Alg1$ and $Alg2$ for the same minimization problem. We know that $Alg1$ is a $2$-approximation algorithm and $Alg2$ a $4$-approximation algorithm.

Is the following statement true?

There must be an input $I$ such that $Alg2(I) \geq 2 \cdot Alg1(I)$.

My answer:

I think the statement is false:

In order to prove that the statement is false it is sufficient to find one case where $Alg1$ is a $2$-approximation and $Alg2$ is a 4 approximation and that there is no input which satisfies the inequality from the statement.

Does my approach make sense? Is there some other approach or thought process which proves statements of this type true/false that I'm missing?

Note:

$Alg$ is a $\rho$-approximation algorithm for a minimization problem $\iff$ $\forall I.(OPT(I) \leq Alg(I) \leq \rho \cdot OPT(I))$ where $\rho > 1$ and $OPT(I)$ denotes the optimal solution to the minimization problem for the input $I$.


texts: Iterative lengthening search: iterative version of Uniform Cost Search or DFS?

texts:
Actually my question has two parts:

1) I wanted to know that whether Iterative Lengthening Search is used in combination with DFS or Uniform Cost Search? Actually, in Russell and Norvig book (on page 90), it is described as follow:

  It would seem worthwhile to develop an iterative analog to uniform-cost search, inheriting the latter algorithm's optimality guarantees while avoiding its memory requirements. The idea is to use increasing path cost limits instead of increasing depth limits. This resulting algorithm is called iterative lengthening search... It turns out, unfortunately, that iterative lengthening incurs substantial overhead compared to uniform-cost search.

It seems that by using "avoiding its memory requirements", they mean that we use it in combination with DFS.

But, here in this link, which is the solution of final exam problems of artificial intelligence course at CMU, on page 4, it is described as follow:

  Iterative lengthening search is an iterative version of uniform cost search. The main idea of this algorithm is that we use increasing limits on path cost.

  We start searching as though we were performing uniform cost search.

  and so on...

And also here in this link, question 4, part 1:

  Iterative lengthening is uniform-cost search which is run multiple times with an increasing bound on the maximum cost from the start to reach before quitting. Iterative lengthening search doesn't have advantages in the same way iterative deepening depth-first search does.Iterative lengthening will simply search the same nodes each time adding more at the end since the first closest node, second closest node, etc. is invariant. All that iterative lengthening does is require the algorithm to restart repeatedly before finding a solution.

It seems that they mean we use it in combination with Uniform-Cost search.

Actually, I implemented it using uniform cost search, but to me there is no point in running uniform cost search over and over from beginning while increasing path cost limit (I mean using DFS seems more reasonable).

So which one is correct? (Is it the case that I misinterpreted them?)

2) Would you clarify why iterative lengthening search occurs substantial overhead?(Actually in case of using Uniform-cost search it is obvious, but I wanted to know this in case of using DFS.)

Clarification:

In order to resolve any ambiguity, here is pseudocodes for ILS in both cases(using DFS or UCS):

ILS using DFS:

0. Set limit to zero.
1. Perform DFS on initial node while discarding any generated node with path cost greater than limit.
2. If DFS ended with Failure or Success, return that as a result.
3. Otherwise set limit to minimum path cost of generated nodes that were discarded in previous run of DFS.
4. Go to line 1.

ILS using UCS:

0. Set limit to zero.
1. Perform UCS on initial node while discarding any generated node with path cost greater than limit.
2. If UCS ended with Failure or Success, return that as a result.
3. Otherwise set limit to minimum path cost of generated nodes that were discarded in previous run of UCS.
4. Go to line 1.

I was thinking about this for the past week. I think that ILS in combination with UCS has no advantages to UCS itself. While ILS in combination with DFS, at least is much better than UCS in terms of memory usage. And I think overhead occurs because in both of them, in each iteration only one more node(or a few if we have several nodes with same minimum path cost) is added to nodes that we explore in next iteration. However I'm not sure about these.


texts: Delaunay Triangulation on Convex Polytopes — Uniform Sampling

texts:
My goal is to uniformly sample from a convex polytope. I know that for the simpler case, where I have to uniformly sample from a simplex, I can use Bayesian Bootstrap, discussed in these posts:

Uniform sampling from a simplex

Random vectors uniformely distributed into convex n-polytope

Therefore, I'm very interested in this approach. But I don't really know how to use Delaunay Triangulation here. What I have is a linear equation Ax = b and a non-negativity constraint that $x \geq \vec{0}$, and I want to sample x uniformly. Can someone tell me how to do the Delaunay Triangulation here? Thanks in advance!


texts: Boolean Functions Implemented by Multiplexers

texts: Electrical engineers often use multiplexers to implement Boolean functions. What is the correct technical term for this model of computation? Is it Decision Tree model or is there another name?


texts: Complexity of emptiness checking for visibly pushdown automata?

texts:
Visibly pushdown automata [1] are pushdown automata in which input symbol determines whether push or pop operation happens in the stack. Does anyone aware of tight lower bound for their emptiness checking complexity?

[1] Rajeev Alur and P. Madhusudan. 2004. Visibly pushdown languages. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (STOC '04). ACM, New York, NY, USA, 202-211. DOI: http://dx.doi.org/10.1145/1007352.1007390


texts: What is the meaning of 'moderately exponential' running time?

texts:
I was reading some research paper where for hypergraph of bounded rank $k$ they have given moderately exponential algorithm. The runtime of the algorithm is $e^{  \mathcal {O}(k^2\sqrt n) \cdot poly(n)}$. Here $k$ is the rank of the hypergraph, and $poly(n)$ means polynomial in variable $n$.

  What is the meaning of moderately exponential running time ?

I have seen this  link, but did not understand much.


texts: Logical and non logical symbols and predicates

texts:
I am going through the text
from "R.Brachmann and H.Levesque: Knowledge representation and reasoning".
Here it has been described(in page 15) that there are two types of symbols : the logical symbols and the non logical symbols.

Logical symbols are the ones that have a fixed meaning and the non logical ones are the ones having application dependent meaning.

What I find confusing is "variables" having classified as logical ones whereas functions symbols have been classified as non logical ones.

I don't know whether I should be confusing this with the context of programming  languages or not but  variables also don't have fixed meanings and they too are created for application dependent use.

Shouldn't they both be in the same slot?

Now for predicates, I do not understand what exactly is  a predicate? Do predicates mean the same thing as relations like "greater than", "less than"? If yes, then can there be an infinite variety of predicates? I can think of only this "lesser than ", "greater than", "equal to".
What are some more examples of predicates?

P.S : Sorry about the predicate part , perhaps the following link contains a lot about it :
https://stackoverflow.com/questions/6337778/predicate-vs-functions-in-first-order-logic


texts: Syntax directed translation , definition and actions

texts:
I have trouble understanding Syntax directed translation/definition/actions. I am reading dragon book but it confuses me even more.

Having production for simple  arithmetic

$$
  \mathit{expr} \rightarrow \mathit{expr} + \mathit{expr} \mathbin{|}  \mathit{expr} - \mathit{expr} \mathbin{|} \mathit{num}
$$

$$
  \mathit{num} \rightarrow 0 \mathbin{|} 1 \mathbin{|} 2 \mathbin{|} \dots \mathbin{|} 9
$$

If I understood it correctly, SDT just adds attributes to the nodes and define rules.

for this production rules can looks like

$$
  \mathit{expr}.\mathit{val} = \mathit{expr}.\mathit{val} + \mathit{expr}.\mathit{val} \mathbin{|} \mathit{expr}.\mathit{val} - \mathit{expr}.\mathit{val} \mathbin{|} \mathit{num}.\mathit{val}
$$

$$
  \mathit{num}.\mathit{val} = 0 \mathbin{|} 1 \mathbin{|} \dots \mathbin{|} 9
$$

this all together is called Syntax directed definiton.

Now what starts to confuse me:

It is often written that SDT is used to transfer infix to postfix notation e.g

$\mathit{expr} \rightarrow \mathit{expr} + \mathit{expr}$ will have semantic rule such as $\mathit{expr}.\mathit{val} = \mathit{expr}.\mathit{val} \mathbin{\|} \mathit{expr}.\mathit{val} \mathbin{\|} \text{'+'}$, where $\|$ represents concating of strings.

Is STD strictly defined to trasnform notation to postfix?

Also, where in this fall actions?

By definition

  A syntax-directed translation scheme is a notation for specifying a
  translation by attaching program fragments to productions in a
  grammar. A translation scheme is like a syntax-directed definition,
  except that the order of evaluation of the semantic rules is
  explicitly specified. Program fragments embedded within production
  bodies are called semantic actions

and example

$$
  \mathit{expr} \rightarrow^{+} \mathit{expr}\ \ \{\, \mathit{print}(\text{'+'}) \,\}\ \ \mathit{expr}
$$

I cannot find what is the usage of this. Which leads to sum of questions:
What is STD (rules) for and what are uses of actions in it?

I appreciate all answers, I read wiki but did not help.

Thanks.


texts: Scheduling algorithm with waiting time and priority

texts:
I have gone through a list of scheduling algorithms and their implementation, however couldn't find any reference to implement an algorithm that solves the following problem.

Given an array of processes having n process, the i'th process being represented by:

Arrival[i] representing its arrival time,

Depart[i] representing the time when a process will be terminated (processed or unprocessed doesn't matter) and

Time[i] representing the time required to serve the process, and

Preferred[i] representing a Boolean value (true if that process is preferred, false otherwise)

We need to schedule the processes to maximize processing of preferred processes.
A preferred process will have Preferred[i] as true.

The constraint being only a single process can be served at a time, and if a process departs before its completion its said to be unprocessed.

In case of a tie following rules apply:

Serve maximum number of processes (preferred and non- preferred combined).
Minimize the Processing time.

Any leads would be appreciated.


texts: I can not understand some petri net properties ( quasi-liveness and liveness )

texts:
Can anyone please help me understand the quasi-liveness and liveness properties of petri nets. Suppose that you explain that to a person with 10 years old.

For my part, i have the following definitions.
- quasi-liveness petri net: its mean that every transition in the net can be enabled at least one time for specific marketing. So may be enabled many times.
-liveness petri net: its mean that every transition in the net can be rechargeable from any marketing.

Am i right ?, can you give me a simple example. Finally what is the best method to find these properties ?


texts: Can the Dijkstra algorithm work with a negative arc?

texts:
When there is no negative circle in the graph?
And can Dijkstra not work even if there is a negative arc that does not create a negative cycle?


texts:
Berman's theorem states

  If a unary language ( a language with all the strings of the type $1^i$, $ i  > 0 $ ) is NP-Complete then P = NP.

I tried reducing SAT to a given unary language $L$ assuming it is NP-Complete. But I can't think of a way  such that after applying the reduction so that SAT gets solved in polynomial time. How do I proceed further?

This is an exercise from Sanjeev Arora and Boaz Barak , but not homework.


texts: What is the difference between assignment, valuation and name binding?

texts: I read that Name binding assigns some value (data/code/expression) to an identifier. Assignment and valuation seem to do the same thing. It is confusing. Can I just tell that free variable is one, which was not assigned a value whereas bound variable has its value assigned?


texts: Can we reduce an NP complete item to an NP item which is $\bf{non}$ P?

texts:
I'm curious if we can reduce an $NP$-complete problem to an $NP$ problem which is not a part of the $P$ set. Meaning, can we take an algorithm for this kind of $NP$ problem and use it to solve a single $NP$-complete problem?

If we could do this would it mean that the single $NP$ problem which is non $P$ is considered to be a part of the $NP$-complete problem set?

Is there a way to prove that all $NP$ problems which are non $P$ are considered to be a part of the $NP$-complete problem set?


texts:
Wikipedia says about Gustafsons's law that:

  It may even be the case that $\alpha$ diminishes as $P$ (together with the problem size) increases.

I'm not understanding how $\alpha$ can ever change given it's definition:

$$ \alpha= a / (a + b)$$

I thought that $a$ and $b$ are constants independent of the problem size.

What am I missing?


texts: Scheduling algorithm with defined starting intervals and processing times

texts:
I need to design an algorithm for opening and closing some valves at regular times. The input schedule will look something like this:

Every 5 minutes, open each of valves 1, 2, and 3 for 5 seconds
Every 8 minutes, open each of valves 4, 5, and 6 for 10 seconds

The main constraint on this schedule is that only one valve can be open at a time.

If I were given just the first line from above as my schedule, the result would be like:

t % 300 = 0: open valve 1
t % 300 = 5: close valve 1, open valve 2
t % 300 = 10: close valve 2, open valve 3
t % 300 = 15: close valve 3

Adding in the second line raises some more problems, like what is the overall time period (i.e. the divisor in the %)? I believe this should be the least common multiple of all the time periods: 2400 = 300 * 8 = 480 * 5. The schedules then become 8 and 5 copies, respectively, of the base schedules lined up sequentially.

I would want to determine if it is possible to fulfill the schedule. A simple sanity check is that the sum of all the open times is less than the total amount of time in the LCM, but I do not believe this is sufficient.

Second, I need to determine what the actual combined schedule is. I believe this would be a series of starting offsets for each valve's schedule. In the simple case I illustrated above, the offsets for each of valve 1, 2, and 3 are 0, 5, and 10, respectively.

I have looked into cyclic static scheduling, earliest deadline first algorithms, etc., but have been unable to synthesize this knowledge into the algorithm that I need here. The difficulty I see is that I do not have an ending deadline but a starting deadline: once the first valve opens at t=0, it must also open at t=300, 600, 300*n.

Other analogies I have considered are:

packing byte patterns into a buffer without overwriting non-null values (view each time slice as a byte and the value at the byte is the number of which valve is open)
dispatching trains of different speeds at given intervals and avoiding collisions
arranging transparent pieces of plastic with some colored areas in a stack (or cylinder since this is repeated) so that a max of one color is present at any given point

To recap: I need to determine a schedule meeting the above criteria. If determining the schedule is computationally intensive, it would also be nice to quickly determine if such a schedule is possible as well.

Am I on the right track here? What should I search for to move forward in this algorithm design? Has this problem been solved already?


texts: Algorithm for printing all accepted strings (to an upper bound if infinite amount) from a given DFA

texts:
As the title states I'm trying to write an algorithm that generates accepted strings to an upper bound from a given DFA.

It should not generate more strings than the upper bound n if it contains cyclic patterns, because obviously I can't print an infinite amount of strings, which leads me to my problem.

Machines with finite languages are very straight forward as I can just do a DFS search and traverse through the graph and concatenate all letters that connect the states recursively, but I have no clue how I should deal with infinite language DFAs unless I hardcode a limit on how many times the DFS should traverse states that can potentially lead to cycles.

So my question is; how should go about approaching this problem. Are there any known algorithms (aside from DFS, BFS) that I could use to tackle this task?

Thanks in advance. I tried hard to find similar questions but I couldn't find anything helpful.

Edit: Clarified problem a little bit.


texts:
It is not uncommon to see students starting their PhDs with only a limited background in mathematics and the formal aspects of computer science. Obviously it will be very difficult for such students to become theoretical computer scientists, but it would be good if they could become savvy with using formal methods and reading papers that contain formal methods.

  What is a good short term path that starting PhD students could follow to gain the expose required to get them reading papers involving formal methods and eventually writing papers that use such formal methods?

In terms of context, I'm thinking more in terms of Theory B and formal verification as the kinds of things that they should learn, but also classical TCS topics such as automata theory.


texts: how real example projects apply formal proof techniques

texts:
Given that there are examples of formal proofs used to formally verify real-world software applications, I would like to know what these people and teams actually do to create these formal proofs. That is, the kind of code they write and/or the types of formal proofs they create, and how the proofs work. For example, maybe the proofs are term derivation trees, or state-transition graphs, etc.

I understand how model checking works, but the model itself should probably be "proven" somehow even before checking it against a specification. What I am wondering here is only about proofs. For example, in airplanes, what types of things they are proving, and how they are going about proving them. For example, maybe they prove that the plane will land if this button is pressed. That is the what they prove part. Then they do this by writing some Coq code that is exported to ocaml, and in the Coq code they have to prove x about the button itself, and y about the forces of air while the plane is flying, and z that the air brakes will apply effective force etc. And they do this by starting from axioms a b and c. That is the how part.

I don't need to know exactly they are doing the specific proofs, just generally how they go about it. I would like to know generally what they start from, how they formalize and prove it (the model not the spec) in a language, and how this results in a feeling of "now our code is proven". My previous questions about proofs didn't go into enough depth about how the proofs actually work.

Another example from the link is satellite technology, compilers, and os-kernels.


texts: Solving recurrence relation where the $f(n)$ has some constant factor $k$ where $0 < k < 1$

texts:
I am trying to see if a recurrence relation where $f(n)$ has some constant factor $k$, e.g. $f(n)=kn$ where $0 < k < 1$, is $O(n)$. I am reaching a different result depending which route I take. Given the following recurrence relation:

$$T(n)=2T(\frac{n}{2})+f(n)$$
$$T(n)=2T(\frac{n}{2})+kn$$
Since $0 < k < 1$, we can represent $kn=n^c$, where $0 < c < 1$

This falls under the case 1 of the Master Theorem, because $a=2, b=2$, and therefore $log_b a = log_2 2 = 1 > c$.

It's $O(n)$.

But if I try to unfold the recurrence:
$$\begin{split}T(n) & = 2T(\frac{n}{2})+kn \\
& = 4T(\frac{n}{4})+2kn \\
& = 8T(\frac{n}{8})+3kn \\
& = ... \\
& = 2^cT(\frac{n}{2^c})+ckn \\
\end{split}$$

When $\frac{n}{2^c}=1$, $n=2^c$, then $log_2 n = c$.

So now it's $T(n) = nT(1) + kn log_2 n$, which is $O(n log_2 n)$. Now I am confused.


texts: What is an algorithm to find the largest rectangle of white space in an image?

texts:
Take an image, (the Google home page) is a good example.

I want an algorithm to find the largest white rectangle in this image. That is to say, the largest rectangle that would fit in an area of white space containing only white space.

Do you know any algorithms that would do this?


texts: Is MCTS an appropriate method for this problem size (large action/state space)?

texts:
I'm doing a research on a finite horizon decision problem with $t=1,\dots,40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t) \in S(t)$. The chosen action $a(t)$ in state $s(t)$ affects the transition to the following state $s(t+1)$. So there is a finite horizon markov decision problem.

In my case the following holds true: $A(t)=A$ and $S(t)=S$, while the size of A is $6\cdot10^6$ and the size of S is $10^8$. Further the transition function is stochastic.

Since I'm relatively new to the theory of Monte Carlo Tree Search (MCTS), i ask myself: is MCTS an appropriate method for my problem (in particular due to the large size of A and S and the stochastic transition function?)

I have already read a lot of papers about MCTS (e.g. progressiv widening and double progressiv widening, which sound quite promising), but maybe someone can tell me about their experiences applying MCTS to similar problems or about appropriate methods for this problem (with large state/action space and a stochastic transition function).


texts: Timing of Synchronous/Asynchronous Bus Operation

texts:
What is difference between Synchronous and Asynchronous Bus Operations. And how are they change in read cycle and write cycle ??
I shared a website it tells these bus operations bu I didint understand clearly and I didint understand these pictures in the website.

https://www.quora.com/What-is-the-difference-between-a-synchronous-and-an-asynchronous-bus


texts: Another version of the online set cover problem?

texts:
Here is a note about online set cover problem:
we are initially given the $m$ sets, but we do not know which elements they contain. At any time $t$, we get a new element $e_t$ and learn which sets contain $e_t$. We then have to irrevocably pick a set that will cover $e_t$ if it is not already covered. The goal is again to minimize the number of sets we pick.

However, I'd like to think about another version: we have a group of sets $\mathcal{S} = \{ S_1, S_2, \cdots, S_m \} $ and a universal set $U=\{ e_1, \cdots, e_n \}$.
$U$ can be covered by $\mathcal{S}$. But we don't know what elments each $S_i \in \mathcal{S}$ contains. Then $S_1$ comes and now we know what elements $S_1$ contains. Meanwhile, we have decide either you will use $S_1$ to cover $U$ or you discard it. Then, $S_2$ comes, you know what elements $S_2$ contains and decide to keep $S_2$ or discard it. The process is repeated until the sets you keep can cover $U$.

I want to ask if there is an algorithm works in the way I mentioned. Must we check all the $S_i \in \mathcal{S}$ in order to get a solution of set cover? Or what is the expected number of sets that have to be checked in order to get a solution of set cover?  If we can also design a $O(\log n\log m)$ approximation ratio algorithm for this online version.


texts: How is Pure Maths utilized in Computer Science research?

texts:
How can People with a background in Mathematics pursue PhD in Computer Science"

Although I have a Postgraduate degree in Mathematics with basic programming knowledge,it sounded quite interesting how knowledge in Mathematics can help to solve Computer Science Research Problems.

Since this site is for researchers in Computer Science,Can someone kindly tell:

What type of problems can a Mathematics postgraduate take up in Computer Science?
What is the current scenario of research in Computer Science where Mathematicians like us can make a significant impact?
What are the other skills needed apart from a sound Programming knowlegde to work here?

Any links/references would suffice too.

I have done courses on Linear Algebra,Abstract Algebra,Functional Analysis,Topology,Number Theory and have enjoyed them.

I really dont know how to use the concepts learnt in these courses can be used to solve research questions on Computer Science.

If someone can kindly comment how concepts in the above Mathematical facts can be used to do research in CS,I can understand why a reputed instititution in our country is asking for postgraduate in Mathematics for a PhD in CS.


texts:
Consider that I have an array of ranges and I want to transform it to the new array that represents the ranges that any range is in.

Example:

Ranges:
[red: [1,11], black: [15,16],yellow: [5,9], green: [7,8]]

Result:

[1,4] - red
[5,7] - red & yellow
[7,8] - red & yellow & green
[8,9] - red & yellow
[10,11] - red
[15,16] - black

My first thought was to use interval tree but the most implementations I found  want to ask tree by range and I want to explicitly list groups as shown in example.


texts: Distributed MST Construction in O(log log n) Rounds in a Clique

texts:
I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5.

It shows by induction on k (phase number), that the spanning tree, for every cluster F (from phase k), is indeed an MST fragment of that cluster of vertices.

The claim is of course trivial for the base case, as the clusters are singletons of vertices. To show the induction step, it suffices to show that each edge $e$ (where $X\left(e\right)=\left(F_{1},F_{2}\right),\ F_{1}\in\hat{F_{1}},\ F_{2}\in\hat{F_{2}}$, where $F_{1},F_{2}$ are the original clusters, that is, the connected components of the previous round, now contracted into one vertex, and $\hat{F_{1}},\hat{F_{2}}$ are their super clusters, that is, the connected components containing them, created as part of this procedure in phase $k$) chosen by the procedure Const_Frags is indeed a minimum weight outgoing edge (MWOE) of either $H_{1}=\underset{F\in\hat{F_{1}}}{\bigcup}F$ or $H_{2}=\underset{F\in\hat{F_{2}}}{\bigcup}F$. They assume wlog that $e$ was chosen as part of $F_1$'s $\mu$ lightest outgoing weight edges, and want to show that $e$ is indeed the MWOE of $H_1$. So they assume otherwise, that there exists $e'$ of lower weight than $e$ that is outgoing from $H_1$.

What I don't understand is, why do they assume that $e'$ is of cluster $F_1$ as well? The only thing we know about $e'$ is that it is outgoing from $H_1$. This means that it can be outgoing from another cluster- $F'\in\hat{F_{1}}\backslash\left\{ F_{1}\right\} $. I would appreciate any help! thanks!


texts: Designing a CFG that produces as many c's as the difference of numbers of a's and b's

texts:
The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is

$\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}; n = |l-m|\}$.

I have so far go to create the cfg for $(a^l)(b^m)$ but don't know how to do the one for $(c^n)$. It looks complicated as to find the value of n, we need to take the abs value for the difference between l and m. Can someone help?

And, here is the cfg I got so far for $(a^l)(b^m)$.

$S \to aS \mid bT|\epsilon $

$T \to bT \mid \epsilon$

I hope this is correct.


texts:
In a programming book that I'm currently reading it's stated that

$$\sum\limits_{i=1}^{n}i^2$$ is $O(n^3)$. My understanding was that $i\times i$ is a primitive operation and the complexity would be $O(n)$. What am I missing?


texts: Method to recognize abstract objects such as hand-drawn objects?

texts:
My research is in the area of Document Image Analysis. To be specific, the topic of my thesis is to automatically recognize and index characters in a set of hand-drawn objects, e.g. given a volume of comics --> how to localize, recognize then index the characters in it (e.g. return "Lucky Luke" position in some random volume).

First thing first, before I can work on the indexing part, I must have some reliable system to recognize the interested characters. After some months working on it, I find the recognition is extremely hard, because the drawings are some time very "abstract".

For normal face recognition, there are a lot of researches on it, thus we have Haar-like features, biometrics features, etc. For normal photograph objects, we may use e.g. SIFT/SURF, or other strong features for the purpose of object recognition.

But in cartoons or comics, we may extract so few or zero feature(s) following the traditional approaches. Human visual interpretation system is amazingly effective in recognize such abstract objects (e.g. only with 4 lines and 2 curves, we still recognize the familiar character).

So I think the solution must be somewhere in the understanding how human can interpret such a set of line strokes as a meaningful object. Once we understand it we can try to "teach" the computer the same way.

Thus are there some good approaches in the terms of recognition of abstract objects such as drawn comic objects? (I searched for some but they're not so relevant). Thanks.


texts: Best- and worst case for Mergesort using Bubblesort for small lists

texts:
Problem statement:

  Merge sort is so modified that for array sizes below 11, instead of recursive Merge sort, the array is sorted using Bubble sort. Will there be any good and bad cases now? Give an example of each case if you think so; if not, argue why.

My thought process:

I understand that the worst-case complexity of bubble sort remains the same as its average-case complexity, but since it is not specified as to how to categorize the "worst case" (only according to its worst-case complexity or even considering least comparisons), I also considered having the least number of comparisons.

For Merge sort, I understand that the worst case will arise when the elements in the merged array are selected alternatively from the two sub-arrays.

So, for an array size of, say 24, I produced the following array -

24, 20, 16, 12, 8, 4, 23, 19, 15, 11, 7, 3, 22, 18, 14, 10, 6, 2, 21, 17, 13, 9, 5, 1

In the first iteration of Merge sort, there will be two sub-arrays of length 12 each. Since this is more than 11, Merge sort is recursively called again.

At some point, we will have four sub-arrays of length 6. At this point Bubble sort will be applied to each of them and they will be recursively joined by Merge sort. The four sub-arrays will be -

[24, 20, 16, 12, 8, 4], [23, 19, 15, 11, 7, 3], [22, 18, 14, 10, 6, 2], [21, 17, 13, 9, 5, 1]

Now each of these present a worst-case for Bubble sort, since all have their elements in descending order. Now lets say the first two arrays are sorted using Bubble sort and merged, they will present a worst case for Merge sort as during the merge operation each element will be alternatively chosen from the two sub-arrays. Similarly, the last two sub-arrays are sorted using Bubble sort and merged.

Is this array a correct example of the worst case of the above problem? Or am I wrong in deriving this conclusion?


texts: Why do we need binary trees when we have multi branch trees?

texts: Why do we need binary trees when we have multiway trees. Are binary trees even used. Are they used only for teaching the concepts of trees?


texts: generation-compare-and-swap, or GCAS, in CTries

texts:
The data structure is used for example in Scala:
https://github.com/scala/scala/blob/v2.12.0-M3/src/library/scala/collection/concurrent/TrieMap.scala

More details in this paper:
http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf

The logic I'm confused about is on line 139 in Figure 11 on page 6 of ctries-snapshot.pdf

The code checks if the generation of the root node is the same as the current node before proceeding. To quote the paper,

  The idea is to communicate the intent of replacing the value in the
  I-node and check the generation field in the root before committing
  to the new value

This is the last sentence of the second paragraph in section 4.1 on page 6. The root generation is changed for example when a snapshot is taken (Figure 7 on page 15).

The question is, I don't see any synchronization mechanism that would prevent updates to the root right after the generation check. To use the papers own words, how is "the intent of replacing the value in the I-node" communicated to other threads attempting to update the root node through snapshots? From what I can tell, the root and the I-node in question can be two distinct nodes, and I'm not sure how the CAS's surrounding the generation check can prevent a race.


texts: Classification and complexity of generating all possible combinations: P, NP, NP-Complete or NP-Hard

texts:
The algorithm needs to generate all possible combinations from a given list (empty set excluded).
list          =>         [1, 2, 3]
combinations  =>         [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]

This algorithm would take O(2n) time complexity to generate all combinations. However, I'm not sure if an improved algorithm can bring this time complexity down. If an improved algorithm exists, please do share your knowledge!
In the case that it takes O(2n) which is exponential, I would like some insight regarding which class this algorithm belongs to P, NP, NP-Complete, NP-Hard, or whether it does not belong to any of them. Thanks in advance :)


texts: How does this answer for automata and Hamming distance not lead to inconsistencies?

texts:
I had already been given the answer by the TA in class, but I don't understand it. I'm not asking for the answer on a homework problem or anything.

The problem:

The Hamming distance ("distance") of a word w to v of the same size is the number of positions wherein they differ. The distance between a w and L is the smallest such distance from a word chosen among L.

Let k be a natural number, and L a regular language. L' is the set of words w at a distance not greater than k from L. Show that L' is regular.

The way to go about this was to construct an automaton for such an L', and to do induction on k. If k = 0, then L' = L0 = L, and M0 = (Q0, E, delta0, q0, F0).

In general

Q is the set of states for an automaton accepting words with a distance at most k.
E is the alphabet among all machines and languages.
d is the tranisition function of Mk,
q0 is the start state for Mk
F is the set of final states for Mk.

The answer, according to the TA:

Assuming that the construction is valid for all i <= k, we can form M' as follows:

Q' = Q x {0, 1}, and **q'** is an element of Q'

q0' = (q0, 0)

d'((q, 0), a) = {(d(q, a), 0)} u {(d(q, b), 1) | b element of E}

d'((q, 1), a) = {(d(q, a), 1)}

F' = {q' = (q, t) | t = 0 or t = 1}

I really don't get this. To me, it seems that if I start off with less than k+1 errors then I'll be in a state (q1, 0) for some q1, and if I read 1 error then I'm put in a state (q2, 1) for some q2. If I am in a state (q1, 1) for some q1 and read anything, then I'll be in a state (q2, 1) for some q2.

If I start with reading the first letter of any input, then I start in (q0, 0), and if I read one error then I'm in (q1, 1), and if I read 50 errors then I'm in (q, 1) for some q, but if we wanted k to be, say, 5, then I've surpassed that.

I'm really confused here. I'd appreciate any help.

Thank you.


texts: Choosing a subset of binary variables to maximize the sum of the highest $K$

texts:
Consider the following problem:

Input:

integers $n > m > k$;
$n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$;
$n$ numbers $r_1, \ldots, r_n$ where ($r_i \geq 0$).

Let $X_1,\dots,X_n$ be $n$ independent random variables with distribution $X_i \sim \text{Bernoulli}(p_i)$  and define $Y_i = r_iX_i$.

Output: a subset $S$ of $[n]$ of size $m$ that maximizes
$r_S = \mathbb{E}[Z_S]$, where $Z_S$ is the random variable $Z_S = \max_{T \subseteq S, |T|=k} \sum_{i\in T} Y_i$.

In other words, we want to select $m$ $Y_i$s such that the expected value of the sum of the largest $k$ of them is maximized.

Can this problem be solved in polynomial time?
Or is it NP-hard?
Is there an efficient $\alpha$-approximation algorithm?

Example:
Input:

$n=3, m=2, k=1$
$p_1=1.00, p_2=0.10, p_3=0.01$
$r_1=2, r_2=11, r_3=100$

Output: the correct output is $S = \{1,3\}$.  Why?

$r_{\{1,3\}} = 2.98$: if $X_3=1$, then $Z_S=100$ (since $T=\{3\}$ in this case), otherwise $Z_S=2$ (since $T=\{1\}$ in this case), and thus

$$r_{\{1,3\}} = \Pr[X_3=1] \times 100 + \Pr[X_3=0] \times 2 = 0.01 \times 100 + 0.99 \times 2 = 2.98.$$
$r_{\{1,2\}} = 2.9$: if $X_2=1$, then $Z_S=11$, otherwise $Z_S=2$, and thus

$$r_{\{1,2\}} = 0.1 \times 11 + 0.9 \times 2 = 2.9.$$

I have been working on this for a while now.
As the example above demonstrates, the obvious greedy approach of selecting $Y_i$s with largest expectation does not work.
I solved the special case of $k=1$ using dynamic programming.
But my guess is that the general case is NP-hard.

Note that the value of of $Z_S$ depends on $S$ and the values of $Y_1,\dots,Y_n$: given $S$, the random process is that we randomly pick the values of the $X_1,\dots,X_n$, compute the values of $Y_1,\dots,Y_n$, then based on the values of $Y_1,\dots,Y_n$ we find the set $T$ of size $k$ that maximizes $\sum_{i \in T} Y_i$, and let $Z_S$ be the result (i.e., we let $Z_S$ be the sum of the $k$ largest values from $Y_1,\dots,Y_n$).  This is why just choosing the $k$ $Y_i$'s whose expected value is largest does not yield the correct result.


texts: optimize string search on black-box function

texts:
Given a lower-bound predicate function which returns true if an input is greater than or equal to a constant string, what is the optimal way to search for the constant? The strings should be lexicographical compared.

For example, given a handle to the following function, but not knowing the specific constant used:

fn lower_bound(s: &[u8]) -> bool {
    s >= &[10, 20, 30]
}

What is the optimal algorithm for determining the enclosed value of &[10, 20, 30]?  A maximum length for the value can be assumed if that makes it more tractable.


texts: Diffie-Hellman and its disadvantage with large primes

texts:
I was reading our university slide on the Diffie-Hellman where it is mentioned that one of the disadvantages of D-H is that For large prime, $p-1$ is an even number so, $\mathbb{Z}^*_p$ will have a subgroup of order 2

What does this statement mean?


texts: Inserting values at maximal distance from current value

texts:
I have the following problem.
Given an array A, filled with 0s, we should set some elements to be equal 1, considering such rules:

If all elements equal 0,set A[0] to 1
Next 1 should be set at maximal distance from any other 1s. At this
stage it will be A[size-1].
In case of equal distances, set 1 at the element with equal distance
AND with smaller index.
At any point of time, any 1 could be set back to 0 at random

Consider an example:

0000000 // initial
1000000 // just first
1000001 // second
1001001
1101001 // all given opportunities have distance 0 to any other 1, so pick up the smallest index
1111001 // again the smallest index
1110001 // we replaced a random 1 with 0
1110101 // at this step we have location with distance 1, so use it!

Input: a sequence of additions/removals of 1s.

Expected output: a sequence of accessed indices at each step.

My question is: how to compute index for a next request? Removals are trivial and it's not interesting (there is some bookkeeping, which is out of the problem's scope), but what about additions? I don't think that you can use dynamic programming or other approaches to compute next index from scratch because of randomized removals.

My idea is to maintain something similar to an interval tree, where each node correspond to 1, left subtree correspond to an interval to the left side, right subtree to right, but it lacks some important details.

Are there any already known approaches/algorithms to this problem? Or how should I proceed with my interval tree idea?


texts: Scheduling m independent jobs on n workers to optimize total run time

texts:
I have a scenario, in which I have m independent jobs to be schedule on n workers parallely. Time required by each of these jobs is known. The problem is how to distribute these m independent jobs such that the total run time of completion of all the m jobs by the n workers is minimum.

One ad-hoc greedy approach I can think of is to sort the jobs by their run time and assign the jobs to workers such that each of them have almost similar run time for job completion.Is there a better approach?
Thanks


texts: How to reduce halting problem to the problem of whether a Turing Machine accepts infinitely many inputs?

texts:
The language $\{w \mid w \in \{0,1\}^{*}\text{ and }M_w\text{ accepts infinitely many inputs}\}$ is undecidable, where $M_w$ is the Turing machine represented by $w$.

I am confused because I do not know how to reduce this problem. Maybe it works with the complement of the Halting problem?


texts: What is the difference between quantum computing and parallel computing?

texts: Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the difference or how are they different?


texts: What is the difference between Multiprogramming and Multitasking

texts:
I am finding it difficult to clearly differentiate between Multiprogramming and Multitasking.

My primary source has been Wikipedia, but the WP article seems to be a little at odds with some less reputable sources (like my college professor).

As I read WP, multiprogramming is a rudimentary way of increasing CPU throughput, by context-switching when a process waits for I/O.

  Multiprogramming doesn't give any guarantee that a program will run in a timely manner. Indeed, the very first program may very well run for hours without needing access to a peripheral.

Cooperative Time-sharing, synonymous with Cooperative Multitasking, is an improvement on multiprogramming (with which it is not synonymous). The CPU context-switches regularly to give the impression of simultaneous execution, but processes are still required to yield - and poorly designed programs can starve the rest of the system.

Preemptive Multitasking takes more aggressive control of scheduling, giving priority to some processes over others, etc.

Is this overview correct? If not is that because WP is incorrect or because I read WP wrong?
Why do some sources seem to conflate multiprogramming and multitasking?


texts:
Let's say I have three classes, Animal, Bird and Pigeon. If Bird extends Animal and Pigeon extends Bird, is Animal the parent class for both or is Bird?

So, for instance, if the constructor for Animal said "hi I am animal" and the  constructor for Bird said "hi am I bird", which will it say in class Pigeon if I call the super constructor?


texts:
I am studying formal language theory and have been asked to prove the following:

$\forall L, L^*=(L^*)^*$

I've started with

$def. L^* = \bigcup_{i \in \mathbb{N}} L_i, L_0=\{{\epsilon}\}, L_1=\{L\}, L_{i+1}=\{uv|u\in L_i, v\in L\}$

$then (L^*)^* = \bigcup_{i \in \mathbb{N}} L_i^*, L_0^*=\{{\epsilon}\}, L_1^*=\{L^*\}, L_{i+1}^*=\{uv|u\in L_i^*, v\in L^*\}$

$L^*L_0^*\in(L^*)^* = L^*\epsilon^* = L^*$ $\therefore L^* \subseteq (L^*)^*$

$L^*L_0^* = L^*, L^*L^*_1 = L^* (def), L^*L_{i+1}^*=L^*_iL^*=L^*L^*$ but the * operator is closed under concatenation, thus, $L^*L^* \in L^* \therefore (L^*)^* \subseteq L^*$

$\therefore L^* = (L^*)^*$

I simply don't have an intuition on whether this attempt at a proof is correct and I would appreciate any insight about it since the subsequent problems are to show $L^+=(L^+)^+$ and then to argue whether $(L^*)^+=(L^+)^*$


texts: find internal rhombi from a list of lines defined by point tuples

texts:
I have a image like this:

I have code to extract the lines in the form [x1,x2,y1,y2]
Now i need to extract the internal rhombi, one could bruteforce combinations and check for intersections easily, but I was hoping a named, optimal algorithm existed, as the combinatoric explosion would ruin the server,

Any help appreciated


texts: What does it mean that numbers are "totally ordered", in the Paxos Made Simple paper?

texts:
I was studying Paxos from the paper by Lamport called "Paxos Made Simple".

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

On page 3, it says

  Since all numbers are totally ordered, condition P2 guarantees the crucial safety property that only a single value is chosen.

where P2 is the following

  If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

What does it mean for numbers to be totally ordered? How is this property essential for condition P2 to guarantee safety?


texts: Turing machine that does not halt on any input

texts:
I'm struggling to find a way to show that
$$T = \{ \langle M \rangle\mid M \text{does not halt on any input}\}$$
is undecidable.
Should I use reduction? If so, reduce this to what &ndashp the halting problem?


texts: Data Compression: Which one is Better "Compress before Encrypt" or "Encrypt before Compression"

texts: Which one is better approach do data compression before encrypting it  or Encrypt data before compression ? I think it is biased towards the application requirement.  Please share your views.


texts: Hamming connectivity of regular languages

texts:
Call a language $L$ Hamming connected iff, for every pair of strings $x, y \in L^2$, where $|x|=|y|$, $x$ may be transformed into $y$ by a sequence of single symbol in-place replacements, so that after every replacement, the resulting string is in $L$.

Is Hamming connectivity a decidable property for regular languages? Note that the brute-force algorithm of checking all string lengths fails, as $L$ may contain infinitely many strings.

Example:

Define $L$ on the binary alphabet to be the set of strings that do not contain $101$ or $010$ as a substring. $L$ is regular. We now show that $L$ is Hamming connected.

Informal Proof: We can grow internal "runs" out to the ends to transform any string in $L$ into the all 1's or all 0's string without creating a forbidden substring, e.g., 001100 -> 011100 -> 111100 -> 111110 -> 111111. This transformation can also be done in reverse to reach any string. Thus, $L$ is Hamming connected.


texts: Least squares fit of a 1D lattice of points to a 2D dataset

texts:
Given a set of data points (shown in red), it is possible to fit a line $y = mx + c$ through the points using linear least squares regression.

I would like to modify this to fit a 1D lattice (grid) along the line such that $d$ is the offset of the the grid along the line and $i$ is the interval between neighboring grid points along the line.

An additional constraint is that more or less the same number of data points should be in the neighbourhood for each grid point in order to prevent picking an arbitrarily small $i$ and overfitting the data.

I believe that calculating the mean square error on a solution can be simple. The squared distances of all of the data points in the neighbourhood of the grid point would be:

$$mse = \sum_{j = 0}^{g} \sum_{k = 0}^{h} distance^2(\vec{latticePoint_j}, \vec{dataPoint_{j,k}})$$

(Where $g$ is the number of clusters and $h$ is the number of points inside the grid point's neighborhood.)

However, I'm not sure how to go about solving for all four variables $m$, $c$, $d$ and $i$ since I'm left with a discrete function. My hope is that since $i$ is fixed and points are distributed reasonably evenly among the clusters this could be done without invoking an overly complicated clustering algorithm.

The number of clusters are not known ahead of time and may contain outliers. Any help is much appreciated.


texts: More efficient vertex-labelling algorithm than BFS?

texts:
I am using the C++ boost library implementation of the push relabel algorithm to solve a max-flow problem. The output from that algorithm is a residual graph and in order to find the min-cut of my original graph, I need to find all of the vertices which are reachable from the source vertex in the residual graph.

I was planning to use BFS or DFS to traverse the residual graph, but I was wondering if there was any more efficient algorithms that anyone can suggest, as the size of my graphs are pretty large.

I plan on implementing my own, modified version of the push relabel algorithm eventually, and then I can probably label them as I go. But for now I would like to just run it with the boost library, so that I have something for comparison - but unfortunately that requires labelling the vertices separately.

Any suggestions would be greatly appreciated


texts: Proof of the base case of Big Theta using induction

texts:
Here is a recursive definition for the runtime of some unspecified function. a and c are positive constants.

$T(n)=a$, if $n=2$

$T(n)=2T(n/2)+cn$ if $n>2$

Use induction to prove that $T(n)=\theta(n\log(n))$

How should I do my base case? It is not a number, so how do I find my n0?


texts: I know Binary Search is more efficient than Ternary search, but my results are opposite. Help interpreting results?

texts:
I have a piece of code that applies recursive Binary and Ternary searches on sorted arrays of increasing size, i.e. 500, 1000, 2000, 4000, etc. The entire code segment is about 200 lines so I've been forced to upload it to Pastebin which you can find here. When the main method is executed, arrays are created and populated according to some heuristic, which here happens to be A[i] = 8 * sqrt(i). The arrays are then searched to see if they contain a key that's randomly generated and may or may not be in the array.

I've ran the tests over a dozen times and each time, the ternary search outperforms the binary search in terms of average comparisons needed before finding the key or knowing that it's not in the array. Shouldn't Binary Search have fewer comparisons if it's a better complexity (log(2) (n) instead of 2*log(3)(n))? Are my sample sizes too small or have I made a mistake in my code somewhere? For example, here's some sample output:

Binary search results:

Average number of comparisons for array of size 500: 7.4
Average number of comparisons for array of size 1000: 7.0
Average number of comparisons for array of size 2000: 8.1
Average number of comparisons for array of size 4000: 9.3
Average number of comparisons for array of size 8000: 9.0

Ternary search results:

Average number of comparisons for array of size 500: 4.6
Average number of comparisons for array of size 1000: 7.0
Average number of comparisons for array of size 2000: 5.3
Average number of comparisons for array of size 4000: 5.9
Average number of comparisons for array of size 8000: 6.0

Note: The 'y' variable in the code is the number of comparisons, this is an assignment and that's what it's supposed to be named as per the specs.


texts:
I've posted this question first on StackOverflow but this section seems more suited for this kind of questions.
Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll figure out the regular expression I'll derive the equivalent Finite Automaton that accepts the language generated by the grammar), but instead I'm trying to understand the methodology to derive regular expressions (if they exists, from context-free grammars)

I have this productions of a context free grammar (axiom S, e is the empty word)

S->AS|b|A
A->abA|Ab|e
I have to figure out a regular expression (if exists) that generates a language equivalent to the one generated by that grammar.

So far i wrote that

L(S)=L(A)L(S) + b + L(A) = L(A)*(L(A) + b) (by Arden Rule)
L(A)=(ab)*(L(A)b+e)

I've tried the method of finding the fixed point (I'd like more info about that since seems I can't get the hang of it

for A: 0 -> e -> (ab)*(b+e) -> (ab)*[(ab)*(b+e)](b+e)

should i check if (ab)(b+e) = (ab)(ab)*(b+e) (if that's is the fixed point? Or should i go ahead?) It's not the first exercise I'm having trouble with so any help would be appreaciated, Thanks.


texts: Randomized communication complexity of indexing

texts:
The function $\mathrm{INDEX}:\{0,1\}^n\times\{1,\dots,n\}\to \{0,1\}$ is defined as

$$\mathrm{INDEX}(x,i)=x_i,$$
where $x=x_1\dots x_n$. I am looking for the randomized communication complexity of $\mathrm{INDEX}$ for an arbitrary number of rounds.

Somehow, I do not manage to find it in the literature.

The deterministic communication complexity is known to be $\Theta(\log n)$, while its one-way randomized communication complexity is $\Theta(n)$.

I guess the randomized communication complexity is still $\Theta(\log n)$, I was not able to find a lower bound.

Since this function its well-studied, it should be stated somewhere.

Thanks for your help.


texts: Finding an element in a sorted array with at most three queries to larger elements

texts:
Given a sorted array A, we have to find the position of an element m in it. (It is also given that the element exists in the array.)

However there is a constraint. Like in a game you have 3 lives. If you probe any element x > m in the array you will lose one life. You can probe as many elements you want which are smaller than m. If you find m, you win.

The solution to this should not be in linear time.

What I tried:

I will drop eggs from floors 1, 2, 4, 8..
And in log n time, I will find a sub-array in which m exists (at cost of 1 life). But this sub-array was of size at most n/2. I cannot repeatedly apply this process since, I have limited number of lives.

My thoughts

I am thinking that a solution does not exist to this problem which is faster than linear. How to prove this (if this is the case)? Can I create a contradiction from the assumption that a solution exists?


texts:
I recently started self-learning about GNNs, and I have trouble understanding the difference between the GNN models.
As I understand it, all GNN models apply an aggregation step on each node, and the different models differ in the aggregation function.

Is the aggregation for a single node done by aggregating the entire graph? or only its close neighbors?
What is the difference between GraphSAGE and other GNN models? Do I understand correctly that GraphSAGE aggregates only some of a node's neighbors and not all of them?


texts: Grammer Class/Production Rules of Programming Languages

texts:
I'd read around on the interwebs, and a lot of the text indicated that many programming languages are generated by a context-free grammar, which leads me to 2 questions:

Doesn't variable scoping require a context-sensitive grammer?  Particularly, I'm thinking of the following valid C code:

int main(){
    int count=0;
    count++;
    return count;
}

As opposed to the following invalid C code:

int main(){
    count++;
    int count=0;
    return count;
}

There could also be some other stuff involving namespaces and classes for C++, or the '.' operator for C structs, for example.  I get the impression that, as a result, C (and various descendents) does (do) have context-sensitive aspects (though this may only be partial context-sensitivity).  Thus question 1:

Is it correct to say that C and some derivative languages, as well as some other languages, can only be generated by grammars with a minimum of context-sensitivity?

Secondly is there a relationship between language class and grammar class?

Particularly, I'm thinking of the language BrainF*** when I ask, since its syntax is clearly generated by a context-free grammar, yet its implementation is turing complete (assuming an implementation with an infinite tape).  Does this mean that there are languages that have regular grammars, yet are turing complete?


texts:
A "Flow Free" puzzle consists of a positive integer $n$ and a set of (unordered) pairs of distinct vertices in the $n \times n$ grid graph such that each vertex is in at most one pair. A solution to such a puzzle is a set of undirected paths in the graph such that each vertex is in exactly one path and each path's set of ends is one of the puzzle's pairs of vertices. This image is an example of a Flow Free puzzle, and this image is an example of a solution to a different Flow Free puzzle.

Is the problem "Does there exist a solution to this Flow Free puzzle?" NP-hard? Does it matter whether $n$ is given in unary or binary?


texts:
This was from a test from my university:

Consider $T = t_1, t_2, \cdots, t_n$ a set of intervals of the form $(s, e)$, representing the start and end time, respectively. Now, select the minimum number of intervals such that their "union" intersects all other intervals. The question then asked for an optimal greedy algorithm.

From what I can see, this is a vertex cover problem (each interval is a vertex; draw an edge between each pair of intervals that intersect), which is NP-complete on general graphs.

Consider $W(i)$ the number of intervals intersecting $i$, and $M$ a set of intervals already covered. Here is my solution:

Order $T$ by $W$ and insert in $T_{ord}$;
If $T_{ord} = \emptyset$ terminate
Remove the first element $e$ from $T_{ord}$;
If $e \in M$ go to $2$;
Decrease $1$ for every element $e^{'}$that intersect $e$, and $M \cup\{e,e^{'}\}$;
Order $T_{ord}$ and go to $2$.

I managed come up with a greedy solution, but couldn't come up with a counterexample. Given that, I was thinking if this is a special case of the vertex cover problem. Is it?


texts: Which non convex optimization algorithms guarantee a global optima?

texts:
Most non-convex optimization algorithms I have come across so far rely basically on random restart to find a better solution. e.g. Genetic Algorithm, Simulated Annealing, Metropolis Hastings Monte Carlo. Even in Stochastic Gradient Descent we can think of training each batch as a random perturbation.
There are some non-statistical algorithms in Dynamic Programming and Backtracking which can guarantee global optima, but I havent found any literature that works on noisy data.
What are the strategies which algorithms use (other than random restart) to get out of the local optima and search for the global optima for noisy data?


texts: Tag-free garbage collection for object oriented languages

texts:
I'm looking around for a good garbage collection technique for my language and found this paper, where Benjamin Goldberg describes a garbage collection technique for strongly typed languages, which removes the need for type information during runtime.

Briefly, this is done by placing a pointer to a garbage collection function right after a function call, directly in the compiled code. They then extend this to support ML-like parametric polymorphism.

Now my question: Has there been any work on how this technique could be implemented in an object oriented language, where much functionality is implemented through indirect calls using pointers in a virtual table?


texts: Minimize Manhattan distance travel algorithm

texts:
I am trying to find the name of an algorithm for a game I am making. I am pretty sure it exists, but I have no idea what name it has.

Say I have a matrix like:

$$
\begin{array}{|r|r|r|} \hline
    \hphantom{-}1 &  -1 &  0 \\\hline
    0 &  0 &  1 \\\hline
    0 &  1 & -2 \\\hline
\end{array}
$$

I know that the sum of each element of the matrix is zero.

And an operation $f$ which sums two elements of the matrix together and replaces both of them with this sum. In our example  $f( a_{1,1} a_{1,2} )$ (where $a_{r,c}$ is the element of the matrix at row $r$ and column $c$) would lead to

$$
\begin{array}{|r|r|r|} \hline
    \hphantom{-}0 &  \hphantom{-}0 &  0 \\\hline
    0 &  0 &  1 \\\hline
    0 &  1 & -2 \\\hline
\end{array}
$$

The cost of this operation is the Manhattan distance between the two points, in this case $1$.

Now, I want to find the moves that:

make each element of the matrix go to $0$
minimize the total cost

Is there an algorithm (or a combination of them) that does that? Sorry for the laymen lingo, I am not a programmer myself!


texts: Should crossover operation in a genetic algorithm modify individuals in order to be "valid"?

texts:
I'm working in a project to create levels for a videogame using genetic algorithms.

I'm using a undirected graph to represent the level, each node represent a room and each room have a maximum of four possible connections (north, south, east, west). Also each connection just have one compatible connection (North <=> South , East <=> West), this mean you can't connect North with East for example, or North with North (Also a room can't be connected with itself).

Anyway, I already have a way to create the initial population with thoses restrictions, but now I'm thinking about the crossover function.

Let's say I crossover two graphs by cutting them in half and merging those halves, there are chances for a room to have more than four connection or using the same connection to connect two differents rooms.

So my question is, Should I create a crossover method to respect thoses restrictions or just to lower the score of thoses individuals?


texts: Algorithm for finding cycles in a hypergraph

texts:
Define a hypergraph as a set $V$ of vertices and a set $E$ of hyperedges, where a hyperedge is a non-empty subset of $V$. (This is a generalisation of an undirected graph, in which edges are allowed to connect any number of nodes, rather than just two.)

Define a cycle in a hypergraph as a cyclic sequence $C$ of vertices $v_0,v_1,\dots,v_n,v_0$, such that

(i) there is no hyperedge that includes all of the members of $C$; and

(ii) for every adjacent pair of vertices in $C$, there is a hyperedge that includes them both.

I'm looking for a simple and straightforward algorithm to detect whether any given hypergraph has a cycle. I feel like it should be obvious but it's not coming to me.

In case it helps: the hypergraphs I'm dealing with are reduced (meaning that no hyperedge is a subset of any other hyperedge), and also have the property that there is at least one hyperedge that contains each vertex.