texts: Formulating the master theorem with Little-O- and Little-Omega notation

texts:
In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this:

  Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \mathbb{R}$ where $T(n) = aT(\frac{n}{b}) + f(n)$, then
  $ \\ T\in\left\{\begin{matrix}
\Theta(n^{\log_b{a}}), & \text{ if } f \in O(n^{log_b{a}-\epsilon}) \text{ for some } \epsilon > 0. \\
\Theta(n^{\log_b{a}} \log{n}), & \text{ if } f \in \Theta(n^{\log_b{a}}). \\
\Theta(f), & \text{ if } f \in \Omega(n^{\log_b{a}+\epsilon}) \text{ for some } \epsilon > 0 \\
& \text{ and if the regularity condition holds. }
\end{matrix}\right.$

When I first had to study this theorem, I found that for me personally, the meaning of $\epsilon$ was somewhat difficult to understand and memorise. I believe to have found a simpler way to write this theorem, and I am wondering if it can be used equivalently, or if there is a flaw in my reasoning.

Let's look at the first case in particular, $f \in O(n^{log_b{a}-\epsilon})$. For simplicitly, let's assume $\log_b(a) = 2$. If we choose an infinitesimally small value for $\epsilon$, then this case basically expresses that $f$ must be asymptotically less than or equal to $n^{1.999 \ldots}$. In other words, $f$ must be asymptotically strictly less than $n^2$. I am wondering if this means that we can write this first case of the theorem as $f \in o(n^{\log_b{a}})$ (and following the same logic, $f \in \omega(n^{\log_b{a}})$ for the third case), rather than the (IMO) more convoluted alternative?


texts: Undecidable problems limit physical theories

texts:
Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual circuit based construction. Then there can be no decidable physical theory which can determine, given any input setting of the circuits, whether the circuit will halt. This seems a triviality, but doesn’t this give us a weak sort of unpredictability without reference to quantum or chaotic considerations? Moreover we can strengthen the above argument by noting that there is nothing special about the circuit based UTM, so we have that the behavior of a physical system is in general undecidable at any level where a UTM can be constructed.

Edit: as pointed out by both Babou and Ben Crowell, my suggested circuit construction is merely an LBA. As I argued in the comments, I find it easy, and intuitive to imagine a machine which is physical but is not linearly bounded. Simply construct a machine (robot) which can mechanically move left/right on an input arbitrarily many times, and assume it has a finite, but non expiring power source. Now we also run into the problem that the universe is finite, but that lets us conclude either that the universe is finite, or the originally hoped for consequence must be true (that would still be a surprising conclusion to arrive at from the above argument).


texts: Why are regular expressions defined with union, concatenation and star operations?

texts:
A regular expresssion is defined recursively as

$a$ for some $a \in \Sigma$ is a regular expression,
$\varepsilon$ is a regular expression,
$\emptyset$ is a regular expression,
$(R_1 \cup R_2)$ where $R_1$ and $R_2$ are regular expressions is a regular expression,
$(R_1 \circ R_2)$ where $R_1$ and $R_2$ are regular expressions is a regular expression,
$(R_1)^*$ where $R_1$ is a regular expression is a regular expression.

This definition is taken from page 64 of

  Sipser, Michael. Introduction to the Theory of Computation, 3rd edition. Cengage Learning, 2012.

Now, I have the following questions.

Why do not the definition contain the intersection, complement or reverse operations?
If we change the 4th item to $R_1 \cap R_2$, do we get an equivalent definition, i.e. for each regular language, there is a modified regular expression and vice versa?
I know that this definition is complete and well-defined, but why is it preferred to other equivalent, well defined and complete definitions?


texts: I know that Assembly is the lowest level of the stack besides machine code, but are the languages above it all considered "high level languages" or is there a hierarchy amongst these languages. For instance, are C++, Ruby, and Python all "high level languages"?


texts: Ideas for CS-related challenge for teams of high school students?

texts:
I am helping design a CS-related activity for a Let's Talk Science competition, which promotes STEM amongst high school students. In the competition, teams of six students will move from station to station, trying to complete each as quickly as possible.

One station might give the team a metre stick, then ask them to measure the height of a building. (This can be solved by using similar triangles to estimate the building's height.) Time penalties are added to the team's completion time depending on how close their answer was.

My constraints are thus:

Most students won't have CS/programming knowledge
Challenge should not require a computer
Idea should challenge teams of six students for 15-20 minutes
Challenge must have clear answer that can be objectively scored (not judged)

One reasonably good challenge presents a sentence encoded with a Caesar cipher, then asks the students to decode it. The person running the station give a short explanation of what a Caesar cipher is, then leave the teams to decode the text. Time penalties are awarded based on correctness -- each incorrect character adds a 30-second penalty.

The Caesar cipher idea has been used often in the past, however, and I'm trying to develop something novel. I have been through the various activities on CS Unplugged, but none appealed to me -- the exercises I saw were generally aimed at illustration and not suitable for competition, were too simple, or required too much explanation of background knowledge.

Do you have any ideas on what would make a fun CS-related challenge for teams of six high school students?

Thanks!


texts: Deciding whether the language of a CFG equals some specific regular language

texts:
I was wandering if $L = \{\langle G \rangle \mid \ G \text{ is a context free grammar and } \mathcal L(G) = A \}$ is decidable where A is a some regular language. Is
$L' = \{ \langle G \rangle \mid \ G \text{ is a context free grammar and } \mathcal L(G) = \overline A \}$ decidable ?  I feel like $L'$ should be decidable, but can't see how. Or does it depends on $A$?


texts:
Decide whether the language $L$, defined by the following grammar is regular or not:
$S \rightarrow aab$
$S \rightarrow aacSb$
$S \rightarrow acSab$
$S \rightarrow acSacSb$
Where should I start?
I have tried defining a new language $L' = \{(aac)^n\ w\ b^n | w \in L\}$, which should be non-regular, because of dependency on $n$ with different left and right sides and since $L' = L$, $L$ has to be non-regular too, but I'm not sure whether this technique is valid.


texts: What is the difference between $ \alpha \to \alpha $ vs $ \forall \alpha. \alpha \to \alpha$?

texts:
I was studying polymorphic types and I was finding the distinction with monomorphic types difficult to pin down (context CS 421). From the course I linked the have the following (vague attempt) at a definition:

  Monomorphic Types ($\tau$):

  Basic Types: $int,bool,float,string,unit, \dots$
  Type types: $\alpha, \beta, \gamma, \delta, \epsilon$.
  Compund Types: $\alpha \to \beta, int * string, bool list, \dots$

  Polymorphic Types:

  Monomorphic types $\tau $
  Universally quantified monomorphic types
  $\forall \alpha_1, \dots, \alpha_n . \tau $  (Question: is this not just universally quantified monomophism? If not what's the
  difference?)
  Can think of $\tau$ (I assume they mean monomorphic types) the same as $\forall . \tau$

I guess I find MANY things in this definition rather confusing. But was seems to be the core about my confusion is the difference between:

$$ expr: \alpha \to \beta$$

vs

$$ expr : \forall \alpha, \beta . \alpha \to \beta$$

I don't understand why they are not the same. What is the difference?

After writing this question I have some ideas of what might be going on and want to double check. Is what is going on that $\alpha \to \beta $ (the first one) saying that the expression $expr$ has a monomorphic type as its type (so it just has a real "fixed" type as a type)... Perhaps what's confusing me are type variables. Because nothing can be of a type "type variable". Type variables are just (meta) variables that can later be filled in with a real "basic type", right? So $\alpha \to \beta$ in my first example just stands for "some function type from one type to another but we have not decided which type to choose later, but the expression really just has a fixed basic type as a type once used in a real programming context". Is that right? So saying $fun x \to x$ has type $\alpha \to \alpha$ when reasoning in the meta-theory just means that the function really just has a fixed basic type except we have not specified it. While saying (in a more expressive type system) that $fun x \to x$ has type $\forall \alpha . \alpha \to \alpha$ means that that expression actually has the capability of encompassing all the monomorphic types at once. i.e. in the monomorphic version we actually have to define each identity function separately for each type (for the sake or argument) while in the polymorphic version we have only have 1 single programming construct for all of them...so the type variable basically just stands for a real monomorphic type (at least in the context of this definition).

I guess if we allowed type variables to be anything, then I'd be confused...I think my main worry is about type variables.

More rambling cuz I'm confused:

Lets look at this from FOL or as if we were trying to construct or define what an L-term is with an L-structure (see mathematical logic MATH 570). I think right now what confuses me is that this mapping between this vague definition of types (that seems to attempt to define an L-term) is not clear to me. Where is the recursion? What is the L-structure? This type definition is vague for me to really believe it. Something like this would be much better:

Related question: What does $ \forall \alpha_1, \dots , \alpha_n . \tau $ mean formally as a type?


texts: Howcome the string "b" is accepted by this nondeterministic finite state automata per the given solution?

texts: Am I correct that the given solution is implying that the string with a single b, "b" is accepted by this NFSA? If so, I don't understand how "b" can end up in the accepting state.


texts: UNDIRECTED HAMCYCLE to HAMPATH reduction

texts:
I'll define the problems

  UHAMPATH

  Input: A undirected graph G and 2 nodes, s and t

  Question: Is there a hamiltonian path from s to t in G?

  UHAMCYCLE

  Input: A undirected graph G

  Question: Is there a hamiltonian cycle in G?

$$UHAMCYCLE \leq_p UHAMPATH$$

my reduction is as followed $(G) \to (G', s, t)$

function(G)

    for each e = (u, v) in E(G)
        G' = G
        add nodes u' and v' to G'
        add edges (u', u) and (v, v')
        s = u'
        t = v'
        if there is a hamilton path from s to t:
            return (G', s, t)

Basically if there is a hamilton cycle in G then some edge in $G$ will form a hamilton path in $G'$.

An example to further illustrate the reduction:

 Graph G

(a) ---- --(d)
 | \        |
 |   \      |
 |    \     |
 |     \    |
 |      \   |
 |       \  |
 |         \|      |
(b) ------ (c)

Has a clear Hamilton cycle (a, b, c, d).

If we choose edges (a, d)

 Graph G'

(s)--(a) ---- --(d)
      | \        |
      |   \      |
      |    \     |
      |     \    |
      |      \   |
      |       \  |
      |         \|
     (b) ------ (c)--(t)

Doesn't have a hamilton path from s to t. However if you choose any other edge such as (a, d) then

(s)--(a) ---- --(d)--(t)
      | \        |
      |   \      |
      |    \     |
      |     \    |
      |      \   |
      |       \  |
      |         \|
     (b) ------ (c)

$(s \to a \to b \to c \to d \to t)$. Holds.

I'm confused whether or not I can use this line:

if there is a hamilton path from s to t:
    return (G', s, t)

Checking to see if a graph has a hamilton path is NP complete but since we are looking to reduce it to it I think we can?


texts: How to maximize the number of buyers in a shop?

texts:
There is a shop which consists of N items and there are M buyers. Each buyer wants to buy a specific set of items. However, the cost of all transactions is same irrespective of the number of items sold. So, the shopkeeper needs to maximize the number of buyers. The buyers will buy only if all the items are being sold. Items are unique. All items need not be sold.

So, basically, we have a bipartite graph. We need to find a set of edges which maximize the number of nodes on Buyer vertex set such that each node on item set has only one edge. Any suggestions?


texts:
There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers.  It uses a median-of-medians approach to find a good enough pivot, partitions the input array in place and then recursively continues in it's search for the $k$'th largest element.

What if we weren't allowed to touch the input array, how much extra space would be needed in order to find the $k$'th largest element in $O(n)$ time?  Could we find the $k$'th largest element in $O(1)$ extra space and still keep the runtime $O(n)$?  For example, finding the maximum or minimum element takes $O(n)$ time and $O(1)$ space.

Intuitively, I cannot imagine that we could do better than $O(n)$ space but is there a proof of this?

Can someone point to a reference or come up with an argument why the $\lfloor n/2 \rfloor$'th element would require $O(n)$ space to be found in $O(n)$ time?


texts: Does the subset sum problem remain $NP$ complete when we increase word size and restrict number of words?

texts:
Is the problem

  'Given $m=\big\lceil{n^b}\big\rceil$ with $b\in(0,1)$ integers $a_1,\cdots,a_m$ each with $\lceil\log_2 |a_i|\rceil=\big\lceil n^a\big\rceil$ with $a\in[1,\infty)$ is there a subset that sums to zero?'

$NP$ complete?

The reason I ask is this problem can be solved in $2^{O(n^b)}=2^{o(n)}$ time.


texts: Finding a maximum-weight base of a a matroid, in reverse

texts:
Given a weighted matroid with positive weights, we can find a independent set with a maximum weight with a greedy algorithm:

Start with an empty set (by definition of matroid, it is independent).
Add an element with maximum weight among all elements whose addition keeps the current set independent (if there are no such elements, terminate).

My goal is to found out whether this approach can also work in reverse. My first attempt was:

Start with a set containing all elements.
As long as the set is NOT independent, remove the element with minimum weight.

This attempt proved to be false. Here is an example:

There are 8 elements, divided to two groups: A and B. The matroid contains all subsets that have at most two elements of each group. The weights are:

Group A: 303,302,301,300.
Group B: 203,202,201,200.

The forward-greedy approach picks 303, 302, 203, 202 - which is optimal. But the reverse-greedy approach removes 200,201,202,203,300,301, and leaves only 302,303.

But, I think the following alternative algorithm should work:

Start with a set containing all elements.
As long as the set is not independent, remove the element with minimum weight among all elements whose removal leaves a base in the current set.

So, in the above example, this algorithm removes 200 and 201, but does not remove 202 and 203 (since then no base will remain), then removes 300 and 301, and stops with the maximum-weight independent set.

I am not sure about the complexity of this algorithm. Particularly, how much time does it take to calculate whether the current set (after removing an element) contains a base?


texts:
The Sieve of Eratosthenes bothers me because you have to specify an upper bound before you begin the algorithm.

Is there a prime sieve that doesn't require this?

More Formally:

Is it possible to write an iterator on which the i'th call to next() yields the prime number $p_i$ in only $O((p_i - p_{i-1})log(log(p_i)))$ time for all i > 1 ?

(Note: I'm looking for a worst-case solution, not amortized.  For amortized time, you can simply use Sieve of Eratosthenes and restart the algorithm doubling n each time you hit the previous upper bound)


texts: Complexity class of problem whose running time features binomial coefficient

texts:
I've built an algorithm that, starting from an array of $n$ cells and an integer value $s$, builds $\binom{n+s-1}{s}$ vectors (that is, all the ways to add a certain $s$ quantity fully distributed among the cells).
Let's assume that this constitutes the space of my "candidates" to be processed by a verifier in $\mathsf{coNP}$.
It can be shown that this is no harder than $\Sigma_2^P$ class ($\mathsf{NP} \cap \mathsf{coNP}$), if I want that at least one of my candidates is "good".
But... Is it any easier?
In general, how can I make myself an idea of how binomial coefficients impact the complexity class of a problem, if they model all the possible candidates to a verifier in some complexity class?


texts:
Given the recurrence $T(n) = T(\sqrt{n}) + \theta(lglgn)$, provide an asymptotically tight bound on it's run time.

My solution was to let $m = 2\sqrt{n}$, which leads to the recurrence $S(m) = S(m/2) + \theta(lg(2lg(m) + lg4)) = S(m/2) + \theta(lglgm)$.

By case 3 of the master rule, this means that $S(m) \in \theta(lglgm)$, because $lglgm \in \Omega(m^{log_2 1})$.

Since $lglgm = lg(lg2 + 0.5lgn) \in \theta(lglgn)$, we have that $T(n) \in \theta(lglgn).$

The provided solution to this problem says that $T(n) \in \theta((lglgn)^2)$, could someone help me find my mistake?

The solution is on page 2 of the below PDF, problem 1-2(d):
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps1sol.pdf


texts:
The Bloom filter data structure requires a set of hashing functions. The Murmur3 family is a great fit, as it contains the seed parameter to easily create a variety of different functions (plus it has good distribution of values and adequate speed).

Choosing the seed

Is there any particular method of choosing the seed values for the Bloom filter application? By selecting them randomly, I give up the deterministic nature of the algorithm and hand-picking these values seems a little bit too brave. Is it known, whether two seed values s1 and s2, where s1 != s2, yield the same function (borrowing a linear algebra term: they would be linearly dependent) ?

Limiting the hash domain

The Murmur3 hash is a 32-bit value. Since the Bloom filter might not need all 32 bits, is it still OK with respect to the uniformity to just apply the modulo function to this value?


texts: Order of growth definition from Reynolds & Tymann

texts:
I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines).

The second chapter introduces algorithms with an example of a sequential search which simply iterates through a list of names and returns TRUE if a given name is found in the list.

The author goes on to say (page 17):

  We say that the "order of growth" of the sequential search algorithm
  is n. The notation for this is T(n). We also say that an algorithm whose order of growth is within some constant factor
  of T(n) has a theta of NL say. "The sequential search has a theta of
  n." The size of the problem is n, the length of the list being
  searched.

I find this really hard to follow. The book is riddled with errors, so I am not sure if I am missing something or if the there is a typo in the paragraph above. In general English I rarely see any sentence end with "...say".

I am very confused.

What does T stand for? The book does not explain. Is it for Time or for Theta?

If "a theta of NL" means "The sequential search has a theta of n." What does L stand for? 'Linear' or 'length'?

I have written to the publishers asking for an explanation. They said they would forward my message to authors. They have not replied. I have also tried looking at other sources but I still get the naggling feeling that I am misunderstanding something - so cannot rest until I have decoded this paragraph.

If anyone has a copy of that book, and has understood that paragraph. Then, I'd appreciate if you could let me know if that paragraph is accurate or explain it in other words. Thanks.


texts: Time complexity of calculating the eigenvalues and eigenvector of a matrix

texts: I know the time complexity of calculating the determinant of a square matrix of order $n$ is $O(n^3)$ (by using standard matrix multiplication). What is the time complexity of calculating the eigenvalues and eigenvector of a square matrix of order $n$?


texts: Has there been any more progress on P vs. PSPACE compared to P vs. NP?

texts: I understand this is a slightly vague question, but there are results for P vs. NP, such as the question cannot be easily resolved using oracles. Are there any results like this which have been shown for P vs. NP but have not been shown for P vs PSPACE, so that there is hope that certain proof techniques might resolve P vs PSPACE even though they cannot resolve P vs NP? And are there any non-trivial results that say that if P = PSPACE then there are implications that do not necessarily hold under P = NP? Or anything else non-trivial in the literature that suggests it's easier to prove P != PSPACE than it is to prove P != NP?


texts: unambiguous context-free languages and complementation

texts:
I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages:

Is the complement of an unambiguous context-free language also a context-free language?
If a language is context-free, and its complement is context-free as well (i.e., a so-called strongly context-free language), is it the case that the language is unambiguous context-free?

The first question above is motivated by the fact that it holds for deterministic context-free languages, which are a strict subclass of the unambiguous context-free languages.


texts: Detection of redundant boolean constraints

texts:
I'm trying to solve a constraint programming problem using a SAT solver. I have set of constraints in the form of propositional logic statements, which are converted to CNF using Tseitin transformation. From the nature of my problem I know that there are redundant constraints. For example, I have a rule:
$$AND\:(OR\: (x1,x2),\: OR\: (x3,x4)) \,\,\,\,\,\,(1)$$

and another:
$$AND\:(OR\: (x1,x2),\: OR\: (x3,x4), \:OR\:(x5,x6))\,\,\,\,\,\, (2)$$
where $x_i$ are inputs. Both constraints have in common subnodes, for example $OR (x1,x2)$. Due to this I know that there is no point in having both constraints - if the first one becomes FALSE, then the second equals FALSE too. So the second one is redundant. This example is the easiest. One more, closer to what might be found in my formula:
$$AND\:(x1,\:x2,\: OR \:(AND \:(x3,x4), \:AND\:(x5,x6)))\,\,\,\,\,\,(3)$$
and the second one:
$$AND\:(x3,x4)\,\,\,\,\,\,(4)$$
In this case, I can simplify the first one to the form of:
$$AND\:(x1,\:x2,\:AND\:(x5,x6))\,\,\,\,\,\,(5)$$
due to (4).

I prefer to have a lot of small rules (by a lot I mean $10^3$ or $10^4$, which in CNF become $10^5-10^6$ of clauses).  The rules are not complicated - 10 ANDs and ORs and 20-30 inputs per rule at most, but they are usually much simpler.

Is there an efficient way to remove such redundancy from a formula? Is it possible with CNF formulation or I should use some other representation of the formula (BDD, for example)?  Any help and directions will be useful.


texts: In what sense do we mean 'distributed' when talking about a distributed representation of words?

texts:
In machine learning literature, when handling words or text inputs, the strings are often mapped onto a vector space using techniques such as word2vec.

The terminology in this is that the individual word vectors are 'embeddings' and the embeddings together are a distributed representation of the input words (see reference to this use in the original word2vec paper).

What does 'distributed' mean in this case? I have been assuming that the transformed words are distributed in the vector space of the codomain, is this correct?


texts: Color a graph using k colors, k>4, with the most equal distribution of colors

texts:
Given a planar graph G with $N$ nodes, 4 colors are enough to color each node, so that adjacent nodes have different colors.

Let $k > 4$. Is there an algorithm to color the nodes with $k$ colors, so that the colors are distributed the most equally possible?

In other words:

Let's call $c_1, ..., c_k$ the colors. We define
$\forall c_k\in[1,k], f(c_k)=\textrm{number of nodes of color}c_k$. Obviously, $\sum f(c_k) = N$. Find an algorithm to color the $N$ node with the $k$ colors to maximize the value $\min f$, with 2 adjacent nodes having different colors.


texts:
I've struggling with this problem for a while.

Given text $T=t_1t_2\ldots t_n$ and pattern $P=p_1p_2\ldots p_m$ over alphabet $\Sigma=\mathbb{N}$, we say there's a block matching of $P$ in index $i$ if there exist $m$ successive blocks $S_1,\ldots,S_m$ such that $$p_1=\sum_{s_1 \in S_1}s_1 \land p_2=\sum_{s_2 \in S_2}s_2 \land \cdots \land p_m=\sum_{s_m \in S_m}s_m. $$

For example:
$T=\text{1 2 3 5 1 2 3 2}$
$P=\text{6 5}$

Then we have block matching in index 1 because $1+2+3=6$ and $5=5$.
Schematically it looks like: $\text{|1 2 3||5| 1 2 3 2}$

We also have a block matching in index 4 because $5+1=6$ and $2+3=5$.
Schematically it looks like: $\text{ 1 2 3 |5 1||2 3| 2}$

The task is to find all indices where we have block matching.

I couldn't do better then a $\mathcal{O}(mn)$ but I believe there's a FFT application here.

Any hints?


texts: Finding maximal factorization of regular languages

texts:
Let language $\mathcal{L} \subseteq \Sigma^*$ be regular.

A factorization of $\mathcal{L}$ is a maximal pair $(X,Y)$ of sets of words with

$X \cdot Y \subseteq \mathcal{L}$
$X  \neq \emptyset \neq Y$,

where $X \cdot Y = \{xy$ | $x \in X, y \in Y\}$.

$(X,Y)$ is maximal if for each pair $(X',Y') \neq (X,Y)$ with $X'\cdot Y' \subseteq \mathcal{L} $ either $X \not \subseteq X'$ or $Y \not \subseteq Y'$.

Is there a simple procedure to find out which pairs are maximal?

Example:

Let $\mathcal{L} = \Sigma^∗ab \Sigma^∗$. The set $F = \{u, v, w\}$ is computed:

$u =(\Sigma^∗, \Sigma^∗ab\Sigma^∗)$
$v = (\Sigma^∗a\Sigma^∗, \Sigma^∗b\Sigma^∗)$
$w = (\Sigma^∗ab\Sigma^∗, \Sigma^∗) $

where $\Sigma = \{a,b\}$.

Another example:

$\Sigma = \{a, b\}$ and $\mathcal{L} = \Sigma^*a\Sigma$
Factorization set $F = \{q, r, s, t\}$ with

$q = (\Sigma^*, \mathcal{L})$
$r = (\Sigma^*a, \Sigma + \mathcal{L})$
$s = (\Sigma^*aa, \epsilon + \Sigma + \mathcal{L})$
$t = (\mathcal{L}, \epsilon + \mathcal{L}) $


texts:
I have this code:

if n is even
{
for i=1....n
   for j=1...i
      print j
return 8*foo(n/2)
}

Asking to calculate the running time $T (n)$. I thought at first that I can write the function like this:

$$T(n)= 8T(n / 2)+n^2$$
But according to the answers of the quiz, they are saying that the function looks like this:

$$T (n)= T(n / 2)+n^2$$
Why we can delete 8? Thank you very much!


texts: Interval schedule maximization when encountering intervals with equivalent end points

texts:
In interval scheduling, the greedy solution which maximizes the schedule that contains the largest number of "compliant intervals" involves initially sorting the list of intervals in ascending order by the end-times/point of each interval.

What confuses me, is if two or more intervals have the same ending time.

When performing the initial sort, should one base the sort of the sub-range of intervals on start time?

and if so should it be in ascending or descending order?


texts: How to prove equivalence relation in this case?

texts:
I am working on $\lambda$-terms and trying to prove the $=$ is an equivalence relation on $\lambda$-terms. My problem is proving reflexive relation.

$\frac{}{\theta \vdash x = x}$

$\frac{ \theta,x \# N, y \# M \vdash  M  = [y := x]N }
          { \theta \vdash  \texttt{$\lambda x.M$ $=$ $\lambda y.N$}   } $

$\frac{\theta \vdash  M_1 = M_2 \quad N_1 = N_2  }
          { \theta \vdash  \texttt{$M_1 \, N_1$ $=$ $M_2 \,N_2$} }$

I put two restrictions on such $\lambda$-terms.First, bound variables are distinct.
For example, there are no two terms such as $\lambda x.M$ and $\lambda x.N$.
Second, multiple bindings of a variable is not allowed.
For example, $\lambda x. \lambda x.M$ should be written as $\lambda y. \lambda x.M$.
To sum up, every bound variable should be distinct.
$[y := x]N$ means variable $x$ replaces variable $y$ in term $N$.
$x \# N$ means $x$ does not occur in $N$.
$\theta$ is a set of $\#$.
Also, $\alpha$-equivalence is assumed for the terms.
For example, $\lambda x.x = \lambda y.y$

I tried to prove that the $=$ shown in above rules is an equivalence relation on such terms.

For equivalence relation, I have to prove the following three relations.

reflexive: $\theta \vdash M=M$.

symmetric : $\theta \vdash M=N$ implies $\theta \vdash N=M$.

transitive: $\theta \vdash M=N$ and $\theta \vdash N=P$ implies $\theta \vdash M=P$.

The proof of reflexive relation is the following.

when $M$ is a variable such as $x$, then $x = x$.

when $M$ is an application such as $M_1 \,N_1$), then I have
$M_1 \,N_1$ = $M_1 \,N_1$, so it is true.

when $M$ is an abstraction such as $\lambda x.M$, from $\lambda x.M = \lambda x.M$, I have $ x \# M \vdash | M=[x:=x]M $, which is not true becuase $x \in M$.
Also, as I said, there are no two terms such as $\lambda x.M$ and $\lambda x.M$, so I cannot show $M=M$ for an abstraction.

Since $\alpha$-equivalence is assumed for terms. I assume that $M=\lambda x.M_1 =\lambda y.M_2$. Therefore, I will have $x \# M_2, y \# M_2 \vdash  M_1=[y:=x]M_2$? is this the right way to prove  reflexivity?

I would appreciate your kind help.


texts: Dove tailing questions about accepting language

texts:
$L = \{M | \text { M is a TM and there exist some string w that contains five 1's such that M halts}\}$

Where $\Sigma =\{0,1\}$

let $w_1, w_2, \cdots, \in \Sigma^*$ be an effective enumeration. We give a TM $R$ that recognizes $L$

R = "On input <M>
    for s = 1 to infinity:
        for i = 1 to s
            run M on input w_i for s steps
            if M halts on w_i within s steps then
                accept

Can I assume $M$ knows to halt only if there are five $1$'s? Or do I need another if statement such as in line 4

if M halts on w_i within s steps then
    if w_i.count("1") is 5 then
        accept


texts: Help with a dynamic programming solution to a pipe cutting problem

texts:
I'm trying to complete a problem where I have to design and implement a dynamic programming solution to the following problem

  You have to cut a metal pipe into several pieces. To do so, you bring it to a company that charges money according to the length of the pipe being cut. Their cutting method means that only one cut can be made at a time.

  Different ways in cutting the pipe can lead to different overall total prices. For example, suppose that a pipe of length 10 meters has to be cut at 2, 4, and 7 meters from one end. There are several ways to do this. One way is to first cut at 2, then 4, and then at 7. This gives a price of 10 + 8 + 6 = 24 because the first pipe was 10 meters in length, the second was 8 meters, and the third was 6 meters in length. Another way is to cut at 4, then at 2, then at 7. This would give a total price of 10 + 4 + 6 = 20, which is a cheaper price.

  Figure out (a method to determine) what is the cheapest price that is possible (to make sure that the company isn't cheating you). The procedure that you write (in Java) should return a single integer, which will be the cheapest possible total cost for performing all of the cuts. Only one cut can be performed at a time, and the cost of making a cut is equal to the length of the pipe being cut (before the cut is performed).

But I'm having trouble knowing where I even need to start. If anyone could point me in the direction of where I can research similar problems or give me an idea of what I should be thinking about with this problem it would be great.


texts: Find position in array where element-wise multiplication with string of 1 and 0s results in max value

texts:
I have a sequence of 1s and 0s. For example: $bits = [1, 0, 1, 1, 1, 0]$. I also have an array of positive integers. For example $arr = [12, 23, 4, 6, 8, 0, 24, 72]$. I need to find the index, $i$, in $arr$ of the leftmost element of $bits$ such that
$$\sum_{j = i}^{i + \textrm{length of bits}}{bits[j - i] * arr[j]}$$
is a maximum. Essentially I am maximizing the element-wise multiplication between the two sequences starting at index $i$.
I need to solve it in $O(n\log n)$ or better, but I can only think of a way to do it in $O(n^2)$. I have a feeling prefix sums could be used but am not sure how.


texts: If $W$ is a Godel universal set there exists a number $x$ s.t. $Wx=x$

texts:
Let $W$ be a subset of $\mathbb{N} \times \mathbb{N}$. Suppose $W$ is the Godel universal enumerable set (for the class of all enumerable subsets of $\mathbb{N}$, i.e. for any enumerable set $V$ subset of $\mathbb{N} \times \mathbb{N}$ there exists a total computable function $s:\mathbb{N} \rightarrow \mathbb{N}$ s.t. $\langle  n,x \rangle \in V \iff \langle  s(n),x \rangle \in W$.

Prove that there exists a number $x \in \mathbb{N}$ in s.t. $W_x=\{x\}$.
Prove that for $y$ not equal to $x$ s.t. $W_x=\{y\}$ and $W_y=\{x\}$.

My argument for the first is that since $W$ is a Godel universal set, there must be some natural number $x$ s.t. $W_x=\{x\}$, using the fact that there exist a total computable function, and any total computable function have a total computable extension s.t. $a=b$ iff $W_a=W_b$.

Do you think this is correct?

How can I use this argument for the second part?


texts: Generating values from a probability density function

texts:
If I have a probability density function, some f(x) which is >= 0 everywhere and integrates to 1, is there a method to generate random numbers using that PDF?

I know there is the box-muller transform to convert uniform random numbers to gaussian, but is there anything for the general case, or at least a more general case of PDFs?


texts: Probabilistic poly-time machine always halts on all inputs?

texts:
In the usual definition of probabilistic poly-time machine it is said that the machine halts in polynomial time for all inputs.

Is the intention really to say that the machine halts for all inputs, or that if it halts it must be in polynomial time?


texts: Lower bound of complexity of simple problem

texts:
Consider the simple problem:

Given a list of objects L of length n, and an object O, determine if O is in L.

It is intuitive that there cannot exist an algorithm a with worst-case time complexity less than O(n) to correctly solve this problem.  But without considering individual algorithms, how can one mathematically prove that no faster algorithm exists?


texts: Looking for fast LP solver algorithm for my Special case

texts:
I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly appreciated and I would appreciate you providing me with relevant papers as well.

Context: I am trying to give an algorithm related to graph theory. Unfortunately, my knowledge of LP is very limited that is why I need your guidance. In the following algorithm $2k$ is the degree of the investigated vertex. Ideally, I am looking for $O(k)$ or $O(k \log k)$ solution, or in total $O(n)/O(n\log n)$ when this applies to all the vertices. Note that $|E|= O(n)$. However, any fast algorithm would be appreciated.

Modification and Clarifications (Edit):
There was a mistake as pointed out by @D.W. I changed the program. Beside $t_i$'s which I need to be distinct positive integers between $1$ to $2k$, there are variables $x_i$'s and $T$. Originally, I want $T$ to be an integer and $x_i$ to be $0$ or $1$; however, it is not important. If we find an optimal solution in which $T$ and $x_i$'s are real values I have a $O(k)$ mechanism to find the solution I want based on it. Do we have a polynomial solution to this program? (based on $n$, number of vertices.) (Any other LP comes to mind such that it forces $t_i$ condition but does not make it Integer Program?)

Minimize: $T$
Subject to:
$\forall i \in [2k] \qquad t_i \in \mathbb{N},\ \ 1 \le t_i \le 2k$
$\forall i, j \in [2k], i \neq j \qquad t_i \neq t_j$

$\forall i \in [2k],\ i \text{ is an odd number} \qquad t_i \le t_{i+1}$

$\forall i \in [k] \qquad 0 \le x_i \le 1$
$\forall i \in [k] \qquad \text{A linear constraint}\ F(x_i,\ t_{2i},\ t_{2i-1},\ T)$
Comment: If it helps, $F(x_i,\ t_{2i},\ t_{2i-1},\ T)$ is $(1-x_i)(T-t_{2i-1}+1\ +\ T-t_{2i}+1)\ +\ (x_i)(T-t_{2i-1}+1) \ge |C_i| - 1$, Where $|C_i|$ is a constant I know.


texts:
I was reviewing for my CS class and came across this question and answer combo that didn't have any explanation why it was correct. I'm confused on how they got the answer:

We have a system to which we can instantaneously add and remove cores
-- adding more cores never leads to slowdown from things like false sharing, thread overhead, context switching, etc
When the program foo() is executed to completion with a single core in
the system, it completes in 20 minutes. When foo() is run with a total
of three cores in the system, it completes in 10 minutes.
If 100% of foo() is parallelizable, with 3 cores it would take
20/3=6.66 minutes. Since it instead takes 10 minutes, what fraction of
foo() is parallelizable?

ANSWER GIVEN: 0.75

How many minutes would it take to execute foo on this magical system
as the number of cores approaches infinity?

ANSWER GIVEN: 5
Could someone explain how the staff got these answers?


texts: Join of recursively enumerable set and its complement

texts:
The union of a recursively enumerable set and its complement is $\Sigma^*$, which is definitely recursively enumerable. What if instead we consider the following operation, on an RE set $S$?
$$
\{ \# w : w \in S \} \cup \{ \\\$ w : w \in \overline{S} \}
$$
Is the result recursively enumerable?


texts: Maximization problem on finite collection of finite sets

texts:
Problem
I am considering the following maximization problem:

Input is a finite collection of finite sets $\mathcal{F} = \{ X_1, X_2, \ldots, X_n \}$.
Goal is to find a subset $G \subseteq \mathcal{F}$ that maximizes $|G| \times |\bigcap G|$ where

$|G|$ is the cardinality of the set $G$, and
$\bigcap G = \bigcap \{X_{i_1}, X_{i_2}, \ldots, X_{i_m} \} = X_{i_1} \cap X_{i_2} \cap \cdots \cap X_{i_m}$.

As an example, for the collection
$$
\mathcal{F} = \{ \{a, b, c\}, \{a, b, c, x\}, \{b, c, y\}, \{a, b, c, z\} \},
$$
the maximizing subset is $G = \{ \{a, b, c\}, \{a, b, c, x\}, \{a, b, c, z\} \}$
and the score is $3 \times |\{a, b, c\}| = 9$.
Note: the score of $\mathcal{F}$ itself is $4 \times |\{b, c\}| = 8$.
Question
I am planning to use a procedure of this problem for compressing data (represented by finite collections of finite sets).
However, I don't have any good idea to solve this problem efficiently.
As yow know, we can solve this by enumerating all the collections of $\mathcal{F}$; but, it's too slow for practical use.
Is there a polynomial-time or some kind of efficient algorithm for this problem?
Or, does this problem belong to the complexity class that cannot be solved in polynomial time?


texts:
I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at this scale.

These are the clustering algorithms I've been looking into:

Affinity propagation:: seems like a good solution, but the memory usage seems way too high, since the data is dense.
DBSCAN: could also be an option, but I want all nodes/strings to belong to a cluster and not be considered "noise.
K-medoids: seems like a good option in terms of memory usage, but the computation time seems worrying. It would also be highly preferred if the number of clusters was not determined before running the algorithm as in affinity propagation.

Do you have any ideas on how this problem can be solved? The computation time is not extremely important, as long as the result is satisfiable and it can be done within a couple of days.

Thank you in advance!


texts:
Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$.

I read the proof that $L$ is closed under logspace reductions in Arora-Barak's textbook. The idea of the proof is, if I'm not getting wrong, to simulate the Turing Machine $M_B$ that computes the solution to $B$, carefully recomputing the $i$-th output bit of $f$ whenever we need it (so to save space).

My (probably naive) question is: since we are only interested in remaining within $L$, why can't we just compute the output of $f$ and store it entirely on the work tape of $M_B$ (this should require only logarithmic space), maybe separating it from the rest of the work tape with a special symbol, and use it as input to $M_B$? Since $B \in L$ this should require just an additional logarithmic amount of space, so there shouldn't be any risk to exit from $L$…where am I getting wrong?


texts: Distributed Serializable Snapshot Isolation

texts: I was wondering if there is any research on distributed transaction algorithms for Serializable Snapshot Isolation. I found Binnig, C. et al.: Distributed snapshot isolation: global transactions pay globally, local transactions pay locally, VLDB J.'14 on Distributed Snapshot Isolation, but I couldn't find anything similar about Serializable Snapshot Isolation...


texts: Why are floats converted from different integers sometimes equal?

texts:
I'm trying to understand the following algorithm:

int ubnd = Integer.MAX_VALUE
int lbnd = ubnd
while (fload)lbnd == (float)ubnd {
    lbnd = lbnd - 1
}
lbnd = lbnd + 1
print "$lbnd..$ubnd"

I don't see why for 63 iterations of the loop, we have (float)lbnd == (float)ubnd. It has something to do with the conversion of integers to floats, but I don't know what. I know that integers and floats both have 32 bits, but there must be a different way of storing them. Could someone help me out?


texts: How to build a TM state diagram for a given language

texts:
I came across following TM state diagram accepting language $\{a^nb^nc^n | n\geq 0\}$

After trying out some valid and invalid strings of various lengths, I was surprised how it is designed to accept language exactly as specified.

Now I have started wondering how I can come up with such TM design given any language specification. When I learned FAs and NFAs, I came across some minimal regexes ($\epsilon$, a, a+b, a*, ab) whose FAs are well known. Then we can combine these FAs to come up with more FAs/NFAs for more complex regexes / languages. Is there any such standard way / approach to come up with TM design for given language? Or is it pure creativity/intuition to design approach.


texts: Rabin Karp algorithm that uses bitwise AND

texts:
I'm reading the source code of JPlag and came across their rabin-karp algorithm implemented found here.

Here's the gist of it:

// modulo = 63

            for (i=0; i<loops; i++) {
                hash -= factor * (s.tokens[i].type & modulo);
                hash = (2*hash) + (s.tokens[i+hashLength].type & modulo);
            }

What makes this a "good" hash function (or is it a terrible one)?

Couple of things I don't understand:

there isn't a modulus applied to the hash at each iteration of the loop unlike the traditional rabin karp algorithm, so is there a "table size" this adheres to, and why?
(2*hash) - what is the significance of choosing 2 as the base? In the regular rabin-karp, the base is recommended to be larger than the character set size. 2 certainly isn't.
(s.tokens[i+hashLength].type & modulo) - What is the bitwise AND doing here?


texts: Why/how are the banking systems that robust?

texts:
I'm a developer, so I understand (a bit) how computers work, and how softwares work and fail.

In all softwares I've dealt with (as a developer or as a user), I've always seen small or huge bugs:

Even in systems well designed/implemented you encounter design/implementation bugs.
Even sites/softwares exceptionally well developed (high-skilled engineers and/or high-budget projects) are subject to problems (StackOverflow is down from time to time, a big Web company database may fail with a few seconds/minutes data loss despite a good mirroring technology, a virus may corrupt files at an e-commerce or social site, etc.).
Even in the medical industry, we see from time to time bugs or other important problems leading to a serious outage.
Even embedded systems in space rockets may have bugs leading to the destruction of the rocket.

However, with banking systems, this seems to never occur:

I've never heard about data loss with credit card transactions.
I've never heard about an ATM failing to provide a customer with cash because the back-end is down (the ATM may be broken, but it's always because of a fault on the ATM side).
I've never heard about an online bank account failing to report the exact list of operations (the Web site may be down, but the data is always accurate at the end).
I've never heard about a virus corrupting banking information resulting in an actual data loss.
And even when I think about the old days, when my parents used to receive paper versions of their bank reports, in the 80s (and I assume the same was true in the 70s), there was no error at all.

How could the banking system be the only one perfectly error-proof, since the early ages of computer science, while all other systems fail from time to time?
This is even more surprising when you consider the amount of interoperability you need accros all banks and countries! And this works fine since 10s years.


texts:
We know that for 3 variables (A=0,B=1,C=1), f$_1$ = (A XNOR B XNOR C) = 1, since the input has even number of 1's.

But if we were to do this step by step, f$_2$ = (A XNOR (B XNOR C)) = (A XNOR (1 XNOR 1))

Now, 1 XNOR 1 = 1. So, f$_2$ = (A XNOR 1) = 0 XNOR 1 = 0.

Why is f$_1 \neq$ f$_2$ ?

Also, which is true : "XNOR operation gives a value of 1 for " : Even number of 1's in the input OR Even number of 0's in the input. (Sorry, but a certain professor implied the later, so have to confirm).


texts: Recursive and recursively enumerable language definition for a layman

texts:
I've come across many definitions of recursive and recursively enumerable languages. But I couldn't quite understand what they are .

Can some one please tell me what they are in simple words?


texts:
Let $\Sigma = \{ \sigma_1 , ..., \sigma_t \}$ and let $S$ be a string from $\Sigma^*$. Denote: $n=|S|$, that is $S$ has $n$ letters. I'd like to find the shortest prefix $T$ of $S$ such that $S$ is a prefix of $T^n$ ($T^n= T \cdot .... \cdot T$, $n$ times).

I tried to build the suffix tree for $S$, and then checking each node, by their levels - from lowest level to top level, because then the corresponding prefix will be shortest at the lowest level of the suffix tree and will get longer - and then for each node checking if this property applies for the prefix of the current suffix node I'm looking at, but that would not necessarily give me the shortest prefix, because the suffix tree may have on the same level different lengths suffices.

I'm not sure as to how I'll be able to find the shortest prefix $T$? Perhaps there is a different way of using a suffix tree?

Or maybe there is a way to solve this efficiently without using suffix trees at all?


texts: Restriction for greater than constraint in linear programming

texts:
I have a model that considers real values and that uses a binary variable $x$. In this model, the following conditions should apply:

\begin{equation}
    x=
    \begin{cases}
      0, & \text{if}\ y > s \\
      1, & \text{otherwise}~(y \le s)
    \end{cases}
  \end{equation}

with $y \ge 0$ and $s \ge 0$.

First I tried these two restrictions:

$$
(s - y) - M x \le 0\\
(y - s) - M  (1-x) \le 0
$$

where $M$ is a very large constant.

Unfortunately, if $y = s$ the binary variable can be either $1$ or $0$. It is also not possible to enforce one value by the objective function. To fix this problem, I added an very small value $\epsilon$ to the first restriction:

$(s - y) + \epsilon - M x \le 0$

This solution works, but is there a way I can model that without the $\epsilon$ value?


texts: What is an example of Licklider’s idea of man-machine symbiosis in constructing information systems?

texts:
I am trying to understand Licklider’s idea of man-machine symbiosis in the real world, does anyone know of any real world examples of the use of a man-machine symbiosis?

Would it be correct to say that safety critical systems such as an aircraft flight control system is an example of this, due to it fitting into the following criteria in Licklider's ideas:

  The main aims are 1) to let computers facilitate formulative thinking
  as they now facilitate the solution of formulated problems, and 2) to
  enable men and computers to cooperate in making decisions and
  controlling complex situations without inflexible dependence on
  predetermined programs.


texts: How to modify Bellman-Ford algorithm for this specific Minimum Cost Flow problem?

texts:
I'm trying to design an algorithm for the following optimization problem. Suppose that $G=(V, E)$ is a digraph where $V$ and $E$ are sets of vertices and edges of $G$, respectively. $|V| = n$ and $|E| = m$. $c$ is the cost vector; $c_{ij}$ is the cost of edge $(i,j)$. Costs can be negative and $G$ may have cycles (negative or positive). The target is a minimum cost flow from source vertex $1$ to sink vertex $n$ which must satisfy some constraints. So let $x$ be the solution vector; if $x_{ij}=1$ then the edge $(i,j)$ is a part of minimum cost flow. Here is my optimization problem:

$$min \sum_{(i,j)\in E}c_{ij}x_{ij}$$

Subject to these constraints:

$$\begin{array}{ll}
\sum_{i\in V}x_{ij}&=&\sum_{i\in V}x_{ji}~~~~~~\forall j\in V (j\neq1,n)\\
\sum_{j\in V}x_{1j}&=&1\\
\sum_{i\in V}x_{in}&=&1\\
x_{ij}&\in&\{0,1\}~~~~~~\forall i,j\in V\end{array}$$

First constraint makes us sure that in the final solution vector, total number of edges outgoing from vertex $i$ and total number of edges incoming to that vertex are equal.

Only one edge can go out from vertex $1$, based on second constraint and only one edge can come to vertex $n$, based on third constraint.

Finally, last constraint tells us that the maximum flow allowed for each edge is $1$.

This is the problem of sending a flow of value one from vertex $1$ to vertex $n$  subject to the constraints with a capacity limit of $1$ on each edge and the vector $b$ set to $0$.

I asked this question because I think a flow in this case can be viewed as a path, in which we can goes around it's cycles (if any cycle exists on the path) only once and it can't meet vertices $1$ and $n$ more than once. So, can we solve this problem using a modified version of Bellman-Ford or any other dynamic programming algorithm? Time order isn't the matter to me. I just don't want to use algorithms designed for the general form of minimum cost flow problem.


texts: What is the relation between countability and recursive enumeration?

texts:
Does recursive enumeration implies countability?
Does countability implies recursive enumeration?

I believe the first implication holds but not sure about the second. A good  example would suffice.


texts: Intuition for the convergence of the distance vector routing protocols

texts:
What is an intuitive way to think about the convergence of the distance vector routing algorithm?

According to Wikipedia:

  Distance-vector routing protocols use the Bellman–Ford algorithm and Ford–Fulkerson algorithm to calculate the best route.

I am aware of the Bellman-Ford and Ford-Fulkerson algorithms and have some intuition for how and why they work. Unfortunately, I fail to see how they relate to the asynchronous distributed distance vector algorithm and so I lack intuition about why it converges.


texts: Relational algebra statement for a query

texts:
For the following schema

Country ("countryID", cName)
CoffeeShop ("shopID", sName, countryID, city)
Product ("productID", size)
Serves ("shopID", "productID")
ProductNames ("productID", "countryID", pName)

where attributes in quotation marks are primary keys, I must write a relational algebra statement for the following query:

List names of products that have same names in all countries they are served.

The thing that made me stuck on this problem is the fact that the product must not necessarily be served in all countries, but rather have the same name in all countries it is served. Without comparing for an initial value, I couldn't get a solution that makes more sense and that is possible to be written as a relational algebra statement.


texts: Algorithms for 2-colouring a 2 x N matrix

texts:
Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions.

An example of all possible solutions for $N = 2$ is as follows:

(R)---(R)   (B)---(R)   (R)---(B)   (B)---(R)   (R)---(B)   (R)---(R)  (R)---(R)
 |     |     |     |     |     |     |     |     |     |     |     |    |     |
 |     |     |     |     |     |     |     |     |     |     |     |    |     |
(R)---(R)   (R)---(B)   (B)---(R)   (R)---(R)   (R)---(R)   (B)---(R)  (R)---(B)

I don't need to list all solutions, but what's a good algorithm for counting all solutions? For example, can we do it in $O(n)$ time or better?


texts:
I'd like to know if I have the right intuition and my answer is headed the correct way.

I am given a function
$ f = \{0, 1\}^* \rightarrow  \{0, 1\}^* $ that is computable in space $O(\log n)$ assume that for every $x \in \{0, 1\}^*$, $f$ is length preserving, $|f(x)| = |x|$.

Define
$$L = \left\{ x\#y \mid \ x, y \in \{0, 1\}^*, |x| = |y|, \ \text{and} \ f(x) = f(y)\right\}$$

I am suppose to prove that $ L \in  {\sf DSPACE}(\log n) $.

Please correct me if my intuition is incorrect.

My solution would be to build a decider $M$ which is a Turing machine.

$M$ takes inputs $x$ and $y$, run the function $f$ on input $x$ and $y$ and if the lengths of the two strings are equal then accept, otherwise reject.

Now the Turing machine runs in $ O(\log n) $ because the function $f$ is computable in $ O(\log n)  + O(\log n) = O(\log n) $ and comparing the length returned by the function is $ O(1) $
Thus the language is decidable by a Turing machine that is run in $ O(\log n) $ and only takes Space $ O(\log n) $.


texts:
If we have a langage $L$ over an alphabet $\Sigma$, then we can defined the density function of $L$ as :

  $$ p_L(n) = | L \cap \Sigma^n | $$

I am wondering why it’s useful to study this function and what informations it gives on $L$.

Moreover, we can then defined the entropy of $L$ as :

$$E_L(n) = \frac{1}{n} \log p_L(n) $$

Once again I am wondering what information does this function reveal about $L$. Moreover, is there any way to think intuitively what the entropy of a language really represents?

Thanks you !


texts:
The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.

P1() {

    C = B - 1;
    B = 2 * C;
}

P2(){

    D = 2 * B;
    B = D - 1;
}

The set of distinct values that B can possibly take is ?
My understanding: Say P1 executes first , then B=2, after that P2 executes next  then value of B=3.  Again P1 executes and we get B value as 4, yet again B executes and we get B value as 7 etc. So does this mean B will take up infinitely many values?  The order of my execution is P1-P2-P1-P2-P1.... Is this correct?


texts:
I've just began studying Artificial Intelligence and am wondering why the reachable state space of an 8-puzzle is $9!/2$. I see that the number of permutations of the tiles is $9!$ but it is not immediately obvious why half the possible states of the puzzle are unreachable at any given state. Can anyone elaborate?

An image of an 8-puzzle for reference with a random configuration on the left and the goal state on the right:


texts: When a problem can be speeded-up using Blum's speed-up theorem?

texts:
Here is the definition of Blum's Speed-Up theorem.

Blum's Speed-Up Theorem. There is a decidable language A such that for every TM $M$ that decides A with running time $u(n)$, there is another TM $M'$ that decides A much faster with running time satisfies $r(u(n))$ such that $r(u(n)) \leq u(n)$ for any computable function r and for all but finitely many n.

Now, this theorem gives us a hint that we cannot reach to optimal algorithm for some problems.
Question: How do we know that if a problem can be speeded-up or not? For example sorting problem has a lower bound and upper bound that match, i.e. $\Theta(n \log n)$. Now, how do we know that Blum's speed up theorem cannot applied here and it might gives us a better running time than $n \log n$? I knew that the theorem says for some problems. So how do classify these computable problem or how do we know them?
Thanks


texts: Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation?

texts: Do the hyper computing machines/models that are supposed to be more powerful than Turing machines, capable of recognizing and deciding the languages that are not recognizable/decidable by Turing machines?


texts:
I am quoting a paragraph from the book "Operating System Principles" by Galvin.

  Usually, each page-table entry is 4 bytes long, but that size can vary as well. A 32-bit entry can point to one of $2^{32}$ physical page frames. If frame size is 4 kB, then a system with 4-byte entries can address $2^{44}$ bytes (or 16 TB) of physical memory.

Now, I know we have $2^{44}$ bytes of memory because we have $2^{32}$ page frames and each frame size is 4 kB, i.e. $2^{12}$ bytes of memory, so physical memory is $2^{32}\cdot2^{12} = 2^{44}$.

Please help me to understand the following:

How did we get the number of frames as $2^{32}$?
If the logical memory space is $2^{32}$ then what should the physical memory space be (considering both the fully used and partially used logical address space concept)?


texts: Convert source code from one language to an other?

texts:
Say I have a full application written in Python. Is it feasible to convert the source code into C? If such a tool doesn't exist, why doesn't it? What are the constraints?

I ask this since I have been wondering why people use C for microcontrollers when they could write their code uber-fast in Python when prototyping and then convert the source.


texts: If $L_1$ is regular and $L_1 \cap L_2$ context-free, is $L_2$ always context-free?

texts:
If $L_1$ is a regular language and $L_1 \cap L_2$ is a context-free language, does it mean that $L_2$ is a context-free language too?

I attempted to prove that $L_2$ was not required to be context-free by the following: If $L_1 = \{ a^n \}$ and $L_2 = \{ a^nb^nc^n \} $ then $L_1 \cap L_2 = \{ a^n \}$ which is context-free.

Is this a counterexample to show that $L_2$ is not required to be context-free? If not, then do you have any suggestions?


texts: DPDA for $L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$ according to empty stack criterion

texts:
I'm having some trouble with the following language:

$L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$

with alphabet $A=\{0,1,2,3\}$

I'd like to find a deterministic pushdown automata to recognise it according to the empty stack criterion.

I built the deterministic pushdown automata according to the final states criterion and as the language has the prefix property there should be an automata according to the empty stack criterion.

Is there an algorithm to do this? The one I use to translate from one criterion to the other doesn't not seem to work for deterministic automata.


texts: Extrema and saddle point of 3D field at different scales

texts:
I have a scalar 3D field $f(x, y, z)$ with $x,y,z$ on a regular grid. I would like to know the location of the maxima, minima, saddle points and their relation as a function of a smoothing scale.

For that, I'm convolving my field $f$ with a filtering function that is a Gaussian with a variance $\sigma$. I vary $\sigma$ from 0 to the size of my grid. I want to be able to:

track the location of extrema and saddle point as a function of $\sigma$
locate the merging events between two saddle points / a saddle point and an extremum
be able to tell which saddle point / extremum merged into which

An extremum / saddle point is defined as

$$ \nabla f = 0 $$

Extrema are distinguished using the Hessian:

$$ H_{i,j} = \nabla_i\nabla_jf = \mathrm{diag}(e_1, e_2, e_3)$$

where $e_1, e_2, e_3$ are the eigenvalues of the Hessian. If all of them are negative (resp. positive), the point is a maximum (resp. minimum). If one and only one is positive (resp. negative), the point is a saddle point which is a maximum (resp. minimum) in 2 dimensions.

Ridges are defined as curves on which

$$ \nabla f = \mathrm{diag}(0,e_1,e_2)$$ where $e_1, e_2 \neq 0$.

For now, I am finding the location of the extrema and saddle point by doing a quadratic interpolation $P(x,y,z)$ on each point of my grid and by computing its first and second derivatives. However I have two issues:

each time I smooth at a different scale, I don't use the information about the location of the extrema and saddle point at the previous scale
I don't know how to robustly find which extrema is linked to which saddle point, and hence, I can't tell robustly which point is merging into which.

Do you have any advice about this problem?

NB: it has to be fast enough to be able to run in less than a month on a 100x100x100 grid, at ~100 smoothing scale for 100,000 grids.


texts: Given directed connected weighted graph, check if d(v) = delta(s,v)

texts:
I'm having some hard time with this problem.
Can someone give me some clue/guidance?

This is an homework question, so please don't just solve it.

  Given a weighted directed connected graph $G = (V,E)$  and given another
  function $d: V \to \mathbb{R}^+$ (including zero), find a linear time algorithm that checks if $d(v)=\text{delta}(s,v)$ for each $v$, for some fixed vertex $s$.

  $\text{delta}(s,v)$ is like in Dijkstra algorithm, meaning shortest path from $s$
  to $v$.

My thought is to make use of BST to check if these functions are equal, but I can't avoid running Dijkstra for it.


texts: How to use DFA/NFA to prove the language {$0^n 1^$ | x ∈ Σ*, n ≥ 1} is regular?

texts:
I'm trying to prove the language L = {$0^n 1^$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA.
I'm thinking to have n+1 states in a NFA, with the start state as the accepting state. The NFA reada $0$s to go from q$0$ to q$n+1$, then reading $1$s or $0$s to stay in the q$n+1$, then reading the same number of $1$s to go back to the q$0$. Is this a valid way to prove L is regular?


texts:
I am actually little bit confused when I am reading through the text - Database system concepts by Henry F. Korth and others

I won't be able to understand one thing, which one of the following models I have to use when I have to design the ER diagram.

As the textbook says:

  We are going to treat the telephone as an entity when one may want to keep extra information about a telephone such as its location, or its type (like mobile, video phone or a plain telephone etc) or all who share the telephone. Thus, treating telephone as an entity is more general than treating it as an attribute

What I want to clarify is: If I draw the ER diagram by choosing telephone as a composite attribute having component attributes: telephone_number and location. Then I can also define the same way as an entity can do. Is it not correct to do it like this way?

If it is correct then what to use and when? If it is incorrect then why is it so.

one reason may be one person cannot have multiple phone numbers but we can design the same by making telephone as multi-valued attribute. So where I am going wrong?


texts: Trying to understand a way to split an AVL tree in O(log n)

texts:
I'm trying to understand a presentation about AVL trees.
It says that the way to split AVL trees in node x is as follows:
You search for the node x and mark every left son of every node when you turn right.
Later, you merge all the marked subtrees.

Now, i've drawn a complete BST with 15 nodes and tried the algorithm by splitting node 7:

Now, I mark nodes 2 and 5, try to merge them, and the left tree does not have node 6 in it. The description about how to split trees is not complete and I don't know what i'm supposed to do with it.


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

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

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

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

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


texts: What is the difference between derivative free optimization and derivative optimization in terms of advantages/disadvantages?

texts:
I understand the basic operation of the algorithms however i'm unclear as to when to use one over the other and what advantages/disadvantages they offer over each other.

Also as an aside, if anyone knows any good resources that go over the topic of optimization in detail (especially gradient free optimization) that I could read or watch, i'd really appreciate it if you could point me in the right direction.

Thanks in advance guys and apologies if its a basic question, I'm quite new to the topic.


texts: Normalization-by-evaluation for untyped lambda calculus which results in -normal form

texts:
Usual NbE algorithms for untyped lambda calculus, which use (P)HOAS to embed terms to a host language constructs, results in a beta-normal form of a terms.
Is there algorithms to (efficiently) exploit host language constructs to normalize untyped terms to beta-eta normal form?


texts: What should be the minimum value when the two threads are executed concurrently

texts:
int count=0;
void *thfunc()
{
    int ctr=0;
    for(ctr=0;ctr<100;ctr++)
    count++;
}

If *thfunc() is executed by two threads concurrently in a uniprocessor system, what will be the minimum value of count when both threads complete their execution? Assume that count++ is performed by using three instructions:(1) Read value of count from memory to a CPU register R,(2) Increment R,(3) Store the value in memory.

(a) 200

(b) 2

(c) 100

(d) None of the above

According to me, the answer should be 100. I cant find any execution sequence in which the count value can go down below 100. But my manual says that the answer is 2.

Can anyone please tell me what I am doing wrong? Also, please explain how the answer 2 is obtained?

Thanks in advance!


texts: Are those temporal logic formulas equivalent?

texts:
I am wondering whether those two formulas are equivalent:
This LTL formula:
$AG[p\rightarrow Gq]$
And this CTL formula:
$AG[p\rightarrow AGq]$
I thought that they are equivalent, however points were deducted when I wrote that they are (This was a yes/no question, so no explanation was needed).
What am I missing? Why are they not equivalent?


texts: Cycles in hardness of ST-CON for the class NL

texts:
It seems to me that the problem of $s$, $t$ connectivity in a DAG should still be NL-Complete.

I am aware that ST-CON without the DAG restriction is complete for NL, so obviously the DAG restriction is still in NL, but I believe hardness follows as well:

For a turing machine that runs in space $s(n)$, its configuration graph is of size $2^{O(s(n))}$. Furthermore, this implies the time for an NL machine to solve any problem, if it halts at all, is also $2^{O(s(n))}$. Then you can blow up the configuration graph by including a counter for any possible time step a configuration is reached, resulting in a graph of size $2^{O(s(n))} \cdot 2^{O(s(n))} = 2^{O(s(n))}$. At this point the typical reduction to ST-CON can be used since the graph is the same size.

If this is true, then I do not understand why the result SL = L did not follow trivially from the formulation of SL. Namely, an undirected acyclic graph is a tree, and a simple maze algorithm can determine $s$, $t$ connectivity in log-space (and linear time!).

Another strange implication would be that the cyclic or non-cyclic versions of $s$, $t$ connectivity on directed or undirected graphs are equivalent for log-space computation. This implies a simple algorithm like the tree-based one for $s$, $t$ connectivity on a generic undirected graph.


texts: Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word

texts:
I have talked to my friend and he said this is the only place somebody could know how to solve it. It is the only exercise(from around 80) from exam revise I just do not know how to do at all.

Create pushdown automation for
{w: #a(w) >= 2#b(w)}; and simulate it for the word ababaaa

# means number

Does any one of you is fluent enought in automation to solve it?


texts: Why is it that a lambda function requiring multiple input also requires multiple functions?

texts:
So I recently discovered lambda calculus and for the most part I understand it. However, one specific part of it that I cannot understand is this:

Let's say we define a very simple function

$$ I := \lambda a.a$$

This is simple to understand, nothing confusing. However, if you add another input I will scratch my head furiously:

$$A := \lambda a.\lambda b.a+b$$

This is confusing to me for at least 2 reasons:

Why is it that I cannot define a function with multiple parameters like so:

$$A := \lambda a,b. a+b$$
How does the second function returned have access to the first parameter if they can only hold one parameter? Is there a prospective for scope? If so, how does it work?


texts: Irregularity of language of prefixes of decimal expansion of pi

texts:
Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$:
$$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$
Prove that Lπ is not DFA-recognizable. You may use the fact that $\pi$ cannot be written as a repeating decimal, that is, there are no sequences of digits $d_1, d_2, \ldots,d_m$ and $e_1, e_2, \ldots,e_n$ such that

$$\pi =  d_1.d_2\cdots d_ne_1e_2\cdots e_n=d_1.d_2 \cdots d_m(e_1\cdots e_n)(e_1\cdots e_n)(e_1\cdots e_n)\cdots.$$

This is how I started my proof:

Proof: by contradiction.

Assume $L_\pi = L(M)$ for some DFA $M$. We'll construct a diabolical string $x$ such that $x\notin L_\pi$, but $M$ accepts $x$.

Let $x = d_1.d_2\cdots d_ne_1e_2\cdots e_n=d_1.d_2 \cdots d_m(e_1\cdots e_n)(e_1\cdots e_n)(e_1\cdots e_n)\cdots$; clearly $x\in L$.

Go through $n + 1$ states, only $n$ states in $M_1$ so $q_i = q_j$ for some $i, j$.

I based my proof off of this: https://courses.cs.cornell.edu/cs2800/wiki/images/2/29/Sp19-lec24-pumping-board.pdf

I'm stuck at the part where I'm trying to make a contradiction.


texts: Fractional cascading allows me to search in k ordered lists. It requires every list to have same ordering (how would I otherwise insert elements from the cascade below, preserving order?). But why is this better than merging those k lists and doing binary search on it?


texts: 'Half-Close' figure of Data Communications and Networking, 5/e

texts: In the Figure 24.13 of Data Communications and Networking, 5/e the first ACK message from the server holds y-1 in it's Sequence no. field. Note that the first FIN message from the client message had y in it's Acknowledgement no. field. So shouldn't the first ACK message from the server be holding y in it's Sequence no. field instead of holding y-1? Is the diagram faulty or is there a reason behind it?


texts:
Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem?

Definitions: Uniform-cost search is also known as lowest cost first. Initial search problem can be any graph with a start and a goal state. You just apply the uniform cost search algorithm on the graph.


texts: Time complexity of a recursive algorithm with two lists as parameters

texts: The goal is to find the function T which describes the time complexity of an algorithm who merges two lists (but the lists are given inversely sorted). The problem is that recursive calls depend on an external factor other than the input size, so , how may one construct a piecewise recursive function T on such an algorithm? How can a piecewise function T(n1,n2) (n1,n2 are the lengths of the lists) be defined when recursive calls do not depend on n1 or n2?


texts: I want know if compiler interacts with operating system during compilation process.And if yes then which part of compiler interacts with which part of operating system


texts: data structure for string queries algorithm

texts:
We have a finite set of words $D$, and denote $Pref(D)$ to be the set of all prefixes from words in $D$ and $l(D)=max_{w\in{}D}|w|$ is the length of the longest word from $D$.
Problem statement:
Given: $D$ subset $\{0,1,...,\sigma\}*$ $\;\;\leftarrow$ finite set of words $a-z$. We will have queries of the following type:
Input: $u,v \in Pref(D)$
Output: $min\big\{|\gamma| \big| u\gamma \in D \Leftrightarrow v\gamma \notin D\big\}$, where $\gamma\in\Sigma*$ is a word from the alphabet $a-z$.
How can we $describe$ algorithm such that solves the problem and has the following:
Time for creating index (data structure) $O(l(D)|Pref(D)|)$
Memory $O(|Pref(D)|)$
Time for answering a query $O(1)$


texts: How to formally prove that if triangle inequality is satisfied in a bunch of edges, then each edge has a positive value?

texts:
The exact questions states the following:

  Suppose that a complete undirected graph $G = (V,E)$ with at least 3 vertices has cost function $c$ that satisfies the triangle inequality. Prove that $c(u,v) \geq 0$ for all $u,v \in V$.

I can intuitively see that $c(u,v)$ is always positive but I don't understand how to present it in a formal proof. From how I see this, for triangle inequality to hold true, $a+b\geq c$, $b+c\geq a$ and $a+c\geq b$.
From the above, we can obtain that $a+b\geq a-b$, $b+c\geq b-c$, etc. Since, sum is larger than the difference, it seems to be intuitive that all numbers positive.

I found out how to prove that each edge has positive weight. Now the issue is that there could be an edge that is not part of a triangle. Then how to prove that it is also positive? I guess we have to assume the graph to be complete. Otherwise I don't have any idea on how to solve it.


texts: Minimum number of intersections to arrive at specific set

texts:
Say I have a large number of sets (on the order of ~1000) with a smaller number of potential entries (~200), and a widely varying number of entries per set. An example:

$s_1 = \{1, 42, 133\}$

$s_2 = \{27, 283, 292, 172, 66, 62\}$

$s_3 = \{1, 42, 292, 66\}$

$...$

$s_{1000} = \{1, 133, 72\}$

Is there an algorithm more efficient than Monte-Carlo / brute force to find the minimum set of sets that I need to intersect to get a result containing exactly one specific item?

For example, given the above four sets, I would need to intersect $s_1, s_3,$ and $s_{1000}$ to arrive at a result containing only the element $1$ - the algorithm would need to find this solution (or a different solution requiring the same or a smaller number of sets), for arbitrary elements appearing in at least one set.

I have a feeling that this could be transformed into a set packing problem (which would make it an NP problem), but I am not an expert on this topic. Any input would be appreciated.


texts:
Are there useful programs that don't take inputs from a user, environment etc. such as key input, or the current time?

A program that computed/printed out predefined data could be turned into a file, right?


texts: Detect whether one Turing machine invokes another

texts:
Given two Turing machines $M,M'$, is it possible to check whether $M$ invokes $M'$?

In other words, is the following problem computable/decidable?

Inputs: Turing machines $M,M'$
Question: Does $M$ ever invoke $M'$?

Perhaps we can look whether $M$ includes the code of $M'$ in it?  In a C program we can check whether a function f invokes a function g, right?  Can we do this for Turing machines too?


texts: Could someone suggest me a good introductory book or an article on graph clustering?

texts:
For my pet project I need to cluster some data which could be easily represented as graph, so I want to use this as an opportunity to educate myself and play with various algorithms. I'd prefer the book on graph clustering as it often more self contained but articles are fine too. Back in the days I used to work in the field of numerical linear algebra so I'd also prefer algebraical view on things (so books which view graph as a matrix with specific properties are more accessible to me).

p.s. I've tried scholar.google.com but was overwhelmed by vast number of results.


texts: Is the inverse of MST cycle property always true? Why?

texts:
I am trying to find an algorithm which would check for each edge in a given weighted undirected graph whether it belongs to any of the graph's Minimum Spanning Trees.

I have found many potential solutions to this problem, which use the cycle property of MSTs, that is (quoting Wikipedia):
For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to a MST.

It is obvious to me how this property can be used to determine which edges can definitely not belong to any of the graph's MTSs, but I have doubts if the inverse of the cycle property is also true, that is if: For every cycle C in the graph, if the weight of an edge e of C is less or equal to the individual weight of any other edge of C, then this edge belongs to at least one MST.

In other words, is edge e not being the heaviest edge in every cycle containing e only a necessary condition, or a sufficient condition to e belonging to an MST?

If the above is false, then all I would want to see is a counterexample. If however this is true, could anybody prove why it is so?


texts: How do i solve this task about the the Reservoir Sampling algorithm?

texts:
Hello I have the following task (no homework).

  You are using the Reservoir Sampling algorithm. You process the 2000th element in the data stream and are maintaining a
  sample of size 500. What is the probability of the first element in the sample being replaced by the current element?

My problem is, that I have no idea how to find this probability.
I know how the algorithm works but I can't solve this task.

I hope someone can help me here.


texts: Question regarding Cook-Levin theorem proof

texts:
I know a key part of the Cook-Levin theorem proof (as presented in the book by Sipser) is that given two rows of configurations, if the upper row is a valid configuration of a nondeterministic Turing machine $N$, and every 2×3 window is consistent with $N$, then the second row is either identical with the upper row or follows from it by a transition of $N$.

Would this still remain true if we were to replace the 2x3 window with a 2x2 window?


texts: Can one insert non-unique elements into an AVL tree?

texts:
Is it possible to insert a sequence of non-unique elements into an AVL tree?

For example, what is the AVL tree result of inserting 3, 3, and 3 into an initially empty AVL tree?

Is it:

        3
      /   \
     3     3


texts:
In a question, it is given that L is a finite language over the unary alphabet and L+ is not regular.
We know that L+ = LL*
Since L is finite, it must be regular because all finite languages are regular.
If L is regular L* is also regular.
Then how can be L+ not regular? It is the concatenation of two regular languages. Where am I wrong?


texts:
Wiki and my classes Textbook defines a decider as:

  In computability theory, a machine that always halts—also called a
  decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a
  Turing machine that halts for every input.

So shouldn't this decider be able to decide the Halting Problem?
Because it halts always? I am a bit confused.


texts: Is it possible to include numerical values or constants within brackets(time complexity)?

texts:
I am currently trying to learn a bit more about the theoretical side of computer science and I have stumbled upon this example I found online:

  $5n^2 + 5n = O(0.5n^2)$

I do have basic understanding of how time complexity works but it is the only example I have found that has a number attached to the $n$ (right side). Does it mean that the person writing that article made a mistake or it is possible to include values this way (like in the definition: $0 ≤ f(n) ≤ cg(n)$ where $c = 0.5$ in this case)?

Sorry if I missed an obvious aspect of this concept but I try learning this stuff on my own and have nobody apart from the internet to ask for help. :)


texts:
I am trying to create a data structure for handling the subsets of the real line of the form $[x,y)$. That is, suppose $X \subseteq \mathbb{R}$ and the data structure supports two types of operations: $add(X, [x,y))$ and $remove(X,[x,y))$. Each of these two queries return the number of disjoint semi-intervals in $X$. For instance,

> add(X, [2, 10))
> 1
> add(X, [3, 9))
> 1
> add(X, [-1, 1))
> 2
> remove(X, [2, 10))
> 1

I suspect that this can be realised with binary search tree, however I could
not properly invent the behaviour. I still suspect this can be done in such a way that each query works in $O(\log n)$ time, where $n$ is the total number of queries. Can you please suggest anything?


texts: Finding the largest linear combination that is not possible

texts:
Regarding the problem:

What is the largest bet that cannot be made with chips worth $\$7.00 $
and $\$9.00$? Verify that your answer is correct with both forms of
induction.

I need to find an algorithmic approach, but till now my approach is to try all possible combinations with 0,1,2,3,4,5,6,7,8 (9) as the column headings and then the next row having the values as 9,10,... and so on, till able to get all values that can be generated.
All this requires an iterative approach that progressively increases the data set size, till at least 9 consecutive values can be generated.
I have found that 47 is the largest value that cannot be generated.

But, first of all this is no programmable algorithm. Second, due to first reason, I cannot prove it by induction of any type.

I feel that the algorithmic approach should consider the values that are originating from the initial set of those values that cannot be generated by any linear combination of values; i.e. 1,2,3,4,5,6,8; and then checking out which value will be the last one that can be generated from them and is not a linear combination of $9x + 7y$ (with $x,y > 0$).

If there were an approach that takes all further points that are not reachable by all the initial set of non-reachable (not having a value given by the linear combination of 9x + 7y, (x,y >0)) points (1, 2, 3, 4, 5, 6, 8); then I would be very happy to get any hint for the same.


texts: When reducing from HALT, can you create a Turing machine that asks whether a simulation stops?

texts:
Lets say I am doing a reduction from $\mathrm{HALT}_{\mathrm{TM}}$ to another language $S$, in order to prove that $S$ is not decidable. For this I need to build a new Turing machine, $M'$. Can I create $M'$ in such a way that the next step is depended upon whether or not a simulation stops? Take the following two examples:

$M' = $ "on input $M, w$:

Simulate $M$ on input $w$. If $M$ stops, go to step 2. Else: go to step 3.
....
....."

And

$M'' = $ "on input $M, w$:

...
Run $M$ on input $w$.
accept."

The first one requires the decider for $S$ to solve $\mathrm{HALT}_{\mathrm{TM}}$ more explicitly then the second one. Is the first one wrong?


texts: Emulation, interpreters and parallel execution

texts:
I'm interested in how software emulators of old game consoles work.  These must consist of an interpreter for the machine language of the emulated processor.

If I have understood correctly an interpreter, for each instruction: reads the instruction and scrolls a huge switch-case (or sequence of if-elseif-...) like structure comparing the instruction with each possible instruction in the architecture of the emulated processor, and then executes the related branch.

Is it possible to distribute the switch-case into severial thread, and give them to a parallel processor (GPGPU, FPGA, ...) ?
In my opinion, this problem is inherently parallel, because if 1 core = 1 opcode, and each core can read the next opcode, then just the right core will execute the instruction. After finishing the execution of the current instruction, then it does the same thing for the next one.

Is it a good idea to create an interpreter (slowest type of emulation, but also the easiest type of emulator and free of problems like self-modifying code) and make it faster using distribute computing?
Each instruction means a different process for a different core
No problem with concurrency, because just one instruction branch is executed.Is this a good idea or there is any problem?


texts: Cover a surface with disks of various size

texts:
I'm trying to find a cover of a surface using disks of variable sizes.
In the image, I want to cover the entire blue surface. The disks can go "out" of the blue surface and into the red part, but they cannot go outside the red area. The red area is always an "expansion" of the blue area.
I'm trying to find a solution that minimizes the number of disks used. I am not looking for the perfect solution, an approximate one is fine too!
The example shows a cross, but the shape can be anything (no holes though)
If it's easier, we could also use squares instead of circles.

Thank you :)


texts:
Using the diagram of a binary tree and algorithm answer the following:

If the following commands store(1,laurence), store(1, ron), store(1,graham), store(1,abe) and store(1,martin) are executed what will be stored at location (3)?

ron
abe
graham
empty

The answer is ron but I am struggling to work out why. How does the algorithm correspond to the tree? Thanks.


texts: Parameterized vertex cover on $r$-regular graphs

texts:
I am trying to solve the following exercise from this book:

  Show that CLIQUE PROBLEM, parameterized by the solution size $k$, is
  Fixed-parameter tractable (FTP) on $r$-regular graphs for every
  fixed integer $r$.

Here, the CLIQUE PROBLEM is given a instance $(G, k)$, decide whether $G$ has a clique of size $k$ or not.

First of all, for an instance $(G, k)$,  if $k > r+1$, then the answer is NO, because each vertex is connected with exactly $r$ elements, the maximum size of a clique is $r + 1$ (vertex plus $r$ neighbours). So, we can assume that $k \le r+1$.

Let $N(v)$ be the set of neighbours of $v$.

I thought of that simple algorithm

.... for each vertex $v \in V(G)$

........ check if for any subset $X \subset N(v)$, such that $|X| = k - 1$, $X \cup \{v\}$ is a clique.

Since there is only $\binom r k$ such subsets $X$ for each vertex and we take time polynomial in $k$ to check if $X \cup \{v\}$ is a clique, then, this algorithm is already a FTP and is of the form $\left( k^{O(1)}\binom{r}{k} \right)n$.

If everything is right, them I have solved the exercise. However, the next thing I have to do in the exercise, is to show that this problem is also a FTP considering the parameter $k + r$ (so, $r$ is no longer seen as a constant), and the same algorithm works in this case. Since I was expecting to face a harder exercise in this case of $k + r$, I started to think my solution is not right.

So, what is wrong?


texts: Linear Regression. Why do we take sum of errors to compute the cost?

texts:
While calculating the cost in linear regression (for either with multiple features or a single one using gradient descent) we compute the cost by squaring and summing up the cost related to each training set. What is the point of summing up the cost related to each training example is what I do not understand.
Why not just calculate the cost for each training example individually ?

( I am following the Machine Learning course taught by Andrew Ng on coursera. )


texts: Recurrence relations that do not have a closed form solution

texts:
A recurrence relation computes value $d_n$ with the $\{d_{i},d_{j}\ldots\}$ previous digits of the sequence

So for example, the Fibonacci sequence is defined as follows:
$$
F_n = F_{n-1}+F_{n-2},\ \ \ F_0=0, F_1=1
$$
The classic closed form solution is given by the Binet formula:
$$
F_n = \frac{\phi^n-\psi^n}{\sqrt{5}}
$$
where $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=1-\phi$.

The question is: are there such sequence of digits defined through some arbitrary recurrence relation that do not have a closed form solution, that is, that provably do not have a closed form solution?

I am asking this question in CS stack exchange because the context of this question is Random Number Generation... If such iterated sequences exist, this could be (could be) helpful in designing RNG's...


texts: How to separate a scanner input number in different digits?

texts:
Suppose I am using the scanner class and the user inputs sum number K of N digits. How can I, based on the input from the scanner, use a for loop to find what each digit is? For example, say the user enters the number 1502. How can I separate this number into each digit 1, 5, 0, 2, for all user inputs?
I have tried writing this with a while loop using modulus but I must use a for loop.
Thank you!


texts: what is the time complexity for an algorithm that operations to complete grows by 4 when doubling the input length?

texts:
I'm working on an algorithm and I'm trying to figure out its time complexity given the operations it takes to complete a input set of specific length, I have been testing the algorithm with varying input lengths.

The results shows that every time I double the input length, it takes 4 times more operations than before to complete:

20 items = 1M (M=million)
40 items = 4M
80 items = 16M
160 items = 64M
320 items = 256M
640 items = 1024M

What is the time complexity/running time that fits better with the above results?


texts: Combining insertion/deletion operations in Levenshtein distance

texts:
Considering the definition below (with $d$ as distance, $w$ as operation weight/cost and $m$, $n$ being the string lengths), the operations $del$ and $ins$ seem to represent pretty much same thing given equal weights (deletion in one string is the same as insertion in the other, and vice versa).
\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }(a_{k}),&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(b_{k}),&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{i}=b_{j}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }(a_{i})\\d_{i,j-1}+w_{\mathrm {ins} }(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{i},b_{j})\end{cases}}&{\text{for}}\;a_{i}\neq b_{j}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}
So my question is, how can we combine those operations without breaking the symmetry?


texts:
Assume we have some statement called $\alpha$. We will define a new statement $P(\alpha):="(\alpha\text{ can be proved})\lor(\lnot\alpha \text{ can be proved})"$
I claim that $P(P(\alpha))$ is always correct (that is, we can always prove\disprove whether a statement can be proved or not).
The following is a "proof" for that:
Assume towards contradiction that $P(P(\alpha))$ is not correct. Then, there is no proof for $P(\alpha)$ and also there isn't a proof for $\lnot P(\alpha)$.
Lemma: If $\alpha$ can be proved, say using some proof $p_\alpha$, then this $p_\alpha$ also proves that "$\alpha$ can be proved", hence $p_\alpha$ proves that $P(\alpha)$ is also true.
Use this lemma again and get that $P(P(\alpha))$ is true.
If $\alpha$ cannot be proved, then either that $\lnot\alpha$ can be proved or not. If it is possible to prove $\lnot \alpha$, then by the lemma we know that $P(\lnot\alpha)$ can be proved. But notice that by the definition of $P$ we have $P(\alpha)\equiv P(\lnot \alpha)$, so also $P(\alpha)$ can be proved, and once again, using the lemma we get that $P(P(\alpha))$ is true.
If its also impossible to prove $\lnot\alpha$, then by the definition of $P(\alpha)$ we have $P(\alpha)$ is false. However the "proof" up until this point proves that $P(\alpha)$ was false, since we assumed that there is no proof for $P(\alpha)$ but in every other case there was a proof. Thus, a contradiction - and hence $P(P(\alpha))$ must be true in this case as well.
My question

Is this idea "correct"?
If it is "correct", then is it possible to formalize it? how would it look like?


texts: Why do we ignore the significant digit for 2-word and 2 significant digit for 4-word?

texts:
Imagine there are 3 direct-mapped cache designs possible, all with total 8-words of data: C1 has 1-word, C2 has 2 -words block, and C3 has 4-word blocks. Assume the sequence of memory accesses is 3,180,43,2,191,88,190...etc

a) Draw a table with each reference being a row and decimal address, binary address, index, tag,Hit or miss.

I understand that $$2^3$$ is the total word,  and C1 - 1 word will have 8  # of blocks so we can just do 3 mod 8  = 3 in binary its 011
but
for C2 there is 4 Blocks but yet 3 mod 8 = 01   and we ignored the 1 from previous. why do we do that?


texts: Proving correctness of the algorithm for convex polygon minimum cost triangulation

texts:
I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be proven by induction but I struggle at choosing the right quantity to look at and also at the inductive step portion of the proof.

For example, can you provide a formal proof for the algorithm described here (page 5 problem 6.12).


texts: Machine learning: do the benefits of more data plateau after a certain point?

texts:
This question is both general in nature and also specific to computer vision. If this is the wrong forum, apologies in advance and suggestions on where to post would be much appreciated.

After a certain point, do the benefits of more data plateau for machine learning algorithms?

For instance, let's say the goal is object recognition of a basketball. Is there a plateau, say, after training on 1M images of basketballs? Or is the plateau lower at like 100K images? Or is there no plateau at all?

More concretely, can you detect basketballs with 99% accuracy after 100K samples, meaning the next 900K samples only nets an additional 1% in accuracy at most?

How about for non-image domains such as speech recognition of all words related to the weather in the English language?

It seems that if there is a plateau, it would hinge on the complexity of the domain. Assuming the data plateau exists, is there a principle for generalizing what the plateau is for a given domain (e.g., to recognize one type of object with no variations, you need about 100K images from every angle and under different lighting conditions)?


texts: Mapping graph to another graph's sub-graph

texts: How to solve the induced sub-graph isomorphism problem?


texts:
I need to create a CFG for the following language:
$$
\{a^ib^jc^k|i≤j≤2i, k=2j\}
$$

Getting the a's and c's to be correct is easy enough but everything else is confusing me slightly. any help would be much appreciated.


texts: Not convincing claim for Master Theorem Case 3

texts:
In a practice exam given in class, we were asked to solve the following recurrence

$$T(n) = 2T(n/4) + \frac{n}{\log n}$$

The given solution claims that this falls in the third case of the Master Theorem and starts with the following claim:

$$f(n) = n / \log n = \Omega (n^{1/2 + \epsilon}) \ \textrm{for any} \ 0 < \epsilon < 1/2$$

Is there a quick way to show this holds. Seeing the $\log n$ is the reason why I am doubting this claim.


texts: What are some applications of binary finite fields in CS?

texts:
I was looking at details on finite fields. Finite binary fields, e.g. $\mathbb{F_2}$, are used in CS in some places such as circuit theory [1].

  What are some key applications of finite fields in CS?

I am also looking for uses of $\mathbb{F_{2}^n}$ which Mathworld shows can be represented as binary vectors.

[1] Noga Alon and Gil Cohen. On Rigid Matrices and Subspace Polynomials. Electronic Colloquium on Computational Complexity, Report No. 133 (2012).


texts: As far as I know, a minheap is data structure whose parent node's value is less than child node and maxheap is when parent node is greater than child node. Here they have used minheap. But as the node closer to root have less length code than nodes below that level i.e., level 1 codes will have shorter codes than level 5; which means level 1 nodes are more frequently occurring than level 5 nodes. Also the numeric value after addition is also greater than that nodes at high level. I am confused, isn't that definition of max heap but they are using min heap. Please explain why they are using Min heap and not Max heap (considering nodes at lower level are more frequent than at higher level)


texts: What is time complexity of given C program?

texts:
int R(int n)
{
    if(n<=1)
        return 1;
    else
    {
        int sum=0;
        for(int i=1;i<=n;i=i*2)
        for(j=1;j<=i;j=j*2){
            sum=sum+i;
            sum=sum*R(n/2);
        }
    }
    return sum;
}

I try to explain

T(1) = 1

T(2) = 2

T(4) = 6

T(8) = 36

T(16) = 360

T(32) = 5400

so, the growth rate is higher than that of $n^2$.


texts:
Suppose, I have an array of length 100.
I have 0s at some positions and 1s at some other positions.
What is the fastest method by which I can separate the 0s and 1s, so that we get all the 0s at the beginning and all the 1s at the remaining positions / vice-versa?