texts:
Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of unity, it can be interpolated in $O(n\log n)$ time with the Fast Fourier Transform. Or at least, that's the only situation that I am aware of that can be done better than $O(n^2)$.

Are there any other forms of input that can be interpolated in better than $O(n^2)$ time?

I am particularly interested in knowing whether or not there is an algorithm that interpolates a polynomial from evenly spaced points (in the x-coordinate that is) that beats $O(n^2)$, because I think I've come up with something that does it in $O(n\log n)$ time.


texts:
Context: I have 100 speech sentences that I asked my friend to speak. The vocabulary in the sentences are same but only the order of words are changed. My friend says that he spoke exactly what was asked for each sentence. But I don't know whether he spoke exactly that sentence or something else. What I have here is those 100 reference sentences against which I need to match his speech samples. As I want to do it by computer and not by listening manually therefore I am seeking your guidance.

Data: I have been able to segment the words in each speech sample of my friend. So I have 100 sentences each segmented into individual words with sequence of each word preserved for each sentence. I have extracted required features from each word (MFCC + Delta and Delta Delta).

What I am looking for: I need your guidance and help in informing how can I recognize these words with over 95% accuracy. As I read many papers and articles, GMM + HMM is the reasonably good way to do this. But I have a confusion, when I have already segmented every sentence, why should I try to match the entire speech sentence by transitioning state to state using HMM? I can simply match each word and see if the sequence is same with respect to the reference sentence word sequence. Is GMM + HMM the way to go for this? Can I use DTW or Neural Network or SVM to classify (matching or not matching) each word and get high accuracy?


texts: Doest sorting accept a dynamic programming solution?

texts:
Are there any known / efficient dynamic programming solutions to sorting?

I understand of course that dynamic programming applies to scenarios where we have overlapping subproblems and optimal substructure, but I wonder if there are transformations and representations of the sorting problem where these conditions are met, and even better, where doing so may actually be useful.


texts: d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

texts:
Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap.  if adjusting d,  we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$.

Then for a fixed $|V|$, what is the largest possible ratio between this runtime and the runtime of Dijkstra using a Fibonacci heap?  Where knowing the Fibonacci heap: delete_min = $O(\log |V |)$, insert/decrease_key = $O(1)$ (amortized) and $|V|$ × delete_min + $(|V | + |E|) $ x insert $= O(|V|\log|V|+|E|)$.

On the other hand, d-ary heap implementation : delete_min = $O(\dfrac{d \log|V|}{\log d})$, insert/ decrease_key =$O(\dfrac{\log|V|}{\log d}$), and |V | × delete_min + (|V | + |E|) × insert  =  $O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d})$.

As trying to follow a provide solution, but I am not sure why it reduces to $O(\dfrac{\log|V|}{\log |E|/|V|})$, in the case 1 where |E| dominates, so Dijkstra with Fibonacci heap is $O(|E|)$. How can we get the ratio as $O(\dfrac{\log|V|}{\log |E|/|V|})$ while Dijkstra with d-ary heap is $O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d}$)?


texts: Creation of skip list: Las Vegas or Monte Carlo?

texts:
I have come across this video on skip lists:
https://www.youtube.com/watch?v=UGaOXaXAM5M
Clearly, the creation of skip-list from a sorted singly linked list is a randomized algorithm.
But I am confused: is it a Las Vegas algorithm or a Monte Carlo algorithm?
I feel it is a Monte Carlo algorithm since there is a possiblity of an incorrect output(degenerate case where every node is in every level), and if we don't maintain a checking condition, we won't know where the algo went wrong.
Am I correct?
P.S. My first question here.


texts: Proving that an orthogonal pyramid may be partitioned by diagonals into convex quadrilaterals?

texts:
I've included an example of one such orthogonal pyramid. I would like to find a way to prove that this orthogonal pyramid can be partitioned by diagonals into convex quadrilaterals, and do so with an algorithm in linear time. My understanding is that a sweep-line algorithm from top to bottom would work well. However, I am not quite sure how to proceed with it.

Some additional info: An orthogonal polygon is a polygon in which each pair of adjacent edges meets orthogonally. An orthogonal pyramid (like the one pictured above) is an orthogonal polygon monotone with respect to the vertical that contains one horizontal edge (h in our case above) whose length is the sum of the lengths of all the other horizontal edges.


texts: Why can't I run a mac program natively on windows?

texts: Basically, I believe that if you have something like a .dmg file the OS opens it with a certain program which takes the code behind it and does things to it. So why couldn't you then take the program that runs the .dmg file on Mac and put it on window to run the program? I know I'm probably missing some key component here that makes me wrong but I have no idea what; I'm a bit of a noob to so take it easy on me.


texts: How to convert statement with the existential quantifier to statement with universal quantifier?

texts:
How to convert the following statement with the existential quantifier to statement with universal quantifier?

$\exists n. n>1\rightarrow x(n)\not=1$

Please give me some suggestion?


texts: For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)?

texts:
For which $c, d$ is $Gap2SAT[c, d]$ in $P$  (such that $0<c<d<1$)?

(I know if d=1 then for each c it will be in P, however with which c,d such that  $0<c<d<1$ can I simply return YES?)


texts: What is the difference between user-level threads and kernel-level threads?

texts:
After reading several sources I'm still confused about user- and kernel-level threads.

In particular:

  Threads can exist at both the user level and the kernel level

What is the difference between the user level and kernel level?


texts: Prove that if for every vertex in $G[U]$ there is an edge in to every vertex in $G[V-U]$ then there is a path from every $u$ to every $v$

texts:
Given a connected directed acyclic Graph $G=(V,E)$ and a subset $U\subseteq V$. Prove that if for every vertex in $G[U]$ with out-degree zero there is an edge in $G$ to every vertex in $G[V-U]$ with in-degree zero, then there is a path from every $u\in U$ to every $v\in V\backslash U $.

I thought maybe to try a proof by contradiction- suppose that $u\in U$ and $v\in V\backslash U $ so there isn't a path $u\leadsto v$. Divide to four cases based on the out-degree of $u$ and the in-degree of $v$,
so when the out-degree of $u =$ the in-degree of $v= 0$, it is straight forward contradiction, but with the other case I'm having some trouble.
Maybe there is an easier way to prove the given proposition?


texts:
Task:
Design a 2 bit comparator.

Input: 2x 2 bit (I take it as 2 2-bit values, let them be unsigned for simplicity)
Output: 1 if result input1>input2 is true, 0 otherwise

Develop truth table and derive circuits.

The problem: I'm completely new to this so I have not even a idea where where to look for the lighthouse.

The question: I'M NOT LOOKING FOR COMPLETE SOLUTION, instead I'm looking for a guidance through topics/materials which I should check to be able to solve it myself.

Done so far: I started with understanding logical gates and those seem to be pretty straight forward.

P.S.: Purpose of posting this question is to boost the speed with which I will get to the actual solution.

SOLUTION:
f(A,B,C,D) = !AB!C!D + A!C + ABC!D. (! - used for negation or NOR, ABC notations means A AND B AND C). I had three adjacent rectangles two of which were of unit cell size and one of 4 cells size (one cell was actually far away, but there's this toroidally connection property, not sure about terminology). A and B are MSD and LSD of the first number respectfully and B and C are same for second number. As for the circuit image: sorry folks my hand drawing requires strong mental stability.


texts: what are the conditions for two NFAs to be equivalent?

texts:
It's a pretty basic question, but I couldn't find an explicit answer in the book which I'm using, also when searching for it - I didn't find a reliable reference.

Correct me if I'm wrong but for two DFA's, $A , A'$ -given that  $L(A) = L(A')$ doesn't mean that the DFA's are equivalent, so what are the (sufficient and necessary) conditions under which $A$ and $A'$ are equivalent? The closest I found was a claim states that in case $\bigcup_{q\in Q} L(q) \neq \bigcup_{q'\in Q'}L(q')$ (when $L(q) = \{w\in\Sigma^* : \hat{\delta}(q_0,w) =q \})$ then $A, A'$ are not equivalent.


texts: Is this algorithm for partial ordering of sets complete and sound?

texts:
I need to build a partial order tree of sets for analysis.

Where the order is defined as A <= B <=> for all x in A, y in B, x <= y.

I realized that if I pre-sort all the maximal and minimal elements of the sets, like this:

// A [1,3]
// B [2,4]
// C [3,5]
// D [6,7]
// E [8,9]
// F [10,11]
const input = [['A', 1], ['B', 2], ['C', 3], ['A', 3], ['B', 4], ['C', 5], ['D', 6], ['D', 7], ['E', 8], ['E', 9], ['F', 10], ['F', 11]]

I can achieve it in O(n), with the following algorithm:

let i = 0
const closed = []
const opened = {}
const lists = []
for (const item of input.reverse()) {
  if (!opened[item[0]]) { // Opening the range.
    // May need to create a new list.
    if (i <= closed.length) {
      lists.push([[i - 1, closed.length], []])
      i = closed.length + 1
    }

    // Add to list.
    lists[lists.length - 1][1].push(item[0])
    opened[item[0]] = true
  } else // Closing the range.
    closed.push(item[0])
}

This is javascript and you can pretty print the result like so:

console.log(lists.map(l => `${closed.slice(l[0][0],l[0][1])}:${l[1]}`).join('\n'))
// :F
// F:E
// E:D
// D:C,B,A

Are there orders for which this might not work?


texts: Applications for boolean logic operations in zero-one integer linear programming (ILP)

texts:
It is nice to know that every boolean formula can be expressed by zero-one
integer programming by this answered question. But are there any applications?

To be more precise: Are there papers which use the existense of zero-one
integer programming for boolean operations?


texts: Intuition why $ L= \{\langle M \rangle| \ L(M)=\Sigma ^* \}\notin RE $

texts:
I know how to prove it by reduction, but I couldn't find an explanation why it is true.

$\langle M \rangle$ represents the encoding of a turing machine $M$.


texts: Equivalence from multi-tape to single-tape implies limited write space?

texts:
Suppose I have the following subroutine, to a more complex program, that uses spaces to the right of the tape:

$A$: "adds a $ at the beginning of the tape."

So we have:
$$
\begin{array}{lc}
\text{Before }: & 0101\sqcup\sqcup\sqcup\ldots\\
\text{After }A: & \$0101\sqcup\sqcup\ldots
\end{array}
$$

And it is running on a multi-tape turing machine. The equivalence theorem from Sipser book proposes we can describe any multi-tape TM with a single-tape applying the following "algorithm", append a $\#$ at every tape and then concat every tape in a single tape, and then put a dot to simulate the header of the previous machine, etc, etc.

