texts: What are some possible "functional" memory structures?

texts:
With my thin knowledge on embedded systems, compilers, and computer architectures, I know that the basics of computer memory(physical) are sort of like an array, with addressing which work like pointers. I see that imperative programming(which eventually unwraps to assembly, or the Turing Machine) fits this architecture very well.

I am a bit interested to see if there is a counterpart of physical memory that might fit the functional programming style. By "fitting", I am making the assumption that all pure functional languages can unwrap to be immutable lambda expressions(via Lambda Calculus). Now, with the array-like memory structure, we have to allocate and gc objects under the scene in order to get lambdas to work(because lambda expressions do not address operations on memory directly). Just as a thought experiment, is it possible to have a device that fits the need of memory in lambda expressions, while not containing a garbage collector?

Yes, I know that some imperative programming languages do use garbage collectors. However, when boiled down to assembly, it doesn't. So I am more curious about the evaluation of "pure" lambda expressions.

Just as a note, the lambda expressions I talk about include the fixed point operator(i.e. recursion).


texts: Subtyping and subkinding, are they relevant?

texts:
I'm thinking about a type system that has some special kind of some certain types that are subtypes of the universe kind type.

Imagine the typing relation, where $A$ and $B$ are both types, $\textbf{Type}$ is the universe kind, like * in Haskell or Type in Idris or Set in Agda; while <: denotes subtyping:

$$
A:a \\
B:b \\
A <: B \\
a <: \textbf{Type} \\
b <: \textbf{Type}
$$

Then what should the relation between $a$ and $b$? Could one of them be the subtype (or subkind?) of the other? Although it is fine to make $a$ and $b$ distinct, but ideally we want more consistent subtyping (subkinding) relations to present.

In other words, if I allow either $a <: b$ or $b <: a$, will the type system become inconsistent?


texts: Shortest curve interpolating points with a constraint on the curvature

texts:
I'm looking for a method for determining a path for a UAV that interpolates a set of input locations, with a constraint on maximum curvature and given an initial velocity vector.

The cost (length) of the path should be as small as possible.

I know a little bit about Dubins curves but that's in 2D and only for two points.


texts: If $n^{\log n}$ is not polynomial or exponential, then what this function is called?

texts:
I just found this sentence on page 6 of Garey and Johnson's "Computers and Intractability".

  Any algorithm whose time complexity function cannot be so bounded is called an exponential time algorithm (although it should be noted that this definition includes certain non-polynomial time complexity functions, like $n^{\log n}$, which are not normally regarded as exponential functions).

My question as following,

If $n^{\log n}$ is not polynomial nor exponential, then what this function is called? Does this have a name or special cases or not?

Thank you.


texts: Words which, cyclically shifted twice, equal their reverse

texts:
Let the alphabet be $Σ = \{0, 1\}$. For any string $w ∈ Σ^*$ of length at least 2, define the
operation $C_2(w)$ to be a cyclic shift of size 2 on $w$. That is, if $w = w_1w_2 \cdots w_n$ with $n ≥ 2$ and each
$w_i ∈ Σ$, then $C_2(w) = w_3 \cdots w_nw_1w_2$ if n ≥ 3, and $C_2(w) = w$ if $n = 2$. Recall that $w^R$ means $w$
written backwards.

Give a context-free grammar that generates the following language:
$$ \{w \mid w \text{ has length at least 2 and } C_2(w) = w^R\}. $$

I'm having trouble constructing the context free grammar, so any tips would be much appreciated!


texts: an algorithm for detecting if noisy univariate data is constant or is sum of step functions

texts:
In an explicit algorithm I'm writing, there is a certain stage where I need to determine whether or not a certain noisy univariate data is constant or is sum of step functions.

For example, defining foo as the algorithm I'm after (writing in Python):

assert foo([0]*20) == False
assert foo([0]*20 + [1]*20) == True
assert foo([0]*20 + [5]*30 + [1]*70) == True

- The data in the examples is not noisy, but assume the real one is (just a bit, one can pinpoint where a step might take place by observing the plot of the data.)

I'd be happy to hear any ideas.


texts: Are there real lexers that use NFAs directly instead of first transforming them to DFAs?

texts: I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic finite automaton (DFA) to parse regular expressions. If I understand correctly, the tradeoff is that a NFA is smaller, but is more time consuming to traverse because all possible states have to be regarded at the same time and therefore it is most of the time transformed into a DFA.  Are there any lexers that use NFAs instead of DFAs in "real"-life i.e. some compiler that is used in production and not a just a proof of concept?


texts: Algorithm to turn gray-scale text into legible binary black and white text

texts:
I have an image with gray-scale anti-aliased text produced by Chromium and need to convert this into pure binary black and white text. Applying a simple binary threshold pass over the image causes artifacts, either missing edges or weird protrusions and text being too bold depending on the chosen threshold.

Below an example of the input, the perfect outcome (as this is how the text would be rendered without AA) and the current outcome based on binary threshold (I think this is a 0.6 threshold). Sadly, it's not possible to instruct Chromium to render the text without anti-aliasing, so a conversion is the only option.

I was wondering if there was an established algorithm for this kind of problem or in what direction I would have to look to find something that could be adapted to work here. Any algorithm would need to be able to run in semi-realtime, no offline solutions.


texts:
I want to construct a DFS and a BFS spanning trees for the graph below. The root is node a. At each step the next edge to be traversed should be the cheapest one.

DFS:

My understanding that to the construct this DFS where each next is the cheapest one, the resultant spanning tree would be:

  {(a,c), (c,h), (h,g), (g,f), (f,b), (b,k), (k, j), (j,i), (i, l), (l,m), (m,e), (e,d)}

BFS:

My understanding that to the construct this BFS where each next is the cheapest one, the resultant spanning tree would be:

  Queue: a  c   d   b   e   f   h   g   k   m   i   j   k

Is my understanding of spanning trees correct when the next edge to be traversed should be the cheapest one? Is this a MCST?


texts: How to handle dfa with countless states?

texts:
I have a question regarding DFA:

Design a DFA M with alphabet $\sum = \ {\{0,1,2,R}\}$ where the states remember actual sums of the number, except that the sum is reset to 0 whenever the symbol $R$ appears. Show diagrammatically how this DFA can be constructed. What is the problem with this DFA?

One thing I do understand is that in order to remember the actual sums I would have to have the sums as states. But sums can be any number from 0 to  infinity. So would the states increase exponentially while reading the input string? How can I tackle this problem?


texts: Building Suffix Array from Suffix Tree. Inorder visit when node has more than two children

texts:
From the notes:

It is not difficult to observe that the suffix array $\texttt{SA}$ of
the text $\texttt{T}$ can be obtained from its suffix tree
$\texttt{ST}$ by performing an in-order visit: each time a leaf is
encountered, the suffix-index stored in this leaf is written into the
suffix array $\texttt{SA}$; each time an internal node u is
encountered, its associated value is written into the array
$\texttt{lcp}$.

How do you do the inorder visit when a node has more than two children?
Let's say you visit the leftmost child, then the node, then the other leftmost child. Then do you visit again the node?
SA in an array of pointer to suffixes, ordered lexicographically.
lcp contains the longest common prefix between two consecutive suffixes $\text{suff}_{SA[i]} \text{ and } \text{suff}_{SA[i+1]}$.
The \$ represents a char that's smaller than every other char.
The value associated to each node is the length of the prefix spelled so far.
The leaves represents indices of suffixes. If T = banana\$, the leaf 3 represents nana\$ (T[3,7])
In the image there's what is supposed to be a suffix tree, but I think there's an error since the edges should be sorted according to their label and the leaf 7 with the edge labeled "\$" should be the leftmost leaf and edge.

When simulating the algorithm, first you visit the node 7 ( using the fixed version of the tree ), then the root, so you have
SA = [7, ...]
lcp = [0, ...]

Then let's say you keep going on with an inorder visit of u. When you go back to the root, do you insert the value 0 again in the lcp? Or do you do it just the first time you visited the root?


texts:
I would like to find a reduction from Max-Cut to Max-2Sat.
Could someone shed light on this problem, preferably spiced with some intuition?

Thanks,
Matan.


texts: Proving $(a+b)^* = b^*(ab^*)^*$ equationally

texts:
I am new to automata theory and have a problem in understanding equivalence of regular expressions, though I can go for the construction procedure of minimized DFAs to prove that both are equal.

I need to prove the following property using different Kleene star properties:

$$(a+b)^* = b^*(ab^*)^*$$


texts: Satisfiability of at least k linear equations over Z2 is NP-hard

texts:
Given a system of $m$ equations in $n$ boolean variables:

$$\begin{align}
a_{11}x_1 + a_{12}x_2 + \dots +a_{1n}x_n &= b_1\pmod2\\
a_{21}x_1 + a_{22}x_2 + \dots +a_{2n}x_n &= b_2\pmod2\\
&\;\vdots\\
a_{m1}{x_1} + a_{m2}x_2 + \dots +a_{mn}x_n &= b_m\pmod2
\end{align}$$

Where all $a_{ij}, x_i$ and $b_i$ are $0$ or $1$, I want to prove that the decision problem of finding if there is a vector $x$ that satisfies at least $k$ equation, is NP hard.

I was given a hint to reduce from 3-SAT, so I am trying to build from each clause in the 3-SAT formula several equations, such that a constant number of them is satisfied iff the clause is satisfied. But I am not sure how to impose this restriction of a constant number of equations satisfied (for all different truth assignments that satisfy the given clause).


texts: How would it be possible that primality testing is in P, but not factorization?

texts:
Suppose that P != NP. Then there exists 3SAT formulas such that their satisfiability is computationally "evil" (i.e, the satisfiability can be exponentially hard to determine in the size of the formula).
Primality testing can be reduced to the satisfiability of a multiplication circuit, which can be reduced to the satisfiability of a 3SAT formula. But "Primes is in P". The satisfiability of this formula cannot be "evil", since it can be reduced to AKS primality test for example.
Integer factorization can be achieved by finding a satisfying assignment to the same formula. This can be achieved by choosing a variable, and then testing the satisfiability again. Choosing a variable, simplifies the formula through unit propagation. The new formula is a subset of the previous one. Now suddenly "we don't know" whether this formula can be solved in polynomial time.
Isn't this a contradiction? Is it possible that the subset of a formula is harder to solve than the formula itself?


texts:
I was given the following problem as homework:

  Let $x$, $y$ be words over an alphabet $Σ$. Prove that $xy = yx$ iff there exists a word
  $z$ such that $x^2y^2 = z^2$.

I was hinted that I am supposed to approach this problem using structural induction. Considering the case where $|x| = |y|$, you obviously get $x=y=z$, as commutativity of concatenation satisfies only under that case.

Taking the case of $|x| < |y|$, we can conclude that $x$ is a prefix of $y$, assuming the induction hypothesis ($xy=yx$), and we can further say that $y=xt$, where $t$ can be assumed to be the trailing symbols of $y$ after the prefix $x$, and hence using $xy=yx$, we get $xxt = xtx$. And I'm stuck here. Can somebody guide me?


texts: Optimising an exhaustive search for a card game

