texts:
Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold):

Let $r = p \oplus q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication the columns aren't summed up, but rather or'd (not xor) together. Nothing is carried.

$$
  \left[\begin{matrix}
    &&p_n & ... & p_i & ... & p_2 & p_1 \\
    &&q_n & ... & q_i & ... & q_2 & q_1 & \otimes\\
    \hline\\
    &&q_1 \cdot p_n & ... & q_1 \cdot p_i
      & ... & q_1 \cdot p_2 & q_1 \cdot p_1\\
    &q_2 \cdot p_n & ... & q_2 \cdot p_i
      & ... & q_2 \cdot p_2 & q_2 \cdot p_1\\
    &&&&&&&...\\
    q_i \cdot p_n & ... & q_i \cdot p_i
      & ... & q_i \cdot p_2 & q_i \cdot p_1 & \stackrel{i}{\leftarrow}
      &&{\bigvee} \\
    \hline \\
    \\r_{2n}& ... & r_i
      & ... &r_4& r_3 & r_2 &r_1 & =
  \end{matrix}
  \right]
$$

Using the long-multiplication-style formulation, this takes $\mathcal O\left(\max\left(\left|p\right|,\left|q\right|\right)^2\right)=\mathcal O\left(\left|r\right|^2\right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.


texts: Recurrence Formula for Bitonic Sorter Runtime

texts: A Bitonic sorter takes a bitonic sequence as an input and the output is a sorted list. I want to analyse Bitonic Sorter by knowing its depth/runtime. Can anyone give an idea on its recurreence formula? Thanks.


texts: Big $O$ approximation for $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$

texts:
I have the following complexity equation: $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$ with the base case $T(m)=1$.
Is it possible to calculate a big $O$ approximation for such equation? What is the right method to do so?
Edit:
I actually need to calculate this equation for any $1\leq{i}<\frac{n}{m}$
so if it is easier to consider $i$ as a constant, such a solution is also helpful.
Edit 2:
I think the equation is also missing floor value of $\frac{n}{m}$ so it will be coherent


texts: Efficient algorithm to find vertex with paths to every other vertex

texts:
$G=<V,E>$ is a directed graph. I need to write an efficient algorithm that finds a $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ ($v$ has a path to every other vertex), or "false" if there aren't any. If there are more than one, return one of them.

The obvious and inefficient way would be to run BFS from every vertex, checking after every run of BFS if there are vertices with distance $= \infty$. If not - that vertex has paths to every other vertex. Complexity would be $O(|E||V| + |V|^{2})$.

I can't think of any substantial improvements. If someone could point me in the right direction (pun intended), that would be great!


texts:
Schwartz-Zippel lemma is as follows. Let $f(x_1,\ldots,x_n)$ be a polynomial of total degree at most $d$ over a field $\mathbb{F}$ and assume that $f$ is not identically zero. Pick uniformally at random elements $r_1,\ldots,r_n$ from the field $\mathbb{F}$ then probability that
$$f(r_1,\ldots,r_n) = 0 \le \frac{d}{|\mathbb{F}|}$$
Let us assume that $f$ is multiplinear which means each of the monomial in the polynomial $f$ is of same degree. My question is as follows. Is the following bound (given below) tight or we can come up with a better bound?
$$f(r_1,\ldots,r_n) = 0 \le \frac{d}{|\mathbb{F}|}$$


texts:
From these notes pages 37-38. In HOL, I'm giving the task of proving:
$\vdash \forall x^T. \forall y^T. (=_T x^T y^T) \implies (=_T y^T x^T)$
applying forall and implication introduction and the definition of $=_T$ I get:
$(\forall_{T \to O} \lambda P'^{T \to O}. P' x^T \implies P' y^T), P y^T \vdash P x^T$
Here I set $P' = \lambda z^T. (=_o (P z^T)  (P x^T))$ and according to forall elimination we can prove: $P' x^T \implies P' y^T \equiv (=_o (P x^T) (P x^T)) \implies (=_o (P y^T) (P x^T))$ since I know that $=_o (P x^T) (P x^T)$ holds I have derived $=_o (P y^T) (P x^T)$ and then taking $P'' = id$ in the definition of equality we derive $P y^T \implies P x^T$.
From the text,

These two last exercises are a little trickier:  they are solved by instantiating the predicate variable by a property involving equality itself.  They therefore highlight the  feature  of  HOL  known  as impredicativity:   we  can  define  a  new  proposition(resp.  property) by quantifying over all propositions (resp.  properties); that is the quantification includes the object which is being defined by the quantification.

I don't see what they mean here. Here we are not defining anything. We are proving something. So I guess the phrase should be:

we can prove a new property by quantifying over all properties that is the quantification includes the property which is being proved by the quantification.

Ok, then it is true that above quantification is ranging over any property. However, I didn't make use of the particular property I wanted to prove. Or did I? My instantiation "includes" the property I want to prove... Is that what they mean?


texts:
I'm trying to prove that a language is not regular. That language is:

{w ∈ {a, b}* | amount of a's in w is equivalent to the amount of b's in w, mod 2}.

I have an inkling that this language is not regular, so when I go to apply the pumping lemma, I would apply it on some subset of the language, and the pump on that, right? So, let's say I choose to pump on a, and then I'm able to produce a string that should be in the language, but it isn't. I can do this because when I pump on a, I can produce a string that is not in the language because it will not be the same mod 2. But, I am having a hard time understanding if this is really true. I'm trying to construct a DFA that is able to count the amount for a's and b's, but I'm not having much success. Am I right or wrong?


texts:
T(m,n) = T(m-1,n) + T(floor(m/2), n-1)

Base conditions

T(m,n) = 1 when n = 0
T(m,n) = 0 when m < n

Edited: Below is the code for which I want to know the time complexity in terms of m and n.

#Python3 program to count total number of
#special sequences of length n where
#Recursive function to find the number of
# special sequences
def getTotalNumberOfSequences(m,n):

    #A special sequence cannot exist if length
    #n is more than the maximum value m.
    if m<n:
        return 0

    #If n is 0, found an empty special sequence
    if n==0:
        return 1

    #There can be two possibilities : (1) Reduce
    #last element value (2) Consider last element
    #as m and reduce number of terms
    res=(getTotalNumberOfSequences(m-1,n)+
         getTotalNumberOfSequences(m//2,n-1))
    return res

#Driver Code
if __name__=='__main__':
    m=10
    n=4
    print('Total number

of possible sequences:',getTotalNumberOfSequences(m,n))


texts:
I have devised the following TM for the language EQUAL.

EQUAL accepts all strings with the same number of a's and b's. It is context free but non regular.

Using the TM I devised, how can I show that EQUAL is recursive? How can I show that it crashes when the input is not in EQUAL.


texts:
Is 17x+11 a function of O(x^2)?

My steps so far:

17x+11 < c.x^2 where x>k
17x+11/x^2 < C

Im not too sure what to do next so I'd really appreciate if it someone could guide me.

This question was not answered. The link that was provided exceeds what we have to know to solve this problem.


texts: Find all the paths from node A to node B

texts:
You are given a bunch of nodes evenly spaced in a rectangular grid. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand (northwest) corner and node B is at the bottom right hand corner (southeast). From each node you can only move east, south, or diagonally southeast to the next adjacent node (assuming there is an adjacent node that permits moving in that direction). How many different paths are there from A to B?

I only found a brute-force method using a depth first search with a stack. Is there a more efficient algorithm to solve this puzzle? Specifically, I am looking for an algorithm (preferably efficient) that can determine the total number of paths you can take from node A to node B in a grid of evenly spaced nodes of size M x N.


texts: How Expensive is Projecting onto a Polytope?

texts:
I have a problem where our action set is a polytope $\mathcal P\subset \mathbb R^d$ and an algorithm that involves projecting onto the action set. For example it says to select the Euclidean projection of $a \in \mathbb R^d$ onto $\mathcal P$.

I believe this can be done efficiently if $\mathcal P$ has a small number of facets. That means we can write $\mathcal P$ in half-space form $\{x \in \mathbb R^d: A x  \le b\}$ for some matrix $A$ with a small number $F$ of columns.

I would like to say "We can use the methods of [1] to project with $O(F)$ computational cost" but am having a hard time finding a clean reference.

In practice there are loads of ways to solve this quadratic programming problem, and in practice they do not get the exact projection; they just get an approximation and hopefully let us control the error by doing more work.

For example we  can use the $F$-many columns of the matrix $A$ as the constraint functions to run Lagrange multipliers.
This turns the problem into an unconstrained optimisation problem where computing the function at each step requires adding up $F$-many things and so the computational cost is $O(F)$.

This method gives a sequence of points converging to the projection. Unfortunately these points probably won't be in the action set so we cannot stop at some finite stage and then select the approximate solutions as actions. We would like to stop at a finite stage and then project onto the action set but that gets us back to where we started!

Is there a way to get $O(F)$ complexity in such a way that our approximate solutions are in the action set? I am looking at self-concordant barriers  at the moment, but everything I can find is phrased in far more generality than needed for my problem and I cannot find a reference to the complexity.

Edit: Every self-concordant-barriers approach I can find also involves the Newton update and inverting the Hessian matrix. In general this costs at least $O(d^2)$.


texts: BFS for transforming one word to another

texts:
I'm having a hard time understand the reasoning in the solution of 18.7 in Elements of programming interviews (EPI):

Let $s$ and $t$ be stings and $D$ a dictionary, i.e., a set of strings. Define $s$ to produce $t$ if there exists a sequence of strings from the dictionary $P = \langle s_0,s_1,\ldots,s_{n-1} \rangle$ such that the first string is $s$, the last string is $t$, and adjacent strings have the same length and differ in exactly one character. The sequence $P$ is called a production sequence. For example, if the dictionary is {bat,cot,dog,dag,dot,cat}, then ⟨cat,cot,dot,dog⟩ is a valid production sequence.
Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. Assume that all characters are lowercase alphabets. If $s$ does produce $t$, output the length of a shortest production sequence; otherwise, output -1.
Hint: Treat strings as vertices in an undirected graph, with an edge between $u$ and $v$ if and only if the corresponding strings differ in one character.

Here is the solution:

The number of vertices is $d$, the number of words in the dictionary. The number of edges is, in the worst-case $O(d^2)$. The time complexity is that of BFS, namely $O(d+d^2) = O(d^2)$. If the string length $n$ is less than $d$ then the maximum number of edges out of a vertex is $O(n)$, implying an $O(nd)$ bound.

So I agree with number of vertices being $d$, and the  worst case number of edges is $d^2$. We know that the complexity of BFS is $O(V+E)$, hence $O(d+d^2) = O(d^2)$, though if we used a set to record visited vertices (or removed a vertex once we visited it from the graph), that should reduce BFS's complexity to $O(d)$. But then things get funky.

If the string length $n$ is less than $d$ then the maximum number of edges out of a vertex is $O(n)$.

don't agree with this. Imagine we have 5 words in our dictionary $\{ab, ac, ad, ae, af\}$, so $d=5$ and $n=2$. All these vertices are connected and you can see that each vertex has 4 edges leaving it... which is more than $O(n)$. You can have $26^n$ possible edges leaving the vertex, but you only have $d$ vertices in the graph, so the number of edges leaving a single vertex should be $O(d)$.
I ultimately agree that the final complexity of the algorithm is $O(nd)$, but I calculated that simply given that we can visit up to $d$ vertices (we use a visited set to prevent cycles) and for each vertex visited one we iterate over the string of length $n$ as we look for differences in the alphabet of lower characters $O(26nd) = O(nd$).
Interested to hear what people think,
Thanks :)


texts: Assigning a unique representation to equivalent circular queues

texts:
First, a few vague definitions:

Circular queues (or circular buffers) are data structures like normal queues but with their ends connected together (forming a "circle").
wikipedia

Let's say that 2 circular queues are equal if they have the exact same elements in them and the order of items in them are exactly the same.

Example: if we form  a circular queue from the string "absa" and one from "bsaa", the two will be equivalent.

My task is to group together "cyclic equivalent" strings. I'm trying to find a "base representation" for all "cyclic equivalent" strings to use it as an "index" in a hash table which would make grouping them more efficient.

Help me find an algorithm that can assign a single unique representation to all equal circular queues!

is it even possible? (let alone useful?)
what about problematic ones like "asdasd"? (see balanced bike wheel analogy)

Some ideas to base the algorithm on:

bicycle wheel analogy: Imagine your bike's wheels have colored spokes, all kinds of colors, each color having a different weight (terrible idea for everyone except for computer scientists). If you flip your bike upside down letting the wheel spin freely, the part of the wheel with the most torque will rotate to the bottom and the wheel will stay in that "base position" and that bottom point of the wheel could be called its "base index". If we recorded the order of the colored spokes starting at that point, that order could be called a linear "base representation" of the wheel. This would not happen in the case of a properly balanced wheel, which would not start rotating. What could we do in that case?
?

Some practical use cases:

finding equivalent circular transportation routes on a map (like those of public transportation) regardless of starting and ending point
?


texts: Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G

texts:
In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:

  Suppose that a friend tells you that a given
  graph G is hamiltonian, and then offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the vertices of $V$ and whether each of the consecutive edges along the cycle actually exists in the graph. You could certainly implement this verification algorithm to run in $O(n^2)$ time, where $n$ is the length of the encoding
  of $G$.

To me, for each consecutive pair $(u,v)$ of the given cycle, we could verify if it's an edge in $G$. Further we could use some color coding for each vertex to ensure we don't revisit a vertex. By doing so, we could verify if the given cycle is Hamiltonian in $O(E)=O(m^2)$ time where $m$ is the  number of vertices in $G$. Further we can see the minimum encoding $n$ of $G$ is $m^2=n$. Thus $O(E)=O(m^2)=O(n)$. Can anyone help me understand, why it is mentioned as $O(n^2)$ instead!


texts: Time complexity of euler totient function

texts:
Code for finding $\phi$(n) is

int phi(int n)
    {
        int result = n;   // Initialize result as n

        // Consider all prime factors of n and subtract their
        // multiples from result
        for (int p=2; p*p<=n; ++p)
        {
            // Check if p is a prime factor.
            if (n % p == 0)
            {
                // If yes, then update n and result
                while (n % p == 0)
                    n /= p;
                result -= result / p;
            }
        }

        // If n has a prime factor greater than sqrt(n)
        // (There can be at-most one such prime factor)
        if (n > 1)
            result -= result / n;
        return result;
    }

I don't understand how is the overall complexity $O(\sqrt{n}) $.

From the code, I see that the outer loop runs for $O(\sqrt{n}) $ time but I am not sure of how to include the time complexity of the inner loop for finding the overall complexity.

If we have n=$128$, then outer loop runs for $O(\sqrt{n}) $ time and inner loop for $O(log_2 n)$, so overall complexity is $O(\sqrt{n}) $  +  $O(log_2 n)$ which is  $O(\sqrt{n}) $.

I don't know how to extend this for general case of $n=P1^{a1}*P2^{a2}*P3^{a3}*..Pn^{an}$


texts:
I'm trying to find all the neighbors of a given cell in a voronoi diagram.
For example, given the following diagram, if I want to find the neighbors of the cell 1, then I should be able to return the points 2, 3 and 4.

Any hints on how to do so ?

[EDIT]

I didn't explained myself very well, I only have the image (pixels with position and colors), not the graph itself. My struggle is that I just can't see an efficient way to create the graph form the image.
In the image below you can see the problem better because I need an algorithm that recognizes black dots and from there search for all the neighbors.


texts: Simple question on the phrasing on a PBS Infinite Series video

texts:
What does she mean by finding the 6 qubit quantum state $|010001\rangle$ from a sphere of dimension $2^6$.

Here is the link: https://www.youtube.com/watch?v=IrbJYsep45E
at time 8:47.


texts: How to prove or disprove that f is computable?

texts:
If $f(x_1,\dots, x_n)$ is a total function that for some constant $K$, $f(x_1,\dots, x_n) \leq K$ for all $x_1,\dots, x_n$ then $f$ is computable.

I want some hints on how to prove/disprove the above claim. This an exercise from the book Computability, Complexity, and Languages. As I didn't find the solutions to the exercises online, I want to see a formal solution of such problems, if possible.


texts: Why is using a lexer/parser on binary data so wrong?

texts:
I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also context sensitive. This basically leads to having only one type of token, a token for byte.

Can someone explain why parsing binary data with a lexer/parser is so wrong with enough clarity for a CS student who hasn't taken a parsing class, but with a footing on theory?


texts: Nearest codeword in a translation-invariant code over $\mathbb{Z}^d$

texts:
Let $c_1,...,c_n,c':\mathbb{Z^d}\rightarrow \{0,1\}$ all have finite support.
Let $C$ be the linear, shift-invariant code generated by $c_1,..,c_n$.

It is possible to calculate the nearest codeword $c\in C$ to $c'$ (measured in Hamming distance)?
Equivalently, is it decidable to tell given $k$ if $C\cap B(c',k)=\varnothing$? (the equivalence of the two versions is a nice exercise).

For $k=0$ this is just asking if $c'\in C$, essentially an ideal membership problem, decidable with Gröbner bases. $d=1$ is easy.
Already for $d=2,k=1$ I'm stumped.


texts: Show that P is closed against the Kleene star

texts:
I have that question that looks kinda easy at first but it is quite hard.

  Let $L\in P$. Prove that $L^*\in P$

my approach:

I tried to generate a Turing machine but I got stuck with the thing of the poly time machine, I only managed to create a non-deterministic machine. I know that there is a complicated method with graphs or with dynamic programming, But I am asking for a full proof or a more gentle one, "computational models"-oriented and not with algorithmic approach, but both kinds of proof will be good.


texts: Intuition behind the Reversal Algorithm [ Rotation of Array ]

texts:
I know that the below program uses Reversal algorithm to rotate an array's elements to k positions to the right. But how does the Reversal algorithm works? It seems kinda magic to see. Can somebody give me the intuition or simple math explanation for me to understand.
void rotate(vector<int>& nums, int k) {
    k %=nums.size();
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin()+k);
    reverse(nums.begin()+k, nums.end());
}


texts: Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?

texts:
These lecture slides sketch a proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup  \{ a^n b^{2n} \mid n \geq 0 \}$
cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give no references as to where the proof comes from.

I was wondering, does anybody know of an academic paper or textbook that gives a full proof? I'd love to be able to cite it, but I haven't been able to find one.


texts:
In another question Initializing non-deterministic variables in QBF, I was interested about translating assertion-based pseudocode to QBF in order to have an exponentially more compact encoding compared to unrolling deeply nested loops into SAT.

While some misunderstandings in the pseudocode for that question ultimately led to several answers adding in 'cheating' simplifications not in the spirit of the original question, D.W. clarified that a full answer depends on the relationship between PSPACE and #PSPACE.

Formally PSPACE and #PSPACE are "incompatible" for comparison in a sense of being a decision problem versus a counting problem, but this artifact can be made consistent in analogy to PH versus #P. Decision classes such as PP and ⊕P find the most-significant bit of the #P counting problem and least-significant bit respectively. Reductions filling in the rest of the bits of #P output should be rather straightforward given a powerful PSPACE-complete oracle, since P#P ⊂ PH ⊂ PSPACE.

Looking at the following assertion pseudocode, it's obvious that counting solutions to either SAT (#SAT) or QBF (#QBF) is trivially possible using polynomial-space. For example, the following pseudocode would naively run in exponential time, but never uses more than a linear O(n) amount of memory. This renders, via abuse of notation, #PSPACE ⊂ PSPACE.

counter = 0
for loop_aux_0 in {0,1}:
  for loop_aux_1 in {0,1}:
    for loop_aux_2 in {0,1}:
      .
        .
          .
            for loop_aux_n in {0,1}:
              counter += f(loop_aux_0, loop_aux_1, .., loop_aux_n)
assert(counter != UINT_MAX)

Here f is an arbitrary PSPACE function that outputs 0 or 1.

If there are no objections that #PSPACE ⊂ PSPACE, how can I actually encode #QBF as part of a QBF instance?

I suggested a QBF implementation (although missing initialization) utilizing an adder circuit for counter with its output fed back in as input alongside f_ouput being the carry-in of the LSB:

∃ counter[n] ∀ loop_aux[n] ∃ f_output[1] (counter += f_output) & (f_output == f(loop_aux_0, loop_aux_1, .., loop_aux_n))

The problem with this encoding is that the counter is incremented non-deterministically without initialization, rendering any value of counter satisfiable. Can this encoding be saved with additional clauses or auxiliary variables to initialize the counter? Or is there a better way to encode #QBF in QBF?


texts: Does Dijkstra's Algorithm actually check nodes marked as visited?

texts:
I guess this is an implementation question, but I suppose it can be answered for the typical way this algorithm works.

So, most ways the algorithm has been explained to me involve going from a source vertex to another vertex so on and so forth. Will any edges going back to the source vertex or any already visited vertex actually get looked at, or does the algorithm ignore those because they already have their shortest path set up.


texts: How is the problem of sorting in contiguous runs called?

texts:
I am having a bit of brain fail and I can't remeber the name of the following problem (so I can find some literature around it...).

  Given a sequence of values, sort it in a way that equal elements are compacted in runs (contiguous subsequences of identical elements).

For instance:

$$
\{1, 2, 4, 2, 1, 3\} \rightarrow \{ 2, 2, 4, 3, 1, 1 \}
$$

The runs are not otherwise sorted -- only equality comparison is required, not ordering; and they're compacted (there should not be two different runs containing equal elements).


texts:
I'm having problems trying to understand the concept of loop invariants.

I have the following code, where M and N are predefined constants.

a = 0
b = M
c = 1
while M - c * N >= 0:
  a = c
  c = c + 1
  b = M - a * N
print(a, b)

I have figured out this code is actually a division algorithm, where in the end prints out a as the quotient of M/N and b as the remainder. But it's unclear to me what the invariant here is. Can I say c-a is the invariant since c-a=1 is always true before and after every iteration? How could I prove that in a mathematical perspective?


texts: Mutation considered harmful, but is there a safe set

texts:
Functional programming does not have mutation. Mutation is usually harmful, however mutation is sometimes beneficial. e.g. Creating a [random number] generator.

In the same way that goto is considered harmful, but now we have structured languages that give us access to a safe set of goto patterns. Is there a safe set of mutation patterns? Is there currently any research into language features that implement them?


texts: Ambiguous grammar to equivalent unambiguous grammar

texts:
I stumbled on this ambiguous grammar and I've been trying to make it unambiguous but it's still ambiguous.

Given the ambiguous CFG :
$S \to A\mid B$
$A \to aAb\mid ab$
$B \to abB\mid \epsilon$

My closet try was:

Given the ambiguous CFG :
$S \to A$
$A \to aAb\mid C$
$B \to b$
$C \to abC\mid\epsilon$

But the string "$ab$" is ambiguous


texts: How to Self Study Some particular Computer Science Subjects?

texts:
this is my first time posting on stack exchange, so excuse my naivety. I'll be straight to the point. I did my Bsc in studying Games Technology. The degree wasn't so much computer science focused and I think I've missed on some core subjects that i really need to get done with. As far as I have identified I lack some key specific subjects that i need to work on. And I'll list them:

Computer Architecture
Operating Systems
Compilers and Programming Languages
Theory of computation

The road map i've planned to follow is:

Computer Systems: A programmers Perspectivev 3rd edition
Then read Modern Operating Systems, Tanenbaum
Then go for Computer Architecture, Fifth Edition: A Quantitative Approach
Then do Compilers | Stanford

Along the way I've scouted some courses from coursera and other MOOC's to help along the way. So what do You guys think? Any comments to help me will be highly appreciated. Please feel free to suggest me to add or subtract anything from the list. Thanks

P.S My programming skills(c++/c) , Math, data structures & algorithm skills are solid so that's already covered. Thanks!


texts: How do you prove that this TM decides a language that is undecidable?

texts:
In Sipser's Introduction to the Theory of Computation, there is an exercise that asks to prove $T$ decides $A_{TM}$, which is the language

$$A_{TM} = \{ \langle M,w \rangle | M \text{ is a TM and $w \in L(M)$}\}.$$

$T$ is a TM defined as follows. On input $\langle M,w \rangle$,

Write the description of a TM $R$ that works as follows. On input $x$,

Run $T_A$ on $x$.
If $T_A$ accepts $x$ then accept.
If $T_A$ rejects $x$ then run $M$ on input $w$ and accept if $M$ does.

Run $P$ on input $\langle R \rangle$, accept if $P$ rejects and reject if $P$ accepts.

Here:

$T_A$ is a TM that decides the language $A$.
$P$ is a TM that can decide the language
$$  Z = \{\langle M\rangle | M\text{ is a TM and } L(M) = A\}. $$
$ A = \{(0 \cup 1)^a(1 \cup 2)^b(2 \cup 3)^c | a \geq b\} $.

How can you prove that $T$ decides $A_{TM}$ ?


texts:
Suppose we are doing a random walk on the infinite integer line and that we take $2n$ total steps. At every step of this walk, the position of the walker is an integer point on this line. For the next step of this walk, the walker moves to one of the two adjacent/neighboring integer points with equal probability (assume we start at integer 0). Let $S_l$ and $S_r$ be random variables denoting the number of leftward steps and rightward steps made over the whole $2n$-step walk, respectively.

There are two things I would like to show:

(1): For any $t > 0$, there exists a constant $c > 0$ such that Pr$[|S_l - S_r| > c\sqrt{n}] \leq t$.

(2): Derive a bound on $\beta$ given that  Pr$[|S_l - S_r| > \beta] \geq 1 - \frac{1}{n}$ (i.e., find a bound on $\beta$ that gives us a high probability guarantee).

One approach I'm considering is that we can take $|S_l - S_r|$ as a random variable $D_{2n}$ denoting the distance from the origin after $2n$ steps. Now we can compute $E[D_{2n}] \approx \sqrt{\frac{2}{\pi}} \sqrt{2n}$. I'd imagine that at this point I'd either need to apply a Chernoff bound or the Chebyshev inequality, but I'm not sure how to apply either in this context.


texts:
You are given the decimal expansion (double) of a rational number $p/q$, where $\gcd(p,q)=1$. How can you efficiently determine what $p$ and $q$ are?
I don't know how to solve this, but I think we need to find a repetition of digits in the number.


texts:
Let $S = \{ ⟨M,q⟩ | (\exists x) M $ reaches state $q$ when running $M$ on $x$$\}$, where ⟨M,q⟩ is coded TM M and state q.

To prove that $S$ is semi-decidable, I've tried to use the equivalence:

Language $L$ over alphabet $\Sigma $ is semi-decidable $ \iff $ There exists a semi-decidable language $M$, such that $L = \{x \in \Sigma ^ \ast| \exists y \in \Sigma ^ \ast ⟨x,y⟩ \in M\} $.

Let $L_H = \{ ⟨M, q, x⟩ ∣ M$ runs on $x$ $\& $ $M$ reaches state $q \}$ and let $H(⟨M, q, x⟩)$ be a TM which decides $L_H$. If we simulate $M$ and $M$ runs on $x$ and reaches state $q$, then H accepts and $⟨M, q, x⟩ \in L_H$, therefore all words in $L_H$ are accepted by $H$ and $L_H$ is semi-decidable. Is it enough to show that $S$ is also semi-decidable? What are other common ways to prove a language is semi-decidable?


texts: What is the fastest online sorting algorithm?

texts:
Quoting Online algorithm from Wikipedia:

  In computer science, an online algorithm[1] is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.

One is Insertion Sort, but it runs in horrible $O(n^2)$ time.


texts: Isn't an improper subset of edges of a cyclic graph, cyclic and thus not a minimum spanning tree?

texts:
This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta, Papadimitrious and U. Vazirani.

Input: An undirected graph $G = (V,E)$; edge weights $w_e$.
Output: A tree $T = (V,E')$, with $E' \subseteq E$, that minimizes
$$ \operatorname{weight}(T) =  \sum_{e \in E'} w_e. $$

My confusion arises from the fact that the edges in the minimum spanning tree are an improper subset of the edges in the original graph. If the graph were cyclic, then we would have removed the cycles in the minimum spanning tree and would have had fewer edges. How is it that we have an improper subset (containing all the edges of the original graph)?
This is the example given right before the definition and the graph clearly contains cycle edges.


texts: Turing machine that accepts $L = \{a^{n^2} | n ≥ 1 \}$

texts:
I have the following language:

  $L = \{a^{n^2} | n ≥ 1 \}$

I am trying to construct a Turing machine that accepts L. My basic idea (without success) is to use a 2-tape TM where in the 2-tape compute the string with length $n^2$. After that, I wish to compare the length of the input string in the 1-tape with the length of the string on the 2-tape.


texts: Nielsen & Chuang Exercise 3.15: Lower bound for compare-and-swap based sorts

texts:
From Nielsen & Chuang (page 138):

Suppose an $n$ element list is sorted by applying some sequence of
compare-and-swap operations to the list. There are $n!$ possible initial
orderings of the list. Show that after $k$ of the compare-and-swap
operations have been applied, at most $2^k$ of the possible initial
orderings will have been sorted into the correct order. Conclude that
$\Omega(n \log n)$ compare-and-swap operations are required to sort all
possible initial orderings into the correct order.

The compare-and-swap(j,k) operation is defined as:

compares the list entries numbered $j$ and $k$, and swaps them if they are out of order

Using an inductive argument, I understand that $k$ applications of the compare-and-swap operation sorts at most $2^k$ of the possible initial orderings into the correct order. However, I have trouble drawing the final conclusion from this, specifically that $\Omega(n \log n)$ compare-and-swap operations are required to sort all possible initial orderings.
$n \log n$ steps will sort at most $2^{n \log n}=\left(2^{\log n} \right)^n=n^n \gt n!$ of the possible orderings. So $n \log n$ steps might be enough to sort all possible orderings but I don't see why we need at least this many steps (which is what I think $\Omega(\cdot)$ means)? To me there seems to be a gap between $n^n$ and $n!$ and it's not obvious why there can't be an algorithm which solves the task by covering more than (or exactly) $n!$  but less than $n^n$ orderings?


texts: What is more effective, a do while or a while?

texts:
I mean, with the same code, if I modify a do while into a while in this way:

do {$S;$} while ($B$) into a $S;$ while ($B$){$S;$} , there is any change
in the code?

B = condition

S; = instructions


texts: How does BFS guarantee the minimum path for this problem?

texts:
https://leetcode.com/problems/bus-routes/
You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.
For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.
You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.
Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.
The solutions for this problem involve doing a BFS from each of the vertices(bus stops), but how does that guarantee a the minimum path ?


texts: Find candidate keys given functional dependencies

texts:
In my database class we practiced how to find the candidate keys, given the functional dependencies. However they were easy examples, based on a single attribute being functionally dependent on a single attribute but in our book it gives the following example of more complex functional dependencies. Let's say that I have the following relationship:

$$R(A,B,C,D,E,F)$$

with the following functional dependencies:

$$f_1: \{A,B,C\} \to \{D,F\}$$
$$f_2: \{D,E,F\} \to \{A,C,E\}$$
$$f_3: \{D\} \to \{B\}$$

and I need to find all the candidate keys. Because we need at least $3$ of the attributes to make candidate keys. Through writing out each of the tuples made up of $3$ or more attributes, I found that $\{A, D,E,F\}$, $\{A,B,C,E\}$, $\{D,E,F\}$ and $\{A,C,D,E\}$ are all candidate keys. However the catch is that either $\{A, D,E,F\}$, $\{A,B,C,E\}$ or $\{D,E,F\}$,$\{A,C,D,E\}$, $\{A,B,C,E\}$ are the candidate keys.

I think that because the definition of a candidate key is that there can't be a subset of it that's also a candidate key. Using this logic, $\{A, D,E,F\}$ would also not be candidate key as $\{D,E,F\}$ is already a candidate key. Therefore, the final candidate keys would be:

$$\{D,E,F\},\{A,C,D,E\}, \{A,B,C,E\}$$

Is my understanding of the topic correct or have I gone of the rails?


texts: How to show the running time of the following algorithm?

texts:
The outer loop runs $n$ times. The inner loop runs $\lfloor \frac{n}{i} \rfloor$ times. So it would be $O(n \cdot \lfloor \frac{n}{i} \rfloor)$. I do not know how to transform that into a proper expression involving Big Oh and n. Maybe it could be first expressed as a sum:

$\qquad\displaystyle \sum_{i=1}^n \sum_{j=i}^n \frac{n}{j}$.

for i = 1 to n:
    j = i
    while j ≤ n:
        A[j] = A[j] + 1
        j = j + i

Could you please indicate, apart from the actual running time of the algorithm, how to show the said running time?


texts: Is it decidable when a TM M gets another as inputs and checks if it fullfiills certain property?

texts:
I was asking myself if it is not possible to decide the language where a TM M gets the Godel number of a TM M' as input and the checks if, let us say, the TM M' has a certain amount of transitions.
My idea was that it is decidable because we have an countably infinite amount of Godel numbers and the number of TMs which fulfill a certain property is also countably infinite. Therefor, we could make a reduction with the Halting-problem and show via this way that it is undecidable.


texts: Partial type inference for dependent types

texts:
I'm looking for resources on (partial) type inference for dependent types.

For example there could be a type inference scheme that fails if the term doesn't have a principal type, or a scheme that makes some choices and infers non-principal types.

I'm also not sure how to integrate type inference into constraint-based type checking.

Are there any papers on this?


texts: Training a HMM with Baum-Welch gives different results across runs

texts:
I am running a Baum-Welch HMM algorithm (in R). The sequence vector contains a series of observations which have been gathered from a dataset where the data has 17 states.

I can successfully run the HMM algorithm and it converges without any problems when I set pseudo count to 1e-09, below that the algorithm fails.

My question relates to the Baum-Welch algorithm and local minima. When I run the algorithm and obtain the estimates for the emission matrix and transition matrix, I then use these as inputs to calculate the posterior probability of a sequence.

That is all fine except that when I redo all of the above (in a new R session) I get completely different posterior probability estimates. Is this because the BW algorithm is getting stuck in different local minima each time?


texts: Trouble understanding this proof about the minimum number of states of a deterministic finite automaton

texts:
So I was browsing online looking for the general structure to proving a DFA has a minimum of $n$ states for some $n$ and most of them use contradiction. However, I'm having a hard time understanding why the proof of proposition 5 works in proving the statement.

My understanding of the proof is that we assume there's a DFA consisting of $<n$ states and we construct $n$ strings. We then use the pigeonhole principle which would mean that two of these strings would have to be in the same state meaning that if we append a new string to both of these strings that are currently in the same state, these new strings should either both be accepted or rejected. This is where we want the contradiction.

I have two questions,

1) Do we have to make strings such that each would be in its own state or can we just make a set of any $n$ strings and so long as we can append something to each pair such that one of the strings in the pair is accepted and the other, rejected (leading to a contradiction)?

2) Does the proof imply that there is a DFA of exactly six states or just that there aren't any DFAs of five, four, three, two,or one state(s)?


texts: Context Free Grammar for $a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$

texts:
I'm having trouble constructing a Context Free Grammar for the following language:
$$a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \}$$

I believe it's telling me that no string can be generated that has the same number of of $a$'s $b$'s and $c$'s.  This is due to the subtraction of the second set.

A good string from a newly formed language should be something like $aaabbc$ or $abbbcc$ and so on.

So I tried breaking the problem into three parts...

Single states:

$S_{1} \rightarrow aS_{1} \mid a \mid \lambda$
$S_{2} \rightarrow bS_{2} \mid b \mid \lambda$
$S_{3} \rightarrow cS_{2} \mid b \mid \lambda$

Two States

$S_{4} \rightarrow aS_{4}b \mid S_{1} \mid S_{2}$
$S_{5} \rightarrow bS_{5}c \mid S_{2}$
$S_{6} \rightarrow aS_{6}c \mid S_{3} \mid S_{1}$

States w/AB states

$S_{7} \rightarrow S_{1} \mid S_{4}S_{6}$
$S_{8} \rightarrow S_{2} \mid S_{5}S_{6}$
$S_{9} \rightarrow S_{3} \mid S_{6}S_{3}$

with an orginal start state of   ...

$$
S \rightarrow  S_{7} \mid S_{8} \mid S_{9}
$$

However I'm having problems building strings like $aaaabbbcc$ ...

Am I forming CFG's incorrectly?  I felt like I was on the right track but now I'm quite lost.


texts: Whether following language is linear or not?

texts:
I have a language $L= \{a^nb^nc^m : n, m \ge 0\}$.

Now, I wanted to determine whether this language is linear or not.

So, I came up with this grammar:

$S \rightarrow A\thinspace|\thinspace Sc$

$A \rightarrow aAb \thinspace | \thinspace \lambda$

I'm pretty sure(not completely however) that this grammar is linear and consequently language too is linear.

Now, when I use pumping lemma of linear languages with $w$, $v$ and $u$ chosen as follow I find that this language is not linear.

$w = a^nb^nc^m, \space v = a^k, \space y=c^k$

$w_0 = a^{n-k}b^nc^{n-k}$

now, $w_0 \notin L \space (\because n_a \neq n_b)$

So, I'm unable to find whether the language is linear or not and what goes wrong in above logic with either case. Please help.


texts: Mastermind (board game) - Five-guess algorithm

texts:
The algorithm (from here) -

  Create a set S of remaining possibilities (at this point there are 1296). The first guess is aabb.
  Remove all possibilities from S that would not give the same score of colored and white pegs if they were the answer.
  For each possible guess (not necessarily in S) calculate how many possibilities from S would be eliminated for each possible
  colored/white score. The score of the guess is the least of such
  values. Play the guess with the highest score (minimax).
  Go back to step 2 until you have got it right.

I confused about the 3nd step -

what is mean -

  how many possibilities from S would be eliminated for each possible
  colored/white score

what is the "correct answer" and the "guess" here  ?

Can someone clear it some more ?


texts: Looking for a subclass of deterministic context-free languages, other than the subclass of regular languages

texts:
Let $X=\{x_1,\ldots,x_n\}$ be a finite set of alphabet and $X^\ast$ denote the set of all words (including empty word) over $X$. Clearly, $X^\ast$ is a regular language.

Is there a subclass, say $C$, of deterministic context-free (DCF) languages over $X$ such that if $L \in C$, then $ X^{\ast}LX^{\ast} \in C$ and the generating function of $L$ is a non-rational (algebraic) function?

How can one describe a DCF grammar of $ X^{\ast}LX^{\ast}$, for  $L\in C$?


texts: DES encryption - what happens if all sub-keys are the same?

texts:
What will happen if we change the DES encryrption algorithm to use the same key in each round ?

How will it affect the encryption - will it only make the encryption same as decryption or are the more effects ? I couldn't find any other possible effects in the DES standard description.

Thanks


texts: bakery algorithm, switching up the condition

texts:
I'm currently studying the Bakery Algorithm.  I understand it for what it is but now I want to switch it up a bit.

If we changed the < in the 2nd while() loop to ≤ what exactly would happen?

My take:  I don't think it'll cause starvation but I think I'm wrong.

Thanks for taking the time to read.

do {
    choosing[i] = true;
    number[i] = max(number[0], number[1], …, number [n – 1])+1;
    choosing[i] = false;
    for (j = 0; j < n; j++) {
        while (choosing[j]);
        while ((number[j]!= 0) && (number[j],j) < (number[i],i)));
    }
    critical section number
    number[i] = 0;
    remainder section
} while(1);


texts: Finding solutions to $n m\equiv x \mod n$

texts: Given a modulus $n\in\mathbb{N}$ and another natural number $0<x<n$, what's an efficient algorithm to enumerate all pairs of natural numbers $(a,b)\in\mathbb{N}^2$ such that both $a$ and $b$ are less than $n$ and $$ab\equiv x \mod n\text?$$


texts: Permute an array in O(n) time with O(1) extra space with a given ordering function?

texts:
This question arises from a problem on a problem solving site (https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately/0).

Given a sorted (ascending order) array $A$ of $N$ numbers, re-arrange the elements of A to be this order: [A[n-1], A[0], A[n-2], A[1], A[n-3], A[2], ...].  While the problem does not actually call for this specific index permutation, that's the approach I took (it will yield the correct answer).  If there is a solution that does not involve this approach, I'm interested to see it, but this question specifically is about whether or not it is possible to perform this specific data value re-arrangement without regards to the values stored in the array.

In other words, alternately interleave the maximum, minimum, 2nd-maximum, 2nd-minimum, etc.  The algorithm should run in $O(n)$ time and consume only $O(1)$ extra space.  It should work regardless of the data values in the array, including scenarios with duplicate values.

Solutions for $O(n^2)$ time with $O(1)$ space and $O(n)$ time with $O(n)$ space are straightforward.

There is a simple function that given a source index in the initial sorted array, determines its destination index in the re-arranged array.  I have a partial solution that works by starting at some index and moving through the cycles of source $=>$ destination element moving.  But I couldn't find a way to compute the locations of all the separate index-moving cycles.  Instead, after completing a cycle, I search the partially re-arranged array for pairs of values that haven't been moved yet (that hold the original, not new, ordering), and use those indices to start a new cycle (this probably means my solution is not $O(n)$ time because of this search).  But this doesn't work in general if the elements of the initial array contain duplicate values.

I have an intuition that there must must be an algorithmic move/swap index ordering dependent only on N, but I haven't been able to find one.


texts:
I am supposed to decide, if the statement is true or false and use arguments for my answer.

In every weighted n-vertices graphs:

with no negative weighted edges,
with n>10,
in which every weighted edge appears constant number of times(e.g. 1,2,3.., but not n number of times), but graphs, in which every edge has the same value, does not satisfy this condition,

there exists between every two vertices at most 4*n^3.

I tried to draw some graphs and I conclude that all of them satisfy my conditions. But I do not have general explanation.

So is that true? If not, can you say me some counter example?

Thanks.


texts:
I have one question for which I don't know any good solution (and my solution doesn't satisfy constraints). Namely, on one of the interviews i got problem like this:

  Determine the minimum possible height of the binary tree, if you could
  remove numNodes leaf nodes from the tree (where after removal of all leaf children of node n, the node n becomes the new leaf node, and can be also counted as leaf). You are given the function int minimumHeight(Node* root, int numNodes), where root is the pointer to the root of the tree, which should be completed, using any oop language.

Constraints are that you can't actually delete node from tree, and you can't use queue or stack, arraylist, list, hashmap, hashset, etc. (you cannot use any built-in c++ stl data structure, you can though make your own from scratch)  My solution used BFS where I stored for each node its level in tree using hashmap m, and created an array arr which contained all nodes, and then sorted it based on node levels in ascending order, and after that the function should return m.get(arr[arr.length-numNodes-2]). (i wrote code in java)
Without constraints I think this could work,but I guess it's not good enough.. Does someone maybe know is there some more elegant way to solve this? (without using unnecessary data structures, and maybe without any sorting) Thank you in advance!

Here if numNodes is 5, the minimum height you could obtain is 2,because first you must delete nodes with 5,11,4 or 2 value,and then you can delete nodes with values 9,6,etc. so in total you will have 5 possibly removed nodes, and 2 will be the minimum height of the tree.


texts: Transforming an array into one with descending order

texts:
Problem Description

Given an array $A$ of $n$ integers, find the minimum number of operations to turn it into a new array $\widehat{A}$ with a (weakly) descending order: we require that $\hat{a}_i \geq \hat{a}_j$ for all $1\leq i<j\leq n$. Here an operation means either increasing or decreasing an element by $1$.

For example, it requires at least $4$ operations to turn the array $[1,2,3,4]$ into descending order. One solution is increasing the first element by $2$, increasing the second element by $1$, and decreasing the last element by $1$ (then the new array is $[3,3,3,3]$, which is in decending order).

My questions:

Is the problem NP-hard?
If not, what algorithm solves this problem with the best time complexity?

My efforts

We can write this problem as an integer linear programming. Say the elements in the array are $a_1,a_2,\ldots,a_n$, and those in the new array are $\hat{a}_1,\ldots,\hat{a}_n$ then the problem is essentially an interger programming:

$$
\begin{align*}
\text{minimize}\quad &\left|\hat{a}_1-a_1\right|+\cdots+\left|\hat{a}_n-a_n\right| \\
\text{subject to}\quad &\hat{a}_1\ge\cdots\ge\hat{a}_n
\end{align*}
$$

or equivalentlly

$$
\begin{align*}
\text{minimize}\quad &t_1+\cdots+t_n \\
\text{subject to}\quad &\hat{a}_i-a_i\le t_i, &i=1,\ldots,n\\
&-\left(\hat{a}_i-a_i\right)\le t_i, &i=1,\ldots,n\\
&\hat{a}_1\ge\cdots\ge\hat{a}_n
\end{align*}
$$

But it seems not to help because the coefficient matrix is not totally unimodular, thus we cannot relax it to linear programming.

I also find a property of optimum solutions:

  If some consecutive elements are originally in non-descending order, then they must be the same in an optimum solution.

I don't know whether this property helps.


texts: Conventions on NP regarding certificates with length exponential in a variable $k$

texts:
Non-computer scientist here.  Suppose you have a problem of the following general form:

  There is a class of objects, and a restricted set of moves to pass between objects.  It is known that all such objects are related by this set of moves.  There's a problem of the form "Given two objects $X_1$ and $X_2$, can you move between them in at most $k$ moves?"

An example would be where the objects are graphs on the same number of vertices, and the moves are deletion and addition of edges.  This question is obviously NP in the sense that you can just list the additions/deletions made to get a certificate.

Now the problem is if there is no a priori upper bound on how many moves you might need to move between two objects.  In the previous example, If the graphs have $n$ vertices then you need at most $n(n-1)/2$ additions/deletions to pass between any two graphs (going from $n$ disjoint vertices to the complete graph on $n$ vertices).  Thus, asking the question with very large $k>n(n-1)/2$ can be answered easily, so the problem is in NP regardless of $k$.

However, if there is no such bound, then maybe $k$ could be very large compared to the size of your objects, requiring a large certificate compared to the size of the input (since $k$ only needs $\log k$ bits).  So if $k$ is fixed before the statement of the problem then it is in NP, but if $k$ is given together with the input then it is not.

What's the convention for dealing with this type of situation?  Do you just say that the problem is NP for any fixed $k$?


texts: Number of different output labels in Local Binary Pattern

texts:
I'm studying about Local Binary Pattern and I'm having trouble understanding the following part about the number of output labels for binary patterns from Computer Vision using Local Binary Patterns, by Pietikäinen et al. (2011):

  Another extension to the original operator uses so called uniform patterns [53]. For this, a uniformity measure of a pattern is used: $U$ ("pattern") is the number of bitwise transitions from 0 to 1 or vice versa when the bit pattern is considered circular. A local binary pattern is called uniform if its uniformity measure is at most 2. For example, the patterns 00000000 (0 transitions), 01110000 (2 transitions) and 11001111 (2 transitions) are uniform whereas the patterns 11001001 (4 transitions) and 01010011 (6 transitions) are not. In uniform LBP mapping there is a separate output label for each uniform pattern and all the non-uniform patterns are assigned to a single label. Thus, the number of different output labels for mapping for patterns of $P$ bits is $P(P-1)+3$. For instance, the uniform mapping produces 59 output labels for neighborhoods of 8 sampling points and 243 labels for neighborhoods of 16 sampling points.

I don't understand why the number of different LBP output labels is $P(P-1) + 3$. Could someone explain why?....

Thnx for any help =)