With $a$ and $b$ being the content of other tapes, we have:
$$
a\#\dot{0}101\#b
$$
If we want to apply $A$ or another subroutine that uses more space, the "algorithm" described in Sipser is not enough, I can intuitively shift $\#b$ to the right, but how to describe it more formally for any other subroutine that uses more space in the tape? I can't figure out a more general "algorithm" to apply in this cases.


texts: Is there an efficient way to insert n items into an n^2 sized heap

texts:
I am aware of a O(n) algorithm for constructing a new heap of n items, this is better than repeatedly inserting into an empty heap which takes O(nlogn). I would like to know if there is something similar for inserting a group of n items into an existing heap. Rather than using repeated insertion, is there something more efficient?

Thanks


texts: Best pathfinding algorithm for undirected unweighted graph

texts: I have an unweighted undirected graph with every node connected with an average of two hundred other nodes (nodes are people from social network). What will be the fastest algorithm to find the shortest path from one node to another?


texts: Time complexity of Dijkstra's algorithm for sparse graph

texts:
I'm not sure I understand the answer to this question:

  Question 9.

  What is the running time of Dijkstra's algorithm in a graph that is sufficently sparse - in particular, $E=o(V^2/\log V)$, where $V$ is the number of vertices and $E$ the number of edges. Assume that we are implementing the min-priority queue with a binary min-heap. Choose the anwser the that gives the tightest correct bound.

  $O(V^2)$
  $O(V^2+E)$
  $O(E^2)$
  $O((V+E)\log V)$
  $O(V\log V)$

  Answer: 4 $O((V+E)\log V)$

As I understand it, the algorithm runs in $O((E+V) \log(V))$ with binary heap. Thus when, $E = V^2/\log(V)$, shouldn't the overall time complexity be $O(V^2)$?


texts: Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j}

texts: Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize every word to be unequal to every other word.


texts:
I came across following question:

There is a building with N floors. We have a balls of same property and have a breaking point of X floor. i.e, If ball dropped from X+1 floor then the ball will break. if ball is dropped from X or less than X then it wont break. Now design an algorithm to find X if N is given.

My Solution:

Drop the ball from N/2 floor. If ball breaks then X < N/2. Else X > N/2. Repeat this process till X is found.
but If X is N/2+1 or N/2-1 the number of steps to find X are high.

Is there a better way to Find X?


texts: Reductions among two problems related to walks of length $k$

texts:
Consider the following two problems:
A. Given a directed graph and a parameter $k$, determine if it contains a path (not necessarily simple) of length $k$.
B. Given a directed graph, two vertices $s,t$ and a parameter $k$, determine if the graph contains a path from $s$ to $t$ (not necessarily simple) of length $k$.
How can I reduce problem B to problem A?
I know that I can make a DFS tree at height $k$ with repeating vertices, however it solves the problem directly rather than by reduction.


texts: Why is it true that the relation R and its negation are not semi decidable?

texts:
An example given for a relation R where its negation and itself are not semi-decidable was:

$R(x,y)$ holds iff $y = 0$ then $R_{HALT}(x)$ holds, otherwise $y = 1$ and $R_{HALT}(x)$ does not hold.

It's stated with the assumption that the proof is trivial (which for most it probably is), but I am struggling to see why it is the case. Can anyone run me through why it is true?


texts: Proving an invariant in a recursion using mathematical induction

texts:
Given the following pseudocode for function AP(x, y: integer) which returns an integer,

function AP(x,y: integer):
    if x = 0 then return y+1
    else
         if y = 0 then return AP(x-1,1)
         else return AP(x-1, AP(x,y-1))

I need to prove, $\forall x (AP(x, y) > y)$.

I have tried solving it using mathematical induction,
Basis: $AP(0, y) = y + 1$
Inductive step: Assuming, $AP(n, y) > y$ and $y > 0$
Prove that $AP(n + 1, y) = AP(n, AP(n + 1, y - 1)) > y$

By unrolling recursion, I get relations like,
$AP(n + 1, y) > AP(n + 1, y - 1) > AP(n, 1)$,
but I am not sure how to proceed from here.


texts: Maximum and Minimum distance from query point within bounding box

texts:
I'm reading an article regarding approximating sums using KD-trees (similar to FMM).

As part of the effort I'm trying to make sense of this article , which is cited.

I'm having trouble understanding this part:

  Computing the maximum variation of weights over all points below node
  ND is easy. We know the location of xquery and we know the bounding
  hyperrectangle of the current node. A simple algorithm costing
  O(Number of tree dimensions) can compute the shortest and largest
  possible distances to any point in the node. From these two values,
  and the assumption that the weight function is non-increasing, we can
  compute the minimum and maximum possible weights wmin and wmax of any
  datapoint below node ND.

The only solution I can think of is to bound the variation (wmax-wmin) from above using the corners of the bounding box, and then computing the distance from the query point to each of the
 corners is indeed O(d), but there are 2^d corners... But this doesn't seem to be the author's intention. Could anybody point me to what I"m missing here?


texts: How is the complexity/size of a problem (for instance SAT) determined?

texts:
We say an algorithm runs in polynomial time if it is of the form $O(n^k)$ where $n$ is the size of the input, right?

So how do we judge how many inputs there are in: $(x_1 \vee x_2 \vee \overline{x_3}) \wedge (\overline{x_1} \vee \overline{x_2} \vee x_4) \wedge (x_2\vee x_3\vee x_5)$

...actually, in looking for an actual definition of an algorithm running in polynomial time, wolframAlpha says:
"An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is $O(n^k)$ for some non-negative integer $k$, where $n$ is the complexity of the input. "

So, then my question is, for my example, what is the complexity of the input? Is the complexity based on how many variables, or how many clauses?


texts: Input size of 3-SAT when analyzing complexity

texts: We know that $\text{3-SAT}$ problem is NP-complete, but I am not sure what is meant by size of input. Does this mean number of literals, or number of variables?


texts: Page fault rate while calculating effective access time

texts:
So here is a question regarding calculating effective access time (EAT).
So the question is :
suppose a system with an average page page-fault service time of 6 milliseconds and
a memory access time of 150 nanoseconds. Calculate its effective access time where
the probability of page fault is 20%.
In the course content we have been taught about these formulae:
EAT = (Page fault rate * Page fault Service Time)  + (1-p)(Main memory access time)
According to this : (0.2 * 6000000) + (0.8)(150)
= 1200120
Have I done it correctly? The page fault rate would be the probability. Isn't it! Also please tell me that do we have to consider the SI base unit of memory access time. If that is in nano second/ micro second then others will also be converted to that respective Si base unit.


texts: What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable?

texts:
Definitions:

positive CNF is a conjunctive normal form formula, where all literals are positive, i.e. the unary connective ¬ does not exist in the formula.

negative CNF is a conjunctive normal form formula, where all literals are negative, i.e. the unary connective ¬ appears next to each literal.

My question is:

Given a CNF, which is a conjunction of positive CNF and negative CNF, what is the complexity of the problem to determine that this special case of CNF is satisfiable?

Does exist polynomial time and space algorithm to solve this problem?

EDIT: Another name for "positive CNF" is "fact CNF", where all clauses are fact and another name for "negative CNF" is "goal CNF", where all clauses are goal.

... clause with no negative literals is sometimes called a fact

... clause without a positive literal is sometimes called a goal clause

Quoted from: this wikipedia documentation


texts:
We throw two coins in a row and thus get the event space $\{ZZ, WW, ZW, WZ\}$.
Each of the 4 elementary events has a probability $1/4$.
how can I construct 3 binary random variable $x_1$, $x_2$, $x_3$ about this event space, which are 2-fold independent, but not independent.


texts: Prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values

texts:
How can I prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values ?

It seems obvious to me, since an ill-conditioned problem is that in which exact input values(D) are totally different from error valuesI(D') (judging by something), thus the exact solution(G) differ much from one with error in some sense. This can be applied in case of algorithms: because if D and D' are far from each other somehow, than no one can expect for G(D*) to get closer to G*(D), where G* is the algorithm for implementing the G problem . Can you please show some more precise approach, less "in words" and more in logic ?

Thank you.


texts: How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem?

texts:
Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set $S$ of size $k$, if there exists another set that covers strictly more elements than $S$ does. Is this problem still NP-complete?

To be clearer, let's think about the Set Cover problem as an optimization problem: what is the maximum number of elements that can be covered by $k$ sets. The decision version is: are there $k$ sets that cover at least $m$ elements? (where $m$ is part of the input, and the version you were saying is simply the special case when $m=n$). Now the problem is, for $k$ given sets (as part of the input), does there exist $k$ other sets that cover strictly more elements than the $k$ given sets do.


texts: Analysis of Radix sort of $n$ $b$ bit numbers

texts:
I was reading radix sort in Introduction to Algorithms by CLRS . And it gave the following Lemma with its analysis

I understood the proof of the Lemma but confused on the part where they try to minimize $\left( b / r\right) \left( n+2^{r}\right)$ .

While choosing $r$ the first case was $b < \left\lfloor \ln \right\rfloor$ . If we ignore the floor function we get $b < \ln \left( n\right)$.

Now how is this possible? Because when

$b < \ln \left( n\right) \\\Rightarrow 2^{b} < n\\\Rightarrow n>2^{b} $

But the maximum number of $b$ bit numbers are $2^{b}$ therefore $\max \left( n\right) =2^{b}$ this seems a contradiction .

Therefore $n\leq 2^{b}\\\Rightarrow \ln \left( n\right) \leq b $

Also following this it seems that $b=O\left( \ln \left( n\right) \right)$ doesn’t exactly seem right since we are getting $b\geq \ln \left( n\right)$

Can someone explain this ?

P.S. In this whole text and question $\ln \left( n\right)$ means $\log _{2}n$


texts: Shortcut for "in the worst-case, with high probability"?

texts:
I am writing a paper in which the worst-case analysis of a certain randomized algorithm is correct with probability $1-1/n$ (where $n$ is the size of the problem). I find myself writing, time after time, the following sentence:

  "With high probability, in the worst case, the performance of phase A is at most X".

The worst-case is with relation to the inputs; the high probability is with relation to the randomization of the algorithm. I.e, there is an adversary that choose the worst possible inputs, but then I do a lottery on which the adversary has no effect.

Since there are many phases, this sentence appears many times throughout the paper and it looks cumbersome.  I tried to make it shorter by writing:

  "In the worst case (WHP), the performance of phase A is at most... "

This still looks cumbersome... Is there a more common way to express this meaning?


texts:
In lots of textbooks and papers, authors often state: compiler emits ...

I want to know why they prefer to use emit? (not return, not produce)

Does this have anything to do with the emitter of a compiler?

thanks


texts: What is the simplest written language to work on in handwriting recognition?

texts:
Handwriting recognition is an important but very complicated domain of Computer Sciences. Computers nowadays do a quite fair job even if there is room for improvement in the future.

I am wondering if the result is language-dependant:
1) Are there languages that are more easily analyzed by handwriting recognition programs? Why?
2) Quality of recognition depends probably on  individuals' handwriting. If there are difference of quality of recognitions between language, is this difference significantly larger or smaller than the individual variation?