texts:
I'd like to search for a combination of resources that when used, would produce at least up to a threshold of different kinds of materials. For the majority who are not in the know, I'll use an analogue for the rest of the question. For the few who benefit from this information: the game I'm referring to is Magic The Gathering, and the problem is finding whether or not a set of lands can cast a given card.
We can think of the materials as steel and wood. Any resource produces a combination of them. For example:
Requirement: 1 steel + 2 wood
Resources:
- 1 steel + 1 wood
- 1 wood
Verdict: POSSIBLE

There may be generic requirements, which can be fulfilled by whatever resource is available.
Requirement: 2 ANY + 1 wood
Resources:
- 1 steel
- 1 wood
- 1 wood
Verdict: POSSIBLE

Resources may be used to produce different combinations at will, when stated of course.
Requirement: 1 steel + 1 wood
Resources:
- 1 steel
- 1 steel OR 1 wood
Verdict: POSSIBLE

Finally, there may be costs associated with certain production. Here marked as cost -> production. Costs are production specific.
Requirement: 2 steel
Resources:
- 1 steel
- 1 wood
- 1 wood -> 1 steel OR 0 -> 1 wood
Verdict: POSSIBLE

Now, given a set of these resources it is relatively easy to figure out if a given requirement can be fulfilled. What I have currently is a naïve exhaustive search with one optimisation (step 1). In pseudo-python it goes as follows:
1. produce with resources that have only one production and no cost to have current "production"
2. can_fulfill(requirement, current production, resource list)

def can_fulfill(requirement, production, resources):
    for i, resource in enumerate(resources):
        remaining = resources[:i] + resources[i + 1:]
        for cost, gain in resource:
            if can_subtract(production, cost):
                new_production = production - cost + gain
                if fulfilled(requirement, production):
                    return True
                recur = can_fulfill(requirement, new_production, remaining)
                if recur:
                    return True
    return False

It does work, and for single-production resources it is lightning fast. But in this particular case there can be many resources with multiple production options, which slows the calculation. I think the exhaustive search is my only option, because one can't know which productions ultimately lead to the fulfillment of a requirement, but could there be more clever optimisations I could implement?
My parameters are somewhat conservative for these kinds of optimisation problems I think: I expect to have up to twenty resources, each with up to eight - typically three different productions. In the game there are five production types (steel, wood and 3 more).


texts: Convolutional Neural Network Example in Tensorflow

texts:
I want to ask the dimension change in different convolution and max-pooling layer. I am referring to the example in TensorFlow tutorial:

http://tensorflow.org/tutorials/mnist/pros/index.html#deep-mnist-for-experts

The original image is a 28x28x1

The first convolutional layer:

apply convolution to a 5x5 patch with 32 features -> 24x24x32
apply max-pooling 2x2 -> 12x12x32

Second convolutional layer:

apply convolution to a 5x5 patch with 64 features -> 8x8x64
apply max-pooling 2x2 -> 4x4x64

But it said "Now that the image size has been reduced to 7x7" but my calculation seems to claim that it is a 4x4

Did I miss some concept? I am new to CNN so it may be a beginner question.

Thanks


texts: Similarity between Min-Conflicts and Coordinate Descent in CSPs?

texts:
I'm currently writing a library that solves a specific type of problem that involves mainly constraint satisfaction.

I have came across the Min-Conflicts Algorithm which proved to be rather efficient in the context of the problem.

However, I have recently chanced upon the Coordinate Descent Algorithm and how strikingly it resembles the Min-Conflicts Algorithm.

Probably the only difference is that in Min-Conflicts, a random variable is selected to be modified at each step whereas Coordinate Descent cycles through the variables.

Am I right to say that apart from this difference, min-conflicts and coordinate descent are essentially equivalent? If so why are classified differently?


texts:
This question is about the correct terminology. Let $P1$ and $P2$ be two LOOP programs. Then $P1;P2$ is also a LOOP program, which executes $P1$ and then executes $P2$. Would this be called concatenation of LOOP programs or nested LOOP programs?
I know the answer has to be concatenation because nested would mean having a LOOP program inside another LOOP program. This is not the same as what is written above. Therefore, the answer has to be the former. I just wanted to make sure that concatenation is the correct term here or is there another, more proper term?


texts: Split array into contiguous subarrays of approximately same sums

texts:
My question is similar to this splitting question, but my objective function is different.

Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty subarrays ($N<n$) of approximately same sums:

$$
\min_{\text{splits}} \,(\max_j S_j - \min_j S_j),
$$
where $S_j$ is sum of numbers in $j$-th subarray $(j=1,\ldots,N)$.

E.g., best splitting of $100, 1, 1, 103, 90$ into three subarrays is $100,1,1|103|90$.

Typically $n\approx~10^6-10^8$, $N\approx 10-100$.

I suspect it would be some greedy approach...


texts: Calculate joint entropy of a Hamming Code over a Binary Symmetric Channel?

texts:
I have a normal (7,4,3) Hamming Code over GF(2) and a parity check matrix for it (not posted, because I don't think it's involved).

I have a set X of 4 bit source vectors called x. They all have equal probability to be sent. So I would assume p(x) = 1/16. They are sent over a BSC with the bit error probability p=0.15.

Y is the decoded message set. It contains the same elements as X. However it can occur that a message x from X sent and decoded into y from Y would not be x = y (too many errors to correct/detect).

For each pair (x, y) from X x Y (Most likely Cartesian product?) we can derive a probability p(x,y) (the probability that a message x was sent, but received as y).

The task says "it is not hard to see we can calculate p(x,y) if we have the BSC bit error probability."

It is hard to see for me, though. I would have 16 vectors in X and 16 vectors in Y, that would give me a 256 row table. Then for each of that to calculate the probability of 1 scrambled bit, 2 scrambled bits, 3... and so forth?

I can write a program to do it, but this course is meant to be done by hand. Any help appreciated!


texts: Check constraint under some condition in linear programming

texts:
I would like to minimize linear pseudo-boolean function

$$\mathrm{obj} = \sum_i c_i \mathrm{sel}_i$$

subject to $$\sum_i c_i sel_i \geq \mathrm{Value} \qquad\qquad(1)$$ where

$c_1,\dots c_5, \mathrm{Value}$ are some constants;

$\mathrm{sel}_1,\dots,\mathrm{sel}_5$ are sort of selector variables, $ 0 \leq \mathrm{sel}_i \leq 1$

Everything is pretty straightforward, but I need to check constraint (1) if and only if some of $\mathrm{sel}_i = 1$. In the other words, if $\mathrm{obj} = 0$, that is OK with me, but if some or all of $\mathrm{sel}_i$ are picked up, I need to check $\mathrm{obj} \geq \mathrm{Value}$. Currently I'm using SAT to solve similar problem, but I prefer to study something else. Maybe I need consider different framework for this task? Any directions will be very useful. Thanks in advance.


texts: How to prove a problem is NOT NP-Complete?

texts:
Is there any general technique for proving a problem NOT being NP-Complete?

I got this question on the exam that asked me to show whether some problem (see below) is NP-Complete. I could not think of any real solution, and just proved it was in P. Obviously this is not a real answer.

NP-Complete is defined as the set of problems which are in NP, and all the NP problems can be reduced to it. So any proof should contradict at least one of these two conditions. This specific problem, is indeed in P (and thus in NP). So I am stuck with proving that there is some problem in NP that can't be reduced to this problem. How on the earth can this be proven??

Here is the specific problem I was given on exam:

  Let $DNF$ be the set of strings in disjunctive normal form.
  Let $DNFSAT$ be the language of strings from $DNF$ that are satisfiable by some assignment of variables. Show whether or not $DNFSAT$ is in NP-Complete.


texts: How would you go about creating a algorithm that should generate a shakespearean sonnet on any given theme

texts:
I need to create an algorithm that is going to create a shakespearean sonnet for a specific theme. This theme should be generated out of twitter tweets that have some hashtag.

My current idea goes like

While training:

break up sonnets and other kinds of poems into words (or charachters, have not decided yet)
extract key words from sonnet using tf/idf
convert key words into a vector that will represent a theme using doc2vec
use this words and a theme vector as an input in lstm network to generate a sonnet by predicting next word (charachter) on a particular theme but without a sonnet structure
create a discriminator lstm network with the same input but trained only on sonnets main function of which is going to be to find how much does this poem looks like a sonnet
combine generator and discriminator networks into a GAN

While generating

find some amount of tweets with this hashtag
extract keywords from this tweets using tf/idf
convert this key words into one vector using doc2vec
generate a sonnet with a trained model usin this parameters

I am only a beginner in machine learning, so I would like to hear opinions of more experienced data scientist, is this algorithm going to work and what can be improved?

Thank you.


texts: It may be a dumb question, but is $\mathsf{DSPACE}(f(n)) \subset \mathsf{NSPACE}(f(n))$ or is $\mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n))$?  In other words, is the containment relation proper or not?  Wikipedia says the first one, while the ComplexityZoo says the other one.


texts: Decidable languages and unrestricted grammars?

texts:
Turing machines and unrestricted grammars are two different formalisms that define the RE languages.  Some RE languages are decidable, but not all are.

We can define the decidable languages with Turing machines by saying that a language is decidable iff there is a TM for the language that halts and accepts all strings in the language and halts and rejects all strings not in the language.  My question is this: is there an analogous definition of decidable languages based on unrestricted grammars rather than Turing machines?


texts: Bachmair and Ganzinger, ordering of equations

texts:
Bachmair and Ganzinger (1991), 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', page 4, defines an order on equations. (This is an arcane piece of machinery but a critical one in the overall attempt to get to the point where equations can be applied in one direction, thereby dramatically improving the performance of automated reasoning on problems involving equality.)

If $s \succ t \succ u$

Let $s\approx t$ have the multiset representation $\{\{s\},\{t\}\}$

Let $s\not\approx t$ have the multiset representation $\{\{s,\bot\},\{t,\bot\}\}$ where $\bot$ is a new symbol such that every existing symbol is greater than $\bot$.

Then $s\not\approx u \succ s\approx t$ even though $t \succ u$.

... wait, how? Sure, $s\not\approx u$ also contains a couple of occurrences of $\bot$, but what of that? $t \succ u \succ \bot$, so the comparison should be decided by $t$ vs. $u$; $\bot$ should not have enough weight to tip the balance, so to speak.

What am I missing?

(I have seen later writing that gives $s\not\approx t$ the multiset representation $\{\{s,s\},\{t,t\}\}$, and I see how this solves the problem, but I don't see how it is solved in the original version.)


texts: Algorithm for out-of-area point classification

texts:
I have a device that sends its coordinates every 30 seconds. When I receive the coordinates, I classify the point as either belonging to (ie being inside) one of a number of predefined areas (so I assign an area number > 0 to it), or an "external" point (indicated by area -1).

External points can be caused, essentially, by two reasons:

1) The device is moving and is currently between two areas, so if moving from area 100 to area 78 there will be a sequence like 100, ... 100, -1, -1, ..., -1, 78, 78, 78... The sequence of -1's will be longer or shorter depending on the distance between the two areas and the device speed.