Update: I think I have some idea already :) I included an example from my book:


texts: Solve the recurrence $\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $

texts:
$$\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $$
I've found so many similar questions but I couldn't understand any of the answers explanations. When I try to draw a recurrence tree, I see that each 'level' has as many operations as nodes (because of only $\ 1 $ operation in each node) so in the first level it has $\ 1 $ node then $\ \sqrt{n} $ nodes then $\ \sqrt{\sqrt{n}} $ nodes and so forth to $\ n^{\frac{1}{2^k}} $ on the lowest level on the tree.
I get the same answer when unrolling it:
$\ T(n) = n^\frac{1}{2} T(n^{\frac{1}{2}}) + 1 = n^{\frac{1}{2}}(n^{\frac{1}{4}} T(n^{\frac{1}{4}}) + 1) + 1= n^{\frac{1}{2}} ( n^{\frac{1}{4}}(n^{\frac{1}{8}} T(n^{\frac{1}{8}}) + 1 ) + 1) + 1 = ...  $
But it is really inconvenient working with this form.
Also tried using substitution as mentioned here and then applying master theorem but with I can't understand how to make the transition back. Also a similar question here but no further explanations in the answers. I would rather use tree recurrence to solve it but substitution and master theorem also good.


texts: Changing Rabin-Karp without modulo to Rabin-Karp with modulo