Concerning the first question, my intuition is that best performances are obtained with languages with a lot of writers like English (more resources to analyze, more motivation, more money,...) or with a particular alphabet/language structure (Korean and its simple alphabet ㄱㄴㄷㄹㅁㅂㅅㅏㅓㅜ seems to be a good candidate).

Edit: I am not sure if the relevant context is language or alphabet. As Tom pointed out in comments, different languages with the same alphabet may behave differently in language recognization. For example, I think that a basic strategy when some letters of a word are identified is comparison with a dictionary. German, with its possibility of creating new words by concatenation, makes this strategy (slightly?) less useful than English. Language structure like genders may also help.

My motivation is to understand some ideas of OCR, so at the end of the day, I'll accept a good answer, even if it is focused about alphabet rather than language.


texts: How to understand the analysis of expected running time of randomized quick-sort in this paper?

texts:
I'm learning the book named Data Structures & Algorithms in Python.

On Page 557-558, there is a proof of the expected running time of randomized qucick-sort. I have some problems confusing me some days. I will note them in bold form.

Here's orginal text:

  Proposition 12.3: The expected running time of randomized quick-sort on a sequence $S$ of size $n$ is $O(n \log n)$.

  Justification: We assume two elements of $S$ can be compared in $O(1)$ time. Consider a single recursive call of randomized quick-sort, and let $n$ denote the size of the input for this call. Say that this call is “good” if the pivot chosen is such that subsequences $L$ and $G$ have size at least $\frac{n}{4}$ and at most $\frac{3n}{4}$ each; otherwise, a call is “bad.”

  Now, consider the implications of our choosing a pivot uniformly at random. Note that there are $\frac{n}{2}$ possible good choices for the pivot for any given call of size n of the randomized quick-sort algorithm. Thus, the probability that any call is good is $\frac{1}{2}$. Note further that a good call will at least partition a list of size $n$ into two lists of size $\frac{3n}{4}$ and $\frac{n}{4}$, and a bad call could be as bad as producing a single call of size $n−1$.

  Now consider a recursion trace for randomized quick-sort. This trace deﬁnes a binary tree, $T$, such that each node in $T$ corresponds to a different recursive call on a subproblem of sorting a portion of the original list.

  Say that a node $v$ in $T$ is in size group $i$ if the size of $v$’s subproblem is greater than $\left(\frac{3}{4}\right)^{i+1}n$ and at most $\left(\frac{3}{4}\right)^in$ Let us analyze the expected time spent working on all the subproblems for nodes in size group $i$. By the linearity of expectation (Proposition A.19), the expected time for working on all these subproblems is the sum of the expected times for each one. Some of these nodes correspond to good calls and some correspond to bad calls. But note that, since a good call occurs with probability $\frac{1}{2}$, the expected number of consecutive calls we have to make before getting a good call is $2$.

  ⓵ Moreover, notice that as soon as we have a good call for a node in size group $i$, its children will be in size groups higher than $i$.

  ⓶ Thus, for any element $x$ from the input list, the expected number of nodes in size group $i$ containing $x$ in their subproblems is $2$. In other words, the expected total size of all the subproblems in size group $i$ is $2n$.

  Since the nonrecursive work we perform for any subproblem is proportional to its size, this implies that the total expected time spent processing subproblems for nodes in size group $i$ is $O(n)$.

  The number of size groups is $\log_{\frac{4}{3}}n$, since repeatedly multiplying by $\frac{3}{4}$ is the same as repeatedly dividing by $\frac{4}{3}$. That is, the number of size groups is $O(\log n)$. Therefore, the total expected running time of randomized quick-sort is $O(n\log n)$. (See Figure 11.13.)

Here are my problems:

According this sentence:

  ⓵ Moreover, notice that as soon as we have a good call for a node in size group $i$, its children will be in size groups higher than $i$.

Which size group does node $s(a)$ belong to? And why?

  ⓶ Thus, for any element $x$ from the input list, the expected number of nodes in size group $i$ containing $x$ in their subproblems is $2$. In other words, the expected total size of all the subproblems in size group $i$ is $2n$.

I can't really understand the meaning of this sentence.


texts: What is a difference between cross-lingual IR and multi-lingual IR?

texts: In papers usually Cross-Lingual Information Retrieval (CLIR) and Multi-Lingual Information Retrieval (MLIR) use equivalently or distinctly. I want to know is there any difference between these two terms?


texts:
We define $\mathbf P$ as the set of problems solvable in polynomial time. We define $\mathbf{NP}$ as the set of problems with a verifier $ \in \mathbf P$.

Is there a name for problems whose verifiers are $\in \mathbf {NP}$ (e.g., $\mathbf{N(NP)}$)? I can't see this being a very useful complexity class, but, for example we have that $\mathbf{NP} \neq \mathbf{N(NP)} \implies \mathbf{P} \neq \mathbf{NP}$, so it might be an area of research for that reason alone.


texts: Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph

texts:
I'm learning Dynamic Programming (By myself) and in the textbook there is this question:

Given two undirected graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ over the same set of Vertices $V$ and a weight function $w: E_1 \cup E_2 \rightarrow \mathbb{R}$, let $P = \left\{e_1, e_2, ..., e_n \right\}$ be a path in $(V, E_1 \cup E_2)$.
We sat that P is alternating if for any $1 \leq i < n$ at least one of the following two conditions hold:

$e_i \in E_1, e_{i+1} \in E_2$
$e_i \in E_2, e_{i+1} \in E_1$

Write a DP algorithm that given $G_1, G_2$, returns the weights of the shortest alternating paths between all pairs of vertices in $V$

OK so I sat on this question for a long time but I can't seem to figure out how to do solve it. Since this is a shortest path between all pairs I tried to think of a solution which uses Floyd-Warshall algorithm, but I can't figure out how to factor in the addition of the alternating path.
Every solution I think of fails when inserting special Edge Cases.
Can anyone give a hint as to how to proceed?


texts:
I have a list of patterns, and I need to find the pattern that matches an input string the most. I.e.:

Patterns:

[
    'AB1XXX',
    'AB2XXX',
    'ABXXXX-0080',
    'BC1XXX',
    'BC15XX'
]

The X character in the patterns is reserved as the wildcard or don't care character. It can be any single alphanumeric character.

I then get an input, i.e.: AB1100. In this case I expect the pattern AB1XXX to be the best match.
However, if I get an input AB1100-0080 I expect ABXXXX-0080 to be the best match for the given input.

I currently use a Trie to find the matching pattern, but it doesn't really work for the given example as it either can't find a match once it gets to -0080.

Best match can be seen as "shortest Levenshtein distance with the least amount of X characters used".

Is there a known algorithm I could implement or should I stick to implementing a Levenshtein distance algorithm?


texts: Does proofs are programs apply to any functional program?

texts: Does Curry howard correspondence, apply to all Functional Program, e.g. in Haskell. i.e. Is it possible to write Equivalent Haskell programs, to COQ proofs?


texts: Graph with two classes of nodes A and B: densest subgraph with same node classes cardinality

texts:
I'm searching (without results) a problem that can be reduced to finding the densest subgraph with the same cardinality between two classes of nodes.

Consider a graph with nodes of class A and nodes of class $B$ (not bipartite and $|A|$ it is not necessarily the same as $|B|$).
The problem is to find the densest subgraph that respects the costraint  $|A\cap D|=|B\cap D|$ where $D$ is the set of the nodes of the desired subgraph.

Before asking I tried with the partition problem, but the transformation between partition in this problem is pseudo polynomial and not polynomial (for each number N in the input set i build a clique of N nodes so the transformation depends on the value of the numbers in the set and this is not ok).

Thanks for the help :)

Edit: the definition of densest is the subgraph that maximizes #edges/#nodes. This subgraph can be computed in polynomial time with an algorithm by Goldberg.


texts:
I know this question is trivial. But I am looking for a concise formal definition of $\alpha$-approximation.

Is it correct to say that "An algorithm is an $\alpha$-approximation to problem $X$, if for any instance of problem $X$ the solution returned by this algorithm is within a factor $\alpha$ of the optimal solution"?

Any correction on the above definition is welcomed.


texts:
The atomic fetch-and-set x,y instruction unconditionally sets the memory location x to 1 and fetches the old value of x in y without allowing any intervening access to the memory location x. Consider the following implementation of P and V functions on a binary semaphore S.

   void P (binary_semaphore *s) {
        unsigned y;
        unsigned *x = &(s->value);
        do {
            fetch-and-set x, y;
        } while (y);
    }

    void V (binary_semaphore *s) {
        S->value = 0;
    }

Which one of the following is true?

The implementation may not work if context switching is disabled in P()
Instead of using fetch-and–set, a pair of normal load/store can be used
The implementation of V is wrong
The code does not implement a binary semaphore

Option 1 is correct. I am unable to understand the reason for it. Please explain.


texts: Finding the point with smallest x-ordinate between two given y-ordinates

texts: Given a set of points P=p1,p2,..pn in R2 in where pi=(xi,yi),finding the point with smallest x-ordinate having y-ordinates between y1 and y2, where y1 and y2 are given as inputs. I can compare the point with other points which gives me an O(n) time algorithm ? Can this be improved any further ?


texts: Regular expressions, is it always true that (r U s)* = r* U s* U (rs)*?

texts:
If r and s are any two regular expressions, then (r ∪ s)* = r* ∪ s* ∪
  (rs)*.

I think this is not true. And I believe this would always be true :

  (r ∪ s)* = r* ∪ s*

I wanted to clarify this because of (rs)*. What do you think the right hand side would be if r* ∪ s* ∪ (rs)* ?


texts: finding the overhead and distance of an unknown code based on message making algorithm

texts:
for an information word M with m bits that is coded as following:

M is coded into a word A using an unknown code that allows detection of not more than one error.
the code word is the word obtained by a concatenation of A to itself. so A becomes AA and etc..

1)is it possible to know the overhead in the given code?

2)is it possible to know the distance of the code?

EDIT: I don't know how to solve it and i've tried several times and apparently i am going to the wrong directions. please solve it if you can so i can learn the correct way of approaching and solving this kind of questions.

thank you very much

my attempt:

after thinking on it again and rereading the text, i began to realize(hopefully i am right now) that the question is about parity bit and not hamming. so if it can detect not more than one error, there's a parity bit, i think. based on that thought i tried to solve it:

1)I began to realize it's not about hamming code. if we can only detect not more than one error, then it's about the parity bit. so i think that if we add a bit to each byte of message, then the overhead will be 9 bytes total. so it can be calculated, i think.

2)since this sub problem is about the concatenation of A to itself, then like @YuvalFilmus said, the minimal distance should be twice now.