2) The device is close to an area's border and due to the limited precision of the device's GPS it may look like sometimes the device is entering and exiting the area, so it will be something like 99, -1, 99, 99, -1, -1, 99, 99... until it finally settles back to a steady run of 99's when the device moves further back into the area (or moves to another area, in which case we have case 1) above).

At the end of the day, I have a list of (timestamp, coordinates, area) entries (about 2500 points, encompassing an unknown number of areas, depending on how the device moved during the day).

Now my need is to classify external points (area == -1) and forcefully assign them to some real area. So for example for case 1), half (more or less) of the -1's should be assigned to area 100, the other half to area 78, while for case 2) all of the -1's should be assigned to area 99.
Of course this reclassification will be done when the complete data for the day is available, not in real time.

I just need some starting point about how to tackle the problem or existing algorithms that can do the job, then I'll do my research. Thanks.


texts: Elegant approach to finding largest $n$ such that $n\lg(n) \leq 10^6$

texts:
I'm studying CLRS, and solving problems listed after each chapter. I'm curious about problem 1-1. That is right after Chapter 1.

The question is, what is the best way to find the largest integer $n$ such that $n \lg(n) \leq 10^6$.

The simplest but the longest one is substitution. Are there some elegant ways to solve this?

Some explanations: $n$ is what I should calculate - total quantity of input elements, $10^6$ - time in microseconds - total algorithm running time. I should figure out $n_{\text{max}}$.


texts: Can languages with infinite strings be recursively enumerable?

texts:
I am not 100% sure about the definition of recursively enumarable languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but it does not have to halt on different inputs.

But suppose I have a language consisting of uncountable size with words of infinite length. Will Turing machine halt with a word of infinite length?

Consider a language constisting of all binary strings (I can produce such a set by diagonalization - Cantors rule, for example). Is this language recursively enumarable? If so, can you tell me why? I have not found any definition of this that would explain the behavior of TM with such inputs...


texts: Why does decreasing the gap size in Shell sort never undo previous sorts?

texts:
I came across this sentence in the Wikipedia article on Shell short, which states that

  If the file is then k-sorted for some smaller integer k, then the file remains h-sorted.

I've seen this claim in other texts like Lafore as well, but I can't wrap my head around why it's true.  Of course I can't find a counterexample, but why must it be so?


texts: Reversing topo-order of the original graph instead of the topo-order of the transposed graph?

texts:
(Note that my question is different from this one, I understand why we have to do a dfs on a reversed graph, I want to understand why we can't reverse the topological order instead of transposing the graph.)

In Kosaraju's algorithm, it is stated to compute the transposed graph and apply topological sort on it. I understand why this is necessary.

What I don't understand is the necessity to actually compute the transposed graph. Can't we just apply the topological sort algorithm on the original graph and use the resulting list in reverse order?

In Dasgupta,Papadimitriou, Vazirani, one can read

  There is not an easy, direct way to pick out a node that is guaranteed
  to lie in a sink strongly connected component.

I am having trouble to see why. If I apply a explore on any node of the following graph, the first finished node will be one of inside a sink strongly connected component.

Wikipedia's description of the algorithm seems to confirm this. The first DFS prepends instead of appending.

Can someone show an example (if any) where using the reversed topological order of the original graph instead of the topological order of the transposed graph is wrong?


texts: Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time

texts:
We have an undirected simple connected graph with odd number of vertices. We also know the number $k$ which is actually the closest odd number greater than or equal to $\Delta$. (So if $\Delta$ is even, $k = \Delta +1$ else $k=\Delta$.) i.e $k$ is the least odd number that is greater than or equal to degrees of all vertices.

We want to find a linear time algorithm that colors the graph with $k$ colors.

I am very new to graph coloring algorithms. I know that a greedy algorithm is actually linear time and can color the graph with $\Delta +1$. But I can't guarantee I can color it with $k= \Delta$ when $\Delta$ is odd.
Also, we probably should use all the information the question gives us. i.e using odd number of vertices somehow, but greedy algorithm don't use this extra information.

How can I solve this?


texts:
This comes from trying to understand the "Simon's algorithm".

So we have a set of $2^n$ kets $|x_i \rangle$ one each for $i \in \{0,1\}^n$. Each $x_j \in \{0,1\}^n$. And we have the further constraint that $x_i = x_j$ iff $i = j + s \pmod{2} = j \oplus s$ (bitwise addition modulo $2$) for a certain $s \in \{0,1\}^n$. (so every $|x_k\rangle$ is guaranteed to have a second copy)

Now one has this state given as $\psi_a = \frac{1}{\sqrt{2^n}}\sum_{i \in \{0,1\}^n} |i\rangle|x_i\rangle $ So this is a state of some 2 qubit system.

Given this I want to understand why a measurement on the second qubit would necessarily collapse this to the state, $\psi_b = \frac{1}{\sqrt{2}} ( |j\rangle + |j \oplus s\rangle)|x_j\rangle$ for some $j \in \{0,1\}^n$?

Is this measurement of the second qubit state trying to measure some observable/Hermitian operator whose eigenstates are precisely these $\psi_b$s? Then it would make some sense that the only things one sees are these $\psi_b$ states.

But this would still not clarify the weird probability addition that is happening here as shown below.

One notes that the state $\psi_b$ will be obtained with a probability of $(\bar{\psi_b} \psi_a)^2 = (\frac{ 2}{ \sqrt{2^{n+1} }})^2 = 1/2^{n-1}$. These $\psi_b$s obviously do not span the entire $2^{2n}$ dimensional Hilbert space available to these two qubits. They are not a basis.

But the probabilities don't add up rightly either $\sum_b ( \bar{\psi_b} \psi_a )^2 = 2$. Wonder is the interpretation of the fact that the probabilites over all these possibilities seem to add up to $2$!
Some explanations I found say that these states $\psi_b$ being the only possibilities is forced because of the fact that the second qubit is being measured in the "computational basis". This argument is not clear to me.


texts: Moving objects onto a line segment so that their pairwise similarities are close to their pairwise distances on the line

texts:
I have some arbitrary pairwise similarity metric for some objects, and I am considering trying to find the best way to position the objects onto a line segment such that the pairwise euclidean distances between points on the segment are best representative of the pairwise similarities between the objects. The application is for part of an experimental visualization technique.

As an optimization problem, maybe it could formulated something like this?

$$argmin_f \sum_{e_1, e_2 \in E} | \frac{ S(e_1,e_2) } { \max_{ a, b\in E }S(a,b) }-|f( e_1 ) - f(e_2)||$$
$$f: E \longrightarrow [0,1] $$

In short, if two points are close on the line segment, they should be similar. Is this an existing problem that people have studied? Anyone know anything about it?


texts:
my doubt is

what is the difference between transition function (delta) and extended transition function  (delta cap ) in finite automata ?

both of them when started at a state q for a string w will lead to same sate p what is the difference

  is transition functions gives the transition over an input alphabet ,
  where as the extended transition symbol gives a transition for the
  string w using the transition function?


texts: Show that a language belongs to the polynomial hierarchy

texts:
I think the following exercise is to "warm up", but nevertheless it's quite difficult for me:

  Let $k \in \mathbb{N}$ and let $L \in \Sigma_k$. Show that also $L^{*} \in \Sigma_k$.

The following details from my lecture notes seem to be useful:

Notation. Let $n \in \mathbb{N}$.

We write $\exists_n y. \varphi(y)$ for $\exists y \in \Sigma^{*}.|y| \le n \wedge \varphi(y)$.

We write $\forall_n y. \varphi(y)$ for $\forall y \in \Sigma^{*}.|y| \le n \Rightarrow \varphi(y)$.

Theorem.

$L \in \Sigma^P_i \Leftrightarrow$ there is a language $A \in P$ and a polynomial $p$ so that: $x \in L \Leftrightarrow \exists_{p(|x|)}y_1 \forall_{p(|x|)}y_2 \exists_{p(|x|)}y_3 .../\forall_{p(|x|)}y_i (x,y_1,y_2,...,y_i) \in A$

Unfortunately I don't see the solution of the "puzzle". Can somebody please help me a little bit (despite the fact that it's weekend)?


texts: A survey on ranking keyword search results

texts:
To rank the keyword search results, I'm trying to crack the way the Airbnb algorithm or similar ones work. I'm not asking which features they are using since those are different depending on the business needs. What I'm asking is where can I find a paper/survey/book to see what are the various relevancy metrics in addition to TF-IDF and PageRank? and how can I merge various metrics/algorithms into a single algorithm to sort the search results?

Input: a couple of keywords
Output: a ranked list of options relevant to the input keywords

Anything from links to surveys/books/algorithms/open-source software would work.

Best


texts: Is the Tomasi-Kanade factorization still commonly used as a modern computer vision technique?

texts:
My understanding is that, in very rough terms, the Tomasi-Kanade algorithm published in 1992 describes a way to reconstruct the 3D structure of an object from multiple images of that object, given that you have a reliable method of identifying important structural features from the 2D images.

A lack of general information on the topic has prompted me to ask this question: is this method deployed in any recent computer vision systems? Has it been followed up by other methods? Finally, if anyone would like to suggest any resources containing background information that are helpful in digesting the paper, please do. Despite being familiar with the mathematics, I had a hard time making any sense of it.


texts: Derivation of product type eliminator in type theory

texts:
In HoTT book, section 1.5 (Product Types) in order to define the eliminators for the product type it assumes a function of type $g:A \rightarrow B \rightarrow C$ and then goes on to define the eliminator rule ,saying that we can define a function $f:A \times B \rightarrow C $ for any such g by:

$f((a, b)) :\equiv g (a) (b)$.

Then it states that

  Note that in set theory, we would justify the above definition of $f$ by the fact that every element of $A \times B$ is an ordered pair, so that it suffices to define $f$ on such pairs. By contrast, type theory reverses the situation: we assume that a function on $A \times B$ is well-defined as soon as we specify its values on pairs, and from this we will be able to prove that every element of $A \times B$ is a pair.

Would you please explain in further detail what the above paragraph is trying to state?


texts: Find vertices of a convex polytope, defined by intersecting half-spaces

texts:
I am looking for a algorithm that returns the vertices of a polytope if provided with the set of intersecting half-spaces  that define it.

In my special case the polytope is constructed by the following constraints on $x \in \mathbb{R}^d$:

$\sum_i x_i = 1$ (i.e., $\|x\|_1 = 1$).
$0 \le a_i \leq x_i\leq b_i \leq1$, where the $a_i,b_i$ are given

This can either be thought of as the intersection of the hyper-plane (defined by the first constraint, in combination with the range restriction of the second constraint) with a hyper-cube (defined by the second constraint) or as the intersection of half-spaces where the first constraint is the intersection of two half-spaces that only intersect on a hyper-plane.

This always generates a convex polytope, if I am not mistaken, as long as the intersection creates a bounded set.

I would like to have an algorithm that returns the set vertices of the polytope if provided with the set of $a_i$'s and $b_i$'s.

There is a special case where there exists no $x$ that satifies this condition. Ideally, this would be picked up on.
Therefore, I would wish for an algorithm that checks if such a polytope exists and if so returns the vertices.