texts:
I am trying to solve a string matching problem using Rabin-karp algorithm.

I made use of Horner's method for calculating hash function, but I forgot to use modulo operator. It's like this now.

(this is for starting pattern length of the big string)

  1     for(i=0;i<l1;i++)
  2     {
  3         unsigned long long int k2 = *(s1+i);
  4         p1 += k2 * k1;
  5         k1 = (k1 * 31);
  6     }

where s1 is a string containing characters,and its like

  s1[0]*(k1^0) + s1[1]*(k1^1) and so on.

and I did the same for the pattern we need to find:

  0     unsigned long long int j;
  1     for(j=0;j<l1;j++)
  2     {
  3         unsigned long long int k3 = *(str+j);
  4         p2 += k3 * k4;
  5         k4 = (k4 *31);
  6     }

Now I am going through strings of length = pattern length in the big string.
     Code for that is:

  0  long long int ll1 = strlen(s1),ll2=strlen(str);
  1     for(j=1;j<=ll2;j++)
  2     {
  3         printf("p1 and p2 are %d nd %d\n",p1,p2);
  4         if ( p2 == p1)
  5         {
  6             r1 = 1;
  7             break;
  8         }
  9         long int w1 = *(str+j-1);
 10         p2 -= w1;
 11         p2 = p2/31;
 12         long int lp = *(str+j+l1-1);
 13         p2 += ((lp *vp));
 14  }
 15     if ( r1 == 0)
 16     {
 17         printf("n\n");
 18     }
 19     else
 20      {
 21           printf("y\n");
 22      }
 23    }