is it correct now? would really appreciate your comments and help.

thank you very much


texts: Using a proof-of-work system to discourage piracy or encourage donations

texts:
Background

A proof-of-work system allows one peer to prove to another peer that a certain amount of computational effort was performed.
In a network setting this can be used to throttle peer requests without needing to keep a precise track on the identity of the peers or prior events.
The most well known use of proof-of-work is to throttle spam throughput in an email network*.

Some proof-of-work systems allow certain roles on the network (say, a mailing list) to calculate the proof of work much faster by using a secret "short-cut" - typically a pre-calculated trapdoor or a private key depending on the proof-of-work system.

Hypothesis

Any algorithm or a certain class of algorithms can be converted into a proof-of-work version of that algorithm. That is: A deliberately inefficient and incompressible algorithm.
Such converted proof-of-work algorithms can support proof-of-work shortcuts.
Such converted proof-of-work algorithms can not be converted back to the original algorithm without considerable computational power; if at all.

Extrapolation

If the hypothesis holds, then selected business logic of an application - specifically that which is unique or value-added by that application vs existing applications - could be converted to proof-of-work equivalents.

End-users could then be provided such an application; which will run slowly either generally or for certain premium features. The development team however, possesses a secret PoW shortcut and set up a subscription, donation or advertising(!)-based service - an SaaS - for solving the proof-of-work bottleneck for the end-user. The end-user can now choose to run the application slower without the SaaS or faster with the SaaS.

This SaaS needs to process considerably less client-side business logic than a general cloud solution (e.g. Diablo 3 style SaaS); as the goal is the speed of execution rather than no execution - and the SaaS proof-of-work speed ratio is tailored accordingly.

This is especially relevant for software projects supported by charity as the developers do want the software available to anyone but can encourage donations without needing a separate fairly easy to pirate Freemium edition. The Tragedy of the Commons (freeloading) could be discouraged to a fair extent without guilt-tripping or rat poisoning, by adjusting the proof-of-work cost relative the value of the application or service.

  Example 1: A commercial stock market estimation tool licensed per
  month. If the user forgoes paying for a subscription, the estimation
  occurs at 1% the normal rate.

  Example 2: A free Triple A co-op video game runs twice fast if the
  user donates some money once a year.

In either example the user must decide between accepting the default speed; spending money on a faster computer/cloud services; or contributing to the upkeep of the product.

Question

Does the hypothesis hold and has anyone attempted to explore or implement this hypothesis?

Any example of an open source library or application that attempts to implement the hypothesis qualifies as a sufficient answer (from my perspective); as I could dissect the code.

 * Which has a variety of issues for the Digital Divide, but that's another story


texts: How did 'Isabelle' (the theorem prover) get its name?

texts: The title says it all, but I'm curious because it isn't obvious how a theorem prover came to be named 'Isabelle'. Was it named for a person? I couldn't find out by some Google searches.


texts: What is a range of an attribute in data mining?

texts:
In my data mining course, we are working with a data set. I have to identity the ranges of each attribute. I am given the set of data for all 150 points and i am given the visualization (charts) of all attributes. However I do not know how to use that set of data or the charts to find the ranges of each attribute. I do not know what is meant by range either.

I'm working on the data set for Iris plants and I have three classes of the flower.


texts: Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

texts:
There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement).

On average, how many of these random comparisons will you need to be able to sort the list?

Some follow-up questions:

What does the distribution for the number of comparisons needed look like?
What is the answer if you use $k$-ary comparisons instead of binary ones.
What is the answer if the comparisons are made without replacement (i.e. you won't get the same comparison twice)?
Given a set of comparisons, how can one check if the list is sort-able? I'm almost certain the answer is to construct a DAG and topological sort, but I just want to confirm.

An exact-ish answer would be nice, but a big $O$ answer is fine too, I suppose.


texts:
I'm reading The Algorithm Design Manual and I stumbled upon this problem.
I can't really get my head around this, I don't even know how the number of multiplications could differ, what I mean is that there is no polynomial that would make this algorithm perform poorly.
I also have no idea how this could get improved, every operation seems necessary to me.
Any help would be much appreciated.


texts: Is $\{ w \in L : wx \in L, \textrm{for some } x \neq \epsilon\}$ a CFG language if $L$ is CFG?

texts: Let $L$ be CFG. Is $\{ w \in L : wx \in L, \textrm{for some } x \neq \epsilon\}$ also CFG?


texts: Problem with formulating LP problem using binary variables

texts:
I have a problem with a task shown below.

I have I am supposed to use big M method, but I don't know how to estimate/compute the minimal value of it and how to implement it into the equations. Any help would be much appreciated:

  Use binary variables to algebraically express the set $Y$ defined as the set of all those $(x_1,x_2,x_3,x_4)\in X$ that meet at least one of the following three constraints:
  \begin{align}
x_1 + 2x_2 + x_3 + 2x_4 &\leq 50,\\
3x_1 - x_2+x_4 &\leq 100,\\
3x_1-x_2+x_3 &\geq 20.
\end{align}


texts:
I am still trying to get my head around what is valid CNF and how distribution works, I am not even sure if the examples I have tried to convert are correct for one, but I am also unsure of the rule for distribution and when I have looked at other posts here it seems so complicated and the actual rule does not seem to me to be obvious.
I think the correct process is:

Elimate Bi-Directionals
Eliminate Implications
Apply De Morgans Law
Apply Distributive Law

Clause One
A V B => C
-(A V B) V C -- Remove implication
(-A ^ -B) V C -- De Morgans Law
(-A V C) ^ (-B V C) -- Is this right? I am unsure of exactly how to distribute the or.

Clause Two
A ^ B => C
-(A ^ B) V C -- Eliminate Implication
(-A V -B) V C -- Is this now valid CNF or is there something more to do?

Clause Three
-A ^ -B => C
(A ^ B) V C -- Elimate Implication - Is this correct for a negated expression?
(A V C) ^ (B V C) -- Distribute OR - Is this correct?

I am not able to access the set of maths symbols for some reason so have used the notation in my course book.
I am currently taking a self taught course and have an exam in two weeks and I know there will conversion to CNF involved so I am trying to make sure I understand the steps now but I am still not entirely sure what is valid CNF.
The course material states it is a conjunction of disjunctions which I get, but then it seems to imply that: A V B V C V ..n is valid CNF?


texts: Are parser combinators equivalent to scannerless parsing?

texts:
From what I can see, parser combinators are equivalent to scannerless parsing.  I do not see this stated in implementations of scannerless parsing page, nor in the parsing combinators page, neither in the google generally. But, it seems they are. I didn't code the low-level rules separately or using different syntax than higher order ones.

Am I correct that parser combinators are simply scannerless parsing?  Or is there a difference that I am overlooking?


texts: Some questions regarding decidability and semi-decidability of $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$

texts:
I have found two interesting questions regarding the quotient of languages, described as:
$A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$
The first one is:

Let $A$ and $B$ be regular languages, prove that $A/B$ is decidable

By using the proof from this other question, it can be proved that $A/B$ is regular if $A$ is regular too.
Then, since any regular language is decidable, $A/B$ will be regular (and decidable) too.
The second one is:

Let $A$ and $B$ be decidable languages, prove that $A/B$ is semi-decidable

I have no idea on how to prove this one, I assume that it's somehow related to $A$ and $B$ being able to stop for any string, whether it's accepted or rejected, but since I don't know whether $A$ is regular or not, I don't know what to do.


texts: Proof of greedy algorithm to minimize cost of job assignment over unlimited number of machines

texts:
I'm trying to prove a greedy algorithm works for a specific problem:

  You have $n$ jobs and some finite number of machines. (The number of machines doesn't matter; we assume you have enough to run all the jobs.) Each job $j$ has a size $s_j$. Each machine $i$ has a constant associated with its speed, $p_i$. The cost of running job $j$ on machine $i$ is simply $s_j \cdot p_i$. We can only assign at most $k$ jobs to one machine. How should the jobs be assigned to minimize the sum of the costs on all machines (that have been given jobs)? I.e., minimize $\sum_{i,j} s_j \cdot p_i$ over all assignments of a job $j$ to a machine $i$. (Note that there is no penalty for assigning lots of jobs to a specific machine. We aren't trying to balance out the number of jobs assigned to each machine.)

The simple greedy algorithm is to first sort the jobs from greatest size to least size, and the machines from fastest (least $p_i$ in this case) to slowest, and then assign the $k$ largest jobs to the fastest machine, second $k$ largest jobs to the second fastest machine, etc. (So in other words, pair off large $s_j$ with small $p_i$ and vice versa.)

I'm now trying to prove this algorithm is correct. My first try was to show that the greedy algorithm stays ahead. I reasoned that the optimal algorithm must also use the fastest machines (or else it is trivial to show it isn't actually optimal), and therefore if we look at the machines from fastest to slowest, we can consider the first job for which they differ. But then it isn't necessarily true that the greedy algorithm is doing better at this point as the optimal algorithm could minimize cost for that specific slot by putting in a smaller job (even though it actually hurts it later).

I also tried doing an overall induction on the number of jobs. Say we show it it optimal for $n$ jobs. Can we show it is optimal for $n+1$ jobs given the same options for machines? Again, it isn't clear how to make this argument since we can't just slide in job $n+1$; maybe the optimal assignment suddenly follows a wildly different pattern.

Thanks for the help!


texts: Hungarian Assignment Algorithm Implementation

texts:
I want to implement the "vertex similarity" algorithm described in the paper Graph Isomorphism Detection Using Vertex Similarity Measure. The algorithm is as follows:

S(0) <- appropriately sized matrix filled with 1's
for k=1 to 10 do:
    S(k) = Y*S(k-1)*X^T + Y^T*S(k-1)*X
    k++
Apply Hungarian assignment algorithm on similarity matrix S.

where X^T means the transpose of the matrix X.