texts: Does an optimal path imply the heuristic is admissible?

texts: If we are given an A$^*$ path search with some heuristic $h$ that yields an optimal path, without knowing that the heuristic is admissible beforehand, would this imply that $h$ is admissible?


texts: Languages that satisfy the pumping lemma but aren't regular?

texts: Given a regular language $L$, then it is easy to prove that there is a constant $N$ such that is $\sigma \in L$, with $\lvert \sigma \rvert \ge N$ there exist strings $\alpha$, $\beta$ and $\gamma$ such that $\lvert \alpha \beta \rvert \le N$ and $\lvert \beta \rvert \ne \epsilon$, and for all $k$ it is $\alpha \beta^k \gamma \in L$. It is widely stated that the converse isn't true, but I haven't seen any clear example. Any suggestions? Clearly the proof that the offending language isn't regular has to use stronger methods than the typical "doesn't satisfy the pumping lemma". I'd be interested in simple examples, to present in introductory formal languages classes.


texts: Can we build a nondeterministic decider PDA using two PDAs accepting a language and its complement?

texts:
When talking about turing machines, it can be easily shown that starting from two machines accepting $L$ and its complement $L^c$, one can build a machine which can fully decide if a word is inside $L$ or not.

But what about PDAs? starting from two different PDAs, one accepting $L$ and one accepting $L^c$ can we build another PDA, which accepts $L$, and only crashes or halts in non-final states (rejects) when $w\notin L$?


texts: Could we design a Turing machine that output every bit of $\pi$ one after another correctly with limited tape length?

texts:
Could we design a Turing machine that output every bit of $\pi$ one after another correctly?

I think we have computer programs that calculate the value of $\pi$ day after day, and thus it's viable.

Could we do that if the Turing machine has a limited tape length?


texts: Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem

texts:
Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence

$$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$

by applying the Master Theorem.

I am very confused by how it is done. So, $a=3, b=4, f(n) = n\cdot \log(n)$
First step is to compare $n^{\log_b a} = n^{\log_4 3}= O(n^{0.793})$ with $f(n)$.

I have no clue on how they compared this. The book explains:

  $f(n) = \Omega (n^{\log_4 3+\epsilon })$, where $\epsilon \approx 0.2$, case 3 applies if we can show that the regularity condition holds for $f(n).$

Followed by:

  For sufficiently large n, we have that: $af\left(\frac{n}{b}\right) = 3\left(\frac{n}{4}\right)\log\left(\frac{n}{5}\right) \le\left(\frac{3}{4}\right)n \log n = cf(n)~ for~ c=\frac{3}{4}.$

Where did $3\left(\frac{n}{4}\right)$ come from?


texts: Coding Theory Optimal Code with given max length

texts:
Why do we need at least 2 Code Words of the max length in optimal Codes?

Any why do they just differ in their Prefix?

Could someone give me more insight into this?

Have to proof that for a given optimal Code C with max length L there are at least 2 Code Words of max length that just differ in their prefix.

I have nothing to start so some start would be good.

I have no given definition of optimal Code in my script and I don't know if it has to be a block code that I see in most definitions.


texts: Computational complexity for more general problems

texts:
When I read computational complexity I encounter problems like 3-SAT, set cover, knapsack. In the first two variables are discrete. In knapsack the weights and values are integer and all three problems have a combinatorial structure, what I mean is selecting a finite number from a finite set.

How about problems in continuous domains like finding the minimum or maximum of a function in real numbers? Or solving a differential equation to find a function? Can we prove that these problems too are hard or easy in a computational complexity sense?

Finally how do I know, by looking at a problem, if asking "is the problem NP-hard?" is a valid question?


texts:
I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript.

I was thinking especially about the node insertion method. Here's my implementation:

class BinaryTree {
// ... initialization
add(val) {
    if(this.root === null) {
        this.root = new Node(val);
        return ;
    }
    this.addNode(val, this.root);
}
addNode(val, node) {
    if(!!!this.comparator) throw new Error('this.comparator cannot be undefined.');
    let comp = this.comparator(val, node.val);
    if(comp === -1) {
        if(node.left === null) {
            node.left = new Node(val);
            return ;
        }
        this.addNode(val, node.left);
    }
    else if(comp === 1) {
        if(node.right === null) {
            node.right = new Node(val);
            return ;
        }
        this.addNode(val, node.right);
    }
}
// ... other methods
}

where this.comparator = (v1, v2) => { return (v1 <= v2) ? -1 : 1; };

My questions are:

Is there a way to modify this add method such that it can balance the tree after every addition?
If so, by factor would the time complexity of add be growing?


texts:
I thought about this problem for a while now and am not able to find a solution for it, be it a direct algorithm or a reduction to a known problem, so I'm asking here:

Suppose you have a matrix $A\in\mathbb{N}^{n\times m}$ with integer entries. I want to partition the columns of $A$ into $k$ groups (or $k$ matrices), such that the sum of the minima of every row in each group is minimized. To illustrate: Suppose
$$
A = \left[
\begin{array}{ccccc}
   1 & 2 & 3 & 4 & 5\\
   3 & 4 & 5 & 6 & 7\\
   6 & 5 & 4 & 3 & 2\\
\end{array}
\right]\text{ .}
$$

If I partition the columns into the following three matrices
$$
A_1 = \left[
\begin{array}{cc}
   \color{red}1 & 2 \\
   \color{red}3 & 4 \\
   6 & \color{red}5 \\
\end{array}
\right],\qquad
A_2 = \left[
\begin{array}{ccccc}
   \color{red}3 & 5\\
   \color{red}5 & 7\\
   4 & \color{red}2\\
\end{array}
\right],\qquad
A_3 = \left[
\begin{array}{ccccc}
   \color{red}4\\
   \color{red}6\\
   \color{red}3\\
\end{array}
\right],
$$

the "score" would be $(1+3+5)+(3+5+2)+(4+6+3)=32$, the sum of all the red entries (which are the minimal entries in each row).

Also, there is a given minimum size $M$ for the groups, so each group must have at least $M$ columns.

Is there any feasible algorithm for minimizing this?


texts: DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?

texts:
https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php

The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile.

Question 1) In the recursive formula for g(n):

g(n) = f(n-1) + h(n-1)

Why didn't we include the case that we can also put a 2x1 tile horizontally on the top row. Something like -

g(n) = f(n-1) + h(n-1) + x(n-3)

where f(n) = f(n-1) + f(n-2) + g(n-2) + h(n-2) still holds.

Basically, are we not looking into the cases how we can start tiling from the state g(n) ? ither we add an L-shaped tile, and look at f(n-1), or we add a 2x1 tile in the bottom layer and look at h(n-1), or add a 2x1 tile in the top layer and look at x(n-3) ?

Question 2) It seems like while writing the recursion, we should only deal with cases that we have already named, i.e. only moving from state g(n) to h(n-1) or moving from state g(n) to f(n-1) ? Is it true, that when once we have decided which states to deal with, we only consider those states?


texts: Algorithm to create balanced teams based on multiple criteria

texts:
I don't know if this is the right place to ask this, but here goes:

I have a set of players in 3 age groups.  Each player has the attributes:

gender
mental skill (1-10)
physical skill (1-10)
age group (1-3)

I want to sort them into 14 teams that have balanced "stats", as in each team has (or as close as possible):

same number of players on each team
same number of each gender as each other team
same average mental skill
same average physical skill
for each age group, same number of players from each age group on each team

What sort of algorithm or method would I use to do this?  An example in python would be great.

As a follow up:

I want to hand-pick two members for each team and have them fixed, how would I build the rest of the teams around that in order to meet the balanced team criteria? Thanks in advance


texts: How to prove that $n^2$ is not $o(n^2+10^{10}n)$?

texts:
I need to prove that $n^2$ is not $o(n^2+10^{10}n)$. I thought of the limit test:
$$
\lim_{n \to \infty} \frac{n^2}{n^2+10^{10}n} = 1 \Rightarrow n^2 = \Theta(n^2+10^{10}n)
$$

However I'm not sure if the result of the test rules out the possibility of $o(n^2+10^{10}n)$.


texts: Implementation of caches on CPUs with pipelines

texts:
I've read that some current CPUs (e.g. Intel i7 and ARM A9) have (L1) cache latencies of multiple clock cycles while also being pipelined. Some devote multiple pipeline stages to instruction fetching.

How is the L1 cache implemented to support pipelining?

Is it, say, $k$ actual stages for decoding the address or does it use some asynchronous multiport logic with a datapath latency set to $k$ clock cycles?


texts: Lower bound for number of nonterminals in a CFG

texts: Let's say we have a context-free grammar for the language $a\mbox{*}b\mbox{*}c\mbox{*}$.  Is there a way to determine a lower bound for the number of nonterminals in this grammar?  I'm pretty sure you need at least 2, but I haven't been able to prove it.


texts: Sum number of times statement is executed in triple nested loop

texts:
I have this code fragment:

for( i=0; i<n; i++ )
    for( j=0; j<i; j++ )
        for( k=0; k<j; k++ )
            S;

I need to find the number of times that S is executed in that code block. I plugged it into Wolfram Alpha but I am not sure if that is the right answer.

I want to be able to do the math in order to figure the answer out so can someone point me in the right direction?


texts: Finding the kth smallest element of an array using DAC

texts:
I'm trying to find the $k^{th}$ smallest element of an array by using Randomized Quicksort, But below code giving erroneous result can anybody help.

from random import randint

lst=[1,3,5,2,4,6]
k=6
n=6

def swap(i,j):
    t=lst[i]
    lst[i]=lst[j]
    lst[j]=t

def rand_partition(p,q):
    # i is the pivot position
    i=randint(p,q)
    while(p<q):
        if(lst[p]>lst[i]):
            swap(p,p+1)
            p+=1
        else:
            p+=1

    swap(p,q)
    return q

def select(p,q,k):
    r = rand_partition(p,q)
    t = r-p+1

    if(k==t):
        return lst[r]
    elif(k<t):
        return select(p,r-1,k)
    else:
        return select(r+1,q,k-t)

res=select(0,n-1,k)

print('%dth Smallest Element = %d' %(k,res))


texts: recursive language and computable function