where str is the big string, s1 is pattern string.

I tested for multiple inputs and I am getting correct answers for all of them but its taking a lot of time. I then realized it's because of high calculations needed when the pattern string is too long and if we use a modulo operator we can minimize those calculations.

  My question is how to incorporate modulo operator in this code while searching for patterns?

My entire  code:
http://ideone.com/81hOiU


texts: Is there a theorem that says when an array of numbers can be searched faster than linearly?

texts: I'm familiar with binary search, but I'm interested in when a collection of numbers can be searched faster than checking them all one by one with any algorithm. Binary search requires sorting to work, which means some knowledge of the structure of the collection, but maybe there is something else.


texts:
Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet? Is this even a meaningful question?

For example, if $\Sigma = \{\texttt{0}, \texttt{1}\}$, we can encode any larger alphabet using $\Sigma$, but if $\Sigma = \{\texttt{0}\}$, this can define a DFA (that say, recognizes $L = \{ \texttt{0}^k \mid k > 0\}$)... but such a DFA would never be able to recognize more "complex" regular expressions. For example, there is no way to encode $\texttt{0011}$ using a unary alphabet that a DFA would recognize (we could use, say, Godel numbering, but that would require a more powerful machine that could "count").

If DFAs with a unary alphabet less powerful than DFAs with a binary alphabet, is there a name for this language/grammar? I recognize this is kind of an odd question, since the DFA that recognizes $L = \{ \texttt{0}^k \mid k > 0\}$ recognizes all unary languages... but technically there still are a countably infinite number of DFAs in this class ($L = \{ \texttt{0}^1 \}$, $L=\{\texttt{0}^2\}$, etc.)