Basically, given two graphs G1, G2 (not necessarily the same # of vertices), create their adjacency matrices X and Y. Then, do this iterative process 10 times, and then apply the Hungarian assignment algorithm. The result would be a similarity matrix where entry (i,j) represents a real number between 0 and 1 that gives how "similar" vertex i is of G1 to vertex j of G2.

My question is: how would this algorithm be implemented? I looked up the algorithm on Wikipedia, and the explanation seems as though all entries in S would be integers, but what is expected is real numbers between 0 and 1.


texts:
I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum of the weights of the colors used. If we have for example a path A->B->C where A and C are red colored and B is blue colored, its length should count the weight of red only once (and the weight of the blue node)! I'm struggling to find an (efficient) algorithm that can do this. Dijkstra's algorithm or any greedy algorithm cannot work, because they require that a local optimum must be also a global optimum. Here, this is not the case because the weight of a vertex depends on the path to it. You could add vertecies for each combination of colors but this would add exponantially many vertecies.
It would be enough for me to find such an algorithm for DAGs.
Thank you very much for your help!


texts: What does $\text{dom}(\Gamma)$ mean in the context of an inference rule?

texts:
In the wikipedia page on pure type systems, it gives the following inference rule:

$\frac{\Gamma \vdash A : s \quad x \notin \text{dom}(\Gamma)}{\Gamma, x : A \vdash x : A }\quad \text{(start)}$

What does $\text{dom}(\Gamma)$ mean here? These are string rewriting systems, so $\Gamma$ is supposed to be a string of symbols, a purely syntactic object. I'm not sure what a "domain of a string" is.


texts: What is Turing's main argument in "Computing Machinery and Intelligence"?

texts:
I read Alan Turing's paper "Computing Machinery and Intelligence" a few times and it isn't clear what exactly is he arguing for. He proposes the imitation game, but doesn't form a concrete conclusion.

It seems like the current consensus is that passing the Turing test doesn't signify human-like intelligence or thinking. It is merely a metric that's easy to measure. Human-like intelligence must necessarily pass the Turing test, but the reverse isn't true.

My understanding is that the Turing test is like the digit recognition test in computer vision. It is an useful metric, but getting 100% on the digit recognition doesn't mean that a computer has human-like vision.

Is Turing arguing that it's possible for a machine to pass the Turing test? Isn't it easily conceivable that a machine could contain every possible question and every possible response? In which case, it could simply look up the appropriate response for any given question, without having to "think" at all. This machine would easily pass the Turing test.
Is Turing arguing that passing the Turing test signifies intelligence or thinking? My example above illustrates a machine that could pass the Turing test, but we wouldn't consider it intelligent or thinking.
Is Turing arguing that the passing the Turing test is merely an arbitrary metric that is easily measurable, since intelligence is too hard to measure? In this case, why is he responding to the objections? E.g. he brings up a theological objection, but that's not relevant if the Turing test is merely measuring Turing's arbitrary metric.


texts: How to simulate a non-deterministic PDA with a turing machine?


texts: Chomsky hierarchy for finite state transducers

texts: In this question in the first answer someone mentions a "special transduction hierarchy". I cannot find anywhere anything about it. Could someone point me to resources on this topic?


texts:
There is question in one of my exercise but I couldn't prove or disprove anything about it.
This is language $L$ which is introduced with grammar:
$$S \to 0S1 | 1S0 | AA$$
$$A \to 0A | \lambda|A1$$

My explanation and work:
I know that we can prove with pumping lemma that a language is not regular.
I know that if $L_1 \subset L_2$ and $L_2$ is regular, then $L_1$ maybe regular or not so in this example, $0^n1^n \subset L$ but we can't say that this language is not regular.
next, I think that $L$ is regular because grammar $A$ can produce anything but after a little try, I found that $A = 0^*1^*$ and $110101$ is not a part of language, so it can not be $(1 | 0)^*$ which is regular.
at this point, I don't know is it regular, or not. $S$ grammar can produce strings which has equal 0 and 1 at the start and end, but maybe $A$ grammar can produce something that make language regular.
Is it possible to help me? can you give me any idea?

Idea (from comment):

if we say that $L$ is regular, then we get intersection of it and $0^*1010101^*$.
for accept a string in this language, there is two state.

1) not equal number of $0$ and $1$ at the start and end of string:
suppose number is form of $0^n1010101^{n+k}$ for $k \gt 0$ (we can prove same for $0$). use $S \to 0S1$ to create $0$ at the start and $1$ end, after some level we get to $0^nS1^n$ but we can't use any $S \to 0S1$ or $S \to 1S0$ anymore so we must use $S \to AA$ and $A = 0^*1^*$ and we can't match string. we couldn't construct it if we start with $S \to AA$.
so $L$ can't produce this kind of strings.

2) equal number of $0$ and $1$ at the start and end of string:
now our string is form of $0^n1010101^n$ and we can construct it with only $S \to 0S1|1S0$.

so intersection of $L$ and $0^*1010101^*$ is $0^n1010101^n$ which is easy to prove that is not regular. so our hypothesis is not correct and $L$ is not regular.

Thanks for idea. Is it true?


texts: Is everything in CS either a numeric method or a symbolic method?

texts: Or maybe also a combination of the two, but not something else, whether numeric, nor symbolic. Do they cover the whole field?


texts: What does it mean to say that a language is "effectively closed" under an operation?

texts:
I've been reading some formal language theory papers, and I've come across a term that I don't understand.

The paper will often refer to a set being "effectively closed under intersection" or other operations. What does "effectively" mean here? How does this differ from normal closure?

For reference, the paper I'm seeing these in is:

M. Daley and I. McQuillan. Formal modelling of viral gene compression. International Journal of Foundations of Computer Science, 16(3):453–469, 2005.


texts: I hope you can help me right now, I am working on lexical analyzer for C language, I am bit confuse bout the regular expression of C style comments. a regex which can handle both single and multiline comments.


texts:
1)Is it possible for a full adder to add three e.g 4 bit numbers? I mean I know the full adder has 3 inputs and two outputs but the second bit of C comes from the previous block (as shown in the image below).I mean C1 comes from the frist block and I dont provide it. And this mean I can only choose the first bit of C0. So it does not add 3 integers, right?

2)Is it possible to get the sum of k n-bit integers with full adder circuit?

Thanks in advance!


texts: Problem of finding pairs of elements that co-occur in some number of sets

texts:
I have a fairly general problem and I wonder if it has a name. The problem statement, as best I can put it, is the following:

  Let $I=\{i_1,i_2,...,i_n\}$ be a set of items. Let $C=\{C_1,C_2,...,C_m\}$ be a set of containers. Each container is unique and contains a set of items from $I$. Let $C_{a,b} \subseteq C$ be the set of containers that contain both $i_a$ and $i_b$. Find all $(i_a, i_b)$ pairs where $\left\vert{C_{a,b}}\right\vert \geq k$ for a given $k \in \mathbb{N}$.

If the items are people and the containers are times and places, then we are asking which people met at least $k$ times. If the items are groceries and the containers are shopping carts, then the problem is a variation of association rule learning. If the items are words and the containers are documents, then we are looking for a co-occurrence network.


texts:
global volatile RingBuffer queue;
global Lock queueLock;
global CV queueEmptyCV;
global CV queueFullCV;

public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.
        queueLock.acquire();

        while (queue.isFull()) { //####
            wait(queueLock, queueFullCV);
        }
        queue.enqueue(myTask);
        signal(queueEmptyCV); -- OR -- notifyAll(queueEmptyCV);

        queueLock.release();
    }
}

public method consumer() {
    while (true) {
        queueLock.acquire();

        while (queue.isEmpty()) {
            wait(queueLock, queueEmptyCV);
        }
        myTask = queue.dequeue();
        signal(queueFullCV); -- OR -- notifyAll(queueFullCV); //###

        queueLock.release();
        doStuff(myTask); // Go off and do something with the task.
    }
}

This is from https://en.wikipedia.org/wiki/Monitor_(synchronization).
I have tried a lot but I cannot understand that when notifyAll(queueFullCV) is called at //### why is there not a race condition in while loop of //####.
I can easily see many treads taking off and then, since while (queue.isFull()) is false at that instant, go and queue.enqueue(myTask) more than capacity.
//OR//
Can only one tread at a time acquire the queueLock, and after one queue.enqueue(myTask), when the other's turn comes while (queue.isFull()) is full and then go back to sleep again?
In that case, what is the need for notifyAll(queueFullCV) when only one tread would get the queueLock?


texts:
I was looking at the following proof for balanced network max flow (A flow network is a “balanced network” if for every v∈V- {s,t} it holds that $c_i(in) (v)=c_o(out) (v)$.) and I was wondering, is there any way to improve it if we knew the in and out degree? for example if in-degree(s)=out-degree(t)=0
The article in full


texts: Rice's theorem applicable to the following language?

texts:
Let $L= \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \} $
be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable.

I've heard that I can't use Rice's theorem to proof its undecidability.

But why? I can construct a set $S = \{f_M \mid f_M(\langle M \rangle)\in \{0,1\}\}$.

It's clear that $S$ is not empty and $S$ contains not every TM.


texts: Polynomial time problems with provably high degree time complexity?

texts: For any integer $k$, does there exist a decision problem in $\textbf P$ that can be proven to require $\Omega(n^k)$ steps?


texts: Difference between First Order Logic and Predicate Calculus

texts: I see the two used interchangeably. Is one the subset of the other or are they both the same thing?


texts: Permutation of multiple groups of different sizes

texts:
While working on my research for my master thesis I have stumbled upon the following problem:

Given $N$ groups of different sizes, create all the possible combinations $p$ such that:
 $p = \{e_{0,j_0},e_{1,j_1},...,e_{N,j_k}\}$ for all $e_{i,j}$.

where $i$ stands for the index of the group and $j$ stands for the index of the element of group $n_j$.

For example: given $\{ 1,2,3\}$ and $\{ a,b,c,d\}$
the answer would be :

$\{ 1,a\}$, $\{ 2,a\}$,$\{ 3,a\}$

$\{ 1,b\}$, $\{ 2,b\}$,$\{ 3,b\}$

$\{ 1,c\}$, $\{ 2,c\}$,$\{ 3,c\}$

$\{ 1,d\}$, $\{ 2,d\}$,$\{ 3,d\}$

The way I solve it is by using an odometer counter, where each digit is of base $size(n_i)$, and I generate all the combinations by simply increasing the odometer until it resets to 0.

Given the previous example, the odometer would be composed of two digits, $(d_0,d_1)$ where $d_0$ would be of base $3$ and $d_1$ would be of base $4$ and the enumeration of all the group would look like :

$(0,0)$,$(1,0)$,$(2,0)$

$(0,1)$,$(1,1)$,$(2,1)$
.
.
.
etc

The problem I have is that the run time of my implementation is not fast enough given a large number of groups. It works fine for 16 groups but starts to really slow down for 32 groups.

Before I go into optimizing my implementation, I wanted to know if there was a theoretical solution that is more efficient than the one I am currently using.


texts: Question on the decidable of Turing Machine

texts:
I am a bit confused about using the subset of the turning machine to prove the desirability of the turning machine.

If I have a Turing Machine M and we have already know M has a single halting state. If we already the machine takes a string was the input and reaches to the state q0, is it possible to prove that M is decidable by considering constructing a new Turing Machine that halts on q0?

Thanks a lot!


texts: Conditional Kolmogorov compexity of string concatenation

texts: In what follows $K(x|y)$ is conditional Kolmogorov complexity, $xx$ is $x$ concatenated with itself. It appears to me that $K(xx|yy)=K(xx)$ should be true for infinitely many strings $x$ and $y$. In fact, it seems this should be true "generically" (in some appropriate sense). How hard is this to show (if true)?