texts:
Question: Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x \in A^{*}$, always halts with $f(x)$ on its tape. Let $L_{f}$ denote the language $\Bigl \{x\# f(x) \mid x\in A^{*} \Bigr \}$. Which of the following statements is true:

(A) $f$ is computable if and only if $L_{f}$ is recursive.

(B) $f$ is computable if and only if $L_{f}$ is recursively enumerable.

(C) If $f$ is computable then $L_{f}$ is recursive, but not conversely.

(D) If $f$ is computable then $L_f$ is recursively enumerable, but not conversely.

My Attempt:

if $f$ is computable then given $x$ on tape of TM, it will always halt in $f(x)$ on Tape.

$L_f$ denote the language $\Bigl \{x\# f(x) \mid x\in A^{*} \Bigr \}$, which means $L_f$ strings of type which has image and pre image to left and right of $\#$.

Now consider a function $f(x)$ is computable and its corresponding language $L_f$, will $L_f$  be recursive ? (given that $f(x)$ is computable )

Yes, $L_f$ wil be recursive if $f(x)$ is computable. Because if $x\# f(x)$ is given then i will first convert $x$ in $f(x)$ (i can do it because $f(x)$ is computable ) this gives me $f(x)\# f(x)$ on table and i just left to match left strings to the right string of $\#$ .

Now consider a function $L_f$  is recursive, will $f(x)$ be computable ?
(i need exlanation of this part)


texts: Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$

texts:
Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and assigning the $i$th string $x_i$ to number $i \in \mathbb{N}$.
But given strings $x_i,x_j \in \Sigma^*$, is there any special mapping such that the concatenation operation $f:\Sigma^* \rightarrow \Sigma^* | (x_i,x_j) \rightarrow x_ix_j$ is also related to the usual addition performed over the corresponding indices $i,j \in \mathbb{N}$ to which $x_i$ and $x_j$ are mapped ?
For instance, if I assign the character $\{1\}$ to the number $1$, and string $x$ is assigned the number $10$, is there a mapping such that the string $x1$ is assigned the number $11$ ? (i.e. $10 + 1$)


texts: Registers of Control Unit and Arithmetic Logic Unit

texts:
For an Instruction fetch cycle we have the flowing registers in a CPU.

Memory Address Register (MAR)
Memory Buffer Register (MBR)
Program Counter (PC)
Instruction Register (IR):
Accumulator Register:
Stack Control Register:
Flag Register:

Out of these I have come to know that PC and IR registers belong to control unit and accumulator belong to ALU but I do not know about rest of the registers. Either they also belong to CU or ALU or they exist separately not as apart of ALU OR CU ?


texts: Why RAID 2 would ever be used instead of RAID 3?

texts:
According to this source and Tanenbaum's Modern Operating Systems a possible implementation of RAID 2 consists of 4 data disks and 3 disks which contain parity bits. Why don't we need 4 disks that stores parity bits, why just 3?

Also in RAID 3 we need just one disk for storing parity bytes for 4 data disks. What would be any potential interest in RAID 2 over RAID 3? As far as I understand read/write speeds are the same in RAID 2/RAID 3.


texts:
Problem
I've got this function:
$f(x,y)=(6-3\cdot x)\cdot(y+2)$, with $(x,y)\in\mathbb{N}^2$
Now I have to find $g=\mu f$.
Proposed solution
My solution was to find the smallest $n\in\mathbb{N}$ to find $f(n,y)=0$ and show that $\forall 0\leq m\leq n : f(m,y)$ is defined:
$f(0,y)=(6-0)(y+2) = 6y+12$, defined $\forall y\in\mathbb{N}$
$f(1,y)=(6-3)(y+2) = 3y+6$, defined $\forall y\in\mathbb{N}$
$f(2,y)=(6-6)(y+2) = 0$, defined $\forall y\in\mathbb{N}$
So I've found $g=\mu f=2$.
Questions

Is above solution correct?
Is it always the first parameter that becomes $n$?
If $f(x,y)=(6-3\cdot x)\cdot(y-2)$ and $f(0,y) = (6-0)(y-2) = 6y-12$, wouldn't be $f(0,y)=0$, if $y=2$ and therefore my $n=0$ for this $y$, but for other $y$, my $n$ would be different?


texts: Why doesn't this derivation of the margin in a SVM give the correct result?

texts:
I'm trying to derive the optimization objective for an SVM (namely $1/\|w\|$), but I'm running into a little trouble. I've already read this question, which has certainly offered a lot of insight into the problem, but I would like to know why my own derivation doesn't quite work.

So essentially, let's say our support vectors on either side of the decision boundary are $\vec x_+$ and $\vec x_-$. Suppose the decision boundary itself is $\vec w\cdot\vec x + b = 0$. We have $\vec w\cdot x_\pm + b = \pm 1$. Now, the margin $d$ can be calculated as the sum of the distances between the points $\vec x_\pm$ and the decision boundary. We can use the typical projection formula to obtain

$$
\begin{aligned}
d & = \left\|\vec w\frac{\vec x_+\cdot\vec w}{\vec w\cdot\vec w}\right\| + \left\|\vec w\frac{\vec x_-\cdot\vec w}{\vec w\cdot\vec w}\right\| \\
& = \frac{\|\vec w\|}{\|\vec w\|^2}(|\vec x_+\cdot\vec w| + |\vec x_-\cdot\vec w|) \\
& = \frac1{\|\vec w\|}(|1-b|+|1+b|)
\end{aligned}
$$

This is almost the correct result, and in fact if we restrict $b\in[-1, 1]$, $d$ reduces to $2/\|\vec w\|$ as expected. However, in general this can be written:
$$
d = \frac{2\max(1,|b|)}{\|w\|}
$$
So my question essentially is why did I end up with the extra b in the numerator? Does it change the optimization objective at all (I feel like it does)? Is there a reasonable explanation for why we could potentially restrict $b\in[-1,1]$?


texts: Is there a computationally reasonable algorithm for generating a set of polygons from a set of 2d points?

texts: Is there a known/existing algorithm for taking a 2D canvas covered in  arbitrarily/randomly distributed points and dividing it entirely into a set of non-overlapping polygons? An example of the kind of result I'm looking for:


texts: The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?

texts:
My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

I understand the argument of the answer above. Also the answer is given in this book ''The Desing of Approximation Algorithms'' that I am reading. In [pp. 67, §2], the authors said:

  Algorithm 3.1 takes $O(n\cdot \min(B, V))$ time. This is not a
  polynomial-time algorithm, since we assume that all input numbers are
  encoded in binary; thus, the size of the input number  $B$ is
  essentially $\lg B$, and so the running time $O(n\cdot B)$ is
  exponential in the size of the input number $B$, not polynomial.
  $\cdots$

I understand that $O(n\cdot B)$ is exponential in the size of the input number $B$, but also, in my point of view (which is wrong), $O(n\cdot B)$ is exponetial in the size of the input number $n$, i.e., the size of the input $n$ is $\lg n$. Why not? (If I were to represent $n$ in binary I would take $\lg n$ size, no?)


texts:
The tit-for-tat strategy is a well-known strategy that can be applied, for example, in the Iterated Prisoner's Dilemma (IPD). Roughly, the idea is that you always repeat what the opponent did in the previous round.

I was wondering, does there exist a name for the opposite of a tit-for-tat strategy? That is, a strategy in which you always do the exact opposite of what your opponent did in the previous round.

Of course, in the IPD such a strategy wouldn't make any sense, but there may be other games where it does. Any links to papers that have investigated such strategies are welcome.


texts: Understanding non-linear dimensionality reduction algorithm (locally linear embedding)

texts:
I have a question about Locally Linear Embedding. I am trying to study this algorithm and implement it for better understanding. I have read An Introduction to Locally Linear Embedding. However, I don't think I really understood this algorithm. There are several questions I want to ask.

I understand that this algorithm takes some high dimensional data set and reduce it into lower dimensional data set while keeping some geometric features of the original data set. In the article, they use S-shape manifold, sample data from the manifold and reduce it into lower dimension. So I see from the picture that each region on the manifold specified by colors are conserved. But I don't think I understood why do we need this kind of reduction. I don't think it is guaranteed that any data set can be reduced to two or three dimension so that we can visualize the original data set which means how the geometric features are conserved. Can anyone explain this with some example?
I don't really understand how this algorithm can be implemented. The paper shows the reconstruction error $\epsilon(W)=\sum_i \left| X_i - \sum_jW_{ij}X_j \right|^2$ and saysThe weights summarize the contribution of the jth data point to ith reconstruction. I don't understand what this sentence means and how the weight matrix $W_{ij}$ can be constructed. Each $X_i$ represents each column in the data?? Then how can I understand $\sum_jW_{ij}X_j$?? Can anyone explain this?
The paper says that the data reduced into lower dimension can be constructed by the closest points of each data points. How is this work?

Thank you


texts: Number of calls with length 2 array in quick-sort

texts:
I need to find average number of recursive calls in quick-sort with array of length 2. I established and solved the following recursion:

$$T_N = \frac{1}{N}\sum_{k=1}^N\left(T_{k-1}+N_{N-k}\right) = \frac{N+1}{N}T_{N-1} = \frac{N+1}{3}.$$

Where $T_0 = T_1 = 0, T_2 = 1$. But:

\begin{align*}
T_3 &= 1/3(1 + 1) &= 2/3\\
T_4 &= 1/4(2/3 + 1 + 1 + 2/3) &= 5/6\\
T_5 &= 1/5 (5/4 + 2/3 + 2 + 2/3 + 5/4) &= 7/6\\
T_6 &= 1/6(7/6 + 5/6 + (1+2/3) + (1+2/3) + 5/6 + 7/6) &= 11/9
\end{align*}

The results are different. How to do it right?

EDIT: The code for quick-sort in question is:

void quicksort(int[] a, int lo, int hi)
{
  if (hi <= lo) return;
  int i = lo-1, j = hi;
  int t, v = a[hi];
  while (true) {
    while (a[++i] < v) ;
    while (v < a[--j]) if (j == lo) break;
    if (i >= j) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
  }
  t = a[i]; a[i] = a[hi]; a[hi] = t;
  quicksort(a, lo, i-1);
  quicksort(a, i+1, hi);
}


texts: Is there any reason why the modulo operator is denoted as %?

texts:
I would like to know if there is any reason why many programming languages use the notation % for the modulo operator?
It is used in the most "famous" languages:

C
C++
C#
Go
Java
Julia
Lua
Perl
Python


texts:
I know that the general consensus among CS researchers is that non-relativizing techniques will be needed to separate P and NP.  However, if there is an oracle language $A \in \textbf{P}$ such that ${\textbf{P}}^A \neq {\textbf{NP}}^A$ would that necessarily imply ${\textbf{P}} \neq {\textbf{NP}}$?  I read somewhere that it would be enough, but I'm not sure.

On the one hand, since any NDTM can be supplemented with a polynomial-time deterministic subroutine for $A$, having oracle access to it should not give an NDTM any more "power".

On the other hand though, aren't oracle TM's able to make queries about strings of any length in the oracle language?  In that case, we could not jump to the conclusion that P does not equal NP, because according to my understanding, polynomial-time Turing machines (whether deterministic or non-deterministic) cannot be "influenced" by strings of length exponential in the length of the input string.


texts:
I have been thinking about the following problem:

Let $J$ be a set of jobs that need to be performed. Each jobs comprises of some number ($>1$) of tasks, and a job is considered finished when all of the tasks have been completed. Find an ordering to perform the tasks such that the sum of the maximum time needed to finish each job is minimised. Assume that the time needed to finish each task is unary and that the time to finish each job is the time that passes from when one of the tasks of the job starts until the last task of the job finishes.

For example:

Suppose we have 3 jobs: $J_1 = \{a,b,c\}$, $J_2 = \{b,d\}$ and $J_3 = \{a,c\}$, where $a,b,c,d$ are tasks. An optimal ordering for this set of tasks is $a-c-b-d$ because the time needed to finish $J_1$ is 2, the time needed to finish $J_2$ is 1 and the time needed to finish $J_3$ is also 1. In total, the maximum time $t$ to finish all jobs is 2+1+1 = 4.

An example of a bad ordering is $b-a-c-d$ would result in $t = 2+3+1 = 6$

I was thinking that maybe I could use dynamic programming to find an optimal ordering but ultimately I cannot do any better than ending up checking every possible order. Is there any trick to finding optimal orders or are there any related problems I could study?


texts: Is there a complexity metric for digital circuits?

texts:
Let's say that I have a digital circuit made up of XOR and AND gates.

Is there any way to describe the complexity of that circuit?

I could just use the total number of gates, but gates being in parallel are not quite the same thing as them being in series when things like latency are concerned.

Also, if at all relevant to an answer for the above, in my particular case, AND is much more costly of an operation than XOR (AND is multiplication where XOR is addition), so should be waited more heavily ideally.

If that last constraint doesn't fit into an established complexity metric for circuits, that is totally fine, and I'm still interested in an answer without that information taken into account.

Thanks!!


texts: Asymptotic growth rate of $f(n)$ and $f(n+1)$

texts:
Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a continuous positive function, where $f(n)$ is integer for each integer $n$. Prove or disprove whether the following always holds:

$\qquad f(n+1) = \Theta(f(n))$


texts: Where is the OS when a process is running?

texts:
We know that operating system is responsible for handling memory allocation, process management etc. CPU can perform only one task at a time(assuming it to be single core). Suppose an operating system has allocated a CPU cycle to some user initiated process and CPU is executing that. Now where is operating system running? If some other process is using the CPU, then, is operating system not running for that moment? as OS itself must need CPU to run. If in case OS is not running, then who is handling process management, device management etc for that period?

This question was previously asked on Stack Overflow by vish. I answered it, and so did Martin James, and our answers feel partly contradictory.


texts: How to replace one symbol with two on Turing machine's tape

texts:
I want to implement following algorithm on Turing machine:

  rewrite binary numbers to their unary counterparts. For example: 101
  will be rewritten to a string of 5 consecutive bars

(wikipedia)

But I don't know how to make the replacement "|0" -> "0||" because it requires 3 cells. Basically I want to insert additional cell or shift all cell symbols from current position to the left(right). Is there a simple way of doing it?


texts:
Has there been any attempt to systematically categorize programming puzzles?

I notice that some problems are similar to one another, or have analogous methods of solution. I would think there must be some way to categorize them, so that you could in a sense look up methods of solution if you knew what category it was in. For example, some problems reduce to finding one string in another.

The closest thing I have seen to this is in Garey and Johnson (1975) in which book there is a list of known NP-complete problems. So, if you can reduce a problem to one of the 200 or so examples they give, you know the problem is NP-complete. I have not seen a general attempt to classify all problems however, except maybe Skiena's book, The Algorithm Design Manual.


texts: Algorithm for assigning people to groups

texts:
Given a list $L = [1, 2, .., n]$ and a list $C = [(L_i, L_j), ....]$ form a group of pairs $G = g_1, ..., g_{n/2}$ such that:

every element of $L$ is assigned to exactly one group
$g_k = (L_i, L_j) \Rightarrow (L_i, L_j) \notin C $ (constraint)

I get that there are (potentially) many solutions to this problem.
How can one construct a recursive algorithm $group(L, C)$ to that returns a possible grouping?
I get that you can: 1) Create all pairs from $L$ and 2) Create all possible groups of size $n/2$ from the pairs and select one group that is legal.
I see that there are $N_P = {N\choose 2} = \frac{n!}{2!(n-2)!}$ potential pairs in $L$. The number of groups is then ${N_P\choose N/2} = \frac{N_P}{(N/2)!(N_P-N/2)!}$
Then one has to go through all these groups and check if it is legal and return it if so.
Any other solutions?