Note I am of course assuming that for $\Sigma = \{ \texttt{0} \}$, that it does not contain the empty symbol $\varepsilon$.


texts: Do operators in the Scheme programming language have associativity. For example, the code (- 5 2 1) evaluates to 2, but it could evaluate to 4 if it was evaluated right-associative. However, it is unambiguous if you were to write the expression as (- (- 5 2) 1). The first example, however, leads me to believe that Scheme is left-associative in the case that you do not group all operations into only two arguments at a time.


texts: What are current cache algorithms and cache strategies?

texts:
Which cache strategies/algorithms (especially for L2 Cache) are used in practice and don't exist solely in research/theory?
There is a list on Wikipedia which does not state which algorithms are really used.
Bélády's Algorithm for example would be as far as i understand it the best solution but is impossible to be used because of the unpredictability of cache behaviour.

Is there a difference when a virtualized environment is used or do hypervisors use the same strategies?


texts:
In Recent Contributions to The Mathematical Theory of Communication (Weaver 1949), aka The Mathematics of Communication (Weaver 1949) (various copies exist online), and also published as Part I of The Mathematical Theory of Communication (Shannon and Weaver 1949), Weaver says:

  We are now in a position to state the fundamental theorem, produced in
  this theory, for a noiseless channel transmitting discrete symbols.
  This theorem relates to a communication channel which has a capacity
  of C bits per second, accepting signals from a source of entropy (or
  information) of H bits per second. The theorem states that by
  devising proper coding procedures for the transmitter it is possible
  to transmit symbols over the channel at an average rate* which is
  nearly C/H, but which, no matter how clever the coding, can never
  be made to exceed C/H.

  …

  * We remember that the capacity C involves the idea of information
  transmitted per second, and is thus measured in bits per second. The
  entropy H here measures information per symbol, so that the ratio of
  C to H measures symbols per second.

I have not managed to find published errata for this text.

Am I correct to think the phrase "H bits per second" ought to read "H bits per symbol"? If not, why not?


texts: How does random number probabilities work in distributed systems?

texts:
Let's say I have a code which does coin toss at 25% win probability.

If I run this code n number of times in the same system it will yield ~25% win.
If I run this code on n devices (once each) will the result be ~25%.