texts: Prove that two vertices are in the same connected component of G if a vertex or his decedent has a step ancestor

texts:
Given the forest $G_\pi$ of a DFS run on an undirected graph $G=(V,E)$ and a simple path  from a root to a descendant $u_0 \rightarrow ...\rightarrow u_k$.
Define $w$ as a step ancestor of $v$ if there is a back-edge from $v$ to $w$.
Mark $G' =(V, E \backslash\{u_k-1,u_k\})$.
Prove that $u_0$ and $u_k$ are in the same connected component of $G'$ if the vertex $u_k$ or his decedent in the tree in $G_\pi$ has a step ancestor $u_i, i\in\{0,...,k-1\}$.
I know that if $u_k$ and $u_0$ are in the same connected component there is a path from $u_0$ to $u_k$ so there is a vertex $v$ such that the edge $(v,u_k)$ is in $G'$ which means there where a circle in the graph and therefore a back-edge on the DFS run.
How can I show that this vertex must be from $u_k$ (this part is easy) or from his decedent in the tree in $G_\pi$ and nothing else (this is the part I'm having some trouble with)?
Thanks:)


texts: Can a petri net fire only one transition at a single moment?

texts: After reading several articles about petri nets, I am confused on how firing works. Can Petri net system fire only one transition out of all active (fire-able transitions) at a single moment? Or are multiple transitions allowed to fire at a single moment?


texts: Time constructible function T in equivalence of Turing Machines

texts:
I'm reading Computational Complexity by Arora and Barak and I had a doubt regarding a statement made about the equivalence of Turing machines:

For every $f\colon \{0, 1\}^∗ → \{0, 1\}$ and time-constructible $T\colon \mathbb N → \mathbb N$, if $f$ is computable in time $T (n)$
by a Turing machine $M$ using alphabet $\Gamma$ then it is computable in time $4\log|\Gamma|T (n)$ by a Turing machine $\tilde{M}$ using the
alphabet $\{0, 1, \square, B\}$.

Specifically, what if any role $T$ being time constructible has here?
The proof (sketch) encodes $\Gamma$ in binary, and uses a larger register to simulate $M$'s transition function, and also a counter. But I don't think $T$ being time constructible comes into play. Could someone confirm or tell me if I'm missing something?


texts: What would be the classification of R according to paradigms?

texts:
I would like to know in which classification is the R programming language. It has elements of the imperative paradigm and object oriented paradigm (some things like that even a number is an object and they can be freely mixed). I am not quite sure if it has functional programming characteristics. So it can be considered a scripting language?

What would be its classification in one of the paradigms?

R can do tasks in batches so it can be considered also a scripting language, is that so?


texts: How to reduce the cost of search based on previous BFS?

texts:
I got an unweighted, undirected graph, with $N$ vertices, where each vertex has degree $K$. In my case its a grid with dynamic obstacles.

My goal is to output a map, based on given location on the grid, with the shortest path to all  the cells on the grid, some thing like this:

4 3 2 3
3 2 1 2
4 x x 3
5 6 5 4

  The starting position is at node with the weight of 1. X represent the
  obstacles.

I achieve this goal using Breadth-first-search. My question is how can I reduce the cost of the next search if:
Only my location on the grid is changed, and/or,
if only the location of the obstacles is changes and/or
if both my location and the location of the obstacles is changed.

As for now I perform full recalculation in all those cases.


texts:
The syntax of dice notation follows the following grammar:

$$ Roll \rightarrow Dice | Dice'x'Int | More \quad Mod \quad More $$
$$ Dice \rightarrow Int_{1}'d'Int_2$$
$$ Mod \rightarrow '+'|'-'$$
$$ More \rightarrow Int | Roll$$
$$ Int \rightarrow <integer>$$

Give a leftmost derivation for the sample string:
$3d8 + 2d4x3 + 1d12 + 567$

I was able to parse the two first operands $3d8 + 2d4x3$ but I couldn't find a reasonable derivation for the rest.

My solution is like:

E -> More Mod More
E -> Roll Mod More
E -> Dice Mod More
E -> Int1’d’Int2 Mod More
E -> <integer>’d’Int2 Mod More
...
...
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + More Mod More
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + Roll Mod More
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + Dice Mod More
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + Int1’d’Int2 Mod More

I was thinking that the given string is not a valid string for this grammar.

Does any have any idea for this problem. I'm newbie in Compiler Design :-)


texts: What kind of standard deviation must be used in optimization algorithms?

texts:
I would like to ask about the standard deviation of objective function value.

There are two types of standard deviations:

Population standard deviation
Sample standard deviation

In metaheuristic optimization algorithms most scholars are used std in your papers. What kind of standard deviation is used in metaheuristic optimization algorithms?


texts: If $PSPACE^{SAT}=PSPACE$ and $PSPACE \subseteq EXP$, then why does $EXP^{SAT}$ not necessarily equal to $EXP$?

texts:
I read the following claim:

$PSPACE^{SAT}=PSPACE$
$EXP^{SAT}$ is not necessarily the same as $EXP$

The first claim makes sense; $PSPACE \subseteq PSPACE^{SAT}$ trivially, and for any language $B \in PSPACE^{SAT}$ decided by an oracle machine $M_B$, we can define a non-deterministic machine $M'_B$ that works like $M_B$, except instead of querying an oracle, $M'_B$ instead guesses a witness and calls $M_{SAT}$ (a machine deciding $SAT$). It can easily be shown that $M'_B$ decides $B$ in polynomial space, and so $B\in NSPACE$. But from Savitch's Thoerem, $NSPACE=PSPACE$, and so $B \in PSPACE$. Thus, $PSPACE^{SAT}=PSPACE$.
I assumed that since $PSPACE \subseteq EXP$, then it should follow that $EXP^{SAT}=EXP$ as well. After all, it only needs to be shown that $EXP^{SAT}\subseteq EXP$ to prove the claim, but I can't see where the problem lies.
For that matter, my assumption was that if $X$ was any complexity class such that $X\subseteq Y$, then $Y^X=Y$. After all, any X-oracle doesn't allow Y to decide any language it couldn't already decide. But if the two claims are true, then obviously my assumption is wrong.


texts: Showing asymptotic lower bound on log of recurrence

texts:
I'm trying to prove a lower bound on some computational problem, but in order to do it, I need an $\Omega(n\log(n))$ lower bound on $\log(T(n))$, where $T(n)$ is a recurrence defined as follows:
$T(1) = 1$
$T(n) = \sum_{k=1}^{n-1} T(k)T(n-k)$
Does this recurrence have a known solution? If not, just giving a lower bound on $\log(T(n))$ would suffice for me. Optimally, I would want an $n\log(n)$ bound, but I don't know if its possible to achieve. So, any lower bound bigger than a linear one would be appreciated! Thanks in advance for helping me out!


texts: Is huffman coding tree a heap or a trie?

texts:
I study Huffman Coding tree from "Data Structures and Algorithm Analysis" of Shaffer and it says that Huffman Coding tree is an opportunity to experience a search trie. However, the code implements it with a heap class.

As a result, I wonder if Huffman Coding tree is actually a heap or a trie? If it is a heap, is it a mimHeap or a maxHeap. I'm somehow confused because there are some online resources calling it a minHeap, as it should be a maxHeap.

Anyway, thank you very much in advance.


texts:
Is there any good formal investigation or at least definition of different strategies of event-driven concurrent programming?
I've read that there exist readiness based (pull based) and completion based (push based) approaches, and also callback based and polling based ones. I believe the two classifications are orthogonal:
               | readiness based | completion based |
---------------|-----------------|------------------|
callback based |                 |                  |
---------------|-----------------|------------------|
polling based  |                 |                  |
---------------|-----------------|------------------|

Additionally, callback based and polling based are not mutually exclusive: a callback can be used for notification that polling can be retried.
What i've read so far gives me only some vague intuition, and distinctions are fuzzy. For example, for an I/O operation to be ready, i suppose that some other operation needs to be completed, and once some operation is completed, something else can become ready.
So, are there any good academic-level references on this subject?


texts:
Would someone please  clarify for me the difference between direct and random access?

Specifically, why does this Wikipedia article on Direct Access Storage Devices distinguish between the two:

  The direct access capability, occasionally and incorrectly called
  random access  (although that term survives when referring to memory or RAM),

whereas this article on random access doesn't:

  In computer science, random access (sometimes called direct access) is
  the ability to access an element at an arbitrary position in a
  sequence in equal time, independent of sequence size.


texts: How can I calculate optimal batch sizes for calls to an external server?

texts:
So I have a large number of commands, say 500,000, that I want to send and run on a server somewhere else, and get the answers back. All of these commands together takes a long time to execute - roughly 30 seconds. I could group all those commands together and send them off, have the server execute them all, and then get my results. But that's significantly slower than grouping those commands into batches, which I send off all at the same time, and can then execute on that server in parallel.

However, I can't make the batches too small, because I'm doing this from a browser, and most modern browsers can only keep ~6 concurrent open connections with the same server. So you get a trade off - for large batch sizes, I'm not sending enough concurrent commands to the server. For small batch sizes, I'm sending so many that the browser gets backed up.

I've tried this experimentally, and I wind up with data that looks something like this (pardon the terrible drawing):

On the x axis is the number of batches I use, and on the y axis is the time the whole resulting calculation takes. I haven't succeeded in finding a model that really works for this data, only a basic crude approximation.

All I really want to know is, is there research on this kind of thing I can look up? Some way that, given code execution times on the server, and delay times for getting there, I can calculate the optimal batch size? I can't be the only person who's wanted to solve this problem. If there isn't, then what do you think?


texts: Show that if Automata $A$ recognize language $L$, there also exists an automata $A′$ that recognize $Double(L)$

texts:
I don't know if this question should have better been on math.Stackexchange

Let be the operation $Double$ on the words on an $\Sigma$ alphabet which inserts after each character a copy of this character. Thus, $D(ab) = aabb$, $D(abaab) = aabbaaaabb$, etc... We had to prove that these regular expressions are closed by this operation and it was a sucess.

  We now have to prove this properties for automata. In other words, we have to prove that if we have a language $L$ such that it exists an automata $A$ that recognize $(L=L(A))$, there also exists an automata $A'$ that recognize tha language $Double(L)$.

  I shouldn't use equivalence between automatas and regular expressions

goal : I therefore deduce that I have to prove that autmomatas are closed by the Double operation.

the hypothese : is that it exists a language $L$ such taht it exists an automata $A$ which recognizes it.

proof attempt : $D(L)$ being a language, it must be a automata associated.

But:

has(have ?) every language(s?) an associated automata?
Isn't this proof too short or taking its goal has an hypothesis ?

Proof attempt n°2