texts: Can a DFA have an empty string as input?

texts:
Given string w such that every odd position in w is a 1

My solution is

The book's solution is

from my understanding $\epsilon$ should not be an accepted state, however in the book's solution it is. How is it handling this case?


texts:
What is a contiguous subarray? I have tried searching online and have found pages about solving the largest contiguous subarray problem but none with a definition or explanation of what contiguous in this actually is.

Ex: Wikipedia: Maximm subarray problem has no explanation of why the given "subarray" is contiguous or what contiguous means in the context.


texts: minimum and maximum nodes of MultiWay tree of height h

texts:
I know that it doesn’t have to be balanced so in theory given that the height of
the tree is $h$, the minimal number of nodes is obtained when each node has 1 key and 1 child, and since the first level "doesn’t count" in the height, I should have $h+1$ nodes.

The maximal number of nodes in a $M-way- tree$ should be $\Sigma^h_{i=0}  M^i$, when $i$ is the tree level.

Is this correct ? Thank you!


texts: What is the computational complexity category of $T(n) = m^{\frac{n-1}{m}}$?

texts:
I'm analyzing the computational complexity of an algorithm whose input size is $n$. Finally, I've ended up with
$T(n) = {m^\frac{n-1}{m}}$ where $m$ is a constant. Can one explain the type name corresponding to this computational complexity (e.g., exponential, etc.)?


texts: Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

texts:
I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part of the input). Note that this is different from the problems of MINCUT and MAXCUT which simply ask to find the minimum and maximum sized cutsets.

For general graphs, the MINCUT problem can be solved in polynomial time while the MAXCUT problem is NP-Hard. It follows that deciding if a cutset of a particular size exists in a general graph is also NP-Hard since we could use it to find the maximum sized cutset.

For bipartite graphs however, the MAXCUT problem is trivial -- all the edges in the graph constitute the MAXCUT. Moreover, if it helps, I think I can show that for bipartite graphs, the edge - complement of a cutset is also a cutset. That is if $E_c \subseteq E$ is a cutset of a bipartite graph $G = (U\cup V, E)$ then $E-E_c$ is also a cutset of $G$.

However, I have not been able to determine if deciding if a cutset of some size $k$ exists is in P or is NP-Complete or something else. If it is Np-Complete, is there a family of graphs for which it is in P? Any pointers will be helpful.


texts: Computer Architecture-3 level RAM hierarchy

texts: In all computer architecture books we study that Cache memory could be divided into 3 levels (L1,L2 and L3) and its very beneficial to do so. Why don't we use the same approach in case of main memory (RAM). Is there any particular reason that we avoid this?


texts: In what sense can a cellular automaton be Turing complete?

texts:
The rule 110 cellular automaton is known (or claimed) to be Turing complete. But what exactly does it mean?

I do know what Turing completeness mean. Roughly speaking a language is Turing complete if any program / algorithm can be expressed using this language.

However, the rule 110 is a fixed set of instructions of how to modify a sequence of zero and ones. So, how can we express any program as a rule 110? If we change the rule 110 it will not be the rule 110 anymore?

I might guess that both the input sequence and the program itself should be encoded into a single sequence of the zeros and ones and then we need to run the rule 110 on it. At some point we will get a sequence that can be interpreted as the output generated by the given program for the given input. Is my interpretation correct?


texts: Clarification on the inapproximability of set cover

texts:
I'm trying to understand the inapproximability of the minimum set cover problem.

The wikipedia page states that it is hard to approximate within a factor of $(1-o(1))\ln n$ and that $n$ refers to the size of the ground set. It references the work of Dinur and Steurer (2013) who state that, for every $\varepsilon>0$, it is NP-hard to approximate min set cover within a factor of $(1-\varepsilon)\ln n$ where $n$ refers to the size of the instance. It seems they don't define what they mean by "size of the instance," but I take that to mean an encoding of the instance (which takes more space than just the size of the ground set).

Would I be correct in saying that set cover is hard to approximate within a factor of $(1-\varepsilon)\ln N$, where $N$ is the size of the ground set plus the sizes of all the subsets? Or, if $N$ is the size of the ground set plus the number of subsets?


texts:
Currently going through a video on Counting Minimum Cuts by Tim Roughgarden.
$(A_{i},B_{i}) = \big((A_{1},B_{1}), ..., (A_{t},B_{t})\big) \forall i \in \Bbb{R}$
$P\big((A_{i},B_{i})\big) \geq \frac{1}{\begin{pmatrix} n \\ 2 \end{pmatrix}} = p$, which I interpret as the lower bound on the probability of having at least one minimal cut.
In the problem set that follows two answers A and B are highlighted as being correct. I understand why A is correct; but am puzzled why B is also marked as correct.
A: For every graph $G$ with $n$ nodes and every min cut $(A,B)$ (I am assuming same thing as $(A_{i},B_{i})$) $P\big((A,B)\big) \geq p$.
B There exists a graph $G$ with $n$ nodes and a min cut $(A,B)$ (again assuming same thing as $(A_{i},B_{i})$) of $G$ such that $P\big((A,B)\big) \leq p$.


texts:
Assume language $L$ as follow:-
$$
L = \{ a^n b^x c^m d^y | (n=m) \lor (x=y)\}
$$
Is it possible to design DPDA/NPDA for this? I know if the condition would have been "and" then it is not possible. But is it possible with "or"?

My approach:- 1. Push all $a$'s to the stack.

At $b$ define non deterministic behavior as follow:-

2.1. Assume we are checking for $n=m$.So skip all the $b$'s.

2.1.2.Whenever $c$ is encountered, pop $a$ for $c$.

2.1.3. When $d$ is encountered check if stack is empty, if yes, then accept else reject.

2.2. Assume we are checking $x=y$. So push all the $b$'s to the stack. Now when $c$'s are  encountered skip them.

2.2.1. When $d$'s are encountered, count them with $b$'s which are on top of stack.

2.2.2. When input is finished and stack is empty or contains only $A$, then accept else reject.


texts:
Take a Turing machine, with a terminating program, convert it to some representation of the machine which captures, in a lossless manner, its state as it performs the computation.

So you have a complete representation of the machine, the program, and its internal organisation as it performs the computation.

I am going to suggest a graphical form, nodes and edges, names for nodes.

Take a second Turing machine with a slightly different program. This program is identical save that it performs a single unit of function from the first program in a non optimal way, say it performs the single unit 3 times, changing some value to the correct output the first time, taking it to some second result the second time and then finally returning again to the correct first result. Like a reflection.

Would it not be possible for some statistical technique to analyse the graph of the two machines including their process and find a compression of the graph of the second machine, which is smaller in terms of the size of the graph of its process and yet consistent with the mode of operation of the machine.

For instance a graph matching algorithm could find that there is a subgraph match between one portion of the the process graph of the first machine and one part of the process graph of the second machine and replace the subgraph of the second machine with the subgraph of the process of the first machine.

How it would then alter the program of the second machine to generate that altered graph I am unsure of.

Do such techniques exist? Where would I find them, or is the analysis flawed or incomplete in some way which prevents its operation? What should I learn to understand its implementation or the truth of its deficiency?


texts: Complexity of nearest codeword in cyclic codes