n = very large number.
Are my assertions right?
Edit:My key doubt was, since computers use pseudo random numbers (which are based on a seed), will this affect this assertion (especially #2)


texts: Why would total comparison of functions solve the Halting problem?

texts:
Why would total comparison of procedures solve the Halting problem?

I've read that if all procedures could be represented syntactical e.g. in Scheme, then they could be compared structurally using the predicate =, and this would in turn solve the Halting problem.

Having read the ordinary proof why the Halting problem cannot be solved by any Turing machine (by reaching a contradition if such algorithm exists), I still cannot see why the comparison of functions would imply the contrary.


texts: Simplest Turing-complete ruleset for Markov algorithm

texts: Is there an example of a particular ruleset for a Markov algorithm that is Turing-complete? If so, what is the simplest example of such a ruleset?


texts:
What is the exact number of loop iterations here and how do you find out?

def func(n):
  i = 4

  while i < n:
    print(i)

  i = i + 1

The solution says max(n-4,0) which is theta(n), but I am confused about how they reached this. I see it starts from 4 and can guess that this relates to the n-4, but would like to be sure.


texts: Dividing unequal parts as equaly as possible

texts: I'm dividing up an animation project among 20 students. The whole film is 4955 frames long, so each student should have as close to 248 frames as possible. However, the scenes have an unequal number of frames that cannot be changed, and each student must have a whole scene (nobody can have .45 of a scene.) What is the easiest way to divide these scenes up to make sure each student gets as close to 248 frames as possible?


texts: Understanding Isabelle's implementation of coinduction

texts:
I'm studying how coinduction was encoded in Isabelle. At page 7 of the attached document, the author describes how some datatypes can be encoded as initial algebras. Here is one example:

Finite lists
The unary type constructor list, which sends each type α to the type α list of lists of α elements, is categorically given as the initial algebra on the second argument of the binary functor (F, Fmap), where (α, β) F = unit+α×β and Fmap f g = id⊕ f ⊗g.
More precisely, there exists a (polymorphic) folding bijection fld : (α, α list) F → α list making (fld, α list) the initial algebra for the unary functor (α, _) F. Here, fld = $\langle$Nil, Cons$\rangle$,
where Nil and Cons are the familiar list operations. The initial algebra property corresponds to the availability of the standard iterator for lists. Then (list, map) is itself a unary functor.

First parragraph
If $U$ is the set of types. $F: U \times U \to U$ is a functor which on objects acts like $F(\alpha,\beta) = unit+\alpha \times \beta$ and on morphisms acts as $F((f,g)) = id \oplus f \otimes g$. As usual, this functor will lead to another functor if we fix $\alpha$. Let's call it $G$. Then, one defines lists as being the initial algebra (if it exists) for the functor $G$. Let's call $\alpha \; list$ the carrier of that algebra.
I think initial algebras for polynomial functors $F: Set \to Set$ always exist so let's drop the existence matter here.
Second parragraph
$fld$ seems to be the structure mapping of the coalgebra $fld: G(\alpha \; list) \to \alpha  \; list$. So in my notation the $G$-algebra is $(\alpha \; list, fld)$. One may check that $\langle Nil, Cons \rangle$ make $fld$ work in the initiality diagram.
Now:
What is meant by the standard "iterator" for lists?
Where was $(list,map)$ defined? (I think nowhere). What is the author transmitting by saying that $(list,map)$ is a unary functor?
It may be worth reading the following section on "Finitely branching trees of finite depth" in the linked thesis.


texts: When can you ignore certain numbers in a recurrence relation?

texts:
I am trying to understand how to work out time complexities given certain recurrence relation, however I know that in certain recurrence relation some numbers can be omitted since they make no difference when $n$ gets very large. The problem i'm having is being able to identify the numbers that can be omitted.

For example

$T(n) = 3T(n/3 - 2) + n/2$ Can we omit the 2's here and use the master theorem on

$T(n)=3T(n/3) + n$ ?

What about the following

$T(n) = T(n-2) + n^2$ can we say that $T(n) = T(n) + n^2$ and once again use the master theorem?

Not really clear to me when it is OK to omit numbers.


texts: When does kernel accessing virtual memory cause problems

texts:
I'm working with the CPU Pintos and have a question that is:

In which situations can the kernel accessing the data in virtual memory via a pointer lead to problems? And how do you avoid them?

I know that the kernel can access the virtual memory via pointers to the stack, but don't understand when errors may occur.


texts: Do we have to calculate time for declaring statement in RAM model?

texts:
Do we have to calculate time for declaring statement, in my case int num3 statement. The following question was asked by professor as a post-lecture quiz. I selected t(n)=3, but the correct answer was t(n)=4.
What is the time taken by following algorithm on RAM model ?

t(n)=3
t(n)=4
t(n)=5
None of the above


texts: resource on translating imperative programs to functional programs

texts:
I'm not asking this question for the purpose of any particular project. Rather, I'm trying to understand how to translate non-trivial programs in imperative style to functional style. By functional program/style I mean one in which all objects are immutable and functions are pure, and so forth.

The only example I've seen so far of translating imperative code to functional code is for highly specific and simple code. In particular, the example that seems to be used a lot is the factorial function, and translating iteration into recursion:

//imperative -- iteration
int factorial (n)
   for i=1;i<n;i++
      x=x*i;
   end for
   return x;

//functional -- recursion
int factorial (n)
    if (n==1) return 1; else return factorial (n-1) * n

However, this is such a specific example of a function (the factorial), that it doesn't make it clear to me how in general to translate core constructs in imperative style to functional style. e.g. can we always translate a for loop into recursion?

I'm looking for a comprehensive textbook or other resource that in generality shows how to translate imperative code to functional code

How do we translate the basic building blocks of imperative code to functional code? Can we even do this in general?
How do we translate some examples of not-completely-trivial (e.g. not the factorial function) programs?
Especially interesting, are there fully general automated algorithms for doing these translations? Are they actually used? I can imagine that some compilers do something like this.
(perhaps also interesting, the opposite, translating functional code to imperative code.)


texts:
The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$:

$
max \displaystyle\sum_{i} x_i, x_i \in \{0,1\}
$

subject to

$
\displaystyle\sum_{i} w_ix_i \leq W
$

for a maximum weight $W$.

Recall that the weights in this version can be negative: we will simply select all items with zero or negative value and then solve for the remaining items with positive weight[1]

Now suppose we also want to limit the maximum weight on the negative side:

$
|\displaystyle\sum_{i} w_ix_i| \leq W
$

We can quickly see that this problem is still hard when we set $W=0$ as this would answer subset-sum.

What is the name of the problem where we have constraints on the absolute weight? As I encounter instances of this problem often I would like to read up on it and possible heuristics. I suspect that it would have long been listed as a variant of subset-sum or knapsack but I fail to find this exact problem.

[1].

$
\displaystyle\sum_{i} \{ w_ix_i | w_i \in w^+ \} \leq W - \displaystyle\sum_{i} \{ w_i | w_i \in w^- \}
$


texts: Proof Idea: How to prove the intersection of regular language and CFL is a CFL?

texts:
I know that the intersection of a regular language and a context free language is a context free language. I've seen this fact proven on here and other websites. However, after spending hours reading through proofs, I don't really understand the general idea of the proof itself. I'm not looking for a formal proof, but I am more concerned with understanding the high level idea. This is my basic idea for a proof, but there are some issues:

Given a regular language $R$ and a context free language $L$, the intersection of $R$ and $L$ is a context free language $L_1$. We know that there exists a DFA $D$ that recognizes $R$, as $R$ is a regular language. We also know that there exists a PDA $P$ that recognizes $L$, as $L$ is a context free language. Since it is a fact that $D$ can be converted into a PDA $P_1$, we know that $R$ is also a context free language. Next, we create a PDA with states as pairs of states from $P$ and $P_1$.

This is where I am getting stuck. How are the transitions modified to simulate both PDAs? And what happens to the stack?


texts: Big O: Analyzing the time complexity of an $O(n \log n)$-algorithm

texts:
For homework, the task is to verify the time complexity of quicksort. User Nick suggested on quora that one could check the number of comparisons made when doubling the input size. If the comparisons increase by a factor of around 2, we verify that quicksort has $O(n \log n)$ time complexity.

Is this a legitimate method to verify the time complexity?


texts:
My professor gave the reduction of Independent Set (IS) $\leq_p$ SAT where SAT is the set of all satisfiable propositional formulas in conjunctive normal form, and IS the set of all pairs (G,k) where G is an undirected graph with an independent set of size k, given as as an exercise and I'm a little confused as to what I am supposed to do to get this reduction.

I know that we have to define a function $f$ that'll map IS to SAT but I'm not entirely sure on how to approach this question.

Tips on intuition or how to approach this question are greatly appreciated!
Thanks in advance!


texts: Integer LP formulation and the existence of a solution

texts:
A film producer is seeking actors and investors for his new movie. There are $n$ available actors; actor $i$ charges $s_i$ dollars. For funding, there are $m$ available investors. Investor $j$ will provide $p_j$ dollars, but only on the condition that certain actors $L_j \subseteq \{1,2,...,n\}$, are included in the cast (all actors $i \in L_j$ must be chosen in order to receive funding from investor $j$). The producer's profit is the sum of the payments from investors minus the payments to actors. The goal is to maximize this profit.

Express this problem as an integer linear program in which the variables take on values on [0,1]
Show that there must in fact be an integral optimal solution (as is the case, for example, with maximum flow and bipartite matching).

I am lost on both parts for this problem.


texts: What makes a proof assistant a proof assistant?

texts:
You open a code editor, define a syntax with lambdas, a few primitives. Then you invent some nice computation rules, some cool typing rules, and write a corresponding interpreter and "type checker". Congratulations! You just built a proof assistant! Now you can formalize all of mathematics on it! Or can you? After all, what makes the thing you built a valid "proof assistant"? What constitutes a "type checker"? As far as I'm concerned, you could have actually implemented Tetris, claimed that blocks are terms, their shapes are types, and the game loop is the computation rule. Who has authority to argue you're wrong?

When it comes to implementing a "programming language", the definition is much more clear. Just invent a syntax, a set of reduction rules and prove your thing Turing-complete. Then it is as good as a programming language is expected to be. When it comes to implementing a proof assistant, I have no idea. Sure, there are common things I see present in proof assistants, so, intuitively, I know what they are. They have lambdas and the corresponding dependent function space, they have inductive datatypes and their introductions and eliminations, and they must be consistent, which mean at least some type is uninhabited. But what if my "proof assistant" has no lambdas nor datatypes? It could have for example just combinators. I don't have a precise definition of what makes a "type theory" a "type theory".

What, formally, makes a program a valid proof assistant, in the same sense that Agda/Coq are? What is a precise and complete definition of a type theory? And what one must do to "justify" his syntax, reduction and typing rules? I'm making this specifically because, while I feel like I can, given enough time, implement something like A Cosmology of Datatypes, I do not feel the freedom to make any change, even minimal, to whatever the author did, because I do not know what justifies those things he did.


texts: Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation

texts:
I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same answer. My steps are below.

Given $T(1) = 1$, $T(2) = 1$ (Time taken is constant in these two cases)

I noticed that by unrolling a few times:
$$T(n) = 2\left[2T\left(\frac{n}{4}\right)+\frac{n}{2}\log{\frac{n}{2}}\right] + n\log n$$
$$T(n) = 2^{2}T\left(\frac{n}{2^{2}}\right)+n \log{\frac{n}{2}} + n\log n$$
$$T(n) = 2^{2}\left[2T(\frac{n}{8})+\frac{n}{2}\log{\frac{n}{4}}\right]+n \log{\frac{n}{2}} + n\log n$$
$$T(n) = 2^{3}T\left(\frac{n}{8}\right)+2n\log{\frac{n}{4}}+n \log{\frac{n}{2}} + n\log n$$

This looks like it follows
$$T(n) = \underbrace{2^{k}T\left(\frac{n}{2^k}\right) + 2^{k}n\log\left(\frac{n}{2^{k+1}}\right)}_{\log_2n \text{ times}}$$

I use the fact that $\frac{n}{2^k} = 1$, so $k = \log_2n$. Substituting this in: $2^{k}T(\frac{n}{2^k})$ = $2^{\log_2n}T(1) = n$

Doing this summation as:
$$T(n)=n + n\log_2{n}+\sum_{k=0}^{\log_2{n}-1}2^{k} n \log_2\left(\frac {n} {2^{k+1}}\right)$$
$$T(n)=n + n\log_2{n}+n\sum_{k=0}^{\log_2{n}-1}2^{k} \log_2\left(\frac {n} {2^{k+1}}\right)$$
$$T(n)=n + n\log_2{n}+n\sum_{k=0}^{\log_2{n}-1}2^{k} \log_2(n-k+1)$$

This is where I get stuck, I have a feeling I messed something up somewhere and it is making this summation much harder to solve, but I am not sure where. Where did I go wrong?


texts: Proving inexistence of a PCOMPLETE language in log logarithmic space cannot exist

texts:
Hello and thank you for helping me understand the following:

I am trying to understand why the following cannot exist: A P-Complete language in regards to a log-logarithmic space.

context: Defining a new kind of reduction: a reduction in log-logarithmic space. For this purpose, we define a log-logarithmic transformer that is identical to a logarithmic transformer, but its working tape can hold $O(log(logn) $symbols and not $O(logn)$ symbols.

We'll say a language A can be reduced in a log-logarithmic space to language B and denote $A ≤_{LL}B$, if exists a transformer with log-logarithmic space that applies a mapping reduction between A to B.

Now, Language C will be called P-complete in regards to reduction in log-logarithmic space if:

C belongs to class P
For every language A in P exists a reduction in log-logarithmic space to C(meaning $A ≤_{LL} C$).

I am quite lost and all of the hierarchies involved and I cannot understand why this P-complete language cannot exist in log-logarithmic space. Would be very glad if you could help me understand it and elaborate so it will be clear.

Thank you very much for your much appreciated help.


texts: A Question about a Question related to Graph Theory and Maximum Flow

texts:
The following question is from the book "Introduction to Algorithms" By Cormen and three other authors.

$26.2-10$
Show how to find a maximum flow in a network $G = (V,E)$ by a sequence of at
most $|E|$ augmenting paths. (Hint: Determine the paths after finding the maximum
flow.)

I find this question confusing because the hint contradicts the question. Is it asking you to find the maximum flow in a graph? or is it asking you to find a path?

Recall that for a given flow graph $G$ there might be several flows that yield the maximum flow. Is this question asking you to find all the flows that produce a maximum flow? Do you think this question is properly worded?

Bob


texts:
In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The $q_2$ state is eliminated first.
The provided solution to eliminate $q_2$ is:

If we first eliminate $q_2$ we obtain an intermediate automata with $3$ states
$(q_0$,$q_1,q_3)$ such that:

  We go from $q_0$ to $q_1$ with RE $a+ba$
  We go from $q_0$ to $q_3$ with RE $bb$
  We go from $q_1$ to $q_1$ with RE $ba$
  We go from $q_1$ to $q_3$ with RE $a+bb$

I don't understand nr2. $q_3$ can also be reached using RE $aa$. Why is this left out?

:

:


texts: How are games like chess provably harder than NP?

texts:
From this question, I had the debate about how problems harder than NP are proved.
I said that intuitively I understand it as (from this video explaining that some problems are provably harder than NP):

Generalized chess is harder than NP, and is EXPTIME-complete for the
decision problem "Given an nxn board with a given position, can white
force a win?" because the proof would require an exponential amount of
steps to show that each branch of the tree eventually leads to a win.
Therefore it's not in NP.

And a user replied:

Your first paragraph is faulty. It has the form "because this one
algorithm I thought of takes exponential time, the problem must not be
in NP". That's faulty -- maybe there's some other algorithm you
haven't thought of that's better.

I'll admit I'm still new at this and the user that wrote the above comment has much more experience in the field than I do. So I trust this user is correct. However, the explanation the video gave seems very intuitive. But can anyone explain why the video's explanation is wrong?
My thought process is as-follows. One of the definitions of NP is "the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes"." So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win. This cannot be done in less than exponential time and thus is provably harder than NP.


texts: Conceptual explanation of negative weights?

texts: What conceptually are negative weights on graphs? Why might they have them?


texts:
I cant find a way to implement a certain solution. Let me flesh out the problem.

Somebody gives you X amount of money and sends you to the shop to buy Y amount of items. You must spend as much money as you can and buy as many items as you can. You cant have more money they X. You cant buy more than Y amount of items. Some money can left afterwards, but as little as it can. You can buy less than Y items, but only if there is no other option. You cant buy same item more than once - items are unique.

Examples:

You have 15£, and need to buy 2 items. There are 4 items for 10£, 5£, 4£ and 3£. You buy 10£ and 5£ items. Perfect scenario - 15£ spend, 2 items aquired.

You have 15£ and have to buy 3 items. There are 4 items for 4£, 3£, 2£, 1£. You buy 4£, 3£ and 2£ items. 9£ and 3 items aquired.

You have 15£ and have to buy 2 items. There are 4 items for 20£, 19£ and 14£. You buy only 14£ item.

I think you understand by now how it works.

Implementation(Javascript):

var arrayOfItems = [];
arrayOfItems[0] = {"name":"Sandwich","price":15};
arrayOfItems[1] = {"name":"Water","price":10};
arrayOfItems[2] = {"name":"Cookie","price":5};

function getItems(moneyAmount,itemsAmount){
    //your code here....
}

var items1 = getItems(21,2); //returns [0,2]
var items2 = getItems(25,2); //returns [0,1]
var items3 = getItems(14,2); //returns [1]

I need to invent the inside of getItems() function. Can you lead me how to do this?

Thank you for help.


texts: Getting from one language to the other using closure properties(automata)

texts:
I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$$

Such that:

$m,n,o \geq 1;$

$m>n>o>0;$

$i_1,i_2,...,i_{2m} \geq 0;$

$j_1,j_2,...,j_{2n} \geq 0;$

$k_1,k_2,...,k_o \geq 0$

this language is also: $$L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$$

My attempt: basically, they both look very similar, but I am not sure the coming procedure is correct:  If we take $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$, Unionize bc, ef and hq to obtain the following: $L=\left\{aB^{i_{2m}^*}dE^{j_{2n}^*}gH^{k_o^*}\right\}$, And then using assignment or homomorphism, defining $h:B^{i_{2m}^*} -> 0^{i_{2m}^*}$, $h:E^{i_{2n}^*} -> 1^{j_{2n}^*}$ , $h:H^{k_o^*} -> 2^{k^*_o}$ obtaining: $L=\left\{a0^{i_{2m}^*}d1^{j_{2n}^*}g2^{k^*_o}\right\}$. Since we can decompose string S using the pumping lemma into $S=uvxyz$ as we choose, We can only regard the $0^{i_{2m}^*}1^{j_{2n}^*}2^{k^*_o}$ part. Because of that, And knowing in advance that $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$ is not context free, we can deduct that $L=\left\{a0^{i^*_{2m}}d1^{j^*_{2n}}g2^{k^*_o}\right\}$ is not context free as well.

Would really appreciate your corrections or knowing if there exists a better and easier way to deduct that.

Thank you very much.


texts: Bipartite matching using Dinitz's Algorithm

texts: How can we show the size of a matching found using Dinitz's algorithm in terms of the size of the largest matching? So, for example, can we prove that there is some small constant $a$ for which $M \ge (1-a)M^*$, where $M$ is the matching we find and $M^*$ is the size of the maximum matching?


texts: Lower-order term constraints and wrong guess

texts:
I'm a self-taught and I'm studying from CLRS.
I'm having difficulty with this recurrence relation:
$$T(n)=3T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + n$$

The problem is that I can "prove" that $T(n) = \mathcal{O}(n)$. It's absurd.
My inductive hypothesis about $\mathcal{O}(n)$ is:
$$\exists c \gt 0 \,\,\exists n_0 \gt 0 \,\,\exists b \ge 0 \quad\forall n_0\le k\lt n \quad T(k) \le ck - bn \le ck $$

From here I haven't problem during the "proof":
$$\begin{align}
T(n) &\le 3\left(c\left\lfloor{\frac{n}{2}}\right\rfloor - bn\right) + n
\\ &\le 3\left(c\frac{n}{2} - bn\right) + n
\\ &= \frac{3}{2}cn - 3bn + n
\\ &= \frac{3}{2}cn -n(3b - 1) \qquad\qquad (1st)
\\ &\le cn
\end{align}$$

The latter holds $\forall b \ge \frac{c+2}{6}$ and it comes from:
$$\frac{3}{2}cn - n(3b - 1) \le cn$$

--EDIT--
It's also easy to prove that
$$(1st) \le cn - bn$$
It holds $\forall b \ge \frac{c+2}{4}$
So $$T(n) \le cn - bn$$
--END EDIT--

So I think that the hypotheses are wrong. Probably I misunderstanding subtraction of lower-order term. What are the constraints to apply this technique? Only that $T(k) \gt 0$? In this recurrence the latter seems valid.

Synthesis: https://cs.stackexchange.com/questions/65549/lower-order-term-constraints-and-wrong-guess/65579?noredirect=1#comment139380_65579


texts: Getting the essential from the fundamental matrix

texts:
Is it possible to get E from F? I suppose that can't work, because then I could calculate the the extrinsic (and maybe also intrinsic?) parameters of the cameras without a calibration object of known size etc. like so:

Pick (8) corresponding points in images i1 and i2
Calculate F with the eight-point-algorithm
Calculate E from F
Determine relative position and orientation of cameras from E (and maybe it is also possible to get the intrinsic parameters, K?)


texts: Amortized analysis - increment in ternary counter

texts: What is the amortized analysis of increment action in a ternary counter that is initialized to 0?


texts:
How would I go about making a Turing machine to accept the following language L?

$$L = \{ www \mid w = \{0,1\}^* \text{ and } w > 0\}$$

I was thinking counting the number of symbols in the input string and then dividing by three to find the beginning of each instance of w and then testing if each instance is the same, but this seems a bit roundabout.

I feel like there is a way by marking the first three symbols and then moving the 2nd and 3rd markers until the strings in between them are the same but I'm having a hard time articulating this into an algorithm.

Can anyone point me in the right direction?


texts:
I'm being asked this question for my computer conceptes class, can't find anything about this in my text book, and have only been able to find half-baked answers googling it.

Why is binary subtraction referred to as the invert-add-shift-add method?


texts: why is discrete maths needed to understand algorithms?

texts: I am new to algorithms. I need to know is it necessary to study discrete maths to understand algorithms. If so, why? In particular, is it necessary for understanding algorithms or is it only necessary for making your own algorithms (when you need to prove algorithm correctness).


texts: Does NTIME($n^\alpha$) $\subset$ EXPTIME imply NP $\subset$ EXPTIME?

texts:
I think I'm able to prove NTIME($n^\alpha$) $\subset$ EXPTIME for arbitrary $\alpha$.

Is this a new result?
If it was, would there be a way to deduce NP $\subset$ EXPTIME from it?


texts: Time complexity of pairs in array double loop

texts:
I know, that the following is: O(n^2),
int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

But, should something like count = count + 1; be taken into account?
For predicting or making up a complex time equation, or using sum notation,
n + n-1 + n-2 + n-3 + (…) + 1


texts: What linked list data structure adjustments would give me fast random lookup?

texts:
I am presently using an doubly linked list (C++ std::list) to hold a bunch of records that each have a unique integer identifier.  The linked list is created in sorted order such that in the list, the next item always has a larger unique identifier than its predecessor.

The issue I'm facing is that occasionally I need to be able to insert an item quickly into its  relative sorted position and using a plain linked list means this operation is $O(n)$ which is causing performance issues for me.  Generally, this would mean I want to use something like a binary tree (C++ std::map), however, I am also depending upon the following feature of a doubly linked list for good performance:

Ability to splice a contiguous section out of one linked list into another in $O(1)$ time. (Amortized $O(1)$ or $O(\log \log n)$ would be good enough.)

One feature of my data that I would like to leverage is that I often have long ranges of contiguous records where each one's unique integer is exactly one more than its predecessor.  When searching for an item's relative sorted position, it would always be outside such contiguous records since there are no duplicate identifiers.

I'd like to find a replacement data structure or augmentation to a doubly linked list that will allow me to continue to splice whole sections from one list to another in constant time but allow me to locate the sorted position in which to insert a new record in better than $O(n)$ time.

Other operations include forward and backward iteration across the items. The record indexes begin at zero and grow upwards towards 64 bits, generally sequentially, and the code works well in such cases. Occasionally some records are not available before subsequent ones, it is the insertion of these missing records that causes the performance issues now.

One possible approach that occurs to me is to cache the location of several indexes.  The cache would get invalidated whenever a splice removes items that might overlap the cached entries.  With this cache, instead of doing a linear search, the search could instead begin from the cache point iterator whose unique index is closest to the one whose position is being  searched for.  However, I'd like to more fully utilize the feature of the contiguous records.  I also thought about a hierarchical linked list where I have a top level linked list of contiguous regions, where each region is a linked list of records that are consecutive, but I didn't see a clean way to adapt a linked list to provide this functionality.  Perhaps something like this has been done before?  I find skip lists to be close, but do not see the splice() functionality, plus a generic skip list would not leverage the fact that insertion never occurs within contiguous records.


texts: How to solve $T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right]$?

texts:
I am trying to find $T(n)=O(f(n))$, where  $$T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right],$$ where $m\in\{1,2,\ldots,n\}$.