Following Rick Decker's advises, here is the second attempt to prove that if we have a language $L$ such that it exists an automata $A$ that recognize $(L=L(A))$, there also exists an automata $A'$ that recognize tha language $Double(L)$ :

To prove it, we are goint to construct an automata $A'$ such that $A'=D(L)$.

The idea is to construct an input string of $w$ that we reads from left to right. After having read the entire string $w$, it checks whether the following char is the same. If it is the case we remain in the final state. Otherwise, we go to a transitional state and if the following char isn't exactly the same, we go to the bin state.

$Q=\{q_0, q_1, q_2, p\}$, $q_1,q_2$ are waiting states, $p$ is a bin state.

$\Sigma$ is the alphabet. For the example it is : $\{a,b\}$.

$\delta : Q × \Sigma → Q$ is a function, called the transition function,

$$\begin{array}{c|cc|c|c|}
& a & b\\
\hline
q_0 & q_2 & q_1\\
q_1 & p& q_0\\
q_2 & q_0&p\\
p & p & p\\
\hline
\end{array}$$

$q=q_0$.

$F=q_0$ is the final state. It corresponds to the intial state because the empty set is accepted by the automata.


texts: Finding the minimum subset of intervals covering the whole set

texts:
Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers and $a < b$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any value within the range of any pair in $A$, the value is also within the range of any pair in $B$.

I am currently considering setting $B$ equal to $A$ and, for each pair in $B$, if removing the pair still upholds the property of $B$ described above, remove it. However, I feel this algorithm is too inefficient. Is there a more efficient algorithm?


texts: fastest way to compute scalar product of an ensemble of vectors

texts:
I have an ensemble of points in 3D space, represented by their coordinates $\mathbf{c_i}\equiv(x_i,y_i,z_i)^\top$ . I need to calculate

the distance between all these points: $\quad\forall i,j\quad d_{ij} \equiv |\mathbf{d_{ij}}|\equiv |\mathbf{c_j}-\mathbf{c_i}|$
the scalar product between all distances that share a common coordinate. $\quad\forall i,j,k\quad \mathbf{d_{ij}}\cdot\mathbf{d_{ik}}$

What is the fastest way to do this on a single thread? Is Fourier space going to be of any use? Can it be parallelized to make it even faster? If approximations are proposed, they should come with an error bound.


texts:
I have an assignment where i have to encode certain problem to conjunctive normal form so i can solve it by using SAT solver. I have been able to encode my problem correctly but the solver is quite slow and most likely the cause for this is the length of some clauses which i have.

So my question is:

How can one break down long clauses into smaller ones and therefore speed up the SAT solver, lets say i have following clause:

$ (x_1 \vee x_2 \vee x_3 \vee ... \vee x_n) $ where n can potentially be large number.

Is there any way to split this into smaller clauses which would be logically equivalent?


texts: Is there any precedence for symbols for constructing parse trees?

texts:
I am wondering if some symbols such as the ones in propositional logic have precedence over others in drawing parse trees.

For example, the sentence: p ∧ q → r, would ∧ take precedence over → in becoming the root of the parse tree or vice versa?

Or is there no precedence meaning, → or ∧ could be used the root?


texts: Prove that, if deg(v) ≥ (n−2)/3 for every vertex v in G, then G contains at most two connected components

texts: Let G be a graph with $n$ vertices such that $n\geq2$. Prove that, if $\mathrm{deg}(v)\geq \frac{n-2}{3}$ for every vertex $v$ in G, then G contains at most two connected components.


texts:
I've been given a task that I had issue solving.

Problem statement:

  John likes jumping so he is about to build a new jumping terrain. The
  terrain consists of N blocks, and in each block he can put multiple
  jumping marks. He starts by jumping from the ground on some mark from
  the first block, then on some mark in the second block, and so on
  until he finally jumps from some mark from the N-th block back to the
  ground.

  John has bought N boxes of jumping marks (i-th box contains ci marks).
  He has put them into the cart and now he is moving from the first
  block to last one. He wants to assign each box to distinct block.
  After that, for each box he will put all marks from the box into
  respective block.

  He is not aware that while setting up the terrain, Mark is
  hiding between boxes and steals one jumping mark from each box that is
  left in the cart every time the cart moves to next position (excluding
  the first position).

  John wants to build such a terrain that the number of ways to jump
  from the beginning to the end of the terrain is maximum possible.

  Help Ivan find out the best arrangement of the boxes to achieve the
  maximum number of ways he can jump the terrain if he places the boxes
  in the correct order.

For example, given an array [2, 4, 4, 1], solution is 2 (correct order is [1, 2, 4, 4], which because of Mark turns to [1, 1, 2, 1], and there are two ways to traverse that array). For [1, 1] solution is 0. For [3,3,3] solution is 6.

At first I thought this is a simple matter, but feedback I got from my instructor told me that solution was unsatisfying.

Here is my solution:

def solution(a):
    # a is input array
    n = len(a)
    a.sort()
    c = 1
    result = a[0]
    for i in range(1, n):
        v = a[i] - c
        if v < 1:
            return 0
        c += 1
        result *= v
    return result % ((10 ** 9) + 7)

What is wrong with this solution?


texts:
This is an example of an assignment question, there are 3 of them so I created my own in order to better understand it.

First, we have the variable m which is a binary encoding such as 100#001#010 which is translated to [4, 1, 2]

Next is the variable n = the total length of the input/encoding

And k which is the largest number in the list (4 in the previous list)

Now we set $f(n)$ as the turing machine that took m as input, and want to see if $f(n) = O(g(n))$ where $g(n)$ is a polynomial.

How can I solve this on $f(n) = m (log (n)) (log (k))$?


texts: Distance function such that we visit every "color region" once

texts:
Consider the following image:

Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right.

We must go through each color exactly once, and once we go outside a color, we can't go back to the same one.

Here is a example of what I think is a optimal path:

As per dikisjtra algorithm, we update the distance at once node if d[current] + weight(this_node, next_node) < d[next_node]. Usually these weights are given to us, but in this case, we must create a weight function such that given any two pixels (x1,y1),(x2,y2), our path follows something like what I have drawn in white.

You can assume all the colors are indeed different, even though they might look similar because of shades.

I am thinking of the following conditions to check in the weight condition:

going from old color -> same color -> maybe a weight of 5

going from old color -> new color -> a low weight of 1

What are the cases of the weights I can assign so dijikistra finds the path shown in white?


texts:
I'm reading through Sebastian Raschka's Python Machine Learning, and I see something confusing that is not explained in the text.
In the code on this page:
https://github.com/rasbt/python-machine-learning-book/blob/master/code/ch02/ch02.ipynb
Implementing a perceptron learning algorithm in Python
In the training process, in addition to updating weights, I see this happening:
 self.w_[0] += update

Then later on, during "prediction," when weights are applied to input, I see self.w_[0] being used:
def net_input(self, X):
    """Calculate net input"""
    return np.dot(X, self.w_[1:]) + self.w_[0]

It looks like this is a bias being added into the perceptron, but the book says that net_input is simply calcuating "weights transpose dot x" and mentions nothing about this + self.w_[0] part...
Can anyone take a look at the linked code and make sense of what's going on with the self.w_[0] part? Or has anyone else got this book that might explain why that's there?


texts: Solve longest common subsequence in a non dynamic programming way?

texts:
I am working on the longest common subsequence (LCS) problem while learning dynamic programming. Below is the Java code I created to solve the problem, which is not dynamic programming as far as I understand.

public class LCS
{
    public static String lcs(String a, String b )
    {
    String lcs = lcs(a, b, "", 0, 0);
    return lcs;
    }
    private static String lcs(String a, String b, String lcs, int i , int j)
    {
    int length_a = a.length();
    int length_b = b.length();
    if (i == length_a || j == length_b) return lcs;
    if (a.charAt(i) == b.charAt(j))
        {
        lcs += a.charAt(i);
        i++;
        j++;
        }
    else
        {
        String lcs_i_plus = lcs(a, b, lcs ,i+1, j);
        String lcs_j_plus = lcs(a, b , lcs ,i, j+1);
        if  ( lcs_i_plus.length() > lcs_j_plus.length())
            i++;
        else
            j++;
        }
    return lcs(a, b, lcs , i, j) ;
    }
    public static void main(String[] args)
    {
    //client
    String a = "GGCACCACG";
    String b = "ACGGCGGATACG";
    String lcs = lcs(a, b);
    StdOut.println(lcs);
    }
}

In contrast, the book I studied offered another solution which was claimed to solve the LCS problem via dynamic programming. The code looks as follows.

 public class LongestCommonSubsequence
 {
    public static String lcs(String s, String t)
    {  // Compute length of LCS for all subproblems.
    int m = s.length(), n = t.length();
    int[][] opt = new int[m+1][n+1];
    for (int i = m-1; i >= 0; i--)
       for (int j = n-1; j >= 0; j--)
       if (s.charAt(i) == t.charAt(j))
          opt[i][j] = opt[i+1][j+1] + 1;
       else
          opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
    // Recover LCS itself.
    String lcs = "";
    int i = 0, j = 0;
    while(i < m && j < n)
    {
       if (s.charAt(i) == t.charAt(j))
       {
          lcs += s.charAt(i);
          i++;
          j++;
       }
       else if (opt[i+1][j] >= opt[i][j+1]) i++;
       else                                 j++;
    }
       return lcs;
    }
    public static void main(String[] args)
    {  StdOut.println(lcs(args[0], args[1]));  }
}

I have tested both implementations and they produced the same results. My questions are:

1.Is my approach correct?

2.If my approach is correct, what are the time complexity of these two approaches?


texts: Graph canonization is not a decision problem. But what type of problem is it?

texts:
I noticed that the most convenient way to deal with quotient structures (like the rational numbers or other equivalence classes) within ZFC is to select a unique representant from each equivalence class, which is possible due to global choice. Then I noticed that this strategy also seems to work quite well in practice, i.e. graph canonization is not really less practical than more general approaches to graph isomorphism. On a theoretical level however, it's hard to clear up the relation between graph canonization and graph isomorphism. The most basic problem is that graph canonization is not a decision problem, and there is no obvious way to reduce it to a decision problem either. In fact, it doesn't fit any problem type which comes to my mind!

Some computational problem types based on different types of requested output:

decision problem
optimization problem
search problem
counting problem
function problem

Some computational problem types based on different types of expected input:

offline/online problem
(non-)promise problem

Yuval Filmus suggests that it is a canonization problem. However, all publications about canonization problems seem to treat questions closely related to graph canonization. I would rather prefer a wider problem class, maybe invariant (property) problem could be a nice class, if it could be suitably nailed down (and formalized).


texts: Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS?

texts:
I am trying to go through the proof of the Master Theorem in Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS). The theorem providers an asymptotic analysis for recurrence relations $T(n)=aT(n/b)+f(n)$ where $a\geq 1, b > 1$  and $f(n)$ is an asymptotically positive function.