texts:
Is it $NP$-complete given $c(x),g(x)\in\mathbb{F}_2[x]$ where $g$ generates a cyclic code of length $n$ (so $g\mid x^n-1$), and $\deg c<n$ to find the nearest codeword to $c$?

This is related to the following problem in finite fields: given $\hat{g},\hat{x}\in\mathbb{F}_{2^k}$, find the sparsest polynomial $F\in\mathbb{F}_2$ such that $F(\hat{g})=\hat{x}$.


texts: Sum of Maximum of continuous blocks of length k

texts:
Given a array of N elements and a number k, then find the sum of maximum of a all continuous blocks of length k?

Examples :

A = {2,5,2}, k = 2, Max for 1st block = 5, 2nd block = 5, So sum is 10.
A = {3,1,8}, k = 2, Max for 1st block = 3, 2nd block = 8, So sum is 11.
A = {2,5,2}, k = 1, Max for 1st block = 2, 2nd block = 5, third block = 2. So sum is 9.
A = {2,5,2}, k = 3, Max for only block = 5. So sum is 5.


texts: Is generalized XOR-SAT efficiently solvable?

texts:
I've seen how XOR-3-SAT is efficiently solvable (for instance, see the "XOR-satisfiability" section in  the Wikipedia entry for Boolean satisfiability problem).

I'm wondering a basic question:  Is XOR-k-SAT efficiently solvable, for formulas with varying amounts of literals per clause?

I'd really like to know if we can increase the amounts of literals per clause beyond 3, and if we can have mixed clause lengths.


texts: Code and time complexity of multiplication à la française

texts:
This references the multiplication algorithm in Chapter 1 of Algorithms by Dasgupta et al.
I am trying to understand how the code for multiplication à la française works from the multiplication by hand. This is the example given.

This is the code given for it.

I went ahead and did multiplication of $13 \times 11$ (odd) case and $13 \times 10$ (even) in a spreadsheet and this is what I got.

It seems to me that in the code the rows of the columns are flipped with respect to handwritten example, that is, in $13 \times 11$, the 1 shows up where 13 is and not where 104 is as in the handwritten example. I still get the correct answer. Where did I make a mistake? In the evaluation or understanding the conversion from handwritten algorithm to algorithm in code.
I also have trouble seeing how to get $O(n^2)$ for the time complexity. I understand that there is bit shifting and addition and so at some point, assuming both $x$ and $y$ are n bits, we end up adding $1 + 2 + 3 + \dots + n = \frac{n}{2}(n+1) = O(n^2)$ but aren't we shifting the bits $n$ times and therefore need to multiply by another factor of $n$ to get $O(n^3)$?
This is what I get when I think of the equation for master theorem: $T(n) = T(\frac{n}{2}) + O(n)$ because there is 1 recursive call and the problem is halved and it takes $O(n)$ time to add n bits. However, this equation would give me $\Theta(n)$ which is wrong.  What step did I miss in the recurrence equation?


texts: How Do Common Pathfinding Algorithms Compare To Human Process

texts: This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A*) compares to the process humans use in different pathfinding situations (given the same information). Are these processes similar?


texts: Algorithmic Design to Undo Rotation of Array

texts:
An array $A$ of $n$ distinct, ascending integers is rotated to the right by $k$ positions, resulting in the array $A_{k}$.

That is, the element at index $i$ in $A$ is moved to index $(i+k)\mod n$ in $A_k$.

Devise a $\Theta(\lg(n))$ algorithm to recover $k$ from $A_k$ where $\lg(n) = \log_2(n)$.

To clarify, the algorithm needs to determine what the shift $k$ applied to $A$ was which resulted in $A_k$. Thus, $A_k$ is sufficient enough for the algorithm to work with in order to determine the shift since we know that $A$ consisted of ascending integers.

Any help or insight would be greatly appreciated!


texts: Algorithm Design Patterns vs. Algorithm Strategies vs. Algorithm Design Techniques vs. Algorithm Design Paradigms

texts:
I often encounter these terms, seemingly bearing same semantics and meaning. I'm almost sure they mean same - the types of Algorithms categorized based on their implementation strategy/paradigm.

Just wondering if I'm right and I get this correct, because, again - in different books/courses these terms are encountered in the same context. I'm kind of a very critical to the exactness of the terms I read.

Could you please confirm or reject my assumption?


texts: Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?

texts:
Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle.

We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking out one row and column, and then taking the determinant of that sub-matrix.

Let's call that determinant t (i.e. there are t possible spanning trees in total).

What is the quickest known algorithm such that its input is G and it's output is one of t possible spanning trees of G (where each spanning tree has as close to $\frac{1}{t}$ chance of being selected as possible)?

Here's the algorithm I'm using currently.

Definitions:

$V_{visited}$ - vertices already traversed

$E_{visited}$ - edges already traversed

$V_C$ - V \ V_visited (i.e. vertices in V but not in $V_{visited}$)

N($V_{visited}$) - the set of all vertices v in $V_C$ such that an edge
exists between v and some vertex in $V_{visited}$

Algorithm:

sample $v_0$ from V randomly
add $v_0$ to $V_{visited}$
sample $v_1$ from N($V_{visited}$) randomly
add ($v_0$, $v_1$) to $E_{visited}$
sample $v_2$ from N($V_{visited}$) randomly
add ($v_*$, $v_2$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_2$'s neighbors in $V_{visited}$)

...

sample $v_{|V| - 1}$ (the second to last vertex in V) randomly
add ($v_*$, $v_{|V| - 1}$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_{|V| - 1}$'s neighbors in $V_{visited}$)
sample $v_{|V|}$ (the last vertex in V)
add (v*, $v_{|V|}$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_{|V|}$'s neighbors in $V_{visited}$)

Now $V_{visited}$ and $E_{visited}$ represents a random spanning tree of G.

Is this the most efficient way of getting a random spanning tree? Is there a more efficient way? (Bonus points if it's parallelizable.)


texts: why p1 misses it first deadline? Rate monotonic scheduling

texts:
I understand that rate monotonic scheduling assigns a priority to a process based on the periodicity of the tasks it generates and the process with the shortest inter-task period has the highest priority but i am confused as to why in this particular scenario p1 will miss its first deadline?

PS Sorry but english isn't my first language


texts:
I've been playing around with a simple probabilistic data structure which is very similar to a Bloom filter. Where a Bloom filter would use $k$ independent hash functions to choose $k$ of the $m$ bits to set, this structure uses $m$ hash functions, and sets each bit with probability $p$.

This structure doesn't produce as low a false-positive rate as Bloom filters, but it seems to be extremely fast to compute, particularly if $m$ is some multiple of the machine word size and $p = 2^{-b}$ for some integer $b$: The hash functions can be computed in parallel by AND-ing $b$ independent $m$-bit hashes, and no dependent indexing or variable bitshifts are required.

I'm certain someone's come up with this idea before me, and done a lot more advanced analysis and comparison of it than I'm qualified to do. Is there a particular name for this type of structure?


texts: How to find a minimum cut of a network flow?

texts:
I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph.

Could someone explain how to find the minimum cut of this graph? I THINK the minimum capacity is 4.


texts: We make $n$ insertions and each insertion targets a list of size $k\le n$, so we can make a binary search which takes maximum $\log k\le \log n$. So why isn't the running time of selection sort $O(n \log n)?$


texts:
Suppose you have two heaps each containing $2^k - 1$ elements.

Design an efficient algorithm for merging these two heaps into a single heap.

My approach was to assume two heaps are maxheap. Create one node with value $-\infty$ and attach one heap as left subtree and another as right subtree, and call the heapify procedure. So it should take $O(\log(2(2^k-1)+1))=\log(k)$ time.

But my confusion is $-\infty$ valued node doesn't necessarily go at the last node of heap.


texts: About to find the maximum sum of transaction within a time window period

texts:
I received hundreds of transactions within one week. Each transaction has amount. I'd like to create an algorithm to find the maximum amount within 24 hour time window period. I know how to do that by creating a nested loop. But I am looking for a better performance algorithm such as n*Log(n) time complexity.

For example, the transaction data looks like:

[
{'05-05-2019:10.00.00', 100},
{'05-05-2019:11.00.00', 100},
{'05-05-2019:12.00.00', 100},
{'05-06-2019:10.00.00', 100},
{'05-06-2019:11.00.00', 100},
{'05-07-2019:10.30.00', 100}
]

For the above data, there are 6 transactions across 2 days. When calculate the 24 hours period time of transactions, there are 4 time period. The first three transactions happens within 24 hours which has a total amount as 300. The second time period includes three transactions, 2ed, 3rd and 4th  which has a total of 300 amount. The third time period is 3rd, 4th and 5th has 300 amount. The fourth time period is 4th and 5th which is 200. The last time period is the last two which is 200. So the maximum amount is 300.


texts: Asymptotic analysis for quicksort on special case

texts:
I have the following problem for homework:

Given an array of the form  $[m+1, m+2,..., n, 1, 2,..., m]$ as an input,
analyze quicksort's run time complexity.
TIP: check for $m > \frac{n}{2}$  and  $m \le \frac{n}{2}$

The quicksort algorithm is the deterministic version from CLRS.

I have a sense of what's going on but I'm having trouble proving it properly.

I arrived at the following formula:
$$\begin{align*}
    T(n, m) &= T(n-m, m) + \theta (m^2) + \theta (n) \\
            &= \cdots \\
            &= T(n-(i+1)m, m) + i\theta(m^2) + \sum_{k=0}^{i} \theta(n-km)
\end{align*}$$ from the following reasoning:

at each "step" $i$ the partition will swap the $m$ smallest numbers (located at the end of the sub-array)  with the next $m$ smallest numbers (located at the beginning of the sub-array), keeping their sorted order.
The sub array is of size $n-im$, so the partition takes $\theta(n-im)$.
Then perform the first recursive call on the $m-1$ smallest numbers on the left of the sub-array for ~$\theta(m^2)$.
Next we perform the next recursive call on an sub-array of size $(n-(i+1)m)$.

We can easily see when this will end with a mod operation.
(I understand there is a bit additional work even after we can't sub $m$ smallest numbers anymore but that's not very important so omitted).

Now, my issues are:

I don't understand how to treat $m$ and $n$. $m$ is somewhat dependent on $n$ because it cannot grow indefinitely without $n$ growing as well. But on the other hand, it doesn't depend directly on $n$.
If I substitute the end condition I get an expression with both $n$ and $m$ which I believe I should find a way to express in terms of $n$ alone but I don't know how.

I know I omitted alot of reasoning, details and formalism but it's got quite long anyhow so I hope it's clear enough.
If not, I will be more than happy to clarify.

I'd appreciate any help or suggestions.

EDIT: here is the pseudocode for partition and quicksort:

Partition: http://qph.is.quoracdn.net/main-qimg-65c54b3e9b6fef01a5ff7543ed3a3092?convert_to_webp=true
Quicksort: http://www2.hawaii.edu/~suthers/courses/ics311s14/Notes/Topic-10/pseudocode-quicksort.jpg


texts: Does Church-Turing thesis also apply to artificial intelligence?

texts:
By Church-Turing's thesis, it is impossible to design an algorithm to decide the halting problem.

Does the word algorithm in this context include artificial
intelligence or not, that is, does Church-Turing thesis also apply to artificial intelligence?

Is it possible to design an intelligence system in the future to decide this problem, or, by Church-Turing thesis, no AI will also be able to decide the halting problem?


texts: Why does the concatenation operation imply the empty string?

texts:
I'm a noob reading Michael Sipser's Introduction to the Theory of Computation, and I'm at a part where he's demonstrating how to construct finite automata that accept languages described by regular expressions. He does this by giving regular expressions, breaking them down into simpler regular expressions that represent the constituent pieces of the whole expression, creating a finite automata for each piece of the expression, and finally connecting them with the finite automata at the bottom that accepts the language described by the regular expression.

One of his examples is the sequence of finite automata in the picture attached, meant to illustrate how one might work through creating a finite automata that accepts the regular expression $(a\cup b)^* aba$.

With his definitions of union, concatenation, and star below.

Concatenation: $A+B=\{xy\mid x\in A\wedge y \in B\}$

Star: $A* = \{x_1x_2...x_k \mid k\geq 0 \wedge x_i \in A\}$

Union: $A\cup B = \{x\mid x\in A\vee x\in B\}$

At one point in the book he explains that two characters next to one another with no symbol between can imply concatenation so I am interpreting the "$aba$" piece as $a+b+a$.

I would think a finite automata that accepts $aba$ would have four states, with an "$a$" transition arrow between the first and second states, a "$b$" transition arrow between the second and third states, and an "$a$" transition arrow between the third state and the accept (fourth) state. The diagram instead is similar to what I imagined but adding a state with an empty string transition arrow between each state I described. See the 5th diagram, given for expression $aba $below $(a \cup b)^*aba$ illustrating how one might go about constructing a finite automaton that accepts the language described by that regular expression.">

These states with associated empty string transition arrows appear in both of the regular expression examples with concatenation he gives, so I must be misunderstanding something. There's a section in the book when he introduces nondeterministic finite automata in part of an effort to prove that regular languages are closed under the concatenation operation and mentions that "In general, an NFA may have arrows labeled with members of the alphabet or $\varepsilon$", and I figure the answer must have something to do with that, but I still don't understand why.


texts: Dynamic Programming - Thief Variation Probem

texts:
I've encountered a Dynamic Programming problem which is a variation of the thief one.

Say you are a thief and you are given a number of houses in a row you should rob :

$$House_1,House_2 \dots House_N$$

with each house having the following values : $$(x_i \geq y_i \geq z_i \gt0)$$

You profit X  if you rob a house but none of the adjacent houses.

You profit Y  if you rob a house and exactly one of the adjacent houses.

You profit Z  if you rob a house and both of the adjacent houses.

Cases with houses A-B-C would be :

$$Profit(001)=0+0+C_x$$
$$Profit(101)=A_x+0+C_x$$
$$Profit(110)=A_y+B_y+0$$
$$Profit(111)=A_y+B_z+C_y$$

Where 1 stands for robbing the house and 0 for not robbing the house

Obviously you can't utilize the Z value for the first and the last house and each set of values is random.

Now the question is : Which houses should you rob to get the maximum profit?

My main issue is that i can't establish a base case for this problem.

At first i thought of creating a N*M array with M being the maximum amount of houses i can rob from 0-N when every house is not robbed and think like : Rob it - Don't rob it but came up with nothing.

Any tips or directions would be appreciated.

Thanks in advance.


texts:
Possible Duplicate:
  Is the k-clique problem NP-complete?

I've been lately reading about the clique problem, specifically, the variety of the clique problem of deciding whether a given graph $G$ with $n$ nodes has a clique of at least size $k$.

Why is this problem $NP$-complete? Could one solve this problem in polynomial time by trying out each possible group of $k$ nodes in the graph and checking if this group is a clique?

Wouldn't this algorithm run in time $O(\binom{n}{k})$ or $O(\frac{n!}{(n-k)!k!})$ or $O(n^2)$?


texts:
I started to learn about compilers and interpreters. But I still can't understand how program execution happens under the hood.
This is what I have understood so far.
Compiler
The Compiler does not run a code, instead, just converts the code into another (low-level) code. This part is clear to me.
Interpreter
First I thought the interpreter converts some high-level code or byte code into machine language and then executes it.
But then I realized that interpreters not convert code into machine code, instead, that instruction becomes an input to the interpreter application and it activate some particular function of the interpreter, which has been already converted into the machine code.
Refer to this pseudo code. Imagine I create a programming language that is interpreted by an interpreter created by python.
add 5 + 3
sub 5 - 3

Interpreter
def add(a, b):
    print(a+b)

def sub(a,b)
    print(a-b)

# Parsing
code = [] #list of instructinos

for instruction in code:
    if instruction.command == "add":
        add(instruction.a, instruction.b)
    elif instruction.command == "sub":
        sub(instruction.a, instruction.b)
    else:
        print("incorrect instruction)

I am not sure whether my understanding of the interpreter is correct. If it is not, I want to know how the interpreter works internally. I mean how the interpreter executes a code without translating it into machine code.


texts: How many RAW dependencies are present in these instructions?

texts:
What is the number of RAW dependencies in below set of instructions?

I1: R1 = R2 - R3
I2: R2 = R1 + R3
I3: R3 = R1 + R2
I4: R1 = R2 - R2

I can see the following RAW dependencies in it:

  $I_2-I_1\ for\ R_1$ ......... (a)

  $I_3-I_1\ for\ R_1$ ......... (b)

  $I_3-I_2\ for\ R_2$ ......... (c)

  $I_4-I_2\ for\ R_2$ ......... (d)

I think taking (a) and (b) implies that (c) has already been included. So, should this be counted as 4 RAW dependencies or 3 RAW dependencies?

https://en.wikipedia.org/wiki/Hazard_(computer_architecture)#Read_after_write_(RAW)


texts: If a problem A has a poly-time reduction to a problem B in co-NP, is A in co-NP as well?

texts:
i.e. $A\leq_pB\:\wedge\:B\in\text{co-NP}\rightarrow A\in\text{co-NP}$ ?
I feel like it's the case but I can't think of a straightforward proof.
Clarification: I am talking about polynomial-time Turing reductions.


texts: Is bounded waiting ensured in given version of Dekker's solution for critical section problem?

texts:
William Stallings discuss various step by step process in developing Dekker's algorithm in his Operating Systems book. In process, he reaches to following version of algorithm (which is incomplete as it results in livelock):

1
2    /*    PROCESS 0    */
3    .
4    .
5    flag[0] = true;
6    while (flag[1])
7    {
8       flag[0] = false;
9       /* delay */ ;
10       flag[0] = true;
11    }
12    /* critical section*/;
13    flag[0] = false;.
14
15    .
16
17    /*    PROCESS 1   */
18    .
19    .
20    flag[1] = true;
21    while (flag[0])
22    {
23       flag[1] = false;
24       /* do */ ;
25       flag[1] = true;
26    }
27    /* critical section*/;
28    flag[1] = false;.
29
30    .
31
32

I want to know whether above algorithm satisfies the "bounded waiting" requirement of critical section solution.

My current opinion is that, if process 0 fails on lines 6,7,8,11,12,13,14,15, that is all lines where flag[0] is already set to true, then process 1 will be blocked and hence will result in unbounded waiting. Am I correct?

Also is there easy way to find whether given/proposed algorithm for critical section problem solution satisfies "bounded waiting" requirement?


texts: How to apply the pumping lemma for CFGs to languages that contain the empty string

texts:
The pumping lemma states that if we can split a string w (taken from a context-free language L) as uvxyz with conditions |vy|>=1 |vxy|<=p |w|>=p for some p then $uv^ixy^iz$ is in L for any i.

However, some context-free languages include the empty string, which has length 0. How can we possibly split the empty string to satisfy the condition |vy|>=1?

For instance, the following language $\{0^n1^n0^n1^n|n>=0 \} $ contains the empty string but is not context-free, so how can I ensure a string taken from it can we split as uvxyz with |vy|>=1?

Thanks!


texts: I am looking for good resources which have classified and solved typical large scale data processing in MapReduce framework (like graph algorithms, statistics, numerical algorithms ...). Any help is appreciated!


texts: Integer Programming Traveling Salesman - Checking if Tour is Complete

texts:
I'm reading a Wikipedia article on the Traveling Salesman problem as an Integer Programming formulation (http://en.wikipedia.org/wiki/Travelling_salesman_problem). The authors have all their constraints and I don't understand the final one. The following statement is in there.

  To prove that every feasible solution contains only one closed sequence of cities, it
      suffices to show that every subtour in a feasible solution passes through city 0 (noting that
      the equalities ensure there can only be one such tour). For if we sum all the   inequalities
      corresponding to x[ij]=1 for any subtour of k steps not passing through city 0, we obtain:
      n * k <= (n-1) * k

I specifically don't understand the "For if we sum all the inequalities..." part. Sum which inequalites?

A little further the author states the following.

  Without loss of generality, define the tour as originating (and ending) at city 0.
      Choose u[i]=t if city i is visited in step t (i, t = 1, 2, ..., n). Then
      u[i]-u[j] <= n-1,
      since u_i can be no greater than n and u_j can be no less than 1; hence the
      constraints are satisfied whenever x_{ij}=0. For x_{ij}=1, we have:

  u[i] - u[j] + nx[ij] = (t) - (t+1) + n = n-1,

  satisfying the constraint.

I guess I don't understand how this detects that we pass through all the nodes.

Okay, looking at this some more, I think I've discovered a bit more. This equation is the MTZ formulation (Miller-Tucker-Zemlin) and it's geared at finding subtours.

Having digested some snippets from papers like Gabor Pataki's Teaching Integer Programming Formulations using the Traveling Salesman Problem, there's a statement in there that if a subtour did not contain node 1, then along this subtour the u[i] value would have to increase to infinity. I'm not 100% sure, but what I think this means is that if you had nodes 3 and 4 linked together (edge from 3 to 4 and another from 4 to 3), you would have the following constraints...

$u_3 - u_4 + 1 \le (n-1)*(1-x_{34}) \le 0$

$u_4 - u_3 + 1 \le (n-1)*(1-x_{43}) \le 0$

The contradiction here is that $u_4$ is one step greater than $u_3$ which is one step greater than $u_4$.


texts: Example of height-balanced tree that is not weight-balanced

texts:
Following this question : Two definitions of balanced binary trees

I am having a hard time making sense of the proofs provided and I'm looking for an example of a simple binary tree that is height-balanced but not weight-balanced.

This would mean that we could clearly see the height differences of two sub-trees being more than one while the maximum depth difference of any two leave nodes would never be more than one.

Does such an example exist?

EDIT: This question was asked because I misunderstood the inner-node concept. I was looking for a tree example where the height of two sub trees differed by more than one while the the maximum depth and minimum depth had a difference of no more than one.


texts:
If it is given that a program has a worst case running time of $O(n)$, then is it still okay to define the running time as being $O(n^2)$. By definition, this seems corrects since Big-Oh is essentially an upper bound.

But, since we already established a worst case running time, can this still be correct.