Is it possible to find $f(n)$ such that $T(n)=O(f(n))$?

I started to fix $m=n/2$ (which I assume the worst scenario, isn't it?). I found $$\begin{align}T(n)&\leq n^2+\frac{n^3}{2}+\frac{n^4}{8}+\frac{n^5}{64}+\frac{n^4}{4}T(n/16),\\ &\;\vdots\\&
\leq n^2+T(1)\sum_{i=1}^{(\lg n)-2}\frac{n^{i+2}}{\sqrt{2^{i(i+1)}}}.\end{align}$$


texts: Complexity of Hamilton path in directed complete bipartite graphs

texts:
Finding a Hamiltonian path in a directed bipartite graph is NP-complete.

  Problem 1 What is the complexity of the problem if we insist that the underlying graph of the digraph be complete bipartite? Is this known? (In other words, what is the complexity if the digraph is semicomplete bipartite, not just any bipartite digraph)

There is a variant of the problem we wish to consider

  Problem 2 What is the complexity of the problem if the underlying graph is complete bipartite (that is, the digraph is semicomplete bipartite), and we specify the starting and ending vertex of the path?


texts: What are efficient data-structures for insert/delete by index?

texts:
First of all, a definition of the operations:

Insert by index: insert element e at index n, increasing the index of all subsequent elements,
Delete by index: delete element at index n, decreasing the index of all subsequent elements,
Access by index: access element at index n.

The interface, therefore, is that of a Dynamic Array.

The simplest implementation of a Dynamic Array is to use an array with exponential growth. The performance of the various operations are:

Insert/Delete by index: O(N),
Access by index: O(1).

Which is great for frequent access, but not so for frequent modifications.

An Order Statistics Tree, that is a binary tree with each node augmented with the number of elements in the sub-tree it roots, has more balanced performance:

Insert/Delete/access by index: O(log N).

It can be implemented using an Eytzinger (BSF) layout for cache friendliness.

Are there more efficient data-structures for insert/delete by index?

Notably, keeping all 3 operations sub-linear, is it possible to improve on O(log N)?


texts: Number of pairs of indexes of two arrays such that one element is greater than the other

texts:
Let $A$ and $B$ be two arrays of size $n$. How many pairs of indices $i, j$ satisfy $1 \le i < j \le n$ and $A[i] > B[j]$?

After quite a bit of thinking the best i had gotten to was make a for loop inside of another, which i don´t think it´s a good solution. So i´d like to know some ideas on how to implement this algorithm more efficiently (possibly $O(n)$, if it´s possible).

Thanks ahead.


texts:
According to the wiki-article, http://en.wikipedia.org/wiki/Tf%E2%80%93idf the term frequency of term $t$ in document $d$ is given as follows:
$$
tf(t,d) = 0.5 + \frac{0.5 \times f(t,d)}{\max{\{f(w,d): w~\epsilon~d\}}}
$$

This is the augmented way of computation. But what does $w$ stand for?


texts: How to choose waiting process in a preemptive priority-based scheduler

texts:
If my CPU schedule is preemptive priority,
and I have no new processes coming, how I should choose from the waiting processes?


texts:
I would like to demonstrate that sometime radix-sort is better than quick-sort. In this example I am using the program below:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <time.h>
#include <math.h>

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

void bin_radix_sort(int *a, const long long size, int digits) {
    assert(digits % 2 == 0);

    long long count[2];
    int *b = malloc(size * sizeof(int));
    int exp = 0;

    while(digits--) {
        // Count elements
        count[0] = count[1] = 0;
        for (int i = 0; i < size; i++)
            count[(a[i] >> exp) & 0x01]++;

        // Cumulative sum
        count[1] += count[0];

        // Build output array
        for (int i = size - 1; i >= 0; i--)
            b[--count[(a[i] >> exp) & 0x01]] = a[i];

        exp++;
        int *p = a; a = b; b = p;
    };

    free(b);
}

struct timespec start;

void tic() {
    timespec_get(&start, TIME_UTC);
}

double toc() {
    struct timespec stop;
    timespec_get(&stop, TIME_UTC);
    return stop.tv_sec - start.tv_sec + (
        stop.tv_nsec - start.tv_nsec
    ) * 1e-9;
}

int main(void)
{
    const long long n = 1024 * 1024 * 50;
    printf("Init memory (%lld MB)...\n", n / 1024 / 1024 * sizeof(int));

    int *data = calloc(n, sizeof(int));

    printf("Sorting n = %lld data elements...\n", n);

    long long O;
    tic();
    O = n * log(n);
    qsort(data, n, sizeof(data[0]), cmpfunc);
    printf("%lld %lf s\n", O, toc());

    int d = 6;
    tic();
    O = d * (n + 2);
    bin_radix_sort(data, n, d);
    printf("%lld %lf s\n", O, toc());
}

It performs as follow:

$ gcc bench.c -lm
$ ./a.out
Init memory (200 MB)...
Sorting n = 52428800 data elements...
931920169 1.858300 s
314572812 1.541998 s

I know that Quick Sort will perform in O(n log n) while Radix Sort will be in O(d (n + r)) ~= O(6 * n). For n = 52428800, log(n) = 17. I am then expecting Radix Sort to be 3 times faster than Quick Sort...

This is not what I observe.

What am I missing?


texts: Language of decimal encodings of cubes is not regular

texts:
Prove that the language that consists of cube numbers as strings is not regular.

I wanted to use pumping lemma but couldn't
$$0, 1, 8, 27, 64, 125, 216, \dots$$


texts: How to validate usability of software frameworks

texts:
My thesis will produce a software framework that can be used by programmers to solve problems in a paticular domain.
One of the case studies I want to do to verify the contribution I'm making is to have some measure of usability of the framework.
I'm looking for techniques to test a software framework that will be used by other programmers, not so much end users.
When including 'usability' in my searches the results lead to end-user UX/UI usability.

I ultimately want to run a test where one or a few programmer try to use the framework on a given problem. To help make sure the test has usable results I want to plan the strategy before hand and first consider existing techniques. But finding existing research or tests about usability of code libraries/frameworks is difficult to find.

Please let me know if you can think of a way to validate the usability of my software framework.

Thanks for reading my question


texts: Other greedy choices to solve activity selection problem

texts:
I have been studying about activity-selection-problem and the solution of greedy choice I came across is to select the activity that finishes in the earliest among the present activities.

But surely there are other greedy choices to solve the problem. The one I have been able to figure out is to select the activity that starts last.

My question is: are there any other greedy choices that can lead to solve activity selection problem? Any formal proof is also appreciated.


texts: Are there polynomial-time algorithms whose input is global but output is local in nature? What I have in mind is a problem instead of an algorithm. It’s the satisfiability (SAT) problem. Each clause is global information, because it’s surrounded by a host of satisfiable assignments, or rather their inverses, in the search space. But the goal, a satisfying assignment, is very local, i.e., one point in the search space. I want example problems and solutions that might shed light on SAT.


texts: Can we use Axiomitization to decide CTL*?

texts: As the title says. There are axioms for CTL*, but can we use them to decide whether a formula is satisfiable? We can use the trick $p$ is satisfiable $\iff$ $\lnot p$ is not valid. My problem is that the formulas arent growing monotonically, so we would never know when to quit.


texts: finite state transducer where concatenation of all UIO sequences is shorter than its shortest distinguishing sequence?

texts: Is there a finite state transducer which has a set of Unique Input/Output sequences such that, when the UIO sequences are concatenated together, the resulting string is shorter than its shortest preset distinguishing sequence, supposing that the finite state transducer has a preset distinguishing sequence?


texts: How to judge whether a point is inside a closed surface

texts: Give the point cloud of a closed surface(triangle mesh models), how to judge whether a point is inside the closed surface? As we know, in 2-D situation, there are some algorithms to do this.