The authors create a formulation of the following lemma (4.3):

  if $f(n) = \Theta(n^{\log_ba})$, then $g(n)=\Theta(n^{\log_ba}{\log_bn})$

where $g(n) = \sum_{j=0}^{\lfloor \log_b n \rfloor - 1} a^jf(n_j)$ and $n_j = \begin{cases}
n,  & \text{if j = 0} \\
\lceil n_{j-1}/b \rceil, & \text{if j > 0}
\end{cases}$

When it is proving for the situation in which floors and ceilings appear the autrors make a statement:

  For case 2, we have $f(n)=\Theta(n^{\log_b a})$. If we can show that
  $f(n_j) = O(n^{\log_ba}/a^j) = O((n/b^j)^{\log_ba})$, then the proof for
  case 2 of Lemma 4.3 will go through.

Well, I got it. When this condition is true we can find some constant $c$, such that

$g(n) \le c\sum_{j=0}^{\lfloor \log_b n \rfloor - 1} n^{\log_b a}$

and conclude that $g(n) = O(n^{\log_b a}{\log_bn})$.

But it's not a proof that $g(n) = \Omega(n^{\log_b a}{\log_bn})$. Where is one? Should it be obvious? How can I prove this statement?


texts: Which word could I use for the Pumping Lemma proof?

texts:
I have the language

$ A_{1} \triangleq\left\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\{a, b\}^{*} \wedge |\left.w\right|_{a}=l+m\right\} \operatorname{with} \Sigma \triangleq\{a, b, c, d\} $

and I have no idea which word I should use to prevent a case distinction.

My first idea was to set $l = 0$ and $w=b^n$ so I would have the word $p=aa^nd^n$.
The problem with that is, I have no idea how to proof this because this single "a" makes me crazy.
Do you could help me?


texts: Explanation for the proof "Every 2-thread consensus protocol has a bivalent initial state"

texts:
From the book 'the art of multiprocessor programming':

  A protocol state is bivalent if the decision value is not yet fixed:
  there is some execution starting from that state in which the threads
  decide 0, and one in which they decide 1.

  Lemma 5.1.1. Every 2-thread consensus protocol has a bivalent initial
  state. Proof: Consider the initial state where A has input 0 and B has
  input 1.  If A finishes the protocol before B takes a step, then A
  must decide 0, because it must decide some thread’s input, and 0 is
  the only input it has seen (it cannot decide 1 because it has no way
  of distinguishing this state from the one in which B has input 0).

  Symmetrically, if B finishes the protocol before A takes a step, then
  B must decide 1, because it must decide some thread’s input, and 1 is
  the only input it has seen. It follows that the initial state where A
  has input 0 and B has input 1 is bivalent.

I don't understand why it can only output the input it has seen already. And for A why "it cannot decide 1 because it has no way of distinguishing this state from the one in which B has input 0)".


texts: How to solve a polynomial of the form y = ax^3 + bx^2 + cx + d using the incremental algorithm in computer graphics

texts:
I am studying Computer Graphics and need to design an incremental algorithm for solving the polynomial $y = ax^3 + bx^2 + cx + d$, and then implement that in OpenGL. The input will be the values of $a, b,c,d$ and the desired output is a line/curve to be drawn. The values of $x$ would be in the range $1\leq x\leq100$. The algorithm needs to be very efficient hence I am required to use only addition operation, as multiplication is less efficient.

It would be similar to this technique, but here the polynomial to be considered is the one given above. I have searched a lot on the Internet but cannot find the required solution, because most of the examples solve the equation $y = mx+b$.

Can anyone kindly guide me how to solve it or which method should be applied to solve it?


texts:
I've been trying to attempt a particular question that I need to translate truth table into boolean expression but I'm completely stuck on one point now.

First, I worked it out by using Sums of product by getting X first.

(I did this by taking the inputs with X = 1)

A'B'C'D' + A'B'C'D + A'B'CD + A'BC'D' + A'BCD' + A'BCD +AB'C'D + AB'CD + ABC'D' + ABC'D

= A'B'C'(D'+D) + A'CD(B'+B) + A'BC(D+D') + AB'D(C'+C) + ABC'(D'+D) (Distributive Law)

= A'B'C' + A'CD + A'BC + AB'D + ABC' (Double Complement Law)

[Currently I'm stuck here and don't know how to proceed]


texts: Formulating if-then constraints in linear binary programming

texts:
From a stock of various computer accessories of different brands, the optimization problem requires deciding to keep or discard products. The decision should be made maintaining the following if-then condition: If one product of a certain brand is eliminated than all the products of that brand should be eliminated. So, for example, if the stock has different models of HP branded monitor, printer, mouse and keyboard, and decision is made to discard one model of HP mouse, then all other HP products need to be discarded as well.
As the number of items under each brand varies, how do I formulate this?


texts: Proving regular languages are closed under a form of interleaving

texts:
I've got the following definitions:

$$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$

when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means the $i$-th letter in $w$.

$$\mathrm{Interleave}\,(L_1,L_2)\ \  = \!\!\!\!\bigcup_{\substack{x\in L_1,\ y\in L_2,\\ |x|=|y|}}\!\!\!\! \mathrm{Interleave}\,(x,y)$$
when both $L_1$ and $L_2$ are languages.

I have to prove that if I know that $L_1$ and $L_2$ are both regular languages, $\mathrm{Interleave}\,(L_1,L_2)$ is a regular language as well.

I have absolutely no idea how to do it .

Thanks in advance.


texts:
Are any algorithms known that can compute the greatest common denominator of multiple (more than two) input values more efficiently than just an iterative application of the fastest GCD algorithm for exactly two input values?  E.g. gcd(a, b, c, ...) vs. gcd(a, gcd(b, gcd(c, ...)))

If so, then what is such an algorithm?

If not, then is it known whether there cannot exist such an algorithm?


texts: Node potentials of minimum cost flow successive shortest path algorithm

texts:
I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum cost maximum flow from $s$ to $t$ using the successive shortest path algorithm. It goes something like this:

Initialize all edge flows to 0.
Initialize all potentials pi[v] to 0.
While there exists an augmenting path in G_f (the residual network):
    Set the costs of all edges e = uv to be:
        b(e) = a(e) + pi[u] - pi[v], if e exists in G or
        b(e) = -a(e_reverse) + pi[u] - pi[v], where e_reverse = vu otherwise
    # We are now assured all edges have nonnegative costs
    Using Dijkstra method with costs b(e) in G_f:
        Find the cheapest augmenting path from s to t
        Calculate dist(v), the cost of cheapest path from s to v
    Augment the cheapest path to t to current flow
    Set pi[v] = pi[v] + dist(v) for all vertices v
The current flow gives the minimum cost maximum flow.

Obviously, if all costs $a(e) \le a_{max}$ and all capacities $c(e) \le c_{max}$, then there is a loose bound $|E|c_{max}a_{max}$ for cost of minimum cost maximum flow. However, the bounds on the potentials $\pi(v)$ and distances $dist(v)$ are not so obvious. In fact, judging by how the algorithm adds $dist(v)$ to $\pi(v)$ each iteration, $\pi(v)$ can possibly be multiplied by $|V|$ each iteration!

My question is, is there a way to calculate a non-exponential bound for $\pi(v)$? For instance, if all capacities and costs are at most $100$, $|V| = 200$, $|E| = 5000$, is it possible that $\pi(v)$ and $dist(v)$ still exceed 64-bit integers? How do so many implementations not use Big Integers?


texts: Approximation for fewest incompatibilities in a scheduling algorithm

texts:
Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal answer, but what will a task selection algorithm that selects tasks based on the fewest incompatibilities produce (i.e. what is the $c$ approximation for this algorithm, such that this algorithm will always select a solution that has at least $1/c$ the number of tasks as the optimal solution does)?

Clearly, selecting tasks that have the fewest incompatibilities will not always be optimal, and I can construct a simple case where this is true. However, I'm having trouble coming up with a $c$ approximation for this algorithm. If we have a set of tasks, and we know the optimal solution will select $k$ of them, how many tasks can we guarantee the fewest incompatibilities algorithm will select?


texts: how to deal with mismatched tag bits in cache

texts:
I was reading a textbook which describe general organization of cache as:

Then an exercise is, given m=32, C = 1024, B = 8,E = 4, S = 32, so s = 5, b = 3, therefore t = 32-5-3 = 24
I am a little bit confused here, since E = 4, we only need 2 bits to differentiate it, so t should be 2, if t is 24, isn't that we waste 22 bits?


texts: Complexity of class finding selection of entries in matrix

texts: Suppose I have a matrix with entries either $x$ or $y$, where the number of rows = number of columns = $n$. If I want to select/circle $n$ entries such that for each row, only exactly one is circled, for each column, also exactly one is circled, and such that all entries circled are only $x$ (if such a circling of entries exists), what complexity class does this belong to? Thanks!


texts: Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$

texts:
The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can't do it. I could do the following specific cases (by repeatedly using the same recursion):
1)$T(n)=T(n-1)+O(n)$
2)$T(n)=2T(\frac n2)+O(n)$
Can anybody please help me to solve this general case (or at least suggest some other way to prove that the worst case is $k=0$)?
P.S. I don't know Master's theorem, so I would appreciate a solution without using that (In case that is applicable here).


texts: Why do we count the ceils and floors in recursive functions?

texts:
When we solve the recursive functions using substitution method, the impact of ceil and floor functions is trivial when the size of the input is large enough. For example the answer of
$$
T(n) = T(\lceil n/3 \rceil) + O(n)
$$
is equivalent to
$$
T(n) = T(n/3) + O(n)
$$
when the $n$ is large enough. Since
$$
T(n) = T(\lceil n/3 \rceil) + O(n) \leq T((n/3) + 1) + O(n)
$$
and the size $1$ added to $n/3$ doesn't effect the running time of the algorithm.

My question is, when the ceil and floor functions don't effect the asymptotic bounds of a algorithm, why not to ignore them and simply solve the $T(n)$ without them?

CLRS page 67 edition3 says

  When we state and solve recurrences, we often omit floors, ceilings, and boundary
  conditions.


texts: Given $n$ items with $k$ properties, construct a query that contains between $\frac {n} 3$ to $\frac {2n} 3$ items

texts:
I have $n$ items that have a total of $k$ properties. Each item can have any number of properties, from $1$ to $k$. There is no upper limit to k (the lower limit is $\lceil log(n) \rceil$). The items are distinct, so they have different properties.

The query must only contain AND logical operators. For example, a query can be property A and NOT property B and property C.

Obviously, I must construct a query that has an intersection of properties such that the search space is reduced by $1/3$. Is there a faster way of doing this than simply doing a $O(2^k)$ brute force algorithm?